[demangler] Add a "partial" demangling API for LLDB

[erik.pilkington]

Summary

lldb-dev thread: http://lists.llvm.org/pipermail/lldb-dev/2018-January/013186.html

Currently, the demangler in ItaniumDemangler works by parsing the mangled name into an AST-like format, then traverses that AST to produce the demangled name. Some users (LLDB) consume this demangled name by writing custom parsers. This is redundant (in a very hot section, AFAIK), as the name has to be printed and the re-parsed. For large demangled names with many (potentially nested) <template-param>s and substitutions, the demangler has to produce a massive symbol that LLDB has to dig through in order to find the small amount of information that it needs. Just parsing to an AST expands no substitutions, and should run in about O(strlen of the mangled name).

This patch adds a partial demangling API that parses the mangled name into the AST-like format without printing and provides some functions to access interesting information from that AST. If LLDB used this instead of char*s to investigate the demangled name, it would be cleaner and save time. (AFAIK, I've never touched lldb!)

I've put this patch up super early, I still want to add more tests and make it more robust. I'm hoping that this would be a good place to find out if this is what the LLDB people actually want. Does anyone have any thoughts?

Thanks for taking a look!
Erik

[davide]

It would be awesome if you could benchmark on some pathological testcases (e.g. the one Greg was pointing out)

_ZNK3shk6detail17CallbackPublisherIZNS_5ThrowERKNSt15__exception_ptr13exception_ptrEEUlOT_E_E9SubscribeINS0_9ConcatMapINS0_18CallbackSubscriberIZNS_6GetAllIiNS1_IZZNS_9ConcatMapIZNS_6ConcatIJNS1_IZZNS_3MapIZZNS_7IfEmptyIS9_EEDaS7_ENKUlS6_E_clINS1_IZZNS_4TakeIiEESI_S7_ENKUlS6_E_clINS1_IZZNS_6FilterIZNS_9ElementAtEmEUlS7_E_EESI_S7_ENKUlS6_E_clINS1_IZZNSL_ImEESI_S7_ENKUlS6_E_clINS1_IZNS_4FromINS0_22InfiniteRangeContainerIiEEEESI_S7_EUlS7_E_EEEESI_S6_EUlS7_E_EEEESI_S6_EUlS7_E_EEEESI_S6_EUlS7_E_EEEESI_S6_EUlS7_E_EESI_S7_ENKUlS6_E_clIS14_EESI_S6_EUlS7_E_EERNS1_IZZNSH_IS9_EESI_S7_ENKSK_IS14_EESI_S6_EUlS7_E0_EEEEESI_DpOT_EUlS7_E_EESI_S7_ENKUlS6_E_clINS1_IZNS_5StartIJZNS_4JustIJS19_S1C_EEESI_S1F_EUlvE_ZNS1K_IJS19_S1C_EEESI_S1F_EUlvE0_EEESI_S1F_EUlS7_E_EEEESI_S6_EUlS7_E_EEEESt6vectorIS6_SaIS6_EERKT0_NS_12ElementCountEbEUlS7_E_ZNSD_IiS1Q_EES1T_S1W_S1X_bEUlOS3_E_ZNSD_IiS1Q_EES1T_S1W_S1X_bEUlvE_EES1G_S1O_E25ConcatMapValuesSubscriberEEEDaS7_

[jingham]

That seems great. This would be the backing for the CPlusPlusLanguage::MethodName class (in lldb in Source/Plugins/Language/CPlusPlus/CPlusPlusLanguage.h). It looks like a great fit for that.

I can't think of anything else we really wanted out of these names that you aren't currently providing. Greg might. But this looks like a great start to me.

[clayborg]

Seems like it might be nice to replace all "char *Buf, size_t *N" arguments, where "char *" is returned with a llvm::raw_ostream and let the user use what ever backing / memory allocation scheme they want instead of forcing re-allocations? Probably best to include a person that has contributed to this file in the LLVM community so they can comment on the changes here.

llvm/include/llvm/Demangle/Demangle.h

42 ↗

(On Diff #139061)

Use "llvm::StringRef MangledName" instead of "const char *"?

46 ↗

(On Diff #139061)

Might be better to use a "llvm::raw_ostream &out" instead of just a plain buffer? Seems like llvm::raw_ostream can be backed by what ever kind of buffer you want it to be backed (llvm::raw_string_ostream is a nice thing to use with this that uses a std::string as the destination buffer).

54 ↗

(On Diff #139061)

Maybe rename to getFunctionDeclContext? or getFunctionDeclContextName?

64 ↗

(On Diff #139061)

s/provably/probably/ in comment and function name. Maybe "couldBeMemberFunction" might be a better name?

69 ↗

(On Diff #139061)

Can you document what a special name is here?

[clayborg]

Great stuff, thanks for doing this BTW

[erik.pilkington]

It would be awesome if you could benchmark on some pathological testcases (e.g. the one Greg was pointing out)

As of r327690, the pathological symbol Greg posted is much smaller, due to a bug in how the demangler parsed generic lambda parameters. Now, partially demangling that symbol and getting the basename "Subscribe" is about 20x faster than fully demangling the name. Just for fun I removed the fix and benchmarked it again and it was more in the ballpark of hundreds of thousands of times faster. For more realistic symbols (test case being all the symbols in LLVM), partially demangling and extracting the basename runs in about 40% less time than fully demangling. Partially demangling and splitting up the entire name runs in about as long as the full demangle, but it should be faster if LLDB avoids parsing the demangled name. Depending on how LLDB is consuming these names, it might be profitable to do a first pass to find the base names of all the symbols in the program, then lazily demangle the other components as needed.

Seems like it might be nice to replace all "char *Buf, size_t *N" arguments, where "char *" is returned with a llvm::raw_ostream and let the user use what ever backing / memory allocation scheme they want instead of forcing re-allocations? Probably best to include a person that has contributed to this file in the LLVM community so they can comment on the changes here.

@rafael: Any thoughts? I think it would be nice to use LLVM data structures to express this API and have the no-dependencies demangler live in libcxxabi.

Thanks!

llvm/include/llvm/Demangle/Demangle.h

64 ↗

(On Diff #139061)

That wasn't a typo, this function checks if the name is for sure a non-static member function, so it conservatively returns false for a::b(). I suppose isDefinitelyMemberFunction() might be more clear.

[clayborg]

llvm/include/llvm/Demangle/Demangle.h

64 ↗

(On Diff #139061)

Maybe just "isMemberFunction()" would be clear enough? Don't think Definitely needs to be in the name.

[labath]

This looks great. Thank you for doing this.

llvm/include/llvm/Demangle/Demangle.h

64 ↗

(On Diff #139061)

I think that having something in the name which indicates this is just a best-effort guess is a good idea.

Alternatively, we could replace this function with something more well-defined (getFunctionQualifiers ? hasFunctionQualifiers?) and leave the business of guessing the member-ness of the function to lldb.

[erik.pilkington]

In this new patch:

• Rename some functions, add some comments
• Support for local names
• More testcases

[erik.pilkington]

Use Rafael's Phab account.

llvm/include/llvm/Demangle/Demangle.h

42 ↗

(On Diff #139061)

On second thought, I don't think we can use LLVM data structures for this. libSupport depends on libDemangle, so using any LLVM stuff would create a circular dependency. (I'm basing this off the commit message for r328072)

46 ↗

(On Diff #139061)

This has the same problem as above, but also raw_ostream isn't compatible with our how the AST is printed (Sometimes the printer look back at the last char).

54 ↗

(On Diff #139061)

Sure, I called this getFunctionDeclContextName() in the new patch.

64 ↗

(On Diff #139061)

I agree it would be better to indicate that this is only a best effort guess. hasFunctionQualifiers sounds good, I renamed this function to that in the new patch.

[erik.pilkington]

Rebase. In this new patch:

• Add some more tests.
• Minor cleanup.

I think I'm happy with the implementation of this now, so I'll land it as long as this API looks okay.

[clayborg]

Looks good to me, but probably need someone that works on LLVM fulltime to give the final ok

[davide]

I don't have objections to this one either. Maybe @majnemer / @espindola / @rnk / @Bigcheese have comment on the API?

[erik.pilkington]

I'll CC @dexonsmith and @compnerd too, they've helped with demangler reviews in the past.

[• espindola]

I don't have an opinion on this.

[dexonsmith]

I'd prefer to have this be as close as possible to the libcxxabi demangler (and use the same data structures) so that it's easy to detect when they diverge. If we ever move to monorepo hopefully there will be a way to factor them out into a single implementation.

Since that's where this ended up, LGTM!

llvm/trunk/include/llvm/Demangle/Demangle.h

 ///   unknown_error: -4
 ///   invalid_args:  -3
 ///   invalid_mangled_name: -2
 ///   memory_alloc_failure: -1
 ///   success: 0
 
 char *itaniumDemangle(const char *mangled_name, char *buf, size_t *n,
                       int *status);
-}
+
+/// "Partial" demangler. This supports demangling a string into an AST
+/// (typically an intermediate stage in itaniumDemangle) and querying certain
+/// properties or partially printing the demangled name.
+struct ItaniumPartialDemangler {
+  ItaniumPartialDemangler();
+
+  ItaniumPartialDemangler(ItaniumPartialDemangler &&Other);
+  ItaniumPartialDemangler &operator=(ItaniumPartialDemangler &&Other);
+
+  /// Demangle into an AST. Subsequent calls to the rest of the member functions
+  /// implicitly operate on the AST this produces.
+  /// \return true on error, false otherwise
+  bool partialDemangle(const char *MangledName);
+
+  /// Just print the entire mangled name into Buf. Buf and N behave like the
+  /// second and third parameters to itaniumDemangle.
+  char *finishDemangle(char *Buf, size_t *N) const;
+
+  /// Get the base name of a function. This doesn't include trailing template
+  /// arguments, ie for "a::b<int>" this function returns "b".
+  char *getFunctionBaseName(char *Buf, size_t *N) const;
+
+  /// Get the context name for a function. For "a::b::c", this function returns
+  /// "a::b".
+  char *getFunctionDeclContextName(char *Buf, size_t *N) const;
+
+  /// Get the entire name of this function.
+  char *getFunctionName(char *Buf, size_t *N) const;
+
+  /// Get the parameters for this function.
+  char *getFunctionParameters(char *Buf, size_t *N) const;
+  char *getFunctionReturnType(char *Buf, size_t *N) const;
+
+  /// If this function has any any cv or reference qualifiers. These imply that
+  /// the function is a non-static member function.
+  bool hasFunctionQualifiers() const;
+
+  /// If this symbol describes a function.
+  bool isFunction() const;
+
+  /// If this symbol describes a variable.
+  bool isData() const;
+
+  /// If this symbol is a <special-name>. These are generally implicitly
+  /// generated by the implementation, such as vtables and typeinfo names.
+  bool isSpecialName() const;
+
+  ~ItaniumPartialDemangler();
+private:
+  void *RootNode;
+  void *Context;
+};
+} // namespace llvm

llvm/trunk/lib/Demangle/ItaniumDemangle.cpp

if (N != nullptr)
       *N = S.getCurrentPosition();
     Buf = S.getBuffer();
   }
 
   if (Status)
     *Status = InternalStatus;
   return InternalStatus == success ? Buf : nullptr;
 }
+
+namespace llvm {
+
+ItaniumPartialDemangler::ItaniumPartialDemangler()
+    : RootNode(nullptr), Context(new Db{nullptr, nullptr}) {}
+
+ItaniumPartialDemangler::~ItaniumPartialDemangler() {
+  delete static_cast<Db *>(Context);
+}
+
+ItaniumPartialDemangler::ItaniumPartialDemangler(
+    ItaniumPartialDemangler &&Other)
+    : RootNode(Other.RootNode), Context(Other.Context) {
+  Other.Context = Other.RootNode = nullptr;
+}
+
+ItaniumPartialDemangler &ItaniumPartialDemangler::
+operator=(ItaniumPartialDemangler &&Other) {
+  std::swap(RootNode, Other.RootNode);
+  std::swap(Context, Other.Context);
+  return *this;
+}
+
+// Demangle MangledName into an AST, storing it into this->RootNode.
+bool ItaniumPartialDemangler::partialDemangle(const char *MangledName) {
+  Db *Parser = static_cast<Db *>(Context);
+  size_t Len = std::strlen(MangledName);
+  Parser->reset(MangledName, MangledName + Len);
+  RootNode = Parser->parse();
+  return RootNode == nullptr;
+}
+
+static char *printNode(Node *RootNode, char *Buf, size_t *N) {
+  OutputStream S;
+  if (initializeOutputStream(Buf, N, S, 128))
+    return nullptr;
+  RootNode->print(S);
+  S += '\0';
+  if (N != nullptr)
+    *N = S.getCurrentPosition();
+  return S.getBuffer();
+}
+
+char *ItaniumPartialDemangler::getFunctionBaseName(char *Buf, size_t *N) const {
+  if (!isFunction())
+    return nullptr;
+
+  Node *Name = static_cast<FunctionEncoding *>(RootNode)->getName();
+
+  while (true) {
+    switch (Name->getKind()) {
+    case Node::KAbiTagAttr:
+      Name = static_cast<AbiTagAttr *>(Name)->Base;
+      continue;
+    case Node::KStdQualifiedName:
+      Name = static_cast<StdQualifiedName *>(Name)->Child;
+      continue;
+    case Node::KNestedName:
+      Name = static_cast<NestedName *>(Name)->Name;
+      continue;
+    case Node::KLocalName:
+      Name = static_cast<LocalName *>(Name)->Entity;
+      continue;
+    case Node::KNameWithTemplateArgs:
+      Name = static_cast<NameWithTemplateArgs *>(Name)->Name;
+      continue;
+    default:
+      return printNode(Name, Buf, N);
+    }
+  }
+}
+
+char *ItaniumPartialDemangler::getFunctionDeclContextName(char *Buf,
+                                                          size_t *N) const {
+  if (!isFunction())
+    return nullptr;
+  Node *Name = static_cast<FunctionEncoding *>(RootNode)->getName();
+
+  OutputStream S;
+  if (initializeOutputStream(Buf, N, S, 128))
+    return nullptr;
+
+ KeepGoingLocalFunction:
+  while (true) {
+    if (Name->getKind() == Node::KAbiTagAttr) {
+      Name = static_cast<AbiTagAttr *>(Name)->Base;
+      continue;
+    }
+    if (Name->getKind() == Node::KNameWithTemplateArgs) {
+      Name = static_cast<NameWithTemplateArgs *>(Name)->Name;
+      continue;
+    }
+    break;
+  }
+
+  switch (Name->getKind()) {
+  case Node::KStdQualifiedName:
+    S += "std";
+    break;
+  case Node::KNestedName:
+    static_cast<NestedName *>(Name)->Qual->print(S);
+    break;
+  case Node::KLocalName: {
+    auto *LN = static_cast<LocalName *>(Name);
+    LN->Encoding->print(S);
+    S += "::";
+    Name = LN->Entity;
+    goto KeepGoingLocalFunction;
+  }
+  default:
+    break;
+  }
+  S += '\0';
+  if (N != nullptr)
+    *N = S.getCurrentPosition();
+  return S.getBuffer();
+}
+
+char *ItaniumPartialDemangler::getFunctionName(char *Buf, size_t *N) const {
+  if (!isFunction())
+    return nullptr;
+  auto *Name = static_cast<FunctionEncoding *>(RootNode)->getName();
+  return printNode(Name, Buf, N);
+}
+
+char *ItaniumPartialDemangler::getFunctionParameters(char *Buf,
+                                                     size_t *N) const {
+  if (!isFunction())
+    return nullptr;
+  NodeArray Params = static_cast<FunctionEncoding *>(RootNode)->getParams();
+
+  OutputStream S;
+  if (initializeOutputStream(Buf, N, S, 128))
+    return nullptr;
+
+  S += '(';
+  Params.printWithComma(S);
+  S += ')';
+  S += '\0';
+  if (N != nullptr)
+    *N = S.getCurrentPosition();
+  return S.getBuffer();
+}
+
+char *ItaniumPartialDemangler::getFunctionReturnType(
+    char *Buf, size_t *N) const {
+  if (!isFunction())
+    return nullptr;
+
+  OutputStream S;
+  if (initializeOutputStream(Buf, N, S, 128))
+    return nullptr;
+
+  if (Node *Ret = static_cast<FunctionEncoding *>(RootNode)->getReturnType())
+    Ret->print(S);
+
+  S += '\0';
+  if (N != nullptr)
+    *N = S.getCurrentPosition();
+  return S.getBuffer();
+}
+
+char *ItaniumPartialDemangler::finishDemangle(char *Buf, size_t *N) const {
+  assert(RootNode != nullptr && "must call partialDemangle()");
+  return printNode(static_cast<Node *>(RootNode), Buf, N);
+}
+
+bool ItaniumPartialDemangler::hasFunctionQualifiers() const {
+  assert(RootNode != nullptr && "must call partialDemangle()");
+  if (!isFunction())
+    return false;
+  auto *E = static_cast<FunctionEncoding *>(RootNode);
+  return E->getCVQuals() != QualNone || E->getRefQual() != FrefQualNone;
+}
+
+bool ItaniumPartialDemangler::isFunction() const {
+  assert(RootNode != nullptr && "must call partialDemangle()");
+  return static_cast<Node *>(RootNode)->getKind() == Node::KFunctionEncoding;
+}
+
+bool ItaniumPartialDemangler::isSpecialName() const {
+  assert(RootNode != nullptr && "must call partialDemangle()");
+  auto K = static_cast<Node *>(RootNode)->getKind();
+  return K == Node::KSpecialName || K == Node::KCtorVtableSpecialName;
+}
+
+bool ItaniumPartialDemangler::isData() const {
+  return !isFunction() && !isSpecialName();
+}
+
+}

llvm/trunk/unittests/CMakeLists.txt

 add_custom_target(UnitTests)
 set_target_properties(UnitTests PROPERTIES FOLDER "Tests")
 
 function(add_llvm_unittest test_dirname)
   add_unittest(UnitTests ${test_dirname} ${ARGN})
 endfunction()
 
 add_subdirectory(ADT)
 add_subdirectory(Analysis)
 add_subdirectory(AsmParser)
 add_subdirectory(Bitcode)
 add_subdirectory(CodeGen)
 add_subdirectory(DebugInfo)
+add_subdirectory(Demangle)
 add_subdirectory(ExecutionEngine)
 add_subdirectory(FuzzMutate)
 add_subdirectory(IR)
 add_subdirectory(LineEditor)
 add_subdirectory(Linker)
 add_subdirectory(MC)
 add_subdirectory(MI)
 add_subdirectory(Object)

llvm/trunk/unittests/Demangle/CMakeLists.txt

+set(DemangleSources
+  PartialDemangleTest.cpp
+)
+
+add_llvm_unittest(DemangleTests
+  ${DemangleSources}
+)

llvm/trunk/unittests/Demangle/PartialDemangleTest.cpp

+//===----------------------- PartialDemangleTest.cpp ----------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include <cstdlib>
+#include "llvm/Demangle/Demangle.h"
+#include "gtest/gtest.h"
+
+struct ChoppedName {
+  const char *Mangled;
+  const char *ContextName, *BaseName, *ReturnType, *Params;
+};
+
+static ChoppedName NamesToTest[] = {
+  {"_Z1fv", "", "f", "", "()"},
+  {"_ZN1a1b1cIiiiEEvm", "a::b", "c", "void", "(unsigned long)"},
+  {"_ZZ5OuterIiEivEN5Inner12inner_memberEv",
+   "int Outer<int>()::Inner", "inner_member", "", "()"},
+  {"_Z1fIiEPFvvEv", "", "f", "void (*)()", "()"},
+  {"_ZN1S1fIiEEvv", "S", "f", "void", "()"},
+
+  // Call operator for a lambda in f().
+  {"_ZZ1fvENK3$_0clEi", "f()::$_0", "operator()", "", "(int)"},
+
+  // A call operator for a lambda in a lambda in f().
+  {"_ZZZ1fvENK3$_0clEvENKUlvE_clEv",
+   "f()::$_0::operator()() const::'lambda'()", "operator()", "", "()"},
+
+  {"_ZZN1S1fEiiEd0_NKUlvE_clEv",
+   "S::f(int, int)::'lambda'()", "operator()", "", "()"},
+
+  {"_ZN1Scv7MuncherIJDpPT_EEIJFivEA_iEEEv",
+   "S", "operator Muncher<int (*)(), int (*) []>", "", "()"},
+
+  // Attributes.
+  {"_ZN5test4IdE1fEUa9enable_ifIXeqfL0p_Li1EEXeqfL0p0_Li2EEEi",
+   "test4<double>", "f", "", "(int)"},
+  {"_ZN1SC2B8ctor_tagEv", "S", "S", "", "()"},
+  {"_ZN1S1fB4MERPIiEEvv", "S", "f", "void", "()"},
+
+  {"_ZNSsC1EmcRKSaIcE",
+   "std::basic_string<char, std::char_traits<char>, std::allocator<char> >",
+   "basic_string", "", "(unsigned long, char, std::allocator<char> const&)"},
+  {"_ZNSsixEm", "std::string", "operator[]", "", "(unsigned long)"},
+  {"_ZSt17__throw_bad_allocv", "std", "__throw_bad_alloc", "", "()"},
+
+  {"_ZN1AI1BEC2Ev", "A<B>", "A", "", "()"},
+  {"_ZN1AI1BED2Ev", "A<B>", "~A", "", "()"},
+  {"_ZN1AI1BECI24BaseEi", "A<B>", "A", "", "(int)"},
+  {"_ZNKR1AI1BE1fIiEEiv", "A<B>", "f", "int", "()"},
+
+  {"_ZN1SIJicfEE3mfnIJjcdEEEvicfDpT_", "S<int, char, float>",
+   "mfn", "void", "(int, char, float, unsigned int, char, double)"},
+};
+
+TEST(PartialDemangleTest, TestNameChopping) {
+  size_t Size = 1;
+  char *Buf = static_cast<char *>(std::malloc(Size));
+
+  llvm::ItaniumPartialDemangler D;
+
+  for (ChoppedName &N : NamesToTest) {
+    EXPECT_FALSE(D.partialDemangle(N.Mangled));
+    EXPECT_TRUE(D.isFunction());
+    EXPECT_FALSE(D.isData());
+    EXPECT_FALSE(D.isSpecialName());
+
+    Buf = D.getFunctionDeclContextName(Buf, &Size);
+    EXPECT_STREQ(Buf, N.ContextName);
+
+    Buf = D.getFunctionBaseName(Buf, &Size);
+    EXPECT_STREQ(Buf, N.BaseName);
+
+    Buf = D.getFunctionReturnType(Buf, &Size);
+    EXPECT_STREQ(Buf, N.ReturnType);
+
+    Buf = D.getFunctionParameters(Buf, &Size);
+    EXPECT_STREQ(Buf, N.Params);
+  }
+}
+
+TEST(PartialDemangleTest, TestNameMeta) {
+  llvm::ItaniumPartialDemangler Demangler;
+
+  EXPECT_FALSE(Demangler.partialDemangle("_ZNK1f1gEv"));
+  EXPECT_TRUE(Demangler.isFunction());
+  EXPECT_TRUE(Demangler.hasFunctionQualifiers());
+  EXPECT_FALSE(Demangler.isSpecialName());
+  EXPECT_FALSE(Demangler.isData());
+
+  EXPECT_FALSE(Demangler.partialDemangle("_Z1fv"));
+  EXPECT_FALSE(Demangler.hasFunctionQualifiers());
+
+  EXPECT_FALSE(Demangler.partialDemangle("_ZTV1S"));
+  EXPECT_TRUE(Demangler.isSpecialName());
+  EXPECT_FALSE(Demangler.isData());
+  EXPECT_FALSE(Demangler.isFunction());
+
+  EXPECT_FALSE(Demangler.partialDemangle("_ZN1aDC1a1b1cEE"));
+  EXPECT_FALSE(Demangler.isFunction());
+  EXPECT_FALSE(Demangler.isSpecialName());
+  EXPECT_TRUE(Demangler.isData());
+}
+
+TEST(PartialDemanglerTest, TestMisc) {
+  llvm::ItaniumPartialDemangler D1, D2;
+
+  EXPECT_FALSE(D1.partialDemangle("_Z1fv"));
+  EXPECT_FALSE(D2.partialDemangle("_Z1g"));
+  std::swap(D1, D2);
+  EXPECT_FALSE(D1.isFunction());
+  EXPECT_TRUE(D2.isFunction());
+
+  EXPECT_TRUE(D1.partialDemangle("Not a mangled name!"));
+
+}