Improve insert/emplace robustness to self insertion

[François Dumont]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: vector_w.patch
Type: text/x-patch
Size: 8799 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20160706/fce7cfa1/attachment.bin>