BLI: improve exception safety of Vector, Array and Stack

Using C++ exceptions in Blender is difficult, due to the large
number of C functions in the call stack. However, C++ data
structures in blenlib should at least try to be exception safe,
so that they can be used if someone wants to use exceptions
in some isolated area.

This patch improves the exception safety of the Vector, Array
and Stack data structure. This is mainly achieved by reordering
some lines and doing some explicit exception handling.
I don't expect performance of common operations to be affected
by this change.

The three containers are supposed to provide at least the
basic exception guarantee for most methods (except for e.g.
`*_unchecked` methods). So, resources should not leak when
the contained type throws an exception.

I also added new unit tests that test the exception handling
in various cases.

1 files changed, 59 insertions, 36 deletions

diff --git a/source/blender/blenlib/BLI_stack.hh b/source/blender/blenlib/BLI_stack.hh
index 8eca356ec54..a463ac102f1 100644
--- a/source/blender/blenlib/BLI_stack.hh
+++ b/source/blender/blenlib/BLI_stack.hh
@@ -117,7 +117,7 @@ class Stack {
   /**
    * Initialize an empty stack. No heap allocation is done.
    */
-  Stack(Allocator allocator = {}) : allocator_(allocator)
+  Stack(Allocator allocator = {}) noexcept : allocator_(allocator)
   {
     inline_chunk_.below = nullptr;
     inline_chunk_.above = nullptr;
@@ -129,11 +129,15 @@ class Stack {
     size_ = 0;
   }
 
+  Stack(NoExceptConstructor, Allocator allocator = {}) noexcept : Stack(allocator)
+  {
+  }
+
   /**
    * Create a new stack that contains the given elements. The values are pushed to the stack in
    * the order they are in the array.
    */
-  Stack(Span<T> values) : Stack()
+  Stack(Span<T> values, Allocator allocator = {}) : Stack(NoExceptConstructor(), allocator)
   {
     this->push_multiple(values);
   }
@@ -147,11 +151,12 @@ class Stack {
    *  assert(stack.pop() == 6);
    *  assert(stack.pop() == 5);
    */
-  Stack(const std::initializer_list<T> &values) : Stack(Span<T>(values))
+  Stack(const std::initializer_list<T> &values, Allocator allocator = {})
+      : Stack(Span<T>(values), allocator)
   {
   }
 
-  Stack(const Stack &other) : Stack(other.allocator_)
+  Stack(const Stack &other) : Stack(NoExceptConstructor(), other.allocator_)
   {
     for (const Chunk *chunk = &other.inline_chunk_; chunk; chunk = chunk->above) {
       const T *begin = chunk->begin;
@@ -160,7 +165,8 @@ class Stack {
     }
   }
 
-  Stack(Stack &&other) noexcept : Stack(other.allocator_)
+  Stack(Stack &&other) noexcept(std::is_nothrow_move_constructible_v<T>)
+      : Stack(NoExceptConstructor(), other.allocator_)
   {
     uninitialized_relocate_n<T>(
         other.inline_buffer_, std::min(other.size_, InlineBufferCapacity), inline_buffer_);
@@ -197,28 +203,14 @@ class Stack {
     }
   }
 
-  Stack &operator=(const Stack &stack)
+  Stack &operator=(const Stack &other)
   {
-    if (this == &stack) {
-      return *this;
-    }
-
-    this->~Stack();
-    new (this) Stack(stack);
-
-    return *this;
+    return copy_assign_container(*this, other);
   }
 
-  Stack &operator=(Stack &&stack)
+  Stack &operator=(Stack &&other)
   {
-    if (this == &stack) {
-      return *this;
-    }
-
-    this->~Stack();
-    new (this) Stack(std::move(stack));
-
-    return *this;
+    return move_assign_container(*this, std::move(other));
   }
 
   /**
@@ -226,21 +218,26 @@ class Stack {
    */
   void push(const T &value)
   {
-    if (top_ == top_chunk_->capacity_end) {
-      this->activate_next_chunk(1);
-    }
-    new (top_) T(value);
-    top_++;
-    size_++;
+    this->push_as(value);
   }
   void push(T &&value)
   {
+    this->push_as(std::move(value));
+  }
+  template<typename ForwardT> void push_as(ForwardT &&value)
+  {
     if (top_ == top_chunk_->capacity_end) {
       this->activate_next_chunk(1);
     }
-    new (top_) T(std::move(value));
-    top_++;
-    size_++;
+    try {
+      new (top_) T(std::forward<ForwardT>(value));
+      top_++;
+      size_++;
+    }
+    catch (...) {
+      this->move_top_pointer_back_to_below_chunk();
+      throw;
+    }
   }
 
   /**
@@ -250,8 +247,8 @@ class Stack {
   T pop()
   {
     BLI_assert(size_ > 0);
+    T value = std::move(*(top_ - 1));
     top_--;
-    T value = std::move(*top_);
     top_->~T();
     size_--;
 
@@ -296,13 +293,18 @@ class Stack {
 
       const int64_t remaining_capacity = top_chunk_->capacity_end - top_;
       const int64_t amount = std::min(remaining_values.size(), remaining_capacity);
-      uninitialized_copy_n(remaining_values.data(), amount, top_);
+      try {
+        uninitialized_copy_n(remaining_values.data(), amount, top_);
+      }
+      catch (...) {
+        this->move_top_pointer_back_to_below_chunk();
+        throw;
+      }
       top_ += amount;
+      size_ += amount;
 
       remaining_values = remaining_values.drop_front(amount);
     }
-
-    size_ += values.size();
   }
 
   /**
@@ -332,6 +334,15 @@ class Stack {
     top_ = top_chunk_->begin;
   }
 
+  /* This should only be called by unit tests. */
+  bool is_invariant_maintained() const
+  {
+    if (size_ == 0) {
+      return top_ == inline_chunk_.begin;
+    }
+    return top_ > top_chunk_->begin;
+  }
+
  private:
   /**
    * Changes top_chunk_ to point to a new chunk that is above the current one. The new chunk might
@@ -365,6 +376,18 @@ class Stack {
     top_ = top_chunk_->begin;
   }
 
+  void move_top_pointer_back_to_below_chunk()
+  {
+    /* This makes sure that the invariant stays intact after a failed push. */
+    if (size_ == 0) {
+      top_ = inline_chunk_.begin;
+    }
+    else if (top_ == top_chunk_->begin) {
+      top_chunk_ = top_chunk_->below;
+      top_ = top_chunk_->capacity_end;
+    }
+  }
+
   void destruct_all_elements()
   {
     for (T *value = top_chunk_->begin; value != top_; value++) {