[libc++][PSTL] Implement std::is_partitioned

[philnik]

Update documentations

[philnik]

Try to fix CI

[ldionne]

libcxx/include/__algorithm/pstl_is_partitioned.h

42

You forgot to pass the policy to the find_if call.

Also, this could be std::none_of(__policy, __g_first, __g_last, __g_pred);.

libcxx/test/std/algorithms/alg.sorting/alg.partitions/pstl.is_partitioned.pass.cpp

28

You're missing a test that is_partition(empty-range) is true.

33

paritioned => partitioned. You probably want to search and replace globally, I can see other instances of this. You also have a few parititoned around.

45

I think this comment is incomplete

[philnik]

Address comments

libcxx/test/std/algorithms/alg.sorting/alg.partitions/pstl.is_partitioned.pass.cpp

45

This is the empty range test.

[ldionne]

LGTM w/ fix and test

libcxx/include/__algorithm/pstl_is_partitioned.h

42–43

Technically, I think we could implement it this way instead:

__g_first = std::find_if_not(__policy, __g_first, __g_last, __g_pred);
if (__g_first == __g_last)
  return true;
++__g_first;
return std::none_of(__policy, __g_first, __g_last, __g_pred);

This way, we avoid running the predicate twice on the first element that doesn't satisfy the predicate (which we do right now). This also mirrors what we do for the serial version of the algorithm. If you agree, I think it might be useful to add a test for this. In particular, we could have a libc++ specific test that ensures that we satisfy this complexity guarantee (from the serial version):

At most std::distance(first, last) applications of p.

Could you also take a look at whether this is tested in the serial version, where that's definitely a requirement?

libcxx/docs/Status/PSTLPaper.csv

 | `[alg.foreach] <https://wg21.link/alg.foreach>`_,std::for_each_n,Nikolas Klauser,|Complete|
 | `[alg.generate] <https://wg21.link/alg.generate>`_,std::generate,Nikolas Klauser,|Complete|
 | `[alg.generate] <https://wg21.link/alg.generate>`_,std::generate_n,Nikolas Klauser,|Complete|
 | `[alg.set.operations] <https://wg21.link/alg.set.operations>`_,std::includes,Nikolas Klauser,|Not Started|
 | `[alg.inclusive.scan] <https://wg21.link/alg.inclusive.scan>`_,std::inclusive_scan,Nikolas Klauser,|Not Started|
 | `[alg.merge] <https://wg21.link/alg.merge>`_,std::inplace_merge,Nikolas Klauser,|Not Started|
 | `[alg.heap.operations] <https://wg21.link/alg.heap.operations>`_,std::is_heap,Nikolas Klauser,|Not Started|
 | `[alg.heap.operations] <https://wg21.link/alg.heap.operations>`_,std::is_heap_until,Nikolas Klauser,|Not Started|
-| `[alg.partitions] <https://wg21.link/alg.partitions>`_,std::is_partitioned,Nikolas Klauser,|Not Started|
+| `[alg.partitions] <https://wg21.link/alg.partitions>`_,std::is_partitioned,Nikolas Klauser,|Complete|
 | `[alg.sort] <https://wg21.link/alg.sort>`_,std::is_sorted,Nikolas Klauser,|Not Started|
 | `[alg.sort] <https://wg21.link/alg.sort>`_,std::is_sorted_until,Nikolas Klauser,|Not Started|
 | `[alg.lex.comparison] <https://wg21.link/alg.lex.comparison>`_,std::lexicographical_compare,Nikolas Klauser,|Not Started|
 | `[alg.min.max] <https://wg21.link/alg.min.max>`_,std::max_element,Nikolas Klauser,|Not Started|
 | `[alg.merge] <https://wg21.link/alg.merge>`_,std::merge,Nikolas Klauser,|Not Started|
 | `[alg.min.max] <https://wg21.link/alg.min.max>`_,std::min_element,Nikolas Klauser,|Not Started|
 | `[alg.min.max] <https://wg21.link/alg.min.max>`_,std::minmax_element,Nikolas Klauser,|Not Started|
 | `[mismatch] <https://wg21.link/mismatch>`_,std::mismatch,Nikolas Klauser,|Not Started|

libcxx/include/CMakeLists.txt

set(files
   __algorithm/pstl_backends/cpu_backends/transform_reduce.h
   __algorithm/pstl_copy.h
   __algorithm/pstl_count.h
   __algorithm/pstl_fill.h
   __algorithm/pstl_find.h
   __algorithm/pstl_for_each.h
   __algorithm/pstl_frontend_dispatch.h
   __algorithm/pstl_generate.h
+  __algorithm/pstl_is_partitioned.h
   __algorithm/pstl_merge.h
   __algorithm/pstl_replace.h
   __algorithm/pstl_stable_sort.h
   __algorithm/pstl_transform.h
   __algorithm/push_heap.h
   __algorithm/ranges_adjacent_find.h
   __algorithm/ranges_all_of.h
   __algorithm/ranges_any_of.h

libcxx/include/__algorithm/pstl_backend.h

implemented, all the algorithms will eventually forward to the basis algorithms listed above:
   void __pstl_fill(_Backend, _Iterator __first, _Iterator __last, const _Tp& __value);
 
   template <class _ExecutionPolicy, class _Iterator, class _SizeT, class _Tp>
   void __pstl_fill_n(_Backend, _Iterator __first, _SizeT __n, const _Tp& __value);
 
   template <class _ExecutionPolicy, class _Iterator, class _Generator>
   void __pstl_generate(_Backend, _Iterator __first, _Iterator __last, _Generator __gen);
 
+  template <class _ExecutionPolicy, class _Iterator, class _Predicate>
+  void __pstl_is_partitioned(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred);
+
   template <class _ExecutionPolicy, class _Iterator, class _Size, class _Generator>
   void __pstl_generator_n(_Backend, _Iterator __first, _Size __n, _Generator __gen);
 
   template <class _ExecutionPolicy, class _terator1, class _Iterator2, class _OutIterator, class _Comp>
   _OutIterator __pstl_merge(_Backend,
                             _Iterator1 __first1,
                             _Iterator1 __last1,
                             _Iterator2 __first2,

libcxx/include/__algorithm/pstl_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_PSTL_IS_PARITTIONED
+#define _LIBCPP___ALGORITHM_PSTL_IS_PARITTIONED
+
+#include <__algorithm/pstl_any_all_none_of.h>
+#include <__algorithm/pstl_backend.h>
+#include <__algorithm/pstl_find.h>
+#include <__algorithm/pstl_frontend_dispatch.h>
+#include <__config>
+#include <__type_traits/is_execution_policy.h>
+#include <__type_traits/remove_cvref.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <class>
+void __pstl_is_partitioned();
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Predicate,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool
+is_partitioned(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
+  return std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_is_partitioned),
+      [&__policy](_ForwardIterator __g_first, _ForwardIterator __g_last, _Predicate __g_pred) {
+        __g_first = std::find_if_not(__policy, __g_first, __g_last, __g_pred);
+        if (__g_first == __g_last)
+          return true;
+        ++__g_first;
+        return std::none_of(__policy, __g_first, __g_last, __g_pred);
+      },
+      std::move(__first),
+      std::move(__last),
+      std::move(__pred));
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_IS_PARITTIONED

libcxx/include/algorithm

 #include <__algorithm/prev_permutation.h>
 #include <__algorithm/pstl_any_all_none_of.h>
 #include <__algorithm/pstl_copy.h>
 #include <__algorithm/pstl_count.h>
 #include <__algorithm/pstl_fill.h>
 #include <__algorithm/pstl_find.h>
 #include <__algorithm/pstl_for_each.h>
 #include <__algorithm/pstl_generate.h>
+#include <__algorithm/pstl_is_partitioned.h>
 #include <__algorithm/pstl_merge.h>
 #include <__algorithm/pstl_replace.h>
 #include <__algorithm/pstl_stable_sort.h>
 #include <__algorithm/pstl_transform.h>
 #include <__algorithm/push_heap.h>
 #include <__algorithm/ranges_adjacent_find.h>
 #include <__algorithm/ranges_all_of.h>
 #include <__algorithm/ranges_any_of.h>

libcxx/test/libcxx/algorithms/alg.sorting/pstl.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
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// Make sure that the predicate is called exactly N times in is_partitioned
+
+#include <algorithm>
+#include <cassert>
+#include <execution>
+#include <iterator>
+
+int main(int, char**) {
+  int call_count = 0;
+  int a[]        = {1, 2, 3, 4, 5, 6, 7, 8};
+  assert(std::is_partitioned(std::execution::seq, std::begin(a), std::end(a), [&](int i) {
+    ++call_count;
+    return i < 5;
+  }));
+  assert(call_count == std::size(a));
+}

libcxx/test/libcxx/algorithms/pstl.robust_against_customization_points_not_working.pass.cpp

 bool pstl_fill_n_called = false;
 
 template <class, class ForwardIterator, class Size, class Func>
 void __pstl_fill_n(TestBackend, ForwardIterator, Size, Func) {
   assert(!pstl_fill_n_called);
   pstl_fill_n_called = true;
 }
 
+bool pstl_is_partitioned_called = false;
+
+template <class, class ForwardIterator, class Func>
+bool __pstl_is_partitioned(TestBackend, ForwardIterator, ForwardIterator, Func) {
+  assert(!pstl_is_partitioned_called);
+  pstl_is_partitioned_called = true;
+  return {};
+}
+
 bool pstl_replace_called = false;
 
 template <class, class ForwardIterator, class T>
 void __pstl_replace(TestBackend, ForwardIterator, ForwardIterator, const T&, const T&) {
   assert(!pstl_replace_called);
   pstl_replace_called = true;
 }
 
int main(int, char**) {
   (void)std::for_each(TestPolicy{}, std::begin(a), std::end(a), pred);
   assert(std::pstl_for_each_called);
   (void)std::for_each_n(TestPolicy{}, std::begin(a), std::size(a), pred);
   assert(std::pstl_for_each_n_called);
   (void)std::generate(TestPolicy{}, std::begin(a), std::end(a), pred);
   assert(std::pstl_generate_called);
   (void)std::generate_n(TestPolicy{}, std::begin(a), std::size(a), pred);
   assert(std::pstl_generate_n_called);
+  (void)std::is_partitioned(TestPolicy{}, std::begin(a), std::end(a), pred);
+  assert(std::pstl_generate_n_called);
   (void)std::replace(TestPolicy{}, std::begin(a), std::end(a), 0, 0);
   assert(std::pstl_replace_called);
   (void)std::replace_if(TestPolicy{}, std::begin(a), std::end(a), pred, 0);
   assert(std::pstl_replace_if_called);
   (void)std::replace_copy(TestPolicy{}, std::begin(a), std::end(a), std::begin(a), 0, 0);
   assert(std::pstl_replace_copy_called);
   (void)std::replace_copy_if(TestPolicy{}, std::begin(a), std::end(a), std::begin(a), pred, 0);
   assert(std::pstl_replace_copy_if_called);

libcxx/test/std/algorithms/alg.sorting/alg.partitions/pstl.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
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// template<class ExecutionPolicy, class ForwardIterator, class Predicate>
+//   bool is_partitioned(ExecutionPolicy&& exec,
+//                       ForwardIterator first, ForwardIterator last, Predicate pred);
+
+#include <algorithm>
+#include <cassert>
+#include <vector>
+
+#include "test_iterators.h"
+#include "test_execution_policies.h"
+
+template <class Iter>
+struct Test {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    { // simple test
+      int a[] = {1, 2, 3, 4, 5};
+      assert(std::is_partitioned(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i < 3; }));
+    }
+    { // check that the range is partitioned if the predicate returns true for all elements
+      int a[] = {1, 2, 3, 4, 5};
+      assert(std::is_partitioned(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int) { return true; }));
+    }
+    { // check that the range is partitioned if the predicate returns false for all elements
+      int a[] = {1, 2, 3, 4, 5};
+      assert(std::is_partitioned(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int) { return false; }));
+    }
+    { // check that false is returned if the range is not partitioned
+      int a[] = {1, 2, 3, 2, 5};
+      assert(!std::is_partitioned(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i < 3; }));
+    }
+    { // check that an empty range is partitioned
+      int a[] = {1, 2, 3, 2, 5};
+      assert(std::is_partitioned(policy, Iter(std::begin(a)), Iter(std::begin(a)), [](int i) { return i < 3; }));
+    }
+    { // check that a single element is partitioned
+      int a[] = {1};
+      assert(std::is_partitioned(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i < 3; }));
+    }
+    { // check that a range is partitioned when the partition point is the first element
+      int a[] = {1, 2, 2, 4, 5};
+      assert(std::is_partitioned(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i < 2; }));
+    }
+    { // check that a range is partitioned when the partition point is the last element
+      int a[] = {1, 2, 2, 4, 5};
+      assert(std::is_partitioned(policy, Iter(std::begin(a)), Iter(std::end(a)), [](int i) { return i < 2; }));
+    }
+    { // check that a large range works
+      std::vector<int> vec(150, 4);
+      vec[0] = 2;
+      vec[1] = 1;
+      assert(std::is_partitioned(policy, Iter(std::data(vec)), Iter(std::data(vec) + std::size(vec)), [](int i) {
+        return i < 3;
+      }));
+    }
+  }
+};
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
+
+  return 0;
+}