1 //===----------------------------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 // UNSUPPORTED: c++03, c++11, c++14, c++17
10 
11 // This test uses iterator types from std::filesystem, which were introduced in macOS 10.15.
12 // XFAIL: use_system_cxx_lib && target={{.+}}-apple-macosx10.{{9|10|11|12|13|14}}
13 
14 // template<class T>
15 // struct iterator_traits;
16 
17 #include <iterator>
18 
19 #include <array>
20 #include <concepts>
21 #include <cstddef>
22 #include <deque>
23 #include <forward_list>
24 #include <list>
25 #include <map>
26 #include <memory>
27 #include <optional>
28 #include <set>
29 #include <string>
30 #include <string_view>
31 #include <unordered_map>
32 #include <unordered_set>
33 #include <vector>
34 
35 #include "test_macros.h"
36 
37 #ifndef TEST_HAS_NO_LOCALIZATION
38 #  include <regex>
39 #  include <ostream>
40 #  include <istream>
41 #endif
42 
43 #ifndef TEST_HAS_NO_FILESYSTEM_LIBRARY
44 #  include <filesystem>
45 #endif
46 
47 #include "test_iterators.h"
48 #include "iterator_traits_cpp17_iterators.h"
49 
50 template <class Traits>
51 constexpr bool has_iterator_concept_v = requires {
52   typename Traits::iterator_concept;
53 };
54 
55 template <class Iter, class Category, class ValueType, class DiffType, class RefType, class PtrType>
test()56 constexpr bool test() {
57   using Traits = std::iterator_traits<Iter>;
58   static_assert(std::same_as<typename Traits::iterator_category, Category>);
59   static_assert(std::same_as<typename Traits::value_type, ValueType>);
60   static_assert(std::same_as<typename Traits::difference_type, DiffType>);
61   static_assert(std::same_as<typename Traits::reference, RefType>);
62   static_assert(std::same_as<typename Traits::pointer, PtrType>);
63   if constexpr (std::is_pointer_v<Iter>) {
64     static_assert(std::same_as<typename Traits::iterator_concept, std::contiguous_iterator_tag>);
65   } else {
66     static_assert(!has_iterator_concept_v<Traits>);
67   }
68 
69   return true;
70 }
71 
72 template <class Iter, class Category>
testIOIterator()73 constexpr bool testIOIterator() {
74   return test<Iter, Category, void, std::ptrdiff_t, void, void>();
75 }
76 
77 template <class Iter, class Category, class ValueType>
testConst()78 constexpr bool testConst() {
79   return test<Iter, Category, ValueType, std::ptrdiff_t, const ValueType&, const ValueType*>();
80 }
81 
82 template <class Iter, class Category, class ValueType>
testMutable()83 constexpr bool testMutable() {
84   return test<Iter, Category, ValueType, std::ptrdiff_t, ValueType&, ValueType*>();
85 }
86 
87 // Standard types.
88 
89 // The Standard does not specify whether iterator_traits<It>::iterator_concept
90 // exists for any particular non-pointer type, we assume it is present
91 // only for pointers.
92 //
93 static_assert(testMutable<std::array<int, 10>::iterator, std::random_access_iterator_tag, int>());
94 static_assert(testConst<std::array<int, 10>::const_iterator, std::random_access_iterator_tag, int>());
95 static_assert(testMutable<std::string::iterator, std::random_access_iterator_tag, char>());
96 static_assert(testConst<std::string::const_iterator, std::random_access_iterator_tag, char>());
97 static_assert(testConst<std::string_view::iterator, std::random_access_iterator_tag, char>());
98 static_assert(testConst<std::string_view::const_iterator, std::random_access_iterator_tag, char>());
99 static_assert(testMutable<std::vector<int>::iterator, std::random_access_iterator_tag, int>());
100 static_assert(testConst<std::vector<int>::const_iterator, std::random_access_iterator_tag, int>());
101 
102 static_assert(testMutable<std::deque<int>::iterator, std::random_access_iterator_tag, int>());
103 static_assert(testConst<std::deque<int>::const_iterator, std::random_access_iterator_tag, int>());
104 static_assert(testMutable<std::forward_list<int>::iterator, std::forward_iterator_tag, int>());
105 static_assert(testConst<std::forward_list<int>::const_iterator, std::forward_iterator_tag, int>());
106 static_assert(testMutable<std::list<int>::iterator, std::bidirectional_iterator_tag, int>());
107 static_assert(testConst<std::list<int>::const_iterator, std::bidirectional_iterator_tag, int>());
108 
109 static_assert(testMutable<std::map<int, int>::iterator, std::bidirectional_iterator_tag, std::pair<const int, int>>());
110 static_assert(testConst<std::map<int, int>::const_iterator, std::bidirectional_iterator_tag, std::pair<const int, int>>());
111 static_assert(testMutable<std::multimap<int, int>::iterator, std::bidirectional_iterator_tag, std::pair<const int, int>>());
112 static_assert(testConst<std::multimap<int, int>::const_iterator, std::bidirectional_iterator_tag, std::pair<const int, int>>());
113 
114 static_assert(testConst<std::set<int>::iterator, std::bidirectional_iterator_tag, int>());
115 static_assert(testConst<std::set<int>::const_iterator, std::bidirectional_iterator_tag, int>());
116 static_assert(testConst<std::multiset<int>::iterator, std::bidirectional_iterator_tag, int>());
117 static_assert(testConst<std::multiset<int>::const_iterator, std::bidirectional_iterator_tag, int>());
118 
119 #ifdef _MSVC_STL_VERSION
120 using unordered_iterator_category = std::bidirectional_iterator_tag;
121 #else // ^^^ MSVC STL / other vvv
122 using unordered_iterator_category = std::forward_iterator_tag;
123 #endif // _MSVC_STL_VERSION
124 
125 static_assert(testMutable<std::unordered_map<int, int>::iterator, unordered_iterator_category, std::pair<const int, int>>());
126 static_assert(testConst<std::unordered_map<int, int>::const_iterator, unordered_iterator_category, std::pair<const int, int>>());
127 static_assert(testMutable<std::unordered_map<int, int>::local_iterator, unordered_iterator_category, std::pair<const int, int>>());
128 static_assert(testConst<std::unordered_map<int, int>::const_local_iterator, unordered_iterator_category, std::pair<const int, int>>());
129 static_assert(testMutable<std::unordered_multimap<int, int>::iterator, unordered_iterator_category, std::pair<const int, int>>());
130 static_assert(testConst<std::unordered_multimap<int, int>::const_iterator, unordered_iterator_category, std::pair<const int, int>>());
131 static_assert(testMutable<std::unordered_multimap<int, int>::local_iterator, unordered_iterator_category, std::pair<const int, int>>());
132 static_assert(testConst<std::unordered_multimap<int, int>::const_local_iterator, unordered_iterator_category, std::pair<const int, int>>());
133 
134 static_assert(testConst<std::unordered_set<int>::iterator, unordered_iterator_category, int>());
135 static_assert(testConst<std::unordered_set<int>::const_iterator, unordered_iterator_category, int>());
136 static_assert(testConst<std::unordered_set<int>::local_iterator, unordered_iterator_category, int>());
137 static_assert(testConst<std::unordered_set<int>::const_local_iterator, unordered_iterator_category, int>());
138 static_assert(testConst<std::unordered_multiset<int>::iterator, unordered_iterator_category, int>());
139 static_assert(testConst<std::unordered_multiset<int>::const_iterator, unordered_iterator_category, int>());
140 static_assert(testConst<std::unordered_multiset<int>::local_iterator, unordered_iterator_category, int>());
141 static_assert(testConst<std::unordered_multiset<int>::const_local_iterator, unordered_iterator_category, int>());
142 
143 static_assert(testMutable<std::reverse_iterator<int*>, std::random_access_iterator_tag, int>());
144 static_assert(testIOIterator<std::back_insert_iterator<std::vector<int>>, std::output_iterator_tag>());
145 static_assert(testIOIterator<std::front_insert_iterator<std::vector<int>>, std::output_iterator_tag>());
146 static_assert(testIOIterator<std::insert_iterator<std::vector<int>>, std::output_iterator_tag>());
147 static_assert(testConst<std::istream_iterator<int, char>, std::input_iterator_tag, int>());
148 
149 #if !defined(TEST_HAS_NO_LOCALIZATION)
150 // libc++-specific since pointer type is unspecified:
151 LIBCPP_STATIC_ASSERT(test<std::istreambuf_iterator<char>, std::input_iterator_tag, char, long long, char, char*>());
152 static_assert(test<std::move_iterator<int*>, std::random_access_iterator_tag, int, std::ptrdiff_t, int&&, int*>());
153 static_assert(testIOIterator<std::ostream_iterator<int, char>, std::output_iterator_tag>());
154 static_assert(testIOIterator<std::ostreambuf_iterator<int, char>, std::output_iterator_tag>());
155 static_assert(testConst<std::cregex_iterator, std::forward_iterator_tag, std::cmatch>());
156 static_assert(testConst<std::cregex_token_iterator, std::forward_iterator_tag, std::csub_match>());
157 #endif // !TEST_HAS_NO_LOCALIZATION
158 
159 #ifndef TEST_HAS_NO_FILESYSTEM_LIBRARY
160 static_assert(test<std::filesystem::directory_iterator, std::input_iterator_tag, std::filesystem::directory_entry,
161                    std::ptrdiff_t, const std::filesystem::directory_entry&, const std::filesystem::directory_entry*>());
162 static_assert(test<std::filesystem::recursive_directory_iterator, std::input_iterator_tag,
163                    std::filesystem::directory_entry, std::ptrdiff_t, const std::filesystem::directory_entry&,
164                    const std::filesystem::directory_entry*>());
165 #endif
166 
167 // Local test iterators.
168 
169 struct AllMembers {
170   struct iterator_category {};
171   struct value_type {};
172   struct difference_type {};
173   struct reference {};
174   struct pointer {};
175 };
176 using AllMembersTraits = std::iterator_traits<AllMembers>;
177 static_assert(std::same_as<AllMembersTraits::iterator_category, AllMembers::iterator_category>);
178 static_assert(std::same_as<AllMembersTraits::value_type, AllMembers::value_type>);
179 static_assert(std::same_as<AllMembersTraits::difference_type, AllMembers::difference_type>);
180 static_assert(std::same_as<AllMembersTraits::reference, AllMembers::reference>);
181 static_assert(std::same_as<AllMembersTraits::pointer, AllMembers::pointer>);
182 static_assert(!has_iterator_concept_v<AllMembersTraits>);
183 
184 struct NoPointerMember {
185   struct iterator_category {};
186   struct value_type {};
187   struct difference_type {};
188   struct reference {};
189   // ignored, because NoPointerMember is not a LegacyInputIterator:
190   value_type* operator->() const;
191 };
192 using NoPointerMemberTraits = std::iterator_traits<NoPointerMember>;
193 static_assert(std::same_as<NoPointerMemberTraits::iterator_category, NoPointerMember::iterator_category>);
194 static_assert(std::same_as<NoPointerMemberTraits::value_type, NoPointerMember::value_type>);
195 static_assert(std::same_as<NoPointerMemberTraits::difference_type, NoPointerMember::difference_type>);
196 static_assert(std::same_as<NoPointerMemberTraits::reference, NoPointerMember::reference>);
197 static_assert(std::same_as<NoPointerMemberTraits::pointer, void>);
198 static_assert(!has_iterator_concept_v<NoPointerMemberTraits>);
199 
200 struct IterConcept {
201   struct iterator_category {};
202   struct value_type {};
203   struct difference_type {};
204   struct reference {};
205   struct pointer {};
206   // iterator_traits does NOT pass through the iterator_concept of the type itself.
207   struct iterator_concept {};
208 };
209 using IterConceptTraits = std::iterator_traits<IterConcept>;
210 static_assert(std::same_as<IterConceptTraits::iterator_category, IterConcept::iterator_category>);
211 static_assert(std::same_as<IterConceptTraits::value_type, IterConcept::value_type>);
212 static_assert(std::same_as<IterConceptTraits::difference_type, IterConcept::difference_type>);
213 static_assert(std::same_as<IterConceptTraits::reference, IterConcept::reference>);
214 static_assert(std::same_as<IterConceptTraits::pointer, IterConcept::pointer>);
215 static_assert(!has_iterator_concept_v<IterConceptTraits>);
216 
217 struct LegacyInput {
218   struct iterator_category {};
219   struct value_type {};
220   struct reference { operator value_type() const; };
221 
222   friend bool operator==(LegacyInput, LegacyInput);
223   reference operator*() const;
224   LegacyInput& operator++();
225   LegacyInput operator++(int);
226 };
227 template <>
228 struct std::incrementable_traits<LegacyInput> {
229   using difference_type = short;
230 };
231 using LegacyInputTraits = std::iterator_traits<LegacyInput>;
232 static_assert(std::same_as<LegacyInputTraits::iterator_category, LegacyInput::iterator_category>);
233 static_assert(std::same_as<LegacyInputTraits::value_type, LegacyInput::value_type>);
234 static_assert(std::same_as<LegacyInputTraits::difference_type, short>);
235 static_assert(std::same_as<LegacyInputTraits::reference, LegacyInput::reference>);
236 static_assert(std::same_as<LegacyInputTraits::pointer, void>);
237 static_assert(!has_iterator_concept_v<LegacyInputTraits>);
238 
239 struct LegacyInputNoValueType {
240   struct not_value_type {};
241   using difference_type = int; // or any signed integral type
242   struct reference { operator not_value_type&() const; };
243 
244   friend bool operator==(LegacyInputNoValueType, LegacyInputNoValueType);
245   reference operator*() const;
246   LegacyInputNoValueType& operator++();
247   LegacyInputNoValueType operator++(int);
248 };
249 template <>
250 struct std::indirectly_readable_traits<LegacyInputNoValueType> {
251   using value_type = LegacyInputNoValueType::not_value_type;
252 };
253 using LegacyInputNoValueTypeTraits = std::iterator_traits<LegacyInputNoValueType>;
254 static_assert(std::same_as<LegacyInputNoValueTypeTraits::iterator_category, std::input_iterator_tag>);
255 static_assert(std::same_as<LegacyInputNoValueTypeTraits::value_type, LegacyInputNoValueType::not_value_type>);
256 static_assert(std::same_as<LegacyInputNoValueTypeTraits::difference_type, int>);
257 static_assert(std::same_as<LegacyInputNoValueTypeTraits::reference, LegacyInputNoValueType::reference>);
258 static_assert(std::same_as<LegacyInputNoValueTypeTraits::pointer, void>);
259 static_assert(!has_iterator_concept_v<LegacyInputNoValueTypeTraits>);
260 
261 struct LegacyForward {
262   struct not_value_type {};
263 
264   friend bool operator==(LegacyForward, LegacyForward);
265   const not_value_type& operator*() const;
266   LegacyForward& operator++();
267   LegacyForward operator++(int);
268 };
269 template <>
270 struct std::indirectly_readable_traits<LegacyForward> {
271   using value_type = LegacyForward::not_value_type;
272 };
273 template <>
274 struct std::incrementable_traits<LegacyForward> {
275   using difference_type = short; // or any signed integral type
276 };
277 using LegacyForwardTraits = std::iterator_traits<LegacyForward>;
278 static_assert(std::same_as<LegacyForwardTraits::iterator_category, std::forward_iterator_tag>);
279 static_assert(std::same_as<LegacyForwardTraits::value_type, LegacyForward::not_value_type>);
280 static_assert(std::same_as<LegacyForwardTraits::difference_type, short>);
281 static_assert(std::same_as<LegacyForwardTraits::reference, const LegacyForward::not_value_type&>);
282 static_assert(std::same_as<LegacyForwardTraits::pointer, void>);
283 static_assert(!has_iterator_concept_v<LegacyForwardTraits>);
284 
285 struct LegacyBidirectional {
286   struct value_type {};
287 
288   friend bool operator==(LegacyBidirectional, LegacyBidirectional);
289   const value_type& operator*() const;
290   LegacyBidirectional& operator++();
291   LegacyBidirectional operator++(int);
292   LegacyBidirectional& operator--();
293   LegacyBidirectional operator--(int);
294   friend short operator-(LegacyBidirectional, LegacyBidirectional);
295 };
296 using LegacyBidirectionalTraits = std::iterator_traits<LegacyBidirectional>;
297 static_assert(std::same_as<LegacyBidirectionalTraits::iterator_category, std::bidirectional_iterator_tag>);
298 static_assert(std::same_as<LegacyBidirectionalTraits::value_type, LegacyBidirectional::value_type>);
299 static_assert(std::same_as<LegacyBidirectionalTraits::difference_type, short>);
300 static_assert(std::same_as<LegacyBidirectionalTraits::reference, const LegacyBidirectional::value_type&>);
301 static_assert(std::same_as<LegacyBidirectionalTraits::pointer, void>);
302 static_assert(!has_iterator_concept_v<LegacyBidirectionalTraits>);
303 
304 // Almost a random access iterator except it is missing operator-(It, It).
305 struct MinusNotDeclaredIter {
306   struct value_type {};
307 
308   friend auto operator<=>(MinusNotDeclaredIter, MinusNotDeclaredIter) = default;
309   const value_type& operator*() const;
310   const value_type& operator[](long) const;
311   MinusNotDeclaredIter& operator++();
312   MinusNotDeclaredIter operator++(int);
313   MinusNotDeclaredIter& operator--();
314   MinusNotDeclaredIter operator--(int);
315   MinusNotDeclaredIter& operator+=(long);
316   MinusNotDeclaredIter& operator-=(long);
317 
318   // Providing difference_type does not fully compensate for missing operator-(It, It).
319   friend MinusNotDeclaredIter operator-(MinusNotDeclaredIter, int);
320   friend MinusNotDeclaredIter operator+(MinusNotDeclaredIter, int);
321   friend MinusNotDeclaredIter operator+(int, MinusNotDeclaredIter);
322 };
323 template <>
324 struct std::incrementable_traits<MinusNotDeclaredIter> {
325   using difference_type = short;
326 };
327 using MinusNotDeclaredIterTraits = std::iterator_traits<MinusNotDeclaredIter>;
328 static_assert(std::same_as<MinusNotDeclaredIterTraits::iterator_category, std::bidirectional_iterator_tag>);
329 static_assert(std::same_as<MinusNotDeclaredIterTraits::value_type, MinusNotDeclaredIter::value_type>);
330 static_assert(std::same_as<MinusNotDeclaredIterTraits::difference_type, short>);
331 static_assert(std::same_as<MinusNotDeclaredIterTraits::reference, const MinusNotDeclaredIter::value_type&>);
332 static_assert(std::same_as<MinusNotDeclaredIterTraits::pointer, void>);
333 static_assert(!has_iterator_concept_v<MinusNotDeclaredIterTraits>);
334 
335 struct WrongSubscriptReturnType {
336   struct value_type {};
337 
338   friend auto operator<=>(WrongSubscriptReturnType, WrongSubscriptReturnType) = default;
339 
340   // The type of it[n] is not convertible to the type of *it; therefore, this is not random-access.
341   value_type& operator*() const;
342   const value_type& operator[](long) const;
343   WrongSubscriptReturnType& operator++();
344   WrongSubscriptReturnType operator++(int);
345   WrongSubscriptReturnType& operator--();
346   WrongSubscriptReturnType operator--(int);
347   WrongSubscriptReturnType& operator+=(long);
348   WrongSubscriptReturnType& operator-=(long);
349   friend short operator-(WrongSubscriptReturnType, WrongSubscriptReturnType);
350   friend WrongSubscriptReturnType operator-(WrongSubscriptReturnType, int);
351   friend WrongSubscriptReturnType operator+(WrongSubscriptReturnType, int);
352   friend WrongSubscriptReturnType operator+(int, WrongSubscriptReturnType);
353 };
354 using WrongSubscriptReturnTypeTraits = std::iterator_traits<WrongSubscriptReturnType>;
355 static_assert(std::same_as<WrongSubscriptReturnTypeTraits::iterator_category, std::bidirectional_iterator_tag>);
356 static_assert(std::same_as<WrongSubscriptReturnTypeTraits::value_type, WrongSubscriptReturnType::value_type>);
357 static_assert(std::same_as<WrongSubscriptReturnTypeTraits::difference_type, short>);
358 static_assert(std::same_as<WrongSubscriptReturnTypeTraits::reference, WrongSubscriptReturnType::value_type&>);
359 static_assert(std::same_as<WrongSubscriptReturnTypeTraits::pointer, void>);
360 static_assert(!has_iterator_concept_v<WrongSubscriptReturnTypeTraits>);
361 
362 struct LegacyRandomAccess {
363   struct value_type {};
364 
365   friend bool operator==(LegacyRandomAccess, LegacyRandomAccess);
366   friend bool operator<(LegacyRandomAccess, LegacyRandomAccess);
367   friend bool operator<=(LegacyRandomAccess, LegacyRandomAccess);
368   friend bool operator>(LegacyRandomAccess, LegacyRandomAccess);
369   friend bool operator>=(LegacyRandomAccess, LegacyRandomAccess);
370   const value_type& operator*() const;
371   const value_type& operator[](long) const;
372   LegacyRandomAccess& operator++();
373   LegacyRandomAccess operator++(int);
374   LegacyRandomAccess& operator--();
375   LegacyRandomAccess operator--(int);
376   LegacyRandomAccess& operator+=(long);
377   LegacyRandomAccess& operator-=(long);
378   friend short operator-(LegacyRandomAccess, LegacyRandomAccess);
379   friend LegacyRandomAccess operator-(LegacyRandomAccess, int);
380   friend LegacyRandomAccess operator+(LegacyRandomAccess, int);
381   friend LegacyRandomAccess operator+(int, LegacyRandomAccess);
382 };
383 using LegacyRandomAccessTraits = std::iterator_traits<LegacyRandomAccess>;
384 static_assert(std::same_as<LegacyRandomAccessTraits::iterator_category, std::random_access_iterator_tag>);
385 static_assert(std::same_as<LegacyRandomAccessTraits::value_type, LegacyRandomAccess::value_type>);
386 static_assert(std::same_as<LegacyRandomAccessTraits::difference_type, short>);
387 static_assert(std::same_as<LegacyRandomAccessTraits::reference, const LegacyRandomAccess::value_type&>);
388 static_assert(std::same_as<LegacyRandomAccessTraits::pointer, void>);
389 static_assert(!has_iterator_concept_v<LegacyRandomAccessTraits>);
390 
391 struct LegacyRandomAccessSpaceship {
392   struct not_value_type {};
393   struct ReferenceConvertible { operator not_value_type&() const; };
394 
395   friend auto operator<=>(LegacyRandomAccessSpaceship, LegacyRandomAccessSpaceship) = default;
396   not_value_type& operator*() const;
397   ReferenceConvertible operator[](long) const;
398   LegacyRandomAccessSpaceship& operator++();
399   LegacyRandomAccessSpaceship operator++(int);
400   LegacyRandomAccessSpaceship& operator--();
401   LegacyRandomAccessSpaceship operator--(int);
402   LegacyRandomAccessSpaceship& operator+=(long);
403   LegacyRandomAccessSpaceship& operator-=(long);
404   friend short operator-(LegacyRandomAccessSpaceship, LegacyRandomAccessSpaceship);
405   friend LegacyRandomAccessSpaceship operator-(LegacyRandomAccessSpaceship, int);
406   friend LegacyRandomAccessSpaceship operator+(LegacyRandomAccessSpaceship, int);
407   friend LegacyRandomAccessSpaceship operator+(int, LegacyRandomAccessSpaceship);
408 };
409 template <>
410 struct std::indirectly_readable_traits<LegacyRandomAccessSpaceship> {
411   using value_type = LegacyRandomAccessSpaceship::not_value_type;
412 };
413 template <>
414 struct std::incrementable_traits<LegacyRandomAccessSpaceship> {
415   using difference_type = short; // or any signed integral type
416 };
417 using LegacyRandomAccessSpaceshipTraits = std::iterator_traits<LegacyRandomAccessSpaceship>;
418 static_assert(std::same_as<LegacyRandomAccessSpaceshipTraits::iterator_category, std::random_access_iterator_tag>);
419 static_assert(std::same_as<LegacyRandomAccessSpaceshipTraits::value_type, LegacyRandomAccessSpaceship::not_value_type>);
420 static_assert(std::same_as<LegacyRandomAccessSpaceshipTraits::difference_type, short>);
421 static_assert(std::same_as<LegacyRandomAccessSpaceshipTraits::reference, LegacyRandomAccessSpaceship::not_value_type&>);
422 static_assert(std::same_as<LegacyRandomAccessSpaceshipTraits::pointer, void>);
423 static_assert(!has_iterator_concept_v<LegacyRandomAccessSpaceshipTraits>);
424 
425 // For output iterators, value_type, difference_type, and reference may be void.
426 struct BareLegacyOutput {
427   struct Empty {};
428   Empty operator*() const;
429   BareLegacyOutput& operator++();
430   BareLegacyOutput operator++(int);
431 };
432 using BareLegacyOutputTraits = std::iterator_traits<BareLegacyOutput>;
433 static_assert(std::same_as<BareLegacyOutputTraits::iterator_category, std::output_iterator_tag>);
434 static_assert(std::same_as<BareLegacyOutputTraits::value_type, void>);
435 static_assert(std::same_as<BareLegacyOutputTraits::difference_type, void>);
436 static_assert(std::same_as<BareLegacyOutputTraits::reference, void>);
437 static_assert(std::same_as<BareLegacyOutputTraits::pointer, void>);
438 static_assert(!has_iterator_concept_v<BareLegacyOutputTraits>);
439 
440 // The operator- means we get difference_type.
441 struct LegacyOutputWithMinus {
442   struct Empty {};
443   Empty operator*() const;
444   LegacyOutputWithMinus& operator++();
445   LegacyOutputWithMinus operator++(int);
446   friend short operator-(LegacyOutputWithMinus, LegacyOutputWithMinus);
447   // Lacking operator==, this is a LegacyIterator but not a LegacyInputIterator.
448 };
449 using LegacyOutputWithMinusTraits = std::iterator_traits<LegacyOutputWithMinus>;
450 static_assert(std::same_as<LegacyOutputWithMinusTraits::iterator_category, std::output_iterator_tag>);
451 static_assert(std::same_as<LegacyOutputWithMinusTraits::value_type, void>);
452 static_assert(std::same_as<LegacyOutputWithMinusTraits::difference_type, short>);
453 static_assert(std::same_as<LegacyOutputWithMinusTraits::reference, void>);
454 static_assert(std::same_as<LegacyOutputWithMinusTraits::pointer, void>);
455 static_assert(!has_iterator_concept_v<LegacyOutputWithMinusTraits>);
456 
457 struct LegacyOutputWithMemberTypes {
458   struct value_type {}; // ignored
459   struct reference {};  // ignored
460   using difference_type = long;
461 
462   friend bool operator==(LegacyOutputWithMemberTypes, LegacyOutputWithMemberTypes);
463   reference operator*() const;
464   LegacyOutputWithMemberTypes& operator++();
465   LegacyOutputWithMemberTypes operator++(int);
466   friend short operator-(LegacyOutputWithMemberTypes, LegacyOutputWithMemberTypes); // ignored
467   // Since (*it) is not convertible to value_type, this is not a LegacyInputIterator.
468 };
469 using LegacyOutputWithMemberTypesTraits = std::iterator_traits<LegacyOutputWithMemberTypes>;
470 static_assert(std::same_as<LegacyOutputWithMemberTypesTraits::iterator_category, std::output_iterator_tag>);
471 static_assert(std::same_as<LegacyOutputWithMemberTypesTraits::value_type, void>);
472 static_assert(std::same_as<LegacyOutputWithMemberTypesTraits::difference_type, long>);
473 static_assert(std::same_as<LegacyOutputWithMemberTypesTraits::reference, void>);
474 static_assert(std::same_as<LegacyOutputWithMemberTypesTraits::pointer, void>);
475 static_assert(!has_iterator_concept_v<LegacyOutputWithMemberTypesTraits>);
476 
477 struct LegacyRandomAccessSpecialized {
478   struct not_value_type {};
479 
480   friend auto operator<=>(LegacyRandomAccessSpecialized, LegacyRandomAccessSpecialized) = default;
481   not_value_type& operator*() const;
482   not_value_type& operator[](long) const;
483   LegacyRandomAccessSpecialized& operator++();
484   LegacyRandomAccessSpecialized operator++(int);
485   LegacyRandomAccessSpecialized& operator--();
486   LegacyRandomAccessSpecialized operator--(int);
487   LegacyRandomAccessSpecialized& operator+=(long);
488   LegacyRandomAccessSpecialized& operator-=(long);
489   friend long operator-(LegacyRandomAccessSpecialized, LegacyRandomAccessSpecialized);
490   friend LegacyRandomAccessSpecialized operator-(LegacyRandomAccessSpecialized, int);
491   friend LegacyRandomAccessSpecialized operator+(LegacyRandomAccessSpecialized, int);
492   friend LegacyRandomAccessSpecialized operator+(int, LegacyRandomAccessSpecialized);
493 };
494 template <class I>
495   requires std::same_as<I, LegacyRandomAccessSpecialized>
496 struct std::iterator_traits<I>
497 {
498   using iterator_category = std::output_iterator_tag;
499   using value_type = short;
500   using difference_type = short;
501   using reference = short&;
502   using pointer = short*;
503 };
504 using LegacyRandomAccessSpecializedTraits = std::iterator_traits<LegacyRandomAccessSpecialized>;
505 static_assert(std::same_as<LegacyRandomAccessSpecializedTraits::iterator_category, std::output_iterator_tag>);
506 static_assert(std::same_as<LegacyRandomAccessSpecializedTraits::value_type, short>);
507 static_assert(std::same_as<LegacyRandomAccessSpecializedTraits::difference_type, short>);
508 static_assert(std::same_as<LegacyRandomAccessSpecializedTraits::reference, short&>);
509 static_assert(std::same_as<LegacyRandomAccessSpecializedTraits::pointer, short*>);
510 static_assert(!has_iterator_concept_v<LegacyRandomAccessSpecializedTraits>);
511 
512 // Other test iterators.
513 
514 using InputTestIteratorTraits = std::iterator_traits<cpp17_input_iterator<int*>>;
515 static_assert(std::same_as<InputTestIteratorTraits::iterator_category, std::input_iterator_tag>);
516 static_assert(std::same_as<InputTestIteratorTraits::value_type, int>);
517 static_assert(std::same_as<InputTestIteratorTraits::difference_type, std::ptrdiff_t>);
518 static_assert(std::same_as<InputTestIteratorTraits::reference, int&>);
519 static_assert(std::same_as<InputTestIteratorTraits::pointer, int*>);
520 static_assert(!has_iterator_concept_v<InputTestIteratorTraits>);
521 
522 using OutputTestIteratorTraits = std::iterator_traits<cpp17_output_iterator<int*>>;
523 static_assert(std::same_as<OutputTestIteratorTraits::iterator_category, std::output_iterator_tag>);
524 static_assert(std::same_as<OutputTestIteratorTraits::value_type, void>);
525 static_assert(std::same_as<OutputTestIteratorTraits::difference_type, std::ptrdiff_t>);
526 static_assert(std::same_as<OutputTestIteratorTraits::reference, int&>);
527 static_assert(std::same_as<OutputTestIteratorTraits::pointer, int*>);
528 static_assert(!has_iterator_concept_v<OutputTestIteratorTraits>);
529 
530 using ForwardTestIteratorTraits = std::iterator_traits<forward_iterator<int*>>;
531 static_assert(std::same_as<ForwardTestIteratorTraits::iterator_category, std::forward_iterator_tag>);
532 static_assert(std::same_as<ForwardTestIteratorTraits::value_type, int>);
533 static_assert(std::same_as<ForwardTestIteratorTraits::difference_type, std::ptrdiff_t>);
534 static_assert(std::same_as<ForwardTestIteratorTraits::reference, int&>);
535 static_assert(std::same_as<ForwardTestIteratorTraits::pointer, int*>);
536 static_assert(!has_iterator_concept_v<ForwardTestIteratorTraits>);
537 
538 using BidirectionalTestIteratorTraits = std::iterator_traits<bidirectional_iterator<int*>>;
539 static_assert(std::same_as<BidirectionalTestIteratorTraits::iterator_category, std::bidirectional_iterator_tag>);
540 static_assert(std::same_as<BidirectionalTestIteratorTraits::value_type, int>);
541 static_assert(std::same_as<BidirectionalTestIteratorTraits::difference_type, std::ptrdiff_t>);
542 static_assert(std::same_as<BidirectionalTestIteratorTraits::reference, int&>);
543 static_assert(std::same_as<BidirectionalTestIteratorTraits::pointer, int*>);
544 static_assert(!has_iterator_concept_v<BidirectionalTestIteratorTraits>);
545 
546 using RandomAccessTestIteratorTraits = std::iterator_traits<random_access_iterator<int*>>;
547 static_assert(std::same_as<RandomAccessTestIteratorTraits::iterator_category, std::random_access_iterator_tag>);
548 static_assert(std::same_as<RandomAccessTestIteratorTraits::value_type, int>);
549 static_assert(std::same_as<RandomAccessTestIteratorTraits::difference_type, std::ptrdiff_t>);
550 static_assert(std::same_as<RandomAccessTestIteratorTraits::reference, int&>);
551 static_assert(std::same_as<RandomAccessTestIteratorTraits::pointer, int*>);
552 static_assert(!has_iterator_concept_v<RandomAccessTestIteratorTraits>);
553 
554 using ContiguousTestIteratorTraits = std::iterator_traits<contiguous_iterator<int*>>;
555 static_assert(std::same_as<ContiguousTestIteratorTraits::iterator_category, std::contiguous_iterator_tag>);
556 static_assert(std::same_as<ContiguousTestIteratorTraits::value_type, int>);
557 static_assert(std::same_as<ContiguousTestIteratorTraits::difference_type, std::ptrdiff_t>);
558 static_assert(std::same_as<ContiguousTestIteratorTraits::reference, int&>);
559 static_assert(std::same_as<ContiguousTestIteratorTraits::pointer, int*>);
560 static_assert(!has_iterator_concept_v<ContiguousTestIteratorTraits>);
561 
562 using Cpp17BasicIteratorTraits = std::iterator_traits<iterator_traits_cpp17_iterator>;
563 static_assert(std::same_as<Cpp17BasicIteratorTraits::iterator_category, std::output_iterator_tag>);
564 static_assert(std::same_as<Cpp17BasicIteratorTraits::value_type, void>);
565 static_assert(std::same_as<Cpp17BasicIteratorTraits::difference_type, void>);
566 static_assert(std::same_as<Cpp17BasicIteratorTraits::reference, void>);
567 static_assert(std::same_as<Cpp17BasicIteratorTraits::pointer, void>);
568 static_assert(!has_iterator_concept_v<Cpp17BasicIteratorTraits>);
569 
570 using Cpp17InputIteratorTraits = std::iterator_traits<iterator_traits_cpp17_input_iterator>;
571 static_assert(std::same_as<Cpp17InputIteratorTraits::iterator_category, std::input_iterator_tag>);
572 static_assert(std::same_as<Cpp17InputIteratorTraits::value_type, long>);
573 static_assert(std::same_as<Cpp17InputIteratorTraits::difference_type, int>);
574 static_assert(std::same_as<Cpp17InputIteratorTraits::reference, int&>);
575 static_assert(std::same_as<Cpp17InputIteratorTraits::pointer, void>);
576 static_assert(!has_iterator_concept_v<Cpp17InputIteratorTraits>);
577 
578 using Cpp17ForwardIteratorTraits = std::iterator_traits<iterator_traits_cpp17_forward_iterator>;
579 static_assert(std::same_as<Cpp17ForwardIteratorTraits::iterator_category, std::forward_iterator_tag>);
580 static_assert(std::same_as<Cpp17ForwardIteratorTraits::value_type, int>);
581 static_assert(std::same_as<Cpp17ForwardIteratorTraits::difference_type, int>);
582 static_assert(std::same_as<Cpp17ForwardIteratorTraits::reference, int&>);
583 static_assert(std::same_as<Cpp17ForwardIteratorTraits::pointer, void>);
584 static_assert(!has_iterator_concept_v<Cpp17ForwardIteratorTraits>);
585