https://gcc.gnu.org/g:d4f7d18b3ed83a8265be913bb230f6efa395e527
commit r15-8902-gd4f7d18b3ed83a8265be913bb230f6efa395e527
Author: Jonathan Wakely <jwak...@redhat.com>
Date: Fri Mar 21 23:21:42 2025 +0000
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 <tkami...@redhat.com>
Diff:
---
libstdc++-v3/include/bits/stl_bvector.h | 77 ++++++++--
libstdc++-v3/include/bits/stl_vector.h | 110 +++++++++++++-
libstdc++-v3/include/bits/vector.tcc | 2 +-
.../vector/bool/modifiers/insert/append_range.cc | 51 +++++++
.../23_containers/vector/modifiers/append_range.cc | 165 +++++++++++++++++++++
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 3ee15eaa938c..03f6434604c3 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 09fd53696d1d..21f6cd04f490 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 acb2f5fca1e7..f197278d52e0 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 a35ed0f20266..43a698f65c41 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 5725cd2ad483..be097e2b1310 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() );
}
