re PR libstdc++/59872 (Cannot move std::map with move-only mapped_type)

	PR libstdc++/59872
	* include/bits/stl_map.h (map::operator=(map&&)): Fix comment.
	* include/bits/stl_multimap.h (multimap::operator=(multimap&&)):
	Likewise.
	* include/bits/stl_multiset.h (multiset::operator=(multiset&&)):
	Likewise.
	* include/bits/stl_set.h (set::operator=(set&&)): Likewise.
	* include/bits/stl_tree.h (_Rb_tree::_M_move_data): New overloaded
	functions to perform moving or copying of elements from rvalue tree.
	(_Rb_tree::_Rb_tree(_Rb_tree&&)): Use _M_move_data.
	(_Rb_tree::_Rb_tree(_Rb_tree&&, _Node_allocator&&)): Likewise.
	* testsuite/23_containers/map/59872.cc: New.
	* testsuite/23_containers/map/56613.cc: Remove duplicate include.

From-SVN: r206994

8 files changed, 113 insertions, 46 deletions

diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog
index e2b9daa..f5cfe01 100644
--- a/libstdc++-v3/ChangeLog
+++ b/libstdc++-v3/ChangeLog
@@ -3,6 +3,20 @@
 	* doc/xml/faq.xml (a-how_to_set_paths): Expand FAQ answer.
 	* doc/xml/manual/abi.xml (abi.versioning.history): Correct symver.
 
+	PR libstdc++/59872
+	* include/bits/stl_map.h (map::operator=(map&&)): Fix comment.
+	* include/bits/stl_multimap.h (multimap::operator=(multimap&&)):
+	Likewise.
+	* include/bits/stl_multiset.h (multiset::operator=(multiset&&)):
+	Likewise.
+	* include/bits/stl_set.h (set::operator=(set&&)): Likewise.
+	* include/bits/stl_tree.h (_Rb_tree::_M_move_data): New overloaded
+	functions to perform moving or copying of elements from rvalue tree.
+	(_Rb_tree::_Rb_tree(_Rb_tree&&)): Use _M_move_data.
+	(_Rb_tree::_Rb_tree(_Rb_tree&&, _Node_allocator&&)): Likewise.
+	* testsuite/23_containers/map/59872.cc: New.
+	* testsuite/23_containers/map/56613.cc: Remove duplicate include.
+
 2014-01-22  Jonathan Wakely  <jwakely@redhat.com>
 
 	* include/bits/stl_deque.h (_Deque_impl): Move comment.
diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h
index e261be8..fa121e2 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -301,8 +301,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  @brief  %Map move assignment operator.
        *  @param  __x  A %map of identical element and allocator types.
        *
-       *  The contents of @a __x are moved into this map (without copying).
-       *  @a __x is a valid, but unspecified %map.
+       *  The contents of @a __x are moved into this map (without copying
+       *  if the allocators compare equal or get moved on assignment).
+       *  Afterwards @a __x is in a valid, but unspecified state.
        */
       map&
       operator=(map&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h
index 84046cb..e4575c1 100644
--- a/libstdc++-v3/include/bits/stl_multimap.h
+++ b/libstdc++-v3/include/bits/stl_multimap.h
@@ -295,8 +295,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  @brief  %Multimap move assignment operator.
        *  @param  __x  A %multimap of identical element and allocator types.
        *
-       *  The contents of @a __x are moved into this multimap (without copying).
-       *  @a __x is a valid, but unspecified multimap.
+       *  The contents of @a __x are moved into this multimap (without copying
+       *  if the allocators compare equal or get moved on assignment).
+       *  Afterwards @a __x is in a valid, but unspecified state.
        */
       multimap&
       operator=(multimap&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h
index 3305107..6d71c1b 100644
--- a/libstdc++-v3/include/bits/stl_multiset.h
+++ b/libstdc++-v3/include/bits/stl_multiset.h
@@ -267,9 +267,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  @brief  %Multiset move assignment operator.
        *  @param  __x  A %multiset of identical element and allocator types.
        *
-       *  The contents of @a __x are moved into this %multiset
-       *  (without copying).  @a __x is a valid, but unspecified
-       *  %multiset.
+       *  The contents of @a __x are moved into this %multiset (without
+       *  copying if the allocators compare equal or get moved on assignment).
+       *  Afterwards @a __x is in a valid, but unspecified state.
        */
       multiset&
       operator=(multiset&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h
index 652be58..3a39154 100644
--- a/libstdc++-v3/include/bits/stl_set.h
+++ b/libstdc++-v3/include/bits/stl_set.h
@@ -271,8 +271,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
        *  @brief %Set move assignment operator.
        *  @param __x  A %set of identical element and allocator types.
        *
-       *  The contents of @a __x are moved into this %set (without copying).
-       *  @a __x is a valid, but unspecified %set.
+       *  The contents of @a __x are moved into this %set (without copying
+       *  if the allocators compare equal or get moved on assignment).
+       *  Afterwards @a __x is in a valid, but unspecified state.
        */
       set&
       operator=(set&& __x) noexcept(_Alloc_traits::_S_nothrow_move())
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index e41b134..d24b1f7 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -698,8 +698,11 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
       }
 
       _Rb_tree(_Rb_tree&& __x)
-      : _Rb_tree(std::move(__x), std::move(__x._M_get_Node_allocator()))
-      { }
+      : _M_impl(__x._M_impl._M_key_compare, __x._M_get_Node_allocator())
+      {
+	if (__x._M_root() != 0)
+	  _M_move_data(__x, std::true_type());
+      }
 
       _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
       : _Rb_tree(std::move(__x), _Node_allocator(__a))
@@ -948,6 +951,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 #if __cplusplus >= 201103L
       bool
       _M_move_assign(_Rb_tree&);
+
+    private:
+      // Move elements from container with equal allocator.
+      void
+      _M_move_data(_Rb_tree&, std::true_type);
+
+      // Move elements from container with possibly non-equal allocator,
+      // which might result in a copy not a move.
+      void
+      _M_move_data(_Rb_tree&, std::false_type);
 #endif
     };
 
@@ -1013,30 +1026,44 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
     _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
     : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
     {
+      using __eq = integral_constant<bool, _Alloc_traits::_S_always_equal()>;
       if (__x._M_root() != 0)
-	{
-	  if (!_Alloc_traits::_S_always_equal()
-	      && __x._M_get_Node_allocator() != __a)
-	    {
-	      _M_root() = _M_copy(__x._M_begin(), _M_end());
-	      _M_leftmost() = _S_minimum(_M_root());
-	      _M_rightmost() = _S_maximum(_M_root());
-	      _M_impl._M_node_count = __x._M_impl._M_node_count;
-	    }
-	  else
-	    {
-	      _M_root() = __x._M_root();
-	      _M_leftmost() = __x._M_leftmost();
-	      _M_rightmost() = __x._M_rightmost();
-	      _M_root()->_M_parent = _M_end();
+	_M_move_data(__x, __eq());
+    }
 
-	      __x._M_root() = 0;
-	      __x._M_leftmost() = __x._M_end();
-	      __x._M_rightmost() = __x._M_end();
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+    void
+    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    _M_move_data(_Rb_tree& __x, std::true_type)
+    {
+      _M_root() = __x._M_root();
+      _M_leftmost() = __x._M_leftmost();
+      _M_rightmost() = __x._M_rightmost();
+      _M_root()->_M_parent = _M_end();
 
-	      this->_M_impl._M_node_count = __x._M_impl._M_node_count;
-	      __x._M_impl._M_node_count = 0;
-	    }
+      __x._M_root() = 0;
+      __x._M_leftmost() = __x._M_end();
+      __x._M_rightmost() = __x._M_end();
+
+      this->_M_impl._M_node_count = __x._M_impl._M_node_count;
+      __x._M_impl._M_node_count = 0;
+    }
+
+  template<typename _Key, typename _Val, typename _KeyOfValue,
+           typename _Compare, typename _Alloc>
+    void
+    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+    _M_move_data(_Rb_tree& __x, std::false_type)
+    {
+      if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
+	  _M_move_data(__x, std::true_type());
+      else
+	{
+	  _M_root() = _M_copy(__x._M_begin(), _M_end());
+	  _M_leftmost() = _S_minimum(_M_root());
+	  _M_rightmost() = _S_maximum(_M_root());
+	  _M_impl._M_node_count = __x._M_impl._M_node_count;
 	}
     }
 
@@ -1052,19 +1079,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 	{
 	  clear();
 	  if (__x._M_root() != 0)
-	    {
-	      _M_root() = __x._M_root();
-	      _M_leftmost() = __x._M_leftmost();
-	      _M_rightmost() = __x._M_rightmost();
-	      _M_root()->_M_parent = _M_end();
-
-	      __x._M_root() = 0;
-	      __x._M_leftmost() = __x._M_end();
-	      __x._M_rightmost() = __x._M_end();
-
-	      this->_M_impl._M_node_count = __x._M_impl._M_node_count;
-	      __x._M_impl._M_node_count = 0;
-	    }
+	    _M_move_data(__x, std::true_type());
 	  if (_Alloc_traits::_S_propagate_on_move_assign())
 	    std::__alloc_on_move(_M_get_Node_allocator(),
 				 __x._M_get_Node_allocator());
diff --git a/libstdc++-v3/testsuite/23_containers/map/56613.cc b/libstdc++-v3/testsuite/23_containers/map/56613.cc
index 3c1164f..6ef2490 100644
--- a/libstdc++-v3/testsuite/23_containers/map/56613.cc
+++ b/libstdc++-v3/testsuite/23_containers/map/56613.cc
@@ -24,7 +24,6 @@
 // { dg-options "-std=gnu++11" }
 
 // libstdc++/56613
-#include <map>
 
 // A conforming C++03 allocator, should still work in C++11 mode.
 template<typename T>
diff --git a/libstdc++-v3/testsuite/23_containers/map/59872.cc b/libstdc++-v3/testsuite/23_containers/map/59872.cc
new file mode 100644
index 0000000..be8413b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/59872.cc
@@ -0,0 +1,36 @@
+// Copyright (C) 2014 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/>.
+
+// { dg-do compile }
+// { dg-options "-std=gnu++11" }
+
+// libstdc++/59872
+
+#include <map>
+
+struct MoveOnly
+{
+    MoveOnly() = default;
+    MoveOnly(MoveOnly&&) = default;
+    MoveOnly(const MoveOnly&) = delete;
+};
+
+using test_type = std::map<int, MoveOnly>;
+
+test_type p;
+test_type q(std::move(p));
+test_type r(std::move(p), test_type::allocator_type());