1 files changed, 373 insertions, 0 deletions
diff --git a/deps/v8/test/unittests/zone/zone-vector-unittest.cc b/deps/v8/test/unittests/zone/zone-vector-unittest.cc
new file mode 100644
index 0000000000..d2406f8b45
--- /dev/null
+++ b/deps/v8/test/unittests/zone/zone-vector-unittest.cc
@@ -0,0 +1,373 @@
+// Copyright 2023 the V8 project authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include <optional>
+
+#include "src/zone/zone-containers.h"
+#include "test/unittests/test-utils.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+namespace v8::internal {
+
+template <class T>
+class LiveSet {
+ public:
+  void Add(const T* new_entry) {
+    CHECK(!Contains(new_entry));
+    set_.insert(new_entry);
+  }
+
+  void Remove(const T* old_entry) {
+    CHECK(Contains(old_entry));
+    set_.erase(old_entry);
+  }
+
+  void CheckContainsAll(ZoneVector<T>& vector) {
+    CHECK_EQ(vector.size(), set_.size());
+    for (const T* m = vector.begin(); m != vector.end(); m++) {
+      CHECK(Contains(m));
+    }
+  }
+
+  void CheckEmpty() { CHECK_EQ(0, set_.size()); }
+
+ private:
+  bool Contains(const T* entry) {
+    // std::set::contains is a C++20 extension.
+    return set_.find(entry) != set_.end();
+  }
+
+  std::set<const T*> set_;
+};
+
+template <typename T>
+LiveSet<T>& live_set() {
+  static LiveSet<T> static_live_set;
+  return static_live_set;
+}
+
+class Trivial {
+ public:
+  Trivial() : id_(0) {}
+  explicit Trivial(int id) : id_(id) {}
+
+  int id() const { return id_; }
+
+ private:
+  int id_;
+};
+
+static_assert(std::is_trivially_copyable_v<Trivial>);
+
+template <>
+class LiveSet<Trivial> {
+ public:
+  void Add(const Trivial* new_entry) { UNREACHABLE(); }
+  void Remove(const Trivial* old_entry) { UNREACHABLE(); }
+  void CheckContainsAll(ZoneVector<Trivial>&) {}
+  void CheckEmpty() {}
+};
+
+class CopyAssignable {
+ public:
+  CopyAssignable() : id_(0) { live_set<CopyAssignable>().Add(this); }
+  explicit CopyAssignable(int id) : id_(id) {
+    live_set<CopyAssignable>().Add(this);
+  }
+  CopyAssignable(const CopyAssignable& other) V8_NOEXCEPT : id_(other.id_) {
+    live_set<CopyAssignable>().Add(this);
+  }
+  ~CopyAssignable() { live_set<CopyAssignable>().Remove(this); }
+  CopyAssignable& operator=(const CopyAssignable& other) V8_NOEXCEPT = default;
+
+  CopyAssignable(CopyAssignable&& other) = delete;
+  CopyAssignable& operator=(CopyAssignable&& other) = delete;
+
+  int id() const { return id_; }
+
+ private:
+  int id_;
+};
+
+static_assert(!std::is_trivially_copyable_v<CopyAssignable>);
+static_assert(std::is_copy_assignable_v<CopyAssignable>);
+static_assert(!std::is_move_assignable_v<CopyAssignable>);
+
+class MoveAssignable {
+ public:
+  MoveAssignable() : id_(0) { live_set<MoveAssignable>().Add(this); }
+  explicit MoveAssignable(int id) : id_(id) {
+    live_set<MoveAssignable>().Add(this);
+  }
+  MoveAssignable(const MoveAssignable& other) V8_NOEXCEPT : id_(other.id_) {
+    live_set<MoveAssignable>().Add(this);
+  }
+  MoveAssignable(MoveAssignable&& other) V8_NOEXCEPT : id_(other.id_) {
+    live_set<MoveAssignable>().Add(this);
+  }
+  MoveAssignable& operator=(const MoveAssignable& other) = delete;
+  MoveAssignable& operator=(MoveAssignable&& other) V8_NOEXCEPT {
+    id_ = other.id_;
+    return *this;
+  }
+  ~MoveAssignable() { live_set<MoveAssignable>().Remove(this); }
+
+  int id() const { return id_; }
+
+ private:
+  int id_;
+};
+
+static_assert(!std::is_trivially_copyable_v<MoveAssignable>);
+static_assert(std::is_move_assignable_v<MoveAssignable>);
+static_assert(!std::is_copy_assignable_v<MoveAssignable>);
+
+class NotAssignable {
+ public:
+  NotAssignable() : id_(0) { live_set<NotAssignable>().Add(this); }
+  explicit NotAssignable(int id) : id_(id) {
+    live_set<NotAssignable>().Add(this);
+  }
+  NotAssignable(const NotAssignable& other) V8_NOEXCEPT : id_(other.id_) {
+    live_set<NotAssignable>().Add(this);
+  }
+  NotAssignable& operator=(const NotAssignable& other) = delete;
+  ~NotAssignable() { live_set<NotAssignable>().Remove(this); }
+
+  NotAssignable(NotAssignable&& other) = delete;
+  NotAssignable& operator=(NotAssignable&& other) = delete;
+
+  int id() const { return id_; }
+
+ private:
+  int id_;
+};
+
+static_assert(!std::is_trivially_copyable_v<NotAssignable>);
+static_assert(!std::is_copy_assignable_v<NotAssignable>);
+static_assert(!std::is_move_assignable_v<NotAssignable>);
+
+class ZoneVectorTest : public TestWithZone {
+ public:
+  template <class T>
+  void CheckConsistency(ZoneVector<T>& vector, std::initializer_list<int> ids) {
+    live_set<T>().CheckContainsAll(vector);
+    CHECK_EQ(vector.size(), ids.size());
+    auto it = ids.begin();
+    for (size_t i = 0; i < ids.size(); i++) {
+      CHECK_EQ(*it++, vector[i].id());
+    }
+  }
+
+  template <class T>
+  void Basic() {
+    {
+      // Constructor with definition.
+      ZoneVector<T> v(1, T(1), zone());
+      CheckConsistency(v, {1});
+    }
+    live_set<T>().CheckEmpty();
+
+    {
+      // Constructor with initializer list.
+      ZoneVector<T> v({T(1), T(2), T(3)}, zone());
+      CheckConsistency(v, {1, 2, 3});
+    }
+    live_set<T>().CheckEmpty();
+
+    {
+      std::optional<ZoneVector<T>> v1;
+      v1.emplace({T(1), T(2), T(3)}, zone());
+      CheckConsistency(v1.value(), {1, 2, 3});
+      {
+        // Copy assignment with growth.
+        ZoneVector<T> v2 = v1.value();
+        v1.reset();
+        CheckConsistency(v2, {1, 2, 3});
+      }
+      v1.emplace({T(1), T(2), T(3)}, zone());
+      CheckConsistency(v1.value(), {1, 2, 3});
+
+      // Copy assignment without growth.
+      ZoneVector<T> v3({T(4), T(5), T(6)}, zone());
+      v3 = v1.value();
+      v1.reset();
+      CheckConsistency(v3, {1, 2, 3});
+
+      // Move assignment.
+      {
+        ZoneVector<T> v4(std::move(v3));
+        CheckConsistency(v4, {1, 2, 3});
+      }
+      CheckConsistency(v3, {});
+    }
+    live_set<T>().CheckEmpty();
+  }
+
+  template <class T>
+  void Assign() {
+    {
+      // Assign with sufficient capacity.
+      ZoneVector<T> v({T(1), T(2), T(3)}, zone());
+      v.assign(2, T(4));
+      CheckConsistency(v, {4, 4});
+      // This time, capacity > size.
+      v.assign(3, T(5));
+      CheckConsistency(v, {5, 5, 5});
+    }
+
+    {
+      // Assign with capacity growth.
+      ZoneVector<T> v({T(1)}, zone());
+      v.assign(2, T(4));
+      CheckConsistency(v, {4, 4});
+    }
+
+    live_set<T>().CheckEmpty();
+  }
+
+  template <class T>
+  void Insert() {
+    // Check that we can insert (by iterator) in the right positions.
+    {
+      ZoneVector<T> v({T(2), T(4)}, zone());
+      {
+        T src1[] = {T(1)};
+        T src3[] = {T(3)};
+        T src5[] = {T(5)};
+        v.insert(&v.at(0), src1, std::end(src1));
+        v.insert(&v.at(2), src3, std::end(src3));
+        v.insert(v.end(), src5, std::end(src5));
+      }
+      CheckConsistency(v, {1, 2, 3, 4, 5});
+    }
+
+    // Check that we can insert (by count) in the right positions.
+    {
+      ZoneVector<T> v({T(2), T(4)}, zone());
+      v.insert(&v.at(0), 1, T(1));
+      v.insert(&v.at(2), 1, T(3));
+      v.insert(v.end(), 1, T(5));
+      CheckConsistency(v, {1, 2, 3, 4, 5});
+    }
+
+    // Test the "insufficient capacity" case in PrepareForInsertion.
+    {
+      ZoneVector<T> v(zone());
+      CHECK_EQ(0, v.capacity());
+      v.insert(v.begin(), 1, T(5));
+      CheckConsistency(v, {5});
+      {
+        T src[] = {T(1), T(2), T(3), T(4)};
+        v.insert(v.begin(), src, std::end(src));
+      }
+      CheckConsistency(v, {1, 2, 3, 4, 5});
+    }
+
+    // Test "case 1" of sufficient capacity in PrepareForInsertion.
+    {
+      ZoneVector<T> v({T(1), T(2), T(3), T(4), T(5)}, zone());
+      v.reserve(10);
+      CHECK_EQ(10, v.capacity());
+      CheckConsistency(v, {1, 2, 3, 4, 5});
+      {
+        T src[] = {T(11), T(12), T(13), T(14)};
+        v.insert(&v.at(3), src, std::end(src));
+      }
+      CheckConsistency(v, {1, 2, 3, 11, 12, 13, 14, 4, 5});
+    }
+
+    // Test "case 2" of sufficient capacity in PrepareForInsertion.
+    {
+      ZoneVector<T> v({T(1), T(2), T(3), T(4), T(5)}, zone());
+      v.reserve(10);
+      {
+        T src[] = {T(11), T(12)};
+        v.insert(&v.at(2), src, std::end(src));
+      }
+      CheckConsistency(v, {1, 2, 11, 12, 3, 4, 5});
+    }
+    live_set<T>().CheckEmpty();
+
+    // For good measure, test the edge case where we're inserting exactly
+    // as many elements as we're moving.
+    {
+      ZoneVector<T> v({T(1), T(2), T(3), T(4)}, zone());
+      v.reserve(10);
+      {
+        T src[] = {T(11), T(12)};
+        v.insert(&v.at(2), src, std::end(src));
+      }
+    }
+  }
+
+  template <class T>
+  void Erase() {
+    // Erase one element.
+    {
+      ZoneVector<T> v({T(1), T(2), T(3)}, zone());
+      v.erase(&v.at(1));
+      CheckConsistency(v, {1, 3});
+    }
+    // Erase a range.
+    {
+      ZoneVector<T> v({T(1), T(2), T(3), T(4)}, zone());
+      v.erase(&v.at(1), &v.at(3));
+      CheckConsistency(v, {1, 4});
+    }
+    // Erase first element.
+    {
+      ZoneVector<T> v({T(1), T(2), T(3)}, zone());
+      v.erase(v.begin());
+      CheckConsistency(v, {2, 3});
+    }
+    // Erase last element.
+    {
+      ZoneVector<T> v({T(1), T(2), T(3)}, zone());
+      v.erase(&v.at(2));
+      CheckConsistency(v, {1, 2});
+    }
+    // Erase nothing (empty range).
+    {
+      ZoneVector<T> v({T(1), T(2), T(3)}, zone());
+      v.erase(v.begin(), v.begin());
+      CheckConsistency(v, {1, 2, 3});
+      v.erase(&v.at(1), &v.at(1));
+      CheckConsistency(v, {1, 2, 3});
+      v.erase(v.end(), v.end());
+      CheckConsistency(v, {1, 2, 3});
+    }
+    live_set<T>().CheckEmpty();
+  }
+};
+
+TEST_F(ZoneVectorTest, Basic) {
+  Basic<Trivial>();
+  Basic<CopyAssignable>();
+  Basic<MoveAssignable>();
+  Basic<NotAssignable>();
+}
+
+TEST_F(ZoneVectorTest, Assign) {
+  Assign<Trivial>();
+  Assign<CopyAssignable>();
+  Assign<MoveAssignable>();
+  Assign<NotAssignable>();
+}
+
+TEST_F(ZoneVectorTest, Insert) {
+  Insert<Trivial>();
+  Insert<CopyAssignable>();
+  Insert<MoveAssignable>();
+  Insert<NotAssignable>();
+}
+
+TEST_F(ZoneVectorTest, Erase) {
+  Erase<Trivial>();
+  Erase<CopyAssignable>();
+  Erase<MoveAssignable>();
+  Erase<NotAssignable>();
+}
+
+}  // namespace v8::internal