Return correct entry in RangeDataVector::FindEntryThatContains

[shivammittal99]

Summary

The FindEntryThatContains function does not return the correct entry in
the case when two non-consecutive entries contain the range.
Eg. Vector = [(0, 40, 0), (10, 10, 1)] and query = (25, 1). The function
currently returns nullptr, but it should return entry 0.

Signed-off-by: Shivam Mittal <[e-mail]>

[labath]

This is definitely a bug, but I fear that fixing this via a linear search will cause a big performance regression. Fortunately, since D74759 we now have a way to implement this more efficiently. Could you reimplement this function to use the binary search tree introduced in that patch?

If not, I can get around to it soon-ish, but I currently have a bunch of other things waiting in my queue...

lldb/include/lldb/Utility/RangeMap.h

#endif
 
   const Entry *FindEntryThatContains(const Entry &range) const {
 #ifdef ASSERT_RANGEMAP_ARE_SORTED
     assert(IsSorted());
 #endif
     if (!m_entries.empty()) {
       typename Collection::const_iterator begin = m_entries.begin();
       typename Collection::const_iterator end = m_entries.end();
-      typename Collection::const_iterator pos =
-          std::lower_bound(begin, end, range, BaseLessThan);
+      typename Collection::const_iterator limit =
+          std::upper_bound(begin, end, range, BaseLessThan);
 
-      while (pos != begin && pos[-1].Contains(range))
-        --pos;
-
-      if (pos != end && pos->Contains(range))
+      for (auto pos = begin; pos < limit; ++pos) {
+        if (pos->Contains(range))
           return &(*pos);
       }
+    }
     return nullptr;
   }
 
   const Entry *FindEntryStartsAt(B addr) const {
 #ifdef ASSERT_RANGEMAP_ARE_SORTED
     assert(IsSorted());
 #endif
     if (!m_entries.empty()) {

lldb/unittests/Utility/RangeMapTest.cpp

TEST(RangeDataVector, FindEntryThatContains_Overlap) {
   Map.Append(EntryT(0, 40, NextID++));
   Map.Append(EntryT(10, 20, NextID++));
   Map.Append(EntryT(20, 10, NextID++));
   Map.Sort();
 
   // With overlapping intervals, the intention seems to be to return the first
   // interval which contains the address.
   EXPECT_THAT(Map.FindEntryThatContains(25), EntryIs(0));
-
-  // However, this does not always succeed.
-  // TODO: This should probably return the range (0, 40) as well.
-  EXPECT_THAT(Map.FindEntryThatContains(35), nullptr);
+  EXPECT_THAT(Map.FindEntryThatContains(35), EntryIs(0));
 }
 
 TEST(RangeDataVector, CustomSort) {
   // First the default ascending order sorting of the data field.
   auto Map = RangeDataVectorT();
   Map.Append(EntryT(0, 10, 50));
   Map.Append(EntryT(0, 10, 52));
   Map.Append(EntryT(0, 10, 53));