[llvm] Add contains(KeyType) -> bool methods to Set types.

[varungandhi-apple]

Summary

Add C++20-esque contains method for sets.

[varungandhi-apple]

Prior art:

• C++20: https://en.cppreference.com/w/cpp/container/set/contains
• Rust: https://doc.rust-lang.org/std/collections/struct.HashSet.html#method.contains
• Swift: https://developer.apple.com/documentation/swift/set

Let's stop writing set.find(key) != set.end() over and over. It's 2020 already.

[varungandhi-apple]

I don't understand the clang-tidy/clang-format complaints. I've formatted the code based on how the surrounding code is formatted.

[fhahn]

Nice, IMO this makes a lot of sense and will help to get rid of a lot of more verbose find(x) != end() expressions.

For most ADT classes, there are unit tests in llvm/unittests/ADT/. It would be good to add additional tests there. Also ,it would be good to add a proper doc-comment in all classes, as well as including the prior art comment in the description and replacing [llvm] with [ADT].

[jroelofs]

In D83449#2140761, @varungandhi-apple wrote:

I don't understand the clang-tidy/clang-format complaints. I've formatted the code based on how the surrounding code is formatted.

IIRC, these come from arcanist. They should behave themselves if you have this utility on your PATH: https://github.com/llvm/llvm-project/blob/master/clang/tools/clang-format/git-clang-format#L15

[dblaikie]

+1 needs unit tests, might make sense to commit each one separately with its test (& maybe some cleanup commits afterwards, to help migrate the codebase/encourage future use in the new direction)

[varungandhi-apple]

Added comments and test cases addressing fhahn's review comment.

[varungandhi-apple]

I've added some unit tests. Are these adequate/do you have any other suggestions on what I should test?

might make sense to commit each one separately with its test

I'm not sure what benefit this would bring. Could you elaborate? I would've understood if the combined change were large by itself, but that's not the case here.

maybe some cleanup commits afterwards, to help migrate the codebase/encourage future use in the new direction

I could do this in a separate revision, if desired.

[dblaikie]

In D83449#2154087, @varungandhi-apple wrote:

I've added some unit tests. Are these adequate/do you have any other suggestions on what I should test?

Looks good to me, thanks!

might make sense to commit each one separately with its test

I'm not sure what benefit this would bring. Could you elaborate? I would've understood if the combined change were large by itself, but that's not the case here.

The usual sentiment that independent changes should be submitted independently - means if something goes wrong they can be reverted in isolation without reverting unrelated changes (eg: if there was a bug in one of these implementations - it got submitted, you committed a few more changes on top of it to start using these APIs more broadly - then someone identified/reported the bug, we rolled back the patch... now we'd have to rollback all the cleanups too - rather than only those cleanups that used the particular API that was buggy & leaving the rest intact)

maybe some cleanup commits afterwards, to help migrate the codebase/encourage future use in the new direction

I could do this in a separate revision, if desired.

I think that'd be nice, thanks!

[fhahn]

LGTM as well, thanks! You could commit this as separate patches for each container.

[varungandhi-apple]

Split up single commit into several commits (one commit per set type).

[varungandhi-apple]

@dblaikie could you land the patch for me? I do not have bot permissions/commit privileges.

[varungandhi-apple]

Thanks! It seems a bit weird that this revision now only shows the one commit under Revision contents even though the 'Commits' above shows the six commits. 🤷

[dblaikie]

In D83449#2159295, @varungandhi-apple wrote:

Thanks! It seems a bit weird that this revision now only shows the one commit under Revision contents even though the 'Commits' above shows the six commits. 🤷

Yeah, I doubt there's much to be done about that. Imagine phab only has the concept of a review being closed by one commit.

[dblaikie]

Oh, and sorry I forgot to update the "author" field to appropriately credit you when I committed these :/ they all have the Phab link in them at least, which leads here for appropriate credit.

[varungandhi-apple]

Oh, and sorry I forgot to update the "author" field to appropriately credit you when I committed these

Nbd, thanks for the review and merging. :)

llvm/include/llvm/ADT/DenseSet.h

public:
   const_iterator begin() const { return ConstIterator(TheMap.begin()); }
   const_iterator end() const { return ConstIterator(TheMap.end()); }
 
   iterator find(const_arg_type_t<ValueT> V) { return Iterator(TheMap.find(V)); }
   const_iterator find(const_arg_type_t<ValueT> V) const {
     return ConstIterator(TheMap.find(V));
   }
 
+  /// Check if the set contains the given element.
+  bool contains(const_arg_type_t<ValueT> V) const {
+    return TheMap.find(V) != TheMap.end();
+  }
+
   /// Alternative version of find() which allows a different, and possibly less
   /// expensive, key type.
   /// The DenseMapInfo is responsible for supplying methods
   /// getHashValue(LookupKeyT) and isEqual(LookupKeyT, KeyT) for each key type
   /// used.
   template <class LookupKeyT>
   iterator find_as(const LookupKeyT &Val) {
     return Iterator(TheMap.find_as(Val));

llvm/include/llvm/ADT/SetVector.h

bool remove_if(UnaryPredicate P) {
     typename vector_type::iterator I =
         llvm::remove_if(vector_, TestAndEraseFromSet<UnaryPredicate>(P, set_));
     if (I == vector_.end())
       return false;
     vector_.erase(I, vector_.end());
     return true;
   }
 
+  /// Check if the SetVector contains the given key.
+  bool contains(const key_type &key) const {
+    return set_.find(key) != set_.end();
+  }
+
   /// Count the number of elements of a given key in the SetVector.
   /// \returns 0 if the element is not in the SetVector, 1 if it is.
   size_type count(const key_type &key) const {
     return set_.count(key);
   }
 
   /// Completely clear the SetVector
   void clear() {

llvm/include/llvm/ADT/SmallPtrSet.h

public:
   }
   /// count - Return 1 if the specified pointer is in the set, 0 otherwise.
   size_type count(ConstPtrType Ptr) const {
     return find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)) != EndPointer();
   }
   iterator find(ConstPtrType Ptr) const {
     return makeIterator(find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)));
   }
+  bool contains(ConstPtrType Ptr) const {
+    return find_imp(ConstPtrTraits::getAsVoidPointer(Ptr)) != EndPointer();
+  }
 
   template <typename IterT>
   void insert(IterT I, IterT E) {
     for (; I != E; ++I)
       insert(*I);
   }
 
   void insert(std::initializer_list<PtrType> IL) {

llvm/include/llvm/ADT/SmallSet.h

public:
   }
 
   const_iterator end() const {
     if (isSmall())
       return {Vector.end()};
     return {Set.end()};
   }
 
+  /// Check if the SmallSet contains the given element.
+  bool contains(const T &V) const {
+    if (isSmall())
+      return vfind(V) != Vector.end();
+    return Set.find(V) != Set.end();
+  }
+
 private:
   bool isSmall() const { return Set.empty(); }
 
   VIterator vfind(const T &V) const {
     for (VIterator I = Vector.begin(), E = Vector.end(); I != E; ++I)
       if (*I == V)
         return I;
     return Vector.end();

llvm/include/llvm/ADT/SparseSet.h

public:
   iterator find(const KeyT &Key) {
     return findIndex(KeyIndexOf(Key));
   }
 
   const_iterator find(const KeyT &Key) const {
     return const_cast<SparseSet*>(this)->findIndex(KeyIndexOf(Key));
   }
 
+  /// Check if the set contains the given \c Key.
+  ///
+  /// @param Key A valid key to find.
+  bool contains(const KeyT &Key) const { return find(Key) == end() ? 0 : 1; }
+
   /// count - Returns 1 if this set contains an element identified by Key,
   /// 0 otherwise.
   ///
-  size_type count(const KeyT &Key) const {
-    return find(Key) == end() ? 0 : 1;
-  }
+  size_type count(const KeyT &Key) const { return contains(Key) ? 1 : 0; }
 
   /// insert - Attempts to insert a new element.
   ///
   /// If Val is successfully inserted, return (I, true), where I is an iterator
   /// pointing to the newly inserted element.
   ///
   /// If the set already contains an element with the same key as Val, return
   /// (I, false), where I is an iterator pointing to the existing element.

llvm/include/llvm/ADT/StringSet.h

for (auto it = begin; it != end; ++it)
       insert(*it);
   }
 
   template <typename ValueTy>
   std::pair<typename Base::iterator, bool>
   insert(const StringMapEntry<ValueTy> &mapEntry) {
     return insert(mapEntry.getKey());
   }
+
+  /// Check if the set contains the given \c key.
+  bool contains(StringRef key) const { return Base::FindKey(key) != -1; }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_ADT_STRINGSET_H

llvm/unittests/ADT/DenseSetTest.cpp

TEST(DenseSetCustomTest, ConstTest) {
   // underlying map is a non-const pointer.
   DenseSet<int *> Map;
   int A;
   int *B = &A;
   const int *C = &A;
   Map.insert(B);
   EXPECT_EQ(Map.count(B), 1u);
   EXPECT_EQ(Map.count(C), 1u);
-  EXPECT_NE(Map.find(B), Map.end());
-  EXPECT_NE(Map.find(C), Map.end());
+  EXPECT_TRUE(Map.contains(B));
+  EXPECT_TRUE(Map.contains(C));
 }
 }

llvm/unittests/ADT/SetVectorTest.cpp

TEST(SetVector, EraseTest) {
   // Test that the returned iterator is the expected one-after-erase
   // and the size/contents is the expected sequence {0, 2}.
   EXPECT_EQ(std::next(S.begin()), I);
   EXPECT_EQ(2u, S.size());
   EXPECT_EQ(0, *S.begin());
   EXPECT_EQ(2, *std::next(S.begin()));
 }
 
+TEST(SetVector, ContainsTest) {
+  SetVector<int> S;
+  S.insert(0);
+  S.insert(1);
+  S.insert(2);
+
+  EXPECT_TRUE(S.contains(0));
+  EXPECT_TRUE(S.contains(1));
+  EXPECT_TRUE(S.contains(2));
+  EXPECT_FALSE(S.contains(-1));
+
+  S.insert(2);
+  EXPECT_TRUE(S.contains(2));
+
+  S.remove(2);
+  EXPECT_FALSE(S.contains(2));
+}

llvm/unittests/ADT/SmallPtrSetTest.cpp

 TEST(SmallPtrSetTest, ConstTest) {
   SmallPtrSet<int *, 8> IntSet;
   int A;
   int *B = &A;
   const int *C = &A;
   IntSet.insert(B);
   EXPECT_EQ(IntSet.count(B), 1u);
   EXPECT_EQ(IntSet.count(C), 1u);
-  EXPECT_NE(IntSet.find(B), IntSet.end());
-  EXPECT_NE(IntSet.find(C), IntSet.end());
+  EXPECT_TRUE(IntSet.contains(B));
+  EXPECT_TRUE(IntSet.contains(C));
 }
 
 // Verify that we automatically get the const version of PointerLikeTypeTraits
 // filled in for us, even for a non-pointer type
 using TestPair = PointerIntPair<int *, 1>;
 
 TEST(SmallPtrSetTest, ConstNonPtrTest) {
   SmallPtrSet<TestPair, 8> IntSet;
   int A[1];
   TestPair Pair(&A[0], 1);
   IntSet.insert(Pair);
   EXPECT_EQ(IntSet.count(Pair), 1u);
-  EXPECT_NE(IntSet.find(Pair), IntSet.end());
+  EXPECT_TRUE(IntSet.contains(Pair));
 }
 
 // Test equality comparison.
 TEST(SmallPtrSetTest, EqualityComparison) {
   int buf[3];
   for (int i = 0; i < 3; ++i)
     buf[i] = 0;
 
TEST(SmallPtrSetTest, EqualityComparison) {
   EXPECT_NE(c, a);
   EXPECT_NE(d, a);
   EXPECT_NE(a, d);
   EXPECT_NE(a, e);
   EXPECT_NE(e, a);
   EXPECT_NE(c, e);
   EXPECT_NE(e, d);
 }
+
+TEST(SmallPtrSetTest, Contains) {
+  SmallPtrSet<int *, 2> Set;
+  int buf[4] = {0, 11, 22, 11};
+  EXPECT_FALSE(Set.contains(&buf[0]));
+  EXPECT_FALSE(Set.contains(&buf[1]));
+
+  Set.insert(&buf[0]);
+  Set.insert(&buf[1]);
+  EXPECT_TRUE(Set.contains(&buf[0]));
+  EXPECT_TRUE(Set.contains(&buf[1]));
+  EXPECT_FALSE(Set.contains(&buf[3]));
+
+  Set.insert(&buf[1]);
+  EXPECT_TRUE(Set.contains(&buf[0]));
+  EXPECT_TRUE(Set.contains(&buf[1]));
+  EXPECT_FALSE(Set.contains(&buf[3]));
+
+  Set.erase(&buf[1]);
+  EXPECT_TRUE(Set.contains(&buf[0]));
+  EXPECT_FALSE(Set.contains(&buf[1]));
+
+  Set.insert(&buf[1]);
+  Set.insert(&buf[2]);
+  EXPECT_TRUE(Set.contains(&buf[0]));
+  EXPECT_TRUE(Set.contains(&buf[1]));
+  EXPECT_TRUE(Set.contains(&buf[2]));
+}

llvm/unittests/ADT/SmallSetTest.cpp

TEST(SmallSetTest, EqualityComparisonTest) {
 
   EXPECT_EQ(s1small, s2small);
   EXPECT_EQ(s1small, s3large);
   EXPECT_EQ(s2small, s3large);
 
   EXPECT_NE(s1small, s4large);
   EXPECT_NE(s4large, s3large);
 }
+
+TEST(SmallSetTest, Contains) {
+  SmallSet<int, 2> Set;
+  EXPECT_FALSE(Set.contains(0));
+  EXPECT_FALSE(Set.contains(1));
+
+  Set.insert(0);
+  Set.insert(1);
+  EXPECT_TRUE(Set.contains(0));
+  EXPECT_TRUE(Set.contains(1));
+
+  Set.insert(1);
+  EXPECT_TRUE(Set.contains(0));
+  EXPECT_TRUE(Set.contains(1));
+
+  Set.erase(1);
+  EXPECT_TRUE(Set.contains(0));
+  EXPECT_FALSE(Set.contains(1));
+
+  Set.insert(1);
+  Set.insert(2);
+  EXPECT_TRUE(Set.contains(0));
+  EXPECT_TRUE(Set.contains(1));
+  EXPECT_TRUE(Set.contains(2));
+}

llvm/unittests/ADT/SparseSetTest.cpp

TEST(SparseSetTest, EmptySet) {
   USet Set;
   EXPECT_TRUE(Set.empty());
   EXPECT_TRUE(Set.begin() == Set.end());
   EXPECT_EQ(0u, Set.size());
 
   Set.setUniverse(10);
 
   // Lookups on empty set.
-  EXPECT_TRUE(Set.find(0) == Set.end());
-  EXPECT_TRUE(Set.find(9) == Set.end());
+  EXPECT_FALSE(Set.contains(0));
+  EXPECT_FALSE(Set.contains(9));
 
   // Same thing on a const reference.
   const USet &CSet = Set;
   EXPECT_TRUE(CSet.empty());
   EXPECT_TRUE(CSet.begin() == CSet.end());
   EXPECT_EQ(0u, CSet.size());
-  EXPECT_TRUE(CSet.find(0) == CSet.end());
+  EXPECT_FALSE(CSet.contains(0));
   USet::const_iterator I = CSet.find(5);
   EXPECT_TRUE(I == CSet.end());
 }
 
 // Single entry set tests.
 TEST(SparseSetTest, SingleEntrySet) {
   USet Set;
   Set.setUniverse(10);
   std::pair<USet::iterator, bool> IP = Set.insert(5);
   EXPECT_TRUE(IP.second);
   EXPECT_TRUE(IP.first == Set.begin());
 
   EXPECT_FALSE(Set.empty());
   EXPECT_FALSE(Set.begin() == Set.end());
   EXPECT_TRUE(Set.begin() + 1 == Set.end());
   EXPECT_EQ(1u, Set.size());
 
-  EXPECT_TRUE(Set.find(0) == Set.end());
-  EXPECT_TRUE(Set.find(9) == Set.end());
+  EXPECT_FALSE(Set.contains(0));
+  EXPECT_FALSE(Set.contains(9));
+  EXPECT_TRUE(Set.contains(5));
 
   EXPECT_FALSE(Set.count(0));
   EXPECT_TRUE(Set.count(5));
 
   // Redundant insert.
   IP = Set.insert(5);
   EXPECT_FALSE(IP.second);
   EXPECT_TRUE(IP.first == Set.begin());
 
   // Erase non-existent element.
   EXPECT_FALSE(Set.erase(1));
   EXPECT_EQ(1u, Set.size());
   EXPECT_EQ(5u, *Set.begin());
 
   // Erase iterator.
   USet::iterator I = Set.find(5);
   EXPECT_TRUE(I == Set.begin());
   I = Set.erase(I);
+  EXPECT_FALSE(Set.contains(5));
   EXPECT_TRUE(I == Set.end());
   EXPECT_TRUE(Set.empty());
 }
 
 // Multiple entry set tests.
 TEST(SparseSetTest, MultipleEntrySet) {
   USet Set;
   Set.setUniverse(10);

llvm/unittests/ADT/StringSetTest.cpp

TEST_F(StringSetTest, EmptyString) {
   size_t Count = Set.count("");
   EXPECT_EQ(Count, 0UL);
 
   Set.insert("");
   Count = Set.count("");
   EXPECT_EQ(Count, 1UL);
 }
 
+TEST_F(StringSetTest, Contains) {
+  StringSet<> Set;
+  EXPECT_FALSE(Set.contains(""));
+  EXPECT_FALSE(Set.contains("test"));
+
+  Set.insert("");
+  Set.insert("test");
+  EXPECT_TRUE(Set.contains(""));
+  EXPECT_TRUE(Set.contains("test"));
+
+  Set.insert("test");
+  EXPECT_TRUE(Set.contains(""));
+  EXPECT_TRUE(Set.contains("test"));
+
+  Set.erase("test");
+  EXPECT_TRUE(Set.contains(""));
+  EXPECT_FALSE(Set.contains("test"));
+}
+
 } // end anonymous namespace