Separate exception safety primitives from operations

Refactored certain bits of qarraydataops.h: picked exception-related
building blocks and put them into one place, (somewhat) documented
the usage, added tests

Personally, the existing code seemed rather complicated to analyze
(and do mental experiments for corner cases), especially when staring
at the whole thing for a while or "returning back" from some other work
and I still have my doubts that everything works correctly. Testing the
building blocks that are used should:
a) increase trust into existing code (provided the usage is correct)
b) give more use cases of how to use the building blocks, which in turn
   would allow to compare and contrast tests vs implementation

Task-number: QTBUG-84320
Change-Id: I313a1d1817577507fe07a5b9b7d2c90b0969b490
Reviewed-by: Thiago Macieira <thiago.macieira@intel.com>

1 files changed, 189 insertions, 195 deletions

diff --git a/src/corelib/tools/qarraydataops.h b/src/corelib/tools/qarraydataops.h
index bc5f3ac52a..369a8ae574 100644
--- a/src/corelib/tools/qarraydataops.h
+++ b/src/corelib/tools/qarraydataops.h
@@ -1,6 +1,6 @@
 /****************************************************************************
 **
-** Copyright (C) 2016 The Qt Company Ltd.
+** Copyright (C) 2020 The Qt Company Ltd.
 ** Copyright (C) 2016 Intel Corporation.
 ** Contact: https://www.qt.io/licensing/
 **
@@ -46,6 +46,8 @@
 
 #include <new>
 #include <string.h>
+#include <utility>
+#include <iterator>
 
 QT_BEGIN_NAMESPACE
 
@@ -53,6 +55,166 @@ template <class T> struct QArrayDataPointer;
 
 namespace QtPrivate {
 
+/*!
+    \internal
+
+    This class provides basic building blocks to do reversible operations. This
+    in turn allows to reason about exception safety under certain conditions.
+
+    This class is not part of the Qt API. It exists for the convenience of other
+    Qt classes.  This class may change from version to version without notice,
+    or even be removed.
+
+    We mean it.
+ */
+template<typename T>
+struct QArrayExceptionSafetyPrimitives
+{
+    using parameter_type = typename QArrayDataPointer<T>::parameter_type;
+    using iterator = typename QArrayDataPointer<T>::iterator;
+
+    // Constructs a range of elements at the specified position. If an exception
+    // is thrown during construction, already constructed elements are
+    // destroyed. By design, only one function (create/copy/clone/move) and only
+    // once is supposed to be called per class instance.
+    struct Constructor
+    {
+        T *const where;
+        size_t n = 0;
+
+        template<typename It>
+        using iterator_copy_value = decltype(*std::declval<It>());
+        template<typename It>
+        using iterator_move_value = decltype(std::move(*std::declval<It>()));
+
+        Constructor(T *w) noexcept : where(w) {}
+        qsizetype create(size_t size) noexcept(std::is_nothrow_default_constructible_v<T>)
+        {
+            n = 0;
+            while (n != size) {
+                new (where + n) T;
+                ++n;
+            }
+            return qsizetype(std::exchange(n, 0));
+        }
+        template<typename ForwardIt>
+        qsizetype copy(ForwardIt first, ForwardIt last)
+            noexcept(std::is_nothrow_constructible_v<T, iterator_copy_value<ForwardIt>>)
+        {
+            n = 0;
+            for (; first != last; ++first) {
+                new (where + n) T(*first);
+                ++n;
+            }
+            return qsizetype(std::exchange(n, 0));
+        }
+        qsizetype clone(size_t size, parameter_type t)
+            noexcept(std::is_nothrow_constructible_v<T, parameter_type>)
+        {
+            n = 0;
+            while (n != size) {
+                new (where + n) T(t);
+                ++n;
+            }
+            return qsizetype(std::exchange(n, 0));
+        }
+        template<typename ForwardIt>
+        qsizetype move(ForwardIt first, ForwardIt last)
+            noexcept(std::is_nothrow_constructible_v<T, iterator_move_value<ForwardIt>>)
+        {
+            n = 0;
+            for (; first != last; ++first) {
+                new (where + n) T(std::move(*first));
+                ++n;
+            }
+            return qsizetype(std::exchange(n, 0));
+        }
+        ~Constructor() noexcept(std::is_nothrow_destructible_v<T>)
+        {
+            while (n)
+                where[--n].~T();
+        }
+    };
+
+    // Watches passed iterator. Unless commit() is called, all the elements that
+    // the watched iterator passes through are deleted at the end of object
+    // lifetime.
+    //
+    // Requirements: when not at starting position, the iterator is expected to
+    //               point to a valid object (to initialized memory)
+    template<typename It = iterator>
+    struct Destructor
+    {
+        It *iter;
+        It end;
+
+        Destructor(It &it) noexcept(std::is_nothrow_copy_constructible_v<It>)
+            : iter(std::addressof(it)), end(it)
+        { }
+        void commit() noexcept
+        {
+            iter = std::addressof(end);
+        }
+        ~Destructor() noexcept(std::is_nothrow_destructible_v<T>)
+        {
+            // Step is either 1 or -1 and depends on the interposition of *iter
+            // and end. Note that *iter is expected to point to a valid object
+            // (see the logic below).
+            for (const int step = *iter < end ? 1 : -1; *iter != end; std::advance(*iter, step))
+                (*iter)->~T();
+        }
+    };
+
+    // Moves the data range in memory by the specified amount. Unless commit()
+    // is called, the data is moved back to the original place at the end of
+    // object lifetime.
+    struct Displacer
+    {
+        T *const begin;
+        T *const end;
+        qsizetype displace;
+
+        static_assert(QTypeInfoQuery<T>::isRelocatable, "Type must be relocatable");
+
+        Displacer(T *start, T *finish, qsizetype diff) noexcept
+            : begin(start), end(finish), displace(diff)
+        {
+            ::memmove(static_cast<void *>(begin + displace), static_cast<void *>(begin),
+                      (end - begin) * sizeof(T));
+        }
+        void commit() noexcept { displace = 0; }
+        ~Displacer() noexcept
+        {
+            if (displace)
+                ::memmove(static_cast<void *>(begin), static_cast<void *>(begin + displace),
+                          (end - begin) * sizeof(T));
+        }
+    };
+
+    // Watches passed iterator. Moves the data range (defined as a start
+    // iterator and a length) to the new starting position at the end of object
+    // lifetime.
+    struct Mover
+    {
+        T *&destination;
+        const T *const source;
+        size_t n;
+        qsizetype &size;
+
+        static_assert(QTypeInfoQuery<T>::isRelocatable, "Type must be relocatable");
+
+        Mover(T *&start, size_t length, qsizetype &sz) noexcept
+            : destination(start), source(start), n(length), size(sz)
+        { }
+        ~Mover() noexcept
+        {
+            ::memmove(static_cast<void *>(destination), static_cast<const void *>(source),
+                      n * sizeof(T));
+            size -= source > destination ? source - destination : destination - source;
+        }
+    };
+};
+
 QT_WARNING_PUSH
 #if defined(Q_CC_GNU) && Q_CC_GNU >= 700
 QT_WARNING_DISABLE_GCC("-Wstringop-overflow")
@@ -265,35 +427,13 @@ struct QGenericArrayOps
         Q_ASSERT(b <= e);
         Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size);
 
+        typedef typename QArrayExceptionSafetyPrimitives<T>::Constructor CopyConstructor;
+
         // Provides strong exception safety guarantee,
         // provided T::~T() nothrow
 
-        struct CopyConstructor
-        {
-            CopyConstructor(T *w) : where(w) {}
-
-            void copy(T *src, const T *const srcEnd)
-            {
-                n = 0;
-                for (; src != srcEnd; ++src) {
-                    new (where + n) T(std::move(*src));
-                    ++n;
-                }
-                n = 0;
-            }
-
-            ~CopyConstructor()
-            {
-                while (n)
-                    where[--n].~T();
-            }
-
-            T *const where;
-            size_t n;
-        } copier(this->end());
-
-        copier.copy(b, e);
-        this->size += (e - b);
+        CopyConstructor copier(this->end());
+        this->size += copier.move(b, e);
     }
 
     void copyAppend(size_t n, parameter_type t)
@@ -341,6 +481,8 @@ struct QGenericArrayOps
         Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append
         Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size);
 
+        typedef typename QArrayExceptionSafetyPrimitives<T>::template Destructor<T *> Destructor;
+
         // Array may be truncated at where in case of exceptions
 
         T *const end = this->end();
@@ -349,28 +491,7 @@ struct QGenericArrayOps
 
         const T *const step1End = where + qMax(e - b, end - where);
 
-        struct Destructor
-        {
-            Destructor(T *&it)
-                : iter(&it)
-                , end(it)
-            {
-            }
-
-            void commit()
-            {
-                iter = &end;
-            }
-
-            ~Destructor()
-            {
-                for (; *iter != end; --*iter)
-                    (*iter)->~T();
-            }
-
-            T **iter;
-            T *end;
-        } destroyer(writeIter);
+        Destructor destroyer(writeIter);
 
         // Construct new elements in array
         while (writeIter != step1End) {
@@ -404,6 +525,8 @@ struct QGenericArrayOps
         Q_ASSERT(where >= this->begin() && where <= this->end());
         Q_ASSERT(this->allocatedCapacity() - this->size >= n);
 
+        typedef typename QArrayExceptionSafetyPrimitives<T>::template Destructor<T *> Destructor;
+
         // Array may be truncated at where in case of exceptions
         T *const end = this->end();
         const T *readIter = end;
@@ -411,28 +534,7 @@ struct QGenericArrayOps
 
         const T *const step1End = where + qMax<size_t>(n, end - where);
 
-        struct Destructor
-        {
-            Destructor(T *&it)
-                : iter(&it)
-                , end(it)
-            {
-            }
-
-            void commit()
-            {
-                iter = &end;
-            }
-
-            ~Destructor()
-            {
-                for (; *iter != end; --*iter)
-                    (*iter)->~T();
-            }
-
-            T **iter;
-            T *end;
-        } destroyer(writeIter);
+        Destructor destroyer(writeIter);
 
         // Construct new elements in array
         while (writeIter != step1End) {
@@ -542,62 +644,17 @@ struct QMovableArrayOps
         Q_ASSERT(e <= where || b > this->end() || where == this->end()); // No overlap or append
         Q_ASSERT(size_t(e - b) <= this->allocatedCapacity() - this->size);
 
+        typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace;
+        typedef typename QArrayExceptionSafetyPrimitives<T>::Constructor CopyConstructor;
+
         // Provides strong exception safety guarantee,
         // provided T::~T() nothrow
 
-        struct ReversibleDisplace
-        {
-            ReversibleDisplace(T *start, T *finish, size_t diff)
-                : begin(start)
-                , end(finish)
-                , displace(diff)
-            {
-                ::memmove(static_cast<void *>(begin + displace), static_cast<void *>(begin),
-                          (end - begin) * sizeof(T));
-            }
-
-            void commit() { displace = 0; }
-
-            ~ReversibleDisplace()
-            {
-                if (displace)
-                    ::memmove(static_cast<void *>(begin), static_cast<void *>(begin + displace),
-                              (end - begin) * sizeof(T));
-            }
-
-            T *const begin;
-            T *const end;
-            size_t displace;
-
-        } displace(where, this->end(), size_t(e - b));
-
-        struct CopyConstructor
-        {
-            CopyConstructor(T *w) : where(w) {}
-
-            void copy(const T *src, const T *const srcEnd)
-            {
-                n = 0;
-                for (; src != srcEnd; ++src) {
-                    new (where + n) T(*src);
-                    ++n;
-                }
-                n = 0;
-            }
-
-            ~CopyConstructor()
-            {
-                while (n)
-                    where[--n].~T();
-            }
-
-            T *const where;
-            size_t n;
-        } copier(where);
-
-        copier.copy(b, e);
+        ReversibleDisplace displace(where, this->end(), e - b);
+        CopyConstructor copier(where);
+        const auto copiedSize = copier.copy(b, e);
         displace.commit();
-        this->size += (e - b);
+        this->size += copiedSize;
     }
 
     void insert(T *where, size_t n, parameter_type t)
@@ -606,62 +663,17 @@ struct QMovableArrayOps
         Q_ASSERT(where >= this->begin() && where <= this->end());
         Q_ASSERT(this->allocatedCapacity() - this->size >= n);
 
+        typedef typename QArrayExceptionSafetyPrimitives<T>::Displacer ReversibleDisplace;
+        typedef typename QArrayExceptionSafetyPrimitives<T>::Constructor CopyConstructor;
+
         // Provides strong exception safety guarantee,
         // provided T::~T() nothrow
 
-        struct ReversibleDisplace
-        {
-            ReversibleDisplace(T *start, T *finish, size_t diff)
-                : begin(start)
-                , end(finish)
-                , displace(diff)
-            {
-                ::memmove(static_cast<void *>(begin + displace), static_cast<void *>(begin),
-                          (end - begin) * sizeof(T));
-            }
-
-            void commit() { displace = 0; }
-
-            ~ReversibleDisplace()
-            {
-                if (displace)
-                    ::memmove(static_cast<void *>(begin), static_cast<void *>(begin + displace),
-                              (end - begin) * sizeof(T));
-            }
-
-            T *const begin;
-            T *const end;
-            size_t displace;
-
-        } displace(where, this->end(), n);
-
-        struct CopyConstructor
-        {
-            CopyConstructor(T *w) : where(w) {}
-
-            void copy(size_t count, parameter_type proto)
-            {
-                n = 0;
-                while (count--) {
-                    new (where + n) T(proto);
-                    ++n;
-                }
-                n = 0;
-            }
-
-            ~CopyConstructor()
-            {
-                while (n)
-                    where[--n].~T();
-            }
-
-            T *const where;
-            size_t n;
-        } copier(where);
-
-        copier.copy(n, t);
+        ReversibleDisplace displace(where, this->end(), qsizetype(n));
+        CopyConstructor copier(where);
+        const auto copiedSize = copier.clone(n, t);
         displace.commit();
-        this->size += int(n);
+        this->size += copiedSize;
     }
 
     // use moving insert
@@ -674,27 +686,9 @@ struct QMovableArrayOps
         Q_ASSERT(b >= this->begin() && b < this->end());
         Q_ASSERT(e > this->begin() && e <= this->end());
 
-        struct Mover
-        {
-            Mover(T *&start, const T *finish, qsizetype &sz)
-                : destination(start)
-                , source(start)
-                , n(finish - start)
-                , size(sz)
-            {
-            }
-
-            ~Mover()
-            {
-                ::memmove(static_cast<void *>(destination), static_cast<const void *>(source), n * sizeof(T));
-                size -= (source - destination);
-            }
+        typedef typename QArrayExceptionSafetyPrimitives<T>::Mover Mover;
 
-            T *&destination;
-            const T *const source;
-            size_t n;
-            qsizetype &size;
-        } mover(e, this->end(), this->size);
+        Mover mover(e, static_cast<const T *>(this->end()) - e, this->size);
 
         // destroy the elements we're erasing
         do {