CPlusPlusLanguage: Use new demangler API to implement type substitution

[labath]

Summary

Now that llvm demangler supports more generic customization, we can
implement type substitution directly on top of this API. This will allow
us to remove the specialized hooks which were added to the demangler to
support this use case.

[sgraenitz]

Hi Pavel, thanks for working on this. The code looks really great. I have no actual concerns about landing it like this.

Two minor remarks:

• We still have no coverage for substitution failures in CPlusPlusLanguageTest.cpp test case FindAlternateFunctionManglings.
• We create a new BumpPtrAllocator for each TypeSubstitutor::substitute(), right? Well, the impact on performance is probably on a different order of magnitude than we are concerned about here.

This will allow us to remove the specialized hooks which were added to the demangler to support this use case.

Right, it bridged the time between removing FastDemangle from LLDB and getting the new ManglingParser in LLVM. IIUC this basically means reverting https://reviews.llvm.org/D50586.

[labath]

Thanks for the review.

I think that creating the new BumpPtrAllocator every call doesn't matter much here, this function
get's called only on a few symbols for each evaluated expression. However, it also wasn't too
hard to reuse it (at least at the level of FindAlternateFunctionManglings), so I just did that.

I also added a simple failure test for this function.

[sgraenitz]

Nice. For parameter lists of reset and substitute indentation could be fixed, but otherwise this looks really good to me.

[erik.pilkington]

Looks good to me too, thanks!

[shafik]

source/Plugins/Language/CPlusPlus/CPlusPlusLanguage.cpp

336 ↗

(On Diff #172583)

Can you just use numLeft() here? It would be less opaque.

337 ↗

(On Diff #172583)

also First - Written is used twice but it is not obvious what the means, naming it via a member function might be helpful.

[sgraenitz]

source/Plugins/Language/CPlusPlus/CPlusPlusLanguage.cpp

337 ↗

(On Diff #172583)

First points to the first char of the input (Mangled).
Written points to the char of the input, up until we have constructed the respective output already.

Quite similar to the previous implementation. Difference is: it used a std::back_insert_iterator, but I wouldn't say that made it simpler. Intelligibility may benefit from comment as in the past:

// Write the unmatched part of the original. Then write the
// replacement string. Finally skip the search string in the original.

IMHO it's not a high prio.

[labath]

Thanks for the review. I have added some comments, and moved appending of the unmodified portion of the name into a separate function to aid readability.

[shafik]

Much better, thank you!

lldb/trunk/source/Plugins/Language/CPlusPlus/CPlusPlusLanguage.cpp

 // C++ Includes
 #include <functional>
 #include <memory>
 #include <mutex>
 #include <set>
 
 // Other libraries and framework includes
 #include "llvm/ADT/StringRef.h"
-#include "llvm/Demangle/Demangle.h"
+#include "llvm/Demangle/ItaniumDemangle.h"
 
 // Project includes
 #include "lldb/Core/PluginManager.h"
 #include "lldb/Core/UniqueCStringMap.h"
 #include "lldb/DataFormatters/CXXFunctionPointer.h"
 #include "lldb/DataFormatters/DataVisualization.h"
 #include "lldb/DataFormatters/FormattersHelpers.h"
 #include "lldb/DataFormatters/VectorType.h"
bool CPlusPlusLanguage::ExtractContextAndIdentifier(
   if (auto full_name = parser.ParseAsFullName()) {
     identifier = full_name.getValue().basename;
     context = full_name.getValue().context;
     return true;
   }
   return false;
 }
 
-/// Given a mangled function `mangled`, replace all the primitive function type
-/// arguments of `search` with type `replace`.
-static ConstString SubsPrimitiveParmItanium(llvm::StringRef mangled,
-                                            llvm::StringRef search,
-                                            llvm::StringRef replace) {
-  class PrimitiveParmSubs {
-    llvm::StringRef mangled;
-    llvm::StringRef search;
-    llvm::StringRef replace;
-    ptrdiff_t read_pos;
-    std::string output;
-    std::back_insert_iterator<std::string> writer;
+namespace {
+class NodeAllocator {
+  llvm::BumpPtrAllocator Alloc;
 
-  public:
-    PrimitiveParmSubs(llvm::StringRef m, llvm::StringRef s, llvm::StringRef r)
-        : mangled(m), search(s), replace(r), read_pos(0),
-          writer(std::back_inserter(output)) {}
+  void reset() { Alloc.Reset(); }
 
-    void Substitute(llvm::StringRef tail) {
-      assert(tail.data() >= mangled.data() &&
-             tail.data() < mangled.data() + mangled.size() &&
-             "tail must point into range of mangled");
-
-      if (tail.startswith(search)) {
-        auto reader = mangled.begin() + read_pos;
-        ptrdiff_t read_len = tail.data() - (mangled.data() + read_pos);
-
-        // First write the unmatched part of the original. Then write the
-        // replacement string. Finally skip the search string in the original.
-        writer = std::copy(reader, reader + read_len, writer);
-        writer = std::copy(replace.begin(), replace.end(), writer);
-        read_pos += read_len + search.size();
-      }
-    }
+  template <typename T, typename... Args> T *makeNode(Args &&... args) {
+    return new (Alloc.Allocate(sizeof(T), alignof(T)))
+        T(std::forward<Args>(args)...);
 
-    ConstString Finalize() {
-      // If we did a substitution, write the remaining part of the original.
-      if (read_pos > 0) {
-        writer = std::copy(mangled.begin() + read_pos, mangled.end(), writer);
-        read_pos = mangled.size();
-      }
+  void *allocateNodeArray(size_t sz) {
+    return Alloc.Allocate(sizeof(llvm::itanium_demangle::Node *) * sz,
+                          alignof(llvm::itanium_demangle::Node *));
+};
 
-      return ConstString(output);
-    }
+/// Given a mangled function `Mangled`, replace all the primitive function type
+/// arguments of `Search` with type `Replace`.
+class TypeSubstitutor
+    : public llvm::itanium_demangle::AbstractManglingParser<TypeSubstitutor,
+                                                            NodeAllocator> {
+  /// Input character until which we have constructed the respective output
+  /// already
+  const char *Written;
+
+  llvm::StringRef Search;
+  llvm::StringRef Replace;
+  llvm::SmallString<128> Result;
+
+  /// Whether we have performed any substitutions.
+  bool Substituted;
+
+  void reset(llvm::StringRef Mangled, llvm::StringRef Search,
+             llvm::StringRef Replace) {
+    AbstractManglingParser::reset(Mangled.begin(), Mangled.end());
+    Written = Mangled.begin();
+    this->Search = Search;
+    this->Replace = Replace;
+    Result.clear();
+    Substituted = false;
+  }
+
+  void appendUnchangedInput() {
+    Result += llvm::StringRef(Written, First - Written);
+    Written = First;
 
-    static void Callback(void *context, const char *match) {
-      ((PrimitiveParmSubs *)context)->Substitute(llvm::StringRef(match));
+public:
+  TypeSubstitutor() : AbstractManglingParser(nullptr, nullptr) {}
+
+  ConstString substitute(llvm::StringRef Mangled, llvm::StringRef From,
+                         llvm::StringRef To) {
+    Log *log = GetLogIfAllCategoriesSet(LIBLLDB_LOG_LANGUAGE);
+
+    reset(Mangled, From, To);
+    if (parse() == nullptr) {
+      LLDB_LOG(log, "Failed to substitute mangling in {0}", Mangled);
+      return ConstString();
     }
-  };
+    if (!Substituted)
+      return ConstString();
 
-  // The demangler will call back for each instance of a primitive type,
-  // allowing us to perform substitution
-  PrimitiveParmSubs parmSubs(mangled, search, replace);
-  assert(mangled.data()[mangled.size()] == '\0' && "Expect C-String");
-  bool err = llvm::itaniumFindTypesInMangledName(mangled.data(), &parmSubs,
-                                                 PrimitiveParmSubs::Callback);
-  ConstString result = parmSubs.Finalize();
-
-  if (Log *log = GetLogIfAllCategoriesSet(LIBLLDB_LOG_LANGUAGE)) {
-    if (err)
-      LLDB_LOG(log, "Failed to substitute mangling in {0}", mangled);
-    else if (result)
-      LLDB_LOG(log, "Substituted mangling {0} -> {1}", mangled, result);
+    // Append any trailing unmodified input.
+    appendUnchangedInput();
+    LLDB_LOG(log, "Substituted mangling {0} -> {1}", Mangled, Result);
+    return ConstString(Result);
   }
 
-  return result;
+  llvm::itanium_demangle::Node *parseType() {
+    if (llvm::StringRef(First, numLeft()).startswith(Search)) {
+      // We found a match. Append unmodified input up to this point.
+      appendUnchangedInput();
+
+      // And then perform the replacement.
+      Result += Replace;
+      Written += Search.size();
+      Substituted = true;
+    }
+    return AbstractManglingParser::parseType();
+  }
+};
 }
 
 uint32_t CPlusPlusLanguage::FindAlternateFunctionManglings(
     const ConstString mangled_name, std::set<ConstString> &alternates) {
   const auto start_size = alternates.size();
   /// Get a basic set of alternative manglings for the given symbol `name`, by
   /// making a few basic possible substitutions on basic types, storage duration
   /// and `const`ness for the given symbol. The output parameter `alternates`
uint32_t CPlusPlusLanguage::FindAlternateFunctionManglings(
   // Maybe we're looking for a static symbol but we thought it was global...
   if (!strncmp(mangled_name.GetCString(), "_Z", 2) &&
       strncmp(mangled_name.GetCString(), "_ZL", 3)) {
     std::string fixed_scratch("_ZL");
     fixed_scratch.append(mangled_name.GetCString() + 2);
     alternates.insert(ConstString(fixed_scratch));
   }
 
+  TypeSubstitutor TS;
   // `char` is implementation defined as either `signed` or `unsigned`.  As a
   // result a char parameter has 3 possible manglings: 'c'-char, 'a'-signed
   // char, 'h'-unsigned char.  If we're looking for symbols with a signed char
   // parameter, try finding matches which have the general case 'c'.
   if (ConstString char_fixup =
-          SubsPrimitiveParmItanium(mangled_name.GetStringRef(), "a", "c"))
+          TS.substitute(mangled_name.GetStringRef(), "a", "c"))
     alternates.insert(char_fixup);
 
   // long long parameter mangling 'x', may actually just be a long 'l' argument
   if (ConstString long_fixup =
-          SubsPrimitiveParmItanium(mangled_name.GetStringRef(), "x", "l"))
+          TS.substitute(mangled_name.GetStringRef(), "x", "l"))
     alternates.insert(long_fixup);
 
   // unsigned long long parameter mangling 'y', may actually just be unsigned
   // long 'm' argument
   if (ConstString ulong_fixup =
-          SubsPrimitiveParmItanium(mangled_name.GetStringRef(), "y", "m"))
+          TS.substitute(mangled_name.GetStringRef(), "y", "m"))
     alternates.insert(ulong_fixup);
 
   return alternates.size() - start_size;
 }
 
 static void LoadLibCxxFormatters(lldb::TypeCategoryImplSP cpp_category_sp) {
   if (!cpp_category_sp)
     return;

lldb/trunk/unittests/Language/CPlusPlus/CPlusPlusLanguageTest.cpp

TEST(CPlusPlusLanguage, FindAlternateFunctionManglings) {
   using namespace testing;
 
   EXPECT_THAT(FindAlternate("_ZN1A1fEv"),
               UnorderedElementsAre("_ZNK1A1fEv", "_ZLN1A1fEv"));
   EXPECT_THAT(FindAlternate("_ZN1A1fEa"), Contains("_ZN1A1fEc"));
   EXPECT_THAT(FindAlternate("_ZN1A1fEx"), Contains("_ZN1A1fEl"));
   EXPECT_THAT(FindAlternate("_ZN1A1fEy"), Contains("_ZN1A1fEm"));
   EXPECT_THAT(FindAlternate("_ZN1A1fEai"), Contains("_ZN1A1fEci"));
+  EXPECT_THAT(FindAlternate("_bogus"), IsEmpty());
 }