[Demangle][Rust] Parse binders

[tmiasko]

Summary

Depends on D102581

[dblaikie]

Yeah, I think there's a bug in the bound count handling (off by one) due to the quirk in the parseOptionalBase62 parsing?

llvm/lib/Demangle/RustDemangle.cpp

462–467

Might be nice to have this written once/reused (rather than duplicated here between 'R' and 'Q' for instance) - not sure if it can be generalized over the use in demangleGenericArg too - all of them use the <lifetime> Production, but there's no common implementation of/function for that production - maybe there could be?

541

Judging by the phrasing, was this meant to say "Inputs exceeding the bound are /valid/" rather than invalid?

Maybe it'd be more suitable to have a fixed upper bound on the size of a demangled name in general instead of these special cases? I guess that could cover the recursion and this bound on bound lifetimes...

That might be more predictable for users and for testing, etc.

700–705

This seems like a really subtle and confusing API, especially given the existing "+ 1" behavior of the Base 62 encoding. I've been staring at the code in demangleFnSig+demangleBinder to figure out the first binder test case for a while before I realized that.

Any chance this could use uintmax for the invalid value, rather than offsetting the result in this way?

llvm/test/Demangle/rust.test

237–238

I'm having a hard time understanding this test in the context of the spec.

The spec says that _ encodes zero. So the G_ should be zero, right? Is there somewhere in the spec that says that <binder> mangled value is then 1 larger than that? (so a binder value 0 (_) is actually for 1 binder)?

[tmiasko]

• Reuse the implementation for R and Q productions.
• Reword the comment regarding invalid binders.

[tmiasko]

llvm/lib/Demangle/RustDemangle.cpp

462–467

I reused the implementation between R and Q productions.

541

I reworded the comment and added an explanation why those inputs are invalid.

I think we need at least two different limitation mechanisms. A recursion limit to avoid unbounded recursion once we start parsing backreferences, especially those that don't produce any output. And another limit to handle large output.

I decided to check for invalid binders specifically since they are uniquely problematic; short strings like _RIC5crateFGAAAAA_EuE already generate gigabytes of output. The proposed bound rejects only invalid inputs, so it shouldn't be surprising for users in practice.

A general limit on the output size would be alternative option. Although it requires answering the hard question what the limit should be.

700–705

There are two layers of +1 which makes it quite confusing, but this is intended encoding of optional base62 numbers.

llvm/test/Demangle/rust.test

237–238

This looks like an omission in the specification The binder production should be marked as optional, and then the presence of G participates in the encoding of the value in analogous way to s in disambiguators:

If the disambiguator is not present, this index is 0. If it is of the form s_ then the index is 1. If it is of the form s<base-62-digit>_ then the index is <base-62-digit> + 2.

Does this clarify the situation?

I will look into updating the specification.

[tmiasko]

Rebuild after a change to a parent revision

[dblaikie]

llvm/lib/Demangle/RustDemangle.cpp

462–467

any chance of having a "demangleLifetime" that can be used in "demangleGenericArg" as well as here? (nice to have a function for each production, so it's easier to find the implementation of that production in one place)

541

Fair enough - thanks for the details!

700–705

Fair enough - maybe some more quotations from the spec to explain this would be useful?

llvm/test/Demangle/rust.test

237–238

Ah, OK - yeah, spec update and some more words in the implementation (see other comment) would probably be handy. Thanks!

[tmiasko]

Extend comment about +1 behaviour when parsing optional base-62 numbers.

llvm/lib/Demangle/RustDemangle.cpp

462–467

Yeah it would be nice to unify those, but there is slight difference in a treatment of erased lifetimes:

• In generic arguments erased lifetimes are always printed, since order is significant (although rustc does not mangle any lifetimes arguments when all lifetimes are erased).
• In references they are not printed (rustc does not mangle them in this context, so a difference in demangler behaviour would be unobservable in practice).
• In trait objects (yet to be implemented) lifetimes are mandatory, but there is no reason to print erased lifetimes.

700–705

I extended the comment and added a few concrete examples.

llvm/test/Demangle/rust.test

237–238

The proposed update to the specification https://github.com/rust-lang/rfcs/pull/3130.

[dblaikie]

Sounds good, thanks!

llvm/lib/Demangle/RustDemangle.cpp

462–467

having parameters to the demangle function to support these different behaviors doesn't seem totally unreasonable, while still having central handling? (or having variants "demangleLifetimeForGenericArg", etc)

[tmiasko]

Rename demangleBinder into demangleOptionalBinder

[tmiasko]

Rerun build

llvm/include/llvm/Demangle/RustDemangle.h

enum class InType {
   Yes,
 };
 
 class Demangler {
   // Maximum recursion level. Used to avoid stack overflow.
   size_t MaxRecursionLevel;
   // Current recursion level.
   size_t RecursionLevel;
-
+  size_t BoundLifetimes;
   // Input string that is being demangled with "_R" prefix removed.
   StringView Input;
   // Position in the input string.
   size_t Position;
 
   // When true, print methods append the output to the stream.
   // When false, the output is suppressed.
   bool Print;
public:
   bool demangle(StringView MangledName);
 
 private:
   void demanglePath(InType InType);
   void demangleImplPath(InType InType);
   void demangleGenericArg();
   void demangleType();
   void demangleFnSig();
+  void demangleBinder();
   void demangleConst();
   void demangleConstInt();
   void demangleConstBool();
   void demangleConstChar();
 
   Identifier parseIdentifier();
   uint64_t parseOptionalBase62Number(char Tag);
   uint64_t parseBase62Number();
private:
   void printDecimalNumber(uint64_t N) {
     if (Error || !Print)
       return;
 
     Output << N;
   }
 
   void printBasicType(BasicType);
+  void printLifetime(uint64_t Index);
 
   char look() const {
     if (Error || Position >= Input.size())
       return 0;
 
     return Input[Position];
   }
 

llvm/lib/Demangle/RustDemangle.cpp

 // responsibility of the caller to free the memory behind the output stream.
 //
 // <symbol-name> = "_R" <path> [<instantiating-crate>]
 bool Demangler::demangle(StringView Mangled) {
   Position = 0;
   Error = false;
   Print = true;
   RecursionLevel = 0;
+  BoundLifetimes = 0;
 
   if (!Mangled.consumeFront("_R")) {
     Error = true;
     return false;
   }
   Input = Mangled;
 
   demanglePath(rust_demangle::InType::No);
void Demangler::demangleImplPath(InType InType) {
   demanglePath(InType);
 }
 
 // <generic-arg> = <lifetime>
 //               | <type>
 //               | "K" <const>
 // <lifetime> = "L" <base-62-number>
 void Demangler::demangleGenericArg() {
-  if (consumeIf('K'))
+  if (consumeIf('L'))
+    printLifetime(parseBase62Number());
+  else if (consumeIf('K'))
     demangleConst();
   else
     demangleType();
-  // FIXME demangle lifetimes.
 }
 
 // <basic-type> = "a"      // i8
 //              | "b"      // bool
 //              | "c"      // char
 //              | "d"      // f64
 //              | "e"      // str
 //              | "f"      // f32
for (; !Error && !consumeIf('E'); ++I) {
       demangleType();
     }
     if (I == 1)
       print(",");
     print(")");
     break;
   }
   case 'R':
-    print("&");
-    // FIXME demangle [<lifetime>].
-    demangleType();
-    break;
   case 'Q':
-    print("&mut ");
-    // FIXME demangle [<lifetime>].
+    print('&');
+    if (consumeIf('L')) {
+      if (auto Lifetime = parseBase62Number()) {
+        printLifetime(Lifetime);
+        print(' ');
+      }
+    }
+    if (C == 'Q')
+      print("mut ");
     demangleType();
     break;
   case 'P':
     print("*const ");
     demangleType();
     break;
   case 'O':
     print("*mut ");
     demangleType();
     break;
   case 'F':
     demangleFnSig();
     break;
   default:
     Position = Start;
     demanglePath(rust_demangle::InType::Yes);
     break;
   }
 }
 
 // <fn-sig> := [<binder>] ["U"] ["K" <abi>] {<type>} "E" <type>
 // <abi> = "C"
 //       | <undisambiguated-identifier>
 void Demangler::demangleFnSig() {
-  // FIXME demangle binder.
+  SwapAndRestore<size_t> SaveBoundLifetimes(BoundLifetimes, BoundLifetimes);
+  demangleBinder();
 
   if (consumeIf('U'))
     print("unsafe ");
 
   if (consumeIf('K')) {
     print("extern \"");
     if (consumeIf('C')) {
       print("C");
void Demangler::demangleFnSig() {
   if (consumeIf('u')) {
     // Skip the unit type from the output.
   } else {
     print(" -> ");
     demangleType();
   }
 }
 
+// Demangles optional binder and updates the number of bound lifetimes.
+//
+// <binder> = ["G" <base-62-number>]
+void Demangler::demangleBinder() {
+  uint64_t Binder = parseOptionalBase62Number('G');
+  if (Error || Binder == 0)
+    return;
+
+  // In valid inputs each bound lifetime is referenced later. Referencing a
+  // lifetime requires at least one byte of input. Reject inputs that are too
+  // short to reference all bound lifetimes. Otherwise demangling of invalid
+  // binders could generate excessive amounts of output.
+  if (Binder >= Input.size() - BoundLifetimes) {
+    Error = true;
+    return;
+  }
+
+  print("for<");
+  for (size_t I = 0; I != Binder; ++I) {
+    BoundLifetimes += 1;
+    if (I > 0)
+      print(", ");
+    printLifetime(1);
+  }
+  print("> ");
+}
+
 // <const> = <basic-type> <const-data>
 //         | "p"                          // placeholder
 //         | <backref>
 void Demangler::demangleConst() {
   BasicType Type;
   if (parseBasicType(consume(), Type)) {
     switch (Type) {
     case BasicType::I8:
if (!std::all_of(S.begin(), S.end(), isValid)) {
     Error = true;
     return {};
   }
 
   return {S, Punycode};
 }
 
 // Parses optional base 62 number. The presence of a number is determined using
-// Tag. Returns 0 when tag is absent and parsed value + 1 otherwise.
+// Tag. Returns 0 when tag is absent and parsed value + 1 otherwise
+//
+// This function is indended for parsing disambiguators and binders which when
+// not present have their value interpreted as 0, and otherwise as decoded
+// value + 1. For example for binders, value for "G_" is 1, for "G0_" value is
+// 2. When "G" is absent value is 0.
 uint64_t Demangler::parseOptionalBase62Number(char Tag) {
   if (!consumeIf(Tag))
     return 0;
 
   uint64_t N = parseBase62Number();
   if (Error || !addAssign(N, 1))
     return 0;
 
if (Error) {
     return 0;
   }
 
   size_t End = Position - 1;
   assert(Start < End);
   HexDigits = Input.substr(Start, End - Start);
   return Value;
 }
+
+// Prints a lifetime. An index 0 always represents an erased lifetime. Indices
+// starting from 1, are De Bruijn indices, referring to higher-ranked lifetimes
+// bound by one of the enclosing binders.
+void Demangler::printLifetime(uint64_t Index) {
+  if (Index == 0) {
+    print("'_");
+    return;
+  }
+
+  if (Index - 1 >= BoundLifetimes) {
+    Error = true;
+    return;
+  }
+
+  uint64_t Depth = BoundLifetimes - Index;
+  print('\'');
+  if (Depth < 26) {
+    char C = 'a' + Depth;
+    print(C);
+  } else {
+    print('z');
+    printDecimalNumber(Depth - 26 + 1);
+  }
+}

llvm/test/Demangle/rust.test

 CHECK: generic::<_, _, _>
        _RIC7genericpppE
 
 ; Generic const arguments
 
 CHECK: generic_const::<_>
        _RIC13generic_constKpE
 
+; Generic lifetime arguments
+
+CHECK: generic_lifetime::<'_>
+       _RIC16generic_lifetimeL_E
+
+; Invalid lifetime index.
+
+CHECK: _RIC16generic_lifetimeL0_E
+       _RIC16generic_lifetimeL0_E
+
 ; Basic types
 
 CHECK: basic::<i8>
        _RIC5basicaE
 
 CHECK: basic::<bool>
        _RIC5basicbE
 
CHECK: types::<(_, _)>
        _RIC5typesTppEE
 
 CHECK: types::<(_, _, _)>
        _RIC5typesTpppEE
 
 CHECK: types::<&_>
        _RIC5typesRpE
 
+CHECK: types::<&_>
+       _RIC5typesRL_pE
+
 CHECK: types::<&mut _>
        _RIC5typesQpE
 
+CHECK: types::<&mut _>
+       _RIC5typesQL_pE
+
 CHECK: types::<*const _>
        _RIC5typesPpE
 
 CHECK: types::<*mut _>
        _RIC5typesOpE
 
 ; Function signatures
 
CHECK: function::<extern "C" fn()>
        _RIC8functionFKCEuE
 
 CHECK: function::<extern "cdecl" fn()>
        _RIC8functionFK5cdeclEuE
 
 CHECK: function::<unsafe extern "C-cmse-nonsecure-call" fn()>
        _RIC8functionFUK21C_cmse_nonsecure_callEuE
 
+; Binders
+
+CHECK: binders::<for<'a> fn(&'a _)>
+       _RIC7bindersFG_RL0_pEuE
+
+CHECK: binders::<for<'a> fn(&'a mut _)>
+       _RIC7bindersFG_QL0_pEuE
+
+CHECK: binders::<for<'a, 'b> fn(&'a _, &'b _)>
+       _RIC7bindersFG0_RL1_pRL0_pEuE
+
+CHECK: binders::<for<'a, 'b> fn() -> for<'c, 'd> fn(&'a _, &'d _)>
+       _RIC7bindersFG0_EFG0_RL3_pRL0_pEuE
+
+CHECK: binders::<for<'a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'l, 'm, 'n, 'o, 'p, 'q, 'r, 's, 't, 'u, 'v, 'w, 'x, 'y, 'z, 'z1, 'z2, 'z3, 'z4> fn(&'a &'b &'c &'d &'e &'f &'g &'h &'i &'j &'k &'l &'m &'n &'o &'p &'q &'r &'s &'t &'u &'v &'w &'x &'y &'z &'z1 &'z2 &'z3 &'z4 ())>
+       _RIC7bindersFGs_RLt_RLs_RLr_RLq_RLp_RLo_RLn_RLm_RLl_RLk_RLj_RLi_RLh_RLg_RLf_RLe_RLd_RLc_RLb_RLa_RL9_RL8_RL7_RL6_RL5_RL4_RL3_RL2_RL1_RL0_uEuE
+
+; Invalid binder. Too many bound lifetimes.
+
+CHECK: _RIC7bindersFGFF_EuE
+       _RIC7bindersFGFF_EuE
+
 ; Integer constants. Test value demangling.
 
 CHECK: integer::<0>
        _RIC7integerKi0_E
 
 CHECK: integer::<1>
        _RIC7integerKi1_E