[llvm][ADT] Change isEqual for DenseMapInfo<std::variant<...>>

[kadircet]

Summary

Defer to DenseMapInfo<T>::isEqual instead of operator==(T,T).

[IncludeGuardian]

llvm/unittests/ADT/DenseMapTest.cpp

755–756

It is worth testing a type were isEqual and operator== disagree? The tombstone and empty keys in StringRef would be an example where they don't work with operator== https://github.com/llvm/llvm-project/blob/a68bbf42fa680c7159165be8915d73e012c50f96/llvm/include/llvm/ADT/StringRef.h#L911-L931

[kadircet]

llvm/unittests/ADT/DenseMapTest.cpp

755–756

i'd rather not depend on the implementation details for DenseMapInfo<StringRef>, added a custom type into the test instead.

[kadircet]

• Add a test case for a type with different operator== and isEqual.

[kadircet]

• formatting

[IncludeGuardian]

llvm/include/llvm/ADT/DenseMapInfo.h

326–329

As this will be instantiated for each combination of types in our variant, I think the approach taken in https://reviews.llvm.org/D151079 is slightly better for compilation speed, although it is not as simple as this.

I would love to suggest C-style variadic functions to avoid any template instantiation, i.e.

bool operator()(...) const {
  return false;
}

but I don't think the behavior is guaranteed for non-POD user-defined types and some compilers will create a copy.

[kadircet]

llvm/include/llvm/ADT/DenseMapInfo.h

326–329

yes that was my concern as well, hence we had an offline discussion with @sammccall and he was kind enough to come up with go/phab/D151557. so i'll abandon this patch in favor of it.

llvm/include/llvm/ADT/DenseMapInfo.h

return std::visit(
           return detail::combineHashValue(
               DenseMapInfo<size_t>::getHashValue(Val.index()),
               DenseMapInfo<T>::getHashValue(Alternative));
         },
         Val);
   }
 
   static bool isEqual(const Variant &LHS, const Variant &RHS) {
-    return LHS == RHS;
+    return LHS.index() == RHS.index() && std::visit(EqVisitor{}, LHS, RHS);
+  }
+
+private:
+  struct EqVisitor {
+    template <typename T, typename U>
+    bool operator()(const T &LHS, const U &RHS) const {
+      return false;
+    }
+    template <typename T> bool operator()(const T &LHS, const T &RHS) const {
+      return DenseMapInfo<T>::isEqual(LHS, RHS);
     }
   };
+};
 } // end namespace llvm
 
 #endif // LLVM_ADT_DENSEMAPINFO_H

llvm/unittests/ADT/DenseMapTest.cpp

 namespace {
 struct A {
   A(int value) : value(value) {}
   int value;
 };
 struct B : public A {
   using A::A;
 };
+
+struct AlwaysEqType {
+  bool operator==(const AlwaysEqType &RHS) const { return true; }
+};
 } // namespace
 
 namespace llvm {
 template <typename T>
 struct DenseMapInfo<T, std::enable_if_t<std::is_base_of_v<A, T>>> {
   static inline T getEmptyKey() { return {static_cast<int>(~0)}; }
   static inline T getTombstoneKey() { return {static_cast<int>(~0U - 1)}; }
   static unsigned getHashValue(const T &Val) { return Val.value; }
   static bool isEqual(const T &LHS, const T &RHS) {
     return LHS.value == RHS.value;
   }
 };
+
+template <> struct DenseMapInfo<AlwaysEqType> {
+  using T = AlwaysEqType;
+  static inline T getEmptyKey() { return {}; }
+  static inline T getTombstoneKey() { return {}; }
+  static unsigned getHashValue(const T &Val) { return 0; }
+  static bool isEqual(const T &LHS, const T &RHS) {
+    return false;
+  }
+};
+
 } // namespace llvm
 
 namespace {
 TEST(DenseMapCustomTest, SFINAEMapInfo) {
   // Test that we can use a pointer to an incomplete type as a DenseMap key.
   // This is an important build time optimization, since many classes have
   // DenseMap members.
   DenseMap<B, int> Map;
   B Keys[3] = {{0}, {1}, {2}};
   Map.insert({Keys[0], 1});
   Map.insert({Keys[1], 2});
   Map.insert({Keys[2], 3});
   EXPECT_EQ(Map.count(Keys[0]), 1u);
   EXPECT_EQ(Map[Keys[0]], 1);
   EXPECT_EQ(Map[Keys[1]], 2);
   EXPECT_EQ(Map[Keys[2]], 3);
   Map.clear();
   EXPECT_EQ(Map.find(Keys[0]), Map.end());
   EXPECT_EQ(Map.find(Keys[1]), Map.end());
   EXPECT_EQ(Map.find(Keys[2]), Map.end());
 }
 
 TEST(DenseMapCustomTest, VariantSupport) {
-  using variant = std::variant<int, int>;
+  using variant = std::variant<int, int, AlwaysEqType>;
   DenseMap<variant, int> Map;
   variant Keys[] = {
       variant(std::in_place_index<0>, 1),
       variant(std::in_place_index<1>, 1),
+      variant(std::in_place_index<2>),
   };
   Map.try_emplace(Keys[0], 0);
   Map.try_emplace(Keys[1], 1);
   EXPECT_THAT(Map, testing::SizeIs(2));
   EXPECT_NE(DenseMapInfo<variant>::getHashValue(Keys[0]),
             DenseMapInfo<variant>::getHashValue(Keys[1]));
+  // Check that isEqual dispatches to isEqual of underlying type, and not to
+  // operator==.
+  EXPECT_FALSE(DenseMapInfo<variant>::isEqual(Keys[2], Keys[2]));
 }
 } // namespace