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