Horizon
any_view.hpp
Go to the documentation of this file.
1 // Range v3 library
3 //
4 // Copyright Eric Niebler 2014-present
5 // Copyright Casey Carter 2017
6 //
7 // Use, modification and distribution is subject to the
8 // Boost Software License, Version 1.0. (See accompanying
9 // file LICENSE_1_0.txt or copy at
10 // http://www.boost.org/LICENSE_1_0.txt)
11 //
12 // Project home: https://github.com/ericniebler/range-v3
13 //
14 
15 #ifndef RANGES_V3_VIEW_ANY_VIEW_HPP
16 #define RANGES_V3_VIEW_ANY_VIEW_HPP
17 
18 #include <type_traits>
19 #include <typeinfo>
20 #include <utility>
21 
22 #include <range/v3/range_fwd.hpp>
23 
28 #include <range/v3/utility/addressof.hpp>
30 #include <range/v3/view/all.hpp>
31 #include <range/v3/view/facade.hpp>
32 
33 #include <range/v3/detail/prologue.hpp>
34 
35 RANGES_DIAGNOSTIC_PUSH
36 RANGES_DIAGNOSTIC_IGNORE_INCONSISTENT_OVERRIDE
37 RANGES_DIAGNOSTIC_SUGGEST_OVERRIDE
38 
39 namespace ranges
40 {
43  enum class category
44  {
45  none = 0,
46  input = 1,
47  forward = 3,
48  bidirectional = 7,
49  random_access = 15,
52  sized = 16,
53  };
54 
59  constexpr category operator&(category lhs, category rhs) noexcept
60  {
61  return static_cast<category>(
62  static_cast<meta::_t<std::underlying_type<category>>>(lhs) &
63  static_cast<meta::_t<std::underlying_type<category>>>(rhs));
64  }
65 
66  constexpr category operator|(category lhs, category rhs) noexcept
67  {
68  return static_cast<category>(
69  static_cast<meta::_t<std::underlying_type<category>>>(lhs) |
70  static_cast<meta::_t<std::underlying_type<category>>>(rhs));
71  }
72 
73  constexpr category operator^(category lhs, category rhs) noexcept
74  {
75  return static_cast<category>(
76  static_cast<meta::_t<std::underlying_type<category>>>(lhs) ^
77  static_cast<meta::_t<std::underlying_type<category>>>(rhs));
78  }
79 
80  constexpr category operator~(category lhs) noexcept
81  {
82  return static_cast<category>(
83  ~static_cast<meta::_t<std::underlying_type<category>>>(lhs));
84  }
85 
86  constexpr category & operator&=(category & lhs, category rhs) noexcept
87  {
88  return (lhs = lhs & rhs);
89  }
90 
91  constexpr category & operator|=(category & lhs, category rhs) noexcept
92  {
93  return (lhs = lhs | rhs);
94  }
95 
96  constexpr category & operator^=(category & lhs, category rhs) noexcept
97  {
98  return (lhs = lhs ^ rhs);
99  }
101 
104  template<typename Rng>
105  constexpr category get_categories() noexcept
106  {
107  return (input_range<Rng> ? category::input : category::none) |
108  (forward_range<Rng> ? category::forward : category::none) |
109  (bidirectional_range<Rng> ? category::bidirectional : category::none) |
110  (random_access_range<Rng> ? category::random_access : category::none) |
111  (sized_range<Rng> ? category::sized : category::none);
112  }
113 
115  namespace detail
116  {
117  // workaround the fact that typeid ignores cv-qualifiers
118  template<typename>
119  struct rtti_tag
120  {};
121 
122  struct any_ref
123  {
124  any_ref() = default;
125  template<typename T>
126  constexpr any_ref(T & obj) noexcept
127  : obj_(detail::addressof(obj))
128 #ifndef NDEBUG
129  , info_(&typeid(rtti_tag<T>))
130 #endif
131  {}
132  template<typename T>
133  T & get() const noexcept
134  {
135  RANGES_ASSERT(obj_ && info_ && *info_ == typeid(rtti_tag<T>));
136  return *const_cast<T *>(static_cast<T const volatile *>(obj_));
137  }
138 
139  private:
140  void const volatile * obj_ = nullptr;
141 #ifndef NDEBUG
142  std::type_info const * info_ = nullptr;
143 #endif
144  };
145 
146  template<typename Base>
147  struct cloneable : Base
148  {
149  using Base::Base;
150  virtual ~cloneable() override = default;
151  cloneable() = default;
152  cloneable(cloneable const &) = delete;
153  cloneable & operator=(cloneable const &) = delete;
154  virtual std::unique_ptr<cloneable> clone() const = 0;
155  };
156 
157  // clang-format off
160  template(typename Rng, typename Ref)(
161  concept (any_compatible_range_)(Rng, Ref),
162  convertible_to<range_reference_t<Rng>, Ref>
163  );
166  template<typename Rng, typename Ref>
167  CPP_concept any_compatible_range =
168  CPP_concept_ref(detail::any_compatible_range_, Rng, Ref);
169  // clang-format on
170 
171  template<typename Rng, typename = void>
172  struct any_view_sentinel_impl
173  : private box<sentinel_t<Rng>, any_view_sentinel_impl<Rng>>
174  {
175  private:
176  using box_t = typename any_view_sentinel_impl::box;
177 
178  public:
179  any_view_sentinel_impl() = default;
180  any_view_sentinel_impl(Rng & rng)
181  : box_t(ranges::end(rng))
182  {}
183  void init(Rng & rng) noexcept
184  {
185  box_t::get() = ranges::end(rng);
186  }
187  sentinel_t<Rng> const & get(Rng &) const noexcept
188  {
189  return box_t::get();
190  }
191  };
192 
193  template<typename Rng>
194  struct any_view_sentinel_impl<
195  Rng, meta::void_<decltype(ranges::end(std::declval<Rng const &>()))>>
196  {
197  any_view_sentinel_impl() = default;
198  any_view_sentinel_impl(Rng &) noexcept
199  {}
200  void init(Rng &) noexcept
201  {}
202  sentinel_t<Rng> get(Rng & rng) const noexcept
203  {
204  return ranges::end(rng);
205  }
206  };
207 
208  template<typename Ref, bool Sized = false>
209  struct any_input_view_interface
210  {
211  virtual ~any_input_view_interface() = default;
212  virtual void init() = 0;
213  virtual bool done() = 0;
214  virtual Ref read() const = 0;
215  virtual void next() = 0;
216  };
217  template<typename Ref>
218  struct any_input_view_interface<Ref, true> : any_input_view_interface<Ref, false>
219  {
220  virtual std::size_t size() = 0;
221  };
222 
223  template<typename Ref>
224  struct any_input_cursor
225  {
226  using single_pass = std::true_type;
227 
228  any_input_cursor() = default;
229  constexpr any_input_cursor(any_input_view_interface<Ref> & view) noexcept
230  : view_{detail::addressof(view)}
231  {}
232  Ref read() const
233  {
234  return view_->read();
235  }
236  void next()
237  {
238  view_->next();
239  }
240  bool equal(any_input_cursor const &) const noexcept
241  {
242  return true;
243  }
244  bool equal(default_sentinel_t) const
245  {
246  return !view_ || view_->done();
247  }
248 
249  private:
250  any_input_view_interface<Ref> * view_ = nullptr;
251  };
252 
253  template<typename Rng, typename Ref, bool Sized = false>
254  struct RANGES_EMPTY_BASES any_input_view_impl
255  : any_input_view_interface<Ref, Sized>
256  , private any_view_sentinel_impl<Rng>
257  {
258  CPP_assert(any_compatible_range<Rng, Ref>);
259  CPP_assert(!Sized || (bool)sized_range<Rng>);
260 
261  explicit any_input_view_impl(Rng rng)
262  : rng_{std::move(rng)}
263  {}
264  any_input_view_impl(any_input_view_impl const &) = delete;
265  any_input_view_impl & operator=(any_input_view_impl const &) = delete;
266 
267  private:
268  using sentinel_box_t = any_view_sentinel_impl<Rng>;
269 
270  virtual void init() override
271  {
272  sentinel_box_t::init(rng_);
273  current_ = ranges::begin(rng_);
274  }
275  virtual bool done() override
276  {
277  return current_ == sentinel_box_t::get(rng_);
278  }
279  virtual Ref read() const override
280  {
281  return *current_;
282  }
283  virtual void next() override
284  {
285  ++current_;
286  }
287  std::size_t size() // override-ish
288  {
289  return static_cast<std::size_t>(ranges::size(rng_));
290  }
291 
292  RANGES_NO_UNIQUE_ADDRESS Rng rng_;
293  RANGES_NO_UNIQUE_ADDRESS iterator_t<Rng> current_{};
294  };
295 
296  template<typename Ref, category Cat = category::forward, typename enable = void>
297  struct any_cursor_interface;
298 
299  template<typename Ref, category Cat>
300  struct any_cursor_interface<
301  Ref, Cat, meta::if_c<(Cat & category::mask) == category::forward>>
302  {
303  virtual ~any_cursor_interface() = default;
304  virtual any_ref iter()
305  const = 0; // returns a const ref to the cursor's wrapped iterator
306  virtual Ref read() const = 0;
307  virtual bool equal(any_cursor_interface const &) const = 0;
308  virtual void next() = 0;
309  };
310 
311  template<typename Ref, category Cat>
312  struct any_cursor_interface<
313  Ref, Cat, meta::if_c<(Cat & category::mask) == category::bidirectional>>
314  : any_cursor_interface<Ref, (Cat & ~category::mask) | category::forward>
315  {
316  virtual void prev() = 0;
317  };
318 
319  template<typename Ref, category Cat>
320  struct any_cursor_interface<
321  Ref, Cat, meta::if_c<(Cat & category::mask) == category::random_access>>
322  : any_cursor_interface<Ref, (Cat & ~category::mask) | category::bidirectional>
323  {
324  virtual void advance(std::ptrdiff_t) = 0;
325  virtual std::ptrdiff_t distance_to(any_cursor_interface const &) const = 0;
326  };
327 
328  template<typename Ref, category Cat>
329  using any_cloneable_cursor_interface = cloneable<any_cursor_interface<Ref, Cat>>;
330 
331  template<typename I, typename Ref, category Cat>
332  struct any_cursor_impl : any_cloneable_cursor_interface<Ref, Cat>
333  {
334  CPP_assert(convertible_to<iter_reference_t<I>, Ref>);
335  CPP_assert((Cat & category::forward) == category::forward);
336 
337  any_cursor_impl() = default;
338  any_cursor_impl(I it)
339  : it_{std::move(it)}
340  {}
341 
342  private:
343  using Forward =
344  any_cursor_interface<Ref, (Cat & ~category::mask) | category::forward>;
345 
346  I it_;
347 
348  any_ref iter() const override
349  {
350  return it_;
351  }
352  Ref read() const override
353  {
354  return *it_;
355  }
356  bool equal(Forward const & that_) const override
357  {
358  auto & that = polymorphic_downcast<any_cursor_impl const &>(that_);
359  return that.it_ == it_;
360  }
361  void next() override
362  {
363  ++it_;
364  }
365  std::unique_ptr<any_cloneable_cursor_interface<Ref, Cat>> clone()
366  const override
367  {
368  return detail::make_unique<any_cursor_impl>(it_);
369  }
370  void prev() // override (sometimes; it's complicated)
371  {
372  --it_;
373  }
374  void advance(std::ptrdiff_t n) // override-ish
375  {
376  it_ += n;
377  }
378  std::ptrdiff_t distance_to(
379  any_cursor_interface<Ref, Cat> const & that_) const // override-ish
380  {
381  auto & that = polymorphic_downcast<any_cursor_impl const &>(that_);
382  return static_cast<std::ptrdiff_t>(that.it_ - it_);
383  }
384  };
385 
386  struct fully_erased_view
387  {
388  virtual bool at_end(
389  any_ref) = 0; // any_ref is a const ref to a wrapped iterator
390  // to be compared to the erased view's last sentinel
391  protected:
392  ~fully_erased_view() = default;
393  };
394 
395  struct any_sentinel
396  {
397  any_sentinel() = default;
398  constexpr explicit any_sentinel(fully_erased_view & view) noexcept
399  : view_{&view}
400  {}
401 
402  private:
403  template<typename, category>
404  friend struct any_cursor;
405 
406  fully_erased_view * view_ = nullptr;
407  };
408 
409  template<typename Ref, category Cat>
410  struct any_cursor
411  {
412  private:
413  CPP_assert((Cat & category::forward) == category::forward);
414 
415  std::unique_ptr<any_cloneable_cursor_interface<Ref, Cat>> ptr_;
416 
417  template<typename Rng>
418  using impl_t = any_cursor_impl<iterator_t<Rng>, Ref, Cat>;
419 
420  public:
421  any_cursor() = default;
422  template(typename Rng)(
423  requires (!same_as<detail::decay_t<Rng>, any_cursor>) AND
424  forward_range<Rng> AND
425  any_compatible_range<Rng, Ref>)
426  explicit any_cursor(Rng && rng)
427  : ptr_{detail::make_unique<impl_t<Rng>>(begin(rng))}
428  {}
429  any_cursor(any_cursor &&) = default;
430  any_cursor(any_cursor const & that)
431  : ptr_{that.ptr_ ? that.ptr_->clone() : nullptr}
432  {}
433  any_cursor & operator=(any_cursor &&) = default;
434  any_cursor & operator=(any_cursor const & that)
435  {
436  ptr_ = (that.ptr_ ? that.ptr_->clone() : nullptr);
437  return *this;
438  }
439  Ref read() const
440  {
441  RANGES_EXPECT(ptr_);
442  return ptr_->read();
443  }
444  bool equal(any_cursor const & that) const
445  {
446  RANGES_EXPECT(!ptr_ == !that.ptr_);
447  return !ptr_ || ptr_->equal(*that.ptr_);
448  }
449  bool equal(any_sentinel const & that) const
450  {
451  RANGES_EXPECT(!ptr_ == !that.view_);
452  return !ptr_ || that.view_->at_end(ptr_->iter());
453  }
454  void next()
455  {
456  RANGES_EXPECT(ptr_);
457  ptr_->next();
458  }
459  CPP_member
460  auto prev() //
461  -> CPP_ret(void)(
462  requires (category::bidirectional == (Cat & category::bidirectional)))
463  {
464  RANGES_EXPECT(ptr_);
465  ptr_->prev();
466  }
467  CPP_member
468  auto advance(std::ptrdiff_t n) //
469  -> CPP_ret(void)(
470  requires (category::random_access == (Cat & category::random_access)))
471  {
472  RANGES_EXPECT(ptr_);
473  ptr_->advance(n);
474  }
475  CPP_member
476  auto distance_to(any_cursor const & that) const //
477  -> CPP_ret(std::ptrdiff_t)(
478  requires (category::random_access == (Cat & category::random_access)))
479  {
480  RANGES_EXPECT(!ptr_ == !that.ptr_);
481  return !ptr_ ? 0 : ptr_->distance_to(*that.ptr_);
482  }
483  };
484 
485  template<typename Ref, category Cat,
486  bool = (Cat & category::sized) == category::sized>
487  struct any_view_interface : fully_erased_view
488  {
489  CPP_assert((Cat & category::forward) == category::forward);
490 
491  virtual ~any_view_interface() = default;
492  virtual any_cursor<Ref, Cat> begin_cursor() = 0;
493  };
494  template<typename Ref, category Cat>
495  struct any_view_interface<Ref, Cat, true> : any_view_interface<Ref, Cat, false>
496  {
497  virtual std::size_t size() = 0;
498  };
499 
500  template<typename Ref, category Cat>
501  using any_cloneable_view_interface = cloneable<any_view_interface<Ref, Cat>>;
502 
503  template<typename Rng, typename Ref, category Cat>
504  struct RANGES_EMPTY_BASES any_view_impl
505  : any_cloneable_view_interface<Ref, Cat>
506  , private box<Rng, any_view_impl<Rng, Ref, Cat>>
507  , private any_view_sentinel_impl<Rng>
508  {
509  CPP_assert((Cat & category::forward) == category::forward);
510  CPP_assert(any_compatible_range<Rng, Ref>);
511  CPP_assert((Cat & category::sized) == category::none ||
512  (bool)sized_range<Rng>);
513 
514  any_view_impl() = default;
515  any_view_impl(Rng rng)
516  : range_box_t{std::move(rng)}
517  , sentinel_box_t{range_box_t::get()}
518  // NB: initialization order dependence
519  {}
520 
521  private:
522  using range_box_t = box<Rng, any_view_impl>;
523  using sentinel_box_t = any_view_sentinel_impl<Rng>;
524 
525  any_cursor<Ref, Cat> begin_cursor() override
526  {
527  return any_cursor<Ref, Cat>{range_box_t::get()};
528  }
529  bool at_end(any_ref it_) override
530  {
531  auto & it = it_.get<iterator_t<Rng> const>();
532  return it == sentinel_box_t::get(range_box_t::get());
533  }
534  std::unique_ptr<any_cloneable_view_interface<Ref, Cat>> clone() const override
535  {
536  return detail::make_unique<any_view_impl>(range_box_t::get());
537  }
538  std::size_t size() // override-ish
539  {
540  return static_cast<std::size_t>(ranges::size(range_box_t::get()));
541  }
542  };
543  } // namespace detail
545 
548  template<typename Ref, category Cat = category::input, typename enable = void>
549  struct any_view
550  : view_facade<any_view<Ref, Cat>,
551  (Cat & category::sized) == category::sized ? finite : unknown>
552  {
553  friend range_access;
554  CPP_assert((Cat & category::forward) == category::forward);
555 
556  any_view() = default;
557  template(typename Rng)(
558  requires //
559  (!same_as<detail::decay_t<Rng>, any_view>) AND
560  input_range<Rng> AND
561  detail::any_compatible_range<Rng, Ref>)
562  any_view(Rng && rng)
563  : any_view(static_cast<Rng &&>(rng),
564  meta::bool_<(get_categories<Rng>() & Cat) == Cat>{})
565  {}
566  any_view(any_view &&) = default;
567  any_view(any_view const & that)
568  : ptr_{that.ptr_ ? that.ptr_->clone() : nullptr}
569  {}
570  any_view & operator=(any_view &&) = default;
571  any_view & operator=(any_view const & that)
572  {
573  ptr_ = (that.ptr_ ? that.ptr_->clone() : nullptr);
574  return *this;
575  }
576 
577  CPP_member
578  auto size() //
579  -> CPP_ret(std::size_t)(
580  requires (category::sized == (Cat & category::sized)))
581  {
582  return ptr_ ? ptr_->size() : 0;
583  }
584 
585  private:
586  template<typename Rng>
587  using impl_t = detail::any_view_impl<views::all_t<Rng>, Ref, Cat>;
588  template<typename Rng>
589  any_view(Rng && rng, std::true_type)
590  : ptr_{detail::make_unique<impl_t<Rng>>(views::all(static_cast<Rng &&>(rng)))}
591  {}
592  template<typename Rng>
593  any_view(Rng &&, std::false_type)
594  {
595  static_assert(
596  (get_categories<Rng>() & Cat) == Cat,
597  "The range passed to any_view() does not model the requested category");
598  }
599 
600  detail::any_cursor<Ref, Cat> begin_cursor()
601  {
602  return ptr_ ? ptr_->begin_cursor() : detail::value_init{};
603  }
604  detail::any_sentinel end_cursor() noexcept
605  {
606  return detail::any_sentinel{*ptr_};
607  }
608 
609  std::unique_ptr<detail::any_cloneable_view_interface<Ref, Cat>> ptr_;
610  };
611 
612  // input and not forward
613  template<typename Ref, category Cat>
614  struct any_view<Ref, Cat, meta::if_c<(Cat & category::forward) == category::input>>
615  : view_facade<any_view<Ref, Cat, void>,
616  (Cat & category::sized) == category::sized ? finite : unknown>
617  {
618  friend range_access;
619 
620  any_view() = default;
621  template(typename Rng)(
622  requires //
623  (!same_as<detail::decay_t<Rng>, any_view>) AND
624  input_range<Rng> AND
625  detail::any_compatible_range<Rng, Ref>)
626  any_view(Rng && rng)
627  : ptr_{std::make_shared<impl_t<Rng>>(views::all(static_cast<Rng &&>(rng)))}
628  {}
629 
630  CPP_member
631  auto size() //
632  -> CPP_ret(std::size_t)(
633  requires (category::sized == (Cat & category::sized)))
634  {
635  return ptr_ ? ptr_->size() : 0;
636  }
637 
638  private:
639  template<typename Rng>
640  using impl_t =
641  detail::any_input_view_impl<views::all_t<Rng>, Ref,
642  (Cat & category::sized) == category::sized>;
643 
644  detail::any_input_cursor<Ref> begin_cursor()
645  {
646  if(!ptr_)
647  return {};
648 
649  ptr_->init();
650  return detail::any_input_cursor<Ref>{*ptr_};
651  }
652 
653  std::shared_ptr<detail::any_input_view_interface<Ref, (Cat & category::sized) ==
654  category::sized>>
655  ptr_;
656  };
657 
658 #if RANGES_CXX_DEDUCTION_GUIDES >= RANGES_CXX_DEDUCTION_GUIDES_17
659  template(typename Rng)(
660  requires view_<Rng>)
661  any_view(Rng &&)
662  ->any_view<range_reference_t<Rng>, get_categories<Rng>()>;
663 #endif
664 
665  template<typename Ref>
666  using any_input_view RANGES_DEPRECATED(
667  "Use any_view<Ref, category::input> instead.") = any_view<Ref, category::input>;
668 
669  template<typename Ref>
670  using any_forward_view RANGES_DEPRECATED(
671  "Use any_view<Ref, category::forward> instead.") =
673 
674  template<typename Ref>
675  using any_bidirectional_view RANGES_DEPRECATED(
676  "Use any_view<Ref, category::bidirectional> instead.") =
678 
679  template<typename Ref>
680  using any_random_access_view RANGES_DEPRECATED(
681  "Use any_view<Ref, category::random_access> instead.") =
683 } // namespace ranges
684 
685 #include <range/v3/detail/satisfy_boost_range.hpp>
686 RANGES_SATISFY_BOOST_RANGE(::ranges::any_view)
687 
688 RANGES_DIAGNOSTIC_POP
689 
690 #include <range/v3/detail/epilogue.hpp>
691 
692 #endif
category
An enum that denotes the supported subset of range concepts supported by a range.
Definition: any_view.hpp:44
@ sized
satisfies ranges::concepts::sized_range
@ random_access
satisfies ranges::concepts::random_access_range
@ none
No concepts met.
@ forward
satisfies ranges::concepts::forward_range
@ input
satisfies ranges::concepts::input_range
@ bidirectional
satisfies ranges::concepts::bidirectional_range
@ mask
Mask away any properties other than iterator category.
CPP_concept view_
\concept view_
Definition: concepts.hpp:252
std::integral_constant< bool, B > bool_
An integral constant wrapper for bool.
Definition: meta.hpp:168
std::integral_constant< std::size_t, N > size_t
An integral constant wrapper for std::size_t.
Definition: meta.hpp:163
typename T::type _t
Type alias for T::type.
Definition: meta.hpp:141
meta::size_t< L::size()> size
An integral constant wrapper that is the size of the meta::list L.
Definition: meta.hpp:1696
void void_
An alias for void.
Definition: meta.hpp:597
Tiny metaprogramming library.
Definition: meta.hpp:116
A type-erased view.
Definition: any_view.hpp:552
A utility for constructing a view from a (derived) type that implements begin and end cursors.
Definition: facade.hpp:66