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