libstdc++: Fix std::vector::append_range for overlapping ranges

Unlike insert_range and assign_range, the append_range function does not
have a precondition that the range doesn't overlap *this. That means we
need to avoid relocating the existing elements until after copying from
the range. This means I need to revert r15-8488-g3e1d760bf49d0e which
made the from_range_t constructor use append_range, because the
constructor can avoid the additional complexity needed by append_range.
When relocating the existing elements in append_range we can use
std::__relocate_a to do it more efficiently, if that's valid.

std::vector<bool>::append_range needs similar treatment, although it's a
bit simpler as we know that the elements are trivially copyable and so
we don't need to worry about them throwing. assign_range doesn't allow
overlapping ranges, so can be rewritten to be more efficient than
calling append_range for the forward or sized range case.

libstdc++-v3/ChangeLog:

	* include/bits/stl_bvector.h (vector::assign_range): More
	efficient implementation for forward/sized ranges.
	(vector::append_range): Handle potentially overlapping range.
	* include/bits/stl_vector.h (vector(from_range_t, R&&, Alloc)):
	Do not use append_range for non-sized input range case.
	(vector::append_range): Handle potentially overlapping range.
	* include/bits/vector.tcc (vector::insert_range): Forward range
	instead of moving it.
	* testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc:
	Test overlapping ranges.
	* testsuite/23_containers/vector/modifiers/append_range.cc:
	Likewise.

Reviewed-by: Tomasz Kamiński <tkaminsk@redhat.com>

5 files changed, 385 insertions, 20 deletions

diff --git a/libstdc++-v3/include/bits/stl_bvector.h b/libstdc++-v3/include/bits/stl_bvector.h
index 3ee15ea..03f6434 100644
--- a/libstdc++-v3/include/bits/stl_bvector.h
+++ b/libstdc++-v3/include/bits/stl_bvector.h
@@ -899,6 +899,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __glibcxx_ranges_to_container // C++ >= 23
       /**
        * @brief Construct a vector from a range.
+       * @param __rg A range of values that are convertible to `value_type`.
        * @since C++23
        */
       template<__detail::__container_compatible_range<bool> _Rg>
@@ -1028,6 +1029,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __glibcxx_ranges_to_container // C++ >= 23
       /**
        * @brief Assign a range to the vector.
+       * @param __rg A range of values that are convertible to `value_type`.
+       * @pre `__rg` and `*this` do not overlap.
        * @since C++23
        */
       template<__detail::__container_compatible_range<bool> _Rg>
@@ -1035,8 +1038,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	assign_range(_Rg&& __rg)
 	{
 	  static_assert(assignable_from<bool&, ranges::range_reference_t<_Rg>>);
-	  clear();
-	  append_range(std::forward<_Rg>(__rg));
+	  if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
+	    {
+	      if (auto __n = size_type(ranges::distance(__rg)))
+		{
+		  reserve(__n);
+		  this->_M_impl._M_finish
+		      = ranges::copy(std::forward<_Rg>(__rg), begin()).out;
+		}
+	      else
+		clear();
+	    }
+	  else
+	    {
+	      clear();
+	      auto __first = ranges::begin(__rg);
+	      const auto __last = ranges::end(__rg);
+	      for (; __first != __last; ++__first)
+		emplace_back(*__first);
+	    }
 	}
 #endif
 
@@ -1330,6 +1350,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __glibcxx_ranges_to_container // C++ >= 23
       /**
        * @brief Insert a range into the vector.
+       * @param __rg A range of values that are convertible to `bool`.
+       * @return An iterator that points to the first new element inserted,
+       *         or to `__pos` if `__rg` is an empty range.
+       * @pre `__rg` and `*this` do not overlap.
        * @since C++23
        */
       template<__detail::__container_compatible_range<bool> _Rg>
@@ -1385,24 +1409,53 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	constexpr void
 	append_range(_Rg&& __rg)
 	{
+	  // N.B. __rg may overlap with *this, so we must copy from __rg before
+	  // existing elements or iterators referring to *this are invalidated.
+	  // e.g. in v.append_range(views::concat(v, foo)) rg overlaps v.
 	  if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
 	    {
-	      reserve(size() + size_type(ranges::distance(__rg)));
-	      this->_M_impl._M_finish = ranges::copy(__rg, end()).out;
+	      const auto __n = size_type(ranges::distance(__rg));
+
+	      // If there is no existing storage, there are no iterators that
+	      // can be referring to our storage, so it's safe to allocate now.
+	      if (capacity() == 0)
+		reserve(__n);
+
+	      const auto __sz = size();
+	      const auto __capacity = capacity();
+	      if ((__capacity - __sz) >= __n)
+		{
+		  this->_M_impl._M_finish
+		      = ranges::copy(std::forward<_Rg>(__rg), end()).out;
+		  return;
+		}
+
+	      vector __tmp(get_allocator());
+	      __tmp.reserve(_M_check_len(__n, "vector::append_range"));
+	      __tmp._M_impl._M_finish
+		   = _M_copy_aligned(cbegin(), cend(), __tmp.begin());
+	      __tmp._M_impl._M_finish
+		   = ranges::copy(std::forward<_Rg>(__rg), __tmp.end()).out;
+	      swap(__tmp);
 	    }
 	  else
 	    {
 	      auto __first = ranges::begin(__rg);
 	      const auto __last = ranges::end(__rg);
-	      size_type __n = size();
-	      const size_type __cap = capacity();
-	      for (; __first != __last && __n < __cap; ++__first, (void)++__n)
+
+	      // Fill up to the end of current capacity.
+	      for (auto __free = capacity() - size();
+		   __first != __last && __free > 0;
+		   ++__first, (void) --__free)
 		emplace_back(*__first);
-	      if (__first != __last)
-		{
-		  ranges::subrange __rest(std::move(__first), __last);
-		  append_range(vector(from_range, __rest, get_allocator()));
-		}
+
+	      if (__first == __last)
+		return;
+
+	      // Copy the rest of the range to a new vector.
+	      ranges::subrange __rest(std::move(__first), __last);
+	      vector __tmp(from_range, __rest, get_allocator());
+	      insert(end(), __tmp.begin(), __tmp.end());
 	    }
 	}
 #endif // ranges_to_container
diff --git a/libstdc++-v3/include/bits/stl_vector.h b/libstdc++-v3/include/bits/stl_vector.h
index 09fd536..21f6cd0 100644
--- a/libstdc++-v3/include/bits/stl_vector.h
+++ b/libstdc++-v3/include/bits/stl_vector.h
@@ -65,7 +65,7 @@
 #if __cplusplus >= 202002L
 # include <compare>
 #endif
-#if __cplusplus > 202002L
+#if __glibcxx_ranges_to_container // C++ >= 23
 # include <bits/ranges_algobase.h>      // ranges::copy
 # include <bits/ranges_util.h>          // ranges::subrange
 #endif
@@ -753,6 +753,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __glibcxx_ranges_to_container // C++ >= 23
       /**
        * @brief Construct a vector from a range.
+       * @param __rg A range of values that are convertible to `bool`.
        * @since C++23
        */
       template<__detail::__container_compatible_range<_Tp> _Rg>
@@ -771,7 +772,12 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	      _Base::_M_append_range(__rg);
 	    }
 	  else
-	    append_range(std::move(__rg));
+	    {
+	      auto __first = ranges::begin(__rg);
+	      const auto __last = ranges::end(__rg);
+	      for (; __first != __last; ++__first)
+		emplace_back(*__first);
+	    }
 	}
 #endif
 
@@ -914,6 +920,8 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __glibcxx_ranges_to_container // C++ >= 23
       /**
        * @brief Assign a range to the vector.
+       * @param __rg A range of values that are convertible to `value_type`.
+       * @pre `__rg` and `*this` do not overlap.
        * @since C++23
        */
       template<__detail::__container_compatible_range<_Tp> _Rg>
@@ -1634,6 +1642,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 #if __glibcxx_ranges_to_container // C++ >= 23
       /**
        * @brief Insert a range into the vector.
+       * @param __rg A range of values that are convertible to `value_type`.
+       * @return An iterator that points to the first new element inserted,
+       *         or to `__pos` if `__rg` is an empty range.
+       * @pre `__rg` and `*this` do not overlap.
        * @since C++23
        */
       template<__detail::__container_compatible_range<_Tp> _Rg>
@@ -1642,26 +1654,110 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       /**
        * @brief Append a range at the end of the vector.
+       * @param __rg A range of values that are convertible to `value_type`.
        * @since C++23
        */
       template<__detail::__container_compatible_range<_Tp> _Rg>
 	constexpr void
 	append_range(_Rg&& __rg)
 	{
+	  // N.B. __rg may overlap with *this, so we must copy from __rg before
+	  // existing elements or iterators referring to *this are invalidated.
+	  // e.g. in v.append_range(views::concat(v, foo)) rg overlaps v.
 	  if constexpr (ranges::forward_range<_Rg> || ranges::sized_range<_Rg>)
 	    {
 	      const auto __n = size_type(ranges::distance(__rg));
-	      reserve(size() + __n);
-	      _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
-	      _Base::_M_append_range(__rg);
-	      _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
+
+	      // If there is no existing storage, there are no iterators that
+	      // can be referring to our storage, so it's safe to allocate now.
+	      if (capacity() == 0)
+		reserve(__n);
+
+	      const auto __sz = size();
+	      const auto __capacity = capacity();
+	      if ((__capacity - __sz) >= __n)
+		{
+		  _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
+		  _Base::_M_append_range(__rg);
+		  _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
+		  return;
+		}
+
+	      const size_type __len = _M_check_len(__n, "vector::append_range");
+
+	      pointer __old_start = this->_M_impl._M_start;
+	      pointer __old_finish = this->_M_impl._M_finish;
+
+	      allocator_type& __a = _M_get_Tp_allocator();
+	      const pointer __start = this->_M_allocate(__len);
+	      const pointer __mid = __start + __sz;
+	      const pointer __back = __mid + __n;
+	      _Guard_alloc __guard(__start, __len, *this);
+	      std::__uninitialized_copy_a(ranges::begin(__rg),
+					  ranges::end(__rg),
+					  __mid, __a);
+
+	      if constexpr (_S_use_relocate())
+		_S_relocate(__old_start, __old_finish, __start, __a);
+	      else
+		{
+		  // RAII type to destroy initialized elements.
+		  struct _Guard_elts
+		  {
+		    pointer _M_first, _M_last;  // Elements to destroy
+		    _Tp_alloc_type& _M_alloc;
+
+		    constexpr
+		    _Guard_elts(pointer __f, pointer __l, _Tp_alloc_type& __a)
+		    : _M_first(__f), _M_last(__l), _M_alloc(__a)
+		    { }
+
+		    constexpr
+		    ~_Guard_elts()
+		    { std::_Destroy(_M_first, _M_last, _M_alloc); }
+
+		    _Guard_elts(_Guard_elts&&) = delete;
+		  };
+		  _Guard_elts __guard_elts{__mid, __back, __a};
+
+		  std::__uninitialized_move_a(__old_start, __old_finish,
+					      __start, __a);
+
+		  // Let old elements get destroyed by __guard_elts:
+		  __guard_elts._M_first = __old_start;
+		  __guard_elts._M_last = __old_finish;
+		}
+
+	      // Now give ownership of old storage to __guard:
+	      __guard._M_storage = __old_start;
+	      __guard._M_len = __capacity;
+	      // Finally, take ownership of new storage:
+	      this->_M_impl._M_start = __start;
+	      this->_M_impl._M_finish = __back;
+	      this->_M_impl._M_end_of_storage = __start + __len;
 	    }
 	  else
 	    {
 	      auto __first = ranges::begin(__rg);
 	      const auto __last = ranges::end(__rg);
-	      for (; __first != __last; ++__first)
+
+	      // Fill up to the end of current capacity.
+	      for (auto __free = capacity() - size();
+		   __first != __last && __free > 0;
+		   ++__first, (void) --__free)
 		emplace_back(*__first);
+
+	      if (__first == __last)
+		return;
+
+	      // Copy the rest of the range to a new vector.
+	      vector __tmp(_M_get_Tp_allocator());
+	      for (; __first != __last; ++__first)
+		__tmp.emplace_back(*__first);
+	      reserve(_M_check_len(__tmp.size(), "vector::append_range"));
+	      ranges::subrange __r(std::make_move_iterator(__tmp.begin()),
+				   std::make_move_iterator(__tmp.end()));
+	      append_range(__r); // This will take the fast path above.
 	    }
 	}
 #endif // ranges_to_container
diff --git a/libstdc++-v3/include/bits/vector.tcc b/libstdc++-v3/include/bits/vector.tcc
index acb2f5f..f197278d 100644
--- a/libstdc++-v3/include/bits/vector.tcc
+++ b/libstdc++-v3/include/bits/vector.tcc
@@ -1094,7 +1094,7 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	    return begin() + __ins_idx;
 	  }
 	else
-	  return insert_range(__pos, vector(from_range, std::move(__rg),
+	  return insert_range(__pos, vector(from_range, std::forward<_Rg>(__rg),
 					    _M_get_Tp_allocator()));
       }
 #endif // ranges_to_container
diff --git a/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc
index a35ed0f..43a698f 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/bool/modifiers/insert/append_range.cc
@@ -83,6 +83,57 @@ test_constexpr()
 {
   // XXX: this doesn't test the non-forward_range code paths are constexpr.
   do_test<std::span<short>, std::allocator<bool>>();
+
+  // Some basic tests for overlapping ranges in constant expressions.
+  using I = std::vector<bool>::iterator;
+
+  struct InputRange
+  {
+    struct Sent { I end; };
+
+    struct Iter
+    {
+      using value_type = bool;
+      using difference_type = int;
+      constexpr explicit Iter(I i) : i(i) { }
+      constexpr Iter& operator++() { ++i; return *this; }
+      constexpr Iter operator++(int) { auto i = *this; ++i; return i; }
+      constexpr int operator*() const { return *i; }
+      constexpr bool operator==(const Iter&) const = default;
+      constexpr bool operator==(const Sent& s) const { return i == s.end; }
+      I i;
+    };
+
+    Iter iter;
+    Sent sent;
+
+    constexpr InputRange(I f, I l) : iter{f}, sent{l} { }
+    constexpr Iter begin() const { return iter; }
+    constexpr Sent end() const { return sent; }
+  };
+  static_assert( std::ranges::input_range<InputRange> );
+  static_assert( ! std::ranges::forward_range<InputRange> );
+
+  std::vector<bool> vec(5);
+
+  // Test overlapping input ranges
+  vec.resize(vec.capacity());
+  vec.append_range(InputRange(vec.begin(), vec.begin() + 3)); // no capacity
+  vec.reserve(vec.capacity() + 2);
+  vec.append_range(InputRange(vec.begin(), vec.begin() + 4)); // some capacity
+  vec.reserve(vec.capacity() + 6);
+  vec.append_range(InputRange(vec.begin(), vec.begin() + 5)); // enough capacity
+
+  using R = std::ranges::subrange<I>;
+
+  // Test overlapping forward ranges
+  vec.resize(vec.capacity());
+  vec.append_range(R(vec.begin(), vec.begin() + 3)); // no capacity
+  vec.reserve(vec.size() + 2);
+  vec.append_range(R(vec.begin(), vec.begin() + 4)); // some capacity
+  vec.reserve(vec.size() + 6);
+  vec.append_range(R(vec.begin(), vec.begin() + 5)); // enough capacity
+
   return true;
 }
 
diff --git a/libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc b/libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc
index 5725cd2..be097e2 100644
--- a/libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc
+++ b/libstdc++-v3/testsuite/23_containers/vector/modifiers/append_range.cc
@@ -82,16 +82,181 @@ test_ranges()
   return true;
 }
 
+void
+test_overlapping()
+{
+  using __gnu_test::test_input_range;
+  using __gnu_test::test_forward_range;
+
+  struct X {
+    unsigned* p;
+    constexpr X(int i = 0) : p(new unsigned(i)) { }
+    constexpr X(const X& m) : p(new unsigned(*m.p)) { }
+    constexpr X(X&& m) noexcept : p(m.p) { m.p = nullptr; }
+    constexpr ~X() { delete p; }
+  };
+
+  std::vector<X> vec;
+  unsigned size = 5;
+  vec.reserve(size);
+  for (unsigned i = 0; i < size; ++i)
+    vec.emplace_back(i);
+
+  // Append an input range that overlaps with vec.
+  {
+    __gnu_test::test_input_range<X> r(vec.data(), vec.data() + size);
+    vec.append_range(r);
+    VERIFY( vec.size() == 2 * size );
+    for (unsigned i = 0; i < size; ++i)
+    {
+      VERIFY( *vec[i].p == i );
+      VERIFY( *vec[i+size].p == i );
+    }
+  }
+
+  size = vec.size() - 2;
+  vec.resize(size);
+  for (unsigned i = 0; i < size; ++i)
+    *vec[i].p = i;
+
+  // Repeat with unused capacity in the vector.
+  {
+    __gnu_test::test_input_range<X> r(vec.data(), vec.data() + size);
+    vec.append_range(r);
+    VERIFY( vec.size() == 2 * size );
+    for (unsigned i = 0; i < size; ++i)
+    {
+      VERIFY( *vec[i].p == i );
+      VERIFY( *vec[i+size].p == i );
+    }
+  }
+
+  size = vec.size() - 2;
+  vec.resize(size);
+  for (unsigned i = 0; i < size; ++i)
+    *vec[i].p = i;
+
+  // Repeat with input range that doesn't overlap full vector.
+  {
+    __gnu_test::test_input_range<X> r(vec.data() + 1, vec.data() + 4);
+    vec.append_range(r);
+    VERIFY( vec.size() == size + 3 );
+    for (unsigned i = 0; i < size; ++i)
+    {
+      VERIFY( *vec[i].p == i );
+      if (i < 3)
+	VERIFY( *vec[i+size].p == i+1 );
+    }
+  }
+
+  size = 5;
+  vec.resize(size);
+  for (unsigned i = 0; i < size; ++i)
+    *vec[i].p = i;
+
+  // Append a forward range that overlaps with vec.
+  {
+    __gnu_test::test_forward_range<X> r(vec.data(), vec.data() + size);
+    vec.append_range(r);
+    VERIFY( vec.size() == 2 * size );
+    for (unsigned i = 0; i < size; ++i)
+    {
+      VERIFY( *vec[i].p == i );
+      VERIFY( *vec[i+size].p == i );
+    }
+  }
+
+  size = vec.size() - 2;
+  vec.resize(size);
+  for (unsigned i = 0; i < size; ++i)
+    *vec[i].p = i;
+
+  // Repeat with insufficient unused capacity in the vector.
+  {
+    __gnu_test::test_forward_range<X> r(vec.data(), vec.data() + size);
+    vec.append_range(r);
+    VERIFY( vec.size() == 2 * size );
+    for (unsigned i = 0; i < size; ++i)
+    {
+      VERIFY( *vec[i].p == i );
+      VERIFY( *vec[i+size].p == i );
+    }
+  }
+
+  size = vec.size() / 2;
+  vec.resize(size);
+
+  // Repeat with sufficient unused capacity in the vector.
+  {
+    __gnu_test::test_forward_range<X> r(vec.data(), vec.data() + size);
+    vec.append_range(r);
+    VERIFY( vec.size() == 2 * size );
+    for (unsigned i = 0; i < size; ++i)
+    {
+      VERIFY( *vec[i].p == i );
+      VERIFY( *vec[i+size].p == i );
+    }
+  }
+}
+
 constexpr bool
 test_constexpr()
 {
   // XXX: this doesn't test the non-forward_range code paths are constexpr.
   do_test<std::span<short>, std::allocator<int>>();
+
+  // Some basic tests for overlapping ranges in constant expressions.
+  struct InputRange
+  {
+    struct Sent { const void* end; };
+
+    struct Iter
+    {
+      using value_type = int;
+      using difference_type = int;
+      constexpr explicit Iter(int* p) : ptr(p) { }
+      constexpr Iter& operator++() { ++ptr; return *this; }
+      constexpr Iter operator++(int) { auto i = *this; ++ptr; return i; }
+      constexpr int operator*() const { return *ptr; }
+      constexpr bool operator==(const Iter&) const = default;
+      constexpr bool operator==(const Sent& s) const { return ptr == s.end; }
+      int* ptr;
+    };
+
+    Iter iter;
+    Sent sent;
+
+    constexpr InputRange(int* f, int* l) : iter{f}, sent{l} { }
+    constexpr Iter begin() const { return iter; }
+    constexpr Sent end() const { return sent; }
+  };
+  static_assert( std::ranges::input_range<InputRange> );
+  static_assert( ! std::ranges::forward_range<InputRange> );
+
+  std::vector<int> vec(5);
+
+  // Test overlapping input ranges
+  vec.resize(vec.capacity());
+  vec.append_range(InputRange(vec.data(), vec.data() + 3)); // no capacity
+  vec.reserve(vec.capacity() + 2);
+  vec.append_range(InputRange(vec.data(), vec.data() + 4)); // some capacity
+  vec.reserve(vec.capacity() + 6);
+  vec.append_range(InputRange(vec.data(), vec.data() + 5)); // enough capacity
+
+  // Test overlapping forward ranges
+  vec.resize(vec.capacity());
+  vec.append_range(std::span<int>(vec));               // no capacity
+  vec.reserve(vec.size() + 2);
+  vec.append_range(std::span<int>(vec).subspan(1, 4)); // some capacity
+  vec.reserve(vec.size() + 6);
+  vec.append_range(std::span<int>(vec).subspan(1, 5)); // enough capacity
+
   return true;
 }
 
 int main()
 {
   test_ranges();
+  test_overlapping();
   static_assert( test_constexpr() );
 }