include/llvm/Demangle/ItaniumDemangle.h

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