master
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
51template <class _Tp>
52concept __dereferenceable = requires(_Tp& __t) {
53 { *__t } -> __referenceable; // not required to be equality-preserving
54};
55
56// [iterator.traits]
57template <__dereferenceable _Tp>
58using iter_reference_t = decltype(*std::declval<_Tp&>());
59
60#endif // _LIBCPP_STD_VER >= 20
61
62template <class _Iter>
63struct iterator_traits;
64
65struct input_iterator_tag {};
66struct output_iterator_tag {};
67struct forward_iterator_tag : public input_iterator_tag {};
68struct bidirectional_iterator_tag : public forward_iterator_tag {};
69struct random_access_iterator_tag : public bidirectional_iterator_tag {};
70#if _LIBCPP_STD_VER >= 20
71struct 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.
79namespace __iterator_traits_detail {
80template <class _Ip>
81concept __cpp17_iterator = requires(_Ip __i) {
82 { *__i } -> __referenceable;
83 { ++__i } -> same_as<_Ip&>;
84 { *__i++ } -> __referenceable;
85} && copyable<_Ip>;
86
87template <class _Ip>
88concept __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
96template <class _Ip>
97concept __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> &&
100 requires(_Ip __i) {
101 { __i++ } -> convertible_to<_Ip const&>;
102 { *__i++ } -> same_as<iter_reference_t<_Ip>>;
103 };
104
105template <class _Ip>
106concept __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
112template <class _Ip>
113concept __cpp17_random_access_iterator =
114 __cpp17_bidirectional_iterator<_Ip> && totally_ordered<_Ip> &&
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
126template <class _Ip>
127concept __has_member_reference = requires { typename _Ip::reference; };
128
129template <class _Ip>
130concept __has_member_pointer = requires { typename _Ip::pointer; };
131
132template <class _Ip>
133concept __has_member_iterator_category = requires { typename _Ip::iterator_category; };
134
135template <class _Ip>
136concept __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
143template <class _Tp>
144concept __cpp17_iterator_missing_members = !__specifies_members<_Tp> && __iterator_traits_detail::__cpp17_iterator<_Tp>;
145
146template <class _Tp>
147concept __cpp17_input_iterator_missing_members =
148 __cpp17_iterator_missing_members<_Tp> && __iterator_traits_detail::__cpp17_input_iterator<_Tp>;
149
150// Otherwise, `pointer` names `void`.
151template <class>
152struct __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.
158template <__has_member_pointer _Ip>
159struct __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.
165template <class _Ip>
166 requires requires(_Ip& __i) { __i.operator->(); } && (!__has_member_pointer<_Ip>)
167struct __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>`.
172template <class _Ip>
173struct __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.
179template <__has_member_reference _Ip>
180struct __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
186template <class _Ip>
187struct __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
193template <__iterator_traits_detail::__cpp17_random_access_iterator _Ip>
194struct __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
200template <__iterator_traits_detail::__cpp17_bidirectional_iterator _Ip>
201struct __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
207template <__iterator_traits_detail::__cpp17_forward_iterator _Ip>
208struct __deduce_iterator_category<_Ip> {
209 using type _LIBCPP_NODEBUG = forward_iterator_tag;
210};
211
212template <class _Ip>
213struct __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.
218template <__has_member_iterator_category _Ip>
219struct __iterator_traits_iterator_category<_Ip> {
220 using type _LIBCPP_NODEBUG = typename _Ip::iterator_category;
221};
222
223// otherwise, it names void.
224template <class>
225struct __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;
231template <class _Ip>
232 requires requires { typename incrementable_traits<_Ip>::difference_type; }
233struct __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.
239template <class>
240struct __iterator_traits {};
241
242template <class _Tp>
243using __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:
248template <__specifies_members _Ip>
249struct __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:
260template <__cpp17_input_iterator_missing_members _Ip>
261struct __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:
271template <__cpp17_iterator_missing_members _Ip>
272struct __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
280template <class _Ip>
281struct iterator_traits : __iterator_traits<_Ip> {
282 using __primary_template _LIBCPP_NODEBUG = iterator_traits;
283};
284
285#else // _LIBCPP_STD_VER >= 20
286
287template <class _Iter, bool>
288struct __iterator_traits {};
289
290template <class _Iter, bool>
291struct __iterator_traits_impl {};
292
293template <class _Iter>
294struct __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
302template <class _Iter>
303struct __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
308template <class _Tp>
309struct __has_iterator_typedefs {
310private:
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
321public:
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
330template <class _Iter>
331struct 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
336template <class _Tp>
337#if _LIBCPP_STD_VER >= 20
338 requires is_object_v<_Tp>
339#endif
340struct 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
351template <class _Tp>
352using __iterator_category _LIBCPP_NODEBUG = typename _Tp::iterator_category;
353
354template <class _Tp>
355using __iterator_concept _LIBCPP_NODEBUG = typename _Tp::iterator_concept;
356
357template <class _Tp, class _Up>
358using __has_iterator_category_convertible_to _LIBCPP_NODEBUG =
359 is_convertible<__detected_or_t<__nat, __iterator_category, iterator_traits<_Tp> >, _Up>;
360
361template <class _Tp, class _Up>
362using __has_iterator_concept_convertible_to _LIBCPP_NODEBUG =
363 is_convertible<__detected_or_t<__nat, __iterator_concept, _Tp>, _Up>;
364
365template <class _Tp>
366using __has_input_iterator_category _LIBCPP_NODEBUG = __has_iterator_category_convertible_to<_Tp, input_iterator_tag>;
367
368template <class _Tp>
369using __has_forward_iterator_category _LIBCPP_NODEBUG =
370 __has_iterator_category_convertible_to<_Tp, forward_iterator_tag>;
371
372template <class _Tp>
373using __has_bidirectional_iterator_category _LIBCPP_NODEBUG =
374 __has_iterator_category_convertible_to<_Tp, bidirectional_iterator_tag>;
375
376template <class _Tp>
377using __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
388template <class _Tp>
389struct __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
393template <class _Tp>
394struct __libcpp_is_contiguous_iterator : false_type {};
395#endif
396
397// Any native pointer which is an iterator is also a contiguous iterator.
398template <class _Up>
399struct __libcpp_is_contiguous_iterator<_Up*> : true_type {};
400
401template <class _Iter>
402class __wrap_iter;
403
404template <class _Tp>
405using __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
410template <class _Tp>
411using __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
416template <class _Tp>
417using __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
422template <class _InputIterator>
423using __iter_value_type _LIBCPP_NODEBUG = typename iterator_traits<_InputIterator>::value_type;
424
425#if _LIBCPP_STD_VER >= 23
426template <class _InputIterator>
427using __iter_key_type _LIBCPP_NODEBUG = remove_const_t<tuple_element_t<0, __iter_value_type<_InputIterator>>>;
428
429template <class _InputIterator>
430using __iter_mapped_type _LIBCPP_NODEBUG = tuple_element_t<1, __iter_value_type<_InputIterator>>;
431
432template <class _InputIterator>
433using __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
437template <class _InputIterator>
438using __iter_key_type _LIBCPP_NODEBUG =
439 __remove_const_t<typename iterator_traits<_InputIterator>::value_type::first_type>;
440
441template <class _InputIterator>
442using __iter_mapped_type _LIBCPP_NODEBUG = typename iterator_traits<_InputIterator>::value_type::second_type;
443
444template <class _InputIterator>
445using __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
450template <class _Iter>
451using __iterator_category_type _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::iterator_category;
452
453template <class _Iter>
454using __iterator_pointer_type _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::pointer;
455
456template <class _Iter>
457using __iter_diff_t _LIBCPP_NODEBUG = typename iterator_traits<_Iter>::difference_type;
458
459template <class _Iter>
460using __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.
470template <class _Ip>
471using 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