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 <__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