[llvm][ADT] Implement `BitVector::{pop_,}back`

[jansvoboda11]

Summary

LLVM Programmer’s Manual strongly discourages the use of std::vector<bool> and suggests llvm::BitVector as a possible replacement.

Currently, some users of std::vector<bool> cannot switch to llvm::BitVector because it doesn't implement the pop_back() and back() functions.

To enable easy transition of std::vector<bool> users, this patch implements llvm::BitVector::pop_back() and llvm::BitVector::back().

[dexonsmith]

Given that BitVector::back() already exists this makes sense.

LGTM, after you add some !empty() assertions for clarity if/when these are misused.

llvm/include/llvm/ADT/BitVector.h

456

I suggest asserting !empty() here for clarity of the assertion message.

480

I suggest asserting !empty() here for clarity of the assertion message.

llvm/include/llvm/ADT/SmallBitVector.h

475

I suggest asserting !empty() here for clarity of the assertion message.

487

I suggest asserting !empty() here for clarity of the assertion message.

llvm/include/llvm/ADT/BitVector.h

public:
   }
 
   bool operator[](unsigned Idx) const {
     assert (Idx < Size && "Out-of-bounds Bit access.");
     BitWord Mask = BitWord(1) << (Idx % BITWORD_SIZE);
     return (Bits[Idx / BITWORD_SIZE] & Mask) != 0;
   }
 
+  /// Return the last element in the vector.
+  bool back() const { return (*this)[size() - 1]; }
+
   bool test(unsigned Idx) const {
     return (*this)[Idx];
   }
 
   // Push single bit to end of vector.
   void push_back(bool Val) {
     unsigned OldSize = Size;
     unsigned NewSize = Size + 1;
 
     // Resize, which will insert zeros.
     // If we already fit then the unused bits will be already zero.
     if (NewSize > getBitCapacity())
       resize(NewSize, false);
     else
       Size = NewSize;
 
     // If true, set single bit.
     if (Val)
       set(OldSize);
   }
 
+  /// Pop one bit from the end of the vector.
+  void pop_back() { resize(size() - 1); }
+
   /// Test if any common bits are set.
   bool anyCommon(const BitVector &RHS) const {
     unsigned ThisWords = Bits.size();
     unsigned RHSWords = RHS.Bits.size();
     for (unsigned i = 0, e = std::min(ThisWords, RHSWords); i != e; ++i)
       if (Bits[i] & RHS.Bits[i])
         return true;
     return false;

llvm/include/llvm/ADT/SmallBitVector.h

public:
 
   bool operator[](unsigned Idx) const {
     assert(Idx < size() && "Out-of-bounds Bit access.");
     if (isSmall())
       return ((getSmallBits() >> Idx) & 1) != 0;
     return getPointer()->operator[](Idx);
   }
 
+  /// Return the last element in the vector.
+  bool back() const { return (*this)[size() - 1]; }
+
   bool test(unsigned Idx) const {
     return (*this)[Idx];
   }
 
   // Push single bit to end of vector.
   void push_back(bool Val) {
     resize(size() + 1, Val);
   }
 
+  /// Pop one bit from the end of the vector.
+  void pop_back() { resize(size() - 1); }
+
   /// Test if any common bits are set.
   bool anyCommon(const SmallBitVector &RHS) const {
     if (isSmall() && RHS.isSmall())
       return (getSmallBits() & RHS.getSmallBits()) != 0;
     if (!isSmall() && !RHS.isSmall())
       return getPointer()->anyCommon(*RHS.getPointer());
 
     for (unsigned i = 0, e = std::min(size(), RHS.size()); i != e; ++i)

llvm/unittests/ADT/BitVectorTest.cpp

for (unsigned Bit : ToFill.set_bits())
     EXPECT_EQ(List[i++], Bit);
 }
 
 TYPED_TEST(BitVectorTest, PushBack) {
   TypeParam Vec(10, false);
   EXPECT_EQ(-1, Vec.find_first());
   EXPECT_EQ(10U, Vec.size());
   EXPECT_EQ(0U, Vec.count());
+  EXPECT_EQ(false, Vec.back());
 
   Vec.push_back(true);
   EXPECT_EQ(10, Vec.find_first());
   EXPECT_EQ(11U, Vec.size());
   EXPECT_EQ(1U, Vec.count());
+  EXPECT_EQ(true, Vec.back());
 
   Vec.push_back(false);
   EXPECT_EQ(10, Vec.find_first());
   EXPECT_EQ(12U, Vec.size());
   EXPECT_EQ(1U, Vec.count());
+  EXPECT_EQ(false, Vec.back());
 
   Vec.push_back(true);
   EXPECT_EQ(10, Vec.find_first());
   EXPECT_EQ(13U, Vec.size());
   EXPECT_EQ(2U, Vec.count());
+  EXPECT_EQ(true, Vec.back());
 
   // Add a lot of values to cause reallocation.
   for (int i = 0; i != 100; ++i) {
     Vec.push_back(true);
     Vec.push_back(false);
   }
   EXPECT_EQ(10, Vec.find_first());
   EXPECT_EQ(213U, Vec.size());
   EXPECT_EQ(102U, Vec.count());
 }
 
+TYPED_TEST(BitVectorTest, PopBack) {
+  TypeParam Vec(10, true);
+  EXPECT_EQ(10U, Vec.size());
+  EXPECT_EQ(10U, Vec.count());
+  EXPECT_EQ(true, Vec.back());
+
+  Vec.pop_back();
+  EXPECT_EQ(9U, Vec.size());
+  EXPECT_EQ(9U, Vec.count());
+  EXPECT_EQ(true, Vec.back());
+
+  Vec.push_back(false);
+  EXPECT_EQ(10U, Vec.size());
+  EXPECT_EQ(9U, Vec.count());
+  EXPECT_EQ(false, Vec.back());
+
+  Vec.pop_back();
+  EXPECT_EQ(9U, Vec.size());
+  EXPECT_EQ(9U, Vec.count());
+  EXPECT_EQ(true, Vec.back());
+}
+
 TYPED_TEST(BitVectorTest, DenseSet) {
   DenseSet<TypeParam> Set;
   TypeParam A(10, true);
   auto I = Set.insert(A);
   EXPECT_EQ(true, I.second);
 
   TypeParam B(5, true);
   I = Set.insert(B);