[ADT] Fix DenseMapInfo<variant>::isEqual to delegate to DenseMapInfo, not ==

[sammccall]

steal tests from D151079

[sammccall]

sorry, sent this prematurely

[sammccall]

fixed

[IncludeGuardian]

llvm/include/llvm/ADT/DenseMapInfo.h

354–356

I think we may be able to use std::visit twice and rely on the type of the parameter in the second visit matching the original type of the value we cast to const void *.

const void *ErasedLHSValue = std::visit([](const auto& LHSValue){
    return static_cast<const void *>(&LHSValue);
}, l);

return std::visit([=](const auto& RHSValue){
    using T = std::remove_reference_t<decltype(RHSValue)>;
    return DenseMapInfo<T>::isEqual(*static_cast<T *>(ErasedLHSValue), RHSValue);
}, r);

[sammccall]

simplify isEqual by using two std::visit calls with generic lambdas

[sammccall]

llvm/include/llvm/ADT/DenseMapInfo.h

354–356

Right! I always forget that auto-params in lambdas are good for something other than saving typing :-)

[kadircet]

thanks!

[IncludeGuardian]

LGTM!

llvm/include/llvm/ADT/DenseMapInfo.h

template <typename... Ts> struct DenseMapInfo<std::tuple<Ts...>> {
   }
 
   static bool isEqual(const Tuple &lhs, const Tuple &rhs) {
     std::integral_constant<bool, 0 == sizeof...(Ts)> atEnd;
     return isEqualImpl<0>(lhs, rhs, atEnd);
   }
 };
 
+namespace detail {
+// Helpers for DenseMapInfo<std::variant>
+
+// Returns a pointer to std::get<Index>(Val), where Index is not constant.
+template <class V, size_t... Indices>
+static const void *variantGetDynamic(const V &Val, int Index,
+                                     std::index_sequence<Indices...>) {
+  const void *Result = nullptr;
+  unsigned I = 0;
+  (((I++ == Index) ? (Result = &std::get<Indices>(Val), true) : false) || ...);
+  return Result;
+}
+
+// Visitor to check equality of values stored in variants.
+// Assumes both values have the same type.
+struct EqVisitor {
+  const void *ErasedRHSVal; // Points to the value stored in B.
+
+  template <class T> bool operator()(const T &LHSVal) const {
+    const T &RHSVal = *reinterpret_cast<const T *>(ErasedRHSVal);
+    return DenseMapInfo<T>::eq(LHSVal, RHSVal);
+  }
+};
+
+} // namespace detail
+
 // Provide DenseMapInfo for variants whose all alternatives have DenseMapInfo.
 template <typename... Ts> struct DenseMapInfo<std::variant<Ts...>> {
   using Variant = std::variant<Ts...>;
   using FirstT = std::variant_alternative_t<0, Variant>;
 
   static inline Variant getEmptyKey() {
     return Variant(std::in_place_index<0>, DenseMapInfo<FirstT>::getEmptyKey());
   }
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;
+    if (LHS.index() != RHS.index()) return false;
+    if (LHS.valueless_by_exception()) return true;
+    // We want to dispatch to DenseMapInfo<T>::isEqual(LHS.get(I), RHS.get(I))
+    // This is surprisingly fiddly:
+    //  - there's no get() for a runtime index (see detail::variantGetDynamic)
+    //  - we know the types are the same, but std::visit(V, LHS, RHS) doesn't
+    // We erase the type held in RHS to void*, and dispatch over LHS.
+    return std::visit<bool>(
+        detail::EqVisitor{
+            dyn_get(RHS, RHS.index(), std::index_sequence_for<Ts...>{})},
+        LHS);
   }
 };
 } // end namespace llvm
 
 #endif // LLVM_ADT_DENSEMAPINFO_H