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