[lldb][DWARFIndex] Use IDX_parent to implement GetFullyQualifiedType query (#79932)

This commit changes DebugNamesDWARFIndex so that it now overrides
`GetFullyQualifiedType` and attempts to use DW_IDX_parent, when
available, to speed up such queries. When this type of information is
not available, the base-class implementation is used.

With this commit, we now achieve the 4x speedups reported in [1].

[1]:
https://discourse.llvm.org/t/rfc-improve-dwarf-5-debug-names-type-lookup-parsing-speed/74151/38

4 files changed, 119 insertions, 0 deletions

diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDeclContext.h b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDeclContext.h
index a20a862..7e6c5f5 100644
--- a/lldb/source/Plugins/SymbolFile/DWARF/DWARFDeclContext.h
+++ b/lldb/source/Plugins/SymbolFile/DWARF/DWARFDeclContext.h
@@ -47,6 +47,10 @@ public:
 
   DWARFDeclContext() : m_entries() {}
 
+  DWARFDeclContext(llvm::ArrayRef<Entry> entries) {
+    llvm::append_range(m_entries, entries);
+  }
+
   void AppendDeclContext(dw_tag_t tag, const char *name) {
     m_entries.push_back(Entry(tag, name));
   }
diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp b/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp
index b718f98..4da0d56 100644
--- a/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp
+++ b/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.cpp
@@ -13,6 +13,7 @@
 #include "lldb/Core/Module.h"
 #include "lldb/Utility/RegularExpression.h"
 #include "lldb/Utility/Stream.h"
+#include "llvm/ADT/Sequence.h"
 #include <optional>
 
 using namespace lldb_private;
@@ -218,6 +219,108 @@ void DebugNamesDWARFIndex::GetCompleteObjCClass(
   m_fallback.GetCompleteObjCClass(class_name, must_be_implementation, callback);
 }
 
+namespace {
+using Entry = llvm::DWARFDebugNames::Entry;
+
+/// If `entry` and all of its parents have an `IDX_parent`, use that information
+/// to build and return a list of at most `max_parents` parent Entries.
+/// `entry` itself is not included in the list.
+/// If any parent does not have an `IDX_parent`, or the Entry data is corrupted,
+/// nullopt is returned.
+std::optional<llvm::SmallVector<Entry, 4>>
+getParentChain(Entry entry, uint32_t max_parents) {
+  llvm::SmallVector<Entry, 4> parent_entries;
+
+  do {
+    if (!entry.hasParentInformation())
+      return std::nullopt;
+
+    llvm::Expected<std::optional<Entry>> parent = entry.getParentDIEEntry();
+    if (!parent) {
+      // Bad data.
+      LLDB_LOG_ERROR(
+          GetLog(DWARFLog::Lookups), parent.takeError(),
+          "Failed to extract parent entry from a non-empty IDX_parent");
+      return std::nullopt;
+    }
+
+    // Last parent in the chain.
+    if (!parent->has_value())
+      break;
+
+    parent_entries.push_back(**parent);
+    entry = **parent;
+  } while (parent_entries.size() < max_parents);
+
+  return parent_entries;
+}
+} // namespace
+
+void DebugNamesDWARFIndex::GetFullyQualifiedType(
+    const DWARFDeclContext &context,
+    llvm::function_ref<bool(DWARFDIE die)> callback) {
+  if (context.GetSize() == 0)
+    return;
+
+  llvm::StringRef leaf_name = context[0].name;
+  llvm::SmallVector<llvm::StringRef> parent_names;
+  for (auto idx : llvm::seq<int>(1, context.GetSize()))
+    parent_names.emplace_back(context[idx].name);
+
+  // For each entry, grab its parent chain and check if we have a match.
+  for (const DebugNames::Entry &entry :
+       m_debug_names_up->equal_range(leaf_name)) {
+    if (!isType(entry.tag()))
+      continue;
+
+    // Grab at most one extra parent, subsequent parents are not necessary to
+    // test equality.
+    std::optional<llvm::SmallVector<Entry, 4>> parent_chain =
+        getParentChain(entry, parent_names.size() + 1);
+
+    if (!parent_chain) {
+      // Fallback: use the base class implementation.
+      if (!ProcessEntry(entry, [&](DWARFDIE die) {
+            return GetFullyQualifiedTypeImpl(context, die, callback);
+          }))
+        return;
+      continue;
+    }
+
+    if (SameParentChain(parent_names, *parent_chain) &&
+        !ProcessEntry(entry, callback))
+      return;
+  }
+}
+
+bool DebugNamesDWARFIndex::SameParentChain(
+    llvm::ArrayRef<llvm::StringRef> parent_names,
+    llvm::ArrayRef<DebugNames::Entry> parent_entries) const {
+
+  if (parent_entries.size() != parent_names.size())
+    return false;
+
+  auto SameAsEntryATName = [this](llvm::StringRef name,
+                                  const DebugNames::Entry &entry) {
+    // Peek at the AT_name of `entry` and test equality to `name`.
+    auto maybe_dieoffset = entry.getDIEUnitOffset();
+    if (!maybe_dieoffset)
+      return false;
+    auto die_ref = ToDIERef(entry);
+    if (!die_ref)
+      return false;
+    return name == m_debug_info.PeekDIEName(*die_ref);
+  };
+
+  // If the AT_name of any parent fails to match the expected name, we don't
+  // have a match.
+  for (auto [parent_name, parent_entry] :
+       llvm::zip_equal(parent_names, parent_entries))
+    if (!SameAsEntryATName(parent_name, parent_entry))
+      return false;
+  return true;
+}
+
 void DebugNamesDWARFIndex::GetTypes(
     ConstString name, llvm::function_ref<bool(DWARFDIE die)> callback) {
   for (const DebugNames::Entry &entry :
diff --git a/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h b/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h
index cca0913..b54dd11 100644
--- a/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h
+++ b/lldb/source/Plugins/SymbolFile/DWARF/DebugNamesDWARFIndex.h
@@ -42,6 +42,11 @@ public:
   void GetCompleteObjCClass(
       ConstString class_name, bool must_be_implementation,
       llvm::function_ref<bool(DWARFDIE die)> callback) override;
+
+  /// Uses DWARF5's IDX_parent fields, when available, to speed up this query.
+  void GetFullyQualifiedType(
+      const DWARFDeclContext &context,
+      llvm::function_ref<bool(DWARFDIE die)> callback) override;
   void GetTypes(ConstString name,
                 llvm::function_ref<bool(DWARFDIE die)> callback) override;
   void GetTypes(const DWARFDeclContext &context,
@@ -83,6 +88,10 @@ private:
   bool ProcessEntry(const DebugNames::Entry &entry,
                     llvm::function_ref<bool(DWARFDIE die)> callback);
 
+  /// Returns true if `parent_entries` have identical names to `parent_names`.
+  bool SameParentChain(llvm::ArrayRef<llvm::StringRef> parent_names,
+                       llvm::ArrayRef<DebugNames::Entry> parent_entries) const;
+
   static void MaybeLogLookupError(llvm::Error error,
                                   const DebugNames::NameIndex &ni,
                                   llvm::StringRef name);
diff --git a/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h b/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h
index 60baf69..01518b2 100644
--- a/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h
+++ b/lldb/source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h
@@ -373,6 +373,9 @@ public:
 
   Type *ResolveTypeUID(const DIERef &die_ref);
 
+  /// Returns the DWARFIndex for this symbol, if it exists.
+  DWARFIndex *getIndex() { return m_index.get(); }
+
 protected:
   SymbolFileDWARF(const SymbolFileDWARF &) = delete;
   const SymbolFileDWARF &operator=(const SymbolFileDWARF &) = delete;