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