RangeMap.h: merge RangeDataArray and RangeDataVector

[labath]

Summary

The main difference between the classes was supposed to be the fact that
one is backed by llvm::SmallVector, and the other by std::vector.
However, over the years, they have accumulated various other differences
too.

This essentially removes the std::vector version, as that is pretty much
identical to llvm::SmallVector<T, 0>, and combines their interfaces. It
does not attempt to do a more significant refactoring, even though there
is still a lot of duplication in this file, as it is hard to tell which
quirk of some API is depended on by somebody (and, a previous, more
ambitious attempt at this in D16769 has failed).

I also add some tests, including one which demonstrates one of the
quirks/bugs of the API I have noticed in the process.

[davide]

unittests/Core/RangeMapTest.cpp

52–54 ↗

(On Diff #179754)

I think this is a bug in the implementation.

[davide]

LG

[labath]

unittests/Core/RangeMapTest.cpp

52–54 ↗

(On Diff #179754)

I agree. I think this can be fixed if we change the while loop in FindEntryThatContains to loop until the current range start address goes below the lookup address. If that's the behavior we want from this function, that is.

[tberghammer]

LGTM

include/lldb/Core/RangeMap.h

636 ↗

(On Diff #179754)

Would it make sense to have a default value of 0 for N so people don't have to specify it explicitly?

source/Plugins/Process/elf-core/ProcessElfCore.h

140 ↗

(On Diff #179754)

Should this be 1 to keep the previous semantics?

[labath]

include/lldb/Core/RangeMap.h

636 ↗

(On Diff #179754)

I don't have an clear opinion on that. On one hand, 0 seems like a perfectly reasonable default, but on the other SmallVector doesn't have a default either. Everyone typedefs these anyway, so it doesn't really matter.

source/Plugins/Process/elf-core/ProcessElfCore.h

140 ↗

(On Diff #179754)

If we wanted to be strict then yes, but it seemed weird to have different sizes for the two VMRange maps, when both of them will (hopefully) hold the same number of entries. My guess is that the author here meant "the smallest number possible" and didn't realize that 0 is valid too (or maybe it wasn't valid at that time).

[clayborg]

include/lldb/Core/RangeMap.h

636 ↗

(On Diff #179754)

Can we default N to be zero?

template <typename B, typename S, typename T, unsigned N=0>

Then remove the zero parameter from many of the changes in this patch?

include/lldb/Symbol/DWARFCallFrameInfo.h

117 ↗

(On Diff #179754)

We can remove the last zero parameter if we default its value in the template definition

include/lldb/Symbol/LineTable.h

233 ↗

(On Diff #179754)

We can remove the last zero parameter if we default its value in the template definition

include/lldb/Symbol/Symtab.h

150 ↗

(On Diff #179754)

We can remove the last zero parameter if we default its value in the template definition

source/Plugins/Process/elf-core/ProcessElfCore.h

139–140 ↗

(On Diff #179754)

We can remove the last zero parameter if we default its value in the template definition

142 ↗

(On Diff #179754)

We can remove the last zero parameter if we default its value in the template definition

source/Plugins/Process/mach-core/ProcessMachCore.h

133–134 ↗

(On Diff #179754)

We can remove the last zero parameter if we default its value in the template definition

136 ↗

(On Diff #179754)

Ditto

source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h

22 ↗

(On Diff #179754)

Should this default to zero instead of 1? Not many DWARFDebugAranges will have just a single address.

source/Plugins/SymbolFile/DWARF/SymbolFileDWARF.h

443 ↗

(On Diff #179754)

We can remove the last zero parameter if we default its value in the template definition

source/Plugins/SymbolFile/DWARF/SymbolFileDWARFDebugMap.h

159 ↗

(On Diff #179754)

We can remove the last zero parameter if we default its value in the template definition

302 ↗

(On Diff #179754)

We can remove the last zero parameter if we default its value in the template definition

[labath]

Set N=0 default parameter, and remove the size specification from all usages
(including the one in DWARFDebugArranges, where N was 1).

lldb/trunk/include/lldb/Core/RangeMap.h

struct RangeData : public Range<B, S> {
   }
 
   bool operator!=(const RangeData &rhs) const {
     return this->GetRangeBase() != rhs.GetRangeBase() ||
            this->GetByteSize() != rhs.GetByteSize() || this->data != rhs.data;
   }
 };
 
-template <typename B, typename S, typename T, unsigned N> class RangeDataArray {
+template <typename B, typename S, typename T, unsigned N = 0>
+class RangeDataVector {
 public:
   typedef RangeData<B, S, T> Entry;
   typedef llvm::SmallVector<Entry, N> Collection;
 
-  RangeDataArray() = default;
-
-  ~RangeDataArray() = default;
-
-  void Append(const Entry &entry) { m_entries.push_back(entry); }
-
-  void Sort() {
-    if (m_entries.size() > 1)
-      std::stable_sort(m_entries.begin(), m_entries.end());
-  }
-
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-  bool IsSorted() const {
-    typename Collection::const_iterator pos, end, prev;
-    // First we determine if we can combine any of the Entry objects so we
-    // don't end up allocating and making a new collection for no reason
-    for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
-         prev = pos++) {
-      if (prev != end && *pos < *prev)
-        return false;
-    }
-    return true;
-  }
-#endif
-
-  void CombineConsecutiveEntriesWithEqualData() {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-    assert(IsSorted());
-#endif
-    typename Collection::iterator pos;
-    typename Collection::iterator end;
-    typename Collection::iterator prev;
-    bool can_combine = false;
-    // First we determine if we can combine any of the Entry objects so we
-    // don't end up allocating and making a new collection for no reason
-    for (pos = m_entries.begin(), end = m_entries.end(), prev = end; pos != end;
-         prev = pos++) {
-      if (prev != end && prev->data == pos->data) {
-        can_combine = true;
-        break;
-      }
-    }
-
-    // We we can combine at least one entry, then we make a new collection and
-    // populate it accordingly, and then swap it into place.
-    if (can_combine) {
-      Collection minimal_ranges;
-      for (pos = m_entries.begin(), end = m_entries.end(), prev = end;
-           pos != end; prev = pos++) {
-        if (prev != end && prev->data == pos->data)
-          minimal_ranges.back().SetRangeEnd(pos->GetRangeEnd());
-        else
-          minimal_ranges.push_back(*pos);
-      }
-      // Use the swap technique in case our new vector is much smaller. We must
-      // swap when using the STL because std::vector objects never release or
-      // reduce the memory once it has been allocated/reserved.
-      m_entries.swap(minimal_ranges);
-    }
-  }
-
-  void Clear() { m_entries.clear(); }
-
-  bool IsEmpty() const { return m_entries.empty(); }
-
-  size_t GetSize() const { return m_entries.size(); }
-
-  const Entry *GetEntryAtIndex(size_t i) const {
-    return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
-  }
-
-  // Clients must ensure that "i" is a valid index prior to calling this
-  // function
-  const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
-
-  static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
-    return lhs.GetRangeBase() < rhs.GetRangeBase();
-  }
-
-  uint32_t FindEntryIndexThatContains(B addr) const {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-    assert(IsSorted());
-#endif
-    if (!m_entries.empty()) {
-      Entry entry(addr, 1);
-      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, entry, BaseLessThan);
-
-      if (pos != end && pos->Contains(addr)) {
-        return std::distance(begin, pos);
-      } else if (pos != begin) {
-        --pos;
-        if (pos->Contains(addr))
-          return std::distance(begin, pos);
-      }
-    }
-    return UINT32_MAX;
-  }
-
-  Entry *FindEntryThatContains(B addr) {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-    assert(IsSorted());
-#endif
-    if (!m_entries.empty()) {
-      Entry entry;
-      entry.SetRangeBase(addr);
-      entry.SetByteSize(1);
-      typename Collection::iterator begin = m_entries.begin();
-      typename Collection::iterator end = m_entries.end();
-      typename Collection::iterator pos =
-          std::lower_bound(begin, end, entry, BaseLessThan);
-
-      if (pos != end && pos->Contains(addr)) {
-        return &(*pos);
-      } else if (pos != begin) {
-        --pos;
-        if (pos->Contains(addr)) {
-          return &(*pos);
-        }
-      }
-    }
-    return nullptr;
-  }
-
-  const Entry *FindEntryThatContains(B addr) const {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-    assert(IsSorted());
-#endif
-    if (!m_entries.empty()) {
-      Entry entry;
-      entry.SetRangeBase(addr);
-      entry.SetByteSize(1);
-      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, entry, BaseLessThan);
-
-      if (pos != end && pos->Contains(addr)) {
-        return &(*pos);
-      } else if (pos != begin) {
-        --pos;
-        if (pos->Contains(addr)) {
-          return &(*pos);
-        }
-      }
-    }
-    return nullptr;
-  }
-
-  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);
-
-      if (pos != end && pos->Contains(range)) {
-        return &(*pos);
-      } else if (pos != begin) {
-        --pos;
-        if (pos->Contains(range)) {
-          return &(*pos);
-        }
-      }
-    }
-    return nullptr;
-  }
-
-  Entry *Back() { return (m_entries.empty() ? nullptr : &m_entries.back()); }
-
-  const Entry *Back() const {
-    return (m_entries.empty() ? nullptr : &m_entries.back());
-  }
-
-protected:
-  Collection m_entries;
-};
-
-// Same as RangeDataArray, but uses std::vector as to not require static
-// storage of N items in the class itself
-template <typename B, typename S, typename T> class RangeDataVector {
-public:
-  typedef RangeData<B, S, T> Entry;
-  typedef std::vector<Entry> Collection;
-
   RangeDataVector() = default;
 
   ~RangeDataVector() = default;
 
   void Append(const Entry &entry) { m_entries.push_back(entry); }
 
   void Sort() {
     if (m_entries.size() > 1)
if (can_combine) {
       }
       // Use the swap technique in case our new vector is much smaller. We must
       // swap when using the STL because std::vector objects never release or
       // reduce the memory once it has been allocated/reserved.
       m_entries.swap(minimal_ranges);
     }
   }
 
-  // Calculate the byte size of ranges with zero byte sizes by finding the next
-  // entry with a base address > the current base address
-  void CalculateSizesOfZeroByteSizeRanges(S full_size = 0) {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-    assert(IsSorted());
-#endif
-    typename Collection::iterator pos;
-    typename Collection::iterator end;
-    typename Collection::iterator next;
-    for (pos = m_entries.begin(), end = m_entries.end(); pos != end; ++pos) {
-      if (pos->GetByteSize() == 0) {
-        // Watch out for multiple entries with same address and make sure we
-        // find an entry that is greater than the current base address before
-        // we use that for the size
-        auto curr_base = pos->GetRangeBase();
-        for (next = pos + 1; next != end; ++next) {
-          auto next_base = next->GetRangeBase();
-          if (next_base > curr_base) {
-            pos->SetByteSize(next_base - curr_base);
-            break;
-          }
-        }
-        if (next == end && full_size > curr_base)
-          pos->SetByteSize(full_size - curr_base);
-      }
-    }
-  }
-
   void Clear() { m_entries.clear(); }
 
-  void Reserve(typename Collection::size_type size) { m_entries.resize(size); }
-
   bool IsEmpty() const { return m_entries.empty(); }
 
   size_t GetSize() const { return m_entries.size(); }
 
   const Entry *GetEntryAtIndex(size_t i) const {
     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
   }
 
   Entry *GetMutableEntryAtIndex(size_t i) {
     return ((i < m_entries.size()) ? &m_entries[i] : nullptr);
   }
 
   // Clients must ensure that "i" is a valid index prior to calling this
   // function
   const Entry &GetEntryRef(size_t i) const { return m_entries[i]; }
 
   static bool BaseLessThan(const Entry &lhs, const Entry &rhs) {
     return lhs.GetRangeBase() < rhs.GetRangeBase();
   }
 
   uint32_t FindEntryIndexThatContains(B addr) const {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-    assert(IsSorted());
-#endif
-    if (!m_entries.empty()) {
-      Entry entry(addr, 1);
-      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, entry, BaseLessThan);
-
-      while (pos != begin && pos[-1].Contains(addr))
-        --pos;
-
-      if (pos != end && pos->Contains(addr))
-        return std::distance(begin, pos);
-    }
+    const Entry *entry = FindEntryThatContains(addr);
+    if (entry)
+      return std::distance(m_entries.begin(), entry);
     return UINT32_MAX;
   }
 
   uint32_t FindEntryIndexesThatContain(B addr,
                                        std::vector<uint32_t> &indexes) const {
 #ifdef ASSERT_RANGEMAP_ARE_SORTED
     assert(IsSorted());
 #endif
 
     if (!m_entries.empty()) {
       for (const auto &entry : m_entries) {
         if (entry.Contains(addr))
           indexes.push_back(entry.data);
       }
     }
     return indexes.size();
   }
 
   Entry *FindEntryThatContains(B addr) {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-    assert(IsSorted());
-#endif
-    if (!m_entries.empty()) {
-      Entry entry;
-      entry.SetRangeBase(addr);
-      entry.SetByteSize(1);
-      typename Collection::iterator begin = m_entries.begin();
-      typename Collection::iterator end = m_entries.end();
-      typename Collection::iterator pos =
-          std::lower_bound(begin, end, entry, BaseLessThan);
-
-      while (pos != begin && pos[-1].Contains(addr))
-        --pos;
-
-      if (pos != end && pos->Contains(addr))
-        return &(*pos);
-    }
-    return nullptr;
+    return const_cast<Entry *>(
+        static_cast<const RangeDataVector *>(this)->FindEntryThatContains(
+            addr));
   }
 
   const Entry *FindEntryThatContains(B addr) const {
-#ifdef ASSERT_RANGEMAP_ARE_SORTED
-    assert(IsSorted());
-#endif
-    if (!m_entries.empty()) {
-      Entry entry;
-      entry.SetRangeBase(addr);
-      entry.SetByteSize(1);
-      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, entry, BaseLessThan);
-
-      while (pos != begin && pos[-1].Contains(addr))
-        --pos;
-
-      if (pos != end && pos->Contains(addr))
-        return &(*pos);
-    }
-    return nullptr;
+    return FindEntryThatContains(Entry(addr, 1));
   }
 
   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();

lldb/trunk/source/Plugins/Process/elf-core/ProcessElfCore.h

struct NT_FILE_Entry {
     lldb::addr_t file_ofs;
     lldb_private::ConstString path;
   };
 
   //------------------------------------------------------------------
   // For ProcessElfCore only
   //------------------------------------------------------------------
   typedef lldb_private::Range<lldb::addr_t, lldb::addr_t> FileRange;
-  typedef lldb_private::RangeDataArray<lldb::addr_t, lldb::addr_t, FileRange, 1>
+  typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, FileRange>
       VMRangeToFileOffset;
   typedef lldb_private::RangeDataVector<lldb::addr_t, lldb::addr_t, uint32_t>
       VMRangeToPermissions;
 
   lldb::ModuleSP m_core_module_sp;
   lldb_private::FileSpec m_core_file;
   std::string m_dyld_plugin_name;
   DISALLOW_COPY_AND_ASSIGN(ProcessElfCore);

lldb/trunk/source/Plugins/SymbolFile/DWARF/DWARFDebugAranges.h

 #include <list>
 
 #include "lldb/Core/RangeMap.h"
 
 class SymbolFileDWARF;
 
 class DWARFDebugAranges {
 protected:
-  typedef lldb_private::RangeDataArray<dw_addr_t, uint32_t, dw_offset_t, 1>
+  typedef lldb_private::RangeDataVector<dw_addr_t, uint32_t, dw_offset_t>
       RangeToDIE;
 
 public:
   typedef RangeToDIE::Entry Range;
   typedef std::vector<RangeToDIE::Entry> RangeColl;
 
   DWARFDebugAranges();
 

lldb/trunk/unittests/Core/CMakeLists.txt

 add_lldb_unittest(LLDBCoreTests
   MangledTest.cpp
+  RangeMapTest.cpp
   RangeTest.cpp
   RichManglingContextTest.cpp
   StreamCallbackTest.cpp
 
   LINK_LIBS
     lldbCore
     lldbHost
     lldbSymbol

lldb/trunk/unittests/Core/RangeMapTest.cpp

+//===-- RangeTest.cpp ----------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "lldb/Core/RangeMap.h"
+#include "gmock/gmock.h"
+#include "gtest/gtest.h"
+
+using namespace lldb_private;
+
+using RangeDataVectorT = RangeDataVector<uint32_t, uint32_t, uint32_t>;
+using EntryT = RangeDataVectorT::Entry;
+
+static testing::Matcher<const EntryT *> EntryIs(uint32_t ID) {
+  return testing::Pointee(testing::Field(&EntryT::data, ID));
+}
+
+TEST(RangeDataVector, FindEntryThatContains) {
+  RangeDataVectorT Map;
+  uint32_t NextID = 0;
+  Map.Append(EntryT(0, 10, NextID++));
+  Map.Append(EntryT(10, 10, NextID++));
+  Map.Append(EntryT(20, 10, NextID++));
+  Map.Sort();
+
+  EXPECT_THAT(Map.FindEntryThatContains(0), EntryIs(0));
+  EXPECT_THAT(Map.FindEntryThatContains(9), EntryIs(0));
+  EXPECT_THAT(Map.FindEntryThatContains(10), EntryIs(1));
+  EXPECT_THAT(Map.FindEntryThatContains(19), EntryIs(1));
+  EXPECT_THAT(Map.FindEntryThatContains(20), EntryIs(2));
+  EXPECT_THAT(Map.FindEntryThatContains(29), EntryIs(2));
+  EXPECT_THAT(Map.FindEntryThatContains(30), nullptr);
+}
+
+TEST(RangeDataVector, FindEntryThatContains_Overlap) {
+  RangeDataVectorT Map;
+  uint32_t NextID = 0;
+  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);
+}