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