[libcxx][iterator] adds `std::ranges::next`

[cjdb]

Summary

Implements part of P0896 'The One Ranges Proposal'.
Implements [range.iter.op.next].

Depends on D101922.

[ldionne]

You need to mark it [[nodiscard]] as an extension in the synopsis in <iterator>.

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/next.pass.cpp

13 ↗

(On Diff #345658)

Normally, we have one test file per overload. I know this slipped through for most ranges reviews so far, but it would be good to do it.

67 ↗

(On Diff #345658)

Drop [[nodiscard]] from the tests please!

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/next.verify.cpp

1 ↗

(On Diff #345658)

The nodiscard part should be in libcxx/test/libcxx since it's an extension.

[cjdb]

Applies @ldionne's feedback:

• removes [[nodiscard]] from ranges::next (per offline discussion: things not explicitly marked [[nodiscard]] in the wording to be on hold till after P2351R0 and P2377R0 are discussed in Library Evolution)
• removes [[nodiscard]] from tests
• splits single next.pass.cpp into four files, one for each overload

[cjdb]

rebases to see if CI started working properly

libcxx/include/CMakeLists.txt

set(files
   __functional_base
   __functional_base_03
   __hash_table
   __iterator/advance.h
   __iterator/concepts.h
   __iterator/incrementable_traits.h
   __iterator/iter_move.h
   __iterator/iterator_traits.h
+  __iterator/next.h
   __iterator/readable_traits.h
   __libcpp_version
   __locale
   __memory/addressof.h
   __memory/allocation_guard.h
   __memory/allocator.h
   __memory/allocator_traits.h
   __memory/auto_ptr.h

libcxx/include/__iterator/next.h

+// -*- 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 <input_or_output_iterator _Ip>
+  constexpr _Ip operator()(_Ip __x) const {
+    ++__x;
+    return __x;
+  }
+
+  template <input_or_output_iterator _Ip>
+  constexpr _Ip operator()(_Ip __x, iter_difference_t<_Ip> __n) const {
+    ranges::advance(__x, __n);
+    return __x;
+  }
+
+  template <input_or_output_iterator _Ip, sentinel_for<_Ip> _Sp>
+  constexpr _Ip operator()(_Ip __x, _Sp __bound) const {
+    ranges::advance(__x, __bound);
+    return __x;
+  }
+
+  template <input_or_output_iterator _Ip, sentinel_for<_Ip> _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

libcxx/include/iterator

 #include <__config>
 #include <__debug>
 #include <__functional_base>
 #include <__iterator/advance.h>
 #include <__iterator/concepts.h>
 #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>
 #include <compare>
 #include <concepts> // Mandated by the Standard.
 #include <cstddef>
 #include <initializer_list>
 #include <iosfwd> // for forward declarations of vector and string

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/check_round_trip.h

+//===----------------------------------------------------------------------===//
+//
+// 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 <std::input_or_output_iterator I>
+constexpr void check_round_trip(stride_counting_iterator<I> 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 <std::random_access_iterator I>
+constexpr void check_round_trip(stride_counting_iterator<I> const& i, std::ptrdiff_t const n) {
+  assert(i.stride_count() <= 1);
+  assert(i.stride_displacement() == n < 0 ? -1 : 1);
+}
+
+template <std::input_or_output_iterator I>
+constexpr bool operator==(output_iterator<I> const& x, output_iterator<I> const& y) {
+  return x.base() == y.base();
+}
+
+#endif // LIBCXX_TEST_CHECK_ROUND_TRIP_H

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/constraints.verify.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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 <iterator>
+
+#include <memory>
+
+#include "test_iterators.h"
+
+void proper_constraints() {
+  auto p = std::unique_ptr<int>();
+  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}}
+}

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/iterator.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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 <iterator>
+
+#include <array>
+#include <cassert>
+
+#include "check_round_trip.h"
+#include "test_iterators.h"
+
+using range_t = std::array<int, 10>;
+
+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;
+}

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/iterator_count.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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 <iterator>
+
+#include <array>
+#include <cassert>
+
+#include "check_round_trip.h"
+#include "test_iterators.h"
+
+using range_t = std::array<int, 10>;
+
+template <std::input_or_output_iterator I>
+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;
+}

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/iterator_count_sentinel.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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 <iterator>
+
+#include <array>
+#include <cassert>
+
+#include "check_round_trip.h"
+#include "test_iterators.h"
+
+template <std::input_or_output_iterator I>
+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;
+}

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/iterator_sentinel.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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 <iterator>
+
+#include <array>
+#include <cassert>
+
+#include "check_round_trip.h"
+#include "test_iterators.h"
+
+using range_t = std::array<int, 10>;
+
+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 <std::input_or_output_iterator I>
+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 <std::input_or_output_iterator I>
+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 <std::input_or_output_iterator I>
+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<cpp17_input_iterator<range_t::const_iterator> >(1);
+  check_assignable_case<forward_iterator<range_t::const_iterator> >(3);
+  check_assignable_case<bidirectional_iterator<range_t::const_iterator> >(4);
+  check_assignable_case<random_access_iterator<range_t::const_iterator> >(5);
+  check_assignable_case<contiguous_iterator<range_t::const_iterator> >(6);
+  check_assignable_case<output_iterator<range_t::iterator> >(7);
+
+  check_sized_sentinel_case<cpp17_input_iterator<range_t::const_iterator> >(7);
+  check_sized_sentinel_case<cpp20_input_iterator<range_t::const_iterator> >(6);
+  check_sized_sentinel_case<forward_iterator<range_t::const_iterator> >(5);
+  check_sized_sentinel_case<bidirectional_iterator<range_t::const_iterator> >(4);
+  check_sized_sentinel_case<random_access_iterator<range_t::const_iterator> >(3);
+  check_sized_sentinel_case<contiguous_iterator<range_t::const_iterator> >(2);
+  check_sized_sentinel_case<output_iterator<range_t::iterator> >(1);
+
+  check_sentinel_case<cpp17_input_iterator<range_t::const_iterator> >(1);
+  // cpp20_input_iterator not copyable, so is omitted
+  check_sentinel_case<forward_iterator<range_t::const_iterator> >(3);
+  check_sentinel_case<bidirectional_iterator<range_t::const_iterator> >(4);
+  check_sentinel_case<random_access_iterator<range_t::const_iterator> >(5);
+  check_sentinel_case<contiguous_iterator<range_t::const_iterator> >(6);
+  check_sentinel_case<output_iterator<range_t::iterator> >(7);
+  return true;
+}
+
+int main(int, char**) {
+  static_assert(check_iterator_sentinel());
+  check_iterator_sentinel();
+  return 0;
+}

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.next/special_function.compile.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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 <iterator>
+
+#include "test_standard_function.h"
+
+static_assert(is_function_like<decltype(std::ranges::next)>());
+
+// 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 <class I, class... Args>
+constexpr bool unqualified_lookup_works = requires(I i, Args... args) {
+  next(i, args...);
+};
+
+static_assert(!unqualified_lookup_works<std::ranges::fake_forward_iterator>);
+static_assert(!unqualified_lookup_works<std::ranges::fake_forward_iterator, std::ptrdiff_t>);
+static_assert(!unqualified_lookup_works<std::ranges::fake_forward_iterator, std::ranges::fake_forward_iterator>);
+static_assert(
+    !unqualified_lookup_works<std::ranges::fake_forward_iterator, std::ptrdiff_t, std::ranges::fake_forward_iterator>);
+
+namespace test {
+template <class>
+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 <class I>
+void next(forward_iterator<I>) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class I>
+void next(forward_iterator<I>, std::ptrdiff_t) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class I>
+void next(forward_iterator<I>, forward_iterator<I>) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class I>
+void next(forward_iterator<I>, std::ptrdiff_t, forward_iterator<I>) {
+  static_assert(std::same_as<I, I*>);
+}
+} // 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<int*> x;
+
+  using std::ranges::next;
+
+  (void)next(x);
+  (void)next(x, 5);
+  (void)next(x, x);
+  (void)next(x, 6, x);
+}