Resurrect data moves in QList

Use the data moves to readjust the free space in the QList,
which ultimately fixes the out-of-memory issues caused by
cases like:
forever {
  list.prepend(list.back());
  list.removeLast();
}

Task-number: QTBUG-91801
Task-number: QTBUG-91360
Task-number: QTBUG-93019
Pick-to: dev 6.0 6.1
Change-Id: Iacff69cbf36b8b5b176bb2663df635ec972c875c
Reviewed-by: Lars Knoll <lars.knoll@qt.io>

8 files changed, 366 insertions, 100 deletions

diff --git a/src/corelib/text/qbytearray.cpp b/src/corelib/text/qbytearray.cpp
index 6a7d8b2657..a710c6ecba 100644
--- a/src/corelib/text/qbytearray.cpp
+++ b/src/corelib/text/qbytearray.cpp
@@ -1971,8 +1971,7 @@ QByteArray &QByteArray::append(const QByteArray &ba)
 
 QByteArray& QByteArray::append(char ch)
 {
-    if (d->needsDetach() || !d->freeSpaceAtEnd())
-        reallocGrowData(1);
+    d.detachAndGrow(QArrayData::GrowsAtEnd, 1, nullptr, nullptr);
     d->copyAppend(1, ch);
     d.data()[d.size] = '\0';
     return *this;
@@ -2012,12 +2011,8 @@ QByteArray &QByteArray::insert(qsizetype i, QByteArrayView data)
         // defer a call to free() so that it comes after we copied the data from
         // the old memory:
         DataPointer detached{};  // construction is free
-        if (d->needsDetach() || i + size - d->size > d.freeSpaceAtEnd()) {
-            detached = DataPointer::allocateGrow(d, i + size - d->size, Data::GrowsAtEnd);
-            Q_CHECK_PTR(detached.data());
-            detached->copyAppend(d.constBegin(), d.constEnd());
-            d.swap(detached);
-        }
+        d.detachAndGrow(Data::GrowsAtEnd, (i - d.size) + size, &str, &detached);
+        Q_CHECK_PTR(d.data());
         d->copyAppend(i - d->size, ' ');
         d->copyAppend(str, str + size);
         d.data()[d.size] = '\0';
@@ -2094,12 +2089,8 @@ QByteArray &QByteArray::insert(qsizetype i, qsizetype count, char ch)
 
     if (i >= d->size) {
         // handle this specially, as QArrayDataOps::insert() doesn't handle out of bounds positions
-        if (d->needsDetach() || i + count - d->size > d.freeSpaceAtEnd()) {
-            DataPointer detached(DataPointer::allocateGrow(d, i + count - d->size, Data::GrowsAtEnd));
-            Q_CHECK_PTR(detached.data());
-            detached->copyAppend(d.constBegin(), d.constEnd());
-            d.swap(detached);
-        }
+        d.detachAndGrow(Data::GrowsAtEnd, (i - d.size) + count, nullptr, nullptr);
+        Q_CHECK_PTR(d.data());
         d->copyAppend(i - d->size, ' ');
         d->copyAppend(count, ch);
         d.data()[d.size] = '\0';
diff --git a/src/corelib/text/qstring.cpp b/src/corelib/text/qstring.cpp
index a86ba03932..b23c88cbb8 100644
--- a/src/corelib/text/qstring.cpp
+++ b/src/corelib/text/qstring.cpp
@@ -2770,13 +2770,17 @@ QString &QString::insert(qsizetype i, QLatin1String str)
         return *this;
 
     qsizetype len = str.size();
+    qsizetype difference = 0;
     if (Q_UNLIKELY(i > size()))
-        resize(i + len, QLatin1Char(' '));
-    else
-        resize(size() + len);
+        difference = i - size();
+    d.detachAndGrow(Data::GrowsAtEnd, difference + len, nullptr, nullptr);
+    Q_CHECK_PTR(d.data());
+    d->copyAppend(difference, u' ');
+    d.size += len;
 
     ::memmove(d.data() + i + len, d.data() + i, (d.size - i - len) * sizeof(QChar));
     qt_from_latin1(d.data() + i, s, size_t(len));
+    d.data()[d.size] = u'\0';
     return *this;
 }
 
@@ -2797,7 +2801,7 @@ QString& QString::insert(qsizetype i, const QChar *unicode, qsizetype size)
     if (i < 0 || size <= 0)
         return *this;
 
-    const auto s = reinterpret_cast<const char16_t *>(unicode);
+    const char16_t *s = reinterpret_cast<const char16_t *>(unicode);
 
     // handle this specially, as QArrayDataOps::insert() doesn't handle out of
     // bounds positions
@@ -2806,12 +2810,8 @@ QString& QString::insert(qsizetype i, const QChar *unicode, qsizetype size)
         // defer a call to free() so that it comes after we copied the data from
         // the old memory:
         DataPointer detached{};  // construction is free
-        if (d->needsDetach() || i + size - d->size > d.freeSpaceAtEnd()) {
-            detached = DataPointer::allocateGrow(d, i + size - d->size, Data::GrowsAtEnd);
-            Q_CHECK_PTR(detached.data());
-            detached->copyAppend(d.constBegin(), d.constEnd());
-            d.swap(detached);
-        }
+        d.detachAndGrow(Data::GrowsAtEnd, (i - d.size) + size, &s, &detached);
+        Q_CHECK_PTR(d.data());
         d->copyAppend(i - d->size, u' ');
         d->copyAppend(s, s + size);
         d.data()[d.size] = u'\0';
@@ -2867,11 +2867,8 @@ QString &QString::append(const QString &str)
     if (!str.isNull()) {
         if (isNull()) {
             operator=(str);
-        } else {
-            if (d->needsDetach() || str.size() > d->freeSpaceAtEnd())
-                reallocGrowData(str.size());
-            d->copyAppend(str.d.data(), str.d.data() + str.d.size);
-            d.data()[d.size] = '\0';
+        } else if (str.size()) {
+            append(str.constData(), str.size());
         }
     }
     return *this;
@@ -2886,13 +2883,11 @@ QString &QString::append(const QString &str)
 QString &QString::append(const QChar *str, qsizetype len)
 {
     if (str && len > 0) {
-        if (d->needsDetach() || len > d->freeSpaceAtEnd())
-            reallocGrowData(len);
         static_assert(sizeof(QChar) == sizeof(char16_t), "Unexpected difference in sizes");
         // the following should be safe as QChar uses char16_t as underlying data
         const char16_t *char16String = reinterpret_cast<const char16_t *>(str);
-        d->copyAppend(char16String, char16String + len);
-        d.data()[d.size] = '\0';
+        d->growAppend(char16String, char16String + len);
+        d.data()[d.size] = u'\0';
     }
     return *this;
 }
@@ -2905,16 +2900,17 @@ QString &QString::append(const QChar *str, qsizetype len)
 QString &QString::append(QLatin1String str)
 {
     const char *s = str.latin1();
-    if (s) {
-        qsizetype len = str.size();
-        if (d->needsDetach() || str.size() > d->freeSpaceAtEnd())
-            reallocGrowData(len);
-
-        Q_ASSERT(str.size() <= d->freeSpaceAtEnd());
+    const qsizetype len = str.size();
+    if (s && len > 0) {
+        d.detachAndGrow(Data::GrowsAtEnd, len, nullptr, nullptr);
+        Q_CHECK_PTR(d.data());
+        Q_ASSERT(len <= d->freeSpaceAtEnd());
         char16_t *i = d.data() + d.size;
         qt_from_latin1(i, s, size_t(len));
         d.size += len;
         d.data()[d.size] = '\0';
+    } else if (d.isNull() && !str.isNull()) { // special case
+        d = DataPointer::fromRawData(&_empty, 0);
     }
     return *this;
 }
@@ -2952,8 +2948,7 @@ QString &QString::append(QLatin1String str)
 */
 QString &QString::append(QChar ch)
 {
-    if (d->needsDetach() || !d->freeSpaceAtEnd())
-        reallocGrowData(1);
+    d.detachAndGrow(QArrayData::GrowsAtEnd, 1, nullptr, nullptr);
     d->copyAppend(1, ch.unicode());
     d.data()[d.size] = '\0';
     return *this;
diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h
index 0c7703c588..02609a369e 100644
--- a/src/corelib/tools/qarraydataops.h
+++ b/src/corelib/tools/qarraydataops.h
@@ -164,8 +164,9 @@ public:
         typename Data::GrowthPosition pos = Data::GrowsAtEnd;
         if (this->size != 0 && i <= (this->size >> 1))
             pos = Data::GrowsAtBeginning;
+
         DataPointer oldData;
-        this->detachAndGrow(pos, n, &oldData);
+        this->detachAndGrow(pos, n, &data, &oldData);
         Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
                  (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
 
@@ -180,7 +181,8 @@ public:
         typename Data::GrowthPosition pos = Data::GrowsAtEnd;
         if (this->size != 0 && i <= (this->size >> 1))
             pos = Data::GrowsAtBeginning;
-        this->detachAndGrow(pos, n);
+
+        this->detachAndGrow(pos, n, nullptr, nullptr);
         Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
                  (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
 
@@ -210,10 +212,8 @@ public:
         typename QArrayData::GrowthPosition pos = QArrayData::GrowsAtEnd;
         if (this->size != 0 && i <= (this->size >> 1))
             pos = QArrayData::GrowsAtBeginning;
-        if (detach ||
-            (pos == QArrayData::GrowsAtBeginning && !this->freeSpaceAtBegin()) ||
-            (pos == QArrayData::GrowsAtEnd && !this->freeSpaceAtEnd()))
-            this->reallocateAndGrow(pos, 1);
+
+        this->detachAndGrow(pos, 1, nullptr, nullptr);
 
         T *where = createHole(pos, i, 1);
         new (where) T(std::move(tmp));
@@ -547,8 +547,9 @@ public:
         typename Data::GrowthPosition pos = Data::GrowsAtEnd;
         if (this->size != 0 && i <= (this->size >> 1))
             pos = Data::GrowsAtBeginning;
+
         DataPointer oldData;
-        this->detachAndGrow(pos, n, &oldData);
+        this->detachAndGrow(pos, n, &data, &oldData);
         Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
                  (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
 
@@ -562,7 +563,8 @@ public:
         typename Data::GrowthPosition pos = Data::GrowsAtEnd;
         if (this->size != 0 && i <= (this->size >> 1))
             pos = Data::GrowsAtBeginning;
-        this->detachAndGrow(pos, n);
+
+        this->detachAndGrow(pos, n, nullptr, nullptr);
         Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
                  (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
 
@@ -590,10 +592,8 @@ public:
         typename QArrayData::GrowthPosition pos = QArrayData::GrowsAtEnd;
         if (this->size != 0 && i <= (this->size >> 1))
             pos = QArrayData::GrowsAtBeginning;
-        if (detach ||
-            (pos == QArrayData::GrowsAtBeginning && !this->freeSpaceAtBegin()) ||
-            (pos == QArrayData::GrowsAtEnd && !this->freeSpaceAtEnd()))
-            this->reallocateAndGrow(pos, 1);
+
+        this->detachAndGrow(pos, 1, nullptr, nullptr);
 
         Inserter(this, pos).insertOne(i, std::move(tmp));
     }
@@ -773,8 +773,9 @@ public:
         typename Data::GrowthPosition pos = Data::GrowsAtEnd;
         if (this->size != 0 && i <= (this->size >> 1))
             pos = Data::GrowsAtBeginning;
+
         DataPointer oldData;
-        this->detachAndGrow(pos, n, &oldData);
+        this->detachAndGrow(pos, n, &data, &oldData);
         Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
                  (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
 
@@ -788,7 +789,8 @@ public:
         typename Data::GrowthPosition pos = Data::GrowsAtEnd;
         if (this->size != 0 && i <= (this->size >> 1))
             pos = Data::GrowsAtBeginning;
-        this->detachAndGrow(pos, n);
+
+        this->detachAndGrow(pos, n, nullptr, nullptr);
         Q_ASSERT((pos == Data::GrowsAtBeginning && this->freeSpaceAtBegin() >= n) ||
                  (pos == Data::GrowsAtEnd && this->freeSpaceAtEnd() >= n));
 
@@ -816,10 +818,8 @@ public:
         typename QArrayData::GrowthPosition pos = QArrayData::GrowsAtEnd;
         if (this->size != 0 && i <= (this->size >> 1))
             pos = QArrayData::GrowsAtBeginning;
-        if (detach ||
-            (pos == QArrayData::GrowsAtBeginning && !this->freeSpaceAtBegin()) ||
-            (pos == QArrayData::GrowsAtEnd && !this->freeSpaceAtEnd()))
-            this->reallocateAndGrow(pos, 1);
+
+        this->detachAndGrow(pos, 1, nullptr, nullptr);
 
         Inserter(this, pos).insertOne(i, std::move(tmp));
     }
@@ -913,6 +913,26 @@ public:
             ++this->size;
         }
     }
+
+    // slightly higher level API than copyAppend() that also preallocates space
+    void growAppend(const T *b, const T *e)
+    {
+        if (b == e)
+            return;
+        Q_ASSERT(b < e);
+        const qsizetype n = e - b;
+        DataPointer old;
+
+        // points into range:
+        if (QtPrivate::q_points_into_range(b, this->begin(), this->end())) {
+            this->detachAndGrow(QArrayData::GrowsAtEnd, n, &b, &old);
+        } else {
+            this->detachAndGrow(QArrayData::GrowsAtEnd, n, nullptr, nullptr);
+        }
+        Q_ASSERT(this->freeSpaceAtEnd() >= n);
+        // b might be updated so use [b, n)
+        this->copyAppend(b, b + n);
+    }
 };
 
 } // namespace QtPrivate
diff --git a/src/corelib/tools/qarraydatapointer.h b/src/corelib/tools/qarraydatapointer.h
index f6aabeee65..af60a105fe 100644
--- a/src/corelib/tools/qarraydatapointer.h
+++ b/src/corelib/tools/qarraydatapointer.h
@@ -166,19 +166,56 @@ public:
             reallocateAndGrow(QArrayData::GrowsAtEnd, 0, old);
     }
 
-    // pass in a pointer to a default constructed QADP, to keep it alive beyond the detach() call
-    void detachAndGrow(QArrayData::GrowthPosition where, qsizetype n, QArrayDataPointer *old = nullptr)
+    /*! \internal
+
+        Detaches this (optionally) and grows to accommodate the free space for
+        \a n elements at the required side. The side is determined from \a pos.
+
+        \a data pointer can be provided when the caller knows that \a data
+        points into range [this->begin(), this->end()). In case it is, *data
+        would be updated so that it continues to point to the element it was
+        pointing to before the data move. if \a data does not point into range,
+        one can/should pass \c nullptr.
+
+        Similarly to \a data, \a old, pointer to a default-constructed QADP, can
+        be provided when the caller expects to e.g. copy the data from this to
+        itself:
+        \code
+        QList<T> list(5);
+        qsizetype pos = getArbitraryPos();
+        list.insert(pos, list.begin(), list.end());
+        \endcode
+
+        The default rule would be: \a data and \a old must either both be valid
+        pointers, or both equal to \c nullptr.
+    */
+    void detachAndGrow(QArrayData::GrowthPosition where, qsizetype n, const T **data,
+                       QArrayDataPointer *old)
     {
-        if (!needsDetach()) {
-            if (!n ||
-                (where == QArrayData::GrowsAtBeginning && freeSpaceAtBegin() >= n) ||
-                (where == QArrayData::GrowsAtEnd && freeSpaceAtEnd() >= n))
+        const bool detach = needsDetach();
+        bool readjusted = false;
+        if (!detach) {
+            if (!n || (where == QArrayData::GrowsAtBeginning && freeSpaceAtBegin() >= n)
+                || (where == QArrayData::GrowsAtEnd && freeSpaceAtEnd() >= n))
                 return;
+            readjusted = tryReadjustFreeSpace(where, n, data);
+            Q_ASSERT(!readjusted
+                     || (where == QArrayData::GrowsAtBeginning && freeSpaceAtBegin() >= n)
+                     || (where == QArrayData::GrowsAtEnd && freeSpaceAtEnd() >= n));
         }
-        reallocateAndGrow(where, n, old);
+
+        if (!readjusted)
+            reallocateAndGrow(where, n, old);
     }
 
-    Q_NEVER_INLINE void reallocateAndGrow(QArrayData::GrowthPosition where, qsizetype n, QArrayDataPointer *old = nullptr)
+    /*! \internal
+
+        Reallocates to accommodate the free space for \a n elements at the
+        required side. The side is determined from \a pos. Might also shrink
+        when n < 0.
+    */
+    Q_NEVER_INLINE void reallocateAndGrow(QArrayData::GrowthPosition where, qsizetype n,
+                                          QArrayDataPointer *old = nullptr)
     {
         if constexpr (QTypeInfo<T>::isRelocatable && alignof(T) <= alignof(std::max_align_t)) {
             if (where == QArrayData::GrowsAtEnd && !old && !needsDetach() && n > 0) {
@@ -188,9 +225,10 @@ public:
         }
 
         QArrayDataPointer dp(allocateGrow(*this, n, where));
+        if (n > 0)
+            Q_CHECK_PTR(dp.data());
         if (where == QArrayData::GrowsAtBeginning) {
             Q_ASSERT(dp.ptr);
-            dp.ptr += n;
             Q_ASSERT(dp.freeSpaceAtBegin() >= n);
         } else {
             Q_ASSERT(dp.freeSpaceAtEnd() >= n);
@@ -211,6 +249,77 @@ public:
             old->swap(dp);
     }
 
+    /*! \internal
+
+        Attempts to relocate [begin(), end()) to accommodate the free space for
+        \a n elements at the required side. The side is determined from \a pos.
+
+        Returns \c true if the internal data is moved. Returns \c false when
+        there is no point in moving the data or the move is impossible. If \c
+        false is returned, it is the responsibility of the caller to figure out
+        how to accommodate the free space for \a n elements at \a pos.
+
+        This function expects that certain preconditions are met, e.g. the
+        detach is not needed, n > 0 and so on. This is intentional to reduce the
+        number of if-statements when the caller knows that preconditions would
+        be satisfied.
+
+        \sa reallocateAndGrow
+    */
+    bool tryReadjustFreeSpace(QArrayData::GrowthPosition pos, qsizetype n, const T **data = nullptr)
+    {
+        Q_ASSERT(!this->needsDetach());
+        Q_ASSERT(n > 0);
+        Q_ASSERT((pos == QArrayData::GrowsAtEnd && this->freeSpaceAtEnd() < n)
+                 || (pos == QArrayData::GrowsAtBeginning && this->freeSpaceAtBegin() < n));
+
+        const qsizetype capacity = this->constAllocatedCapacity();
+        const qsizetype freeAtBegin = this->freeSpaceAtBegin();
+        const qsizetype freeAtEnd = this->freeSpaceAtEnd();
+
+        qsizetype dataStartOffset = 0;
+        // algorithm:
+        //   a. GrowsAtEnd: relocate if space at begin AND size < (capacity * 2) / 3
+        //      [all goes to free space at end]:
+        //      new free space at begin = 0
+        //
+        //   b. GrowsAtBeginning: relocate if space at end AND size < capacity / 3
+        //      [balance the free space]:
+        //      new free space at begin = n + (total free space - n) / 2
+        if (pos == QArrayData::GrowsAtEnd && freeAtBegin >= n
+            && ((3 * this->size) < (2 * capacity))) {
+            // dataStartOffset = 0; - done in declaration
+        } else if (pos == QArrayData::GrowsAtBeginning && freeAtEnd >= n
+                   && ((3 * this->size) < capacity)) {
+            // total free space == capacity - size
+            dataStartOffset = n + qMax(0, (capacity - this->size - n) / 2);
+        } else {
+            // nothing to do otherwise
+            return false;
+        }
+
+        relocate(dataStartOffset - freeAtBegin, data);
+
+        Q_ASSERT((pos == QArrayData::GrowsAtEnd && this->freeSpaceAtEnd() >= n)
+                 || (pos == QArrayData::GrowsAtBeginning && this->freeSpaceAtBegin() >= n));
+        return true;
+    }
+
+    /*! \internal
+
+        Relocates [begin(), end()) by \a offset and updates \a data if it is not
+        \c nullptr and points into [begin(), end()).
+    */
+    void relocate(qsizetype offset, const T **data = nullptr)
+    {
+        T *res = this->ptr + offset;
+        QtPrivate::q_relocate_overlap_n(this->ptr, this->size, res);
+        // first update data pointer, then this->ptr
+        if (data && QtPrivate::q_points_into_range(*data, this->begin(), this->end()))
+            *data += offset;
+        this->ptr = res;
+    }
+
     // forwards from QArrayData
     qsizetype allocatedCapacity() noexcept { return d ? d->allocatedCapacity() : 0; }
     qsizetype constAllocatedCapacity() const noexcept { return d ? d->constAllocatedCapacity() : 0; }
@@ -262,10 +371,9 @@ public:
 
         // Idea: * when growing backwards, adjust pointer to prepare free space at the beginning
         //       * when growing forward, adjust by the previous data pointer offset
-
-        // TODO: what's with CapacityReserved?
-        dataPtr += (position == QArrayData::GrowsAtBeginning) ? qMax(0, (header->alloc - from.size - n) / 2)
-                                                    : from.freeSpaceAtBegin();
+        dataPtr += (position == QArrayData::GrowsAtBeginning)
+                ? n + qMax(0, (header->alloc - from.size - n) / 2)
+                : from.freeSpaceAtBegin();
         header->flags = from.flags();
         return QArrayDataPointer(header, dataPtr);
     }
diff --git a/src/corelib/tools/qcontainertools_impl.h b/src/corelib/tools/qcontainertools_impl.h
index 465ea5c544..2053de6408 100644
--- a/src/corelib/tools/qcontainertools_impl.h
+++ b/src/corelib/tools/qcontainertools_impl.h
@@ -53,6 +53,7 @@
 #include <cstring>
 #include <iterator>
 #include <memory>
+#include <algorithm>
 
 QT_BEGIN_NAMESPACE
 
@@ -88,6 +89,116 @@ void q_uninitialized_relocate_n(T* first, N n, T* out)
     }
 }
 
+template<typename iterator, typename N>
+void q_relocate_overlap_n_left_move(iterator first, N n, iterator d_first)
+{
+    // requires: [first, n) is a valid range
+    // requires: d_first + n is reachable from d_first
+    // requires: iterator is at least a random access iterator
+    // requires: value_type(iterator) has a non-throwing destructor
+
+    Q_ASSERT(n);
+    Q_ASSERT(d_first < first); // only allow moves to the "left"
+    using T = typename std::iterator_traits<iterator>::value_type;
+
+    // Watches passed iterator. Unless commit() is called, all the elements that
+    // the watched iterator passes through are deleted at the end of object
+    // lifetime. freeze() could be used to stop watching the passed iterator and
+    // remain at current place.
+    //
+    // requires: the iterator is expected to always point to an invalid object
+    //           (to uninitialized memory)
+    struct Destructor
+    {
+        iterator *iter;
+        iterator end;
+        iterator intermediate;
+
+        Destructor(iterator &it) noexcept : iter(std::addressof(it)), end(it) { }
+        void commit() noexcept { iter = std::addressof(end); }
+        void freeze() noexcept
+        {
+            intermediate = *iter;
+            iter = std::addressof(intermediate);
+        }
+        ~Destructor() noexcept
+        {
+            for (const int step = *iter < end ? 1 : -1; *iter != end;) {
+                std::advance(*iter, step);
+                (*iter)->~T();
+            }
+        }
+    } destroyer(d_first);
+
+    const iterator d_last = d_first + n;
+    // Note: use pair and explicitly copy iterators from it to prevent
+    // accidental reference semantics instead of copy. equivalent to:
+    //
+    // auto [overlapBegin, overlapEnd] = std::minmax(d_last, first);
+    auto pair = std::minmax(d_last, first);
+
+    // overlap area between [d_first, d_first + n) and [first, first + n) or an
+    // uninitialized memory area between the two ranges
+    iterator overlapBegin = pair.first;
+    iterator overlapEnd = pair.second;
+
+    // move construct elements in uninitialized region
+    while (d_first != overlapBegin) {
+        // account for std::reverse_iterator, cannot use new(d_first) directly
+        new (std::addressof(*d_first)) T(std::move_if_noexcept(*first));
+        ++d_first;
+        ++first;
+    }
+
+    // cannot commit but have to stop - there might be an overlap region
+    // which we don't want to delete (because it's part of existing data)
+    destroyer.freeze();
+
+    // move assign elements in overlap region
+    while (d_first != d_last) {
+        *d_first = std::move_if_noexcept(*first);
+        ++d_first;
+        ++first;
+    }
+
+    Q_ASSERT(d_first == destroyer.end + n);
+    destroyer.commit(); // can commit here as ~T() below does not throw
+
+    while (first != overlapEnd)
+        (--first)->~T();
+}
+
+/*!
+  \internal
+
+  Relocates a range [first, n) to [d_first, n) taking care of potential memory
+  overlaps. This is a generic equivalent of memmove.
+
+  If an exception is thrown during the relocation, all the relocated elements
+  are destroyed and [first, n) may contain valid but unspecified values,
+  including moved-from values (basic exception safety).
+*/
+template<typename T, typename N>
+void q_relocate_overlap_n(T *first, N n, T *d_first)
+{
+    static_assert(std::is_nothrow_destructible_v<T>,
+                  "This algorithm requires that T has a non-throwing destructor");
+
+    if (n == N(0) || first == d_first || first == nullptr || d_first == nullptr)
+        return;
+
+    if constexpr (QTypeInfo<T>::isRelocatable) {
+        std::memmove(static_cast<void *>(d_first), static_cast<const void *>(first), n * sizeof(T));
+    } else { // generic version has to be used
+        if (d_first < first) {
+            q_relocate_overlap_n_left_move(first, n, d_first);
+        } else { // first < d_first
+            auto rfirst = std::make_reverse_iterator(first + n);
+            auto rd_first = std::make_reverse_iterator(d_first + n);
+            q_relocate_overlap_n_left_move(rfirst, n, rd_first);
+        }
+    }
+}
 
 template <typename Iterator>
 using IfIsInputIterator = typename std::enable_if<
diff --git a/src/corelib/tools/qlist.h b/src/corelib/tools/qlist.h
index b50cd9090f..2811688e4b 100644
--- a/src/corelib/tools/qlist.h
+++ b/src/corelib/tools/qlist.h
@@ -663,9 +663,10 @@ inline void QList<T>::resize_internal(qsizetype newSize)
     Q_ASSERT(newSize >= 0);
 
     if (d->needsDetach() || newSize > capacity() - d.freeSpaceAtBegin()) {
-        d.reallocateAndGrow(QArrayData::GrowsAtEnd, newSize - d.size);
-    } else if (newSize < size())
+        d.detachAndGrow(QArrayData::GrowsAtEnd, newSize - d.size, nullptr, nullptr);
+    } else if (newSize < size()) {
         d->truncate(newSize);
+    }
 }
 
 template <typename T>
@@ -748,12 +749,7 @@ inline T QList<T>::value(qsizetype i, parameter_type defaultValue) const
 template <typename T>
 inline void QList<T>::append(const_iterator i1, const_iterator i2)
 {
-    if (i1 == i2)
-        return;
-    const auto distance = std::distance(i1, i2);
-    DataPointer oldData;
-    d.detachAndGrow(QArrayData::GrowsAtEnd, distance, &oldData);
-    d->copyAppend(i1, i2);
+    d->growAppend(i1, i2);
 }
 
 template <typename T>
@@ -765,7 +761,9 @@ inline void QList<T>::append(QList<T> &&other)
     if (other.d->needsDetach() || !std::is_nothrow_move_constructible_v<T>)
         return append(other);
 
-    d.detachAndGrow(QArrayData::GrowsAtEnd, other.size());
+    // due to precondition &other != this, we can unconditionally modify 'this'
+    d.detachAndGrow(QArrayData::GrowsAtEnd, other.size(), nullptr, nullptr);
+    Q_ASSERT(d.freeSpaceAtEnd() >= other.size());
     d->moveAppend(other.begin(), other.end());
 }
 
@@ -783,8 +781,9 @@ inline typename QList<T>::iterator
 QList<T>::insert(qsizetype i, qsizetype n, parameter_type t)
 {
     Q_ASSERT_X(size_t(i) <= size_t(d->size), "QList<T>::insert", "index out of range");
-
-    d->insert(i, n, t);
+    Q_ASSERT_X(n >= 0, "QList::insert", "invalid count");
+    if (Q_LIKELY(n))
+        d->insert(i, n, t);
     return d.begin() + i;
 }
 
diff --git a/tests/auto/corelib/tools/qarraydata/simplevector.h b/tests/auto/corelib/tools/qarraydata/simplevector.h
index 747af3d422..1fc5e9b8e1 100644
--- a/tests/auto/corelib/tools/qarraydata/simplevector.h
+++ b/tests/auto/corelib/tools/qarraydata/simplevector.h
@@ -209,22 +209,7 @@ public:
         d->insert(0, first, last - first);
     }
 
-    void append(const_iterator first, const_iterator last)
-    {
-        if (first == last)
-            return;
-
-        auto requiredSize = qsizetype(last - first);
-        if (d->needsDetach() || d.freeSpaceAtEnd() < requiredSize) {
-            DataPointer oldData;
-            d.reallocateAndGrow(QArrayData::GrowsAtEnd, requiredSize, &oldData);
-
-            d->copyAppend(first, last);
-            return;
-        }
-
-        d->copyAppend(first, last);
-    }
+    void append(const_iterator first, const_iterator last) { d->growAppend(first, last); }
 
     void insert(int position, const_iterator first, const_iterator last)
     {
diff --git a/tests/auto/corelib/tools/qlist/tst_qlist.cpp b/tests/auto/corelib/tools/qlist/tst_qlist.cpp
index 80adb0f6a1..14c679562f 100644
--- a/tests/auto/corelib/tools/qlist/tst_qlist.cpp
+++ b/tests/auto/corelib/tools/qlist/tst_qlist.cpp
@@ -348,8 +348,13 @@ private slots:
     void emplaceWithElementFromTheSameContainer_data();
 
     void fromReadOnlyData() const;
-
     void qtbug_90359() const;
+    void reinsertToBeginInt_qtbug91360() const { reinsertToBegin<int>(); }
+    void reinsertToBeginMovable_qtbug91360() const { reinsertToBegin<Movable>(); }
+    void reinsertToBeginCustom_qtbug91360() const { reinsertToBegin<Custom>(); }
+    void reinsertToEndInt_qtbug91360() const { reinsertToEnd<int>(); }
+    void reinsertToEndMovable_qtbug91360() const { reinsertToEnd<Movable>(); }
+    void reinsertToEndCustom_qtbug91360() const { reinsertToEnd<Custom>(); }
 
 private:
     template<typename T> void copyConstructor() const;
@@ -379,6 +384,10 @@ private:
     template<typename T> void detachThreadSafety() const;
     template<typename T> void emplaceImpl() const;
     template<typename T> void emplaceConsistentWithStdVectorImpl() const;
+    template<typename T>
+    void reinsertToBegin() const;
+    template<typename T>
+    void reinsertToEnd() const;
 };
 
 
@@ -3265,5 +3274,53 @@ void tst_QList::qtbug_90359() const
     QCOMPARE(actual, expected);
 }
 
+template<typename T>
+void tst_QList::reinsertToBegin() const
+{
+    QList<T> list(1);
+    const auto reinsert = [](QList<T> &list) {
+        list.prepend(list.back());
+        list.removeLast();
+    };
+
+    // this constant is big enough for the QList to stop reallocating, after
+    // all, size is always less than 3
+    const int maxIters = 128;
+    for (int i = 0; i < maxIters; ++i) {
+        reinsert(list);
+    }
+
+    // if QList continues to grow, it's an error
+    qsizetype capacity = list.capacity();
+    for (int i = 0, enoughIters = int(capacity) * 2; i < enoughIters; ++i) {
+        reinsert(list);
+        QCOMPARE(capacity, list.capacity());
+    }
+}
+
+template<typename T>
+void tst_QList::reinsertToEnd() const
+{
+    QList<T> list(1);
+    const auto reinsert = [](QList<T> &list) {
+        list.append(list.front());
+        list.removeFirst();
+    };
+
+    // this constant is big enough for the QList to stop reallocating, after
+    // all, size is always less than 3
+    const int maxIters = 128;
+    for (int i = 0; i < maxIters; ++i) {
+        reinsert(list);
+    }
+
+    // if QList continues to grow, it's an error
+    qsizetype capacity = list.capacity();
+    for (int i = 0, enoughIters = int(capacity) * 2; i < enoughIters; ++i) {
+        reinsert(list);
+        QCOMPARE(capacity, list.capacity());
+    }
+}
+
 QTEST_MAIN(tst_QList)
 #include "tst_qlist.moc"