diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -17,6 +17,7 @@ __iterator/incrementable_traits.h __iterator/iter_move.h __iterator/iterator_traits.h + __iterator/next.h __iterator/readable_traits.h __libcpp_version __locale diff --git a/libcxx/include/__iterator/next.h b/libcxx/include/__iterator/next.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__iterator/next.h @@ -0,0 +1,68 @@ +// -*- 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_NEXT_H +#define _LIBCPP___ITERATOR_NEXT_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 __next_fn final : private __function_like { + constexpr explicit __next_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 _Sp> + [[nodiscard]] constexpr _Ip operator()(_Ip __x, _Sp __bound) const { + ranges::advance(__x, __bound); + return __x; + } + + template _Sp> + [[nodiscard]] constexpr _Ip operator()(_Ip __x, iter_difference_t<_Ip> __n, _Sp __bound) const { + ranges::advance(__x, __n, __bound); + return __x; + } +}; + +inline constexpr auto next = __next_fn(__function_like::__value); +} // namespace ranges + +#endif // !defined(_LIBCPP_HAS_NO_RANGES) + +_LIBCPP_END_NAMESPACE_STD + +_LIBCPP_POP_MACROS + +#endif // _LIBCPP___ITERATOR_PRIMITIVES_H diff --git a/libcxx/include/iterator b/libcxx/include/iterator --- a/libcxx/include/iterator +++ b/libcxx/include/iterator @@ -488,6 +488,7 @@ #include <__iterator/incrementable_traits.h> #include <__iterator/iter_move.h> #include <__iterator/iterator_traits.h> +#include <__iterator/next.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.next/next.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/next.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/next.pass.cpp @@ -0,0 +1,212 @@ +//===----------------------------------------------------------------------===// +// +// 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); +} + +template +constexpr bool operator==(output_iterator const& x, output_iterator const& y) { + return x.base() == y.base(); +} + +namespace iterator { +[[nodiscard]] constexpr bool check_iterator() { + assert(std::ranges::next(cpp17_input_iterator(&range[0])) == cpp17_input_iterator(&range[1])); + assert(std::ranges::next(cpp20_input_iterator(&range[1])).base() == &range[2]); + assert(std::ranges::next(forward_iterator(&range[2])) == forward_iterator(&range[3])); + assert(std::ranges::next(bidirectional_iterator(&range[3])) == bidirectional_iterator(&range[4])); + assert(std::ranges::next(random_access_iterator(&range[4])) == random_access_iterator(&range[5])); + assert(std::ranges::next(contiguous_iterator(&range[5])) == contiguous_iterator(&range[6])); + assert(std::ranges::next(output_iterator(&range[6])).base() == &range[7]); + 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::next(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(cpp17_input_iterator(&range[0]), 1, &range[1]); + iterator_count_impl(cpp20_input_iterator(&range[6]), 2, &range[8]); + iterator_count_impl(forward_iterator(&range[0]), 3, &range[3]); + iterator_count_impl(bidirectional_iterator(&range[2]), 6, &range[8]); + iterator_count_impl(random_access_iterator(&range[3]), 4, &range[7]); + iterator_count_impl(contiguous_iterator(&range[0]), 5, &range[5]); + iterator_count_impl(output_iterator(&range[0]), 6, &range[6]); + + iterator_count_impl(cpp17_input_iterator(&range[0]), 0, &range[0]); + iterator_count_impl(cpp20_input_iterator(&range[6]), 0, &range[6]); + iterator_count_impl(forward_iterator(&range[0]), 0, &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(output_iterator(&range[0]), 0, &range[0]); + + iterator_count_impl(bidirectional_iterator(&range[8]), -5, &range[3]); + iterator_count_impl(random_access_iterator(&range[6]), -3, &range[3]); + iterator_count_impl(contiguous_iterator(&range[4]), -1, &range[3]); + return true; +} +} // namespace iterator_count + +namespace iterator_sentinel { +class distance_apriori_sentinel { +public: + distance_apriori_sentinel() = default; + constexpr explicit distance_apriori_sentinel(std::ptrdiff_t const count) : count_(count) {} + + [[nodiscard]] constexpr bool operator==(std::input_or_output_iterator auto const&) const { + assert(false && "difference op should take precedence"); + return false; + } + + [[nodiscard]] constexpr friend std::ptrdiff_t operator-(std::input_or_output_iterator auto const&, + distance_apriori_sentinel const y) { + return -y.count_; + } + + [[nodiscard]] constexpr friend std::ptrdiff_t operator-(distance_apriori_sentinel const x, + std::input_or_output_iterator auto const&) { + return x.count_; + } + +private: + std::ptrdiff_t count_ = 0; +}; + +template +constexpr void check_assignable_case(std::ptrdiff_t const n) { + auto range = range_t{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + auto result = + std::ranges::next(stride_counting_iterator(I(range.begin())), stride_counting_iterator(I(range.begin() + n))); + assert(result.base().base() == range.begin() + n); + assert(result.stride_count() == 0); // always zero, so don't use `check_round_trip` +} + +template +constexpr void check_sized_sentinel_case(std::ptrdiff_t const n) { + auto range = range_t{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + auto result = std::ranges::next(stride_counting_iterator(I(range.begin())), distance_apriori_sentinel(n)); + assert(std::move(result).base().base() == range.begin() + n); + check_round_trip(result, n); +} + +template +constexpr void check_sentinel_case(std::ptrdiff_t const n) { + auto range = range_t{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + auto const last = I(range.begin() + n); + auto result = std::ranges::next(stride_counting_iterator(I(range.begin())), sentinel_wrapper(last)); + assert(std::move(result).base() == last); + assert(result.stride_count() == n); // always `n`, so don't use `check_round_trip` +} + +[[nodiscard]] constexpr bool check_iterator_sentinel() { + check_assignable_case >(1); + check_assignable_case >(3); + check_assignable_case >(4); + check_assignable_case >(5); + check_assignable_case >(6); + check_assignable_case >(7); + + check_sized_sentinel_case >(7); + check_sized_sentinel_case >(6); + check_sized_sentinel_case >(5); + check_sized_sentinel_case >(4); + check_sized_sentinel_case >(3); + check_sized_sentinel_case >(2); + check_sized_sentinel_case >(1); + + check_sentinel_case >(1); + // cpp20_input_iterator not copyable, so is omitted + check_sentinel_case >(3); + check_sentinel_case >(4); + check_sentinel_case >(5); + check_sentinel_case >(6); + check_sentinel_case >(7); + return true; +} +} // namespace iterator_sentinel +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::next(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(cpp17_input_iterator(&range[0]), 1, cpp17_input_iterator(&range[1])); + check_iterator_count_sentinel_impl(forward_iterator(&range[0]), 2, forward_iterator(&range[2])); + check_iterator_count_sentinel_impl(bidirectional_iterator(&range[2]), 6, bidirectional_iterator(&range[8])); + check_iterator_count_sentinel_impl(random_access_iterator(&range[3]), 2, random_access_iterator(&range[5])); + check_iterator_count_sentinel_impl(contiguous_iterator(&range[0]), 5, contiguous_iterator(&range[5])); + check_iterator_count_sentinel_impl(output_iterator(&range[3]), 2, output_iterator(&range[5])); + + check_iterator_count_sentinel_impl(cpp17_input_iterator(&range[0]), 0, cpp17_input_iterator(&range[0])); + check_iterator_count_sentinel_impl(forward_iterator(&range[0]), 0, forward_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(output_iterator(&range[3]), 0, output_iterator(&range[3])); + + check_iterator_count_sentinel_impl(bidirectional_iterator(&range[6]), -1, bidirectional_iterator(&range[5])); + check_iterator_count_sentinel_impl(random_access_iterator(&range[7]), -2, random_access_iterator(&range[5])); + check_iterator_count_sentinel_impl(contiguous_iterator(&range[8]), -3, contiguous_iterator(&range[5])); + 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_sentinel::check_iterator_sentinel()); + assert(iterator_sentinel::check_iterator_sentinel()); + + 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.next/next.verify.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/next.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/next.verify.cpp @@ -0,0 +1,89 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +namespace std::ranges { +class forward_iterator { +public: + using value_type = int; + using difference_type = std::ptrdiff_t; + using iterator_category = std::forward_iterator_tag; + + forward_iterator() = default; + + value_type operator*() const; + forward_iterator& operator++(); + forward_iterator operator++(int); + + bool operator==(forward_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::forward_iterator x; + next(x, 0); // expected-error{{use of undeclared identifier 'next'}} + next(x, x); // expected-error {{use of undeclared identifier 'next'}} + // expected-error@*:*{{no matching function for call to 'next'}} + next(x, 0, x); // expected-error {{use of undeclared identifier 'next'}} +} + +namespace test { +template +class forward_iterator { +public: + using value_type = int; + using difference_type = std::ptrdiff_t; + using iterator_category = std::forward_iterator_tag; + + forward_iterator() = default; + + value_type operator*() const; + forward_iterator& operator++(); + forward_iterator operator++(int); + + bool operator==(forward_iterator const&) const = default; +}; + +template +void next(forward_iterator&, std::ptrdiff_t) { + static_assert(std::same_as); +} + +template +void next(forward_iterator&, forward_iterator) { + static_assert(std::same_as); +} + +template +void next(forward_iterator&, std::ptrdiff_t, forward_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::forward_iterator x; + + using std::ranges::next; + + next(x); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}} + next(x, 5); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}} + next(x, x); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}} + next(x, 6, x); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}} +}