[Demangle] Add support for D symbols back referencing

[ljmf00]

Summary

This patch adds support for identifier back referencing allowing compressed
mangled names by avoiding repetitiveness.

Signed-off-by: Luís Ferreira <[e-mail]>

[dblaikie]

Looks like this is a bit undertested - the number encoding supports uppercase values, but I don't think the test case tests any uppercase (multi-digit/character encoded) values, for instance? As well as various (I count about 3-4 or so, at least) different encoding failure cases that should probably be tested too.

llvm/lib/Demangle/DLangDemangle.cpp

73–84

Perhaps it'd make sense if this took Mangled as a const char** in/out, and returned Optional<Ret>? (both callers overwrite their Mangled parameter with the return result anyway - so seems simpler for it to be in/out?) if Optional isn't available, maybe long min, -1, something could be the invalid result value?

(similarly for decodeBackref)

221–222

is this an overflow check? Can it be reached if the other overflow check at 379 succeeds? (is it tested?)

237–238

Looks like this condition's probably untested? Should it be removed or turned into an assertion?

[ljmf00]

llvm/lib/Demangle/DLangDemangle.cpp

73–84

As is, I understand your point, but what if I want to preserve Mangled and use decodeBackref/decodeBackrefPos as an expression for an if, strcmp or else? e.g. On the patch I introduce integer literal values I use decodeBackref like the following:

if (decodeBackref(Mangled, &Backref) == nullptr)
{
    //...
}

If I pass a reference of Mangled and use old Mangled inside, I would need to preserve a copy of its old position to make sure it won't be a "dirty" value. e.g. back reference "AAAA0", will produce a dirty Mangled and can produce bad behaviour afterwards.

221–222

This is a safe check when casting to long. The above overflow check is for unsigned long, but Ret is a long value. This is being done that way because signed overflow checks are considered undefined behaviour, since there is various ways to represent a signed value in different CPU targets. I checked locally, _D8demangleQDXXXXXXXXXXXXx triggers it with the fuzzer when that code is commented, so I'm going to add this to the test suite.

237–238

Well this shouldn't happen and since those methods are not exposed somewhere else, the compiler can optimize this out easily. I think it is reasonable to keep this check as a safety measure, although if we do some action, I maybe prefer to assert it. In my vision, triggering an assert on, e.g. a failed demangling for a linker error is worse than just outputting the mangled symbol anyway (nullptr will make llvm::demangle fallback to the initial Mangled reference). It is also worth mentioning that removing this when assert are disabled in release mode, can produce wrong and hard to debug behaviour.

[dblaikie]

llvm/lib/Demangle/DLangDemangle.cpp

73–84

Fair enough, if there are future use cases that won't immediately overwrite Mangled, sounds good.

Ret should probably be passed by reference here, and in decodeBackref if they can't be null?

221–222

The fuzzer trips ubsan with this <= 0 check commented out, for this test case? OK, great - thanks for explaining & adding the test case!

Hmm, I'm still not quite sure how this overflow could occur, if the check on line 214 passed. Could you walk me through a specific value of Val at the start of the loop that passes the initial overflow check, but then fails this one? And/or could you explain what the - 25 is for in the earlier overflow check. I'm reading that as "make sure it's not too close to the end, so there's room to add the next value" but maybe it's for some other purpose?

237–238

Sorry, not sure I'm following. Generally if the code can't be reached, it should be an assert, not a runtime check - adding defensive coding to support behavior if there are other bugs in the code isn't something we should be doing. This ensures the code doesn't have "haunted graveyard" kind of effects where code becomes hard to maintain because it's unclear why it's there in the first place, isn't tested, etc. Assertions document the intended invariants in a piece of code that make it easier for developers to make changes in the future.

It is also worth mentioning that removing this when assert are disabled in release mode, can produce wrong and hard to debug behaviour.

It can produce wrong/hard to debug behavior if there's some other bug in the code, yes? Generally the first thing LLVM developers do if they encounter problematic behavior, is run it with an assertions-enabled build which should help diagnose the issue. There's some further discussion here: https://llvm.org/docs/CodingStandards.html#assert-liberally

[ljmf00]

I simplified the symbol back referencing. I thought that referencing a back reference was permitted by the ABI spec, but it was pointing to the same position, so it is redundant to add two back-references. I also added a comment on the nullptr tests to describe what it is testing. In the case of Qa, it references itself and hangs.

llvm/lib/Demangle/DLangDemangle.cpp

73–84

Fixed. I will also introduce a patch in the stack to make decodeNumber use Ret by reference, instead.

221–222

The fuzzer trips with Asan, since Ret value is used to offset the current position to discover the back reference. Since it is documented in decodeBackrefPos that Ret is required to be > 0 on success, negative values aren't checked, bad offset memory is dereferenced later, and it eventually segfaults.

All the math operations are made with unsigned long and then casted to a long value, at the end. Lets consider a 64-bit unsigned long, with max capacity of (2^64 - 1). If we consider ((ulong.max - 25) / 26) - 10 (709490156681136589), I can safely do both operations of multiply and add (709490156681136589 * 26 + 25 == 18446744073709551339) and still have a negative value when casting it to long. This would obviously depend on how signed numbers are represented in hardware but will likely produce -277 if two's complement. https://godbolt.org/z/1GaMzzcxj

In another perspective, the last check is here to make sure that a value in unsigned long or long values are the same.

237–238

Right, your points made me change my point of view on that and makes perfect sense, since this is supposed to never ever happen. I was skeptical by the fact that it would produce a wrong behaviour if asserts were disabled, but this end up being easier to debug if, with the same input we trigger the assert.

[dblaikie]

Looks good, thanks!

llvm/lib/Demangle/DLangDemangle.cpp

80

Since the function already communicates failure via a null return - should this maybe be an invariant/assertion/postcondition ("Ret is always >=0 on success, and unspecified on failure" or something like that?)

221–222

Ah, thanks for walking me through it!

[ljmf00]

llvm/lib/Demangle/DLangDemangle.cpp

80

Right. Changed the documentation as suggested.

llvm/lib/Demangle/DLangDemangle.cpp

private:
   ///
   /// \return The remaining string on success or nullptr on failure.
   ///
   /// \note A result larger than UINT_MAX is considered a failure.
   ///
   /// \see https://dlang.org/spec/abi.html#Number .
   const char *decodeNumber(const char *Mangled, unsigned long *Ret);
 
+  /// Extract the back reference position from a given string.
+  ///
+  /// \param Mangled string to extract the back reference position.
+  /// \param Ret assigned result value.
+  ///
+  /// \return the remaining string on success or nullptr on failure.
+  ///
+  /// \note Ret is always >= 0 on success, and unspecified on failure
+  ///
+  /// \see https://dlang.org/spec/abi.html#back_ref .
+  /// \see https://dlang.org/spec/abi.html#NumberBackRef .
+  const char *decodeBackrefPos(const char *Mangled, long &Ret);
+
+  /// Extract the symbol pointed by the back reference form a given string.
+  ///
+  /// \param Mangled string to extract the back reference position.
+  /// \param Ret assigned result value.
+  ///
+  /// \return the remaining string on success or nullptr on failure.
+  ///
+  /// \see https://dlang.org/spec/abi.html#back_ref .
+  const char *decodeBackref(const char *Mangled, const char *&Ret);
+
+  /// Extract and demangle backreferenced symbol from a given mangled symbol
+  /// and append it to the output string.
+  ///
+  /// \param Demangled output buffer to write the demangled name.
+  /// \param Mangled mangled symbol to be demangled.
+  ///
+  /// \return the remaining string on success or nullptr on failure.
+  ///
+  /// \see https://dlang.org/spec/abi.html#back_ref .
+  /// \see https://dlang.org/spec/abi.html#IdentifierBackRef .
+  const char *parseSymbolBackref(OutputBuffer *Demangled, const char *Mangled);
+
   /// Check whether it is the beginning of a symbol name.
   ///
   /// \param Mangled string to extract the symbol name.
   ///
   /// \return true on success, false otherwise.
   ///
   /// \see https://dlang.org/spec/abi.html#SymbolName .
   bool isSymbolName(const char *Mangled);
const char *Demangler::decodeNumber(const char *Mangled, unsigned long *Ret) {
 
   if (*Mangled == '\0')
     return nullptr;
 
   *Ret = Val;
   return Mangled;
 }
 
+const char *Demangler::decodeBackrefPos(const char *Mangled, long &Ret) {
+  // Return nullptr if trying to extract something that isn't a digit
+  if (Mangled == nullptr || !std::isalpha(*Mangled))
+    return nullptr;
+
+  // Any identifier or non-basic type that has been emitted to the mangled
+  // symbol before will not be emitted again, but is referenced by a special
+  // sequence encoding the relative position of the original occurrence in the
+  // mangled symbol name.
+  // Numbers in back references are encoded with base 26 by upper case letters
+  // A-Z for higher digits but lower case letters a-z for the last digit.
+  //    NumberBackRef:
+  //        [a-z]
+  //        [A-Z] NumberBackRef
+  //        ^
+  unsigned long Val = 0;
+
+  while (std::isalpha(*Mangled)) {
+    // Check for overflow
+    if (Val > (std::numeric_limits<unsigned long>::max() - 25) / 26)
+      break;
+
+    Val *= 26;
+
+    if (Mangled[0] >= 'a' && Mangled[0] <= 'z') {
+      Val += Mangled[0] - 'a';
+      if ((long)Val <= 0)
+        break;
+      Ret = Val;
+      return Mangled + 1;
+    }
+
+    Val += Mangled[0] - 'A';
+    ++Mangled;
+  }
+
+  return nullptr;
+}
+
+const char *Demangler::decodeBackref(const char *Mangled, const char *&Ret) {
+  assert(Mangled != nullptr && *Mangled == 'Q' && "Invalid back reference!");
+  Ret = nullptr;
+
+  // Position of 'Q'
+  const char *Qpos = Mangled;
+  long RefPos;
+  ++Mangled;
+
+  Mangled = decodeBackrefPos(Mangled, RefPos);
+  if (Mangled == nullptr)
+    return nullptr;
+
+  if (RefPos > Qpos - Str)
+    return nullptr;
+
+  // Set the position of the back reference.
+  Ret = Qpos - RefPos;
+
+  return Mangled;
+}
+
+const char *Demangler::parseSymbolBackref(OutputBuffer *Demangled,
+                                          const char *Mangled) {
+  // An identifier back reference always points to a digit 0 to 9.
+  //    IdentifierBackRef:
+  //        Q NumberBackRef
+  //        ^
+  const char *Backref;
+  unsigned long Len;
+
+  // Get position of the back reference
+  Mangled = decodeBackref(Mangled, Backref);
+
+  // Must point to a simple identifier
+  Backref = decodeNumber(Backref, &Len);
+  if (Backref == nullptr || strlen(Backref) < Len)
+    return nullptr;
+
+  Backref = parseLName(Demangled, Backref, Len);
+  if (Backref == nullptr)
+    return nullptr;
+
+  return Mangled;
+}
+
 bool Demangler::isSymbolName(const char *Mangled) {
+  long Ret;
+  const char *Qref = Mangled;
+
   if (std::isdigit(*Mangled))
     return true;
 
-  // TODO: Handle symbol back references and template instances.
+  // TODO: Handle template instances.
+
+  if (*Mangled != 'Q')
     return false;
+
+  Mangled = decodeBackrefPos(Mangled + 1, Ret);
+  if (Mangled == nullptr || Ret > Qref - Str)
+    return false;
+
+  return std::isdigit(Qref[-Ret]);
 }
 
 const char *Demangler::parseMangle(OutputBuffer *Demangled,
                                    const char *Mangled) {
   // A D mangled symbol is comprised of both scope and type information.
   //    MangleName:
   //        _D QualifiedName Type
   //        _D QualifiedName Z

 
 const char *Demangler::parseIdentifier(OutputBuffer *Demangled,
                                        const char *Mangled) {
   unsigned long Len;
 
   if (Mangled == nullptr || *Mangled == '\0')
     return nullptr;
 
-  // TODO: Parse back references and lengthless template instances.
+  if (*Mangled == 'Q')
+    return parseSymbolBackref(Demangled, Mangled);
+
+  // TODO: Parse lengthless template instances.
 
   const char *Endptr = decodeNumber(Mangled, &Len);
 
   if (Endptr == nullptr || Len == 0)
     return nullptr;
 
   if (strlen(Endptr) < Len)
     return nullptr;

llvm/unittests/Demangle/DLangDemangleTest.cpp

testing::Values(
         std::make_pair("_D8demangle4test12__ModuleInfoZ",
                        "ModuleInfo for demangle.test"),
         std::make_pair("_D8demangle4__S14testZ", "demangle.test"),
         std::make_pair("_D8demangle4__Sd4testZ", "demangle.__Sd.test"),
         std::make_pair("_D8demangle3fooi", "demangle.foo"),
         std::make_pair("_D8demangle3foo",
                        nullptr), // symbol without a type sequence.
         std::make_pair("_D8demangle3fooinvalidtypeseq",
-                       nullptr))); // invalid type sequence.
+                       nullptr), // invalid type sequence.
+        std::make_pair(
+            "_D8demangle3ABCQe1ai",
+            "demangle.ABC.ABC.a"), // symbol back reference: `Qe` is a back
+                                   // reference for position 5, counting from e
+                                   // char, so decoding it points to `3`. Since
+                                   // `3` is a number, 3 chars get read and it
+                                   // succeeded.
+        std::make_pair("_D8demangle3ABCQa1ai",
+                       nullptr), // invalid symbol back reference (recursive).
+        std::make_pair("_D8demangleQDXXXXXXXXXXXXx",
+                       nullptr))); // overflow back reference position.