1 /// \file
2 // Range v3 library
3 //
4 //  Copyright Eric Niebler 2014-present
5 //  Copyright Casey Carter 2016
6 //
7 //  Use, modification and distribution is subject to the
8 //  Boost Software License, Version 1.0. (See accompanying
9 //  file LICENSE_1_0.txt or copy at
10 //  http://www.boost.org/LICENSE_1_0.txt)
11 //
12 // Project home: https://github.com/ericniebler/range-v3
13 //
14 #ifndef RANGES_V3_ITERATOR_COMMON_ITERATOR_HPP
15 #define RANGES_V3_ITERATOR_COMMON_ITERATOR_HPP
16 
17 #include <cstdint>
18 #include <iterator>
19 #include <type_traits>
20 
21 #include <meta/meta.hpp>
22 
23 #include <concepts/concepts.hpp>
24 
25 #include <range/v3/range_fwd.hpp>
26 
27 #include <range/v3/detail/variant.hpp>
28 #include <range/v3/iterator/basic_iterator.hpp>
29 #include <range/v3/iterator/concepts.hpp>
30 #include <range/v3/utility/common_tuple.hpp>
31 
32 #include <range/v3/detail/prologue.hpp>
33 
34 namespace ranges
35 {
36     /// \addtogroup group-iterator
37     /// @{
38 
39     /// \cond
40     namespace detail
41     {
42         template<typename I, typename S>
cidata(common_iterator<I,S> & that)43         variant<I, S> & cidata(common_iterator<I, S> & that)
44         {
45             return that.data_;
46         }
47 
48         template<typename I, typename S>
cidata(common_iterator<I,S> const & that)49         variant<I, S> const & cidata(common_iterator<I, S> const & that)
50         {
51             return that.data_;
52         }
53     } // namespace detail
54 
55 #if RANGES_BROKEN_CPO_LOOKUP
56     namespace _common_iterator_
57     {
58         struct adl_hook
59         {};
60     } // namespace _common_iterator_
61 #endif
62     /// \endcond
63 
64     template<typename I, typename S>
65     struct common_iterator
66 #if RANGES_BROKEN_CPO_LOOKUP
67       : private _common_iterator_::adl_hook
68 #endif
69     {
70     private:
71         CPP_assert(input_or_output_iterator<I>);
72         CPP_assert(sentinel_for<S, I>);
73         CPP_assert(!same_as<I, S>);
74         variant<I, S> data_;
75 
76         friend variant<I, S> & detail::cidata<>(common_iterator<I, S> &);
77         friend variant<I, S> const & detail::cidata<>(common_iterator<I, S> const &);
78         struct emplace_fn
79         {
80             variant<I, S> * data_;
81             template<typename T, std::size_t N>
operator ()ranges::common_iterator::emplace_fn82             void operator()(indexed_element<T, N> t) const
83             {
84                 ranges::emplace<N>(*data_, t.get());
85             }
86         };
87         struct arrow_proxy_
88         {
89         private:
90             friend common_iterator;
91             iter_value_t<I> keep_;
arrow_proxy_ranges::common_iterator::arrow_proxy_92             arrow_proxy_(iter_reference_t<I> && x)
93               : keep_(std::move(x))
94             {}
95 
96         public:
operator ->ranges::common_iterator::arrow_proxy_97             const iter_value_t<I> * operator->() const noexcept
98             {
99                 return std::addressof(keep_);
100             }
101         };
102         template<typename T>
operator_arrow_ranges::common_iterator103         static T * operator_arrow_(T * p, int) noexcept
104         {
105             return p;
106         }
107         template<typename J, typename = detail::iter_arrow_t<J const>>
operator_arrow_ranges::common_iterator108         static J operator_arrow_(J const & j, int) noexcept(noexcept(J(j)))
109         {
110             return j;
111         }
112         template(typename J, typename R = iter_reference_t<J>)(
113             /// \pre
114             requires std::is_reference<R>::value) //
operator_arrow_ranges::common_iterator115         static meta::_t<std::add_pointer<R>> operator_arrow_(J const & j, long) noexcept
116         {
117             auto && r = *j;
118             return std::addressof(r);
119         }
120         template(typename J, typename V = iter_value_t<J>)(
121             /// \pre
122             requires constructible_from<V, iter_reference_t<J>>)
123         static arrow_proxy_ operator_arrow_(J const & j, ...) noexcept(noexcept(V(V(*j))))
124         {
125             return arrow_proxy_(*j);
126         }
127 
128     public:
129         using difference_type = iter_difference_t<I>;
130 
131         common_iterator() = default;
common_iteratorranges::common_iterator132         common_iterator(I i)
133           : data_(emplaced_index<0>, std::move(i))
134         {}
common_iteratorranges::common_iterator135         common_iterator(S s)
136           : data_(emplaced_index<1>, std::move(s))
137         {}
138         template(typename I2, typename S2)(
139             /// \pre
140             requires convertible_to<I2, I> AND convertible_to<S2, S>)
common_iteratorranges::common_iterator141         common_iterator(common_iterator<I2, S2> const & that)
142           : data_(detail::variant_core_access::make_empty<I, S>())
143         {
144             detail::cidata(that).visit_i(emplace_fn{&data_});
145         }
146         template(typename I2, typename S2)(
147             /// \pre
148             requires convertible_to<I2, I> AND convertible_to<S2, S>)
149         common_iterator & operator=(common_iterator<I2, S2> const & that)
150         {
151             detail::cidata(that).visit_i(emplace_fn{&data_});
152             return *this;
153         }
154         iter_reference_t<I> operator*() //
155             noexcept(noexcept(iter_reference_t<I>(*std::declval<I &>())))
156         {
157             return *ranges::get<0>(data_);
158         }
159         CPP_member
operator *ranges::common_iterator160         auto operator*() const //
161             noexcept(noexcept(iter_reference_t<I>(*std::declval<I const &>())))
162             -> CPP_ret(iter_reference_t<I>)(
163                 /// \pre
164                 requires indirectly_readable<I const>)
165         {
166             return *ranges::get<0>(data_);
167         }
168         template(typename J = I)(
169             /// \pre
170             requires indirectly_readable<J>)
operator ->() const171         auto operator->() const //
172             noexcept(
173                 noexcept(common_iterator::operator_arrow_(std::declval<I const &>(), 42)))
174             -> decltype(common_iterator::operator_arrow_(std::declval<J const &>(), 42))
175         {
176             return common_iterator::operator_arrow_(ranges::get<0>(data_), 42);
177         }
178         common_iterator & operator++()
179         {
180             ++ranges::get<0>(data_);
181             return *this;
182         }
183 #ifdef RANGES_WORKAROUND_MSVC_677925
184         template(typename I2 = I)(
185             /// \pre
186             requires (!forward_iterator<I2>)) //
187         auto operator++(int) //
188             -> decltype(std::declval<I2 &>()++)
189         {
190             return ranges::get<0>(data_)++;
191         }
192 #else  // ^^^ workaround ^^^ / vvv no workaround vvv
193         CPP_member
194         auto operator++(int) //
195             -> CPP_ret(decltype(std::declval<I &>()++))(
196                 /// \pre
197                 requires (!forward_iterator<I>))
198         {
199             return ranges::get<0>(data_)++;
200         }
201 #endif // RANGES_WORKAROUND_MSVC_677925
202         CPP_member
203         auto operator++(int) //
204             -> CPP_ret(common_iterator)(
205                 /// \pre
206                 requires forward_iterator<I>)
207         {
208             return common_iterator(ranges::get<0>(data_)++);
209         }
210 
211 #if !RANGES_BROKEN_CPO_LOOKUP
212         template<typename I_ = I>
213         friend constexpr auto iter_move(common_iterator const & i) //
214             noexcept(detail::has_nothrow_iter_move_v<I>)
215             -> CPP_broken_friend_ret(iter_rvalue_reference_t<I>)(
216                 /// \pre
217                 requires input_iterator<I_>)
218         {
219             return ranges::iter_move(ranges::get<0>(detail::cidata(i)));
220         }
221         template<typename I2, typename S2>
iter_swap(common_iterator const & x,common_iterator<I2,S2> const & y)222         friend auto iter_swap(
223             common_iterator const & x,
224             common_iterator<I2, S2> const &
225                 y) noexcept(is_nothrow_indirectly_swappable<I, I2>::value)
226             -> CPP_broken_friend_ret(void)(
227                 /// \pre
228                 requires indirectly_swappable<I2, I>)
229         {
230             return ranges::iter_swap(ranges::get<0>(detail::cidata(x)),
231                                      ranges::get<0>(detail::cidata(y)));
232         }
233 #endif
234     };
235 
236     /// \cond
237 #if RANGES_BROKEN_CPO_LOOKUP
238     namespace _common_iterator_
239     {
240         template<typename I, typename S>
iter_move(common_iterator<I,S> const & i)241         constexpr auto iter_move(common_iterator<I, S> const & i) noexcept(
242             detail::has_nothrow_iter_move_v<I>)
243             -> CPP_broken_friend_ret(iter_rvalue_reference_t<I>)(
244                 /// \pre
245                 requires input_iterator<I>)
246         {
247             return ranges::iter_move(ranges::get<0>(detail::cidata(i)));
248         }
249         template<typename I1, typename S1, typename I2, typename S2>
iter_swap(common_iterator<I1,S1> const & x,common_iterator<I2,S2> const & y)250         auto iter_swap(common_iterator<I1, S1> const & x,
251                        common_iterator<I2, S2> const & y) //
252             noexcept(is_nothrow_indirectly_swappable<I1, I2>::value)
253                 -> CPP_broken_friend_ret(void)(
254                     /// \pre
255                     requires indirectly_swappable<I1, I2>)
256         {
257             return ranges::iter_swap(ranges::get<0>(detail::cidata(x)),
258                                      ranges::get<0>(detail::cidata(y)));
259         }
260     } // namespace _common_iterator_
261 #endif
262     /// \endcond
263 
264     template(typename I1, typename I2, typename S1, typename S2)(
265         /// \pre
266         requires sentinel_for<S1, I2> AND sentinel_for<S2, I1> AND
267         (!equality_comparable_with<I1, I2>)) //
268     bool operator==(common_iterator<I1, S1> const & x, common_iterator<I2, S2> const & y)
269     {
270         return detail::cidata(x).index() == 1u ? (detail::cidata(y).index() == 1u ||
271                                                   ranges::get<0>(detail::cidata(y)) ==
272                                                       ranges::get<1>(detail::cidata(x)))
273                                                : (detail::cidata(y).index() != 1u ||
274                                                   ranges::get<0>(detail::cidata(x)) ==
275                                                       ranges::get<1>(detail::cidata(y)));
276     }
277 
278     template(typename I1, typename I2, typename S1, typename S2)(
279         /// \pre
280         requires sentinel_for<S1, I2> AND sentinel_for<S2, I1> AND
281             equality_comparable_with<I1, I2>)
282     bool operator==(common_iterator<I1, S1> const & x, common_iterator<I2, S2> const & y)
283     {
284         return detail::cidata(x).index() == 1u
285                    ? (detail::cidata(y).index() == 1u ||
286                       ranges::get<0>(detail::cidata(y)) ==
287                           ranges::get<1>(detail::cidata(x)))
288                    : (detail::cidata(y).index() == 1u
289                           ? ranges::get<0>(detail::cidata(x)) ==
290                                 ranges::get<1>(detail::cidata(y))
291                           : ranges::get<0>(detail::cidata(x)) ==
292                                 ranges::get<0>(detail::cidata(y)));
293     }
294 
295     template(typename I1, typename I2, typename S1, typename S2)(
296         /// \pre
297         requires sentinel_for<S1, I2> AND sentinel_for<S2, I1>)
298     bool operator!=(common_iterator<I1, S1> const & x, common_iterator<I2, S2> const & y)
299     {
300         return !(x == y);
301     }
302 
303     template(typename I1, typename I2, typename S1, typename S2)(
304         /// \pre
305         requires sized_sentinel_for<I1, I2> AND sized_sentinel_for<S1, I2> AND
306             sized_sentinel_for<S2, I1>)
307     iter_difference_t<I2> operator-(common_iterator<I1, S1> const & x,
308                                     common_iterator<I2, S2> const & y)
309     {
310         return detail::cidata(x).index() == 1u
311                    ? (detail::cidata(y).index() == 1u
312                           ? 0
313                           : ranges::get<1>(detail::cidata(x)) -
314                                 ranges::get<0>(detail::cidata(y)))
315                    : (detail::cidata(y).index() == 1u
316                           ? ranges::get<0>(detail::cidata(x)) -
317                                 ranges::get<1>(detail::cidata(y))
318                           : ranges::get<0>(detail::cidata(x)) -
319                                 ranges::get<0>(detail::cidata(y)));
320     }
321 
322     template<typename I, typename S>
323     struct indirectly_readable_traits<common_iterator<I, S>>
324       : meta::if_c<
325         (bool)indirectly_readable<I>,
326         indirectly_readable_traits<I>,
327         meta::nil_>
328     {};
329 
330     /// \cond
331     namespace detail
332     {
333         template<typename I>
334         auto demote_common_iter_cat(...) -> nil_;
335         template<typename I>
336         auto demote_common_iter_cat(long)
337             -> with_iterator_category<std::input_iterator_tag>;
338         template(typename I)(
339             /// \pre
340             requires derived_from<typename std::iterator_traits<I>::iterator_category,
341                                       std::forward_iterator_tag>)
342         auto demote_common_iter_cat(int)
343             -> with_iterator_category<std::forward_iterator_tag>;
344 
345         template<typename I, bool = (bool)input_iterator<I>>
346         struct common_iterator_std_traits : decltype(detail::demote_common_iter_cat<I>(0))
347         {
348             using difference_type = iter_difference_t<I>;
349             using value_type = iter_value_t<I>;
350             using reference = iter_reference_t<I>;
351             using pointer = detail::iter_pointer_t<I>;
352             using iterator_concept =
353                 meta::conditional_t<(bool)forward_iterator<I>, std::forward_iterator_tag,
354                           std::input_iterator_tag>;
355         };
356 
357         template<typename I>
358         struct common_iterator_std_traits<I, false>
359         {
360             using difference_type = iter_difference_t<I>;
361             using value_type = void;
362             using reference = void;
363             using pointer = void;
364             using iterator_category = std::output_iterator_tag;
365         };
366 
367         // An iterator adaptor that demotes a user-defined difference_type to
368         // std::intmax_t, for use when constructing containers from such
369         // iterators.
370         template<typename I>
371         struct cpp17_iterator_cursor
372         {
373         private:
374             friend range_access;
375             I it_;
376             struct mixin : basic_mixin<cpp17_iterator_cursor>
377             {
378                 mixin() = default;
379                 #ifndef _MSC_VER
380                 using basic_mixin<cpp17_iterator_cursor>::basic_mixin;
381                 #else
mixinranges::detail::cpp17_iterator_cursor::mixin382                 constexpr explicit mixin(cpp17_iterator_cursor && cur)
383                   : basic_mixin<cpp17_iterator_cursor>(
384                         static_cast<cpp17_iterator_cursor &&>(cur))
385                 {}
mixinranges::detail::cpp17_iterator_cursor::mixin386                 constexpr explicit mixin(cpp17_iterator_cursor const & cur)
387                   : basic_mixin<cpp17_iterator_cursor>(cur)
388                 {}
389                 #endif
mixinranges::detail::cpp17_iterator_cursor::mixin390                 explicit mixin(I it)
391                   : mixin{cpp17_iterator_cursor{std::move(it)}}
392                 {}
baseranges::detail::cpp17_iterator_cursor::mixin393                 I base() const
394                 {
395                     return this->get().it_;
396                 }
397             };
398 
399         public:
400             using single_pass = meta::bool_<!forward_iterator<I>>;
401             using difference_type = std::ptrdiff_t;
402             using value_type = iter_value_t<I>;
403 
404             cpp17_iterator_cursor() = default;
cpp17_iterator_cursorranges::detail::cpp17_iterator_cursor405             constexpr explicit cpp17_iterator_cursor(I i)
406               : it_(static_cast<I &&>(i))
407             {}
408 
arrowranges::detail::cpp17_iterator_cursor409             I arrow() const
410             {
411                 return it_;
412             }
readranges::detail::cpp17_iterator_cursor413             decltype(auto) read()
414             {
415                 return *it_;
416             }
readranges::detail::cpp17_iterator_cursor417             decltype(auto) read() const
418             {
419                 return *it_;
420             }
nextranges::detail::cpp17_iterator_cursor421             void next()
422             {
423                 ++it_;
424             }
equalranges::detail::cpp17_iterator_cursor425             bool equal(cpp17_iterator_cursor const & that) const
426             {
427                 return it_ == that.it_;
428             }
429             CPP_member
prevranges::detail::cpp17_iterator_cursor430             auto prev() //
431                 -> CPP_ret(void)(
432                     /// \pre
433                     requires bidirectional_iterator<I>)
434             {
435                 --it_;
436             }
437             CPP_member
advanceranges::detail::cpp17_iterator_cursor438             auto advance(std::ptrdiff_t n) //
439                 -> CPP_ret(void)(
440                     /// \pre
441                     requires random_access_iterator<I>)
442             {
443                 it_ += static_cast<iter_difference_t<I>>(n);
444             }
445             CPP_member
distance_toranges::detail::cpp17_iterator_cursor446             auto distance_to(cpp17_iterator_cursor const & that) //
447                 -> CPP_ret(std::ptrdiff_t)(
448                     /// \pre
449                     requires random_access_iterator<I>)
450             {
451                 auto d = that.it_ - it_;
452                 RANGES_EXPECT(d <= PTRDIFF_MAX);
453                 return static_cast<std::ptrdiff_t>(d);
454             }
455         };
456     } // namespace detail
457     /// \endcond
458 
459     namespace cpp20
460     {
461         using ranges::common_iterator;
462     }
463     /// @}
464 } // namespace ranges
465 
466 /// \cond
467 RANGES_DIAGNOSTIC_PUSH
468 RANGES_DIAGNOSTIC_IGNORE_MISMATCHED_TAGS
469 
470 namespace std
471 {
472     template<typename I, typename S>
473     struct iterator_traits<::ranges::common_iterator<I, S>>
474       : ::ranges::detail::common_iterator_std_traits<I>
475     {};
476 } // namespace std
477 
478 RANGES_DIAGNOSTIC_POP
479 /// \endcond
480 
481 #include <range/v3/detail/epilogue.hpp>
482 
483 #endif
484