hana/experimental/view.hpp

0001 /*
0002 @file
0003 Defines experimental views.
0004
0005 Copyright Louis Dionne 2013-2022
0006 Distributed under the Boost Software License, Version 1.0.
0007 (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
0008  */
0009
0010 #ifndef BOOST_HANA_EXPERIMENTAL_VIEW_HPP
0011 #define BOOST_HANA_EXPERIMENTAL_VIEW_HPP
0012
0013 #include <boost/hana/and.hpp>
0014 #include <boost/hana/at.hpp>
0015 #include <boost/hana/bool.hpp>
0016 #include <boost/hana/detail/decay.hpp>
0017 #include <boost/hana/fold_left.hpp>
0018 #include <boost/hana/functional/compose.hpp>
0019 #include <boost/hana/functional/on.hpp>
0020 #include <boost/hana/fwd/ap.hpp>
0021 #include <boost/hana/fwd/concat.hpp>
0022 #include <boost/hana/fwd/drop_front.hpp>
0023 #include <boost/hana/fwd/empty.hpp>
0024 #include <boost/hana/fwd/equal.hpp>
0025 #include <boost/hana/fwd/flatten.hpp>
0026 #include <boost/hana/fwd/is_empty.hpp>
0027 #include <boost/hana/fwd/less.hpp>
0028 #include <boost/hana/fwd/lift.hpp>
0029 #include <boost/hana/fwd/transform.hpp>
0030 #include <boost/hana/integral_constant.hpp>
0031 #include <boost/hana/length.hpp>
0032 #include <boost/hana/lexicographical_compare.hpp>
0033 #include <boost/hana/range.hpp>
0034 #include <boost/hana/tuple.hpp>
0035 #include <boost/hana/unpack.hpp>
0036
0037 #include <cstddef>
0038 #include <type_traits>
0039 #include <utility>
0040
0041
0042 // Pros of views
0043 //     - No temporary container created between algorithms
0044 //     - Lazy, so only the minimum is required
0045 //
0046 // Cons of views
0047 //     - Reference semantics mean possibility for dangling references
0048 //     - Lose the ability to move from temporary containers
0049 //     - When fetching the members of a view multiple times, no caching is done.
0050 //       So for example, `t = transform(xs, f); at_c<0>(t); at_c<0>(t)` will
0051 //       compute `f(at_c<0>(xs))` twice.
0052 //     - push_back creates a joint_view and a single_view. The single_view holds
0053 //       the value as a member. When doing multiple push_backs, we end up with a
0054 //         joint_view<xxx, joint_view<single_view<T>, joint_view<single_view<T>, ....>>>
0055 //       which contains a reference to `xxx` and all the `T`s by value. Such a
0056 //       "view" is not cheap to copy, which is inconsistent with the usual
0057 //       expectations about views.
0058
0059 namespace boost { namespace hana {
0060
0061 namespace experimental {
0062     struct view_tag;
0063
0064     namespace detail {
0065         template <typename Sequence>
0066         struct is_view {
0067             static constexpr bool value = false;
0068         };
0069
0070         template <typename Sequence>
0071         using view_storage = typename std::conditional<
0072             detail::is_view<Sequence>::value, Sequence, Sequence&
0073         >::type;
0074     }
0075
0076     //////////////////////////////////////////////////////////////////////////
0077     // sliced_view
0078     //////////////////////////////////////////////////////////////////////////
0079     template <typename Sequence, std::size_t ...indices>
0080     struct sliced_view_t {
0081         detail::view_storage<Sequence> sequence_;
0082         using hana_tag = view_tag;
0083     };
0084
0085     template <typename Sequence, typename Indices>
0086     constexpr auto sliced(Sequence& sequence, Indices const& indices) {
0087         return hana::unpack(indices, [&](auto ...i) {
0088             return sliced_view_t<Sequence, decltype(i)::value...>{sequence};
0089         });
0090     }
0091
0092     namespace detail {
0093         template <typename Sequence, std::size_t ...i>
0094         struct is_view<sliced_view_t<Sequence, i...>> {
0095             static constexpr bool value = true;
0096         };
0097     }
0098
0099     //////////////////////////////////////////////////////////////////////////
0100     // transformed_view
0101     //////////////////////////////////////////////////////////////////////////
0102     template <typename Sequence, typename F>
0103     struct transformed_view_t {
0104         detail::view_storage<Sequence> sequence_;
0105         F f_;
0106         using hana_tag = view_tag;
0107     };
0108
0109     template <typename Sequence, typename F>
0110     constexpr transformed_view_t<Sequence, typename hana::detail::decay<F>::type>
0111     transformed(Sequence& sequence, F&& f) {
0112         return {sequence, static_cast<F&&>(f)};
0113     }
0114
0115     namespace detail {
0116         template <typename Sequence, typename F>
0117         struct is_view<transformed_view_t<Sequence, F>> {
0118             static constexpr bool value = true;
0119         };
0120     }
0121
0122     //////////////////////////////////////////////////////////////////////////
0123     // filtered_view
0124     //////////////////////////////////////////////////////////////////////////
0125 #if 0
0126     template <typename Sequence, typename Pred>
0127     using filtered_view_t = sliced_view_t<Sequence, detail::filtered_indices<...>>;
0128
0129     template <typename Sequence, typename Pred>
0130     constexpr filtered_view_t<Sequence, Pred> filtered(Sequence& sequence, Pred&& pred) {
0131         return {sequence};
0132     }
0133 #endif
0134
0135     //////////////////////////////////////////////////////////////////////////
0136     // joined_view
0137     //////////////////////////////////////////////////////////////////////////
0138     template <typename Sequence1, typename Sequence2>
0139     struct joined_view_t {
0140         detail::view_storage<Sequence1> sequence1_;
0141         detail::view_storage<Sequence2> sequence2_;
0142         using hana_tag = view_tag;
0143     };
0144
0145     struct make_joined_view_t {
0146         template <typename Sequence1, typename Sequence2>
0147         constexpr joined_view_t<Sequence1, Sequence2> operator()(Sequence1& s1, Sequence2& s2) const {
0148             return {s1, s2};
0149         }
0150     };
0151     BOOST_HANA_INLINE_VARIABLE constexpr make_joined_view_t joined{};
0152
0153     namespace detail {
0154         template <typename Sequence1, typename Sequence2>
0155         struct is_view<joined_view_t<Sequence1, Sequence2>> {
0156             static constexpr bool value = true;
0157         };
0158     }
0159
0160     //////////////////////////////////////////////////////////////////////////
0161     // single_view
0162     //////////////////////////////////////////////////////////////////////////
0163     template <typename T>
0164     struct single_view_t {
0165         T value_;
0166         using hana_tag = view_tag;
0167     };
0168
0169     template <typename T>
0170     constexpr single_view_t<typename hana::detail::decay<T>::type> single_view(T&& t) {
0171         return {static_cast<T&&>(t)};
0172     }
0173
0174     namespace detail {
0175         template <typename T>
0176         struct is_view<single_view_t<T>> {
0177             static constexpr bool value = true;
0178         };
0179     }
0180
0181     //////////////////////////////////////////////////////////////////////////
0182     // empty_view
0183     //////////////////////////////////////////////////////////////////////////
0184     struct empty_view_t {
0185         using hana_tag = view_tag;
0186     };
0187
0188     constexpr empty_view_t empty_view() {
0189         return {};
0190     }
0191
0192     namespace detail {
0193         template <>
0194         struct is_view<empty_view_t> {
0195             static constexpr bool value = true;
0196         };
0197     }
0198 } // end namespace experimental
0199
0200 //////////////////////////////////////////////////////////////////////////
0201 // Foldable
0202 //////////////////////////////////////////////////////////////////////////
0203 template <>
0204 struct unpack_impl<experimental::view_tag> {
0205     // sliced_view
0206     template <typename Sequence, std::size_t ...i, typename F>
0207     static constexpr decltype(auto)
0208     apply(experimental::sliced_view_t<Sequence, i...> view, F&& f) {
0209         (void)view; // Remove spurious unused variable warning with GCC
0210         return static_cast<F&&>(f)(hana::at_c<i>(view.sequence_)...);
0211     }
0212
0213     // transformed_view
0214     template <typename Sequence, typename F, typename G>
0215     static constexpr decltype(auto)
0216     apply(experimental::transformed_view_t<Sequence, F> view, G&& g) {
0217         return hana::unpack(view.sequence_, hana::on(static_cast<G&&>(g), view.f_));
0218     }
0219
0220     // joined_view
0221     template <typename View, typename F, std::size_t ...i1, std::size_t ...i2>
0222     static constexpr decltype(auto)
0223     unpack_joined(View view, F&& f, std::index_sequence<i1...>,
0224                                     std::index_sequence<i2...>)
0225     {
0226         (void)view; // Remove spurious unused variable warning with GCC
0227         return static_cast<F&&>(f)(hana::at_c<i1>(view.sequence1_)...,
0228                                    hana::at_c<i2>(view.sequence2_)...);
0229     }
0230
0231     template <typename S1, typename S2, typename F>
0232     static constexpr decltype(auto)
0233     apply(experimental::joined_view_t<S1, S2> view, F&& f) {
0234         constexpr auto N1 = decltype(hana::length(view.sequence1_))::value;
0235         constexpr auto N2 = decltype(hana::length(view.sequence2_))::value;
0236         return unpack_joined(view, static_cast<F&&>(f),
0237                              std::make_index_sequence<N1>{},
0238                              std::make_index_sequence<N2>{});
0239     }
0240
0241     // single_view
0242     template <typename T, typename F>
0243     static constexpr decltype(auto) apply(experimental::single_view_t<T> view, F&& f) {
0244         return static_cast<F&&>(f)(view.value_);
0245     }
0246
0247     // empty_view
0248     template <typename F>
0249     static constexpr decltype(auto) apply(experimental::empty_view_t, F&& f) {
0250         return static_cast<F&&>(f)();
0251     }
0252 };
0253
0254 //////////////////////////////////////////////////////////////////////////
0255 // Iterable
0256 //////////////////////////////////////////////////////////////////////////
0257 template <>
0258 struct at_impl<experimental::view_tag> {
0259     // sliced_view
0260     template <typename Sequence, std::size_t ...i, typename N>
0261     static constexpr decltype(auto)
0262     apply(experimental::sliced_view_t<Sequence, i...> view, N const&) {
0263         constexpr std::size_t indices[] = {i...};
0264         constexpr std::size_t n = indices[N::value];
0265         return hana::at_c<n>(view.sequence_);
0266     }
0267
0268     // transformed_view
0269     template <typename Sequence, typename F, typename N>
0270     static constexpr decltype(auto)
0271     apply(experimental::transformed_view_t<Sequence, F> view, N const& n) {
0272         return view.f_(hana::at(view.sequence_, n));
0273     }
0274
0275     // joined_view
0276     template <std::size_t Left, typename View, typename N>
0277     static constexpr decltype(auto) at_joined_view(View view, N const&, hana::true_) {
0278         return hana::at_c<N::value>(view.sequence1_);
0279     }
0280
0281     template <std::size_t Left, typename View, typename N>
0282     static constexpr decltype(auto) at_joined_view(View view, N const&, hana::false_) {
0283         return hana::at_c<N::value - Left>(view.sequence2_);
0284     }
0285
0286     template <typename S1, typename S2, typename N>
0287     static constexpr decltype(auto)
0288     apply(experimental::joined_view_t<S1, S2> view, N const& n) {
0289         constexpr auto Left = decltype(hana::length(view.sequence1_))::value;
0290         return at_joined_view<Left>(view, n, hana::bool_c<(N::value < Left)>);
0291     }
0292
0293     // single_view
0294     template <typename T, typename N>
0295     static constexpr decltype(auto) apply(experimental::single_view_t<T> view, N const&) {
0296         static_assert(N::value == 0,
0297         "trying to fetch an out-of-bounds element in a hana::single_view");
0298         return view.value_;
0299     }
0300
0301     // empty_view
0302     template <typename N>
0303     static constexpr decltype(auto) apply(experimental::empty_view_t, N const&) = delete;
0304 };
0305
0306 template <>
0307 struct length_impl<experimental::view_tag> {
0308     // sliced_view
0309     template <typename Sequence, std::size_t ...i>
0310     static constexpr auto
0311     apply(experimental::sliced_view_t<Sequence, i...>) {
0312         return hana::size_c<sizeof...(i)>;
0313     }
0314
0315     // transformed_view
0316     template <typename Sequence, typename F>
0317     static constexpr auto apply(experimental::transformed_view_t<Sequence, F> view) {
0318         return hana::length(view.sequence_);
0319     }
0320
0321     // joined_view
0322     template <typename S1, typename S2>
0323     static constexpr auto apply(experimental::joined_view_t<S1, S2> view) {
0324         return hana::size_c<
0325             decltype(hana::length(view.sequence1_))::value +
0326             decltype(hana::length(view.sequence2_))::value
0327         >;
0328     }
0329
0330     // single_view
0331     template <typename T>
0332     static constexpr auto apply(experimental::single_view_t<T>) {
0333         return hana::size_c<1>;
0334     }
0335
0336     // empty_view
0337     static constexpr auto apply(experimental::empty_view_t) {
0338         return hana::size_c<0>;
0339     }
0340 };
0341
0342 template <>
0343 struct is_empty_impl<experimental::view_tag> {
0344     // sliced_view
0345     template <typename Sequence, std::size_t ...i>
0346     static constexpr auto
0347     apply(experimental::sliced_view_t<Sequence, i...>) {
0348         return hana::bool_c<sizeof...(i) == 0>;
0349     }
0350
0351     // transformed_view
0352     template <typename Sequence, typename F>
0353     static constexpr auto apply(experimental::transformed_view_t<Sequence, F> view) {
0354         return hana::is_empty(view.sequence_);
0355     }
0356
0357     // joined_view
0358     template <typename S1, typename S2>
0359     static constexpr auto apply(experimental::joined_view_t<S1, S2> view) {
0360         return hana::and_(hana::is_empty(view.sequence1_),
0361                           hana::is_empty(view.sequence2_));
0362     }
0363
0364     // single_view
0365     template <typename T>
0366     static constexpr auto apply(experimental::single_view_t<T>) {
0367         return hana::false_c;
0368     }
0369
0370     // empty_view
0371     static constexpr auto apply(experimental::empty_view_t) {
0372         return hana::true_c;
0373     }
0374 };
0375
0376 template <>
0377 struct drop_front_impl<experimental::view_tag> {
0378     template <typename View, typename N>
0379     static constexpr auto apply(View view, N const&) {
0380         constexpr auto n = N::value;
0381         constexpr auto Length = decltype(hana::length(view))::value;
0382         return experimental::sliced(view, hana::range_c<std::size_t, n, Length>);
0383     }
0384 };
0385
0386 //////////////////////////////////////////////////////////////////////////
0387 // Functor
0388 //////////////////////////////////////////////////////////////////////////
0389 template <>
0390 struct transform_impl<experimental::view_tag> {
0391     template <typename Sequence, typename F, typename G>
0392     static constexpr auto
0393     apply(experimental::transformed_view_t<Sequence, F> view, G&& g) {
0394         return experimental::transformed(view.sequence_,
0395                                          hana::compose(static_cast<G&&>(g), view.f_));
0396     }
0397
0398     template <typename View, typename F>
0399     static constexpr auto apply(View view, F&& f) {
0400         return experimental::transformed(view, static_cast<F&&>(f));
0401     }
0402 };
0403
0404 //////////////////////////////////////////////////////////////////////////
0405 // Applicative
0406 //////////////////////////////////////////////////////////////////////////
0407 template <>
0408 struct lift_impl<experimental::view_tag> {
0409     template <typename T>
0410     static constexpr auto apply(T&& t) {
0411         return experimental::single_view(static_cast<T&&>(t));
0412     }
0413 };
0414
0415 template <>
0416 struct ap_impl<experimental::view_tag> {
0417     template <typename F, typename X>
0418     static constexpr auto apply(F&& f, X&& x) {
0419         // TODO: Implement cleverly; we most likely need a cartesian_product
0420         //       view or something like that.
0421         return hana::ap(hana::to_tuple(f), hana::to_tuple(x));
0422     }
0423 };
0424
0425 //////////////////////////////////////////////////////////////////////////
0426 // Monad
0427 //////////////////////////////////////////////////////////////////////////
0428 template <>
0429 struct flatten_impl<experimental::view_tag> {
0430     template <typename View>
0431     static constexpr auto apply(View view) {
0432         // TODO: Implement a flattened_view instead
0433         return hana::fold_left(view, experimental::empty_view(),
0434                                      experimental::joined);
0435     }
0436 };
0437
0438 //////////////////////////////////////////////////////////////////////////
0439 // MonadPlus
0440 //////////////////////////////////////////////////////////////////////////
0441 template <>
0442 struct concat_impl<experimental::view_tag> {
0443     template <typename View1, typename View2>
0444     static constexpr auto apply(View1 view1, View2 view2) {
0445         return experimental::joined(view1, view2);
0446     }
0447 };
0448
0449 template <>
0450 struct empty_impl<experimental::view_tag> {
0451     static constexpr auto apply() {
0452         return experimental::empty_view();
0453     }
0454 };
0455
0456 //////////////////////////////////////////////////////////////////////////
0457 // Comparable
0458 //////////////////////////////////////////////////////////////////////////
0459 template <>
0460 struct equal_impl<experimental::view_tag, experimental::view_tag> {
0461     template <typename View1, typename View2>
0462     static constexpr auto apply(View1 v1, View2 v2) {
0463         // TODO: Use a lexicographical comparison algorithm.
0464         return hana::equal(hana::to_tuple(v1), hana::to_tuple(v2));
0465     }
0466 };
0467
0468 template <typename S>
0469 struct equal_impl<experimental::view_tag, S, hana::when<hana::Sequence<S>::value>> {
0470     template <typename View1, typename Seq>
0471     static constexpr auto apply(View1 v1, Seq const& s) {
0472         // TODO: Use a lexicographical comparison algorithm.
0473         return hana::equal(hana::to_tuple(v1), hana::to_tuple(s));
0474     }
0475 };
0476
0477 template <typename S>
0478 struct equal_impl<S, experimental::view_tag, hana::when<hana::Sequence<S>::value>> {
0479     template <typename Seq, typename View2>
0480     static constexpr auto apply(Seq const& s, View2 v2) {
0481         // TODO: Use a lexicographical comparison algorithm.
0482         return hana::equal(hana::to_tuple(s), hana::to_tuple(v2));
0483     }
0484 };
0485
0486 //////////////////////////////////////////////////////////////////////////
0487 // Orderable
0488 //////////////////////////////////////////////////////////////////////////
0489 template <>
0490 struct less_impl<experimental::view_tag, experimental::view_tag> {
0491     template <typename View1, typename View2>
0492     static constexpr auto apply(View1 v1, View2 v2) {
0493         return hana::lexicographical_compare(v1, v2);
0494     }
0495 };
0496
0497 template <typename S>
0498 struct less_impl<experimental::view_tag, S, hana::when<hana::Sequence<S>::value>> {
0499     template <typename View1, typename Seq>
0500     static constexpr auto apply(View1 v1, Seq const& s) {
0501         return hana::lexicographical_compare(v1, s);
0502     }
0503 };
0504
0505 template <typename S>
0506 struct less_impl<S, experimental::view_tag, hana::when<hana::Sequence<S>::value>> {
0507     template <typename Seq, typename View2>
0508     static constexpr auto apply(Seq const& s, View2 v2) {
0509         return hana::lexicographical_compare(s, v2);
0510     }
0511 };
0512
0513 }} // end namespace boost::hana
0514
0515 #endif // !BOOST_HANA_EXPERIMENTAL_VIEW_HPP