Make bssl::Vector not require a default constructor

Rather than leaving default-initialized things in there, a real
std::vector implementation leaves the elements passed size_
unconstructed and constructs them as needed.

Change-Id: Ib884e2c10894de011d75a46037b446088195ba96
Reviewed-on: https://boringssl-review.googlesource.com/c/boringssl/+/71828
Commit-Queue: David Benjamin <davidben@google.com>
Reviewed-by: Adam Langley <agl@google.com>

ssl/internal.h

diff --git a/ssl/internal.h b/ssl/internal.h
index 247f8c6..d4c1c27 100644
--- a/ssl/internal.h
+++ b/ssl/internal.h
@@ -204,6 +204,16 @@
   return first;
 }
 
+template <typename InputIt, typename OutputIt>
+InputIt cxx17_uninitialized_move(InputIt first, InputIt last, OutputIt out) {
+  using OutputT = typename std::iterator_traits<OutputIt>::value_type;
+  for (; first != last; ++first) {
+    new (std::addressof(*out)) OutputT(std::move(*first));
+    ++out;
+  }
+  return out;
+}
+
 template <typename ForwardIt>
 ForwardIt cxx17_destroy_n(ForwardIt first, size_t n) {
   using T = typename std::iterator_traits<ForwardIt>::value_type;
@@ -367,42 +377,42 @@
 };
 
 // Vector<T> is a resizable array of elements of |T|.
-//
-// Note, for simplicity, this class currently differs from |std::vector| in that
-// |T| must be efficiently default-constructible. Allocated elements beyond the
-// end of the array are constructed and destructed.
 template <typename T>
 class Vector {
  public:
   Vector() = default;
   Vector(const Vector &) = delete;
   Vector(Vector &&other) { *this = std::move(other); }
-  ~Vector() {}
+  ~Vector() { clear(); }
 
   Vector &operator=(const Vector &) = delete;
   Vector &operator=(Vector &&other) {
-    size_ = other.size_;
-    other.size_ = 0;
-    array_ = std::move(other.array_);
+    clear();
+    std::swap(data_, other.data_);
+    std::swap(size_, other.size_);
+    std::swap(capacity_, other.capacity_);
     return *this;
   }
 
-  const T *data() const { return array_.data(); }
-  T *data() { return array_.data(); }
+  const T *data() const { return data_; }
+  T *data() { return data_; }
   size_t size() const { return size_; }
   bool empty() const { return size_ == 0; }
 
-  const T &operator[](size_t i) const { return array_[i]; }
-  T &operator[](size_t i) { return array_[i]; }
+  const T &operator[](size_t i) const { return data_[i]; }
+  T &operator[](size_t i) { return data_[i]; }
 
-  T *begin() { return array_.data(); }
-  const T *begin() const { return array_.data(); }
-  T *end() { return array_.data() + size_; }
-  const T *end() const { return array_.data() + size_; }
+  T *begin() { return data_; }
+  const T *begin() const { return data_; }
+  T *end() { return data_ + size_; }
+  const T *end() const { return data_ + size_; }
 
   void clear() {
+    cxx17_destroy_n(data_, size_);
+    OPENSSL_free(data_);
+    data_ = nullptr;
     size_ = 0;
-    array_.Reset();
+    capacity_ = 0;
   }
 
   // Push adds |elem| at the end of the internal array, growing if necessary. It
@@ -411,7 +421,7 @@
     if (!MaybeGrow()) {
       return false;
     }
-    array_[size_] = std::move(elem);
+    new (&data_[size_]) T(std::move(elem));
     size_++;
     return true;
   }
@@ -419,10 +429,14 @@
   // CopyFrom replaces the contents of the array with a copy of |in|. It returns
   // true on success and false on allocation error.
   bool CopyFrom(Span<const T> in) {
-    if (!array_.CopyFrom(in)) {
+    Array<T> copy;
+    if (!copy.CopyFrom(in)) {
       return false;
     }
-    size_ = in.size();
+
+    clear();
+    copy.Release(&data_, &size_);
+    capacity_ = size_;
     return true;
   }
 
@@ -430,35 +444,44 @@
   // If there is no room for one more element, creates a new backing array with
   // double the size of the old one and copies elements over.
   bool MaybeGrow() {
-    if (array_.size() == 0) {
-      return array_.Init(kDefaultSize);
-    }
     // No need to grow if we have room for one more T.
-    if (size_ < array_.size()) {
+    if (size_ < capacity_) {
       return true;
     }
-    // Double the array's size if it's safe to do so.
-    if (array_.size() > std::numeric_limits<size_t>::max() / 2) {
+    size_t new_capacity = kDefaultSize;
+    if (capacity_ > 0) {
+      // Double the array's size if it's safe to do so.
+      if (capacity_ > std::numeric_limits<size_t>::max() / 2) {
+        OPENSSL_PUT_ERROR(SSL, ERR_R_OVERFLOW);
+        return false;
+      }
+      new_capacity = capacity_ * 2;
+    }
+    if (new_capacity > std::numeric_limits<size_t>::max() / sizeof(T)) {
       OPENSSL_PUT_ERROR(SSL, ERR_R_OVERFLOW);
       return false;
     }
-    Array<T> new_array;
-    if (!new_array.Init(array_.size() * 2)) {
+    T *new_data =
+        reinterpret_cast<T *>(OPENSSL_malloc(new_capacity * sizeof(T)));
+    if (new_data == nullptr) {
       return false;
     }
-    for (size_t i = 0; i < array_.size(); i++) {
-      new_array[i] = std::move(array_[i]);
-    }
-    array_ = std::move(new_array);
-
+    size_t new_size = size_;
+    cxx17_uninitialized_move(begin(), end(), new_data);
+    clear();
+    data_ = new_data;
+    size_ = new_size;
+    capacity_ = new_capacity;
     return true;
   }
 
+  // data_ is a pointer to |capacity_| objects of size |T|, the first |size_| of
+  // which are constructed.
+  T *data_ = nullptr;
   // |size_| is the number of elements stored in this Vector.
   size_t size_ = 0;
-  // |array_| is the backing array. Note that |array_.size()| is this
-  // Vector's current capacity and that |size_ <= array_.size()|.
-  Array<T> array_;
+  // |capacity_| is the number of elements allocated in this Vector.
+  size_t capacity_ = 0;
   // |kDefaultSize| is the default initial size of the backing array.
   static constexpr size_t kDefaultSize = 16;
 };

ssl/ssl_test.cc

diff --git a/ssl/ssl_test.cc b/ssl/ssl_test.cc
index b552885..b21c798 100644
--- a/ssl/ssl_test.cc
+++ b/ssl/ssl_test.cc
@@ -587,6 +587,16 @@
   for (size_t i = 0; i < vec.size(); i++) {
     EXPECT_EQ(vec[i], i == 0 ? 42 : i);
   }
+
+  // Clearing the vector should give an empty one.
+  vec.clear();
+  ASSERT_TRUE(vec.empty());
+  EXPECT_EQ(vec.size(), 0u);
+
+  ASSERT_TRUE(vec.Push(42));
+  ASSERT_TRUE(!vec.empty());
+  EXPECT_EQ(vec.size(), 1u);
+  EXPECT_EQ(vec[0], 42u);
 }
 
 TEST(VectorTest, MoveConstructor) {
@@ -635,6 +645,24 @@
   }
 }
 
+TEST(VectorTest, NotDefaultConstructible) {
+  struct NotDefaultConstructible {
+    explicit NotDefaultConstructible(size_t n) { array.Init(n); }
+    Array<int> array;
+  };
+
+  Vector<NotDefaultConstructible> vec;
+  vec.Push(NotDefaultConstructible(0));
+  vec.Push(NotDefaultConstructible(1));
+  vec.Push(NotDefaultConstructible(2));
+  vec.Push(NotDefaultConstructible(3));
+  EXPECT_EQ(vec.size(), 4u);
+  EXPECT_EQ(0u, vec[0].array.size());
+  EXPECT_EQ(1u, vec[1].array.size());
+  EXPECT_EQ(2u, vec[2].array.size());
+  EXPECT_EQ(3u, vec[3].array.size());
+}
+
 TEST(ReconstructSeqnumTest, Increment) {
   // Test simple cases from the beginning of an epoch with both 8- and 16-bit
   // wire sequence numbers.