Index: libcxxabi/trunk/src/cxa_demangle.cpp
===================================================================
--- libcxxabi/trunk/src/cxa_demangle.cpp
+++ libcxxabi/trunk/src/cxa_demangle.cpp
@@ -340,20 +340,17 @@
 
 class VendorExtQualType final : public Node {
   const Node *Ty;
-  const Node *Ext;
+  StringView Ext;
 
 public:
-  VendorExtQualType(Node *Ty_, Node *Ext_)
-      : Node(KVendorExtQualType,
-             std::min(Ty_->ParameterPackSize, Ext_->ParameterPackSize)),
+  VendorExtQualType(Node *Ty_, StringView Ext_)
+      : Node(KVendorExtQualType, Ty_->ParameterPackSize),
         Ty(Ty_), Ext(Ext_) {}
 
-  const Node* getQual() const { return Ext; }
-
   void printLeft(OutputStream &S) const override {
     Ty->print(S);
     S += " ";
-    Ext->print(S);
+    S += Ext;
   }
 };
 
@@ -465,12 +462,12 @@
 
 class ObjCProtoName : public Node {
   Node *Ty;
-  Node *Protocol;
+  StringView Protocol;
 
   friend class PointerType;
 
 public:
-  ObjCProtoName(Node *Ty_, Node *Protocol_)
+  ObjCProtoName(Node *Ty_, StringView Protocol_)
       : Node(KObjCProtoName), Ty(Ty_), Protocol(Protocol_) {}
 
   bool isObjCObject() const {
@@ -481,7 +478,7 @@
   void printLeft(OutputStream &S) const override {
     Ty->print(S);
     S += "<";
-    Protocol->print(S);
+    S += Protocol;
     S += ">";
   }
 };
@@ -512,7 +509,7 @@
     } else {
       const auto *objcProto = static_cast<const ObjCProtoName *>(Pointee);
       s += "id<";
-      objcProto->Protocol->print(s);
+      s += objcProto->Protocol;
       s += ">";
     }
   }
@@ -1958,6 +1955,8 @@
 
   StringView parseNumber(bool AllowNegative = false);
   Qualifiers parseCVQualifiers();
+  bool parsePositiveInteger(size_t *Out);
+  StringView parseBareSourceName();
 
   /// Parse the <expr> production.
   Node *parseExpr();
@@ -1970,6 +1969,15 @@
   Node *parseNewExpr();
   Node *parseConversionExpr();
 
+  /// Parse the <type> production.
+  Node *parseType();
+  Node *parseFunctionType();
+  Node *parseVectorType();
+  Node *parseDecltype();
+  Node *parseArrayType();
+  Node *parsePointerToMemberType();
+  Node *parseClassEnumType();
+
   // FIXME: remove this when all the parse_* functions have been rewritten.
   template <const char *(*parse_fn)(const char *, const char *, Db &)>
   Node *legacyParse() {
@@ -1983,6 +1991,18 @@
     Names.pop_back();
     return R;
   }
+  template <const char *(*parse_fn)(const char *, const char *, Db &, bool *)>
+  Node *legacyParse() {
+    size_t BeforeType = Names.size();
+    const char *OrigFirst = First;
+    const char *T = parse_fn(First, Last, *this, nullptr);
+    if (T == OrigFirst || BeforeType + 1 != Names.size())
+      return nullptr;
+    First = T;
+    Node *R = Names.back();
+    Names.pop_back();
+    return R;
+  }
 };
 
 const char *parse_expression(const char *first, const char *last, Db &db) {
@@ -2005,6 +2025,26 @@
   return db.First;
 }
 
+const char *parse_type(const char *first, const char *last, Db &db) {
+  db.First = first;
+  db.Last = last;
+  Node *R = db.parseType();
+  if (R == nullptr)
+    return first;
+  db.Names.push_back(R);
+  return db.First;
+}
+
+const char *parse_decltype(const char *first, const char *last, Db &db) {
+  db.First = first;
+  db.Last = last;
+  Node *R = db.parseDecltype();
+  if (R == nullptr)
+    return first;
+  db.Names.push_back(R);
+  return db.First;
+}
+
 const char *parse_type(const char *first, const char *last, Db &db);
 const char *parse_encoding(const char *first, const char *last, Db &db);
 const char *parse_name(const char *first, const char *last, Db &db,
@@ -2015,6 +2055,7 @@
 const char *parse_unqualified_name(const char *first, const char *last, Db &db);
 const char *parse_decltype(const char *first, const char *last, Db &db);
 const char *parse_unresolved_name(const char *, const char *, Db &);
+const char *parse_substitution(const char *, const char *, Db &);
 
 // <number> ::= [n] <non-negative decimal integer>
 StringView Db::parseNumber(bool AllowNegative) {
@@ -2028,6 +2069,539 @@
   return StringView(Tmp, 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;
+}
+
+StringView Db::parseBareSourceName() {
+  size_t Int = 0;
+  if (parsePositiveInteger(&Int) || numLeft() < Int)
+    return StringView();
+  StringView R(First, First + Int);
+  First += Int;
+  return R;
+}
+
+// <function-type> ::= F [Y] <bare-function-type> [<ref-qualifier>] E
+//
+//  <ref-qualifier> ::= R                   # & ref-qualifier
+//  <ref-qualifier> ::= O                   # && ref-qualifier
+Node *Db::parseFunctionType() {
+  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;
+    if (consumeIf('v'))
+      continue;
+    if (consumeIf("RE")) {
+      ReferenceQualifier = FrefQualLValue;
+      break;
+    }
+    if (consumeIf("OE")) {
+      ReferenceQualifier = FrefQualRValue;
+      break;
+    }
+    Node *T = parseType();
+    if (T == nullptr)
+      return nullptr;
+    Names.push_back(T);
+  }
+
+  NodeArray Params = popTrailingNodeArray(ParamsBegin);
+  Node *Fn = make<FunctionType>(ReturnType, Params);
+  if (ReferenceQualifier != FrefQualNone)
+    Fn = make<FunctionRefQualType>(Fn, ReferenceQualifier);
+  return Fn;
+}
+
+// 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() {
+  // FIXME: try to parse the elaborated type specifiers here!
+  return legacyParse<parse_name>();
+}
+
+// <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': {
+    Qualifiers Q = parseCVQualifiers();
+    bool AppliesToFunction = look() == 'F';
+
+    Node *Child = parseType();
+    if (Child == nullptr)
+      return nullptr;
+
+    if (AppliesToFunction)
+      Result = make<FunctionQualType>(Child, Q);
+    else
+      Result = make<QualType>(Child, Q);
+
+    // Itanium C++ ABI 5.1.5.3:
+    //   For the purposes of substitution, the CV-qualifiers and ref-qualifier
+    //   of a function type are an indivisible part of the type.
+    if (AppliesToFunction)
+      return Result;
+    break;
+  }
+  // <extended-qualifier> ::= U <source-name> [<template-args>] # vendor extended type qualifier
+  case 'U': {
+    // FIXME: We should fold this into the cvr qualifier parsing above. This
+    // currently adds too many entries into the substitution table if multiple
+    // qualifiers are present on the same type, as all the qualifiers on a type
+    // should just get one entry in the substitution table.
+    ++First;
+    StringView Qual = parseBareSourceName();
+    if (Qual.empty())
+      return nullptr;
+
+    // FIXME parse the optional <template-args> here!
+
+    Result = parseType();
+    if (Result == nullptr)
+      return nullptr;
+
+    // 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;
+      Result = make<ObjCProtoName>(Result, Proto);
+    } else
+      Result = make<VendorExtQualType>(Result, Qual);
+    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':
+      First += 2;
+      return make<NameType>("decimal64");
+    //                ::= De   # IEEE 754r decimal floating point (128 bits)
+    case 'e':
+      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':
+      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':
+      First += 2;
+      return make<NameType>("std::nullptr_t");
+
+    //             ::= <decltype>
+    case 't':
+    case 'T': {
+      Result = parseDecltype();
+      break;
+    }
+    // extension   ::= <vector-type> # <vector-type> starts with Dv
+    case 'v': {
+      Result = parseVectorType();
+      break;
+    }
+    //           ::= Dp <type>       # pack expansion (C++0x)
+    case 'p': {
+      First += 2;
+      Node *Child = parseType();
+      if (!Child)
+        return nullptr;
+      Result = make<ParameterPackExpansion>(Child);
+      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': {
+    Result = legacyParse<parse_template_param>();
+    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 = legacyParse<parse_template_args>();
+      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 = legacyParse<parse_substitution>();
+      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 = legacyParse<parse_template_args>();
+        if (TA == nullptr)
+          return nullptr;
+        Result = make<NameWithTemplateArgs>(Sub, TA);
+        break;
+      }
+
+      // If all we parsed was a substitution, don't re-insert into the
+      // substitution table.
+      return Sub;
+    }
+    _LIBCPP_FALLTHROUGH();
+  }
+  //        ::= <class-enum-type>
+  default: {
+    Result = parseClassEnumType();
+    break;
+  }
+  }
+
+  // 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;
+}
+
 Node *Db::parsePrefixExpr(StringView Kind) {
   Node *E = parseExpr();
   if (E == nullptr)
@@ -2107,7 +2681,7 @@
     Names.push_back(Ex);
   }
   NodeArray ExprList = popTrailingNodeArray(Exprs);
-  Node *Ty = legacyParse<parse_type>();
+  Node *Ty = parseType();
   if (Ty == nullptr)
     return Ty;
   if (consumeIf("pi")) {
@@ -2133,7 +2707,7 @@
   Node *Ty;
   {
     SwapAndRestore<bool> SaveTemp(TryToParseTemplateArgs, false);
-    Ty = legacyParse<parse_type>();
+    Ty = parseType();
   }
 
   if (Ty == nullptr)
@@ -2237,7 +2811,7 @@
     return nullptr;
   default: {
     // might be named type
-    Node *T = legacyParse<parse_type>();
+    Node *T = parseType();
     if (T == nullptr)
       return nullptr;
     StringView N = parseNumber();
@@ -2327,7 +2901,7 @@
       return parseBinaryExpr("=");
     case 't': {
       First += 2;
-      Node *Ty = legacyParse<parse_type>();
+      Node *Ty = parseType();
       if (Ty == nullptr)
         return nullptr;
       return make<EnclosingExpr>("alignof (", Ty, ")");
@@ -2346,7 +2920,7 @@
     // cc <type> <expression>                               # const_cast<type>(expression)
     case 'c': {
       First += 2;
-      Node *Ty = legacyParse<parse_type>();
+      Node *Ty = parseType();
       if (Ty == nullptr)
         return Ty;
       Node *Ex = parseExpr();
@@ -2390,7 +2964,7 @@
     }
     case 'c': {
       First += 2;
-      Node *T = legacyParse<parse_type>();
+      Node *T = parseType();
       if (T == nullptr)
         return T;
       Node *Ex = parseExpr();
@@ -2604,7 +3178,7 @@
     switch (First[1]) {
     case 'c': {
       First += 2;
-      Node *T = legacyParse<parse_type>();
+      Node *T = parseType();
       if (T == nullptr)
         return T;
       Node *Ex = parseExpr();
@@ -2630,7 +3204,7 @@
     switch (First[1]) {
     case 'c': {
       First += 2;
-      Node *T = legacyParse<parse_type>();
+      Node *T = parseType();
       if (T == nullptr)
         return T;
       Node *Ex = parseExpr();
@@ -2649,7 +3223,7 @@
       return legacyParse<parse_unresolved_name>();
     case 't': {
       First += 2;
-      Node *Ty = legacyParse<parse_type>();
+      Node *Ty = parseType();
       if (Ty == nullptr)
         return Ty;
       return make<EnclosingExpr>("sizeof (", Ty, ")");
@@ -2688,7 +3262,7 @@
     }
     case 'i': {
       First += 2;
-      Node *Ty = legacyParse<parse_type>();
+      Node *Ty = parseType();
       if (Ty == nullptr)
         return Ty;
       return make<EnclosingExpr>("typeid (", Ty, ")");
@@ -2958,206 +3532,27 @@
     return first;
 }
 
-// <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
+// <CV-Qualifiers> ::= [r] [V] [K]
 
 const char*
-parse_builtin_type(const char* first, const char* last, Db& db)
+parse_cv_qualifiers(const char* first, const char* last, Qualifiers& cv)
 {
+    cv = QualNone;
     if (first != last)
     {
-        switch (*first)
+        if (*first == 'r')
         {
-        case 'v':
-            db.Names.push_back(db.make<NameType>("void"));
-            ++first;
-            break;
-        case 'w':
-            db.Names.push_back(db.make<NameType>("wchar_t"));
-            ++first;
-            break;
-        case 'b':
-            db.Names.push_back(db.make<NameType>("bool"));
+            addQualifiers(cv, QualRestrict);
             ++first;
-            break;
-        case 'c':
-            db.Names.push_back(db.make<NameType>("char"));
+        }
+        if (*first == 'V')
+        {
+            addQualifiers(cv, QualVolatile);
             ++first;
-            break;
-        case 'a':
-            db.Names.push_back(db.make<NameType>("signed char"));
-            ++first;
-            break;
-        case 'h':
-            db.Names.push_back(db.make<NameType>("unsigned char"));
-            ++first;
-            break;
-        case 's':
-            db.Names.push_back(db.make<NameType>("short"));
-            ++first;
-            break;
-        case 't':
-            db.Names.push_back(db.make<NameType>("unsigned short"));
-            ++first;
-            break;
-        case 'i':
-            db.Names.push_back(db.make<NameType>("int"));
-            ++first;
-            break;
-        case 'j':
-            db.Names.push_back(db.make<NameType>("unsigned int"));
-            ++first;
-            break;
-        case 'l':
-            db.Names.push_back(db.make<NameType>("long"));
-            ++first;
-            break;
-        case 'm':
-            db.Names.push_back(db.make<NameType>("unsigned long"));
-            ++first;
-            break;
-        case 'x':
-            db.Names.push_back(db.make<NameType>("long long"));
-            ++first;
-            break;
-        case 'y':
-            db.Names.push_back(db.make<NameType>("unsigned long long"));
-            ++first;
-            break;
-        case 'n':
-            db.Names.push_back(db.make<NameType>("__int128"));
-            ++first;
-            break;
-        case 'o':
-            db.Names.push_back(db.make<NameType>("unsigned __int128"));
-            ++first;
-            break;
-        case 'f':
-            db.Names.push_back(db.make<NameType>("float"));
-            ++first;
-            break;
-        case 'd':
-            db.Names.push_back(db.make<NameType>("double"));
-            ++first;
-            break;
-        case 'e':
-            db.Names.push_back(db.make<NameType>("long double"));
-            ++first;
-            break;
-        case 'g':
-            db.Names.push_back(db.make<NameType>("__float128"));
-            ++first;
-            break;
-        case 'z':
-            db.Names.push_back(db.make<NameType>("..."));
-            ++first;
-            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(db.make<NameType>("decimal64"));
-                    first += 2;
-                    break;
-                case 'e':
-                    db.Names.push_back(db.make<NameType>("decimal128"));
-                    first += 2;
-                    break;
-                case 'f':
-                    db.Names.push_back(db.make<NameType>("decimal32"));
-                    first += 2;
-                    break;
-                case 'h':
-                    db.Names.push_back(db.make<NameType>("decimal16"));
-                    first += 2;
-                    break;
-                case 'i':
-                    db.Names.push_back(db.make<NameType>("char32_t"));
-                    first += 2;
-                    break;
-                case 's':
-                    db.Names.push_back(db.make<NameType>("char16_t"));
-                    first += 2;
-                    break;
-                case 'a':
-                    db.Names.push_back(db.make<NameType>("auto"));
-                    first += 2;
-                    break;
-                case 'c':
-                    db.Names.push_back(db.make<NameType>("decltype(auto)"));
-                    first += 2;
-                    break;
-                case 'n':
-                    db.Names.push_back(db.make<NameType>("std::nullptr_t"));
-                    first += 2;
-                    break;
-                }
-            }
-            break;
-        }
-    }
-    return first;
-}
-
-// <CV-Qualifiers> ::= [r] [V] [K]
-
-const char*
-parse_cv_qualifiers(const char* first, const char* last, Qualifiers& cv)
-{
-    cv = QualNone;
-    if (first != last)
-    {
-        if (*first == 'r')
-        {
-            addQualifiers(cv, QualRestrict);
-            ++first;
-        }
-        if (*first == 'V')
-        {
-            addQualifiers(cv, QualVolatile);
-            ++first;
-        }
-        if (*first == 'K')
-        {
-            addQualifiers(cv, QualConst);
+        }
+        if (*first == 'K')
+        {
+            addQualifiers(cv, QualConst);
             ++first;
         }
     }
@@ -3576,627 +3971,6 @@
     return first;
 }
 
-//  <ref-qualifier> ::= R                   # & ref-qualifier
-//  <ref-qualifier> ::= O                   # && ref-qualifier
-
-// <function-type> ::= F [Y] <bare-function-type> [<ref-qualifier>] E
-
-const char*
-parse_function_type(const char* first, const char* last, Db& 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 && !db.Names.empty())
-            {
-                Node* ret_type = db.Names.back();
-                db.Names.pop_back();
-                size_t params_begin = db.Names.size();
-                t = t1;
-                FunctionRefQual RefQuals = FrefQualNone;
-                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')
-                    {
-                        RefQuals = FrefQualLValue;
-                        ++t;
-                        continue;
-                    }
-                    if (*t == 'O' && t+1 != last && t[1] == 'E')
-                    {
-                        RefQuals = FrefQualRValue;
-                        ++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 || k1 < k0)
-                        return first;
-                    t = t1;
-                }
-                if (db.Names.empty() || params_begin > db.Names.size())
-                    return first;
-                Node* fty = db.make<FunctionType>(
-                    ret_type, db.popTrailingNodeArray(params_begin));
-                if (RefQuals)
-                    fty = db.make<FunctionRefQualType>(fty, RefQuals);
-                db.Names.push_back(fty);
-                first = t;
-            }
-        }
-    }
-    return first;
-}
-
-// <pointer-to-member-type> ::= M <class type> <member type>
-
-const char*
-parse_pointer_to_member_type(const char* first, const char* last, Db& 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 ClassType = std::move(db.Names.back());
-                db.Names.back() =
-                    db.make<PointerToMemberType>(ClassType, func);
-                first = t2;
-            }
-        }
-    }
-    return first;
-}
-
-// <array-type> ::= A <positive dimension number> _ <element type>
-//              ::= A [<dimension expression>] _ <element type>
-
-const char*
-parse_array_type(const char* first, const char* last, Db& 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;
-                db.Names.back() = db.make<ArrayType>(db.Names.back());
-                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;
-                    db.Names.back() =
-                        db.make<ArrayType>(db.Names.back(),
-                                            StringView(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 base_type = std::move(db.Names.back());
-                    db.Names.pop_back();
-                    auto dimension_expr = std::move(db.Names.back());
-                    db.Names.back() =
-                        db.make<ArrayType>(base_type, dimension_expr);
-                    first = t2;
-                }
-            }
-        }
-    }
-    return first;
-}
-
-// <decltype>  ::= Dt <expression> E  # decltype of an id-expression or class member access (C++0x)
-//             ::= DT <expression> E  # decltype of an expression (C++0x)
-
-const char*
-parse_decltype(const char* first, const char* last, Db& 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() = db.make<EnclosingExpr>(
-                        "decltype(", db.Names.back(), ")");
-                    first = t+1;
-                }
-            }
-            break;
-        }
-    }
-    return first;
-}
-
-// extension:
-// <vector-type>           ::= Dv <positive dimension number> _
-//                                    <extended element type>
-//                         ::= Dv [<dimension expression>] _ <element type>
-// <extended element type> ::= <element type>
-//                         ::= p # AltiVec vector pixel
-
-const char*
-parse_vector_type(const char* first, const char* last, Db& 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() =
-                            db.make<VectorType>(db.Names.back(),
-                                                 StringView(num, num + sz));
-                        first = t1;
-                    }
-                }
-                else
-                {
-                    ++t;
-                    db.Names.push_back(
-                        db.make<VectorType>(StringView(num, num + sz)));
-                    first = t;
-                }
-            }
-        }
-        else
-        {
-            Node* num = nullptr;
-            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();
-                    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;
-                    if (num)
-                        db.Names.back() =
-                            db.make<VectorType>(db.Names.back(), num);
-                    else
-                        db.Names.back() =
-                            db.make<VectorType>(db.Names.back(), StringView());
-                    first = t;
-                } else if (num)
-                    db.Names.push_back(num);
-            }
-        }
-    }
-    return first;
-}
-
-// <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>
-
-const char*
-parse_type(const char* first, const char* last, Db& db)
-{
-    if (first != last)
-    {
-        switch (*first)
-        {
-            case 'r':
-            case 'V':
-            case 'K':
-              {
-                Qualifiers cv = QualNone;
-                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 && k0 + 1 == k1)
-                    {
-                        if (is_function)
-                            db.Subs.pop_back();
-                        if (cv)
-                        {
-                            if (is_function)
-                                db.Names.back() = db.make<FunctionQualType>(
-                                    db.Names.back(), cv);
-                            else
-                                db.Names.back() =
-                                    db.make<QualType>(db.Names.back(), cv);
-                        }
-                        db.Subs.push_back(db.Names.back());
-                        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(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() = db.make<PostfixQualifiedType>(
-                                db.Names.back(), " complex");
-                            first = t;
-                            db.Subs.push_back(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(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() = db.make<PostfixQualifiedType>(
-                                db.Names.back(), " imaginary");
-                            first = t;
-                            db.Subs.push_back(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(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 && k0 + 1 == k1)
-                        {
-                            db.Names.back() =
-                                db.make<RValueReferenceType>(db.Names.back());
-                            db.Subs.push_back(db.Names.back());
-                            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 && k0 + 1 == k1)
-                        {
-                            db.Names.back() = db.make<PointerType>(db.Names.back());
-                            db.Subs.push_back(db.Names.back());
-                            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 && k0 + 1 == k1)
-                        {
-                            db.Names.back() =
-                                db.make<LValueReferenceType>(db.Names.back());
-                            db.Subs.push_back(db.Names.back());
-                            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 && k0 + 1 == k1)
-                        {
-                            db.Subs.push_back(db.Names.back());
-                            if (db.TryToParseTemplateArgs && k1 == k0+1)
-                            {
-                                const char* t1 = parse_template_args(t, last, db);
-                                if (t1 != t)
-                                {
-                                    auto args = db.Names.back();
-                                    db.Names.pop_back();
-                                    db.Names.back() = db.make<
-                                        NameWithTemplateArgs>(
-                                        db.Names.back(), args);
-                                    db.Subs.push_back(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();
-                                    db.Names.pop_back();
-                                    if (db.Names.back()->K != Node::KNameType ||
-                                        !static_cast<NameType*>(db.Names.back())->getName().startsWith("objcproto"))
-                                    {
-                                        db.Names.back() = db.make<VendorExtQualType>(type, db.Names.back());
-                                    }
-                                    else
-                                    {
-                                        auto* proto = static_cast<NameType*>(db.Names.back());
-                                        db.Names.pop_back();
-                                        t = parse_source_name(proto->getName().begin() + 9, proto->getName().end(), db);
-                                        if (t != proto->getName().begin() + 9)
-                                        {
-                                            db.Names.back() = db.make<ObjCProtoName>(type, db.Names.back());
-                                        }
-                                        else
-                                        {
-                                            db.Names.push_back(db.make<VendorExtQualType>(type, proto));
-                                        }
-                                    }
-                                    db.Subs.push_back(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(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>.
-                                if (db.TryToParseTemplateArgs)
-                                {
-                                    t = parse_template_args(first, last, db);
-                                    if (t != first)
-                                    {
-                                        if (db.Names.size() < 2)
-                                            return first;
-                                        auto template_args = db.Names.back();
-                                        db.Names.pop_back();
-                                        db.Names.back() = db.make<
-                                          NameWithTemplateArgs>(
-                                              db.Names.back(), template_args);
-                                        // Need to create substitution for <template-template-param> <template-args>
-                                        db.Subs.push_back(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 && k0 + 1 == k1)
-                                {
-                                    db.Names.back() =
-                                        db.make<ParameterPackExpansion>(
-                                            db.Names.back());
-                                    db.Subs.push_back(db.Names.back());
-                                    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(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(db.Names.back());
-                                    first = t;
-                                    return first;
-                                }
-                                break;
-                            }
-                        }
-                        _LIBCPP_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(db.Names.back());
-                                first = t;
-                            }
-                        }
-                        break;
-                    }
-              }
-                break;
-            }
-        }
-    }
-    return first;
-}
-
 //   <operator-name>
 //                   ::= aa    # &&            
 //                   ::= ad    # & (unary)