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