diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -20,6 +20,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 + 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 + 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::__tag()); +} // 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/check_round_trip.h b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/check_round_trip.h new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/check_round_trip.h @@ -0,0 +1,26 @@ +//===----------------------------------------------------------------------===// +// +// 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_PREV_CHECK_ROUND_TRIP_H +#define LIBCXX_TEST_PREV_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); +} + +#endif // LIBCXX_TEST_PREV_CHECK_ROUND_TRIP_H diff --git a/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/constraints.verify.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/constraints.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/constraints.verify.cpp @@ -0,0 +1,26 @@ +//===----------------------------------------------------------------------===// +// +// 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::prev + +#include + +#include + +#include "test_iterators.h" + +void proper_constraints() { + auto a = std::array{0, 1, 2}; + (void)std::ranges::prev(forward_iterator(a.begin())); // expected-error {{no matching function for call}} + (void)std::ranges::prev(forward_iterator(a.begin()), 5); // expected-error {{no matching function for call}} + (void)std::ranges::prev(forward_iterator(a.begin()), 7); // expected-error {{no matching function for call}} +} diff --git a/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/iterator.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/iterator.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/iterator.pass.cpp @@ -0,0 +1,35 @@ +//===----------------------------------------------------------------------===// +// +// 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::prev(iterator) + +#include + +#include +#include + +#include "check_round_trip.h" +#include "test_iterators.h" + +constexpr bool check_iterator() { + constexpr auto range = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; + 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; +} + +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.prev/iterator_count.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/iterator_count.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/iterator_count.pass.cpp @@ -0,0 +1,52 @@ +//===----------------------------------------------------------------------===// +// +// 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::prev(iterator, count) + +#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::prev(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(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; +} + +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.prev/iterator_count_sentinel.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/iterator_count_sentinel.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/iterator_count_sentinel.pass.cpp @@ -0,0 +1,51 @@ +//===----------------------------------------------------------------------===// +// +// 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::prev(iterator, count, sentinel) + +#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::prev(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(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; +} + +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.prev/special_function.compile.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/special_function.compile.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.prev/special_function.compile.pass.cpp @@ -0,0 +1,97 @@ +//===----------------------------------------------------------------------===// +// +// 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" +#include "test_standard_function.h" + +static_assert(is_function_like()); + +namespace std::ranges { +class fake_bidirectional_iterator { +public: + using value_type = int; + using difference_type = std::ptrdiff_t; + using iterator_category = std::bidirectional_iterator_tag; + + fake_bidirectional_iterator() = default; + + value_type operator*() const; + fake_bidirectional_iterator& operator++(); + fake_bidirectional_iterator operator++(int); + fake_bidirectional_iterator& operator--(); + fake_bidirectional_iterator operator--(int); + + bool operator==(fake_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]). +template +constexpr bool unqualified_lookup_works = requires(I i, Args... args) { + prev(i, args...); +}; + +static_assert(!unqualified_lookup_works); +static_assert(!unqualified_lookup_works); +static_assert(!unqualified_lookup_works); + +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 prev(bidirectional_iterator) { + static_assert(std::same_as); +} + +template +void prev(bidirectional_iterator, std::ptrdiff_t) { + static_assert(std::same_as); +} + +template +void prev(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; + + (void)prev(x); + (void)prev(x, 5); + (void)prev(x, 6, x); +}