[Demangle][Rust] Parse integer constants

[dblaikie]

llvm/lib/Demangle/RustDemangle.cpp

207–212

Previous code didn't have an error path for this missing piece - any particular reason to add it now (& thus have to test it) compared to not supporting this & having const or type as the only options (& if it's not const, parse it as a type - as the previous code did, parsing everything as a type regardless)

427

Somewhat surprising that though this production uses <basic-type> but the implementation doesn't call parseBasicType - any chance of sharing that implementation detail, trivial as it is?

458

grammar production comment for this?

466–471

switching between int and decimal for the demangling seems like it could be problematic for readers/parsers/etc, maybe? (what does llvm-cxxfilt do for equivalent C++ numbered values (like integer template parameters))

Maybe APSInt could be used which supports bigger (though not arbitrarily big, I don't think... - I think you have to pick the size, though I guess you could pick it dynamically based on the number of hex digits) integers.

llvm/test/Demangle/rust.test

151–185

Do these benefit from the second parameter that shows the type? Or is the type testing redundant with the existing type testing added in the previous patch?

[pirama]

@tmiasko Thanks for adding this support to llvm. We're already using your work in Android. Can you comment on the status of this support? For e.g., I see that the following name is not demangled:

_RNvYNtNtNtCs7WMZDM8jTtQ_10env_logger3fmt6writer6TargetNtNtCsfOHkQPwunBC_4core3cmp9PartialEq2neB8_.

This symbol is generated with rust 1.51 with -Z symbol-mangling-version=v0

[tmiasko]

Address review comments

• Add an basic type enum & reuse basic type parsing.
• Use APInt to format all const integers as decimals.

llvm/lib/Demangle/RustDemangle.cpp

207–212

No particular reason. I reverted the changes so that code falls back to the type production as before.

427

I introduced an enum for a basic types and reused the parsing code. What do you think?

466–471

I used APInt to consistently format values as decimals. This matches rustc pretty printing which consistently uses decimal as well.

In itanium this is non-issue since values have decimal mangling.

llvm/test/Demangle/rust.test

151–185

I included a type argument in addition to a const integer value, so that demangled from clearly indicates what type is being tested, and to visually distinguish checks from each other (in case one of them fails for example).

[tmiasko]

@pirama path productions which are necessary to demangle most symbols are not implemented yet. I can let you know the implementation is complete. At that point any reports about not demangled symbols would be quite valuable.

[dblaikie]

llvm/lib/Demangle/RustDemangle.cpp

427

Looks pretty good - if you like, you could commit that as a preliminary refactoring-only commit. (might be a good point to follow the steps to get commit access for changes like this)

438–440

Hmm - I'm just realizing that it looks like the demangle library has no dependencies on the rest of LLVM (the StringView type was a hint I saw earlier - but now looking more closely).

I'm guessing that's intentional & I'm surprised this code links successfully - I'd expect some part of SmallString or APInt would have some link-time dependence on the rest of LLVM, which I think (looking at the CMake file at least) there's no dependency on from the demangle library? Hmm, maybe llvm-cxxfilt has such a dependency and it's being picked up by accident (are you using lld or a windows linker, by chance? Those will be a bit more flexible about fulfilling library dependencies, perhaps).

So maybe we'll have to stick with the previous implementation you had here :/ (if so, might be worth a comment explaining why - though I don't immediately know where this constraint for libDemangle is documented/comes from - could you check around a bit in the library/version control history, maybe?)

llvm/test/Demangle/rust.test

151–185

perhaps rather than relying on the type encoding to test the integer encoding, the type could be rendered in the name (replacing the "integer" string) instead? (though that may be harder to read in the mangling - maybe not though)

[tmiasko]

llvm/lib/Demangle/RustDemangle.cpp

438–440

The code of Itanium demangler (ItaniumDemangle.h, DemangleConfig.h, StringView.h, and Utility.h) is shared with libcxxabi. The initial commit that introduced demangler to LLVM, comments:

The code also has no dependencies on anything else in LLVM. To enforce
that I added it as another library. That way a BUILD_SHARED_LIBS will
fail if anyone adds an use of StringRef for example.

The build with BUILD_SHARED_LIBS does indeed fail.

The implementation of the Itanium demangler itself cannot any dependencies, but it seems to me that we could add them to the demangler component. I don't know if we want to do that. Functionally wise, the difference is rather minor. Apart from APInt used here, I was potentially looking into using unicode::isPrintable when demangling char constants.

[tmiasko]

• Remove dependencies from implementation.
• Show integer constants wider than 64-bits as hexadecimal numbers.
• Include integer types in non-mangled form in tests

[dblaikie]

Seems good, thanks!

llvm/lib/Demangle/RustDemangle.cpp

553–555

Might be worth a more formal description here, something like:

The return value is unspecified if HexDigits.size() > 16.

(so you can't even rely on the return value being zero, maximum, or some other default value - it's arbitrary/meaningless)

llvm/include/llvm/Demangle/RustDemangle.h

 
 struct Identifier {
   StringView Name;
   bool Punycode;
 
   bool empty() const { return Name.empty(); }
 };
 
+enum class BasicType {
+  Bool,
+  Char,
+  I8,
+  I16,
+  I32,
+  I64,
+  I128,
+  ISize,
+  U8,
+  U16,
+  U32,
+  U64,
+  U128,
+  USize,
+  F32,
+  F64,
+  Str,
+  Placeholder,
+  Unit,
+  Variadic,
+  Never,
+};
+
 class Demangler {
   // Maximum recursion level. Used to avoid stack overflow.
   size_t MaxRecursionLevel;
   // Current recursion level.
   size_t RecursionLevel;
 
   // Input string that is being demangled with "_R" prefix removed.
   StringView Input;
public:
   Demangler(size_t MaxRecursionLevel = 500);
 
   bool demangle(StringView MangledName);
 
 private:
   void demanglePath();
   void demangleGenericArg();
   void demangleType();
+  void demangleConst();
+  void demangleConstInt();
 
   Identifier parseIdentifier();
   uint64_t parseOptionalBase62Number(char Tag);
   uint64_t parseBase62Number();
   uint64_t parseDecimalNumber();
+  uint64_t parseHexNumber(StringView &HexDigits);
 
   void print(char C) {
     if (Error)
       return;
 
     Output += C;
   }
 
   void print(StringView S) {
     if (Error)
       return;
 
     Output += S;
   }
 
   void printDecimalNumber(uint64_t N) {
     if (Error)
       return;
 
     Output << N;
   }
 
+  void printBasicType(BasicType);
+
   char look() const {
     if (Error || Position >= Input.size())
       return 0;
 
     return Input[Position];
   }
 
   char consume() {

llvm/lib/Demangle/RustDemangle.cpp

char *llvm::rustDemangle(const char *MangledName, char *Buf, size_t *N,
   return Demangled;
 }
 
 Demangler::Demangler(size_t MaxRecursionLevel)
     : MaxRecursionLevel(MaxRecursionLevel) {}
 
 static inline bool isDigit(const char C) { return '0' <= C && C <= '9'; }
 
+static inline bool isHexDigit(const char C) {
+  return ('0' <= C && C <= '9') || ('a' <= C && C <= 'f');
+}
+
 static inline bool isLower(const char C) { return 'a' <= C && C <= 'z'; }
 
 static inline bool isUpper(const char C) { return 'A' <= C && C <= 'Z'; }
 
 /// Returns true if C is a valid mangled character: <0-9a-zA-Z_>.
 static inline bool isValid(const char C) {
   return isDigit(C) || isLower(C) || isUpper(C) || C == '_';
 }
void Demangler::demanglePath() {
   }
 }
 
 // <generic-arg> = <lifetime>
 //               | <type>
 //               | "K" <const>
 // <lifetime> = "L" <base-62-number>
 void Demangler::demangleGenericArg() {
-  // FIXME parse remaining productions
+  if (consumeIf('K'))
+    demangleConst();
+  else
     demangleType();
+  // FIXME demangle lifetimes.
 }
 
-static const char *const BasicTypes[] = {
-    "i8",    // a
-    "bool",  // b
-    "char",  // c
-    "f64",   // d
-    "str",   // e
-    "f32",   // f
-    nullptr, // g
-    "u8",    // h
-    "isize", // i
-    "usize", // j
-    nullptr, // k
-    "i32",   // l
-    "u32",   // m
-    "i128",  // n
-    "u128",  // o
-    "_",     // p
-    nullptr, // q
-    nullptr, // r
-    "i16",   // s
-    "u16",   // t
-    "()",    // u
-    "...",   // v
-    nullptr, // w
-    "i64",   // x
-    "u64",   // y
-    "!",     // z
-};
-
 // <basic-type> = "a"      // i8
 //              | "b"      // bool
 //              | "c"      // char
 //              | "d"      // f64
 //              | "e"      // str
 //              | "f"      // f32
 //              | "h"      // u8
 //              | "i"      // isize
 //              | "j"      // usize
 //              | "l"      // i32
 //              | "m"      // u32
 //              | "n"      // i128
 //              | "o"      // u128
 //              | "s"      // i16
 //              | "t"      // u16
 //              | "u"      // ()
 //              | "v"      // ...
 //              | "x"      // i64
 //              | "y"      // u64
 //              | "z"      // !
 //              | "p"      // placeholder (e.g. for generic params), shown as _
-static const char *parseBasicType(char C) {
-  if (isLower(C))
-    return BasicTypes[C - 'a'];
-  return nullptr;
+static bool parseBasicType(char C, BasicType &Type) {
+  switch (C) {
+  case 'a':
+    Type = BasicType::I8;
+    return true;
+  case 'b':
+    Type = BasicType::Bool;
+    return true;
+  case 'c':
+    Type = BasicType::Char;
+    return true;
+  case 'd':
+    Type = BasicType::F64;
+    return true;
+  case 'e':
+    Type = BasicType::Str;
+    return true;
+  case 'f':
+    Type = BasicType::F32;
+    return true;
+  case 'h':
+    Type = BasicType::U8;
+    return true;
+  case 'i':
+    Type = BasicType::ISize;
+    return true;
+  case 'j':
+    Type = BasicType::USize;
+    return true;
+  case 'l':
+    Type = BasicType::I32;
+    return true;
+  case 'm':
+    Type = BasicType::U32;
+    return true;
+  case 'n':
+    Type = BasicType::I128;
+    return true;
+  case 'o':
+    Type = BasicType::U128;
+    return true;
+  case 'p':
+    Type = BasicType::Placeholder;
+    return true;
+  case 's':
+    Type = BasicType::I16;
+    return true;
+  case 't':
+    Type = BasicType::U16;
+    return true;
+  case 'u':
+    Type = BasicType::Unit;
+    return true;
+  case 'v':
+    Type = BasicType::Variadic;
+    return true;
+  case 'x':
+    Type = BasicType::I64;
+    return true;
+  case 'y':
+    Type = BasicType::U64;
+    return true;
+  case 'z':
+    Type = BasicType::Never;
+    return true;
+  default:
+    return false;
+  }
+}
+
+void Demangler::printBasicType(BasicType Type) {
+  switch (Type) {
+  case BasicType::Bool:
+    print("bool");
+    break;
+  case BasicType::Char:
+    print("char");
+    break;
+  case BasicType::I8:
+    print("i8");
+    break;
+  case BasicType::I16:
+    print("i16");
+    break;
+  case BasicType::I32:
+    print("i32");
+    break;
+  case BasicType::I64:
+    print("i64");
+    break;
+  case BasicType::I128:
+    print("i128");
+    break;
+  case BasicType::ISize:
+    print("isize");
+    break;
+  case BasicType::U8:
+    print("u8");
+    break;
+  case BasicType::U16:
+    print("u16");
+    break;
+  case BasicType::U32:
+    print("u32");
+    break;
+  case BasicType::U64:
+    print("u64");
+    break;
+  case BasicType::U128:
+    print("u128");
+    break;
+  case BasicType::USize:
+    print("usize");
+    break;
+  case BasicType::F32:
+    print("f32");
+    break;
+  case BasicType::F64:
+    print("f64");
+    break;
+  case BasicType::Str:
+    print("str");
+    break;
+  case BasicType::Placeholder:
+    print("_");
+    break;
+  case BasicType::Unit:
+    print("()");
+    break;
+  case BasicType::Variadic:
+    print("...");
+    break;
+  case BasicType::Never:
+    print("!");
+    break;
+  }
 }
 
 // <type> = | <basic-type>
 //          | <path>                      // named type
 //          | "A" <type> <const>          // [T; N]
 //          | "S" <type>                  // [T]
 //          | "T" {<type>} "E"            // (T1, T2, T3, ...)
 //          | "R" [<lifetime>] <type>     // &T
 //          | "Q" [<lifetime>] <type>     // &mut T
 //          | "P" <type>                  // *const T
 //          | "O" <type>                  // *mut T
 //          | "F" <fn-sig>                // fn(...) -> ...
 //          | "D" <dyn-bounds> <lifetime> // dyn Trait<Assoc = X> + Send + 'a
 //          | <backref>                   // backref
 void Demangler::demangleType() {
-  if (const char *BasicType = parseBasicType(consume())) {
-    print(BasicType);
+  BasicType Type;
+  if (parseBasicType(consume(), Type))
+    printBasicType(Type);
+  else
+    Error = true; // FIXME parse remaining productions.
+}
+
+// <const> = <basic-type> <const-data>
+//         | "p"                          // placeholder
+//         | <backref>
+void Demangler::demangleConst() {
+  BasicType Type;
+  if (parseBasicType(consume(), Type)) {
+    switch (Type) {
+    case BasicType::I8:
+    case BasicType::I16:
+    case BasicType::I32:
+    case BasicType::I64:
+    case BasicType::I128:
+    case BasicType::ISize:
+    case BasicType::U8:
+    case BasicType::U16:
+    case BasicType::U32:
+    case BasicType::U64:
+    case BasicType::U128:
+    case BasicType::USize:
+      demangleConstInt();
+      break;
+    case BasicType::Placeholder:
+      print('_');
+      break;
+    default:
+      // FIXME demangle backreferences, bool constants, and char constants.
+      Error = true;
+      break;
+    }
   } else {
-    // FIXME parse remaining productions.
     Error = true;
   }
 }
 
+// <const-data> = ["n"] <hex-number>
+void Demangler::demangleConstInt() {
+  if (consumeIf('n'))
+    print('-');
+
+  StringView HexDigits;
+  uint64_t Value = parseHexNumber(HexDigits);
+  if (HexDigits.size() <= 16) {
+    printDecimalNumber(Value);
+  } else {
+    print("0x");
+    print(HexDigits);
+  }
+}
+
 // <undisambiguated-identifier> = ["u"] <decimal-number> ["_"] <bytes>
 Identifier Demangler::parseIdentifier() {
   bool Punycode = consumeIf('u');
   uint64_t Bytes = parseDecimalNumber();
 
   // Underscore resolves the ambiguity when identifier starts with a decimal
   // digit or another underscore.
   consumeIf('_');
 
   if (Error || Bytes > Input.size() - Position) {
     Error = true;
     return {};
   }
   StringView S = Input.substr(Position, Bytes);
   Position += Bytes;
 
   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.
 uint64_t Demangler::parseOptionalBase62Number(char Tag) {
   if (!consumeIf(Tag))
     return 0;
 
   uint64_t N = parseBase62Number();
   if (Error || !addAssign(N, 1))
     return 0;
 
   return N;
 }
 
 // Parses base 62 number with <0-9a-zA-Z> as digits. Number is terminated by
while (isDigit(look())) {
 
     uint64_t D = consume() - '0';
     if (!addAssign(Value, D))
       return 0;
   }
 
   return Value;
 }
+
+// Parses a hexadecimal number with <0-9a-f> as a digits. Returns the parsed
+// value and stores hex digits in HexDigits. The return value is unspecified if
+// HexDigits.size() > 16.
+//
+// <hex-number> = "0_"
+//              | <1-9a-f> {<0-9a-f>} "_"
+uint64_t Demangler::parseHexNumber(StringView &HexDigits) {
+  size_t Start = Position;
+  uint64_t Value = 0;
+
+  if (!isHexDigit(look()))
+    Error = true;
+
+  if (consumeIf('0')) {
+    if (!consumeIf('_'))
+      Error = true;
+  } else {
+    while (!Error && !consumeIf('_')) {
+      char C = consume();
+      Value *= 16;
+      if (isDigit(C))
+        Value += C - '0';
+      else if ('a' <= C && C <= 'f')
+        Value += 10 + (C - 'a');
+      else
+        Error = true;
+    }
+  }
+
+  if (Error) {
+    HexDigits = StringView();
+    return 0;
+  }
+
+  size_t End = Position - 1;
+  assert(Start < End);
+  HexDigits = Input.substr(Start, End - Start);
+  return Value;
+}

llvm/test/Demangle/rust.test

CHECK: generic::<_>
        _RIC7genericpE
 
 CHECK: generic::<_, _>
        _RIC7genericppE
 
 CHECK: generic::<_, _, _>
        _RIC7genericpppE
 
+; Generic const arguments
+
+CHECK: generic_const::<_>
+       _RIC13generic_constKpE
+
 ; Basic types
 
 CHECK: basic::<i8>
        _RIC5basicaE
 
 CHECK: basic::<bool>
        _RIC5basicbE
 
CHECK: basic::<i64>
        _RIC5basicxE
 
 CHECK: basic::<u64>
        _RIC5basicyE
 
 CHECK: basic::<!>
        _RIC5basiczE
 
+; Integer constants. Test value demangling.
+
+CHECK: integer::<0>
+       _RIC7integerKi0_E
+
+CHECK: integer::<1>
+       _RIC7integerKi1_E
+
+CHECK: integer::<-1>
+       _RIC7integerKin1_E
+
+CHECK: integer::<-15>
+       _RIC7integerKinf_E
+
+CHECK: integer::<-16>
+       _RIC7integerKin10_E
+
+CHECK: integer::<18446744073709551615>
+       _RIC7integerKoffffffffffffffff_E
+
+CHECK: integer::<0x10000000000000000>
+       _RIC7integerKo10000000000000000_E
+
+CHECK: integer::<-0x123456789abcdef01>
+       _RIC7integerKnn123456789abcdef01_E
+
+; Invalid integer constant without any digits:
+
+CHECK: _RIC7integerKi_E
+       _RIC7integerKi_E
+
+; Invalid integer constants with insignificant leading zeros:
+
+CHECK: _RIC7integerKi00_E
+       _RIC7integerKi00_E
+
+CHECK: _RIC7integerKi01_E
+       _RIC7integerKi01_E
+
+; Integer constants. Test all integer types.
+
+CHECK: i8::<0>
+       _RIC2i8Ka0_E
+
+CHECK: u8::<0>
+       _RIC2u8Kh0_E
+
+CHECK: isize::<0>
+       _RIC5isizeKi0_E
+
+CHECK: usize::<0>
+       _RIC5usizeKj0_E
+
+CHECK: i32::<0>
+       _RIC3i32Kl0_E
+
+CHECK: u32::<0>
+       _RIC3u32Km0_E
+
+CHECK: i128::<0>
+       _RIC4i128Kn0_E
+
+CHECK: u128::<0>
+       _RIC4u128Ko0_E
+
+CHECK: i16::<0>
+       _RIC3i16Ks0_E
+
+CHECK: u16::<0>
+       _RIC3u16Kt0_E
+
+CHECK: i64::<0>
+       _RIC3i64Kx0_E
+
+CHECK: u64::<0>
+       _RIC3u64Ky0_E
+
 ; Invalid mangled characters
 
 CHECK: _RNvC2a.1c
        _RNvC2a.1c
 
 CHECK: _RNvC2a$1c
        _RNvC2a$1c