1 files changed, 95 insertions, 61 deletions

diff --git a/contrib/llvm-project/libcxx/include/__algorithm/pstl_backend.h b/contrib/llvm-project/libcxx/include/__algorithm/pstl_backend.h
index 93372f019031..3af03ce2fbc8 100644
--- a/contrib/llvm-project/libcxx/include/__algorithm/pstl_backend.h
+++ b/contrib/llvm-project/libcxx/include/__algorithm/pstl_backend.h
@@ -27,23 +27,38 @@ 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 _ForwardIterator1,
+            class _ForwardIterator2,
+            class _ForwardOutIterator,
+            class _Comp>
+  optional<_ForwardOutIterator> __pstl_merge(_Backend,
+                                             _ForwardIterator1 __first1,
+                                             _ForwardIterator1 __last1,
+                                             _ForwardIterator2 __first2,
+                                             _ForwardIterator2 __last2,
+                                             _ForwardOutIterator __result,
+                                             _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(_Backend, _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,
-                                _InIterator2 __first2,
-                                _OutIterator __result,
-                                _BinaryOperation __op);
+  optional<_OutIterator> __pstl_transform(_InIterator1 __first1,
+                                          _InIterator2 __first2,
+                                          _InIterator1 __last1,
+                                          _OutIterator __result,
+                                          _BinaryOperation __op);
 
   template <class _ExecutionPolicy,
             class _Iterator1,
@@ -51,22 +66,22 @@ A PSTL parallel backend is a tag type to which the following functions are assoc
             class _Tp,
             class _BinaryOperation1,
             class _BinaryOperation2>
-  _Tp __pstl_transform_reduce(_Backend,
-                              _Iterator1 __first1,
-                              _Iterator1 __last1,
-                              _Iterator2 __first2,
-                              _Iterator2 __last2,
-                              _Tp __init,
-                              _BinaryOperation1 __reduce,
-                              _BinaryOperation2 __transform);
+  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,
-                              _Iterator __first,
-                              _Iterator __last,
-                              _Tp __init,
-                              _BinaryOperation __reduce,
-                              _UnaryOperation __transform);
+  optional<_Tp> __pstl_transform_reduce(_Backend,
+                                        _Iterator __first,
+                                        _Iterator __last,
+                                        _Tp __init,
+                                        _BinaryOperation __reduce,
+                                        _UnaryOperation __transform);
 
 // TODO: Complete this list
 
@@ -75,86 +90,105 @@ algorithms, otherwise they are implemented in terms of other algorithms. If none
 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,
-                            _Iterator1 __first1,
-                            _Iterator1 __last1,
-                            _Iterator2 __first2,
-                            _Iterator2 __last2,
-                            _OutIterator __result,
-                            _Comp __comp);
+  optional<_OutIterator> __pstl_merge(_Backend,
+                                      _Iterator1 __first1,
+                                      _Iterator1 __last1,
+                                      _Iterator2 __first2,
+                                      _Iterator2 __last2,
+                                      _OutIterator __result,
+                                      _Comp __comp);
+
+  template <class _ExecutionPolicy, class _Iterator, class _OutIterator>
+  optional<_OutIterator> __pstl_move(_Backend, _Iterator __first, _Iterator __last, _OutIterator __result);
 
   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);
+  template <class _ExecutionPolicy, class _Iterator, class _Tp>
+  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,
-                           _Iterator __first,
-                           _Iterator __last,
-                           _OutIterator __result,
-                           const _Tp& __old_value,
-                           const _Tp& __new_value);
+  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,
-                              _Iterator __first,
-                              _Iterator __last,
-                              _OutIterator __result,
-                              _Pred __pred,
-                              const _Tp& __new_value);
+  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 _OutIterator>
+  optional<_Iterator> __pstl_rotate_copy(
+      _Backend, _Iterator __first, _Iterator __middle, _Iterator __last, _OutIterator __result);
 
   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);
+
+  template <class _ExecutionPolicy, class _Iterator1, class _Iterator2, class _Comp>
+  optional<bool> __pstl_equal(_Backend, _Iterator1 first1, _Iterator1 last1, _Iterator2 first2, _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>