[libc++][nfc] Move iterator_traits and related into __iterator/iterator_traits.h.
Based on D100682 and D99855.
(Note: I originally was going to just make this part of D99855, but I decided not to because this patch moves lots of unrelated code around, and I didn't want to make D99855 harder to review because of unrelated code-changes/moves.)
Differential Revision: https://reviews.llvm.org/D100686
GitOrigin-RevId: 120fa8293e22f760374a5757d081dc674046e0f0
diff --git a/include/iterator b/include/iterator
index b24f254..7570860 100644
--- a/include/iterator
+++ b/include/iterator
@@ -413,10 +413,11 @@
#include <__functional_base>
#include <type_traits>
#include <compare>
-#include <concepts>
+#include <concepts> // Mandated by the Standard.
#include <cstddef>
#include <initializer_list>
#include <__iterator/incrementable_traits.h>
+#include <__iterator/iterator_traits.h>
#include <__iterator/readable_traits.h>
#include <__memory/addressof.h>
#include <__memory/pointer_traits.h>
@@ -430,464 +431,6 @@
_LIBCPP_BEGIN_NAMESPACE_STD
-#if !defined(_LIBCPP_HAS_NO_RANGES)
-
-// [iterator.traits]
-template<__dereferenceable _Tp>
-using iter_reference_t = decltype(*declval<_Tp&>());
-#endif // !defined(_LIBCPP_HAS_NO_RANGES)
-
-template <class _Iter>
-struct _LIBCPP_TEMPLATE_VIS iterator_traits;
-
-struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {};
-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
-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
-{
-private:
- struct __two {char __lx; char __lxx;};
- template <class _Up> static __two __test(...);
- template <class _Up> static char __test(typename __void_t<typename _Up::iterator_category>::type* = 0,
- typename __void_t<typename _Up::difference_type>::type* = 0,
- typename __void_t<typename _Up::value_type>::type* = 0,
- typename __void_t<typename _Up::reference>::type* = 0,
- typename __void_t<typename _Up::pointer>::type* = 0);
-public:
- static const bool value = sizeof(__test<_Tp>(0,0,0,0,0)) == 1;
-};
-
-
-template <class _Tp>
-struct __has_iterator_category
-{
-private:
- struct __two {char __lx; char __lxx;};
- template <class _Up> static __two __test(...);
- template <class _Up> static char __test(typename _Up::iterator_category* = nullptr);
-public:
- static const bool value = sizeof(__test<_Tp>(nullptr)) == 1;
-};
-
-template <class _Tp>
-struct __has_iterator_concept
-{
-private:
- struct __two {char __lx; char __lxx;};
- template <class _Up> static __two __test(...);
- template <class _Up> static char __test(typename _Up::iterator_concept* = nullptr);
-public:
- static const bool value = sizeof(__test<_Tp>(nullptr)) == 1;
-};
-
-#if !defined(_LIBCPP_HAS_NO_RANGES)
-
-// The `cpp17-*-iterator` exposition-only concepts are easily confused with the Cpp17*Iterator tables,
-// so they've been banished to a namespace that makes it obvious they have a niche use-case.
-namespace __iterator_traits_detail {
-template<class _Ip>
-concept __cpp17_iterator =
- requires(_Ip __i) {
- { *__i } -> __referenceable;
- { ++__i } -> same_as<_Ip&>;
- { *__i++ } -> __referenceable;
- } &&
- copyable<_Ip>;
-
-template<class _Ip>
-concept __cpp17_input_iterator =
- __cpp17_iterator<_Ip> &&
- equality_comparable<_Ip> &&
- requires(_Ip __i) {
- typename incrementable_traits<_Ip>::difference_type;
- typename indirectly_readable_traits<_Ip>::value_type;
- typename common_reference_t<iter_reference_t<_Ip>&&,
- typename indirectly_readable_traits<_Ip>::value_type&>;
- typename common_reference_t<decltype(*__i++)&&,
- typename indirectly_readable_traits<_Ip>::value_type&>;
- requires signed_integral<typename incrementable_traits<_Ip>::difference_type>;
- };
-
-template<class _Ip>
-concept __cpp17_forward_iterator =
- __cpp17_input_iterator<_Ip> &&
- constructible_from<_Ip> &&
- is_lvalue_reference_v<iter_reference_t<_Ip>> &&
- same_as<remove_cvref_t<iter_reference_t<_Ip>>,
- typename indirectly_readable_traits<_Ip>::value_type> &&
- requires(_Ip __i) {
- { __i++ } -> convertible_to<_Ip const&>;
- { *__i++ } -> same_as<iter_reference_t<_Ip>>;
- };
-
-template<class _Ip>
-concept __cpp17_bidirectional_iterator =
- __cpp17_forward_iterator<_Ip> &&
- requires(_Ip __i) {
- { --__i } -> same_as<_Ip&>;
- { __i-- } -> convertible_to<_Ip const&>;
- { *__i-- } -> same_as<iter_reference_t<_Ip>>;
- };
-
-template<class _Ip>
-concept __cpp17_random_access_iterator =
- __cpp17_bidirectional_iterator<_Ip> and
- totally_ordered<_Ip> and
- requires(_Ip __i, typename incrementable_traits<_Ip>::difference_type __n) {
- { __i += __n } -> same_as<_Ip&>;
- { __i -= __n } -> same_as<_Ip&>;
- { __i + __n } -> same_as<_Ip>;
- { __n + __i } -> same_as<_Ip>;
- { __i - __n } -> same_as<_Ip>;
- { __i - __i } -> same_as<decltype(__n)>;
- { __i[__n] } -> convertible_to<iter_reference_t<_Ip>>;
- };
-} // namespace __iterator_traits_detail
-
-template<class _Ip>
-concept __has_member_reference = requires { typename _Ip::reference; };
-
-template<class _Ip>
-concept __has_member_pointer = requires { typename _Ip::pointer; };
-
-template<class _Ip>
-concept __has_member_iterator_category = requires { typename _Ip::iterator_category; };
-
-template<class _Ip>
-concept __specifies_members = requires {
- typename _Ip::value_type;
- typename _Ip::difference_type;
- requires __has_member_reference<_Ip>;
- requires __has_member_iterator_category<_Ip>;
- };
-
-template<class>
-struct __iterator_traits_member_pointer_or_void {
- using type = void;
-};
-
-template<__has_member_pointer _Tp>
-struct __iterator_traits_member_pointer_or_void<_Tp> {
- using type = typename _Tp::pointer;
-};
-
-template<class _Tp>
-concept __cpp17_iterator_missing_members =
- !__specifies_members<_Tp> &&
- __iterator_traits_detail::__cpp17_iterator<_Tp>;
-
-template<class _Tp>
-concept __cpp17_input_iterator_missing_members =
- __cpp17_iterator_missing_members<_Tp> &&
- __iterator_traits_detail::__cpp17_input_iterator<_Tp>;
-
-// Otherwise, `pointer` names `void`.
-template<class>
-struct __iterator_traits_member_pointer_or_arrow_or_void { using type = void; };
-
-// [iterator.traits]/3.2.1
-// If the qualified-id `I::pointer` is valid and denotes a type, `pointer` names that type.
-template<__has_member_pointer _Ip>
-struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { using type = typename _Ip::pointer; };
-
-// Otherwise, if `decltype(declval<I&>().operator->())` is well-formed, then `pointer` names that
-// type.
-template<class _Ip>
-concept __has_arrow =
- requires(_Ip& __i) {
- __i.operator->();
- };
-
-template<class _Ip>
- requires __has_arrow<_Ip> && (!__has_member_pointer<_Ip>)
-struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> {
- using type = decltype(declval<_Ip&>().operator->());
-};
-
-// Otherwise, `reference` names `iter-reference-t<I>`.
-template<class _Ip>
-struct __iterator_traits_member_reference { using type = iter_reference_t<_Ip>; };
-
-// [iterator.traits]/3.2.2
-// If the qualified-id `I::reference` is valid and denotes a type, `reference` names that type.
-template<__has_member_reference _Ip>
-struct __iterator_traits_member_reference<_Ip> { using type = typename _Ip::reference; };
-
-// [iterator.traits]/3.2.3.4
-// input_iterator_tag
-template<class _Ip>
-struct __deduce_iterator_category {
- using type = input_iterator_tag;
-};
-
-// [iterator.traits]/3.2.3.1
-// `random_access_iterator_tag` if `I` satisfies `cpp17-random-access-iterator`, or otherwise
-template<__iterator_traits_detail::__cpp17_random_access_iterator _Ip>
-struct __deduce_iterator_category<_Ip> {
- using type = random_access_iterator_tag;
-};
-
-// [iterator.traits]/3.2.3.2
-// `bidirectional_iterator_tag` if `I` satisfies `cpp17-bidirectional-iterator`, or otherwise
-template<__iterator_traits_detail::__cpp17_bidirectional_iterator _Ip>
-struct __deduce_iterator_category<_Ip> {
- using type = bidirectional_iterator_tag;
-};
-
-// [iterator.traits]/3.2.3.3
-// `forward_iterator_tag` if `I` satisfies `cpp17-forward-iterator`, or otherwise
-template<__iterator_traits_detail::__cpp17_forward_iterator _Ip>
-struct __deduce_iterator_category<_Ip> {
- using type = forward_iterator_tag;
-};
-
-template<class _Ip>
-struct __iterator_traits_iterator_category : __deduce_iterator_category<_Ip> {};
-
-// [iterator.traits]/3.2.3
-// If the qualified-id `I::iterator-category` is valid and denotes a type, `iterator-category` names
-// that type.
-template<__has_member_iterator_category _Ip>
-struct __iterator_traits_iterator_category<_Ip> {
- using type = typename _Ip::iterator_category;
-};
-
-// otherwise, it names void.
-template<class>
-struct __iterator_traits_difference_type { using type = void; };
-
-// If the qualified-id `incrementable_traits<I>::difference_type` is valid and denotes a type, then
-// `difference_type` names that type;
-template<class _Ip>
-requires requires { typename incrementable_traits<_Ip>::difference_type; }
-struct __iterator_traits_difference_type<_Ip> {
- using type = typename incrementable_traits<_Ip>::difference_type;
-};
-
-// [iterator.traits]/3.4
-// Otherwise, `iterator_traits<I>` has no members by any of the above names.
-template<class>
-struct __iterator_traits {};
-
-// [iterator.traits]/3.1
-// If `I` has valid ([temp.deduct]) member types `difference-type`, `value-type`, `reference`, and
-// `iterator-category`, then `iterator-traits<I>` has the following publicly accessible members:
-template<__specifies_members _Ip>
-struct __iterator_traits<_Ip> {
- using iterator_category = typename _Ip::iterator_category;
- using value_type = typename _Ip::value_type;
- using difference_type = typename _Ip::difference_type;
- using pointer = typename __iterator_traits_member_pointer_or_void<_Ip>::type;
- using reference = typename _Ip::reference;
-};
-
-// [iterator.traits]/3.2
-// Otherwise, if `I` satisfies the exposition-only concept `cpp17-input-iterator`,
-// `iterator-traits<I>` has the following publicly accessible members:
-template<__cpp17_input_iterator_missing_members _Ip>
-struct __iterator_traits<_Ip> {
- using iterator_category = typename __iterator_traits_iterator_category<_Ip>::type;
- using value_type = typename indirectly_readable_traits<_Ip>::value_type;
- using difference_type = typename incrementable_traits<_Ip>::difference_type;
- using pointer = typename __iterator_traits_member_pointer_or_arrow_or_void<_Ip>::type;
- using reference = typename __iterator_traits_member_reference<_Ip>::type;
-};
-
-// Otherwise, if `I` satisfies the exposition-only concept `cpp17-iterator`, then
-// `iterator_traits<I>` has the following publicly accessible members:
-template<__cpp17_iterator_missing_members _Ip>
-struct __iterator_traits<_Ip> {
- using iterator_category = output_iterator_tag;
- using value_type = void;
- using difference_type = typename __iterator_traits_difference_type<_Ip>::type;
- using pointer = void;
- using reference = void;
-};
-
-template<class _Ip>
-struct iterator_traits : __iterator_traits<_Ip> {
- using __primary_template = iterator_traits;
-};
-
-#else // !defined(_LIBCPP_HAS_NO_RANGES)
-
-template <class _Iter, bool> struct __iterator_traits {};
-
-template <class _Iter, bool> struct __iterator_traits_impl {};
-
-template <class _Iter>
-struct __iterator_traits_impl<_Iter, true>
-{
- typedef typename _Iter::difference_type difference_type;
- typedef typename _Iter::value_type value_type;
- typedef typename _Iter::pointer pointer;
- typedef typename _Iter::reference reference;
- typedef typename _Iter::iterator_category iterator_category;
-};
-
-template <class _Iter>
-struct __iterator_traits<_Iter, true>
- : __iterator_traits_impl
- <
- _Iter,
- is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value ||
- is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value
- >
-{};
-
-// iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category
-// exists. Else iterator_traits<Iterator> will be an empty class. This is a
-// conforming extension which allows some programs to compile and behave as
-// the client expects instead of failing at compile time.
-
-template <class _Iter>
-struct _LIBCPP_TEMPLATE_VIS iterator_traits
- : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> {
-
- using __primary_template = iterator_traits;
-};
-#endif // !defined(_LIBCPP_HAS_NO_RANGES)
-
-template<class _Tp>
-#if !defined(_LIBCPP_HAS_NO_RANGES)
-requires is_object_v<_Tp>
-#endif
-struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*>
-{
- typedef ptrdiff_t difference_type;
- typedef typename remove_cv<_Tp>::type value_type;
- 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>
-struct __has_iterator_category_convertible_to
- : _BoolConstant<is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>::value>
-{};
-
-template <class _Tp, class _Up>
-struct __has_iterator_category_convertible_to<_Tp, _Up, false> : false_type {};
-
-template <class _Tp, class _Up, bool = __has_iterator_concept<_Tp>::value>
-struct __has_iterator_concept_convertible_to
- : _BoolConstant<is_convertible<typename _Tp::iterator_concept, _Up>::value>
-{};
-
-template <class _Tp, class _Up>
-struct __has_iterator_concept_convertible_to<_Tp, _Up, false> : false_type {};
-
-template <class _Tp>
-struct __is_cpp17_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {};
-
-template <class _Tp>
-struct __is_cpp17_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {};
-
-template <class _Tp>
-struct __is_cpp17_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {};
-
-template <class _Tp>
-struct __is_cpp17_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {};
-
-// __is_cpp17_contiguous_iterator determines if an iterator is contiguous,
-// either because it advertises itself as such (in C++20) or because it
-// is a pointer type or a known trivial wrapper around a pointer type,
-// such as __wrap_iter<T*>.
-//
-#if _LIBCPP_STD_VER > 17
-template <class _Tp>
-struct __is_cpp17_contiguous_iterator : _Or<
- __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>,
- __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag>
-> {};
-#else
-template <class _Tp>
-struct __is_cpp17_contiguous_iterator : false_type {};
-#endif
-
-// Any native pointer which is an iterator is also a contiguous iterator.
-template <class _Up>
-struct __is_cpp17_contiguous_iterator<_Up*> : true_type {};
-
-
-template <class _Tp>
-struct __is_exactly_cpp17_input_iterator
- : public integral_constant<bool,
- __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value &&
- !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value> {};
-
-#ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
-template<class _InputIterator>
-using __iter_value_type = typename iterator_traits<_InputIterator>::value_type;
-
-template<class _InputIterator>
-using __iter_key_type = remove_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>;
-
-template<class _InputIterator>
-using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type;
-
-template<class _InputIterator>
-using __iter_to_alloc_type = pair<
- add_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>,
- typename iterator_traits<_InputIterator>::value_type::second_type>;
-#endif
-
template<class _Category, class _Tp, class _Distance = ptrdiff_t,
class _Pointer = _Tp*, class _Reference = _Tp&>
struct _LIBCPP_TEMPLATE_VIS iterator