[DWARF] Fix DWARFVerifier::DieRangeInfo::contains
It didn't handle empty LHS correctly. If two ranges of LHS were
contiguous and jointly contained one range of RHS, it could also be incorrect.
DWARFAddressRange::contains can be removed and its tests can be merged into DWARFVerifier::DieRangeInfo::contains
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@358387 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/include/llvm/DebugInfo/DWARF/DWARFAddressRange.h b/include/llvm/DebugInfo/DWARF/DWARFAddressRange.h
index 56d46c6..2d5f9f3 100644
--- a/include/llvm/DebugInfo/DWARF/DWARFAddressRange.h
+++ b/include/llvm/DebugInfo/DWARF/DWARFAddressRange.h
@@ -42,12 +42,6 @@
return LowPC < RHS.HighPC && RHS.LowPC < HighPC;
}
- /// Returns true if [LowPC, HighPC) fully contains [RHS.LowPC, RHS.HighPC).
- bool contains(const DWARFAddressRange &RHS) const {
- assert(valid() && RHS.valid());
- return LowPC <= RHS.LowPC && RHS.HighPC <= HighPC;
- }
-
void dump(raw_ostream &OS, uint32_t AddressSize,
DIDumpOptions DumpOpts = {}) const;
};
diff --git a/lib/DebugInfo/DWARF/DWARFVerifier.cpp b/lib/DebugInfo/DWARF/DWARFVerifier.cpp
index 43e83c8..a95c4f9 100644
--- a/lib/DebugInfo/DWARF/DWARFVerifier.cpp
+++ b/lib/DebugInfo/DWARF/DWARFVerifier.cpp
@@ -60,28 +60,27 @@
}
bool DWARFVerifier::DieRangeInfo::contains(const DieRangeInfo &RHS) const {
- // Both list of ranges are sorted so we can make this fast.
+ auto I1 = Ranges.begin(), E1 = Ranges.end();
+ auto I2 = RHS.Ranges.begin(), E2 = RHS.Ranges.end();
+ if (I2 == E2)
+ return true;
- if (Ranges.empty() || RHS.Ranges.empty())
- return false;
-
- // Since the ranges are sorted we can advance where we start searching with
- // this object's ranges as we traverse RHS.Ranges.
- auto End = Ranges.end();
- auto Iter = findRange(RHS.Ranges.front());
-
- // Now linearly walk the ranges in this object and see if they contain each
- // ranges from RHS.Ranges.
- for (const auto &R : RHS.Ranges) {
- while (Iter != End) {
- if (Iter->contains(R))
- break;
- ++Iter;
+ DWARFAddressRange R = *I2;
+ while (I1 != E1) {
+ bool Covered = I1->LowPC <= R.LowPC;
+ if (R.LowPC == R.HighPC || (Covered && R.HighPC <= I1->HighPC)) {
+ if (++I2 == E2)
+ return true;
+ R = *I2;
+ continue;
}
- if (Iter == End)
+ if (!Covered)
return false;
+ if (R.LowPC < I1->HighPC)
+ R.LowPC = I1->HighPC;
+ ++I1;
}
- return true;
+ return false;
}
bool DWARFVerifier::DieRangeInfo::intersects(const DieRangeInfo &RHS) const {
diff --git a/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp b/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp
index d3643ca..ef51ce0 100644
--- a/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp
+++ b/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp
@@ -2983,72 +2983,34 @@
VerifySuccess(*DwarfContext);
}
-TEST(DWARFDebugInfo, TestDwarfRangesContains) {
- DWARFAddressRange R(0x10, 0x20);
-
- //----------------------------------------------------------------------
- // Test ranges that start before R...
- //----------------------------------------------------------------------
- // Other range ends before start of R
- ASSERT_FALSE(R.contains({0x0f, 0x10}));
- // Other range end address is start of a R
- ASSERT_FALSE(R.contains({0x0f, 0x11}));
- // Other range end address is at and of R
- ASSERT_FALSE(R.contains({0x0f, 0x20}));
- // Other range end address is past end of R
- ASSERT_FALSE(R.contains({0x0f, 0x40}));
-
- //----------------------------------------------------------------------
- // Test ranges that start at R's start address
- //----------------------------------------------------------------------
- // Ensure empty ranges matches
- ASSERT_TRUE(R.contains({0x10, 0x10}));
- // 1 byte of Range
- ASSERT_TRUE(R.contains({0x10, 0x11}));
- // same as Range
- ASSERT_TRUE(R.contains({0x10, 0x20}));
- // 1 byte past Range
- ASSERT_FALSE(R.contains({0x10, 0x21}));
-
- //----------------------------------------------------------------------
- // Test ranges that start inside Range
- //----------------------------------------------------------------------
- // empty in range
- ASSERT_TRUE(R.contains({0x11, 0x11}));
- // all in Range
- ASSERT_TRUE(R.contains({0x11, 0x1f}));
- // ends at end of Range
- ASSERT_TRUE(R.contains({0x11, 0x20}));
- // ends past Range
- ASSERT_FALSE(R.contains({0x11, 0x21}));
-
- //----------------------------------------------------------------------
- // Test ranges that start at last bytes of Range
- //----------------------------------------------------------------------
- // ends at end of Range
- ASSERT_TRUE(R.contains({0x1f, 0x20}));
- // ends past Range
- ASSERT_FALSE(R.contains({0x1f, 0x21}));
-
- //----------------------------------------------------------------------
- // Test ranges that start after Range
- //----------------------------------------------------------------------
- // empty considered in Range
- ASSERT_TRUE(R.contains({0x20, 0x20}));
- // valid past Range
- ASSERT_FALSE(R.contains({0x20, 0x21}));
-}
-
TEST(DWARFDebugInfo, TestDWARFDieRangeInfoContains) {
- DWARFVerifier::DieRangeInfo Ranges({{0x10, 0x20}, {0x30, 0x40}});
+ DWARFVerifier::DieRangeInfo Empty;
+ ASSERT_TRUE(Empty.contains(Empty));
+ DWARFVerifier::DieRangeInfo Ranges(
+ {{0x10, 0x20}, {0x30, 0x40}, {0x40, 0x50}});
+
+ ASSERT_TRUE(Ranges.contains(Empty));
ASSERT_FALSE(Ranges.contains({{{0x0f, 0x10}}}));
- ASSERT_FALSE(Ranges.contains({{{0x20, 0x30}}}));
- ASSERT_FALSE(Ranges.contains({{{0x40, 0x41}}}));
+ ASSERT_FALSE(Ranges.contains({{{0x0f, 0x20}}}));
+ ASSERT_FALSE(Ranges.contains({{{0x0f, 0x21}}}));
+
+ // Test ranges that start at R's start address
+ ASSERT_TRUE(Ranges.contains({{{0x10, 0x10}}}));
+ ASSERT_TRUE(Ranges.contains({{{0x10, 0x11}}}));
ASSERT_TRUE(Ranges.contains({{{0x10, 0x20}}}));
+ ASSERT_FALSE(Ranges.contains({{{0x10, 0x21}}}));
+
ASSERT_TRUE(Ranges.contains({{{0x11, 0x12}}}));
+
+ // Test ranges that start at last bytes of Range
ASSERT_TRUE(Ranges.contains({{{0x1f, 0x20}}}));
- ASSERT_TRUE(Ranges.contains({{{0x30, 0x40}}}));
+ ASSERT_FALSE(Ranges.contains({{{0x1f, 0x21}}}));
+
+ // Test ranges that start after Range
+ ASSERT_TRUE(Ranges.contains({{{0x20, 0x20}}}));
+ ASSERT_FALSE(Ranges.contains({{{0x20, 0x21}}}));
+
ASSERT_TRUE(Ranges.contains({{{0x31, 0x32}}}));
ASSERT_TRUE(Ranges.contains({{{0x3f, 0x40}}}));
ASSERT_TRUE(Ranges.contains({{{0x10, 0x20}, {0x30, 0x40}}}));
@@ -3061,7 +3023,10 @@
{0x31, 0x32},
{0x32, 0x33}}}));
ASSERT_FALSE(Ranges.contains(
- {{{0x11, 0x12}, {0x12, 0x13}, {0x31, 0x32}, {0x32, 0x41}}}));
+ {{{0x11, 0x12}, {0x12, 0x13}, {0x31, 0x32}, {0x32, 0x51}}}));
+ ASSERT_TRUE(Ranges.contains({{{0x11, 0x12}, {0x30, 0x50}}}));
+ ASSERT_FALSE(Ranges.contains({{{0x30, 0x51}}}));
+ ASSERT_FALSE(Ranges.contains({{{0x50, 0x51}}}));
}
namespace {
