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,
52 fn slice_start_index_len_fail_rt(index: usize, len: usize) -> ! {
53 panic!("range start index {index} out of range for slice of length {len}");
57 const fn slice_start_index_len_fail_ct(_: usize, _: usize) -> ! {
58 panic!("slice start index is out of range for slice");
61 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
62 #[cfg_attr(feature = "panic_immediate_abort", inline)]
65 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
66 const fn slice_end_index_len_fail(index: usize, len: usize) -> ! {
67 // SAFETY: we are just panicking here
69 const_eval_select((index, len), slice_end_index_len_fail_ct, slice_end_index_len_fail_rt)
75 fn slice_end_index_len_fail_rt(index: usize, len: usize) -> ! {
76 panic!("range end index {index} out of range for slice of length {len}");
80 const fn slice_end_index_len_fail_ct(_: usize, _: usize) -> ! {
81 panic!("slice end index is out of range for slice");
84 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
85 #[cfg_attr(feature = "panic_immediate_abort", inline)]
88 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
89 const fn slice_index_order_fail(index: usize, end: usize) -> ! {
90 // SAFETY: we are just panicking here
91 unsafe { const_eval_select((index, end), slice_index_order_fail_ct, slice_index_order_fail_rt) }
96 fn slice_index_order_fail_rt(index: usize, end: usize) -> ! {
97 panic!("slice index starts at {index} but ends at {end}");
101 const fn slice_index_order_fail_ct(_: usize, _: usize) -> ! {
102 panic!("slice index start is larger than end");
105 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
106 #[cfg_attr(feature = "panic_immediate_abort", inline)]
109 const fn slice_start_index_overflow_fail() -> ! {
110 panic!("attempted to index slice from after maximum usize");
113 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
114 #[cfg_attr(feature = "panic_immediate_abort", inline)]
117 const fn slice_end_index_overflow_fail() -> ! {
118 panic!("attempted to index slice up to maximum usize");
121 mod private_slice_index {
123 #[stable(feature = "slice_get_slice", since = "1.28.0")]
126 #[stable(feature = "slice_get_slice", since = "1.28.0")]
127 impl Sealed for usize {}
128 #[stable(feature = "slice_get_slice", since = "1.28.0")]
129 impl Sealed for ops::Range<usize> {}
130 #[stable(feature = "slice_get_slice", since = "1.28.0")]
131 impl Sealed for ops::RangeTo<usize> {}
132 #[stable(feature = "slice_get_slice", since = "1.28.0")]
133 impl Sealed for ops::RangeFrom<usize> {}
134 #[stable(feature = "slice_get_slice", since = "1.28.0")]
135 impl Sealed for ops::RangeFull {}
136 #[stable(feature = "slice_get_slice", since = "1.28.0")]
137 impl Sealed for ops::RangeInclusive<usize> {}
138 #[stable(feature = "slice_get_slice", since = "1.28.0")]
139 impl Sealed for ops::RangeToInclusive<usize> {}
140 #[stable(feature = "slice_index_with_ops_bound_pair", since = "1.53.0")]
141 impl Sealed for (ops::Bound<usize>, ops::Bound<usize>) {}
144 /// A helper trait used for indexing operations.
146 /// Implementations of this trait have to promise that if the argument
147 /// to `get_unchecked(_mut)` is a safe reference, then so is the result.
148 #[stable(feature = "slice_get_slice", since = "1.28.0")]
149 #[rustc_diagnostic_item = "SliceIndex"]
150 #[rustc_on_unimplemented(
151 on(T = "str", label = "string indices are ranges of `usize`",),
153 all(any(T = "str", T = "&str", T = "std::string::String"), _Self = "{integer}"),
154 note = "you can use `.chars().nth()` or `.bytes().nth()`\n\
155 for more information, see chapter 8 in The Book: \
156 <https://doc.rust-lang.org/book/ch08-02-strings.html#indexing-into-strings>"
158 message = "the type `{T}` cannot be indexed by `{Self}`",
159 label = "slice indices are of type `usize` or ranges of `usize`"
161 pub unsafe trait SliceIndex<T: ?Sized>: private_slice_index::Sealed {
162 /// The output type returned by methods.
163 #[stable(feature = "slice_get_slice", since = "1.28.0")]
166 /// Returns a shared reference to the output at this location, if in
168 #[unstable(feature = "slice_index_methods", issue = "none")]
169 fn get(self, slice: &T) -> Option<&Self::Output>;
171 /// Returns a mutable reference to the output at this location, if in
173 #[unstable(feature = "slice_index_methods", issue = "none")]
174 fn get_mut(self, slice: &mut T) -> Option<&mut Self::Output>;
176 /// Returns a shared reference to the output at this location, without
177 /// performing any bounds checking.
178 /// Calling this method with an out-of-bounds index or a dangling `slice` pointer
179 /// is *[undefined behavior]* even if the resulting reference is not used.
181 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
182 #[unstable(feature = "slice_index_methods", issue = "none")]
183 unsafe fn get_unchecked(self, slice: *const T) -> *const Self::Output;
185 /// Returns a mutable reference to the output at this location, without
186 /// performing any bounds checking.
187 /// Calling this method with an out-of-bounds index or a dangling `slice` pointer
188 /// is *[undefined behavior]* even if the resulting reference is not used.
190 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
191 #[unstable(feature = "slice_index_methods", issue = "none")]
192 unsafe fn get_unchecked_mut(self, slice: *mut T) -> *mut Self::Output;
194 /// Returns a shared reference to the output at this location, panicking
195 /// if out of bounds.
196 #[unstable(feature = "slice_index_methods", issue = "none")]
198 fn index(self, slice: &T) -> &Self::Output;
200 /// Returns a mutable reference to the output at this location, panicking
201 /// if out of bounds.
202 #[unstable(feature = "slice_index_methods", issue = "none")]
204 fn index_mut(self, slice: &mut T) -> &mut Self::Output;
207 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
208 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
209 unsafe impl<T> const SliceIndex<[T]> for usize {
213 fn get(self, slice: &[T]) -> Option<&T> {
214 // SAFETY: `self` is checked to be in bounds.
215 if self < slice.len() { unsafe { Some(&*self.get_unchecked(slice)) } } else { None }
219 fn get_mut(self, slice: &mut [T]) -> Option<&mut T> {
220 // SAFETY: `self` is checked to be in bounds.
221 if self < slice.len() { unsafe { Some(&mut *self.get_unchecked_mut(slice)) } } else { None }
225 unsafe fn get_unchecked(self, slice: *const [T]) -> *const T {
227 // SAFETY: the caller guarantees that `slice` is not dangling, so it
228 // cannot be longer than `isize::MAX`. They also guarantee that
229 // `self` is in bounds of `slice` so `self` cannot overflow an `isize`,
230 // so the call to `add` is safe.
232 assert_unsafe_precondition!([T](this: usize, slice: *const [T]) => this < slice.len());
233 slice.as_ptr().add(self)
238 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut T {
240 // SAFETY: see comments for `get_unchecked` above.
242 assert_unsafe_precondition!([T](this: usize, slice: *mut [T]) => this < slice.len());
243 slice.as_mut_ptr().add(self)
248 fn index(self, slice: &[T]) -> &T {
249 // N.B., use intrinsic indexing
254 fn index_mut(self, slice: &mut [T]) -> &mut T {
255 // N.B., use intrinsic indexing
260 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
261 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
262 unsafe impl<T> const SliceIndex<[T]> for ops::Range<usize> {
266 fn get(self, slice: &[T]) -> Option<&[T]> {
267 if self.start > self.end || self.end > slice.len() {
270 // SAFETY: `self` is checked to be valid and in bounds above.
271 unsafe { Some(&*self.get_unchecked(slice)) }
276 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
277 if self.start > self.end || self.end > slice.len() {
280 // SAFETY: `self` is checked to be valid and in bounds above.
281 unsafe { Some(&mut *self.get_unchecked_mut(slice)) }
286 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
287 let this = ops::Range { start: self.start, end: self.end };
288 // SAFETY: the caller guarantees that `slice` is not dangling, so it
289 // cannot be longer than `isize::MAX`. They also guarantee that
290 // `self` is in bounds of `slice` so `self` cannot overflow an `isize`,
291 // so the call to `add` is safe.
294 assert_unsafe_precondition!([T](this: ops::Range<usize>, slice: *const [T]) =>
295 this.end >= this.start && this.end <= slice.len());
296 ptr::slice_from_raw_parts(slice.as_ptr().add(self.start), self.end - self.start)
301 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
302 let this = ops::Range { start: self.start, end: self.end };
303 // SAFETY: see comments for `get_unchecked` above.
305 assert_unsafe_precondition!([T](this: ops::Range<usize>, slice: *mut [T]) =>
306 this.end >= this.start && this.end <= slice.len());
307 ptr::slice_from_raw_parts_mut(slice.as_mut_ptr().add(self.start), self.end - self.start)
312 fn index(self, slice: &[T]) -> &[T] {
313 if self.start > self.end {
314 slice_index_order_fail(self.start, self.end);
315 } else if self.end > slice.len() {
316 slice_end_index_len_fail(self.end, slice.len());
318 // SAFETY: `self` is checked to be valid and in bounds above.
319 unsafe { &*self.get_unchecked(slice) }
323 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
324 if self.start > self.end {
325 slice_index_order_fail(self.start, self.end);
326 } else if self.end > slice.len() {
327 slice_end_index_len_fail(self.end, slice.len());
329 // SAFETY: `self` is checked to be valid and in bounds above.
330 unsafe { &mut *self.get_unchecked_mut(slice) }
334 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
335 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
336 unsafe impl<T> const SliceIndex<[T]> for ops::RangeTo<usize> {
340 fn get(self, slice: &[T]) -> Option<&[T]> {
341 (0..self.end).get(slice)
345 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
346 (0..self.end).get_mut(slice)
350 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
351 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
352 unsafe { (0..self.end).get_unchecked(slice) }
356 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
357 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
358 unsafe { (0..self.end).get_unchecked_mut(slice) }
362 fn index(self, slice: &[T]) -> &[T] {
363 (0..self.end).index(slice)
367 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
368 (0..self.end).index_mut(slice)
372 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
373 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
374 unsafe impl<T> const SliceIndex<[T]> for ops::RangeFrom<usize> {
378 fn get(self, slice: &[T]) -> Option<&[T]> {
379 (self.start..slice.len()).get(slice)
383 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
384 (self.start..slice.len()).get_mut(slice)
388 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
389 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
390 unsafe { (self.start..slice.len()).get_unchecked(slice) }
394 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
395 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
396 unsafe { (self.start..slice.len()).get_unchecked_mut(slice) }
400 fn index(self, slice: &[T]) -> &[T] {
401 if self.start > slice.len() {
402 slice_start_index_len_fail(self.start, slice.len());
404 // SAFETY: `self` is checked to be valid and in bounds above.
405 unsafe { &*self.get_unchecked(slice) }
409 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
410 if self.start > slice.len() {
411 slice_start_index_len_fail(self.start, slice.len());
413 // SAFETY: `self` is checked to be valid and in bounds above.
414 unsafe { &mut *self.get_unchecked_mut(slice) }
418 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
419 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
420 unsafe impl<T> const SliceIndex<[T]> for ops::RangeFull {
424 fn get(self, slice: &[T]) -> Option<&[T]> {
429 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
434 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
439 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
444 fn index(self, slice: &[T]) -> &[T] {
449 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
454 #[stable(feature = "inclusive_range", since = "1.26.0")]
455 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
456 unsafe impl<T> const SliceIndex<[T]> for ops::RangeInclusive<usize> {
460 fn get(self, slice: &[T]) -> Option<&[T]> {
461 if *self.end() == usize::MAX { None } else { self.into_slice_range().get(slice) }
465 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
466 if *self.end() == usize::MAX { None } else { self.into_slice_range().get_mut(slice) }
470 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
471 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
472 unsafe { self.into_slice_range().get_unchecked(slice) }
476 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
477 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
478 unsafe { self.into_slice_range().get_unchecked_mut(slice) }
482 fn index(self, slice: &[T]) -> &[T] {
483 if *self.end() == usize::MAX {
484 slice_end_index_overflow_fail();
486 self.into_slice_range().index(slice)
490 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
491 if *self.end() == usize::MAX {
492 slice_end_index_overflow_fail();
494 self.into_slice_range().index_mut(slice)
498 #[stable(feature = "inclusive_range", since = "1.26.0")]
499 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
500 unsafe impl<T> const SliceIndex<[T]> for ops::RangeToInclusive<usize> {
504 fn get(self, slice: &[T]) -> Option<&[T]> {
505 (0..=self.end).get(slice)
509 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
510 (0..=self.end).get_mut(slice)
514 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
515 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
516 unsafe { (0..=self.end).get_unchecked(slice) }
520 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
521 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
522 unsafe { (0..=self.end).get_unchecked_mut(slice) }
526 fn index(self, slice: &[T]) -> &[T] {
527 (0..=self.end).index(slice)
531 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
532 (0..=self.end).index_mut(slice)
536 /// Performs bounds-checking of a range.
538 /// This method is similar to [`Index::index`] for slices, but it returns a
539 /// [`Range`] equivalent to `range`. You can use this method to turn any range
540 /// into `start` and `end` values.
542 /// `bounds` is the range of the slice to use for bounds-checking. It should
543 /// be a [`RangeTo`] range that ends at the length of the slice.
545 /// The returned [`Range`] is safe to pass to [`slice::get_unchecked`] and
546 /// [`slice::get_unchecked_mut`] for slices with the given range.
548 /// [`Range`]: ops::Range
549 /// [`RangeTo`]: ops::RangeTo
550 /// [`slice::get_unchecked`]: slice::get_unchecked
551 /// [`slice::get_unchecked_mut`]: slice::get_unchecked_mut
555 /// Panics if `range` would be out of bounds.
560 /// #![feature(slice_range)]
564 /// let v = [10, 40, 30];
565 /// assert_eq!(1..2, slice::range(1..2, ..v.len()));
566 /// assert_eq!(0..2, slice::range(..2, ..v.len()));
567 /// assert_eq!(1..3, slice::range(1.., ..v.len()));
570 /// Panics when [`Index::index`] would panic:
573 /// #![feature(slice_range)]
577 /// let _ = slice::range(2..1, ..3);
581 /// #![feature(slice_range)]
585 /// let _ = slice::range(1..4, ..3);
589 /// #![feature(slice_range)]
593 /// let _ = slice::range(1..=usize::MAX, ..3);
596 /// [`Index::index`]: ops::Index::index
598 #[unstable(feature = "slice_range", issue = "76393")]
600 pub fn range<R>(range: R, bounds: ops::RangeTo<usize>) -> ops::Range<usize>
602 R: ops::RangeBounds<usize>,
604 let len = bounds.end;
606 let start: ops::Bound<&usize> = range.start_bound();
607 let start = match start {
608 ops::Bound::Included(&start) => start,
609 ops::Bound::Excluded(start) => {
610 start.checked_add(1).unwrap_or_else(|| slice_start_index_overflow_fail())
612 ops::Bound::Unbounded => 0,
615 let end: ops::Bound<&usize> = range.end_bound();
616 let end = match end {
617 ops::Bound::Included(end) => {
618 end.checked_add(1).unwrap_or_else(|| slice_end_index_overflow_fail())
620 ops::Bound::Excluded(&end) => end,
621 ops::Bound::Unbounded => len,
625 slice_index_order_fail(start, end);
628 slice_end_index_len_fail(end, len);
631 ops::Range { start, end }
634 /// Convert pair of `ops::Bound`s into `ops::Range` without performing any bounds checking and (in debug) overflow checking
635 fn into_range_unchecked(
637 (start, end): (ops::Bound<usize>, ops::Bound<usize>),
638 ) -> ops::Range<usize> {
640 let start = match start {
641 Bound::Included(i) => i,
642 Bound::Excluded(i) => i + 1,
643 Bound::Unbounded => 0,
645 let end = match end {
646 Bound::Included(i) => i + 1,
647 Bound::Excluded(i) => i,
648 Bound::Unbounded => len,
653 /// Convert pair of `ops::Bound`s into `ops::Range`.
654 /// Returns `None` on overflowing indices.
657 (start, end): (ops::Bound<usize>, ops::Bound<usize>),
658 ) -> Option<ops::Range<usize>> {
660 let start = match start {
661 Bound::Included(start) => start,
662 Bound::Excluded(start) => start.checked_add(1)?,
663 Bound::Unbounded => 0,
666 let end = match end {
667 Bound::Included(end) => end.checked_add(1)?,
668 Bound::Excluded(end) => end,
669 Bound::Unbounded => len,
672 // Don't bother with checking `start < end` and `end <= len`
673 // since these checks are handled by `Range` impls
678 /// Convert pair of `ops::Bound`s into `ops::Range`.
679 /// Panics on overflowing indices.
682 (start, end): (ops::Bound<usize>, ops::Bound<usize>),
683 ) -> ops::Range<usize> {
685 let start = match start {
686 Bound::Included(start) => start,
687 Bound::Excluded(start) => {
688 start.checked_add(1).unwrap_or_else(|| slice_start_index_overflow_fail())
690 Bound::Unbounded => 0,
693 let end = match end {
694 Bound::Included(end) => {
695 end.checked_add(1).unwrap_or_else(|| slice_end_index_overflow_fail())
697 Bound::Excluded(end) => end,
698 Bound::Unbounded => len,
701 // Don't bother with checking `start < end` and `end <= len`
702 // since these checks are handled by `Range` impls
707 #[stable(feature = "slice_index_with_ops_bound_pair", since = "1.53.0")]
708 unsafe impl<T> SliceIndex<[T]> for (ops::Bound<usize>, ops::Bound<usize>) {
712 fn get(self, slice: &[T]) -> Option<&Self::Output> {
713 into_range(slice.len(), self)?.get(slice)
717 fn get_mut(self, slice: &mut [T]) -> Option<&mut Self::Output> {
718 into_range(slice.len(), self)?.get_mut(slice)
722 unsafe fn get_unchecked(self, slice: *const [T]) -> *const Self::Output {
723 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
724 unsafe { into_range_unchecked(slice.len(), self).get_unchecked(slice) }
728 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut Self::Output {
729 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
730 unsafe { into_range_unchecked(slice.len(), self).get_unchecked_mut(slice) }
734 fn index(self, slice: &[T]) -> &Self::Output {
735 into_slice_range(slice.len(), self).index(slice)
739 fn index_mut(self, slice: &mut [T]) -> &mut Self::Output {
740 into_slice_range(slice.len(), self).index_mut(slice)