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> sliced(Sequence & sequence,Indices const & 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> transformed(Sequence & sequence,F && f)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> operator ()experimental::make_joined_view_t147 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> single_view(T && 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 empty_view()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) applyunpack_impl208 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) applyunpack_impl216 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) unpack_joinedunpack_impl223 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) applyunpack_impl233 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> applyunpack_impl243 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> applyunpack_impl249 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) applyat_impl262 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) applyat_impl271 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> at_joined_viewat_impl277 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> at_joined_viewat_impl282 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) applyat_impl288 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> applyat_impl295 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 applylength_impl311 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> applylength_impl317 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> applylength_impl323 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> applylength_impl332 static constexpr auto apply(experimental::single_view_t<T>) { 333 return hana::size_c<1>; 334 } 335 336 // empty_view applylength_impl337 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 applyis_empty_impl347 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> applyis_empty_impl353 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> applyis_empty_impl359 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> applyis_empty_impl366 static constexpr auto apply(experimental::single_view_t<T>) { 367 return hana::false_c; 368 } 369 370 // empty_view applyis_empty_impl371 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> applydrop_front_impl379 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 applytransform_impl393 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> applytransform_impl399 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> applylift_impl410 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> applyap_impl418 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> applyflatten_impl431 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> applyconcat_impl444 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> { applyempty_impl451 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> applyequal_impl462 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> applyequal_impl471 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> applyequal_impl480 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> applyless_impl492 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> applyless_impl500 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> applyless_impl508 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 516