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