[libcxxabi][demangler] Clean up and llvm-ify the type parser

[erik.pilkington]

Summary

As of https://reviews.llvm.org/D41885, every parse_* function now either returns a single Node* or fails. I'm using this new rule to clean up the parsing for the demangler, and also update it to use LLVM coding conventions. This patch updates the type parser. This patch also fixes a bug I noticed where multiple qualifiers on a type get distinct entries in the substitution table.

Thanks!
Erik

[dexonsmith]

If it's possible to separate the bugfix into a separate commit (either before or after), I think you should.

[erik.pilkington]

Rebase and remove the qualifier substitution bug fix.

[dexonsmith]

LGTM!

src/cxa_demangle.cpp

   void printLeft(OutputStream &S) const override {
     Prefix->print(S);
     S += " (";
     S += Suffix;
     S += ")";
   }
 };
 
+class NameType final : public Node {
+  const StringView Name;
+
+public:
+  NameType(StringView Name_) : Node(KNameType), Name(Name_) {
+    setCachedRHSComponent(false);
+    setCachedArray(false);
+    setCachedFunction(false);
+    ParameterPackSize = NoParameterPack;
+  }
+
+  StringView getName() const { return Name; }
+  StringView getBaseName() const override { return Name; }
+
+  void printLeft(OutputStream &s) const override { s += Name; }
+};
+
 class VendorExtQualType final : public Node {
   const Node *Ty;
   const Node *Ext;
 
 public:
   VendorExtQualType(Node* Ty_, Node *Ext_)
       : Node(KVendorExtQualType), Ty(Ty_), Ext(Ext_) {
     ParameterPackSize = Ty->ParameterPackSize;
     if (Ty->HasCachedRHSComponent)
       setCachedRHSComponent(Ty->CachedRHSComponent);
     if (Ty->HasCachedArray)
       setCachedArray(Ty->CachedArray);
     if (Ty->HasCachedFunction)
       setCachedFunction(Ty->CachedFunction);
   }
 
+  bool isObjCObject() const {
+    return Ext->getKind() == KObjCProtoName &&
+      Ty->getKind() == KNameType &&
+      static_cast<const NameType*>(Ty)->getName() == "objc_object";
+  }
+
   const Node* getQual() const { return Ext; }
 
   void printLeft(OutputStream &S) const override {
     Ty->print(S);
-    S += " ";
+    if (Ext->getKind() != KObjCProtoName)
+      S += " ";
     Ext->printLeft(S);
   }
 };
 
 enum Qualifiers {
   QualNone = 0,
   QualConst = 0x1,
   QualVolatile = 0x2,

   void printLeft(OutputStream &s) const override {
     Ty->printLeft(s);
     s += Postfix;
   }
 
   void printRight(OutputStream &S) const override { Ty->printRight(S); }
 };
 
-class NameType final : public Node {
-  const StringView Name;
-
-public:
-  NameType(StringView Name_) : Node(KNameType), Name(Name_) {
-    setCachedRHSComponent(false);
-    setCachedArray(false);
-    setCachedFunction(false);
-    ParameterPackSize = NoParameterPack;
-  }
-
-  StringView getName() const { return Name; }
-  StringView getBaseName() const override { return Name; }
-
-  void printLeft(OutputStream &s) const override { s += Name; }
-};
-
 class AbiTagAttr final : public Node {
   const Node* Base;
   StringView Tag;
 public:
   AbiTagAttr(const Node* Base_, StringView Tag_) : Base(Base_), Tag(Tag_) {
     if (Base->HasCachedRHSComponent)
       setCachedRHSComponent(Base->CachedRHSComponent);
     if (Base->HasCachedArray)
       setCachedArray(Base->CachedArray);
     if (Base->HasCachedFunction)
       setCachedFunction(Base->CachedFunction);
     ParameterPackSize = Base->ParameterPackSize;
   }
 
   void printLeft(OutputStream &S) const override {
     Base->printLeft(S);
     S += "[abi:";
     S += Tag;
     S += "]";
   }
 };
 
 class ObjCProtoName : public Node {
-  Node *Ty;
-  Node *Protocol;
+  StringView Protocol;
 
   friend class PointerType;
 
 public:
-  ObjCProtoName(Node *Ty_, Node *Protocol_)
-      : Node(KObjCProtoName), Ty(Ty_), Protocol(Protocol_) {
+  ObjCProtoName(StringView Protocol_)
+      : Node(KObjCProtoName), Protocol(Protocol_) {
     setCachedRHSComponent(false);
     setCachedArray(false);
     setCachedFunction(false);
     ParameterPackSize = NoParameterPack;
   }
 
-  bool isObjCObject() const {
-    return Ty->getKind() == KNameType &&
-           static_cast<NameType *>(Ty)->getName() == "objc_object";
-  }
-
   void printLeft(OutputStream &S) const override {
-    Ty->print(S);
     S += "<";
-    Protocol->print(S);
+    S += Protocol;
     S += ">";
   }
 };
 
 class PointerType final : public Node {
   const Node *Pointee;
 
 public:
   PointerType(Node *Pointee_) : Pointee(Pointee_) {
     ParameterPackSize = Pointee->ParameterPackSize;
     if (Pointee->HasCachedRHSComponent)
       setCachedRHSComponent(Pointee->CachedRHSComponent);
     setCachedArray(false);
     setCachedFunction(false);
   }
 
   bool hasRHSComponentSlow(OutputStream &S) const override {
     return Pointee->hasRHSComponent(S);
   }
 
-  void printLeft(OutputStream &s) const override {
+  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 += "*";
+    if (Pointee->getKind() == KVendorExtQualType &&
+        static_cast<const VendorExtQualType *>(Pointee)->isObjCObject()) {
+      const auto *ExtQual = static_cast<const VendorExtQualType *>(Pointee);
+      S += "id";
+      ExtQual->getQual()->print(S);
     } else {
-      const auto *objcProto = static_cast<const ObjCProtoName *>(Pointee);
-      s += "id<";
-      objcProto->Protocol->print(s);
-      s += ">";
+      Pointee->printLeft(S);
+      if (Pointee->hasArray(S))
+        S += " ";
+      if (Pointee->hasArray(S) || Pointee->hasFunction(S))
+        S += "(";
+      S += "*";
     }
   }
 
-  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);
+  void printRight(OutputStream &S) const override {
+    if (Pointee->getKind() != KVendorExtQualType ||
+        !static_cast<const VendorExtQualType *>(Pointee)->isObjCObject()) {
+      if (Pointee->hasArray(S) || Pointee->hasFunction(S))
+        S += ")";
+      Pointee->printRight(S);
     }
   }
 };
 
 class LValueReferenceType final : public Node {
   const Node *Pointee;
 
 public:

       return '\0';
     return First[Lookahead];
   }
 
   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();
 
   /// 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();
 
+  /// Parse the <type> production.
+  Node *parseType();
+  Node *parseFunctionType();
+  Node *parseVectorType();
+  Node *parseDecltype();
+  Node *parseArrayType();
+  Node *parsePointerToMemberType();
+  Node *parseQualifiedType(bool &AppliesToFunction);
+  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() {
     size_t BeforeType = Names.size();
     const char *OrigFirst = First;
     const char *T = parse_fn(First, Last, *this);
     if (T == OrigFirst || BeforeType + 1 != Names.size())
       return nullptr;
     First = T;
     Node *R = Names.back();
     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)
 {
     db.First = first;
     db.Last = last;
     Node *R = db.parseExpr();

   db.Last = last;
   Node *R = db.parseExprPrimary();
   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_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_encoding(const char* first, const char* last, Db& db);
 const char* parse_name(const char* first, const char* last, Db& db,
                        bool* ends_with_template_args = 0);
 const char* parse_template_args(const char* first, const char* last, Db& db);
 const char* parse_template_param(const char*, const char*, Db&);
 const char* parse_operator_name(const char* first, const char* last, Db& db);
 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) {
   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);
 }
 
-Node *Db::parsePrefixExpr(StringView Kind) {
-  Node *E = parseExpr();
-  if (E == nullptr)
-    return nullptr;
-  return make<PrefixExpr>(Kind, E);
-  // FIXME inline this
+// <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;
 }
 
-Node *Db::parseBinaryExpr(StringView Kind) {
-  Node *LHS = parseExpr();
-  if (LHS == nullptr)
+StringView Db::parseBareSourceName() {
+  size_t Int = 0;
+  if (parsePositiveInteger(&Int) || numLeft() < Int)
+    return StringView();
+  StringView R(First, First + Int);
+  First += Int;
+  return R;
+}
+
+//  <ref-qualifier> ::= R                   # & ref-qualifier
+//  <ref-qualifier> ::= O                   # && ref-qualifier
+//
+// <function-type> ::= F [Y] <bare-function-type> [<ref-qualifier>] E
+Node *Db::parseFunctionType() {
+  if (!consumeIf('F'))
     return nullptr;
-  Node *RHS = parseExpr();
-  if (RHS == nullptr)
+  consumeIf('Y'); // extern "C"
+  Node *ReturnType = parseType();
+  if (ReturnType == nullptr)
     return nullptr;
-  return make<BinaryExpr>(LHS, Kind, RHS);
-}
 
-Node *Db::parseIntegerLiteral(StringView Lit) {
-  StringView Tmp = parseNumber(true);
-  if (!Tmp.empty() && consumeIf('E'))
-    return make<IntegerExpr>(Lit, Tmp);
-  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);
+  }
 
-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;
+  NodeArray Params = popTrailingNodeArray(ParamsBegin);
+  Node *Fn = make<FunctionType>(ReturnType, Params);
+  if (ReferenceQualifier)
+    Fn = make<FunctionRefQualType>(Fn, ReferenceQualifier);
+  return Fn;
 }
 
-// <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();
+// 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 (*First >= '1' && *First <= '9') {
+    StringView DimensionNumber = parseNumber();
     if (!consumeIf('_'))
       return nullptr;
-    return make<FunctionParam>(Num);
-  }
-  if (consumeIf("fL")) {
-    if (parseNumber().empty())
+    if (consumeIf('p'))
+      return make<VectorType>(DimensionNumber);
+    Node *ElemType = parseType();
+    if (ElemType == nullptr)
       return nullptr;
-    if (!consumeIf('p'))
+    return make<VectorType>(ElemType, DimensionNumber);
+  }
+
+  if (!consumeIf('_')) {
+    Node *DimExpr = parseExpr();
+    if (!DimExpr)
       return nullptr;
-    parseCVQualifiers();
-    StringView Num = parseNumber();
     if (!consumeIf('_'))
       return nullptr;
-    return make<FunctionParam>(Num);
+    Node *ElemType = parseType();
+    if (!ElemType)
+      return nullptr;
+    return make<VectorType>(ElemType, DimExpr);
   }
+
   return nullptr;
 }
 
-// [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) == 'w';
-  if (!consumeIf("nw") && !consumeIf("na"))
+// <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;
-  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 = legacyParse<parse_type>();
-  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);
-  }
-  return make<NewExpr>(ExprList, Ty, NodeArray(), Global, IsArray);
+  if (!consumeIf('t') && !consumeIf('T'))
+    return nullptr;
+  Node *E = parseExpr();
+  if (E == nullptr)
+  if (!consumeIf('E'))
+    return nullptr;
+  return make<EnclosingExpr>("decltype(", E, ")");
 }
 
-// cv <type> <expression>                               # conversion with one argument
-// cv <type> _ <expression>* E                          # conversion with a different number of arguments
-Node *Db::parseConversionExpr() {
-  if (!consumeIf("cv"))
+// <array-type> ::= A <positive dimension number> _ <element type>
+//              ::= A [<dimension expression>] _ <element type>
+Node *Db::parseArrayType() {
+  if (!consumeIf('A'))
     return nullptr;
-  Node *Ty;
-  {
-    SwapAndRestore<bool> SaveTemp(TryToParseTemplateArgs, false);
-    Ty = legacyParse<parse_type>();
+
+  if (std::isdigit(*First)) {
+    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);
+}
 
-  if (consumeIf('_')) {
-    size_t ExprsBegin = Names.size();
-    while (!consumeIf('E')) {
-      Node *E = legacyParse<parse_type>();
-      if (E == nullptr)
-        return E;
-      Names.push_back(E);
+// <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);
+}
+
+// <qualified-type>     ::= <qualifiers> <type>
+//
+// <qualifiers>         ::= <extended-qualifier>* <CV-qualifiers>
+//
+// <extended-qualifier> ::= U <source-name> [<template-args>] # vendor extended type qualifier
+//
+// <CV-qualifiers>      ::= [r] [V] [K]     # restrict (C99), volatile, const
+Node *Db::parseQualifiedType(bool &AppliesToFunction) {
+  // First, parse the <extended-qualifier>*
+  PODSmallVector<Node*, 2> ExtendedQualifiers;
+  while (consumeIf('U')) {
+    StringView Result = parseBareSourceName();
+    if (Result.empty())
+      return nullptr;
+
+    if (Result.startsWith("objcproto")) {
+      StringView ProtoName = Result.dropFront(std::strlen("objcproto"));
+      StringView BareProto;
+      {
+        SwapAndRestore<const char *> SaveFirst(First, ProtoName.begin()),
+                                     SaveLast(Last, ProtoName.end());
+        StringView SN = parseBareSourceName();
+        if (SN.empty())
+          return nullptr;
+        ExtendedQualifiers.push_back(make<ObjCProtoName>(SN));
+        continue;
+      }
     }
-    NodeArray Exprs = popTrailingNodeArray(ExprsBegin);
-    return make<ConversionExpr>(Ty, Exprs);
+
+    // FIXME: parse the optional <template-args> here.
+
+    ExtendedQualifiers.push_back(make<NameType>(Result));
   }
 
-  Node *E = parseExpr();
-  if (E == nullptr)
+  // Next, parse any cvr qualifiers.
+  Qualifiers CVR = parseCVQualifiers();
+
+  if (CVR == QualNone && ExtendedQualifiers.empty())
     return nullptr;
-  return make<ConversionExpr>(Ty, makeNodeArray(&E, &E + 1));
-}
 
-// <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'))
+  Node *Ty = parseType();
+  if (!Ty)
     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);
+  AppliesToFunction = Ty->getKind() == Node::KFunctionType ||
+                      Ty->getKind() == Node::KFunctionRefQualType;
+  // Apply the qualifiers to Ty.
+  if (CVR != QualNone) {
+    if (AppliesToFunction)
+      Ty = make<FunctionQualType>(Ty, CVR);
+    else
+      Ty = make<QualType>(Ty, CVR);
+  }
+  for (auto* ExtQ : ExtendedQualifiers)
+    Ty = make<VendorExtQualType>(Ty, ExtQ);
+  return Ty;
+}
+
+// <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() {
+  if (numLeft() == 0)
     return nullptr;
+
+  Node *Result = nullptr;
+
+  switch (*First) {
+  //             ::= <qualified-type>
+  case 'U':
+  case 'r':
+  case 'V':
+  case 'K': {
+    bool AppliesToFunction = false;
+    Result = parseQualifiedType(AppliesToFunction);
+    // Functions have the rule that both them and their qualifiers form just one
+    // entry in the substitution table. Bail out before the (now) qualified
+    // function gets inserted into the substitution table.
+    if (AppliesToFunction)
+      return Result;
+    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 parseIntegerLiteral("char");
+    return make<NameType>("char");
+  //                ::= a    # signed char
   case 'a':
     ++First;
-    return parseIntegerLiteral("signed char");
+    return make<NameType>("signed char");
+  //                ::= h    # unsigned char
   case 'h':
     ++First;
-    return parseIntegerLiteral("unsigned char");
+    return make<NameType>("unsigned char");
+  //                ::= s    # short
   case 's':
     ++First;
-    return parseIntegerLiteral("short");
+    return make<NameType>("short");
+  //                ::= t    # unsigned short
   case 't':
     ++First;
-    return parseIntegerLiteral("unsigned short");
+    return make<NameType>("unsigned short");
+  //                ::= i    # int
   case 'i':
     ++First;
-    return parseIntegerLiteral("");
+    return make<NameType>("int");
+  //                ::= j    # unsigned int
   case 'j':
     ++First;
-    return parseIntegerLiteral("u");
+    return make<NameType>("unsigned int");
+  //                ::= l    # long
   case 'l':
     ++First;
-    return parseIntegerLiteral("l");
+    return make<NameType>("long");
+  //                ::= m    # unsigned long
   case 'm':
     ++First;
-    return parseIntegerLiteral("ul");
+    return make<NameType>("unsigned long");
+  //                ::= x    # long long, __int64
   case 'x':
     ++First;
-    return parseIntegerLiteral("ll");
+    return make<NameType>("long long");
+  //                ::= y    # unsigned long long, __int64
   case 'y':
     ++First;
-    return parseIntegerLiteral("ull");
+    return make<NameType>("unsigned long long");
+  //                ::= n    # __int128
   case 'n':
     ++First;
-    return parseIntegerLiteral("__int128");
+    return make<NameType>("__int128");
+  //                ::= o    # unsigned __int128
   case 'o':
     ++First;
-    return parseIntegerLiteral("unsigned __int128");
+    return make<NameType>("unsigned __int128");
+  //                ::= f    # float
   case 'f':
     ++First;
-    return parseFloatingLiteral<float>();
+    return make<NameType>("float");
+  //                ::= d    # double
   case 'd':
     ++First;
-    return parseFloatingLiteral<double>();
+    return make<NameType>("double");
+  //                ::= e    # long double, __float80
   case 'e':
     ++First;
-    return parseFloatingLiteral<long double>();
-  case '_':
-    if (consumeIf("_Z")) {
-      Node *R = legacyParse<parse_encoding>();
-      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 = legacyParse<parse_type>();
-    if (T == nullptr)
+    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;
-    StringView N = parseNumber();
-    if (!N.empty()) {
-      if (!consumeIf('E'))
-        return nullptr;
-      return make<IntegerCastExpr>(T, N);
-    }
-    if (consumeIf('E'))
-      return T;
-    return nullptr;
-  }
+    return make<NameType>(Res);
   }
-}
-
-// <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;
-
-  switch (*First) {
-  case 'L': return parseExprPrimary();
-  case 'T': return legacyParse<parse_template_param>();
-  case 'f': return parseFunctionParam();
-  case 'a':
+  case 'D':
+    if (numLeft() < 2)
+      return nullptr;
     switch (First[1]) {
-    case 'a':
-      First += 2;
-      return parseBinaryExpr("&&");
+    //                ::= Dd   # IEEE 754r decimal floating point (64 bits)
     case 'd':
       First += 2;
-      return parsePrefixExpr("&");
-    case 'n':
-      First += 2;
-      return parseBinaryExpr("&");
-    case 'N':
-      First += 2;
-      return parseBinaryExpr("&=");
-    case 'S':
+      return make<NameType>("decimal64");
+    //                ::= De   # IEEE 754r decimal floating point (128 bits)
+    case 'e':
       First += 2;
-      return parseBinaryExpr("=");
-    case 't': {
+      return make<NameType>("decimal128");
+    //                ::= Df   # IEEE 754r decimal floating point (32 bits)
+    case 'f':
       First += 2;
-      Node *Ty = legacyParse<parse_type>();
-      if (Ty == nullptr)
-        return nullptr;
-      return make<EnclosingExpr>("alignof (", Ty, ")");
-    }
-    case 'z': {
+      return make<NameType>("decimal32");
+    //                ::= Dh   # IEEE 754r half-precision floating point (16 bits)
+    case 'h':
       First += 2;
-      Node *Ty = parseExpr();
-      if (Ty == nullptr)
-        return nullptr;
-      return make<EnclosingExpr>("alignof (", Ty, ")");
-    }
-    }
-    return nullptr;
-  case 'c':
-    switch (First[1]) {
-    // cc <type> <expression>                               # const_cast<type> (expression)
-    case 'c': {
+      return make<NameType>("decimal16");
+    //                ::= Di   # char32_t
+    case 'i':
       First += 2;
-      Node *Ty = legacyParse<parse_type>();
-      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': {
+      return make<NameType>("char32_t");
+    //                ::= Ds   # char16_t
+    case 's':
       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);
-      }
-      return make<CallExpr>(Callee, popTrailingNodeArray(ExprsBegin));
-    }
-    case 'm':
+      return make<NameType>("char16_t");
+    //                ::= Da   # auto (in dependent new-expressions)
+    case 'a':
       First += 2;
-      return parseBinaryExpr(",");
-    case 'o':
+      return make<NameType>("auto");
+    //                ::= Dc   # decltype(auto)
+    case 'c':
       First += 2;
-      return parsePrefixExpr("~");
-    case 'v':
-      return parseConversionExpr();
-    }
-    return nullptr;
-  case 'd':
-    switch (First[1]) {
-    case 'a': {
+      return make<NameType>("decltype(auto)");
+    //                ::= Dn   # std::nullptr_t (i.e., decltype(nullptr))
+    case 'n':
       First += 2;
-      Node *Ex = parseExpr();
-      if (Ex == nullptr)
-        return Ex;
-      return make<DeleteExpr>(Ex, Global, /*is_array=*/true);
+      return make<NameType>("std::nullptr_t");
+
+    //             ::= <decltype>
+    case 't':
+    case 'T': {
+      Result = parseDecltype();
+      break;
     }
-    case 'c': {
-      First += 2;
-      Node *T = legacyParse<parse_type>();
-      if (T == nullptr)
-        return T;
-      Node *Ex = parseExpr();
-      if (Ex == nullptr)
-        return Ex;
-      return make<CastExpr>("dynamic_cast", T, Ex);
+    // extension   ::= <vector-type> # <vector-type> starts with Dv
+    case 'v': {
+      Result = parseVectorType();
+      break;
     }
-    case 'e':
-      First += 2;
-      return parsePrefixExpr("*");
-    case 'l': {
+    //           ::= Dp <type>       # pack expansion (C++0x)
+    case 'p': {
       First += 2;
-      Node *E = parseExpr();
-      if (E == nullptr)
-        return E;
-      return make<DeleteExpr>(E, Global, /*is_array=*/false);
+      Node *Child = parseType();
+      if (!Child)
+        return nullptr;
+      Result = make<ParameterPackExpansion>(Child);
+      break;
     }
-    case 'n': {
-      First++;
-      return legacyParse<parse_unresolved_name>();
     }
-    case 's': {
-      First += 2;
-      Node *LHS = parseExpr();
-      if (LHS == nullptr)
-        return nullptr;
-      Node *RHS = parseExpr();
-      if (RHS == nullptr)
+    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 && numLeft() != 0 && *First == 'I') {
+      Node *TA = legacyParse<parse_template_args>();
+      if (TA == nullptr)
         return nullptr;
-      return make<MemberExpr>(LHS, ".*", RHS);
+      Result = make<NameWithTemplateArgs>(Result, TA);
     }
-    case 't': {
-      First += 2;
-      Node *LHS = parseExpr();
-      if (LHS == nullptr)
-        return LHS;
-      Node *RHS = parseExpr();
-      if (RHS == nullptr)
+    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 (numLeft() < 2 || First[1] != 't') {
+      Node *Sub = legacyParse<parse_substitution>();
+      if (Sub == nullptr)
         return nullptr;
-      return make<MemberExpr>(LHS, ".", RHS);
+
+      // 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 && numLeft() != 0 && *First == '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;
     }
-    case 'v':
+    _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)
+    return nullptr;
+  return make<PrefixExpr>(Kind, E);
+  // FIXME inline this
+}
+
+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);
+}
+
+Node *Db::parseIntegerLiteral(StringView Lit) {
+  StringView Tmp = parseNumber(true);
+  if (!Tmp.empty() && consumeIf('E'))
+    return make<IntegerExpr>(Lit, Tmp);
+  return nullptr;
+}
+
+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 nullptr;
+}
+
+// [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) == 'w';
+  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);
+  }
+  return make<NewExpr>(ExprList, Ty, NodeArray(), Global, IsArray);
+}
+
+// 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 = parseType();
+      if (E == nullptr)
+        return E;
+      Names.push_back(E);
+    }
+    NodeArray Exprs = popTrailingNodeArray(ExprsBegin);
+    return make<ConversionExpr>(Ty, Exprs);
+  }
+
+  Node *E = parseExpr();
+  if (E == nullptr)
+    return nullptr;
+  return make<ConversionExpr>(Ty, makeNodeArray(&E, &E + 1));
+}
+
+// <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 = legacyParse<parse_encoding>();
+      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;
+  }
+  }
+}
+
+// <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;
+
+  switch (*First) {
+  case 'L': return parseExprPrimary();
+  case 'T': return legacyParse<parse_template_param>();
+  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': {
+      First += 2;
+      Node *Ty = parseExpr();
+      if (Ty == nullptr)
+        return nullptr;
+      return make<EnclosingExpr>("alignof (", Ty, ")");
+    }
+    }
+    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);
+      }
+      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': {
+      First++;
+      return legacyParse<parse_unresolved_name>();
+    }
+    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':

       if (Cond && LHS && RHS)
         return make<ConditionalExpr>(Cond, LHS, RHS);
     }
     return nullptr;
   case 'r':
     switch (First[1]) {
     case 'c': {
       First += 2;
-      Node *T = legacyParse<parse_type>();
+      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(">>=");
     }
     return nullptr;
   case 's':
     switch (First[1]) {
     case 'c': {
       First += 2;
-      Node *T = legacyParse<parse_type>();
+      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 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, ")");
     }
     case 'z': {
       First += 2;
       Node *Ex = parseExpr();
       if (Ex == nullptr)

       First += 2;
       Node *Ex = parseExpr();
       if (Ex == nullptr)
         return Ex;
       return make<EnclosingExpr>("typeid (", Ex, ")");
     }
     case 'i': {
       First += 2;
-      Node *Ty = legacyParse<parse_type>();
+      Node *Ty = parseType();
       if (Ty == nullptr)
         return Ty;
       return make<EnclosingExpr>("typeid(", Ty, ")");
     }
     case 'r':
       First += 2;
       return make<NameType>("throw");
     case 'w': {

             case 'i':
                 db.Names.push_back(db.make<SpecialSubstitution>(SpecialSubKind::istream));
                 first += 2;
                 break;
             case 'o':
                 db.Names.push_back(db.make<SpecialSubstitution>(SpecialSubKind::ostream));
                 first += 2;
                 break;
-            case 'd':
-                db.Names.push_back(db.make<SpecialSubstitution>(SpecialSubKind::iostream));
-                first += 2;
-                break;
-            case '_':
-                if (!db.Subs.empty())
-                {
-                    db.Names.push_back(db.Subs[0]);
-                    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())
-                    {
-                        db.Names.push_back(db.Subs[sub]);
-                        first = t+1;
-                    }
-                }
-                break;
-            }
-        }
-    }
-    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
-
-const char*
-parse_builtin_type(const char* first, const char* last, Db& db)
-{
-    if (first != last)
-    {
-        switch (*first)
-        {
-        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"));
-            ++first;
-            break;
-        case 'c':
-            db.Names.push_back(db.make<NameType>("char"));
-            ++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<SpecialSubstitution>(SpecialSubKind::iostream));
+                first += 2;
+                break;
+            case '_':
+                if (!db.Subs.empty())
                 {
-                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"));
+                    db.Names.push_back(db.Subs[0]);
                     first += 2;
-                    break;
                 }
+                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())
+                    {
+                        db.Names.push_back(db.Subs[sub]);
+                        first = t+1;
+                    }
+                }
+                break;
             }
-            break;
         }
     }
     return first;
 }
 
 // <CV-Qualifiers> ::= [r] [V] [K]
 
 const char*

                 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();
-                    db.Names.pop_back();
-                    db.Names.back() = db.make<NameWithTemplateArgs>(
-                        db.Names.back(), 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();
-                    db.Names.pop_back();
-                    db.Names.back() =
-                        db.make<QualifiedName>(db.Names.back(), 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();
-                db.Names.pop_back();
-                db.Names.back() =
-                    db.make<QualifiedName>(db.Names.back(), 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();
-                        db.Names.pop_back();
-                        db.Names.back() =
-                            db.make<NameWithTemplateArgs>(
-                                db.Names.back(), 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();
-                    db.Names.pop_back();
-                    db.Names.back() =
-                        db.make<QualifiedName>(db.Names.back(), 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() =
-                            db.make<GlobalQualifiedName>(
-                                db.Names.back());
-                    }
-                    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();
-                        db.Names.pop_back();
-                        db.Names.back() = db.make<QualifiedName>(
-                            db.Names.back(), 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();
-                    db.Names.pop_back();
-                    db.Names.back() =
-                        db.make<QualifiedName>(db.Names.back(), s);
-                    first = t1;
-                }
-            }
-        }
-    }
-    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())
+                    if (db.Names.size() < 2)
                         return first;
-                    db.Names.back() =
-                        db.make<ArrayType>(db.Names.back(),
-                                            StringView(first + 1, t));
-                    first = t2;
+                    auto args = db.Names.back();
+                    db.Names.pop_back();
+                    db.Names.back() = db.make<NameWithTemplateArgs>(
+                        db.Names.back(), args);
+                    t = t1;
+                    if (t == last)
+                    {
+                        db.Names.pop_back();
+                        return first;
+                    }
                 }
-            }
-        }
-        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)
+                while (*t != 'E')
                 {
-                    if (db.Names.size() < 2)
+                    t1 = parse_unresolved_qualifier_level(t, last, db);
+                    if (t1 == t || t1 == last || db.Names.size() < 2)
                         return first;
-                    auto base_type = std::move(db.Names.back());
+                    auto s = 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;
+                        db.make<QualifiedName>(db.Names.back(), s);
+                    t = t1;
                 }
-            }
-        }
-    }
-    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')
+                ++t;
+                t1 = parse_base_unresolved_name(t, last, db);
+                if (t1 == t)
                 {
-                    if (db.Names.empty())
-                        return first;
-                    db.Names.back() = db.make<EnclosingExpr>(
-                        "decltype(", db.Names.back(), ")");
-                    first = t+1;
+                    if (!db.Names.empty())
+                        db.Names.pop_back();
+                    return first;
                 }
+                if (db.Names.size() < 2)
+                    return first;
+                auto s = db.Names.back();
+                db.Names.pop_back();
+                db.Names.back() =
+                    db.make<QualifiedName>(db.Names.back(), s);
+                first = t1;
             }
-            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)
+            else
             {
-                if (*t != 'p')
+                t += 2;
+                const char* t1 = parse_unresolved_type(t, last, db);
+                if (t1 != t)
                 {
-                    const char* t1 = parse_type(t, last, db);
+                    t = t1;
+                    t1 = parse_template_args(t, last, db);
                     if (t1 != t)
                     {
-                        if (db.Names.empty())
+                        if (db.Names.size() < 2)
                             return first;
+                        auto args = db.Names.back();
+                        db.Names.pop_back();
                         db.Names.back() =
-                            db.make<VectorType>(db.Names.back(),
-                                                 StringView(num, num + sz));
-                        first = t1;
+                            db.make<NameWithTemplateArgs>(
+                                db.Names.back(), args);
+                        t = t1;
                     }
-                }
-                else
+                    t1 = parse_base_unresolved_name(t, last, db);
+                    if (t1 == t)
                     {
-                    ++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())
+                        if (!db.Names.empty())
+                            db.Names.pop_back();
+                        return first;
+                    }
+                    if (db.Names.size() < 2)
                         return first;
-                    num = db.Names.back();
+                    auto s = db.Names.back();
                     db.Names.pop_back();
-                    t1 = t;
+                    db.Names.back() =
+                        db.make<QualifiedName>(db.Names.back(), s);
+                    first = t1;
                 }
-            }
-            if (t1 != last && *t1 == '_' && ++t1 != last)
-            {
-                const char* t = parse_type(t1, last, db);
-                if (t != t1)
+                else
                 {
-                    if (db.Names.empty())
+                    t1 = parse_unresolved_qualifier_level(t, last, db);
+                    if (t1 == t || t1 == last)
                         return first;
-                    if (num)
-                        db.Names.back() =
-                            db.make<VectorType>(db.Names.back(), num);
-                    else
+                    t = t1;
+                    if (global)
+                    {
+                        if (db.Names.empty())
+                            return first;
                         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)
+                            db.make<GlobalQualifiedName>(
+                                db.Names.back());
+                    }
+                    while (*t != 'E')
                     {
-                        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;
+                        t1 = parse_unresolved_qualifier_level(t, last, db);
+                        if (t1 == t || t1 == last || db.Names.size() < 2)
+                            return first;
+                        auto s = db.Names.back();
+                        db.Names.pop_back();
+                        db.Names.back() = db.make<QualifiedName>(
+                            db.Names.back(), s);
+                        t = t1;
                     }
-                }
-              }
-                break;
-            default:
-              {
-                const char* t = parse_builtin_type(first, last, db);
-                if (t != first)
-                {
-                    first = t;
-                }
-                else
-                {
-                    switch (*first)
+                    ++t;
+                    t1 = parse_base_unresolved_name(t, last, db);
+                    if (t1 == t)
                     {
-                    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;
+                        if (!db.Names.empty())
+                            db.Names.pop_back();
+                        return first;
                     }
-              }
-                break;
+                    if (db.Names.size() < 2)
+                        return first;
+                    auto s = db.Names.back();
+                    db.Names.pop_back();
+                    db.Names.back() =
+                        db.make<QualifiedName>(db.Names.back(), s);
+                    first = t1;
+                }
             }
         }
     }
     return first;
 }
 
 //   <operator-name>
 //                   ::= aa    # &&            

test/test_demangle.pass.cpp

     {"_ZN1SC2B8ctor_tagEv", "S::S[abi:ctor_tag]()"},
     {"_ZplB4MERP1SS_", "operator+[abi:MERP](S, S)"},
 
     {"_Z1fIJifcEEvDp5unaryIT_E", "void f<int, float, char>(unary<int>, unary<float>, unary<char>)"},
     {"_Z1fIJEJiEEvDpT_DpT0_", "void f<int>(int)"},
     {"_Z1fIJicEEvDp7MuncherIAstT__S1_E", "void f<int, char>(Muncher<int [sizeof (int)]>, Muncher<char [sizeof (char)]>)"},
     {"_ZN1SIJifcEE1fIJdjEEEiDp4MerpIJifcT_EE", "int S<int, float, char>::f<double, unsigned int>(Merp<int, float, char, double>, Merp<int, float, char, unsigned int>)"},
     {"_Z1pIJicEEiDp4MerpIXsZT_EJT_EE", "int p<int, char>(Merp<sizeof...(int, char), int>, Merp<sizeof...(int, char), char>)"},
+
+    // Multiple qualifiers on the same type should all get the same entry in the substitution table.
+    {"_Z1fPU3AS1KiS0_", "f(int const AS1*, int const AS1*)"}
 };
 
 const unsigned N = sizeof(cases) / sizeof(cases[0]);
 
 struct FPLiteralCase {
     const char *mangled;
     // There are four possible demanglings of a given float.
     std::string expecting[4];