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

[cjdb]

Summary

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

[cjdb]

removes 0wcp

[cjdb]

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

87–95 ↗

(On Diff #343090)

I'm toying with the idea of replacing this with

// in some header
template<class T>
inline constexpr bool not_addressable = !requires(T& t) { &t; };

template<class T>
[[nodiscard]] consteval bool standard_function_properties()
{
  static_assert(!not_addressable<T>);
  static_assert(!not_addressable<T const>);

  static_assert(!std::default_initializable<advance_t>);

  static_assert(!std::move_constructible<advance_t>);
  static_assert(!std::assignable<advance_t&, advance_t>);
  static_assert(!std::assignable<advance_t&, advance_t const>);

  static_assert(!std::copy_constructible<advance_t>);
  static_assert(!std::assignable<advance_t&, advance_t&>);
  static_assert(!std::assignable<advance_t&, advance_t const&>);

  static_assert(std::is_final_v<advance_t>);
}

// in this file
static_assert(std::remove_cv_t<decltype(std::ranges::advance)>);

[cjdb]

removes a different 0wcp

[Mordante]

I like the Implements [range.iter.op.advance] part in the description, makes finding the documentation a lot easier!
Is the synopsis up to date?

libcxx/include/__iterator/functionish.h

31 ↗

(On Diff #343090)

Can we use a clearer name, for example __function_like, ish sounds rather fishy to me. Or maybe something with ADL in the name, but I've no nice name for that to offer.

libcxx/include/__iterator/primitives.h

39 ↗

(On Diff #343090)

Can't we return the unsigned version of _Tp? Then we can return the largest negative value.

56 ↗

(On Diff #343090)

Can you remove the else?

112 ↗

(On Diff #343090)

Can you remove the else?

[Mordante]

libcxx/include/__iterator/primitives.h

129 ↗

(On Diff #343090)

If we violate the preconditions we leave the function without returning a value, resulting in UB. Can you add _LIBCPP_UNREACHABLE() instead.

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

16

Please use

// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_DEBUG=1                                  
// UNSUPPORTED: libcxx-no-debug-mode

instead.
I wonder whether we still need to use this at all now we have a CI build with debug mode enabled. I will probably remove them from my format patches.

[cjdb]

libcxx/include/__iterator/functionish.h

31 ↗

(On Diff #343090)

__function_like wfm. There's more going on here than just ADL inhibition, so we'd need a very good replacement.

libcxx/include/__iterator/primitives.h

56 ↗

(On Diff #343090)

This is an if constexpr else, which prunes the false case from the codegen when the true path is generated.

112 ↗

(On Diff #343090)

See above.

129 ↗

(On Diff #343090)

Oooooh thanks for this! I was sad that _LIBCPP_ASSERT was so... relaxed.

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

16

That's just something I forgot to delete. I was trying to get my _LIBCPP_ASSERT to fire since I was sure a precondition was bad and forgot to delete it. _LIBCPP_UNREACHABLE will render the debug stuff unnecessary anyway, I hope.

[• Quuxplusone]

libcxx/include/CMakeLists.txt

20–21

Both of these filenames violate my continuing-to-devolve-but-still-fairly-conservative rules about helper header naming. Looking at these names I have no idea what these headers contain or for what purpose they exist as separate entities.

libcxx/include/__iterator/functionish.h

31 ↗

(On Diff #343090)

I believe the traditional name is "niebloid"; could we use "niebloid"? (Or point to a technical difficulty with "niebloid"?)
In that case, this class would be niebloid_base, and the filename would be __ranges/niebloid_base.h (__iterator/? __algorithm/?)

But at a higher level, I don't see why we'd want all of our niebloids to inherit from a common base class at all. This seems like the sort of thing that should be handled via a macro, so that we could just write, like,

class __advance_fn {
    _LIBCPP_NIEBLOID_SPECIAL_MEMBERS(__advance_fn);
public:
    void operator()(...) const...
    etc...
};

You're also trying to command the tides a little bit here; e.g. you're going out of your way to make __advance_fn "not default constructible," but that doesn't actually stop anyone from writing e.g. decltype(std::ranges::advance) ha = {};.
We also need people to be able to pass these objects around like functions, right? I mean,

std::vector<int*> v = ...;
std::transform(v.begin(), v.end(), std::ranges::next);

is supposed to work? (Right?) If we need that to work, then making these objects immovable is actually counterproductive: we want them to be copyable just like function pointers and lambdas would be.

[cjdb]

libcxx/include/CMakeLists.txt

20–21

• I'll admit __iterator/functionish.h should probably have been just __functionish.h.
• __iterator/primitives.h on the other hand corresponds to the stable name [iterator.primitives]. We could always do __iterator/primitives/advance.h, etc.

libcxx/include/__iterator/functionish.h

31 ↗

(On Diff #343090)

I believe the traditional name is "niebloid"; could we use "niebloid"? (Or point to a technical difficulty with "niebloid"?)

advance is a "niebloid", but this __function_like has no relationship with niebloids. I'm just getting back the functionality of functions here. Also, "niebloid" is a cute name, but it's about as informative as "Koenig" lookup (so I'd prefer a more boring name). As for where this file lives, I have zero opinion.

But at a higher level, I don't see why we'd want all of our niebloids to inherit from a common base class at all. This seems like the sort of thing that should be handled via a macro, so that we could just write, like,

I'm certainly not married to the current implementation: whatever's most readable is probably best (readable for the user getting a diagnostic, that is). Lemme experiment when I am working on this next.

You're also trying to command the tides a little bit here; e.g. you're going out of your way to make __advance_fn "not default constructible," but that doesn't actually stop anyone from writing e.g. decltype(std::ranges::advance) ha = {};.

Is that because it's an aggregate? Ugh.

We also need people to be able to pass these objects around like functions, right? I mean,

std::vector<int*> v = ...;
std::transform(v.begin(), v.end(), std::ranges::next);

is supposed to work? (Right?) If we need that to work, then making these objects immovable is actually counterproductive: we want them to be copyable just like function pointers and lambdas would be.

Should it work? Morally, yes. Unless this is an addressable function (and I don't see that it is), the standard goes out of its way to say that this is not possible (grep for "addressable" in http://wg21.link/library). Try doing the above with std::next, for example. Niebloids are not function objects: it's just the easiest (and only portable) way we can do them presently.

[• Quuxplusone]

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

39 ↗

(On Diff #343094)

I don't think we can have tests in test/std/ that depend on the internals of libc++ in this way.
You could do this as a SFINAE test, like,

template<class T>
concept HasADLAdvance = requires(T x) { advance(x, 0); }
    || requires(T x) { advance(x, x); }
    || requires(T x) { advance(x, 0, x); };
template<class T>
concept IsAddressable = requires(T x) { &x; } || std::movable<T>;
static_assert(!HasADLAdvance<std::ranges::dangling*>);
static_assert(!IsAddressable<decltype(std::ranges::advance)>);

(I also recommend using std::ranges::dangling* or something like that, because it's way lighter-weight than std::ranges::forward_iterator and also does not require you to reopen namespace std in this test file.)

[Mordante]

libcxx/include/__iterator/primitives.h

56 ↗

(On Diff #343090)

Good point. I'm too used commenting on a 'return else' sequence ;-)

[cjdb]

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

39 ↗

(On Diff #343094)

I don't think we can have tests in test/std/ that depend on the internals of libc++ in this way.

Is this in regard to avoiding just // expected-error@*:*{{no matching function for call to '__convert_to_integral'}}? That's an instantiation error I didn't try too hard to fix, so I could revisit it.

You could do this as a SFINAE test, like,

template<class T>
concept HasADLAdvance = requires(T x) { advance(x, 0); }
    || requires(T x) { advance(x, x); }
    || requires(T x) { advance(x, 0, x); };
template<class T>
concept IsAddressable = requires(T x) { &x; } || std::movable<T>;
static_assert(!HasADLAdvance<std::ranges::dangling*>);
static_assert(!IsAddressable<decltype(std::ranges::advance)>);

Why is IsAddressable a disjunction instead of a conjunction? (Also, why is movability involved at all?).

(I also recommend using std::ranges::dangling* or something like that, because it's way lighter-weight than std::ranges::forward_iterator and also does not require you to reopen namespace std in this test file.)

std::ranges::view_base is already in, so I'll use that instead.

[cjdb]

responds to comments from @Mordante

• renames __functionish to __function_like
• adds synopsis
• changes __abs to return an unsigned
• adds _LIBCPP_UNREACHABLE()
• removes _LIBCPP_DEBUG_LEVEL

responds to comments from @Quuxplusone

• moves __iterator/function_like.h to __function_like.h
• SFINAEs out std::advance when _Distance isn't convertible to an integral
  • fixes expected error in verification test
• adds missing _LIBCPP_POP_MACROS

miscellaneous fixes:

• moves certain verification tests into test_standard_function.h so they can be put in advance.pass.cpp

[cjdb]

Is the synopsis up to date?

It is now :-)

libcxx/include/__iterator/functionish.h

31 ↗

(On Diff #343090)

You're also trying to command the tides a little bit here; e.g. you're going out of your way to make __advance_fn "not default constructible," but that doesn't actually stop anyone from writing e.g. decltype(std::ranges::advance) ha = {};.

I just tried this and it's not valid. Are there any other ways it can be written?

libcxx/include/__iterator/primitives.h

39 ↗

(On Diff #343090)

I suppose we could. I don't like treating unsigned ints as "non-negative whole numbers", but I don't think we've got a choice here.

[cjdb]

removes 0wcp

[Mordante]

LGTM modulo some small nits.

libcxx/include/__function_like.h

11

Please also rename the include guard.

libcxx/include/__iterator/primitives.h

39 ↗

(On Diff #343090)

In general I also dislike this way to treat unsigned values. But I think it's better than disallowing one value.

41 ↗

(On Diff #343448)

I'm not too fond of negating unsigned values. How do you feel about method/approach used in <charconv>?
Here the code I'm referring to, mainly __complement, but some added context.

template <typename _Tp>
inline _LIBCPP_INLINE_VISIBILITY _Tp
__complement(_Tp __x)
{
    static_assert(is_unsigned<_Tp>::value, "cast to unsigned first");
    return _Tp(~__x + 1);
}

template <typename _Tp>
inline _LIBCPP_INLINE_VISIBILITY typename make_unsigned<_Tp>::type
__to_unsigned(_Tp __x)
{
    return static_cast<typename make_unsigned<_Tp>::type>(__x);
}

template <typename _Tp>
_LIBCPP_AVAILABILITY_TO_CHARS
inline _LIBCPP_INLINE_VISIBILITY to_chars_result
__to_chars_itoa(char* __first, char* __last, _Tp __value, true_type)
{
    auto __x = __to_unsigned(__value);
    if (__value < 0 && __first != __last)
    {
        *__first++ = '-';
        __x = __complement(__x);
    }

    return __to_chars_itoa(__first, __last, __x, false_type());
}

[zoecarver]

libcxx/include/__iterator/primitives.h

99 ↗

(On Diff #343448)

This is a value we likely actually do want to discard.

[cjdb]

libcxx/include/__iterator/primitives.h

99 ↗

(On Diff #343448)

Please elaborate?

[cjdb]

applies feedback from @Mordante:

• replaces leftover instances of "functionish" with "function_like"
• changes -__n to explicit two's complement

applies self-feedback (not listed):

• adds output_iterator tests
• replaces conversion to unsigned int with __to_unsigned_like

[zoecarver]

libcxx/include/__iterator/primitives.h

99 ↗

(On Diff #343448)

If we did the thing I wish we did in C++ and functions were nodiscard by default, there would be a [[discardable_result]] attribute instead.

If that were the case, this function would be one of the ones that's marked with [[discardable_result]], because there are valid reasons to use this function and discard the result. That's probably the most common use, in fact.

In other words, this function is one of the ones where we don't actually need the nodiscard attribute.

[cjdb]

libcxx/include/__iterator/primitives.h

99 ↗

(On Diff #343448)

In other words, this function is one of the ones where we don't actually need the nodiscard attribute.

What I meant was "please elaborate on why you feel this function's result should be considered discardable".

[zoecarver]

libcxx/include/__iterator/primitives.h

99 ↗

(On Diff #343448)

Because it has side effects: advancing the iterator. It's possible, and even likely, that users would only care about the side effects. One example of this is in the implementation of ranges::next another is in my drop_view patch.

[• Quuxplusone]

libcxx/include/__iterator/primitives.h

99 ↗

(On Diff #343448)

std::ranges::advance(i, s); // advance i to s
This is the normal and expected use of the function: for its side effect. It's just like std::advance. When we get to std::ranges::next, you'll have a stronger case for _LIBCPP_NODISCARD_EXT.

Also, again, please make sure to use _LIBCPP_NODISCARD_EXT for things that are non-nodiscard according to the Standard Itself. We can mark them, but we need to be clear that it's a libc++ extension. libc++ uses raw [[nodiscard]] only in places that the Standard Itself uses [[nodiscard]] — a rare occurrence.

[zoecarver]

libcxx/test/support/test_iterators.h

783

Maybe we should have a operations_count too. I feel like these should be += n but that's not very helpful for testing complexity.

[ldionne]

libcxx/include/__iterator/primitives.h

10 ↗

(On Diff #343579)

Why is this header named that way? Shouldn't this be __iterator/advance.h to be consistent with what we've done so far? We've never named headers after the section of the standard that they roughly represent, and I don't think we should start doing that. Section names can change, they don't necessarily best represent what's in the file, and it goes against what we've started doing consistently.

39 ↗

(On Diff #343579)

Drop [[nodiscard]] (as discussed offline). Also applies to most other places where you use it.

Also, should this be promoted to a more general utility?

And also, this may be obvious to you, but why don't we simply use std::abs? Is it because http://eel.is/c++draft/iterator.primitives#range.iter.op.advance-6.1.1 uses absolute value in math notation (which is well-defined for all inputs), whereas std::abs is UB if the absolute value can't be represented in the return type?

60–70 ↗

(On Diff #343579)

I understand why this works, but I find it's a slightly confusing way to write this. Instead, Maybe else if constexpr (is_bidirectional_iterator<_Ip>) { handle bidirectional case } else { handle-forward-only-case }.

It's not as clever, but maybe easier to understand?

libcxx/include/iterator

550

What's the rationale for this change? I remember playing around the same area here: https://reviews.llvm.org/D81425, it might be useful to read that again for context. I don't have enough time to form an opinion again right now unfortunately.

If we decide to keep it, we should add a test. IIUC that would be considered a libc++ extension at this point based on glancing at https://reviews.llvm.org/D81425 again quickly.

libcxx/test/support/test_iterators.h

727

s/[[nodiscard]]//g

[cjdb]

libcxx/include/__iterator/primitives.h

10 ↗

(On Diff #343579)

Same reason we have __ranges/access.h. I can split it up, but it feels weird to do two different things here.

39 ↗

(On Diff #343579)

Drop [[nodiscard]] (as discussed offline). Also applies to most other places where you use it.

Also, should this be promoted to a more general utility?

And also, this may be obvious to you, but why don't we simply use std::abs? Is it because http://eel.is/c++draft/iterator.primitives#range.iter.op.advance-6.1.1 uses absolute value in math notation (which is well-defined for all inputs), whereas std::abs is UB if the absolute value can't be represented in the return type?

std::abs isn't constexpr, so that's a no-go. I can promote it to a general utility. Which header would you like it in?

60–70 ↗

(On Diff #343579)

I can do that, but it results in code duplication.

else if constexpr (bidirectional_iterator<_Ip>) {
  while (__n > 0) {
    --__n;
    ++_i;
  }
  while (__n < 0) {
    ++__n;
    --__i;
  }
}
else {
  while (__n > 0) {
    --__n;
    ++_i;
  }
}

I suppose I could put the forward case into an __advance_forward and call that twice. WDYT?

else if constexpr (bidirectional_iterator<_Ip>) {
  __advance_forward(__i, __n);
  __advance_backward(__i, __n);
}
else {
  __advance_forward(__i, __n);
}

99 ↗

(On Diff #343448)

Also, again, please make sure to use _LIBCPP_NODISCARD_EXT for things that are non-nodiscard according to the Standard Itself. We can mark them, but we need to be clear that it's a libc++ extension.

Also, again, why do we need to be clear that it's an extension? What does _LIBCPP_NODISCARD_EXT offer us over using [[nodiscard]] and the user disabling the extension?

libc++ uses raw [[nodiscard]] only in places that the Standard Itself uses [[nodiscard]] — a rare occurrence.

That's because no one has gone to the effort of adding [[nodiscard]] to everything that should have it. I tried to change this for ranges in C++20, but LEWG felt the effort at the NB comment stage was to much when we had scores (if not hundreds) of other comments to look into and forward to LWG, so they asked me to defer to C++23. That's a paper I should revisit.

Because it has side effects: advancing the iterator. It's possible, and even likely, that users would only care about the side effects.

I still feel that this is information that the user shouldn't be implicitly discarding, but it looks like I've got @ldionne, @zoecarver, and @Quuxplusone against, so I'm going to remove it.

libcxx/include/iterator

550

Making an unqualified call to advance(i, s) will yield no matching function for call to '__convert_to_integral' otherwise. That's definitely an implementation detail leaking out of the interface, and suppresses what I think is the more natural diagnostic: no matching function for call to 'advance'.

If we decide to keep it, we should add a test. IIUC that would be considered a libc++ extension at this point based on glancing at https://reviews.llvm.org/D81425 again quickly.

I'll have a read and report my opinions here. I'm actually surprised that std::advance doesn't constrain this function on Distance being convertible to the iterator's distance type! That's probably an LWG defect there.

libcxx/test/support/test_iterators.h

783

Hmm that's a better name. I'm not really tracking the distance: I'm tracking the number of forward and backward operations. WDYT about

• s/distance_traversed/operation_count/g
• s/displacement/operation_displacement/g

With the exception of input iterators, tracking distance isn't useful since we'll very soon have std::ranges::distance. For the input iterator case, operation_count is synonymous.

[cjdb]

libcxx/include/iterator

550

After looking at D81425, I think the goals are different. D81425 takes a not-to-spec std::advance that has iterator_traits<I>::difference_type as its parameter and makes it to-spec by changing it to _Distance. As much as I don't like that, it's to-spec and so is a Good Thing.

What I'm doing here is constraining when std::advance can participate in overload resolution, which prevents this unfortunate diagnostic spew. There's always a diagnostic, but I'm changing what's presented to a user.

Yes, it's an extension, but I believe it's a conforming one, since the wording implies that n is convertible to an integral. See std::for_each_n, for an example (all the _n algorithms already do this), which @mclow.lists points out. I've also now sent off an LWG defect asking for a mandates paragraph to be applied retroactively all the way back to C++98, so hopefully this won't be an extension come year-end.

[zoecarver]

I may have a few more comments later.

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

34

Nit: I think abs would make this clearer.

41

When would this not be exactly one?

41

Maybe i.distance_traversed() == 1 || n & i.distance_traversed() == 0.

78

Might as well test them all with N == 0.

113

I feel like there've been a few times where I could have used a type like this. Maybe move it into the test_iterators.h header?

128

What is the "assignable case"?

156

Why is 2 missing? If you're going to have seven, might as well have them all.

Edit: I see, maybe make a comment about why we can't use cpp20_iterator.

163

This suggestion might not actually be helpful, so feel free to just ignore it. But I was thinking, maybe we don't always want to test input iterator with N == 1, so maybe make this go 7, 6, 5, ...

192

If you dereference this, it should always be n, right? Maybe that's simpler and then we can get rid of expected_t.

[cjdb]

Applies feedback from @ldionne:

• renames __iterator/primitives.h to __iterator/advance.h
• adds __advance_forward and __advance_backward to simplify advance(i, s) overload
• removes some [[nodiscard]]

Applies feedback from @zoecarver:

• removes [[nodiscard]] from advance(i, n, s) overload
• moves sentinel_wrapper into test_iterators.h
• adds comment explaining why cpp20_input_iterator is missing
• reverses the distance in some cases

[cjdb]

libcxx/include/__iterator/primitives.h

60–70 ↗

(On Diff #343579)

PTAL.

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

34

abs is not constexpr.

41

In the case where assignment happens, which has distance_traversed == 0.

128

http://eel.is/c++draft/range.iter.ops#range.iter.op.advance-4.1

192

The point of these tests is to confirm that?

libcxx/test/support/test_iterators.h

727

I've removed it for some areas, but kept it where I think calling and not using is error-prone.

[cjdb]

rebases to activate CI

[cjdb]

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

41

That's really unclear. There are only two states: 0 or 1. I can see the case for wanting an explicit i.stride_count() == 0 || i.stride_count() == 1, but n & i.stride_count() == 0 is a strange way to word that.

[cjdb]

Changes requested by @zoecarver:

• Replaces x <= 0 check with x == 0 or x == 1 check.

Changes requested by @Quuxplusone:

• Replaces verify test with compile-time test.
• Adds comment explaining why something non-standard has been added to std::ranges in the test file.

Changes requested by @ldionne:

• Removes more [[nodiscard]] (still keeps a few that I think could result in bugginess).

[ldionne]

libcxx/include/__iterator/advance.h

11

Needs the correct header guard.

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/incrementable_traits.h
   __iterator/iter_move.h
   __iterator/iterator_traits.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
   __memory/compressed_pair.h
   __memory/construct_at.h

libcxx/include/__function_like.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_FUNCTION_LIKE_H
+#define _LIBCPP___ITERATOR_FUNCTION_LIKE_H
+
+#include <__config>
+
+#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 {
+// Per [range.iter.ops.general] and [algorithms.requirements], functions in namespace std::ranges
+// can't be found by ADL and inhibit ADL when found by unqualified lookup. The easiest way to
+// facilitate this is to use function objects.
+//
+// Since these are still standard library functions, we use `__function_like` to eliminate most of
+// the properties that function objects get by default (e.g. semiregularity, addressability), to
+// limit the surface area of the unintended public interface, so as to curb the effect of Hyrum's
+// law.
+struct __function_like {
+  __function_like() = delete;
+  __function_like(__function_like const&) = delete;
+  __function_like& operator=(__function_like const&) = delete;
+
+  void operator&() const = delete;
+
+  struct __tag { };
+
+protected:
+  constexpr explicit __function_like(__tag) noexcept {}
+  ~__function_like() = default;
+};
+} // namespace ranges
+
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ITERATOR_FUNCTION_LIKE_H

libcxx/include/__iterator/advance.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_ADVANCE_H
+#define _LIBCPP___ITERATOR_ADVANCE_H
+
+#include <__config>
+#include <__debug>
+#include <__function_like.h>
+#include <__iterator/concepts.h>
+#include <__iterator/incrementable_traits.h>
+#include <concepts>
+#include <limits>
+#include <type_traits>
+#include <utility>
+
+#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 {
+// [range.iter.op.advance]
+struct __advance_fn final : __function_like {
+private:
+  template <signed_integral _Tp>
+  static constexpr make_unsigned_t<_Tp> __abs(_Tp const __n) noexcept {
+    auto const __unsigned_n = __to_unsigned_like(__n);
+    auto const __complement = ~__unsigned_n + 1;
+    return __n < 0 ? __complement : __unsigned_n;
+  }
+
+  template <class _Ip>
+  static constexpr void __advance_forward(_Ip& __i, iter_difference_t<_Ip> __n) {
+    while (__n > 0) {
+      --__n;
+      ++__i;
+    }
+  }
+
+  template <class _Ip>
+  static constexpr void __advance_backward(_Ip& __i, iter_difference_t<_Ip> __n) {
+    while (__n < 0) {
+      ++__n;
+      --__i;
+    }
+  }
+
+public:
+  constexpr explicit __advance_fn(__tag __x) noexcept : __function_like(__x) {}
+
+  // Preconditions: If `I` does not model `bidirectional_iterator`, `n` is not negative.
+  template <input_or_output_iterator _Ip>
+  constexpr void operator()(_Ip& __i, iter_difference_t<_Ip> __n) const {
+    _LIBCPP_ASSERT(__n >= 0 || bidirectional_iterator<_Ip>,
+                   "If `n < 0`, then `bidirectional_iterator<I>` must be true.");
+
+    // If `I` models `random_access_iterator`, equivalent to `i += n`.
+    if constexpr (random_access_iterator<_Ip>) {
+      __i += __n;
+      return;
+    } else if constexpr (bidirectional_iterator<_Ip>) {
+      // Otherwise, if `n` is non-negative, increments `i` by `n`.
+      __advance_forward(__i, __n);
+      // Otherwise, decrements `i` by `-n`.
+      __advance_backward(__i, __n);
+      return;
+    } else {
+      // Otherwise, if `n` is non-negative, increments `i` by `n`.
+      __advance_forward(__i, __n);
+      return;
+    }
+  }
+
+  // Preconditions: Either `assignable_from<I&, S> || sized_sentinel_for<S, I>` is modeled, or [i, bound) denotes a range.
+  template <input_or_output_iterator _Ip, sentinel_for<_Ip> _Sp>
+  constexpr void operator()(_Ip& __i, _Sp __bound) const {
+    // If `I` and `S` model `assignable_from<I&, S>`, equivalent to `i = std::move(bound)`.
+    if constexpr (assignable_from<_Ip&, _Sp>) {
+      __i = std::move(__bound);
+    }
+    // Otherwise, if `S` and `I` model `sized_sentinel_for<S, I>`, equivalent to `ranges::advance(i, bound - i)`.
+    else if constexpr (sized_sentinel_for<_Sp, _Ip>) {
+      (*this)(__i, __bound - __i);
+    }
+    // Otherwise, while `bool(i != bound)` is true, increments `i`.
+    else {
+      while (__i != __bound) {
+        ++__i;
+      }
+    }
+  }
+
+  // Preconditions:
+  //   * If `n > 0`, [i, bound) denotes a range.
+  //   * If `n == 0`, [i, bound) or [bound, i) denotes a range.
+  //   * If `n < 0`, [bound, i) denotes a range, `I` models `bidirectional_iterator`, and `I` and `S` model `same_as<I, S>`.
+  // Returns: `n - M`, where `M` is the difference between the the ending and starting position.
+  template <input_or_output_iterator _Ip, sentinel_for<_Ip> _Sp>
+  constexpr iter_difference_t<_Ip> operator()(_Ip& __i, iter_difference_t<_Ip> __n, _Sp __bound) const {
+    _LIBCPP_ASSERT(__n >= 0 || (bidirectional_iterator<_Ip> && same_as<_Ip, _Sp>),
+                   "If `n < 0`, then `bidirectional_iterator<I> && same_as<I, S>` must be true.");
+    // If `S` and `I` model `sized_sentinel_for<S, I>`:
+    if constexpr (sized_sentinel_for<_Sp, _Ip>) {
+      // If |n| >= |bound - i|, equivalent to `ranges::advance(i, bound)`.
+      if (const auto __M = __bound - __i; __abs(__n) >= __abs(__M)) {
+        (*this)(__i, __bound);
+        return __n - __M;
+      }
+
+      // Otherwise, equivalent to `ranges::advance(i, n)`.
+      (*this)(__i, __n);
+      return 0;
+    } else {
+      // Otherwise, if `n` is non-negative, while `bool(i != bound)` is true, increments `i` but at
+      // most `n` times.
+      while (__i != __bound && __n > 0) {
+        ++__i;
+        --__n;
+      }
+
+      // Otherwise, while `bool(i != bound)` is true, decrements `i` but at most `-n` times.
+      if constexpr (bidirectional_iterator<_Ip> && same_as<_Ip, _Sp>) {
+        while (__i != __bound && __n < 0) {
+          --__i;
+          ++__n;
+        }
+      }
+      return __n;
+    }
+
+    _LIBCPP_UNREACHABLE();
+  }
+};
+
+inline constexpr auto advance = __advance_fn(__function_like::__tag());
+} // namespace ranges
+
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ITERATOR_ADVANCE_H

libcxx/include/iterator

 template <class InputIterator>  // constexpr in C++17
   constexpr InputIterator next(InputIterator x,
 typename iterator_traits<InputIterator>::difference_type n = 1);
 
 template <class BidirectionalIterator>  // constexpr in C++17
   constexpr BidirectionalIterator prev(BidirectionalIterator x,
     typename iterator_traits<BidirectionalIterator>::difference_type n = 1);
 
+// [range.iter.ops], range iterator operations
+namespace ranges {
+  // [range.iter.op.advance], ranges::advance
+  template<input_or_output_iterator I>
+    constexpr void advance(I& i, iter_difference_t<I> n);                          // since C++20
+  template<input_or_output_iterator I, sentinel_for<I> S>
+    constexpr void advance(I& i, S bound);                                         // since C++20
+  template<input_or_output_iterator I, sentinel_for<I> S>
+    constexpr iter_difference_t<I> advance(I& i, iter_difference_t<I> n, S bound); // since C++20
+}
+
 template <class Iterator>
 class reverse_iterator
     : public iterator<typename iterator_traits<Iterator>::iterator_category,
                       typename iterator_traits<Iterator>::value_type,
                       typename iterator_traits<Iterator>::difference_type,
                       typename iterator_traits<Iterator>::pointer,
                       typename iterator_traits<Iterator>::reference>
 {

 
 }  // std
 
 */
 
 #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/readable_traits.h>
 #include <__memory/addressof.h>
 #include <__memory/pointer_traits.h>
 #include <compare>

 template <class _RandIter>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 void __advance(_RandIter& __i,
              typename iterator_traits<_RandIter>::difference_type __n, random_access_iterator_tag)
 {
    __i += __n;
 }
 
-template <class _InputIter, class _Distance>
+template <class _InputIter, class _Distance,
+          class = typename enable_if<is_integral<decltype(_VSTD::__convert_to_integral(declval<_Distance>()))>::value>::type>
 inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX14
 void advance(_InputIter& __i, _Distance __orig_n)
 {
     typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize;
     _IntegralSize __n = __orig_n;
     _LIBCPP_ASSERT(__n >= 0 || __is_cpp17_bidirectional_iterator<_InputIter>::value,
                    "Attempt to advance(it, n) with negative n on a non-bidirectional iterator");
     _VSTD::__advance(__i, __n, typename iterator_traits<_InputIter>::iterator_category());

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/advance.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::advance
+
+#include <iterator>
+
+#include <array>
+#include <cassert>
+
+#include "test_standard_function.h"
+#include "test_iterators.h"
+
+static_assert(is_function_like<decltype(std::ranges::advance)>());
+
+using range_t = std::array<int, 10>;
+
+[[nodiscard]] constexpr bool operator==(output_iterator<int*> const x, output_iterator<int*> const y) {
+  return x.base() == y.base();
+}
+
+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() == 0 || i.stride_count() == 1);
+  assert(i.stride_displacement() == n < 0 ? -1 : 1);
+}
+
+namespace iterator_count {
+template <std::input_or_output_iterator I>
+constexpr void check_move_forward(std::ptrdiff_t const n) {
+  auto range = range_t{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+  auto first = stride_counting_iterator(I(range.begin()));
+  std::ranges::advance(first, n);
+  assert(std::move(first).base().base() == range.begin() + n);
+  check_round_trip(first, n);
+}
+
+template <std::bidirectional_iterator I>
+constexpr void check_move_backward(std::ptrdiff_t const n) {
+  auto range = range_t{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+  auto first = stride_counting_iterator(I(range.begin() + n));
+  std::ranges::advance(first, -n);
+  assert(std::move(first).base().base() == range.begin());
+  check_round_trip(first, -n);
+}
+
+[[nodiscard]] constexpr bool test() {
+  check_move_forward<cpp17_input_iterator<range_t::const_iterator> >(1);
+  check_move_forward<cpp20_input_iterator<range_t::const_iterator> >(2);
+  check_move_forward<forward_iterator<range_t::const_iterator> >(3);
+  check_move_forward<bidirectional_iterator<range_t::const_iterator> >(4);
+  check_move_forward<random_access_iterator<range_t::const_iterator> >(5);
+  check_move_forward<contiguous_iterator<range_t::const_iterator> >(6);
+  check_move_forward<output_iterator<range_t::iterator> >(7);
+
+  check_move_backward<bidirectional_iterator<range_t::const_iterator> >(4);
+  check_move_backward<random_access_iterator<range_t::const_iterator> >(5);
+  check_move_backward<contiguous_iterator<range_t::const_iterator> >(6);
+
+  // Zero should be checked for each case and each overload
+  check_move_forward<cpp17_input_iterator<range_t::const_iterator> >(0);
+  check_move_forward<cpp20_input_iterator<range_t::const_iterator> >(0);
+  check_move_forward<forward_iterator<range_t::const_iterator> >(0);
+  check_move_forward<bidirectional_iterator<range_t::const_iterator> >(0);
+  check_move_forward<random_access_iterator<range_t::const_iterator> >(0);
+  check_move_forward<output_iterator<range_t::iterator> >(0);
+  check_move_backward<bidirectional_iterator<range_t::const_iterator> >(0);
+  check_move_backward<random_access_iterator<range_t::const_iterator> >(0);
+
+  return true;
+}
+} // namespace iterator_count
+
+class distance_apriori_sentinel {
+public:
+  distance_apriori_sentinel() = default;
+  constexpr explicit distance_apriori_sentinel(std::ptrdiff_t const count) : count_(count) {}
+
+  [[nodiscard]] constexpr bool operator==(std::input_or_output_iterator auto const&) const {
+    assert(false && "difference op should take precedence");
+    return false;
+  }
+
+  [[nodiscard]] constexpr friend std::ptrdiff_t operator-(std::input_or_output_iterator auto const&,
+                                                          distance_apriori_sentinel const y) {
+    return -y.count_;
+  }
+
+  [[nodiscard]] 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;
+};
+
+namespace iterator_sentinel {
+template <std::input_or_output_iterator I, std::sentinel_for<I> S = 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 first = stride_counting_iterator(I(range.begin()));
+  std::ranges::advance(first, stride_counting_iterator(S(I(range.begin() + n))));
+  assert(std::move(first).base().base() == range.begin() + n);
+  assert(first.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 first = stride_counting_iterator(I(range.begin()));
+  std::ranges::advance(first, distance_apriori_sentinel(n));
+  assert(std::move(first).base().base() == range.begin() + n);
+  check_round_trip(first, 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 first = stride_counting_iterator(I(range.begin()));
+  auto const last = I(range.begin() + n);
+  std::ranges::advance(first, sentinel_wrapper(last));
+  assert(first.base() == last);
+  assert(first.stride_count() == n); // always `n`, so don't use `check_round_trip`
+}
+
+[[nodiscard]] constexpr bool test() {
+  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;
+}
+} // namespace iterator_sentinel
+
+namespace iterator_count_sentinel {
+struct expected_t {
+  range_t::const_iterator coordinate;
+  std::ptrdiff_t result;
+};
+
+template <std::input_or_output_iterator I>
+constexpr void check_forward_sized_sentinel_case(std::ptrdiff_t const n, expected_t const expected, range_t& range) {
+  auto current = stride_counting_iterator(I(range.begin()));
+  auto const result = std::ranges::advance(current, n, distance_apriori_sentinel(range.size()));
+  assert(current.base().base() == expected.coordinate);
+  assert(result == expected.result);
+  check_round_trip(current, n - expected.result);
+}
+
+template <std::random_access_iterator I>
+constexpr void check_backward_sized_sentinel_case(std::ptrdiff_t const n, expected_t const expected, range_t& range) {
+  auto current = stride_counting_iterator(I(range.end()));
+  auto const result = std::ranges::advance(current, -n, stride_counting_iterator(I(range.begin())));
+  assert(current.base().base() == expected.coordinate);
+  assert(result == expected.result);
+  check_round_trip(current, n - expected.result);
+}
+
+template <std::input_or_output_iterator I>
+constexpr void check_forward_case(std::ptrdiff_t const n, expected_t const expected, range_t& range) {
+  auto current = stride_counting_iterator(I(range.begin()));
+  auto const result = std::ranges::advance(current, n, sentinel_wrapper(I(range.end())));
+  assert(current.base().base() == expected.coordinate);
+  assert(result == expected.result);
+  assert(current.stride_count() == n - expected.result);
+}
+
+template <std::bidirectional_iterator I>
+constexpr void check_backward_case(std::ptrdiff_t const n, expected_t const expected, range_t& range) {
+  auto current = stride_counting_iterator(I(range.end()));
+  auto const result = std::ranges::advance(current, -n, stride_counting_iterator(I(range.begin())));
+  assert(current.base().base() == expected.coordinate);
+  assert(result == expected.result);
+  assert(current.stride_count() == n + expected.result);
+  assert(current.stride_count() == -current.stride_displacement());
+}
+
+[[nodiscard]] constexpr bool test() {
+  auto range = range_t{0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
+  check_forward_sized_sentinel_case<cpp17_input_iterator<range_t::const_iterator> >(1, {range.begin() + 1, 0}, range);
+  // cpp20_input_iterator not copyable, so is omitted
+  check_forward_sized_sentinel_case<forward_iterator<range_t::const_iterator> >(3, {range.begin() + 3, 0}, range);
+  check_forward_sized_sentinel_case<bidirectional_iterator<range_t::const_iterator> >(4, {range.begin() + 4, 0}, range);
+  check_forward_sized_sentinel_case<random_access_iterator<range_t::const_iterator> >(5, {range.begin() + 5, 0}, range);
+  check_forward_sized_sentinel_case<contiguous_iterator<range_t::const_iterator> >(6, {range.begin() + 6, 0}, range);
+  check_forward_sized_sentinel_case<output_iterator<range_t::iterator> >(7, {range.begin() + 7, 0}, range);
+
+  // bidirectional_iterator omitted because `n < 0` case requires `same_as<I, S>`
+  check_backward_sized_sentinel_case<random_access_iterator<range_t::const_iterator> >(5, {range.begin() + 5, 0},
+                                                                                       range);
+  check_backward_sized_sentinel_case<contiguous_iterator<range_t::const_iterator> >(6, {range.begin() + 4, 0}, range);
+
+  // disntance == range.size()
+  check_forward_sized_sentinel_case<forward_iterator<range_t::const_iterator> >(10, {range.end(), 0}, range);
+  check_forward_sized_sentinel_case<output_iterator<range_t::iterator> >(10, {range.end(), 0}, range);
+  check_backward_sized_sentinel_case<random_access_iterator<range_t::const_iterator> >(10, {range.begin(), 0}, range);
+
+  // distance > range.size()
+  check_forward_sized_sentinel_case<forward_iterator<range_t::const_iterator> >(1000, {range.end(), 990}, range);
+  check_forward_sized_sentinel_case<output_iterator<range_t::iterator> >(1000, {range.end(), 990}, range);
+  check_backward_sized_sentinel_case<random_access_iterator<range_t::const_iterator> >(1000, {range.begin(), -990},
+                                                                                       range);
+
+  check_forward_case<cpp17_input_iterator<range_t::const_iterator> >(1, {range.begin() + 1, 0}, range);
+  check_forward_case<forward_iterator<range_t::const_iterator> >(3, {range.begin() + 3, 0}, range);
+  check_forward_case<bidirectional_iterator<range_t::const_iterator> >(4, {range.begin() + 4, 0}, range);
+  check_forward_case<random_access_iterator<range_t::const_iterator> >(5, {range.begin() + 5, 0}, range);
+  check_forward_case<contiguous_iterator<range_t::const_iterator> >(6, {range.begin() + 6, 0}, range);
+  check_forward_case<output_iterator<range_t::iterator> >(7, {range.begin() + 7, 0}, range);
+  check_backward_case<bidirectional_iterator<range_t::const_iterator> >(8, {range.begin() + 2, 0}, range);
+
+  // disntance == range.size()
+  check_forward_case<forward_iterator<range_t::const_iterator> >(10, {range.end(), 0}, range);
+  check_forward_case<output_iterator<range_t::iterator> >(10, {range.end(), 0}, range);
+  check_backward_case<bidirectional_iterator<range_t::const_iterator> >(10, {range.begin(), 0}, range);
+
+  // distance > range.size()
+  check_forward_case<forward_iterator<range_t::const_iterator> >(1000, {range.end(), 990}, range);
+  check_forward_case<output_iterator<range_t::iterator> >(1000, {range.end(), 990}, range);
+  check_backward_case<bidirectional_iterator<range_t::const_iterator> >(1000, {range.begin(), -990}, range);
+
+  return true;
+}
+} // namespace iterator_count_sentinel
+
+int main(int, char**) {
+  static_assert(iterator_count::test());
+  assert(iterator_count::test());
+
+  static_assert(iterator_sentinel::test());
+  assert(iterator_sentinel::test());
+
+  static_assert(iterator_count_sentinel::test());
+  assert(iterator_count_sentinel::test());
+
+  return 0;
+}

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/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::advance(p, 5); // expected-error {{no matching function for call}}
+  std::ranges::advance(p, p); // expected-error {{no matching function for call}}
+  std::ranges::advance(p, 5, p); // expected-error {{no matching function for call}}
+}

libcxx/test/std/iterators/iterator.primitives/range.iter.ops/range.iter.ops.advance/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::advance
+
+#include <iterator>
+
+// 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
+
+template <class I, class... Args>
+constexpr bool unqualified_lookup_works = requires(I i, Args... args) {
+  advance(i, args...);
+};
+
+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 advance(forward_iterator<I>&, std::ptrdiff_t) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class I>
+void advance(forward_iterator<I>&, forward_iterator<I>) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class I>
+void advance(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::advance;
+  advance(x, 0);
+  advance(x, x);
+  advance(x, 0, x);
+}

libcxx/test/support/test_iterators.h

 {   return a.operator==(b); }
 
 template <typename T>
 bool operator!= (const NonThrowingIterator<T>& a, const NonThrowingIterator<T>& b) TEST_NOEXCEPT
 {   return !a.operator==(b); }
 
 #ifdef TEST_SUPPORTS_RANGES
 
+// clang-format off
+
 template <class I>
 struct cpp20_input_iterator {
   using value_type = std::iter_value_t<I>;
   using difference_type = std::iter_difference_t<I>;
   using iterator_concept = std::input_iterator_tag;
 
   cpp20_input_iterator() = default;
 
   cpp20_input_iterator(cpp20_input_iterator&&) = default;
   cpp20_input_iterator& operator=(cpp20_input_iterator&&) = default;
 
   cpp20_input_iterator(cpp20_input_iterator const&) = delete;
   cpp20_input_iterator& operator=(cpp20_input_iterator const&) = delete;
 
   explicit constexpr cpp20_input_iterator(I base) : base_(std::move(base)) {}
 
   constexpr decltype(auto) operator*() const { return *base_; }
 
-  cpp20_input_iterator& operator++() {
+  constexpr cpp20_input_iterator& operator++() {
     ++base_;
     return *this;
   }
 
-  void operator++(int) { ++base_; }
+  constexpr void operator++(int) { ++base_; }
 
-  [[nodiscard]] I const& base() const& { return base_; }
+  [[nodiscard]] constexpr I const& base() const& { return base_; }
 
-  [[nodiscard]] I base() && { return std::move(base_); }
+  [[nodiscard]] constexpr I base() && { return std::move(base_); }
 
 private:
   I base_ = I();
 };
 
+template <std::input_or_output_iterator I>
+struct iterator_concept {
+  using type = std::output_iterator_tag;
+};
+
+template <std::input_iterator I>
+struct iterator_concept<I> {
+  using type = std::input_iterator_tag;
+};
+
+template <std::forward_iterator I>
+struct iterator_concept<I> {
+  using type = std::forward_iterator_tag;
+};
+
+template <std::bidirectional_iterator I>
+struct iterator_concept<I> {
+  using type = std::bidirectional_iterator_tag;
+};
+
+template <std::random_access_iterator I>
+struct iterator_concept<I> {
+  using type = std::random_access_iterator_tag;
+};
+
+template<std::contiguous_iterator I>
+struct iterator_concept<I> {
+  using type = std::contiguous_iterator_tag;
+};
+
+template <std::input_or_output_iterator I>
+using iterator_concept_t = typename iterator_concept<I>::type;
+
+template<std::input_or_output_iterator>
+struct iter_value_or_void { using type = void; };
+
+template<std::input_iterator I>
+struct iter_value_or_void<I> {
+  using type = std::iter_value_t<I>;
+};
+
+// Iterator adaptor that counts the number of times the iterator has had a successor/predecessor
+// operation called. Has two recorders:
+// * `stride_count`, which records the total number of calls to an op++, op--, op+=, or op-=.
+// * `stride_displacement`, which records the displacement of the calls. This means that both
+//   op++/op+= will increase the displacement counter by 1, and op--/op-= will decrease the
+//   displacement counter by 1.
+template <std::input_or_output_iterator I>
+class 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>;
+
+  stride_counting_iterator() = default;
+
+  constexpr explicit stride_counting_iterator(I current) : base_(std::move(current)) {}
+
+  [[nodiscard]] constexpr I const& base() const& requires std::copyable<I> { return base_; }
+
+  [[nodiscard]] constexpr I base() && { return std::move(base_); }
+
+  constexpr difference_type stride_count() const { return stride_count_; }
+
+  constexpr difference_type stride_displacement() const { return stride_displacement_; }
+
+  constexpr decltype(auto) operator*() const { return *base_; }
+
+  constexpr decltype(auto) operator[](difference_type const n) const { return base_[n]; }
+
+  constexpr stride_counting_iterator& operator++()
+  {
+    ++base_;
+    ++stride_count_;
+    ++stride_displacement_;
+    return *this;
+  }
+
+  constexpr void operator++(int) { ++*this; }
+
+  constexpr stride_counting_iterator operator++(int)
+  requires std::forward_iterator<I>
+  {
+    auto temp = *this;
+    ++*this;
+    return temp;
+  }
+
+  constexpr stride_counting_iterator& operator--()
+  requires std::bidirectional_iterator<I>
+  {
+    --base_;
+    ++stride_count_;
+    --stride_displacement_;
+    return *this;
+  }
+
+  constexpr stride_counting_iterator operator--(int)
+  requires std::bidirectional_iterator<I>
+  {
+    auto temp = *this;
+    --*this;
+    return temp;
+  }
+
+  constexpr stride_counting_iterator& operator+=(difference_type const n)
+  requires std::random_access_iterator<I>
+  {
+    base_ += n;
+    ++stride_count_;
+    ++stride_displacement_;
+    return *this;
+  }
+
+  constexpr stride_counting_iterator& operator-=(difference_type const n)
+  requires std::random_access_iterator<I>
+  {
+    base_ -= n;
+    ++stride_count_;
+    --stride_displacement_;
+    return *this;
+  }
+
+  constexpr friend stride_counting_iterator operator+(stride_counting_iterator i, difference_type const n)
+  requires std::random_access_iterator<I>
+  {
+    return i += n;
+  }
+
+  constexpr friend stride_counting_iterator operator+(difference_type const n, stride_counting_iterator i)
+  requires std::random_access_iterator<I>
+  {
+    return i += n;
+  }
+
+  constexpr friend stride_counting_iterator operator-(stride_counting_iterator i, difference_type const n)
+  requires std::random_access_iterator<I>
+  {
+    return i -= n;
+  }
+
+  constexpr friend difference_type operator-(stride_counting_iterator const& x, stride_counting_iterator const& y)
+  requires std::sized_sentinel_for<I, I>
+  {
+    return x.base() - y.base();
+  }
+
+  constexpr bool operator==(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<(stride_counting_iterator const& x, stride_counting_iterator const& y)
+  requires std::random_access_iterator<I>
+  {
+    return x.base_ < y.base_;
+  }
+
+  constexpr friend bool operator>(stride_counting_iterator const& x, stride_counting_iterator const& y)
+  requires std::random_access_iterator<I>
+  {
+    return y < x;
+  }
+
+  constexpr friend bool operator<=(stride_counting_iterator const& x, stride_counting_iterator const& y)
+  requires std::random_access_iterator<I>
+  {
+    return !(y < x);
+  }
+
+  constexpr friend bool operator>=(stride_counting_iterator const& x, stride_counting_iterator const& y)
+  requires std::random_access_iterator<I>
+  {
+    return !(x < y);
+  }
+
+private:
+  I base_;
+  difference_type stride_count_ = 0;
+  difference_type stride_displacement_ = 0;
+};
+
+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::equality_comparable<I> {
+    return base_ == other;
+  }
+
+private:
+  I base_ = I();
+};
+
+// clang-format on
+
 #endif // TEST_STD_VER > 17 && defined(__cpp_lib_concepts)
 
 #undef DELETE_FUNCTION
 
 #endif // ITERATORS_H

libcxx/test/support/test_standard_function.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_SUPPORT_TEST_STANDARD_FUNCTION_H
+#define LIBCXX_TEST_SUPPORT_TEST_STANDARD_FUNCTION_H
+
+#include "test_macros.h"
+
+#if TEST_STD_VER >= 20
+template <class T>
+constexpr bool is_addressable = requires(T t) {
+  &t;
+};
+
+template <class T>
+[[nodiscard]] constexpr bool is_function_like() {
+  using X = std::remove_cvref_t<T>;
+  static_assert(!is_addressable<X>);
+  static_assert(!is_addressable<X const>);
+
+  static_assert(std::destructible<X> && !std::default_initializable<X>);
+
+  static_assert(!std::move_constructible<X>);
+  static_assert(!std::assignable_from<X&, X>);
+
+  static_assert(!std::copy_constructible<X>);
+  static_assert(!std::assignable_from<X&, X const>);
+  static_assert(!std::assignable_from<X&, X&>);
+  static_assert(!std::assignable_from<X&, X const&>);
+  static_assert(std::is_final_v<X>);
+  return true;
+}
+#endif
+
+#endif // LIBCXX_TEST_SUPPORT_TEST_STANDARD_FUNCTION_H