LCOV - code coverage report
Current view: top level - lib/Demangle - ItaniumDemangle.cpp (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 1234 2569 48.0 %
Date: 2018-07-13 00:08:38 Functions: 182 446 40.8 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===------------------------- ItaniumDemangle.cpp ------------------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is dual licensed under the MIT and the University of Illinois Open
       6             : // Source Licenses. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : 
      10             : // FIXME: (possibly) incomplete list of features that clang mangles that this
      11             : // file does not yet support:
      12             : //   - C++ modules TS
      13             : 
      14             : #include "llvm/Demangle/Demangle.h"
      15             : 
      16             : #include <algorithm>
      17             : #include <cassert>
      18             : #include <cctype>
      19             : #include <cstdio>
      20             : #include <cstdlib>
      21             : #include <cstring>
      22             : #include <numeric>
      23             : #include <vector>
      24             : 
      25             : #ifdef _MSC_VER
      26             : // snprintf is implemented in VS 2015
      27             : #if _MSC_VER < 1900
      28             : #define snprintf _snprintf_s
      29             : #endif
      30             : #endif
      31             : 
      32             : // A variety of feature test macros copied from include/llvm/Support/Compiler.h
      33             : #ifndef __has_feature
      34             : #define __has_feature(x) 0
      35             : #endif
      36             : 
      37             : #ifndef __has_cpp_attribute
      38             : #define __has_cpp_attribute(x) 0
      39             : #endif
      40             : 
      41             : #ifndef __has_attribute
      42             : #define __has_attribute(x) 0
      43             : #endif
      44             : 
      45             : #ifndef __has_builtin
      46             : #define __has_builtin(x) 0
      47             : #endif
      48             : 
      49             : #ifndef LLVM_GNUC_PREREQ
      50             : #if defined(__GNUC__) && defined(__GNUC_MINOR__) && defined(__GNUC_PATCHLEVEL__)
      51             : #define LLVM_GNUC_PREREQ(maj, min, patch)                                      \
      52             :   ((__GNUC__ << 20) + (__GNUC_MINOR__ << 10) + __GNUC_PATCHLEVEL__ >=          \
      53             :    ((maj) << 20) + ((min) << 10) + (patch))
      54             : #elif defined(__GNUC__) && defined(__GNUC_MINOR__)
      55             : #define LLVM_GNUC_PREREQ(maj, min, patch)                                      \
      56             :   ((__GNUC__ << 20) + (__GNUC_MINOR__ << 10) >= ((maj) << 20) + ((min) << 10))
      57             : #else
      58             : #define LLVM_GNUC_PREREQ(maj, min, patch) 0
      59             : #endif
      60             : #endif
      61             : 
      62             : #if __has_attribute(used) || LLVM_GNUC_PREREQ(3, 1, 0)
      63             : #define LLVM_ATTRIBUTE_USED __attribute__((__used__))
      64             : #else
      65             : #define LLVM_ATTRIBUTE_USED
      66             : #endif
      67             : 
      68             : #if __has_builtin(__builtin_unreachable) || LLVM_GNUC_PREREQ(4, 5, 0)
      69             : #define LLVM_BUILTIN_UNREACHABLE __builtin_unreachable()
      70             : #elif defined(_MSC_VER)
      71             : #define LLVM_BUILTIN_UNREACHABLE __assume(false)
      72             : #endif
      73             : 
      74             : #if __has_attribute(noinline) || LLVM_GNUC_PREREQ(3, 4, 0)
      75             : #define LLVM_ATTRIBUTE_NOINLINE __attribute__((noinline))
      76             : #elif defined(_MSC_VER)
      77             : #define LLVM_ATTRIBUTE_NOINLINE __declspec(noinline)
      78             : #else
      79             : #define LLVM_ATTRIBUTE_NOINLINE
      80             : #endif
      81             : 
      82             : #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
      83             : #define LLVM_DUMP_METHOD LLVM_ATTRIBUTE_NOINLINE LLVM_ATTRIBUTE_USED
      84             : #else
      85             : #define LLVM_DUMP_METHOD LLVM_ATTRIBUTE_NOINLINE
      86             : #endif
      87             : 
      88             : #if __cplusplus > 201402L && __has_cpp_attribute(fallthrough)
      89             : #define LLVM_FALLTHROUGH [[fallthrough]]
      90             : #elif __has_cpp_attribute(gnu::fallthrough)
      91             : #define LLVM_FALLTHROUGH [[gnu::fallthrough]]
      92             : #elif !__cplusplus
      93             : // Workaround for llvm.org/PR23435, since clang 3.6 and below emit a spurious
      94             : // error when __has_cpp_attribute is given a scoped attribute in C mode.
      95             : #define LLVM_FALLTHROUGH
      96             : #elif __has_cpp_attribute(clang::fallthrough)
      97             : #define LLVM_FALLTHROUGH [[clang::fallthrough]]
      98             : #else
      99             : #define LLVM_FALLTHROUGH
     100             : #endif
     101             : 
     102             : namespace {
     103             : 
     104             : class StringView {
     105             :   const char *First;
     106             :   const char *Last;
     107             : 
     108             : public:
     109             :   template <size_t N>
     110       65211 :   StringView(const char (&Str)[N]) : First(Str), Last(Str + N - 1) {}
     111       49943 :   StringView(const char *First_, const char *Last_) : First(First_), Last(Last_) {}
     112        5165 :   StringView() : First(nullptr), Last(nullptr) {}
     113             : 
     114             :   StringView substr(size_t From, size_t To) {
     115             :     if (To >= size())
     116             :       To = size() - 1;
     117             :     if (From >= size())
     118             :       From = size() - 1;
     119             :     return StringView(First + From, First + To);
     120             :   }
     121             : 
     122             :   StringView dropFront(size_t N) const {
     123           0 :     if (N >= size())
     124           0 :       N = size() - 1;
     125           0 :     return StringView(First + N, Last);
     126             :   }
     127             : 
     128       49943 :   bool startsWith(StringView Str) const {
     129       49943 :     if (Str.size() > size())
     130             :       return false;
     131             :     return std::equal(Str.begin(), Str.end(), begin());
     132             :   }
     133             : 
     134         767 :   const char &operator[](size_t Idx) const { return *(begin() + Idx); }
     135             : 
     136             :   const char *begin() const { return First; }
     137             :   const char *end() const { return Last; }
     138      120710 :   size_t size() const { return static_cast<size_t>(Last - First); }
     139        4541 :   bool empty() const { return First == Last; }
     140             : };
     141             : 
     142           0 : bool operator==(const StringView &LHS, const StringView &RHS) {
     143           0 :   return LHS.size() == RHS.size() &&
     144           0 :          std::equal(LHS.begin(), LHS.end(), RHS.begin());
     145             : }
     146             : 
     147             : // Stream that AST nodes write their string representation into after the AST
     148             : // has been parsed.
     149             : class OutputStream {
     150             :   char *Buffer;
     151             :   size_t CurrentPosition;
     152             :   size_t BufferCapacity;
     153             : 
     154             :   // Ensure there is at least n more positions in buffer.
     155       70683 :   void grow(size_t N) {
     156       70683 :     if (N + CurrentPosition >= BufferCapacity) {
     157          98 :       BufferCapacity *= 2;
     158          98 :       if (BufferCapacity < N + CurrentPosition)
     159           6 :         BufferCapacity = N + CurrentPosition;
     160          98 :       Buffer = static_cast<char *>(std::realloc(Buffer, BufferCapacity));
     161             :     }
     162       70683 :   }
     163             : 
     164             : public:
     165             :   OutputStream(char *StartBuf, size_t Size)
     166             :       : Buffer(StartBuf), CurrentPosition(0), BufferCapacity(Size) {}
     167        3945 :   OutputStream() = default;
     168             :   void reset(char *Buffer_, size_t BufferCapacity_) {
     169        1420 :     CurrentPosition = 0;
     170        1420 :     Buffer = Buffer_;
     171        1420 :     BufferCapacity = BufferCapacity_;
     172             :   }
     173             : 
     174             :   /// If a ParameterPackExpansion (or similar type) is encountered, the offset
     175             :   /// into the pack that we're currently printing.
     176             :   unsigned CurrentPackIndex = std::numeric_limits<unsigned>::max();
     177             :   unsigned CurrentPackMax = std::numeric_limits<unsigned>::max();
     178             : 
     179       69233 :   OutputStream &operator+=(StringView R) {
     180             :     size_t Size = R.size();
     181       69233 :     if (Size == 0)
     182             :       return *this;
     183       69223 :     grow(Size);
     184       69223 :     memmove(Buffer + CurrentPosition, R.begin(), Size);
     185       69223 :     CurrentPosition += Size;
     186       69223 :     return *this;
     187             :   }
     188             : 
     189             :   OutputStream &operator+=(char C) {
     190        1460 :     grow(1);
     191        1460 :     Buffer[CurrentPosition++] = C;
     192             :     return *this;
     193             :   }
     194             : 
     195             :   size_t getCurrentPosition() const { return CurrentPosition; }
     196         160 :   void setCurrentPosition(size_t NewPos) { CurrentPosition = NewPos; }
     197             : 
     198             :   char back() const {
     199        8098 :     return CurrentPosition ? Buffer[CurrentPosition - 1] : '\0';
     200             :   }
     201             : 
     202             :   bool empty() const { return CurrentPosition == 0; }
     203             : 
     204             :   char *getBuffer() { return Buffer; }
     205             :   char *getBufferEnd() { return Buffer + CurrentPosition - 1; }
     206             :   size_t getBufferCapacity() { return BufferCapacity; }
     207             : };
     208             : 
     209             : template <class T>
     210             : class SwapAndRestore {
     211             :   T &Restore;
     212             :   T OriginalValue;
     213             : public:
     214             :   SwapAndRestore(T& Restore_, T NewVal)
     215         499 :       : Restore(Restore_), OriginalValue(Restore) {
     216         512 :     Restore = std::move(NewVal);
     217             :   }
     218         230 :   ~SwapAndRestore() { Restore = std::move(OriginalValue); }
     219             : 
     220             :   SwapAndRestore(const SwapAndRestore &) = delete;
     221             :   SwapAndRestore &operator=(const SwapAndRestore &) = delete;
     222             : };
     223             : 
     224             : // Base class of all AST nodes. The AST is built by the parser, then is
     225             : // traversed by the printLeft/Right functions to produce a demangled string.
     226             : class Node {
     227             : public:
     228             :   enum Kind : unsigned char {
     229             :     KNodeArrayNode,
     230             :     KDotSuffix,
     231             :     KVendorExtQualType,
     232             :     KQualType,
     233             :     KConversionOperatorType,
     234             :     KPostfixQualifiedType,
     235             :     KElaboratedTypeSpefType,
     236             :     KNameType,
     237             :     KAbiTagAttr,
     238             :     KEnableIfAttr,
     239             :     KObjCProtoName,
     240             :     KPointerType,
     241             :     KLValueReferenceType,
     242             :     KRValueReferenceType,
     243             :     KPointerToMemberType,
     244             :     KArrayType,
     245             :     KFunctionType,
     246             :     KNoexceptSpec,
     247             :     KDynamicExceptionSpec,
     248             :     KFunctionEncoding,
     249             :     KLiteralOperator,
     250             :     KSpecialName,
     251             :     KCtorVtableSpecialName,
     252             :     KQualifiedName,
     253             :     KNestedName,
     254             :     KLocalName,
     255             :     KVectorType,
     256             :     KParameterPack,
     257             :     KTemplateArgumentPack,
     258             :     KParameterPackExpansion,
     259             :     KTemplateArgs,
     260             :     KForwardTemplateReference,
     261             :     KNameWithTemplateArgs,
     262             :     KGlobalQualifiedName,
     263             :     KStdQualifiedName,
     264             :     KExpandedSpecialSubstitution,
     265             :     KSpecialSubstitution,
     266             :     KCtorDtorName,
     267             :     KDtorName,
     268             :     KUnnamedTypeName,
     269             :     KClosureTypeName,
     270             :     KStructuredBindingName,
     271             :     KExpr,
     272             :     KBracedExpr,
     273             :     KBracedRangeExpr,
     274             :   };
     275             : 
     276             :   Kind K;
     277             : 
     278             :   /// Three-way bool to track a cached value. Unknown is possible if this node
     279             :   /// has an unexpanded parameter pack below it that may affect this cache.
     280             :   enum class Cache : unsigned char { Yes, No, Unknown, };
     281             : 
     282             :   /// Tracks if this node has a component on its right side, in which case we
     283             :   /// need to call printRight.
     284             :   Cache RHSComponentCache;
     285             : 
     286             :   /// Track if this node is a (possibly qualified) array type. This can affect
     287             :   /// how we format the output string.
     288             :   Cache ArrayCache;
     289             : 
     290             :   /// Track if this node is a (possibly qualified) function type. This can
     291             :   /// affect how we format the output string.
     292             :   Cache FunctionCache;
     293             : 
     294             :   Node(Kind K_, Cache RHSComponentCache_ = Cache::No,
     295             :        Cache ArrayCache_ = Cache::No, Cache FunctionCache_ = Cache::No)
     296       50748 :       : K(K_), RHSComponentCache(RHSComponentCache_), ArrayCache(ArrayCache_),
     297       50748 :         FunctionCache(FunctionCache_) {}
     298             : 
     299             :   bool hasRHSComponent(OutputStream &S) const {
     300         280 :     if (RHSComponentCache != Cache::Unknown)
     301         280 :       return RHSComponentCache == Cache::Yes;
     302           0 :     return hasRHSComponentSlow(S);
     303             :   }
     304             : 
     305             :   bool hasArray(OutputStream &S) const {
     306        5631 :     if (ArrayCache != Cache::Unknown)
     307        5619 :       return ArrayCache == Cache::Yes;
     308          12 :     return hasArraySlow(S);
     309             :   }
     310             : 
     311             :   bool hasFunction(OutputStream &S) const {
     312        3104 :     if (FunctionCache != Cache::Unknown)
     313        3100 :       return FunctionCache == Cache::Yes;
     314           4 :     return hasFunctionSlow(S);
     315             :   }
     316             : 
     317             :   Kind getKind() const { return K; }
     318             : 
     319           0 :   virtual bool hasRHSComponentSlow(OutputStream &) const { return false; }
     320           0 :   virtual bool hasArraySlow(OutputStream &) const { return false; }
     321           0 :   virtual bool hasFunctionSlow(OutputStream &) const { return false; }
     322             : 
     323             :   void print(OutputStream &S) const {
     324       52057 :     printLeft(S);
     325       52057 :     if (RHSComponentCache != Cache::No)
     326        1751 :       printRight(S);
     327             :   }
     328             : 
     329             :   // Print the "left" side of this Node into OutputStream.
     330             :   virtual void printLeft(OutputStream &) const = 0;
     331             : 
     332             :   // Print the "right". This distinction is necessary to represent C++ types
     333             :   // that appear on the RHS of their subtype, such as arrays or functions.
     334             :   // Since most types don't have such a component, provide a default
     335             :   // implementation.
     336         717 :   virtual void printRight(OutputStream &) const {}
     337             : 
     338           0 :   virtual StringView getBaseName() const { return StringView(); }
     339             : 
     340             :   // Silence compiler warnings, this dtor will never be called.
     341             :   virtual ~Node() = default;
     342             : 
     343             : #ifndef NDEBUG
     344             :   LLVM_DUMP_METHOD void dump() const {
     345             :     char *Buffer = static_cast<char*>(std::malloc(1024));
     346             :     OutputStream S(Buffer, 1024);
     347             :     print(S);
     348             :     S += '\0';
     349             :     printf("Symbol dump for %p: %s\n", (const void*)this, S.getBuffer());
     350             :     std::free(S.getBuffer());
     351             :   }
     352             : #endif
     353             : };
     354             : 
     355             : class NodeArray {
     356             :   Node **Elements;
     357             :   size_t NumElements;
     358             : 
     359             : public:
     360        1496 :   NodeArray() : Elements(nullptr), NumElements(0) {}
     361             :   NodeArray(Node **Elements_, size_t NumElements_)
     362             :       : Elements(Elements_), NumElements(NumElements_) {}
     363             : 
     364             :   bool empty() const { return NumElements == 0; }
     365             :   size_t size() const { return NumElements; }
     366             : 
     367             :   Node **begin() const { return Elements; }
     368         307 :   Node **end() const { return Elements + NumElements; }
     369             : 
     370         437 :   Node *operator[](size_t Idx) const { return Elements[Idx]; }
     371             : 
     372       10528 :   void printWithComma(OutputStream &S) const {
     373             :     bool FirstElement = true;
     374       42858 :     for (size_t Idx = 0; Idx != NumElements; ++Idx) {
     375       16165 :       size_t BeforeComma = S.getCurrentPosition();
     376       16165 :       if (!FirstElement)
     377        6187 :         S += ", ";
     378       16165 :       size_t AfterComma = S.getCurrentPosition();
     379       16165 :       Elements[Idx]->print(S);
     380             : 
     381             :       // Elements[Idx] is an empty parameter pack expansion, we should erase the
     382             :       // comma we just printed.
     383       16290 :       if (AfterComma == S.getCurrentPosition()) {
     384             :         S.setCurrentPosition(BeforeComma);
     385         125 :         continue;
     386             :       }
     387             : 
     388             :       FirstElement = false;
     389             :     }
     390       10528 :   }
     391             : };
     392             : 
     393           0 : struct NodeArrayNode : Node {
     394             :   NodeArray Array;
     395           0 :   NodeArrayNode(NodeArray Array_) : Node(KNodeArrayNode), Array(Array_) {}
     396           0 :   void printLeft(OutputStream &S) const override {
     397           0 :     Array.printWithComma(S);
     398           0 :   }
     399             : };
     400             : 
     401           0 : class DotSuffix final : public Node {
     402             :   const Node *Prefix;
     403             :   const StringView Suffix;
     404             : 
     405             : public:
     406             :   DotSuffix(Node *Prefix_, StringView Suffix_)
     407           0 :       : Node(KDotSuffix), Prefix(Prefix_), Suffix(Suffix_) {}
     408             : 
     409           0 :   void printLeft(OutputStream &s) const override {
     410           0 :     Prefix->print(s);
     411           0 :     s += " (";
     412           0 :     s += Suffix;
     413           0 :     s += ")";
     414           0 :   }
     415             : };
     416             : 
     417           0 : class VendorExtQualType final : public Node {
     418             :   const Node *Ty;
     419             :   StringView Ext;
     420             : 
     421             : public:
     422             :   VendorExtQualType(Node *Ty_, StringView Ext_)
     423           0 :       : Node(KVendorExtQualType), Ty(Ty_), Ext(Ext_) {}
     424             : 
     425           0 :   void printLeft(OutputStream &S) const override {
     426           0 :     Ty->print(S);
     427           0 :     S += " ";
     428           0 :     S += Ext;
     429           0 :   }
     430             : };
     431             : 
     432             : enum FunctionRefQual : unsigned char {
     433             :   FrefQualNone,
     434             :   FrefQualLValue,
     435             :   FrefQualRValue,
     436             : };
     437             : 
     438             : enum Qualifiers {
     439             :   QualNone = 0,
     440             :   QualConst = 0x1,
     441             :   QualVolatile = 0x2,
     442             :   QualRestrict = 0x4,
     443             : };
     444             : 
     445             : void addQualifiers(Qualifiers &Q1, Qualifiers Q2) {
     446        1002 :   Q1 = static_cast<Qualifiers>(Q1 | Q2);
     447             : }
     448             : 
     449           0 : class QualType : public Node {
     450             : protected:
     451             :   const Qualifiers Quals;
     452             :   const Node *Child;
     453             : 
     454         934 :   void printQuals(OutputStream &S) const {
     455         934 :     if (Quals & QualConst)
     456         934 :       S += " const";
     457         934 :     if (Quals & QualVolatile)
     458           0 :       S += " volatile";
     459         934 :     if (Quals & QualRestrict)
     460           0 :       S += " restrict";
     461         934 :   }
     462             : 
     463             : public:
     464             :   QualType(Node *Child_, Qualifiers Quals_)
     465         892 :       : Node(KQualType, Child_->RHSComponentCache,
     466             :              Child_->ArrayCache, Child_->FunctionCache),
     467        1784 :         Quals(Quals_), Child(Child_) {}
     468             : 
     469           0 :   bool hasRHSComponentSlow(OutputStream &S) const override {
     470           0 :     return Child->hasRHSComponent(S);
     471             :   }
     472           0 :   bool hasArraySlow(OutputStream &S) const override {
     473           0 :     return Child->hasArray(S);
     474             :   }
     475           0 :   bool hasFunctionSlow(OutputStream &S) const override {
     476           0 :     return Child->hasFunction(S);
     477             :   }
     478             : 
     479         934 :   void printLeft(OutputStream &S) const override {
     480         934 :     Child->printLeft(S);
     481         934 :     printQuals(S);
     482         934 :   }
     483             : 
     484          46 :   void printRight(OutputStream &S) const override { Child->printRight(S); }
     485             : };
     486             : 
     487           0 : class ConversionOperatorType final : public Node {
     488             :   const Node *Ty;
     489             : 
     490             : public:
     491             :   ConversionOperatorType(Node *Ty_)
     492           2 :       : Node(KConversionOperatorType), Ty(Ty_) {}
     493             : 
     494           1 :   void printLeft(OutputStream &S) const override {
     495           1 :     S += "operator ";
     496           1 :     Ty->print(S);
     497           1 :   }
     498             : };
     499             : 
     500           0 : class PostfixQualifiedType final : public Node {
     501             :   const Node *Ty;
     502             :   const StringView Postfix;
     503             : 
     504             : public:
     505             :   PostfixQualifiedType(Node *Ty_, StringView Postfix_)
     506           0 :       : Node(KPostfixQualifiedType), Ty(Ty_), Postfix(Postfix_) {}
     507             : 
     508           0 :   void printLeft(OutputStream &s) const override {
     509           0 :     Ty->printLeft(s);
     510           0 :     s += Postfix;
     511           0 :   }
     512             : };
     513             : 
     514           0 : class NameType final : public Node {
     515             :   const StringView Name;
     516             : 
     517             : public:
     518       35864 :   NameType(StringView Name_) : Node(KNameType), Name(Name_) {}
     519             : 
     520             :   StringView getName() const { return Name; }
     521         247 :   StringView getBaseName() const override { return Name; }
     522             : 
     523       20709 :   void printLeft(OutputStream &s) const override { s += Name; }
     524             : };
     525             : 
     526           0 : class ElaboratedTypeSpefType : public Node {
     527             :   StringView Kind;
     528             :   Node *Child;
     529             : public:
     530             :   ElaboratedTypeSpefType(StringView Kind_, Node *Child_)
     531           0 :       : Node(KElaboratedTypeSpefType), Kind(Kind_), Child(Child_) {}
     532             : 
     533           0 :   void printLeft(OutputStream &S) const override {
     534           0 :     S += Kind;
     535             :     S += ' ';
     536           0 :     Child->print(S);
     537           0 :   }
     538             : };
     539             : 
     540           0 : struct AbiTagAttr : Node {
     541             :   Node *Base;
     542             :   StringView Tag;
     543             : 
     544             :   AbiTagAttr(Node* Base_, StringView Tag_)
     545           6 :       : Node(KAbiTagAttr, Base_->RHSComponentCache,
     546             :              Base_->ArrayCache, Base_->FunctionCache),
     547          12 :         Base(Base_), Tag(Tag_) {}
     548             : 
     549           3 :   void printLeft(OutputStream &S) const override {
     550           3 :     Base->printLeft(S);
     551           3 :     S += "[abi:";
     552           3 :     S += Tag;
     553           3 :     S += "]";
     554           3 :   }
     555             : };
     556             : 
     557           0 : class EnableIfAttr : public Node {
     558             :   NodeArray Conditions;
     559             : public:
     560             :   EnableIfAttr(NodeArray Conditions_)
     561           2 :       : Node(KEnableIfAttr), Conditions(Conditions_) {}
     562             : 
     563           0 :   void printLeft(OutputStream &S) const override {
     564           0 :     S += " [enable_if:";
     565           0 :     Conditions.printWithComma(S);
     566             :     S += ']';
     567           0 :   }
     568             : };
     569             : 
     570           0 : class ObjCProtoName : public Node {
     571             :   Node *Ty;
     572             :   StringView Protocol;
     573             : 
     574             :   friend class PointerType;
     575             : 
     576             : public:
     577             :   ObjCProtoName(Node *Ty_, StringView Protocol_)
     578           0 :       : Node(KObjCProtoName), Ty(Ty_), Protocol(Protocol_) {}
     579             : 
     580           0 :   bool isObjCObject() const {
     581           0 :     return Ty->getKind() == KNameType &&
     582           0 :            static_cast<NameType *>(Ty)->getName() == "objc_object";
     583             :   }
     584             : 
     585           0 :   void printLeft(OutputStream &S) const override {
     586           0 :     Ty->print(S);
     587           0 :     S += "<";
     588           0 :     S += Protocol;
     589           0 :     S += ">";
     590           0 :   }
     591             : };
     592             : 
     593           0 : class PointerType final : public Node {
     594             :   const Node *Pointee;
     595             : 
     596             : public:
     597             :   PointerType(Node *Pointee_)
     598        1191 :       : Node(KPointerType, Pointee_->RHSComponentCache),
     599        2382 :         Pointee(Pointee_) {}
     600             : 
     601           0 :   bool hasRHSComponentSlow(OutputStream &S) const override {
     602           0 :     return Pointee->hasRHSComponent(S);
     603             :   }
     604             : 
     605        1186 :   void printLeft(OutputStream &s) const override {
     606             :     // We rewrite objc_object<SomeProtocol>* into id<SomeProtocol>.
     607        1186 :     if (Pointee->getKind() != KObjCProtoName ||
     608           0 :         !static_cast<const ObjCProtoName *>(Pointee)->isObjCObject()) {
     609        1186 :       Pointee->printLeft(s);
     610        2372 :       if (Pointee->hasArray(s))
     611           1 :         s += " ";
     612        3557 :       if (Pointee->hasArray(s) || Pointee->hasFunction(s))
     613         313 :         s += "(";
     614        1186 :       s += "*";
     615             :     } else {
     616           0 :       const auto *objcProto = static_cast<const ObjCProtoName *>(Pointee);
     617           0 :       s += "id<";
     618           0 :       s += objcProto->Protocol;
     619           0 :       s += ">";
     620             :     }
     621        1186 :   }
     622             : 
     623         428 :   void printRight(OutputStream &s) const override {
     624         428 :     if (Pointee->getKind() != KObjCProtoName ||
     625           0 :         !static_cast<const ObjCProtoName *>(Pointee)->isObjCObject()) {
     626        1283 :       if (Pointee->hasArray(s) || Pointee->hasFunction(s))
     627         313 :         s += ")";
     628         428 :       Pointee->printRight(s);
     629             :     }
     630         428 :   }
     631             : };
     632             : 
     633           0 : class LValueReferenceType final : public Node {
     634             :   const Node *Pointee;
     635             : 
     636             : public:
     637             :   LValueReferenceType(Node *Pointee_)
     638        1016 :       : Node(KLValueReferenceType, Pointee_->RHSComponentCache),
     639        2032 :         Pointee(Pointee_) {}
     640             : 
     641           0 :   bool hasRHSComponentSlow(OutputStream &S) const override {
     642           0 :     return Pointee->hasRHSComponent(S);
     643             :   }
     644             : 
     645         832 :   void printLeft(OutputStream &s) const override {
     646         832 :     Pointee->printLeft(s);
     647        1664 :     if (Pointee->hasArray(s))
     648          39 :       s += " ";
     649        2457 :     if (Pointee->hasArray(s) || Pointee->hasFunction(s))
     650          95 :       s += "(&";
     651             :     else
     652         737 :       s += "&";
     653         832 :   }
     654         174 :   void printRight(OutputStream &s) const override {
     655         483 :     if (Pointee->hasArray(s) || Pointee->hasFunction(s))
     656          95 :       s += ")";
     657         174 :     Pointee->printRight(s);
     658         174 :   }
     659             : };
     660             : 
     661           0 : class RValueReferenceType final : public Node {
     662             :   const Node *Pointee;
     663             : 
     664             : public:
     665             :   RValueReferenceType(Node *Pointee_)
     666         339 :       : Node(KRValueReferenceType, Pointee_->RHSComponentCache),
     667         678 :         Pointee(Pointee_) {}
     668             : 
     669           0 :   bool hasRHSComponentSlow(OutputStream &S) const override {
     670           0 :     return Pointee->hasRHSComponent(S);
     671             :   }
     672             : 
     673         421 :   void printLeft(OutputStream &s) const override {
     674         421 :     Pointee->printLeft(s);
     675         842 :     if (Pointee->hasArray(s))
     676           0 :       s += " ";
     677        1263 :     if (Pointee->hasArray(s) || Pointee->hasFunction(s))
     678           0 :       s += "(&&";
     679             :     else
     680         421 :       s += "&&";
     681         421 :   }
     682             : 
     683         125 :   void printRight(OutputStream &s) const override {
     684         375 :     if (Pointee->hasArray(s) || Pointee->hasFunction(s))
     685           0 :       s += ")";
     686         125 :     Pointee->printRight(s);
     687         125 :   }
     688             : };
     689             : 
     690           0 : class PointerToMemberType final : public Node {
     691             :   const Node *ClassType;
     692             :   const Node *MemberType;
     693             : 
     694             : public:
     695             :   PointerToMemberType(Node *ClassType_, Node *MemberType_)
     696           7 :       : Node(KPointerToMemberType, MemberType_->RHSComponentCache),
     697          14 :         ClassType(ClassType_), MemberType(MemberType_) {}
     698             : 
     699           0 :   bool hasRHSComponentSlow(OutputStream &S) const override {
     700           0 :     return MemberType->hasRHSComponent(S);
     701             :   }
     702             : 
     703           7 :   void printLeft(OutputStream &s) const override {
     704           7 :     MemberType->printLeft(s);
     705          21 :     if (MemberType->hasArray(s) || MemberType->hasFunction(s))
     706           7 :       s += "(";
     707             :     else
     708           0 :       s += " ";
     709           7 :     ClassType->print(s);
     710           7 :     s += "::*";
     711           7 :   }
     712             : 
     713           7 :   void printRight(OutputStream &s) const override {
     714          21 :     if (MemberType->hasArray(s) || MemberType->hasFunction(s))
     715           7 :       s += ")";
     716           7 :     MemberType->printRight(s);
     717           7 :   }
     718             : };
     719             : 
     720             : class NodeOrString {
     721             :   const void *First;
     722             :   const void *Second;
     723             : 
     724             : public:
     725             :   /* implicit */ NodeOrString(StringView Str) {
     726             :     const char *FirstChar = Str.begin();
     727             :     const char *SecondChar = Str.end();
     728          18 :     if (SecondChar == nullptr) {
     729             :       assert(FirstChar == SecondChar);
     730           0 :       ++FirstChar, ++SecondChar;
     731             :     }
     732             :     First = static_cast<const void *>(FirstChar);
     733             :     Second = static_cast<const void *>(SecondChar);
     734             :   }
     735             : 
     736             :   /* implicit */ NodeOrString(Node *N)
     737             :       : First(static_cast<const void *>(N)), Second(nullptr) {}
     738           1 :   NodeOrString() : First(nullptr), Second(nullptr) {}
     739             : 
     740          40 :   bool isString() const { return Second && First; }
     741           1 :   bool isNode() const { return First && !Second; }
     742             :   bool isEmpty() const { return !First && !Second; }
     743             : 
     744             :   StringView asString() const {
     745             :     assert(isString());
     746           0 :     return StringView(static_cast<const char *>(First),
     747           0 :                       static_cast<const char *>(Second));
     748             :   }
     749             : 
     750             :   const Node *asNode() const {
     751             :     assert(isNode());
     752             :     return static_cast<const Node *>(First);
     753             :   }
     754             : };
     755             : 
     756           0 : class ArrayType final : public Node {
     757             :   Node *Base;
     758             :   NodeOrString Dimension;
     759             : 
     760             : public:
     761             :   ArrayType(Node *Base_, NodeOrString Dimension_)
     762          18 :       : Node(KArrayType,
     763             :              /*RHSComponentCache=*/Cache::Yes,
     764             :              /*ArrayCache=*/Cache::Yes),
     765          18 :         Base(Base_), Dimension(Dimension_) {}
     766             : 
     767             :   // Incomplete array type.
     768             :   ArrayType(Node *Base_)
     769           1 :       : Node(KArrayType,
     770             :              /*RHSComponentCache=*/Cache::Yes,
     771             :              /*ArrayCache=*/Cache::Yes),
     772           1 :         Base(Base_) {}
     773             : 
     774           0 :   bool hasRHSComponentSlow(OutputStream &) const override { return true; }
     775           0 :   bool hasArraySlow(OutputStream &) const override { return true; }
     776             : 
     777          40 :   void printLeft(OutputStream &S) const override { Base->printLeft(S); }
     778             : 
     779          40 :   void printRight(OutputStream &S) const override {
     780          80 :     if (S.back() != ']')
     781          40 :       S += " ";
     782          40 :     S += "[";
     783             :     if (Dimension.isString())
     784          39 :       S += Dimension.asString();
     785             :     else if (Dimension.isNode())
     786             :       Dimension.asNode()->print(S);
     787          40 :     S += "]";
     788          40 :     Base->printRight(S);
     789          40 :   }
     790             : };
     791             : 
     792           0 : class FunctionType final : public Node {
     793             :   Node *Ret;
     794             :   NodeArray Params;
     795             :   Qualifiers CVQuals;
     796             :   FunctionRefQual RefQual;
     797             :   Node *ExceptionSpec;
     798             : 
     799             : public:
     800             :   FunctionType(Node *Ret_, NodeArray Params_, Qualifiers CVQuals_,
     801             :                FunctionRefQual RefQual_, Node *ExceptionSpec_)
     802         279 :       : Node(KFunctionType,
     803             :              /*RHSComponentCache=*/Cache::Yes, /*ArrayCache=*/Cache::No,
     804             :              /*FunctionCache=*/Cache::Yes),
     805             :         Ret(Ret_), Params(Params_), CVQuals(CVQuals_), RefQual(RefQual_),
     806         279 :         ExceptionSpec(ExceptionSpec_) {}
     807             : 
     808           0 :   bool hasRHSComponentSlow(OutputStream &) const override { return true; }
     809           0 :   bool hasFunctionSlow(OutputStream &) const override { return true; }
     810             : 
     811             :   // Handle C++'s ... quirky decl grammar by using the left & right
     812             :   // distinction. Consider:
     813             :   //   int (*f(float))(char) {}
     814             :   // f is a function that takes a float and returns a pointer to a function
     815             :   // that takes a char and returns an int. If we're trying to print f, start
     816             :   // by printing out the return types's left, then print our parameters, then
     817             :   // finally print right of the return type.
     818         385 :   void printLeft(OutputStream &S) const override {
     819         385 :     Ret->printLeft(S);
     820         385 :     S += " ";
     821         385 :   }
     822             : 
     823         385 :   void printRight(OutputStream &S) const override {
     824         385 :     S += "(";
     825         385 :     Params.printWithComma(S);
     826         385 :     S += ")";
     827         385 :     Ret->printRight(S);
     828             : 
     829         385 :     if (CVQuals & QualConst)
     830           0 :       S += " const";
     831         385 :     if (CVQuals & QualVolatile)
     832           0 :       S += " volatile";
     833         385 :     if (CVQuals & QualRestrict)
     834           0 :       S += " restrict";
     835             : 
     836         385 :     if (RefQual == FrefQualLValue)
     837           0 :       S += " &";
     838         385 :     else if (RefQual == FrefQualRValue)
     839           0 :       S += " &&";
     840             : 
     841         385 :     if (ExceptionSpec != nullptr) {
     842             :       S += ' ';
     843           0 :       ExceptionSpec->print(S);
     844             :     }
     845         385 :   }
     846             : };
     847             : 
     848           0 : class NoexceptSpec : public Node {
     849             :   Node *E;
     850             : public:
     851           0 :   NoexceptSpec(Node *E_) : Node(KNoexceptSpec), E(E_) {}
     852             : 
     853           0 :   void printLeft(OutputStream &S) const override {
     854           0 :     S += "noexcept(";
     855           0 :     E->print(S);
     856           0 :     S += ")";
     857           0 :   }
     858             : };
     859             : 
     860           0 : class DynamicExceptionSpec : public Node {
     861             :   NodeArray Types;
     862             : public:
     863             :   DynamicExceptionSpec(NodeArray Types_)
     864           0 :       : Node(KDynamicExceptionSpec), Types(Types_) {}
     865             : 
     866           0 :   void printLeft(OutputStream &S) const override {
     867           0 :     S += "throw(";
     868           0 :     Types.printWithComma(S);
     869             :     S += ')';
     870           0 :   }
     871             : };
     872             : 
     873           0 : class FunctionEncoding final : public Node {
     874             :   Node *Ret;
     875             :   Node *Name;
     876             :   NodeArray Params;
     877             :   Node *Attrs;
     878             :   Qualifiers CVQuals;
     879             :   FunctionRefQual RefQual;
     880             : 
     881             : public:
     882             :   FunctionEncoding(Node *Ret_, Node *Name_, NodeArray Params_,
     883             :                    Node *Attrs_, Qualifiers CVQuals_, FunctionRefQual RefQual_)
     884        2445 :       : Node(KFunctionEncoding,
     885             :              /*RHSComponentCache=*/Cache::Yes, /*ArrayCache=*/Cache::No,
     886             :              /*FunctionCache=*/Cache::Yes),
     887             :         Ret(Ret_), Name(Name_), Params(Params_), Attrs(Attrs_),
     888        2445 :         CVQuals(CVQuals_), RefQual(RefQual_) {}
     889             : 
     890             :   Qualifiers getCVQuals() const { return CVQuals; }
     891             :   FunctionRefQual getRefQual() const { return RefQual; }
     892             :   NodeArray getParams() const { return Params; }
     893             :   Node *getReturnType() const { return Ret; }
     894             : 
     895           0 :   bool hasRHSComponentSlow(OutputStream &) const override { return true; }
     896           0 :   bool hasFunctionSlow(OutputStream &) const override { return true; }
     897             : 
     898             :   Node *getName() { return const_cast<Node *>(Name); }
     899             : 
     900        1314 :   void printLeft(OutputStream &S) const override {
     901        1314 :     if (Ret) {
     902         280 :       Ret->printLeft(S);
     903         560 :       if (!Ret->hasRHSComponent(S))
     904         257 :         S += " ";
     905             :     }
     906        1314 :     Name->print(S);
     907        1314 :   }
     908             : 
     909        1314 :   void printRight(OutputStream &S) const override {
     910        1314 :     S += "(";
     911        1314 :     Params.printWithComma(S);
     912        1314 :     S += ")";
     913        1314 :     if (Ret)
     914         280 :       Ret->printRight(S);
     915             : 
     916        1314 :     if (CVQuals & QualConst)
     917          60 :       S += " const";
     918        1314 :     if (CVQuals & QualVolatile)
     919           0 :       S += " volatile";
     920        1314 :     if (CVQuals & QualRestrict)
     921           0 :       S += " restrict";
     922             : 
     923        1314 :     if (RefQual == FrefQualLValue)
     924           0 :       S += " &";
     925        1314 :     else if (RefQual == FrefQualRValue)
     926           0 :       S += " &&";
     927             : 
     928        1314 :     if (Attrs != nullptr)
     929             :       Attrs->print(S);
     930        1314 :   }
     931             : };
     932             : 
     933           0 : class LiteralOperator : public Node {
     934             :   const Node *OpName;
     935             : 
     936             : public:
     937           0 :   LiteralOperator(Node *OpName_) : Node(KLiteralOperator), OpName(OpName_) {}
     938             : 
     939           0 :   void printLeft(OutputStream &S) const override {
     940           0 :     S += "operator\"\" ";
     941           0 :     OpName->print(S);
     942           0 :   }
     943             : };
     944             : 
     945           0 : class SpecialName final : public Node {
     946             :   const StringView Special;
     947             :   const Node *Child;
     948             : 
     949             : public:
     950             :   SpecialName(StringView Special_, Node* Child_)
     951         712 :       : Node(KSpecialName), Special(Special_), Child(Child_) {}
     952             : 
     953          19 :   void printLeft(OutputStream &S) const override {
     954          19 :     S += Special;
     955          19 :     Child->print(S);
     956          19 :   }
     957             : };
     958             : 
     959           0 : class CtorVtableSpecialName final : public Node {
     960             :   const Node *FirstType;
     961             :   const Node *SecondType;
     962             : 
     963             : public:
     964             :   CtorVtableSpecialName(Node *FirstType_, Node *SecondType_)
     965           0 :       : Node(KCtorVtableSpecialName),
     966           0 :         FirstType(FirstType_), SecondType(SecondType_) {}
     967             : 
     968           0 :   void printLeft(OutputStream &S) const override {
     969           0 :     S += "construction vtable for ";
     970           0 :     FirstType->print(S);
     971           0 :     S += "-in-";
     972           0 :     SecondType->print(S);
     973           0 :   }
     974             : };
     975             : 
     976           0 : struct NestedName : Node {
     977             :   Node *Qual;
     978             :   Node *Name;
     979             : 
     980             :   NestedName(Node *Qual_, Node *Name_)
     981       14050 :       : Node(KNestedName), Qual(Qual_), Name(Name_) {}
     982             : 
     983         241 :   StringView getBaseName() const override { return Name->getBaseName(); }
     984             : 
     985        6456 :   void printLeft(OutputStream &S) const override {
     986        6456 :     Qual->print(S);
     987        6456 :     S += "::";
     988        6456 :     Name->print(S);
     989        6456 :   }
     990             : };
     991             : 
     992           0 : struct LocalName : Node {
     993             :   Node *Encoding;
     994             :   Node *Entity;
     995             : 
     996             :   LocalName(Node *Encoding_, Node *Entity_)
     997          18 :       : Node(KLocalName), Encoding(Encoding_), Entity(Entity_) {}
     998             : 
     999           5 :   void printLeft(OutputStream &S) const override {
    1000           5 :     Encoding->print(S);
    1001           5 :     S += "::";
    1002           5 :     Entity->print(S);
    1003           5 :   }
    1004             : };
    1005             : 
    1006           0 : class QualifiedName final : public Node {
    1007             :   // qualifier::name
    1008             :   const Node *Qualifier;
    1009             :   const Node *Name;
    1010             : 
    1011             : public:
    1012             :   QualifiedName(Node* Qualifier_, Node* Name_)
    1013          60 :       : Node(KQualifiedName), Qualifier(Qualifier_), Name(Name_) {}
    1014             : 
    1015           0 :   StringView getBaseName() const override { return Name->getBaseName(); }
    1016             : 
    1017          30 :   void printLeft(OutputStream &S) const override {
    1018          30 :     Qualifier->print(S);
    1019          30 :     S += "::";
    1020          30 :     Name->print(S);
    1021          30 :   }
    1022             : };
    1023             : 
    1024           0 : class VectorType final : public Node {
    1025             :   const Node *BaseType;
    1026             :   const NodeOrString Dimension;
    1027             :   const bool IsPixel;
    1028             : 
    1029             : public:
    1030             :   VectorType(NodeOrString Dimension_)
    1031           0 :       : Node(KVectorType), BaseType(nullptr), Dimension(Dimension_),
    1032           0 :         IsPixel(true) {}
    1033             :   VectorType(Node *BaseType_, NodeOrString Dimension_)
    1034           0 :       : Node(KVectorType), BaseType(BaseType_),
    1035           0 :         Dimension(Dimension_), IsPixel(false) {}
    1036             : 
    1037           0 :   void printLeft(OutputStream &S) const override {
    1038           0 :     if (IsPixel) {
    1039           0 :       S += "pixel vector[";
    1040           0 :       S += Dimension.asString();
    1041           0 :       S += "]";
    1042             :     } else {
    1043           0 :       BaseType->print(S);
    1044           0 :       S += " vector[";
    1045             :       if (Dimension.isNode())
    1046             :         Dimension.asNode()->print(S);
    1047             :       else if (Dimension.isString())
    1048           0 :         S += Dimension.asString();
    1049           0 :       S += "]";
    1050             :     }
    1051           0 :   }
    1052             : };
    1053             : 
    1054             : /// An unexpanded parameter pack (either in the expression or type context). If
    1055             : /// this AST is correct, this node will have a ParameterPackExpansion node above
    1056             : /// it.
    1057             : ///
    1058             : /// This node is created when some <template-args> are found that apply to an
    1059             : /// <encoding>, and is stored in the TemplateParams table. In order for this to
    1060             : /// appear in the final AST, it has to referenced via a <template-param> (ie,
    1061             : /// T_).
    1062           0 : class ParameterPack final : public Node {
    1063             :   NodeArray Data;
    1064             : 
    1065             :   // Setup OutputStream for a pack expansion unless we're already expanding one.
    1066             :   void initializePackExpansion(OutputStream &S) const {
    1067         472 :     if (S.CurrentPackMax == std::numeric_limits<unsigned>::max()) {
    1068         246 :       S.CurrentPackMax = static_cast<unsigned>(Data.size());
    1069         246 :       S.CurrentPackIndex = 0;
    1070             :     }
    1071             :   }
    1072             : 
    1073             : public:
    1074         614 :   ParameterPack(NodeArray Data_) : Node(KParameterPack), Data(Data_) {
    1075         307 :     ArrayCache = FunctionCache = RHSComponentCache = Cache::Unknown;
    1076         307 :     if (std::all_of(Data.begin(), Data.end(), [](Node* P) {
    1077             :           return P->ArrayCache == Cache::No;
    1078             :         }))
    1079         306 :       ArrayCache = Cache::No;
    1080         307 :     if (std::all_of(Data.begin(), Data.end(), [](Node* P) {
    1081             :           return P->FunctionCache == Cache::No;
    1082             :         }))
    1083         306 :       FunctionCache = Cache::No;
    1084         307 :     if (std::all_of(Data.begin(), Data.end(), [](Node* P) {
    1085             :           return P->RHSComponentCache == Cache::No;
    1086             :         }))
    1087         248 :       RHSComponentCache = Cache::No;
    1088         307 :   }
    1089             : 
    1090           0 :   bool hasRHSComponentSlow(OutputStream &S) const override {
    1091             :     initializePackExpansion(S);
    1092           0 :     size_t Idx = S.CurrentPackIndex;
    1093           0 :     return Idx < Data.size() && Data[Idx]->hasRHSComponent(S);
    1094             :   }
    1095           6 :   bool hasArraySlow(OutputStream &S) const override {
    1096             :     initializePackExpansion(S);
    1097           6 :     size_t Idx = S.CurrentPackIndex;
    1098          12 :     return Idx < Data.size() && Data[Idx]->hasArray(S);
    1099             :   }
    1100           2 :   bool hasFunctionSlow(OutputStream &S) const override {
    1101             :     initializePackExpansion(S);
    1102           2 :     size_t Idx = S.CurrentPackIndex;
    1103           4 :     return Idx < Data.size() && Data[Idx]->hasFunction(S);
    1104             :   }
    1105             : 
    1106         380 :   void printLeft(OutputStream &S) const override {
    1107             :     initializePackExpansion(S);
    1108         380 :     size_t Idx = S.CurrentPackIndex;
    1109         380 :     if (Idx < Data.size())
    1110         690 :       Data[Idx]->printLeft(S);
    1111         380 :   }
    1112          84 :   void printRight(OutputStream &S) const override {
    1113             :     initializePackExpansion(S);
    1114          84 :     size_t Idx = S.CurrentPackIndex;
    1115          84 :     if (Idx < Data.size())
    1116         168 :       Data[Idx]->printRight(S);
    1117          84 :   }
    1118             : };
    1119             : 
    1120             : /// A variadic template argument. This node represents an occurrence of
    1121             : /// J<something>E in some <template-args>. It isn't itself unexpanded, unless
    1122             : /// one of it's Elements is. The parser inserts a ParameterPack into the
    1123             : /// TemplateParams table if the <template-args> this pack belongs to apply to an
    1124             : /// <encoding>.
    1125           0 : class TemplateArgumentPack final : public Node {
    1126             :   NodeArray Elements;
    1127             : public:
    1128             :   TemplateArgumentPack(NodeArray Elements_)
    1129        1086 :       : Node(KTemplateArgumentPack), Elements(Elements_) {}
    1130             : 
    1131             :   NodeArray getElements() const { return Elements; }
    1132             : 
    1133         729 :   void printLeft(OutputStream &S) const override {
    1134         729 :     Elements.printWithComma(S);
    1135         729 :   }
    1136             : };
    1137             : 
    1138             : /// A pack expansion. Below this node, there are some unexpanded ParameterPacks
    1139             : /// which each have Child->ParameterPackSize elements.
    1140           0 : class ParameterPackExpansion final : public Node {
    1141             :   const Node *Child;
    1142             : 
    1143             : public:
    1144             :   ParameterPackExpansion(Node* Child_)
    1145         400 :       : Node(KParameterPackExpansion), Child(Child_) {}
    1146             : 
    1147             :   const Node *getChild() const { return Child; }
    1148             : 
    1149         246 :   void printLeft(OutputStream &S) const override {
    1150             :     constexpr unsigned Max = std::numeric_limits<unsigned>::max();
    1151         246 :     SwapAndRestore<unsigned> SavePackIdx(S.CurrentPackIndex, Max);
    1152         246 :     SwapAndRestore<unsigned> SavePackMax(S.CurrentPackMax, Max);
    1153         246 :     size_t StreamPos = S.getCurrentPosition();
    1154             : 
    1155             :     // Print the first element in the pack. If Child contains a ParameterPack,
    1156             :     // it will set up S.CurrentPackMax and print the first element.
    1157         246 :     Child->print(S);
    1158             : 
    1159             :     // No ParameterPack was found in Child. This can occur if we've found a pack
    1160             :     // expansion on a <function-param>.
    1161         246 :     if (S.CurrentPackMax == Max) {
    1162           0 :       S += "...";
    1163           0 :       return;
    1164             :     }
    1165             : 
    1166             :     // We found a ParameterPack, but it has no elements. Erase whatever we may
    1167             :     // of printed.
    1168         246 :     if (S.CurrentPackMax == 0) {
    1169             :       S.setCurrentPosition(StreamPos);
    1170             :       return;
    1171             :     }
    1172             : 
    1173             :     // Else, iterate through the rest of the elements in the pack.
    1174         479 :     for (unsigned I = 1, E = S.CurrentPackMax; I < E; ++I) {
    1175         134 :       S += ", ";
    1176         134 :       S.CurrentPackIndex = I;
    1177         134 :       Child->print(S);
    1178             :     }
    1179             :   }
    1180             : };
    1181             : 
    1182           0 : class TemplateArgs final : public Node {
    1183             :   NodeArray Params;
    1184             : 
    1185             : public:
    1186       11934 :   TemplateArgs(NodeArray Params_) : Node(KTemplateArgs), Params(Params_) {}
    1187             : 
    1188             :   NodeArray getParams() { return Params; }
    1189             : 
    1190        8058 :   void printLeft(OutputStream &S) const override {
    1191        8058 :     S += "<";
    1192        8058 :     Params.printWithComma(S);
    1193       16116 :     if (S.back() == '>')
    1194        3490 :       S += " ";
    1195        8058 :     S += ">";
    1196        8058 :   }
    1197             : };
    1198             : 
    1199           0 : struct ForwardTemplateReference : Node {
    1200             :   size_t Index;
    1201             :   Node *Ref = nullptr;
    1202             : 
    1203             :   // If we're currently printing this node. It is possible (though invalid) for
    1204             :   // a forward template reference to refer to itself via a substitution. This
    1205             :   // creates a cyclic AST, which will stack overflow printing. To fix this, bail
    1206             :   // out if more than one print* function is active.
    1207             :   mutable bool Printing = false;
    1208             : 
    1209             :   ForwardTemplateReference(size_t Index_)
    1210           1 :       : Node(KForwardTemplateReference, Cache::Unknown, Cache::Unknown,
    1211             :              Cache::Unknown),
    1212           1 :         Index(Index_) {}
    1213             : 
    1214           0 :   bool hasRHSComponentSlow(OutputStream &S) const override {
    1215           0 :     if (Printing)
    1216             :       return false;
    1217           0 :     SwapAndRestore<bool> SavePrinting(Printing, true);
    1218           0 :     return Ref->hasRHSComponent(S);
    1219             :   }
    1220           6 :   bool hasArraySlow(OutputStream &S) const override {
    1221           6 :     if (Printing)
    1222             :       return false;
    1223           6 :     SwapAndRestore<bool> SavePrinting(Printing, true);
    1224           6 :     return Ref->hasArray(S);
    1225             :   }
    1226           2 :   bool hasFunctionSlow(OutputStream &S) const override {
    1227           2 :     if (Printing)
    1228             :       return false;
    1229           2 :     SwapAndRestore<bool> SavePrinting(Printing, true);
    1230           2 :     return Ref->hasFunction(S);
    1231             :   }
    1232             : 
    1233           2 :   void printLeft(OutputStream &S) const override {
    1234           2 :     if (Printing)
    1235             :       return;
    1236           2 :     SwapAndRestore<bool> SavePrinting(Printing, true);
    1237           2 :     Ref->printLeft(S);
    1238             :   }
    1239           2 :   void printRight(OutputStream &S) const override {
    1240           2 :     if (Printing)
    1241             :       return;
    1242           2 :     SwapAndRestore<bool> SavePrinting(Printing, true);
    1243           2 :     Ref->printRight(S);
    1244             :   }
    1245             : };
    1246             : 
    1247           0 : struct NameWithTemplateArgs : Node {
    1248             :   // name<template_args>
    1249             :   Node *Name;
    1250             :   Node *TemplateArgs;
    1251             : 
    1252             :   NameWithTemplateArgs(Node *Name_, Node *TemplateArgs_)
    1253       11934 :       : Node(KNameWithTemplateArgs), Name(Name_), TemplateArgs(TemplateArgs_) {}
    1254             : 
    1255         241 :   StringView getBaseName() const override { return Name->getBaseName(); }
    1256             : 
    1257        8058 :   void printLeft(OutputStream &S) const override {
    1258        8058 :     Name->print(S);
    1259        8058 :     TemplateArgs->print(S);
    1260        8058 :   }
    1261             : };
    1262             : 
    1263           0 : class GlobalQualifiedName final : public Node {
    1264             :   Node *Child;
    1265             : 
    1266             : public:
    1267             :   GlobalQualifiedName(Node* Child_)
    1268           0 :       : Node(KGlobalQualifiedName), Child(Child_) {}
    1269             : 
    1270           0 :   StringView getBaseName() const override { return Child->getBaseName(); }
    1271             : 
    1272           0 :   void printLeft(OutputStream &S) const override {
    1273           0 :     S += "::";
    1274           0 :     Child->print(S);
    1275           0 :   }
    1276             : };
    1277             : 
    1278           0 : struct StdQualifiedName : Node {
    1279             :   Node *Child;
    1280             : 
    1281        6136 :   StdQualifiedName(Node *Child_) : Node(KStdQualifiedName), Child(Child_) {}
    1282             : 
    1283           0 :   StringView getBaseName() const override { return Child->getBaseName(); }
    1284             : 
    1285        3608 :   void printLeft(OutputStream &S) const override {
    1286        3608 :     S += "std::";
    1287        3608 :     Child->print(S);
    1288        3608 :   }
    1289             : };
    1290             : 
    1291             : enum class SpecialSubKind {
    1292             :   allocator,
    1293             :   basic_string,
    1294             :   string,
    1295             :   istream,
    1296             :   ostream,
    1297             :   iostream,
    1298             : };
    1299             : 
    1300           0 : class ExpandedSpecialSubstitution final : public Node {
    1301             :   SpecialSubKind SSK;
    1302             : 
    1303             : public:
    1304             :   ExpandedSpecialSubstitution(SpecialSubKind SSK_)
    1305           2 :       : Node(KExpandedSpecialSubstitution), SSK(SSK_) {}
    1306             : 
    1307           1 :   StringView getBaseName() const override {
    1308           1 :     switch (SSK) {
    1309             :     case SpecialSubKind::allocator:
    1310           0 :       return StringView("allocator");
    1311             :     case SpecialSubKind::basic_string:
    1312           0 :       return StringView("basic_string");
    1313             :     case SpecialSubKind::string:
    1314           1 :       return StringView("basic_string");
    1315             :     case SpecialSubKind::istream:
    1316           0 :       return StringView("basic_istream");
    1317             :     case SpecialSubKind::ostream:
    1318           0 :       return StringView("basic_ostream");
    1319             :     case SpecialSubKind::iostream:
    1320           0 :       return StringView("basic_iostream");
    1321             :     }
    1322           0 :     LLVM_BUILTIN_UNREACHABLE;
    1323             :   }
    1324             : 
    1325           1 :   void printLeft(OutputStream &S) const override {
    1326           1 :     switch (SSK) {
    1327             :     case SpecialSubKind::allocator:
    1328           0 :       S += "std::basic_string<char, std::char_traits<char>, "
    1329           0 :            "std::allocator<char> >";
    1330           0 :       break;
    1331             :     case SpecialSubKind::basic_string:
    1332             :     case SpecialSubKind::string:
    1333           1 :       S += "std::basic_string<char, std::char_traits<char>, "
    1334           1 :            "std::allocator<char> >";
    1335           1 :       break;
    1336             :     case SpecialSubKind::istream:
    1337           0 :       S += "std::basic_istream<char, std::char_traits<char> >";
    1338           0 :       break;
    1339             :     case SpecialSubKind::ostream:
    1340           0 :       S += "std::basic_ostream<char, std::char_traits<char> >";
    1341           0 :       break;
    1342             :     case SpecialSubKind::iostream:
    1343           0 :       S += "std::basic_iostream<char, std::char_traits<char> >";
    1344           0 :       break;
    1345             :     }
    1346           1 :   }
    1347             : };
    1348             : 
    1349           0 : class SpecialSubstitution final : public Node {
    1350             : public:
    1351             :   SpecialSubKind SSK;
    1352             : 
    1353             :   SpecialSubstitution(SpecialSubKind SSK_)
    1354        2976 :       : Node(KSpecialSubstitution), SSK(SSK_) {}
    1355             : 
    1356          13 :   StringView getBaseName() const override {
    1357          13 :     switch (SSK) {
    1358             :     case SpecialSubKind::allocator:
    1359          13 :       return StringView("allocator");
    1360             :     case SpecialSubKind::basic_string:
    1361           0 :       return StringView("basic_string");
    1362             :     case SpecialSubKind::string:
    1363           0 :       return StringView("string");
    1364             :     case SpecialSubKind::istream:
    1365           0 :       return StringView("istream");
    1366             :     case SpecialSubKind::ostream:
    1367           0 :       return StringView("ostream");
    1368             :     case SpecialSubKind::iostream:
    1369           0 :       return StringView("iostream");
    1370             :     }
    1371           0 :     LLVM_BUILTIN_UNREACHABLE;
    1372             :   }
    1373             : 
    1374        1852 :   void printLeft(OutputStream &S) const override {
    1375        1852 :     switch (SSK) {
    1376             :     case SpecialSubKind::allocator:
    1377        1798 :       S += "std::allocator";
    1378        1798 :       break;
    1379             :     case SpecialSubKind::basic_string:
    1380           0 :       S += "std::basic_string";
    1381           0 :       break;
    1382             :     case SpecialSubKind::string:
    1383          54 :       S += "std::string";
    1384          54 :       break;
    1385             :     case SpecialSubKind::istream:
    1386           0 :       S += "std::istream";
    1387           0 :       break;
    1388             :     case SpecialSubKind::ostream:
    1389           0 :       S += "std::ostream";
    1390           0 :       break;
    1391             :     case SpecialSubKind::iostream:
    1392           0 :       S += "std::iostream";
    1393           0 :       break;
    1394             :     }
    1395        1852 :   }
    1396             : };
    1397             : 
    1398           0 : class CtorDtorName final : public Node {
    1399             :   const Node *Basename;
    1400             :   const bool IsDtor;
    1401             : 
    1402             : public:
    1403             :   CtorDtorName(Node *Basename_, bool IsDtor_)
    1404        2174 :       : Node(KCtorDtorName), Basename(Basename_), IsDtor(IsDtor_) {}
    1405             : 
    1406         261 :   void printLeft(OutputStream &S) const override {
    1407         261 :     if (IsDtor)
    1408          65 :       S += "~";
    1409         261 :     S += Basename->getBaseName();
    1410         261 :   }
    1411             : };
    1412             : 
    1413           0 : class DtorName : public Node {
    1414             :   const Node *Base;
    1415             : 
    1416             : public:
    1417           0 :   DtorName(Node *Base_) : Node(KDtorName), Base(Base_) {}
    1418             : 
    1419           0 :   void printLeft(OutputStream &S) const override {
    1420           0 :     S += "~";
    1421           0 :     Base->printLeft(S);
    1422           0 :   }
    1423             : };
    1424             : 
    1425           0 : class UnnamedTypeName : public Node {
    1426             :   const StringView Count;
    1427             : 
    1428             : public:
    1429           0 :   UnnamedTypeName(StringView Count_) : Node(KUnnamedTypeName), Count(Count_) {}
    1430             : 
    1431           0 :   void printLeft(OutputStream &S) const override {
    1432           0 :     S += "'unnamed";
    1433           0 :     S += Count;
    1434           0 :     S += "\'";
    1435           0 :   }
    1436             : };
    1437             : 
    1438           0 : class ClosureTypeName : public Node {
    1439             :   NodeArray Params;
    1440             :   StringView Count;
    1441             : 
    1442             : public:
    1443             :   ClosureTypeName(NodeArray Params_, StringView Count_)
    1444          12 :       : Node(KClosureTypeName), Params(Params_), Count(Count_) {}
    1445             : 
    1446           6 :   void printLeft(OutputStream &S) const override {
    1447           6 :     S += "\'lambda";
    1448           6 :     S += Count;
    1449           6 :     S += "\'(";
    1450           6 :     Params.printWithComma(S);
    1451           6 :     S += ")";
    1452           6 :   }
    1453             : };
    1454             : 
    1455           0 : class StructuredBindingName : public Node {
    1456             :   NodeArray Bindings;
    1457             : public:
    1458             :   StructuredBindingName(NodeArray Bindings_)
    1459           2 :       : Node(KStructuredBindingName), Bindings(Bindings_) {}
    1460             : 
    1461           0 :   void printLeft(OutputStream &S) const override {
    1462             :     S += '[';
    1463           0 :     Bindings.printWithComma(S);
    1464             :     S += ']';
    1465           0 :   }
    1466             : };
    1467             : 
    1468             : // -- Expression Nodes --
    1469             : 
    1470             : struct Expr : public Node {
    1471             :   Expr(Kind K = KExpr) : Node(K) {}
    1472             : };
    1473             : 
    1474           0 : class BinaryExpr : public Expr {
    1475             :   const Node *LHS;
    1476             :   const StringView InfixOperator;
    1477             :   const Node *RHS;
    1478             : 
    1479             : public:
    1480             :   BinaryExpr(Node *LHS_, StringView InfixOperator_, Node *RHS_)
    1481           4 :       : LHS(LHS_), InfixOperator(InfixOperator_), RHS(RHS_) {}
    1482             : 
    1483           0 :   void printLeft(OutputStream &S) const override {
    1484             :     // might be a template argument expression, then we need to disambiguate
    1485             :     // with parens.
    1486           0 :     if (InfixOperator == ">")
    1487           0 :       S += "(";
    1488             : 
    1489           0 :     S += "(";
    1490           0 :     LHS->print(S);
    1491           0 :     S += ") ";
    1492           0 :     S += InfixOperator;
    1493           0 :     S += " (";
    1494           0 :     RHS->print(S);
    1495           0 :     S += ")";
    1496             : 
    1497           0 :     if (InfixOperator == ">")
    1498           0 :       S += ")";
    1499           0 :   }
    1500             : };
    1501             : 
    1502           0 : class ArraySubscriptExpr : public Expr {
    1503             :   const Node *Op1;
    1504             :   const Node *Op2;
    1505             : 
    1506             : public:
    1507           0 :   ArraySubscriptExpr(Node *Op1_, Node *Op2_) : Op1(Op1_), Op2(Op2_) {}
    1508             : 
    1509           0 :   void printLeft(OutputStream &S) const override {
    1510           0 :     S += "(";
    1511           0 :     Op1->print(S);
    1512           0 :     S += ")[";
    1513           0 :     Op2->print(S);
    1514           0 :     S += "]";
    1515           0 :   }
    1516             : };
    1517             : 
    1518           0 : class PostfixExpr : public Expr {
    1519             :   const Node *Child;
    1520             :   const StringView Operand;
    1521             : 
    1522             : public:
    1523             :   PostfixExpr(Node *Child_, StringView Operand_)
    1524           0 :       : Child(Child_), Operand(Operand_) {}
    1525             : 
    1526           0 :   void printLeft(OutputStream &S) const override {
    1527           0 :     S += "(";
    1528           0 :     Child->print(S);
    1529           0 :     S += ")";
    1530           0 :     S += Operand;
    1531           0 :   }
    1532             : };
    1533             : 
    1534           0 : class ConditionalExpr : public Expr {
    1535             :   const Node *Cond;
    1536             :   const Node *Then;
    1537             :   const Node *Else;
    1538             : 
    1539             : public:
    1540             :   ConditionalExpr(Node *Cond_, Node *Then_, Node *Else_)
    1541           0 :       : Cond(Cond_), Then(Then_), Else(Else_) {}
    1542             : 
    1543           0 :   void printLeft(OutputStream &S) const override {
    1544           0 :     S += "(";
    1545           0 :     Cond->print(S);
    1546           0 :     S += ") ? (";
    1547           0 :     Then->print(S);
    1548           0 :     S += ") : (";
    1549           0 :     Else->print(S);
    1550           0 :     S += ")";
    1551           0 :   }
    1552             : };
    1553             : 
    1554           0 : class MemberExpr : public Expr {
    1555             :   const Node *LHS;
    1556             :   const StringView Kind;
    1557             :   const Node *RHS;
    1558             : 
    1559             : public:
    1560             :   MemberExpr(Node *LHS_, StringView Kind_, Node *RHS_)
    1561           2 :       : LHS(LHS_), Kind(Kind_), RHS(RHS_) {}
    1562             : 
    1563           1 :   void printLeft(OutputStream &S) const override {
    1564           1 :     LHS->print(S);
    1565           1 :     S += Kind;
    1566           1 :     RHS->print(S);
    1567           1 :   }
    1568             : };
    1569             : 
    1570           0 : class EnclosingExpr : public Expr {
    1571             :   const StringView Prefix;
    1572             :   const Node *Infix;
    1573             :   const StringView Postfix;
    1574             : 
    1575             : public:
    1576             :   EnclosingExpr(StringView Prefix_, Node *Infix_, StringView Postfix_)
    1577          12 :       : Prefix(Prefix_), Infix(Infix_), Postfix(Postfix_) {}
    1578             : 
    1579           6 :   void printLeft(OutputStream &S) const override {
    1580           6 :     S += Prefix;
    1581           6 :     Infix->print(S);
    1582           6 :     S += Postfix;
    1583           6 :   }
    1584             : };
    1585             : 
    1586           0 : class CastExpr : public Expr {
    1587             :   // cast_kind<to>(from)
    1588             :   const StringView CastKind;
    1589             :   const Node *To;
    1590             :   const Node *From;
    1591             : 
    1592             : public:
    1593             :   CastExpr(StringView CastKind_, Node *To_, Node *From_)
    1594           0 :       : CastKind(CastKind_), To(To_), From(From_) {}
    1595             : 
    1596           0 :   void printLeft(OutputStream &S) const override {
    1597           0 :     S += CastKind;
    1598           0 :     S += "<";
    1599           0 :     To->printLeft(S);
    1600           0 :     S += ">(";
    1601           0 :     From->printLeft(S);
    1602           0 :     S += ")";
    1603           0 :   }
    1604             : };
    1605             : 
    1606           0 : class SizeofParamPackExpr : public Expr {
    1607             :   Node *Pack;
    1608             : 
    1609             : public:
    1610           0 :   SizeofParamPackExpr(Node *Pack_) : Pack(Pack_) {}
    1611             : 
    1612           0 :   void printLeft(OutputStream &S) const override {
    1613           0 :     S += "sizeof...(";
    1614           0 :     ParameterPackExpansion PPE(Pack);
    1615           0 :     PPE.printLeft(S);
    1616           0 :     S += ")";
    1617           0 :   }
    1618             : };
    1619             : 
    1620           0 : class CallExpr : public Expr {
    1621             :   const Node *Callee;
    1622             :   NodeArray Args;
    1623             : 
    1624             : public:
    1625          24 :   CallExpr(Node *Callee_, NodeArray Args_) : Callee(Callee_), Args(Args_) {}
    1626             : 
    1627          16 :   void printLeft(OutputStream &S) const override {
    1628          16 :     Callee->print(S);
    1629          16 :     S += "(";
    1630          16 :     Args.printWithComma(S);
    1631          16 :     S += ")";
    1632          16 :   }
    1633             : };
    1634             : 
    1635           0 : class NewExpr : public Expr {
    1636             :   // new (expr_list) type(init_list)
    1637             :   NodeArray ExprList;
    1638             :   Node *Type;
    1639             :   NodeArray InitList;
    1640             :   bool IsGlobal; // ::operator new ?
    1641             :   bool IsArray;  // new[] ?
    1642             : public:
    1643             :   NewExpr(NodeArray ExprList_, Node *Type_, NodeArray InitList_, bool IsGlobal_,
    1644             :           bool IsArray_)
    1645           0 :       : ExprList(ExprList_), Type(Type_), InitList(InitList_),
    1646           0 :         IsGlobal(IsGlobal_), IsArray(IsArray_) {}
    1647             : 
    1648           0 :   void printLeft(OutputStream &S) const override {
    1649           0 :     if (IsGlobal)
    1650           0 :       S += "::operator ";
    1651           0 :     S += "new";
    1652           0 :     if (IsArray)
    1653           0 :       S += "[]";
    1654             :     S += ' ';
    1655           0 :     if (!ExprList.empty()) {
    1656           0 :       S += "(";
    1657           0 :       ExprList.printWithComma(S);
    1658           0 :       S += ")";
    1659             :     }
    1660           0 :     Type->print(S);
    1661           0 :     if (!InitList.empty()) {
    1662           0 :       S += "(";
    1663           0 :       InitList.printWithComma(S);
    1664           0 :       S += ")";
    1665             :     }
    1666             : 
    1667           0 :   }
    1668             : };
    1669             : 
    1670           0 : class DeleteExpr : public Expr {
    1671             :   Node *Op;
    1672             :   bool IsGlobal;
    1673             :   bool IsArray;
    1674             : 
    1675             : public:
    1676             :   DeleteExpr(Node *Op_, bool IsGlobal_, bool IsArray_)
    1677           0 :       : Op(Op_), IsGlobal(IsGlobal_), IsArray(IsArray_) {}
    1678             : 
    1679           0 :   void printLeft(OutputStream &S) const override {
    1680           0 :     if (IsGlobal)
    1681           0 :       S += "::";
    1682           0 :     S += "delete";
    1683           0 :     if (IsArray)
    1684           0 :       S += "[] ";
    1685           0 :     Op->print(S);
    1686           0 :   }
    1687             : };
    1688             : 
    1689           0 : class PrefixExpr : public Expr {
    1690             :   StringView Prefix;
    1691             :   Node *Child;
    1692             : 
    1693             : public:
    1694           4 :   PrefixExpr(StringView Prefix_, Node *Child_) : Prefix(Prefix_), Child(Child_) {}
    1695             : 
    1696           2 :   void printLeft(OutputStream &S) const override {
    1697           2 :     S += Prefix;
    1698           2 :     S += "(";
    1699           2 :     Child->print(S);
    1700           2 :     S += ")";
    1701           2 :   }
    1702             : };
    1703             : 
    1704           0 : class FunctionParam : public Expr {
    1705             :   StringView Number;
    1706             : 
    1707             : public:
    1708           6 :   FunctionParam(StringView Number_) : Number(Number_) {}
    1709             : 
    1710           1 :   void printLeft(OutputStream &S) const override {
    1711           1 :     S += "fp";
    1712           1 :     S += Number;
    1713           1 :   }
    1714             : };
    1715             : 
    1716           0 : class ConversionExpr : public Expr {
    1717             :   const Node *Type;
    1718             :   NodeArray Expressions;
    1719             : 
    1720             : public:
    1721             :   ConversionExpr(const Node *Type_, NodeArray Expressions_)
    1722           0 :       : Type(Type_), Expressions(Expressions_) {}
    1723             : 
    1724           0 :   void printLeft(OutputStream &S) const override {
    1725           0 :     S += "(";
    1726           0 :     Type->print(S);
    1727           0 :     S += ")(";
    1728           0 :     Expressions.printWithComma(S);
    1729           0 :     S += ")";
    1730           0 :   }
    1731             : };
    1732             : 
    1733           0 : class InitListExpr : public Expr {
    1734             :   Node *Ty;
    1735             :   NodeArray Inits;
    1736             : public:
    1737           0 :   InitListExpr(Node *Ty_, NodeArray Inits_) : Ty(Ty_), Inits(Inits_) {}
    1738             : 
    1739           0 :   void printLeft(OutputStream &S) const override {
    1740           0 :     if (Ty)
    1741             :       Ty->print(S);
    1742             :     S += '{';
    1743           0 :     Inits.printWithComma(S);
    1744             :     S += '}';
    1745           0 :   }
    1746             : };
    1747             : 
    1748           0 : class BracedExpr : public Expr {
    1749             :   Node *Elem;
    1750             :   Node *Init;
    1751             :   bool IsArray;
    1752             : public:
    1753             :   BracedExpr(Node *Elem_, Node *Init_, bool IsArray_)
    1754           0 :       : Expr(KBracedExpr), Elem(Elem_), Init(Init_), IsArray(IsArray_) {}
    1755             : 
    1756           0 :   void printLeft(OutputStream &S) const override {
    1757           0 :     if (IsArray) {
    1758             :       S += '[';
    1759           0 :       Elem->print(S);
    1760             :       S += ']';
    1761             :     } else {
    1762             :       S += '.';
    1763           0 :       Elem->print(S);
    1764             :     }
    1765           0 :     if (Init->getKind() != KBracedExpr && Init->getKind() != KBracedRangeExpr)
    1766           0 :       S += " = ";
    1767           0 :     Init->print(S);
    1768           0 :   }
    1769             : };
    1770             : 
    1771           0 : class BracedRangeExpr : public Expr {
    1772             :   Node *First;
    1773             :   Node *Last;
    1774             :   Node *Init;
    1775             : public:
    1776             :   BracedRangeExpr(Node *First_, Node *Last_, Node *Init_)
    1777           0 :       : Expr(KBracedRangeExpr), First(First_), Last(Last_), Init(Init_) {}
    1778             : 
    1779           0 :   void printLeft(OutputStream &S) const override {
    1780             :     S += '[';
    1781           0 :     First->print(S);
    1782           0 :     S += " ... ";
    1783           0 :     Last->print(S);
    1784             :     S += ']';
    1785           0 :     if (Init->getKind() != KBracedExpr && Init->getKind() != KBracedRangeExpr)
    1786           0 :       S += " = ";
    1787           0 :     Init->print(S);
    1788           0 :   }
    1789             : };
    1790             : 
    1791           0 : struct FoldExpr : Expr {
    1792             :   Node *Pack, *Init;
    1793             :   StringView OperatorName;
    1794             :   bool IsLeftFold;
    1795             : 
    1796             :   FoldExpr(bool IsLeftFold_, StringView OperatorName_, Node *Pack_, Node *Init_)
    1797           0 :       : Pack(Pack_), Init(Init_), OperatorName(OperatorName_),
    1798           0 :         IsLeftFold(IsLeftFold_) {}
    1799             : 
    1800           0 :   void printLeft(OutputStream &S) const override {
    1801           0 :     auto PrintPack = [&] {
    1802           0 :       S += '(';
    1803           0 :       ParameterPackExpansion(Pack).print(S);
    1804             :       S += ')';
    1805           0 :     };
    1806             : 
    1807             :     S += '(';
    1808             : 
    1809           0 :     if (IsLeftFold) {
    1810             :       // init op ... op pack
    1811           0 :       if (Init != nullptr) {
    1812             :         Init->print(S);
    1813             :         S += ' ';
    1814           0 :         S += OperatorName;
    1815             :         S += ' ';
    1816             :       }
    1817             :       // ... op pack
    1818           0 :       S += "... ";
    1819           0 :       S += OperatorName;
    1820             :       S += ' ';
    1821           0 :       PrintPack();
    1822             :     } else { // !IsLeftFold
    1823             :       // pack op ...
    1824           0 :       PrintPack();
    1825             :       S += ' ';
    1826           0 :       S += OperatorName;
    1827           0 :       S += " ...";
    1828             :       // pack op ... op init
    1829           0 :       if (Init != nullptr) {
    1830             :         S += ' ';
    1831           0 :         S += OperatorName;
    1832             :         S += ' ';
    1833           0 :         Init->print(S);
    1834             :       }
    1835             :     }
    1836             :     S += ')';
    1837           0 :   }
    1838             : };
    1839             : 
    1840           0 : class ThrowExpr : public Expr {
    1841             :   const Node *Op;
    1842             : 
    1843             : public:
    1844           0 :   ThrowExpr(Node *Op_) : Op(Op_) {}
    1845             : 
    1846           0 :   void printLeft(OutputStream &S) const override {
    1847           0 :     S += "throw ";
    1848           0 :     Op->print(S);
    1849           0 :   }
    1850             : };
    1851             : 
    1852           0 : class BoolExpr : public Expr {
    1853             :   bool Value;
    1854             : 
    1855             : public:
    1856         190 :   BoolExpr(bool Value_) : Value(Value_) {}
    1857             : 
    1858         104 :   void printLeft(OutputStream &S) const override {
    1859         104 :     S += Value ? StringView("true") : StringView("false");
    1860         104 :   }
    1861             : };
    1862             : 
    1863           0 : class IntegerCastExpr : public Expr {
    1864             :   // ty(integer)
    1865             :   Node *Ty;
    1866             :   StringView Integer;
    1867             : 
    1868             : public:
    1869             :   IntegerCastExpr(Node *Ty_, StringView Integer_)
    1870          80 :       : Ty(Ty_), Integer(Integer_) {}
    1871             : 
    1872          52 :   void printLeft(OutputStream &S) const override {
    1873          52 :     S += "(";
    1874          52 :     Ty->print(S);
    1875          52 :     S += ")";
    1876          52 :     S += Integer;
    1877          52 :   }
    1878             : };
    1879             : 
    1880           0 : class IntegerExpr : public Expr {
    1881             :   StringView Type;
    1882             :   StringView Value;
    1883             : 
    1884             : public:
    1885         806 :   IntegerExpr(StringView Type_, StringView Value_) : Type(Type_), Value(Value_) {}
    1886             : 
    1887         767 :   void printLeft(OutputStream &S) const override {
    1888         767 :     if (Type.size() > 3) {
    1889           0 :       S += "(";
    1890           0 :       S += Type;
    1891           0 :       S += ")";
    1892             :     }
    1893             : 
    1894         767 :     if (Value[0] == 'n') {
    1895           0 :       S += "-";
    1896           0 :       S += Value.dropFront(1);
    1897             :     } else
    1898         767 :       S += Value;
    1899             : 
    1900         767 :     if (Type.size() <= 3)
    1901         767 :       S += Type;
    1902         767 :   }
    1903             : };
    1904             : 
    1905             : template <class Float> struct FloatData;
    1906             : 
    1907           0 : template <class Float> class FloatExpr : public Expr {
    1908             :   const StringView Contents;
    1909             : 
    1910             : public:
    1911           0 :   FloatExpr(StringView Contents_) : Contents(Contents_) {}
    1912             : 
    1913           0 :   void printLeft(OutputStream &s) const override {
    1914           0 :     const char *first = Contents.begin();
    1915           0 :     const char *last = Contents.end() + 1;
    1916             : 
    1917             :     const size_t N = FloatData<Float>::mangled_size;
    1918           0 :     if (static_cast<std::size_t>(last - first) > N) {
    1919           0 :       last = first + N;
    1920             :       union {
    1921             :         Float value;
    1922             :         char buf[sizeof(Float)];
    1923           0 :       };
    1924             :       const char *t = first;
    1925             :       char *e = buf;
    1926           0 :       for (; t != last; ++t, ++e) {
    1927           0 :         unsigned d1 = isdigit(*t) ? static_cast<unsigned>(*t - '0')
    1928           0 :                                   : static_cast<unsigned>(*t - 'a' + 10);
    1929             :         ++t;
    1930           0 :         unsigned d0 = isdigit(*t) ? static_cast<unsigned>(*t - '0')
    1931           0 :                                   : static_cast<unsigned>(*t - 'a' + 10);
    1932           0 :         *e = static_cast<char>((d1 << 4) + d0);
    1933             :       }
    1934             : #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
    1935             :       std::reverse(buf, e);
    1936             : #endif
    1937           0 :       char num[FloatData<Float>::max_demangled_size] = {0};
    1938           0 :       int n = snprintf(num, sizeof(num), FloatData<Float>::spec, value);
    1939           0 :       s += StringView(num, num + n);
    1940             :     }
    1941           0 :   }
    1942             : };
    1943             : 
    1944             : class BumpPointerAllocator {
    1945             :   struct BlockMeta {
    1946             :     BlockMeta* Next;
    1947             :     size_t Current;
    1948             :   };
    1949             : 
    1950             :   static constexpr size_t AllocSize = 4096;
    1951             :   static constexpr size_t UsableAllocSize = AllocSize - sizeof(BlockMeta);
    1952             : 
    1953             :   alignas(long double) char InitialBuffer[AllocSize];
    1954             :   BlockMeta* BlockList = nullptr;
    1955             : 
    1956             :   void grow() {
    1957           0 :     char* NewMeta = new char[AllocSize];
    1958           0 :     BlockList = new (NewMeta) BlockMeta{BlockList, 0};
    1959             :   }
    1960             : 
    1961             :   void* allocateMassive(size_t NBytes) {
    1962           0 :     NBytes += sizeof(BlockMeta);
    1963           0 :     BlockMeta* NewMeta = reinterpret_cast<BlockMeta*>(new char[NBytes]);
    1964           0 :     BlockList->Next = new (NewMeta) BlockMeta{BlockList->Next, 0};
    1965           0 :     return static_cast<void*>(NewMeta + 1);
    1966             :   }
    1967             : 
    1968             : public:
    1969             :   BumpPointerAllocator()
    1970        3870 :       : BlockList(new (InitialBuffer) BlockMeta{nullptr, 0}) {}
    1971             : 
    1972       58506 :   void* allocate(size_t N) {
    1973       58506 :     N = (N + 15u) & ~15u;
    1974       58506 :     if (N + BlockList->Current >= UsableAllocSize) {
    1975           0 :       if (N > UsableAllocSize)
    1976           0 :         return allocateMassive(N);
    1977             :       grow();
    1978             :     }
    1979       58506 :     BlockList->Current += N;
    1980       58506 :     return static_cast<void*>(reinterpret_cast<char*>(BlockList + 1) +
    1981       58506 :                               BlockList->Current - N);
    1982             :   }
    1983             : 
    1984        3906 :   void reset() {
    1985        7812 :     while (BlockList) {
    1986             :       BlockMeta* Tmp = BlockList;
    1987        3906 :       BlockList = BlockList->Next;
    1988        3906 :       if (reinterpret_cast<char*>(Tmp) != InitialBuffer)
    1989           0 :         delete[] reinterpret_cast<char*>(Tmp);
    1990             :     }
    1991        3906 :     BlockList = new (InitialBuffer) BlockMeta{nullptr, 0};
    1992        3906 :   }
    1993             : 
    1994        3870 :   ~BumpPointerAllocator() { reset(); }
    1995             : };
    1996             : 
    1997             : template <class T, size_t N>
    1998             : class PODSmallVector {
    1999             :   static_assert(std::is_pod<T>::value,
    2000             :                 "T is required to be a plain old data type");
    2001             : 
    2002             :   T* First;
    2003             :   T* Last;
    2004             :   T* Cap;
    2005             :   T Inline[N];
    2006             : 
    2007       30715 :   bool isInline() const { return First == Inline; }
    2008             : 
    2009             :   void clearInline() {
    2010           0 :     First = Inline;
    2011           0 :     Last = Inline;
    2012           0 :     Cap = Inline + N;
    2013             :   }
    2014             : 
    2015           3 :   void reserve(size_t NewCap) {
    2016           3 :     size_t S = size();
    2017           3 :     if (isInline()) {
    2018           3 :       auto* Tmp = static_cast<T*>(std::malloc(NewCap * sizeof(T)));
    2019             :       std::copy(First, Last, Tmp);
    2020           3 :       First = Tmp;
    2021             :     } else
    2022           0 :       First = static_cast<T*>(std::realloc(First, NewCap * sizeof(T)));
    2023           3 :     Last = First + S;
    2024           3 :     Cap = First + NewCap;
    2025           3 :   }
    2026             : 
    2027             : public:
    2028        7678 :   PODSmallVector() : First(Inline), Last(First), Cap(Inline + N) {}
    2029             : 
    2030             :   PODSmallVector(const PODSmallVector&) = delete;
    2031             :   PODSmallVector& operator=(const PODSmallVector&) = delete;
    2032             : 
    2033        3808 :   PODSmallVector(PODSmallVector&& Other) : PODSmallVector() {
    2034        3808 :     if (Other.isInline()) {
    2035        3808 :       std::copy(Other.begin(), Other.end(), First);
    2036        7616 :       Last = First + Other.size();
    2037        3808 :       Other.clear();
    2038             :       return;
    2039             :     }
    2040             : 
    2041           0 :     First = Other.First;
    2042           0 :     Last = Other.Last;
    2043           0 :     Cap = Other.Cap;
    2044             :     Other.clearInline();
    2045             :   }
    2046             : 
    2047        3808 :   PODSmallVector& operator=(PODSmallVector&& Other) {
    2048        3808 :     if (Other.isInline()) {
    2049        3808 :       if (!isInline()) {
    2050           0 :         std::free(First);
    2051             :         clearInline();
    2052             :       }
    2053        3808 :       std::copy(Other.begin(), Other.end(), First);
    2054        7616 :       Last = First + Other.size();
    2055        3808 :       Other.clear();
    2056        3808 :       return *this;
    2057             :     }
    2058             : 
    2059           0 :     if (isInline()) {
    2060           0 :       First = Other.First;
    2061           0 :       Last = Other.Last;
    2062           0 :       Cap = Other.Cap;
    2063             :       Other.clearInline();
    2064           0 :       return *this;
    2065             :     }
    2066             : 
    2067             :     std::swap(First, Other.First);
    2068             :     std::swap(Last, Other.Last);
    2069             :     std::swap(Cap, Other.Cap);
    2070           0 :     Other.clear();
    2071           0 :     return *this;
    2072             :   }
    2073             : 
    2074       39496 :   void push_back(const T& Elem) {
    2075       39496 :     if (Last == Cap)
    2076           6 :       reserve(size() * 2);
    2077       39496 :     *Last++ = Elem;
    2078       39496 :   }
    2079             : 
    2080             :   void pop_back() {
    2081             :     assert(Last != First && "Popping empty vector!");
    2082        3791 :     --Last;
    2083             :   }
    2084             : 
    2085             :   void dropBack(size_t Index) {
    2086             :     assert(Index <= size() && "dropBack() can't expand!");
    2087       11295 :     Last = First + Index;
    2088             :   }
    2089             : 
    2090             :   T* begin() { return First; }
    2091             :   T* end() { return Last; }
    2092             : 
    2093             :   bool empty() const { return First == Last; }
    2094       26273 :   size_t size() const { return static_cast<size_t>(Last - First); }
    2095             :   T& back() {
    2096             :     assert(Last != First && "Calling back() on empty vector!");
    2097             :     return *(Last - 1);
    2098             :   }
    2099             :   T& operator[](size_t Index) {
    2100             :     assert(Index < size() && "Invalid access!");
    2101        2745 :     return *(begin() + Index);
    2102             :   }
    2103        9449 :   void clear() { Last = First; }
    2104             : 
    2105             :   ~PODSmallVector() {
    2106       19288 :     if (!isInline())
    2107           3 :       std::free(First);
    2108       11610 :   }
    2109             : };
    2110             : 
    2111        7740 : struct Db {
    2112             :   const char *First;
    2113             :   const char *Last;
    2114             : 
    2115             :   // Name stack, this is used by the parser to hold temporary names that were
    2116             :   // parsed. The parser collapses multiple names into new nodes to construct
    2117             :   // the AST. Once the parser is finished, names.size() == 1.
    2118             :   PODSmallVector<Node *, 32> Names;
    2119             : 
    2120             :   // Substitution table. Itanium supports name substitutions as a means of
    2121             :   // compression. The string "S42_" refers to the 44nd entry (base-36) in this
    2122             :   // table.
    2123             :   PODSmallVector<Node *, 32> Subs;
    2124             : 
    2125             :   // Template parameter table. Like the above, but referenced like "T42_".
    2126             :   // This has a smaller size compared to Subs and Names because it can be
    2127             :   // stored on the stack.
    2128             :   PODSmallVector<Node *, 8> TemplateParams;
    2129             : 
    2130             :   // Set of unresolved forward <template-param> references. These can occur in a
    2131             :   // conversion operator's type, and are resolved in the enclosing <encoding>.
    2132             :   PODSmallVector<ForwardTemplateReference *, 4> ForwardTemplateRefs;
    2133             : 
    2134             :   bool TryToParseTemplateArgs = true;
    2135             :   bool PermitForwardTemplateReferences = false;
    2136             :   bool ParsingLambdaParams = false;
    2137             : 
    2138             :   BumpPointerAllocator ASTAllocator;
    2139             : 
    2140        7740 :   Db(const char *First_, const char *Last_) : First(First_), Last(Last_) {}
    2141             : 
    2142             :   void reset(const char *First_, const char *Last_) {
    2143          36 :     First = First_;
    2144          36 :     Last = Last_;
    2145          36 :     Names.clear();
    2146          36 :     Subs.clear();
    2147          36 :     TemplateParams.clear();
    2148          36 :     ParsingLambdaParams = false;
    2149          36 :     TryToParseTemplateArgs = true;
    2150          36 :     PermitForwardTemplateReferences = false;
    2151          36 :     ASTAllocator.reset();
    2152             :   }
    2153             : 
    2154       50748 :   template <class T, class... Args> T *make(Args &&... args) {
    2155       50748 :     return new (ASTAllocator.allocate(sizeof(T)))
    2156       93268 :         T(std::forward<Args>(args)...);
    2157             :   }
    2158             : 
    2159        7758 :   template <class It> NodeArray makeNodeArray(It begin, It end) {
    2160        7758 :     size_t sz = static_cast<size_t>(end - begin);
    2161        7758 :     void *mem = ASTAllocator.allocate(sizeof(Node *) * sz);
    2162             :     Node **data = new (mem) Node *[sz];
    2163             :     std::copy(begin, end, data);
    2164        7758 :     return NodeArray(data, sz);
    2165             :   }
    2166             : 
    2167        7758 :   NodeArray popTrailingNodeArray(size_t FromPosition) {
    2168             :     assert(FromPosition <= Names.size());
    2169             :     NodeArray res =
    2170        7758 :         makeNodeArray(Names.begin() + (long)FromPosition, Names.end());
    2171        7758 :     Names.dropBack(FromPosition);
    2172        7758 :     return res;
    2173             :   }
    2174             : 
    2175             :   bool consumeIf(StringView S) {
    2176       58715 :     if (StringView(First, Last).startsWith(S)) {
    2177        6366 :       First += S.size();
    2178             :       return true;
    2179             :     }
    2180             :     return false;
    2181             :   }
    2182             : 
    2183             :   bool consumeIf(char C) {
    2184      126333 :     if (First != Last && *First == C) {
    2185       33060 :       ++First;
    2186             :       return true;
    2187             :     }
    2188             :     return false;
    2189             :   }
    2190             : 
    2191       15026 :   char consume() { return First != Last ? *First++ : '\0'; }
    2192             : 
    2193             :   char look(unsigned Lookahead = 0) {
    2194      213400 :     if (static_cast<size_t>(Last - First) <= Lookahead)
    2195             :       return '\0';
    2196      216986 :     return First[Lookahead];
    2197             :   }
    2198             : 
    2199       20967 :   size_t numLeft() const { return static_cast<size_t>(Last - First); }
    2200             : 
    2201             :   StringView parseNumber(bool AllowNegative = false);
    2202             :   Qualifiers parseCVQualifiers();
    2203             :   bool parsePositiveInteger(size_t *Out);
    2204             :   StringView parseBareSourceName();
    2205             : 
    2206             :   bool parseSeqId(size_t *Out);
    2207             :   Node *parseSubstitution();
    2208             :   Node *parseTemplateParam();
    2209             :   Node *parseTemplateArgs(bool TagTemplates = false);
    2210             :   Node *parseTemplateArg();
    2211             : 
    2212             :   /// Parse the <expr> production.
    2213             :   Node *parseExpr();
    2214             :   Node *parsePrefixExpr(StringView Kind);
    2215             :   Node *parseBinaryExpr(StringView Kind);
    2216             :   Node *parseIntegerLiteral(StringView Lit);
    2217             :   Node *parseExprPrimary();
    2218             :   template <class Float> Node *parseFloatingLiteral();
    2219             :   Node *parseFunctionParam();
    2220             :   Node *parseNewExpr();
    2221             :   Node *parseConversionExpr();
    2222             :   Node *parseBracedExpr();
    2223             :   Node *parseFoldExpr();
    2224             : 
    2225             :   /// Parse the <type> production.
    2226             :   Node *parseType();
    2227             :   Node *parseFunctionType();
    2228             :   Node *parseVectorType();
    2229             :   Node *parseDecltype();
    2230             :   Node *parseArrayType();
    2231             :   Node *parsePointerToMemberType();
    2232             :   Node *parseClassEnumType();
    2233             :   Node *parseQualifiedType();
    2234             : 
    2235             :   Node *parseEncoding();
    2236             :   bool parseCallOffset();
    2237             :   Node *parseSpecialName();
    2238             : 
    2239             :   /// Holds some extra information about a <name> that is being parsed. This
    2240             :   /// information is only pertinent if the <name> refers to an <encoding>.
    2241             :   struct NameState {
    2242             :     bool CtorDtorConversion = false;
    2243             :     bool EndsWithTemplateArgs = false;
    2244             :     Qualifiers CVQualifiers = QualNone;
    2245             :     FunctionRefQual ReferenceQualifier = FrefQualNone;
    2246             :     size_t ForwardTemplateRefsBegin;
    2247             : 
    2248             :     NameState(Db *Enclosing)
    2249        7074 :         : ForwardTemplateRefsBegin(Enclosing->ForwardTemplateRefs.size()) {}
    2250             :   };
    2251             : 
    2252        3537 :   bool resolveForwardTemplateRefs(NameState &State) {
    2253        3537 :     size_t I = State.ForwardTemplateRefsBegin;
    2254        3537 :     size_t E = ForwardTemplateRefs.size();
    2255        3539 :     for (; I < E; ++I) {
    2256           1 :       size_t Idx = ForwardTemplateRefs[I]->Index;
    2257           2 :       if (Idx >= TemplateParams.size())
    2258             :         return true;
    2259           1 :       ForwardTemplateRefs[I]->Ref = TemplateParams[Idx];
    2260             :     }
    2261             :     ForwardTemplateRefs.dropBack(State.ForwardTemplateRefsBegin);
    2262             :     return false;
    2263             :   }
    2264             : 
    2265             :   /// Parse the <name> production>
    2266             :   Node *parseName(NameState *State = nullptr);
    2267             :   Node *parseLocalName(NameState *State);
    2268             :   Node *parseOperatorName(NameState *State);
    2269             :   Node *parseUnqualifiedName(NameState *State);
    2270             :   Node *parseUnnamedTypeName(NameState *State);
    2271             :   Node *parseSourceName(NameState *State);
    2272             :   Node *parseUnscopedName(NameState *State);
    2273             :   Node *parseNestedName(NameState *State);
    2274             :   Node *parseCtorDtorName(Node *&SoFar, NameState *State);
    2275             : 
    2276             :   Node *parseAbiTags(Node *N);
    2277             : 
    2278             :   /// Parse the <unresolved-name> production.
    2279             :   Node *parseUnresolvedName();
    2280             :   Node *parseSimpleId();
    2281             :   Node *parseBaseUnresolvedName();
    2282             :   Node *parseUnresolvedType();
    2283             :   Node *parseDestructorName();
    2284             : 
    2285             :   /// Top-level entry point into the parser.
    2286             :   Node *parse();
    2287             : };
    2288             : 
    2289             : const char* parse_discriminator(const char* first, const char* last);
    2290             : 
    2291             : // <name> ::= <nested-name> // N
    2292             : //        ::= <local-name> # See Scope Encoding below  // Z
    2293             : //        ::= <unscoped-template-name> <template-args>
    2294             : //        ::= <unscoped-name>
    2295             : //
    2296             : // <unscoped-template-name> ::= <unscoped-name>
    2297             : //                          ::= <substitution>
    2298        8712 : Node *Db::parseName(NameState *State) {
    2299             :   consumeIf('L'); // extension
    2300             : 
    2301       17424 :   if (look() == 'N')
    2302        3792 :     return parseNestedName(State);
    2303        4920 :   if (look() == 'Z')
    2304           9 :     return parseLocalName(State);
    2305             : 
    2306             :   //        ::= <unscoped-template-name> <template-args>
    2307        7979 :   if (look() == 'S' && look(1) != 't') {
    2308           0 :     Node *S = parseSubstitution();
    2309           0 :     if (S == nullptr)
    2310             :       return nullptr;
    2311           0 :     if (look() != 'I')
    2312             :       return nullptr;
    2313           0 :     Node *TA = parseTemplateArgs(State != nullptr);
    2314           0 :     if (TA == nullptr)
    2315             :       return nullptr;
    2316           0 :     if (State) State->EndsWithTemplateArgs = true;
    2317           0 :     return make<NameWithTemplateArgs>(S, TA);
    2318             :   }
    2319             : 
    2320        4911 :   Node *N = parseUnscopedName(State);
    2321        4911 :   if (N == nullptr)
    2322             :     return nullptr;
    2323             :   //        ::= <unscoped-template-name> <template-args>
    2324        7643 :   if (look() == 'I') {
    2325        2459 :     Subs.push_back(N);
    2326        2459 :     Node *TA = parseTemplateArgs(State != nullptr);
    2327        2459 :     if (TA == nullptr)
    2328             :       return nullptr;
    2329        2459 :     if (State) State->EndsWithTemplateArgs = true;
    2330        2459 :     return make<NameWithTemplateArgs>(N, TA);
    2331             :   }
    2332             :   //        ::= <unscoped-name>
    2333             :   return N;
    2334             : }
    2335             : 
    2336             : // <local-name> := Z <function encoding> E <entity name> [<discriminator>]
    2337             : //              := Z <function encoding> E s [<discriminator>]
    2338             : //              := Z <function encoding> Ed [ <parameter number> ] _ <entity name>
    2339           9 : Node *Db::parseLocalName(NameState *State) {
    2340             :   if (!consumeIf('Z'))
    2341             :     return nullptr;
    2342           9 :   Node *Encoding = parseEncoding();
    2343           9 :   if (Encoding == nullptr || !consumeIf('E'))
    2344             :     return nullptr;
    2345             : 
    2346             :   if (consumeIf('s')) {
    2347           0 :     First = parse_discriminator(First, Last);
    2348           0 :     return make<LocalName>(Encoding, make<NameType>("string literal"));
    2349             :   }
    2350             : 
    2351             :   if (consumeIf('d')) {
    2352           1 :     parseNumber(true);
    2353             :     if (!consumeIf('_'))
    2354             :       return nullptr;
    2355           1 :     Node *N = parseName(State);
    2356           1 :     if (N == nullptr)
    2357             :       return nullptr;
    2358           1 :     return make<LocalName>(Encoding, N);
    2359             :   }
    2360             : 
    2361           8 :   Node *Entity = parseName(State);
    2362           8 :   if (Entity == nullptr)
    2363             :     return nullptr;
    2364           8 :   First = parse_discriminator(First, Last);
    2365           8 :   return make<LocalName>(Encoding, Entity);
    2366             : }
    2367             : 
    2368             : // <unscoped-name> ::= <unqualified-name>
    2369             : //                 ::= St <unqualified-name>   # ::std::
    2370             : // extension       ::= StL<unqualified-name>
    2371        4911 : Node *Db::parseUnscopedName(NameState *State) {
    2372        4911 :  if (consumeIf("StL") || consumeIf("St")) {
    2373        3068 :    Node *R = parseUnqualifiedName(State);
    2374        3068 :    if (R == nullptr)
    2375             :      return nullptr;
    2376        3068 :    return make<StdQualifiedName>(R);
    2377             :  }
    2378        1843 :  return parseUnqualifiedName(State);
    2379             : }
    2380             : 
    2381             : // <unqualified-name> ::= <operator-name> [abi-tags]
    2382             : //                    ::= <ctor-dtor-name>
    2383             : //                    ::= <source-name>
    2384             : //                    ::= <unnamed-type-name>
    2385             : //                    ::= DC <source-name>+ E      # structured binding declaration
    2386       11426 : Node *Db::parseUnqualifiedName(NameState *State) {
    2387             :  // <ctor-dtor-name>s are special-cased in parseNestedName().
    2388             :  Node *Result;
    2389       22852 :  if (look() == 'U')
    2390           6 :    Result = parseUnnamedTypeName(State);
    2391       11420 :  else if (look() >= '1' && look() <= '9')
    2392        9741 :    Result = parseSourceName(State);
    2393             :  else if (consumeIf("DC")) {
    2394           1 :    size_t BindingsBegin = Names.size();
    2395             :    do {
    2396           3 :      Node *Binding = parseSourceName(State);
    2397           3 :      if (Binding == nullptr)
    2398           0 :        return nullptr;
    2399           3 :      Names.push_back(Binding);
    2400             :    } while (!consumeIf('E'));
    2401           1 :    Result = make<StructuredBindingName>(popTrailingNodeArray(BindingsBegin));
    2402             :  } else
    2403        1678 :    Result = parseOperatorName(State);
    2404       11426 :  if (Result != nullptr)
    2405       10350 :    Result = parseAbiTags(Result);
    2406             :  return Result;
    2407             : }
    2408             : 
    2409             : // <unnamed-type-name> ::= Ut [<nonnegative number>] _
    2410             : //                     ::= <closure-type-name>
    2411             : //
    2412             : // <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
    2413             : //
    2414             : // <lambda-sig> ::= <parameter type>+  # Parameter types or "v" if the lambda has no parameters
    2415           6 : Node *Db::parseUnnamedTypeName(NameState *) {
    2416           6 :   if (consumeIf("Ut")) {
    2417           0 :     StringView Count = parseNumber();
    2418             :     if (!consumeIf('_'))
    2419             :       return nullptr;
    2420           0 :     return make<UnnamedTypeName>(Count);
    2421             :   }
    2422             :   if (consumeIf("Ul")) {
    2423             :     NodeArray Params;
    2424           6 :     SwapAndRestore<bool> SwapParams(ParsingLambdaParams, true);
    2425             :     if (!consumeIf("vE")) {
    2426           0 :       size_t ParamsBegin = Names.size();
    2427             :       do {
    2428           0 :         Node *P = parseType();
    2429           0 :         if (P == nullptr)
    2430           0 :           return nullptr;
    2431           0 :         Names.push_back(P);
    2432             :       } while (!consumeIf('E'));
    2433           0 :       Params = popTrailingNodeArray(ParamsBegin);
    2434             :     }
    2435           6 :     StringView Count = parseNumber();
    2436             :     if (!consumeIf('_'))
    2437             :       return nullptr;
    2438           6 :     return make<ClosureTypeName>(Params, Count);
    2439             :   }
    2440             :   return nullptr;
    2441             : }
    2442             : 
    2443             : // <source-name> ::= <positive length number> <identifier>
    2444        9811 : Node *Db::parseSourceName(NameState *) {
    2445        9811 :   size_t Length = 0;
    2446        9811 :   if (parsePositiveInteger(&Length))
    2447             :     return nullptr;
    2448       19622 :   if (numLeft() < Length || Length == 0)
    2449             :     return nullptr;
    2450        9811 :   StringView Name(First, First + Length);
    2451        9811 :   First += Length;
    2452        9811 :   if (Name.startsWith("_GLOBAL__N"))
    2453          13 :     return make<NameType>("(anonymous namespace)");
    2454        9798 :   return make<NameType>(Name);
    2455             : }
    2456             : 
    2457             : //   <operator-name> ::= aa    # &&
    2458             : //                   ::= ad    # & (unary)
    2459             : //                   ::= an    # &
    2460             : //                   ::= aN    # &=
    2461             : //                   ::= aS    # =
    2462             : //                   ::= cl    # ()
    2463             : //                   ::= cm    # ,
    2464             : //                   ::= co    # ~
    2465             : //                   ::= cv <type>    # (cast)
    2466             : //                   ::= da    # delete[]
    2467             : //                   ::= de    # * (unary)
    2468             : //                   ::= dl    # delete
    2469             : //                   ::= dv    # /
    2470             : //                   ::= dV    # /=
    2471             : //                   ::= eo    # ^
    2472             : //                   ::= eO    # ^=
    2473             : //                   ::= eq    # ==
    2474             : //                   ::= ge    # >=
    2475             : //                   ::= gt    # >
    2476             : //                   ::= ix    # []
    2477             : //                   ::= le    # <=
    2478             : //                   ::= li <source-name>  # operator ""
    2479             : //                   ::= ls    # <<
    2480             : //                   ::= lS    # <<=
    2481             : //                   ::= lt    # <
    2482             : //                   ::= mi    # -
    2483             : //                   ::= mI    # -=
    2484             : //                   ::= ml    # *
    2485             : //                   ::= mL    # *=
    2486             : //                   ::= mm    # -- (postfix in <expression> context)
    2487             : //                   ::= na    # new[]
    2488             : //                   ::= ne    # !=
    2489             : //                   ::= ng    # - (unary)
    2490             : //                   ::= nt    # !
    2491             : //                   ::= nw    # new
    2492             : //                   ::= oo    # ||
    2493             : //                   ::= or    # |
    2494             : //                   ::= oR    # |=
    2495             : //                   ::= pm    # ->*
    2496             : //                   ::= pl    # +
    2497             : //                   ::= pL    # +=
    2498             : //                   ::= pp    # ++ (postfix in <expression> context)
    2499             : //                   ::= ps    # + (unary)
    2500             : //                   ::= pt    # ->
    2501             : //                   ::= qu    # ?
    2502             : //                   ::= rm    # %
    2503             : //                   ::= rM    # %=
    2504             : //                   ::= rs    # >>
    2505             : //                   ::= rS    # >>=
    2506             : //                   ::= ss    # <=> C++2a
    2507             : //                   ::= v <digit> <source-name>        # vendor extended operator
    2508        1678 : Node *Db::parseOperatorName(NameState *State) {
    2509        3356 :   switch (look()) {
    2510           7 :   case 'a':
    2511           7 :     switch (look(1)) {
    2512           0 :     case 'a':
    2513           0 :       First += 2;
    2514           0 :       return make<NameType>("operator&&");
    2515           0 :     case 'd':
    2516             :     case 'n':
    2517           0 :       First += 2;
    2518           0 :       return make<NameType>("operator&");
    2519           0 :     case 'N':
    2520           0 :       First += 2;
    2521           0 :       return make<NameType>("operator&=");
    2522           7 :     case 'S':
    2523           7 :       First += 2;
    2524           7 :       return make<NameType>("operator=");
    2525             :     }
    2526             :     return nullptr;
    2527          15 :   case 'c':
    2528          15 :     switch (look(1)) {
    2529          14 :     case 'l':
    2530          14 :       First += 2;
    2531          14 :       return make<NameType>("operator()");
    2532           0 :     case 'm':
    2533           0 :       First += 2;
    2534           0 :       return make<NameType>("operator,");
    2535           0 :     case 'o':
    2536           0 :       First += 2;
    2537           0 :       return make<NameType>("operator~");
    2538             :     //                   ::= cv <type>    # (cast)
    2539           1 :     case 'v': {
    2540           1 :       First += 2;
    2541           1 :       SwapAndRestore<bool> SaveTemplate(TryToParseTemplateArgs, false);
    2542             :       // If we're parsing an encoding, State != nullptr and the conversion
    2543             :       // operators' <type> could have a <template-param> that refers to some
    2544             :       // <template-arg>s further ahead in the mangled name.
    2545             :       SwapAndRestore<bool> SavePermit(PermitForwardTemplateReferences,
    2546           1 :                                       PermitForwardTemplateReferences ||
    2547           1 :                                           State != nullptr);
    2548           1 :       Node* Ty = parseType();
    2549           1 :       if (Ty == nullptr)
    2550             :         return nullptr;
    2551           1 :       if (State) State->CtorDtorConversion = true;
    2552           1 :       return make<ConversionOperatorType>(Ty);
    2553             :     }
    2554             :     }
    2555             :     return nullptr;
    2556         220 :   case 'd':
    2557         220 :     switch (look(1)) {
    2558          14 :     case 'a':
    2559          14 :       First += 2;
    2560          14 :       return make<NameType>("operator delete[]");
    2561           4 :     case 'e':
    2562           4 :       First += 2;
    2563           4 :       return make<NameType>("operator*");
    2564         202 :     case 'l':
    2565         202 :       First += 2;
    2566         202 :       return make<NameType>("operator delete");
    2567           0 :     case 'v':
    2568           0 :       First += 2;
    2569           0 :       return make<NameType>("operator/");
    2570           0 :     case 'V':
    2571           0 :       First += 2;
    2572           0 :       return make<NameType>("operator/=");
    2573             :     }
    2574             :     return nullptr;
    2575           5 :   case 'e':
    2576           5 :     switch (look(1)) {
    2577           0 :     case 'o':
    2578           0 :       First += 2;
    2579           0 :       return make<NameType>("operator^");
    2580           0 :     case 'O':
    2581           0 :       First += 2;
    2582           0 :       return make<NameType>("operator^=");
    2583           5 :     case 'q':
    2584           5 :       First += 2;
    2585           5 :       return make<NameType>("operator==");
    2586             :     }
    2587             :     return nullptr;
    2588           0 :   case 'g':
    2589           0 :     switch (look(1)) {
    2590           0 :     case 'e':
    2591           0 :       First += 2;
    2592           0 :       return make<NameType>("operator>=");
    2593           0 :     case 't':
    2594           0 :       First += 2;
    2595           0 :       return make<NameType>("operator>");
    2596             :     }
    2597             :     return nullptr;
    2598          10 :   case 'i':
    2599          10 :     if (look(1) == 'x') {
    2600          10 :       First += 2;
    2601          10 :       return make<NameType>("operator[]");
    2602             :     }
    2603             :     return nullptr;
    2604          84 :   case 'l':
    2605          84 :     switch (look(1)) {
    2606           0 :     case 'e':
    2607           0 :       First += 2;
    2608           0 :       return make<NameType>("operator<=");
    2609             :     //                   ::= li <source-name>  # operator ""
    2610           0 :     case 'i': {
    2611           0 :       First += 2;
    2612           0 :       Node *SN = parseSourceName(State);
    2613           0 :       if (SN == nullptr)
    2614             :         return nullptr;
    2615           0 :       return make<LiteralOperator>(SN);
    2616             :     }
    2617          83 :     case 's':
    2618          83 :       First += 2;
    2619          83 :       return make<NameType>("operator<<");
    2620           0 :     case 'S':
    2621           0 :       First += 2;
    2622           0 :       return make<NameType>("operator<<=");
    2623           1 :     case 't':
    2624           1 :       First += 2;
    2625           1 :       return make<NameType>("operator<");
    2626             :     }
    2627             :     return nullptr;
    2628          11 :   case 'm':
    2629          11 :     switch (look(1)) {
    2630           8 :     case 'i':
    2631           8 :       First += 2;
    2632           8 :       return make<NameType>("operator-");
    2633           0 :     case 'I':
    2634           0 :       First += 2;
    2635           0 :       return make<NameType>("operator-=");
    2636           0 :     case 'l':
    2637           0 :       First += 2;
    2638           0 :       return make<NameType>("operator*");
    2639           0 :     case 'L':
    2640           0 :       First += 2;
    2641           0 :       return make<NameType>("operator*=");
    2642           3 :     case 'm':
    2643           3 :       First += 2;
    2644           3 :       return make<NameType>("operator--");
    2645             :     }
    2646             :     return nullptr;
    2647         236 :   case 'n':
    2648         236 :     switch (look(1)) {
    2649          28 :     case 'a':
    2650          28 :       First += 2;
    2651          28 :       return make<NameType>("operator new[]");
    2652           1 :     case 'e':
    2653           1 :       First += 2;
    2654           1 :       return make<NameType>("operator!=");
    2655           0 :     case 'g':
    2656           0 :       First += 2;
    2657           0 :       return make<NameType>("operator-");
    2658           0 :     case 't':
    2659           0 :       First += 2;
    2660           0 :       return make<NameType>("operator!");
    2661         207 :     case 'w':
    2662         207 :       First += 2;
    2663         207 :       return make<NameType>("operator new");
    2664             :     }
    2665             :     return nullptr;
    2666           1 :   case 'o':
    2667           1 :     switch (look(1)) {
    2668           0 :     case 'o':
    2669           0 :       First += 2;
    2670           0 :       return make<NameType>("operator||");
    2671           0 :     case 'r':
    2672           0 :       First += 2;
    2673           0 :       return make<NameType>("operator|");
    2674           0 :     case 'R':
    2675           0 :       First += 2;
    2676           0 :       return make<NameType>("operator|=");
    2677             :     }
    2678             :     return nullptr;
    2679           4 :   case 'p':
    2680           4 :     switch (look(1)) {
    2681           0 :     case 'm':
    2682           0 :       First += 2;
    2683           0 :       return make<NameType>("operator->*");
    2684           0 :     case 'l':
    2685           0 :       First += 2;
    2686           0 :       return make<NameType>("operator+");
    2687           0 :     case 'L':
    2688           0 :       First += 2;
    2689           0 :       return make<NameType>("operator+=");
    2690           4 :     case 'p':
    2691           4 :       First += 2;
    2692           4 :       return make<NameType>("operator++");
    2693           0 :     case 's':
    2694           0 :       First += 2;
    2695           0 :       return make<NameType>("operator+");
    2696           0 :     case 't':
    2697           0 :       First += 2;
    2698           0 :       return make<NameType>("operator->");
    2699             :     }
    2700             :     return nullptr;
    2701          10 :   case 'q':
    2702          10 :     if (look(1) == 'u') {
    2703          10 :       First += 2;
    2704          10 :       return make<NameType>("operator?");
    2705             :     }
    2706             :     return nullptr;
    2707           0 :   case 'r':
    2708           0 :     switch (look(1)) {
    2709           0 :     case 'm':
    2710           0 :       First += 2;
    2711           0 :       return make<NameType>("operator%");
    2712           0 :     case 'M':
    2713           0 :       First += 2;
    2714           0 :       return make<NameType>("operator%=");
    2715           0 :     case 's':
    2716           0 :       First += 2;
    2717           0 :       return make<NameType>("operator>>");
    2718           0 :     case 'S':
    2719           0 :       First += 2;
    2720           0 :       return make<NameType>("operator>>=");
    2721             :     }
    2722             :     return nullptr;
    2723           0 :   case 's':
    2724           0 :     if (look(1) == 's') {
    2725           0 :       First += 2;
    2726           0 :       return make<NameType>("operator<=>");
    2727             :     }
    2728             :     return nullptr;
    2729             :   // ::= v <digit> <source-name>        # vendor extended operator
    2730           0 :   case 'v':
    2731           0 :     if (std::isdigit(look(1))) {
    2732           0 :       First += 2;
    2733           0 :       Node *SN = parseSourceName(State);
    2734           0 :       if (SN == nullptr)
    2735             :         return nullptr;
    2736           0 :       return make<ConversionOperatorType>(SN);
    2737             :     }
    2738             :     return nullptr;
    2739             :   }
    2740             :   return nullptr;
    2741             : }
    2742             : 
    2743             : // <ctor-dtor-name> ::= C1  # complete object constructor
    2744             : //                  ::= C2  # base object constructor
    2745             : //                  ::= C3  # complete object allocating constructor
    2746             : //   extension      ::= C5    # ?
    2747             : //                  ::= D0  # deleting destructor
    2748             : //                  ::= D1  # complete object destructor
    2749             : //                  ::= D2  # base object destructor
    2750             : //   extension      ::= D5    # ?
    2751        1087 : Node *Db::parseCtorDtorName(Node *&SoFar, NameState *State) {
    2752        1087 :   if (SoFar->K == Node::KSpecialSubstitution) {
    2753           1 :     auto SSK = static_cast<SpecialSubstitution *>(SoFar)->SSK;
    2754           1 :     switch (SSK) {
    2755           1 :     case SpecialSubKind::string:
    2756             :     case SpecialSubKind::istream:
    2757             :     case SpecialSubKind::ostream:
    2758             :     case SpecialSubKind::iostream:
    2759           1 :       SoFar = make<ExpandedSpecialSubstitution>(SSK);
    2760             :     default:
    2761             :       break;
    2762             :     }
    2763             :   }
    2764             : 
    2765             :   if (consumeIf('C')) {
    2766             :     bool IsInherited = consumeIf('I');
    2767        1370 :     if (look() != '1' && look() != '2' && look() != '3' && look() != '5')
    2768             :       return nullptr;
    2769         585 :     ++First;
    2770         585 :     if (State) State->CtorDtorConversion = true;
    2771         585 :     if (IsInherited) {
    2772           1 :       if (parseName(State) == nullptr)
    2773             :         return nullptr;
    2774             :     }
    2775         585 :     return make<CtorDtorName>(SoFar, false);
    2776             :   }
    2777             : 
    2778        1004 :   if (look() == 'D' &&
    2779         630 :       (look(1) == '0' || look(1) == '1' || look(1) == '2' || look(1) == '5')) {
    2780         502 :     First += 2;
    2781         502 :     if (State) State->CtorDtorConversion = true;
    2782         502 :     return make<CtorDtorName>(SoFar, true);
    2783             :   }
    2784             : 
    2785             :   return nullptr;
    2786             : }
    2787             : 
    2788             : // <nested-name> ::= N [<CV-Qualifiers>] [<ref-qualifier>] <prefix> <unqualified-name> E
    2789             : //               ::= N [<CV-Qualifiers>] [<ref-qualifier>] <template-prefix> <template-args> E
    2790             : //
    2791             : // <prefix> ::= <prefix> <unqualified-name>
    2792             : //          ::= <template-prefix> <template-args>
    2793             : //          ::= <template-param>
    2794             : //          ::= <decltype>
    2795             : //          ::= # empty
    2796             : //          ::= <substitution>
    2797             : //          ::= <prefix> <data-member-prefix>
    2798             : //  extension ::= L
    2799             : //
    2800             : // <data-member-prefix> := <member source-name> [<template-args>] M
    2801             : //
    2802             : // <template-prefix> ::= <prefix> <template unqualified-name>
    2803             : //                   ::= <template-param>
    2804             : //                   ::= <substitution>
    2805        3792 : Node *Db::parseNestedName(NameState *State) {
    2806             :   if (!consumeIf('N'))
    2807             :     return nullptr;
    2808             : 
    2809        3792 :   Qualifiers CVTmp = parseCVQualifiers();
    2810        3792 :   if (State) State->CVQualifiers = CVTmp;
    2811             : 
    2812             :   if (consumeIf('O')) {
    2813           0 :     if (State) State->ReferenceQualifier = FrefQualRValue;
    2814             :   } else if (consumeIf('R')) {
    2815           1 :     if (State) State->ReferenceQualifier = FrefQualLValue;
    2816             :   } else
    2817        3791 :     if (State) State->ReferenceQualifier = FrefQualNone;
    2818             : 
    2819        3792 :   Node *SoFar = nullptr;
    2820        8476 :   auto PushComponent = [&](Node *Comp) {
    2821        8476 :     if (SoFar) SoFar = make<NestedName>(SoFar, Comp);
    2822        1451 :     else       SoFar = Comp;
    2823        8476 :     if (State) State->EndsWithTemplateArgs = false;
    2824       12268 :   };
    2825             : 
    2826        3792 :   if (consumeIf("St"))
    2827        2340 :     SoFar = make<NameType>("std");
    2828             : 
    2829             :   while (!consumeIf('E')) {
    2830             :     consumeIf('L'); // extension
    2831             : 
    2832             :     // <data-member-prefix> := <member source-name> [<template-args>] M
    2833           0 :     if (consumeIf('M')) {
    2834           0 :       if (SoFar == nullptr)
    2835             :         return nullptr;
    2836           0 :       continue;
    2837             :     }
    2838             : 
    2839             :     //          ::= <template-param>
    2840       10749 :     if (look() == 'T') {
    2841           0 :       Node *TP = parseTemplateParam();
    2842           0 :       if (TP == nullptr)
    2843             :         return nullptr;
    2844           0 :       PushComponent(TP);
    2845           0 :       Subs.push_back(SoFar);
    2846           0 :       continue;
    2847             :     }
    2848             : 
    2849             :     //          ::= <template-prefix> <template-args>
    2850       10749 :     if (look() == 'I') {
    2851        2272 :       Node *TA = parseTemplateArgs(State != nullptr);
    2852        2272 :       if (TA == nullptr || SoFar == nullptr)
    2853             :         return nullptr;
    2854        2272 :       SoFar = make<NameWithTemplateArgs>(SoFar, TA);
    2855        2272 :       if (State) State->EndsWithTemplateArgs = true;
    2856        2272 :       Subs.push_back(SoFar);
    2857        2272 :       continue;
    2858             :     }
    2859             : 
    2860             :     //          ::= <decltype>
    2861        9483 :     if (look() == 'D' && (look(1) == 't' || look(1) == 'T')) {
    2862           0 :       Node *DT = parseDecltype();
    2863           0 :       if (DT == nullptr)
    2864             :         return nullptr;
    2865           0 :       PushComponent(DT);
    2866           0 :       Subs.push_back(SoFar);
    2867           0 :       continue;
    2868             :     }
    2869             : 
    2870             :     //          ::= <substitution>
    2871        9352 :     if (look() == 'S' && look(1) != 't') {
    2872         875 :       Node *S = parseSubstitution();
    2873         875 :       if (S == nullptr)
    2874           0 :         return nullptr;
    2875         875 :       PushComponent(S);
    2876         875 :       if (SoFar != S)
    2877           0 :         Subs.push_back(S);
    2878         875 :       continue;
    2879             :     }
    2880             : 
    2881             :     // Parse an <unqualified-name> thats actually a <ctor-dtor-name>.
    2882       15122 :     if (look() == 'C' || (look() == 'D' && look(1) != 'C')) {
    2883        1087 :       if (SoFar == nullptr)
    2884             :         return nullptr;
    2885        1087 :       Node *CtorDtor = parseCtorDtorName(SoFar, State);
    2886        1087 :       if (CtorDtor == nullptr)
    2887             :         return nullptr;
    2888        1087 :       PushComponent(CtorDtor);
    2889        1087 :       SoFar = parseAbiTags(SoFar);
    2890        1087 :       if (SoFar == nullptr)
    2891             :         return nullptr;
    2892        1087 :       Subs.push_back(SoFar);
    2893        1087 :       continue;
    2894             :     }
    2895             : 
    2896             :     //          ::= <prefix> <unqualified-name>
    2897        6515 :     Node *N = parseUnqualifiedName(State);
    2898        6515 :     if (N == nullptr)
    2899             :       return nullptr;
    2900        6514 :     PushComponent(N);
    2901        6514 :     Subs.push_back(SoFar);
    2902             :   }
    2903             : 
    2904        7582 :   if (SoFar == nullptr || Subs.empty())
    2905             :     return nullptr;
    2906             : 
    2907             :   Subs.pop_back();
    2908        3791 :   return SoFar;
    2909             : }
    2910             : 
    2911             : // <simple-id> ::= <source-name> [ <template-args> ]
    2912          67 : Node *Db::parseSimpleId() {
    2913          67 :   Node *SN = parseSourceName(/*NameState=*/nullptr);
    2914          67 :   if (SN == nullptr)
    2915             :     return nullptr;
    2916         134 :   if (look() == 'I') {
    2917          30 :     Node *TA = parseTemplateArgs();
    2918          30 :     if (TA == nullptr)
    2919             :       return nullptr;
    2920          30 :     return make<NameWithTemplateArgs>(SN, TA);
    2921             :   }
    2922             :   return SN;
    2923             : }
    2924             : 
    2925             : // <destructor-name> ::= <unresolved-type>  # e.g., ~T or ~decltype(f())
    2926             : //                   ::= <simple-id>        # e.g., ~A<2*N>
    2927           0 : Node *Db::parseDestructorName() {
    2928             :   Node *Result;
    2929           0 :   if (std::isdigit(look()))
    2930           0 :     Result = parseSimpleId();
    2931             :   else
    2932           0 :     Result = parseUnresolvedType();
    2933           0 :   if (Result == nullptr)
    2934             :     return nullptr;
    2935           0 :   return make<DtorName>(Result);
    2936             : }
    2937             : 
    2938             : // <unresolved-type> ::= <template-param>
    2939             : //                   ::= <decltype>
    2940             : //                   ::= <substitution>
    2941           0 : Node *Db::parseUnresolvedType() {
    2942           0 :   if (look() == 'T') {
    2943           0 :     Node *TP = parseTemplateParam();
    2944           0 :     if (TP == nullptr)
    2945             :       return nullptr;
    2946           0 :     Subs.push_back(TP);
    2947           0 :     return TP;
    2948             :   }
    2949           0 :   if (look() == 'D') {
    2950           0 :     Node *DT = parseDecltype();
    2951           0 :     if (DT == nullptr)
    2952             :       return nullptr;
    2953           0 :     Subs.push_back(DT);
    2954           0 :     return DT;
    2955             :   }
    2956           0 :   return parseSubstitution();
    2957             : }
    2958             : 
    2959             : // <base-unresolved-name> ::= <simple-id>                                # unresolved name
    2960             : //          extension     ::= <operator-name>                            # unresolved operator-function-id
    2961             : //          extension     ::= <operator-name> <template-args>            # unresolved operator template-id
    2962             : //                        ::= on <operator-name>                         # unresolved operator-function-id
    2963             : //                        ::= on <operator-name> <template-args>         # unresolved operator template-id
    2964             : //                        ::= dn <destructor-name>                       # destructor or pseudo-destructor;
    2965             : //                                                                         # e.g. ~X or ~X<N-1>
    2966          37 : Node *Db::parseBaseUnresolvedName() {
    2967          74 :   if (std::isdigit(look()))
    2968          37 :     return parseSimpleId();
    2969             : 
    2970             :   if (consumeIf("dn"))
    2971           0 :     return parseDestructorName();
    2972             : 
    2973             :   consumeIf("on");
    2974             : 
    2975           0 :   Node *Oper = parseOperatorName(/*NameState=*/nullptr);
    2976           0 :   if (Oper == nullptr)
    2977             :     return nullptr;
    2978           0 :   if (look() == 'I') {
    2979           0 :     Node *TA = parseTemplateArgs();
    2980           0 :     if (TA == nullptr)
    2981             :       return nullptr;
    2982           0 :     return make<NameWithTemplateArgs>(Oper, TA);
    2983             :   }
    2984             :   return Oper;
    2985             : }
    2986             : 
    2987             : // <unresolved-name>
    2988             : //  extension        ::= srN <unresolved-type> [<template-args>] <unresolved-qualifier-level>* E <base-unresolved-name>
    2989             : //                   ::= [gs] <base-unresolved-name>                     # x or (with "gs") ::x
    2990             : //                   ::= [gs] sr <unresolved-qualifier-level>+ E <base-unresolved-name>  
    2991             : //                                                                       # A::x, N::y, A<T>::z; "gs" means leading "::"
    2992             : //                   ::= sr <unresolved-type> <base-unresolved-name>     # T::x / decltype(p)::x
    2993             : //  extension        ::= sr <unresolved-type> <template-args> <base-unresolved-name>
    2994             : //                                                                       # T::N::x /decltype(p)::N::x
    2995             : //  (ignored)        ::= srN <unresolved-type>  <unresolved-qualifier-level>+ E <base-unresolved-name>
    2996             : //
    2997             : // <unresolved-qualifier-level> ::= <simple-id>
    2998          37 : Node *Db::parseUnresolvedName() {
    2999             :   Node *SoFar = nullptr;
    3000             : 
    3001             :   // srN <unresolved-type> [<template-args>] <unresolved-qualifier-level>* E <base-unresolved-name>
    3002             :   // srN <unresolved-type>                   <unresolved-qualifier-level>+ E <base-unresolved-name>
    3003          37 :   if (consumeIf("srN")) {
    3004           0 :     SoFar = parseUnresolvedType();
    3005           0 :     if (SoFar == nullptr)
    3006             :       return nullptr;
    3007             : 
    3008           0 :     if (look() == 'I') {
    3009           0 :       Node *TA = parseTemplateArgs();
    3010           0 :       if (TA == nullptr)
    3011             :         return nullptr;
    3012           0 :       SoFar = make<NameWithTemplateArgs>(SoFar, TA);
    3013             :     }
    3014             : 
    3015           0 :     while (!consumeIf('E')) {
    3016           0 :       Node *Qual = parseSimpleId();
    3017           0 :       if (Qual == nullptr)
    3018             :         return nullptr;
    3019           0 :       SoFar = make<QualifiedName>(SoFar, Qual);
    3020             :     }
    3021             : 
    3022           0 :     Node *Base = parseBaseUnresolvedName();
    3023           0 :     if (Base == nullptr)
    3024             :       return nullptr;
    3025           0 :     return make<QualifiedName>(SoFar, Base);
    3026             :   }
    3027             : 
    3028             :   bool Global = consumeIf("gs");
    3029             : 
    3030             :   // [gs] <base-unresolved-name>                     # x or (with "gs") ::x
    3031             :   if (!consumeIf("sr")) {
    3032           7 :     SoFar = parseBaseUnresolvedName();
    3033           7 :     if (SoFar == nullptr)
    3034             :       return nullptr;
    3035           7 :     if (Global)
    3036           0 :       SoFar = make<GlobalQualifiedName>(SoFar);
    3037             :     return SoFar;
    3038             :   }
    3039             : 
    3040             :   // [gs] sr <unresolved-qualifier-level>+ E   <base-unresolved-name>  
    3041          30 :   if (std::isdigit(look())) {
    3042             :     do {
    3043          30 :       Node *Qual = parseSimpleId();
    3044          30 :       if (Qual == nullptr)
    3045             :         return nullptr;
    3046          30 :       if (SoFar)
    3047           0 :         SoFar = make<QualifiedName>(SoFar, Qual);
    3048          30 :       else if (Global)
    3049           0 :         SoFar = make<GlobalQualifiedName>(Qual);
    3050             :       else
    3051             :         SoFar = Qual;
    3052             :     } while (!consumeIf('E'));
    3053             :   }
    3054             :   //      sr <unresolved-type>                 <base-unresolved-name>
    3055             :   //      sr <unresolved-type> <template-args> <base-unresolved-name>
    3056             :   else {
    3057           0 :     SoFar = parseUnresolvedType();
    3058           0 :     if (SoFar == nullptr)
    3059             :       return nullptr;
    3060             : 
    3061           0 :     if (look() == 'I') {
    3062           0 :       Node *TA = parseTemplateArgs();
    3063           0 :       if (TA == nullptr)
    3064             :         return nullptr;
    3065           0 :       SoFar = make<NameWithTemplateArgs>(SoFar, TA);
    3066             :     }
    3067             :   }
    3068             : 
    3069             :   assert(SoFar != nullptr);
    3070             : 
    3071          30 :   Node *Base = parseBaseUnresolvedName();
    3072          30 :   if (Base == nullptr)
    3073             :     return nullptr;
    3074          30 :   return make<QualifiedName>(SoFar, Base);
    3075             : }
    3076             : 
    3077             : // <abi-tags> ::= <abi-tag> [<abi-tags>]
    3078             : // <abi-tag> ::= B <source-name>
    3079       12925 : Node *Db::parseAbiTags(Node *N) {
    3080           6 :   while (consumeIf('B')) {
    3081           6 :     StringView SN = parseBareSourceName();
    3082           6 :     if (SN.empty())
    3083           0 :       return nullptr;
    3084           6 :     N = make<AbiTagAttr>(N, SN);
    3085             :   }
    3086             :   return N;
    3087             : }
    3088             : 
    3089             : // <number> ::= [n] <non-negative decimal integer>
    3090         474 : StringView Db::parseNumber(bool AllowNegative) {
    3091         474 :   const char *Tmp = First;
    3092         474 :   if (AllowNegative)
    3093             :     consumeIf('n');
    3094         948 :   if (numLeft() == 0 || !std::isdigit(*First))
    3095           8 :     return StringView();
    3096        3509 :   while (numLeft() != 0 && std::isdigit(*First))
    3097         859 :     ++First;
    3098         466 :   return StringView(Tmp, First);
    3099             : }
    3100             : 
    3101             : // <positive length number> ::= [0-9]*
    3102       10158 : bool Db::parsePositiveInteger(size_t *Out) {
    3103       10158 :   *Out = 0;
    3104       20316 :   if (look() < '0' || look() > '9')
    3105             :     return true;
    3106       65394 :   while (look() >= '0' && look() <= '9') {
    3107       15026 :     *Out *= 10;
    3108       30052 :     *Out += static_cast<size_t>(consume() - '0');
    3109             :   }
    3110             :   return false;
    3111             : }
    3112             : 
    3113           6 : StringView Db::parseBareSourceName() {
    3114           6 :   size_t Int = 0;
    3115          12 :   if (parsePositiveInteger(&Int) || numLeft() < Int)
    3116           0 :     return StringView();
    3117           6 :   StringView R(First, First + Int);
    3118           6 :   First += Int;
    3119           6 :   return R;
    3120             : }
    3121             : 
    3122             : // <function-type> ::= [<CV-qualifiers>] [<exception-spec>] [Dx] F [Y] <bare-function-type> [<ref-qualifier>] E
    3123             : //
    3124             : // <exception-spec> ::= Do                # non-throwing exception-specification (e.g., noexcept, throw())
    3125             : //                  ::= DO <expression> E # computed (instantiation-dependent) noexcept
    3126             : //                  ::= Dw <type>+ E      # dynamic exception specification with instantiation-dependent types
    3127             : //
    3128             : // <ref-qualifier> ::= R                   # & ref-qualifier
    3129             : // <ref-qualifier> ::= O                   # && ref-qualifier
    3130         279 : Node *Db::parseFunctionType() {
    3131         279 :   Qualifiers CVQuals = parseCVQualifiers();
    3132             : 
    3133             :   Node *ExceptionSpec = nullptr;
    3134         279 :   if (consumeIf("Do")) {
    3135           0 :     ExceptionSpec = make<NameType>("noexcept");
    3136             :   } else if (consumeIf("DO")) {
    3137           0 :     Node *E = parseExpr();
    3138           0 :     if (E == nullptr || !consumeIf('E'))
    3139             :       return nullptr;
    3140           0 :     ExceptionSpec = make<NoexceptSpec>(E);
    3141             :   } else if (consumeIf("Dw")) {
    3142           0 :     size_t SpecsBegin = Names.size();
    3143           0 :     while (!consumeIf('E')) {
    3144           0 :       Node *T = parseType();
    3145           0 :       if (T == nullptr)
    3146           0 :         return nullptr;
    3147           0 :       Names.push_back(T);
    3148             :     }
    3149             :     ExceptionSpec =
    3150           0 :       make<DynamicExceptionSpec>(popTrailingNodeArray(SpecsBegin));
    3151             :   }
    3152             : 
    3153         279 :   consumeIf("Dx"); // transaction safe
    3154             : 
    3155             :   if (!consumeIf('F'))
    3156             :     return nullptr;
    3157             :   consumeIf('Y'); // extern "C"
    3158         279 :   Node *ReturnType = parseType();
    3159         279 :   if (ReturnType == nullptr)
    3160             :     return nullptr;
    3161             : 
    3162             :   FunctionRefQual ReferenceQualifier = FrefQualNone;
    3163         279 :   size_t ParamsBegin = Names.size();
    3164             :   while (true) {
    3165             :     if (consumeIf('E'))
    3166             :       break;
    3167         113 :     if (consumeIf('v'))
    3168         113 :       continue;
    3169             :     if (consumeIf("RE")) {
    3170             :       ReferenceQualifier = FrefQualLValue;
    3171             :       break;
    3172             :     }
    3173             :     if (consumeIf("OE")) {
    3174             :       ReferenceQualifier = FrefQualRValue;
    3175             :       break;
    3176             :     }
    3177         166 :     Node *T = parseType();
    3178         166 :     if (T == nullptr)
    3179           0 :       return nullptr;
    3180         166 :     Names.push_back(T);
    3181             :   }
    3182             : 
    3183         279 :   NodeArray Params = popTrailingNodeArray(ParamsBegin);
    3184             :   return make<FunctionType>(ReturnType, Params, CVQuals,
    3185         279 :                             ReferenceQualifier, ExceptionSpec);
    3186             : }
    3187             : 
    3188             : // extension:
    3189             : // <vector-type>           ::= Dv <positive dimension number> _ <extended element type>
    3190             : //                         ::= Dv [<dimension expression>] _ <element type>
    3191             : // <extended element type> ::= <element type>
    3192             : //                         ::= p # AltiVec vector pixel
    3193           0 : Node *Db::parseVectorType() {
    3194           0 :   if (!consumeIf("Dv"))
    3195             :     return nullptr;
    3196           0 :   if (look() >= '1' && look() <= '9') {
    3197           0 :     StringView DimensionNumber = parseNumber();
    3198             :     if (!consumeIf('_'))
    3199             :       return nullptr;
    3200             :     if (consumeIf('p'))
    3201           0 :       return make<VectorType>(DimensionNumber);
    3202           0 :     Node *ElemType = parseType();
    3203           0 :     if (ElemType == nullptr)
    3204             :       return nullptr;
    3205           0 :     return make<VectorType>(ElemType, DimensionNumber);
    3206             :   }
    3207             : 
    3208             :   if (!consumeIf('_')) {
    3209           0 :     Node *DimExpr = parseExpr();
    3210           0 :     if (!DimExpr)
    3211             :       return nullptr;
    3212             :     if (!consumeIf('_'))
    3213             :       return nullptr;
    3214           0 :     Node *ElemType = parseType();
    3215           0 :     if (!ElemType)
    3216             :       return nullptr;
    3217           0 :     return make<VectorType>(ElemType, DimExpr);
    3218             :   }
    3219           0 :   Node *ElemType = parseType();
    3220           0 :   if (!ElemType)
    3221             :     return nullptr;
    3222           0 :   return make<VectorType>(ElemType, StringView());
    3223             : }
    3224             : 
    3225             : // <decltype>  ::= Dt <expression> E  # decltype of an id-expression or class member access (C++0x)
    3226             : //             ::= DT <expression> E  # decltype of an expression (C++0x)
    3227           6 : Node *Db::parseDecltype() {
    3228             :   if (!consumeIf('D'))
    3229             :     return nullptr;
    3230             :   if (!consumeIf('t') && !consumeIf('T'))
    3231             :     return nullptr;
    3232           6 :   Node *E = parseExpr();
    3233           6 :   if (E == nullptr)
    3234             :     return nullptr;
    3235             :   if (!consumeIf('E'))
    3236             :     return nullptr;
    3237           6 :   return make<EnclosingExpr>("decltype(", E, ")");
    3238             : }
    3239             : 
    3240             : // <array-type> ::= A <positive dimension number> _ <element type>
    3241             : //              ::= A [<dimension expression>] _ <element type>
    3242          19 : Node *Db::parseArrayType() {
    3243             :   if (!consumeIf('A'))
    3244             :     return nullptr;
    3245             : 
    3246          19 :   if (std::isdigit(look())) {
    3247          18 :     StringView Dimension = parseNumber();
    3248             :     if (!consumeIf('_'))
    3249             :       return nullptr;
    3250          18 :     Node *Ty = parseType();
    3251          18 :     if (Ty == nullptr)
    3252             :       return nullptr;
    3253          18 :     return make<ArrayType>(Ty, Dimension);
    3254             :   }
    3255             : 
    3256             :   if (!consumeIf('_')) {
    3257           0 :     Node *DimExpr = parseExpr();
    3258           0 :     if (DimExpr == nullptr)
    3259             :       return nullptr;
    3260             :     if (!consumeIf('_'))
    3261             :       return nullptr;
    3262           0 :     Node *ElementType = parseType();
    3263           0 :     if (ElementType == nullptr)
    3264             :       return nullptr;
    3265           0 :     return make<ArrayType>(ElementType, DimExpr);
    3266             :   }
    3267             : 
    3268           1 :   Node *Ty = parseType();
    3269           1 :   if (Ty == nullptr)
    3270             :     return nullptr;
    3271           1 :   return make<ArrayType>(Ty);
    3272             : }
    3273             : 
    3274             : // <pointer-to-member-type> ::= M <class type> <member type>
    3275           7 : Node *Db::parsePointerToMemberType() {
    3276             :   if (!consumeIf('M'))
    3277             :     return nullptr;
    3278           7 :   Node *ClassType = parseType();
    3279           7 :   if (ClassType == nullptr)
    3280             :     return nullptr;
    3281           7 :   Node *MemberType = parseType();
    3282           7 :   if (MemberType == nullptr)
    3283             :     return nullptr;
    3284           7 :   return make<PointerToMemberType>(ClassType, MemberType);
    3285             : }
    3286             : 
    3287             : // <class-enum-type> ::= <name>     # non-dependent type name, dependent type name, or dependent typename-specifier
    3288             : //                   ::= Ts <name>  # dependent elaborated type specifier using 'struct' or 'class'
    3289             : //                   ::= Tu <name>  # dependent elaborated type specifier using 'union'
    3290             : //                   ::= Te <name>  # dependent elaborated type specifier using 'enum'
    3291        5165 : Node *Db::parseClassEnumType() {
    3292             :   StringView ElabSpef;
    3293        5165 :   if (consumeIf("Ts"))
    3294           0 :     ElabSpef = "struct";
    3295             :   else if (consumeIf("Tu"))
    3296           0 :     ElabSpef = "union";
    3297             :   else if (consumeIf("Te"))
    3298           0 :     ElabSpef = "enum";
    3299             : 
    3300        5165 :   Node *Name = parseName();
    3301        5165 :   if (Name == nullptr)
    3302             :     return nullptr;
    3303             : 
    3304        4089 :   if (!ElabSpef.empty())
    3305           0 :     return make<ElaboratedTypeSpefType>(ElabSpef, Name);
    3306             : 
    3307             :   return Name;
    3308             : }
    3309             : 
    3310             : // <qualified-type>     ::= <qualifiers> <type>
    3311             : // <qualifiers> ::= <extended-qualifier>* <CV-qualifiers>
    3312             : // <extended-qualifier> ::= U <source-name> [<template-args>] # vendor extended type qualifier
    3313         892 : Node *Db::parseQualifiedType() {
    3314             :   if (consumeIf('U')) {
    3315           0 :     StringView Qual = parseBareSourceName();
    3316           0 :     if (Qual.empty())
    3317             :       return nullptr;
    3318             : 
    3319             :     // FIXME parse the optional <template-args> here!
    3320             : 
    3321             :     // extension            ::= U <objc-name> <objc-type>  # objc-type<identifier>
    3322           0 :     if (Qual.startsWith("objcproto")) {
    3323             :       StringView ProtoSourceName = Qual.dropFront(std::strlen("objcproto"));
    3324             :       StringView Proto;
    3325             :       {
    3326           0 :         SwapAndRestore<const char *> SaveFirst(First, ProtoSourceName.begin()),
    3327           0 :                                      SaveLast(Last, ProtoSourceName.end());
    3328           0 :         Proto = parseBareSourceName();
    3329             :       }
    3330           0 :       if (Proto.empty())
    3331             :         return nullptr;
    3332           0 :       Node *Child = parseQualifiedType();
    3333           0 :       if (Child == nullptr)
    3334             :         return nullptr;
    3335           0 :       return make<ObjCProtoName>(Child, Proto);
    3336             :     }
    3337             : 
    3338           0 :     Node *Child = parseQualifiedType();
    3339           0 :     if (Child == nullptr)
    3340             :       return nullptr;
    3341           0 :     return make<VendorExtQualType>(Child, Qual);
    3342             :   }
    3343             : 
    3344         892 :   Qualifiers Quals = parseCVQualifiers();
    3345         892 :   Node *Ty = parseType();
    3346         892 :   if (Ty == nullptr)
    3347             :     return nullptr;
    3348         892 :   if (Quals != QualNone)
    3349         892 :     Ty = make<QualType>(Ty, Quals);
    3350             :   return Ty;
    3351             : }
    3352             : 
    3353             : // <type>      ::= <builtin-type>
    3354             : //             ::= <qualified-type>
    3355             : //             ::= <function-type>
    3356             : //             ::= <class-enum-type>
    3357             : //             ::= <array-type>
    3358             : //             ::= <pointer-to-member-type>
    3359             : //             ::= <template-param>
    3360             : //             ::= <template-template-param> <template-args>
    3361             : //             ::= <decltype>
    3362             : //             ::= P <type>        # pointer
    3363             : //             ::= R <type>        # l-value reference
    3364             : //             ::= O <type>        # r-value reference (C++11)
    3365             : //             ::= C <type>        # complex pair (C99)
    3366             : //             ::= G <type>        # imaginary (C99)
    3367             : //             ::= <substitution>  # See Compression below
    3368             : // extension   ::= U <objc-name> <objc-type>  # objc-type<identifier>
    3369             : // extension   ::= <vector-type> # <vector-type> starts with Dv
    3370             : //
    3371             : // <objc-name> ::= <k0 number> objcproto <k1 number> <identifier>  # k0 = 9 + <number of digits in k1> + k1
    3372             : // <objc-type> ::= <source-name>  # PU<11+>objcproto 11objc_object<source-name> 11objc_object -> id<source-name>
    3373       18029 : Node *Db::parseType() {
    3374       18029 :   Node *Result = nullptr;
    3375             : 
    3376       36058 :   switch (look()) {
    3377             :   //             ::= <qualified-type>
    3378             :   case 'r':
    3379             :   case 'V':
    3380             :   case 'K': {
    3381             :     unsigned AfterQuals = 0;
    3382         892 :     if (look(AfterQuals) == 'r') ++AfterQuals;
    3383         892 :     if (look(AfterQuals) == 'V') ++AfterQuals;
    3384         892 :     if (look(AfterQuals) == 'K') ++AfterQuals;
    3385             : 
    3386        1784 :     if (look(AfterQuals) == 'F' ||
    3387           0 :         (look(AfterQuals) == 'D' &&
    3388           0 :          (look(AfterQuals + 1) == 'o' || look(AfterQuals + 1) == 'O' ||
    3389           0 :           look(AfterQuals + 1) == 'w' || look(AfterQuals + 1) == 'x'))) {
    3390           0 :       Result = parseFunctionType();
    3391           0 :       break;
    3392             :     }
    3393             :     LLVM_FALLTHROUGH;
    3394             :   }
    3395             :   case 'U': {
    3396         892 :     Result = parseQualifiedType();
    3397         892 :     break;
    3398             :   }
    3399             :   // <builtin-type> ::= v    # void
    3400         610 :   case 'v':
    3401         610 :     ++First;
    3402         610 :     return make<NameType>("void");
    3403             :   //                ::= w    # wchar_t
    3404          26 :   case 'w':
    3405          26 :     ++First;
    3406          26 :     return make<NameType>("wchar_t");
    3407             :   //                ::= b    # bool
    3408          73 :   case 'b':
    3409          73 :     ++First;
    3410          73 :     return make<NameType>("bool");
    3411             :   //                ::= c    # char
    3412        3121 :   case 'c':
    3413        3121 :     ++First;
    3414        3121 :     return make<NameType>("char");
    3415             :   //                ::= a    # signed char
    3416           0 :   case 'a':
    3417           0 :     ++First;
    3418           0 :     return make<NameType>("signed char");
    3419             :   //                ::= h    # unsigned char
    3420           0 :   case 'h':
    3421           0 :     ++First;
    3422           0 :     return make<NameType>("unsigned char");
    3423             :   //                ::= s    # short
    3424           0 :   case 's':
    3425           0 :     ++First;
    3426           0 :     return make<NameType>("short");
    3427             :   //                ::= t    # unsigned short
    3428           0 :   case 't':
    3429           0 :     ++First;
    3430           0 :     return make<NameType>("unsigned short");
    3431             :   //                ::= i    # int
    3432         705 :   case 'i':
    3433         705 :     ++First;
    3434         705 :     return make<NameType>("int");
    3435             :   //                ::= j    # unsigned int
    3436         132 :   case 'j':
    3437         132 :     ++First;
    3438         132 :     return make<NameType>("unsigned int");
    3439             :   //                ::= l    # long
    3440         211 :   case 'l':
    3441         211 :     ++First;
    3442         211 :     return make<NameType>("long");
    3443             :   //                ::= m    # unsigned long
    3444         282 :   case 'm':
    3445         282 :     ++First;
    3446         282 :     return make<NameType>("unsigned long");
    3447             :   //                ::= x    # long long, __int64
    3448           0 :   case 'x':
    3449           0 :     ++First;
    3450           0 :     return make<NameType>("long long");
    3451             :   //                ::= y    # unsigned long long, __int64
    3452           0 :   case 'y':
    3453           0 :     ++First;
    3454           0 :     return make<NameType>("unsigned long long");
    3455             :   //                ::= n    # __int128
    3456           0 :   case 'n':
    3457           0 :     ++First;
    3458           0 :     return make<NameType>("__int128");
    3459             :   //                ::= o    # unsigned __int128
    3460           0 :   case 'o':
    3461           0 :     ++First;
    3462           0 :     return make<NameType>("unsigned __int128");
    3463             :   //                ::= f    # float
    3464          11 :   case 'f':
    3465          11 :     ++First;
    3466          11 :     return make<NameType>("float");
    3467             :   //                ::= d    # double
    3468           8 :   case 'd':
    3469           8 :     ++First;
    3470           8 :     return make<NameType>("double");
    3471             :   //                ::= e    # long double, __float80
    3472           0 :   case 'e':
    3473           0 :     ++First;
    3474           0 :     return make<NameType>("long double");
    3475             :   //                ::= g    # __float128
    3476           0 :   case 'g':
    3477           0 :     ++First;
    3478           0 :     return make<NameType>("__float128");
    3479             :   //                ::= z    # ellipsis
    3480           0 :   case 'z':
    3481           0 :     ++First;
    3482           0 :     return make<NameType>("...");
    3483             : 
    3484             :   // <builtin-type> ::= u <source-name>    # vendor extended type
    3485           0 :   case 'u': {
    3486           0 :     ++First;
    3487           0 :     StringView Res = parseBareSourceName();
    3488           0 :     if (Res.empty())
    3489             :       return nullptr;
    3490           0 :     return make<NameType>(Res);
    3491             :   }
    3492         189 :   case 'D':
    3493         189 :     switch (look(1)) {
    3494             :     //                ::= Dd   # IEEE 754r decimal floating point (64 bits)
    3495           0 :     case 'd':
    3496           0 :       First += 2;
    3497           0 :       return make<NameType>("decimal64");
    3498             :     //                ::= De   # IEEE 754r decimal floating point (128 bits)
    3499           0 :     case 'e':
    3500           0 :       First += 2;
    3501           0 :       return make<NameType>("decimal128");
    3502             :     //                ::= Df   # IEEE 754r decimal floating point (32 bits)
    3503           0 :     case 'f':
    3504           0 :       First += 2;
    3505           0 :       return make<NameType>("decimal32");
    3506             :     //                ::= Dh   # IEEE 754r half-precision floating point (16 bits)
    3507           0 :     case 'h':
    3508           0 :       First += 2;
    3509           0 :       return make<NameType>("decimal16");
    3510             :     //                ::= Di   # char32_t
    3511           0 :     case 'i':
    3512           0 :       First += 2;
    3513           0 :       return make<NameType>("char32_t");
    3514             :     //                ::= Ds   # char16_t
    3515           0 :     case 's':
    3516           0 :       First += 2;
    3517           0 :       return make<NameType>("char16_t");
    3518             :     //                ::= Da   # auto (in dependent new-expressions)
    3519           0 :     case 'a':
    3520           0 :       First += 2;
    3521           0 :       return make<NameType>("auto");
    3522             :     //                ::= Dc   # decltype(auto)
    3523           0 :     case 'c':
    3524           0 :       First += 2;
    3525           0 :       return make<NameType>("decltype(auto)");
    3526             :     //                ::= Dn   # std::nullptr_t (i.e., decltype(nullptr))
    3527           1 :     case 'n':
    3528           1 :       First += 2;
    3529           1 :       return make<NameType>("std::nullptr_t");
    3530             : 
    3531             :     //             ::= <decltype>
    3532           6 :     case 't':
    3533             :     case 'T': {
    3534           6 :       Result = parseDecltype();
    3535           6 :       break;
    3536             :     }
    3537             :     // extension   ::= <vector-type> # <vector-type> starts with Dv
    3538           0 :     case 'v': {
    3539           0 :       Result = parseVectorType();
    3540           0 :       break;
    3541             :     }
    3542             :     //           ::= Dp <type>       # pack expansion (C++0x)
    3543         182 :     case 'p': {
    3544         182 :       First += 2;
    3545         182 :       Node *Child = parseType();
    3546         182 :       if (!Child)
    3547             :         return nullptr;
    3548         182 :       Result = make<ParameterPackExpansion>(Child);
    3549             :       break;
    3550             :     }
    3551             :     // Exception specifier on a function type.
    3552           0 :     case 'o':
    3553             :     case 'O':
    3554             :     case 'w':
    3555             :     // Transaction safe function type.
    3556             :     case 'x':
    3557           0 :       Result = parseFunctionType();
    3558           0 :       break;
    3559             :     }
    3560             :     break;
    3561             :   //             ::= <function-type>
    3562         279 :   case 'F': {
    3563         279 :     Result = parseFunctionType();
    3564         279 :     break;
    3565             :   }
    3566             :   //             ::= <array-type>
    3567          19 :   case 'A': {
    3568          19 :     Result = parseArrayType();
    3569          19 :     break;
    3570             :   }
    3571             :   //             ::= <pointer-to-member-type>
    3572           7 :   case 'M': {
    3573           7 :     Result = parsePointerToMemberType();
    3574           7 :     break;
    3575             :   }
    3576             :   //             ::= <template-param>
    3577         671 :   case 'T': {
    3578             :     // This could be an elaborate type specifier on a <class-enum-type>.
    3579        2013 :     if (look(1) == 's' || look(1) == 'u' || look(1) == 'e') {
    3580           0 :       Result = parseClassEnumType();
    3581           0 :       break;
    3582             :     }
    3583             : 
    3584         671 :     Result = parseTemplateParam();
    3585         671 :     if (Result == nullptr)
    3586             :       return nullptr;
    3587             : 
    3588             :     // Result could be either of:
    3589             :     //   <type>        ::= <template-param>
    3590             :     //   <type>        ::= <template-template-param> <template-args>
    3591             :     //
    3592             :     //   <template-template-param> ::= <template-param>
    3593             :     //                             ::= <substitution>
    3594             :     //
    3595             :     // If this is followed by some <template-args>, and we're permitted to
    3596             :     // parse them, take the second production.
    3597             : 
    3598        1217 :     if (TryToParseTemplateArgs && look() == 'I') {
    3599           0 :       Node *TA = parseTemplateArgs();
    3600           0 :       if (TA == nullptr)
    3601             :         return nullptr;
    3602           0 :       Result = make<NameWithTemplateArgs>(Result, TA);
    3603             :     }
    3604             :     break;
    3605             :   }
    3606             :   //             ::= P <type>        # pointer
    3607        1191 :   case 'P': {
    3608        1191 :     ++First;
    3609        1191 :     Node *Ptr = parseType();
    3610        1191 :     if (Ptr == nullptr)
    3611             :       return nullptr;
    3612        1191 :     Result = make<PointerType>(Ptr);
    3613             :     break;
    3614             :   }
    3615             :   //             ::= R <type>        # l-value reference
    3616        1016 :   case 'R': {
    3617        1016 :     ++First;
    3618        1016 :     Node *Ref = parseType();
    3619        1016 :     if (Ref == nullptr)
    3620             :       return nullptr;
    3621        1016 :     Result = make<LValueReferenceType>(Ref);
    3622             :     break;
    3623             :   }
    3624             :   //             ::= O <type>        # r-value reference (C++11)
    3625         339 :   case 'O': {
    3626         339 :     ++First;
    3627         339 :     Node *Ref = parseType();
    3628         339 :     if (Ref == nullptr)
    3629             :       return nullptr;
    3630         339 :     Result = make<RValueReferenceType>(Ref);
    3631             :     break;
    3632             :   }
    3633             :   //             ::= C <type>        # complex pair (C99)
    3634           0 :   case 'C': {
    3635           0 :     ++First;
    3636           0 :     Node *P = parseType();
    3637           0 :     if (P == nullptr)
    3638             :       return nullptr;
    3639           0 :     Result = make<PostfixQualifiedType>(P, " complex");
    3640             :     break;
    3641             :   }
    3642             :   //             ::= G <type>        # imaginary (C99)
    3643           0 :   case 'G': {
    3644           0 :     ++First;
    3645           0 :     Node *P = parseType();
    3646           0 :     if (P == nullptr)
    3647             :       return P;
    3648           0 :     Result = make<PostfixQualifiedType>(P, " imaginary");
    3649             :     break;
    3650             :   }
    3651             :   //             ::= <substitution>  # See Compression below
    3652        5469 :   case 'S': {
    3653        5469 :     if (look(1) && look(1) != 't') {
    3654        3082 :       Node *Sub = parseSubstitution();
    3655        3082 :       if (Sub == nullptr)
    3656             :         return nullptr;
    3657             : 
    3658             :       // Sub could be either of:
    3659             :       //   <type>        ::= <substitution>
    3660             :       //   <type>        ::= <template-template-param> <template-args>
    3661             :       //
    3662             :       //   <template-template-param> ::= <template-param>
    3663             :       //                             ::= <substitution>
    3664             :       //
    3665             :       // If this is followed by some <template-args>, and we're permitted to
    3666             :       // parse them, take the second production.
    3667             : 
    3668        5883 :       if (TryToParseTemplateArgs && look() == 'I') {
    3669        1206 :         Node *TA = parseTemplateArgs();
    3670        1206 :         if (TA == nullptr)
    3671             :           return nullptr;
    3672        1206 :         Result = make<NameWithTemplateArgs>(Sub, TA);
    3673             :         break;
    3674             :       }
    3675             : 
    3676             :       // If all we parsed was a substitution, don't re-insert into the
    3677             :       // substitution table.
    3678             :       return Sub;
    3679             :     }
    3680             :     LLVM_FALLTHROUGH;
    3681             :   }
    3682             :   //        ::= <class-enum-type>
    3683             :   default: {
    3684        5165 :     Result = parseClassEnumType();
    3685        5165 :     break;
    3686             :   }
    3687             :   }
    3688             : 
    3689             :   // If we parsed a type, insert it into the substitution table. Note that all
    3690             :   // <builtin-type>s and <substitution>s have already bailed out, because they
    3691             :   // don't get substitutions.
    3692       10973 :   if (Result != nullptr)
    3693        9897 :     Subs.push_back(Result);
    3694       10973 :   return Result;
    3695             : }
    3696             : 
    3697           2 : Node *Db::parsePrefixExpr(StringView Kind) {
    3698           2 :   Node *E = parseExpr();
    3699           2 :   if (E == nullptr)
    3700             :     return nullptr;
    3701           2 :   return make<PrefixExpr>(Kind, E);
    3702             : }
    3703             : 
    3704           2 : Node *Db::parseBinaryExpr(StringView Kind) {
    3705           2 :   Node *LHS = parseExpr();
    3706           2 :   if (LHS == nullptr)
    3707             :     return nullptr;
    3708           2 :   Node *RHS = parseExpr();
    3709           2 :   if (RHS == nullptr)
    3710             :     return nullptr;
    3711           2 :   return make<BinaryExpr>(LHS, Kind, RHS);
    3712             : }
    3713             : 
    3714         403 : Node *Db::parseIntegerLiteral(StringView Lit) {
    3715         403 :   StringView Tmp = parseNumber(true);
    3716         403 :   if (!Tmp.empty() && consumeIf('E'))
    3717         403 :     return make<IntegerExpr>(Lit, Tmp);
    3718             :   return nullptr;
    3719             : }
    3720             : 
    3721             : // <CV-Qualifiers> ::= [r] [V] [K]
    3722        4966 : Qualifiers Db::parseCVQualifiers() {
    3723             :   Qualifiers CVR = QualNone;
    3724             :   if (consumeIf('r'))
    3725             :     addQualifiers(CVR, QualRestrict);
    3726             :   if (consumeIf('V'))
    3727             :     addQualifiers(CVR, QualVolatile);
    3728             :   if (consumeIf('K'))
    3729             :     addQualifiers(CVR, QualConst);
    3730        4966 :   return CVR;
    3731             : }
    3732             : 
    3733             : // <function-param> ::= fp <top-level CV-Qualifiers> _                                     # L == 0, first parameter
    3734             : //                  ::= fp <top-level CV-Qualifiers> <parameter-2 non-negative number> _   # L == 0, second and later parameters
    3735             : //                  ::= fL <L-1 non-negative number> p <top-level CV-Qualifiers> _         # L > 0, first parameter
    3736             : //                  ::= fL <L-1 non-negative number> p <top-level CV-Qualifiers> <parameter-2 non-negative number> _   # L > 0, second and later parameters
    3737           3 : Node *Db::parseFunctionParam() {
    3738           3 :   if (consumeIf("fp")) {
    3739           1 :     parseCVQualifiers();
    3740           1 :     StringView Num = parseNumber();
    3741             :     if (!consumeIf('_'))
    3742             :       return nullptr;
    3743           1 :     return make<FunctionParam>(Num);
    3744             :   }
    3745             :   if (consumeIf("fL")) {
    3746           4 :     if (parseNumber().empty())
    3747             :       return nullptr;
    3748             :     if (!consumeIf('p'))
    3749             :       return nullptr;
    3750           2 :     parseCVQualifiers();
    3751           2 :     StringView Num = parseNumber();
    3752             :     if (!consumeIf('_'))
    3753             :       return nullptr;
    3754           2 :     return make<FunctionParam>(Num);
    3755             :   }
    3756             :   return nullptr;
    3757             : }
    3758             : 
    3759             : // [gs] nw <expression>* _ <type> E                     # new (expr-list) type
    3760             : // [gs] nw <expression>* _ <type> <initializer>         # new (expr-list) type (init)
    3761             : // [gs] na <expression>* _ <type> E                     # new[] (expr-list) type
    3762             : // [gs] na <expression>* _ <type> <initializer>         # new[] (expr-list) type (init)
    3763             : // <initializer> ::= pi <expression>* E                 # parenthesized initialization
    3764           0 : Node *Db::parseNewExpr() {
    3765           0 :   bool Global = consumeIf("gs");
    3766           0 :   bool IsArray = look(1) == 'a';
    3767             :   if (!consumeIf("nw") && !consumeIf("na"))
    3768             :     return nullptr;
    3769           0 :   size_t Exprs = Names.size();
    3770           0 :   while (!consumeIf('_')) {
    3771           0 :     Node *Ex = parseExpr();
    3772           0 :     if (Ex == nullptr)
    3773           0 :       return nullptr;
    3774           0 :     Names.push_back(Ex);
    3775             :   }
    3776           0 :   NodeArray ExprList = popTrailingNodeArray(Exprs);
    3777           0 :   Node *Ty = parseType();
    3778           0 :   if (Ty == nullptr)
    3779             :     return Ty;
    3780           0 :   if (consumeIf("pi")) {
    3781           0 :     size_t InitsBegin = Names.size();
    3782           0 :     while (!consumeIf('E')) {
    3783           0 :       Node *Init = parseExpr();
    3784           0 :       if (Init == nullptr)
    3785           0 :         return Init;
    3786           0 :       Names.push_back(Init);
    3787             :     }
    3788           0 :     NodeArray Inits = popTrailingNodeArray(InitsBegin);
    3789           0 :     return make<NewExpr>(ExprList, Ty, Inits, Global, IsArray);
    3790             :   } else if (!consumeIf('E'))
    3791             :     return nullptr;
    3792           0 :   return make<NewExpr>(ExprList, Ty, NodeArray(), Global, IsArray);
    3793             : }
    3794             : 
    3795             : // cv <type> <expression>                               # conversion with one argument
    3796             : // cv <type> _ <expression>* E                          # conversion with a different number of arguments
    3797           0 : Node *Db::parseConversionExpr() {
    3798           0 :   if (!consumeIf("cv"))
    3799             :     return nullptr;
    3800             :   Node *Ty;
    3801             :   {
    3802           0 :     SwapAndRestore<bool> SaveTemp(TryToParseTemplateArgs, false);
    3803           0 :     Ty = parseType();
    3804             :   }
    3805             : 
    3806           0 :   if (Ty == nullptr)
    3807             :     return nullptr;
    3808             : 
    3809             :   if (consumeIf('_')) {
    3810           0 :     size_t ExprsBegin = Names.size();
    3811           0 :     while (!consumeIf('E')) {
    3812           0 :       Node *E = parseExpr();
    3813           0 :       if (E == nullptr)
    3814           0 :         return E;
    3815           0 :       Names.push_back(E);
    3816             :     }
    3817           0 :     NodeArray Exprs = popTrailingNodeArray(ExprsBegin);
    3818           0 :     return make<ConversionExpr>(Ty, Exprs);
    3819             :   }
    3820             : 
    3821           0 :   Node *E[1] = {parseExpr()};
    3822           0 :   if (E[0] == nullptr)
    3823             :     return nullptr;
    3824           0 :   return make<ConversionExpr>(Ty, makeNodeArray(E, E + 1));
    3825             : }
    3826             : 
    3827             : // <expr-primary> ::= L <type> <value number> E                          # integer literal
    3828             : //                ::= L <type> <value float> E                           # floating literal
    3829             : //                ::= L <string type> E                                  # string literal
    3830             : //                ::= L <nullptr type> E                                 # nullptr literal (i.e., "LDnE")
    3831             : // FIXME:         ::= L <type> <real-part float> _ <imag-part float> E   # complex floating point literal (C 2000)
    3832             : //                ::= L <mangled-name> E                                 # external name
    3833         538 : Node *Db::parseExprPrimary() {
    3834             :   if (!consumeIf('L'))
    3835             :     return nullptr;
    3836         538 :   switch (look()) {
    3837           0 :   case 'w':
    3838           0 :     ++First;
    3839           0 :     return parseIntegerLiteral("wchar_t");
    3840             :   case 'b':
    3841             :     if (consumeIf("b0E"))
    3842          41 :       return make<BoolExpr>(0);
    3843             :     if (consumeIf("b1E"))
    3844          54 :       return make<BoolExpr>(1);
    3845             :     return nullptr;
    3846           0 :   case 'c':
    3847           0 :     ++First;
    3848           0 :     return parseIntegerLiteral("char");
    3849           0 :   case 'a':
    3850           0 :     ++First;
    3851           0 :     return parseIntegerLiteral("signed char");
    3852           0 :   case 'h':
    3853           0 :     ++First;
    3854           0 :     return parseIntegerLiteral("unsigned char");
    3855           0 :   case 's':
    3856           0 :     ++First;
    3857           0 :     return parseIntegerLiteral("short");
    3858           0 :   case 't':
    3859           0 :     ++First;
    3860           0 :     return parseIntegerLiteral("unsigned short");
    3861           5 :   case 'i':
    3862           5 :     ++First;
    3863           5 :     return parseIntegerLiteral("");
    3864           0 :   case 'j':
    3865           0 :     ++First;
    3866           0 :     return parseIntegerLiteral("u");
    3867         188 :   case 'l':
    3868         188 :     ++First;
    3869         188 :     return parseIntegerLiteral("l");
    3870         210 :   case 'm':
    3871         210 :     ++First;
    3872         210 :     return parseIntegerLiteral("ul");
    3873           0 :   case 'x':
    3874           0 :     ++First;
    3875           0 :     return parseIntegerLiteral("ll");
    3876           0 :   case 'y':
    3877           0 :     ++First;
    3878           0 :     return parseIntegerLiteral("ull");
    3879           0 :   case 'n':
    3880           0 :     ++First;
    3881           0 :     return parseIntegerLiteral("__int128");
    3882           0 :   case 'o':
    3883           0 :     ++First;
    3884           0 :     return parseIntegerLiteral("unsigned __int128");
    3885           0 :   case 'f':
    3886           0 :     ++First;
    3887           0 :     return parseFloatingLiteral<float>();
    3888           0 :   case 'd':
    3889           0 :     ++First;
    3890           0 :     return parseFloatingLiteral<double>();
    3891           0 :   case 'e':
    3892           0 :     ++First;
    3893           0 :     return parseFloatingLiteral<long double>();
    3894             :   case '_':
    3895             :     if (consumeIf("_Z")) {
    3896           0 :       Node *R = parseEncoding();
    3897           0 :       if (R != nullptr && consumeIf('E'))
    3898             :         return R;
    3899             :     }
    3900             :     return nullptr;
    3901             :   case 'T':
    3902             :     // Invalid mangled name per
    3903             :     //   http://sourcerytools.com/pipermail/cxx-abi-dev/2011-August/002422.html
    3904             :     return nullptr;
    3905          40 :   default: {
    3906             :     // might be named type
    3907          40 :     Node *T = parseType();
    3908          40 :     if (T == nullptr)
    3909             :       return nullptr;
    3910          40 :     StringView N = parseNumber();
    3911          40 :     if (!N.empty()) {
    3912             :       if (!consumeIf('E'))
    3913             :         return nullptr;
    3914          40 :       return make<IntegerCastExpr>(T, N);
    3915             :     }
    3916             :     if (consumeIf('E'))
    3917             :       return T;
    3918             :     return nullptr;
    3919             :   }
    3920             :   }
    3921             : }
    3922             : 
    3923             : // <braced-expression> ::= <expression>
    3924             : //                     ::= di <field source-name> <braced-expression>    # .name = expr
    3925             : //                     ::= dx <index expression> <braced-expression>     # [expr] = expr
    3926             : //                     ::= dX <range begin expression> <range end expression> <braced-expression>
    3927           0 : Node *Db::parseBracedExpr() {
    3928           0 :   if (look() == 'd') {
    3929           0 :     switch (look(1)) {
    3930           0 :     case 'i': {
    3931           0 :       First += 2;
    3932           0 :       Node *Field = parseSourceName(/*NameState=*/nullptr);
    3933           0 :       if (Field == nullptr)
    3934             :         return nullptr;
    3935           0 :       Node *Init = parseBracedExpr();
    3936           0 :       if (Init == nullptr)
    3937             :         return nullptr;
    3938           0 :       return make<BracedExpr>(Field, Init, /*isArray=*/false);
    3939             :     }
    3940           0 :     case 'x': {
    3941           0 :       First += 2;
    3942           0 :       Node *Index = parseExpr();
    3943           0 :       if (Index == nullptr)
    3944             :         return nullptr;
    3945           0 :       Node *Init = parseBracedExpr();
    3946           0 :       if (Init == nullptr)
    3947             :         return nullptr;
    3948           0 :       return make<BracedExpr>(Index, Init, /*isArray=*/true);
    3949             :     }
    3950           0 :     case 'X': {
    3951           0 :       First += 2;
    3952           0 :       Node *RangeBegin = parseExpr();
    3953           0 :       if (RangeBegin == nullptr)
    3954             :         return nullptr;
    3955           0 :       Node *RangeEnd = parseExpr();
    3956           0 :       if (RangeEnd == nullptr)
    3957             :         return nullptr;
    3958           0 :       Node *Init = parseBracedExpr();
    3959           0 :       if (Init == nullptr)
    3960             :         return nullptr;
    3961           0 :       return make<BracedRangeExpr>(RangeBegin, RangeEnd, Init);
    3962             :     }
    3963             :     }
    3964             :   }
    3965           0 :   return parseExpr();
    3966             : }
    3967             : 
    3968             : // (not yet in the spec)
    3969             : // <fold-expr> ::= fL <binary-operator-name> <expression> <expression>
    3970             : //             ::= fR <binary-operator-name> <expression> <expression>
    3971             : //             ::= fl <binary-operator-name> <expression>
    3972             : //             ::= fr <binary-operator-name> <expression>
    3973           0 : Node *Db::parseFoldExpr() {
    3974             :   if (!consumeIf('f'))
    3975             :     return nullptr;
    3976             : 
    3977             :   char FoldKind = look();
    3978             :   bool IsLeftFold, HasInitializer;
    3979           0 :   HasInitializer = FoldKind == 'L' || FoldKind == 'R';
    3980           0 :   if (FoldKind == 'l' || FoldKind == 'L')
    3981             :     IsLeftFold = true;
    3982           0 :   else if (FoldKind == 'r' || FoldKind == 'R')
    3983             :     IsLeftFold = false;
    3984             :   else
    3985             :     return nullptr;
    3986           0 :   ++First;
    3987             : 
    3988             :   // FIXME: This map is duplicated in parseOperatorName and parseExpr.
    3989             :   StringView OperatorName;
    3990           0 :   if      (consumeIf("aa")) OperatorName = "&&";
    3991           0 :   else if (consumeIf("an")) OperatorName = "&";
    3992           0 :   else if (consumeIf("aN")) OperatorName = "&=";
    3993           0 :   else if (consumeIf("aS")) OperatorName = "=";
    3994           0 :   else if (consumeIf("cm")) OperatorName = ",";
    3995           0 :   else if (consumeIf("ds")) OperatorName = ".*";
    3996           0 :   else if (consumeIf("dv")) OperatorName = "/";
    3997           0 :   else if (consumeIf("dV")) OperatorName = "/=";
    3998           0 :   else if (consumeIf("eo")) OperatorName = "^";
    3999           0 :   else if (consumeIf("eO")) OperatorName = "^=";
    4000           0 :   else if (consumeIf("eq")) OperatorName = "==";
    4001           0 :   else if (consumeIf("ge")) OperatorName = ">=";
    4002           0 :   else if (consumeIf("gt")) OperatorName = ">";
    4003           0 :   else if (consumeIf("le")) OperatorName = "<=";
    4004           0 :   else if (consumeIf("ls")) OperatorName = "<<";
    4005           0 :   else if (consumeIf("lS")) OperatorName = "<<=";
    4006           0 :   else if (consumeIf("lt")) OperatorName = "<";
    4007           0 :   else if (consumeIf("mi")) OperatorName = "-";
    4008           0 :   else if (consumeIf("mI")) OperatorName = "-=";
    4009           0 :   else if (consumeIf("ml")) OperatorName = "*";
    4010           0 :   else if (consumeIf("mL")) OperatorName = "*=";
    4011           0 :   else if (consumeIf("ne")) OperatorName = "!=";
    4012           0 :   else if (consumeIf("oo")) OperatorName = "||";
    4013           0 :   else if (consumeIf("or")) OperatorName = "|";
    4014           0 :   else if (consumeIf("oR")) OperatorName = "|=";
    4015           0 :   else if (consumeIf("pl")) OperatorName = "+";
    4016           0 :   else if (consumeIf("pL")) OperatorName = "+=";
    4017           0 :   else if (consumeIf("rm")) OperatorName = "%";
    4018           0 :   else if (consumeIf("rM")) OperatorName = "%=";
    4019           0 :   else if (consumeIf("rs")) OperatorName = ">>";
    4020           0 :   else if (consumeIf("rS")) OperatorName = ">>=";
    4021             :   else return nullptr;
    4022             : 
    4023           0 :   Node *Pack = parseExpr(), *Init = nullptr;
    4024           0 :   if (Pack == nullptr)
    4025             :     return nullptr;
    4026           0 :   if (HasInitializer) {
    4027           0 :     Init = parseExpr();
    4028           0 :     if (Init == nullptr)
    4029             :       return nullptr;
    4030             :   }
    4031             : 
    4032           0 :   if (IsLeftFold && Init)
    4033             :     std::swap(Pack, Init);
    4034             : 
    4035           0 :   return make<FoldExpr>(IsLeftFold, OperatorName, Pack, Init);
    4036             : }
    4037             : 
    4038             : // <expression> ::= <unary operator-name> <expression>
    4039             : //              ::= <binary operator-name> <expression> <expression>
    4040             : //              ::= <ternary operator-name> <expression> <expression> <expression>
    4041             : //              ::= cl <expression>+ E                                   # call
    4042             : //              ::= cv <type> <expression>                               # conversion with one argument
    4043             : //              ::= cv <type> _ <expression>* E                          # conversion with a different number of arguments
    4044             : //              ::= [gs] nw <expression>* _ <type> E                     # new (expr-list) type
    4045             : //              ::= [gs] nw <expression>* _ <type> <initializer>         # new (expr-list) type (init)
    4046             : //              ::= [gs] na <expression>* _ <type> E                     # new[] (expr-list) type
    4047             : //              ::= [gs] na <expression>* _ <type> <initializer>         # new[] (expr-list) type (init)
    4048             : //              ::= [gs] dl <expression>                                 # delete expression
    4049             : //              ::= [gs] da <expression>                                 # delete[] expression
    4050             : //              ::= pp_ <expression>                                     # prefix ++
    4051             : //              ::= mm_ <expression>                                     # prefix --
    4052             : //              ::= ti <type>                                            # typeid (type)
    4053             : //              ::= te <expression>                                      # typeid (expression)
    4054             : //              ::= dc <type> <expression>                               # dynamic_cast<type> (expression)
    4055             : //              ::= sc <type> <expression>                               # static_cast<type> (expression)
    4056             : //              ::= cc <type> <expression>                               # const_cast<type> (expression)
    4057             : //              ::= rc <type> <expression>                               # reinterpret_cast<type> (expression)
    4058             : //              ::= st <type>                                            # sizeof (a type)
    4059             : //              ::= sz <expression>                                      # sizeof (an expression)
    4060             : //              ::= at <type>                                            # alignof (a type)
    4061             : //              ::= az <expression>                                      # alignof (an expression)
    4062             : //              ::= nx <expression>                                      # noexcept (expression)
    4063             : //              ::= <template-param>
    4064             : //              ::= <function-param>
    4065             : //              ::= dt <expression> <unresolved-name>                    # expr.name
    4066             : //              ::= pt <expression> <unresolved-name>                    # expr->name
    4067             : //              ::= ds <expression> <expression>                         # expr.*expr
    4068             : //              ::= sZ <template-param>                                  # size of a parameter pack
    4069             : //              ::= sZ <function-param>                                  # size of a function parameter pack
    4070             : //              ::= sP <template-arg>* E                                 # sizeof...(T), size of a captured template parameter pack from an alias template
    4071             : //              ::= sp <expression>                                      # pack expansion
    4072             : //              ::= tw <expression>                                      # throw expression
    4073             : //              ::= tr                                                   # throw with no operand (rethrow)
    4074             : //              ::= <unresolved-name>                                    # f(p), N::f(p), ::f(p),
    4075             : //                                                                       # freestanding dependent name (e.g., T::x),
    4076             : //                                                                       # objectless nonstatic member reference
    4077             : //              ::= fL <binary-operator-name> <expression> <expression>
    4078             : //              ::= fR <binary-operator-name> <expression> <expression>
    4079             : //              ::= fl <binary-operator-name> <expression>
    4080             : //              ::= fr <binary-operator-name> <expression>
    4081             : //              ::= <expr-primary>
    4082         172 : Node *Db::parseExpr() {
    4083         172 :   bool Global = consumeIf("gs");
    4084         344 :   if (numLeft() < 2)
    4085             :     return nullptr;
    4086             : 
    4087         172 :   switch (*First) {
    4088           2 :   case 'L':
    4089           2 :     return parseExprPrimary();
    4090          95 :   case 'T':
    4091          95 :     return parseTemplateParam();
    4092             :   case 'f': {
    4093             :     // Disambiguate a fold expression from a <function-param>.
    4094           7 :     if (look(1) == 'p' || (look(1) == 'L' && std::isdigit(look(2))))
    4095           3 :       return parseFunctionParam();
    4096           0 :     return parseFoldExpr();
    4097             :   }
    4098           0 :   case 'a':
    4099           0 :     switch (First[1]) {
    4100           0 :     case 'a':
    4101           0 :       First += 2;
    4102           0 :       return parseBinaryExpr("&&");
    4103           0 :     case 'd':
    4104           0 :       First += 2;
    4105           0 :       return parsePrefixExpr("&");
    4106           0 :     case 'n':
    4107           0 :       First += 2;
    4108           0 :       return parseBinaryExpr("&");
    4109           0 :     case 'N':
    4110           0 :       First += 2;
    4111           0 :       return parseBinaryExpr("&=");
    4112           0 :     case 'S':
    4113           0 :       First += 2;
    4114           0 :       return parseBinaryExpr("=");
    4115           0 :     case 't': {
    4116           0 :       First += 2;
    4117           0 :       Node *Ty = parseType();
    4118           0 :       if (Ty == nullptr)
    4119             :         return nullptr;
    4120           0 :       return make<EnclosingExpr>("alignof (", Ty, ")");
    4121             :     }
    4122           0 :     case 'z': {
    4123           0 :       First += 2;
    4124           0 :       Node *Ty = parseExpr();
    4125           0 :       if (Ty == nullptr)
    4126             :         return nullptr;
    4127           0 :       return make<EnclosingExpr>("alignof (", Ty, ")");
    4128             :     }
    4129             :     }
    4130             :     return nullptr;
    4131          12 :   case 'c':
    4132          12 :     switch (First[1]) {
    4133             :     // cc <type> <expression>                               # const_cast<type>(expression)
    4134           0 :     case 'c': {
    4135           0 :       First += 2;
    4136           0 :       Node *Ty = parseType();
    4137           0 :       if (Ty == nullptr)
    4138             :         return Ty;
    4139           0 :       Node *Ex = parseExpr();
    4140           0 :       if (Ex == nullptr)
    4141             :         return Ex;
    4142           0 :       return make<CastExpr>("const_cast", Ty, Ex);
    4143             :     }
    4144             :     // cl <expression>+ E                                   # call
    4145          12 :     case 'l': {
    4146          12 :       First += 2;
    4147          12 :       Node *Callee = parseExpr();
    4148          12 :       if (Callee == nullptr)
    4149             :         return Callee;
    4150          12 :       size_t ExprsBegin = Names.size();
    4151           6 :       while (!consumeIf('E')) {
    4152           6 :         Node *E = parseExpr();
    4153           6 :         if (E == nullptr)
    4154           0 :           return E;
    4155           6 :         Names.push_back(E);
    4156             :       }
    4157          12 :       return make<CallExpr>(Callee, popTrailingNodeArray(ExprsBegin));
    4158             :     }
    4159           0 :     case 'm':
    4160           0 :       First += 2;
    4161           0 :       return parseBinaryExpr(",");
    4162           0 :     case 'o':
    4163           0 :       First += 2;
    4164           0 :       return parsePrefixExpr("~");
    4165           0 :     case 'v':
    4166           0 :       return parseConversionExpr();
    4167             :     }
    4168             :     return nullptr;
    4169           1 :   case 'd':
    4170           1 :     switch (First[1]) {
    4171           0 :     case 'a': {
    4172           0 :       First += 2;
    4173           0 :       Node *Ex = parseExpr();
    4174           0 :       if (Ex == nullptr)
    4175             :         return Ex;
    4176           0 :       return make<DeleteExpr>(Ex, Global, /*is_array=*/true);
    4177             :     }
    4178           0 :     case 'c': {
    4179           0 :       First += 2;
    4180           0 :       Node *T = parseType();
    4181           0 :       if (T == nullptr)
    4182             :         return T;
    4183           0 :       Node *Ex = parseExpr();
    4184           0 :       if (Ex == nullptr)
    4185             :         return Ex;
    4186           0 :       return make<CastExpr>("dynamic_cast", T, Ex);
    4187             :     }
    4188           0 :     case 'e':
    4189           0 :       First += 2;
    4190           0 :       return parsePrefixExpr("*");
    4191           0 :     case 'l': {
    4192           0 :       First += 2;
    4193           0 :       Node *E = parseExpr();
    4194           0 :       if (E == nullptr)
    4195             :         return E;
    4196           0 :       return make<DeleteExpr>(E, Global, /*is_array=*/false);
    4197             :     }
    4198           0 :     case 'n':
    4199           0 :       return parseUnresolvedName();
    4200           0 :     case 's': {
    4201           0 :       First += 2;
    4202           0 :       Node *LHS = parseExpr();
    4203           0 :       if (LHS == nullptr)
    4204             :         return nullptr;
    4205           0 :       Node *RHS = parseExpr();
    4206           0 :       if (RHS == nullptr)
    4207             :         return nullptr;
    4208           0 :       return make<MemberExpr>(LHS, ".*", RHS);
    4209             :     }
    4210           1 :     case 't': {
    4211           1 :       First += 2;
    4212           1 :       Node *LHS = parseExpr();
    4213           1 :       if (LHS == nullptr)
    4214             :         return LHS;
    4215           1 :       Node *RHS = parseExpr();
    4216           1 :       if (RHS == nullptr)
    4217             :         return nullptr;
    4218           1 :       return make<MemberExpr>(LHS, ".", RHS);
    4219             :     }
    4220           0 :     case 'v':
    4221           0 :       First += 2;
    4222           0 :       return parseBinaryExpr("/");
    4223           0 :     case 'V':
    4224           0 :       First += 2;
    4225           0 :       return parseBinaryExpr("/=");
    4226             :     }
    4227             :     return nullptr;
    4228           2 :   case 'e':
    4229           2 :     switch (First[1]) {
    4230           0 :     case 'o':
    4231           0 :       First += 2;
    4232           0 :       return parseBinaryExpr("^");
    4233           0 :     case 'O':
    4234           0 :       First += 2;
    4235           0 :       return parseBinaryExpr("^=");
    4236           2 :     case 'q':
    4237           2 :       First += 2;
    4238           2 :       return parseBinaryExpr("==");
    4239             :     }
    4240             :     return nullptr;
    4241           0 :   case 'g':
    4242           0 :     switch (First[1]) {
    4243           0 :     case 'e':
    4244           0 :       First += 2;
    4245           0 :       return parseBinaryExpr(">=");
    4246           0 :     case 't':
    4247           0 :       First += 2;
    4248           0 :       return parseBinaryExpr(">");
    4249             :     }
    4250             :     return nullptr;
    4251           0 :   case 'i':
    4252           0 :     switch (First[1]) {
    4253           0 :     case 'x': {
    4254           0 :       First += 2;
    4255           0 :       Node *Base = parseExpr();
    4256           0 :       if (Base == nullptr)
    4257             :         return nullptr;
    4258           0 :       Node *Index = parseExpr();
    4259           0 :       if (Index == nullptr)
    4260             :         return Index;
    4261           0 :       return make<ArraySubscriptExpr>(Base, Index);
    4262             :     }
    4263           0 :     case 'l': {
    4264           0 :       First += 2;
    4265           0 :       size_t InitsBegin = Names.size();
    4266           0 :       while (!consumeIf('E')) {
    4267           0 :         Node *E = parseBracedExpr();
    4268           0 :         if (E == nullptr)
    4269           0 :           return nullptr;
    4270           0 :         Names.push_back(E);
    4271             :       }
    4272           0 :       return make<InitListExpr>(nullptr, popTrailingNodeArray(InitsBegin));
    4273             :     }
    4274             :     }
    4275             :     return nullptr;
    4276           0 :   case 'l':
    4277           0 :     switch (First[1]) {
    4278           0 :     case 'e':
    4279           0 :       First += 2;
    4280           0 :       return parseBinaryExpr("<=");
    4281           0 :     case 's':
    4282           0 :       First += 2;
    4283           0 :       return parseBinaryExpr("<<");
    4284           0 :     case 'S':
    4285           0 :       First += 2;
    4286           0 :       return parseBinaryExpr("<<=");
    4287           0 :     case 't':
    4288           0 :       First += 2;
    4289           0 :       return parseBinaryExpr("<");
    4290             :     }
    4291             :     return nullptr;
    4292           0 :   case 'm':
    4293           0 :     switch (First[1]) {
    4294           0 :     case 'i':
    4295           0 :       First += 2;
    4296           0 :       return parseBinaryExpr("-");
    4297           0 :     case 'I':
    4298           0 :       First += 2;
    4299           0 :       return parseBinaryExpr("-=");
    4300           0 :     case 'l':
    4301           0 :       First += 2;
    4302           0 :       return parseBinaryExpr("*");
    4303           0 :     case 'L':
    4304           0 :       First += 2;
    4305           0 :       return parseBinaryExpr("*=");
    4306           0 :     case 'm':
    4307           0 :       First += 2;
    4308             :       if (consumeIf('_'))
    4309           0 :         return parsePrefixExpr("--");
    4310           0 :       Node *Ex = parseExpr();
    4311           0 :       if (Ex == nullptr)
    4312             :         return nullptr;
    4313           0 :       return make<PostfixExpr>(Ex, "--");
    4314             :     }
    4315             :     return nullptr;
    4316           2 :   case 'n':
    4317           2 :     switch (First[1]) {
    4318           0 :     case 'a':
    4319             :     case 'w':
    4320           0 :       return parseNewExpr();
    4321           0 :     case 'e':
    4322           0 :       First += 2;
    4323           0 :       return parseBinaryExpr("!=");
    4324           0 :     case 'g':
    4325           0 :       First += 2;
    4326           0 :       return parsePrefixExpr("-");
    4327           2 :     case 't':
    4328           2 :       First += 2;
    4329           2 :       return parsePrefixExpr("!");
    4330           0 :     case 'x':
    4331           0 :       First += 2;
    4332           0 :       Node *Ex = parseExpr();
    4333           0 :       if (Ex == nullptr)
    4334             :         return Ex;
    4335           0 :       return make<EnclosingExpr>("noexcept (", Ex, ")");
    4336             :     }
    4337             :     return nullptr;
    4338           0 :   case 'o':
    4339           0 :     switch (First[1]) {
    4340           0 :     case 'n':
    4341           0 :       return parseUnresolvedName();
    4342           0 :     case 'o':
    4343           0 :       First += 2;
    4344           0 :       return parseBinaryExpr("||");
    4345           0 :     case 'r':
    4346           0 :       First += 2;
    4347           0 :       return parseBinaryExpr("|");
    4348           0 :     case 'R':
    4349           0 :       First += 2;
    4350           0 :       return parseBinaryExpr("|=");
    4351             :     }
    4352             :     return nullptr;
    4353           0 :   case 'p':
    4354           0 :     switch (First[1]) {
    4355           0 :     case 'm':
    4356           0 :       First += 2;
    4357           0 :       return parseBinaryExpr("->*");
    4358           0 :     case 'l':
    4359           0 :       First += 2;
    4360           0 :       return parseBinaryExpr("+");
    4361           0 :     case 'L':
    4362           0 :       First += 2;
    4363           0 :       return parseBinaryExpr("+=");
    4364           0 :     case 'p': {
    4365           0 :       First += 2;
    4366             :       if (consumeIf('_'))
    4367           0 :         return parsePrefixExpr("++");
    4368           0 :       Node *Ex = parseExpr();
    4369           0 :       if (Ex == nullptr)
    4370             :         return Ex;
    4371           0 :       return make<PostfixExpr>(Ex, "++");
    4372             :     }
    4373           0 :     case 's':
    4374           0 :       First += 2;
    4375           0 :       return parsePrefixExpr("+");
    4376           0 :     case 't': {
    4377           0 :       First += 2;
    4378           0 :       Node *L = parseExpr();
    4379           0 :       if (L == nullptr)
    4380             :         return nullptr;
    4381           0 :       Node *R = parseExpr();
    4382           0 :       if (R == nullptr)
    4383             :         return nullptr;
    4384           0 :       return make<MemberExpr>(L, "->", R);
    4385             :     }
    4386             :     }
    4387             :     return nullptr;
    4388           0 :   case 'q':
    4389           0 :     if (First[1] == 'u') {
    4390           0 :       First += 2;
    4391           0 :       Node *Cond = parseExpr();
    4392           0 :       if (Cond == nullptr)
    4393             :         return nullptr;
    4394           0 :       Node *LHS = parseExpr();
    4395           0 :       if (LHS == nullptr)
    4396             :         return nullptr;
    4397           0 :       Node *RHS = parseExpr();
    4398           0 :       if (RHS == nullptr)
    4399             :         return nullptr;
    4400           0 :       return make<ConditionalExpr>(Cond, LHS, RHS);
    4401           0 :     }
    4402             :     return nullptr;
    4403           0 :   case 'r':
    4404           0 :     switch (First[1]) {
    4405           0 :     case 'c': {
    4406           0 :       First += 2;
    4407           0 :       Node *T = parseType();
    4408           0 :       if (T == nullptr)
    4409             :         return T;
    4410           0 :       Node *Ex = parseExpr();
    4411           0 :       if (Ex == nullptr)
    4412             :         return Ex;
    4413           0 :       return make<CastExpr>("reinterpret_cast", T, Ex);
    4414             :     }
    4415           0 :     case 'm':
    4416           0 :       First += 2;
    4417           0 :       return parseBinaryExpr("%");
    4418           0 :     case 'M':
    4419           0 :       First += 2;
    4420           0 :       return parseBinaryExpr("%=");
    4421           0 :     case 's':
    4422           0 :       First += 2;
    4423           0 :       return parseBinaryExpr(">>");
    4424           0 :     case 'S':
    4425           0 :       First += 2;
    4426           0 :       return parseBinaryExpr(">>=");
    4427             :     }
    4428             :     return nullptr;
    4429          48 :   case 's':
    4430          48 :     switch (First[1]) {
    4431           0 :     case 'c': {
    4432           0 :       First += 2;
    4433           0 :       Node *T = parseType();
    4434           0 :       if (T == nullptr)
    4435             :         return T;
    4436           0 :       Node *Ex = parseExpr();
    4437           0 :       if (Ex == nullptr)
    4438             :         return Ex;
    4439           0 :       return make<CastExpr>("static_cast", T, Ex);
    4440             :     }
    4441          18 :     case 'p': {
    4442          18 :       First += 2;
    4443          18 :       Node *Child = parseExpr();
    4444          18 :       if (Child == nullptr)
    4445             :         return nullptr;
    4446          18 :       return make<ParameterPackExpansion>(Child);
    4447             :     }
    4448          30 :     case 'r':
    4449          30 :       return parseUnresolvedName();
    4450           0 :     case 't': {
    4451           0 :       First += 2;
    4452           0 :       Node *Ty = parseType();
    4453           0 :       if (Ty == nullptr)
    4454             :         return Ty;
    4455           0 :       return make<EnclosingExpr>("sizeof (", Ty, ")");
    4456             :     }
    4457           0 :     case 'z': {
    4458           0 :       First += 2;
    4459           0 :       Node *Ex = parseExpr();
    4460           0 :       if (Ex == nullptr)
    4461             :         return Ex;
    4462           0 :       return make<EnclosingExpr>("sizeof (", Ex, ")");
    4463             :     }
    4464           0 :     case 'Z':
    4465           0 :       First += 2;
    4466           0 :       if (look() == 'T') {
    4467           0 :         Node *R = parseTemplateParam();
    4468           0 :         if (R == nullptr)
    4469             :           return nullptr;
    4470           0 :         return make<SizeofParamPackExpr>(R);
    4471           0 :       } else if (look() == 'f') {
    4472           0 :         Node *FP = parseFunctionParam();
    4473           0 :         if (FP == nullptr)
    4474             :           return nullptr;
    4475           0 :         return make<EnclosingExpr>("sizeof... (", FP, ")");
    4476           0 :       }
    4477             :       return nullptr;
    4478           0 :     case 'P': {
    4479           0 :       First += 2;
    4480           0 :       size_t ArgsBegin = Names.size();
    4481           0 :       while (!consumeIf('E')) {
    4482           0 :         Node *Arg = parseTemplateArg();
    4483           0 :         if (Arg == nullptr)
    4484           0 :           return nullptr;
    4485           0 :         Names.push_back(Arg);
    4486             :       }
    4487             :       return make<EnclosingExpr>(
    4488           0 :           "sizeof... (", make<NodeArrayNode>(popTrailingNodeArray(ArgsBegin)),
    4489           0 :           ")");
    4490             :     }
    4491             :     }
    4492             :     return nullptr;
    4493           0 :   case 't':
    4494           0 :     switch (First[1]) {
    4495           0 :     case 'e': {
    4496           0 :       First += 2;
    4497           0 :       Node *Ex = parseExpr();
    4498           0 :       if (Ex == nullptr)
    4499             :         return Ex;
    4500           0 :       return make<EnclosingExpr>("typeid (", Ex, ")");
    4501             :     }
    4502           0 :     case 'i': {
    4503           0 :       First += 2;
    4504           0 :       Node *Ty = parseType();
    4505           0 :       if (Ty == nullptr)
    4506             :         return Ty;
    4507           0 :       return make<EnclosingExpr>("typeid (", Ty, ")");
    4508             :     }
    4509           0 :     case 'l': {
    4510           0 :       First += 2;
    4511           0 :       Node *Ty = parseType();
    4512           0 :       if (Ty == nullptr)
    4513             :         return nullptr;
    4514           0 :       size_t InitsBegin = Names.size();
    4515           0 :       while (!consumeIf('E')) {
    4516           0 :         Node *E = parseBracedExpr();
    4517           0 :         if (E == nullptr)
    4518           0 :           return nullptr;
    4519           0 :         Names.push_back(E);
    4520             :       }
    4521           0 :       return make<InitListExpr>(Ty, popTrailingNodeArray(InitsBegin));
    4522             :     }
    4523           0 :     case 'r':
    4524           0 :       First += 2;
    4525           0 :       return make<NameType>("throw");
    4526           0 :     case 'w': {
    4527           0 :       First += 2;
    4528           0 :       Node *Ex = parseExpr();
    4529           0 :       if (Ex == nullptr)
    4530             :         return nullptr;
    4531           0 :       return make<ThrowExpr>(Ex);
    4532             :     }
    4533             :     }
    4534             :     return nullptr;
    4535           7 :   case '1':
    4536             :   case '2':
    4537             :   case '3':
    4538             :   case '4':
    4539             :   case '5':
    4540             :   case '6':
    4541             :   case '7':
    4542             :   case '8':
    4543             :   case '9':
    4544           7 :     return parseUnresolvedName();
    4545             :   }
    4546             :   return nullptr;
    4547             : }
    4548             : 
    4549             : // <call-offset> ::= h <nv-offset> _
    4550             : //               ::= v <v-offset> _
    4551             : //
    4552             : // <nv-offset> ::= <offset number>
    4553             : //               # non-virtual base override
    4554             : //
    4555             : // <v-offset>  ::= <offset number> _ <virtual offset number>
    4556             : //               # virtual base override, with vcall offset
    4557           0 : bool Db::parseCallOffset() {
    4558             :   // Just scan through the call offset, we never add this information into the
    4559             :   // output.
    4560             :   if (consumeIf('h'))
    4561           0 :     return parseNumber(true).empty() || !consumeIf('_');
    4562             :   if (consumeIf('v'))
    4563           0 :     return parseNumber(true).empty() || !consumeIf('_') ||
    4564           0 :            parseNumber(true).empty() || !consumeIf('_');
    4565             :   return true;
    4566             : }
    4567             : 
    4568             : // <special-name> ::= TV <type>    # virtual table
    4569             : //                ::= TT <type>    # VTT structure (construction vtable index)
    4570             : //                ::= TI <type>    # typeinfo structure
    4571             : //                ::= TS <type>    # typeinfo name (null-terminated byte string)
    4572             : //                ::= Tc <call-offset> <call-offset> <base encoding>
    4573             : //                    # base is the nominal target function of thunk
    4574             : //                    # first call-offset is 'this' adjustment
    4575             : //                    # second call-offset is result adjustment
    4576             : //                ::= T <call-offset> <base encoding>
    4577             : //                    # base is the nominal target function of thunk
    4578             : //                ::= GV <object name> # Guard variable for one-time initialization
    4579             : //                                     # No <type>
    4580             : //                ::= TW <object name> # Thread-local wrapper
    4581             : //                ::= TH <object name> # Thread-local initialization
    4582             : //                ::= GR <object name> _             # First temporary
    4583             : //                ::= GR <object name> <seq-id> _    # Subsequent temporaries
    4584             : //      extension ::= TC <first type> <number> _ <second type> # construction vtable for second-in-first
    4585             : //      extension ::= GR <object name> # reference temporary for object
    4586         355 : Node *Db::parseSpecialName() {
    4587         710 :   switch (look()) {
    4588         355 :   case 'T':
    4589         355 :     switch (look(1)) {
    4590             :     // TV <type>    # virtual table
    4591         246 :     case 'V': {
    4592         246 :       First += 2;
    4593         246 :       Node *Ty = parseType();
    4594         246 :       if (Ty == nullptr)
    4595             :         return nullptr;
    4596         246 :       return make<SpecialName>("vtable for ", Ty);
    4597             :     }
    4598             :     // TT <type>    # VTT structure (construction vtable index)
    4599           0 :     case 'T': {
    4600           0 :       First += 2;
    4601           0 :       Node *Ty = parseType();
    4602           0 :       if (Ty == nullptr)
    4603             :         return nullptr;
    4604           0 :       return make<SpecialName>("VTT for ", Ty);
    4605             :     }
    4606             :     // TI <type>    # typeinfo structure
    4607         103 :     case 'I': {
    4608         103 :       First += 2;
    4609         103 :       Node *Ty = parseType();
    4610         103 :       if (Ty == nullptr)
    4611             :         return nullptr;
    4612         103 :       return make<SpecialName>("typeinfo for ", Ty);
    4613             :     }
    4614             :     // TS <type>    # typeinfo name (null-terminated byte string)
    4615           6 :     case 'S': {
    4616           6 :       First += 2;
    4617           6 :       Node *Ty = parseType();
    4618           6 :       if (Ty == nullptr)
    4619             :         return nullptr;
    4620           6 :       return make<SpecialName>("typeinfo name for ", Ty);
    4621             :     }
    4622             :     // Tc <call-offset> <call-offset> <base encoding>
    4623           0 :     case 'c': {
    4624           0 :       First += 2;
    4625           0 :       if (parseCallOffset() || parseCallOffset())
    4626             :         return nullptr;
    4627           0 :       Node *Encoding = parseEncoding();
    4628           0 :       if (Encoding == nullptr)
    4629             :         return nullptr;
    4630           0 :       return make<SpecialName>("covariant return thunk to ", Encoding);
    4631             :     }
    4632             :     // extension ::= TC <first type> <number> _ <second type>
    4633             :     //               # construction vtable for second-in-first
    4634           0 :     case 'C': {
    4635           0 :       First += 2;
    4636           0 :       Node *FirstType = parseType();
    4637           0 :       if (FirstType == nullptr)
    4638             :         return nullptr;
    4639           0 :       if (parseNumber(true).empty() || !consumeIf('_'))
    4640             :         return nullptr;
    4641           0 :       Node *SecondType = parseType();
    4642           0 :       if (SecondType == nullptr)
    4643             :         return nullptr;
    4644           0 :       return make<CtorVtableSpecialName>(SecondType, FirstType);
    4645             :     }
    4646             :     // TW <object name> # Thread-local wrapper
    4647           0 :     case 'W': {
    4648           0 :       First += 2;
    4649           0 :       Node *Name = parseName();
    4650           0 :       if (Name == nullptr)
    4651             :         return nullptr;
    4652           0 :       return make<SpecialName>("thread-local wrapper routine for ", Name);
    4653             :     }
    4654             :     // TH <object name> # Thread-local initialization
    4655           0 :     case 'H': {
    4656           0 :       First += 2;
    4657           0 :       Node *Name = parseName();
    4658           0 :       if (Name == nullptr)
    4659             :         return nullptr;
    4660           0 :       return make<SpecialName>("thread-local initialization routine for ", Name);
    4661             :     }
    4662             :     // T <call-offset> <base encoding>
    4663           0 :     default: {
    4664           0 :       ++First;
    4665             :       bool IsVirt = look() == 'v';
    4666           0 :       if (parseCallOffset())
    4667             :         return nullptr;
    4668           0 :       Node *BaseEncoding = parseEncoding();
    4669           0 :       if (BaseEncoding == nullptr)
    4670             :         return nullptr;
    4671           0 :       if (IsVirt)
    4672           0 :         return make<SpecialName>("virtual thunk to ", BaseEncoding);
    4673             :       else
    4674           0 :         return make<SpecialName>("non-virtual thunk to ", BaseEncoding);
    4675             :     }
    4676             :     }
    4677           0 :   case 'G':
    4678           0 :     switch (look(1)) {
    4679             :     // GV <object name> # Guard variable for one-time initialization
    4680           0 :     case 'V': {
    4681           0 :       First += 2;
    4682           0 :       Node *Name = parseName();
    4683           0 :       if (Name == nullptr)
    4684             :         return nullptr;
    4685           0 :       return make<SpecialName>("guard variable for ", Name);
    4686             :     }
    4687             :     // GR <object name> # reference temporary for object
    4688             :     // GR <object name> _             # First temporary
    4689             :     // GR <object name> <seq-id> _    # Subsequent temporaries
    4690           0 :     case 'R': {
    4691           0 :       First += 2;
    4692           0 :       Node *Name = parseName();
    4693           0 :       if (Name == nullptr)
    4694             :         return nullptr;
    4695             :       size_t Count;
    4696           0 :       bool ParsedSeqId = !parseSeqId(&Count);
    4697           0 :       if (!consumeIf('_') && ParsedSeqId)
    4698             :         return nullptr;
    4699           0 :       return make<SpecialName>("reference temporary for ", Name);
    4700             :     }
    4701             :     }
    4702             :   }
    4703             :   return nullptr;
    4704             : }
    4705             : 
    4706             : // <encoding> ::= <function name> <bare-function-type>
    4707             : //            ::= <data name>
    4708             : //            ::= <special-name>
    4709        3892 : Node *Db::parseEncoding() {
    4710       11676 :   if (look() == 'G' || look() == 'T')
    4711         355 :     return parseSpecialName();
    4712             : 
    4713             :   auto IsEndOfEncoding = [&] {
    4714             :     // The set of chars that can potentially follow an <encoding> (none of which
    4715             :     // can start a <type>). Enumerating these allows us to avoid speculative
    4716             :     // parsing.
    4717       18093 :     return numLeft() == 0 || look() == 'E' || look() == '.' || look() == '_';
    4718             :   };
    4719             : 
    4720             :   NameState NameInfo(this);
    4721        3537 :   Node *Name = parseName(&NameInfo);
    4722        3537 :   if (Name == nullptr)
    4723             :     return nullptr;
    4724             : 
    4725        3537 :   if (resolveForwardTemplateRefs(NameInfo))
    4726             :     return nullptr;
    4727             : 
    4728             :   if (IsEndOfEncoding())
    4729             :     return Name;
    4730             : 
    4731             :   Node *Attrs = nullptr;
    4732             :   if (consumeIf("Ua9enable_ifI")) {
    4733           1 :     size_t BeforeArgs = Names.size();
    4734           2 :     while (!consumeIf('E')) {
    4735           2 :       Node *Arg = parseTemplateArg();
    4736           2 :       if (Arg == nullptr)
    4737           0 :         return nullptr;
    4738           2 :       Names.push_back(Arg);
    4739             :     }
    4740           1 :     Attrs = make<EnableIfAttr>(popTrailingNodeArray(BeforeArgs));
    4741             :   }
    4742             : 
    4743             :   Node *ReturnType = nullptr;
    4744        3520 :   if (!NameInfo.CtorDtorConversion && NameInfo.EndsWithTemplateArgs) {
    4745         360 :     ReturnType = parseType();
    4746         360 :     if (ReturnType == nullptr)
    4747             :       return nullptr;
    4748             :   }
    4749             : 
    4750             :   if (consumeIf('v'))
    4751        1490 :     return make<FunctionEncoding>(ReturnType, Name, NodeArray(),
    4752             :                                   Attrs, NameInfo.CVQualifiers,
    4753        1490 :                                   NameInfo.ReferenceQualifier);
    4754             : 
    4755        2030 :   size_t ParamsBegin = Names.size();
    4756             :   do {
    4757        3891 :     Node *Ty = parseType();
    4758        3891 :     if (Ty == nullptr)
    4759        1075 :       return nullptr;
    4760        2816 :     Names.push_back(Ty);
    4761             :   } while (!IsEndOfEncoding());
    4762             : 
    4763             :   return make<FunctionEncoding>(ReturnType, Name,
    4764        1910 :                                 popTrailingNodeArray(ParamsBegin),
    4765             :                                 Attrs, NameInfo.CVQualifiers,
    4766         955 :                                 NameInfo.ReferenceQualifier);
    4767             : }
    4768             : 
    4769             : template <class Float>
    4770             : struct FloatData;
    4771             : 
    4772             : template <>
    4773             : struct FloatData<float>
    4774             : {
    4775             :     static const size_t mangled_size = 8;
    4776             :     static const size_t max_demangled_size = 24;
    4777             :     static constexpr const char* spec = "%af";
    4778             : };
    4779             : 
    4780             : constexpr const char* FloatData<float>::spec;
    4781             : 
    4782             : template <>
    4783             : struct FloatData<double>
    4784             : {
    4785             :     static const size_t mangled_size = 16;
    4786             :     static const size_t max_demangled_size = 32;
    4787             :     static constexpr const char* spec = "%a";
    4788             : };
    4789             : 
    4790             : constexpr const char* FloatData<double>::spec;
    4791             : 
    4792             : template <>
    4793             : struct FloatData<long double>
    4794             : {
    4795             : #if defined(__mips__) && defined(__mips_n64) || defined(__aarch64__) || \
    4796             :     defined(__wasm__)
    4797             :     static const size_t mangled_size = 32;
    4798             : #elif defined(__arm__) || defined(__mips__) || defined(__hexagon__)
    4799             :     static const size_t mangled_size = 16;
    4800             : #else
    4801             :     static const size_t mangled_size = 20;  // May need to be adjusted to 16 or 24 on other platforms
    4802             : #endif
    4803             :     static const size_t max_demangled_size = 40;
    4804             :     static constexpr const char *spec = "%LaL";
    4805             : };
    4806             : 
    4807             : constexpr const char *FloatData<long double>::spec;
    4808             : 
    4809           0 : template <class Float> Node *Db::parseFloatingLiteral() {
    4810             :   const size_t N = FloatData<Float>::mangled_size;
    4811           0 :   if (numLeft() <= N)
    4812             :     return nullptr;
    4813           0 :   StringView Data(First, First + N);
    4814           0 :   for (char C : Data)
    4815           0 :     if (!std::isxdigit(C))
    4816             :       return nullptr;
    4817           0 :   First += N;
    4818             :   if (!consumeIf('E'))
    4819             :     return nullptr;
    4820           0 :   return make<FloatExpr<Float>>(Data);
    4821             : }
    4822             : 
    4823             : // <seq-id> ::= <0-9A-Z>+
    4824        1978 : bool Db::parseSeqId(size_t *Out) {
    4825        4074 :   if (!(look() >= '0' && look() <= '9') &&
    4826         118 :       !(look() >= 'A' && look() <= 'Z'))
    4827             :     return true;
    4828             : 
    4829             :   size_t Id = 0;
    4830             :   while (true) {
    4831        9890 :     if (look() >= '0' && look() <= '9') {
    4832        1860 :       Id *= 36;
    4833        1860 :       Id += static_cast<size_t>(look() - '0');
    4834        2096 :     } else if (look() >= 'A' && look() <= 'Z') {
    4835         118 :       Id *= 36;
    4836         118 :       Id += static_cast<size_t>(look() - 'A') + 10;
    4837             :     } else {
    4838        1978 :       *Out = Id;
    4839        1978 :       return false;
    4840             :     }
    4841        1978 :     ++First;
    4842             :   }
    4843             : }
    4844             : 
    4845             : // <substitution> ::= S <seq-id> _
    4846             : //                ::= S_
    4847             : // <substitution> ::= Sa # ::std::allocator
    4848             : // <substitution> ::= Sb # ::std::basic_string
    4849             : // <substitution> ::= Ss # ::std::basic_string < char,
    4850             : //                                               ::std::char_traits<char>,
    4851             : //                                               ::std::allocator<char> >
    4852             : // <substitution> ::= Si # ::std::basic_istream<char,  std::char_traits<char> >
    4853             : // <substitution> ::= So # ::std::basic_ostream<char,  std::char_traits<char> >
    4854             : // <substitution> ::= Sd # ::std::basic_iostream<char, std::char_traits<char> >
    4855        3957 : Node *Db::parseSubstitution() {
    4856             :   if (!consumeIf('S'))
    4857             :     return nullptr;
    4858             : 
    4859        3957 :   if (std::islower(look())) {
    4860             :     Node *SpecialSub;
    4861        1488 :     switch (look()) {
    4862        1379 :     case 'a':
    4863        1379 :       ++First;
    4864        1379 :       SpecialSub = make<SpecialSubstitution>(SpecialSubKind::allocator);
    4865        1379 :       break;
    4866           0 :     case 'b':
    4867           0 :       ++First;
    4868           0 :       SpecialSub = make<SpecialSubstitution>(SpecialSubKind::basic_string);
    4869           0 :       break;
    4870          55 :     case 's':
    4871          55 :       ++First;
    4872          55 :       SpecialSub = make<SpecialSubstitution>(SpecialSubKind::string);
    4873          55 :       break;
    4874           0 :     case 'i':
    4875           0 :       ++First;
    4876           0 :       SpecialSub = make<SpecialSubstitution>(SpecialSubKind::istream);
    4877           0 :       break;
    4878          54 :     case 'o':
    4879          54 :       ++First;
    4880          54 :       SpecialSub = make<SpecialSubstitution>(SpecialSubKind::ostream);
    4881          54 :       break;
    4882           0 :     case 'd':
    4883           0 :       ++First;
    4884           0 :       SpecialSub = make<SpecialSubstitution>(SpecialSubKind::iostream);
    4885           0 :       break;
    4886             :     default:
    4887             :       return nullptr;
    4888             :     }
    4889             :     // Itanium C++ ABI 5.1.2: If a name that would use a built-in <substitution>
    4890             :     // has ABI tags, the tags are appended to the substitution; the result is a
    4891             :     // substitutable component.
    4892        1488 :     Node *WithTags = parseAbiTags(SpecialSub);
    4893        1488 :     if (WithTags != SpecialSub) {
    4894           0 :       Subs.push_back(WithTags);
    4895           0 :       SpecialSub = WithTags;
    4896             :     }
    4897             :     return SpecialSub;
    4898             :   }
    4899             : 
    4900             :   //                ::= S_
    4901             :   if (consumeIf('_')) {
    4902         491 :     if (Subs.empty())
    4903             :       return nullptr;
    4904         491 :     return Subs[0];
    4905             :   }
    4906             : 
    4907             :   //                ::= S <seq-id> _
    4908        1978 :   size_t Index = 0;
    4909        1978 :   if (parseSeqId(&Index))
    4910             :     return nullptr;
    4911        1978 :   ++Index;
    4912        3956 :   if (!consumeIf('_') || Index >= Subs.size())
    4913             :     return nullptr;
    4914        1978 :   return Subs[Index];
    4915             : }
    4916             : 
    4917             : // <template-param> ::= T_    # first template parameter
    4918             : //                  ::= T <parameter-2 non-negative number> _
    4919         766 : Node *Db::parseTemplateParam() {
    4920             :   if (!consumeIf('T'))
    4921             :     return nullptr;
    4922             : 
    4923         766 :   size_t Index = 0;
    4924             :   if (!consumeIf('_')) {
    4925         341 :     if (parsePositiveInteger(&Index))
    4926             :       return nullptr;
    4927         341 :     ++Index;
    4928             :     if (!consumeIf('_'))
    4929             :       return nullptr;
    4930             :   }
    4931             : 
    4932             :   // Itanium ABI 5.1.8: In a generic lambda, uses of auto in the parameter list
    4933             :   // are mangled as the corresponding artificial template type parameter.
    4934         766 :   if (ParsingLambdaParams)
    4935           0 :     return make<NameType>("auto");
    4936             : 
    4937             :   // If we're in a context where this <template-param> refers to a
    4938             :   // <template-arg> further ahead in the mangled name (currently just conversion
    4939             :   // operator types), then we should only look it up in the right context.
    4940         766 :   if (PermitForwardTemplateReferences) {
    4941           1 :     ForwardTemplateRefs.push_back(make<ForwardTemplateReference>(Index));
    4942           1 :     return ForwardTemplateRefs.back();
    4943             :   }
    4944             : 
    4945        1530 :   if (Index >= TemplateParams.size())
    4946             :     return nullptr;
    4947         765 :   return TemplateParams[Index];
    4948             : }
    4949             : 
    4950             : // <template-arg> ::= <type>                    # type or template
    4951             : //                ::= X <expression> E          # expression
    4952             : //                ::= <expr-primary>            # simple expressions
    4953             : //                ::= J <template-arg>* E       # argument pack
    4954             : //                ::= LZ <encoding> E           # extension
    4955       10467 : Node *Db::parseTemplateArg() {
    4956       20934 :   switch (look()) {
    4957         122 :   case 'X': {
    4958         122 :     ++First;
    4959         122 :     Node *Arg = parseExpr();
    4960         122 :     if (Arg == nullptr || !consumeIf('E'))
    4961             :       return nullptr;
    4962             :     return Arg;
    4963             :   }
    4964         543 :   case 'J': {
    4965         543 :     ++First;
    4966         543 :     size_t ArgsBegin = Names.size();
    4967         746 :     while (!consumeIf('E')) {
    4968         746 :       Node *Arg = parseTemplateArg();
    4969         746 :       if (Arg == nullptr)
    4970           0 :         return nullptr;
    4971         746 :       Names.push_back(Arg);
    4972             :     }
    4973         543 :     NodeArray Args = popTrailingNodeArray(ArgsBegin);
    4974         543 :     return make<TemplateArgumentPack>(Args);
    4975             :   }
    4976         536 :   case 'L': {
    4977             :     //                ::= LZ <encoding> E           # extension
    4978         536 :     if (look(1) == 'Z') {
    4979           0 :       First += 2;
    4980           0 :       Node *Arg = parseEncoding();
    4981           0 :       if (Arg == nullptr || !consumeIf('E'))
    4982             :         return nullptr;
    4983             :       return Arg;
    4984             :     }
    4985             :     //                ::= <expr-primary>            # simple expressions
    4986         536 :     return parseExprPrimary();
    4987             :   }
    4988        9266 :   default:
    4989        9266 :     return parseType();
    4990             :   }
    4991             : }
    4992             : 
    4993             : // <template-args> ::= I <template-arg>* E
    4994             : //     extension, the abi says <template-arg>+
    4995        5967 : Node *Db::parseTemplateArgs(bool TagTemplates) {
    4996             :   if (!consumeIf('I'))
    4997             :     return nullptr;
    4998             : 
    4999             :   // <template-params> refer to the innermost <template-args>. Clear out any
    5000             :   // outer args that we may have inserted into TemplateParams.
    5001        5967 :   if (TagTemplates)
    5002        1725 :     TemplateParams.clear();
    5003             : 
    5004        5967 :   size_t ArgsBegin = Names.size();
    5005             :   while (!consumeIf('E')) {
    5006        9719 :     if (TagTemplates) {
    5007        3808 :       auto OldParams = std::move(TemplateParams);
    5008        3808 :       Node *Arg = parseTemplateArg();
    5009        3808 :       TemplateParams = std::move(OldParams);
    5010        3808 :       if (Arg == nullptr)
    5011             :         return nullptr;
    5012        3808 :       Names.push_back(Arg);
    5013        3808 :       Node *TableEntry = Arg;
    5014        3808 :       if (Arg->getKind() == Node::KTemplateArgumentPack) {
    5015         307 :         TableEntry = make<ParameterPack>(
    5016         614 :             static_cast<TemplateArgumentPack*>(TableEntry)->getElements());
    5017             :       }
    5018        3808 :       TemplateParams.push_back(TableEntry);
    5019             :     } else {
    5020        5911 :       Node *Arg = parseTemplateArg();
    5021        5911 :       if (Arg == nullptr)
    5022           0 :         return nullptr;
    5023        5911 :       Names.push_back(Arg);
    5024             :     }
    5025             :   }
    5026        5967 :   return make<TemplateArgs>(popTrailingNodeArray(ArgsBegin));
    5027             : }
    5028             : 
    5029             : // <discriminator> := _ <non-negative number>      # when number < 10
    5030             : //                 := __ <non-negative number> _   # when number >= 10
    5031             : //  extension      := decimal-digit+               # at the end of string
    5032             : 
    5033             : const char*
    5034           8 : parse_discriminator(const char* first, const char* last)
    5035             : {
    5036             :     // parse but ignore discriminator
    5037           8 :     if (first != last)
    5038             :     {
    5039           8 :         if (*first == '_')
    5040             :         {
    5041           0 :             const char* t1 = first+1;
    5042           0 :             if (t1 != last)
    5043             :             {
    5044           0 :                 if (std::isdigit(*t1))
    5045           0 :                     first = t1+1;
    5046           0 :                 else if (*t1 == '_')
    5047             :                 {
    5048           0 :                     for (++t1; t1 != last && std::isdigit(*t1); ++t1)
    5049             :                         ;
    5050           0 :                     if (t1 != last && *t1 == '_')
    5051           0 :                         first = t1 + 1;
    5052             :                 }
    5053             :             }
    5054             :         }
    5055           8 :         else if (std::isdigit(*first))
    5056             :         {
    5057           0 :             const char* t1 = first+1;
    5058           0 :             for (; t1 != last && std::isdigit(*t1); ++t1)
    5059             :                 ;
    5060           0 :             if (t1 == last)
    5061             :                 first = last;
    5062             :         }
    5063             :     }
    5064           8 :     return first;
    5065             : }
    5066             : 
    5067             : // <mangled-name> ::= _Z <encoding>
    5068             : //                ::= <type>
    5069             : // extension      ::= ___Z <encoding> _block_invoke
    5070             : // extension      ::= ___Z <encoding> _block_invoke<decimal-digit>+
    5071             : // extension      ::= ___Z <encoding> _block_invoke_<decimal-digit>+
    5072        3901 : Node *Db::parse() {
    5073        3901 :   if (consumeIf("_Z")) {
    5074        3882 :     Node *Encoding = parseEncoding();
    5075        3882 :     if (Encoding == nullptr)
    5076             :       return nullptr;
    5077        4242 :     if (look() == '.') {
    5078           0 :       Encoding = make<DotSuffix>(Encoding, StringView(First, Last));
    5079           0 :       First = Last;
    5080             :     }
    5081        5614 :     if (numLeft() != 0)
    5082             :       return nullptr;
    5083        1372 :     return Encoding;
    5084             :   }
    5085             : 
    5086             :   if (consumeIf("___Z")) {
    5087           1 :     Node *Encoding = parseEncoding();
    5088           2 :     if (Encoding == nullptr || !consumeIf("_block_invoke"))
    5089             :       return nullptr;
    5090             :     bool RequireNumber = consumeIf('_');
    5091           2 :     if (parseNumber().empty() && RequireNumber)
    5092             :       return nullptr;
    5093           2 :     if (numLeft() != 0)
    5094             :       return nullptr;
    5095           1 :     return make<SpecialName>("invocation function for block in ", Encoding);
    5096             :   }
    5097             : 
    5098          18 :   Node *Ty = parseType();
    5099          36 :   if (numLeft() != 0)
    5100             :     return nullptr;
    5101           2 :   return Ty;
    5102             : }
    5103             : 
    5104             : bool initializeOutputStream(char *Buf, size_t *N, OutputStream &S,
    5105             :                             size_t InitSize) {
    5106             :   size_t BufferSize;
    5107        1420 :   if (Buf == nullptr) {
    5108        1340 :     Buf = static_cast<char *>(std::malloc(InitSize));
    5109        1340 :     if (Buf == nullptr)
    5110             :       return true;
    5111             :     BufferSize = InitSize;
    5112             :   } else
    5113          80 :     BufferSize = *N;
    5114             : 
    5115             :   S.reset(Buf, BufferSize);
    5116             :   return false;
    5117             : }
    5118             : 
    5119             : }  // unnamed namespace
    5120             : 
    5121             : enum {
    5122             :   unknown_error = -4,
    5123             :   invalid_args = -3,
    5124             :   invalid_mangled_name = -2,
    5125             :   memory_alloc_failure = -1,
    5126             :   success = 0,
    5127             : };
    5128             : 
    5129        3865 : char *llvm::itaniumDemangle(const char *MangledName, char *Buf,
    5130             :                             size_t *N, int *Status) {
    5131        3865 :   if (MangledName == nullptr || (Buf != nullptr && N == nullptr)) {
    5132           0 :     if (Status)
    5133           0 :       *Status = invalid_args;
    5134             :     return nullptr;
    5135             :   }
    5136             : 
    5137             :   int InternalStatus = success;
    5138        7730 :   Db Parser(MangledName, MangledName + std::strlen(MangledName));
    5139             :   OutputStream S;
    5140             : 
    5141        3865 :   Node *AST = Parser.parse();
    5142             : 
    5143        3865 :   if (AST == nullptr)
    5144             :     InternalStatus = invalid_mangled_name;
    5145             :   else if (initializeOutputStream(Buf, N, S, 1024))
    5146             :     InternalStatus = memory_alloc_failure;
    5147             :   else {
    5148             :     assert(Parser.ForwardTemplateRefs.empty());
    5149             :     AST->print(S);
    5150             :     S += '\0';
    5151        1340 :     if (N != nullptr)
    5152           0 :       *N = S.getCurrentPosition();
    5153        1340 :     Buf = S.getBuffer();
    5154             :   }
    5155             : 
    5156        3865 :   if (Status)
    5157         437 :     *Status = InternalStatus;
    5158        3865 :   return InternalStatus == success ? Buf : nullptr;
    5159             : }
    5160             : 
    5161             : namespace llvm {
    5162             : 
    5163           5 : ItaniumPartialDemangler::ItaniumPartialDemangler()
    5164          10 :     : RootNode(nullptr), Context(new Db{nullptr, nullptr}) {}
    5165             : 
    5166          12 : ItaniumPartialDemangler::~ItaniumPartialDemangler() {
    5167           6 :   delete static_cast<Db *>(Context);
    5168           6 : }
    5169             : 
    5170           1 : ItaniumPartialDemangler::ItaniumPartialDemangler(
    5171           1 :     ItaniumPartialDemangler &&Other)
    5172           1 :     : RootNode(Other.RootNode), Context(Other.Context) {
    5173           1 :   Other.Context = Other.RootNode = nullptr;
    5174           1 : }
    5175             : 
    5176           2 : ItaniumPartialDemangler &ItaniumPartialDemangler::
    5177             : operator=(ItaniumPartialDemangler &&Other) {
    5178             :   std::swap(RootNode, Other.RootNode);
    5179             :   std::swap(Context, Other.Context);
    5180           2 :   return *this;
    5181             : }
    5182             : 
    5183             : // Demangle MangledName into an AST, storing it into this->RootNode.
    5184          36 : bool ItaniumPartialDemangler::partialDemangle(const char *MangledName) {
    5185          36 :   Db *Parser = static_cast<Db *>(Context);
    5186          36 :   size_t Len = std::strlen(MangledName);
    5187          36 :   Parser->reset(MangledName, MangledName + Len);
    5188          36 :   RootNode = Parser->parse();
    5189          36 :   return RootNode == nullptr;
    5190             : }
    5191             : 
    5192          20 : static char *printNode(Node *RootNode, char *Buf, size_t *N) {
    5193             :   OutputStream S;
    5194             :   if (initializeOutputStream(Buf, N, S, 128))
    5195             :     return nullptr;
    5196             :   RootNode->print(S);
    5197             :   S += '\0';
    5198          20 :   if (N != nullptr)
    5199          20 :     *N = S.getCurrentPosition();
    5200          20 :   return S.getBuffer();
    5201             : }
    5202             : 
    5203          20 : char *ItaniumPartialDemangler::getFunctionBaseName(char *Buf, size_t *N) const {
    5204          20 :   if (!isFunction())
    5205             :     return nullptr;
    5206             : 
    5207          20 :   Node *Name = static_cast<FunctionEncoding *>(RootNode)->getName();
    5208             : 
    5209             :   while (true) {
    5210          82 :     switch (Name->getKind()) {
    5211           2 :     case Node::KAbiTagAttr:
    5212           2 :       Name = static_cast<AbiTagAttr *>(Name)->Base;
    5213           2 :       continue;
    5214           1 :     case Node::KStdQualifiedName:
    5215           1 :       Name = static_cast<StdQualifiedName *>(Name)->Child;
    5216           1 :       continue;
    5217          17 :     case Node::KNestedName:
    5218          17 :       Name = static_cast<NestedName *>(Name)->Name;
    5219          17 :       continue;
    5220           4 :     case Node::KLocalName:
    5221           4 :       Name = static_cast<LocalName *>(Name)->Entity;
    5222           4 :       continue;
    5223           7 :     case Node::KNameWithTemplateArgs:
    5224           7 :       Name = static_cast<NameWithTemplateArgs *>(Name)->Name;
    5225           7 :       continue;
    5226          20 :     default:
    5227          20 :       return printNode(Name, Buf, N);
    5228             :     }
    5229             :   }
    5230             : }
    5231             : 
    5232          20 : char *ItaniumPartialDemangler::getFunctionDeclContextName(char *Buf,
    5233             :                                                           size_t *N) const {
    5234          20 :   if (!isFunction())
    5235             :     return nullptr;
    5236          20 :   Node *Name = static_cast<FunctionEncoding *>(RootNode)->getName();
    5237             : 
    5238             :   OutputStream S;
    5239             :   if (initializeOutputStream(Buf, N, S, 128))
    5240             :     return nullptr;
    5241             : 
    5242             :  KeepGoingLocalFunction:
    5243             :   while (true) {
    5244          33 :     if (Name->getKind() == Node::KAbiTagAttr) {
    5245           1 :       Name = static_cast<AbiTagAttr *>(Name)->Base;
    5246           1 :       continue;
    5247             :     }
    5248          38 :     if (Name->getKind() == Node::KNameWithTemplateArgs) {
    5249           7 :       Name = static_cast<NameWithTemplateArgs *>(Name)->Name;
    5250           7 :       continue;
    5251             :     }
    5252             :     break;
    5253             :   }
    5254             : 
    5255          24 :   switch (Name->getKind()) {
    5256             :   case Node::KStdQualifiedName:
    5257           1 :     S += "std";
    5258           1 :     break;
    5259          17 :   case Node::KNestedName:
    5260          17 :     static_cast<NestedName *>(Name)->Qual->print(S);
    5261             :     break;
    5262           4 :   case Node::KLocalName: {
    5263             :     auto *LN = static_cast<LocalName *>(Name);
    5264           4 :     LN->Encoding->print(S);
    5265           4 :     S += "::";
    5266           4 :     Name = LN->Entity;
    5267           4 :     goto KeepGoingLocalFunction;
    5268             :   }
    5269             :   default:
    5270             :     break;
    5271             :   }
    5272             :   S += '\0';
    5273          20 :   if (N != nullptr)
    5274          20 :     *N = S.getCurrentPosition();
    5275          20 :   return S.getBuffer();
    5276             : }
    5277             : 
    5278           0 : char *ItaniumPartialDemangler::getFunctionName(char *Buf, size_t *N) const {
    5279           0 :   if (!isFunction())
    5280             :     return nullptr;
    5281           0 :   auto *Name = static_cast<FunctionEncoding *>(RootNode)->getName();
    5282           0 :   return printNode(Name, Buf, N);
    5283             : }
    5284             : 
    5285          20 : char *ItaniumPartialDemangler::getFunctionParameters(char *Buf,
    5286             :                                                      size_t *N) const {
    5287          20 :   if (!isFunction())
    5288             :     return nullptr;
    5289          20 :   NodeArray Params = static_cast<FunctionEncoding *>(RootNode)->getParams();
    5290             : 
    5291             :   OutputStream S;
    5292             :   if (initializeOutputStream(Buf, N, S, 128))
    5293             :     return nullptr;
    5294             : 
    5295             :   S += '(';
    5296          20 :   Params.printWithComma(S);
    5297             :   S += ')';
    5298             :   S += '\0';
    5299          20 :   if (N != nullptr)
    5300          20 :     *N = S.getCurrentPosition();
    5301          20 :   return S.getBuffer();
    5302             : }
    5303             : 
    5304          20 : char *ItaniumPartialDemangler::getFunctionReturnType(
    5305             :     char *Buf, size_t *N) const {
    5306          20 :   if (!isFunction())
    5307             :     return nullptr;
    5308             : 
    5309             :   OutputStream S;
    5310             :   if (initializeOutputStream(Buf, N, S, 128))
    5311             :     return nullptr;
    5312             : 
    5313          20 :   if (Node *Ret = static_cast<FunctionEncoding *>(RootNode)->getReturnType())
    5314             :     Ret->print(S);
    5315             : 
    5316             :   S += '\0';
    5317          20 :   if (N != nullptr)
    5318          20 :     *N = S.getCurrentPosition();
    5319          20 :   return S.getBuffer();
    5320             : }
    5321             : 
    5322           0 : char *ItaniumPartialDemangler::finishDemangle(char *Buf, size_t *N) const {
    5323             :   assert(RootNode != nullptr && "must call partialDemangle()");
    5324           0 :   return printNode(static_cast<Node *>(RootNode), Buf, N);
    5325             : }
    5326             : 
    5327           2 : bool ItaniumPartialDemangler::hasFunctionQualifiers() const {
    5328             :   assert(RootNode != nullptr && "must call partialDemangle()");
    5329           2 :   if (!isFunction())
    5330             :     return false;
    5331           2 :   auto *E = static_cast<FunctionEncoding *>(RootNode);
    5332           2 :   return E->getCVQuals() != QualNone || E->getRefQual() != FrefQualNone;
    5333             : }
    5334             : 
    5335           9 : bool ItaniumPartialDemangler::isCtorOrDtor() const {
    5336           9 :   Node *N = static_cast<Node *>(RootNode);
    5337          30 :   while (N) {
    5338          30 :     switch (N->getKind()) {
    5339             :     default:
    5340             :       return false;
    5341           7 :     case Node::KCtorDtorName:
    5342           7 :       return true;
    5343             : 
    5344           1 :     case Node::KAbiTagAttr:
    5345           1 :       N = static_cast<AbiTagAttr *>(N)->Base;
    5346           1 :       break;
    5347           9 :     case Node::KFunctionEncoding:
    5348           9 :       N = static_cast<FunctionEncoding *>(N)->getName();
    5349           9 :       break;
    5350           0 :     case Node::KLocalName:
    5351           0 :       N = static_cast<LocalName *>(N)->Entity;
    5352           0 :       break;
    5353           3 :     case Node::KNameWithTemplateArgs:
    5354           3 :       N = static_cast<NameWithTemplateArgs *>(N)->Name;
    5355           3 :       break;
    5356           8 :     case Node::KNestedName:
    5357           8 :       N = static_cast<NestedName *>(N)->Name;
    5358           8 :       break;
    5359           0 :     case Node::KStdQualifiedName:
    5360           0 :       N = static_cast<StdQualifiedName *>(N)->Child;
    5361           0 :       break;
    5362             :     }
    5363             :   }
    5364             :   return false;
    5365             : }
    5366             : 
    5367         130 : bool ItaniumPartialDemangler::isFunction() const {
    5368             :   assert(RootNode != nullptr && "must call partialDemangle()");
    5369         130 :   return static_cast<Node *>(RootNode)->getKind() == Node::KFunctionEncoding;
    5370             : }
    5371             : 
    5372          25 : bool ItaniumPartialDemangler::isSpecialName() const {
    5373             :   assert(RootNode != nullptr && "must call partialDemangle()");
    5374          25 :   auto K = static_cast<Node *>(RootNode)->getKind();
    5375          25 :   return K == Node::KSpecialName || K == Node::KCtorVtableSpecialName;
    5376             : }
    5377             : 
    5378          23 : bool ItaniumPartialDemangler::isData() const {
    5379          23 :   return !isFunction() && !isSpecialName();
    5380             : }
    5381             : 
    5382             : }

Generated by: LCOV version 1.13