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