1 //! Indexing implementations for `[T]`.
3 use crate::intrinsics::const_eval_select;
7 #[stable(feature = "rust1", since = "1.0.0")]
8 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
9 impl<T, I> const ops::Index<I> for [T]
11 I: ~const SliceIndex<[T]>,
13 type Output = I::Output;
16 fn index(&self, index: I) -> &I::Output {
21 #[stable(feature = "rust1", since = "1.0.0")]
22 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
23 impl<T, I> const ops::IndexMut<I> for [T]
25 I: ~const SliceIndex<[T]>,
28 fn index_mut(&mut self, index: I) -> &mut I::Output {
33 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
34 #[cfg_attr(feature = "panic_immediate_abort", inline)]
37 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
38 const fn slice_start_index_len_fail(index: usize, len: usize) -> ! {
39 // SAFETY: we are just panicking here
43 slice_start_index_len_fail_ct,
44 slice_start_index_len_fail_rt,
50 fn slice_start_index_len_fail_rt(index: usize, len: usize) -> ! {
51 panic!("range start index {index} out of range for slice of length {len}");
54 const fn slice_start_index_len_fail_ct(_: usize, _: usize) -> ! {
55 panic!("slice start index is out of range for slice");
58 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
59 #[cfg_attr(feature = "panic_immediate_abort", inline)]
62 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
63 const fn slice_end_index_len_fail(index: usize, len: usize) -> ! {
64 // SAFETY: we are just panicking here
66 const_eval_select((index, len), slice_end_index_len_fail_ct, slice_end_index_len_fail_rt)
71 fn slice_end_index_len_fail_rt(index: usize, len: usize) -> ! {
72 panic!("range end index {index} out of range for slice of length {len}");
75 const fn slice_end_index_len_fail_ct(_: usize, _: usize) -> ! {
76 panic!("slice end index is out of range for slice");
79 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
80 #[cfg_attr(feature = "panic_immediate_abort", inline)]
83 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
84 const fn slice_index_order_fail(index: usize, end: usize) -> ! {
85 // SAFETY: we are just panicking here
86 unsafe { const_eval_select((index, end), slice_index_order_fail_ct, slice_index_order_fail_rt) }
90 fn slice_index_order_fail_rt(index: usize, end: usize) -> ! {
91 panic!("slice index starts at {index} but ends at {end}");
94 const fn slice_index_order_fail_ct(_: usize, _: usize) -> ! {
95 panic!("slice index start is larger than end");
98 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
99 #[cfg_attr(feature = "panic_immediate_abort", inline)]
102 const fn slice_start_index_overflow_fail() -> ! {
103 panic!("attempted to index slice from after maximum usize");
106 #[cfg_attr(not(feature = "panic_immediate_abort"), inline(never))]
107 #[cfg_attr(feature = "panic_immediate_abort", inline)]
110 const fn slice_end_index_overflow_fail() -> ! {
111 panic!("attempted to index slice up to maximum usize");
114 mod private_slice_index {
116 #[stable(feature = "slice_get_slice", since = "1.28.0")]
119 #[stable(feature = "slice_get_slice", since = "1.28.0")]
120 impl Sealed for usize {}
121 #[stable(feature = "slice_get_slice", since = "1.28.0")]
122 impl Sealed for ops::Range<usize> {}
123 #[stable(feature = "slice_get_slice", since = "1.28.0")]
124 impl Sealed for ops::RangeTo<usize> {}
125 #[stable(feature = "slice_get_slice", since = "1.28.0")]
126 impl Sealed for ops::RangeFrom<usize> {}
127 #[stable(feature = "slice_get_slice", since = "1.28.0")]
128 impl Sealed for ops::RangeFull {}
129 #[stable(feature = "slice_get_slice", since = "1.28.0")]
130 impl Sealed for ops::RangeInclusive<usize> {}
131 #[stable(feature = "slice_get_slice", since = "1.28.0")]
132 impl Sealed for ops::RangeToInclusive<usize> {}
133 #[stable(feature = "slice_index_with_ops_bound_pair", since = "1.53.0")]
134 impl Sealed for (ops::Bound<usize>, ops::Bound<usize>) {}
137 /// A helper trait used for indexing operations.
139 /// Implementations of this trait have to promise that if the argument
140 /// to `get_(mut_)unchecked` is a safe reference, then so is the result.
141 #[stable(feature = "slice_get_slice", since = "1.28.0")]
142 #[rustc_on_unimplemented(
143 on(T = "str", label = "string indices are ranges of `usize`",),
145 all(any(T = "str", T = "&str", T = "std::string::String"), _Self = "{integer}"),
146 note = "you can use `.chars().nth()` or `.bytes().nth()`\n\
147 for more information, see chapter 8 in The Book: \
148 <https://doc.rust-lang.org/book/ch08-02-strings.html#indexing-into-strings>"
150 message = "the type `{T}` cannot be indexed by `{Self}`",
151 label = "slice indices are of type `usize` or ranges of `usize`"
153 pub unsafe trait SliceIndex<T: ?Sized>: private_slice_index::Sealed {
154 /// The output type returned by methods.
155 #[stable(feature = "slice_get_slice", since = "1.28.0")]
158 /// Returns a shared reference to the output at this location, if in
160 #[unstable(feature = "slice_index_methods", issue = "none")]
161 fn get(self, slice: &T) -> Option<&Self::Output>;
163 /// Returns a mutable reference to the output at this location, if in
165 #[unstable(feature = "slice_index_methods", issue = "none")]
166 fn get_mut(self, slice: &mut T) -> Option<&mut Self::Output>;
168 /// Returns a shared reference to the output at this location, without
169 /// performing any bounds checking.
170 /// Calling this method with an out-of-bounds index or a dangling `slice` pointer
171 /// is *[undefined behavior]* even if the resulting reference is not used.
173 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
174 #[unstable(feature = "slice_index_methods", issue = "none")]
175 unsafe fn get_unchecked(self, slice: *const T) -> *const Self::Output;
177 /// Returns a mutable reference to the output at this location, without
178 /// performing any bounds checking.
179 /// Calling this method with an out-of-bounds index or a dangling `slice` pointer
180 /// is *[undefined behavior]* even if the resulting reference is not used.
182 /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
183 #[unstable(feature = "slice_index_methods", issue = "none")]
184 unsafe fn get_unchecked_mut(self, slice: *mut T) -> *mut Self::Output;
186 /// Returns a shared reference to the output at this location, panicking
187 /// if out of bounds.
188 #[unstable(feature = "slice_index_methods", issue = "none")]
190 fn index(self, slice: &T) -> &Self::Output;
192 /// Returns a mutable reference to the output at this location, panicking
193 /// if out of bounds.
194 #[unstable(feature = "slice_index_methods", issue = "none")]
196 fn index_mut(self, slice: &mut T) -> &mut Self::Output;
199 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
200 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
201 unsafe impl<T> const SliceIndex<[T]> for usize {
205 fn get(self, slice: &[T]) -> Option<&T> {
206 // SAFETY: `self` is checked to be in bounds.
207 if self < slice.len() { unsafe { Some(&*self.get_unchecked(slice)) } } else { None }
211 fn get_mut(self, slice: &mut [T]) -> Option<&mut T> {
212 // SAFETY: `self` is checked to be in bounds.
213 if self < slice.len() { unsafe { Some(&mut *self.get_unchecked_mut(slice)) } } else { None }
217 unsafe fn get_unchecked(self, slice: *const [T]) -> *const T {
218 // SAFETY: the caller guarantees that `slice` is not dangling, so it
219 // cannot be longer than `isize::MAX`. They also guarantee that
220 // `self` is in bounds of `slice` so `self` cannot overflow an `isize`,
221 // so the call to `add` is safe.
222 unsafe { slice.as_ptr().add(self) }
226 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut T {
227 // SAFETY: see comments for `get_unchecked` above.
228 unsafe { slice.as_mut_ptr().add(self) }
232 fn index(self, slice: &[T]) -> &T {
233 // N.B., use intrinsic indexing
238 fn index_mut(self, slice: &mut [T]) -> &mut T {
239 // N.B., use intrinsic indexing
244 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
245 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
246 unsafe impl<T> const SliceIndex<[T]> for ops::Range<usize> {
250 fn get(self, slice: &[T]) -> Option<&[T]> {
251 if self.start > self.end || self.end > slice.len() {
254 // SAFETY: `self` is checked to be valid and in bounds above.
255 unsafe { Some(&*self.get_unchecked(slice)) }
260 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
261 if self.start > self.end || self.end > slice.len() {
264 // SAFETY: `self` is checked to be valid and in bounds above.
265 unsafe { Some(&mut *self.get_unchecked_mut(slice)) }
270 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
271 // SAFETY: the caller guarantees that `slice` is not dangling, so it
272 // cannot be longer than `isize::MAX`. They also guarantee that
273 // `self` is in bounds of `slice` so `self` cannot overflow an `isize`,
274 // so the call to `add` is safe.
275 unsafe { ptr::slice_from_raw_parts(slice.as_ptr().add(self.start), self.end - self.start) }
279 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
280 // SAFETY: see comments for `get_unchecked` above.
282 ptr::slice_from_raw_parts_mut(slice.as_mut_ptr().add(self.start), self.end - self.start)
287 fn index(self, slice: &[T]) -> &[T] {
288 if self.start > self.end {
289 slice_index_order_fail(self.start, self.end);
290 } else if self.end > slice.len() {
291 slice_end_index_len_fail(self.end, slice.len());
293 // SAFETY: `self` is checked to be valid and in bounds above.
294 unsafe { &*self.get_unchecked(slice) }
298 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
299 if self.start > self.end {
300 slice_index_order_fail(self.start, self.end);
301 } else if self.end > slice.len() {
302 slice_end_index_len_fail(self.end, slice.len());
304 // SAFETY: `self` is checked to be valid and in bounds above.
305 unsafe { &mut *self.get_unchecked_mut(slice) }
309 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
310 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
311 unsafe impl<T> const SliceIndex<[T]> for ops::RangeTo<usize> {
315 fn get(self, slice: &[T]) -> Option<&[T]> {
316 (0..self.end).get(slice)
320 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
321 (0..self.end).get_mut(slice)
325 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
326 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
327 unsafe { (0..self.end).get_unchecked(slice) }
331 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
332 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
333 unsafe { (0..self.end).get_unchecked_mut(slice) }
337 fn index(self, slice: &[T]) -> &[T] {
338 (0..self.end).index(slice)
342 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
343 (0..self.end).index_mut(slice)
347 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
348 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
349 unsafe impl<T> const SliceIndex<[T]> for ops::RangeFrom<usize> {
353 fn get(self, slice: &[T]) -> Option<&[T]> {
354 (self.start..slice.len()).get(slice)
358 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
359 (self.start..slice.len()).get_mut(slice)
363 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
364 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
365 unsafe { (self.start..slice.len()).get_unchecked(slice) }
369 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
370 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
371 unsafe { (self.start..slice.len()).get_unchecked_mut(slice) }
375 fn index(self, slice: &[T]) -> &[T] {
376 if self.start > slice.len() {
377 slice_start_index_len_fail(self.start, slice.len());
379 // SAFETY: `self` is checked to be valid and in bounds above.
380 unsafe { &*self.get_unchecked(slice) }
384 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
385 if self.start > slice.len() {
386 slice_start_index_len_fail(self.start, slice.len());
388 // SAFETY: `self` is checked to be valid and in bounds above.
389 unsafe { &mut *self.get_unchecked_mut(slice) }
393 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
394 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
395 unsafe impl<T> const SliceIndex<[T]> for ops::RangeFull {
399 fn get(self, slice: &[T]) -> Option<&[T]> {
404 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
409 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
414 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
419 fn index(self, slice: &[T]) -> &[T] {
424 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
429 #[stable(feature = "inclusive_range", since = "1.26.0")]
430 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
431 unsafe impl<T> const SliceIndex<[T]> for ops::RangeInclusive<usize> {
435 fn get(self, slice: &[T]) -> Option<&[T]> {
436 if *self.end() == usize::MAX { None } else { self.into_slice_range().get(slice) }
440 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
441 if *self.end() == usize::MAX { None } else { self.into_slice_range().get_mut(slice) }
445 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
446 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
447 unsafe { self.into_slice_range().get_unchecked(slice) }
451 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
452 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
453 unsafe { self.into_slice_range().get_unchecked_mut(slice) }
457 fn index(self, slice: &[T]) -> &[T] {
458 if *self.end() == usize::MAX {
459 slice_end_index_overflow_fail();
461 self.into_slice_range().index(slice)
465 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
466 if *self.end() == usize::MAX {
467 slice_end_index_overflow_fail();
469 self.into_slice_range().index_mut(slice)
473 #[stable(feature = "inclusive_range", since = "1.26.0")]
474 #[rustc_const_unstable(feature = "const_slice_index", issue = "none")]
475 unsafe impl<T> const SliceIndex<[T]> for ops::RangeToInclusive<usize> {
479 fn get(self, slice: &[T]) -> Option<&[T]> {
480 (0..=self.end).get(slice)
484 fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
485 (0..=self.end).get_mut(slice)
489 unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
490 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
491 unsafe { (0..=self.end).get_unchecked(slice) }
495 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
496 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
497 unsafe { (0..=self.end).get_unchecked_mut(slice) }
501 fn index(self, slice: &[T]) -> &[T] {
502 (0..=self.end).index(slice)
506 fn index_mut(self, slice: &mut [T]) -> &mut [T] {
507 (0..=self.end).index_mut(slice)
511 /// Performs bounds-checking of a range.
513 /// This method is similar to [`Index::index`] for slices, but it returns a
514 /// [`Range`] equivalent to `range`. You can use this method to turn any range
515 /// into `start` and `end` values.
517 /// `bounds` is the range of the slice to use for bounds-checking. It should
518 /// be a [`RangeTo`] range that ends at the length of the slice.
520 /// The returned [`Range`] is safe to pass to [`slice::get_unchecked`] and
521 /// [`slice::get_unchecked_mut`] for slices with the given range.
523 /// [`Range`]: ops::Range
524 /// [`RangeTo`]: ops::RangeTo
525 /// [`slice::get_unchecked`]: slice::get_unchecked
526 /// [`slice::get_unchecked_mut`]: slice::get_unchecked_mut
530 /// Panics if `range` would be out of bounds.
535 /// #![feature(slice_range)]
539 /// let v = [10, 40, 30];
540 /// assert_eq!(1..2, slice::range(1..2, ..v.len()));
541 /// assert_eq!(0..2, slice::range(..2, ..v.len()));
542 /// assert_eq!(1..3, slice::range(1.., ..v.len()));
545 /// Panics when [`Index::index`] would panic:
548 /// #![feature(slice_range)]
552 /// slice::range(2..1, ..3);
556 /// #![feature(slice_range)]
560 /// slice::range(1..4, ..3);
564 /// #![feature(slice_range)]
568 /// slice::range(1..=usize::MAX, ..3);
571 /// [`Index::index`]: ops::Index::index
573 #[unstable(feature = "slice_range", issue = "76393")]
574 pub fn range<R>(range: R, bounds: ops::RangeTo<usize>) -> ops::Range<usize>
576 R: ops::RangeBounds<usize>,
578 let len = bounds.end;
580 let start: ops::Bound<&usize> = range.start_bound();
581 let start = match start {
582 ops::Bound::Included(&start) => start,
583 ops::Bound::Excluded(start) => {
584 start.checked_add(1).unwrap_or_else(|| slice_start_index_overflow_fail())
586 ops::Bound::Unbounded => 0,
589 let end: ops::Bound<&usize> = range.end_bound();
590 let end = match end {
591 ops::Bound::Included(end) => {
592 end.checked_add(1).unwrap_or_else(|| slice_end_index_overflow_fail())
594 ops::Bound::Excluded(&end) => end,
595 ops::Bound::Unbounded => len,
599 slice_index_order_fail(start, end);
602 slice_end_index_len_fail(end, len);
605 ops::Range { start, end }
608 /// Convert pair of `ops::Bound`s into `ops::Range` without performing any bounds checking and (in debug) overflow checking
609 fn into_range_unchecked(
611 (start, end): (ops::Bound<usize>, ops::Bound<usize>),
612 ) -> ops::Range<usize> {
614 let start = match start {
615 Bound::Included(i) => i,
616 Bound::Excluded(i) => i + 1,
617 Bound::Unbounded => 0,
619 let end = match end {
620 Bound::Included(i) => i + 1,
621 Bound::Excluded(i) => i,
622 Bound::Unbounded => len,
627 /// Convert pair of `ops::Bound`s into `ops::Range`.
628 /// Returns `None` on overflowing indices.
631 (start, end): (ops::Bound<usize>, ops::Bound<usize>),
632 ) -> Option<ops::Range<usize>> {
634 let start = match start {
635 Bound::Included(start) => start,
636 Bound::Excluded(start) => start.checked_add(1)?,
637 Bound::Unbounded => 0,
640 let end = match end {
641 Bound::Included(end) => end.checked_add(1)?,
642 Bound::Excluded(end) => end,
643 Bound::Unbounded => len,
646 // Don't bother with checking `start < end` and `end <= len`
647 // since these checks are handled by `Range` impls
652 /// Convert pair of `ops::Bound`s into `ops::Range`.
653 /// Panics on overflowing indices.
656 (start, end): (ops::Bound<usize>, ops::Bound<usize>),
657 ) -> ops::Range<usize> {
659 let start = match start {
660 Bound::Included(start) => start,
661 Bound::Excluded(start) => {
662 start.checked_add(1).unwrap_or_else(|| slice_start_index_overflow_fail())
664 Bound::Unbounded => 0,
667 let end = match end {
668 Bound::Included(end) => {
669 end.checked_add(1).unwrap_or_else(|| slice_end_index_overflow_fail())
671 Bound::Excluded(end) => end,
672 Bound::Unbounded => len,
675 // Don't bother with checking `start < end` and `end <= len`
676 // since these checks are handled by `Range` impls
681 #[stable(feature = "slice_index_with_ops_bound_pair", since = "1.53.0")]
682 unsafe impl<T> SliceIndex<[T]> for (ops::Bound<usize>, ops::Bound<usize>) {
686 fn get(self, slice: &[T]) -> Option<&Self::Output> {
687 into_range(slice.len(), self)?.get(slice)
691 fn get_mut(self, slice: &mut [T]) -> Option<&mut Self::Output> {
692 into_range(slice.len(), self)?.get_mut(slice)
696 unsafe fn get_unchecked(self, slice: *const [T]) -> *const Self::Output {
697 // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
698 unsafe { into_range_unchecked(slice.len(), self).get_unchecked(slice) }
702 unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut Self::Output {
703 // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
704 unsafe { into_range_unchecked(slice.len(), self).get_unchecked_mut(slice) }
708 fn index(self, slice: &[T]) -> &Self::Output {
709 into_slice_range(slice.len(), self).index(slice)
713 fn index_mut(self, slice: &mut [T]) -> &mut Self::Output {
714 into_slice_range(slice.len(), self).index_mut(slice)