libcxx/include/__ranges/subrange.h

   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 <__cstddef/size_t.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/tuple_element.h>
  33 #include <__tuple/tuple_like_no_subrange.h>
  34 #include <__tuple/tuple_size.h>
  35 #include <__type_traits/conditional.h>
  36 #include <__type_traits/decay.h>
  37 #include <__type_traits/integral_constant.h>
  38 #include <__type_traits/is_pointer.h>
  39 #include <__type_traits/is_reference.h>
  40 #include <__type_traits/make_unsigned.h>
  41 #include <__type_traits/remove_const.h>
  42 #include <__type_traits/remove_pointer.h>
  43 #include <__utility/move.h>
  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> && !__uses_nonqualification_pointer_conversion<decay_t<_From>, decay_t<_To>>;
  65
  66 template <class _Pair, class _Iter, class _Sent>
  67 concept __pair_like_convertible_from =
  68     !range<_Pair> && __pair_like_no_subrange<_Pair> && constructible_from<_Pair, _Iter, _Sent> &&
  69     __convertible_to_non_slicing<_Iter, tuple_element_t<0, _Pair>> && convertible_to<_Sent, tuple_element_t<1, _Pair>>;
  70
  71 template <input_or_output_iterator _Iter,
  72           sentinel_for<_Iter> _Sent = _Iter,
  73           subrange_kind _Kind       = sized_sentinel_for<_Sent, _Iter> ? subrange_kind::sized : subrange_kind::unsized>
  74   requires(_Kind == subrange_kind::sized || !sized_sentinel_for<_Sent, _Iter>)
  75 class _LIBCPP_TEMPLATE_VIS subrange : public view_interface<subrange<_Iter, _Sent, _Kind>> {
  76 public:
  77   // Note: this is an internal implementation detail that is public only for internal usage.
  78   static constexpr bool _StoreSize = (_Kind == subrange_kind::sized && !sized_sentinel_for<_Sent, _Iter>);
  79
  80 private:
  81   static constexpr bool _MustProvideSizeAtConstruction = !_StoreSize; // just to improve compiler diagnostics
  82   struct _Empty {
  83     _LIBCPP_HIDE_FROM_ABI constexpr _Empty(auto) noexcept {}
  84   };
  85   using _Size = conditional_t<_StoreSize, make_unsigned_t<iter_difference_t<_Iter>>, _Empty>;
  86   _LIBCPP_NO_UNIQUE_ADDRESS _Iter __begin_ = _Iter();
  87   _LIBCPP_NO_UNIQUE_ADDRESS _Sent __end_   = _Sent();
  88   _LIBCPP_NO_UNIQUE_ADDRESS _Size __size_  = 0;
  89
  90 public:
  91   _LIBCPP_HIDE_FROM_ABI subrange()
  92     requires default_initializable<_Iter>
  93   = default;
  94
  95   _LIBCPP_HIDE_FROM_ABI constexpr subrange(__convertible_to_non_slicing<_Iter> auto __iter, _Sent __sent)
  96     requires _MustProvideSizeAtConstruction
  97       : __begin_(std::move(__iter)), __end_(std::move(__sent)) {}
  98
  99   _LIBCPP_HIDE_FROM_ABI constexpr subrange(
 100       __convertible_to_non_slicing<_Iter> auto __iter, _Sent __sent, make_unsigned_t<iter_difference_t<_Iter>> __n)
 101     requires(_Kind == subrange_kind::sized)
 102       : __begin_(std::move(__iter)), __end_(std::move(__sent)), __size_(__n) {
 103     if constexpr (sized_sentinel_for<_Sent, _Iter>)
 104       _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS((__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> && __convertible_to_non_slicing<iterator_t<_Range>, _Iter> &&
 110              convertible_to<sentinel_t<_Range>, _Sent>
 111              _LIBCPP_HIDE_FROM_ABI constexpr subrange(_Range&& __range)
 112                requires(!_StoreSize)
 113       : subrange(ranges::begin(__range), ranges::end(__range)) {}
 114
 115   template <__different_from<subrange> _Range>
 116     requires borrowed_range<_Range> && __convertible_to_non_slicing<iterator_t<_Range>, _Iter> &&
 117              convertible_to<sentinel_t<_Range>, _Sent>
 118              _LIBCPP_HIDE_FROM_ABI constexpr subrange(_Range&& __range)
 119                requires _StoreSize && sized_range<_Range>
 120       : subrange(__range, ranges::size(__range)) {}
 121
 122   template <borrowed_range _Range>
 123     requires __convertible_to_non_slicing<iterator_t<_Range>, _Iter> &&
 124              convertible_to<sentinel_t<_Range>, _Sent>
 125              _LIBCPP_HIDE_FROM_ABI constexpr subrange(_Range&& __range, make_unsigned_t<iter_difference_t<_Iter>> __n)
 126                requires(_Kind == subrange_kind::sized)
 127       : subrange(ranges::begin(__range), ranges::end(__range), __n) {}
 128
 129   template <__pair_like_convertible_from<const _Iter&, const _Sent&> _Pair>
 130   _LIBCPP_HIDE_FROM_ABI constexpr operator _Pair() const {
 131     return _Pair(__begin_, __end_);
 132   }
 133
 134   _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin() const
 135     requires copyable<_Iter>
 136   {
 137     return __begin_;
 138   }
 139
 140   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Iter begin()
 141     requires(!copyable<_Iter>)
 142   {
 143     return std::move(__begin_);
 144   }
 145
 146   _LIBCPP_HIDE_FROM_ABI constexpr _Sent end() const { return __end_; }
 147
 148   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr bool empty() const { return __begin_ == __end_; }
 149
 150   _LIBCPP_HIDE_FROM_ABI constexpr make_unsigned_t<iter_difference_t<_Iter>> size() const
 151     requires(_Kind == subrange_kind::sized)
 152   {
 153     if constexpr (_StoreSize)
 154       return __size_;
 155     else
 156       return std::__to_unsigned_like(__end_ - __begin_);
 157   }
 158
 159   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) const&
 160     requires forward_iterator<_Iter>
 161   {
 162     auto __tmp = *this;
 163     __tmp.advance(__n);
 164     return __tmp;
 165   }
 166
 167   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange next(iter_difference_t<_Iter> __n = 1) && {
 168     advance(__n);
 169     return std::move(*this);
 170   }
 171
 172   [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr subrange prev(iter_difference_t<_Iter> __n = 1) const
 173     requires bidirectional_iterator<_Iter>
 174   {
 175     auto __tmp = *this;
 176     __tmp.advance(-__n);
 177     return __tmp;
 178   }
 179
 180   _LIBCPP_HIDE_FROM_ABI constexpr subrange& advance(iter_difference_t<_Iter> __n) {
 181     if constexpr (bidirectional_iterator<_Iter>) {
 182       if (__n < 0) {
 183         ranges::advance(__begin_, __n);
 184         if constexpr (_StoreSize)
 185           __size_ += std::__to_unsigned_like(-__n);
 186         return *this;
 187       }
 188     }
 189
 190     auto __d = __n - ranges::advance(__begin_, __n, __end_);
 191     if constexpr (_StoreSize)
 192       __size_ -= std::__to_unsigned_like(__d);
 193     return *this;
 194   }
 195 };
 196
 197 template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
 198 subrange(_Iter, _Sent) -> subrange<_Iter, _Sent>;
 199
 200 template <input_or_output_iterator _Iter, sentinel_for<_Iter> _Sent>
 201 subrange(_Iter, _Sent, make_unsigned_t<iter_difference_t<_Iter>>) -> subrange<_Iter, _Sent, subrange_kind::sized>;
 202
 203 template <borrowed_range _Range>
 204 subrange(_Range&&) -> subrange<iterator_t<_Range>,
 205                                sentinel_t<_Range>,
 206                                (sized_range<_Range> || sized_sentinel_for<sentinel_t<_Range>, iterator_t<_Range>>)
 207                                    ? subrange_kind::sized
 208                                    : subrange_kind::unsized>;
 209
 210 template <borrowed_range _Range>
 211 subrange(_Range&&, make_unsigned_t<range_difference_t<_Range>>)
 212     -> subrange<iterator_t<_Range>, sentinel_t<_Range>, subrange_kind::sized>;
 213
 214 template <size_t _Index, class _Iter, class _Sent, subrange_kind _Kind>
 215   requires((_Index == 0 && copyable<_Iter>) || _Index == 1)
 216 _LIBCPP_HIDE_FROM_ABI constexpr auto get(const subrange<_Iter, _Sent, _Kind>& __subrange) {
 217   if constexpr (_Index == 0)
 218     return __subrange.begin();
 219   else
 220     return __subrange.end();
 221 }
 222
 223 template <size_t _Index, class _Iter, class _Sent, subrange_kind _Kind>
 224   requires(_Index < 2)
 225 _LIBCPP_HIDE_FROM_ABI constexpr auto get(subrange<_Iter, _Sent, _Kind>&& __subrange) {
 226   if constexpr (_Index == 0)
 227     return __subrange.begin();
 228   else
 229     return __subrange.end();
 230 }
 231
 232 template <class _Ip, class _Sp, subrange_kind _Kp>
 233 inline constexpr bool enable_borrowed_range<subrange<_Ip, _Sp, _Kp>> = true;
 234
 235 template <range _Rp>
 236 using borrowed_subrange_t = _If<borrowed_range<_Rp>, subrange<iterator_t<_Rp>>, dangling>;
 237 } // namespace ranges
 238
 239 // [range.subrange.general]
 240
 241 using ranges::get;
 242
 243 // [ranges.syn]
 244
 245 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
 246 struct tuple_size<ranges::subrange<_Ip, _Sp, _Kp>> : integral_constant<size_t, 2> {};
 247
 248 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
 249 struct tuple_element<0, ranges::subrange<_Ip, _Sp, _Kp>> {
 250   using type = _Ip;
 251 };
 252
 253 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
 254 struct tuple_element<1, ranges::subrange<_Ip, _Sp, _Kp>> {
 255   using type = _Sp;
 256 };
 257
 258 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
 259 struct tuple_element<0, const ranges::subrange<_Ip, _Sp, _Kp>> {
 260   using type = _Ip;
 261 };
 262
 263 template <class _Ip, class _Sp, ranges::subrange_kind _Kp>
 264 struct tuple_element<1, const ranges::subrange<_Ip, _Sp, _Kp>> {
 265   using type = _Sp;
 266 };
 267
 268 #endif // _LIBCPP_STD_VER >= 20
 269
 270 _LIBCPP_END_NAMESPACE_STD
 271
 272 _LIBCPP_POP_MACROS
 273
 274 #endif // _LIBCPP___RANGES_SUBRANGE_H