[libcxx][algorithms] adds ranges::is_partitioned and ranges::partition_point

[cjdb]

Summary

Implements part of http://wg21.link/P0896.
Implements part of [alg.partitions].

Depends on D105793.

[cjdb]

rebases to activate CI

[cjdb]

rebases to activate CI

[cjdb]

rebases to activate CI

[cjdb]

rebases to activate CI

[Mordante]

I didn't do a detailed analysis of the algorithm used.

libcxx/include/__algorithm/is_partitioned.h

52

Please add _LIBCPP_TEMPLATE_VIS and validate all other structs.

57

Please add _LIBCPP_HIDE_FROM_ABI and check all other functions.

68

__last is used after moving.

libcxx/include/__algorithm/partition_point.h

71

Why the const in const _Sp __last. (I personally like it, but it deviates from our coding style.)

libcxx/include/algorithm

369

Please add // since C++20 to these two.

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_is_partitioned/ranges_is_partitioned.pass.cpp

44

Can the range move to the parent scope?

46

Why can't you test against an exact value?

[cjdb]

In D105794#2893803, @Mordante wrote:

I didn't do a detailed analysis of the algorithm used.

Thanks for the review! A few clarifying things, but this all sounds reasonable.

libcxx/include/__algorithm/partition_point.h

71

I like the compiler catching accidental writes. Also, this is a new section of code, so I think it's worth piloting this style here. (@ldionne seems to be ambivalent towards it based on prior commits as evidence.)

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_is_partitioned/ranges_is_partitioned.pass.cpp

44

Yes, it can. I think this is a relic of when range used complexity_iterator (where the answer would've been "no").

46

I guess it's possible to say pred.count() <= 5, but my interpretation of the wording at the time made me want to base this in terms of the range's length. I take it you'd prefer 5 over ssize(all_odd)?

[Mordante]

libcxx/include/__algorithm/partition_point.h

71

I like the const too for the the same reason. So then let's keep it. I probably will start to use it in new code too.

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_is_partitioned/ranges_is_partitioned.pass.cpp

46

No I like the ssize(all_odd) over 5. IMO 5 is a fragile magic number.
I see I misread the test. It tests the complexity of the algorithm.
IMO it would be clearer to use assert(pred.count() <= ranges::ssize(range));

So just discard my previous comment.

[• Quuxplusone]

libcxx/include/__algorithm/partition_point.h

71

@cjdb @Mordante @ldionne: Please, please, don't misuse const to "pass by const value" or "return by const value." These are common typos in C++ code. @zoecarver will (I hope) recall the couple of times I've caught bugs in his code by grepping for pass-by-const-value typos.

I have a whole blog post on "const" here:
https://quuxplusone.github.io/blog/2019/01/03/const-is-a-contract/

and it ends with [a set of git grep regexes](https://quuxplusone.github.io/blog/2019/01/03/const-is-a-contract/#grep-your-codebase-today) that enable anyone — not just me, but any of you! — to find your missing-ampersand typos by grepping for parameters of the form const _Sp __last. If you start using that typo-style in code you don't want to change, it makes the job of the typo-finder vastly harder.

As of this writing, we have only five instances of pass-by-const-value in the codebase. Three of them are in requires-clauses.

$ git grep '[(,] *const [A-Za-z0-9_:]* [A-Za-z0-9_:]* *[,)=]'
__iterator/advance.h:      if (const auto __M = __bound - __i; __abs(__n) >= __abs(__M)) {
__iterator/concepts.h:  requires(const _In __i) {
__iterator/concepts.h:  requires(_Ip __i, const _Ip __j, const iter_difference_t<_Ip> __n) {
__iterator/iter_swap.h:  requires(const _I1 __i1, const _I2 __i2) {
random:binomial_distribution<_IntType>::param_type::param_type(const result_type __t, const double __p)

[cjdb]

libcxx/include/__algorithm/partition_point.h

71

I've read through this a handful of times now. I don't find it particularly convincing. You claim that they're "common typos", but I can only find one concrete example that you've come across in that blog, which doesn't generalise. I can't speak to Zoe's experience here.

Yes, const-qualifying value parameters can be a problem. It's not absolute truth that they all are. You wrote that "const is a contract". I agree with this: hell, I even teach it, but it seems we have a fundamental point of contention on this topic. Your blog implies that it's only a contract between a programmer and the interface they're programming against. From this perspective, yes, a const value parameter is useless, but this is not the only way in which const is a contract. const is also a contract between the programmer and the compiler. Under this lens, a const value parameter has strong meaning, because it gives both the reader and writer strong confidence that the object isn't going to be modified.

and it ends with a set of git grep regexes that enable anyone — not just me, but any of you! — to find your missing-ampersand typos by grepping for parameters of the form const _Sp __last. If you start using that typo-style in code you don't want to change, it makes the job of the typo-finder vastly harder.

This isn't as strong an argument against const value parameters as you think it is. It effectively reads as "let's weaken our code guarantees so that the person auditing our codebase has an easy time doing their audit". If you want an effective and painless auditing experience, write a tool that automates the process and has a configurable set of exemptions or set of rules.

79

Needs to be std::iter_difference_t<_Ip>{0}.

[Mordante]

libcxx/include/__algorithm/partition_point.h

71

and it ends with [a set of git grep regexes](https://quuxplusone.github.io/blog/2019/01/03/const-is-a-contract/#grep-your-codebase-today) that enable anyone — not just me, but any of you! — to find your missing-ampersand typos by grepping for parameters of the form const _Sp __last. If you start using that typo-style in code you don't want to change, it makes the job of the typo-finder vastly harder.

I love grep, but IMO grep isn't the best tool for this job. Nowadays there are more powerful tools for this job. For example, clang-tidy has performance-unnecessary-value-param https://clang.llvm.org/extra/clang-tidy/checks/performance-unnecessary-value-param.html .

So if we have errors due to incorrect usage of const I'd much rather invest time to improve our tooling to catch these errors.
(I don't volunteer to do this since I really want to focus on <format>.)

libcxx/include/__algorithm/is_partitioned.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 _LIBCPP___ALGORITHM_IS_PARTITIONED_H
 #define _LIBCPP___ALGORITHM_IS_PARTITIONED_H
 
+#include <__algorithm/find_if.h>
+#include <__algorithm/find_if_not.h>
 #include <__config>
+#include <__function_like.h>
+#include <__functional/identity.h>
+#include <__functional/reference_wrapper.h>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
if ( __first == __last )
         return true;
     ++__first;
     for (; __first != __last; ++__first)
         if (__pred(*__first))
             return false;
     return true;
 }
 
+#if !defined(_LIBCPP_HAS_NO_RANGES)
+
+namespace ranges {
+  struct __is_partitioned_fn final : __function_like {
+    constexpr explicit __is_partitioned_fn(__tag __x) noexcept : __function_like(__x) {}
+
+    template<input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Proj = identity,
+             indirect_unary_predicate<projected<_Ip, _Proj>> _Pred>
+    _LIBCPP_NODISCARD_EXT constexpr
+    bool operator()(_Ip __first, _Sp __last, _Pred __pred, _Proj __proj = {}) const {
+      auto __pred_ref = _VSTD::ref(__pred);
+      auto __proj_ref = _VSTD::ref(__proj);
+
+      __first = ranges::find_if_not(_VSTD::move(__first), __last, __pred_ref, __proj_ref);
+      if (__first == __last) {
+        return true;
+      }
+
+      ++__first;
+      return ranges::find_if(_VSTD::move(__first), _VSTD::move(__last), __pred_ref, __proj_ref) == __last;
+    }
+
+    template<input_range _Rp, class _Proj = identity,
+             indirect_unary_predicate<projected<iterator_t<_Rp>, _Proj>> _Pred>
+    _LIBCPP_NODISCARD_EXT constexpr
+    bool operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const {
+      return (*this)(ranges::begin(__r), ranges::end(__r), _VSTD::ref(__pred), _VSTD::ref(__proj));
+    }
+  };
+
+  inline constexpr auto is_partitioned = __is_partitioned_fn(__function_like::__tag());
+} // namespace ranges
+
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_IS_PARTITIONED_H

libcxx/include/__algorithm/partition_point.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 _LIBCPP___ALGORITHM_PARTITION_POINT_H
 #define _LIBCPP___ALGORITHM_PARTITION_POINT_H
 
 #include <__config>
+#include <__debug>
 #include <__algorithm/half_positive.h>
-#include <iterator>
+#include <__algorithm/is_partitioned.h>
+#include <__function_like.h>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/reference_wrapper.h>
+#include <__iterator/advance.h>
+#include <__iterator/distance.h>
+#include <__iterator/next.h>
+#include <__iterator/iterator_traits.h>
+#include <__iterator/concepts.h>
+#include <__iterator/projected.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__ranges/dangling.h>
+#include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
while (__len != 0)
             __len -= __l2 + 1;
         }
         else
             __len = __l2;
     }
     return __first;
 }
 
+#if !defined(_LIBCPP_HAS_NO_RANGES)
+
+namespace ranges {
+  struct __partition_point_fn final : __function_like {
+    constexpr explicit __partition_point_fn(__tag __x) noexcept : __function_like(__x) {}
+
+    template<forward_iterator _Ip, sentinel_for<_Ip> _Sp, class _Proj = identity,
+             indirect_unary_predicate<projected<_Ip, _Proj>> _Pred>
+    _LIBCPP_NODISCARD_EXT constexpr
+    _Ip operator()(_Ip __first, const _Sp __last, _Pred __pred, _Proj __proj = {}) const {
+      // This assertion breaks the logarithmic complexity requirement, but since it is only evaluated
+      // when a user opts into a debug level, the non-conformance is deemed acceptable, since it is
+      // useful for catching violated precondition bugs.
+      _LIBCPP_ASSERT(ranges::is_partitioned(__first, __last, _VSTD::ref(__pred), _VSTD::ref(__proj)),
+                     "partition_point precondition:\n"
+                     "\tthe projected elements of the range [`first`, `last`) are partitioned with respect to `pred`.");
+
+      auto __distance = 0;
+      for (auto __i = __first; __i != __last; ++__i) ++__distance; // FIXME: replace with ranges::distance
+
+      while (__distance != 0) {
+        const auto __half_distance = _VSTD::__half_positive(__distance);
+        auto __midpoint = _VSTD::next(__first, __half_distance);
+
+        if (_VSTD::invoke(__pred, _VSTD::invoke(__proj, *__midpoint))) {
+          __first = _VSTD::next(_VSTD::move(__midpoint));
+          __distance -= __half_distance + 1;
+        }
+        else {
+          __distance = __half_distance;
+        }
+      }
+
+      return __first;
+    }
+
+    template<forward_range _Rp, class _Proj = identity,
+             indirect_unary_predicate<projected<iterator_t<_Rp>, _Proj>> _Pred>
+    _LIBCPP_NODISCARD_EXT constexpr
+    borrowed_iterator_t<_Rp> operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const {
+      return (*this)(ranges::begin(__r), ranges::end(__r), _VSTD::ref(__pred), _VSTD::ref(__proj));
+    }
+  };
+
+  inline constexpr auto partition_point = __partition_point_fn(__function_like::__tag());
+} // namespace ranges
+
+#endif // !defined(_LIBCPP_HAS_NO_RANGES)
+
 _LIBCPP_END_NAMESPACE_STD
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_PARTITION_POINT_H

libcxx/include/algorithm

template<class ForwardIterator>
   constexpr ForwardIterator
     shift_right(ForwardIterator first, ForwardIterator last,
                 typename iterator_traits<ForwardIterator>::difference_type n); // C++20
 
 template <class InputIterator, class Predicate>
     constexpr bool  // constexpr in C++20
     is_partitioned(InputIterator first, InputIterator last, Predicate pred);
 
+template<input_iterator I, sentinel_for<I> S, class Proj = identity,
+         indirect_unary_predicate<projected<I, Proj>> Pred>
+  constexpr bool ranges::is_partitioned(I first, S last, Pred pred, Proj proj = {});
+
+template<input_range R, class Proj = identity,
+         indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+  constexpr bool ranges::is_partitioned(R&& r, Pred pred, Proj proj = {});
+
 template <class ForwardIterator, class Predicate>
     constexpr ForwardIterator  // constexpr in C++20
     partition(ForwardIterator first, ForwardIterator last, Predicate pred);
 
 template <class InputIterator, class OutputIterator1,
           class OutputIterator2, class Predicate>
     constexpr pair<OutputIterator1, OutputIterator2>   // constexpr in C++20
     partition_copy(InputIterator first, InputIterator last,
                    OutputIterator1 out_true, OutputIterator2 out_false,
                    Predicate pred);
 
 template <class ForwardIterator, class Predicate>
     ForwardIterator
     stable_partition(ForwardIterator first, ForwardIterator last, Predicate pred);
 
 template<class ForwardIterator, class Predicate>
     constexpr ForwardIterator  // constexpr in C++20
     partition_point(ForwardIterator first, ForwardIterator last, Predicate pred);
 
+template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
+         indirect_unary_predicate<projected<I, Proj>> Pred>
+  constexpr I ranges::partition_point(I first, S last, Pred pred, Proj proj = {}); // since C++20
+template<forward_range R, class Proj = identity,
+         indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+  constexpr borrowed_iterator_t<R>
+    ranges::partition_point(R&& r, Pred pred, Proj proj = {}); // since C++20
+
 template <class ForwardIterator>
     constexpr bool  // constexpr in C++20
     is_sorted(ForwardIterator first, ForwardIterator last);
 
 template <class ForwardIterator, class Compare>
     constexpr bool  // constexpr in C++20
     is_sorted(ForwardIterator first, ForwardIterator last, Compare comp);
 

libcxx/include/module.modulemap

module __algorithm {
       module for_each_n               { header "__algorithm/for_each_n.h" }
       module generate                 { header "__algorithm/generate.h" }
       module generate_n               { header "__algorithm/generate_n.h" }
       module half_positive            { header "__algorithm/half_positive.h" }
       module includes                 { header "__algorithm/includes.h" }
       module inplace_merge            { header "__algorithm/inplace_merge.h" }
       module is_heap                  { header "__algorithm/is_heap.h" }
       module is_heap_until            { header "__algorithm/is_heap_until.h" }
-      module is_partitioned           { header "__algorithm/is_partitioned.h" }
+      module is_partitioned           {
+        header "__algorithm/is_partitioned.h"
+        export __function_like
+      }
       module is_permutation           { header "__algorithm/is_permutation.h" }
       module is_sorted                { header "__algorithm/is_sorted.h" }
       module is_sorted_until          { header "__algorithm/is_sorted_until.h" }
       module iter_swap                { header "__algorithm/iter_swap.h" }
       module lexicographical_compare  { header "__algorithm/lexicographical_compare.h" }
       module lower_bound              { header "__algorithm/lower_bound.h" }
       module make_heap                { header "__algorithm/make_heap.h" }
       module max                      { header "__algorithm/max.h" }
module __algorithm {
         header "__algorithm/none_of.h"
         export __function_like
       }
       module nth_element              { header "__algorithm/nth_element.h" }
       module partial_sort             { header "__algorithm/partial_sort.h" }
       module partial_sort_copy        { header "__algorithm/partial_sort_copy.h" }
       module partition                { header "__algorithm/partition.h" }
       module partition_copy           { header "__algorithm/partition_copy.h" }
-      module partition_point          { header "__algorithm/partition_point.h" }
+      module partition_point          {
+        header "__algorithm/partition_point.h"
+        export __function_like
+      }
       module pop_heap                 { header "__algorithm/pop_heap.h" }
       module prev_permutation         { header "__algorithm/prev_permutation.h" }
       module push_heap                { header "__algorithm/push_heap.h" }
       module remove                   { header "__algorithm/remove.h" }
       module remove_copy              { header "__algorithm/remove_copy.h" }
       module remove_copy_if           { header "__algorithm/remove_copy_if.h" }
       module remove_if                { header "__algorithm/remove_if.h" }
       module replace                  { header "__algorithm/replace.h" }

libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.pass.cpp

int main(int, char**) {
   ranges::find(arr, 1);
 
   ranges::find_if(ranges::begin(arr), ranges::end(arr), [](auto) { return true; });
   ranges::find_if(arr, [](auto) { return true; });
 
   ranges::find_if_not(ranges::begin(arr), ranges::end(arr), [](auto) { return true; });
   ranges::find_if_not(arr, [](auto) { return true; });
 
+  ranges::is_partitioned(ranges::begin(arr), ranges::end(arr), [](auto) { return true; });
+  ranges::is_partitioned(arr, [](auto) { return true; });
+
+  ranges::partition_point(ranges::begin(arr), ranges::end(arr), [](auto) { return true; });
+  ranges::partition_point(arr, [](auto) { return true; });
+
   return 0;
 }

libcxx/test/libcxx/diagnostics/nodiscard_ranges_extensions.verify.cpp

int main()
   // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
   ranges::find_if(arr, [](auto) { return true; });
 
   // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
   ranges::find_if_not(ranges::begin(arr), ranges::end(arr), [](auto) { return true; });
 
   // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
   ranges::find_if_not(arr, [](auto) { return true; });
+
+  // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
+  ranges::is_partitioned(ranges::begin(arr), ranges::end(arr), [](auto) { return true; });
+
+  // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
+  ranges::is_partitioned(arr, [](auto) { return true; });
+
+  // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
+  ranges::partition_point(ranges::begin(arr), ranges::end(arr), [](auto) { return true; });
+
+  // expected-warning-re@+1 {{ignoring return value of function declared with {{'nodiscard'|warn_unused_result}} attribute}}
+  ranges::partition_point(arr, [](auto) { return true; });
 }

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_is_partitioned/ranges_is_partitioned.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
+
+// <algorithm>
+
+// ranges::is_partition
+
+#include <algorithm>
+
+#include <array>
+#include <cassert>
+#include <functional>
+#include <ranges>
+
+#include "test_algorithm.h"
+#include "test_iterators.h"
+#include "test_macros.h"
+
+template<template<class...> class I, class T>
+constexpr bool check_is_partitioned() {
+  namespace ranges = std::ranges;
+
+  auto all_even = std::array{0, 2, 4, 6, 8};
+  auto all_odd = std::array{1, 3, 5, 7, 9};
+  auto odd_first = std::array{1, 3, 5, 7, 9, 0, 2, 4, 6, 8};
+  auto even_first = std::array{0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
+  auto no_partition = std::array{1, 3, 5, 9, 0, 2, 4, 6, 7, 8};
+
+  auto is_odd = [](T const x) { return static_cast<int>(x) % 2 != 0; };
+  auto successor = [](T const x) { return x + 1; };
+
+  {
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto range = ranges::subrange(I(all_odd.begin()), sentinel_wrapper(all_odd.end()));
+      assert(ranges::is_partitioned(range.begin(), range.end(), std::ref(pred)));
+      assert(pred.count() <= ranges::ssize(all_odd));
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto range = ranges::subrange(I(all_odd.begin()), sentinel_wrapper(all_odd.end()));
+      assert(ranges::is_partitioned(range, std::ref(pred)));
+      assert(pred.count() <= ranges::ssize(all_odd));
+    }
+  }
+  {
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto range = ranges::subrange(I(all_even.begin()), sentinel_wrapper(all_even.end()));
+      assert(ranges::is_partitioned(range.begin(), range.end(), std::ref(pred)));
+      assert(pred.count() <= ranges::ssize(all_even));
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto range = ranges::subrange(I(all_even.begin()), sentinel_wrapper(all_even.end()));
+      assert(ranges::is_partitioned(range, std::ref(pred)));
+      assert(pred.count() <= ranges::ssize(all_even));
+    }
+  }
+  {
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto range = ranges::subrange(I(odd_first.begin()), sentinel_wrapper(odd_first.end()));
+      assert(ranges::is_partitioned(range.begin(), range.end(), std::ref(pred)));
+      assert(pred.count() <= ranges::ssize(odd_first));
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto range = ranges::subrange(I(odd_first.begin()), sentinel_wrapper(odd_first.end()));
+      assert(ranges::is_partitioned(range, std::ref(pred)));
+      assert(pred.count() <= ranges::ssize(odd_first));
+    }
+  }
+  {
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto range = ranges::subrange(I(even_first.begin()), sentinel_wrapper(even_first.end()));
+      assert(!ranges::is_partitioned(range.begin(), range.end(), std::ref(pred)));
+      assert(pred.count() <= ranges::ssize(even_first));
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto range = ranges::subrange(I(even_first.begin()), sentinel_wrapper(even_first.end()));
+      assert(!ranges::is_partitioned(range, std::ref(pred)));
+      assert(pred.count() <= ranges::ssize(even_first));
+    }
+  }
+  {
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto range = ranges::subrange(I(no_partition.begin()), sentinel_wrapper(no_partition.end()));
+      assert(!ranges::is_partitioned(range.begin(), range.end(), std::ref(pred)));
+      assert(pred.count() <= ranges::ssize(no_partition));
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto range = ranges::subrange(I(no_partition.begin()), sentinel_wrapper(no_partition.end()));
+      assert(!ranges::is_partitioned(range, std::ref(pred)));
+      assert(pred.count() <= ranges::ssize(no_partition));
+    }
+  }
+  {
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto proj = complexity_invocable(successor);
+      auto range = ranges::subrange(I(all_odd.begin()), sentinel_wrapper(all_odd.end()));
+      assert(ranges::is_partitioned(range.begin(), range.end(), std::ref(pred), std::ref(proj)));
+      assert(pred.count() <= ranges::ssize(all_odd));
+      assert(proj.count() == pred.count());
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto proj = complexity_invocable(successor);
+      auto range = ranges::subrange(I(all_odd.begin()), sentinel_wrapper(all_odd.end()));
+      assert(ranges::is_partitioned(range, std::ref(pred), std::ref(proj)));
+      assert(pred.count() <= ranges::ssize(all_odd));
+      assert(proj.count() == pred.count());
+    }
+  }
+  {
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto proj = complexity_invocable(successor);
+      auto range = ranges::subrange(I(all_even.begin()), sentinel_wrapper(all_even.end()));
+      assert(ranges::is_partitioned(range.begin(), range.end(), std::ref(pred), std::ref(proj)));
+      assert(pred.count() <= ranges::ssize(all_even));
+      assert(proj.count() == pred.count());
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto proj = complexity_invocable(successor);
+      auto range = ranges::subrange(I(all_even.begin()), sentinel_wrapper(all_even.end()));
+      assert(ranges::is_partitioned(range, std::ref(pred), std::ref(proj)));
+      assert(pred.count() <= ranges::ssize(all_even));
+      assert(proj.count() == pred.count());
+    }
+  }
+  {
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto proj = complexity_invocable(successor);
+      auto range = ranges::subrange(I(odd_first.begin()), sentinel_wrapper(odd_first.end()));
+      assert(!ranges::is_partitioned(range.begin(), range.end(), std::ref(pred), std::ref(proj)));
+      assert(pred.count() <= ranges::ssize(odd_first));
+      assert(proj.count() == pred.count());
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto proj = complexity_invocable(successor);
+      auto range = ranges::subrange(I(odd_first.begin()), sentinel_wrapper(odd_first.end()));
+      assert(!ranges::is_partitioned(range, std::ref(pred), std::ref(proj)));
+      assert(pred.count() <= ranges::ssize(odd_first));
+      assert(proj.count() == pred.count());
+    }
+  }
+  {
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto proj = complexity_invocable(successor);
+      auto range = ranges::subrange(I(even_first.begin()), sentinel_wrapper(even_first.end()));
+      assert(ranges::is_partitioned(range.begin(), range.end(), std::ref(pred), std::ref(proj)));
+      assert(pred.count() <= ranges::ssize(even_first));
+      assert(proj.count() == pred.count());
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto proj = complexity_invocable(successor);
+      auto range = ranges::subrange(I(even_first.begin()), sentinel_wrapper(even_first.end()));
+      assert(ranges::is_partitioned(range, std::ref(pred), std::ref(proj)));
+      assert(pred.count() <= ranges::ssize(even_first));
+      assert(proj.count() == pred.count());
+    }
+  }
+  {
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto proj = complexity_invocable(successor);
+      auto range = ranges::subrange(I(no_partition.begin()), sentinel_wrapper(no_partition.end()));
+      assert(!ranges::is_partitioned(range.begin(), range.end(), std::ref(pred), std::ref(proj)));
+      assert(pred.count() <= ranges::ssize(no_partition));
+      assert(proj.count() == pred.count());
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto proj = complexity_invocable(successor);
+      auto range = ranges::subrange(I(no_partition.begin()), sentinel_wrapper(no_partition.end()));
+      assert(!ranges::is_partitioned(range, std::ref(pred), std::ref(proj)));
+      assert(pred.count() <= ranges::ssize(no_partition));
+      assert(proj.count() == pred.count());
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  static_assert(check_is_partitioned<cpp17_input_iterator, int>());
+  static_assert(check_is_partitioned<cpp17_input_iterator, double>());
+  check_is_partitioned<cpp17_input_iterator, int>();
+  check_is_partitioned<cpp17_input_iterator, double>();
+
+  static_assert(check_is_partitioned<cpp20_input_iterator, int>());
+  static_assert(check_is_partitioned<cpp20_input_iterator, double>());
+  check_is_partitioned<cpp20_input_iterator, int>();
+  check_is_partitioned<cpp20_input_iterator, double>();
+
+  static_assert(check_is_partitioned<forward_iterator, int>());
+  static_assert(check_is_partitioned<forward_iterator, double>());
+  check_is_partitioned<forward_iterator, int>();
+  check_is_partitioned<forward_iterator, double>();
+
+  static_assert(check_is_partitioned<bidirectional_iterator, int>());
+  static_assert(check_is_partitioned<bidirectional_iterator, double>());
+  check_is_partitioned<bidirectional_iterator, int>();
+  check_is_partitioned<bidirectional_iterator, double>();
+
+  static_assert(check_is_partitioned<random_access_iterator, int>());
+  static_assert(check_is_partitioned<random_access_iterator, double>());
+  check_is_partitioned<random_access_iterator, int>();
+  check_is_partitioned<random_access_iterator, double>();
+
+  static_assert(check_is_partitioned<contiguous_iterator, int>());
+  static_assert(check_is_partitioned<contiguous_iterator, double>());
+  check_is_partitioned<contiguous_iterator, int>();
+  check_is_partitioned<contiguous_iterator, double>();
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_is_partitioned/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::is_partitioned
+
+#include <algorithm>
+
+#include <array>
+#include <iterator>
+#include <ranges>
+#include <utility>
+
+#include "test_range.h"
+#include "test_standard_function.h"
+
+static_assert(is_function_like<decltype(std::ranges::is_partitioned)>());
+
+namespace ranges = std::ranges;
+
+namespace std::ranges {
+  template<class T>
+  class basic_istream_view {
+    struct iterator;
+  public:
+    iterator begin();
+    default_sentinel_t end() const;
+  };
+} // namespace std::ranges
+
+auto f = [](auto) { return true; };
+
+// The entities defined in the std::ranges namespace in this Clause are not found by argument-dependent
+// name lookup ([basic.lookup.argdep]). 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.
+template <class T>
+constexpr bool no_unqualified_lookup() {
+  auto identity = ranges::basic_istream_view<T>();
+  static_assert(!requires { is_partitioned(ranges::begin(identity), ranges::end(identity), f); });
+  static_assert(!requires { is_partitioned(ranges::begin(identity), ranges::end(identity), f, &T::first); });
+  static_assert(!requires { is_partitioned(identity, f); });
+  static_assert(!requires { is_partitioned(identity, f, &T::first); });
+  return true;
+};
+
+static_assert(no_unqualified_lookup<std::pair<int, int>>());
+
+namespace test {
+template <class>
+struct iterator {
+  using value_type = std::pair<int, int>;
+  using difference_type = std::ptrdiff_t;
+  using iterator_category = std::forward_iterator_tag;
+
+  iterator() = default;
+
+  value_type operator*() const;
+  iterator& operator++();
+  iterator operator++(int);
+
+  bool operator==(iterator const&) const = default;
+};
+
+template<class>
+struct range {
+  std::pair<int, int> const* begin() const;
+  std::pair<int, int> const* end() const;
+};
+
+template <class I>
+void is_partitioned(iterator<I>, iterator<I>, auto) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class I>
+void is_partitioned(iterator<I>, iterator<I>, auto, auto) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class R>
+void is_partitioned(R&&, auto) {
+  static_assert(std::same_as<R, R*>);
+}
+
+template <class R>
+void is_partitioned(R&&, auto, auto) {
+  static_assert(std::same_as<R, R*>);
+}
+} // namespace test
+
+// When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a
+// function call ([expr.call]), they inhibit argument-dependent name lookup.
+void adl_inhibition() {
+  using std::ranges::is_partitioned;
+
+  test::iterator<std::pair<int, int>*> x;
+  (void)is_partitioned(x, x, f);
+  (void)is_partitioned(x, x, f, &std::pair<int, int>::first);
+
+  test::range<int*> r;
+  (void)is_partitioned(r, f);
+  (void)is_partitioned(r, f, &std::pair<int, int>::first);
+}

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_point/ranges_partition_point.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::partition_point
+
+#include <algorithm>
+
+#include <array>
+#include <cassert>
+#include <functional>
+#include <ranges>
+#include <vector>
+
+#include "test_algorithm.h"
+#include "test_iterators.h"
+#include "test_macros.h"
+
+template<template<class...> class I, class T>
+constexpr bool check_partition_point() {
+  namespace ranges = std::ranges;
+
+  auto all_odd = std::array{1, 3, 5, 7, 9};
+  auto all_even = std::array{0, 2, 4, 6, 8};
+  auto odd_first = std::array{1, 3, 5, 7, 9, 0, 2, 4, 6, 8};
+  auto even_first = std::array{0, 2, 4, 6, 8, 1, 3, 5, 7, 9};
+
+  auto is_odd = [](T const x) { return static_cast<int>(x) % 2 != 0; };
+  auto successor = [](T const x) { return x + 1; };
+
+  {
+    auto const range = ranges::subrange(I(all_odd.begin()), sentinel_wrapper(all_odd.end()));
+    {
+      auto pred = complexity_invocable(is_odd);
+      assert(ranges::partition_point(range.begin(), range.end(), std::ref(pred)) == range.end());
+      assert(pred.count() == 2);
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      assert(ranges::partition_point(range, std::ref(pred)) == range.end());
+      assert(pred.count() == 2);
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto proj = complexity_invocable(successor);
+      assert(ranges::partition_point(range.begin(), range.end(), std::ref(pred), std::ref(proj)) == range.begin());
+      assert(pred.count() == 3);
+      assert(proj.count() == 3);
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto proj = complexity_invocable(successor);
+      assert(ranges::partition_point(range, std::ref(pred), std::ref(proj)) == range.begin());
+      assert(pred.count() == 3);
+      assert(proj.count() == 3);
+    }
+  }
+  {
+    auto const range = ranges::subrange(I(all_even.begin()), sentinel_wrapper(all_even.end()));
+
+    {
+      auto pred = complexity_invocable(is_odd);
+      assert(ranges::partition_point(range.begin(), range.end(), std::ref(pred)) == range.begin());
+      assert(pred.count() == 3);
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      assert(ranges::partition_point(range, std::ref(pred)) == range.begin());
+      assert(pred.count() == 3);
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto proj = complexity_invocable(successor);
+      assert(ranges::partition_point(range.begin(), range.end(), std::ref(pred), std::ref(proj)) == range.end());
+      assert(pred.count() == 2);
+      assert(proj.count() == 2);
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto proj = complexity_invocable(successor);
+      assert(ranges::partition_point(range, std::ref(pred), std::ref(proj)) == range.end());
+      assert(pred.count() == 2);
+      assert(proj.count() == 2);
+    }
+  }
+  {
+    auto const range = ranges::subrange(I(odd_first.begin()), sentinel_wrapper(odd_first.end()));
+
+    {
+      auto pred = complexity_invocable(is_odd);
+      assert(ranges::partition_point(range.begin(), range.end(), std::ref(pred)).base() == odd_first.begin() + 5);
+      assert(pred.count() == 3);
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      assert(ranges::partition_point(range, std::ref(pred)).base() == odd_first.begin() + 5);
+      assert(pred.count() == 3);
+    }
+  }
+  {
+    auto const range = ranges::subrange(I(even_first.begin()), sentinel_wrapper(even_first.end()));
+
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto proj = complexity_invocable(successor);
+      assert(ranges::partition_point(range.begin(), range.end(), std::ref(pred), std::ref(proj)).base() == even_first.begin() + 5);
+      assert(pred.count() == 3);
+      assert(proj.count() == 3);
+    }
+    {
+      auto pred = complexity_invocable(is_odd);
+      auto proj = complexity_invocable(successor);
+      assert(ranges::partition_point(range, std::ref(pred), std::ref(proj)).base() == even_first.begin() + 5);
+      assert(pred.count() == 3);
+      assert(proj.count() == 3);
+    }
+  }
+  {
+    ASSERT_SAME_TYPE(decltype(ranges::partition_point(std::vector(all_odd.begin(), all_odd.end()), is_odd)),
+                     ranges::dangling);
+    ASSERT_SAME_TYPE(decltype(ranges::partition_point(std::vector(all_odd.begin(), all_odd.end()), is_odd, successor)),
+                     ranges::dangling);
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  static_assert(check_partition_point<forward_iterator, int>());
+  static_assert(check_partition_point<forward_iterator, double>());
+  check_partition_point<forward_iterator, int>();
+  check_partition_point<forward_iterator, double>();
+
+  static_assert(check_partition_point<bidirectional_iterator, int>());
+  static_assert(check_partition_point<bidirectional_iterator, double>());
+  check_partition_point<bidirectional_iterator, int>();
+  check_partition_point<bidirectional_iterator, double>();
+
+  static_assert(check_partition_point<random_access_iterator, int>());
+  static_assert(check_partition_point<random_access_iterator, double>());
+  check_partition_point<random_access_iterator, int>();
+  check_partition_point<random_access_iterator, double>();
+
+  static_assert(check_partition_point<contiguous_iterator, int>());
+  static_assert(check_partition_point<contiguous_iterator, double>());
+  check_partition_point<contiguous_iterator, int>();
+  check_partition_point<contiguous_iterator, double>();
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/ranges_partition_point/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::partition_point
+
+#include <algorithm>
+
+#include <array>
+#include <iterator>
+#include <ranges>
+#include <utility>
+
+#include "test_range.h"
+#include "test_standard_function.h"
+
+static_assert(is_function_like<decltype(std::ranges::partition_point)>());
+
+namespace ranges = std::ranges;
+
+namespace std::ranges {
+  template<class T>
+  class basic_istream_view {
+    struct iterator;
+  public:
+    iterator begin();
+    default_sentinel_t end() const;
+  };
+} // namespace std::ranges
+
+auto f = [](auto) { return true; };
+
+// The entities defined in the std::ranges namespace in this Clause are not found by argument-dependent
+// name lookup ([basic.lookup.argdep]). 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.
+template <class T>
+constexpr bool no_unqualified_lookup() {
+  auto identity = ranges::basic_istream_view<T>();
+  static_assert(!requires { partition_point(ranges::begin(identity), ranges::end(identity), f); });
+  static_assert(!requires { partition_point(ranges::begin(identity), ranges::end(identity), f, &T::first); });
+  static_assert(!requires { partition_point(identity, f); });
+  static_assert(!requires { partition_point(identity, f, &T::first); });
+  return true;
+};
+
+static_assert(no_unqualified_lookup<std::pair<int, int>>());
+
+namespace test {
+template <class>
+struct iterator {
+  using value_type = std::pair<int, int>;
+  using difference_type = std::ptrdiff_t;
+  using iterator_category = std::forward_iterator_tag;
+
+  iterator() = default;
+
+  value_type operator*() const;
+  iterator& operator++();
+  iterator operator++(int);
+
+  bool operator==(iterator const&) const = default;
+};
+
+template<class>
+struct range {
+  std::pair<int, int> const* begin() const;
+  std::pair<int, int> const* end() const;
+};
+
+template <class I>
+void partition_point(iterator<I>, iterator<I>, auto) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class I>
+void partition_point(iterator<I>, iterator<I>, auto, auto) {
+  static_assert(std::same_as<I, I*>);
+}
+
+template <class R>
+void partition_point(R&&, auto) {
+  static_assert(std::same_as<R, R*>);
+}
+
+template <class R>
+void partition_point(R&&, auto, auto) {
+  static_assert(std::same_as<R, R*>);
+}
+} // namespace test
+
+// When found by unqualified ([basic.lookup.unqual]) name lookup for the postfix-expression in a
+// function call ([expr.call]), they inhibit argument-dependent name lookup.
+void adl_inhibition() {
+  using std::ranges::partition_point;
+
+  test::iterator<std::pair<int, int>*> x;
+  (void)partition_point(x, x, f);
+  (void)partition_point(x, x, f, &std::pair<int, int>::first);
+
+  test::range<int*> r;
+  (void)partition_point(r, f);
+  (void)partition_point(r, f, &std::pair<int, int>::first);
+}