[Demangle] Add support for D simple single qualified names

[ljmf00]

Summary

This patch adds support for simple single qualified names that includes
internal mangled names and normal symbol names.

[dblaikie]

This patch still looks pretty long - perhaps it could be split up. Could support a single identifier first, then multiple identifiers (qualifiers) and then the LName things? (could be one at a time, but might be easy enough to check them all together there if they're really regularly structured)

llvm/lib/Demangle/DLangDemangle.cpp

385–386

Might be easier to read with a StringSwitch (could make a StringRef from the Mnagled pointer and the length - maybe pass as StringRef here, rather than as the decomposed components) rather than a switch over length + strncmps?

391–392

Remove else-after-return(s)

423–429

This appears to be unstested

[ljmf00]

llvm/lib/Demangle/DLangDemangle.cpp

385–386

I guess you are missing the point of this switch. Maybe some comments can be added to cover this behaviour but the point here is: the length passed into parseLName is the length of the identifier name but not of the mangled name evaluated inside strncmp. This is specifically needed, because, for other special names, e.g. initializers (__initZ), a Z is suffixed indicating it is a special symbol. In order to verify that, extra length to accommodate the 'Z' char is needed.

The StringSwitch is not applicable here because of that, otherwise would be a good fit. I see optimizations that can be done, however, which is:

1. Use integer literals on strncmp instead of being calculated in runtime
2. Use a second inner switch to make the compiler optimize it with jump tables

423–429

Thanks, this actually needs to be on another patch, since this is technically part of the function mangling. It also includes this and ~this (they are not being tested here, but on https://reviews.llvm.org/D111423 although they should be all tested on https://reviews.llvm.org/D110576) I'm going to update the path when tests file get rearranged (due to the discussion on https://reviews.llvm.org/D111414)

[ljmf00]

llvm/lib/Demangle/DLangDemangle.cpp

385–386

Well, I realized that the first option is not doable here and the second one, from what I tested on clang 13, the optimizer can take what I suggested easily. https://godbolt.org/z/5dorfsWq9
If you have any other suggestions here that can increase readability, I would appreciate discussing them :)

[ljmf00]

I changed the patch to avoid else-after-return, use // comment style, remove untested code, use ++i over i++ when possible, and use the OutputBuffer.

@dblaikie Can you rereview now?

[dblaikie]

Still seems a bit long in one patch/hard to verify that all the cases are covered by tests, etc. Could you break this up further - maybe implementing only the most basic, single 'parseIdentifier' case, then the iteration, then the anonymous symbols, then the lnames?

[ljmf00]

In D111415#3140916, @dblaikie wrote:

Still seems a bit long in one patch/hard to verify that all the cases are covered by tests, etc. Could you break this up further - maybe implementing only the most basic, single 'parseIdentifier' case, then the iteration, then the anonymous symbols, then the lnames?

I have to disagree here a bit, but I'm going to do it anyway since I really want to go forward with this and don't lose time discussing this nit. I think parsing LName special cases could be indeed in another patch, but either anonymous symbols and identifier iteration are really little things. About anonymous symbols, we are talking about 5 lines of code that are trivial:

// Skip over anonymous symbols.
    if (*Mangled == '0') {
      do
        ++Mangled;
      while (*Mangled == '0');

      continue;
    }

And the iteration with an if for adding the dot is a simple do while dependent on isSymbolName which currently just checks if the next char is a digit or not before parsing another node, which is like 10 lines of code.

I'm going to also separate the fake parent symbols, which is not yet in the spec. See here for context https://github.com/dlang/dlang.org/pull/3124 .

[ljmf00]

https://reviews.llvm.org/D114305
https://reviews.llvm.org/D114307
https://reviews.llvm.org/D114308
https://reviews.llvm.org/D114309

I added four more patches, corresponding to the requested split content.

llvm/lib/Demangle/DLangDemangle.cpp

 //===--- DLangDemangle.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
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// This file defines a demangler for the D programming language as specified
 /// in the ABI specification, available at:
 /// https://dlang.org/spec/abi.html#name_mangling
 ///
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Demangle/Demangle.h"
+#include "llvm/Demangle/StringView.h"
 #include "llvm/Demangle/Utility.h"
 
 #include <cstring>
+#include <limits>
 
 using namespace llvm;
 using llvm::itanium_demangle::OutputBuffer;
+using llvm::itanium_demangle::StringView;
+
+namespace {
+
+/// Demangle information structure.
+struct Demangler {
+  /// Initialize the information structure we use to pass around information.
+  ///
+  /// \param Mangled String to demangle.
+  Demangler(const char *Mangled);
+
+  /// Extract and demangle the mangled symbol and append it to the output
+  /// string.
+  ///
+  /// \param Demangled Output buffer to write the demangled name.
+  ///
+  /// \return The remaining string on success or nullptr on failure.
+  ///
+  /// \see https://dlang.org/spec/abi.html#name_mangling .
+  /// \see https://dlang.org/spec/abi.html#MangledName .
+  const char *parseMangle(OutputBuffer *Demangled);
+
+private:
+  /// Extract and demangle 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#name_mangling .
+  /// \see https://dlang.org/spec/abi.html#MangledName .
+  const char *parseMangle(OutputBuffer *Demangled, const char *Mangled);
+
+  /// Extract the number from a given string.
+  ///
+  /// \param Mangled string to extract the number.
+  /// \param Ret assigned result value.
+  ///
+  /// \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 and demangle an identifier from a given mangled symbol 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#SymbolName .
+  const char *parseIdentifier(OutputBuffer *Demangled, const char *Mangled);
+
+  /// Extract and demangle the plain identifier from a given mangled symbol and
+  /// prepend/append it to the output string, with a special treatment for some
+  /// magic compiler generated symbols.
+  ///
+  /// \param Demangled Output buffer to write the demangled name.
+  /// \param Mangled Mangled symbol to be demangled.
+  /// \param Len Length of the mangled symbol name.
+  ///
+  /// \return The remaining string on success or nullptr on failure.
+  ///
+  /// \see https://dlang.org/spec/abi.html#LName .
+  const char *parseLName(OutputBuffer *Demangled, const char *Mangled,
+                         unsigned long Len);
+
+  /// Extract and demangle the qualified symbol from a given mangled symbol
+  /// 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#QualifiedName .
+  const char *parseQualified(OutputBuffer *Demangled, const char *Mangled);
+
+  /// The string we are demangling.
+  const char *Str;
+};
+
+} // namespace
+
+const char *Demangler::decodeNumber(const char *Mangled, unsigned long *Ret) {
+  // Return nullptr if trying to extract something that isn't a digit.
+  if (Mangled == nullptr || !std::isdigit(*Mangled))
+    return nullptr;
+
+  unsigned long Val = 0;
+
+  do {
+    unsigned long Digit = Mangled[0] - '0';
+
+    // Check for overflow.
+    if (Val > (std::numeric_limits<unsigned int>::max() - Digit) / 10)
+      return nullptr;
+
+    Val = Val * 10 + Digit;
+    ++Mangled;
+  } while (std::isdigit(*Mangled));
+
+  if (*Mangled == '\0')
+    return nullptr;
+
+  *Ret = Val;
+  return Mangled;
+}
+
+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
+  //        ^
+  // The caller should have guaranteed that the start pointer is at the
+  // above location.
+  // Note that type is never a function type, but only the return type of
+  // a function or the type of a variable.
+  Mangled += 2;
+
+  Mangled = parseQualified(Demangled, Mangled);
+
+  if (Mangled != nullptr) {
+    // Artificial symbols end with 'Z' and have no type.
+    if (*Mangled == 'Z')
+      ++Mangled;
+    else {
+      // TODO: Implement symbols with types.
+      return nullptr;
+    }
+  }
+
+  return Mangled;
+}
+
+const char *Demangler::parseQualified(OutputBuffer *Demangled,
+                                      const char *Mangled) {
+  // Qualified names are identifiers separated by their encoded length.
+  // Nested functions also encode their argument types without specifying
+  // what they return.
+  //    QualifiedName:
+  //        SymbolFunctionName
+  //        SymbolFunctionName QualifiedName
+  //        ^
+  //    SymbolFunctionName:
+  //        SymbolName
+  //        SymbolName TypeFunctionNoReturn
+  //        SymbolName M TypeFunctionNoReturn
+  //        SymbolName M TypeModifiers TypeFunctionNoReturn
+  // The start pointer should be at the above location.
+
+  // TODO: Parse multiple identifiers
+
+  return parseIdentifier(Demangled, Mangled);
+}
+
+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.
+
+  const char *Endptr = decodeNumber(Mangled, &Len);
+
+  if (Endptr == nullptr || Len == 0)
+    return nullptr;
+
+  if (strlen(Endptr) < Len)
+    return nullptr;
+
+  Mangled = Endptr;
+
+  // TODO: Parse template instances with a length prefix.
+
+  return parseLName(Demangled, Mangled, Len);
+}
+
+const char *Demangler::parseLName(OutputBuffer *Demangled, const char *Mangled,
+                                  unsigned long Len) {
+  *Demangled << StringView(Mangled, Len);
+  Mangled += Len;
+
+  return Mangled;
+}
+
+Demangler::Demangler(const char *Mangled) : Str(Mangled) {}
+
+const char *Demangler::parseMangle(OutputBuffer *Demangled) {
+  return parseMangle(Demangled, this->Str);
+}
 
 char *llvm::dlangDemangle(const char *MangledName) {
   if (MangledName == nullptr || strncmp(MangledName, "_D", 2) != 0)
     return nullptr;
 
   OutputBuffer Demangled;
   if (!initializeOutputBuffer(nullptr, nullptr, Demangled, 1024))
     return nullptr;
 
-  if (strcmp(MangledName, "_Dmain") == 0)
+  if (strcmp(MangledName, "_Dmain") == 0) {
     Demangled << "D main";
+  } else {
+
+    Demangler D = Demangler(MangledName);
+    MangledName = D.parseMangle(&Demangled);
+
+    // Check that the entire symbol was successfully demangled.
+    if (MangledName == nullptr || *MangledName != '\0') {
+      std::free(Demangled.getBuffer());
+      return nullptr;
+    }
+  }
 
   // OutputBuffer's internal buffer is not null terminated and therefore we need
   // to add it to comply with C null terminated strings.
   if (Demangled.getCurrentPosition() > 0) {
     Demangled << '\0';
     Demangled.setCurrentPosition(Demangled.getCurrentPosition() - 1);
     return Demangled.getBuffer();
   }
 
-  free(Demangled.getBuffer());
+  std::free(Demangled.getBuffer());
   return nullptr;
 }

llvm/unittests/Demangle/DLangDemangleTest.cpp

 TEST_P(DLangDemangleTestFixture, DLangDemangleTest) {
   EXPECT_STREQ(Demangled, GetParam().second);
 }
 
 INSTANTIATE_TEST_SUITE_P(DLangDemangleTest, DLangDemangleTestFixture,
                          testing::Values(std::make_pair("_Dmain", "D main"),
                                          std::make_pair(nullptr, nullptr),
                                          std::make_pair("_Z", nullptr),
-                                         std::make_pair("_DDD", nullptr)));
+                                         std::make_pair("_DDD", nullptr),
+                                         std::make_pair("_D88", nullptr),
+                                         std::make_pair("_D8demangleZ",
+                                                        "demangle")));