mfbt/Span.h

   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 // Adapted from https://github.com/Microsoft/GSL/blob/3819df6e378ffccf0e29465afe99c3b324c2aa70/include/gsl/span
  18 // and https://github.com/Microsoft/GSL/blob/3819df6e378ffccf0e29465afe99c3b324c2aa70/include/gsl/gsl_util
  19
  20 #ifndef mozilla_Span_h
  21 #define mozilla_Span_h
  22
  23 #include "mozilla/Array.h"
  24 #include "mozilla/Assertions.h"
  25 #include "mozilla/Casting.h"
  26 #include "mozilla/IntegerTypeTraits.h"
  27 #include "mozilla/Move.h"
  28 #include "mozilla/TypeTraits.h"
  29 #include "mozilla/UniquePtr.h"
  30
  31 #include <algorithm>
  32 #include <array>
  33 #include <cstring>
  34 #include <iterator>
  35
  36 #ifdef _MSC_VER
  37 #pragma warning(push)
  38
  39 // turn off some warnings that are noisy about our MOZ_RELEASE_ASSERT statements
  40 #pragma warning(disable : 4127) // conditional expression is constant
  41
  42 // blanket turn off warnings from CppCoreCheck for now
  43 // so people aren't annoyed by them when running the tool.
  44 // more targeted suppressions will be added in a future update to the GSL
  45 #pragma warning(disable : 26481 26482 26483 26485 26490 26491 26492 26493 26495)
  46
  47 #if _MSC_VER < 1910
  48 #pragma push_macro("constexpr")
  49 #define constexpr /*constexpr*/
  50
  51 #endif            // _MSC_VER < 1910
  52 #endif            // _MSC_VER
  53
  54 namespace mozilla {
  55
  56 // Stuff from gsl_util
  57
  58 // narrow_cast(): a searchable way to do narrowing casts of values
  59 template<class T, class U>
  60 inline constexpr T
  61 narrow_cast(U&& u)
  62 {
  63   return static_cast<T>(mozilla::Forward<U>(u));
  64 }
  65
  66 // end gsl_util
  67
  68 // [views.constants], constants
  69 // This was -1 in gsl::span, but using size_t for sizes instead of ptrdiff_t
  70 // and reserving a magic value that realistically doesn't occur in
  71 // compile-time-constant Span sizes makes things a lot less messy in terms of
  72 // comparison between signed and unsigned.
  73 constexpr const size_t dynamic_extent = mozilla::MaxValue<size_t>::value;
  74
  75 template<class ElementType, size_t Extent = dynamic_extent>
  76 class Span;
  77
  78 // implementation details
  79 namespace span_details {
  80
  81 inline size_t strlen16(const char16_t* aZeroTerminated) {
  82   size_t len = 0;
  83   while (*(aZeroTerminated++)) {
  84     len++;
  85   }
  86   return len;
  87 }
  88
  89 // C++14 types that we don't have because we build as C++11.
  90 template<class T>
  91 using remove_cv_t = typename mozilla::RemoveCV<T>::Type;
  92 template<class T>
  93 using remove_const_t = typename mozilla::RemoveConst<T>::Type;
  94 template<bool B, class T, class F>
  95 using conditional_t = typename mozilla::Conditional<B, T, F>::Type;
  96 template<class T>
  97 using add_pointer_t = typename mozilla::AddPointer<T>::Type;
  98 template<bool B, class T = void>
  99 using enable_if_t = typename mozilla::EnableIf<B, T>::Type;
 100
 101 template<class T>
 102 struct is_span_oracle : mozilla::FalseType
 103 {
 104 };
 105
 106 template<class ElementType, size_t Extent>
 107 struct is_span_oracle<mozilla::Span<ElementType, Extent>> : mozilla::TrueType
 108 {
 109 };
 110
 111 template<class T>
 112 struct is_span : public is_span_oracle<remove_cv_t<T>>
 113 {
 114 };
 115
 116 template<class T>
 117 struct is_std_array_oracle : mozilla::FalseType
 118 {
 119 };
 120
 121 template<class ElementType, size_t Extent>
 122 struct is_std_array_oracle<std::array<ElementType, Extent>> : mozilla::TrueType
 123 {
 124 };
 125
 126 template<class T>
 127 struct is_std_array : public is_std_array_oracle<remove_cv_t<T>>
 128 {
 129 };
 130
 131 template<size_t From, size_t To>
 132 struct is_allowed_extent_conversion
 133   : public mozilla::IntegralConstant<bool,
 134                                   From == To ||
 135                                     From == mozilla::dynamic_extent ||
 136                                     To == mozilla::dynamic_extent>
 137 {
 138 };
 139
 140 template<class From, class To>
 141 struct is_allowed_element_type_conversion
 142   : public mozilla::IntegralConstant<bool, mozilla::IsConvertible<From (*)[], To (*)[]>::value>
 143 {
 144 };
 145
 146 template<class Span, bool IsConst>
 147 class span_iterator
 148 {
 149   using element_type_ = typename Span::element_type;
 150
 151 public:
 152   using iterator_category = std::random_access_iterator_tag;
 153   using value_type = remove_const_t<element_type_>;
 154   using difference_type = typename Span::index_type;
 155
 156   using reference = conditional_t<IsConst, const element_type_, element_type_>&;
 157   using pointer = add_pointer_t<reference>;
 158
 159   constexpr span_iterator() : span_iterator(nullptr, 0) {}
 160
 161   constexpr span_iterator(const Span* span,
 162                                              typename Span::index_type index)
 163     : span_(span)
 164     , index_(index)
 165   {
 166     MOZ_RELEASE_ASSERT(span == nullptr ||
 167                        (index_ >= 0 && index <= span_->Length()));
 168   }
 169
 170   friend class span_iterator<Span, true>;
 171   constexpr MOZ_IMPLICIT span_iterator(const span_iterator<Span, false>& other)
 172     : span_iterator(other.span_, other.index_)
 173   {
 174   }
 175
 176   constexpr span_iterator<Span, IsConst>&
 177   operator=(const span_iterator<Span, IsConst>&) = default;
 178
 179   constexpr reference operator*() const
 180   {
 181     MOZ_RELEASE_ASSERT(span_);
 182     return (*span_)[index_];
 183   }
 184
 185   constexpr pointer operator->() const
 186   {
 187     MOZ_RELEASE_ASSERT(span_);
 188     return &((*span_)[index_]);
 189   }
 190
 191   constexpr span_iterator& operator++()
 192   {
 193     MOZ_RELEASE_ASSERT(span_ && index_ >= 0 && index_ < span_->Length());
 194     ++index_;
 195     return *this;
 196   }
 197
 198   constexpr span_iterator operator++(int)
 199   {
 200     auto ret = *this;
 201     ++(*this);
 202     return ret;
 203   }
 204
 205   constexpr span_iterator& operator--()
 206   {
 207     MOZ_RELEASE_ASSERT(span_ && index_ > 0 && index_ <= span_->Length());
 208     --index_;
 209     return *this;
 210   }
 211
 212   constexpr span_iterator operator--(int)
 213   {
 214     auto ret = *this;
 215     --(*this);
 216     return ret;
 217   }
 218
 219   constexpr span_iterator
 220   operator+(difference_type n) const
 221   {
 222     auto ret = *this;
 223     return ret += n;
 224   }
 225
 226   constexpr span_iterator& operator+=(difference_type n)
 227   {
 228     MOZ_RELEASE_ASSERT(span_ && (index_ + n) >= 0 &&
 229                        (index_ + n) <= span_->Length());
 230     index_ += n;
 231     return *this;
 232   }
 233
 234   constexpr span_iterator
 235   operator-(difference_type n) const
 236   {
 237     auto ret = *this;
 238     return ret -= n;
 239   }
 240
 241   constexpr span_iterator& operator-=(difference_type n)
 242
 243   {
 244     return *this += -n;
 245   }
 246
 247   constexpr difference_type
 248   operator-(const span_iterator& rhs) const
 249   {
 250     MOZ_RELEASE_ASSERT(span_ == rhs.span_);
 251     return index_ - rhs.index_;
 252   }
 253
 254   constexpr reference operator[](difference_type n) const
 255   {
 256     return *(*this + n);
 257   }
 258
 259   constexpr friend bool operator==(const span_iterator& lhs,
 260                                    const span_iterator& rhs)
 261   {
 262     return lhs.span_ == rhs.span_ && lhs.index_ == rhs.index_;
 263   }
 264
 265   constexpr friend bool operator!=(const span_iterator& lhs,
 266                                    const span_iterator& rhs)
 267   {
 268     return !(lhs == rhs);
 269   }
 270
 271   constexpr friend bool operator<(const span_iterator& lhs,
 272                                                const span_iterator& rhs)
 273   {
 274     MOZ_RELEASE_ASSERT(lhs.span_ == rhs.span_);
 275     return lhs.index_ < rhs.index_;
 276   }
 277
 278   constexpr friend bool operator<=(const span_iterator& lhs,
 279                                                 const span_iterator& rhs)
 280   {
 281     return !(rhs < lhs);
 282   }
 283
 284   constexpr friend bool operator>(const span_iterator& lhs,
 285                                                const span_iterator& rhs)
 286   {
 287     return rhs < lhs;
 288   }
 289
 290   constexpr friend bool operator>=(const span_iterator& lhs,
 291                                                 const span_iterator& rhs)
 292   {
 293     return !(rhs > lhs);
 294   }
 295
 296   void swap(span_iterator& rhs)
 297   {
 298     std::swap(index_, rhs.index_);
 299     std::swap(span_, rhs.span_);
 300   }
 301
 302 protected:
 303   const Span* span_;
 304   size_t index_;
 305 };
 306
 307 template<class Span, bool IsConst>
 308 inline constexpr span_iterator<Span, IsConst>
 309 operator+(typename span_iterator<Span, IsConst>::difference_type n,
 310           const span_iterator<Span, IsConst>& rhs)
 311 {
 312   return rhs + n;
 313 }
 314
 315 template<size_t Ext>
 316 class extent_type
 317 {
 318 public:
 319   using index_type = size_t;
 320
 321   static_assert(Ext >= 0, "A fixed-size Span must be >= 0 in size.");
 322
 323   constexpr extent_type() {}
 324
 325   template<index_type Other>
 326   constexpr MOZ_IMPLICIT extent_type(extent_type<Other> ext)
 327   {
 328     static_assert(
 329       Other == Ext || Other == dynamic_extent,
 330       "Mismatch between fixed-size extent and size of initializing data.");
 331     MOZ_RELEASE_ASSERT(ext.size() == Ext);
 332   }
 333
 334   constexpr MOZ_IMPLICIT extent_type(index_type length)
 335   {
 336     MOZ_RELEASE_ASSERT(length == Ext);
 337   }
 338
 339   constexpr index_type size() const { return Ext; }
 340 };
 341
 342 template<>
 343 class extent_type<dynamic_extent>
 344 {
 345 public:
 346   using index_type = size_t;
 347
 348   template<index_type Other>
 349   explicit constexpr extent_type(extent_type<Other> ext)
 350     : size_(ext.size())
 351   {
 352   }
 353
 354   explicit constexpr extent_type(index_type length)
 355     : size_(length)
 356   {
 357   }
 358
 359   constexpr index_type size() const { return size_; }
 360
 361 private:
 362   index_type size_;
 363 };
 364 } // namespace span_details
 365
 366 /**
 367  * Span - slices for C++
 368  *
 369  * Span implements Rust's slice concept for C++. It's called "Span" instead of
 370  * "Slice" to follow the naming used in C++ Core Guidelines.
 371  *
 372  * A Span wraps a pointer and a length that identify a non-owning view to a
 373  * contiguous block of memory of objects of the same type. Various types,
 374  * including (pre-decay) C arrays, XPCOM strings, nsTArray, mozilla::Array,
 375  * mozilla::Range and contiguous standard-library containers, auto-convert
 376  * into Spans when attempting to pass them as arguments to methods that take
 377  * Spans. MakeSpan() functions can be used for explicit conversion in other
 378  * contexts. (Span itself autoconverts into mozilla::Range.)
 379  *
 380  * Like Rust's slices, Span provides safety against out-of-bounds access by
 381  * performing run-time bound checks. However, unlike Rust's slices, Span
 382  * cannot provide safety against use-after-free.
 383  *
 384  * (Note: Span is like Rust's slice only conceptually. Due to the lack of
 385  * ABI guarantees, you should still decompose spans/slices to raw pointer
 386  * and length parts when crossing the FFI. The Elements() and data() methods
 387  * are guaranteed to return a non-null pointer even for zero-length spans,
 388  * so the pointer can be used as a raw part of a Rust slice without further
 389  * checks.)
 390  *
 391  * In addition to having constructors and MakeSpan() functions that take
 392  * various well-known types, a Span for an arbitrary type can be constructed
 393  * (via constructor or MakeSpan()) from a pointer and a length or a pointer
 394  * and another pointer pointing just past the last element.
 395  *
 396  * A Span<const char> or Span<const char16_t> can be obtained for const char*
 397  * or const char16_t pointing to a zero-terminated string using the
 398  * MakeStringSpan() function (which treats a nullptr argument equivalently
 399  * to the empty string). Corresponding implicit constructor does not exist
 400  * in order to avoid accidental construction in cases where const char* or
 401  * const char16_t* do not point to a zero-terminated string.
 402  *
 403  * Span has methods that follow the Mozilla naming style and methods that
 404  * don't. The methods that follow the Mozilla naming style are meant to be
 405  * used directly from Mozilla code. The methods that don't are meant for
 406  * integration with C++11 range-based loops and with meta-programming that
 407  * expects the same methods that are found on the standard-library
 408  * containers. For example, to decompose a Span into its parts in Mozilla
 409  * code, use Elements() and Length() (as with nsTArray) instead of data()
 410  * and size() (as with std::vector).
 411  *
 412  * The pointer and length wrapped by a Span cannot be changed after a Span has
 413  * been created. When new values are required, simply create a new Span. Span
 414  * has a method called Subspan() that works analogously to the Substring()
 415  * method of XPCOM strings taking a start index and an optional length. As a
 416  * Mozilla extension (relative to Microsoft's gsl::span that mozilla::Span is
 417  * based on), Span has methods From(start), To(end) and FromTo(start, end)
 418  * that correspond to Rust's &slice[start..], &slice[..end] and
 419  * &slice[start..end], respectively. (That is, the end index is the index of
 420  * the first element not to be included in the new subspan.)
 421  *
 422  * When indicating a Span that's only read from, const goes inside the type
 423  * parameter. Don't put const in front of Span. That is:
 424  * size_t ReadsFromOneSpanAndWritesToAnother(Span<const uint8_t> aReadFrom,
 425  *                                           Span<uint8_t> aWrittenTo);
 426  *
 427  * Any Span<const T> can be viewed as Span<const uint8_t> using the function
 428  * AsBytes(). Any Span<T> can be viewed as Span<uint8_t> using the function
 429  * AsWritableBytes().
 430  */
 431 template<class ElementType, size_t Extent>
 432 class Span
 433 {
 434 public:
 435   // constants and types
 436   using element_type = ElementType;
 437   using index_type = size_t;
 438   using pointer = element_type*;
 439   using reference = element_type&;
 440
 441   using iterator =
 442     span_details::span_iterator<Span<ElementType, Extent>, false>;
 443   using const_iterator =
 444     span_details::span_iterator<Span<ElementType, Extent>, true>;
 445   using reverse_iterator = std::reverse_iterator<iterator>;
 446   using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 447
 448   constexpr static const index_type extent = Extent;
 449
 450   // [Span.cons], Span constructors, copy, assignment, and destructor
 451   // "Dependent" is needed to make "span_details::enable_if_t<(Dependent || Extent == 0 || Extent == mozilla::MaxValue<size_t>::value)>" SFINAE,
 452   // since "span_details::enable_if_t<(Extent == 0 || Extent == mozilla::MaxValue<size_t>::value)>" is ill-formed when Extent is neither of the extreme values.
 453   /**
 454    * Constructor with no args.
 455    */
 456   template<
 457     bool Dependent = false,
 458     class = span_details::enable_if_t<
 459       (Dependent || Extent == 0 || Extent == mozilla::MaxValue<size_t>::value)>>
 460   constexpr Span()
 461     : storage_(nullptr, span_details::extent_type<0>())
 462   {
 463   }
 464
 465   /**
 466    * Constructor for nullptr.
 467    */
 468   constexpr MOZ_IMPLICIT Span(std::nullptr_t) : Span() {}
 469
 470   /**
 471    * Constructor for pointer and length.
 472    */
 473   constexpr Span(pointer aPtr, index_type aLength)
 474     : storage_(aPtr, aLength)
 475   {
 476   }
 477
 478   /**
 479    * Constructor for start pointer and pointer past end.
 480    */
 481   constexpr Span(pointer aStartPtr, pointer aEndPtr)
 482     : storage_(aStartPtr, std::distance(aStartPtr, aEndPtr))
 483   {
 484   }
 485
 486   /**
 487    * Constructor for C array.
 488    */
 489   template<size_t N>
 490   constexpr MOZ_IMPLICIT Span(element_type (&aArr)[N])
 491     : storage_(&aArr[0], span_details::extent_type<N>())
 492   {
 493   }
 494
 495   // Implicit constructors for char* and char16_t* pointers are deleted in order
 496   // to avoid accidental construction in cases where a pointer does not point to
 497   // a zero-terminated string. A Span<const char> or Span<const char16_t> can be
 498   // obtained for const char* or const char16_t pointing to a zero-terminated
 499   // string using the MakeStringSpan() function.
 500   Span(char* aStr) = delete;
 501   Span(const char* aStr) = delete;
 502   Span(char16_t* aStr) = delete;
 503   Span(const char16_t* aStr) = delete;
 504
 505   /**
 506    * Constructor for std::array.
 507    */
 508   template<size_t N,
 509            class ArrayElementType = span_details::remove_const_t<element_type>>
 510   constexpr MOZ_IMPLICIT Span(std::array<ArrayElementType, N>& aArr)
 511     : storage_(&aArr[0], span_details::extent_type<N>())
 512   {
 513   }
 514
 515   /**
 516    * Constructor for const std::array.
 517    */
 518   template<size_t N>
 519   constexpr MOZ_IMPLICIT Span(
 520     const std::array<span_details::remove_const_t<element_type>, N>& aArr)
 521     : storage_(&aArr[0], span_details::extent_type<N>())
 522   {
 523   }
 524
 525   /**
 526    * Constructor for mozilla::Array.
 527    */
 528   template<size_t N,
 529            class ArrayElementType = span_details::remove_const_t<element_type>>
 530   constexpr MOZ_IMPLICIT Span(mozilla::Array<ArrayElementType, N>& aArr)
 531     : storage_(&aArr[0], span_details::extent_type<N>())
 532   {
 533   }
 534
 535   /**
 536    * Constructor for const mozilla::Array.
 537    */
 538   template<size_t N>
 539   constexpr MOZ_IMPLICIT Span(
 540     const mozilla::Array<span_details::remove_const_t<element_type>, N>& aArr)
 541     : storage_(&aArr[0], span_details::extent_type<N>())
 542   {
 543   }
 544
 545   /**
 546    * Constructor for mozilla::UniquePtr holding an array and length.
 547    */
 548   template<class ArrayElementType = std::add_pointer<element_type>>
 549   constexpr Span(const mozilla::UniquePtr<ArrayElementType>& aPtr,
 550                  index_type aLength)
 551     : storage_(aPtr.get(), aLength)
 552   {
 553   }
 554
 555   // NB: the SFINAE here uses .data() as a incomplete/imperfect proxy for the requirement
 556   // on Container to be a contiguous sequence container.
 557   /**
 558    * Constructor for standard-library containers.
 559    */
 560   template<
 561     class Container,
 562     class = span_details::enable_if_t<
 563       !span_details::is_span<Container>::value &&
 564       !span_details::is_std_array<Container>::value &&
 565       mozilla::IsConvertible<typename Container::pointer, pointer>::value &&
 566       mozilla::IsConvertible<typename Container::pointer,
 567                           decltype(mozilla::DeclVal<Container>().data())>::value>>
 568   constexpr MOZ_IMPLICIT Span(Container& cont)
 569     : Span(cont.data(), ReleaseAssertedCast<index_type>(cont.size()))
 570   {
 571   }
 572
 573   /**
 574    * Constructor for standard-library containers (const version).
 575    */
 576   template<
 577     class Container,
 578     class = span_details::enable_if_t<
 579       mozilla::IsConst<element_type>::value &&
 580       !span_details::is_span<Container>::value &&
 581       mozilla::IsConvertible<typename Container::pointer, pointer>::value &&
 582       mozilla::IsConvertible<typename Container::pointer,
 583                           decltype(mozilla::DeclVal<Container>().data())>::value>>
 584   constexpr MOZ_IMPLICIT Span(const Container& cont)
 585     : Span(cont.data(), ReleaseAssertedCast<index_type>(cont.size()))
 586   {
 587   }
 588
 589   /**
 590    * Constructor from other Span.
 591    */
 592   constexpr Span(const Span& other) = default;
 593
 594   /**
 595    * Constructor from other Span.
 596    */
 597   constexpr Span(Span&& other) = default;
 598
 599   /**
 600    * Constructor from other Span with conversion of element type.
 601    */
 602   template<
 603     class OtherElementType,
 604     size_t OtherExtent,
 605     class = span_details::enable_if_t<
 606       span_details::is_allowed_extent_conversion<OtherExtent, Extent>::value &&
 607       span_details::is_allowed_element_type_conversion<OtherElementType,
 608                                                        element_type>::value>>
 609   constexpr MOZ_IMPLICIT Span(const Span<OtherElementType, OtherExtent>& other)
 610     : storage_(other.data(),
 611                span_details::extent_type<OtherExtent>(other.size()))
 612   {
 613   }
 614
 615   /**
 616    * Constructor from other Span with conversion of element type.
 617    */
 618   template<
 619     class OtherElementType,
 620     size_t OtherExtent,
 621     class = span_details::enable_if_t<
 622       span_details::is_allowed_extent_conversion<OtherExtent, Extent>::value &&
 623       span_details::is_allowed_element_type_conversion<OtherElementType,
 624                                                        element_type>::value>>
 625   constexpr MOZ_IMPLICIT Span(Span<OtherElementType, OtherExtent>&& other)
 626     : storage_(other.data(),
 627                span_details::extent_type<OtherExtent>(other.size()))
 628   {
 629   }
 630
 631   ~Span() = default;
 632   constexpr Span& operator=(const Span& other)
 633     = default;
 634
 635   constexpr Span& operator=(Span&& other)
 636     = default;
 637
 638   // [Span.sub], Span subviews
 639   /**
 640    * Subspan with first N elements with compile-time N.
 641    */
 642   template<size_t Count>
 643   constexpr Span<element_type, Count> First() const
 644   {
 645     MOZ_RELEASE_ASSERT(Count <= size());
 646     return { data(), Count };
 647   }
 648
 649   /**
 650    * Subspan with last N elements with compile-time N.
 651    */
 652   template<size_t Count>
 653   constexpr Span<element_type, Count> Last() const
 654   {
 655     const size_t len = size();
 656     MOZ_RELEASE_ASSERT(Count <= len);
 657     return { data() + (len - Count), Count };
 658   }
 659
 660   /**
 661    * Subspan with compile-time start index and length.
 662    */
 663   template<size_t Offset, size_t Count = dynamic_extent>
 664   constexpr Span<element_type, Count> Subspan() const
 665   {
 666     const size_t len = size();
 667     MOZ_RELEASE_ASSERT(Offset <= len &&
 668       (Count == dynamic_extent || (Offset + Count <= len)));
 669     return { data() + Offset,
 670              Count == dynamic_extent ? len - Offset : Count };
 671   }
 672
 673   /**
 674    * Subspan with first N elements with run-time N.
 675    */
 676   constexpr Span<element_type, dynamic_extent> First(
 677     index_type aCount) const
 678   {
 679     MOZ_RELEASE_ASSERT(aCount <= size());
 680     return { data(), aCount };
 681   }
 682
 683   /**
 684    * Subspan with last N elements with run-time N.
 685    */
 686   constexpr Span<element_type, dynamic_extent> Last(
 687     index_type aCount) const
 688   {
 689     const size_t len = size();
 690     MOZ_RELEASE_ASSERT(aCount <= len);
 691     return { data() + (len - aCount), aCount };
 692   }
 693
 694   /**
 695    * Subspan with run-time start index and length.
 696    */
 697   constexpr Span<element_type, dynamic_extent> Subspan(
 698     index_type aStart,
 699     index_type aLength = dynamic_extent) const
 700   {
 701     const size_t len = size();
 702     MOZ_RELEASE_ASSERT(aStart <= len &&
 703                        (aLength == dynamic_extent ||
 704                         (aStart + aLength <= len)));
 705     return { data() + aStart,
 706              aLength == dynamic_extent ? len - aStart : aLength };
 707   }
 708
 709   /**
 710    * Subspan with run-time start index. (Rust's &foo[start..])
 711    */
 712   constexpr Span<element_type, dynamic_extent> From(
 713     index_type aStart) const
 714   {
 715     return Subspan(aStart);
 716   }
 717
 718   /**
 719    * Subspan with run-time exclusive end index. (Rust's &foo[..end])
 720    */
 721   constexpr Span<element_type, dynamic_extent> To(
 722     index_type aEnd) const
 723   {
 724     return Subspan(0, aEnd);
 725   }
 726
 727   /**
 728    * Subspan with run-time start index and exclusive end index.
 729    * (Rust's &foo[start..end])
 730    */
 731   constexpr Span<element_type, dynamic_extent> FromTo(
 732     index_type aStart,
 733     index_type aEnd) const
 734   {
 735     MOZ_RELEASE_ASSERT(aStart <= aEnd);
 736     return Subspan(aStart, aEnd - aStart);
 737   }
 738
 739   // [Span.obs], Span observers
 740   /**
 741    * Number of elements in the span.
 742    */
 743   constexpr index_type Length() const { return size(); }
 744
 745   /**
 746    * Number of elements in the span (standard-libray duck typing version).
 747    */
 748   constexpr index_type size() const { return storage_.size(); }
 749
 750   /**
 751    * Size of the span in bytes.
 752    */
 753   constexpr index_type LengthBytes() const { return size_bytes(); }
 754
 755   /**
 756    * Size of the span in bytes (standard-library naming style version).
 757    */
 758   constexpr index_type size_bytes() const
 759   {
 760     return size() * narrow_cast<index_type>(sizeof(element_type));
 761   }
 762
 763   /**
 764    * Checks if the the length of the span is zero.
 765    */
 766   constexpr bool IsEmpty() const { return empty(); }
 767
 768   /**
 769    * Checks if the the length of the span is zero (standard-libray duck
 770    * typing version).
 771    */
 772   constexpr bool empty() const { return size() == 0; }
 773
 774   // [Span.elem], Span element access
 775   constexpr reference operator[](index_type idx) const
 776   {
 777     MOZ_RELEASE_ASSERT(idx < storage_.size());
 778     return data()[idx];
 779   }
 780
 781   /**
 782    * Access element of span by index (standard-library duck typing version).
 783    */
 784   constexpr reference at(index_type idx) const { return this->operator[](idx); }
 785
 786   constexpr reference operator()(index_type idx) const
 787   {
 788     return this->operator[](idx);
 789   }
 790
 791   /**
 792    * Pointer to the first element of the span. The return value is never
 793    * nullptr, not ever for zero-length spans, so it can be passed as-is
 794    * to std::slice::from_raw_parts() in Rust.
 795    */
 796   constexpr pointer Elements() const { return data(); }
 797
 798   /**
 799    * Pointer to the first element of the span (standard-libray duck typing version).
 800    * The return value is never nullptr, not ever for zero-length spans, so it can
 801    * be passed as-is to std::slice::from_raw_parts() in Rust.
 802    */
 803   constexpr pointer data() const { return storage_.data(); }
 804
 805   // [Span.iter], Span iterator support
 806   iterator begin() const { return { this, 0 }; }
 807   iterator end() const { return { this, Length() }; }
 808
 809   const_iterator cbegin() const { return { this, 0 }; }
 810   const_iterator cend() const { return { this, Length() }; }
 811
 812   reverse_iterator rbegin() const
 813   {
 814     return reverse_iterator{ end() };
 815   }
 816   reverse_iterator rend() const
 817   {
 818     return reverse_iterator{ begin() };
 819   }
 820
 821   const_reverse_iterator crbegin() const
 822   {
 823     return const_reverse_iterator{ cend() };
 824   }
 825   const_reverse_iterator crend() const
 826   {
 827     return const_reverse_iterator{ cbegin() };
 828   }
 829
 830 private:
 831   // this implementation detail class lets us take advantage of the
 832   // empty base class optimization to pay for only storage of a single
 833   // pointer in the case of fixed-size Spans
 834   template<class ExtentType>
 835   class storage_type : public ExtentType
 836   {
 837   public:
 838     template<class OtherExtentType>
 839     constexpr storage_type(pointer elements,
 840                                               OtherExtentType ext)
 841       : ExtentType(ext)
 842       // Replace nullptr with 0x1 for Rust slice compatibility. See
 843       // https://doc.rust-lang.org/std/slice/fn.from_raw_parts.html
 844       , data_(elements ? elements : reinterpret_cast<pointer>(0x1))
 845     {
 846       const size_t extentSize = ExtentType::size();
 847       MOZ_RELEASE_ASSERT(
 848         (!elements && extentSize == 0) ||
 849         (elements && extentSize != mozilla::MaxValue<size_t>::value));
 850     }
 851
 852     constexpr pointer data() const { return data_; }
 853
 854   private:
 855     pointer data_;
 856   };
 857
 858   storage_type<span_details::extent_type<Extent>> storage_;
 859 };
 860
 861 // [Span.comparison], Span comparison operators
 862 template<class ElementType, size_t FirstExtent, size_t SecondExtent>
 863 inline constexpr bool
 864 operator==(const Span<ElementType, FirstExtent>& l,
 865            const Span<ElementType, SecondExtent>& r)
 866 {
 867   return (l.size() == r.size()) && std::equal(l.begin(), l.end(), r.begin());
 868 }
 869
 870 template<class ElementType, size_t Extent>
 871 inline constexpr bool
 872 operator!=(const Span<ElementType, Extent>& l,
 873            const Span<ElementType, Extent>& r)
 874 {
 875   return !(l == r);
 876 }
 877
 878 template<class ElementType, size_t Extent>
 879 inline constexpr bool
 880 operator<(const Span<ElementType, Extent>& l,
 881           const Span<ElementType, Extent>& r)
 882 {
 883   return std::lexicographical_compare(l.begin(), l.end(), r.begin(), r.end());
 884 }
 885
 886 template<class ElementType, size_t Extent>
 887 inline constexpr bool
 888 operator<=(const Span<ElementType, Extent>& l,
 889            const Span<ElementType, Extent>& r)
 890 {
 891   return !(l > r);
 892 }
 893
 894 template<class ElementType, size_t Extent>
 895 inline constexpr bool
 896 operator>(const Span<ElementType, Extent>& l,
 897           const Span<ElementType, Extent>& r)
 898 {
 899   return r < l;
 900 }
 901
 902 template<class ElementType, size_t Extent>
 903 inline constexpr bool
 904 operator>=(const Span<ElementType, Extent>& l,
 905            const Span<ElementType, Extent>& r)
 906 {
 907   return !(l < r);
 908 }
 909
 910 namespace span_details {
 911 // if we only supported compilers with good constexpr support then
 912 // this pair of classes could collapse down to a constexpr function
 913
 914 // we should use a narrow_cast<> to go to size_t, but older compilers may not see it as
 915 // constexpr
 916 // and so will fail compilation of the template
 917 template<class ElementType, size_t Extent>
 918 struct calculate_byte_size
 919   : mozilla::IntegralConstant<size_t,
 920                            static_cast<size_t>(sizeof(ElementType) *
 921                                                static_cast<size_t>(Extent))>
 922 {
 923 };
 924
 925 template<class ElementType>
 926 struct calculate_byte_size<ElementType, dynamic_extent>
 927   : mozilla::IntegralConstant<size_t, dynamic_extent>
 928 {
 929 };
 930 }
 931
 932 // [Span.objectrep], views of object representation
 933 /**
 934  * View span as Span<const uint8_t>.
 935  */
 936 template<class ElementType, size_t Extent>
 937 Span<const uint8_t,
 938      span_details::calculate_byte_size<ElementType, Extent>::value>
 939 AsBytes(Span<ElementType, Extent> s)
 940 {
 941   return { reinterpret_cast<const uint8_t*>(s.data()), s.size_bytes() };
 942 }
 943
 944 /**
 945  * View span as Span<uint8_t>.
 946  */
 947 template<class ElementType,
 948          size_t Extent,
 949          class = span_details::enable_if_t<!mozilla::IsConst<ElementType>::value>>
 950 Span<uint8_t, span_details::calculate_byte_size<ElementType, Extent>::value>
 951 AsWritableBytes(Span<ElementType, Extent> s)
 952 {
 953   return { reinterpret_cast<uint8_t*>(s.data()), s.size_bytes() };
 954 }
 955
 956 //
 957 // MakeSpan() - Utility functions for creating Spans
 958 //
 959 /**
 960  * Create span from pointer and length.
 961  */
 962 template<class ElementType>
 963 Span<ElementType>
 964 MakeSpan(ElementType* aPtr, typename Span<ElementType>::index_type aLength)
 965 {
 966   return Span<ElementType>(aPtr, aLength);
 967 }
 968
 969 /**
 970  * Create span from start pointer and pointer past end.
 971  */
 972 template<class ElementType>
 973 Span<ElementType>
 974 MakeSpan(ElementType* aStartPtr, ElementType* aEndPtr)
 975 {
 976   return Span<ElementType>(aStartPtr, aEndPtr);
 977 }
 978
 979 /**
 980  * Create span from C array.
 981  * MakeSpan() does not permit creating Span objects from string literals (const
 982  * char or char16_t arrays) because the Span length would include the zero
 983  * terminator, which may surprise callers. Use MakeStringSpan() to create a
 984  * Span whose length that excludes the string literal's zero terminator or use
 985  * the MakeSpan() overload that accepts a pointer and length and specify the
 986  * string literal's full length.
 987  */
 988 template<class ElementType, size_t N,
 989          class = span_details::enable_if_t<
 990                    !IsSame<ElementType, const char>::value &&
 991                    !IsSame<ElementType, const char16_t>::value>>
 992 Span<ElementType> MakeSpan(ElementType (&aArr)[N])
 993 {
 994   return Span<ElementType>(aArr, N);
 995 }
 996
 997 /**
 998  * Create span from mozilla::Array.
 999  */
1000 template<class ElementType, size_t N>
1001 Span<ElementType>
1002 MakeSpan(mozilla::Array<ElementType, N>& aArr)
1003 {
1004   return aArr;
1005 }
1006
1007 /**
1008  * Create span from const mozilla::Array.
1009  */
1010 template<class ElementType, size_t N>
1011 Span<const ElementType>
1012 MakeSpan(const mozilla::Array<ElementType, N>& arr)
1013 {
1014   return arr;
1015 }
1016
1017 /**
1018  * Create span from standard-library container.
1019  */
1020 template<class Container>
1021 Span<typename Container::value_type>
1022 MakeSpan(Container& cont)
1023 {
1024   return Span<typename Container::value_type>(cont);
1025 }
1026
1027 /**
1028  * Create span from standard-library container (const version).
1029  */
1030 template<class Container>
1031 Span<const typename Container::value_type>
1032 MakeSpan(const Container& cont)
1033 {
1034   return Span<const typename Container::value_type>(cont);
1035 }
1036
1037 /**
1038  * Create span from smart pointer and length.
1039  */
1040 template<class Ptr>
1041 Span<typename Ptr::element_type>
1042 MakeSpan(Ptr& aPtr, size_t aLength)
1043 {
1044   return Span<typename Ptr::element_type>(aPtr, aLength);
1045 }
1046
1047 /**
1048  * Create span from a zero-terminated C string. nullptr is
1049  * treated as the empty string.
1050  */
1051 inline Span<const char>
1052 MakeStringSpan(const char* aZeroTerminated)
1053 {
1054   if (!aZeroTerminated) {
1055     return Span<const char>();
1056   }
1057   return Span<const char>(aZeroTerminated, std::strlen(aZeroTerminated));
1058 }
1059
1060 /**
1061  * Create span from a zero-terminated UTF-16 C string. nullptr is
1062  * treated as the empty string.
1063  */
1064 inline Span<const char16_t>
1065 MakeStringSpan(const char16_t* aZeroTerminated)
1066 {
1067   if (!aZeroTerminated) {
1068     return Span<const char16_t>();
1069   }
1070   return Span<const char16_t>(aZeroTerminated, span_details::strlen16(aZeroTerminated));
1071 }
1072
1073 } // namespace mozilla
1074
1075 #ifdef _MSC_VER
1076 #if _MSC_VER < 1910
1077 #undef constexpr
1078 #pragma pop_macro("constexpr")
1079
1080 #endif // _MSC_VER < 1910
1081
1082 #pragma warning(pop)
1083 #endif // _MSC_VER
1084
1085 #endif // mozilla_Span_h