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-exception
7 //
8 //===----------------------------------------------------------------------===//
9
10 #ifndef _LIBCPP___ITERATOR_ITERATOR_TRAITS_H
11 #define _LIBCPP___ITERATOR_ITERATOR_TRAITS_H
12
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 <__fwd/pair.h>
22 #include <__iterator/incrementable_traits.h>
23 #include <__iterator/readable_traits.h>
24 #include <__type_traits/common_reference.h>
25 #include <__type_traits/conditional.h>
26 #include <__type_traits/disjunction.h>
27 #include <__type_traits/is_convertible.h>
28 #include <__type_traits/is_object.h>
29 #include <__type_traits/is_primary_template.h>
30 #include <__type_traits/is_reference.h>
31 #include <__type_traits/is_valid_expansion.h>
32 #include <__type_traits/remove_const.h>
33 #include <__type_traits/remove_cv.h>
34 #include <__type_traits/remove_cvref.h>
35 #include <__type_traits/void_t.h>
36 #include <__utility/declval.h>
37 #include <cstddef>
38
39 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
40 # pragma GCC system_header
41 #endif
42
43 _LIBCPP_BEGIN_NAMESPACE_STD
44
45 #if _LIBCPP_STD_VER >= 20
46
47 template <class _Tp>
48 using __with_reference = _Tp&;
49
50 template <class _Tp>
51 concept __can_reference = requires { typename __with_reference<_Tp>; };
52
53 template <class _Tp>
requires(_Tp & __t)54 concept __dereferenceable = requires(_Tp& __t) {
55 { *__t } -> __can_reference; // not required to be equality-preserving
56 };
57
58 // [iterator.traits]
59 template <__dereferenceable _Tp>
60 using iter_reference_t = decltype(*std::declval<_Tp&>());
61
62 #endif // _LIBCPP_STD_VER >= 20
63
64 template <class _Iter>
65 struct _LIBCPP_TEMPLATE_VIS iterator_traits;
66
67 struct _LIBCPP_TEMPLATE_VIS input_iterator_tag {};
68 struct _LIBCPP_TEMPLATE_VIS output_iterator_tag {};
69 struct _LIBCPP_TEMPLATE_VIS forward_iterator_tag : public input_iterator_tag {};
70 struct _LIBCPP_TEMPLATE_VIS bidirectional_iterator_tag : public forward_iterator_tag {};
71 struct _LIBCPP_TEMPLATE_VIS random_access_iterator_tag : public bidirectional_iterator_tag {};
72 #if _LIBCPP_STD_VER >= 20
73 struct _LIBCPP_TEMPLATE_VIS contiguous_iterator_tag : public random_access_iterator_tag {};
74 #endif
75
76 template <class _Iter>
77 struct __iter_traits_cache {
78 using type = _If< __is_primary_template<iterator_traits<_Iter> >::value, _Iter, iterator_traits<_Iter> >;
79 };
80 template <class _Iter>
81 using _ITER_TRAITS = typename __iter_traits_cache<_Iter>::type;
82
83 struct __iter_concept_concept_test {
84 template <class _Iter>
85 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_concept;
86 };
87 struct __iter_concept_category_test {
88 template <class _Iter>
89 using _Apply = typename _ITER_TRAITS<_Iter>::iterator_category;
90 };
91 struct __iter_concept_random_fallback {
92 template <class _Iter>
93 using _Apply = __enable_if_t< __is_primary_template<iterator_traits<_Iter> >::value, random_access_iterator_tag >;
94 };
95
96 template <class _Iter, class _Tester>
97 struct __test_iter_concept : _IsValidExpansion<_Tester::template _Apply, _Iter>, _Tester {};
98
99 template <class _Iter>
100 struct __iter_concept_cache {
101 using type = _Or< __test_iter_concept<_Iter, __iter_concept_concept_test>,
102 __test_iter_concept<_Iter, __iter_concept_category_test>,
103 __test_iter_concept<_Iter, __iter_concept_random_fallback> >;
104 };
105
106 template <class _Iter>
107 using _ITER_CONCEPT = typename __iter_concept_cache<_Iter>::type::template _Apply<_Iter>;
108
109 template <class _Tp>
110 struct __has_iterator_typedefs {
111 private:
112 template <class _Up>
113 static false_type __test(...);
114 template <class _Up>
115 static true_type
116 __test(__void_t<typename _Up::iterator_category>* = nullptr,
117 __void_t<typename _Up::difference_type>* = nullptr,
118 __void_t<typename _Up::value_type>* = nullptr,
119 __void_t<typename _Up::reference>* = nullptr,
120 __void_t<typename _Up::pointer>* = nullptr);
121
122 public:
123 static const bool value = decltype(__test<_Tp>(nullptr, nullptr, nullptr, nullptr, nullptr))::value;
124 };
125
126 template <class _Tp>
127 struct __has_iterator_category {
128 private:
129 template <class _Up>
130 static false_type __test(...);
131 template <class _Up>
132 static true_type __test(typename _Up::iterator_category* = nullptr);
133
134 public:
135 static const bool value = decltype(__test<_Tp>(nullptr))::value;
136 };
137
138 template <class _Tp>
139 struct __has_iterator_concept {
140 private:
141 template <class _Up>
142 static false_type __test(...);
143 template <class _Up>
144 static true_type __test(typename _Up::iterator_concept* = nullptr);
145
146 public:
147 static const bool value = decltype(__test<_Tp>(nullptr))::value;
148 };
149
150 #if _LIBCPP_STD_VER >= 20
151
152 // The `cpp17-*-iterator` exposition-only concepts have very similar names to the `Cpp17*Iterator` named requirements
153 // from `[iterator.cpp17]`. To avoid confusion between the two, the exposition-only concepts have been banished to
154 // a "detail" namespace indicating they have a niche use-case.
155 namespace __iterator_traits_detail {
156 template <class _Ip>
requires(_Ip __i)157 concept __cpp17_iterator = requires(_Ip __i) {
158 { *__i } -> __can_reference;
159 { ++__i } -> same_as<_Ip&>;
160 { *__i++ } -> __can_reference;
161 } && copyable<_Ip>;
162
163 template <class _Ip>
requires(_Ip __i)164 concept __cpp17_input_iterator = __cpp17_iterator<_Ip> && equality_comparable<_Ip> && requires(_Ip __i) {
165 typename incrementable_traits<_Ip>::difference_type;
166 typename indirectly_readable_traits<_Ip>::value_type;
167 typename common_reference_t<iter_reference_t<_Ip>&&, typename indirectly_readable_traits<_Ip>::value_type&>;
168 typename common_reference_t<decltype(*__i++)&&, typename indirectly_readable_traits<_Ip>::value_type&>;
169 requires signed_integral<typename incrementable_traits<_Ip>::difference_type>;
170 };
171
172 template <class _Ip>
173 concept __cpp17_forward_iterator =
174 __cpp17_input_iterator<_Ip> && constructible_from<_Ip> && is_reference_v<iter_reference_t<_Ip>> &&
175 same_as<remove_cvref_t<iter_reference_t<_Ip>>, typename indirectly_readable_traits<_Ip>::value_type> &&
requires(_Ip __i)176 requires(_Ip __i) {
177 { __i++ } -> convertible_to<_Ip const&>;
178 { *__i++ } -> same_as<iter_reference_t<_Ip>>;
179 };
180
181 template <class _Ip>
requires(_Ip __i)182 concept __cpp17_bidirectional_iterator = __cpp17_forward_iterator<_Ip> && requires(_Ip __i) {
183 { --__i } -> same_as<_Ip&>;
184 { __i-- } -> convertible_to<_Ip const&>;
185 { *__i-- } -> same_as<iter_reference_t<_Ip>>;
186 };
187
188 template <class _Ip>
189 concept __cpp17_random_access_iterator =
190 __cpp17_bidirectional_iterator<_Ip> && totally_ordered<_Ip> &&
requires(_Ip __i,typename incrementable_traits<_Ip>::difference_type __n)191 requires(_Ip __i, typename incrementable_traits<_Ip>::difference_type __n) {
192 { __i += __n } -> same_as<_Ip&>;
193 { __i -= __n } -> same_as<_Ip&>;
194 { __i + __n } -> same_as<_Ip>;
195 { __n + __i } -> same_as<_Ip>;
196 { __i - __n } -> same_as<_Ip>;
197 { __i - __i } -> same_as<decltype(__n)>; // NOLINT(misc-redundant-expression) ; This is llvm.org/PR54114
198 { __i[__n] } -> convertible_to<iter_reference_t<_Ip>>;
199 };
200 } // namespace __iterator_traits_detail
201
202 template <class _Ip>
203 concept __has_member_reference = requires { typename _Ip::reference; };
204
205 template <class _Ip>
206 concept __has_member_pointer = requires { typename _Ip::pointer; };
207
208 template <class _Ip>
209 concept __has_member_iterator_category = requires { typename _Ip::iterator_category; };
210
211 template <class _Ip>
212 concept __specifies_members = requires {
213 typename _Ip::value_type;
214 typename _Ip::difference_type;
215 requires __has_member_reference<_Ip>;
216 requires __has_member_iterator_category<_Ip>;
217 };
218
219 template <class>
220 struct __iterator_traits_member_pointer_or_void {
221 using type = void;
222 };
223
224 template <__has_member_pointer _Tp>
225 struct __iterator_traits_member_pointer_or_void<_Tp> {
226 using type = typename _Tp::pointer;
227 };
228
229 template <class _Tp>
230 concept __cpp17_iterator_missing_members = !__specifies_members<_Tp> && __iterator_traits_detail::__cpp17_iterator<_Tp>;
231
232 template <class _Tp>
233 concept __cpp17_input_iterator_missing_members =
234 __cpp17_iterator_missing_members<_Tp> && __iterator_traits_detail::__cpp17_input_iterator<_Tp>;
235
236 // Otherwise, `pointer` names `void`.
237 template <class>
238 struct __iterator_traits_member_pointer_or_arrow_or_void {
239 using type = void;
240 };
241
242 // [iterator.traits]/3.2.1
243 // If the qualified-id `I::pointer` is valid and denotes a type, `pointer` names that type.
244 template <__has_member_pointer _Ip>
245 struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> {
246 using type = typename _Ip::pointer;
247 };
248
249 // Otherwise, if `decltype(declval<I&>().operator->())` is well-formed, then `pointer` names that
250 // type.
251 template <class _Ip>
252 requires requires(_Ip& __i) { __i.operator->(); } && (!__has_member_pointer<_Ip>)
253 struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> {
254 using type = decltype(std::declval<_Ip&>().operator->());
255 };
256
257 // Otherwise, `reference` names `iter-reference-t<I>`.
258 template <class _Ip>
259 struct __iterator_traits_member_reference {
260 using type = iter_reference_t<_Ip>;
261 };
262
263 // [iterator.traits]/3.2.2
264 // If the qualified-id `I::reference` is valid and denotes a type, `reference` names that type.
265 template <__has_member_reference _Ip>
266 struct __iterator_traits_member_reference<_Ip> {
267 using type = typename _Ip::reference;
268 };
269
270 // [iterator.traits]/3.2.3.4
271 // input_iterator_tag
272 template <class _Ip>
273 struct __deduce_iterator_category {
274 using type = input_iterator_tag;
275 };
276
277 // [iterator.traits]/3.2.3.1
278 // `random_access_iterator_tag` if `I` satisfies `cpp17-random-access-iterator`, or otherwise
279 template <__iterator_traits_detail::__cpp17_random_access_iterator _Ip>
280 struct __deduce_iterator_category<_Ip> {
281 using type = random_access_iterator_tag;
282 };
283
284 // [iterator.traits]/3.2.3.2
285 // `bidirectional_iterator_tag` if `I` satisfies `cpp17-bidirectional-iterator`, or otherwise
286 template <__iterator_traits_detail::__cpp17_bidirectional_iterator _Ip>
287 struct __deduce_iterator_category<_Ip> {
288 using type = bidirectional_iterator_tag;
289 };
290
291 // [iterator.traits]/3.2.3.3
292 // `forward_iterator_tag` if `I` satisfies `cpp17-forward-iterator`, or otherwise
293 template <__iterator_traits_detail::__cpp17_forward_iterator _Ip>
294 struct __deduce_iterator_category<_Ip> {
295 using type = forward_iterator_tag;
296 };
297
298 template <class _Ip>
299 struct __iterator_traits_iterator_category : __deduce_iterator_category<_Ip> {};
300
301 // [iterator.traits]/3.2.3
302 // If the qualified-id `I::iterator-category` is valid and denotes a type, `iterator-category` names
303 // that type.
304 template <__has_member_iterator_category _Ip>
305 struct __iterator_traits_iterator_category<_Ip> {
306 using type = typename _Ip::iterator_category;
307 };
308
309 // otherwise, it names void.
310 template <class>
311 struct __iterator_traits_difference_type {
312 using type = void;
313 };
314
315 // If the qualified-id `incrementable_traits<I>::difference_type` is valid and denotes a type, then
316 // `difference_type` names that type;
317 template <class _Ip>
318 requires requires { typename incrementable_traits<_Ip>::difference_type; }
319 struct __iterator_traits_difference_type<_Ip> {
320 using type = typename incrementable_traits<_Ip>::difference_type;
321 };
322
323 // [iterator.traits]/3.4
324 // Otherwise, `iterator_traits<I>` has no members by any of the above names.
325 template <class>
326 struct __iterator_traits {};
327
328 // [iterator.traits]/3.1
329 // If `I` has valid ([temp.deduct]) member types `difference-type`, `value-type`, `reference`, and
330 // `iterator-category`, then `iterator-traits<I>` has the following publicly accessible members:
331 template <__specifies_members _Ip>
332 struct __iterator_traits<_Ip> {
333 using iterator_category = typename _Ip::iterator_category;
334 using value_type = typename _Ip::value_type;
335 using difference_type = typename _Ip::difference_type;
336 using pointer = typename __iterator_traits_member_pointer_or_void<_Ip>::type;
337 using reference = typename _Ip::reference;
338 };
339
340 // [iterator.traits]/3.2
341 // Otherwise, if `I` satisfies the exposition-only concept `cpp17-input-iterator`,
342 // `iterator-traits<I>` has the following publicly accessible members:
343 template <__cpp17_input_iterator_missing_members _Ip>
344 struct __iterator_traits<_Ip> {
345 using iterator_category = typename __iterator_traits_iterator_category<_Ip>::type;
346 using value_type = typename indirectly_readable_traits<_Ip>::value_type;
347 using difference_type = typename incrementable_traits<_Ip>::difference_type;
348 using pointer = typename __iterator_traits_member_pointer_or_arrow_or_void<_Ip>::type;
349 using reference = typename __iterator_traits_member_reference<_Ip>::type;
350 };
351
352 // Otherwise, if `I` satisfies the exposition-only concept `cpp17-iterator`, then
353 // `iterator_traits<I>` has the following publicly accessible members:
354 template <__cpp17_iterator_missing_members _Ip>
355 struct __iterator_traits<_Ip> {
356 using iterator_category = output_iterator_tag;
357 using value_type = void;
358 using difference_type = typename __iterator_traits_difference_type<_Ip>::type;
359 using pointer = void;
360 using reference = void;
361 };
362
363 template <class _Ip>
364 struct iterator_traits : __iterator_traits<_Ip> {
365 using __primary_template = iterator_traits;
366 };
367
368 #else // _LIBCPP_STD_VER >= 20
369
370 template <class _Iter, bool>
371 struct __iterator_traits {};
372
373 template <class _Iter, bool>
374 struct __iterator_traits_impl {};
375
376 template <class _Iter>
377 struct __iterator_traits_impl<_Iter, true> {
378 typedef typename _Iter::difference_type difference_type;
379 typedef typename _Iter::value_type value_type;
380 typedef typename _Iter::pointer pointer;
381 typedef typename _Iter::reference reference;
382 typedef typename _Iter::iterator_category iterator_category;
383 };
384
385 template <class _Iter>
386 struct __iterator_traits<_Iter, true>
387 : __iterator_traits_impl< _Iter,
388 is_convertible<typename _Iter::iterator_category, input_iterator_tag>::value ||
389 is_convertible<typename _Iter::iterator_category, output_iterator_tag>::value > {};
390
391 // iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category
392 // exists. Else iterator_traits<Iterator> will be an empty class. This is a
393 // conforming extension which allows some programs to compile and behave as
394 // the client expects instead of failing at compile time.
395
396 template <class _Iter>
397 struct _LIBCPP_TEMPLATE_VIS iterator_traits : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> {
398 using __primary_template = iterator_traits;
399 };
400 #endif // _LIBCPP_STD_VER >= 20
401
402 template <class _Tp>
403 #if _LIBCPP_STD_VER >= 20
404 requires is_object_v<_Tp>
405 #endif
406 struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*> {
407 typedef ptrdiff_t difference_type;
408 typedef __remove_cv_t<_Tp> value_type;
409 typedef _Tp* pointer;
410 typedef _Tp& reference;
411 typedef random_access_iterator_tag iterator_category;
412 #if _LIBCPP_STD_VER >= 20
413 typedef contiguous_iterator_tag iterator_concept;
414 #endif
415 };
416
417 template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value>
418 struct __has_iterator_category_convertible_to : is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up> {
419 };
420
421 template <class _Tp, class _Up>
422 struct __has_iterator_category_convertible_to<_Tp, _Up, false> : false_type {};
423
424 template <class _Tp, class _Up, bool = __has_iterator_concept<_Tp>::value>
425 struct __has_iterator_concept_convertible_to : is_convertible<typename _Tp::iterator_concept, _Up> {};
426
427 template <class _Tp, class _Up>
428 struct __has_iterator_concept_convertible_to<_Tp, _Up, false> : false_type {};
429
430 template <class _Tp>
431 using __has_input_iterator_category = __has_iterator_category_convertible_to<_Tp, input_iterator_tag>;
432
433 template <class _Tp>
434 using __has_forward_iterator_category = __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>;
435
436 template <class _Tp>
437 using __has_bidirectional_iterator_category = __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>;
438
439 template <class _Tp>
440 using __has_random_access_iterator_category = __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>;
441
442 // __libcpp_is_contiguous_iterator determines if an iterator is known by
443 // libc++ to be contiguous, either because it advertises itself as such
444 // (in C++20) or because it is a pointer type or a known trivial wrapper
445 // around a (possibly fancy) pointer type, such as __wrap_iter<T*>.
446 // Such iterators receive special "contiguous" optimizations in
447 // std::copy and std::sort.
448 //
449 #if _LIBCPP_STD_VER >= 20
450 template <class _Tp>
451 struct __libcpp_is_contiguous_iterator
452 : _Or< __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>,
453 __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag> > {};
454 #else
455 template <class _Tp>
456 struct __libcpp_is_contiguous_iterator : false_type {};
457 #endif
458
459 // Any native pointer which is an iterator is also a contiguous iterator.
460 template <class _Up>
461 struct __libcpp_is_contiguous_iterator<_Up*> : true_type {};
462
463 template <class _Iter>
464 class __wrap_iter;
465
466 template <class _Tp>
467 using __has_exactly_input_iterator_category =
468 integral_constant<bool,
469 __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value &&
470 !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value>;
471
472 template <class _Tp>
473 using __has_exactly_forward_iterator_category =
474 integral_constant<bool,
475 __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value &&
476 !__has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value>;
477
478 template <class _Tp>
479 using __has_exactly_bidirectional_iterator_category =
480 integral_constant<bool,
481 __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>::value &&
482 !__has_iterator_category_convertible_to<_Tp, random_access_iterator_tag>::value>;
483
484 template <class _InputIterator>
485 using __iter_value_type = typename iterator_traits<_InputIterator>::value_type;
486
487 template <class _InputIterator>
488 using __iter_key_type = __remove_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>;
489
490 template <class _InputIterator>
491 using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type;
492
493 template <class _InputIterator>
494 using __iter_to_alloc_type =
495 pair<const typename iterator_traits<_InputIterator>::value_type::first_type,
496 typename iterator_traits<_InputIterator>::value_type::second_type>;
497
498 template <class _Iter>
499 using __iterator_category_type = typename iterator_traits<_Iter>::iterator_category;
500
501 template <class _Iter>
502 using __iterator_pointer_type = typename iterator_traits<_Iter>::pointer;
503
504 template <class _Iter>
505 using __iter_diff_t = typename iterator_traits<_Iter>::difference_type;
506
507 template <class _Iter>
508 using __iter_reference = typename iterator_traits<_Iter>::reference;
509
510 #if _LIBCPP_STD_VER >= 20
511
512 // [readable.traits]
513
514 // Let `RI` be `remove_cvref_t<I>`. The type `iter_value_t<I>` denotes
515 // `indirectly_readable_traits<RI>::value_type` if `iterator_traits<RI>` names a specialization
516 // generated from the primary template, and `iterator_traits<RI>::value_type` otherwise.
517 // This has to be in this file and not readable_traits.h to break the include cycle between the two.
518 template <class _Ip>
519 using iter_value_t =
520 typename conditional_t<__is_primary_template<iterator_traits<remove_cvref_t<_Ip> > >::value,
521 indirectly_readable_traits<remove_cvref_t<_Ip> >,
522 iterator_traits<remove_cvref_t<_Ip> > >::value_type;
523
524 #endif // _LIBCPP_STD_VER >= 20
525
526 _LIBCPP_END_NAMESPACE_STD
527
528 #endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H
529