Re: [PATCH][_Hashtable] Fix insertion of range of type convertible to value_type PR 105714

["François Dumont" <frs.dumont@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 4391 bytes --]

Here is the patch to fix just what is described in PR 105714.

     libstdc++: [_Hashtable] Insert range of types convertible to 
value_type PR 105714

     Fix insertion of range of types convertible to value_type.

     libstdc++-v3/ChangeLog:

             PR libstdc++/105714
             * include/bits/hashtable_policy.h (_ValueTypeEnforcer): New.
             * include/bits/hashtable.h 
(_Hashtable<>::_M_insert_unique_aux): New.
             (_Hashtable<>::_M_insert(_Arg&&, const _NodeGenerator&, 
true_type)): Use latters.
             (_Hashtable<>::_M_insert(_Arg&&, const _NodeGenerator&, 
false_type)): Likewise.
             (_Hashtable(_InputIterator, _InputIterator, size_type, 
const _Hash&, const _Equal&,
             const allocator_type&, true_type)): Use this.insert range.
             (_Hashtable(_InputIterator, _InputIterator, size_type, 
const _Hash&, const _Equal&,
             const allocator_type&, false_type)): Use _M_insert.
             * testsuite/23_containers/unordered_map/cons/56112.cc: 
Check how many times conversion
             is done.
             * testsuite/23_containers/unordered_map/insert/105714.cc: 
New test.
             * testsuite/23_containers/unordered_set/insert/105714.cc: 
New test.

Tested under Linux x64, ok to commit ?

François

On 24/05/22 12:31, Jonathan Wakely wrote:
> On Tue, 24 May 2022 at 11:22, Jonathan Wakely wrote:
>> On Tue, 24 May 2022 at 11:18, Jonathan Wakely wrote:
>>> On Thu, 5 May 2022 at 18:38, François Dumont via Libstdc++
>>> <libstdc++@gcc.gnu.org> wrote:
>>>> Hi
>>>>
>>>> Renewing my patch to fix PR 56112 but for the insert methods, I totally
>>>> change it, now works also with move-only key types.
>>>>
>>>> I let you Jonathan find a better name than _ValueTypeEnforcer as usual :-)
>>>>
>>>> libstdc++: [_Hashtable] Insert range of types convertible to value_type
>>>> PR 56112
>>>>
>>>> Fix insertion of range of types convertible to value_type. Fix also when
>>>> this value_type
>>>> has a move-only key_type which also allow converted values to be moved.
>>>>
>>>> libstdc++-v3/ChangeLog:
>>>>
>>>>           PR libstdc++/56112
>>>>           * include/bits/hashtable_policy.h (_ValueTypeEnforcer): New.
>>>>           * include/bits/hashtable.h
>>>> (_Hashtable<>::_M_insert_unique_aux): New.
>>>>           (_Hashtable<>::_M_insert(_Arg&&, const _NodeGenerator&,
>>>> true_type)): Use latters.
>>>>           (_Hashtable<>::_M_insert(_Arg&&, const _NodeGenerator&,
>>>> false_type)): Likewise.
>>>>           (_Hashtable(_InputIterator, _InputIterator, size_type, const
>>>> _Hash&, const _Equal&,
>>>>           const allocator_type&, true_type)): Use this.insert range.
>>>>           (_Hashtable(_InputIterator, _InputIterator, size_type, const
>>>> _Hash&, const _Equal&,
>>>>           const allocator_type&, false_type)): Use _M_insert.
>>>>           * testsuite/23_containers/unordered_map/cons/56112.cc: Check
>>>> how many times conversion
>>>>           is done.
>>>>           (test02): New test case.
>>>>           * testsuite/23_containers/unordered_set/cons/56112.cc: New test.
>>>>
>>>> Tested under Linux x86_64.
>>>>
>>>> Ok to commit ?
>>> No, sorry.
>>>
>>> The new test02 function in 23_containers/unordered_map/cons/56112.cc
>>> doesn't compile with libc++ or MSVC either, are you sure that test is
>>> valid? I don't think it is, because S2 is not convertible to
>>> pair<const MoveOnlyKey, int>. None of the pair constructors are
>>> viable, because the move constructor would require two user-defined
>>> conversions (from S2 to pair<MoveOnlyKey, int> and then from
>>> pair<MoveOnlyKey, int> to pair<const MoveOnlyKey, int>). A conversion
>>> sequence cannot have more than one user-defined conversion using a
>>> constructor or converion operator. So if your patch makes that
>>> compile, it's a bug in the new code. I haven't analyzed that code to
>>> see where the problem is, I'm just looking at the test results and the
>>> changes in behaviour.
>> I meant to include this link showing that libc++ and MSVC reject
>> test02() as well:
>>
>> https://godbolt.org/z/j7E9f6bd4
> I've created https://gcc.gnu.org/bugzilla/show_bug.cgi?id=105717 for
> the insertion bug, rather than reopening PR 56112.
>

[-- Attachment #2: pr105714.patch --]
[-- Type: text/x-patch, Size: 9372 bytes --]

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 5e1a417f7cd..cd42d3c9ba0 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -898,21 +898,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
       template<typename _Arg, typename _NodeGenerator>
 	std::pair<iterator, bool>
-	_M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
-		  true_type /* __uks */)
+	_M_insert_unique_aux(_Arg&& __arg, const _NodeGenerator& __node_gen)
 	{
 	  return _M_insert_unique(
 	    _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
 	    std::forward<_Arg>(__arg), __node_gen);
 	}
 
+      template<typename _Arg, typename _NodeGenerator>
+	std::pair<iterator, bool>
+	_M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
+		  true_type /* __uks */)
+	{
+	  using __to_value
+	    = __detail::_ValueTypeEnforcer<_ExtractKey, value_type>;
+	  return _M_insert_unique_aux(
+	    __to_value{}(std::forward<_Arg>(__arg)), __node_gen);
+	}
+
       template<typename _Arg, typename _NodeGenerator>
 	iterator
 	_M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
 		  false_type __uks)
 	{
-	  return _M_insert(cend(), std::forward<_Arg>(__arg), __node_gen,
-			   __uks);
+	  using __to_value
+	    = __detail::_ValueTypeEnforcer<_ExtractKey, value_type>;
+	  return _M_insert(cend(),
+	    __to_value{}(std::forward<_Arg>(__arg)), __node_gen, __uks);
 	}
 
       // Insert with hint, not used when keys are unique.
@@ -1184,10 +1196,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 		 const _Hash& __h, const _Equal& __eq,
 		 const allocator_type& __a, true_type /* __uks */)
       : _Hashtable(__bkt_count_hint, __h, __eq, __a)
-      {
-	for (; __f != __l; ++__f)
-	  this->insert(*__f);
-      }
+      { this->insert(__f, __l); }
 
   template<typename _Key, typename _Value, typename _Alloc,
 	   typename _ExtractKey, typename _Equal,
@@ -1199,7 +1208,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       _Hashtable(_InputIterator __f, _InputIterator __l,
 		 size_type __bkt_count_hint,
 		 const _Hash& __h, const _Equal& __eq,
-		 const allocator_type& __a, false_type /* __uks */)
+		 const allocator_type& __a, false_type __uks)
       : _Hashtable(__h, __eq, __a)
       {
 	auto __nb_elems = __detail::__distance_fw(__f, __l);
@@ -1214,8 +1223,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	    _M_bucket_count = __bkt_count;
 	  }
 
+	__alloc_node_gen_t __node_gen(*this);
 	for (; __f != __l; ++__f)
-	  this->insert(*__f);
+	  _M_insert(*__f, __node_gen, __uks);
       }
 
   template<typename _Key, typename _Value, typename _Alloc,
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 0f0b0f9ea51..a6ba6a1d1ac 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -109,6 +109,40 @@ namespace __detail
       { return std::forward<_Tp>(__x).first; }
   };
 
+  template<typename _ExKey, typename _Value>
+    struct _ValueTypeEnforcer;
+
+  template<typename _Value>
+    struct _ValueTypeEnforcer<_Identity, _Value>
+    {
+      template<typename _Kt>
+	constexpr _Kt&&
+	operator()(_Kt&& __k) noexcept
+	{ return std::forward<_Kt>(__k); }
+    };
+
+  template<typename _Value>
+    struct _ValueTypeEnforcer<_Select1st, _Value>
+    {
+      constexpr _Value&&
+      operator()(_Value&& __x) noexcept
+      { return std::move(__x); }
+
+      constexpr const _Value&
+      operator()(const _Value& __x) noexcept
+      { return __x; }
+
+      template<typename _Kt, typename _Val>
+	constexpr std::pair<_Kt, _Val>&&
+	operator()(std::pair<_Kt, _Val>&& __x) noexcept
+	{ return std::move(__x); }
+
+      template<typename _Kt, typename _Val>
+	constexpr const std::pair<_Kt, _Val>&
+	operator()(const std::pair<_Kt, _Val>& __x) noexcept
+	{ return __x; }
+    };
+
   template<typename _ExKey>
     struct _NodeBuilder;
 
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/cons/56112.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/cons/56112.cc
index c4cdeee234c..b0eda30b4cb 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_map/cons/56112.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/cons/56112.cc
@@ -20,30 +20,51 @@
 #include <unordered_map>
 #include <utility>
 
+#include <testsuite_hooks.h>
+
 struct Key
 {
   explicit Key(const int* p) : value(p) { }
   ~Key() { value = nullptr; }
 
-  bool operator==(const Key& k) const { return *value == *k.value; }
+  bool operator==(const Key& k) const
+  { return *value == *k.value; }
 
   const int* value;
 };
 
 struct hash
 {
-  std::size_t operator()(const Key& k) const noexcept { return *k.value; }
+  std::size_t operator()(const Key& k) const noexcept
+  { return *k.value; }
 };
 
 struct S
 {
+  static int _count;
+
   int value;
-  operator std::pair<const Key, int>() const { return {Key(&value), value}; }
+  operator std::pair<const Key, int>() const
+  {
+    ++_count;
+    return { Key(&value), value };
+  }
 };
 
-int main()
+int S::_count = 0;
+
+void test01()
 {
     S s[1] = { {2} };
-    std::unordered_map<Key, int, hash> m(s, s+1);
-    std::unordered_multimap<Key, int, hash> mm(s, s+1);
+    std::unordered_map<Key, int, hash> m(s, s + 1);
+    VERIFY( S::_count == 1 );
+
+    std::unordered_multimap<Key, int, hash> mm(s, s + 1);
+    VERIFY( S::_count == 2 );
+}
+
+int main()
+{
+  test01();
+  return 0;
 }
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_map/insert/105717.cc b/libstdc++-v3/testsuite/23_containers/unordered_map/insert/105717.cc
new file mode 100644
index 00000000000..202baa9818b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/insert/105717.cc
@@ -0,0 +1,73 @@
+// { dg-do run { target c++11 } }
+
+// Copyright (C) 2022 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <unordered_map>
+#include <utility>
+
+#include <testsuite_hooks.h>
+
+struct Key
+{
+  explicit Key(const int* p) : value(p) { }
+  ~Key() { value = nullptr; }
+
+  bool operator==(const Key& k) const
+  { return *value == *k.value; }
+
+  const int* value;
+};
+
+struct hash
+{
+  std::size_t operator()(const Key& k) const noexcept
+  { return *k.value; }
+};
+
+struct S
+{
+  static int _count;
+
+  int value;
+  operator std::pair<const Key, int>() const
+  {
+    ++_count;
+    return { Key(&value), value };
+  }
+};
+
+int S::_count = 0;
+
+void test01()
+{
+    S s[1] = { {2} };
+    std::unordered_map<Key, int, hash> m;
+    std::unordered_multimap<Key, int, hash> mm;
+
+    m.insert(s, s + 1);
+    VERIFY( S::_count == 1 );
+
+    mm.insert(s, s + 1);
+    VERIFY( S::_count == 2 );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/insert/105717.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/105717.cc
new file mode 100644
index 00000000000..ab229c5baa1
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/insert/105717.cc
@@ -0,0 +1,73 @@
+// { dg-do run { target c++11 } }
+
+// Copyright (C) 2022 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the
+// terms of the GNU General Public License as published by the
+// Free Software Foundation; either version 3, or (at your option)
+// any later version.
+
+// This library is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+// GNU General Public License for more details.
+
+// You should have received a copy of the GNU General Public License along
+// with this library; see the file COPYING3.  If not see
+// <http://www.gnu.org/licenses/>.
+
+#include <unordered_set>
+#include <utility>
+
+#include <testsuite_hooks.h>
+
+struct Key
+{
+  explicit Key(const int* p) : value(p) { }
+  ~Key() { value = nullptr; }
+
+  bool operator==(const Key& k) const
+  { return *value == *k.value; }
+
+  const int* value;
+};
+
+struct hash
+{
+  std::size_t operator()(const Key& k) const noexcept
+  { return *k.value; }
+};
+
+struct S
+{
+  static int _count;
+
+  int value;
+  operator Key() const
+  {
+    ++_count;
+    return Key(&value);
+  }
+};
+
+int S::_count = 0;
+
+void test01()
+{
+    S a[1] = { {2} };
+    std::unordered_set<Key, hash> s;
+    std::unordered_multiset<Key, hash> ms;
+
+    s.insert(a, a + 1);
+    VERIFY( S::_count == 1 );
+
+    ms.insert(a, a + 1);
+    VERIFY( S::_count == 2 );
+}
+
+int main()
+{
+  test01();
+  return 0;
+}