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

[cjdb]

Summary

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

Depends on D102564 and D102434.

[• Quuxplusone]

libcxx/include/__iterator/distance.h

40–45

Please put lines 40-45 in an else block, so that we don't instantiate them unnecessarily in the case that the if block is taken.

48–55

I notice we're not doing the noexcept thing here. Is that because https://eel.is/c++draft/range.iter.op.distance#3 says merely "equivalent to" instead of the term of power "expression-equivalent to"?

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

17

I don't think you're (that is, I don't think the programmer is) allowed to add your own types to namespace std::ranges.

39–46

We could do this in a .pass.cpp by SFINAE-testing the well-formedness of distance(r), instead of relying on the exact wording of the compiler error and then having to skip the test for non-Clang compilers.

[cjdb]

libcxx/include/__iterator/distance.h

48–55

Yes. As it is, the noexcept specifiers would either be really difficult to read or would need their own special functions, neither of which I'm keen to do.

I've just noticed that having four overloads won't hurt readability like it did with ranges::advance, so I think I can get away with making ranges::distance noexcept without it being a colossal eyesore. (I might have fixed the problem with ranges::advance, so I'll need to go back and check soon.)

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

17

I'm aware users aren't allowed to do this, but we're testing the standard library here. We need to ensure that ADL doesn't find something in the same namespace as the function, but there's nothing to test with (no range adaptors have been merged with main yet).

39–46

Something like this?

template<class T>
constexpr bool is_adl_friendly = requires(T t) { distance(t); };

static_assert(!is_adl_friendly<std::ranges::forward_iterator>);
static_assert(!is_adl_friendly<std::ranges::some_range>);

[Mordante]

SGTM. no real comments from me, I'll have another look after you addressed Arthur's review comments.

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

17

Would it make sense to add a TODO and improve this test after we have adaptors?

[ldionne]

libcxx/include/__iterator/distance.h

35

Drop [[nodiscard]]

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

13

Please split into two test files, one for each overload.

45

Can we avoid using a global range here (and below) and instead have a local variable? It's a tiny difference but it helps local reasoning.

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

17

@cjdb Please add a TODO like you've done in other patches, we'll go back and fix it as soon as we check-in an adaptor.

libcxx/test/support/test_iterators.h

877

Drop [[nodiscard]] from the tests (here and elsewhere), except for really vexing cases as we've discussed (but I don't think there's any).

[cjdb]

Changes to be applied in the next day or so.

libcxx/include/__iterator/distance.h

35

After much deliberation on this, I think it's worth considering that we keep [[nodiscard]] on anything that consumes a proper input_iterator or output_iterator. Two reasons:

• they could be move-only (thus the result is lost forever)

libcxx/include/CMakeLists.txt

 set(files
   __availability
   __bit_reference
   __bits
   __bsd_locale_defaults.h
   __bsd_locale_fallbacks.h
   __config
   __debug
   __errc
   __function_like.h
   __functional_03
   __functional_base
   __functional_base_03
   __hash_table
   __iterator/advance.h
   __iterator/concepts.h
+  __iterator/distance.h
   __iterator/incrementable_traits.h
   __iterator/iter_move.h
   __iterator/iterator_traits.h
   __iterator/next.h
   __iterator/prev.h
   __iterator/readable_traits.h
   __libcpp_version
   __locale

libcxx/include/__iterator/distance.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_DISTANCE_H
+#define _LIBCPP___ITERATOR_DISTANCE_H
+
+#include <__config>
+#include <__function_like.h>
+#include <__iterator/concepts.h>
+#include <__iterator/incrementable_traits.h>
+#include <__ranges/concepts.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 __distance_fn final : __function_like {
+  constexpr explicit __distance_fn(__tag __x) noexcept : __function_like(__x) {}
+
+  template <input_or_output_iterator _Ip, sentinel_for<_Ip> _Sp>
+  [[nodiscard]] constexpr iter_difference_t<_Ip> operator()(_Ip __first, _Sp __last) const {
+    if constexpr (sized_sentinel_for<_Sp, _Ip>) {
+      return __last - __first;
+    }
+
+    auto __distance = iter_difference_t<_Ip>(0);
+    for (; __first != __last; ++__first) {
+      ++__distance;
+    }
+
+    return __distance;
+  }
+
+  template <range _Rp>
+  [[nodiscard]] constexpr range_difference_t<_Rp> operator()(_Rp&& __r) const {
+    if constexpr (sized_range<_Rp>) {
+      return static_cast<range_difference_t<_Rp> >(ranges::size(__r));
+    } else {
+      return (*this)(ranges::begin(__r), ranges::end(__r));
+    }
+  }
+};
+
+inline constexpr auto distance = __distance_fn(__function_like::__value);
+} // namespace ranges
+
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ITERATOR_DISTANCE_H

libcxx/include/iterator

 
 */
 
 #include <__config>
 #include <__debug>
 #include <__functional_base>
 #include <__iterator/advance.h>
 #include <__iterator/concepts.h>
+#include <__iterator/distance.h>
 #include <__iterator/incrementable_traits.h>
 #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>

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/distance.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
 
-// std::forward_iterator;
+// std::ranges::distance
 
 #include <iterator>
 
-#include <concepts>
+#include <array>
+#include <cassert>
+#include <ranges>
+#include <utility>
 
 #include "test_iterators.h"
+#include "test_range.h"
+#include "test_standard_function.h"
 
-int main(int, char**) { return 0; }
+static_assert(is_function_like<decltype(std::ranges::distance)>());
+
+constexpr auto range = std::array{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+using iterator = decltype(range)::const_iterator;
+
+template <class T>
+constexpr bool operator==(external_stride_counting_iterator<T> const& x, sentinel_wrapper<iterator> const& y) {
+  return x.base() == y;
+}
+
+template <template <class...> class I>
+requires requires {
+  typename I<iterator>;
+}
+constexpr bool operator==(I<iterator> const& x, sentinel_wrapper<iterator> const& y) { return x.base() == y; }
+
+namespace iterator_sentinel {
+template <std::input_or_output_iterator I>
+constexpr void check_iterator_sentinel() {
+  assert(std::ranges::distance(I(range.begin()), sentinel_wrapper(range.begin() + 5)) == 5);
+  assert(std::ranges::distance(I(range.begin()), sentinel_wrapper(range.begin())) == 0);
+
+  auto counter = std::ptrdiff_t(0);
+  assert(std::ranges::distance(external_stride_counting_iterator(I(range.begin()), counter),
+                               sentinel_wrapper(range.end())) == 10);
+  assert(counter == 10);
+}
+
+template <std::input_or_output_iterator I>
+constexpr void check_iterator_sized_sentinel() {
+  assert(std::ranges::distance(I(range.begin()), sized_sentinel_wrapper(I(range.end()))) == 10);
+  assert(std::ranges::distance(I(range.begin()), sized_sentinel_wrapper(I(range.begin()))) == 0);
+
+  auto counter = std::ptrdiff_t(0);
+  assert((std::ranges::distance(
+              external_stride_counting_iterator(I(range.begin()), counter),
+              sized_sentinel_wrapper(external_stride_counting_iterator(I(range.begin() + 5), counter))) == 5));
+  assert(counter == 0);
+
+  counter = 0;
+  assert(std::ranges::distance(external_stride_counting_iterator(I(range.begin() + 2), counter),
+                               external_stride_counting_iterator(I(range.begin()), counter)) == -2);
+  assert(counter == 0);
+}
+
+constexpr bool test() {
+  check_iterator_sentinel<cpp17_input_iterator<iterator> >();
+  check_iterator_sentinel<cpp20_input_iterator<iterator> >();
+  check_iterator_sentinel<forward_iterator<iterator> >();
+  check_iterator_sentinel<bidirectional_iterator<iterator> >();
+  check_iterator_sentinel<random_access_iterator<iterator> >();
+  check_iterator_sentinel<contiguous_iterator<iterator> >();
+
+  check_iterator_sized_sentinel<random_access_iterator<iterator> >();
+  check_iterator_sized_sentinel<contiguous_iterator<iterator> >();
+  return true;
+}
+} // namespace iterator_sentinel
+
+namespace range_based {
+template <std::input_or_output_iterator I>
+class external_stride_counting_range {
+public:
+  constexpr external_stride_counting_range(I first, iterator last) : first_(std::move(first), counter_), last_(last) {}
+
+  [[nodiscard]] constexpr external_stride_counting_iterator<I> begin() {
+    if constexpr (std::copy_constructible<I>)
+      return first_;
+    else
+      return std::move(first_);
+  }
+
+  [[nodiscard]] constexpr external_stride_counting_iterator<I> begin() const { return first_; }
+
+  [[nodiscard]] constexpr sentinel_wrapper<iterator> end() const { return last_; }
+
+  [[nodiscard]] constexpr std::ptrdiff_t counter() const { return counter_; }
+  constexpr void reset() { counter_ = 0; }
+
+private:
+  std::ptrdiff_t counter_ = 0;
+  external_stride_counting_iterator<I> first_;
+  sentinel_wrapper<iterator> last_;
+};
+
+template <std::input_or_output_iterator I>
+constexpr void check_range_case() {
+  auto r = external_stride_counting_range<I>(I(range.begin()), range.end());
+  assert(std::ranges::distance(r) == 10);
+  assert(r.counter() == 10);
+
+  r.reset();
+  assert(std::ranges::distance(std::as_const(r)) == 10);
+  assert(r.counter() == 10);
+
+  r.reset();
+  assert(std::ranges::distance(std::move(r)) == 10); // use after move okay
+  assert(r.counter() == 10);
+}
+
+template <std::input_or_output_iterator I>
+class sized_range {
+public:
+  constexpr sized_range(std::size_t const size) : size_(size) {}
+
+  external_stride_counting_iterator<I> begin();
+  external_stride_counting_iterator<I> begin() const;
+  sentinel_wrapper<iterator> end() const;
+
+  [[nodiscard]] constexpr std::size_t size() const { return size_; }
+
+private:
+  std::size_t size_ = 0;
+};
+
+template <std::input_or_output_iterator I>
+constexpr void check_sized_range_case() {
+  auto r = sized_range<I>(42);
+  assert(std::ranges::distance(r) == 42);
+  assert(std::ranges::distance(std::as_const(r)) == 42);
+  assert(std::ranges::distance(std::move(r)) == 42);
+}
+
+constexpr bool test() {
+  check_range_case<cpp17_input_iterator<iterator> >();
+  // cpp20_input_iterator special cased below
+  check_range_case<forward_iterator<iterator> >();
+  check_range_case<bidirectional_iterator<iterator> >();
+  check_range_case<random_access_iterator<iterator> >();
+  check_range_case<contiguous_iterator<iterator> >();
+  check_range_case<output_iterator<iterator> >();
+
+  check_sized_range_case<cpp17_input_iterator<iterator> >();
+  check_sized_range_case<cpp20_input_iterator<iterator> >();
+  check_sized_range_case<forward_iterator<iterator> >();
+  check_sized_range_case<bidirectional_iterator<iterator> >();
+  check_sized_range_case<random_access_iterator<iterator> >();
+  check_sized_range_case<contiguous_iterator<iterator> >();
+  check_sized_range_case<output_iterator<iterator> >();
+
+  {
+    auto r = external_stride_counting_range<cpp20_input_iterator<iterator> >(cpp20_input_iterator(range.begin()),
+                                                                             range.end());
+    assert(std::ranges::distance(r) == 10);
+    assert(r.counter() == 10);
+
+    r.reset();
+    assert(std::ranges::distance(std::move(r)) == 10); // use after move okay
+    assert(r.counter() == 10);
+  }
+  return true;
+}
+} // namespace range_based
+
+int main(int, char**) {
+  static_assert(iterator_sentinel::test());
+  iterator_sentinel::test();
+
+  static_assert(range_based::test());
+  range_based::test();
+  return 0;
+}

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/distance.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::distance
+
+#include <iterator>
+
+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;
+};
+
+struct some_range {
+  int* begin() const;
+  int* end() const;
+};
+} // 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 i;
+  distance(i, i); // expected-error {{use of undeclared identifier 'distance'}}
+
+  std::ranges::some_range r;
+  distance(r); // expected-error {{use of undeclared identifier 'distance'}}
+}
+
+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 distance(forward_iterator<I>, forward_iterator<I>) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class>
+struct range {
+  int* begin() const;
+  int* end() const;
+};
+
+template <class R>
+void distance(range<R>) {
+  static_assert(std::same_as<R, R*>);
+}
+} // 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*> i;
+  test::range<int> r;
+
+  using std::ranges::distance;
+
+  distance(i, i); // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}}
+  distance(r);    // expected-warning {{ignoring return value of function declared with 'nodiscard' attribute}}
+}
+
+void correct_interface() {
+  int i = 0;
+  (void)std::ranges::distance(1, nullptr); // expected-error {{no matching function for call}}
+  (void)std::ranges::distance(&i, 1);      // expected-error {{no matching function for call}}
+  (void)std::ranges::distance(i);          // expected-error {{no matching function for call}}
+}

libcxx/test/support/test_iterators.h

public:
   }
 
 private:
   I base_;
   difference_type stride_count_ = 0;
   difference_type stride_displacement_ = 0;
 };
 
+// std::ranges::distance doesn't give back an iterator, so we need to ensure the counter is external
+// to our iterator for inspection.
+template <std::input_or_output_iterator I>
+class external_stride_counting_iterator {
+public:
+  using value_type = typename iter_value_or_void<I>::type;
+  using difference_type = std::iter_difference_t<I>;
+  using iterator_concept = iterator_concept_t<I>;
+
+  external_stride_counting_iterator() = default;
+
+  constexpr explicit external_stride_counting_iterator(I current, difference_type& counter) : base_(std::move(current)), counter_(&counter) {}
+
+  [[nodiscard]] constexpr I const& base() const& requires std::copyable<I> { return base_; }
+
+  [[nodiscard]] constexpr I base() && { return std::move(base_); }
+
+  [[nodiscard]] constexpr decltype(auto) operator*() const { return *base_; }
+
+  [[nodiscard]] constexpr decltype(auto) operator[](difference_type const n) const { return base_[n]; }
+
+  constexpr external_stride_counting_iterator& operator++()
+  {
+    ++base_;
+    ++*counter_;
+    return *this;
+  }
+
+  constexpr void operator++(int) { ++*this; }
+
+  constexpr external_stride_counting_iterator operator++(int)
+  requires std::forward_iterator<I>
+  {
+    auto temp = *this;
+    ++*this;
+    return temp;
+  }
+
+  constexpr external_stride_counting_iterator& operator--()
+  requires std::bidirectional_iterator<I>
+  {
+    --base_;
+    ++*counter_;
+    return *this;
+  }
+
+  [[nodiscard]] constexpr external_stride_counting_iterator operator--(int)
+  requires std::bidirectional_iterator<I>
+  {
+    auto temp = *this;
+    --*this;
+    return temp;
+  }
+
+  constexpr external_stride_counting_iterator& operator+=(difference_type const n)
+  requires std::random_access_iterator<I>
+  {
+    base_ += n;
+    ++*counter_;
+    return *this;
+  }
+
+  constexpr external_stride_counting_iterator& operator-=(difference_type const n)
+  requires std::random_access_iterator<I>
+  {
+    base_ -= n;
+    ++*counter_;
+    return *this;
+  }
+
+  [[nodiscard]] constexpr friend external_stride_counting_iterator operator+(external_stride_counting_iterator i, difference_type const n)
+  requires std::random_access_iterator<I>
+  {
+    return i += n;
+  }
+
+  [[nodiscard]] constexpr friend external_stride_counting_iterator operator+(difference_type const n, external_stride_counting_iterator i)
+  requires std::random_access_iterator<I>
+  {
+    return i += n;
+  }
+
+  [[nodiscard]] constexpr friend external_stride_counting_iterator operator-(external_stride_counting_iterator i, difference_type const n)
+  requires std::random_access_iterator<I>
+  {
+    return i -= n;
+  }
+
+  [[nodiscard]] constexpr friend difference_type operator-(external_stride_counting_iterator const& x, external_stride_counting_iterator const& y)
+  requires std::sized_sentinel_for<I, I>
+  {
+    return x.base() - y.base();
+  }
+
+  constexpr bool operator==(external_stride_counting_iterator const& other) const
+  requires std::sentinel_for<I, I>
+  {
+    return base_ == other.base_;
+  }
+
+  template <std::sentinel_for<I> S>
+  constexpr bool operator==(S const last) const
+  {
+      return base_ == last;
+  }
+
+  constexpr friend bool operator<(external_stride_counting_iterator const& x, external_stride_counting_iterator const& y)
+  requires std::random_access_iterator<I>
+  {
+    return x.base_ < y.base_;
+  }
+
+  constexpr friend bool operator>(external_stride_counting_iterator const& x, external_stride_counting_iterator const& y)
+  requires std::random_access_iterator<I>
+  {
+    return y < x;
+  }
+
+  constexpr friend bool operator<=(external_stride_counting_iterator const& x, external_stride_counting_iterator const& y)
+  requires std::random_access_iterator<I>
+  {
+    return !(y < x);
+  }
+
+  constexpr friend bool operator>=(external_stride_counting_iterator const& x, external_stride_counting_iterator const& y)
+  requires std::random_access_iterator<I>
+  {
+    return !(x < y);
+  }
+
+private:
+  I base_ = I();
+  difference_type* counter_ = nullptr;
+};
+
 template <std::input_or_output_iterator I>
 class sentinel_wrapper {
 public:
   sentinel_wrapper() = default;
   constexpr explicit sentinel_wrapper(I base) : base_(std::move(base)) {}
 
+  constexpr bool operator==(I const& other) const requires std::sentinel_for<I, I> {
+    return base_ == other;
+  }
+
+private:
+  I base_ = I();
+};
+
+template <std::input_or_output_iterator I>
+class sized_sentinel_wrapper {
+public:
+  sized_sentinel_wrapper() = default;
+  constexpr explicit sized_sentinel_wrapper(I base) : base_(std::move(base)) {}
+
   constexpr bool operator==(I const& other) const requires std::equality_comparable<I> {
     return base_ == other;
   }
 
+  [[nodiscard]] friend constexpr std::iter_difference_t<I> operator-(sized_sentinel_wrapper const& s, I const& i)
+  {
+    return s.base_ - i;
+  }
+
+  [[nodiscard]] friend constexpr std::iter_difference_t<I> operator-(I const& i, sized_sentinel_wrapper const& s)
+  {
+    return i - s.base_;
+  }
+
 private:
   I base_ = I();
 };
 
 // clang-format on
 
 #endif // TEST_STD_VER > 17 && defined(__cpp_lib_concepts)
 
 #undef DELETE_FUNCTION
 
 #endif // ITERATORS_H