Export of internal Abseil changes.

--
2f187776e55fe7741882d64aa4fb04d361dcd1da by Shaindel Schwartz <shaindel@google.com>:

Fix spaces.

PiperOrigin-RevId: 254880665

--
50a2c390c1e56bec574e9418a6d0c5765f2e1d56 by CJ Johnson <johnsoncj@google.com>:

Fixes a ubsan violation bug report: https://github.com/abseil/abseil-cpp/issues/337

PiperOrigin-RevId: 254846112

--
563fee16ee0ac32a93292c3b2d1cf9543bad4758 by CJ Johnson <johnsoncj@google.com>:

In the InlinedVector copy-assignment operator, substitutes-in a call to DeallocateIfAllocated() (which was not previously available)

PiperOrigin-RevId: 254835012

--
d07f4d91b43242c5e8bd90f1e93f55f7972eed04 by Shaindel Schwartz <shaindel@google.com>:

#336

PiperOrigin-RevId: 254833534

--
1ad0fe00169a794176605a897f15fad8625339bd by Shaindel Schwartz <shaindel@google.com>:

#335

PiperOrigin-RevId: 254826748

--
436a29591c60c6ac9bb7b98e4906c0a7466611c1 by Shaindel Schwartz <shaindel@google.com>:

Import of CCTZ from GitHub.

PiperOrigin-RevId: 254820333

--
e782a5387a750319eb6ed5d9927ec2463bd68ebb by CJ Johnson <johnsoncj@google.com>:

Updates the definition of InlinedVector::resize(...) to be exception safe and adds exception safety tests

PiperOrigin-RevId: 254818993

--
6d2f8538fb06a09af47232d86b32dfc020b62133 by CJ Johnson <johnsoncj@google.com>:

Removes unnecessary transaction object from the implementation of InlinedVector::reserve(n)

PiperOrigin-RevId: 254804166

--
9a3a806702679a7442837089469cf171194da776 by Abseil Team <absl-team@google.com>:

Internal Change.

PiperOrigin-RevId: 254489023

--
ded1463ef81f3257645becc6be58df3b433ea21f by CJ Johnson <johnsoncj@google.com>:

Updates the definition of InlinedVector::reserve(size_type) to be exception safe and adds exception safety tests

PiperOrigin-RevId: 254463057
GitOrigin-RevId: 2f187776e55fe7741882d64aa4fb04d361dcd1da
Change-Id: Id41fc5a62c8d71021e803721ecdbfb3ce60ef574

3 files changed, 194 insertions, 69 deletions

diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
index 10881b22..784b07f4 100644
--- a/absl/container/inlined_vector.h
+++ b/absl/container/inlined_vector.h
@@ -467,11 +467,7 @@ class InlinedVector {
     if (IsMemcpyOk::value || other.storage_.GetIsAllocated()) {
       inlined_vector_internal::DestroyElements(storage_.GetAllocPtr(), data(),
                                                size());
-      if (storage_.GetIsAllocated()) {
-        AllocatorTraits::deallocate(*storage_.GetAllocPtr(),
-                                    storage_.GetAllocatedData(),
-                                    storage_.GetAllocatedCapacity());
-      }
+      storage_.DeallocateIfAllocated();
       storage_.MemcpyFrom(other.storage_);
       other.storage_.SetInlinedSize(0);
     } else {
@@ -525,49 +521,13 @@ class InlinedVector {
   // Resizes the inlined vector to contain `n` elements. If `n` is smaller than
   // the inlined vector's current size, extra elements are destroyed. If `n` is
   // larger than the initial size, new elements are value-initialized.
-  void resize(size_type n) {
-    size_type s = size();
-    if (n < s) {
-      erase(begin() + n, end());
-      return;
-    }
-    reserve(n);
-    assert(capacity() >= n);
-
-    // Fill new space with elements constructed in-place.
-    if (storage_.GetIsAllocated()) {
-      UninitializedFill(storage_.GetAllocatedData() + s,
-                        storage_.GetAllocatedData() + n);
-      storage_.SetAllocatedSize(n);
-    } else {
-      UninitializedFill(storage_.GetInlinedData() + s,
-                        storage_.GetInlinedData() + n);
-      storage_.SetInlinedSize(n);
-    }
-  }
+  void resize(size_type n) { storage_.Resize(DefaultValueAdapter(), n); }
 
   // Overload of `InlinedVector::resize()` to resize the inlined vector to
   // contain `n` elements where, if `n` is larger than `size()`, the new values
   // will be copy-constructed from `v`.
   void resize(size_type n, const_reference v) {
-    size_type s = size();
-    if (n < s) {
-      erase(begin() + n, end());
-      return;
-    }
-    reserve(n);
-    assert(capacity() >= n);
-
-    // Fill new space with copies of `v`.
-    if (storage_.GetIsAllocated()) {
-      UninitializedFill(storage_.GetAllocatedData() + s,
-                        storage_.GetAllocatedData() + n, v);
-      storage_.SetAllocatedSize(n);
-    } else {
-      UninitializedFill(storage_.GetInlinedData() + s,
-                        storage_.GetInlinedData() + n, v);
-      storage_.SetInlinedSize(n);
-    }
+    storage_.Resize(CopyValueAdapter(v), n);
   }
 
   // `InlinedVector::insert()`
@@ -784,22 +744,7 @@ class InlinedVector {
   // NOTE: If `n` does not exceed `capacity()`, `reserve()` will have no
   // effects. Otherwise, `reserve()` will reallocate, performing an n-time
   // element-wise move of everything contained.
-  void reserve(size_type n) {
-    if (n <= capacity()) {
-      return;
-    }
-    const size_type s = size();
-    size_type target = (std::max)(static_cast<size_type>(N), n);
-    size_type new_capacity = capacity();
-    while (new_capacity < target) {
-      new_capacity <<= 1;
-    }
-    pointer new_data =
-        AllocatorTraits::allocate(*storage_.GetAllocPtr(), new_capacity);
-    UninitializedCopy(std::make_move_iterator(data()),
-                      std::make_move_iterator(data() + s), new_data);
-    ResetAllocation(new_data, new_capacity, s);
-  }
+  void reserve(size_type n) { storage_.Reserve(n); }
 
   // `InlinedVector::shrink_to_fit()`
   //
diff --git a/absl/container/inlined_vector_exception_safety_test.cc b/absl/container/inlined_vector_exception_safety_test.cc
index e7c47127..1775699e 100644
--- a/absl/container/inlined_vector_exception_safety_test.cc
+++ b/absl/container/inlined_vector_exception_safety_test.cc
@@ -259,6 +259,26 @@ TYPED_TEST(TwoSizeTest, Assign) {
   }));
 }
 
+TYPED_TEST(TwoSizeTest, Resize) {
+  using VecT = typename TypeParam::VecT;
+  using value_type = typename VecT::value_type;
+  constexpr static auto from_size = TypeParam::GetSizeAt(0);
+  constexpr static auto to_size = TypeParam::GetSizeAt(1);
+
+  auto tester = testing::MakeExceptionSafetyTester()
+                    .WithInitialValue(VecT{from_size})
+                    .WithContracts(InlinedVectorInvariants<VecT>,
+                                   testing::strong_guarantee);
+
+  EXPECT_TRUE(tester.Test([](VecT* vec) {
+    vec->resize(to_size);  //
+  }));
+
+  EXPECT_TRUE(tester.Test([](VecT* vec) {
+    vec->resize(to_size, value_type{});  //
+  }));
+}
+
 TYPED_TEST(OneSizeTest, PopBack) {
   using VecT = typename TypeParam::VecT;
   constexpr static auto size = TypeParam::GetSizeAt(0);
@@ -285,6 +305,20 @@ TYPED_TEST(OneSizeTest, Clear) {
   }));
 }
 
+TYPED_TEST(TwoSizeTest, Reserve) {
+  using VecT = typename TypeParam::VecT;
+  constexpr static auto from_size = TypeParam::GetSizeAt(0);
+  constexpr static auto to_capacity = TypeParam::GetSizeAt(1);
+
+  auto tester = testing::MakeExceptionSafetyTester()
+                    .WithInitialValue(VecT{from_size})
+                    .WithContracts(InlinedVectorInvariants<VecT>);
+
+  EXPECT_TRUE(tester.Test([](VecT* vec) {
+    vec->reserve(to_capacity);  //
+  }));
+}
+
 TYPED_TEST(OneSizeTest, ShrinkToFit) {
   using VecT = typename TypeParam::VecT;
   constexpr static auto size = TypeParam::GetSizeAt(0);
diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h
index f117ee0c..a84b5255 100644
--- a/absl/container/internal/inlined_vector.h
+++ b/absl/container/internal/inlined_vector.h
@@ -47,19 +47,23 @@ template <typename AllocatorType, typename ValueType, typename SizeType>
 void DestroyElements(AllocatorType* alloc_ptr, ValueType* destroy_first,
                      SizeType destroy_size) {
   using AllocatorTraits = absl::allocator_traits<AllocatorType>;
-  for (SizeType i = 0; i < destroy_size; ++i) {
-    AllocatorTraits::destroy(*alloc_ptr, destroy_first + i);
-  }
+
+  if (destroy_first != nullptr) {
+    for (auto i = destroy_size; i != 0;) {
+      --i;
+      AllocatorTraits::destroy(*alloc_ptr, destroy_first + i);
+    }
 
 #ifndef NDEBUG
-  // Overwrite unused memory with `0xab` so we can catch uninitialized usage.
-  //
-  // Cast to `void*` to tell the compiler that we don't care that we might be
-  // scribbling on a vtable pointer.
-  void* memory = reinterpret_cast<void*>(destroy_first);
-  size_t memory_size = sizeof(ValueType) * destroy_size;
-  std::memset(memory, 0xab, memory_size);
+    // Overwrite unused memory with `0xab` so we can catch uninitialized usage.
+    //
+    // Cast to `void*` to tell the compiler that we don't care that we might be
+    // scribbling on a vtable pointer.
+    auto* memory_ptr = static_cast<void*>(destroy_first);
+    auto memory_size = sizeof(ValueType) * destroy_size;
+    std::memset(memory_ptr, 0xab, memory_size);
 #endif  // NDEBUG
+  }
 }
 
 template <typename AllocatorType, typename ValueType, typename ValueAdapter,
@@ -191,6 +195,46 @@ class AllocationTransaction {
   size_type capacity_ = 0;
 };
 
+template <typename AllocatorType>
+class ConstructionTransaction {
+  using pointer = typename AllocatorType::pointer;
+  using size_type = typename AllocatorType::size_type;
+
+ public:
+  explicit ConstructionTransaction(AllocatorType* alloc_ptr)
+      : alloc_data_(*alloc_ptr, nullptr) {}
+
+  ConstructionTransaction(const ConstructionTransaction&) = delete;
+  void operator=(const ConstructionTransaction&) = delete;
+
+  template <typename ValueAdapter>
+  void Construct(pointer data, ValueAdapter* values_ptr, size_type size) {
+    inlined_vector_internal::ConstructElements(std::addressof(GetAllocator()),
+                                               data, values_ptr, size);
+    GetData() = data;
+    GetSize() = size;
+  }
+  void Commit() {
+    GetData() = nullptr;
+    GetSize() = 0;
+  }
+
+  ~ConstructionTransaction() {
+    if (GetData() != nullptr) {
+      inlined_vector_internal::DestroyElements(std::addressof(GetAllocator()),
+                                               GetData(), GetSize());
+    }
+  }
+
+ private:
+  AllocatorType& GetAllocator() { return alloc_data_.template get<0>(); }
+  pointer& GetData() { return alloc_data_.template get<1>(); }
+  size_type& GetSize() { return size_; }
+
+  container_internal::CompressedTuple<AllocatorType, pointer> alloc_data_;
+  size_type size_ = 0;
+};
+
 template <typename T, size_t N, typename A>
 class Storage {
  public:
@@ -223,6 +267,8 @@ class Storage {
 
   using AllocationTransaction =
       inlined_vector_internal::AllocationTransaction<allocator_type>;
+  using ConstructionTransaction =
+      inlined_vector_internal::ConstructionTransaction<allocator_type>;
 
   Storage() : metadata_() {}
 
@@ -339,6 +385,11 @@ class Storage {
   template <typename ValueAdapter>
   void Assign(ValueAdapter values, size_type new_size);
 
+  template <typename ValueAdapter>
+  void Resize(ValueAdapter values, size_type new_size);
+
+  void Reserve(size_type requested_capacity);
+
   void ShrinkToFit();
 
  private:
@@ -348,6 +399,16 @@ class Storage {
     return metadata_.template get<1>();
   }
 
+  static size_type LegacyNextCapacityFrom(size_type current_capacity,
+                                          size_type requested_capacity) {
+    // TODO(johnsoncj): Get rid of this old behavior.
+    size_type new_capacity = current_capacity;
+    while (new_capacity < requested_capacity) {
+      new_capacity *= 2;
+    }
+    return new_capacity;
+  }
+
   using Metadata =
       container_internal::CompressedTuple<allocator_type, size_type>;
 
@@ -434,11 +495,70 @@ auto Storage<T, N, A>::Assign(ValueAdapter values, size_type new_size) -> void {
 
   inlined_vector_internal::AssignElements(assign_loop.data(), &values,
                                           assign_loop.size());
+
   inlined_vector_internal::ConstructElements(
       GetAllocPtr(), construct_loop.data(), &values, construct_loop.size());
+
+  inlined_vector_internal::DestroyElements(GetAllocPtr(), destroy_loop.data(),
+                                           destroy_loop.size());
+
+  if (allocation_tx.DidAllocate()) {
+    DeallocateIfAllocated();
+    AcquireAllocation(&allocation_tx);
+    SetIsAllocated();
+  }
+
+  SetSize(new_size);
+}
+
+template <typename T, size_t N, typename A>
+template <typename ValueAdapter>
+auto Storage<T, N, A>::Resize(ValueAdapter values, size_type new_size) -> void {
+  StorageView storage_view = MakeStorageView();
+
+  AllocationTransaction allocation_tx(GetAllocPtr());
+  ConstructionTransaction construction_tx(GetAllocPtr());
+
+  IteratorValueAdapter<MoveIterator> move_values(
+      MoveIterator(storage_view.data));
+
+  absl::Span<value_type> construct_loop;
+  absl::Span<value_type> move_construct_loop;
+  absl::Span<value_type> destroy_loop;
+
+  if (new_size > storage_view.capacity) {
+    pointer new_data = allocation_tx.Allocate(
+        LegacyNextCapacityFrom(storage_view.capacity, new_size));
+
+    // Construct new objects in `new_data`
+    construct_loop = {new_data + storage_view.size,
+                      new_size - storage_view.size};
+
+    // Move all existing objects into `new_data`
+    move_construct_loop = {new_data, storage_view.size};
+
+    // Destroy all existing objects in `storage_view.data`
+    destroy_loop = {storage_view.data, storage_view.size};
+  } else if (new_size > storage_view.size) {
+    // Construct new objects in `storage_view.data`
+    construct_loop = {storage_view.data + storage_view.size,
+                      new_size - storage_view.size};
+  } else {
+    // Destroy end `storage_view.size - new_size` objects in `storage_view.data`
+    destroy_loop = {storage_view.data + new_size, storage_view.size - new_size};
+  }
+
+  construction_tx.Construct(construct_loop.data(), &values,
+                            construct_loop.size());
+
+  inlined_vector_internal::ConstructElements(
+      GetAllocPtr(), move_construct_loop.data(), &move_values,
+      move_construct_loop.size());
+
   inlined_vector_internal::DestroyElements(GetAllocPtr(), destroy_loop.data(),
                                            destroy_loop.size());
 
+  construction_tx.Commit();
   if (allocation_tx.DidAllocate()) {
     DeallocateIfAllocated();
     AcquireAllocation(&allocation_tx);
@@ -449,6 +569,31 @@ auto Storage<T, N, A>::Assign(ValueAdapter values, size_type new_size) -> void {
 }
 
 template <typename T, size_t N, typename A>
+auto Storage<T, N, A>::Reserve(size_type requested_capacity) -> void {
+  StorageView storage_view = MakeStorageView();
+
+  if (ABSL_PREDICT_FALSE(requested_capacity <= storage_view.capacity)) return;
+
+  AllocationTransaction allocation_tx(GetAllocPtr());
+
+  IteratorValueAdapter<MoveIterator> move_values(
+      MoveIterator(storage_view.data));
+
+  pointer new_data = allocation_tx.Allocate(
+      LegacyNextCapacityFrom(storage_view.capacity, requested_capacity));
+
+  inlined_vector_internal::ConstructElements(GetAllocPtr(), new_data,
+                                             &move_values, storage_view.size);
+
+  inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data,
+                                           storage_view.size);
+
+  DeallocateIfAllocated();
+  AcquireAllocation(&allocation_tx);
+  SetIsAllocated();
+}
+
+template <typename T, size_t N, typename A>
 auto Storage<T, N, A>::ShrinkToFit() -> void {
   // May only be called on allocated instances!
   assert(GetIsAllocated());
@@ -484,6 +629,7 @@ auto Storage<T, N, A>::ShrinkToFit() -> void {
 
   inlined_vector_internal::DestroyElements(GetAllocPtr(), storage_view.data,
                                            storage_view.size);
+
   AllocatorTraits::deallocate(*GetAllocPtr(), storage_view.data,
                               storage_view.capacity);