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