[libc++][PSTL] Implement std::copy{,_n}

[ldionne]

libcxx/include/__algorithm/pstl_copy.h

29

I think it's fine to do in a separate patch. However, I think we need to do this before we can figure out the backend story because that's definitely an additional complexity we'll want to take into account in our dispatching mechanism.

35

Let's do this consistently.

[philnik]

• Address comments
• Improve tests

[ldionne]

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

99

I see this is repeating a lot, and because of C++17 we can't use template lambas. But we can do this:

types::for_each(types::forward_iterator_list<int*>{}, types::apply_type_identity([](auto It) {
  using Iter = typename decltype(It)::type;
  // the rest of your stuff
}));

// where
template <class F>
struct apply_type_identity {
  F f;
  template <class ...Args>
  auto operator()() const {
    return f(std::type_identity<Args>{}...);
  }
};

We can bikeshed about the name of apply_type_identity, I'm open to anything reasonable. IMO if we apply this throughout, it will localize the "loops" and make the testing code easier to read (and write!). WDYT?

[ldionne]

Please watch CI!

[philnik]

• Rebased
• Address comments

[philnik]

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

99

I'm not a huge fan of the name, but I can't come up with anything better.

[jloser]

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

99

I think the name is fine FWIW. Do we have a generic type for applying a generic metafunction (e.g. so a call site could look like apply<F, std::type_identity>)? The metafunction would be bound with the Args parameter pack on the call operator like it is now. Then, if you had such generic construct, you wouldn't need to name the entity apply_type_identity, it would be obvious from the callers.

[philnik]

Rebased

[philnik]

• Rebased
• Try to fix CI

[philnik]

Use new dispatching scheme

[philnik]

Rebased

[philnik]

Rebased

[philnik]

Rebased

[ldionne]

LGTM w/ comments and CI.

libcxx/include/__algorithm/pstl_backend.h

25–26

Let's add something like:

PSTL algorithms are a thin API layer that forward to a backend that implements the actual operation. The backend is selected based on the execution policy provided by the user.

All algorithms go through the dispatching mechanism, so a backend can customize any algorithm in the PSTL in a way that suits it. However, the only exception to this is when an algorithm can be implemented by a C function, we assume that the C function is the most efficient way to implement it on the platform and we use that unconditionally. For example, `std::copy(policy, ...)` will forward to `memmove` if the iterators and the copied type allow for it, regardless of whether the backend associated to `policy` implements `__pstl_copy`.

The following functions must be provided by all backends:

libcxx/include/__algorithm/pstl_copy.h

42–49

Here I would do something like

if constexpr (can-be-optimized-to-memmove(_ForwardIterator, ...)) {
  // ditch the execution policy and call the single-threaded std::copy, since we know it handles the complexity of optimizing properly
  return std::copy(__first, __last, __result);
} else {
  return std::__pstl_frontend_dispatch(...);
}

In a separate patch.

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

12

This isn't used anymore, and it means the test never ran!

99

The downside of apply<F, std::type_identity> is that F here is decltype(lamda), and that doesn't work with Clang :/

So we'd have to introduce the lambda and then do decltype(x), which is not as compositional.

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

12

x2

93

Same comment about lambdas.

[philnik]

• Address comments
• Try to fix CI

[philnik]

Rebased

[philnik]

Rebased

[philnik]

Rebased

[philnik]

Rebased

[philnik]

Fix diff

[philnik]

Fix diff

libcxx/include/CMakeLists.txt

set(files
   __algorithm/pstl_backends/cpu_backend.h
   __algorithm/pstl_backends/cpu_backends/any_of.h
   __algorithm/pstl_backends/cpu_backends/backend.h
   __algorithm/pstl_backends/cpu_backends/find_if.h
   __algorithm/pstl_backends/cpu_backends/fill.h
   __algorithm/pstl_backends/cpu_backends/for_each.h
   __algorithm/pstl_backends/cpu_backends/serial.h
   __algorithm/pstl_backends/cpu_backends/transform.h
+  __algorithm/pstl_copy.h
   __algorithm/pstl_fill.h
   __algorithm/pstl_find.h
   __algorithm/pstl_for_each.h
   __algorithm/pstl_frontend_dispatch.h
   __algorithm/pstl_transform.h
   __algorithm/push_heap.h
   __algorithm/ranges_adjacent_find.h
   __algorithm/ranges_all_of.h

libcxx/include/__algorithm/pstl_backend.h

 #  pragma GCC system_header
 #endif
 
 #if !defined(_LIBCPP_HAS_NO_INCOMPLETE_PSTL) && _LIBCPP_STD_VER >= 17
 
 _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);
 
   template <class _ExecutionPolicy, class _Iterator, class _Predicate>
   _Iterator __pstl_find_if(_Backend, _Iterator __first, _Iterator __last, _Predicate __pred);
 
implemented, all the algorithms will eventually forward to the basis algorithms listed above:
   void __pstl_for_each_n(_Backend, _ExecutionPolicy&&, _Iterator __first, _Size __n, _Func __f);
 
   template <class _ExecutionPolicy, class _Iterator, class _Predicate>
   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);
 
+  template <class _ExecutionPolicy, class _InIterator, class _OutIterator>
+  _OutIterator __pstl_copy(_Backend, _InIterator __first, _InIterator __last, _OutIterator __result);
+
+  template <class _ExecutionPolicy, class _InIterator, class _OutIterator, class _Size>
+  _OutIterator __pstl_copy_n(_Backend, _InIterator __first, _Size __n, _OutIterator __result);
+
   template <class _ExecutionPolicy, class _Iterator, class _Predicate>
   bool __pstl_none_of(_Backend, _Iterator __first, _iterator __last, _Predicate __pred);
 
   template <class _ExecutionPolicy, class _Iterator, class _Tp>
   void __pstl_fill(_Iterator __first, _Iterator __last, const _Tp& __value);
 
   template <class _ExecutionPolicy, class _Iterator, class _SizeT, class _Tp>
   void __pstl_fill_n(_Iterator __first, _SizeT __n, const _Tp& __value);

libcxx/include/__algorithm/pstl_copy.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_FILL_H
+#define _LIBCPP___ALGORITHM_PSTL_FILL_H
+
+#include <__algorithm/copy_n.h>
+#include <__algorithm/pstl_frontend_dispatch.h>
+#include <__algorithm/pstl_transform.h>
+#include <__config>
+#include <__iterator/iterator_traits.h>
+#include <__type_traits/is_constant_evaluated.h>
+#include <__type_traits/is_execution_policy.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if !defined(_LIBCPP_HAS_NO_INCOMLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+// TODO: Use the std::copy/move shenanigans to forward to std::memmove
+// (do we want to decide this on behalf of the backend?)
+
+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) {
+  return std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_copy),
+      [&](_ForwardIterator __first, _ForwardIterator __last, _ForwardOutIterator __result) {
+        return std::transform(__policy, __first, __last, __result, __identity());
+      },
+      std::move(__first),
+      std::move(__last),
+      std::move(__result));
+}
+
+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) {
+  return std::__pstl_frontend_dispatch(
+      _LIBCPP_PSTL_CUSTOMIZATION_POINT(__pstl_copy_n),
+      [&](_ForwardIterator __first, _Size __n, _ForwardOutIterator __result) {
+        if constexpr (__is_cpp17_random_access_iterator<_ForwardIterator>::value)
+          return std::copy(__policy, __first, __first + __n, __result);
+        else
+          return std::copy_n(__first, __n, __result);
+      },
+      __first,
+      __first + __n,
+      std::move(__result));
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_INCOMLETE_PSTL) && _LIBCPP_STD_VER >= 17
+
+#endif // _LIBCPP___ALGORITHM_PSTL_FILL_H

libcxx/include/__pstl/internal/glue_algorithm_defs.h

search_n(_ExecutionPolicy&& __exec,
          _BinaryPredicate __pred);
 
 template <class _ExecutionPolicy, class _ForwardIterator, class _Size, class _Tp>
 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator> search_n(
     _ExecutionPolicy&& __exec, _ForwardIterator __first, _ForwardIterator __last, _Size __count, const _Tp& __value);
 
 // [alg.copy]
 
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
-copy(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result);
-
-template <class _ExecutionPolicy, class _ForwardIterator1, class _Size, class _ForwardIterator2>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
-copy_n(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _Size __n, _ForwardIterator2 __result);
-
 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
 copy_if(_ExecutionPolicy&& __exec,
         _ForwardIterator1 __first,
         _ForwardIterator1 __last,
         _ForwardIterator2 result,
         _Predicate __pred);
 

libcxx/include/__pstl/internal/glue_algorithm_impl.h

return std::search_n(
       __last,
       __count,
       __value,
       std::equal_to<typename iterator_traits<_ForwardIterator>::value_type>());
 }
 
 // [alg.copy]
 
-template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
-copy(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _ForwardIterator1 __last, _ForwardIterator2 __result) {
-  auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result);
-
-  using __is_vector = typename decltype(__dispatch_tag)::__is_vector;
-
-  return __pstl::__internal::__pattern_walk2_brick(
-      __dispatch_tag,
-      std::forward<_ExecutionPolicy>(__exec),
-      __first,
-      __last,
-      __result,
-      [](_ForwardIterator1 __begin, _ForwardIterator1 __end, _ForwardIterator2 __res) {
-        return __pstl::__internal::__brick_copy(__begin, __end, __res, __is_vector{});
-      });
-}
-
-template <class _ExecutionPolicy, class _ForwardIterator1, class _Size, class _ForwardIterator2>
-__pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
-copy_n(_ExecutionPolicy&& __exec, _ForwardIterator1 __first, _Size __n, _ForwardIterator2 __result) {
-  auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result);
-
-  using __is_vector = typename decltype(__dispatch_tag)::__is_vector;
-
-  return __pstl::__internal::__pattern_walk2_brick_n(
-      __dispatch_tag,
-      std::forward<_ExecutionPolicy>(__exec),
-      __first,
-      __n,
-      __result,
-      [](_ForwardIterator1 __begin, _Size __sz, _ForwardIterator2 __res) {
-        return __pstl::__internal::__brick_copy_n(__begin, __sz, __res, __is_vector{});
-      });
-}
-
 template <class _ExecutionPolicy, class _ForwardIterator1, class _ForwardIterator2, class _Predicate>
 __pstl::__internal::__enable_if_execution_policy<_ExecutionPolicy, _ForwardIterator2>
 copy_if(_ExecutionPolicy&& __exec,
         _ForwardIterator1 __first,
         _ForwardIterator1 __last,
         _ForwardIterator2 __result,
         _Predicate __pred) {
   auto __dispatch_tag = __pstl::__internal::__select_backend(__exec, __first, __result);

libcxx/include/algorithm

 #include <__algorithm/partial_sort.h>
 #include <__algorithm/partial_sort_copy.h>
 #include <__algorithm/partition.h>
 #include <__algorithm/partition_copy.h>
 #include <__algorithm/partition_point.h>
 #include <__algorithm/pop_heap.h>
 #include <__algorithm/prev_permutation.h>
 #include <__algorithm/pstl_any_all_none_of.h>
+#include <__algorithm/pstl_copy.h>
 #include <__algorithm/pstl_fill.h>
 #include <__algorithm/pstl_find.h>
 #include <__algorithm/pstl_for_each.h>
 #include <__algorithm/pstl_transform.h>
 #include <__algorithm/push_heap.h>
 #include <__algorithm/ranges_adjacent_find.h>
 #include <__algorithm/ranges_all_of.h>
 #include <__algorithm/ranges_any_of.h>

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/pstl.copy.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
+
+// REQUIRES: with-pstl
+
+// <algorithm>
+
+// template<class ExecutionPolicy, class ForwardIterator1, class ForwardIterator2>
+//   ForwardIterator2 copy(ExecutionPolicy&& policy,
+//                         ForwardIterator1 first, ForwardIterator1 last,
+//                         ForwardIterator2 result);
+
+#include <algorithm>
+#include <vector>
+
+#include "test_macros.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+EXECUTION_POLICY_SFINAE_TEST(copy);
+
+static_assert(sfinae_test_copy<int, int*, int*, bool (*)(int)>);
+static_assert(!sfinae_test_copy<std::execution::parallel_policy, int*, int*, int>);
+
+template <class Iter1, class Iter2>
+struct TestInt {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    // simple test
+    for (const int size : {0, 1, 2, 100, 350}) {
+      std::vector<int> a(size);
+      for (int i = 0; i != size; ++i)
+        a[i] = i + 1;
+
+      std::vector<int> out(std::size(a));
+      decltype(auto) ret =
+          std::copy(policy, Iter1(std::data(a)), Iter1(std::data(a) + std::size(a)), Iter2(std::data(out)));
+      static_assert(std::is_same_v<decltype(ret), Iter2>);
+      assert(base(ret) == std::data(out) + std::size(out));
+      for (int i = 0; i != size; ++i)
+        assert(out[i] == i + 1);
+    }
+  }
+};
+
+struct CopiedToTester {
+  bool copied_to   = false;
+  CopiedToTester() = default;
+  CopiedToTester(const CopiedToTester&) {}
+  CopiedToTester& operator=(const CopiedToTester&) {
+    assert(!copied_to);
+    copied_to = true;
+    return *this;
+  }
+  ~CopiedToTester() = default;
+};
+
+template <class Iter1, class Iter2>
+struct TestNonTrivial {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    // simple test
+    for (const int size : {0, 1, 2, 100, 350}) {
+      std::vector<CopiedToTester> a(size);
+
+      std::vector<CopiedToTester> out(std::size(a));
+      auto ret = std::copy(policy, Iter1(std::data(a)), Iter1(std::data(a) + std::size(a)), Iter2(std::data(out)));
+      assert(base(ret) == std::data(out) + std::size(out));
+      assert(std::all_of(std::begin(out), std::end(out), [](CopiedToTester& t) { return t.copied_to; }));
+      assert(std::none_of(std::begin(a), std::end(a), [](CopiedToTester& t) { return t.copied_to; }));
+    }
+  }
+};
+
+struct TestIteratorsNonTrivial {
+  template <class Iter2>
+  void operator()() {}
+};
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, types::apply_type_identity{[](auto v) {
+                    using Iter = typename decltype(v)::type;
+                    types::for_each(
+                        types::forward_iterator_list<int*>{},
+                        TestIteratorWithPolicies< types::partial_instantiation<TestInt, Iter>::template apply>{});
+                  }});
+
+  types::for_each(
+      types::forward_iterator_list<CopiedToTester*>{}, types::apply_type_identity{[](auto v) {
+        using Iter = typename decltype(v)::type;
+        types::for_each(
+            types::forward_iterator_list<CopiedToTester*>{},
+            TestIteratorWithPolicies< types::partial_instantiation<TestNonTrivial, Iter>::template apply>{});
+      }});
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.modifying.operations/alg.copy/pstl.copy_n.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
+
+// REQUIRES: with-pstl
+
+// <algorithm>
+
+// template<class ExecutionPolicy, class ForwardIterator1, class Size, class ForwardIterator2>
+//   ForwardIterator2 copy_n(ExecutionPolicy&& exec,
+//                           ForwardIterator1 first, Size n,
+//                           ForwardIterator2 result);
+
+#include <algorithm>
+#include <vector>
+
+#include "test_macros.h"
+#include "test_execution_policies.h"
+#include "test_iterators.h"
+
+EXECUTION_POLICY_SFINAE_TEST(copy_n);
+
+static_assert(sfinae_test_copy_n<int, int*, int*, bool (*)(int)>);
+static_assert(!sfinae_test_copy_n<std::execution::parallel_policy, int*, int*, int>);
+
+template <class Iter1, class Iter2>
+struct TestInt {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    // simple test
+    for (const int size : {0, 1, 2, 100, 350}) {
+      std::vector<int> a(size);
+      for (int i = 0; i != size; ++i)
+        a[i] = i + 1;
+
+      std::vector<int> out(std::size(a));
+      decltype(auto) ret = std::copy_n(policy, Iter1(std::data(a)), std::size(a), Iter2(std::data(out)));
+      static_assert(std::is_same_v<decltype(ret), Iter2>);
+      assert(base(ret) == std::data(out) + std::size(out));
+      for (int i = 0; i != size; ++i)
+        assert(out[i] == i + 1);
+    }
+  }
+};
+
+struct TestIteratorsInt {
+  template <class Iter2>
+  void operator()() {
+    types::for_each(types::forward_iterator_list<int*>{},
+                    TestIteratorWithPolicies<types::partial_instantiation<TestInt, Iter2>::template apply>{});
+  }
+};
+
+struct CopiedToTester {
+  bool copied_to = false;
+  CopiedToTester() = default;
+  CopiedToTester(const CopiedToTester&) {}
+  CopiedToTester& operator=(const CopiedToTester&) {
+    assert(!copied_to);
+    copied_to = true;
+    return *this;
+  }
+  ~CopiedToTester() = default;
+};
+
+template <class Iter1, class Iter2>
+struct TestNonTrivial {
+  template <class Policy>
+  void operator()(Policy&& policy) {
+    // simple test
+    for (const int size : {0, 1, 2, 100, 350}) {
+      std::vector<CopiedToTester> a(size);
+
+      std::vector<CopiedToTester> out(std::size(a));
+      auto ret = std::copy_n(policy, Iter1(std::data(a)), std::size(a), Iter2(std::data(out)));
+      assert(base(ret) == std::data(out) + std::size(out));
+      assert(std::all_of(std::begin(out), std::end(out), [](CopiedToTester& t) { return t.copied_to; }));
+      assert(std::none_of(std::begin(a), std::end(a), [](CopiedToTester& t) { return t.copied_to; }));
+    }
+  }
+};
+
+struct TestIteratorsNonTrivial {
+  template <class Iter2>
+  void operator()() {
+    types::for_each(types::forward_iterator_list<CopiedToTester*>{},
+                    TestIteratorWithPolicies<types::partial_instantiation<TestNonTrivial, Iter2>::template apply>{});
+  }
+};
+
+int main(int, char**) {
+  types::for_each(types::forward_iterator_list<int*>{}, TestIteratorsInt{});
+  types::for_each(types::forward_iterator_list<CopiedToTester*>{}, TestIteratorsNonTrivial{});
+
+  return 0;
+}

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

 #include "test_macros.h"
 #include "test_execution_policies.h"
 #include "test_iterators.h"
 
 // We can't test the constraint on the execution policy, because that would conflict with the binary
 // transform algorithm that doesn't take an execution policy, which is not constrained at all.
 
 template <class Iter1, class Iter2>
-struct Test {
+struct TestInt {
   template <class Policy>
   void operator()(Policy&& policy) {
     // simple test
     for (const int size : {0, 1, 2, 100, 350}) {
       std::vector<int> a(size);
       for (int i = 0; i != size; ++i)
         a[i] = i + 1;
 
       std::vector<int> out(std::size(a));
       decltype(auto) ret = std::transform(
           policy, Iter1(std::data(a)), Iter1(std::data(a) + std::size(a)), Iter2(std::data(out)), [](int i) {
             return i + 3;
           });
       static_assert(std::is_same_v<decltype(ret), Iter2>);
       assert(base(ret) == std::data(out) + std::size(out));
       for (int i = 0; i != size; ++i)
         assert(out[i] == i + 4);
     }
   }
 };
 
-struct TestIterators {
+struct TestIteratorsInt {
   template <class Iter2>
   void operator()() {
     types::for_each(types::forward_iterator_list<int*>{},
                     TestIteratorWithPolicies<types::partial_instantiation<Test, Iter2>::template apply>{});
   }
 };
 
 int main(int, char**) {
-  types::for_each(types::forward_iterator_list<int*>{}, TestIterators{});
+  types::for_each(types::forward_iterator_list<int*>{}, TestIteratorsInt{});
 
   return 0;
 }

libcxx/test/support/type_algorithms.h

 template <class... Types>
 TEST_CONSTEXPR_CXX14 void swallow(Types...) {}
 
 template <class... Types, class Functor>
 TEST_CONSTEXPR_CXX14 void for_each(type_list<Types...>, Functor f) {
   swallow((f.template operator()<Types>(), 0)...);
 }
 
+#if TEST_STD_VER >= 17
+template <class Func>
+struct apply_type_identity {
+  Func func_;
+
+  apply_type_identity(Func func) : func_(func) {}
+
+  template <class... Args>
+  decltype(auto) operator()() const {
+    return func_(std::type_identity<Args>{}...);
+  }
+};
+
+template <class T>
+apply_type_identity(T) -> apply_type_identity<T>;
+
+#endif
 
 template <template <class...> class T, class... Args>
 struct partial_instantiation {
   template <class Other>
   using apply = T<Args..., Other>;
 };
 
 // type categories defined in [basic.fundamental] plus extensions (without CV-qualifiers)