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