[libc++] [ranges] Implement std::ranges::distance

[• Quuxplusone]

Summary

This includes an experimental workaround for
LWG3664 "LWG3392 broke std::ranges::distance(a, a+3)",
but the workaround may be incomplete, I'm not sure.
This should be re-audited when LWG3664 is actually adopted,
to see if we need to change anything about our implementation.

See also https://github.com/microsoft/STL/pull/2500

The current draft standard says

template<input_or_output_iterator I, sentinel_for<I> S>
  requires (!sized_sentinel_for<S, I>)
    constexpr iter_difference_t<I> distance(I first, S last);

template<input_or_output_iterator I, sized_sentinel_for<I> S>
  constexpr iter_difference_t<I> distance(const I& first, const S& last);

My P/R is

template<class I, sentinel_for<I> S>
  requires (!sized_sentinel_for<S, I>)
    constexpr iter_difference_t<I> distance(I first, S last);

template<class I, sized_sentinel_for<decay_t<I>> S>
  constexpr iter_difference_t<I> distance(const I& first, S last);

Microsoft STL is also planning to adopt the P/R: https://github.com/microsoft/STL/pull/2500

However, @tcanens pointed out a problem with the P/R: you can have an evil sentinel that is a sized_sentinel_for<int*> but doesn't support last - first when first is not literally an int*.

[philnik]

LGTM % nits

libcxx/docs/Status/RangesPaper.csv

74

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

34

Since you're testing 3/4 possible combinations also test the fourth? ditto below.

113–114

Please move the static_asserts together.

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

53

Why not std::move?

[• Quuxplusone]

Wow, niebloid.compile.pass.cpp caught a real LWG-worthy bug! std::ranges::distance(a, a+10) didn't compile, and I hadn't thought to test that case directly in my new tests. Now I'm testing it (and have implemented a workaround while we wait for the LWG issue to be recorded).

[• Quuxplusone]

s/Complete/|Complete|/

[• Quuxplusone]

Try to fix the Apple build's CI failure: https://buildkite.com/llvm-project/libcxx-ci/builds/8074
by adding UNSUPPORTED: libcpp-has-no-incomplete-ranges to the test that uses subrange.

[Mordante]

Since the current Standard seems to be broken I agree with implementing your proposed LWG-issue.
I prefer to wait with landing until you have a number so it can be used in the issue table and commit message.

libcxx/docs/Status/Cxx2bIssues.csv

140

Can you add your new issue here once you have a number?

libcxx/include/__iterator/distance.h

63

input_or_output_iterator doesn't match the description. Should this be input_or_output_iterator if just class _Ip?

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

18

Please update this to match the implementation.

82

Likewise two lines above.

[• Quuxplusone]

libcxx/docs/Status/RangesPaper.csv

74

Meh, we only have one row here, and he did 3/4 of them.

libcxx/include/__iterator/distance.h

63

Oops, good catch. This should be class _Ip. (The constraint is superfluous, because it's already implied by sentinel_for<_Ip> _Sp right afterward. Therefore, we remove the superfluous constraint, to save the environment.)

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

113–114

These four tests are always in the same order: lvalue-lvalue, lvalue-rvalue, rvalue-lvalue, rvalue-rvalue.
Although, in this case, I did throw in line 115, which broke up the pattern a bit. I should just remove line 115.

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

53

I was waffling between using static_cast for all of the cvref-qualifications, or using the more "normal-looking" versions; e.g. line 51 could have said static_cast<R&>(r) too. I think I'll change line 39 to avoid std::move, which might help avoid the question. :)

[• Quuxplusone]

Review comments. CI should still be green.
Still waiting on an LWG issue number; will add it to libcxx/docs/ when I get it.

[Mordante]

LGTM.

[• Quuxplusone]

Improve the LWG3664 evil test case a bit more.

[• Quuxplusone]

s/remove_reference/__uncvref/, and regression-test.

[var-const]

libcxx/docs/Status/RangesPaper.csv

74

You can do Christopher Di Bella and Arthur O'Dwyer (see line 100).

[ldionne]

A few comments, nothing big. Overall LGTM, thanks.

This supersedes D102789 (mentioning so it gets cross-referenced).

libcxx/docs/Status/Cxx2bIssues.csv

101

Can you add an entry for not-yet-voted LWG3664 and mark it as implemented?

However, @tcanens pointed out a problem with the P/R: you can have an evil sentinel that is a sized_sentinel_for<int*> but doesn't support last - first when first is not literally an int*.

So do I understand correctly that the resolution of LWG3664 might change? I just want to be careful to avoid implementing stale resolutions.

libcxx/docs/Status/RangesPaper.csv

74

I've used various in the past too. Just to clarify, the goal of these is not attribution, it's only to keep track of who's doing what. In fact, this page will be removed as soon as all of the original "One Ranges Proposal" is fully implemented, and then we'll fold that into a simple green check-mark in front of P0896.

74

libcxx/include/__iterator/distance.h

81

This is to handle the array case, right? I assume the answer is yes, but do you have a test case for this if constexpr?

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

2

We seem to be missing tests that count the number of operations we're doing. Can you add some using stride_counting_iterator?

[• Quuxplusone]

libcxx/include/__iterator/distance.h

81

The current (but problematic) P/R for LWG3664 fixes the array-vs-pointer case. This if constexpr is specifically for the array-vs-EvilSentinel case, and yes, that's tested.

A more helpful way to look at is probably: line 81 is actually the happy path, that works for almost all iterator types and for all array types... but line 81 doesn't work for move-only iterator types such as cpp20_input_iterator. For those move-only types, we must use line 78 instead.

This is my current-informally-suggested P/R for LWG3664. The P/R will change at some point, because we need ranges::distance(a, a) to work — it's just unacceptable for it not to work. Therefore, I'm willing to add a line for LWG3664 but wouldn't mark it "Complete", which also means maybe we don't need to add a line at all, and can just wait for LWG3664 to be adopted before we revisit and audit it. WDYT?

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

2

Sure, will do, although you probably know I'm not a fan of stride_counting_iterator in its current state.

[ldionne]

libcxx/include/__iterator/distance.h

81

Hmm, tricky. Let's not mention LWG3664 at all then, and we can audit the state of our implementation when it is actually filed.

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

2

Yeah, me neither, but it still provides something of value for test coverage.

[ldionne]

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

7

We also seem to be missing tests for the return type of ranges::distance, unless I missed them.

[• Quuxplusone]

Add two stride-counting tests. (I made my own type rather than use stride_counting_iterator, because (1) it seemed easier, and (2) I need something that holds a pointer *inc_ rather than incrementing a count stored inside the iterator itself. Seems like stride_counting_iterator was written specifically for ranges::advance and nothing else, because it assumes the iterator will never be copied.)
Add ASSERT_SAME_TYPE tests.

[• Quuxplusone]

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

18

I guess it's still unclear what we should put here. What's here right now is the P/R for LWG3664, but we know the P/R is buggy — what I actually implemented uses I&& in place of const I&. I can fix that before landing, if we decide it needs fixing. No matter what, the person who fixes LWG3664 should re-audit this comment anyway.

Alternative ideas: use the P/R as written (i.e. what's here now); or, use the working draft's wording (i.e., remove the decay_t and replace S with const S&).

[Mordante]

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

18

I think it would be better to use I&& since that's what you've implemented. Maybe add a comment this wording needs updating for LWG3664.

[• Quuxplusone]

s/const I&/I&&/ in the test comment. Leave a TODO for when LWG3664 is actually resolved by LWG.
@ldionne I believe all your comments have been addressed; let me know if that's not the case.

[ldionne]

LGTM. We could/should look into simplifying some of the existing tests we have that use stride_counting_iterator. It occurs to me that those existing tests probably don't need to check stride_counting_iterator<various archetypes>, and a simple check like what you do here provides basically the same coverage.

libcxx/docs/Status/Cxx2bIssues.csv

 `3548 <https://wg21.link/LWG3548>`__,"``shared_ptr`` construction from ``unique_ptr`` should move (not copy) the deleter","June 2021","",""
 `3549 <https://wg21.link/LWG3549>`__,"``view_interface`` is overspecified to derive from ``view_base``","June 2021","|Complete|","14.0","|ranges|"
 `3551 <https://wg21.link/LWG3551>`__,"``borrowed_{iterator,subrange}_t`` are overspecified","June 2021","|Nothing To Do|","","|ranges|"
 `3552 <https://wg21.link/LWG3552>`__,"Parallel specialized memory algorithms should require forward iterators","June 2021","",""
 `3553 <https://wg21.link/LWG3553>`__,"Useless constraint in ``split_view::outer-iterator::value_type::begin()``","June 2021","","","|ranges|"
 `3555 <https://wg21.link/LWG3555>`__,"``{transform,elements}_view::iterator::iterator_concept`` should consider const-qualification of the underlying range","June 2021","","","|ranges|"
 "","","","",""
 `2191 <https://wg21.link/LWG2191>`__,"Incorrect specification of ``match_results(match_results&&)``","October 2021","|Nothing To Do|",""
 `2381 <https://wg21.link/LWG2381>`__,"Inconsistency in parsing floating point numbers","October 2021","",""
 `2762 <https://wg21.link/LWG2762>`__,"``unique_ptr operator*()`` should be ``noexcept``","October 2021","",""
 `3121 <https://wg21.link/LWG3121>`__,"``tuple`` constructor constraints for ``UTypes&&...`` overloads","October 2021","",""
 `3123 <https://wg21.link/LWG3123>`__,"``duration`` constructor from representation shouldn't be effectively non-throwing","October 2021","","","|chrono|"
 `3146 <https://wg21.link/LWG3146>`__,"Excessive unwrapping in ``std::ref/cref``","October 2021","|Complete|","14.0"
 `3152 <https://wg21.link/LWG3152>`__,"``common_type`` and ``common_reference`` have flaws in common","October 2021","",""
 `3293 <https://wg21.link/LWG3293>`__,"``move_iterator operator+()`` has incorrect constraints","October 2021","","","|ranges|"
 `3361 <https://wg21.link/LWG3361>`__,"``safe_range<SomeRange&>`` case","October 2021","|Nothing To Do|","","|ranges|"
-`3392 <https://wg21.link/LWG3392>`__,"``ranges::distance()`` cannot be used on a move-only iterator with a sized sentinel","October 2021","","","|ranges|"
+`3392 <https://wg21.link/LWG3392>`__,"``ranges::distance()`` cannot be used on a move-only iterator with a sized sentinel","October 2021","|Complete|","14.0","|ranges|"
 `3407 <https://wg21.link/LWG3407>`__,"Some problems with the wording changes of P1739R4","October 2021","","","|ranges|"
 `3422 <https://wg21.link/LWG3422>`__,"Issues of ``seed_seq``'s constructors","October 2021","|Complete|","14.0"
 `3470 <https://wg21.link/LWG3470>`__,"``convertible-to-non-slicing`` seems to reject valid case","October 2021","|Complete|","14.0","|ranges|"
 `3480 <https://wg21.link/LWG3480>`__,"``directory_iterator`` and ``recursive_directory_iterator`` are not C++20 ranges","October 2021","|Complete|","14.0","|ranges|"
 `3498 <https://wg21.link/LWG3498>`__,"Inconsistent ``noexcept``-specifiers for ``basic_syncbuf``","October 2021","",""
 `3535 <https://wg21.link/LWG3535>`__,"``join_view::iterator::iterator_category`` and ``::iterator_concept`` lie","October 2021","","","|ranges|"
 `3554 <https://wg21.link/LWG3554>`__,"``chrono::parse`` needs ``const charT*`` and ``basic_string_view<charT>`` overloads","October 2021","","","|chrono|"
 `3557 <https://wg21.link/LWG3557>`__,"The ``static_cast`` expression in ``convertible_to`` has the wrong operand","October 2021","|Complete|","14.0"

 `3585 <https://wg21.link/LWG3585>`__,"``variant`` converting assignment with immovable alternative","October 2021","",""
 `3589 <https://wg21.link/LWG3589>`__,"The ``const`` lvalue reference overload of ``get`` for ``subrange`` does not constrain ``I`` to be ``copyable`` when ``N == 0``","October 2021","","","|ranges|"
 `3590 <https://wg21.link/LWG3590>`__,"``split_view::base() const &`` is overconstrained","October 2021","","","|ranges|"
 `3591 <https://wg21.link/LWG3591>`__,"``lazy_split_view<input_view>::inner-iterator::base() &&`` invalidates outer iterators","October 2021","","","|ranges|"
 `3592 <https://wg21.link/LWG3592>`__,"``lazy_split_view`` needs to check the simpleness of Pattern","October 2021","","","|ranges|"
 `3593 <https://wg21.link/LWG3593>`__,"Several iterators' ``base() const &`` and ``lazy_split_view::outer-iterator::value_type::end()`` missing ``noexcept``","October 2021","","","|ranges|"
 `3595 <https://wg21.link/LWG3595>`__,"Exposition-only classes proxy and postfix-proxy for ``common_iterator`` should be fully ``constexpr``","October 2021","|Complete|","14.0","|ranges|"
 "","","","",""
 `3645 <https://wg21.link/LWG3645>`__,"``resize_and_overwrite`` is overspecified to call its callback with lvalues", "Not voted in","|Complete|","14.0",""
 "","","","",""

libcxx/docs/Status/RangesPaper.csv

 `[common.alg.req] <https://wg21.link/common.alg.req>`_: pt. 3,`indirectly_comparable <https://llvm.org/D116268>`_,[projected],Nikolas Klauser,✅
 `[common.alg.req] <https://wg21.link/common.alg.req>`_: pt. 4,"| permutable
 | mergeable
 | sortable",[iterator.concepts],Unassigned,Not started
 `[std.iterator.tags] <https://wg21.link/std.iterator.tags>`_,,[iterator.traits],Unassigned,Not started
 `[range.iter.ops] <https://wg21.link/range.iter.ops>`_,"| `ranges::advance <https://llvm.org/D101922>`_
 | `ranges::distance <https://llvm.org/D102789>`_
 | `ranges::next <https://llvm.org/D102563>`_
-| `ranges::prev <https://llvm.org/D102564>`_",[iterator.concepts],Christopher Di Bella,In progress
+| `ranges::prev <https://llvm.org/D102564>`_",[iterator.concepts],Christopher Di Bella and Arthur O'Dwyer,✅
 `[predef.iterators] <https://wg21.link/predef.iterators>`_,Updates to predefined iterators.,"| [iterator.concepts]
 | [iterator.cust.swap]
 | [iterator.cust.move]",Unassigned,Not started
 `[move.sentinel] <https://wg21.link/move.sentinel>`_,,[predef.iterators],Unassigned,Not started
 `[common.iterator] <https://wg21.link/common.iterator>`_,`common_iterator <https://llvm.org/D103335>`_,"| [iterator.concepts]
 | [iterator.cust.swap]
 | [iterator.cust.move]",Zoe Carver,✅
 `[default.sentinel] <https://wg21.link/default.sentinel>`_,`std::default_sentinel_t <https://llvm.org/D103487>`_,No dependencies,Zoe Carver,✅

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 <__iterator/concepts.h>
+#include <__iterator/incrementable_traits.h>
 #include <__iterator/iterator_traits.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/size.h>
+#include <type_traits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _InputIter>

 template <class _InputIter>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 typename iterator_traits<_InputIter>::difference_type
 distance(_InputIter __first, _InputIter __last)
 {
     return _VSTD::__distance(__first, __last, typename iterator_traits<_InputIter>::iterator_category());
 }
 
+#if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS)
+
+// [range.iter.op.distance]
+
+namespace ranges {
+namespace __distance {
+
+struct __fn {
+  template<class _Ip, sentinel_for<_Ip> _Sp>
+    requires (!sized_sentinel_for<_Sp, _Ip>)
+  _LIBCPP_HIDE_FROM_ABI
+  constexpr iter_difference_t<_Ip> operator()(_Ip __first, _Sp __last) const {
+    iter_difference_t<_Ip> __n = 0;
+    while (__first != __last) {
+      ++__first;
+      ++__n;
+    }
+    return __n;
+  }
+
+  template<class _Ip, sized_sentinel_for<decay_t<_Ip>> _Sp>
+  _LIBCPP_HIDE_FROM_ABI
+  constexpr iter_difference_t<_Ip> operator()(_Ip&& __first, _Sp __last) const {
+    if constexpr (sized_sentinel_for<_Sp, __uncvref_t<_Ip>>) {
+      return __last - __first;
+    } else {
+      return __last - decay_t<_Ip>(__first);
+    }
+  }
+
+  template<range _Rp>
+  _LIBCPP_HIDE_FROM_ABI
+  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 operator()(ranges::begin(__r), ranges::end(__r));
+    }
+  }
+};
+
+} // namespace __distance
+
+inline namespace __cpo {
+  inline constexpr auto distance = __distance::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_CONCEPTS)
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_DISTANCE_H

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/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
+
+// template<class I, sentinel_for<I> S>
+//   requires (!sized_sentinel_for<S, I>)
+//     constexpr iter_difference_t<I> ranges::distance(I first, S last);
+//
+// template<class I, sized_sentinel_for<decay_t<I>> S>
+//   constexpr iter_difference_t<I> ranges::distance(I&& first, S last); // TODO: update when LWG3664 is resolved
+
+#include <iterator>
+#include <cassert>
+
+#include "test_iterators.h"
+#include "test_macros.h"
+
+template<class It, class Sent>
+constexpr void test_unsized() {
+  static_assert(std::sentinel_for<Sent, It> && !std::sized_sentinel_for<Sent, It>);
+  int a[3] = {1,2,3};
+  {
+    It first = It(a);
+    auto last = Sent(It(a));
+    assert(std::ranges::distance(first, last) == 0);
+    assert(std::ranges::distance(It(a), last) == 0);
+    assert(std::ranges::distance(first, Sent(It(a))) == 0);
+    assert(std::ranges::distance(It(a), Sent(It(a))) == 0);
+    ASSERT_SAME_TYPE(decltype(std::ranges::distance(It(a), Sent(It(a)))), std::iter_difference_t<It>);
+  }
+  {
+    It first = It(a);
+    auto last = Sent(It(a + 3));
+    assert(std::ranges::distance(first, last) == 3);
+
+    // Test all const/ref-qualifications of both operands.
+    assert(std::ranges::distance(static_cast<It&>(first), static_cast<Sent&>(last)) == 3);
+    assert(std::ranges::distance(static_cast<It&>(first), static_cast<Sent&&>(last)) == 3);
+    assert(std::ranges::distance(static_cast<It&>(first), static_cast<const Sent&>(last)) == 3);
+    assert(std::ranges::distance(static_cast<It&>(first), static_cast<const Sent&&>(last)) == 3);
+    assert(std::ranges::distance(static_cast<It&&>(first), static_cast<Sent&>(last)) == 3);
+    assert(std::ranges::distance(static_cast<It&&>(first), static_cast<Sent&&>(last)) == 3);
+    assert(std::ranges::distance(static_cast<It&&>(first), static_cast<const Sent&>(last)) == 3);
+    assert(std::ranges::distance(static_cast<It&&>(first), static_cast<const Sent&&>(last)) == 3);
+    assert(std::ranges::distance(static_cast<const It&>(first), static_cast<Sent&>(last)) == 3);
+    assert(std::ranges::distance(static_cast<const It&>(first), static_cast<Sent&&>(last)) == 3);
+    assert(std::ranges::distance(static_cast<const It&>(first), static_cast<const Sent&>(last)) == 3);
+    assert(std::ranges::distance(static_cast<const It&>(first), static_cast<const Sent&&>(last)) == 3);
+    assert(std::ranges::distance(static_cast<const It&&>(first), static_cast<Sent&>(last)) == 3);
+    assert(std::ranges::distance(static_cast<const It&&>(first), static_cast<Sent&&>(last)) == 3);
+    assert(std::ranges::distance(static_cast<const It&&>(first), static_cast<const Sent&>(last)) == 3);
+    assert(std::ranges::distance(static_cast<const It&&>(first), static_cast<const Sent&&>(last)) == 3);
+  }
+}
+
+template<class It, class Sent>
+constexpr void test_sized() {
+  static_assert(std::sized_sentinel_for<Sent, It>);
+  int a[] = {1,2,3};
+  {
+    It first = It(a + 3);
+    auto last = Sent(It(a));
+    assert(std::ranges::distance(first, last) == -3);
+
+    // Test all const/ref-qualifications of both operands.
+    assert(std::ranges::distance(static_cast<It&>(first), static_cast<Sent&>(last)) == -3);
+    assert(std::ranges::distance(static_cast<It&>(first), static_cast<Sent&&>(last)) == -3);
+    assert(std::ranges::distance(static_cast<It&>(first), static_cast<const Sent&>(last)) == -3);
+    assert(std::ranges::distance(static_cast<It&>(first), static_cast<const Sent&&>(last)) == -3);
+    assert(std::ranges::distance(static_cast<It&&>(first), static_cast<Sent&>(last)) == -3);
+    assert(std::ranges::distance(static_cast<It&&>(first), static_cast<Sent&&>(last)) == -3);
+    assert(std::ranges::distance(static_cast<It&&>(first), static_cast<const Sent&>(last)) == -3);
+    assert(std::ranges::distance(static_cast<It&&>(first), static_cast<const Sent&&>(last)) == -3);
+    assert(std::ranges::distance(static_cast<const It&>(first), static_cast<Sent&>(last)) == -3);
+    assert(std::ranges::distance(static_cast<const It&>(first), static_cast<Sent&&>(last)) == -3);
+    assert(std::ranges::distance(static_cast<const It&>(first), static_cast<const Sent&>(last)) == -3);
+    assert(std::ranges::distance(static_cast<const It&>(first), static_cast<const Sent&&>(last)) == -3);
+    assert(std::ranges::distance(static_cast<const It&&>(first), static_cast<Sent&>(last)) == -3);
+    assert(std::ranges::distance(static_cast<const It&&>(first), static_cast<Sent&&>(last)) == -3);
+    assert(std::ranges::distance(static_cast<const It&&>(first), static_cast<const Sent&>(last)) == -3);
+    assert(std::ranges::distance(static_cast<const It&&>(first), static_cast<const Sent&&>(last)) == -3);
+  }
+  {
+    It first = It(a);
+    auto last = Sent(It(a));
+    assert(std::ranges::distance(first, last) == 0);
+    assert(std::ranges::distance(It(a), last) == 0);
+    assert(std::ranges::distance(first, Sent(It(a))) == 0);
+    assert(std::ranges::distance(It(a), Sent(It(a))) == 0);
+    ASSERT_SAME_TYPE(decltype(std::ranges::distance(It(a), Sent(It(a)))), std::iter_difference_t<It>);
+  }
+  {
+    It first = It(a);
+    auto last = Sent(It(a + 3));
+    assert(std::ranges::distance(first, last) == 3);
+    assert(std::ranges::distance(It(a), last) == 3);
+    assert(std::ranges::distance(first, Sent(It(a + 3))) == 3);
+    assert(std::ranges::distance(It(a), Sent(It(a + 3))) == 3);
+  }
+}
+
+struct StrideCounter {
+  int *it_;
+  int *inc_;
+  using value_type = int;
+  using difference_type = int;
+  explicit StrideCounter();
+  constexpr explicit StrideCounter(int *it, int *inc) : it_(it), inc_(inc) {}
+  constexpr auto& operator++() { ++it_; *inc_ += 1; return *this; }
+  StrideCounter operator++(int);
+  int& operator*() const;
+  bool operator==(StrideCounter) const;
+};
+static_assert(std::forward_iterator<StrideCounter>);
+static_assert(!std::sized_sentinel_for<StrideCounter, StrideCounter>);
+
+struct SizedStrideCounter {
+  int *it_;
+  int *minus_;
+  using value_type = int;
+  explicit SizedStrideCounter();
+  constexpr explicit SizedStrideCounter(int *it, int *minus) : it_(it), minus_(minus) {}
+  SizedStrideCounter& operator++();
+  SizedStrideCounter operator++(int);
+  int& operator*() const;
+  bool operator==(SizedStrideCounter) const;
+  constexpr int operator-(SizedStrideCounter rhs) const { *minus_ += 1; return it_ - rhs.it_; }
+};
+static_assert(std::forward_iterator<SizedStrideCounter>);
+static_assert(std::sized_sentinel_for<SizedStrideCounter, SizedStrideCounter>);
+
+constexpr void test_stride_counting() {
+  {
+    int a[] = {1, 2, 3};
+    int inc = 0;
+    StrideCounter first(a, &inc);
+    StrideCounter last(a+3, nullptr);
+    std::same_as<int> auto result = std::ranges::distance(first, last);
+    assert(result == 3);
+    assert(inc == 3);
+  }
+  {
+    int a[] = {1, 2, 3};
+    int minus = 0;
+    SizedStrideCounter first(a, &minus);
+    SizedStrideCounter last(a+3, nullptr);
+    std::same_as<int> auto result = std::ranges::distance(first, last);
+    assert(result == 3);
+    assert(minus == 1);
+  }
+}
+
+constexpr bool test() {
+  {
+    int a[] = {1, 2, 3};
+    assert(std::ranges::distance(a, a + 3) == 3);
+    assert(std::ranges::distance(a, a) == 0);
+    assert(std::ranges::distance(a + 3, a) == -3);
+  }
+
+  test_unsized<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
+  test_unsized<output_iterator<int*>, sentinel_wrapper<output_iterator<int*>>>();
+  test_unsized<forward_iterator<int*>, sentinel_wrapper<forward_iterator<int*>>>();
+  test_unsized<bidirectional_iterator<int*>, sentinel_wrapper<bidirectional_iterator<int*>>>();
+  test_unsized<random_access_iterator<int*>, sentinel_wrapper<random_access_iterator<int*>>>();
+  test_unsized<contiguous_iterator<int*>, sentinel_wrapper<contiguous_iterator<int*>>>();
+  test_unsized<int*, sentinel_wrapper<int*>>();
+  test_unsized<const int*, sentinel_wrapper<const int*>>();
+  test_unsized<forward_iterator<int*>, forward_iterator<int*>>();
+  test_unsized<bidirectional_iterator<int*>, bidirectional_iterator<int*>>();
+
+  test_sized<cpp17_input_iterator<int*>, sized_sentinel<cpp17_input_iterator<int*>>>();
+  test_sized<cpp20_input_iterator<int*>, sized_sentinel<cpp20_input_iterator<int*>>>();
+  test_sized<output_iterator<int*>, sized_sentinel<output_iterator<int*>>>();
+  test_sized<forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>();
+  test_sized<bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>();
+  test_sized<random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>();
+  test_sized<contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>();
+  test_sized<int*, sized_sentinel<int*>>();
+  test_sized<const int*, sized_sentinel<const int*>>();
+  test_sized<int*, int*>();
+  test_sized<int*, const int*>();
+  test_sized<random_access_iterator<int*>, random_access_iterator<int*>>();
+  test_sized<contiguous_iterator<int*>, contiguous_iterator<int*>>();
+
+  {
+    using It = cpp20_input_iterator<int*>;  // non-copyable, thus not a sentinel for itself
+    static_assert(!std::is_copy_constructible_v<It>);
+    static_assert(!std::sentinel_for<It, It>);
+    static_assert(!std::is_invocable_v<decltype(std::ranges::distance), It&, It&>);
+    static_assert(!std::is_invocable_v<decltype(std::ranges::distance), It&, It&&>);
+    static_assert(!std::is_invocable_v<decltype(std::ranges::distance), It&&, It&>);
+    static_assert(!std::is_invocable_v<decltype(std::ranges::distance), It&&, It&&>);
+  }
+  {
+    using It = cpp20_input_iterator<int*>;  // non-copyable
+    using Sent = sentinel_wrapper<It>;  // not a sized sentinel
+    static_assert(std::sentinel_for<Sent, It> && !std::sized_sentinel_for<Sent, It>);
+    int a[] = {1,2,3};
+    Sent last = Sent(It(a + 3));
+    static_assert(!std::is_invocable_v<decltype(std::ranges::distance), It&, Sent&>);
+    static_assert(!std::is_invocable_v<decltype(std::ranges::distance), It&, Sent&&>);
+    assert(std::ranges::distance(It(a), last) == 3);
+    assert(std::ranges::distance(It(a), Sent(It(a + 3))) == 3);
+  }
+  {
+    using It = cpp17_input_iterator<int*>;  // not a sentinel for itself
+    static_assert(!std::sentinel_for<It, It>);
+    static_assert(!std::is_invocable_v<decltype(std::ranges::distance), It&, It&>);
+    static_assert(!std::is_invocable_v<decltype(std::ranges::distance), It&, It&&>);
+    static_assert(!std::is_invocable_v<decltype(std::ranges::distance), It&&, It&>);
+    static_assert(!std::is_invocable_v<decltype(std::ranges::distance), It&&, It&&>);
+  }
+
+  // Calling it on a non-iterator or non-sentinel isn't allowed.
+  static_assert(!std::is_invocable_v<decltype(std::ranges::distance), int, int>);
+  static_assert(!std::is_invocable_v<decltype(std::ranges::distance), int*, int>);
+  static_assert(!std::is_invocable_v<decltype(std::ranges::distance), int, int*>);
+  static_assert(!std::is_invocable_v<decltype(std::ranges::distance), int*, char*>);
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/lwg3664.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
+
+// template<class I, sentinel_for<I> S>
+//   requires (!sized_sentinel_for<S, I>)
+//     constexpr iter_difference_t<I> ranges::distance(I first, S last);
+//
+// template<class I, sized_sentinel_for<decay_t<I>> S>
+//   constexpr iter_difference_t<I> ranges::distance(const I& first, S last);
+
+#include <iterator>
+#include <cassert>
+
+#include "test_iterators.h"
+
+template<class It>
+struct EvilSentinel {
+  It p_;
+  friend constexpr bool operator==(EvilSentinel s, It p) { return s.p_ == p; }
+  friend constexpr auto operator-(EvilSentinel s, It p) { return s.p_ - p; }
+  friend constexpr auto operator-(It p, EvilSentinel s) { return p - s.p_; }
+  friend constexpr void operator-(EvilSentinel s, int(&)[3]) = delete;
+  friend constexpr void operator-(EvilSentinel s, int(&&)[3]) = delete;
+  friend constexpr void operator-(EvilSentinel s, const int(&)[3]) = delete;
+  friend constexpr void operator-(EvilSentinel s, const int(&&)[3]) = delete;
+};
+static_assert( std::sized_sentinel_for<EvilSentinel<int*>, int*>);
+static_assert(!std::sized_sentinel_for<EvilSentinel<int*>, const int*>);
+static_assert( std::sized_sentinel_for<EvilSentinel<const int*>, int*>);
+static_assert( std::sized_sentinel_for<EvilSentinel<const int*>, const int*>);
+
+constexpr bool test() {
+  {
+    int a[] = {1, 2, 3};
+    assert(std::ranges::distance(a, a + 3) == 3);
+    assert(std::ranges::distance(a, a) == 0);
+    assert(std::ranges::distance(a + 3, a) == -3);
+  }
+  {
+    int a[] = {1, 2, 3};
+    assert(std::ranges::distance(a, EvilSentinel<int*>{a+3}) == 3);
+    assert(std::ranges::distance(a, EvilSentinel<int*>{a}) == 0);
+    assert(std::ranges::distance(a+3, EvilSentinel<int*>{a}) == -3);
+    assert(std::ranges::distance(std::move(a), EvilSentinel<int*>{a+3}) == 3);
+  }
+  {
+    const int a[] = {1, 2, 3};
+    assert(std::ranges::distance(a, EvilSentinel<const int*>{a+3}) == 3);
+    assert(std::ranges::distance(a, EvilSentinel<const int*>{a}) == 0);
+    assert(std::ranges::distance(a+3, EvilSentinel<const int*>{a}) == -3);
+    assert(std::ranges::distance(std::move(a), EvilSentinel<const int*>{a+3}) == 3);
+    static_assert(!std::is_invocable_v<decltype(std::ranges::distance), const int(&)[3], EvilSentinel<int*>>);
+    static_assert(!std::is_invocable_v<decltype(std::ranges::distance), const int(&&)[3], EvilSentinel<int*>>);
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.distance/range.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: libcpp-has-no-incomplete-ranges
+
+// template<range R>
+//   constexpr range_difference_t<R> ranges::distance(R&& r);
+
+#include <iterator>
+#include <cassert>
+#include <ranges>
+
+#include "test_iterators.h"
+#include "test_macros.h"
+
+template<class It, class Sent>
+constexpr void test_ordinary() {
+  struct R {
+    mutable int a[3] = {1, 2, 3};
+    constexpr It begin() const { return It(a); }
+    constexpr Sent end() const { return Sent(It(a + 3)); }
+  };
+  R r;
+  assert(std::ranges::distance(r) == 3);
+  assert(std::ranges::distance(static_cast<R&&>(r)) == 3);
+  assert(std::ranges::distance(static_cast<const R&>(r)) == 3);
+  assert(std::ranges::distance(static_cast<const R&&>(r)) == 3);
+  ASSERT_SAME_TYPE(decltype(std::ranges::distance(r)), std::ranges::range_difference_t<R>);
+}
+
+constexpr bool test() {
+  {
+    using R = int[3];
+    int a[] = {1, 2, 3};
+    assert(std::ranges::distance(static_cast<R&>(a)) == 3);
+    assert(std::ranges::distance(static_cast<R&&>(a)) == 3);
+    assert(std::ranges::distance(static_cast<const R&>(a)) == 3);
+    assert(std::ranges::distance(static_cast<const R&&>(a)) == 3);
+    ASSERT_SAME_TYPE(decltype(std::ranges::distance(a)), std::ptrdiff_t);
+    ASSERT_SAME_TYPE(decltype(std::ranges::distance(a)), std::ranges::range_difference_t<R>);
+  }
+  {
+    // Unsized range, non-copyable iterator type, rvalue-ref-qualified begin()
+    using It = cpp20_input_iterator<int*>;
+    using Sent = sentinel_wrapper<cpp20_input_iterator<int*>>;
+    using R = std::ranges::subrange<It, Sent, std::ranges::subrange_kind::unsized>;
+
+    int a[] = {1, 2, 3};
+    auto r = R(It(a), Sent(It(a + 3)));
+    assert(std::ranges::distance(r) == 3);
+    assert(std::ranges::distance(static_cast<R&&>(r)) == 3);
+    static_assert(!std::is_invocable_v<decltype(std::ranges::distance), const R&>);
+    static_assert(!std::is_invocable_v<decltype(std::ranges::distance), const R&&>);
+  }
+  {
+    // Sized range (unsized sentinel type), non-copyable iterator type, rvalue-ref-qualified begin()
+    using It = cpp20_input_iterator<int*>;
+    using Sent = sentinel_wrapper<cpp20_input_iterator<int*>>;
+    using R = std::ranges::subrange<It, Sent, std::ranges::subrange_kind::sized>;
+
+    int a[] = {1, 2, 3};
+    auto r = R(It(a), Sent(It(a + 3)), 3);
+    assert(std::ranges::distance(r) == 3);
+    assert(std::ranges::distance(static_cast<R&&>(r)) == 3);
+    static_assert(!std::is_invocable_v<decltype(std::ranges::distance), const R&>);
+    static_assert(!std::is_invocable_v<decltype(std::ranges::distance), const R&&>);
+  }
+  {
+    // Sized range (sized sentinel type), non-copyable iterator type
+    test_ordinary<cpp20_input_iterator<int*>, sized_sentinel<cpp20_input_iterator<int*>>>();
+  }
+  test_ordinary<cpp17_input_iterator<int*>, sentinel_wrapper<cpp17_input_iterator<int*>>>();
+  test_ordinary<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
+  test_ordinary<output_iterator<int*>, sentinel_wrapper<output_iterator<int*>>>();
+  test_ordinary<forward_iterator<int*>, sentinel_wrapper<forward_iterator<int*>>>();
+  test_ordinary<bidirectional_iterator<int*>, sentinel_wrapper<bidirectional_iterator<int*>>>();
+  test_ordinary<random_access_iterator<int*>, sentinel_wrapper<random_access_iterator<int*>>>();
+  test_ordinary<contiguous_iterator<int*>, sentinel_wrapper<contiguous_iterator<int*>>>();
+  test_ordinary<int*, sentinel_wrapper<int*>>();
+
+  test_ordinary<cpp17_input_iterator<int*>, sized_sentinel<cpp17_input_iterator<int*>>>();
+  test_ordinary<cpp20_input_iterator<int*>, sized_sentinel<cpp20_input_iterator<int*>>>();
+  test_ordinary<output_iterator<int*>, sized_sentinel<output_iterator<int*>>>();
+  test_ordinary<forward_iterator<int*>, sized_sentinel<forward_iterator<int*>>>();
+  test_ordinary<bidirectional_iterator<int*>, sized_sentinel<bidirectional_iterator<int*>>>();
+  test_ordinary<random_access_iterator<int*>, sized_sentinel<random_access_iterator<int*>>>();
+  test_ordinary<contiguous_iterator<int*>, sized_sentinel<contiguous_iterator<int*>>>();
+  test_ordinary<int*, sized_sentinel<int*>>();
+  test_ordinary<int*, int*>();
+
+  // Calling it on a non-range isn't allowed.
+  static_assert(!std::is_invocable_v<decltype(std::ranges::distance), int>);
+  static_assert(!std::is_invocable_v<decltype(std::ranges::distance), int*>);
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

 
 // [numeric.ops.overview] currently has no ranges algorithms. See P1813, P2214
 
 // [range.iter.ops]
 
 static_assert(test(std::ranges::advance, p, 5));
 static_assert(test(std::ranges::advance, p, 5, a+10));
 static_assert(test(std::ranges::advance, p, a+10));
-//static_assert(test(std::ranges::distance, a));
-//static_assert(test(std::ranges::distance, a, a+10));
+static_assert(test(std::ranges::distance, a));
+static_assert(test(std::ranges::distance, a, a+10));
 static_assert(test(std::ranges::next, a));
 static_assert(test(std::ranges::next, a, 5));
 static_assert(test(std::ranges::next, a, 5, a+10));
 static_assert(test(std::ranges::next, a, a+10));
 static_assert(test(std::ranges::prev, a+10));
 static_assert(test(std::ranges::prev, a+10, 5));
 static_assert(test(std::ranges::prev, a+10, 5, a));