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:`. --- .../Example/Firestore.xcodeproj/project.pbxproj | 4 + .../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 ++++++++++++++ 8 files changed, 270 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 diff --git a/Firestore/Example/Firestore.xcodeproj/project.pbxproj b/Firestore/Example/Firestore.xcodeproj/project.pbxproj index 8aecc9f..35d6e83 100644 --- a/Firestore/Example/Firestore.xcodeproj/project.pbxproj +++ b/Firestore/Example/Firestore.xcodeproj/project.pbxproj @@ -28,6 +28,7 @@ 347FDC6AA737A754541F7C8A /* Pods_Firestore_Tests_iOS.framework in Frameworks */ = {isa = PBXBuildFile; fileRef = 8525646842C83F703237BAA4 /* Pods_Firestore_Tests_iOS.framework */; }; 3B843E4C1F3A182900548890 /* remote_store_spec_test.json in Resources */ = {isa = PBXBuildFile; fileRef = 3B843E4A1F3930A400548890 /* remote_store_spec_test.json */; }; 5436F32420008FAD006E51E3 /* string_printf_test.cc in Sources */ = {isa = PBXBuildFile; fileRef = 5436F32320008FAD006E51E3 /* string_printf_test.cc */; }; + 54511E8E209805F8005BD28F /* hashing_test.cc in Sources */ = {isa = PBXBuildFile; fileRef = 54511E8D209805F8005BD28F /* hashing_test.cc */; }; 5467FB01203E5717009C9584 /* FIRFirestoreTests.mm in Sources */ = {isa = PBXBuildFile; fileRef = 5467FAFF203E56F8009C9584 /* FIRFirestoreTests.mm */; }; 5467FB08203E6A44009C9584 /* app_testing.mm in Sources */ = {isa = PBXBuildFile; fileRef = 5467FB07203E6A44009C9584 /* app_testing.mm */; }; 54740A571FC914BA00713A1A /* secure_random_test.cc in Sources */ = {isa = PBXBuildFile; fileRef = 54740A531FC913E500713A1A /* secure_random_test.cc */; }; @@ -243,6 +244,7 @@ 42491D7DC8C8CD245CC22B93 /* Pods-SwiftBuildTest.debug.xcconfig */ = {isa = PBXFileReference; includeInIndex = 1; lastKnownFileType = text.xcconfig; name = "Pods-SwiftBuildTest.debug.xcconfig"; path = "Pods/Target Support Files/Pods-SwiftBuildTest/Pods-SwiftBuildTest.debug.xcconfig"; sourceTree = ""; }; 4EBC5F5ABE1FD097EFE5E224 /* Pods-Firestore_Example.release.xcconfig */ = {isa = PBXFileReference; includeInIndex = 1; lastKnownFileType = text.xcconfig; name = "Pods-Firestore_Example.release.xcconfig"; path = "Pods/Target Support Files/Pods-Firestore_Example/Pods-Firestore_Example.release.xcconfig"; sourceTree = ""; }; 5436F32320008FAD006E51E3 /* string_printf_test.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = string_printf_test.cc; path = ../../core/test/firebase/firestore/util/string_printf_test.cc; sourceTree = ""; }; + 54511E8D209805F8005BD28F /* hashing_test.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = hashing_test.cc; path = ../../core/test/firebase/firestore/util/hashing_test.cc; sourceTree = ""; }; 5467FAFF203E56F8009C9584 /* FIRFirestoreTests.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = FIRFirestoreTests.mm; sourceTree = ""; }; 5467FB06203E6A44009C9584 /* app_testing.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; name = app_testing.h; path = ../../core/test/firebase/firestore/testutil/app_testing.h; sourceTree = ""; }; 5467FB07203E6A44009C9584 /* app_testing.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; name = app_testing.mm; path = ../../core/test/firebase/firestore/testutil/app_testing.mm; sourceTree = ""; }; @@ -497,6 +499,7 @@ 54740A521FC913E500713A1A /* autoid_test.cc */, AB380D01201BC69F00D97691 /* bits_test.cc */, 548DB928200D59F600E00ABC /* comparison_test.cc */, + 54511E8D209805F8005BD28F /* hashing_test.cc */, 54C2294E1FECABAE007D065B /* log_test.cc */, AB380D03201BC6E400D97691 /* ordered_code_test.cc */, 54740A531FC913E500713A1A /* secure_random_test.cc */, @@ -1481,6 +1484,7 @@ ABF6506C201131F8005F2C74 /* timestamp_test.cc in Sources */, 5492E0AE2021552D00B64F25 /* FSTLevelDBQueryCacheTests.mm in Sources */, ABC1D7DC2023A04B00BA84F0 /* credentials_provider_test.cc in Sources */, + 54511E8E209805F8005BD28F /* hashing_test.cc in Sources */, 5492E059202154AB00B64F25 /* FIRQuerySnapshotTests.mm in Sources */, 5492E050202154AA00B64F25 /* FIRCollectionReferenceTests.mm in Sources */, ABA495BB202B7E80008A7851 /* snapshot_version_test.cc in Sources */, 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