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> &&
197 totally_ordered<_Ip> &&
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 requires requires(_Ip& __i) { __i.operator->(); } && (!__has_member_pointer<_Ip>)
259 struct __iterator_traits_member_pointer_or_arrow_or_void<_Ip> {
260 using type = decltype(declval<_Ip&>().operator->());
261 };
262
263 // Otherwise, `reference` names `iter-reference-t<I>`.
264 template<class _Ip>
265 struct __iterator_traits_member_reference { using type = iter_reference_t<_Ip>; };
266
267 // [iterator.traits]/3.2.2
268 // If the qualified-id `I::reference` is valid and denotes a type, `reference` names that type.
269 template<__has_member_reference _Ip>
270 struct __iterator_traits_member_reference<_Ip> { using type = typename _Ip::reference; };
271
272 // [iterator.traits]/3.2.3.4
273 // input_iterator_tag
274 template<class _Ip>
275 struct __deduce_iterator_category {
276 using type = input_iterator_tag;
277 };
278
279 // [iterator.traits]/3.2.3.1
280 // `random_access_iterator_tag` if `I` satisfies `cpp17-random-access-iterator`, or otherwise
281 template<__iterator_traits_detail::__cpp17_random_access_iterator _Ip>
282 struct __deduce_iterator_category<_Ip> {
283 using type = random_access_iterator_tag;
284 };
285
286 // [iterator.traits]/3.2.3.2
287 // `bidirectional_iterator_tag` if `I` satisfies `cpp17-bidirectional-iterator`, or otherwise
288 template<__iterator_traits_detail::__cpp17_bidirectional_iterator _Ip>
289 struct __deduce_iterator_category<_Ip> {
290 using type = bidirectional_iterator_tag;
291 };
292
293 // [iterator.traits]/3.2.3.3
294 // `forward_iterator_tag` if `I` satisfies `cpp17-forward-iterator`, or otherwise
295 template<__iterator_traits_detail::__cpp17_forward_iterator _Ip>
296 struct __deduce_iterator_category<_Ip> {
297 using type = forward_iterator_tag;
298 };
299
300 template<class _Ip>
301 struct __iterator_traits_iterator_category : __deduce_iterator_category<_Ip> {};
302
303 // [iterator.traits]/3.2.3
304 // If the qualified-id `I::iterator-category` is valid and denotes a type, `iterator-category` names
305 // that type.
306 template<__has_member_iterator_category _Ip>
307 struct __iterator_traits_iterator_category<_Ip> {
308 using type = typename _Ip::iterator_category;
309 };
310
311 // otherwise, it names void.
312 template<class>
313 struct __iterator_traits_difference_type { using type = void; };
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 // !defined(_LIBCPP_HAS_NO_RANGES)
369
370 template <class _Iter, bool> struct __iterator_traits {};
371
372 template <class _Iter, bool> struct __iterator_traits_impl {};
373
374 template <class _Iter>
375 struct __iterator_traits_impl<_Iter, true>
376 {
377 typedef typename _Iter::difference_type difference_type;
378 typedef typename _Iter::value_type value_type;
379 typedef typename _Iter::pointer pointer;
380 typedef typename _Iter::reference reference;
381 typedef typename _Iter::iterator_category iterator_category;
382 };
383
384 template <class _Iter>
385 struct __iterator_traits<_Iter, true>
386 : __iterator_traits_impl
387 <
388 _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 {};
393
394 // iterator_traits<Iterator> will only have the nested types if Iterator::iterator_category
395 // exists. Else iterator_traits<Iterator> will be an empty class. This is a
396 // conforming extension which allows some programs to compile and behave as
397 // the client expects instead of failing at compile time.
398
399 template <class _Iter>
400 struct _LIBCPP_TEMPLATE_VIS iterator_traits
401 : __iterator_traits<_Iter, __has_iterator_typedefs<_Iter>::value> {
402
403 using __primary_template = iterator_traits;
404 };
405 #endif // !defined(_LIBCPP_HAS_NO_RANGES)
406
407 template<class _Tp>
408 #if !defined(_LIBCPP_HAS_NO_RANGES)
409 requires is_object_v<_Tp>
410 #endif
411 struct _LIBCPP_TEMPLATE_VIS iterator_traits<_Tp*>
412 {
413 typedef ptrdiff_t difference_type;
414 typedef typename remove_cv<_Tp>::type value_type;
415 typedef _Tp* pointer;
416 typedef _Tp& reference;
417 typedef random_access_iterator_tag iterator_category;
418 #if _LIBCPP_STD_VER > 17
419 typedef contiguous_iterator_tag iterator_concept;
420 #endif
421 };
422
423 template <class _Tp, class _Up, bool = __has_iterator_category<iterator_traits<_Tp> >::value>
424 struct __has_iterator_category_convertible_to
425 : is_convertible<typename iterator_traits<_Tp>::iterator_category, _Up>
426 {};
427
428 template <class _Tp, class _Up>
429 struct __has_iterator_category_convertible_to<_Tp, _Up, false> : false_type {};
430
431 template <class _Tp, class _Up, bool = __has_iterator_concept<_Tp>::value>
432 struct __has_iterator_concept_convertible_to
433 : is_convertible<typename _Tp::iterator_concept, _Up>
434 {};
435
436 template <class _Tp, class _Up>
437 struct __has_iterator_concept_convertible_to<_Tp, _Up, false> : false_type {};
438
439 template <class _Tp>
440 struct __is_cpp17_input_iterator : public __has_iterator_category_convertible_to<_Tp, input_iterator_tag> {};
441
442 template <class _Tp>
443 struct __is_cpp17_forward_iterator : public __has_iterator_category_convertible_to<_Tp, forward_iterator_tag> {};
444
445 template <class _Tp>
446 struct __is_cpp17_bidirectional_iterator : public __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag> {};
447
448 template <class _Tp>
449 struct __is_cpp17_random_access_iterator : public __has_iterator_category_convertible_to<_Tp, random_access_iterator_tag> {};
450
451 // __is_cpp17_contiguous_iterator determines if an iterator is known by
452 // libc++ to be contiguous, either because it advertises itself as such
453 // (in C++20) or because it is a pointer type or a known trivial wrapper
454 // around a (possibly fancy) pointer type, such as __wrap_iter<T*>.
455 // Such iterators receive special "contiguous" optimizations in
456 // std::copy and std::sort.
457 //
458 #if _LIBCPP_STD_VER > 17
459 template <class _Tp>
460 struct __is_cpp17_contiguous_iterator : _Or<
461 __has_iterator_category_convertible_to<_Tp, contiguous_iterator_tag>,
462 __has_iterator_concept_convertible_to<_Tp, contiguous_iterator_tag>
463 > {};
464 #else
465 template <class _Tp>
466 struct __is_cpp17_contiguous_iterator : false_type {};
467 #endif
468
469 // Any native pointer which is an iterator is also a contiguous iterator.
470 template <class _Up>
471 struct __is_cpp17_contiguous_iterator<_Up*> : true_type {};
472
473
474 template <class _Tp>
475 struct __is_exactly_cpp17_input_iterator
476 : public integral_constant<bool,
477 __has_iterator_category_convertible_to<_Tp, input_iterator_tag>::value &&
478 !__has_iterator_category_convertible_to<_Tp, forward_iterator_tag>::value> {};
479
480 #ifndef _LIBCPP_HAS_NO_DEDUCTION_GUIDES
481 template<class _InputIterator>
482 using __iter_value_type = typename iterator_traits<_InputIterator>::value_type;
483
484 template<class _InputIterator>
485 using __iter_key_type = remove_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>;
486
487 template<class _InputIterator>
488 using __iter_mapped_type = typename iterator_traits<_InputIterator>::value_type::second_type;
489
490 template<class _InputIterator>
491 using __iter_to_alloc_type = pair<
492 add_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>,
493 typename iterator_traits<_InputIterator>::value_type::second_type>;
494 #endif // _LIBCPP_HAS_NO_DEDUCTION_GUIDES
495
496 _LIBCPP_END_NAMESPACE_STD
497
498 _LIBCPP_POP_MACROS
499
500 #endif // _LIBCPP___ITERATOR_ITERATOR_TRAITS_H
501