[Support] Automatically support `hash_value` when `HashBuilder` support is available.

[arames]

Summary

Use the HBuilder interface to provide default implementations of llvm::hash_value.

[arames]

llvm/include/llvm/Support/HashBuilder.h

410

This was suggested as part of https://reviews.llvm.org/D102943.

A couple things to consider:

The default implementation of hash_value would always go through ArrayRef<uint8_t>:
This may be less efficient than an explicit implementation. IMO that's ok, since it can be explicitly implemented if performance is an issue.
The behavior may differ from what would happen with hash_value and co. For example hash_value for integral and enum types casts to uint64_t to guarantee (char)1 and (int)1 have the same hash. Again, IMO that's ok. We are talking about generating hashes for custom structures. If this behavior is required, it can be explicitly implemented.

Using hash_value with that mechanism requires calling llvm::hash_value or (using llvm::hash_value) explicitly. I need to brush up on ADL and template functions (I think that's what involved here). Again, that looks acceptable to me.

What do you think ?

[arames]

Fix clang-format warning.

[dexonsmith]

llvm/include/llvm/Support/HashBuilder.h

101–106

Noticing now that this trait is independent of HashBuilder's template parameters. I suggest moving it outside HashBuilder in a prep commit (probably doesn't need a review), maybe into a detail namespace like llvm::hashbuilder_detail.

410

One option would be to throw HashCodeHasher and HashCodeHashBuilder into a detail namespace to discourage anyone trying to use HashCodeHashBuilder directly. There's an asymmetric relationship:

• Objects get hash_value for free if they add HashBuilder support.
• ... but using HashBuilder<HashCodeHasher> directly isn't very useful, since HashCodeHashBuilder().add(X).getHasher().Code is not guaranteed to match hash_value(X).

[arames]

Address review comments.

[arames]

Applied suggestions.

[dexonsmith]

llvm/include/llvm/Support/HashBuilder.h

30–37

This change should be a separate NFC commit, since it touches a lot of lines (and isn't directly related)

91

Diff would be reduced if teh public: didn't move before teh static_assert

410

Probably cleaner to use the same name for the detail namespace as above.

[arames]

Address review comments.

[arames]

llvm/include/llvm/Support/HashBuilder.h

30–37

https://reviews.llvm.org/D109205

[dexonsmith]

LGTM, with one more inline comment.

llvm/include/llvm/Support/HashBuilder.h

424–425

Please move this typedef into the detail namespace as well, since it's not intended to be used directly.

Could even be inside HashCodeHasher:

class HashCodeHasher {
public:
  //...

  using Builder = HashBuilder<...>;
};

but up to you.

llvm/include/llvm/Support/HashBuilder.h

 // about hashed data types.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_SUPPORT_HASHBUILDER_H
 #define LLVM_SUPPORT_HASHBUILDER_H
 
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/Hashing.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/type_traits.h"
 
 #include <iterator>
 #include <utility>
 
 namespace llvm {
 
 namespace hashbuilder_detail {
 /// Trait to indicate whether a type's bits can be hashed directly (after
 /// endianness correction).
 template <typename U>
 struct IsHashableData
     : std::integral_constant<bool, is_integral_or_enum<U>::value> {};
 
 } // namespace hashbuilder_detail
 
 /// Declares the hasher member, and functions forwarding directly to the hasher.
 template <typename HasherT> class HashBuilderBase {
 public:
   HasherT &getHasher() { return Hasher; }
 
   /// Forward to `HasherT::update(ArrayRef<uint8_t>)`.
   ///

 
 /// Implementation of the `HashBuilder` interface.
 ///
 /// `support::endianness::native` is not supported. `HashBuilder` is
 /// expected to canonicalize `support::endianness::native` to one of
 /// `support::endianness::big` or `support::endianness::little`.
 template <typename HasherT, support::endianness Endianness>
 class HashBuilderImpl : public HashBuilderBase<HasherT> {
   static_assert(Endianness != support::endianness::native,
                 "HashBuilder should canonicalize endianness");
 
 public:
   explicit HashBuilderImpl(HasherT &Hasher)
       : HashBuilderBase<HasherT>(Hasher) {}
   template <typename... ArgTypes>
   explicit HashBuilderImpl(ArgTypes &&...Args)
       : HashBuilderBase<HasherT>(Args...) {}
 
   /// Implement hashing for hashable data types, e.g. integral or enum values.
   template <typename T>
   std::enable_if_t<hashbuilder_detail::IsHashableData<T>::value,
                    HashBuilderImpl &>
   add(T Value) {
     return adjustForEndiannessAndAdd(Value);
   }
 
   /// Support hashing `ArrayRef`.
   ///
   /// `Value.size()` is taken into account to ensure cases like
   /// ```
   /// builder.add({1});
   /// builder.add({2, 3});

 /// computation (for example when computing `add((int)123)`).
 /// Specifiying a non-`native` `Endianness` template parameter allows to compute
 /// stable hash across platforms with different endianness.
 template <class HasherT, support::endianness Endianness>
 using HashBuilder =
     HashBuilderImpl<HasherT, (Endianness == support::endianness::native
                                   ? support::endian::system_endianness()
                                   : Endianness)>;
+
+namespace hashbuilder_detail {
+class HashCodeHasher {
+public:
+  HashCodeHasher() : Code(0) {}
+  void update(ArrayRef<uint8_t> Data) {
+    hash_code DataCode = hash_value(Data);
+    Code = hash_combine(Code, DataCode);
+  }
+  hash_code Code;
+};
+
+using HashCodeHashBuilder = HashBuilder<hashbuilder_detail::HashCodeHasher,
+                                        support::endianness::native>;
+} // namespace hashbuilder_detail
+
+/// Provide a default implementation of `hash_value` when `addHash(const T &)`
+/// is supported.
+template <typename T>
+std::enable_if_t<
+    is_detected<hashbuilder_detail::HashCodeHashBuilder::HasAddHashT, T>::value,
+    hash_code>
+hash_value(const T &Value) {
+  hashbuilder_detail::HashCodeHashBuilder HBuilder;
+  HBuilder.add(Value);
+  return HBuilder.getHasher().Code;
+}
 } // end namespace llvm
 
 #endif // LLVM_SUPPORT_HASHBUILDER_H

llvm/unittests/ADT/HashingTest.cpp

 //===- llvm/unittest/ADT/HashingTest.cpp ----------------------------------===//
 //
 // 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
 //
 //===----------------------------------------------------------------------===//
 //
 // Hashing.h unit tests.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/Hashing.h"
 #include "llvm/Support/DataTypes.h"
+#include "llvm/Support/HashBuilder.h"
 #include "gtest/gtest.h"
 #include <deque>
 #include <list>
 #include <map>
 #include <vector>
 
 namespace llvm {
 
#define CHECK_SAME(...)                                                        \
   CHECK_SAME(1, 2, 3, 4, 5);
   CHECK_SAME(1, 2, 3, 4);
   CHECK_SAME(1, 2, 3);
   CHECK_SAME(1, 2);
   CHECK_SAME(1);
 #undef CHECK_SAME
 }
 
+struct StructWithHashBuilderSupport {
+  char C;
+  int I;
+  template <typename HasherT, llvm::support::endianness Endianness>
+  friend void addHash(llvm::HashBuilderImpl<HasherT, Endianness> &HBuilder,
+                      const StructWithHashBuilderSupport &Value) {
+    HBuilder.add(Value.C, Value.I);
   }
+};
+
+TEST(HashingTest, HashWithHashBuilder) {
+  StructWithHashBuilderSupport S{'c', 1};
+  EXPECT_NE(static_cast<size_t>(llvm::hash_value(S)), static_cast<size_t>(0));
+}
+
+struct StructWithHashBuilderAndHashValueSupport {
+  char C;
+  int I;
+  template <typename HasherT, llvm::support::endianness Endianness>
+  friend void addHash(llvm::HashBuilderImpl<HasherT, Endianness> &HBuilder,
+                      const StructWithHashBuilderAndHashValueSupport &Value) {}
+  friend hash_code
+  hash_value(const StructWithHashBuilderAndHashValueSupport &Value) {
+    return 0xbeef;
+  }
+};
+
+TEST(HashingTest, HashBuilderAndHashValue) {
+  StructWithHashBuilderAndHashValueSupport S{'c', 1};
+  EXPECT_EQ(static_cast<size_t>(hash_value(S)), static_cast<size_t>(0xbeef));
+}
+
+} // namespace