[libc++][PSTL] Reduce the amount of transitive includes

[philnik]

Generate files

[philnik]

Try to fix CI

[philnik]

Add removed transitive includes

[ldionne]

LGTM w/ comments

libcxx/include/__algorithm/pstl_any_all_none_of.h

62–64

I would just use a lambda instead, since this is used only in two places. Otherwise, honestly I'd imagine someone finding __negate_function and "refactoring" it to std::not_fn.

libcxx/include/__pstl/internal/parallel_impl.h

36

I think I would still use std::atomic here, but I'd include <__atomic/atomic.h> instead. __atomic_base is arguably an implementation detail of std::atomic, and I don't think we should start using it widely in the rest of our code base. And in fact there's a few places that use std::__atomic_base right now in the synchronization library, and those could be refactored to use std::atomic (although those are IMO less vexing since the synchronization library is so close to <atomic>).

[philnik]

Address comments

[philnik]

Generate files

[philnik]

Fix stuff

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/any_of.h>
+#include <__algorithm/negate_function.h>
 #include <__config>
-#include <__functional/not_fn.h>
+#include <__iterator/iterator_traits.h>
 #include <__pstl/internal/parallel_impl.h>
 #include <__pstl/internal/unseq_backend_simd.h>
 #include <__type_traits/enable_if.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__utility/terminate_on_exception.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header

 }
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Pred,
           enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool
 all_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) {
-  return !std::any_of(__policy, __first, __last, std::not_fn(__pred));
+  return !std::any_of(__policy, __first, __last, [&](__iter_reference<_ForwardIterator> __value) {
+    return __pred(__value);
+  });
 }
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Pred,
           enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
 _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI bool
 none_of(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Pred __pred) {
   return !std::any_of(__policy, __first, __last, __pred);
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER >= 17
 
 #endif // _LIBCPP___ALGORITHM_PSTL_ANY_ALL_NONE_OF_H

libcxx/include/__algorithm/pstl_find.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_FIND_H
 #define _LIBCPP___ALGORITHM_PSTL_FIND_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/find.h>
+#include <__algorithm/negate_function.h>
 #include <__config>
-#include <__functional/not_fn.h>
 #include <__pstl/internal/parallel_impl.h>
 #include <__pstl/internal/unseq_backend_simd.h>
 #include <__type_traits/is_execution_policy.h>
 #include <__utility/terminate_on_exception.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif

 }
 
 template <class _ExecutionPolicy,
           class _ForwardIterator,
           class _Predicate,
           enable_if_t<is_execution_policy_v<__remove_cvref_t<_ExecutionPolicy>>, int> = 0>
 _LIBCPP_HIDE_FROM_ABI _ForwardIterator
 find_if_not(_ExecutionPolicy&& __policy, _ForwardIterator __first, _ForwardIterator __last, _Predicate __pred) {
-  return std::find_if(__policy, __first, __last, std::not_fn(std::move(__pred)));
+  return std::find_if(__policy, __first, __last, [&](__iter_reference<_ForwardIterator> __value) {
+    return __pred(__value);
+  });
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_PSTL_FIND_H

libcxx/include/__iterator/iterator_traits.h

 using __iterator_pointer_type = typename iterator_traits<_Iter>::pointer;
 
 template <class _Iter>
 using __iter_diff_t = typename iterator_traits<_Iter>::difference_type;
 
 template<class _InputIterator>
 using __iter_value_type = typename iterator_traits<_InputIterator>::value_type;
 
+template <class _Iter>
+using __iter_reference = typename iterator_traits<_Iter>::reference;
+
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H

libcxx/include/__memory/allocator.h

 #include <__memory/allocator_traits.h>
 #include <__type_traits/is_constant_evaluated.h>
 #include <__type_traits/is_same.h>
 #include <__type_traits/is_void.h>
 #include <__type_traits/is_volatile.h>
 #include <__utility/forward.h>
 #include <cstddef>
 #include <new>
-#include <stdexcept>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 template <class _Tp> class allocator;

libcxx/include/__pstl/internal/execution_defs.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 _PSTL_EXECUTION_POLICY_DEFS_H
 #define _PSTL_EXECUTION_POLICY_DEFS_H
 
-#include <type_traits>
+#include <__type_traits/decay.h>
+#include <__type_traits/enable_if.h>
+#include <__type_traits/integral_constant.h>
 
 #include "pstl_config.h"
 
 namespace __pstl {
 namespace execution {
 inline namespace v1 {
 
 // 2.4, Sequential execution policy

libcxx/include/__pstl/internal/execution_impl.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 _PSTL_EXECUTION_IMPL_H
 #define _PSTL_EXECUTION_IMPL_H
 
-#include <iterator>
-#include <type_traits>
+#include <__iterator/iterator_traits.h>
 
 #include "execution_defs.h"
 #include "pstl_config.h"
 
 namespace __pstl {
 namespace __internal {
 
 template <typename _IteratorTag, typename... _IteratorTypes>

libcxx/include/__pstl/internal/parallel_backend_utils.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 _PSTL_PARALLEL_BACKEND_UTILS_H
 #define _PSTL_PARALLEL_BACKEND_UTILS_H
 
-#include <iterator>
-#include <utility>
+#include <__iterator/iterator_traits.h>
+#include <__memory/addressof.h>
+
 #include "utils.h"
 
 #include "pstl_config.h"
 
 namespace __pstl
 {
 
 namespace __utils

libcxx/include/__pstl/internal/parallel_impl.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 _PSTL_PARALLEL_IMPL_H
 #define _PSTL_PARALLEL_IMPL_H
 
 #include "pstl_config.h"
 
+#include <__atomic/atomic.h>
 #include <__pstl/internal/parallel_backend.h>
-#include <atomic>
-// This header defines the minimum set of parallel routines required to support Parallel STL,
-// implemented on top of Intel(R) Threading Building Blocks (Intel(R) TBB) library
 
 namespace __pstl
 {
 namespace __internal
 {
 
 //------------------------------------------------------------------------
 // parallel_find
 //-----------------------------------------------------------------------
 /** Return extremum value returned by brick f[i,j) for subranges [i,j) of [first,last)
 Each f[i,j) must return a value in [i,j). */
 template <class _BackendTag, class _ExecutionPolicy, class _Index, class _Brick, class _Compare>
 _LIBCPP_HIDE_FROM_ABI _Index
 __parallel_find(_BackendTag __tag, _ExecutionPolicy&& __exec, _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
     __par_backend::__parallel_for(__tag, std::forward<_ExecutionPolicy>(__exec), __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))
                                       {

libcxx/include/__pstl/internal/unseq_backend_simd.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 _PSTL_UNSEQ_BACKEND_SIMD_H
 #define _PSTL_UNSEQ_BACKEND_SIMD_H
 
 #include <__functional/operations.h>
-#include <type_traits>
+#include <__utility/pair.h>
 
 #include "pstl_config.h"
 #include "utils.h"
 
 // This header defines the minimum set of vector routines required
 // to support parallel STL.
 
 namespace __pstl

libcxx/include/__pstl/internal/utils.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 _PSTL_UTILS_H
 #define _PSTL_UTILS_H
 
 #include <__exception/terminate.h>
-#include <iterator>
+#include <__pstl/internal/pstl_config.h>
+#include <__utility/forward.h>
 #include <new>
-#include <utility>
 
 namespace __pstl {
 namespace __internal {
 
 template <typename _Fp>
 _LIBCPP_HIDE_FROM_ABI auto __except_handler(_Fp __f) -> decltype(__f()) {
 #ifndef _LIBCPP_HAS_NO_EXCEPTIONS
   try {

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>
+#include <__exception/terminate.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 #if _LIBCPP_STD_VER >= 17
 
 _LIBCPP_BEGIN_NAMESPACE_STD

libcxx/include/any

 
 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
 #  include <atomic>
 #  include <concepts>
 #  include <cstdlib>
 #  include <iosfwd>
 #  include <iterator>
 #  include <memory>
+#  include <stdexcept>
 #  include <type_traits>
 #  include <variant>
 #endif
 
 #endif // _LIBCPP_ANY

libcxx/include/valarray

 _LIBCPP_POP_MACROS
 
 #if !defined(_LIBCPP_REMOVE_TRANSITIVE_INCLUDES) && _LIBCPP_STD_VER <= 20
 #  include <algorithm>
 #  include <concepts>
 #  include <cstdlib>
 #  include <cstring>
 #  include <functional>
+#  include <stdexcept>
 #  include <type_traits>
 #endif
 
 #endif // _LIBCPP_VALARRAY

libcxx/test/libcxx/transitive_includes/cxx2b.csv

 algorithm climits
 algorithm cstddef
 algorithm cstdint
 algorithm cstring
 algorithm initializer_list
 algorithm iosfwd
 algorithm limits
 algorithm new
 algorithm version
 any cstddef
 any cstdint
 any cstring
 any initializer_list
 any limits
 any new
-any stdexcept
 any typeinfo
 any version
 array compare
 array cstddef
 array initializer_list
 array limits
 array stdexcept
 array version

 utility limits
 utility version
 valarray cmath
 valarray cstddef
 valarray cstdint
 valarray initializer_list
 valarray limits
 valarray new
-valarray stdexcept
 valarray version
 variant compare
 variant cstddef
 variant cstdint
 variant cstring
 variant initializer_list
 variant limits
 variant new

libcxx/test/support/test_execution_policies.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_TEST_EXECUTION_POLICIES
 #define TEST_SUPPORT_TEST_EXECUTION_POLICIES
 
 #include <cstdlib>
+#include <exception>
 #include <execution>
 #include <type_traits>
 #include <utility>
 
 #include "test_macros.h"
 
 #define EXECUTION_POLICY_SFINAE_TEST(function)                                                                         \
   template <class, class...>                                                                                           \