boost/hana/experimental/view.hpp

   1 /*
   2 @file
   3 Defines experimental views.
   4
   5 @copyright Louis Dionne 2013-2017
   6 Distributed under the Boost Software License, Version 1.0.
   7 (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
   8  */
   9
  10 #ifndef BOOST_HANA_EXPERIMENTAL_VIEW_HPP
  11 #define BOOST_HANA_EXPERIMENTAL_VIEW_HPP
  12
  13 #include <boost/hana/and.hpp>
  14 #include <boost/hana/at.hpp>
  15 #include <boost/hana/bool.hpp>
  16 #include <boost/hana/detail/decay.hpp>
  17 #include <boost/hana/fold_left.hpp>
  18 #include <boost/hana/functional/compose.hpp>
  19 #include <boost/hana/fwd/ap.hpp>
  20 #include <boost/hana/fwd/concat.hpp>
  21 #include <boost/hana/fwd/drop_front.hpp>
  22 #include <boost/hana/fwd/empty.hpp>
  23 #include <boost/hana/fwd/equal.hpp>
  24 #include <boost/hana/fwd/flatten.hpp>
  25 #include <boost/hana/fwd/is_empty.hpp>
  26 #include <boost/hana/fwd/less.hpp>
  27 #include <boost/hana/fwd/lift.hpp>
  28 #include <boost/hana/fwd/transform.hpp>
  29 #include <boost/hana/integral_constant.hpp>
  30 #include <boost/hana/length.hpp>
  31 #include <boost/hana/lexicographical_compare.hpp>
  32 #include <boost/hana/range.hpp>
  33 #include <boost/hana/tuple.hpp>
  34 #include <boost/hana/unpack.hpp>
  35
  36 #include <cstddef>
  37 #include <type_traits>
  38 #include <utility>
  39
  40
  41 // Pros of views
  42 //     - No temporary container created between algorithms
  43 //     - Lazy, so only the minimum is required
  44 //
  45 // Cons of views
  46 //     - Reference semantics mean possibility for dangling references
  47 //     - Lose the ability to move from temporary containers
  48 //     - When fetching the members of a view multiple times, no caching is done.
  49 //       So for example, `t = transform(xs, f); at_c<0>(t); at_c<0>(t)` will
  50 //       compute `f(at_c<0>(xs))` twice.
  51 //     - push_back creates a joint_view and a single_view. The single_view holds
  52 //       the value as a member. When doing multiple push_backs, we end up with a
  53 //         joint_view<xxx, joint_view<single_view<T>, joint_view<single_view<T>, ....>>>
  54 //       which contains a reference to `xxx` and all the `T`s by value. Such a
  55 //       "view" is not cheap to copy, which is inconsistent with the usual
  56 //       expectations about views.
  57
  58 BOOST_HANA_NAMESPACE_BEGIN
  59
  60 namespace experimental {
  61     struct view_tag;
  62
  63     namespace detail {
  64         template <typename Sequence>
  65         struct is_view {
  66             static constexpr bool value = false;
  67         };
  68
  69         template <typename Sequence>
  70         using view_storage = typename std::conditional<
  71             detail::is_view<Sequence>::value, Sequence, Sequence&
  72         >::type;
  73     }
  74
  75     //////////////////////////////////////////////////////////////////////////
  76     // sliced_view
  77     //////////////////////////////////////////////////////////////////////////
  78     template <typename Sequence, std::size_t ...indices>
  79     struct sliced_view_t {
  80         detail::view_storage<Sequence> sequence_;
  81         using hana_tag = view_tag;
  82     };
  83
  84     template <typename Sequence, typename Indices>
  85     constexpr auto sliced(Sequence& sequence, Indices const& indices) {
  86         return hana::unpack(indices, [&](auto ...i) {
  87             return sliced_view_t<Sequence, decltype(i)::value...>{sequence};
  88         });
  89     }
  90
  91     namespace detail {
  92         template <typename Sequence, std::size_t ...i>
  93         struct is_view<sliced_view_t<Sequence, i...>> {
  94             static constexpr bool value = true;
  95         };
  96     }
  97
  98     //////////////////////////////////////////////////////////////////////////
  99     // transformed_view
 100     //////////////////////////////////////////////////////////////////////////
 101     template <typename Sequence, typename F>
 102     struct transformed_view_t {
 103         detail::view_storage<Sequence> sequence_;
 104         F f_;
 105         using hana_tag = view_tag;
 106     };
 107
 108     template <typename Sequence, typename F>
 109     constexpr transformed_view_t<Sequence, typename hana::detail::decay<F>::type>
 110     transformed(Sequence& sequence, F&& f) {
 111         return {sequence, static_cast<F&&>(f)};
 112     }
 113
 114     namespace detail {
 115         template <typename Sequence, typename F>
 116         struct is_view<transformed_view_t<Sequence, F>> {
 117             static constexpr bool value = true;
 118         };
 119     }
 120
 121     //////////////////////////////////////////////////////////////////////////
 122     // filtered_view
 123     //////////////////////////////////////////////////////////////////////////
 124 #if 0
 125     template <typename Sequence, typename Pred>
 126     using filtered_view_t = sliced_view_t<Sequence, detail::filtered_indices<...>>;
 127
 128     template <typename Sequence, typename Pred>
 129     constexpr filtered_view_t<Sequence, Pred> filtered(Sequence& sequence, Pred&& pred) {
 130         return {sequence};
 131     }
 132 #endif
 133
 134     //////////////////////////////////////////////////////////////////////////
 135     // joined_view
 136     //////////////////////////////////////////////////////////////////////////
 137     template <typename Sequence1, typename Sequence2>
 138     struct joined_view_t {
 139         detail::view_storage<Sequence1> sequence1_;
 140         detail::view_storage<Sequence2> sequence2_;
 141         using hana_tag = view_tag;
 142     };
 143
 144     struct make_joined_view_t {
 145         template <typename Sequence1, typename Sequence2>
 146         constexpr joined_view_t<Sequence1, Sequence2> operator()(Sequence1& s1, Sequence2& s2) const {
 147             return {s1, s2};
 148         }
 149     };
 150     constexpr make_joined_view_t joined{};
 151
 152     namespace detail {
 153         template <typename Sequence1, typename Sequence2>
 154         struct is_view<joined_view_t<Sequence1, Sequence2>> {
 155             static constexpr bool value = true;
 156         };
 157     }
 158
 159     //////////////////////////////////////////////////////////////////////////
 160     // single_view
 161     //////////////////////////////////////////////////////////////////////////
 162     template <typename T>
 163     struct single_view_t {
 164         T value_;
 165         using hana_tag = view_tag;
 166     };
 167
 168     template <typename T>
 169     constexpr single_view_t<typename hana::detail::decay<T>::type> single_view(T&& t) {
 170         return {static_cast<T&&>(t)};
 171     }
 172
 173     namespace detail {
 174         template <typename T>
 175         struct is_view<single_view_t<T>> {
 176             static constexpr bool value = true;
 177         };
 178     }
 179
 180     //////////////////////////////////////////////////////////////////////////
 181     // empty_view
 182     //////////////////////////////////////////////////////////////////////////
 183     struct empty_view_t {
 184         using hana_tag = view_tag;
 185     };
 186
 187     constexpr empty_view_t empty_view() {
 188         return {};
 189     }
 190
 191     namespace detail {
 192         template <>
 193         struct is_view<empty_view_t> {
 194             static constexpr bool value = true;
 195         };
 196     }
 197 } // end namespace experimental
 198
 199 //////////////////////////////////////////////////////////////////////////
 200 // Foldable
 201 //////////////////////////////////////////////////////////////////////////
 202 template <>
 203 struct unpack_impl<experimental::view_tag> {
 204     // sliced_view
 205     template <typename Sequence, std::size_t ...i, typename F>
 206     static constexpr decltype(auto)
 207     apply(experimental::sliced_view_t<Sequence, i...> view, F&& f) {
 208         (void)view; // Remove spurious unused variable warning with GCC
 209         return static_cast<F&&>(f)(hana::at_c<i>(view.sequence_)...);
 210     }
 211
 212     // transformed_view
 213     template <typename Sequence, typename F, typename G>
 214     static constexpr decltype(auto)
 215     apply(experimental::transformed_view_t<Sequence, F> view, G&& g) {
 216         return hana::unpack(view.sequence_, hana::on(static_cast<G&&>(g), view.f_));
 217     }
 218
 219     // joined_view
 220     template <typename View, typename F, std::size_t ...i1, std::size_t ...i2>
 221     static constexpr decltype(auto)
 222     unpack_joined(View view, F&& f, std::index_sequence<i1...>,
 223                                     std::index_sequence<i2...>)
 224     {
 225         (void)view; // Remove spurious unused variable warning with GCC
 226         return static_cast<F&&>(f)(hana::at_c<i1>(view.sequence1_)...,
 227                                    hana::at_c<i2>(view.sequence2_)...);
 228     }
 229
 230     template <typename S1, typename S2, typename F>
 231     static constexpr decltype(auto)
 232     apply(experimental::joined_view_t<S1, S2> view, F&& f) {
 233         constexpr auto N1 = decltype(hana::length(view.sequence1_))::value;
 234         constexpr auto N2 = decltype(hana::length(view.sequence2_))::value;
 235         return unpack_joined(view, static_cast<F&&>(f),
 236                              std::make_index_sequence<N1>{},
 237                              std::make_index_sequence<N2>{});
 238     }
 239
 240     // single_view
 241     template <typename T, typename F>
 242     static constexpr decltype(auto) apply(experimental::single_view_t<T> view, F&& f) {
 243         return static_cast<F&&>(f)(view.value_);
 244     }
 245
 246     // empty_view
 247     template <typename F>
 248     static constexpr decltype(auto) apply(experimental::empty_view_t, F&& f) {
 249         return static_cast<F&&>(f)();
 250     }
 251 };
 252
 253 //////////////////////////////////////////////////////////////////////////
 254 // Iterable
 255 //////////////////////////////////////////////////////////////////////////
 256 template <>
 257 struct at_impl<experimental::view_tag> {
 258     // sliced_view
 259     template <typename Sequence, std::size_t ...i, typename N>
 260     static constexpr decltype(auto)
 261     apply(experimental::sliced_view_t<Sequence, i...> view, N const&) {
 262         constexpr std::size_t indices[] = {i...};
 263         constexpr std::size_t n = indices[N::value];
 264         return hana::at_c<n>(view.sequence_);
 265     }
 266
 267     // transformed_view
 268     template <typename Sequence, typename F, typename N>
 269     static constexpr decltype(auto)
 270     apply(experimental::transformed_view_t<Sequence, F> view, N const& n) {
 271         return view.f_(hana::at(view.sequence_, n));
 272     }
 273
 274     // joined_view
 275     template <std::size_t Left, typename View, typename N>
 276     static constexpr decltype(auto) at_joined_view(View view, N const&, hana::true_) {
 277         return hana::at_c<N::value>(view.sequence1_);
 278     }
 279
 280     template <std::size_t Left, typename View, typename N>
 281     static constexpr decltype(auto) at_joined_view(View view, N const&, hana::false_) {
 282         return hana::at_c<N::value - Left>(view.sequence2_);
 283     }
 284
 285     template <typename S1, typename S2, typename N>
 286     static constexpr decltype(auto)
 287     apply(experimental::joined_view_t<S1, S2> view, N const& n) {
 288         constexpr auto Left = decltype(hana::length(view.sequence1_))::value;
 289         return at_joined_view<Left>(view, n, hana::bool_c<(N::value < Left)>);
 290     }
 291
 292     // single_view
 293     template <typename T, typename N>
 294     static constexpr decltype(auto) apply(experimental::single_view_t<T> view, N const&) {
 295         static_assert(N::value == 0,
 296         "trying to fetch an out-of-bounds element in a hana::single_view");
 297         return view.value_;
 298     }
 299
 300     // empty_view
 301     template <typename N>
 302     static constexpr decltype(auto) apply(experimental::empty_view_t, N const&) = delete;
 303 };
 304
 305 template <>
 306 struct length_impl<experimental::view_tag> {
 307     // sliced_view
 308     template <typename Sequence, std::size_t ...i>
 309     static constexpr auto
 310     apply(experimental::sliced_view_t<Sequence, i...>) {
 311         return hana::size_c<sizeof...(i)>;
 312     }
 313
 314     // transformed_view
 315     template <typename Sequence, typename F>
 316     static constexpr auto apply(experimental::transformed_view_t<Sequence, F> view) {
 317         return hana::length(view.sequence_);
 318     }
 319
 320     // joined_view
 321     template <typename S1, typename S2>
 322     static constexpr auto apply(experimental::joined_view_t<S1, S2> view) {
 323         return hana::size_c<
 324             decltype(hana::length(view.sequence1_))::value +
 325             decltype(hana::length(view.sequence2_))::value
 326         >;
 327     }
 328
 329     // single_view
 330     template <typename T>
 331     static constexpr auto apply(experimental::single_view_t<T>) {
 332         return hana::size_c<1>;
 333     }
 334
 335     // empty_view
 336     static constexpr auto apply(experimental::empty_view_t) {
 337         return hana::size_c<0>;
 338     }
 339 };
 340
 341 template <>
 342 struct is_empty_impl<experimental::view_tag> {
 343     // sliced_view
 344     template <typename Sequence, std::size_t ...i>
 345     static constexpr auto
 346     apply(experimental::sliced_view_t<Sequence, i...>) {
 347         return hana::bool_c<sizeof...(i) == 0>;
 348     }
 349
 350     // transformed_view
 351     template <typename Sequence, typename F>
 352     static constexpr auto apply(experimental::transformed_view_t<Sequence, F> view) {
 353         return hana::is_empty(view.sequence_);
 354     }
 355
 356     // joined_view
 357     template <typename S1, typename S2>
 358     static constexpr auto apply(experimental::joined_view_t<S1, S2> view) {
 359         return hana::and_(hana::is_empty(view.sequence1_),
 360                           hana::is_empty(view.sequence2_));
 361     }
 362
 363     // single_view
 364     template <typename T>
 365     static constexpr auto apply(experimental::single_view_t<T>) {
 366         return hana::false_c;
 367     }
 368
 369     // empty_view
 370     static constexpr auto apply(experimental::empty_view_t) {
 371         return hana::true_c;
 372     }
 373 };
 374
 375 template <>
 376 struct drop_front_impl<experimental::view_tag> {
 377     template <typename View, typename N>
 378     static constexpr auto apply(View view, N const&) {
 379         constexpr auto n = N::value;
 380         constexpr auto Length = decltype(hana::length(view))::value;
 381         return experimental::sliced(view, hana::range_c<std::size_t, n, Length>);
 382     }
 383 };
 384
 385 //////////////////////////////////////////////////////////////////////////
 386 // Functor
 387 //////////////////////////////////////////////////////////////////////////
 388 template <>
 389 struct transform_impl<experimental::view_tag> {
 390     template <typename Sequence, typename F, typename G>
 391     static constexpr auto
 392     apply(experimental::transformed_view_t<Sequence, F> view, G&& g) {
 393         return experimental::transformed(view.sequence_,
 394                                          hana::compose(static_cast<G&&>(g), view.f_));
 395     }
 396
 397     template <typename View, typename F>
 398     static constexpr auto apply(View view, F&& f) {
 399         return experimental::transformed(view, static_cast<F&&>(f));
 400     }
 401 };
 402
 403 //////////////////////////////////////////////////////////////////////////
 404 // Applicative
 405 //////////////////////////////////////////////////////////////////////////
 406 template <>
 407 struct lift_impl<experimental::view_tag> {
 408     template <typename T>
 409     static constexpr auto apply(T&& t) {
 410         return experimental::single_view(static_cast<T&&>(t));
 411     }
 412 };
 413
 414 template <>
 415 struct ap_impl<experimental::view_tag> {
 416     template <typename F, typename X>
 417     static constexpr auto apply(F&& f, X&& x) {
 418         // TODO: Implement cleverly; we most likely need a cartesian_product
 419         //       view or something like that.
 420         return hana::ap(hana::to_tuple(f), hana::to_tuple(x));
 421     }
 422 };
 423
 424 //////////////////////////////////////////////////////////////////////////
 425 // Monad
 426 //////////////////////////////////////////////////////////////////////////
 427 template <>
 428 struct flatten_impl<experimental::view_tag> {
 429     template <typename View>
 430     static constexpr auto apply(View view) {
 431         // TODO: Implement a flattened_view instead
 432         return hana::fold_left(view, experimental::empty_view(),
 433                                      experimental::joined);
 434     }
 435 };
 436
 437 //////////////////////////////////////////////////////////////////////////
 438 // MonadPlus
 439 //////////////////////////////////////////////////////////////////////////
 440 template <>
 441 struct concat_impl<experimental::view_tag> {
 442     template <typename View1, typename View2>
 443     static constexpr auto apply(View1 view1, View2 view2) {
 444         return experimental::joined(view1, view2);
 445     }
 446 };
 447
 448 template <>
 449 struct empty_impl<experimental::view_tag> {
 450     static constexpr auto apply() {
 451         return experimental::empty_view();
 452     }
 453 };
 454
 455 //////////////////////////////////////////////////////////////////////////
 456 // Comparable
 457 //////////////////////////////////////////////////////////////////////////
 458 template <>
 459 struct equal_impl<experimental::view_tag, experimental::view_tag> {
 460     template <typename View1, typename View2>
 461     static constexpr auto apply(View1 v1, View2 v2) {
 462         // TODO: Use a lexicographical comparison algorithm.
 463         return hana::equal(hana::to_tuple(v1), hana::to_tuple(v2));
 464     }
 465 };
 466
 467 template <typename S>
 468 struct equal_impl<experimental::view_tag, S, hana::when<hana::Sequence<S>::value>> {
 469     template <typename View1, typename Seq>
 470     static constexpr auto apply(View1 v1, Seq const& s) {
 471         // TODO: Use a lexicographical comparison algorithm.
 472         return hana::equal(hana::to_tuple(v1), hana::to_tuple(s));
 473     }
 474 };
 475
 476 template <typename S>
 477 struct equal_impl<S, experimental::view_tag, hana::when<hana::Sequence<S>::value>> {
 478     template <typename Seq, typename View2>
 479     static constexpr auto apply(Seq const& s, View2 v2) {
 480         // TODO: Use a lexicographical comparison algorithm.
 481         return hana::equal(hana::to_tuple(s), hana::to_tuple(v2));
 482     }
 483 };
 484
 485 //////////////////////////////////////////////////////////////////////////
 486 // Orderable
 487 //////////////////////////////////////////////////////////////////////////
 488 template <>
 489 struct less_impl<experimental::view_tag, experimental::view_tag> {
 490     template <typename View1, typename View2>
 491     static constexpr auto apply(View1 v1, View2 v2) {
 492         return hana::lexicographical_compare(v1, v2);
 493     }
 494 };
 495
 496 template <typename S>
 497 struct less_impl<experimental::view_tag, S, hana::when<hana::Sequence<S>::value>> {
 498     template <typename View1, typename Seq>
 499     static constexpr auto apply(View1 v1, Seq const& s) {
 500         return hana::lexicographical_compare(v1, s);
 501     }
 502 };
 503
 504 template <typename S>
 505 struct less_impl<S, experimental::view_tag, hana::when<hana::Sequence<S>::value>> {
 506     template <typename Seq, typename View2>
 507     static constexpr auto apply(Seq const& s, View2 v2) {
 508         return hana::lexicographical_compare(s, v2);
 509     }
 510 };
 511
 512 BOOST_HANA_NAMESPACE_END
 513
 514 #endif // !BOOST_HANA_EXPERIMENTAL_VIEW_HPP