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