diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -191,6 +191,7 @@ __ranges/empty.h __ranges/enable_borrowed_range.h __ranges/enable_view.h + __ranges/non_propagating_cache.h __ranges/ref_view.h __ranges/size.h __ranges/subrange.h diff --git a/libcxx/include/__ranges/drop_view.h b/libcxx/include/__ranges/drop_view.h --- a/libcxx/include/__ranges/drop_view.h +++ b/libcxx/include/__ranges/drop_view.h @@ -17,9 +17,9 @@ #include <__ranges/all.h> #include <__ranges/concepts.h> #include <__ranges/enable_borrowed_range.h> +#include <__ranges/non_propagating_cache.h> #include <__ranges/size.h> #include <__ranges/view_interface.h> -#include #include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -36,21 +36,16 @@ namespace ranges { template class drop_view - : public view_interface> { - + : public view_interface> + { // We cache begin() whenever ranges::next is not guaranteed O(1) to provide an // amortized O(1) begin() method. If this is an input_range, then we cannot cache // begin because begin is not equality preserving. // Note: drop_view::begin() is still trivially amortized O(1) because // one can't call begin() on it more than once. static constexpr bool _UseCache = forward_range<_View> && !(random_access_range<_View> && sized_range<_View>); - using _Cache = optional>; - struct _Empty { }; - - // For forward ranges use std::optional to cache the begin iterator. - // No unique address + _Empty means we don't use any extra space when this - // is not a forward iterator. - [[no_unique_address]] conditional_t<_UseCache, _Cache, _Empty> __cached_begin_; + using _Cache = _If<_UseCache, __non_propagating_cache>, __empty_cache>; + [[no_unique_address]] _Cache __cached_begin_ = _Cache(); range_difference_t<_View> __count_ = 0; _View __base_ = _View(); @@ -59,48 +54,12 @@ _LIBCPP_HIDE_FROM_ABI constexpr drop_view(_View __base, range_difference_t<_View> __count) - : __cached_begin_() - , __count_(__count) + : __count_(__count) , __base_(_VSTD::move(__base)) { _LIBCPP_ASSERT(__count_ >= 0, "count must be greater than or equal to zero."); } - _LIBCPP_HIDE_FROM_ABI - constexpr drop_view(drop_view const& __other) - : __cached_begin_() // Intentionally not propagating the cached begin iterator. - , __count_(__other.__count_) - , __base_(__other.__base_) - { } - - _LIBCPP_HIDE_FROM_ABI - constexpr drop_view(drop_view&& __other) - : __cached_begin_() // Intentionally not propagating the cached begin iterator. - , __count_(_VSTD::move(__other.__count_)) - , __base_(_VSTD::move(__other.__base_)) - { } - - _LIBCPP_HIDE_FROM_ABI - constexpr drop_view& operator=(drop_view const& __other) { - if constexpr (_UseCache) { - __cached_begin_.reset(); - } - __base_ = __other.__base_; - __count_ = __other.__count_; - return *this; - } - - _LIBCPP_HIDE_FROM_ABI - constexpr drop_view& operator=(drop_view&& __other) { - if constexpr (_UseCache) { - __cached_begin_.reset(); - __other.__cached_begin_.reset(); - } - __base_ = _VSTD::move(__other.__base_); - __count_ = _VSTD::move(__other.__count_); - return *this; - } - _LIBCPP_HIDE_FROM_ABI constexpr _View base() const& requires copy_constructible<_View> { return __base_; } _LIBCPP_HIDE_FROM_ABI constexpr _View base() && { return _VSTD::move(__base_); } @@ -110,12 +69,12 @@ random_access_range && sized_range)) { if constexpr (_UseCache) - if (__cached_begin_) + if (__cached_begin_.__has_value()) return *__cached_begin_; auto __tmp = ranges::next(ranges::begin(__base_), __count_, ranges::end(__base_)); if constexpr (_UseCache) - __cached_begin_ = __tmp; + __cached_begin_.__set(__tmp); return __tmp; } diff --git a/libcxx/include/__ranges/non_propagating_cache.h b/libcxx/include/__ranges/non_propagating_cache.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__ranges/non_propagating_cache.h @@ -0,0 +1,98 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +#ifndef _LIBCPP___RANGES_NON_PROPAGATING_CACHE_H +#define _LIBCPP___RANGES_NON_PROPAGATING_CACHE_H + +#include <__config> +#include <__iterator/concepts.h> // indirectly_readable +#include <__iterator/iterator_traits.h> // iter_reference_t +#include <__memory/addressof.h> +#include // constructible_from +#include +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +// clang-format off + +#if !defined(_LIBCPP_HAS_NO_RANGES) + +namespace ranges { + // __non_propagating_cache is a helper type that allows storing an optional value in it, + // but which does not copy the source's value when it is copy constructed/assigned to, + // and which resets the source's value when it is moved-from. + // + // This type is used as an implementation detail of some views that need to cache the + // result of `begin()` in order to provide an amortized O(1) begin() method. Typically, + // we don't want to propagate the value of the cache upon copy because the cached iterator + // may refer to internal details of the source view. + template + class __non_propagating_cache { + optional<_Tp> __value_ = nullopt; + + public: + _LIBCPP_HIDE_FROM_ABI __non_propagating_cache() = default; + + _LIBCPP_HIDE_FROM_ABI + constexpr __non_propagating_cache(__non_propagating_cache const&) noexcept + : __value_(nullopt) + { } + + _LIBCPP_HIDE_FROM_ABI + constexpr __non_propagating_cache(__non_propagating_cache&& __other) noexcept + : __value_(nullopt) + { + __other.__value_.reset(); + } + + _LIBCPP_HIDE_FROM_ABI + constexpr __non_propagating_cache& operator=(__non_propagating_cache const& __other) noexcept { + if (this != _VSTD::addressof(__other)) { + __value_.reset(); + } + return *this; + } + + _LIBCPP_HIDE_FROM_ABI + constexpr __non_propagating_cache& operator=(__non_propagating_cache&& __other) noexcept { + __value_.reset(); + __other.__value_.reset(); + return *this; + } + + _LIBCPP_HIDE_FROM_ABI + constexpr _Tp& operator*() { return *__value_; } + _LIBCPP_HIDE_FROM_ABI + constexpr _Tp const& operator*() const { return *__value_; } + + _LIBCPP_HIDE_FROM_ABI + constexpr bool __has_value() const { return __value_.has_value(); } + _LIBCPP_HIDE_FROM_ABI + constexpr void __set(_Tp const& __value) { __value_.emplace(__value); } + _LIBCPP_HIDE_FROM_ABI + constexpr void __set(_Tp&& __value) { __value_.emplace(_VSTD::move(__value)); } + }; + + struct __empty_cache { }; +} // namespace ranges + +#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_RANGES) + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___RANGES_NON_PROPAGATING_CACHE_H diff --git a/libcxx/include/module.modulemap b/libcxx/include/module.modulemap --- a/libcxx/include/module.modulemap +++ b/libcxx/include/module.modulemap @@ -611,6 +611,7 @@ module empty_view { private header "__ranges/empty_view.h" } module enable_borrowed_range { private header "__ranges/enable_borrowed_range.h" } module enable_view { private header "__ranges/enable_view.h" } + module non_propagating_cache { private header "__ranges/non_propagating_cache.h" } module ref_view { private header "__ranges/ref_view.h" } module size { private header "__ranges/size.h" } module subrange { private header "__ranges/subrange.h" } diff --git a/libcxx/test/libcxx/diagnostics/detail.headers/ranges/non_propagating_cache.module.verify.cpp b/libcxx/test/libcxx/diagnostics/detail.headers/ranges/non_propagating_cache.module.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/diagnostics/detail.headers/ranges/non_propagating_cache.module.verify.cpp @@ -0,0 +1,16 @@ +// -*- C++ -*- +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// REQUIRES: modules-build + +// WARNING: This test was generated by 'generate_private_header_tests.py' +// and should not be edited manually. + +// expected-error@*:* {{use of private header from outside its module: '__ranges/non_propagating_cache.h'}} +#include <__ranges/non_propagating_cache.h> diff --git a/libcxx/test/libcxx/ranges/range.nonprop.cache/assign.copy.pass.cpp b/libcxx/test/libcxx/ranges/range.nonprop.cache/assign.copy.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/ranges/range.nonprop.cache/assign.copy.pass.cpp @@ -0,0 +1,104 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: gcc-10 + +// __non_propagating_cache& operator=(__non_propagating_cache const&); + +// ADDITIONAL_COMPILE_FLAGS: -Wno-self-assign + +#include + +#include +#include +#include + +template +struct CopyAssignable { + int x; + constexpr explicit CopyAssignable(int i) : x(i) { } + CopyAssignable(CopyAssignable const&) = default; + constexpr CopyAssignable& operator=(CopyAssignable const& other) noexcept(NoexceptCopy) { + x = other.x; + return *this; + } + constexpr bool operator==(CopyAssignable const& other) const { return x == other.x; } +}; + +struct NotCopyAssignable { + int x; + constexpr explicit NotCopyAssignable(int i) : x(i) { } + NotCopyAssignable(NotCopyAssignable const&) = default; + NotCopyAssignable& operator=(NotCopyAssignable const&) = delete; + constexpr bool operator==(NotCopyAssignable const& other) const { return x == other.x; } +}; + +template +constexpr void test() { + using Cache = std::ranges::__non_propagating_cache; + static_assert(std::is_nothrow_copy_assignable_v); + + // Assign to an empty cache + { + Cache a; a.__set(T{3}); + Cache b; + + Cache& result = (b = a); + assert(&result == &b); + assert(!b.__has_value()); // make sure we don't propagate + + assert(a.__has_value()); // make sure we don't "steal" from the source + assert(*a == T{3}); // + } + + // Assign to a non-empty cache + { + Cache a; a.__set(T{3}); + Cache b; b.__set(T{5}); + + Cache& result = (b = a); + assert(&result == &b); + assert(!b.__has_value()); // make sure we don't propagate + + assert(a.__has_value()); // make sure we don't "steal" from the source + assert(*a == T{3}); // + } + + // Self-assignment should not do anything (case with empty cache) + { + Cache b; + Cache& result = (b = b); + assert(&result == &b); + assert(!b.__has_value()); + } + + // Self-assignment should not do anything (case with non-empty cache) + { + Cache b; b.__set(T{5}); + Cache& result = (b = b); + assert(&result == &b); + assert(b.__has_value()); + assert(*b == T{5}); + } +} + +constexpr bool tests() { + test>(); + test>(); + test(); + test(); + return true; +} + +int main(int, char**) { + static_assert(tests()); + tests(); + return 0; +} diff --git a/libcxx/test/libcxx/ranges/range.nonprop.cache/assign.move.pass.cpp b/libcxx/test/libcxx/ranges/range.nonprop.cache/assign.move.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/ranges/range.nonprop.cache/assign.move.pass.cpp @@ -0,0 +1,100 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: gcc-10 + +// __non_propagating_cache& operator=(__non_propagating_cache&&); + +// ADDITIONAL_COMPILE_FLAGS: -Wno-self-assign + +#include + +#include +#include +#include + +template +struct MoveAssignable { + int x; + constexpr explicit MoveAssignable(int i) : x(i) { } + MoveAssignable(MoveAssignable&&) = default; + constexpr MoveAssignable& operator=(MoveAssignable&& other) noexcept(NoexceptMove) { + x = other.x; + other.x = -1; + return *this; + } +}; + +struct NotMoveAssignable { + int x; + constexpr explicit NotMoveAssignable(int i) : x(i) { } + NotMoveAssignable(NotMoveAssignable&&) = default; + NotMoveAssignable& operator=(NotMoveAssignable&&) = delete; +}; + +template +constexpr void test() { + using Cache = std::ranges::__non_propagating_cache; + static_assert(std::is_nothrow_move_assignable_v); + + // Assign to an empty cache + { + Cache a; a.__set(T{3}); + Cache b; + + Cache& result = (b = std::move(a)); + assert(&result == &b); + assert(!b.__has_value()); // make sure we don't propagate + assert(!a.__has_value()); // make sure we disengage the source + } + + // Assign to a non-empty cache + { + Cache a; a.__set(T{3}); + Cache b; b.__set(T{5}); + + Cache& result = (b = std::move(a)); + assert(&result == &b); + assert(!b.__has_value()); // make sure we don't propagate + assert(!a.__has_value()); // make sure we disengage the source + } + + // Self-assignment should clear the cache (case with empty cache) + { + Cache b; + + Cache& result = (b = std::move(b)); + assert(&result == &b); + assert(!b.__has_value()); + } + + // Self-assignment should clear the cache (case with non-empty cache) + { + Cache b; b.__set(T{5}); + + Cache& result = (b = std::move(b)); + assert(&result == &b); + assert(!b.__has_value()); + } +} + +constexpr bool tests() { + test>(); + test>(); + test(); + test(); + return true; +} + +int main(int, char**) { + static_assert(tests()); + tests(); + return 0; +} diff --git a/libcxx/test/libcxx/ranges/range.nonprop.cache/ctor.copy.pass.cpp b/libcxx/test/libcxx/ranges/range.nonprop.cache/ctor.copy.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/ranges/range.nonprop.cache/ctor.copy.pass.cpp @@ -0,0 +1,75 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: gcc-10 + +// __non_propagating_cache(__non_propagating_cache const&); + +#include + +#include +#include + +template +struct CopyConstructible { + int x; + constexpr explicit CopyConstructible(int i) : x(i) { } + constexpr CopyConstructible(CopyConstructible const& other) noexcept(NoexceptCopy) : x(other.x) { } + CopyConstructible& operator=(CopyConstructible const&) = default; + constexpr bool operator==(CopyConstructible const& other) const { return x == other.x; } +}; + +struct NotCopyConstructible { + int x; + constexpr explicit NotCopyConstructible(int i) : x(i) { } + NotCopyConstructible(NotCopyConstructible const&) = delete; + NotCopyConstructible(NotCopyConstructible&&) = default; + constexpr bool operator==(NotCopyConstructible const& other) const { return x == other.x; } +}; + +template +constexpr void test() { + using Cache = std::ranges::__non_propagating_cache; + static_assert(std::is_nothrow_copy_constructible_v); + Cache a; + a.__set(T{3}); + + // Test with direct initialization + { + Cache b(a); + assert(!b.__has_value()); // make sure we don't propagate + + assert(a.__has_value()); // make sure we don't "steal" from the source + assert(*a == T{3}); // + } + + // Test with copy initialization + { + Cache b = a; + assert(!b.__has_value()); // make sure we don't propagate + + assert(a.__has_value()); // make sure we don't "steal" from the source + assert(*a == T{3}); // + } +} + +constexpr bool tests() { + test>(); + test>(); + test(); + test(); + return true; +} + +int main(int, char**) { + static_assert(tests()); + tests(); + return 0; +} diff --git a/libcxx/test/libcxx/ranges/range.nonprop.cache/ctor.default.pass.cpp b/libcxx/test/libcxx/ranges/range.nonprop.cache/ctor.default.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/ranges/range.nonprop.cache/ctor.default.pass.cpp @@ -0,0 +1,43 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: gcc-10 + +// __non_propagating_cache(); + +#include + +#include +#include + +struct HasDefault { HasDefault() = default; }; +struct NoDefault { NoDefault() = delete; }; + +template +constexpr void test() { + using Cache = std::ranges::__non_propagating_cache; + static_assert(std::is_nothrow_default_constructible_v); + Cache cache; + assert(!cache.__has_value()); +} + +constexpr bool tests() { + test(); + test(); + test(); + test(); + return true; +} + +int main(int, char**) { + static_assert(tests()); + tests(); + return 0; +} diff --git a/libcxx/test/libcxx/ranges/range.nonprop.cache/ctor.move.pass.cpp b/libcxx/test/libcxx/ranges/range.nonprop.cache/ctor.move.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/ranges/range.nonprop.cache/ctor.move.pass.cpp @@ -0,0 +1,66 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: gcc-10 + +// __non_propagating_cache(__non_propagating_cache&&); + +#include + +#include +#include +#include + +template +struct MoveConstructible { + int x; + constexpr explicit MoveConstructible(int i) : x(i) { } + constexpr MoveConstructible(MoveConstructible&& other) noexcept(NoexceptMove) : x(other.x) { other.x = -1; } + MoveConstructible& operator=(MoveConstructible&&) = default; +}; + +template +constexpr void test() { + using Cache = std::ranges::__non_propagating_cache; + static_assert(std::is_nothrow_move_constructible_v); + + // Test with direct initialization + { + Cache a; + a.__set(T{3}); + + Cache b(std::move(a)); + assert(!b.__has_value()); // make sure we don't propagate + assert(!a.__has_value()); // make sure we disengage the source + } + + // Test with copy initialization + { + Cache a; + a.__set(T{3}); + + Cache b = std::move(a); + assert(!b.__has_value()); // make sure we don't propagate + assert(!a.__has_value()); // make sure we disengage the source + } +} + +constexpr bool tests() { + test>(); + test>(); + test(); + return true; +} + +int main(int, char**) { + static_assert(tests()); + tests(); + return 0; +} diff --git a/libcxx/test/libcxx/ranges/range.nonprop.cache/deref.pass.cpp b/libcxx/test/libcxx/ranges/range.nonprop.cache/deref.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/ranges/range.nonprop.cache/deref.pass.cpp @@ -0,0 +1,55 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: gcc-10 + +// constexpr T const& operator*() const; +// constexpr T& operator*(); + +#include + +#include + +template +constexpr void test() { + using Cache = std::ranges::__non_propagating_cache; + + // non-const version + { + Cache cache; cache.__set(T{3}); + T& result = *cache; + assert(result == T{3}); + } + + // const version + { + Cache cache; cache.__set(T{3}); + T const& result = *static_cast(cache); + assert(result == T{3}); + } +} + +struct T { + int x; + constexpr explicit T(int i) : x(i) { } + constexpr bool operator==(T const& other) const { return x == other.x; } +}; + +constexpr bool tests() { + test(); + test(); + return true; +} + +int main(int, char**) { + static_assert(tests()); + tests(); + return 0; +} diff --git a/libcxx/test/libcxx/ranges/range.nonprop.cache/has_value.pass.cpp b/libcxx/test/libcxx/ranges/range.nonprop.cache/has_value.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/ranges/range.nonprop.cache/has_value.pass.cpp @@ -0,0 +1,48 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17 +// UNSUPPORTED: libcpp-no-concepts +// UNSUPPORTED: gcc-10 + +// constexpr bool __has_value() const; + +#include + +#include + +template +constexpr void test() { + using Cache = std::ranges::__non_propagating_cache; + + // __has_value on an empty cache + { + Cache const cache; + assert(!cache.__has_value()); + } + + // __has_value on a non-empty cache + { + Cache cache; cache.__set(T{}); + assert(cache.__has_value()); + } +} + +struct T { }; + +constexpr bool tests() { + test(); + test(); + return true; +} + +int main(int, char**) { + static_assert(tests()); + tests(); + return 0; +}