[Demangle][Rust] Parse non-ASCII identifiers

[tmiasko]

Summary

Rust allows use of non-ASCII identifiers, which in Rust mangling scheme
are encoded using Punycode.

The encoding deviates from the standard by using an underscore as the
separator between ASCII part and a base-36 encoding of non-ASCII
characters (avoiding hypen-minus in the symbol name). Other than that,
the encoding follows the standard, and the decoder implemented here in
turn follows the one given in RFC 3492.

To avoid an extra intermediate memory allocation while decoding
Punycode, the interface of OutputStream is extended with an insert
method.

[tmiasko]

• Avoid else after return.

[dblaikie]

I haven't looked in detail at the punycode implementation - I guess this'll get some workout when tested against rust's output (leaving some chance of symmetric encode/decode bugs) & that's probably good enough.

libcxxabi/src/demangle/Utility.h

129

Could use an Arrayref<const char> (Or StringRef) instead of separate const char * and size_t parameters. Not necessary, there's some value in the symmetry with standard library functions (though I guess they're more likely to use begin/end rather than begin/length), etc.

131–136

I'd probably use an early return here to reduce indentation.

llvm/lib/Demangle/RustDemangle.cpp

672–673

Is this error path tested?

[tmiasko]

• Rebase and resolve conflicts with D104362.
• Return early on zero length insert.

[tmiasko]

Thanks for looking David!

In addition to the test cases here, I was also compiling source code with randomly generated non-ASCII identifiers and subsequently cross-validating demangled symbols with other implementations. The only issue I observed at the time, was that compilation time is quadratic with respect to the number of multibyte characters in the source code ...

@ldionne @erik.pilkington could you take a look at the new insert method added to demangling Utility.h? (I synchronized changes with a copy in libcxxabi).

libcxxabi/src/demangle/Utility.h

129

The API is based on the standard std::string::insert with the same type signature. I would prefer to leave this as is.

llvm/lib/Demangle/RustDemangle.cpp

672–673

This error code path is covered by:

; Invalid ABI with punycode.

CHECK: _RIC8functionFKu3n3hEuE
       _RIC8functionFKu3n3hEuE

If Punycode were to be supported in this position, it would demangle to function::<unsafe extern "☃" fn()>.

[tmiasko]

Oh, I forgot this didn't land yet and didn't follow up. I wasn't exactly sure how to interpret blocking review by libc++abi. @dblaikie is your review sufficient for landing this? If not, @ldionne could you take a look at the small part of changes in libcxxabi?

[dblaikie]

In D104366#3035856, @tmiasko wrote:

Oh, I forgot this didn't land yet and didn't follow up. I wasn't exactly sure how to interpret blocking review by libc++abi. @dblaikie is your review sufficient for landing this? If not, @ldionne could you take a look at the small part of changes in libcxxabi?

Yeah, I'm fairly comfortable approving a change like this - but now that you mention the libc++abi surface area here: Are other features of Utility.h tested (unit tested?) somewhere? Could you add testing for this new function too?

Also, admittedly I don't fully understand how this LLVM change ended up needing a change to libc++abi - how do these pieces connect/depend on each other?

[tmiasko]

Rebase and add a unit test for OutputStream::insert

[tmiasko]

In D104366#3037010, @dblaikie wrote:

Yeah, I'm fairly comfortable approving a change like this - but now that you mention the libc++abi surface area here: Are other features of Utility.h tested (unit tested?) somewhere? Could you add testing for this new function too?

Also, admittedly I don't fully understand how this LLVM change ended up needing a change to libc++abi - how do these pieces connect/depend on each other?

I added a unit test for OutputStream::insert. It is also indirectly tested by the Rust demangler of course.

libcxxabi carries its own copy of Itanium demangler to implement __cxa_demangle. Those changes are just keeping those two in sync.

[dblaikie]

In D104366#3037259, @tmiasko wrote:

In D104366#3037010, @dblaikie wrote:

Yeah, I'm fairly comfortable approving a change like this - but now that you mention the libc++abi surface area here: Are other features of Utility.h tested (unit tested?) somewhere? Could you add testing for this new function too?

Also, admittedly I don't fully understand how this LLVM change ended up needing a change to libc++abi - how do these pieces connect/depend on each other?

I added a unit test for OutputStream::insert. It is also indirectly tested by the Rust demangler of course.

libcxxabi carries its own copy of Itanium demangler to implement __cxa_demangle. Those changes are just keeping those two in sync.

Ah, so the issue is that the itanium demangling support is intended to be kept identical between these two places - and that includes a utility header which is, on the LLVM side, used by Rust demangling (which doesn't exist in libcxxabi) - so it's an update to this common header, which is to be kept in sync though there's no (current) use for the extra functionality on the libcxxabi side, because it's not used by the itanium demangling, only the rust demangling. (but good to keep it in sync anyway, in case someone does end up using it in itanium demangling, etc)

Fair enough. Thanks for the help!

libcxxabi/src/demangle/Utility.h

public:
   OutputStream &operator<<(int N) {
     return this->operator<<(static_cast<long long>(N));
   }
 
   OutputStream &operator<<(unsigned int N) {
     return this->operator<<(static_cast<unsigned long long>(N));
   }
 
+  void insert(size_t Pos, const char *S, size_t N) {
+    assert(Pos <= CurrentPosition);
+    if (N == 0)
+      return;
+    grow(N);
+    std::memmove(Buffer + Pos + N, Buffer + Pos, CurrentPosition - Pos);
+    std::memcpy(Buffer + Pos, S, N);
+    CurrentPosition += N;
+  }
+
   size_t getCurrentPosition() const { return CurrentPosition; }
   void setCurrentPosition(size_t NewPos) { CurrentPosition = NewPos; }
 
   char back() const {
     return CurrentPosition ? Buffer[CurrentPosition - 1] : '\0';
   }
 
   bool empty() const { return CurrentPosition == 0; }

llvm/include/llvm/Demangle/Utility.h

public:
   OutputStream &operator<<(int N) {
     return this->operator<<(static_cast<long long>(N));
   }
 
   OutputStream &operator<<(unsigned int N) {
     return this->operator<<(static_cast<unsigned long long>(N));
   }
 
+  void insert(size_t Pos, const char *S, size_t N) {
+    assert(Pos <= CurrentPosition);
+    if (N == 0)
+      return;
+    grow(N);
+    std::memmove(Buffer + Pos + N, Buffer + Pos, CurrentPosition - Pos);
+    std::memcpy(Buffer + Pos, S, N);
+    CurrentPosition += N;
+  }
+
   size_t getCurrentPosition() const { return CurrentPosition; }
   void setCurrentPosition(size_t NewPos) { CurrentPosition = NewPos; }
 
   char back() const {
     return CurrentPosition ? Buffer[CurrentPosition - 1] : '\0';
   }
 
   bool empty() const { return CurrentPosition == 0; }

llvm/lib/Demangle/RustDemangle.cpp

private:
   uint64_t parseDecimalNumber();
   uint64_t parseHexNumber(StringView &HexDigits);
 
   void print(char C);
   void print(StringView S);
   void printDecimalNumber(uint64_t N);
   void printBasicType(BasicType);
   void printLifetime(uint64_t Index);
+  void printIdentifier(Identifier Ident);
 
   char look() const;
   char consume();
   bool consumeIf(char Prefix);
 
   bool addAssign(uint64_t &A, uint64_t B);
   bool mulAssign(uint64_t &A, uint64_t B);
 };
if (Error || RecursionLevel >= MaxRecursionLevel) {
     Error = true;
     return false;
   }
   SwapAndRestore<size_t> SaveRecursionLevel(RecursionLevel, RecursionLevel + 1);
 
   switch (consume()) {
   case 'C': {
     parseOptionalBase62Number('s');
-    Identifier Ident = parseIdentifier();
-    print(Ident.Name);
+    printIdentifier(parseIdentifier());
     break;
   }
   case 'M': {
     demangleImplPath(InType);
     print("<");
     demangleType();
     print(">");
     break;
if (isUpper(NS)) {
       if (NS == 'C')
         print("closure");
       else if (NS == 'S')
         print("shim");
       else
         print(NS);
       if (!Ident.empty()) {
         print(":");
-        print(Ident.Name);
+        printIdentifier(Ident);
       }
       print('#');
       printDecimalNumber(Disambiguator);
       print('}');
     } else {
       // Implementation internal namespaces.
       if (!Ident.empty()) {
         print("::");
-        print(Ident.Name);
+        printIdentifier(Ident);
       }
     }
     break;
   }
   case 'I': {
     demanglePath(InType);
     // Omit "::" when in a type, where it is optional.
     if (InType == IsInType::No)
if (consumeIf('U'))
     print("unsafe ");
 
   if (consumeIf('K')) {
     print("extern \"");
     if (consumeIf('C')) {
       print("C");
     } else {
       Identifier Ident = parseIdentifier();
+      if (Ident.Punycode)
+        Error = true;
       for (char C : Ident.Name) {
         // When mangling ABI string, the "-" is replaced with "_".
         if (C == '_')
           C = '-';
         print(C);
       }
     }
     print("\" ");
if (Depth < 26) {
     char C = 'a' + Depth;
     print(C);
   } else {
     print('z');
     printDecimalNumber(Depth - 26 + 1);
   }
 }
 
+static inline bool decodePunycodeDigit(char C, size_t &Value) {
+  if (isLower(C)) {
+    Value = C - 'a';
+    return true;
+  }
+
+  if (isDigit(C)) {
+    Value = 26 + (C - '0');
+    return true;
+  }
+
+  return false;
+}
+
+static void removeNullBytes(OutputStream &Output, size_t StartIdx) {
+  char *Buffer = Output.getBuffer();
+  char *Start = Buffer + StartIdx;
+  char *End = Buffer + Output.getCurrentPosition();
+  Output.setCurrentPosition(std::remove(Start, End, '\0') - Buffer);
+}
+
+// Encodes code point as UTF-8 and stores results in Output. Returns false if
+// CodePoint is not a valid unicode scalar value.
+static inline bool encodeUTF8(size_t CodePoint, char *Output) {
+  if (0xD800 <= CodePoint && CodePoint <= 0xDFFF)
+    return false;
+
+  if (CodePoint <= 0x7F) {
+    Output[0] = CodePoint;
+    return true;
+  }
+
+  if (CodePoint <= 0x7FF) {
+    Output[0] = 0xC0 | ((CodePoint >> 6) & 0x3F);
+    Output[1] = 0x80 | (CodePoint & 0x3F);
+    return true;
+  }
+
+  if (CodePoint <= 0xFFFF) {
+    Output[0] = 0xE0 | (CodePoint >> 12);
+    Output[1] = 0x80 | ((CodePoint >> 6) & 0x3F);
+    Output[2] = 0x80 | (CodePoint & 0x3F);
+    return true;
+  }
+
+  if (CodePoint <= 0x10FFFF) {
+    Output[0] = 0xF0 | (CodePoint >> 18);
+    Output[1] = 0x80 | ((CodePoint >> 12) & 0x3F);
+    Output[2] = 0x80 | ((CodePoint >> 6) & 0x3F);
+    Output[3] = 0x80 | (CodePoint & 0x3F);
+    return true;
+  }
+
+  return false;
+}
+
+// Decodes string encoded using punycode and appends results to Output.
+// Returns true if decoding was successful.
+static bool decodePunycode(StringView Input, OutputStream &Output) {
+  size_t OutputSize = Output.getCurrentPosition();
+  size_t InputIdx = 0;
+
+  // Rust uses an underscore as a delimiter.
+  size_t DelimiterPos = StringView::npos;
+  for (size_t I = 0; I != Input.size(); ++I)
+    if (Input[I] == '_')
+      DelimiterPos = I;
+
+  if (DelimiterPos != StringView::npos) {
+    // Copy basic code points before the last delimiter to the output.
+    for (; InputIdx != DelimiterPos; ++InputIdx) {
+      char C = Input[InputIdx];
+      if (!isValid(C))
+        return false;
+      // Code points are padded with zeros while decoding is in progress.
+      char UTF8[4] = {C};
+      Output += StringView(UTF8, UTF8 + 4);
+    }
+    // Skip over the delimiter.
+    ++InputIdx;
+  }
+
+  size_t Base = 36;
+  size_t Skew = 38;
+  size_t Bias = 72;
+  size_t N = 0x80;
+  size_t TMin = 1;
+  size_t TMax = 26;
+  size_t Damp = 700;
+
+  auto Adapt = [&](size_t Delta, size_t NumPoints) {
+    Delta /= Damp;
+    Delta += Delta / NumPoints;
+    Damp = 2;
+
+    size_t K = 0;
+    while (Delta > (Base - TMin) * TMax / 2) {
+      Delta /= Base - TMin;
+      K += Base;
+    }
+    return K + (((Base - TMin + 1) * Delta) / (Delta + Skew));
+  };
+
+  // Main decoding loop.
+  for (size_t I = 0; InputIdx != Input.size(); I += 1) {
+    size_t OldI = I;
+    size_t W = 1;
+    size_t Max = std::numeric_limits<size_t>::max();
+    for (size_t K = Base; true; K += Base) {
+      if (InputIdx == Input.size())
+        return false;
+      char C = Input[InputIdx++];
+      size_t Digit = 0;
+      if (!decodePunycodeDigit(C, Digit))
+        return false;
+
+      if (Digit > (Max - I) / W)
+        return false;
+      I += Digit * W;
+
+      size_t T;
+      if (K <= Bias)
+        T = TMin;
+      else if (K >= Bias + TMax)
+        T = TMax;
+      else
+        T = K - Bias;
+
+      if (Digit < T)
+        break;
+
+      if (W > Max / (Base - T))
+        return false;
+      W *= (Base - T);
+    }
+    size_t NumPoints = (Output.getCurrentPosition() - OutputSize) / 4 + 1;
+    Bias = Adapt(I - OldI, NumPoints);
+
+    if (I / NumPoints > Max - N)
+      return false;
+    N += I / NumPoints;
+    I = I % NumPoints;
+
+    // Insert N at position I in the output.
+    char UTF8[4] = {};
+    if (!encodeUTF8(N, UTF8))
+      return false;
+    Output.insert(OutputSize + I * 4, UTF8, 4);
+  }
+
+  removeNullBytes(Output, OutputSize);
+  return true;
+}
+
+void Demangler::printIdentifier(Identifier Ident) {
+  if (Error || !Print)
+    return;
+
+  if (Ident.Punycode) {
+    if (!decodePunycode(Ident.Name, Output))
+      Error = true;
+  } else {
+    print(Ident.Name);
+  }
+}
+
 char Demangler::look() const {
   if (Error || Position >= Input.size())
     return 0;
 
   return Input[Position];
 }
 
 char Demangler::consume() {

llvm/test/Demangle/rust.test

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
 
+; Invalid ABI with punycode.
+
+CHECK: _RIC8functionFKu3n3hEuE
+       _RIC8functionFKu3n3hEuE
+
 ; Trait objects
 
 CHECK: trait::<dyn >
        _RIC5traitDEL_E
 
 CHECK: trait::<dyn for<'a> >
        _RIC5traitDG_EL_E
 

 ; Dot suffix
 
 CHECK: dot (.llvm.1234)
        _RC3dot.llvm.1234
 
 CHECK: dot (.llvm.6789)
        _RC3dotC5crate.llvm.6789
 
+; Punycode
+
+CHECK: punycode::東京
+       _RNvC8punycodeu7_1lqs71d
+
+CHECK: punycode::zażółć_gęślą_jaźń
+       _RNvC8punycodeu29za_gl_ja_w3a7psa2tqtgb10airva
+
+CHECK: punycode::საჭმელად_გემრიელი_სადილი
+       _RNvC8punycodeu30____7hkackfecea1cbdathfdh9hlq6y
+
+CHECK: Gödel::Escher::Bach
+       _RNtNvCu8Gdel_5qa6Escher4Bach
+
+CHECK: punycode::🦁🐅
+       _RNvC8punycodeu7wn8hx1g
+
+; Punycode - invalid code point
+
+CHECK: _RCu5r731r
+       _RCu5r731r
+
+CHECK: _RCu8b44444yy
+       _RCu8b44444yy
+
+CHECK: _RNvC1au25zzzzzzzzzzzzzzzzzzzzzzzzz
+       _RNvC1au25zzzzzzzzzzzzzzzzzzzzzzzzz
+
+; Punycode - early EOF
+
+CHECK: _RCu8_CCCAR_u4
+       _RCu8_CCCAR_u4
+
+; Punycode - overflow
+
+CHECK: _RNvC1au21p18888888888888888888
+       _RNvC1au21p18888888888888888888
+
 ; Invalid mangled characters
 
 CHECK: _RNvC2a.1c
        _RNvC2a.1c
 
 CHECK: _RNvC2a$1c
        _RNvC2a$1c
 

llvm/unittests/Demangle/CMakeLists.txt

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

llvm/unittests/Demangle/OutputStreamTest.cpp

+//===- llvm/unittest/OutputStreamTest.cpp - OutputStream unit tests -------===//
+//
+// 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/Utility.h"
+#include "gtest/gtest.h"
+#include <string>
+
+using namespace llvm;
+using llvm::itanium_demangle::OutputStream;
+
+static std::string toString(OutputStream &OS) {
+  return {OS.getBuffer(), OS.getCurrentPosition()};
+}
+
+template <typename T> static std::string printToString(const T &Value) {
+  OutputStream OS;
+  OS << Value;
+  std::string s = toString(OS);
+  std::free(OS.getBuffer());
+  return s;
+}
+
+TEST(OutputStreamTest, Format) {
+  EXPECT_EQ("0", printToString(0));
+  EXPECT_EQ("1", printToString(1));
+  EXPECT_EQ("-1", printToString(-1));
+  EXPECT_EQ("-90", printToString(-90));
+  EXPECT_EQ("109", printToString(109));
+  EXPECT_EQ("400", printToString(400));
+
+  EXPECT_EQ("a", printToString('a'));
+  EXPECT_EQ("?", printToString('?'));
+
+  EXPECT_EQ("abc", printToString("abc"));
+}
+
+TEST(OutputStreamTest, Insert) {
+  OutputStream OS;
+
+  OS.insert(0, "", 0);
+  EXPECT_EQ("", toString(OS));
+
+  OS.insert(0, "abcd", 4);
+  EXPECT_EQ("abcd", toString(OS));
+
+  OS.insert(0, "x", 1);
+  EXPECT_EQ("xabcd", toString(OS));
+
+  OS.insert(5, "y", 1);
+  EXPECT_EQ("xabcdy", toString(OS));
+
+  OS.insert(3, "defghi", 6);
+  EXPECT_EQ("xabdefghicdy", toString(OS));
+
+  std::free(OS.getBuffer());
+}