library/core/src/slice/index.rs

   1 //! Indexing implementations for `[T]`.
   2
   3 use crate::ops;
   4 use crate::ptr;
   5
   6 #[stable(feature = "rust1", since = "1.0.0")]
   7 impl<T, I> ops::Index<I> for [T]
   8 where
   9     I: SliceIndex<[T]>,
  10 {
  11     type Output = I::Output;
  12
  13     #[inline]
  14     fn index(&self, index: I) -> &I::Output {
  15         index.index(self)
  16     }
  17 }
  18
  19 #[stable(feature = "rust1", since = "1.0.0")]
  20 impl<T, I> ops::IndexMut<I> for [T]
  21 where
  22     I: SliceIndex<[T]>,
  23 {
  24     #[inline]
  25     fn index_mut(&mut self, index: I) -> &mut I::Output {
  26         index.index_mut(self)
  27     }
  28 }
  29
  30 #[inline(never)]
  31 #[cold]
  32 #[track_caller]
  33 fn slice_start_index_len_fail(index: usize, len: usize) -> ! {
  34     panic!("range start index {} out of range for slice of length {}", index, len);
  35 }
  36
  37 #[inline(never)]
  38 #[cold]
  39 #[track_caller]
  40 fn slice_end_index_len_fail(index: usize, len: usize) -> ! {
  41     panic!("range end index {} out of range for slice of length {}", index, len);
  42 }
  43
  44 #[inline(never)]
  45 #[cold]
  46 #[track_caller]
  47 fn slice_index_order_fail(index: usize, end: usize) -> ! {
  48     panic!("slice index starts at {} but ends at {}", index, end);
  49 }
  50
  51 #[inline(never)]
  52 #[cold]
  53 #[track_caller]
  54 fn slice_start_index_overflow_fail() -> ! {
  55     panic!("attempted to index slice from after maximum usize");
  56 }
  57
  58 #[inline(never)]
  59 #[cold]
  60 #[track_caller]
  61 fn slice_end_index_overflow_fail() -> ! {
  62     panic!("attempted to index slice up to maximum usize");
  63 }
  64
  65 mod private_slice_index {
  66     use super::ops;
  67     #[stable(feature = "slice_get_slice", since = "1.28.0")]
  68     pub trait Sealed {}
  69
  70     #[stable(feature = "slice_get_slice", since = "1.28.0")]
  71     impl Sealed for usize {}
  72     #[stable(feature = "slice_get_slice", since = "1.28.0")]
  73     impl Sealed for ops::Range<usize> {}
  74     #[stable(feature = "slice_get_slice", since = "1.28.0")]
  75     impl Sealed for ops::RangeTo<usize> {}
  76     #[stable(feature = "slice_get_slice", since = "1.28.0")]
  77     impl Sealed for ops::RangeFrom<usize> {}
  78     #[stable(feature = "slice_get_slice", since = "1.28.0")]
  79     impl Sealed for ops::RangeFull {}
  80     #[stable(feature = "slice_get_slice", since = "1.28.0")]
  81     impl Sealed for ops::RangeInclusive<usize> {}
  82     #[stable(feature = "slice_get_slice", since = "1.28.0")]
  83     impl Sealed for ops::RangeToInclusive<usize> {}
  84 }
  85
  86 /// A helper trait used for indexing operations.
  87 ///
  88 /// Implementations of this trait have to promise that if the argument
  89 /// to `get_(mut_)unchecked` is a safe reference, then so is the result.
  90 #[stable(feature = "slice_get_slice", since = "1.28.0")]
  91 #[rustc_on_unimplemented(
  92     on(T = "str", label = "string indices are ranges of `usize`",),
  93     on(
  94         all(any(T = "str", T = "&str", T = "std::string::String"), _Self = "{integer}"),
  95         note = "you can use `.chars().nth()` or `.bytes().nth()`\n\
  96                 for more information, see chapter 8 in The Book: \
  97                 <https://doc.rust-lang.org/book/ch08-02-strings.html#indexing-into-strings>"
  98     ),
  99     message = "the type `{T}` cannot be indexed by `{Self}`",
 100     label = "slice indices are of type `usize` or ranges of `usize`"
 101 )]
 102 pub unsafe trait SliceIndex<T: ?Sized>: private_slice_index::Sealed {
 103     /// The output type returned by methods.
 104     #[stable(feature = "slice_get_slice", since = "1.28.0")]
 105     type Output: ?Sized;
 106
 107     /// Returns a shared reference to the output at this location, if in
 108     /// bounds.
 109     #[unstable(feature = "slice_index_methods", issue = "none")]
 110     fn get(self, slice: &T) -> Option<&Self::Output>;
 111
 112     /// Returns a mutable reference to the output at this location, if in
 113     /// bounds.
 114     #[unstable(feature = "slice_index_methods", issue = "none")]
 115     fn get_mut(self, slice: &mut T) -> Option<&mut Self::Output>;
 116
 117     /// Returns a shared reference to the output at this location, without
 118     /// performing any bounds checking.
 119     /// Calling this method with an out-of-bounds index or a dangling `slice` pointer
 120     /// is *[undefined behavior]* even if the resulting reference is not used.
 121     ///
 122     /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
 123     #[unstable(feature = "slice_index_methods", issue = "none")]
 124     unsafe fn get_unchecked(self, slice: *const T) -> *const Self::Output;
 125
 126     /// Returns a mutable reference to the output at this location, without
 127     /// performing any bounds checking.
 128     /// Calling this method with an out-of-bounds index or a dangling `slice` pointer
 129     /// is *[undefined behavior]* even if the resulting reference is not used.
 130     ///
 131     /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
 132     #[unstable(feature = "slice_index_methods", issue = "none")]
 133     unsafe fn get_unchecked_mut(self, slice: *mut T) -> *mut Self::Output;
 134
 135     /// Returns a shared reference to the output at this location, panicking
 136     /// if out of bounds.
 137     #[unstable(feature = "slice_index_methods", issue = "none")]
 138     #[track_caller]
 139     fn index(self, slice: &T) -> &Self::Output;
 140
 141     /// Returns a mutable reference to the output at this location, panicking
 142     /// if out of bounds.
 143     #[unstable(feature = "slice_index_methods", issue = "none")]
 144     #[track_caller]
 145     fn index_mut(self, slice: &mut T) -> &mut Self::Output;
 146 }
 147
 148 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
 149 unsafe impl<T> SliceIndex<[T]> for usize {
 150     type Output = T;
 151
 152     #[inline]
 153     fn get(self, slice: &[T]) -> Option<&T> {
 154         // SAFETY: `self` is checked to be in bounds.
 155         if self < slice.len() { unsafe { Some(&*self.get_unchecked(slice)) } } else { None }
 156     }
 157
 158     #[inline]
 159     fn get_mut(self, slice: &mut [T]) -> Option<&mut T> {
 160         // SAFETY: `self` is checked to be in bounds.
 161         if self < slice.len() { unsafe { Some(&mut *self.get_unchecked_mut(slice)) } } else { None }
 162     }
 163
 164     #[inline]
 165     unsafe fn get_unchecked(self, slice: *const [T]) -> *const T {
 166         // SAFETY: the caller guarantees that `slice` is not dangling, so it
 167         // cannot be longer than `isize::MAX`. They also guarantee that
 168         // `self` is in bounds of `slice` so `self` cannot overflow an `isize`,
 169         // so the call to `add` is safe.
 170         unsafe { slice.as_ptr().add(self) }
 171     }
 172
 173     #[inline]
 174     unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut T {
 175         // SAFETY: see comments for `get_unchecked` above.
 176         unsafe { slice.as_mut_ptr().add(self) }
 177     }
 178
 179     #[inline]
 180     fn index(self, slice: &[T]) -> &T {
 181         // N.B., use intrinsic indexing
 182         &(*slice)[self]
 183     }
 184
 185     #[inline]
 186     fn index_mut(self, slice: &mut [T]) -> &mut T {
 187         // N.B., use intrinsic indexing
 188         &mut (*slice)[self]
 189     }
 190 }
 191
 192 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
 193 unsafe impl<T> SliceIndex<[T]> for ops::Range<usize> {
 194     type Output = [T];
 195
 196     #[inline]
 197     fn get(self, slice: &[T]) -> Option<&[T]> {
 198         if self.start > self.end || self.end > slice.len() {
 199             None
 200         } else {
 201             // SAFETY: `self` is checked to be valid and in bounds above.
 202             unsafe { Some(&*self.get_unchecked(slice)) }
 203         }
 204     }
 205
 206     #[inline]
 207     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
 208         if self.start > self.end || self.end > slice.len() {
 209             None
 210         } else {
 211             // SAFETY: `self` is checked to be valid and in bounds above.
 212             unsafe { Some(&mut *self.get_unchecked_mut(slice)) }
 213         }
 214     }
 215
 216     #[inline]
 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 { ptr::slice_from_raw_parts(slice.as_ptr().add(self.start), self.end - self.start) }
 223     }
 224
 225     #[inline]
 226     unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
 227         // SAFETY: see comments for `get_unchecked` above.
 228         unsafe {
 229             ptr::slice_from_raw_parts_mut(slice.as_mut_ptr().add(self.start), self.end - self.start)
 230         }
 231     }
 232
 233     #[inline]
 234     fn index(self, slice: &[T]) -> &[T] {
 235         if self.start > self.end {
 236             slice_index_order_fail(self.start, self.end);
 237         } else if self.end > slice.len() {
 238             slice_end_index_len_fail(self.end, slice.len());
 239         }
 240         // SAFETY: `self` is checked to be valid and in bounds above.
 241         unsafe { &*self.get_unchecked(slice) }
 242     }
 243
 244     #[inline]
 245     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
 246         if self.start > self.end {
 247             slice_index_order_fail(self.start, self.end);
 248         } else if self.end > slice.len() {
 249             slice_end_index_len_fail(self.end, slice.len());
 250         }
 251         // SAFETY: `self` is checked to be valid and in bounds above.
 252         unsafe { &mut *self.get_unchecked_mut(slice) }
 253     }
 254 }
 255
 256 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
 257 unsafe impl<T> SliceIndex<[T]> for ops::RangeTo<usize> {
 258     type Output = [T];
 259
 260     #[inline]
 261     fn get(self, slice: &[T]) -> Option<&[T]> {
 262         (0..self.end).get(slice)
 263     }
 264
 265     #[inline]
 266     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
 267         (0..self.end).get_mut(slice)
 268     }
 269
 270     #[inline]
 271     unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
 272         // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
 273         unsafe { (0..self.end).get_unchecked(slice) }
 274     }
 275
 276     #[inline]
 277     unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
 278         // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
 279         unsafe { (0..self.end).get_unchecked_mut(slice) }
 280     }
 281
 282     #[inline]
 283     fn index(self, slice: &[T]) -> &[T] {
 284         (0..self.end).index(slice)
 285     }
 286
 287     #[inline]
 288     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
 289         (0..self.end).index_mut(slice)
 290     }
 291 }
 292
 293 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
 294 unsafe impl<T> SliceIndex<[T]> for ops::RangeFrom<usize> {
 295     type Output = [T];
 296
 297     #[inline]
 298     fn get(self, slice: &[T]) -> Option<&[T]> {
 299         (self.start..slice.len()).get(slice)
 300     }
 301
 302     #[inline]
 303     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
 304         (self.start..slice.len()).get_mut(slice)
 305     }
 306
 307     #[inline]
 308     unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
 309         // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
 310         unsafe { (self.start..slice.len()).get_unchecked(slice) }
 311     }
 312
 313     #[inline]
 314     unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
 315         // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
 316         unsafe { (self.start..slice.len()).get_unchecked_mut(slice) }
 317     }
 318
 319     #[inline]
 320     fn index(self, slice: &[T]) -> &[T] {
 321         if self.start > slice.len() {
 322             slice_start_index_len_fail(self.start, slice.len());
 323         }
 324         // SAFETY: `self` is checked to be valid and in bounds above.
 325         unsafe { &*self.get_unchecked(slice) }
 326     }
 327
 328     #[inline]
 329     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
 330         if self.start > slice.len() {
 331             slice_start_index_len_fail(self.start, slice.len());
 332         }
 333         // SAFETY: `self` is checked to be valid and in bounds above.
 334         unsafe { &mut *self.get_unchecked_mut(slice) }
 335     }
 336 }
 337
 338 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
 339 unsafe impl<T> SliceIndex<[T]> for ops::RangeFull {
 340     type Output = [T];
 341
 342     #[inline]
 343     fn get(self, slice: &[T]) -> Option<&[T]> {
 344         Some(slice)
 345     }
 346
 347     #[inline]
 348     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
 349         Some(slice)
 350     }
 351
 352     #[inline]
 353     unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
 354         slice
 355     }
 356
 357     #[inline]
 358     unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
 359         slice
 360     }
 361
 362     #[inline]
 363     fn index(self, slice: &[T]) -> &[T] {
 364         slice
 365     }
 366
 367     #[inline]
 368     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
 369         slice
 370     }
 371 }
 372
 373 #[stable(feature = "inclusive_range", since = "1.26.0")]
 374 unsafe impl<T> SliceIndex<[T]> for ops::RangeInclusive<usize> {
 375     type Output = [T];
 376
 377     #[inline]
 378     fn get(self, slice: &[T]) -> Option<&[T]> {
 379         if *self.end() == usize::MAX { None } else { self.into_slice_range().get(slice) }
 380     }
 381
 382     #[inline]
 383     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
 384         if *self.end() == usize::MAX { None } else { self.into_slice_range().get_mut(slice) }
 385     }
 386
 387     #[inline]
 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.into_slice_range().get_unchecked(slice) }
 391     }
 392
 393     #[inline]
 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.into_slice_range().get_unchecked_mut(slice) }
 397     }
 398
 399     #[inline]
 400     fn index(self, slice: &[T]) -> &[T] {
 401         if *self.end() == usize::MAX {
 402             slice_end_index_overflow_fail();
 403         }
 404         self.into_slice_range().index(slice)
 405     }
 406
 407     #[inline]
 408     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
 409         if *self.end() == usize::MAX {
 410             slice_end_index_overflow_fail();
 411         }
 412         self.into_slice_range().index_mut(slice)
 413     }
 414 }
 415
 416 #[stable(feature = "inclusive_range", since = "1.26.0")]
 417 unsafe impl<T> SliceIndex<[T]> for ops::RangeToInclusive<usize> {
 418     type Output = [T];
 419
 420     #[inline]
 421     fn get(self, slice: &[T]) -> Option<&[T]> {
 422         (0..=self.end).get(slice)
 423     }
 424
 425     #[inline]
 426     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
 427         (0..=self.end).get_mut(slice)
 428     }
 429
 430     #[inline]
 431     unsafe fn get_unchecked(self, slice: *const [T]) -> *const [T] {
 432         // SAFETY: the caller has to uphold the safety contract for `get_unchecked`.
 433         unsafe { (0..=self.end).get_unchecked(slice) }
 434     }
 435
 436     #[inline]
 437     unsafe fn get_unchecked_mut(self, slice: *mut [T]) -> *mut [T] {
 438         // SAFETY: the caller has to uphold the safety contract for `get_unchecked_mut`.
 439         unsafe { (0..=self.end).get_unchecked_mut(slice) }
 440     }
 441
 442     #[inline]
 443     fn index(self, slice: &[T]) -> &[T] {
 444         (0..=self.end).index(slice)
 445     }
 446
 447     #[inline]
 448     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
 449         (0..=self.end).index_mut(slice)
 450     }
 451 }
 452
 453 /// Performs bounds-checking of a range.
 454 ///
 455 /// This method is similar to [`Index::index`] for slices, but it returns a
 456 /// [`Range`] equivalent to `range`. You can use this method to turn any range
 457 /// into `start` and `end` values.
 458 ///
 459 /// `bounds` is the range of the slice to use for bounds-checking. It should
 460 /// be a [`RangeTo`] range that ends at the length of the slice.
 461 ///
 462 /// The returned [`Range`] is safe to pass to [`slice::get_unchecked`] and
 463 /// [`slice::get_unchecked_mut`] for slices with the given range.
 464 ///
 465 /// [`Range`]: ops::Range
 466 /// [`RangeTo`]: ops::RangeTo
 467 /// [`slice::get_unchecked`]: slice::get_unchecked
 468 /// [`slice::get_unchecked_mut`]: slice::get_unchecked_mut
 469 ///
 470 /// # Panics
 471 ///
 472 /// Panics if `range` would be out of bounds.
 473 ///
 474 /// # Examples
 475 ///
 476 /// ```
 477 /// #![feature(slice_range)]
 478 ///
 479 /// use std::slice;
 480 ///
 481 /// let v = [10, 40, 30];
 482 /// assert_eq!(1..2, slice::range(1..2, ..v.len()));
 483 /// assert_eq!(0..2, slice::range(..2, ..v.len()));
 484 /// assert_eq!(1..3, slice::range(1.., ..v.len()));
 485 /// ```
 486 ///
 487 /// Panics when [`Index::index`] would panic:
 488 ///
 489 /// ```should_panic
 490 /// #![feature(slice_range)]
 491 ///
 492 /// use std::slice;
 493 ///
 494 /// slice::range(2..1, ..3);
 495 /// ```
 496 ///
 497 /// ```should_panic
 498 /// #![feature(slice_range)]
 499 ///
 500 /// use std::slice;
 501 ///
 502 /// slice::range(1..4, ..3);
 503 /// ```
 504 ///
 505 /// ```should_panic
 506 /// #![feature(slice_range)]
 507 ///
 508 /// use std::slice;
 509 ///
 510 /// slice::range(1..=usize::MAX, ..3);
 511 /// ```
 512 ///
 513 /// [`Index::index`]: ops::Index::index
 514 #[track_caller]
 515 #[unstable(feature = "slice_range", issue = "76393")]
 516 pub fn range<R>(range: R, bounds: ops::RangeTo<usize>) -> ops::Range<usize>
 517 where
 518     R: ops::RangeBounds<usize>,
 519 {
 520     let len = bounds.end;
 521
 522     let start: ops::Bound<&usize> = range.start_bound();
 523     let start = match start {
 524         ops::Bound::Included(&start) => start,
 525         ops::Bound::Excluded(start) => {
 526             start.checked_add(1).unwrap_or_else(|| slice_start_index_overflow_fail())
 527         }
 528         ops::Bound::Unbounded => 0,
 529     };
 530
 531     let end: ops::Bound<&usize> = range.end_bound();
 532     let end = match end {
 533         ops::Bound::Included(end) => {
 534             end.checked_add(1).unwrap_or_else(|| slice_end_index_overflow_fail())
 535         }
 536         ops::Bound::Excluded(&end) => end,
 537         ops::Bound::Unbounded => len,
 538     };
 539
 540     if start > end {
 541         slice_index_order_fail(start, end);
 542     }
 543     if end > len {
 544         slice_end_index_len_fail(end, len);
 545     }
 546
 547     ops::Range { start, end }
 548 }