| // -*- 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 _LIBCPP___ITERATOR_ITERATOR_TRAITS_H | |
| #define _LIBCPP___ITERATOR_ITERATOR_TRAITS_H | |
| #include <__concepts/arithmetic.h> | |
| #include <__concepts/constructible.h> | |
| #include <__concepts/convertible_to.h> | |
| #include <__concepts/copyable.h> | |
| #include <__concepts/equality_comparable.h> | |
| #include <__concepts/same_as.h> | |
| #include <__concepts/totally_ordered.h> | |
| #include <__config> | |
| #include <__cstddef/ptrdiff_t.h> | |
| #include <__fwd/pair.h> | |
| #include <__iterator/incrementable_traits.h> | |
| #include <__iterator/readable_traits.h> | |
| #include <__tuple/tuple_element.h> | |
| #include <__type_traits/common_reference.h> | |
| #include <__type_traits/conditional.h> | |
| #include <__type_traits/detected_or.h> | |
| #include <__type_traits/disjunction.h> | |
| #include <__type_traits/integral_constant.h> | |
| #include <__type_traits/is_convertible.h> | |
| #include <__type_traits/is_object.h> | |
| #include <__type_traits/is_primary_template.h> | |
| #include <__type_traits/is_reference.h> | |
| #include <__type_traits/is_referenceable.h> | |
| #include <__type_traits/nat.h> | |
| #include <__type_traits/remove_const.h> | |
| #include <__type_traits/remove_cv.h> | |
| #include <__type_traits/remove_cvref.h> | |
| #include <__type_traits/void_t.h> | |
| #include <__utility/declval.h> | |
| #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) | |
| # pragma GCC system_header | |
| #endif | |
| _LIBCPP_BEGIN_NAMESPACE_STD | |
| #if _LIBCPP_STD_VER >= 20 | |
| template <class _Tp> | |
| concept __dereferenceable = requires(_Tp& __t) { | |
| { *__t } -> __referenceable; // not required to be equality-preserving | |
| }; | |
| // [iterator.traits] | |
| template <__dereferenceable _Tp> | |
| using iter_reference_t = decltype(*std::declval<_Tp&>()); | |
| #endif // _LIBCPP_STD_VER >= 20 | |
| template <class _Iter> | |
| struct iterator_traits; | |
| struct input_iterator_tag {}; | |
| struct output_iterator_tag {}; | |
| struct forward_iterator_tag : public input_iterator_tag {}; | |
| struct bidirectional_iterator_tag : public forward_iterator_tag {}; | |
| struct random_access_iterator_tag : public bidirectional_iterator_tag {}; | |
| #if _LIBCPP_STD_VER >= 20 | |
| struct contiguous_iterator_tag : public random_access_iterator_tag {}; | |
| #endif | |
| #if _LIBCPP_STD_VER >= 20 | |
| // The `cpp17-*-iterator` exposition-only concepts have very similar names to the `Cpp17*Iterator` named requirements | |
| // from `[iterator.cpp17]`. To avoid confusion between the two, the exposition-only concepts have been banished to | |
| // a "detail" namespace indicating 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_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> && totally_ordered<_Ip> && | |
| 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)>; // NOLINT(misc-redundant-expression) ; This is llvm.org/PR54114 | |
| { __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 _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 _LIBCPP_NODEBUG = 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 _LIBCPP_NODEBUG = typename _Ip::pointer; | |
| }; | |
| // Otherwise, if `decltype(declval<I&>().operator->())` is well-formed, then `pointer` names that | |
| // type. | |
| template <class _Ip> | |
| requires requires(_Ip& __i) { __i.operator->(); } && (!__has_member_pointer<_Ip>) | |
| struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> { | |
| using type _LIBCPP_NODEBUG = decltype(std::declval<_Ip&>().operator->()); | |
| }; | |
| // Otherwise, `reference` names `iter-reference-t<I>`. | |
| template <class _Ip> | |
| struct __iterator_traits_member_reference { | |
| using type _LIBCPP_NODEBUG = 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 _LIBCPP_NODEBUG = typename _Ip::reference; | |
| }; | |
| // [iterator.traits]/3.2.3.4 | |
| // input_iterator_tag | |
| template <class _Ip> | |
| struct __deduce_iterator_category { | |
| using type _LIBCPP_NODEBUG = 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 _LIBCPP_NODEBUG = 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 _LIBCPP_NODEBUG = 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 _LIBCPP_NODEBUG = 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 _LIBCPP_NODEBUG = typename _Ip::iterator_category; | |
| }; | |
| // otherwise, it names void. | |
| template <class> | |
| struct __iterator_traits_difference_type { | |
| using type _LIBCPP_NODEBUG = 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 _LIBCPP_NODEBUG = 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 {}; | |
| template <class _Tp> | |
| using __pointer_member _LIBCPP_NODEBUG = typename _Tp::pointer; | |
| // [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 = __detected_or_t<void, __pointer_member, _Ip>; | |
| 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 _LIBCPP_NODEBUG = iterator_traits; | |
| }; | |
| #else // _LIBCPP_STD_VER >= 20 | |
| 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 > {}; | |
| template <class _Tp> | |
| struct __has_iterator_typedefs { | |
| private: | |
| template <class _Up> | |
| static false_type __test(...); | |
| template <class _Up> | |
| static true_type | |
| __test(__void_t<typename _Up::iterator_category>* = nullptr, | |
| __void_t<typename _Up::difference_type>* = nullptr, | |
| __void_t<typename _Up::value_type>* = nullptr, | |
| __void_t<typename _Up::reference>* = nullptr, | |
| __void_t<typename _Up::pointer>* = nullptr); | |
| public: | |
| static const bool value = decltype(__test<_Tp>(nullptr, nullptr, nullptr, nullptr, nullptr))::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 iterator_traits : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> { | |
| using __primary_template _LIBCPP_NODEBUG = iterator_traits; | |
| }; | |
| #endif // _LIBCPP_STD_VER >= 20 | |
| template <class _Tp> | |
| #if _LIBCPP_STD_VER >= 20 | |
| requires is_object_v<_Tp> | |
| #endif | |
| struct iterator_traits<_Tp*> { | |
| typedef ptrdiff_t difference_type; | |
| typedef __remove_cv_t<_Tp> value_type; | |
| typedef _Tp* pointer; | |
| typedef _Tp& reference; | |
| typedef random_access_iterator_tag iterator_category; | |
| #if _LIBCPP_STD_VER >= 20 | |
| typedef contiguous_iterator_tag iterator_concept; | |
| #endif | |
| }; | |
| template <class _Tp> | |
| using __iterator_category _LIBCPP_NODEBUG = typename _Tp::iterator_category; | |
| template <class _Tp> | |
| using __iterator_concept _LIBCPP_NODEBUG = typename _Tp::iterator_concept; | |
| template <class _Tp, class _Up> | |
| using __has_iterator_category_convertible_to _LIBCPP_NODEBUG = | |
| is_convertible<__detected_or_t<__nat, __iterator_category, iterator_traits<_Tp> >, _Up>; | |
| template <class _Tp, class _Up> | |
| using __has_iterator_concept_convertible_to _LIBCPP_NODEBUG = | |
| is_convertible<__detected_or_t<__nat, __iterator_concept, _Tp>, _Up>; | |
| template <class _Tp> | |
| using __has_input_iterator_category _LIBCPP_NODEBUG = __has_iterator_category_convertible_to<_Tp, input_iterator_tag>; | |
| template <class _Tp> | |
| using __has_forward_iterator_category _LIBCPP_NODEBUG = | |
| __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>; | |
| template <class _Tp> | |
| using __has_bidirectional_iterator_category _LIBCPP_NODEBUG = | |
| __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>; | |
| template <class _Tp> | |
| using __has_random_access_iterator_category _LIBCPP_NODEBUG = | |
| __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>; | |
| // __libcpp_is_contiguous_iterator determines if an iterator is known by | |
| // libc++ to be 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 (possibly fancy) pointer type, such as __wrap_iter<T*>. | |
| // Such iterators receive special "contiguous" optimizations in | |
| // std::copy and std::sort. | |
| // | |
| #if _LIBCPP_STD_VER >= 20 | |
| template <class _Tp> | |
| struct __libcpp_is_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 __libcpp_is_contiguous_iterator : false_type {}; | |
| #endif | |
| // Any native pointer which is an iterator is also a contiguous iterator. | |
| template <class _Up> | |
| struct __libcpp_is_contiguous_iterator<_Up*> : true_type {}; | |
| template <class _Iter> | |
| class __wrap_iter; | |
| template <class _Tp> | |
| using __has_exactly_input_iterator_category _LIBCPP_NODEBUG = | |
| integral_constant<bool, | |
| __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value && | |
| !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value>; | |
| template <class _Tp> | |
| using __has_exactly_forward_iterator_category _LIBCPP_NODEBUG = | |
| integral_constant<bool, | |
| __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value && | |
| !__has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value>; | |
| template <class _Tp> | |
| using __has_exactly_bidirectional_iterator_category _LIBCPP_NODEBUG = | |
| integral_constant<bool, | |
| __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value && | |
| !__has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>::value>; | |
| template <class _InputIterator> | |
| using __iterator_value_type _LIBCPP_NODEBUG = typename iterator_traits<_InputIterator>::value_type; | |
| #if _LIBCPP_STD_VER >= 23 | |
| template <class _InputIterator> | |
| using __iter_key_type _LIBCPP_NODEBUG = remove_const_t<tuple_element_t<0, __iterator_value_type<_InputIterator>>>; | |
| template <class _InputIterator> | |
| using __iter_mapped_type _LIBCPP_NODEBUG = tuple_element_t<1, __iterator_value_type<_InputIterator>>; | |
| template <class _InputIterator> | |
| using __iter_to_alloc_type _LIBCPP_NODEBUG = | |
| pair<const tuple_element_t<0, __iterator_value_type<_InputIterator>>, | |
| tuple_element_t<1, __iterator_value_type<_InputIterator>>>; | |
| #else | |
| template <class _InputIterator> | |
| using __iter_key_type _LIBCPP_NODEBUG = __remove_const_t<typename __iterator_value_type<_InputIterator>::first_type>; | |
| template <class _InputIterator> | |
| using __iter_mapped_type _LIBCPP_NODEBUG = typename __iterator_value_type<_InputIterator>::second_type; | |
| template <class _InputIterator> | |
| using __iter_to_alloc_type _LIBCPP_NODEBUG = | |
| pair<const typename __iterator_value_type<_InputIterator>::first_type, | |
| typename __iterator_value_type<_InputIterator>::second_type>; | |
| #endif // _LIBCPP_STD_VER >= 23 | |
| template <class _Iter> | |
| using __iterator_iterator_category _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::iterator_category; | |
| template <class _Iter> | |
| using __iterator_pointer _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::pointer; | |
| template <class _Iter> | |
| using __iterator_difference_type _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::difference_type; | |
| template <class _Iter> | |
| using __iterator_reference _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::reference; | |
| #if _LIBCPP_STD_VER >= 20 | |
| // [readable.traits] | |
| // Let `RI` be `remove_cvref_t<I>`. The type `iter_value_t<I>` denotes | |
| // `indirectly_readable_traits<RI>::value_type` if `iterator_traits<RI>` names a specialization | |
| // generated from the primary template, and `iterator_traits<RI>::value_type` otherwise. | |
| // This has to be in this file and not readable_traits.h to break the include cycle between the two. | |
| template <class _Ip> | |
| using iter_value_t = | |
| typename conditional_t<__is_primary_template<iterator_traits<remove_cvref_t<_Ip> > >::value, | |
| indirectly_readable_traits<remove_cvref_t<_Ip> >, | |
| iterator_traits<remove_cvref_t<_Ip> > >::value_type; | |
| #endif // _LIBCPP_STD_VER >= 20 | |
| _LIBCPP_END_NAMESPACE_STD | |
| #endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H |