[Bug libstdc++/115285] [12/13/14/15 Regression] std::unordered_set can have duplicate value
Jonathan Wakely
jwakely@redhat.com
Tue Nov 5 18:47:52 GMT 2024
On 05/11/24 17:50 +0000, Jonathan Wakely wrote:
>On 28/10/24 21:51 +0100, François Dumont wrote:
>>
>>>On 24/10/2024 21:49, Jonathan Wakely wrote:
>>>>On Thu, 24 Oct 2024 at 19:43, François Dumont<frs.dumont@gmail.com> wrote:
>>>>>Committed as trivial the attached patch.
>>>>>
>>>>> libstdc++: Fix test broken when using COW std::string
>>>>>
>>>>> libstdc++-v3/ChangeLog:
>>>>>
>>>>> * testsuite/23_containers/unordered_map/96088.cc (test03):
>>>>Thanks! I think it was affecting the unordered_set test too.
>>>>
>>Hi
>>
>>This was indeed revealing a problem in my attempt to fix this bug.
>>
>>Here is the complete patch that I will backport if validated.
>>
>>libstdc++: [_Hashtable] Avoid temporaries when inserting existing key
>>
>>Following PR 115285 fix, the hashtable _S_forward_key responsible
>>for finding
>>the best way to transmit the key part of the argument parameter to the hash
>>functor was modified to return a key_type instance for any argument
>>type. Only
>>the overloads for const key_type& and key_type&& were still
>>preventing a key_type
>>instanciation.
>>
>>It revealed that a overload for key_type& was missing. To fix this
>>problem we now
>>deal with all sort of key_type of reference type in the unique
>>_S_forward_key static
>>method and remove the overloads. When decayed type of the input
>>instance is the same
>>as key_type we avoid the instanciation. Note that for the comparison
>>we also decay
>>key_type to properly managed when unordered container is
>>instantiated with a const
>>type.
>>
>>libstdc++-v3/ChangeLog:
>>
>> * include/bits/hashtable_policy.h
>> (_ConvertToValueType<_Select1st,
>>_Value>::operator(std::pair<>&)): New,
>> allow consistent behavior with
>>_ConvertToValueType<_Identity, _Value>.
>> * include/bits/hashtable.h
>> (_S_forward_key<_Kt>(_Kt&&)): Adapt to return _Kt&& when
>>decayed _Kt is
>> key_type, return a new key_type instance otherwise.
>> (_S_forward_key(const key_type&)): Remove.
>> (_S_forward_key(key_type&&)): Remove.
>> * testsuite/23_containers/unordered_set/96088.cc (test03):
>>Adapt expected
>> allocation increment.
>>
>>Tested under linux x64, both std::string abi.
>>
>>Ok to commit ?
>
>No, because it's still not a complete fix, just more special cases.
>
>I think the attached patch (actually two patches, as there's one to
>add __is_pair first) fixes PR 115285, including all the other cases I
>added in comment 14. It also avoids regressing PR 96088.
>
>This seems small and safe enough to backport. On trunk I still plan to
>follow this with the bigger refactoring.
>
>Tests are still running ...
>
>
>commit 590091e997248dd475d7329f4613765d7cff8bb6
>Author: Jonathan Wakely <jwakely@redhat.com>
>Date: Fri Nov 1 10:09:55 2024
>
> libstdc++: Define __is_pair variable template for C++11
>
> libstdc++-v3/ChangeLog:
>
> * include/bits/stl_pair.h (__is_pair): Define for C++11 and
> C++14 as well.
>
>diff --git a/libstdc++-v3/include/bits/stl_pair.h b/libstdc++-v3/include/bits/stl_pair.h
>index e92fcad2d66..527fb9105f0 100644
>--- a/libstdc++-v3/include/bits/stl_pair.h
>+++ b/libstdc++-v3/include/bits/stl_pair.h
>@@ -1189,12 +1189,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>
> template<typename _Tp1, typename _Tp2>
> inline constexpr size_t tuple_size_v<const pair<_Tp1, _Tp2>> = 2;
>+#endif
>
>+#if __cplusplus >= 201103L
>+#pragma GCC diagnostic push
>+#pragma GCC diagnostic ignored "-Wc++14-extensions" // variable templates
>+#pragma GCC diagnostic ignored "-Wc++17-extensions" // inline variables
> template<typename _Tp>
> inline constexpr bool __is_pair = false;
>
> template<typename _Tp, typename _Up>
> inline constexpr bool __is_pair<pair<_Tp, _Up>> = true;
>+#pragma GCC diagnostic pop
> #endif
>
> /// @cond undocumented
>
>commit 23328cc25365593d045096ccf913cb273202edb0
>Author: Jonathan Wakely <jwakely@redhat.com>
>Date: Tue Nov 5 17:19:06 2024
>
> libstdc++: Fix conversions to key/value type for insertions into hash tables [PR115285]
>
> The conversions to key_type and value_type that are performed when
> inserting into _Hashtable need to be fixed to do any required
> conversions explicitly. The current code assumes that conversions from
> the parameter to the key_type or value_type can be done implicitly,
> which isn't necessarily true.
>
> Remove the _S_forward_key function which doesn't handle all cases and
> either forward the parameter if it already has type cv key_type, or
> explicitly construct a temporary of type key_type.
>
> Similarly, for the _ConvertToValueType specialization for maps, either
> forward a std::pair parameter unchanged, or explicitly construct a
> temporary of type value_type.
>
> libstdc++-v3/ChangeLog:
>
> PR libstdc++/115285
> * include/bits/hashtable.h (_Hashtable::_S_forward_key): Remove.
> (_Hashtable::_M_insert_unique_aux):
> * include/bits/hashtable_policy.h (_ConvertToValueType): Add
> comment.
> (_ConvertToValueType<_Select1st, _Value>): Replace incomplete
> overload set with two overloads, one for std::pair
> specializations and one for everything else.
> * testsuite/23_containers/unordered_map/insert/115285.cc: New test.
> * testsuite/23_containers/unordered_set/insert/115285.cc: New test.
> * testsuite/23_containers/unordered_set/96088.cc: Adjust
> expected number of allocations.
>
>diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
>index 47321a9cb13..0759a9699e5 100644
>--- a/libstdc++-v3/include/bits/hashtable.h
>+++ b/libstdc++-v3/include/bits/hashtable.h
>@@ -929,25 +929,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> std::pair<iterator, bool>
> _M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&);
>
>- template<typename _Kt>
>- key_type
>- _S_forward_key(_Kt&& __k)
>- { return std::forward<_Kt>(__k); }
>-
>- static const key_type&
>- _S_forward_key(const key_type& __k)
>- { return __k; }
>-
>- static key_type&&
>- _S_forward_key(key_type&& __k)
>- { return std::move(__k); }
>-
> template<typename _Arg, typename _NodeGenerator>
> std::pair<iterator, bool>
> _M_insert_unique_aux(_Arg&& __arg, _NodeGenerator& __node_gen)
> {
>+ using _Kt = decltype(_ExtractKey{}(std::forward<_Arg>(__arg)));
>+ constexpr bool __is_key_type
>+ = is_same<__remove_cvref_t<_Kt>, key_type>::value;
>+ using _Fwd_key = __conditional_t<__is_key_type, _Kt&&, key_type>;
> return _M_insert_unique(
>- _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
>+ static_cast<_Fwd_key>(_ExtractKey{}(std::forward<_Arg>(__arg))),
> std::forward<_Arg>(__arg), __node_gen);
> }
Actually we can simplify this further.
There's no need to use _ConvertToValueType for the non-unique keys
case. We don't need to extract a key and search for duplicates, we are
just going to insert it anyway. So just forward the _Arg without
conversion.
That means we only use _ConvertToValueType in one place, the overload
of _M_insert for unique keys. And we can replace it with a typedef and
a static_cast there. That means we don't need to instantiate the
_ConvertToValueType class template at all, and can remove it.
Here's an incremental patch to be applied on top of the previous one:
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 0759a9699e5..45829fa2a14 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -947,10 +947,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
true_type /* __uks */)
{
- using __to_value
- = __detail::_ConvertToValueType<_ExtractKey, value_type>;
+ using __detail::_Identity;
+ using _Vt = __conditional_t<is_same<_ExtractKey, _Identity>::value
+ || __is_pair<__remove_cvref_t<_Arg>>,
+ _Arg&&, value_type>;
return _M_insert_unique_aux(
- __to_value{}(std::forward<_Arg>(__arg)), __node_gen);
+ static_cast<_Vt>(std::forward<_Arg>(__arg)), __node_gen);
}
template<typename _Arg, typename _NodeGenerator>
@@ -958,10 +960,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
false_type __uks)
{
- using __to_value
- = __detail::_ConvertToValueType<_ExtractKey, value_type>;
- return _M_insert(cend(),
- __to_value{}(std::forward<_Arg>(__arg)), __node_gen, __uks);
+ return _M_insert(cend(), std::forward<_Arg>(__arg),
+ __node_gen, __uks);
}
// Insert with hint, not used when keys are unique.
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 36cd3219af4..b8d1f5de36d 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -113,37 +113,6 @@ namespace __detail
{ return std::forward<_Tp>(__x).first; }
};
- // This is misnamed, it doesn't actually convert to the value_type,
- // but for maps it converts non-pairs to the value_type.
- template<typename _ExKey, typename _Value>
- struct _ConvertToValueType;
-
- template<typename _Value>
- struct _ConvertToValueType<_Identity, _Value>
- {
- template<typename _Kt>
- constexpr _Kt&&
- operator()(_Kt&& __k) const noexcept
- { return std::forward<_Kt>(__k); }
- };
-
- template<typename _Value>
- struct _ConvertToValueType<_Select1st, _Value>
- {
- // If the argument is already a std::pair, just forward it unchanged
- // (even if not the same std::pair specialization as _Value).
- template<typename _Tp>
- constexpr __enable_if_t<__is_pair<__remove_cvref_t<_Tp>>, _Tp&&>
- operator()(_Tp&& __x) const noexcept
- { return std::forward<_Tp>(__x); }
-
- // Otherwise, create a temporary of the container's value_type.
- template<typename _Tp>
- constexpr __enable_if_t<!__is_pair<__remove_cvref_t<_Tp>>, _Value>
- operator()(_Tp&& __x) const noexcept
- { return _Value(std::forward<_Tp>(__x)); }
- };
-
template<typename _ExKey>
struct _NodeBuilder;
More information about the Libstdc++
mailing list