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