LibDebug: Add caches of DIE objects to DwarfInfo

There is one cache that indexes DIE objects by the start address of
their range, and another cache that indexes by their offset in the
debug_info section.

Both caches are implemented with RedBlackTree, and are optional - they
will only be populated if 'build_cached_dies' is invoked.

2 files changed, 74 insertions, 2 deletions

diff --git a/Userland/Libraries/LibDebug/Dwarf/DwarfInfo.cpp b/Userland/Libraries/LibDebug/Dwarf/DwarfInfo.cpp
index eae91e9874..ab1a5ac341 100644
--- a/Userland/Libraries/LibDebug/Dwarf/DwarfInfo.cpp
+++ b/Userland/Libraries/LibDebug/Dwarf/DwarfInfo.cpp
@@ -1,13 +1,15 @@
 /*
- * Copyright (c) 2020, Itamar S. <itamar8910@gmail.com>
+ * Copyright (c) 2020-2021, Itamar S. <itamar8910@gmail.com>
  *
  * SPDX-License-Identifier: BSD-2-Clause
  */
 
 #include "DwarfInfo.h"
 #include "AttributeValue.h"
+#include "CompilationUnit.h"
 
 #include <AK/MemoryStream.h>
+#include <LibDebug/DebugInfo.h>
 
 namespace Debug::Dwarf {
 
@@ -233,4 +235,57 @@ AttributeValue DwarfInfo::get_attribute_value(AttributeDataForm form, ssize_t im
     return value;
 }
 
+void DwarfInfo::build_cached_dies() const
+{
+    auto insert_to_cache = [this](const DIE& die, DIERange& range) {
+        m_cached_dies_by_range.insert(range.start_address, DIEAndRange { die, range });
+        m_cached_dies_by_offset.insert(die.offset(), die);
+    };
+    auto get_ranges_of_die = [this](const DIE& die) -> Vector<DIERange> {
+        // TODO support DW_AT_ranges (appears when range is non-contiguous)
+
+        auto start = die.get_attribute(Attribute::LowPc);
+        auto end = die.get_attribute(Attribute::HighPc);
+
+        if (!start.has_value() || !end.has_value())
+            return {};
+
+        VERIFY(sizeof(FlatPtr) == sizeof(u32));
+        VERIFY(start->type == Dwarf::AttributeValue::Type::UnsignedNumber);
+
+        // DW_AT_high_pc attribute can have different meanings depending on the attribute form.
+        // (Dwarf version 5, section 2.17.2).
+
+        uint32_t range_end = 0;
+        if (end->form == Dwarf::AttributeDataForm::Addr)
+            range_end = end->data.as_u32;
+        else
+            range_end = start->data.as_u32 + end->data.as_u32;
+
+        return { DIERange { start.value().data.as_u32, range_end } };
+    };
+
+    // If we simply use a lambda, type deduction fails because it's used recursively.
+    Function<void(const DIE& die)> insert_to_cache_recursively;
+    insert_to_cache_recursively = [&](const DIE& die) {
+        if (die.offset() == 0 || die.parent_offset().has_value()) {
+            auto ranges = get_ranges_of_die(die);
+            for (auto& range : ranges) {
+                insert_to_cache(die, range);
+            }
+        }
+        die.for_each_child([&](const DIE& child) {
+            if (!child.is_null()) {
+                insert_to_cache_recursively(child);
+            }
+        });
+    };
+
+    for_each_compilation_unit([&](const CompilationUnit& compilation_unit) {
+        insert_to_cache_recursively(compilation_unit.root_die());
+    });
+
+    m_built_cached_dies = true;
+}
+
 }
diff --git a/Userland/Libraries/LibDebug/Dwarf/DwarfInfo.h b/Userland/Libraries/LibDebug/Dwarf/DwarfInfo.h
index f2b2d2cd60..5af366a20a 100644
--- a/Userland/Libraries/LibDebug/Dwarf/DwarfInfo.h
+++ b/Userland/Libraries/LibDebug/Dwarf/DwarfInfo.h
@@ -1,5 +1,5 @@
 /*
- * Copyright (c) 2020, Itamar S. <itamar8910@gmail.com>
+ * Copyright (c) 2020-2021, Itamar S. <itamar8910@gmail.com>
  *
  * SPDX-License-Identifier: BSD-2-Clause
  */
@@ -39,6 +39,7 @@ public:
 
 private:
     void populate_compilation_units();
+    void build_cached_dies() const;
 
     ReadonlyBytes section_data(const StringView& section_name) const;
 
@@ -50,6 +51,22 @@ private:
     ReadonlyBytes m_debug_line_strings_data;
 
     NonnullOwnPtrVector<Dwarf::CompilationUnit> m_compilation_units;
+
+    struct DIERange {
+        FlatPtr start_address { 0 };
+        FlatPtr end_address { 0 };
+    };
+
+    struct DIEAndRange {
+        DIE die;
+        DIERange range;
+    };
+
+    using DIEStartAddress = FlatPtr;
+
+    mutable RedBlackTree<DIEStartAddress, DIEAndRange> m_cached_dies_by_range;
+    mutable RedBlackTree<FlatPtr, DIE> m_cached_dies_by_offset;
+    mutable bool m_built_cached_dies { false };
 };
 
 template<typename Callback>