libcxx/include/__mdspan/layout_right.h

   1 // -*- C++ -*-
   2 //===----------------------------------------------------------------------===//
   3 //
   4 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   5 // See https://llvm.org/LICENSE.txt for license information.
   6 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   7 //
   8 //                        Kokkos v. 4.0
   9 //       Copyright (2022) National Technology & Engineering
  10 //               Solutions of Sandia, LLC (NTESS).
  11 //
  12 // Under the terms of Contract DE-NA0003525 with NTESS,
  13 // the U.S. Government retains certain rights in this software.
  14 //
  15 //===---------------------------------------------------------------------===//
  16
  17 #ifndef _LIBCPP___MDSPAN_LAYOUT_RIGHT_H
  18 #define _LIBCPP___MDSPAN_LAYOUT_RIGHT_H
  19
  20 #include <__assert>
  21 #include <__config>
  22 #include <__fwd/mdspan.h>
  23 #include <__mdspan/extents.h>
  24 #include <__type_traits/is_constructible.h>
  25 #include <__type_traits/is_convertible.h>
  26 #include <__type_traits/is_nothrow_constructible.h>
  27 #include <__utility/integer_sequence.h>
  28 #include <cinttypes>
  29 #include <cstddef>
  30 #include <limits>
  31
  32 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  33 #  pragma GCC system_header
  34 #endif
  35
  36 _LIBCPP_PUSH_MACROS
  37 #include <__undef_macros>
  38
  39 _LIBCPP_BEGIN_NAMESPACE_STD
  40
  41 #if _LIBCPP_STD_VER >= 23
  42
  43 template <class _Extents>
  44 class layout_right::mapping {
  45 public:
  46   static_assert(__mdspan_detail::__is_extents<_Extents>::value,
  47                 "layout_right::mapping template argument must be a specialization of extents.");
  48
  49   using extents_type = _Extents;
  50   using index_type   = typename extents_type::index_type;
  51   using size_type    = typename extents_type::size_type;
  52   using rank_type    = typename extents_type::rank_type;
  53   using layout_type  = layout_right;
  54
  55 private:
  56   _LIBCPP_HIDE_FROM_ABI static constexpr bool __required_span_size_is_representable(const extents_type& __ext) {
  57     if constexpr (extents_type::rank() == 0)
  58       return true;
  59
  60     index_type __prod = __ext.extent(0);
  61     for (rank_type __r = 1; __r < extents_type::rank(); __r++) {
  62       bool __overflowed = __builtin_mul_overflow(__prod, __ext.extent(__r), &__prod);
  63       if (__overflowed)
  64         return false;
  65     }
  66     return true;
  67   }
  68
  69   static_assert((extents_type::rank_dynamic() > 0) || __required_span_size_is_representable(extents_type()),
  70                 "layout_right::mapping product of static extents must be representable as index_type.");
  71
  72 public:
  73   // [mdspan.layout.right.cons], constructors
  74   _LIBCPP_HIDE_FROM_ABI constexpr mapping() noexcept               = default;
  75   _LIBCPP_HIDE_FROM_ABI constexpr mapping(const mapping&) noexcept = default;
  76   _LIBCPP_HIDE_FROM_ABI constexpr mapping(const extents_type& __ext) noexcept : __extents_(__ext) {
  77     // not catching this could lead to out-of-bounds access later when used inside mdspan
  78     // mapping<dextents<char, 2>> map(dextents<char, 2>(40,40)); map(3, 10) == -126
  79     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
  80         __required_span_size_is_representable(__ext),
  81         "layout_right::mapping extents ctor: product of extents must be representable as index_type.");
  82   }
  83
  84   template <class _OtherExtents>
  85     requires(is_constructible_v<extents_type, _OtherExtents>)
  86   _LIBCPP_HIDE_FROM_ABI constexpr explicit(!is_convertible_v<_OtherExtents, extents_type>)
  87       mapping(const mapping<_OtherExtents>& __other) noexcept
  88       : __extents_(__other.extents()) {
  89     // not catching this could lead to out-of-bounds access later when used inside mdspan
  90     // mapping<dextents<char, 2>> map(mapping<dextents<int, 2>>(dextents<int, 2>(40,40))); map(3, 10) == -126
  91     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
  92         __mdspan_detail::__is_representable_as<index_type>(__other.required_span_size()),
  93         "layout_right::mapping converting ctor: other.required_span_size() must be representable as index_type.");
  94   }
  95
  96   template <class _OtherExtents>
  97     requires(is_constructible_v<extents_type, _OtherExtents> && _OtherExtents::rank() <= 1)
  98   _LIBCPP_HIDE_FROM_ABI constexpr explicit(!is_convertible_v<_OtherExtents, extents_type>)
  99       mapping(const layout_left::mapping<_OtherExtents>& __other) noexcept
 100       : __extents_(__other.extents()) {
 101     // not catching this could lead to out-of-bounds access later when used inside mdspan
 102     // Note: since this is constraint to rank 1, extents itself would catch the invalid conversion first
 103     //       and thus this assertion should never be triggered, but keeping it here for consistency
 104     // layout_right::mapping<dextents<char, 1>> map(
 105     //           layout_left::mapping<dextents<unsigned, 1>>(dextents<unsigned, 1>(200))); map.extents().extent(0) ==
 106     //           -56
 107     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 108         __mdspan_detail::__is_representable_as<index_type>(__other.required_span_size()),
 109         "layout_right::mapping converting ctor: other.required_span_size() must be representable as index_type.");
 110   }
 111
 112   template <class _OtherExtents>
 113     requires(is_constructible_v<extents_type, _OtherExtents>)
 114   _LIBCPP_HIDE_FROM_ABI constexpr explicit(extents_type::rank() > 0)
 115       mapping(const layout_stride::mapping<_OtherExtents>& __other) noexcept
 116       : __extents_(__other.extents()) {
 117     if constexpr (extents_type::rank() > 0) {
 118       _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 119           ([&]() {
 120             using _CommonType = common_type_t<typename extents_type::index_type, typename _OtherExtents::index_type>;
 121             for (rank_type __r = 0; __r < extents_type::rank(); __r++)
 122               if (static_cast<_CommonType>(stride(__r)) != static_cast<_CommonType>(__other.stride(__r)))
 123                 return false;
 124             return true;
 125           }()),
 126           "layout_right::mapping from layout_stride ctor: strides are not compatible with layout_right.");
 127       _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 128           __mdspan_detail::__is_representable_as<index_type>(__other.required_span_size()),
 129           "layout_right::mapping from layout_stride ctor: other.required_span_size() must be representable as "
 130           "index_type.");
 131     }
 132   }
 133
 134   _LIBCPP_HIDE_FROM_ABI constexpr mapping& operator=(const mapping&) noexcept = default;
 135
 136   // [mdspan.layout.right.obs], observers
 137   _LIBCPP_HIDE_FROM_ABI constexpr const extents_type& extents() const noexcept { return __extents_; }
 138
 139   _LIBCPP_HIDE_FROM_ABI constexpr index_type required_span_size() const noexcept {
 140     index_type __size = 1;
 141     for (size_t __r = 0; __r < extents_type::rank(); __r++)
 142       __size *= __extents_.extent(__r);
 143     return __size;
 144   }
 145
 146   template <class... _Indices>
 147     requires((sizeof...(_Indices) == extents_type::rank()) && (is_convertible_v<_Indices, index_type> && ...) &&
 148              (is_nothrow_constructible_v<index_type, _Indices> && ...))
 149   _LIBCPP_HIDE_FROM_ABI constexpr index_type operator()(_Indices... __idx) const noexcept {
 150     // Mappings are generally meant to be used for accessing allocations and are meant to guarantee to never
 151     // return a value exceeding required_span_size(), which is used to know how large an allocation one needs
 152     // Thus, this is a canonical point in multi-dimensional data structures to make invalid element access checks
 153     // However, mdspan does check this on its own, so for now we avoid double checking in hardened mode
 154     _LIBCPP_ASSERT_UNCATEGORIZED(__mdspan_detail::__is_multidimensional_index_in(__extents_, __idx...),
 155                                  "layout_right::mapping: out of bounds indexing");
 156     return [&]<size_t... _Pos>(index_sequence<_Pos...>) {
 157       index_type __res = 0;
 158       ((__res = static_cast<index_type>(__idx) + __extents_.extent(_Pos) * __res), ...);
 159       return __res;
 160     }(make_index_sequence<sizeof...(_Indices)>());
 161   }
 162
 163   _LIBCPP_HIDE_FROM_ABI static constexpr bool is_always_unique() noexcept { return true; }
 164   _LIBCPP_HIDE_FROM_ABI static constexpr bool is_always_exhaustive() noexcept { return true; }
 165   _LIBCPP_HIDE_FROM_ABI static constexpr bool is_always_strided() noexcept { return true; }
 166
 167   _LIBCPP_HIDE_FROM_ABI static constexpr bool is_unique() noexcept { return true; }
 168   _LIBCPP_HIDE_FROM_ABI static constexpr bool is_exhaustive() noexcept { return true; }
 169   _LIBCPP_HIDE_FROM_ABI static constexpr bool is_strided() noexcept { return true; }
 170
 171   _LIBCPP_HIDE_FROM_ABI constexpr index_type stride(rank_type __r) const noexcept
 172     requires(extents_type::rank() > 0)
 173   {
 174     // While it would be caught by extents itself too, using a too large __r
 175     // is functionally an out of bounds access on the stored information needed to compute strides
 176     _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(
 177         __r < extents_type::rank(), "layout_right::mapping::stride(): invalid rank index");
 178     index_type __s = 1;
 179     for (rank_type __i = extents_type::rank() - 1; __i > __r; __i--)
 180       __s *= __extents_.extent(__i);
 181     return __s;
 182   }
 183
 184   template <class _OtherExtents>
 185     requires(_OtherExtents::rank() == extents_type::rank())
 186   _LIBCPP_HIDE_FROM_ABI friend constexpr bool
 187   operator==(const mapping& __lhs, const mapping<_OtherExtents>& __rhs) noexcept {
 188     return __lhs.extents() == __rhs.extents();
 189   }
 190
 191 private:
 192   _LIBCPP_NO_UNIQUE_ADDRESS extents_type __extents_{};
 193 };
 194
 195 #endif // _LIBCPP_STD_VER >= 23
 196
 197 _LIBCPP_END_NAMESPACE_STD
 198
 199 _LIBCPP_POP_MACROS
 200
 201 #endif // _LIBCPP___MDSPAN_LAYOUT_RIGHT_H