1 /// \file
2 // Range v3 library
3 //
4 //  Copyright Eric Niebler 2013-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 
15 #ifndef RANGES_V3_ITERATOR_ACCESS_HPP
16 #define RANGES_V3_ITERATOR_ACCESS_HPP
17 
18 #include <iterator>
19 #include <type_traits>
20 #include <utility>
21 
22 #include <std/detail/associated_types.hpp>
23 
24 #include <meta/meta.hpp>
25 
26 #include <concepts/concepts.hpp>
27 
28 #include <range/v3/range_fwd.hpp>
29 
30 #include <range/v3/utility/move.hpp>
31 #include <range/v3/utility/static_const.hpp>
32 #include <range/v3/utility/swap.hpp>
33 
34 #include <range/v3/detail/prologue.hpp>
35 
36 namespace ranges
37 {
38     /// \addtogroup group-iterator
39     /// @{
40 
41     /// \cond
42     namespace detail
43     {
44         template<typename I,
45 #ifdef RANGES_WORKAROUND_MSVC_683388
46                  typename R = meta::conditional_t<
47                      std::is_pointer<uncvref_t<I>>::value &&
48                          std::is_array<std::remove_pointer_t<uncvref_t<I>>>::value,
49                      std::add_lvalue_reference_t<std::remove_pointer_t<uncvref_t<I>>>,
50                      decltype(*std::declval<I &>())>,
51 #else
52                  typename R = decltype(*std::declval<I &>()),
53 #endif
54                  typename = R &>
55         using iter_reference_t_ = R;
56 
57 #if defined(RANGES_DEEP_STL_INTEGRATION) && RANGES_DEEP_STL_INTEGRATION && \
58     !defined(RANGES_DOXYGEN_INVOKED)
59         template<typename T>
60         using iter_value_t_ =
61             typename meta::conditional_t<
62                 is_std_iterator_traits_specialized_v<T>,
63                 std::iterator_traits<T>,
64                 indirectly_readable_traits<T>>::value_type;
65 #else
66         template<typename T>
67         using iter_value_t_ = typename indirectly_readable_traits<T>::value_type;
68 #endif
69     } // namespace detail
70     /// \endcond
71 
72     template<typename R>
73     using iter_reference_t = detail::iter_reference_t_<R>;
74 
75     template<typename R>
76     using iter_value_t = detail::iter_value_t_<uncvref_t<R>>;
77 
78     /// \cond
79     namespace _iter_move_
80     {
81 #if RANGES_BROKEN_CPO_LOOKUP
82         void iter_move(); // unqualified name lookup block
83 #endif
84 
85         template<typename T>
86         decltype(iter_move(std::declval<T>())) try_adl_iter_move_(int);
87 
88         template<typename T>
89         void try_adl_iter_move_(long);
90 
91         template<typename T>
92         RANGES_INLINE_VAR constexpr bool is_adl_indirectly_movable_v =
93             !RANGES_IS_SAME(void, decltype(_iter_move_::try_adl_iter_move_<T>(42)));
94 
95         struct fn
96         {
97             // clang-format off
98             template<typename I,
99                      typename = detail::enable_if_t<is_adl_indirectly_movable_v<I &>>>
100 #ifndef RANGES_WORKAROUND_CLANG_23135
101             constexpr
102 #endif // RANGES_WORKAROUND_CLANG_23135
103             auto CPP_auto_fun(operator())(I &&i)(const)
104             (
105                 return iter_move(i)
106             )
107 
108             template<
109                 typename I,
110                 typename = detail::enable_if_t<!is_adl_indirectly_movable_v<I &>>,
111                 typename R = iter_reference_t<I>>
112 #ifndef RANGES_WORKAROUND_CLANG_23135
113             constexpr
114 #endif // RANGES_WORKAROUND_CLANG_23135
115             auto CPP_auto_fun(operator())(I &&i)(const)
116             (
117                 return static_cast<aux::move_t<R>>(aux::move(*i))
118             )
119             // clang-format on
120         };
121     } // namespace _iter_move_
122     /// \endcond
123 
124     RANGES_DEFINE_CPO(_iter_move_::fn, iter_move)
125 
126     /// \cond
127     namespace detail
128     {
129         template<typename I, typename O>
130         auto is_indirectly_movable_(I & (*i)(), O & (*o)(), iter_value_t<I> * v = nullptr)
131             -> always_<std::true_type,
132                        decltype(iter_value_t<I>(iter_move(i()))),
133                        decltype(*v = iter_move(i())),
134                        decltype(*o() = (iter_value_t<I> &&) * v),
135                        decltype(*o() = iter_move(i()))>;
136         template<typename I, typename O>
137         auto is_indirectly_movable_(...) -> std::false_type;
138 
139         template<typename I, typename O>
140         auto is_nothrow_indirectly_movable_(iter_value_t<I> * v) -> meta::bool_<
141             noexcept(iter_value_t<I>(iter_move(std::declval<I &>()))) &&
142             noexcept(*v = iter_move(std::declval<I &>())) &&
143             noexcept(*std::declval<O &>() = (iter_value_t<I> &&) * v) &&
144             noexcept(*std::declval<O &>() = iter_move(std::declval<I &>()))>;
145         template<typename I, typename O>
146         auto is_nothrow_indirectly_movable_(...) -> std::false_type;
147     } // namespace detail
148     /// \endcond
149 
150     template<typename I, typename O>
151     RANGES_INLINE_VAR constexpr bool is_indirectly_movable_v =
152         decltype(detail::is_indirectly_movable_<I, O>(nullptr, nullptr))::value;
153 
154     template<typename I, typename O>
155     RANGES_INLINE_VAR constexpr bool is_nothrow_indirectly_movable_v =
156         decltype(detail::is_nothrow_indirectly_movable_<I, O>(nullptr))::value;
157 
158     template<typename I, typename O>
159     struct is_indirectly_movable : meta::bool_<is_indirectly_movable_v<I, O>>
160     {};
161 
162     template<typename I, typename O>
163     struct is_nothrow_indirectly_movable
164       : meta::bool_<is_nothrow_indirectly_movable_v<I, O>>
165     {};
166 
167     /// \cond
168     namespace _iter_swap_
169     {
170         struct nope
171         {};
172 
173         // Q: Should std::reference_wrapper be considered a proxy wrt swapping rvalues?
174         // A: No. Its operator= is currently defined to reseat the references, so
175         //    std::swap(ra, rb) already means something when ra and rb are (lvalue)
176         //    reference_wrappers. That reseats the reference wrappers but leaves the
177         //    referents unmodified. Treating rvalue reference_wrappers differently would
178         //    be confusing.
179 
180         // Q: Then why is it OK to "re"-define swap for pairs and tuples of references?
181         // A: Because as defined above, swapping an rvalue tuple of references has the
182         //    same semantics as swapping an lvalue tuple of references. Rather than
183         //    reseat the references, assignment happens *through* the references.
184 
185         // Q: But I have an iterator whose operator* returns an rvalue
186         //    std::reference_wrapper<T>. How do I make it model indirectly_swappable?
187         // A: With an overload of iter_swap.
188 
189         // Intentionally create an ambiguity with std::iter_swap, which is
190         // unconstrained.
191         template<typename T, typename U>
192         nope iter_swap(T, U) = delete;
193 
194 #ifdef RANGES_WORKAROUND_MSVC_895622
195         nope iter_swap();
196 #endif
197 
198         template<typename T, typename U>
199         decltype(iter_swap(std::declval<T>(), std::declval<U>())) try_adl_iter_swap_(int);
200 
201         template<typename T, typename U>
202         nope try_adl_iter_swap_(long);
203 
204         // Test whether an overload of iter_swap for a T and a U can be found
205         // via ADL with the iter_swap overload above participating in the
206         // overload set. This depends on user-defined iter_swap overloads
207         // being a better match than the overload in namespace std.
208         template<typename T, typename U>
209         RANGES_INLINE_VAR constexpr bool is_adl_indirectly_swappable_v =
210             !RANGES_IS_SAME(nope, decltype(_iter_swap_::try_adl_iter_swap_<T, U>(42)));
211 
212         struct fn
213         {
214             // *If* a user-defined iter_swap is found via ADL, call that:
215             template<typename T, typename U>
operator ()ranges::_iter_swap_::fn216             constexpr detail::enable_if_t<is_adl_indirectly_swappable_v<T, U>> operator()(
217                 T && t, U && u) const noexcept(noexcept(iter_swap((T &&) t, (U &&) u)))
218             {
219                 (void)iter_swap((T &&) t, (U &&) u);
220             }
221 
222             // *Otherwise*, for readable types with swappable reference
223             // types, call ranges::swap(*a, *b)
224             template<typename I0, typename I1>
225             constexpr detail::enable_if_t<
226                 !is_adl_indirectly_swappable_v<I0, I1> &&
227                 is_swappable_with<iter_reference_t<I0>, iter_reference_t<I1>>::value>
operator ()ranges::_iter_swap_::fn228             operator()(I0 && a, I1 && b) const noexcept(noexcept(ranges::swap(*a, *b)))
229             {
230                 ranges::swap(*a, *b);
231             }
232 
233             // *Otherwise*, for readable types that are mutually
234             // indirectly_movable_storable, implement as:
235             //      iter_value_t<T0> tmp = iter_move(a);
236             //      *a = iter_move(b);
237             //      *b = std::move(tmp);
238             template<typename I0, typename I1>
239             constexpr detail::enable_if_t<
240                 !is_adl_indirectly_swappable_v<I0, I1> &&
241                 !is_swappable_with<iter_reference_t<I0>, iter_reference_t<I1>>::value &&
242                 is_indirectly_movable_v<I0, I1> && is_indirectly_movable_v<I1, I0>>
operator ()ranges::_iter_swap_::fn243             operator()(I0 && a, I1 && b) const
244                 noexcept(is_nothrow_indirectly_movable_v<I0, I1> &&
245                              is_nothrow_indirectly_movable_v<I1, I0>)
246             {
247                 iter_value_t<I0> v0 = iter_move(a);
248                 *a = iter_move(b);
249                 *b = detail::move(v0);
250             }
251         };
252     } // namespace _iter_swap_
253     /// \endcond
254 
255     /// \relates _iter_swap_::fn
256     RANGES_DEFINE_CPO(_iter_swap_::fn, iter_swap)
257 
258     /// \cond
259     namespace detail
260     {
261         template<typename T, typename U>
262         auto is_indirectly_swappable_(T & (*t)(), U & (*u)())
263             -> detail::always_<std::true_type, decltype(iter_swap(t(), u()))>;
264         template<typename T, typename U>
265         auto is_indirectly_swappable_(...) -> std::false_type;
266 
267         template<typename T, typename U>
268         auto is_nothrow_indirectly_swappable_(int)
269             -> meta::bool_<noexcept(iter_swap(std::declval<T &>(), std::declval<U &>()))>;
270         template<typename T, typename U>
271         auto is_nothrow_indirectly_swappable_(long) -> std::false_type;
272     } // namespace detail
273     /// \endcond
274 
275     template<typename T, typename U>
276     RANGES_INLINE_VAR constexpr bool is_indirectly_swappable_v =
277         decltype(detail::is_indirectly_swappable_<T, U>(nullptr, nullptr))::value;
278 
279     template<typename T, typename U>
280     RANGES_INLINE_VAR constexpr bool is_nothrow_indirectly_swappable_v =
281         decltype(detail::is_nothrow_indirectly_swappable_<T, U>(0))::value;
282 
283     template<typename T, typename U>
284     struct is_indirectly_swappable : meta::bool_<is_indirectly_swappable_v<T, U>>
285     {};
286 
287     template<typename T, typename U>
288     struct is_nothrow_indirectly_swappable
289       : meta::bool_<is_nothrow_indirectly_swappable_v<T, U>>
290     {};
291 
292     namespace cpp20
293     {
294         using ranges::iter_move;
295         using ranges::iter_reference_t;
296         using ranges::iter_swap;
297         using ranges::iter_value_t;
298     } // namespace cpp20
299     /// @}
300 } // namespace ranges
301 
302 #include <range/v3/detail/epilogue.hpp>
303 
304 #endif // RANGES_V3_ITERATOR_ACCESS_HPP
305