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_diagnostic_item = "SliceIndex"]
144 #[rustc_on_unimplemented(
145 on(T = "str", label = "string indices are ranges of `usize`",),
147 all(any(T = "str", T = "&str", T = "std::string::String"), _Self = "{integer}"),
148 note = "you can use `.chars().nth()` or `.bytes().nth()`\n\
149 for more information, see chapter 8 in The Book: \
150 <https://doc.rust-lang.org/book/ch08-02-strings.html#indexing-into-strings>"
152 message = "the type `{T}` cannot be indexed by `{Self}`",
153 label = "slice indices are of type `usize` or ranges of `usize`"
155 pub unsafe trait SliceIndex<T: ?Sized>: private_slice_index::Sealed {
156 /// The output type returned by methods.
157 #[stable(feature = "slice_get_slice", since = "1.28.0")]
160 /// Returns a shared reference to the output at this location, if in
162 #[unstable(feature = "slice_index_methods", issue = "none")]
163 fn get(self, slice: &T) -> Option<&Self::Output>;
165 /// Returns a mutable reference to the output at this location, if in
167 #[unstable(feature = "slice_index_methods", issue = "none")]
168 fn get_mut(self, slice: &mut T) -> Option<&mut Self::Output>;
170 /// Returns a shared reference to the output at this location, without
171 /// performing any bounds checking.
172 /// Calling this method with an out-of-bounds index or a dangling `slice` pointer
173 /// is *[undefined behavior]* even if the resulting reference is not used.
175 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
176 #[unstable(feature = "slice_index_methods", issue = "none")]
177 unsafe fn get_unchecked(self, slice: *const T) -> *const Self::Output;
179 /// Returns a mutable reference to the output at this location, without
180 /// performing any bounds checking.
181 /// Calling this method with an out-of-bounds index or a dangling `slice` pointer
182 /// is *[undefined behavior]* even if the resulting reference is not used.
184 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
185 #[unstable(feature = "slice_index_methods", issue = "none")]
186 unsafe fn get_unchecked_mut(self, slice: *mut T) -> *mut Self::Output;
188 /// Returns a shared reference to the output at this location, panicking
189 /// if out of bounds.
190 #[unstable(feature = "slice_index_methods", issue = "none")]
192 fn index(self, slice: &T) -> &Self::Output;
194 /// Returns a mutable reference to the output at this location, panicking
195 /// if out of bounds.
196 #[unstable(feature = "slice_index_methods", issue = "none")]
198 fn index_mut(self, slice: &mut T) -> &mut Self::Output;
201 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
202 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
203 unsafe impl<T> const SliceIndex<[T]> for usize {
207 fn get(self, slice: &[T]) -> Option<&T> {
208 // SAFETY: `self` is checked to be in bounds.
209 if self < slice.len() { unsafe { Some(&*self.get_unchecked(slice)) } } else { None }
213 fn get_mut(self, slice: &mut [T]) -> Option<&mut T> {
214 // SAFETY: `self` is checked to be in bounds.
215 if self < slice.len() { unsafe { Some(&mut *self.get_unchecked_mut(slice)) } } else { None }
219 unsafe fn get_unchecked(self, slice: *const [T]) -> *const T {
220 // SAFETY: the caller guarantees that `slice` is not dangling, so it
221 // cannot be longer than `isize::MAX`. They also guarantee that
222 // `self` is in bounds of `slice` so `self` cannot overflow an `isize`,
223 // so the call to `add` is safe.
225 assert_unsafe_precondition!(self < slice.len());
226 slice.as_ptr().add(self)
231 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut T {
232 // SAFETY: see comments for `get_unchecked` above.
234 assert_unsafe_precondition!(self < slice.len());
235 slice.as_mut_ptr().add(self)
240 fn index(self, slice: &[T]) -> &T {
241 // N.B., use intrinsic indexing
246 fn index_mut(self, slice: &mut [T]) -> &mut T {
247 // N.B., use intrinsic indexing
252 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
253 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
254 unsafe impl<T> const SliceIndex<[T]> for ops::Range<usize> {
258 fn get(self, slice: &[T]) -> Option<&[T]> {
259 if self.start > self.end || self.end > slice.len() {
262 // SAFETY: `self` is checked to be valid and in bounds above.
263 unsafe { Some(&*self.get_unchecked(slice)) }
268 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
269 if self.start > self.end || self.end > slice.len() {
272 // SAFETY: `self` is checked to be valid and in bounds above.
273 unsafe { Some(&mut *self.get_unchecked_mut(slice)) }
278 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
279 // SAFETY: the caller guarantees that `slice` is not dangling, so it
280 // cannot be longer than `isize::MAX`. They also guarantee that
281 // `self` is in bounds of `slice` so `self` cannot overflow an `isize`,
282 // so the call to `add` is safe.
285 assert_unsafe_precondition!(self.end >= self.start && self.end <= slice.len());
286 ptr::slice_from_raw_parts(slice.as_ptr().add(self.start), self.end - self.start)
291 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
292 // SAFETY: see comments for `get_unchecked` above.
294 assert_unsafe_precondition!(self.end >= self.start && self.end <= slice.len());
295 ptr::slice_from_raw_parts_mut(slice.as_mut_ptr().add(self.start), self.end - self.start)
300 fn index(self, slice: &[T]) -> &[T] {
301 if self.start > self.end {
302 slice_index_order_fail(self.start, self.end);
303 } else if self.end > slice.len() {
304 slice_end_index_len_fail(self.end, slice.len());
306 // SAFETY: `self` is checked to be valid and in bounds above.
307 unsafe { &*self.get_unchecked(slice) }
311 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
312 if self.start > self.end {
313 slice_index_order_fail(self.start, self.end);
314 } else if self.end > slice.len() {
315 slice_end_index_len_fail(self.end, slice.len());
317 // SAFETY: `self` is checked to be valid and in bounds above.
318 unsafe { &mut *self.get_unchecked_mut(slice) }
322 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
323 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
324 unsafe impl<T> const SliceIndex<[T]> for ops::RangeTo<usize> {
328 fn get(self, slice: &[T]) -> Option<&[T]> {
329 (0..self.end).get(slice)
333 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
334 (0..self.end).get_mut(slice)
338 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
339 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
340 unsafe { (0..self.end).get_unchecked(slice) }
344 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
345 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
346 unsafe { (0..self.end).get_unchecked_mut(slice) }
350 fn index(self, slice: &[T]) -> &[T] {
351 (0..self.end).index(slice)
355 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
356 (0..self.end).index_mut(slice)
360 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
361 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
362 unsafe impl<T> const SliceIndex<[T]> for ops::RangeFrom<usize> {
366 fn get(self, slice: &[T]) -> Option<&[T]> {
367 (self.start..slice.len()).get(slice)
371 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
372 (self.start..slice.len()).get_mut(slice)
376 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
377 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
378 unsafe { (self.start..slice.len()).get_unchecked(slice) }
382 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
383 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
384 unsafe { (self.start..slice.len()).get_unchecked_mut(slice) }
388 fn index(self, slice: &[T]) -> &[T] {
389 if self.start > slice.len() {
390 slice_start_index_len_fail(self.start, slice.len());
392 // SAFETY: `self` is checked to be valid and in bounds above.
393 unsafe { &*self.get_unchecked(slice) }
397 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
398 if self.start > slice.len() {
399 slice_start_index_len_fail(self.start, slice.len());
401 // SAFETY: `self` is checked to be valid and in bounds above.
402 unsafe { &mut *self.get_unchecked_mut(slice) }
406 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
407 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
408 unsafe impl<T> const SliceIndex<[T]> for ops::RangeFull {
412 fn get(self, slice: &[T]) -> Option<&[T]> {
417 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
422 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
427 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
432 fn index(self, slice: &[T]) -> &[T] {
437 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
442 #[stable(feature = "inclusive_range", since = "1.26.0")]
443 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
444 unsafe impl<T> const SliceIndex<[T]> for ops::RangeInclusive<usize> {
448 fn get(self, slice: &[T]) -> Option<&[T]> {
449 if *self.end() == usize::MAX { None } else { self.into_slice_range().get(slice) }
453 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
454 if *self.end() == usize::MAX { None } else { self.into_slice_range().get_mut(slice) }
458 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
459 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
460 unsafe { self.into_slice_range().get_unchecked(slice) }
464 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
465 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
466 unsafe { self.into_slice_range().get_unchecked_mut(slice) }
470 fn index(self, slice: &[T]) -> &[T] {
471 if *self.end() == usize::MAX {
472 slice_end_index_overflow_fail();
474 self.into_slice_range().index(slice)
478 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
479 if *self.end() == usize::MAX {
480 slice_end_index_overflow_fail();
482 self.into_slice_range().index_mut(slice)
486 #[stable(feature = "inclusive_range", since = "1.26.0")]
487 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
488 unsafe impl<T> const SliceIndex<[T]> for ops::RangeToInclusive<usize> {
492 fn get(self, slice: &[T]) -> Option<&[T]> {
493 (0..=self.end).get(slice)
497 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
498 (0..=self.end).get_mut(slice)
502 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
503 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
504 unsafe { (0..=self.end).get_unchecked(slice) }
508 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
509 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
510 unsafe { (0..=self.end).get_unchecked_mut(slice) }
514 fn index(self, slice: &[T]) -> &[T] {
515 (0..=self.end).index(slice)
519 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
520 (0..=self.end).index_mut(slice)
524 /// Performs bounds-checking of a range.
526 /// This method is similar to [`Index::index`] for slices, but it returns a
527 /// [`Range`] equivalent to `range`. You can use this method to turn any range
528 /// into `start` and `end` values.
530 /// `bounds` is the range of the slice to use for bounds-checking. It should
531 /// be a [`RangeTo`] range that ends at the length of the slice.
533 /// The returned [`Range`] is safe to pass to [`slice::get_unchecked`] and
534 /// [`slice::get_unchecked_mut`] for slices with the given range.
536 /// [`Range`]: ops::Range
537 /// [`RangeTo`]: ops::RangeTo
538 /// [`slice::get_unchecked`]: slice::get_unchecked
539 /// [`slice::get_unchecked_mut`]: slice::get_unchecked_mut
543 /// Panics if `range` would be out of bounds.
548 /// #![feature(slice_range)]
552 /// let v = [10, 40, 30];
553 /// assert_eq!(1..2, slice::range(1..2, ..v.len()));
554 /// assert_eq!(0..2, slice::range(..2, ..v.len()));
555 /// assert_eq!(1..3, slice::range(1.., ..v.len()));
558 /// Panics when [`Index::index`] would panic:
561 /// #![feature(slice_range)]
565 /// let _ = slice::range(2..1, ..3);
569 /// #![feature(slice_range)]
573 /// let _ = slice::range(1..4, ..3);
577 /// #![feature(slice_range)]
581 /// let _ = slice::range(1..=usize::MAX, ..3);
584 /// [`Index::index`]: ops::Index::index
586 #[unstable(feature = "slice_range", issue = "76393")]
588 pub fn range<R>(range: R, bounds: ops::RangeTo<usize>) -> ops::Range<usize>
590 R: ops::RangeBounds<usize>,
592 let len = bounds.end;
594 let start: ops::Bound<&usize> = range.start_bound();
595 let start = match start {
596 ops::Bound::Included(&start) => start,
597 ops::Bound::Excluded(start) => {
598 start.checked_add(1).unwrap_or_else(|| slice_start_index_overflow_fail())
600 ops::Bound::Unbounded => 0,
603 let end: ops::Bound<&usize> = range.end_bound();
604 let end = match end {
605 ops::Bound::Included(end) => {
606 end.checked_add(1).unwrap_or_else(|| slice_end_index_overflow_fail())
608 ops::Bound::Excluded(&end) => end,
609 ops::Bound::Unbounded => len,
613 slice_index_order_fail(start, end);
616 slice_end_index_len_fail(end, len);
619 ops::Range { start, end }
622 /// Convert pair of `ops::Bound`s into `ops::Range` without performing any bounds checking and (in debug) overflow checking
623 fn into_range_unchecked(
625 (start, end): (ops::Bound<usize>, ops::Bound<usize>),
626 ) -> ops::Range<usize> {
628 let start = match start {
629 Bound::Included(i) => i,
630 Bound::Excluded(i) => i + 1,
631 Bound::Unbounded => 0,
633 let end = match end {
634 Bound::Included(i) => i + 1,
635 Bound::Excluded(i) => i,
636 Bound::Unbounded => len,
641 /// Convert pair of `ops::Bound`s into `ops::Range`.
642 /// Returns `None` on overflowing indices.
645 (start, end): (ops::Bound<usize>, ops::Bound<usize>),
646 ) -> Option<ops::Range<usize>> {
648 let start = match start {
649 Bound::Included(start) => start,
650 Bound::Excluded(start) => start.checked_add(1)?,
651 Bound::Unbounded => 0,
654 let end = match end {
655 Bound::Included(end) => end.checked_add(1)?,
656 Bound::Excluded(end) => end,
657 Bound::Unbounded => len,
660 // Don't bother with checking `start < end` and `end <= len`
661 // since these checks are handled by `Range` impls
666 /// Convert pair of `ops::Bound`s into `ops::Range`.
667 /// Panics on overflowing indices.
670 (start, end): (ops::Bound<usize>, ops::Bound<usize>),
671 ) -> ops::Range<usize> {
673 let start = match start {
674 Bound::Included(start) => start,
675 Bound::Excluded(start) => {
676 start.checked_add(1).unwrap_or_else(|| slice_start_index_overflow_fail())
678 Bound::Unbounded => 0,
681 let end = match end {
682 Bound::Included(end) => {
683 end.checked_add(1).unwrap_or_else(|| slice_end_index_overflow_fail())
685 Bound::Excluded(end) => end,
686 Bound::Unbounded => len,
689 // Don't bother with checking `start < end` and `end <= len`
690 // since these checks are handled by `Range` impls
695 #[stable(feature = "slice_index_with_ops_bound_pair", since = "1.53.0")]
696 unsafe impl<T> SliceIndex<[T]> for (ops::Bound<usize>, ops::Bound<usize>) {
700 fn get(self, slice: &[T]) -> Option<&Self::Output> {
701 into_range(slice.len(), self)?.get(slice)
705 fn get_mut(self, slice: &mut [T]) -> Option<&mut Self::Output> {
706 into_range(slice.len(), self)?.get_mut(slice)
710 unsafe fn get_unchecked(self, slice: *const [T]) -> *const Self::Output {
711 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
712 unsafe { into_range_unchecked(slice.len(), self).get_unchecked(slice) }
716 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut Self::Output {
717 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
718 unsafe { into_range_unchecked(slice.len(), self).get_unchecked_mut(slice) }
722 fn index(self, slice: &[T]) -> &Self::Output {
723 into_slice_range(slice.len(), self).index(slice)
727 fn index_mut(self, slice: &mut [T]) -> &mut Self::Output {
728 into_slice_range(slice.len(), self).index_mut(slice)