`absl::InlinedVector::swap` supports non-assignable types.

PiperOrigin-RevId: 483752526
Change-Id: Ie6b63a4a3cc7593e5b8bf255ba571a77d609ce04

3 files changed, 254 insertions, 104 deletions

diff --git a/absl/container/inlined_vector.h b/absl/container/inlined_vector.h
index 10b1896b..15616001 100644
--- a/absl/container/inlined_vector.h
+++ b/absl/container/inlined_vector.h
@@ -97,14 +97,11 @@ class InlinedVector {
   using DisableIfAtLeastForwardIterator = absl::enable_if_t<
       !inlined_vector_internal::IsAtLeastForwardIterator<Iterator>::value, int>;
 
-  struct MemcpyPolicy {};
-  struct ElementwiseAssignPolicy {};
-  struct ElementwiseConstructPolicy {};
-
-  using MoveAssignmentPolicy = absl::conditional_t<
-      IsMemcpyOk<A>::value, MemcpyPolicy,
-      absl::conditional_t<IsMoveAssignOk<A>::value, ElementwiseAssignPolicy,
-                          ElementwiseConstructPolicy>>;
+  using MemcpyPolicy = typename Storage::MemcpyPolicy;
+  using ElementwiseAssignPolicy = typename Storage::ElementwiseAssignPolicy;
+  using ElementwiseConstructPolicy =
+      typename Storage::ElementwiseConstructPolicy;
+  using MoveAssignmentPolicy = typename Storage::MoveAssignmentPolicy;
 
  public:
   using allocator_type = A;
diff --git a/absl/container/inlined_vector_test.cc b/absl/container/inlined_vector_test.cc
index 65ddbab6..1dc6c81b 100644
--- a/absl/container/inlined_vector_test.cc
+++ b/absl/container/inlined_vector_test.cc
@@ -1841,98 +1841,185 @@ MATCHER(HasValue, "") {
   return ::testing::get<0>(arg).value() == ::testing::get<1>(arg);
 }
 
-TEST(MoveAssignment, NonAssignable) {
+TEST(NonAssignableMoveAssignmentTest, AllocatedToInline) {
   using X = MoveConstructibleOnlyInstance;
-  {
-    InstanceTracker tracker;
-    absl::InlinedVector<X, 2> inlined;
-    inlined.emplace_back(1);
-    absl::InlinedVector<X, 2> allocated;
-    allocated.emplace_back(1);
-    allocated.emplace_back(2);
-    allocated.emplace_back(3);
-    tracker.ResetCopiesMovesSwaps();
+  InstanceTracker tracker;
+  absl::InlinedVector<X, 2> inlined;
+  inlined.emplace_back(1);
+  absl::InlinedVector<X, 2> allocated;
+  allocated.emplace_back(1);
+  allocated.emplace_back(2);
+  allocated.emplace_back(3);
+  tracker.ResetCopiesMovesSwaps();
 
-    inlined = std::move(allocated);
-    // passed ownership of the allocated storage
-    EXPECT_EQ(tracker.moves(), 0);
-    EXPECT_EQ(tracker.live_instances(), 3);
+  inlined = std::move(allocated);
+  // passed ownership of the allocated storage
+  EXPECT_EQ(tracker.moves(), 0);
+  EXPECT_EQ(tracker.live_instances(), 3);
 
-    EXPECT_THAT(inlined, Pointwise(HasValue(), {1, 2, 3}));
-  }
+  EXPECT_THAT(inlined, Pointwise(HasValue(), {1, 2, 3}));
+}
 
-  {
-    InstanceTracker tracker;
-    absl::InlinedVector<X, 2> inlined;
-    inlined.emplace_back(1);
-    absl::InlinedVector<X, 2> allocated;
-    allocated.emplace_back(1);
-    allocated.emplace_back(2);
-    allocated.emplace_back(3);
-    tracker.ResetCopiesMovesSwaps();
+TEST(NonAssignableMoveAssignmentTest, InlineToAllocated) {
+  using X = MoveConstructibleOnlyInstance;
+  InstanceTracker tracker;
+  absl::InlinedVector<X, 2> inlined;
+  inlined.emplace_back(1);
+  absl::InlinedVector<X, 2> allocated;
+  allocated.emplace_back(1);
+  allocated.emplace_back(2);
+  allocated.emplace_back(3);
+  tracker.ResetCopiesMovesSwaps();
 
-    allocated = std::move(inlined);
-    // Moved elements
-    EXPECT_EQ(tracker.moves(), 1);
-    EXPECT_EQ(tracker.live_instances(), 1);
+  allocated = std::move(inlined);
+  // Moved elements
+  EXPECT_EQ(tracker.moves(), 1);
+  EXPECT_EQ(tracker.live_instances(), 1);
 
-    EXPECT_THAT(allocated, Pointwise(HasValue(), {1}));
-  }
+  EXPECT_THAT(allocated, Pointwise(HasValue(), {1}));
+}
 
-  {
-    InstanceTracker tracker;
-    absl::InlinedVector<X, 2> inlined_a;
-    inlined_a.emplace_back(1);
-    absl::InlinedVector<X, 2> inlined_b;
-    inlined_b.emplace_back(1);
-    tracker.ResetCopiesMovesSwaps();
+TEST(NonAssignableMoveAssignmentTest, InlineToInline) {
+  using X = MoveConstructibleOnlyInstance;
+  InstanceTracker tracker;
+  absl::InlinedVector<X, 2> inlined_a;
+  inlined_a.emplace_back(1);
+  absl::InlinedVector<X, 2> inlined_b;
+  inlined_b.emplace_back(1);
+  tracker.ResetCopiesMovesSwaps();
 
-    inlined_a = std::move(inlined_b);
-    // Moved elements
-    EXPECT_EQ(tracker.moves(), 1);
-    EXPECT_EQ(tracker.live_instances(), 1);
+  inlined_a = std::move(inlined_b);
+  // Moved elements
+  EXPECT_EQ(tracker.moves(), 1);
+  EXPECT_EQ(tracker.live_instances(), 1);
 
-    EXPECT_THAT(inlined_a, Pointwise(HasValue(), {1}));
-  }
+  EXPECT_THAT(inlined_a, Pointwise(HasValue(), {1}));
+}
 
-  {
-    InstanceTracker tracker;
-    absl::InlinedVector<X, 2> allocated_a;
-    allocated_a.emplace_back(1);
-    allocated_a.emplace_back(2);
-    allocated_a.emplace_back(3);
-    absl::InlinedVector<X, 2> allocated_b;
-    allocated_b.emplace_back(4);
-    allocated_b.emplace_back(5);
-    allocated_b.emplace_back(6);
-    allocated_b.emplace_back(7);
-    tracker.ResetCopiesMovesSwaps();
+TEST(NonAssignableMoveAssignmentTest, AllocatedToAllocated) {
+  using X = MoveConstructibleOnlyInstance;
+  InstanceTracker tracker;
+  absl::InlinedVector<X, 2> allocated_a;
+  allocated_a.emplace_back(1);
+  allocated_a.emplace_back(2);
+  allocated_a.emplace_back(3);
+  absl::InlinedVector<X, 2> allocated_b;
+  allocated_b.emplace_back(4);
+  allocated_b.emplace_back(5);
+  allocated_b.emplace_back(6);
+  allocated_b.emplace_back(7);
+  tracker.ResetCopiesMovesSwaps();
 
-    allocated_a = std::move(allocated_b);
-    // passed ownership of the allocated storage
-    EXPECT_EQ(tracker.moves(), 0);
-    EXPECT_EQ(tracker.live_instances(), 4);
+  allocated_a = std::move(allocated_b);
+  // passed ownership of the allocated storage
+  EXPECT_EQ(tracker.moves(), 0);
+  EXPECT_EQ(tracker.live_instances(), 4);
 
-    EXPECT_THAT(allocated_a, Pointwise(HasValue(), {4, 5, 6, 7}));
-  }
+  EXPECT_THAT(allocated_a, Pointwise(HasValue(), {4, 5, 6, 7}));
+}
 
-  {
-    InstanceTracker tracker;
-    absl::InlinedVector<X, 2> v;
-    v.emplace_back(1);
-    v.emplace_back(2);
-    v.emplace_back(3);
+TEST(NonAssignableMoveAssignmentTest, AssignThis) {
+  using X = MoveConstructibleOnlyInstance;
+  InstanceTracker tracker;
+  absl::InlinedVector<X, 2> v;
+  v.emplace_back(1);
+  v.emplace_back(2);
+  v.emplace_back(3);
 
-    tracker.ResetCopiesMovesSwaps();
+  tracker.ResetCopiesMovesSwaps();
 
-    // Obfuscated in order to pass -Wself-move.
-    v = std::move(*std::addressof(v));
-    // nothing happens
-    EXPECT_EQ(tracker.moves(), 0);
-    EXPECT_EQ(tracker.live_instances(), 3);
+  // Obfuscated in order to pass -Wself-move.
+  v = std::move(*std::addressof(v));
+  // nothing happens
+  EXPECT_EQ(tracker.moves(), 0);
+  EXPECT_EQ(tracker.live_instances(), 3);
 
-    EXPECT_THAT(v, Pointwise(HasValue(), {1, 2, 3}));
-  }
+  EXPECT_THAT(v, Pointwise(HasValue(), {1, 2, 3}));
+}
+
+class NonSwappableInstance : public absl::test_internal::BaseCountedInstance {
+ public:
+  explicit NonSwappableInstance(int x) : BaseCountedInstance(x) {}
+  NonSwappableInstance(const NonSwappableInstance& other) = default;
+  NonSwappableInstance& operator=(const NonSwappableInstance& other) = default;
+  NonSwappableInstance(NonSwappableInstance&& other) = default;
+  NonSwappableInstance& operator=(NonSwappableInstance&& other) = default;
+};
+
+void swap(NonSwappableInstance&, NonSwappableInstance&) = delete;
+
+TEST(NonSwappableSwapTest, InlineAndAllocatedTransferStorageAndMove) {
+  using X = NonSwappableInstance;
+  InstanceTracker tracker;
+  absl::InlinedVector<X, 2> inlined;
+  inlined.emplace_back(1);
+  absl::InlinedVector<X, 2> allocated;
+  allocated.emplace_back(1);
+  allocated.emplace_back(2);
+  allocated.emplace_back(3);
+  tracker.ResetCopiesMovesSwaps();
+
+  inlined.swap(allocated);
+  EXPECT_EQ(tracker.moves(), 1);
+  EXPECT_EQ(tracker.live_instances(), 4);
+
+  EXPECT_THAT(inlined, Pointwise(HasValue(), {1, 2, 3}));
+}
+
+TEST(NonSwappableSwapTest, InlineAndInlineMoveIndividualElements) {
+  using X = NonSwappableInstance;
+  InstanceTracker tracker;
+  absl::InlinedVector<X, 2> inlined_a;
+  inlined_a.emplace_back(1);
+  absl::InlinedVector<X, 2> inlined_b;
+  inlined_b.emplace_back(2);
+  tracker.ResetCopiesMovesSwaps();
+
+  inlined_a.swap(inlined_b);
+  EXPECT_EQ(tracker.moves(), 3);
+  EXPECT_EQ(tracker.live_instances(), 2);
+
+  EXPECT_THAT(inlined_a, Pointwise(HasValue(), {2}));
+  EXPECT_THAT(inlined_b, Pointwise(HasValue(), {1}));
+}
+
+TEST(NonSwappableSwapTest, AllocatedAndAllocatedOnlyTransferStorage) {
+  using X = NonSwappableInstance;
+  InstanceTracker tracker;
+  absl::InlinedVector<X, 2> allocated_a;
+  allocated_a.emplace_back(1);
+  allocated_a.emplace_back(2);
+  allocated_a.emplace_back(3);
+  absl::InlinedVector<X, 2> allocated_b;
+  allocated_b.emplace_back(4);
+  allocated_b.emplace_back(5);
+  allocated_b.emplace_back(6);
+  allocated_b.emplace_back(7);
+  tracker.ResetCopiesMovesSwaps();
+
+  allocated_a.swap(allocated_b);
+  EXPECT_EQ(tracker.moves(), 0);
+  EXPECT_EQ(tracker.live_instances(), 7);
+
+  EXPECT_THAT(allocated_a, Pointwise(HasValue(), {4, 5, 6, 7}));
+  EXPECT_THAT(allocated_b, Pointwise(HasValue(), {1, 2, 3}));
+}
+
+TEST(NonSwappableSwapTest, SwapThis) {
+  using X = NonSwappableInstance;
+  InstanceTracker tracker;
+  absl::InlinedVector<X, 2> v;
+  v.emplace_back(1);
+  v.emplace_back(2);
+  v.emplace_back(3);
+
+  tracker.ResetCopiesMovesSwaps();
+
+  v.swap(v);
+  EXPECT_EQ(tracker.moves(), 0);
+  EXPECT_EQ(tracker.live_instances(), 3);
+
+  EXPECT_THAT(v, Pointwise(HasValue(), {1, 2, 3}));
 }
 
 }  // anonymous namespace
diff --git a/absl/container/internal/inlined_vector.h b/absl/container/internal/inlined_vector.h
index f623494c..e2dd843f 100644
--- a/absl/container/internal/inlined_vector.h
+++ b/absl/container/internal/inlined_vector.h
@@ -85,6 +85,8 @@ using IsMemcpyOk =
 
 template <typename A>
 using IsMoveAssignOk = std::is_move_assignable<ValueType<A>>;
+template <typename A>
+using IsSwapOk = absl::type_traits_internal::IsSwappable<ValueType<A>>;
 
 template <typename T>
 struct TypeIdentity {
@@ -300,6 +302,20 @@ class ConstructionTransaction {
 template <typename T, size_t N, typename A>
 class Storage {
  public:
+  struct MemcpyPolicy {};
+  struct ElementwiseAssignPolicy {};
+  struct ElementwiseSwapPolicy {};
+  struct ElementwiseConstructPolicy {};
+
+  using MoveAssignmentPolicy = absl::conditional_t<
+      IsMemcpyOk<A>::value, MemcpyPolicy,
+      absl::conditional_t<IsMoveAssignOk<A>::value, ElementwiseAssignPolicy,
+                          ElementwiseConstructPolicy>>;
+  using SwapPolicy = absl::conditional_t<
+      IsMemcpyOk<A>::value, MemcpyPolicy,
+      absl::conditional_t<IsSwapOk<A>::value, ElementwiseSwapPolicy,
+                          ElementwiseConstructPolicy>>;
+
   static SizeType<A> NextCapacity(SizeType<A> current_capacity) {
     return current_capacity * 2;
   }
@@ -476,6 +492,13 @@ class Storage {
     Inlined inlined;
   };
 
+  void SwapN(ElementwiseSwapPolicy, Storage* other, SizeType<A> n);
+  void SwapN(ElementwiseConstructPolicy, Storage* other, SizeType<A> n);
+
+  void SwapInlinedElements(MemcpyPolicy, Storage* other);
+  template <typename NotMemcpyPolicy>
+  void SwapInlinedElements(NotMemcpyPolicy, Storage* other);
+
   template <typename... Args>
   ABSL_ATTRIBUTE_NOINLINE Reference<A> EmplaceBackSlow(Args&&... args);
 
@@ -889,26 +912,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()) {
-    Storage* small_ptr = this;
-    Storage* large_ptr = other_storage_ptr;
-    if (small_ptr->GetSize() > large_ptr->GetSize()) swap(small_ptr, large_ptr);
-
-    for (SizeType<A> i = 0; i < small_ptr->GetSize(); ++i) {
-      swap(small_ptr->GetInlinedData()[i], large_ptr->GetInlinedData()[i]);
-    }
-
-    IteratorValueAdapter<A, MoveIterator<A>> move_values(
-        MoveIterator<A>(large_ptr->GetInlinedData() + small_ptr->GetSize()));
-
-    ConstructElements<A>(large_ptr->GetAllocator(),
-                         small_ptr->GetInlinedData() + small_ptr->GetSize(),
-                         move_values,
-                         large_ptr->GetSize() - small_ptr->GetSize());
-
-    DestroyAdapter<A>::DestroyElements(
-        large_ptr->GetAllocator(),
-        large_ptr->GetInlinedData() + small_ptr->GetSize(),
-        large_ptr->GetSize() - small_ptr->GetSize());
+    SwapInlinedElements(SwapPolicy{}, other_storage_ptr);
   } else {
     Storage* allocated_ptr = this;
     Storage* inlined_ptr = other_storage_ptr;
@@ -944,6 +948,68 @@ auto Storage<T, N, A>::Swap(Storage* other_storage_ptr) -> void {
   swap(GetAllocator(), other_storage_ptr->GetAllocator());
 }
 
+template <typename T, size_t N, typename A>
+void Storage<T, N, A>::SwapN(ElementwiseSwapPolicy, Storage* other,
+                             SizeType<A> n) {
+  std::swap_ranges(GetInlinedData(), GetInlinedData() + n,
+                   other->GetInlinedData());
+}
+
+template <typename T, size_t N, typename A>
+void Storage<T, N, A>::SwapN(ElementwiseConstructPolicy, Storage* other,
+                             SizeType<A> n) {
+  Pointer<A> a = GetInlinedData();
+  Pointer<A> b = other->GetInlinedData();
+  // see note on allocators in `SwapInlinedElements`.
+  A& allocator_a = GetAllocator();
+  A& allocator_b = other->GetAllocator();
+  for (SizeType<A> i = 0; i < n; ++i, ++a, ++b) {
+    ValueType<A> tmp(std::move(*a));
+
+    AllocatorTraits<A>::destroy(allocator_a, a);
+    AllocatorTraits<A>::construct(allocator_b, a, std::move(*b));
+
+    AllocatorTraits<A>::destroy(allocator_b, b);
+    AllocatorTraits<A>::construct(allocator_a, b, std::move(tmp));
+  }
+}
+
+template <typename T, size_t N, typename A>
+void Storage<T, N, A>::SwapInlinedElements(MemcpyPolicy, Storage* other) {
+  Data tmp = data_;
+  data_ = other->data_;
+  other->data_ = tmp;
+}
+
+template <typename T, size_t N, typename A>
+template <typename NotMemcpyPolicy>
+void Storage<T, N, A>::SwapInlinedElements(NotMemcpyPolicy policy,
+                                           Storage* other) {
+  // Note: `destroy` needs to use pre-swap allocator while `construct` -
+  // post-swap allocator. Allocators will be swaped later on outside of
+  // `SwapInlinedElements`.
+  Storage* small_ptr = this;
+  Storage* large_ptr = other;
+  if (small_ptr->GetSize() > large_ptr->GetSize()) {
+    std::swap(small_ptr, large_ptr);
+  }
+
+  auto small_size = small_ptr->GetSize();
+  auto diff = large_ptr->GetSize() - small_size;
+  SwapN(policy, other, small_size);
+
+  IteratorValueAdapter<A, MoveIterator<A>> move_values(
+      MoveIterator<A>(large_ptr->GetInlinedData() + small_size));
+
+  ConstructElements<A>(large_ptr->GetAllocator(),
+                       small_ptr->GetInlinedData() + small_size, move_values,
+                       diff);
+
+  DestroyAdapter<A>::DestroyElements(large_ptr->GetAllocator(),
+                                     large_ptr->GetInlinedData() + small_size,
+                                     diff);
+}
+
 // End ignore "array-bounds"
 #if !defined(__clang__) && defined(__GNUC__)
 #pragma GCC diagnostic pop