legacy-libs/grpc/deps/grpc/third_party/abseil-cpp/absl/hash/hash_testing.h

   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_HASH_TESTING_H_
  16 #define ABSL_HASH_HASH_TESTING_H_
  17
  18 #include <initializer_list>
  19 #include <tuple>
  20 #include <type_traits>
  21 #include <vector>
  22
  23 #include "gmock/gmock.h"
  24 #include "gtest/gtest.h"
  25 #include "absl/hash/internal/spy_hash_state.h"
  26 #include "absl/meta/type_traits.h"
  27 #include "absl/strings/str_cat.h"
  28 #include "absl/types/variant.h"
  29
  30 namespace absl {
  31
  32 // Run the absl::Hash algorithm over all the elements passed in and verify that
  33 // their hash expansion is congruent with their `==` operator.
  34 //
  35 // It is used in conjunction with EXPECT_TRUE. Failures will output information
  36 // on what requirement failed and on which objects.
  37 //
  38 // Users should pass a collection of types as either an initializer list or a
  39 // container of cases.
  40 //
  41 //   EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
  42 //       {v1, v2, ..., vN}));
  43 //
  44 //   std::vector<MyType> cases;
  45 //   // Fill cases...
  46 //   EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(cases));
  47 //
  48 // Users can pass a variety of types for testing heterogeneous lookup with
  49 // `std::make_tuple`:
  50 //
  51 //   EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
  52 //       std::make_tuple(v1, v2, ..., vN)));
  53 //
  54 //
  55 // Ideally, the values passed should provide enough coverage of the `==`
  56 // operator and the AbslHashValue implementations.
  57 // For dynamically sized types, the empty state should usually be included in
  58 // the values.
  59 //
  60 // The function accepts an optional comparator function, in case that `==` is
  61 // not enough for the values provided.
  62 //
  63 // Usage:
  64 //
  65 //   EXPECT_TRUE(absl::VerifyTypeImplementsAbslHashCorrectly(
  66 //       std::make_tuple(v1, v2, ..., vN), MyCustomEq{}));
  67 //
  68 // It checks the following requirements:
  69 //   1. The expansion for a value is deterministic.
  70 //   2. For any two objects `a` and `b` in the sequence, if `a == b` evaluates
  71 //      to true, then their hash expansion must be equal.
  72 //   3. If `a == b` evaluates to false their hash expansion must be unequal.
  73 //   4. If `a == b` evaluates to false neither hash expansion can be a
  74 //      suffix of the other.
  75 //   5. AbslHashValue overloads should not be called by the user. They are only
  76 //      meant to be called by the framework. Users should call H::combine() and
  77 //      H::combine_contiguous().
  78 //   6. No moved-from instance of the hash state is used in the implementation
  79 //      of AbslHashValue.
  80 //
  81 // The values do not have to have the same type. This can be useful for
  82 // equivalent types that support heterogeneous lookup.
  83 //
  84 // A possible reason for breaking (2) is combining state in the hash expansion
  85 // that was not used in `==`.
  86 // For example:
  87 //
  88 // struct Bad2 {
  89 //   int a, b;
  90 //   template <typename H>
  91 //   friend H AbslHashValue(H state, Bad2 x) {
  92 //     // Uses a and b.
  93 //     return H::combine(std::move(state), x.a, x.b);
  94 //   }
  95 //   friend bool operator==(Bad2 x, Bad2 y) {
  96 //     // Only uses a.
  97 //     return x.a == y.a;
  98 //   }
  99 // };
 100 //
 101 // As for (3), breaking this usually means that there is state being passed to
 102 // the `==` operator that is not used in the hash expansion.
 103 // For example:
 104 //
 105 // struct Bad3 {
 106 //   int a, b;
 107 //   template <typename H>
 108 //   friend H AbslHashValue(H state, Bad3 x) {
 109 //     // Only uses a.
 110 //     return H::combine(std::move(state), x.a);
 111 //   }
 112 //   friend bool operator==(Bad3 x, Bad3 y) {
 113 //     // Uses a and b.
 114 //     return x.a == y.a && x.b == y.b;
 115 //   }
 116 // };
 117 //
 118 // Finally, a common way to break 4 is by combining dynamic ranges without
 119 // combining the size of the range.
 120 // For example:
 121 //
 122 // struct Bad4 {
 123 //   int *p, size;
 124 //   template <typename H>
 125 //   friend H AbslHashValue(H state, Bad4 x) {
 126 //     return H::combine_contiguous(std::move(state), x.p, x.p + x.size);
 127 //   }
 128 //   friend bool operator==(Bad4 x, Bad4 y) {
 129 //    // Compare two ranges for equality. C++14 code can instead use std::equal.
 130 //     return absl::equal(x.p, x.p + x.size, y.p, y.p + y.size);
 131 //   }
 132 // };
 133 //
 134 // An easy solution to this is to combine the size after combining the range,
 135 // like so:
 136 // template <typename H>
 137 // friend H AbslHashValue(H state, Bad4 x) {
 138 //   return H::combine(
 139 //       H::combine_contiguous(std::move(state), x.p, x.p + x.size), x.size);
 140 // }
 141 //
 142 template <int&... ExplicitBarrier, typename Container>
 143 ABSL_MUST_USE_RESULT testing::AssertionResult
 144 VerifyTypeImplementsAbslHashCorrectly(const Container& values);
 145
 146 template <int&... ExplicitBarrier, typename Container, typename Eq>
 147 ABSL_MUST_USE_RESULT testing::AssertionResult
 148 VerifyTypeImplementsAbslHashCorrectly(const Container& values, Eq equals);
 149
 150 template <int&..., typename T>
 151 ABSL_MUST_USE_RESULT testing::AssertionResult
 152 VerifyTypeImplementsAbslHashCorrectly(std::initializer_list<T> values);
 153
 154 template <int&..., typename T, typename Eq>
 155 ABSL_MUST_USE_RESULT testing::AssertionResult
 156 VerifyTypeImplementsAbslHashCorrectly(std::initializer_list<T> values,
 157                                       Eq equals);
 158
 159 namespace hash_internal {
 160
 161 struct PrintVisitor {
 162   size_t index;
 163   template <typename T>
 164   std::string operator()(const T* value) const {
 165     return absl::StrCat("#", index, "(", testing::PrintToString(*value), ")");
 166   }
 167 };
 168
 169 template <typename Eq>
 170 struct EqVisitor {
 171   Eq eq;
 172   template <typename T, typename U>
 173   bool operator()(const T* t, const U* u) const {
 174     return eq(*t, *u);
 175   }
 176 };
 177
 178 struct ExpandVisitor {
 179   template <typename T>
 180   SpyHashState operator()(const T* value) const {
 181     return SpyHashState::combine(SpyHashState(), *value);
 182   }
 183 };
 184
 185 template <typename Container, typename Eq>
 186 ABSL_MUST_USE_RESULT testing::AssertionResult
 187 VerifyTypeImplementsAbslHashCorrectly(const Container& values, Eq equals) {
 188   using V = typename Container::value_type;
 189
 190   struct Info {
 191     const V& value;
 192     size_t index;
 193     std::string ToString() const {
 194       return absl::visit(PrintVisitor{index}, value);
 195     }
 196     SpyHashState expand() const { return absl::visit(ExpandVisitor{}, value); }
 197   };
 198
 199   using EqClass = std::vector<Info>;
 200   std::vector<EqClass> classes;
 201
 202   // Gather the values in equivalence classes.
 203   size_t i = 0;
 204   for (const auto& value : values) {
 205     EqClass* c = nullptr;
 206     for (auto& eqclass : classes) {
 207       if (absl::visit(EqVisitor<Eq>{equals}, value, eqclass[0].value)) {
 208         c = &eqclass;
 209         break;
 210       }
 211     }
 212     if (c == nullptr) {
 213       classes.emplace_back();
 214       c = &classes.back();
 215     }
 216     c->push_back({value, i});
 217     ++i;
 218
 219     // Verify potential errors captured by SpyHashState.
 220     if (auto error = c->back().expand().error()) {
 221       return testing::AssertionFailure() << *error;
 222     }
 223   }
 224
 225   if (classes.size() < 2) {
 226     return testing::AssertionFailure()
 227            << "At least two equivalence classes are expected.";
 228   }
 229
 230   // We assume that equality is correctly implemented.
 231   // Now we verify that AbslHashValue is also correctly implemented.
 232
 233   for (const auto& c : classes) {
 234     // All elements of the equivalence class must have the same hash
 235     // expansion.
 236     const SpyHashState expected = c[0].expand();
 237     for (const Info& v : c) {
 238       if (v.expand() != v.expand()) {
 239         return testing::AssertionFailure()
 240                << "Hash expansion for " << v.ToString()
 241                << " is non-deterministic.";
 242       }
 243       if (v.expand() != expected) {
 244         return testing::AssertionFailure()
 245                << "Values " << c[0].ToString() << " and " << v.ToString()
 246                << " evaluate as equal but have an unequal hash expansion.";
 247       }
 248     }
 249
 250     // Elements from other classes must have different hash expansion.
 251     for (const auto& c2 : classes) {
 252       if (&c == &c2) continue;
 253       const SpyHashState c2_hash = c2[0].expand();
 254       switch (SpyHashState::Compare(expected, c2_hash)) {
 255         case SpyHashState::CompareResult::kEqual:
 256           return testing::AssertionFailure()
 257                  << "Values " << c[0].ToString() << " and " << c2[0].ToString()
 258                  << " evaluate as unequal but have an equal hash expansion.";
 259         case SpyHashState::CompareResult::kBSuffixA:
 260           return testing::AssertionFailure()
 261                  << "Hash expansion of " << c2[0].ToString()
 262                  << " is a suffix of the hash expansion of " << c[0].ToString()
 263                  << ".";
 264         case SpyHashState::CompareResult::kASuffixB:
 265           return testing::AssertionFailure()
 266                  << "Hash expansion of " << c[0].ToString()
 267                  << " is a suffix of the hash expansion of " << c2[0].ToString()
 268                  << ".";
 269         case SpyHashState::CompareResult::kUnequal:
 270           break;
 271       }
 272     }
 273   }
 274   return testing::AssertionSuccess();
 275 }
 276
 277 template <typename... T>
 278 struct TypeSet {
 279   template <typename U, bool = disjunction<std::is_same<T, U>...>::value>
 280   struct Insert {
 281     using type = TypeSet<U, T...>;
 282   };
 283   template <typename U>
 284   struct Insert<U, true> {
 285     using type = TypeSet;
 286   };
 287
 288   template <template <typename...> class C>
 289   using apply = C<T...>;
 290 };
 291
 292 template <typename... T>
 293 struct MakeTypeSet : TypeSet<> {};
 294 template <typename T, typename... Ts>
 295 struct MakeTypeSet<T, Ts...> : MakeTypeSet<Ts...>::template Insert<T>::type {};
 296
 297 template <typename... T>
 298 using VariantForTypes = typename MakeTypeSet<
 299     const typename std::decay<T>::type*...>::template apply<absl::variant>;
 300
 301 template <typename Container>
 302 struct ContainerAsVector {
 303   using V = absl::variant<const typename Container::value_type*>;
 304   using Out = std::vector<V>;
 305
 306   static Out Do(const Container& values) {
 307     Out out;
 308     for (const auto& v : values) out.push_back(&v);
 309     return out;
 310   }
 311 };
 312
 313 template <typename... T>
 314 struct ContainerAsVector<std::tuple<T...>> {
 315   using V = VariantForTypes<T...>;
 316   using Out = std::vector<V>;
 317
 318   template <size_t... I>
 319   static Out DoImpl(const std::tuple<T...>& tuple, absl::index_sequence<I...>) {
 320     return Out{&std::get<I>(tuple)...};
 321   }
 322
 323   static Out Do(const std::tuple<T...>& values) {
 324     return DoImpl(values, absl::index_sequence_for<T...>());
 325   }
 326 };
 327
 328 template <>
 329 struct ContainerAsVector<std::tuple<>> {
 330   static std::vector<VariantForTypes<int>> Do(std::tuple<>) { return {}; }
 331 };
 332
 333 struct DefaultEquals {
 334   template <typename T, typename U>
 335   bool operator()(const T& t, const U& u) const {
 336     return t == u;
 337   }
 338 };
 339
 340 }  // namespace hash_internal
 341
 342 template <int&..., typename Container>
 343 ABSL_MUST_USE_RESULT testing::AssertionResult
 344 VerifyTypeImplementsAbslHashCorrectly(const Container& values) {
 345   return hash_internal::VerifyTypeImplementsAbslHashCorrectly(
 346       hash_internal::ContainerAsVector<Container>::Do(values),
 347       hash_internal::DefaultEquals{});
 348 }
 349
 350 template <int&..., typename Container, typename Eq>
 351 ABSL_MUST_USE_RESULT testing::AssertionResult
 352 VerifyTypeImplementsAbslHashCorrectly(const Container& values, Eq equals) {
 353   return hash_internal::VerifyTypeImplementsAbslHashCorrectly(
 354       hash_internal::ContainerAsVector<Container>::Do(values), equals);
 355 }
 356
 357 template <int&..., typename T>
 358 ABSL_MUST_USE_RESULT testing::AssertionResult
 359 VerifyTypeImplementsAbslHashCorrectly(std::initializer_list<T> values) {
 360   return hash_internal::VerifyTypeImplementsAbslHashCorrectly(
 361       hash_internal::ContainerAsVector<std::initializer_list<T>>::Do(values),
 362       hash_internal::DefaultEquals{});
 363 }
 364
 365 template <int&..., typename T, typename Eq>
 366 ABSL_MUST_USE_RESULT testing::AssertionResult
 367 VerifyTypeImplementsAbslHashCorrectly(std::initializer_list<T> values,
 368                                       Eq equals) {
 369   return hash_internal::VerifyTypeImplementsAbslHashCorrectly(
 370       hash_internal::ContainerAsVector<std::initializer_list<T>>::Do(values),
 371       equals);
 372 }
 373
 374 }  // namespace absl
 375
 376 #endif  // ABSL_HASH_HASH_TESTING_H_