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_EXTENTS_H 18 #define _LIBCPP___MDSPAN_EXTENTS_H 19 20 #include <__assert> 21 #include <__config> 22 #include <__type_traits/common_type.h> 23 #include <__type_traits/is_convertible.h> 24 #include <__type_traits/is_nothrow_constructible.h> 25 #include <__type_traits/is_same.h> 26 #include <__type_traits/make_unsigned.h> 27 #include <__utility/integer_sequence.h> 28 #include <__utility/unreachable.h> 29 #include <array> 30 #include <cinttypes> 31 #include <concepts> 32 #include <cstddef> 33 #include <limits> 34 #include <span> 35 36 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 37 # pragma GCC system_header 38 #endif 39 40 _LIBCPP_PUSH_MACROS 41 #include <__undef_macros> 42 43 _LIBCPP_BEGIN_NAMESPACE_STD 44 45 #if _LIBCPP_STD_VER >= 23 46 47 namespace __mdspan_detail { 48 49 // ------------------------------------------------------------------ 50 // ------------ __static_array -------------------------------------- 51 // ------------------------------------------------------------------ 52 // array like class which provides an array of static values with get 53 template <class _Tp, _Tp... _Values> 54 struct __static_array { 55 static constexpr array<_Tp, sizeof...(_Values)> __array = {_Values...}; 56 57 public: 58 _LIBCPP_HIDE_FROM_ABI static constexpr size_t __size() { return sizeof...(_Values); } 59 _LIBCPP_HIDE_FROM_ABI static constexpr _Tp __get(size_t __index) noexcept { return __array[__index]; } 60 61 template <size_t _Index> 62 _LIBCPP_HIDE_FROM_ABI static constexpr _Tp __get() { 63 return __get(_Index); 64 } 65 }; 66 67 // ------------------------------------------------------------------ 68 // ------------ __possibly_empty_array ----------------------------- 69 // ------------------------------------------------------------------ 70 71 // array like class which provides get function and operator [], and 72 // has a specialization for the size 0 case. 73 // This is needed to make the __maybe_static_array be truly empty, for 74 // all static values. 75 76 template <class _Tp, size_t _Size> 77 struct __possibly_empty_array { 78 _Tp __vals_[_Size]; 79 _LIBCPP_HIDE_FROM_ABI constexpr _Tp& operator[](size_t __index) { return __vals_[__index]; } 80 _LIBCPP_HIDE_FROM_ABI constexpr const _Tp& operator[](size_t __index) const { return __vals_[__index]; } 81 }; 82 83 template <class _Tp> 84 struct __possibly_empty_array<_Tp, 0> { 85 _LIBCPP_HIDE_FROM_ABI constexpr _Tp& operator[](size_t) { __libcpp_unreachable(); } 86 _LIBCPP_HIDE_FROM_ABI constexpr const _Tp& operator[](size_t) const { __libcpp_unreachable(); } 87 }; 88 89 // ------------------------------------------------------------------ 90 // ------------ static_partial_sums --------------------------------- 91 // ------------------------------------------------------------------ 92 93 // Provides a compile time partial sum one can index into 94 95 template <size_t... _Values> 96 struct __static_partial_sums { 97 _LIBCPP_HIDE_FROM_ABI static constexpr array<size_t, sizeof...(_Values)> __static_partial_sums_impl() { 98 array<size_t, sizeof...(_Values)> __values{_Values...}; 99 array<size_t, sizeof...(_Values)> __partial_sums{{}}; 100 size_t __running_sum = 0; 101 for (int __i = 0; __i != sizeof...(_Values); ++__i) { 102 __partial_sums[__i] = __running_sum; 103 __running_sum += __values[__i]; 104 } 105 return __partial_sums; 106 } 107 static constexpr array<size_t, sizeof...(_Values)> __result{__static_partial_sums_impl()}; 108 109 _LIBCPP_HIDE_FROM_ABI static constexpr size_t __get(size_t __index) { return __result[__index]; } 110 }; 111 112 // ------------------------------------------------------------------ 113 // ------------ __maybe_static_array -------------------------------- 114 // ------------------------------------------------------------------ 115 116 // array like class which has a mix of static and runtime values but 117 // only stores the runtime values. 118 // The type of the static and the runtime values can be different. 119 // The position of a dynamic value is indicated through a tag value. 120 template <class _TDynamic, class _TStatic, _TStatic _DynTag, _TStatic... _Values> 121 struct __maybe_static_array { 122 static_assert(is_convertible<_TStatic, _TDynamic>::value, 123 "__maybe_static_array: _TStatic must be convertible to _TDynamic"); 124 static_assert(is_convertible<_TDynamic, _TStatic>::value, 125 "__maybe_static_array: _TDynamic must be convertible to _TStatic"); 126 127 private: 128 // Static values member 129 static constexpr size_t __size_ = sizeof...(_Values); 130 static constexpr size_t __size_dynamic_ = ((_Values == _DynTag) + ... + 0); 131 using _StaticValues = __static_array<_TStatic, _Values...>; 132 using _DynamicValues = __possibly_empty_array<_TDynamic, __size_dynamic_>; 133 134 // Dynamic values member 135 _LIBCPP_NO_UNIQUE_ADDRESS _DynamicValues __dyn_vals_; 136 137 // static mapping of indices to the position in the dynamic values array 138 using _DynamicIdxMap = __static_partial_sums<static_cast<size_t>(_Values == _DynTag)...>; 139 140 template <size_t... Indices> 141 _LIBCPP_HIDE_FROM_ABI static constexpr _DynamicValues __zeros(index_sequence<Indices...>) noexcept { 142 return _DynamicValues{((void)Indices, 0)...}; 143 } 144 145 public: 146 _LIBCPP_HIDE_FROM_ABI constexpr __maybe_static_array() noexcept 147 : __dyn_vals_{__zeros(make_index_sequence<__size_dynamic_>())} {} 148 149 // constructors from dynamic values only -- this covers the case for rank() == 0 150 template <class... _DynVals> 151 requires(sizeof...(_DynVals) == __size_dynamic_) 152 _LIBCPP_HIDE_FROM_ABI constexpr __maybe_static_array(_DynVals... __vals) 153 : __dyn_vals_{static_cast<_TDynamic>(__vals)...} {} 154 155 template <class _Tp, size_t _Size > 156 requires(_Size == __size_dynamic_) 157 _LIBCPP_HIDE_FROM_ABI constexpr __maybe_static_array([[maybe_unused]] const span<_Tp, _Size>& __vals) { 158 if constexpr (_Size > 0) { 159 for (size_t __i = 0; __i < _Size; __i++) 160 __dyn_vals_[__i] = static_cast<_TDynamic>(__vals[__i]); 161 } 162 } 163 164 // constructors from all values -- here rank will be greater than 0 165 template <class... _DynVals> 166 requires(sizeof...(_DynVals) != __size_dynamic_) 167 _LIBCPP_HIDE_FROM_ABI constexpr __maybe_static_array(_DynVals... __vals) { 168 static_assert((sizeof...(_DynVals) == __size_), "Invalid number of values."); 169 _TDynamic __values[__size_] = {static_cast<_TDynamic>(__vals)...}; 170 for (size_t __i = 0; __i < __size_; __i++) { 171 _TStatic __static_val = _StaticValues::__get(__i); 172 if (__static_val == _DynTag) { 173 __dyn_vals_[_DynamicIdxMap::__get(__i)] = __values[__i]; 174 } 175 // Precondition check 176 else 177 _LIBCPP_ASSERT_UNCATEGORIZED(__values[__i] == static_cast<_TDynamic>(__static_val), 178 "extents construction: mismatch of provided arguments with static extents."); 179 } 180 } 181 182 template <class _Tp, size_t _Size> 183 requires(_Size != __size_dynamic_) 184 _LIBCPP_HIDE_FROM_ABI constexpr __maybe_static_array(const span<_Tp, _Size>& __vals) { 185 static_assert((_Size == __size_) || (__size_ == dynamic_extent)); 186 for (size_t __i = 0; __i < __size_; __i++) { 187 _TStatic __static_val = _StaticValues::__get(__i); 188 if (__static_val == _DynTag) { 189 __dyn_vals_[_DynamicIdxMap::__get(__i)] = static_cast<_TDynamic>(__vals[__i]); 190 } 191 // Precondition check 192 else 193 _LIBCPP_ASSERT_UNCATEGORIZED(static_cast<_TDynamic>(__vals[__i]) == static_cast<_TDynamic>(__static_val), 194 "extents construction: mismatch of provided arguments with static extents."); 195 } 196 } 197 198 // access functions 199 _LIBCPP_HIDE_FROM_ABI static constexpr _TStatic __static_value(size_t __i) noexcept { 200 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__i < __size_, "extents access: index must be less than rank"); 201 return _StaticValues::__get(__i); 202 } 203 204 _LIBCPP_HIDE_FROM_ABI constexpr _TDynamic __value(size_t __i) const { 205 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__i < __size_, "extents access: index must be less than rank"); 206 _TStatic __static_val = _StaticValues::__get(__i); 207 return __static_val == _DynTag ? __dyn_vals_[_DynamicIdxMap::__get(__i)] : static_cast<_TDynamic>(__static_val); 208 } 209 _LIBCPP_HIDE_FROM_ABI constexpr _TDynamic operator[](size_t __i) const { 210 _LIBCPP_ASSERT_VALID_ELEMENT_ACCESS(__i < __size_, "extents access: index must be less than rank"); 211 return __value(__i); 212 } 213 214 // observers 215 _LIBCPP_HIDE_FROM_ABI static constexpr size_t __size() { return __size_; } 216 _LIBCPP_HIDE_FROM_ABI static constexpr size_t __size_dynamic() { return __size_dynamic_; } 217 }; 218 219 // Function to check whether a value is representable as another type 220 // value must be a positive integer otherwise returns false 221 // if _From is not an integral, we just check positivity 222 template <integral _To, class _From> 223 requires(integral<_From>) 224 _LIBCPP_HIDE_FROM_ABI constexpr bool __is_representable_as(_From __value) { 225 using _To_u = make_unsigned_t<_To>; 226 using _From_u = make_unsigned_t<_From>; 227 if constexpr (is_signed_v<_From>) { 228 if (__value < 0) 229 return false; 230 } 231 if constexpr (static_cast<_To_u>(numeric_limits<_To>::max()) >= static_cast<_From_u>(numeric_limits<_From>::max())) { 232 return true; 233 } else { 234 return static_cast<_To_u>(numeric_limits<_To>::max()) >= static_cast<_From_u>(__value); 235 } 236 } 237 238 template <integral _To, class _From> 239 requires(!integral<_From>) 240 _LIBCPP_HIDE_FROM_ABI constexpr bool __is_representable_as(_From __value) { 241 if constexpr (is_signed_v<_To>) { 242 if (static_cast<_To>(__value) < 0) 243 return false; 244 } 245 return true; 246 } 247 248 template <integral _To, class... _From> 249 _LIBCPP_HIDE_FROM_ABI constexpr bool __are_representable_as(_From... __values) { 250 return (__mdspan_detail::__is_representable_as<_To>(__values) && ... && true); 251 } 252 253 template <integral _To, class _From, size_t _Size> 254 _LIBCPP_HIDE_FROM_ABI constexpr bool __are_representable_as(span<_From, _Size> __values) { 255 for (size_t __i = 0; __i < _Size; __i++) 256 if (!__mdspan_detail::__is_representable_as<_To>(__values[__i])) 257 return false; 258 return true; 259 } 260 261 } // namespace __mdspan_detail 262 263 // ------------------------------------------------------------------ 264 // ------------ extents --------------------------------------------- 265 // ------------------------------------------------------------------ 266 267 // Class to describe the extents of a multi dimensional array. 268 // Used by mdspan, mdarray and layout mappings. 269 // See ISO C++ standard [mdspan.extents] 270 271 template <class _IndexType, size_t... _Extents> 272 class extents { 273 public: 274 // typedefs for integral types used 275 using index_type = _IndexType; 276 using size_type = make_unsigned_t<index_type>; 277 using rank_type = size_t; 278 279 static_assert(is_integral<index_type>::value && !is_same<index_type, bool>::value, 280 "extents::index_type must be a signed or unsigned integer type"); 281 static_assert(((__mdspan_detail::__is_representable_as<index_type>(_Extents) || (_Extents == dynamic_extent)) && ...), 282 "extents ctor: arguments must be representable as index_type and nonnegative"); 283 284 private: 285 static constexpr rank_type __rank_ = sizeof...(_Extents); 286 static constexpr rank_type __rank_dynamic_ = ((_Extents == dynamic_extent) + ... + 0); 287 288 // internal storage type using __maybe_static_array 289 using _Values = __mdspan_detail::__maybe_static_array<_IndexType, size_t, dynamic_extent, _Extents...>; 290 [[no_unique_address]] _Values __vals_; 291 292 public: 293 // [mdspan.extents.obs], observers of multidimensional index space 294 _LIBCPP_HIDE_FROM_ABI static constexpr rank_type rank() noexcept { return __rank_; } 295 _LIBCPP_HIDE_FROM_ABI static constexpr rank_type rank_dynamic() noexcept { return __rank_dynamic_; } 296 297 _LIBCPP_HIDE_FROM_ABI constexpr index_type extent(rank_type __r) const noexcept { return __vals_.__value(__r); } 298 _LIBCPP_HIDE_FROM_ABI static constexpr size_t static_extent(rank_type __r) noexcept { 299 return _Values::__static_value(__r); 300 } 301 302 // [mdspan.extents.cons], constructors 303 _LIBCPP_HIDE_FROM_ABI constexpr extents() noexcept = default; 304 305 // Construction from just dynamic or all values. 306 // Precondition check is deferred to __maybe_static_array constructor 307 template <class... _OtherIndexTypes> 308 requires((is_convertible_v<_OtherIndexTypes, index_type> && ...) && 309 (is_nothrow_constructible_v<index_type, _OtherIndexTypes> && ...) && 310 (sizeof...(_OtherIndexTypes) == __rank_ || sizeof...(_OtherIndexTypes) == __rank_dynamic_)) 311 _LIBCPP_HIDE_FROM_ABI constexpr explicit extents(_OtherIndexTypes... __dynvals) noexcept 312 : __vals_(static_cast<index_type>(__dynvals)...) { 313 _LIBCPP_ASSERT_UNCATEGORIZED(__mdspan_detail::__are_representable_as<index_type>(__dynvals...), 314 "extents ctor: arguments must be representable as index_type and nonnegative"); 315 } 316 317 template <class _OtherIndexType, size_t _Size> 318 requires(is_convertible_v<_OtherIndexType, index_type> && is_nothrow_constructible_v<index_type, _OtherIndexType> && 319 (_Size == __rank_ || _Size == __rank_dynamic_)) 320 explicit(_Size != __rank_dynamic_) 321 _LIBCPP_HIDE_FROM_ABI constexpr extents(const array<_OtherIndexType, _Size>& __exts) noexcept 322 : __vals_(span(__exts)) { 323 _LIBCPP_ASSERT_UNCATEGORIZED(__mdspan_detail::__are_representable_as<index_type>(span(__exts)), 324 "extents ctor: arguments must be representable as index_type and nonnegative"); 325 } 326 327 template <class _OtherIndexType, size_t _Size> 328 requires(is_convertible_v<_OtherIndexType, index_type> && is_nothrow_constructible_v<index_type, _OtherIndexType> && 329 (_Size == __rank_ || _Size == __rank_dynamic_)) 330 explicit(_Size != __rank_dynamic_) 331 _LIBCPP_HIDE_FROM_ABI constexpr extents(const span<_OtherIndexType, _Size>& __exts) noexcept 332 : __vals_(__exts) { 333 _LIBCPP_ASSERT_UNCATEGORIZED(__mdspan_detail::__are_representable_as<index_type>(__exts), 334 "extents ctor: arguments must be representable as index_type and nonnegative"); 335 } 336 337 private: 338 // Function to construct extents storage from other extents. 339 template <size_t _DynCount, size_t _Idx, class _OtherExtents, class... _DynamicValues> 340 requires(_Idx < __rank_) 341 _LIBCPP_HIDE_FROM_ABI constexpr _Values __construct_vals_from_extents( 342 integral_constant<size_t, _DynCount>, 343 integral_constant<size_t, _Idx>, 344 const _OtherExtents& __exts, 345 _DynamicValues... __dynamic_values) noexcept { 346 if constexpr (static_extent(_Idx) == dynamic_extent) 347 return __construct_vals_from_extents( 348 integral_constant<size_t, _DynCount + 1>(), 349 integral_constant<size_t, _Idx + 1>(), 350 __exts, 351 __dynamic_values..., 352 __exts.extent(_Idx)); 353 else 354 return __construct_vals_from_extents( 355 integral_constant<size_t, _DynCount>(), integral_constant<size_t, _Idx + 1>(), __exts, __dynamic_values...); 356 } 357 358 template <size_t _DynCount, size_t _Idx, class _OtherExtents, class... _DynamicValues> 359 requires((_Idx == __rank_) && (_DynCount == __rank_dynamic_)) 360 _LIBCPP_HIDE_FROM_ABI constexpr _Values __construct_vals_from_extents( 361 integral_constant<size_t, _DynCount>, 362 integral_constant<size_t, _Idx>, 363 const _OtherExtents&, 364 _DynamicValues... __dynamic_values) noexcept { 365 return _Values{static_cast<index_type>(__dynamic_values)...}; 366 } 367 368 public: 369 // Converting constructor from other extents specializations 370 template <class _OtherIndexType, size_t... _OtherExtents> 371 requires((sizeof...(_OtherExtents) == sizeof...(_Extents)) && 372 ((_OtherExtents == dynamic_extent || _Extents == dynamic_extent || _OtherExtents == _Extents) && ...)) 373 explicit((((_Extents != dynamic_extent) && (_OtherExtents == dynamic_extent)) || ...) || 374 (static_cast<make_unsigned_t<index_type>>(numeric_limits<index_type>::max()) < 375 static_cast<make_unsigned_t<_OtherIndexType>>(numeric_limits<_OtherIndexType>::max()))) 376 _LIBCPP_HIDE_FROM_ABI constexpr extents(const extents<_OtherIndexType, _OtherExtents...>& __other) noexcept 377 : __vals_( 378 __construct_vals_from_extents(integral_constant<size_t, 0>(), integral_constant<size_t, 0>(), __other)) { 379 if constexpr (rank() > 0) { 380 for (size_t __r = 0; __r < rank(); __r++) { 381 if constexpr (static_cast<make_unsigned_t<index_type>>(numeric_limits<index_type>::max()) < 382 static_cast<make_unsigned_t<_OtherIndexType>>(numeric_limits<_OtherIndexType>::max())) { 383 _LIBCPP_ASSERT_UNCATEGORIZED(__mdspan_detail::__is_representable_as<index_type>(__other.extent(__r)), 384 "extents ctor: arguments must be representable as index_type and nonnegative"); 385 } 386 _LIBCPP_ASSERT_UNCATEGORIZED( 387 (_Values::__static_value(__r) == dynamic_extent) || 388 (static_cast<index_type>(__other.extent(__r)) == static_cast<index_type>(_Values::__static_value(__r))), 389 "extents construction: mismatch of provided arguments with static extents."); 390 } 391 } 392 } 393 394 // Comparison operator 395 template <class _OtherIndexType, size_t... _OtherExtents> 396 _LIBCPP_HIDE_FROM_ABI friend constexpr bool 397 operator==(const extents& __lhs, const extents<_OtherIndexType, _OtherExtents...>& __rhs) noexcept { 398 if constexpr (rank() != sizeof...(_OtherExtents)) { 399 return false; 400 } else { 401 for (rank_type __r = 0; __r < __rank_; __r++) { 402 // avoid warning when comparing signed and unsigner integers and pick the wider of two types 403 using _CommonType = common_type_t<index_type, _OtherIndexType>; 404 if (static_cast<_CommonType>(__lhs.extent(__r)) != static_cast<_CommonType>(__rhs.extent(__r))) { 405 return false; 406 } 407 } 408 } 409 return true; 410 } 411 }; 412 413 // Recursive helper classes to implement dextents alias for extents 414 namespace __mdspan_detail { 415 416 template <class _IndexType, size_t _Rank, class _Extents = extents<_IndexType>> 417 struct __make_dextents; 418 419 template <class _IndexType, size_t _Rank, size_t... _ExtentsPack> 420 struct __make_dextents< _IndexType, _Rank, extents<_IndexType, _ExtentsPack...>> { 421 using type = 422 typename __make_dextents< _IndexType, _Rank - 1, extents<_IndexType, dynamic_extent, _ExtentsPack...>>::type; 423 }; 424 425 template <class _IndexType, size_t... _ExtentsPack> 426 struct __make_dextents< _IndexType, 0, extents<_IndexType, _ExtentsPack...>> { 427 using type = extents<_IndexType, _ExtentsPack...>; 428 }; 429 430 } // end namespace __mdspan_detail 431 432 // [mdspan.extents.dextents], alias template 433 template <class _IndexType, size_t _Rank> 434 using dextents = typename __mdspan_detail::__make_dextents<_IndexType, _Rank>::type; 435 436 // Deduction guide for extents 437 template <class... _IndexTypes> 438 extents(_IndexTypes...) -> extents<size_t, size_t((_IndexTypes(), dynamic_extent))...>; 439 440 namespace __mdspan_detail { 441 442 // Helper type traits for identifying a class as extents. 443 template <class _Tp> 444 struct __is_extents : false_type {}; 445 446 template <class _IndexType, size_t... _ExtentsPack> 447 struct __is_extents<extents<_IndexType, _ExtentsPack...>> : true_type {}; 448 449 template <class _Tp> 450 inline constexpr bool __is_extents_v = __is_extents<_Tp>::value; 451 452 // Function to check whether a set of indices are a multidimensional 453 // index into extents. This is a word of power in the C++ standard 454 // requiring that the indices are larger than 0 and smaller than 455 // the respective extents. 456 457 template <integral _IndexType, class _From> 458 requires(integral<_From>) 459 _LIBCPP_HIDE_FROM_ABI constexpr bool __is_index_in_extent(_IndexType __extent, _From __value) { 460 if constexpr (is_signed_v<_From>) { 461 if (__value < 0) 462 return false; 463 } 464 using _Tp = common_type_t<_IndexType, _From>; 465 return static_cast<_Tp>(__value) < static_cast<_Tp>(__extent); 466 } 467 468 template <integral _IndexType, class _From> 469 requires(!integral<_From>) 470 _LIBCPP_HIDE_FROM_ABI constexpr bool __is_index_in_extent(_IndexType __extent, _From __value) { 471 if constexpr (is_signed_v<_IndexType>) { 472 if (static_cast<_IndexType>(__value) < 0) 473 return false; 474 } 475 return static_cast<_IndexType>(__value) < __extent; 476 } 477 478 template <size_t... _Idxs, class _Extents, class... _From> 479 _LIBCPP_HIDE_FROM_ABI constexpr bool 480 __is_multidimensional_index_in_impl(index_sequence<_Idxs...>, const _Extents& __ext, _From... __values) { 481 return (__mdspan_detail::__is_index_in_extent(__ext.extent(_Idxs), __values) && ...); 482 } 483 484 template <class _Extents, class... _From> 485 _LIBCPP_HIDE_FROM_ABI constexpr bool __is_multidimensional_index_in(const _Extents& __ext, _From... __values) { 486 return __mdspan_detail::__is_multidimensional_index_in_impl( 487 make_index_sequence<_Extents::rank()>(), __ext, __values...); 488 } 489 490 } // namespace __mdspan_detail 491 492 #endif // _LIBCPP_STD_VER >= 23 493 494 _LIBCPP_END_NAMESPACE_STD 495 496 _LIBCPP_POP_MACROS 497 498 #endif // _LIBCPP___MDSPAN_EXTENTS_H 499