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