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

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

Differential Revision: https://reviews.llvm.org/D101922

NOKEYCHECK=True
GitOrigin-RevId: 36d0fdf9ac3b4d2f509e1c56b3d45ac02cdc977e
diff --git a/include/CMakeLists.txt b/include/CMakeLists.txt
index 4a58a2c..e086a4c 100644
--- a/include/CMakeLists.txt
+++ b/include/CMakeLists.txt
@@ -7,10 +7,12 @@
   __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
diff --git a/include/__function_like.h b/include/__function_like.h
new file mode 100644
index 0000000..8a3597b
--- /dev/null
+++ b/include/__function_like.h
@@ -0,0 +1,56 @@
+// -*- 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
diff --git a/include/__iterator/advance.h b/include/__iterator/advance.h
new file mode 100644
index 0000000..3591b9d
--- /dev/null
+++ b/include/__iterator/advance.h
@@ -0,0 +1,157 @@
+// -*- 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
diff --git a/include/iterator b/include/iterator
index e3d1360..e490210 100644
--- a/include/iterator
+++ b/include/iterator
@@ -124,6 +124,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,
@@ -472,6 +483,7 @@
 #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>
@@ -534,7 +546,8 @@
    __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)
 {