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