utils/ranges/ranges.hpp

0001 // This file is part of the ACTS project.
0002 //
0003 // Copyright (C) 2016 CERN for the benefit of the ACTS project
0004 //
0005 // This Source Code Form is subject to the terms of the Mozilla Public
0006 // License, v. 2.0. If a copy of the MPL was not distributed with this
0007 // file, You can obtain one at https://mozilla.org/MPL/2.0/.
0008
0009 #pragma once
0010
0011 // Project include(s)
0012 #include "detray/definitions/detail/qualifiers.hpp"
0013 #include "detray/definitions/indexing.hpp"
0014 #include "detray/utils/ranges/detail/iterator_functions.hpp"
0015 #include "detray/utils/type_traits.hpp"
0016
0017 // System include(s)
0018 #include <cassert>
0019 #include <concepts>
0020 #include <memory>
0021 #include <ranges>
0022 #include <type_traits>
0023
0024 namespace detray::ranges {
0025
0026 /// @brief Provides detray iterators in a simplified std::ranges style,
0027 ///        meant to be used in device code.
0028 ///
0029 /// @note Does make use of concepts and des not implement full ranges standard
0030 /// (e.g. not every requirement is modelled, range/view complexity guarantees
0031 /// are not strictly given and there is no lazy-evaluation).
0032 ///
0033 /// @see https://en.cppreference.com/w/cpp/ranges
0034 /// @see https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0896r4.pdf
0035 /// @{
0036
0037 /// Pull in iterator functionality
0038 /// @{
0039 // std version
0040 using detray::ranges::detail::begin;
0041 using detray::ranges::detail::cbegin;
0042 using detray::ranges::detail::cend;
0043 using detray::ranges::detail::crbegin;
0044 using detray::ranges::detail::crend;
0045 using detray::ranges::detail::end;
0046 using detray::ranges::detail::rbegin;
0047 using detray::ranges::detail::rend;
0048
0049 using detray::ranges::detail::data;
0050 using detray::ranges::detail::empty;
0051 using detray::ranges::detail::size;
0052
0053 // These are the only ones that are reimplemented using device quilifiers
0054 using detray::ranges::detail::advance;
0055 using detray::ranges::detail::distance;
0056 using detray::ranges::detail::next;
0057 using detray::ranges::detail::prev;
0058 /// @}
0059
0060 /// Ranges typedefs,
0061 /// @see https://en.cppreference.com/w/cpp/ranges/iterator_t
0062 /// @{
0063 template <class R>
0064 using iterator_t = decltype(detray::ranges::begin(std::declval<R&>()));
0065
0066 template <class R>
0067 using sentinel_t = decltype(detray::ranges::end(std::declval<R&>()));
0068
0069 template <class R>
0070 using const_iterator_t = decltype(detray::ranges::cbegin(std::declval<R&>()));
0071
0072 template <class R>
0073 using range_size_t = decltype(detray::ranges::size(std::declval<R&>()));
0074
0075 template <class R>
0076 using range_difference_t =
0077     std::iter_difference_t<detray::ranges::iterator_t<std::remove_cvref_t<R>>>;
0078
0079 template <class R>
0080 using range_value_t =
0081     std::iter_value_t<detray::ranges::iterator_t<std::remove_cvref_t<R>>>;
0082
0083 template <class R>
0084 using range_reference_t =
0085     std::iter_reference_t<detray::ranges::iterator_t<std::remove_cvref_t<R>>>;
0086
0087 template <class R>
0088 using range_const_reference_t = const range_reference_t<R>;
0089
0090 template <class R>
0091 using range_rvalue_reference_t = std::add_rvalue_reference_t<range_value_t<R>>;
0092
0093 /// @}
0094
0095 /// Range concept
0096 template <class R>
0097 concept range = std::ranges::range<R>;
0098
0099 /// Range of a given type
0100 template <typename R, typename T>
0101 concept range_of =
0102     detray::ranges::range<R> && std::same_as<std::ranges::range_value_t<R>, T>;
0103
0104 /// Range category concepts
0105 /// @{
0106 template <class R>
0107 concept input_range =
0108     detray::ranges::range<R> &&
0109     detray::ranges::input_iterator<detray::ranges::iterator_t<R>>;
0110
0111 template <class R, typename T>
0112 concept output_range =
0113     detray::ranges::range<R> &&
0114     detray::ranges::output_iterator<detray::ranges::iterator_t<R>, T>;
0115
0116 template <class R>
0117 concept forward_range =
0118     detray::ranges::range<R> &&
0119     detray::ranges::forward_iterator<detray::ranges::iterator_t<R>>;
0120
0121 template <class R>
0122 concept bidirectional_range =
0123     detray::ranges::range<R> &&
0124     detray::ranges::bidirectional_iterator<detray::ranges::iterator_t<R>>;
0125
0126 template <class R>
0127 concept random_access_range =
0128     detray::ranges::range<R> &&
0129     detray::ranges::random_access_iterator<detray::ranges::iterator_t<R>>;
0130 /// @}
0131
0132 // Contiguous iterator trait is only available in c++20
0133 // TODO: template <typename R> inline constexpr bool contiguous_range_v = ...
0134
0135 /// @see https://en.cppreference.com/w/cpp/ranges/sized_range
0136 template <class R>
0137 inline constexpr bool disable_sized_range = false;
0138
0139 /// @brief A function 'size' is implemented for the range @tparam R
0140 template <class R>
0141 inline constexpr bool sized_range =
0142     !ranges::disable_sized_range<std::remove_cvref_t<R>> &&
0143     (detray::ranges::range<R> &&
0144      std::is_integral_v<detray::ranges::range_size_t<R>>);
0145
0146 /// @see https://en.cppreference.com/w/cpp/ranges/borrowed_range
0147 template <class R>
0148 inline constexpr bool enable_borrowed_range = false;
0149
0150 template <class R>
0151 inline constexpr bool borrowed_range =
0152     detray::ranges::range<R> &&
0153     (std::is_lvalue_reference_v<R> ||
0154      ranges::enable_borrowed_range<std::remove_cvref_t<R>>);
0155
0156 /// @brief models a dangling iterator
0157 /// @see https://en.cppreference.com/w/cpp/ranges/dangling
0158 struct dangling {
0159   constexpr dangling() noexcept = default;
0160
0161   template <class... Args>
0162     requires(!(std::same_as<dangling, Args> || ...))
0163   explicit constexpr dangling(Args&&... /*unused*/) noexcept {}
0164 };
0165
0166 template <class R>
0167 using borrowed_iterator_t =
0168     std::conditional_t<borrowed_range<R>, detray::ranges::iterator_t<R>,
0169                        dangling>;
0170
0171 /// @see https://en.cppreference.com/w/cpp/ranges/common_range
0172 template <class R>
0173 inline constexpr bool common_range =
0174     std::is_same_v<detray::ranges::iterator_t<R>,
0175                    detray::ranges::sentinel_t<R>>;
0176 /// @}
0177
0178 /// Definition of 'view'
0179 /// @see https://en.cppreference.com/w/cpp/ranges/view
0180 /// @{
0181
0182 /// Tags a type as a view
0183 struct base_view {};
0184
0185 /// Defines a detray 'view'. For now, the views have to restrict the member
0186 /// functions themselves (i.e. forward, bidirectional, random access)
0187 template <typename view_impl_t>
0188 class view_interface : public base_view {
0189   /// Cast to the implementation type to access its methods
0190   /// @{
0191   DETRAY_HOST_DEVICE
0192   constexpr auto cast_impl() -> view_impl_t& {
0193     return static_cast<view_impl_t&>(*this);
0194   }
0195   DETRAY_HOST_DEVICE
0196   constexpr auto cast_impl() const -> const view_impl_t& {
0197     return static_cast<const view_impl_t&>(*this);
0198   }
0199   /// @}
0200
0201  public:
0202   /// @note requires forward range
0203   template <detray::ranges::forward_range R = view_impl_t>
0204   DETRAY_HOST_DEVICE constexpr auto empty() const -> bool {
0205     return (detray::ranges::begin(cast_impl()) ==
0206             detray::ranges::end(cast_impl()));
0207   }
0208
0209   DETRAY_HOST_DEVICE
0210   constexpr explicit operator bool() const {
0211     return !detray::ranges::empty(cast_impl());
0212   }
0213
0214   /// @note requires contiguous range (not yet modelled)
0215   DETRAY_HOST_DEVICE
0216   constexpr auto data() const {
0217     return empty() ? nullptr
0218                    : std::addressof(*(detray::ranges::begin(cast_impl())));
0219   }
0220
0221   /// @note requires contiguous range (not yet modelled)
0222   DETRAY_HOST_DEVICE
0223   constexpr auto data() {
0224     return empty() ? nullptr : &(*(detray::ranges::begin(cast_impl())));
0225   }
0226
0227   /// @note requires forward range
0228   template <detray::ranges::forward_range R = view_impl_t>
0229   DETRAY_HOST_DEVICE constexpr auto size() const {
0230     return static_cast<dindex>(detray::ranges::distance(
0231         detray::ranges::begin(cast_impl()), detray::ranges::end(cast_impl())));
0232   }
0233
0234   /// @note requires forward range
0235   template <detray::ranges::forward_range R = view_impl_t>
0236   DETRAY_HOST_DEVICE constexpr decltype(auto) front() const {
0237     const auto bg = detray::ranges::begin(cast_impl());
0238     assert(!empty());
0239     return *bg;
0240   }
0241
0242   /// @note requires forward range
0243   template <detray::ranges::forward_range R = view_impl_t>
0244   DETRAY_HOST_DEVICE constexpr decltype(auto) front() {
0245     const auto bg = detray::ranges::begin(cast_impl());
0246     assert(!empty());
0247     return *bg;
0248   }
0249
0250   /// @note requires bidirectional range
0251   template <detray::ranges::bidirectional_range R = view_impl_t>
0252   DETRAY_HOST_DEVICE constexpr decltype(auto) back() const {
0253     auto sentinel = detray::ranges::end(cast_impl());
0254     assert(!empty());
0255     return *(--sentinel);
0256   }
0257
0258   /// @note requires bidirectional range
0259   template <detray::ranges::bidirectional_range R = view_impl_t>
0260   DETRAY_HOST_DEVICE constexpr decltype(auto) back() {
0261     auto sentinel = detray::ranges::end(cast_impl());
0262     assert(!empty());
0263     return *(--sentinel);
0264   }
0265
0266   /// Subscript operator that takes detray @c dindex
0267   ///
0268   /// @note requires random access range
0269   template <detray::ranges::random_access_range R = view_impl_t>
0270   DETRAY_HOST_DEVICE constexpr decltype(auto) operator[](const dindex i) const {
0271     // Call 'begin()' directly here to make CUDA happy
0272     return (
0273         cast_impl()
0274             .begin())[static_cast<detray::ranges::range_difference_t<R>>(i)];
0275   }
0276   /// Subscript operator that takes detray @c dindex
0277   ///
0278   /// @note requires random access range
0279   template <detray::ranges::random_access_range R = view_impl_t>
0280   DETRAY_HOST_DEVICE constexpr decltype(auto) operator[](const dindex i) {
0281     // Call 'begin()' directly here to make CUDA happy
0282     return (
0283         cast_impl()
0284             .begin())[static_cast<detray::ranges::range_difference_t<R>>(i)];
0285   }
0286 };
0287
0288 /// View traits
0289 /// @{
0290 template <class R>
0291 inline constexpr bool enable_view =
0292     std::is_base_of_v<base_view, R> || std::is_base_of_v<view_interface<R>, R>;
0293
0294 template <class R>
0295 inline constexpr bool view = detray::ranges::range<R> && std::is_object_v<R> &&
0296                              std::is_move_constructible_v<R> && enable_view<R>;
0297
0298 template <class R>
0299 inline constexpr bool viewable_range =
0300     detray::ranges::range<R> &&
0301     (borrowed_range<R> || view<std::remove_cvref_t<R>>);
0302 /// @}
0303
0304 /// Pipe operator for range composition
0305 ///
0306 /// @param r range adaptor
0307 /// @param c closure
0308 ///
0309 /// @returns composed range c(r)
0310 /// @TODO: Add concept for range adaptors, closures etc.
0311 template <detray::ranges::range R, detray::ranges::range C>
0312 DETRAY_HOST_DEVICE auto operator|(R&& r, C&& c) {
0313   return std::forward<C>(c)(std::forward<R>(r));
0314 }
0315
0316 }  // namespace detray::ranges