[adt] SparseBitVector::test() should be const

[dsanders]

Summary

Re-worked SparseBitVector's most-recently-used-word caching (CurrElementIter)
such that SparseBitVector::test() can be made const. This came up when
attempting to test individual bits in a SparseBitVector which was a member of a
const object.

The cached iterator has no bearing on the externally visible state, it's merely
a performance optimization. Therefore it has been made mutable and
FindLowerBound() has been split into a const and non-const function
(FindLowerBound/FindLowerBoundConst) for the const/non-const
interfaces.

[rtereshin]

LGTM, thanks for doing this!

include/llvm/ADT/SparseBitVector.h

310

Technically, const qualifier is a part of the member function signature, so no need for a different name. If called from another const function, like test, the const version of this function will be called regardless of the object itself being const or not.

But honestly, I like making the difference explicit in this specific case, it draws attention, and it's probably a good thing as FindLowerBoundImpl needs to be used or modified with care so we don't accidentally leak a non-const iterator from a const object in the future.

In the end, I'm fine with both, a different name and the same.

[dsanders]

Thanks

include/llvm/ADT/SparseBitVector.h

310

Yep, that's the reason I used separate names in this particular case. The const_casts are safe so long as we only call the const version in a const context and the non-const version in a non-const context. It's difficult to tell which you're calling when the names are the same.

include/llvm/ADT/SparseBitVector.h

 class SparseBitVector {
   using ElementList = std::list<SparseBitVectorElement<ElementSize>>;
   using ElementListIter = typename ElementList::iterator;
   using ElementListConstIter = typename ElementList::const_iterator;
   enum {
     BITWORD_SIZE = SparseBitVectorElement<ElementSize>::BITWORD_SIZE
   };
 
-  // Pointer to our current Element.
-  ElementListIter CurrElementIter;
+  // Pointer to our current Element. This has no visible effect on the external
+  // state of a SparseBitVector, it's just used to improve performance in the
+  // common case of testing/modifying bits with similar indices.
+  mutable ElementListIter CurrElementIter;
   ElementList Elements;
 
   // This is like std::lower_bound, except we do linear searching from the
   // current position.
-  ElementListIter FindLowerBound(unsigned ElementIndex) {
+  ElementListIter FindLowerBoundImpl(unsigned ElementIndex) const {
+
+    // We cache a non-const iterator so we're forced to resort to const_cast to
+    // get the begin/end in the case where 'this' is const. To avoid duplication
+    // of code with the only difference being whether the const cast is present
+    // 'this' is always const in this particular function and we sort out the
+    // difference in FindLowerBound and FindLowerBoundConst.
+    ElementListIter Begin =
+        const_cast<SparseBitVector<ElementSize> *>(this)->Elements.begin();
+    ElementListIter End =
+        const_cast<SparseBitVector<ElementSize> *>(this)->Elements.end();
 
     if (Elements.empty()) {
-      CurrElementIter = Elements.begin();
-      return Elements.begin();
+      CurrElementIter = Begin;
+      return CurrElementIter;
     }
 
     // Make sure our current iterator is valid.
-    if (CurrElementIter == Elements.end())
+    if (CurrElementIter == End)
       --CurrElementIter;
 
     // Search from our current iterator, either backwards or forwards,
     // depending on what element we are looking for.
     ElementListIter ElementIter = CurrElementIter;
     if (CurrElementIter->index() == ElementIndex) {
       return ElementIter;
     } else if (CurrElementIter->index() > ElementIndex) {
-      while (ElementIter != Elements.begin()
+      while (ElementIter != Begin
              && ElementIter->index() > ElementIndex)
         --ElementIter;
     } else {
-      while (ElementIter != Elements.end() &&
+      while (ElementIter != End &&
              ElementIter->index() < ElementIndex)
         ++ElementIter;
     }
     CurrElementIter = ElementIter;
     return ElementIter;
   }
+  ElementListConstIter FindLowerBoundConst(unsigned ElementIndex) const {
+    return FindLowerBoundImpl(ElementIndex);
+  }
+  ElementListIter FindLowerBound(unsigned ElementIndex) {
+    return FindLowerBoundImpl(ElementIndex);
+  }
 
   // Iterator to walk set bits in the bitmap.  This iterator is a lot uglier
   // than it would be, in order to be efficient.
   class SparseBitVectorIterator {
   private:
     bool AtEnd;
 
     const SparseBitVector<ElementSize> *BitVector = nullptr;
SparseBitVector& operator=(const SparseBitVector& RHS) {
     }
 
     CurrElementIter = Elements.begin ();
 
     return *this;
   }
 
   // Test, Reset, and Set a bit in the bitmap.
-  bool test(unsigned Idx) {
+  bool test(unsigned Idx) const {
     if (Elements.empty())
       return false;
 
     unsigned ElementIndex = Idx / ElementSize;
-    ElementListIter ElementIter = FindLowerBound(ElementIndex);
+    ElementListConstIter ElementIter = FindLowerBoundConst(ElementIndex);
 
     // If we can't find an element that is supposed to contain this bit, there
     // is nothing more to do.
     if (ElementIter == Elements.end() ||
         ElementIter->index() != ElementIndex)
       return false;
     return ElementIter->test(Idx % ElementSize);
   }

unittests/ADT/SparseBitVectorTest.cpp

TEST(SparseBitVectorTest, TrivialOperation) {
   EXPECT_FALSE(Vec.test(6));
   Vec.reset(5);
   EXPECT_FALSE(Vec.test(5));
   EXPECT_TRUE(Vec.test_and_set(17));
   EXPECT_FALSE(Vec.test_and_set(17));
   EXPECT_TRUE(Vec.test(17));
   Vec.clear();
   EXPECT_FALSE(Vec.test(17));
+
+  Vec.set(5);
+  const SparseBitVector<> ConstVec = Vec;
+  EXPECT_TRUE(ConstVec.test(5));
+  EXPECT_FALSE(ConstVec.test(17));
 }
 
 TEST(SparseBitVectorTest, IntersectWith) {
   SparseBitVector<> Vec, Other;
 
   Vec.set(1);
   Other.set(1);
   EXPECT_FALSE(Vec &= Other);