diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -18,6 +18,7 @@ __iterator/iter_move.h __iterator/iterator_traits.h __iterator/next.h + __iterator/prev.h __iterator/readable_traits.h __libcpp_version __locale diff --git a/libcxx/include/__iterator/prev.h b/libcxx/include/__iterator/prev.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__iterator/prev.h @@ -0,0 +1,62 @@ +// -*- 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___ITERATOR_PREV_H +#define _LIBCPP___ITERATOR_PREV_H + +#include <__config> +#include <__function_like.h> +#include <__iterator/advance.h> +#include <__iterator/concepts.h> +#include <__iterator/incrementable_traits.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +#pragma GCC system_header +#endif + +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if !defined(_LIBCPP_HAS_NO_RANGES) + +namespace ranges { +struct __prev_fn final : private __function_like { + constexpr explicit __prev_fn(__tag __x) noexcept : __function_like(__x) {} + + template + [[nodiscard]] constexpr _Ip operator()(_Ip __x) const { + --__x; + return __x; + } + + template + [[nodiscard]] constexpr _Ip operator()(_Ip __x, iter_difference_t<_Ip> __n) const { + ranges::advance(__x, -__n); + return __x; + } + + template + [[nodiscard]] constexpr _Ip operator()(_Ip __x, iter_difference_t<_Ip> __n, _Ip __bound) const { + ranges::advance(__x, -__n, __bound); + return __x; + } +}; + +inline constexpr auto prev = __prev_fn(__function_like::__value); +} // namespace ranges + +#endif // !defined(_LIBCPP_HAS_NO_RANGES) + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ITERATOR_PREV_H diff --git a/libcxx/include/iterator b/libcxx/include/iterator --- a/libcxx/include/iterator +++ b/libcxx/include/iterator @@ -489,6 +489,7 @@ #include <__iterator/iter_move.h> #include <__iterator/iterator_traits.h> #include <__iterator/next.h> +#include <__iterator/prev.h> #include <__iterator/readable_traits.h> #include <__memory/addressof.h> #include <__memory/pointer_traits.h> diff --git a/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/prev.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/prev.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/prev.pass.cpp @@ -0,0 +1,109 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// ranges::next + +#include + +#include +#include + +#include "test_standard_function.h" +#include "test_iterators.h" + +static_assert(is_function_like()); + +using range_t = std::array; +constexpr auto range = range_t{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + +template +constexpr void check_round_trip(stride_counting_iterator const& i, std::ptrdiff_t const n) { + auto const distance = n < 0 ? -n : n; + assert(i.stride_count() == distance); + assert(i.stride_displacement() == -n); +} + +template +constexpr void check_round_trip(stride_counting_iterator const& i, std::ptrdiff_t const n) { + assert(i.stride_count() <= 1); + assert(i.stride_displacement() == n < 0 ? -1 : 1); +} + +namespace iterator { +[[nodiscard]] constexpr bool check_iterator() { + assert(std::ranges::prev(bidirectional_iterator(&range[4])) == bidirectional_iterator(&range[3])); + assert(std::ranges::prev(random_access_iterator(&range[5])) == random_access_iterator(&range[4])); + assert(std::ranges::prev(contiguous_iterator(&range[6])) == contiguous_iterator(&range[5])); + return true; +} +} // namespace iterator + +namespace iterator_count { +template +constexpr void iterator_count_impl(I first, std::ptrdiff_t const n, range_t::const_iterator const expected) { + auto result = std::ranges::prev(stride_counting_iterator(std::move(first)), n); + assert(std::move(result).base().base() == expected); + check_round_trip(result, n); +} + +[[nodiscard]] constexpr bool check_iterator_count() { + iterator_count_impl(bidirectional_iterator(&range[8]), 6, &range[2]); + iterator_count_impl(random_access_iterator(&range[7]), 4, &range[3]); + iterator_count_impl(contiguous_iterator(&range[5]), 5, &range[0]); + + iterator_count_impl(bidirectional_iterator(&range[2]), 0, &range[2]); + iterator_count_impl(random_access_iterator(&range[3]), 0, &range[3]); + iterator_count_impl(contiguous_iterator(&range[0]), 0, &range[0]); + + iterator_count_impl(bidirectional_iterator(&range[3]), -5, &range[8]); + iterator_count_impl(random_access_iterator(&range[3]), -3, &range[6]); + iterator_count_impl(contiguous_iterator(&range[3]), -1, &range[4]); + return true; +} +} // namespace iterator_count + +namespace iterator_count_sentinel { +template +constexpr void check_iterator_count_sentinel_impl(I first, std::ptrdiff_t const steps, I const last) { + auto result = std::ranges::prev(stride_counting_iterator(first), steps, stride_counting_iterator(last)); + assert(result == last); + check_round_trip(result, steps); +} + +[[nodiscard]] constexpr bool check_iterator_count_sentinel() { + check_iterator_count_sentinel_impl(bidirectional_iterator(&range[8]), 6, bidirectional_iterator(&range[2])); + check_iterator_count_sentinel_impl(random_access_iterator(&range[5]), 2, random_access_iterator(&range[3])); + check_iterator_count_sentinel_impl(contiguous_iterator(&range[5]), 5, contiguous_iterator(&range[0])); + + check_iterator_count_sentinel_impl(bidirectional_iterator(&range[2]), 0, bidirectional_iterator(&range[2])); + check_iterator_count_sentinel_impl(random_access_iterator(&range[3]), 0, random_access_iterator(&range[3])); + check_iterator_count_sentinel_impl(contiguous_iterator(&range[0]), 0, contiguous_iterator(&range[0])); + + check_iterator_count_sentinel_impl(bidirectional_iterator(&range[5]), -1, bidirectional_iterator(&range[6])); + check_iterator_count_sentinel_impl(random_access_iterator(&range[5]), -2, random_access_iterator(&range[7])); + check_iterator_count_sentinel_impl(contiguous_iterator(&range[5]), -3, contiguous_iterator(&range[8])); + return true; +} +} // namespace iterator_count_sentinel + +int main(int, char**) { + static_assert(iterator::check_iterator()); + assert(iterator::check_iterator()); + + static_assert(iterator_count::check_iterator_count()); + assert(iterator_count::check_iterator_count()); + + static_assert(iterator_count_sentinel::check_iterator_count_sentinel()); + assert(iterator_count_sentinel::check_iterator_count_sentinel()); + + return 0; +} diff --git a/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/prev.verify.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/prev.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/prev.verify.cpp @@ -0,0 +1,99 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +// ranges::next + +#include + +#include "test_iterators.h" + +namespace std::ranges { +class bidirectional_iterator { +public: + using value_type = int; + using difference_type = std::ptrdiff_t; + using iterator_category = std::bidirectional_iterator_tag; + + bidirectional_iterator() = default; + + value_type operator*() const; + bidirectional_iterator& operator++(); + bidirectional_iterator operator++(int); + bidirectional_iterator& operator--(); + bidirectional_iterator operator--(int); + + bool operator==(bidirectional_iterator const&) const = default; +}; +} // namespace std::ranges + +// The function templates defined in [range.iter.ops] are not found by argument-dependent name lookup ([basic.lookup.argdep]). +void no_adl_participation() { + std::ranges::bidirectional_iterator x; + prev(x, 0); // expected-error{{use of undeclared identifier 'prev'}} + prev(x, x); // expected-error {{use of undeclared identifier 'prev'}} + // expected-error@*:*{{no matching function for call to 'prev'}} + prev(x, 0, x); // expected-error {{use of undeclared identifier 'prev'}} +} + +namespace test { +template +class bidirectional_iterator { +public: + using value_type = int; + using difference_type = std::ptrdiff_t; + using iterator_category = std::bidirectional_iterator_tag; + + bidirectional_iterator() = default; + + value_type operator*() const; + bidirectional_iterator& operator++(); + bidirectional_iterator operator++(int); + bidirectional_iterator& operator--(); + bidirectional_iterator operator--(int); + + bool operator==(bidirectional_iterator const&) const = default; +}; + +template +void next(bidirectional_iterator&, std::ptrdiff_t) { + static_assert(std::same_as); +} + +template +void next(bidirectional_iterator&, bidirectional_iterator) { + static_assert(std::same_as); +} + +template +void next(bidirectional_iterator&, std::ptrdiff_t, bidirectional_iterator) { + static_assert(std::same_as); +} +} // namespace test + +// When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a +// function call ([expr.call]), they inhibit argument-dependent name lookup. +void adl_inhibition() { + test::bidirectional_iterator x; + + using std::ranges::prev; + + prev(x); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}} + prev(x, 5); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}} + prev(x, 6, x); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}} +} + +void proper_constraints() { + forward_iterator i; + (void)std::ranges::prev(i); // expected-error {{no matching function for call}} + (void)std::ranges::prev(i, 5); // expected-error {{no matching function for call}} + (void)std::ranges::prev(i, 7); // expected-error {{no matching function for call}} +}