contrib/llvm/lib/Demangle/MicrosoftDemangle.cpp

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