span revision 3aea9f7201c4bcb03011b47ce296f3b4afaea7ff
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 <class From, class To> 127 struct is_allowed_pointer_conversion 128 : public std::integral_constant<bool, std::is_pointer<From>::value && 129 std::is_pointer<To>::value && 130 std::is_convertible<From, To>::value> 131 { 132 }; 133 134 template <class From, class To> 135 struct is_allowed_integral_conversion 136 : public std::integral_constant< 137 bool, std::is_integral<From>::value && std::is_integral<To>::value && 138 sizeof(From) == sizeof(To) && alignof(From) == alignof(To) && 139 std::is_convertible<From, To>::value> 140 { 141 }; 142 143 template <std::ptrdiff_t From, std::ptrdiff_t To> 144 struct is_allowed_extent_conversion 145 : public std::integral_constant<bool, From == To || From == gsl::dynamic_extent || 146 To == gsl::dynamic_extent> 147 { 148 }; 149 150 template <class From, class To> 151 struct is_allowed_element_type_conversion 152 : public std::integral_constant<bool, std::is_same<From, std::remove_cv_t<To>>::value || 153 is_allowed_pointer_conversion<From, To>::value || 154 is_allowed_integral_conversion<From, To>::value> 155 { 156 }; 157 158 template <class From> 159 struct is_allowed_element_type_conversion<From, byte> 160 : public std::integral_constant<bool, !std::is_const<From>::value> 161 { 162 }; 163 164 template <class From> 165 struct is_allowed_element_type_conversion<From, const byte> : public std::true_type 166 { 167 }; 168 169 template <class Span, bool IsConst> 170 class span_iterator 171 { 172 public: 173 using iterator_category = std::random_access_iterator_tag; 174 using value_type = 175 std::conditional_t<IsConst, std::add_const_t<typename Span::element_type>, 176 typename Span::element_type>; 177 using difference_type = typename Span::index_type; 178 179 using pointer = std::add_pointer_t<value_type>; 180 using reference = std::add_lvalue_reference_t<value_type>; 181 182 constexpr span_iterator() noexcept : span_iterator(nullptr, 0) {} 183 184 constexpr span_iterator(const Span* span, typename Span::index_type index) 185 : span_(span), index_(index) 186 { 187 Expects(span == nullptr || (index_ >= 0 && index <= span_->length())); 188 } 189 190 friend class span_iterator<Span, true>; 191 constexpr span_iterator(const span_iterator<Span, false>& other) noexcept 192 : span_iterator(other.span_, other.index_) 193 { 194 } 195 196 constexpr reference operator*() const 197 { 198 Expects(span_); 199 return (*span_)[index_]; 200 } 201 202 constexpr pointer operator->() const 203 { 204 Expects(span_); 205 return &((*span_)[index_]); 206 } 207 208 constexpr span_iterator& operator++() noexcept 209 { 210 Expects(span_ && index_ >= 0 && index_ < span_->length()); 211 ++index_; 212 return *this; 213 } 214 215 constexpr span_iterator operator++(int) noexcept 216 { 217 auto ret = *this; 218 ++(*this); 219 return ret; 220 } 221 222 constexpr span_iterator& operator--() noexcept 223 { 224 Expects(span_ && index_ > 0 && index_ <= span_->length()); 225 --index_; 226 return *this; 227 } 228 229 constexpr span_iterator operator--(int) noexcept 230 { 231 auto ret = *this; 232 --(*this); 233 return ret; 234 } 235 236 constexpr span_iterator operator+(difference_type n) const noexcept 237 { 238 auto ret = *this; 239 return ret += n; 240 } 241 242 constexpr span_iterator& operator+=(difference_type n) noexcept 243 { 244 Expects(span_ && (index_ + n) >= 0 && (index_ + n) <= span_->length()); 245 index_ += n; 246 return *this; 247 } 248 249 constexpr span_iterator operator-(difference_type n) const noexcept 250 { 251 auto ret = *this; 252 return ret -= n; 253 } 254 255 constexpr span_iterator& operator-=(difference_type n) noexcept { return *this += -n; } 256 257 constexpr difference_type operator-(const span_iterator& rhs) const noexcept 258 { 259 Expects(span_ == rhs.span_); 260 return index_ - rhs.index_; 261 } 262 263 constexpr reference operator[](difference_type n) const noexcept { return *(*this + n); } 264 265 constexpr friend bool operator==(const span_iterator& lhs, 266 const span_iterator& rhs) noexcept 267 { 268 return lhs.span_ == rhs.span_ && lhs.index_ == rhs.index_; 269 } 270 271 constexpr friend bool operator!=(const span_iterator& lhs, 272 const span_iterator& rhs) noexcept 273 { 274 return !(lhs == rhs); 275 } 276 277 constexpr friend bool operator<(const span_iterator& lhs, const span_iterator& rhs) noexcept 278 { 279 Expects(lhs.span_ == rhs.span_); 280 return lhs.index_ < rhs.index_; 281 } 282 283 constexpr friend bool operator<=(const span_iterator& lhs, 284 const span_iterator& rhs) noexcept 285 { 286 return !(rhs < lhs); 287 } 288 289 constexpr friend bool operator>(const span_iterator& lhs, const span_iterator& rhs) noexcept 290 { 291 return rhs < lhs; 292 } 293 294 constexpr friend bool operator>=(const span_iterator& lhs, 295 const span_iterator& rhs) noexcept 296 { 297 return !(rhs > lhs); 298 } 299 300 void swap(span_iterator& rhs) noexcept 301 { 302 std::swap(index_, rhs.index_); 303 std::swap(span_, rhs.span_); 304 } 305 306 protected: 307 const Span* span_; 308 std::ptrdiff_t index_; 309 }; 310 311 template <class Span, bool IsConst> 312 constexpr span_iterator<Span, IsConst> 313 operator+(typename span_iterator<Span, IsConst>::difference_type n, 314 const span_iterator<Span, IsConst>& rhs) noexcept 315 { 316 return rhs + n; 317 } 318 319 template <class Span, bool IsConst> 320 constexpr span_iterator<Span, IsConst> 321 operator-(typename span_iterator<Span, IsConst>::difference_type n, 322 const span_iterator<Span, IsConst>& rhs) noexcept 323 { 324 return rhs - n; 325 } 326 327 template <std::ptrdiff_t Ext> 328 class extent_type 329 { 330 public: 331 using index_type = std::ptrdiff_t; 332 333 static_assert(Ext >= 0, "A fixed-size span must be >= 0 in size."); 334 335 constexpr extent_type() noexcept {} 336 337 template <index_type Other> 338 constexpr extent_type(extent_type<Other> ext) noexcept 339 { 340 static_assert(Other == Ext || Other == dynamic_extent, 341 "Mismatch between fixed-size extent and size of initializing data."); 342 Expects(ext.size() == Ext); 343 } 344 345 constexpr extent_type(index_type size) { Expects(size == Ext); } 346 347 constexpr inline index_type size() const noexcept { return Ext; } 348 }; 349 350 template <> 351 class extent_type<dynamic_extent> 352 { 353 public: 354 using index_type = std::ptrdiff_t; 355 356 template <index_type Other> 357 explicit constexpr extent_type(extent_type<Other> ext) : size_(ext.size()) 358 { 359 } 360 361 explicit constexpr extent_type(index_type size) : size_(size) { Expects(size >= 0); } 362 363 constexpr inline index_type size() const noexcept { return size_; } 364 365 private: 366 index_type size_; 367 }; 368} // namespace details 369 370// [span], class template span 371template <class ElementType, std::ptrdiff_t Extent> 372class span 373{ 374public: 375 // constants and types 376 using element_type = ElementType; 377 using index_type = std::ptrdiff_t; 378 using pointer = element_type*; 379 using reference = element_type&; 380 381 using iterator = details::span_iterator<span<ElementType, Extent>, false>; 382 using const_iterator = details::span_iterator<span<ElementType, Extent>, true>; 383 using reverse_iterator = std::reverse_iterator<iterator>; 384 using const_reverse_iterator = std::reverse_iterator<const_iterator>; 385 386 constexpr static const index_type extent = Extent; 387 388 // [span.cons], span constructors, copy, assignment, and destructor 389 constexpr span() noexcept : storage_(nullptr, details::extent_type<0>()) {} 390 391 constexpr span(std::nullptr_t) noexcept : span() {} 392 393 constexpr span(pointer ptr, index_type count) : storage_(ptr, count) {} 394 395 constexpr span(pointer firstElem, pointer lastElem) 396 : storage_(firstElem, std::distance(firstElem, lastElem)) 397 { 398 } 399 400 template <size_t N> 401 constexpr span(element_type (&arr)[N]) noexcept : storage_(&arr[0], details::extent_type<N>()) 402 { 403 } 404 405 template <size_t N, class ArrayElementType = std::remove_const_t<element_type>> 406 constexpr span(std::array<ArrayElementType, N>& arr) noexcept 407 : storage_(&arr[0], details::extent_type<N>()) 408 { 409 } 410 411 template <size_t N> 412 constexpr span(const std::array<std::remove_const_t<element_type>, N>& arr) noexcept 413 : storage_(&arr[0], details::extent_type<N>()) 414 { 415 } 416 417 // NB: the SFINAE here uses .data() as a incomplete/imperfect proxy for the requirement 418 // on Container to be a contiguous sequence container. 419 template <class Container, 420 class = std::enable_if_t< 421 !details::is_span<Container>::value && !details::is_std_array<Container>::value && 422 std::is_convertible<typename Container::pointer, pointer>::value && 423 std::is_convertible<typename Container::pointer, 424 decltype(std::declval<Container>().data())>::value>> 425 constexpr span(Container& cont) : span(cont.data(), cont.size()) 426 { 427 } 428 429 template <class Container, 430 class = std::enable_if_t< 431 std::is_const<element_type>::value && !details::is_span<Container>::value && 432 std::is_convertible<typename Container::pointer, pointer>::value && 433 std::is_convertible<typename Container::pointer, 434 decltype(std::declval<Container>().data())>::value>> 435 constexpr span(const Container& cont) : span(cont.data(), cont.size()) 436 { 437 } 438 439 constexpr span(const span& other) noexcept = default; 440#ifndef GSL_MSVC_NO_DEFAULT_MOVE_CTOR 441 constexpr span(span&& other) noexcept = default; 442#else 443 constexpr span(span&& other) noexcept : storage_(std::move(other.storage_)) {} 444#endif 445 446 template < 447 class OtherElementType, std::ptrdiff_t OtherExtent, 448 class = std::enable_if_t< 449 details::is_allowed_extent_conversion<OtherExtent, Extent>::value && 450 details::is_allowed_element_type_conversion<OtherElementType, element_type>::value>> 451 constexpr span(const span<OtherElementType, OtherExtent>& other) 452 : storage_(reinterpret_cast<pointer>(other.data()), 453 details::extent_type<OtherExtent>(other.size())) 454 { 455 } 456 457 template < 458 class OtherElementType, std::ptrdiff_t OtherExtent, 459 class = std::enable_if_t< 460 details::is_allowed_extent_conversion<OtherExtent, Extent>::value && 461 details::is_allowed_element_type_conversion<OtherElementType, element_type>::value>> 462 constexpr span(span<OtherElementType, OtherExtent>&& other) 463 : storage_(reinterpret_cast<pointer>(other.data()), 464 details::extent_type<OtherExtent>(other.size())) 465 { 466 } 467 468 ~span() noexcept = default; 469 constexpr span& operator=(const span& other) noexcept = default; 470 471#ifndef GSL_MSVC_NO_DEFAULT_MOVE_CTOR 472 constexpr span& operator=(span&& other) noexcept = default; 473#else 474 constexpr span& operator=(span&& other) noexcept 475 { 476 storage_ = std::move(other.storage_); 477 return *this; 478 } 479#endif 480 // [span.sub], span subviews 481 template <std::ptrdiff_t Count> 482 constexpr span<element_type, Count> first() const 483 { 484 Expects(Count >= 0 && Count <= size()); 485 return {data(), Count}; 486 } 487 488 template <std::ptrdiff_t Count> 489 constexpr span<element_type, Count> last() const 490 { 491 Expects(Count >= 0 && Count <= size()); 492 return {data() + (size() - Count), Count}; 493 } 494 495 template <std::ptrdiff_t Offset, std::ptrdiff_t Count = dynamic_extent> 496 constexpr span<element_type, Count> subspan() const 497 { 498 Expects((Offset == 0 || (Offset > 0 && Offset <= size())) && 499 (Count == dynamic_extent || (Count >= 0 && Offset + Count <= size()))); 500 return {data() + Offset, Count == dynamic_extent ? size() - Offset : Count}; 501 } 502 503 constexpr span<element_type, dynamic_extent> first(index_type count) const 504 { 505 Expects(count >= 0 && count <= size()); 506 return {data(), count}; 507 } 508 509 constexpr span<element_type, dynamic_extent> last(index_type count) const 510 { 511 Expects(count >= 0 && count <= size()); 512 return {data() + (size() - count), count}; 513 } 514 515 constexpr span<element_type, dynamic_extent> subspan(index_type offset, 516 index_type count = dynamic_extent) const 517 { 518 Expects((offset == 0 || (offset > 0 && offset <= size())) && 519 (count == dynamic_extent || (count >= 0 && offset + count <= size()))); 520 return {data() + offset, count == dynamic_extent ? size() - offset : count}; 521 } 522 523 // [span.obs], span observers 524 constexpr index_type length() const noexcept { return size(); } 525 constexpr index_type size() const noexcept { return storage_.size(); } 526 constexpr index_type length_bytes() const noexcept { return size_bytes(); } 527 constexpr index_type size_bytes() const noexcept { return size() * sizeof(element_type); } 528 constexpr bool empty() const noexcept { return size() == 0; } 529 530 // [span.elem], span element access 531 constexpr reference operator[](index_type idx) const 532 { 533 Expects(idx >= 0 && idx < storage_.size()); 534 return data()[idx]; 535 } 536 constexpr reference operator()(index_type idx) const { return this->operator[](idx); } 537 constexpr pointer data() const noexcept { return storage_.data(); } 538 539 // [span.iter], span iterator support 540 iterator begin() const noexcept { return {this, 0}; } 541 iterator end() const noexcept { return {this, length()}; } 542 543 const_iterator cbegin() const noexcept { return {this, 0}; } 544 const_iterator cend() const noexcept { return {this, length()}; } 545 546 reverse_iterator rbegin() const noexcept { return reverse_iterator{end()}; } 547 reverse_iterator rend() const noexcept { return reverse_iterator{begin()}; } 548 549 const_reverse_iterator crbegin() const noexcept { return const_reverse_iterator{cend()}; } 550 const_reverse_iterator crend() const noexcept { return const_reverse_iterator{cbegin()}; } 551 552private: 553 // this implementation detail class lets us take advantage of the 554 // empty base class optimization to pay for only storage of a single 555 // pointer in the case of fixed-size spans 556 template <class ExtentType> 557 class storage_type : public ExtentType 558 { 559 public: 560 template <class OtherExtentType> 561 constexpr storage_type(pointer data, OtherExtentType ext) : ExtentType(ext), data_(data) 562 { 563 Expects((!data && ExtentType::size() == 0) || (data && ExtentType::size() >= 0)); 564 } 565 566 constexpr inline pointer data() const noexcept { return data_; } 567 568 private: 569 pointer data_; 570 }; 571 572 storage_type<details::extent_type<Extent>> storage_; 573}; 574 575// [span.comparison], span comparison operators 576template <class ElementType, std::ptrdiff_t FirstExtent, std::ptrdiff_t SecondExtent> 577constexpr bool operator==(const span<ElementType, FirstExtent>& l, 578 const span<ElementType, SecondExtent>& r) 579{ 580#ifdef GSL_MSVC_NO_CPP14_STD_EQUAL 581 return (l.size() == r.size()) && std::equal(l.begin(), l.end(), r.begin()); 582#else 583 return std::equal(l.begin(), l.end(), r.begin(), r.end()); 584#endif 585} 586 587template <class ElementType, std::ptrdiff_t Extent> 588constexpr bool operator!=(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r) 589{ 590 return !(l == r); 591} 592 593template <class ElementType, std::ptrdiff_t Extent> 594constexpr bool operator<(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r) 595{ 596 return std::lexicographical_compare(l.begin(), l.end(), r.begin(), r.end()); 597} 598 599template <class ElementType, std::ptrdiff_t Extent> 600constexpr bool operator<=(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r) 601{ 602 return !(l > r); 603} 604 605template <class ElementType, std::ptrdiff_t Extent> 606constexpr bool operator>(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r) 607{ 608 return r < l; 609} 610 611template <class ElementType, std::ptrdiff_t Extent> 612constexpr bool operator>=(const span<ElementType, Extent>& l, const span<ElementType, Extent>& r) 613{ 614 return !(l < r); 615} 616 617namespace details 618{ 619 // if we only supported compilers with good constexpr support then 620 // this pair of classes could collapse down to a constexpr function 621 622 // we should use a narrow_cast<> to go to size_t, but older compilers may not see it as 623 // constexpr 624 // and so will fail compilation of the template 625 template <class ElementType, std::ptrdiff_t Extent> 626 struct calculate_byte_size 627 : std::integral_constant<std::ptrdiff_t, 628 static_cast<std::ptrdiff_t>(sizeof(ElementType) * 629 static_cast<std::size_t>(Extent))> 630 { 631 }; 632 633 template <class ElementType> 634 struct calculate_byte_size<ElementType, dynamic_extent> 635 : std::integral_constant<std::ptrdiff_t, dynamic_extent> 636 { 637 }; 638} 639 640// [span.objectrep], views of object representation 641template <class ElementType, std::ptrdiff_t Extent> 642span<const byte, details::calculate_byte_size<ElementType, Extent>::value> 643as_bytes(span<ElementType, Extent> s) noexcept 644{ 645 return {reinterpret_cast<const byte*>(s.data()), s.size_bytes()}; 646} 647 648template <class ElementType, std::ptrdiff_t Extent, 649 class = std::enable_if_t<!std::is_const<ElementType>::value>> 650span<byte, details::calculate_byte_size<ElementType, Extent>::value> 651as_writeable_bytes(span<ElementType, Extent> s) noexcept 652{ 653 return {reinterpret_cast<byte*>(s.data()), s.size_bytes()}; 654} 655 656} // namespace gsl 657 658#ifdef _MSC_VER 659 660#undef constexpr 661#pragma pop_macro("constexpr") 662 663#if _MSC_VER <= 1800 664#pragma warning(pop) 665 666#ifndef GSL_THROW_ON_CONTRACT_VIOLATION 667#undef noexcept 668#pragma pop_macro("noexcept") 669#endif // GSL_THROW_ON_CONTRACT_VIOLATION 670 671#pragma pop_macro("alignof") 672 673#undef GSL_MSVC_HAS_VARIADIC_CTOR_BUG 674 675#endif // _MSC_VER <= 1800 676 677#endif // _MSC_VER 678 679#if defined(GSL_THROW_ON_CONTRACT_VIOLATION) 680 681#undef noexcept 682 683#ifdef _MSC_VER 684#pragma pop_macro("noexcept") 685#endif 686 687#endif // GSL_THROW_ON_CONTRACT_VIOLATION 688 689#ifdef _MSC_VER 690#pragma warning(pop) 691#endif 692 693#endif // GSL_SPAN_H 694