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