1 //===- MicrosoftDemangle.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 // This file defines a demangler for MSVC-style mangled symbols.
11 //
12 // This file has no dependencies on the rest of LLVM so that it can be
13 // easily reused in other programs such as libcxxabi.
14 //
15 //===----------------------------------------------------------------------===//
16 
17 #include "llvm/Demangle/MicrosoftDemangle.h"
18 #include "llvm/Demangle/Demangle.h"
19 #include "llvm/Demangle/MicrosoftDemangleNodes.h"
20 
21 #include "llvm/Demangle/Compiler.h"
22 #include "llvm/Demangle/StringView.h"
23 #include "llvm/Demangle/Utility.h"
24 
25 #include <array>
26 #include <cctype>
27 #include <cstdio>
28 #include <tuple>
29 
30 using namespace llvm;
31 using namespace ms_demangle;
32 
33 static bool startsWithDigit(StringView S) {
34   return !S.empty() && std::isdigit(S.front());
35 }
36 
37 
38 struct NodeList {
39   Node *N = nullptr;
40   NodeList *Next = nullptr;
41 };
42 
43 static bool isMemberPointer(StringView MangledName) {
44   switch (MangledName.popFront()) {
45   case '$':
46     // This is probably an rvalue reference (e.g. $$Q), and you cannot have an
47     // rvalue reference to a member.
48     return false;
49   case 'A':
50     // 'A' indicates a reference, and you cannot have a reference to a member
51     // function or member.
52     return false;
53   case 'P':
54   case 'Q':
55   case 'R':
56   case 'S':
57     // These 4 values indicate some kind of pointer, but we still don't know
58     // what.
59     break;
60   default:
61     assert(false && "Ty is not a pointer type!");
62   }
63 
64   // If it starts with a number, then 6 indicates a non-member function
65   // pointer, and 8 indicates a member function pointer.
66   if (startsWithDigit(MangledName)) {
67     assert(MangledName[0] == '6' || MangledName[0] == '8');
68     return (MangledName[0] == '8');
69   }
70 
71   // Remove ext qualifiers since those can appear on either type and are
72   // therefore not indicative.
73   MangledName.consumeFront('E'); // 64-bit
74   MangledName.consumeFront('I'); // restrict
75   MangledName.consumeFront('F'); // unaligned
76 
77   assert(!MangledName.empty());
78 
79   // The next value should be either ABCD (non-member) or QRST (member).
80   switch (MangledName.front()) {
81   case 'A':
82   case 'B':
83   case 'C':
84   case 'D':
85     return false;
86   case 'Q':
87   case 'R':
88   case 'S':
89   case 'T':
90     return true;
91   default:
92     assert(false);
93   }
94   return false;
95 }
96 
97 static SpecialIntrinsicKind
98 consumeSpecialIntrinsicKind(StringView &MangledName) {
99   if (MangledName.consumeFront("?_7"))
100     return SpecialIntrinsicKind::Vftable;
101   if (MangledName.consumeFront("?_8"))
102     return SpecialIntrinsicKind::Vbtable;
103   if (MangledName.consumeFront("?_9"))
104     return SpecialIntrinsicKind::VcallThunk;
105   if (MangledName.consumeFront("?_A"))
106     return SpecialIntrinsicKind::Typeof;
107   if (MangledName.consumeFront("?_B"))
108     return SpecialIntrinsicKind::LocalStaticGuard;
109   if (MangledName.consumeFront("?_C"))
110     return SpecialIntrinsicKind::StringLiteralSymbol;
111   if (MangledName.consumeFront("?_P"))
112     return SpecialIntrinsicKind::UdtReturning;
113   if (MangledName.consumeFront("?_R0"))
114     return SpecialIntrinsicKind::RttiTypeDescriptor;
115   if (MangledName.consumeFront("?_R1"))
116     return SpecialIntrinsicKind::RttiBaseClassDescriptor;
117   if (MangledName.consumeFront("?_R2"))
118     return SpecialIntrinsicKind::RttiBaseClassArray;
119   if (MangledName.consumeFront("?_R3"))
120     return SpecialIntrinsicKind::RttiClassHierarchyDescriptor;
121   if (MangledName.consumeFront("?_R4"))
122     return SpecialIntrinsicKind::RttiCompleteObjLocator;
123   if (MangledName.consumeFront("?_S"))
124     return SpecialIntrinsicKind::LocalVftable;
125   if (MangledName.consumeFront("?__E"))
126     return SpecialIntrinsicKind::DynamicInitializer;
127   if (MangledName.consumeFront("?__F"))
128     return SpecialIntrinsicKind::DynamicAtexitDestructor;
129   if (MangledName.consumeFront("?__J"))
130     return SpecialIntrinsicKind::LocalStaticThreadGuard;
131   return SpecialIntrinsicKind::None;
132 }
133 
134 static bool startsWithLocalScopePattern(StringView S) {
135   if (!S.consumeFront('?'))
136     return false;
137   if (S.size() < 2)
138     return false;
139 
140   size_t End = S.find('?');
141   if (End == StringView::npos)
142     return false;
143   StringView Candidate = S.substr(0, End);
144   if (Candidate.empty())
145     return false;
146 
147   // \?[0-9]\?
148   // ?@? is the discriminator 0.
149   if (Candidate.size() == 1)
150     return Candidate[0] == '@' || (Candidate[0] >= '0' && Candidate[0] <= '9');
151 
152   // If it's not 0-9, then it's an encoded number terminated with an @
153   if (Candidate.back() != '@')
154     return false;
155   Candidate = Candidate.dropBack();
156 
157   // An encoded number starts with B-P and all subsequent digits are in A-P.
158   // Note that the reason the first digit cannot be A is two fold.  First, it
159   // would create an ambiguity with ?A which delimits the beginning of an
160   // anonymous namespace.  Second, A represents 0, and you don't start a multi
161   // digit number with a leading 0.  Presumably the anonymous namespace
162   // ambiguity is also why single digit encoded numbers use 0-9 rather than A-J.
163   if (Candidate[0] < 'B' || Candidate[0] > 'P')
164     return false;
165   Candidate = Candidate.dropFront();
166   while (!Candidate.empty()) {
167     if (Candidate[0] < 'A' || Candidate[0] > 'P')
168       return false;
169     Candidate = Candidate.dropFront();
170   }
171 
172   return true;
173 }
174 
175 static bool isTagType(StringView S) {
176   switch (S.front()) {
177   case 'T': // union
178   case 'U': // struct
179   case 'V': // class
180   case 'W': // enum
181     return true;
182   }
183   return false;
184 }
185 
186 static bool isCustomType(StringView S) { return S[0] == '?'; }
187 
188 static bool isPointerType(StringView S) {
189   if (S.startsWith("$$Q")) // foo &&
190     return true;
191 
192   switch (S.front()) {
193   case 'A': // foo &
194   case 'P': // foo *
195   case 'Q': // foo *const
196   case 'R': // foo *volatile
197   case 'S': // foo *const volatile
198     return true;
199   }
200   return false;
201 }
202 
203 static bool isArrayType(StringView S) { return S[0] == 'Y'; }
204 
205 static bool isFunctionType(StringView S) {
206   return S.startsWith("$$A8@@") || S.startsWith("$$A6");
207 }
208 
209 static FunctionRefQualifier
210 demangleFunctionRefQualifier(StringView &MangledName) {
211   if (MangledName.consumeFront('G'))
212     return FunctionRefQualifier::Reference;
213   else if (MangledName.consumeFront('H'))
214     return FunctionRefQualifier::RValueReference;
215   return FunctionRefQualifier::None;
216 }
217 
218 static std::pair<Qualifiers, PointerAffinity>
219 demanglePointerCVQualifiers(StringView &MangledName) {
220   if (MangledName.consumeFront("$$Q"))
221     return std::make_pair(Q_None, PointerAffinity::RValueReference);
222 
223   switch (MangledName.popFront()) {
224   case 'A':
225     return std::make_pair(Q_None, PointerAffinity::Reference);
226   case 'P':
227     return std::make_pair(Q_None, PointerAffinity::Pointer);
228   case 'Q':
229     return std::make_pair(Q_Const, PointerAffinity::Pointer);
230   case 'R':
231     return std::make_pair(Q_Volatile, PointerAffinity::Pointer);
232   case 'S':
233     return std::make_pair(Qualifiers(Q_Const | Q_Volatile),
234                           PointerAffinity::Pointer);
235   default:
236     assert(false && "Ty is not a pointer type!");
237   }
238   return std::make_pair(Q_None, PointerAffinity::Pointer);
239 }
240 
241 StringView Demangler::copyString(StringView Borrowed) {
242   char *Stable = Arena.allocUnalignedBuffer(Borrowed.size() + 1);
243   std::strcpy(Stable, Borrowed.begin());
244 
245   return {Stable, Borrowed.size()};
246 }
247 
248 SpecialTableSymbolNode *
249 Demangler::demangleSpecialTableSymbolNode(StringView &MangledName,
250                                           SpecialIntrinsicKind K) {
251   NamedIdentifierNode *NI = Arena.alloc<NamedIdentifierNode>();
252   switch (K) {
253   case SpecialIntrinsicKind::Vftable:
254     NI->Name = "`vftable'";
255     break;
256   case SpecialIntrinsicKind::Vbtable:
257     NI->Name = "`vbtable'";
258     break;
259   case SpecialIntrinsicKind::LocalVftable:
260     NI->Name = "`local vftable'";
261     break;
262   case SpecialIntrinsicKind::RttiCompleteObjLocator:
263     NI->Name = "`RTTI Complete Object Locator'";
264     break;
265   default:
266     LLVM_BUILTIN_UNREACHABLE;
267   }
268   QualifiedNameNode *QN = demangleNameScopeChain(MangledName, NI);
269   SpecialTableSymbolNode *STSN = Arena.alloc<SpecialTableSymbolNode>();
270   STSN->Name = QN;
271   bool IsMember = false;
272   char Front = MangledName.popFront();
273   if (Front != '6' && Front != '7') {
274     Error = true;
275     return nullptr;
276   }
277 
278   std::tie(STSN->Quals, IsMember) = demangleQualifiers(MangledName);
279   if (!MangledName.consumeFront('@'))
280     STSN->TargetName = demangleFullyQualifiedTypeName(MangledName);
281   return STSN;
282 }
283 
284 LocalStaticGuardVariableNode *
285 Demangler::demangleLocalStaticGuard(StringView &MangledName) {
286   LocalStaticGuardIdentifierNode *LSGI =
287       Arena.alloc<LocalStaticGuardIdentifierNode>();
288   QualifiedNameNode *QN = demangleNameScopeChain(MangledName, LSGI);
289   LocalStaticGuardVariableNode *LSGVN =
290       Arena.alloc<LocalStaticGuardVariableNode>();
291   LSGVN->Name = QN;
292 
293   if (MangledName.consumeFront("4IA"))
294     LSGVN->IsVisible = false;
295   else if (MangledName.consumeFront("5"))
296     LSGVN->IsVisible = true;
297   else {
298     Error = true;
299     return nullptr;
300   }
301 
302   if (!MangledName.empty())
303     LSGI->ScopeIndex = demangleUnsigned(MangledName);
304   return LSGVN;
305 }
306 
307 static NamedIdentifierNode *synthesizeNamedIdentifier(ArenaAllocator &Arena,
308                                                       StringView Name) {
309   NamedIdentifierNode *Id = Arena.alloc<NamedIdentifierNode>();
310   Id->Name = Name;
311   return Id;
312 }
313 
314 static QualifiedNameNode *synthesizeQualifiedName(ArenaAllocator &Arena,
315                                                   IdentifierNode *Identifier) {
316   QualifiedNameNode *QN = Arena.alloc<QualifiedNameNode>();
317   QN->Components = Arena.alloc<NodeArrayNode>();
318   QN->Components->Count = 1;
319   QN->Components->Nodes = Arena.allocArray<Node *>(1);
320   QN->Components->Nodes[0] = Identifier;
321   return QN;
322 }
323 
324 static QualifiedNameNode *synthesizeQualifiedName(ArenaAllocator &Arena,
325                                                   StringView Name) {
326   NamedIdentifierNode *Id = synthesizeNamedIdentifier(Arena, Name);
327   return synthesizeQualifiedName(Arena, Id);
328 }
329 
330 static VariableSymbolNode *synthesizeVariable(ArenaAllocator &Arena,
331                                               TypeNode *Type,
332                                               StringView VariableName) {
333   VariableSymbolNode *VSN = Arena.alloc<VariableSymbolNode>();
334   VSN->Type = Type;
335   VSN->Name = synthesizeQualifiedName(Arena, VariableName);
336   return VSN;
337 }
338 
339 VariableSymbolNode *Demangler::demangleUntypedVariable(
340     ArenaAllocator &Arena, StringView &MangledName, StringView VariableName) {
341   NamedIdentifierNode *NI = synthesizeNamedIdentifier(Arena, VariableName);
342   QualifiedNameNode *QN = demangleNameScopeChain(MangledName, NI);
343   VariableSymbolNode *VSN = Arena.alloc<VariableSymbolNode>();
344   VSN->Name = QN;
345   if (MangledName.consumeFront("8"))
346     return VSN;
347 
348   Error = true;
349   return nullptr;
350 }
351 
352 VariableSymbolNode *
353 Demangler::demangleRttiBaseClassDescriptorNode(ArenaAllocator &Arena,
354                                                StringView &MangledName) {
355   RttiBaseClassDescriptorNode *RBCDN =
356       Arena.alloc<RttiBaseClassDescriptorNode>();
357   RBCDN->NVOffset = demangleUnsigned(MangledName);
358   RBCDN->VBPtrOffset = demangleSigned(MangledName);
359   RBCDN->VBTableOffset = demangleUnsigned(MangledName);
360   RBCDN->Flags = demangleUnsigned(MangledName);
361   if (Error)
362     return nullptr;
363 
364   VariableSymbolNode *VSN = Arena.alloc<VariableSymbolNode>();
365   VSN->Name = demangleNameScopeChain(MangledName, RBCDN);
366   MangledName.consumeFront('8');
367   return VSN;
368 }
369 
370 FunctionSymbolNode *Demangler::demangleInitFiniStub(StringView &MangledName,
371                                                     bool IsDestructor) {
372   DynamicStructorIdentifierNode *DSIN =
373       Arena.alloc<DynamicStructorIdentifierNode>();
374   DSIN->IsDestructor = IsDestructor;
375 
376   bool IsKnownStaticDataMember = false;
377   if (MangledName.consumeFront('?'))
378     IsKnownStaticDataMember = true;
379 
380   QualifiedNameNode *QN = demangleFullyQualifiedSymbolName(MangledName);
381 
382   SymbolNode *Symbol = demangleEncodedSymbol(MangledName, QN);
383   FunctionSymbolNode *FSN = nullptr;
384   Symbol->Name = QN;
385 
386   if (Symbol->kind() == NodeKind::VariableSymbol) {
387     DSIN->Variable = static_cast<VariableSymbolNode *>(Symbol);
388 
389     // Older versions of clang mangled this type of symbol incorrectly.  They
390     // would omit the leading ? and they would only emit a single @ at the end.
391     // The correct mangling is a leading ? and 2 trailing @ signs.  Handle
392     // both cases.
393     int AtCount = IsKnownStaticDataMember ? 2 : 1;
394     for (int I = 0; I < AtCount; ++I) {
395       if (MangledName.consumeFront('@'))
396         continue;
397       Error = true;
398       return nullptr;
399     }
400 
401     FSN = demangleFunctionEncoding(MangledName);
402     FSN->Name = synthesizeQualifiedName(Arena, DSIN);
403   } else {
404     if (IsKnownStaticDataMember) {
405       // This was supposed to be a static data member, but we got a function.
406       Error = true;
407       return nullptr;
408     }
409 
410     FSN = static_cast<FunctionSymbolNode *>(Symbol);
411     DSIN->Name = Symbol->Name;
412     FSN->Name = synthesizeQualifiedName(Arena, DSIN);
413   }
414 
415   return FSN;
416 }
417 
418 SymbolNode *Demangler::demangleSpecialIntrinsic(StringView &MangledName) {
419   SpecialIntrinsicKind SIK = consumeSpecialIntrinsicKind(MangledName);
420   if (SIK == SpecialIntrinsicKind::None)
421     return nullptr;
422 
423   switch (SIK) {
424   case SpecialIntrinsicKind::StringLiteralSymbol:
425     return demangleStringLiteral(MangledName);
426   case SpecialIntrinsicKind::Vftable:
427   case SpecialIntrinsicKind::Vbtable:
428   case SpecialIntrinsicKind::LocalVftable:
429   case SpecialIntrinsicKind::RttiCompleteObjLocator:
430     return demangleSpecialTableSymbolNode(MangledName, SIK);
431   case SpecialIntrinsicKind::VcallThunk:
432     return demangleVcallThunkNode(MangledName);
433   case SpecialIntrinsicKind::LocalStaticGuard:
434     return demangleLocalStaticGuard(MangledName);
435   case SpecialIntrinsicKind::RttiTypeDescriptor: {
436     TypeNode *T = demangleType(MangledName, QualifierMangleMode::Result);
437     if (Error)
438       break;
439     if (!MangledName.consumeFront("@8"))
440       break;
441     if (!MangledName.empty())
442       break;
443     return synthesizeVariable(Arena, T, "`RTTI Type Descriptor'");
444   }
445   case SpecialIntrinsicKind::RttiBaseClassArray:
446     return demangleUntypedVariable(Arena, MangledName,
447                                    "`RTTI Base Class Array'");
448   case SpecialIntrinsicKind::RttiClassHierarchyDescriptor:
449     return demangleUntypedVariable(Arena, MangledName,
450                                    "`RTTI Class Hierarchy Descriptor'");
451   case SpecialIntrinsicKind::RttiBaseClassDescriptor:
452     return demangleRttiBaseClassDescriptorNode(Arena, MangledName);
453   case SpecialIntrinsicKind::DynamicInitializer:
454     return demangleInitFiniStub(MangledName, false);
455   case SpecialIntrinsicKind::DynamicAtexitDestructor:
456     return demangleInitFiniStub(MangledName, true);
457   default:
458     break;
459   }
460   Error = true;
461   return nullptr;
462 }
463 
464 IdentifierNode *
465 Demangler::demangleFunctionIdentifierCode(StringView &MangledName) {
466   assert(MangledName.startsWith('?'));
467   MangledName = MangledName.dropFront();
468 
469   if (MangledName.consumeFront("__"))
470     return demangleFunctionIdentifierCode(
471         MangledName, FunctionIdentifierCodeGroup::DoubleUnder);
472   else if (MangledName.consumeFront("_"))
473     return demangleFunctionIdentifierCode(MangledName,
474                                           FunctionIdentifierCodeGroup::Under);
475   return demangleFunctionIdentifierCode(MangledName,
476                                         FunctionIdentifierCodeGroup::Basic);
477 }
478 
479 StructorIdentifierNode *
480 Demangler::demangleStructorIdentifier(StringView &MangledName,
481                                       bool IsDestructor) {
482   StructorIdentifierNode *N = Arena.alloc<StructorIdentifierNode>();
483   N->IsDestructor = IsDestructor;
484   return N;
485 }
486 
487 ConversionOperatorIdentifierNode *
488 Demangler::demangleConversionOperatorIdentifier(StringView &MangledName) {
489   ConversionOperatorIdentifierNode *N =
490       Arena.alloc<ConversionOperatorIdentifierNode>();
491   return N;
492 }
493 
494 LiteralOperatorIdentifierNode *
495 Demangler::demangleLiteralOperatorIdentifier(StringView &MangledName) {
496   LiteralOperatorIdentifierNode *N =
497       Arena.alloc<LiteralOperatorIdentifierNode>();
498   N->Name = demangleSimpleString(MangledName, false);
499   return N;
500 }
501 
502 static IntrinsicFunctionKind
503 translateIntrinsicFunctionCode(char CH, FunctionIdentifierCodeGroup Group) {
504   // Not all ? identifiers are intrinsics *functions*.  This function only maps
505   // operator codes for the special functions, all others are handled elsewhere,
506   // hence the IFK::None entries in the table.
507   using IFK = IntrinsicFunctionKind;
508   static IFK Basic[36] = {
509       IFK::None,             // ?0 # Foo::Foo()
510       IFK::None,             // ?1 # Foo::~Foo()
511       IFK::New,              // ?2 # operator new
512       IFK::Delete,           // ?3 # operator delete
513       IFK::Assign,           // ?4 # operator=
514       IFK::RightShift,       // ?5 # operator>>
515       IFK::LeftShift,        // ?6 # operator<<
516       IFK::LogicalNot,       // ?7 # operator!
517       IFK::Equals,           // ?8 # operator==
518       IFK::NotEquals,        // ?9 # operator!=
519       IFK::ArraySubscript,   // ?A # operator[]
520       IFK::None,             // ?B # Foo::operator <type>()
521       IFK::Pointer,          // ?C # operator->
522       IFK::Dereference,      // ?D # operator*
523       IFK::Increment,        // ?E # operator++
524       IFK::Decrement,        // ?F # operator--
525       IFK::Minus,            // ?G # operator-
526       IFK::Plus,             // ?H # operator+
527       IFK::BitwiseAnd,       // ?I # operator&
528       IFK::MemberPointer,    // ?J # operator->*
529       IFK::Divide,           // ?K # operator/
530       IFK::Modulus,          // ?L # operator%
531       IFK::LessThan,         // ?M operator<
532       IFK::LessThanEqual,    // ?N operator<=
533       IFK::GreaterThan,      // ?O operator>
534       IFK::GreaterThanEqual, // ?P operator>=
535       IFK::Comma,            // ?Q operator,
536       IFK::Parens,           // ?R operator()
537       IFK::BitwiseNot,       // ?S operator~
538       IFK::BitwiseXor,       // ?T operator^
539       IFK::BitwiseOr,        // ?U operator|
540       IFK::LogicalAnd,       // ?V operator&&
541       IFK::LogicalOr,        // ?W operator||
542       IFK::TimesEqual,       // ?X operator*=
543       IFK::PlusEqual,        // ?Y operator+=
544       IFK::MinusEqual,       // ?Z operator-=
545   };
546   static IFK Under[36] = {
547       IFK::DivEqual,           // ?_0 operator/=
548       IFK::ModEqual,           // ?_1 operator%=
549       IFK::RshEqual,           // ?_2 operator>>=
550       IFK::LshEqual,           // ?_3 operator<<=
551       IFK::BitwiseAndEqual,    // ?_4 operator&=
552       IFK::BitwiseOrEqual,     // ?_5 operator|=
553       IFK::BitwiseXorEqual,    // ?_6 operator^=
554       IFK::None,               // ?_7 # vftable
555       IFK::None,               // ?_8 # vbtable
556       IFK::None,               // ?_9 # vcall
557       IFK::None,               // ?_A # typeof
558       IFK::None,               // ?_B # local static guard
559       IFK::None,               // ?_C # string literal
560       IFK::VbaseDtor,          // ?_D # vbase destructor
561       IFK::VecDelDtor,         // ?_E # vector deleting destructor
562       IFK::DefaultCtorClosure, // ?_F # default constructor closure
563       IFK::ScalarDelDtor,      // ?_G # scalar deleting destructor
564       IFK::VecCtorIter,        // ?_H # vector constructor iterator
565       IFK::VecDtorIter,        // ?_I # vector destructor iterator
566       IFK::VecVbaseCtorIter,   // ?_J # vector vbase constructor iterator
567       IFK::VdispMap,           // ?_K # virtual displacement map
568       IFK::EHVecCtorIter,      // ?_L # eh vector constructor iterator
569       IFK::EHVecDtorIter,      // ?_M # eh vector destructor iterator
570       IFK::EHVecVbaseCtorIter, // ?_N # eh vector vbase constructor iterator
571       IFK::CopyCtorClosure,    // ?_O # copy constructor closure
572       IFK::None,               // ?_P<name> # udt returning <name>
573       IFK::None,               // ?_Q # <unknown>
574       IFK::None,               // ?_R0 - ?_R4 # RTTI Codes
575       IFK::None,               // ?_S # local vftable
576       IFK::LocalVftableCtorClosure, // ?_T # local vftable constructor closure
577       IFK::ArrayNew,                // ?_U operator new[]
578       IFK::ArrayDelete,             // ?_V operator delete[]
579       IFK::None,                    // ?_W <unused>
580       IFK::None,                    // ?_X <unused>
581       IFK::None,                    // ?_Y <unused>
582       IFK::None,                    // ?_Z <unused>
583   };
584   static IFK DoubleUnder[36] = {
585       IFK::None,                       // ?__0 <unused>
586       IFK::None,                       // ?__1 <unused>
587       IFK::None,                       // ?__2 <unused>
588       IFK::None,                       // ?__3 <unused>
589       IFK::None,                       // ?__4 <unused>
590       IFK::None,                       // ?__5 <unused>
591       IFK::None,                       // ?__6 <unused>
592       IFK::None,                       // ?__7 <unused>
593       IFK::None,                       // ?__8 <unused>
594       IFK::None,                       // ?__9 <unused>
595       IFK::ManVectorCtorIter,          // ?__A managed vector ctor iterator
596       IFK::ManVectorDtorIter,          // ?__B managed vector dtor iterator
597       IFK::EHVectorCopyCtorIter,       // ?__C EH vector copy ctor iterator
598       IFK::EHVectorVbaseCopyCtorIter,  // ?__D EH vector vbase copy ctor iter
599       IFK::None,                       // ?__E dynamic initializer for `T'
600       IFK::None,                       // ?__F dynamic atexit destructor for `T'
601       IFK::VectorCopyCtorIter,         // ?__G vector copy constructor iter
602       IFK::VectorVbaseCopyCtorIter,    // ?__H vector vbase copy ctor iter
603       IFK::ManVectorVbaseCopyCtorIter, // ?__I managed vector vbase copy ctor
604                                        // iter
605       IFK::None,                       // ?__J local static thread guard
606       IFK::None,                       // ?__K operator ""_name
607       IFK::CoAwait,                    // ?__L co_await
608       IFK::None,                       // ?__M <unused>
609       IFK::None,                       // ?__N <unused>
610       IFK::None,                       // ?__O <unused>
611       IFK::None,                       // ?__P <unused>
612       IFK::None,                       // ?__Q <unused>
613       IFK::None,                       // ?__R <unused>
614       IFK::None,                       // ?__S <unused>
615       IFK::None,                       // ?__T <unused>
616       IFK::None,                       // ?__U <unused>
617       IFK::None,                       // ?__V <unused>
618       IFK::None,                       // ?__W <unused>
619       IFK::None,                       // ?__X <unused>
620       IFK::None,                       // ?__Y <unused>
621       IFK::None,                       // ?__Z <unused>
622   };
623 
624   int Index = (CH >= '0' && CH <= '9') ? (CH - '0') : (CH - 'A' + 10);
625   switch (Group) {
626   case FunctionIdentifierCodeGroup::Basic:
627     return Basic[Index];
628   case FunctionIdentifierCodeGroup::Under:
629     return Under[Index];
630   case FunctionIdentifierCodeGroup::DoubleUnder:
631     return DoubleUnder[Index];
632   }
633   LLVM_BUILTIN_UNREACHABLE;
634 }
635 
636 IdentifierNode *
637 Demangler::demangleFunctionIdentifierCode(StringView &MangledName,
638                                           FunctionIdentifierCodeGroup Group) {
639   switch (Group) {
640   case FunctionIdentifierCodeGroup::Basic:
641     switch (char CH = MangledName.popFront()) {
642     case '0':
643     case '1':
644       return demangleStructorIdentifier(MangledName, CH == '1');
645     case 'B':
646       return demangleConversionOperatorIdentifier(MangledName);
647     default:
648       return Arena.alloc<IntrinsicFunctionIdentifierNode>(
649           translateIntrinsicFunctionCode(CH, Group));
650     }
651     break;
652   case FunctionIdentifierCodeGroup::Under:
653     return Arena.alloc<IntrinsicFunctionIdentifierNode>(
654         translateIntrinsicFunctionCode(MangledName.popFront(), Group));
655   case FunctionIdentifierCodeGroup::DoubleUnder:
656     switch (char CH = MangledName.popFront()) {
657     case 'K':
658       return demangleLiteralOperatorIdentifier(MangledName);
659     default:
660       return Arena.alloc<IntrinsicFunctionIdentifierNode>(
661           translateIntrinsicFunctionCode(CH, Group));
662     }
663   }
664   // No Mangling Yet:      Spaceship,                    // operator<=>
665 
666   return nullptr;
667 }
668 
669 SymbolNode *Demangler::demangleEncodedSymbol(StringView &MangledName,
670                                              QualifiedNameNode *Name) {
671   // Read a variable.
672   switch (MangledName.front()) {
673   case '0':
674   case '1':
675   case '2':
676   case '3':
677   case '4': {
678     StorageClass SC = demangleVariableStorageClass(MangledName);
679     return demangleVariableEncoding(MangledName, SC);
680   }
681   case '8':
682     return nullptr;
683   }
684   FunctionSymbolNode *FSN = demangleFunctionEncoding(MangledName);
685 
686   IdentifierNode *UQN = Name->getUnqualifiedIdentifier();
687   if (UQN->kind() == NodeKind::ConversionOperatorIdentifier) {
688     ConversionOperatorIdentifierNode *COIN =
689         static_cast<ConversionOperatorIdentifierNode *>(UQN);
690     COIN->TargetType = FSN->Signature->ReturnType;
691   }
692   return FSN;
693 }
694 
695 // Parser entry point.
696 SymbolNode *Demangler::parse(StringView &MangledName) {
697   // We can't demangle MD5 names, just output them as-is.
698   // Also, MSVC-style mangled symbols must start with '?'.
699   if (MangledName.startsWith("??@")) {
700     // This is an MD5 mangled name.  We can't demangle it, just return the
701     // mangled name.
702     SymbolNode *S = Arena.alloc<SymbolNode>(NodeKind::Md5Symbol);
703     S->Name = synthesizeQualifiedName(Arena, MangledName);
704     return S;
705   }
706 
707   if (!MangledName.startsWith('?')) {
708     Error = true;
709     return nullptr;
710   }
711 
712   MangledName.consumeFront('?');
713 
714   // ?$ is a template instantiation, but all other names that start with ? are
715   // operators / special names.
716   if (SymbolNode *SI = demangleSpecialIntrinsic(MangledName))
717     return SI;
718 
719   // What follows is a main symbol name. This may include namespaces or class
720   // back references.
721   QualifiedNameNode *QN = demangleFullyQualifiedSymbolName(MangledName);
722   if (Error)
723     return nullptr;
724 
725   SymbolNode *Symbol = demangleEncodedSymbol(MangledName, QN);
726   if (Symbol) {
727     Symbol->Name = QN;
728   }
729 
730   if (Error)
731     return nullptr;
732 
733   return Symbol;
734 }
735 
736 TagTypeNode *Demangler::parseTagUniqueName(StringView &MangledName) {
737   if (!MangledName.consumeFront(".?A"))
738     return nullptr;
739   MangledName.consumeFront(".?A");
740   if (MangledName.empty())
741     return nullptr;
742 
743   return demangleClassType(MangledName);
744 }
745 
746 // <type-encoding> ::= <storage-class> <variable-type>
747 // <storage-class> ::= 0  # private static member
748 //                 ::= 1  # protected static member
749 //                 ::= 2  # public static member
750 //                 ::= 3  # global
751 //                 ::= 4  # static local
752 
753 VariableSymbolNode *Demangler::demangleVariableEncoding(StringView &MangledName,
754                                                         StorageClass SC) {
755   VariableSymbolNode *VSN = Arena.alloc<VariableSymbolNode>();
756 
757   VSN->Type = demangleType(MangledName, QualifierMangleMode::Drop);
758   VSN->SC = SC;
759 
760   // <variable-type> ::= <type> <cvr-qualifiers>
761   //                 ::= <type> <pointee-cvr-qualifiers> # pointers, references
762   switch (VSN->Type->kind()) {
763   case NodeKind::PointerType: {
764     PointerTypeNode *PTN = static_cast<PointerTypeNode *>(VSN->Type);
765 
766     Qualifiers ExtraChildQuals = Q_None;
767     PTN->Quals = Qualifiers(VSN->Type->Quals |
768                             demanglePointerExtQualifiers(MangledName));
769 
770     bool IsMember = false;
771     std::tie(ExtraChildQuals, IsMember) = demangleQualifiers(MangledName);
772 
773     if (PTN->ClassParent) {
774       QualifiedNameNode *BackRefName =
775           demangleFullyQualifiedTypeName(MangledName);
776       (void)BackRefName;
777     }
778     PTN->Pointee->Quals = Qualifiers(PTN->Pointee->Quals | ExtraChildQuals);
779 
780     break;
781   }
782   default:
783     VSN->Type->Quals = demangleQualifiers(MangledName).first;
784     break;
785   }
786 
787   return VSN;
788 }
789 
790 // Sometimes numbers are encoded in mangled symbols. For example,
791 // "int (*x)[20]" is a valid C type (x is a pointer to an array of
792 // length 20), so we need some way to embed numbers as part of symbols.
793 // This function parses it.
794 //
795 // <number>               ::= [?] <non-negative integer>
796 //
797 // <non-negative integer> ::= <decimal digit> # when 1 <= Number <= 10
798 //                        ::= <hex digit>+ @  # when Numbrer == 0 or >= 10
799 //
800 // <hex-digit>            ::= [A-P]           # A = 0, B = 1, ...
801 std::pair<uint64_t, bool> Demangler::demangleNumber(StringView &MangledName) {
802   bool IsNegative = MangledName.consumeFront('?');
803 
804   if (startsWithDigit(MangledName)) {
805     uint64_t Ret = MangledName[0] - '0' + 1;
806     MangledName = MangledName.dropFront(1);
807     return {Ret, IsNegative};
808   }
809 
810   uint64_t Ret = 0;
811   for (size_t i = 0; i < MangledName.size(); ++i) {
812     char C = MangledName[i];
813     if (C == '@') {
814       MangledName = MangledName.dropFront(i + 1);
815       return {Ret, IsNegative};
816     }
817     if ('A' <= C && C <= 'P') {
818       Ret = (Ret << 4) + (C - 'A');
819       continue;
820     }
821     break;
822   }
823 
824   Error = true;
825   return {0ULL, false};
826 }
827 
828 uint64_t Demangler::demangleUnsigned(StringView &MangledName) {
829   bool IsNegative = false;
830   uint64_t Number = 0;
831   std::tie(Number, IsNegative) = demangleNumber(MangledName);
832   if (IsNegative)
833     Error = true;
834   return Number;
835 }
836 
837 int64_t Demangler::demangleSigned(StringView &MangledName) {
838   bool IsNegative = false;
839   uint64_t Number = 0;
840   std::tie(Number, IsNegative) = demangleNumber(MangledName);
841   if (Number > INT64_MAX)
842     Error = true;
843   int64_t I = static_cast<int64_t>(Number);
844   return IsNegative ? -I : I;
845 }
846 
847 // First 10 strings can be referenced by special BackReferences ?0, ?1, ..., ?9.
848 // Memorize it.
849 void Demangler::memorizeString(StringView S) {
850   if (Backrefs.NamesCount >= BackrefContext::Max)
851     return;
852   for (size_t i = 0; i < Backrefs.NamesCount; ++i)
853     if (S == Backrefs.Names[i]->Name)
854       return;
855   NamedIdentifierNode *N = Arena.alloc<NamedIdentifierNode>();
856   N->Name = S;
857   Backrefs.Names[Backrefs.NamesCount++] = N;
858 }
859 
860 NamedIdentifierNode *Demangler::demangleBackRefName(StringView &MangledName) {
861   assert(startsWithDigit(MangledName));
862 
863   size_t I = MangledName[0] - '0';
864   if (I >= Backrefs.NamesCount) {
865     Error = true;
866     return nullptr;
867   }
868 
869   MangledName = MangledName.dropFront();
870   return Backrefs.Names[I];
871 }
872 
873 void Demangler::memorizeIdentifier(IdentifierNode *Identifier) {
874   // Render this class template name into a string buffer so that we can
875   // memorize it for the purpose of back-referencing.
876   OutputStream OS;
877   if (!initializeOutputStream(nullptr, nullptr, OS, 1024))
878     // FIXME: Propagate out-of-memory as an error?
879     std::terminate();
880   Identifier->output(OS, OF_Default);
881   OS << '\0';
882   char *Name = OS.getBuffer();
883 
884   StringView Owned = copyString(Name);
885   memorizeString(Owned);
886   std::free(Name);
887 }
888 
889 IdentifierNode *
890 Demangler::demangleTemplateInstantiationName(StringView &MangledName,
891                                              NameBackrefBehavior NBB) {
892   assert(MangledName.startsWith("?$"));
893   MangledName.consumeFront("?$");
894 
895   BackrefContext OuterContext;
896   std::swap(OuterContext, Backrefs);
897 
898   IdentifierNode *Identifier =
899       demangleUnqualifiedSymbolName(MangledName, NBB_Simple);
900   if (!Error)
901     Identifier->TemplateParams = demangleTemplateParameterList(MangledName);
902 
903   std::swap(OuterContext, Backrefs);
904   if (Error)
905     return nullptr;
906 
907   if (NBB & NBB_Template)
908     memorizeIdentifier(Identifier);
909 
910   return Identifier;
911 }
912 
913 NamedIdentifierNode *Demangler::demangleSimpleName(StringView &MangledName,
914                                                    bool Memorize) {
915   StringView S = demangleSimpleString(MangledName, Memorize);
916   if (Error)
917     return nullptr;
918 
919   NamedIdentifierNode *Name = Arena.alloc<NamedIdentifierNode>();
920   Name->Name = S;
921   return Name;
922 }
923 
924 static bool isRebasedHexDigit(char C) { return (C >= 'A' && C <= 'P'); }
925 
926 static uint8_t rebasedHexDigitToNumber(char C) {
927   assert(isRebasedHexDigit(C));
928   return (C <= 'J') ? (C - 'A') : (10 + C - 'K');
929 }
930 
931 uint8_t Demangler::demangleCharLiteral(StringView &MangledName) {
932   if (!MangledName.startsWith('?'))
933     return MangledName.popFront();
934 
935   MangledName = MangledName.dropFront();
936   if (MangledName.empty())
937     goto CharLiteralError;
938 
939   if (MangledName.consumeFront('$')) {
940     // Two hex digits
941     if (MangledName.size() < 2)
942       goto CharLiteralError;
943     StringView Nibbles = MangledName.substr(0, 2);
944     if (!isRebasedHexDigit(Nibbles[0]) || !isRebasedHexDigit(Nibbles[1]))
945       goto CharLiteralError;
946     // Don't append the null terminator.
947     uint8_t C1 = rebasedHexDigitToNumber(Nibbles[0]);
948     uint8_t C2 = rebasedHexDigitToNumber(Nibbles[1]);
949     MangledName = MangledName.dropFront(2);
950     return (C1 << 4) | C2;
951   }
952 
953   if (startsWithDigit(MangledName)) {
954     const char *Lookup = ",/\\:. \n\t'-";
955     char C = Lookup[MangledName[0] - '0'];
956     MangledName = MangledName.dropFront();
957     return C;
958   }
959 
960   if (MangledName[0] >= 'a' && MangledName[0] <= 'z') {
961     char Lookup[26] = {'\xE1', '\xE2', '\xE3', '\xE4', '\xE5', '\xE6', '\xE7',
962                        '\xE8', '\xE9', '\xEA', '\xEB', '\xEC', '\xED', '\xEE',
963                        '\xEF', '\xF0', '\xF1', '\xF2', '\xF3', '\xF4', '\xF5',
964                        '\xF6', '\xF7', '\xF8', '\xF9', '\xFA'};
965     char C = Lookup[MangledName[0] - 'a'];
966     MangledName = MangledName.dropFront();
967     return C;
968   }
969 
970   if (MangledName[0] >= 'A' && MangledName[0] <= 'Z') {
971     char Lookup[26] = {'\xC1', '\xC2', '\xC3', '\xC4', '\xC5', '\xC6', '\xC7',
972                        '\xC8', '\xC9', '\xCA', '\xCB', '\xCC', '\xCD', '\xCE',
973                        '\xCF', '\xD0', '\xD1', '\xD2', '\xD3', '\xD4', '\xD5',
974                        '\xD6', '\xD7', '\xD8', '\xD9', '\xDA'};
975     char C = Lookup[MangledName[0] - 'A'];
976     MangledName = MangledName.dropFront();
977     return C;
978   }
979 
980 CharLiteralError:
981   Error = true;
982   return '\0';
983 }
984 
985 wchar_t Demangler::demangleWcharLiteral(StringView &MangledName) {
986   uint8_t C1, C2;
987 
988   C1 = demangleCharLiteral(MangledName);
989   if (Error)
990     goto WCharLiteralError;
991   C2 = demangleCharLiteral(MangledName);
992   if (Error)
993     goto WCharLiteralError;
994 
995   return ((wchar_t)C1 << 8) | (wchar_t)C2;
996 
997 WCharLiteralError:
998   Error = true;
999   return L'\0';
1000 }
1001 
1002 static void writeHexDigit(char *Buffer, uint8_t Digit) {
1003   assert(Digit <= 15);
1004   *Buffer = (Digit < 10) ? ('0' + Digit) : ('A' + Digit - 10);
1005 }
1006 
1007 static void outputHex(OutputStream &OS, unsigned C) {
1008   if (C == 0) {
1009     OS << "\\x00";
1010     return;
1011   }
1012   // It's easier to do the math if we can work from right to left, but we need
1013   // to print the numbers from left to right.  So render this into a temporary
1014   // buffer first, then output the temporary buffer.  Each byte is of the form
1015   // \xAB, which means that each byte needs 4 characters.  Since there are at
1016   // most 4 bytes, we need a 4*4+1 = 17 character temporary buffer.
1017   char TempBuffer[17];
1018 
1019   ::memset(TempBuffer, 0, sizeof(TempBuffer));
1020   constexpr int MaxPos = 15;
1021 
1022   int Pos = MaxPos - 1;
1023   while (C != 0) {
1024     for (int I = 0; I < 2; ++I) {
1025       writeHexDigit(&TempBuffer[Pos--], C % 16);
1026       C /= 16;
1027     }
1028     TempBuffer[Pos--] = 'x';
1029     TempBuffer[Pos--] = '\\';
1030     assert(Pos >= 0);
1031   }
1032   OS << StringView(&TempBuffer[Pos + 1]);
1033 }
1034 
1035 static void outputEscapedChar(OutputStream &OS, unsigned C) {
1036   switch (C) {
1037   case '\'': // single quote
1038     OS << "\\\'";
1039     return;
1040   case '\"': // double quote
1041     OS << "\\\"";
1042     return;
1043   case '\\': // backslash
1044     OS << "\\\\";
1045     return;
1046   case '\a': // bell
1047     OS << "\\a";
1048     return;
1049   case '\b': // backspace
1050     OS << "\\b";
1051     return;
1052   case '\f': // form feed
1053     OS << "\\f";
1054     return;
1055   case '\n': // new line
1056     OS << "\\n";
1057     return;
1058   case '\r': // carriage return
1059     OS << "\\r";
1060     return;
1061   case '\t': // tab
1062     OS << "\\t";
1063     return;
1064   case '\v': // vertical tab
1065     OS << "\\v";
1066     return;
1067   default:
1068     break;
1069   }
1070 
1071   if (C > 0x1F && C < 0x7F) {
1072     // Standard ascii char.
1073     OS << (char)C;
1074     return;
1075   }
1076 
1077   outputHex(OS, C);
1078 }
1079 
1080 static unsigned countTrailingNullBytes(const uint8_t *StringBytes, int Length) {
1081   const uint8_t *End = StringBytes + Length - 1;
1082   unsigned Count = 0;
1083   while (Length > 0 && *End == 0) {
1084     --Length;
1085     --End;
1086     ++Count;
1087   }
1088   return Count;
1089 }
1090 
1091 static unsigned countEmbeddedNulls(const uint8_t *StringBytes,
1092                                    unsigned Length) {
1093   unsigned Result = 0;
1094   for (unsigned I = 0; I < Length; ++I) {
1095     if (*StringBytes++ == 0)
1096       ++Result;
1097   }
1098   return Result;
1099 }
1100 
1101 static unsigned guessCharByteSize(const uint8_t *StringBytes, unsigned NumChars,
1102                                   unsigned NumBytes) {
1103   assert(NumBytes > 0);
1104 
1105   // If the number of bytes is odd, this is guaranteed to be a char string.
1106   if (NumBytes % 2 == 1)
1107     return 1;
1108 
1109   // All strings can encode at most 32 bytes of data.  If it's less than that,
1110   // then we encoded the entire string.  In this case we check for a 1-byte,
1111   // 2-byte, or 4-byte null terminator.
1112   if (NumBytes < 32) {
1113     unsigned TrailingNulls = countTrailingNullBytes(StringBytes, NumChars);
1114     if (TrailingNulls >= 4)
1115       return 4;
1116     if (TrailingNulls >= 2)
1117       return 2;
1118     return 1;
1119   }
1120 
1121   // The whole string was not able to be encoded.  Try to look at embedded null
1122   // terminators to guess.  The heuristic is that we count all embedded null
1123   // terminators.  If more than 2/3 are null, it's a char32.  If more than 1/3
1124   // are null, it's a char16.  Otherwise it's a char8.  This obviously isn't
1125   // perfect and is biased towards languages that have ascii alphabets, but this
1126   // was always going to be best effort since the encoding is lossy.
1127   unsigned Nulls = countEmbeddedNulls(StringBytes, NumChars);
1128   if (Nulls >= 2 * NumChars / 3)
1129     return 4;
1130   if (Nulls >= NumChars / 3)
1131     return 2;
1132   return 1;
1133 }
1134 
1135 static unsigned decodeMultiByteChar(const uint8_t *StringBytes,
1136                                     unsigned CharIndex, unsigned CharBytes) {
1137   assert(CharBytes == 1 || CharBytes == 2 || CharBytes == 4);
1138   unsigned Offset = CharIndex * CharBytes;
1139   unsigned Result = 0;
1140   StringBytes = StringBytes + Offset;
1141   for (unsigned I = 0; I < CharBytes; ++I) {
1142     unsigned C = static_cast<unsigned>(StringBytes[I]);
1143     Result |= C << (8 * I);
1144   }
1145   return Result;
1146 }
1147 
1148 FunctionSymbolNode *Demangler::demangleVcallThunkNode(StringView &MangledName) {
1149   FunctionSymbolNode *FSN = Arena.alloc<FunctionSymbolNode>();
1150   VcallThunkIdentifierNode *VTIN = Arena.alloc<VcallThunkIdentifierNode>();
1151   FSN->Signature = Arena.alloc<ThunkSignatureNode>();
1152   FSN->Signature->FunctionClass = FC_NoParameterList;
1153 
1154   FSN->Name = demangleNameScopeChain(MangledName, VTIN);
1155   if (!Error)
1156     Error = !MangledName.consumeFront("$B");
1157   if (!Error)
1158     VTIN->OffsetInVTable = demangleUnsigned(MangledName);
1159   if (!Error)
1160     Error = !MangledName.consumeFront('A');
1161   if (!Error)
1162     FSN->Signature->CallConvention = demangleCallingConvention(MangledName);
1163   return (Error) ? nullptr : FSN;
1164 }
1165 
1166 EncodedStringLiteralNode *
1167 Demangler::demangleStringLiteral(StringView &MangledName) {
1168   // This function uses goto, so declare all variables up front.
1169   OutputStream OS;
1170   StringView CRC;
1171   uint64_t StringByteSize;
1172   bool IsWcharT = false;
1173   bool IsNegative = false;
1174   size_t CrcEndPos = 0;
1175   char *ResultBuffer = nullptr;
1176 
1177   EncodedStringLiteralNode *Result = Arena.alloc<EncodedStringLiteralNode>();
1178 
1179   // Prefix indicating the beginning of a string literal
1180   if (!MangledName.consumeFront("@_"))
1181     goto StringLiteralError;
1182   if (MangledName.empty())
1183     goto StringLiteralError;
1184 
1185   // Char Type (regular or wchar_t)
1186   switch (MangledName.popFront()) {
1187   case '1':
1188     IsWcharT = true;
1189     LLVM_FALLTHROUGH;
1190   case '0':
1191     break;
1192   default:
1193     goto StringLiteralError;
1194   }
1195 
1196   // Encoded Length
1197   std::tie(StringByteSize, IsNegative) = demangleNumber(MangledName);
1198   if (Error || IsNegative)
1199     goto StringLiteralError;
1200 
1201   // CRC 32 (always 8 characters plus a terminator)
1202   CrcEndPos = MangledName.find('@');
1203   if (CrcEndPos == StringView::npos)
1204     goto StringLiteralError;
1205   CRC = MangledName.substr(0, CrcEndPos);
1206   MangledName = MangledName.dropFront(CrcEndPos + 1);
1207   if (MangledName.empty())
1208     goto StringLiteralError;
1209 
1210   if (!initializeOutputStream(nullptr, nullptr, OS, 1024))
1211     // FIXME: Propagate out-of-memory as an error?
1212     std::terminate();
1213   if (IsWcharT) {
1214     Result->Char = CharKind::Wchar;
1215     if (StringByteSize > 64)
1216       Result->IsTruncated = true;
1217 
1218     while (!MangledName.consumeFront('@')) {
1219       assert(StringByteSize >= 2);
1220       wchar_t W = demangleWcharLiteral(MangledName);
1221       if (StringByteSize != 2 || Result->IsTruncated)
1222         outputEscapedChar(OS, W);
1223       StringByteSize -= 2;
1224       if (Error)
1225         goto StringLiteralError;
1226     }
1227   } else {
1228     // The max byte length is actually 32, but some compilers mangled strings
1229     // incorrectly, so we have to assume it can go higher.
1230     constexpr unsigned MaxStringByteLength = 32 * 4;
1231     uint8_t StringBytes[MaxStringByteLength];
1232 
1233     unsigned BytesDecoded = 0;
1234     while (!MangledName.consumeFront('@')) {
1235       assert(StringByteSize >= 1);
1236       StringBytes[BytesDecoded++] = demangleCharLiteral(MangledName);
1237     }
1238 
1239     if (StringByteSize > BytesDecoded)
1240       Result->IsTruncated = true;
1241 
1242     unsigned CharBytes =
1243         guessCharByteSize(StringBytes, BytesDecoded, StringByteSize);
1244     assert(StringByteSize % CharBytes == 0);
1245     switch (CharBytes) {
1246     case 1:
1247       Result->Char = CharKind::Char;
1248       break;
1249     case 2:
1250       Result->Char = CharKind::Char16;
1251       break;
1252     case 4:
1253       Result->Char = CharKind::Char32;
1254       break;
1255     default:
1256       LLVM_BUILTIN_UNREACHABLE;
1257     }
1258     const unsigned NumChars = BytesDecoded / CharBytes;
1259     for (unsigned CharIndex = 0; CharIndex < NumChars; ++CharIndex) {
1260       unsigned NextChar =
1261           decodeMultiByteChar(StringBytes, CharIndex, CharBytes);
1262       if (CharIndex + 1 < NumChars || Result->IsTruncated)
1263         outputEscapedChar(OS, NextChar);
1264     }
1265   }
1266 
1267   OS << '\0';
1268   ResultBuffer = OS.getBuffer();
1269   Result->DecodedString = copyString(ResultBuffer);
1270   std::free(ResultBuffer);
1271   return Result;
1272 
1273 StringLiteralError:
1274   Error = true;
1275   return nullptr;
1276 }
1277 
1278 StringView Demangler::demangleSimpleString(StringView &MangledName,
1279                                            bool Memorize) {
1280   StringView S;
1281   for (size_t i = 0; i < MangledName.size(); ++i) {
1282     if (MangledName[i] != '@')
1283       continue;
1284     S = MangledName.substr(0, i);
1285     MangledName = MangledName.dropFront(i + 1);
1286 
1287     if (Memorize)
1288       memorizeString(S);
1289     return S;
1290   }
1291 
1292   Error = true;
1293   return {};
1294 }
1295 
1296 NamedIdentifierNode *
1297 Demangler::demangleAnonymousNamespaceName(StringView &MangledName) {
1298   assert(MangledName.startsWith("?A"));
1299   MangledName.consumeFront("?A");
1300 
1301   NamedIdentifierNode *Node = Arena.alloc<NamedIdentifierNode>();
1302   Node->Name = "`anonymous namespace'";
1303   size_t EndPos = MangledName.find('@');
1304   if (EndPos == StringView::npos) {
1305     Error = true;
1306     return nullptr;
1307   }
1308   StringView NamespaceKey = MangledName.substr(0, EndPos);
1309   memorizeString(NamespaceKey);
1310   MangledName = MangledName.substr(EndPos + 1);
1311   return Node;
1312 }
1313 
1314 NamedIdentifierNode *
1315 Demangler::demangleLocallyScopedNamePiece(StringView &MangledName) {
1316   assert(startsWithLocalScopePattern(MangledName));
1317 
1318   NamedIdentifierNode *Identifier = Arena.alloc<NamedIdentifierNode>();
1319   MangledName.consumeFront('?');
1320   auto Number = demangleNumber(MangledName);
1321   assert(!Number.second);
1322 
1323   // One ? to terminate the number
1324   MangledName.consumeFront('?');
1325 
1326   assert(!Error);
1327   Node *Scope = parse(MangledName);
1328   if (Error)
1329     return nullptr;
1330 
1331   // Render the parent symbol's name into a buffer.
1332   OutputStream OS;
1333   if (!initializeOutputStream(nullptr, nullptr, OS, 1024))
1334     // FIXME: Propagate out-of-memory as an error?
1335     std::terminate();
1336   OS << '`';
1337   Scope->output(OS, OF_Default);
1338   OS << '\'';
1339   OS << "::`" << Number.first << "'";
1340   OS << '\0';
1341   char *Result = OS.getBuffer();
1342   Identifier->Name = copyString(Result);
1343   std::free(Result);
1344   return Identifier;
1345 }
1346 
1347 // Parses a type name in the form of A@B@C@@ which represents C::B::A.
1348 QualifiedNameNode *
1349 Demangler::demangleFullyQualifiedTypeName(StringView &MangledName) {
1350   IdentifierNode *Identifier = demangleUnqualifiedTypeName(MangledName, true);
1351   if (Error)
1352     return nullptr;
1353   assert(Identifier);
1354 
1355   QualifiedNameNode *QN = demangleNameScopeChain(MangledName, Identifier);
1356   if (Error)
1357     return nullptr;
1358   assert(QN);
1359   return QN;
1360 }
1361 
1362 // Parses a symbol name in the form of A@B@C@@ which represents C::B::A.
1363 // Symbol names have slightly different rules regarding what can appear
1364 // so we separate out the implementations for flexibility.
1365 QualifiedNameNode *
1366 Demangler::demangleFullyQualifiedSymbolName(StringView &MangledName) {
1367   // This is the final component of a symbol name (i.e. the leftmost component
1368   // of a mangled name.  Since the only possible template instantiation that
1369   // can appear in this context is a function template, and since those are
1370   // not saved for the purposes of name backreferences, only backref simple
1371   // names.
1372   IdentifierNode *Identifier =
1373       demangleUnqualifiedSymbolName(MangledName, NBB_Simple);
1374   if (Error)
1375     return nullptr;
1376 
1377   QualifiedNameNode *QN = demangleNameScopeChain(MangledName, Identifier);
1378   if (Error)
1379     return nullptr;
1380 
1381   if (Identifier->kind() == NodeKind::StructorIdentifier) {
1382     StructorIdentifierNode *SIN =
1383         static_cast<StructorIdentifierNode *>(Identifier);
1384     assert(QN->Components->Count >= 2);
1385     Node *ClassNode = QN->Components->Nodes[QN->Components->Count - 2];
1386     SIN->Class = static_cast<IdentifierNode *>(ClassNode);
1387   }
1388   assert(QN);
1389   return QN;
1390 }
1391 
1392 IdentifierNode *Demangler::demangleUnqualifiedTypeName(StringView &MangledName,
1393                                                        bool Memorize) {
1394   // An inner-most name can be a back-reference, because a fully-qualified name
1395   // (e.g. Scope + Inner) can contain other fully qualified names inside of
1396   // them (for example template parameters), and these nested parameters can
1397   // refer to previously mangled types.
1398   if (startsWithDigit(MangledName))
1399     return demangleBackRefName(MangledName);
1400 
1401   if (MangledName.startsWith("?$"))
1402     return demangleTemplateInstantiationName(MangledName, NBB_Template);
1403 
1404   return demangleSimpleName(MangledName, Memorize);
1405 }
1406 
1407 IdentifierNode *
1408 Demangler::demangleUnqualifiedSymbolName(StringView &MangledName,
1409                                          NameBackrefBehavior NBB) {
1410   if (startsWithDigit(MangledName))
1411     return demangleBackRefName(MangledName);
1412   if (MangledName.startsWith("?$"))
1413     return demangleTemplateInstantiationName(MangledName, NBB);
1414   if (MangledName.startsWith('?'))
1415     return demangleFunctionIdentifierCode(MangledName);
1416   return demangleSimpleName(MangledName, (NBB & NBB_Simple) != 0);
1417 }
1418 
1419 IdentifierNode *Demangler::demangleNameScopePiece(StringView &MangledName) {
1420   if (startsWithDigit(MangledName))
1421     return demangleBackRefName(MangledName);
1422 
1423   if (MangledName.startsWith("?$"))
1424     return demangleTemplateInstantiationName(MangledName, NBB_Template);
1425 
1426   if (MangledName.startsWith("?A"))
1427     return demangleAnonymousNamespaceName(MangledName);
1428 
1429   if (startsWithLocalScopePattern(MangledName))
1430     return demangleLocallyScopedNamePiece(MangledName);
1431 
1432   return demangleSimpleName(MangledName, true);
1433 }
1434 
1435 static NodeArrayNode *nodeListToNodeArray(ArenaAllocator &Arena, NodeList *Head,
1436                                           size_t Count) {
1437   NodeArrayNode *N = Arena.alloc<NodeArrayNode>();
1438   N->Count = Count;
1439   N->Nodes = Arena.allocArray<Node *>(Count);
1440   for (size_t I = 0; I < Count; ++I) {
1441     N->Nodes[I] = Head->N;
1442     Head = Head->Next;
1443   }
1444   return N;
1445 }
1446 
1447 QualifiedNameNode *
1448 Demangler::demangleNameScopeChain(StringView &MangledName,
1449                                   IdentifierNode *UnqualifiedName) {
1450   NodeList *Head = Arena.alloc<NodeList>();
1451 
1452   Head->N = UnqualifiedName;
1453 
1454   size_t Count = 1;
1455   while (!MangledName.consumeFront("@")) {
1456     ++Count;
1457     NodeList *NewHead = Arena.alloc<NodeList>();
1458     NewHead->Next = Head;
1459     Head = NewHead;
1460 
1461     if (MangledName.empty()) {
1462       Error = true;
1463       return nullptr;
1464     }
1465 
1466     assert(!Error);
1467     IdentifierNode *Elem = demangleNameScopePiece(MangledName);
1468     if (Error)
1469       return nullptr;
1470 
1471     Head->N = Elem;
1472   }
1473 
1474   QualifiedNameNode *QN = Arena.alloc<QualifiedNameNode>();
1475   QN->Components = nodeListToNodeArray(Arena, Head, Count);
1476   return QN;
1477 }
1478 
1479 FuncClass Demangler::demangleFunctionClass(StringView &MangledName) {
1480   switch (MangledName.popFront()) {
1481   case '9':
1482     return FuncClass(FC_ExternC | FC_NoParameterList);
1483   case 'A':
1484     return FC_Private;
1485   case 'B':
1486     return FuncClass(FC_Private | FC_Far);
1487   case 'C':
1488     return FuncClass(FC_Private | FC_Static);
1489   case 'D':
1490     return FuncClass(FC_Private | FC_Static);
1491   case 'E':
1492     return FuncClass(FC_Private | FC_Virtual);
1493   case 'F':
1494     return FuncClass(FC_Private | FC_Virtual);
1495   case 'G':
1496     return FuncClass(FC_Private | FC_StaticThisAdjust);
1497   case 'H':
1498     return FuncClass(FC_Private | FC_StaticThisAdjust | FC_Far);
1499   case 'I':
1500     return FuncClass(FC_Protected);
1501   case 'J':
1502     return FuncClass(FC_Protected | FC_Far);
1503   case 'K':
1504     return FuncClass(FC_Protected | FC_Static);
1505   case 'L':
1506     return FuncClass(FC_Protected | FC_Static | FC_Far);
1507   case 'M':
1508     return FuncClass(FC_Protected | FC_Virtual);
1509   case 'N':
1510     return FuncClass(FC_Protected | FC_Virtual | FC_Far);
1511   case 'O':
1512     return FuncClass(FC_Protected | FC_Virtual | FC_StaticThisAdjust);
1513   case 'P':
1514     return FuncClass(FC_Protected | FC_Virtual | FC_StaticThisAdjust | FC_Far);
1515   case 'Q':
1516     return FuncClass(FC_Public);
1517   case 'R':
1518     return FuncClass(FC_Public | FC_Far);
1519   case 'S':
1520     return FuncClass(FC_Public | FC_Static);
1521   case 'T':
1522     return FuncClass(FC_Public | FC_Static | FC_Far);
1523   case 'U':
1524     return FuncClass(FC_Public | FC_Virtual);
1525   case 'V':
1526     return FuncClass(FC_Public | FC_Virtual | FC_Far);
1527   case 'W':
1528     return FuncClass(FC_Public | FC_Virtual | FC_StaticThisAdjust);
1529   case 'X':
1530     return FuncClass(FC_Public | FC_Virtual | FC_StaticThisAdjust | FC_Far);
1531   case 'Y':
1532     return FuncClass(FC_Global);
1533   case 'Z':
1534     return FuncClass(FC_Global | FC_Far);
1535   case '$': {
1536     FuncClass VFlag = FC_VirtualThisAdjust;
1537     if (MangledName.consumeFront('R'))
1538       VFlag = FuncClass(VFlag | FC_VirtualThisAdjustEx);
1539 
1540     switch (MangledName.popFront()) {
1541     case '0':
1542       return FuncClass(FC_Private | FC_Virtual | VFlag);
1543     case '1':
1544       return FuncClass(FC_Private | FC_Virtual | VFlag | FC_Far);
1545     case '2':
1546       return FuncClass(FC_Protected | FC_Virtual | VFlag);
1547     case '3':
1548       return FuncClass(FC_Protected | FC_Virtual | VFlag | FC_Far);
1549     case '4':
1550       return FuncClass(FC_Public | FC_Virtual | VFlag);
1551     case '5':
1552       return FuncClass(FC_Public | FC_Virtual | VFlag | FC_Far);
1553     }
1554   }
1555   }
1556 
1557   Error = true;
1558   return FC_Public;
1559 }
1560 
1561 CallingConv Demangler::demangleCallingConvention(StringView &MangledName) {
1562   switch (MangledName.popFront()) {
1563   case 'A':
1564   case 'B':
1565     return CallingConv::Cdecl;
1566   case 'C':
1567   case 'D':
1568     return CallingConv::Pascal;
1569   case 'E':
1570   case 'F':
1571     return CallingConv::Thiscall;
1572   case 'G':
1573   case 'H':
1574     return CallingConv::Stdcall;
1575   case 'I':
1576   case 'J':
1577     return CallingConv::Fastcall;
1578   case 'M':
1579   case 'N':
1580     return CallingConv::Clrcall;
1581   case 'O':
1582   case 'P':
1583     return CallingConv::Eabi;
1584   case 'Q':
1585     return CallingConv::Vectorcall;
1586   }
1587 
1588   return CallingConv::None;
1589 }
1590 
1591 StorageClass Demangler::demangleVariableStorageClass(StringView &MangledName) {
1592   assert(std::isdigit(MangledName.front()));
1593 
1594   switch (MangledName.popFront()) {
1595   case '0':
1596     return StorageClass::PrivateStatic;
1597   case '1':
1598     return StorageClass::ProtectedStatic;
1599   case '2':
1600     return StorageClass::PublicStatic;
1601   case '3':
1602     return StorageClass::Global;
1603   case '4':
1604     return StorageClass::FunctionLocalStatic;
1605   }
1606   Error = true;
1607   return StorageClass::None;
1608 }
1609 
1610 std::pair<Qualifiers, bool>
1611 Demangler::demangleQualifiers(StringView &MangledName) {
1612 
1613   switch (MangledName.popFront()) {
1614   // Member qualifiers
1615   case 'Q':
1616     return std::make_pair(Q_None, true);
1617   case 'R':
1618     return std::make_pair(Q_Const, true);
1619   case 'S':
1620     return std::make_pair(Q_Volatile, true);
1621   case 'T':
1622     return std::make_pair(Qualifiers(Q_Const | Q_Volatile), true);
1623   // Non-Member qualifiers
1624   case 'A':
1625     return std::make_pair(Q_None, false);
1626   case 'B':
1627     return std::make_pair(Q_Const, false);
1628   case 'C':
1629     return std::make_pair(Q_Volatile, false);
1630   case 'D':
1631     return std::make_pair(Qualifiers(Q_Const | Q_Volatile), false);
1632   }
1633   Error = true;
1634   return std::make_pair(Q_None, false);
1635 }
1636 
1637 // <variable-type> ::= <type> <cvr-qualifiers>
1638 //                 ::= <type> <pointee-cvr-qualifiers> # pointers, references
1639 TypeNode *Demangler::demangleType(StringView &MangledName,
1640                                   QualifierMangleMode QMM) {
1641   Qualifiers Quals = Q_None;
1642   bool IsMember = false;
1643   if (QMM == QualifierMangleMode::Mangle) {
1644     std::tie(Quals, IsMember) = demangleQualifiers(MangledName);
1645   } else if (QMM == QualifierMangleMode::Result) {
1646     if (MangledName.consumeFront('?'))
1647       std::tie(Quals, IsMember) = demangleQualifiers(MangledName);
1648   }
1649 
1650   TypeNode *Ty = nullptr;
1651   if (isTagType(MangledName))
1652     Ty = demangleClassType(MangledName);
1653   else if (isPointerType(MangledName)) {
1654     if (isMemberPointer(MangledName))
1655       Ty = demangleMemberPointerType(MangledName);
1656     else
1657       Ty = demanglePointerType(MangledName);
1658   } else if (isArrayType(MangledName))
1659     Ty = demangleArrayType(MangledName);
1660   else if (isFunctionType(MangledName)) {
1661     if (MangledName.consumeFront("$$A8@@"))
1662       Ty = demangleFunctionType(MangledName, true);
1663     else {
1664       assert(MangledName.startsWith("$$A6"));
1665       MangledName.consumeFront("$$A6");
1666       Ty = demangleFunctionType(MangledName, false);
1667     }
1668   } else if (isCustomType(MangledName)) {
1669     Ty = demangleCustomType(MangledName);
1670   } else {
1671     Ty = demanglePrimitiveType(MangledName);
1672     if (!Ty || Error)
1673       return Ty;
1674   }
1675 
1676   Ty->Quals = Qualifiers(Ty->Quals | Quals);
1677   return Ty;
1678 }
1679 
1680 void Demangler::demangleThrowSpecification(StringView &MangledName) {
1681   if (MangledName.consumeFront('Z'))
1682     return;
1683 
1684   Error = true;
1685 }
1686 
1687 FunctionSignatureNode *Demangler::demangleFunctionType(StringView &MangledName,
1688                                                        bool HasThisQuals) {
1689   FunctionSignatureNode *FTy = Arena.alloc<FunctionSignatureNode>();
1690 
1691   if (HasThisQuals) {
1692     FTy->Quals = demanglePointerExtQualifiers(MangledName);
1693     FTy->RefQualifier = demangleFunctionRefQualifier(MangledName);
1694     FTy->Quals = Qualifiers(FTy->Quals | demangleQualifiers(MangledName).first);
1695   }
1696 
1697   // Fields that appear on both member and non-member functions.
1698   FTy->CallConvention = demangleCallingConvention(MangledName);
1699 
1700   // <return-type> ::= <type>
1701   //               ::= @ # structors (they have no declared return type)
1702   bool IsStructor = MangledName.consumeFront('@');
1703   if (!IsStructor)
1704     FTy->ReturnType = demangleType(MangledName, QualifierMangleMode::Result);
1705 
1706   FTy->Params = demangleFunctionParameterList(MangledName);
1707 
1708   demangleThrowSpecification(MangledName);
1709 
1710   return FTy;
1711 }
1712 
1713 FunctionSymbolNode *
1714 Demangler::demangleFunctionEncoding(StringView &MangledName) {
1715   FuncClass ExtraFlags = FC_None;
1716   if (MangledName.consumeFront("$$J0"))
1717     ExtraFlags = FC_ExternC;
1718 
1719   FuncClass FC = demangleFunctionClass(MangledName);
1720   FC = FuncClass(ExtraFlags | FC);
1721 
1722   FunctionSignatureNode *FSN = nullptr;
1723   ThunkSignatureNode *TTN = nullptr;
1724   if (FC & FC_StaticThisAdjust) {
1725     TTN = Arena.alloc<ThunkSignatureNode>();
1726     TTN->ThisAdjust.StaticOffset = demangleSigned(MangledName);
1727   } else if (FC & FC_VirtualThisAdjust) {
1728     TTN = Arena.alloc<ThunkSignatureNode>();
1729     if (FC & FC_VirtualThisAdjustEx) {
1730       TTN->ThisAdjust.VBPtrOffset = demangleSigned(MangledName);
1731       TTN->ThisAdjust.VBOffsetOffset = demangleSigned(MangledName);
1732     }
1733     TTN->ThisAdjust.VtordispOffset = demangleSigned(MangledName);
1734     TTN->ThisAdjust.StaticOffset = demangleSigned(MangledName);
1735   }
1736 
1737   if (FC & FC_NoParameterList) {
1738     // This is an extern "C" function whose full signature hasn't been mangled.
1739     // This happens when we need to mangle a local symbol inside of an extern
1740     // "C" function.
1741     FSN = Arena.alloc<FunctionSignatureNode>();
1742   } else {
1743     bool HasThisQuals = !(FC & (FC_Global | FC_Static));
1744     FSN = demangleFunctionType(MangledName, HasThisQuals);
1745   }
1746   if (TTN) {
1747     *static_cast<FunctionSignatureNode *>(TTN) = *FSN;
1748     FSN = TTN;
1749   }
1750   FSN->FunctionClass = FC;
1751 
1752   FunctionSymbolNode *Symbol = Arena.alloc<FunctionSymbolNode>();
1753   Symbol->Signature = FSN;
1754   return Symbol;
1755 }
1756 
1757 CustomTypeNode *Demangler::demangleCustomType(StringView &MangledName) {
1758   assert(MangledName.startsWith('?'));
1759   MangledName.popFront();
1760 
1761   CustomTypeNode *CTN = Arena.alloc<CustomTypeNode>();
1762   CTN->Identifier = demangleUnqualifiedTypeName(MangledName, true);
1763   if (!MangledName.consumeFront('@'))
1764     Error = true;
1765   if (Error)
1766     return nullptr;
1767   return CTN;
1768 }
1769 
1770 // Reads a primitive type.
1771 PrimitiveTypeNode *Demangler::demanglePrimitiveType(StringView &MangledName) {
1772   if (MangledName.consumeFront("$$T"))
1773     return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Nullptr);
1774 
1775   switch (MangledName.popFront()) {
1776   case 'X':
1777     return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Void);
1778   case 'D':
1779     return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Char);
1780   case 'C':
1781     return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Schar);
1782   case 'E':
1783     return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Uchar);
1784   case 'F':
1785     return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Short);
1786   case 'G':
1787     return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Ushort);
1788   case 'H':
1789     return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Int);
1790   case 'I':
1791     return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Uint);
1792   case 'J':
1793     return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Long);
1794   case 'K':
1795     return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Ulong);
1796   case 'M':
1797     return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Float);
1798   case 'N':
1799     return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Double);
1800   case 'O':
1801     return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Ldouble);
1802   case '_': {
1803     if (MangledName.empty()) {
1804       Error = true;
1805       return nullptr;
1806     }
1807     switch (MangledName.popFront()) {
1808     case 'N':
1809       return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Bool);
1810     case 'J':
1811       return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Int64);
1812     case 'K':
1813       return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Uint64);
1814     case 'W':
1815       return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Wchar);
1816     case 'S':
1817       return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Char16);
1818     case 'U':
1819       return Arena.alloc<PrimitiveTypeNode>(PrimitiveKind::Char32);
1820     }
1821     break;
1822   }
1823   }
1824   Error = true;
1825   return nullptr;
1826 }
1827 
1828 TagTypeNode *Demangler::demangleClassType(StringView &MangledName) {
1829   TagTypeNode *TT = nullptr;
1830 
1831   switch (MangledName.popFront()) {
1832   case 'T':
1833     TT = Arena.alloc<TagTypeNode>(TagKind::Union);
1834     break;
1835   case 'U':
1836     TT = Arena.alloc<TagTypeNode>(TagKind::Struct);
1837     break;
1838   case 'V':
1839     TT = Arena.alloc<TagTypeNode>(TagKind::Class);
1840     break;
1841   case 'W':
1842     if (MangledName.popFront() != '4') {
1843       Error = true;
1844       return nullptr;
1845     }
1846     TT = Arena.alloc<TagTypeNode>(TagKind::Enum);
1847     break;
1848   default:
1849     assert(false);
1850   }
1851 
1852   TT->QualifiedName = demangleFullyQualifiedTypeName(MangledName);
1853   return TT;
1854 }
1855 
1856 // <pointer-type> ::= E? <pointer-cvr-qualifiers> <ext-qualifiers> <type>
1857 //                       # the E is required for 64-bit non-static pointers
1858 PointerTypeNode *Demangler::demanglePointerType(StringView &MangledName) {
1859   PointerTypeNode *Pointer = Arena.alloc<PointerTypeNode>();
1860 
1861   std::tie(Pointer->Quals, Pointer->Affinity) =
1862       demanglePointerCVQualifiers(MangledName);
1863 
1864   if (MangledName.consumeFront("6")) {
1865     Pointer->Pointee = demangleFunctionType(MangledName, false);
1866     return Pointer;
1867   }
1868 
1869   Qualifiers ExtQuals = demanglePointerExtQualifiers(MangledName);
1870   Pointer->Quals = Qualifiers(Pointer->Quals | ExtQuals);
1871 
1872   Pointer->Pointee = demangleType(MangledName, QualifierMangleMode::Mangle);
1873   return Pointer;
1874 }
1875 
1876 PointerTypeNode *Demangler::demangleMemberPointerType(StringView &MangledName) {
1877   PointerTypeNode *Pointer = Arena.alloc<PointerTypeNode>();
1878 
1879   std::tie(Pointer->Quals, Pointer->Affinity) =
1880       demanglePointerCVQualifiers(MangledName);
1881   assert(Pointer->Affinity == PointerAffinity::Pointer);
1882 
1883   Qualifiers ExtQuals = demanglePointerExtQualifiers(MangledName);
1884   Pointer->Quals = Qualifiers(Pointer->Quals | ExtQuals);
1885 
1886   if (MangledName.consumeFront("8")) {
1887     Pointer->ClassParent = demangleFullyQualifiedTypeName(MangledName);
1888     Pointer->Pointee = demangleFunctionType(MangledName, true);
1889   } else {
1890     Qualifiers PointeeQuals = Q_None;
1891     bool IsMember = false;
1892     std::tie(PointeeQuals, IsMember) = demangleQualifiers(MangledName);
1893     assert(IsMember);
1894     Pointer->ClassParent = demangleFullyQualifiedTypeName(MangledName);
1895 
1896     Pointer->Pointee = demangleType(MangledName, QualifierMangleMode::Drop);
1897     Pointer->Pointee->Quals = PointeeQuals;
1898   }
1899 
1900   return Pointer;
1901 }
1902 
1903 Qualifiers Demangler::demanglePointerExtQualifiers(StringView &MangledName) {
1904   Qualifiers Quals = Q_None;
1905   if (MangledName.consumeFront('E'))
1906     Quals = Qualifiers(Quals | Q_Pointer64);
1907   if (MangledName.consumeFront('I'))
1908     Quals = Qualifiers(Quals | Q_Restrict);
1909   if (MangledName.consumeFront('F'))
1910     Quals = Qualifiers(Quals | Q_Unaligned);
1911 
1912   return Quals;
1913 }
1914 
1915 ArrayTypeNode *Demangler::demangleArrayType(StringView &MangledName) {
1916   assert(MangledName.front() == 'Y');
1917   MangledName.popFront();
1918 
1919   uint64_t Rank = 0;
1920   bool IsNegative = false;
1921   std::tie(Rank, IsNegative) = demangleNumber(MangledName);
1922   if (IsNegative || Rank == 0) {
1923     Error = true;
1924     return nullptr;
1925   }
1926 
1927   ArrayTypeNode *ATy = Arena.alloc<ArrayTypeNode>();
1928   NodeList *Head = Arena.alloc<NodeList>();
1929   NodeList *Tail = Head;
1930 
1931   for (uint64_t I = 0; I < Rank; ++I) {
1932     uint64_t D = 0;
1933     std::tie(D, IsNegative) = demangleNumber(MangledName);
1934     if (IsNegative) {
1935       Error = true;
1936       return nullptr;
1937     }
1938     Tail->N = Arena.alloc<IntegerLiteralNode>(D, IsNegative);
1939     if (I + 1 < Rank) {
1940       Tail->Next = Arena.alloc<NodeList>();
1941       Tail = Tail->Next;
1942     }
1943   }
1944   ATy->Dimensions = nodeListToNodeArray(Arena, Head, Rank);
1945 
1946   if (MangledName.consumeFront("$$C")) {
1947     bool IsMember = false;
1948     std::tie(ATy->Quals, IsMember) = demangleQualifiers(MangledName);
1949     if (IsMember) {
1950       Error = true;
1951       return nullptr;
1952     }
1953   }
1954 
1955   ATy->ElementType = demangleType(MangledName, QualifierMangleMode::Drop);
1956   return ATy;
1957 }
1958 
1959 // Reads a function or a template parameters.
1960 NodeArrayNode *
1961 Demangler::demangleFunctionParameterList(StringView &MangledName) {
1962   // Empty parameter list.
1963   if (MangledName.consumeFront('X'))
1964     return {};
1965 
1966   NodeList *Head = Arena.alloc<NodeList>();
1967   NodeList **Current = &Head;
1968   size_t Count = 0;
1969   while (!Error && !MangledName.startsWith('@') &&
1970          !MangledName.startsWith('Z')) {
1971     ++Count;
1972 
1973     if (startsWithDigit(MangledName)) {
1974       size_t N = MangledName[0] - '0';
1975       if (N >= Backrefs.FunctionParamCount) {
1976         Error = true;
1977         return {};
1978       }
1979       MangledName = MangledName.dropFront();
1980 
1981       *Current = Arena.alloc<NodeList>();
1982       (*Current)->N = Backrefs.FunctionParams[N];
1983       Current = &(*Current)->Next;
1984       continue;
1985     }
1986 
1987     size_t OldSize = MangledName.size();
1988 
1989     *Current = Arena.alloc<NodeList>();
1990     TypeNode *TN = demangleType(MangledName, QualifierMangleMode::Drop);
1991 
1992     (*Current)->N = TN;
1993 
1994     size_t CharsConsumed = OldSize - MangledName.size();
1995     assert(CharsConsumed != 0);
1996 
1997     // Single-letter types are ignored for backreferences because memorizing
1998     // them doesn't save anything.
1999     if (Backrefs.FunctionParamCount <= 9 && CharsConsumed > 1)
2000       Backrefs.FunctionParams[Backrefs.FunctionParamCount++] = TN;
2001 
2002     Current = &(*Current)->Next;
2003   }
2004 
2005   if (Error)
2006     return {};
2007 
2008   NodeArrayNode *NA = nodeListToNodeArray(Arena, Head, Count);
2009   // A non-empty parameter list is terminated by either 'Z' (variadic) parameter
2010   // list or '@' (non variadic).  Careful not to consume "@Z", as in that case
2011   // the following Z could be a throw specifier.
2012   if (MangledName.consumeFront('@'))
2013     return NA;
2014 
2015   if (MangledName.consumeFront('Z')) {
2016     // This is a variadic parameter list.  We probably need a variadic node to
2017     // append to the end.
2018     return NA;
2019   }
2020 
2021   Error = true;
2022   return {};
2023 }
2024 
2025 NodeArrayNode *
2026 Demangler::demangleTemplateParameterList(StringView &MangledName) {
2027   NodeList *Head;
2028   NodeList **Current = &Head;
2029   size_t Count = 0;
2030 
2031   while (!Error && !MangledName.startsWith('@')) {
2032     if (MangledName.consumeFront("$S") || MangledName.consumeFront("$$V") ||
2033         MangledName.consumeFront("$$$V") || MangledName.consumeFront("$$Z")) {
2034       // parameter pack separator
2035       continue;
2036     }
2037 
2038     ++Count;
2039 
2040     // Template parameter lists don't participate in back-referencing.
2041     *Current = Arena.alloc<NodeList>();
2042 
2043     NodeList &TP = **Current;
2044 
2045     TemplateParameterReferenceNode *TPRN = nullptr;
2046     if (MangledName.consumeFront("$$Y")) {
2047       // Template alias
2048       TP.N = demangleFullyQualifiedTypeName(MangledName);
2049     } else if (MangledName.consumeFront("$$B")) {
2050       // Array
2051       TP.N = demangleType(MangledName, QualifierMangleMode::Drop);
2052     } else if (MangledName.consumeFront("$$C")) {
2053       // Type has qualifiers.
2054       TP.N = demangleType(MangledName, QualifierMangleMode::Mangle);
2055     } else if (MangledName.startsWith("$1") || MangledName.startsWith("$H") ||
2056                MangledName.startsWith("$I") || MangledName.startsWith("$J")) {
2057       // Pointer to member
2058       TP.N = TPRN = Arena.alloc<TemplateParameterReferenceNode>();
2059       TPRN->IsMemberPointer = true;
2060 
2061       MangledName = MangledName.dropFront();
2062       // 1 - single inheritance       <name>
2063       // H - multiple inheritance     <name> <number>
2064       // I - virtual inheritance      <name> <number> <number> <number>
2065       // J - unspecified inheritance  <name> <number> <number> <number>
2066       char InheritanceSpecifier = MangledName.popFront();
2067       SymbolNode *S = nullptr;
2068       if (MangledName.startsWith('?')) {
2069         S = parse(MangledName);
2070         memorizeIdentifier(S->Name->getUnqualifiedIdentifier());
2071       }
2072 
2073       switch (InheritanceSpecifier) {
2074       case 'J':
2075         TPRN->ThunkOffsets[TPRN->ThunkOffsetCount++] =
2076             demangleSigned(MangledName);
2077         LLVM_FALLTHROUGH;
2078       case 'I':
2079         TPRN->ThunkOffsets[TPRN->ThunkOffsetCount++] =
2080             demangleSigned(MangledName);
2081         LLVM_FALLTHROUGH;
2082       case 'H':
2083         TPRN->ThunkOffsets[TPRN->ThunkOffsetCount++] =
2084             demangleSigned(MangledName);
2085         LLVM_FALLTHROUGH;
2086       case '1':
2087         break;
2088       default:
2089         Error = true;
2090         break;
2091       }
2092       TPRN->Affinity = PointerAffinity::Pointer;
2093       TPRN->Symbol = S;
2094     } else if (MangledName.startsWith("$E?")) {
2095       MangledName.consumeFront("$E");
2096       // Reference to symbol
2097       TP.N = TPRN = Arena.alloc<TemplateParameterReferenceNode>();
2098       TPRN->Symbol = parse(MangledName);
2099       TPRN->Affinity = PointerAffinity::Reference;
2100     } else if (MangledName.startsWith("$F") || MangledName.startsWith("$G")) {
2101       TP.N = TPRN = Arena.alloc<TemplateParameterReferenceNode>();
2102 
2103       // Data member pointer.
2104       MangledName = MangledName.dropFront();
2105       char InheritanceSpecifier = MangledName.popFront();
2106 
2107       switch (InheritanceSpecifier) {
2108       case 'G':
2109         TPRN->ThunkOffsets[TPRN->ThunkOffsetCount++] =
2110             demangleSigned(MangledName);
2111         LLVM_FALLTHROUGH;
2112       case 'F':
2113         TPRN->ThunkOffsets[TPRN->ThunkOffsetCount++] =
2114             demangleSigned(MangledName);
2115         TPRN->ThunkOffsets[TPRN->ThunkOffsetCount++] =
2116             demangleSigned(MangledName);
2117         LLVM_FALLTHROUGH;
2118       case '0':
2119         break;
2120       default:
2121         Error = true;
2122         break;
2123       }
2124       TPRN->IsMemberPointer = true;
2125 
2126     } else if (MangledName.consumeFront("$0")) {
2127       // Integral non-type template parameter
2128       bool IsNegative = false;
2129       uint64_t Value = 0;
2130       std::tie(Value, IsNegative) = demangleNumber(MangledName);
2131 
2132       TP.N = Arena.alloc<IntegerLiteralNode>(Value, IsNegative);
2133     } else {
2134       TP.N = demangleType(MangledName, QualifierMangleMode::Drop);
2135     }
2136     if (Error)
2137       return nullptr;
2138 
2139     Current = &TP.Next;
2140   }
2141 
2142   if (Error)
2143     return nullptr;
2144 
2145   // Template parameter lists cannot be variadic, so it can only be terminated
2146   // by @.
2147   if (MangledName.consumeFront('@'))
2148     return nodeListToNodeArray(Arena, Head, Count);
2149   Error = true;
2150   return nullptr;
2151 }
2152 
2153 void Demangler::dumpBackReferences() {
2154   std::printf("%d function parameter backreferences\n",
2155               (int)Backrefs.FunctionParamCount);
2156 
2157   // Create an output stream so we can render each type.
2158   OutputStream OS;
2159   if (!initializeOutputStream(nullptr, nullptr, OS, 1024))
2160     std::terminate();
2161   for (size_t I = 0; I < Backrefs.FunctionParamCount; ++I) {
2162     OS.setCurrentPosition(0);
2163 
2164     TypeNode *T = Backrefs.FunctionParams[I];
2165     T->output(OS, OF_Default);
2166 
2167     std::printf("  [%d] - %.*s\n", (int)I, (int)OS.getCurrentPosition(),
2168                 OS.getBuffer());
2169   }
2170   std::free(OS.getBuffer());
2171 
2172   if (Backrefs.FunctionParamCount > 0)
2173     std::printf("\n");
2174   std::printf("%d name backreferences\n", (int)Backrefs.NamesCount);
2175   for (size_t I = 0; I < Backrefs.NamesCount; ++I) {
2176     std::printf("  [%d] - %.*s\n", (int)I, (int)Backrefs.Names[I]->Name.size(),
2177                 Backrefs.Names[I]->Name.begin());
2178   }
2179   if (Backrefs.NamesCount > 0)
2180     std::printf("\n");
2181 }
2182 
2183 char *llvm::microsoftDemangle(const char *MangledName, char *Buf, size_t *N,
2184                               int *Status, MSDemangleFlags Flags) {
2185   int InternalStatus = demangle_success;
2186   Demangler D;
2187   OutputStream S;
2188 
2189   StringView Name{MangledName};
2190   SymbolNode *AST = D.parse(Name);
2191 
2192   if (Flags & MSDF_DumpBackrefs)
2193     D.dumpBackReferences();
2194 
2195   if (D.Error)
2196     InternalStatus = demangle_invalid_mangled_name;
2197   else if (!initializeOutputStream(Buf, N, S, 1024))
2198     InternalStatus = demangle_memory_alloc_failure;
2199   else {
2200     AST->output(S, OF_Default);
2201     S += '\0';
2202     if (N != nullptr)
2203       *N = S.getCurrentPosition();
2204     Buf = S.getBuffer();
2205   }
2206 
2207   if (Status)
2208     *Status = InternalStatus;
2209   return InternalStatus == demangle_success ? Buf : nullptr;
2210 }
2211