QVarLengthArray: fix UBs in emplace()/insert() ([basic.life], broken class invariant)

There are two problems in emplace_impl() (the same code exists as
rvalue insert() since 5.10):

First, the old code updated size() at the end of the function.

However, if, after constructing the new end element, one of the
subsequent move-assignments fail (throws), then the class invariant
that size() be the number of alive elements in the container is
broken, with the immediate consequence that the QVLA dtor would not
destroy this element, but surely other unpleasantness (UB) that the
C++ lifetime rules decide to throw our way.

Similarly, in the trivially-relocatable case, the memmove() starts the
life-time of the new end object, so if the following placement new
fails, we're in the same situation.

The latter case is worse, though, since here we leave *b in some weird
zombie state: the memmove() effectively ended its lifetime in the
sense that one mustn't call the destructor on the source object after
trivial relocation, but C++ doesn't agree and QVLA's dtor will happily
call b->~T() as part of its cleanup.

The other ugly thing is that we're using placement new into an object
that C++ says is still alive. QString is trivially relocatable, but
not trivially copyable, so we can't end a QString's lifetime by
placement-new'ing a new QString instance into it without first having
ended the old object's lifetime.

The fix for both of these is, fortunately, the same: It's a rotate!™

By using emplace_back() + std::rotate(), we always place the new
object in a spot that didn't contain an alive object (in the C++
sense) before, we always update the size() right after doing so,
maintaining that invariant, and we then rotate() it into place, which
doesn't leave zombie objects around.

std::rotate() is such a fundamental algorithm that we should trust the
STL implementors to have optimized it well:
https://stackoverflow.com/questions/21160875/why-is-stdrotate-so-fast

We know we can do better only for trivially-relocatable, but
non-trivially-copyable types (ex: QString), so in order to not lose
the memmove() optimization, we now fall back to std::rotate on raw
memory for that case.

Amends dd58ddd5d97f0663d5fafb7e81bff4fc7db13ba7.

Manual conflict resolutions:
 - no q20::construct_at() in 6.4

Change-Id: Iacce4488ca649502861e0ed4e084c9fad38cab47
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>
Reviewed-by: Fabian Kosmale <fabian.kosmale@qt.io>
(cherry picked from commit e24df8bc726d12e80f3f1d14834f9305586fcc98)
Reviewed-by: Qt CI Bot <qt_ci_bot@qt-project.org>
Reviewed-by: Mårten Nordheim <marten.nordheim@qt.io>

1 files changed, 9 insertions, 21 deletions

diff --git a/src/corelib/tools/qvarlengtharray.h b/src/corelib/tools/qvarlengtharray.h
index 6b3c90c371..2c88fbef2b 100644
--- a/src/corelib/tools/qvarlengtharray.h
+++ b/src/corelib/tools/qvarlengtharray.h
@@ -849,29 +849,17 @@ Q_OUTOFLINE_TEMPLATE auto QVLABase<T>::emplace_impl(qsizetype prealloc, void *ar
     Q_ASSERT(size() <= capacity());
     Q_ASSERT(capacity() > 0);
 
-    qsizetype offset = qsizetype(before - cbegin());
-    if (size() == capacity())
-        growBy(prealloc, array, 1);
-    if constexpr (!QTypeInfo<T>::isRelocatable) {
-        T *b = begin() + offset;
-        T *i = end();
-        T *j = i + 1;
-        // The new end-element needs to be constructed, the rest must be move assigned
-        if (i != b) {
-            new (--j) T(std::move(*--i));
-            while (i != b)
-                *--j = std::move(*--i);
-            *b = T(std::forward<Args>(args)...);
-        } else {
-            new (b) T(std::forward<Args>(args)...);
-        }
+    const qsizetype offset = qsizetype(before - cbegin());
+    emplace_back_impl(prealloc, array, std::forward<Args>(args)...);
+    const auto b = begin() + offset;
+    const auto e = end();
+    if constexpr (QTypeInfo<T>::isRelocatable) {
+        auto cast = [](T *p) { return reinterpret_cast<uchar*>(p); };
+        std::rotate(cast(b), cast(e - 1), cast(e));
     } else {
-        T *b = begin() + offset;
-        memmove(static_cast<void *>(b + 1), static_cast<const void *>(b), (size() - offset) * sizeof(T));
-        new (b) T(std::forward<Args>(args)...);
+        std::rotate(b, e - 1, e);
     }
-    this->s += 1;
-    return data() + offset;
+    return b;
 }
 
 template <class T>