[Demangle][Rust] Print special namespaces

[dblaikie]

Any chance this could be subdivided further to implement only one grammar rule or the like? It'd make it much easier to inspect the test quality with smaller increments like that.

llvm/include/llvm/Demangle/RustDemangle.h

83–84

We tend not to use 'const' on locals, and maybe especially not on parameters (since it's even more readily confused with const-ref on parameters).

llvm/lib/Demangle/RustDemangle.cpp

268–309

This whole thing is alphabetic except for 'p' - maybe put it in order?

Also - maybe use a const char* array indexed on C - 'a'? Not necessary by any means, though.

328–357

Perhaps the recursion system could be a scoped device, making it easier to add/less error-prone in case of early returns, etc?

Recurse R(Error, RecursionLimit); // or just take *this and befriend for access to Error and RecursionLimit
if (!R)
  return;
// Recurse's dtor decrements the RecursionLimit)

[tmiasko]

• Limit changes to M / X / Y path productions
• Use SwapAndRestore for recursion limit, printing mode, and parser position.

[tmiasko]

Update description

[dblaikie]

Could this be cut down further to be paths OR named types, rather than both? (I know this seems fussy/like a pain & I'm sorry about that - but if it gets down to the smallest thing possible (like adding only one named type and associated tests) I'm hoping it'll be super easy to review and verify the tests/understand how the grammar is implemented, etc - as it stands currently it does take me a while to understand each test case, which set of grammar rules are being tested relative to which different rules are being implemented in the patch, etc)

[tmiasko]

Print special namespaces

[tmiasko]

In D101821#2745300, @dblaikie wrote:

Could this be cut down further to be paths OR named types, rather than both?

I reduced the changes further still. To introduce further path productions I need types, and the one already implemented type is a named type, i.e., a path. Grammar limits how much I can break it down, but I will see what I can do.

[dblaikie]

llvm/test/Demangle/rust.test

14–25

Do these benefit from being inside two namespaces? I think it'd be great if features were tested as much in isolation as possible, with maybe a single test demonstrating that a feature works in a particular context (which is really testing the outer production - and should used the simplest instance of the inner production as possible).

There's also a rather large and, so far as I can tell, arbitrary, disambiguator ('s21hi0yVfW1J') - is there a particular reason for that being present, and having such a long/complicated value?

ie, maybe these tests could be:

_RNCC5crate0
_RNCC5crates_0
_RNCNCC5crates_00
_RNCNCC5crates_01g

& I'm still thinking maybe some kind of comment would be useful to describe these things, though I'm not sure exactly what.

_R N [ C [ C 5crate ] 0 ]
_R N [ C [ C 5crate ] [ s _0 ] ]
_R N [ C [ N [ C [ C 5crate ] [ s _0 ] ] ] 0 ]

In any case - could you simplify down the test cases to make them as narrow and legible/obvious as possible? Maybe add some comments about the invalid/mangled cases - where the invalidity is interesting, for instance? But hopefully if they're simplified way down, the invalidity will be more clear/obvious?

[tmiasko]

Simplify test cases

llvm/test/Demangle/rust.test

14–25

I used rustc to generate the test cases previously. The extra nesting is necessary at language level. The long disambiguator s21hi0yVfW1J is a crate hash. Together with a crate name it forms a unique global identifier of the crate (c++filt shows / omits those hashes output based on -i flag, and I would like to implement something similar later on).

Neither of those aspect is strictly necessary for testing, so I reduced the test cases, but they no longer correspond to valid Rust programs.

[dblaikie]

Looks great - thanks for sticking with me/helping make this easier for me to follow.

llvm/test/Demangle/rust.test

33–34

Might be worth consistently using certain easy to identify identifiers? (I at least find it easier to understand the tests when the identifiers are readily.. identifiable - 'crate' is easy to spot in the other examples, for instance - but in an example with single letter identifiers like this ('a' and 'c') can make it a bit harder to read the example - knowing where the user-provided names start/end, which parts aren't from the user identifier)

(similarly below in the invalid namespace)

I guess in the first few examples the manglings were short/simple enough for me to figure out which component was from what - but as the examples get more complicated it's a bit harder to follow/understand and maybe clearer/long/obvious names would make it a bit easier.

[tmiasko]

Use easy to distinguish identifiers in test cases

Could you commit this for me? Thanks.

llvm/include/llvm/Demangle/RustDemangle.h

 //===--- RustDemangle.h -----------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DEMANGLE_RUSTDEMANGLE_H
 #define LLVM_DEMANGLE_RUSTDEMANGLE_H
 
 #include "llvm/Demangle/DemangleConfig.h"
 #include "llvm/Demangle/StringView.h"
 #include "llvm/Demangle/Utility.h"
+#include <cstdint>
 
 namespace llvm {
 namespace rust_demangle {
 
 using llvm::itanium_demangle::OutputStream;
 using llvm::itanium_demangle::StringView;
+using llvm::itanium_demangle::SwapAndRestore;
 
 struct Identifier {
   StringView Name;
   bool Punycode;
 
   bool empty() const { return Name.empty(); }
 };
 
 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;
   // 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;
+
   // True if an error occurred.
   bool Error;
 
 public:
   // Demangled output.
   OutputStream Output;
 
   Demangler(size_t MaxRecursionLevel = 500);
 
   bool demangle(StringView MangledName);
 
 private:
   void demanglePath();
+  void demangleImplPath();
+  void demangleType();
+
+  // <backref> = "B" <base-62-number>
+  template <typename Callable> void demangleBackref(Callable Demangler) {
+    uint64_t Backref = parseBase62Number();
+    if (Error || Backref >= Position) {
+      Error = true;
+      return;
+    }
+
+    if (!Print)
+      return;
+
+    SwapAndRestore<size_t> SavePosition(Position, Backref);
+    Demangler();
+  }
 
   Identifier parseIdentifier();
-  void parseOptionalBase62Number(char Tag);
+  uint64_t parseOptionalBase62Number(char Tag);
   uint64_t parseBase62Number();
   uint64_t parseDecimalNumber();
 
+  void print(char C) {
+    if (Error || !Print)
+      return;
+
+    Output += C;
+  }
+
   void print(StringView S) {
-    if (Error)
+    if (Error || !Print)
       return;
 
     Output += S;
   }
 
+  void printDecimalNumber(uint64_t N) {
+    if (Error || !Print)
+      return;
+
+    Output << N;
+  }
+
   char look() const {
     if (Error || Position >= Input.size())
       return 0;
 
     return Input[Position];
   }
 
   char consume() {

llvm/lib/Demangle/RustDemangle.cpp

 
 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 == '_';
 }
 
+/// Returns true if C starts a <path>.
+static inline bool isPath(char C) {
+  switch (C) {
+  case 'C':
+  case 'M':
+  case 'X':
+  case 'Y':
+  case 'N':
+  case 'I':
+  case 'B':
+    return true;
+  default:
+    return false;
+  }
+}
+
 // Demangles Rust v0 mangled symbol. Returns true when successful, and false
 // otherwise. The demangled symbol is stored in Output field. It is
 // responsibility of the caller to free the memory behind the output stream.
 //
 // <symbol-name> = "_R" <path> [<instantiating-crate>]
+// <instantiating-crate> = <path>
 bool Demangler::demangle(StringView Mangled) {
+  Print = true;
   Position = 0;
   Error = false;
   RecursionLevel = 0;
 
   if (!Mangled.consumeFront("_R")) {
     Error = true;
     return false;
   }
   Input = Mangled;
 
   demanglePath();
 
-  // FIXME parse optional <instantiating-crate>.
+  if (isPath(look())) {
+    SwapAndRestore<bool> SavePrint(Print, false);
+    demanglePath();
+  }
 
   if (Position != Input.size())
     Error = true;
 
   return !Error;
 }
 
+// Demangles a path.
+//
 // <path> = "C" <identifier>               // crate root
 //        | "M" <impl-path> <type>         // <T> (inherent impl)
 //        | "X" <impl-path> <type> <path>  // <T as Trait> (trait impl)
 //        | "Y" <type> <path>              // <T as Trait> (trait definition)
 //        | "N" <ns> <path> <identifier>   // ...::ident (nested path)
 //        | "I" <path> {<generic-arg>} "E" // ...<T, U> (generic args)
 //        | <backref>
 // <identifier> = [<disambiguator>] <undisambiguated-identifier>
 // <ns> = "C"      // closure
 //      | "S"      // shim
 //      | <A-Z>    // other special namespaces
 //      | <a-z>    // internal namespaces
 void Demangler::demanglePath() {
   if (Error || RecursionLevel >= MaxRecursionLevel) {
     Error = true;
     return;
   }
-  RecursionLevel += 1;
+  SwapAndRestore<size_t> SaveRecursionLevel(RecursionLevel, RecursionLevel + 1);
 
   switch (consume()) {
   case 'C': {
     parseOptionalBase62Number('s');
     Identifier Ident = parseIdentifier();
     print(Ident.Name);
     break;
   }
+  case 'M': {
+    demangleImplPath();
+    print('<');
+    demangleType();
+    print('>');
+    break;
+  }
+  case 'X': {
+    demangleImplPath();
+    print('<');
+    demangleType();
+    print(" as ");
+    demanglePath();
+    print('>');
+    break;
+  }
+  case 'Y': {
+    print('<');
+    demangleType();
+    print(" as ");
+    demanglePath();
+    print('>');
+    break;
+  }
   case 'N': {
     char NS = consume();
     if (!isLower(NS) && !isUpper(NS)) {
       Error = true;
       break;
     }
     demanglePath();
 
-    parseOptionalBase62Number('s');
+    uint64_t Disambiguator = parseOptionalBase62Number('s');
     Identifier Ident = parseIdentifier();
 
+    if (isUpper(NS)) {
+      // Special namespaces
+      print("::{");
+      if (NS == 'C')
+        print("closure");
+      else if (NS == 'S')
+        print("shim");
+      else
+        print(NS);
+      if (!Ident.empty()) {
+        print(":");
+        print(Ident.Name);
+      }
+      print('#');
+      printDecimalNumber(Disambiguator);
+      print('}');
+    } else {
+      // Implementation internal namespaces.
       if (!Ident.empty()) {
-      // FIXME print special namespaces:
-      // * "C" closures
-      // * "S" shim
         print("::");
         print(Ident.Name);
       }
+    }
+    break;
+  }
+  case 'B': {
+    demangleBackref([&] { demanglePath(); });
     break;
   }
   default:
-    // FIXME parse remaining productions.
+    // FIXME parse remaining production.
     Error = true;
     break;
   }
+}
 
-  RecursionLevel -= 1;
+// <impl-path> = [<disambiguator>] <path>
+// <disambiguator> = "s" <base-62-number>
+void Demangler::demangleImplPath() {
+  SwapAndRestore<bool> SavePrint(Print, false);
+  parseOptionalBase62Number('s');
+  demanglePath();
 }
 
+// <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() { demanglePath(); }
+
 // <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.
-void Demangler::parseOptionalBase62Number(char Tag) {
-  // Parsing result is currently unused.
-  if (consumeIf(Tag))
-    parseBase62Number();
+// 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
 // "_". All values are offset by 1, so that "_" encodes 0, "0_" encodes 1,
 // "1_" encodes 2, etc.
 //
 // <base-62-number> = {<0-9a-zA-Z>} "_"
 uint64_t Demangler::parseBase62Number() {
   if (consumeIf('_'))
     return 0;
 
   uint64_t Value = 0;
 
   while (true) {
     uint64_t Digit;
     char C = consume();
 
     if (C == '_') {
       break;
     } else if (isDigit(C)) {
       Digit = C - '0';
     } else if (isLower(C)) {
       Digit = 10 + (C - 'a');
     } else if (isUpper(C)) {
       Digit = 10 + 26 + (C - 'A');
     } else {
       Error = true;
       return 0;
     }
 
     if (!mulAssign(Value, 62))
       return 0;
 
     if (!addAssign(Value, Digit))
       return 0;
   }
 
   if (!addAssign(Value, 1))
     return 0;
 
   return Value;
 }
 
 // Parses a decimal number that had been encoded without any leading zeros.
 //
 // <decimal-number> = "0"
 //                  | <1-9> {<0-9>}
 uint64_t Demangler::parseDecimalNumber() {
   char C = look();
   if (!isDigit(C)) {
     Error = true;
     return 0;
   }
 
   if (C == '0') {
     consume();
     return 0;
   }
 
   uint64_t Value = 0;
 
   while (isDigit(look())) {
     if (!mulAssign(Value, 10)) {
       Error = true;
       return 0;
     }
 
     uint64_t D = consume() - '0';
     if (!addAssign(Value, D))
       return 0;
   }
 
   return Value;
 }

llvm/test/Demangle/rust.test

 RUN: llvm-cxxfilt -n  < %s | FileCheck --match-full-lines %s
 
 CHECK: a::main
        _RNvC1a4main
 
 CHECK: hello::rust
        _RNvCshGpAVYOtgW1_5hello4rust
 
 CHECK: a::b::c
        _RNvNvC1a1b1c
 
+; Closure namespace
+
+CHECK: ns::f::{closure#0}
+       _RNCNvCs21hi0yVfW1J_2ns1f0B3_
+
+CHECK: ns::f::{closure#1}
+       _RNCNvCs21hi0yVfW1J_2ns1fs_0B3_
+
+CHECK: ns::f::{closure#1}::{closure#0}
+       _RNCNCNvCs21hi0yVfW1J_2ns1fs_00B5_
+
+CHECK: ns::f::{closure#1}::g
+       _RNvNCNvCs21hi0yVfW1J_2ns1fs_01g
+
+; Shim namespace
+
+CHECK: ns::g::{shim:reify#0}
+       _RNSNvCshGpAVYOtgW1_2ns1g5reifyB3_
+
+; Unrecognized special namespace
+
+CHECK: a::{B:c#10}
+       _RNBC1as8_1c
+
+; Inherent impl
+
+CHECK: <p::SmallStr>::new
+       _RNvMCshGpAVYOtgW1_1pNtB2_8SmallStr3new
+
+CHECK: <p::SmallStr>::len
+       _RNvMs_CshGpAVYOtgW1_1pNtB4_8SmallStr3len
+
+; Trait definition
+
+CHECK: <p::SmallStr as core::cmp::Ord>::max
+       _RNvYNtCshGpAVYOtgW1_1p8SmallStrNtNtCskrsM4FCwAVA_4core3cmp3Ord3maxB4_
+
+CHECK: <p::SmallStr as core::clone::Clone>::clone_from
+       _RNvYNtCshGpAVYOtgW1_1p8SmallStrNtNtCskrsM4FCwAVA_4core5clone5Clone10clone_fromB4_
+
+; Trait impl
+
+CHECK: <p::SmallStr as core::default::Default>::default
+       _RNvXs1_CshGpAVYOtgW1_1pNtB5_8SmallStrNtNtCskrsM4FCwAVA_4core7default7Default7defaultB5_
+
+CHECK: <p::SmallStr as core::str::traits::FromStr>::from_str
+       _RNvXCshGpAVYOtgW1_1pNtB2_8SmallStrNtNtNtCskrsM4FCwAVA_4core3str6traits7FromStr8from_str
+
 ; Invalid mangled characters
 
 CHECK: _RNvC2a.1c
        _RNvC2a.1c
 
 CHECK: _RNvC2a$1c
        _RNvC2a$1c
 
+CHECK: _RNvCs._1a1b
+       _RNvCs._1a1b
+
+; Invalid namespace
+
+CHECK: _RNvN_NvC2ns1i01f
+       _RNvN_NvC2ns1i01f
+
 ; Invalid identifier length (UINT64_MAX + 3, which happens to be ok after a wraparound).
 
 CHECK: _RNvC2ab18446744073709551618xy
        _RNvC2ab18446744073709551618xy
 
 ; Mangling scheme includes an optional encoding version. When present it would
 ; indicate an encoding we don't support yet. Check that it is rejected:
 
 CHECK: _R0NvC1a4main
        _R0NvC1a4main
 
 ; Early EOF
 
 CHECK: _RNv
        _RNv
 
 CHECK: _RNvC
        _RNvC
 
 CHECK: _RNvC1a5main
        _RNvC1a5main
 
 CHECK: _RNvC1a20abc
        _RNvC1a20abc
+
+; Invalid backreferences
+
+CHECK: _RB_
+       _RB_
+
+CHECK: _RB9_
+       _RB9_
+
+CHECK: _RB_1a
+       _RB_1a
+
+CHECK: _RB_RMRX
+       _RB_RMRX
+
+CHECK: _RNvNvB_1a1b1c
+       _RNvNvB_1a1b1c
+
+CHECK: _RINvCshGpAVYOtgW1_1a1fTlllEB_EB2_
+       _RINvCshGpAVYOtgW1_1a1fTlllEB_EB2_