Define a general hashing utility in C++ (#1195)

This is good enough to make it possible for the new C++ code to
interoperate with existing Objective-C code where `-hash` is required if
you override `-isEqual:`.

7 files changed, 266 insertions, 11 deletions

diff --git a/Firestore/core/src/firebase/firestore/model/base_path.h b/Firestore/core/src/firebase/firestore/model/base_path.h
index bc1f89d..59a9b5a 100644
--- a/Firestore/core/src/firebase/firestore/model/base_path.h
+++ b/Firestore/core/src/firebase/firestore/model/base_path.h
@@ -25,6 +25,7 @@
 #include <vector>
 
 #include "Firestore/core/src/firebase/firestore/util/firebase_assert.h"
+#include "Firestore/core/src/firebase/firestore/util/hashing.h"
 
 namespace firebase {
 namespace firestore {
@@ -162,13 +163,8 @@ class BasePath {
 #if defined(__OBJC__)
   // For Objective-C++ hash; to be removed after migration.
   // Do NOT use in C++ code.
-  NSUInteger Hash() const {
-    std::hash<std::string> hash_fn;
-    NSUInteger hash_result = 0;
-    for (const std::string& segment : segments_) {
-      hash_result = hash_result * 31u + hash_fn(segment);
-    }
-    return hash_result;
+  size_t Hash() const {
+    return util::Hash(segments_);
   }
 #endif  // defined(__OBJC__)
 
diff --git a/Firestore/core/src/firebase/firestore/model/database_id.h b/Firestore/core/src/firebase/firestore/model/database_id.h
index 0c0e0ec..c432b8f 100644
--- a/Firestore/core/src/firebase/firestore/model/database_id.h
+++ b/Firestore/core/src/firebase/firestore/model/database_id.h
@@ -20,6 +20,7 @@
 #include <cstdint>
 #include <string>
 
+#include "Firestore/core/src/firebase/firestore/util/hashing.h"
 #include "absl/strings/string_view.h"
 
 namespace firebase {
@@ -62,9 +63,8 @@ class DatabaseId {
 #if defined(__OBJC__)
   // For objective-c++ hash; to be removed after migration.
   // Do NOT use in C++ code.
-  NSUInteger Hash() const {
-    std::hash<std::string> hash_fn;
-    return hash_fn(project_id_) * 31u + hash_fn(database_id_);
+  size_t Hash() const {
+    return util::Hash(project_id_, database_id_);
   }
 #endif  // defined(__OBJC__)
 
diff --git a/Firestore/core/src/firebase/firestore/model/document_key.h b/Firestore/core/src/firebase/firestore/model/document_key.h
index 4bdc04b..7f6478f 100644
--- a/Firestore/core/src/firebase/firestore/model/document_key.h
+++ b/Firestore/core/src/firebase/firestore/model/document_key.h
@@ -26,6 +26,7 @@
 #endif  // defined(__OBJC__)
 
 #include "Firestore/core/src/firebase/firestore/model/resource_path.h"
+#include "Firestore/core/src/firebase/firestore/util/hashing.h"
 #include "absl/strings/string_view.h"
 
 namespace firebase {
@@ -61,7 +62,7 @@ class DocumentKey {
   }
 
   NSUInteger Hash() const {
-    return std::hash<std::string>{}(ToString());
+    return util::Hash(ToString());
   }
 #endif
 
diff --git a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt
index 3afead1..95cd72f 100644
--- a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt
+++ b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt
@@ -128,6 +128,7 @@ cc_library(
     comparison.cc
     comparison.h
     config.h
+    hashing.h
     iterator_adaptors.h
     ordered_code.cc
     ordered_code.h
diff --git a/Firestore/core/src/firebase/firestore/util/hashing.h b/Firestore/core/src/firebase/firestore/util/hashing.h
new file mode 100644
index 0000000..d8058c8
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/util/hashing.h
@@ -0,0 +1,151 @@
+/*
+ * Copyright 2018 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_HASHING_H_
+#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_HASHING_H_
+
+#include <iterator>
+#include <type_traits>
+
+namespace firebase {
+namespace firestore {
+namespace util {
+
+// This is a pretty terrible hash implementation for lack of a better one being
+// readily available. It exists as a portability crutch between our existing
+// Objective-C code where overriding `-isEqual:` also requires `-hash` and C++
+// where `operator==()` can be defined without defining a hash code.
+//
+// It's based on the recommendation in Effective Java, Item 9, wherein you
+// implement composite hashes like so:
+//
+//     size_t result = first_;
+//     result = 31 * result + second_;
+//     result = 31 * result + third_;
+//     // ...
+//     return result;
+//
+// This is the basis of this implementation because that's what the existing
+// Objective-C code mostly does by hand. Using this implementation gets the
+// same result by calling
+//
+//     return util::Hash(first_, second_, /* ..., */ third_);
+//
+// TODO(wilhuff): Replace this with whatever Abseil releases.
+
+namespace impl {
+
+/**
+ * Combines a hash_value with whatever accumulated state there is so far.
+ */
+inline size_t Combine(size_t state, size_t hash_value) {
+  return 31 * state + hash_value;
+}
+
+/**
+ * Explicit ordering of hashers, allowing SFINAE without all the enable_if
+ * cruft.
+ *
+ * In order we try:
+ *   * A Hash() member, if defined and the return type is an integral type
+ *   * A std::hash specialization, if available
+ *   * A range-based specialization, valid if either of the above hold on the
+ *     members of the range.
+ *
+ * Explicit ordering resolves the ambiguity of the case where a std::hash
+ * specialization is available, but the type is also a range for whose members
+ * std::hash is also available, e.g. with std::string.
+ *
+ * HashChoice is a recursive type, defined such that HashChoice<0> is the most
+ * specific type with HashChoice<1> and beyond being progressively less
+ * specific. This causes the compiler to prioritize the overloads with
+ * lower-numbered HashChoice types, allowing compilation to succeed even if
+ * multiple specializations match.
+ */
+template <int I>
+struct HashChoice : HashChoice<I + 1> {};
+
+template <>
+struct HashChoice<2> {};
+
+template <typename K>
+size_t InvokeHash(const K& value);
+
+/**
+ * Hashes the given value if it defines a Hash() member.
+ *
+ * @return The result of `value.Hash()`.
+ */
+template <typename K>
+auto RankedInvokeHash(const K& value, HashChoice<0>) -> decltype(value.Hash()) {
+  return value.Hash();
+}
+
+/**
+ * Hashes the given value if it has a specialization of std::hash.
+ *
+ * @return The result of `std::hash<K>{}(value)`
+ */
+template <typename K>
+auto RankedInvokeHash(const K& value, HashChoice<1>)
+    -> decltype(std::hash<K>{}(value)) {
+  return std::hash<K>{}(value);
+}
+
+/**
+ * Hashes the contents of the given range of values if the value_type of the
+ * range can be hashed.
+ */
+template <typename Range>
+auto RankedInvokeHash(const Range& range, HashChoice<2>)
+    -> decltype(impl::InvokeHash(*std::begin(range))) {
+  size_t result = 0;
+  size_t size = 0;
+  for (auto&& element : range) {
+    ++size;
+    result = Combine(result, InvokeHash(element));
+  }
+  result = Combine(result, size);
+  return result;
+}
+
+template <typename K>
+size_t InvokeHash(const K& value) {
+  return RankedInvokeHash(value, HashChoice<0>{});
+}
+
+inline size_t HashInternal(size_t state) {
+  return state;
+}
+
+template <typename T, typename... Ts>
+size_t HashInternal(size_t state, const T& value, const Ts&... rest) {
+  state = Combine(state, InvokeHash(value));
+  return HashInternal(state, rest...);
+}
+
+}  // namespace impl
+
+template <typename... Ts>
+size_t Hash(const Ts&... values) {
+  return impl::HashInternal(0u, values...);
+}
+
+}  // namespace util
+}  // namespace firestore
+}  // namespace firebase
+
+#endif  // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_HASHING_H_
diff --git a/Firestore/core/test/firebase/firestore/util/CMakeLists.txt b/Firestore/core/test/firebase/firestore/util/CMakeLists.txt
index e5dbec5..e4da8d3 100644
--- a/Firestore/core/test/firebase/firestore/util/CMakeLists.txt
+++ b/Firestore/core/test/firebase/firestore/util/CMakeLists.txt
@@ -69,6 +69,7 @@ cc_test(
     autoid_test.cc
     bits_test.cc
     comparison_test.cc
+    hashing_test.cc
     iterator_adaptors_test.cc
     ordered_code_test.cc
     status_test.cc
diff --git a/Firestore/core/test/firebase/firestore/util/hashing_test.cc b/Firestore/core/test/firebase/firestore/util/hashing_test.cc
new file mode 100644
index 0000000..e5d9ff8
--- /dev/null
+++ b/Firestore/core/test/firebase/firestore/util/hashing_test.cc
@@ -0,0 +1,105 @@
+/*
+ * Copyright 2018 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include "Firestore/core/src/firebase/firestore/util/hashing.h"
+
+#include "absl/strings/string_view.h"
+#include "gtest/gtest.h"
+
+namespace firebase {
+namespace firestore {
+namespace util {
+
+struct HasHashMember {
+  size_t Hash() const {
+    return 42;
+  }
+};
+
+TEST(HashingTest, Int) {
+  ASSERT_EQ(std::hash<int>{}(0), Hash(0));
+}
+
+TEST(HashingTest, Float) {
+  ASSERT_EQ(std::hash<double>{}(1.0), Hash(1.0));
+}
+
+TEST(HashingTest, String) {
+  ASSERT_EQ(std::hash<std::string>{}("foobar"), Hash(std::string{"foobar"}));
+}
+
+TEST(HashingTest, StringView) {
+  // For StringView we expect the range-based hasher to kick in. This is
+  // basically terrible, but no worse than Java's `String.hashCode()`. Another
+  // possibility would be just to create a temporary std::string and std::hash
+  // that, but that requires an explicit specialization. Since we're only
+  // defining this for compatibility with Objective-C and not really sensitive
+  // to performance or hash quality here, this is good enough.
+  size_t expected = 'a';
+  expected = 31u * expected + 1;
+  ASSERT_EQ(expected, Hash(absl::string_view{"a"}));
+}
+
+TEST(HashingTest, SizeT) {
+  ASSERT_EQ(42u, Hash(size_t{42u}));
+}
+
+TEST(HashingTest, Array) {
+  int values[] = {0, 1, 2};
+
+  size_t expected = 0;
+  expected = 31 * expected + 1;
+  expected = 31 * expected + 2;
+  expected = 31 * expected + 3;  // length of array
+  ASSERT_EQ(expected, Hash(values));
+}
+
+TEST(HashingTest, HasHashMember) {
+  ASSERT_EQ(static_cast<size_t>(42), Hash(HasHashMember{}));
+}
+
+TEST(HashingTest, RangeOfStdHashable) {
+  std::vector<int> values{42};
+  ASSERT_EQ(31u * 42u + 1, Hash(values));
+
+  std::vector<int> values_leading_zero{0, 42};
+  std::vector<int> values_trailing_zero{42, 0};
+
+  EXPECT_NE(Hash(values), Hash(values_leading_zero));
+  EXPECT_NE(Hash(values), Hash(values_trailing_zero));
+  EXPECT_NE(Hash(values_leading_zero), Hash(values_trailing_zero));
+}
+
+TEST(HashingTest, RangeOfHashMember) {
+  std::vector<HasHashMember> values{HasHashMember{}};
+  ASSERT_EQ(31u * 42u + 1, Hash(values));
+}
+
+TEST(HashingTest, Composite) {
+  // Verify the result ends up as if hand-rolled
+  EXPECT_EQ(1u, Hash(1));
+  EXPECT_EQ(31u, Hash(1, 0));
+  EXPECT_EQ(31u * 31u, Hash(1, 0, 0));
+
+  size_t expected = Hash(1);
+  expected = 31 * expected + Hash(2);
+  expected = 31 * expected + Hash(3);
+  EXPECT_EQ(expected, Hash(1, 2, 3));
+}
+
+}  // namespace util
+}  // namespace firestore
+}  // namespace firebase