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