Merge new upstream LTS 20230802.0

1 files changed, 167 insertions, 79 deletions

diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
index 7058f375..04e2c385 100644
--- a/absl/container/inlined_vector.h
+++ b/absl/container/inlined_vector.h
@@ -77,8 +77,6 @@ class InlinedVector {
   template <typename TheA>
   using MoveIterator = inlined_vector_internal::MoveIterator<TheA>;
   template <typename TheA>
-  using IsMemcpyOk = inlined_vector_internal::IsMemcpyOk<TheA>;
-  template <typename TheA>
   using IsMoveAssignOk = inlined_vector_internal::IsMoveAssignOk<TheA>;
 
   template <typename TheA, typename Iterator>
@@ -182,14 +180,23 @@ class InlinedVector {
   // provided `allocator`.
   InlinedVector(const InlinedVector& other, const allocator_type& allocator)
       : storage_(allocator) {
+    // Fast path: if the other vector is empty, there's nothing for us to do.
     if (other.empty()) {
-      // Empty; nothing to do.
-    } else if (IsMemcpyOk<A>::value && !other.storage_.GetIsAllocated()) {
-      // Memcpy-able and do not need allocation.
+      return;
+    }
+
+    // Fast path: if the value type is trivially copy constructible, we know the
+    // allocator doesn't do anything fancy, and there is nothing on the heap
+    // then we know it is legal for us to simply memcpy the other vector's
+    // inlined bytes to form our copy of its elements.
+    if (absl::is_trivially_copy_constructible<value_type>::value &&
+        std::is_same<A, std::allocator<value_type>>::value &&
+        !other.storage_.GetIsAllocated()) {
       storage_.MemcpyFrom(other.storage_);
-    } else {
-      storage_.InitFrom(other.storage_);
+      return;
     }
+
+    storage_.InitFrom(other.storage_);
   }
 
   // Creates an inlined vector by moving in the contents of `other` without
@@ -210,26 +217,38 @@ class InlinedVector {
       absl::allocator_is_nothrow<allocator_type>::value ||
       std::is_nothrow_move_constructible<value_type>::value)
       : storage_(other.storage_.GetAllocator()) {
-    if (IsMemcpyOk<A>::value) {
+    // Fast path: if the value type can be trivially relocated (i.e. moved from
+    // and destroyed), and we know the allocator doesn't do anything fancy, then
+    // it's safe for us to simply adopt the contents of the storage for `other`
+    // and remove its own reference to them. It's as if we had individually
+    // move-constructed each value and then destroyed the original.
+    if (absl::is_trivially_relocatable<value_type>::value &&
+        std::is_same<A, std::allocator<value_type>>::value) {
       storage_.MemcpyFrom(other.storage_);
-
       other.storage_.SetInlinedSize(0);
-    } else if (other.storage_.GetIsAllocated()) {
+      return;
+    }
+
+    // Fast path: if the other vector is on the heap, we can simply take over
+    // its allocation.
+    if (other.storage_.GetIsAllocated()) {
       storage_.SetAllocation({other.storage_.GetAllocatedData(),
                               other.storage_.GetAllocatedCapacity()});
       storage_.SetAllocatedSize(other.storage_.GetSize());
 
       other.storage_.SetInlinedSize(0);
-    } else {
-      IteratorValueAdapter<A, MoveIterator<A>> other_values(
-          MoveIterator<A>(other.storage_.GetInlinedData()));
+      return;
+    }
 
-      inlined_vector_internal::ConstructElements<A>(
-          storage_.GetAllocator(), storage_.GetInlinedData(), other_values,
-          other.storage_.GetSize());
+    // Otherwise we must move each element individually.
+    IteratorValueAdapter<A, MoveIterator<A>> other_values(
+        MoveIterator<A>(other.storage_.GetInlinedData()));
 
-      storage_.SetInlinedSize(other.storage_.GetSize());
-    }
+    inlined_vector_internal::ConstructElements<A>(
+        storage_.GetAllocator(), storage_.GetInlinedData(), other_values,
+        other.storage_.GetSize());
+
+    storage_.SetInlinedSize(other.storage_.GetSize());
   }
 
   // Creates an inlined vector by moving in the contents of `other` with a copy
@@ -244,22 +263,34 @@ class InlinedVector {
       const allocator_type&
           allocator) noexcept(absl::allocator_is_nothrow<allocator_type>::value)
       : storage_(allocator) {
-    if (IsMemcpyOk<A>::value) {
+    // Fast path: if the value type can be trivially relocated (i.e. moved from
+    // and destroyed), and we know the allocator doesn't do anything fancy, then
+    // it's safe for us to simply adopt the contents of the storage for `other`
+    // and remove its own reference to them. It's as if we had individually
+    // move-constructed each value and then destroyed the original.
+    if (absl::is_trivially_relocatable<value_type>::value &&
+        std::is_same<A, std::allocator<value_type>>::value) {
       storage_.MemcpyFrom(other.storage_);
-
       other.storage_.SetInlinedSize(0);
-    } else if ((storage_.GetAllocator() == other.storage_.GetAllocator()) &&
-               other.storage_.GetIsAllocated()) {
+      return;
+    }
+
+    // Fast path: if the other vector is on the heap and shared the same
+    // allocator, we can simply take over its allocation.
+    if ((storage_.GetAllocator() == other.storage_.GetAllocator()) &&
+        other.storage_.GetIsAllocated()) {
       storage_.SetAllocation({other.storage_.GetAllocatedData(),
                               other.storage_.GetAllocatedCapacity()});
       storage_.SetAllocatedSize(other.storage_.GetSize());
 
       other.storage_.SetInlinedSize(0);
-    } else {
-      storage_.Initialize(IteratorValueAdapter<A, MoveIterator<A>>(
-                              MoveIterator<A>(other.data())),
-                          other.size());
+      return;
     }
+
+    // Otherwise we must move each element individually.
+    storage_.Initialize(
+        IteratorValueAdapter<A, MoveIterator<A>>(MoveIterator<A>(other.data())),
+        other.size());
   }
 
   ~InlinedVector() {}
@@ -310,7 +341,7 @@ class InlinedVector {
   // can be used to access and modify the contained elements.
   //
   // NOTE: only elements within [`data()`, `data() + size()`) are valid.
-  pointer data() noexcept {
+  pointer data() noexcept ABSL_ATTRIBUTE_LIFETIME_BOUND {
     return storage_.GetIsAllocated() ? storage_.GetAllocatedData()
                                      : storage_.GetInlinedData();
   }
@@ -320,7 +351,7 @@ class InlinedVector {
   // modify the contained elements.
   //
   // NOTE: only elements within [`data()`, `data() + size()`) are valid.
-  const_pointer data() const noexcept {
+  const_pointer data() const noexcept ABSL_ATTRIBUTE_LIFETIME_BOUND {
     return storage_.GetIsAllocated() ? storage_.GetAllocatedData()
                                      : storage_.GetInlinedData();
   }
@@ -328,14 +359,14 @@ class InlinedVector {
   // `InlinedVector::operator[](...)`
   //
   // Returns a `reference` to the `i`th element of the inlined vector.
-  reference operator[](size_type i) {
+  reference operator[](size_type i) ABSL_ATTRIBUTE_LIFETIME_BOUND {
     ABSL_HARDENING_ASSERT(i < size());
     return data()[i];
   }
 
   // Overload of `InlinedVector::operator[](...)` that returns a
   // `const_reference` to the `i`th element of the inlined vector.
-  const_reference operator[](size_type i) const {
+  const_reference operator[](size_type i) const ABSL_ATTRIBUTE_LIFETIME_BOUND {
     ABSL_HARDENING_ASSERT(i < size());
     return data()[i];
   }
@@ -346,7 +377,7 @@ class InlinedVector {
   //
   // NOTE: if `i` is not within the required range of `InlinedVector::at(...)`,
   // in both debug and non-debug builds, `std::out_of_range` will be thrown.
-  reference at(size_type i) {
+  reference at(size_type i) ABSL_ATTRIBUTE_LIFETIME_BOUND {
     if (ABSL_PREDICT_FALSE(i >= size())) {
       base_internal::ThrowStdOutOfRange(
           "`InlinedVector::at(size_type)` failed bounds check");
@@ -359,7 +390,7 @@ class InlinedVector {
   //
   // NOTE: if `i` is not within the required range of `InlinedVector::at(...)`,
   // in both debug and non-debug builds, `std::out_of_range` will be thrown.
-  const_reference at(size_type i) const {
+  const_reference at(size_type i) const ABSL_ATTRIBUTE_LIFETIME_BOUND {
     if (ABSL_PREDICT_FALSE(i >= size())) {
       base_internal::ThrowStdOutOfRange(
           "`InlinedVector::at(size_type) const` failed bounds check");
@@ -370,14 +401,14 @@ class InlinedVector {
   // `InlinedVector::front()`
   //
   // Returns a `reference` to the first element of the inlined vector.
-  reference front() {
+  reference front() ABSL_ATTRIBUTE_LIFETIME_BOUND {
     ABSL_HARDENING_ASSERT(!empty());
     return data()[0];
   }
 
   // Overload of `InlinedVector::front()` that returns a `const_reference` to
   // the first element of the inlined vector.
-  const_reference front() const {
+  const_reference front() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
     ABSL_HARDENING_ASSERT(!empty());
     return data()[0];
   }
@@ -385,14 +416,14 @@ class InlinedVector {
   // `InlinedVector::back()`
   //
   // Returns a `reference` to the last element of the inlined vector.
-  reference back() {
+  reference back() ABSL_ATTRIBUTE_LIFETIME_BOUND {
     ABSL_HARDENING_ASSERT(!empty());
     return data()[size() - 1];
   }
 
   // Overload of `InlinedVector::back()` that returns a `const_reference` to the
   // last element of the inlined vector.
-  const_reference back() const {
+  const_reference back() const ABSL_ATTRIBUTE_LIFETIME_BOUND {
     ABSL_HARDENING_ASSERT(!empty());
     return data()[size() - 1];
   }
@@ -400,63 +431,82 @@ class InlinedVector {
   // `InlinedVector::begin()`
   //
   // Returns an `iterator` to the beginning of the inlined vector.
-  iterator begin() noexcept { return data(); }
+  iterator begin() noexcept ABSL_ATTRIBUTE_LIFETIME_BOUND { return data(); }
 
   // Overload of `InlinedVector::begin()` that returns a `const_iterator` to
   // the beginning of the inlined vector.
-  const_iterator begin() const noexcept { return data(); }
+  const_iterator begin() const noexcept ABSL_ATTRIBUTE_LIFETIME_BOUND {
+    return data();
+  }
 
   // `InlinedVector::end()`
   //
   // Returns an `iterator` to the end of the inlined vector.
-  iterator end() noexcept { return data() + size(); }
+  iterator end() noexcept ABSL_ATTRIBUTE_LIFETIME_BOUND {
+    return data() + size();
+  }
 
   // Overload of `InlinedVector::end()` that returns a `const_iterator` to the
   // end of the inlined vector.
-  const_iterator end() const noexcept { return data() + size(); }
+  const_iterator end() const noexcept ABSL_ATTRIBUTE_LIFETIME_BOUND {
+    return data() + size();
+  }
 
   // `InlinedVector::cbegin()`
   //
   // Returns a `const_iterator` to the beginning of the inlined vector.
-  const_iterator cbegin() const noexcept { return begin(); }
+  const_iterator cbegin() const noexcept ABSL_ATTRIBUTE_LIFETIME_BOUND {
+    return begin();
+  }
 
   // `InlinedVector::cend()`
   //
   // Returns a `const_iterator` to the end of the inlined vector.
-  const_iterator cend() const noexcept { return end(); }
+  const_iterator cend() const noexcept ABSL_ATTRIBUTE_LIFETIME_BOUND {
+    return end();
+  }
 
   // `InlinedVector::rbegin()`
   //
   // Returns a `reverse_iterator` from the end of the inlined vector.
-  reverse_iterator rbegin() noexcept { return reverse_iterator(end()); }
+  reverse_iterator rbegin() noexcept ABSL_ATTRIBUTE_LIFETIME_BOUND {
+    return reverse_iterator(end());
+  }
 
   // Overload of `InlinedVector::rbegin()` that returns a
   // `const_reverse_iterator` from the end of the inlined vector.
-  const_reverse_iterator rbegin() const noexcept {
+  const_reverse_iterator rbegin() const noexcept ABSL_ATTRIBUTE_LIFETIME_BOUND {
     return const_reverse_iterator(end());
   }
 
   // `InlinedVector::rend()`
   //
   // Returns a `reverse_iterator` from the beginning of the inlined vector.
-  reverse_iterator rend() noexcept { return reverse_iterator(begin()); }
+  reverse_iterator rend() noexcept ABSL_ATTRIBUTE_LIFETIME_BOUND {
+    return reverse_iterator(begin());
+  }
 
   // Overload of `InlinedVector::rend()` that returns a `const_reverse_iterator`
   // from the beginning of the inlined vector.
-  const_reverse_iterator rend() const noexcept {
+  const_reverse_iterator rend() const noexcept ABSL_ATTRIBUTE_LIFETIME_BOUND {
     return const_reverse_iterator(begin());
   }
 
   // `InlinedVector::crbegin()`
   //
   // Returns a `const_reverse_iterator` from the end of the inlined vector.
-  const_reverse_iterator crbegin() const noexcept { return rbegin(); }
+  const_reverse_iterator crbegin() const noexcept
+      ABSL_ATTRIBUTE_LIFETIME_BOUND {
+    return rbegin();
+  }
 
   // `InlinedVector::crend()`
   //
   // Returns a `const_reverse_iterator` from the beginning of the inlined
   // vector.
-  const_reverse_iterator crend() const noexcept { return rend(); }
+  const_reverse_iterator crend() const noexcept ABSL_ATTRIBUTE_LIFETIME_BOUND {
+    return rend();
+  }
 
   // `InlinedVector::get_allocator()`
   //
@@ -566,20 +616,23 @@ class InlinedVector {
   //
   // Inserts a copy of `v` at `pos`, returning an `iterator` to the newly
   // inserted element.
-  iterator insert(const_iterator pos, const_reference v) {
+  iterator insert(const_iterator pos,
+                  const_reference v) ABSL_ATTRIBUTE_LIFETIME_BOUND {
     return emplace(pos, v);
   }
 
   // Overload of `InlinedVector::insert(...)` that inserts `v` at `pos` using
   // move semantics, returning an `iterator` to the newly inserted element.
-  iterator insert(const_iterator pos, value_type&& v) {
+  iterator insert(const_iterator pos,
+                  value_type&& v) ABSL_ATTRIBUTE_LIFETIME_BOUND {
     return emplace(pos, std::move(v));
   }
 
   // Overload of `InlinedVector::insert(...)` that inserts `n` contiguous copies
   // of `v` starting at `pos`, returning an `iterator` pointing to the first of
   // the newly inserted elements.
-  iterator insert(const_iterator pos, size_type n, const_reference v) {
+  iterator insert(const_iterator pos, size_type n,
+                  const_reference v) ABSL_ATTRIBUTE_LIFETIME_BOUND {
     ABSL_HARDENING_ASSERT(pos >= begin());
     ABSL_HARDENING_ASSERT(pos <= end());
 
@@ -607,7 +660,8 @@ class InlinedVector {
   // Overload of `InlinedVector::insert(...)` that inserts copies of the
   // elements of `list` starting at `pos`, returning an `iterator` pointing to
   // the first of the newly inserted elements.
-  iterator insert(const_iterator pos, std::initializer_list<value_type> list) {
+  iterator insert(const_iterator pos, std::initializer_list<value_type> list)
+      ABSL_ATTRIBUTE_LIFETIME_BOUND {
     return insert(pos, list.begin(), list.end());
   }
 
@@ -619,7 +673,7 @@ class InlinedVector {
   template <typename ForwardIterator,
             EnableIfAtLeastForwardIterator<ForwardIterator> = 0>
   iterator insert(const_iterator pos, ForwardIterator first,
-                  ForwardIterator last) {
+                  ForwardIterator last) ABSL_ATTRIBUTE_LIFETIME_BOUND {
     ABSL_HARDENING_ASSERT(pos >= begin());
     ABSL_HARDENING_ASSERT(pos <= end());
 
@@ -639,7 +693,8 @@ class InlinedVector {
   // NOTE: this overload is for iterators that are "input" category.
   template <typename InputIterator,
             DisableIfAtLeastForwardIterator<InputIterator> = 0>
-  iterator insert(const_iterator pos, InputIterator first, InputIterator last) {
+  iterator insert(const_iterator pos, InputIterator first,
+                  InputIterator last) ABSL_ATTRIBUTE_LIFETIME_BOUND {
     ABSL_HARDENING_ASSERT(pos >= begin());
     ABSL_HARDENING_ASSERT(pos <= end());
 
@@ -656,7 +711,8 @@ class InlinedVector {
   // Constructs and inserts an element using `args...` in the inlined vector at
   // `pos`, returning an `iterator` pointing to the newly emplaced element.
   template <typename... Args>
-  iterator emplace(const_iterator pos, Args&&... args) {
+  iterator emplace(const_iterator pos,
+                   Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND {
     ABSL_HARDENING_ASSERT(pos >= begin());
     ABSL_HARDENING_ASSERT(pos <= end());
 
@@ -684,7 +740,7 @@ class InlinedVector {
   // Constructs and inserts an element using `args...` in the inlined vector at
   // `end()`, returning a `reference` to the newly emplaced element.
   template <typename... Args>
-  reference emplace_back(Args&&... args) {
+  reference emplace_back(Args&&... args) ABSL_ATTRIBUTE_LIFETIME_BOUND {
     return storage_.EmplaceBack(std::forward<Args>(args)...);
   }
 
@@ -714,8 +770,8 @@ class InlinedVector {
   // Erases the element at `pos`, returning an `iterator` pointing to where the
   // erased element was located.
   //
-  // NOTE: may return `end()`, which is not dereferencable.
-  iterator erase(const_iterator pos) {
+  // NOTE: may return `end()`, which is not dereferenceable.
+  iterator erase(const_iterator pos) ABSL_ATTRIBUTE_LIFETIME_BOUND {
     ABSL_HARDENING_ASSERT(pos >= begin());
     ABSL_HARDENING_ASSERT(pos < end());
 
@@ -726,8 +782,9 @@ class InlinedVector {
   // range [`from`, `to`), returning an `iterator` pointing to where the first
   // erased element was located.
   //
-  // NOTE: may return `end()`, which is not dereferencable.
-  iterator erase(const_iterator from, const_iterator to) {
+  // NOTE: may return `end()`, which is not dereferenceable.
+  iterator erase(const_iterator from,
+                 const_iterator to) ABSL_ATTRIBUTE_LIFETIME_BOUND {
     ABSL_HARDENING_ASSERT(from >= begin());
     ABSL_HARDENING_ASSERT(from <= to);
     ABSL_HARDENING_ASSERT(to <= end());
@@ -784,39 +841,70 @@ class InlinedVector {
   friend H AbslHashValue(H h, const absl::InlinedVector<TheT, TheN, TheA>& a);
 
   void MoveAssignment(MemcpyPolicy, InlinedVector&& other) {
+    // Assumption check: we shouldn't be told to use memcpy to implement move
+    // assignment unless we have trivially destructible elements and an
+    // allocator that does nothing fancy.
+    static_assert(absl::is_trivially_destructible<value_type>::value, "");
+    static_assert(std::is_same<A, std::allocator<value_type>>::value, "");
+
+    // Throw away our existing heap allocation, if any. There is no need to
+    // destroy the existing elements one by one because we know they are
+    // trivially destructible.
+    storage_.DeallocateIfAllocated();
+
+    // Adopt the other vector's inline elements or heap allocation.
+    storage_.MemcpyFrom(other.storage_);
+    other.storage_.SetInlinedSize(0);
+  }
+
+  // Destroy our existing elements, if any, and adopt the heap-allocated
+  // elements of the other vector.
+  //
+  // REQUIRES: other.storage_.GetIsAllocated()
+  void DestroyExistingAndAdopt(InlinedVector&& other) {
+    ABSL_HARDENING_ASSERT(other.storage_.GetIsAllocated());
+
     inlined_vector_internal::DestroyAdapter<A>::DestroyElements(
         storage_.GetAllocator(), data(), size());
     storage_.DeallocateIfAllocated();
-    storage_.MemcpyFrom(other.storage_);
 
+    storage_.MemcpyFrom(other.storage_);
     other.storage_.SetInlinedSize(0);
   }
 
   void MoveAssignment(ElementwiseAssignPolicy, InlinedVector&& other) {
+    // Fast path: if the other vector is on the heap then we don't worry about
+    // actually move-assigning each element. Instead we only throw away our own
+    // existing elements and adopt the heap allocation of the other vector.
     if (other.storage_.GetIsAllocated()) {
-      MoveAssignment(MemcpyPolicy{}, std::move(other));
-    } else {
-      storage_.Assign(IteratorValueAdapter<A, MoveIterator<A>>(
-                          MoveIterator<A>(other.storage_.GetInlinedData())),
-                      other.size());
+      DestroyExistingAndAdopt(std::move(other));
+      return;
     }
+
+    storage_.Assign(IteratorValueAdapter<A, MoveIterator<A>>(
+                        MoveIterator<A>(other.storage_.GetInlinedData())),
+                    other.size());
   }
 
   void MoveAssignment(ElementwiseConstructPolicy, InlinedVector&& other) {
+    // Fast path: if the other vector is on the heap then we don't worry about
+    // actually move-assigning each element. Instead we only throw away our own
+    // existing elements and adopt the heap allocation of the other vector.
     if (other.storage_.GetIsAllocated()) {
-      MoveAssignment(MemcpyPolicy{}, std::move(other));
-    } else {
-      inlined_vector_internal::DestroyAdapter<A>::DestroyElements(
-          storage_.GetAllocator(), data(), size());
-      storage_.DeallocateIfAllocated();
-
-      IteratorValueAdapter<A, MoveIterator<A>> other_values(
-          MoveIterator<A>(other.storage_.GetInlinedData()));
-      inlined_vector_internal::ConstructElements<A>(
-          storage_.GetAllocator(), storage_.GetInlinedData(), other_values,
-          other.storage_.GetSize());
-      storage_.SetInlinedSize(other.storage_.GetSize());
+      DestroyExistingAndAdopt(std::move(other));
+      return;
     }
+
+    inlined_vector_internal::DestroyAdapter<A>::DestroyElements(
+        storage_.GetAllocator(), data(), size());
+    storage_.DeallocateIfAllocated();
+
+    IteratorValueAdapter<A, MoveIterator<A>> other_values(
+        MoveIterator<A>(other.storage_.GetInlinedData()));
+    inlined_vector_internal::ConstructElements<A>(
+        storage_.GetAllocator(), storage_.GetInlinedData(), other_values,
+        other.storage_.GetSize());
+    storage_.SetInlinedSize(other.storage_.GetSize());
   }
 
   Storage storage_;
@@ -843,7 +931,7 @@ bool operator==(const absl::InlinedVector<T, N, A>& a,
                 const absl::InlinedVector<T, N, A>& b) {
   auto a_data = a.data();
   auto b_data = b.data();
-  return absl::equal(a_data, a_data + a.size(), b_data, b_data + b.size());
+  return std::equal(a_data, a_data + a.size(), b_data, b_data + b.size());
 }
 
 // `operator!=(...)`