1 2/////////////////////////////////////////////////////////////////////////////// 3// 4// Copyright (c) 2015 Microsoft Corporation. All rights reserved. 5// 6// This code is licensed under the MIT License (MIT). 7// 8// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 9// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 10// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 11// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 12// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 13// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 14// THE SOFTWARE. 15// 16/////////////////////////////////////////////////////////////////////////////// 17 18#pragma once 19 20#ifndef GSL_SPAN_H 21#define GSL_SPAN_H 22 23#include "gsl_assert" 24#include "gsl_byte" 25#include "gsl_util" 26#include <array> 27#include <iterator> 28#include <limits> 29#include <stdexcept> 30#include <type_traits> 31#include <utility> 32 33#ifdef _MSC_VER 34 35#pragma warning(push) 36 37// turn off some warnings that are noisy about our Expects statements 38#pragma warning(disable : 4127) // conditional expression is constant 39 40// blanket turn off warnings from CppCoreCheck for now 41// so people aren't annoyed by them when running the tool. 42// more targeted suppressions will be added in a future update to the GSL 43#pragma warning(disable : 26481 26482 26483 26485 26490 26491 26492 26493 26495) 44 45// No MSVC does constexpr fully yet 46#pragma push_macro("constexpr") 47#define constexpr /*constexpr*/ 48 49// VS 2013 workarounds 50#if _MSC_VER <= 1800 51 52#define GSL_MSVC_HAS_VARIADIC_CTOR_BUG 53#define GSL_MSVC_NO_DEFAULT_MOVE_CTOR 54#define GSL_MSVC_NO_CPP14_STD_EQUAL 55 56// noexcept is not understood 57#ifndef GSL_THROW_ON_CONTRACT_VIOLATION 58#pragma push_macro("noexcept") 59#define noexcept /*noexcept*/ 60#endif 61 62#pragma push_macro("alignof") 63#define alignof __alignof 64 65// turn off some misguided warnings 66#pragma warning(push) 67#pragma warning(disable : 4351) // warns about newly introduced aggregate initializer behavior 68#pragma warning(disable : 4512) // warns that assignment op could not be generated 69 70#endif // _MSC_VER <= 1800 71 72#endif // _MSC_VER 73 74#ifdef GSL_THROW_ON_CONTRACT_VIOLATION 75 76#ifdef _MSC_VER 77#pragma push_macro("noexcept") 78#endif 79 80#define noexcept /*noexcept*/ 81 82#endif // GSL_THROW_ON_CONTRACT_VIOLATION 83 84namespace gsl 85{ 86 87// [views.constants], constants 88constexpr const std::ptrdiff_t dynamic_extent = -1; 89 90template <class ElementType, std::ptrdiff_t Extent = dynamic_extent> 91class span; 92 93// implementation details 94namespace details 95{ 96 template <class T> 97 struct is_span_oracle : std::false_type 98 { 99 }; 100 101 template <class ElementType, std::ptrdiff_t Extent> 102 struct is_span_oracle<gsl::span<ElementType, Extent>> : std::true_type 103 { 104 }; 105 106 template <class T> 107 struct is_span : public is_span_oracle<std::remove_cv_t<T>> 108 { 109 }; 110 111 template <class T> 112 struct is_std_array_oracle : std::false_type 113 { 114 }; 115 116 template <class ElementType, size_t Extent> 117 struct is_std_array_oracle<std::array<ElementType, Extent>> : std::true_type 118 { 119 }; 120 121 template <class T> 122 struct is_std_array : public is_std_array_oracle<std::remove_cv_t<T>> 123 { 124 }; 125 126 template <std::ptrdiff_t From, std::ptrdiff_t To> 127 struct is_allowed_extent_conversion 128 : public std::integral_constant<bool, From == To || From == gsl::dynamic_extent || 129 To == gsl::dynamic_extent> 130 { 131 }; 132 133 template <class From, class To> 134 struct is_allowed_element_type_conversion 135 : public std::integral_constant<bool, std::is_convertible<From (*)[], To (*)[]>::value> 136 { 137 }; 138 139 template <class Span, bool IsConst> 140 class span_iterator 141 { 142 public: 143 using iterator_category = std::random_access_iterator_tag; 144 using value_type = 145 std::conditional_t<IsConst, std::add_const_t<typename Span::element_type>, 146 typename Span::element_type>; 147 using difference_type = typename Span::index_type; 148 149 using pointer = std::add_pointer_t<value_type>; 150 using reference = std::add_lvalue_reference_t<value_type>; 151 152 constexpr span_iterator() noexcept : span_iterator(nullptr, 0) {} 153 154 constexpr span_iterator(const Span* span, typename Span::index_type index) 155 : span_(span), index_(index) 156 { 157 Expects(span == nullptr || (index_ >= 0 && index <= span_->length())); 158 } 159 160 friend class span_iterator<Span, true>; 161 constexpr span_iterator(const span_iterator<Span, false>& other) noexcept 162 : span_iterator(other.span_, other.index_) 163 { 164 } 165 166 constexpr span_iterator<Span, IsConst>& operator=(const span_iterator<Span, IsConst>&) noexcept = default; 167 168 constexpr reference operator*() const 169 { 170 Expects(span_); 171 return (*span_)[index_]; 172 } 173 174 constexpr pointer operator->() const 175 { 176 Expects(span_); 177 return &((*span_)[index_]); 178 } 179 180 constexpr span_iterator& operator++() noexcept 181 { 182 Expects(span_ && index_ >= 0 && index_ < span_->length()); 183 ++index_; 184 return *this; 185 } 186 187 constexpr span_iterator operator++(int) noexcept 188 { 189 auto ret = *this; 190 ++(*this); 191 return ret; 192 } 193 194 constexpr span_iterator& operator--() noexcept 195 { 196 Expects(span_ && index_ > 0 && index_ <= span_->length()); 197 --index_; 198 return *this; 199 } 200 201 constexpr span_iterator operator--(int) noexcept 202 { 203 auto ret = *this; 204 --(*this); 205 return ret; 206 } 207 208 constexpr span_iterator operator+(difference_type n) const noexcept 209 { 210 auto ret = *this; 211 return ret += n; 212 } 213 214 constexpr span_iterator& operator+=(difference_type n) noexcept 215 { 216 Expects(span_ && (index_ + n) >= 0 && (index_ + n) <= span_->length()); 217 index_ += n; 218 return *this; 219 } 220 221 constexpr span_iterator operator-(difference_type n) const noexcept 222 { 223 auto ret = *this; 224 return ret -= n; 225 } 226 227 constexpr span_iterator& operator-=(difference_type n) noexcept { return *this += -n; } 228 229 constexpr difference_type operator-(const span_iterator& rhs) const noexcept 230 { 231 Expects(span_ == rhs.span_); 232 return index_ - rhs.index_; 233 } 234 235 constexpr reference operator[](difference_type n) const noexcept { return *(*this + n); } 236 237 constexpr friend bool operator==(const span_iterator& lhs, 238 const span_iterator& rhs) noexcept 239 { 240 return lhs.span_ == rhs.span_ && lhs.index_ == rhs.index_; 241 } 242 243 constexpr friend bool operator!=(const span_iterator& lhs, 244 const span_iterator& rhs) noexcept 245 { 246 return !(lhs == rhs); 247 } 248 249 constexpr friend bool operator<(const span_iterator& lhs, const span_iterator& rhs) noexcept 250 { 251 Expects(lhs.span_ == rhs.span_); 252 return lhs.index_ < rhs.index_; 253 } 254 255 constexpr friend bool operator<=(const span_iterator& lhs, 256 const span_iterator& rhs) noexcept 257 { 258 return !(rhs < lhs); 259 } 260 261 constexpr friend bool operator>(const span_iterator& lhs, const span_iterator& rhs) noexcept 262 { 263 return rhs < lhs; 264 } 265 266 constexpr friend bool operator>=(const span_iterator& lhs, 267 const span_iterator& rhs) noexcept 268 { 269 return !(rhs > lhs); 270 } 271 272 void swap(span_iterator& rhs) noexcept 273 { 274 std::swap(index_, rhs.index_); 275 std::swap(span_, rhs.span_); 276 } 277 278 protected: 279 const Span* span_; 280 std::ptrdiff_t index_; 281 }; 282 283 template <class Span, bool IsConst> 284 constexpr span_iterator<Span, IsConst> 285 operator+(typename span_iterator<Span, IsConst>::difference_type n, 286 const span_iterator<Span, IsConst>& rhs) noexcept 287 { 288 return rhs + n; 289 } 290 291 template <class Span, bool IsConst> 292 constexpr span_iterator<Span, IsConst> 293 operator-(typename span_iterator<Span, IsConst>::difference_type n, 294 const span_iterator<Span, IsConst>& rhs) noexcept 295 { 296 return rhs - n; 297 } 298 299 template <std::ptrdiff_t Ext> 300 class extent_type 301 { 302 public: 303 using index_type = std::ptrdiff_t; 304 305 static_assert(Ext >= 0, "A fixed-size span must be >= 0 in size."); 306 307 constexpr extent_type() noexcept {} 308 309 template <index_type Other> 310 constexpr extent_type(extent_type<Other> ext) noexcept 311 { 312 static_assert(Other == Ext || Other == dynamic_extent, 313 "Mismatch between fixed-size extent and size of initializing data."); 314 Expects(ext.size() == Ext); 315 } 316 317 constexpr extent_type(index_type size) { Expects(size == Ext); } 318 319 constexpr inline index_type size() const noexcept { return Ext; } 320 }; 321 322 template <> 323 class extent_type<dynamic_extent> 324 { 325 public: 326 using index_type = std::ptrdiff_t; 327 328 template <index_type Other> 329 explicit constexpr extent_type(extent_type<Other> ext) : size_(ext.size()) 330 { 331 } 332 333 explicit constexpr extent_type(index_type size) : size_(size) { Expects(size >= 0); } 334 335 constexpr inline index_type size() const noexcept { return size_; } 336 337 private: 338 index_type size_; 339 }; 340} // namespace details 341 342// [span], class template span 343template <class ElementType, std::ptrdiff_t Extent> 344class span 345{ 346public: 347 // constants and types 348 using element_type = ElementType; 349 using index_type = std::ptrdiff_t; 350 using pointer = element_type*; 351 using reference = element_type&; 352 353 using iterator = details::span_iterator<span<ElementType, Extent>, false>; 354 using const_iterator = details::span_iterator<span<ElementType, Extent>, true>; 355 using reverse_iterator = std::reverse_iterator<iterator>; 356 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 357 358 constexpr static const index_type extent = Extent; 359 360 // [span.cons], span constructors, copy, assignment, and destructor 361 constexpr span() noexcept : storage_(nullptr, details::extent_type<0>()) {} 362 363 constexpr span(std::nullptr_t) noexcept : span() {} 364 365 constexpr span(pointer ptr, index_type count) : storage_(ptr, count) {} 366 367 constexpr span(pointer firstElem, pointer lastElem) 368 : storage_(firstElem, std::distance(firstElem, lastElem)) 369 { 370 } 371 372 template <size_t N> 373 constexpr span(element_type (&arr)[N]) noexcept : storage_(&arr[0], details::extent_type<N>()) 374 { 375 } 376 377 template <size_t N, class ArrayElementType = std::remove_const_t<element_type>> 378 constexpr span(std::array<ArrayElementType, N>& arr) noexcept 379 : storage_(&arr[0], details::extent_type<N>()) 380 { 381 } 382 383 template <size_t N> 384 constexpr span(const std::array<std::remove_const_t<element_type>, N>& arr) noexcept 385 : storage_(&arr[0], details::extent_type<N>()) 386 { 387 } 388 389 // NB: the SFINAE here uses .data() as a incomplete/imperfect proxy for the requirement 390 // on Container to be a contiguous sequence container. 391 template <class Container, 392 class = std::enable_if_t< 393 !details::is_span<Container>::value && !details::is_std_array<Container>::value && 394 std::is_convertible<typename Container::pointer, pointer>::value && 395 std::is_convertible<typename Container::pointer, 396 decltype(std::declval<Container>().data())>::value>> 397 constexpr span(Container& cont) : span(cont.data(), narrow<index_type>(cont.size())) 398 { 399 } 400 401 template <class Container, 402 class = std::enable_if_t< 403 std::is_const<element_type>::value && !details::is_span<Container>::value && 404 std::is_convertible<typename Container::pointer, pointer>::value && 405 std::is_convertible<typename Container::pointer, 406 decltype(std::declval<Container>().data())>::value>> 407 constexpr span(const Container& cont) : span(cont.data(), narrow<index_type>(cont.size())) 408 { 409 } 410 411 constexpr span(const span& other) noexcept = default; 412#ifndef GSL_MSVC_NO_DEFAULT_MOVE_CTOR 413 constexpr span(span&& other) noexcept = default; 414#else 415 constexpr span(span&& other) noexcept : storage_(std::move(other.storage_)) {} 416#endif 417 418 template < 419 class OtherElementType, std::ptrdiff_t OtherExtent, 420 class = std::enable_if_t< 421 details::is_allowed_extent_conversion<OtherExtent, Extent>::value && 422 details::is_allowed_element_type_conversion<OtherElementType, element_type>::value>> 423 constexpr span(const span<OtherElementType, OtherExtent>& other) 424 : storage_(other.data(), details::extent_type<OtherExtent>(other.size())) 425 { 426 } 427 428 template < 429 class OtherElementType, std::ptrdiff_t OtherExtent, 430 class = std::enable_if_t< 431 details::is_allowed_extent_conversion<OtherExtent, Extent>::value && 432 details::is_allowed_element_type_conversion<OtherElementType, element_type>::value>> 433 constexpr span(span<OtherElementType, OtherExtent>&& other) 434 : storage_(other.data(), details::extent_type<OtherExtent>(other.size())) 435 { 436 } 437 438 ~span() noexcept = default; 439 constexpr span& operator=(const span& other) noexcept = default; 440 441#ifndef GSL_MSVC_NO_DEFAULT_MOVE_CTOR 442 constexpr span& operator=(span&& other) noexcept = default; 443#else 444 constexpr span& operator=(span&& other) noexcept 445 { 446 storage_ = std::move(other.storage_); 447 return *this; 448 } 449#endif 450 // [span.sub], span subviews 451 template <std::ptrdiff_t Count> 452 constexpr span<element_type, Count> first() const 453 { 454 Expects(Count >= 0 && Count <= size()); 455 return {data(), Count}; 456 } 457 458 template <std::ptrdiff_t Count> 459 constexpr span<element_type, Count> last() const 460 { 461 Expects(Count >= 0 && Count <= size()); 462 return {data() + (size() - Count), Count}; 463 } 464 465 template <std::ptrdiff_t Offset, std::ptrdiff_t Count = dynamic_extent> 466 constexpr span<element_type, Count> subspan() const 467 { 468 Expects((Offset == 0 || (Offset > 0 && Offset <= size())) && 469 (Count == dynamic_extent || (Count >= 0 && Offset + Count <= size()))); 470 return {data() + Offset, Count == dynamic_extent ? size() - Offset : Count}; 471 } 472 473 constexpr span<element_type, dynamic_extent> first(index_type count) const 474 { 475 Expects(count >= 0 && count <= size()); 476 return {data(), count}; 477 } 478 479 constexpr span<element_type, dynamic_extent> last(index_type count) const 480 { 481 Expects(count >= 0 && count <= size()); 482 return {data() + (size() - count), count}; 483 } 484 485 constexpr span<element_type, dynamic_extent> subspan(index_type offset, 486 index_type count = dynamic_extent) const 487 { 488 Expects((offset == 0 || (offset > 0 && offset <= size())) && 489 (count == dynamic_extent || (count >= 0 && offset + count <= size()))); 490 return {data() + offset, count == dynamic_extent ? size() - offset : count}; 491 } 492 493 // [span.obs], span observers 494 constexpr index_type length() const noexcept { return size(); } 495 constexpr index_type size() const noexcept { return storage_.size(); } 496 constexpr index_type length_bytes() const noexcept { return size_bytes(); } 497 constexpr index_type size_bytes() const noexcept { return size() * sizeof(element_type); } 498 constexpr bool empty() const noexcept { return size() == 0; } 499 500 // [span.elem], span element access 501 constexpr reference operator[](index_type idx) const 502 { 503 Expects(idx >= 0 && idx < storage_.size()); 504 return data()[idx]; 505 } 506 507 constexpr reference at(index_type idx) const { return this->operator[](idx); } 508 constexpr reference operator()(index_type idx) const { return this->operator[](idx); } 509 constexpr pointer data() const noexcept { return storage_.data(); } 510 511 // [span.iter], span iterator support 512 iterator begin() const noexcept { return {this, 0}; } 513 iterator end() const noexcept { return {this, length()}; } 514 515 const_iterator cbegin() const noexcept { return {this, 0}; } 516 const_iterator cend() const noexcept { return {this, length()}; } 517 518 reverse_iterator rbegin() const noexcept { return reverse_iterator{end()}; } 519 reverse_iterator rend() const noexcept { return reverse_iterator{begin()}; } 520 521 const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator{cend()}; } 522 const_reverse_iterator crend() const noexcept { return const_reverse_iterator{cbegin()}; } 523 524private: 525 // this implementation detail class lets us take advantage of the 526 // empty base class optimization to pay for only storage of a single 527 // pointer in the case of fixed-size spans 528 template <class ExtentType> 529 class storage_type : public ExtentType 530 { 531 public: 532 template <class OtherExtentType> 533 constexpr storage_type(pointer data, OtherExtentType ext) : ExtentType(ext), data_(data) 534 { 535 Expects((!data && ExtentType::size() == 0) || (data && ExtentType::size() >= 0)); 536 } 537 538 constexpr inline pointer data() const noexcept { return data_; } 539 540 private: 541 pointer data_; 542 }; 543 544 storage_type<details::extent_type<Extent>> storage_; 545}; 546 547// [span.comparison], span comparison operators 548template <class ElementType, std::ptrdiff_t FirstExtent, std::ptrdiff_t SecondExtent> 549constexpr bool operator==(const span<ElementType, FirstExtent>& l, 550 const span<ElementType, SecondExtent>& r) 551{ 552#ifdef GSL_MSVC_NO_CPP14_STD_EQUAL 553 return (l.size() == r.size()) && std::equal(l.begin(), l.end(), r.begin()); 554#else 555 return std::equal(l.begin(), l.end(), r.begin(), r.end()); 556#endif 557} 558 559template <class ElementType, std::ptrdiff_t Extent> 560constexpr bool operator!=(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r) 561{ 562 return !(l == r); 563} 564 565template <class ElementType, std::ptrdiff_t Extent> 566constexpr bool operator<(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r) 567{ 568 return std::lexicographical_compare(l.begin(), l.end(), r.begin(), r.end()); 569} 570 571template <class ElementType, std::ptrdiff_t Extent> 572constexpr bool operator<=(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r) 573{ 574 return !(l > r); 575} 576 577template <class ElementType, std::ptrdiff_t Extent> 578constexpr bool operator>(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r) 579{ 580 return r < l; 581} 582 583template <class ElementType, std::ptrdiff_t Extent> 584constexpr bool operator>=(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r) 585{ 586 return !(l < r); 587} 588 589namespace details 590{ 591 // if we only supported compilers with good constexpr support then 592 // this pair of classes could collapse down to a constexpr function 593 594 // we should use a narrow_cast<> to go to size_t, but older compilers may not see it as 595 // constexpr 596 // and so will fail compilation of the template 597 template <class ElementType, std::ptrdiff_t Extent> 598 struct calculate_byte_size 599 : std::integral_constant<std::ptrdiff_t, 600 static_cast<std::ptrdiff_t>(sizeof(ElementType) * 601 static_cast<std::size_t>(Extent))> 602 { 603 }; 604 605 template <class ElementType> 606 struct calculate_byte_size<ElementType, dynamic_extent> 607 : std::integral_constant<std::ptrdiff_t, dynamic_extent> 608 { 609 }; 610} 611 612// [span.objectrep], views of object representation 613template <class ElementType, std::ptrdiff_t Extent> 614span<const byte, details::calculate_byte_size<ElementType, Extent>::value> 615as_bytes(span<ElementType, Extent> s) noexcept 616{ 617 return {reinterpret_cast<const byte*>(s.data()), s.size_bytes()}; 618} 619 620template <class ElementType, std::ptrdiff_t Extent, 621 class = std::enable_if_t<!std::is_const<ElementType>::value>> 622span<byte, details::calculate_byte_size<ElementType, Extent>::value> 623as_writeable_bytes(span<ElementType, Extent> s) noexcept 624{ 625 return {reinterpret_cast<byte*>(s.data()), s.size_bytes()}; 626} 627 628// Specialization of gsl::at for span 629template <class ElementType, std::ptrdiff_t Extent> 630constexpr ElementType& at(const span<ElementType, Extent>& s, size_t index) 631{ 632 // No bounds checking here because it is done in span::operator[] called below 633 return s[index]; 634} 635 636} // namespace gsl 637 638#ifdef _MSC_VER 639 640#undef constexpr 641#pragma pop_macro("constexpr") 642 643#if _MSC_VER <= 1800 644#pragma warning(pop) 645 646#ifndef GSL_THROW_ON_CONTRACT_VIOLATION 647#undef noexcept 648#pragma pop_macro("noexcept") 649#endif // GSL_THROW_ON_CONTRACT_VIOLATION 650 651#pragma pop_macro("alignof") 652 653#undef GSL_MSVC_HAS_VARIADIC_CTOR_BUG 654 655#endif // _MSC_VER <= 1800 656 657#endif // _MSC_VER 658 659#if defined(GSL_THROW_ON_CONTRACT_VIOLATION) 660 661#undef noexcept 662 663#ifdef _MSC_VER 664#pragma pop_macro("noexcept") 665#endif 666 667#endif // GSL_THROW_ON_CONTRACT_VIOLATION 668 669#ifdef _MSC_VER 670#pragma warning(pop) 671#endif 672 673#endif // GSL_SPAN_H 674