Improve insert/emplace robustness to self insertion

[François Dumont]

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.
>
>
>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: vector_self_insert.patch
Type: text/x-patch
Size: 16375 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20160628/4ccd7a92/attachment.bin>