[Demangle][Rust] Parse integer constants

[dblaikie]

llvm/lib/Demangle/RustDemangle.cpp

210–215

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)

407

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?

438

grammar production comment for this?

446–451

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

210–215

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

407

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

446–451

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

407

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)

418–420

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

418–420

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

536–538

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();
+  StringView parseHexNumber();
 
   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

 //===--- RustDemangle.cpp ---------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file defines a demangler for Rust v0 mangled symbols as specified in
 // https://rust-lang.github.io/rfcs/2603-rust-symbol-name-mangling-v0.html
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Demangle/RustDemangle.h"
+#include "llvm/ADT/APInt.h"
+#include "llvm/ADT/Optional.h"
+#include "llvm/ADT/SmallString.h"
 #include "llvm/Demangle/Demangle.h"
 
 #include <algorithm>
 #include <cassert>
 #include <cstring>
 #include <limits>
 
 using namespace llvm;
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 Optional<BasicType> parseBasicType(char C) {
+  switch (C) {
+  case 'a':
+    return BasicType::I8;
+  case 'b':
+    return BasicType::Bool;
+  case 'c':
+    return BasicType::Char;
+  case 'd':
+    return BasicType::F64;
+  case 'e':
+    return BasicType::Str;
+  case 'f':
+    return BasicType::F32;
+  case 'h':
+    return BasicType::U8;
+  case 'i':
+    return BasicType::ISize;
+  case 'j':
+    return BasicType::USize;
+  case 'l':
+    return BasicType::I32;
+  case 'm':
+    return BasicType::U32;
+  case 'n':
+    return BasicType::I128;
+  case 'o':
+    return BasicType::U128;
+  case 'p':
+    return BasicType::Placeholder;
+  case 's':
+    return BasicType::I16;
+  case 't':
+    return BasicType::U16;
+  case 'u':
+    return BasicType::Unit;
+  case 'v':
+    return BasicType::Variadic;
+  case 'x':
+    return BasicType::I64;
+  case 'y':
+    return BasicType::U64;
+  case 'z':
+    return BasicType::Never;
+  default:
+    return None;
+  }
+}
+
+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);
+  if (Optional<BasicType> Type = parseBasicType(consume()))
+    printBasicType(*Type);
+  else
+    Error = true; // FIXME parse remaining productions.
+}
+
+// <const> = <basic-type> <const-data>
+//         | "p"                          // placeholder
+//         | <backref>
+void Demangler::demangleConst() {
+  if (Optional<BasicType> Type = parseBasicType(consume())) {
+    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-digit>} "_"
+void Demangler::demangleConstInt() {
+  if (consumeIf('n'))
+    print('-');
+
+  StringView HexDigits = parseHexNumber();
+  if (Error || HexDigits.size() > 32) {
+    Error = true;
+    return;
+  }
+
+  APInt Value(HexDigits.size() * 4 /* NumBits */,
+              StringRef(HexDigits.begin(), HexDigits.size()), 16 /* Radix */);
+  SmallString<40> Str;
+  Value.toString(Str, 10, false /* Signed */);
+  print(StringView(Str.begin(), Str.end()));
+}
+
 // <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;
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.
+//
+// <hex-number> | "0_"
+//              = <1-9a-f> {<0-9a-f>} "_"
+StringView Demangler::parseHexNumber() {
+  size_t Start = Position;
+
+  if (!isHexDigit(look()))
+    Error = true;
+
+  if (consumeIf('0')) {
+    if (!consumeIf('_'))
+      Error = true;
+  } else {
+    while (!Error && !consumeIf('_'))
+      if (!isHexDigit(consume()))
+        Error = true;
+  }
+
+  if (Error)
+    return StringView();
+
+  size_t End = Position - 1;
+  assert(Start < End);
+  return Input.substr(Start, End - Start);
+}

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
+
+; Integer constant with maximum possible value:
+
+CHECK: integer::<340282366920938463463374607431768211455>
+       _RIC7integerKoffffffffffffffffffffffffffffffff_E
+
+; Integer constant with too many digits:
+
+CHECK: _RIC7integerKo123456789012345678901234567890123_E
+       _RIC7integerKo123456789012345678901234567890123_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: integer::<0, i8>
+       _RIC7integerKa0_aE
+
+CHECK: integer::<0, u8>
+       _RIC7integerKh0_hE
+
+CHECK: integer::<0, isize>
+       _RIC7integerKi0_iE
+
+CHECK: integer::<0, usize>
+       _RIC7integerKj0_jE
+
+CHECK: integer::<0, i32>
+       _RIC7integerKl0_lE
+
+CHECK: integer::<0, u32>
+       _RIC7integerKm0_mE
+
+CHECK: integer::<0, i128>
+       _RIC7integerKn0_nE
+
+CHECK: integer::<0, u128>
+       _RIC7integerKo0_oE
+
+CHECK: integer::<0, i16>
+       _RIC7integerKs0_sE
+
+CHECK: integer::<0, u16>
+       _RIC7integerKt0_tE
+
+CHECK: integer::<0, i64>
+       _RIC7integerKx0_xE
+
+CHECK: integer::<0, u64>
+       _RIC7integerKy0_yE
+
 ; Invalid mangled characters
 
 CHECK: _RNvC2a.1c
        _RNvC2a.1c
 
 CHECK: _RNvC2a$1c
        _RNvC2a$1c