[demangler] Recopy the demangler from libcxxabi.

Some significant work has gone into libcxxabi's copy of this file:
  - Uses an AST to represent mangled names.
  - Support/bugfixes for many C++ features.
  - Uses LLVM coding style.

llvm-svn: 327859

1 files changed, 4521 insertions, 3943 deletions

diff --git a/llvm/lib/Demangle/ItaniumDemangle.cpp b/llvm/lib/Demangle/ItaniumDemangle.cpp
index 9c2258f5b93..7ac3eaddf4d 100644
--- a/llvm/lib/Demangle/ItaniumDemangle.cpp
+++ b/llvm/lib/Demangle/ItaniumDemangle.cpp
@@ -1,4 +1,4 @@
-//===- ItaniumDemangle.cpp ------------------------------------------------===//
+//===------------------------- ItaniumDemangle.cpp ------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
@@ -7,20 +7,22 @@
 //
 //===----------------------------------------------------------------------===//
 
+// FIXME: (possibly) incomplete list of features that clang mangles that this
+// file does not yet support:
+//   - enable_if attribute
+//   - C++ modules TS
+//   - All C++14 and C++17 features
+
 #include "llvm/Demangle/Demangle.h"
 #include "llvm/Support/Compiler.h"
-
-// This file exports a single function: llvm::itanium_demangle.
-// It also has no dependencies on the rest of llvm. It is implemented this way
-// so that it can be easily reused in libcxxabi.
-
+#include <vector>
 #include <algorithm>
-#include <cctype>
+#include <numeric>
+#include <cassert>
+#include <cstdio>
 #include <cstdlib>
 #include <cstring>
-#include <numeric>
-#include <string>
-#include <vector>
+#include <cctype>
 
 #ifdef _MSC_VER
 // snprintf is implemented in VS 2015
@@ -29,1953 +31,2270 @@
 #endif
 #endif
 
-enum {
-  unknown_error = -4,
-  invalid_args = -3,
-  invalid_mangled_name,
-  memory_alloc_failure,
-  success
+namespace {
+
+class StringView {
+  const char *First;
+  const char *Last;
+
+public:
+  template <size_t N>
+  StringView(const char (&Str)[N]) : First(Str), Last(Str + N - 1) {}
+  StringView(const char *First_, const char *Last_) : First(First_), Last(Last_) {}
+  StringView() : First(nullptr), Last(nullptr) {}
+
+  StringView substr(size_t From, size_t To) {
+    if (To >= size())
+      To = size() - 1;
+    if (From >= size())
+      From = size() - 1;
+    return StringView(First + From, First + To);
+  }
+
+  StringView dropFront(size_t N) const {
+    if (N >= size())
+      N = size() - 1;
+    return StringView(First + N, Last);
+  }
+
+  bool startsWith(StringView Str) const {
+    if (Str.size() > size())
+      return false;
+    return std::equal(Str.begin(), Str.end(), begin());
+  }
+
+  const char &operator[](size_t Idx) const { return *(begin() + Idx); }
+
+  const char *begin() const { return First; }
+  const char *end() const { return Last; }
+  size_t size() const { return static_cast<size_t>(Last - First); }
+  bool empty() const { return First == Last; }
 };
 
-enum {
-  CV_const = (1 << 0),
-  CV_volatile = (1 << 1),
-  CV_restrict = (1 << 2),
+bool operator==(const StringView &LHS, const StringView &RHS) {
+  return LHS.size() == RHS.size() &&
+         std::equal(LHS.begin(), LHS.end(), RHS.begin());
+}
+
+// Stream that AST nodes write their string representation into after the AST
+// has been parsed.
+class OutputStream {
+  char *Buffer;
+  size_t CurrentPosition;
+  size_t BufferCapacity;
+
+  // Ensure there is at least n more positions in buffer.
+  void grow(size_t N) {
+    if (N + CurrentPosition >= BufferCapacity) {
+      BufferCapacity *= 2;
+      if (BufferCapacity < N + CurrentPosition)
+        BufferCapacity = N + CurrentPosition;
+      Buffer = static_cast<char *>(std::realloc(Buffer, BufferCapacity));
+    }
+  }
+
+public:
+  OutputStream(char *StartBuf, size_t Size)
+      : Buffer(StartBuf), CurrentPosition(0), BufferCapacity(Size) {}
+
+  /// If a ParameterPackExpansion (or similar type) is encountered, the offset
+  /// into the pack that we're currently printing.
+  unsigned CurrentPackIndex = std::numeric_limits<unsigned>::max();
+
+  OutputStream &operator+=(StringView R) {
+    size_t Size = R.size();
+    if (Size == 0)
+      return *this;
+    grow(Size);
+    memmove(Buffer + CurrentPosition, R.begin(), Size);
+    CurrentPosition += Size;
+    return *this;
+  }
+
+  OutputStream &operator+=(char C) {
+    grow(1);
+    Buffer[CurrentPosition++] = C;
+    return *this;
+  }
+
+  size_t getCurrentPosition() const { return CurrentPosition; };
+
+  char back() const {
+    return CurrentPosition ? Buffer[CurrentPosition - 1] : '\0';
+  }
+
+  bool empty() const { return CurrentPosition == 0; }
+
+  char *getBuffer() { return Buffer; }
+  char *getBufferEnd() { return Buffer + CurrentPosition - 1; }
+  size_t getBufferCapacity() { return BufferCapacity; }
+};
+
+template <class T>
+class SwapAndRestore {
+  T &Restore;
+  T OriginalValue;
+public:
+  SwapAndRestore(T& Restore_, T NewVal)
+      : Restore(Restore_), OriginalValue(Restore) {
+    Restore = std::move(NewVal);
+  }
+  ~SwapAndRestore() { Restore = std::move(OriginalValue); }
+
+  SwapAndRestore(const SwapAndRestore &) = delete;
+  SwapAndRestore &operator=(const SwapAndRestore &) = delete;
 };
 
-template <class C>
-static const char *parse_type(const char *first, const char *last, C &db);
-template <class C>
-static const char *parse_encoding(const char *first, const char *last, C &db);
-template <class C>
-static const char *parse_name(const char *first, const char *last, C &db,
-                              bool *ends_with_template_args = 0);
-template <class C>
-static const char *parse_expression(const char *first, const char *last, C &db);
-template <class C>
-static const char *parse_template_args(const char *first, const char *last,
-                                       C &db);
-template <class C>
-static const char *parse_operator_name(const char *first, const char *last,
-                                       C &db);
-template <class C>
-static const char *parse_unqualified_name(const char *first, const char *last,
-                                          C &db);
-template <class C>
-static const char *parse_decltype(const char *first, const char *last, C &db);
+// Base class of all AST nodes. The AST is built by the parser, then is
+// traversed by the printLeft/Right functions to produce a demangled string.
+class Node {
+public:
+  enum Kind : unsigned char {
+    KDotSuffix,
+    KVendorExtQualType,
+    KQualType,
+    KConversionOperatorType,
+    KPostfixQualifiedType,
+    KElaboratedTypeSpefType,
+    KNameType,
+    KAbiTagAttr,
+    KObjCProtoName,
+    KPointerType,
+    KLValueReferenceType,
+    KRValueReferenceType,
+    KPointerToMemberType,
+    KArrayType,
+    KFunctionType,
+    KNoexceptSpec,
+    KDynamicExceptionSpec,
+    KFunctionEncoding,
+    KLiteralOperator,
+    KSpecialName,
+    KCtorVtableSpecialName,
+    KQualifiedName,
+    KEmptyName,
+    KVectorType,
+    KParameterPack,
+    KTemplateArgumentPack,
+    KParameterPackExpansion,
+    KTemplateArgs,
+    KNameWithTemplateArgs,
+    KGlobalQualifiedName,
+    KStdQualifiedName,
+    KExpandedSpecialSubstitution,
+    KSpecialSubstitution,
+    KCtorDtorName,
+    KDtorName,
+    KUnnamedTypeName,
+    KClosureTypeName,
+    KStructuredBindingName,
+    KExpr,
+    KBracedExpr,
+    KBracedRangeExpr,
+  };
+
+  static constexpr unsigned NoParameterPack =
+    std::numeric_limits<unsigned>::max();
+  unsigned ParameterPackSize = NoParameterPack;
+
+  Kind K;
+
+  /// Three-way bool to track a cached value. Unknown is possible if this node
+  /// has an unexpanded parameter pack below it that may affect this cache.
+  enum class Cache : unsigned char { Yes, No, Unknown, };
+
+  /// Tracks if this node has a component on its right side, in which case we
+  /// need to call printRight.
+  Cache RHSComponentCache;
+
+  /// Track if this node is a (possibly qualified) array type. This can affect
+  /// how we format the output string.
+  Cache ArrayCache;
+
+  /// Track if this node is a (possibly qualified) function type. This can
+  /// affect how we format the output string.
+  Cache FunctionCache;
+
+  Node(Kind K_, unsigned ParameterPackSize_ = NoParameterPack,
+       Cache RHSComponentCache_ = Cache::No, Cache ArrayCache_ = Cache::No,
+       Cache FunctionCache_ = Cache::No)
+      : ParameterPackSize(ParameterPackSize_), K(K_),
+        RHSComponentCache(RHSComponentCache_), ArrayCache(ArrayCache_),
+        FunctionCache(FunctionCache_) {}
+
+  bool containsUnexpandedParameterPack() const {
+    return ParameterPackSize != NoParameterPack;
+  }
 
-// <number> ::= [n] <non-negative decimal integer>
+  bool hasRHSComponent(OutputStream &S) const {
+    if (RHSComponentCache != Cache::Unknown)
+      return RHSComponentCache == Cache::Yes;
+    return hasRHSComponentSlow(S);
+  }
 
-static const char *parse_number(const char *first, const char *last) {
-  if (first != last) {
-    const char *t = first;
-    if (*t == 'n')
-      ++t;
-    if (t != last) {
-      if (*t == '0') {
-        first = t + 1;
-      } else if ('1' <= *t && *t <= '9') {
-        first = t + 1;
-        while (first != last && std::isdigit(*first))
-          ++first;
-      }
+  bool hasArray(OutputStream &S) const {
+    if (ArrayCache != Cache::Unknown)
+      return ArrayCache == Cache::Yes;
+    return hasArraySlow(S);
+  }
+
+  bool hasFunction(OutputStream &S) const {
+    if (FunctionCache != Cache::Unknown)
+      return FunctionCache == Cache::Yes;
+    return hasFunctionSlow(S);
+  }
+
+  Kind getKind() const { return K; }
+
+  virtual bool hasRHSComponentSlow(OutputStream &) const { return false; }
+  virtual bool hasArraySlow(OutputStream &) const { return false; }
+  virtual bool hasFunctionSlow(OutputStream &) const { return false; }
+
+  /// If this node is a pack expansion that expands to 0 elements. This can have
+  /// an effect on how we should format the output.
+  bool isEmptyPackExpansion() const;
+
+  void print(OutputStream &S) const {
+    printLeft(S);
+    if (RHSComponentCache != Cache::No)
+      printRight(S);
+  }
+
+  // Print the "left" side of this Node into OutputStream.
+  virtual void printLeft(OutputStream &) const = 0;
+
+  // Print the "right". This distinction is necessary to represent C++ types
+  // that appear on the RHS of their subtype, such as arrays or functions.
+  // Since most types don't have such a component, provide a default
+  // implemenation.
+  virtual void printRight(OutputStream &) const {}
+
+  virtual StringView getBaseName() const { return StringView(); }
+
+  // Silence compiler warnings, this dtor will never be called.
+  virtual ~Node() = default;
+
+#ifndef NDEBUG
+  LLVM_DUMP_METHOD void dump() const {
+    char *Buffer = static_cast<char*>(std::malloc(1024));
+    OutputStream S(Buffer, 1024);
+    print(S);
+    S += '\0';
+    printf("Symbol dump for %p: %s\n", (const void*)this, S.getBuffer());
+    std::free(S.getBuffer());
+  }
+#endif
+};
+
+class NodeArray {
+  Node **Elements;
+  size_t NumElements;
+
+public:
+  NodeArray() : Elements(nullptr), NumElements(0) {}
+  NodeArray(Node **Elements_, size_t NumElements_)
+      : Elements(Elements_), NumElements(NumElements_) {}
+
+  bool empty() const { return NumElements == 0; }
+  size_t size() const { return NumElements; }
+
+  Node **begin() const { return Elements; }
+  Node **end() const { return Elements + NumElements; }
+
+  Node *operator[](size_t Idx) const { return Elements[Idx]; }
+
+  void printWithComma(OutputStream &S) const {
+    bool FirstElement = true;
+    for (size_t Idx = 0; Idx != NumElements; ++Idx) {
+      if (Elements[Idx]->isEmptyPackExpansion())
+        continue;
+      if (!FirstElement)
+        S += ", ";
+      FirstElement = false;
+      Elements[Idx]->print(S);
     }
   }
-  return first;
-}
+};
 
-namespace {
-template <class Float> struct float_data;
+class DotSuffix final : public Node {
+  const Node *Prefix;
+  const StringView Suffix;
 
-template <> struct float_data<float> {
-  static const size_t mangled_size = 8;
-  static const size_t max_demangled_size = 24;
-  static const char *spec;
+public:
+  DotSuffix(Node *Prefix_, StringView Suffix_)
+      : Node(KDotSuffix), Prefix(Prefix_), Suffix(Suffix_) {}
+
+  void printLeft(OutputStream &s) const override {
+    Prefix->print(s);
+    s += " (";
+    s += Suffix;
+    s += ")";
+  }
 };
-const char *float_data<float>::spec = "%af";
 
-template <> struct float_data<double> {
-  static const size_t mangled_size = 16;
-  static const size_t max_demangled_size = 32;
-  static const char *spec;
+class VendorExtQualType final : public Node {
+  const Node *Ty;
+  StringView Ext;
+
+public:
+  VendorExtQualType(Node *Ty_, StringView Ext_)
+      : Node(KVendorExtQualType, Ty_->ParameterPackSize),
+        Ty(Ty_), Ext(Ext_) {}
+
+  void printLeft(OutputStream &S) const override {
+    Ty->print(S);
+    S += " ";
+    S += Ext;
+  }
 };
 
-const char *float_data<double>::spec = "%a";
+enum FunctionRefQual : unsigned char {
+  FrefQualNone,
+  FrefQualLValue,
+  FrefQualRValue,
+};
 
-template <> struct float_data<long double> {
-#if defined(__mips__) && defined(__mips_n64) || defined(__aarch64__) ||        \
-    defined(__wasm__)
-  static const size_t mangled_size = 32;
-#elif defined(__arm__) || defined(__mips__) || defined(__hexagon__)
-  static const size_t mangled_size = 16;
-#else
-  static const size_t mangled_size =
-      20; // May need to be adjusted to 16 or 24 on other platforms
-#endif
-  static const size_t max_demangled_size = 40;
-  static const char *spec;
+enum Qualifiers {
+  QualNone = 0,
+  QualConst = 0x1,
+  QualVolatile = 0x2,
+  QualRestrict = 0x4,
 };
 
-const char *float_data<long double>::spec = "%LaL";
+void addQualifiers(Qualifiers &Q1, Qualifiers Q2) {
+  Q1 = static_cast<Qualifiers>(Q1 | Q2);
 }
 
-template <class Float, class C>
-static const char *parse_floating_number(const char *first, const char *last,
-                                         C &db) {
-  const size_t N = float_data<Float>::mangled_size;
-  if (static_cast<std::size_t>(last - first) > N) {
-    last = first + N;
-    union {
-      Float value;
-      char buf[sizeof(Float)];
-    };
-    const char *t = first;
-    char *e = buf;
-    for (; t != last; ++t, ++e) {
-      if (!isxdigit(*t))
-        return first;
-      unsigned d1 = isdigit(*t) ? static_cast<unsigned>(*t - '0')
-                                : static_cast<unsigned>(*t - 'a' + 10);
-      ++t;
-      unsigned d0 = isdigit(*t) ? static_cast<unsigned>(*t - '0')
-                                : static_cast<unsigned>(*t - 'a' + 10);
-      *e = static_cast<char>((d1 << 4) + d0);
-    }
-    if (*t == 'E') {
-#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
-      std::reverse(buf, e);
-#endif
-      char num[float_data<Float>::max_demangled_size] = {0};
-      int n = snprintf(num, sizeof(num), float_data<Float>::spec, value);
-      if (static_cast<std::size_t>(n) >= sizeof(num))
-        return first;
-      db.names.push_back(std::string(num, static_cast<std::size_t>(n)));
-      first = t + 1;
+class QualType : public Node {
+protected:
+  const Qualifiers Quals;
+  const Node *Child;
+
+  void printQuals(OutputStream &S) const {
+    if (Quals & QualConst)
+      S += " const";
+    if (Quals & QualVolatile)
+      S += " volatile";
+    if (Quals & QualRestrict)
+      S += " restrict";
+  }
+
+public:
+  QualType(Node *Child_, Qualifiers Quals_)
+      : Node(KQualType, Child_->ParameterPackSize, Child_->RHSComponentCache,
+             Child_->ArrayCache, Child_->FunctionCache),
+        Quals(Quals_), Child(Child_) {}
+
+  bool hasRHSComponentSlow(OutputStream &S) const override {
+    return Child->hasRHSComponent(S);
+  }
+  bool hasArraySlow(OutputStream &S) const override {
+    return Child->hasArray(S);
+  }
+  bool hasFunctionSlow(OutputStream &S) const override {
+    return Child->hasFunction(S);
+  }
+
+  void printLeft(OutputStream &S) const override {
+    Child->printLeft(S);
+    printQuals(S);
+  }
+
+  void printRight(OutputStream &S) const override { Child->printRight(S); }
+};
+
+class ConversionOperatorType final : public Node {
+  const Node *Ty;
+
+public:
+  ConversionOperatorType(Node *Ty_)
+      : Node(KConversionOperatorType, Ty_->ParameterPackSize), Ty(Ty_) {}
+
+  void printLeft(OutputStream &S) const override {
+    S += "operator ";
+    Ty->print(S);
+  }
+};
+
+class PostfixQualifiedType final : public Node {
+  const Node *Ty;
+  const StringView Postfix;
+
+public:
+  PostfixQualifiedType(Node *Ty_, StringView Postfix_)
+      : Node(KPostfixQualifiedType, Ty_->ParameterPackSize),
+        Ty(Ty_), Postfix(Postfix_) {}
+
+  void printLeft(OutputStream &s) const override {
+    Ty->printLeft(s);
+    s += Postfix;
+  }
+};
+
+class NameType final : public Node {
+  const StringView Name;
+
+public:
+  NameType(StringView Name_) : Node(KNameType), Name(Name_) {}
+
+  StringView getName() const { return Name; }
+  StringView getBaseName() const override { return Name; }
+
+  void printLeft(OutputStream &s) const override { s += Name; }
+};
+
+class ElaboratedTypeSpefType : public Node {
+  StringView Kind;
+  Node *Child;
+public:
+  ElaboratedTypeSpefType(StringView Kind_, Node *Child_)
+      : Node(KElaboratedTypeSpefType), Kind(Kind_), Child(Child_) {
+    ParameterPackSize = Child->ParameterPackSize;
+  }
+
+  void printLeft(OutputStream &S) const override {
+    S += Kind;
+    S += ' ';
+    Child->print(S);
+  }
+};
+
+class AbiTagAttr final : public Node {
+  const Node* Base;
+  StringView Tag;
+public:
+  AbiTagAttr(const Node* Base_, StringView Tag_)
+      : Node(KAbiTagAttr, Base_->ParameterPackSize, Base_->RHSComponentCache,
+             Base_->ArrayCache, Base_->FunctionCache),
+        Base(Base_), Tag(Tag_) {}
+
+  void printLeft(OutputStream &S) const override {
+    Base->printLeft(S);
+    S += "[abi:";
+    S += Tag;
+    S += "]";
+  }
+};
+
+class ObjCProtoName : public Node {
+  Node *Ty;
+  StringView Protocol;
+
+  friend class PointerType;
+
+public:
+  ObjCProtoName(Node *Ty_, StringView Protocol_)
+      : Node(KObjCProtoName), Ty(Ty_), Protocol(Protocol_) {}
+
+  bool isObjCObject() const {
+    return Ty->getKind() == KNameType &&
+           static_cast<NameType *>(Ty)->getName() == "objc_object";
+  }
+
+  void printLeft(OutputStream &S) const override {
+    Ty->print(S);
+    S += "<";
+    S += Protocol;
+    S += ">";
+  }
+};
+
+class PointerType final : public Node {
+  const Node *Pointee;
+
+public:
+  PointerType(Node *Pointee_)
+      : Node(KPointerType, Pointee_->ParameterPackSize,
+             Pointee_->RHSComponentCache),
+        Pointee(Pointee_) {}
+
+  bool hasRHSComponentSlow(OutputStream &S) const override {
+    return Pointee->hasRHSComponent(S);
+  }
+
+  void printLeft(OutputStream &s) const override {
+    // We rewrite objc_object<SomeProtocol>* into id<SomeProtocol>.
+    if (Pointee->getKind() != KObjCProtoName ||
+        !static_cast<const ObjCProtoName *>(Pointee)->isObjCObject()) {
+      Pointee->printLeft(s);
+      if (Pointee->hasArray(s))
+        s += " ";
+      if (Pointee->hasArray(s) || Pointee->hasFunction(s))
+        s += "(";
+      s += "*";
+    } else {
+      const auto *objcProto = static_cast<const ObjCProtoName *>(Pointee);
+      s += "id<";
+      s += objcProto->Protocol;
+      s += ">";
     }
   }
-  return first;
-}
 
-// <source-name> ::= <positive length number> <identifier>
+  void printRight(OutputStream &s) const override {
+    if (Pointee->getKind() != KObjCProtoName ||
+        !static_cast<const ObjCProtoName *>(Pointee)->isObjCObject()) {
+      if (Pointee->hasArray(s) || Pointee->hasFunction(s))
+        s += ")";
+      Pointee->printRight(s);
+    }
+  }
+};
 
-template <class C>
-static const char *parse_source_name(const char *first, const char *last,
-                                     C &db) {
-  if (first != last) {
-    char c = *first;
-    if (isdigit(c) && first + 1 != last) {
-      const char *t = first + 1;
-      size_t n = static_cast<size_t>(c - '0');
-      for (c = *t; isdigit(c); c = *t) {
-        n = n * 10 + static_cast<size_t>(c - '0');
-        if (++t == last)
-          return first;
-      }
-      if (static_cast<size_t>(last - t) >= n) {
-        std::string r(t, n);
-        if (r.substr(0, 10) == "_GLOBAL__N")
-          db.names.push_back("(anonymous namespace)");
-        else
-          db.names.push_back(std::move(r));
-        first = t + n;
-      }
+class LValueReferenceType final : public Node {
+  const Node *Pointee;
+
+public:
+  LValueReferenceType(Node *Pointee_)
+      : Node(KLValueReferenceType, Pointee_->ParameterPackSize,
+             Pointee_->RHSComponentCache),
+        Pointee(Pointee_) {}
+
+  bool hasRHSComponentSlow(OutputStream &S) const override {
+    return Pointee->hasRHSComponent(S);
+  }
+
+  void printLeft(OutputStream &s) const override {
+    Pointee->printLeft(s);
+    if (Pointee->hasArray(s))
+      s += " ";
+    if (Pointee->hasArray(s) || Pointee->hasFunction(s))
+      s += "(&";
+    else
+      s += "&";
+  }
+  void printRight(OutputStream &s) const override {
+    if (Pointee->hasArray(s) || Pointee->hasFunction(s))
+      s += ")";
+    Pointee->printRight(s);
+  }
+};
+
+class RValueReferenceType final : public Node {
+  const Node *Pointee;
+
+public:
+  RValueReferenceType(Node *Pointee_)
+      : Node(KRValueReferenceType, Pointee_->ParameterPackSize,
+             Pointee_->RHSComponentCache),
+        Pointee(Pointee_) {}
+
+  bool hasRHSComponentSlow(OutputStream &S) const override {
+    return Pointee->hasRHSComponent(S);
+  }
+
+  void printLeft(OutputStream &s) const override {
+    Pointee->printLeft(s);
+    if (Pointee->hasArray(s))
+      s += " ";
+    if (Pointee->hasArray(s) || Pointee->hasFunction(s))
+      s += "(&&";
+    else
+      s += "&&";
+  }
+
+  void printRight(OutputStream &s) const override {
+    if (Pointee->hasArray(s) || Pointee->hasFunction(s))
+      s += ")";
+    Pointee->printRight(s);
+  }
+};
+
+class PointerToMemberType final : public Node {
+  const Node *ClassType;
+  const Node *MemberType;
+
+public:
+  PointerToMemberType(Node *ClassType_, Node *MemberType_)
+      : Node(KPointerToMemberType,
+             std::min(MemberType_->ParameterPackSize,
+                      ClassType_->ParameterPackSize),
+             MemberType_->RHSComponentCache),
+        ClassType(ClassType_), MemberType(MemberType_) {}
+
+  bool hasRHSComponentSlow(OutputStream &S) const override {
+    return MemberType->hasRHSComponent(S);
+  }
+
+  void printLeft(OutputStream &s) const override {
+    MemberType->printLeft(s);
+    if (MemberType->hasArray(s) || MemberType->hasFunction(s))
+      s += "(";
+    else
+      s += " ";
+    ClassType->print(s);
+    s += "::*";
+  }
+
+  void printRight(OutputStream &s) const override {
+    if (MemberType->hasArray(s) || MemberType->hasFunction(s))
+      s += ")";
+    MemberType->printRight(s);
+  }
+};
+
+class NodeOrString {
+  const void *First;
+  const void *Second;
+
+public:
+  /* implicit */ NodeOrString(StringView Str) {
+    const char *FirstChar = Str.begin();
+    const char *SecondChar = Str.end();
+    if (SecondChar == nullptr) {
+      assert(FirstChar == SecondChar);
+      ++FirstChar, ++SecondChar;
     }
+    First = static_cast<const void *>(FirstChar);
+    Second = static_cast<const void *>(SecondChar);
   }
-  return first;
-}
 
-// <substitution> ::= S <seq-id> _
-//                ::= S_
-// <substitution> ::= Sa # ::std::allocator
-// <substitution> ::= Sb # ::std::basic_string
-// <substitution> ::= Ss # ::std::basic_string < char,
-//                                               ::std::char_traits<char>,
-//                                               ::std::allocator<char> >
-// <substitution> ::= Si # ::std::basic_istream<char,  std::char_traits<char> >
-// <substitution> ::= So # ::std::basic_ostream<char,  std::char_traits<char> >
-// <substitution> ::= Sd # ::std::basic_iostream<char, std::char_traits<char> >
+  /* implicit */ NodeOrString(Node *N)
+      : First(static_cast<const void *>(N)), Second(nullptr) {}
+  NodeOrString() : First(nullptr), Second(nullptr) {}
 
-template <class C>
-static const char *parse_substitution(const char *first, const char *last,
-                                      C &db) {
-  if (last - first >= 2) {
-    if (*first == 'S') {
-      switch (first[1]) {
-      case 'a':
-        db.names.push_back("std::allocator");
-        first += 2;
-        break;
-      case 'b':
-        db.names.push_back("std::basic_string");
-        first += 2;
-        break;
-      case 's':
-        db.names.push_back("std::string");
-        first += 2;
-        break;
-      case 'i':
-        db.names.push_back("std::istream");
-        first += 2;
-        break;
-      case 'o':
-        db.names.push_back("std::ostream");
-        first += 2;
-        break;
-      case 'd':
-        db.names.push_back("std::iostream");
-        first += 2;
-        break;
-      case '_':
-        if (!db.subs.empty()) {
-          for (const auto &n : db.subs.front())
-            db.names.push_back(n);
-          first += 2;
-        }
-        break;
-      default:
-        if (std::isdigit(first[1]) || std::isupper(first[1])) {
-          size_t sub = 0;
-          const char *t = first + 1;
-          if (std::isdigit(*t))
-            sub = static_cast<size_t>(*t - '0');
-          else
-            sub = static_cast<size_t>(*t - 'A') + 10;
-          for (++t; t != last && (std::isdigit(*t) || std::isupper(*t)); ++t) {
-            sub *= 36;
-            if (std::isdigit(*t))
-              sub += static_cast<size_t>(*t - '0');
-            else
-              sub += static_cast<size_t>(*t - 'A') + 10;
-          }
-          if (t == last || *t != '_')
-            return first;
-          ++sub;
-          if (sub < db.subs.size()) {
-            for (const auto &n : db.subs[sub])
-              db.names.push_back(n);
-            first = t + 1;
-          }
-        }
-        break;
-      }
+  bool isString() const { return Second && First; }
+  bool isNode() const { return First && !Second; }
+  bool isEmpty() const { return !First && !Second; }
+
+  StringView asString() const {
+    assert(isString());
+    return StringView(static_cast<const char *>(First),
+                      static_cast<const char *>(Second));
+  }
+
+  const Node *asNode() const {
+    assert(isNode());
+    return static_cast<const Node *>(First);
+  }
+};
+
+class ArrayType final : public Node {
+  Node *Base;
+  NodeOrString Dimension;
+
+public:
+  ArrayType(Node *Base_, NodeOrString Dimension_)
+      : Node(KArrayType, Base_->ParameterPackSize,
+             /*RHSComponentCache=*/Cache::Yes,
+             /*ArrayCache=*/Cache::Yes),
+        Base(Base_), Dimension(Dimension_) {
+    if (Dimension.isNode())
+      ParameterPackSize =
+          std::min(ParameterPackSize, Dimension.asNode()->ParameterPackSize);
+  }
+
+  // Incomplete array type.
+  ArrayType(Node *Base_)
+      : Node(KArrayType, Base_->ParameterPackSize,
+             /*RHSComponentCache=*/Cache::Yes,
+             /*ArrayCache=*/Cache::Yes),
+        Base(Base_) {}
+
+  bool hasRHSComponentSlow(OutputStream &) const override { return true; }
+  bool hasArraySlow(OutputStream &) const override { return true; }
+
+  void printLeft(OutputStream &S) const override { Base->printLeft(S); }
+
+  void printRight(OutputStream &S) const override {
+    if (S.back() != ']')
+      S += " ";
+    S += "[";
+    if (Dimension.isString())
+      S += Dimension.asString();
+    else if (Dimension.isNode())
+      Dimension.asNode()->print(S);
+    S += "]";
+    Base->printRight(S);
+  }
+};
+
+class FunctionType final : public Node {
+  Node *Ret;
+  NodeArray Params;
+  Qualifiers CVQuals;
+  FunctionRefQual RefQual;
+  Node *ExceptionSpec;
+
+public:
+  FunctionType(Node *Ret_, NodeArray Params_, Qualifiers CVQuals_,
+               FunctionRefQual RefQual_, Node *ExceptionSpec_)
+      : Node(KFunctionType, Ret_->ParameterPackSize,
+             /*RHSComponentCache=*/Cache::Yes, /*ArrayCache=*/Cache::No,
+             /*FunctionCache=*/Cache::Yes),
+        Ret(Ret_), Params(Params_), CVQuals(CVQuals_), RefQual(RefQual_),
+        ExceptionSpec(ExceptionSpec_) {
+    for (Node *P : Params)
+      ParameterPackSize = std::min(ParameterPackSize, P->ParameterPackSize);
+    if (ExceptionSpec != nullptr)
+      ParameterPackSize =
+        std::min(ParameterPackSize, ExceptionSpec->ParameterPackSize);
+  }
+
+  bool hasRHSComponentSlow(OutputStream &) const override { return true; }
+  bool hasFunctionSlow(OutputStream &) const override { return true; }
+
+  // Handle C++'s ... quirky decl grammer by using the left & right
+  // distinction. Consider:
+  //   int (*f(float))(char) {}
+  // f is a function that takes a float and returns a pointer to a function
+  // that takes a char and returns an int. If we're trying to print f, start
+  // by printing out the return types's left, then print our parameters, then
+  // finally print right of the return type.
+  void printLeft(OutputStream &S) const override {
+    Ret->printLeft(S);
+    S += " ";
+  }
+
+  void printRight(OutputStream &S) const override {
+    S += "(";
+    Params.printWithComma(S);
+    S += ")";
+    Ret->printRight(S);
+
+    if (CVQuals & QualConst)
+      S += " const";
+    if (CVQuals & QualVolatile)
+      S += " volatile";
+    if (CVQuals & QualRestrict)
+      S += " restrict";
+
+    if (RefQual == FrefQualLValue)
+      S += " &";
+    else if (RefQual == FrefQualRValue)
+      S += " &&";
+
+    if (ExceptionSpec != nullptr) {
+      S += ' ';
+      ExceptionSpec->print(S);
+    }
+  }
+};
+
+class NoexceptSpec : public Node {
+  Node *E;
+public:
+  NoexceptSpec(Node *E_) : Node(KNoexceptSpec, E_->ParameterPackSize), E(E_) {}
+
+  void printLeft(OutputStream &S) const override {
+    S += "noexcept(";
+    E->print(S);
+    S += ")";
+  }
+};
+
+class DynamicExceptionSpec : public Node {
+  NodeArray Types;
+public:
+  DynamicExceptionSpec(NodeArray Types_)
+      : Node(KDynamicExceptionSpec), Types(Types_) {
+    for (Node *T : Types)
+      ParameterPackSize = std::min(ParameterPackSize, T->ParameterPackSize);
+  }
+
+  void printLeft(OutputStream &S) const override {
+    S += "throw(";
+    Types.printWithComma(S);
+    S += ')';
+  }
+};
+
+class FunctionEncoding final : public Node {
+  const Node *Ret;
+  const Node *Name;
+  NodeArray Params;
+  Qualifiers CVQuals;
+  FunctionRefQual RefQual;
+
+public:
+  FunctionEncoding(Node *Ret_, Node *Name_, NodeArray Params_,
+                   Qualifiers CVQuals_, FunctionRefQual RefQual_)
+      : Node(KFunctionEncoding, NoParameterPack,
+             /*RHSComponentCache=*/Cache::Yes, /*ArrayCache=*/Cache::No,
+             /*FunctionCache=*/Cache::Yes),
+        Ret(Ret_), Name(Name_), Params(Params_), CVQuals(CVQuals_),
+        RefQual(RefQual_) {
+    for (Node *P : Params)
+      ParameterPackSize = std::min(ParameterPackSize, P->ParameterPackSize);
+    if (Ret)
+      ParameterPackSize = std::min(ParameterPackSize, Ret->ParameterPackSize);
+  }
+
+  bool hasRHSComponentSlow(OutputStream &) const override { return true; }
+  bool hasFunctionSlow(OutputStream &) const override { return true; }
+
+  Node *getName() { return const_cast<Node *>(Name); }
+
+  void printLeft(OutputStream &S) const override {
+    if (Ret) {
+      Ret->printLeft(S);
+      if (!Ret->hasRHSComponent(S))
+        S += " ";
+    }
+    Name->print(S);
+  }
+
+  void printRight(OutputStream &S) const override {
+    S += "(";
+    Params.printWithComma(S);
+    S += ")";
+    if (Ret)
+      Ret->printRight(S);
+
+    if (CVQuals & QualConst)
+      S += " const";
+    if (CVQuals & QualVolatile)
+      S += " volatile";
+    if (CVQuals & QualRestrict)
+      S += " restrict";
+
+    if (RefQual == FrefQualLValue)
+      S += " &";
+    else if (RefQual == FrefQualRValue)
+      S += " &&";
+  }
+};
+
+class LiteralOperator : public Node {
+  const Node *OpName;
+
+public:
+  LiteralOperator(Node *OpName_)
+      : Node(KLiteralOperator, OpName_->ParameterPackSize), OpName(OpName_) {}
+
+  void printLeft(OutputStream &S) const override {
+    S += "operator\"\" ";
+    OpName->print(S);
+  }
+};
+
+class SpecialName final : public Node {
+  const StringView Special;
+  const Node *Child;
+
+public:
+  SpecialName(StringView Special_, Node* Child_)
+      : Node(KSpecialName, Child_->ParameterPackSize), Special(Special_),
+        Child(Child_) {}
+
+  void printLeft(OutputStream &S) const override {
+    S += Special;
+    Child->print(S);
+  }
+};
+
+class CtorVtableSpecialName final : public Node {
+  const Node *FirstType;
+  const Node *SecondType;
+
+public:
+  CtorVtableSpecialName(Node *FirstType_, Node *SecondType_)
+      : Node(KCtorVtableSpecialName, std::min(FirstType_->ParameterPackSize,
+                                              SecondType_->ParameterPackSize)),
+        FirstType(FirstType_), SecondType(SecondType_) {}
+
+  void printLeft(OutputStream &S) const override {
+    S += "construction vtable for ";
+    FirstType->print(S);
+    S += "-in-";
+    SecondType->print(S);
+  }
+};
+
+class QualifiedName final : public Node {
+  // qualifier::name
+  const Node *Qualifier;
+  const Node *Name;
+
+public:
+  QualifiedName(Node* Qualifier_, Node* Name_)
+      : Node(KQualifiedName,
+             std::min(Qualifier_->ParameterPackSize, Name_->ParameterPackSize)),
+        Qualifier(Qualifier_), Name(Name_) {}
+
+  StringView getBaseName() const override { return Name->getBaseName(); }
+
+  void printLeft(OutputStream &S) const override {
+    Qualifier->print(S);
+    S += "::";
+    Name->print(S);
+  }
+};
+
+class EmptyName : public Node {
+public:
+  EmptyName() : Node(KEmptyName) {}
+  void printLeft(OutputStream &) const override {}
+};
+
+class VectorType final : public Node {
+  const Node *BaseType;
+  const NodeOrString Dimension;
+  const bool IsPixel;
+
+public:
+  VectorType(NodeOrString Dimension_)
+      : Node(KVectorType), BaseType(nullptr), Dimension(Dimension_),
+        IsPixel(true) {
+    if (Dimension.isNode())
+      ParameterPackSize = Dimension.asNode()->ParameterPackSize;
+  }
+  VectorType(Node *BaseType_, NodeOrString Dimension_)
+      : Node(KVectorType, BaseType_->ParameterPackSize), BaseType(BaseType_),
+        Dimension(Dimension_), IsPixel(false) {
+    if (Dimension.isNode())
+      ParameterPackSize =
+          std::min(ParameterPackSize, Dimension.asNode()->ParameterPackSize);
+  }
+
+  void printLeft(OutputStream &S) const override {
+    if (IsPixel) {
+      S += "pixel vector[";
+      S += Dimension.asString();
+      S += "]";
+    } else {
+      BaseType->print(S);
+      S += " vector[";
+      if (Dimension.isNode())
+        Dimension.asNode()->print(S);
+      else if (Dimension.isString())
+        S += Dimension.asString();
+      S += "]";
+    }
+  }
+};
+
+/// An unexpanded parameter pack (either in the expression or type context). If
+/// this AST is correct, this node will have a ParameterPackExpansion node above
+/// it.
+///
+/// This node is created when some <template-args> are found that apply to an
+/// <encoding>, and is stored in the TemplateParams table. In order for this to
+/// appear in the final AST, it has to referenced via a <template-param> (ie,
+/// T_).
+class ParameterPack final : public Node {
+  NodeArray Data;
+public:
+  ParameterPack(NodeArray Data_)
+      : Node(KParameterPack, static_cast<unsigned>(Data_.size())), Data(Data_) {
+    ArrayCache = FunctionCache = RHSComponentCache = Cache::Unknown;
+    if (std::all_of(Data.begin(), Data.end(), [](Node* P) {
+          return P->ArrayCache == Cache::No;
+        }))
+      ArrayCache = Cache::No;
+    if (std::all_of(Data.begin(), Data.end(), [](Node* P) {
+          return P->FunctionCache == Cache::No;
+        }))
+      FunctionCache = Cache::No;
+    if (std::all_of(Data.begin(), Data.end(), [](Node* P) {
+          return P->RHSComponentCache == Cache::No;
+        }))
+      RHSComponentCache = Cache::No;
+  }
+
+  bool hasRHSComponentSlow(OutputStream &S) const override {
+    size_t Idx = S.CurrentPackIndex;
+    return Idx < Data.size() && Data[Idx]->hasRHSComponent(S);
+  }
+  bool hasArraySlow(OutputStream &S) const override {
+    size_t Idx = S.CurrentPackIndex;
+    return Idx < Data.size() && Data[Idx]->hasArray(S);
+  }
+  bool hasFunctionSlow(OutputStream &S) const override {
+    size_t Idx = S.CurrentPackIndex;
+    return Idx < Data.size() && Data[Idx]->hasFunction(S);
+  }
+
+  void printLeft(OutputStream &S) const override {
+    size_t Idx = S.CurrentPackIndex;
+    if (Idx < Data.size())
+      Data[Idx]->printLeft(S);
+  }
+  void printRight(OutputStream &S) const override {
+    size_t Idx = S.CurrentPackIndex;
+    if (Idx < Data.size())
+      Data[Idx]->printRight(S);
+  }
+};
+
+/// A variadic template argument. This node represents an occurance of
+/// J<something>E in some <template-args>. It isn't itself unexpanded, unless
+/// one of it's Elements is. The parser inserts a ParameterPack into the
+/// TemplateParams table if the <template-args> this pack belongs to apply to an
+/// <encoding>.
+class TemplateArgumentPack final : public Node {
+  NodeArray Elements;
+public:
+  TemplateArgumentPack(NodeArray Elements_)
+      : Node(KTemplateArgumentPack), Elements(Elements_) {
+    for (Node *E : Elements)
+      ParameterPackSize = std::min(E->ParameterPackSize, ParameterPackSize);
+  }
+
+  NodeArray getElements() const { return Elements; }
+
+  void printLeft(OutputStream &S) const override {
+    Elements.printWithComma(S);
+  }
+};
+
+/// A pack expansion. Below this node, there are some unexpanded ParameterPacks
+/// which each have Child->ParameterPackSize elements.
+class ParameterPackExpansion final : public Node {
+  const Node *Child;
+
+public:
+  ParameterPackExpansion(Node* Child_)
+      : Node(KParameterPackExpansion), Child(Child_) {}
+
+  const Node *getChild() const { return Child; }
+
+  void printLeft(OutputStream &S) const override {
+    unsigned PackSize = Child->ParameterPackSize;
+    if (PackSize == NoParameterPack) {
+      Child->print(S);
+      S += "...";
+      return;
+    }
+
+    SwapAndRestore<unsigned> SavePackIndex(S.CurrentPackIndex, 0);
+    for (unsigned I = 0; I != PackSize; ++I) {
+      if (I != 0)
+        S += ", ";
+      S.CurrentPackIndex = I;
+      Child->print(S);
     }
   }
-  return first;
+};
+
+inline bool Node::isEmptyPackExpansion() const {
+  if (getKind() == KParameterPackExpansion) {
+    auto *AsPack = static_cast<const ParameterPackExpansion *>(this);
+    return AsPack->getChild()->isEmptyPackExpansion();
+  }
+  if (getKind() == KTemplateArgumentPack) {
+    auto *AsTemplateArg = static_cast<const TemplateArgumentPack *>(this);
+    for (Node *E : AsTemplateArg->getElements())
+      if (!E->isEmptyPackExpansion())
+        return false;
+    return true;
+  }
+  return ParameterPackSize == 0;
 }
 
-// <builtin-type> ::= v    # void
-//                ::= w    # wchar_t
-//                ::= b    # bool
-//                ::= c    # char
-//                ::= a    # signed char
-//                ::= h    # unsigned char
-//                ::= s    # short
-//                ::= t    # unsigned short
-//                ::= i    # int
-//                ::= j    # unsigned int
-//                ::= l    # long
-//                ::= m    # unsigned long
-//                ::= x    # long long, __int64
-//                ::= y    # unsigned long long, __int64
-//                ::= n    # __int128
-//                ::= o    # unsigned __int128
-//                ::= f    # float
-//                ::= d    # double
-//                ::= e    # long double, __float80
-//                ::= g    # __float128
-//                ::= z    # ellipsis
-//                ::= Dd   # IEEE 754r decimal floating point (64 bits)
-//                ::= De   # IEEE 754r decimal floating point (128 bits)
-//                ::= Df   # IEEE 754r decimal floating point (32 bits)
-//                ::= Dh   # IEEE 754r half-precision floating point (16 bits)
-//                ::= Di   # char32_t
-//                ::= Ds   # char16_t
-//                ::= Da   # auto (in dependent new-expressions)
-//                ::= Dc   # decltype(auto)
-//                ::= Dn   # std::nullptr_t (i.e., decltype(nullptr))
-//                ::= u <source-name>    # vendor extended type
-
-template <class C>
-static const char *parse_builtin_type(const char *first, const char *last,
-                                      C &db) {
-  if (first != last) {
-    switch (*first) {
-    case 'v':
-      db.names.push_back("void");
-      ++first;
-      break;
-    case 'w':
-      db.names.push_back("wchar_t");
-      ++first;
-      break;
-    case 'b':
-      db.names.push_back("bool");
-      ++first;
-      break;
-    case 'c':
-      db.names.push_back("char");
-      ++first;
-      break;
-    case 'a':
-      db.names.push_back("signed char");
-      ++first;
-      break;
-    case 'h':
-      db.names.push_back("unsigned char");
-      ++first;
-      break;
-    case 's':
-      db.names.push_back("short");
-      ++first;
-      break;
-    case 't':
-      db.names.push_back("unsigned short");
-      ++first;
-      break;
-    case 'i':
-      db.names.push_back("int");
-      ++first;
-      break;
-    case 'j':
-      db.names.push_back("unsigned int");
-      ++first;
-      break;
-    case 'l':
-      db.names.push_back("long");
-      ++first;
-      break;
-    case 'm':
-      db.names.push_back("unsigned long");
-      ++first;
+class TemplateArgs final : public Node {
+  NodeArray Params;
+
+public:
+  TemplateArgs(NodeArray Params_) : Node(KTemplateArgs), Params(Params_) {
+    for (Node *P : Params)
+      ParameterPackSize = std::min(ParameterPackSize, P->ParameterPackSize);
+  }
+
+  NodeArray getParams() { return Params; }
+
+  void printLeft(OutputStream &S) const override {
+    S += "<";
+    bool FirstElement = true;
+    for (size_t Idx = 0, E = Params.size(); Idx != E; ++Idx) {
+      if (Params[Idx]->isEmptyPackExpansion())
+        continue;
+      if (!FirstElement)
+        S += ", ";
+      FirstElement = false;
+      Params[Idx]->print(S);
+    }
+    if (S.back() == '>')
+      S += " ";
+    S += ">";
+  }
+};
+
+class NameWithTemplateArgs final : public Node {
+  // name<template_args>
+  Node *Name;
+  Node *TemplateArgs;
+
+public:
+  NameWithTemplateArgs(Node *Name_, Node *TemplateArgs_)
+      : Node(KNameWithTemplateArgs, std::min(Name_->ParameterPackSize,
+                                             TemplateArgs_->ParameterPackSize)),
+        Name(Name_), TemplateArgs(TemplateArgs_) {}
+
+  StringView getBaseName() const override { return Name->getBaseName(); }
+
+  void printLeft(OutputStream &S) const override {
+    Name->print(S);
+    TemplateArgs->print(S);
+  }
+};
+
+class GlobalQualifiedName final : public Node {
+  Node *Child;
+
+public:
+  GlobalQualifiedName(Node* Child_)
+      : Node(KGlobalQualifiedName, Child_->ParameterPackSize), Child(Child_) {}
+
+  StringView getBaseName() const override { return Child->getBaseName(); }
+
+  void printLeft(OutputStream &S) const override {
+    S += "::";
+    Child->print(S);
+  }
+};
+
+class StdQualifiedName final : public Node {
+  Node *Child;
+
+public:
+  StdQualifiedName(Node *Child_)
+      : Node(KStdQualifiedName, Child_->ParameterPackSize), Child(Child_) {}
+
+  StringView getBaseName() const override { return Child->getBaseName(); }
+
+  void printLeft(OutputStream &S) const override {
+    S += "std::";
+    Child->print(S);
+  }
+};
+
+enum class SpecialSubKind {
+  allocator,
+  basic_string,
+  string,
+  istream,
+  ostream,
+  iostream,
+};
+
+class ExpandedSpecialSubstitution final : public Node {
+  SpecialSubKind SSK;
+
+public:
+  ExpandedSpecialSubstitution(SpecialSubKind SSK_)
+      : Node(KExpandedSpecialSubstitution), SSK(SSK_) {}
+
+  StringView getBaseName() const override {
+    switch (SSK) {
+    case SpecialSubKind::allocator:
+      return StringView("allocator");
+    case SpecialSubKind::basic_string:
+      return StringView("basic_string");
+    case SpecialSubKind::string:
+      return StringView("basic_string");
+    case SpecialSubKind::istream:
+      return StringView("basic_istream");
+    case SpecialSubKind::ostream:
+      return StringView("basic_ostream");
+    case SpecialSubKind::iostream:
+      return StringView("basic_iostream");
+    }
+    LLVM_BUILTIN_UNREACHABLE;
+  }
+
+  void printLeft(OutputStream &S) const override {
+    switch (SSK) {
+    case SpecialSubKind::allocator:
+      S += "std::basic_string<char, std::char_traits<char>, "
+           "std::allocator<char> >";
       break;
-    case 'x':
-      db.names.push_back("long long");
-      ++first;
+    case SpecialSubKind::basic_string:
+    case SpecialSubKind::string:
+      S += "std::basic_string<char, std::char_traits<char>, "
+           "std::allocator<char> >";
       break;
-    case 'y':
-      db.names.push_back("unsigned long long");
-      ++first;
+    case SpecialSubKind::istream:
+      S += "std::basic_istream<char, std::char_traits<char> >";
       break;
-    case 'n':
-      db.names.push_back("__int128");
-      ++first;
+    case SpecialSubKind::ostream:
+      S += "std::basic_ostream<char, std::char_traits<char> >";
       break;
-    case 'o':
-      db.names.push_back("unsigned __int128");
-      ++first;
+    case SpecialSubKind::iostream:
+      S += "std::basic_iostream<char, std::char_traits<char> >";
       break;
-    case 'f':
-      db.names.push_back("float");
-      ++first;
+    }
+  }
+};
+
+class SpecialSubstitution final : public Node {
+public:
+  SpecialSubKind SSK;
+
+  SpecialSubstitution(SpecialSubKind SSK_)
+      : Node(KSpecialSubstitution), SSK(SSK_) {}
+
+  StringView getBaseName() const override {
+    switch (SSK) {
+    case SpecialSubKind::allocator:
+      return StringView("allocator");
+    case SpecialSubKind::basic_string:
+      return StringView("basic_string");
+    case SpecialSubKind::string:
+      return StringView("string");
+    case SpecialSubKind::istream:
+      return StringView("istream");
+    case SpecialSubKind::ostream:
+      return StringView("ostream");
+    case SpecialSubKind::iostream:
+      return StringView("iostream");
+    }
+    LLVM_BUILTIN_UNREACHABLE;
+  }
+
+  void printLeft(OutputStream &S) const override {
+    switch (SSK) {
+    case SpecialSubKind::allocator:
+      S += "std::allocator";
       break;
-    case 'd':
-      db.names.push_back("double");
-      ++first;
+    case SpecialSubKind::basic_string:
+      S += "std::basic_string";
       break;
-    case 'e':
-      db.names.push_back("long double");
-      ++first;
+    case SpecialSubKind::string:
+      S += "std::string";
       break;
-    case 'g':
-      db.names.push_back("__float128");
-      ++first;
+    case SpecialSubKind::istream:
+      S += "std::istream";
       break;
-    case 'z':
-      db.names.push_back("...");
-      ++first;
+    case SpecialSubKind::ostream:
+      S += "std::ostream";
       break;
-    case 'u': {
-      const char *t = parse_source_name(first + 1, last, db);
-      if (t != first + 1)
-        first = t;
-    } break;
-    case 'D':
-      if (first + 1 != last) {
-        switch (first[1]) {
-        case 'd':
-          db.names.push_back("decimal64");
-          first += 2;
-          break;
-        case 'e':
-          db.names.push_back("decimal128");
-          first += 2;
-          break;
-        case 'f':
-          db.names.push_back("decimal32");
-          first += 2;
-          break;
-        case 'h':
-          db.names.push_back("decimal16");
-          first += 2;
-          break;
-        case 'i':
-          db.names.push_back("char32_t");
-          first += 2;
-          break;
-        case 's':
-          db.names.push_back("char16_t");
-          first += 2;
-          break;
-        case 'a':
-          db.names.push_back("auto");
-          first += 2;
-          break;
-        case 'c':
-          db.names.push_back("decltype(auto)");
-          first += 2;
-          break;
-        case 'n':
-          db.names.push_back("std::nullptr_t");
-          first += 2;
-          break;
-        }
-      }
+    case SpecialSubKind::iostream:
+      S += "std::iostream";
       break;
     }
   }
-  return first;
-}
+};
 
-// <CV-qualifiers> ::= [r] [V] [K]
+class CtorDtorName final : public Node {
+  const Node *Basename;
+  const bool IsDtor;
 
-static const char *parse_cv_qualifiers(const char *first, const char *last,
-                                       unsigned &cv) {
-  cv = 0;
-  if (first != last) {
-    if (*first == 'r') {
-      cv |= CV_restrict;
-      ++first;
-    }
-    if (*first == 'V') {
-      cv |= CV_volatile;
-      ++first;
-    }
-    if (*first == 'K') {
-      cv |= CV_const;
-      ++first;
-    }
+public:
+  CtorDtorName(Node *Basename_, bool IsDtor_)
+      : Node(KCtorDtorName, Basename_->ParameterPackSize),
+        Basename(Basename_), IsDtor(IsDtor_) {}
+
+  void printLeft(OutputStream &S) const override {
+    if (IsDtor)
+      S += "~";
+    S += Basename->getBaseName();
   }
-  return first;
-}
+};
 
-// <template-param> ::= T_    # first template parameter
-//                  ::= T <parameter-2 non-negative number> _
+class DtorName : public Node {
+  const Node *Base;
 
-template <class C>
-static const char *parse_template_param(const char *first, const char *last,
-                                        C &db) {
-  if (last - first >= 2) {
-    if (*first == 'T') {
-      if (first[1] == '_') {
-        if (db.template_param.empty())
-          return first;
-        if (!db.template_param.back().empty()) {
-          for (auto &t : db.template_param.back().front())
-            db.names.push_back(t);
-          first += 2;
-        } else {
-          db.names.push_back("T_");
-          first += 2;
-          db.fix_forward_references = true;
-        }
-      } else if (isdigit(first[1])) {
-        const char *t = first + 1;
-        size_t sub = static_cast<size_t>(*t - '0');
-        for (++t; t != last && isdigit(*t); ++t) {
-          sub *= 10;
-          sub += static_cast<size_t>(*t - '0');
-        }
-        if (t == last || *t != '_' || db.template_param.empty())
-          return first;
-        ++sub;
-        if (sub < db.template_param.back().size()) {
-          for (auto &temp : db.template_param.back()[sub])
-            db.names.push_back(temp);
-          first = t + 1;
-        } else {
-          db.names.push_back(std::string(first, t + 1));
-          first = t + 1;
-          db.fix_forward_references = true;
-        }
-      }
-    }
+public:
+  DtorName(Node *Base_) : Node(KDtorName), Base(Base_) {
+    ParameterPackSize = Base->ParameterPackSize;
   }
-  return first;
-}
 
-// cc <type> <expression>                               # const_cast<type>
-// (expression)
-
-template <class C>
-static const char *parse_const_cast_expr(const char *first, const char *last,
-                                         C &db) {
-  if (last - first >= 3 && first[0] == 'c' && first[1] == 'c') {
-    const char *t = parse_type(first + 2, last, db);
-    if (t != first + 2) {
-      const char *t1 = parse_expression(t, last, db);
-      if (t1 != t) {
-        if (db.names.size() < 2)
-          return first;
-        auto expr = db.names.back().move_full();
-        db.names.pop_back();
-        if (db.names.empty())
-          return first;
-        db.names.back() =
-            "const_cast<" + db.names.back().move_full() + ">(" + expr + ")";
-        first = t1;
-      }
-    }
+  void printLeft(OutputStream &S) const override {
+    S += "~";
+    Base->printLeft(S);
   }
-  return first;
-}
+};
 
-// dc <type> <expression>                               # dynamic_cast<type>
-// (expression)
-
-template <class C>
-static const char *parse_dynamic_cast_expr(const char *first, const char *last,
-                                           C &db) {
-  if (last - first >= 3 && first[0] == 'd' && first[1] == 'c') {
-    const char *t = parse_type(first + 2, last, db);
-    if (t != first + 2) {
-      const char *t1 = parse_expression(t, last, db);
-      if (t1 != t) {
-        if (db.names.size() < 2)
-          return first;
-        auto expr = db.names.back().move_full();
-        db.names.pop_back();
-        if (db.names.empty())
-          return first;
-        db.names.back() =
-            "dynamic_cast<" + db.names.back().move_full() + ">(" + expr + ")";
-        first = t1;
-      }
-    }
+class UnnamedTypeName : public Node {
+  const StringView Count;
+
+public:
+  UnnamedTypeName(StringView Count_) : Node(KUnnamedTypeName), Count(Count_) {}
+
+  void printLeft(OutputStream &S) const override {
+    S += "'unnamed";
+    S += Count;
+    S += "\'";
   }
-  return first;
-}
+};
 
-// rc <type> <expression>                               # reinterpret_cast<type>
-// (expression)
-
-template <class C>
-static const char *parse_reinterpret_cast_expr(const char *first,
-                                               const char *last, C &db) {
-  if (last - first >= 3 && first[0] == 'r' && first[1] == 'c') {
-    const char *t = parse_type(first + 2, last, db);
-    if (t != first + 2) {
-      const char *t1 = parse_expression(t, last, db);
-      if (t1 != t) {
-        if (db.names.size() < 2)
-          return first;
-        auto expr = db.names.back().move_full();
-        db.names.pop_back();
-        if (db.names.empty())
-          return first;
-        db.names.back() = "reinterpret_cast<" + db.names.back().move_full() +
-                          ">(" + expr + ")";
-        first = t1;
-      }
-    }
+class ClosureTypeName : public Node {
+  NodeArray Params;
+  StringView Count;
+
+public:
+  ClosureTypeName(NodeArray Params_, StringView Count_)
+      : Node(KClosureTypeName), Params(Params_), Count(Count_) {
+    for (Node *P : Params)
+      ParameterPackSize = std::min(ParameterPackSize, P->ParameterPackSize);
   }
-  return first;
-}
 
-// sc <type> <expression>                               # static_cast<type>
-// (expression)
-
-template <class C>
-static const char *parse_static_cast_expr(const char *first, const char *last,
-                                          C &db) {
-  if (last - first >= 3 && first[0] == 's' && first[1] == 'c') {
-    const char *t = parse_type(first + 2, last, db);
-    if (t != first + 2) {
-      const char *t1 = parse_expression(t, last, db);
-      if (t1 != t) {
-        if (db.names.size() < 2)
-          return first;
-        auto expr = db.names.back().move_full();
-        db.names.pop_back();
-        db.names.back() =
-            "static_cast<" + db.names.back().move_full() + ">(" + expr + ")";
-        first = t1;
-      }
-    }
+  void printLeft(OutputStream &S) const override {
+    S += "\'lambda";
+    S += Count;
+    S += "\'(";
+    Params.printWithComma(S);
+    S += ")";
   }
-  return first;
-}
+};
 
-// sp <expression>                                  # pack expansion
+class StructuredBindingName : public Node {
+  NodeArray Bindings;
+public:
+  StructuredBindingName(NodeArray Bindings_)
+      : Node(KStructuredBindingName), Bindings(Bindings_) {}
 
-template <class C>
-static const char *parse_pack_expansion(const char *first, const char *last,
-                                        C &db) {
-  if (last - first >= 3 && first[0] == 's' && first[1] == 'p') {
-    const char *t = parse_expression(first + 2, last, db);
-    if (t != first + 2)
-      first = t;
+  void printLeft(OutputStream &S) const override {
+    S += '[';
+    Bindings.printWithComma(S);
+    S += ']';
   }
-  return first;
-}
+};
 
-// st <type>                                            # sizeof (a type)
+// -- Expression Nodes --
 
-template <class C>
-static const char *parse_sizeof_type_expr(const char *first, const char *last,
-                                          C &db) {
-  if (last - first >= 3 && first[0] == 's' && first[1] == 't') {
-    const char *t = parse_type(first + 2, last, db);
-    if (t != first + 2) {
-      if (db.names.empty())
-        return first;
-      db.names.back() = "sizeof (" + db.names.back().move_full() + ")";
-      first = t;
-    }
+struct Expr : public Node {
+  Expr(Kind K = KExpr) : Node(K) {}
+};
+
+class BinaryExpr : public Expr {
+  const Node *LHS;
+  const StringView InfixOperator;
+  const Node *RHS;
+
+public:
+  BinaryExpr(Node *LHS_, StringView InfixOperator_, Node *RHS_)
+      : LHS(LHS_), InfixOperator(InfixOperator_), RHS(RHS_) {
+    ParameterPackSize =
+      std::min(LHS->ParameterPackSize, RHS->ParameterPackSize);
   }
-  return first;
-}
 
-// sz <expr>                                            # sizeof (a expression)
+  void printLeft(OutputStream &S) const override {
+    // might be a template argument expression, then we need to disambiguate
+    // with parens.
+    if (InfixOperator == ">")
+      S += "(";
+
+    S += "(";
+    LHS->print(S);
+    S += ") ";
+    S += InfixOperator;
+    S += " (";
+    RHS->print(S);
+    S += ")";
+
+    if (InfixOperator == ">")
+      S += ")";
+  }
+};
 
-template <class C>
-static const char *parse_sizeof_expr_expr(const char *first, const char *last,
-                                          C &db) {
-  if (last - first >= 3 && first[0] == 's' && first[1] == 'z') {
-    const char *t = parse_expression(first + 2, last, db);
-    if (t != first + 2) {
-      if (db.names.empty())
-        return first;
-      db.names.back() = "sizeof (" + db.names.back().move_full() + ")";
-      first = t;
-    }
+class ArraySubscriptExpr : public Expr {
+  const Node *Op1;
+  const Node *Op2;
+
+public:
+  ArraySubscriptExpr(Node *Op1_, Node *Op2_) : Op1(Op1_), Op2(Op2_) {
+    ParameterPackSize =
+      std::min(Op1->ParameterPackSize, Op2->ParameterPackSize);
   }
-  return first;
-}
 
-// sZ <template-param>                                  # size of a parameter
-// pack
-
-template <class C>
-static const char *parse_sizeof_param_pack_expr(const char *first,
-                                                const char *last, C &db) {
-  if (last - first >= 3 && first[0] == 's' && first[1] == 'Z' &&
-      first[2] == 'T') {
-    size_t k0 = db.names.size();
-    const char *t = parse_template_param(first + 2, last, db);
-    size_t k1 = db.names.size();
-    if (t != first + 2) {
-      std::string tmp("sizeof...(");
-      size_t k = k0;
-      if (k != k1) {
-        tmp += db.names[k].move_full();
-        for (++k; k != k1; ++k)
-          tmp += ", " + db.names[k].move_full();
-      }
-      tmp += ")";
-      for (; k1 != k0; --k1)
-        db.names.pop_back();
-      db.names.push_back(std::move(tmp));
-      first = t;
-    }
+  void printLeft(OutputStream &S) const override {
+    S += "(";
+    Op1->print(S);
+    S += ")[";
+    Op2->print(S);
+    S += "]";
   }
-  return first;
-}
+};
 
-// <function-param> ::= fp <top-level CV-qualifiers> _ # L == 0, first parameter
-//                  ::= fp <top-level CV-qualifiers> <parameter-2 non-negative
-//                  number> _   # L == 0, second and later parameters
-//                  ::= fL <L-1 non-negative number> p <top-level CV-qualifiers>
-//                  _         # L > 0, first parameter
-//                  ::= fL <L-1 non-negative number> p <top-level CV-qualifiers>
-//                  <parameter-2 non-negative number> _   # L > 0, second and
-//                  later parameters
-
-template <class C>
-static const char *parse_function_param(const char *first, const char *last,
-                                        C &db) {
-  if (last - first >= 3 && *first == 'f') {
-    if (first[1] == 'p') {
-      unsigned cv;
-      const char *t = parse_cv_qualifiers(first + 2, last, cv);
-      const char *t1 = parse_number(t, last);
-      if (t1 != last && *t1 == '_') {
-        db.names.push_back("fp" + std::string(t, t1));
-        first = t1 + 1;
-      }
-    } else if (first[1] == 'L') {
-      unsigned cv;
-      const char *t0 = parse_number(first + 2, last);
-      if (t0 != last && *t0 == 'p') {
-        ++t0;
-        const char *t = parse_cv_qualifiers(t0, last, cv);
-        const char *t1 = parse_number(t, last);
-        if (t1 != last && *t1 == '_') {
-          db.names.push_back("fp" + std::string(t, t1));
-          first = t1 + 1;
-        }
-      }
-    }
+class PostfixExpr : public Expr {
+  const Node *Child;
+  const StringView Operand;
+
+public:
+  PostfixExpr(Node *Child_, StringView Operand_)
+      : Child(Child_), Operand(Operand_) {
+    ParameterPackSize = Child->ParameterPackSize;
   }
-  return first;
-}
 
-// sZ <function-param>                                  # size of a function
-// parameter pack
+  void printLeft(OutputStream &S) const override {
+    S += "(";
+    Child->print(S);
+    S += ")";
+    S += Operand;
+  }
+};
+
+class ConditionalExpr : public Expr {
+  const Node *Cond;
+  const Node *Then;
+  const Node *Else;
 
-template <class C>
-static const char *parse_sizeof_function_param_pack_expr(const char *first,
-                                                         const char *last,
-                                                         C &db) {
-  if (last - first >= 3 && first[0] == 's' && first[1] == 'Z' &&
-      first[2] == 'f') {
-    const char *t = parse_function_param(first + 2, last, db);
-    if (t != first + 2) {
-      if (db.names.empty())
-        return first;
-      db.names.back() = "sizeof...(" + db.names.back().move_full() + ")";
-      first = t;
-    }
+public:
+  ConditionalExpr(Node *Cond_, Node *Then_, Node *Else_)
+      : Cond(Cond_), Then(Then_), Else(Else_) {
+    ParameterPackSize =
+        std::min(Cond->ParameterPackSize,
+                 std::min(Then->ParameterPackSize, Else->ParameterPackSize));
   }
-  return first;
-}
 
-// te <expression>                                      # typeid (expression)
-// ti <type>                                            # typeid (type)
-
-template <class C>
-static const char *parse_typeid_expr(const char *first, const char *last,
-                                     C &db) {
-  if (last - first >= 3 && first[0] == 't' &&
-      (first[1] == 'e' || first[1] == 'i')) {
-    const char *t;
-    if (first[1] == 'e')
-      t = parse_expression(first + 2, last, db);
-    else
-      t = parse_type(first + 2, last, db);
-    if (t != first + 2) {
-      if (db.names.empty())
-        return first;
-      db.names.back() = "typeid(" + db.names.back().move_full() + ")";
-      first = t;
-    }
+  void printLeft(OutputStream &S) const override {
+    S += "(";
+    Cond->print(S);
+    S += ") ? (";
+    Then->print(S);
+    S += ") : (";
+    Else->print(S);
+    S += ")";
   }
-  return first;
-}
+};
 
-// tw <expression>                                      # throw expression
+class MemberExpr : public Expr {
+  const Node *LHS;
+  const StringView Kind;
+  const Node *RHS;
 
-template <class C>
-static const char *parse_throw_expr(const char *first, const char *last,
-                                    C &db) {
-  if (last - first >= 3 && first[0] == 't' && first[1] == 'w') {
-    const char *t = parse_expression(first + 2, last, db);
-    if (t != first + 2) {
-      if (db.names.empty())
-        return first;
-      db.names.back() = "throw " + db.names.back().move_full();
-      first = t;
-    }
+public:
+  MemberExpr(Node *LHS_, StringView Kind_, Node *RHS_)
+      : LHS(LHS_), Kind(Kind_), RHS(RHS_) {
+    ParameterPackSize =
+      std::min(LHS->ParameterPackSize, RHS->ParameterPackSize);
   }
-  return first;
-}
 
-// ds <expression> <expression>                         # expr.*expr
-
-template <class C>
-static const char *parse_dot_star_expr(const char *first, const char *last,
-                                       C &db) {
-  if (last - first >= 3 && first[0] == 'd' && first[1] == 's') {
-    const char *t = parse_expression(first + 2, last, db);
-    if (t != first + 2) {
-      const char *t1 = parse_expression(t, last, db);
-      if (t1 != t) {
-        if (db.names.size() < 2)
-          return first;
-        auto expr = db.names.back().move_full();
-        db.names.pop_back();
-        db.names.back().first += ".*" + expr;
-        first = t1;
-      }
-    }
+  void printLeft(OutputStream &S) const override {
+    LHS->print(S);
+    S += Kind;
+    RHS->print(S);
   }
-  return first;
-}
+};
 
-// <simple-id> ::= <source-name> [ <template-args> ]
+class EnclosingExpr : public Expr {
+  const StringView Prefix;
+  const Node *Infix;
+  const StringView Postfix;
 
-template <class C>
-static const char *parse_simple_id(const char *first, const char *last, C &db) {
-  if (first != last) {
-    const char *t = parse_source_name(first, last, db);
-    if (t != first) {
-      const char *t1 = parse_template_args(t, last, db);
-      if (t1 != t) {
-        if (db.names.size() < 2)
-          return first;
-        auto args = db.names.back().move_full();
-        db.names.pop_back();
-        db.names.back().first += std::move(args);
-      }
-      first = t1;
-    } else
-      first = t;
+public:
+  EnclosingExpr(StringView Prefix_, Node *Infix_, StringView Postfix_)
+      : Prefix(Prefix_), Infix(Infix_), Postfix(Postfix_) {
+    ParameterPackSize = Infix->ParameterPackSize;
   }
-  return first;
-}
 
-// <unresolved-type> ::= <template-param>
-//                   ::= <decltype>
-//                   ::= <substitution>
+  void printLeft(OutputStream &S) const override {
+    S += Prefix;
+    Infix->print(S);
+    S += Postfix;
+  }
+};
 
-template <class C>
-static const char *parse_unresolved_type(const char *first, const char *last,
-                                         C &db) {
-  if (first != last) {
-    const char *t = first;
-    switch (*first) {
-    case 'T': {
-      size_t k0 = db.names.size();
-      t = parse_template_param(first, last, db);
-      size_t k1 = db.names.size();
-      if (t != first && k1 == k0 + 1) {
-        db.subs.push_back(typename C::sub_type(1, db.names.back()));
-        first = t;
-      } else {
-        for (; k1 != k0; --k1)
-          db.names.pop_back();
-      }
-      break;
+class CastExpr : public Expr {
+  // cast_kind<to>(from)
+  const StringView CastKind;
+  const Node *To;
+  const Node *From;
+
+public:
+  CastExpr(StringView CastKind_, Node *To_, Node *From_)
+      : CastKind(CastKind_), To(To_), From(From_) {
+    ParameterPackSize =
+      std::min(To->ParameterPackSize, From->ParameterPackSize);
+  }
+
+  void printLeft(OutputStream &S) const override {
+    S += CastKind;
+    S += "<";
+    To->printLeft(S);
+    S += ">(";
+    From->printLeft(S);
+    S += ")";
+  }
+};
+
+class SizeofParamPackExpr : public Expr {
+  Node *Pack;
+
+public:
+  SizeofParamPackExpr(Node *Pack_) : Pack(Pack_) {}
+
+  void printLeft(OutputStream &S) const override {
+    S += "sizeof...(";
+    ParameterPackExpansion PPE(Pack);
+    PPE.printLeft(S);
+    S += ")";
+  }
+};
+
+class CallExpr : public Expr {
+  const Node *Callee;
+  NodeArray Args;
+
+public:
+  CallExpr(Node *Callee_, NodeArray Args_) : Callee(Callee_), Args(Args_) {
+    for (Node *P : Args)
+      ParameterPackSize = std::min(ParameterPackSize, P->ParameterPackSize);
+    ParameterPackSize = std::min(ParameterPackSize, Callee->ParameterPackSize);
+  }
+
+  void printLeft(OutputStream &S) const override {
+    Callee->print(S);
+    S += "(";
+    Args.printWithComma(S);
+    S += ")";
+  }
+};
+
+class NewExpr : public Expr {
+  // new (expr_list) type(init_list)
+  NodeArray ExprList;
+  Node *Type;
+  NodeArray InitList;
+  bool IsGlobal; // ::operator new ?
+  bool IsArray;  // new[] ?
+public:
+  NewExpr(NodeArray ExprList_, Node *Type_, NodeArray InitList_, bool IsGlobal_,
+          bool IsArray_)
+      : ExprList(ExprList_), Type(Type_), InitList(InitList_),
+        IsGlobal(IsGlobal_), IsArray(IsArray_) {
+    for (Node *E : ExprList)
+      ParameterPackSize = std::min(ParameterPackSize, E->ParameterPackSize);
+    for (Node *I : InitList)
+      ParameterPackSize = std::min(ParameterPackSize, I->ParameterPackSize);
+    if (Type)
+      ParameterPackSize = std::min(ParameterPackSize, Type->ParameterPackSize);
+  }
+
+  void printLeft(OutputStream &S) const override {
+    if (IsGlobal)
+      S += "::operator ";
+    S += "new";
+    if (IsArray)
+      S += "[]";
+    S += ' ';
+    if (!ExprList.empty()) {
+      S += "(";
+      ExprList.printWithComma(S);
+      S += ")";
     }
-    case 'D':
-      t = parse_decltype(first, last, db);
-      if (t != first) {
-        if (db.names.empty())
-          return first;
-        db.subs.push_back(typename C::sub_type(1, db.names.back()));
-        first = t;
-      }
-      break;
-    case 'S':
-      t = parse_substitution(first, last, db);
-      if (t != first)
-        first = t;
-      else {
-        if (last - first > 2 && first[1] == 't') {
-          t = parse_unqualified_name(first + 2, last, db);
-          if (t != first + 2) {
-            if (db.names.empty())
-              return first;
-            db.names.back().first.insert(0, "std::");
-            db.subs.push_back(typename C::sub_type(1, db.names.back()));
-            first = t;
-          }
-        }
-      }
-      break;
+    Type->print(S);
+    if (!InitList.empty()) {
+      S += "(";
+      InitList.printWithComma(S);
+      S += ")";
     }
+
   }
-  return first;
-}
+};
 
-// <destructor-name> ::= <unresolved-type>                               # e.g.,
-// ~T or ~decltype(f())
-//                   ::= <simple-id>                                     # e.g.,
-//                   ~A<2*N>
-
-template <class C>
-static const char *parse_destructor_name(const char *first, const char *last,
-                                         C &db) {
-  if (first != last) {
-    const char *t = parse_unresolved_type(first, last, db);
-    if (t == first)
-      t = parse_simple_id(first, last, db);
-    if (t != first) {
-      if (db.names.empty())
-        return first;
-      db.names.back().first.insert(0, "~");
-      first = t;
-    }
-  }
-  return first;
-}
+class DeleteExpr : public Expr {
+  Node *Op;
+  bool IsGlobal;
+  bool IsArray;
 
-// <base-unresolved-name> ::= <simple-id>                                #
-// unresolved name
-//          extension     ::= <operator-name>                            #
-//          unresolved operator-function-id
-//          extension     ::= <operator-name> <template-args>            #
-//          unresolved operator template-id
-//                        ::= on <operator-name>                         #
-//                        unresolved operator-function-id
-//                        ::= on <operator-name> <template-args>         #
-//                        unresolved operator template-id
-//                        ::= dn <destructor-name>                       #
-//                        destructor or pseudo-destructor;
-//                                                                         #
-//                                                                         e.g.
-//                                                                         ~X or
-//                                                                         ~X<N-1>
-
-template <class C>
-static const char *parse_base_unresolved_name(const char *first,
-                                              const char *last, C &db) {
-  if (last - first >= 2) {
-    if ((first[0] == 'o' || first[0] == 'd') && first[1] == 'n') {
-      if (first[0] == 'o') {
-        const char *t = parse_operator_name(first + 2, last, db);
-        if (t != first + 2) {
-          first = parse_template_args(t, last, db);
-          if (first != t) {
-            if (db.names.size() < 2)
-              return first;
-            auto args = db.names.back().move_full();
-            db.names.pop_back();
-            db.names.back().first += std::move(args);
-          }
-        }
-      } else {
-        const char *t = parse_destructor_name(first + 2, last, db);
-        if (t != first + 2)
-          first = t;
-      }
+public:
+  DeleteExpr(Node *Op_, bool IsGlobal_, bool IsArray_)
+      : Op(Op_), IsGlobal(IsGlobal_), IsArray(IsArray_) {
+    ParameterPackSize = Op->ParameterPackSize;
+  }
+
+  void printLeft(OutputStream &S) const override {
+    if (IsGlobal)
+      S += "::";
+    S += "delete";
+    if (IsArray)
+      S += "[] ";
+    Op->print(S);
+  }
+};
+
+class PrefixExpr : public Expr {
+  StringView Prefix;
+  Node *Child;
+
+public:
+  PrefixExpr(StringView Prefix_, Node *Child_) : Prefix(Prefix_), Child(Child_) {
+    ParameterPackSize = Child->ParameterPackSize;
+  }
+
+  void printLeft(OutputStream &S) const override {
+    S += Prefix;
+    S += "(";
+    Child->print(S);
+    S += ")";
+  }
+};
+
+class FunctionParam : public Expr {
+  StringView Number;
+
+public:
+  FunctionParam(StringView Number_) : Number(Number_) {}
+
+  void printLeft(OutputStream &S) const override {
+    S += "fp";
+    S += Number;
+  }
+};
+
+class ConversionExpr : public Expr {
+  const Node *Type;
+  NodeArray Expressions;
+
+public:
+  ConversionExpr(const Node *Type_, NodeArray Expressions_)
+      : Type(Type_), Expressions(Expressions_) {
+    for (Node *E : Expressions)
+      ParameterPackSize = std::min(ParameterPackSize, E->ParameterPackSize);
+    ParameterPackSize = std::min(ParameterPackSize, Type->ParameterPackSize);
+  }
+
+  void printLeft(OutputStream &S) const override {
+    S += "(";
+    Type->print(S);
+    S += ")(";
+    Expressions.printWithComma(S);
+    S += ")";
+  }
+};
+
+class InitListExpr : public Expr {
+  Node *Ty;
+  NodeArray Inits;
+public:
+  InitListExpr(Node *Ty_, NodeArray Inits_)
+      : Ty(Ty_), Inits(Inits_) {
+    if (Ty)
+      ParameterPackSize = Ty->ParameterPackSize;
+    for (Node *I : Inits)
+      ParameterPackSize = std::min(I->ParameterPackSize, ParameterPackSize);
+  }
+
+  void printLeft(OutputStream &S) const override {
+    if (Ty)
+      Ty->print(S);
+    S += '{';
+    Inits.printWithComma(S);
+    S += '}';
+  }
+};
+
+class BracedExpr : public Expr {
+  Node *Elem;
+  Node *Init;
+  bool IsArray;
+public:
+  BracedExpr(Node *Elem_, Node *Init_, bool IsArray_)
+      : Expr(KBracedExpr), Elem(Elem_), Init(Init_), IsArray(IsArray_) {}
+
+  void printLeft(OutputStream &S) const override {
+    if (IsArray) {
+      S += '[';
+      Elem->print(S);
+      S += ']';
     } else {
-      const char *t = parse_simple_id(first, last, db);
-      if (t == first) {
-        t = parse_operator_name(first, last, db);
-        if (t != first) {
-          first = parse_template_args(t, last, db);
-          if (first != t) {
-            if (db.names.size() < 2)
-              return first;
-            auto args = db.names.back().move_full();
-            db.names.pop_back();
-            db.names.back().first += std::move(args);
-          }
-        }
-      } else
-        first = t;
+      S += '.';
+      Elem->print(S);
     }
+    if (Init->getKind() != KBracedExpr && Init->getKind() != KBracedRangeExpr)
+      S += " = ";
+    Init->print(S);
   }
-  return first;
-}
+};
 
-// <unresolved-qualifier-level> ::= <simple-id>
+class BracedRangeExpr : public Expr {
+  Node *First;
+  Node *Last;
+  Node *Init;
+public:
+  BracedRangeExpr(Node *First_, Node *Last_, Node *Init_)
+      : Expr(KBracedRangeExpr), First(First_), Last(Last_), Init(Init_) {}
+
+  void printLeft(OutputStream &S) const override {
+    S += '[';
+    First->print(S);
+    S += " ... ";
+    Last->print(S);
+    S += ']';
+    if (Init->getKind() != KBracedExpr && Init->getKind() != KBracedRangeExpr)
+      S += " = ";
+    Init->print(S);
+  }
+};
 
-template <class C>
-static const char *parse_unresolved_qualifier_level(const char *first,
-                                                    const char *last, C &db) {
-  return parse_simple_id(first, last, db);
-}
+class ThrowExpr : public Expr {
+  const Node *Op;
 
-// <unresolved-name>
-//  extension        ::= srN <unresolved-type> [<template-args>]
-//  <unresolved-qualifier-level>* E <base-unresolved-name>
-//                   ::= [gs] <base-unresolved-name>                     # x or
-//                   (with "gs") ::x
-//                   ::= [gs] sr <unresolved-qualifier-level>+ E
-//                   <base-unresolved-name>
-//                                                                       # A::x,
-//                                                                       N::y,
-//                                                                       A<T>::z;
-//                                                                       "gs"
-//                                                                       means
-//                                                                       leading
-//                                                                       "::"
-//                   ::= sr <unresolved-type> <base-unresolved-name>     # T::x
-//                   / decltype(p)::x
-//  extension        ::= sr <unresolved-type> <template-args>
-//  <base-unresolved-name>
-//                                                                       #
-//                                                                       T::N::x
-//                                                                       /decltype(p)::N::x
-//  (ignored)        ::= srN <unresolved-type>  <unresolved-qualifier-level>+ E
-//  <base-unresolved-name>
-
-template <class C>
-static const char *parse_unresolved_name(const char *first, const char *last,
-                                         C &db) {
-  if (last - first > 2) {
-    const char *t = first;
-    bool global = false;
-    if (t[0] == 'g' && t[1] == 's') {
-      global = true;
-      t += 2;
-    }
-    const char *t2 = parse_base_unresolved_name(t, last, db);
-    if (t2 != t) {
-      if (global) {
-        if (db.names.empty())
-          return first;
-        db.names.back().first.insert(0, "::");
-      }
-      first = t2;
-    } else if (last - t > 2 && t[0] == 's' && t[1] == 'r') {
-      if (t[2] == 'N') {
-        t += 3;
-        const char *t1 = parse_unresolved_type(t, last, db);
-        if (t1 == t || t1 == last)
-          return first;
-        t = t1;
-        t1 = parse_template_args(t, last, db);
-        if (t1 != t) {
-          if (db.names.size() < 2)
-            return first;
-          auto args = db.names.back().move_full();
-          db.names.pop_back();
-          db.names.back().first += std::move(args);
-          t = t1;
-          if (t == last) {
-            db.names.pop_back();
-            return first;
-          }
-        }
-        while (*t != 'E') {
-          t1 = parse_unresolved_qualifier_level(t, last, db);
-          if (t1 == t || t1 == last || db.names.size() < 2)
-            return first;
-          auto s = db.names.back().move_full();
-          db.names.pop_back();
-          db.names.back().first += "::" + std::move(s);
-          t = t1;
-        }
+public:
+  ThrowExpr(Node *Op_) : Op(Op_) {
+    ParameterPackSize = Op->ParameterPackSize;
+  }
+
+  void printLeft(OutputStream &S) const override {
+    S += "throw ";
+    Op->print(S);
+  }
+};
+
+class BoolExpr : public Expr {
+  bool Value;
+
+public:
+  BoolExpr(bool Value_) : Value(Value_) {}
+
+  void printLeft(OutputStream &S) const override {
+    S += Value ? StringView("true") : StringView("false");
+  }
+};
+
+class IntegerCastExpr : public Expr {
+  // ty(integer)
+  Node *Ty;
+  StringView Integer;
+
+public:
+  IntegerCastExpr(Node *Ty_, StringView Integer_) : Ty(Ty_), Integer(Integer_) {
+    ParameterPackSize = Ty->ParameterPackSize;
+  }
+
+  void printLeft(OutputStream &S) const override {
+    S += "(";
+    Ty->print(S);
+    S += ")";
+    S += Integer;
+  }
+};
+
+class IntegerExpr : public Expr {
+  StringView Type;
+  StringView Value;
+
+public:
+  IntegerExpr(StringView Type_, StringView Value_) : Type(Type_), Value(Value_) {}
+
+  void printLeft(OutputStream &S) const override {
+    if (Type.size() > 3) {
+      S += "(";
+      S += Type;
+      S += ")";
+    }
+
+    if (Value[0] == 'n') {
+      S += "-";
+      S += Value.dropFront(1);
+    } else
+      S += Value;
+
+    if (Type.size() <= 3)
+      S += Type;
+  }
+};
+
+template <class Float> struct FloatData;
+
+template <class Float> class FloatExpr : public Expr {
+  const StringView Contents;
+
+public:
+  FloatExpr(StringView Contents_) : Contents(Contents_) {}
+
+  void printLeft(OutputStream &s) const override {
+    const char *first = Contents.begin();
+    const char *last = Contents.end() + 1;
+
+    const size_t N = FloatData<Float>::mangled_size;
+    if (static_cast<std::size_t>(last - first) > N) {
+      last = first + N;
+      union {
+        Float value;
+        char buf[sizeof(Float)];
+      };
+      const char *t = first;
+      char *e = buf;
+      for (; t != last; ++t, ++e) {
+        unsigned d1 = isdigit(*t) ? static_cast<unsigned>(*t - '0')
+                                  : static_cast<unsigned>(*t - 'a' + 10);
         ++t;
-        t1 = parse_base_unresolved_name(t, last, db);
-        if (t1 == t) {
-          if (!db.names.empty())
-            db.names.pop_back();
-          return first;
-        }
-        if (db.names.size() < 2)
-          return first;
-        auto s = db.names.back().move_full();
-        db.names.pop_back();
-        db.names.back().first += "::" + std::move(s);
-        first = t1;
-      } else {
-        t += 2;
-        const char *t1 = parse_unresolved_type(t, last, db);
-        if (t1 != t) {
-          t = t1;
-          t1 = parse_template_args(t, last, db);
-          if (t1 != t) {
-            if (db.names.size() < 2)
-              return first;
-            auto args = db.names.back().move_full();
-            db.names.pop_back();
-            db.names.back().first += std::move(args);
-            t = t1;
-          }
-          t1 = parse_base_unresolved_name(t, last, db);
-          if (t1 == t) {
-            if (!db.names.empty())
-              db.names.pop_back();
-            return first;
-          }
-          if (db.names.size() < 2)
-            return first;
-          auto s = db.names.back().move_full();
-          db.names.pop_back();
-          db.names.back().first += "::" + std::move(s);
-          first = t1;
-        } else {
-          t1 = parse_unresolved_qualifier_level(t, last, db);
-          if (t1 == t || t1 == last)
-            return first;
-          t = t1;
-          if (global) {
-            if (db.names.empty())
-              return first;
-            db.names.back().first.insert(0, "::");
-          }
-          while (*t != 'E') {
-            t1 = parse_unresolved_qualifier_level(t, last, db);
-            if (t1 == t || t1 == last || db.names.size() < 2)
-              return first;
-            auto s = db.names.back().move_full();
-            db.names.pop_back();
-            db.names.back().first += "::" + std::move(s);
-            t = t1;
-          }
-          ++t;
-          t1 = parse_base_unresolved_name(t, last, db);
-          if (t1 == t) {
-            if (!db.names.empty())
-              db.names.pop_back();
-            return first;
-          }
-          if (db.names.size() < 2)
-            return first;
-          auto s = db.names.back().move_full();
-          db.names.pop_back();
-          db.names.back().first += "::" + std::move(s);
-          first = t1;
-        }
+        unsigned d0 = isdigit(*t) ? static_cast<unsigned>(*t - '0')
+                                  : static_cast<unsigned>(*t - 'a' + 10);
+        *e = static_cast<char>((d1 << 4) + d0);
       }
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+      std::reverse(buf, e);
+#endif
+      char num[FloatData<Float>::max_demangled_size] = {0};
+      int n = snprintf(num, sizeof(num), FloatData<Float>::spec, value);
+      s += StringView(num, num + n);
     }
   }
-  return first;
-}
+};
 
-// dt <expression> <unresolved-name>                    # expr.name
-
-template <class C>
-static const char *parse_dot_expr(const char *first, const char *last, C &db) {
-  if (last - first >= 3 && first[0] == 'd' && first[1] == 't') {
-    const char *t = parse_expression(first + 2, last, db);
-    if (t != first + 2) {
-      const char *t1 = parse_unresolved_name(t, last, db);
-      if (t1 != t) {
-        if (db.names.size() < 2)
-          return first;
-        auto name = db.names.back().move_full();
-        db.names.pop_back();
-        if (db.names.empty())
-          return first;
-        db.names.back().first += "." + name;
-        first = t1;
-      }
+class BumpPointerAllocator {
+  struct BlockMeta {
+    BlockMeta* Next;
+    size_t Current;
+  };
+
+  static constexpr size_t AllocSize = 4096;
+  static constexpr size_t UsableAllocSize = AllocSize - sizeof(BlockMeta);
+
+  alignas(16) char InitialBuffer[AllocSize];
+  BlockMeta* BlockList = nullptr;
+
+  void grow() {
+    char* NewMeta = new char[AllocSize];
+    BlockList = new (NewMeta) BlockMeta{BlockList, 0};
+  }
+
+  void* allocateMassive(size_t NBytes) {
+    NBytes += sizeof(BlockMeta);
+    BlockMeta* NewMeta = reinterpret_cast<BlockMeta*>(new char[NBytes]);
+    BlockList->Next = new (NewMeta) BlockMeta{BlockList->Next, 0};
+    return static_cast<void*>(NewMeta + 1);
+  }
+
+public:
+  BumpPointerAllocator()
+      : BlockList(new (InitialBuffer) BlockMeta{nullptr, 0}) {}
+
+  void* allocate(size_t N) {
+    N = (N + 15u) & ~15u;
+    if (N + BlockList->Current >= UsableAllocSize) {
+      if (N > UsableAllocSize)
+        return allocateMassive(N);
+      grow();
     }
+    BlockList->Current += N;
+    return static_cast<void*>(reinterpret_cast<char*>(BlockList + 1) +
+                              BlockList->Current - N);
   }
-  return first;
-}
 
-// cl <expression>+ E                                   # call
-
-template <class C>
-static const char *parse_call_expr(const char *first, const char *last, C &db) {
-  if (last - first >= 4 && first[0] == 'c' && first[1] == 'l') {
-    const char *t = parse_expression(first + 2, last, db);
-    if (t != first + 2) {
-      if (t == last)
-        return first;
-      if (db.names.empty())
-        return first;
-      db.names.back().first += db.names.back().second;
-      db.names.back().second = std::string();
-      db.names.back().first.append("(");
-      bool first_expr = true;
-      while (*t != 'E') {
-        const char *t1 = parse_expression(t, last, db);
-        if (t1 == t || t1 == last)
-          return first;
-        if (db.names.empty())
-          return first;
-        auto tmp = db.names.back().move_full();
-        db.names.pop_back();
-        if (!tmp.empty()) {
-          if (db.names.empty())
-            return first;
-          if (!first_expr) {
-            db.names.back().first.append(", ");
-            first_expr = false;
-          }
-          db.names.back().first.append(tmp);
-        }
-        t = t1;
-      }
-      ++t;
-      if (db.names.empty())
-        return first;
-      db.names.back().first.append(")");
-      first = t;
+  ~BumpPointerAllocator() {
+    while (BlockList) {
+      BlockMeta* Tmp = BlockList;
+      BlockList = BlockList->Next;
+      if (reinterpret_cast<char*>(Tmp) != InitialBuffer)
+        delete[] reinterpret_cast<char*>(Tmp);
     }
   }
-  return first;
-}
+};
 
-// [gs] nw <expression>* _ <type> E                     # new (expr-list) type
-// [gs] nw <expression>* _ <type> <initializer>         # new (expr-list) type
-// (init)
-// [gs] na <expression>* _ <type> E                     # new[] (expr-list) type
-// [gs] na <expression>* _ <type> <initializer>         # new[] (expr-list) type
-// (init)
-// <initializer> ::= pi <expression>* E                 # parenthesized
-// initialization
-
-template <class C>
-static const char *parse_new_expr(const char *first, const char *last, C &db) {
-  if (last - first >= 4) {
-    const char *t = first;
-    bool parsed_gs = false;
-    if (t[0] == 'g' && t[1] == 's') {
-      t += 2;
-      parsed_gs = true;
-    }
-    if (t[0] == 'n' && (t[1] == 'w' || t[1] == 'a')) {
-      bool is_array = t[1] == 'a';
-      t += 2;
-      if (t == last)
-        return first;
-      bool has_expr_list = false;
-      bool first_expr = true;
-      while (*t != '_') {
-        const char *t1 = parse_expression(t, last, db);
-        if (t1 == t || t1 == last)
-          return first;
-        has_expr_list = true;
-        if (!first_expr) {
-          if (db.names.empty())
-            return first;
-          auto tmp = db.names.back().move_full();
-          db.names.pop_back();
-          if (!tmp.empty()) {
-            if (db.names.empty())
-              return first;
-            db.names.back().first.append(", ");
-            db.names.back().first.append(tmp);
-            first_expr = false;
-          }
-        }
-        t = t1;
-      }
-      ++t;
-      const char *t1 = parse_type(t, last, db);
-      if (t1 == t || t1 == last)
-        return first;
-      t = t1;
-      bool has_init = false;
-      if (last - t >= 3 && t[0] == 'p' && t[1] == 'i') {
-        t += 2;
-        has_init = true;
-        first_expr = true;
-        while (*t != 'E') {
-          t1 = parse_expression(t, last, db);
-          if (t1 == t || t1 == last)
-            return first;
-          if (!first_expr) {
-            if (db.names.empty())
-              return first;
-            auto tmp = db.names.back().move_full();
-            db.names.pop_back();
-            if (!tmp.empty()) {
-              if (db.names.empty())
-                return first;
-              db.names.back().first.append(", ");
-              db.names.back().first.append(tmp);
-              first_expr = false;
-            }
-          }
-          t = t1;
-        }
-      }
-      if (*t != 'E')
-        return first;
-      std::string init_list;
-      if (has_init) {
-        if (db.names.empty())
-          return first;
-        init_list = db.names.back().move_full();
-        db.names.pop_back();
-      }
-      if (db.names.empty())
-        return first;
-      auto type = db.names.back().move_full();
-      db.names.pop_back();
-      std::string expr_list;
-      if (has_expr_list) {
-        if (db.names.empty())
-          return first;
-        expr_list = db.names.back().move_full();
-        db.names.pop_back();
-      }
-      std::string r;
-      if (parsed_gs)
-        r = "::";
-      if (is_array)
-        r += "[] ";
-      else
-        r += " ";
-      if (has_expr_list)
-        r += "(" + expr_list + ") ";
-      r += type;
-      if (has_init)
-        r += " (" + init_list + ")";
-      db.names.push_back(std::move(r));
-      first = t + 1;
+template <class T, size_t N>
+class PODSmallVector {
+  static_assert(std::is_pod<T>::value,
+                "T is required to be a plain old data type");
+
+  T* First;
+  T* Last;
+  T* Cap;
+  T Inline[N];
+
+  bool isInline() const { return First == Inline; }
+
+  void clearInline() {
+    First = Inline;
+    Last = Inline;
+    Cap = Inline + N;
+  }
+
+  void reserve(size_t NewCap) {
+    size_t S = size();
+    if (isInline()) {
+      auto* Tmp = static_cast<T*>(std::malloc(NewCap * sizeof(T)));
+      std::copy(First, Last, Tmp);
+      First = Tmp;
+    } else
+      First = static_cast<T*>(std::realloc(First, NewCap * sizeof(T)));
+    Last = First + S;
+    Cap = First + NewCap;
+  }
+
+public:
+  PODSmallVector() : First(Inline), Last(First), Cap(Inline + N) {}
+
+  PODSmallVector(const PODSmallVector&) = delete;
+  PODSmallVector& operator=(const PODSmallVector&) = delete;
+
+  PODSmallVector(PODSmallVector&& Other) : PODSmallVector() {
+    if (Other.isInline()) {
+      std::copy(Other.begin(), Other.end(), First);
+      Last = First + Other.size();
+      Other.clear();
+      return;
     }
+
+    First = Other.First;
+    Last = Other.Last;
+    Cap = Other.Cap;
+    Other.clearInline();
   }
-  return first;
-}
 
-// cv <type> <expression>                               # conversion with one
-// argument
-// cv <type> _ <expression>* E                          # conversion with a
-// different number of arguments
-
-template <class C>
-static const char *parse_conversion_expr(const char *first, const char *last,
-                                         C &db) {
-  if (last - first >= 3 && first[0] == 'c' && first[1] == 'v') {
-    bool try_to_parse_template_args = db.try_to_parse_template_args;
-    db.try_to_parse_template_args = false;
-    const char *t = parse_type(first + 2, last, db);
-    db.try_to_parse_template_args = try_to_parse_template_args;
-    if (t != first + 2 && t != last) {
-      if (*t != '_') {
-        const char *t1 = parse_expression(t, last, db);
-        if (t1 == t)
-          return first;
-        t = t1;
-      } else {
-        ++t;
-        if (t == last)
-          return first;
-        if (*t == 'E')
-          db.names.emplace_back();
-        else {
-          bool first_expr = true;
-          while (*t != 'E') {
-            const char *t1 = parse_expression(t, last, db);
-            if (t1 == t || t1 == last)
-              return first;
-            if (!first_expr) {
-              if (db.names.empty())
-                return first;
-              auto tmp = db.names.back().move_full();
-              db.names.pop_back();
-              if (!tmp.empty()) {
-                if (db.names.empty())
-                  return first;
-                db.names.back().first.append(", ");
-                db.names.back().first.append(tmp);
-                first_expr = false;
-              }
-            }
-            t = t1;
-          }
-        }
-        ++t;
+  PODSmallVector& operator=(PODSmallVector&& Other) {
+    if (Other.isInline()) {
+      if (!isInline()) {
+        std::free(First);
+        clearInline();
       }
-      if (db.names.size() < 2)
-        return first;
-      auto tmp = db.names.back().move_full();
-      db.names.pop_back();
-      db.names.back() = "(" + db.names.back().move_full() + ")(" + tmp + ")";
-      first = t;
+      std::copy(Other.begin(), Other.end(), First);
+      Last = First + Other.size();
+      Other.clear();
+      return *this;
     }
+
+    if (isInline()) {
+      First = Other.First;
+      Last = Other.Last;
+      Cap = Other.Cap;
+      Other.clearInline();
+      return *this;
+    }
+
+    std::swap(First, Other.First);
+    std::swap(Last, Other.Last);
+    std::swap(Cap, Other.Cap);
+    Other.clear();
+    return *this;
   }
-  return first;
-}
 
-// pt <expression> <expression>                    # expr->name
-
-template <class C>
-static const char *parse_arrow_expr(const char *first, const char *last,
-                                    C &db) {
-  if (last - first >= 3 && first[0] == 'p' && first[1] == 't') {
-    const char *t = parse_expression(first + 2, last, db);
-    if (t != first + 2) {
-      const char *t1 = parse_expression(t, last, db);
-      if (t1 != t) {
-        if (db.names.size() < 2)
-          return first;
-        auto tmp = db.names.back().move_full();
-        db.names.pop_back();
-        db.names.back().first += "->";
-        db.names.back().first += tmp;
-        first = t1;
-      }
+  void push_back(const T& Elem) {
+    if (Last == Cap)
+      reserve(size() * 2);
+    *Last++ = Elem;
+  }
+
+  void pop_back() {
+    assert(Last != First && "Popping empty vector!");
+    --Last;
+  }
+
+  void dropBack(size_t Index) {
+    assert(Index <= size() && "dropBack() can't expand!");
+    Last = First + Index;
+  }
+
+  T* begin() { return First; }
+  T* end() { return Last; }
+
+  bool empty() const { return First == Last; }
+  size_t size() const { return static_cast<size_t>(Last - First); }
+  T& back() {
+    assert(Last != First && "Calling back() on empty vector!");
+    return *(Last - 1);
+  }
+  T& operator[](size_t Index) {
+    assert(Index < size() && "Invalid access!");
+    return *(begin() + Index);
+  }
+  void clear() { Last = First; }
+
+  ~PODSmallVector() {
+    if (!isInline())
+      std::free(First);
+  }
+};
+
+struct Db {
+  const char *First;
+  const char *Last;
+
+  // Name stack, this is used by the parser to hold temporary names that were
+  // parsed. The parser colapses multiple names into new nodes to construct
+  // the AST. Once the parser is finished, names.size() == 1.
+  PODSmallVector<Node *, 32> Names;
+
+  // Substitution table. Itanium supports name substitutions as a means of
+  // compression. The string "S42_" refers to the 44nd entry (base-36) in this
+  // table.
+  PODSmallVector<Node *, 32> Subs;
+
+  // Template parameter table. Like the above, but referenced like "T42_".
+  // This has a smaller size compared to Subs and Names because it can be
+  // stored on the stack.
+  PODSmallVector<Node *, 8> TemplateParams;
+
+  unsigned EncodingDepth = 0;
+  bool TagTemplates = true;
+  bool FixForwardReferences = false;
+  bool TryToParseTemplateArgs = true;
+  bool ParsingLambdaParams = false;
+
+  BumpPointerAllocator ASTAllocator;
+
+  Db(const char *First_, const char *Last_) : First(First_), Last(Last_) {}
+
+  template <class T, class... Args> T *make(Args &&... args) {
+    return new (ASTAllocator.allocate(sizeof(T)))
+        T(std::forward<Args>(args)...);
+  }
+
+  template <class It> NodeArray makeNodeArray(It begin, It end) {
+    size_t sz = static_cast<size_t>(end - begin);
+    void *mem = ASTAllocator.allocate(sizeof(Node *) * sz);
+    Node **data = new (mem) Node *[sz];
+    std::copy(begin, end, data);
+    return NodeArray(data, sz);
+  }
+
+  NodeArray popTrailingNodeArray(size_t FromPosition) {
+    assert(FromPosition <= Names.size());
+    NodeArray res =
+        makeNodeArray(Names.begin() + (long)FromPosition, Names.end());
+    Names.dropBack(FromPosition);
+    return res;
+  }
+
+  bool consumeIf(StringView S) {
+    if (StringView(First, Last).startsWith(S)) {
+      First += S.size();
+      return true;
     }
+    return false;
   }
-  return first;
-}
 
-//  <ref-qualifier> ::= R                   # & ref-qualifier
-//  <ref-qualifier> ::= O                   # && ref-qualifier
-
-// <function-type> ::= F [Y] <bare-function-type> [<ref-qualifier>] E
-
-template <class C>
-static const char *parse_function_type(const char *first, const char *last,
-                                       C &db) {
-  if (first != last && *first == 'F') {
-    const char *t = first + 1;
-    if (t != last) {
-      if (*t == 'Y') {
-        /* extern "C" */
-        if (++t == last)
-          return first;
-      }
-      const char *t1 = parse_type(t, last, db);
-      if (t1 != t) {
-        t = t1;
-        std::string sig("(");
-        int ref_qual = 0;
-        while (true) {
-          if (t == last) {
-            if (!db.names.empty())
-              db.names.pop_back();
-            return first;
-          }
-          if (*t == 'E') {
-            ++t;
-            break;
-          }
-          if (*t == 'v') {
-            ++t;
-            continue;
-          }
-          if (*t == 'R' && t + 1 != last && t[1] == 'E') {
-            ref_qual = 1;
-            ++t;
-            continue;
-          }
-          if (*t == 'O' && t + 1 != last && t[1] == 'E') {
-            ref_qual = 2;
-            ++t;
-            continue;
-          }
-          size_t k0 = db.names.size();
-          t1 = parse_type(t, last, db);
-          size_t k1 = db.names.size();
-          if (t1 == t || t1 == last)
-            return first;
-          for (size_t k = k0; k < k1; ++k) {
-            if (sig.size() > 1)
-              sig += ", ";
-            sig += db.names[k].move_full();
-          }
-          for (size_t k = k0; k < k1; ++k)
-            db.names.pop_back();
-          t = t1;
-        }
-        sig += ")";
-        switch (ref_qual) {
-        case 1:
-          sig += " &";
-          break;
-        case 2:
-          sig += " &&";
-          break;
-        }
-        if (db.names.empty())
-          return first;
-        db.names.back().first += " ";
-        db.names.back().second.insert(0, sig);
-        first = t;
-      }
+  bool consumeIf(char C) {
+    if (First != Last && *First == C) {
+      ++First;
+      return true;
     }
+    return false;
   }
-  return first;
-}
 
-// <pointer-to-member-type> ::= M <class type> <member type>
+  char consume() { return First != Last ? *First++ : '\0'; }
 
-template <class C>
-static const char *parse_pointer_to_member_type(const char *first,
-                                                const char *last, C &db) {
-  if (first != last && *first == 'M') {
-    const char *t = parse_type(first + 1, last, db);
-    if (t != first + 1) {
-      const char *t2 = parse_type(t, last, db);
-      if (t2 != t) {
-        if (db.names.size() < 2)
-          return first;
-        auto func = std::move(db.names.back());
-        db.names.pop_back();
-        auto class_type = std::move(db.names.back());
-        if (!func.second.empty() && func.second.front() == '(') {
-          db.names.back().first =
-              std::move(func.first) + "(" + class_type.move_full() + "::*";
-          db.names.back().second = ")" + std::move(func.second);
-        } else {
-          db.names.back().first =
-              std::move(func.first) + " " + class_type.move_full() + "::*";
-          db.names.back().second = std::move(func.second);
-        }
-        first = t2;
-      }
-    }
+  char look(unsigned Lookahead = 0) {
+    if (static_cast<size_t>(Last - First) <= Lookahead)
+      return '\0';
+    return First[Lookahead];
   }
-  return first;
-}
 
-// <array-type> ::= A <positive dimension number> _ <element type>
-//              ::= A [<dimension expression>] _ <element type>
+  size_t numLeft() const { return static_cast<size_t>(Last - First); }
+
+  StringView parseNumber(bool AllowNegative = false);
+  Qualifiers parseCVQualifiers();
+  bool parsePositiveInteger(size_t *Out);
+  StringView parseBareSourceName();
+
+  bool parseSeqId(size_t *Out);
+  Node *parseSubstitution();
+  Node *parseTemplateParam();
+  Node *parseTemplateArgs();
+  Node *parseTemplateArg();
+
+  /// Parse the <expr> production.
+  Node *parseExpr();
+  Node *parsePrefixExpr(StringView Kind);
+  Node *parseBinaryExpr(StringView Kind);
+  Node *parseIntegerLiteral(StringView Lit);
+  Node *parseExprPrimary();
+  template <class Float> Node *parseFloatingLiteral();
+  Node *parseFunctionParam();
+  Node *parseNewExpr();
+  Node *parseConversionExpr();
+  Node *parseBracedExpr();
+
+  /// Parse the <type> production.
+  Node *parseType();
+  Node *parseFunctionType();
+  Node *parseVectorType();
+  Node *parseDecltype();
+  Node *parseArrayType();
+  Node *parsePointerToMemberType();
+  Node *parseClassEnumType();
+  Node *parseQualifiedType();
+
+  Node *parseEncoding();
+  bool parseCallOffset();
+  Node *parseSpecialName();
+
+  /// Holds some extra information about a <name> that is being parsed. This
+  /// information is only pertinent if the <name> refers to an <encoding>.
+  struct NameState {
+    bool CtorDtorConversion = false;
+    bool EndsWithTemplateArgs = false;
+    Qualifiers CVQualifiers = QualNone;
+    FunctionRefQual ReferenceQualifier = FrefQualNone;
+  };
+
+  /// Parse the <name> production>
+  Node *parseName(NameState *State = nullptr);
+  Node *parseLocalName(NameState *State);
+  Node *parseOperatorName(NameState *State);
+  Node *parseUnqualifiedName(NameState *State);
+  Node *parseUnnamedTypeName(NameState *State);
+  Node *parseSourceName(NameState *State);
+  Node *parseUnscopedName(NameState *State);
+  Node *parseNestedName(NameState *State);
+  Node *parseCtorDtorName(Node *&SoFar, NameState *State);
+
+  Node *parseAbiTags(Node *N);
+
+  /// Parse the <unresolved-name> production.
+  Node *parseUnresolvedName();
+  Node *parseSimpleId();
+  Node *parseBaseUnresolvedName();
+  Node *parseUnresolvedType();
+  Node *parseDestructorName();
+
+  /// Top-level entry point into the parser.
+  Node *parse();
+};
 
-template <class C>
-static const char *parse_array_type(const char *first, const char *last,
-                                    C &db) {
-  if (first != last && *first == 'A' && first + 1 != last) {
-    if (first[1] == '_') {
-      const char *t = parse_type(first + 2, last, db);
-      if (t != first + 2) {
-        if (db.names.empty())
-          return first;
-        if (db.names.back().second.substr(0, 2) == " [")
-          db.names.back().second.erase(0, 1);
-        db.names.back().second.insert(0, " []");
-        first = t;
-      }
-    } else if ('1' <= first[1] && first[1] <= '9') {
-      const char *t = parse_number(first + 1, last);
-      if (t != last && *t == '_') {
-        const char *t2 = parse_type(t + 1, last, db);
-        if (t2 != t + 1) {
-          if (db.names.empty())
-            return first;
-          if (db.names.back().second.substr(0, 2) == " [")
-            db.names.back().second.erase(0, 1);
-          db.names.back().second.insert(0,
-                                        " [" + std::string(first + 1, t) + "]");
-          first = t2;
-        }
-      }
-    } else {
-      const char *t = parse_expression(first + 1, last, db);
-      if (t != first + 1 && t != last && *t == '_') {
-        const char *t2 = parse_type(++t, last, db);
-        if (t2 != t) {
-          if (db.names.size() < 2)
-            return first;
-          auto type = std::move(db.names.back());
-          db.names.pop_back();
-          auto expr = std::move(db.names.back());
-          db.names.back().first = std::move(type.first);
-          if (type.second.substr(0, 2) == " [")
-            type.second.erase(0, 1);
-          db.names.back().second =
-              " [" + expr.move_full() + "]" + std::move(type.second);
-          first = t2;
-        }
-      }
-    }
+const char* parse_discriminator(const char* first, const char* last);
+
+// <name> ::= <nested-name> // N
+//        ::= <local-name> # See Scope Encoding below  // Z
+//        ::= <unscoped-template-name> <template-args>
+//        ::= <unscoped-name>
+//
+// <unscoped-template-name> ::= <unscoped-name>
+//                          ::= <substitution>
+Node *Db::parseName(NameState *State) {
+  consumeIf('L'); // extension
+
+  if (look() == 'N')
+    return parseNestedName(State);
+  if (look() == 'Z')
+    return parseLocalName(State);
+
+  //        ::= <unscoped-template-name> <template-args>
+  if (look() == 'S' && look(1) != 't') {
+    Node *S = parseSubstitution();
+    if (S == nullptr)
+      return nullptr;
+    if (look() != 'I')
+      return nullptr;
+    Node *TA = parseTemplateArgs();
+    if (TA == nullptr)
+      return nullptr;
+    if (State) State->EndsWithTemplateArgs = true;
+    return make<NameWithTemplateArgs>(S, TA);
+  }
+
+  Node *N = parseUnscopedName(State);
+  if (N == nullptr)
+    return nullptr;
+  //        ::= <unscoped-template-name> <template-args>
+  if (look() == 'I') {
+    Subs.push_back(N);
+    Node *TA = parseTemplateArgs();
+    if (TA == nullptr)
+      return nullptr;
+    if (State) State->EndsWithTemplateArgs = true;
+    return make<NameWithTemplateArgs>(N, TA);
   }
-  return first;
+  //        ::= <unscoped-name>
+  return N;
 }
 
-// <decltype>  ::= Dt <expression> E  # decltype of an id-expression or class
-// member access (C++0x)
-//             ::= DT <expression> E  # decltype of an expression (C++0x)
+// <local-name> := Z <function encoding> E <entity name> [<discriminator>]
+//              := Z <function encoding> E s [<discriminator>]
+//              := Z <function encoding> Ed [ <parameter number> ] _ <entity name>
+Node *Db::parseLocalName(NameState *State) {
+  if (!consumeIf('Z'))
+    return nullptr;
+  Node *Encoding = parseEncoding();
+  if (Encoding == nullptr || !consumeIf('E'))
+    return nullptr;
 
-template <class C>
-static const char *parse_decltype(const char *first, const char *last, C &db) {
-  if (last - first >= 4 && first[0] == 'D') {
-    switch (first[1]) {
-    case 't':
-    case 'T': {
-      const char *t = parse_expression(first + 2, last, db);
-      if (t != first + 2 && t != last && *t == 'E') {
-        if (db.names.empty())
-          return first;
-        db.names.back() = "decltype(" + db.names.back().move_full() + ")";
-        first = t + 1;
-      }
-    } break;
-    }
+  if (consumeIf('s')) {
+    First = parse_discriminator(First, Last);
+    return make<QualifiedName>(Encoding, make<NameType>("string literal"));
   }
-  return first;
+
+  if (consumeIf('d')) {
+    parseNumber(true);
+    if (!consumeIf('_'))
+      return nullptr;
+    Node *N = parseName(State);
+    if (N == nullptr)
+      return nullptr;
+    return make<QualifiedName>(Encoding, N);
+  }
+
+  Node *Entity = parseName(State);
+  if (Entity == nullptr)
+    return nullptr;
+  First = parse_discriminator(First, Last);
+  return make<QualifiedName>(Encoding, Entity);
 }
 
-// extension:
-// <vector-type>           ::= Dv <positive dimension number> _
-//                                    <extended element type>
-//                         ::= Dv [<dimension expression>] _ <element type>
-// <extended element type> ::= <element type>
-//                         ::= p # AltiVec vector pixel
+// <unscoped-name> ::= <unqualified-name>
+//                 ::= St <unqualified-name>   # ::std::
+// extension       ::= StL<unqualified-name>
+Node *Db::parseUnscopedName(NameState *State) {
+ if (consumeIf("StL") || consumeIf("St")) {
+   Node *R = parseUnqualifiedName(State);
+   if (R == nullptr)
+     return nullptr;
+   return make<StdQualifiedName>(R);
+ }
+ return parseUnqualifiedName(State);
+}
 
-template <class C>
-static const char *parse_vector_type(const char *first, const char *last,
-                                     C &db) {
-  if (last - first > 3 && first[0] == 'D' && first[1] == 'v') {
-    if ('1' <= first[2] && first[2] <= '9') {
-      const char *t = parse_number(first + 2, last);
-      if (t == last || *t != '_')
-        return first;
-      const char *num = first + 2;
-      size_t sz = static_cast<size_t>(t - num);
-      if (++t != last) {
-        if (*t != 'p') {
-          const char *t1 = parse_type(t, last, db);
-          if (t1 != t) {
-            if (db.names.empty())
-              return first;
-            db.names.back().first += " vector[" + std::string(num, sz) + "]";
-            first = t1;
-          }
-        } else {
-          ++t;
-          db.names.push_back("pixel vector[" + std::string(num, sz) + "]");
-          first = t;
-        }
-      }
-    } else {
-      std::string num;
-      const char *t1 = first + 2;
-      if (*t1 != '_') {
-        const char *t = parse_expression(t1, last, db);
-        if (t != t1) {
-          if (db.names.empty())
-            return first;
-          num = db.names.back().move_full();
-          db.names.pop_back();
-          t1 = t;
-        }
-      }
-      if (t1 != last && *t1 == '_' && ++t1 != last) {
-        const char *t = parse_type(t1, last, db);
-        if (t != t1) {
-          if (db.names.empty())
-            return first;
-          db.names.back().first += " vector[" + num + "]";
-          first = t;
-        }
-      }
-    }
-  }
-  return first;
+// <unqualified-name> ::= <operator-name> [abi-tags]
+//                    ::= <ctor-dtor-name>
+//                    ::= <source-name>
+//                    ::= <unnamed-type-name>
+//                    ::= DC <source-name>+ E      # structured binding declaration
+Node *Db::parseUnqualifiedName(NameState *State) {
+ // <ctor-dtor-name>s are special-cased in parseNestedName().
+ Node *Result;
+ if (look() == 'U')
+   Result = parseUnnamedTypeName(State);
+ else if (look() >= '1' && look() <= '9')
+   Result = parseSourceName(State);
+ else if (consumeIf("DC")) {
+   size_t BindingsBegin = Names.size();
+   do {
+     Node *Binding = parseSourceName(State);
+     if (Binding == nullptr)
+       return nullptr;
+     Names.push_back(Binding);
+   } while (!consumeIf('E'));
+   Result = make<StructuredBindingName>(popTrailingNodeArray(BindingsBegin));
+ } else
+   Result = parseOperatorName(State);
+ if (Result != nullptr)
+   Result = parseAbiTags(Result);
+ return Result;
 }
 
-// <type> ::= <builtin-type>
-//        ::= <function-type>
-//        ::= <class-enum-type>
-//        ::= <array-type>
-//        ::= <pointer-to-member-type>
-//        ::= <template-param>
-//        ::= <template-template-param> <template-args>
-//        ::= <decltype>
-//        ::= <substitution>
-//        ::= <CV-qualifiers> <type>
-//        ::= P <type>        # pointer-to
-//        ::= R <type>        # reference-to
-//        ::= O <type>        # rvalue reference-to (C++0x)
-//        ::= C <type>        # complex pair (C 2000)
-//        ::= G <type>        # imaginary (C 2000)
-//        ::= Dp <type>       # pack expansion (C++0x)
-//        ::= U <source-name> <type>  # vendor extended type qualifier
-// extension := U <objc-name> <objc-type>  # objc-type<identifier>
-// extension := <vector-type> # <vector-type> starts with Dv
-
-// <objc-name> ::= <k0 number> objcproto <k1 number> <identifier>  # k0 = 9 +
-// <number of digits in k1> + k1
-// <objc-type> := <source-name>  # PU<11+>objcproto 11objc_object<source-name>
-// 11objc_object -> id<source-name>
-
-template <class C>
-static const char *parse_type(const char *first, const char *last, C &db) {
-  if (first != last) {
-    switch (*first) {
-    case 'r':
-    case 'V':
-    case 'K': {
-      unsigned cv = 0;
-      const char *t = parse_cv_qualifiers(first, last, cv);
-      if (t != first) {
-        bool is_function = *t == 'F';
-        size_t k0 = db.names.size();
-        const char *t1 = parse_type(t, last, db);
-        size_t k1 = db.names.size();
-        if (t1 != t) {
-          if (is_function)
-            db.subs.pop_back();
-          db.subs.emplace_back();
-          for (size_t k = k0; k < k1; ++k) {
-            if (is_function) {
-              auto &name = db.names[k].second;
-              size_t p = name.size();
-
-              if (name[p - 2] == '&' && name[p - 1] == '&')
-                p -= 2;
-              else if (name.back() == '&')
-                p -= 1;
-
-              if (cv & CV_const) {
-                name.insert(p, " const");
-                p += 6;
-              }
-              if (cv & CV_volatile) {
-                name.insert(p, " volatile");
-                p += 9;
-              }
-              if (cv & CV_restrict)
-                name.insert(p, " restrict");
-            } else {
-              if (cv & CV_const)
-                db.names[k].first.append(" const");
-              if (cv & CV_volatile)
-                db.names[k].first.append(" volatile");
-              if (cv & CV_restrict)
-                db.names[k].first.append(" restrict");
-            }
-            db.subs.back().push_back(db.names[k]);
-          }
-          first = t1;
-        }
-      }
-    } break;
-    default: {
-      const char *t = parse_builtin_type(first, last, db);
-      if (t != first) {
-        first = t;
-      } else {
-        switch (*first) {
-        case 'A':
-          t = parse_array_type(first, last, db);
-          if (t != first) {
-            if (db.names.empty())
-              return first;
-            first = t;
-            db.subs.push_back(typename C::sub_type(1, db.names.back()));
-          }
-          break;
-        case 'C':
-          t = parse_type(first + 1, last, db);
-          if (t != first + 1) {
-            if (db.names.empty())
-              return first;
-            db.names.back().first.append(" complex");
-            first = t;
-            db.subs.push_back(typename C::sub_type(1, db.names.back()));
-          }
-          break;
-        case 'F':
-          t = parse_function_type(first, last, db);
-          if (t != first) {
-            if (db.names.empty())
-              return first;
-            first = t;
-            db.subs.push_back(typename C::sub_type(1, db.names.back()));
-          }
-          break;
-        case 'G':
-          t = parse_type(first + 1, last, db);
-          if (t != first + 1) {
-            if (db.names.empty())
-              return first;
-            db.names.back().first.append(" imaginary");
-            first = t;
-            db.subs.push_back(typename C::sub_type(1, db.names.back()));
-          }
-          break;
-        case 'M':
-          t = parse_pointer_to_member_type(first, last, db);
-          if (t != first) {
-            if (db.names.empty())
-              return first;
-            first = t;
-            db.subs.push_back(typename C::sub_type(1, db.names.back()));
-          }
-          break;
-        case 'O': {
-          size_t k0 = db.names.size();
-          t = parse_type(first + 1, last, db);
-          size_t k1 = db.names.size();
-          if (t != first + 1) {
-            db.subs.emplace_back();
-            for (size_t k = k0; k < k1; ++k) {
-              if (db.names[k].second.substr(0, 2) == " [") {
-                db.names[k].first += " (";
-                db.names[k].second.insert(0, ")");
-              } else if (!db.names[k].second.empty() &&
-                         db.names[k].second.front() == '(') {
-                db.names[k].first += "(";
-                db.names[k].second.insert(0, ")");
-              }
-              db.names[k].first.append("&&");
-              db.subs.back().push_back(db.names[k]);
-            }
-            first = t;
-          }
-          break;
-        }
-        case 'P': {
-          size_t k0 = db.names.size();
-          t = parse_type(first + 1, last, db);
-          size_t k1 = db.names.size();
-          if (t != first + 1) {
-            db.subs.emplace_back();
-            for (size_t k = k0; k < k1; ++k) {
-              if (db.names[k].second.substr(0, 2) == " [") {
-                db.names[k].first += " (";
-                db.names[k].second.insert(0, ")");
-              } else if (!db.names[k].second.empty() &&
-                         db.names[k].second.front() == '(') {
-                db.names[k].first += "(";
-                db.names[k].second.insert(0, ")");
-              }
-              if (first[1] != 'U' ||
-                  db.names[k].first.substr(0, 12) != "objc_object<") {
-                db.names[k].first.append("*");
-              } else {
-                db.names[k].first.replace(0, 11, "id");
-              }
-              db.subs.back().push_back(db.names[k]);
-            }
-            first = t;
-          }
-          break;
-        }
-        case 'R': {
-          size_t k0 = db.names.size();
-          t = parse_type(first + 1, last, db);
-          size_t k1 = db.names.size();
-          if (t != first + 1) {
-            db.subs.emplace_back();
-            for (size_t k = k0; k < k1; ++k) {
-              if (db.names[k].second.substr(0, 2) == " [") {
-                db.names[k].first += " (";
-                db.names[k].second.insert(0, ")");
-              } else if (!db.names[k].second.empty() &&
-                         db.names[k].second.front() == '(') {
-                db.names[k].first += "(";
-                db.names[k].second.insert(0, ")");
-              }
-              db.names[k].first.append("&");
-              db.subs.back().push_back(db.names[k]);
-            }
-            first = t;
-          }
-          break;
-        }
-        case 'T': {
-          size_t k0 = db.names.size();
-          t = parse_template_param(first, last, db);
-          size_t k1 = db.names.size();
-          if (t != first) {
-            db.subs.emplace_back();
-            for (size_t k = k0; k < k1; ++k)
-              db.subs.back().push_back(db.names[k]);
-            if (db.try_to_parse_template_args && k1 == k0 + 1) {
-              const char *t1 = parse_template_args(t, last, db);
-              if (t1 != t) {
-                auto args = db.names.back().move_full();
-                db.names.pop_back();
-                db.names.back().first += std::move(args);
-                db.subs.push_back(typename C::sub_type(1, db.names.back()));
-                t = t1;
-              }
-            }
-            first = t;
-          }
-          break;
-        }
-        case 'U':
-          if (first + 1 != last) {
-            t = parse_source_name(first + 1, last, db);
-            if (t != first + 1) {
-              const char *t2 = parse_type(t, last, db);
-              if (t2 != t) {
-                if (db.names.size() < 2)
-                  return first;
-                auto type = db.names.back().move_full();
-                db.names.pop_back();
-                if (db.names.back().first.substr(0, 9) != "objcproto") {
-                  db.names.back() = type + " " + db.names.back().move_full();
-                } else {
-                  auto proto = db.names.back().move_full();
-                  db.names.pop_back();
-                  t = parse_source_name(proto.data() + 9,
-                                        proto.data() + proto.size(), db);
-                  if (t != proto.data() + 9) {
-                    db.names.back() =
-                        type + "<" + db.names.back().move_full() + ">";
-                  } else {
-                    db.names.push_back(type + " " + proto);
-                  }
-                }
-                db.subs.push_back(typename C::sub_type(1, db.names.back()));
-                first = t2;
-              }
-            }
-          }
-          break;
-        case 'S':
-          if (first + 1 != last && first[1] == 't') {
-            t = parse_name(first, last, db);
-            if (t != first) {
-              if (db.names.empty())
-                return first;
-              db.subs.push_back(typename C::sub_type(1, db.names.back()));
-              first = t;
-            }
-          } else {
-            t = parse_substitution(first, last, db);
-            if (t != first) {
-              first = t;
-              // Parsed a substitution.  If the substitution is a
-              //  <template-param> it might be followed by <template-args>.
-              t = parse_template_args(first, last, db);
-              if (t != first) {
-                if (db.names.size() < 2)
-                  return first;
-                auto template_args = db.names.back().move_full();
-                db.names.pop_back();
-                db.names.back().first += template_args;
-                // Need to create substitution for <template-template-param>
-                // <template-args>
-                db.subs.push_back(typename C::sub_type(1, db.names.back()));
-                first = t;
-              }
-            }
-          }
-          break;
-        case 'D':
-          if (first + 1 != last) {
-            switch (first[1]) {
-            case 'p': {
-              size_t k0 = db.names.size();
-              t = parse_type(first + 2, last, db);
-              size_t k1 = db.names.size();
-              if (t != first + 2) {
-                db.subs.emplace_back();
-                for (size_t k = k0; k < k1; ++k)
-                  db.subs.back().push_back(db.names[k]);
-                first = t;
-                return first;
-              }
-              break;
-            }
-            case 't':
-            case 'T':
-              t = parse_decltype(first, last, db);
-              if (t != first) {
-                if (db.names.empty())
-                  return first;
-                db.subs.push_back(typename C::sub_type(1, db.names.back()));
-                first = t;
-                return first;
-              }
-              break;
-            case 'v':
-              t = parse_vector_type(first, last, db);
-              if (t != first) {
-                if (db.names.empty())
-                  return first;
-                db.subs.push_back(typename C::sub_type(1, db.names.back()));
-                first = t;
-                return first;
-              }
-              break;
-            }
-          }
-          LLVM_FALLTHROUGH;
-        default:
-          // must check for builtin-types before class-enum-types to avoid
-          // ambiguities with operator-names
-          t = parse_builtin_type(first, last, db);
-          if (t != first) {
-            first = t;
-          } else {
-            t = parse_name(first, last, db);
-            if (t != first) {
-              if (db.names.empty())
-                return first;
-              db.subs.push_back(typename C::sub_type(1, db.names.back()));
-              first = t;
-            }
-          }
-          break;
-        }
-      }
-      break;
-    }
+// <unnamed-type-name> ::= Ut [<nonnegative number>] _
+//                     ::= <closure-type-name>
+//
+// <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
+//
+// <lambda-sig> ::= <parameter type>+  # Parameter types or "v" if the lambda has no parameters
+Node *Db::parseUnnamedTypeName(NameState *) {
+  if (consumeIf("Ut")) {
+    StringView Count = parseNumber();
+    if (!consumeIf('_'))
+      return nullptr;
+    return make<UnnamedTypeName>(Count);
+  }
+  if (consumeIf("Ul")) {
+    NodeArray Params;
+    SwapAndRestore<bool> SwapParams(ParsingLambdaParams, true);
+    if (!consumeIf("vE")) {
+      size_t ParamsBegin = Names.size();
+      do {
+        Node *P = parseType();
+        if (P == nullptr)
+          return nullptr;
+        Names.push_back(P);
+      } while (!consumeIf('E'));
+      Params = popTrailingNodeArray(ParamsBegin);
     }
+    StringView Count = parseNumber();
+    if (!consumeIf('_'))
+      return nullptr;
+    return make<ClosureTypeName>(Params, Count);
   }
-  return first;
+  return nullptr;
 }
 
-//   <operator-name>
-//                   ::= aa    # &&
+// <source-name> ::= <positive length number> <identifier>
+Node *Db::parseSourceName(NameState *) {
+  size_t Length = 0;
+  if (parsePositiveInteger(&Length))
+    return nullptr;
+  if (numLeft() < Length || Length == 0)
+    return nullptr;
+  StringView Name(First, First + Length);
+  First += Length;
+  if (Name.startsWith("_GLOBAL__N"))
+    return make<NameType>("(anonymous namespace)");
+  return make<NameType>(Name);
+}
+
+//   <operator-name> ::= aa    # &&
 //                   ::= ad    # & (unary)
 //                   ::= an    # &
 //                   ::= aN    # &=
@@ -2024,1783 +2343,1944 @@ static const char *parse_type(const char *first, const char *last, C &db) {
 //                   ::= rM    # %=
 //                   ::= rs    # >>
 //                   ::= rS    # >>=
-//                   ::= v <digit> <source-name>        # vendor extended
-//                   operator
-
-template <class C>
-static const char *parse_operator_name(const char *first, const char *last,
-                                       C &db) {
-  if (last - first >= 2) {
-    switch (first[0]) {
+//                   ::= ss    # <=> C++2a
+//                   ::= v <digit> <source-name>        # vendor extended operator
+Node *Db::parseOperatorName(NameState *State) {
+  switch (look()) {
+  case 'a':
+    switch (look(1)) {
     case 'a':
-      switch (first[1]) {
-      case 'a':
-        db.names.push_back("operator&&");
-        first += 2;
-        break;
-      case 'd':
-      case 'n':
-        db.names.push_back("operator&");
-        first += 2;
-        break;
-      case 'N':
-        db.names.push_back("operator&=");
-        first += 2;
-        break;
-      case 'S':
-        db.names.push_back("operator=");
-        first += 2;
-        break;
-      }
-      break;
-    case 'c':
-      switch (first[1]) {
-      case 'l':
-        db.names.push_back("operator()");
-        first += 2;
-        break;
-      case 'm':
-        db.names.push_back("operator,");
-        first += 2;
-        break;
-      case 'o':
-        db.names.push_back("operator~");
-        first += 2;
-        break;
-      case 'v': {
-        bool try_to_parse_template_args = db.try_to_parse_template_args;
-        db.try_to_parse_template_args = false;
-        const char *t = parse_type(first + 2, last, db);
-        db.try_to_parse_template_args = try_to_parse_template_args;
-        if (t != first + 2) {
-          if (db.names.empty())
-            return first;
-          db.names.back().first.insert(0, "operator ");
-          db.parsed_ctor_dtor_cv = true;
-          first = t;
-        }
-      } break;
-      }
-      break;
+      First += 2;
+      return make<NameType>("operator&&");
     case 'd':
-      switch (first[1]) {
-      case 'a':
-        db.names.push_back("operator delete[]");
-        first += 2;
-        break;
-      case 'e':
-        db.names.push_back("operator*");
-        first += 2;
-        break;
-      case 'l':
-        db.names.push_back("operator delete");
-        first += 2;
-        break;
-      case 'v':
-        db.names.push_back("operator/");
-        first += 2;
-        break;
-      case 'V':
-        db.names.push_back("operator/=");
-        first += 2;
-        break;
-      }
-      break;
+    case 'n':
+      First += 2;
+      return make<NameType>("operator&");
+    case 'N':
+      First += 2;
+      return make<NameType>("operator&=");
+    case 'S':
+      First += 2;
+      return make<NameType>("operator=");
+    }
+    return nullptr;
+  case 'c':
+    switch (look(1)) {
+    case 'l':
+      First += 2;
+      return make<NameType>("operator()");
+    case 'm':
+      First += 2;
+      return make<NameType>("operator,");
+    case 'o':
+      First += 2;
+      return make<NameType>("operator~");
+    //                   ::= cv <type>    # (cast)
+    case 'v': {
+      SwapAndRestore<bool> SaveTemplate(TryToParseTemplateArgs, false);
+      First += 2;
+      Node *Ty = parseType();
+      if (Ty == nullptr)
+        return nullptr;
+      if (State) State->CtorDtorConversion = true;
+      return make<ConversionOperatorType>(Ty);
+    }
+    }
+    return nullptr;
+  case 'd':
+    switch (look(1)) {
+    case 'a':
+      First += 2;
+      return make<NameType>("operator delete[]");
     case 'e':
-      switch (first[1]) {
-      case 'o':
-        db.names.push_back("operator^");
-        first += 2;
-        break;
-      case 'O':
-        db.names.push_back("operator^=");
-        first += 2;
-        break;
-      case 'q':
-        db.names.push_back("operator==");
-        first += 2;
-        break;
-      }
-      break;
-    case 'g':
-      switch (first[1]) {
-      case 'e':
-        db.names.push_back("operator>=");
-        first += 2;
-        break;
-      case 't':
-        db.names.push_back("operator>");
-        first += 2;
-        break;
-      }
-      break;
+      First += 2;
+      return make<NameType>("operator*");
+    case 'l':
+      First += 2;
+      return make<NameType>("operator delete");
+    case 'v':
+      First += 2;
+      return make<NameType>("operator/");
+    case 'V':
+      First += 2;
+      return make<NameType>("operator/=");
+    }
+    return nullptr;
+  case 'e':
+    switch (look(1)) {
+    case 'o':
+      First += 2;
+      return make<NameType>("operator^");
+    case 'O':
+      First += 2;
+      return make<NameType>("operator^=");
+    case 'q':
+      First += 2;
+      return make<NameType>("operator==");
+    }
+    return nullptr;
+  case 'g':
+    switch (look(1)) {
+    case 'e':
+      First += 2;
+      return make<NameType>("operator>=");
+    case 't':
+      First += 2;
+      return make<NameType>("operator>");
+    }
+    return nullptr;
+  case 'i':
+    if (look(1) == 'x') {
+      First += 2;
+      return make<NameType>("operator[]");
+    }
+    return nullptr;
+  case 'l':
+    switch (look(1)) {
+    case 'e':
+      First += 2;
+      return make<NameType>("operator<=");
+    //                   ::= li <source-name>  # operator ""
+    case 'i': {
+      First += 2;
+      Node *SN = parseSourceName(State);
+      if (SN == nullptr)
+        return nullptr;
+      return make<LiteralOperator>(SN);
+    }
+    case 's':
+      First += 2;
+      return make<NameType>("operator<<");
+    case 'S':
+      First += 2;
+      return make<NameType>("operator<<=");
+    case 't':
+      First += 2;
+      return make<NameType>("operator<");
+    }
+    return nullptr;
+  case 'm':
+    switch (look(1)) {
     case 'i':
-      if (first[1] == 'x') {
-        db.names.push_back("operator[]");
-        first += 2;
-      }
-      break;
+      First += 2;
+      return make<NameType>("operator-");
+    case 'I':
+      First += 2;
+      return make<NameType>("operator-=");
     case 'l':
-      switch (first[1]) {
-      case 'e':
-        db.names.push_back("operator<=");
-        first += 2;
-        break;
-      case 'i': {
-        const char *t = parse_source_name(first + 2, last, db);
-        if (t != first + 2) {
-          if (db.names.empty())
-            return first;
-          db.names.back().first.insert(0, "operator\"\" ");
-          first = t;
-        }
-      } break;
-      case 's':
-        db.names.push_back("operator<<");
-        first += 2;
-        break;
-      case 'S':
-        db.names.push_back("operator<<=");
-        first += 2;
-        break;
-      case 't':
-        db.names.push_back("operator<");
-        first += 2;
-        break;
-      }
-      break;
+      First += 2;
+      return make<NameType>("operator*");
+    case 'L':
+      First += 2;
+      return make<NameType>("operator*=");
     case 'm':
-      switch (first[1]) {
-      case 'i':
-        db.names.push_back("operator-");
-        first += 2;
-        break;
-      case 'I':
-        db.names.push_back("operator-=");
-        first += 2;
-        break;
-      case 'l':
-        db.names.push_back("operator*");
-        first += 2;
-        break;
-      case 'L':
-        db.names.push_back("operator*=");
-        first += 2;
-        break;
-      case 'm':
-        db.names.push_back("operator--");
-        first += 2;
-        break;
-      }
-      break;
-    case 'n':
-      switch (first[1]) {
-      case 'a':
-        db.names.push_back("operator new[]");
-        first += 2;
-        break;
-      case 'e':
-        db.names.push_back("operator!=");
-        first += 2;
-        break;
-      case 'g':
-        db.names.push_back("operator-");
-        first += 2;
-        break;
-      case 't':
-        db.names.push_back("operator!");
-        first += 2;
-        break;
-      case 'w':
-        db.names.push_back("operator new");
-        first += 2;
-        break;
-      }
-      break;
+      First += 2;
+      return make<NameType>("operator--");
+    }
+    return nullptr;
+  case 'n':
+    switch (look(1)) {
+    case 'a':
+      First += 2;
+      return make<NameType>("operator new[]");
+    case 'e':
+      First += 2;
+      return make<NameType>("operator!=");
+    case 'g':
+      First += 2;
+      return make<NameType>("operator-");
+    case 't':
+      First += 2;
+      return make<NameType>("operator!");
+    case 'w':
+      First += 2;
+      return make<NameType>("operator new");
+    }
+    return nullptr;
+  case 'o':
+    switch (look(1)) {
     case 'o':
-      switch (first[1]) {
-      case 'o':
-        db.names.push_back("operator||");
-        first += 2;
-        break;
-      case 'r':
-        db.names.push_back("operator|");
-        first += 2;
-        break;
-      case 'R':
-        db.names.push_back("operator|=");
-        first += 2;
-        break;
-      }
-      break;
-    case 'p':
-      switch (first[1]) {
-      case 'm':
-        db.names.push_back("operator->*");
-        first += 2;
-        break;
-      case 'l':
-        db.names.push_back("operator+");
-        first += 2;
-        break;
-      case 'L':
-        db.names.push_back("operator+=");
-        first += 2;
-        break;
-      case 'p':
-        db.names.push_back("operator++");
-        first += 2;
-        break;
-      case 's':
-        db.names.push_back("operator+");
-        first += 2;
-        break;
-      case 't':
-        db.names.push_back("operator->");
-        first += 2;
-        break;
-      }
-      break;
-    case 'q':
-      if (first[1] == 'u') {
-        db.names.push_back("operator?");
-        first += 2;
-      }
-      break;
+      First += 2;
+      return make<NameType>("operator||");
     case 'r':
-      switch (first[1]) {
-      case 'm':
-        db.names.push_back("operator%");
-        first += 2;
-        break;
-      case 'M':
-        db.names.push_back("operator%=");
-        first += 2;
-        break;
-      case 's':
-        db.names.push_back("operator>>");
-        first += 2;
-        break;
-      case 'S':
-        db.names.push_back("operator>>=");
-        first += 2;
-        break;
-      }
-      break;
-    case 'v':
-      if (std::isdigit(first[1])) {
-        const char *t = parse_source_name(first + 2, last, db);
-        if (t != first + 2) {
-          if (db.names.empty())
-            return first;
-          db.names.back().first.insert(0, "operator ");
-          first = t;
-        }
-      }
-      break;
+      First += 2;
+      return make<NameType>("operator|");
+    case 'R':
+      First += 2;
+      return make<NameType>("operator|=");
     }
-  }
-  return first;
-}
-
-template <class C>
-static const char *parse_integer_literal(const char *first, const char *last,
-                                         const std::string &lit, C &db) {
-  const char *t = parse_number(first, last);
-  if (t != first && t != last && *t == 'E') {
-    if (lit.size() > 3)
-      db.names.push_back("(" + lit + ")");
-    else
-      db.names.emplace_back();
-    if (*first == 'n') {
-      db.names.back().first += '-';
-      ++first;
+    return nullptr;
+  case 'p':
+    switch (look(1)) {
+    case 'm':
+      First += 2;
+      return make<NameType>("operator->*");
+    case 'l':
+      First += 2;
+      return make<NameType>("operator+");
+    case 'L':
+      First += 2;
+      return make<NameType>("operator+=");
+    case 'p':
+      First += 2;
+      return make<NameType>("operator++");
+    case 's':
+      First += 2;
+      return make<NameType>("operator+");
+    case 't':
+      First += 2;
+      return make<NameType>("operator->");
+    }
+    return nullptr;
+  case 'q':
+    if (look(1) == 'u') {
+      First += 2;
+      return make<NameType>("operator?");
+    }
+    return nullptr;
+  case 'r':
+    switch (look(1)) {
+    case 'm':
+      First += 2;
+      return make<NameType>("operator%");
+    case 'M':
+      First += 2;
+      return make<NameType>("operator%=");
+    case 's':
+      First += 2;
+      return make<NameType>("operator>>");
+    case 'S':
+      First += 2;
+      return make<NameType>("operator>>=");
+    }
+    return nullptr;
+  case 's':
+    if (look(1) == 's') {
+      First += 2;
+      return make<NameType>("operator<=>");
+    }
+    return nullptr;
+  // ::= v <digit> <source-name>        # vendor extended operator
+  case 'v':
+    if (std::isdigit(look(1))) {
+      First += 2;
+      Node *SN = parseSourceName(State);
+      if (SN == nullptr)
+        return nullptr;
+      return make<ConversionOperatorType>(SN);
     }
-    db.names.back().first.append(first, t);
-    if (lit.size() <= 3)
-      db.names.back().first += lit;
-    first = t + 1;
+    return nullptr;
   }
-  return first;
+  return nullptr;
 }
 
-// <expr-primary> ::= L <type> <value number> E                          #
-// integer literal
-//                ::= L <type> <value float> E                           #
-//                floating literal
-//                ::= L <string type> E                                  #
-//                string literal
-//                ::= L <nullptr type> E                                 #
-//                nullptr literal (i.e., "LDnE")
-//                ::= L <type> <real-part float> _ <imag-part float> E   #
-//                complex floating point literal (C 2000)
-//                ::= L <mangled-name> E                                 #
-//                external name
-
-template <class C>
-static const char *parse_expr_primary(const char *first, const char *last,
-                                      C &db) {
-  if (last - first >= 4 && *first == 'L') {
-    switch (first[1]) {
-    case 'w': {
-      const char *t = parse_integer_literal(first + 2, last, "wchar_t", db);
-      if (t != first + 2)
-        first = t;
-    } break;
-    case 'b':
-      if (first[3] == 'E') {
-        switch (first[2]) {
-        case '0':
-          db.names.push_back("false");
-          first += 4;
-          break;
-        case '1':
-          db.names.push_back("true");
-          first += 4;
-          break;
-        }
-      }
-      break;
-    case 'c': {
-      const char *t = parse_integer_literal(first + 2, last, "char", db);
-      if (t != first + 2)
-        first = t;
-    } break;
-    case 'a': {
-      const char *t = parse_integer_literal(first + 2, last, "signed char", db);
-      if (t != first + 2)
-        first = t;
-    } break;
-    case 'h': {
-      const char *t =
-          parse_integer_literal(first + 2, last, "unsigned char", db);
-      if (t != first + 2)
-        first = t;
-    } break;
-    case 's': {
-      const char *t = parse_integer_literal(first + 2, last, "short", db);
-      if (t != first + 2)
-        first = t;
-    } break;
-    case 't': {
-      const char *t =
-          parse_integer_literal(first + 2, last, "unsigned short", db);
-      if (t != first + 2)
-        first = t;
-    } break;
-    case 'i': {
-      const char *t = parse_integer_literal(first + 2, last, "", db);
-      if (t != first + 2)
-        first = t;
-    } break;
-    case 'j': {
-      const char *t = parse_integer_literal(first + 2, last, "u", db);
-      if (t != first + 2)
-        first = t;
-    } break;
-    case 'l': {
-      const char *t = parse_integer_literal(first + 2, last, "l", db);
-      if (t != first + 2)
-        first = t;
-    } break;
-    case 'm': {
-      const char *t = parse_integer_literal(first + 2, last, "ul", db);
-      if (t != first + 2)
-        first = t;
-    } break;
-    case 'x': {
-      const char *t = parse_integer_literal(first + 2, last, "ll", db);
-      if (t != first + 2)
-        first = t;
-    } break;
-    case 'y': {
-      const char *t = parse_integer_literal(first + 2, last, "ull", db);
-      if (t != first + 2)
-        first = t;
-    } break;
-    case 'n': {
-      const char *t = parse_integer_literal(first + 2, last, "__int128", db);
-      if (t != first + 2)
-        first = t;
-    } break;
-    case 'o': {
-      const char *t =
-          parse_integer_literal(first + 2, last, "unsigned __int128", db);
-      if (t != first + 2)
-        first = t;
-    } break;
-    case 'f': {
-      const char *t = parse_floating_number<float>(first + 2, last, db);
-      if (t != first + 2)
-        first = t;
-    } break;
-    case 'd': {
-      const char *t = parse_floating_number<double>(first + 2, last, db);
-      if (t != first + 2)
-        first = t;
-    } break;
-    case 'e': {
-      const char *t = parse_floating_number<long double>(first + 2, last, db);
-      if (t != first + 2)
-        first = t;
-    } break;
-    case '_':
-      if (first[2] == 'Z') {
-        const char *t = parse_encoding(first + 3, last, db);
-        if (t != first + 3 && t != last && *t == 'E')
-          first = t + 1;
-      }
-      break;
-    case 'T':
-      // Invalid mangled name per
-      //   http://sourcerytools.com/pipermail/cxx-abi-dev/2011-August/002422.html
+// <ctor-dtor-name> ::= C1  # complete object constructor
+//                  ::= C2  # base object constructor
+//                  ::= C3  # complete object allocating constructor
+//   extension      ::= C5    # ?
+//                  ::= D0  # deleting destructor
+//                  ::= D1  # complete object destructor
+//                  ::= D2  # base object destructor
+//   extension      ::= D5    # ?
+Node *Db::parseCtorDtorName(Node *&SoFar, NameState *State) {
+  if (SoFar->K == Node::KSpecialSubstitution) {
+    auto SSK = static_cast<SpecialSubstitution *>(SoFar)->SSK;
+    switch (SSK) {
+    case SpecialSubKind::string:
+    case SpecialSubKind::istream:
+    case SpecialSubKind::ostream:
+    case SpecialSubKind::iostream:
+      SoFar = make<ExpandedSpecialSubstitution>(SSK);
+    default:
       break;
-    default: {
-      // might be named type
-      const char *t = parse_type(first + 1, last, db);
-      if (t != first + 1 && t != last) {
-        if (*t != 'E') {
-          const char *n = t;
-          for (; n != last && isdigit(*n); ++n)
-            ;
-          if (n != t && n != last && *n == 'E') {
-            if (db.names.empty())
-              return first;
-            db.names.back() =
-                "(" + db.names.back().move_full() + ")" + std::string(t, n);
-            first = n + 1;
-            break;
-          }
-        } else {
-          first = t + 1;
-          break;
-        }
-      }
     }
+  }
+
+  if (consumeIf('C')) {
+    bool IsInherited = consumeIf('I');
+    if (look() != '1' && look() != '2' && look() != '3' && look() != '5')
+      return nullptr;
+    ++First;
+    if (State) State->CtorDtorConversion = true;
+    if (IsInherited) {
+      if (parseName() == nullptr)
+        return nullptr;
     }
+    return make<CtorDtorName>(SoFar, false);
+  }
+
+  if (look() == 'D' &&
+      (look(1) == '0' || look(1) == '1' || look(1) == '2' || look(1) == '5')) {
+    First += 2;
+    if (State) State->CtorDtorConversion = true;
+    return make<CtorDtorName>(SoFar, true);
   }
-  return first;
+
+  return nullptr;
 }
 
-static std::string base_name(std::string &s) {
-  if (s.empty())
-    return s;
-  if (s == "std::string") {
-    s = "std::basic_string<char, std::char_traits<char>, std::allocator<char> "
-        ">";
-    return "basic_string";
-  }
-  if (s == "std::istream") {
-    s = "std::basic_istream<char, std::char_traits<char> >";
-    return "basic_istream";
-  }
-  if (s == "std::ostream") {
-    s = "std::basic_ostream<char, std::char_traits<char> >";
-    return "basic_ostream";
-  }
-  if (s == "std::iostream") {
-    s = "std::basic_iostream<char, std::char_traits<char> >";
-    return "basic_iostream";
-  }
-  const char *const pf = s.data();
-  const char *pe = pf + s.size();
-  if (pe[-1] == '>') {
-    unsigned c = 1;
-    while (true) {
-      if (--pe == pf)
-        return std::string();
-      if (pe[-1] == '<') {
-        if (--c == 0) {
-          --pe;
-          break;
-        }
-      } else if (pe[-1] == '>')
-        ++c;
+// <nested-name> ::= N [<CV-Qualifiers>] [<ref-qualifier>] <prefix> <unqualified-name> E
+//               ::= N [<CV-Qualifiers>] [<ref-qualifier>] <template-prefix> <template-args> E
+//
+// <prefix> ::= <prefix> <unqualified-name>
+//          ::= <template-prefix> <template-args>
+//          ::= <template-param>
+//          ::= <decltype>
+//          ::= # empty
+//          ::= <substitution>
+//          ::= <prefix> <data-member-prefix>
+//  extension ::= L
+//
+// <template-prefix> ::= <prefix> <template unqualified-name>
+//                   ::= <template-param>
+//                   ::= <substitution>
+Node *Db::parseNestedName(NameState *State) {
+  if (!consumeIf('N'))
+    return nullptr;
+
+  Qualifiers CVTmp = parseCVQualifiers();
+  if (State) State->CVQualifiers = CVTmp;
+
+  if (consumeIf('O')) {
+    if (State) State->ReferenceQualifier = FrefQualRValue;
+  } else if (consumeIf('R')) {
+    if (State) State->ReferenceQualifier = FrefQualLValue;
+  } else
+    if (State) State->ReferenceQualifier = FrefQualNone;
+
+  Node *SoFar = nullptr;
+  auto PushComponent = [&](Node *Comp) {
+    if (SoFar) SoFar = make<QualifiedName>(SoFar, Comp);
+    else       SoFar = Comp;
+    if (State) State->EndsWithTemplateArgs = false;
+  };
+
+  if (consumeIf("St"))
+    SoFar = make<NameType>("std");
+
+  while (!consumeIf('E')) {
+    consumeIf('L'); // extension
+
+    //          ::= <template-param>
+    if (look() == 'T') {
+      Node *TP = parseTemplateParam();
+      if (TP == nullptr)
+        return nullptr;
+      PushComponent(TP);
+      Subs.push_back(SoFar);
+      continue;
     }
-  }
-  if (pe - pf <= 1)
-    return std::string();
-  const char *p0 = pe - 1;
-  for (; p0 != pf; --p0) {
-    if (*p0 == ':') {
-      ++p0;
-      break;
+
+    //          ::= <template-prefix> <template-args>
+    if (look() == 'I') {
+      Node *TA = parseTemplateArgs();
+      if (TA == nullptr || SoFar == nullptr)
+        return nullptr;
+      SoFar = make<NameWithTemplateArgs>(SoFar, TA);
+      if (State) State->EndsWithTemplateArgs = true;
+      Subs.push_back(SoFar);
+      continue;
     }
-    if (!isalpha(*p0) && !isdigit(*p0) && *p0 != '_') {
-      return std::string();
+
+    //          ::= <decltype>
+    if (look() == 'D' && (look(1) == 't' || look(1) == 'T')) {
+      Node *DT = parseDecltype();
+      if (DT == nullptr)
+        return nullptr;
+      PushComponent(DT);
+      Subs.push_back(SoFar);
+      continue;
     }
-  }
-  return std::string(p0, pe);
-}
 
-// <ctor-dtor-name> ::= C1    # complete object constructor
-//                  ::= C2    # base object constructor
-//                  ::= C3    # complete object allocating constructor
-//   extension      ::= C5    # ?
-//                  ::= D0    # deleting destructor
-//                  ::= D1    # complete object destructor
-//                  ::= D2    # base object destructor
-//   extension      ::= D5    # ?
+    //          ::= <substitution>
+    if (look() == 'S' && look(1) != 't') {
+      Node *S = parseSubstitution();
+      if (S == nullptr)
+        return nullptr;
+      PushComponent(S);
+      if (SoFar != S)
+        Subs.push_back(S);
+      continue;
+    }
 
-template <class C>
-static const char *parse_ctor_dtor_name(const char *first, const char *last,
-                                        C &db) {
-  if (last - first >= 2 && !db.names.empty()) {
-    switch (first[0]) {
-    case 'C':
-      switch (first[1]) {
-      case '1':
-      case '2':
-      case '3':
-      case '5':
-        if (db.names.empty())
-          return first;
-        db.names.push_back(base_name(db.names.back().first));
-        first += 2;
-        db.parsed_ctor_dtor_cv = true;
-        break;
-      }
-      break;
-    case 'D':
-      switch (first[1]) {
-      case '0':
-      case '1':
-      case '2':
-      case '5':
-        if (db.names.empty())
-          return first;
-        db.names.push_back("~" + base_name(db.names.back().first));
-        first += 2;
-        db.parsed_ctor_dtor_cv = true;
-        break;
-      }
-      break;
+    // Parse an <unqualified-name> thats actually a <ctor-dtor-name>.
+    if (look() == 'C' || (look() == 'D' && look(1) != 'C')) {
+      if (SoFar == nullptr)
+        return nullptr;
+      Node *CtorDtor = parseCtorDtorName(SoFar, State);
+      if (CtorDtor == nullptr)
+        return nullptr;
+      PushComponent(CtorDtor);
+      SoFar = parseAbiTags(SoFar);
+      if (SoFar == nullptr)
+        return nullptr;
+      Subs.push_back(SoFar);
+      continue;
     }
+
+    //          ::= <prefix> <unqualified-name>
+    Node *N = parseUnqualifiedName(State);
+    if (N == nullptr)
+      return nullptr;
+    PushComponent(N);
+    Subs.push_back(SoFar);
   }
-  return first;
+
+  if (SoFar == nullptr || Subs.empty())
+    return nullptr;
+
+  Subs.pop_back();
+  return SoFar;
 }
 
-// <unnamed-type-name> ::= Ut [ <nonnegative number> ] _
-//                     ::= <closure-type-name>
-//
-// <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
-//
-// <lambda-sig> ::= <parameter type>+  # Parameter types or "v" if the lambda
-// has no parameters
-
-template <class C>
-static const char *parse_unnamed_type_name(const char *first, const char *last,
-                                           C &db) {
-  if (last - first > 2 && first[0] == 'U') {
-    char type = first[1];
-    switch (type) {
-    case 't': {
-      db.names.push_back(std::string("'unnamed"));
-      const char *t0 = first + 2;
-      if (t0 == last) {
-        db.names.pop_back();
-        return first;
-      }
-      if (std::isdigit(*t0)) {
-        const char *t1 = t0 + 1;
-        while (t1 != last && std::isdigit(*t1))
-          ++t1;
-        db.names.back().first.append(t0, t1);
-        t0 = t1;
-      }
-      db.names.back().first.push_back('\'');
-      if (t0 == last || *t0 != '_') {
-        db.names.pop_back();
-        return first;
-      }
-      first = t0 + 1;
-    } break;
-    case 'l': {
-      size_t lambda_pos = db.names.size();
-      db.names.push_back(std::string("'lambda'("));
-      const char *t0 = first + 2;
-      if (first[2] == 'v') {
-        db.names.back().first += ')';
-        ++t0;
-      } else {
-        bool is_first_it = true;
-        while (true) {
-          long k0 = static_cast<long>(db.names.size());
-          const char *t1 = parse_type(t0, last, db);
-          long k1 = static_cast<long>(db.names.size());
-          if (t1 == t0)
-            break;
-          if (k0 >= k1)
-            return first;
-          // If the call to parse_type above found a pack expansion
-          // substitution, then multiple names could have been
-          // inserted into the name table. Walk through the names,
-          // appending each onto the lambda's parameter list.
-          std::for_each(db.names.begin() + k0, db.names.begin() + k1,
-                        [&](typename C::sub_type::value_type &pair) {
-                          if (pair.empty())
-                            return;
-                          auto &lambda = db.names[lambda_pos].first;
-                          if (!is_first_it)
-                            lambda.append(", ");
-                          is_first_it = false;
-                          lambda.append(pair.move_full());
-                        });
-          db.names.erase(db.names.begin() + k0, db.names.end());
-          t0 = t1;
-        }
-        if (is_first_it) {
-          if (!db.names.empty())
-            db.names.pop_back();
-          return first;
-        }
-        if (db.names.empty() || db.names.size() - 1 != lambda_pos)
-          return first;
-        db.names.back().first.append(")");
-      }
-      if (t0 == last || *t0 != 'E') {
-        if (!db.names.empty())
-          db.names.pop_back();
-        return first;
-      }
-      ++t0;
-      if (t0 == last) {
-        if (!db.names.empty())
-          db.names.pop_back();
-        return first;
-      }
-      if (std::isdigit(*t0)) {
-        const char *t1 = t0 + 1;
-        while (t1 != last && std::isdigit(*t1))
-          ++t1;
-        db.names.back().first.insert(db.names.back().first.begin() + 7, t0, t1);
-        t0 = t1;
-      }
-      if (t0 == last || *t0 != '_') {
-        if (!db.names.empty())
-          db.names.pop_back();
-        return first;
-      }
-      first = t0 + 1;
-    } break;
-    }
+// <simple-id> ::= <source-name> [ <template-args> ]
+Node *Db::parseSimpleId() {
+  Node *SN = parseSourceName(/*NameState=*/nullptr);
+  if (SN == nullptr)
+    return nullptr;
+  if (look() == 'I') {
+    Node *TA = parseTemplateArgs();
+    if (TA == nullptr)
+      return nullptr;
+    return make<NameWithTemplateArgs>(SN, TA);
   }
-  return first;
+  return SN;
 }
 
-// <unqualified-name> ::= <operator-name>
-//                    ::= <ctor-dtor-name>
-//                    ::= <source-name>
-//                    ::= <unnamed-type-name>
+// <destructor-name> ::= <unresolved-type>  # e.g., ~T or ~decltype(f())
+//                   ::= <simple-id>        # e.g., ~A<2*N>
+Node *Db::parseDestructorName() {
+  Node *Result;
+  if (std::isdigit(look()))
+    Result = parseSimpleId();
+  else
+    Result = parseUnresolvedType();
+  if (Result == nullptr)
+    return nullptr;
+  return make<DtorName>(Result);
+}
 
-template <class C>
-static const char *parse_unqualified_name(const char *first, const char *last,
-                                          C &db) {
-  if (first != last) {
-    const char *t;
-    switch (*first) {
-    case 'C':
-    case 'D':
-      t = parse_ctor_dtor_name(first, last, db);
-      if (t != first)
-        first = t;
-      break;
-    case 'U':
-      t = parse_unnamed_type_name(first, last, db);
-      if (t != first)
-        first = t;
-      break;
-    case '1':
-    case '2':
-    case '3':
-    case '4':
-    case '5':
-    case '6':
-    case '7':
-    case '8':
-    case '9':
-      t = parse_source_name(first, last, db);
-      if (t != first)
-        first = t;
-      break;
-    default:
-      t = parse_operator_name(first, last, db);
-      if (t != first)
-        first = t;
-      break;
-    };
+// <unresolved-type> ::= <template-param>
+//                   ::= <decltype>
+//                   ::= <substitution>
+Node *Db::parseUnresolvedType() {
+  if (look() == 'T') {
+    Node *TP = parseTemplateParam();
+    if (TP == nullptr)
+      return nullptr;
+    Subs.push_back(TP);
+    return TP;
   }
-  return first;
+  if (look() == 'D') {
+    Node *DT = parseDecltype();
+    if (DT == nullptr)
+      return nullptr;
+    Subs.push_back(DT);
+    return DT;
+  }
+  return parseSubstitution();
 }
 
-// <unscoped-name> ::= <unqualified-name>
-//                 ::= St <unqualified-name>   # ::std::
-// extension       ::= StL<unqualified-name>
+// <base-unresolved-name> ::= <simple-id>                                # unresolved name
+//          extension     ::= <operator-name>                            # unresolved operator-function-id
+//          extension     ::= <operator-name> <template-args>            # unresolved operator template-id
+//                        ::= on <operator-name>                         # unresolved operator-function-id
+//                        ::= on <operator-name> <template-args>         # unresolved operator template-id
+//                        ::= dn <destructor-name>                       # destructor or pseudo-destructor;
+//                                                                         # e.g. ~X or ~X<N-1>
+Node *Db::parseBaseUnresolvedName() {
+  if (std::isdigit(look()))
+    return parseSimpleId();
 
-template <class C>
-static const char *parse_unscoped_name(const char *first, const char *last,
-                                       C &db) {
-  if (last - first >= 2) {
-    const char *t0 = first;
-    bool St = false;
-    if (first[0] == 'S' && first[1] == 't') {
-      t0 += 2;
-      St = true;
-      if (t0 != last && *t0 == 'L')
-        ++t0;
-    }
-    const char *t1 = parse_unqualified_name(t0, last, db);
-    if (t1 != t0) {
-      if (St) {
-        if (db.names.empty())
-          return first;
-        db.names.back().first.insert(0, "std::");
-      }
-      first = t1;
-    }
+  if (consumeIf("dn"))
+    return parseDestructorName();
+
+  consumeIf("on");
+
+  Node *Oper = parseOperatorName(/*NameState=*/nullptr);
+  if (Oper == nullptr)
+    return nullptr;
+  if (look() == 'I') {
+    Node *TA = parseTemplateArgs();
+    if (TA == nullptr)
+      return nullptr;
+    return make<NameWithTemplateArgs>(Oper, TA);
   }
-  return first;
+  return Oper;
 }
 
-// at <type>                                            # alignof (a type)
+// <unresolved-name>
+//  extension        ::= srN <unresolved-type> [<template-args>] <unresolved-qualifier-level>* E <base-unresolved-name>
+//                   ::= [gs] <base-unresolved-name>                     # x or (with "gs") ::x
+//                   ::= [gs] sr <unresolved-qualifier-level>+ E <base-unresolved-name>  
+//                                                                       # A::x, N::y, A<T>::z; "gs" means leading "::"
+//                   ::= sr <unresolved-type> <base-unresolved-name>     # T::x / decltype(p)::x
+//  extension        ::= sr <unresolved-type> <template-args> <base-unresolved-name>
+//                                                                       # T::N::x /decltype(p)::N::x
+//  (ignored)        ::= srN <unresolved-type>  <unresolved-qualifier-level>+ E <base-unresolved-name>
+//
+// <unresolved-qualifier-level> ::= <simple-id>
+Node *Db::parseUnresolvedName() {
+  Node *SoFar = nullptr;
+
+  // srN <unresolved-type> [<template-args>] <unresolved-qualifier-level>* E <base-unresolved-name>
+  // srN <unresolved-type>                   <unresolved-qualifier-level>+ E <base-unresolved-name>
+  if (consumeIf("srN")) {
+    SoFar = parseUnresolvedType();
+    if (SoFar == nullptr)
+      return nullptr;
+
+    if (look() == 'I') {
+      Node *TA = parseTemplateArgs();
+      if (TA == nullptr)
+        return nullptr;
+      SoFar = make<NameWithTemplateArgs>(SoFar, TA);
+    }
 
-template <class C>
-static const char *parse_alignof_type(const char *first, const char *last,
-                                      C &db) {
-  if (last - first >= 3 && first[0] == 'a' && first[1] == 't') {
-    const char *t = parse_type(first + 2, last, db);
-    if (t != first + 2) {
-      if (db.names.empty())
-        return first;
-      db.names.back().first = "alignof (" + db.names.back().move_full() + ")";
-      first = t;
+    while (!consumeIf('E')) {
+      Node *Qual = parseSimpleId();
+      if (Qual == nullptr)
+        return nullptr;
+      SoFar = make<QualifiedName>(SoFar, Qual);
     }
+
+    Node *Base = parseBaseUnresolvedName();
+    if (Base == nullptr)
+      return nullptr;
+    return make<QualifiedName>(SoFar, Base);
   }
-  return first;
-}
 
-// az <expression>                                            # alignof (a
-// expression)
+  bool Global = consumeIf("gs");
+
+  // [gs] <base-unresolved-name>                     # x or (with "gs") ::x
+  if (!consumeIf("sr")) {
+    SoFar = parseBaseUnresolvedName();
+    if (SoFar == nullptr)
+      return nullptr;
+    if (Global)
+      SoFar = make<GlobalQualifiedName>(SoFar);
+    return SoFar;
+  }
 
-template <class C>
-static const char *parse_alignof_expr(const char *first, const char *last,
-                                      C &db) {
-  if (last - first >= 3 && first[0] == 'a' && first[1] == 'z') {
-    const char *t = parse_expression(first + 2, last, db);
-    if (t != first + 2) {
-      if (db.names.empty())
-        return first;
-      db.names.back().first = "alignof (" + db.names.back().move_full() + ")";
-      first = t;
+  // [gs] sr <unresolved-qualifier-level>+ E   <base-unresolved-name>  
+  if (std::isdigit(look())) {
+    do {
+      Node *Qual = parseSimpleId();
+      if (Qual == nullptr)
+        return nullptr;
+      if (SoFar)
+        SoFar = make<QualifiedName>(SoFar, Qual);
+      else if (Global)
+        SoFar = make<GlobalQualifiedName>(Qual);
+      else
+        SoFar = Qual;
+    } while (!consumeIf('E'));
+  }
+  //      sr <unresolved-type>                 <base-unresolved-name>
+  //      sr <unresolved-type> <template-args> <base-unresolved-name>
+  else {
+    SoFar = parseUnresolvedType();
+    if (SoFar == nullptr)
+      return nullptr;
+
+    if (look() == 'I') {
+      Node *TA = parseTemplateArgs();
+      if (TA == nullptr)
+        return nullptr;
+      SoFar = make<NameWithTemplateArgs>(SoFar, TA);
     }
   }
-  return first;
+
+  assert(SoFar != nullptr);
+
+  Node *Base = parseBaseUnresolvedName();
+  if (Base == nullptr)
+    return nullptr;
+  return make<QualifiedName>(SoFar, Base);
 }
 
-template <class C>
-static const char *parse_noexcept_expression(const char *first,
-                                             const char *last, C &db) {
-  const char *t1 = parse_expression(first, last, db);
-  if (t1 != first) {
-    if (db.names.empty())
-      return first;
-    db.names.back().first = "noexcept (" + db.names.back().move_full() + ")";
-    first = t1;
-  }
-  return first;
+// <abi-tags> ::= <abi-tag> [<abi-tags>]
+// <abi-tag> ::= B <source-name>
+Node *Db::parseAbiTags(Node *N) {
+  while (consumeIf('B')) {
+    StringView SN = parseBareSourceName();
+    if (SN.empty())
+      return nullptr;
+    N = make<AbiTagAttr>(N, SN);
+  }
+  return N;
 }
 
-template <class C>
-static const char *parse_prefix_expression(const char *first, const char *last,
-                                           const std::string &op,
-                                           C &db) {
-  const char *t1 = parse_expression(first, last, db);
-  if (t1 != first) {
-    if (db.names.empty())
-      return first;
-    db.names.back().first = op + "(" + db.names.back().move_full() + ")";
-    first = t1;
-  }
-  return first;
+// <number> ::= [n] <non-negative decimal integer>
+StringView Db::parseNumber(bool AllowNegative) {
+  const char *Tmp = First;
+  if (AllowNegative)
+    consumeIf('n');
+  if (numLeft() == 0 || !std::isdigit(*First))
+    return StringView();
+  while (numLeft() != 0 && std::isdigit(*First))
+    ++First;
+  return StringView(Tmp, First);
 }
 
-template <class C>
-static const char *parse_binary_expression(const char *first, const char *last,
-                                           const std::string &op,
-                                           C &db) {
-  const char *t1 = parse_expression(first, last, db);
-  if (t1 != first) {
-    const char *t2 = parse_expression(t1, last, db);
-    if (t2 != t1) {
-      if (db.names.size() < 2)
-        return first;
-      auto op2 = db.names.back().move_full();
-      db.names.pop_back();
-      auto op1 = db.names.back().move_full();
-      auto &nm = db.names.back().first;
-      nm.clear();
-      if (op == ">")
-        nm += '(';
-      nm += "(" + op1 + ") " + op + " (" + op2 + ")";
-      if (op == ">")
-        nm += ')';
-      first = t2;
-    } else if (!db.names.empty())
-      db.names.pop_back();
-  }
-  return first;
+// <positive length number> ::= [0-9]*
+bool Db::parsePositiveInteger(size_t *Out) {
+  *Out = 0;
+  if (look() < '0' || look() > '9')
+    return true;
+  while (look() >= '0' && look() <= '9') {
+    *Out *= 10;
+    *Out += static_cast<size_t>(consume() - '0');
+  }
+  return false;
 }
 
-// <expression> ::= <unary operator-name> <expression>
-//              ::= <binary operator-name> <expression> <expression>
-//              ::= <ternary operator-name> <expression> <expression>
-//              <expression>
-//              ::= cl <expression>+ E                                   # call
-//              ::= cv <type> <expression>                               #
-//              conversion with one argument
-//              ::= cv <type> _ <expression>* E                          #
-//              conversion with a different number of arguments
-//              ::= [gs] nw <expression>* _ <type> E                     # new
-//              (expr-list) type
-//              ::= [gs] nw <expression>* _ <type> <initializer>         # new
-//              (expr-list) type (init)
-//              ::= [gs] na <expression>* _ <type> E                     # new[]
-//              (expr-list) type
-//              ::= [gs] na <expression>* _ <type> <initializer>         # new[]
-//              (expr-list) type (init)
-//              ::= [gs] dl <expression>                                 #
-//              delete expression
-//              ::= [gs] da <expression>                                 #
-//              delete[] expression
-//              ::= pp_ <expression>                                     #
-//              prefix ++
-//              ::= mm_ <expression>                                     #
-//              prefix --
-//              ::= ti <type>                                            #
-//              typeid (type)
-//              ::= te <expression>                                      #
-//              typeid (expression)
-//              ::= dc <type> <expression>                               #
-//              dynamic_cast<type> (expression)
-//              ::= sc <type> <expression>                               #
-//              static_cast<type> (expression)
-//              ::= cc <type> <expression>                               #
-//              const_cast<type> (expression)
-//              ::= rc <type> <expression>                               #
-//              reinterpret_cast<type> (expression)
-//              ::= st <type>                                            #
-//              sizeof (a type)
-//              ::= sz <expression>                                      #
-//              sizeof (an expression)
-//              ::= at <type>                                            #
-//              alignof (a type)
-//              ::= az <expression>                                      #
-//              alignof (an expression)
-//              ::= nx <expression>                                      #
-//              noexcept (expression)
-//              ::= <template-param>
-//              ::= <function-param>
-//              ::= dt <expression> <unresolved-name>                    #
-//              expr.name
-//              ::= pt <expression> <unresolved-name>                    #
-//              expr->name
-//              ::= ds <expression> <expression>                         #
-//              expr.*expr
-//              ::= sZ <template-param>                                  # size
-//              of a parameter pack
-//              ::= sZ <function-param>                                  # size
-//              of a function parameter pack
-//              ::= sp <expression>                                      # pack
-//              expansion
-//              ::= tw <expression>                                      # throw
-//              expression
-//              ::= tr                                                   # throw
-//              with no operand (rethrow)
-//              ::= <unresolved-name>                                    # f(p),
-//              N::f(p), ::f(p),
-//                                                                       #
-//                                                                       freestanding
-//                                                                       dependent
-//                                                                       name
-//                                                                       (e.g.,
-//                                                                       T::x),
-//                                                                       #
-//                                                                       objectless
-//                                                                       nonstatic
-//                                                                       member
-//                                                                       reference
-//              ::= <expr-primary>
+StringView Db::parseBareSourceName() {
+  size_t Int = 0;
+  if (parsePositiveInteger(&Int) || numLeft() < Int)
+    return StringView();
+  StringView R(First, First + Int);
+  First += Int;
+  return R;
+}
 
-template <class C>
-static const char *parse_expression(const char *first, const char *last,
-                                    C &db) {
-  if (last - first >= 2) {
-    const char *t = first;
-    bool parsed_gs = false;
-    if (last - first >= 4 && t[0] == 'g' && t[1] == 's') {
-      t += 2;
-      parsed_gs = true;
-    }
-    switch (*t) {
-    case 'L':
-      first = parse_expr_primary(first, last, db);
-      break;
-    case 'T':
-      first = parse_template_param(first, last, db);
+// <function-type> ::= [<CV-qualifiers>] [<exception-spec>] [Dx] F [Y] <bare-function-type> [<ref-qualifier>] E
+//
+// <exception-spec> ::= Do                # non-throwing exception-specification (e.g., noexcept, throw())
+//                  ::= DO <expression> E # computed (instantiation-dependent) noexcept
+//                  ::= Dw <type>+ E      # dynamic exception specification with instantiation-dependent types
+//
+// <ref-qualifier> ::= R                   # & ref-qualifier
+// <ref-qualifier> ::= O                   # && ref-qualifier
+Node *Db::parseFunctionType() {
+  Qualifiers CVQuals = parseCVQualifiers();
+
+  Node *ExceptionSpec = nullptr;
+  if (consumeIf("Do")) {
+    ExceptionSpec = make<NameType>("noexcept");
+  } else if (consumeIf("DO")) {
+    Node *E = parseExpr();
+    if (E == nullptr || !consumeIf('E'))
+      return nullptr;
+    ExceptionSpec = make<NoexceptSpec>(E);
+  } else if (consumeIf("Dw")) {
+    size_t SpecsBegin = Names.size();
+    while (!consumeIf('E')) {
+      Node *T = parseType();
+      if (T == nullptr)
+        return nullptr;
+      Names.push_back(T);
+    }
+    ExceptionSpec =
+      make<DynamicExceptionSpec>(popTrailingNodeArray(SpecsBegin));
+  }
+
+  consumeIf("Dx"); // transaction safe
+
+  if (!consumeIf('F'))
+    return nullptr;
+  consumeIf('Y'); // extern "C"
+  Node *ReturnType = parseType();
+  if (ReturnType == nullptr)
+    return nullptr;
+
+  FunctionRefQual ReferenceQualifier = FrefQualNone;
+  size_t ParamsBegin = Names.size();
+  while (true) {
+    if (consumeIf('E'))
       break;
-    case 'f':
-      first = parse_function_param(first, last, db);
+    if (consumeIf('v'))
+      continue;
+    if (consumeIf("RE")) {
+      ReferenceQualifier = FrefQualLValue;
       break;
-    case 'a':
-      switch (t[1]) {
-      case 'a':
-        t = parse_binary_expression(first + 2, last, "&&", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'd':
-        t = parse_prefix_expression(first + 2, last, "&", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'n':
-        t = parse_binary_expression(first + 2, last, "&", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'N':
-        t = parse_binary_expression(first + 2, last, "&=", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'S':
-        t = parse_binary_expression(first + 2, last, "=", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 't':
-        first = parse_alignof_type(first, last, db);
-        break;
-      case 'z':
-        first = parse_alignof_expr(first, last, db);
-        break;
-      }
+    }
+    if (consumeIf("OE")) {
+      ReferenceQualifier = FrefQualRValue;
       break;
-    case 'c':
-      switch (t[1]) {
-      case 'c':
-        first = parse_const_cast_expr(first, last, db);
-        break;
-      case 'l':
-        first = parse_call_expr(first, last, db);
-        break;
-      case 'm':
-        t = parse_binary_expression(first + 2, last, ",", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'o':
-        t = parse_prefix_expression(first + 2, last, "~", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'v':
-        first = parse_conversion_expr(first, last, db);
-        break;
+    }
+    Node *T = parseType();
+    if (T == nullptr)
+      return nullptr;
+    Names.push_back(T);
+  }
+
+  NodeArray Params = popTrailingNodeArray(ParamsBegin);
+  return make<FunctionType>(ReturnType, Params, CVQuals,
+                            ReferenceQualifier, ExceptionSpec);
+}
+
+// extension:
+// <vector-type>           ::= Dv <positive dimension number> _ <extended element type>
+//                         ::= Dv [<dimension expression>] _ <element type>
+// <extended element type> ::= <element type>
+//                         ::= p # AltiVec vector pixel
+Node *Db::parseVectorType() {
+  if (!consumeIf("Dv"))
+    return nullptr;
+  if (look() >= '1' && look() <= '9') {
+    StringView DimensionNumber = parseNumber();
+    if (!consumeIf('_'))
+      return nullptr;
+    if (consumeIf('p'))
+      return make<VectorType>(DimensionNumber);
+    Node *ElemType = parseType();
+    if (ElemType == nullptr)
+      return nullptr;
+    return make<VectorType>(ElemType, DimensionNumber);
+  }
+
+  if (!consumeIf('_')) {
+    Node *DimExpr = parseExpr();
+    if (!DimExpr)
+      return nullptr;
+    if (!consumeIf('_'))
+      return nullptr;
+    Node *ElemType = parseType();
+    if (!ElemType)
+      return nullptr;
+    return make<VectorType>(ElemType, DimExpr);
+  }
+  Node *ElemType = parseType();
+  if (!ElemType)
+    return nullptr;
+  return make<VectorType>(ElemType, StringView());
+}
+
+// <decltype>  ::= Dt <expression> E  # decltype of an id-expression or class member access (C++0x)
+//             ::= DT <expression> E  # decltype of an expression (C++0x)
+Node *Db::parseDecltype() {
+  if (!consumeIf('D'))
+    return nullptr;
+  if (!consumeIf('t') && !consumeIf('T'))
+    return nullptr;
+  Node *E = parseExpr();
+  if (E == nullptr)
+    return nullptr;
+  if (!consumeIf('E'))
+    return nullptr;
+  return make<EnclosingExpr>("decltype(", E, ")");
+}
+
+// <array-type> ::= A <positive dimension number> _ <element type>
+//              ::= A [<dimension expression>] _ <element type>
+Node *Db::parseArrayType() {
+  if (!consumeIf('A'))
+    return nullptr;
+
+  if (std::isdigit(look())) {
+    StringView Dimension = parseNumber();
+    if (!consumeIf('_'))
+      return nullptr;
+    Node *Ty = parseType();
+    if (Ty == nullptr)
+      return nullptr;
+    return make<ArrayType>(Ty, Dimension);
+  }
+
+  if (!consumeIf('_')) {
+    Node *DimExpr = parseExpr();
+    if (DimExpr == nullptr)
+      return nullptr;
+    if (!consumeIf('_'))
+      return nullptr;
+    Node *ElementType = parseType();
+    if (ElementType == nullptr)
+      return nullptr;
+    return make<ArrayType>(ElementType, DimExpr);
+  }
+
+  Node *Ty = parseType();
+  if (Ty == nullptr)
+    return nullptr;
+  return make<ArrayType>(Ty);
+}
+
+// <pointer-to-member-type> ::= M <class type> <member type>
+Node *Db::parsePointerToMemberType() {
+  if (!consumeIf('M'))
+    return nullptr;
+  Node *ClassType = parseType();
+  if (ClassType == nullptr)
+    return nullptr;
+  Node *MemberType = parseType();
+  if (MemberType == nullptr)
+    return nullptr;
+  return make<PointerToMemberType>(ClassType, MemberType);
+}
+
+// <class-enum-type> ::= <name>     # non-dependent type name, dependent type name, or dependent typename-specifier
+//                   ::= Ts <name>  # dependent elaborated type specifier using 'struct' or 'class'
+//                   ::= Tu <name>  # dependent elaborated type specifier using 'union'
+//                   ::= Te <name>  # dependent elaborated type specifier using 'enum'
+Node *Db::parseClassEnumType() {
+  StringView ElabSpef;
+  if (consumeIf("Ts"))
+    ElabSpef = "struct";
+  else if (consumeIf("Tu"))
+    ElabSpef = "union";
+  else if (consumeIf("Te"))
+    ElabSpef = "enum";
+
+  Node *Name = parseName();
+  if (Name == nullptr)
+    return nullptr;
+
+  if (!ElabSpef.empty())
+    return make<ElaboratedTypeSpefType>(ElabSpef, Name);
+
+  return Name;
+}
+
+// <qualified-type>     ::= <qualifiers> <type>
+// <qualifiers> ::= <extended-qualifier>* <CV-qualifiers>
+// <extended-qualifier> ::= U <source-name> [<template-args>] # vendor extended type qualifier
+Node *Db::parseQualifiedType() {
+  if (consumeIf('U')) {
+    StringView Qual = parseBareSourceName();
+    if (Qual.empty())
+      return nullptr;
+
+    // FIXME parse the optional <template-args> here!
+
+    // extension            ::= U <objc-name> <objc-type>  # objc-type<identifier>
+    if (Qual.startsWith("objcproto")) {
+      StringView ProtoSourceName = Qual.dropFront(std::strlen("objcproto"));
+      StringView Proto;
+      {
+        SwapAndRestore<const char *> SaveFirst(First, ProtoSourceName.begin()),
+                                     SaveLast(Last, ProtoSourceName.end());
+        Proto = parseBareSourceName();
       }
+      if (Proto.empty())
+        return nullptr;
+      Node *Child = parseQualifiedType();
+      if (Child == nullptr)
+        return nullptr;
+      return make<ObjCProtoName>(Child, Proto);
+    }
+
+    Node *Child = parseQualifiedType();
+    if (Child == nullptr)
+      return nullptr;
+    return make<VendorExtQualType>(Child, Qual);
+  }
+
+  Qualifiers Quals = parseCVQualifiers();
+  Node *Ty = parseType();
+  if (Ty == nullptr)
+    return nullptr;
+  if (Quals != QualNone)
+    Ty = make<QualType>(Ty, Quals);
+  return Ty;
+}
+
+// <type>      ::= <builtin-type>
+//             ::= <qualified-type>
+//             ::= <function-type>
+//             ::= <class-enum-type>
+//             ::= <array-type>
+//             ::= <pointer-to-member-type>
+//             ::= <template-param>
+//             ::= <template-template-param> <template-args>
+//             ::= <decltype>
+//             ::= P <type>        # pointer
+//             ::= R <type>        # l-value reference
+//             ::= O <type>        # r-value reference (C++11)
+//             ::= C <type>        # complex pair (C99)
+//             ::= G <type>        # imaginary (C99)
+//             ::= <substitution>  # See Compression below
+// extension   ::= U <objc-name> <objc-type>  # objc-type<identifier>
+// extension   ::= <vector-type> # <vector-type> starts with Dv
+//
+// <objc-name> ::= <k0 number> objcproto <k1 number> <identifier>  # k0 = 9 + <number of digits in k1> + k1
+// <objc-type> ::= <source-name>  # PU<11+>objcproto 11objc_object<source-name> 11objc_object -> id<source-name>
+Node *Db::parseType() {
+  Node *Result = nullptr;
+
+  switch (look()) {
+  //             ::= <qualified-type>
+  case 'r':
+  case 'V':
+  case 'K': {
+    unsigned AfterQuals = 0;
+    if (look(AfterQuals) == 'r') ++AfterQuals;
+    if (look(AfterQuals) == 'V') ++AfterQuals;
+    if (look(AfterQuals) == 'K') ++AfterQuals;
+
+    if (look(AfterQuals) == 'F' ||
+        (look(AfterQuals) == 'D' &&
+         (look(AfterQuals + 1) == 'o' || look(AfterQuals + 1) == 'O' ||
+          look(AfterQuals + 1) == 'w' || look(AfterQuals + 1) == 'x'))) {
+      Result = parseFunctionType();
       break;
+    }
+    LLVM_FALLTHROUGH;
+  }
+  case 'U': {
+    Result = parseQualifiedType();
+    break;
+  }
+  // <builtin-type> ::= v    # void
+  case 'v':
+    ++First;
+    return make<NameType>("void");
+  //                ::= w    # wchar_t
+  case 'w':
+    ++First;
+    return make<NameType>("wchar_t");
+  //                ::= b    # bool
+  case 'b':
+    ++First;
+    return make<NameType>("bool");
+  //                ::= c    # char
+  case 'c':
+    ++First;
+    return make<NameType>("char");
+  //                ::= a    # signed char
+  case 'a':
+    ++First;
+    return make<NameType>("signed char");
+  //                ::= h    # unsigned char
+  case 'h':
+    ++First;
+    return make<NameType>("unsigned char");
+  //                ::= s    # short
+  case 's':
+    ++First;
+    return make<NameType>("short");
+  //                ::= t    # unsigned short
+  case 't':
+    ++First;
+    return make<NameType>("unsigned short");
+  //                ::= i    # int
+  case 'i':
+    ++First;
+    return make<NameType>("int");
+  //                ::= j    # unsigned int
+  case 'j':
+    ++First;
+    return make<NameType>("unsigned int");
+  //                ::= l    # long
+  case 'l':
+    ++First;
+    return make<NameType>("long");
+  //                ::= m    # unsigned long
+  case 'm':
+    ++First;
+    return make<NameType>("unsigned long");
+  //                ::= x    # long long, __int64
+  case 'x':
+    ++First;
+    return make<NameType>("long long");
+  //                ::= y    # unsigned long long, __int64
+  case 'y':
+    ++First;
+    return make<NameType>("unsigned long long");
+  //                ::= n    # __int128
+  case 'n':
+    ++First;
+    return make<NameType>("__int128");
+  //                ::= o    # unsigned __int128
+  case 'o':
+    ++First;
+    return make<NameType>("unsigned __int128");
+  //                ::= f    # float
+  case 'f':
+    ++First;
+    return make<NameType>("float");
+  //                ::= d    # double
+  case 'd':
+    ++First;
+    return make<NameType>("double");
+  //                ::= e    # long double, __float80
+  case 'e':
+    ++First;
+    return make<NameType>("long double");
+  //                ::= g    # __float128
+  case 'g':
+    ++First;
+    return make<NameType>("__float128");
+  //                ::= z    # ellipsis
+  case 'z':
+    ++First;
+    return make<NameType>("...");
+
+  // <builtin-type> ::= u <source-name>    # vendor extended type
+  case 'u': {
+    ++First;
+    StringView Res = parseBareSourceName();
+    if (Res.empty())
+      return nullptr;
+    return make<NameType>(Res);
+  }
+  case 'D':
+    switch (look(1)) {
+    //                ::= Dd   # IEEE 754r decimal floating point (64 bits)
     case 'd':
-      switch (t[1]) {
-      case 'a': {
-        const char *t1 = parse_expression(t + 2, last, db);
-        if (t1 != t + 2) {
-          if (db.names.empty())
-            return first;
-          db.names.back().first =
-              (parsed_gs ? std::string("::") : std::string()) + "delete[] " +
-              db.names.back().move_full();
-          first = t1;
-        }
-      } break;
-      case 'c':
-        first = parse_dynamic_cast_expr(first, last, db);
-        break;
-      case 'e':
-        t = parse_prefix_expression(first + 2, last, "*", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'l': {
-        const char *t1 = parse_expression(t + 2, last, db);
-        if (t1 != t + 2) {
-          if (db.names.empty())
-            return first;
-          db.names.back().first =
-              (parsed_gs ? std::string("::") : std::string()) + "delete " +
-              db.names.back().move_full();
-          first = t1;
-        }
-      } break;
-      case 'n':
-        return parse_unresolved_name(first, last, db);
-      case 's':
-        first = parse_dot_star_expr(first, last, db);
-        break;
-      case 't':
-        first = parse_dot_expr(first, last, db);
-        break;
-      case 'v':
-        t = parse_binary_expression(first + 2, last, "/", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'V':
-        t = parse_binary_expression(first + 2, last, "/=", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      }
-      break;
+      First += 2;
+      return make<NameType>("decimal64");
+    //                ::= De   # IEEE 754r decimal floating point (128 bits)
     case 'e':
-      switch (t[1]) {
-      case 'o':
-        t = parse_binary_expression(first + 2, last, "^", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'O':
-        t = parse_binary_expression(first + 2, last, "^=", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'q':
-        t = parse_binary_expression(first + 2, last, "==", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      }
-      break;
-    case 'g':
-      switch (t[1]) {
-      case 'e':
-        t = parse_binary_expression(first + 2, last, ">=", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 't':
-        t = parse_binary_expression(first + 2, last, ">", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      }
-      break;
+      First += 2;
+      return make<NameType>("decimal128");
+    //                ::= Df   # IEEE 754r decimal floating point (32 bits)
+    case 'f':
+      First += 2;
+      return make<NameType>("decimal32");
+    //                ::= Dh   # IEEE 754r half-precision floating point (16 bits)
+    case 'h':
+      First += 2;
+      return make<NameType>("decimal16");
+    //                ::= Di   # char32_t
     case 'i':
-      if (t[1] == 'x') {
-        const char *t1 = parse_expression(first + 2, last, db);
-        if (t1 != first + 2) {
-          const char *t2 = parse_expression(t1, last, db);
-          if (t2 != t1) {
-            if (db.names.size() < 2)
-              return first;
-            auto op2 = db.names.back().move_full();
-            db.names.pop_back();
-            auto op1 = db.names.back().move_full();
-            db.names.back() = "(" + op1 + ")[" + op2 + "]";
-            first = t2;
-          } else if (!db.names.empty())
-            db.names.pop_back();
-        }
-      }
-      break;
-    case 'l':
-      switch (t[1]) {
-      case 'e':
-        t = parse_binary_expression(first + 2, last, "<=", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 's':
-        t = parse_binary_expression(first + 2, last, "<<", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'S':
-        t = parse_binary_expression(first + 2, last, "<<=", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 't':
-        t = parse_binary_expression(first + 2, last, "<", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      }
-      break;
-    case 'm':
-      switch (t[1]) {
-      case 'i':
-        t = parse_binary_expression(first + 2, last, "-", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'I':
-        t = parse_binary_expression(first + 2, last, "-=", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'l':
-        t = parse_binary_expression(first + 2, last, "*", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'L':
-        t = parse_binary_expression(first + 2, last, "*=", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'm':
-        if (first + 2 != last && first[2] == '_') {
-          t = parse_prefix_expression(first + 3, last, "--", db);
-          if (t != first + 3)
-            first = t;
-        } else {
-          const char *t1 = parse_expression(first + 2, last, db);
-          if (t1 != first + 2) {
-            if (db.names.empty())
-              return first;
-            db.names.back() = "(" + db.names.back().move_full() + ")--";
-            first = t1;
-          }
-        }
-        break;
-      }
-      break;
+      First += 2;
+      return make<NameType>("char32_t");
+    //                ::= Ds   # char16_t
+    case 's':
+      First += 2;
+      return make<NameType>("char16_t");
+    //                ::= Da   # auto (in dependent new-expressions)
+    case 'a':
+      First += 2;
+      return make<NameType>("auto");
+    //                ::= Dc   # decltype(auto)
+    case 'c':
+      First += 2;
+      return make<NameType>("decltype(auto)");
+    //                ::= Dn   # std::nullptr_t (i.e., decltype(nullptr))
     case 'n':
-      switch (t[1]) {
-      case 'a':
-      case 'w':
-        first = parse_new_expr(first, last, db);
-        break;
-      case 'e':
-        t = parse_binary_expression(first + 2, last, "!=", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'g':
-        t = parse_prefix_expression(first + 2, last, "-", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 't':
-        t = parse_prefix_expression(first + 2, last, "!", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'x':
-        t = parse_noexcept_expression(first + 2, last, db);
-        if (t != first + 2)
-          first = t;
-        break;
-      }
-      break;
-    case 'o':
-      switch (t[1]) {
-      case 'n':
-        return parse_unresolved_name(first, last, db);
-      case 'o':
-        t = parse_binary_expression(first + 2, last, "||", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'r':
-        t = parse_binary_expression(first + 2, last, "|", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'R':
-        t = parse_binary_expression(first + 2, last, "|=", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      }
+      First += 2;
+      return make<NameType>("std::nullptr_t");
+
+    //             ::= <decltype>
+    case 't':
+    case 'T': {
+      Result = parseDecltype();
       break;
-    case 'p':
-      switch (t[1]) {
-      case 'm':
-        t = parse_binary_expression(first + 2, last, "->*", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'l':
-        t = parse_binary_expression(first + 2, last, "+", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'L':
-        t = parse_binary_expression(first + 2, last, "+=", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'p':
-        if (first + 2 != last && first[2] == '_') {
-          t = parse_prefix_expression(first + 3, last, "++", db);
-          if (t != first + 3)
-            first = t;
-        } else {
-          const char *t1 = parse_expression(first + 2, last, db);
-          if (t1 != first + 2) {
-            if (db.names.empty())
-              return first;
-            db.names.back() = "(" + db.names.back().move_full() + ")++";
-            first = t1;
-          }
-        }
-        break;
-      case 's':
-        t = parse_prefix_expression(first + 2, last, "+", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 't':
-        first = parse_arrow_expr(first, last, db);
-        break;
-      }
+    }
+    // extension   ::= <vector-type> # <vector-type> starts with Dv
+    case 'v': {
+      Result = parseVectorType();
       break;
-    case 'q':
-      if (t[1] == 'u') {
-        const char *t1 = parse_expression(first + 2, last, db);
-        if (t1 != first + 2) {
-          const char *t2 = parse_expression(t1, last, db);
-          if (t2 != t1) {
-            const char *t3 = parse_expression(t2, last, db);
-            if (t3 != t2) {
-              if (db.names.size() < 3)
-                return first;
-              auto op3 = db.names.back().move_full();
-              db.names.pop_back();
-              auto op2 = db.names.back().move_full();
-              db.names.pop_back();
-              auto op1 = db.names.back().move_full();
-              db.names.back() = "(" + op1 + ") ? (" + op2 + ") : (" + op3 + ")";
-              first = t3;
-            } else {
-              if (db.names.size() < 2)
-                return first;
-              db.names.pop_back();
-              db.names.pop_back();
-            }
-          } else if (!db.names.empty())
-            db.names.pop_back();
-        }
-      }
+    }
+    //           ::= Dp <type>       # pack expansion (C++0x)
+    case 'p': {
+      First += 2;
+      Node *Child = parseType();
+      if (!Child)
+        return nullptr;
+      Result = make<ParameterPackExpansion>(Child);
       break;
-    case 'r':
-      switch (t[1]) {
-      case 'c':
-        first = parse_reinterpret_cast_expr(first, last, db);
-        break;
-      case 'm':
-        t = parse_binary_expression(first + 2, last, "%", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'M':
-        t = parse_binary_expression(first + 2, last, "%=", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 's':
-        t = parse_binary_expression(first + 2, last, ">>", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      case 'S':
-        t = parse_binary_expression(first + 2, last, ">>=", db);
-        if (t != first + 2)
-          first = t;
-        break;
-      }
+    }
+    // Exception specifier on a function type.
+    case 'o':
+    case 'O':
+    case 'w':
+    // Transaction safe function type.
+    case 'x':
+      Result = parseFunctionType();
       break;
-    case 's':
-      switch (t[1]) {
-      case 'c':
-        first = parse_static_cast_expr(first, last, db);
-        break;
-      case 'p':
-        first = parse_pack_expansion(first, last, db);
-        break;
-      case 'r':
-        return parse_unresolved_name(first, last, db);
-      case 't':
-        first = parse_sizeof_type_expr(first, last, db);
-        break;
-      case 'z':
-        first = parse_sizeof_expr_expr(first, last, db);
-        break;
-      case 'Z':
-        if (last - t >= 3) {
-          switch (t[2]) {
-          case 'T':
-            first = parse_sizeof_param_pack_expr(first, last, db);
-            break;
-          case 'f':
-            first = parse_sizeof_function_param_pack_expr(first, last, db);
-            break;
-          }
-        }
-        break;
-      }
+    }
+    break;
+  //             ::= <function-type>
+  case 'F': {
+    Result = parseFunctionType();
+    break;
+  }
+  //             ::= <array-type>
+  case 'A': {
+    Result = parseArrayType();
+    break;
+  }
+  //             ::= <pointer-to-member-type>
+  case 'M': {
+    Result = parsePointerToMemberType();
+    break;
+  }
+  //             ::= <template-param>
+  case 'T': {
+    // This could be an elaborate type specifier on a <class-enum-type>.
+    if (look(1) == 's' || look(1) == 'u' || look(1) == 'e') {
+      Result = parseClassEnumType();
       break;
-    case 't':
-      switch (t[1]) {
-      case 'e':
-      case 'i':
-        first = parse_typeid_expr(first, last, db);
-        break;
-      case 'r':
-        db.names.push_back("throw");
-        first += 2;
-        break;
-      case 'w':
-        first = parse_throw_expr(first, last, db);
+    }
+
+    Result = parseTemplateParam();
+    if (Result == nullptr)
+      return nullptr;
+
+    // Result could be either of:
+    //   <type>        ::= <template-param>
+    //   <type>        ::= <template-template-param> <template-args>
+    //
+    //   <template-template-param> ::= <template-param>
+    //                             ::= <substitution>
+    //
+    // If this is followed by some <template-args>, and we're permitted to
+    // parse them, take the second production.
+
+    if (TryToParseTemplateArgs && look() == 'I') {
+      Node *TA = parseTemplateArgs();
+      if (TA == nullptr)
+        return nullptr;
+      Result = make<NameWithTemplateArgs>(Result, TA);
+    }
+    break;
+  }
+  //             ::= P <type>        # pointer
+  case 'P': {
+    ++First;
+    Node *Ptr = parseType();
+    if (Ptr == nullptr)
+      return nullptr;
+    Result = make<PointerType>(Ptr);
+    break;
+  }
+  //             ::= R <type>        # l-value reference
+  case 'R': {
+    ++First;
+    Node *Ref = parseType();
+    if (Ref == nullptr)
+      return nullptr;
+    Result = make<LValueReferenceType>(Ref);
+    break;
+  }
+  //             ::= O <type>        # r-value reference (C++11)
+  case 'O': {
+    ++First;
+    Node *Ref = parseType();
+    if (Ref == nullptr)
+      return nullptr;
+    Result = make<RValueReferenceType>(Ref);
+    break;
+  }
+  //             ::= C <type>        # complex pair (C99)
+  case 'C': {
+    ++First;
+    Node *P = parseType();
+    if (P == nullptr)
+      return nullptr;
+    Result = make<PostfixQualifiedType>(P, " complex");
+    break;
+  }
+  //             ::= G <type>        # imaginary (C99)
+  case 'G': {
+    ++First;
+    Node *P = parseType();
+    if (P == nullptr)
+      return P;
+    Result = make<PostfixQualifiedType>(P, " imaginary");
+    break;
+  }
+  //             ::= <substitution>  # See Compression below
+  case 'S': {
+    if (look(1) && look(1) != 't') {
+      Node *Sub = parseSubstitution();
+      if (Sub == nullptr)
+        return nullptr;
+
+      // Sub could be either of:
+      //   <type>        ::= <substitution>
+      //   <type>        ::= <template-template-param> <template-args>
+      //
+      //   <template-template-param> ::= <template-param>
+      //                             ::= <substitution>
+      //
+      // If this is followed by some <template-args>, and we're permitted to
+      // parse them, take the second production.
+
+      if (TryToParseTemplateArgs && look() == 'I') {
+        Node *TA = parseTemplateArgs();
+        if (TA == nullptr)
+          return nullptr;
+        Result = make<NameWithTemplateArgs>(Sub, TA);
         break;
       }
-      break;
-    case '1':
-    case '2':
-    case '3':
-    case '4':
-    case '5':
-    case '6':
-    case '7':
-    case '8':
-    case '9':
-      return parse_unresolved_name(first, last, db);
-    }
-  }
-  return first;
-}
 
-// <template-arg> ::= <type>                                             # type
-// or template
-//                ::= X <expression> E                                   #
-//                expression
-//                ::= <expr-primary>                                     #
-//                simple expressions
-//                ::= J <template-arg>* E                                #
-//                argument pack
-//                ::= LZ <encoding> E                                    #
-//                extension
-
-template <class C>
-static const char *parse_template_arg(const char *first, const char *last,
-                                      C &db) {
-  if (first != last) {
-    const char *t;
-    switch (*first) {
-    case 'X':
-      t = parse_expression(first + 1, last, db);
-      if (t != first + 1) {
-        if (t != last && *t == 'E')
-          first = t + 1;
-      }
-      break;
-    case 'J':
-      t = first + 1;
-      if (t == last)
-        return first;
-      while (*t != 'E') {
-        const char *t1 = parse_template_arg(t, last, db);
-        if (t1 == t)
-          return first;
-        t = t1;
-      }
-      first = t + 1;
-      break;
-    case 'L':
-      // <expr-primary> or LZ <encoding> E
-      if (first + 1 != last && first[1] == 'Z') {
-        t = parse_encoding(first + 2, last, db);
-        if (t != first + 2 && t != last && *t == 'E')
-          first = t + 1;
-      } else
-        first = parse_expr_primary(first, last, db);
-      break;
-    default:
-      // <type>
-      first = parse_type(first, last, db);
-      break;
+      // If all we parsed was a substitution, don't re-insert into the
+      // substitution table.
+      return Sub;
     }
+    LLVM_FALLTHROUGH;
+  }
+  //        ::= <class-enum-type>
+  default: {
+    Result = parseClassEnumType();
+    break;
   }
-  return first;
+  }
+
+  // If we parsed a type, insert it into the substitution table. Note that all
+  // <builtin-type>s and <substitution>s have already bailed out, because they
+  // don't get substitutions.
+  if (Result != nullptr)
+    Subs.push_back(Result);
+  return Result;
 }
 
-// <template-args> ::= I <template-arg>* E
-//     extension, the abi says <template-arg>+
+Node *Db::parsePrefixExpr(StringView Kind) {
+  Node *E = parseExpr();
+  if (E == nullptr)
+    return nullptr;
+  return make<PrefixExpr>(Kind, E);
+}
 
-template <class C>
-static const char *parse_template_args(const char *first, const char *last,
-                                       C &db) {
-  if (last - first >= 2 && *first == 'I') {
-    if (db.tag_templates)
-      db.template_param.back().clear();
-    const char *t = first + 1;
-    std::string args("<");
-    while (*t != 'E') {
-      if (db.tag_templates)
-        db.template_param.emplace_back();
-      size_t k0 = db.names.size();
-      const char *t1 = parse_template_arg(t, last, db);
-      size_t k1 = db.names.size();
-      if (db.tag_templates)
-        db.template_param.pop_back();
-      if (t1 == t || t1 == last)
-        return first;
-      if (db.tag_templates) {
-        db.template_param.back().emplace_back();
-        for (size_t k = k0; k < k1; ++k)
-          db.template_param.back().back().push_back(db.names[k]);
-      }
-      for (size_t k = k0; k < k1; ++k) {
-        if (args.size() > 1)
-          args += ", ";
-        args += db.names[k].move_full();
-      }
-      for (; k1 > k0; --k1)
-        if (!db.names.empty())
-          db.names.pop_back();
-      t = t1;
-    }
-    first = t + 1;
-    if (args.back() != '>')
-      args += ">";
-    else
-      args += " >";
-    db.names.push_back(std::move(args));
-  }
-  return first;
+Node *Db::parseBinaryExpr(StringView Kind) {
+  Node *LHS = parseExpr();
+  if (LHS == nullptr)
+    return nullptr;
+  Node *RHS = parseExpr();
+  if (RHS == nullptr)
+    return nullptr;
+  return make<BinaryExpr>(LHS, Kind, RHS);
 }
 
-// <nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix>
-// <unqualified-name> E
-//               ::= N [<CV-qualifiers>] [<ref-qualifier>] <template-prefix>
-//               <template-args> E
-//
-// <prefix> ::= <prefix> <unqualified-name>
-//          ::= <template-prefix> <template-args>
-//          ::= <template-param>
-//          ::= <decltype>
-//          ::= # empty
-//          ::= <substitution>
-//          ::= <prefix> <data-member-prefix>
-//  extension ::= L
-//
-// <template-prefix> ::= <prefix> <template unqualified-name>
-//                   ::= <template-param>
-//                   ::= <substitution>
+Node *Db::parseIntegerLiteral(StringView Lit) {
+  StringView Tmp = parseNumber(true);
+  if (!Tmp.empty() && consumeIf('E'))
+    return make<IntegerExpr>(Lit, Tmp);
+  return nullptr;
+}
 
-template <class C>
-static const char *parse_nested_name(const char *first, const char *last, C &db,
-                                     bool *ends_with_template_args) {
-  if (first != last && *first == 'N') {
-    unsigned cv;
-    const char *t0 = parse_cv_qualifiers(first + 1, last, cv);
-    if (t0 == last)
-      return first;
-    db.ref = 0;
-    if (*t0 == 'R') {
-      db.ref = 1;
-      ++t0;
-    } else if (*t0 == 'O') {
-      db.ref = 2;
-      ++t0;
-    }
-    db.names.emplace_back();
-    if (last - t0 >= 2 && t0[0] == 'S' && t0[1] == 't') {
-      t0 += 2;
-      db.names.back().first = "std";
-    }
-    if (t0 == last) {
-      db.names.pop_back();
-      return first;
-    }
-    bool pop_subs = false;
-    bool component_ends_with_template_args = false;
-    while (*t0 != 'E') {
-      component_ends_with_template_args = false;
-      const char *t1;
-      switch (*t0) {
-      case 'S':
-        if (t0 + 1 != last && t0[1] == 't')
-          goto do_parse_unqualified_name;
-        t1 = parse_substitution(t0, last, db);
-        if (t1 != t0 && t1 != last) {
-          auto name = db.names.back().move_full();
-          db.names.pop_back();
-          if (db.names.empty())
-            return first;
-          if (!db.names.back().first.empty()) {
-            db.names.back().first += "::" + name;
-            db.subs.push_back(typename C::sub_type(1, db.names.back()));
-          } else
-            db.names.back().first = name;
-          pop_subs = true;
-          t0 = t1;
-        } else
-          return first;
-        break;
-      case 'T':
-        t1 = parse_template_param(t0, last, db);
-        if (t1 != t0 && t1 != last) {
-          auto name = db.names.back().move_full();
-          db.names.pop_back();
-          if (db.names.empty())
-            return first;
-          if (!db.names.back().first.empty())
-            db.names.back().first += "::" + name;
-          else
-            db.names.back().first = name;
-          db.subs.push_back(typename C::sub_type(1, db.names.back()));
-          pop_subs = true;
-          t0 = t1;
-        } else
-          return first;
-        break;
-      case 'D':
-        if (t0 + 1 != last && t0[1] != 't' && t0[1] != 'T')
-          goto do_parse_unqualified_name;
-        t1 = parse_decltype(t0, last, db);
-        if (t1 != t0 && t1 != last) {
-          auto name = db.names.back().move_full();
-          db.names.pop_back();
-          if (db.names.empty())
-            return first;
-          if (!db.names.back().first.empty())
-            db.names.back().first += "::" + name;
-          else
-            db.names.back().first = name;
-          db.subs.push_back(typename C::sub_type(1, db.names.back()));
-          pop_subs = true;
-          t0 = t1;
-        } else
-          return first;
-        break;
-      case 'I':
-        t1 = parse_template_args(t0, last, db);
-        if (t1 != t0 && t1 != last) {
-          auto name = db.names.back().move_full();
-          db.names.pop_back();
-          if (db.names.empty())
-            return first;
-          db.names.back().first += name;
-          db.subs.push_back(typename C::sub_type(1, db.names.back()));
-          t0 = t1;
-          component_ends_with_template_args = true;
-        } else
-          return first;
-        break;
-      case 'L':
-        if (++t0 == last)
-          return first;
-        break;
-      default:
-      do_parse_unqualified_name:
-        t1 = parse_unqualified_name(t0, last, db);
-        if (t1 != t0 && t1 != last) {
-          auto name = db.names.back().move_full();
-          db.names.pop_back();
-          if (db.names.empty())
-            return first;
-          if (!db.names.back().first.empty())
-            db.names.back().first += "::" + name;
-          else
-            db.names.back().first = name;
-          db.subs.push_back(typename C::sub_type(1, db.names.back()));
-          pop_subs = true;
-          t0 = t1;
-        } else
-          return first;
-      }
-    }
-    first = t0 + 1;
-    db.cv = cv;
-    if (pop_subs && !db.subs.empty())
-      db.subs.pop_back();
-    if (ends_with_template_args)
-      *ends_with_template_args = component_ends_with_template_args;
+// <CV-Qualifiers> ::= [r] [V] [K]
+Qualifiers Db::parseCVQualifiers() {
+  Qualifiers CVR = QualNone;
+  if (consumeIf('r'))
+    addQualifiers(CVR, QualRestrict);
+  if (consumeIf('V'))
+    addQualifiers(CVR, QualVolatile);
+  if (consumeIf('K'))
+    addQualifiers(CVR, QualConst);
+  return CVR;
+}
+
+// <function-param> ::= fp <top-level CV-Qualifiers> _                                     # L == 0, first parameter
+//                  ::= fp <top-level CV-Qualifiers> <parameter-2 non-negative number> _   # L == 0, second and later parameters
+//                  ::= fL <L-1 non-negative number> p <top-level CV-Qualifiers> _         # L > 0, first parameter
+//                  ::= fL <L-1 non-negative number> p <top-level CV-Qualifiers> <parameter-2 non-negative number> _   # L > 0, second and later parameters
+Node *Db::parseFunctionParam() {
+  if (consumeIf("fp")) {
+    parseCVQualifiers();
+    StringView Num = parseNumber();
+    if (!consumeIf('_'))
+      return nullptr;
+    return make<FunctionParam>(Num);
+  }
+  if (consumeIf("fL")) {
+    if (parseNumber().empty())
+      return nullptr;
+    if (!consumeIf('p'))
+      return nullptr;
+    parseCVQualifiers();
+    StringView Num = parseNumber();
+    if (!consumeIf('_'))
+      return nullptr;
+    return make<FunctionParam>(Num);
   }
-  return first;
+  return nullptr;
 }
 
-// <discriminator> := _ <non-negative number>      # when number < 10
-//                 := __ <non-negative number> _   # when number >= 10
-//  extension      := decimal-digit+               # at the end of string
+// [gs] nw <expression>* _ <type> E                     # new (expr-list) type
+// [gs] nw <expression>* _ <type> <initializer>         # new (expr-list) type (init)
+// [gs] na <expression>* _ <type> E                     # new[] (expr-list) type
+// [gs] na <expression>* _ <type> <initializer>         # new[] (expr-list) type (init)
+// <initializer> ::= pi <expression>* E                 # parenthesized initialization
+Node *Db::parseNewExpr() {
+  bool Global = consumeIf("gs");
+  bool IsArray = look(1) == 'a';
+  if (!consumeIf("nw") && !consumeIf("na"))
+    return nullptr;
+  size_t Exprs = Names.size();
+  while (!consumeIf('_')) {
+    Node *Ex = parseExpr();
+    if (Ex == nullptr)
+      return nullptr;
+    Names.push_back(Ex);
+  }
+  NodeArray ExprList = popTrailingNodeArray(Exprs);
+  Node *Ty = parseType();
+  if (Ty == nullptr)
+    return Ty;
+  if (consumeIf("pi")) {
+    size_t InitsBegin = Names.size();
+    while (!consumeIf('E')) {
+      Node *Init = parseExpr();
+      if (Init == nullptr)
+        return Init;
+      Names.push_back(Init);
+    }
+    NodeArray Inits = popTrailingNodeArray(InitsBegin);
+    return make<NewExpr>(ExprList, Ty, Inits, Global, IsArray);
+  } else if (!consumeIf('E'))
+    return nullptr;
+  return make<NewExpr>(ExprList, Ty, NodeArray(), Global, IsArray);
+}
 
-static const char *parse_discriminator(const char *first, const char *last) {
-  // parse but ignore discriminator
-  if (first != last) {
-    if (*first == '_') {
-      const char *t1 = first + 1;
-      if (t1 != last) {
-        if (std::isdigit(*t1))
-          first = t1 + 1;
-        else if (*t1 == '_') {
-          for (++t1; t1 != last && std::isdigit(*t1); ++t1)
-            ;
-          if (t1 != last && *t1 == '_')
-            first = t1 + 1;
-        }
-      }
-    } else if (std::isdigit(*first)) {
-      const char *t1 = first + 1;
-      for (; t1 != last && std::isdigit(*t1); ++t1)
-        ;
-      if (t1 == last)
-        first = last;
+// cv <type> <expression>                               # conversion with one argument
+// cv <type> _ <expression>* E                          # conversion with a different number of arguments
+Node *Db::parseConversionExpr() {
+  if (!consumeIf("cv"))
+    return nullptr;
+  Node *Ty;
+  {
+    SwapAndRestore<bool> SaveTemp(TryToParseTemplateArgs, false);
+    Ty = parseType();
+  }
+
+  if (Ty == nullptr)
+    return nullptr;
+
+  if (consumeIf('_')) {
+    size_t ExprsBegin = Names.size();
+    while (!consumeIf('E')) {
+      Node *E = parseExpr();
+      if (E == nullptr)
+        return E;
+      Names.push_back(E);
     }
+    NodeArray Exprs = popTrailingNodeArray(ExprsBegin);
+    return make<ConversionExpr>(Ty, Exprs);
   }
-  return first;
+
+  Node *E[1] = {parseExpr()};
+  if (E[0] == nullptr)
+    return nullptr;
+  return make<ConversionExpr>(Ty, makeNodeArray(E, E + 1));
 }
 
-// <local-name> := Z <function encoding> E <entity name> [<discriminator>]
-//              := Z <function encoding> E s [<discriminator>]
-//              := Z <function encoding> Ed [ <parameter number> ] _ <entity
-//              name>
-
-template <class C>
-static const char *parse_local_name(const char *first, const char *last, C &db,
-                                    bool *ends_with_template_args) {
-  if (first != last && *first == 'Z') {
-    const char *t = parse_encoding(first + 1, last, db);
-    if (t != first + 1 && t != last && *t == 'E' && ++t != last) {
-      switch (*t) {
-      case 's':
-        first = parse_discriminator(t + 1, last);
-        if (db.names.empty())
-          return first;
-        db.names.back().first.append("::string literal");
-        break;
-      case 'd':
-        if (++t != last) {
-          const char *t1 = parse_number(t, last);
-          if (t1 != last && *t1 == '_') {
-            t = t1 + 1;
-            t1 = parse_name(t, last, db, ends_with_template_args);
-            if (t1 != t) {
-              if (db.names.size() < 2)
-                return first;
-              auto name = db.names.back().move_full();
-              db.names.pop_back();
-              if (db.names.empty())
-                return first;
-              db.names.back().first.append("::");
-              db.names.back().first.append(name);
-              first = t1;
-            } else if (!db.names.empty())
-              db.names.pop_back();
-          }
-        }
-        break;
-      default: {
-        const char *t1 = parse_name(t, last, db, ends_with_template_args);
-        if (t1 != t) {
-          // parse but ignore discriminator
-          first = parse_discriminator(t1, last);
-          if (db.names.size() < 2)
-            return first;
-          auto name = db.names.back().move_full();
-          db.names.pop_back();
-          if (db.names.empty())
-            return first;
-          db.names.back().first.append("::");
-          db.names.back().first.append(name);
-        } else if (!db.names.empty())
-          db.names.pop_back();
-      } break;
-      }
+// <expr-primary> ::= L <type> <value number> E                          # integer literal
+//                ::= L <type> <value float> E                           # floating literal
+//                ::= L <string type> E                                  # string literal
+//                ::= L <nullptr type> E                                 # nullptr literal (i.e., "LDnE")
+// FIXME:         ::= L <type> <real-part float> _ <imag-part float> E   # complex floating point literal (C 2000)
+//                ::= L <mangled-name> E                                 # external name
+Node *Db::parseExprPrimary() {
+  if (!consumeIf('L'))
+    return nullptr;
+  switch (look()) {
+  case 'w':
+    ++First;
+    return parseIntegerLiteral("wchar_t");
+  case 'b':
+    if (consumeIf("b0E"))
+      return make<BoolExpr>(0);
+    if (consumeIf("b1E"))
+      return make<BoolExpr>(1);
+    return nullptr;
+  case 'c':
+    ++First;
+    return parseIntegerLiteral("char");
+  case 'a':
+    ++First;
+    return parseIntegerLiteral("signed char");
+  case 'h':
+    ++First;
+    return parseIntegerLiteral("unsigned char");
+  case 's':
+    ++First;
+    return parseIntegerLiteral("short");
+  case 't':
+    ++First;
+    return parseIntegerLiteral("unsigned short");
+  case 'i':
+    ++First;
+    return parseIntegerLiteral("");
+  case 'j':
+    ++First;
+    return parseIntegerLiteral("u");
+  case 'l':
+    ++First;
+    return parseIntegerLiteral("l");
+  case 'm':
+    ++First;
+    return parseIntegerLiteral("ul");
+  case 'x':
+    ++First;
+    return parseIntegerLiteral("ll");
+  case 'y':
+    ++First;
+    return parseIntegerLiteral("ull");
+  case 'n':
+    ++First;
+    return parseIntegerLiteral("__int128");
+  case 'o':
+    ++First;
+    return parseIntegerLiteral("unsigned __int128");
+  case 'f':
+    ++First;
+    return parseFloatingLiteral<float>();
+  case 'd':
+    ++First;
+    return parseFloatingLiteral<double>();
+  case 'e':
+    ++First;
+    return parseFloatingLiteral<long double>();
+  case '_':
+    if (consumeIf("_Z")) {
+      Node *R = parseEncoding();
+      if (R != nullptr && consumeIf('E'))
+        return R;
+    }
+    return nullptr;
+  case 'T':
+    // Invalid mangled name per
+    //   http://sourcerytools.com/pipermail/cxx-abi-dev/2011-August/002422.html
+    return nullptr;
+  default: {
+    // might be named type
+    Node *T = parseType();
+    if (T == nullptr)
+      return nullptr;
+    StringView N = parseNumber();
+    if (!N.empty()) {
+      if (!consumeIf('E'))
+        return nullptr;
+      return make<IntegerCastExpr>(T, N);
     }
+    if (consumeIf('E'))
+      return T;
+    return nullptr;
+  }
   }
-  return first;
 }
 
-// <name> ::= <nested-name> // N
-//        ::= <local-name> # See Scope Encoding below  // Z
-//        ::= <unscoped-template-name> <template-args>
-//        ::= <unscoped-name>
+// <braced-expression> ::= <expression>
+//                     ::= di <field source-name> <braced-expression>    # .name = expr
+//                     ::= dx <index expression> <braced-expression>     # [expr] = expr
+//                     ::= dX <range begin expression> <range end expression> <braced-expression>
+Node *Db::parseBracedExpr() {
+  if (look() == 'd') {
+    switch (look(1)) {
+    case 'i': {
+      First += 2;
+      Node *Field = parseSourceName(/*NameState=*/nullptr);
+      if (Field == nullptr)
+        return nullptr;
+      Node *Init = parseBracedExpr();
+      if (Init == nullptr)
+        return nullptr;
+      return make<BracedExpr>(Field, Init, /*isArray=*/false);
+    }
+    case 'x': {
+      First += 2;
+      Node *Index = parseExpr();
+      if (Index == nullptr)
+        return nullptr;
+      Node *Init = parseBracedExpr();
+      if (Init == nullptr)
+        return nullptr;
+      return make<BracedExpr>(Index, Init, /*isArray=*/true);
+    }
+    case 'X': {
+      First += 2;
+      Node *RangeBegin = parseExpr();
+      if (RangeBegin == nullptr)
+        return nullptr;
+      Node *RangeEnd = parseExpr();
+      if (RangeEnd == nullptr)
+        return nullptr;
+      Node *Init = parseBracedExpr();
+      if (Init == nullptr)
+        return nullptr;
+      return make<BracedRangeExpr>(RangeBegin, RangeEnd, Init);
+    }
+    }
+  }
+  return parseExpr();
+}
 
-// <unscoped-template-name> ::= <unscoped-name>
-//                          ::= <substitution>
+// <expression> ::= <unary operator-name> <expression>
+//              ::= <binary operator-name> <expression> <expression>
+//              ::= <ternary operator-name> <expression> <expression> <expression>
+//              ::= cl <expression>+ E                                   # call
+//              ::= cv <type> <expression>                               # conversion with one argument
+//              ::= cv <type> _ <expression>* E                          # conversion with a different number of arguments
+//              ::= [gs] nw <expression>* _ <type> E                     # new (expr-list) type
+//              ::= [gs] nw <expression>* _ <type> <initializer>         # new (expr-list) type (init)
+//              ::= [gs] na <expression>* _ <type> E                     # new[] (expr-list) type
+//              ::= [gs] na <expression>* _ <type> <initializer>         # new[] (expr-list) type (init)
+//              ::= [gs] dl <expression>                                 # delete expression
+//              ::= [gs] da <expression>                                 # delete[] expression
+//              ::= pp_ <expression>                                     # prefix ++
+//              ::= mm_ <expression>                                     # prefix --
+//              ::= ti <type>                                            # typeid (type)
+//              ::= te <expression>                                      # typeid (expression)
+//              ::= dc <type> <expression>                               # dynamic_cast<type> (expression)
+//              ::= sc <type> <expression>                               # static_cast<type> (expression)
+//              ::= cc <type> <expression>                               # const_cast<type> (expression)
+//              ::= rc <type> <expression>                               # reinterpret_cast<type> (expression)
+//              ::= st <type>                                            # sizeof (a type)
+//              ::= sz <expression>                                      # sizeof (an expression)
+//              ::= at <type>                                            # alignof (a type)
+//              ::= az <expression>                                      # alignof (an expression)
+//              ::= nx <expression>                                      # noexcept (expression)
+//              ::= <template-param>
+//              ::= <function-param>
+//              ::= dt <expression> <unresolved-name>                    # expr.name
+//              ::= pt <expression> <unresolved-name>                    # expr->name
+//              ::= ds <expression> <expression>                         # expr.*expr
+//              ::= sZ <template-param>                                  # size of a parameter pack
+//              ::= sZ <function-param>                                  # size of a function parameter pack
+//              ::= sp <expression>                                      # pack expansion
+//              ::= tw <expression>                                      # throw expression
+//              ::= tr                                                   # throw with no operand (rethrow)
+//              ::= <unresolved-name>                                    # f(p), N::f(p), ::f(p),
+//                                                                       # freestanding dependent name (e.g., T::x),
+//                                                                       # objectless nonstatic member reference
+//              ::= fL <binary-operator-name> <expression> <expression>
+//              ::= fR <binary-operator-name> <expression> <expression>
+//              ::= fl <binary-operator-name> <expression>
+//              ::= fr <binary-operator-name> <expression>
+//              ::= <expr-primary>
+Node *Db::parseExpr() {
+  bool Global = consumeIf("gs");
+  if (numLeft() < 2)
+    return nullptr;
 
-template <class C>
-static const char *parse_name(const char *first, const char *last, C &db,
-                              bool *ends_with_template_args) {
-  if (last - first >= 2) {
-    const char *t0 = first;
-    // extension: ignore L here
-    if (*t0 == 'L')
-      ++t0;
-    switch (*t0) {
-    case 'N': {
-      const char *t1 = parse_nested_name(t0, last, db, ends_with_template_args);
-      if (t1 != t0)
-        first = t1;
-      break;
+  switch (*First) {
+  case 'L':
+    return parseExprPrimary();
+  case 'T':
+    return parseTemplateParam();
+  case 'f':
+    return parseFunctionParam();
+  case 'a':
+    switch (First[1]) {
+    case 'a':
+      First += 2;
+      return parseBinaryExpr("&&");
+    case 'd':
+      First += 2;
+      return parsePrefixExpr("&");
+    case 'n':
+      First += 2;
+      return parseBinaryExpr("&");
+    case 'N':
+      First += 2;
+      return parseBinaryExpr("&=");
+    case 'S':
+      First += 2;
+      return parseBinaryExpr("=");
+    case 't': {
+      First += 2;
+      Node *Ty = parseType();
+      if (Ty == nullptr)
+        return nullptr;
+      return make<EnclosingExpr>("alignof (", Ty, ")");
     }
-    case 'Z': {
-      const char *t1 = parse_local_name(t0, last, db, ends_with_template_args);
-      if (t1 != t0)
-        first = t1;
-      break;
+    case 'z': {
+      First += 2;
+      Node *Ty = parseExpr();
+      if (Ty == nullptr)
+        return nullptr;
+      return make<EnclosingExpr>("alignof (", Ty, ")");
     }
-    default: {
-      const char *t1 = parse_unscoped_name(t0, last, db);
-      if (t1 != t0) {
-        if (t1 != last &&
-            *t1 == 'I') // <unscoped-template-name> <template-args>
-        {
-          if (db.names.empty())
-            return first;
-          db.subs.push_back(typename C::sub_type(1, db.names.back()));
-          t0 = t1;
-          t1 = parse_template_args(t0, last, db);
-          if (t1 != t0) {
-            if (db.names.size() < 2)
-              return first;
-            auto tmp = db.names.back().move_full();
-            db.names.pop_back();
-            if (db.names.empty())
-              return first;
-            db.names.back().first += tmp;
-            first = t1;
-            if (ends_with_template_args)
-              *ends_with_template_args = true;
-          }
-        } else // <unscoped-name>
-          first = t1;
-      } else { // try <substitution> <template-args>
-        t1 = parse_substitution(t0, last, db);
-        if (t1 != t0 && t1 != last && *t1 == 'I') {
-          t0 = t1;
-          t1 = parse_template_args(t0, last, db);
-          if (t1 != t0) {
-            if (db.names.size() < 2)
-              return first;
-            auto tmp = db.names.back().move_full();
-            db.names.pop_back();
-            if (db.names.empty())
-              return first;
-            db.names.back().first += tmp;
-            first = t1;
-            if (ends_with_template_args)
-              *ends_with_template_args = true;
-          }
-        }
+    }
+    return nullptr;
+  case 'c':
+    switch (First[1]) {
+    // cc <type> <expression>                               # const_cast<type>(expression)
+    case 'c': {
+      First += 2;
+      Node *Ty = parseType();
+      if (Ty == nullptr)
+        return Ty;
+      Node *Ex = parseExpr();
+      if (Ex == nullptr)
+        return Ex;
+      return make<CastExpr>("const_cast", Ty, Ex);
+    }
+    // cl <expression>+ E                                   # call
+    case 'l': {
+      First += 2;
+      Node *Callee = parseExpr();
+      if (Callee == nullptr)
+        return Callee;
+      size_t ExprsBegin = Names.size();
+      while (!consumeIf('E')) {
+        Node *E = parseExpr();
+        if (E == nullptr)
+          return E;
+        Names.push_back(E);
       }
-      break;
+      return make<CallExpr>(Callee, popTrailingNodeArray(ExprsBegin));
+    }
+    case 'm':
+      First += 2;
+      return parseBinaryExpr(",");
+    case 'o':
+      First += 2;
+      return parsePrefixExpr("~");
+    case 'v':
+      return parseConversionExpr();
+    }
+    return nullptr;
+  case 'd':
+    switch (First[1]) {
+    case 'a': {
+      First += 2;
+      Node *Ex = parseExpr();
+      if (Ex == nullptr)
+        return Ex;
+      return make<DeleteExpr>(Ex, Global, /*is_array=*/true);
+    }
+    case 'c': {
+      First += 2;
+      Node *T = parseType();
+      if (T == nullptr)
+        return T;
+      Node *Ex = parseExpr();
+      if (Ex == nullptr)
+        return Ex;
+      return make<CastExpr>("dynamic_cast", T, Ex);
+    }
+    case 'e':
+      First += 2;
+      return parsePrefixExpr("*");
+    case 'l': {
+      First += 2;
+      Node *E = parseExpr();
+      if (E == nullptr)
+        return E;
+      return make<DeleteExpr>(E, Global, /*is_array=*/false);
+    }
+    case 'n':
+      return parseUnresolvedName();
+    case 's': {
+      First += 2;
+      Node *LHS = parseExpr();
+      if (LHS == nullptr)
+        return nullptr;
+      Node *RHS = parseExpr();
+      if (RHS == nullptr)
+        return nullptr;
+      return make<MemberExpr>(LHS, ".*", RHS);
+    }
+    case 't': {
+      First += 2;
+      Node *LHS = parseExpr();
+      if (LHS == nullptr)
+        return LHS;
+      Node *RHS = parseExpr();
+      if (RHS == nullptr)
+        return nullptr;
+      return make<MemberExpr>(LHS, ".", RHS);
+    }
+    case 'v':
+      First += 2;
+      return parseBinaryExpr("/");
+    case 'V':
+      First += 2;
+      return parseBinaryExpr("/=");
+    }
+    return nullptr;
+  case 'e':
+    switch (First[1]) {
+    case 'o':
+      First += 2;
+      return parseBinaryExpr("^");
+    case 'O':
+      First += 2;
+      return parseBinaryExpr("^=");
+    case 'q':
+      First += 2;
+      return parseBinaryExpr("==");
+    }
+    return nullptr;
+  case 'g':
+    switch (First[1]) {
+    case 'e':
+      First += 2;
+      return parseBinaryExpr(">=");
+    case 't':
+      First += 2;
+      return parseBinaryExpr(">");
+    }
+    return nullptr;
+  case 'i':
+    switch (First[1]) {
+    case 'x': {
+      First += 2;
+      Node *Base = parseExpr();
+      if (Base == nullptr)
+        return nullptr;
+      Node *Index = parseExpr();
+      if (Index == nullptr)
+        return Index;
+      return make<ArraySubscriptExpr>(Base, Index);
+    }
+    case 'l': {
+      First += 2;
+      size_t InitsBegin = Names.size();
+      while (!consumeIf('E')) {
+        Node *E = parseBracedExpr();
+        if (E == nullptr)
+          return nullptr;
+        Names.push_back(E);
+      }
+      return make<InitListExpr>(nullptr, popTrailingNodeArray(InitsBegin));
+    }
+    }
+    return nullptr;
+  case 'l':
+    switch (First[1]) {
+    case 'e':
+      First += 2;
+      return parseBinaryExpr("<=");
+    case 's':
+      First += 2;
+      return parseBinaryExpr("<<");
+    case 'S':
+      First += 2;
+      return parseBinaryExpr("<<=");
+    case 't':
+      First += 2;
+      return parseBinaryExpr("<");
+    }
+    return nullptr;
+  case 'm':
+    switch (First[1]) {
+    case 'i':
+      First += 2;
+      return parseBinaryExpr("-");
+    case 'I':
+      First += 2;
+      return parseBinaryExpr("-=");
+    case 'l':
+      First += 2;
+      return parseBinaryExpr("*");
+    case 'L':
+      First += 2;
+      return parseBinaryExpr("*=");
+    case 'm':
+      First += 2;
+      if (consumeIf('_'))
+        return parsePrefixExpr("--");
+      Node *Ex = parseExpr();
+      if (Ex == nullptr)
+        return nullptr;
+      return make<PostfixExpr>(Ex, "--");
+    }
+    return nullptr;
+  case 'n':
+    switch (First[1]) {
+    case 'a':
+    case 'w':
+      return parseNewExpr();
+    case 'e':
+      First += 2;
+      return parseBinaryExpr("!=");
+    case 'g':
+      First += 2;
+      return parsePrefixExpr("-");
+    case 't':
+      First += 2;
+      return parsePrefixExpr("!");
+    case 'x':
+      First += 2;
+      Node *Ex = parseExpr();
+      if (Ex == nullptr)
+        return Ex;
+      return make<EnclosingExpr>("noexcept (", Ex, ")");
+    }
+    return nullptr;
+  case 'o':
+    switch (First[1]) {
+    case 'n':
+      return parseUnresolvedName();
+    case 'o':
+      First += 2;
+      return parseBinaryExpr("||");
+    case 'r':
+      First += 2;
+      return parseBinaryExpr("|");
+    case 'R':
+      First += 2;
+      return parseBinaryExpr("|=");
+    }
+    return nullptr;
+  case 'p':
+    switch (First[1]) {
+    case 'm':
+      First += 2;
+      return parseBinaryExpr("->*");
+    case 'l':
+      First += 2;
+      return parseBinaryExpr("+");
+    case 'L':
+      First += 2;
+      return parseBinaryExpr("+=");
+    case 'p': {
+      First += 2;
+      if (consumeIf('_'))
+        return parsePrefixExpr("++");
+      Node *Ex = parseExpr();
+      if (Ex == nullptr)
+        return Ex;
+      return make<PostfixExpr>(Ex, "++");
+    }
+    case 's':
+      First += 2;
+      return parsePrefixExpr("+");
+    case 't': {
+      First += 2;
+      Node *L = parseExpr();
+      if (L == nullptr)
+        return nullptr;
+      Node *R = parseExpr();
+      if (R == nullptr)
+        return nullptr;
+      return make<MemberExpr>(L, "->", R);
+    }
+    }
+    return nullptr;
+  case 'q':
+    if (First[1] == 'u') {
+      First += 2;
+      Node *Cond = parseExpr();
+      if (Cond == nullptr)
+        return nullptr;
+      Node *LHS = parseExpr();
+      if (LHS == nullptr)
+        return nullptr;
+      Node *RHS = parseExpr();
+      if (RHS == nullptr)
+        return nullptr;
+      return make<ConditionalExpr>(Cond, LHS, RHS);
     }
+    return nullptr;
+  case 'r':
+    switch (First[1]) {
+    case 'c': {
+      First += 2;
+      Node *T = parseType();
+      if (T == nullptr)
+        return T;
+      Node *Ex = parseExpr();
+      if (Ex == nullptr)
+        return Ex;
+      return make<CastExpr>("reinterpret_cast", T, Ex);
+    }
+    case 'm':
+      First += 2;
+      return parseBinaryExpr("%");
+    case 'M':
+      First += 2;
+      return parseBinaryExpr("%=");
+    case 's':
+      First += 2;
+      return parseBinaryExpr(">>");
+    case 'S':
+      First += 2;
+      return parseBinaryExpr(">>=");
+    }
+    return nullptr;
+  case 's':
+    switch (First[1]) {
+    case 'c': {
+      First += 2;
+      Node *T = parseType();
+      if (T == nullptr)
+        return T;
+      Node *Ex = parseExpr();
+      if (Ex == nullptr)
+        return Ex;
+      return make<CastExpr>("static_cast", T, Ex);
+    }
+    case 'p': {
+      First += 2;
+      Node *Child = parseExpr();
+      if (Child == nullptr)
+        return nullptr;
+      return make<ParameterPackExpansion>(Child);
+    }
+    case 'r':
+      return parseUnresolvedName();
+    case 't': {
+      First += 2;
+      Node *Ty = parseType();
+      if (Ty == nullptr)
+        return Ty;
+      return make<EnclosingExpr>("sizeof (", Ty, ")");
     }
+    case 'z': {
+      First += 2;
+      Node *Ex = parseExpr();
+      if (Ex == nullptr)
+        return Ex;
+      return make<EnclosingExpr>("sizeof (", Ex, ")");
+    }
+    case 'Z':
+      First += 2;
+      if (look() == 'T') {
+        Node *R = parseTemplateParam();
+        if (R == nullptr)
+          return nullptr;
+        return make<SizeofParamPackExpr>(R);
+      } else if (look() == 'f') {
+        Node *FP = parseFunctionParam();
+        if (FP == nullptr)
+          return nullptr;
+        return make<EnclosingExpr>("sizeof...", FP, ")");
+      }
+      return nullptr;
+    }
+    return nullptr;
+  case 't':
+    switch (First[1]) {
+    case 'e': {
+      First += 2;
+      Node *Ex = parseExpr();
+      if (Ex == nullptr)
+        return Ex;
+      return make<EnclosingExpr>("typeid (", Ex, ")");
+    }
+    case 'i': {
+      First += 2;
+      Node *Ty = parseType();
+      if (Ty == nullptr)
+        return Ty;
+      return make<EnclosingExpr>("typeid (", Ty, ")");
+    }
+    case 'l': {
+      First += 2;
+      Node *Ty = parseType();
+      if (Ty == nullptr)
+        return nullptr;
+      size_t InitsBegin = Names.size();
+      while (!consumeIf('E')) {
+        Node *E = parseBracedExpr();
+        if (E == nullptr)
+          return nullptr;
+        Names.push_back(E);
+      }
+      return make<InitListExpr>(Ty, popTrailingNodeArray(InitsBegin));
+    }
+    case 'r':
+      First += 2;
+      return make<NameType>("throw");
+    case 'w': {
+      First += 2;
+      Node *Ex = parseExpr();
+      if (Ex == nullptr)
+        return nullptr;
+      return make<ThrowExpr>(Ex);
+    }
+    }
+    return nullptr;
+  case '1':
+  case '2':
+  case '3':
+  case '4':
+  case '5':
+  case '6':
+  case '7':
+  case '8':
+  case '9':
+    return parseUnresolvedName();
   }
-  return first;
+  return nullptr;
 }
 
 // <call-offset> ::= h <nv-offset> _
@@ -3811,26 +4291,15 @@ static const char *parse_name(const char *first, const char *last, C &db,
 //
 // <v-offset>  ::= <offset number> _ <virtual offset number>
 //               # virtual base override, with vcall offset
-
-static const char *parse_call_offset(const char *first, const char *last) {
-  if (first != last) {
-    switch (*first) {
-    case 'h': {
-      const char *t = parse_number(first + 1, last);
-      if (t != first + 1 && t != last && *t == '_')
-        first = t + 1;
-    } break;
-    case 'v': {
-      const char *t = parse_number(first + 1, last);
-      if (t != first + 1 && t != last && *t == '_') {
-        const char *t2 = parse_number(++t, last);
-        if (t2 != t && t2 != last && *t2 == '_')
-          first = t2 + 1;
-      }
-    } break;
-    }
-  }
-  return first;
+bool Db::parseCallOffset() {
+  // Just scan through the call offset, we never add this information into the
+  // output.
+  if (consumeIf('h'))
+    return parseNumber(true).empty() || !consumeIf('_');
+  if (consumeIf('v'))
+    return parseNumber(true).empty() || !consumeIf('_') ||
+           parseNumber(true).empty() || !consumeIf('_');
+  return true;
 }
 
 // <special-name> ::= TV <type>    # virtual table
@@ -3843,471 +4312,580 @@ static const char *parse_call_offset(const char *first, const char *last) {
 //                    # second call-offset is result adjustment
 //                ::= T <call-offset> <base encoding>
 //                    # base is the nominal target function of thunk
-//                ::= GV <object name> # Guard variable for one-time
-//                initialization
+//                ::= GV <object name> # Guard variable for one-time initialization
 //                                     # No <type>
 //                ::= TW <object name> # Thread-local wrapper
 //                ::= TH <object name> # Thread-local initialization
-//      extension ::= TC <first type> <number> _ <second type> # construction
-//      vtable for second-in-first
+//                ::= GR <object name> _             # First temporary
+//                ::= GR <object name> <seq-id> _    # Subsequent temporaries
+//      extension ::= TC <first type> <number> _ <second type> # construction vtable for second-in-first
 //      extension ::= GR <object name> # reference temporary for object
-
-template <class C>
-static const char *parse_special_name(const char *first, const char *last,
-                                      C &db) {
-  if (last - first > 2) {
-    const char *t;
-    switch (*first) {
-    case 'T':
-      switch (first[1]) {
-      case 'V':
-        // TV <type>    # virtual table
-        t = parse_type(first + 2, last, db);
-        if (t != first + 2) {
-          if (db.names.empty())
-            return first;
-          db.names.back().first.insert(0, "vtable for ");
-          first = t;
-        }
-        break;
-      case 'T':
-        // TT <type>    # VTT structure (construction vtable index)
-        t = parse_type(first + 2, last, db);
-        if (t != first + 2) {
-          if (db.names.empty())
-            return first;
-          db.names.back().first.insert(0, "VTT for ");
-          first = t;
-        }
-        break;
-      case 'I':
-        // TI <type>    # typeinfo structure
-        t = parse_type(first + 2, last, db);
-        if (t != first + 2) {
-          if (db.names.empty())
-            return first;
-          db.names.back().first.insert(0, "typeinfo for ");
-          first = t;
-        }
-        break;
-      case 'S':
-        // TS <type>    # typeinfo name (null-terminated byte string)
-        t = parse_type(first + 2, last, db);
-        if (t != first + 2) {
-          if (db.names.empty())
-            return first;
-          db.names.back().first.insert(0, "typeinfo name for ");
-          first = t;
-        }
-        break;
-      case 'c':
-        // Tc <call-offset> <call-offset> <base encoding>
-        {
-          const char *t0 = parse_call_offset(first + 2, last);
-          if (t0 == first + 2)
-            break;
-          const char *t1 = parse_call_offset(t0, last);
-          if (t1 == t0)
-            break;
-          t = parse_encoding(t1, last, db);
-          if (t != t1) {
-            if (db.names.empty())
-              return first;
-            db.names.back().first.insert(0, "covariant return thunk to ");
-            first = t;
-          }
-        }
-        break;
-      case 'C':
-        // extension ::= TC <first type> <number> _ <second type> # construction
-        // vtable for second-in-first
-        t = parse_type(first + 2, last, db);
-        if (t != first + 2) {
-          const char *t0 = parse_number(t, last);
-          if (t0 != t && t0 != last && *t0 == '_') {
-            const char *t1 = parse_type(++t0, last, db);
-            if (t1 != t0) {
-              if (db.names.size() < 2)
-                return first;
-              auto left = db.names.back().move_full();
-              db.names.pop_back();
-              if (db.names.empty())
-                return first;
-              db.names.back().first = "construction vtable for " +
-                                      std::move(left) + "-in-" +
-                                      db.names.back().move_full();
-              first = t1;
-            }
-          }
-        }
-        break;
-      case 'W':
-        // TW <object name> # Thread-local wrapper
-        t = parse_name(first + 2, last, db);
-        if (t != first + 2) {
-          if (db.names.empty())
-            return first;
-          db.names.back().first.insert(0, "thread-local wrapper routine for ");
-          first = t;
-        }
-        break;
-      case 'H':
-        // TH <object name> # Thread-local initialization
-        t = parse_name(first + 2, last, db);
-        if (t != first + 2) {
-          if (db.names.empty())
-            return first;
-          db.names.back().first.insert(
-              0, "thread-local initialization routine for ");
-          first = t;
-        }
-        break;
-      default:
-        // T <call-offset> <base encoding>
-        {
-          const char *t0 = parse_call_offset(first + 1, last);
-          if (t0 == first + 1)
-            break;
-          t = parse_encoding(t0, last, db);
-          if (t != t0) {
-            if (db.names.empty())
-              return first;
-            if (first[1] == 'v') {
-              db.names.back().first.insert(0, "virtual thunk to ");
-              first = t;
-            } else {
-              db.names.back().first.insert(0, "non-virtual thunk to ");
-              first = t;
-            }
-          }
-        }
-        break;
-      }
-      break;
-    case 'G':
-      switch (first[1]) {
-      case 'V':
-        // GV <object name> # Guard variable for one-time initialization
-        t = parse_name(first + 2, last, db);
-        if (t != first + 2) {
-          if (db.names.empty())
-            return first;
-          db.names.back().first.insert(0, "guard variable for ");
-          first = t;
-        }
-        break;
-      case 'R':
-        // extension ::= GR <object name> # reference temporary for object
-        t = parse_name(first + 2, last, db);
-        if (t != first + 2) {
-          if (db.names.empty())
-            return first;
-          db.names.back().first.insert(0, "reference temporary for ");
-          first = t;
-        }
-        break;
-      }
-      break;
+Node *Db::parseSpecialName() {
+  switch (look()) {
+  case 'T':
+    switch (look(1)) {
+    // TV <type>    # virtual table
+    case 'V': {
+      First += 2;
+      Node *Ty = parseType();
+      if (Ty == nullptr)
+        return nullptr;
+      return make<SpecialName>("vtable for ", Ty);
+    }
+    // TT <type>    # VTT structure (construction vtable index)
+    case 'T': {
+      First += 2;
+      Node *Ty = parseType();
+      if (Ty == nullptr)
+        return nullptr;
+      return make<SpecialName>("VTT for ", Ty);
+    }
+    // TI <type>    # typeinfo structure
+    case 'I': {
+      First += 2;
+      Node *Ty = parseType();
+      if (Ty == nullptr)
+        return nullptr;
+      return make<SpecialName>("typeinfo for ", Ty);
+    }
+    // TS <type>    # typeinfo name (null-terminated byte string)
+    case 'S': {
+      First += 2;
+      Node *Ty = parseType();
+      if (Ty == nullptr)
+        return nullptr;
+      return make<SpecialName>("typeinfo name for ", Ty);
+    }
+    // Tc <call-offset> <call-offset> <base encoding>
+    case 'c': {
+      First += 2;
+      if (parseCallOffset() || parseCallOffset())
+        return nullptr;
+      Node *Encoding = parseEncoding();
+      if (Encoding == nullptr)
+        return nullptr;
+      return make<SpecialName>("covariant return thunk to ", Encoding);
+    }
+    // extension ::= TC <first type> <number> _ <second type>
+    //               # construction vtable for second-in-first
+    case 'C': {
+      First += 2;
+      Node *FirstType = parseType();
+      if (FirstType == nullptr)
+        return nullptr;
+      if (parseNumber(true).empty() || !consumeIf('_'))
+        return nullptr;
+      Node *SecondType = parseType();
+      if (SecondType == nullptr)
+        return nullptr;
+      return make<CtorVtableSpecialName>(SecondType, FirstType);
+    }
+    // TW <object name> # Thread-local wrapper
+    case 'W': {
+      First += 2;
+      Node *Name = parseName();
+      if (Name == nullptr)
+        return nullptr;
+      return make<SpecialName>("thread-local wrapper routine for ", Name);
+    }
+    // TH <object name> # Thread-local initialization
+    case 'H': {
+      First += 2;
+      Node *Name = parseName();
+      if (Name == nullptr)
+        return nullptr;
+      return make<SpecialName>("thread-local initialization routine for ", Name);
+    }
+    // T <call-offset> <base encoding>
+    default: {
+      ++First;
+      bool IsVirt = look() == 'v';
+      if (parseCallOffset())
+        return nullptr;
+      Node *BaseEncoding = parseEncoding();
+      if (BaseEncoding == nullptr)
+        return nullptr;
+      if (IsVirt)
+        return make<SpecialName>("virtual thunk to ", BaseEncoding);
+      else
+        return make<SpecialName>("non-virtual thunk to ", BaseEncoding);
+    }
+    }
+  case 'G':
+    switch (look(1)) {
+    // GV <object name> # Guard variable for one-time initialization
+    case 'V': {
+      First += 2;
+      Node *Name = parseName();
+      if (Name == nullptr)
+        return nullptr;
+      return make<SpecialName>("guard variable for ", Name);
+    }
+    // GR <object name> # reference temporary for object
+    // GR <object name> _             # First temporary
+    // GR <object name> <seq-id> _    # Subsequent temporaries
+    case 'R': {
+      First += 2;
+      Node *Name = parseName();
+      if (Name == nullptr)
+        return nullptr;
+      size_t Count;
+      bool ParsedSeqId = !parseSeqId(&Count);
+      if (!consumeIf('_') && ParsedSeqId)
+        return nullptr;
+      return make<SpecialName>("reference temporary for ", Name);
+    }
     }
   }
-  return first;
+  return nullptr;
 }
 
-namespace {
-template <class T> class save_value {
-  T &restore_;
-  T original_value_;
+// <encoding> ::= <function name> <bare-function-type>
+//            ::= <data name>
+//            ::= <special-name>
+Node *Db::parseEncoding() {
+  // Always "tag" templates (insert them into Db::TemplateParams) unless we're
+  // doing a second parse to resolve a forward template reference, in which case
+  // we only tag templates if EncodingDepth > 1.
+  // FIXME: This is kinda broken; it would be better to make a forward reference
+  // and patch it all in one pass.
+  SwapAndRestore<bool> SaveTagTemplates(TagTemplates,
+                                        TagTemplates || EncodingDepth);
+  SwapAndRestore<unsigned> SaveEncodingDepth(EncodingDepth, EncodingDepth + 1);
+
+  if (look() == 'G' || look() == 'T')
+    return parseSpecialName();
+
+  auto IsEndOfEncoding = [&] {
+    // The set of chars that can potentially follow an <encoding> (none of which
+    // can start a <type>). Enumerating these allows us to avoid speculative
+    // parsing.
+    return numLeft() == 0 || look() == 'E' || look() == '.' || look() == '_';
+  };
+
+  NameState NameInfo;
+  Node *Name = parseName(&NameInfo);
+  if (Name == nullptr || IsEndOfEncoding())
+    return Name;
+
+  TagTemplates = false;
+
+  Node *ReturnType = nullptr;
+  if (!NameInfo.CtorDtorConversion && NameInfo.EndsWithTemplateArgs) {
+    ReturnType = parseType();
+    if (ReturnType == nullptr)
+      return nullptr;
+  }
 
-public:
-  save_value(T &restore) : restore_(restore), original_value_(restore) {}
+  if (consumeIf('v'))
+    return make<FunctionEncoding>(ReturnType, Name, NodeArray(),
+                                  NameInfo.CVQualifiers,
+                                  NameInfo.ReferenceQualifier);
+
+  size_t ParamsBegin = Names.size();
+  do {
+    Node *Ty = parseType();
+    if (Ty == nullptr)
+      return nullptr;
+    Names.push_back(Ty);
+  } while (!IsEndOfEncoding());
+
+  return make<FunctionEncoding>(ReturnType, Name,
+                                popTrailingNodeArray(ParamsBegin),
+                                NameInfo.CVQualifiers,
+                                NameInfo.ReferenceQualifier);
+}
 
-  ~save_value() { restore_ = std::move(original_value_); }
+template <class Float>
+struct FloatData;
 
-  save_value(const save_value &) = delete;
-  save_value &operator=(const save_value &) = delete;
+template <>
+struct FloatData<float>
+{
+    static const size_t mangled_size = 8;
+    static const size_t max_demangled_size = 24;
+    static constexpr const char* spec = "%af";
 };
+
+constexpr const char* FloatData<float>::spec;
+
+template <>
+struct FloatData<double>
+{
+    static const size_t mangled_size = 16;
+    static const size_t max_demangled_size = 32;
+    static constexpr const char* spec = "%a";
+};
+
+constexpr const char* FloatData<double>::spec;
+
+template <>
+struct FloatData<long double>
+{
+#if defined(__mips__) && defined(__mips_n64) || defined(__aarch64__) || \
+    defined(__wasm__)
+    static const size_t mangled_size = 32;
+#elif defined(__arm__) || defined(__mips__) || defined(__hexagon__)
+    static const size_t mangled_size = 16;
+#else
+    static const size_t mangled_size = 20;  // May need to be adjusted to 16 or 24 on other platforms
+#endif
+    static const size_t max_demangled_size = 40;
+    static constexpr const char *spec = "%LaL";
+};
+
+constexpr const char *FloatData<long double>::spec;
+
+template <class Float> Node *Db::parseFloatingLiteral() {
+  const size_t N = FloatData<Float>::mangled_size;
+  if (numLeft() <= N)
+    return nullptr;
+  StringView Data(First, First + N);
+  for (char C : Data)
+    if (!std::isxdigit(C))
+      return nullptr;
+  First += N;
+  if (!consumeIf('E'))
+    return nullptr;
+  return make<FloatExpr<Float>>(Data);
 }
 
-// <encoding> ::= <function name> <bare-function-type>
-//            ::= <data name>
-//            ::= <special-name>
+// <seq-id> ::= <0-9A-Z>+
+bool Db::parseSeqId(size_t *Out) {
+  if (!(look() >= '0' && look() <= '9') &&
+      !(look() >= 'A' && look() <= 'Z'))
+    return true;
+
+  size_t Id = 0;
+  while (true) {
+    if (look() >= '0' && look() <= '9') {
+      Id *= 36;
+      Id += static_cast<size_t>(look() - '0');
+    } else if (look() >= 'A' && look() <= 'Z') {
+      Id *= 36;
+      Id += static_cast<size_t>(look() - 'A') + 10;
+    } else {
+      *Out = Id;
+      return false;
+    }
+    ++First;
+  }
+}
+
+// <substitution> ::= S <seq-id> _
+//                ::= S_
+// <substitution> ::= Sa # ::std::allocator
+// <substitution> ::= Sb # ::std::basic_string
+// <substitution> ::= Ss # ::std::basic_string < char,
+//                                               ::std::char_traits<char>,
+//                                               ::std::allocator<char> >
+// <substitution> ::= Si # ::std::basic_istream<char,  std::char_traits<char> >
+// <substitution> ::= So # ::std::basic_ostream<char,  std::char_traits<char> >
+// <substitution> ::= Sd # ::std::basic_iostream<char, std::char_traits<char> >
+Node *Db::parseSubstitution() {
+  if (!consumeIf('S'))
+    return nullptr;
 
-template <class C>
-static const char *parse_encoding(const char *first, const char *last, C &db) {
-  if (first != last) {
-    save_value<decltype(db.encoding_depth)> su(db.encoding_depth);
-    ++db.encoding_depth;
-    save_value<decltype(db.tag_templates)> sb(db.tag_templates);
-    if (db.encoding_depth > 1)
-      db.tag_templates = true;
-    save_value<decltype(db.parsed_ctor_dtor_cv)> sp(db.parsed_ctor_dtor_cv);
-    db.parsed_ctor_dtor_cv = false;
-    switch (*first) {
-    case 'G':
-    case 'T':
-      first = parse_special_name(first, last, db);
+  if (std::islower(look())) {
+    Node *SpecialSub;
+    switch (look()) {
+    case 'a':
+      ++First;
+      SpecialSub = make<SpecialSubstitution>(SpecialSubKind::allocator);
       break;
-    default: {
-      bool ends_with_template_args = false;
-      const char *t = parse_name(first, last, db, &ends_with_template_args);
-      unsigned cv = db.cv;
-      unsigned ref = db.ref;
-      if (t != first) {
-        if (t != last && *t != 'E' && *t != '.') {
-          save_value<bool> sb2(db.tag_templates);
-          db.tag_templates = false;
-          const char *t2;
-          std::string ret2;
-          if (db.names.empty())
-            return first;
-          const std::string &nm = db.names.back().first;
-          if (nm.empty())
-            return first;
-          if (!db.parsed_ctor_dtor_cv && ends_with_template_args) {
-            t2 = parse_type(t, last, db);
-            if (t2 == t)
-              return first;
-            if (db.names.size() < 2)
-              return first;
-            auto ret1 = std::move(db.names.back().first);
-            ret2 = std::move(db.names.back().second);
-            if (ret2.empty())
-              ret1 += ' ';
-            db.names.pop_back();
-            if (db.names.empty())
-              return first;
-
-            db.names.back().first.insert(0, ret1);
-            t = t2;
-          }
-          db.names.back().first += '(';
-          if (t != last && *t == 'v') {
-            ++t;
-          } else {
-            bool first_arg = true;
-            while (true) {
-              size_t k0 = db.names.size();
-              t2 = parse_type(t, last, db);
-              size_t k1 = db.names.size();
-              if (t2 == t)
-                break;
-              if (k1 > k0) {
-                std::string tmp;
-                for (size_t k = k0; k < k1; ++k) {
-                  if (!tmp.empty())
-                    tmp += ", ";
-                  tmp += db.names[k].move_full();
-                }
-                for (size_t k = k0; k < k1; ++k) {
-                  if (db.names.empty())
-                    return first;
-                  db.names.pop_back();
-                }
-                if (!tmp.empty()) {
-                  if (db.names.empty())
-                    return first;
-                  if (!first_arg)
-                    db.names.back().first += ", ";
-                  else
-                    first_arg = false;
-                  db.names.back().first += tmp;
-                }
-              }
-              t = t2;
-            }
-          }
-          if (db.names.empty())
-            return first;
-          db.names.back().first += ')';
-          if (cv & CV_const)
-            db.names.back().first.append(" const");
-          if (cv & CV_volatile)
-            db.names.back().first.append(" volatile");
-          if (cv & CV_restrict)
-            db.names.back().first.append(" restrict");
-          if (ref == 1)
-            db.names.back().first.append(" &");
-          else if (ref == 2)
-            db.names.back().first.append(" &&");
-          db.names.back().first += ret2;
-          first = t;
-        } else
-          first = t;
-      }
+    case 'b':
+      ++First;
+      SpecialSub = make<SpecialSubstitution>(SpecialSubKind::basic_string);
+      break;
+    case 's':
+      ++First;
+      SpecialSub = make<SpecialSubstitution>(SpecialSubKind::string);
+      break;
+    case 'i':
+      ++First;
+      SpecialSub = make<SpecialSubstitution>(SpecialSubKind::istream);
+      break;
+    case 'o':
+      ++First;
+      SpecialSub = make<SpecialSubstitution>(SpecialSubKind::ostream);
       break;
+    case 'd':
+      ++First;
+      SpecialSub = make<SpecialSubstitution>(SpecialSubKind::iostream);
+      break;
+    default:
+      return nullptr;
     }
+    // Itanium C++ ABI 5.1.2: If a name that would use a built-in <substitution>
+    // has ABI tags, the tags are appended to the substitution; the result is a
+    // substitutable component.
+    Node *WithTags = parseAbiTags(SpecialSub);
+    if (WithTags != SpecialSub) {
+      Subs.push_back(WithTags);
+      SpecialSub = WithTags;
     }
+    return SpecialSub;
   }
-  return first;
+
+  //                ::= S_
+  if (consumeIf('_')) {
+    if (Subs.empty())
+      return nullptr;
+    return Subs[0];
+  }
+
+  //                ::= S <seq-id> _
+  size_t Index = 0;
+  if (parseSeqId(&Index))
+    return nullptr;
+  ++Index;
+  if (!consumeIf('_') || Index >= Subs.size())
+    return nullptr;
+  return Subs[Index];
 }
 
-// _block_invoke
-// _block_invoke<decimal-digit>+
-// _block_invoke_<decimal-digit>+
-
-template <class C>
-static const char *parse_block_invoke(const char *first, const char *last,
-                                      C &db) {
-  if (last - first >= 13) {
-    const char test[] = "_block_invoke";
-    const char *t = first;
-    for (int i = 0; i < 13; ++i, ++t) {
-      if (*t != test[i])
-        return first;
-    }
-    if (t != last) {
-      if (*t == '_') {
-        // must have at least 1 decimal digit
-        if (++t == last || !std::isdigit(*t))
-          return first;
-        ++t;
-      }
-      // parse zero or more digits
-      while (t != last && isdigit(*t))
-        ++t;
+// <template-param> ::= T_    # first template parameter
+//                  ::= T <parameter-2 non-negative number> _
+Node *Db::parseTemplateParam() {
+  if (!consumeIf('T'))
+    return nullptr;
+
+  size_t Index = 0;
+  if (!consumeIf('_')) {
+    if (parsePositiveInteger(&Index))
+      return nullptr;
+    ++Index;
+    if (!consumeIf('_'))
+      return nullptr;
+  }
+
+  // Itanium ABI 5.1.8: In a generic lambda, uses of auto in the parameter list
+  // are mangled as the corresponding artificial template type parameter.
+  if (ParsingLambdaParams)
+    return make<NameType>("auto");
+
+  if (Index >= TemplateParams.size()) {
+    FixForwardReferences = true;
+    return make<NameType>("FORWARD_REFERENCE");
+  }
+  return TemplateParams[Index];
+}
+
+// <template-arg> ::= <type>                    # type or template
+//                ::= X <expression> E          # expression
+//                ::= <expr-primary>            # simple expressions
+//                ::= J <template-arg>* E       # argument pack
+//                ::= LZ <encoding> E           # extension
+Node *Db::parseTemplateArg() {
+  switch (look()) {
+  case 'X': {
+    ++First;
+    Node *Arg = parseExpr();
+    if (Arg == nullptr || !consumeIf('E'))
+      return nullptr;
+    return Arg;
+  }
+  case 'J': {
+    ++First;
+    size_t ArgsBegin = Names.size();
+    while (!consumeIf('E')) {
+      Node *Arg = parseTemplateArg();
+      if (Arg == nullptr)
+        return nullptr;
+      Names.push_back(Arg);
     }
-    if (db.names.empty())
-      return first;
-    db.names.back().first.insert(0, "invocation function for block in ");
-    first = t;
+    NodeArray Args = popTrailingNodeArray(ArgsBegin);
+    return make<TemplateArgumentPack>(Args);
+  }
+  case 'L': {
+    //                ::= LZ <encoding> E           # extension
+    if (look(1) == 'Z') {
+      First += 2;
+      Node *Arg = parseEncoding();
+      if (Arg == nullptr || !consumeIf('E'))
+        return nullptr;
+      return Arg;
+    }
+    //                ::= <expr-primary>            # simple expressions
+    return parseExprPrimary();
+  }
+  default:
+    return parseType();
   }
-  return first;
 }
 
-// extension
-// <dot-suffix> := .<anything and everything>
+// <template-args> ::= I <template-arg>* E
+//     extension, the abi says <template-arg>+
+Node *Db::parseTemplateArgs() {
+  if (!consumeIf('I'))
+    return nullptr;
 
-template <class C>
-static const char *parse_dot_suffix(const char *first, const char *last,
-                                    C &db) {
-  if (first != last && *first == '.') {
-    if (db.names.empty())
-      return first;
-    db.names.back().first += " (" + std::string(first, last) + ")";
-    first = last;
+  // <template-params> refer to the innermost <template-args>. Clear out any
+  // outer args that we may have inserted into TemplateParams.
+  if (TagTemplates)
+    TemplateParams.clear();
+
+  size_t ArgsBegin = Names.size();
+  while (!consumeIf('E')) {
+    if (TagTemplates) {
+      auto OldParams = std::move(TemplateParams);
+      Node *Arg = parseTemplateArg();
+      TemplateParams = std::move(OldParams);
+      if (Arg == nullptr)
+        return nullptr;
+      Names.push_back(Arg);
+      Node *TableEntry = Arg;
+      if (Arg->getKind() == Node::KTemplateArgumentPack) {
+        TableEntry = make<ParameterPack>(
+            static_cast<TemplateArgumentPack*>(TableEntry)->getElements());
+      }
+      TemplateParams.push_back(TableEntry);
+    } else {
+      Node *Arg = parseTemplateArg();
+      if (Arg == nullptr)
+        return nullptr;
+      Names.push_back(Arg);
+    }
   }
-  return first;
+  return make<TemplateArgs>(popTrailingNodeArray(ArgsBegin));
 }
 
-// <block-involcaton-function> ___Z<encoding>_block_invoke
-// <block-involcaton-function> ___Z<encoding>_block_invoke<decimal-digit>+
-// <block-involcaton-function> ___Z<encoding>_block_invoke_<decimal-digit>+
-// <mangled-name> ::= _Z<encoding>
-//                ::= <type>
+// <discriminator> := _ <non-negative number>      # when number < 10
+//                 := __ <non-negative number> _   # when number >= 10
+//  extension      := decimal-digit+               # at the end of string
 
-template <class C>
-static void demangle(const char *first, const char *last, C &db, int &status) {
-  if (first >= last) {
-    status = invalid_mangled_name;
-    return;
-  }
-  if (*first == '_') {
-    if (last - first >= 4) {
-      if (first[1] == 'Z') {
-        const char *t = parse_encoding(first + 2, last, db);
-        if (t != first + 2 && t != last && *t == '.')
-          t = parse_dot_suffix(t, last, db);
-        if (t != last)
-          status = invalid_mangled_name;
-      } else if (first[1] == '_' && first[2] == '_' && first[3] == 'Z') {
-        const char *t = parse_encoding(first + 4, last, db);
-        if (t != first + 4 && t != last) {
-          const char *t1 = parse_block_invoke(t, last, db);
-          if (t1 != last)
-            status = invalid_mangled_name;
-        } else
-          status = invalid_mangled_name;
-      } else
-        status = invalid_mangled_name;
-    } else
-      status = invalid_mangled_name;
-  } else {
-    const char *t = parse_type(first, last, db);
-    if (t != last)
-      status = invalid_mangled_name;
-  }
-  if (status == success && db.names.empty())
-    status = invalid_mangled_name;
+const char*
+parse_discriminator(const char* first, const char* last)
+{
+    // parse but ignore discriminator
+    if (first != last)
+    {
+        if (*first == '_')
+        {
+            const char* t1 = first+1;
+            if (t1 != last)
+            {
+                if (std::isdigit(*t1))
+                    first = t1+1;
+                else if (*t1 == '_')
+                {
+                    for (++t1; t1 != last && std::isdigit(*t1); ++t1)
+                        ;
+                    if (t1 != last && *t1 == '_')
+                        first = t1 + 1;
+                }
+            }
+        }
+        else if (std::isdigit(*first))
+        {
+            const char* t1 = first+1;
+            for (; t1 != last && std::isdigit(*t1); ++t1)
+                ;
+            if (t1 == last)
+                first = last;
+        }
+    }
+    return first;
 }
 
-namespace {
-template <class StrT> struct string_pair {
-  StrT first;
-  StrT second;
-
-  string_pair() = default;
-  string_pair(StrT f) : first(std::move(f)) {}
-  string_pair(StrT f, StrT s) : first(std::move(f)), second(std::move(s)) {}
-  template <size_t N> string_pair(const char (&s)[N]) : first(s, N - 1) {}
-
-  size_t size() const { return first.size() + second.size(); }
-  bool empty() const { return first.empty() && second.empty(); }
-  StrT full() const { return first + second; }
-  StrT move_full() { return std::move(first) + std::move(second); }
-};
+// <mangled-name> ::= _Z <encoding>
+//                ::= <type>
+// extension      ::= ___Z <encoding> _block_invoke
+// extension      ::= ___Z <encoding> _block_invoke<decimal-digit>+
+// extension      ::= ___Z <encoding> _block_invoke_<decimal-digit>+
+Node *Db::parse() {
+  if (consumeIf("_Z")) {
+    Node *Encoding = parseEncoding();
+    if (Encoding == nullptr)
+      return nullptr;
+    if (look() == '.') {
+      Encoding = make<DotSuffix>(Encoding, StringView(First, Last));
+      First = Last;
+    }
+    if (numLeft() != 0)
+      return nullptr;
+    return Encoding;
+  }
 
-struct Db {
-  typedef std::vector<string_pair<std::string>> sub_type;
-  typedef std::vector<sub_type> template_param_type;
-  sub_type names;
-  template_param_type subs;
-  std::vector<template_param_type> template_param;
-  unsigned cv = 0;
-  unsigned ref = 0;
-  unsigned encoding_depth = 0;
-  bool parsed_ctor_dtor_cv = false;
-  bool tag_templates = true;
-  bool fix_forward_references = false;
-  bool try_to_parse_template_args = true;
-
-  Db() : subs(0, names), template_param(0, subs) {}
-};
+  if (consumeIf("___Z")) {
+    Node *Encoding = parseEncoding();
+    if (Encoding == nullptr || !consumeIf("_block_invoke"))
+      return nullptr;
+    bool RequireNumber = consumeIf('_');
+    if (parseNumber().empty() && RequireNumber)
+      return nullptr;
+    if (numLeft() != 0)
+      return nullptr;
+    return make<SpecialName>("invocation function for block in ", Encoding);
+  }
+
+  Node *Ty = parseType();
+  if (numLeft() != 0)
+    return nullptr;
+  return Ty;
 }
+}  // unnamed namespace
 
-char *llvm::itaniumDemangle(const char *mangled_name, char *buf, size_t *n,
-                            int *status) {
-  if (mangled_name == nullptr || (buf != nullptr && n == nullptr)) {
-    if (status)
-      *status = invalid_args;
+enum {
+  unknown_error = -4,
+  invalid_args = -3,
+  invalid_mangled_name = -2,
+  memory_alloc_failure = -1,
+  success = 0,
+};
+
+char *llvm::itaniumDemangle(const char *MangledName, char *Buf,
+                            size_t *N, int *Status) {
+  if (MangledName == nullptr || (Buf != nullptr && N == nullptr)) {
+    if (Status)
+      *Status = invalid_args;
     return nullptr;
   }
-  size_t internal_size = buf != nullptr ? *n : 0;
-  Db db;
-  db.template_param.emplace_back();
-  int internal_status = success;
-  size_t len = std::strlen(mangled_name);
-  demangle(mangled_name, mangled_name + len, db, internal_status);
-  if (internal_status == success && db.fix_forward_references &&
-      !db.template_param.empty() && !db.template_param.front().empty()) {
-    db.fix_forward_references = false;
-    db.tag_templates = false;
-    db.names.clear();
-    db.subs.clear();
-    demangle(mangled_name, mangled_name + len, db, internal_status);
-    if (db.fix_forward_references)
-      internal_status = invalid_mangled_name;
-  }
-  if (internal_status == success) {
-    size_t sz = db.names.back().size() + 1;
-    if (sz > internal_size) {
-      char *newbuf = static_cast<char *>(std::realloc(buf, sz));
-      if (newbuf == nullptr) {
-        internal_status = memory_alloc_failure;
-        buf = nullptr;
-      } else {
-        buf = newbuf;
-        if (n != nullptr)
-          *n = sz;
-      }
-    }
-    if (buf != nullptr) {
-      db.names.back().first += db.names.back().second;
-      std::memcpy(buf, db.names.back().first.data(), sz - 1);
-      buf[sz - 1] = char(0);
+
+  size_t BufSize = Buf != nullptr ? *N : 0;
+  int InternalStatus = success;
+  size_t MangledNameLength = std::strlen(MangledName);
+
+  Db Parser(MangledName, MangledName + MangledNameLength);
+  Node *AST = Parser.parse();
+
+  if (AST == nullptr)
+    InternalStatus = invalid_mangled_name;
+
+  if (InternalStatus == success && Parser.FixForwardReferences &&
+      !Parser.TemplateParams.empty()) {
+    Parser.FixForwardReferences = false;
+    Parser.TagTemplates = false;
+    Parser.Names.clear();
+    Parser.Subs.clear();
+    Parser.First = MangledName;
+    Parser.Last = MangledName + MangledNameLength;
+    AST = Parser.parse();
+    if (AST == nullptr || Parser.FixForwardReferences)
+      InternalStatus = invalid_mangled_name;
+  }
+
+  if (InternalStatus == success && AST->containsUnexpandedParameterPack())
+    InternalStatus = invalid_mangled_name;
+
+  if (InternalStatus == success) {
+    if (Buf == nullptr) {
+      BufSize = 1024;
+      Buf = static_cast<char*>(std::malloc(BufSize));
     }
-  } else
-    buf = nullptr;
-  if (status)
-    *status = internal_status;
-  return buf;
+
+    if (Buf) {
+      OutputStream Stream(Buf, BufSize);
+      AST->print(Stream);
+      Stream += '\0';
+      if (N != nullptr)
+        *N = Stream.getCurrentPosition();
+      Buf = Stream.getBuffer();
+    } else
+      InternalStatus = memory_alloc_failure;
+  }
+
+  if (Status)
+    *Status = InternalStatus;
+  return InternalStatus == success ? Buf : nullptr;
 }