lib/Demangle/MicrosoftDemangle.cpp

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