Constrain RequireUsableKey to non-transparent keys. For non-transparent Hash and Eq functors, RequireUsableKey previously accepted any argument type implicitly convertible to key_type. As a result, calling insert or emplace with different convertible types (such as int, unsigned, and double on a flat_hash_set<int>) instantiated separate find_or_prepare_insert<T> specializations—bloating binary size—and converted the key repeatedly on every hash and equality probe instead of once at the API boundary. Constraining RequireUsableKey to require either an exact key_type match or transparent Hash and Eq eliminates those redundant specializations and repeated conversions. Adding explicit insert(const init_type&) overloads preserves support for const init_type& and types convertible to it (such as keys derived from key_type) when PreferredMoveParamType is init_type&&. PiperOrigin-RevId: 1023078356
diff --git a/absl/container/BUILD.bazel b/absl/container/BUILD.bazel index fbf0d56..af27cd1 100644 --- a/absl/container/BUILD.bazel +++ b/absl/container/BUILD.bazel
@@ -442,6 +442,7 @@ "@do_not_use_for_gloop_visibility_only//gloop/util/gtl:__pkg__", ], deps = [ + ":common", "//absl/base:config", "//absl/base:core_headers", "//absl/hash", @@ -460,6 +461,7 @@ tags = ["no_test_loonix"], deps = [ ":container_memory", + ":hash_function_defaults", ":test_instance_tracker", "//absl/base:config", "//absl/base:no_destructor",
diff --git a/absl/container/CMakeLists.txt b/absl/container/CMakeLists.txt index 2d234aa..af5cc35 100644 --- a/absl/container/CMakeLists.txt +++ b/absl/container/CMakeLists.txt
@@ -494,6 +494,7 @@ DEPS absl::canonical_hash absl::config + absl::container_common absl::core_headers absl::hash absl::memory @@ -513,6 +514,7 @@ absl::config absl::container_memory absl::hash + absl::hash_function_defaults absl::no_destructor absl::overload absl::string_view
diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h index 54cde80..05fb990 100644 --- a/absl/container/internal/container_memory.h +++ b/absl/container/internal/container_memory.h
@@ -28,6 +28,7 @@ #include "absl/base/attributes.h" #include "absl/base/config.h" +#include "absl/container/internal/common.h" #include "absl/hash/hash.h" #include "absl/hash/internal/canonical_hash.h" #include "absl/memory/memory.h" @@ -318,11 +319,19 @@ return std::forward<F>(f)(key, std::forward<Arg>(arg)); } -// SFINAE probe checking that `PassedKey` can be hashed and compared against -// `ContainerKey`. +// SFINAE probe checking that `PassedKey` is `ContainerKey` (or `Hash` and `Eq` +// are transparent) and can be hashed and compared against `ContainerKey`. template <class ContainerKey, class Hash, class Eq> struct RequireUsableKey { - template <class PassedKey, class... Args> + template <class PassedKey, class... Args, + // Only allow heterogeneous keys when both `Hash` and `Eq` are + // transparent. Otherwise, non-transparent functors taking + // `const ContainerKey&` match implicitly convertible types, + // instantiating extra lookup functions and converting repeatedly. + std::enable_if_t< + std::is_same_v<absl::remove_cvref_t<PassedKey>, ContainerKey> || + (IsTransparent<Eq>::value && IsTransparent<Hash>::value), + int> = 0> std::pair< decltype(std::declval<const Hash&>()(std::declval<const PassedKey&>())), decltype(std::declval<const Eq&>()(std::declval<const ContainerKey&>(),
diff --git a/absl/container/internal/container_memory_test.cc b/absl/container/internal/container_memory_test.cc index 619a749..a305cd5 100644 --- a/absl/container/internal/container_memory_test.cc +++ b/absl/container/internal/container_memory_test.cc
@@ -30,6 +30,7 @@ #include "gtest/gtest.h" #include "absl/base/config.h" #include "absl/base/no_destructor.h" +#include "absl/container/internal/hash_function_defaults.h" #include "absl/container/internal/test_instance_tracker.h" #include "absl/functional/overload.h" #include "absl/hash/hash.h" @@ -253,6 +254,43 @@ std::make_tuple(0.5))); } +struct StringSetPolicy { + using key_type = std::string; + template <class F, class... Args> + static decltype(DecomposeValue(std::declval<F>(), std::declval<Args>()...)) + apply(F&& f, Args&&... args) { + return DecomposeValue(std::forward<F>(f), std::forward<Args>(args)...); + } +}; + +using TransparentStringHash = StringHash; +using TransparentStringEq = StringEq; + +TEST(IsDecomposable, RequireUsableKey) { + using NonTransparentHash = absl::Hash<std::string>; + using NonTransparentEq = std::equal_to<std::string>; + + EXPECT_TRUE((IsDecomposable<void, StringSetPolicy, NonTransparentHash, + NonTransparentEq, std::string>::value)); + EXPECT_TRUE((IsDecomposable<void, StringSetPolicy, NonTransparentHash, + NonTransparentEq, const std::string&>::value)); + // Non-transparent Hash/Eq reject heterogeneous or convertible keys. + EXPECT_FALSE((IsDecomposable<void, StringSetPolicy, NonTransparentHash, + NonTransparentEq, const char*>::value)); + EXPECT_FALSE((IsDecomposable<void, StringSetPolicy, NonTransparentHash, + TransparentStringEq, const char*>::value)); + EXPECT_FALSE((IsDecomposable<void, StringSetPolicy, TransparentStringHash, + NonTransparentEq, const char*>::value)); + + // Transparent Hash and Eq accept heterogeneous keys supported by both. + EXPECT_TRUE((IsDecomposable<void, StringSetPolicy, TransparentStringHash, + TransparentStringEq, const char*>::value)); + EXPECT_TRUE((IsDecomposable<void, StringSetPolicy, TransparentStringHash, + TransparentStringEq, absl::string_view>::value)); + EXPECT_FALSE((IsDecomposable<void, StringSetPolicy, TransparentStringHash, + TransparentStringEq, int>::value)); +} + TEST(MapSlotPolicy, ConstKeyAndValue) { using slot_policy = map_slot_policy<const CopyableMovableInstance, const CopyableMovableInstance>;
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h index 94bbfd1..b5af7dc 100644 --- a/absl/container/internal/raw_hash_set.h +++ b/absl/container/internal/raw_hash_set.h
@@ -3097,20 +3097,12 @@ template <class... Ts> using IsDecomposable = IsDecomposable<void, PolicyTraits, Hash, Eq, Ts...>; - template <class T, class ParamTypeToExclude> - using IsDecomposableAndInsertableImpl = std::bool_constant< - // Make sure that T isn't convertible to the preferred-qualified version - // of init_type itself, or otherwise we'll have ambiguous overloads. - !std::conjunction_v< - std::is_same<remove_cvref_t<T>, remove_cvref_t<ParamTypeToExclude>>, - std::is_convertible<T, ParamTypeToExclude>> && - IsDecomposable<std::enable_if_t<Insertable<T>::value, T>>::value>; - + // Enabler for templated `insert` overloads: `T` must be insertable and must + // not be `init_type` (which is handled by the dedicated `init_type` + // overloads to avoid overload ambiguity). template <class T> - using IsDecomposableAndInsertable = IsDecomposableAndInsertableImpl< - T, - PreferredMoveParamType<init_type, Alloc, - (std::conditional_t<false, T, std::nullptr_t>())>>; + using IsInsertableNotInit = std::conjunction< + std::negation<std::is_same<remove_cvref_t<T>, init_type>>, Insertable<T>>; // Evaluates to true if an assignment from the given type would require the // source object to remain alive for the life of the element. @@ -3503,22 +3495,26 @@ Clear<SooEnabled()>(common(), GetAllocPolicy(), get_destroy_slot_fn()); } - // This overload kicks in when the argument is an rvalue of insertable and - // decomposable type other than init_type. + // This overload kicks in when the argument is an rvalue of insertable type + // other than init_type. // // flat_hash_map<std::string, int> m; // m.insert(std::make_pair("abc", 42)); template <class T, - int = std::enable_if_t<IsDecomposableAndInsertable<T>::value && + int = std::enable_if_t<IsInsertableNotInit<T>::value && EnableElementMoveFrom<T>::value && !IsLifetimeBoundAssignmentFrom<T>::value, int>()> std::pair<iterator, bool> insert(T&& value) ABSL_ATTRIBUTE_LIFETIME_BOUND { - return emplace(std::forward<T>(value)); + if constexpr (IsDecomposable<T>::value) { + return emplace(std::forward<T>(value)); + } else { + return insert(static_cast<init_type>(std::forward<T>(value))); + } } template <class T, int&..., - std::enable_if_t<IsDecomposableAndInsertable<T>::value && + std::enable_if_t<IsInsertableNotInit<T>::value && EnableElementMoveFrom<T>::value && IsLifetimeBoundAssignmentFrom<T>::value, int> = 0> @@ -3529,7 +3525,7 @@ } // This overload kicks in when the argument is a bitfield or an lvalue of - // insertable and decomposable type. + // insertable type other than init_type. // // union { int n : 1; }; // flat_hash_set<int> s; @@ -3540,15 +3536,19 @@ // s.insert(p); // template <class T, int = std::enable_if_t< - IsDecomposableAndInsertable<const T&>::value && + IsInsertableNotInit<const T&>::value && !IsLifetimeBoundAssignmentFrom<const T&>::value, int>()> std::pair<iterator, bool> insert(const T& value) ABSL_ATTRIBUTE_LIFETIME_BOUND { - return emplace(value); + if constexpr (IsDecomposable<const T&>::value) { + return emplace(value); + } else { + return insert(static_cast<init_type>(value)); + } } template <class T, int&..., - std::enable_if_t<IsDecomposableAndInsertable<const T&>::value && + std::enable_if_t<IsInsertableNotInit<const T&>::value && IsLifetimeBoundAssignmentFrom<const T&>::value, int> = 0> std::pair<iterator, bool> insert( @@ -3584,8 +3584,20 @@ } #endif + // Handles `const init_type&` (and non-decomposable types convertible to it, + // notably keys derived from `key_type` on non-transparent sets) when + // `PreferredMoveParamType` is `init_type&&`. + template <std::nullptr_t Dummy = nullptr, + std::enable_if_t<std::is_rvalue_reference_v<PreferredMoveParamType< + init_type, Alloc, Dummy>>, + int> = 0> + std::pair<iterator, bool> insert(const init_type& value) + ABSL_ATTRIBUTE_LIFETIME_BOUND { + return emplace(value); + } + template <class T, - int = std::enable_if_t<IsDecomposableAndInsertable<T>::value && + int = std::enable_if_t<IsInsertableNotInit<T>::value && EnableElementMoveFrom<T>::value && !IsLifetimeBoundAssignmentFrom<T>::value, int>()> @@ -3593,7 +3605,7 @@ return insert(std::forward<T>(value)).first; } template <class T, int&..., - std::enable_if_t<IsDecomposableAndInsertable<T>::value && + std::enable_if_t<IsInsertableNotInit<T>::value && EnableElementMoveFrom<T>::value && IsLifetimeBoundAssignmentFrom<T>::value, int> = 0> @@ -3604,7 +3616,7 @@ } template <class T, std::enable_if_t< - IsDecomposableAndInsertable<const T&>::value, int> = 0> + IsInsertableNotInit<const T&>::value, int> = 0> iterator insert(const_iterator, const T& value) ABSL_ATTRIBUTE_LIFETIME_BOUND { return insert(value).first; @@ -3617,6 +3629,16 @@ return insert(std::move(value)).first; } + // Same as `insert(const init_type&)` above, with an iterator hint. + template <std::nullptr_t Dummy = nullptr, + std::enable_if_t<std::is_rvalue_reference_v<PreferredMoveParamType< + init_type, Alloc, Dummy>>, + int> = 0> + iterator insert(const_iterator, + const init_type& value) ABSL_ATTRIBUTE_LIFETIME_BOUND { + return insert(value).first; + } + template <class InputIt> void insert(InputIt first, InputIt last) { insert_range(first, last);
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc index e0a6cb1..14a5674 100644 --- a/absl/container/internal/raw_hash_set_test.cc +++ b/absl/container/internal/raw_hash_set_test.cc
@@ -2938,6 +2938,10 @@ return *this; } + friend bool operator==(const DecomposeType& a, const DecomposeType& b) { + return a.i == b.i; + } + template <typename H> friend H AbslHashValue(H h, const DecomposeType& d) { return H::combine(std::move(h), d.i); @@ -2992,15 +2996,11 @@ }; template <typename Hash, typename Eq> -void TestDecompose(bool construct_three) { +void TestDecompose(bool construct_three, bool construct_one = false) { DecomposeType elem{0}; const int one = 1; const char* three_p = "3"; const auto& three = three_p; - const int elem_vector_count = 256; - std::vector<DecomposeType> elem_vector(elem_vector_count, DecomposeType{0}); - std::iota(elem_vector.begin(), elem_vector.end(), 0); - using DecomposeSet = raw_hash_set<DecomposePolicy, Hash, Eq, std::allocator<int>>; DecomposeSet set1; @@ -3014,35 +3014,44 @@ EXPECT_EQ(++expected_constructed, decompose_constructed); set1.emplace("3"); EXPECT_EQ(++expected_constructed, decompose_constructed); - EXPECT_EQ(expected_constructed, decompose_constructed); - { // insert(T&&) + { // insert(T&&) / insert(const T&) / insert(hint, ...) set1.insert(1); + expected_constructed += construct_one; EXPECT_EQ(expected_constructed, decompose_constructed); - } - - { // insert(const T&) set1.insert(one); + expected_constructed += construct_one; EXPECT_EQ(expected_constructed, decompose_constructed); - } - - { // insert(hint, T&&) set1.insert(set1.begin(), 1); + expected_constructed += construct_one; + EXPECT_EQ(expected_constructed, decompose_constructed); + set1.insert(set1.begin(), one); + expected_constructed += construct_one; EXPECT_EQ(expected_constructed, decompose_constructed); } - { // insert(hint, const T&) - set1.insert(set1.begin(), one); + { // insert(const init_type&) via derived type and reference_wrapper + struct DerivedDecomposeType : DecomposeType { + using DecomposeType::DecomposeType; + }; + const DerivedDecomposeType derived(0); + ++expected_constructed; + EXPECT_FALSE(set1.insert(derived).second); + EXPECT_EQ(set1.insert(set1.begin(), derived)->i, 0); + EXPECT_FALSE(set1.insert(std::cref(elem)).second); + EXPECT_NE(set1.find(derived), set1.end()); EXPECT_EQ(expected_constructed, decompose_constructed); } { // emplace(...) set1.emplace(1); + expected_constructed += construct_one; EXPECT_EQ(expected_constructed, decompose_constructed); set1.emplace("3"); expected_constructed += construct_three; EXPECT_EQ(expected_constructed, decompose_constructed); set1.emplace(one); + expected_constructed += construct_one; EXPECT_EQ(expected_constructed, decompose_constructed); set1.emplace(three); expected_constructed += construct_three; @@ -3051,17 +3060,25 @@ { // emplace_hint(...) set1.emplace_hint(set1.begin(), 1); + expected_constructed += construct_one; EXPECT_EQ(expected_constructed, decompose_constructed); set1.emplace_hint(set1.begin(), "3"); expected_constructed += construct_three; EXPECT_EQ(expected_constructed, decompose_constructed); set1.emplace_hint(set1.begin(), one); + expected_constructed += construct_one; EXPECT_EQ(expected_constructed, decompose_constructed); set1.emplace_hint(set1.begin(), three); expected_constructed += construct_three; EXPECT_EQ(expected_constructed, decompose_constructed); } + // Generations cause extra rehashes that change internal move counts. + if (SwisstableGenerationsEnabled()) return; + + const int elem_vector_count = 256; + std::vector<DecomposeType> elem_vector(elem_vector_count, DecomposeType{0}); + std::iota(elem_vector.begin(), elem_vector.end(), 0); decompose_copy_constructed = 0; decompose_copy_assigned = 0; decompose_move_constructed = 0; @@ -3110,33 +3127,92 @@ EXPECT_GE(expected_move_constructed, decompose_move_constructed); EXPECT_EQ(0, decompose_move_assigned); EXPECT_EQ(0, decompose_copy_assigned); - expected_copy_constructed = decompose_copy_constructed; - expected_move_constructed = decompose_move_constructed; } } -TEST(Table, Decompose) { - if (SwisstableGenerationsEnabled()) { - GTEST_SKIP() << "Generations being enabled causes extra rehashes."; +TEST(Table, DerivedKeyType) { + struct DerivedDecomposeType : DecomposeType { + using DecomposeType::DecomposeType; + }; + const DerivedDecomposeType d(2); + absl::flat_hash_map<DecomposeType, int> map; + std::pair<DerivedDecomposeType, int> p(DerivedDecomposeType(10), 100); + EXPECT_TRUE(map.insert(p).second); + EXPECT_TRUE(map.insert({d, 200}).second); + EXPECT_FALSE(map.try_emplace(d, 300).second); + EXPECT_EQ(map.find(d)->second, 200); + EXPECT_EQ(map[d], 200); + + struct TrivialBase { + int v; + }; + struct TrivialDerived : TrivialBase {}; + struct TrivialHash { + size_t operator()(TrivialBase k) const { return static_cast<size_t>(k.v); } + }; + struct TrivialEq { + bool operator()(TrivialBase a, TrivialBase b) const { return a.v == b.v; } + }; + absl::flat_hash_set<TrivialBase, TrivialHash, TrivialEq> set; + const TrivialDerived td{{7}}; + EXPECT_TRUE(set.insert(td).second); + EXPECT_EQ(set.insert(set.begin(), td)->v, 7); +} + +struct TemplatedConversionProxy { + int v; + template <typename T> + operator T() const { // NOLINT(google-explicit-constructor) + static_assert(std::is_same_v<T, int>); + return T(v); } +}; +TEST(Table, InsertTemplatedConversionOperator) { + absl::flat_hash_set<int> set; + const TemplatedConversionProxy p{42}; + EXPECT_TRUE(set.insert(p).second); + EXPECT_EQ(*set.insert(set.begin(), TemplatedConversionProxy{42}), 42); + EXPECT_THAT(set, ElementsAre(42)); +} + +struct TransparentHashIntOverload { + using is_transparent = void; + size_t operator()(const DecomposeType& a) const { + return static_cast<size_t>(a.i); + } + size_t operator()(int a) const { return static_cast<size_t>(a); } +}; + +struct TransparentEqIntOverload { + using is_transparent = void; + bool operator()(const DecomposeType& a, const DecomposeType& b) const { + return a.i == b.i; + } + bool operator()(const DecomposeType& a, int b) const { return a.i == b; } +}; + +TEST(Table, Decompose) { TestDecompose<DecomposeHash, DecomposeEq>(false); - - struct TransparentHashIntOverload { - size_t operator()(const DecomposeType& a) const { return a.i; } - size_t operator()(int a) const { return a; } - }; - struct TransparentEqIntOverload { - bool operator()(const DecomposeType& a, const DecomposeType& b) const { - return a.i == b.i; - } - bool operator()(const DecomposeType& a, int b) const { return a.i == b; } - }; TestDecompose<TransparentHashIntOverload, DecomposeEq>(true); TestDecompose<TransparentHashIntOverload, TransparentEqIntOverload>(true); TestDecompose<DecomposeHash, TransparentEqIntOverload>(true); TestDecompose<absl::TransparentHash<DecomposeType, int>, TransparentEqIntOverload>(true); + + struct NonTransparentHash { + size_t operator()(const DecomposeType& a) const { + return static_cast<size_t>(a.i) % 2; + } + }; + struct NonTransparentEq { + bool operator()(const DecomposeType& a, const DecomposeType& b) const { + return a.i == b.i; + } + }; + TestDecompose<NonTransparentHash, DecomposeEq>(true, true); + TestDecompose<NonTransparentHash, NonTransparentEq>(true, true); + TestDecompose<DecomposeHash, NonTransparentEq>(true, true); } struct Modulo1000Hash {