llvm/lib/Demangle/RustDemangle.cpp

   1 //===--- RustDemangle.cpp ---------------------------------------*- C++ -*-===//
   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 Rust v0 mangled symbols as specified in
  10 // https://rust-lang.github.io/rfcs/2603-rust-symbol-name-mangling-v0.html
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/Demangle/Demangle.h"
  15 #include "llvm/Demangle/StringView.h"
  16 #include "llvm/Demangle/Utility.h"
  17
  18 #include <algorithm>
  19 #include <cassert>
  20 #include <cstdint>
  21 #include <cstring>
  22 #include <limits>
  23
  24 using namespace llvm;
  25
  26 using llvm::itanium_demangle::OutputStream;
  27 using llvm::itanium_demangle::StringView;
  28 using llvm::itanium_demangle::SwapAndRestore;
  29
  30 namespace {
  31
  32 struct Identifier {
  33   StringView Name;
  34   bool Punycode;
  35
  36   bool empty() const { return Name.empty(); }
  37 };
  38
  39 enum class BasicType {
  40   Bool,
  41   Char,
  42   I8,
  43   I16,
  44   I32,
  45   I64,
  46   I128,
  47   ISize,
  48   U8,
  49   U16,
  50   U32,
  51   U64,
  52   U128,
  53   USize,
  54   F32,
  55   F64,
  56   Str,
  57   Placeholder,
  58   Unit,
  59   Variadic,
  60   Never,
  61 };
  62
  63 enum class IsInType {
  64   No,
  65   Yes,
  66 };
  67
  68 enum class LeaveGenericsOpen {
  69   No,
  70   Yes,
  71 };
  72
  73 class Demangler {
  74   // Maximum recursion level. Used to avoid stack overflow.
  75   size_t MaxRecursionLevel;
  76   // Current recursion level.
  77   size_t RecursionLevel;
  78   size_t BoundLifetimes;
  79   // Input string that is being demangled with "_R" prefix removed.
  80   StringView Input;
  81   // Position in the input string.
  82   size_t Position;
  83   // When true, print methods append the output to the stream.
  84   // When false, the output is suppressed.
  85   bool Print;
  86   // True if an error occurred.
  87   bool Error;
  88
  89 public:
  90   // Demangled output.
  91   OutputStream Output;
  92
  93   Demangler(size_t MaxRecursionLevel = 500);
  94
  95   bool demangle(StringView MangledName);
  96
  97 private:
  98   bool demanglePath(IsInType Type,
  99                     LeaveGenericsOpen LeaveOpen = LeaveGenericsOpen::No);
 100   void demangleImplPath(IsInType InType);
 101   void demangleGenericArg();
 102   void demangleType();
 103   void demangleFnSig();
 104   void demangleDynBounds();
 105   void demangleDynTrait();
 106   void demangleOptionalBinder();
 107   void demangleConst();
 108   void demangleConstInt();
 109   void demangleConstBool();
 110   void demangleConstChar();
 111
 112   template <typename Callable> void demangleBackref(Callable Demangler) {
 113     uint64_t Backref = parseBase62Number();
 114     if (Error || Backref >= Position) {
 115       Error = true;
 116       return;
 117     }
 118
 119     if (!Print)
 120       return;
 121
 122     SwapAndRestore<size_t> SavePosition(Position, Position);
 123     Position = Backref;
 124     Demangler();
 125   }
 126
 127   Identifier parseIdentifier();
 128   uint64_t parseOptionalBase62Number(char Tag);
 129   uint64_t parseBase62Number();
 130   uint64_t parseDecimalNumber();
 131   uint64_t parseHexNumber(StringView &HexDigits);
 132
 133   void print(char C);
 134   void print(StringView S);
 135   void printDecimalNumber(uint64_t N);
 136   void printBasicType(BasicType);
 137   void printLifetime(uint64_t Index);
 138
 139   char look() const;
 140   char consume();
 141   bool consumeIf(char Prefix);
 142
 143   bool addAssign(uint64_t &A, uint64_t B);
 144   bool mulAssign(uint64_t &A, uint64_t B);
 145 };
 146
 147 } // namespace
 148
 149 char *llvm::rustDemangle(const char *MangledName, char *Buf, size_t *N,
 150                          int *Status) {
 151   if (MangledName == nullptr || (Buf != nullptr && N == nullptr)) {
 152     if (Status != nullptr)
 153       *Status = demangle_invalid_args;
 154     return nullptr;
 155   }
 156
 157   // Return early if mangled name doesn't look like a Rust symbol.
 158   StringView Mangled(MangledName);
 159   if (!Mangled.startsWith("_R")) {
 160     if (Status != nullptr)
 161       *Status = demangle_invalid_mangled_name;
 162     return nullptr;
 163   }
 164
 165   Demangler D;
 166   if (!initializeOutputStream(nullptr, nullptr, D.Output, 1024)) {
 167     if (Status != nullptr)
 168       *Status = demangle_memory_alloc_failure;
 169     return nullptr;
 170   }
 171
 172   if (!D.demangle(Mangled)) {
 173     if (Status != nullptr)
 174       *Status = demangle_invalid_mangled_name;
 175     std::free(D.Output.getBuffer());
 176     return nullptr;
 177   }
 178
 179   D.Output += '\0';
 180   char *Demangled = D.Output.getBuffer();
 181   size_t DemangledLen = D.Output.getCurrentPosition();
 182
 183   if (Buf != nullptr) {
 184     if (DemangledLen <= *N) {
 185       std::memcpy(Buf, Demangled, DemangledLen);
 186       std::free(Demangled);
 187       Demangled = Buf;
 188     } else {
 189       std::free(Buf);
 190     }
 191   }
 192
 193   if (N != nullptr)
 194     *N = DemangledLen;
 195
 196   if (Status != nullptr)
 197     *Status = demangle_success;
 198
 199   return Demangled;
 200 }
 201
 202 Demangler::Demangler(size_t MaxRecursionLevel)
 203     : MaxRecursionLevel(MaxRecursionLevel) {}
 204
 205 static inline bool isDigit(const char C) { return '0' <= C && C <= '9'; }
 206
 207 static inline bool isHexDigit(const char C) {
 208   return ('0' <= C && C <= '9') || ('a' <= C && C <= 'f');
 209 }
 210
 211 static inline bool isLower(const char C) { return 'a' <= C && C <= 'z'; }
 212
 213 static inline bool isUpper(const char C) { return 'A' <= C && C <= 'Z'; }
 214
 215 /// Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
 216 static inline bool isValid(const char C) {
 217   return isDigit(C) || isLower(C) || isUpper(C) || C == '_';
 218 }
 219
 220 // Demangles Rust v0 mangled symbol. Returns true when successful, and false
 221 // otherwise. The demangled symbol is stored in Output field. It is
 222 // responsibility of the caller to free the memory behind the output stream.
 223 //
 224 // <symbol-name> = "_R" <path> [<instantiating-crate>]
 225 bool Demangler::demangle(StringView Mangled) {
 226   Position = 0;
 227   Error = false;
 228   Print = true;
 229   RecursionLevel = 0;
 230   BoundLifetimes = 0;
 231
 232   if (!Mangled.consumeFront("_R")) {
 233     Error = true;
 234     return false;
 235   }
 236   size_t Dot = Mangled.find('.');
 237   Input = Mangled.substr(0, Dot);
 238   StringView Suffix = Mangled.dropFront(Dot);
 239
 240   demanglePath(IsInType::No);
 241
 242   if (Position != Input.size()) {
 243     SwapAndRestore<bool> SavePrint(Print, false);
 244     demanglePath(IsInType::No);
 245   }
 246
 247   if (Position != Input.size())
 248     Error = true;
 249
 250   if (!Suffix.empty()) {
 251     print(" (");
 252     print(Suffix);
 253     print(")");
 254   }
 255
 256   return !Error;
 257 }
 258
 259 // Demangles a path. InType indicates whether a path is inside a type. When
 260 // LeaveOpen is true, a closing `>` after generic arguments is omitted from the
 261 // output. Return value indicates whether generics arguments have been left
 262 // open.
 263 //
 264 // <path> = "C" <identifier>               // crate root
 265 //        | "M" <impl-path> <type>         // <T> (inherent impl)
 266 //        | "X" <impl-path> <type> <path>  // <T as Trait> (trait impl)
 267 //        | "Y" <type> <path>              // <T as Trait> (trait definition)
 268 //        | "N" <ns> <path> <identifier>   // ...::ident (nested path)
 269 //        | "I" <path> {<generic-arg>} "E" // ...<T, U> (generic args)
 270 //        | <backref>
 271 // <identifier> = [<disambiguator>] <undisambiguated-identifier>
 272 // <ns> = "C"      // closure
 273 //      | "S"      // shim
 274 //      | <A-Z>    // other special namespaces
 275 //      | <a-z>    // internal namespaces
 276 bool Demangler::demanglePath(IsInType InType, LeaveGenericsOpen LeaveOpen) {
 277   if (Error || RecursionLevel >= MaxRecursionLevel) {
 278     Error = true;
 279     return false;
 280   }
 281   SwapAndRestore<size_t> SaveRecursionLevel(RecursionLevel, RecursionLevel + 1);
 282
 283   switch (consume()) {
 284   case 'C': {
 285     parseOptionalBase62Number('s');
 286     Identifier Ident = parseIdentifier();
 287     print(Ident.Name);
 288     break;
 289   }
 290   case 'M': {
 291     demangleImplPath(InType);
 292     print("<");
 293     demangleType();
 294     print(">");
 295     break;
 296   }
 297   case 'X': {
 298     demangleImplPath(InType);
 299     print("<");
 300     demangleType();
 301     print(" as ");
 302     demanglePath(IsInType::Yes);
 303     print(">");
 304     break;
 305   }
 306   case 'Y': {
 307     print("<");
 308     demangleType();
 309     print(" as ");
 310     demanglePath(IsInType::Yes);
 311     print(">");
 312     break;
 313   }
 314   case 'N': {
 315     char NS = consume();
 316     if (!isLower(NS) && !isUpper(NS)) {
 317       Error = true;
 318       break;
 319     }
 320     demanglePath(InType);
 321
 322     uint64_t Disambiguator = parseOptionalBase62Number('s');
 323     Identifier Ident = parseIdentifier();
 324
 325     if (isUpper(NS)) {
 326       // Special namespaces
 327       print("::{");
 328       if (NS == 'C')
 329         print("closure");
 330       else if (NS == 'S')
 331         print("shim");
 332       else
 333         print(NS);
 334       if (!Ident.empty()) {
 335         print(":");
 336         print(Ident.Name);
 337       }
 338       print('#');
 339       printDecimalNumber(Disambiguator);
 340       print('}');
 341     } else {
 342       // Implementation internal namespaces.
 343       if (!Ident.empty()) {
 344         print("::");
 345         print(Ident.Name);
 346       }
 347     }
 348     break;
 349   }
 350   case 'I': {
 351     demanglePath(InType);
 352     // Omit "::" when in a type, where it is optional.
 353     if (InType == IsInType::No)
 354       print("::");
 355     print("<");
 356     for (size_t I = 0; !Error && !consumeIf('E'); ++I) {
 357       if (I > 0)
 358         print(", ");
 359       demangleGenericArg();
 360     }
 361     if (LeaveOpen == LeaveGenericsOpen::Yes)
 362       return true;
 363     else
 364       print(">");
 365     break;
 366   }
 367   case 'B': {
 368     bool IsOpen = false;
 369     demangleBackref([&] { IsOpen = demanglePath(InType, LeaveOpen); });
 370     return IsOpen;
 371   }
 372   default:
 373     Error = true;
 374     break;
 375   }
 376
 377   return false;
 378 }
 379
 380 // <impl-path> = [<disambiguator>] <path>
 381 // <disambiguator> = "s" <base-62-number>
 382 void Demangler::demangleImplPath(IsInType InType) {
 383   SwapAndRestore<bool> SavePrint(Print, false);
 384   parseOptionalBase62Number('s');
 385   demanglePath(InType);
 386 }
 387
 388 // <generic-arg> = <lifetime>
 389 //               | <type>
 390 //               | "K" <const>
 391 // <lifetime> = "L" <base-62-number>
 392 void Demangler::demangleGenericArg() {
 393   if (consumeIf('L'))
 394     printLifetime(parseBase62Number());
 395   else if (consumeIf('K'))
 396     demangleConst();
 397   else
 398     demangleType();
 399 }
 400
 401 // <basic-type> = "a"      // i8
 402 //              | "b"      // bool
 403 //              | "c"      // char
 404 //              | "d"      // f64
 405 //              | "e"      // str
 406 //              | "f"      // f32
 407 //              | "h"      // u8
 408 //              | "i"      // isize
 409 //              | "j"      // usize
 410 //              | "l"      // i32
 411 //              | "m"      // u32
 412 //              | "n"      // i128
 413 //              | "o"      // u128
 414 //              | "s"      // i16
 415 //              | "t"      // u16
 416 //              | "u"      // ()
 417 //              | "v"      // ...
 418 //              | "x"      // i64
 419 //              | "y"      // u64
 420 //              | "z"      // !
 421 //              | "p"      // placeholder (e.g. for generic params), shown as _
 422 static bool parseBasicType(char C, BasicType &Type) {
 423   switch (C) {
 424   case 'a':
 425     Type = BasicType::I8;
 426     return true;
 427   case 'b':
 428     Type = BasicType::Bool;
 429     return true;
 430   case 'c':
 431     Type = BasicType::Char;
 432     return true;
 433   case 'd':
 434     Type = BasicType::F64;
 435     return true;
 436   case 'e':
 437     Type = BasicType::Str;
 438     return true;
 439   case 'f':
 440     Type = BasicType::F32;
 441     return true;
 442   case 'h':
 443     Type = BasicType::U8;
 444     return true;
 445   case 'i':
 446     Type = BasicType::ISize;
 447     return true;
 448   case 'j':
 449     Type = BasicType::USize;
 450     return true;
 451   case 'l':
 452     Type = BasicType::I32;
 453     return true;
 454   case 'm':
 455     Type = BasicType::U32;
 456     return true;
 457   case 'n':
 458     Type = BasicType::I128;
 459     return true;
 460   case 'o':
 461     Type = BasicType::U128;
 462     return true;
 463   case 'p':
 464     Type = BasicType::Placeholder;
 465     return true;
 466   case 's':
 467     Type = BasicType::I16;
 468     return true;
 469   case 't':
 470     Type = BasicType::U16;
 471     return true;
 472   case 'u':
 473     Type = BasicType::Unit;
 474     return true;
 475   case 'v':
 476     Type = BasicType::Variadic;
 477     return true;
 478   case 'x':
 479     Type = BasicType::I64;
 480     return true;
 481   case 'y':
 482     Type = BasicType::U64;
 483     return true;
 484   case 'z':
 485     Type = BasicType::Never;
 486     return true;
 487   default:
 488     return false;
 489   }
 490 }
 491
 492 void Demangler::printBasicType(BasicType Type) {
 493   switch (Type) {
 494   case BasicType::Bool:
 495     print("bool");
 496     break;
 497   case BasicType::Char:
 498     print("char");
 499     break;
 500   case BasicType::I8:
 501     print("i8");
 502     break;
 503   case BasicType::I16:
 504     print("i16");
 505     break;
 506   case BasicType::I32:
 507     print("i32");
 508     break;
 509   case BasicType::I64:
 510     print("i64");
 511     break;
 512   case BasicType::I128:
 513     print("i128");
 514     break;
 515   case BasicType::ISize:
 516     print("isize");
 517     break;
 518   case BasicType::U8:
 519     print("u8");
 520     break;
 521   case BasicType::U16:
 522     print("u16");
 523     break;
 524   case BasicType::U32:
 525     print("u32");
 526     break;
 527   case BasicType::U64:
 528     print("u64");
 529     break;
 530   case BasicType::U128:
 531     print("u128");
 532     break;
 533   case BasicType::USize:
 534     print("usize");
 535     break;
 536   case BasicType::F32:
 537     print("f32");
 538     break;
 539   case BasicType::F64:
 540     print("f64");
 541     break;
 542   case BasicType::Str:
 543     print("str");
 544     break;
 545   case BasicType::Placeholder:
 546     print("_");
 547     break;
 548   case BasicType::Unit:
 549     print("()");
 550     break;
 551   case BasicType::Variadic:
 552     print("...");
 553     break;
 554   case BasicType::Never:
 555     print("!");
 556     break;
 557   }
 558 }
 559
 560 // <type> = | <basic-type>
 561 //          | <path>                      // named type
 562 //          | "A" <type> <const>          // [T; N]
 563 //          | "S" <type>                  // [T]
 564 //          | "T" {<type>} "E"            // (T1, T2, T3, ...)
 565 //          | "R" [<lifetime>] <type>     // &T
 566 //          | "Q" [<lifetime>] <type>     // &mut T
 567 //          | "P" <type>                  // *const T
 568 //          | "O" <type>                  // *mut T
 569 //          | "F" <fn-sig>                // fn(...) -> ...
 570 //          | "D" <dyn-bounds> <lifetime> // dyn Trait<Assoc = X> + Send + 'a
 571 //          | <backref>                   // backref
 572 void Demangler::demangleType() {
 573   if (Error || RecursionLevel >= MaxRecursionLevel) {
 574     Error = true;
 575     return;
 576   }
 577   SwapAndRestore<size_t> SaveRecursionLevel(RecursionLevel, RecursionLevel + 1);
 578
 579   size_t Start = Position;
 580   char C = consume();
 581   BasicType Type;
 582   if (parseBasicType(C, Type))
 583     return printBasicType(Type);
 584
 585   switch (C) {
 586   case 'A':
 587     print("[");
 588     demangleType();
 589     print("; ");
 590     demangleConst();
 591     print("]");
 592     break;
 593   case 'S':
 594     print("[");
 595     demangleType();
 596     print("]");
 597     break;
 598   case 'T': {
 599     print("(");
 600     size_t I = 0;
 601     for (; !Error && !consumeIf('E'); ++I) {
 602       if (I > 0)
 603         print(", ");
 604       demangleType();
 605     }
 606     if (I == 1)
 607       print(",");
 608     print(")");
 609     break;
 610   }
 611   case 'R':
 612   case 'Q':
 613     print('&');
 614     if (consumeIf('L')) {
 615       if (auto Lifetime = parseBase62Number()) {
 616         printLifetime(Lifetime);
 617         print(' ');
 618       }
 619     }
 620     if (C == 'Q')
 621       print("mut ");
 622     demangleType();
 623     break;
 624   case 'P':
 625     print("*const ");
 626     demangleType();
 627     break;
 628   case 'O':
 629     print("*mut ");
 630     demangleType();
 631     break;
 632   case 'F':
 633     demangleFnSig();
 634     break;
 635   case 'D':
 636     demangleDynBounds();
 637     if (consumeIf('L')) {
 638       if (auto Lifetime = parseBase62Number()) {
 639         print(" + ");
 640         printLifetime(Lifetime);
 641       }
 642     } else {
 643       Error = true;
 644     }
 645     break;
 646   case 'B':
 647     demangleBackref([&] { demangleType(); });
 648     break;
 649   default:
 650     Position = Start;
 651     demanglePath(IsInType::Yes);
 652     break;
 653   }
 654 }
 655
 656 // <fn-sig> := [<binder>] ["U"] ["K" <abi>] {<type>} "E" <type>
 657 // <abi> = "C"
 658 //       | <undisambiguated-identifier>
 659 void Demangler::demangleFnSig() {
 660   SwapAndRestore<size_t> SaveBoundLifetimes(BoundLifetimes, BoundLifetimes);
 661   demangleOptionalBinder();
 662
 663   if (consumeIf('U'))
 664     print("unsafe ");
 665
 666   if (consumeIf('K')) {
 667     print("extern \"");
 668     if (consumeIf('C')) {
 669       print("C");
 670     } else {
 671       Identifier Ident = parseIdentifier();
 672       for (char C : Ident.Name) {
 673         // When mangling ABI string, the "-" is replaced with "_".
 674         if (C == '_')
 675           C = '-';
 676         print(C);
 677       }
 678     }
 679     print("\" ");
 680   }
 681
 682   print("fn(");
 683   for (size_t I = 0; !Error && !consumeIf('E'); ++I) {
 684     if (I > 0)
 685       print(", ");
 686     demangleType();
 687   }
 688   print(")");
 689
 690   if (consumeIf('u')) {
 691     // Skip the unit type from the output.
 692   } else {
 693     print(" -> ");
 694     demangleType();
 695   }
 696 }
 697
 698 // <dyn-bounds> = [<binder>] {<dyn-trait>} "E"
 699 void Demangler::demangleDynBounds() {
 700   SwapAndRestore<size_t> SaveBoundLifetimes(BoundLifetimes, BoundLifetimes);
 701   print("dyn ");
 702   demangleOptionalBinder();
 703   for (size_t I = 0; !Error && !consumeIf('E'); ++I) {
 704     if (I > 0)
 705       print(" + ");
 706     demangleDynTrait();
 707   }
 708 }
 709
 710 // <dyn-trait> = <path> {<dyn-trait-assoc-binding>}
 711 // <dyn-trait-assoc-binding> = "p" <undisambiguated-identifier> <type>
 712 void Demangler::demangleDynTrait() {
 713   bool IsOpen = demanglePath(IsInType::Yes, LeaveGenericsOpen::Yes);
 714   while (!Error && consumeIf('p')) {
 715     if (!IsOpen) {
 716       IsOpen = true;
 717       print('<');
 718     } else {
 719       print(", ");
 720     }
 721     print(parseIdentifier().Name);
 722     print(" = ");
 723     demangleType();
 724   }
 725   if (IsOpen)
 726     print(">");
 727 }
 728
 729 // Demangles optional binder and updates the number of bound lifetimes.
 730 //
 731 // <binder> = "G" <base-62-number>
 732 void Demangler::demangleOptionalBinder() {
 733   uint64_t Binder = parseOptionalBase62Number('G');
 734   if (Error || Binder == 0)
 735     return;
 736
 737   // In valid inputs each bound lifetime is referenced later. Referencing a
 738   // lifetime requires at least one byte of input. Reject inputs that are too
 739   // short to reference all bound lifetimes. Otherwise demangling of invalid
 740   // binders could generate excessive amounts of output.
 741   if (Binder >= Input.size() - BoundLifetimes) {
 742     Error = true;
 743     return;
 744   }
 745
 746   print("for<");
 747   for (size_t I = 0; I != Binder; ++I) {
 748     BoundLifetimes += 1;
 749     if (I > 0)
 750       print(", ");
 751     printLifetime(1);
 752   }
 753   print("> ");
 754 }
 755
 756 // <const> = <basic-type> <const-data>
 757 //         | "p"                          // placeholder
 758 //         | <backref>
 759 void Demangler::demangleConst() {
 760   if (Error || RecursionLevel >= MaxRecursionLevel) {
 761     Error = true;
 762     return;
 763   }
 764   SwapAndRestore<size_t> SaveRecursionLevel(RecursionLevel, RecursionLevel + 1);
 765
 766   char C = consume();
 767   BasicType Type;
 768   if (parseBasicType(C, Type)) {
 769     switch (Type) {
 770     case BasicType::I8:
 771     case BasicType::I16:
 772     case BasicType::I32:
 773     case BasicType::I64:
 774     case BasicType::I128:
 775     case BasicType::ISize:
 776     case BasicType::U8:
 777     case BasicType::U16:
 778     case BasicType::U32:
 779     case BasicType::U64:
 780     case BasicType::U128:
 781     case BasicType::USize:
 782       demangleConstInt();
 783       break;
 784     case BasicType::Bool:
 785       demangleConstBool();
 786       break;
 787     case BasicType::Char:
 788       demangleConstChar();
 789       break;
 790     case BasicType::Placeholder:
 791       print('_');
 792       break;
 793     default:
 794       Error = true;
 795       break;
 796     }
 797   } else if (C == 'B') {
 798     demangleBackref([&] { demangleConst(); });
 799   } else {
 800     Error = true;
 801   }
 802 }
 803
 804 // <const-data> = ["n"] <hex-number>
 805 void Demangler::demangleConstInt() {
 806   if (consumeIf('n'))
 807     print('-');
 808
 809   StringView HexDigits;
 810   uint64_t Value = parseHexNumber(HexDigits);
 811   if (HexDigits.size() <= 16) {
 812     printDecimalNumber(Value);
 813   } else {
 814     print("0x");
 815     print(HexDigits);
 816   }
 817 }
 818
 819 // <const-data> = "0_" // false
 820 //              | "1_" // true
 821 void Demangler::demangleConstBool() {
 822   StringView HexDigits;
 823   parseHexNumber(HexDigits);
 824   if (HexDigits == "0")
 825     print("false");
 826   else if (HexDigits == "1")
 827     print("true");
 828   else
 829     Error = true;
 830 }
 831
 832 /// Returns true if CodePoint represents a printable ASCII character.
 833 static bool isAsciiPrintable(uint64_t CodePoint) {
 834   return 0x20 <= CodePoint && CodePoint <= 0x7e;
 835 }
 836
 837 // <const-data> = <hex-number>
 838 void Demangler::demangleConstChar() {
 839   StringView HexDigits;
 840   uint64_t CodePoint = parseHexNumber(HexDigits);
 841   if (Error || HexDigits.size() > 6) {
 842     Error = true;
 843     return;
 844   }
 845
 846   print("'");
 847   switch (CodePoint) {
 848   case '\t':
 849     print(R"(\t)");
 850     break;
 851   case '\r':
 852     print(R"(\r)");
 853     break;
 854   case '\n':
 855     print(R"(\n)");
 856     break;
 857   case '\\':
 858     print(R"(\\)");
 859     break;
 860   case '"':
 861     print(R"(")");
 862     break;
 863   case '\'':
 864     print(R"(\')");
 865     break;
 866   default:
 867     if (isAsciiPrintable(CodePoint)) {
 868       char C = CodePoint;
 869       print(C);
 870     } else {
 871       print(R"(\u{)");
 872       print(HexDigits);
 873       print('}');
 874     }
 875     break;
 876   }
 877   print('\'');
 878 }
 879
 880 // <undisambiguated-identifier> = ["u"] <decimal-number> ["_"] <bytes>
 881 Identifier Demangler::parseIdentifier() {
 882   bool Punycode = consumeIf('u');
 883   uint64_t Bytes = parseDecimalNumber();
 884
 885   // Underscore resolves the ambiguity when identifier starts with a decimal
 886   // digit or another underscore.
 887   consumeIf('_');
 888
 889   if (Error || Bytes > Input.size() - Position) {
 890     Error = true;
 891     return {};
 892   }
 893   StringView S = Input.substr(Position, Bytes);
 894   Position += Bytes;
 895
 896   if (!std::all_of(S.begin(), S.end(), isValid)) {
 897     Error = true;
 898     return {};
 899   }
 900
 901   return {S, Punycode};
 902 }
 903
 904 // Parses optional base 62 number. The presence of a number is determined using
 905 // Tag. Returns 0 when tag is absent and parsed value + 1 otherwise
 906 //
 907 // This function is indended for parsing disambiguators and binders which when
 908 // not present have their value interpreted as 0, and otherwise as decoded
 909 // value + 1. For example for binders, value for "G_" is 1, for "G0_" value is
 910 // 2. When "G" is absent value is 0.
 911 uint64_t Demangler::parseOptionalBase62Number(char Tag) {
 912   if (!consumeIf(Tag))
 913     return 0;
 914
 915   uint64_t N = parseBase62Number();
 916   if (Error || !addAssign(N, 1))
 917     return 0;
 918
 919   return N;
 920 }
 921
 922 // Parses base 62 number with <0-9a-zA-Z> as digits. Number is terminated by
 923 // "_". All values are offset by 1, so that "_" encodes 0, "0_" encodes 1,
 924 // "1_" encodes 2, etc.
 925 //
 926 // <base-62-number> = {<0-9a-zA-Z>} "_"
 927 uint64_t Demangler::parseBase62Number() {
 928   if (consumeIf('_'))
 929     return 0;
 930
 931   uint64_t Value = 0;
 932
 933   while (true) {
 934     uint64_t Digit;
 935     char C = consume();
 936
 937     if (C == '_') {
 938       break;
 939     } else if (isDigit(C)) {
 940       Digit = C - '0';
 941     } else if (isLower(C)) {
 942       Digit = 10 + (C - 'a');
 943     } else if (isUpper(C)) {
 944       Digit = 10 + 26 + (C - 'A');
 945     } else {
 946       Error = true;
 947       return 0;
 948     }
 949
 950     if (!mulAssign(Value, 62))
 951       return 0;
 952
 953     if (!addAssign(Value, Digit))
 954       return 0;
 955   }
 956
 957   if (!addAssign(Value, 1))
 958     return 0;
 959
 960   return Value;
 961 }
 962
 963 // Parses a decimal number that had been encoded without any leading zeros.
 964 //
 965 // <decimal-number> = "0"
 966 //                  | <1-9> {<0-9>}
 967 uint64_t Demangler::parseDecimalNumber() {
 968   char C = look();
 969   if (!isDigit(C)) {
 970     Error = true;
 971     return 0;
 972   }
 973
 974   if (C == '0') {
 975     consume();
 976     return 0;
 977   }
 978
 979   uint64_t Value = 0;
 980
 981   while (isDigit(look())) {
 982     if (!mulAssign(Value, 10)) {
 983       Error = true;
 984       return 0;
 985     }
 986
 987     uint64_t D = consume() - '0';
 988     if (!addAssign(Value, D))
 989       return 0;
 990   }
 991
 992   return Value;
 993 }
 994
 995 // Parses a hexadecimal number with <0-9a-f> as a digits. Returns the parsed
 996 // value and stores hex digits in HexDigits. The return value is unspecified if
 997 // HexDigits.size() > 16.
 998 //
 999 // <hex-number> = "0_"
1000 //              | <1-9a-f> {<0-9a-f>} "_"
1001 uint64_t Demangler::parseHexNumber(StringView &HexDigits) {
1002   size_t Start = Position;
1003   uint64_t Value = 0;
1004
1005   if (!isHexDigit(look()))
1006     Error = true;
1007
1008   if (consumeIf('0')) {
1009     if (!consumeIf('_'))
1010       Error = true;
1011   } else {
1012     while (!Error && !consumeIf('_')) {
1013       char C = consume();
1014       Value *= 16;
1015       if (isDigit(C))
1016         Value += C - '0';
1017       else if ('a' <= C && C <= 'f')
1018         Value += 10 + (C - 'a');
1019       else
1020         Error = true;
1021     }
1022   }
1023
1024   if (Error) {
1025     HexDigits = StringView();
1026     return 0;
1027   }
1028
1029   size_t End = Position - 1;
1030   assert(Start < End);
1031   HexDigits = Input.substr(Start, End - Start);
1032   return Value;
1033 }
1034
1035 void Demangler::print(char C) {
1036   if (Error || !Print)
1037     return;
1038
1039   Output += C;
1040 }
1041
1042 void Demangler::print(StringView S) {
1043   if (Error || !Print)
1044     return;
1045
1046   Output += S;
1047 }
1048
1049 void Demangler::printDecimalNumber(uint64_t N) {
1050   if (Error || !Print)
1051     return;
1052
1053   Output << N;
1054 }
1055
1056 // Prints a lifetime. An index 0 always represents an erased lifetime. Indices
1057 // starting from 1, are De Bruijn indices, referring to higher-ranked lifetimes
1058 // bound by one of the enclosing binders.
1059 void Demangler::printLifetime(uint64_t Index) {
1060   if (Index == 0) {
1061     print("'_");
1062     return;
1063   }
1064
1065   if (Index - 1 >= BoundLifetimes) {
1066     Error = true;
1067     return;
1068   }
1069
1070   uint64_t Depth = BoundLifetimes - Index;
1071   print('\'');
1072   if (Depth < 26) {
1073     char C = 'a' + Depth;
1074     print(C);
1075   } else {
1076     print('z');
1077     printDecimalNumber(Depth - 26 + 1);
1078   }
1079 }
1080
1081 char Demangler::look() const {
1082   if (Error || Position >= Input.size())
1083     return 0;
1084
1085   return Input[Position];
1086 }
1087
1088 char Demangler::consume() {
1089   if (Error || Position >= Input.size()) {
1090     Error = true;
1091     return 0;
1092   }
1093
1094   return Input[Position++];
1095 }
1096
1097 bool Demangler::consumeIf(char Prefix) {
1098   if (Error || Position >= Input.size() || Input[Position] != Prefix)
1099     return false;
1100
1101   Position += 1;
1102   return true;
1103 }
1104
1105 /// Computes A + B. When computation wraps around sets the error and returns
1106 /// false. Otherwise assigns the result to A and returns true.
1107 bool Demangler::addAssign(uint64_t &A, uint64_t B) {
1108   if (A > std::numeric_limits<uint64_t>::max() - B) {
1109     Error = true;
1110     return false;
1111   }
1112
1113   A += B;
1114   return true;
1115 }
1116
1117 /// Computes A * B. When computation wraps around sets the error and returns
1118 /// false. Otherwise assigns the result to A and returns true.
1119 bool Demangler::mulAssign(uint64_t &A, uint64_t B) {
1120   if (B != 0 && A > std::numeric_limits<uint64_t>::max() / B) {
1121     Error = true;
1122     return false;
1123   }
1124
1125   A *= B;
1126   return true;
1127 }