Factor Node creation out of the demangler. No functionality change intended.

[rsmith]

Summary

This is a prerequisite for planned extensions to the demangler.

[erik.pilkington]

LGTM, don't forget to also commit this to libcxxabi!

[rsmith]

Committed as LLVM rL339944, libc++abi rCXXA339952.

lib/Demangle/ItaniumDemangle.cpp

public:
   void clear() { Last = First; }
 
   ~PODSmallVector() {
     if (!isInline())
       std::free(First);
   }
 };
 
+class DefaultAllocator {
+  BumpPointerAllocator Alloc;
+
+public:
+  void reset() { Alloc.reset(); }
+
+  template<typename T, typename ...Args> T *makeNode(Args &&...args) {
+    return new (Alloc.allocate(sizeof(T)))
+        T(std::forward<Args>(args)...);
+  }
+
+  void *allocateNodeArray(size_t sz) {
+    return Alloc.allocate(sizeof(Node *) * sz);
+  }
+};
+
+template<typename Alloc = DefaultAllocator>
 struct Db {
   const char *First;
   const char *Last;
 
   // Name stack, this is used by the parser to hold temporary names that were
   // parsed. The parser collapses multiple names into new nodes to construct
   // the AST. Once the parser is finished, names.size() == 1.
   PODSmallVector<Node *, 32> Names;
struct Db {
 
   void (*TypeCallback)(void *, const char *) = nullptr;
   void *TypeCallbackContext = nullptr;
 
   bool TryToParseTemplateArgs = true;
   bool PermitForwardTemplateReferences = false;
   bool ParsingLambdaParams = false;
 
-  BumpPointerAllocator ASTAllocator;
+  Alloc ASTAllocator;
 
   Db(const char *First_, const char *Last_) : First(First_), Last(Last_) {}
 
   void reset(const char *First_, const char *Last_) {
     First = First_;
     Last = Last_;
     Names.clear();
     Subs.clear();
     TemplateParams.clear();
     ParsingLambdaParams = false;
     TryToParseTemplateArgs = true;
     PermitForwardTemplateReferences = false;
     ASTAllocator.reset();
   }
 
   template <class T, class... Args> T *make(Args &&... args) {
-    return new (ASTAllocator.allocate(sizeof(T)))
-        T(std::forward<Args>(args)...);
+    return ASTAllocator.template makeNode<T>(std::forward<Args>(args)...);
   }
 
   template <class It> NodeArray makeNodeArray(It begin, It end) {
     size_t sz = static_cast<size_t>(end - begin);
-    void *mem = ASTAllocator.allocate(sizeof(Node *) * sz);
+    void *mem = ASTAllocator.allocateNodeArray(sz);
     Node **data = new (mem) Node *[sz];
     std::copy(begin, end, data);
     return NodeArray(data, sz);
   }
 
   NodeArray popTrailingNodeArray(size_t FromPosition) {
     assert(FromPosition <= Names.size());
     NodeArray res =

 
 // <name> ::= <nested-name> // N
 //        ::= <local-name> # See Scope Encoding below  // Z
 //        ::= <unscoped-template-name> <template-args>
 //        ::= <unscoped-name>
 //
 // <unscoped-template-name> ::= <unscoped-name>
 //                          ::= <substitution>
-Node *Db::parseName(NameState *State) {
+template<typename Alloc> Node *Db<Alloc>::parseName(NameState *State) {
   consumeIf('L'); // extension
 
   if (look() == 'N')
     return parseNestedName(State);
   if (look() == 'Z')
     return parseLocalName(State);
 
   //        ::= <unscoped-template-name> <template-args>
template<typename Alloc> Node *Db<Alloc>::parseName(NameState *State) {
   }
   //        ::= <unscoped-name>
   return N;
 }
 
 // <local-name> := Z <function encoding> E <entity name> [<discriminator>]
 //              := Z <function encoding> E s [<discriminator>]
 //              := Z <function encoding> Ed [ <parameter number> ] _ <entity name>
-Node *Db::parseLocalName(NameState *State) {
+template<typename Alloc> Node *Db<Alloc>::parseLocalName(NameState *State) {
   if (!consumeIf('Z'))
     return nullptr;
   Node *Encoding = parseEncoding();
   if (Encoding == nullptr || !consumeIf('E'))
     return nullptr;
 
   if (consumeIf('s')) {
     First = parse_discriminator(First, Last);
if (Entity == nullptr)
     return nullptr;
   First = parse_discriminator(First, Last);
   return make<LocalName>(Encoding, Entity);
 }
 
 // <unscoped-name> ::= <unqualified-name>
 //                 ::= St <unqualified-name>   # ::std::
 // extension       ::= StL<unqualified-name>
-Node *Db::parseUnscopedName(NameState *State) {
+template<typename Alloc> Node *Db<Alloc>::parseUnscopedName(NameState *State) {
  if (consumeIf("StL") || consumeIf("St")) {
    Node *R = parseUnqualifiedName(State);
    if (R == nullptr)
      return nullptr;
    return make<StdQualifiedName>(R);
  }
  return parseUnqualifiedName(State);
 }
 
 // <unqualified-name> ::= <operator-name> [abi-tags]
 //                    ::= <ctor-dtor-name>
 //                    ::= <source-name>
 //                    ::= <unnamed-type-name>
 //                    ::= DC <source-name>+ E      # structured binding declaration
-Node *Db::parseUnqualifiedName(NameState *State) {
+template<typename Alloc>
+Node *Db<Alloc>::parseUnqualifiedName(NameState *State) {
   // <ctor-dtor-name>s are special-cased in parseNestedName().
   Node *Result;
   if (look() == 'U')
     Result = parseUnnamedTypeName(State);
   else if (look() >= '1' && look() <= '9')
     Result = parseSourceName(State);
   else if (consumeIf("DC")) {
     size_t BindingsBegin = Names.size();
     do {
       Node *Binding = parseSourceName(State);
       if (Binding == nullptr)
         return nullptr;
       Names.push_back(Binding);
     } while (!consumeIf('E'));
     Result = make<StructuredBindingName>(popTrailingNodeArray(BindingsBegin));
   } else
     Result = parseOperatorName(State);
   if (Result != nullptr)
     Result = parseAbiTags(Result);
   return Result;
 }
 
 // <unnamed-type-name> ::= Ut [<nonnegative number>] _
 //                     ::= <closure-type-name>
 //
 // <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
 //
 // <lambda-sig> ::= <parameter type>+  # Parameter types or "v" if the lambda has no parameters
-Node *Db::parseUnnamedTypeName(NameState *) {
+template<typename Alloc> Node *Db<Alloc>::parseUnnamedTypeName(NameState *) {
   if (consumeIf("Ut")) {
     StringView Count = parseNumber();
     if (!consumeIf('_'))
       return nullptr;
     return make<UnnamedTypeName>(Count);
   }
   if (consumeIf("Ul")) {
     NodeArray Params;
if (consumeIf("Ul")) {
     if (!consumeIf('_'))
       return nullptr;
     return make<ClosureTypeName>(Params, Count);
   }
   return nullptr;
 }
 
 // <source-name> ::= <positive length number> <identifier>
-Node *Db::parseSourceName(NameState *) {
+template<typename Alloc> Node *Db<Alloc>::parseSourceName(NameState *) {
   size_t Length = 0;
   if (parsePositiveInteger(&Length))
     return nullptr;
   if (numLeft() < Length || Length == 0)
     return nullptr;
   StringView Name(First, First + Length);
   First += Length;
   if (Name.startsWith("_GLOBAL__N"))

 //                   ::= pt    # ->
 //                   ::= qu    # ?
 //                   ::= rm    # %
 //                   ::= rM    # %=
 //                   ::= rs    # >>
 //                   ::= rS    # >>=
 //                   ::= ss    # <=> C++2a
 //                   ::= v <digit> <source-name>        # vendor extended operator
-Node *Db::parseOperatorName(NameState *State) {
+template<typename Alloc> Node *Db<Alloc>::parseOperatorName(NameState *State) {
   switch (look()) {
   case 'a':
     switch (look(1)) {
     case 'a':
       First += 2;
       return make<NameType>("operator&&");
     case 'd':
     case 'n':

 // <ctor-dtor-name> ::= C1  # complete object constructor
 //                  ::= C2  # base object constructor
 //                  ::= C3  # complete object allocating constructor
 //   extension      ::= C5    # ?
 //                  ::= D0  # deleting destructor
 //                  ::= D1  # complete object destructor
 //                  ::= D2  # base object destructor
 //   extension      ::= D5    # ?
-Node *Db::parseCtorDtorName(Node *&SoFar, NameState *State) {
+template<typename Alloc>
+Node *Db<Alloc>::parseCtorDtorName(Node *&SoFar, NameState *State) {
   if (SoFar->K == Node::KSpecialSubstitution) {
     auto SSK = static_cast<SpecialSubstitution *>(SoFar)->SSK;
     switch (SSK) {
     case SpecialSubKind::string:
     case SpecialSubKind::istream:
     case SpecialSubKind::ostream:
     case SpecialSubKind::iostream:
       SoFar = make<ExpandedSpecialSubstitution>(SSK);

 //          ::= <prefix> <data-member-prefix>
 //  extension ::= L
 //
 // <data-member-prefix> := <member source-name> [<template-args>] M
 //
 // <template-prefix> ::= <prefix> <template unqualified-name>
 //                   ::= <template-param>
 //                   ::= <substitution>
-Node *Db::parseNestedName(NameState *State) {
+template<typename Alloc> Node *Db<Alloc>::parseNestedName(NameState *State) {
   if (!consumeIf('N'))
     return nullptr;
 
   Qualifiers CVTmp = parseCVQualifiers();
   if (State) State->CVQualifiers = CVTmp;
 
   if (consumeIf('O')) {
     if (State) State->ReferenceQualifier = FrefQualRValue;
template<typename Alloc> Node *Db<Alloc>::parseNestedName(NameState *State) {
   if (SoFar == nullptr || Subs.empty())
     return nullptr;
 
   Subs.pop_back();
   return SoFar;
 }
 
 // <simple-id> ::= <source-name> [ <template-args> ]
-Node *Db::parseSimpleId() {
+template<typename Alloc> Node *Db<Alloc>::parseSimpleId() {
   Node *SN = parseSourceName(/*NameState=*/nullptr);
   if (SN == nullptr)
     return nullptr;
   if (look() == 'I') {
     Node *TA = parseTemplateArgs();
     if (TA == nullptr)
       return nullptr;
     return make<NameWithTemplateArgs>(SN, TA);
   }
   return SN;
 }
 
 // <destructor-name> ::= <unresolved-type>  # e.g., ~T or ~decltype(f())
 //                   ::= <simple-id>        # e.g., ~A<2*N>
-Node *Db::parseDestructorName() {
+template<typename Alloc> Node *Db<Alloc>::parseDestructorName() {
   Node *Result;
   if (std::isdigit(look()))
     Result = parseSimpleId();
   else
     Result = parseUnresolvedType();
   if (Result == nullptr)
     return nullptr;
   return make<DtorName>(Result);
 }
 
 // <unresolved-type> ::= <template-param>
 //                   ::= <decltype>
 //                   ::= <substitution>
-Node *Db::parseUnresolvedType() {
+template<typename Alloc> Node *Db<Alloc>::parseUnresolvedType() {
   if (look() == 'T') {
     Node *TP = parseTemplateParam();
     if (TP == nullptr)
       return nullptr;
     Subs.push_back(TP);
     return TP;
   }
   if (look() == 'D') {
     Node *DT = parseDecltype();
     if (DT == nullptr)
       return nullptr;
     Subs.push_back(DT);
     return DT;
   }
   return parseSubstitution();
 }
 
 // <base-unresolved-name> ::= <simple-id>                                # unresolved name
 //          extension     ::= <operator-name>                            # unresolved operator-function-id
 //          extension     ::= <operator-name> <template-args>            # unresolved operator template-id
 //                        ::= on <operator-name>                         # unresolved operator-function-id
 //                        ::= on <operator-name> <template-args>         # unresolved operator template-id
 //                        ::= dn <destructor-name>                       # destructor or pseudo-destructor;
 //                                                                         # e.g. ~X or ~X<N-1>
-Node *Db::parseBaseUnresolvedName() {
+template<typename Alloc> Node *Db<Alloc>::parseBaseUnresolvedName() {
   if (std::isdigit(look()))
     return parseSimpleId();
 
   if (consumeIf("dn"))
     return parseDestructorName();
 
   consumeIf("on");
 

 //                   ::= [gs] sr <unresolved-qualifier-level>+ E <base-unresolved-name>
 //                                                                       # A::x, N::y, A<T>::z; "gs" means leading "::"
 //                   ::= sr <unresolved-type> <base-unresolved-name>     # T::x / decltype(p)::x
 //  extension        ::= sr <unresolved-type> <template-args> <base-unresolved-name>
 //                                                                       # T::N::x /decltype(p)::N::x
 //  (ignored)        ::= srN <unresolved-type>  <unresolved-qualifier-level>+ E <base-unresolved-name>
 //
 // <unresolved-qualifier-level> ::= <simple-id>
-Node *Db::parseUnresolvedName() {
+template<typename Alloc> Node *Db<Alloc>::parseUnresolvedName() {
   Node *SoFar = nullptr;
 
   // srN <unresolved-type> [<template-args>] <unresolved-qualifier-level>* E <base-unresolved-name>
   // srN <unresolved-type>                   <unresolved-qualifier-level>+ E <base-unresolved-name>
   if (consumeIf("srN")) {
     SoFar = parseUnresolvedType();
     if (SoFar == nullptr)
       return nullptr;
template<typename Alloc> Node *Db<Alloc>::parseUnresolvedName() {
   Node *Base = parseBaseUnresolvedName();
   if (Base == nullptr)
     return nullptr;
   return make<QualifiedName>(SoFar, Base);
 }
 
 // <abi-tags> ::= <abi-tag> [<abi-tags>]
 // <abi-tag> ::= B <source-name>
-Node *Db::parseAbiTags(Node *N) {
+template<typename Alloc> Node *Db<Alloc>::parseAbiTags(Node *N) {
   while (consumeIf('B')) {
     StringView SN = parseBareSourceName();
     if (SN.empty())
       return nullptr;
     N = make<AbiTagAttr>(N, SN);
   }
   return N;
 }
 
 // <number> ::= [n] <non-negative decimal integer>
-StringView Db::parseNumber(bool AllowNegative) {
+template<typename Alloc>
+StringView Db<Alloc>::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);
 }
 
 // <positive length number> ::= [0-9]*
-bool Db::parsePositiveInteger(size_t *Out) {
+template<typename Alloc> bool Db<Alloc>::parsePositiveInteger(size_t *Out) {
   *Out = 0;
   if (look() < '0' || look() > '9')
     return true;
   while (look() >= '0' && look() <= '9') {
     *Out *= 10;
     *Out += static_cast<size_t>(consume() - '0');
   }
   return false;
 }
 
-StringView Db::parseBareSourceName() {
+template<typename Alloc> StringView Db<Alloc>::parseBareSourceName() {
   size_t Int = 0;
   if (parsePositiveInteger(&Int) || numLeft() < Int)
     return StringView();
   StringView R(First, First + Int);
   First += Int;
   return R;
 }
 
 // <function-type> ::= [<CV-qualifiers>] [<exception-spec>] [Dx] F [Y] <bare-function-type> [<ref-qualifier>] E
 //
 // <exception-spec> ::= Do                # non-throwing exception-specification (e.g., noexcept, throw())
 //                  ::= DO <expression> E # computed (instantiation-dependent) noexcept
 //                  ::= Dw <type>+ E      # dynamic exception specification with instantiation-dependent types
 //
 // <ref-qualifier> ::= R                   # & ref-qualifier
 // <ref-qualifier> ::= O                   # && ref-qualifier
-Node *Db::parseFunctionType() {
+template<typename Alloc> Node *Db<Alloc>::parseFunctionType() {
   Qualifiers CVQuals = parseCVQualifiers();
 
   Node *ExceptionSpec = nullptr;
   if (consumeIf("Do")) {
     ExceptionSpec = make<NameType>("noexcept");
   } else if (consumeIf("DO")) {
     Node *E = parseExpr();
     if (E == nullptr || !consumeIf('E'))
return make<FunctionType>(ReturnType, Params, CVQuals,
                             ReferenceQualifier, ExceptionSpec);
 }
 
 // extension:
 // <vector-type>           ::= Dv <positive dimension number> _ <extended element type>
 //                         ::= Dv [<dimension expression>] _ <element type>
 // <extended element type> ::= <element type>
 //                         ::= p # AltiVec vector pixel
-Node *Db::parseVectorType() {
+template<typename Alloc> Node *Db<Alloc>::parseVectorType() {
   if (!consumeIf("Dv"))
     return nullptr;
   if (look() >= '1' && look() <= '9') {
     StringView DimensionNumber = parseNumber();
     if (!consumeIf('_'))
       return nullptr;
     if (consumeIf('p'))
       return make<VectorType>(DimensionNumber);
template<typename Alloc> Node *Db<Alloc>::parseVectorType() {
   Node *ElemType = parseType();
   if (!ElemType)
     return nullptr;
   return make<VectorType>(ElemType, StringView());
 }
 
 // <decltype>  ::= Dt <expression> E  # decltype of an id-expression or class member access (C++0x)
 //             ::= DT <expression> E  # decltype of an expression (C++0x)
-Node *Db::parseDecltype() {
+template<typename Alloc> Node *Db<Alloc>::parseDecltype() {
   if (!consumeIf('D'))
     return nullptr;
   if (!consumeIf('t') && !consumeIf('T'))
     return nullptr;
   Node *E = parseExpr();
   if (E == nullptr)
     return nullptr;
   if (!consumeIf('E'))
     return nullptr;
   return make<EnclosingExpr>("decltype(", E, ")");
 }
 
 // <array-type> ::= A <positive dimension number> _ <element type>
 //              ::= A [<dimension expression>] _ <element type>
-Node *Db::parseArrayType() {
+template<typename Alloc> Node *Db<Alloc>::parseArrayType() {
   if (!consumeIf('A'))
     return nullptr;
 
   if (std::isdigit(look())) {
     StringView Dimension = parseNumber();
     if (!consumeIf('_'))
       return nullptr;
     Node *Ty = parseType();
template<typename Alloc> Node *Db<Alloc>::parseArrayType() {
 
   Node *Ty = parseType();
   if (Ty == nullptr)
     return nullptr;
   return make<ArrayType>(Ty);
 }
 
 // <pointer-to-member-type> ::= M <class type> <member type>
-Node *Db::parsePointerToMemberType() {
+template<typename Alloc> Node *Db<Alloc>::parsePointerToMemberType() {
   if (!consumeIf('M'))
     return nullptr;
   Node *ClassType = parseType();
   if (ClassType == nullptr)
     return nullptr;
   Node *MemberType = parseType();
   if (MemberType == nullptr)
     return nullptr;
   return make<PointerToMemberType>(ClassType, MemberType);
 }
 
 // <class-enum-type> ::= <name>     # non-dependent type name, dependent type name, or dependent typename-specifier
 //                   ::= Ts <name>  # dependent elaborated type specifier using 'struct' or 'class'
 //                   ::= Tu <name>  # dependent elaborated type specifier using 'union'
 //                   ::= Te <name>  # dependent elaborated type specifier using 'enum'
-Node *Db::parseClassEnumType() {
+template<typename Alloc> Node *Db<Alloc>::parseClassEnumType() {
   StringView ElabSpef;
   if (consumeIf("Ts"))
     ElabSpef = "struct";
   else if (consumeIf("Tu"))
     ElabSpef = "union";
   else if (consumeIf("Te"))
     ElabSpef = "enum";
 
   Node *Name = parseName();
   if (Name == nullptr)
     return nullptr;
 
   if (!ElabSpef.empty())
     return make<ElaboratedTypeSpefType>(ElabSpef, Name);
 
   return Name;
 }
 
 // <qualified-type>     ::= <qualifiers> <type>
 // <qualifiers> ::= <extended-qualifier>* <CV-qualifiers>
 // <extended-qualifier> ::= U <source-name> [<template-args>] # vendor extended type qualifier
-Node *Db::parseQualifiedType() {
+template<typename Alloc> Node *Db<Alloc>::parseQualifiedType() {
   if (consumeIf('U')) {
     StringView Qual = parseBareSourceName();
     if (Qual.empty())
       return nullptr;
 
     // FIXME parse the optional <template-args> here!
 
     // extension            ::= U <objc-name> <objc-type>  # objc-type<identifier>

 //             ::= 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() {
+template<typename Alloc> Node *Db<Alloc>::parseType() {
   Node *Result = nullptr;
 
   if (TypeCallback != nullptr)
     TypeCallback(TypeCallbackContext, First);
 
   switch (look()) {
   //             ::= <qualified-type>
   case 'r':
template<typename Alloc> Node *Db<Alloc>::parseType() {
   // 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) {
+template<typename Alloc> Node *Db<Alloc>::parsePrefixExpr(StringView Kind) {
   Node *E = parseExpr();
   if (E == nullptr)
     return nullptr;
   return make<PrefixExpr>(Kind, E);
 }
 
-Node *Db::parseBinaryExpr(StringView Kind) {
+template<typename Alloc> Node *Db<Alloc>::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) {
+template<typename Alloc> Node *Db<Alloc>::parseIntegerLiteral(StringView Lit) {
   StringView Tmp = parseNumber(true);
   if (!Tmp.empty() && consumeIf('E'))
     return make<IntegerExpr>(Lit, Tmp);
   return nullptr;
 }
 
 // <CV-Qualifiers> ::= [r] [V] [K]
-Qualifiers Db::parseCVQualifiers() {
+template<typename Alloc> Qualifiers Db<Alloc>::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() {
+template<typename Alloc> Node *Db<Alloc>::parseFunctionParam() {
   if (consumeIf("fp")) {
     parseCVQualifiers();
     StringView Num = parseNumber();
     if (!consumeIf('_'))
       return nullptr;
     return make<FunctionParam>(Num);
   }
   if (consumeIf("fL")) {
template<typename Alloc> Node *Db<Alloc>::parseFunctionParam() {
   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() {
+template<typename Alloc> Node *Db<Alloc>::parseNewExpr() {
   bool Global = consumeIf("gs");
   bool IsArray = look(1) == 'a';
   if (!consumeIf("nw") && !consumeIf("na"))
     return nullptr;
   size_t Exprs = Names.size();
   while (!consumeIf('_')) {
     Node *Ex = parseExpr();
     if (Ex == nullptr)
if (consumeIf("pi")) {
     return make<NewExpr>(ExprList, Ty, Inits, Global, IsArray);
   } else if (!consumeIf('E'))
     return nullptr;
   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() {
+template<typename Alloc> Node *Db<Alloc>::parseConversionExpr() {
   if (!consumeIf("cv"))
     return nullptr;
   Node *Ty;
   {
     SwapAndRestore<bool> SaveTemp(TryToParseTemplateArgs, false);
     Ty = parseType();
   }
 

 }
 
 // <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() {
+template<typename Alloc> Node *Db<Alloc>::parseExprPrimary() {
   if (!consumeIf('L'))
     return nullptr;
   switch (look()) {
   case 'w':
     ++First;
     return parseIntegerLiteral("wchar_t");
   case 'b':
     if (consumeIf("b0E"))
template<typename Alloc> Node *Db<Alloc>::parseExprPrimary() {
   }
   }
 }
 
 // <braced-expression> ::= <expression>
 //                     ::= di <field source-name> <braced-expression>    # .name = expr
 //                     ::= dx <index expression> <braced-expression>     # [expr] = expr
 //                     ::= dX <range begin expression> <range end expression> <braced-expression>
-Node *Db::parseBracedExpr() {
+template<typename Alloc> Node *Db<Alloc>::parseBracedExpr() {
   if (look() == 'd') {
     switch (look(1)) {
     case 'i': {
       First += 2;
       Node *Field = parseSourceName(/*NameState=*/nullptr);
       if (Field == nullptr)
         return nullptr;
       Node *Init = parseBracedExpr();
template<typename Alloc> Node *Db<Alloc>::parseBracedExpr() {
   return parseExpr();
 }
 
 // (not yet in the spec)
 // <fold-expr> ::= fL <binary-operator-name> <expression> <expression>
 //             ::= fR <binary-operator-name> <expression> <expression>
 //             ::= fl <binary-operator-name> <expression>
 //             ::= fr <binary-operator-name> <expression>
-Node *Db::parseFoldExpr() {
+template<typename Alloc> Node *Db<Alloc>::parseFoldExpr() {
   if (!consumeIf('f'))
     return nullptr;
 
   char FoldKind = look();
   bool IsLeftFold, HasInitializer;
   HasInitializer = FoldKind == 'L' || FoldKind == 'R';
   if (FoldKind == 'l' || FoldKind == 'L')
     IsLeftFold = true;

 //              ::= <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() {
+template<typename Alloc> Node *Db<Alloc>::parseExpr() {
   bool Global = consumeIf("gs");
   if (numLeft() < 2)
     return nullptr;
 
   switch (*First) {
   case 'L':
     return parseExprPrimary();
   case 'T':

 // <call-offset> ::= h <nv-offset> _
 //               ::= v <v-offset> _
 //
 // <nv-offset> ::= <offset number>
 //               # non-virtual base override
 //
 // <v-offset>  ::= <offset number> _ <virtual offset number>
 //               # virtual base override, with vcall offset
-bool Db::parseCallOffset() {
+template<typename Alloc> bool Db<Alloc>::parseCallOffset() {
   // Just scan through the call offset, we never add this information into the
   // output.
   if (consumeIf('h'))
     return parseNumber(true).empty() || !consumeIf('_');
   if (consumeIf('v'))
     return parseNumber(true).empty() || !consumeIf('_') ||
            parseNumber(true).empty() || !consumeIf('_');
   return true;

 //                ::= GV <object name> # Guard variable for one-time initialization
 //                                     # No <type>
 //                ::= TW <object name> # Thread-local wrapper
 //                ::= TH <object name> # Thread-local initialization
 //                ::= GR <object name> _             # First temporary
 //                ::= GR <object name> <seq-id> _    # Subsequent temporaries
 //      extension ::= TC <first type> <number> _ <second type> # construction vtable for second-in-first
 //      extension ::= GR <object name> # reference temporary for object
-Node *Db::parseSpecialName() {
+template<typename Alloc> Node *Db<Alloc>::parseSpecialName() {
   switch (look()) {
   case 'T':
     switch (look(1)) {
     // TV <type>    # virtual table
     case 'V': {
       First += 2;
       Node *Ty = parseType();
       if (Ty == nullptr)
case 'G':
     }
   }
   return nullptr;
 }
 
 // <encoding> ::= <function name> <bare-function-type>
 //            ::= <data name>
 //            ::= <special-name>
-Node *Db::parseEncoding() {
+template<typename Alloc> Node *Db<Alloc>::parseEncoding() {
   if (look() == 'G' || look() == 'T')
     return parseSpecialName();
 
   auto IsEndOfEncoding = [&] {
     // The set of chars that can potentially follow an <encoding> (none of which
     // can start a <type>). Enumerating these allows us to avoid speculative
     // parsing.
     return numLeft() == 0 || look() == 'E' || look() == '.' || look() == '_';
#else
     static const size_t mangled_size = 20;  // May need to be adjusted to 16 or 24 on other platforms
 #endif
     static const size_t max_demangled_size = 40;
     static constexpr const char *spec = "%LaL";
 };
 
 constexpr const char *FloatData<long double>::spec;
 
-template <class Float> Node *Db::parseFloatingLiteral() {
+template<typename Alloc>
+template<class Float>
+Node *Db<Alloc>::parseFloatingLiteral() {
   const size_t N = FloatData<Float>::mangled_size;
   if (numLeft() <= N)
     return nullptr;
   StringView Data(First, First + N);
   for (char C : Data)
     if (!std::isxdigit(C))
       return nullptr;
   First += N;
   if (!consumeIf('E'))
     return nullptr;
   return make<FloatExpr<Float>>(Data);
 }
 
 // <seq-id> ::= <0-9A-Z>+
-bool Db::parseSeqId(size_t *Out) {
+template<typename Alloc> bool Db<Alloc>::parseSeqId(size_t *Out) {
   if (!(look() >= '0' && look() <= '9') &&
       !(look() >= 'A' && look() <= 'Z'))
     return true;
 
   size_t Id = 0;
   while (true) {
     if (look() >= '0' && look() <= '9') {
       Id *= 36;

 // <substitution> ::= Sa # ::std::allocator
 // <substitution> ::= Sb # ::std::basic_string
 // <substitution> ::= Ss # ::std::basic_string < char,
 //                                               ::std::char_traits<char>,
 //                                               ::std::allocator<char> >
 // <substitution> ::= Si # ::std::basic_istream<char,  std::char_traits<char> >
 // <substitution> ::= So # ::std::basic_ostream<char,  std::char_traits<char> >
 // <substitution> ::= Sd # ::std::basic_iostream<char, std::char_traits<char> >
-Node *Db::parseSubstitution() {
+template<typename Alloc> Node *Db<Alloc>::parseSubstitution() {
   if (!consumeIf('S'))
     return nullptr;
 
   if (std::islower(look())) {
     Node *SpecialSub;
     switch (look()) {
     case 'a':
       ++First;
template<typename Alloc> Node *Db<Alloc>::parseSubstitution() {
   ++Index;
   if (!consumeIf('_') || Index >= Subs.size())
     return nullptr;
   return Subs[Index];
 }
 
 // <template-param> ::= T_    # first template parameter
 //                  ::= T <parameter-2 non-negative number> _
-Node *Db::parseTemplateParam() {
+template<typename Alloc> Node *Db<Alloc>::parseTemplateParam() {
   if (!consumeIf('T'))
     return nullptr;
 
   size_t Index = 0;
   if (!consumeIf('_')) {
     if (parsePositiveInteger(&Index))
       return nullptr;
     ++Index;
template<typename Alloc> Node *Db<Alloc>::parseTemplateParam() {
   return TemplateParams[Index];
 }
 
 // <template-arg> ::= <type>                    # type or template
 //                ::= X <expression> E          # expression
 //                ::= <expr-primary>            # simple expressions
 //                ::= J <template-arg>* E       # argument pack
 //                ::= LZ <encoding> E           # extension
-Node *Db::parseTemplateArg() {
+template<typename Alloc> Node *Db<Alloc>::parseTemplateArg() {
   switch (look()) {
   case 'X': {
     ++First;
     Node *Arg = parseExpr();
     if (Arg == nullptr || !consumeIf('E'))
       return nullptr;
     return Arg;
   }
template<typename Alloc> Node *Db<Alloc>::parseTemplateArg() {
   }
   default:
     return parseType();
   }
 }
 
 // <template-args> ::= I <template-arg>* E
 //     extension, the abi says <template-arg>+
-Node *Db::parseTemplateArgs(bool TagTemplates) {
+template <typename Alloc>
+Node *Db<Alloc>::parseTemplateArgs(bool TagTemplates) {
   if (!consumeIf('I'))
     return nullptr;
 
   // <template-params> refer to the innermost <template-args>. Clear out any
   // outer args that we may have inserted into TemplateParams.
   if (TagTemplates)
     TemplateParams.clear();
 
parse_discriminator(const char* first, const char* last)
     return first;
 }
 
 // <mangled-name> ::= _Z <encoding>
 //                ::= <type>
 // extension      ::= ___Z <encoding> _block_invoke
 // extension      ::= ___Z <encoding> _block_invoke<decimal-digit>+
 // extension      ::= ___Z <encoding> _block_invoke_<decimal-digit>+
-Node *Db::parse() {
+template<typename Alloc> Node *Db<Alloc>::parse() {
   if (consumeIf("_Z")) {
     Node *Encoding = parseEncoding();
     if (Encoding == nullptr)
       return nullptr;
     if (look() == '.') {
       Encoding = make<DotSuffix>(Encoding, StringView(First, Last));
       First = Last;
     }
char *llvm::itaniumDemangle(const char *MangledName, char *Buf,
                             size_t *N, int *Status) {
   if (MangledName == nullptr || (Buf != nullptr && N == nullptr)) {
     if (Status)
       *Status = demangle_invalid_args;
     return nullptr;
   }
 
   int InternalStatus = demangle_success;
-  Db Parser(MangledName, MangledName + std::strlen(MangledName));
+  Db<> Parser(MangledName, MangledName + std::strlen(MangledName));
   OutputStream S;
 
   Node *AST = Parser.parse();
 
   if (AST == nullptr)
     InternalStatus = demangle_invalid_mangled_name;
   else if (initializeOutputStream(Buf, N, S, 1024))
     InternalStatus = demangle_memory_alloc_failure;
char *llvm::itaniumDemangle(const char *MangledName, char *Buf,
   if (Status)
     *Status = InternalStatus;
   return InternalStatus == demangle_success ? Buf : nullptr;
 }
 
 bool llvm::itaniumFindTypesInMangledName(const char *MangledName, void *Ctx,
                                          void (*Callback)(void *,
                                                           const char *)) {
-  Db Parser(MangledName, MangledName + std::strlen(MangledName));
+  Db<> Parser(MangledName, MangledName + std::strlen(MangledName));
   Parser.TypeCallback = Callback;
   Parser.TypeCallbackContext = Ctx;
   return Parser.parse() == nullptr;
 }
 
 namespace llvm {
 
 ItaniumPartialDemangler::ItaniumPartialDemangler()
-    : RootNode(nullptr), Context(new Db{nullptr, nullptr}) {}
+    : RootNode(nullptr), Context(new Db<>{nullptr, nullptr}) {}
 
 ItaniumPartialDemangler::~ItaniumPartialDemangler() {
-  delete static_cast<Db *>(Context);
+  delete static_cast<Db<> *>(Context);
 }
 
 ItaniumPartialDemangler::ItaniumPartialDemangler(
     ItaniumPartialDemangler &&Other)
     : RootNode(Other.RootNode), Context(Other.Context) {
   Other.Context = Other.RootNode = nullptr;
 }
 
 ItaniumPartialDemangler &ItaniumPartialDemangler::
 operator=(ItaniumPartialDemangler &&Other) {
   std::swap(RootNode, Other.RootNode);
   std::swap(Context, Other.Context);
   return *this;
 }
 
 // Demangle MangledName into an AST, storing it into this->RootNode.
 bool ItaniumPartialDemangler::partialDemangle(const char *MangledName) {
-  Db *Parser = static_cast<Db *>(Context);
+  Db<> *Parser = static_cast<Db<> *>(Context);
   size_t Len = std::strlen(MangledName);
   Parser->reset(MangledName, MangledName + Len);
   RootNode = Parser->parse();
   return RootNode == nullptr;
 }
 
 static char *printNode(Node *RootNode, char *Buf, size_t *N) {
   OutputStream S;
bool ItaniumPartialDemangler::isSpecialName() const {
   assert(RootNode != nullptr && "must call partialDemangle()");
   auto K = static_cast<Node *>(RootNode)->getKind();
   return K == Node::KSpecialName || K == Node::KCtorVtableSpecialName;
 }
 
 bool ItaniumPartialDemangler::isData() const {
   return !isFunction() && !isSpecialName();
 }
-}
+}  // namespace llvm