Improve insert/emplace robustness to self insertion

[FranÃois Dumont <frs dot dumont at gmail dot com>]

Hi

    Following below discussion here is a patch to make sure we 
correctly deal with insertion of instances stored into the vector itself.

    When we don't need reallocation I have implemented the libc++ trick 
to avoid an intermediate copy. I did my best to detect when a value_type 
instance is being inserted, whatever how it is inserted, lvalue/rvalue 
or xvalue reference. I was thinking that taking address of an rvalue 
would fail but it didn't. I also reuse _M_data_ptr method even if when 
vector is empty it doesn't work but vector is not empty when used so it 
should be fine. In the _M_insert_aux taking variadic number of 
parameters I always create a copy cause we can't know if one of those 
parameter has a link to vector values.

    We could also implement libc++ trick in _M_fill_insert but not sure 
it worth it, what do you think ?

    All vector tests run so far.

François

On 20/06/2016 09:42, Jonathan Wakely wrote:
> On 19/06/16 10:21 +0200, François Dumont wrote:
> > On 16/06/2016 22:21, Jonathan Wakely wrote:
> > > On 16/06/16 21:27 +0200, François Dumont wrote:
> > > > Very nice improvement. Could also benefit to other containers, 
> > > > especially std::deque. Do you plan to take care of it ?
> > >
> > > Good point - I'd only looked at it for std::vector, because that's
> > > what Howard's experiment tested. I haven't looked at the other
> > > containers at all, and wasn't planning to do so. If you have time to
> > > look at them that would be great, otherwise I'll add it to my TODO
> > > list for something to look at later.
> > I started considering it and so came to the question of 
> > insert/emplace of the container self values. Is the following program 
> > ill-formed ?
> >
> > int main()
> > {
> >  std::vector<std::vector<int>> vv =
> >    {
> >      { 2, 3 },
> >      { 4, 5 },
> >      { 0, 1 }
> >    };
> >
> >  vv.reserve(4);
> >  vv.emplace(vv.begin(), vv[0]);
> >
> >  assert( vv[0].size() == 2 );
> > }
> >
> > The assert fails because we end-up assigning a moved vector instance 
> > to vv first entry. This is not a regression of this patch, we were 
> > already not creating any copy before moving all vector values. If 
> > this program is ill-formed why does libc++ consider this kind of 
> > situation in its insert implementation ?
>
> I think this should work correctly, for both insert and emplace.
>
> > Note that it gave me the idear of adding a DEBUG check detecting when 
> > a moved instance is being used. A moved instance shall only be 
> > destroyed or assigned, no ?
>
> That's not true in general, but is true for these members of vector.

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index eaafa22..d7435cc 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -949,7 +949,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __cplusplus >= 201103L
 	  _M_emplace_back_aux(__x);
 #else
-	  _M_insert_aux(end(), __x);
+	  _M_realloc_insert_aux(end(), __x);
 #endif
       }
 
@@ -1432,23 +1432,37 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #endif
 
       // Called by insert(p,x)
+      void
+      _M_insert_aux(iterator __position, const value_type& __x)
+      { _M_insert_value_aux(__position, __x); }
+
 #if __cplusplus < 201103L
       void
-      _M_insert_aux(iterator __position, const value_type& __x);
-#else
-      template<typename... _Args>
-	static void
-	_S_insert_aux_assign(iterator __pos, _Args&&... __args)
-	{ *__pos =  _Tp(std::forward<_Args>(__args)...); }
+      _M_insert_value_aux(iterator __position, const value_type& __x);
 
-      static void
-      _S_insert_aux_assign(iterator __pos, _Tp&& __arg)
-      { *__pos = std::move(__arg); }
+      void
+      _M_realloc_insert_aux(iterator __position, const value_type& __x);
+#else
+      template<typename _Val>
+        void
+        _M_insert_value_aux(iterator __position, _Val&& __x);
 
       template<typename... _Args>
 	void
 	_M_insert_aux(iterator __position, _Args&&... __args);
 
+      void
+      _M_insert_aux(iterator __position, value_type& __x)
+      { _M_insert_value_aux(__position, __x); }
+
+      void
+      _M_insert_aux(iterator __position, value_type&& __x)
+      { _M_insert_value_aux(__position, std::move(__x)); }
+
+      template<typename... _Args>
+        void
+        _M_realloc_insert_aux(iterator __position, _Args&&... __args);
+
       template<typename... _Args>
 	void
 	_M_emplace_back_aux(_Args&&... __args);
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 604be7b..dab578e 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -112,27 +112,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #endif
     {
       const size_type __n = __position - begin();
-      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	  && __position == end())
-	{
-	  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
-	  ++this->_M_impl._M_finish;
-	}
+      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+	if (__position == end())
+	  {
+	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, __x);
+	    ++this->_M_impl._M_finish;
+	  }
+	else
+#if __cplusplus >= 201103L
+	  _M_insert_value_aux(begin() + (__position - cbegin()), __x);
+#else
+	  _M_insert_value_aux(__position, __x);
+#endif
       else
-	{
 #if __cplusplus >= 201103L
-	  const auto __pos = begin() + (__position - cbegin());
-	  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
-	    {
-	      _Tp __x_copy = __x;
-	      _M_insert_aux(__pos, std::move(__x_copy));
-	    }
-	  else
-	    _M_insert_aux(__pos, __x);
+	_M_realloc_insert_aux(begin() + (__position - cbegin()), __x);
 #else
-	    _M_insert_aux(__position, __x);
+	_M_realloc_insert_aux(__position, __x);
 #endif
-	}
+
       return iterator(this->_M_impl._M_start + __n);
     }
 
@@ -303,16 +301,20 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       emplace(const_iterator __position, _Args&&... __args)
       {
 	const size_type __n = __position - begin();
-	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	    && __position == end())
-	  {
-	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
-				     std::forward<_Args>(__args)...);
-	    ++this->_M_impl._M_finish;
-	  }
+	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+	  if (__position == end())
+	    {
+	      _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				       std::forward<_Args>(__args)...);
+	      ++this->_M_impl._M_finish;
+	    }
+	  else
+	    _M_insert_aux(begin() + (__position - cbegin()),
+			  std::forward<_Args>(__args)...);
 	else
-	  _M_insert_aux(begin() + (__position - cbegin()),
-			std::forward<_Args>(__args)...);
+	  _M_realloc_insert_aux(begin() + (__position - cbegin()),
+				std::forward<_Args>(__args)...);
+
 	return iterator(this->_M_impl._M_start + __n);
       }
 
@@ -321,84 +323,115 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       void
       vector<_Tp, _Alloc>::
       _M_insert_aux(iterator __position, _Args&&... __args)
+      {
+	_Tp __x(std::forward<_Args>(__args)...);
+	_Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				 std::move(*(this->_M_impl._M_finish - 1)));
+	++this->_M_impl._M_finish;
+
+	std::move_backward(__position.base(),
+			   this->_M_impl._M_finish - 2,
+			   this->_M_impl._M_finish - 1);
+	*__position = std::move(__x);
+      }
+#endif
+
+#if __cplusplus >= 201103L
+  template<typename _Tp, typename _Alloc>
+    template<typename _Val>
+      void
+      vector<_Tp, _Alloc>::
+      _M_insert_value_aux(iterator __position, _Val&& __x)
 #else
   template<typename _Tp, typename _Alloc>
     void
     vector<_Tp, _Alloc>::
-    _M_insert_aux(iterator __position, const _Tp& __x)
+    _M_insert_value_aux(iterator __position, const _Tp& __x)
 #endif
     {
-      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+      const _Tp* __ptr = std::__addressof(__x);
+
+      _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+			       _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
+      ++this->_M_impl._M_finish;
+
+      _GLIBCXX_MOVE_BACKWARD3(__position.base(),
+			      this->_M_impl._M_finish - 2,
+			      this->_M_impl._M_finish - 1);
+
+      if (_M_data_ptr(__position.base()) <= __ptr
+	  && __ptr < _M_data_ptr(this->_M_impl._M_finish - 1))
 	{
-	  _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
-			           _GLIBCXX_MOVE(*(this->_M_impl._M_finish
-				                   - 1)));
-	  ++this->_M_impl._M_finish;
-#if __cplusplus < 201103L
-	  _Tp __x_copy = __x;
-#endif
-	  _GLIBCXX_MOVE_BACKWARD3(__position.base(),
-				  this->_M_impl._M_finish - 2,
-				  this->_M_impl._M_finish - 1);
-#if __cplusplus < 201103L
-	  *__position = __x_copy;
-#else
-	  _S_insert_aux_assign(__position, std::forward<_Args>(__args)...);
-#endif
+	  ++__ptr;
+	  *__position = *__ptr;
 	}
       else
+	*__position = _GLIBCXX_FORWARD(_Val, __x);
+    }
+
+#if __cplusplus >= 201103L
+  template<typename _Tp, typename _Alloc>
+    template<typename... _Args>
+      void
+      vector<_Tp, _Alloc>::
+      _M_realloc_insert_aux(iterator __position, _Args&&... __args)
+#else
+  template<typename _Tp, typename _Alloc>
+    void
+    vector<_Tp, _Alloc>::
+    _M_realloc_insert_aux(iterator __position, const _Tp& __x)
+#endif
+    {
+      const size_type __len =
+	_M_check_len(size_type(1), "vector::_M_realloc_insert_aux");
+      const size_type __elems_before = __position - begin();
+      pointer __new_start(this->_M_allocate(__len));
+      pointer __new_finish(__new_start);
+      __try
 	{
-	  const size_type __len =
-	    _M_check_len(size_type(1), "vector::_M_insert_aux");
-	  const size_type __elems_before = __position - begin();
-	  pointer __new_start(this->_M_allocate(__len));
-	  pointer __new_finish(__new_start);
-	  __try
-	    {
-	      // The order of the three operations is dictated by the C++0x
-	      // case, where the moves could alter a new element belonging
-	      // to the existing vector.  This is an issue only for callers
-	      // taking the element by const lvalue ref (see 23.1/13).
-	      _Alloc_traits::construct(this->_M_impl,
-		                       __new_start + __elems_before,
+	  // The order of the three operations is dictated by the C++0x
+	  // case, where the moves could alter a new element belonging
+	  // to the existing vector.  This is an issue only for callers
+	  // taking the element by const lvalue ref (see 23.1/13).
+	  _Alloc_traits::construct(this->_M_impl,
+				   __new_start + __elems_before,
 #if __cplusplus >= 201103L
-				       std::forward<_Args>(__args)...);
+				   std::forward<_Args>(__args)...);
 #else
-	                               __x);
+				   __x);
 #endif
-	      __new_finish = pointer();
+	  __new_finish = pointer();
 
-	      __new_finish
-		= std::__uninitialized_move_if_noexcept_a
-		(this->_M_impl._M_start, __position.base(),
-		 __new_start, _M_get_Tp_allocator());
+	  __new_finish
+	    = std::__uninitialized_move_if_noexcept_a
+	    (this->_M_impl._M_start, __position.base(),
+	     __new_start, _M_get_Tp_allocator());
 
-	      ++__new_finish;
+	  ++__new_finish;
 
-	      __new_finish
-		= std::__uninitialized_move_if_noexcept_a
-		(__position.base(), this->_M_impl._M_finish,
-		 __new_finish, _M_get_Tp_allocator());
-	    }
-          __catch(...)
-	    {
-	      if (!__new_finish)
-		_Alloc_traits::destroy(this->_M_impl,
-		                       __new_start + __elems_before);
-	      else
-		std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
-	      _M_deallocate(__new_start, __len);
-	      __throw_exception_again;
-	    }
-	  std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
-			_M_get_Tp_allocator());
-	  _M_deallocate(this->_M_impl._M_start,
-			this->_M_impl._M_end_of_storage
-			- this->_M_impl._M_start);
-	  this->_M_impl._M_start = __new_start;
-	  this->_M_impl._M_finish = __new_finish;
-	  this->_M_impl._M_end_of_storage = __new_start + __len;
+	  __new_finish
+	    = std::__uninitialized_move_if_noexcept_a
+	    (__position.base(), this->_M_impl._M_finish,
+	     __new_finish, _M_get_Tp_allocator());
+	}
+      __catch(...)
+	{
+	  if (!__new_finish)
+	    _Alloc_traits::destroy(this->_M_impl,
+				   __new_start + __elems_before);
+	  else
+	    std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
+	  _M_deallocate(__new_start, __len);
+	  __throw_exception_again;
 	}
+      std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+		    _M_get_Tp_allocator());
+      _M_deallocate(this->_M_impl._M_start,
+		    this->_M_impl._M_end_of_storage
+		    - this->_M_impl._M_start);
+      this->_M_impl._M_start = __new_start;
+      this->_M_impl._M_finish = __new_finish;
+      this->_M_impl._M_end_of_storage = __new_start + __len;
     }
 
 #if __cplusplus >= 201103L
@@ -493,7 +526,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	      pointer __new_finish(__new_start);
 	      __try
 		{
-		  // See _M_insert_aux above.
+		  // See _M_realloc_insert_aux above.
 		  std::__uninitialized_fill_n_a(__new_start + __elems_before,
 						__n, __x,
 						_M_get_Tp_allocator());
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
new file mode 100644
index 0000000..d452b5b
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/emplace/self_emplace.cc
@@ -0,0 +1,144 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2016 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 <vector>
+#include "testsuite_hooks.h"
+
+bool test __attribute__((unused)) = true;
+
+void
+test01()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure emplace will imply reallocation.
+  VERIFY( vv.capacity() == 3 );
+
+  vv.emplace(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+void
+test02()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure emplace won't reallocate.
+  vv.reserve(4);
+  vv.emplace(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+struct A
+{
+  A(int i) : _i(i)
+  { }
+
+  A(const A& other) : _i(other._i)
+  {
+    VERIFY( other._i >= 0 );
+  }
+
+  A(A&& other) : _i(other._i)
+  {
+    VERIFY( other._i >= 0 );
+
+    other._i = -1;
+  }
+
+  A(std::vector<A>::iterator it) : _i(it->_i)
+  {
+    VERIFY( it->_i >= 0 );
+  }
+
+  A& operator=(const A&) = default;
+  A& operator=(A&& other)
+  {
+    VERIFY(other._i >= 0 );
+
+    _i = other._i;
+    other._i = -1;
+    return *this;
+  }
+
+  int _i;
+};
+
+void
+test03()
+{
+  std::vector<A> va =
+    {
+      { A(1) },
+      { A(2) },
+      { A(3) }
+    };
+
+  // Make sure emplace will imply reallocation.
+  VERIFY( va.capacity() == 3 );
+
+  va.emplace(va.begin(), va.begin());
+
+  VERIFY( va.size() == 4 );
+  VERIFY( va[0]._i == 1 );
+}
+
+void
+test04()
+{
+  std::vector<A> va =
+    {
+      { A(1) },
+      { A(2) },
+      { A(3) }
+    };
+
+  // Make sure emplace won't reallocate.
+  va.reserve(4);
+  va.emplace(va.begin(), va.begin());
+
+  VERIFY( va.size() == 4 );
+  VERIFY( va[0]._i == 1 );
+}
+
+int main()
+{
+  test01();
+  test02();
+  test03();
+  test04();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
new file mode 100644
index 0000000..9944cbb
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert/self_insert.cc
@@ -0,0 +1,70 @@
+// { dg-options "-std=gnu++11" }
+
+// Copyright (C) 2016 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 <vector>
+
+#include "testsuite_hooks.h"
+
+bool test __attribute__((unused)) = true;
+
+void test01()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure it doesn't reallocate during insertion.
+  vv.reserve(4);
+
+  vv.insert(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+void test02()
+{
+  std::vector<std::vector<int>> vv =
+    {
+      { 2, 3 },
+      { 4, 5 },
+      { 0, 1 }
+    };
+
+  // Make sure we will reallocate for insertion.
+  VERIFY( vv.capacity() == 3 );
+
+  vv.insert(vv.begin(), vv[0]);
+
+  VERIFY( vv.size() == 4 );
+  VERIFY( vv[0].size() == 2 );
+  VERIFY( vv[0][0] == 2 );
+  VERIFY( vv[0][1] == 3 );
+}
+
+int main()
+{
+  test01();
+  test02();
+}
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
index 39a3f03..4c9c57e 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc
@@ -111,7 +111,7 @@ operator==(const X::special& lhs, const X::special& rhs)
 void
 test01()
 {
-  const X::special expected{ 0, 1, 1, 0, 1, 3 };
+  const X::special expected{ 0, 0, 0, 1, 1, 2 };
   X::special ins, emp;
   {
     std::vector<X> v;