[ADT] Enable set_difference() to be used on StringSet

[mmpozulp]

Summary

Re-land r362766 after it was reverted in r362823.

[mmpozulp]

This patch must land before https://reviews.llvm.org/D62275 in which I use set_difference() on StringSet

[jhenderson]

I'm not sure I know enough about LLVM's ADT classes to be able to properly review this (on the surface the code looks fine though), so I've added a few reviewers who have worked on some of the *Set classes in the past according to the history. If you don't hear back from any of them by the end of next week, ping me and I'll take a look.

[aaron.ballman]

For my part, this seems reasonable to me.

[dblaikie]

llvm/unittests/ADT/SetOperationsTest.cpp

1–29 ↗

(On Diff #201132)

This test probably should go where other StringSet tests are (presumably unittests/ADT/StringSetTest) - and I would /generally/ be in favor of not 'integration testing' that set_difference works with StringSet, but that StringSet exposes the appropriate kind of iterators/operations that set_difference requires in general?

Oh, I see, this llvm::set_difference doesn't just wrap std::set_difference, so it has different interface requirements. I'd /probably/ still test the surface area of StringSet directly - and certainly feel like code changes to StringSet would be tested in StringSet's tests.

[mmpozulp]

Incorporated feedback from @dblaikie to change test name from SetOperationsTest.cpp to StringSetTest.cpp and moved an existing StringSet test from StringMapTest.cpp to new file StringSetTest.cpp.

[dblaikie]

llvm/unittests/ADT/StringSetTest.cpp

34–43

I'd still prefer this as two unit tests for the two new functions you added (& the test wouldn't use set_difference at all - unit tests being what they are, try to test things in isolation) - but I'll leave it up to you. No big deal (:

[mmpozulp]

Incorporate feedback from @dblaikie to call insert(StringMapEntry) and count(StringMapEntry) instead of set_difference(StringSet, StringSet) in StringSetTest.cpp, which better adheres to the spirit of unit-testing.

[dblaikie]

Can you commit this yourself - or would you like me to do it for you?

[mmpozulp]

Change a const char * to a StringRef

[mmpozulp]

In D62369#1522112, @dblaikie wrote:

Can you commit this yourself - or would you like me to do it for you?

Yes, please commit for me. I just requested commit access by email to Chris on Friday. No response yet so I assume I don't have access, which is fine because helpful people like you can do it for me while I wait. Thanks! :)

[jhenderson]

@dblaikie, did this get committed? I think @mmpozulp you may now have access so could commit if it hasn't happened yet.

[dblaikie]

In D62369#1527350, @jhenderson wrote:

@dblaikie, did this get committed? I think @mmpozulp you may now have access so could commit if it hasn't happened yet.

Yeah, had my local client tangled up with some other work for a bit so I haven't got to committing this - but if @mmpozulp has commit access now - then, yeah, he should go ahead and commit it so the author information's more accurate, etc.

[mmpozulp]

I'm fighting with svn. I ran svn co https://[e-mail]/svn/llvm-project/llvm/trunk llvm which took about 90 minutes to checkout the repo. If I run svn up it hangs for ~10 minutes on a poll() call (which I discovered by running strace) then emits an error

$ svn up
Updating '.':
svn: E175002: REPORT of '/svn/llvm-project/!svn/vcc/default': Could not read status line: Secure connection truncated (https://llvm.org)

I'm running svn 1.7.14

$ svn --version
svn, version 1.7.14 (r1542130)

[mmpozulp]

Good news! Apparently I can commit from git (https://llvm.org/docs/GettingStarted.html#for-developers-to-commit-changes-from-git). Thank you, @smeenai!!! I should be able to land this commit soon. Good-bye svn :)

[mmpozulp]

Delete unused header in StringSetTest.cpp.

[mmpozulp]

I committed as r362766. Thanks! Note that the Differential Revision listed in the r362766 commit message is D62992 instead of D62369. That was my mistake caused by an accidental arc diff instead of arc diff --update. I posted a link in D62992 to D62369. Sorry for the confusion.

[mmpozulp]

Fix asan-detected stack-buffer-overflow in StringSetTest.cpp

[mmpozulp]

@dblaikie approved the stack-buffer-overflow fix (see https://reviews.llvm.org/D63000) which I have applied here, so I'm going to re-land this patch :)

[mmpozulp]

Committed as r362835.

llvm/include/llvm/ADT/StringMap.h

public:
   /// if the key is not in the map.
   ValueTy &operator[](StringRef Key) { return try_emplace(Key).first->second; }
 
   /// count - Return 1 if the element is in the map, 0 otherwise.
   size_type count(StringRef Key) const {
     return find(Key) == end() ? 0 : 1;
   }
 
+  template <typename InputTy>
+  size_type count(const StringMapEntry<InputTy> &MapEntry) const {
+    return count(MapEntry.getKey());
+  }
+
   /// insert - Insert the specified key/value pair into the map.  If the key
   /// already exists in the map, return false and ignore the request, otherwise
   /// insert it and return true.
   bool insert(MapEntryTy *KeyValue) {
     unsigned BucketNo = LookupBucketFor(KeyValue->getKey());
     StringMapEntryBase *&Bucket = TheTable[BucketNo];
     if (Bucket && Bucket != getTombstoneVal())
       return false;  // Already exists in map.

llvm/include/llvm/ADT/StringSet.h

std::pair<typename base::iterator, bool> insert(StringRef Key) {
       return base::insert(std::make_pair(Key, '\0'));
     }
 
     template <typename InputIt>
     void insert(const InputIt &Begin, const InputIt &End) {
       for (auto It = Begin; It != End; ++It)
         base::insert(std::make_pair(*It, '\0'));
     }
+
+    template <typename ValueTy>
+    std::pair<typename base::iterator, bool>
+    insert(const StringMapEntry<ValueTy> &MapEntry) {
+      return insert(MapEntry.getKey());
+    }
   };
 
 } // end namespace llvm
 
 #endif // LLVM_ADT_STRINGSET_H

llvm/unittests/ADT/CMakeLists.txt

add_llvm_unittest(ADTTests
   SmallVectorTest.cpp
   SparseBitVectorTest.cpp
   SparseMultiSetTest.cpp
   SparseSetTest.cpp
   StatisticTest.cpp
   StringExtrasTest.cpp
   StringMapTest.cpp
   StringRefTest.cpp
+  StringSetTest.cpp
   StringSwitchTest.cpp
   TinyPtrVectorTest.cpp
   TripleTest.cpp
   TwineTest.cpp
   VariadicFunctionTest.cpp
   )
 
 target_link_libraries(ADTTests PRIVATE LLVMTestingSupport)
 
 add_dependencies(ADTTests intrinsics_gen)

llvm/unittests/ADT/StringMapTest.cpp

 //===- llvm/unittest/ADT/StringMapMap.cpp - StringMap unit tests ----------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/StringMap.h"
-#include "llvm/ADT/StringSet.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/Support/DataTypes.h"
 #include "gtest/gtest.h"
 #include <limits>
 #include <tuple>
 using namespace llvm;
 
 namespace {
TEST_F(StringMapTest, IterMapKeys) {
 
   auto Keys = to_vector<4>(Map.keys());
   llvm::sort(Keys);
 
   SmallVector<StringRef, 4> Expected = {"A", "B", "C", "D"};
   EXPECT_EQ(Expected, Keys);
 }
 
-TEST_F(StringMapTest, IterSetKeys) {
-  StringSet<> Set;
-  Set.insert("A");
-  Set.insert("B");
-  Set.insert("C");
-  Set.insert("D");
-
-  auto Keys = to_vector<4>(Set.keys());
-  llvm::sort(Keys);
-
-  SmallVector<StringRef, 4> Expected = {"A", "B", "C", "D"};
-  EXPECT_EQ(Expected, Keys);
-}
-
 // Create a non-default constructable value
 struct StringMapTestStruct {
   StringMapTestStruct(int i) : i(i) {}
   StringMapTestStruct() = delete;
   int i;
 };
 
 TEST_F(StringMapTest, NonDefaultConstructable) {

llvm/unittests/ADT/StringSetTest.cpp

+//===- llvm/unittest/ADT/StringSetTest.cpp - StringSet unit tests ----------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/StringSet.h"
+#include "gtest/gtest.h"
+using namespace llvm;
+
+namespace {
+
+// Test fixture
+class StringSetTest : public testing::Test {};
+
+TEST_F(StringSetTest, IterSetKeys) {
+  StringSet<> Set;
+  Set.insert("A");
+  Set.insert("B");
+  Set.insert("C");
+  Set.insert("D");
+
+  auto Keys = to_vector<4>(Set.keys());
+  llvm::sort(Keys);
+
+  SmallVector<StringRef, 4> Expected = {"A", "B", "C", "D"};
+  EXPECT_EQ(Expected, Keys);
+}
+
+TEST_F(StringSetTest, InsertAndCountStringMapEntry) {
+  // Test insert(StringMapEntry) and count(StringMapEntry)
+  // which are required for set_difference(StringSet, StringSet).
+  StringSet<> Set;
+  StringMapEntry<StringRef> Element(1, "A");
+  Set.insert(Element);
+  size_t Count = Set.count(Element);
+  size_t Expected = 1;
+  EXPECT_EQ(Expected, Count);
+}
+
+} // end anonymous namespace