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

[Jonathan Wakely]

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?
>
>Does it need to be something like:
>
>template<typename _Kt>
>  static __conditional_t<is_same<const _Kt&, const key_type&>::value,
>                         _Kt&&, key_type>

P.S. this could still use __decay_t here, but it's less expensive to
just check if const Kt& and const key_type& are the same, which is
true if remove_cvref_t<Kt> and remove_cvref_t<key_type> are the same,
as long as we assume neither type can be volatile (which is allowed,
because the standard library generally doesn't support
volatile-qualified types).

>  _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);
>  }
>
>?
>
>>
>>-      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)
>>diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
>>index 5d79e2ba26f..f35eb7ddb43 100644
>>--- a/libstdc++-v3/include/bits/hashtable_policy.h
>>+++ b/libstdc++-v3/include/bits/hashtable_policy.h
>>@@ -141,6 +141,11 @@ namespace __detail
>>	operator()(std::pair<_Kt, _Val>&& __x) const noexcept
>>	{ return std::move(__x); }
>>
>>+      template<typename _Kt, typename _Val>
>>+	constexpr std::pair<_Kt, _Val>&
>>+	operator()(std::pair<_Kt, _Val>& __x) const noexcept
>>+	{ return __x; }
>>+
>>      template<typename _Kt, typename _Val>
>>	constexpr const std::pair<_Kt, _Val>&
>>	operator()(const std::pair<_Kt, _Val>& __x) const noexcept
>>diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc
>>index bc2f093f47c..59e1ad12401 100644
>>--- a/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc
>>+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/96088.cc
>>@@ -244,7 +244,7 @@ test03()
>>    VERIFY( us.size() == 1 );
>>
>>    VERIFY( __gnu_test::counter::count() == origin + increments );
>>-    VERIFY( __gnu_test::counter::get()._M_increments == increments + 1 );
>>+    VERIFY( __gnu_test::counter::get()._M_increments == increments );
>>  }
>>  VERIFY( __gnu_test::counter::count() == origin );
>>
>