diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -19,6 +19,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 + constexpr _Ip operator()(_Ip __x) const { + ++__x; + return __x; + } + + template + constexpr _Ip operator()(_Ip __x, iter_difference_t<_Ip> __n) const { + ranges::advance(__x, __n); + return __x; + } + + template _Sp> + constexpr _Ip operator()(_Ip __x, _Sp __bound) const { + ranges::advance(__x, __bound); + return __x; + } + + template _Sp> + 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::__tag()); +} // 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/check_round_trip.h b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/check_round_trip.h new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/check_round_trip.h @@ -0,0 +1,31 @@ +//===----------------------------------------------------------------------===// +// +// 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 LIBCXX_TEST_CHECK_ROUND_TRIP_H +#define LIBCXX_TEST_CHECK_ROUND_TRIP_H + +#include "test_iterators.h" + +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(); +} + +#endif // LIBCXX_TEST_CHECK_ROUND_TRIP_H diff --git a/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/constraints.verify.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/constraints.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/constraints.verify.cpp @@ -0,0 +1,27 @@ +//===----------------------------------------------------------------------===// +// +// 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 "test_iterators.h" + +void proper_constraints() { + auto p = std::unique_ptr(); + std::ranges::next(p); // expected-error {{no matching function for call}} + std::ranges::next(p, p); // expected-error {{no matching function for call}} + std::ranges::next(p, 5); // expected-error {{no matching function for call}} + std::ranges::next(p, 7); // expected-error {{no matching function for call}} +} diff --git a/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/iterator.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/iterator.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/iterator.pass.cpp @@ -0,0 +1,41 @@ +//===----------------------------------------------------------------------===// +// +// 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(first, n) + +#include + +#include +#include + +#include "check_round_trip.h" +#include "test_iterators.h" + +using range_t = std::array; + +constexpr bool check_iterator() { + constexpr auto range = range_t{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + 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; +} + +int main(int, char**) { + static_assert(check_iterator()); + check_iterator(); + return 0; +} diff --git a/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/iterator_count.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/iterator_count.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/iterator_count.pass.cpp @@ -0,0 +1,61 @@ +//===----------------------------------------------------------------------===// +// +// 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(first, n) + +#include + +#include +#include + +#include "check_round_trip.h" +#include "test_iterators.h" + +using range_t = std::array; + +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); +} + +constexpr bool check_iterator_count() { + constexpr auto range = range_t{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + + 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; +} + +int main(int, char**) { + static_assert(check_iterator_count()); + check_iterator_count(); + return 0; +} diff --git a/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/iterator_count_sentinel.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/iterator_count_sentinel.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/iterator_count_sentinel.pass.cpp @@ -0,0 +1,57 @@ +//===----------------------------------------------------------------------===// +// +// 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 "check_round_trip.h" +#include "test_iterators.h" + +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); +} + +constexpr bool check_iterator_count_sentinel() { + constexpr auto range = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + 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; +} + +int main(int, char**) { + static_assert(check_iterator_count_sentinel()); + assert(check_iterator_count_sentinel()); + + return 0; +} diff --git a/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/iterator_sentinel.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/iterator_sentinel.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/iterator_sentinel.pass.cpp @@ -0,0 +1,105 @@ +//===----------------------------------------------------------------------===// +// +// 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 "check_round_trip.h" +#include "test_iterators.h" + +using range_t = std::array; + +class distance_apriori_sentinel { +public: + distance_apriori_sentinel() = default; + constexpr explicit distance_apriori_sentinel(std::ptrdiff_t const count) : count_(count) {} + + constexpr bool operator==(std::input_or_output_iterator auto const&) const { + assert(false && "difference op should take precedence"); + return false; + } + + constexpr friend std::ptrdiff_t operator-(std::input_or_output_iterator auto const&, + distance_apriori_sentinel const y) { + return -y.count_; + } + + 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` +} + +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; +} + +int main(int, char**) { + static_assert(check_iterator_sentinel()); + check_iterator_sentinel(); + return 0; +} diff --git a/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/special_function.compile.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/special_function.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/special_function.compile.pass.cpp @@ -0,0 +1,103 @@ +//===----------------------------------------------------------------------===// +// +// 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_standard_function.h" + +static_assert(is_function_like()); + +// FIXME: We're bending the rules here by adding a new type to namespace std::ranges. Since this is +// the standard library's test suite, this should be fine (we *are* the implementation), but it's +// necessary at the time of writing since there aren't any iterators in std::ranges that we can +// borrow for this test. +namespace std::ranges { +class fake_forward_iterator { +public: + using value_type = int; + using difference_type = std::ptrdiff_t; + using iterator_category = std::forward_iterator_tag; + + fake_forward_iterator() = default; + + value_type operator*() const; + fake_forward_iterator& operator++(); + fake_forward_iterator operator++(int); + + bool operator==(fake_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]). +template +constexpr bool unqualified_lookup_works = requires(I i, Args... args) { + next(i, args...); +}; + +static_assert(!unqualified_lookup_works); +static_assert(!unqualified_lookup_works); +static_assert(!unqualified_lookup_works); +static_assert( + !unqualified_lookup_works); + +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) { + static_assert(std::same_as); +} + +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; + + (void)next(x); + (void)next(x, 5); + (void)next(x, x); + (void)next(x, 6, x); +}