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