xref: /freebsd/contrib/llvm-project/llvm/lib/Demangle/RustDemangle.cpp (revision ec0ea6efa1ad229d75c394c1a9b9cac33af2b1d3) 
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 }
1128