Re: Improve insert/emplace robustness to self insertion

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

On 05/07/2016 12:47, Jonathan Wakely wrote:
> On 04/07/16 15:55 +0100, Jonathan Wakely wrote:
> > I'm getting nervous about the smart insertion trick to avoid making a
> > copy, I have a devious testcase in mind which will break with that
> > change. I'll share the testcase later today.
>
> Here's a testcase which passes with libstdc++ but fails with libc++
> because libc++ doesn't make a copy when inserting a T lvalue into
> std::vector<T>:
>
> #include <vector>
> #include <memory>
> #include <cassert>
>
> struct T
> {
>  T(int v = 0) : value(v) { }
>  T(const T& t);
>  T& operator=(const T& t);
>  void make_child() { child = std::make_unique<T>(value + 10); }
>  std::unique_ptr<T> child;
>  int value;
> };
>
> T::T(const T& t) : value(t.value)
> {
>  if (t.child)
>    child.reset(new T(*t.child));
> }
>
> T& T::operator=(const T& t)
> {
>  value = t.value;
>  if (t.child)
>  {
>    if (child)
>      *child = *t.child;
>    else
>      child.reset(new T(*t.child));
>  }
>  else
>    child.reset();
>  return *this;
> }
>
> int main()
> {
>  std::vector<T> v;
>  v.reserve(3);
>  v.push_back(T(1));
>  v.back().make_child();
>  v.push_back(T(2));
>  v.back().make_child();
>
>  assert(v[1].child->value == 12);
>  assert(v[1].child->child == nullptr);
>
>  v.insert(v.begin(), *v[1].child);
>
>  assert(v[0].value == 12);
>  assert(v[0].child == nullptr);
> }
>
> The problem is that the object being inserted (*v[1].child) is not an
> element of the vector, so the optimization assumes it is unchanged by
> shuffling the existing elements. That assumption is wrong.
>
> As far as I can see, this program is perfectly valid. It's slightly
> contrived to prove a point, but it's not entirely unrealistic code.
Don't you plan to add it to the testsuite ?

On my side I rebase part of my patch to reorganize a little bit code. I 
reintroduced _M_realloc_insert which isolates the code of _M_insert_aux 
used when we need to reallocate memory. So _M_insert_aux is used only 
when insertion can be done in place. It is a nice replacement for 
_M_emplace_back_aux that have been removed. In most of vector modifiers 
we start checking if we need to reallocate or not. With this 
reorganization we don't check it several times. Moreover, as soon as we 
reallocate we know that we don't need to do any temporary copy so 
insert_vs_emplace.cc test04 has been adapted and we now have no 
situation where emplace and insert are not equivalent.

    * include/bits/stl_vector.h (push_back(const value_type&)): Forward
    to _M_realloc_insert.
    (insert(const_iterator, value_type&&)): Forward to _M_insert_rval.
    (_M_realloc_insert): Declare new function.
    (_M_emplace_back_aux): Remove definition.
    * include/bits/vector.tcc (emplace_back(_Args...)):
    Use _M_realloc_insert.
    (insert(const_iterator, const value_type&)): Likewise.
    (_M_insert_rval, _M_emplace_aux): Likewise.
    (_M_emplace_back_aux): Remove declaration.
    (_M_realloc_insert): Define.
    * testsuite/23_containers/vector/modifiers/insert_vs_emplace.cc:
    Adjust expected results for emplacing an lvalue with reallocation.

Tested under Linux x86_64.

Ok to commit ?

François

diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index 8e8aa7c..85abf4a 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -946,11 +946,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	    ++this->_M_impl._M_finish;
 	  }
 	else
-#if __cplusplus >= 201103L
-	  _M_emplace_back_aux(__x);
-#else
-	  _M_insert_aux(end(), __x);
-#endif
+	  _M_realloc_insert(end(), __x);
       }
 
 #if __cplusplus >= 201103L
@@ -1436,6 +1432,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       // Called by insert(p,x)
       void
       _M_insert_aux(iterator __position, const value_type& __x);
+
+      void
+      _M_realloc_insert(iterator __position, const value_type& __x);
 #else
       // A value_type object constructed with _Alloc_traits::construct()
       // and destroyed with _Alloc_traits::destroy().
@@ -1469,16 +1468,14 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	void
 	_M_insert_aux(iterator __position, _Arg&& __arg);
 
+      template<typename... _Args>
+	void
+	_M_realloc_insert(iterator __position, _Args&&... __args);
+
       // Either move-construct at the end, or forward to _M_insert_aux.
       iterator
       _M_insert_rval(const_iterator __position, value_type&& __v);
 
-      // Called by push_back(x) and emplace_back(args) when they need to
-      // reallocate.
-      template<typename... _Args>
-	void
-	_M_emplace_back_aux(_Args&&... __args);
-
       // Try to emplace at the end, otherwise forward to _M_insert_aux.
       template<typename... _Args>
 	iterator
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index 6e9be7f..b291e95 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -98,7 +98,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	    ++this->_M_impl._M_finish;
 	  }
 	else
-	  _M_emplace_back_aux(std::forward<_Args>(__args)...);
+	  _M_realloc_insert(end(), std::forward<_Args>(__args)...);
       }
 #endif
 
@@ -112,29 +112,32 @@ _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())
+      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);
+	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				     __x);
 	    ++this->_M_impl._M_finish;
 	  }
 	else
 	  {
 #if __cplusplus >= 201103L
 	    const auto __pos = begin() + (__position - cbegin());
-	  if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
-	    {
 	    // __x could be an existing element of this vector, so make a
 	    // copy of it before _M_insert_aux moves elements around.
 	    _Temporary_value __x_copy(this, __x);
 	    _M_insert_aux(__pos, std::move(__x_copy._M_val()));
-	    }
-	  else
-	    _M_insert_aux(__pos, __x);
 #else
 	    _M_insert_aux(__position, __x);
 #endif
 	  }
+      else
+#if __cplusplus >= 201103L
+	_M_realloc_insert(begin() + (__position - cbegin()), __x);
+#else
+	_M_realloc_insert(__position, __x);
+#endif
+
       return iterator(this->_M_impl._M_start + __n);
     }
 
@@ -304,8 +307,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator
     {
       const auto __n = __position - cbegin();
-      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage
-	  && __position == cend())
+      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+	if (__position == cend())
 	  {
 	    _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
 				     std::move(__v));
@@ -313,6 +316,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  }
 	else
 	  _M_insert_aux(begin() + __n, std::move(__v));
+      else
+	_M_realloc_insert(begin() + __n, std::move(__v));
+
       return iterator(this->_M_impl._M_start + __n);
     }
 
@@ -324,8 +330,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       -> iterator
       {
 	const auto __n = __position - cbegin();
+	if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
 	  if (__position == cend())
-	  emplace_back(std::forward<_Args>(__args)...);
+	    {
+	      _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+				       std::forward<_Args>(__args)...);
+	      ++this->_M_impl._M_finish;
+	    }
 	  else
 	    {
 	      // We need to construct a temporary because something in __args...
@@ -334,6 +345,9 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	      _Temporary_value __tmp(this, std::forward<_Args>(__args)...);
 	      _M_insert_aux(begin() + __n, std::move(__tmp._M_val()));
 	    }
+	else
+	  _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...);
+
 	return iterator(this->_M_impl._M_start + __n);
       }
 
@@ -349,8 +363,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
     _M_insert_aux(iterator __position, const _Tp& __x)
 #endif
     {
-      if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
-	{
       _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
 			       _GLIBCXX_MOVE(*(this->_M_impl._M_finish
 					       - 1)));
@@ -367,10 +379,22 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       *__position = std::forward<_Arg>(__arg);
 #endif
     }
-      else
+
+#if __cplusplus >= 201103L
+  template<typename _Tp, typename _Alloc>
+    template<typename... _Args>
+      void
+      vector<_Tp, _Alloc>::
+      _M_realloc_insert(iterator __position, _Args&&... __args)
+#else
+  template<typename _Tp, typename _Alloc>
+    void
+    vector<_Tp, _Alloc>::
+    _M_realloc_insert(iterator __position, const _Tp& __x)
+#endif
     {
       const size_type __len =
-	    _M_check_len(size_type(1), "vector::_M_insert_aux");
+	_M_check_len(size_type(1), "vector::_M_realloc_insert");
       const size_type __elems_before = __position - begin();
       pointer __new_start(this->_M_allocate(__len));
       pointer __new_finish(__new_start);
@@ -384,7 +408,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	  _Alloc_traits::construct(this->_M_impl,
 				   __new_start + __elems_before,
 #if __cplusplus >= 201103L
-				       std::forward<_Arg>(__arg));
+				   std::forward<_Args>(__args)...);
 #else
 				   __x);
 #endif
@@ -421,51 +445,6 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       this->_M_impl._M_finish = __new_finish;
       this->_M_impl._M_end_of_storage = __new_start + __len;
     }
-    }
-
-#if __cplusplus >= 201103L
-  template<typename _Tp, typename _Alloc>
-    template<typename... _Args>
-      void
-      vector<_Tp, _Alloc>::
-      _M_emplace_back_aux(_Args&&... __args)
-      {
-	const size_type __len =
-	  _M_check_len(size_type(1), "vector::_M_emplace_back_aux");
-	pointer __new_start(this->_M_allocate(__len));
-	pointer __new_finish(__new_start);
-	__try
-	  {
-	    _Alloc_traits::construct(this->_M_impl, __new_start + size(),
-				     std::forward<_Args>(__args)...);
-	    __new_finish = pointer();
-
-	    __new_finish
-	      = std::__uninitialized_move_if_noexcept_a
-	      (this->_M_impl._M_start, this->_M_impl._M_finish,
-	       __new_start, _M_get_Tp_allocator());
-
-	    ++__new_finish;
-	  }
-	__catch(...)
-	  {
-	    if (!__new_finish)
-	      _Alloc_traits::destroy(this->_M_impl, __new_start + size());
-	    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;
-      }
-#endif
 
   template<typename _Tp, typename _Alloc>
     void
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 1b46124..39a3f03 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
@@ -223,8 +223,7 @@ test03()
 void
 test04()
 {
-  const X::special expected_ins{ 0, 3, 1, 0, 3, 0 };
-  const X::special expected_emp{ 0, 4, 1, 0, 4, 0 };
+  const X::special expected{ 0, 3, 1, 0, 3, 0 };
   X::special ins, emp;
   {
     std::vector<X> v;
@@ -254,8 +253,8 @@ test04()
     // std::cout << "----\n";
     emp = X::sp;
   }
-  VERIFY( ins == expected_ins );
-  VERIFY( emp == expected_emp );
+  VERIFY( ins == emp );
+  VERIFY( ins == expected );
 }
 
 // insert vs emplace xvalue reallocation