1 //! Indexing implementations for `[T]`.
3 use crate::intrinsics::assert_unsafe_precondition;
4 use crate::intrinsics::const_eval_select;
8 #[stable(feature = "rust1", since = "1.0.0")]
9 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
10 impl<T, I> const ops::Index<I> for [T]
12 I: ~const SliceIndex<[T]>,
14 type Output = I::Output;
17 fn index(&self, index: I) -> &I::Output {
22 #[stable(feature = "rust1", since = "1.0.0")]
23 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
24 impl<T, I> const ops::IndexMut<I> for [T]
26 I: ~const SliceIndex<[T]>,
29 fn index_mut(&mut self, index: I) -> &mut I::Output {
34 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
35 #[cfg_attr(feature = "panic_immediate_abort", inline)]
38 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
39 const fn slice_start_index_len_fail(index: usize, len: usize) -> ! {
40 // SAFETY: we are just panicking here
44 slice_start_index_len_fail_ct,
45 slice_start_index_len_fail_rt,
51 fn slice_start_index_len_fail_rt(index: usize, len: usize) -> ! {
52 panic!("range start index {index} out of range for slice of length {len}");
55 const fn slice_start_index_len_fail_ct(_: usize, _: usize) -> ! {
56 panic!("slice start index is out of range for slice");
59 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
60 #[cfg_attr(feature = "panic_immediate_abort", inline)]
63 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
64 const fn slice_end_index_len_fail(index: usize, len: usize) -> ! {
65 // SAFETY: we are just panicking here
67 const_eval_select((index, len), slice_end_index_len_fail_ct, slice_end_index_len_fail_rt)
72 fn slice_end_index_len_fail_rt(index: usize, len: usize) -> ! {
73 panic!("range end index {index} out of range for slice of length {len}");
76 const fn slice_end_index_len_fail_ct(_: usize, _: usize) -> ! {
77 panic!("slice end index is out of range for slice");
80 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
81 #[cfg_attr(feature = "panic_immediate_abort", inline)]
84 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
85 const fn slice_index_order_fail(index: usize, end: usize) -> ! {
86 // SAFETY: we are just panicking here
87 unsafe { const_eval_select((index, end), slice_index_order_fail_ct, slice_index_order_fail_rt) }
91 fn slice_index_order_fail_rt(index: usize, end: usize) -> ! {
92 panic!("slice index starts at {index} but ends at {end}");
95 const fn slice_index_order_fail_ct(_: usize, _: usize) -> ! {
96 panic!("slice index start is larger than end");
99 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
100 #[cfg_attr(feature = "panic_immediate_abort", inline)]
103 const fn slice_start_index_overflow_fail() -> ! {
104 panic!("attempted to index slice from after maximum usize");
107 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
108 #[cfg_attr(feature = "panic_immediate_abort", inline)]
111 const fn slice_end_index_overflow_fail() -> ! {
112 panic!("attempted to index slice up to maximum usize");
115 mod private_slice_index {
117 #[stable(feature = "slice_get_slice", since = "1.28.0")]
120 #[stable(feature = "slice_get_slice", since = "1.28.0")]
121 impl Sealed for usize {}
122 #[stable(feature = "slice_get_slice", since = "1.28.0")]
123 impl Sealed for ops::Range<usize> {}
124 #[stable(feature = "slice_get_slice", since = "1.28.0")]
125 impl Sealed for ops::RangeTo<usize> {}
126 #[stable(feature = "slice_get_slice", since = "1.28.0")]
127 impl Sealed for ops::RangeFrom<usize> {}
128 #[stable(feature = "slice_get_slice", since = "1.28.0")]
129 impl Sealed for ops::RangeFull {}
130 #[stable(feature = "slice_get_slice", since = "1.28.0")]
131 impl Sealed for ops::RangeInclusive<usize> {}
132 #[stable(feature = "slice_get_slice", since = "1.28.0")]
133 impl Sealed for ops::RangeToInclusive<usize> {}
134 #[stable(feature = "slice_index_with_ops_bound_pair", since = "1.53.0")]
135 impl Sealed for (ops::Bound<usize>, ops::Bound<usize>) {}
138 /// A helper trait used for indexing operations.
140 /// Implementations of this trait have to promise that if the argument
141 /// to `get_(mut_)unchecked` is a safe reference, then so is the result.
142 #[stable(feature = "slice_get_slice", since = "1.28.0")]
143 #[rustc_on_unimplemented(
144 on(T = "str", label = "string indices are ranges of `usize`",),
146 all(any(T = "str", T = "&str", T = "std::string::String"), _Self = "{integer}"),
147 note = "you can use `.chars().nth()` or `.bytes().nth()`\n\
148 for more information, see chapter 8 in The Book: \
149 <https://doc.rust-lang.org/book/ch08-02-strings.html#indexing-into-strings>"
151 message = "the type `{T}` cannot be indexed by `{Self}`",
152 label = "slice indices are of type `usize` or ranges of `usize`"
154 pub unsafe trait SliceIndex<T: ?Sized>: private_slice_index::Sealed {
155 /// The output type returned by methods.
156 #[stable(feature = "slice_get_slice", since = "1.28.0")]
159 /// Returns a shared reference to the output at this location, if in
161 #[unstable(feature = "slice_index_methods", issue = "none")]
162 fn get(self, slice: &T) -> Option<&Self::Output>;
164 /// Returns a mutable reference to the output at this location, if in
166 #[unstable(feature = "slice_index_methods", issue = "none")]
167 fn get_mut(self, slice: &mut T) -> Option<&mut Self::Output>;
169 /// Returns a shared reference to the output at this location, without
170 /// performing any bounds checking.
171 /// Calling this method with an out-of-bounds index or a dangling `slice` pointer
172 /// is *[undefined behavior]* even if the resulting reference is not used.
174 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
175 #[unstable(feature = "slice_index_methods", issue = "none")]
176 unsafe fn get_unchecked(self, slice: *const T) -> *const Self::Output;
178 /// Returns a mutable reference to the output at this location, without
179 /// performing any bounds checking.
180 /// Calling this method with an out-of-bounds index or a dangling `slice` pointer
181 /// is *[undefined behavior]* even if the resulting reference is not used.
183 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
184 #[unstable(feature = "slice_index_methods", issue = "none")]
185 unsafe fn get_unchecked_mut(self, slice: *mut T) -> *mut Self::Output;
187 /// Returns a shared reference to the output at this location, panicking
188 /// if out of bounds.
189 #[unstable(feature = "slice_index_methods", issue = "none")]
191 fn index(self, slice: &T) -> &Self::Output;
193 /// Returns a mutable reference to the output at this location, panicking
194 /// if out of bounds.
195 #[unstable(feature = "slice_index_methods", issue = "none")]
197 fn index_mut(self, slice: &mut T) -> &mut Self::Output;
200 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
201 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
202 unsafe impl<T> const SliceIndex<[T]> for usize {
206 fn get(self, slice: &[T]) -> Option<&T> {
207 // SAFETY: `self` is checked to be in bounds.
208 if self < slice.len() { unsafe { Some(&*self.get_unchecked(slice)) } } else { None }
212 fn get_mut(self, slice: &mut [T]) -> Option<&mut T> {
213 // SAFETY: `self` is checked to be in bounds.
214 if self < slice.len() { unsafe { Some(&mut *self.get_unchecked_mut(slice)) } } else { None }
218 unsafe fn get_unchecked(self, slice: *const [T]) -> *const T {
219 // SAFETY: the caller guarantees that `slice` is not dangling, so it
220 // cannot be longer than `isize::MAX`. They also guarantee that
221 // `self` is in bounds of `slice` so `self` cannot overflow an `isize`,
222 // so the call to `add` is safe.
224 assert_unsafe_precondition!(self < slice.len());
225 slice.as_ptr().add(self)
230 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut T {
231 // SAFETY: see comments for `get_unchecked` above.
233 assert_unsafe_precondition!(self < slice.len());
234 slice.as_mut_ptr().add(self)
239 fn index(self, slice: &[T]) -> &T {
240 // N.B., use intrinsic indexing
245 fn index_mut(self, slice: &mut [T]) -> &mut T {
246 // N.B., use intrinsic indexing
251 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
252 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
253 unsafe impl<T> const SliceIndex<[T]> for ops::Range<usize> {
257 fn get(self, slice: &[T]) -> Option<&[T]> {
258 if self.start > self.end || self.end > slice.len() {
261 // SAFETY: `self` is checked to be valid and in bounds above.
262 unsafe { Some(&*self.get_unchecked(slice)) }
267 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
268 if self.start > self.end || self.end > slice.len() {
271 // SAFETY: `self` is checked to be valid and in bounds above.
272 unsafe { Some(&mut *self.get_unchecked_mut(slice)) }
277 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
278 // SAFETY: the caller guarantees that `slice` is not dangling, so it
279 // cannot be longer than `isize::MAX`. They also guarantee that
280 // `self` is in bounds of `slice` so `self` cannot overflow an `isize`,
281 // so the call to `add` is safe.
284 assert_unsafe_precondition!(self.end >= self.start && self.end <= slice.len());
285 ptr::slice_from_raw_parts(slice.as_ptr().add(self.start), self.end - self.start)
290 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
291 // SAFETY: see comments for `get_unchecked` above.
293 assert_unsafe_precondition!(self.end >= self.start && self.end <= slice.len());
294 ptr::slice_from_raw_parts_mut(slice.as_mut_ptr().add(self.start), self.end - self.start)
299 fn index(self, slice: &[T]) -> &[T] {
300 if self.start > self.end {
301 slice_index_order_fail(self.start, self.end);
302 } else if self.end > slice.len() {
303 slice_end_index_len_fail(self.end, slice.len());
305 // SAFETY: `self` is checked to be valid and in bounds above.
306 unsafe { &*self.get_unchecked(slice) }
310 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
311 if self.start > self.end {
312 slice_index_order_fail(self.start, self.end);
313 } else if self.end > slice.len() {
314 slice_end_index_len_fail(self.end, slice.len());
316 // SAFETY: `self` is checked to be valid and in bounds above.
317 unsafe { &mut *self.get_unchecked_mut(slice) }
321 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
322 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
323 unsafe impl<T> const SliceIndex<[T]> for ops::RangeTo<usize> {
327 fn get(self, slice: &[T]) -> Option<&[T]> {
328 (0..self.end).get(slice)
332 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
333 (0..self.end).get_mut(slice)
337 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
338 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
339 unsafe { (0..self.end).get_unchecked(slice) }
343 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
344 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
345 unsafe { (0..self.end).get_unchecked_mut(slice) }
349 fn index(self, slice: &[T]) -> &[T] {
350 (0..self.end).index(slice)
354 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
355 (0..self.end).index_mut(slice)
359 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
360 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
361 unsafe impl<T> const SliceIndex<[T]> for ops::RangeFrom<usize> {
365 fn get(self, slice: &[T]) -> Option<&[T]> {
366 (self.start..slice.len()).get(slice)
370 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
371 (self.start..slice.len()).get_mut(slice)
375 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
376 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
377 unsafe { (self.start..slice.len()).get_unchecked(slice) }
381 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
382 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
383 unsafe { (self.start..slice.len()).get_unchecked_mut(slice) }
387 fn index(self, slice: &[T]) -> &[T] {
388 if self.start > slice.len() {
389 slice_start_index_len_fail(self.start, slice.len());
391 // SAFETY: `self` is checked to be valid and in bounds above.
392 unsafe { &*self.get_unchecked(slice) }
396 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
397 if self.start > slice.len() {
398 slice_start_index_len_fail(self.start, slice.len());
400 // SAFETY: `self` is checked to be valid and in bounds above.
401 unsafe { &mut *self.get_unchecked_mut(slice) }
405 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
406 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
407 unsafe impl<T> const SliceIndex<[T]> for ops::RangeFull {
411 fn get(self, slice: &[T]) -> Option<&[T]> {
416 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
421 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
426 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
431 fn index(self, slice: &[T]) -> &[T] {
436 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
441 #[stable(feature = "inclusive_range", since = "1.26.0")]
442 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
443 unsafe impl<T> const SliceIndex<[T]> for ops::RangeInclusive<usize> {
447 fn get(self, slice: &[T]) -> Option<&[T]> {
448 if *self.end() == usize::MAX { None } else { self.into_slice_range().get(slice) }
452 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
453 if *self.end() == usize::MAX { None } else { self.into_slice_range().get_mut(slice) }
457 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
458 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
459 unsafe { self.into_slice_range().get_unchecked(slice) }
463 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
464 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
465 unsafe { self.into_slice_range().get_unchecked_mut(slice) }
469 fn index(self, slice: &[T]) -> &[T] {
470 if *self.end() == usize::MAX {
471 slice_end_index_overflow_fail();
473 self.into_slice_range().index(slice)
477 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
478 if *self.end() == usize::MAX {
479 slice_end_index_overflow_fail();
481 self.into_slice_range().index_mut(slice)
485 #[stable(feature = "inclusive_range", since = "1.26.0")]
486 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
487 unsafe impl<T> const SliceIndex<[T]> for ops::RangeToInclusive<usize> {
491 fn get(self, slice: &[T]) -> Option<&[T]> {
492 (0..=self.end).get(slice)
496 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
497 (0..=self.end).get_mut(slice)
501 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
502 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
503 unsafe { (0..=self.end).get_unchecked(slice) }
507 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
508 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
509 unsafe { (0..=self.end).get_unchecked_mut(slice) }
513 fn index(self, slice: &[T]) -> &[T] {
514 (0..=self.end).index(slice)
518 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
519 (0..=self.end).index_mut(slice)
523 /// Performs bounds-checking of a range.
525 /// This method is similar to [`Index::index`] for slices, but it returns a
526 /// [`Range`] equivalent to `range`. You can use this method to turn any range
527 /// into `start` and `end` values.
529 /// `bounds` is the range of the slice to use for bounds-checking. It should
530 /// be a [`RangeTo`] range that ends at the length of the slice.
532 /// The returned [`Range`] is safe to pass to [`slice::get_unchecked`] and
533 /// [`slice::get_unchecked_mut`] for slices with the given range.
535 /// [`Range`]: ops::Range
536 /// [`RangeTo`]: ops::RangeTo
537 /// [`slice::get_unchecked`]: slice::get_unchecked
538 /// [`slice::get_unchecked_mut`]: slice::get_unchecked_mut
542 /// Panics if `range` would be out of bounds.
547 /// #![feature(slice_range)]
551 /// let v = [10, 40, 30];
552 /// assert_eq!(1..2, slice::range(1..2, ..v.len()));
553 /// assert_eq!(0..2, slice::range(..2, ..v.len()));
554 /// assert_eq!(1..3, slice::range(1.., ..v.len()));
557 /// Panics when [`Index::index`] would panic:
560 /// #![feature(slice_range)]
564 /// let _ = slice::range(2..1, ..3);
568 /// #![feature(slice_range)]
572 /// let _ = slice::range(1..4, ..3);
576 /// #![feature(slice_range)]
580 /// let _ = slice::range(1..=usize::MAX, ..3);
583 /// [`Index::index`]: ops::Index::index
585 #[unstable(feature = "slice_range", issue = "76393")]
587 pub fn range<R>(range: R, bounds: ops::RangeTo<usize>) -> ops::Range<usize>
589 R: ops::RangeBounds<usize>,
591 let len = bounds.end;
593 let start: ops::Bound<&usize> = range.start_bound();
594 let start = match start {
595 ops::Bound::Included(&start) => start,
596 ops::Bound::Excluded(start) => {
597 start.checked_add(1).unwrap_or_else(|| slice_start_index_overflow_fail())
599 ops::Bound::Unbounded => 0,
602 let end: ops::Bound<&usize> = range.end_bound();
603 let end = match end {
604 ops::Bound::Included(end) => {
605 end.checked_add(1).unwrap_or_else(|| slice_end_index_overflow_fail())
607 ops::Bound::Excluded(&end) => end,
608 ops::Bound::Unbounded => len,
612 slice_index_order_fail(start, end);
615 slice_end_index_len_fail(end, len);
618 ops::Range { start, end }
621 /// Convert pair of `ops::Bound`s into `ops::Range` without performing any bounds checking and (in debug) overflow checking
622 fn into_range_unchecked(
624 (start, end): (ops::Bound<usize>, ops::Bound<usize>),
625 ) -> ops::Range<usize> {
627 let start = match start {
628 Bound::Included(i) => i,
629 Bound::Excluded(i) => i + 1,
630 Bound::Unbounded => 0,
632 let end = match end {
633 Bound::Included(i) => i + 1,
634 Bound::Excluded(i) => i,
635 Bound::Unbounded => len,
640 /// Convert pair of `ops::Bound`s into `ops::Range`.
641 /// Returns `None` on overflowing indices.
644 (start, end): (ops::Bound<usize>, ops::Bound<usize>),
645 ) -> Option<ops::Range<usize>> {
647 let start = match start {
648 Bound::Included(start) => start,
649 Bound::Excluded(start) => start.checked_add(1)?,
650 Bound::Unbounded => 0,
653 let end = match end {
654 Bound::Included(end) => end.checked_add(1)?,
655 Bound::Excluded(end) => end,
656 Bound::Unbounded => len,
659 // Don't bother with checking `start < end` and `end <= len`
660 // since these checks are handled by `Range` impls
665 /// Convert pair of `ops::Bound`s into `ops::Range`.
666 /// Panics on overflowing indices.
669 (start, end): (ops::Bound<usize>, ops::Bound<usize>),
670 ) -> ops::Range<usize> {
672 let start = match start {
673 Bound::Included(start) => start,
674 Bound::Excluded(start) => {
675 start.checked_add(1).unwrap_or_else(|| slice_start_index_overflow_fail())
677 Bound::Unbounded => 0,
680 let end = match end {
681 Bound::Included(end) => {
682 end.checked_add(1).unwrap_or_else(|| slice_end_index_overflow_fail())
684 Bound::Excluded(end) => end,
685 Bound::Unbounded => len,
688 // Don't bother with checking `start < end` and `end <= len`
689 // since these checks are handled by `Range` impls
694 #[stable(feature = "slice_index_with_ops_bound_pair", since = "1.53.0")]
695 unsafe impl<T> SliceIndex<[T]> for (ops::Bound<usize>, ops::Bound<usize>) {
699 fn get(self, slice: &[T]) -> Option<&Self::Output> {
700 into_range(slice.len(), self)?.get(slice)
704 fn get_mut(self, slice: &mut [T]) -> Option<&mut Self::Output> {
705 into_range(slice.len(), self)?.get_mut(slice)
709 unsafe fn get_unchecked(self, slice: *const [T]) -> *const Self::Output {
710 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
711 unsafe { into_range_unchecked(slice.len(), self).get_unchecked(slice) }
715 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut Self::Output {
716 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
717 unsafe { into_range_unchecked(slice.len(), self).get_unchecked_mut(slice) }
721 fn index(self, slice: &[T]) -> &Self::Output {
722 into_slice_range(slice.len(), self).index(slice)
726 fn index_mut(self, slice: &mut [T]) -> &mut Self::Output {
727 into_slice_range(slice.len(), self).index_mut(slice)