[libc++] Add C++20 contiguous_iterator_tag.

This work is part of an ongoing effort to allow libc++ to
optimize user provided contiguous iterators.

3 files changed, 48 insertions, 1 deletions

diff --git a/libcxx/include/iterator b/libcxx/include/iterator
index c5c0f669ee8..6a9a08241b6 100644
--- a/libcxx/include/iterator
+++ b/libcxx/include/iterator
@@ -440,6 +440,11 @@ struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {};
 struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag       : public input_iterator_tag {};
 struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag {};
 struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {};
+#if _LIBCPP_STD_VER > 17
+// TODO(EricWF)  contiguous_iterator_tag is provided as an extension prior to
+//  C++20 to allow optimizations for users providing wrapped iterator types.
+struct _LIBCPP_TEMPLATE_VIS contiguous_iterator_tag: public random_access_iterator_tag { };
+#endif
 
 template <class _Tp>
 struct __has_iterator_typedefs
@@ -510,6 +515,9 @@ struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*>
     typedef _Tp* pointer;
     typedef _Tp& reference;
     typedef random_access_iterator_tag iterator_category;
+#if _LIBCPP_STD_VER > 17
+    typedef contiguous_iterator_tag    iterator_concept;
+#endif
 };
 
 template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value>
@@ -532,6 +540,11 @@ struct __is_bidirectional_iterator : public __has_iterator_category_convertible_
 template <class _Tp>
 struct __is_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {};
 
+#if _LIBCPP_STD_VER > 17
+template <class _Tp>
+struct __is_contiguous_iterator : public __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag> {};
+#endif
+
 template <class _Tp>
 struct __is_exactly_input_iterator
     : public integral_constant<bool,
diff --git a/libcxx/test/std/iterators/iterator.primitives/iterator.traits/pointer.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/iterator.traits/pointer.pass.cpp
index 79deed7b7ba..4cf214a8be8 100644
--- a/libcxx/test/std/iterators/iterator.primitives/iterator.traits/pointer.pass.cpp
+++ b/libcxx/test/std/iterators/iterator.primitives/iterator.traits/pointer.pass.cpp
@@ -16,6 +16,7 @@
 //   typedef T*                         pointer;
 //   typedef T&                         reference;
 //   typedef random_access_iterator_tag iterator_category;
+//   typedef contiguous_iterator_tag iterator_category; // C++20
 // };
 
 #include <iterator>
@@ -33,6 +34,8 @@ int main(int, char**)
     static_assert((std::is_same<It::pointer, A*>::value), "");
     static_assert((std::is_same<It::reference, A&>::value), "");
     static_assert((std::is_same<It::iterator_category, std::random_access_iterator_tag>::value), "");
-
+#if TEST_STD_VER > 17
+    ASSERT_SAME_TYPE(It::iterator_concept, std::contiguous_iterator_tag);
+#endif
   return 0;
 }
diff --git a/libcxx/test/std/iterators/iterator.primitives/std.iterator.tags/contiguous_iterator_tag.pass.cpp b/libcxx/test/std/iterators/iterator.primitives/std.iterator.tags/contiguous_iterator_tag.pass.cpp
new file mode 100644
index 00000000000..7527668c7a5
--- /dev/null
+++ b/libcxx/test/std/iterators/iterator.primitives/std.iterator.tags/contiguous_iterator_tag.pass.cpp
@@ -0,0 +1,31 @@
+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// <iterator>
+
+// struct contiguous_iterator_tag : public random_access_iterator_tag {};
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17
+
+
+#include <iterator>
+#include <type_traits>
+
+#include "test_macros.h"
+
+int main(int, char**)
+{
+    std::contiguous_iterator_tag tag;
+    ((void)tag); // Prevent unused warning
+    static_assert((std::is_base_of<std::random_access_iterator_tag,
+                                   std::contiguous_iterator_tag>::value), "");
+    static_assert((!std::is_base_of<std::output_iterator_tag,
+                                    std::contiguous_iterator_tag>::value), "");
+
+  return 0;
+}