spy_hash_state.h (9576B)
1 // Copyright 2018 The Abseil Authors. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // https://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef ABSL_HASH_INTERNAL_SPY_HASH_STATE_H_ 16 #define ABSL_HASH_INTERNAL_SPY_HASH_STATE_H_ 17 18 #include <algorithm> 19 #include <cstdint> 20 #include <ostream> 21 #include <string> 22 #include <vector> 23 24 #include "absl/hash/hash.h" 25 #include "absl/strings/match.h" 26 #include "absl/strings/str_format.h" 27 #include "absl/strings/str_join.h" 28 29 namespace absl { 30 ABSL_NAMESPACE_BEGIN 31 namespace hash_internal { 32 33 // SpyHashState is an implementation of the HashState API that simply 34 // accumulates all input bytes in an internal buffer. This makes it useful 35 // for testing AbslHashValue overloads (so long as they are templated on the 36 // HashState parameter), since it can report the exact hash representation 37 // that the AbslHashValue overload produces. 38 // 39 // Sample usage: 40 // EXPECT_EQ(SpyHashState::combine(SpyHashState(), foo), 41 // SpyHashState::combine(SpyHashState(), bar)); 42 template <typename T> 43 class SpyHashStateImpl : public HashStateBase<SpyHashStateImpl<T>> { 44 public: 45 SpyHashStateImpl() : error_(std::make_shared<absl::optional<std::string>>()) { 46 static_assert(std::is_void<T>::value, ""); 47 } 48 49 // Move-only 50 SpyHashStateImpl(const SpyHashStateImpl&) = delete; 51 SpyHashStateImpl& operator=(const SpyHashStateImpl&) = delete; 52 53 SpyHashStateImpl(SpyHashStateImpl&& other) noexcept { 54 *this = std::move(other); 55 } 56 57 SpyHashStateImpl& operator=(SpyHashStateImpl&& other) noexcept { 58 hash_representation_ = std::move(other.hash_representation_); 59 error_ = other.error_; 60 moved_from_ = other.moved_from_; 61 other.moved_from_ = true; 62 return *this; 63 } 64 65 template <typename U> 66 SpyHashStateImpl(SpyHashStateImpl<U>&& other) { // NOLINT 67 hash_representation_ = std::move(other.hash_representation_); 68 error_ = other.error_; 69 moved_from_ = other.moved_from_; 70 other.moved_from_ = true; 71 } 72 73 template <typename A, typename... Args> 74 static SpyHashStateImpl combine(SpyHashStateImpl s, const A& a, 75 const Args&... args) { 76 // Pass an instance of SpyHashStateImpl<A> when trying to combine `A`. This 77 // allows us to test that the user only uses this instance for combine calls 78 // and does not call AbslHashValue directly. 79 // See AbslHashValue implementation at the bottom. 80 s = SpyHashStateImpl<A>::HashStateBase::combine(std::move(s), a); 81 return SpyHashStateImpl::combine(std::move(s), args...); 82 } 83 static SpyHashStateImpl combine(SpyHashStateImpl s) { 84 if (direct_absl_hash_value_error_) { 85 *s.error_ = "AbslHashValue should not be invoked directly."; 86 } else if (s.moved_from_) { 87 *s.error_ = "Used moved-from instance of the hash state object."; 88 } 89 return s; 90 } 91 92 static void SetDirectAbslHashValueError() { 93 direct_absl_hash_value_error_ = true; 94 } 95 96 // Two SpyHashStateImpl objects are equal if they hold equal hash 97 // representations. 98 friend bool operator==(const SpyHashStateImpl& lhs, 99 const SpyHashStateImpl& rhs) { 100 return lhs.hash_representation_ == rhs.hash_representation_; 101 } 102 103 friend bool operator!=(const SpyHashStateImpl& lhs, 104 const SpyHashStateImpl& rhs) { 105 return !(lhs == rhs); 106 } 107 108 enum class CompareResult { 109 kEqual, 110 kASuffixB, 111 kBSuffixA, 112 kUnequal, 113 }; 114 115 static CompareResult Compare(const SpyHashStateImpl& a, 116 const SpyHashStateImpl& b) { 117 const std::string a_flat = absl::StrJoin(a.hash_representation_, ""); 118 const std::string b_flat = absl::StrJoin(b.hash_representation_, ""); 119 if (a_flat == b_flat) return CompareResult::kEqual; 120 if (absl::EndsWith(a_flat, b_flat)) return CompareResult::kBSuffixA; 121 if (absl::EndsWith(b_flat, a_flat)) return CompareResult::kASuffixB; 122 return CompareResult::kUnequal; 123 } 124 125 // operator<< prints the hash representation as a hex and ASCII dump, to 126 // facilitate debugging. 127 friend std::ostream& operator<<(std::ostream& out, 128 const SpyHashStateImpl& hash_state) { 129 out << "[\n"; 130 for (auto& s : hash_state.hash_representation_) { 131 size_t offset = 0; 132 for (char c : s) { 133 if (offset % 16 == 0) { 134 out << absl::StreamFormat("\n0x%04x: ", offset); 135 } 136 if (offset % 2 == 0) { 137 out << " "; 138 } 139 out << absl::StreamFormat("%02x", c); 140 ++offset; 141 } 142 out << "\n"; 143 } 144 return out << "]"; 145 } 146 147 // The base case of the combine recursion, which writes raw bytes into the 148 // internal buffer. 149 static SpyHashStateImpl combine_contiguous(SpyHashStateImpl hash_state, 150 const unsigned char* begin, 151 size_t size) { 152 const size_t large_chunk_stride = PiecewiseChunkSize(); 153 // Combining a large contiguous buffer must have the same effect as 154 // doing it piecewise by the stride length, followed by the (possibly 155 // empty) remainder. 156 while (size > large_chunk_stride) { 157 hash_state = SpyHashStateImpl::combine_contiguous( 158 std::move(hash_state), begin, large_chunk_stride); 159 begin += large_chunk_stride; 160 size -= large_chunk_stride; 161 } 162 163 if (size > 0) { 164 hash_state.hash_representation_.emplace_back( 165 reinterpret_cast<const char*>(begin), size); 166 } 167 return hash_state; 168 } 169 170 using SpyHashStateImpl::HashStateBase::combine_contiguous; 171 172 template <typename CombinerT> 173 static SpyHashStateImpl RunCombineUnordered(SpyHashStateImpl state, 174 CombinerT combiner) { 175 UnorderedCombinerCallback cb; 176 177 combiner(SpyHashStateImpl<void>{}, std::ref(cb)); 178 179 std::sort(cb.element_hash_representations.begin(), 180 cb.element_hash_representations.end()); 181 state.hash_representation_.insert(state.hash_representation_.end(), 182 cb.element_hash_representations.begin(), 183 cb.element_hash_representations.end()); 184 if (cb.error && cb.error->has_value()) { 185 state.error_ = std::move(cb.error); 186 } 187 return state; 188 } 189 190 absl::optional<std::string> error() const { 191 if (moved_from_) { 192 return "Returned a moved-from instance of the hash state object."; 193 } 194 return *error_; 195 } 196 197 private: 198 template <typename U> 199 friend class SpyHashStateImpl; 200 friend struct CombineRaw; 201 202 struct UnorderedCombinerCallback { 203 std::vector<std::string> element_hash_representations; 204 std::shared_ptr<absl::optional<std::string>> error; 205 206 // The inner spy can have a different type. 207 template <typename U> 208 void operator()(SpyHashStateImpl<U>& inner) { 209 element_hash_representations.push_back( 210 absl::StrJoin(inner.hash_representation_, "")); 211 if (inner.error_->has_value()) { 212 error = std::move(inner.error_); 213 } 214 inner = SpyHashStateImpl<void>{}; 215 } 216 }; 217 218 // Combines raw data from e.g. integrals/floats/pointers/etc. 219 static SpyHashStateImpl combine_raw(SpyHashStateImpl state, uint64_t value) { 220 const unsigned char* data = reinterpret_cast<const unsigned char*>(&value); 221 return SpyHashStateImpl::combine_contiguous(std::move(state), data, 8); 222 } 223 224 // This is true if SpyHashStateImpl<T> has been passed to a call of 225 // AbslHashValue with the wrong type. This detects that the user called 226 // AbslHashValue directly (because the hash state type does not match). 227 static bool direct_absl_hash_value_error_; 228 229 std::vector<std::string> hash_representation_; 230 // This is a shared_ptr because we want all instances of the particular 231 // SpyHashState run to share the field. This way we can set the error for 232 // use-after-move and all the copies will see it. 233 std::shared_ptr<absl::optional<std::string>> error_; 234 bool moved_from_ = false; 235 }; 236 237 template <typename T> 238 bool SpyHashStateImpl<T>::direct_absl_hash_value_error_; 239 240 template <bool& B> 241 struct OdrUse { 242 constexpr OdrUse() {} 243 bool& b = B; 244 }; 245 246 template <void (*)()> 247 struct RunOnStartup { 248 static bool run; 249 static constexpr OdrUse<run> kOdrUse{}; 250 }; 251 252 template <void (*f)()> 253 bool RunOnStartup<f>::run = (f(), true); 254 255 template < 256 typename T, typename U, 257 // Only trigger for when (T != U), 258 typename = absl::enable_if_t<!std::is_same<T, U>::value>, 259 // This statement works in two ways: 260 // - First, it instantiates RunOnStartup and forces the initialization of 261 // `run`, which set the global variable. 262 // - Second, it triggers a SFINAE error disabling the overload to prevent 263 // compile time errors. If we didn't disable the overload we would get 264 // ambiguous overload errors, which we don't want. 265 int = RunOnStartup<SpyHashStateImpl<T>::SetDirectAbslHashValueError>::run> 266 void AbslHashValue(SpyHashStateImpl<T>, const U&); 267 268 using SpyHashState = SpyHashStateImpl<void>; 269 270 } // namespace hash_internal 271 ABSL_NAMESPACE_END 272 } // namespace absl 273 274 #endif // ABSL_HASH_INTERNAL_SPY_HASH_STATE_H_