[Bug libstdc++/115285] [12/13/14/15 Regression] std::unordered_set can have duplicate value

[Jonathan Wakely]

On 31/10/24 19:11 +0000, Jonathan Wakely wrote:
>On 31/10/24 10:38 +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 ?
>>>
>>>François
>>
>>>diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
>>>index f1a5490b5ff..8324e75aefd 100644
>>>--- a/libstdc++-v3/include/bits/hashtable.h
>>>+++ b/libstdc++-v3/include/bits/hashtable.h
>>>@@ -930,18 +930,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>>>	_M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&);
>>>
>>>     template<typename _Kt>
>>>-	key_type
>>>+	static __conditional_t<std::is_same<__decay_t<_Kt>,
>>>+					    __decay_t<key_type>>::value,
>>>+			       _Kt&&, key_type>
>>>	_S_forward_key(_Kt&& __k)
>>>	{ return std::forward<_Kt>(__k); }
>>
>>Does this assume that __k is implicitly convertible to key_type?
>>
>>e.g. if Kt is int and the key_type(int) constructor is explicit?
>
>Yes, this fails, and I think it should compile:
>
>#include <unordered_set>
>
>struct K {
>  explicit K(int) noexcept { }
>  bool operator==(const K&) const { return true; }
>};
>
>template<> struct std::hash<K> {
>  auto operator()(const K&) const { return 0ul; }
>};
>
>int main()
>{
>  int i[1]{};
>  std::unordered_set<K> s(i, i);
>}
>
>
>>Does it need to be something like:
>>
>>template<typename _Kt>
>> static __conditional_t<is_same<const _Kt&, const key_type&>::value,
>>                        _Kt&&, key_type>
>> _S_forward_key(_Kt&& __k)
>> {
>>   using type = __conditional_t<is_same<const _Kt&, const key_type&>::value,
>>                                _Kt&&, key_type>
>>   return static_cast<type>(__k);
>> }
>>
>>?

Can we just remove _S_forward_key and use static_cast directly?


--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -929,26 +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
+	    = __conditional_t<is_same<const _Arg&, const key_type&>::value,
+			      _Arg&&, key_type>;
  	  return _M_insert_unique(
-	    _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
-	    std::forward<_Arg>(__arg), __node_gen);
+		   static_cast<_Kt>(_ExtractKey{}(std::forward<_Arg>(__arg))),
+		   std::forward<_Arg>(__arg), __node_gen);
  	}
  
        template<typename _Arg, typename _NodeGenerator>