[libc++] Add _ITER_CONCEPT and _ITER_TRAITS implementations from C++20

These traits are currently unused because we don't implement ranges.
However, their addition is part of ongoing work to allow libc++
to optimize on user-provided contiguous iterators.

1 files changed, 52 insertions, 1 deletions

diff --git a/libcxx/include/iterator b/libcxx/include/iterator
index 6a9a08241b6..13329e1473d 100644
--- a/libcxx/include/iterator
+++ b/libcxx/include/iterator
@@ -434,6 +434,8 @@ template <class E> constexpr const E* data(initializer_list<E> il) noexcept;
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
+template <class _Iter>
+struct _LIBCPP_TEMPLATE_VIS iterator_traits;
 
 struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {};
 struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {};
@@ -446,6 +448,52 @@ struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_it
 struct _LIBCPP_TEMPLATE_VIS contiguous_iterator_tag: public random_access_iterator_tag { };
 #endif
 
+template <class _Iter>
+struct __iter_traits_cache {
+  using type = _If<
+    __is_primary_template<iterator_traits<_Iter> >::value,
+    _Iter,
+    iterator_traits<_Iter>
+  >;
+};
+template <class _Iter>
+using _ITER_TRAITS = typename __iter_traits_cache<_Iter>::type;
+
+struct __iter_concept_concept_test {
+  template <class _Iter>
+  using _Apply = typename _ITER_TRAITS<_Iter>::iterator_concept;
+};
+struct __iter_concept_category_test {
+  template <class _Iter>
+  using _Apply = typename _ITER_TRAITS<_Iter>::iterator_category;
+};
+struct __iter_concept_random_fallback {
+  template <class _Iter>
+  using _Apply = _EnableIf<
+                          __is_primary_template<iterator_traits<_Iter> >::value,
+                          random_access_iterator_tag
+                        >;
+};
+
+template <class _Iter, class _Tester> struct __test_iter_concept
+    : _IsValidExpansion<_Tester::template _Apply, _Iter>,
+      _Tester
+{
+};
+
+template <class _Iter>
+struct __iter_concept_cache {
+  using type = _Or<
+    __test_iter_concept<_Iter, __iter_concept_concept_test>,
+    __test_iter_concept<_Iter, __iter_concept_category_test>,
+    __test_iter_concept<_Iter, __iter_concept_random_fallback>
+  >;
+};
+
+template <class _Iter>
+using _ITER_CONCEPT = typename __iter_concept_cache<_Iter>::type::template _Apply<_Iter>;
+
+
 template <class _Tp>
 struct __has_iterator_typedefs
 {
@@ -505,7 +553,10 @@ struct __iterator_traits<_Iter, true>
 
 template <class _Iter>
 struct _LIBCPP_TEMPLATE_VIS iterator_traits
-    : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> {};
+    : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> {
+
+  using __primary_template = iterator_traits;
+};
 
 template<class _Tp>
 struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*>