https://github.com/labath created
https://github.com/llvm/llvm-project/pull/127806
After (too) much deliberation, I came to the conclusion that this isn't the
right abstraction, as it doesn't behave completely like the standard
upper_bound method. What I really wanted was to get the range of line entries
for a given address range -- so I implement just that.
lower_bound is still useful as a primitive for building other kinds of lookups.
>From d1da63666eeb50b688d3df66bec54772f22ad9d4 Mon Sep 17 00:00:00 2001
From: Pavel Labath <pa...@labath.sk>
Date: Wed, 19 Feb 2025 15:59:44 +0100
Subject: [PATCH] [lldb] Replace LineTable::upper_bound with
GetLineEntryIndexRange
After (too) much deliberation, I came to the conclusion that this isn't
the right abstraction, as it doesn't behave completely like the standard
upper_bound method. What I really wanted was to get the range of line
entries for a given address range -- so I implement just that.
lower_bound is still useful as a primitive for building other kinds of
lookups.
---
lldb/include/lldb/Symbol/LineTable.h | 23 ++++----
lldb/source/Symbol/LineTable.cpp | 24 ++++----
lldb/unittests/Symbol/LineTableTest.cpp | 74 ++++++++++++++++---------
3 files changed, 73 insertions(+), 48 deletions(-)
diff --git a/lldb/include/lldb/Symbol/LineTable.h
b/lldb/include/lldb/Symbol/LineTable.h
index f66081b6ee110..c1a973635cdd4 100644
--- a/lldb/include/lldb/Symbol/LineTable.h
+++ b/lldb/include/lldb/Symbol/LineTable.h
@@ -102,18 +102,19 @@ class LineTable {
void GetDescription(Stream *s, Target *target, lldb::DescriptionLevel level);
- /// Helper function for line table iteration. \c lower_bound returns the
index
- /// of the first line entry which ends after the given address (i.e., the
- /// first entry which contains the given address or it comes after it).
- /// \c upper_bound returns the index of the first line entry which begins on
- /// or after the given address (i.e., the entry which would come after the
- /// entry containing the given address, if such an entry exists). Functions
- /// return <tt>GetSize()</tt> if there is no such entry. The functions are
- /// most useful in combination: iterating from <tt>lower_bound(a)</tt> to
- /// <tt>upper_bound(b) returns all line tables which intersect the half-open
- /// range <tt>[a,b)</tt>.
+ /// Returns the index of the first line entry which ends after the given
+ /// address (i.e., the first entry which contains the given address or it
+ /// comes after it). Returns <tt>GetSize()</tt> if there is no such entry.
uint32_t lower_bound(const Address &so_addr) const;
- uint32_t upper_bound(const Address &so_addr) const;
+
+ /// Returns the (half-open) range of line entry indexes which overlap the
+ /// given address range. Line entries partially overlapping the range (on
+ /// either side) are included as well. Returns an empty range
+ /// (<tt>first==second</tt>) pointing to the "right" place in the list if
+ /// there are no such line entries. Empty input ranges always result in an
+ /// empty output range.
+ std::pair<uint32_t, uint32_t>
+ GetLineEntryIndexRange(const AddressRange &range) const;
/// Find a line entry that contains the section offset address \a so_addr.
///
diff --git a/lldb/source/Symbol/LineTable.cpp b/lldb/source/Symbol/LineTable.cpp
index aae4ab59ff156..c5914a2719cc9 100644
--- a/lldb/source/Symbol/LineTable.cpp
+++ b/lldb/source/Symbol/LineTable.cpp
@@ -206,25 +206,27 @@ uint32_t LineTable::lower_bound(const Address &so_addr)
const {
return std::distance(m_entries.begin(), pos);
}
-uint32_t LineTable::upper_bound(const Address &so_addr) const {
- if (so_addr.GetModule() != m_comp_unit->GetModule())
- return GetSize();
+std::pair<uint32_t, uint32_t>
+LineTable::GetLineEntryIndexRange(const AddressRange &range) const {
+ uint32_t first = lower_bound(range.GetBaseAddress());
+ if (first >= GetSize() || range.GetByteSize() == 0)
+ return {first, first};
Entry search_entry;
- search_entry.file_addr = so_addr.GetFileAddress();
- if (search_entry.file_addr == LLDB_INVALID_ADDRESS)
- return GetSize();
+ search_entry.file_addr =
+ range.GetBaseAddress().GetFileAddress() + range.GetByteSize();
- // This is not a typo. lower_bound returns the first entry which starts on or
- // after the given address, which is exactly what we want -- *except* if the
- // entry is a termination entry (in that case, we want the one after it).
+ // lower_bound returns the first entry which starts on or after the given
+ // address, which is exactly what we want -- *except* if the entry is a
+ // termination entry (in that case, we want the one after it).
auto pos =
- llvm::lower_bound(m_entries, search_entry, Entry::EntryAddressLessThan);
+ std::lower_bound(std::next(m_entries.begin(), first), m_entries.end(),
+ search_entry, Entry::EntryAddressLessThan);
if (pos != m_entries.end() && pos->file_addr == search_entry.file_addr &&
pos->is_terminal_entry)
++pos;
- return std::distance(m_entries.begin(), pos);
+ return {first, std::distance(m_entries.begin(), pos)};
}
bool LineTable::FindLineEntryByAddress(const Address &so_addr,
diff --git a/lldb/unittests/Symbol/LineTableTest.cpp
b/lldb/unittests/Symbol/LineTableTest.cpp
index 2fa2913f67f9e..ef5493138f318 100644
--- a/lldb/unittests/Symbol/LineTableTest.cpp
+++ b/lldb/unittests/Symbol/LineTableTest.cpp
@@ -194,7 +194,7 @@ CreateFakeModule(std::vector<std::unique_ptr<LineSequence>>
line_sequences) {
std::move(text_sp), line_table};
}
-TEST_F(LineTableTest, LowerAndUpperBound) {
+TEST_F(LineTableTest, lower_bound) {
LineSequenceBuilder builder;
builder.Entry(0);
builder.Entry(10);
@@ -211,41 +211,63 @@ TEST_F(LineTableTest, LowerAndUpperBound) {
auto make_addr = [&](addr_t addr) { return Address(fixture->text_sp, addr);
};
- // Both functions return the same value for boundary values. This way the
- // index range for e.g. [0,10) is [0,1).
EXPECT_EQ(table->lower_bound(make_addr(0)), 0u);
- EXPECT_EQ(table->upper_bound(make_addr(0)), 0u);
+ EXPECT_EQ(table->lower_bound(make_addr(9)), 0u);
EXPECT_EQ(table->lower_bound(make_addr(10)), 1u);
- EXPECT_EQ(table->upper_bound(make_addr(10)), 1u);
+ EXPECT_EQ(table->lower_bound(make_addr(19)), 1u);
+
+ // Skips over the terminal entry.
EXPECT_EQ(table->lower_bound(make_addr(20)), 3u);
- EXPECT_EQ(table->upper_bound(make_addr(20)), 3u);
+ EXPECT_EQ(table->lower_bound(make_addr(29)), 3u);
- // In case there's no "real" entry at this address, they return the first
real
- // entry.
+ // In case there's no "real" entry at this address, the function returns the
+ // first real entry.
EXPECT_EQ(table->lower_bound(make_addr(30)), 5u);
- EXPECT_EQ(table->upper_bound(make_addr(30)), 5u);
-
EXPECT_EQ(table->lower_bound(make_addr(40)), 5u);
- EXPECT_EQ(table->upper_bound(make_addr(40)), 5u);
-
- // For in-between values, their result differs by one. [9,19) maps to [0,2)
- // because the first two entries contain a part of that range.
- EXPECT_EQ(table->lower_bound(make_addr(9)), 0u);
- EXPECT_EQ(table->upper_bound(make_addr(9)), 1u);
- EXPECT_EQ(table->lower_bound(make_addr(19)), 1u);
- EXPECT_EQ(table->upper_bound(make_addr(19)), 2u);
- EXPECT_EQ(table->lower_bound(make_addr(29)), 3u);
- EXPECT_EQ(table->upper_bound(make_addr(29)), 4u);
- // In a gap, they both return the first entry after the gap.
- EXPECT_EQ(table->upper_bound(make_addr(39)), 5u);
- EXPECT_EQ(table->upper_bound(make_addr(39)), 5u);
+ // In a gap, return the first entry after the gap.
+ EXPECT_EQ(table->lower_bound(make_addr(39)), 5u);
- // And if there's no such entry, they return the size of the list.
+ // And if there's no such entry, return the size of the list.
EXPECT_EQ(table->lower_bound(make_addr(50)), table->GetSize());
- EXPECT_EQ(table->upper_bound(make_addr(50)), table->GetSize());
EXPECT_EQ(table->lower_bound(make_addr(59)), table->GetSize());
- EXPECT_EQ(table->upper_bound(make_addr(59)), table->GetSize());
+}
+
+TEST_F(LineTableTest, GetLineEntryIndexRange) {
+ LineSequenceBuilder builder;
+ builder.Entry(0);
+ builder.Entry(10);
+ builder.Entry(20, LineSequenceBuilder::Terminal);
+
+ llvm::Expected<FakeModuleFixture> fixture =
CreateFakeModule(builder.Build());
+ ASSERT_THAT_EXPECTED(fixture, llvm::Succeeded());
+
+ LineTable *table = fixture->line_table;
+
+ auto make_range = [&](addr_t addr, addr_t size) {
+ return AddressRange(fixture->text_sp, addr, size);
+ };
+
+ EXPECT_THAT(table->GetLineEntryIndexRange(make_range(0, 10)),
+ testing::Pair(0, 1));
+ EXPECT_THAT(table->GetLineEntryIndexRange(make_range(0, 20)),
+ testing::Pair(0, 3)); // Includes the terminal entry.
+ // Partial overlap on one side.
+ EXPECT_THAT(table->GetLineEntryIndexRange(make_range(3, 7)),
+ testing::Pair(0, 1));
+ // On the other side
+ EXPECT_THAT(table->GetLineEntryIndexRange(make_range(0, 15)),
+ testing::Pair(0, 2));
+ // On both sides
+ EXPECT_THAT(table->GetLineEntryIndexRange(make_range(2, 3)),
+ testing::Pair(0, 1));
+ // Empty ranges
+ EXPECT_THAT(table->GetLineEntryIndexRange(make_range(0, 0)),
+ testing::Pair(0, 0));
+ EXPECT_THAT(table->GetLineEntryIndexRange(make_range(5, 0)),
+ testing::Pair(0, 0));
+ EXPECT_THAT(table->GetLineEntryIndexRange(make_range(10, 0)),
+ testing::Pair(1, 1));
}
TEST_F(LineTableTest, FindLineEntryByAddress) {
_______________________________________________
lldb-commits mailing list
lldb-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
