]> git.lizzy.rs Git - rust.git/blob - src/libcore/slice/mod.rs
Add comment on use of unsafe
[rust.git] / src / libcore / slice / mod.rs
1 // ignore-tidy-filelength
2 // ignore-tidy-undocumented-unsafe
3
4 //! Slice management and manipulation.
5 //!
6 //! For more details see [`std::slice`].
7 //!
8 //! [`std::slice`]: ../../std/slice/index.html
9
10 #![stable(feature = "rust1", since = "1.0.0")]
11
12 // How this module is organized.
13 //
14 // The library infrastructure for slices is fairly messy. There's
15 // a lot of stuff defined here. Let's keep it clean.
16 //
17 // The layout of this file is thus:
18 //
19 // * Inherent methods. This is where most of the slice API resides.
20 // * Implementations of a few common traits with important slice ops.
21 // * Definitions of a bunch of iterators.
22 // * Free functions.
23 // * The `raw` and `bytes` submodules.
24 // * Boilerplate trait implementations.
25
26 use crate::cmp;
27 use crate::cmp::Ordering::{self, Equal, Greater, Less};
28 use crate::fmt;
29 use crate::intrinsics::{assume, exact_div, is_aligned_and_not_null, unchecked_sub};
30 use crate::iter::*;
31 use crate::marker::{self, Copy, Send, Sized, Sync};
32 use crate::mem;
33 use crate::ops::{self, FnMut, Range};
34 use crate::option::Option;
35 use crate::option::Option::{None, Some};
36 use crate::ptr::{self, NonNull};
37 use crate::result::Result;
38 use crate::result::Result::{Err, Ok};
39
40 #[unstable(
41     feature = "slice_internals",
42     issue = "none",
43     reason = "exposed from core to be reused in std; use the memchr crate"
44 )]
45 /// Pure rust memchr implementation, taken from rust-memchr
46 pub mod memchr;
47
48 mod rotate;
49 mod sort;
50
51 //
52 // Extension traits
53 //
54
55 #[lang = "slice"]
56 #[cfg(not(test))]
57 impl<T> [T] {
58     /// Returns the number of elements in the slice.
59     ///
60     /// # Examples
61     ///
62     /// ```
63     /// let a = [1, 2, 3];
64     /// assert_eq!(a.len(), 3);
65     /// ```
66     #[stable(feature = "rust1", since = "1.0.0")]
67     #[rustc_const_stable(feature = "const_slice_len", since = "1.32.0")]
68     #[inline]
69     // SAFETY: const sound because we transmute out the length field as a usize (which it must be)
70     #[allow(unused_attributes)]
71     #[allow_internal_unstable(const_fn_union)]
72     pub const fn len(&self) -> usize {
73         unsafe { crate::ptr::Repr { rust: self }.raw.len }
74     }
75
76     /// Returns `true` if the slice has a length of 0.
77     ///
78     /// # Examples
79     ///
80     /// ```
81     /// let a = [1, 2, 3];
82     /// assert!(!a.is_empty());
83     /// ```
84     #[stable(feature = "rust1", since = "1.0.0")]
85     #[rustc_const_stable(feature = "const_slice_is_empty", since = "1.32.0")]
86     #[inline]
87     pub const fn is_empty(&self) -> bool {
88         self.len() == 0
89     }
90
91     /// Returns the first element of the slice, or `None` if it is empty.
92     ///
93     /// # Examples
94     ///
95     /// ```
96     /// let v = [10, 40, 30];
97     /// assert_eq!(Some(&10), v.first());
98     ///
99     /// let w: &[i32] = &[];
100     /// assert_eq!(None, w.first());
101     /// ```
102     #[stable(feature = "rust1", since = "1.0.0")]
103     #[inline]
104     pub fn first(&self) -> Option<&T> {
105         if let [first, ..] = self { Some(first) } else { None }
106     }
107
108     /// Returns a mutable pointer to the first element of the slice, or `None` if it is empty.
109     ///
110     /// # Examples
111     ///
112     /// ```
113     /// let x = &mut [0, 1, 2];
114     ///
115     /// if let Some(first) = x.first_mut() {
116     ///     *first = 5;
117     /// }
118     /// assert_eq!(x, &[5, 1, 2]);
119     /// ```
120     #[stable(feature = "rust1", since = "1.0.0")]
121     #[inline]
122     pub fn first_mut(&mut self) -> Option<&mut T> {
123         if let [first, ..] = self { Some(first) } else { None }
124     }
125
126     /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
127     ///
128     /// # Examples
129     ///
130     /// ```
131     /// let x = &[0, 1, 2];
132     ///
133     /// if let Some((first, elements)) = x.split_first() {
134     ///     assert_eq!(first, &0);
135     ///     assert_eq!(elements, &[1, 2]);
136     /// }
137     /// ```
138     #[stable(feature = "slice_splits", since = "1.5.0")]
139     #[inline]
140     pub fn split_first(&self) -> Option<(&T, &[T])> {
141         if let [first, tail @ ..] = self { Some((first, tail)) } else { None }
142     }
143
144     /// Returns the first and all the rest of the elements of the slice, or `None` if it is empty.
145     ///
146     /// # Examples
147     ///
148     /// ```
149     /// let x = &mut [0, 1, 2];
150     ///
151     /// if let Some((first, elements)) = x.split_first_mut() {
152     ///     *first = 3;
153     ///     elements[0] = 4;
154     ///     elements[1] = 5;
155     /// }
156     /// assert_eq!(x, &[3, 4, 5]);
157     /// ```
158     #[stable(feature = "slice_splits", since = "1.5.0")]
159     #[inline]
160     pub fn split_first_mut(&mut self) -> Option<(&mut T, &mut [T])> {
161         if let [first, tail @ ..] = self { Some((first, tail)) } else { None }
162     }
163
164     /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
165     ///
166     /// # Examples
167     ///
168     /// ```
169     /// let x = &[0, 1, 2];
170     ///
171     /// if let Some((last, elements)) = x.split_last() {
172     ///     assert_eq!(last, &2);
173     ///     assert_eq!(elements, &[0, 1]);
174     /// }
175     /// ```
176     #[stable(feature = "slice_splits", since = "1.5.0")]
177     #[inline]
178     pub fn split_last(&self) -> Option<(&T, &[T])> {
179         if let [init @ .., last] = self { Some((last, init)) } else { None }
180     }
181
182     /// Returns the last and all the rest of the elements of the slice, or `None` if it is empty.
183     ///
184     /// # Examples
185     ///
186     /// ```
187     /// let x = &mut [0, 1, 2];
188     ///
189     /// if let Some((last, elements)) = x.split_last_mut() {
190     ///     *last = 3;
191     ///     elements[0] = 4;
192     ///     elements[1] = 5;
193     /// }
194     /// assert_eq!(x, &[4, 5, 3]);
195     /// ```
196     #[stable(feature = "slice_splits", since = "1.5.0")]
197     #[inline]
198     pub fn split_last_mut(&mut self) -> Option<(&mut T, &mut [T])> {
199         if let [init @ .., last] = self { Some((last, init)) } else { None }
200     }
201
202     /// Returns the last element of the slice, or `None` if it is empty.
203     ///
204     /// # Examples
205     ///
206     /// ```
207     /// let v = [10, 40, 30];
208     /// assert_eq!(Some(&30), v.last());
209     ///
210     /// let w: &[i32] = &[];
211     /// assert_eq!(None, w.last());
212     /// ```
213     #[stable(feature = "rust1", since = "1.0.0")]
214     #[inline]
215     pub fn last(&self) -> Option<&T> {
216         if let [.., last] = self { Some(last) } else { None }
217     }
218
219     /// Returns a mutable pointer to the last item in the slice.
220     ///
221     /// # Examples
222     ///
223     /// ```
224     /// let x = &mut [0, 1, 2];
225     ///
226     /// if let Some(last) = x.last_mut() {
227     ///     *last = 10;
228     /// }
229     /// assert_eq!(x, &[0, 1, 10]);
230     /// ```
231     #[stable(feature = "rust1", since = "1.0.0")]
232     #[inline]
233     pub fn last_mut(&mut self) -> Option<&mut T> {
234         if let [.., last] = self { Some(last) } else { None }
235     }
236
237     /// Returns a reference to an element or subslice depending on the type of
238     /// index.
239     ///
240     /// - If given a position, returns a reference to the element at that
241     ///   position or `None` if out of bounds.
242     /// - If given a range, returns the subslice corresponding to that range,
243     ///   or `None` if out of bounds.
244     ///
245     /// # Examples
246     ///
247     /// ```
248     /// let v = [10, 40, 30];
249     /// assert_eq!(Some(&40), v.get(1));
250     /// assert_eq!(Some(&[10, 40][..]), v.get(0..2));
251     /// assert_eq!(None, v.get(3));
252     /// assert_eq!(None, v.get(0..4));
253     /// ```
254     #[stable(feature = "rust1", since = "1.0.0")]
255     #[inline]
256     pub fn get<I>(&self, index: I) -> Option<&I::Output>
257     where
258         I: SliceIndex<Self>,
259     {
260         index.get(self)
261     }
262
263     /// Returns a mutable reference to an element or subslice depending on the
264     /// type of index (see [`get`]) or `None` if the index is out of bounds.
265     ///
266     /// [`get`]: #method.get
267     ///
268     /// # Examples
269     ///
270     /// ```
271     /// let x = &mut [0, 1, 2];
272     ///
273     /// if let Some(elem) = x.get_mut(1) {
274     ///     *elem = 42;
275     /// }
276     /// assert_eq!(x, &[0, 42, 2]);
277     /// ```
278     #[stable(feature = "rust1", since = "1.0.0")]
279     #[inline]
280     pub fn get_mut<I>(&mut self, index: I) -> Option<&mut I::Output>
281     where
282         I: SliceIndex<Self>,
283     {
284         index.get_mut(self)
285     }
286
287     /// Returns a reference to an element or subslice, without doing bounds
288     /// checking.
289     ///
290     /// This is generally not recommended, use with caution!
291     /// Calling this method with an out-of-bounds index is *[undefined behavior]*
292     /// even if the resulting reference is not used.
293     /// For a safe alternative see [`get`].
294     ///
295     /// [`get`]: #method.get
296     /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
297     ///
298     /// # Examples
299     ///
300     /// ```
301     /// let x = &[1, 2, 4];
302     ///
303     /// unsafe {
304     ///     assert_eq!(x.get_unchecked(1), &2);
305     /// }
306     /// ```
307     #[stable(feature = "rust1", since = "1.0.0")]
308     #[inline]
309     pub unsafe fn get_unchecked<I>(&self, index: I) -> &I::Output
310     where
311         I: SliceIndex<Self>,
312     {
313         index.get_unchecked(self)
314     }
315
316     /// Returns a mutable reference to an element or subslice, without doing
317     /// bounds checking.
318     ///
319     /// This is generally not recommended, use with caution!
320     /// Calling this method with an out-of-bounds index is *[undefined behavior]*
321     /// even if the resulting reference is not used.
322     /// For a safe alternative see [`get_mut`].
323     ///
324     /// [`get_mut`]: #method.get_mut
325     /// [undefined behavior]: https://doc.rust-lang.org/reference/behavior-considered-undefined.html
326     ///
327     /// # Examples
328     ///
329     /// ```
330     /// let x = &mut [1, 2, 4];
331     ///
332     /// unsafe {
333     ///     let elem = x.get_unchecked_mut(1);
334     ///     *elem = 13;
335     /// }
336     /// assert_eq!(x, &[1, 13, 4]);
337     /// ```
338     #[stable(feature = "rust1", since = "1.0.0")]
339     #[inline]
340     pub unsafe fn get_unchecked_mut<I>(&mut self, index: I) -> &mut I::Output
341     where
342         I: SliceIndex<Self>,
343     {
344         index.get_unchecked_mut(self)
345     }
346
347     /// Returns a raw pointer to the slice's buffer.
348     ///
349     /// The caller must ensure that the slice outlives the pointer this
350     /// function returns, or else it will end up pointing to garbage.
351     ///
352     /// The caller must also ensure that the memory the pointer (non-transitively) points to
353     /// is never written to (except inside an `UnsafeCell`) using this pointer or any pointer
354     /// derived from it. If you need to mutate the contents of the slice, use [`as_mut_ptr`].
355     ///
356     /// Modifying the container referenced by this slice may cause its buffer
357     /// to be reallocated, which would also make any pointers to it invalid.
358     ///
359     /// # Examples
360     ///
361     /// ```
362     /// let x = &[1, 2, 4];
363     /// let x_ptr = x.as_ptr();
364     ///
365     /// unsafe {
366     ///     for i in 0..x.len() {
367     ///         assert_eq!(x.get_unchecked(i), &*x_ptr.add(i));
368     ///     }
369     /// }
370     /// ```
371     ///
372     /// [`as_mut_ptr`]: #method.as_mut_ptr
373     #[stable(feature = "rust1", since = "1.0.0")]
374     #[rustc_const_stable(feature = "const_slice_as_ptr", since = "1.32.0")]
375     #[inline]
376     pub const fn as_ptr(&self) -> *const T {
377         self as *const [T] as *const T
378     }
379
380     /// Returns an unsafe mutable pointer to the slice's buffer.
381     ///
382     /// The caller must ensure that the slice outlives the pointer this
383     /// function returns, or else it will end up pointing to garbage.
384     ///
385     /// Modifying the container referenced by this slice may cause its buffer
386     /// to be reallocated, which would also make any pointers to it invalid.
387     ///
388     /// # Examples
389     ///
390     /// ```
391     /// let x = &mut [1, 2, 4];
392     /// let x_ptr = x.as_mut_ptr();
393     ///
394     /// unsafe {
395     ///     for i in 0..x.len() {
396     ///         *x_ptr.add(i) += 2;
397     ///     }
398     /// }
399     /// assert_eq!(x, &[3, 4, 6]);
400     /// ```
401     #[stable(feature = "rust1", since = "1.0.0")]
402     #[inline]
403     pub fn as_mut_ptr(&mut self) -> *mut T {
404         self as *mut [T] as *mut T
405     }
406
407     /// Returns the two raw pointers spanning the slice.
408     ///
409     /// The returned range is half-open, which means that the end pointer
410     /// points *one past* the last element of the slice. This way, an empty
411     /// slice is represented by two equal pointers, and the difference between
412     /// the two pointers represents the size of the slice.
413     ///
414     /// See [`as_ptr`] for warnings on using these pointers. The end pointer
415     /// requires extra caution, as it does not point to a valid element in the
416     /// slice.
417     ///
418     /// This function is useful for interacting with foreign interfaces which
419     /// use two pointers to refer to a range of elements in memory, as is
420     /// common in C++.
421     ///
422     /// It can also be useful to check if a pointer to an element refers to an
423     /// element of this slice:
424     ///
425     /// ```
426     /// #![feature(slice_ptr_range)]
427     ///
428     /// let a = [1, 2, 3];
429     /// let x = &a[1] as *const _;
430     /// let y = &5 as *const _;
431     ///
432     /// assert!(a.as_ptr_range().contains(&x));
433     /// assert!(!a.as_ptr_range().contains(&y));
434     /// ```
435     ///
436     /// [`as_ptr`]: #method.as_ptr
437     #[unstable(feature = "slice_ptr_range", issue = "65807")]
438     #[inline]
439     pub fn as_ptr_range(&self) -> Range<*const T> {
440         // The `add` here is safe, because:
441         //
442         //   - Both pointers are part of the same object, as pointing directly
443         //     past the object also counts.
444         //
445         //   - The size of the slice is never larger than isize::MAX bytes, as
446         //     noted here:
447         //       - https://github.com/rust-lang/unsafe-code-guidelines/issues/102#issuecomment-473340447
448         //       - https://doc.rust-lang.org/reference/behavior-considered-undefined.html
449         //       - https://doc.rust-lang.org/core/slice/fn.from_raw_parts.html#safety
450         //     (This doesn't seem normative yet, but the very same assumption is
451         //     made in many places, including the Index implementation of slices.)
452         //
453         //   - There is no wrapping around involved, as slices do not wrap past
454         //     the end of the address space.
455         //
456         // See the documentation of pointer::add.
457         let start = self.as_ptr();
458         let end = unsafe { start.add(self.len()) };
459         start..end
460     }
461
462     /// Returns the two unsafe mutable pointers spanning the slice.
463     ///
464     /// The returned range is half-open, which means that the end pointer
465     /// points *one past* the last element of the slice. This way, an empty
466     /// slice is represented by two equal pointers, and the difference between
467     /// the two pointers represents the size of the slice.
468     ///
469     /// See [`as_mut_ptr`] for warnings on using these pointers. The end
470     /// pointer requires extra caution, as it does not point to a valid element
471     /// in the slice.
472     ///
473     /// This function is useful for interacting with foreign interfaces which
474     /// use two pointers to refer to a range of elements in memory, as is
475     /// common in C++.
476     ///
477     /// [`as_mut_ptr`]: #method.as_mut_ptr
478     #[unstable(feature = "slice_ptr_range", issue = "65807")]
479     #[inline]
480     pub fn as_mut_ptr_range(&mut self) -> Range<*mut T> {
481         // See as_ptr_range() above for why `add` here is safe.
482         let start = self.as_mut_ptr();
483         let end = unsafe { start.add(self.len()) };
484         start..end
485     }
486
487     /// Swaps two elements in the slice.
488     ///
489     /// # Arguments
490     ///
491     /// * a - The index of the first element
492     /// * b - The index of the second element
493     ///
494     /// # Panics
495     ///
496     /// Panics if `a` or `b` are out of bounds.
497     ///
498     /// # Examples
499     ///
500     /// ```
501     /// let mut v = ["a", "b", "c", "d"];
502     /// v.swap(1, 3);
503     /// assert!(v == ["a", "d", "c", "b"]);
504     /// ```
505     #[stable(feature = "rust1", since = "1.0.0")]
506     #[inline]
507     pub fn swap(&mut self, a: usize, b: usize) {
508         unsafe {
509             // Can't take two mutable loans from one vector, so instead just cast
510             // them to their raw pointers to do the swap
511             let pa: *mut T = &mut self[a];
512             let pb: *mut T = &mut self[b];
513             ptr::swap(pa, pb);
514         }
515     }
516
517     /// Reverses the order of elements in the slice, in place.
518     ///
519     /// # Examples
520     ///
521     /// ```
522     /// let mut v = [1, 2, 3];
523     /// v.reverse();
524     /// assert!(v == [3, 2, 1]);
525     /// ```
526     #[stable(feature = "rust1", since = "1.0.0")]
527     #[inline]
528     pub fn reverse(&mut self) {
529         let mut i: usize = 0;
530         let ln = self.len();
531
532         // For very small types, all the individual reads in the normal
533         // path perform poorly.  We can do better, given efficient unaligned
534         // load/store, by loading a larger chunk and reversing a register.
535
536         // Ideally LLVM would do this for us, as it knows better than we do
537         // whether unaligned reads are efficient (since that changes between
538         // different ARM versions, for example) and what the best chunk size
539         // would be.  Unfortunately, as of LLVM 4.0 (2017-05) it only unrolls
540         // the loop, so we need to do this ourselves.  (Hypothesis: reverse
541         // is troublesome because the sides can be aligned differently --
542         // will be, when the length is odd -- so there's no way of emitting
543         // pre- and postludes to use fully-aligned SIMD in the middle.)
544
545         let fast_unaligned = cfg!(any(target_arch = "x86", target_arch = "x86_64"));
546
547         if fast_unaligned && mem::size_of::<T>() == 1 {
548             // Use the llvm.bswap intrinsic to reverse u8s in a usize
549             let chunk = mem::size_of::<usize>();
550             while i + chunk - 1 < ln / 2 {
551                 unsafe {
552                     let pa: *mut T = self.get_unchecked_mut(i);
553                     let pb: *mut T = self.get_unchecked_mut(ln - i - chunk);
554                     let va = ptr::read_unaligned(pa as *mut usize);
555                     let vb = ptr::read_unaligned(pb as *mut usize);
556                     ptr::write_unaligned(pa as *mut usize, vb.swap_bytes());
557                     ptr::write_unaligned(pb as *mut usize, va.swap_bytes());
558                 }
559                 i += chunk;
560             }
561         }
562
563         if fast_unaligned && mem::size_of::<T>() == 2 {
564             // Use rotate-by-16 to reverse u16s in a u32
565             let chunk = mem::size_of::<u32>() / 2;
566             while i + chunk - 1 < ln / 2 {
567                 unsafe {
568                     let pa: *mut T = self.get_unchecked_mut(i);
569                     let pb: *mut T = self.get_unchecked_mut(ln - i - chunk);
570                     let va = ptr::read_unaligned(pa as *mut u32);
571                     let vb = ptr::read_unaligned(pb as *mut u32);
572                     ptr::write_unaligned(pa as *mut u32, vb.rotate_left(16));
573                     ptr::write_unaligned(pb as *mut u32, va.rotate_left(16));
574                 }
575                 i += chunk;
576             }
577         }
578
579         while i < ln / 2 {
580             // Unsafe swap to avoid the bounds check in safe swap.
581             unsafe {
582                 let pa: *mut T = self.get_unchecked_mut(i);
583                 let pb: *mut T = self.get_unchecked_mut(ln - i - 1);
584                 ptr::swap(pa, pb);
585             }
586             i += 1;
587         }
588     }
589
590     /// Returns an iterator over the slice.
591     ///
592     /// # Examples
593     ///
594     /// ```
595     /// let x = &[1, 2, 4];
596     /// let mut iterator = x.iter();
597     ///
598     /// assert_eq!(iterator.next(), Some(&1));
599     /// assert_eq!(iterator.next(), Some(&2));
600     /// assert_eq!(iterator.next(), Some(&4));
601     /// assert_eq!(iterator.next(), None);
602     /// ```
603     #[stable(feature = "rust1", since = "1.0.0")]
604     #[inline]
605     pub fn iter(&self) -> Iter<'_, T> {
606         unsafe {
607             let ptr = self.as_ptr();
608             assume(!ptr.is_null());
609
610             let end = if mem::size_of::<T>() == 0 {
611                 (ptr as *const u8).wrapping_add(self.len()) as *const T
612             } else {
613                 ptr.add(self.len())
614             };
615
616             Iter { ptr: NonNull::new_unchecked(ptr as *mut T), end, _marker: marker::PhantomData }
617         }
618     }
619
620     /// Returns an iterator that allows modifying each value.
621     ///
622     /// # Examples
623     ///
624     /// ```
625     /// let x = &mut [1, 2, 4];
626     /// for elem in x.iter_mut() {
627     ///     *elem += 2;
628     /// }
629     /// assert_eq!(x, &[3, 4, 6]);
630     /// ```
631     #[stable(feature = "rust1", since = "1.0.0")]
632     #[inline]
633     pub fn iter_mut(&mut self) -> IterMut<'_, T> {
634         unsafe {
635             let ptr = self.as_mut_ptr();
636             assume(!ptr.is_null());
637
638             let end = if mem::size_of::<T>() == 0 {
639                 (ptr as *mut u8).wrapping_add(self.len()) as *mut T
640             } else {
641                 ptr.add(self.len())
642             };
643
644             IterMut { ptr: NonNull::new_unchecked(ptr), end, _marker: marker::PhantomData }
645         }
646     }
647
648     /// Returns an iterator over all contiguous windows of length
649     /// `size`. The windows overlap. If the slice is shorter than
650     /// `size`, the iterator returns no values.
651     ///
652     /// # Panics
653     ///
654     /// Panics if `size` is 0.
655     ///
656     /// # Examples
657     ///
658     /// ```
659     /// let slice = ['r', 'u', 's', 't'];
660     /// let mut iter = slice.windows(2);
661     /// assert_eq!(iter.next().unwrap(), &['r', 'u']);
662     /// assert_eq!(iter.next().unwrap(), &['u', 's']);
663     /// assert_eq!(iter.next().unwrap(), &['s', 't']);
664     /// assert!(iter.next().is_none());
665     /// ```
666     ///
667     /// If the slice is shorter than `size`:
668     ///
669     /// ```
670     /// let slice = ['f', 'o', 'o'];
671     /// let mut iter = slice.windows(4);
672     /// assert!(iter.next().is_none());
673     /// ```
674     #[stable(feature = "rust1", since = "1.0.0")]
675     #[inline]
676     pub fn windows(&self, size: usize) -> Windows<'_, T> {
677         assert!(size != 0);
678         Windows { v: self, size }
679     }
680
681     /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
682     /// beginning of the slice.
683     ///
684     /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
685     /// slice, then the last chunk will not have length `chunk_size`.
686     ///
687     /// See [`chunks_exact`] for a variant of this iterator that returns chunks of always exactly
688     /// `chunk_size` elements, and [`rchunks`] for the same iterator but starting at the end of the
689     /// slice.
690     ///
691     /// # Panics
692     ///
693     /// Panics if `chunk_size` is 0.
694     ///
695     /// # Examples
696     ///
697     /// ```
698     /// let slice = ['l', 'o', 'r', 'e', 'm'];
699     /// let mut iter = slice.chunks(2);
700     /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
701     /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
702     /// assert_eq!(iter.next().unwrap(), &['m']);
703     /// assert!(iter.next().is_none());
704     /// ```
705     ///
706     /// [`chunks_exact`]: #method.chunks_exact
707     /// [`rchunks`]: #method.rchunks
708     #[stable(feature = "rust1", since = "1.0.0")]
709     #[inline]
710     pub fn chunks(&self, chunk_size: usize) -> Chunks<'_, T> {
711         assert!(chunk_size != 0);
712         Chunks { v: self, chunk_size }
713     }
714
715     /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
716     /// beginning of the slice.
717     ///
718     /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
719     /// length of the slice, then the last chunk will not have length `chunk_size`.
720     ///
721     /// See [`chunks_exact_mut`] for a variant of this iterator that returns chunks of always
722     /// exactly `chunk_size` elements, and [`rchunks_mut`] for the same iterator but starting at
723     /// the end of the slice.
724     ///
725     /// # Panics
726     ///
727     /// Panics if `chunk_size` is 0.
728     ///
729     /// # Examples
730     ///
731     /// ```
732     /// let v = &mut [0, 0, 0, 0, 0];
733     /// let mut count = 1;
734     ///
735     /// for chunk in v.chunks_mut(2) {
736     ///     for elem in chunk.iter_mut() {
737     ///         *elem += count;
738     ///     }
739     ///     count += 1;
740     /// }
741     /// assert_eq!(v, &[1, 1, 2, 2, 3]);
742     /// ```
743     ///
744     /// [`chunks_exact_mut`]: #method.chunks_exact_mut
745     /// [`rchunks_mut`]: #method.rchunks_mut
746     #[stable(feature = "rust1", since = "1.0.0")]
747     #[inline]
748     pub fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<'_, T> {
749         assert!(chunk_size != 0);
750         ChunksMut { v: self, chunk_size }
751     }
752
753     /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
754     /// beginning of the slice.
755     ///
756     /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
757     /// slice, then the last up to `chunk_size-1` elements will be omitted and can be retrieved
758     /// from the `remainder` function of the iterator.
759     ///
760     /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
761     /// resulting code better than in the case of [`chunks`].
762     ///
763     /// See [`chunks`] for a variant of this iterator that also returns the remainder as a smaller
764     /// chunk, and [`rchunks_exact`] for the same iterator but starting at the end of the slice.
765     ///
766     /// # Panics
767     ///
768     /// Panics if `chunk_size` is 0.
769     ///
770     /// # Examples
771     ///
772     /// ```
773     /// let slice = ['l', 'o', 'r', 'e', 'm'];
774     /// let mut iter = slice.chunks_exact(2);
775     /// assert_eq!(iter.next().unwrap(), &['l', 'o']);
776     /// assert_eq!(iter.next().unwrap(), &['r', 'e']);
777     /// assert!(iter.next().is_none());
778     /// assert_eq!(iter.remainder(), &['m']);
779     /// ```
780     ///
781     /// [`chunks`]: #method.chunks
782     /// [`rchunks_exact`]: #method.rchunks_exact
783     #[stable(feature = "chunks_exact", since = "1.31.0")]
784     #[inline]
785     pub fn chunks_exact(&self, chunk_size: usize) -> ChunksExact<'_, T> {
786         assert!(chunk_size != 0);
787         let rem = self.len() % chunk_size;
788         let len = self.len() - rem;
789         let (fst, snd) = self.split_at(len);
790         ChunksExact { v: fst, rem: snd, chunk_size }
791     }
792
793     /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
794     /// beginning of the slice.
795     ///
796     /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
797     /// length of the slice, then the last up to `chunk_size-1` elements will be omitted and can be
798     /// retrieved from the `into_remainder` function of the iterator.
799     ///
800     /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
801     /// resulting code better than in the case of [`chunks_mut`].
802     ///
803     /// See [`chunks_mut`] for a variant of this iterator that also returns the remainder as a
804     /// smaller chunk, and [`rchunks_exact_mut`] for the same iterator but starting at the end of
805     /// the slice.
806     ///
807     /// # Panics
808     ///
809     /// Panics if `chunk_size` is 0.
810     ///
811     /// # Examples
812     ///
813     /// ```
814     /// let v = &mut [0, 0, 0, 0, 0];
815     /// let mut count = 1;
816     ///
817     /// for chunk in v.chunks_exact_mut(2) {
818     ///     for elem in chunk.iter_mut() {
819     ///         *elem += count;
820     ///     }
821     ///     count += 1;
822     /// }
823     /// assert_eq!(v, &[1, 1, 2, 2, 0]);
824     /// ```
825     ///
826     /// [`chunks_mut`]: #method.chunks_mut
827     /// [`rchunks_exact_mut`]: #method.rchunks_exact_mut
828     #[stable(feature = "chunks_exact", since = "1.31.0")]
829     #[inline]
830     pub fn chunks_exact_mut(&mut self, chunk_size: usize) -> ChunksExactMut<'_, T> {
831         assert!(chunk_size != 0);
832         let rem = self.len() % chunk_size;
833         let len = self.len() - rem;
834         let (fst, snd) = self.split_at_mut(len);
835         ChunksExactMut { v: fst, rem: snd, chunk_size }
836     }
837
838     /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end
839     /// of the slice.
840     ///
841     /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
842     /// slice, then the last chunk will not have length `chunk_size`.
843     ///
844     /// See [`rchunks_exact`] for a variant of this iterator that returns chunks of always exactly
845     /// `chunk_size` elements, and [`chunks`] for the same iterator but starting at the beginning
846     /// of the slice.
847     ///
848     /// # Panics
849     ///
850     /// Panics if `chunk_size` is 0.
851     ///
852     /// # Examples
853     ///
854     /// ```
855     /// let slice = ['l', 'o', 'r', 'e', 'm'];
856     /// let mut iter = slice.rchunks(2);
857     /// assert_eq!(iter.next().unwrap(), &['e', 'm']);
858     /// assert_eq!(iter.next().unwrap(), &['o', 'r']);
859     /// assert_eq!(iter.next().unwrap(), &['l']);
860     /// assert!(iter.next().is_none());
861     /// ```
862     ///
863     /// [`rchunks_exact`]: #method.rchunks_exact
864     /// [`chunks`]: #method.chunks
865     #[stable(feature = "rchunks", since = "1.31.0")]
866     #[inline]
867     pub fn rchunks(&self, chunk_size: usize) -> RChunks<'_, T> {
868         assert!(chunk_size != 0);
869         RChunks { v: self, chunk_size }
870     }
871
872     /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end
873     /// of the slice.
874     ///
875     /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
876     /// length of the slice, then the last chunk will not have length `chunk_size`.
877     ///
878     /// See [`rchunks_exact_mut`] for a variant of this iterator that returns chunks of always
879     /// exactly `chunk_size` elements, and [`chunks_mut`] for the same iterator but starting at the
880     /// beginning of the slice.
881     ///
882     /// # Panics
883     ///
884     /// Panics if `chunk_size` is 0.
885     ///
886     /// # Examples
887     ///
888     /// ```
889     /// let v = &mut [0, 0, 0, 0, 0];
890     /// let mut count = 1;
891     ///
892     /// for chunk in v.rchunks_mut(2) {
893     ///     for elem in chunk.iter_mut() {
894     ///         *elem += count;
895     ///     }
896     ///     count += 1;
897     /// }
898     /// assert_eq!(v, &[3, 2, 2, 1, 1]);
899     /// ```
900     ///
901     /// [`rchunks_exact_mut`]: #method.rchunks_exact_mut
902     /// [`chunks_mut`]: #method.chunks_mut
903     #[stable(feature = "rchunks", since = "1.31.0")]
904     #[inline]
905     pub fn rchunks_mut(&mut self, chunk_size: usize) -> RChunksMut<'_, T> {
906         assert!(chunk_size != 0);
907         RChunksMut { v: self, chunk_size }
908     }
909
910     /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the
911     /// end of the slice.
912     ///
913     /// The chunks are slices and do not overlap. If `chunk_size` does not divide the length of the
914     /// slice, then the last up to `chunk_size-1` elements will be omitted and can be retrieved
915     /// from the `remainder` function of the iterator.
916     ///
917     /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
918     /// resulting code better than in the case of [`chunks`].
919     ///
920     /// See [`rchunks`] for a variant of this iterator that also returns the remainder as a smaller
921     /// chunk, and [`chunks_exact`] for the same iterator but starting at the beginning of the
922     /// slice.
923     ///
924     /// # Panics
925     ///
926     /// Panics if `chunk_size` is 0.
927     ///
928     /// # Examples
929     ///
930     /// ```
931     /// let slice = ['l', 'o', 'r', 'e', 'm'];
932     /// let mut iter = slice.rchunks_exact(2);
933     /// assert_eq!(iter.next().unwrap(), &['e', 'm']);
934     /// assert_eq!(iter.next().unwrap(), &['o', 'r']);
935     /// assert!(iter.next().is_none());
936     /// assert_eq!(iter.remainder(), &['l']);
937     /// ```
938     ///
939     /// [`chunks`]: #method.chunks
940     /// [`rchunks`]: #method.rchunks
941     /// [`chunks_exact`]: #method.chunks_exact
942     #[stable(feature = "rchunks", since = "1.31.0")]
943     #[inline]
944     pub fn rchunks_exact(&self, chunk_size: usize) -> RChunksExact<'_, T> {
945         assert!(chunk_size != 0);
946         let rem = self.len() % chunk_size;
947         let (fst, snd) = self.split_at(rem);
948         RChunksExact { v: snd, rem: fst, chunk_size }
949     }
950
951     /// Returns an iterator over `chunk_size` elements of the slice at a time, starting at the end
952     /// of the slice.
953     ///
954     /// The chunks are mutable slices, and do not overlap. If `chunk_size` does not divide the
955     /// length of the slice, then the last up to `chunk_size-1` elements will be omitted and can be
956     /// retrieved from the `into_remainder` function of the iterator.
957     ///
958     /// Due to each chunk having exactly `chunk_size` elements, the compiler can often optimize the
959     /// resulting code better than in the case of [`chunks_mut`].
960     ///
961     /// See [`rchunks_mut`] for a variant of this iterator that also returns the remainder as a
962     /// smaller chunk, and [`chunks_exact_mut`] for the same iterator but starting at the beginning
963     /// of the slice.
964     ///
965     /// # Panics
966     ///
967     /// Panics if `chunk_size` is 0.
968     ///
969     /// # Examples
970     ///
971     /// ```
972     /// let v = &mut [0, 0, 0, 0, 0];
973     /// let mut count = 1;
974     ///
975     /// for chunk in v.rchunks_exact_mut(2) {
976     ///     for elem in chunk.iter_mut() {
977     ///         *elem += count;
978     ///     }
979     ///     count += 1;
980     /// }
981     /// assert_eq!(v, &[0, 2, 2, 1, 1]);
982     /// ```
983     ///
984     /// [`chunks_mut`]: #method.chunks_mut
985     /// [`rchunks_mut`]: #method.rchunks_mut
986     /// [`chunks_exact_mut`]: #method.chunks_exact_mut
987     #[stable(feature = "rchunks", since = "1.31.0")]
988     #[inline]
989     pub fn rchunks_exact_mut(&mut self, chunk_size: usize) -> RChunksExactMut<'_, T> {
990         assert!(chunk_size != 0);
991         let rem = self.len() % chunk_size;
992         let (fst, snd) = self.split_at_mut(rem);
993         RChunksExactMut { v: snd, rem: fst, chunk_size }
994     }
995
996     /// Divides one slice into two at an index.
997     ///
998     /// The first will contain all indices from `[0, mid)` (excluding
999     /// the index `mid` itself) and the second will contain all
1000     /// indices from `[mid, len)` (excluding the index `len` itself).
1001     ///
1002     /// # Panics
1003     ///
1004     /// Panics if `mid > len`.
1005     ///
1006     /// # Examples
1007     ///
1008     /// ```
1009     /// let v = [1, 2, 3, 4, 5, 6];
1010     ///
1011     /// {
1012     ///    let (left, right) = v.split_at(0);
1013     ///    assert!(left == []);
1014     ///    assert!(right == [1, 2, 3, 4, 5, 6]);
1015     /// }
1016     ///
1017     /// {
1018     ///     let (left, right) = v.split_at(2);
1019     ///     assert!(left == [1, 2]);
1020     ///     assert!(right == [3, 4, 5, 6]);
1021     /// }
1022     ///
1023     /// {
1024     ///     let (left, right) = v.split_at(6);
1025     ///     assert!(left == [1, 2, 3, 4, 5, 6]);
1026     ///     assert!(right == []);
1027     /// }
1028     /// ```
1029     #[stable(feature = "rust1", since = "1.0.0")]
1030     #[inline]
1031     pub fn split_at(&self, mid: usize) -> (&[T], &[T]) {
1032         (&self[..mid], &self[mid..])
1033     }
1034
1035     /// Divides one mutable slice into two at an index.
1036     ///
1037     /// The first will contain all indices from `[0, mid)` (excluding
1038     /// the index `mid` itself) and the second will contain all
1039     /// indices from `[mid, len)` (excluding the index `len` itself).
1040     ///
1041     /// # Panics
1042     ///
1043     /// Panics if `mid > len`.
1044     ///
1045     /// # Examples
1046     ///
1047     /// ```
1048     /// let mut v = [1, 0, 3, 0, 5, 6];
1049     /// // scoped to restrict the lifetime of the borrows
1050     /// {
1051     ///     let (left, right) = v.split_at_mut(2);
1052     ///     assert!(left == [1, 0]);
1053     ///     assert!(right == [3, 0, 5, 6]);
1054     ///     left[1] = 2;
1055     ///     right[1] = 4;
1056     /// }
1057     /// assert!(v == [1, 2, 3, 4, 5, 6]);
1058     /// ```
1059     #[stable(feature = "rust1", since = "1.0.0")]
1060     #[inline]
1061     pub fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
1062         let len = self.len();
1063         let ptr = self.as_mut_ptr();
1064
1065         unsafe {
1066             assert!(mid <= len);
1067
1068             (from_raw_parts_mut(ptr, mid), from_raw_parts_mut(ptr.add(mid), len - mid))
1069         }
1070     }
1071
1072     /// Returns an iterator over subslices separated by elements that match
1073     /// `pred`. The matched element is not contained in the subslices.
1074     ///
1075     /// # Examples
1076     ///
1077     /// ```
1078     /// let slice = [10, 40, 33, 20];
1079     /// let mut iter = slice.split(|num| num % 3 == 0);
1080     ///
1081     /// assert_eq!(iter.next().unwrap(), &[10, 40]);
1082     /// assert_eq!(iter.next().unwrap(), &[20]);
1083     /// assert!(iter.next().is_none());
1084     /// ```
1085     ///
1086     /// If the first element is matched, an empty slice will be the first item
1087     /// returned by the iterator. Similarly, if the last element in the slice
1088     /// is matched, an empty slice will be the last item returned by the
1089     /// iterator:
1090     ///
1091     /// ```
1092     /// let slice = [10, 40, 33];
1093     /// let mut iter = slice.split(|num| num % 3 == 0);
1094     ///
1095     /// assert_eq!(iter.next().unwrap(), &[10, 40]);
1096     /// assert_eq!(iter.next().unwrap(), &[]);
1097     /// assert!(iter.next().is_none());
1098     /// ```
1099     ///
1100     /// If two matched elements are directly adjacent, an empty slice will be
1101     /// present between them:
1102     ///
1103     /// ```
1104     /// let slice = [10, 6, 33, 20];
1105     /// let mut iter = slice.split(|num| num % 3 == 0);
1106     ///
1107     /// assert_eq!(iter.next().unwrap(), &[10]);
1108     /// assert_eq!(iter.next().unwrap(), &[]);
1109     /// assert_eq!(iter.next().unwrap(), &[20]);
1110     /// assert!(iter.next().is_none());
1111     /// ```
1112     #[stable(feature = "rust1", since = "1.0.0")]
1113     #[inline]
1114     pub fn split<F>(&self, pred: F) -> Split<'_, T, F>
1115     where
1116         F: FnMut(&T) -> bool,
1117     {
1118         Split { v: self, pred, finished: false }
1119     }
1120
1121     /// Returns an iterator over mutable subslices separated by elements that
1122     /// match `pred`. The matched element is not contained in the subslices.
1123     ///
1124     /// # Examples
1125     ///
1126     /// ```
1127     /// let mut v = [10, 40, 30, 20, 60, 50];
1128     ///
1129     /// for group in v.split_mut(|num| *num % 3 == 0) {
1130     ///     group[0] = 1;
1131     /// }
1132     /// assert_eq!(v, [1, 40, 30, 1, 60, 1]);
1133     /// ```
1134     #[stable(feature = "rust1", since = "1.0.0")]
1135     #[inline]
1136     pub fn split_mut<F>(&mut self, pred: F) -> SplitMut<'_, T, F>
1137     where
1138         F: FnMut(&T) -> bool,
1139     {
1140         SplitMut { v: self, pred, finished: false }
1141     }
1142
1143     /// Returns an iterator over subslices separated by elements that match
1144     /// `pred`. The matched element is contained in the end of the previous
1145     /// subslice as a terminator.
1146     ///
1147     /// # Examples
1148     ///
1149     /// ```
1150     /// #![feature(split_inclusive)]
1151     /// let slice = [10, 40, 33, 20];
1152     /// let mut iter = slice.split_inclusive(|num| num % 3 == 0);
1153     ///
1154     /// assert_eq!(iter.next().unwrap(), &[10, 40, 33]);
1155     /// assert_eq!(iter.next().unwrap(), &[20]);
1156     /// assert!(iter.next().is_none());
1157     /// ```
1158     ///
1159     /// If the last element of the slice is matched,
1160     /// that element will be considered the terminator of the preceding slice.
1161     /// That slice will be the last item returned by the iterator.
1162     ///
1163     /// ```
1164     /// #![feature(split_inclusive)]
1165     /// let slice = [3, 10, 40, 33];
1166     /// let mut iter = slice.split_inclusive(|num| num % 3 == 0);
1167     ///
1168     /// assert_eq!(iter.next().unwrap(), &[3]);
1169     /// assert_eq!(iter.next().unwrap(), &[10, 40, 33]);
1170     /// assert!(iter.next().is_none());
1171     /// ```
1172     #[unstable(feature = "split_inclusive", issue = "72360")]
1173     #[inline]
1174     pub fn split_inclusive<F>(&self, pred: F) -> SplitInclusive<'_, T, F>
1175     where
1176         F: FnMut(&T) -> bool,
1177     {
1178         SplitInclusive { v: self, pred, finished: false }
1179     }
1180
1181     /// Returns an iterator over mutable subslices separated by elements that
1182     /// match `pred`. The matched element is contained in the previous
1183     /// subslice as a terminator.
1184     ///
1185     /// # Examples
1186     ///
1187     /// ```
1188     /// #![feature(split_inclusive)]
1189     /// let mut v = [10, 40, 30, 20, 60, 50];
1190     ///
1191     /// for group in v.split_inclusive_mut(|num| *num % 3 == 0) {
1192     ///     let terminator_idx = group.len()-1;
1193     ///     group[terminator_idx] = 1;
1194     /// }
1195     /// assert_eq!(v, [10, 40, 1, 20, 1, 1]);
1196     /// ```
1197     #[unstable(feature = "split_inclusive", issue = "72360")]
1198     #[inline]
1199     pub fn split_inclusive_mut<F>(&mut self, pred: F) -> SplitInclusiveMut<'_, T, F>
1200     where
1201         F: FnMut(&T) -> bool,
1202     {
1203         SplitInclusiveMut { v: self, pred, finished: false }
1204     }
1205
1206     /// Returns an iterator over subslices separated by elements that match
1207     /// `pred`, starting at the end of the slice and working backwards.
1208     /// The matched element is not contained in the subslices.
1209     ///
1210     /// # Examples
1211     ///
1212     /// ```
1213     /// let slice = [11, 22, 33, 0, 44, 55];
1214     /// let mut iter = slice.rsplit(|num| *num == 0);
1215     ///
1216     /// assert_eq!(iter.next().unwrap(), &[44, 55]);
1217     /// assert_eq!(iter.next().unwrap(), &[11, 22, 33]);
1218     /// assert_eq!(iter.next(), None);
1219     /// ```
1220     ///
1221     /// As with `split()`, if the first or last element is matched, an empty
1222     /// slice will be the first (or last) item returned by the iterator.
1223     ///
1224     /// ```
1225     /// let v = &[0, 1, 1, 2, 3, 5, 8];
1226     /// let mut it = v.rsplit(|n| *n % 2 == 0);
1227     /// assert_eq!(it.next().unwrap(), &[]);
1228     /// assert_eq!(it.next().unwrap(), &[3, 5]);
1229     /// assert_eq!(it.next().unwrap(), &[1, 1]);
1230     /// assert_eq!(it.next().unwrap(), &[]);
1231     /// assert_eq!(it.next(), None);
1232     /// ```
1233     #[stable(feature = "slice_rsplit", since = "1.27.0")]
1234     #[inline]
1235     pub fn rsplit<F>(&self, pred: F) -> RSplit<'_, T, F>
1236     where
1237         F: FnMut(&T) -> bool,
1238     {
1239         RSplit { inner: self.split(pred) }
1240     }
1241
1242     /// Returns an iterator over mutable subslices separated by elements that
1243     /// match `pred`, starting at the end of the slice and working
1244     /// backwards. The matched element is not contained in the subslices.
1245     ///
1246     /// # Examples
1247     ///
1248     /// ```
1249     /// let mut v = [100, 400, 300, 200, 600, 500];
1250     ///
1251     /// let mut count = 0;
1252     /// for group in v.rsplit_mut(|num| *num % 3 == 0) {
1253     ///     count += 1;
1254     ///     group[0] = count;
1255     /// }
1256     /// assert_eq!(v, [3, 400, 300, 2, 600, 1]);
1257     /// ```
1258     ///
1259     #[stable(feature = "slice_rsplit", since = "1.27.0")]
1260     #[inline]
1261     pub fn rsplit_mut<F>(&mut self, pred: F) -> RSplitMut<'_, T, F>
1262     where
1263         F: FnMut(&T) -> bool,
1264     {
1265         RSplitMut { inner: self.split_mut(pred) }
1266     }
1267
1268     /// Returns an iterator over subslices separated by elements that match
1269     /// `pred`, limited to returning at most `n` items. The matched element is
1270     /// not contained in the subslices.
1271     ///
1272     /// The last element returned, if any, will contain the remainder of the
1273     /// slice.
1274     ///
1275     /// # Examples
1276     ///
1277     /// Print the slice split once by numbers divisible by 3 (i.e., `[10, 40]`,
1278     /// `[20, 60, 50]`):
1279     ///
1280     /// ```
1281     /// let v = [10, 40, 30, 20, 60, 50];
1282     ///
1283     /// for group in v.splitn(2, |num| *num % 3 == 0) {
1284     ///     println!("{:?}", group);
1285     /// }
1286     /// ```
1287     #[stable(feature = "rust1", since = "1.0.0")]
1288     #[inline]
1289     pub fn splitn<F>(&self, n: usize, pred: F) -> SplitN<'_, T, F>
1290     where
1291         F: FnMut(&T) -> bool,
1292     {
1293         SplitN { inner: GenericSplitN { iter: self.split(pred), count: n } }
1294     }
1295
1296     /// Returns an iterator over subslices separated by elements that match
1297     /// `pred`, limited to returning at most `n` items. The matched element is
1298     /// not contained in the subslices.
1299     ///
1300     /// The last element returned, if any, will contain the remainder of the
1301     /// slice.
1302     ///
1303     /// # Examples
1304     ///
1305     /// ```
1306     /// let mut v = [10, 40, 30, 20, 60, 50];
1307     ///
1308     /// for group in v.splitn_mut(2, |num| *num % 3 == 0) {
1309     ///     group[0] = 1;
1310     /// }
1311     /// assert_eq!(v, [1, 40, 30, 1, 60, 50]);
1312     /// ```
1313     #[stable(feature = "rust1", since = "1.0.0")]
1314     #[inline]
1315     pub fn splitn_mut<F>(&mut self, n: usize, pred: F) -> SplitNMut<'_, T, F>
1316     where
1317         F: FnMut(&T) -> bool,
1318     {
1319         SplitNMut { inner: GenericSplitN { iter: self.split_mut(pred), count: n } }
1320     }
1321
1322     /// Returns an iterator over subslices separated by elements that match
1323     /// `pred` limited to returning at most `n` items. This starts at the end of
1324     /// the slice and works backwards. The matched element is not contained in
1325     /// the subslices.
1326     ///
1327     /// The last element returned, if any, will contain the remainder of the
1328     /// slice.
1329     ///
1330     /// # Examples
1331     ///
1332     /// Print the slice split once, starting from the end, by numbers divisible
1333     /// by 3 (i.e., `[50]`, `[10, 40, 30, 20]`):
1334     ///
1335     /// ```
1336     /// let v = [10, 40, 30, 20, 60, 50];
1337     ///
1338     /// for group in v.rsplitn(2, |num| *num % 3 == 0) {
1339     ///     println!("{:?}", group);
1340     /// }
1341     /// ```
1342     #[stable(feature = "rust1", since = "1.0.0")]
1343     #[inline]
1344     pub fn rsplitn<F>(&self, n: usize, pred: F) -> RSplitN<'_, T, F>
1345     where
1346         F: FnMut(&T) -> bool,
1347     {
1348         RSplitN { inner: GenericSplitN { iter: self.rsplit(pred), count: n } }
1349     }
1350
1351     /// Returns an iterator over subslices separated by elements that match
1352     /// `pred` limited to returning at most `n` items. This starts at the end of
1353     /// the slice and works backwards. The matched element is not contained in
1354     /// the subslices.
1355     ///
1356     /// The last element returned, if any, will contain the remainder of the
1357     /// slice.
1358     ///
1359     /// # Examples
1360     ///
1361     /// ```
1362     /// let mut s = [10, 40, 30, 20, 60, 50];
1363     ///
1364     /// for group in s.rsplitn_mut(2, |num| *num % 3 == 0) {
1365     ///     group[0] = 1;
1366     /// }
1367     /// assert_eq!(s, [1, 40, 30, 20, 60, 1]);
1368     /// ```
1369     #[stable(feature = "rust1", since = "1.0.0")]
1370     #[inline]
1371     pub fn rsplitn_mut<F>(&mut self, n: usize, pred: F) -> RSplitNMut<'_, T, F>
1372     where
1373         F: FnMut(&T) -> bool,
1374     {
1375         RSplitNMut { inner: GenericSplitN { iter: self.rsplit_mut(pred), count: n } }
1376     }
1377
1378     /// Returns `true` if the slice contains an element with the given value.
1379     ///
1380     /// # Examples
1381     ///
1382     /// ```
1383     /// let v = [10, 40, 30];
1384     /// assert!(v.contains(&30));
1385     /// assert!(!v.contains(&50));
1386     /// ```
1387     ///
1388     /// If you do not have an `&T`, but just an `&U` such that `T: Borrow<U>`
1389     /// (e.g. `String: Borrow<str>`), you can use `iter().any`:
1390     ///
1391     /// ```
1392     /// let v = [String::from("hello"), String::from("world")]; // slice of `String`
1393     /// assert!(v.iter().any(|e| e == "hello")); // search with `&str`
1394     /// assert!(!v.iter().any(|e| e == "hi"));
1395     /// ```
1396     #[stable(feature = "rust1", since = "1.0.0")]
1397     pub fn contains(&self, x: &T) -> bool
1398     where
1399         T: PartialEq,
1400     {
1401         x.slice_contains(self)
1402     }
1403
1404     /// Returns `true` if `needle` is a prefix of the slice.
1405     ///
1406     /// # Examples
1407     ///
1408     /// ```
1409     /// let v = [10, 40, 30];
1410     /// assert!(v.starts_with(&[10]));
1411     /// assert!(v.starts_with(&[10, 40]));
1412     /// assert!(!v.starts_with(&[50]));
1413     /// assert!(!v.starts_with(&[10, 50]));
1414     /// ```
1415     ///
1416     /// Always returns `true` if `needle` is an empty slice:
1417     ///
1418     /// ```
1419     /// let v = &[10, 40, 30];
1420     /// assert!(v.starts_with(&[]));
1421     /// let v: &[u8] = &[];
1422     /// assert!(v.starts_with(&[]));
1423     /// ```
1424     #[stable(feature = "rust1", since = "1.0.0")]
1425     pub fn starts_with(&self, needle: &[T]) -> bool
1426     where
1427         T: PartialEq,
1428     {
1429         let n = needle.len();
1430         self.len() >= n && needle == &self[..n]
1431     }
1432
1433     /// Returns `true` if `needle` is a suffix of the slice.
1434     ///
1435     /// # Examples
1436     ///
1437     /// ```
1438     /// let v = [10, 40, 30];
1439     /// assert!(v.ends_with(&[30]));
1440     /// assert!(v.ends_with(&[40, 30]));
1441     /// assert!(!v.ends_with(&[50]));
1442     /// assert!(!v.ends_with(&[50, 30]));
1443     /// ```
1444     ///
1445     /// Always returns `true` if `needle` is an empty slice:
1446     ///
1447     /// ```
1448     /// let v = &[10, 40, 30];
1449     /// assert!(v.ends_with(&[]));
1450     /// let v: &[u8] = &[];
1451     /// assert!(v.ends_with(&[]));
1452     /// ```
1453     #[stable(feature = "rust1", since = "1.0.0")]
1454     pub fn ends_with(&self, needle: &[T]) -> bool
1455     where
1456         T: PartialEq,
1457     {
1458         let (m, n) = (self.len(), needle.len());
1459         m >= n && needle == &self[m - n..]
1460     }
1461
1462     /// Binary searches this sorted slice for a given element.
1463     ///
1464     /// If the value is found then [`Result::Ok`] is returned, containing the
1465     /// index of the matching element. If there are multiple matches, then any
1466     /// one of the matches could be returned. If the value is not found then
1467     /// [`Result::Err`] is returned, containing the index where a matching
1468     /// element could be inserted while maintaining sorted order.
1469     ///
1470     /// # Examples
1471     ///
1472     /// Looks up a series of four elements. The first is found, with a
1473     /// uniquely determined position; the second and third are not
1474     /// found; the fourth could match any position in `[1, 4]`.
1475     ///
1476     /// ```
1477     /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
1478     ///
1479     /// assert_eq!(s.binary_search(&13),  Ok(9));
1480     /// assert_eq!(s.binary_search(&4),   Err(7));
1481     /// assert_eq!(s.binary_search(&100), Err(13));
1482     /// let r = s.binary_search(&1);
1483     /// assert!(match r { Ok(1..=4) => true, _ => false, });
1484     /// ```
1485     ///
1486     /// If you want to insert an item to a sorted vector, while maintaining
1487     /// sort order:
1488     ///
1489     /// ```
1490     /// let mut s = vec![0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
1491     /// let num = 42;
1492     /// let idx = s.binary_search(&num).unwrap_or_else(|x| x);
1493     /// s.insert(idx, num);
1494     /// assert_eq!(s, [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 42, 55]);
1495     /// ```
1496     #[stable(feature = "rust1", since = "1.0.0")]
1497     pub fn binary_search(&self, x: &T) -> Result<usize, usize>
1498     where
1499         T: Ord,
1500     {
1501         self.binary_search_by(|p| p.cmp(x))
1502     }
1503
1504     /// Binary searches this sorted slice with a comparator function.
1505     ///
1506     /// The comparator function should implement an order consistent
1507     /// with the sort order of the underlying slice, returning an
1508     /// order code that indicates whether its argument is `Less`,
1509     /// `Equal` or `Greater` the desired target.
1510     ///
1511     /// If the value is found then [`Result::Ok`] is returned, containing the
1512     /// index of the matching element. If there are multiple matches, then any
1513     /// one of the matches could be returned. If the value is not found then
1514     /// [`Result::Err`] is returned, containing the index where a matching
1515     /// element could be inserted while maintaining sorted order.
1516     ///
1517     /// # Examples
1518     ///
1519     /// Looks up a series of four elements. The first is found, with a
1520     /// uniquely determined position; the second and third are not
1521     /// found; the fourth could match any position in `[1, 4]`.
1522     ///
1523     /// ```
1524     /// let s = [0, 1, 1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55];
1525     ///
1526     /// let seek = 13;
1527     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Ok(9));
1528     /// let seek = 4;
1529     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(7));
1530     /// let seek = 100;
1531     /// assert_eq!(s.binary_search_by(|probe| probe.cmp(&seek)), Err(13));
1532     /// let seek = 1;
1533     /// let r = s.binary_search_by(|probe| probe.cmp(&seek));
1534     /// assert!(match r { Ok(1..=4) => true, _ => false, });
1535     /// ```
1536     #[stable(feature = "rust1", since = "1.0.0")]
1537     #[inline]
1538     pub fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
1539     where
1540         F: FnMut(&'a T) -> Ordering,
1541     {
1542         let s = self;
1543         let mut size = s.len();
1544         if size == 0 {
1545             return Err(0);
1546         }
1547         let mut base = 0usize;
1548         while size > 1 {
1549             let half = size / 2;
1550             let mid = base + half;
1551             // mid is always in [0, size), that means mid is >= 0 and < size.
1552             // mid >= 0: by definition
1553             // mid < size: mid = size / 2 + size / 4 + size / 8 ...
1554             let cmp = f(unsafe { s.get_unchecked(mid) });
1555             base = if cmp == Greater { base } else { mid };
1556             size -= half;
1557         }
1558         // base is always in [0, size) because base <= mid.
1559         let cmp = f(unsafe { s.get_unchecked(base) });
1560         if cmp == Equal { Ok(base) } else { Err(base + (cmp == Less) as usize) }
1561     }
1562
1563     /// Binary searches this sorted slice with a key extraction function.
1564     ///
1565     /// Assumes that the slice is sorted by the key, for instance with
1566     /// [`sort_by_key`] using the same key extraction function.
1567     ///
1568     /// If the value is found then [`Result::Ok`] is returned, containing the
1569     /// index of the matching element. If there are multiple matches, then any
1570     /// one of the matches could be returned. If the value is not found then
1571     /// [`Result::Err`] is returned, containing the index where a matching
1572     /// element could be inserted while maintaining sorted order.
1573     ///
1574     /// [`sort_by_key`]: #method.sort_by_key
1575     ///
1576     /// # Examples
1577     ///
1578     /// Looks up a series of four elements in a slice of pairs sorted by
1579     /// their second elements. The first is found, with a uniquely
1580     /// determined position; the second and third are not found; the
1581     /// fourth could match any position in `[1, 4]`.
1582     ///
1583     /// ```
1584     /// let s = [(0, 0), (2, 1), (4, 1), (5, 1), (3, 1),
1585     ///          (1, 2), (2, 3), (4, 5), (5, 8), (3, 13),
1586     ///          (1, 21), (2, 34), (4, 55)];
1587     ///
1588     /// assert_eq!(s.binary_search_by_key(&13, |&(a,b)| b),  Ok(9));
1589     /// assert_eq!(s.binary_search_by_key(&4, |&(a,b)| b),   Err(7));
1590     /// assert_eq!(s.binary_search_by_key(&100, |&(a,b)| b), Err(13));
1591     /// let r = s.binary_search_by_key(&1, |&(a,b)| b);
1592     /// assert!(match r { Ok(1..=4) => true, _ => false, });
1593     /// ```
1594     #[stable(feature = "slice_binary_search_by_key", since = "1.10.0")]
1595     #[inline]
1596     pub fn binary_search_by_key<'a, B, F>(&'a self, b: &B, mut f: F) -> Result<usize, usize>
1597     where
1598         F: FnMut(&'a T) -> B,
1599         B: Ord,
1600     {
1601         self.binary_search_by(|k| f(k).cmp(b))
1602     }
1603
1604     /// Sorts the slice, but may not preserve the order of equal elements.
1605     ///
1606     /// This sort is unstable (i.e., may reorder equal elements), in-place
1607     /// (i.e., does not allocate), and `O(n * log(n))` worst-case.
1608     ///
1609     /// # Current implementation
1610     ///
1611     /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
1612     /// which combines the fast average case of randomized quicksort with the fast worst case of
1613     /// heapsort, while achieving linear time on slices with certain patterns. It uses some
1614     /// randomization to avoid degenerate cases, but with a fixed seed to always provide
1615     /// deterministic behavior.
1616     ///
1617     /// It is typically faster than stable sorting, except in a few special cases, e.g., when the
1618     /// slice consists of several concatenated sorted sequences.
1619     ///
1620     /// # Examples
1621     ///
1622     /// ```
1623     /// let mut v = [-5, 4, 1, -3, 2];
1624     ///
1625     /// v.sort_unstable();
1626     /// assert!(v == [-5, -3, 1, 2, 4]);
1627     /// ```
1628     ///
1629     /// [pdqsort]: https://github.com/orlp/pdqsort
1630     #[stable(feature = "sort_unstable", since = "1.20.0")]
1631     #[inline]
1632     pub fn sort_unstable(&mut self)
1633     where
1634         T: Ord,
1635     {
1636         sort::quicksort(self, |a, b| a.lt(b));
1637     }
1638
1639     /// Sorts the slice with a comparator function, but may not preserve the order of equal
1640     /// elements.
1641     ///
1642     /// This sort is unstable (i.e., may reorder equal elements), in-place
1643     /// (i.e., does not allocate), and `O(n * log(n))` worst-case.
1644     ///
1645     /// The comparator function must define a total ordering for the elements in the slice. If
1646     /// the ordering is not total, the order of the elements is unspecified. An order is a
1647     /// total order if it is (for all a, b and c):
1648     ///
1649     /// * total and antisymmetric: exactly one of a < b, a == b or a > b is true; and
1650     /// * transitive, a < b and b < c implies a < c. The same must hold for both == and >.
1651     ///
1652     /// For example, while [`f64`] doesn't implement [`Ord`] because `NaN != NaN`, we can use
1653     /// `partial_cmp` as our sort function when we know the slice doesn't contain a `NaN`.
1654     ///
1655     /// ```
1656     /// let mut floats = [5f64, 4.0, 1.0, 3.0, 2.0];
1657     /// floats.sort_unstable_by(|a, b| a.partial_cmp(b).unwrap());
1658     /// assert_eq!(floats, [1.0, 2.0, 3.0, 4.0, 5.0]);
1659     /// ```
1660     ///
1661     /// # Current implementation
1662     ///
1663     /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
1664     /// which combines the fast average case of randomized quicksort with the fast worst case of
1665     /// heapsort, while achieving linear time on slices with certain patterns. It uses some
1666     /// randomization to avoid degenerate cases, but with a fixed seed to always provide
1667     /// deterministic behavior.
1668     ///
1669     /// It is typically faster than stable sorting, except in a few special cases, e.g., when the
1670     /// slice consists of several concatenated sorted sequences.
1671     ///
1672     /// # Examples
1673     ///
1674     /// ```
1675     /// let mut v = [5, 4, 1, 3, 2];
1676     /// v.sort_unstable_by(|a, b| a.cmp(b));
1677     /// assert!(v == [1, 2, 3, 4, 5]);
1678     ///
1679     /// // reverse sorting
1680     /// v.sort_unstable_by(|a, b| b.cmp(a));
1681     /// assert!(v == [5, 4, 3, 2, 1]);
1682     /// ```
1683     ///
1684     /// [pdqsort]: https://github.com/orlp/pdqsort
1685     #[stable(feature = "sort_unstable", since = "1.20.0")]
1686     #[inline]
1687     pub fn sort_unstable_by<F>(&mut self, mut compare: F)
1688     where
1689         F: FnMut(&T, &T) -> Ordering,
1690     {
1691         sort::quicksort(self, |a, b| compare(a, b) == Ordering::Less);
1692     }
1693
1694     /// Sorts the slice with a key extraction function, but may not preserve the order of equal
1695     /// elements.
1696     ///
1697     /// This sort is unstable (i.e., may reorder equal elements), in-place
1698     /// (i.e., does not allocate), and `O(m * n * log(n))` worst-case, where the key function is
1699     /// `O(m)`.
1700     ///
1701     /// # Current implementation
1702     ///
1703     /// The current algorithm is based on [pattern-defeating quicksort][pdqsort] by Orson Peters,
1704     /// which combines the fast average case of randomized quicksort with the fast worst case of
1705     /// heapsort, while achieving linear time on slices with certain patterns. It uses some
1706     /// randomization to avoid degenerate cases, but with a fixed seed to always provide
1707     /// deterministic behavior.
1708     ///
1709     /// Due to its key calling strategy, [`sort_unstable_by_key`](#method.sort_unstable_by_key)
1710     /// is likely to be slower than [`sort_by_cached_key`](#method.sort_by_cached_key) in
1711     /// cases where the key function is expensive.
1712     ///
1713     /// # Examples
1714     ///
1715     /// ```
1716     /// let mut v = [-5i32, 4, 1, -3, 2];
1717     ///
1718     /// v.sort_unstable_by_key(|k| k.abs());
1719     /// assert!(v == [1, 2, -3, 4, -5]);
1720     /// ```
1721     ///
1722     /// [pdqsort]: https://github.com/orlp/pdqsort
1723     #[stable(feature = "sort_unstable", since = "1.20.0")]
1724     #[inline]
1725     pub fn sort_unstable_by_key<K, F>(&mut self, mut f: F)
1726     where
1727         F: FnMut(&T) -> K,
1728         K: Ord,
1729     {
1730         sort::quicksort(self, |a, b| f(a).lt(&f(b)));
1731     }
1732
1733     /// Reorder the slice such that the element at `index` is at its final sorted position.
1734     ///
1735     /// This reordering has the additional property that any value at position `i < index` will be
1736     /// less than or equal to any value at a position `j > index`. Additionally, this reordering is
1737     /// unstable (i.e. any number of equal elements may end up at position `index`), in-place
1738     /// (i.e. does not allocate), and `O(n)` worst-case. This function is also/ known as "kth
1739     /// element" in other libraries. It returns a triplet of the following values: all elements less
1740     /// than the one at the given index, the value at the given index, and all elements greater than
1741     /// the one at the given index.
1742     ///
1743     /// # Current implementation
1744     ///
1745     /// The current algorithm is based on the quickselect portion of the same quicksort algorithm
1746     /// used for [`sort_unstable`].
1747     ///
1748     /// [`sort_unstable`]: #method.sort_unstable
1749     ///
1750     /// # Panics
1751     ///
1752     /// Panics when `index >= len()`, meaning it always panics on empty slices.
1753     ///
1754     /// # Examples
1755     ///
1756     /// ```
1757     /// #![feature(slice_partition_at_index)]
1758     ///
1759     /// let mut v = [-5i32, 4, 1, -3, 2];
1760     ///
1761     /// // Find the median
1762     /// v.partition_at_index(2);
1763     ///
1764     /// // We are only guaranteed the slice will be one of the following, based on the way we sort
1765     /// // about the specified index.
1766     /// assert!(v == [-3, -5, 1, 2, 4] ||
1767     ///         v == [-5, -3, 1, 2, 4] ||
1768     ///         v == [-3, -5, 1, 4, 2] ||
1769     ///         v == [-5, -3, 1, 4, 2]);
1770     /// ```
1771     #[unstable(feature = "slice_partition_at_index", issue = "55300")]
1772     #[inline]
1773     pub fn partition_at_index(&mut self, index: usize) -> (&mut [T], &mut T, &mut [T])
1774     where
1775         T: Ord,
1776     {
1777         let mut f = |a: &T, b: &T| a.lt(b);
1778         sort::partition_at_index(self, index, &mut f)
1779     }
1780
1781     /// Reorder the slice with a comparator function such that the element at `index` is at its
1782     /// final sorted position.
1783     ///
1784     /// This reordering has the additional property that any value at position `i < index` will be
1785     /// less than or equal to any value at a position `j > index` using the comparator function.
1786     /// Additionally, this reordering is unstable (i.e. any number of equal elements may end up at
1787     /// position `index`), in-place (i.e. does not allocate), and `O(n)` worst-case. This function
1788     /// is also known as "kth element" in other libraries. It returns a triplet of the following
1789     /// values: all elements less than the one at the given index, the value at the given index,
1790     /// and all elements greater than the one at the given index, using the provided comparator
1791     /// function.
1792     ///
1793     /// # Current implementation
1794     ///
1795     /// The current algorithm is based on the quickselect portion of the same quicksort algorithm
1796     /// used for [`sort_unstable`].
1797     ///
1798     /// [`sort_unstable`]: #method.sort_unstable
1799     ///
1800     /// # Panics
1801     ///
1802     /// Panics when `index >= len()`, meaning it always panics on empty slices.
1803     ///
1804     /// # Examples
1805     ///
1806     /// ```
1807     /// #![feature(slice_partition_at_index)]
1808     ///
1809     /// let mut v = [-5i32, 4, 1, -3, 2];
1810     ///
1811     /// // Find the median as if the slice were sorted in descending order.
1812     /// v.partition_at_index_by(2, |a, b| b.cmp(a));
1813     ///
1814     /// // We are only guaranteed the slice will be one of the following, based on the way we sort
1815     /// // about the specified index.
1816     /// assert!(v == [2, 4, 1, -5, -3] ||
1817     ///         v == [2, 4, 1, -3, -5] ||
1818     ///         v == [4, 2, 1, -5, -3] ||
1819     ///         v == [4, 2, 1, -3, -5]);
1820     /// ```
1821     #[unstable(feature = "slice_partition_at_index", issue = "55300")]
1822     #[inline]
1823     pub fn partition_at_index_by<F>(
1824         &mut self,
1825         index: usize,
1826         mut compare: F,
1827     ) -> (&mut [T], &mut T, &mut [T])
1828     where
1829         F: FnMut(&T, &T) -> Ordering,
1830     {
1831         let mut f = |a: &T, b: &T| compare(a, b) == Less;
1832         sort::partition_at_index(self, index, &mut f)
1833     }
1834
1835     /// Reorder the slice with a key extraction function such that the element at `index` is at its
1836     /// final sorted position.
1837     ///
1838     /// This reordering has the additional property that any value at position `i < index` will be
1839     /// less than or equal to any value at a position `j > index` using the key extraction function.
1840     /// Additionally, this reordering is unstable (i.e. any number of equal elements may end up at
1841     /// position `index`), in-place (i.e. does not allocate), and `O(n)` worst-case. This function
1842     /// is also known as "kth element" in other libraries. It returns a triplet of the following
1843     /// values: all elements less than the one at the given index, the value at the given index, and
1844     /// all elements greater than the one at the given index, using the provided key extraction
1845     /// function.
1846     ///
1847     /// # Current implementation
1848     ///
1849     /// The current algorithm is based on the quickselect portion of the same quicksort algorithm
1850     /// used for [`sort_unstable`].
1851     ///
1852     /// [`sort_unstable`]: #method.sort_unstable
1853     ///
1854     /// # Panics
1855     ///
1856     /// Panics when `index >= len()`, meaning it always panics on empty slices.
1857     ///
1858     /// # Examples
1859     ///
1860     /// ```
1861     /// #![feature(slice_partition_at_index)]
1862     ///
1863     /// let mut v = [-5i32, 4, 1, -3, 2];
1864     ///
1865     /// // Return the median as if the array were sorted according to absolute value.
1866     /// v.partition_at_index_by_key(2, |a| a.abs());
1867     ///
1868     /// // We are only guaranteed the slice will be one of the following, based on the way we sort
1869     /// // about the specified index.
1870     /// assert!(v == [1, 2, -3, 4, -5] ||
1871     ///         v == [1, 2, -3, -5, 4] ||
1872     ///         v == [2, 1, -3, 4, -5] ||
1873     ///         v == [2, 1, -3, -5, 4]);
1874     /// ```
1875     #[unstable(feature = "slice_partition_at_index", issue = "55300")]
1876     #[inline]
1877     pub fn partition_at_index_by_key<K, F>(
1878         &mut self,
1879         index: usize,
1880         mut f: F,
1881     ) -> (&mut [T], &mut T, &mut [T])
1882     where
1883         F: FnMut(&T) -> K,
1884         K: Ord,
1885     {
1886         let mut g = |a: &T, b: &T| f(a).lt(&f(b));
1887         sort::partition_at_index(self, index, &mut g)
1888     }
1889
1890     /// Moves all consecutive repeated elements to the end of the slice according to the
1891     /// [`PartialEq`] trait implementation.
1892     ///
1893     /// Returns two slices. The first contains no consecutive repeated elements.
1894     /// The second contains all the duplicates in no specified order.
1895     ///
1896     /// If the slice is sorted, the first returned slice contains no duplicates.
1897     ///
1898     /// # Examples
1899     ///
1900     /// ```
1901     /// #![feature(slice_partition_dedup)]
1902     ///
1903     /// let mut slice = [1, 2, 2, 3, 3, 2, 1, 1];
1904     ///
1905     /// let (dedup, duplicates) = slice.partition_dedup();
1906     ///
1907     /// assert_eq!(dedup, [1, 2, 3, 2, 1]);
1908     /// assert_eq!(duplicates, [2, 3, 1]);
1909     /// ```
1910     #[unstable(feature = "slice_partition_dedup", issue = "54279")]
1911     #[inline]
1912     pub fn partition_dedup(&mut self) -> (&mut [T], &mut [T])
1913     where
1914         T: PartialEq,
1915     {
1916         self.partition_dedup_by(|a, b| a == b)
1917     }
1918
1919     /// Moves all but the first of consecutive elements to the end of the slice satisfying
1920     /// a given equality relation.
1921     ///
1922     /// Returns two slices. The first contains no consecutive repeated elements.
1923     /// The second contains all the duplicates in no specified order.
1924     ///
1925     /// The `same_bucket` function is passed references to two elements from the slice and
1926     /// must determine if the elements compare equal. The elements are passed in opposite order
1927     /// from their order in the slice, so if `same_bucket(a, b)` returns `true`, `a` is moved
1928     /// at the end of the slice.
1929     ///
1930     /// If the slice is sorted, the first returned slice contains no duplicates.
1931     ///
1932     /// # Examples
1933     ///
1934     /// ```
1935     /// #![feature(slice_partition_dedup)]
1936     ///
1937     /// let mut slice = ["foo", "Foo", "BAZ", "Bar", "bar", "baz", "BAZ"];
1938     ///
1939     /// let (dedup, duplicates) = slice.partition_dedup_by(|a, b| a.eq_ignore_ascii_case(b));
1940     ///
1941     /// assert_eq!(dedup, ["foo", "BAZ", "Bar", "baz"]);
1942     /// assert_eq!(duplicates, ["bar", "Foo", "BAZ"]);
1943     /// ```
1944     #[unstable(feature = "slice_partition_dedup", issue = "54279")]
1945     #[inline]
1946     pub fn partition_dedup_by<F>(&mut self, mut same_bucket: F) -> (&mut [T], &mut [T])
1947     where
1948         F: FnMut(&mut T, &mut T) -> bool,
1949     {
1950         // Although we have a mutable reference to `self`, we cannot make
1951         // *arbitrary* changes. The `same_bucket` calls could panic, so we
1952         // must ensure that the slice is in a valid state at all times.
1953         //
1954         // The way that we handle this is by using swaps; we iterate
1955         // over all the elements, swapping as we go so that at the end
1956         // the elements we wish to keep are in the front, and those we
1957         // wish to reject are at the back. We can then split the slice.
1958         // This operation is still `O(n)`.
1959         //
1960         // Example: We start in this state, where `r` represents "next
1961         // read" and `w` represents "next_write`.
1962         //
1963         //           r
1964         //     +---+---+---+---+---+---+
1965         //     | 0 | 1 | 1 | 2 | 3 | 3 |
1966         //     +---+---+---+---+---+---+
1967         //           w
1968         //
1969         // Comparing self[r] against self[w-1], this is not a duplicate, so
1970         // we swap self[r] and self[w] (no effect as r==w) and then increment both
1971         // r and w, leaving us with:
1972         //
1973         //               r
1974         //     +---+---+---+---+---+---+
1975         //     | 0 | 1 | 1 | 2 | 3 | 3 |
1976         //     +---+---+---+---+---+---+
1977         //               w
1978         //
1979         // Comparing self[r] against self[w-1], this value is a duplicate,
1980         // so we increment `r` but leave everything else unchanged:
1981         //
1982         //                   r
1983         //     +---+---+---+---+---+---+
1984         //     | 0 | 1 | 1 | 2 | 3 | 3 |
1985         //     +---+---+---+---+---+---+
1986         //               w
1987         //
1988         // Comparing self[r] against self[w-1], this is not a duplicate,
1989         // so swap self[r] and self[w] and advance r and w:
1990         //
1991         //                       r
1992         //     +---+---+---+---+---+---+
1993         //     | 0 | 1 | 2 | 1 | 3 | 3 |
1994         //     +---+---+---+---+---+---+
1995         //                   w
1996         //
1997         // Not a duplicate, repeat:
1998         //
1999         //                           r
2000         //     +---+---+---+---+---+---+
2001         //     | 0 | 1 | 2 | 3 | 1 | 3 |
2002         //     +---+---+---+---+---+---+
2003         //                       w
2004         //
2005         // Duplicate, advance r. End of slice. Split at w.
2006
2007         let len = self.len();
2008         if len <= 1 {
2009             return (self, &mut []);
2010         }
2011
2012         let ptr = self.as_mut_ptr();
2013         let mut next_read: usize = 1;
2014         let mut next_write: usize = 1;
2015
2016         unsafe {
2017             // Avoid bounds checks by using raw pointers.
2018             while next_read < len {
2019                 let ptr_read = ptr.add(next_read);
2020                 let prev_ptr_write = ptr.add(next_write - 1);
2021                 if !same_bucket(&mut *ptr_read, &mut *prev_ptr_write) {
2022                     if next_read != next_write {
2023                         let ptr_write = prev_ptr_write.offset(1);
2024                         mem::swap(&mut *ptr_read, &mut *ptr_write);
2025                     }
2026                     next_write += 1;
2027                 }
2028                 next_read += 1;
2029             }
2030         }
2031
2032         self.split_at_mut(next_write)
2033     }
2034
2035     /// Moves all but the first of consecutive elements to the end of the slice that resolve
2036     /// to the same key.
2037     ///
2038     /// Returns two slices. The first contains no consecutive repeated elements.
2039     /// The second contains all the duplicates in no specified order.
2040     ///
2041     /// If the slice is sorted, the first returned slice contains no duplicates.
2042     ///
2043     /// # Examples
2044     ///
2045     /// ```
2046     /// #![feature(slice_partition_dedup)]
2047     ///
2048     /// let mut slice = [10, 20, 21, 30, 30, 20, 11, 13];
2049     ///
2050     /// let (dedup, duplicates) = slice.partition_dedup_by_key(|i| *i / 10);
2051     ///
2052     /// assert_eq!(dedup, [10, 20, 30, 20, 11]);
2053     /// assert_eq!(duplicates, [21, 30, 13]);
2054     /// ```
2055     #[unstable(feature = "slice_partition_dedup", issue = "54279")]
2056     #[inline]
2057     pub fn partition_dedup_by_key<K, F>(&mut self, mut key: F) -> (&mut [T], &mut [T])
2058     where
2059         F: FnMut(&mut T) -> K,
2060         K: PartialEq,
2061     {
2062         self.partition_dedup_by(|a, b| key(a) == key(b))
2063     }
2064
2065     /// Rotates the slice in-place such that the first `mid` elements of the
2066     /// slice move to the end while the last `self.len() - mid` elements move to
2067     /// the front. After calling `rotate_left`, the element previously at index
2068     /// `mid` will become the first element in the slice.
2069     ///
2070     /// # Panics
2071     ///
2072     /// This function will panic if `mid` is greater than the length of the
2073     /// slice. Note that `mid == self.len()` does _not_ panic and is a no-op
2074     /// rotation.
2075     ///
2076     /// # Complexity
2077     ///
2078     /// Takes linear (in `self.len()`) time.
2079     ///
2080     /// # Examples
2081     ///
2082     /// ```
2083     /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
2084     /// a.rotate_left(2);
2085     /// assert_eq!(a, ['c', 'd', 'e', 'f', 'a', 'b']);
2086     /// ```
2087     ///
2088     /// Rotating a subslice:
2089     ///
2090     /// ```
2091     /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
2092     /// a[1..5].rotate_left(1);
2093     /// assert_eq!(a, ['a', 'c', 'd', 'e', 'b', 'f']);
2094     /// ```
2095     #[stable(feature = "slice_rotate", since = "1.26.0")]
2096     pub fn rotate_left(&mut self, mid: usize) {
2097         assert!(mid <= self.len());
2098         let k = self.len() - mid;
2099
2100         unsafe {
2101             let p = self.as_mut_ptr();
2102             rotate::ptr_rotate(mid, p.add(mid), k);
2103         }
2104     }
2105
2106     /// Rotates the slice in-place such that the first `self.len() - k`
2107     /// elements of the slice move to the end while the last `k` elements move
2108     /// to the front. After calling `rotate_right`, the element previously at
2109     /// index `self.len() - k` will become the first element in the slice.
2110     ///
2111     /// # Panics
2112     ///
2113     /// This function will panic if `k` is greater than the length of the
2114     /// slice. Note that `k == self.len()` does _not_ panic and is a no-op
2115     /// rotation.
2116     ///
2117     /// # Complexity
2118     ///
2119     /// Takes linear (in `self.len()`) time.
2120     ///
2121     /// # Examples
2122     ///
2123     /// ```
2124     /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
2125     /// a.rotate_right(2);
2126     /// assert_eq!(a, ['e', 'f', 'a', 'b', 'c', 'd']);
2127     /// ```
2128     ///
2129     /// Rotate a subslice:
2130     ///
2131     /// ```
2132     /// let mut a = ['a', 'b', 'c', 'd', 'e', 'f'];
2133     /// a[1..5].rotate_right(1);
2134     /// assert_eq!(a, ['a', 'e', 'b', 'c', 'd', 'f']);
2135     /// ```
2136     #[stable(feature = "slice_rotate", since = "1.26.0")]
2137     pub fn rotate_right(&mut self, k: usize) {
2138         assert!(k <= self.len());
2139         let mid = self.len() - k;
2140
2141         unsafe {
2142             let p = self.as_mut_ptr();
2143             rotate::ptr_rotate(mid, p.add(mid), k);
2144         }
2145     }
2146
2147     /// Fills `self` with elements by cloning `value`.
2148     ///
2149     /// # Examples
2150     ///
2151     /// ```
2152     /// #![feature(slice_fill)]
2153     ///
2154     /// let mut buf = vec![0; 10];
2155     /// buf.fill(1);
2156     /// assert_eq!(buf, vec![1; 10]);
2157     /// ```
2158     #[unstable(feature = "slice_fill", issue = "70758")]
2159     pub fn fill(&mut self, value: T)
2160     where
2161         T: Clone,
2162     {
2163         if let Some((last, elems)) = self.split_last_mut() {
2164             for el in elems {
2165                 el.clone_from(&value);
2166             }
2167
2168             *last = value
2169         }
2170     }
2171
2172     /// Copies the elements from `src` into `self`.
2173     ///
2174     /// The length of `src` must be the same as `self`.
2175     ///
2176     /// If `T` implements `Copy`, it can be more performant to use
2177     /// [`copy_from_slice`].
2178     ///
2179     /// # Panics
2180     ///
2181     /// This function will panic if the two slices have different lengths.
2182     ///
2183     /// # Examples
2184     ///
2185     /// Cloning two elements from a slice into another:
2186     ///
2187     /// ```
2188     /// let src = [1, 2, 3, 4];
2189     /// let mut dst = [0, 0];
2190     ///
2191     /// // Because the slices have to be the same length,
2192     /// // we slice the source slice from four elements
2193     /// // to two. It will panic if we don't do this.
2194     /// dst.clone_from_slice(&src[2..]);
2195     ///
2196     /// assert_eq!(src, [1, 2, 3, 4]);
2197     /// assert_eq!(dst, [3, 4]);
2198     /// ```
2199     ///
2200     /// Rust enforces that there can only be one mutable reference with no
2201     /// immutable references to a particular piece of data in a particular
2202     /// scope. Because of this, attempting to use `clone_from_slice` on a
2203     /// single slice will result in a compile failure:
2204     ///
2205     /// ```compile_fail
2206     /// let mut slice = [1, 2, 3, 4, 5];
2207     ///
2208     /// slice[..2].clone_from_slice(&slice[3..]); // compile fail!
2209     /// ```
2210     ///
2211     /// To work around this, we can use [`split_at_mut`] to create two distinct
2212     /// sub-slices from a slice:
2213     ///
2214     /// ```
2215     /// let mut slice = [1, 2, 3, 4, 5];
2216     ///
2217     /// {
2218     ///     let (left, right) = slice.split_at_mut(2);
2219     ///     left.clone_from_slice(&right[1..]);
2220     /// }
2221     ///
2222     /// assert_eq!(slice, [4, 5, 3, 4, 5]);
2223     /// ```
2224     ///
2225     /// [`copy_from_slice`]: #method.copy_from_slice
2226     /// [`split_at_mut`]: #method.split_at_mut
2227     #[stable(feature = "clone_from_slice", since = "1.7.0")]
2228     pub fn clone_from_slice(&mut self, src: &[T])
2229     where
2230         T: Clone,
2231     {
2232         assert!(self.len() == src.len(), "destination and source slices have different lengths");
2233         // NOTE: We need to explicitly slice them to the same length
2234         // for bounds checking to be elided, and the optimizer will
2235         // generate memcpy for simple cases (for example T = u8).
2236         let len = self.len();
2237         let src = &src[..len];
2238         for i in 0..len {
2239             self[i].clone_from(&src[i]);
2240         }
2241     }
2242
2243     /// Copies all elements from `src` into `self`, using a memcpy.
2244     ///
2245     /// The length of `src` must be the same as `self`.
2246     ///
2247     /// If `T` does not implement `Copy`, use [`clone_from_slice`].
2248     ///
2249     /// # Panics
2250     ///
2251     /// This function will panic if the two slices have different lengths.
2252     ///
2253     /// # Examples
2254     ///
2255     /// Copying two elements from a slice into another:
2256     ///
2257     /// ```
2258     /// let src = [1, 2, 3, 4];
2259     /// let mut dst = [0, 0];
2260     ///
2261     /// // Because the slices have to be the same length,
2262     /// // we slice the source slice from four elements
2263     /// // to two. It will panic if we don't do this.
2264     /// dst.copy_from_slice(&src[2..]);
2265     ///
2266     /// assert_eq!(src, [1, 2, 3, 4]);
2267     /// assert_eq!(dst, [3, 4]);
2268     /// ```
2269     ///
2270     /// Rust enforces that there can only be one mutable reference with no
2271     /// immutable references to a particular piece of data in a particular
2272     /// scope. Because of this, attempting to use `copy_from_slice` on a
2273     /// single slice will result in a compile failure:
2274     ///
2275     /// ```compile_fail
2276     /// let mut slice = [1, 2, 3, 4, 5];
2277     ///
2278     /// slice[..2].copy_from_slice(&slice[3..]); // compile fail!
2279     /// ```
2280     ///
2281     /// To work around this, we can use [`split_at_mut`] to create two distinct
2282     /// sub-slices from a slice:
2283     ///
2284     /// ```
2285     /// let mut slice = [1, 2, 3, 4, 5];
2286     ///
2287     /// {
2288     ///     let (left, right) = slice.split_at_mut(2);
2289     ///     left.copy_from_slice(&right[1..]);
2290     /// }
2291     ///
2292     /// assert_eq!(slice, [4, 5, 3, 4, 5]);
2293     /// ```
2294     ///
2295     /// [`clone_from_slice`]: #method.clone_from_slice
2296     /// [`split_at_mut`]: #method.split_at_mut
2297     #[stable(feature = "copy_from_slice", since = "1.9.0")]
2298     pub fn copy_from_slice(&mut self, src: &[T])
2299     where
2300         T: Copy,
2301     {
2302         assert_eq!(self.len(), src.len(), "destination and source slices have different lengths");
2303         unsafe {
2304             ptr::copy_nonoverlapping(src.as_ptr(), self.as_mut_ptr(), self.len());
2305         }
2306     }
2307
2308     /// Copies elements from one part of the slice to another part of itself,
2309     /// using a memmove.
2310     ///
2311     /// `src` is the range within `self` to copy from. `dest` is the starting
2312     /// index of the range within `self` to copy to, which will have the same
2313     /// length as `src`. The two ranges may overlap. The ends of the two ranges
2314     /// must be less than or equal to `self.len()`.
2315     ///
2316     /// # Panics
2317     ///
2318     /// This function will panic if either range exceeds the end of the slice,
2319     /// or if the end of `src` is before the start.
2320     ///
2321     /// # Examples
2322     ///
2323     /// Copying four bytes within a slice:
2324     ///
2325     /// ```
2326     /// let mut bytes = *b"Hello, World!";
2327     ///
2328     /// bytes.copy_within(1..5, 8);
2329     ///
2330     /// assert_eq!(&bytes, b"Hello, Wello!");
2331     /// ```
2332     #[stable(feature = "copy_within", since = "1.37.0")]
2333     #[track_caller]
2334     pub fn copy_within<R: ops::RangeBounds<usize>>(&mut self, src: R, dest: usize)
2335     where
2336         T: Copy,
2337     {
2338         let src_start = match src.start_bound() {
2339             ops::Bound::Included(&n) => n,
2340             ops::Bound::Excluded(&n) => {
2341                 n.checked_add(1).unwrap_or_else(|| slice_index_overflow_fail())
2342             }
2343             ops::Bound::Unbounded => 0,
2344         };
2345         let src_end = match src.end_bound() {
2346             ops::Bound::Included(&n) => {
2347                 n.checked_add(1).unwrap_or_else(|| slice_index_overflow_fail())
2348             }
2349             ops::Bound::Excluded(&n) => n,
2350             ops::Bound::Unbounded => self.len(),
2351         };
2352         assert!(src_start <= src_end, "src end is before src start");
2353         assert!(src_end <= self.len(), "src is out of bounds");
2354         let count = src_end - src_start;
2355         assert!(dest <= self.len() - count, "dest is out of bounds");
2356         unsafe {
2357             ptr::copy(self.as_ptr().add(src_start), self.as_mut_ptr().add(dest), count);
2358         }
2359     }
2360
2361     /// Swaps all elements in `self` with those in `other`.
2362     ///
2363     /// The length of `other` must be the same as `self`.
2364     ///
2365     /// # Panics
2366     ///
2367     /// This function will panic if the two slices have different lengths.
2368     ///
2369     /// # Example
2370     ///
2371     /// Swapping two elements across slices:
2372     ///
2373     /// ```
2374     /// let mut slice1 = [0, 0];
2375     /// let mut slice2 = [1, 2, 3, 4];
2376     ///
2377     /// slice1.swap_with_slice(&mut slice2[2..]);
2378     ///
2379     /// assert_eq!(slice1, [3, 4]);
2380     /// assert_eq!(slice2, [1, 2, 0, 0]);
2381     /// ```
2382     ///
2383     /// Rust enforces that there can only be one mutable reference to a
2384     /// particular piece of data in a particular scope. Because of this,
2385     /// attempting to use `swap_with_slice` on a single slice will result in
2386     /// a compile failure:
2387     ///
2388     /// ```compile_fail
2389     /// let mut slice = [1, 2, 3, 4, 5];
2390     /// slice[..2].swap_with_slice(&mut slice[3..]); // compile fail!
2391     /// ```
2392     ///
2393     /// To work around this, we can use [`split_at_mut`] to create two distinct
2394     /// mutable sub-slices from a slice:
2395     ///
2396     /// ```
2397     /// let mut slice = [1, 2, 3, 4, 5];
2398     ///
2399     /// {
2400     ///     let (left, right) = slice.split_at_mut(2);
2401     ///     left.swap_with_slice(&mut right[1..]);
2402     /// }
2403     ///
2404     /// assert_eq!(slice, [4, 5, 3, 1, 2]);
2405     /// ```
2406     ///
2407     /// [`split_at_mut`]: #method.split_at_mut
2408     #[stable(feature = "swap_with_slice", since = "1.27.0")]
2409     pub fn swap_with_slice(&mut self, other: &mut [T]) {
2410         assert!(self.len() == other.len(), "destination and source slices have different lengths");
2411         unsafe {
2412             ptr::swap_nonoverlapping(self.as_mut_ptr(), other.as_mut_ptr(), self.len());
2413         }
2414     }
2415
2416     /// Function to calculate lengths of the middle and trailing slice for `align_to{,_mut}`.
2417     fn align_to_offsets<U>(&self) -> (usize, usize) {
2418         // What we gonna do about `rest` is figure out what multiple of `U`s we can put in a
2419         // lowest number of `T`s. And how many `T`s we need for each such "multiple".
2420         //
2421         // Consider for example T=u8 U=u16. Then we can put 1 U in 2 Ts. Simple. Now, consider
2422         // for example a case where size_of::<T> = 16, size_of::<U> = 24. We can put 2 Us in
2423         // place of every 3 Ts in the `rest` slice. A bit more complicated.
2424         //
2425         // Formula to calculate this is:
2426         //
2427         // Us = lcm(size_of::<T>, size_of::<U>) / size_of::<U>
2428         // Ts = lcm(size_of::<T>, size_of::<U>) / size_of::<T>
2429         //
2430         // Expanded and simplified:
2431         //
2432         // Us = size_of::<T> / gcd(size_of::<T>, size_of::<U>)
2433         // Ts = size_of::<U> / gcd(size_of::<T>, size_of::<U>)
2434         //
2435         // Luckily since all this is constant-evaluated... performance here matters not!
2436         #[inline]
2437         fn gcd(a: usize, b: usize) -> usize {
2438             use crate::intrinsics;
2439             // iterative stein’s algorithm
2440             // We should still make this `const fn` (and revert to recursive algorithm if we do)
2441             // because relying on llvm to consteval all this is… well, it makes me uncomfortable.
2442             let (ctz_a, mut ctz_b) = unsafe {
2443                 if a == 0 {
2444                     return b;
2445                 }
2446                 if b == 0 {
2447                     return a;
2448                 }
2449                 (intrinsics::cttz_nonzero(a), intrinsics::cttz_nonzero(b))
2450             };
2451             let k = ctz_a.min(ctz_b);
2452             let mut a = a >> ctz_a;
2453             let mut b = b;
2454             loop {
2455                 // remove all factors of 2 from b
2456                 b >>= ctz_b;
2457                 if a > b {
2458                     mem::swap(&mut a, &mut b);
2459                 }
2460                 b = b - a;
2461                 unsafe {
2462                     if b == 0 {
2463                         break;
2464                     }
2465                     ctz_b = intrinsics::cttz_nonzero(b);
2466                 }
2467             }
2468             a << k
2469         }
2470         let gcd: usize = gcd(mem::size_of::<T>(), mem::size_of::<U>());
2471         let ts: usize = mem::size_of::<U>() / gcd;
2472         let us: usize = mem::size_of::<T>() / gcd;
2473
2474         // Armed with this knowledge, we can find how many `U`s we can fit!
2475         let us_len = self.len() / ts * us;
2476         // And how many `T`s will be in the trailing slice!
2477         let ts_len = self.len() % ts;
2478         (us_len, ts_len)
2479     }
2480
2481     /// Transmute the slice to a slice of another type, ensuring alignment of the types is
2482     /// maintained.
2483     ///
2484     /// This method splits the slice into three distinct slices: prefix, correctly aligned middle
2485     /// slice of a new type, and the suffix slice. The method may make the middle slice the greatest
2486     /// length possible for a given type and input slice, but only your algorithm's performance
2487     /// should depend on that, not its correctness. It is permissible for all of the input data to
2488     /// be returned as the prefix or suffix slice.
2489     ///
2490     /// This method has no purpose when either input element `T` or output element `U` are
2491     /// zero-sized and will return the original slice without splitting anything.
2492     ///
2493     /// # Safety
2494     ///
2495     /// This method is essentially a `transmute` with respect to the elements in the returned
2496     /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here.
2497     ///
2498     /// # Examples
2499     ///
2500     /// Basic usage:
2501     ///
2502     /// ```
2503     /// unsafe {
2504     ///     let bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7];
2505     ///     let (prefix, shorts, suffix) = bytes.align_to::<u16>();
2506     ///     // less_efficient_algorithm_for_bytes(prefix);
2507     ///     // more_efficient_algorithm_for_aligned_shorts(shorts);
2508     ///     // less_efficient_algorithm_for_bytes(suffix);
2509     /// }
2510     /// ```
2511     #[stable(feature = "slice_align_to", since = "1.30.0")]
2512     pub unsafe fn align_to<U>(&self) -> (&[T], &[U], &[T]) {
2513         // Note that most of this function will be constant-evaluated,
2514         if mem::size_of::<U>() == 0 || mem::size_of::<T>() == 0 {
2515             // handle ZSTs specially, which is – don't handle them at all.
2516             return (self, &[], &[]);
2517         }
2518
2519         // First, find at what point do we split between the first and 2nd slice. Easy with
2520         // ptr.align_offset.
2521         let ptr = self.as_ptr();
2522         let offset = crate::ptr::align_offset(ptr, mem::align_of::<U>());
2523         if offset > self.len() {
2524             (self, &[], &[])
2525         } else {
2526             let (left, rest) = self.split_at(offset);
2527             // now `rest` is definitely aligned, so `from_raw_parts_mut` below is okay
2528             let (us_len, ts_len) = rest.align_to_offsets::<U>();
2529             (
2530                 left,
2531                 from_raw_parts(rest.as_ptr() as *const U, us_len),
2532                 from_raw_parts(rest.as_ptr().add(rest.len() - ts_len), ts_len),
2533             )
2534         }
2535     }
2536
2537     /// Transmute the slice to a slice of another type, ensuring alignment of the types is
2538     /// maintained.
2539     ///
2540     /// This method splits the slice into three distinct slices: prefix, correctly aligned middle
2541     /// slice of a new type, and the suffix slice. The method may make the middle slice the greatest
2542     /// length possible for a given type and input slice, but only your algorithm's performance
2543     /// should depend on that, not its correctness. It is permissible for all of the input data to
2544     /// be returned as the prefix or suffix slice.
2545     ///
2546     /// This method has no purpose when either input element `T` or output element `U` are
2547     /// zero-sized and will return the original slice without splitting anything.
2548     ///
2549     /// # Safety
2550     ///
2551     /// This method is essentially a `transmute` with respect to the elements in the returned
2552     /// middle slice, so all the usual caveats pertaining to `transmute::<T, U>` also apply here.
2553     ///
2554     /// # Examples
2555     ///
2556     /// Basic usage:
2557     ///
2558     /// ```
2559     /// unsafe {
2560     ///     let mut bytes: [u8; 7] = [1, 2, 3, 4, 5, 6, 7];
2561     ///     let (prefix, shorts, suffix) = bytes.align_to_mut::<u16>();
2562     ///     // less_efficient_algorithm_for_bytes(prefix);
2563     ///     // more_efficient_algorithm_for_aligned_shorts(shorts);
2564     ///     // less_efficient_algorithm_for_bytes(suffix);
2565     /// }
2566     /// ```
2567     #[stable(feature = "slice_align_to", since = "1.30.0")]
2568     pub unsafe fn align_to_mut<U>(&mut self) -> (&mut [T], &mut [U], &mut [T]) {
2569         // Note that most of this function will be constant-evaluated,
2570         if mem::size_of::<U>() == 0 || mem::size_of::<T>() == 0 {
2571             // handle ZSTs specially, which is – don't handle them at all.
2572             return (self, &mut [], &mut []);
2573         }
2574
2575         // First, find at what point do we split between the first and 2nd slice. Easy with
2576         // ptr.align_offset.
2577         let ptr = self.as_ptr();
2578         let offset = crate::ptr::align_offset(ptr, mem::align_of::<U>());
2579         if offset > self.len() {
2580             (self, &mut [], &mut [])
2581         } else {
2582             let (left, rest) = self.split_at_mut(offset);
2583             // now `rest` is definitely aligned, so `from_raw_parts_mut` below is okay
2584             let (us_len, ts_len) = rest.align_to_offsets::<U>();
2585             let rest_len = rest.len();
2586             let mut_ptr = rest.as_mut_ptr();
2587             // We can't use `rest` again after this, that would invalidate its alias `mut_ptr`!
2588             (
2589                 left,
2590                 from_raw_parts_mut(mut_ptr as *mut U, us_len),
2591                 from_raw_parts_mut(mut_ptr.add(rest_len - ts_len), ts_len),
2592             )
2593         }
2594     }
2595
2596     /// Checks if the elements of this slice are sorted.
2597     ///
2598     /// That is, for each element `a` and its following element `b`, `a <= b` must hold. If the
2599     /// slice yields exactly zero or one element, `true` is returned.
2600     ///
2601     /// Note that if `Self::Item` is only `PartialOrd`, but not `Ord`, the above definition
2602     /// implies that this function returns `false` if any two consecutive items are not
2603     /// comparable.
2604     ///
2605     /// # Examples
2606     ///
2607     /// ```
2608     /// #![feature(is_sorted)]
2609     /// let empty: [i32; 0] = [];
2610     ///
2611     /// assert!([1, 2, 2, 9].is_sorted());
2612     /// assert!(![1, 3, 2, 4].is_sorted());
2613     /// assert!([0].is_sorted());
2614     /// assert!(empty.is_sorted());
2615     /// assert!(![0.0, 1.0, f32::NAN].is_sorted());
2616     /// ```
2617     #[inline]
2618     #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
2619     pub fn is_sorted(&self) -> bool
2620     where
2621         T: PartialOrd,
2622     {
2623         self.is_sorted_by(|a, b| a.partial_cmp(b))
2624     }
2625
2626     /// Checks if the elements of this slice are sorted using the given comparator function.
2627     ///
2628     /// Instead of using `PartialOrd::partial_cmp`, this function uses the given `compare`
2629     /// function to determine the ordering of two elements. Apart from that, it's equivalent to
2630     /// [`is_sorted`]; see its documentation for more information.
2631     ///
2632     /// [`is_sorted`]: #method.is_sorted
2633     #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
2634     pub fn is_sorted_by<F>(&self, mut compare: F) -> bool
2635     where
2636         F: FnMut(&T, &T) -> Option<Ordering>,
2637     {
2638         self.iter().is_sorted_by(|a, b| compare(*a, *b))
2639     }
2640
2641     /// Checks if the elements of this slice are sorted using the given key extraction function.
2642     ///
2643     /// Instead of comparing the slice's elements directly, this function compares the keys of the
2644     /// elements, as determined by `f`. Apart from that, it's equivalent to [`is_sorted`]; see its
2645     /// documentation for more information.
2646     ///
2647     /// [`is_sorted`]: #method.is_sorted
2648     ///
2649     /// # Examples
2650     ///
2651     /// ```
2652     /// #![feature(is_sorted)]
2653     ///
2654     /// assert!(["c", "bb", "aaa"].is_sorted_by_key(|s| s.len()));
2655     /// assert!(![-2i32, -1, 0, 3].is_sorted_by_key(|n| n.abs()));
2656     /// ```
2657     #[inline]
2658     #[unstable(feature = "is_sorted", reason = "new API", issue = "53485")]
2659     pub fn is_sorted_by_key<F, K>(&self, f: F) -> bool
2660     where
2661         F: FnMut(&T) -> K,
2662         K: PartialOrd,
2663     {
2664         self.iter().is_sorted_by_key(f)
2665     }
2666
2667     /// Returns index of partition point according to the given predicate,
2668     /// such that all those that return true precede the index and
2669     /// such that all those that return false succeed the index.
2670     ///
2671     /// The slice must be partitioned
2672     /// so that all elements where the predicate returns true
2673     /// precede the elements where the predicate returns false.
2674     ///
2675     /// # Examples
2676     ///
2677     /// ```
2678     /// #![feature(partition_point)]
2679     ///
2680     /// let v = [1, 2, 3, 3, 5, 6, 7];
2681     /// let i = v.partition_point(|&x| x < 5);
2682     ///
2683     /// assert_eq!(i, 4);
2684     /// assert!(v[..i].iter().all(|&x| x < 5));
2685     /// assert!(v[i..].iter().all(|&x| !(x < 5)));
2686     /// ```
2687     #[unstable(feature = "partition_point", reason = "new API", issue = "99999")]
2688     pub fn partition_point<P>(&self, mut pred: P) -> usize
2689     where
2690         P: FnMut(&T) -> bool,
2691     {
2692         let mut left = 0;
2693         let mut right = self.len();
2694
2695         while left != right {
2696             let mid = left + (right - left) / 2;
2697             // SAFETY:
2698             // When left < right, left <= mid < right.
2699             // Therefore left always increases and right always decreases,
2700             // and eigher of them is selected.
2701             // In both cases left <= right is satisfied.
2702             // Therefore if left < right in a step,
2703             // left <= right is satisfied in the next step.
2704             // Therefore as long as left != right, 0 <= left < right <= len is satisfied
2705             // and if this case 0 <= mid < len is satisfied too.
2706             let value = unsafe { self.get_unchecked(mid) };
2707             if pred(value) {
2708                 left = mid + 1;
2709             } else {
2710                 right = mid;
2711             }
2712         }
2713         return left;
2714     }
2715 }
2716
2717 #[lang = "slice_u8"]
2718 #[cfg(not(test))]
2719 impl [u8] {
2720     /// Checks if all bytes in this slice are within the ASCII range.
2721     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
2722     #[inline]
2723     pub fn is_ascii(&self) -> bool {
2724         self.iter().all(|b| b.is_ascii())
2725     }
2726
2727     /// Checks that two slices are an ASCII case-insensitive match.
2728     ///
2729     /// Same as `to_ascii_lowercase(a) == to_ascii_lowercase(b)`,
2730     /// but without allocating and copying temporaries.
2731     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
2732     #[inline]
2733     pub fn eq_ignore_ascii_case(&self, other: &[u8]) -> bool {
2734         self.len() == other.len() && self.iter().zip(other).all(|(a, b)| a.eq_ignore_ascii_case(b))
2735     }
2736
2737     /// Converts this slice to its ASCII upper case equivalent in-place.
2738     ///
2739     /// ASCII letters 'a' to 'z' are mapped to 'A' to 'Z',
2740     /// but non-ASCII letters are unchanged.
2741     ///
2742     /// To return a new uppercased value without modifying the existing one, use
2743     /// [`to_ascii_uppercase`].
2744     ///
2745     /// [`to_ascii_uppercase`]: #method.to_ascii_uppercase
2746     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
2747     #[inline]
2748     pub fn make_ascii_uppercase(&mut self) {
2749         for byte in self {
2750             byte.make_ascii_uppercase();
2751         }
2752     }
2753
2754     /// Converts this slice to its ASCII lower case equivalent in-place.
2755     ///
2756     /// ASCII letters 'A' to 'Z' are mapped to 'a' to 'z',
2757     /// but non-ASCII letters are unchanged.
2758     ///
2759     /// To return a new lowercased value without modifying the existing one, use
2760     /// [`to_ascii_lowercase`].
2761     ///
2762     /// [`to_ascii_lowercase`]: #method.to_ascii_lowercase
2763     #[stable(feature = "ascii_methods_on_intrinsics", since = "1.23.0")]
2764     #[inline]
2765     pub fn make_ascii_lowercase(&mut self) {
2766         for byte in self {
2767             byte.make_ascii_lowercase();
2768         }
2769     }
2770 }
2771
2772 #[stable(feature = "rust1", since = "1.0.0")]
2773 impl<T, I> ops::Index<I> for [T]
2774 where
2775     I: SliceIndex<[T]>,
2776 {
2777     type Output = I::Output;
2778
2779     #[inline]
2780     fn index(&self, index: I) -> &I::Output {
2781         index.index(self)
2782     }
2783 }
2784
2785 #[stable(feature = "rust1", since = "1.0.0")]
2786 impl<T, I> ops::IndexMut<I> for [T]
2787 where
2788     I: SliceIndex<[T]>,
2789 {
2790     #[inline]
2791     fn index_mut(&mut self, index: I) -> &mut I::Output {
2792         index.index_mut(self)
2793     }
2794 }
2795
2796 #[inline(never)]
2797 #[cold]
2798 #[track_caller]
2799 fn slice_index_len_fail(index: usize, len: usize) -> ! {
2800     panic!("index {} out of range for slice of length {}", index, len);
2801 }
2802
2803 #[inline(never)]
2804 #[cold]
2805 #[track_caller]
2806 fn slice_index_order_fail(index: usize, end: usize) -> ! {
2807     panic!("slice index starts at {} but ends at {}", index, end);
2808 }
2809
2810 #[inline(never)]
2811 #[cold]
2812 #[track_caller]
2813 fn slice_index_overflow_fail() -> ! {
2814     panic!("attempted to index slice up to maximum usize");
2815 }
2816
2817 mod private_slice_index {
2818     use super::ops;
2819     #[stable(feature = "slice_get_slice", since = "1.28.0")]
2820     pub trait Sealed {}
2821
2822     #[stable(feature = "slice_get_slice", since = "1.28.0")]
2823     impl Sealed for usize {}
2824     #[stable(feature = "slice_get_slice", since = "1.28.0")]
2825     impl Sealed for ops::Range<usize> {}
2826     #[stable(feature = "slice_get_slice", since = "1.28.0")]
2827     impl Sealed for ops::RangeTo<usize> {}
2828     #[stable(feature = "slice_get_slice", since = "1.28.0")]
2829     impl Sealed for ops::RangeFrom<usize> {}
2830     #[stable(feature = "slice_get_slice", since = "1.28.0")]
2831     impl Sealed for ops::RangeFull {}
2832     #[stable(feature = "slice_get_slice", since = "1.28.0")]
2833     impl Sealed for ops::RangeInclusive<usize> {}
2834     #[stable(feature = "slice_get_slice", since = "1.28.0")]
2835     impl Sealed for ops::RangeToInclusive<usize> {}
2836 }
2837
2838 /// A helper trait used for indexing operations.
2839 #[stable(feature = "slice_get_slice", since = "1.28.0")]
2840 #[rustc_on_unimplemented(
2841     on(T = "str", label = "string indices are ranges of `usize`",),
2842     on(
2843         all(any(T = "str", T = "&str", T = "std::string::String"), _Self = "{integer}"),
2844         note = "you can use `.chars().nth()` or `.bytes().nth()`
2845 see chapter in The Book <https://doc.rust-lang.org/book/ch08-02-strings.html#indexing-into-strings>"
2846     ),
2847     message = "the type `{T}` cannot be indexed by `{Self}`",
2848     label = "slice indices are of type `usize` or ranges of `usize`"
2849 )]
2850 pub trait SliceIndex<T: ?Sized>: private_slice_index::Sealed {
2851     /// The output type returned by methods.
2852     #[stable(feature = "slice_get_slice", since = "1.28.0")]
2853     type Output: ?Sized;
2854
2855     /// Returns a shared reference to the output at this location, if in
2856     /// bounds.
2857     #[unstable(feature = "slice_index_methods", issue = "none")]
2858     fn get(self, slice: &T) -> Option<&Self::Output>;
2859
2860     /// Returns a mutable reference to the output at this location, if in
2861     /// bounds.
2862     #[unstable(feature = "slice_index_methods", issue = "none")]
2863     fn get_mut(self, slice: &mut T) -> Option<&mut Self::Output>;
2864
2865     /// Returns a shared reference to the output at this location, without
2866     /// performing any bounds checking.
2867     /// Calling this method with an out-of-bounds index is *[undefined behavior]*
2868     /// even if the resulting reference is not used.
2869     /// [undefined behavior]: ../../reference/behavior-considered-undefined.html
2870     #[unstable(feature = "slice_index_methods", issue = "none")]
2871     unsafe fn get_unchecked(self, slice: &T) -> &Self::Output;
2872
2873     /// Returns a mutable reference to the output at this location, without
2874     /// performing any bounds checking.
2875     /// Calling this method with an out-of-bounds index is *[undefined behavior]*
2876     /// even if the resulting reference is not used.
2877     /// [undefined behavior]: ../../reference/behavior-considered-undefined.html
2878     #[unstable(feature = "slice_index_methods", issue = "none")]
2879     unsafe fn get_unchecked_mut(self, slice: &mut T) -> &mut Self::Output;
2880
2881     /// Returns a shared reference to the output at this location, panicking
2882     /// if out of bounds.
2883     #[unstable(feature = "slice_index_methods", issue = "none")]
2884     #[track_caller]
2885     fn index(self, slice: &T) -> &Self::Output;
2886
2887     /// Returns a mutable reference to the output at this location, panicking
2888     /// if out of bounds.
2889     #[unstable(feature = "slice_index_methods", issue = "none")]
2890     #[track_caller]
2891     fn index_mut(self, slice: &mut T) -> &mut Self::Output;
2892 }
2893
2894 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
2895 impl<T> SliceIndex<[T]> for usize {
2896     type Output = T;
2897
2898     #[inline]
2899     fn get(self, slice: &[T]) -> Option<&T> {
2900         if self < slice.len() { unsafe { Some(self.get_unchecked(slice)) } } else { None }
2901     }
2902
2903     #[inline]
2904     fn get_mut(self, slice: &mut [T]) -> Option<&mut T> {
2905         if self < slice.len() { unsafe { Some(self.get_unchecked_mut(slice)) } } else { None }
2906     }
2907
2908     #[inline]
2909     unsafe fn get_unchecked(self, slice: &[T]) -> &T {
2910         &*slice.as_ptr().add(self)
2911     }
2912
2913     #[inline]
2914     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut T {
2915         &mut *slice.as_mut_ptr().add(self)
2916     }
2917
2918     #[inline]
2919     fn index(self, slice: &[T]) -> &T {
2920         // N.B., use intrinsic indexing
2921         &(*slice)[self]
2922     }
2923
2924     #[inline]
2925     fn index_mut(self, slice: &mut [T]) -> &mut T {
2926         // N.B., use intrinsic indexing
2927         &mut (*slice)[self]
2928     }
2929 }
2930
2931 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
2932 impl<T> SliceIndex<[T]> for ops::Range<usize> {
2933     type Output = [T];
2934
2935     #[inline]
2936     fn get(self, slice: &[T]) -> Option<&[T]> {
2937         if self.start > self.end || self.end > slice.len() {
2938             None
2939         } else {
2940             unsafe { Some(self.get_unchecked(slice)) }
2941         }
2942     }
2943
2944     #[inline]
2945     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2946         if self.start > self.end || self.end > slice.len() {
2947             None
2948         } else {
2949             unsafe { Some(self.get_unchecked_mut(slice)) }
2950         }
2951     }
2952
2953     #[inline]
2954     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
2955         from_raw_parts(slice.as_ptr().add(self.start), self.end - self.start)
2956     }
2957
2958     #[inline]
2959     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
2960         from_raw_parts_mut(slice.as_mut_ptr().add(self.start), self.end - self.start)
2961     }
2962
2963     #[inline]
2964     fn index(self, slice: &[T]) -> &[T] {
2965         if self.start > self.end {
2966             slice_index_order_fail(self.start, self.end);
2967         } else if self.end > slice.len() {
2968             slice_index_len_fail(self.end, slice.len());
2969         }
2970         unsafe { self.get_unchecked(slice) }
2971     }
2972
2973     #[inline]
2974     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
2975         if self.start > self.end {
2976             slice_index_order_fail(self.start, self.end);
2977         } else if self.end > slice.len() {
2978             slice_index_len_fail(self.end, slice.len());
2979         }
2980         unsafe { self.get_unchecked_mut(slice) }
2981     }
2982 }
2983
2984 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
2985 impl<T> SliceIndex<[T]> for ops::RangeTo<usize> {
2986     type Output = [T];
2987
2988     #[inline]
2989     fn get(self, slice: &[T]) -> Option<&[T]> {
2990         (0..self.end).get(slice)
2991     }
2992
2993     #[inline]
2994     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
2995         (0..self.end).get_mut(slice)
2996     }
2997
2998     #[inline]
2999     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
3000         (0..self.end).get_unchecked(slice)
3001     }
3002
3003     #[inline]
3004     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
3005         (0..self.end).get_unchecked_mut(slice)
3006     }
3007
3008     #[inline]
3009     fn index(self, slice: &[T]) -> &[T] {
3010         (0..self.end).index(slice)
3011     }
3012
3013     #[inline]
3014     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
3015         (0..self.end).index_mut(slice)
3016     }
3017 }
3018
3019 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
3020 impl<T> SliceIndex<[T]> for ops::RangeFrom<usize> {
3021     type Output = [T];
3022
3023     #[inline]
3024     fn get(self, slice: &[T]) -> Option<&[T]> {
3025         (self.start..slice.len()).get(slice)
3026     }
3027
3028     #[inline]
3029     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
3030         (self.start..slice.len()).get_mut(slice)
3031     }
3032
3033     #[inline]
3034     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
3035         (self.start..slice.len()).get_unchecked(slice)
3036     }
3037
3038     #[inline]
3039     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
3040         (self.start..slice.len()).get_unchecked_mut(slice)
3041     }
3042
3043     #[inline]
3044     fn index(self, slice: &[T]) -> &[T] {
3045         (self.start..slice.len()).index(slice)
3046     }
3047
3048     #[inline]
3049     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
3050         (self.start..slice.len()).index_mut(slice)
3051     }
3052 }
3053
3054 #[stable(feature = "slice_get_slice_impls", since = "1.15.0")]
3055 impl<T> SliceIndex<[T]> for ops::RangeFull {
3056     type Output = [T];
3057
3058     #[inline]
3059     fn get(self, slice: &[T]) -> Option<&[T]> {
3060         Some(slice)
3061     }
3062
3063     #[inline]
3064     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
3065         Some(slice)
3066     }
3067
3068     #[inline]
3069     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
3070         slice
3071     }
3072
3073     #[inline]
3074     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
3075         slice
3076     }
3077
3078     #[inline]
3079     fn index(self, slice: &[T]) -> &[T] {
3080         slice
3081     }
3082
3083     #[inline]
3084     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
3085         slice
3086     }
3087 }
3088
3089 #[stable(feature = "inclusive_range", since = "1.26.0")]
3090 impl<T> SliceIndex<[T]> for ops::RangeInclusive<usize> {
3091     type Output = [T];
3092
3093     #[inline]
3094     fn get(self, slice: &[T]) -> Option<&[T]> {
3095         if *self.end() == usize::MAX { None } else { (*self.start()..self.end() + 1).get(slice) }
3096     }
3097
3098     #[inline]
3099     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
3100         if *self.end() == usize::MAX {
3101             None
3102         } else {
3103             (*self.start()..self.end() + 1).get_mut(slice)
3104         }
3105     }
3106
3107     #[inline]
3108     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
3109         (*self.start()..self.end() + 1).get_unchecked(slice)
3110     }
3111
3112     #[inline]
3113     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
3114         (*self.start()..self.end() + 1).get_unchecked_mut(slice)
3115     }
3116
3117     #[inline]
3118     fn index(self, slice: &[T]) -> &[T] {
3119         if *self.end() == usize::MAX {
3120             slice_index_overflow_fail();
3121         }
3122         (*self.start()..self.end() + 1).index(slice)
3123     }
3124
3125     #[inline]
3126     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
3127         if *self.end() == usize::MAX {
3128             slice_index_overflow_fail();
3129         }
3130         (*self.start()..self.end() + 1).index_mut(slice)
3131     }
3132 }
3133
3134 #[stable(feature = "inclusive_range", since = "1.26.0")]
3135 impl<T> SliceIndex<[T]> for ops::RangeToInclusive<usize> {
3136     type Output = [T];
3137
3138     #[inline]
3139     fn get(self, slice: &[T]) -> Option<&[T]> {
3140         (0..=self.end).get(slice)
3141     }
3142
3143     #[inline]
3144     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
3145         (0..=self.end).get_mut(slice)
3146     }
3147
3148     #[inline]
3149     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
3150         (0..=self.end).get_unchecked(slice)
3151     }
3152
3153     #[inline]
3154     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
3155         (0..=self.end).get_unchecked_mut(slice)
3156     }
3157
3158     #[inline]
3159     fn index(self, slice: &[T]) -> &[T] {
3160         (0..=self.end).index(slice)
3161     }
3162
3163     #[inline]
3164     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
3165         (0..=self.end).index_mut(slice)
3166     }
3167 }
3168
3169 ////////////////////////////////////////////////////////////////////////////////
3170 // Common traits
3171 ////////////////////////////////////////////////////////////////////////////////
3172
3173 #[stable(feature = "rust1", since = "1.0.0")]
3174 impl<T> Default for &[T] {
3175     /// Creates an empty slice.
3176     fn default() -> Self {
3177         &[]
3178     }
3179 }
3180
3181 #[stable(feature = "mut_slice_default", since = "1.5.0")]
3182 impl<T> Default for &mut [T] {
3183     /// Creates a mutable empty slice.
3184     fn default() -> Self {
3185         &mut []
3186     }
3187 }
3188
3189 //
3190 // Iterators
3191 //
3192
3193 #[stable(feature = "rust1", since = "1.0.0")]
3194 impl<'a, T> IntoIterator for &'a [T] {
3195     type Item = &'a T;
3196     type IntoIter = Iter<'a, T>;
3197
3198     fn into_iter(self) -> Iter<'a, T> {
3199         self.iter()
3200     }
3201 }
3202
3203 #[stable(feature = "rust1", since = "1.0.0")]
3204 impl<'a, T> IntoIterator for &'a mut [T] {
3205     type Item = &'a mut T;
3206     type IntoIter = IterMut<'a, T>;
3207
3208     fn into_iter(self) -> IterMut<'a, T> {
3209         self.iter_mut()
3210     }
3211 }
3212
3213 // Macro helper functions
3214 #[inline(always)]
3215 fn size_from_ptr<T>(_: *const T) -> usize {
3216     mem::size_of::<T>()
3217 }
3218
3219 // Inlining is_empty and len makes a huge performance difference
3220 macro_rules! is_empty {
3221     // The way we encode the length of a ZST iterator, this works both for ZST
3222     // and non-ZST.
3223     ($self: ident) => {
3224         $self.ptr.as_ptr() as *const T == $self.end
3225     };
3226 }
3227
3228 // To get rid of some bounds checks (see `position`), we compute the length in a somewhat
3229 // unexpected way. (Tested by `codegen/slice-position-bounds-check`.)
3230 macro_rules! len {
3231     ($self: ident) => {{
3232         #![allow(unused_unsafe)] // we're sometimes used within an unsafe block
3233
3234         let start = $self.ptr;
3235         let size = size_from_ptr(start.as_ptr());
3236         if size == 0 {
3237             // This _cannot_ use `unchecked_sub` because we depend on wrapping
3238             // to represent the length of long ZST slice iterators.
3239             ($self.end as usize).wrapping_sub(start.as_ptr() as usize)
3240         } else {
3241             // We know that `start <= end`, so can do better than `offset_from`,
3242             // which needs to deal in signed.  By setting appropriate flags here
3243             // we can tell LLVM this, which helps it remove bounds checks.
3244             // SAFETY: By the type invariant, `start <= end`
3245             let diff = unsafe { unchecked_sub($self.end as usize, start.as_ptr() as usize) };
3246             // By also telling LLVM that the pointers are apart by an exact
3247             // multiple of the type size, it can optimize `len() == 0` down to
3248             // `start == end` instead of `(end - start) < size`.
3249             // SAFETY: By the type invariant, the pointers are aligned so the
3250             //         distance between them must be a multiple of pointee size
3251             unsafe { exact_div(diff, size) }
3252         }
3253     }};
3254 }
3255
3256 // The shared definition of the `Iter` and `IterMut` iterators
3257 macro_rules! iterator {
3258     (
3259         struct $name:ident -> $ptr:ty,
3260         $elem:ty,
3261         $raw_mut:tt,
3262         {$( $mut_:tt )*},
3263         {$($extra:tt)*}
3264     ) => {
3265         // Returns the first element and moves the start of the iterator forwards by 1.
3266         // Greatly improves performance compared to an inlined function. The iterator
3267         // must not be empty.
3268         macro_rules! next_unchecked {
3269             ($self: ident) => {& $( $mut_ )* *$self.post_inc_start(1)}
3270         }
3271
3272         // Returns the last element and moves the end of the iterator backwards by 1.
3273         // Greatly improves performance compared to an inlined function. The iterator
3274         // must not be empty.
3275         macro_rules! next_back_unchecked {
3276             ($self: ident) => {& $( $mut_ )* *$self.pre_dec_end(1)}
3277         }
3278
3279         // Shrinks the iterator when T is a ZST, by moving the end of the iterator
3280         // backwards by `n`. `n` must not exceed `self.len()`.
3281         macro_rules! zst_shrink {
3282             ($self: ident, $n: ident) => {
3283                 $self.end = ($self.end as * $raw_mut u8).wrapping_offset(-$n) as * $raw_mut T;
3284             }
3285         }
3286
3287         impl<'a, T> $name<'a, T> {
3288             // Helper function for creating a slice from the iterator.
3289             #[inline(always)]
3290             fn make_slice(&self) -> &'a [T] {
3291                 unsafe { from_raw_parts(self.ptr.as_ptr(), len!(self)) }
3292             }
3293
3294             // Helper function for moving the start of the iterator forwards by `offset` elements,
3295             // returning the old start.
3296             // Unsafe because the offset must not exceed `self.len()`.
3297             #[inline(always)]
3298             unsafe fn post_inc_start(&mut self, offset: isize) -> * $raw_mut T {
3299                 if mem::size_of::<T>() == 0 {
3300                     zst_shrink!(self, offset);
3301                     self.ptr.as_ptr()
3302                 } else {
3303                     let old = self.ptr.as_ptr();
3304                     self.ptr = NonNull::new_unchecked(self.ptr.as_ptr().offset(offset));
3305                     old
3306                 }
3307             }
3308
3309             // Helper function for moving the end of the iterator backwards by `offset` elements,
3310             // returning the new end.
3311             // Unsafe because the offset must not exceed `self.len()`.
3312             #[inline(always)]
3313             unsafe fn pre_dec_end(&mut self, offset: isize) -> * $raw_mut T {
3314                 if mem::size_of::<T>() == 0 {
3315                     zst_shrink!(self, offset);
3316                     self.ptr.as_ptr()
3317                 } else {
3318                     self.end = self.end.offset(-offset);
3319                     self.end
3320                 }
3321             }
3322         }
3323
3324         #[stable(feature = "rust1", since = "1.0.0")]
3325         impl<T> ExactSizeIterator for $name<'_, T> {
3326             #[inline(always)]
3327             fn len(&self) -> usize {
3328                 len!(self)
3329             }
3330
3331             #[inline(always)]
3332             fn is_empty(&self) -> bool {
3333                 is_empty!(self)
3334             }
3335         }
3336
3337         #[stable(feature = "rust1", since = "1.0.0")]
3338         impl<'a, T> Iterator for $name<'a, T> {
3339             type Item = $elem;
3340
3341             #[inline]
3342             fn next(&mut self) -> Option<$elem> {
3343                 // could be implemented with slices, but this avoids bounds checks
3344                 unsafe {
3345                     assume(!self.ptr.as_ptr().is_null());
3346                     if mem::size_of::<T>() != 0 {
3347                         assume(!self.end.is_null());
3348                     }
3349                     if is_empty!(self) {
3350                         None
3351                     } else {
3352                         Some(next_unchecked!(self))
3353                     }
3354                 }
3355             }
3356
3357             #[inline]
3358             fn size_hint(&self) -> (usize, Option<usize>) {
3359                 let exact = len!(self);
3360                 (exact, Some(exact))
3361             }
3362
3363             #[inline]
3364             fn count(self) -> usize {
3365                 len!(self)
3366             }
3367
3368             #[inline]
3369             fn nth(&mut self, n: usize) -> Option<$elem> {
3370                 if n >= len!(self) {
3371                     // This iterator is now empty.
3372                     if mem::size_of::<T>() == 0 {
3373                         // We have to do it this way as `ptr` may never be 0, but `end`
3374                         // could be (due to wrapping).
3375                         self.end = self.ptr.as_ptr();
3376                     } else {
3377                         unsafe {
3378                             // End can't be 0 if T isn't ZST because ptr isn't 0 and end >= ptr
3379                             self.ptr = NonNull::new_unchecked(self.end as *mut T);
3380                         }
3381                     }
3382                     return None;
3383                 }
3384                 // We are in bounds. `post_inc_start` does the right thing even for ZSTs.
3385                 unsafe {
3386                     self.post_inc_start(n as isize);
3387                     Some(next_unchecked!(self))
3388                 }
3389             }
3390
3391             #[inline]
3392             fn last(mut self) -> Option<$elem> {
3393                 self.next_back()
3394             }
3395
3396             // We override the default implementation, which uses `try_fold`,
3397             // because this simple implementation generates less LLVM IR and is
3398             // faster to compile.
3399             #[inline]
3400             fn for_each<F>(mut self, mut f: F)
3401             where
3402                 Self: Sized,
3403                 F: FnMut(Self::Item),
3404             {
3405                 while let Some(x) = self.next() {
3406                     f(x);
3407                 }
3408             }
3409
3410             // We override the default implementation, which uses `try_fold`,
3411             // because this simple implementation generates less LLVM IR and is
3412             // faster to compile.
3413             #[inline]
3414             fn all<F>(&mut self, mut f: F) -> bool
3415             where
3416                 Self: Sized,
3417                 F: FnMut(Self::Item) -> bool,
3418             {
3419                 while let Some(x) = self.next() {
3420                     if !f(x) {
3421                         return false;
3422                     }
3423                 }
3424                 true
3425             }
3426
3427             // We override the default implementation, which uses `try_fold`,
3428             // because this simple implementation generates less LLVM IR and is
3429             // faster to compile.
3430             #[inline]
3431             fn any<F>(&mut self, mut f: F) -> bool
3432             where
3433                 Self: Sized,
3434                 F: FnMut(Self::Item) -> bool,
3435             {
3436                 while let Some(x) = self.next() {
3437                     if f(x) {
3438                         return true;
3439                     }
3440                 }
3441                 false
3442             }
3443
3444             // We override the default implementation, which uses `try_fold`,
3445             // because this simple implementation generates less LLVM IR and is
3446             // faster to compile.
3447             #[inline]
3448             fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item>
3449             where
3450                 Self: Sized,
3451                 P: FnMut(&Self::Item) -> bool,
3452             {
3453                 while let Some(x) = self.next() {
3454                     if predicate(&x) {
3455                         return Some(x);
3456                     }
3457                 }
3458                 None
3459             }
3460
3461             // We override the default implementation, which uses `try_fold`,
3462             // because this simple implementation generates less LLVM IR and is
3463             // faster to compile.
3464             #[inline]
3465             fn find_map<B, F>(&mut self, mut f: F) -> Option<B>
3466             where
3467                 Self: Sized,
3468                 F: FnMut(Self::Item) -> Option<B>,
3469             {
3470                 while let Some(x) = self.next() {
3471                     if let Some(y) = f(x) {
3472                         return Some(y);
3473                     }
3474                 }
3475                 None
3476             }
3477
3478             // We override the default implementation, which uses `try_fold`,
3479             // because this simple implementation generates less LLVM IR and is
3480             // faster to compile. Also, the `assume` avoids a bounds check.
3481             #[inline]
3482             #[rustc_inherit_overflow_checks]
3483             fn position<P>(&mut self, mut predicate: P) -> Option<usize> where
3484                 Self: Sized,
3485                 P: FnMut(Self::Item) -> bool,
3486             {
3487                 let n = len!(self);
3488                 let mut i = 0;
3489                 while let Some(x) = self.next() {
3490                     if predicate(x) {
3491                         unsafe { assume(i < n) };
3492                         return Some(i);
3493                     }
3494                     i += 1;
3495                 }
3496                 None
3497             }
3498
3499             // We override the default implementation, which uses `try_fold`,
3500             // because this simple implementation generates less LLVM IR and is
3501             // faster to compile. Also, the `assume` avoids a bounds check.
3502             #[inline]
3503             fn rposition<P>(&mut self, mut predicate: P) -> Option<usize> where
3504                 P: FnMut(Self::Item) -> bool,
3505                 Self: Sized + ExactSizeIterator + DoubleEndedIterator
3506             {
3507                 let n = len!(self);
3508                 let mut i = n;
3509                 while let Some(x) = self.next_back() {
3510                     i -= 1;
3511                     if predicate(x) {
3512                         unsafe { assume(i < n) };
3513                         return Some(i);
3514                     }
3515                 }
3516                 None
3517             }
3518
3519             $($extra)*
3520         }
3521
3522         #[stable(feature = "rust1", since = "1.0.0")]
3523         impl<'a, T> DoubleEndedIterator for $name<'a, T> {
3524             #[inline]
3525             fn next_back(&mut self) -> Option<$elem> {
3526                 // could be implemented with slices, but this avoids bounds checks
3527                 unsafe {
3528                     assume(!self.ptr.as_ptr().is_null());
3529                     if mem::size_of::<T>() != 0 {
3530                         assume(!self.end.is_null());
3531                     }
3532                     if is_empty!(self) {
3533                         None
3534                     } else {
3535                         Some(next_back_unchecked!(self))
3536                     }
3537                 }
3538             }
3539
3540             #[inline]
3541             fn nth_back(&mut self, n: usize) -> Option<$elem> {
3542                 if n >= len!(self) {
3543                     // This iterator is now empty.
3544                     self.end = self.ptr.as_ptr();
3545                     return None;
3546                 }
3547                 // We are in bounds. `pre_dec_end` does the right thing even for ZSTs.
3548                 unsafe {
3549                     self.pre_dec_end(n as isize);
3550                     Some(next_back_unchecked!(self))
3551                 }
3552             }
3553         }
3554
3555         #[stable(feature = "fused", since = "1.26.0")]
3556         impl<T> FusedIterator for $name<'_, T> {}
3557
3558         #[unstable(feature = "trusted_len", issue = "37572")]
3559         unsafe impl<T> TrustedLen for $name<'_, T> {}
3560     }
3561 }
3562
3563 /// Immutable slice iterator
3564 ///
3565 /// This struct is created by the [`iter`] method on [slices].
3566 ///
3567 /// # Examples
3568 ///
3569 /// Basic usage:
3570 ///
3571 /// ```
3572 /// // First, we declare a type which has `iter` method to get the `Iter` struct (&[usize here]):
3573 /// let slice = &[1, 2, 3];
3574 ///
3575 /// // Then, we iterate over it:
3576 /// for element in slice.iter() {
3577 ///     println!("{}", element);
3578 /// }
3579 /// ```
3580 ///
3581 /// [`iter`]: ../../std/primitive.slice.html#method.iter
3582 /// [slices]: ../../std/primitive.slice.html
3583 #[stable(feature = "rust1", since = "1.0.0")]
3584 pub struct Iter<'a, T: 'a> {
3585     ptr: NonNull<T>,
3586     end: *const T, // If T is a ZST, this is actually ptr+len.  This encoding is picked so that
3587     // ptr == end is a quick test for the Iterator being empty, that works
3588     // for both ZST and non-ZST.
3589     _marker: marker::PhantomData<&'a T>,
3590 }
3591
3592 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3593 impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> {
3594     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3595         f.debug_tuple("Iter").field(&self.as_slice()).finish()
3596     }
3597 }
3598
3599 #[stable(feature = "rust1", since = "1.0.0")]
3600 unsafe impl<T: Sync> Sync for Iter<'_, T> {}
3601 #[stable(feature = "rust1", since = "1.0.0")]
3602 unsafe impl<T: Sync> Send for Iter<'_, T> {}
3603
3604 impl<'a, T> Iter<'a, T> {
3605     /// Views the underlying data as a subslice of the original data.
3606     ///
3607     /// This has the same lifetime as the original slice, and so the
3608     /// iterator can continue to be used while this exists.
3609     ///
3610     /// # Examples
3611     ///
3612     /// Basic usage:
3613     ///
3614     /// ```
3615     /// // First, we declare a type which has the `iter` method to get the `Iter`
3616     /// // struct (&[usize here]):
3617     /// let slice = &[1, 2, 3];
3618     ///
3619     /// // Then, we get the iterator:
3620     /// let mut iter = slice.iter();
3621     /// // So if we print what `as_slice` method returns here, we have "[1, 2, 3]":
3622     /// println!("{:?}", iter.as_slice());
3623     ///
3624     /// // Next, we move to the second element of the slice:
3625     /// iter.next();
3626     /// // Now `as_slice` returns "[2, 3]":
3627     /// println!("{:?}", iter.as_slice());
3628     /// ```
3629     #[stable(feature = "iter_to_slice", since = "1.4.0")]
3630     pub fn as_slice(&self) -> &'a [T] {
3631         self.make_slice()
3632     }
3633 }
3634
3635 iterator! {struct Iter -> *const T, &'a T, const, {/* no mut */}, {
3636     fn is_sorted_by<F>(self, mut compare: F) -> bool
3637     where
3638         Self: Sized,
3639         F: FnMut(&Self::Item, &Self::Item) -> Option<Ordering>,
3640     {
3641         self.as_slice().windows(2).all(|w| {
3642             compare(&&w[0], &&w[1]).map(|o| o != Ordering::Greater).unwrap_or(false)
3643         })
3644     }
3645 }}
3646
3647 #[stable(feature = "rust1", since = "1.0.0")]
3648 impl<T> Clone for Iter<'_, T> {
3649     fn clone(&self) -> Self {
3650         Iter { ptr: self.ptr, end: self.end, _marker: self._marker }
3651     }
3652 }
3653
3654 #[stable(feature = "slice_iter_as_ref", since = "1.13.0")]
3655 impl<T> AsRef<[T]> for Iter<'_, T> {
3656     fn as_ref(&self) -> &[T] {
3657         self.as_slice()
3658     }
3659 }
3660
3661 /// Mutable slice iterator.
3662 ///
3663 /// This struct is created by the [`iter_mut`] method on [slices].
3664 ///
3665 /// # Examples
3666 ///
3667 /// Basic usage:
3668 ///
3669 /// ```
3670 /// // First, we declare a type which has `iter_mut` method to get the `IterMut`
3671 /// // struct (&[usize here]):
3672 /// let mut slice = &mut [1, 2, 3];
3673 ///
3674 /// // Then, we iterate over it and increment each element value:
3675 /// for element in slice.iter_mut() {
3676 ///     *element += 1;
3677 /// }
3678 ///
3679 /// // We now have "[2, 3, 4]":
3680 /// println!("{:?}", slice);
3681 /// ```
3682 ///
3683 /// [`iter_mut`]: ../../std/primitive.slice.html#method.iter_mut
3684 /// [slices]: ../../std/primitive.slice.html
3685 #[stable(feature = "rust1", since = "1.0.0")]
3686 pub struct IterMut<'a, T: 'a> {
3687     ptr: NonNull<T>,
3688     end: *mut T, // If T is a ZST, this is actually ptr+len.  This encoding is picked so that
3689     // ptr == end is a quick test for the Iterator being empty, that works
3690     // for both ZST and non-ZST.
3691     _marker: marker::PhantomData<&'a mut T>,
3692 }
3693
3694 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3695 impl<T: fmt::Debug> fmt::Debug for IterMut<'_, T> {
3696     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3697         f.debug_tuple("IterMut").field(&self.make_slice()).finish()
3698     }
3699 }
3700
3701 #[stable(feature = "rust1", since = "1.0.0")]
3702 unsafe impl<T: Sync> Sync for IterMut<'_, T> {}
3703 #[stable(feature = "rust1", since = "1.0.0")]
3704 unsafe impl<T: Send> Send for IterMut<'_, T> {}
3705
3706 impl<'a, T> IterMut<'a, T> {
3707     /// Views the underlying data as a subslice of the original data.
3708     ///
3709     /// To avoid creating `&mut` references that alias, this is forced
3710     /// to consume the iterator.
3711     ///
3712     /// # Examples
3713     ///
3714     /// Basic usage:
3715     ///
3716     /// ```
3717     /// // First, we declare a type which has `iter_mut` method to get the `IterMut`
3718     /// // struct (&[usize here]):
3719     /// let mut slice = &mut [1, 2, 3];
3720     ///
3721     /// {
3722     ///     // Then, we get the iterator:
3723     ///     let mut iter = slice.iter_mut();
3724     ///     // We move to next element:
3725     ///     iter.next();
3726     ///     // So if we print what `into_slice` method returns here, we have "[2, 3]":
3727     ///     println!("{:?}", iter.into_slice());
3728     /// }
3729     ///
3730     /// // Now let's modify a value of the slice:
3731     /// {
3732     ///     // First we get back the iterator:
3733     ///     let mut iter = slice.iter_mut();
3734     ///     // We change the value of the first element of the slice returned by the `next` method:
3735     ///     *iter.next().unwrap() += 1;
3736     /// }
3737     /// // Now slice is "[2, 2, 3]":
3738     /// println!("{:?}", slice);
3739     /// ```
3740     #[stable(feature = "iter_to_slice", since = "1.4.0")]
3741     pub fn into_slice(self) -> &'a mut [T] {
3742         unsafe { from_raw_parts_mut(self.ptr.as_ptr(), len!(self)) }
3743     }
3744
3745     /// Views the underlying data as a subslice of the original data.
3746     ///
3747     /// To avoid creating `&mut [T]` references that alias, the returned slice
3748     /// borrows its lifetime from the iterator the method is applied on.
3749     ///
3750     /// # Examples
3751     ///
3752     /// Basic usage:
3753     ///
3754     /// ```
3755     /// # #![feature(slice_iter_mut_as_slice)]
3756     /// let mut slice: &mut [usize] = &mut [1, 2, 3];
3757     ///
3758     /// // First, we get the iterator:
3759     /// let mut iter = slice.iter_mut();
3760     /// // So if we check what the `as_slice` method returns here, we have "[1, 2, 3]":
3761     /// assert_eq!(iter.as_slice(), &[1, 2, 3]);
3762     ///
3763     /// // Next, we move to the second element of the slice:
3764     /// iter.next();
3765     /// // Now `as_slice` returns "[2, 3]":
3766     /// assert_eq!(iter.as_slice(), &[2, 3]);
3767     /// ```
3768     #[unstable(feature = "slice_iter_mut_as_slice", reason = "recently added", issue = "58957")]
3769     pub fn as_slice(&self) -> &[T] {
3770         self.make_slice()
3771     }
3772 }
3773
3774 iterator! {struct IterMut -> *mut T, &'a mut T, mut, {mut}, {}}
3775
3776 /// An internal abstraction over the splitting iterators, so that
3777 /// splitn, splitn_mut etc can be implemented once.
3778 #[doc(hidden)]
3779 trait SplitIter: DoubleEndedIterator {
3780     /// Marks the underlying iterator as complete, extracting the remaining
3781     /// portion of the slice.
3782     fn finish(&mut self) -> Option<Self::Item>;
3783 }
3784
3785 /// An iterator over subslices separated by elements that match a predicate
3786 /// function.
3787 ///
3788 /// This struct is created by the [`split`] method on [slices].
3789 ///
3790 /// [`split`]: ../../std/primitive.slice.html#method.split
3791 /// [slices]: ../../std/primitive.slice.html
3792 #[stable(feature = "rust1", since = "1.0.0")]
3793 pub struct Split<'a, T: 'a, P>
3794 where
3795     P: FnMut(&T) -> bool,
3796 {
3797     v: &'a [T],
3798     pred: P,
3799     finished: bool,
3800 }
3801
3802 #[stable(feature = "core_impl_debug", since = "1.9.0")]
3803 impl<T: fmt::Debug, P> fmt::Debug for Split<'_, T, P>
3804 where
3805     P: FnMut(&T) -> bool,
3806 {
3807     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3808         f.debug_struct("Split").field("v", &self.v).field("finished", &self.finished).finish()
3809     }
3810 }
3811
3812 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
3813 #[stable(feature = "rust1", since = "1.0.0")]
3814 impl<T, P> Clone for Split<'_, T, P>
3815 where
3816     P: Clone + FnMut(&T) -> bool,
3817 {
3818     fn clone(&self) -> Self {
3819         Split { v: self.v, pred: self.pred.clone(), finished: self.finished }
3820     }
3821 }
3822
3823 #[stable(feature = "rust1", since = "1.0.0")]
3824 impl<'a, T, P> Iterator for Split<'a, T, P>
3825 where
3826     P: FnMut(&T) -> bool,
3827 {
3828     type Item = &'a [T];
3829
3830     #[inline]
3831     fn next(&mut self) -> Option<&'a [T]> {
3832         if self.finished {
3833             return None;
3834         }
3835
3836         match self.v.iter().position(|x| (self.pred)(x)) {
3837             None => self.finish(),
3838             Some(idx) => {
3839                 let ret = Some(&self.v[..idx]);
3840                 self.v = &self.v[idx + 1..];
3841                 ret
3842             }
3843         }
3844     }
3845
3846     #[inline]
3847     fn size_hint(&self) -> (usize, Option<usize>) {
3848         if self.finished { (0, Some(0)) } else { (1, Some(self.v.len() + 1)) }
3849     }
3850 }
3851
3852 #[stable(feature = "rust1", since = "1.0.0")]
3853 impl<'a, T, P> DoubleEndedIterator for Split<'a, T, P>
3854 where
3855     P: FnMut(&T) -> bool,
3856 {
3857     #[inline]
3858     fn next_back(&mut self) -> Option<&'a [T]> {
3859         if self.finished {
3860             return None;
3861         }
3862
3863         match self.v.iter().rposition(|x| (self.pred)(x)) {
3864             None => self.finish(),
3865             Some(idx) => {
3866                 let ret = Some(&self.v[idx + 1..]);
3867                 self.v = &self.v[..idx];
3868                 ret
3869             }
3870         }
3871     }
3872 }
3873
3874 impl<'a, T, P> SplitIter for Split<'a, T, P>
3875 where
3876     P: FnMut(&T) -> bool,
3877 {
3878     #[inline]
3879     fn finish(&mut self) -> Option<&'a [T]> {
3880         if self.finished {
3881             None
3882         } else {
3883             self.finished = true;
3884             Some(self.v)
3885         }
3886     }
3887 }
3888
3889 #[stable(feature = "fused", since = "1.26.0")]
3890 impl<T, P> FusedIterator for Split<'_, T, P> where P: FnMut(&T) -> bool {}
3891
3892 /// An iterator over subslices separated by elements that match a predicate
3893 /// function. Unlike `Split`, it contains the matched part as a terminator
3894 /// of the subslice.
3895 ///
3896 /// This struct is created by the [`split_inclusive`] method on [slices].
3897 ///
3898 /// [`split_inclusive`]: ../../std/primitive.slice.html#method.split_inclusive
3899 /// [slices]: ../../std/primitive.slice.html
3900 #[unstable(feature = "split_inclusive", issue = "72360")]
3901 pub struct SplitInclusive<'a, T: 'a, P>
3902 where
3903     P: FnMut(&T) -> bool,
3904 {
3905     v: &'a [T],
3906     pred: P,
3907     finished: bool,
3908 }
3909
3910 #[unstable(feature = "split_inclusive", issue = "72360")]
3911 impl<T: fmt::Debug, P> fmt::Debug for SplitInclusive<'_, T, P>
3912 where
3913     P: FnMut(&T) -> bool,
3914 {
3915     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
3916         f.debug_struct("SplitInclusive")
3917             .field("v", &self.v)
3918             .field("finished", &self.finished)
3919             .finish()
3920     }
3921 }
3922
3923 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
3924 #[unstable(feature = "split_inclusive", issue = "72360")]
3925 impl<T, P> Clone for SplitInclusive<'_, T, P>
3926 where
3927     P: Clone + FnMut(&T) -> bool,
3928 {
3929     fn clone(&self) -> Self {
3930         SplitInclusive { v: self.v, pred: self.pred.clone(), finished: self.finished }
3931     }
3932 }
3933
3934 #[unstable(feature = "split_inclusive", issue = "72360")]
3935 impl<'a, T, P> Iterator for SplitInclusive<'a, T, P>
3936 where
3937     P: FnMut(&T) -> bool,
3938 {
3939     type Item = &'a [T];
3940
3941     #[inline]
3942     fn next(&mut self) -> Option<&'a [T]> {
3943         if self.finished {
3944             return None;
3945         }
3946
3947         let idx =
3948             self.v.iter().position(|x| (self.pred)(x)).map(|idx| idx + 1).unwrap_or(self.v.len());
3949         if idx == self.v.len() {
3950             self.finished = true;
3951         }
3952         let ret = Some(&self.v[..idx]);
3953         self.v = &self.v[idx..];
3954         ret
3955     }
3956
3957     #[inline]
3958     fn size_hint(&self) -> (usize, Option<usize>) {
3959         if self.finished { (0, Some(0)) } else { (1, Some(self.v.len() + 1)) }
3960     }
3961 }
3962
3963 #[unstable(feature = "split_inclusive", issue = "72360")]
3964 impl<'a, T, P> DoubleEndedIterator for SplitInclusive<'a, T, P>
3965 where
3966     P: FnMut(&T) -> bool,
3967 {
3968     #[inline]
3969     fn next_back(&mut self) -> Option<&'a [T]> {
3970         if self.finished {
3971             return None;
3972         }
3973
3974         // The last index of self.v is already checked and found to match
3975         // by the last iteration, so we start searching a new match
3976         // one index to the left.
3977         let remainder = if self.v.is_empty() { &[] } else { &self.v[..(self.v.len() - 1)] };
3978         let idx = remainder.iter().rposition(|x| (self.pred)(x)).map(|idx| idx + 1).unwrap_or(0);
3979         if idx == 0 {
3980             self.finished = true;
3981         }
3982         let ret = Some(&self.v[idx..]);
3983         self.v = &self.v[..idx];
3984         ret
3985     }
3986 }
3987
3988 #[unstable(feature = "split_inclusive", issue = "72360")]
3989 impl<T, P> FusedIterator for SplitInclusive<'_, T, P> where P: FnMut(&T) -> bool {}
3990
3991 /// An iterator over the mutable subslices of the vector which are separated
3992 /// by elements that match `pred`.
3993 ///
3994 /// This struct is created by the [`split_mut`] method on [slices].
3995 ///
3996 /// [`split_mut`]: ../../std/primitive.slice.html#method.split_mut
3997 /// [slices]: ../../std/primitive.slice.html
3998 #[stable(feature = "rust1", since = "1.0.0")]
3999 pub struct SplitMut<'a, T: 'a, P>
4000 where
4001     P: FnMut(&T) -> bool,
4002 {
4003     v: &'a mut [T],
4004     pred: P,
4005     finished: bool,
4006 }
4007
4008 #[stable(feature = "core_impl_debug", since = "1.9.0")]
4009 impl<T: fmt::Debug, P> fmt::Debug for SplitMut<'_, T, P>
4010 where
4011     P: FnMut(&T) -> bool,
4012 {
4013     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
4014         f.debug_struct("SplitMut").field("v", &self.v).field("finished", &self.finished).finish()
4015     }
4016 }
4017
4018 impl<'a, T, P> SplitIter for SplitMut<'a, T, P>
4019 where
4020     P: FnMut(&T) -> bool,
4021 {
4022     #[inline]
4023     fn finish(&mut self) -> Option<&'a mut [T]> {
4024         if self.finished {
4025             None
4026         } else {
4027             self.finished = true;
4028             Some(mem::replace(&mut self.v, &mut []))
4029         }
4030     }
4031 }
4032
4033 #[stable(feature = "rust1", since = "1.0.0")]
4034 impl<'a, T, P> Iterator for SplitMut<'a, T, P>
4035 where
4036     P: FnMut(&T) -> bool,
4037 {
4038     type Item = &'a mut [T];
4039
4040     #[inline]
4041     fn next(&mut self) -> Option<&'a mut [T]> {
4042         if self.finished {
4043             return None;
4044         }
4045
4046         let idx_opt = {
4047             // work around borrowck limitations
4048             let pred = &mut self.pred;
4049             self.v.iter().position(|x| (*pred)(x))
4050         };
4051         match idx_opt {
4052             None => self.finish(),
4053             Some(idx) => {
4054                 let tmp = mem::replace(&mut self.v, &mut []);
4055                 let (head, tail) = tmp.split_at_mut(idx);
4056                 self.v = &mut tail[1..];
4057                 Some(head)
4058             }
4059         }
4060     }
4061
4062     #[inline]
4063     fn size_hint(&self) -> (usize, Option<usize>) {
4064         if self.finished {
4065             (0, Some(0))
4066         } else {
4067             // if the predicate doesn't match anything, we yield one slice
4068             // if it matches every element, we yield len+1 empty slices.
4069             (1, Some(self.v.len() + 1))
4070         }
4071     }
4072 }
4073
4074 #[stable(feature = "rust1", since = "1.0.0")]
4075 impl<'a, T, P> DoubleEndedIterator for SplitMut<'a, T, P>
4076 where
4077     P: FnMut(&T) -> bool,
4078 {
4079     #[inline]
4080     fn next_back(&mut self) -> Option<&'a mut [T]> {
4081         if self.finished {
4082             return None;
4083         }
4084
4085         let idx_opt = {
4086             // work around borrowck limitations
4087             let pred = &mut self.pred;
4088             self.v.iter().rposition(|x| (*pred)(x))
4089         };
4090         match idx_opt {
4091             None => self.finish(),
4092             Some(idx) => {
4093                 let tmp = mem::replace(&mut self.v, &mut []);
4094                 let (head, tail) = tmp.split_at_mut(idx);
4095                 self.v = head;
4096                 Some(&mut tail[1..])
4097             }
4098         }
4099     }
4100 }
4101
4102 #[stable(feature = "fused", since = "1.26.0")]
4103 impl<T, P> FusedIterator for SplitMut<'_, T, P> where P: FnMut(&T) -> bool {}
4104
4105 /// An iterator over the mutable subslices of the vector which are separated
4106 /// by elements that match `pred`. Unlike `SplitMut`, it contains the matched
4107 /// parts in the ends of the subslices.
4108 ///
4109 /// This struct is created by the [`split_inclusive_mut`] method on [slices].
4110 ///
4111 /// [`split_inclusive_mut`]: ../../std/primitive.slice.html#method.split_inclusive_mut
4112 /// [slices]: ../../std/primitive.slice.html
4113 #[unstable(feature = "split_inclusive", issue = "72360")]
4114 pub struct SplitInclusiveMut<'a, T: 'a, P>
4115 where
4116     P: FnMut(&T) -> bool,
4117 {
4118     v: &'a mut [T],
4119     pred: P,
4120     finished: bool,
4121 }
4122
4123 #[unstable(feature = "split_inclusive", issue = "72360")]
4124 impl<T: fmt::Debug, P> fmt::Debug for SplitInclusiveMut<'_, T, P>
4125 where
4126     P: FnMut(&T) -> bool,
4127 {
4128     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
4129         f.debug_struct("SplitInclusiveMut")
4130             .field("v", &self.v)
4131             .field("finished", &self.finished)
4132             .finish()
4133     }
4134 }
4135
4136 #[unstable(feature = "split_inclusive", issue = "72360")]
4137 impl<'a, T, P> Iterator for SplitInclusiveMut<'a, T, P>
4138 where
4139     P: FnMut(&T) -> bool,
4140 {
4141     type Item = &'a mut [T];
4142
4143     #[inline]
4144     fn next(&mut self) -> Option<&'a mut [T]> {
4145         if self.finished {
4146             return None;
4147         }
4148
4149         let idx_opt = {
4150             // work around borrowck limitations
4151             let pred = &mut self.pred;
4152             self.v.iter().position(|x| (*pred)(x))
4153         };
4154         let idx = idx_opt.map(|idx| idx + 1).unwrap_or(self.v.len());
4155         if idx == self.v.len() {
4156             self.finished = true;
4157         }
4158         let tmp = mem::replace(&mut self.v, &mut []);
4159         let (head, tail) = tmp.split_at_mut(idx);
4160         self.v = tail;
4161         Some(head)
4162     }
4163
4164     #[inline]
4165     fn size_hint(&self) -> (usize, Option<usize>) {
4166         if self.finished {
4167             (0, Some(0))
4168         } else {
4169             // if the predicate doesn't match anything, we yield one slice
4170             // if it matches every element, we yield len+1 empty slices.
4171             (1, Some(self.v.len() + 1))
4172         }
4173     }
4174 }
4175
4176 #[unstable(feature = "split_inclusive", issue = "72360")]
4177 impl<'a, T, P> DoubleEndedIterator for SplitInclusiveMut<'a, T, P>
4178 where
4179     P: FnMut(&T) -> bool,
4180 {
4181     #[inline]
4182     fn next_back(&mut self) -> Option<&'a mut [T]> {
4183         if self.finished {
4184             return None;
4185         }
4186
4187         let idx_opt = if self.v.is_empty() {
4188             None
4189         } else {
4190             // work around borrowck limitations
4191             let pred = &mut self.pred;
4192
4193             // The last index of self.v is already checked and found to match
4194             // by the last iteration, so we start searching a new match
4195             // one index to the left.
4196             let remainder = &self.v[..(self.v.len() - 1)];
4197             remainder.iter().rposition(|x| (*pred)(x))
4198         };
4199         let idx = idx_opt.map(|idx| idx + 1).unwrap_or(0);
4200         if idx == 0 {
4201             self.finished = true;
4202         }
4203         let tmp = mem::replace(&mut self.v, &mut []);
4204         let (head, tail) = tmp.split_at_mut(idx);
4205         self.v = head;
4206         Some(tail)
4207     }
4208 }
4209
4210 #[unstable(feature = "split_inclusive", issue = "72360")]
4211 impl<T, P> FusedIterator for SplitInclusiveMut<'_, T, P> where P: FnMut(&T) -> bool {}
4212
4213 /// An iterator over subslices separated by elements that match a predicate
4214 /// function, starting from the end of the slice.
4215 ///
4216 /// This struct is created by the [`rsplit`] method on [slices].
4217 ///
4218 /// [`rsplit`]: ../../std/primitive.slice.html#method.rsplit
4219 /// [slices]: ../../std/primitive.slice.html
4220 #[stable(feature = "slice_rsplit", since = "1.27.0")]
4221 #[derive(Clone)] // Is this correct, or does it incorrectly require `T: Clone`?
4222 pub struct RSplit<'a, T: 'a, P>
4223 where
4224     P: FnMut(&T) -> bool,
4225 {
4226     inner: Split<'a, T, P>,
4227 }
4228
4229 #[stable(feature = "slice_rsplit", since = "1.27.0")]
4230 impl<T: fmt::Debug, P> fmt::Debug for RSplit<'_, T, P>
4231 where
4232     P: FnMut(&T) -> bool,
4233 {
4234     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
4235         f.debug_struct("RSplit")
4236             .field("v", &self.inner.v)
4237             .field("finished", &self.inner.finished)
4238             .finish()
4239     }
4240 }
4241
4242 #[stable(feature = "slice_rsplit", since = "1.27.0")]
4243 impl<'a, T, P> Iterator for RSplit<'a, T, P>
4244 where
4245     P: FnMut(&T) -> bool,
4246 {
4247     type Item = &'a [T];
4248
4249     #[inline]
4250     fn next(&mut self) -> Option<&'a [T]> {
4251         self.inner.next_back()
4252     }
4253
4254     #[inline]
4255     fn size_hint(&self) -> (usize, Option<usize>) {
4256         self.inner.size_hint()
4257     }
4258 }
4259
4260 #[stable(feature = "slice_rsplit", since = "1.27.0")]
4261 impl<'a, T, P> DoubleEndedIterator for RSplit<'a, T, P>
4262 where
4263     P: FnMut(&T) -> bool,
4264 {
4265     #[inline]
4266     fn next_back(&mut self) -> Option<&'a [T]> {
4267         self.inner.next()
4268     }
4269 }
4270
4271 #[stable(feature = "slice_rsplit", since = "1.27.0")]
4272 impl<'a, T, P> SplitIter for RSplit<'a, T, P>
4273 where
4274     P: FnMut(&T) -> bool,
4275 {
4276     #[inline]
4277     fn finish(&mut self) -> Option<&'a [T]> {
4278         self.inner.finish()
4279     }
4280 }
4281
4282 #[stable(feature = "slice_rsplit", since = "1.27.0")]
4283 impl<T, P> FusedIterator for RSplit<'_, T, P> where P: FnMut(&T) -> bool {}
4284
4285 /// An iterator over the subslices of the vector which are separated
4286 /// by elements that match `pred`, starting from the end of the slice.
4287 ///
4288 /// This struct is created by the [`rsplit_mut`] method on [slices].
4289 ///
4290 /// [`rsplit_mut`]: ../../std/primitive.slice.html#method.rsplit_mut
4291 /// [slices]: ../../std/primitive.slice.html
4292 #[stable(feature = "slice_rsplit", since = "1.27.0")]
4293 pub struct RSplitMut<'a, T: 'a, P>
4294 where
4295     P: FnMut(&T) -> bool,
4296 {
4297     inner: SplitMut<'a, T, P>,
4298 }
4299
4300 #[stable(feature = "slice_rsplit", since = "1.27.0")]
4301 impl<T: fmt::Debug, P> fmt::Debug for RSplitMut<'_, T, P>
4302 where
4303     P: FnMut(&T) -> bool,
4304 {
4305     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
4306         f.debug_struct("RSplitMut")
4307             .field("v", &self.inner.v)
4308             .field("finished", &self.inner.finished)
4309             .finish()
4310     }
4311 }
4312
4313 #[stable(feature = "slice_rsplit", since = "1.27.0")]
4314 impl<'a, T, P> SplitIter for RSplitMut<'a, T, P>
4315 where
4316     P: FnMut(&T) -> bool,
4317 {
4318     #[inline]
4319     fn finish(&mut self) -> Option<&'a mut [T]> {
4320         self.inner.finish()
4321     }
4322 }
4323
4324 #[stable(feature = "slice_rsplit", since = "1.27.0")]
4325 impl<'a, T, P> Iterator for RSplitMut<'a, T, P>
4326 where
4327     P: FnMut(&T) -> bool,
4328 {
4329     type Item = &'a mut [T];
4330
4331     #[inline]
4332     fn next(&mut self) -> Option<&'a mut [T]> {
4333         self.inner.next_back()
4334     }
4335
4336     #[inline]
4337     fn size_hint(&self) -> (usize, Option<usize>) {
4338         self.inner.size_hint()
4339     }
4340 }
4341
4342 #[stable(feature = "slice_rsplit", since = "1.27.0")]
4343 impl<'a, T, P> DoubleEndedIterator for RSplitMut<'a, T, P>
4344 where
4345     P: FnMut(&T) -> bool,
4346 {
4347     #[inline]
4348     fn next_back(&mut self) -> Option<&'a mut [T]> {
4349         self.inner.next()
4350     }
4351 }
4352
4353 #[stable(feature = "slice_rsplit", since = "1.27.0")]
4354 impl<T, P> FusedIterator for RSplitMut<'_, T, P> where P: FnMut(&T) -> bool {}
4355
4356 /// An private iterator over subslices separated by elements that
4357 /// match a predicate function, splitting at most a fixed number of
4358 /// times.
4359 #[derive(Debug)]
4360 struct GenericSplitN<I> {
4361     iter: I,
4362     count: usize,
4363 }
4364
4365 impl<T, I: SplitIter<Item = T>> Iterator for GenericSplitN<I> {
4366     type Item = T;
4367
4368     #[inline]
4369     fn next(&mut self) -> Option<T> {
4370         match self.count {
4371             0 => None,
4372             1 => {
4373                 self.count -= 1;
4374                 self.iter.finish()
4375             }
4376             _ => {
4377                 self.count -= 1;
4378                 self.iter.next()
4379             }
4380         }
4381     }
4382
4383     #[inline]
4384     fn size_hint(&self) -> (usize, Option<usize>) {
4385         let (lower, upper_opt) = self.iter.size_hint();
4386         (lower, upper_opt.map(|upper| cmp::min(self.count, upper)))
4387     }
4388 }
4389
4390 /// An iterator over subslices separated by elements that match a predicate
4391 /// function, limited to a given number of splits.
4392 ///
4393 /// This struct is created by the [`splitn`] method on [slices].
4394 ///
4395 /// [`splitn`]: ../../std/primitive.slice.html#method.splitn
4396 /// [slices]: ../../std/primitive.slice.html
4397 #[stable(feature = "rust1", since = "1.0.0")]
4398 pub struct SplitN<'a, T: 'a, P>
4399 where
4400     P: FnMut(&T) -> bool,
4401 {
4402     inner: GenericSplitN<Split<'a, T, P>>,
4403 }
4404
4405 #[stable(feature = "core_impl_debug", since = "1.9.0")]
4406 impl<T: fmt::Debug, P> fmt::Debug for SplitN<'_, T, P>
4407 where
4408     P: FnMut(&T) -> bool,
4409 {
4410     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
4411         f.debug_struct("SplitN").field("inner", &self.inner).finish()
4412     }
4413 }
4414
4415 /// An iterator over subslices separated by elements that match a
4416 /// predicate function, limited to a given number of splits, starting
4417 /// from the end of the slice.
4418 ///
4419 /// This struct is created by the [`rsplitn`] method on [slices].
4420 ///
4421 /// [`rsplitn`]: ../../std/primitive.slice.html#method.rsplitn
4422 /// [slices]: ../../std/primitive.slice.html
4423 #[stable(feature = "rust1", since = "1.0.0")]
4424 pub struct RSplitN<'a, T: 'a, P>
4425 where
4426     P: FnMut(&T) -> bool,
4427 {
4428     inner: GenericSplitN<RSplit<'a, T, P>>,
4429 }
4430
4431 #[stable(feature = "core_impl_debug", since = "1.9.0")]
4432 impl<T: fmt::Debug, P> fmt::Debug for RSplitN<'_, T, P>
4433 where
4434     P: FnMut(&T) -> bool,
4435 {
4436     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
4437         f.debug_struct("RSplitN").field("inner", &self.inner).finish()
4438     }
4439 }
4440
4441 /// An iterator over subslices separated by elements that match a predicate
4442 /// function, limited to a given number of splits.
4443 ///
4444 /// This struct is created by the [`splitn_mut`] method on [slices].
4445 ///
4446 /// [`splitn_mut`]: ../../std/primitive.slice.html#method.splitn_mut
4447 /// [slices]: ../../std/primitive.slice.html
4448 #[stable(feature = "rust1", since = "1.0.0")]
4449 pub struct SplitNMut<'a, T: 'a, P>
4450 where
4451     P: FnMut(&T) -> bool,
4452 {
4453     inner: GenericSplitN<SplitMut<'a, T, P>>,
4454 }
4455
4456 #[stable(feature = "core_impl_debug", since = "1.9.0")]
4457 impl<T: fmt::Debug, P> fmt::Debug for SplitNMut<'_, T, P>
4458 where
4459     P: FnMut(&T) -> bool,
4460 {
4461     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
4462         f.debug_struct("SplitNMut").field("inner", &self.inner).finish()
4463     }
4464 }
4465
4466 /// An iterator over subslices separated by elements that match a
4467 /// predicate function, limited to a given number of splits, starting
4468 /// from the end of the slice.
4469 ///
4470 /// This struct is created by the [`rsplitn_mut`] method on [slices].
4471 ///
4472 /// [`rsplitn_mut`]: ../../std/primitive.slice.html#method.rsplitn_mut
4473 /// [slices]: ../../std/primitive.slice.html
4474 #[stable(feature = "rust1", since = "1.0.0")]
4475 pub struct RSplitNMut<'a, T: 'a, P>
4476 where
4477     P: FnMut(&T) -> bool,
4478 {
4479     inner: GenericSplitN<RSplitMut<'a, T, P>>,
4480 }
4481
4482 #[stable(feature = "core_impl_debug", since = "1.9.0")]
4483 impl<T: fmt::Debug, P> fmt::Debug for RSplitNMut<'_, T, P>
4484 where
4485     P: FnMut(&T) -> bool,
4486 {
4487     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
4488         f.debug_struct("RSplitNMut").field("inner", &self.inner).finish()
4489     }
4490 }
4491
4492 macro_rules! forward_iterator {
4493     ($name:ident: $elem:ident, $iter_of:ty) => {
4494         #[stable(feature = "rust1", since = "1.0.0")]
4495         impl<'a, $elem, P> Iterator for $name<'a, $elem, P>
4496         where
4497             P: FnMut(&T) -> bool,
4498         {
4499             type Item = $iter_of;
4500
4501             #[inline]
4502             fn next(&mut self) -> Option<$iter_of> {
4503                 self.inner.next()
4504             }
4505
4506             #[inline]
4507             fn size_hint(&self) -> (usize, Option<usize>) {
4508                 self.inner.size_hint()
4509             }
4510         }
4511
4512         #[stable(feature = "fused", since = "1.26.0")]
4513         impl<'a, $elem, P> FusedIterator for $name<'a, $elem, P> where P: FnMut(&T) -> bool {}
4514     };
4515 }
4516
4517 forward_iterator! { SplitN: T, &'a [T] }
4518 forward_iterator! { RSplitN: T, &'a [T] }
4519 forward_iterator! { SplitNMut: T, &'a mut [T] }
4520 forward_iterator! { RSplitNMut: T, &'a mut [T] }
4521
4522 /// An iterator over overlapping subslices of length `size`.
4523 ///
4524 /// This struct is created by the [`windows`] method on [slices].
4525 ///
4526 /// [`windows`]: ../../std/primitive.slice.html#method.windows
4527 /// [slices]: ../../std/primitive.slice.html
4528 #[derive(Debug)]
4529 #[stable(feature = "rust1", since = "1.0.0")]
4530 pub struct Windows<'a, T: 'a> {
4531     v: &'a [T],
4532     size: usize,
4533 }
4534
4535 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
4536 #[stable(feature = "rust1", since = "1.0.0")]
4537 impl<T> Clone for Windows<'_, T> {
4538     fn clone(&self) -> Self {
4539         Windows { v: self.v, size: self.size }
4540     }
4541 }
4542
4543 #[stable(feature = "rust1", since = "1.0.0")]
4544 impl<'a, T> Iterator for Windows<'a, T> {
4545     type Item = &'a [T];
4546
4547     #[inline]
4548     fn next(&mut self) -> Option<&'a [T]> {
4549         if self.size > self.v.len() {
4550             None
4551         } else {
4552             let ret = Some(&self.v[..self.size]);
4553             self.v = &self.v[1..];
4554             ret
4555         }
4556     }
4557
4558     #[inline]
4559     fn size_hint(&self) -> (usize, Option<usize>) {
4560         if self.size > self.v.len() {
4561             (0, Some(0))
4562         } else {
4563             let size = self.v.len() - self.size + 1;
4564             (size, Some(size))
4565         }
4566     }
4567
4568     #[inline]
4569     fn count(self) -> usize {
4570         self.len()
4571     }
4572
4573     #[inline]
4574     fn nth(&mut self, n: usize) -> Option<Self::Item> {
4575         let (end, overflow) = self.size.overflowing_add(n);
4576         if end > self.v.len() || overflow {
4577             self.v = &[];
4578             None
4579         } else {
4580             let nth = &self.v[n..end];
4581             self.v = &self.v[n + 1..];
4582             Some(nth)
4583         }
4584     }
4585
4586     #[inline]
4587     fn last(self) -> Option<Self::Item> {
4588         if self.size > self.v.len() {
4589             None
4590         } else {
4591             let start = self.v.len() - self.size;
4592             Some(&self.v[start..])
4593         }
4594     }
4595 }
4596
4597 #[stable(feature = "rust1", since = "1.0.0")]
4598 impl<'a, T> DoubleEndedIterator for Windows<'a, T> {
4599     #[inline]
4600     fn next_back(&mut self) -> Option<&'a [T]> {
4601         if self.size > self.v.len() {
4602             None
4603         } else {
4604             let ret = Some(&self.v[self.v.len() - self.size..]);
4605             self.v = &self.v[..self.v.len() - 1];
4606             ret
4607         }
4608     }
4609
4610     #[inline]
4611     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
4612         let (end, overflow) = self.v.len().overflowing_sub(n);
4613         if end < self.size || overflow {
4614             self.v = &[];
4615             None
4616         } else {
4617             let ret = &self.v[end - self.size..end];
4618             self.v = &self.v[..end - 1];
4619             Some(ret)
4620         }
4621     }
4622 }
4623
4624 #[stable(feature = "rust1", since = "1.0.0")]
4625 impl<T> ExactSizeIterator for Windows<'_, T> {}
4626
4627 #[unstable(feature = "trusted_len", issue = "37572")]
4628 unsafe impl<T> TrustedLen for Windows<'_, T> {}
4629
4630 #[stable(feature = "fused", since = "1.26.0")]
4631 impl<T> FusedIterator for Windows<'_, T> {}
4632
4633 #[doc(hidden)]
4634 unsafe impl<'a, T> TrustedRandomAccess for Windows<'a, T> {
4635     unsafe fn get_unchecked(&mut self, i: usize) -> &'a [T] {
4636         from_raw_parts(self.v.as_ptr().add(i), self.size)
4637     }
4638     fn may_have_side_effect() -> bool {
4639         false
4640     }
4641 }
4642
4643 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
4644 /// time), starting at the beginning of the slice.
4645 ///
4646 /// When the slice len is not evenly divided by the chunk size, the last slice
4647 /// of the iteration will be the remainder.
4648 ///
4649 /// This struct is created by the [`chunks`] method on [slices].
4650 ///
4651 /// [`chunks`]: ../../std/primitive.slice.html#method.chunks
4652 /// [slices]: ../../std/primitive.slice.html
4653 #[derive(Debug)]
4654 #[stable(feature = "rust1", since = "1.0.0")]
4655 pub struct Chunks<'a, T: 'a> {
4656     v: &'a [T],
4657     chunk_size: usize,
4658 }
4659
4660 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
4661 #[stable(feature = "rust1", since = "1.0.0")]
4662 impl<T> Clone for Chunks<'_, T> {
4663     fn clone(&self) -> Self {
4664         Chunks { v: self.v, chunk_size: self.chunk_size }
4665     }
4666 }
4667
4668 #[stable(feature = "rust1", since = "1.0.0")]
4669 impl<'a, T> Iterator for Chunks<'a, T> {
4670     type Item = &'a [T];
4671
4672     #[inline]
4673     fn next(&mut self) -> Option<&'a [T]> {
4674         if self.v.is_empty() {
4675             None
4676         } else {
4677             let chunksz = cmp::min(self.v.len(), self.chunk_size);
4678             let (fst, snd) = self.v.split_at(chunksz);
4679             self.v = snd;
4680             Some(fst)
4681         }
4682     }
4683
4684     #[inline]
4685     fn size_hint(&self) -> (usize, Option<usize>) {
4686         if self.v.is_empty() {
4687             (0, Some(0))
4688         } else {
4689             let n = self.v.len() / self.chunk_size;
4690             let rem = self.v.len() % self.chunk_size;
4691             let n = if rem > 0 { n + 1 } else { n };
4692             (n, Some(n))
4693         }
4694     }
4695
4696     #[inline]
4697     fn count(self) -> usize {
4698         self.len()
4699     }
4700
4701     #[inline]
4702     fn nth(&mut self, n: usize) -> Option<Self::Item> {
4703         let (start, overflow) = n.overflowing_mul(self.chunk_size);
4704         if start >= self.v.len() || overflow {
4705             self.v = &[];
4706             None
4707         } else {
4708             let end = match start.checked_add(self.chunk_size) {
4709                 Some(sum) => cmp::min(self.v.len(), sum),
4710                 None => self.v.len(),
4711             };
4712             let nth = &self.v[start..end];
4713             self.v = &self.v[end..];
4714             Some(nth)
4715         }
4716     }
4717
4718     #[inline]
4719     fn last(self) -> Option<Self::Item> {
4720         if self.v.is_empty() {
4721             None
4722         } else {
4723             let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size;
4724             Some(&self.v[start..])
4725         }
4726     }
4727 }
4728
4729 #[stable(feature = "rust1", since = "1.0.0")]
4730 impl<'a, T> DoubleEndedIterator for Chunks<'a, T> {
4731     #[inline]
4732     fn next_back(&mut self) -> Option<&'a [T]> {
4733         if self.v.is_empty() {
4734             None
4735         } else {
4736             let remainder = self.v.len() % self.chunk_size;
4737             let chunksz = if remainder != 0 { remainder } else { self.chunk_size };
4738             let (fst, snd) = self.v.split_at(self.v.len() - chunksz);
4739             self.v = fst;
4740             Some(snd)
4741         }
4742     }
4743
4744     #[inline]
4745     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
4746         let len = self.len();
4747         if n >= len {
4748             self.v = &[];
4749             None
4750         } else {
4751             let start = (len - 1 - n) * self.chunk_size;
4752             let end = match start.checked_add(self.chunk_size) {
4753                 Some(res) => cmp::min(res, self.v.len()),
4754                 None => self.v.len(),
4755             };
4756             let nth_back = &self.v[start..end];
4757             self.v = &self.v[..start];
4758             Some(nth_back)
4759         }
4760     }
4761 }
4762
4763 #[stable(feature = "rust1", since = "1.0.0")]
4764 impl<T> ExactSizeIterator for Chunks<'_, T> {}
4765
4766 #[unstable(feature = "trusted_len", issue = "37572")]
4767 unsafe impl<T> TrustedLen for Chunks<'_, T> {}
4768
4769 #[stable(feature = "fused", since = "1.26.0")]
4770 impl<T> FusedIterator for Chunks<'_, T> {}
4771
4772 #[doc(hidden)]
4773 unsafe impl<'a, T> TrustedRandomAccess for Chunks<'a, T> {
4774     unsafe fn get_unchecked(&mut self, i: usize) -> &'a [T] {
4775         let start = i * self.chunk_size;
4776         let end = match start.checked_add(self.chunk_size) {
4777             None => self.v.len(),
4778             Some(end) => cmp::min(end, self.v.len()),
4779         };
4780         from_raw_parts(self.v.as_ptr().add(start), end - start)
4781     }
4782     fn may_have_side_effect() -> bool {
4783         false
4784     }
4785 }
4786
4787 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
4788 /// elements at a time), starting at the beginning of the slice.
4789 ///
4790 /// When the slice len is not evenly divided by the chunk size, the last slice
4791 /// of the iteration will be the remainder.
4792 ///
4793 /// This struct is created by the [`chunks_mut`] method on [slices].
4794 ///
4795 /// [`chunks_mut`]: ../../std/primitive.slice.html#method.chunks_mut
4796 /// [slices]: ../../std/primitive.slice.html
4797 #[derive(Debug)]
4798 #[stable(feature = "rust1", since = "1.0.0")]
4799 pub struct ChunksMut<'a, T: 'a> {
4800     v: &'a mut [T],
4801     chunk_size: usize,
4802 }
4803
4804 #[stable(feature = "rust1", since = "1.0.0")]
4805 impl<'a, T> Iterator for ChunksMut<'a, T> {
4806     type Item = &'a mut [T];
4807
4808     #[inline]
4809     fn next(&mut self) -> Option<&'a mut [T]> {
4810         if self.v.is_empty() {
4811             None
4812         } else {
4813             let sz = cmp::min(self.v.len(), self.chunk_size);
4814             let tmp = mem::replace(&mut self.v, &mut []);
4815             let (head, tail) = tmp.split_at_mut(sz);
4816             self.v = tail;
4817             Some(head)
4818         }
4819     }
4820
4821     #[inline]
4822     fn size_hint(&self) -> (usize, Option<usize>) {
4823         if self.v.is_empty() {
4824             (0, Some(0))
4825         } else {
4826             let n = self.v.len() / self.chunk_size;
4827             let rem = self.v.len() % self.chunk_size;
4828             let n = if rem > 0 { n + 1 } else { n };
4829             (n, Some(n))
4830         }
4831     }
4832
4833     #[inline]
4834     fn count(self) -> usize {
4835         self.len()
4836     }
4837
4838     #[inline]
4839     fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
4840         let (start, overflow) = n.overflowing_mul(self.chunk_size);
4841         if start >= self.v.len() || overflow {
4842             self.v = &mut [];
4843             None
4844         } else {
4845             let end = match start.checked_add(self.chunk_size) {
4846                 Some(sum) => cmp::min(self.v.len(), sum),
4847                 None => self.v.len(),
4848             };
4849             let tmp = mem::replace(&mut self.v, &mut []);
4850             let (head, tail) = tmp.split_at_mut(end);
4851             let (_, nth) = head.split_at_mut(start);
4852             self.v = tail;
4853             Some(nth)
4854         }
4855     }
4856
4857     #[inline]
4858     fn last(self) -> Option<Self::Item> {
4859         if self.v.is_empty() {
4860             None
4861         } else {
4862             let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size;
4863             Some(&mut self.v[start..])
4864         }
4865     }
4866 }
4867
4868 #[stable(feature = "rust1", since = "1.0.0")]
4869 impl<'a, T> DoubleEndedIterator for ChunksMut<'a, T> {
4870     #[inline]
4871     fn next_back(&mut self) -> Option<&'a mut [T]> {
4872         if self.v.is_empty() {
4873             None
4874         } else {
4875             let remainder = self.v.len() % self.chunk_size;
4876             let sz = if remainder != 0 { remainder } else { self.chunk_size };
4877             let tmp = mem::replace(&mut self.v, &mut []);
4878             let tmp_len = tmp.len();
4879             let (head, tail) = tmp.split_at_mut(tmp_len - sz);
4880             self.v = head;
4881             Some(tail)
4882         }
4883     }
4884
4885     #[inline]
4886     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
4887         let len = self.len();
4888         if n >= len {
4889             self.v = &mut [];
4890             None
4891         } else {
4892             let start = (len - 1 - n) * self.chunk_size;
4893             let end = match start.checked_add(self.chunk_size) {
4894                 Some(res) => cmp::min(res, self.v.len()),
4895                 None => self.v.len(),
4896             };
4897             let (temp, _tail) = mem::replace(&mut self.v, &mut []).split_at_mut(end);
4898             let (head, nth_back) = temp.split_at_mut(start);
4899             self.v = head;
4900             Some(nth_back)
4901         }
4902     }
4903 }
4904
4905 #[stable(feature = "rust1", since = "1.0.0")]
4906 impl<T> ExactSizeIterator for ChunksMut<'_, T> {}
4907
4908 #[unstable(feature = "trusted_len", issue = "37572")]
4909 unsafe impl<T> TrustedLen for ChunksMut<'_, T> {}
4910
4911 #[stable(feature = "fused", since = "1.26.0")]
4912 impl<T> FusedIterator for ChunksMut<'_, T> {}
4913
4914 #[doc(hidden)]
4915 unsafe impl<'a, T> TrustedRandomAccess for ChunksMut<'a, T> {
4916     unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut [T] {
4917         let start = i * self.chunk_size;
4918         let end = match start.checked_add(self.chunk_size) {
4919             None => self.v.len(),
4920             Some(end) => cmp::min(end, self.v.len()),
4921         };
4922         from_raw_parts_mut(self.v.as_mut_ptr().add(start), end - start)
4923     }
4924     fn may_have_side_effect() -> bool {
4925         false
4926     }
4927 }
4928
4929 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
4930 /// time), starting at the beginning of the slice.
4931 ///
4932 /// When the slice len is not evenly divided by the chunk size, the last
4933 /// up to `chunk_size-1` elements will be omitted but can be retrieved from
4934 /// the [`remainder`] function from the iterator.
4935 ///
4936 /// This struct is created by the [`chunks_exact`] method on [slices].
4937 ///
4938 /// [`chunks_exact`]: ../../std/primitive.slice.html#method.chunks_exact
4939 /// [`remainder`]: ../../std/slice/struct.ChunksExact.html#method.remainder
4940 /// [slices]: ../../std/primitive.slice.html
4941 #[derive(Debug)]
4942 #[stable(feature = "chunks_exact", since = "1.31.0")]
4943 pub struct ChunksExact<'a, T: 'a> {
4944     v: &'a [T],
4945     rem: &'a [T],
4946     chunk_size: usize,
4947 }
4948
4949 impl<'a, T> ChunksExact<'a, T> {
4950     /// Returns the remainder of the original slice that is not going to be
4951     /// returned by the iterator. The returned slice has at most `chunk_size-1`
4952     /// elements.
4953     #[stable(feature = "chunks_exact", since = "1.31.0")]
4954     pub fn remainder(&self) -> &'a [T] {
4955         self.rem
4956     }
4957 }
4958
4959 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
4960 #[stable(feature = "chunks_exact", since = "1.31.0")]
4961 impl<T> Clone for ChunksExact<'_, T> {
4962     fn clone(&self) -> Self {
4963         ChunksExact { v: self.v, rem: self.rem, chunk_size: self.chunk_size }
4964     }
4965 }
4966
4967 #[stable(feature = "chunks_exact", since = "1.31.0")]
4968 impl<'a, T> Iterator for ChunksExact<'a, T> {
4969     type Item = &'a [T];
4970
4971     #[inline]
4972     fn next(&mut self) -> Option<&'a [T]> {
4973         if self.v.len() < self.chunk_size {
4974             None
4975         } else {
4976             let (fst, snd) = self.v.split_at(self.chunk_size);
4977             self.v = snd;
4978             Some(fst)
4979         }
4980     }
4981
4982     #[inline]
4983     fn size_hint(&self) -> (usize, Option<usize>) {
4984         let n = self.v.len() / self.chunk_size;
4985         (n, Some(n))
4986     }
4987
4988     #[inline]
4989     fn count(self) -> usize {
4990         self.len()
4991     }
4992
4993     #[inline]
4994     fn nth(&mut self, n: usize) -> Option<Self::Item> {
4995         let (start, overflow) = n.overflowing_mul(self.chunk_size);
4996         if start >= self.v.len() || overflow {
4997             self.v = &[];
4998             None
4999         } else {
5000             let (_, snd) = self.v.split_at(start);
5001             self.v = snd;
5002             self.next()
5003         }
5004     }
5005
5006     #[inline]
5007     fn last(mut self) -> Option<Self::Item> {
5008         self.next_back()
5009     }
5010 }
5011
5012 #[stable(feature = "chunks_exact", since = "1.31.0")]
5013 impl<'a, T> DoubleEndedIterator for ChunksExact<'a, T> {
5014     #[inline]
5015     fn next_back(&mut self) -> Option<&'a [T]> {
5016         if self.v.len() < self.chunk_size {
5017             None
5018         } else {
5019             let (fst, snd) = self.v.split_at(self.v.len() - self.chunk_size);
5020             self.v = fst;
5021             Some(snd)
5022         }
5023     }
5024
5025     #[inline]
5026     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
5027         let len = self.len();
5028         if n >= len {
5029             self.v = &[];
5030             None
5031         } else {
5032             let start = (len - 1 - n) * self.chunk_size;
5033             let end = start + self.chunk_size;
5034             let nth_back = &self.v[start..end];
5035             self.v = &self.v[..start];
5036             Some(nth_back)
5037         }
5038     }
5039 }
5040
5041 #[stable(feature = "chunks_exact", since = "1.31.0")]
5042 impl<T> ExactSizeIterator for ChunksExact<'_, T> {
5043     fn is_empty(&self) -> bool {
5044         self.v.is_empty()
5045     }
5046 }
5047
5048 #[unstable(feature = "trusted_len", issue = "37572")]
5049 unsafe impl<T> TrustedLen for ChunksExact<'_, T> {}
5050
5051 #[stable(feature = "chunks_exact", since = "1.31.0")]
5052 impl<T> FusedIterator for ChunksExact<'_, T> {}
5053
5054 #[doc(hidden)]
5055 #[stable(feature = "chunks_exact", since = "1.31.0")]
5056 unsafe impl<'a, T> TrustedRandomAccess for ChunksExact<'a, T> {
5057     unsafe fn get_unchecked(&mut self, i: usize) -> &'a [T] {
5058         let start = i * self.chunk_size;
5059         from_raw_parts(self.v.as_ptr().add(start), self.chunk_size)
5060     }
5061     fn may_have_side_effect() -> bool {
5062         false
5063     }
5064 }
5065
5066 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
5067 /// elements at a time), starting at the beginning of the slice.
5068 ///
5069 /// When the slice len is not evenly divided by the chunk size, the last up to
5070 /// `chunk_size-1` elements will be omitted but can be retrieved from the
5071 /// [`into_remainder`] function from the iterator.
5072 ///
5073 /// This struct is created by the [`chunks_exact_mut`] method on [slices].
5074 ///
5075 /// [`chunks_exact_mut`]: ../../std/primitive.slice.html#method.chunks_exact_mut
5076 /// [`into_remainder`]: ../../std/slice/struct.ChunksExactMut.html#method.into_remainder
5077 /// [slices]: ../../std/primitive.slice.html
5078 #[derive(Debug)]
5079 #[stable(feature = "chunks_exact", since = "1.31.0")]
5080 pub struct ChunksExactMut<'a, T: 'a> {
5081     v: &'a mut [T],
5082     rem: &'a mut [T],
5083     chunk_size: usize,
5084 }
5085
5086 impl<'a, T> ChunksExactMut<'a, T> {
5087     /// Returns the remainder of the original slice that is not going to be
5088     /// returned by the iterator. The returned slice has at most `chunk_size-1`
5089     /// elements.
5090     #[stable(feature = "chunks_exact", since = "1.31.0")]
5091     pub fn into_remainder(self) -> &'a mut [T] {
5092         self.rem
5093     }
5094 }
5095
5096 #[stable(feature = "chunks_exact", since = "1.31.0")]
5097 impl<'a, T> Iterator for ChunksExactMut<'a, T> {
5098     type Item = &'a mut [T];
5099
5100     #[inline]
5101     fn next(&mut self) -> Option<&'a mut [T]> {
5102         if self.v.len() < self.chunk_size {
5103             None
5104         } else {
5105             let tmp = mem::replace(&mut self.v, &mut []);
5106             let (head, tail) = tmp.split_at_mut(self.chunk_size);
5107             self.v = tail;
5108             Some(head)
5109         }
5110     }
5111
5112     #[inline]
5113     fn size_hint(&self) -> (usize, Option<usize>) {
5114         let n = self.v.len() / self.chunk_size;
5115         (n, Some(n))
5116     }
5117
5118     #[inline]
5119     fn count(self) -> usize {
5120         self.len()
5121     }
5122
5123     #[inline]
5124     fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
5125         let (start, overflow) = n.overflowing_mul(self.chunk_size);
5126         if start >= self.v.len() || overflow {
5127             self.v = &mut [];
5128             None
5129         } else {
5130             let tmp = mem::replace(&mut self.v, &mut []);
5131             let (_, snd) = tmp.split_at_mut(start);
5132             self.v = snd;
5133             self.next()
5134         }
5135     }
5136
5137     #[inline]
5138     fn last(mut self) -> Option<Self::Item> {
5139         self.next_back()
5140     }
5141 }
5142
5143 #[stable(feature = "chunks_exact", since = "1.31.0")]
5144 impl<'a, T> DoubleEndedIterator for ChunksExactMut<'a, T> {
5145     #[inline]
5146     fn next_back(&mut self) -> Option<&'a mut [T]> {
5147         if self.v.len() < self.chunk_size {
5148             None
5149         } else {
5150             let tmp = mem::replace(&mut self.v, &mut []);
5151             let tmp_len = tmp.len();
5152             let (head, tail) = tmp.split_at_mut(tmp_len - self.chunk_size);
5153             self.v = head;
5154             Some(tail)
5155         }
5156     }
5157
5158     #[inline]
5159     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
5160         let len = self.len();
5161         if n >= len {
5162             self.v = &mut [];
5163             None
5164         } else {
5165             let start = (len - 1 - n) * self.chunk_size;
5166             let end = start + self.chunk_size;
5167             let (temp, _tail) = mem::replace(&mut self.v, &mut []).split_at_mut(end);
5168             let (head, nth_back) = temp.split_at_mut(start);
5169             self.v = head;
5170             Some(nth_back)
5171         }
5172     }
5173 }
5174
5175 #[stable(feature = "chunks_exact", since = "1.31.0")]
5176 impl<T> ExactSizeIterator for ChunksExactMut<'_, T> {
5177     fn is_empty(&self) -> bool {
5178         self.v.is_empty()
5179     }
5180 }
5181
5182 #[unstable(feature = "trusted_len", issue = "37572")]
5183 unsafe impl<T> TrustedLen for ChunksExactMut<'_, T> {}
5184
5185 #[stable(feature = "chunks_exact", since = "1.31.0")]
5186 impl<T> FusedIterator for ChunksExactMut<'_, T> {}
5187
5188 #[doc(hidden)]
5189 #[stable(feature = "chunks_exact", since = "1.31.0")]
5190 unsafe impl<'a, T> TrustedRandomAccess for ChunksExactMut<'a, T> {
5191     unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut [T] {
5192         let start = i * self.chunk_size;
5193         from_raw_parts_mut(self.v.as_mut_ptr().add(start), self.chunk_size)
5194     }
5195     fn may_have_side_effect() -> bool {
5196         false
5197     }
5198 }
5199
5200 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
5201 /// time), starting at the end of the slice.
5202 ///
5203 /// When the slice len is not evenly divided by the chunk size, the last slice
5204 /// of the iteration will be the remainder.
5205 ///
5206 /// This struct is created by the [`rchunks`] method on [slices].
5207 ///
5208 /// [`rchunks`]: ../../std/primitive.slice.html#method.rchunks
5209 /// [slices]: ../../std/primitive.slice.html
5210 #[derive(Debug)]
5211 #[stable(feature = "rchunks", since = "1.31.0")]
5212 pub struct RChunks<'a, T: 'a> {
5213     v: &'a [T],
5214     chunk_size: usize,
5215 }
5216
5217 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
5218 #[stable(feature = "rchunks", since = "1.31.0")]
5219 impl<T> Clone for RChunks<'_, T> {
5220     fn clone(&self) -> Self {
5221         RChunks { v: self.v, chunk_size: self.chunk_size }
5222     }
5223 }
5224
5225 #[stable(feature = "rchunks", since = "1.31.0")]
5226 impl<'a, T> Iterator for RChunks<'a, T> {
5227     type Item = &'a [T];
5228
5229     #[inline]
5230     fn next(&mut self) -> Option<&'a [T]> {
5231         if self.v.is_empty() {
5232             None
5233         } else {
5234             let chunksz = cmp::min(self.v.len(), self.chunk_size);
5235             let (fst, snd) = self.v.split_at(self.v.len() - chunksz);
5236             self.v = fst;
5237             Some(snd)
5238         }
5239     }
5240
5241     #[inline]
5242     fn size_hint(&self) -> (usize, Option<usize>) {
5243         if self.v.is_empty() {
5244             (0, Some(0))
5245         } else {
5246             let n = self.v.len() / self.chunk_size;
5247             let rem = self.v.len() % self.chunk_size;
5248             let n = if rem > 0 { n + 1 } else { n };
5249             (n, Some(n))
5250         }
5251     }
5252
5253     #[inline]
5254     fn count(self) -> usize {
5255         self.len()
5256     }
5257
5258     #[inline]
5259     fn nth(&mut self, n: usize) -> Option<Self::Item> {
5260         let (end, overflow) = n.overflowing_mul(self.chunk_size);
5261         if end >= self.v.len() || overflow {
5262             self.v = &[];
5263             None
5264         } else {
5265             // Can't underflow because of the check above
5266             let end = self.v.len() - end;
5267             let start = match end.checked_sub(self.chunk_size) {
5268                 Some(sum) => sum,
5269                 None => 0,
5270             };
5271             let nth = &self.v[start..end];
5272             self.v = &self.v[0..start];
5273             Some(nth)
5274         }
5275     }
5276
5277     #[inline]
5278     fn last(self) -> Option<Self::Item> {
5279         if self.v.is_empty() {
5280             None
5281         } else {
5282             let rem = self.v.len() % self.chunk_size;
5283             let end = if rem == 0 { self.chunk_size } else { rem };
5284             Some(&self.v[0..end])
5285         }
5286     }
5287 }
5288
5289 #[stable(feature = "rchunks", since = "1.31.0")]
5290 impl<'a, T> DoubleEndedIterator for RChunks<'a, T> {
5291     #[inline]
5292     fn next_back(&mut self) -> Option<&'a [T]> {
5293         if self.v.is_empty() {
5294             None
5295         } else {
5296             let remainder = self.v.len() % self.chunk_size;
5297             let chunksz = if remainder != 0 { remainder } else { self.chunk_size };
5298             let (fst, snd) = self.v.split_at(chunksz);
5299             self.v = snd;
5300             Some(fst)
5301         }
5302     }
5303
5304     #[inline]
5305     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
5306         let len = self.len();
5307         if n >= len {
5308             self.v = &[];
5309             None
5310         } else {
5311             // can't underflow because `n < len`
5312             let offset_from_end = (len - 1 - n) * self.chunk_size;
5313             let end = self.v.len() - offset_from_end;
5314             let start = end.saturating_sub(self.chunk_size);
5315             let nth_back = &self.v[start..end];
5316             self.v = &self.v[end..];
5317             Some(nth_back)
5318         }
5319     }
5320 }
5321
5322 #[stable(feature = "rchunks", since = "1.31.0")]
5323 impl<T> ExactSizeIterator for RChunks<'_, T> {}
5324
5325 #[unstable(feature = "trusted_len", issue = "37572")]
5326 unsafe impl<T> TrustedLen for RChunks<'_, T> {}
5327
5328 #[stable(feature = "rchunks", since = "1.31.0")]
5329 impl<T> FusedIterator for RChunks<'_, T> {}
5330
5331 #[doc(hidden)]
5332 #[stable(feature = "rchunks", since = "1.31.0")]
5333 unsafe impl<'a, T> TrustedRandomAccess for RChunks<'a, T> {
5334     unsafe fn get_unchecked(&mut self, i: usize) -> &'a [T] {
5335         let end = self.v.len() - i * self.chunk_size;
5336         let start = match end.checked_sub(self.chunk_size) {
5337             None => 0,
5338             Some(start) => start,
5339         };
5340         from_raw_parts(self.v.as_ptr().add(start), end - start)
5341     }
5342     fn may_have_side_effect() -> bool {
5343         false
5344     }
5345 }
5346
5347 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
5348 /// elements at a time), starting at the end of the slice.
5349 ///
5350 /// When the slice len is not evenly divided by the chunk size, the last slice
5351 /// of the iteration will be the remainder.
5352 ///
5353 /// This struct is created by the [`rchunks_mut`] method on [slices].
5354 ///
5355 /// [`rchunks_mut`]: ../../std/primitive.slice.html#method.rchunks_mut
5356 /// [slices]: ../../std/primitive.slice.html
5357 #[derive(Debug)]
5358 #[stable(feature = "rchunks", since = "1.31.0")]
5359 pub struct RChunksMut<'a, T: 'a> {
5360     v: &'a mut [T],
5361     chunk_size: usize,
5362 }
5363
5364 #[stable(feature = "rchunks", since = "1.31.0")]
5365 impl<'a, T> Iterator for RChunksMut<'a, T> {
5366     type Item = &'a mut [T];
5367
5368     #[inline]
5369     fn next(&mut self) -> Option<&'a mut [T]> {
5370         if self.v.is_empty() {
5371             None
5372         } else {
5373             let sz = cmp::min(self.v.len(), self.chunk_size);
5374             let tmp = mem::replace(&mut self.v, &mut []);
5375             let tmp_len = tmp.len();
5376             let (head, tail) = tmp.split_at_mut(tmp_len - sz);
5377             self.v = head;
5378             Some(tail)
5379         }
5380     }
5381
5382     #[inline]
5383     fn size_hint(&self) -> (usize, Option<usize>) {
5384         if self.v.is_empty() {
5385             (0, Some(0))
5386         } else {
5387             let n = self.v.len() / self.chunk_size;
5388             let rem = self.v.len() % self.chunk_size;
5389             let n = if rem > 0 { n + 1 } else { n };
5390             (n, Some(n))
5391         }
5392     }
5393
5394     #[inline]
5395     fn count(self) -> usize {
5396         self.len()
5397     }
5398
5399     #[inline]
5400     fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
5401         let (end, overflow) = n.overflowing_mul(self.chunk_size);
5402         if end >= self.v.len() || overflow {
5403             self.v = &mut [];
5404             None
5405         } else {
5406             // Can't underflow because of the check above
5407             let end = self.v.len() - end;
5408             let start = match end.checked_sub(self.chunk_size) {
5409                 Some(sum) => sum,
5410                 None => 0,
5411             };
5412             let tmp = mem::replace(&mut self.v, &mut []);
5413             let (head, tail) = tmp.split_at_mut(start);
5414             let (nth, _) = tail.split_at_mut(end - start);
5415             self.v = head;
5416             Some(nth)
5417         }
5418     }
5419
5420     #[inline]
5421     fn last(self) -> Option<Self::Item> {
5422         if self.v.is_empty() {
5423             None
5424         } else {
5425             let rem = self.v.len() % self.chunk_size;
5426             let end = if rem == 0 { self.chunk_size } else { rem };
5427             Some(&mut self.v[0..end])
5428         }
5429     }
5430 }
5431
5432 #[stable(feature = "rchunks", since = "1.31.0")]
5433 impl<'a, T> DoubleEndedIterator for RChunksMut<'a, T> {
5434     #[inline]
5435     fn next_back(&mut self) -> Option<&'a mut [T]> {
5436         if self.v.is_empty() {
5437             None
5438         } else {
5439             let remainder = self.v.len() % self.chunk_size;
5440             let sz = if remainder != 0 { remainder } else { self.chunk_size };
5441             let tmp = mem::replace(&mut self.v, &mut []);
5442             let (head, tail) = tmp.split_at_mut(sz);
5443             self.v = tail;
5444             Some(head)
5445         }
5446     }
5447
5448     #[inline]
5449     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
5450         let len = self.len();
5451         if n >= len {
5452             self.v = &mut [];
5453             None
5454         } else {
5455             // can't underflow because `n < len`
5456             let offset_from_end = (len - 1 - n) * self.chunk_size;
5457             let end = self.v.len() - offset_from_end;
5458             let start = end.saturating_sub(self.chunk_size);
5459             let (tmp, tail) = mem::replace(&mut self.v, &mut []).split_at_mut(end);
5460             let (_, nth_back) = tmp.split_at_mut(start);
5461             self.v = tail;
5462             Some(nth_back)
5463         }
5464     }
5465 }
5466
5467 #[stable(feature = "rchunks", since = "1.31.0")]
5468 impl<T> ExactSizeIterator for RChunksMut<'_, T> {}
5469
5470 #[unstable(feature = "trusted_len", issue = "37572")]
5471 unsafe impl<T> TrustedLen for RChunksMut<'_, T> {}
5472
5473 #[stable(feature = "rchunks", since = "1.31.0")]
5474 impl<T> FusedIterator for RChunksMut<'_, T> {}
5475
5476 #[doc(hidden)]
5477 #[stable(feature = "rchunks", since = "1.31.0")]
5478 unsafe impl<'a, T> TrustedRandomAccess for RChunksMut<'a, T> {
5479     unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut [T] {
5480         let end = self.v.len() - i * self.chunk_size;
5481         let start = match end.checked_sub(self.chunk_size) {
5482             None => 0,
5483             Some(start) => start,
5484         };
5485         from_raw_parts_mut(self.v.as_mut_ptr().add(start), end - start)
5486     }
5487     fn may_have_side_effect() -> bool {
5488         false
5489     }
5490 }
5491
5492 /// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
5493 /// time), starting at the end of the slice.
5494 ///
5495 /// When the slice len is not evenly divided by the chunk size, the last
5496 /// up to `chunk_size-1` elements will be omitted but can be retrieved from
5497 /// the [`remainder`] function from the iterator.
5498 ///
5499 /// This struct is created by the [`rchunks_exact`] method on [slices].
5500 ///
5501 /// [`rchunks_exact`]: ../../std/primitive.slice.html#method.rchunks_exact
5502 /// [`remainder`]: ../../std/slice/struct.ChunksExact.html#method.remainder
5503 /// [slices]: ../../std/primitive.slice.html
5504 #[derive(Debug)]
5505 #[stable(feature = "rchunks", since = "1.31.0")]
5506 pub struct RChunksExact<'a, T: 'a> {
5507     v: &'a [T],
5508     rem: &'a [T],
5509     chunk_size: usize,
5510 }
5511
5512 impl<'a, T> RChunksExact<'a, T> {
5513     /// Returns the remainder of the original slice that is not going to be
5514     /// returned by the iterator. The returned slice has at most `chunk_size-1`
5515     /// elements.
5516     #[stable(feature = "rchunks", since = "1.31.0")]
5517     pub fn remainder(&self) -> &'a [T] {
5518         self.rem
5519     }
5520 }
5521
5522 // FIXME(#26925) Remove in favor of `#[derive(Clone)]`
5523 #[stable(feature = "rchunks", since = "1.31.0")]
5524 impl<'a, T> Clone for RChunksExact<'a, T> {
5525     fn clone(&self) -> RChunksExact<'a, T> {
5526         RChunksExact { v: self.v, rem: self.rem, chunk_size: self.chunk_size }
5527     }
5528 }
5529
5530 #[stable(feature = "rchunks", since = "1.31.0")]
5531 impl<'a, T> Iterator for RChunksExact<'a, T> {
5532     type Item = &'a [T];
5533
5534     #[inline]
5535     fn next(&mut self) -> Option<&'a [T]> {
5536         if self.v.len() < self.chunk_size {
5537             None
5538         } else {
5539             let (fst, snd) = self.v.split_at(self.v.len() - self.chunk_size);
5540             self.v = fst;
5541             Some(snd)
5542         }
5543     }
5544
5545     #[inline]
5546     fn size_hint(&self) -> (usize, Option<usize>) {
5547         let n = self.v.len() / self.chunk_size;
5548         (n, Some(n))
5549     }
5550
5551     #[inline]
5552     fn count(self) -> usize {
5553         self.len()
5554     }
5555
5556     #[inline]
5557     fn nth(&mut self, n: usize) -> Option<Self::Item> {
5558         let (end, overflow) = n.overflowing_mul(self.chunk_size);
5559         if end >= self.v.len() || overflow {
5560             self.v = &[];
5561             None
5562         } else {
5563             let (fst, _) = self.v.split_at(self.v.len() - end);
5564             self.v = fst;
5565             self.next()
5566         }
5567     }
5568
5569     #[inline]
5570     fn last(mut self) -> Option<Self::Item> {
5571         self.next_back()
5572     }
5573 }
5574
5575 #[stable(feature = "rchunks", since = "1.31.0")]
5576 impl<'a, T> DoubleEndedIterator for RChunksExact<'a, T> {
5577     #[inline]
5578     fn next_back(&mut self) -> Option<&'a [T]> {
5579         if self.v.len() < self.chunk_size {
5580             None
5581         } else {
5582             let (fst, snd) = self.v.split_at(self.chunk_size);
5583             self.v = snd;
5584             Some(fst)
5585         }
5586     }
5587
5588     #[inline]
5589     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
5590         let len = self.len();
5591         if n >= len {
5592             self.v = &[];
5593             None
5594         } else {
5595             // now that we know that `n` corresponds to a chunk,
5596             // none of these operations can underflow/overflow
5597             let offset = (len - n) * self.chunk_size;
5598             let start = self.v.len() - offset;
5599             let end = start + self.chunk_size;
5600             let nth_back = &self.v[start..end];
5601             self.v = &self.v[end..];
5602             Some(nth_back)
5603         }
5604     }
5605 }
5606
5607 #[stable(feature = "rchunks", since = "1.31.0")]
5608 impl<'a, T> ExactSizeIterator for RChunksExact<'a, T> {
5609     fn is_empty(&self) -> bool {
5610         self.v.is_empty()
5611     }
5612 }
5613
5614 #[unstable(feature = "trusted_len", issue = "37572")]
5615 unsafe impl<T> TrustedLen for RChunksExact<'_, T> {}
5616
5617 #[stable(feature = "rchunks", since = "1.31.0")]
5618 impl<T> FusedIterator for RChunksExact<'_, T> {}
5619
5620 #[doc(hidden)]
5621 #[stable(feature = "rchunks", since = "1.31.0")]
5622 unsafe impl<'a, T> TrustedRandomAccess for RChunksExact<'a, T> {
5623     unsafe fn get_unchecked(&mut self, i: usize) -> &'a [T] {
5624         let end = self.v.len() - i * self.chunk_size;
5625         let start = end - self.chunk_size;
5626         from_raw_parts(self.v.as_ptr().add(start), self.chunk_size)
5627     }
5628     fn may_have_side_effect() -> bool {
5629         false
5630     }
5631 }
5632
5633 /// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
5634 /// elements at a time), starting at the end of the slice.
5635 ///
5636 /// When the slice len is not evenly divided by the chunk size, the last up to
5637 /// `chunk_size-1` elements will be omitted but can be retrieved from the
5638 /// [`into_remainder`] function from the iterator.
5639 ///
5640 /// This struct is created by the [`rchunks_exact_mut`] method on [slices].
5641 ///
5642 /// [`rchunks_exact_mut`]: ../../std/primitive.slice.html#method.rchunks_exact_mut
5643 /// [`into_remainder`]: ../../std/slice/struct.ChunksExactMut.html#method.into_remainder
5644 /// [slices]: ../../std/primitive.slice.html
5645 #[derive(Debug)]
5646 #[stable(feature = "rchunks", since = "1.31.0")]
5647 pub struct RChunksExactMut<'a, T: 'a> {
5648     v: &'a mut [T],
5649     rem: &'a mut [T],
5650     chunk_size: usize,
5651 }
5652
5653 impl<'a, T> RChunksExactMut<'a, T> {
5654     /// Returns the remainder of the original slice that is not going to be
5655     /// returned by the iterator. The returned slice has at most `chunk_size-1`
5656     /// elements.
5657     #[stable(feature = "rchunks", since = "1.31.0")]
5658     pub fn into_remainder(self) -> &'a mut [T] {
5659         self.rem
5660     }
5661 }
5662
5663 #[stable(feature = "rchunks", since = "1.31.0")]
5664 impl<'a, T> Iterator for RChunksExactMut<'a, T> {
5665     type Item = &'a mut [T];
5666
5667     #[inline]
5668     fn next(&mut self) -> Option<&'a mut [T]> {
5669         if self.v.len() < self.chunk_size {
5670             None
5671         } else {
5672             let tmp = mem::replace(&mut self.v, &mut []);
5673             let tmp_len = tmp.len();
5674             let (head, tail) = tmp.split_at_mut(tmp_len - self.chunk_size);
5675             self.v = head;
5676             Some(tail)
5677         }
5678     }
5679
5680     #[inline]
5681     fn size_hint(&self) -> (usize, Option<usize>) {
5682         let n = self.v.len() / self.chunk_size;
5683         (n, Some(n))
5684     }
5685
5686     #[inline]
5687     fn count(self) -> usize {
5688         self.len()
5689     }
5690
5691     #[inline]
5692     fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
5693         let (end, overflow) = n.overflowing_mul(self.chunk_size);
5694         if end >= self.v.len() || overflow {
5695             self.v = &mut [];
5696             None
5697         } else {
5698             let tmp = mem::replace(&mut self.v, &mut []);
5699             let tmp_len = tmp.len();
5700             let (fst, _) = tmp.split_at_mut(tmp_len - end);
5701             self.v = fst;
5702             self.next()
5703         }
5704     }
5705
5706     #[inline]
5707     fn last(mut self) -> Option<Self::Item> {
5708         self.next_back()
5709     }
5710 }
5711
5712 #[stable(feature = "rchunks", since = "1.31.0")]
5713 impl<'a, T> DoubleEndedIterator for RChunksExactMut<'a, T> {
5714     #[inline]
5715     fn next_back(&mut self) -> Option<&'a mut [T]> {
5716         if self.v.len() < self.chunk_size {
5717             None
5718         } else {
5719             let tmp = mem::replace(&mut self.v, &mut []);
5720             let (head, tail) = tmp.split_at_mut(self.chunk_size);
5721             self.v = tail;
5722             Some(head)
5723         }
5724     }
5725
5726     #[inline]
5727     fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
5728         let len = self.len();
5729         if n >= len {
5730             self.v = &mut [];
5731             None
5732         } else {
5733             // now that we know that `n` corresponds to a chunk,
5734             // none of these operations can underflow/overflow
5735             let offset = (len - n) * self.chunk_size;
5736             let start = self.v.len() - offset;
5737             let end = start + self.chunk_size;
5738             let (tmp, tail) = mem::replace(&mut self.v, &mut []).split_at_mut(end);
5739             let (_, nth_back) = tmp.split_at_mut(start);
5740             self.v = tail;
5741             Some(nth_back)
5742         }
5743     }
5744 }
5745
5746 #[stable(feature = "rchunks", since = "1.31.0")]
5747 impl<T> ExactSizeIterator for RChunksExactMut<'_, T> {
5748     fn is_empty(&self) -> bool {
5749         self.v.is_empty()
5750     }
5751 }
5752
5753 #[unstable(feature = "trusted_len", issue = "37572")]
5754 unsafe impl<T> TrustedLen for RChunksExactMut<'_, T> {}
5755
5756 #[stable(feature = "rchunks", since = "1.31.0")]
5757 impl<T> FusedIterator for RChunksExactMut<'_, T> {}
5758
5759 #[doc(hidden)]
5760 #[stable(feature = "rchunks", since = "1.31.0")]
5761 unsafe impl<'a, T> TrustedRandomAccess for RChunksExactMut<'a, T> {
5762     unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut [T] {
5763         let end = self.v.len() - i * self.chunk_size;
5764         let start = end - self.chunk_size;
5765         from_raw_parts_mut(self.v.as_mut_ptr().add(start), self.chunk_size)
5766     }
5767     fn may_have_side_effect() -> bool {
5768         false
5769     }
5770 }
5771
5772 //
5773 // Free functions
5774 //
5775
5776 /// Forms a slice from a pointer and a length.
5777 ///
5778 /// The `len` argument is the number of **elements**, not the number of bytes.
5779 ///
5780 /// # Safety
5781 ///
5782 /// Behavior is undefined if any of the following conditions are violated:
5783 ///
5784 /// * `data` must be [valid] for reads for `len * mem::size_of::<T>()` many bytes,
5785 ///   and it must be properly aligned. This means in particular:
5786 ///
5787 ///     * The entire memory range of this slice must be contained within a single allocated object!
5788 ///       Slices can never span across multiple allocated objects. See [below](#incorrect-usage)
5789 ///       for an example incorrectly not taking this into account.
5790 ///     * `data` must be non-null and aligned even for zero-length slices. One
5791 ///       reason for this is that enum layout optimizations may rely on references
5792 ///       (including slices of any length) being aligned and non-null to distinguish
5793 ///       them from other data. You can obtain a pointer that is usable as `data`
5794 ///       for zero-length slices using [`NonNull::dangling()`].
5795 ///
5796 /// * The memory referenced by the returned slice must not be mutated for the duration
5797 ///   of lifetime `'a`, except inside an `UnsafeCell`.
5798 ///
5799 /// * The total size `len * mem::size_of::<T>()` of the slice must be no larger than `isize::MAX`.
5800 ///   See the safety documentation of [`pointer::offset`].
5801 ///
5802 /// # Caveat
5803 ///
5804 /// The lifetime for the returned slice is inferred from its usage. To
5805 /// prevent accidental misuse, it's suggested to tie the lifetime to whichever
5806 /// source lifetime is safe in the context, such as by providing a helper
5807 /// function taking the lifetime of a host value for the slice, or by explicit
5808 /// annotation.
5809 ///
5810 /// # Examples
5811 ///
5812 /// ```
5813 /// use std::slice;
5814 ///
5815 /// // manifest a slice for a single element
5816 /// let x = 42;
5817 /// let ptr = &x as *const _;
5818 /// let slice = unsafe { slice::from_raw_parts(ptr, 1) };
5819 /// assert_eq!(slice[0], 42);
5820 /// ```
5821 ///
5822 /// ### Incorrect usage
5823 ///
5824 /// The following `join_slices` function is **unsound** ⚠️
5825 ///
5826 /// ```rust,no_run
5827 /// use std::slice;
5828 ///
5829 /// fn join_slices<'a, T>(fst: &'a [T], snd: &'a [T]) -> &'a [T] {
5830 ///     let fst_end = fst.as_ptr().wrapping_add(fst.len());
5831 ///     let snd_start = snd.as_ptr();
5832 ///     assert_eq!(fst_end, snd_start, "Slices must be contiguous!");
5833 ///     unsafe {
5834 ///         // The assertion above ensures `fst` and `snd` are contiguous, but they might
5835 ///         // still be contained within _different allocated objects_, in which case
5836 ///         // creating this slice is undefined behavior.
5837 ///         slice::from_raw_parts(fst.as_ptr(), fst.len() + snd.len())
5838 ///     }
5839 /// }
5840 ///
5841 /// fn main() {
5842 ///     // `a` and `b` are different allocated objects...
5843 ///     let a = 42;
5844 ///     let b = 27;
5845 ///     // ... which may nevertheless be laid out contiguously in memory: | a | b |
5846 ///     let _ = join_slices(slice::from_ref(&a), slice::from_ref(&b)); // UB
5847 /// }
5848 /// ```
5849 ///
5850 /// [valid]: ../../std/ptr/index.html#safety
5851 /// [`NonNull::dangling()`]: ../../std/ptr/struct.NonNull.html#method.dangling
5852 /// [`pointer::offset`]: ../../std/primitive.pointer.html#method.offset
5853 #[inline]
5854 #[stable(feature = "rust1", since = "1.0.0")]
5855 pub unsafe fn from_raw_parts<'a, T>(data: *const T, len: usize) -> &'a [T] {
5856     debug_assert!(is_aligned_and_not_null(data), "attempt to create unaligned or null slice");
5857     debug_assert!(
5858         mem::size_of::<T>().saturating_mul(len) <= isize::MAX as usize,
5859         "attempt to create slice covering at least half the address space"
5860     );
5861     &*ptr::slice_from_raw_parts(data, len)
5862 }
5863
5864 /// Performs the same functionality as [`from_raw_parts`], except that a
5865 /// mutable slice is returned.
5866 ///
5867 /// # Safety
5868 ///
5869 /// Behavior is undefined if any of the following conditions are violated:
5870 ///
5871 /// * `data` must be [valid] for writes for `len * mem::size_of::<T>()` many bytes,
5872 ///   and it must be properly aligned. This means in particular:
5873 ///
5874 ///     * The entire memory range of this slice must be contained within a single allocated object!
5875 ///       Slices can never span across multiple allocated objects.
5876 ///     * `data` must be non-null and aligned even for zero-length slices. One
5877 ///       reason for this is that enum layout optimizations may rely on references
5878 ///       (including slices of any length) being aligned and non-null to distinguish
5879 ///       them from other data. You can obtain a pointer that is usable as `data`
5880 ///       for zero-length slices using [`NonNull::dangling()`].
5881 ///
5882 /// * The memory referenced by the returned slice must not be accessed through any other pointer
5883 ///   (not derived from the return value) for the duration of lifetime `'a`.
5884 ///   Both read and write accesses are forbidden.
5885 ///
5886 /// * The total size `len * mem::size_of::<T>()` of the slice must be no larger than `isize::MAX`.
5887 ///   See the safety documentation of [`pointer::offset`].
5888 ///
5889 /// [valid]: ../../std/ptr/index.html#safety
5890 /// [`NonNull::dangling()`]: ../../std/ptr/struct.NonNull.html#method.dangling
5891 /// [`pointer::offset`]: ../../std/primitive.pointer.html#method.offset
5892 /// [`from_raw_parts`]: ../../std/slice/fn.from_raw_parts.html
5893 #[inline]
5894 #[stable(feature = "rust1", since = "1.0.0")]
5895 pub unsafe fn from_raw_parts_mut<'a, T>(data: *mut T, len: usize) -> &'a mut [T] {
5896     debug_assert!(is_aligned_and_not_null(data), "attempt to create unaligned or null slice");
5897     debug_assert!(
5898         mem::size_of::<T>().saturating_mul(len) <= isize::MAX as usize,
5899         "attempt to create slice covering at least half the address space"
5900     );
5901     &mut *ptr::slice_from_raw_parts_mut(data, len)
5902 }
5903
5904 /// Converts a reference to T into a slice of length 1 (without copying).
5905 #[stable(feature = "from_ref", since = "1.28.0")]
5906 pub fn from_ref<T>(s: &T) -> &[T] {
5907     unsafe { from_raw_parts(s, 1) }
5908 }
5909
5910 /// Converts a reference to T into a slice of length 1 (without copying).
5911 #[stable(feature = "from_ref", since = "1.28.0")]
5912 pub fn from_mut<T>(s: &mut T) -> &mut [T] {
5913     unsafe { from_raw_parts_mut(s, 1) }
5914 }
5915
5916 // This function is public only because there is no other way to unit test heapsort.
5917 #[unstable(feature = "sort_internals", reason = "internal to sort module", issue = "none")]
5918 #[doc(hidden)]
5919 pub fn heapsort<T, F>(v: &mut [T], mut is_less: F)
5920 where
5921     F: FnMut(&T, &T) -> bool,
5922 {
5923     sort::heapsort(v, &mut is_less);
5924 }
5925
5926 //
5927 // Comparison traits
5928 //
5929
5930 extern "C" {
5931     /// Calls implementation provided memcmp.
5932     ///
5933     /// Interprets the data as u8.
5934     ///
5935     /// Returns 0 for equal, < 0 for less than and > 0 for greater
5936     /// than.
5937     // FIXME(#32610): Return type should be c_int
5938     fn memcmp(s1: *const u8, s2: *const u8, n: usize) -> i32;
5939 }
5940
5941 #[stable(feature = "rust1", since = "1.0.0")]
5942 impl<A, B> PartialEq<[B]> for [A]
5943 where
5944     A: PartialEq<B>,
5945 {
5946     fn eq(&self, other: &[B]) -> bool {
5947         SlicePartialEq::equal(self, other)
5948     }
5949
5950     fn ne(&self, other: &[B]) -> bool {
5951         SlicePartialEq::not_equal(self, other)
5952     }
5953 }
5954
5955 #[stable(feature = "rust1", since = "1.0.0")]
5956 impl<T: Eq> Eq for [T] {}
5957
5958 /// Implements comparison of vectors lexicographically.
5959 #[stable(feature = "rust1", since = "1.0.0")]
5960 impl<T: Ord> Ord for [T] {
5961     fn cmp(&self, other: &[T]) -> Ordering {
5962         SliceOrd::compare(self, other)
5963     }
5964 }
5965
5966 /// Implements comparison of vectors lexicographically.
5967 #[stable(feature = "rust1", since = "1.0.0")]
5968 impl<T: PartialOrd> PartialOrd for [T] {
5969     fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
5970         SlicePartialOrd::partial_compare(self, other)
5971     }
5972 }
5973
5974 #[doc(hidden)]
5975 // intermediate trait for specialization of slice's PartialEq
5976 trait SlicePartialEq<B> {
5977     fn equal(&self, other: &[B]) -> bool;
5978
5979     fn not_equal(&self, other: &[B]) -> bool {
5980         !self.equal(other)
5981     }
5982 }
5983
5984 // Generic slice equality
5985 impl<A, B> SlicePartialEq<B> for [A]
5986 where
5987     A: PartialEq<B>,
5988 {
5989     default fn equal(&self, other: &[B]) -> bool {
5990         if self.len() != other.len() {
5991             return false;
5992         }
5993
5994         self.iter().zip(other.iter()).all(|(x, y)| x == y)
5995     }
5996 }
5997
5998 // Use an equal-pointer optimization when types are `Eq`
5999 impl<A> SlicePartialEq<A> for [A]
6000 where
6001     A: PartialEq<A> + Eq,
6002 {
6003     default fn equal(&self, other: &[A]) -> bool {
6004         if self.len() != other.len() {
6005             return false;
6006         }
6007
6008         if self.as_ptr() == other.as_ptr() {
6009             return true;
6010         }
6011
6012         self.iter().zip(other.iter()).all(|(x, y)| x == y)
6013     }
6014 }
6015
6016 // Use memcmp for bytewise equality when the types allow
6017 impl<A> SlicePartialEq<A> for [A]
6018 where
6019     A: PartialEq<A> + BytewiseEquality,
6020 {
6021     fn equal(&self, other: &[A]) -> bool {
6022         if self.len() != other.len() {
6023             return false;
6024         }
6025         if self.as_ptr() == other.as_ptr() {
6026             return true;
6027         }
6028         unsafe {
6029             let size = mem::size_of_val(self);
6030             memcmp(self.as_ptr() as *const u8, other.as_ptr() as *const u8, size) == 0
6031         }
6032     }
6033 }
6034
6035 #[doc(hidden)]
6036 // intermediate trait for specialization of slice's PartialOrd
6037 trait SlicePartialOrd: Sized {
6038     fn partial_compare(left: &[Self], right: &[Self]) -> Option<Ordering>;
6039 }
6040
6041 impl<A: PartialOrd> SlicePartialOrd for A {
6042     default fn partial_compare(left: &[A], right: &[A]) -> Option<Ordering> {
6043         let l = cmp::min(left.len(), right.len());
6044
6045         // Slice to the loop iteration range to enable bound check
6046         // elimination in the compiler
6047         let lhs = &left[..l];
6048         let rhs = &right[..l];
6049
6050         for i in 0..l {
6051             match lhs[i].partial_cmp(&rhs[i]) {
6052                 Some(Ordering::Equal) => (),
6053                 non_eq => return non_eq,
6054             }
6055         }
6056
6057         left.len().partial_cmp(&right.len())
6058     }
6059 }
6060
6061 // This is the impl that we would like to have. Unfortunately it's not sound.
6062 // See `partial_ord_slice.rs`.
6063 /*
6064 impl<A> SlicePartialOrd for A
6065 where
6066     A: Ord,
6067 {
6068     default fn partial_compare(left: &[A], right: &[A]) -> Option<Ordering> {
6069         Some(SliceOrd::compare(left, right))
6070     }
6071 }
6072 */
6073
6074 impl<A: AlwaysApplicableOrd> SlicePartialOrd for A {
6075     fn partial_compare(left: &[A], right: &[A]) -> Option<Ordering> {
6076         Some(SliceOrd::compare(left, right))
6077     }
6078 }
6079
6080 trait AlwaysApplicableOrd: SliceOrd + Ord {}
6081
6082 macro_rules! always_applicable_ord {
6083     ($([$($p:tt)*] $t:ty,)*) => {
6084         $(impl<$($p)*> AlwaysApplicableOrd for $t {})*
6085     }
6086 }
6087
6088 always_applicable_ord! {
6089     [] u8, [] u16, [] u32, [] u64, [] u128, [] usize,
6090     [] i8, [] i16, [] i32, [] i64, [] i128, [] isize,
6091     [] bool, [] char,
6092     [T: ?Sized] *const T, [T: ?Sized] *mut T,
6093     [T: AlwaysApplicableOrd] &T,
6094     [T: AlwaysApplicableOrd] &mut T,
6095     [T: AlwaysApplicableOrd] Option<T>,
6096 }
6097
6098 #[doc(hidden)]
6099 // intermediate trait for specialization of slice's Ord
6100 trait SliceOrd: Sized {
6101     fn compare(left: &[Self], right: &[Self]) -> Ordering;
6102 }
6103
6104 impl<A: Ord> SliceOrd for A {
6105     default fn compare(left: &[Self], right: &[Self]) -> Ordering {
6106         let l = cmp::min(left.len(), right.len());
6107
6108         // Slice to the loop iteration range to enable bound check
6109         // elimination in the compiler
6110         let lhs = &left[..l];
6111         let rhs = &right[..l];
6112
6113         for i in 0..l {
6114             match lhs[i].cmp(&rhs[i]) {
6115                 Ordering::Equal => (),
6116                 non_eq => return non_eq,
6117             }
6118         }
6119
6120         left.len().cmp(&right.len())
6121     }
6122 }
6123
6124 // memcmp compares a sequence of unsigned bytes lexicographically.
6125 // this matches the order we want for [u8], but no others (not even [i8]).
6126 impl SliceOrd for u8 {
6127     #[inline]
6128     fn compare(left: &[Self], right: &[Self]) -> Ordering {
6129         let order =
6130             unsafe { memcmp(left.as_ptr(), right.as_ptr(), cmp::min(left.len(), right.len())) };
6131         if order == 0 {
6132             left.len().cmp(&right.len())
6133         } else if order < 0 {
6134             Less
6135         } else {
6136             Greater
6137         }
6138     }
6139 }
6140
6141 #[doc(hidden)]
6142 /// Trait implemented for types that can be compared for equality using
6143 /// their bytewise representation
6144 trait BytewiseEquality: Eq + Copy {}
6145
6146 macro_rules! impl_marker_for {
6147     ($traitname:ident, $($ty:ty)*) => {
6148         $(
6149             impl $traitname for $ty { }
6150         )*
6151     }
6152 }
6153
6154 impl_marker_for!(BytewiseEquality,
6155                  u8 i8 u16 i16 u32 i32 u64 i64 u128 i128 usize isize char bool);
6156
6157 #[doc(hidden)]
6158 unsafe impl<'a, T> TrustedRandomAccess for Iter<'a, T> {
6159     unsafe fn get_unchecked(&mut self, i: usize) -> &'a T {
6160         &*self.ptr.as_ptr().add(i)
6161     }
6162     fn may_have_side_effect() -> bool {
6163         false
6164     }
6165 }
6166
6167 #[doc(hidden)]
6168 unsafe impl<'a, T> TrustedRandomAccess for IterMut<'a, T> {
6169     unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut T {
6170         &mut *self.ptr.as_ptr().add(i)
6171     }
6172     fn may_have_side_effect() -> bool {
6173         false
6174     }
6175 }
6176
6177 trait SliceContains: Sized {
6178     fn slice_contains(&self, x: &[Self]) -> bool;
6179 }
6180
6181 impl<T> SliceContains for T
6182 where
6183     T: PartialEq,
6184 {
6185     default fn slice_contains(&self, x: &[Self]) -> bool {
6186         x.iter().any(|y| *y == *self)
6187     }
6188 }
6189
6190 impl SliceContains for u8 {
6191     fn slice_contains(&self, x: &[Self]) -> bool {
6192         memchr::memchr(*self, x).is_some()
6193     }
6194 }
6195
6196 impl SliceContains for i8 {
6197     fn slice_contains(&self, x: &[Self]) -> bool {
6198         let byte = *self as u8;
6199         let bytes: &[u8] = unsafe { from_raw_parts(x.as_ptr() as *const u8, x.len()) };
6200         memchr::memchr(byte, bytes).is_some()
6201     }
6202 }