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___RANGES_SUBRANGE_H
11 #define _LIBCPP___RANGES_SUBRANGE_H
12 
13 #include <__assert>
14 #include <__concepts/constructible.h>
15 #include <__concepts/convertible_to.h>
16 #include <__concepts/copyable.h>
17 #include <__concepts/derived_from.h>
18 #include <__concepts/different_from.h>
19 #include <__config>
20 #include <__fwd/get.h>
21 #include <__fwd/subrange.h>
22 #include <__iterator/advance.h>
23 #include <__iterator/concepts.h>
24 #include <__iterator/incrementable_traits.h>
25 #include <__iterator/iterator_traits.h>
26 #include <__ranges/access.h>
27 #include <__ranges/concepts.h>
28 #include <__ranges/dangling.h>
29 #include <__ranges/enable_borrowed_range.h>
30 #include <__ranges/size.h>
31 #include <__ranges/view_interface.h>
32 #include <__tuple/pair_like.h>
33 #include <__tuple/tuple_element.h>
34 #include <__tuple/tuple_size.h>
35 #include <__type_traits/conditional.h>
36 #include <__type_traits/decay.h>
37 #include <__type_traits/is_pointer.h>
38 #include <__type_traits/is_reference.h>
39 #include <__type_traits/make_unsigned.h>
40 #include <__type_traits/remove_const.h>
41 #include <__type_traits/remove_pointer.h>
42 #include <__utility/move.h>
43 #include <cstddef>
44 
45 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
46 #  pragma GCC system_header
47 #endif
48 
49 _LIBCPP_PUSH_MACROS
50 #include <__undef_macros>
51 
52 _LIBCPP_BEGIN_NAMESPACE_STD
53 
54 #if _LIBCPP_STD_VER >= 20
55 
56 namespace ranges {
57   template<class _From, class _To>
58   concept __uses_nonqualification_pointer_conversion =
59     is_pointer_v<_From> && is_pointer_v<_To> &&
60     !convertible_to<remove_pointer_t<_From>(*)[], remove_pointer_t<_To>(*)[]>;
61 
62   template<class _From, class _To>
63   concept __convertible_to_non_slicing =
64     convertible_to<_From, _To> &&
65     !__uses_nonqualification_pointer_conversion<decay_t<_From>, decay_t<_To>>;
66 
67   template<class _Pair, class _Iter, class _Sent>
68   concept __pair_like_convertible_from =
69     !range<_Pair> && __pair_like<_Pair> &&
70     constructible_from<_Pair, _Iter, _Sent> &&
71     __convertible_to_non_slicing<_Iter, tuple_element_t<0, _Pair>> &&
72     convertible_to<_Sent, tuple_element_t<1, _Pair>>;
73 
74   template<input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent = _Iter,
75            subrange_kind _Kind = sized_sentinel_for<_Sent, _Iter>
76              ? subrange_kind::sized
77              : subrange_kind::unsized>
78     requires (_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _Iter>)
79   class _LIBCPP_TEMPLATE_VIS subrange
80     : public view_interface<subrange<_Iter, _Sent, _Kind>>
81   {
82   public:
83     // Note: this is an internal implementation detail that is public only for internal usage.
84     static constexpr bool _StoreSize = (_Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _Iter>);
85 
86   private:
87     static constexpr bool _MustProvideSizeAtConstruction = !_StoreSize; // just to improve compiler diagnostics
88     struct _Empty { _LIBCPP_HIDE_FROM_ABI constexpr _Empty(auto) noexcept { } };
89     using _Size = conditional_t<_StoreSize, make_unsigned_t<iter_difference_t<_Iter>>, _Empty>;
90     _LIBCPP_NO_UNIQUE_ADDRESS _Iter __begin_ = _Iter();
91     _LIBCPP_NO_UNIQUE_ADDRESS _Sent __end_ = _Sent();
92     _LIBCPP_NO_UNIQUE_ADDRESS _Size __size_ = 0;
93 
94   public:
95     _LIBCPP_HIDE_FROM_ABI
96     subrange() requires default_initializable<_Iter> = default;
97 
98     _LIBCPP_HIDE_FROM_ABI
99     constexpr subrange(__convertible_to_non_slicing<_Iter> auto __iter, _Sent __sent)
100       requires _MustProvideSizeAtConstruction
101       : __begin_(std::move(__iter)), __end_(std::move(__sent))
102     { }
103 
104     _LIBCPP_HIDE_FROM_ABI
105     constexpr subrange(__convertible_to_non_slicing<_Iter> auto __iter, _Sent __sent,
106                        make_unsigned_t<iter_difference_t<_Iter>> __n)
107       requires (_Kind == subrange_kind::sized)
108       : __begin_(std::move(__iter)), __end_(std::move(__sent)), __size_(__n)
109     {
110       if constexpr (sized_sentinel_for<_Sent, _Iter>)
111         _LIBCPP_ASSERT_UNCATEGORIZED((__end_ - __begin_) == static_cast<iter_difference_t<_Iter>>(__n),
112           "std::ranges::subrange was passed an invalid size hint");
113     }
114 
115     template<__different_from<subrange> _Range>
116       requires borrowed_range<_Range> &&
117                __convertible_to_non_slicing<iterator_t<_Range>, _Iter> &&
118                convertible_to<sentinel_t<_Range>, _Sent>
119     _LIBCPP_HIDE_FROM_ABI
120     constexpr subrange(_Range&& __range)
121       requires (!_StoreSize)
122       : subrange(ranges::begin(__range), ranges::end(__range))
123     { }
124 
125     template<__different_from<subrange> _Range>
126       requires borrowed_range<_Range> &&
127                __convertible_to_non_slicing<iterator_t<_Range>, _Iter> &&
128                convertible_to<sentinel_t<_Range>, _Sent>
129     _LIBCPP_HIDE_FROM_ABI
130     constexpr subrange(_Range&& __range)
131       requires _StoreSize && sized_range<_Range>
132       : subrange(__range, ranges::size(__range))
133     { }
134 
135     template<borrowed_range _Range>
136       requires __convertible_to_non_slicing<iterator_t<_Range>, _Iter> &&
137                convertible_to<sentinel_t<_Range>, _Sent>
138     _LIBCPP_HIDE_FROM_ABI
139     constexpr subrange(_Range&& __range, make_unsigned_t<iter_difference_t<_Iter>> __n)
140       requires (_Kind == subrange_kind::sized)
141       : subrange(ranges::begin(__range), ranges::end(__range), __n)
142     { }
143 
144     template<__different_from<subrange> _Pair>
145       requires __pair_like_convertible_from<_Pair, const _Iter&, const _Sent&>
146     _LIBCPP_HIDE_FROM_ABI
147     constexpr operator _Pair() const {
148       return _Pair(__begin_, __end_);
149     }
150 
151     _LIBCPP_HIDE_FROM_ABI
152     constexpr _Iter begin() const requires copyable<_Iter> {
153       return __begin_;
154     }
155 
156     [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin() requires (!copyable<_Iter>) {
157       return std::move(__begin_);
158     }
159 
160     _LIBCPP_HIDE_FROM_ABI
161     constexpr _Sent end() const {
162       return __end_;
163     }
164 
165     [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool empty() const {
166       return __begin_ == __end_;
167     }
168 
169     _LIBCPP_HIDE_FROM_ABI
170     constexpr make_unsigned_t<iter_difference_t<_Iter>> size() const
171       requires (_Kind == subrange_kind::sized)
172     {
173       if constexpr (_StoreSize)
174         return __size_;
175       else
176         return std::__to_unsigned_like(__end_ - __begin_);
177     }
178 
179     [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) const&
180       requires forward_iterator<_Iter>
181     {
182       auto __tmp = *this;
183       __tmp.advance(__n);
184       return __tmp;
185     }
186 
187     [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) && {
188       advance(__n);
189       return std::move(*this);
190     }
191 
192     [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange prev(iter_difference_t<_Iter> __n = 1) const
193       requires bidirectional_iterator<_Iter>
194     {
195       auto __tmp = *this;
196       __tmp.advance(-__n);
197       return __tmp;
198     }
199 
200     _LIBCPP_HIDE_FROM_ABI
201     constexpr subrange& advance(iter_difference_t<_Iter> __n) {
202       if constexpr (bidirectional_iterator<_Iter>) {
203         if (__n < 0) {
204           ranges::advance(__begin_, __n);
205           if constexpr (_StoreSize)
206             __size_ += std::__to_unsigned_like(-__n);
207           return *this;
208         }
209       }
210 
211       auto __d = __n - ranges::advance(__begin_, __n, __end_);
212       if constexpr (_StoreSize)
213         __size_ -= std::__to_unsigned_like(__d);
214       return *this;
215     }
216   };
217 
218   template<input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
219   subrange(_Iter, _Sent) -> subrange<_Iter, _Sent>;
220 
221   template<input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
222   subrange(_Iter, _Sent, make_unsigned_t<iter_difference_t<_Iter>>)
223     -> subrange<_Iter, _Sent, subrange_kind::sized>;
224 
225   template<borrowed_range _Range>
226   subrange(_Range&&) -> subrange<iterator_t<_Range>, sentinel_t<_Range>,
227                                  (sized_range<_Range> || sized_sentinel_for<sentinel_t<_Range>, iterator_t<_Range>>)
228                                    ? subrange_kind::sized : subrange_kind::unsized>;
229 
230   template<borrowed_range _Range>
231   subrange(_Range&&, make_unsigned_t<range_difference_t<_Range>>)
232     -> subrange<iterator_t<_Range>, sentinel_t<_Range>, subrange_kind::sized>;
233 
234   template<size_t _Index, class _Iter, class _Sent, subrange_kind _Kind>
235     requires ((_Index == 0 && copyable<_Iter>) || _Index == 1)
236   _LIBCPP_HIDE_FROM_ABI
237   constexpr auto get(const subrange<_Iter, _Sent, _Kind>& __subrange) {
238     if constexpr (_Index == 0)
239       return __subrange.begin();
240     else
241       return __subrange.end();
242   }
243 
244   template<size_t _Index, class _Iter, class _Sent, subrange_kind _Kind>
245     requires (_Index < 2)
246   _LIBCPP_HIDE_FROM_ABI
247   constexpr auto get(subrange<_Iter, _Sent, _Kind>&& __subrange) {
248     if constexpr (_Index == 0)
249       return __subrange.begin();
250     else
251       return __subrange.end();
252   }
253 
254   template<class _Ip, class _Sp, subrange_kind _Kp>
255   inline constexpr bool enable_borrowed_range<subrange<_Ip, _Sp, _Kp>> = true;
256 
257   template<range _Rp>
258   using borrowed_subrange_t = _If<borrowed_range<_Rp>, subrange<iterator_t<_Rp>>, dangling>;
259 } // namespace ranges
260 
261 // [range.subrange.general]
262 
263 using ranges::get;
264 
265 // [ranges.syn]
266 
267 template<class _Ip, class _Sp, ranges::subrange_kind _Kp>
268 struct tuple_size<ranges::subrange<_Ip, _Sp, _Kp>> : integral_constant<size_t, 2> {};
269 
270 template<class _Ip, class _Sp, ranges::subrange_kind _Kp>
271 struct tuple_element<0, ranges::subrange<_Ip, _Sp, _Kp>> {
272   using type = _Ip;
273 };
274 
275 template<class _Ip, class _Sp, ranges::subrange_kind _Kp>
276 struct tuple_element<1, ranges::subrange<_Ip, _Sp, _Kp>> {
277   using type = _Sp;
278 };
279 
280 template<class _Ip, class _Sp, ranges::subrange_kind _Kp>
281 struct tuple_element<0, const ranges::subrange<_Ip, _Sp, _Kp>> {
282   using type = _Ip;
283 };
284 
285 template<class _Ip, class _Sp, ranges::subrange_kind _Kp>
286 struct tuple_element<1, const ranges::subrange<_Ip, _Sp, _Kp>> {
287   using type = _Sp;
288 };
289 
290 #endif // _LIBCPP_STD_VER >= 20
291 
292 _LIBCPP_END_NAMESPACE_STD
293 
294 _LIBCPP_POP_MACROS
295 
296 #endif // _LIBCPP___RANGES_SUBRANGE_H
297