span

///////////////////////////////////////////////////////////////////////////////
//
// Copyright (c) 2015 Microsoft Corporation. All rights reserved.
//
// This code is licensed under the MIT License (MIT).
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.
//
///////////////////////////////////////////////////////////////////////////////

#pragma once

#ifndef GSL_SPAN_H
#define GSL_SPAN_H

#include "gsl_config.hpp"
#include "stdex/type_traits.hpp"
#include "stdex/algorithm.hpp"

#include "gsl_assert"
#include "gsl_byte"
#include "gsl_util"
#include <array>
#include <iterator>
#include <limits>
#include <stdexcept>
#include <type_traits>
#include <utility>
#include <memory>

#ifdef _MSC_VER

#pragma warning(push)

// turn off some warnings that are noisy about our Expects statements
#pragma warning(disable : 4127) // conditional expression is constant

// blanket turn off warnings from CppCoreCheck for now
// so people aren't annoyed by them when running the tool.
// more targeted suppressions will be added in a future update to the GSL
#pragma warning(disable : 26481 26482 26483 26485 26490 26491 26492 26493 26495)

// No MSVC does constexpr fully yet
#pragma push_macro("constexpr")
#define constexpr /*constexpr*/

// VS 2013 workarounds
#if _MSC_VER <= 1800

#define GSL_MSVC_HAS_VARIADIC_CTOR_BUG
#define GSL_MSVC_NO_DEFAULT_MOVE_CTOR
#define GSL_MSVC_NO_CPP14_STD_EQUAL

// noexcept is not understood
#ifndef GSL_THROW_ON_CONTRACT_VIOLATION
#pragma push_macro("noexcept")
#define noexcept /*noexcept*/
#endif

#pragma push_macro("alignof")
#define alignof __alignof

// turn off some misguided warnings
#pragma warning(push)
#pragma warning(disable : 4351) // warns about newly introduced aggregate initializer behavior
#pragma warning(disable : 4512) // warns that assignment op could not be generated

#endif // _MSC_VER <= 1800

#endif // _MSC_VER

#ifdef GSL_THROW_ON_CONTRACT_VIOLATION

#ifdef _MSC_VER
#pragma push_macro("noexcept")
#endif

//#define noexcept /*noexcept*/

#endif // GSL_THROW_ON_CONTRACT_VIOLATION

namespace gsl
{

// [views.constants], constants
constexpr const std::ptrdiff_t dynamic_extent = -1;

template <class ElementType, std::ptrdiff_t Extent = dynamic_extent>
class span;

// implementation details
namespace details
{
    template <class T>
    struct is_span_oracle : std::false_type
    {
    };

    template <class ElementType, std::ptrdiff_t Extent>
    struct is_span_oracle<gsl::span<ElementType, Extent>> : std::true_type
    {
    };

    template <class T>
    struct is_span : public is_span_oracle<stdex::remove_cv_t<T>>
    {
    };

    template <class T>
    struct is_std_array_oracle : std::false_type
    {
    };

    template <class ElementType, size_t Extent>
    struct is_std_array_oracle<std::array<ElementType, Extent>> : std::true_type
    {
    };

    template <class T>
    struct is_std_array : public is_std_array_oracle<stdex::remove_cv_t<T>>
    {
    };
    
    template <std::ptrdiff_t From, std::ptrdiff_t To>
    struct is_allowed_extent_conversion
        : public std::integral_constant<bool, From == To || From == gsl::dynamic_extent ||
                                                  To == gsl::dynamic_extent>
    {
    };

    template <class From, class To>
    struct is_allowed_element_type_conversion
        : public std::integral_constant<bool, std::is_same<From, stdex::remove_cv_t<To>>::value ||
                                              std::is_convertible<From(*)[], To (*)[]>::value>
    {
    };

    template <class Span, bool IsConst>
    class span_iterator
    {
        using element_type_ = typename Span::element_type;
    public:
        using iterator_category = std::random_access_iterator_tag;
        using value_type = stdex::remove_const_t<element_type_>;
        using difference_type = typename Span::index_type;

        using reference =
            stdex::conditional_t<IsConst, const element_type_, element_type_> &;
        using pointer = stdex::add_pointer_t<reference>;

        constexpr span_iterator() noexcept : span_iterator(nullptr, 0) {}

        GSL_CONTRACT_CONSTEXPR span_iterator(const Span* span, typename Span::index_type index)
            : span_(span), index_(index)
        {
            Expects(span == nullptr || (index_ >= 0 && index <= span_->length()));
        }

        friend class span_iterator<Span, true>;
        constexpr span_iterator(const span_iterator<Span, false>& other) noexcept
            : span_iterator(other.span_, other.index_)
        {
        }

#if __cplusplus >= 201402L
        constexpr span_iterator<Span, IsConst>& operator=(const span_iterator<Span, IsConst>&) noexcept = default;
#endif
        GSL_CONTRACT_CONSTEXPR reference operator*() const
        {
            Expects(span_);
            return (*span_)[index_];
        }

        GSL_CONTRACT_CONSTEXPR pointer operator->() const
        {
            Expects(span_);
            return &((*span_)[index_]);
        }

        GSL_MUTABLE_CONSTEXPR span_iterator& operator++() noexcept
        {
            Expects(span_ && index_ >= 0 && index_ < span_->length());
            ++index_;
            return *this;
        }

        GSL_MUTABLE_CONSTEXPR span_iterator operator++(int) noexcept
        {
            auto ret = *this;
            ++(*this);
            return ret;
        }

        GSL_MUTABLE_CONSTEXPR span_iterator& operator--() noexcept
        {
            Expects(span_ && index_ > 0 && index_ <= span_->length());
            --index_;
            return *this;
        }

        GSL_MUTABLE_CONSTEXPR span_iterator operator--(int) noexcept
        {
            auto ret = *this;
            --(*this);
            return ret;
        }

        GSL_CXX14_CONSTEXPR span_iterator operator+(difference_type n) const noexcept
        {
            auto ret = *this;
            return ret += n;
        }

        GSL_MUTABLE_CONSTEXPR span_iterator& operator+=(difference_type n) noexcept
        {
            Expects(span_ && (index_ + n) >= 0 && (index_ + n) <= span_->length());
            index_ += n;
            return *this;
        }

        GSL_CXX14_CONSTEXPR span_iterator operator-(difference_type n) const noexcept
        {
            auto ret = *this;
            return ret -= n;
        }

        GSL_MUTABLE_CONSTEXPR span_iterator& operator-=(difference_type n) noexcept { return *this += -n; }

        GSL_CONTRACT_CONSTEXPR difference_type operator-(const span_iterator& rhs) const noexcept
        {
            Expects(span_ == rhs.span_);
            return index_ - rhs.index_;
        }

        constexpr reference operator[](difference_type n) const noexcept { return *(*this + n); }

        constexpr friend bool operator==(const span_iterator& lhs,
                                         const span_iterator& rhs) noexcept
        {
            return lhs.span_ == rhs.span_ && lhs.index_ == rhs.index_;
        }

        constexpr friend bool operator!=(const span_iterator& lhs,
                                         const span_iterator& rhs) noexcept
        {
            return !(lhs == rhs);
        }

        GSL_CONTRACT_CONSTEXPR friend bool operator<(const span_iterator& lhs, const span_iterator& rhs) noexcept
        {
            Expects(lhs.span_ == rhs.span_);
            return lhs.index_ < rhs.index_;
        }

        constexpr friend bool operator<=(const span_iterator& lhs,
                                         const span_iterator& rhs) noexcept
        {
            return !(rhs < lhs);
        }

        constexpr friend bool operator>(const span_iterator& lhs, const span_iterator& rhs) noexcept
        {
            return rhs < lhs;
        }

        constexpr friend bool operator>=(const span_iterator& lhs,
                                         const span_iterator& rhs) noexcept
        {
            return !(rhs > lhs);
        }

        void swap(span_iterator& rhs) noexcept
        {
            std::swap(index_, rhs.index_);
            std::swap(span_, rhs.span_);
        }

    protected:
        const Span* span_;
        std::ptrdiff_t index_;
    };

    template <class Span, bool IsConst>
    constexpr span_iterator<Span, IsConst>
    operator+(typename span_iterator<Span, IsConst>::difference_type n,
              const span_iterator<Span, IsConst>& rhs) noexcept
    {
        return rhs + n;
    }

    template <class Span, bool IsConst>
    constexpr span_iterator<Span, IsConst>
    operator-(typename span_iterator<Span, IsConst>::difference_type n,
              const span_iterator<Span, IsConst>& rhs) noexcept
    {
        return rhs - n;
    }

    template <std::ptrdiff_t Ext>
    class extent_type
    {
    public:
        using index_type = std::ptrdiff_t;

        static_assert(Ext >= 0, "A fixed-size span must be >= 0 in size.");

        constexpr extent_type() noexcept {}

        template <index_type Other>
        GSL_CONTRACT_CONSTEXPR extent_type(extent_type<Other> ext)
        {
            static_assert(Other == Ext || Other == dynamic_extent,
                          "Mismatch between fixed-size extent and size of initializing data.");
            Expects(ext.size() == Ext);
        }

        GSL_CONTRACT_CONSTEXPR extent_type(index_type size) { Expects(size == Ext); }

        constexpr inline index_type size() const noexcept { return Ext; }
    };

    template <>
    class extent_type<dynamic_extent>
    {
    public:
        using index_type = std::ptrdiff_t;

        template <index_type Other>
        explicit constexpr extent_type(extent_type<Other> ext) : size_(ext.size())
        {
        }

        explicit GSL_CONTRACT_CONSTEXPR extent_type(index_type size) : size_(size) { Expects(size >= 0); }

        constexpr inline index_type size() const noexcept { return size_; }

    private:
        index_type size_;
    };
} // namespace details

// [span], class template span
template <class ElementType, std::ptrdiff_t Extent>
class span
{
public:
    // constants and types
    using element_type = ElementType;
    using index_type = std::ptrdiff_t;
    using pointer = element_type*;
    using reference = element_type&;

    using iterator = details::span_iterator<span<ElementType, Extent>, false>;
    using const_iterator = details::span_iterator<span<ElementType, Extent>, true>;
    using reverse_iterator = std::reverse_iterator<iterator>;
    using const_reverse_iterator = std::reverse_iterator<const_iterator>;

    constexpr static const index_type extent = Extent;

    // [span.cons], span constructors, copy, assignment, and destructor
    template <bool Dependent = false,
        // "Dependent" is needed to make "std::enable_if_t<Dependent || Extent <= 0>" SFINAE,
        // since "std::enable_if_t<Extent <= 0>" is ill-formed when Extent is greater than 0.
        class = stdex::enable_if_t<(Dependent || Extent <= 0)>>
    constexpr span() noexcept : storage_(nullptr, details::extent_type<0>()) {}

    constexpr span(std::nullptr_t) noexcept : span() {}

    constexpr span(pointer ptr, index_type count) : storage_(ptr, count) {}

    constexpr span(pointer firstElem, pointer lastElem)
        : storage_(firstElem, std::distance(firstElem, lastElem))
    {
    }

    template <size_t N>
    constexpr span(element_type (&arr)[N]) noexcept : storage_(&arr[0], details::extent_type<N>())
    {
    }

    template <size_t N, class ArrayElementType = stdex::remove_const_t<element_type>>
    constexpr span(std::array<ArrayElementType, N>& arr) noexcept
        : storage_(&arr[0], details::extent_type<N>())
    {
    }

    template <size_t N>
    constexpr span(const std::array<stdex::remove_const_t<element_type>, N>& arr) noexcept
        : storage_(&arr[0], details::extent_type<N>())
    {
    }

    template<class ArrayElementType = std::add_pointer<element_type>>
    constexpr span(const std::unique_ptr<ArrayElementType>& ptr, index_type count) : storage_(ptr.get(), count) {}

    constexpr span(const std::unique_ptr<ElementType>& ptr) : storage_(ptr.get(), ptr.get() ? 1 : 0) {}
    constexpr span(const std::shared_ptr<ElementType>& ptr) : storage_(ptr.get(), ptr.get() ? 1 : 0) {}

    // NB: the SFINAE here uses .data() as a incomplete/imperfect proxy for the requirement
    // on Container to be a contiguous sequence container.
    template <class Container,
              class = stdex::enable_if_t<
                  !details::is_span<Container>::value && !details::is_std_array<Container>::value &&
                  std::is_convertible<typename Container::pointer, pointer>::value &&
                  std::is_convertible<typename Container::pointer,
                                      decltype(std::declval<Container>().data())>::value>>
    constexpr span(Container& cont) : span(cont.data(), narrow<index_type>(cont.size()))
    {
    }

    template <class Container,
              class = stdex::enable_if_t<
                  std::is_const<element_type>::value && !details::is_span<Container>::value &&
                  std::is_convertible<typename Container::pointer, pointer>::value &&
                  std::is_convertible<typename Container::pointer,
                                      decltype(std::declval<Container>().data())>::value>>
    constexpr span(const Container& cont) : span(cont.data(), narrow<index_type>(cont.size()))
    {
    }

    constexpr span(const span& other) noexcept = default;
#ifndef GSL_MSVC_NO_DEFAULT_MOVE_CTOR
    constexpr span(span&& other) noexcept = default;
#else
    constexpr span(span&& other) noexcept : storage_(std::move(other.storage_)) {}
#endif

    template <
        class OtherElementType, std::ptrdiff_t OtherExtent,
        class = stdex::enable_if_t<
            details::is_allowed_extent_conversion<OtherExtent, Extent>::value &&
            details::is_allowed_element_type_conversion<OtherElementType, element_type>::value>>
    constexpr span(const span<OtherElementType, OtherExtent>& other)
        : storage_(other.data(), details::extent_type<OtherExtent>(other.size()))
    {
    }

    template <
        class OtherElementType, std::ptrdiff_t OtherExtent,
        class = stdex::enable_if_t<
            details::is_allowed_extent_conversion<OtherExtent, Extent>::value &&
            details::is_allowed_element_type_conversion<OtherElementType, element_type>::value>>
    constexpr span(span<OtherElementType, OtherExtent>&& other)
        : storage_(other.data(), details::extent_type<OtherExtent>(other.size()))
    {
    }

    ~span() noexcept = default;
    GSL_DEFAULT_CONSTEXPR span& operator=(const span& other) noexcept = default;

#ifndef GSL_MSVC_NO_DEFAULT_MOVE_CTOR
    GSL_DEFAULT_CONSTEXPR span& operator=(span&& other) noexcept = default;
#else
    constexpr span& operator=(span&& other) noexcept
    {
        storage_ = std::move(other.storage_);
        return *this;
    }
#endif
    // [span.sub], span subviews
    template <std::ptrdiff_t Count>
    GSL_CONTRACT_CONSTEXPR span<element_type, Count> first() const
    {
        Expects(Count >= 0 && Count <= size());
        return {data(), Count};
    }

    template <std::ptrdiff_t Count>
    GSL_CONTRACT_CONSTEXPR span<element_type, Count> last() const
    {
        Expects(Count >= 0 && Count <= size());
        return {data() + (size() - Count), Count};
    }

    template <std::ptrdiff_t Offset, std::ptrdiff_t Count = dynamic_extent>
    GSL_CONTRACT_CONSTEXPR span<element_type, Count> subspan() const
    {
        Expects((Offset == 0 || (Offset > 0 && Offset <= size())) &&
                (Count == dynamic_extent || (Count >= 0 && Offset + Count <= size())));
        return {data() + Offset, Count == dynamic_extent ? size() - Offset : Count};
    }

    GSL_CONTRACT_CONSTEXPR span<element_type, dynamic_extent> first(index_type count) const
    {
        Expects(count >= 0 && count <= size());
        return {data(), count};
    }

    GSL_CONTRACT_CONSTEXPR span<element_type, dynamic_extent> last(index_type count) const
    {
        Expects(count >= 0 && count <= size());
        return {data() + (size() - count), count};
    }

    GSL_CONTRACT_CONSTEXPR span<element_type, dynamic_extent> subspan(index_type offset,
                                                         index_type count = dynamic_extent) const
    {
        Expects((offset == 0 || (offset > 0 && offset <= size())) &&
                (count == dynamic_extent || (count >= 0 && offset + count <= size())));
        return {data() + offset, count == dynamic_extent ? size() - offset : count};
    }

    // [span.obs], span observers
    constexpr index_type length() const noexcept { return size(); }
    constexpr index_type size() const noexcept { return storage_.size(); }
    constexpr index_type length_bytes() const noexcept { return size_bytes(); }
    constexpr index_type size_bytes() const noexcept { return size() * narrow_cast<index_type>(sizeof(element_type)); }
    constexpr bool empty() const noexcept { return size() == 0; }

    // [span.elem], span element access
    GSL_CONTRACT_CONSTEXPR reference operator[](index_type idx) const
    {
        Expects(idx >= 0 && idx < storage_.size());
        return data()[idx];
    }

    constexpr reference at(index_type idx) const { return this->operator[](idx); }
    constexpr reference operator()(index_type idx) const { return this->operator[](idx); }
    constexpr pointer data() const noexcept { return storage_.data(); }

    // [span.iter], span iterator support
    iterator begin() const noexcept { return {this, 0}; }
    iterator end() const noexcept { return {this, length()}; }

    const_iterator cbegin() const noexcept { return {this, 0}; }
    const_iterator cend() const noexcept { return {this, length()}; }

    reverse_iterator rbegin() const noexcept { return reverse_iterator{end()}; }
    reverse_iterator rend() const noexcept { return reverse_iterator{begin()}; }

    const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator{cend()}; }
    const_reverse_iterator crend() const noexcept { return const_reverse_iterator{cbegin()}; }

private:
    // this implementation detail class lets us take advantage of the
    // empty base class optimization to pay for only storage of a single
    // pointer in the case of fixed-size spans
    template <class ExtentType>
    class storage_type : public ExtentType
    {
    public:
        template <class OtherExtentType>
        GSL_CONTRACT_CONSTEXPR storage_type(pointer data, OtherExtentType ext) : ExtentType(ext), data_(data)
        {
            Expects((!data && ExtentType::size() == 0) || (data && ExtentType::size() >= 0));
        }

        constexpr inline pointer data() const noexcept { return data_; }

    private:
        pointer data_;
    };

    storage_type<details::extent_type<Extent>> storage_;
};

// [span.comparison], span comparison operators
template <class ElementType, std::ptrdiff_t FirstExtent, std::ptrdiff_t SecondExtent>
constexpr bool operator==(const span<ElementType, FirstExtent>& l,
                          const span<ElementType, SecondExtent>& r)
{
#ifdef GSL_MSVC_NO_CPP14_STD_EQUAL
    return (l.size() == r.size()) && std::equal(l.begin(), l.end(), r.begin());
#else
    return stdex::equal(l.begin(), l.end(), r.begin(), r.end());
#endif
}

template <class ElementType, std::ptrdiff_t Extent>
constexpr bool operator!=(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r)
{
    return !(l == r);
}

template <class ElementType, std::ptrdiff_t Extent>
constexpr bool operator<(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r)
{
    return std::lexicographical_compare(l.begin(), l.end(), r.begin(), r.end());
}

template <class ElementType, std::ptrdiff_t Extent>
constexpr bool operator<=(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r)
{
    return !(l > r);
}

template <class ElementType, std::ptrdiff_t Extent>
constexpr bool operator>(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r)
{
    return r < l;
}

template <class ElementType, std::ptrdiff_t Extent>
constexpr bool operator>=(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r)
{
    return !(l < r);
}

namespace details
{
    // if we only supported compilers with good constexpr support then
    // this pair of classes could collapse down to a constexpr function

    // we should use a narrow_cast<> to go to size_t, but older compilers may not see it as
    // constexpr
    // and so will fail compilation of the template
    template <class ElementType, std::ptrdiff_t Extent>
    struct calculate_byte_size
        : std::integral_constant<std::ptrdiff_t,
                                 static_cast<std::ptrdiff_t>(sizeof(ElementType) *
                                                             static_cast<std::size_t>(Extent))>
    {
    };

    template <class ElementType>
    struct calculate_byte_size<ElementType, dynamic_extent>
        : std::integral_constant<std::ptrdiff_t, dynamic_extent>
    {
    };
}

// [span.objectrep], views of object representation
template <class ElementType, std::ptrdiff_t Extent>
span<const byte, details::calculate_byte_size<ElementType, Extent>::value>
as_bytes(span<ElementType, Extent> s) noexcept
{
    return {reinterpret_cast<const byte*>(s.data()), s.size_bytes()};
}

template <class ElementType, std::ptrdiff_t Extent,
          class = stdex::enable_if_t<!std::is_const<ElementType>::value>>
span<byte, details::calculate_byte_size<ElementType, Extent>::value>
as_writeable_bytes(span<ElementType, Extent> s) noexcept
{
    return {reinterpret_cast<byte*>(s.data()), s.size_bytes()};
}

//
// make_span() - Utility functions for creating spans
//
template <class ElementType>
span<ElementType>
make_span(ElementType* ptr, typename span<ElementType>::index_type count)
{ return span<ElementType>(ptr, count); }

template <class ElementType>
span<ElementType>
make_span(ElementType* firstElem, ElementType* lastElem)
{ return span<ElementType>(firstElem, lastElem); }

template <class ElementType, size_t N>
span<ElementType>
make_span(ElementType (&arr)[N])
{ return span<ElementType>(arr); }

template <class Container>
span<typename Container::value_type>
make_span(Container &cont)
{ return span<typename Container::value_type>(cont); }

template <class Container>
span<const typename Container::value_type>
make_span(const Container &cont)
{ return span<const typename Container::value_type>(cont); }

template <class Ptr>
span<typename Ptr::element_type>
make_span(Ptr& cont, std::ptrdiff_t count)
{ return span<typename Ptr::element_type>(cont, count); }

template <class Ptr>
span<typename Ptr::element_type>
make_span(Ptr& cont)
{ return span<typename Ptr::element_type>(cont); }


// Specialization of gsl::at for span
template <class ElementType, std::ptrdiff_t Extent>
constexpr ElementType& at(const span<ElementType, Extent>& s, std::ptrdiff_t index)
{
    // No bounds checking here because it is done in span::operator[] called below
    return s[index];
}

} // namespace gsl

#ifdef _MSC_VER

#undef constexpr
#pragma pop_macro("constexpr")

#if _MSC_VER <= 1800
#pragma warning(pop)

#ifndef GSL_THROW_ON_CONTRACT_VIOLATION
#undef noexcept
#pragma pop_macro("noexcept")
#endif // GSL_THROW_ON_CONTRACT_VIOLATION

#pragma pop_macro("alignof")

#undef GSL_MSVC_HAS_VARIADIC_CTOR_BUG

#endif // _MSC_VER <= 1800

#endif // _MSC_VER

#if defined(GSL_THROW_ON_CONTRACT_VIOLATION)

#undef noexcept

#ifdef _MSC_VER
#pragma pop_macro("noexcept")
#endif

#endif // GSL_THROW_ON_CONTRACT_VIOLATION

#ifdef _MSC_VER
#pragma warning(pop)
#endif

#endif // GSL_SPAN_H