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