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