Line data Source code
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>(std::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 0 : inline size_t strlen16(const char16_t* aZeroTerminated) {
82 0 : size_t len = 0;
83 0 : while (*(aZeroTerminated++)) {
84 0 : len++;
85 : }
86 0 : 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 0 : constexpr span_iterator(const Span* span,
162 : typename Span::index_type index)
163 : : span_(span)
164 0 : , index_(index)
165 : {
166 0 : MOZ_RELEASE_ASSERT(span == nullptr ||
167 : (index_ >= 0 && index <= span_->Length()));
168 0 : }
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 0 : constexpr reference operator*() const
180 : {
181 0 : MOZ_RELEASE_ASSERT(span_);
182 0 : return (*span_)[index_];
183 : }
184 :
185 : constexpr pointer operator->() const
186 : {
187 : MOZ_RELEASE_ASSERT(span_);
188 : return &((*span_)[index_]);
189 : }
190 :
191 0 : constexpr span_iterator& operator++()
192 : {
193 0 : MOZ_RELEASE_ASSERT(span_ && index_ >= 0 && index_ < span_->Length());
194 0 : ++index_;
195 0 : 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 0 : constexpr friend bool operator==(const span_iterator& lhs,
260 : const span_iterator& rhs)
261 : {
262 0 : return lhs.span_ == rhs.span_ && lhs.index_ == rhs.index_;
263 : }
264 :
265 0 : constexpr friend bool operator!=(const span_iterator& lhs,
266 : const span_iterator& rhs)
267 : {
268 0 : 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 0 : 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 0 : explicit constexpr extent_type(extent_type<Other> ext)
350 0 : : size_(ext.size())
351 : {
352 0 : }
353 :
354 : explicit constexpr extent_type(index_type length)
355 0 : : size_(length)
356 : {
357 : }
358 :
359 0 : 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 0 : constexpr Span()
461 0 : : storage_(nullptr, span_details::extent_type<0>())
462 : {
463 0 : }
464 :
465 : /**
466 : * Constructor for nullptr.
467 : */
468 0 : constexpr MOZ_IMPLICIT Span(std::nullptr_t) : Span() {}
469 :
470 : /**
471 : * Constructor for pointer and length.
472 : */
473 0 : constexpr Span(pointer aPtr, index_type aLength)
474 0 : : storage_(aPtr, aLength)
475 : {
476 0 : }
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 0 : constexpr MOZ_IMPLICIT Span(element_type (&aArr)[N])
491 0 : : storage_(&aArr[0], span_details::extent_type<N>())
492 : {
493 0 : }
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 0 : constexpr MOZ_IMPLICIT Span(Container& cont)
569 0 : : Span(cont.data(), ReleaseAssertedCast<index_type>(cont.size()))
570 : {
571 0 : }
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 0 : constexpr MOZ_IMPLICIT Span(const Container& cont)
585 0 : : Span(cont.data(), ReleaseAssertedCast<index_type>(cont.size()))
586 : {
587 0 : }
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 0 : constexpr MOZ_IMPLICIT Span(const Span<OtherElementType, OtherExtent>& other)
610 : : storage_(other.data(),
611 0 : span_details::extent_type<OtherExtent>(other.size()))
612 : {
613 0 : }
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 0 : constexpr MOZ_IMPLICIT Span(Span<OtherElementType, OtherExtent>&& other)
626 : : storage_(other.data(),
627 0 : span_details::extent_type<OtherExtent>(other.size()))
628 : {
629 0 : }
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 0 : constexpr Span<element_type, dynamic_extent> First(
677 : index_type aCount) const
678 : {
679 0 : MOZ_RELEASE_ASSERT(aCount <= size());
680 0 : 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 0 : constexpr Span<element_type, dynamic_extent> Subspan(
698 : index_type aStart,
699 : index_type aLength = dynamic_extent) const
700 : {
701 0 : const size_t len = size();
702 0 : MOZ_RELEASE_ASSERT(aStart <= len &&
703 : (aLength == dynamic_extent ||
704 : (aStart + aLength <= len)));
705 0 : return { data() + aStart,
706 0 : aLength == dynamic_extent ? len - aStart : aLength };
707 : }
708 :
709 : /**
710 : * Subspan with run-time start index. (Rust's &foo[start..])
711 : */
712 0 : constexpr Span<element_type, dynamic_extent> From(
713 : index_type aStart) const
714 : {
715 0 : return Subspan(aStart);
716 : }
717 :
718 : /**
719 : * Subspan with run-time exclusive end index. (Rust's &foo[..end])
720 : */
721 0 : constexpr Span<element_type, dynamic_extent> To(
722 : index_type aEnd) const
723 : {
724 0 : 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 0 : constexpr Span<element_type, dynamic_extent> FromTo(
732 : index_type aStart,
733 : index_type aEnd) const
734 : {
735 0 : MOZ_RELEASE_ASSERT(aStart <= aEnd);
736 0 : return Subspan(aStart, aEnd - aStart);
737 : }
738 :
739 : // [Span.obs], Span observers
740 : /**
741 : * Number of elements in the span.
742 : */
743 0 : constexpr index_type Length() const { return size(); }
744 :
745 : /**
746 : * Number of elements in the span (standard-libray duck typing version).
747 : */
748 0 : 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 0 : 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 0 : 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 0 : constexpr bool empty() const { return size() == 0; }
773 :
774 : // [Span.elem], Span element access
775 0 : constexpr reference operator[](index_type idx) const
776 : {
777 0 : MOZ_RELEASE_ASSERT(idx < storage_.size());
778 0 : 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 0 : 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 0 : constexpr pointer data() const { return storage_.data(); }
804 :
805 : // [Span.iter], Span iterator support
806 0 : iterator begin() const { return { this, 0 }; }
807 0 : 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 0 : constexpr storage_type(pointer elements,
840 : OtherExtentType ext)
841 : : ExtentType(ext)
842 : // Replace nullptr with aligned bogus pointer for Rust slice
843 : // compatibility. See
844 : // https://doc.rust-lang.org/std/slice/fn.from_raw_parts.html
845 5712 : , data_(elements ? elements : reinterpret_cast<pointer>(alignof(element_type)))
846 : {
847 0 : const size_t extentSize = ExtentType::size();
848 2868 : MOZ_RELEASE_ASSERT(
849 : (!elements && extentSize == 0) ||
850 : (elements && extentSize != mozilla::MaxValue<size_t>::value));
851 5030 : }
852 :
853 : constexpr pointer data() const { return data_; }
854 :
855 : private:
856 : pointer data_;
857 : };
858 :
859 : storage_type<span_details::extent_type<Extent>> storage_;
860 : };
861 :
862 : // [Span.comparison], Span comparison operators
863 : template<class ElementType, size_t FirstExtent, size_t SecondExtent>
864 : inline constexpr bool
865 : operator==(const Span<ElementType, FirstExtent>& l,
866 : const Span<ElementType, SecondExtent>& r)
867 : {
868 : return (l.size() == r.size()) && std::equal(l.begin(), l.end(), r.begin());
869 : }
870 :
871 : template<class ElementType, size_t Extent>
872 : inline constexpr bool
873 : operator!=(const Span<ElementType, Extent>& l,
874 : const Span<ElementType, Extent>& r)
875 : {
876 : return !(l == r);
877 : }
878 :
879 : template<class ElementType, size_t Extent>
880 : inline constexpr bool
881 : operator<(const Span<ElementType, Extent>& l,
882 : const Span<ElementType, Extent>& r)
883 : {
884 : return std::lexicographical_compare(l.begin(), l.end(), r.begin(), r.end());
885 : }
886 :
887 : template<class ElementType, size_t Extent>
888 : inline constexpr bool
889 : operator<=(const Span<ElementType, Extent>& l,
890 : const Span<ElementType, Extent>& r)
891 : {
892 : return !(l > r);
893 : }
894 :
895 : template<class ElementType, size_t Extent>
896 : inline constexpr bool
897 : operator>(const Span<ElementType, Extent>& l,
898 : const Span<ElementType, Extent>& r)
899 : {
900 : return r < l;
901 : }
902 :
903 : template<class ElementType, size_t Extent>
904 : inline constexpr bool
905 : operator>=(const Span<ElementType, Extent>& l,
906 : const Span<ElementType, Extent>& r)
907 : {
908 : return !(l < r);
909 : }
910 :
911 : namespace span_details {
912 : // if we only supported compilers with good constexpr support then
913 : // this pair of classes could collapse down to a constexpr function
914 :
915 : // we should use a narrow_cast<> to go to size_t, but older compilers may not see it as
916 : // constexpr
917 : // and so will fail compilation of the template
918 : template<class ElementType, size_t Extent>
919 : struct calculate_byte_size
920 : : mozilla::IntegralConstant<size_t,
921 : static_cast<size_t>(sizeof(ElementType) *
922 : static_cast<size_t>(Extent))>
923 : {
924 : };
925 :
926 : template<class ElementType>
927 : struct calculate_byte_size<ElementType, dynamic_extent>
928 : : mozilla::IntegralConstant<size_t, dynamic_extent>
929 : {
930 : };
931 : }
932 :
933 : // [Span.objectrep], views of object representation
934 : /**
935 : * View span as Span<const uint8_t>.
936 : */
937 : template<class ElementType, size_t Extent>
938 : Span<const uint8_t,
939 : span_details::calculate_byte_size<ElementType, Extent>::value>
940 159 : AsBytes(Span<ElementType, Extent> s)
941 : {
942 477 : return { reinterpret_cast<const uint8_t*>(s.data()), s.size_bytes() };
943 : }
944 :
945 : /**
946 : * View span as Span<uint8_t>.
947 : */
948 : template<class ElementType,
949 : size_t Extent,
950 : class = span_details::enable_if_t<!mozilla::IsConst<ElementType>::value>>
951 : Span<uint8_t, span_details::calculate_byte_size<ElementType, Extent>::value>
952 0 : AsWritableBytes(Span<ElementType, Extent> s)
953 : {
954 0 : return { reinterpret_cast<uint8_t*>(s.data()), s.size_bytes() };
955 : }
956 :
957 : //
958 : // MakeSpan() - Utility functions for creating Spans
959 : //
960 : /**
961 : * Create span from pointer and length.
962 : */
963 : template<class ElementType>
964 : Span<ElementType>
965 791 : MakeSpan(ElementType* aPtr, typename Span<ElementType>::index_type aLength)
966 : {
967 791 : return Span<ElementType>(aPtr, aLength);
968 : }
969 :
970 : /**
971 : * Create span from start pointer and pointer past end.
972 : */
973 : template<class ElementType>
974 : Span<ElementType>
975 : MakeSpan(ElementType* aStartPtr, ElementType* aEndPtr)
976 : {
977 : return Span<ElementType>(aStartPtr, aEndPtr);
978 : }
979 :
980 : /**
981 : * Create span from C array.
982 : * MakeSpan() does not permit creating Span objects from string literals (const
983 : * char or char16_t arrays) because the Span length would include the zero
984 : * terminator, which may surprise callers. Use MakeStringSpan() to create a
985 : * Span whose length that excludes the string literal's zero terminator or use
986 : * the MakeSpan() overload that accepts a pointer and length and specify the
987 : * string literal's full length.
988 : */
989 : template<class ElementType, size_t N,
990 : class = span_details::enable_if_t<
991 : !IsSame<ElementType, const char>::value &&
992 : !IsSame<ElementType, const char16_t>::value>>
993 0 : Span<ElementType> MakeSpan(ElementType (&aArr)[N])
994 : {
995 0 : return Span<ElementType>(aArr, N);
996 : }
997 :
998 : /**
999 : * Create span from mozilla::Array.
1000 : */
1001 : template<class ElementType, size_t N>
1002 : Span<ElementType>
1003 : MakeSpan(mozilla::Array<ElementType, N>& aArr)
1004 : {
1005 : return aArr;
1006 : }
1007 :
1008 : /**
1009 : * Create span from const mozilla::Array.
1010 : */
1011 : template<class ElementType, size_t N>
1012 : Span<const ElementType>
1013 : MakeSpan(const mozilla::Array<ElementType, N>& arr)
1014 : {
1015 : return arr;
1016 : }
1017 :
1018 : /**
1019 : * Create span from standard-library container.
1020 : */
1021 : template<class Container>
1022 : Span<typename Container::value_type>
1023 : MakeSpan(Container& cont)
1024 : {
1025 : return Span<typename Container::value_type>(cont);
1026 : }
1027 :
1028 : /**
1029 : * Create span from standard-library container (const version).
1030 : */
1031 : template<class Container>
1032 : Span<const typename Container::value_type>
1033 : MakeSpan(const Container& cont)
1034 : {
1035 : return Span<const typename Container::value_type>(cont);
1036 : }
1037 :
1038 : /**
1039 : * Create span from smart pointer and length.
1040 : */
1041 : template<class Ptr>
1042 : Span<typename Ptr::element_type>
1043 : MakeSpan(Ptr& aPtr, size_t aLength)
1044 : {
1045 : return Span<typename Ptr::element_type>(aPtr, aLength);
1046 : }
1047 :
1048 : /**
1049 : * Create span from a zero-terminated C string. nullptr is
1050 : * treated as the empty string.
1051 : */
1052 : inline Span<const char>
1053 1722 : MakeStringSpan(const char* aZeroTerminated)
1054 : {
1055 0 : if (!aZeroTerminated) {
1056 0 : return Span<const char>();
1057 : }
1058 3444 : return Span<const char>(aZeroTerminated, std::strlen(aZeroTerminated));
1059 : }
1060 :
1061 : /**
1062 : * Create span from a zero-terminated UTF-16 C string. nullptr is
1063 : * treated as the empty string.
1064 : */
1065 : inline Span<const char16_t>
1066 0 : MakeStringSpan(const char16_t* aZeroTerminated)
1067 : {
1068 0 : if (!aZeroTerminated) {
1069 0 : return Span<const char16_t>();
1070 : }
1071 : return Span<const char16_t>(aZeroTerminated, span_details::strlen16(aZeroTerminated));
1072 : }
1073 :
1074 : } // namespace mozilla
1075 :
1076 : #ifdef _MSC_VER
1077 : #if _MSC_VER < 1910
1078 : #undef constexpr
1079 : #pragma pop_macro("constexpr")
1080 :
1081 : #endif // _MSC_VER < 1910
1082 :
1083 : #pragma warning(pop)
1084 : #endif // _MSC_VER
1085 :
1086 : #endif // mozilla_Span_h
|
