On Mon, 24 Mar 2025 at 14:18, Patrick Palka <ppa...@redhat.com> wrote:
>
> On Mon, 24 Mar 2025, Jonathan Wakely wrote:
>
> > 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)
> > (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.
> > ---
> >
> > Changed vector<bool, A>::assign_range to just use a loop for the
> > non-sized input range case, instead of calling append_range.
> >
> > Changed private copy ctor to deleted move ctor in RAII type.
> >
> > Testing x86_64-linux now.
> >
> > libstdc++-v3/include/bits/stl_bvector.h | 69 ++++++--
> > libstdc++-v3/include/bits/stl_vector.h | 101 ++++++++++-
> > libstdc++-v3/include/bits/vector.tcc | 2 +-
> > .../bool/modifiers/insert/append_range.cc | 50 ++++++
> > .../vector/modifiers/append_range.cc | 164 ++++++++++++++++++
> > 5 files changed, 366 insertions(+), 20 deletions(-)
> >
> > diff --git a/libstdc++-v3/include/bits/stl_bvector.h
> > b/libstdc++-v3/include/bits/stl_bvector.h
> > index 3ee15eaa938..5addab048c9 100644
> > --- a/libstdc++-v3/include/bits/stl_bvector.h
> > +++ b/libstdc++-v3/include/bits/stl_bvector.h
> > @@ -1035,8 +1035,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
> >
> > @@ -1385,24 +1402,52 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> > constexpr void
> > append_range(_Rg&& __rg)
> > {
> > + // N.B. append_range(r) allows r to overlap with *this,
> > + // e.g. it could be *this | views::filter(pred) | views::to_input
> > + // and so we must not invalidate existing elements too soon.
> > 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));
> > + const auto __sz = size();
> > +
> > + // If there are no existing elements it's safe to allocate now.
> > + if (__sz == 0)
> > + reserve(__n);
> > +
> > + 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 09fd53696d1..7f0b62e9b93 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
> > @@ -771,7 +771,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
> >
> > @@ -1648,20 +1653,102 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
> > constexpr void
> > append_range(_Rg&& __rg)
> > {
> > + // N.B. append_range(r) allows r to overlap with *this,
> > + // e.g. it could be *this | views::filter(pred) | views::to_input
> > + // and so we must not invalidate existing elements too soon.
> > 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);
> > + const auto __sz = size();
> > +
> > + // If there are no existing elements it's safe to allocate now.
> > + if (__sz == 0)
> > + reserve(__n);
> > +
> > + 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 acb2f5fca1e..f197278d52e 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 a35ed0f2026..bb103a47202 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,56 @@ test_constexpr()
> > {
> > // XXX: this doesn't test the non-forward_range code paths are constexpr.
>
> I think we could remove this comment now?
The do_test call immediately below the comment still doesn't test the
non-forward paths.
The new additions do test it, although not as thoroughly as do_test
does. The new additions only check that the calls to append_range with
overlapping ranges don't hit UB (and specifically, UB that G++
actually diagnoses), they don't check the values in the resulting
range are correct. I could make the comments more clear, or add
another comment below saying that the rest of test_constexpr only
tests a subset of the functionality.
>
> > do_test<std::span<short>, std::allocator<bool>>();
> > +
> > + using I = std::vector<bool>::iterator;
> > + std::vector<bool> vec(5);
> > +
> > + 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> );
> > +
> > + // Test 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 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 5725cd2ad48..6bfe2047d1c 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,180 @@ 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.
>
> Same
>
> > do_test<std::span<short>, std::allocator<int>>();
> > +
> > + std::vector<int> vec(5);
> > +
> > + 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> );
> > +
> > + // Test 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 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_overlapping();
> > test_ranges();
> > static_assert( test_constexpr() );
> > }
> > --
> > 2.49.0
> >
> >
>
