[libc++][PSTL] Overhaul exceptions handling

[philnik]

Summary

This makes exception handling a lot simpler, since we don't have to convert any exceptions this way. Is also properly handles all the user-thrown exceptions.

[ldionne]

libcxx/include/__algorithm/pstl_backends/cpu_backends/any_of.h

66

We should document how backends are expected to handle exceptions in libcxx/include/__algorithm/pstl_backend.h and in libcxx/include/__algorithm/pstl_backends/cpu_backend.h.

libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h

97

Notes from our 1:1 session:

// Option 1:
// Pros:
// - CPU sub-backends don't have to handle user exceptions in any special way. They only have to care
//   about any exception that might be thrown in their own setup code (aka std::bad_alloc).
// - Handling of excetpions at the `__pstl_foo` level is uniform across all algorithms.
// - We can write all code inside the PSTL with the mindset that exceptions are disabled,
//   i.e. we never throw and we use appropriate types to report errors instead. This might be
//   a nice systematic approach?
// Cons:
// - Requires introducing a custom std::expected-like type for internal use.
// - Hardcodes the fact that we can only throw `std::bad_alloc` from backends.
// - We can't elide the move construction of the return value out of `__pstl_find_if`.
template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
_LIBCPP_HIDE_FROM_ABI _ForwardIterator
__pstl_find_if(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
  auto __maybe_result = std::__terminate_on_exception([&] -> __funky_expected<_ForwardIterator, std::bad_alloc> {
    if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
                  __has_random_access_iterator_category<_ForwardIterator>::value) {
      return std::__parallel_find(
          __first,
          __last,
          [&__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
            return std::__pstl_find_if<__remove_parallel_policy_t<_ExecutionPolicy>>(
                __cpu_backend_tag{}, __brick_first, __brick_last, __pred);
          },
          less<>{},
          true);
    } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
                        __has_random_access_iterator_category<_ForwardIterator>::value) {
      using __diff_t = __iter_diff_t<_ForwardIterator>;
      return std::__simd_first(__first, __diff_t(0), __last - __first, [&__pred](_ForwardIterator __iter, __diff_t __i) {
        return __pred(__iter[__i]);
      });
    } else {
      return std::find_if(__first, __last, __pred);
    }
  });
  return *std::move(__maybe_result).or_else([](auto&& __exception) -> __funky_expected<_ForwardIterator, void> { std::__throw_bad_alloc(); });
}

// Option 2:
// Pros:
// - Each layer fully handles all of its exceptions independently. That can be simpler or more complicated depending
//   on how you look at it.
// Cons:
// - When you're writing a CPU backend, you need to explicitly handle user-thrown exceptions and carve out the
//   setup-thrown exceptions from the `terminate_on_exception` code paths.
template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
_LIBCPP_HIDE_FROM_ABI _ForwardIterator
__pstl_find_if(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
  if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
                __has_random_access_iterator_category<_ForwardIterator>::value) {
    return std::__parallel_find( // we would document that CPU sub-backends need to handle exceptions appropriately
        __first,
        __last,
        [&__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
          return std::__pstl_find_if<__remove_parallel_policy_t<_ExecutionPolicy>>(
              __cpu_backend_tag{}, __brick_first, __brick_last, __pred);
        },
        less<>{},
        true);
  } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
                      __has_random_access_iterator_category<_ForwardIterator>::value) {
    using __diff_t = __iter_diff_t<_ForwardIterator>;
    return std::__terminate_on_exception([&] {
      return std::__simd_first(__first, __diff_t(0), __last - __first, [&__pred](_ForwardIterator __iter, __diff_t __i) {
        return __pred(__iter[__i]);
      });
    });
  } else {
    return std::__terminate_on_exception([&] {
      return std::find_if(__first, __last, __pred);
    });
  }
}

At the end, we both agreed that option 2 is the way to go for now, largely because implementing an expected-like type in C++17 drives the cost of option 1 up a lot.

116–118

If an exception is thrown in here, we would also need to terminate. This needs to be fixed + a test.

120

If an exception is thrown in here, we should also terminate even though this is actually running serial. This needs fix + tests.

[philnik]

Address comments

[ldionne]

libcxx/include/__algorithm/pstl_backend.h

166–167

And also below.

libcxx/include/__algorithm/pstl_backends/cpu_backend.h

52

libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill.pass.cpp

27

This include is not necessary.

libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill.terminate.pass.cpp

30 ↗

(On Diff #537895)

Can we also test iterators that throw when some operation (e.g. increment) is applied to them? I think this might catch issues in backends when they e.g. compute the size of the range. For this algorithms but others as well.

Or throwing on copy of the iterator.

Actually, this raises the question of how to handle throwing iterators at all. I think this approach doesn't work, since an iterator could technically throw even in one of the frontend functions. It's possible that the only approach that will work is to actually make the top-level function noexcept (but still throw std::bad_alloc in a few cases).

[philnik]

Use an expected type

[ldionne]

libcxx/include/__algorithm/pstl_backends/cpu_backends/libdispatch.h

103

noexcept?

141–142

We don't need __terminate_on_exception anymore here.

libcxx/include/__algorithm/pstl_backends/cpu_backends/merge.h

40

noexcept?

libcxx/include/__algorithm/pstl_backends/pstl_expected.h

1 ↗

(On Diff #548302)

As discussed, let's go for std::optional. It handles triviality properly and it resolves a lot of complexity that we run into if we try to do expected.

libcxx/include/__algorithm/pstl_merge.h

77–80

We need a test that we behave properly if the iterators throw when they are moved here.

Also note that it would be possible to pass by rvalue ref into __pstl_merge and drop __terminate_on_exception altogether here (and in fact I don't think we'd need it anywhere anymore, which would be great). But I'm neutral on that, what I care about most is to add tests for this.

libcxx/include/__numeric/pstl_transform_reduce.h

78–82

Same thing for moving iterators applies here.

88

This could be:

*std::__terminate_on_exception(...).or_else([]{ std::__throw_bad_alloc(); });

We only need to use some pre-C++23 or_else version.

[philnik]

Address comments

[ldionne]

libcxx/include/__algorithm/pstl_backend.h

80

These should be updated for optional<foo>

167

a disengaged optional. Same below.

[ldionne]

libcxx/include/__algorithm/pstl_backends/cpu_backend.h

52

Actually, I think we want to say:

CPU backends are expected to report errors (i.e. failure to allocate) by returning a disengaged `optional` from their implementation. Exceptions shouldn't be used to report an internal failure-to-allocate, since all exceptions are turned into a program termination at the front-end level. When a backend returns a disengaged `optional` to the frontend, the frontend will turn that into a call to `std::__throw_bad_alloc();` to report the internal failure to the user.

libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h

106

Let's add an internal assertion here to document why __pstl_find_if will never return nullopt (the reason is that unseq isn't allowed to allocate, assuming that's true).

If that's not true, then this is a bug.

libcxx/include/__algorithm/pstl_backends/cpu_backends/libdispatch.h

66

Per our discussion just now, we should actually remove noexcept here!

libcxx/include/__algorithm/pstl_backends/cpu_backends/transform_reduce.h

166

Same, internal assertion.

libcxx/include/__algorithm/pstl_for_each.h

65–66

As discussed, it looks like we actually need to do this (otherwise we'd terminate in case std::for_each(policy, ...) throws bad_alloc):

template <class _ExecutionPolicy,
          class _ForwardIterator,
          class _Size,
          class _Function,
          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
_LIBCPP_HIDE_FROM_ABI void
__for_each_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __size, _Function __func) noexcept {
  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
  return std::__pstl_frontend_dispatch(
      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_for_each_n),
      [&](_ForwardIterator __g_first, _Size __g_size, _Function __g_func) -> optional<__empty> {
        if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
          std::for_each(__policy, std::move(__g_first), __g_first + __g_size, std::move(__g_func));
          return __empty{};
        } else {
          std::for_each_n(std::move(__g_first), __g_size, std::move(__g_func));
          return __empty{};
        }
      },
      __first,
      __size,
      std::move(__func));
}

template <class _ExecutionPolicy,
          class _ForwardIterator,
          class _Size,
          class _Function,
          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
_LIBCPP_HIDE_FROM_ABI void
for_each_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __size, _Function __func) {
  auto __res = std::__for_each_n(...);
  if (!__res)
    std::__throw_bad_alloc();
}

And then we should use the noexcept version from fallback implementations.

libcxx/include/__utility/terminate_on_exception.h

0

I think this is just not needed at all anymore.

[philnik]

Address comments

[ldionne]

libcxx/include/__algorithm/pstl_any_all_none_of.h

14

Missing <optional> include. Please make a pass throughout.

libcxx/include/__algorithm/pstl_backends/cpu_backends/any_of.h

22–23

<__utility/move.h>

libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h

36

This seems like a leftover, we decided to only mark the top-level __find algo noexcept.

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.h

38

noexcept leftover

libcxx/include/__algorithm/pstl_backends/cpu_backends/transform.h

45

noexcept leftover

92

noexcept leftover

libcxx/include/__algorithm/pstl_is_partitioned.h

61

In another patch, can you please make a pass to make sure you're not missing _LLIBCPP_REQUIRE_CPP17_FOO from any of them?

libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill.terminate.pass.cpp

1 ↗

(On Diff #548774)

Let's name this test pstl.exception_handling.pass.cpp since this isn't only specific to std::fill. WDYT?

13 ↗

(On Diff #548774)

You can adjust all the comments

13 ↗

(On Diff #548774)

Also you should mention that you're testing std::fill_n here (this applies to all these tests).

40 ↗

(On Diff #548774)

everywhere

43 ↗

(On Diff #548774)

Please add a comment like // test std::fill_n to separate each algorithm you're testing. This is kinda dumb here cause there's 2, but when there's more it's useful to have a visual marker

libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/pstl.for_each.terminate.pass.cpp

1 ↗

(On Diff #548774)

I think you need to UNSUPPORT these tests when -fno-exceptions

[philnik]

Address comments

[ldionne]

LGTM, thanks!

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Fix formatting

[philnik]

Try to fix CI

[philnik]

Rebased

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CTry to fix CII

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

• Rebased
• Run the full pipeline

[philnik]

Try to fix CI

libcxx/include/CMakeLists.txt

set(files
   __type_traits/unwrap_ref.h
   __type_traits/void_t.h
   __undef_macros
   __utility/as_const.h
   __utility/auto_cast.h
   __utility/cmp.h
   __utility/convert_to_integral.h
   __utility/declval.h
+  __utility/empty.h
   __utility/exception_guard.h
   __utility/exchange.h
   __utility/forward.h
   __utility/forward_like.h
   __utility/in_place.h
   __utility/integer_sequence.h
   __utility/is_pointer_in_range.h
   __utility/move.h
   __utility/pair.h
   __utility/piecewise_construct.h
   __utility/priority_tag.h
   __utility/rel_ops.h
   __utility/swap.h
-  __utility/terminate_on_exception.h
   __utility/to_underlying.h
   __utility/unreachable.h
   __variant/monostate.h
   __verbose_abort
   algorithm
   any
   array
   atomic

libcxx/include/__algorithm/pstl_any_all_none_of.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_ANY_ALL_NONE_OF_H
 #define _LIBCPP___ALGORITHM_PSTL_ANY_ALL_NONE_OF_H
 
 #include <__algorithm/pstl_find.h>
 #include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
 #include <__iterator/cpp17_iterator_concepts.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
 #include <__utility/move.h>
-#include <__utility/terminate_on_exception.h>
+#include <optional>
 
 #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_any_of(); // declaration needed for the frontend dispatch below
 
 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
-any_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
-  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool> __any_of(
+    _ExecutionPolicy&& __policy, _ForwardIterator&& __first, _ForwardIterator&& __last, _Predicate&& __pred) noexcept {
   return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_any_of),
-      [&](_ForwardIterator __g_first, _ForwardIterator __g_last, _Predicate __g_pred) {
-        return std::find_if(__policy, __g_first, __g_last, __g_pred) != __g_last;
+      [&](_ForwardIterator __g_first, _ForwardIterator __g_last, _Predicate __g_pred) -> optional<bool> {
+        auto __res = std::__find_if(__policy, __g_first, __g_last, __g_pred);
+        if (!__res)
+          return nullopt;
+        return *__res != __g_last;
       },
       std::move(__first),
       std::move(__last),
       std::move(__pred));
 }
 
+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
+any_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
+  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+  auto __res = std::__any_of(__policy, std::move(__first), std::move(__last), std::move(__pred));
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *std::move(__res);
+}
+
 template <class>
 void __pstl_all_of(); // declaration needed for the frontend dispatch below
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Pred,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool
-all_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) {
-  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
+__all_of(_ExecutionPolicy&& __policy, _ForwardIterator&& __first, _ForwardIterator&& __last, _Pred&& __pred) noexcept {
   return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_all_of),
-      [&](_ForwardIterator __g_first, _ForwardIterator __g_last, _Pred __g_pred) {
-        return !std::any_of(__policy, __g_first, __g_last, [&](__iter_reference<_ForwardIterator> __value) {
+      [&](_ForwardIterator __g_first, _ForwardIterator __g_last, _Pred __g_pred) -> optional<bool> {
+        auto __res = std::__any_of(__policy, __g_first, __g_last, [&](__iter_reference<_ForwardIterator> __value) {
           return !__g_pred(__value);
         });
+        if (!__res)
+          return nullopt;
+        return !*__res;
       },
       std::move(__first),
       std::move(__last),
       std::move(__pred));
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Pred,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool
+all_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) {
+  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+  auto __res = std::__all_of(__policy, std::move(__first), std::move(__last), std::move(__pred));
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *std::move(__res);
+}
+
 template <class>
 void __pstl_none_of(); // declaration needed for the frontend dispatch below
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Pred,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool
-none_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) {
-  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<bool>
+__none_of(_ExecutionPolicy&& __policy, _ForwardIterator&& __first, _ForwardIterator&& __last, _Pred&& __pred) noexcept {
   return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_none_of),
-      [&](_ForwardIterator __g_first, _ForwardIterator __g_last, _Pred __g_pred) {
-        return !std::any_of(__policy, __g_first, __g_last, __g_pred);
+      [&](_ForwardIterator __g_first, _ForwardIterator __g_last, _Pred __g_pred) -> optional<bool> {
+        auto __res = std::__any_of(__policy, __g_first, __g_last, __g_pred);
+        if (!__res)
+          return nullopt;
+        return !*__res;
       },
       std::move(__first),
       std::move(__last),
       std::move(__pred));
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Pred,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool
+none_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) {
+  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+  auto __res = std::__none_of(__policy, std::move(__first), std::move(__last), std::move(__pred));
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *std::move(__res);
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_ANY_ALL_NONE_OF_H

libcxx/include/__algorithm/pstl_backend.h

 _LIBCPP_BEGIN_NAMESPACE_STD
 
 /*
 TODO: Documentation of how backends work
 
 A PSTL parallel backend is a tag type to which the following functions are associated, at minimum:
 
   template <class _ExecutionPolicy, class _Iterator, class _Func>
-  void __pstl_for_each(_Backend, _ExecutionPolicy&&, _Iterator __first, _Iterator __last, _Func __f);
+  optional<__empty> __pstl_for_each(_Backend, _ExecutionPolicy&&, _Iterator __first, _Iterator __last, _Func __f);
 
   template <class _ExecutionPolicy, class _Iterator, class _Predicate>
-  _Iterator __pstl_find_if(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred);
+  optional<_Iterator> __pstl_find_if(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred);
 
   template <class _ExecutionPolicy, class _RandomAccessIterator, class _Comp>
-  void __pstl_stable_sort(_Backend, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp);
+  optional<__empty>
+  __pstl_stable_sort(_Backend, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp);
 
   template <class _ExecutionPolicy, class _InIterator, class _OutIterator, class _UnaryOperation>
-  _OutIterator __pstl_transform(_InIterator __first, _InIterator __last, _OutIterator __result, _UnaryOperation __op);
+  optional<_OutIterator>
+  __pstl_transform(_InIterator __first, _InIterator __last, _OutIterator __result, _UnaryOperation __op);
 
   template <class _ExecutionPolicy, class _InIterator1, class _InIterator2, class _OutIterator, class _BinaryOperation>
-  _OutIterator __pstl_transform(_InIterator1 __first1,
-                                _InIterator1 __last1,
+  optional<_OutIterator> __pstl_transform(_InIterator1 __first1,
                                           _InIterator2 __first2,
+                                          _InIterator1 __last1,
                                           _OutIterator __result,
                                           _BinaryOperation __op);
 
   template <class _ExecutionPolicy,
             class _Iterator1,
             class _Iterator2,
             class _Tp,
             class _BinaryOperation1,
             class _BinaryOperation2>
-  _Tp __pstl_transform_reduce(_Backend,
+  optional<_Tp> __pstl_transform_reduce(_Backend,
                                         _Iterator1 __first1,
                                         _Iterator1 __last1,
                                         _Iterator2 __first2,
                                         _Iterator2 __last2,
                                         _Tp __init,
                                         _BinaryOperation1 __reduce,
                                         _BinaryOperation2 __transform);
 
   template <class _ExecutionPolicy, class _Iterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
-  _Tp __pstl_transform_reduce(_Backend,
+  optional<_Tp> __pstl_transform_reduce(_Backend,
                                         _Iterator __first,
                                         _Iterator __last,
                                         _Tp __init,
                                         _BinaryOperation __reduce,
                                         _UnaryOperation __transform);
 
 // TODO: Complete this list
 
 The following functions are optional but can be provided. If provided, they are used by the corresponding
 algorithms, otherwise they are implemented in terms of other algorithms. If none of the optional algorithms are
 implemented, all the algorithms will eventually forward to the basis algorithms listed above:
 
   template <class _ExecutionPolicy, class _Iterator, class _Size, class _Func>
-  void __pstl_for_each_n(_Backend, _Iterator __first, _Size __n, _Func __f);
+  optional<__empty> __pstl_for_each_n(_Backend, _Iterator __first, _Size __n, _Func __f);
 
   template <class _ExecutionPolicy, class _Iterator, class _Predicate>
-  bool __pstl_any_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred);
+  optional<bool> __pstl_any_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred);
 
   template <class _ExecutionPolicy, class _Iterator, class _Predicate>
-  bool __pstl_all_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred);
+  optional<bool> __pstl_all_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred);
 
   template <class _ExecutionPolicy, class _Iterator, class _Predicate>
-  bool __pstl_none_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred);
+  optional<bool> __pstl_none_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred);
 
   template <class _ExecutionPolicy, class _Iterator, class _Tp>
-  _Iterator __pstl_find(_Backend, _Iterator __first, _Iterator __last, const _Tp& __value);
+  optional<_Iterator> __pstl_find(_Backend, _Iterator __first, _Iterator __last, const _Tp& __value);
 
   template <class _ExecutionPolicy, class _Iterator, class _Predicate>
-  _Iterator __pstl_find_if_not(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred);
+  optional<_Iterator> __pstl_find_if_not(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred);
 
   template <class _ExecutionPolicy, class _Iterator, class _Tp>
-  void __pstl_fill(_Backend, _Iterator __first, _Iterator __last, const _Tp& __value);
+  optional<__empty> __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);
+  optional<__empty> __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);
+  optional<__empty> __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);
+  optional<__empty> __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);
+  optional<__empty> __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,
+  optional<_OutIterator> __pstl_merge(_Backend,
                                       _Iterator1 __first1,
                                       _Iterator1 __last1,
                                       _Iterator2 __first2,
                                       _Iterator2 __last2,
                                       _OutIterator __result,
                                       _Comp __comp);
 
   template <class _ExecutionPolicy, class _Iterator, class _Tp, class _BinaryOperation>
-  _Tp __pstl_reduce(_Backend, _Iterator __first, _Iterator __last, _Tp __init, _BinaryOperation __op);
+  optional<_Tp> __pstl_reduce(_Backend, _Iterator __first, _Iterator __last, _Tp __init, _BinaryOperation __op);
 
   temlate <class _ExecutionPolicy, class _Iterator>
-  __iter_value_type<_Iterator> __pstl_reduce(_Backend, _Iterator __first, _Iterator __last);
+  optional<__iter_value_type<_Iterator>> __pstl_reduce(_Backend, _Iterator __first, _Iterator __last);
 
   template <class _ExecuitonPolicy, class _Iterator, class _Tp>
-  __iter_diff_t<_Iterator> __pstl_count(_Backend, _Iterator __first, _Iterator __last, const _Tp& __value);
+  optional<__iter_diff_t<_Iterator>> __pstl_count(_Backend, _Iterator __first, _Iterator __last, const _Tp& __value);
 
   template <class _ExecutionPolicy, class _Iterator, class _Predicate>
-  __iter_diff_t<_Iterator> __pstl_count_if(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred);
+  optional<__iter_diff_t<_Iterator>> __pstl_count_if(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred);
 
   template <class _ExecutionPolicy, class _Iterator, class _Tp>
-  void __pstl_replace(_Backend, _Iterator __first, _Iterator __last, const _Tp& __old_value, const _Tp& __new_value);
+  optional<__empty>
+  __pstl_replace(_Backend, _Iterator __first, _Iterator __last, const _Tp& __old_value, const _Tp& __new_value);
 
   template <class _ExecutionPolicy, class _Iterator, class _Pred, class _Tp>
-  void __pstl_replace_if(_Backend, _Iterator __first, _Iterator __last, _Pred __pred, const _Tp& __new_value);
+  optional<__empty>
+  __pstl_replace_if(_Backend, _Iterator __first, _Iterator __last, _Pred __pred, const _Tp& __new_value);
 
   template <class _ExecutionPolicy, class _Iterator, class _OutIterator, class _Tp>
-  void __pstl_replace_copy(_Backend,
+  optional<__empty> __pstl_replace_copy(_Backend,
                                         _Iterator __first,
                                         _Iterator __last,
                                         _OutIterator __result,
                                         const _Tp& __old_value,
                                         const _Tp& __new_value);
 
   template <class _ExecutionPolicy, class _Iterator, class _OutIterator, class _Pred, class _Tp>
-  void __pstl_replace_copy_if(_Backend,
+  optional<__empty> __pstl_replace_copy_if(_Backend,
                                            _Iterator __first,
                                            _Iterator __last,
                                            _OutIterator __result,
                                            _Pred __pred,
                                            const _Tp& __new_value);
 
   template <class _ExecutionPolicy, class _Iterator, class _Comp>
-  void __pstl_sort(_Backend, _Iterator __first, _Iterator __last, _Comp __comp);
+  optional<__empty> __pstl_sort(_Backend, _Iterator __first, _Iterator __last, _Comp __comp);
 
 // TODO: Complete this list
 
+Exception handling
+==================
+
+PSTL backends are expected to report errors (i.e. failure to allocate) by returning a disengaged `optional` from their
+implementation. Exceptions shouldn't be used to report an internal failure-to-allocate, since all exceptions are turned
+into a program termination at the front-end level. When a backend returns a disengaged `optional` to the frontend, the
+frontend will turn that into a call to `std::__throw_bad_alloc();` to report the internal failure to the user.
 */
 
 template <class _ExecutionPolicy>
 struct __select_backend;
 
 template <>
 struct __select_backend<std::execution::sequenced_policy> {
   using type = __cpu_backend_tag;

libcxx/include/__algorithm/pstl_backends/cpu_backend.h

 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_H
 
 #include <__config>
 
 /*
 
   // _Functor takes a subrange for [__first, __last) that should be executed in serial
   template <class _RandomAccessIterator, class _Functor>
-  void __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Functor __func);
+  optional<__empty> __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Functor __func);
 
   template <class _Iterator, class _UnaryOp, class _Tp, class _BinaryOp, class _Reduction>
-  _Tp __parallel_transform_reduce(_Iterator __first, _Iterator __last, _UnaryOp, _Tp __init, _BinaryOp, _Reduction);
+  optional<_Tp>
+  __parallel_transform_reduce(_Iterator __first, _Iterator __last, _UnaryOp, _Tp __init, _BinaryOp, _Reduction);
 
   // Cancel the execution of other jobs - they aren't needed anymore
   void __cancel_execution();
 
   template <class _RandomAccessIterator1,
             class _RandomAccessIterator2,
             class _RandomAccessIterator3,
             class _Compare,
             class _LeafMerge>
-  void __parallel_merge(
+  optional<void> __parallel_merge(
       _RandomAccessIterator1 __first1,
       _RandomAccessIterator1 __last1,
       _RandomAccessIterator2 __first2,
       _RandomAccessIterator2 __last2,
       _RandomAccessIterator3 __outit,
       _Compare __comp,
       _LeafMerge __leaf_merge);
 
   template <class _RandomAccessIterator, class _Comp, class _LeafSort>
   void __parallel_stable_sort(_RandomAccessIterator __first,
                               _RandomAccessIterator __last,
                               _Comp __comp,
                               _LeafSort __leaf_sort);
 
   TODO: Document the parallel backend
+
+Exception handling
+==================
+
+CPU backends are expected to report errors (i.e. failure to allocate) by returning a disengaged `optional` from their
+implementation. Exceptions shouldn't be used to report an internal failure-to-allocate, since all exceptions are turned
+into a program termination at the front-end level. When a backend returns a disengaged `optional` to the frontend, the
+frontend will turn that into a call to `std::__throw_bad_alloc();` to report the internal failure to the user.
 */
 
 #include <__algorithm/pstl_backends/cpu_backends/any_of.h>
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__algorithm/pstl_backends/cpu_backends/fill.h>
 #include <__algorithm/pstl_backends/cpu_backends/find_if.h>
 #include <__algorithm/pstl_backends/cpu_backends/for_each.h>
 #include <__algorithm/pstl_backends/cpu_backends/merge.h>
 #include <__algorithm/pstl_backends/cpu_backends/stable_sort.h>
 #include <__algorithm/pstl_backends/cpu_backends/transform.h>
 #include <__algorithm/pstl_backends/cpu_backends/transform_reduce.h>
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/any_of.h

 #include <__algorithm/find_if.h>
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__atomic/atomic.h>
 #include <__atomic/memory_order.h>
 #include <__config>
 #include <__functional/operations.h>
 #include <__iterator/concepts.h>
 #include <__type_traits/is_execution_policy.h>
+#include <__utility/move.h>
 #include <__utility/pair.h>
-#include <__utility/terminate_on_exception.h>
 #include <cstdint>
+#include <optional>
 
 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Index, class _Brick>
-_LIBCPP_HIDE_FROM_ABI bool __parallel_or(_Index __first, _Index __last, _Brick __f) {
+_LIBCPP_HIDE_FROM_ABI optional<bool> __parallel_or(_Index __first, _Index __last, _Brick __f) {
   std::atomic<bool> __found(false);
-  __par_backend::__parallel_for(__first, __last, [__f, &__found](_Index __i, _Index __j) {
+  auto __ret = __par_backend::__parallel_for(__first, __last, [__f, &__found](_Index __i, _Index __j) {
     if (!__found.load(std::memory_order_relaxed) && __f(__i, __j)) {
       __found.store(true, std::memory_order_relaxed);
       __par_backend::__cancel_execution();
     }
   });
+  if (!__ret)
+    return nullopt;
   return __found;
 }
 
 // TODO: check whether __simd_first() can be used here
 template <class _Index, class _DifferenceType, class _Pred>
 _LIBCPP_HIDE_FROM_ABI bool __simd_or(_Index __first, _DifferenceType __n, _Pred __pred) noexcept {
   _DifferenceType __block_size = 4 < __n ? 4 : __n;
   const _Index __last          = __first + __n;
while (__last != __first) {
     __first += __block_size;
     if (__last - __first >= __block_size << 1) {
       // Double the block _Size.  Any unnecessary iterations can be amortized against work done so far.
       __block_size <<= 1;
     } else {
       __block_size = __last - __first;
     }
   }
   return false;
 }
 
 template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
-_LIBCPP_HIDE_FROM_ABI bool
+_LIBCPP_HIDE_FROM_ABI optional<bool>
 __pstl_any_of(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
                 __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
-    return std::__terminate_on_exception([&] {
-      return std::__parallel_or(
-          __first, __last, [&__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
-            return std::__pstl_any_of<__remove_parallel_policy_t<_ExecutionPolicy>>(
-                __cpu_backend_tag{}, __brick_first, __brick_last, __pred);
-          });
+          auto __res = std::__pstl_any_of<__remove_parallel_policy_t<_ExecutionPolicy>>(
+          _LIBCPP_ASSERT_INTERNAL(__res, "unseq/seq should never try to allocate!");
+          return *std::move(__res);
         });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
                        __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     return std::__simd_or(__first, __last - __first, __pred);
   } else {
     return std::any_of(__first, __last, __pred);
   }
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKEND_ANY_OF_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/fill.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_BACKENDS_CPU_BACKENDS_FILL_H
 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_FILL_H
 
 #include <__algorithm/fill.h>
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__config>
 #include <__iterator/concepts.h>
 #include <__type_traits/is_execution_policy.h>
-#include <__utility/terminate_on_exception.h>
+#include <optional>
 
 #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 _Index, class _DifferenceType, class _Tp>
 _LIBCPP_HIDE_FROM_ABI _Index __simd_fill_n(_Index __first, _DifferenceType __n, const _Tp& __value) noexcept {
   _PSTL_USE_NONTEMPORAL_STORES_IF_ALLOWED
   _PSTL_PRAGMA_SIMD
   for (_DifferenceType __i = 0; __i < __n; ++__i)
     __first[__i] = __value;
   return __first + __n;
 }
 
 template <class _ExecutionPolicy, class _ForwardIterator, class _Tp>
-_LIBCPP_HIDE_FROM_ABI void
+_LIBCPP_HIDE_FROM_ABI optional<__empty>
 __pstl_fill(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
                 __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
-    std::__terminate_on_exception([&] {
-      __par_backend::__parallel_for(
-          __first, __last, [&__value](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
-            std::__pstl_fill<__remove_parallel_policy_t<_ExecutionPolicy>>(
-                __cpu_backend_tag{}, __brick_first, __brick_last, __value);
-          });
+    return __par_backend::__parallel_for(
+          [[maybe_unused]] auto __res = std::__pstl_fill<__remove_parallel_policy_t<_ExecutionPolicy>>(
+          _LIBCPP_ASSERT_INTERNAL(__res, "unseq/seq should never try to allocate!");
         });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
                        __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     std::__simd_fill_n(__first, __last - __first, __value);
+    return __empty{};
   } else {
     std::fill(__first, __last, __value);
+    return __empty{};
   }
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_FILL_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/find_if.h

 #include <__algorithm/find_if.h>
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__atomic/atomic.h>
 #include <__config>
 #include <__functional/operations.h>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__type_traits/is_execution_policy.h>
+#include <__utility/move.h>
 #include <__utility/pair.h>
-#include <__utility/terminate_on_exception.h>
 #include <cstddef>
+#include <optional>
 
 #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 _Index, class _Brick, class _Compare>
-_LIBCPP_HIDE_FROM_ABI _Index
+_LIBCPP_HIDE_FROM_ABI optional<_Index>
 __parallel_find(_Index __first, _Index __last, _Brick __f, _Compare __comp, bool __b_first) {
   typedef typename std::iterator_traits<_Index>::difference_type _DifferenceType;
   const _DifferenceType __n      = __last - __first;
   _DifferenceType __initial_dist = __b_first ? __n : -1;
   std::atomic<_DifferenceType> __extremum(__initial_dist);
   // TODO: find out what is better here: parallel_for or parallel_reduce
+  auto __res =
       __par_backend::__parallel_for(__first, __last, [__comp, __f, __first, &__extremum](_Index __i, _Index __j) {
         // See "Reducing Contention Through Priority Updates", PPoPP '13, for discussion of
         // why using a shared variable scales fairly well in this situation.
         if (__comp(__i - __first, __extremum)) {
-      _Index __res = __f(__i, __j);
+          _Index __result = __f(__i, __j);
           // If not '__last' returned then we found what we want so put this to extremum
-      if (__res != __j) {
-        const _DifferenceType __k = __res - __first;
+          if (__result != __j) {
+            const _DifferenceType __k = __result - __first;
             for (_DifferenceType __old = __extremum; __comp(__k, __old); __old = __extremum) {
               __extremum.compare_exchange_weak(__old, __k);
             }
           }
         }
       });
+  if (!__res)
+    return nullopt;
   return __extremum != __initial_dist ? __first + __extremum : __last;
 }
 
 template <class _Index, class _DifferenceType, class _Compare>
 _LIBCPP_HIDE_FROM_ABI _Index
 __simd_first(_Index __first, _DifferenceType __begin, _DifferenceType __end, _Compare __comp) noexcept {
   // Experiments show good block sizes like this
   const _DifferenceType __block_size                        = 8;
while (__begin != __end) {
     if (__comp(__first, __begin)) {
       return __first + __begin;
     }
     ++__begin;
   }
   return __first + __end;
 }
 
 template <class _ExecutionPolicy, class _ForwardIterator, class _Predicate>
-_LIBCPP_HIDE_FROM_ABI _ForwardIterator
+_LIBCPP_HIDE_FROM_ABI optional<_ForwardIterator>
 __pstl_find_if(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
                 __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
-    return std::__terminate_on_exception([&] {
-      return std::__parallel_find(
-          __first,
-          __last,
-          [&__pred](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
-            return std::__pstl_find_if<__remove_parallel_policy_t<_ExecutionPolicy>>(
-                __cpu_backend_tag{}, __brick_first, __brick_last, __pred);
-          },
-          less<>{},
-          true);
-    });
+          auto __res = std::__pstl_find_if<__remove_parallel_policy_t<_ExecutionPolicy>>(
+          _LIBCPP_ASSERT_INTERNAL(__res, "unseq/seq should never try to allocate!");
+          return *std::move(__res);
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
                        __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     using __diff_t = __iter_diff_t<_ForwardIterator>;
     return std::__simd_first(__first, __diff_t(0), __last - __first, [&__pred](_ForwardIterator __iter, __diff_t __i) {
       return __pred(__iter[__i]);
     });
   } else {
     return std::find_if(__first, __last, __pred);
   }
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_FIND_IF_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/for_each.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_BACKENDS_CPU_BACKNEDS_FOR_EACH_H
 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKNEDS_FOR_EACH_H
 
 #include <__algorithm/for_each.h>
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__config>
 #include <__iterator/concepts.h>
 #include <__type_traits/is_execution_policy.h>
-#include <__utility/terminate_on_exception.h>
+#include <optional>
 
 #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 _Iterator, class _DifferenceType, class _Function>
 _LIBCPP_HIDE_FROM_ABI _Iterator __simd_walk_1(_Iterator __first, _DifferenceType __n, _Function __f) noexcept {
   _PSTL_PRAGMA_SIMD
   for (_DifferenceType __i = 0; __i < __n; ++__i)
     __f(__first[__i]);
 
   return __first + __n;
 }
 
 template <class _ExecutionPolicy, class _ForwardIterator, class _Functor>
-_LIBCPP_HIDE_FROM_ABI void
+_LIBCPP_HIDE_FROM_ABI optional<__empty>
 __pstl_for_each(__cpu_backend_tag, _ForwardIterator __first, _ForwardIterator __last, _Functor __func) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
                 __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
-    std::__terminate_on_exception([&] {
-      std::__par_backend::__parallel_for(
-          __first, __last, [__func](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
-            std::__pstl_for_each<__remove_parallel_policy_t<_ExecutionPolicy>>(
-                __cpu_backend_tag{}, __brick_first, __brick_last, __func);
-          });
+    return std::__par_backend::__parallel_for(
+          [[maybe_unused]] auto __res = std::__pstl_for_each<__remove_parallel_policy_t<_ExecutionPolicy>>(
+          _LIBCPP_ASSERT_INTERNAL(__res, "unseq/seq should never try to allocate!");
         });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
                        __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     std::__simd_walk_1(__first, __last - __first, __func);
+    return __empty{};
   } else {
     std::for_each(__first, __last, __func);
+    return __empty{};
   }
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKNEDS_FOR_EACH_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/libdispatch.h

 #include <__config>
 #include <__exception/terminate.h>
 #include <__iterator/iterator_traits.h>
 #include <__iterator/move_iterator.h>
 #include <__memory/allocator.h>
 #include <__memory/construct_at.h>
 #include <__memory/unique_ptr.h>
 #include <__numeric/reduce.h>
+#include <__utility/empty.h>
 #include <__utility/exception_guard.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
-#include <__utility/terminate_on_exception.h>
 #include <cstddef>
 #include <new>
+#include <optional>
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
struct __chunk_partitions {
   ptrdiff_t __chunk_count_; // includes the first chunk
   ptrdiff_t __chunk_size_;
   ptrdiff_t __first_chunk_size_;
 };
 
 [[__gnu__::__const__]] _LIBCPP_EXPORTED_FROM_ABI __chunk_partitions __partition_chunks(ptrdiff_t __size);
 
 template <class _RandomAccessIterator, class _Functor>
-_LIBCPP_HIDE_FROM_ABI void
+_LIBCPP_HIDE_FROM_ABI optional<__empty>
 __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Functor __func) {
   auto __partitions = __libdispatch::__partition_chunks(__last - __first);
 
   // Perform the chunked execution.
   __libdispatch::__dispatch_apply(__partitions.__chunk_count_, [&](size_t __chunk) {
     auto __this_chunk_size = __chunk == 0 ? __partitions.__first_chunk_size_ : __partitions.__chunk_size_;
     auto __index =
         __chunk == 0
             ? 0
             : (__chunk * __partitions.__chunk_size_) + (__partitions.__first_chunk_size_ - __partitions.__chunk_size_);
     __func(__first + __index, __first + __index + __this_chunk_size);
   });
+
+  return __empty{};
 }
 
 template <class _RandomAccessIterator1, class _RandomAccessIterator2, class _RandomAccessIteratorOut>
 struct __merge_range {
   __merge_range(_RandomAccessIterator1 __mid1, _RandomAccessIterator2 __mid2, _RandomAccessIteratorOut __result)
       : __mid1_(__mid1), __mid2_(__mid2), __result_(__result) {}
 
   _RandomAccessIterator1 __mid1_;
   _RandomAccessIterator2 __mid2_;
   _RandomAccessIteratorOut __result_;
 };
 
 template <typename _RandomAccessIterator1,
           typename _RandomAccessIterator2,
           typename _RandomAccessIterator3,
           typename _Compare,
           typename _LeafMerge>
-_LIBCPP_HIDE_FROM_ABI void __parallel_merge(
+_LIBCPP_HIDE_FROM_ABI optional<__empty> __parallel_merge(
     _RandomAccessIterator1 __first1,
     _RandomAccessIterator1 __last1,
     _RandomAccessIterator2 __first2,
     _RandomAccessIterator2 __last2,
     _RandomAccessIterator3 __result,
     _Compare __comp,
-    _LeafMerge __leaf_merge) {
+    _LeafMerge __leaf_merge) noexcept {
   __chunk_partitions __partitions =
       __libdispatch::__partition_chunks(std::max<ptrdiff_t>(__last1 - __first1, __last2 - __first2));
 
   if (__partitions.__chunk_count_ == 0)
-    return;
+    return __empty{};
 
   if (__partitions.__chunk_count_ == 1) {
     __leaf_merge(__first1, __last1, __first2, __last2, __result, __comp);
-    return;
+    return __empty{};
   }
 
   using __merge_range_t = __merge_range<_RandomAccessIterator1, _RandomAccessIterator2, _RandomAccessIterator3>;
   auto const __n_ranges = __partitions.__chunk_count_ + 1;
 
   // TODO: use __uninitialized_buffer
   auto __destroy = [=](__merge_range_t* __ptr) {
     std::destroy_n(__ptr, __n_ranges);
     std::allocator<__merge_range_t>().deallocate(__ptr, __n_ranges);
   };
+
   unique_ptr<__merge_range_t[], decltype(__destroy)> __ranges(
-      std::allocator<__merge_range_t>().allocate(__n_ranges), __destroy);
+      [&]() -> __merge_range_t* {
+#  ifndef _LIBCPP_HAS_NO_EXCEPTIONS
+        try {
+#  endif
+          return std::allocator<__merge_range_t>().allocate(__n_ranges);
+#  ifndef _LIBCPP_HAS_NO_EXCEPTIONS
+        } catch (const std::bad_alloc&) {
+          return nullptr;
+        }
+#  endif
+      }(),
+      __destroy);
+
+  if (!__ranges)
+    return nullopt;
 
   // TODO: Improve the case where the smaller range is merged into just a few (or even one) chunks of the larger case
-  std::__terminate_on_exception([&] {
-    __merge_range_t* __r = __ranges.get();
-    std::__construct_at(__r++, __first1, __first2, __result);
 
-    bool __iterate_first_range = __last1 - __first1 > __last2 - __first2;
 
-    auto __compute_chunk = [&](size_t __chunk_size) -> __merge_range_t {
-      auto [__mid1, __mid2] = [&] {
-        if (__iterate_first_range) {
-          auto __m1 = __first1 + __chunk_size;
-          auto __m2 = std::lower_bound(__first2, __last2, __m1[-1], __comp);
-          return std::make_pair(__m1, __m2);
-        } else {
-          auto __m2 = __first2 + __chunk_size;
-          auto __m1 = std::lower_bound(__first1, __last1, __m2[-1], __comp);
-          return std::make_pair(__m1, __m2);
-        }
-      }();
 
-      __result += (__mid1 - __first1) + (__mid2 - __first2);
-      __first1 = __mid1;
-      __first2 = __mid2;
-      return {std::move(__mid1), std::move(__mid2), __result};
-    };
 
-    // handle first chunk
-    std::__construct_at(__r++, __compute_chunk(__partitions.__first_chunk_size_));
 
-    // handle 2 -> N - 1 chunks
-    for (ptrdiff_t __i = 0; __i != __partitions.__chunk_count_ - 2; ++__i)
-      std::__construct_at(__r++, __compute_chunk(__partitions.__chunk_size_));
 
-    // handle last chunk
-    std::__construct_at(__r, __last1, __last2, __result);
 
-    __libdispatch::__dispatch_apply(__partitions.__chunk_count_, [&](size_t __index) {
-      auto __first_iters = __ranges[__index];
-      auto __last_iters  = __ranges[__index + 1];
-      __leaf_merge(
-          __first_iters.__mid1_,
-          __last_iters.__mid1_,
-          __first_iters.__mid2_,
-          __last_iters.__mid2_,
-          __first_iters.__result_,
-          __comp);
-    });
-  });
+
+  return __empty{};
 }
 
 template <class _RandomAccessIterator, class _Transform, class _Value, class _Combiner, class _Reduction>
-_LIBCPP_HIDE_FROM_ABI _Value __parallel_transform_reduce(
+_LIBCPP_HIDE_FROM_ABI optional<_Value> __parallel_transform_reduce(
     _RandomAccessIterator __first,
     _RandomAccessIterator __last,
     _Transform __transform,
     _Value __init,
     _Combiner __combiner,
     _Reduction __reduction) {
   if (__first == __last)
     return __init;
if (__this_chunk_size != 1) {
           __reduction(__first + __index + 2,
                       __first + __index + __this_chunk_size,
                       __combiner(__transform(__first + __index), __transform(__first + __index + 1))));
     } else {
       std::__construct_at(__values.get() + __chunk, __transform(__first + __index));
     }
   });
 
-  return std::__terminate_on_exception([&] {
-    return std::reduce(
-        std::make_move_iterator(__values.get()),
-        std::make_move_iterator(__values.get() + __partitions.__chunk_count_),
-        std::move(__init),
-        __combiner);
-  });
 }
 
 // TODO: parallelize this
 template <class _RandomAccessIterator, class _Comp, class _LeafSort>
-_LIBCPP_HIDE_FROM_ABI void __parallel_stable_sort(
+_LIBCPP_HIDE_FROM_ABI optional<__empty> __parallel_stable_sort(
     _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp, _LeafSort __leaf_sort) {
   __leaf_sort(__first, __last, __comp);
+  return __empty{};
 }
 
 _LIBCPP_HIDE_FROM_ABI inline void __cancel_execution() {}
 
 } // namespace __libdispatch
 } // namespace __par_backend
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_LIBDISPATCH_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/merge.h

 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_MERGE_H
 
 #include <__algorithm/merge.h>
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__config>
 #include <__iterator/concepts.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__utility/move.h>
-#include <__utility/terminate_on_exception.h>
+#include <optional>
 
 #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 _ExecutionPolicy,
           class _ForwardIterator1,
           class _ForwardIterator2,
           class _ForwardOutIterator,
           class _Comp>
-_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator __pstl_merge(
+_LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> __pstl_merge(
     __cpu_backend_tag,
     _ForwardIterator1 __first1,
     _ForwardIterator1 __last1,
     _ForwardIterator2 __first2,
     _ForwardIterator2 __last2,
     _ForwardOutIterator __result,
     _Comp __comp) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
                 __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
                 __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value &&
                 __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) {
-    return std::__terminate_on_exception([&] {
-      __par_backend::__parallel_merge(
-          __first1,
-          __last1,
-          __first2,
-          __last2,
-          __result,
-          __comp,
-          [](_ForwardIterator1 __g_first1,
-             _ForwardIterator1 __g_last1,
-             _ForwardIterator2 __g_first2,
-             _ForwardIterator2 __g_last2,
-             _ForwardOutIterator __g_result,
-             _Comp __g_comp) {
-            return std::__pstl_merge<__remove_parallel_policy_t<_ExecutionPolicy>>(
-                __cpu_backend_tag{},
-                std::move(__g_first1),
-                std::move(__g_last1),
-                std::move(__g_first2),
-                std::move(__g_last2),
-                std::move(__g_result),
-                std::move(__g_comp));
-          });
-      return __result + (__last1 - __first1) + (__last2 - __first2);
-    });
+    auto __res = __par_backend::__parallel_merge(
+          [[maybe_unused]] auto __g_res = std::__pstl_merge<__remove_parallel_policy_t<_ExecutionPolicy>>(
+          _LIBCPP_ASSERT_INTERNAL(__g_res, "unsed/sed should never try to allocate!");
+    if (!__res)
+      return nullopt;
   } else {
     return std::merge(__first1, __last1, __first2, __last2, __result, __comp);
   }
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_MERGE_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/serial.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___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_SERIAL_H
 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_SERIAL_H
 
 #include <__config>
+#include <__utility/empty.h>
 #include <__utility/move.h>
 #include <cstddef>
+#include <optional>
 
 #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
 
 namespace __par_backend {
 inline namespace __serial_cpu_backend {
 
 template <class _RandomAccessIterator, class _Fp>
-_LIBCPP_HIDE_FROM_ABI void __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Fp __f) {
+_LIBCPP_HIDE_FROM_ABI optional<__empty>
+__parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Fp __f) {
   __f(__first, __last);
+  return __empty{};
 }
 
 template <class _Index, class _UnaryOp, class _Tp, class _BinaryOp, class _Reduce>
-_LIBCPP_HIDE_FROM_ABI _Tp
+_LIBCPP_HIDE_FROM_ABI optional<_Tp>
 __parallel_transform_reduce(_Index __first, _Index __last, _UnaryOp, _Tp __init, _BinaryOp, _Reduce __reduce) {
   return __reduce(std::move(__first), std::move(__last), std::move(__init));
 }
 
 template <class _RandomAccessIterator, class _Compare, class _LeafSort>
-_LIBCPP_HIDE_FROM_ABI void __parallel_stable_sort(
+_LIBCPP_HIDE_FROM_ABI optional<__empty> __parallel_stable_sort(
     _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, _LeafSort __leaf_sort) {
   __leaf_sort(__first, __last, __comp);
+  return __empty{};
 }
 
 _LIBCPP_HIDE_FROM_ABI inline void __cancel_execution() {}
 
 template <class _RandomAccessIterator1,
           class _RandomAccessIterator2,
           class _RandomAccessIterator3,
           class _Compare,
           class _LeafMerge>
-_LIBCPP_HIDE_FROM_ABI void __parallel_merge(
+_LIBCPP_HIDE_FROM_ABI optional<__empty> __parallel_merge(
     _RandomAccessIterator1 __first1,
     _RandomAccessIterator1 __last1,
     _RandomAccessIterator2 __first2,
     _RandomAccessIterator2 __last2,
     _RandomAccessIterator3 __outit,
     _Compare __comp,
     _LeafMerge __leaf_merge) {
   __leaf_merge(__first1, __last1, __first2, __last2, __outit, __comp);
+  return __empty{};
 }
 
 // TODO: Complete this list
 
 } // namespace __serial_cpu_backend
 } // namespace __par_backend
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_SERIAL_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/stable_sort.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_BACKENDS_CPU_BACKENDS_STABLE_SORT_H
 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_STABLE_SORT_H
 
 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__algorithm/stable_sort.h>
 #include <__config>
 #include <__type_traits/is_execution_policy.h>
-#include <__utility/terminate_on_exception.h>
+#include <optional>
 
 #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 _ExecutionPolicy, class _RandomAccessIterator, class _Comp>
-_LIBCPP_HIDE_FROM_ABI void
+_LIBCPP_HIDE_FROM_ABI optional<__empty>
 __pstl_stable_sort(__cpu_backend_tag, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy>) {
-    std::__terminate_on_exception([&] {
-      __par_backend::__parallel_stable_sort(
-          __first, __last, __comp, [](_RandomAccessIterator __g_first, _RandomAccessIterator __g_last, _Comp __g_comp) {
-            std::stable_sort(__g_first, __g_last, __g_comp);
-          });
-    });
+    return __par_backend::__parallel_stable_sort(
   } else {
     std::stable_sort(__first, __last, __comp);
+    return __empty{};
   }
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_STABLE_SORT_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/thread.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_BACKENDS_CPU_BACKENDS_THREAD_H
 #define _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_THREAD_H
 
 #include <__assert>
 #include <__config>
+#include <__utility/empty.h>
 #include <__utility/move.h>
 #include <cstddef>
+#include <optional>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_PUSH_MACROS
 #include <__undef_macros>
 
 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 // This backend implementation is for testing purposes only and not meant for production use. This will be replaced
 // by a proper implementation once the PSTL implementation is somewhat stable.
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace __par_backend {
 inline namespace __thread_cpu_backend {
 
 template <class _RandomAccessIterator, class _Fp>
-_LIBCPP_HIDE_FROM_ABI void __parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Fp __f) {
+_LIBCPP_HIDE_FROM_ABI optional<__empty>
+__parallel_for(_RandomAccessIterator __first, _RandomAccessIterator __last, _Fp __f) {
   __f(__first, __last);
+  return __empty{};
 }
 
 template <class _Index, class _UnaryOp, class _Tp, class _BinaryOp, class _Reduce>
-_LIBCPP_HIDE_FROM_ABI _Tp
+_LIBCPP_HIDE_FROM_ABI optional<_Tp>
 __parallel_transform_reduce(_Index __first, _Index __last, _UnaryOp, _Tp __init, _BinaryOp, _Reduce __reduce) {
   return __reduce(std::move(__first), std::move(__last), std::move(__init));
 }
 
 template <class _RandomAccessIterator, class _Compare, class _LeafSort>
-_LIBCPP_HIDE_FROM_ABI void __parallel_stable_sort(
+_LIBCPP_HIDE_FROM_ABI optional<__empty> __parallel_stable_sort(
     _RandomAccessIterator __first, _RandomAccessIterator __last, _Compare __comp, _LeafSort __leaf_sort) {
   __leaf_sort(__first, __last, __comp);
+  return __empty{};
 }
 
 _LIBCPP_HIDE_FROM_ABI inline void __cancel_execution() {}
 
 template <class _RandomAccessIterator1,
           class _RandomAccessIterator2,
           class _RandomAccessIterator3,
           class _Compare,
           class _LeafMerge>
-_LIBCPP_HIDE_FROM_ABI void __parallel_merge(
+_LIBCPP_HIDE_FROM_ABI optional<__empty> __parallel_merge(
     _RandomAccessIterator1 __first1,
     _RandomAccessIterator1 __last1,
     _RandomAccessIterator2 __first2,
     _RandomAccessIterator2 __last2,
     _RandomAccessIterator3 __outit,
     _Compare __comp,
     _LeafMerge __leaf_merge) {
   __leaf_merge(__first1, __last1, __first2, __last2, __outit, __comp);
+  return __empty{};
 }
 
 } // namespace __thread_cpu_backend
 } // namespace __par_backend
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && && _LIBCPP_STD_VER >= 17
 
 _LIBCPP_POP_MACROS
 
 #endif // _LIBCPP___ALGORITHM_PSTL_BACKENDS_CPU_BACKENDS_THREAD_H

libcxx/include/__algorithm/pstl_backends/cpu_backends/transform.h

 #include <__algorithm/pstl_backends/cpu_backends/backend.h>
 #include <__algorithm/transform.h>
 #include <__config>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
-#include <__utility/terminate_on_exception.h>
+#include <optional>
 
 #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 _Iterator1, class _DifferenceType, class _Iterator2, class _Function>
 _LIBCPP_HIDE_FROM_ABI _Iterator2
 __simd_walk_2(_Iterator1 __first1, _DifferenceType __n, _Iterator2 __first2, _Function __f) noexcept {
   _PSTL_PRAGMA_SIMD
   for (_DifferenceType __i = 0; __i < __n; ++__i)
     __f(__first1[__i], __first2[__i]);
   return __first2 + __n;
 }
 
 template <class _ExecutionPolicy, class _ForwardIterator, class _ForwardOutIterator, class _UnaryOperation>
-_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator __pstl_transform(
+_LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> __pstl_transform(
     __cpu_backend_tag,
     _ForwardIterator __first,
     _ForwardIterator __last,
     _ForwardOutIterator __result,
     _UnaryOperation __op) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
                 __has_random_access_iterator_category_or_concept<_ForwardIterator>::value &&
                 __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) {
-    std::__terminate_on_exception([&] {
-      std::__par_backend::__parallel_for(
-          __first, __last, [__op, __first, __result](_ForwardIterator __brick_first, _ForwardIterator __brick_last) {
-            return std::__pstl_transform<__remove_parallel_policy_t<_ExecutionPolicy>>(
-                __cpu_backend_tag{}, __brick_first, __brick_last, __result + (__brick_first - __first), __op);
-          });
+          auto __res = std::__pstl_transform<__remove_parallel_policy_t<_ExecutionPolicy>>(
+          _LIBCPP_ASSERT_INTERNAL(__res, "unseq/seq should never try to allocate!");
+          return *std::move(__res);
         });
     return __result + (__last - __first);
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
                        __has_random_access_iterator_category_or_concept<_ForwardIterator>::value &&
                        __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) {
     return std::__simd_walk_2(
         __first,
         __last - __first,
         __result,
_LIBCPP_HIDE_FROM_ABI _Iterator3 __simd_walk_3(
   return __first3 + __n;
 }
 template <class _ExecutionPolicy,
           class _ForwardIterator1,
           class _ForwardIterator2,
           class _ForwardOutIterator,
           class _BinaryOperation,
           enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator __pstl_transform(
+_LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> __pstl_transform(
     __cpu_backend_tag,
     _ForwardIterator1 __first1,
     _ForwardIterator1 __last1,
     _ForwardIterator2 __first2,
     _ForwardOutIterator __result,
     _BinaryOperation __op) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
                 __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
                 __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value &&
                 __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) {
-    std::__terminate_on_exception([&] {
-      std::__par_backend::__parallel_for(
-          __first1,
-          __last1,
-          [__op, __first1, __first2, __result](_ForwardIterator1 __brick_first, _ForwardIterator1 __brick_last) {
-            return std::__pstl_transform<__remove_parallel_policy_t<_ExecutionPolicy>>(
-                __cpu_backend_tag{},
-                __brick_first,
-                __brick_last,
-                __first2 + (__brick_first - __first1),
-                __result + (__brick_first - __first1),
-                __op);
-          });
-    });
+    auto __res = std::__par_backend::__parallel_for(
+    if (!__res)
+      return nullopt;
     return __result + (__last1 - __first1);
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
                        __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
                        __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value &&
                        __has_random_access_iterator_category_or_concept<_ForwardOutIterator>::value) {
     return std::__simd_walk_3(
         __first1,
         __last1 - __first1,

libcxx/include/__algorithm/pstl_backends/cpu_backends/transform_reduce.h

 #include <__config>
 #include <__iterator/concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__numeric/transform_reduce.h>
 #include <__type_traits/is_arithmetic.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/operation_traits.h>
 #include <__utility/move.h>
-#include <__utility/terminate_on_exception.h>
 #include <new>
+#include <optional>
 
 #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 _ExecutionPolicy,
           class _ForwardIterator1,
           class _ForwardIterator2,
           class _Tp,
           class _BinaryOperation1,
           class _BinaryOperation2>
-_LIBCPP_HIDE_FROM_ABI _Tp __pstl_transform_reduce(
+_LIBCPP_HIDE_FROM_ABI optional<_Tp> __pstl_transform_reduce(
     __cpu_backend_tag,
     _ForwardIterator1 __first1,
     _ForwardIterator1 __last1,
     _ForwardIterator2 __first2,
     _Tp __init,
     _BinaryOperation1 __reduce,
     _BinaryOperation2 __transform) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
                 __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
                 __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
-    return std::__terminate_on_exception([&] {
-      return __par_backend::__parallel_transform_reduce(
-          __first1,
-          std::move(__last1),
-          [__first1, __first2, __transform](_ForwardIterator1 __iter) {
-            return __transform(*__iter, *(__first2 + (__iter - __first1)));
-          },
-          std::move(__init),
-          std::move(__reduce),
-          [__first1, __first2, __reduce, __transform](
-              _ForwardIterator1 __brick_first, _ForwardIterator1 __brick_last, _Tp __brick_init) {
-            return std::__pstl_transform_reduce<__remove_parallel_policy_t<_ExecutionPolicy>>(
-                __cpu_backend_tag{},
-                __brick_first,
-                std::move(__brick_last),
-                __first2 + (__brick_first - __first1),
-                std::move(__brick_init),
-                std::move(__reduce),
-                std::move(__transform));
-          });
-    });
+          return *std::__pstl_transform_reduce<__remove_parallel_policy_t<_ExecutionPolicy>>(
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
                        __has_random_access_iterator_category_or_concept<_ForwardIterator1>::value &&
                        __has_random_access_iterator_category_or_concept<_ForwardIterator2>::value) {
     return std::__simd_transform_reduce(
         __last1 - __first1, std::move(__init), std::move(__reduce), [&](__iter_diff_t<_ForwardIterator1> __i) {
           return __transform(__first1[__i], __first2[__i]);
         });
   } else {
     return std::transform_reduce(
         std::move(__first1),
         std::move(__last1),
         std::move(__first2),
         std::move(__init),
         std::move(__reduce),
         std::move(__transform));
   }
 }
 
 template <class _ExecutionPolicy, class _ForwardIterator, class _Tp, class _BinaryOperation, class _UnaryOperation>
-_LIBCPP_HIDE_FROM_ABI _Tp __pstl_transform_reduce(
+_LIBCPP_HIDE_FROM_ABI optional<_Tp> __pstl_transform_reduce(
     __cpu_backend_tag,
     _ForwardIterator __first,
     _ForwardIterator __last,
     _Tp __init,
     _BinaryOperation __reduce,
     _UnaryOperation __transform) {
   if constexpr (__is_parallel_execution_policy_v<_ExecutionPolicy> &&
                 __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
-    return std::__terminate_on_exception([&] {
-      return __par_backend::__parallel_transform_reduce(
-          std::move(__first),
-          std::move(__last),
-          [__transform](_ForwardIterator __iter) { return __transform(*__iter); },
-          std::move(__init),
-          __reduce,
-          [__transform, __reduce](auto __brick_first, auto __brick_last, _Tp __brick_init) {
-            return std::__pstl_transform_reduce<__remove_parallel_policy_t<_ExecutionPolicy>>(
-                __cpu_backend_tag{},
-                std::move(__brick_first),
-                std::move(__brick_last),
-                std::move(__brick_init),
-                std::move(__reduce),
-                std::move(__transform));
-          });
+          auto __res = std::__pstl_transform_reduce<__remove_parallel_policy_t<_ExecutionPolicy>>(
+          _LIBCPP_ASSERT_INTERNAL(__res, "unseq/seq should never try to allocate!");
+          return *std::move(__res);
         });
   } else if constexpr (__is_unsequenced_execution_policy_v<_ExecutionPolicy> &&
                        __has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
     return std::__simd_transform_reduce(
         __last - __first,
         std::move(__init),
         std::move(__reduce),
         [=, &__transform](__iter_diff_t<_ForwardIterator> __i) { return __transform(__first[__i]); });
   } else {

libcxx/include/__algorithm/pstl_copy.h

 #include <__functional/identity.h>
 #include <__iterator/concepts.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_constant_evaluated.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/is_trivially_copyable.h>
 #include <__type_traits/remove_cvref.h>
 #include <__utility/move.h>
+#include <optional>
 
 #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
 
 // TODO: Use the std::copy/move shenanigans to forward to std::memmove
 
 template <class>
 void __pstl_copy();
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _ForwardOutIterator,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator
-copy(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __result) {
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
+__copy(_ExecutionPolicy&& __policy,
+       _ForwardIterator&& __first,
+       _ForwardIterator&& __last,
+       _ForwardOutIterator&& __result) noexcept {
   return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_copy),
       [&__policy](_ForwardIterator __g_first, _ForwardIterator __g_last, _ForwardOutIterator __g_result) {
-        return std::transform(__policy, __g_first, __g_last, __g_result, __identity());
+        return std::__transform(__policy, __g_first, __g_last, __g_result, __identity());
       },
       std::move(__first),
       std::move(__last),
       std::move(__result));
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _ForwardOutIterator,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator
+copy(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __result) {
+  auto __res = std::__copy(__policy, std::move(__first), std::move(__last), std::move(__result));
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *std::move(__res);
+}
+
 template <class>
 void __pstl_copy_n();
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _ForwardOutIterator,
           class _Size,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator
-copy_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __n, _ForwardOutIterator __result) {
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator> __copy_n(
+    _ExecutionPolicy&& __policy, _ForwardIterator&& __first, _Size&& __n, _ForwardOutIterator&& __result) noexcept {
   return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_copy_n),
-      [&__policy](_ForwardIterator __g_first, _Size __g_n, _ForwardOutIterator __g_result) {
+      [&__policy](
+          _ForwardIterator __g_first, _Size __g_n, _ForwardOutIterator __g_result) -> optional<_ForwardIterator> {
         if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value)
-          return std::copy(__policy, __g_first, __g_first + __g_n, __g_result);
+          return std::__copy(__policy, __g_first, __g_first + __g_n, __g_result);
         else
           return std::copy_n(__g_first, __g_n, __g_result);
       },
       std::move(__first),
-      __n,
+      std::move(__n),
       std::move(__result));
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _ForwardOutIterator,
+          class _Size,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator
+copy_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __n, _ForwardOutIterator __result) {
+  auto __res = std::__copy_n(__policy, std::move(__first), std::move(__n), std::move(__result));
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *std::move(__res);
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_COPY_H

libcxx/include/__algorithm/pstl_count.h

 #include <__config>
 #include <__functional/operations.h>
 #include <__iterator/iterator_traits.h>
 #include <__numeric/pstl_transform_reduce.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
 #include <__utility/move.h>
-#include <__utility/terminate_on_exception.h>
+#include <optional>
 
 #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_count_if(); // declaration needed for the frontend dispatch below
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Predicate,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI __iter_diff_t<_ForwardIterator>
-count_if(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iter_diff_t<_ForwardIterator>> __count_if(
+    _ExecutionPolicy&& __policy, _ForwardIterator&& __first, _ForwardIterator&& __last, _Predicate&& __pred) noexcept {
   using __diff_t = __iter_diff_t<_ForwardIterator>;
   return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_count_if),
-      [&](_ForwardIterator __g_first, _ForwardIterator __g_last, _Predicate __g_pred) {
-        return std::transform_reduce(
+      [&](_ForwardIterator __g_first, _ForwardIterator __g_last, _Predicate __g_pred) -> optional<__diff_t> {
+        return std::__transform_reduce(
             __policy,
             std::move(__g_first),
             std::move(__g_last),
             __diff_t(),
             std::plus{},
             [&](__iter_reference<_ForwardIterator> __element) -> bool { return __g_pred(__element); });
       },
       std::move(__first),
       std::move(__last),
       std::move(__pred));
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Predicate,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI __iter_diff_t<_ForwardIterator>
+count_if(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
+  auto __res = std::__count_if(__policy, std::move(__first), std::move(__last), std::move(__pred));
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *std::move(__res);
+}
+
 template <class>
 void __pstl_count(); // declaration needed for the frontend dispatch below
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Tp,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI __iter_diff_t<_ForwardIterator>
-count(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__iter_diff_t<_ForwardIterator>>
+__count(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
   return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_count),
-      [&](_ForwardIterator __g_first, _ForwardIterator __g_last, const _Tp& __g_value) {
+      [&](_ForwardIterator __g_first, _ForwardIterator __g_last, const _Tp& __g_value)
+          -> optional<__iter_diff_t<_ForwardIterator>> {
         return std::count_if(__policy, __g_first, __g_last, [&](__iter_reference<_ForwardIterator> __v) {
           return __v == __g_value;
         });
       },
       std::move(__first),
       std::move(__last),
       __value);
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Tp,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI __iter_diff_t<_ForwardIterator>
+count(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
+  auto __res = std::__count(__policy, std::move(__first), std::move(__last), __value);
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *__res;
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_COUNT_H

libcxx/include/__algorithm/pstl_fill.h

 #include <__config>
 #include <__iterator/concepts.h>
 #include <__iterator/cpp17_iterator_concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
 #include <__utility/move.h>
-#include <__utility/terminate_on_exception.h>
+#include <optional>
 
 #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_fill(); // declaration needed for the frontend dispatch below
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Tp,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI void
-fill(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
+_LIBCPP_HIDE_FROM_ABI optional<__empty>
+__fill(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) noexcept {
   _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
-  std::__pstl_frontend_dispatch(
+  return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_fill),
       [&](_ForwardIterator __g_first, _ForwardIterator __g_last, const _Tp& __g_value) {
-        std::for_each(__policy, __g_first, __g_last, [&](__iter_reference<_ForwardIterator> __element) {
+        return std::__for_each(__policy, __g_first, __g_last, [&](__iter_reference<_ForwardIterator> __element) {
           __element = __g_value;
         });
       },
       std::move(__first),
       std::move(__last),
       __value);
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Tp,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void
+fill(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
+  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+  if (!std::__fill(__policy, std::move(__first), std::move(__last), __value))
+    std::__throw_bad_alloc();
+}
+
 template <class>
 void __pstl_fill_n(); // declaration needed for the frontend dispatch below
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _SizeT,
           class _Tp,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI void
-fill_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _SizeT __n, const _Tp& __value) {
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
+__fill_n(_ExecutionPolicy&& __policy, _ForwardIterator&& __first, _SizeT&& __n, const _Tp& __value) noexcept {
   _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
-  std::__pstl_frontend_dispatch(
+  return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_fill_n),
       [&](_ForwardIterator __g_first, _SizeT __g_n, const _Tp& __g_value) {
         if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value)
           std::fill(__policy, __g_first, __g_first + __g_n, __g_value);
         else
           std::fill_n(__g_first, __g_n, __g_value);
+        return optional<__empty>{__empty{}};
       },
       std::move(__first),
-      __n,
+      std::move(__n),
       __value);
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _SizeT,
+          class _Tp,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void
+fill_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _SizeT __n, const _Tp& __value) {
+  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+  if (!std::__fill_n(__policy, std::move(__first), std::move(__n), __value))
+    std::__throw_bad_alloc();
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_FILL_H

libcxx/include/__algorithm/pstl_find.h

 #include <__algorithm/pstl_backend.h>
 #include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
 #include <__iterator/cpp17_iterator_concepts.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
 #include <__utility/move.h>
-#include <__utility/terminate_on_exception.h>
+#include <optional>
 
 #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 _ExecutionPolicy,
           class _ForwardIterator,
           class _Predicate,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI _ForwardIterator
-find_if(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
-  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<remove_cvref_t<_ForwardIterator>>
+__find_if(_ExecutionPolicy&&, _ForwardIterator&& __first, _ForwardIterator&& __last, _Predicate&& __pred) noexcept {
   using _Backend = typename __select_backend<_RawPolicy>::type;
   return std::__pstl_find_if<_RawPolicy>(_Backend{}, std::move(__first), std::move(__last), std::move(__pred));
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Predicate,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _ForwardIterator
+find_if(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
+  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+  auto __res = std::__find_if(__policy, std::move(__first), std::move(__last), std::move(__pred));
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *std::move(__res);
+}
+
 template <class>
 void __pstl_find_if_not();
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Predicate,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI _ForwardIterator
-find_if_not(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
-  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<remove_cvref_t<_ForwardIterator>>
+__find_if_not(_ExecutionPolicy&& __policy, _ForwardIterator&& __first, _ForwardIterator&& __last, _Predicate&& __pred) {
   return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_find_if_not),
-      [&](_ForwardIterator __g_first, _ForwardIterator __g_last, _Predicate __g_pred) {
-        return std::find_if(__policy, __g_first, __g_last, [&](__iter_reference<_ForwardIterator> __value) {
+      [&](_ForwardIterator&& __g_first, _ForwardIterator&& __g_last, _Predicate&& __g_pred)
+          -> optional<remove_cvref_t<_ForwardIterator>> {
+        return std::__find_if(
+            __policy, __g_first, __g_last, [&](__iter_reference<remove_cvref_t<_ForwardIterator>> __value) {
               return !__g_pred(__value);
             });
       },
       std::move(__first),
       std::move(__last),
       std::move(__pred));
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Predicate,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _ForwardIterator
+find_if_not(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
+  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+  auto __res = std::__find_if_not(__policy, std::move(__first), std::move(__last), std::move(__pred));
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *std::move(__res);
+}
+
 template <class>
 void __pstl_find();
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Tp,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI _ForwardIterator
-find(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
-  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<remove_cvref_t<_ForwardIterator>>
+__find(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) noexcept {
   return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_find),
-      [&](_ForwardIterator __g_first, _ForwardIterator __g_last, const _Tp& __g_value) {
-        return std::find_if(__policy, __g_first, __g_last, [&](__iter_reference<_ForwardIterator> __element) {
+      [&](_ForwardIterator __g_first, _ForwardIterator __g_last, const _Tp& __g_value) -> optional<_ForwardIterator> {
+        return std::find_if(
+            __policy, __g_first, __g_last, [&](__iter_reference<remove_cvref_t<_ForwardIterator>> __element) {
               return __element == __g_value;
             });
       },
       std::move(__first),
       std::move(__last),
       __value);
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Tp,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _ForwardIterator
+find(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, const _Tp& __value) {
+  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+  auto __res = std::__find(__policy, std::move(__first), std::move(__last), __value);
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *std::move(__res);
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_FIND_H

libcxx/include/__algorithm/pstl_for_each.h

 #include <__config>
 #include <__iterator/concepts.h>
 #include <__iterator/cpp17_iterator_concepts.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
 #include <__type_traits/void_t.h>
 #include <__utility/move.h>
-#include <__utility/terminate_on_exception.h>
+#include <optional>
 
 #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 _ExecutionPolicy,
           class _ForwardIterator,
           class _Function,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
+__for_each(_ExecutionPolicy&&, _ForwardIterator&& __first, _ForwardIterator&& __last, _Function&& __func) {
+  using _Backend = typename __select_backend<_RawPolicy>::type;
+  return std::__pstl_for_each<_RawPolicy>(_Backend{}, std::move(__first), std::move(__last), std::move(__func));
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Function,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI void
-for_each(_ExecutionPolicy&&, _ForwardIterator __first, _ForwardIterator __last, _Function __func) {
+for_each(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Function __func) {
   _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
-  using _Backend = typename __select_backend<_RawPolicy>::type;
-  std::__pstl_for_each<_RawPolicy>(_Backend{}, std::move(__first), std::move(__last), std::move(__func));
+  if (!std::__for_each(__policy, std::move(__first), std::move(__last), std::move(__func)))
+    std::__throw_bad_alloc();
 }
 
 template <class>
 void __pstl_for_each_n(); // declaration needed for the frontend dispatch below
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Size,
           class _Function,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI void
-for_each_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __size, _Function __func) {
-  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
+__for_each_n(_ExecutionPolicy&& __policy, _ForwardIterator&& __first, _Size&& __size, _Function&& __func) {
   return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_for_each_n),
-      [&](_ForwardIterator __g_first, _Size __g_size, _Function __g_func) {
+      [&](_ForwardIterator __g_first, _Size __g_size, _Function __g_func) -> optional<__empty> {
         if constexpr (__has_random_access_iterator_category_or_concept<_ForwardIterator>::value) {
           std::for_each(__policy, std::move(__g_first), __g_first + __g_size, std::move(__g_func));
+          return __empty{};
         } else {
           std::for_each_n(std::move(__g_first), __g_size, std::move(__g_func));
+          return __empty{};
         }
       },
-      __first,
-      __size,
+      std::move(__first),
+      std::move(__size),
       std::move(__func));
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Size,
+          class _Function,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void
+for_each_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __size, _Function __func) {
+  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+  auto __res = std::__for_each_n(__policy, std::move(__first), std::move(__size), std::move(__func));
+  if (!__res)
+    std::__throw_bad_alloc();
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_FOR_EACH_H

libcxx/include/__algorithm/pstl_generate.h

 #include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
 #include <__iterator/cpp17_iterator_concepts.h>
 #include <__iterator/iterator_traits.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
 #include <__utility/move.h>
+#include <optional>
 
 #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_generate();
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Generator,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI void
-generate(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Generator __gen) {
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
+__generate(_ExecutionPolicy&& __policy, _ForwardIterator&& __first, _ForwardIterator&& __last, _Generator&& __gen) {
   _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
-  std::__pstl_frontend_dispatch(
+  return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_generate),
       [&__policy](_ForwardIterator __g_first, _ForwardIterator __g_last, _Generator __g_gen) {
-        std::for_each(
+        return std::__for_each(
             __policy, std::move(__g_first), std::move(__g_last), [&](__iter_reference<_ForwardIterator> __element) {
               __element = __g_gen();
             });
       },
       std::move(__first),
       std::move(__last),
       std::move(__gen));
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Generator,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void
+generate(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Generator __gen) {
+  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+  if (!std::__generate(__policy, std::move(__first), std::move(__last), std::move(__gen)))
+    std::__throw_bad_alloc();
+}
+
 template <class>
 void __pstl_generate_n();
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Size,
           class _Generator,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI void
-generate_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __n, _Generator __gen) {
-  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
-  std::__pstl_frontend_dispatch(
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
+__generate_n(_ExecutionPolicy&& __policy, _ForwardIterator&& __first, _Size&& __n, _Generator&& __gen) {
+  return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_generate_n),
       [&__policy](_ForwardIterator __g_first, _Size __g_n, _Generator __g_gen) {
-        std::for_each_n(__policy, std::move(__g_first), __g_n, [&](__iter_reference<_ForwardIterator> __element) {
+        return std::__for_each_n(
+            __policy, std::move(__g_first), std::move(__g_n), [&](__iter_reference<_ForwardIterator> __element) {
               __element = __g_gen();
             });
       },
       std::move(__first),
       __n,
       std::move(__gen));
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Size,
+          class _Generator,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void
+generate_n(_ExecutionPolicy&& __policy, _ForwardIterator __first, _Size __n, _Generator __gen) {
+  _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
+  if (!std::__generate_n(__policy, std::move(__first), std::move(__n), std::move(__gen)))
+    std::__throw_bad_alloc();
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_GENERATE_H

libcxx/include/__algorithm/pstl_is_partitioned.h

 #include <__algorithm/pstl_backend.h>
 #include <__algorithm/pstl_find.h>
 #include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
 #include <__utility/move.h>
+#include <optional>
 
 #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) {
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<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));
 }
 
+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) {
+  auto __res = std::__is_partitioned(__policy, std::move(__first), std::move(__last), std::move(__pred));
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *std::move(__res);
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_IS_PARITTIONED

libcxx/include/__algorithm/pstl_merge.h

 
 #include <__algorithm/pstl_backend.h>
 #include <__config>
 #include <__functional/operations.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
 #include <__utility/move.h>
+#include <optional>
 
 #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 _ExecutionPolicy,
           class _ForwardIterator1,
           class _ForwardIterator2,
           class _ForwardOutIterator,
           class _Comp                                         = std::less<>,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator
-merge(_ExecutionPolicy&&,
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<_ForwardOutIterator>
+__merge(_ExecutionPolicy&&,
         _ForwardIterator1 __first1,
         _ForwardIterator1 __last1,
         _ForwardIterator2 __first2,
         _ForwardIterator2 __last2,
         _ForwardOutIterator __result,
-      _Comp __comp = {}) {
+        _Comp __comp = {}) noexcept {
   using _Backend = typename __select_backend<_RawPolicy>::type;
   return std::__pstl_merge<_RawPolicy>(
       _Backend{},
       std::move(__first1),
       std::move(__last1),
       std::move(__first2),
       std::move(__last2),
       std::move(__result),
       std::move(__comp));
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator1,
+          class _ForwardIterator2,
+          class _ForwardOutIterator,
+          class _Comp                                         = std::less<>,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _ForwardOutIterator
+merge(_ExecutionPolicy&& __policy,
+      _ForwardIterator1 __first1,
+      _ForwardIterator1 __last1,
+      _ForwardIterator2 __first2,
+      _ForwardIterator2 __last2,
+      _ForwardOutIterator __result,
+      _Comp __comp = {}) {
+  auto __res = std::__merge(
+      __policy,
+      std::move(__first1),
+      std::move(__last1),
+      std::move(__first2),
+      std::move(__last2),
+      std::move(__result),
+      std::move(__comp));
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *std::move(__res);
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_MERGE_H

libcxx/include/__algorithm/pstl_replace.h

 #include <__algorithm/pstl_for_each.h>
 #include <__algorithm/pstl_frontend_dispatch.h>
 #include <__algorithm/pstl_transform.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/remove_cvref.h>
 #include <__utility/move.h>
+#include <optional>
 
 #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_replace_if();
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Pred,
           class _Tp,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI void
-replace_if(_ExecutionPolicy&& __policy,
-           _ForwardIterator __first,
-           _ForwardIterator __last,
-           _Pred __pred,
-           const _Tp& __new_value) {
-  std::__pstl_frontend_dispatch(
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
+__replace_if(_ExecutionPolicy&& __policy,
+             _ForwardIterator&& __first,
+             _ForwardIterator&& __last,
+             _Pred&& __pred,
+             const _Tp& __new_value) noexcept {
+  return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_replace_if),
-      [&__policy](_ForwardIterator __g_first, _ForwardIterator __g_last, _Pred __g_pred, const _Tp& __g_new_value) {
+      [&__policy](
+          _ForwardIterator&& __g_first, _ForwardIterator&& __g_last, _Pred&& __g_pred, const _Tp& __g_new_value) {
         std::for_each(__policy, __g_first, __g_last, [&](__iter_reference<_ForwardIterator> __element) {
           if (__g_pred(__element))
             __element = __g_new_value;
         });
+        return optional<__empty>{__empty{}};
       },
       std::move(__first),
       std::move(__last),
       std::move(__pred),
       __new_value);
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Pred,
+          class _Tp,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void
+replace_if(_ExecutionPolicy&& __policy,
+           _ForwardIterator __first,
+           _ForwardIterator __last,
+           _Pred __pred,
+           const _Tp& __new_value) {
+  auto __res = std::__replace_if(__policy, std::move(__first), std::move(__last), std::move(__pred), __new_value);
+  if (!__res)
+    std::__throw_bad_alloc();
+}
+
 template <class>
 void __pstl_replace();
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Tp,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI void
-replace(_ExecutionPolicy&& __policy,
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty>
+__replace(_ExecutionPolicy&& __policy,
           _ForwardIterator __first,
           _ForwardIterator __last,
           const _Tp& __old_value,
-        const _Tp& __new_value) {
-  std::__pstl_frontend_dispatch(
+          const _Tp& __new_value) noexcept {
+  return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_replace),
       [&__policy](
           _ForwardIterator __g_first, _ForwardIterator __g_last, const _Tp& __g_old_value, const _Tp& __g_new_value) {
-        std::replace_if(
+        return std::__replace_if(
             __policy,
             std::move(__g_first),
             std::move(__g_last),
             [&](__iter_reference<_ForwardIterator> __element) { return __element == __g_old_value; },
             __g_new_value);
       },
       std::move(__first),
       std::move(__last),
       __old_value,
       __new_value);
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Tp,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void
+replace(_ExecutionPolicy&& __policy,
+        _ForwardIterator __first,
+        _ForwardIterator __last,
+        const _Tp& __old_value,
+        const _Tp& __new_value) {
+  if (!std::__replace(__policy, std::move(__first), std::move(__last), __old_value, __new_value))
+    std::__throw_bad_alloc();
+}
+
 template <class>
 void __pstl_replace_copy_if();
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _ForwardOutIterator,
           class _Pred,
           class _Tp,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI void replace_copy_if(
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> __replace_copy_if(
     _ExecutionPolicy&& __policy,
-    _ForwardIterator __first,
-    _ForwardIterator __last,
-    _ForwardOutIterator __result,
-    _Pred __pred,
+    _ForwardIterator&& __first,
+    _ForwardIterator&& __last,
+    _ForwardOutIterator&& __result,
+    _Pred&& __pred,
     const _Tp& __new_value) {
-  std::__pstl_frontend_dispatch(
+  return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_replace_copy_if),
       [&__policy](_ForwardIterator __g_first,
                   _ForwardIterator __g_last,
                   _ForwardOutIterator __g_result,
                   _Pred __g_pred,
-                  const _Tp& __g_new_value) {
-        std::transform(__policy, __g_first, __g_last, __g_result, [&](__iter_reference<_ForwardIterator> __element) {
+                  const _Tp& __g_new_value) -> optional<__empty> {
+        if (!std::__transform(
+                __policy, __g_first, __g_last, __g_result, [&](__iter_reference<_ForwardIterator> __element) {
                   return __g_pred(__element) ? __g_new_value : __element;
-        });
+                }))
+          return nullopt;
+        return __empty{};
       },
       std::move(__first),
       std::move(__last),
       std::move(__result),
       std::move(__pred),
       __new_value);
 }
 
-template <class>
-void __pstl_replace_copy();
-
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _ForwardOutIterator,
+          class _Pred,
           class _Tp,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI void replace_copy(
+_LIBCPP_HIDE_FROM_ABI void replace_copy_if(
     _ExecutionPolicy&& __policy,
     _ForwardIterator __first,
     _ForwardIterator __last,
     _ForwardOutIterator __result,
-    const _Tp& __old_value,
+    _Pred __pred,
     const _Tp& __new_value) {
-  std::__pstl_frontend_dispatch(
+  if (!std::__replace_copy_if(
+          __policy, std::move(__first), std::move(__last), std::move(__result), std::move(__pred), __new_value))
+    std::__throw_bad_alloc();
+}
+
+template <class>
+void __pstl_replace_copy();
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _ForwardOutIterator,
+          class _Tp,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> __replace_copy(
+    _ExecutionPolicy&& __policy,
+    _ForwardIterator&& __first,
+    _ForwardIterator&& __last,
+    _ForwardOutIterator&& __result,
+    const _Tp& __old_value,
+    const _Tp& __new_value) noexcept {
+  return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_replace_copy),
       [&__policy](_ForwardIterator __g_first,
                   _ForwardIterator __g_last,
                   _ForwardOutIterator __g_result,
                   const _Tp& __g_old_value,
                   const _Tp& __g_new_value) {
-        return std::replace_copy_if(
+        return std::__replace_copy_if(
             __policy,
             std::move(__g_first),
             std::move(__g_last),
             std::move(__g_result),
             [&](__iter_reference<_ForwardIterator> __element) { return __element == __g_old_value; },
             __g_new_value);
       },
       std::move(__first),
       std::move(__last),
       std::move(__result),
       __old_value,
       __new_value);
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _ForwardOutIterator,
+          class _Tp,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void replace_copy(
+    _ExecutionPolicy&& __policy,
+    _ForwardIterator __first,
+    _ForwardIterator __last,
+    _ForwardOutIterator __result,
+    const _Tp& __old_value,
+    const _Tp& __new_value) {
+  if (!std::__replace_copy(
+          __policy, std::move(__first), std::move(__last), std::move(__result), __old_value, __new_value))
+    std::__throw_bad_alloc();
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_REPLACE_H

libcxx/include/__algorithm/pstl_sort.h

 #include <__algorithm/pstl_frontend_dispatch.h>
 #include <__algorithm/pstl_stable_sort.h>
 #include <__config>
 #include <__functional/operations.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
 #include <__utility/forward.h>
 #include <__utility/move.h>
+#include <optional>
 
 #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_sort();
 
 template <class _ExecutionPolicy,
           class _RandomAccessIterator,
           class _Comp,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI void
-sort(_ExecutionPolicy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) {
-  std::__pstl_frontend_dispatch(
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> __sort(
+    _ExecutionPolicy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) noexcept {
+  return std::__pstl_frontend_dispatch(
       _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_sort),
       [&__policy](_RandomAccessIterator __g_first, _RandomAccessIterator __g_last, _Comp __g_comp) {
         std::stable_sort(__policy, std::move(__g_first), std::move(__g_last), std::move(__g_comp));
+        return optional<__empty>{__empty{}};
       },
       std::move(__first),
       std::move(__last),
       std::move(__comp));
 }
 
 template <class _ExecutionPolicy,
           class _RandomAccessIterator,
+          class _Comp,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void
+sort(_ExecutionPolicy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp) {
+  if (!std::__sort(__policy, std::move(__first), std::move(__last), std::move(__comp)))
+    std::__throw_bad_alloc();
+}
+
+template <class _ExecutionPolicy,
+          class _RandomAccessIterator,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI void
 sort(_ExecutionPolicy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last) {
   std::sort(std::forward<_ExecutionPolicy>(__policy), std::move(__first), std::move(__last), less{});
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_SORT_H

libcxx/include/__algorithm/pstl_stable_sort.h

 
 #include <__algorithm/pstl_backend.h>
 #include <__config>
 #include <__functional/operations.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
 #include <__utility/move.h>
+#include <optional>
 
 #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 _ExecutionPolicy,
           class _RandomAccessIterator,
           class _Comp                                         = less<>,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI void
-stable_sort(_ExecutionPolicy&&, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp = {}) {
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<__empty> __stable_sort(
+    _ExecutionPolicy&&, _RandomAccessIterator&& __first, _RandomAccessIterator&& __last, _Comp&& __comp = {}) noexcept {
   using _Backend = typename __select_backend<_RawPolicy>::type;
-  std::__pstl_stable_sort<_RawPolicy>(_Backend{}, std::move(__first), std::move(__last), std::move(__comp));
+  return std::__pstl_stable_sort<_RawPolicy>(_Backend{}, std::move(__first), std::move(__last), std::move(__comp));
+}
+
+template <class _ExecutionPolicy,
+          class _RandomAccessIterator,
+          class _Comp                                         = less<>,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI void stable_sort(
+    _ExecutionPolicy&& __policy, _RandomAccessIterator __first, _RandomAccessIterator __last, _Comp __comp = {}) {
+  if (!std::__stable_sort(__policy, std::move(__first), std::move(__last), std::move(__comp)))
+    std::__throw_bad_alloc();
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_STABLE_SORT_H

libcxx/include/__algorithm/pstl_transform.h

 
 #include <__algorithm/pstl_backend.h>
 #include <__config>
 #include <__iterator/cpp17_iterator_concepts.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__type_traits/remove_cvref.h>
 #include <__utility/move.h>
-#include <__utility/terminate_on_exception.h>
+#include <optional>
 
 #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 _ExecutionPolicy,
           class _ForwardIterator,
           class _ForwardOutIterator,
           class _UnaryOperation,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<remove_cvref_t<_ForwardOutIterator>>
+__transform(_ExecutionPolicy&&,
+            _ForwardIterator&& __first,
+            _ForwardIterator&& __last,
+            _ForwardOutIterator&& __result,
+            _UnaryOperation&& __op) noexcept {
+  using _Backend = typename __select_backend<_RawPolicy>::type;
+  return std::__pstl_transform<_RawPolicy>(
+      _Backend{}, std::move(__first), std::move(__last), std::move(__result), std::move(__op));
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _ForwardOutIterator,
+          class _UnaryOperation,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI _ForwardOutIterator transform(
-    _ExecutionPolicy&&,
+    _ExecutionPolicy&& __policy,
     _ForwardIterator __first,
     _ForwardIterator __last,
     _ForwardOutIterator __result,
     _UnaryOperation __op) {
   _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator);
   _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardOutIterator);
   _LIBCPP_REQUIRE_CPP17_OUTPUT_ITERATOR(_ForwardOutIterator, decltype(__op(*__first)));
+  auto __res = std::__transform(__policy, std::move(__first), std::move(__last), std::move(__result), std::move(__op));
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *std::move(__res);
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator1,
+          class _ForwardIterator2,
+          class _ForwardOutIterator,
+          class _BinaryOperation,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI optional<remove_cvref_t<_ForwardOutIterator>>
+__transform(_ExecutionPolicy&&,
+            _ForwardIterator1&& __first1,
+            _ForwardIterator1&& __last1,
+            _ForwardIterator2&& __first2,
+            _ForwardOutIterator&& __result,
+            _BinaryOperation&& __op) noexcept {
   using _Backend = typename __select_backend<_RawPolicy>::type;
   return std::__pstl_transform<_RawPolicy>(
-      _Backend{}, std::move(__first), std::move(__last), std::move(__result), std::move(__op));
+      _Backend{}, std::move(__first1), std::move(__last1), std::move(__first2), std::move(__result), std::move(__op));
 }
 
 template <class _ExecutionPolicy,
           class _ForwardIterator1,
           class _ForwardIterator2,
           class _ForwardOutIterator,
           class _BinaryOperation,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI _ForwardOutIterator transform(
-    _ExecutionPolicy&&,
+    _ExecutionPolicy&& __policy,
     _ForwardIterator1 __first1,
     _ForwardIterator1 __last1,
     _ForwardIterator2 __first2,
     _ForwardOutIterator __result,
     _BinaryOperation __op) {
   _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator1);
   _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardIterator2);
   _LIBCPP_REQUIRE_CPP17_FORWARD_ITERATOR(_ForwardOutIterator);
   _LIBCPP_REQUIRE_CPP17_OUTPUT_ITERATOR(_ForwardOutIterator, decltype(__op(*__first1, *__first2)));
-  using _Backend = typename __select_backend<_RawPolicy>::type;
-  return std::__pstl_transform<_RawPolicy>(
-      _Backend{}, std::move(__first1), std::move(__last1), std::move(__first2), std::move(__result), std::move(__op));
+  auto __res = std::__transform(
+      __policy, std::move(__first1), std::move(__last1), std::move(__first2), std::move(__result), std::move(__op));
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *std::move(__res);
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_TRANSFORM_H

libcxx/include/__numeric/pstl_transform_reduce.h

 
 #include <__algorithm/pstl_backend.h>
 #include <__algorithm/pstl_frontend_dispatch.h>
 #include <__config>
 #include <__functional/operations.h>
 #include <__numeric/transform_reduce.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__utility/move.h>
-#include <__utility/terminate_on_exception.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 _ExecutionPolicy,
           class _ForwardIterator1,
           class _ForwardIterator2,
           class _Tp,
           class _BinaryOperation1,
           class _BinaryOperation2,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI _Tp transform_reduce(
+_LIBCPP_HIDE_FROM_ABI optional<_Tp> __transform_reduce(
     _ExecutionPolicy&&,
+    _ForwardIterator1&& __first1,
+    _ForwardIterator1&& __last1,
+    _ForwardIterator2&& __first2,
+    _Tp&& __init,
+    _BinaryOperation1&& __reduce,
+    _BinaryOperation2&& __transform) noexcept {
+  using _Backend = typename __select_backend<_RawPolicy>::type;
+  return std::__pstl_transform_reduce<_RawPolicy>(
+      _Backend{},
+      std::move(__first1),
+      std::move(__last1),
+      std::move(__first2),
+      std::move(__init),
+      std::move(__reduce),
+      std::move(__transform));
+}
+
+template <class _ExecutionPolicy,
+          class _ForwardIterator1,
+          class _ForwardIterator2,
+          class _Tp,
+          class _BinaryOperation1,
+          class _BinaryOperation2,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _Tp transform_reduce(
+    _ExecutionPolicy&& __policy,
     _ForwardIterator1 __first1,
     _ForwardIterator1 __last1,
     _ForwardIterator2 __first2,
     _Tp __init,
     _BinaryOperation1 __reduce,
     _BinaryOperation2 __transform) {
-  using _Backend = typename __select_backend<_RawPolicy>::type;
-  return std::__pstl_transform_reduce<_RawPolicy>(
-      _Backend{},
+  auto __res = std::__transform_reduce(
+      __policy,
       std::move(__first1),
       std::move(__last1),
       std::move(__first2),
       std::move(__init),
       std::move(__reduce),
       std::move(__transform));
+
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *std::move(__res);
 }
 
 // This overload doesn't get a customization point because it's trivial to detect (through e.g.
 // __is_trivial_plus_operation) when specializing the more general variant, which should always be preferred
 template <class _ExecutionPolicy,
           class _ForwardIterator1,
           class _ForwardIterator2,
           class _Tp,
           enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI _Tp transform_reduce(
     _ExecutionPolicy&& __policy,
     _ForwardIterator1 __first1,
     _ForwardIterator1 __last1,
     _ForwardIterator2 __first2,
     _Tp __init) {
   return std::transform_reduce(__policy, __first1, __last1, __first2, __init, plus{}, multiplies{});
 }
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Tp,
           class _BinaryOperation,
           class _UnaryOperation,
           class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
           enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
-_LIBCPP_HIDE_FROM_ABI _Tp transform_reduce(
+[[nodiscard]] _LIBCPP_HIDE_FROM_ABI optional<remove_cvref_t<_Tp>> __transform_reduce(
     _ExecutionPolicy&&,
-    _ForwardIterator __first,
-    _ForwardIterator __last,
-    _Tp __init,
-    _BinaryOperation __reduce,
-    _UnaryOperation __transform) {
+    _ForwardIterator&& __first,
+    _ForwardIterator&& __last,
+    _Tp&& __init,
+    _BinaryOperation&& __reduce,
+    _UnaryOperation&& __transform) noexcept {
   using _Backend = typename __select_backend<_RawPolicy>::type;
   return std::__pstl_transform_reduce<_RawPolicy>(
       _Backend{},
       std::move(__first),
       std::move(__last),
       std::move(__init),
       std::move(__reduce),
       std::move(__transform));
 }
 
+template <class _ExecutionPolicy,
+          class _ForwardIterator,
+          class _Tp,
+          class _BinaryOperation,
+          class _UnaryOperation,
+          class _RawPolicy                                    = __remove_cvref_t<_ExecutionPolicy>,
+          enable_if_t<is_execution_policy_v<_RawPolicy>, int> = 0>
+_LIBCPP_HIDE_FROM_ABI _Tp transform_reduce(
+    _ExecutionPolicy&& __policy,
+    _ForwardIterator __first,
+    _ForwardIterator __last,
+    _Tp __init,
+    _BinaryOperation __reduce,
+    _UnaryOperation __transform) {
+  auto __res = std::__transform_reduce(
+      __policy, std::move(__first), std::move(__last), std::move(__init), std::move(__reduce), std::move(__transform));
+  if (!__res)
+    std::__throw_bad_alloc();
+  return *std::move(__res);
+}
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___NUMERIC_PSTL_TRANSFORM_REDUCE_H

libcxx/include/__utility/empty.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___UTILITY_EMPTY_H
+#define _LIBCPP___UTILITY_EMPTY_H
+
+#include <__config>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+struct __empty {};
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___UTILITY_EMPTY_H

libcxx/include/__utility/terminate_on_exception.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___UTILITY_TERMINATE_ON_EXCEPTION_H
-#define _LIBCPP___UTILITY_TERMINATE_ON_EXCEPTION_H
-
-#include <__config>
-#include <__exception/terminate.h>
-#include <new>
-
-#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
-#  pragma GCC system_header
-#endif
-
-#if _LIBCPP_STD_VER >= 17
-
-_LIBCPP_BEGIN_NAMESPACE_STD
-
-#  ifndef _LIBCPP_HAS_NO_EXCEPTIONS
-
-template <class _Func>
-_LIBCPP_HIDE_FROM_ABI auto __terminate_on_exception(_Func __func) {
-  try {
-    return __func();
-  } catch (...) {
-    std::terminate();
-  }
-}
-
-#  else // _LIBCPP_HAS_NO_EXCEPTIONS
-
-template <class _Func>
-_LIBCPP_HIDE_FROM_ABI auto __terminate_on_exception(_Func __func) {
-  return __func();
-}
-
-#  endif // _LIBCPP_HAS_NO_EXCEPTIONS
-
-_LIBCPP_END_NAMESPACE_STD
-
-#endif // _LIBCPP_STD_VER >= 17
-
-#endif // _LIBCPP___UTILITY_TERMINATE_ON_EXCEPTION_H

libcxx/include/module.modulemap.in

module std_private_utility_auto_cast              [system] {
   export std_private_type_traits_decay
 }
 module std_private_utility_cmp                    [system] {
   header "__utility/cmp.h"
   export std_private_type_traits_make_unsigned
 }
 module std_private_utility_convert_to_integral    [system] { header "__utility/convert_to_integral.h" }
 module std_private_utility_declval                [system] { header "__utility/declval.h" }
+module std_private_utility_empty                  [system] { header "__utility/empty.h" }
 module std_private_utility_exception_guard        [system] { header "__utility/exception_guard.h" }
 module std_private_utility_exchange               [system] { header "__utility/exchange.h" }
 module std_private_utility_forward                [system] { header "__utility/forward.h" }
 module std_private_utility_forward_like           [system] { header "__utility/forward_like.h" }
 module std_private_utility_in_place               [system] { header "__utility/in_place.h" }
 module std_private_utility_integer_sequence       [system] { header "__utility/integer_sequence.h" }
 module std_private_utility_is_pointer_in_range    [system] { header "__utility/is_pointer_in_range.h" }
 module std_private_utility_move                   [system] {

 module std_private_utility_pair_fwd               [system] { header "__fwd/pair.h" }
 module std_private_utility_piecewise_construct    [system] { header "__utility/piecewise_construct.h" }
 module std_private_utility_priority_tag           [system] { header "__utility/priority_tag.h" }
 module std_private_utility_rel_ops                [system] { header "__utility/rel_ops.h" }
 module std_private_utility_swap                   [system] {
   header "__utility/swap.h"
   export std_private_type_traits_is_swappable
 }
-module std_private_utility_terminate_on_exception [system] { header "__utility/terminate_on_exception.h" }
 module std_private_utility_to_underlying          [system] { header "__utility/to_underlying.h" }
 module std_private_utility_unreachable            [system] { header "__utility/unreachable.h" }
 
 module std_private_variant_monostate [system] { header "__variant/monostate.h" }

libcxx/test/libcxx/transitive_includes/cxx03.csv

 algorithm cwchar
 algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
 algorithm limits
 algorithm memory
 algorithm new
+algorithm optional
 algorithm ratio
 algorithm stdexcept
 algorithm type_traits
 algorithm utility
 algorithm version
 any atomic
 any chrono
 any concepts

 numeric cstring
 numeric ctime
 numeric execution
 numeric functional
 numeric initializer_list
 numeric iterator
 numeric limits
 numeric new
+numeric optional
 numeric ratio
 numeric type_traits
 numeric version
 optional atomic
 optional climits
 optional compare
 optional concepts
 optional cstddef

libcxx/test/libcxx/transitive_includes/cxx11.csv

 algorithm cwchar
 algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
 algorithm limits
 algorithm memory
 algorithm new
+algorithm optional
 algorithm ratio
 algorithm stdexcept
 algorithm type_traits
 algorithm utility
 algorithm version
 any atomic
 any chrono
 any concepts

 numeric cstring
 numeric ctime
 numeric execution
 numeric functional
 numeric initializer_list
 numeric iterator
 numeric limits
 numeric new
+numeric optional
 numeric ratio
 numeric type_traits
 numeric version
 optional atomic
 optional climits
 optional compare
 optional concepts
 optional cstddef

libcxx/test/libcxx/transitive_includes/cxx14.csv

 algorithm cwchar
 algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
 algorithm limits
 algorithm memory
 algorithm new
+algorithm optional
 algorithm ratio
 algorithm stdexcept
 algorithm type_traits
 algorithm utility
 algorithm version
 any atomic
 any chrono
 any concepts

 numeric cstring
 numeric ctime
 numeric execution
 numeric functional
 numeric initializer_list
 numeric iterator
 numeric limits
 numeric new
+numeric optional
 numeric ratio
 numeric type_traits
 numeric version
 optional atomic
 optional climits
 optional compare
 optional concepts
 optional cstddef

libcxx/test/libcxx/transitive_includes/cxx17.csv

 algorithm cwchar
 algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
 algorithm limits
 algorithm memory
 algorithm new
+algorithm optional
 algorithm ratio
 algorithm stdexcept
 algorithm type_traits
 algorithm utility
 algorithm version
 any atomic
 any chrono
 any concepts

 numeric cstring
 numeric ctime
 numeric execution
 numeric functional
 numeric initializer_list
 numeric iterator
 numeric limits
 numeric new
+numeric optional
 numeric ratio
 numeric type_traits
 numeric version
 optional atomic
 optional climits
 optional compare
 optional concepts
 optional cstddef

libcxx/test/libcxx/transitive_includes/cxx20.csv

 algorithm cwchar
 algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm iterator
 algorithm limits
 algorithm memory
 algorithm new
+algorithm optional
 algorithm ratio
 algorithm stdexcept
 algorithm type_traits
 algorithm utility
 algorithm version
 any atomic
 any concepts
 any cstddef

 numeric cstring
 numeric ctime
 numeric execution
 numeric functional
 numeric initializer_list
 numeric iterator
 numeric limits
 numeric new
+numeric optional
 numeric ratio
 numeric type_traits
 numeric version
 optional atomic
 optional climits
 optional compare
 optional concepts
 optional cstddef

libcxx/test/libcxx/transitive_includes/cxx23.csv

 algorithm climits
 algorithm cstddef
 algorithm cstdint
 algorithm cstring
 algorithm ctime
 algorithm cwchar
 algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm limits
 algorithm new
+algorithm optional
 algorithm ratio
 algorithm version
 any cstddef
 any cstdint
 any cstring
 any initializer_list
 any limits
 any new

 numeric cstddef
 numeric cstdint
 numeric cstring
 numeric ctime
 numeric execution
 numeric initializer_list
 numeric limits
 numeric new
+numeric optional
 numeric ratio
 numeric version
 optional compare
 optional cstddef
 optional cstdint
 optional cstring
 optional initializer_list
 optional limits

libcxx/test/libcxx/transitive_includes/cxx26.csv

 algorithm climits
 algorithm cstddef
 algorithm cstdint
 algorithm cstring
 algorithm ctime
 algorithm cwchar
 algorithm execution
 algorithm initializer_list
 algorithm iosfwd
 algorithm limits
 algorithm new
+algorithm optional
 algorithm ratio
 algorithm version
 any cstddef
 any cstdint
 any cstring
 any initializer_list
 any limits
 any new

 numeric cstddef
 numeric cstdint
 numeric cstring
 numeric ctime
 numeric execution
 numeric initializer_list
 numeric limits
 numeric new
+numeric optional
 numeric ratio
 numeric version
 optional compare
 optional cstddef
 optional cstdint
 optional cstring
 optional initializer_list
 optional limits

libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.exception_handling.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: no-exceptions
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// check that std::fill(ExecutionPolicy) and std::fill_n(ExecutionPolicy) terminate on user-thrown exceptions
+
+#include <algorithm>
+
+#include "check_assertion.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+struct ThrowOnCopy {
+  ThrowOnCopy& operator=(const ThrowOnCopy&) { throw int{}; }
+};
+#endif
+
+int main(int, char**) {
+  ThrowOnCopy a[2]{};
+  int b[2]{};
+
+  test_execution_policies([&](auto&& policy) {
+    // std::fill
+    EXPECT_STD_TERMINATE([&] { (void)std::fill(policy, std::begin(a), std::end(a), ThrowOnCopy{}); });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        (void)std::fill(
+            policy, util::throw_on_move_iterator(std::begin(b), 1), util::throw_on_move_iterator(std::end(b), 1), 0);
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+
+    // std::fill_n
+    EXPECT_STD_TERMINATE([&] { (void)std::fill_n(policy, std::begin(a), std::size(a), ThrowOnCopy{}); });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        (void)std::fill_n(policy, util::throw_on_move_iterator(std::begin(b), 1), std::size(b), 0);
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+  });
+}

libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill.pass.cpp

 #include <algorithm>
 #include <cassert>
 #include <vector>
 
 #include "test_macros.h"
 #include "test_execution_policies.h"
 #include "test_iterators.h"
 
 EXECUTION_POLICY_SFINAE_TEST(fill);
 
 static_assert(sfinae_test_fill<int, int*, int*, bool (*)(int)>);
 static_assert(!sfinae_test_fill<std::execution::parallel_policy, int*, int*, int>);
 
 template <class Iter>
 struct Test {
   template <class Policy>
   void operator()(Policy&& policy) {
void operator()(Policy&& policy) {
     { // check that a large range works
       std::vector<int> a(234, 2);
       std::fill(policy, Iter(std::data(a)), Iter(std::data(a) + std::size(a)), 33);
       assert(std::all_of(std::begin(a), std::end(a), [](int i) { return i == 33; }));
     }
   }
 };
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-struct ThrowOnCopy {
-  ThrowOnCopy& operator=(const ThrowOnCopy&) { throw int{}; }
-};
-#endif
-
 int main(int, char**) {
   types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-  std::set_terminate(terminate_successful);
-  ThrowOnCopy a[2];
-  try {
-    (void)std::fill(std::execution::par, std::begin(a), std::end(a), ThrowOnCopy{});
-  } catch (int) {
-    assert(false);
-  }
-#endif
-
   return 0;
 }

libcxx/test/std/algorithms/alg.modifying.operations/alg.fill/pstl.fill_n.pass.cpp

void operator()(Policy&& policy) {
     { // check that a large range works
       std::vector<int> a(234, 2);
       std::fill_n(policy, Iter(std::data(a)), std::size(a), 33);
       assert(std::all_of(std::begin(a), std::end(a), [](int i) { return i == 33; }));
     }
   }
 };
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-struct ThrowOnCopy {
-  ThrowOnCopy& operator=(const ThrowOnCopy&) { throw int{}; }
-};
-#endif
-
 int main(int, char**) {
   types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-  std::set_terminate(terminate_successful);
-  ThrowOnCopy a[2];
-  try {
-    (void)std::fill_n(std::execution::par, std::begin(a), std::size(a), ThrowOnCopy{});
-  } catch (int) {
-    assert(false);
-  }
-#endif
-
   return 0;
 }

libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.exception_handling.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: no-exceptions
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// check that std::replace(ExecutionPolicy), std::replace_if(ExecutionPolicy), std::replace_copy(ExecutionPolicy)
+// and std::replace_copy_if(ExecutionPolicy) terminate on user-thrown exceptions
+
+#include <algorithm>
+
+#include "check_assertion.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+struct ThrowOnCompare {};
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; }
+#endif
+
+int main(int, char**) {
+  test_execution_policies([&](auto&& policy) {
+    // std::replace
+    EXPECT_STD_TERMINATE([&] {
+      ThrowOnCompare a[2]{};
+      (void)std::replace(policy, std::begin(a), std::end(a), ThrowOnCompare{}, ThrowOnCompare{});
+    });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        int a[] = {1, 2};
+        (void)std::replace(
+            policy, util::throw_on_move_iterator(std::begin(a), 1), util::throw_on_move_iterator(std::end(a), 1), 1, 2);
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+
+    // std::replace_if
+    EXPECT_STD_TERMINATE([&] {
+      ThrowOnCompare a[2]{};
+      (void)std::replace_if(
+          policy, std::begin(a), std::end(a), [](ThrowOnCompare&) -> bool { throw int{}; }, ThrowOnCompare{});
+    });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        int a[] = {1, 2};
+        (void)std::replace_if(
+            policy,
+            util::throw_on_move_iterator(std::begin(a), 1),
+            util::throw_on_move_iterator(std::end(a), 1),
+            [](int) { return true; },
+            2);
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+
+    // std::replace_copy
+    EXPECT_STD_TERMINATE([&] {
+      ThrowOnCompare a[2]{};
+      (void)std::replace_copy(policy, std::begin(a), std::end(a), std::begin(a), ThrowOnCompare{}, ThrowOnCompare{});
+    });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        int a[] = {1, 2};
+        (void)std::replace_copy(
+            policy,
+            util::throw_on_move_iterator(std::begin(a), 1),
+            util::throw_on_move_iterator(std::end(a), 1),
+            util::throw_on_move_iterator(std::begin(a), 1),
+            1,
+            2);
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+
+    // std::replace_copy_if
+    EXPECT_STD_TERMINATE([&] {
+      ThrowOnCompare a[2]{};
+      (void)std::replace_copy_if(
+          policy,
+          std::begin(a),
+          std::end(a),
+          std::begin(a),
+          [](ThrowOnCompare& i) { return i == i; },
+          ThrowOnCompare{});
+    });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        int a[] = {1, 2};
+        (void)std::replace_copy_if(
+            policy,
+            util::throw_on_move_iterator(std::begin(a), 1),
+            util::throw_on_move_iterator(std::end(a), 1),
+            util::throw_on_move_iterator(std::begin(a), 1),
+            [](int) { return true; },
+            2);
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+  });
+}

libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace.pass.cpp

void operator()(ExecutionPolicy&& policy) {
 
       std::vector<int> comp(150, 6);
       comp[45] = 5;
       assert(std::equal(a.begin(), a.end(), comp.begin()));
     }
   }
 };
 
-struct ThrowOnCompare {};
-
-#ifndef TEST_HAS_NO_EXCEPTIONS
-bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; }
-#endif
-
 int main(int, char**) {
   types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-  std::set_terminate(terminate_successful);
-  ThrowOnCompare a[2];
-  try {
-    (void)std::replace(std::execution::par, std::begin(a), std::end(a), ThrowOnCompare{}, ThrowOnCompare{});
-  } catch (int) {
-    assert(false);
-  }
-#endif
-
   return 0;
 }

libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_copy.pass.cpp

void operator()(ExecutionPolicy&& policy) {
 
       std::vector<int> comp(150, 6);
       comp[45] = 5;
       assert(std::equal(out.begin(), out.end(), comp.begin()));
     }
   }
 };
 
-struct ThrowOnCompare {};
-
-#ifndef TEST_HAS_NO_EXCEPTIONS
-bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; }
-#endif
-
 int main(int, char**) {
   types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-  std::set_terminate(terminate_successful);
-  ThrowOnCompare a[2];
-  try {
-    (void)std::replace_copy(
-        std::execution::par, std::begin(a), std::end(a), std::begin(a), ThrowOnCompare{}, ThrowOnCompare{});
-  } catch (int) {
-    assert(false);
-  }
-#endif
-
   return 0;
 }

libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_copy_if.pass.cpp

void operator()(ExecutionPolicy&& policy) {
 
       std::vector<int> comp(150, 6);
       comp[45] = 5;
       assert(std::equal(out.begin(), out.end(), comp.begin()));
     }
   }
 };
 
-struct ThrowOnCompare {};
-
-#ifndef TEST_HAS_NO_EXCEPTIONS
-bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; }
-#endif
-
 int main(int, char**) {
   types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-  std::set_terminate(terminate_successful);
-  ThrowOnCompare a[2];
-  try {
-    (void)std::replace_copy_if(
-        std::execution::par,
-        std::begin(a),
-        std::end(a),
-        std::begin(a),
-        [](ThrowOnCompare& i) { return i == i; },
-        ThrowOnCompare{});
-  } catch (int) {
-    assert(false);
-  }
-#endif
-
   return 0;
 }

libcxx/test/std/algorithms/alg.modifying.operations/alg.replace/pstl.replace_if.pass.cpp

void operator()(ExecutionPolicy&& policy) {
 
       std::vector<int> comp(150, 6);
       comp[45] = 5;
       assert(std::equal(a.begin(), a.end(), comp.begin()));
     }
   }
 };
 
-struct ThrowOnCompare {};
-
-#ifndef TEST_HAS_NO_EXCEPTIONS
-bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; }
-#endif
-
 int main(int, char**) {
   types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-  std::set_terminate(terminate_successful);
-  ThrowOnCompare a[2];
-  try {
-    (void)std::replace_if(
-        std::execution::par, std::begin(a), std::end(a), [](ThrowOnCompare&) { return false; }, ThrowOnCompare{});
-  } catch (int) {
-    assert(false);
-  }
-#endif
-
   return 0;
 }

libcxx/test/std/algorithms/alg.modifying.operations/alg.transform/pstl.exception_handling.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: no-exceptions
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// check that std::transform(ExecutionPolicy) terminates on user-thrown exceptions
+
+#include <algorithm>
+
+#include "check_assertion.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+int main(int, char**) {
+  test_execution_policies([&](auto&& policy) {
+    EXPECT_STD_TERMINATE([&] {
+      int a[2]{};
+      int b[2]{};
+      int c[2]{};
+      (void)std::transform(
+          policy, std::begin(a), std::end(a), std::begin(b), std::begin(c), [](auto v, auto) -> decltype(v) {
+            throw int{};
+          });
+    });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        int a[] = {1, 2};
+        (void)std::transform(
+            policy,
+            util::throw_on_move_iterator(std::begin(a), 1),
+            util::throw_on_move_iterator(std::end(a), 1),
+            util::throw_on_move_iterator(std::begin(a), 1),
+            [](int i) { return i; });
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+
+    EXPECT_STD_TERMINATE([&] {
+      int a[2]{};
+      int b[2]{};
+      (void)std::transform(policy, std::begin(a), std::end(a), std::begin(b), [](auto v) -> decltype(v) {
+        throw int{};
+      });
+    });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        int a[] = {1, 2};
+        (void)std::transform(
+            policy,
+            util::throw_on_move_iterator(std::begin(a), 1),
+            util::throw_on_move_iterator(std::end(a), 1),
+            util::throw_on_move_iterator(std::begin(a), 1),
+            util::throw_on_move_iterator(std::begin(a), 1),
+            std::plus{});
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+  });
+}

libcxx/test/std/algorithms/alg.nonmodifying/alg.all_of/pstl.all_of.pass.cpp

void operator()(Policy&& policy) {
     std::fill(vec.begin(), vec.end(), 3);
     assert(std::all_of(Iter(vec.data()), Iter(vec.data() + vec.size()), [](int i) { return i == 3; }));
   }
 };
 
 int main(int, char**) {
   types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-  std::set_terminate(terminate_successful);
-  int a[] = {1, 2};
-  try {
-    (void)std::all_of(std::execution::par, std::begin(a), std::end(a), [](int i) -> bool { throw i; });
-  } catch (int) {
-    assert(false);
-  }
-#endif
-
   return 0;
 }

libcxx/test/std/algorithms/alg.nonmodifying/alg.all_of/pstl.exception_handling.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: no-exceptions
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// check that std::all_of(ExecutionPolicy) terminates on user-thrown exceptions
+
+#include <algorithm>
+
+#include "check_assertion.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+int main(int, char**) {
+  test_execution_policies([](auto&& policy) {
+    EXPECT_STD_TERMINATE([&] {
+      int a[] = {1, 2};
+      (void)std::all_of(policy, std::begin(a), std::end(a), [](int i) -> bool { throw i; });
+    });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        int a[] = {1, 2};
+        (void)std::all_of(
+            policy,
+            util::throw_on_move_iterator(std::begin(a), 1),
+            util::throw_on_move_iterator(std::end(a), 1),
+            [](int) { return true; });
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+  });
+}

libcxx/test/std/algorithms/alg.nonmodifying/alg.any_of/pstl.any_of.pass.cpp

void operator()(Policy&& policy) {
     vec[96] = 3;
     assert(std::any_of(Iter(vec.data()), Iter(vec.data() + vec.size()), [](int i) { return i == 3; }));
   }
 };
 
 int main(int, char**) {
   types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-  std::set_terminate(terminate_successful);
-  int a[] = {1, 2};
-  try {
-    (void)std::any_of(std::execution::par, std::begin(a), std::end(a), [](int i) -> bool { throw i; });
-  } catch (int) {
-    assert(false);
-  }
-#endif
-
   return 0;
 }

libcxx/test/std/algorithms/alg.nonmodifying/alg.any_of/pstl.exception_handling.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: no-exceptions
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// check that std::any_of(ExecutionPolicy) terminates on user-thrown exceptions
+
+#include <algorithm>
+
+#include "check_assertion.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+int main(int, char**) {
+  test_execution_policies([](auto&& policy) {
+    EXPECT_STD_TERMINATE([&] {
+      int a[] = {1, 2};
+      (void)std::any_of(policy, std::begin(a), std::end(a), [](int i) -> bool { throw i; });
+    });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        int a[] = {1, 2};
+        (void)std::any_of(
+            policy,
+            util::throw_on_move_iterator(std::begin(a), 1),
+            util::throw_on_move_iterator(std::end(a), 1),
+            [](int) { return true; });
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+  });
+}

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/pstl.exception_handling.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: no-exceptions
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// check that std::find(ExecutionPolicy), std::find_if(ExecutionPolicy) and std::find_if_not(ExecutionPolicy) terminate
+// on user-thrown exceptions
+
+#include <algorithm>
+
+#include "check_assertion.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+struct ThrowOnCompare {};
+
+#ifndef TEST_HAS_NO_EXCEPTIONS
+bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; }
+#endif
+
+int main(int, char**) {
+  test_execution_policies([](auto&& policy) {
+    // std::find
+    EXPECT_STD_TERMINATE([&] {
+      ThrowOnCompare a[2] = {};
+      (void)std::find(policy, std::begin(a), std::end(a), ThrowOnCompare{});
+    });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        int a[] = {1, 2};
+        (void)std::find(
+            policy, util::throw_on_move_iterator(std::begin(a), 1), util::throw_on_move_iterator(std::end(a), 1), 0);
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+
+    // std::find_if
+    EXPECT_STD_TERMINATE([&] {
+      int a[] = {1, 2};
+      (void)std::find_if(policy, std::begin(a), std::end(a), [](int) -> bool { throw int{}; });
+    });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        int a[] = {1, 2};
+        (void)std::find_if(
+            policy,
+            util::throw_on_move_iterator(std::begin(a), 1),
+            util::throw_on_move_iterator(std::end(a), 1),
+            [](int) { return true; });
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+
+    // std::find_if_not
+    EXPECT_STD_TERMINATE([&] {
+      int a[] = {1, 2};
+      (void)std::find_if_not(policy, std::begin(a), std::end(a), [](int) -> bool { throw int{}; });
+    });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        int a[] = {1, 2};
+        (void)std::find_if_not(
+            policy,
+            util::throw_on_move_iterator(std::begin(a), 1),
+            util::throw_on_move_iterator(std::end(a), 1),
+            [](int) { return true; });
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+  });
+}

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/pstl.find.pass.cpp

void operator()(Policy&& policy) {
     // check that a large number of elements works
     std::vector<int> vec(200, 4);
     vec[176] = 5;
     assert(base(std::find(policy, Iter(std::data(vec)), Iter(std::data(vec) + std::size(vec)), 5)) ==
            std::data(vec) + 176);
   }
 };
 
-struct ThrowOnCompare {};
-
-#ifndef TEST_HAS_NO_EXCEPTIONS
-bool operator==(ThrowOnCompare, ThrowOnCompare) { throw int{}; }
-#endif
-
 int main(int, char**) {
   types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-  std::set_terminate(terminate_successful);
-  ThrowOnCompare a[2];
-  try {
-    (void)std::find(std::execution::par, std::begin(a), std::end(a), ThrowOnCompare{});
-  } catch (int) {
-    assert(false);
-  }
-#endif
-
   return 0;
 }

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/pstl.find_if.pass.cpp

assert(base(std::find_if(policy, Iter(std::data(vec)), Iter(std::data(vec) + std::size(vec)), [](int i) {
              return i == 5;
            })) == std::data(vec) + 176);
   }
 };
 
 int main(int, char**) {
   types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-  std::set_terminate(terminate_successful);
-  int a[] = {1, 2};
-  try {
-    (void)std::find_if(std::execution::par, std::begin(a), std::end(a), [](int) -> bool { throw int{}; });
-  } catch (int) {
-    assert(false);
-  }
-#endif
-
   return 0;
 }

libcxx/test/std/algorithms/alg.nonmodifying/alg.find/pstl.find_if_not.pass.cpp

assert(base(std::find_if_not(policy, Iter(std::data(vec)), Iter(std::data(vec) + std::size(vec)), [](int i) {
              return i != 5;
            })) == std::data(vec) + 176);
   }
 };
 
 int main(int, char**) {
   types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-  std::set_terminate(terminate_successful);
-  int a[] = {1, 2};
-  try {
-    (void)std::find_if_not(std::execution::par, std::begin(a), std::end(a), [](int) -> bool { throw int{}; });
-  } catch (int) {
-    assert(false);
-  }
-#endif
-
   return 0;
 }

libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/pstl.exception_handling.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: no-exceptions
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// check that std::for_each(ExecutionPolicy) and std::for_each_n(ExecutionPolicy) terminate on user-thrown exceptions
+
+#include <algorithm>
+
+#include "check_assertion.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+int main(int, char**) {
+  test_execution_policies([](auto&& policy) {
+    int a[] = {1, 2};
+    // std::for_each
+    EXPECT_STD_TERMINATE([&] { std::for_each(policy, std::begin(a), std::end(a), [](int) { throw int{}; }); });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        (void)std::for_each(
+            policy, util::throw_on_move_iterator(std::begin(a), 1), util::throw_on_move_iterator(std::end(a), 1), [] {
+            });
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+
+    // std::for_each_n
+    EXPECT_STD_TERMINATE([&] { std::for_each_n(policy, std::data(a), std::size(a), [](int) { throw int{}; }); });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        (void)std::for_each_n(
+            policy, util::throw_on_move_iterator(std::begin(a), 1), std::size(a), [] {
+            });
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+
+  });
+}

libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/pstl.for_each.pass.cpp

for (auto size : sizes) {
       assert(std::all_of(std::begin(called), std::end(called), [](bool b) { return b; }));
     }
   }
 };
 
 int main(int, char**) {
   types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-  std::set_terminate(terminate_successful);
-  int a[] = {1, 2};
-  try {
-    std::for_each(std::execution::par, std::begin(a), std::end(a), [](int) { throw int{}; });
-  } catch (int) {
-    assert(false);
-  }
-#endif
-
   return 0;
 }

libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/pstl.for_each_n.pass.cpp

for (auto size : sizes) {
       assert(std::all_of(std::begin(called), std::end(called), [](bool b) { return b; }));
     }
   }
 };
 
 int main(int, char**) {
   types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-  std::set_terminate(terminate_successful);
-  int a[] = {1, 2};
-  try {
-    std::for_each_n(std::execution::par, std::data(a), std::size(a), [](int) { throw int{}; });
-  } catch (int) {
-    assert(false);
-  }
-#endif
-
   return 0;
 }

libcxx/test/std/algorithms/alg.nonmodifying/alg.none_of/pstl.exception_handling.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: no-exceptions
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// check that std::none_of(ExecutionPolicy) terminates on user-thrown exceptions
+
+#include <algorithm>
+
+#include "check_assertion.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+int main(int, char**) {
+  test_execution_policies([](auto&& policy) {
+    EXPECT_STD_TERMINATE([&] {
+      int a[] = {1, 2};
+      (void)std::none_of(policy, std::begin(a), std::end(a), [](int i) -> bool { throw i; });
+    });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        int a[] = {1, 2};
+        (void)std::none_of(
+            policy,
+            util::throw_on_move_iterator(std::begin(a), 1),
+            util::throw_on_move_iterator(std::end(a), 1),
+            [](int) { return true; });
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+  });
+}

libcxx/test/std/algorithms/alg.nonmodifying/alg.none_of/pstl.none_of.pass.cpp

void operator()(Policy&& policy) {
     std::fill(vec.begin(), vec.end(), 3);
     assert(std::none_of(Iter(vec.data()), Iter(vec.data() + vec.size()), [](int i) { return i != 3; }));
   }
 };
 
 int main(int, char**) {
   types::for_each(types::forward_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-  std::set_terminate(terminate_successful);
-  int a[] = {1, 2};
-  try {
-    (void)std::none_of(std::execution::par, std::begin(a), std::end(a), [](int i) -> bool { throw i; });
-  } catch (int) {
-    assert(false);
-  }
-#endif
-
   return 0;
 }

libcxx/test/std/algorithms/alg.sorting/alg.merge/pstl.exception_handling.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: no-exceptions
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// check that std::merge(ExecutionPolicy) terminates on user-thrown exceptions
+
+#include <algorithm>
+
+#include "check_assertion.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+int main(int, char**) {
+  test_execution_policies([](auto&& policy) {
+    EXPECT_STD_TERMINATE([&] {
+      int a[] = {1, 2};
+      std::merge(policy, std::begin(a), std::end(a), std::begin(a), std::end(a), std::begin(a), [](int, int) -> bool {
+        throw int{};
+      });
+    });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        int a[] = {1, 2};
+        (void)std::merge(
+            policy,
+            util::throw_on_move_iterator(std::begin(a), 1),
+            util::throw_on_move_iterator(std::end(a), 1),
+            util::throw_on_move_iterator(std::begin(a), 1),
+            util::throw_on_move_iterator(std::end(a), 1),
+            util::throw_on_move_iterator(std::begin(a), 1),
+            std::less{});
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+  });
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/pstl.exception_handling.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: no-exceptions
+
+// UNSUPPORTED: libcpp-has-no-incomplete-pstl
+
+// check that std::stable_sort(ExecutionPolicy) terminates on user-thrown exceptions
+
+#include <algorithm>
+
+#include "check_assertion.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+int main(int, char**) {
+  test_execution_policies([](auto&& policy) {
+    EXPECT_STD_TERMINATE([&] {
+      int a[] = {1, 2};
+      std::stable_sort(policy, std::begin(a), std::end(a), [](int, int) -> bool { throw int{}; });
+    });
+    EXPECT_STD_TERMINATE([&] {
+      try {
+        int a[] = {1, 2};
+        (void)std::stable_sort(
+            policy, util::throw_on_move_iterator(std::begin(a), 1), util::throw_on_move_iterator(std::end(a), 1));
+      } catch (const util::iterator_error&) {
+        assert(false);
+      }
+      std::terminate(); // make the test pass in case the algorithm didn't move the iterator
+    });
+  });
+}

libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/pstl.stable_sort.pass.cpp

test_one<Iter, 6>({1, 2, 1, 2, 1, 2}, {1, 1, 1, 2, 2, 2});
       assert(in == expected);
     }
   }
 };
 
 int main(int, char**) {
   types::for_each(types::random_access_iterator_list<int*>{}, TestIteratorWithPolicies<Test>{});
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-  std::set_terminate(terminate_successful);
-  int a[] = {1, 2};
-  try {
-    std::stable_sort(std::execution::par, std::begin(a), std::end(a), [](int, int) -> bool { throw int{}; });
-  } catch (int) {
-    assert(false);
-  }
-#endif
-
   return 0;
 }

libcxx/test/support/check_assertion.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 TEST_SUPPORT_CHECK_ASSERTION_H
 #define TEST_SUPPORT_CHECK_ASSERTION_H
 
 #include <cassert>
 #include <cstdarg>
 #include <cstddef>
 #include <cstdio>
 #include <cstdlib>
+#include <exception>
 #include <string>
 #include <string_view>
 #include <utility>
 
 #include <unistd.h>
 #include <errno.h>
 #include <sys/wait.h>
 #include "test_macros.h"
 #include "test_allocator.h"
 
-#ifndef _LIBCPP_VERSION
-# error "This header may only be used for libc++ tests"
-#endif
-
 #if TEST_STD_VER < 11
 # error "C++11 or greater is required to use this header"
 #endif
 
 struct AssertionInfoMatcher {
   static const int any_line = -1;
   static constexpr const char* any_file = "*";
   static constexpr const char* any_msg = "*";

 
 inline AssertionInfoMatcher& GlobalMatcher() {
   static AssertionInfoMatcher GMatch;
   return GMatch;
 }
 
 struct DeathTest {
   enum ResultKind {
-    RK_DidNotDie, RK_MatchFound, RK_MatchFailure, RK_SetupFailure, RK_Unknown
+    RK_DidNotDie, RK_MatchFound, RK_MatchFailure, RK_Terminate, RK_SetupFailure, RK_Unknown
   };
 
   static const char* ResultKindToString(ResultKind RK) {
 #define CASE(K) case K: return #K
     switch (RK) {
     CASE(RK_MatchFailure);
     CASE(RK_DidNotDie);
     CASE(RK_SetupFailure);
     CASE(RK_MatchFound);
     CASE(RK_Unknown);
+    CASE(RK_Terminate);
     }
     return "not a result kind";
   }
 
   static bool IsValidResultKind(int val) {
     return val >= RK_DidNotDie && val <= RK_Unknown;
   }
 
private:
   pid_t child_pid_ = -1;
   int exit_code_ = -1;
   int stdout_pipe_fd_[2];
   int stderr_pipe_fd_[2];
   std::string stdout_from_child_;
   std::string stderr_from_child_;
 };
 
+#ifdef _LIBCPP_VERSION
 void std::__libcpp_verbose_abort(char const* format, ...) {
   // Extract information from the error message. This has to stay synchronized with
   // how we format assertions in the library.
   va_list list;
   va_start(list, format);
   char const* file = va_arg(list, char const*);
   int line = va_arg(list, int);
   char const* expression = va_arg(list, char const*); (void)expression;
   char const* message = va_arg(list, char const*);
   va_end(list);
 
   if (GlobalMatcher().Matches(file, line, message)) {
     std::exit(DeathTest::RK_MatchFound);
   }
   std::exit(DeathTest::RK_MatchFailure);
 }
+#endif // _LIBCPP_VERSION
+
+[[noreturn]] inline void terminate_handler() {
+  std::exit(DeathTest::RK_Terminate);
+}
 
 template <class Func>
 inline bool ExpectDeath(const char* stmt, Func&& func, AssertionInfoMatcher Matcher) {
+  std::set_terminate(terminate_handler);
   DeathTest DT(Matcher);
   DeathTest::ResultKind RK = DT.Run(func);
   auto OnFailure = [&](const char* msg) {
     std::fprintf(stderr, "EXPECT_DEATH( %s ) failed! (%s)\n\n", stmt, msg);
     if (RK != DeathTest::RK_Unknown) {
       std::fprintf(stderr, "child exit code: %d\n", DT.getChildExitCode());
     }
     if (!DT.getChildStdErr().empty()) {
       std::fprintf(stderr, "---------- standard err ----------\n%s\n", DT.getChildStdErr().c_str());
     }
     if (!DT.getChildStdOut().empty()) {
       std::fprintf(stderr, "---------- standard out ----------\n%s\n", DT.getChildStdOut().c_str());
     }
     return false;
   };
   switch (RK) {
   case DeathTest::RK_MatchFound:
+  case DeathTest::RK_Terminate:
     return true;
   case DeathTest::RK_SetupFailure:
     return OnFailure("child failed to setup test environment");
   case DeathTest::RK_Unknown:
       return OnFailure("reason unknown");
   case DeathTest::RK_DidNotDie:
       return OnFailure("child did not die");
   case DeathTest::RK_MatchFailure:
       return OnFailure("matcher failed");
   }
   assert(false && "unreachable");
 }
 
 template <class Func>
 inline bool ExpectDeath(const char* stmt, Func&& func) {
   return ExpectDeath(stmt, func, AnyMatcher);
 }
 
 /// Assert that the specified expression throws a libc++ debug exception.
 #define EXPECT_DEATH(...) assert((ExpectDeath(#__VA_ARGS__, [&]() { __VA_ARGS__; } )))
 
+#define EXPECT_STD_TERMINATE(...) assert(ExpectDeath(#__VA_ARGS__, __VA_ARGS__))
+
 #define EXPECT_DEATH_MATCHES(Matcher, ...) assert((ExpectDeath(#__VA_ARGS__, [&]() { __VA_ARGS__; }, Matcher)))
 
 #define TEST_LIBCPP_ASSERT_FAILURE(expr, message) assert((ExpectDeath(#expr, [&]() { (void)(expr); }, AssertionInfoMatcher(message))))
 
 #endif // TEST_SUPPORT_CHECK_ASSERTION_H

libcxx/test/support/test_execution_policies.h

struct Bool {
   Bool() = default;
   Bool(bool b) : b_(b) {}
 
   operator bool&() {
     return b_;
   }
 };
 
-#ifndef TEST_HAS_NO_EXCEPTIONS
-[[noreturn]] inline void terminate_successful() { std::exit(0); }
-#endif
-
 #endif // TEST_SUPPORT_TEST_EXECUTION_POLICIES

libcxx/test/support/test_iterators.h

 };
 
 template <std::ranges::input_range R>
   requires std::ranges::viewable_range<R&&>
 ProxyRange(R&&) -> ProxyRange<std::views::all_t<R&&>>;
 
 #endif // TEST_STD_VER > 17
 
+#if TEST_STD_VER >= 17
+
+namespace util {
+template <class Derived, class Iter>
+class iterator_wrapper {
+  Iter iter_;
+
+  using iter_traits = std::iterator_traits<Iter>;
+
+public:
+  using iterator_cateory = typename iter_traits::iterator_category;
+  using value_type       = typename iter_traits::value_type;
+  using difference_type  = typename iter_traits::difference_type;
+  using pointer          = typename iter_traits::pointer;
+  using reference        = typename iter_traits::reference;
+
+  constexpr iterator_wrapper() : iter_() {}
+  constexpr explicit iterator_wrapper(Iter iter) : iter_(iter) {}
+
+  decltype(*iter_) operator*() { return *iter_; }
+  decltype(*iter_) operator*() const { return *iter_; }
+
+  Derived& operator++() {
+    ++iter_;
+    return static_cast<Derived&>(*this);
+  }
+
+  Derived operator++(int) {
+    auto tmp = static_cast<Derived&>(*this);
+    ++(*this);
+    return tmp;
+  }
+
+  Derived& operator--() {
+    --iter_;
+    return static_cast<Derived&>(*this);
+  }
+
+  Derived operator--(int) {
+    auto tmp = static_cast<Derived&>(*this);
+    --(*this);
+    return tmp;
+  }
+
+  iterator_wrapper& operator+=(difference_type i) {
+    iter_ += i;
+    return *this;
+  }
+
+  friend decltype(iter_ - iter_) operator-(const iterator_wrapper& lhs, const iterator_wrapper& rhs) {
+    return lhs.iter_ - rhs.iter_;
+  }
+
+  friend Derived operator+(Derived iter, difference_type i) {
+    iter.iter_ += i;
+    return iter;
+  }
+
+  friend bool operator==(const iterator_wrapper& lhs, const iterator_wrapper& rhs) { return lhs.iter_ == rhs.iter_; }
+};
+
+class iterator_error : std::runtime_error {
+public:
+  iterator_error(const char* what) : std::runtime_error(what) {}
+};
+
+template <class Iter>
+class throw_on_move_iterator : public iterator_wrapper<throw_on_move_iterator<Iter>, Iter> {
+  using base = iterator_wrapper<throw_on_move_iterator<Iter>, Iter>;
+
+  int moves_until_throw_ = 0;
+
+public:
+  using difference_type   = base::difference_type;
+  using value_type        = base::value_type;
+  using iterator_category = base::iterator_cateory;
+
+  throw_on_move_iterator() = default;
+  throw_on_move_iterator(Iter iter, int moves_until_throw)
+      : base(std::move(iter)), moves_until_throw_(moves_until_throw) {}
+
+  throw_on_move_iterator(const throw_on_move_iterator& other) : base(other) {}
+  throw_on_move_iterator& operator=(const throw_on_move_iterator& other) {
+    static_cast<base&>(*this) = other;
+    return *this;
+  }
+
+  throw_on_move_iterator(throw_on_move_iterator&& other)
+      : base(std::move(other)), moves_until_throw_(other.moves_until_throw_ - 1) {
+    if (moves_until_throw_ == -1)
+      throw iterator_error("throw_on_move_iterator");
+  }
+
+  throw_on_move_iterator& operator=(throw_on_move_iterator&& other) {
+    moves_until_throw_ = other.moves_until_throw_ - 1;
+    if (moves_until_throw_ == -1)
+      throw iterator_error("throw_on_move_iterator");
+    return *this;
+  }
+};
+
+template <class Iter>
+throw_on_move_iterator(Iter) -> throw_on_move_iterator<Iter>;
+} // namespace util
+
+#endif // TEST_STD_VER >= 17
+
 namespace types {
 template <class Ptr>
 using random_access_iterator_list =
     type_list<Ptr,
 #if TEST_STD_VER >= 20
               contiguous_iterator<Ptr>,
 #endif
               random_access_iterator<Ptr> >;