BLI: improve exception safety of VectorSet

For more information see rB2aff45146f1464ba8899368ad004522cb6a1a98c.

4 files changed, 144 insertions, 57 deletions

diff --git a/source/blender/blenlib/BLI_array.hh b/source/blender/blenlib/BLI_array.hh
index dddf4f64ff5..8a7dcb7ffaa 100644
--- a/source/blender/blenlib/BLI_array.hh
+++ b/source/blender/blenlib/BLI_array.hh
@@ -353,6 +353,10 @@ class Array {
   {
     return allocator_;
   }
+  const Allocator &allocator() const
+  {
+    return allocator_;
+  }
 
   /**
    * Get the value of the InlineBufferCapacity template argument. This is the number of elements
diff --git a/source/blender/blenlib/BLI_vector_set.hh b/source/blender/blenlib/BLI_vector_set.hh
index 9d7c61f9e3b..c9773dc599d 100644
--- a/source/blender/blenlib/BLI_vector_set.hh
+++ b/source/blender/blenlib/BLI_vector_set.hh
@@ -143,7 +143,7 @@ class VectorSet {
    * no keys are removed. The first set->size() elements in this array are initialized. The
    * capacity of the array is usable_slots_.
    */
-  Key *keys_;
+  Key *keys_ = nullptr;
 
   /** Iterate over a slot index sequence for a given hash. */
 #define VECTOR_SET_SLOT_PROBING_BEGIN(HASH, R_SLOT) \
@@ -157,22 +157,31 @@ class VectorSet {
    * necessary to avoid a high cost when no elements are added at all. An optimized grow operation
    * is performed on the first insertion.
    */
-  VectorSet()
+  VectorSet(Allocator allocator = {}) noexcept
       : removed_slots_(0),
         occupied_and_removed_slots_(0),
         usable_slots_(0),
         slot_mask_(0),
-        slots_(1),
+        slots_(1, allocator),
         keys_(nullptr)
   {
   }
 
+  VectorSet(NoExceptConstructor, Allocator allocator = {}) : VectorSet(allocator)
+  {
+  }
+
+  VectorSet(Span<Key> keys, Allocator allocator = {}) : VectorSet(NoExceptConstructor(), allocator)
+  {
+    this->add_multiple(keys);
+  }
+
   /**
    * Construct a vector set that contains the given keys. Duplicates will be removed automatically.
    */
-  VectorSet(const std::initializer_list<Key> &keys) : VectorSet()
+  VectorSet(const std::initializer_list<Key> &keys, Allocator allocator = {})
+      : VectorSet(Span(keys), allocator)
   {
-    this->add_multiple(keys);
   }
 
   ~VectorSet()
@@ -183,15 +192,23 @@ class VectorSet {
     }
   }
 
-  VectorSet(const VectorSet &other)
-      : removed_slots_(other.removed_slots_),
-        occupied_and_removed_slots_(other.occupied_and_removed_slots_),
-        usable_slots_(other.usable_slots_),
-        slot_mask_(other.slot_mask_),
-        slots_(other.slots_)
+  VectorSet(const VectorSet &other) : slots_(other.slots_)
   {
-    keys_ = this->allocate_keys_array(usable_slots_);
-    uninitialized_copy_n(other.keys_, other.size(), keys_);
+    keys_ = this->allocate_keys_array(other.usable_slots_);
+    try {
+      uninitialized_copy_n(other.keys_, other.size(), keys_);
+    }
+    catch (...) {
+      this->deallocate_keys_array(keys_);
+      throw;
+    }
+
+    removed_slots_ = other.removed_slots_;
+    occupied_and_removed_slots_ = other.occupied_and_removed_slots_;
+    usable_slots_ = other.usable_slots_;
+    slot_mask_ = other.slot_mask_;
+    hash_ = other.hash_;
+    is_equal_ = other.is_equal_;
   }
 
   VectorSet(VectorSet &&other) noexcept
@@ -212,26 +229,12 @@ class VectorSet {
 
   VectorSet &operator=(const VectorSet &other)
   {
-    if (this == &other) {
-      return *this;
-    }
-
-    this->~VectorSet();
-    new (this) VectorSet(other);
-
-    return *this;
+    return copy_assign_container(*this, other);
   }
 
   VectorSet &operator=(VectorSet &&other)
   {
-    if (this == &other) {
-      return *this;
-    }
-
-    this->~VectorSet();
-    new (this) VectorSet(std::move(other));
-
-    return *this;
+    return move_assign_container(*this, std::move(other));
   }
 
   /**
@@ -490,32 +493,48 @@ class VectorSet {
 
     /* Optimize the case when the set was empty beforehand. We can avoid some copies here. */
     if (this->size() == 0) {
-      slots_.~Array();
-      new (&slots_) SlotArray(total_slots);
+      try {
+        slots_.reinitialize(total_slots);
+        keys_ = this->allocate_keys_array(usable_slots);
+      }
+      catch (...) {
+        this->noexcept_reset();
+        throw;
+      }
       removed_slots_ = 0;
       occupied_and_removed_slots_ = 0;
       usable_slots_ = usable_slots;
       slot_mask_ = new_slot_mask;
-      keys_ = this->allocate_keys_array(usable_slots);
       return;
     }
 
     SlotArray new_slots(total_slots);
 
-    for (Slot &slot : slots_) {
-      if (slot.is_occupied()) {
-        this->add_after_grow_and_destruct_old(slot, new_slots, new_slot_mask);
+    try {
+      for (Slot &slot : slots_) {
+        if (slot.is_occupied()) {
+          this->add_after_grow(slot, new_slots, new_slot_mask);
+          slot.remove();
+        }
       }
+      slots_ = std::move(new_slots);
+    }
+    catch (...) {
+      this->noexcept_reset();
+      throw;
     }
 
     Key *new_keys = this->allocate_keys_array(usable_slots);
-    uninitialized_relocate_n(keys_, this->size(), new_keys);
+    try {
+      uninitialized_relocate_n(keys_, this->size(), new_keys);
+    }
+    catch (...) {
+      this->deallocate_keys_array(new_keys);
+      this->noexcept_reset();
+      throw;
+    }
     this->deallocate_keys_array(keys_);
 
-    /* All occupied slots have been destructed already and empty/removed slots are assumed to be
-     * trivially destructible. */
-    slots_.clear_without_destruct();
-    slots_ = std::move(new_slots);
     keys_ = new_keys;
     occupied_and_removed_slots_ -= removed_slots_;
     usable_slots_ = usable_slots;
@@ -523,9 +542,7 @@ class VectorSet {
     slot_mask_ = new_slot_mask;
   }
 
-  void add_after_grow_and_destruct_old(Slot &old_slot,
-                                       SlotArray &new_slots,
-                                       const uint64_t new_slot_mask)
+  void add_after_grow(Slot &old_slot, SlotArray &new_slots, const uint64_t new_slot_mask)
   {
     const Key &key = keys_[old_slot.index()];
     const uint64_t hash = old_slot.get_hash(key, Hash());
@@ -533,13 +550,20 @@ class VectorSet {
     SLOT_PROBING_BEGIN (ProbingStrategy, hash, new_slot_mask, slot_index) {
       Slot &slot = new_slots[slot_index];
       if (slot.is_empty()) {
-        slot.relocate_occupied_here(old_slot, hash);
+        slot.occupy(old_slot.index(), hash);
         return;
       }
     }
     SLOT_PROBING_END();
   }
 
+  void noexcept_reset() noexcept
+  {
+    Allocator allocator = slots_.allocator();
+    this->~VectorSet();
+    new (this) VectorSet(NoExceptConstructor(), allocator);
+  }
+
   template<typename ForwardKey>
   bool contains__impl(const ForwardKey &key, const uint64_t hash) const
   {
@@ -580,8 +604,8 @@ class VectorSet {
       if (slot.is_empty()) {
         int64_t index = this->size();
         new (keys_ + index) Key(std::forward<ForwardKey>(key));
-        occupied_and_removed_slots_++;
         slot.occupy(index, hash);
+        occupied_and_removed_slots_++;
         return true;
       }
       if (slot.contains(key, is_equal_, hash, keys_)) {
diff --git a/source/blender/blenlib/BLI_vector_set_slots.hh b/source/blender/blenlib/BLI_vector_set_slots.hh
index 0e75c4690a4..b79341ed744 100644
--- a/source/blender/blenlib/BLI_vector_set_slots.hh
+++ b/source/blender/blenlib/BLI_vector_set_slots.hh
@@ -97,18 +97,6 @@ template<typename Key> class SimpleVectorSetSlot {
   }
 
   /**
-   * Move the other slot into this slot and destruct it. We do destruction here, because this way
-   * we can avoid a comparison with the state, since we know the slot is occupied. For this
-   * specific slot implementation, this does not make a difference.
-   */
-  void relocate_occupied_here(SimpleVectorSetSlot &other, uint64_t UNUSED(hash))
-  {
-    BLI_assert(!this->is_occupied());
-    BLI_assert(other.is_occupied());
-    state_ = other.state_;
-  }
-
-  /**
    * Change the state of this slot from empty/removed to occupied. The hash can be used by other
    * slot implementations.
    */
diff --git a/source/blender/blenlib/tests/BLI_vector_set_test.cc b/source/blender/blenlib/tests/BLI_vector_set_test.cc
index 8f3db8d8403..320cb15f450 100644
--- a/source/blender/blenlib/tests/BLI_vector_set_test.cc
+++ b/source/blender/blenlib/tests/BLI_vector_set_test.cc
@@ -1,5 +1,6 @@
 /* Apache License, Version 2.0 */
 
+#include "BLI_exception_safety_test_utils.hh"
 #include "BLI_strict_flags.h"
 #include "BLI_vector_set.hh"
 #include "testing/testing.h"
@@ -161,4 +162,74 @@ TEST(vector_set, Remove)
   EXPECT_FALSE(set.contains(5));
 }
 
+TEST(vector_set, SpanConstructorExceptions)
+{
+  std::array<ExceptionThrower, 5> array = {1, 2, 3, 4, 5};
+  array[3].throw_during_copy = true;
+  Span<ExceptionThrower> span = array;
+
+  EXPECT_ANY_THROW({ VectorSet<ExceptionThrower> set(span); });
+}
+
+TEST(vector_set, CopyConstructorExceptions)
+{
+  VectorSet<ExceptionThrower> set = {1, 2, 3, 4, 5};
+  set[3].throw_during_copy = true;
+
+  EXPECT_ANY_THROW({ VectorSet<ExceptionThrower> set_copy(set); });
+}
+
+TEST(vector_set, MoveConstructorExceptions)
+{
+  VectorSet<ExceptionThrower> set = {1, 2, 3, 4, 5};
+  set[3].throw_during_copy = true;
+  set[3].throw_during_move = true;
+  /* Currently never throws on move, because values are separately allocated. */
+  VectorSet<ExceptionThrower> set_moved(std::move(set));
+  EXPECT_EQ(set.size(), 0); /* NOLINT: bugprone-use-after-move */
+  set.add_multiple({4, 5, 6, 7, 8});
+  EXPECT_EQ(set.size(), 5);
+}
+
+TEST(vector_set, AddNewExceptions)
+{
+  VectorSet<ExceptionThrower> set;
+  ExceptionThrower value;
+  value.throw_during_copy = true;
+  EXPECT_ANY_THROW({ set.add_new(value); });
+  EXPECT_EQ(set.size(), 0);
+  EXPECT_ANY_THROW({ set.add_new(value); });
+  EXPECT_EQ(set.size(), 0);
+}
+
+TEST(vector_set, AddExceptions)
+{
+  VectorSet<ExceptionThrower> set;
+  ExceptionThrower value;
+  value.throw_during_copy = true;
+  EXPECT_ANY_THROW({ set.add(value); });
+  EXPECT_EQ(set.size(), 0);
+  EXPECT_ANY_THROW({ set.add(value); });
+  EXPECT_EQ(set.size(), 0);
+}
+
+TEST(vector_set, ReserveExceptions)
+{
+  VectorSet<ExceptionThrower> set;
+  set.add_multiple({1, 2, 3, 4, 5});
+  set[2].throw_during_move = true;
+  EXPECT_ANY_THROW({ set.reserve(100); });
+}
+
+TEST(vector_set, PopExceptions)
+{
+  VectorSet<ExceptionThrower> set = {1, 2, 3};
+  set.as_span().last().throw_during_move = true;
+  EXPECT_EQ(set.size(), 3);
+  EXPECT_ANY_THROW({ set.pop(); }); /* NOLINT: bugprone-throw-keyword-missing */
+  EXPECT_EQ(set.size(), 3);
+  set.add(10);
+  EXPECT_EQ(set.size(), 4);
+}
+
 }  // namespace blender::tests