ADT: Fix reference invalidation in SmallVector::emplace_back and assign(N,V)
authorDuncan P. N. Exon Smith <dexonsmith@apple.com>
Fri, 15 Jan 2021 00:40:41 +0000 (16:40 -0800)
committerDuncan P. N. Exon Smith <dexonsmith@apple.com>
Thu, 21 Jan 2021 20:11:41 +0000 (12:11 -0800)
commitd7ff0036463fbf049a240fe3792fcfcd8081c41e
treeeb68edcc6262b5263ed1d12517102bcfa09dedc8
parent4ab0f51a7518332b8b7691915b5fdad4c1ed045f
ADT: Fix reference invalidation in SmallVector::emplace_back and assign(N,V)

This fixes the final (I think?) reference invalidation in `SmallVector`
that we need to fix to align with `std::vector`. (There is still some
left in the range insert / append / assign, but the standard calls that
UB for `std::vector` so I think we don't care?)

For POD-like types, reimplement `emplace_back()` in terms of
`push_back()`, taking a copy even for large `T` rather than lose the
realloc optimization in `grow_pod()`.

For other types, split the grow operation in three and construct the new
element in the middle.

- `mallocForGrow()` calculates the new capacity and returns the result
  of `safe_malloc()`. We only need a single definition per
  `SmallVectorBase` so this is defined in SmallVector.cpp to avoid code
  size bloat. Moving this part of non-POD grow to the source file also
  allows the logic to be easily shared with `grow_pod`, and
  `report_size_overflow()` and `report_at_maximum_capacity()` can move
  there too.
- `moveElementsForGrow()` moves elements from the old to the new
  allocation.
- `takeAllocationForGrow()` frees the old allocation and saves the
  new allocation and capacity .

`SmallVector:assign(size_type, const T&)` also uses the split-grow
operations for non-POD, but it also has a semantic change when not
growing. Previously, assign would start with `clear()`, and so the old
elements were destructed and all elements of the new vector were
copy-constructed (potentially invalidating references). The new
implementation skips destruction and uses copy-assignment for the prefix
of the new vector that fits. The new semantics match what libc++ does
for `std::vector::assign()`.

Note that the following is another possible implementation:
```
  void assign(size_type NumElts, ValueParamT Elt) {
    std::fill_n(this->begin(), std::min(NumElts, this->size()), Elt);
    this->resize(NumElts, Elt);
  }
```
The downside of this simpler implementation is that if the vector has to
grow there will be `size()` redundant copy operations.

(I had planned on splitting this patch up into three for committing
(after getting performance numbers / initial review), but I've realized
that if this does for some reason need to be reverted we'll probably
want to revert the whole package...)

Differential Revision: https://reviews.llvm.org/D94739
llvm/include/llvm/ADT/SmallVector.h
llvm/lib/Support/SmallVector.cpp
llvm/unittests/ADT/SmallVectorTest.cpp