InlinedVector doesn't protect against method arguments aliasing the vector

[stephan-tolksdorf]

It seems that the append, insert, emplace and assign methods of InlinedVector don't protect against arguments being invalidated when the capacity of the vector has to be increased or existing values have to be moved. For example, vector.insert(vector.begin(), vector[0]) is currently never safe, and vector.push_back(vector[0]) is not safe if vector.size() == vector.capacity(). If this is the intended behaviour, it should probably be documented, as it deviates from what the C++ standard requires for the standard library (20.5.4.9.1.3).

Similarly, InlinedVector::operator=(const InlinedVector&) will call std::copy(vector.begin(), vector.end(), vector.begin()) for self-assignments, which technically violates the precondition for the output iterator argument passed to copy (28.6.1.1).

Even ignoring issue #32, InlinedVector currently can't provide the same strong exception guarantee that the C++ standard requires (26.2.1.11) for some basic container operations like push_back, because if the construction of a new element throws an exception after the capacity of the vector has been increased, the vector isn't left in the same state as before the call (since the capacity remains changed and all pointers into the vector remain invalidated). This only really matters if you intend to support arguments that could be invalidated by capacity changes, but it may be worth documenting in any case.

[JonathanDCohen]

I'll take a look at the aliasing issues.

For exception safety, the short story is that we know InlinedVector isn't exception safe. I'm currently writing tooling for us to thoroughly test our classes for exception safety. Once we have that, we will start updating all of our types which need to worry about exceptions accordingly.

I would guess that InlinedVector will have slightly weaker guarantees than std::vector, partly for the reasons you outlined. Our current thought is that we will be going for basic exception safety everywhere, and strong exception safety where reasonable and where it won't affect performance.

[JonathanDCohen]

I took a look at this today. Insert() indeed has a bug, and it is fixed in an internal change which will be upstreamed once accepted. Similarly with operator=.

I don't see the issue with push_back. push_back calls emplace_back, which if we need to grow, calls GrowAndEmplaceBack. GrowAndEmplaceBack first allocates a new buffer, then constructs the new object into it, then moves everything else into the new buffer, so it should be safe.

[stephan-tolksdorf]

You're right, I was mistaken about push_back, sorry.

The insert(const_iterator position, size_type n, const value_type& v) and insert(const_iterator position, InputIterator first, InputIterator last) (for forward iterators) overloads also suffer from this issue, but you've probably seen that too. Making the latter completely safe would hurt performance, but maybe an assert that checks e.g. the address of the first element in the range would be worth the overhead.

[JonathanDCohen]

The two-iterator insert, we won't support aliasing, just like in std::vector (#4 in http://en.cppreference.com/w/cpp/container/vector/insert).

The iterator-count overload is also being fixed, yes :)

[JonathanDCohen]

This is fixed in 5fcbe86