[PATCH][_Hashtable] Fix insertion of range of type convertible to value_type PR 56112

[PATCH][_Hashtable] Fix insertion of range of type convertible to value_type PR 56112

[François Dumont]

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

We have a regression regarding management of types convertible to 
value_type. It is an occurrence of PR 56112 but for the insert method.

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

     Fix insertion of range of types convertible to value_type.

     libstdc++-v3/ChangeLog:

             PR libstdc++/56112
             * include/bits/hashtable.h
             (_Hashtable<>::_M_insert_unique_aux): New.
             (_Hashtable<>::_S_to_value): New.
             (_Hashtable<>::_M_insert(_Arg&&, const _NodeGenerator&, 
true_type)): Use latters.
             * testsuite/23_containers/unordered_map/cons/56112.cc: Use 
dg-do compile.
             * testsuite/23_containers/unordered_set/cons/56112.cc: New 
test.

Tested under Linux x86_64.

Ok to commit ?

François

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

diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 5e1a417f7cd..5a502c02fe0 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -898,14 +898,51 @@ _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 _Kt>
+	static typename std::enable_if<std::is_same<_ExtractKey,
+						    __detail::_Identity>::value,
+				       _Kt&&>::type
+	_S_to_value(_Kt&& __x) noexcept
+	{ return std::forward<_Kt>(__x); }
+
+      template<typename _Kt, typename _Val>
+	static typename std::enable_if<std::is_same<_ExtractKey,
+						   __detail::_Select1st>::value,
+				       const std::pair<_Kt, _Val>&>::type
+	_S_to_value(const std::pair<_Kt, _Val>& __x) noexcept
+	{ return __x; }
+
+      template<typename _Kt, typename _Val>
+	static typename std::enable_if<std::is_same<_ExtractKey,
+						   __detail::_Select1st>::value,
+				       std::pair<_Kt, _Val>&&>::type
+	_S_to_value(std::pair<_Kt, _Val>&& __x) noexcept
+	{ return std::move(__x); }
+
+      static value_type&&
+      _S_to_value(value_type&& __x) noexcept
+      { return std::move(__x); }
+
+      static const value_type&
+      _S_to_value(const value_type& __x) noexcept
+      { return __x; }
+
+      template<typename _Arg, typename _NodeGenerator>
+	std::pair<iterator, bool>
+	_M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
+		  true_type /* __uks */)
+	{
+	  return _M_insert_unique_aux(
+	    _S_to_value(std::forward<_Arg>(__arg)), __node_gen);
+	}
+
       template<typename _Arg, typename _NodeGenerator>
 	iterator
 	_M_insert(_Arg&& __arg, const _NodeGenerator& __node_gen,
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..8ec0d89af69 100644
--- a/libstdc++-v3/testsuite/23_containers/unordered_map/cons/56112.cc
+++ b/libstdc++-v3/testsuite/23_containers/unordered_map/cons/56112.cc
@@ -1,4 +1,4 @@
-// { dg-do run { target c++11 } }
+// { dg-do compile { target c++11 } }
 
 // Copyright (C) 2013-2022 Free Software Foundation, Inc.
 //
@@ -25,20 +25,23 @@ 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
 {
   int value;
-  operator std::pair<const Key, int>() const { return {Key(&value), value}; }
+  operator std::pair<const Key, int>() const
+  { return {Key(&value), value}; }
 };
 
 int main()
@@ -46,4 +49,7 @@ int main()
     S s[1] = { {2} };
     std::unordered_map<Key, int, hash> m(s, s+1);
     std::unordered_multimap<Key, int, hash> mm(s, s+1);
+
+    m.insert(s, s + 1);
+    mm.insert(s, s + 1);
 }
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/cons/56112.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/56112.cc
new file mode 100644
index 00000000000..aa34ed4c603
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/56112.cc
@@ -0,0 +1,55 @@
+// { dg-do compile { 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>
+
+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
+{
+  int value;
+  operator Key() const
+  { return Key(&value); }
+};
+
+int main()
+{
+    S s[1] = { {2} };
+    std::unordered_set<Key, hash> m(s, s+1);
+    std::unordered_multiset<Key, hash> mm(s, s+1);
+
+    m.insert(s, s + 1);
+    mm.insert(s, s + 1);
+}

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

[François Dumont]

Gentle reminder, it is important to have this for gcc 12.

On 15/02/22 10:05, François Dumont wrote:
> We have a regression regarding management of types convertible to 
> value_type. It is an occurrence of PR 56112 but for the insert method.
>
>     libstdc++: [_Hashtable] Insert range of types convertible to 
> value_type PR 56112
>
>     Fix insertion of range of types convertible to value_type.
>
>     libstdc++-v3/ChangeLog:
>
>             PR libstdc++/56112
>             * include/bits/hashtable.h
>             (_Hashtable<>::_M_insert_unique_aux): New.
>             (_Hashtable<>::_S_to_value): New.
>             (_Hashtable<>::_M_insert(_Arg&&, const _NodeGenerator&, 
> true_type)): Use latters.
>             * testsuite/23_containers/unordered_map/cons/56112.cc: Use 
> dg-do compile.
>             * testsuite/23_containers/unordered_set/cons/56112.cc: New 
> test.
>
> Tested under Linux x86_64.
>
> Ok to commit ?
>
> François

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

[Jonathan Wakely]

On Mon, 21 Feb 2022 at 18:00, François Dumont via Libstdc++ <
libstdc++@gcc.gnu.org> wrote:

> Gentle reminder, it is important to have this for gcc 12.
>

Well, it's been broken since 4.8, so another year wouldn't be the end of
the world ;-)

I did start reviewing it, but I was trying to find a simpler way to solve
it than adding all those overloads. I'll take another look tomorrow and
either approve your patch or suggest something else.



>
> On 15/02/22 10:05, François Dumont wrote:
> > We have a regression regarding management of types convertible to
> > value_type. It is an occurrence of PR 56112 but for the insert method.
> >
> >     libstdc++: [_Hashtable] Insert range of types convertible to
> > value_type PR 56112
> >
> >     Fix insertion of range of types convertible to value_type.
> >
> >     libstdc++-v3/ChangeLog:
> >
> >             PR libstdc++/56112
> >             * include/bits/hashtable.h
> >             (_Hashtable<>::_M_insert_unique_aux): New.
> >             (_Hashtable<>::_S_to_value): New.
> >             (_Hashtable<>::_M_insert(_Arg&&, const _NodeGenerator&,
> > true_type)): Use latters.
> >             * testsuite/23_containers/unordered_map/cons/56112.cc: Use
> > dg-do compile.
> >             * testsuite/23_containers/unordered_set/cons/56112.cc: New
> > test.
> >
> > Tested under Linux x86_64.
> >
> > Ok to commit ?
> >
> > François
>
>
>

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

[François Dumont]

On 21/02/22 21:54, Jonathan Wakely wrote:
>
>
> On Mon, 21 Feb 2022 at 18:00, François Dumont via Libstdc++ 
> <libstdc++@gcc.gnu.org <mailto:libstdc%2B%2B@gcc.gnu.org>> wrote:
>
>     Gentle reminder, it is important to have this for gcc 12.
>
>
> Well, it's been broken since 4.8, so another year wouldn't be the end 
> of the world ;-)

Sorry for the pressure, I thought I had broken it with my fix of PR 
96088. Which moreover was in gcc 11.

So indeed not mandatory for gcc 12 but still nice to fix eventually.

Thanks


>
> I did start reviewing it, but I was trying to find a simpler way to 
> solve it than adding all those overloads. I'll take another look 
> tomorrow and either approve your patch or suggest something else.
>
>
>
>     On 15/02/22 10:05, François Dumont wrote:
>     > We have a regression regarding management of types convertible to
>     > value_type. It is an occurrence of PR 56112 but for the insert
>     method.
>     >
>     >     libstdc++: [_Hashtable] Insert range of types convertible to
>     > value_type PR 56112
>     >
>     >     Fix insertion of range of types convertible to value_type.
>     >
>     >     libstdc++-v3/ChangeLog:
>     >
>     >             PR libstdc++/56112
>     >             * include/bits/hashtable.h
>     >             (_Hashtable<>::_M_insert_unique_aux): New.
>     >             (_Hashtable<>::_S_to_value): New.
>     > (_Hashtable<>::_M_insert(_Arg&&, const _NodeGenerator&,
>     > true_type)): Use latters.
>     >             *
>     testsuite/23_containers/unordered_map/cons/56112.cc: Use
>     > dg-do compile.
>     >             *
>     testsuite/23_containers/unordered_set/cons/56112.cc: New
>     > test.
>     >
>     > Tested under Linux x86_64.
>     >
>     > Ok to commit ?
>     >
>     > François
>
>

[PATCH][_Hashtable] Fix insertion of range of type convertible to value_type PR 56112

[François Dumont]

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

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 ?

François


[-- Attachment #2: pr56112.patch --]
[-- Type: text/x-patch, Size: 9232 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..51518316cb8 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -109,6 +109,58 @@ 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; }
+
+      using __fst_type = typename _Value::first_type;
+
+      template<typename _Pair>
+	using __mutable_value_t =
+	  std::pair<
+	    typename std::remove_const<typename _Pair::first_type>::type,
+	    typename _Pair::second_type>;
+
+      constexpr __enable_if_t<std::is_const<__fst_type>::value,
+			      __mutable_value_t<_Value>&&>
+      operator()(__mutable_value_t<_Value>&& __x) noexcept
+      { return std::move(__x); }
+
+      constexpr __enable_if_t<std::is_const<__fst_type>::value,
+			      const __mutable_value_t<_Value>&>
+      operator()(const __mutable_value_t<_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..4476103c986 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,108 @@
 #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 );
+
+    m.insert(s, s + 1);
+    VERIFY( S::_count == 3 );
+
+    mm.insert(s, s + 1);
+    VERIFY( S::_count == 4 );
+}
+
+struct MoveOnlyKey
+{
+  explicit MoveOnlyKey(const int* p) : value(p) { }
+  MoveOnlyKey(const MoveOnlyKey&) = delete;
+  MoveOnlyKey(MoveOnlyKey&& k) : value(k.value)
+  { k.value = nullptr;  }
+  ~MoveOnlyKey() { value = nullptr; }
+
+  bool operator==(const MoveOnlyKey& k) const
+  { return *value == *k.value; }
+
+  const int* value;
+};
+
+struct MoveOnlyKeyHash
+{
+  std::size_t operator()(const MoveOnlyKey& k) const noexcept
+  { return *k.value; }
+};
+
+struct S2
+{
+  static int _count;
+
+  int value;
+  operator std::pair<MoveOnlyKey, int>() const
+  {
+    ++_count;
+    return { MoveOnlyKey(&value), value };
+  }
+};
+
+int S2::_count = 0;
+
+void test02()
+{
+    S2 s[1] = { {2} };
+    std::unordered_map<MoveOnlyKey, int, MoveOnlyKeyHash> m(s, s + 1);
+    VERIFY( S2::_count == 1 );
+
+    std::unordered_multimap<MoveOnlyKey, int, MoveOnlyKeyHash> mm(s, s + 1);
+    VERIFY( S2::_count == 2 );
+
+    m.insert(s, s + 1);
+    VERIFY( S2::_count == 3 );
+
+    mm.insert(s, s + 1);
+    VERIFY( S2::_count == 4 );
+}
+
+int main()
+{
+  test01();
+  test02();
+  return 0;
 }
diff --git a/libstdc++-v3/testsuite/23_containers/unordered_set/cons/56112.cc b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/56112.cc
new file mode 100644
index 00000000000..c55965a2caa
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/unordered_set/cons/56112.cc
@@ -0,0 +1,70 @@
+// { 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;
+
+int main()
+{
+    S s[1] = { {2} };
+    std::unordered_set<Key, hash> m(s, s + 1);
+    VERIFY( S::_count == 1 );
+
+    std::unordered_multiset<Key, hash> mm(s, s + 1);
+    VERIFY( S::_count == 2 );
+
+    m.insert(s, s + 1);
+    VERIFY( S::_count == 3 );
+
+    mm.insert(s, s + 1);
+    VERIFY( S::_count == 4 );
+}

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

[François Dumont]

Gentle reminder !

On 05/05/22 19:37, François Dumont 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 ?
>
> François
>

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

[François Dumont]

Still no chance to validate ?

On 11/05/22 19:03, François Dumont wrote:
> Gentle reminder !
>
> On 05/05/22 19:37, François Dumont 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 ?
>>
>> François
>>
>

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

[Jonathan Wakely]

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.

The new 23_containers/unordered_set/cons/56112.cc test fails for GCC
11 but passes for GCC 12, even without your patch. Is it actually
testing some other change, not this patch, and not the 2013 fix for PR
56112?

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

[Jonathan Wakely]

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


>
> The new 23_containers/unordered_set/cons/56112.cc test fails for GCC
> 11 but passes for GCC 12, even without your patch. Is it actually
> testing some other change, not this patch, and not the 2013 fix for PR
> 56112?

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

[Jonathan Wakely]

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.

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

[François Dumont]

On 24/05/22 12: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.
>
> The new 23_containers/unordered_set/cons/56112.cc test fails for GCC
> 11 but passes for GCC 12, even without your patch. Is it actually
> testing some other change, not this patch, and not the 2013 fix for PR
> 56112?
>
> .

Yes, I'm not surprised. This is due to this operator on _ValueTypeEnforcer:


       constexpr __enable_if_t<std::is_const<__fst_type>::value,
                   const __mutable_value_t<_Value>&>
       operator()(const __mutable_value_t<_Value>& __x) noexcept
       { return __x; }

I thought it was nice to allow move construction in this case.

If the Standard forces a copy in this case I can just remove it.

François

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

[François Dumont]

[-- 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;
+}

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

[François Dumont]

Hi

Is this less ambitious version ok ?

Thanks

On 25/05/22 07:09, François Dumont wrote:
> 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.
>>

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

[Jonathan Wakely]

On Wed, 25 May 2022 at 06:10, François Dumont <frs.dumont@gmail.com> wrote:
>
> 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 ?

I think "_ConvertToValueType" would be a better name than
_ValueTypeEnforcer, and all overloads of _ValueTypeEnforcer can be
const.

OK with that change, thanks.