480 lines · c
1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___ITERATOR_ITERATOR_TRAITS_H11#define _LIBCPP___ITERATOR_ITERATOR_TRAITS_H12 13#include <__concepts/arithmetic.h>14#include <__concepts/constructible.h>15#include <__concepts/convertible_to.h>16#include <__concepts/copyable.h>17#include <__concepts/equality_comparable.h>18#include <__concepts/same_as.h>19#include <__concepts/totally_ordered.h>20#include <__config>21#include <__cstddef/ptrdiff_t.h>22#include <__fwd/pair.h>23#include <__iterator/incrementable_traits.h>24#include <__iterator/readable_traits.h>25#include <__tuple/tuple_element.h>26#include <__type_traits/common_reference.h>27#include <__type_traits/conditional.h>28#include <__type_traits/detected_or.h>29#include <__type_traits/disjunction.h>30#include <__type_traits/integral_constant.h>31#include <__type_traits/is_convertible.h>32#include <__type_traits/is_object.h>33#include <__type_traits/is_primary_template.h>34#include <__type_traits/is_reference.h>35#include <__type_traits/is_referenceable.h>36#include <__type_traits/nat.h>37#include <__type_traits/remove_const.h>38#include <__type_traits/remove_cv.h>39#include <__type_traits/remove_cvref.h>40#include <__type_traits/void_t.h>41#include <__utility/declval.h>42 43#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)44# pragma GCC system_header45#endif46 47_LIBCPP_BEGIN_NAMESPACE_STD48 49#if _LIBCPP_STD_VER >= 2050 51template <class _Tp>52concept __dereferenceable = requires(_Tp& __t) {53 { *__t } -> __referenceable; // not required to be equality-preserving54};55 56// [iterator.traits]57template <__dereferenceable _Tp>58using iter_reference_t = decltype(*std::declval<_Tp&>());59 60#endif // _LIBCPP_STD_VER >= 2061 62template <class _Iter>63struct iterator_traits;64 65struct input_iterator_tag {};66struct output_iterator_tag {};67struct forward_iterator_tag : public input_iterator_tag {};68struct bidirectional_iterator_tag : public forward_iterator_tag {};69struct random_access_iterator_tag : public bidirectional_iterator_tag {};70#if _LIBCPP_STD_VER >= 2071struct contiguous_iterator_tag : public random_access_iterator_tag {};72#endif73 74#if _LIBCPP_STD_VER >= 2075 76// The `cpp17-*-iterator` exposition-only concepts have very similar names to the `Cpp17*Iterator` named requirements77// from `[iterator.cpp17]`. To avoid confusion between the two, the exposition-only concepts have been banished to78// a "detail" namespace indicating they have a niche use-case.79namespace __iterator_traits_detail {80template <class _Ip>81concept __cpp17_iterator = requires(_Ip __i) {82 { *__i } -> __referenceable;83 { ++__i } -> same_as<_Ip&>;84 { *__i++ } -> __referenceable;85} && copyable<_Ip>;86 87template <class _Ip>88concept __cpp17_input_iterator = __cpp17_iterator<_Ip> && equality_comparable<_Ip> && requires(_Ip __i) {89 typename incrementable_traits<_Ip>::difference_type;90 typename indirectly_readable_traits<_Ip>::value_type;91 typename common_reference_t<iter_reference_t<_Ip>&&, typename indirectly_readable_traits<_Ip>::value_type&>;92 typename common_reference_t<decltype(*__i++)&&, typename indirectly_readable_traits<_Ip>::value_type&>;93 requires signed_integral<typename incrementable_traits<_Ip>::difference_type>;94};95 96template <class _Ip>97concept __cpp17_forward_iterator =98 __cpp17_input_iterator<_Ip> && constructible_from<_Ip> && is_reference_v<iter_reference_t<_Ip>> &&99 same_as<remove_cvref_t<iter_reference_t<_Ip>>, typename indirectly_readable_traits<_Ip>::value_type> &&100 requires(_Ip __i) {101 { __i++ } -> convertible_to<_Ip const&>;102 { *__i++ } -> same_as<iter_reference_t<_Ip>>;103 };104 105template <class _Ip>106concept __cpp17_bidirectional_iterator = __cpp17_forward_iterator<_Ip> && requires(_Ip __i) {107 { --__i } -> same_as<_Ip&>;108 { __i-- } -> convertible_to<_Ip const&>;109 { *__i-- } -> same_as<iter_reference_t<_Ip>>;110};111 112template <class _Ip>113concept __cpp17_random_access_iterator =114 __cpp17_bidirectional_iterator<_Ip> && totally_ordered<_Ip> &&115 requires(_Ip __i, typename incrementable_traits<_Ip>::difference_type __n) {116 { __i += __n } -> same_as<_Ip&>;117 { __i -= __n } -> same_as<_Ip&>;118 { __i + __n } -> same_as<_Ip>;119 { __n + __i } -> same_as<_Ip>;120 { __i - __n } -> same_as<_Ip>;121 { __i - __i } -> same_as<decltype(__n)>; // NOLINT(misc-redundant-expression) ; This is llvm.org/PR54114122 { __i[__n] } -> convertible_to<iter_reference_t<_Ip>>;123 };124} // namespace __iterator_traits_detail125 126template <class _Ip>127concept __has_member_reference = requires { typename _Ip::reference; };128 129template <class _Ip>130concept __has_member_pointer = requires { typename _Ip::pointer; };131 132template <class _Ip>133concept __has_member_iterator_category = requires { typename _Ip::iterator_category; };134 135template <class _Ip>136concept __specifies_members = requires {137 typename _Ip::value_type;138 typename _Ip::difference_type;139 requires __has_member_reference<_Ip>;140 requires __has_member_iterator_category<_Ip>;141};142 143template <class _Tp>144concept __cpp17_iterator_missing_members = !__specifies_members<_Tp> && __iterator_traits_detail::__cpp17_iterator<_Tp>;145 146template <class _Tp>147concept __cpp17_input_iterator_missing_members =148 __cpp17_iterator_missing_members<_Tp> && __iterator_traits_detail::__cpp17_input_iterator<_Tp>;149 150// Otherwise, `pointer` names `void`.151template <class>152struct __iterator_traits_member_pointer_or_arrow_or_void {153 using type _LIBCPP_NODEBUG = void;154};155 156// [iterator.traits]/3.2.1157// If the qualified-id `I::pointer` is valid and denotes a type, `pointer` names that type.158template <__has_member_pointer _Ip>159struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> {160 using type _LIBCPP_NODEBUG = typename _Ip::pointer;161};162 163// Otherwise, if `decltype(declval<I&>().operator->())` is well-formed, then `pointer` names that164// type.165template <class _Ip>166 requires requires(_Ip& __i) { __i.operator->(); } && (!__has_member_pointer<_Ip>)167struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> {168 using type _LIBCPP_NODEBUG = decltype(std::declval<_Ip&>().operator->());169};170 171// Otherwise, `reference` names `iter-reference-t<I>`.172template <class _Ip>173struct __iterator_traits_member_reference {174 using type _LIBCPP_NODEBUG = iter_reference_t<_Ip>;175};176 177// [iterator.traits]/3.2.2178// If the qualified-id `I::reference` is valid and denotes a type, `reference` names that type.179template <__has_member_reference _Ip>180struct __iterator_traits_member_reference<_Ip> {181 using type _LIBCPP_NODEBUG = typename _Ip::reference;182};183 184// [iterator.traits]/3.2.3.4185// input_iterator_tag186template <class _Ip>187struct __deduce_iterator_category {188 using type _LIBCPP_NODEBUG = input_iterator_tag;189};190 191// [iterator.traits]/3.2.3.1192// `random_access_iterator_tag` if `I` satisfies `cpp17-random-access-iterator`, or otherwise193template <__iterator_traits_detail::__cpp17_random_access_iterator _Ip>194struct __deduce_iterator_category<_Ip> {195 using type _LIBCPP_NODEBUG = random_access_iterator_tag;196};197 198// [iterator.traits]/3.2.3.2199// `bidirectional_iterator_tag` if `I` satisfies `cpp17-bidirectional-iterator`, or otherwise200template <__iterator_traits_detail::__cpp17_bidirectional_iterator _Ip>201struct __deduce_iterator_category<_Ip> {202 using type _LIBCPP_NODEBUG = bidirectional_iterator_tag;203};204 205// [iterator.traits]/3.2.3.3206// `forward_iterator_tag` if `I` satisfies `cpp17-forward-iterator`, or otherwise207template <__iterator_traits_detail::__cpp17_forward_iterator _Ip>208struct __deduce_iterator_category<_Ip> {209 using type _LIBCPP_NODEBUG = forward_iterator_tag;210};211 212template <class _Ip>213struct __iterator_traits_iterator_category : __deduce_iterator_category<_Ip> {};214 215// [iterator.traits]/3.2.3216// If the qualified-id `I::iterator-category` is valid and denotes a type, `iterator-category` names217// that type.218template <__has_member_iterator_category _Ip>219struct __iterator_traits_iterator_category<_Ip> {220 using type _LIBCPP_NODEBUG = typename _Ip::iterator_category;221};222 223// otherwise, it names void.224template <class>225struct __iterator_traits_difference_type {226 using type _LIBCPP_NODEBUG = void;227};228 229// If the qualified-id `incrementable_traits<I>::difference_type` is valid and denotes a type, then230// `difference_type` names that type;231template <class _Ip>232 requires requires { typename incrementable_traits<_Ip>::difference_type; }233struct __iterator_traits_difference_type<_Ip> {234 using type _LIBCPP_NODEBUG = typename incrementable_traits<_Ip>::difference_type;235};236 237// [iterator.traits]/3.4238// Otherwise, `iterator_traits<I>` has no members by any of the above names.239template <class>240struct __iterator_traits {};241 242template <class _Tp>243using __pointer_member _LIBCPP_NODEBUG = typename _Tp::pointer;244 245// [iterator.traits]/3.1246// If `I` has valid ([temp.deduct]) member types `difference-type`, `value-type`, `reference`, and247// `iterator-category`, then `iterator-traits<I>` has the following publicly accessible members:248template <__specifies_members _Ip>249struct __iterator_traits<_Ip> {250 using iterator_category = typename _Ip::iterator_category;251 using value_type = typename _Ip::value_type;252 using difference_type = typename _Ip::difference_type;253 using pointer = __detected_or_t<void, __pointer_member, _Ip>;254 using reference = typename _Ip::reference;255};256 257// [iterator.traits]/3.2258// Otherwise, if `I` satisfies the exposition-only concept `cpp17-input-iterator`,259// `iterator-traits<I>` has the following publicly accessible members:260template <__cpp17_input_iterator_missing_members _Ip>261struct __iterator_traits<_Ip> {262 using iterator_category = typename __iterator_traits_iterator_category<_Ip>::type;263 using value_type = typename indirectly_readable_traits<_Ip>::value_type;264 using difference_type = typename incrementable_traits<_Ip>::difference_type;265 using pointer = typename __iterator_traits_member_pointer_or_arrow_or_void<_Ip>::type;266 using reference = typename __iterator_traits_member_reference<_Ip>::type;267};268 269// Otherwise, if `I` satisfies the exposition-only concept `cpp17-iterator`, then270// `iterator_traits<I>` has the following publicly accessible members:271template <__cpp17_iterator_missing_members _Ip>272struct __iterator_traits<_Ip> {273 using iterator_category = output_iterator_tag;274 using value_type = void;275 using difference_type = typename __iterator_traits_difference_type<_Ip>::type;276 using pointer = void;277 using reference = void;278};279 280template <class _Ip>281struct iterator_traits : __iterator_traits<_Ip> {282 using __primary_template _LIBCPP_NODEBUG = iterator_traits;283};284 285#else // _LIBCPP_STD_VER >= 20286 287template <class _Iter, bool>288struct __iterator_traits {};289 290template <class _Iter, bool>291struct __iterator_traits_impl {};292 293template <class _Iter>294struct __iterator_traits_impl<_Iter, true> {295 typedef typename _Iter::difference_type difference_type;296 typedef typename _Iter::value_type value_type;297 typedef typename _Iter::pointer pointer;298 typedef typename _Iter::reference reference;299 typedef typename _Iter::iterator_category iterator_category;300};301 302template <class _Iter>303struct __iterator_traits<_Iter, true>304 : __iterator_traits_impl< _Iter,305 is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value ||306 is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value > {};307 308template <class _Tp>309struct __has_iterator_typedefs {310private:311 template <class _Up>312 static false_type __test(...);313 template <class _Up>314 static true_type315 __test(__void_t<typename _Up::iterator_category>* = nullptr,316 __void_t<typename _Up::difference_type>* = nullptr,317 __void_t<typename _Up::value_type>* = nullptr,318 __void_t<typename _Up::reference>* = nullptr,319 __void_t<typename _Up::pointer>* = nullptr);320 321public:322 static const bool value = decltype(__test<_Tp>(nullptr, nullptr, nullptr, nullptr, nullptr))::value;323};324 325// iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category326// exists. Else iterator_traits<Iterator> will be an empty class. This is a327// conforming extension which allows some programs to compile and behave as328// the client expects instead of failing at compile time.329 330template <class _Iter>331struct iterator_traits : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> {332 using __primary_template _LIBCPP_NODEBUG = iterator_traits;333};334#endif // _LIBCPP_STD_VER >= 20335 336template <class _Tp>337#if _LIBCPP_STD_VER >= 20338 requires is_object_v<_Tp>339#endif340struct iterator_traits<_Tp*> {341 typedef ptrdiff_t difference_type;342 typedef __remove_cv_t<_Tp> value_type;343 typedef _Tp* pointer;344 typedef _Tp& reference;345 typedef random_access_iterator_tag iterator_category;346#if _LIBCPP_STD_VER >= 20347 typedef contiguous_iterator_tag iterator_concept;348#endif349};350 351template <class _Tp>352using __iterator_category _LIBCPP_NODEBUG = typename _Tp::iterator_category;353 354template <class _Tp>355using __iterator_concept _LIBCPP_NODEBUG = typename _Tp::iterator_concept;356 357template <class _Tp, class _Up>358using __has_iterator_category_convertible_to _LIBCPP_NODEBUG =359 is_convertible<__detected_or_t<__nat, __iterator_category, iterator_traits<_Tp> >, _Up>;360 361template <class _Tp, class _Up>362using __has_iterator_concept_convertible_to _LIBCPP_NODEBUG =363 is_convertible<__detected_or_t<__nat, __iterator_concept, _Tp>, _Up>;364 365template <class _Tp>366using __has_input_iterator_category _LIBCPP_NODEBUG = __has_iterator_category_convertible_to<_Tp, input_iterator_tag>;367 368template <class _Tp>369using __has_forward_iterator_category _LIBCPP_NODEBUG =370 __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>;371 372template <class _Tp>373using __has_bidirectional_iterator_category _LIBCPP_NODEBUG =374 __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>;375 376template <class _Tp>377using __has_random_access_iterator_category _LIBCPP_NODEBUG =378 __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>;379 380// __libcpp_is_contiguous_iterator determines if an iterator is known by381// libc++ to be contiguous, either because it advertises itself as such382// (in C++20) or because it is a pointer type or a known trivial wrapper383// around a (possibly fancy) pointer type, such as __wrap_iter<T*>.384// Such iterators receive special "contiguous" optimizations in385// std::copy and std::sort.386//387#if _LIBCPP_STD_VER >= 20388template <class _Tp>389struct __libcpp_is_contiguous_iterator390 : _Or< __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>,391 __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag> > {};392#else393template <class _Tp>394struct __libcpp_is_contiguous_iterator : false_type {};395#endif396 397// Any native pointer which is an iterator is also a contiguous iterator.398template <class _Up>399struct __libcpp_is_contiguous_iterator<_Up*> : true_type {};400 401template <class _Iter>402class __wrap_iter;403 404template <class _Tp>405using __has_exactly_input_iterator_category _LIBCPP_NODEBUG =406 integral_constant<bool,407 __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value &&408 !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value>;409 410template <class _Tp>411using __has_exactly_forward_iterator_category _LIBCPP_NODEBUG =412 integral_constant<bool,413 __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value &&414 !__has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value>;415 416template <class _Tp>417using __has_exactly_bidirectional_iterator_category _LIBCPP_NODEBUG =418 integral_constant<bool,419 __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value &&420 !__has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>::value>;421 422template <class _InputIterator>423using __iterator_value_type _LIBCPP_NODEBUG = typename iterator_traits<_InputIterator>::value_type;424 425#if _LIBCPP_STD_VER >= 23426template <class _InputIterator>427using __iter_key_type _LIBCPP_NODEBUG = remove_const_t<tuple_element_t<0, __iterator_value_type<_InputIterator>>>;428 429template <class _InputIterator>430using __iter_mapped_type _LIBCPP_NODEBUG = tuple_element_t<1, __iterator_value_type<_InputIterator>>;431 432template <class _InputIterator>433using __iter_to_alloc_type _LIBCPP_NODEBUG =434 pair<const tuple_element_t<0, __iterator_value_type<_InputIterator>>,435 tuple_element_t<1, __iterator_value_type<_InputIterator>>>;436#else437template <class _InputIterator>438using __iter_key_type _LIBCPP_NODEBUG = __remove_const_t<typename __iterator_value_type<_InputIterator>::first_type>;439 440template <class _InputIterator>441using __iter_mapped_type _LIBCPP_NODEBUG = typename __iterator_value_type<_InputIterator>::second_type;442 443template <class _InputIterator>444using __iter_to_alloc_type _LIBCPP_NODEBUG =445 pair<const typename __iterator_value_type<_InputIterator>::first_type,446 typename __iterator_value_type<_InputIterator>::second_type>;447#endif // _LIBCPP_STD_VER >= 23448 449template <class _Iter>450using __iterator_iterator_category _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::iterator_category;451 452template <class _Iter>453using __iterator_pointer _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::pointer;454 455template <class _Iter>456using __iterator_difference_type _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::difference_type;457 458template <class _Iter>459using __iterator_reference _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::reference;460 461#if _LIBCPP_STD_VER >= 20462 463// [readable.traits]464 465// Let `RI` be `remove_cvref_t<I>`. The type `iter_value_t<I>` denotes466// `indirectly_readable_traits<RI>::value_type` if `iterator_traits<RI>` names a specialization467// generated from the primary template, and `iterator_traits<RI>::value_type` otherwise.468// This has to be in this file and not readable_traits.h to break the include cycle between the two.469template <class _Ip>470using iter_value_t =471 typename conditional_t<__is_primary_template<iterator_traits<remove_cvref_t<_Ip> > >::value,472 indirectly_readable_traits<remove_cvref_t<_Ip> >,473 iterator_traits<remove_cvref_t<_Ip> > >::value_type;474 475#endif // _LIBCPP_STD_VER >= 20476 477_LIBCPP_END_NAMESPACE_STD478 479#endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H480