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

source code of flutter_engine/third_party/libcxx/include/__iterator/iterator_traits.h