[demangler] Initial support for the new Rust mangling scheme

[tmiasko]

Summary

Add a demangling support for a small subset of a new Rust mangling
scheme, with complete support planned as a follow up work.

Intergate Rust demangling into llvm-cxxfilt and use llvm-cxxfilt for
end-to-end testing. The new Rust mangling scheme uses "_R" as a prefix,
which makes it easy to disambiguate it from other mangling schemes.

The public API is modeled after __cxa_demangle / llvm::itaniumDemangle,
since potential candidates for further integration use those.

[dblaikie]

llvm/include/llvm/Demangle/RustDemangle.h

9

Got a link to a spec for the mangling scheme that could go somewhere up here? (and/or in the .cpp file)

31–32

Most of the LLVM codebase doesn't use const members (can do weird things with assignability, for instance - not that this type needs to be assignable) - so I'd be inclined to stick with that convention and not make this const either.

32

Does the itanium demangler have a similar recursion limit handler? I didn't find one while quickly glancing around - would be good to understand any differences/tradeoffs here.

36

This comment seems incorrect - the demangle function is passed a string that includes the "_R" prefix, and parses that before doing anything else?

50

Looks like this part of the API isn't designed to be drop-in compatible with the itanium demangler API, yeah? (because the itanium one takes the buffer in the ctor rather than in a separate function, and takes the buffer as start/end rather than start/length)

If that's the case - any particular reason for this divergence and if we're diverging anyway, perhaps this could use a StringView parameter type rather than a decomposed start+length?

llvm/lib/Demangle/RustDemangle.cpp

46

If this took the argument by StringView (well, I guess, even if it didn't - could always build a StringView earlier and pass data()+size() here), then the StringView could be constructed earlier and StringView's startsWith(StringView) function could be used for the _R prefix check)

60–63

Any chance of using less raw memory management here? (been some recent discussions about the complexities of memory management in the itanium demangler that, if possible, it'd be good to avoid ( https://reviews.llvm.org/D100800 ) - but if it's all wrapped up in the "wanting to conform to the same API" (ie: the API design itself is awkward, but compatibility trumps fixing that awkwardness) - such is life)

94

The decimal-number and instantiating-crate parts aren't implemented in this patch, I take it? Could you include a FIXME that mentions that?

141–142

Is this correct/am I understanding this correctly, that some parsed components are not rendered in the demangling? Is that intentional/valid - that multiple mangled names could demangle to the same string/be ambiguous? Or is this a case of some feature not being implemented yet?

167–168

LLVM doesn't tend to use const local variables - I'd probably skip the const here & elsewhere.

169

This is here in case the decimal-number and initial bytes value would be ambiguous?

178–183

190

Nothing's currently using (& so nothing's currently testing) the return value of this function - probably best to omit it until it's needed/tested.

208–211

Maybe, like parseDecimalNumber below (though pick either way - so long as they're both the same), it might be nicer to move the 'Value' declaration further down and have this code be if (consume...) { return 0; }?

(though for both cases, if there's some nice way to avoid these special cases & have them fall out of the main loop/algorithm, that'd be even better I think - though I couldn't come up with a way off-hand)

209–211

LLVM style generally omits {} from single line blocks - remove these here and anywhere else in the patch.

238

This particular check could be written maybe more clearly as "Value == Max" but I see it's a pattern for overflow testing - perhaps it could be combined in a utility function for that purposes, so the 1 here matches up with the 1 in the += below. (& used for the "+= D" & overflow check in the next function)

263

This (& similarly in other places) could be constexpr to indicate it's a compile-time constant? (& distinct from the "don't generally use const on locals in LLVM)

264

This one 0 value uses 'u' but most/none of the others do - maybe drop it here for consistency?

284–289

Is this function worth it compared to calling "print(Ident.Name)"? (or at least could/should this function be implemented as "print(Ident.Name)" since the error checking is already done in print(StringView) and doesn't need to be done again in this caller?)

llvm/test/Demangle/rust.test

4–5

I'd have a bit of an easier time following the test cases if there was a comment describing the parse tree - would that be worth including?

26–32

Maybe this comment could be more descriptive - currently the implementation doesn't support any mangling version? (is the plan to support this currently, or is the version field purely forward-looking/for future use?) Maybe the comment could read "Only the null mangling version is currently supported" or something like that?

I'd probably only test 0 if that's the case - doesn't seem like 1 adds especially more coverage? But don't mind.

34–35

This is an attempt to overflow the version number, if it were parsed at all? Not sure it's an interesting test case.

[tmiasko]

address review comments

[tmiasko]

@dblaikie thanks for review!

llvm/include/llvm/Demangle/RustDemangle.h

9

Included a link to a specification in the .cpp file.

32

In Rust mangling scheme, backreferences are given as offsets in the mangled symbol. Without any limits or additional protections, it would be easy to create a symbol that would lead to a stack overflow during demangling. I would consider a recursion limit to be necessary for fuzzing.

As far as I understand this isn't a problem for itanium demangler, where substitutions cannot refer to components that are yet to be demangled. Although the implementation has some form of protection against stack overflow in the form of Printing field.

36

I reorganized the code so that input is assigned only after removing the prefix.

The motivation for this becomes more apparent later; backreferences start from the end of the prefix.

50

I expect that rustDemangle will be the entry point, so there are no compatibility concerns here.

Replaced the arguments with a StringView.

llvm/lib/Demangle/RustDemangle.cpp

60–63

The motivation was to be compatible with itanium demangler API. I feel that interface will be easier to integrate.

If you see trade-offs differently, I am open to changing it to avoid manual memory management. Just consider how a different API would fit in in places where itaniumDemangle is used right now.

Internally, for the demangler itself, it is of little significance if demangled output is appended to an OutputStream or say an std::string.

94

Added a FXIME for <instantiating-crate>, and removed [<decimal-number>] which specification reserves for an encoding version. Encoding version is not in use currently, so there is no reason to parse it.

141–142

Yes, some components are not shown.

In the case here we have two kinds of namespaces: implementation internal namespaces using lowercase letters, and special well-known namespaces using uppercase letters. The former are not intended to be shown. The latter currently includes closures C and shims S and are shown by the existing demanglers.

This is yet to be implemented. I added a FIXME.

169

Exactly. "_" resolves an ambiguity in the case identifier itself starts with a digit or "_". Added a comment reflecting that.

178–183

I would find it convenient to leave this unaddressed for the time being. Currently implementation has no build time dependency on any generated headers or libraries, and using STLExtras.h introduces both.

llvm/test/Demangle/rust.test

4–5

I tried a few different notations, but even for short symbols they feel too verbose to be included in tests. For example:

_RNvNtCshGpAVYOtgW1_1a1b1c 

a::b::c

(symbol-name "_R"
  (path "N" (namespace "v")
    (path "N" (namespace "t")
      (path "C" (identifier (disambiguator "s" (base-62-number "hGpAVYOtgW1_")) "1a"))
      (identifier "1b"))
    (identifier "1c")))

I also have another parser that produces output as below, if that would be helpful I could publish it:

"" <symbol-name>
"_R" [<decimal-number>] <path> [<instantiating-crate>]
"_R" <path> [<instantiating-crate>]
"_R" "N" <namespace> <path> <identifier> [<instantiating-crate>]
"_RN" <namespace> <path> <identifier> [<instantiating-crate>]
"_RNv" <path> <identifier> [<instantiating-crate>]
"_RNv" "N" <namespace> <path> <identifier> <identifier> [<instantiating-crate>]
"_RNvN" <namespace> <path> <identifier> <identifier> [<instantiating-crate>]
"_RNvNt" <path> <identifier> <identifier> [<instantiating-crate>]
"_RNvNt" "C" <identifier> <identifier> <identifier> [<instantiating-crate>]
"_RNvNtC" <identifier> <identifier> <identifier> [<instantiating-crate>]
"_RNvNtC" [<disambiguator>] <undisambiguated-identifier> <identifier> <identifier> [<instantiating-crate>]
"_RNvNtC" ["s" <base-62-number>] <undisambiguated-identifier> <identifier> <identifier> [<instantiating-crate>]
"_RNvNtCs" <base-62-number> <undisambiguated-identifier> <identifier> <identifier> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_" <undisambiguated-identifier> <identifier> <identifier> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_" ["u"] <decimal-number> ["_"] <bytes> <identifier> <identifier> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_" <decimal-number> ["_"] <bytes> <identifier> <identifier> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1" ["_"] <byte> <identifier> <identifier> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1" <byte> <identifier> <identifier> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1a" <identifier> <identifier> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1a" [<disambiguator>] <undisambiguated-identifier> <identifier> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1a" <undisambiguated-identifier> <identifier> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1a" ["u"] <decimal-number> ["_"] <bytes> <identifier> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1a" <decimal-number> ["_"] <bytes> <identifier> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1a1" ["_"] <byte> <identifier> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1a1" <byte> <identifier> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1a1b" <identifier> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1a1b" [<disambiguator>] <undisambiguated-identifier> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1a1b" <undisambiguated-identifier> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1a1b" ["u"] <decimal-number> ["_"] <bytes> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1a1b" <decimal-number> ["_"] <bytes> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1a1b1" ["_"] <byte> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1a1b1" <byte> [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1a1b1c" [<instantiating-crate>]
"_RNvNtCshGpAVYOtgW1_1a1b1c" [<path>]
"_RNvNtCshGpAVYOtgW1_1a1b1c"

26–32

Added a comment explaining the situation with encoding version, and removed other test cases.

[tmiasko]

Add functions for checked arithmetic.

[dblaikie]

llvm/lib/Demangle/RustDemangle.cpp

60–63

Yeah, fair - don't think there's much to do about that, short of some unique_ptr with custom std::freeing deleter (& maybe some utility to do realloc with such a thing), but best not to roll that into this patch - if you wanted to do some cleanup like that, probably implementing it first in the itanium demangler & this common OutputStream abstraction, then port it to the Rust one (either before/after this code is committed).

141–142

I see this notion is referenced in the mangling spec document ("Like other disambiguation information, this path would usually not actually be shown by demanglers.") but this is still quite surprising to me - is there precedent for this, do any itanium or Windows manglings produce ambiguous demanglings?

If there isn't precedent for this, I think it'd be worth having a broader discussion about it (maybe a llvm-dev thread).

178–183

std::all_of can be used instead, if the standard library is suitable here

254–255

Might be worth rolling the Error updating into mulAssign/addAssign? Remove a bit more duplication/chance of mistakes of not setting the Error flag?

llvm/test/Demangle/rust.test

4–5

The hand-rendered version doesn't seem too bad, really - but up to you.

[tmiasko]

Set error directly in mulAssign & addAssign

[tmiasko]

llvm/lib/Demangle/RustDemangle.cpp

141–142

One case in itanium that results in the same f()::a demangling for both
statics, would be the following:

void f() {
  { static int a; }
  { static int a; }
}

The symbols corresponding to constructors & destructors in itanium are
ambiguous after demangling as well.

254–255

I moved responsibility for setting the error into mulAssign/addAssign.

llvm/test/Demangle/rust.test

4–5

I would rather not maintain parse tree for test cases.

But, see https://gist.github.com/tmiasko/7c31853276d94af57c18ca7522badd1c for a parser producing a parse tree.

[dblaikie]

Looks good - thanks!

llvm/lib/Demangle/RustDemangle.cpp

141–142

Oh, right - thanks for the examples!

[tschuett]

Stupid question! Why does the rust demangler has to follow the API of

__cxa_demangle

instead of a modern API with llvm::Error and a BumpPtrAllocator ? Or SmallString and StringRef.

[tmiasko]

In D101444#2732206, @tschuett wrote:

Stupid question! Why does the rust demangler has to follow the API of

__cxa_demangle

instead of a modern API with llvm::Error and a BumpPtrAllocator ? Or SmallString and StringRef.

It is hard to realize the benefits of an improved API when it is inconsistent with API offered by other demanglers (earlier comments regarding API can be found in https://reviews.llvm.org/D101444?id=341152#inline-959049).

I don't have commit access. Could you commit this for me? Thank you.

Tomasz Miąsko <[e-mail]>

llvm/include/llvm/Demangle/Demangle.h

 /// *n_buf stores the size of buf on input if buf is non-nullptr, and it
 /// receives the size of the demangled string on output if n_buf is not nullptr.
 /// status receives one of the demangle_ enum entries above if it's not nullptr.
 /// Flags controls various details of the demangled representation.
 char *microsoftDemangle(const char *mangled_name, size_t *n_read,
                         char *buf, size_t *n_buf,
                         int *status, MSDemangleFlags Flags = MSDF_None);
 
+// Demangles a Rust v0 mangled symbol. The API follows that of __cxa_demangle.
+char *rustDemangle(const char *MangledName, char *Buf, size_t *N, int *Status);
+
 /// Attempt to demangle a string using different demangling schemes.
 /// The function uses heuristics to determine which demangling scheme to use.
 /// \param MangledName - reference to string to demangle.
 /// \returns - the demangled string, or a copy of the input string if no
 /// demangling occurred.
 std::string demangle(const std::string &MangledName);
 
 /// "Partial" demangler. This supports demangling a string into an AST

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"
+
+namespace llvm {
+namespace rust_demangle {
+
+using llvm::itanium_demangle::OutputStream;
+using llvm::itanium_demangle::StringView;
+
+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;
+
+  // True if an error occurred.
+  bool Error;
+
+public:
+  // Demangled output.
+  OutputStream Output;
+
+  Demangler(size_t MaxRecursionLevel = 500);
+
+  bool demangle(StringView MangledName);
+
+private:
+  void demanglePath();
+
+  Identifier parseIdentifier();
+  void parseOptionalBase62Number(char Tag);
+  uint64_t parseBase62Number();
+  uint64_t parseDecimalNumber();
+
+  void print(StringView S) {
+    if (Error)
+      return;
+
+    Output += S;
+  }
+
+  char look() const {
+    if (Error || Position >= Input.size())
+      return 0;
+
+    return Input[Position];
+  }
+
+  char consume() {
+    if (Error || Position >= Input.size()) {
+      Error = true;
+      return 0;
+    }
+
+    return Input[Position++];
+  }
+
+  bool consumeIf(char Prefix) {
+    if (Error || Position >= Input.size() || Input[Position] != Prefix)
+      return false;
+
+    Position += 1;
+    return true;
+  }
+};
+
+} // namespace rust_demangle
+} // namespace llvm
+
+#endif

llvm/lib/Demangle/CMakeLists.txt

 add_llvm_component_library(LLVMDemangle
   Demangle.cpp
   ItaniumDemangle.cpp
   MicrosoftDemangle.cpp
   MicrosoftDemangleNodes.cpp
+  RustDemangle.cpp
 
   ADDITIONAL_HEADER_DIRS
   "${LLVM_MAIN_INCLUDE_DIR}/llvm/Demangle"
 
 )

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/Demangle/Demangle.h"
+
+#include <cassert>
+#include <cstring>
+#include <limits>
+
+using namespace llvm;
+using namespace rust_demangle;
+
+char *llvm::rustDemangle(const char *MangledName, char *Buf, size_t *N,
+                         int *Status) {
+  if (MangledName == nullptr || (Buf != nullptr && N == nullptr)) {
+    if (Status != nullptr)
+      *Status = demangle_invalid_args;
+    return nullptr;
+  }
+
+  // Return early if mangled name doesn't look like a Rust symbol.
+  StringView Mangled(MangledName);
+  if (!Mangled.startsWith("_R")) {
+    if (Status != nullptr)
+      *Status = demangle_invalid_mangled_name;
+    return nullptr;
+  }
+
+  Demangler D;
+  if (!initializeOutputStream(nullptr, nullptr, D.Output, 1024)) {
+    if (Status != nullptr)
+      *Status = demangle_memory_alloc_failure;
+    return nullptr;
+  }
+
+  if (!D.demangle(Mangled)) {
+    if (Status != nullptr)
+      *Status = demangle_invalid_mangled_name;
+    std::free(D.Output.getBuffer());
+    return nullptr;
+  }
+
+  D.Output += '\0';
+  char *Demangled = D.Output.getBuffer();
+  size_t DemangledLen = D.Output.getCurrentPosition();
+
+  if (Buf != nullptr) {
+    if (DemangledLen <= *N) {
+      std::memcpy(Buf, Demangled, DemangledLen);
+      std::free(Demangled);
+      Demangled = Buf;
+    } else {
+      std::free(Buf);
+    }
+  }
+
+  if (N != nullptr)
+    *N = DemangledLen;
+
+  if (Status != nullptr)
+    *Status = demangle_success;
+
+  return Demangled;
+}
+
+Demangler::Demangler(size_t MaxRecursionLevel)
+    : MaxRecursionLevel(MaxRecursionLevel) {}
+
+static inline bool isDigit(const char C) { return '0' <= C && C <= '9'; }
+
+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 == '_';
+}
+
+/// Computes A + B. When computation wraps around returns false.
+/// Otherwise assigns the result to A and returns true.
+static inline bool addAssign(uint64_t &A, uint64_t B) {
+  if (A > std::numeric_limits<uint64_t>::max() - B)
+    return false;
+
+  A += B;
+  return true;
+}
+
+/// Computes A * B. When computation wraps around returns false.
+/// Otherwise assigns the result to A and returns true.
+static inline bool mulAssign(uint64_t &A, uint64_t B) {
+  if (A > std::numeric_limits<uint64_t>::max() / B)
+    return false;
+
+  A *= B;
+  return true;
+}
+
+// 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>]
+bool Demangler::demangle(StringView Mangled) {
+  Position = 0;
+  Error = false;
+  RecursionLevel = 0;
+
+  if (!Mangled.consumeFront("_R")) {
+    Error = true;
+    return false;
+  }
+  Input = Mangled;
+
+  demanglePath();
+
+  // FIXME parse optional <instantiating-crate>.
+
+  if (Position != Input.size())
+    Error = true;
+
+  return !Error;
+}
+
+// <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;
+
+  switch (consume()) {
+  case 'C': {
+    parseOptionalBase62Number('s');
+    Identifier Ident = parseIdentifier();
+    print(Ident.Name);
+    break;
+  }
+  case 'N': {
+    char NS = consume();
+    if (!isLower(NS) && !isUpper(NS)) {
+      Error = true;
+      break;
+    }
+    demanglePath();
+
+    parseOptionalBase62Number('s');
+    Identifier Ident = parseIdentifier();
+
+    if (!Ident.empty()) {
+      // FIXME print special namespaces:
+      // * "C" closures
+      // * "S" shim
+      print("::");
+      print(Ident.Name);
+    }
+    break;
+  }
+  default:
+    // FIXME parse remaining productions.
+    Error = true;
+    break;
+  }
+
+  RecursionLevel -= 1;
+}
+
+// <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;
+
+  for (char C : S) {
+    if (!isValid(C)) {
+      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();
+}
+
+// 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)) {
+      Error = true;
+      return 0;
+    }
+
+    if (!addAssign(Value, Digit)) {
+      Error = true;
+      return 0;
+    }
+  }
+
+  if (!addAssign(Value, 1)) {
+    Error = true;
+    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)) {
+      Error = true;
+      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
+
+; Invalid mangled characters
+
+CHECK: _RNvC2a.1c
+       _RNvC2a.1c
+
+CHECK: _RNvC2a$1c
+       _RNvC2a$1c
+
+; 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

llvm/tools/llvm-cxxfilt/llvm-cxxfilt.cpp

if (Types ||
     Undecorated = itaniumDemangle(DecoratedStr, nullptr, nullptr, &Status);
 
   if (!Undecorated &&
       (DecoratedLength > 6 && strncmp(DecoratedStr, "__imp_", 6) == 0)) {
     Prefix = "import thunk for ";
     Undecorated = itaniumDemangle(DecoratedStr + 6, nullptr, nullptr, &Status);
   }
 
+  if (!Undecorated &&
+      (DecoratedLength >= 2 && strncmp(DecoratedStr, "_R", 2) == 0)) {
+    Undecorated = rustDemangle(DecoratedStr, nullptr, nullptr, &Status);
+  }
+
   std::string Result(Undecorated ? Prefix + Undecorated : Mangled);
   free(Undecorated);
   return Result;
 }
 
 // Split 'Source' on any character that fails to pass 'IsLegalChar'.  The
 // returned vector consists of pairs where 'first' is the delimited word, and
 // 'second' are the delimiters following that word.

llvm/unittests/Demangle/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Demangle
   Support
 )
 
 add_llvm_unittest(DemangleTests
   DemangleTest.cpp
   ItaniumDemangleTest.cpp
   PartialDemangleTest.cpp
+  RustDemangleTest.cpp
   StringViewTest.cpp
 )

llvm/unittests/Demangle/RustDemangleTest.cpp

+//===------------------ RustDemangleTest.cpp ------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Demangle/Demangle.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+#include <cstdlib>
+
+TEST(RustDemangle, Success) {
+  char *Demangled =
+      llvm::rustDemangle("_RNvC1a4main", nullptr, nullptr, nullptr);
+  EXPECT_STREQ(Demangled, "a::main");
+  std::free(Demangled);
+
+  // With status.
+  int Status = 0;
+  Demangled = llvm::rustDemangle("_RNvC1a4main", nullptr, nullptr, &Status);
+  EXPECT_EQ(Status, llvm::demangle_success);
+  EXPECT_STREQ(Demangled, "a::main");
+  std::free(Demangled);
+
+  // With status and length.
+  size_t N = 0;
+  Demangled = llvm::rustDemangle("_RNvC1a4main", nullptr, &N, &Status);
+  EXPECT_EQ(Status, llvm::demangle_success);
+  EXPECT_EQ(N, 8u);
+  EXPECT_STREQ(Demangled, "a::main");
+  std::free(Demangled);
+}
+
+TEST(RustDemangle, Invalid) {
+  int Status = 0;
+  char *Demangled = nullptr;
+
+  // Invalid prefix.
+  Demangled = llvm::rustDemangle("_ABCDEF", nullptr, nullptr, &Status);
+  EXPECT_EQ(Status, llvm::demangle_invalid_mangled_name);
+  EXPECT_EQ(Demangled, nullptr);
+
+  // Correct prefix but still invalid.
+  Demangled = llvm::rustDemangle("_RRR", nullptr, nullptr, &Status);
+  EXPECT_EQ(Status, llvm::demangle_invalid_mangled_name);
+  EXPECT_EQ(Demangled, nullptr);
+}
+
+TEST(RustDemangle, OutputBufferWithoutLength) {
+  char *Buffer = static_cast<char *>(std::malloc(1024));
+  ASSERT_NE(Buffer, nullptr);
+
+  int Status = 0;
+  char *Demangled =
+      llvm::rustDemangle("_RNvC1a4main", Buffer, nullptr, &Status);
+
+  EXPECT_EQ(Status, llvm::demangle_invalid_args);
+  EXPECT_EQ(Demangled, nullptr);
+  std::free(Buffer);
+}
+
+TEST(RustDemangle, OutputBuffer) {
+  size_t N = 1024;
+  char *Buffer = static_cast<char *>(std::malloc(N));
+  ASSERT_NE(Buffer, nullptr);
+
+  int Status = 0;
+  char *Demangled = llvm::rustDemangle("_RNvC1a4main", Buffer, &N, &Status);
+
+  EXPECT_EQ(Status, llvm::demangle_success);
+  EXPECT_EQ(Demangled, Buffer);
+  EXPECT_STREQ(Demangled, "a::main");
+  std::free(Demangled);
+}
+
+TEST(RustDemangle, SmallOutputBuffer) {
+  size_t N = 1;
+  char *Buffer = static_cast<char *>(std::malloc(N));
+  ASSERT_NE(Buffer, nullptr);
+
+  int Status = 0;
+  char *Demangled = llvm::rustDemangle("_RNvC1a4main", Buffer, &N, &Status);
+
+  EXPECT_EQ(Status, llvm::demangle_success);
+  EXPECT_STREQ(Demangled, "a::main");
+  std::free(Demangled);
+}