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