From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 1888) id 90ED5386FC11; Mon, 24 May 2021 19:24:52 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 90ED5386FC11 MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Content-Type: text/plain; charset="utf-8" From: Patrick Palka To: gcc-cvs@gcc.gnu.org, libstdc++-cvs@gcc.gnu.org Subject: [gcc r12-1018] libstdc++: Fix iterator caching inside range adaptors [PR100479] X-Act-Checkin: gcc X-Git-Author: Patrick Palka X-Git-Refname: refs/heads/master X-Git-Oldrev: 6fdc59f196c3e1b4aeeb8a0407d4eb40645c5251 X-Git-Newrev: 46ed811bcb4b86a81ef3d78ea8cfffc6cd043144 Message-Id: <20210524192452.90ED5386FC11@sourceware.org> Date: Mon, 24 May 2021 19:24:52 +0000 (GMT) X-BeenThere: libstdc++-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 24 May 2021 19:24:52 -0000 https://gcc.gnu.org/g:46ed811bcb4b86a81ef3d78ea8cfffc6cd043144 commit r12-1018-g46ed811bcb4b86a81ef3d78ea8cfffc6cd043144 Author: Patrick Palka Date: Mon May 24 15:24:44 2021 -0400 libstdc++: Fix iterator caching inside range adaptors [PR100479] This fixes two issues with our iterator caching as described in detail in the PR. Since we recently added the __non_propagating_cache class template as part of r12-336 for P2328, this patch just rewrites the problematic _CachedPosition partial specialization in terms of this class template. For the offset partial specialization, it's safe to propagate the cached offset on copy/move, but we should still invalidate the cached offset in the source object on move. libstdc++-v3/ChangeLog: PR libstdc++/100479 * include/std/ranges (__detail::__non_propagating_cache): Move definition up to before that of _CachedPosition. Make base class _Optional_base protected instead of private. Add const overload for operator*. (__detail::_CachedPosition): Rewrite the partial specialization for forward ranges as a derived class of __non_propagating_cache. Remove the size constraint on the partial specialization for random access ranges. Add copy/move/copy-assignment/move-assignment members to the offset partial specialization for random access ranges that propagate the cached value but additionally invalidate it in the source object on move. * testsuite/std/ranges/adaptors/100479.cc: New test. Diff: --- libstdc++-v3/include/std/ranges | 155 ++++++++++++--------- .../testsuite/std/ranges/adaptors/100479.cc | 113 +++++++++++++++ 2 files changed, 201 insertions(+), 67 deletions(-) diff --git a/libstdc++-v3/include/std/ranges b/libstdc++-v3/include/std/ranges index 76add252ca6..e1df4240117 100644 --- a/libstdc++-v3/include/std/ranges +++ b/libstdc++-v3/include/std/ranges @@ -1043,6 +1043,67 @@ namespace views::__adaptor namespace __detail { + template + struct __non_propagating_cache + { + // When _Tp is not an object type (e.g. is a reference type), we make + // __non_propagating_cache<_Tp> empty rather than ill-formed so that + // users can easily conditionally declare data members with this type + // (such as join_view::_M_inner). + }; + + template + requires is_object_v<_Tp> + struct __non_propagating_cache<_Tp> : protected _Optional_base<_Tp> + { + __non_propagating_cache() = default; + + constexpr + __non_propagating_cache(const __non_propagating_cache&) noexcept + { } + + constexpr + __non_propagating_cache(__non_propagating_cache&& __other) noexcept + { __other._M_reset(); } + + constexpr __non_propagating_cache& + operator=(const __non_propagating_cache& __other) noexcept + { + if (std::__addressof(__other) != this) + this->_M_reset(); + return *this; + } + + constexpr __non_propagating_cache& + operator=(__non_propagating_cache&& __other) noexcept + { + this->_M_reset(); + __other._M_reset(); + return *this; + } + + constexpr _Tp& + operator*() noexcept + { return this->_M_get(); } + + constexpr const _Tp& + operator*() const noexcept + { return this->_M_get(); } + + template + _Tp& + _M_emplace_deref(const _Iter& __i) + { + this->_M_reset(); + // Using _Optional_base::_M_construct to initialize from '*__i' + // would incur an extra move due to the indirection, so we instead + // use placement new directly. + ::new ((void *) std::__addressof(this->_M_payload._M_payload)) _Tp(*__i); + this->_M_payload._M_engaged = true; + return this->_M_get(); + } + }; + template struct _CachedPosition { @@ -1064,27 +1125,26 @@ namespace views::__adaptor template struct _CachedPosition<_Range> + : protected __non_propagating_cache> { - private: - iterator_t<_Range> _M_iter{}; - - public: constexpr bool _M_has_value() const - { return _M_iter != iterator_t<_Range>{}; } + { return this->_M_is_engaged(); } constexpr iterator_t<_Range> _M_get(const _Range&) const { __glibcxx_assert(_M_has_value()); - return _M_iter; + return **this; } constexpr void _M_set(const _Range&, const iterator_t<_Range>& __it) { __glibcxx_assert(!_M_has_value()); - _M_iter = __it; + std::construct_at(std::__addressof(this->_M_payload._M_payload), + in_place, __it); + this->_M_payload._M_engaged = true; } }; @@ -1097,6 +1157,27 @@ namespace views::__adaptor range_difference_t<_Range> _M_offset = -1; public: + _CachedPosition() = default; + + constexpr + _CachedPosition(const _CachedPosition&) = default; + + constexpr + _CachedPosition(_CachedPosition&& __other) noexcept + { *this = std::move(__other); } + + constexpr _CachedPosition& + operator=(const _CachedPosition&) = default; + + constexpr _CachedPosition& + operator=(_CachedPosition&& __other) noexcept + { + // Propagate the cached offset, but invalidate the source. + _M_offset = __other._M_offset; + __other._M_offset = -1; + return *this; + } + constexpr bool _M_has_value() const { return _M_offset >= 0; } @@ -2238,66 +2319,6 @@ namespace views::__adaptor inline constexpr _DropWhile drop_while; } // namespace views - namespace __detail - { - template - struct __non_propagating_cache - { - // When _Tp is not an object type (e.g. is a reference type), we make - // __non_propagating_cache<_Tp> empty rather than ill-formed so that - // users can easily conditionally declare data members with this type - // (such as join_view::_M_inner). - }; - - template - requires is_object_v<_Tp> - struct __non_propagating_cache<_Tp> : private _Optional_base<_Tp> - { - __non_propagating_cache() = default; - - constexpr - __non_propagating_cache(const __non_propagating_cache&) noexcept - { } - - constexpr - __non_propagating_cache(__non_propagating_cache&& __other) noexcept - { __other._M_reset(); } - - constexpr __non_propagating_cache& - operator=(const __non_propagating_cache& __other) noexcept - { - if (std::__addressof(__other) != this) - this->_M_reset(); - return *this; - } - - constexpr __non_propagating_cache& - operator=(__non_propagating_cache&& __other) noexcept - { - this->_M_reset(); - __other._M_reset(); - return *this; - } - - constexpr _Tp& - operator*() noexcept - { return this->_M_get(); } - - template - _Tp& - _M_emplace_deref(const _Iter& __i) - { - this->_M_reset(); - // Using _Optional_base::_M_construct to initialize from '*__i' - // would incur an extra move due to the indirection, so we instead - // use placement new directly. - ::new ((void *) std::__addressof(this->_M_payload._M_payload)) _Tp(*__i); - this->_M_payload._M_engaged = true; - return this->_M_get(); - } - }; - } - template requires view<_Vp> && input_range> class join_view : public view_interface> diff --git a/libstdc++-v3/testsuite/std/ranges/adaptors/100479.cc b/libstdc++-v3/testsuite/std/ranges/adaptors/100479.cc new file mode 100644 index 00000000000..ba10b7baf3f --- /dev/null +++ b/libstdc++-v3/testsuite/std/ranges/adaptors/100479.cc @@ -0,0 +1,113 @@ +// Copyright (C) 2021 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 3, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING3. If not see +// . + +// { dg-options "-std=gnu++2a" } +// { dg-do run { target c++2a } } + +// PR libstdc++/100479 + +#include +#include +#include + +using __gnu_test::test_forward_range; +using __gnu_test::test_random_access_range; + +namespace ranges = std::ranges; +namespace views = std::views; + +void +test01() +{ + // Verify we don't propagate cached iterators when copying/moving an adapted + // forward range that memoizes its begin(). + static int pred_counter; + int x[] = {1,2,3,4,5}; + test_forward_range rx(x); + auto is_odd = [](auto n) { ++pred_counter; return n%2 != 0; }; + + auto v = rx | views::filter(is_odd); + v.begin(); v.begin(); + VERIFY( pred_counter == 1 ); // filter_view caches its begin() iterator + + auto w = v; + v.begin(); v.begin(); + VERIFY( pred_counter == 1 ); // cached iterator not invalidated on copy + w.begin(); w.begin(); + VERIFY( pred_counter == 2 ); // cached iterator not propagated on copy + + auto z = std::move(w); + w.begin(); w.begin(); + VERIFY( pred_counter == 3 ); // cached iterator invalidated on move + z.begin(); z.begin(); + VERIFY( pred_counter == 4 ); // cached iterator not propagated on move +} + +void +test02() +{ + // Verify we invalidate the cached offset when moving an adapted + // random access range that memoizes its begin(). + static int pred_counter; + int x[] = {1,2,3,4,5}; + test_random_access_range rx(x); + auto is_odd = [](auto n) { ++pred_counter; return n%2 != 0; }; + + auto v = rx | views::filter(is_odd); + v.begin(); v.begin(); + VERIFY( pred_counter == 1 ); // filter_view caches its begin() iterator + + auto w = v; + v.begin(); v.begin(); + VERIFY( pred_counter == 1 ); // cached offset not invalidated on copy + w.begin(); w.begin(); + VERIFY( pred_counter == 1 ); // cached offset propagated on copy + + auto z = std::move(w); + w.begin(); w.begin(); + VERIFY( pred_counter == 2 ); // cached offset invalidated on move + z.begin(); z.begin(); + VERIFY( pred_counter == 2 ); // cached offset propagated on move +} + +constexpr bool +test03() +{ + // Propagating cached iterators during copy/move would cause these asserts + // to fail here. + auto v = views::single(1) + | views::split(1) + | views::drop(0) + | views::drop_while([](auto) { return false; }) + | views::filter([](auto) { return true; }); + static_assert(ranges::forward_range); + VERIFY( ranges::next(v.begin()) == v.end() ); + auto w = v; + VERIFY( ranges::next(w.begin()) == w.end() ); + auto z = std::move(w); + VERIFY( ranges::next(z.begin()) == z.end() ); + return true; +} + +int +main() +{ + test01(); + test02(); + test03(); + static_assert(test03()); +}