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