contrib/llvm/include/llvm/Demangle/ItaniumDemangle.h

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