From 51be76700c3b71a0924e8eaf7bac4b02e0130e62 Mon Sep 17 00:00:00 2001 From: Gil Date: Tue, 1 May 2018 08:57:31 -0700 Subject: 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:`. --- .../core/src/firebase/firestore/model/base_path.h | 10 +- .../src/firebase/firestore/model/database_id.h | 6 +- .../src/firebase/firestore/model/document_key.h | 3 +- .../src/firebase/firestore/util/CMakeLists.txt | 1 + .../core/src/firebase/firestore/util/hashing.h | 151 +++++++++++++++++++++ .../test/firebase/firestore/util/CMakeLists.txt | 1 + .../test/firebase/firestore/util/hashing_test.cc | 105 ++++++++++++++ 7 files changed, 266 insertions(+), 11 deletions(-) create mode 100644 Firestore/core/src/firebase/firestore/util/hashing.h create mode 100644 Firestore/core/test/firebase/firestore/util/hashing_test.cc (limited to 'Firestore/core') 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 #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 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 #include +#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 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{}(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 +#include + +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 +struct HashChoice : HashChoice {}; + +template <> +struct HashChoice<2> {}; + +template +size_t InvokeHash(const K& value); + +/** + * Hashes the given value if it defines a Hash() member. + * + * @return The result of `value.Hash()`. + */ +template +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{}(value)` + */ +template +auto RankedInvokeHash(const K& value, HashChoice<1>) + -> decltype(std::hash{}(value)) { + return std::hash{}(value); +} + +/** + * Hashes the contents of the given range of values if the value_type of the + * range can be hashed. + */ +template +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 +size_t InvokeHash(const K& value) { + return RankedInvokeHash(value, HashChoice<0>{}); +} + +inline size_t HashInternal(size_t state) { + return state; +} + +template +size_t HashInternal(size_t state, const T& value, const Ts&... rest) { + state = Combine(state, InvokeHash(value)); + return HashInternal(state, rest...); +} + +} // namespace impl + +template +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{}(0), Hash(0)); +} + +TEST(HashingTest, Float) { + ASSERT_EQ(std::hash{}(1.0), Hash(1.0)); +} + +TEST(HashingTest, String) { + ASSERT_EQ(std::hash{}("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(42), Hash(HasHashMember{})); +} + +TEST(HashingTest, RangeOfStdHashable) { + std::vector values{42}; + ASSERT_EQ(31u * 42u + 1, Hash(values)); + + std::vector values_leading_zero{0, 42}; + std::vector 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 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 -- cgit v1.2.3