blob: a5d2823d02f2ddf16b32f06912c70438c8ed6604 [file] [log] [blame]
///////////////////////////////////////////////////////////////////////////////
//
// 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_assert.h"
#include "gsl_byte.h"
#include "gsl_util.h"
#include <array>
#include <iterator>
#include <limits>
#include <stdexcept>
#include <type_traits>
#include <utility>
#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
// 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 /* nothing */
#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 /* nothing */
#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<std::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<std::remove_cv_t<T>>
{
};
template <class From, class To>
struct is_allowed_pointer_conversion
: public std::integral_constant<bool, std::is_pointer<From>::value &&
std::is_pointer<To>::value &&
std::is_convertible<From, To>::value>
{
};
template <class From, class To>
struct is_allowed_integral_conversion
: public std::integral_constant<
bool, std::is_integral<From>::value && std::is_integral<To>::value &&
sizeof(From) == sizeof(To) && alignof(From) == alignof(To) &&
std::is_convertible<From, To>::value>
{
};
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, std::remove_cv_t<To>>::value ||
is_allowed_pointer_conversion<From, To>::value ||
is_allowed_integral_conversion<From, To>::value>
{
};
template <class From>
struct is_allowed_element_type_conversion<From, byte>
: public std::integral_constant<bool, !std::is_const<From>::value>
{
};
template <class From>
struct is_allowed_element_type_conversion<From, const byte> : public std::true_type
{
};
template <class Span>
class const_span_iterator
{
public:
using iterator_category = std::random_access_iterator_tag;
using value_type = typename Span::element_type;
using difference_type = std::ptrdiff_t;
using const_pointer = std::add_const_t<value_type*>;
using pointer = const_pointer;
using const_reference = std::add_const_t<value_type&>;
using reference = const_reference;
constexpr const_span_iterator() : const_span_iterator(nullptr, 0) {}
constexpr const_span_iterator(const Span* span, typename Span::index_type index)
: span_(span), index_(index)
{
Expects(span == nullptr || (index_ >= 0 && index <= span_->length()));
}
constexpr reference operator*() const
{
Expects(span_);
return (*span_)[index_];
}
constexpr pointer operator->() const
{
Expects(span_);
return &((*span_)[index_]);
}
constexpr const_span_iterator& operator++() noexcept
{
Expects(span_ && index_ >= 0 && index_ < span_->length());
++index_;
return *this;
}
constexpr const_span_iterator operator++(int) noexcept
{
auto ret = *this;
++(*this);
return ret;
}
constexpr const_span_iterator& operator--() noexcept
{
Expects(span_ && index_ > 0 && index_ <= span_->length());
--index_;
return *this;
}
constexpr const_span_iterator operator--(int) noexcept
{
auto ret = *this;
--(*this);
return ret;
}
constexpr const_span_iterator operator+(difference_type n) const noexcept
{
auto ret = *this;
return ret += n;
}
constexpr const_span_iterator& operator+=(difference_type n) noexcept
{
Expects(span_ && (index_ + n) >= 0 && (index_ + n) <= span_->length());
index_ += n;
return *this;
}
constexpr const_span_iterator operator-(difference_type n) const noexcept
{
auto ret = *this;
return ret -= n;
}
constexpr const_span_iterator& operator-=(difference_type n) noexcept
{
return *this += -n;
}
constexpr difference_type operator-(const 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 bool operator==(const const_span_iterator& rhs) const noexcept
{
return span_ == rhs.span_ && index_ == rhs.index_;
}
constexpr bool operator!=(const const_span_iterator& rhs) const noexcept
{
return !(*this == rhs);
}
constexpr bool operator<(const const_span_iterator& rhs) const noexcept
{
Expects(span_ == rhs.span_);
return index_ < rhs.index_;
}
constexpr bool operator<=(const const_span_iterator& rhs) const noexcept
{
return !(rhs < *this);
}
constexpr bool operator>(const const_span_iterator& rhs) const noexcept
{
return rhs < *this;
}
constexpr bool operator>=(const const_span_iterator& rhs) const noexcept
{
return !(rhs > *this);
}
void swap(const_span_iterator& rhs) noexcept
{
std::swap(index_, rhs.index_);
std::swap(span_, rhs.span_);
}
private:
const Span* span_;
std::ptrdiff_t index_;
};
template <class Span>
class span_iterator
{
public:
using iterator_category = std::random_access_iterator_tag;
using value_type = typename Span::element_type;
using difference_type = std::ptrdiff_t;
using pointer = value_type*;
using reference = value_type&;
constexpr span_iterator() : span_iterator(nullptr, 0) {}
constexpr span_iterator(const Span* span, typename Span::index_type index)
: span_(span), index_(index)
{
Expects(span == nullptr || (index_ >= 0 && index <= span_->length()));
}
constexpr reference operator*() const
{
Expects(span_);
return (*span_)[index_];
}
constexpr pointer operator->() const
{
Expects(span_);
return &((*span_)[index_]);
}
constexpr span_iterator& operator++() noexcept
{
Expects(span_ && index_ >= 0 && index_ < span_->length());
++index_;
return *this;
}
constexpr span_iterator operator++(int) noexcept
{
auto ret = *this;
++(*this);
return ret;
}
constexpr span_iterator& operator--() noexcept
{
Expects(span_ && index_ > 0 && index_ <= span_->length());
--index_;
return *this;
}
constexpr span_iterator operator--(int) noexcept
{
auto ret = *this;
--(*this);
return ret;
}
constexpr span_iterator operator+(difference_type n) const noexcept
{
auto ret = *this;
return ret += n;
}
constexpr span_iterator& operator+=(difference_type n) noexcept
{
Expects(span_ && (index_ + n) >= 0 && (index_ + n) <= span_->length());
index_ += n;
return *this;
}
constexpr span_iterator operator-(difference_type n) const noexcept
{
auto ret = *this;
return ret -= n;
}
constexpr span_iterator& operator-=(difference_type n) noexcept { return *this += -n; }
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 bool operator==(const span_iterator& rhs) const noexcept
{
return span_ == rhs.span_ && index_ == rhs.index_;
}
constexpr bool operator!=(const span_iterator& rhs) const noexcept
{
return !(*this == rhs);
}
constexpr bool operator<(const span_iterator& rhs) const noexcept
{
Expects(span_ == rhs.span_);
return index_ < rhs.index_;
}
constexpr bool operator<=(const span_iterator& rhs) const noexcept
{
return !(rhs < *this);
}
constexpr bool operator>(const span_iterator& rhs) const noexcept { return rhs < *this; }
constexpr bool operator>=(const span_iterator& rhs) const noexcept
{
return !(rhs > *this);
}
void swap(span_iterator& rhs) noexcept
{
std::swap(index_, rhs.index_);
std::swap(span_, rhs.span_);
}
private:
const Span* span_;
std::ptrdiff_t index_;
};
template <typename Span>
constexpr const_span_iterator<Span>
operator+(typename const_span_iterator<Span>::difference_type n,
const const_span_iterator<Span>& rhs) noexcept
{
return rhs + n;
}
template <typename Span>
constexpr const_span_iterator<Span>
operator-(typename const_span_iterator<Span>::difference_type n,
const const_span_iterator<Span>& rhs) noexcept
{
return rhs - n;
}
template <typename Span>
constexpr span_iterator<Span> operator+(typename span_iterator<Span>::difference_type n,
const span_iterator<Span>& rhs) noexcept
{
return rhs + n;
}
template <typename Span>
constexpr span_iterator<Span> operator-(typename span_iterator<Span>::difference_type n,
const span_iterator<Span>& 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>
constexpr extent_type(extent_type<Other> ext) noexcept
{
static_assert(Other == Ext || Other == dynamic_extent,
"Mismatch between fixed-size extent and size of initializing data.");
Expects(ext.size() == Ext);
}
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 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>>;
using const_iterator = details::const_span_iterator<span<ElementType, Extent>>;
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
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 = std::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<std::remove_const_t<element_type>, N>& arr) noexcept
: storage_(&arr[0], details::extent_type<N>())
{
}
// 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 = std::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(), cont.size())
{
}
template <class Container,
class = std::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(), 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 = std::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_(reinterpret_cast<pointer>(other.data()),
details::extent_type<OtherExtent>(other.size()))
{
}
template <
class OtherElementType, std::ptrdiff_t OtherExtent,
class = std::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_(reinterpret_cast<pointer>(other.data()),
details::extent_type<OtherExtent>(other.size()))
{
}
~span() noexcept = default;
constexpr span& operator=(const span& other) noexcept = default;
#ifndef GSL_MSVC_NO_DEFAULT_MOVE_CTOR
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>
constexpr span<element_type, Count> first() const
{
Expects(Count >= 0 && Count <= size());
return {data(), Count};
}
template <std::ptrdiff_t Count>
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>
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};
}
constexpr span<element_type, dynamic_extent> first(index_type count) const
{
Expects(count >= 0 && count <= size());
return {data(), count};
}
constexpr span<element_type, dynamic_extent> last(index_type count) const
{
Expects(count >= 0 && count <= size());
return {data() + (size() - count), count};
}
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() * sizeof(element_type); }
constexpr bool empty() const noexcept { return size() == 0; }
// [span.elem], span element access
constexpr reference operator[](index_type idx) const
{
Expects(idx >= 0 && idx < storage_.size());
return data()[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>
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 std::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 = std::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()};
}
} // 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 warning(pop)
#pragma pop_macro("noexcept")
#endif
#endif // GSL_THROW_ON_CONTRACT_VIOLATION
#endif // GSL_SPAN_H