[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/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));
 }
 }