inlined_vector: get rid of IsMemcpyOk.

This type trait had no precise definition, and indeed not even any documentation
at all. Giving the ill-defined concept a name was harmful, because it obscured
several places where the concept was used too conservatively, or even flat-out
incorrectly.

This CL has no behavior change: it simply expands IsMemcpyOk to the same
conditions it previously had. It leaves TODOs for each place where this was too
conservative or incorrect.

PiperOrigin-RevId: 519278325
Change-Id: I25bc89f299f6e40b5c3bce7370ed90f33a95612f

2 files changed, 229 insertions, 60 deletions

diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
index 42a4f946..f5b819a1 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,33 @@ 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.
+    //
+    // TODO(b/274984172): the condition on copy-assignability is here only for
+    // historical reasons. It doesn't make semantic sense: we don't need to be
+    // able to copy assign here, we are doing an "as-if" copy construction.
+    //
+    // TODO(b/274984172): the condition on trivial destructibility is here only
+    // for historical reasons. It doesn't make sense: there is no destruction
+    // here.
+    if (absl::is_trivially_copy_constructible<value_type>::value &&
+        std::is_same<A, std::allocator<value_type>>::value &&
+        absl::is_trivially_copy_assignable<value_type>::value &&
+        absl::is_trivially_destructible<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 +227,57 @@ 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 trivally move constructed 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.
+    //
+    // TODO(b/274984172): we check for copy-constructibility here only for
+    // historical reasons. This is too strict: we are simulating move
+    // construction here. In fact this is arguably incorrect, since in theory a
+    // type might be trivially copy-constructible but not trivially
+    // move-constructible.
+    //
+    // TODO(b/274984172): the condition on copy-assignability is here only for
+    // historical reasons. It doesn't make semantic sense: we don't need to be
+    // able to copy assign here, we are doing an "as-if" move construction.
+    //
+    // TODO(b/274984172): a move construction followed by destroying the source
+    // is a "relocation" in the language of P1144R4. So actually the minimum
+    // condition we need here (in addition to the allocator) is "trivially
+    // relocatable". Relaxing this would allow using memcpy with types like
+    // std::unique_ptr that opt in to declaring themselves trivially relocatable
+    // despite not being trivially move-constructible and/oror destructible.
+    if (absl::is_trivially_copy_constructible<value_type>::value &&
+        absl::is_trivially_destructible<value_type>::value &&
+        std::is_same<A, std::allocator<value_type>>::value &&
+        absl::is_trivially_copy_assignable<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 +292,53 @@ 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 trivally move constructed 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.
+    //
+    // TODO(b/274984172): we check for copy-constructibility here only for
+    // historical reasons. This is too strict: we are simulating move
+    // construction here. In fact this is arguably incorrect, since in theory a
+    // type might be trivially copy-constructible but not trivially
+    // move-constructible.
+    //
+    // TODO(b/274984172): the condition on copy-assignability is here only for
+    // historical reasons. It doesn't make semantic sense: we don't need to be
+    // able to copy assign here, we are doing an "as-if" move construction.
+    //
+    // TODO(b/274984172): a move construction followed by destroying the source
+    // is a "relocation" in the language of P1144R4. So actually the minimum
+    // condition we need here (in addition to the allocator) is "trivially
+    // relocatable". Relaxing this would allow using memcpy with types like
+    // std::unique_ptr that opt in to declaring themselves trivially relocatable
+    // despite not being trivially move-constructible and/oror destructible.
+    if (absl::is_trivially_copy_constructible<value_type>::value &&
+        absl::is_trivially_destructible<value_type>::value &&
+        std::is_same<A, std::allocator<value_type>>::value &&
+        absl::is_trivially_copy_assignable<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() {}
@@ -784,6 +863,10 @@ class InlinedVector {
   friend H AbslHashValue(H h, const absl::InlinedVector<TheT, TheN, TheA>& a);
 
   void MoveAssignment(MemcpyPolicy, InlinedVector&& other) {
+    // TODO(b/274984172): we shouldn't need to do this. We already know the
+    // elements are trivially destructible when our move-assignment policy is
+    // MemcpyPolicy. Except the other overloads of MoveAssignment call this one.
+    // Make them not.
     inlined_vector_internal::DestroyAdapter<A>::DestroyElements(
         storage_.GetAllocator(), data(), size());
     storage_.DeallocateIfAllocated();
@@ -793,30 +876,38 @@ class InlinedVector {
   }
 
   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());
+      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());
+      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_;
diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h
index 0398f530..3cd69b55 100644
--- a/absl/container/internal/inlined_vector.h
+++ b/absl/container/internal/inlined_vector.h
@@ -77,13 +77,6 @@ using IsAtLeastForwardIterator = std::is_convertible<
     std::forward_iterator_tag>;
 
 template <typename A>
-using IsMemcpyOk =
-    absl::conjunction<std::is_same<A, std::allocator<ValueType<A>>>,
-                      absl::is_trivially_copy_constructible<ValueType<A>>,
-                      absl::is_trivially_copy_assignable<ValueType<A>>,
-                      absl::is_trivially_destructible<ValueType<A>>>;
-
-template <typename A>
 using IsMoveAssignOk = std::is_move_assignable<ValueType<A>>;
 template <typename A>
 using IsSwapOk = absl::type_traits_internal::IsSwappable<ValueType<A>>;
@@ -308,11 +301,51 @@ class Storage {
   struct ElementwiseConstructPolicy {};
 
   using MoveAssignmentPolicy = absl::conditional_t<
-      IsMemcpyOk<A>::value, MemcpyPolicy,
+      // Fast path: if the value type can be trivally move assigned 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-assigned each value and then destroyed the original.
+      //
+      // TODO(b/274984172): we check for copy-assignability here only for
+      // historical reasons. This is too strict: we are simulating move
+      // assignment here.
+      //
+      // TODO(b/274984172): the condition on copy-constructibility is here only
+      // for historical reasons. It doesn't make semantic sense: we don't need
+      // to be able to copy construct here, we are doing an "as-if" move
+      // assignment.
+      absl::conjunction<
+          absl::is_trivially_copy_assignable<ValueType<A>>,
+          absl::is_trivially_destructible<ValueType<A>>,
+          std::is_same<A, std::allocator<ValueType<A>>>,
+          absl::is_trivially_copy_constructible<ValueType<A>>>::value,
+      MemcpyPolicy,
+      // Otherwise we use move assignment if possible. If not, we simulate
+      // move assignment using move construction.
+      //
+      // Note that this is in contrast to e.g. std::vector and std::optional,
+      // which are themselves not move-assignable when their contained type is
+      // not.
       absl::conditional_t<IsMoveAssignOk<A>::value, ElementwiseAssignPolicy,
                           ElementwiseConstructPolicy>>;
-  using SwapPolicy = absl::conditional_t<
-      IsMemcpyOk<A>::value, MemcpyPolicy,
+
+  // The policy to be used specifically when swapping inlined elements.
+  using SwapInlinedElementsPolicy = absl::conditional_t<
+      // Fast path: if the value type can be trivally move constructed/assigned
+      // and destroyed, and we know the allocator doesn't do anything fancy,
+      // then it's safe for us to simply swap the bytes in the inline storage.
+      // It's as if we had move-constructed a temporary vector, move-assigned
+      // one to the other, then move-assigned the first from the temporary.
+      //
+      // TODO(b/274984172): we check for copy-constructability and
+      // -assignability here only for historical reasons. This is too strict: we
+      // are simulating move operations here.
+      absl::conjunction<absl::is_trivially_copy_constructible<ValueType<A>>,
+                        absl::is_trivially_copy_assignable<ValueType<A>>,
+                        absl::is_trivially_destructible<ValueType<A>>,
+                        std::is_same<A, std::allocator<ValueType<A>>>>::value,
+      MemcpyPolicy,
       absl::conditional_t<IsSwapOk<A>::value, ElementwiseSwapPolicy,
                           ElementwiseConstructPolicy>>;
 
@@ -335,14 +368,26 @@ class Storage {
       : metadata_(allocator, /* size and is_allocated */ 0u) {}
 
   ~Storage() {
+    // Fast path: if we are empty and not allocated, there's nothing to do.
     if (GetSizeAndIsAllocated() == 0) {
-      // Empty and not allocated; nothing to do.
-    } else if (IsMemcpyOk<A>::value) {
-      // No destructors need to be run; just deallocate if necessary.
+      return;
+    }
+
+    // Fast path: if no destructors need to be run and we know the allocator
+    // doesn't do anything fancy, then all we need to do is allocate (and maybe
+    // not even that).
+    //
+    // TODO(b/274984172): the conditions on copy constructibility/assignability
+    // are unnecessary, and are here only for historical reasons. Remove them.
+    if (absl::is_trivially_destructible<ValueType<A>>::value &&
+        std::is_same<A, std::allocator<ValueType<A>>>::value &&
+        absl::is_trivially_copy_constructible<ValueType<A>>::value &&
+        absl::is_trivially_copy_assignable<ValueType<A>>::value) {
       DeallocateIfAllocated();
-    } else {
-      DestroyContents();
+      return;
     }
+
+    DestroyContents();
   }
 
   // ---------------------------------------------------------------------------
@@ -461,8 +506,25 @@ class Storage {
   }
 
   void MemcpyFrom(const Storage& other_storage) {
-    ABSL_HARDENING_ASSERT(IsMemcpyOk<A>::value ||
-                          other_storage.GetIsAllocated());
+    // Assumption check: it doesn't make sense to memcpy inlined elements unless
+    // we know the allocator doesn't do anything fancy, and one of the following
+    // holds:
+    //
+    //  *  It's possible to trivially move construct/assign the elements and
+    //     then destroy the source.
+    //
+    //  *  It's possible to trivially copy construct/assign the elements.
+    //
+    // TODO(b/274984172): the conditions here, preserved from historical ones,
+    // don't actually implement this. They are far too conservative (they don't
+    // work for move-only types, and require both copyability and
+    // assignability).
+    ABSL_HARDENING_ASSERT(
+        other_storage.GetIsAllocated() ||
+        (std::is_same<A, std::allocator<ValueType<A>>>::value &&
+         absl::is_trivially_copy_constructible<ValueType<A>>::value &&
+         absl::is_trivially_copy_assignable<ValueType<A>>::value &&
+         absl::is_trivially_destructible<ValueType<A>>::value));
 
     GetSizeAndIsAllocated() = other_storage.GetSizeAndIsAllocated();
     data_ = other_storage.data_;
@@ -542,13 +604,29 @@ void Storage<T, N, A>::InitFrom(const Storage& other) {
     dst = allocation.data;
     src = other.GetAllocatedData();
   }
-  if (IsMemcpyOk<A>::value) {
+
+  // Fast path: if the value type is trivially copy constructible and we know
+  // the allocator doesn't do anything fancy, then we know it is legal for us to
+  // simply memcpy the other vector's elements.
+  //
+  // TODO(b/274984172): the condition on copy-assignability is here only for
+  // historical reasons. It doesn't make semantic sense: we don't need to be
+  // able to copy assign here, we are doing an "as-if" copy construction.
+  //
+  // TODO(b/274984172): the condition on trivial destructibility is here only
+  // for historical reasons. It doesn't make sense: there is no destruction
+  // here.
+  if (absl::is_trivially_copy_constructible<ValueType<A>>::value &&
+      std::is_same<A, std::allocator<ValueType<A>>>::value &&
+      absl::is_trivially_copy_assignable<ValueType<A>>::value &&
+      absl::is_trivially_destructible<ValueType<A>>::value) {
     std::memcpy(reinterpret_cast<char*>(dst),
                 reinterpret_cast<const char*>(src), n * sizeof(ValueType<A>));
   } else {
     auto values = IteratorValueAdapter<A, ConstPointer<A>>(src);
     ConstructElements<A>(GetAllocator(), dst, values, n);
   }
+
   GetSizeAndIsAllocated() = other.GetSizeAndIsAllocated();
 }
 
@@ -921,7 +999,7 @@ auto Storage<T, N, A>::Swap(Storage* other_storage_ptr) -> void {
   if (GetIsAllocated() && other_storage_ptr->GetIsAllocated()) {
     swap(data_.allocated, other_storage_ptr->data_.allocated);
   } else if (!GetIsAllocated() && !other_storage_ptr->GetIsAllocated()) {
-    SwapInlinedElements(SwapPolicy{}, other_storage_ptr);
+    SwapInlinedElements(SwapInlinedElementsPolicy{}, other_storage_ptr);
   } else {
     Storage* allocated_ptr = this;
     Storage* inlined_ptr = other_storage_ptr;