1///////////////////////////////////////////////////////////////////////////////
2//
3// Copyright (c) 2015 Microsoft Corporation. All rights reserved.
4//
5// This code is licensed under the MIT License (MIT).
6//
7// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
8// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
9// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
10// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
11// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
12// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
13// THE SOFTWARE.
14//
15///////////////////////////////////////////////////////////////////////////////
16
17#ifndef GSL_MULTI_SPAN_H
18#define GSL_MULTI_SPAN_H
19
20#include <gsl/gsl_assert> // for Expects
21#include <gsl/gsl_byte>   // for byte
22#include <gsl/gsl_util>   // for narrow_cast
23
24#include <algorithm> // for transform, lexicographical_compare
25#include <array>     // for array
26#include <cassert>
27#include <cstddef>          // for ptrdiff_t, size_t, nullptr_t
28#include <cstdint>          // for PTRDIFF_MAX
29#include <functional>       // for divides, multiplies, minus, negate, plus
30#include <initializer_list> // for initializer_list
31#include <iterator>         // for iterator, random_access_iterator_tag
32#include <limits>           // for numeric_limits
33#include <new>
34#include <numeric>
35#include <stdexcept>
36#include <string>      // for basic_string
37#include <type_traits> // for enable_if_t, remove_cv_t, is_same, is_co...
38#include <utility>
39
40#if defined(_MSC_VER) && !defined(__clang__)
41
42// turn off some warnings that are noisy about our Expects statements
43#pragma warning(push)
44#pragma warning(disable : 4127) // conditional expression is constant
45#pragma warning(disable : 4702) // unreachable code
46
47// Turn MSVC /analyze rules that generate too much noise. TODO: fix in the tool.
48#pragma warning(disable : 26495) // uninitalized member when constructor calls constructor
49#pragma warning(disable : 26473) // in some instantiations we cast to the same type
50#pragma warning(disable : 26490) // TODO: bug in parser - attributes and templates
51#pragma warning(disable : 26465) // TODO: bug - suppression does not work on template functions
52
53#if _MSC_VER < 1910
54#pragma push_macro("constexpr")
55#define constexpr /*constexpr*/
56
57#endif                          // _MSC_VER < 1910
58#endif                          // _MSC_VER
59
60// GCC 7 does not like the signed unsigned missmatch (size_t ptrdiff_t)
61// While there is a conversion from signed to unsigned, it happens at
62// compiletime, so the compiler wouldn't have to warn indiscriminently, but
63// could check if the source value actually doesn't fit into the target type
64// and only warn in those cases.
65#if defined(__GNUC__) && __GNUC__ > 6
66#pragma GCC diagnostic push
67#pragma GCC diagnostic ignored "-Wsign-conversion"
68#endif
69
70namespace gsl
71{
72
73/*
74** begin definitions of index and bounds
75*/
76namespace details
77{
78    template <typename SizeType>
79    struct SizeTypeTraits
80    {
81        static const SizeType max_value = std::numeric_limits<SizeType>::max();
82    };
83
84    template <typename... Ts>
85    class are_integral : public std::integral_constant<bool, true>
86    {
87    };
88
89    template <typename T, typename... Ts>
90    class are_integral<T, Ts...>
91        : public std::integral_constant<bool,
92                                        std::is_integral<T>::value && are_integral<Ts...>::value>
93    {
94    };
95} // namespace details
96
97template <std::size_t Rank>
98class multi_span_index final
99{
100    static_assert(Rank > 0, "Rank must be greater than 0!");
101
102    template <std::size_t OtherRank>
103    friend class multi_span_index;
104
105public:
106    static const std::size_t rank = Rank;
107    using value_type = std::ptrdiff_t;
108    using size_type = value_type;
109    using reference = std::add_lvalue_reference_t<value_type>;
110    using const_reference = std::add_lvalue_reference_t<std::add_const_t<value_type>>;
111
112    constexpr multi_span_index() noexcept {}
113
114    constexpr multi_span_index(const value_type (&values)[Rank]) noexcept
115    {
116        GSL_SUPPRESS(bounds.1) // NO-FORMAT: attribute
117        GSL_SUPPRESS(bounds.3) // NO-FORMAT: attribute
118        std::copy(values, values + Rank, elems);
119    }
120
121    template <typename... Ts, typename = std::enable_if_t<(sizeof...(Ts) == Rank) &&
122                                                          details::are_integral<Ts...>::value>>
123    constexpr multi_span_index(Ts... ds) noexcept : elems{narrow_cast<value_type>(ds)...}
124    {}
125
126    constexpr multi_span_index(const multi_span_index& other) noexcept = default;
127
128    constexpr multi_span_index& operator=(const multi_span_index& rhs) noexcept = default;
129
130    // Preconditions: component_idx < rank
131    GSL_SUPPRESS(bounds.2) // NO-FORMAT: attribute
132    GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
133    constexpr reference operator[](std::size_t component_idx)
134    {
135        Expects(component_idx < Rank); // Component index must be less than rank
136        return elems[component_idx];
137    }
138
139    // Preconditions: component_idx < rank
140    GSL_SUPPRESS(bounds.2) // NO-FORMAT: attribute
141    GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
142    constexpr const_reference operator[](std::size_t component_idx) const
143    {
144        Expects(component_idx < Rank); // Component index must be less than rank
145        return elems[component_idx];
146    }
147
148    GSL_SUPPRESS(bounds.1) // NO-FORMAT: attribute
149    GSL_SUPPRESS(bounds.3) // NO-FORMAT: attribute
150    constexpr bool operator==(const multi_span_index& rhs) const
151    {
152        return std::equal(elems, elems + rank, rhs.elems);
153    }
154
155    constexpr bool operator!=(const multi_span_index& rhs) const
156    {
157        return !(*this == rhs);
158    }
159
160    constexpr multi_span_index operator+() const noexcept { return *this; }
161
162    constexpr multi_span_index operator-() const
163    {
164        multi_span_index ret = *this;
165        std::transform(ret, ret + rank, ret, std::negate<value_type>{});
166        return ret;
167    }
168
169    constexpr multi_span_index operator+(const multi_span_index& rhs) const
170    {
171        multi_span_index ret = *this;
172        ret += rhs;
173        return ret;
174    }
175
176    constexpr multi_span_index operator-(const multi_span_index& rhs) const
177    {
178        multi_span_index ret = *this;
179        ret -= rhs;
180        return ret;
181    }
182
183    constexpr multi_span_index& operator+=(const multi_span_index& rhs)
184    {
185        GSL_SUPPRESS(bounds.1) // NO-FORMAT: attribute
186        GSL_SUPPRESS(bounds.3) // NO-FORMAT: attribute
187        std::transform(elems, elems + rank, rhs.elems, elems,
188                       std::plus<value_type>{});
189        return *this;
190    }
191
192    constexpr multi_span_index& operator-=(const multi_span_index& rhs)
193    {
194        GSL_SUPPRESS(bounds.1) // NO-FORMAT: attribute
195        GSL_SUPPRESS(bounds.3) // NO-FORMAT: attribute
196        std::transform(elems, elems + rank, rhs.elems, elems, std::minus<value_type>{});
197        return *this;
198    }
199
200    constexpr multi_span_index operator*(value_type v) const
201    {
202        multi_span_index ret = *this;
203        ret *= v;
204        return ret;
205    }
206
207    constexpr multi_span_index operator/(value_type v) const
208    {
209        multi_span_index ret = *this;
210        ret /= v;
211        return ret;
212    }
213
214    friend constexpr multi_span_index operator*(value_type v, const multi_span_index& rhs)
215    {
216        return rhs * v;
217    }
218
219    constexpr multi_span_index& operator*=(value_type v)
220    {
221        GSL_SUPPRESS(bounds.1) // NO-FORMAT: attribute
222        GSL_SUPPRESS(bounds.3) // NO-FORMAT: attribute
223        std::transform(elems, elems + rank, elems,
224                       [v](value_type x) { return std::multiplies<value_type>{}(x, v); });
225        return *this;
226    }
227
228    constexpr multi_span_index& operator/=(value_type v)
229    {
230        GSL_SUPPRESS(bounds.1) // NO-FORMAT: attribute
231        GSL_SUPPRESS(bounds.3) // NO-FORMAT: attribute
232        std::transform(elems, elems + rank, elems,
233                       [v](value_type x) { return std::divides<value_type>{}(x, v); });
234        return *this;
235    }
236
237private:
238    value_type elems[Rank] = {};
239};
240
241#if !defined(_MSC_VER) || _MSC_VER >= 1910
242
243struct static_bounds_dynamic_range_t
244{
245    template <typename T, typename = std::enable_if_t<std::is_integral<T>::value>>
246    constexpr operator T() const noexcept
247    {
248        return narrow_cast<T>(-1);
249    }
250};
251
252constexpr bool operator==(static_bounds_dynamic_range_t, static_bounds_dynamic_range_t) noexcept
253{
254    return true;
255}
256
257constexpr bool operator!=(static_bounds_dynamic_range_t, static_bounds_dynamic_range_t) noexcept
258{
259    return false;
260}
261
262template <typename T, typename = std::enable_if_t<std::is_integral<T>::value>>
263constexpr bool operator==(static_bounds_dynamic_range_t, T other) noexcept
264{
265    return narrow_cast<T>(-1) == other;
266}
267
268template <typename T, typename = std::enable_if_t<std::is_integral<T>::value>>
269constexpr bool operator==(T left, static_bounds_dynamic_range_t right) noexcept
270{
271    return right == left;
272}
273
274template <typename T, typename = std::enable_if_t<std::is_integral<T>::value>>
275constexpr bool operator!=(static_bounds_dynamic_range_t, T other) noexcept
276{
277    return narrow_cast<T>(-1) != other;
278}
279
280template <typename T, typename = std::enable_if_t<std::is_integral<T>::value>>
281constexpr bool operator!=(T left, static_bounds_dynamic_range_t right) noexcept
282{
283    return right != left;
284}
285
286constexpr static_bounds_dynamic_range_t dynamic_range{};
287#else
288const std::ptrdiff_t dynamic_range = -1;
289#endif
290
291struct generalized_mapping_tag
292{
293};
294struct contiguous_mapping_tag : generalized_mapping_tag
295{
296};
297
298namespace details
299{
300
301    template <std::ptrdiff_t Left, std::ptrdiff_t Right>
302    struct LessThan
303    {
304        static const bool value = Left < Right;
305    };
306
307    template <std::ptrdiff_t... Ranges>
308    struct BoundsRanges
309    {
310        using size_type = std::ptrdiff_t;
311        static const size_type Depth = 0;
312        static const size_type DynamicNum = 0;
313        static const size_type CurrentRange = 1;
314        static const size_type TotalSize = 1;
315
316        // TODO : following signature is for work around VS bug
317        template <typename OtherRange>
318        constexpr BoundsRanges(const OtherRange&, bool /* firstLevel */)
319        {}
320
321        constexpr BoundsRanges(const std::ptrdiff_t* const) {}
322        constexpr BoundsRanges() noexcept = default;
323
324        template <typename T, std::size_t Dim>
325        constexpr void serialize(T&) const
326        {}
327
328        template <typename T, std::size_t Dim>
329        constexpr size_type linearize(const T&) const
330        {
331            return 0;
332        }
333
334        template <typename T, std::size_t Dim>
335        constexpr size_type contains(const T&) const
336        {
337            return -1;
338        }
339
340        constexpr size_type elementNum(std::size_t) const noexcept { return 0; }
341
342        constexpr size_type totalSize() const noexcept { return TotalSize; }
343
344        constexpr bool operator==(const BoundsRanges&) const noexcept { return true; }
345    };
346
347    template <std::ptrdiff_t... RestRanges>
348    struct BoundsRanges<dynamic_range, RestRanges...> : BoundsRanges<RestRanges...>
349    {
350        using Base = BoundsRanges<RestRanges...>;
351        using size_type = std::ptrdiff_t;
352        static const std::size_t Depth = Base::Depth + 1;
353        static const std::size_t DynamicNum = Base::DynamicNum + 1;
354        static const size_type CurrentRange = dynamic_range;
355        static const size_type TotalSize = dynamic_range;
356
357    private:
358        size_type m_bound;
359
360    public:
361        GSL_SUPPRESS(f.23) // NO-FORMAT: attribute // this pointer type is cannot be assigned nullptr - issue in not_null
362        GSL_SUPPRESS(bounds.1)  // NO-FORMAT: attribute
363        constexpr BoundsRanges(const std::ptrdiff_t* const arr)
364            : Base(arr + 1), m_bound(*arr * this->Base::totalSize())
365        {
366            Expects(0 <= *arr);
367        }
368
369        constexpr BoundsRanges() noexcept : m_bound(0) {}
370
371        template <std::ptrdiff_t OtherRange, std::ptrdiff_t... RestOtherRanges>
372        constexpr BoundsRanges(const BoundsRanges<OtherRange, RestOtherRanges...>& other,
373                     bool /* firstLevel */ = true)
374            : Base(static_cast<const BoundsRanges<RestOtherRanges...>&>(other), false)
375            , m_bound(other.totalSize())
376        {}
377
378        template <typename T, std::size_t Dim = 0>
379        constexpr void serialize(T& arr) const
380        {
381            arr[Dim] = elementNum();
382            this->Base::template serialize<T, Dim + 1>(arr);
383        }
384
385        template <typename T, std::size_t Dim = 0>
386        GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
387        constexpr size_type linearize(const T& arr) const
388        {
389            const size_type index = this->Base::totalSize() * arr[Dim];
390            Expects(index < m_bound);
391            return index + this->Base::template linearize<T, Dim + 1>(arr);
392        }
393
394        template <typename T, std::size_t Dim = 0>
395        constexpr size_type contains(const T& arr) const
396        {
397            const ptrdiff_t last = this->Base::template contains<T, Dim + 1>(arr);
398            if (last == -1) return -1;
399            const ptrdiff_t cur = this->Base::totalSize() * arr[Dim];
400            return cur < m_bound ? cur + last : -1;
401        }
402
403        GSL_SUPPRESS(c.128) // NO-FORMAT: attribute // no pointers to BoundsRanges should be ever used
404        constexpr size_type totalSize() const noexcept
405        {
406            return m_bound;
407        }
408
409        GSL_SUPPRESS(c.128) // NO-FORMAT: attribute // no pointers to BoundsRanges should be ever used
410        constexpr size_type elementNum() const noexcept
411        {
412            return totalSize() / this->Base::totalSize();
413        }
414
415        GSL_SUPPRESS(c.128) // NO-FORMAT: attribute // no pointers to BoundsRanges should be ever used
416        constexpr size_type elementNum(std::size_t dim) const noexcept
417        {
418            if (dim > 0)
419                return this->Base::elementNum(dim - 1);
420            else
421                return elementNum();
422        }
423
424        constexpr bool operator==(const BoundsRanges& rhs) const noexcept
425        {
426            return m_bound == rhs.m_bound &&
427                   static_cast<const Base&>(*this) == static_cast<const Base&>(rhs);
428        }
429    };
430
431    template <std::ptrdiff_t CurRange, std::ptrdiff_t... RestRanges>
432    struct BoundsRanges<CurRange, RestRanges...> : BoundsRanges<RestRanges...>
433    {
434        using Base = BoundsRanges<RestRanges...>;
435        using size_type = std::ptrdiff_t;
436        static const std::size_t Depth = Base::Depth + 1;
437        static const std::size_t DynamicNum = Base::DynamicNum;
438        static const size_type CurrentRange = CurRange;
439        static const size_type TotalSize =
440            Base::TotalSize == dynamic_range ? dynamic_range : CurrentRange * Base::TotalSize;
441
442        constexpr BoundsRanges(const std::ptrdiff_t* const arr) : Base(arr) {}
443        constexpr BoundsRanges() = default;
444
445        template <std::ptrdiff_t OtherRange, std::ptrdiff_t... RestOtherRanges>
446        constexpr BoundsRanges(const BoundsRanges<OtherRange, RestOtherRanges...>& other,
447                     bool firstLevel = true)
448            : Base(static_cast<const BoundsRanges<RestOtherRanges...>&>(other), false)
449        {
450            GSL_SUPPRESS(type.4) // NO-FORMAT: attribute // TODO: false positive
451            (void) firstLevel;
452        }
453
454        template <typename T, std::size_t Dim = 0>
455        constexpr void serialize(T& arr) const
456        {
457            arr[Dim] = elementNum();
458            this->Base::template serialize<T, Dim + 1>(arr);
459        }
460
461        template <typename T, std::size_t Dim = 0>
462        constexpr size_type linearize(const T& arr) const
463        {
464            GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
465            Expects(arr[Dim] >= 0 && arr[Dim] < CurrentRange); // Index is out of range
466            GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
467            const ptrdiff_t d = arr[Dim];
468            return this->Base::totalSize() * d +
469                   this->Base::template linearize<T, Dim + 1>(arr);
470        }
471
472        template <typename T, std::size_t Dim = 0>
473        constexpr size_type contains(const T& arr) const
474        {
475            if (arr[Dim] >= CurrentRange) return -1;
476            const size_type last = this->Base::template contains<T, Dim + 1>(arr);
477            if (last == -1) return -1;
478            return this->Base::totalSize() * arr[Dim] + last;
479        }
480
481        GSL_SUPPRESS(c.128) // NO-FORMAT: attribute // no pointers to BoundsRanges should be ever used
482        constexpr size_type totalSize() const noexcept
483        {
484            return CurrentRange * this->Base::totalSize();
485        }
486
487        GSL_SUPPRESS(c.128) // NO-FORMAT: attribute // no pointers to BoundsRanges should be ever used
488        constexpr size_type elementNum() const noexcept
489        {
490            return CurrentRange;
491        }
492
493        GSL_SUPPRESS(c.128) // NO-FORMAT: attribute // no pointers to BoundsRanges should be ever used
494        constexpr size_type elementNum(std::size_t dim) const noexcept
495        {
496            if (dim > 0)
497                return this->Base::elementNum(dim - 1);
498            else
499                return elementNum();
500        }
501
502        constexpr bool operator==(const BoundsRanges& rhs) const noexcept
503        {
504            return static_cast<const Base&>(*this) == static_cast<const Base&>(rhs);
505        }
506    };
507
508    template <typename SourceType, typename TargetType>
509    struct BoundsRangeConvertible
510        : public std::integral_constant<bool, (SourceType::TotalSize >= TargetType::TotalSize ||
511                                               TargetType::TotalSize == dynamic_range ||
512                                               SourceType::TotalSize == dynamic_range ||
513                                               TargetType::TotalSize == 0)>
514    {
515    };
516
517    template <typename TypeChain>
518    struct TypeListIndexer
519    {
520        const TypeChain& obj_;
521        TypeListIndexer(const TypeChain& obj) : obj_(obj) {}
522
523        template <std::size_t N>
524        const TypeChain& getObj(std::true_type)
525        {
526            return obj_;
527        }
528
529        template <std::size_t N, typename MyChain = TypeChain,
530                  typename MyBase = typename MyChain::Base>
531        auto getObj(std::false_type)
532            -> decltype(TypeListIndexer<MyBase>(static_cast<const MyBase&>(obj_)).template get<N>())
533        {
534            return TypeListIndexer<MyBase>(static_cast<const MyBase&>(obj_)).template get<N>();
535        }
536
537        template <std::size_t N>
538        auto get() -> decltype(getObj<N - 1>(std::integral_constant<bool, N == 0>()))
539        {
540            return getObj<N - 1>(std::integral_constant<bool, N == 0>());
541        }
542    };
543
544    template <typename TypeChain>
545    TypeListIndexer<TypeChain> createTypeListIndexer(const TypeChain& obj)
546    {
547        return TypeListIndexer<TypeChain>(obj);
548    }
549
550    template <std::size_t Rank, bool Enabled = (Rank > 1),
551              typename Ret = std::enable_if_t<Enabled, multi_span_index<Rank - 1>>>
552    constexpr Ret shift_left(const multi_span_index<Rank>& other) noexcept
553    {
554        Ret ret{};
555        for (std::size_t i = 0; i < Rank - 1; ++i)
556        {
557            GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
558                ret[i] = other[i + 1];
559        }
560        return ret;
561    }
562} // namespace details
563
564template <typename IndexType>
565class bounds_iterator;
566
567template <std::ptrdiff_t... Ranges>
568class static_bounds
569{
570public:
571    static_bounds(const details::BoundsRanges<Ranges...>&) {}
572};
573
574template <std::ptrdiff_t FirstRange, std::ptrdiff_t... RestRanges>
575class static_bounds<FirstRange, RestRanges...>
576{
577    using MyRanges = details::BoundsRanges<FirstRange, RestRanges...>;
578
579    MyRanges m_ranges;
580    constexpr static_bounds(const MyRanges& range) noexcept : m_ranges(range) {}
581
582    template <std::ptrdiff_t... OtherRanges>
583    friend class static_bounds;
584
585public:
586    static const std::size_t rank = MyRanges::Depth;
587    static const std::size_t dynamic_rank = MyRanges::DynamicNum;
588    static const std::ptrdiff_t static_size = MyRanges::TotalSize;
589
590    using size_type = std::ptrdiff_t;
591    using index_type = multi_span_index<rank>;
592    using const_index_type = std::add_const_t<index_type>;
593    using iterator = bounds_iterator<const_index_type>;
594    using const_iterator = bounds_iterator<const_index_type>;
595    using difference_type = std::ptrdiff_t;
596    using sliced_type = static_bounds<RestRanges...>;
597    using mapping_type = contiguous_mapping_tag;
598
599    constexpr static_bounds() /*noexcept*/ = default;
600
601    template <typename SourceType, typename TargetType, std::size_t Rank>
602    struct BoundsRangeConvertible2;
603
604    template <std::size_t Rank, typename SourceType, typename TargetType,
605              typename Ret = BoundsRangeConvertible2<typename SourceType::Base,
606                                                     typename TargetType::Base, Rank>>
607    static auto helpBoundsRangeConvertible(SourceType, TargetType, std::true_type) -> Ret;
608
609    template <std::size_t Rank, typename SourceType, typename TargetType>
610    static auto helpBoundsRangeConvertible(SourceType, TargetType, ...) -> std::false_type;
611
612    template <typename SourceType, typename TargetType, std::size_t Rank>
613    struct BoundsRangeConvertible2
614        : decltype(helpBoundsRangeConvertible<Rank - 1>(
615              SourceType(), TargetType(),
616              std::integral_constant<bool,
617                                     SourceType::Depth == TargetType::Depth &&
618                                         (SourceType::CurrentRange == TargetType::CurrentRange ||
619                                          TargetType::CurrentRange == dynamic_range ||
620                                          SourceType::CurrentRange == dynamic_range)>()))
621    {
622    };
623
624    template <typename SourceType, typename TargetType>
625    struct BoundsRangeConvertible2<SourceType, TargetType, 0> : std::true_type
626    {
627    };
628
629    template <typename SourceType, typename TargetType, std::ptrdiff_t Rank = TargetType::Depth>
630    struct BoundsRangeConvertible
631        : decltype(helpBoundsRangeConvertible<Rank - 1>(
632              SourceType(), TargetType(),
633              std::integral_constant<bool,
634                                     SourceType::Depth == TargetType::Depth &&
635                                         (!details::LessThan<SourceType::CurrentRange,
636                                                             TargetType::CurrentRange>::value ||
637                                          TargetType::CurrentRange == dynamic_range ||
638                                          SourceType::CurrentRange == dynamic_range)>()))
639    {
640    };
641
642    template <typename SourceType, typename TargetType>
643    struct BoundsRangeConvertible<SourceType, TargetType, 0> : std::true_type
644    {
645    };
646
647    template <std::ptrdiff_t... Ranges,
648              typename = std::enable_if_t<details::BoundsRangeConvertible<
649                  details::BoundsRanges<Ranges...>,
650                  details::BoundsRanges<FirstRange, RestRanges...>>::value>>
651    constexpr static_bounds(const static_bounds<Ranges...>& other) : m_ranges(other.m_ranges)
652    {
653        Expects((MyRanges::DynamicNum == 0 && details::BoundsRanges<Ranges...>::DynamicNum == 0) ||
654                MyRanges::DynamicNum > 0 || other.m_ranges.totalSize() >= m_ranges.totalSize());
655    }
656
657    constexpr static_bounds(std::initializer_list<size_type> il) : m_ranges(il.begin())
658    {
659        // Size of the initializer list must match the rank of the array
660        Expects((MyRanges::DynamicNum == 0 && il.size() == 1 && *il.begin() == static_size) ||
661                MyRanges::DynamicNum == il.size());
662        // Size of the range must be less than the max element of the size type
663        Expects(m_ranges.totalSize() <= PTRDIFF_MAX);
664    }
665
666    constexpr sliced_type slice() const noexcept
667    {
668        return sliced_type{static_cast<const details::BoundsRanges<RestRanges...>&>(m_ranges)};
669    }
670
671    constexpr size_type stride() const noexcept { return rank > 1 ? slice().size() : 1; }
672
673    constexpr size_type size() const noexcept { return m_ranges.totalSize(); }
674
675    constexpr size_type total_size() const noexcept { return m_ranges.totalSize(); }
676
677    constexpr size_type linearize(const index_type& idx) const { return m_ranges.linearize(idx); }
678
679    constexpr bool contains(const index_type& idx) const noexcept
680    {
681        return m_ranges.contains(idx) != -1;
682    }
683
684    constexpr size_type operator[](std::size_t idx) const noexcept
685    {
686        return m_ranges.elementNum(idx);
687    }
688
689    template <std::size_t Dim = 0>
690    constexpr size_type extent() const noexcept
691    {
692        static_assert(Dim < rank,
693                      "dimension should be less than rank (dimension count starts from 0)");
694        return details::createTypeListIndexer(m_ranges).template get<Dim>().elementNum();
695    }
696
697    template <typename IntType>
698    constexpr size_type extent(IntType dim) const
699    {
700        static_assert(std::is_integral<IntType>::value,
701                      "Dimension parameter must be supplied as an integral type.");
702        auto real_dim = narrow_cast<std::size_t>(dim);
703        Expects(real_dim < rank);
704
705        return m_ranges.elementNum(real_dim);
706    }
707
708    constexpr index_type index_bounds() const noexcept
709    {
710        size_type extents[rank] = {};
711        m_ranges.serialize(extents);
712        return {extents};
713    }
714
715    template <std::ptrdiff_t... Ranges>
716    constexpr bool operator==(const static_bounds<Ranges...>& rhs) const noexcept
717    {
718        return this->size() == rhs.size();
719    }
720
721    template <std::ptrdiff_t... Ranges>
722    constexpr bool operator!=(const static_bounds<Ranges...>& rhs) const noexcept
723    {
724        return !(*this == rhs);
725    }
726
727    constexpr const_iterator begin() const noexcept
728    {
729        return const_iterator(*this, index_type{});
730    }
731
732    constexpr const_iterator end() const noexcept
733    {
734        return const_iterator(*this, this->index_bounds());
735    }
736};
737
738template <std::size_t Rank>
739class strided_bounds {
740    template <std::size_t OtherRank>
741    friend class strided_bounds;
742
743public:
744    static const std::size_t rank = Rank;
745    using value_type = std::ptrdiff_t;
746    using reference = std::add_lvalue_reference_t<value_type>;
747    using const_reference = std::add_const_t<reference>;
748    using size_type = value_type;
749    using difference_type = value_type;
750    using index_type = multi_span_index<rank>;
751    using const_index_type = std::add_const_t<index_type>;
752    using iterator = bounds_iterator<const_index_type>;
753    using const_iterator = bounds_iterator<const_index_type>;
754    static const value_type dynamic_rank = rank;
755    static const value_type static_size = dynamic_range;
756    using sliced_type = std::conditional_t<rank != 0, strided_bounds<rank - 1>, void>;
757    using mapping_type = generalized_mapping_tag;
758
759    constexpr strided_bounds(const strided_bounds&) noexcept = default;
760
761    constexpr strided_bounds& operator=(const strided_bounds&) noexcept = default;
762
763    constexpr strided_bounds(const value_type (&values)[rank], index_type strides)
764        : m_extents(values), m_strides(std::move(strides))
765    {}
766
767    constexpr strided_bounds(const index_type& extents, const index_type& strides) noexcept
768        : m_extents(extents), m_strides(strides)
769    {
770    }
771
772    constexpr index_type strides() const noexcept { return m_strides; }
773
774    GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
775    constexpr size_type total_size() const noexcept
776    {
777        size_type ret = 0;
778        for (std::size_t i = 0; i < rank; ++i) { ret += (m_extents[i] - 1) * m_strides[i]; }
779        return ret + 1;
780    }
781
782    GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
783    constexpr size_type size() const noexcept
784    {
785        size_type ret = 1;
786        for (std::size_t i = 0; i < rank; ++i) { ret *= m_extents[i]; }
787        return ret;
788    }
789
790    constexpr bool contains(const index_type& idx) const noexcept
791    {
792        for (std::size_t i = 0; i < rank; ++i)
793        {
794            if (idx[i] < 0 || idx[i] >= m_extents[i]) return false;
795        }
796        return true;
797    }
798
799    GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
800    constexpr size_type linearize(const index_type& idx) const
801    {
802        size_type ret = 0;
803        for (std::size_t i = 0; i < rank; i++)
804        {
805            Expects(idx[i] < m_extents[i]); // index is out of bounds of the array
806            ret += idx[i] * m_strides[i];
807        }
808        return ret;
809    }
810
811    GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
812    constexpr size_type stride() const noexcept { return m_strides[0]; }
813
814    template <bool Enabled = (rank > 1), typename Ret = std::enable_if_t<Enabled, sliced_type>>
815    constexpr sliced_type slice() const
816    {
817        return {details::shift_left(m_extents), details::shift_left(m_strides)};
818    }
819
820    template <std::size_t Dim = 0>
821
822    GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
823    constexpr size_type extent() const noexcept
824    {
825        static_assert(Dim < Rank,
826                      "dimension should be less than rank (dimension count starts from 0)");
827        return m_extents[Dim];
828    }
829
830    constexpr index_type index_bounds() const noexcept { return m_extents; }
831
832    constexpr const_iterator begin() const noexcept { return const_iterator{*this, index_type{}}; }
833
834    constexpr const_iterator end() const noexcept { return const_iterator{*this, index_bounds()}; }
835
836private:
837    index_type m_extents;
838    index_type m_strides;
839};
840
841template <typename T>
842struct is_bounds : std::integral_constant<bool, false>
843{
844};
845template <std::ptrdiff_t... Ranges>
846struct is_bounds<static_bounds<Ranges...>> : std::integral_constant<bool, true>
847{
848};
849template <std::size_t Rank>
850struct is_bounds<strided_bounds<Rank>> : std::integral_constant<bool, true>
851{
852};
853
854template <typename IndexType>
855class bounds_iterator
856{
857public:
858    static const std::size_t rank = IndexType::rank;
859    using iterator_category = std::random_access_iterator_tag;
860    using value_type = IndexType;
861    using difference_type = std::ptrdiff_t;
862    using pointer = value_type*;
863    using reference = value_type&;
864    using index_type = value_type;
865    using index_size_type = typename IndexType::value_type;
866    template <typename Bounds>
867    explicit bounds_iterator(const Bounds& bnd, value_type curr) noexcept
868        : boundary_(bnd.index_bounds()), curr_(std::move(curr))
869    {
870        static_assert(is_bounds<Bounds>::value, "Bounds type must be provided");
871    }
872
873    constexpr reference operator*() const noexcept { return curr_; }
874
875    constexpr pointer operator->() const noexcept { return &curr_; }
876
877    GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
878    GSL_SUPPRESS(bounds.2) // NO-FORMAT: attribute
879    constexpr bounds_iterator& operator++() noexcept
880
881    {
882        for (std::size_t i = rank; i-- > 0;)
883        {
884            if (curr_[i] < boundary_[i] - 1)
885            {
886                curr_[i]++;
887                return *this;
888            }
889            curr_[i] = 0;
890        }
891        // If we're here we've wrapped over - set to past-the-end.
892        curr_ = boundary_;
893        return *this;
894    }
895
896    constexpr bounds_iterator operator++(int) noexcept
897    {
898        auto ret = *this;
899        ++(*this);
900        return ret;
901    }
902
903    GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
904    constexpr bounds_iterator& operator--()
905    {
906        if (!less(curr_, boundary_))
907        {
908            // if at the past-the-end, set to last element
909            for (std::size_t i = 0; i < rank; ++i) { curr_[i] = boundary_[i] - 1; }
910            return *this;
911        }
912        for (std::size_t i = rank; i-- > 0;)
913        {
914            if (curr_[i] >= 1)
915            {
916                curr_[i]--;
917                return *this;
918            }
919            curr_[i] = boundary_[i] - 1;
920        }
921        // If we're here the preconditions were violated
922        // "pre: there exists s such that r == ++s"
923        Expects(false);
924        return *this;
925    }
926
927    constexpr bounds_iterator operator--(int) noexcept
928    {
929        auto ret = *this;
930        --(*this);
931        return ret;
932    }
933
934    constexpr bounds_iterator operator+(difference_type n) const noexcept
935    {
936        bounds_iterator ret{*this};
937        return ret += n;
938    }
939
940    GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
941    constexpr bounds_iterator& operator+=(difference_type n)
942    {
943        auto linear_idx = linearize(curr_) + n;
944        std::remove_const_t<value_type> stride = 0;
945        stride[rank - 1] = 1;
946        for (std::size_t i = rank - 1; i-- > 0;) { stride[i] = stride[i + 1] * boundary_[i + 1]; }
947        for (std::size_t i = 0; i < rank; ++i)
948        {
949            curr_[i] = linear_idx / stride[i];
950            linear_idx = linear_idx % stride[i];
951        }
952        // index is out of bounds of the array
953        Expects(!less(curr_, index_type{}) && !less(boundary_, curr_));
954        return *this;
955    }
956
957    constexpr bounds_iterator operator-(difference_type n) const noexcept
958    {
959        bounds_iterator ret{*this};
960        return ret -= n;
961    }
962
963    constexpr bounds_iterator& operator-=(difference_type n) noexcept { return *this += -n; }
964
965    constexpr difference_type operator-(const bounds_iterator& rhs) const noexcept
966    {
967        return linearize(curr_) - linearize(rhs.curr_);
968    }
969
970    constexpr value_type operator[](difference_type n) const noexcept { return *(*this + n); }
971
972    constexpr bool operator==(const bounds_iterator& rhs) const noexcept
973    {
974        return curr_ == rhs.curr_;
975    }
976
977
978    constexpr bool operator!=(const bounds_iterator& rhs) const noexcept { return !(*this == rhs); }
979
980    constexpr bool operator<(const bounds_iterator& rhs) const noexcept
981    {
982        return less(curr_, rhs.curr_);
983    }
984
985    constexpr bool operator<=(const bounds_iterator& rhs) const noexcept { return !(rhs < *this); }
986
987    constexpr bool operator>(const bounds_iterator& rhs) const noexcept { return rhs < *this; }
988
989    constexpr bool operator>=(const bounds_iterator& rhs) const noexcept { return !(rhs > *this); }
990
991    void swap(bounds_iterator& rhs) noexcept
992    {
993        std::swap(boundary_, rhs.boundary_);
994        std::swap(curr_, rhs.curr_);
995    }
996
997private:
998
999    GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
1000    constexpr bool less(index_type& one, index_type& other) const noexcept
1001    {
1002        for (std::size_t i = 0; i < rank; ++i)
1003        {
1004            if (one[i] < other[i]) return true;
1005        }
1006        return false;
1007    }
1008
1009    GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
1010    constexpr index_size_type linearize(const value_type& idx) const noexcept
1011    {
1012        // TODO: Smarter impl.
1013        // Check if past-the-end
1014        index_size_type multiplier = 1;
1015        index_size_type res = 0;
1016        if (!less(idx, boundary_))
1017        {
1018            res = 1;
1019            for (std::size_t i = rank; i-- > 0;)
1020            {
1021                res += (idx[i] - 1) * multiplier;
1022                multiplier *= boundary_[i];
1023            }
1024        }
1025        else
1026        {
1027            for (std::size_t i = rank; i-- > 0;)
1028            {
1029                res += idx[i] * multiplier;
1030                multiplier *= boundary_[i];
1031            }
1032        }
1033        return res;
1034    }
1035
1036    value_type boundary_;
1037    std::remove_const_t<value_type> curr_;
1038};
1039
1040template <typename IndexType>
1041bounds_iterator<IndexType> operator+(typename bounds_iterator<IndexType>::difference_type n,
1042                                     const bounds_iterator<IndexType>& rhs) noexcept
1043{
1044    return rhs + n;
1045}
1046
1047namespace details
1048{
1049    template <typename Bounds>
1050    constexpr std::enable_if_t<
1051        std::is_same<typename Bounds::mapping_type, generalized_mapping_tag>::value,
1052        typename Bounds::index_type>
1053    make_stride(const Bounds& bnd) noexcept
1054    {
1055        return bnd.strides();
1056    }
1057
1058    // Make a stride vector from bounds, assuming contiguous memory.
1059    template <typename Bounds>
1060    constexpr std::enable_if_t<
1061        std::is_same<typename Bounds::mapping_type, contiguous_mapping_tag>::value,
1062        typename Bounds::index_type>
1063    make_stride(const Bounds& bnd) noexcept
1064    {
1065        auto extents = bnd.index_bounds();
1066        typename Bounds::size_type stride[Bounds::rank] = {};
1067
1068        stride[Bounds::rank - 1] = 1;
1069        for (std::size_t i = 1; i < Bounds::rank; ++i)
1070        {
1071            GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
1072            GSL_SUPPRESS(bounds.2) // NO-FORMAT: attribute
1073            stride[Bounds::rank - i - 1] = stride[Bounds::rank - i] * extents[Bounds::rank - i];
1074        }
1075        return {stride};
1076    }
1077
1078    template <typename BoundsSrc, typename BoundsDest>
1079    void verifyBoundsReshape(const BoundsSrc& src, const BoundsDest& dest)
1080    {
1081        static_assert(is_bounds<BoundsSrc>::value && is_bounds<BoundsDest>::value,
1082                      "The src type and dest type must be bounds");
1083        static_assert(std::is_same<typename BoundsSrc::mapping_type, contiguous_mapping_tag>::value,
1084                      "The source type must be a contiguous bounds");
1085        static_assert(BoundsDest::static_size == dynamic_range ||
1086                          BoundsSrc::static_size == dynamic_range ||
1087                          BoundsDest::static_size == BoundsSrc::static_size,
1088                      "The source bounds must have same size as dest bounds");
1089        Expects(src.size() == dest.size());
1090    }
1091
1092} // namespace details
1093
1094template <typename Span>
1095class contiguous_span_iterator;
1096template <typename Span>
1097class general_span_iterator;
1098
1099template <std::ptrdiff_t DimSize = dynamic_range>
1100struct dim_t
1101{
1102    static const std::ptrdiff_t value = DimSize;
1103};
1104template <>
1105struct dim_t<dynamic_range>
1106{
1107    static const std::ptrdiff_t value = dynamic_range;
1108    const std::ptrdiff_t dvalue;
1109    constexpr dim_t(std::ptrdiff_t size) noexcept : dvalue(size) {}
1110};
1111
1112template <std::ptrdiff_t N, class = std::enable_if_t<(N >= 0)>>
1113constexpr dim_t<N> dim() noexcept
1114{
1115    return dim_t<N>();
1116}
1117
1118template <std::ptrdiff_t N = dynamic_range, class = std::enable_if_t<N == dynamic_range>>
1119constexpr dim_t<N> dim(std::ptrdiff_t n) noexcept
1120{
1121    return dim_t<>(n);
1122}
1123
1124template <typename ValueType, std::ptrdiff_t FirstDimension = dynamic_range,
1125          std::ptrdiff_t... RestDimensions>
1126class multi_span;
1127template <typename ValueType, std::size_t Rank>
1128class strided_span;
1129
1130namespace details
1131{
1132    template <typename T, typename = std::true_type>
1133    struct SpanTypeTraits
1134    {
1135        using value_type = T;
1136        using size_type = std::size_t;
1137    };
1138
1139    template <typename Traits>
1140    struct SpanTypeTraits<Traits, typename std::is_reference<typename Traits::span_traits&>::type>
1141    {
1142        using value_type = typename Traits::span_traits::value_type;
1143        using size_type = typename Traits::span_traits::size_type;
1144    };
1145
1146    template <typename T, std::ptrdiff_t... Ranks>
1147    struct SpanArrayTraits
1148    {
1149        using type = multi_span<T, Ranks...>;
1150        using value_type = T;
1151        using bounds_type = static_bounds<Ranks...>;
1152        using pointer = T*;
1153        using reference = T&;
1154    };
1155    template <typename T, std::ptrdiff_t N, std::ptrdiff_t... Ranks>
1156    struct SpanArrayTraits<T[N], Ranks...> : SpanArrayTraits<T, Ranks..., N>
1157    {
1158    };
1159
1160    template <typename BoundsType>
1161    BoundsType newBoundsHelperImpl(std::ptrdiff_t totalSize, std::true_type) // dynamic size
1162    {
1163        Expects(totalSize >= 0 && totalSize <= PTRDIFF_MAX);
1164        return BoundsType{totalSize};
1165    }
1166    template <typename BoundsType>
1167    BoundsType newBoundsHelperImpl(std::ptrdiff_t totalSize, std::false_type) // static size
1168    {
1169        Expects(BoundsType::static_size <= totalSize);
1170        return {};
1171    }
1172    template <typename BoundsType>
1173    BoundsType newBoundsHelper(std::ptrdiff_t totalSize)
1174    {
1175        static_assert(BoundsType::dynamic_rank <= 1, "dynamic rank must less or equal to 1");
1176        return newBoundsHelperImpl<BoundsType>(
1177            totalSize, std::integral_constant<bool, BoundsType::dynamic_rank == 1>());
1178    }
1179
1180    struct Sep
1181    {
1182    };
1183
1184    template <typename T, typename... Args>
1185    T static_as_multi_span_helper(Sep, Args... args)
1186    {
1187        return T{narrow_cast<typename T::size_type>(args)...};
1188    }
1189    template <typename T, typename Arg, typename... Args>
1190    std::enable_if_t<
1191        !std::is_same<Arg, dim_t<dynamic_range>>::value && !std::is_same<Arg, Sep>::value, T>
1192    static_as_multi_span_helper(Arg, Args... args)
1193    {
1194        return static_as_multi_span_helper<T>(args...);
1195    }
1196    template <typename T, typename... Args>
1197    T static_as_multi_span_helper(dim_t<dynamic_range> val, Args... args)
1198    {
1199        return static_as_multi_span_helper<T>(args..., val.dvalue);
1200    }
1201
1202    template <typename... Dimensions>
1203    struct static_as_multi_span_static_bounds_helper
1204    {
1205        using type = static_bounds<(Dimensions::value)...>;
1206    };
1207
1208    template <typename T>
1209    struct is_multi_span_oracle : std::false_type
1210    {
1211    };
1212
1213    template <typename ValueType, std::ptrdiff_t FirstDimension, std::ptrdiff_t... RestDimensions>
1214    struct is_multi_span_oracle<multi_span<ValueType, FirstDimension, RestDimensions...>>
1215        : std::true_type
1216    {
1217    };
1218
1219    template <typename ValueType, std::ptrdiff_t Rank>
1220    struct is_multi_span_oracle<strided_span<ValueType, Rank>> : std::true_type
1221    {
1222    };
1223
1224    template <typename T>
1225    struct is_multi_span : is_multi_span_oracle<std::remove_cv_t<T>>
1226    {
1227    };
1228} // namespace details
1229
1230template <typename ValueType, std::ptrdiff_t FirstDimension, std::ptrdiff_t... RestDimensions>
1231class multi_span
1232{
1233    // TODO do we still need this?
1234    template <typename ValueType2, std::ptrdiff_t FirstDimension2,
1235              std::ptrdiff_t... RestDimensions2>
1236    friend class multi_span;
1237
1238public:
1239    using bounds_type = static_bounds<FirstDimension, RestDimensions...>;
1240    static const std::size_t Rank = bounds_type::rank;
1241    using size_type = typename bounds_type::size_type;
1242    using index_type = typename bounds_type::index_type;
1243    using value_type = ValueType;
1244    using const_value_type = std::add_const_t<value_type>;
1245    using pointer = std::add_pointer_t<value_type>;
1246    using reference = std::add_lvalue_reference_t<value_type>;
1247    using iterator = contiguous_span_iterator<multi_span>;
1248    using const_span = multi_span<const_value_type, FirstDimension, RestDimensions...>;
1249    using const_iterator = contiguous_span_iterator<const_span>;
1250    using reverse_iterator = std::reverse_iterator<iterator>;
1251    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
1252    using sliced_type =
1253        std::conditional_t<Rank == 1, value_type, multi_span<value_type, RestDimensions...>>;
1254
1255private:
1256    pointer data_;
1257    bounds_type bounds_;
1258
1259    friend iterator;
1260    friend const_iterator;
1261
1262public:
1263    // default constructor - same as constructing from nullptr_t
1264    GSL_SUPPRESS(type.6) // NO-FORMAT: attribute // TODO: false positive
1265    constexpr multi_span() noexcept
1266        : multi_span(nullptr, bounds_type{})
1267    {
1268        static_assert(bounds_type::dynamic_rank != 0 ||
1269                          (bounds_type::dynamic_rank == 0 && bounds_type::static_size == 0),
1270                      "Default construction of multi_span<T> only possible "
1271                      "for dynamic or fixed, zero-length spans.");
1272    }
1273
1274    // construct from nullptr - get an empty multi_span
1275    GSL_SUPPRESS(type.6) // NO-FORMAT: attribute // TODO: false positive
1276    constexpr multi_span(std::nullptr_t) noexcept
1277        : multi_span(nullptr, bounds_type{})
1278    {
1279        static_assert(bounds_type::dynamic_rank != 0 ||
1280                          (bounds_type::dynamic_rank == 0 && bounds_type::static_size == 0),
1281                      "nullptr_t construction of multi_span<T> only possible "
1282                      "for dynamic or fixed, zero-length spans.");
1283    }
1284
1285    // construct from nullptr with size of 0 (helps with template function calls)
1286    template <class IntType, typename = std::enable_if_t<std::is_integral<IntType>::value>>
1287
1288    // GSL_SUPPRESS(type.6) // NO-FORMAT: attribute // TODO: false positive // TODO: parser bug
1289    constexpr multi_span(std::nullptr_t, IntType size) : multi_span(nullptr, bounds_type{})
1290    {
1291        static_assert(bounds_type::dynamic_rank != 0 ||
1292                          (bounds_type::dynamic_rank == 0 && bounds_type::static_size == 0),
1293                      "nullptr_t construction of multi_span<T> only possible "
1294                      "for dynamic or fixed, zero-length spans.");
1295        Expects(size == 0);
1296    }
1297
1298    // construct from a single element
1299
1300    GSL_SUPPRESS(type.6) // NO-FORMAT: attribute // TODO: false positive
1301    constexpr multi_span(reference data) noexcept
1302        : multi_span(&data, bounds_type{1})
1303    {
1304        static_assert(bounds_type::dynamic_rank > 0 || bounds_type::static_size == 0 ||
1305                          bounds_type::static_size == 1,
1306                      "Construction from a single element only possible "
1307                      "for dynamic or fixed spans of length 0 or 1.");
1308    }
1309
1310    // prevent constructing from temporaries for single-elements
1311    constexpr multi_span(value_type&&) = delete;
1312
1313    // construct from pointer + length
1314    GSL_SUPPRESS(type.6) // NO-FORMAT: attribute // TODO: false positive
1315    constexpr multi_span(pointer ptr, size_type size)
1316        : multi_span(ptr, bounds_type{size})
1317    {}
1318
1319    // construct from pointer + length - multidimensional
1320    constexpr multi_span(pointer data, bounds_type bounds)
1321        : data_(data), bounds_(std::move(bounds))
1322    {
1323        Expects((bounds_.size() > 0 && data != nullptr) || bounds_.size() == 0);
1324    }
1325
1326    // construct from begin,end pointer pair
1327    template <typename Ptr,
1328              typename = std::enable_if_t<std::is_convertible<Ptr, pointer>::value &&
1329                                          details::LessThan<bounds_type::dynamic_rank, 2>::value>>
1330    constexpr multi_span(pointer begin, Ptr end)
1331        : multi_span(begin,
1332                     details::newBoundsHelper<bounds_type>(static_cast<pointer>(end) - begin))
1333    {
1334        Expects(begin != nullptr && end != nullptr && begin <= static_cast<pointer>(end));
1335    }
1336
1337    // construct from n-dimensions static array
1338    template <typename T, std::size_t N, typename Helper = details::SpanArrayTraits<T, N>>
1339    constexpr multi_span(T (&arr)[N])
1340        : multi_span(reinterpret_cast<pointer>(arr), bounds_type{typename Helper::bounds_type{}})
1341    {
1342        static_assert(std::is_convertible<typename Helper::value_type(*)[], value_type(*)[]>::value,
1343                      "Cannot convert from source type to target multi_span type.");
1344        static_assert(std::is_convertible<typename Helper::bounds_type, bounds_type>::value,
1345                      "Cannot construct a multi_span from an array with fewer elements.");
1346    }
1347
1348    // construct from n-dimensions dynamic array (e.g. new int[m][4])
1349    // (precedence will be lower than the 1-dimension pointer)
1350    template <typename T, typename Helper = details::SpanArrayTraits<T, dynamic_range>>
1351    constexpr multi_span(T* const& data, size_type size)
1352        : multi_span(reinterpret_cast<pointer>(data), typename Helper::bounds_type{size})
1353    {
1354        static_assert(std::is_convertible<typename Helper::value_type(*)[], value_type(*)[]>::value,
1355                      "Cannot convert from source type to target multi_span type.");
1356    }
1357
1358    // construct from std::array
1359    template <typename T, std::size_t N>
1360    constexpr multi_span(std::array<T, N>& arr)
1361        : multi_span(arr.data(), bounds_type{static_bounds<N>{}})
1362    {
1363        static_assert(
1364            std::is_convertible<T(*)[], typename std::remove_const_t<value_type>(*)[]>::value,
1365            "Cannot convert from source type to target multi_span type.");
1366        static_assert(std::is_convertible<static_bounds<N>, bounds_type>::value,
1367                      "You cannot construct a multi_span from a std::array of smaller size.");
1368    }
1369
1370    // construct from const std::array
1371    template <typename T, std::size_t N>
1372    constexpr multi_span(const std::array<T, N>& arr)
1373        : multi_span(arr.data(), bounds_type{static_bounds<N>{}})
1374    {
1375        static_assert(
1376            std::is_convertible<T(*)[], typename std::remove_const_t<value_type>(*)[]>::value,
1377            "Cannot convert from source type to target multi_span type.");
1378        static_assert(std::is_convertible<static_bounds<N>, bounds_type>::value,
1379                      "You cannot construct a multi_span from a std::array of smaller size.");
1380    }
1381
1382    // prevent constructing from temporary std::array
1383    template <typename T, std::size_t N>
1384    constexpr multi_span(std::array<T, N>&& arr) = delete;
1385
1386    // construct from containers
1387    // future: could use contiguous_iterator_traits to identify only contiguous containers
1388    // type-requirements: container must have .size(), operator[] which are value_type compatible
1389    template <typename Cont, typename DataType = typename Cont::value_type,
1390              typename = std::enable_if_t<
1391                  !details::is_multi_span<Cont>::value &&
1392                  std::is_convertible<DataType (*)[], value_type (*)[]>::value &&
1393                  std::is_same<std::decay_t<decltype(std::declval<Cont>().size(),
1394                                                     *std::declval<Cont>().data())>,
1395                               DataType>::value>>
1396    constexpr multi_span(Cont& cont)
1397        : multi_span(static_cast<pointer>(cont.data()),
1398                     details::newBoundsHelper<bounds_type>(narrow_cast<size_type>(cont.size())))
1399    {}
1400
1401    // prevent constructing from temporary containers
1402    template <typename Cont, typename DataType = typename Cont::value_type,
1403              typename = std::enable_if_t<
1404                  !details::is_multi_span<Cont>::value &&
1405                  std::is_convertible<DataType (*)[], value_type (*)[]>::value &&
1406                  std::is_same<std::decay_t<decltype(std::declval<Cont>().size(),
1407                                                     *std::declval<Cont>().data())>,
1408                               DataType>::value>>
1409    explicit constexpr multi_span(Cont&& cont) = delete;
1410
1411    // construct from a convertible multi_span
1412    template <typename OtherValueType, std::ptrdiff_t... OtherDimensions,
1413              typename OtherBounds = static_bounds<OtherDimensions...>,
1414              typename = std::enable_if_t<std::is_convertible<OtherValueType, ValueType>::value &&
1415                                          std::is_convertible<OtherBounds, bounds_type>::value>>
1416    constexpr multi_span(multi_span<OtherValueType, OtherDimensions...> other)
1417        : data_(other.data_), bounds_(other.bounds_)
1418    {}
1419
1420    // trivial copy and move
1421    constexpr multi_span(const multi_span&) = default;
1422    constexpr multi_span(multi_span&&) = default;
1423
1424    // trivial assignment
1425    constexpr multi_span& operator=(const multi_span&) = default;
1426    constexpr multi_span& operator=(multi_span&&) = default;
1427
1428    // first() - extract the first Count elements into a new multi_span
1429    template <std::ptrdiff_t Count>
1430
1431    constexpr multi_span<ValueType, Count> first() const
1432    {
1433        static_assert(Count >= 0, "Count must be >= 0.");
1434        static_assert(bounds_type::static_size == dynamic_range ||
1435                          Count <= bounds_type::static_size,
1436                      "Count is out of bounds.");
1437
1438        Expects(bounds_type::static_size != dynamic_range || Count <= this->size());
1439        return {this->data(), Count};
1440    }
1441
1442    // first() - extract the first count elements into a new multi_span
1443    constexpr multi_span<ValueType, dynamic_range> first(size_type count) const
1444    {
1445        Expects(count >= 0 && count <= this->size());
1446        return {this->data(), count};
1447    }
1448
1449    // last() - extract the last Count elements into a new multi_span
1450    template <std::ptrdiff_t Count>
1451    constexpr multi_span<ValueType, Count> last() const
1452    {
1453        static_assert(Count >= 0, "Count must be >= 0.");
1454        static_assert(bounds_type::static_size == dynamic_range ||
1455                          Count <= bounds_type::static_size,
1456                      "Count is out of bounds.");
1457
1458        Expects(bounds_type::static_size != dynamic_range || Count <= this->size());
1459        return {this->data() + this->size() - Count, Count};
1460    }
1461
1462    // last() - extract the last count elements into a new multi_span
1463    constexpr multi_span<ValueType, dynamic_range> last(size_type count) const
1464    {
1465        Expects(count >= 0 && count <= this->size());
1466        return {this->data() + this->size() - count, count};
1467    }
1468
1469    // subspan() - create a subview of Count elements starting at Offset
1470    template <std::ptrdiff_t Offset, std::ptrdiff_t Count>
1471    constexpr multi_span<ValueType, Count> subspan() const
1472    {
1473        static_assert(Count >= 0, "Count must be >= 0.");
1474        static_assert(Offset >= 0, "Offset must be >= 0.");
1475        static_assert(bounds_type::static_size == dynamic_range ||
1476                          ((Offset <= bounds_type::static_size) &&
1477                           Count <= bounds_type::static_size - Offset),
1478                      "You must describe a sub-range within bounds of the multi_span.");
1479
1480        Expects(bounds_type::static_size != dynamic_range ||
1481                (Offset <= this->size() && Count <= this->size() - Offset));
1482        return {this->data() + Offset, Count};
1483    }
1484
1485    // subspan() - create a subview of count elements starting at offset
1486    // supplying dynamic_range for count will consume all available elements from offset
1487    constexpr multi_span<ValueType, dynamic_range> subspan(size_type offset,
1488                                                           size_type count = dynamic_range) const
1489    {
1490        Expects((offset >= 0 && offset <= this->size()) &&
1491                (count == dynamic_range || (count <= this->size() - offset)));
1492        return {this->data() + offset, count == dynamic_range ? this->length() - offset : count};
1493    }
1494
1495    // section - creates a non-contiguous, strided multi_span from a contiguous one
1496    constexpr strided_span<ValueType, Rank> section(index_type origin,
1497                                                    index_type extents) const
1498    {
1499        const size_type size = this->bounds().total_size() - this->bounds().linearize(origin);
1500        return {&this->operator[](origin), size,
1501                strided_bounds<Rank>{extents, details::make_stride(bounds())}};
1502    }
1503
1504    // length of the multi_span in elements
1505    constexpr size_type size() const noexcept { return bounds_.size(); }
1506
1507    // length of the multi_span in elements
1508    constexpr size_type length() const noexcept { return this->size(); }
1509
1510    // length of the multi_span in bytes
1511    constexpr size_type size_bytes() const noexcept
1512    {
1513        return narrow_cast<size_type>(sizeof(value_type)) * this->size();
1514    }
1515
1516    // length of the multi_span in bytes
1517    constexpr size_type length_bytes() const noexcept { return this->size_bytes(); }
1518
1519    constexpr bool empty() const noexcept { return this->size() == 0; }
1520
1521    static constexpr std::size_t rank() { return Rank; }
1522
1523    template <std::size_t Dim = 0>
1524    constexpr size_type extent() const noexcept
1525    {
1526        static_assert(Dim < Rank,
1527                      "Dimension should be less than rank (dimension count starts from 0).");
1528        return bounds_.template extent<Dim>();
1529    }
1530
1531    template <typename IntType>
1532    constexpr size_type extent(IntType dim) const
1533    {
1534        return bounds_.extent(dim);
1535    }
1536
1537    constexpr bounds_type bounds() const noexcept { return bounds_; }
1538
1539    constexpr pointer data() const noexcept { return data_; }
1540
1541    template <typename FirstIndex>
1542    constexpr reference operator()(FirstIndex idx)
1543    {
1544        return this->operator[](narrow_cast<std::ptrdiff_t>(idx));
1545    }
1546
1547    template <typename FirstIndex, typename... OtherIndices>
1548    constexpr reference operator()(FirstIndex firstIndex, OtherIndices... indices)
1549    {
1550        const index_type idx = {narrow_cast<std::ptrdiff_t>(firstIndex),
1551                                narrow_cast<std::ptrdiff_t>(indices)...};
1552        return this->operator[](idx);
1553    }
1554
1555    GSL_SUPPRESS(bounds.1) // NO-FORMAT: attribute
1556    constexpr reference operator[](const index_type& idx) const
1557    {
1558        return data_[bounds_.linearize(idx)];
1559    }
1560
1561    template <bool Enabled = (Rank > 1), typename Ret = std::enable_if_t<Enabled, sliced_type>>
1562
1563    GSL_SUPPRESS(bounds.1) // NO-FORMAT: attribute
1564    constexpr Ret operator[](size_type idx) const
1565    {
1566        Expects(idx >= 0 && idx < bounds_.size()); // index is out of bounds of the array
1567        const size_type ridx = idx * bounds_.stride();
1568
1569        // index is out of bounds of the underlying data
1570        Expects(ridx < bounds_.total_size());
1571        return Ret{data_ + ridx, bounds_.slice()};
1572    }
1573
1574    constexpr iterator begin() const noexcept { return iterator{this, true}; }
1575
1576    constexpr iterator end() const noexcept { return iterator{this, false}; }
1577
1578    GSL_SUPPRESS(type.1) // NO-FORMAT: attribute
1579    constexpr const_iterator cbegin() const noexcept
1580    {
1581        return const_iterator{reinterpret_cast<const const_span*>(this), true};
1582    }
1583
1584    constexpr const_iterator cend() const noexcept
1585    {
1586        return const_iterator{reinterpret_cast<const const_span*>(this), false};
1587    }
1588
1589    constexpr reverse_iterator rbegin() const noexcept { return reverse_iterator{end()}; }
1590
1591    constexpr reverse_iterator rend() const noexcept { return reverse_iterator{begin()}; }
1592
1593    constexpr const_reverse_iterator crbegin() const noexcept
1594    {
1595        return const_reverse_iterator{cend()};
1596    }
1597
1598    constexpr const_reverse_iterator crend() const noexcept
1599    {
1600        return const_reverse_iterator{cbegin()};
1601    }
1602
1603    template <typename OtherValueType, std::ptrdiff_t... OtherDimensions,
1604              typename = std::enable_if_t<std::is_same<std::remove_cv_t<value_type>,
1605                                                       std::remove_cv_t<OtherValueType>>::value>>
1606    constexpr bool operator==(const multi_span<OtherValueType, OtherDimensions...>& other) const
1607    {
1608        return bounds_.size() == other.bounds_.size() &&
1609               (data_ == other.data_ || std::equal(this->begin(), this->end(), other.begin()));
1610    }
1611
1612    template <typename OtherValueType, std::ptrdiff_t... OtherDimensions,
1613              typename = std::enable_if_t<std::is_same<std::remove_cv_t<value_type>,
1614                                                       std::remove_cv_t<OtherValueType>>::value>>
1615    constexpr bool operator!=(const multi_span<OtherValueType, OtherDimensions...>& other) const
1616    {
1617        return !(*this == other);
1618    }
1619
1620    template <typename OtherValueType, std::ptrdiff_t... OtherDimensions,
1621              typename = std::enable_if_t<std::is_same<std::remove_cv_t<value_type>,
1622                                                       std::remove_cv_t<OtherValueType>>::value>>
1623    constexpr bool operator<(const multi_span<OtherValueType, OtherDimensions...>& other) const
1624    {
1625        return std::lexicographical_compare(this->begin(), this->end(), other.begin(), other.end());
1626    }
1627
1628    template <typename OtherValueType, std::ptrdiff_t... OtherDimensions,
1629              typename = std::enable_if_t<std::is_same<std::remove_cv_t<value_type>,
1630                                                       std::remove_cv_t<OtherValueType>>::value>>
1631    constexpr bool operator<=(const multi_span<OtherValueType, OtherDimensions...>& other) const
1632    {
1633        return !(other < *this);
1634    }
1635
1636    template <typename OtherValueType, std::ptrdiff_t... OtherDimensions,
1637              typename = std::enable_if_t<std::is_same<std::remove_cv_t<value_type>,
1638                                                       std::remove_cv_t<OtherValueType>>::value>>
1639    constexpr bool operator>(const multi_span<OtherValueType, OtherDimensions...>& other) const
1640        noexcept
1641    {
1642        return (other < *this);
1643    }
1644
1645    template <typename OtherValueType, std::ptrdiff_t... OtherDimensions,
1646              typename = std::enable_if_t<std::is_same<std::remove_cv_t<value_type>,
1647                                                       std::remove_cv_t<OtherValueType>>::value>>
1648    constexpr bool operator>=(const multi_span<OtherValueType, OtherDimensions...>& other) const
1649    {
1650        return !(*this < other);
1651    }
1652};
1653
1654//
1655// Free functions for manipulating spans
1656//
1657
1658// reshape a multi_span into a different dimensionality
1659// DimCount and Enabled here are workarounds for a bug in MSVC 2015
1660template <typename SpanType, typename... Dimensions2, std::size_t DimCount = sizeof...(Dimensions2),
1661          bool Enabled = (DimCount > 0), typename = std::enable_if_t<Enabled>>
1662constexpr auto as_multi_span(SpanType s, Dimensions2... dims)
1663    -> multi_span<typename SpanType::value_type, Dimensions2::value...>
1664{
1665    static_assert(details::is_multi_span<SpanType>::value,
1666                  "Variadic as_multi_span() is for reshaping existing spans.");
1667    using BoundsType =
1668        typename multi_span<typename SpanType::value_type, (Dimensions2::value)...>::bounds_type;
1669    const auto tobounds = details::static_as_multi_span_helper<BoundsType>(dims..., details::Sep{});
1670    details::verifyBoundsReshape(s.bounds(), tobounds);
1671    return {s.data(), tobounds};
1672}
1673
1674// convert a multi_span<T> to a multi_span<const byte>
1675template <typename U, std::ptrdiff_t... Dimensions>
1676multi_span<const byte, dynamic_range> as_bytes(multi_span<U, Dimensions...> s) noexcept
1677{
1678    static_assert(std::is_trivial<std::decay_t<U>>::value,
1679                  "The value_type of multi_span must be a trivial type.");
1680    return {reinterpret_cast<const byte*>(s.data()), s.size_bytes()};
1681}
1682
1683// convert a multi_span<T> to a multi_span<byte> (a writeable byte multi_span)
1684// this is not currently a portable function that can be relied upon to work
1685// on all implementations. It should be considered an experimental extension
1686// to the standard GSL interface.
1687template <typename U, std::ptrdiff_t... Dimensions>
1688multi_span<byte> as_writeable_bytes(multi_span<U, Dimensions...> s) noexcept
1689{
1690    static_assert(std::is_trivial<std::decay_t<U>>::value,
1691                  "The value_type of multi_span must be a trivial type.");
1692    return {reinterpret_cast<byte*>(s.data()), s.size_bytes()};
1693}
1694
1695// convert a multi_span<const byte> to a multi_span<const T>
1696// this is not currently a portable function that can be relied upon to work
1697// on all implementations. It should be considered an experimental extension
1698// to the standard GSL interface.
1699template <typename U, std::ptrdiff_t... Dimensions>
1700constexpr auto as_multi_span(multi_span<const byte, Dimensions...> s) -> multi_span<
1701    const U, static_cast<std::ptrdiff_t>(
1702                 multi_span<const byte, Dimensions...>::bounds_type::static_size != dynamic_range
1703                     ? (static_cast<std::size_t>(
1704                            multi_span<const byte, Dimensions...>::bounds_type::static_size) /
1705                        sizeof(U))
1706                     : dynamic_range)>
1707{
1708    using ConstByteSpan = multi_span<const byte, Dimensions...>;
1709    static_assert(
1710        std::is_trivial<std::decay_t<U>>::value &&
1711            (ConstByteSpan::bounds_type::static_size == dynamic_range ||
1712             ConstByteSpan::bounds_type::static_size % narrow_cast<std::ptrdiff_t>(sizeof(U)) == 0),
1713        "Target type must be a trivial type and its size must match the byte array size");
1714
1715    Expects((s.size_bytes() % narrow_cast<std::ptrdiff_t>(sizeof(U))) == 0 &&
1716            (s.size_bytes() / narrow_cast<std::ptrdiff_t>(sizeof(U))) < PTRDIFF_MAX);
1717    return {reinterpret_cast<const U*>(s.data()),
1718            s.size_bytes() / narrow_cast<std::ptrdiff_t>(sizeof(U))};
1719}
1720
1721// convert a multi_span<byte> to a multi_span<T>
1722// this is not currently a portable function that can be relied upon to work
1723// on all implementations. It should be considered an experimental extension
1724// to the standard GSL interface.
1725template <typename U, std::ptrdiff_t... Dimensions>
1726constexpr auto as_multi_span(multi_span<byte, Dimensions...> s)
1727    -> multi_span<U, narrow_cast<std::ptrdiff_t>(
1728                         multi_span<byte, Dimensions...>::bounds_type::static_size != dynamic_range
1729                             ? static_cast<std::size_t>(
1730                                   multi_span<byte, Dimensions...>::bounds_type::static_size) /
1731                                   sizeof(U)
1732                             : dynamic_range)>
1733{
1734    using ByteSpan = multi_span<byte, Dimensions...>;
1735    static_assert(std::is_trivial<std::decay_t<U>>::value &&
1736                      (ByteSpan::bounds_type::static_size == dynamic_range ||
1737                       ByteSpan::bounds_type::static_size % sizeof(U) == 0),
1738                  "Target type must be a trivial type and its size must match the byte array size");
1739
1740    Expects((s.size_bytes() % sizeof(U)) == 0);
1741    return {reinterpret_cast<U*>(s.data()),
1742            s.size_bytes() / narrow_cast<std::ptrdiff_t>(sizeof(U))};
1743}
1744
1745template <typename T, std::ptrdiff_t... Dimensions>
1746constexpr auto as_multi_span(T* const& ptr, dim_t<Dimensions>... args)
1747    -> multi_span<std::remove_all_extents_t<T>, Dimensions...>
1748{
1749    return {reinterpret_cast<std::remove_all_extents_t<T>*>(ptr),
1750            details::static_as_multi_span_helper<static_bounds<Dimensions...>>(args...,
1751                                                                               details::Sep{})};
1752}
1753
1754template <typename T>
1755constexpr auto as_multi_span(T* arr, std::ptrdiff_t len) ->
1756    typename details::SpanArrayTraits<T, dynamic_range>::type
1757{
1758    return {reinterpret_cast<std::remove_all_extents_t<T>*>(arr), len};
1759}
1760
1761template <typename T, std::size_t N>
1762constexpr auto as_multi_span(T (&arr)[N]) -> typename details::SpanArrayTraits<T, N>::type
1763{
1764    return {arr};
1765}
1766
1767template <typename T, std::size_t N>
1768constexpr multi_span<const T, N> as_multi_span(const std::array<T, N>& arr)
1769{
1770    return {arr};
1771}
1772
1773template <typename T, std::size_t N>
1774constexpr multi_span<const T, N> as_multi_span(const std::array<T, N>&&) = delete;
1775
1776template <typename T, std::size_t N>
1777constexpr multi_span<T, N> as_multi_span(std::array<T, N>& arr)
1778{
1779    return {arr};
1780}
1781
1782template <typename T>
1783constexpr multi_span<T, dynamic_range> as_multi_span(T* begin, T* end)
1784{
1785    return {begin, end};
1786}
1787
1788template <typename Cont>
1789constexpr auto as_multi_span(Cont& arr) -> std::enable_if_t<
1790    !details::is_multi_span<std::decay_t<Cont>>::value,
1791    multi_span<std::remove_reference_t<decltype(arr.size(), *arr.data())>, dynamic_range>>
1792{
1793    Expects(arr.size() < PTRDIFF_MAX);
1794    return {arr.data(), narrow_cast<std::ptrdiff_t>(arr.size())};
1795}
1796
1797template <typename Cont>
1798constexpr auto as_multi_span(Cont&& arr) -> std::enable_if_t<
1799    !details::is_multi_span<std::decay_t<Cont>>::value,
1800    multi_span<std::remove_reference_t<decltype(arr.size(), *arr.data())>, dynamic_range>> = delete;
1801
1802// from basic_string which doesn't have nonconst .data() member like other contiguous containers
1803template <typename CharT, typename Traits, typename Allocator>
1804GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
1805constexpr auto as_multi_span(std::basic_string<CharT, Traits, Allocator>& str)
1806    -> multi_span<CharT, dynamic_range>
1807{
1808    Expects(str.size() < PTRDIFF_MAX);
1809    return {&str[0], narrow_cast<std::ptrdiff_t>(str.size())};
1810}
1811
1812// strided_span is an extension that is not strictly part of the GSL at this time.
1813// It is kept here while the multidimensional interface is still being defined.
1814template <typename ValueType, std::size_t Rank>
1815class strided_span
1816{
1817public:
1818    using bounds_type = strided_bounds<Rank>;
1819    using size_type = typename bounds_type::size_type;
1820    using index_type = typename bounds_type::index_type;
1821    using value_type = ValueType;
1822    using const_value_type = std::add_const_t<value_type>;
1823    using pointer = std::add_pointer_t<value_type>;
1824    using reference = std::add_lvalue_reference_t<value_type>;
1825    using iterator = general_span_iterator<strided_span>;
1826    using const_strided_span = strided_span<const_value_type, Rank>;
1827    using const_iterator = general_span_iterator<const_strided_span>;
1828    using reverse_iterator = std::reverse_iterator<iterator>;
1829    using const_reverse_iterator = std::reverse_iterator<const_iterator>;
1830    using sliced_type =
1831        std::conditional_t<Rank == 1, value_type, strided_span<value_type, Rank - 1>>;
1832
1833private:
1834    pointer data_;
1835    bounds_type bounds_;
1836
1837    friend iterator;
1838    friend const_iterator;
1839    template <typename OtherValueType, std::size_t OtherRank>
1840    friend class strided_span;
1841
1842public:
1843    // from raw data
1844    constexpr strided_span(pointer ptr, size_type size, bounds_type bounds)
1845        : data_(ptr), bounds_(std::move(bounds))
1846    {
1847        Expects((bounds_.size() > 0 && ptr != nullptr) || bounds_.size() == 0);
1848        // Bounds cross data boundaries
1849        Expects(this->bounds().total_size() <= size);
1850        GSL_SUPPRESS(type.4) // NO-FORMAT: attribute // TODO: false positive
1851        (void) size;
1852    }
1853
1854    // from static array of size N
1855    template <size_type N>
1856    constexpr strided_span(value_type (&values)[N], bounds_type bounds)
1857        : strided_span(values, N, std::move(bounds))
1858    {}
1859
1860    // from array view
1861    template <typename OtherValueType, std::ptrdiff_t... Dimensions,
1862              bool Enabled1 = (sizeof...(Dimensions) == Rank),
1863              bool Enabled2 = std::is_convertible<OtherValueType*, ValueType*>::value,
1864              typename = std::enable_if_t<Enabled1 && Enabled2>>
1865    constexpr strided_span(multi_span<OtherValueType, Dimensions...> av, bounds_type bounds)
1866        : strided_span(av.data(), av.bounds().total_size(), std::move(bounds))
1867    {}
1868
1869    // convertible
1870    template <typename OtherValueType, typename = std::enable_if_t<std::is_convertible<
1871                                           OtherValueType (*)[], value_type (*)[]>::value>>
1872    constexpr strided_span(const strided_span<OtherValueType, Rank>& other)
1873        : data_(other.data_), bounds_(other.bounds_)
1874    {}
1875
1876    // convert from bytes
1877    template <typename OtherValueType>
1878    constexpr strided_span<
1879        typename std::enable_if<std::is_same<value_type, const byte>::value, OtherValueType>::type,
1880        Rank>
1881    as_strided_span() const
1882    {
1883        static_assert((sizeof(OtherValueType) >= sizeof(value_type)) &&
1884                          (sizeof(OtherValueType) % sizeof(value_type) == 0),
1885                      "OtherValueType should have a size to contain a multiple of ValueTypes");
1886        auto d = narrow_cast<size_type>(sizeof(OtherValueType) / sizeof(value_type));
1887
1888        const size_type size = this->bounds().total_size() / d;
1889
1890        GSL_SUPPRESS(type.3) // NO-FORMAT: attribute
1891        return {const_cast<OtherValueType*>(reinterpret_cast<const OtherValueType*>(this->data())),
1892                size,
1893                bounds_type{resize_extent(this->bounds().index_bounds(), d),
1894                            resize_stride(this->bounds().strides(), d)}};
1895    }
1896
1897    constexpr strided_span section(index_type origin, index_type extents) const
1898    {
1899        const size_type size = this->bounds().total_size() - this->bounds().linearize(origin);
1900        return {&this->operator[](origin), size,
1901                bounds_type{extents, details::make_stride(bounds())}};
1902    }
1903
1904    GSL_SUPPRESS(bounds.1) // NO-FORMAT: attribute
1905    constexpr reference operator[](const index_type& idx) const
1906    {
1907        return data_[bounds_.linearize(idx)];
1908    }
1909
1910    template <bool Enabled = (Rank > 1), typename Ret = std::enable_if_t<Enabled, sliced_type>>
1911    GSL_SUPPRESS(bounds.1) // NO-FORMAT: attribute
1912    constexpr Ret operator[](size_type idx) const
1913    {
1914        Expects(idx < bounds_.size()); // index is out of bounds of the array
1915        const size_type ridx = idx * bounds_.stride();
1916
1917        // index is out of bounds of the underlying data
1918        Expects(ridx < bounds_.total_size());
1919        return {data_ + ridx, bounds_.slice().total_size(), bounds_.slice()};
1920    }
1921
1922    constexpr bounds_type bounds() const noexcept { return bounds_; }
1923
1924    template <std::size_t Dim = 0>
1925    constexpr size_type extent() const noexcept
1926    {
1927        static_assert(Dim < Rank,
1928                      "dimension should be less than Rank (dimension count starts from 0)");
1929        return bounds_.template extent<Dim>();
1930    }
1931
1932    constexpr size_type size() const noexcept { return bounds_.size(); }
1933
1934    constexpr pointer data() const noexcept { return data_; }
1935
1936    constexpr bool empty() const noexcept { return this->size() == 0; }
1937
1938    constexpr explicit operator bool() const noexcept { return data_ != nullptr; }
1939
1940    constexpr iterator begin() const { return iterator{this, true}; }
1941
1942    constexpr iterator end() const { return iterator{this, false}; }
1943
1944    constexpr const_iterator cbegin() const
1945    {
1946        return const_iterator{reinterpret_cast<const const_strided_span*>(this), true};
1947    }
1948
1949    constexpr const_iterator cend() const
1950    {
1951        return const_iterator{reinterpret_cast<const const_strided_span*>(this), false};
1952    }
1953
1954    constexpr reverse_iterator rbegin() const { return reverse_iterator{end()}; }
1955
1956    constexpr reverse_iterator rend() const { return reverse_iterator{begin()}; }
1957
1958    constexpr const_reverse_iterator crbegin() const { return const_reverse_iterator{cend()}; }
1959
1960    constexpr const_reverse_iterator crend() const { return const_reverse_iterator{cbegin()}; }
1961
1962    template <typename OtherValueType, std::ptrdiff_t OtherRank,
1963              typename = std::enable_if_t<std::is_same<std::remove_cv_t<value_type>,
1964                                                       std::remove_cv_t<OtherValueType>>::value>>
1965    constexpr bool operator==(const strided_span<OtherValueType, OtherRank>& other) const
1966    {
1967        return bounds_.size() == other.bounds_.size() &&
1968               (data_ == other.data_ || std::equal(this->begin(), this->end(), other.begin()));
1969    }
1970
1971    template <typename OtherValueType, std::ptrdiff_t OtherRank,
1972              typename = std::enable_if_t<std::is_same<std::remove_cv_t<value_type>,
1973                                                       std::remove_cv_t<OtherValueType>>::value>>
1974    constexpr bool operator!=(const strided_span<OtherValueType, OtherRank>& other) const
1975    {
1976        return !(*this == other);
1977    }
1978
1979    template <typename OtherValueType, std::ptrdiff_t OtherRank,
1980              typename = std::enable_if_t<std::is_same<std::remove_cv_t<value_type>,
1981                                                       std::remove_cv_t<OtherValueType>>::value>>
1982    constexpr bool operator<(const strided_span<OtherValueType, OtherRank>& other) const
1983    {
1984        return std::lexicographical_compare(this->begin(), this->end(), other.begin(), other.end());
1985    }
1986
1987    template <typename OtherValueType, std::ptrdiff_t OtherRank,
1988              typename = std::enable_if_t<std::is_same<std::remove_cv_t<value_type>,
1989                                                       std::remove_cv_t<OtherValueType>>::value>>
1990    constexpr bool operator<=(const strided_span<OtherValueType, OtherRank>& other) const
1991    {
1992        return !(other < *this);
1993    }
1994
1995    template <typename OtherValueType, std::ptrdiff_t OtherRank,
1996              typename = std::enable_if_t<std::is_same<std::remove_cv_t<value_type>,
1997                                                       std::remove_cv_t<OtherValueType>>::value>>
1998    constexpr bool operator>(const strided_span<OtherValueType, OtherRank>& other) const
1999    {
2000        return (other < *this);
2001    }
2002
2003    template <typename OtherValueType, std::ptrdiff_t OtherRank,
2004              typename = std::enable_if_t<std::is_same<std::remove_cv_t<value_type>,
2005                                                       std::remove_cv_t<OtherValueType>>::value>>
2006    constexpr bool operator>=(const strided_span<OtherValueType, OtherRank>& other) const
2007    {
2008        return !(*this < other);
2009    }
2010
2011private:
2012    static index_type resize_extent(const index_type& extent, std::ptrdiff_t d)
2013    {
2014        // The last dimension of the array needs to contain a multiple of new type elements
2015        GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
2016        Expects(extent[Rank - 1] >= d && (extent[Rank - 1] % d == 0));
2017
2018        index_type ret = extent;
2019        ret[Rank - 1] /= d;
2020
2021        return ret;
2022    }
2023
2024    template <bool Enabled = (Rank == 1), typename = std::enable_if_t<Enabled>>
2025    static index_type resize_stride(const index_type& strides, std::ptrdiff_t, void* = nullptr)
2026    {
2027        // Only strided arrays with regular strides can be resized
2028        GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
2029        Expects(strides[Rank - 1] == 1);
2030
2031        return strides;
2032    }
2033
2034    template <bool Enabled = (Rank > 1), typename = std::enable_if_t<Enabled>>
2035    GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
2036    static index_type resize_stride(const index_type& strides, std::ptrdiff_t d)
2037    {
2038        // Only strided arrays with regular strides can be resized
2039        Expects(strides[Rank - 1] == 1);
2040        // The strides must have contiguous chunks of
2041        // memory that can contain a multiple of new type elements
2042        Expects(strides[Rank - 2] >= d && (strides[Rank - 2] % d == 0));
2043
2044        for (std::size_t i = Rank - 1; i > 0; --i)
2045        {
2046            // Only strided arrays with regular strides can be resized
2047            Expects((strides[i - 1] >= strides[i]) && (strides[i - 1] % strides[i] == 0));
2048        }
2049
2050        index_type ret = strides / d;
2051        ret[Rank - 1] = 1;
2052
2053        return ret;
2054    }
2055};
2056
2057template <class Span>
2058class contiguous_span_iterator
2059{
2060public:
2061    using iterator_category = std::random_access_iterator_tag;
2062    using value_type = typename Span::value_type;
2063    using difference_type = std::ptrdiff_t;
2064    using pointer = value_type*;
2065    using reference = value_type&;
2066
2067private:
2068    template <typename ValueType, std::ptrdiff_t FirstDimension, std::ptrdiff_t... RestDimensions>
2069    friend class multi_span;
2070
2071    pointer data_;
2072    const Span* m_validator;
2073
2074    GSL_SUPPRESS(bounds.1) // NO-FORMAT: attribute
2075    void validateThis() const {
2076        // iterator is out of range of the array
2077        Expects(data_ >= m_validator->data_ && data_ < m_validator->data_ + m_validator->size());
2078    }
2079
2080    GSL_SUPPRESS(bounds.1) // NO-FORMAT: attribute
2081    contiguous_span_iterator(const Span* container, bool isbegin)
2082        : data_(isbegin ? container->data_ : container->data_ + container->size())
2083        , m_validator(container)
2084    {}
2085
2086public:
2087    reference operator*() const
2088    {
2089        validateThis();
2090        return *data_;
2091    }
2092    pointer operator->() const
2093    {
2094        validateThis();
2095        return data_;
2096    }
2097
2098    GSL_SUPPRESS(bounds.1) // NO-FORMAT: attribute
2099    contiguous_span_iterator& operator++() noexcept
2100    {
2101        ++data_;
2102        return *this;
2103    }
2104    contiguous_span_iterator operator++(int) noexcept
2105    {
2106        auto ret = *this;
2107        ++(*this);
2108        return ret;
2109    }
2110
2111    GSL_SUPPRESS(bounds.1) // NO-FORMAT: attribute
2112    contiguous_span_iterator& operator--() noexcept
2113    {
2114        --data_;
2115        return *this;
2116    }
2117    contiguous_span_iterator operator--(int) noexcept
2118    {
2119        auto ret = *this;
2120        --(*this);
2121        return ret;
2122    }
2123    contiguous_span_iterator operator+(difference_type n) const noexcept
2124    {
2125        contiguous_span_iterator ret{*this};
2126        return ret += n;
2127    }
2128    contiguous_span_iterator& operator+=(difference_type n) noexcept
2129    {
2130        data_ += n;
2131        return *this;
2132    }
2133    contiguous_span_iterator operator-(difference_type n) const noexcept
2134    {
2135        contiguous_span_iterator ret{*this};
2136        return ret -= n;
2137    }
2138
2139    contiguous_span_iterator& operator-=(difference_type n) { return *this += -n; }
2140    difference_type operator-(const contiguous_span_iterator& rhs) const
2141    {
2142        Expects(m_validator == rhs.m_validator);
2143        return data_ - rhs.data_;
2144    }
2145    reference operator[](difference_type n) const { return *(*this + n); }
2146    bool operator==(const contiguous_span_iterator& rhs) const
2147    {
2148        Expects(m_validator == rhs.m_validator);
2149        return data_ == rhs.data_;
2150    }
2151
2152    bool operator!=(const contiguous_span_iterator& rhs) const { return !(*this == rhs); }
2153
2154    bool operator<(const contiguous_span_iterator& rhs) const
2155    {
2156        Expects(m_validator == rhs.m_validator);
2157        return data_ < rhs.data_;
2158    }
2159
2160    bool operator<=(const contiguous_span_iterator& rhs) const { return !(rhs < *this); }
2161    bool operator>(const contiguous_span_iterator& rhs) const { return rhs < *this; }
2162    bool operator>=(const contiguous_span_iterator& rhs) const { return !(rhs > *this); }
2163
2164    void swap(contiguous_span_iterator& rhs) noexcept
2165    {
2166        std::swap(data_, rhs.data_);
2167        std::swap(m_validator, rhs.m_validator);
2168    }
2169};
2170
2171template <typename Span>
2172contiguous_span_iterator<Span> operator+(typename contiguous_span_iterator<Span>::difference_type n,
2173                                         const contiguous_span_iterator<Span>& rhs) noexcept
2174{
2175    return rhs + n;
2176}
2177
2178template <typename Span>
2179class general_span_iterator {
2180public:
2181    using iterator_category = std::random_access_iterator_tag;
2182    using value_type = typename Span::value_type;
2183    using difference_type = std::ptrdiff_t;
2184    using pointer = value_type*;
2185    using reference = value_type&;
2186
2187private:
2188    template <typename ValueType, std::size_t Rank>
2189    friend class strided_span;
2190
2191    const Span* m_container;
2192    typename Span::bounds_type::iterator m_itr;
2193    general_span_iterator(const Span* container, bool isbegin)
2194        : m_container(container)
2195        , m_itr(isbegin ? m_container->bounds().begin() : m_container->bounds().end())
2196    {}
2197
2198public:
2199    reference operator*() noexcept { return (*m_container)[*m_itr]; }
2200    pointer operator->() noexcept { return &(*m_container)[*m_itr]; }
2201    general_span_iterator& operator++() noexcept
2202    {
2203        ++m_itr;
2204        return *this;
2205    }
2206    general_span_iterator operator++(int) noexcept
2207    {
2208        auto ret = *this;
2209        ++(*this);
2210        return ret;
2211    }
2212    general_span_iterator& operator--() noexcept
2213    {
2214        --m_itr;
2215        return *this;
2216    }
2217    general_span_iterator operator--(int) noexcept
2218    {
2219        auto ret = *this;
2220        --(*this);
2221        return ret;
2222    }
2223    general_span_iterator operator+(difference_type n) const noexcept
2224    {
2225        general_span_iterator ret{*this};
2226        return ret += n;
2227    }
2228    general_span_iterator& operator+=(difference_type n) noexcept
2229    {
2230        m_itr += n;
2231        return *this;
2232    }
2233    general_span_iterator operator-(difference_type n) const noexcept
2234    {
2235        general_span_iterator ret{*this};
2236        return ret -= n;
2237    }
2238    general_span_iterator& operator-=(difference_type n) noexcept { return *this += -n; }
2239    difference_type operator-(const general_span_iterator& rhs) const
2240    {
2241        Expects(m_container == rhs.m_container);
2242        return m_itr - rhs.m_itr;
2243    }
2244
2245    GSL_SUPPRESS(bounds.4) // NO-FORMAT: attribute
2246    value_type operator[](difference_type n) const { return (*m_container)[m_itr[n]]; }
2247
2248    bool operator==(const general_span_iterator& rhs) const
2249    {
2250        Expects(m_container == rhs.m_container);
2251        return m_itr == rhs.m_itr;
2252    }
2253    bool operator!=(const general_span_iterator& rhs) const { return !(*this == rhs); }
2254    bool operator<(const general_span_iterator& rhs) const
2255    {
2256        Expects(m_container == rhs.m_container);
2257        return m_itr < rhs.m_itr;
2258    }
2259    bool operator<=(const general_span_iterator& rhs) const { return !(rhs < *this); }
2260    bool operator>(const general_span_iterator& rhs) const { return rhs < *this; }
2261    bool operator>=(const general_span_iterator& rhs) const { return !(rhs > *this); }
2262    void swap(general_span_iterator& rhs) noexcept
2263    {
2264        std::swap(m_itr, rhs.m_itr);
2265        std::swap(m_container, rhs.m_container);
2266    }
2267};
2268
2269template <typename Span>
2270general_span_iterator<Span> operator+(typename general_span_iterator<Span>::difference_type n,
2271                                      const general_span_iterator<Span>& rhs) noexcept
2272{
2273    return rhs + n;
2274}
2275
2276} // namespace gsl
2277
2278#if defined(_MSC_VER) && !defined(__clang__)
2279#if _MSC_VER < 1910
2280
2281#undef constexpr
2282#pragma pop_macro("constexpr")
2283#endif // _MSC_VER < 1910
2284
2285#pragma warning(pop)
2286
2287#endif // _MSC_VER
2288
2289#if defined(__GNUC__) && __GNUC__ > 6
2290#pragma GCC diagnostic pop
2291#endif // __GNUC__ > 6
2292
2293#endif // GSL_MULTI_SPAN_H
2294