[Demangle] Add itaniumFindTypesInMangledName()

[erik.pilkington]

Summary

This enables parameter type substitutions for mangled names in LLDB.
Thanks Erik for the patch!

[sgraenitz]

The respective LLDB patch is here: https://reviews.llvm.org/D50587

[erik.pilkington]

I'll commandeer this so I can upload a patch with a test!

[erik.pilkington]

Add a test, libcxxabi changes.

[labath]

I've recently ran into another case where I've needed to modify a mangled name.

In short, the problem was that clang does not bother emitting complete object constructors (C1) when they are linkonce_odr, this causes a problem for us in expression evaluation, since it's then never possible to construct these objects in the expression. After my attempts to get clang (D46685) to emit these C1 symbols always resulted in code size regressions, we started looking at ways to fix this elsewhere. One of the possibilities was to substitute the C1 for the C2 version when we know they are identical. However, for this to work, I'd need a) to know whether a symbol is C1 or C2; b) modify the symbol from C1 to C2.

Doing things this way, would require adding more hooks to the demangler, which does not seem particularly nice. OTOH, exposing the AST would allow other interesting uses too. (For example, sometimes the mangled name actually contains more information than debug info -- debug info will describe a template function as foo<int>(int), but it will not tell you whether the int argument is actually the template parameter of the function, or if it's just a static type. This currently causes problems for us when trying to round-trip these functions into clang AST. If we could understand the structure of the mangled name (which preserves this kind of information), we could do a better job at supporting these functions).

I've put up my work so far at https://reviews.llvm.org/D50599. It is still very WIP, but I believe it's enough to show the general direction of where I'm heading with this. Unfortunately, I don't think I'll have the time in the next 2-3 weeks to complete that patch, but I wanted to show a possible alternative to the approach taken here (and see if it's even worth trying to complete that patch).

[sgraenitz]

I'll commandeer this so I can upload a patch with a test!
Add a test, libcxxabi changes.

Sure, thanks for adding this.

Doing things this way, would require adding more hooks to the demangler, which does not seem particularly nice. OTOH, exposing the AST would allow other interesting uses too. ...

Yes, I am totally with you. Doing this on an exposed AST adds lots of potential, but it also seems like a bigger functional change to me, which requires proper planning and feature discussions. Thus, I am in favour of doing things step by step here. I'd first mimic the old LLDB behaviour with the new demangler and remove FastDemangle from LLDB. Afterwards we can plan and discuss at which places and for which extended functionality we can make use of an exposed AST.

In the meantime, I think llvm::itaniumFindTypesInMangledName() even adds value on its own as it's a simple way to visit parameter types in a mangled name.

What do you think?

I've put up my work so far at https://reviews.llvm.org/D50599. It is still very WIP, but I believe it's enough to show the general direction of where I'm heading with this.

Thanks for sharing this! I will have a closer look asap.

[labath]

In D50586#1197041, @sgraenitz wrote:

Doing things this way, would require adding more hooks to the demangler, which does not seem particularly nice. OTOH, exposing the AST would allow other interesting uses too. ...

Yes, I am totally with you. Doing this on an exposed AST adds lots of potential, but it also seems like a bigger functional change to me, which requires proper planning and feature discussions. Thus, I am in favour of doing things step by step here. I'd first mimic the old LLDB behaviour with the new demangler and remove FastDemangle from LLDB. Afterwards we can plan and discuss at which places and for which extended functionality we can make use of an exposed AST.

In the meantime, I think llvm::itaniumFindTypesInMangledName() even adds value on its own as it's a simple way to visit parameter types in a mangled name.

What do you think?

I think that's up to Erik mostly. Doing things this way definitely makes LLDB's life easier, but OTOH, I am generally trying to avoid cleaning up LLDB by pushing the mess into LLVM. This is not a particularly large mess, but it still a very odd specialized api that will only ever be used by a single customer.

I agree that the AST thing is a much bigger change, and originally I was planning to send an email to llvm-dev first (and probably I will at some point) after I clean things up, but your patches kinda forced my hand (I thought it was important for you to know that this is not a one-off thing, but there are other use cases for transforming mangled names). FWIW, I am fine with this going in and then being backed out once the more general framework is in, or just poking another hole for constructors if exposing the AST does not seem a good idea. That's particularly true as I cannot make much progress on that patch this week (though if either of you wants to pick that up, I wouldn't be offended :)).

[sgraenitz]

Function for quite specialised use, but the implementation is simple and straightforward. LGTM

For my use case in LLDB this is perfect and we would like to use the functionality at least for a time. Pavel is right that exposing the AST (or implementing a more general visitor pattern etc.) would be very useful for many things in LLDB and probably other places around LLVM too, but I only know little about the details yet. For a good design we should take proper time. If we do that and if it all works out, then in the end this function may become obsolete again, right. My proposal for this case would be to keep FindTypesInMangledNameTest and reimplement itaniumFindTypesInMangledName locally in the test file with whatever tools we have by that time. I am happy to make the effort.

@erik.pilkington What do you think?

llvm/unittests/Demangle/FindTypesInMangledNameTest.cpp

33

Well f(int&*, void) is maybe not the most practical example, but the mangled name alone should be valid :)

[erik.pilkington]

I think that's up to Erik mostly. Doing things this way definitely makes LLDB's life easier, but OTOH, I am generally trying to avoid cleaning up LLDB by pushing the mess into LLVM. This is not a particularly large mess, but it still a very odd specialized api that will only ever be used by a single customer.

That's true, and we should probably look for a cleaner way of doing this. At the moment though, I think that adding this (small) hack so we can remove the big hack that is FastDemangle is a really good tradeoff.

I agree that the AST thing is a much bigger change, and originally I was planning to send an email to llvm-dev first (and probably I will at some point) after I clean things up, but your patches kinda forced my hand (I thought it was important for you to know that this is not a one-off thing, but there are other use cases for transforming mangled names). FWIW, I am fine with this going in and then being backed out once the more general framework is in, or just poking another hole for constructors if exposing the AST does not seem a good idea. That's particularly true as I cannot make much progress on that patch this week (though if either of you wants to pick that up, I wouldn't be offended :)).

Okay, look forward to seeing what you come up with!

[erik.pilkington]

In D50586#1197261, @sgraenitz wrote:

For my use case in LLDB this is perfect and we would like to use the functionality at least for a time. Pavel is right that exposing the AST (or implementing a more general visitor pattern etc.) would be very useful for many things in LLDB and probably other places around LLVM too, but I only know little about the details yet. For a good design we should take proper time. If we do that and if it all works out, then in the end this function may become obsolete again, right. My proposal for this case would be to keep FindTypesInMangledNameTest and reimplement itaniumFindTypesInMangledName locally in the test file with whatever tools we have by that time. I am happy to make the effort.

@erik.pilkington What do you think?

Sounds good! I'll commit this so you can move forward with the dependent patch.

llvm/unittests/Demangle/FindTypesInMangledNameTest.cpp

33

Oh, my mistake! I'll fix that in the commit.

libcxxabi/src/cxa_demangle.cpp

   // This has a smaller size compared to Subs and Names because it can be
   // stored on the stack.
   PODSmallVector<Node *, 8> TemplateParams;
 
   // Set of unresolved forward <template-param> references. These can occur in a
   // conversion operator's type, and are resolved in the enclosing <encoding>.
   PODSmallVector<ForwardTemplateReference *, 4> ForwardTemplateRefs;
 
+  void (*TypeCallback)(void *, const char *) = nullptr;
+  void *TypeCallbackContext = nullptr;
+
   bool TryToParseTemplateArgs = true;
   bool PermitForwardTemplateReferences = false;
   bool ParsingLambdaParams = false;
 
   BumpPointerAllocator ASTAllocator;
 
   Db(const char *First_, const char *Last_) : First(First_), Last(Last_) {}
 

 // extension   ::= U <objc-name> <objc-type>  # objc-type<identifier>
 // extension   ::= <vector-type> # <vector-type> starts with Dv
 //
 // <objc-name> ::= <k0 number> objcproto <k1 number> <identifier>  # k0 = 9 + <number of digits in k1> + k1
 // <objc-type> ::= <source-name>  # PU<11+>objcproto 11objc_object<source-name> 11objc_object -> id<source-name>
 Node *Db::parseType() {
   Node *Result = nullptr;
 
+  if (TypeCallback != nullptr)
+    TypeCallback(TypeCallbackContext, First);
+
   switch (look()) {
   //             ::= <qualified-type>
   case 'r':
   case 'V':
   case 'K': {
     unsigned AfterQuals = 0;
     if (look(AfterQuals) == 'r') ++AfterQuals;
     if (look(AfterQuals) == 'V') ++AfterQuals;

llvm/include/llvm/Demangle/Demangle.h

enum : int {
   demangle_invalid_mangled_name = -2,
   demangle_memory_alloc_failure = -1,
   demangle_success = 0,
 };
 
 char *itaniumDemangle(const char *mangled_name, char *buf, size_t *n,
                       int *status);
 
+/// Calls the callback \c Callback with \c Ctx as an argument whenever a type is
+/// encountered. Returns true if \c MangledName couldn't be parsed.
+bool itaniumFindTypesInMangledName(const char *MangledName, void *Ctx,
+                                   void (*Callback)(void *, const char *));
+
+
 enum MSDemangleFlags { MSDF_None = 0, MSDF_DumpBackrefs = 1 << 0 };
 char *microsoftDemangle(const char *mangled_name, char *buf, size_t *n,
                         int *status, MSDemangleFlags Flags = MSDF_None);
 
 /// "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 {

llvm/lib/Demangle/ItaniumDemangle.cpp

   // This has a smaller size compared to Subs and Names because it can be
   // stored on the stack.
   PODSmallVector<Node *, 8> TemplateParams;
 
   // Set of unresolved forward <template-param> references. These can occur in a
   // conversion operator's type, and are resolved in the enclosing <encoding>.
   PODSmallVector<ForwardTemplateReference *, 4> ForwardTemplateRefs;
 
+  void (*TypeCallback)(void *, const char *) = nullptr;
+  void *TypeCallbackContext = nullptr;
+
   bool TryToParseTemplateArgs = true;
   bool PermitForwardTemplateReferences = false;
   bool ParsingLambdaParams = false;
 
   BumpPointerAllocator ASTAllocator;
 
   Db(const char *First_, const char *Last_) : First(First_), Last(Last_) {}
 

 // extension   ::= U <objc-name> <objc-type>  # objc-type<identifier>
 // extension   ::= <vector-type> # <vector-type> starts with Dv
 //
 // <objc-name> ::= <k0 number> objcproto <k1 number> <identifier>  # k0 = 9 + <number of digits in k1> + k1
 // <objc-type> ::= <source-name>  # PU<11+>objcproto 11objc_object<source-name> 11objc_object -> id<source-name>
 Node *Db::parseType() {
   Node *Result = nullptr;
 
+  if (TypeCallback != nullptr)
+    TypeCallback(TypeCallbackContext, First);
+
   switch (look()) {
   //             ::= <qualified-type>
   case 'r':
   case 'V':
   case 'K': {
     unsigned AfterQuals = 0;
     if (look(AfterQuals) == 'r') ++AfterQuals;
     if (look(AfterQuals) == 'V') ++AfterQuals;

     Buf = S.getBuffer();
   }
 
   if (Status)
     *Status = InternalStatus;
   return InternalStatus == demangle_success ? Buf : nullptr;
 }
 
+bool llvm::itaniumFindTypesInMangledName(const char *MangledName, void *Ctx,
+                                         void (*Callback)(void *,
+                                                          const char *)) {
+  Db Parser(MangledName, MangledName + std::strlen(MangledName));
+  Parser.TypeCallback = Callback;
+  Parser.TypeCallbackContext = Ctx;
+  return Parser.parse() == nullptr;
+}
+
 namespace llvm {
 
 ItaniumPartialDemangler::ItaniumPartialDemangler()
     : RootNode(nullptr), Context(new Db{nullptr, nullptr}) {}
 
 ItaniumPartialDemangler::~ItaniumPartialDemangler() {
   delete static_cast<Db *>(Context);
 }

   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/unittests/Demangle/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Demangle
 )
 
 add_llvm_unittest(DemangleTests
   PartialDemangleTest.cpp
+  FindTypesInMangledNameTest.cpp
 )

llvm/unittests/Demangle/FindTypesInMangledNameTest.cpp

+//===------------------ FindTypesInMangledNameTest.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 <vector>
+#include "llvm/Demangle/Demangle.h"
+#include "gtest/gtest.h"
+
+TEST(FindTypesInMangledNameTest, Test) {
+  std::vector<const char *> Types;
+  const char *Mangled = "_Z1fiv";
+  EXPECT_FALSE(llvm::itaniumFindTypesInMangledName(
+      Mangled, static_cast<void *>(&Types), +[](void *Ty, const char *P) {
+        static_cast<std::vector<const char *> *>(Ty)->push_back(P);
+      }));
+  EXPECT_EQ(Types.size(), size_t(2));
+  EXPECT_EQ(Mangled + 4, Types.front());
+  EXPECT_EQ(Mangled + 5, Types.back());
+
+  EXPECT_TRUE(llvm::itaniumFindTypesInMangledName(
+      "Not a mangled name!", nullptr, +[](void *, const char *) {}));
+
+  int TC = 0;
+  EXPECT_FALSE(llvm::itaniumFindTypesInMangledName(
+      "_Z1fPRiv", static_cast<void *>(&TC),
+      +[](void *Ctx, const char *) { ++*static_cast<int *>(Ctx); }));
+  EXPECT_EQ(TC, 4); // pointer, reference, int, void.
+}

llvm/unittests/Demangle/PartialDemangleTest.cpp

static ChoppedName NamesToTest[] = {
   {"_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) {
+TEST(PartialDemanglerTest, 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());
for (ChoppedName &N : NamesToTest) {
 
     Buf = D.getFunctionParameters(Buf, &Size);
     EXPECT_STREQ(Buf, N.Params);
   }
 
   std::free(Buf);
 }
 
-TEST(PartialDemangleTest, TestNameMeta) {
+TEST(PartialDemanglerTest, 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());