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