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