src/libcore/slice/mod.rs

   1 // Copyright 2012-2017 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 //! Slice management and manipulation
  12 //!
  13 //! For more details see [`std::slice`].
  14 //!
  15 //! [`std::slice`]: ../../std/slice/index.html
  16
  17 #![stable(feature = "rust1", since = "1.0.0")]
  18
  19 // How this module is organized.
  20 //
  21 // The library infrastructure for slices is fairly messy. There's
  22 // a lot of stuff defined here. Let's keep it clean.
  23 //
  24 // Since slices don't support inherent methods; all operations
  25 // on them are defined on traits, which are then reexported from
  26 // the prelude for convenience. So there are a lot of traits here.
  27 //
  28 // The layout of this file is thus:
  29 //
  30 // * Slice-specific 'extension' traits and their implementations. This
  31 //   is where most of the slice API resides.
  32 // * Implementations of a few common traits with important slice ops.
  33 // * Definitions of a bunch of iterators.
  34 // * Free functions.
  35 // * The `raw` and `bytes` submodules.
  36 // * Boilerplate trait implementations.
  37
  38 use borrow::Borrow;
  39 use cmp::Ordering::{self, Less, Equal, Greater};
  40 use cmp;
  41 use fmt;
  42 use intrinsics::assume;
  43 use iter::*;
  44 use ops::{FnMut, self};
  45 use option::Option;
  46 use option::Option::{None, Some};
  47 use result::Result;
  48 use result::Result::{Ok, Err};
  49 use ptr;
  50 use mem;
  51 use marker::{Copy, Send, Sync, Sized, self};
  52 use iter_private::TrustedRandomAccess;
  53
  54 mod sort;
  55
  56 #[repr(C)]
  57 struct Repr<T> {
  58     pub data: *const T,
  59     pub len: usize,
  60 }
  61
  62 //
  63 // Extension traits
  64 //
  65
  66 /// Extension methods for slices.
  67 #[unstable(feature = "core_slice_ext",
  68            reason = "stable interface provided by `impl [T]` in later crates",
  69            issue = "32110")]
  70 #[allow(missing_docs)] // documented elsewhere
  71 pub trait SliceExt {
  72     type Item;
  73
  74     #[stable(feature = "core", since = "1.6.0")]
  75     fn split_at(&self, mid: usize) -> (&[Self::Item], &[Self::Item]);
  76
  77     #[stable(feature = "core", since = "1.6.0")]
  78     fn iter(&self) -> Iter<Self::Item>;
  79
  80     #[stable(feature = "core", since = "1.6.0")]
  81     fn split<P>(&self, pred: P) -> Split<Self::Item, P>
  82         where P: FnMut(&Self::Item) -> bool;
  83
  84     #[unstable(feature = "slice_rsplit", issue = "41020")]
  85     fn rsplit<P>(&self, pred: P) -> RSplit<Self::Item, P>
  86         where P: FnMut(&Self::Item) -> bool;
  87
  88     #[stable(feature = "core", since = "1.6.0")]
  89     fn splitn<P>(&self, n: usize, pred: P) -> SplitN<Self::Item, P>
  90         where P: FnMut(&Self::Item) -> bool;
  91
  92     #[stable(feature = "core", since = "1.6.0")]
  93     fn rsplitn<P>(&self,  n: usize, pred: P) -> RSplitN<Self::Item, P>
  94         where P: FnMut(&Self::Item) -> bool;
  95
  96     #[stable(feature = "core", since = "1.6.0")]
  97     fn windows(&self, size: usize) -> Windows<Self::Item>;
  98
  99     #[stable(feature = "core", since = "1.6.0")]
 100     fn chunks(&self, size: usize) -> Chunks<Self::Item>;
 101
 102     #[stable(feature = "core", since = "1.6.0")]
 103     fn get<I>(&self, index: I) -> Option<&I::Output>
 104         where I: SliceIndex<Self>;
 105     #[stable(feature = "core", since = "1.6.0")]
 106     fn first(&self) -> Option<&Self::Item>;
 107
 108     #[stable(feature = "core", since = "1.6.0")]
 109     fn split_first(&self) -> Option<(&Self::Item, &[Self::Item])>;
 110
 111     #[stable(feature = "core", since = "1.6.0")]
 112     fn split_last(&self) -> Option<(&Self::Item, &[Self::Item])>;
 113
 114     #[stable(feature = "core", since = "1.6.0")]
 115     fn last(&self) -> Option<&Self::Item>;
 116
 117     #[stable(feature = "core", since = "1.6.0")]
 118     unsafe fn get_unchecked<I>(&self, index: I) -> &I::Output
 119         where I: SliceIndex<Self>;
 120     #[stable(feature = "core", since = "1.6.0")]
 121     fn as_ptr(&self) -> *const Self::Item;
 122
 123     #[stable(feature = "core", since = "1.6.0")]
 124     fn binary_search<Q: ?Sized>(&self, x: &Q) -> Result<usize, usize>
 125         where Self::Item: Borrow<Q>,
 126               Q: Ord;
 127
 128     #[stable(feature = "core", since = "1.6.0")]
 129     fn binary_search_by<'a, F>(&'a self, f: F) -> Result<usize, usize>
 130         where F: FnMut(&'a Self::Item) -> Ordering;
 131
 132     #[stable(feature = "slice_binary_search_by_key", since = "1.10.0")]
 133     fn binary_search_by_key<'a, B, F, Q: ?Sized>(&'a self, b: &Q, f: F) -> Result<usize, usize>
 134         where F: FnMut(&'a Self::Item) -> B,
 135               B: Borrow<Q>,
 136               Q: Ord;
 137
 138     #[stable(feature = "core", since = "1.6.0")]
 139     fn len(&self) -> usize;
 140
 141     #[stable(feature = "core", since = "1.6.0")]
 142     fn is_empty(&self) -> bool { self.len() == 0 }
 143
 144     #[stable(feature = "core", since = "1.6.0")]
 145     fn get_mut<I>(&mut self, index: I) -> Option<&mut I::Output>
 146         where I: SliceIndex<Self>;
 147     #[stable(feature = "core", since = "1.6.0")]
 148     fn iter_mut(&mut self) -> IterMut<Self::Item>;
 149
 150     #[stable(feature = "core", since = "1.6.0")]
 151     fn first_mut(&mut self) -> Option<&mut Self::Item>;
 152
 153     #[stable(feature = "core", since = "1.6.0")]
 154     fn split_first_mut(&mut self) -> Option<(&mut Self::Item, &mut [Self::Item])>;
 155
 156     #[stable(feature = "core", since = "1.6.0")]
 157     fn split_last_mut(&mut self) -> Option<(&mut Self::Item, &mut [Self::Item])>;
 158
 159     #[stable(feature = "core", since = "1.6.0")]
 160     fn last_mut(&mut self) -> Option<&mut Self::Item>;
 161
 162     #[stable(feature = "core", since = "1.6.0")]
 163     fn split_mut<P>(&mut self, pred: P) -> SplitMut<Self::Item, P>
 164         where P: FnMut(&Self::Item) -> bool;
 165
 166     #[unstable(feature = "slice_rsplit", issue = "41020")]
 167     fn rsplit_mut<P>(&mut self, pred: P) -> RSplitMut<Self::Item, P>
 168         where P: FnMut(&Self::Item) -> bool;
 169
 170     #[stable(feature = "core", since = "1.6.0")]
 171     fn splitn_mut<P>(&mut self, n: usize, pred: P) -> SplitNMut<Self::Item, P>
 172         where P: FnMut(&Self::Item) -> bool;
 173
 174     #[stable(feature = "core", since = "1.6.0")]
 175     fn rsplitn_mut<P>(&mut self,  n: usize, pred: P) -> RSplitNMut<Self::Item, P>
 176         where P: FnMut(&Self::Item) -> bool;
 177
 178     #[stable(feature = "core", since = "1.6.0")]
 179     fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<Self::Item>;
 180
 181     #[stable(feature = "core", since = "1.6.0")]
 182     fn swap(&mut self, a: usize, b: usize);
 183
 184     #[stable(feature = "core", since = "1.6.0")]
 185     fn split_at_mut(&mut self, mid: usize) -> (&mut [Self::Item], &mut [Self::Item]);
 186
 187     #[stable(feature = "core", since = "1.6.0")]
 188     fn reverse(&mut self);
 189
 190     #[stable(feature = "core", since = "1.6.0")]
 191     unsafe fn get_unchecked_mut<I>(&mut self, index: I) -> &mut I::Output
 192         where I: SliceIndex<Self>;
 193     #[stable(feature = "core", since = "1.6.0")]
 194     fn as_mut_ptr(&mut self) -> *mut Self::Item;
 195
 196     #[stable(feature = "core", since = "1.6.0")]
 197     fn contains(&self, x: &Self::Item) -> bool where Self::Item: PartialEq;
 198
 199     #[stable(feature = "core", since = "1.6.0")]
 200     fn starts_with(&self, needle: &[Self::Item]) -> bool where Self::Item: PartialEq;
 201
 202     #[stable(feature = "core", since = "1.6.0")]
 203     fn ends_with(&self, needle: &[Self::Item]) -> bool where Self::Item: PartialEq;
 204
 205     #[stable(feature = "clone_from_slice", since = "1.7.0")]
 206     fn clone_from_slice(&mut self, src: &[Self::Item]) where Self::Item: Clone;
 207
 208     #[stable(feature = "copy_from_slice", since = "1.9.0")]
 209     fn copy_from_slice(&mut self, src: &[Self::Item]) where Self::Item: Copy;
 210
 211     #[unstable(feature = "sort_unstable", issue = "40585")]
 212     fn sort_unstable(&mut self)
 213         where Self::Item: Ord;
 214
 215     #[unstable(feature = "sort_unstable", issue = "40585")]
 216     fn sort_unstable_by<F>(&mut self, compare: F)
 217         where F: FnMut(&Self::Item, &Self::Item) -> Ordering;
 218
 219     #[unstable(feature = "sort_unstable", issue = "40585")]
 220     fn sort_unstable_by_key<B, F>(&mut self, f: F)
 221         where F: FnMut(&Self::Item) -> B,
 222               B: Ord;
 223 }
 224
 225 // Use macros to be generic over const/mut
 226 macro_rules! slice_offset {
 227     ($ptr:expr, $by:expr) => {{
 228         let ptr = $ptr;
 229         if size_from_ptr(ptr) == 0 {
 230             (ptr as *mut i8).wrapping_offset($by) as _
 231         } else {
 232             ptr.offset($by)
 233         }
 234     }};
 235 }
 236
 237 // make a &T from a *const T
 238 macro_rules! make_ref {
 239     ($ptr:expr) => {{
 240         let ptr = $ptr;
 241         if size_from_ptr(ptr) == 0 {
 242             // Use a non-null pointer value
 243             &*(1 as *mut _)
 244         } else {
 245             &*ptr
 246         }
 247     }};
 248 }
 249
 250 // make a &mut T from a *mut T
 251 macro_rules! make_ref_mut {
 252     ($ptr:expr) => {{
 253         let ptr = $ptr;
 254         if size_from_ptr(ptr) == 0 {
 255             // Use a non-null pointer value
 256             &mut *(1 as *mut _)
 257         } else {
 258             &mut *ptr
 259         }
 260     }};
 261 }
 262
 263 #[unstable(feature = "core_slice_ext",
 264            reason = "stable interface provided by `impl [T]` in later crates",
 265            issue = "32110")]
 266 impl<T> SliceExt for [T] {
 267     type Item = T;
 268
 269     #[inline]
 270     fn split_at(&self, mid: usize) -> (&[T], &[T]) {
 271         (&self[..mid], &self[mid..])
 272     }
 273
 274     #[inline]
 275     fn iter(&self) -> Iter<T> {
 276         unsafe {
 277             let p = if mem::size_of::<T>() == 0 {
 278                 1 as *const _
 279             } else {
 280                 let p = self.as_ptr();
 281                 assume(!p.is_null());
 282                 p
 283             };
 284
 285             Iter {
 286                 ptr: p,
 287                 end: slice_offset!(p, self.len() as isize),
 288                 _marker: marker::PhantomData
 289             }
 290         }
 291     }
 292
 293     #[inline]
 294     fn split<P>(&self, pred: P) -> Split<T, P>
 295         where P: FnMut(&T) -> bool
 296     {
 297         Split {
 298             v: self,
 299             pred: pred,
 300             finished: false
 301         }
 302     }
 303
 304     #[inline]
 305     fn rsplit<P>(&self, pred: P) -> RSplit<T, P>
 306         where P: FnMut(&T) -> bool
 307     {
 308         RSplit { inner: self.split(pred) }
 309     }
 310
 311     #[inline]
 312     fn splitn<P>(&self, n: usize, pred: P) -> SplitN<T, P>
 313         where P: FnMut(&T) -> bool
 314     {
 315         SplitN {
 316             inner: GenericSplitN {
 317                 iter: self.split(pred),
 318                 count: n
 319             }
 320         }
 321     }
 322
 323     #[inline]
 324     fn rsplitn<P>(&self, n: usize, pred: P) -> RSplitN<T, P>
 325         where P: FnMut(&T) -> bool
 326     {
 327         RSplitN {
 328             inner: GenericSplitN {
 329                 iter: self.rsplit(pred),
 330                 count: n
 331             }
 332         }
 333     }
 334
 335     #[inline]
 336     fn windows(&self, size: usize) -> Windows<T> {
 337         assert!(size != 0);
 338         Windows { v: self, size: size }
 339     }
 340
 341     #[inline]
 342     fn chunks(&self, size: usize) -> Chunks<T> {
 343         assert!(size != 0);
 344         Chunks { v: self, size: size }
 345     }
 346
 347     #[inline]
 348     fn get<I>(&self, index: I) -> Option<&I::Output>
 349         where I: SliceIndex<[T]>
 350     {
 351         index.get(self)
 352     }
 353
 354     #[inline]
 355     fn first(&self) -> Option<&T> {
 356         if self.is_empty() { None } else { Some(&self[0]) }
 357     }
 358
 359     #[inline]
 360     fn split_first(&self) -> Option<(&T, &[T])> {
 361         if self.is_empty() { None } else { Some((&self[0], &self[1..])) }
 362     }
 363
 364     #[inline]
 365     fn split_last(&self) -> Option<(&T, &[T])> {
 366         let len = self.len();
 367         if len == 0 { None } else { Some((&self[len - 1], &self[..(len - 1)])) }
 368     }
 369
 370     #[inline]
 371     fn last(&self) -> Option<&T> {
 372         if self.is_empty() { None } else { Some(&self[self.len() - 1]) }
 373     }
 374
 375     #[inline]
 376     unsafe fn get_unchecked<I>(&self, index: I) -> &I::Output
 377         where I: SliceIndex<[T]>
 378     {
 379         index.get_unchecked(self)
 380     }
 381
 382     #[inline]
 383     fn as_ptr(&self) -> *const T {
 384         self as *const [T] as *const T
 385     }
 386
 387     fn binary_search_by<'a, F>(&'a self, mut f: F) -> Result<usize, usize>
 388         where F: FnMut(&'a T) -> Ordering
 389     {
 390         let mut base = 0usize;
 391         let mut s = self;
 392
 393         loop {
 394             let (head, tail) = s.split_at(s.len() >> 1);
 395             if tail.is_empty() {
 396                 return Err(base)
 397             }
 398             match f(&tail[0]) {
 399                 Less => {
 400                     base += head.len() + 1;
 401                     s = &tail[1..];
 402                 }
 403                 Greater => s = head,
 404                 Equal => return Ok(base + head.len()),
 405             }
 406         }
 407     }
 408
 409     #[inline]
 410     fn len(&self) -> usize {
 411         unsafe {
 412             mem::transmute::<&[T], Repr<T>>(self).len
 413         }
 414     }
 415
 416     #[inline]
 417     fn get_mut<I>(&mut self, index: I) -> Option<&mut I::Output>
 418         where I: SliceIndex<[T]>
 419     {
 420         index.get_mut(self)
 421     }
 422
 423     #[inline]
 424     fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
 425         let len = self.len();
 426         let ptr = self.as_mut_ptr();
 427
 428         unsafe {
 429             assert!(mid <= len);
 430
 431             (from_raw_parts_mut(ptr, mid),
 432              from_raw_parts_mut(ptr.offset(mid as isize), len - mid))
 433         }
 434     }
 435
 436     #[inline]
 437     fn iter_mut(&mut self) -> IterMut<T> {
 438         unsafe {
 439             let p = if mem::size_of::<T>() == 0 {
 440                 1 as *mut _
 441             } else {
 442                 let p = self.as_mut_ptr();
 443                 assume(!p.is_null());
 444                 p
 445             };
 446
 447             IterMut {
 448                 ptr: p,
 449                 end: slice_offset!(p, self.len() as isize),
 450                 _marker: marker::PhantomData
 451             }
 452         }
 453     }
 454
 455     #[inline]
 456     fn last_mut(&mut self) -> Option<&mut T> {
 457         let len = self.len();
 458         if len == 0 { return None; }
 459         Some(&mut self[len - 1])
 460     }
 461
 462     #[inline]
 463     fn first_mut(&mut self) -> Option<&mut T> {
 464         if self.is_empty() { None } else { Some(&mut self[0]) }
 465     }
 466
 467     #[inline]
 468     fn split_first_mut(&mut self) -> Option<(&mut T, &mut [T])> {
 469         if self.is_empty() { None } else {
 470             let split = self.split_at_mut(1);
 471             Some((&mut split.0[0], split.1))
 472         }
 473     }
 474
 475     #[inline]
 476     fn split_last_mut(&mut self) -> Option<(&mut T, &mut [T])> {
 477         let len = self.len();
 478         if len == 0 { None } else {
 479             let split = self.split_at_mut(len - 1);
 480             Some((&mut split.1[0], split.0))
 481         }
 482     }
 483
 484     #[inline]
 485     fn split_mut<P>(&mut self, pred: P) -> SplitMut<T, P>
 486         where P: FnMut(&T) -> bool
 487     {
 488         SplitMut { v: self, pred: pred, finished: false }
 489     }
 490
 491     #[inline]
 492     fn rsplit_mut<P>(&mut self, pred: P) -> RSplitMut<T, P>
 493         where P: FnMut(&T) -> bool
 494     {
 495         RSplitMut { inner: self.split_mut(pred) }
 496     }
 497
 498     #[inline]
 499     fn splitn_mut<P>(&mut self, n: usize, pred: P) -> SplitNMut<T, P>
 500         where P: FnMut(&T) -> bool
 501     {
 502         SplitNMut {
 503             inner: GenericSplitN {
 504                 iter: self.split_mut(pred),
 505                 count: n
 506             }
 507         }
 508     }
 509
 510     #[inline]
 511     fn rsplitn_mut<P>(&mut self, n: usize, pred: P) -> RSplitNMut<T, P> where
 512         P: FnMut(&T) -> bool,
 513     {
 514         RSplitNMut {
 515             inner: GenericSplitN {
 516                 iter: self.rsplit_mut(pred),
 517                 count: n
 518             }
 519         }
 520     }
 521
 522     #[inline]
 523     fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<T> {
 524         assert!(chunk_size > 0);
 525         ChunksMut { v: self, chunk_size: chunk_size }
 526     }
 527
 528     #[inline]
 529     fn swap(&mut self, a: usize, b: usize) {
 530         unsafe {
 531             // Can't take two mutable loans from one vector, so instead just cast
 532             // them to their raw pointers to do the swap
 533             let pa: *mut T = &mut self[a];
 534             let pb: *mut T = &mut self[b];
 535             ptr::swap(pa, pb);
 536         }
 537     }
 538
 539     fn reverse(&mut self) {
 540         let mut i: usize = 0;
 541         let ln = self.len();
 542         while i < ln / 2 {
 543             // Unsafe swap to avoid the bounds check in safe swap.
 544             unsafe {
 545                 let pa: *mut T = self.get_unchecked_mut(i);
 546                 let pb: *mut T = self.get_unchecked_mut(ln - i - 1);
 547                 ptr::swap(pa, pb);
 548             }
 549             i += 1;
 550         }
 551     }
 552
 553     #[inline]
 554     unsafe fn get_unchecked_mut<I>(&mut self, index: I) -> &mut I::Output
 555         where I: SliceIndex<[T]>
 556     {
 557         index.get_unchecked_mut(self)
 558     }
 559
 560     #[inline]
 561     fn as_mut_ptr(&mut self) -> *mut T {
 562         self as *mut [T] as *mut T
 563     }
 564
 565     #[inline]
 566     fn contains(&self, x: &T) -> bool where T: PartialEq {
 567         self.iter().any(|elt| *x == *elt)
 568     }
 569
 570     #[inline]
 571     fn starts_with(&self, needle: &[T]) -> bool where T: PartialEq {
 572         let n = needle.len();
 573         self.len() >= n && needle == &self[..n]
 574     }
 575
 576     #[inline]
 577     fn ends_with(&self, needle: &[T]) -> bool where T: PartialEq {
 578         let (m, n) = (self.len(), needle.len());
 579         m >= n && needle == &self[m-n..]
 580     }
 581
 582     fn binary_search<Q: ?Sized>(&self, x: &Q) -> Result<usize, usize>
 583         where T: Borrow<Q>,
 584               Q: Ord
 585     {
 586         self.binary_search_by(|p| p.borrow().cmp(x))
 587     }
 588
 589     #[inline]
 590     fn clone_from_slice(&mut self, src: &[T]) where T: Clone {
 591         assert!(self.len() == src.len(),
 592                 "destination and source slices have different lengths");
 593         // NOTE: We need to explicitly slice them to the same length
 594         // for bounds checking to be elided, and the optimizer will
 595         // generate memcpy for simple cases (for example T = u8).
 596         let len = self.len();
 597         let src = &src[..len];
 598         for i in 0..len {
 599             self[i].clone_from(&src[i]);
 600         }
 601     }
 602
 603     #[inline]
 604     fn copy_from_slice(&mut self, src: &[T]) where T: Copy {
 605         assert!(self.len() == src.len(),
 606                 "destination and source slices have different lengths");
 607         unsafe {
 608             ptr::copy_nonoverlapping(
 609                 src.as_ptr(), self.as_mut_ptr(), self.len());
 610         }
 611     }
 612
 613     #[inline]
 614     fn binary_search_by_key<'a, B, F, Q: ?Sized>(&'a self, b: &Q, mut f: F) -> Result<usize, usize>
 615         where F: FnMut(&'a Self::Item) -> B,
 616               B: Borrow<Q>,
 617               Q: Ord
 618     {
 619         self.binary_search_by(|k| f(k).borrow().cmp(b))
 620     }
 621
 622     #[inline]
 623     fn sort_unstable(&mut self)
 624         where Self::Item: Ord
 625     {
 626         sort::quicksort(self, |a, b| a.lt(b));
 627     }
 628
 629     #[inline]
 630     fn sort_unstable_by<F>(&mut self, mut compare: F)
 631         where F: FnMut(&Self::Item, &Self::Item) -> Ordering
 632     {
 633         sort::quicksort(self, |a, b| compare(a, b) == Ordering::Less);
 634     }
 635
 636     #[inline]
 637     fn sort_unstable_by_key<B, F>(&mut self, mut f: F)
 638         where F: FnMut(&Self::Item) -> B,
 639               B: Ord
 640     {
 641         sort::quicksort(self, |a, b| f(a).lt(&f(b)));
 642     }
 643 }
 644
 645 #[stable(feature = "rust1", since = "1.0.0")]
 646 #[rustc_on_unimplemented = "slice indices are of type `usize` or ranges of `usize`"]
 647 impl<T, I> ops::Index<I> for [T]
 648     where I: SliceIndex<[T]>
 649 {
 650     type Output = I::Output;
 651
 652     #[inline]
 653     fn index(&self, index: I) -> &I::Output {
 654         index.index(self)
 655     }
 656 }
 657
 658 #[stable(feature = "rust1", since = "1.0.0")]
 659 #[rustc_on_unimplemented = "slice indices are of type `usize` or ranges of `usize`"]
 660 impl<T, I> ops::IndexMut<I> for [T]
 661     where I: SliceIndex<[T]>
 662 {
 663     #[inline]
 664     fn index_mut(&mut self, index: I) -> &mut I::Output {
 665         index.index_mut(self)
 666     }
 667 }
 668
 669 #[inline(never)]
 670 #[cold]
 671 fn slice_index_len_fail(index: usize, len: usize) -> ! {
 672     panic!("index {} out of range for slice of length {}", index, len);
 673 }
 674
 675 #[inline(never)]
 676 #[cold]
 677 fn slice_index_order_fail(index: usize, end: usize) -> ! {
 678     panic!("slice index starts at {} but ends at {}", index, end);
 679 }
 680
 681 /// A helper trait used for indexing operations.
 682 #[unstable(feature = "slice_get_slice", issue = "35729")]
 683 #[rustc_on_unimplemented = "slice indices are of type `usize` or ranges of `usize`"]
 684 pub trait SliceIndex<T: ?Sized> {
 685     /// The output type returned by methods.
 686     type Output: ?Sized;
 687
 688     /// Returns a shared reference to the output at this location, if in
 689     /// bounds.
 690     fn get(self, slice: &T) -> Option<&Self::Output>;
 691
 692     /// Returns a mutable reference to the output at this location, if in
 693     /// bounds.
 694     fn get_mut(self, slice: &mut T) -> Option<&mut Self::Output>;
 695
 696     /// Returns a shared reference to the output at this location, without
 697     /// performing any bounds checking.
 698     unsafe fn get_unchecked(self, slice: &T) -> &Self::Output;
 699
 700     /// Returns a mutable reference to the output at this location, without
 701     /// performing any bounds checking.
 702     unsafe fn get_unchecked_mut(self, slice: &mut T) -> &mut Self::Output;
 703
 704     /// Returns a shared reference to the output at this location, panicking
 705     /// if out of bounds.
 706     fn index(self, slice: &T) -> &Self::Output;
 707
 708     /// Returns a mutable reference to the output at this location, panicking
 709     /// if out of bounds.
 710     fn index_mut(self, slice: &mut T) -> &mut Self::Output;
 711 }
 712
 713 #[stable(feature = "slice-get-slice-impls", since = "1.15.0")]
 714 impl<T> SliceIndex<[T]> for usize {
 715     type Output = T;
 716
 717     #[inline]
 718     fn get(self, slice: &[T]) -> Option<&T> {
 719         if self < slice.len() {
 720             unsafe {
 721                 Some(self.get_unchecked(slice))
 722             }
 723         } else {
 724             None
 725         }
 726     }
 727
 728     #[inline]
 729     fn get_mut(self, slice: &mut [T]) -> Option<&mut T> {
 730         if self < slice.len() {
 731             unsafe {
 732                 Some(self.get_unchecked_mut(slice))
 733             }
 734         } else {
 735             None
 736         }
 737     }
 738
 739     #[inline]
 740     unsafe fn get_unchecked(self, slice: &[T]) -> &T {
 741         &*slice.as_ptr().offset(self as isize)
 742     }
 743
 744     #[inline]
 745     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut T {
 746         &mut *slice.as_mut_ptr().offset(self as isize)
 747     }
 748
 749     #[inline]
 750     fn index(self, slice: &[T]) -> &T {
 751         // NB: use intrinsic indexing
 752         &(*slice)[self]
 753     }
 754
 755     #[inline]
 756     fn index_mut(self, slice: &mut [T]) -> &mut T {
 757         // NB: use intrinsic indexing
 758         &mut (*slice)[self]
 759     }
 760 }
 761
 762 #[stable(feature = "slice-get-slice-impls", since = "1.15.0")]
 763 impl<T> SliceIndex<[T]> for  ops::Range<usize> {
 764     type Output = [T];
 765
 766     #[inline]
 767     fn get(self, slice: &[T]) -> Option<&[T]> {
 768         if self.start > self.end || self.end > slice.len() {
 769             None
 770         } else {
 771             unsafe {
 772                 Some(self.get_unchecked(slice))
 773             }
 774         }
 775     }
 776
 777     #[inline]
 778     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
 779         if self.start > self.end || self.end > slice.len() {
 780             None
 781         } else {
 782             unsafe {
 783                 Some(self.get_unchecked_mut(slice))
 784             }
 785         }
 786     }
 787
 788     #[inline]
 789     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
 790         from_raw_parts(slice.as_ptr().offset(self.start as isize), self.end - self.start)
 791     }
 792
 793     #[inline]
 794     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
 795         from_raw_parts_mut(slice.as_mut_ptr().offset(self.start as isize), self.end - self.start)
 796     }
 797
 798     #[inline]
 799     fn index(self, slice: &[T]) -> &[T] {
 800         if self.start > self.end {
 801             slice_index_order_fail(self.start, self.end);
 802         } else if self.end > slice.len() {
 803             slice_index_len_fail(self.end, slice.len());
 804         }
 805         unsafe {
 806             self.get_unchecked(slice)
 807         }
 808     }
 809
 810     #[inline]
 811     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
 812         if self.start > self.end {
 813             slice_index_order_fail(self.start, self.end);
 814         } else if self.end > slice.len() {
 815             slice_index_len_fail(self.end, slice.len());
 816         }
 817         unsafe {
 818             self.get_unchecked_mut(slice)
 819         }
 820     }
 821 }
 822
 823 #[stable(feature = "slice-get-slice-impls", since = "1.15.0")]
 824 impl<T> SliceIndex<[T]> for ops::RangeTo<usize> {
 825     type Output = [T];
 826
 827     #[inline]
 828     fn get(self, slice: &[T]) -> Option<&[T]> {
 829         (0..self.end).get(slice)
 830     }
 831
 832     #[inline]
 833     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
 834         (0..self.end).get_mut(slice)
 835     }
 836
 837     #[inline]
 838     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
 839         (0..self.end).get_unchecked(slice)
 840     }
 841
 842     #[inline]
 843     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
 844         (0..self.end).get_unchecked_mut(slice)
 845     }
 846
 847     #[inline]
 848     fn index(self, slice: &[T]) -> &[T] {
 849         (0..self.end).index(slice)
 850     }
 851
 852     #[inline]
 853     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
 854         (0..self.end).index_mut(slice)
 855     }
 856 }
 857
 858 #[stable(feature = "slice-get-slice-impls", since = "1.15.0")]
 859 impl<T> SliceIndex<[T]> for ops::RangeFrom<usize> {
 860     type Output = [T];
 861
 862     #[inline]
 863     fn get(self, slice: &[T]) -> Option<&[T]> {
 864         (self.start..slice.len()).get(slice)
 865     }
 866
 867     #[inline]
 868     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
 869         (self.start..slice.len()).get_mut(slice)
 870     }
 871
 872     #[inline]
 873     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
 874         (self.start..slice.len()).get_unchecked(slice)
 875     }
 876
 877     #[inline]
 878     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
 879         (self.start..slice.len()).get_unchecked_mut(slice)
 880     }
 881
 882     #[inline]
 883     fn index(self, slice: &[T]) -> &[T] {
 884         (self.start..slice.len()).index(slice)
 885     }
 886
 887     #[inline]
 888     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
 889         (self.start..slice.len()).index_mut(slice)
 890     }
 891 }
 892
 893 #[stable(feature = "slice-get-slice-impls", since = "1.15.0")]
 894 impl<T> SliceIndex<[T]> for ops::RangeFull {
 895     type Output = [T];
 896
 897     #[inline]
 898     fn get(self, slice: &[T]) -> Option<&[T]> {
 899         Some(slice)
 900     }
 901
 902     #[inline]
 903     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
 904         Some(slice)
 905     }
 906
 907     #[inline]
 908     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
 909         slice
 910     }
 911
 912     #[inline]
 913     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
 914         slice
 915     }
 916
 917     #[inline]
 918     fn index(self, slice: &[T]) -> &[T] {
 919         slice
 920     }
 921
 922     #[inline]
 923     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
 924         slice
 925     }
 926 }
 927
 928
 929 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
 930 impl<T> SliceIndex<[T]> for ops::RangeInclusive<usize> {
 931     type Output = [T];
 932
 933     #[inline]
 934     fn get(self, slice: &[T]) -> Option<&[T]> {
 935         match self {
 936             ops::RangeInclusive::Empty { .. } => Some(&[]),
 937             ops::RangeInclusive::NonEmpty { end, .. } if end == usize::max_value() => None,
 938             ops::RangeInclusive::NonEmpty { start, end } => (start..end + 1).get(slice),
 939         }
 940     }
 941
 942     #[inline]
 943     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
 944         match self {
 945             ops::RangeInclusive::Empty { .. } => Some(&mut []),
 946             ops::RangeInclusive::NonEmpty { end, .. } if end == usize::max_value() => None,
 947             ops::RangeInclusive::NonEmpty { start, end } => (start..end + 1).get_mut(slice),
 948         }
 949     }
 950
 951     #[inline]
 952     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
 953         match self {
 954             ops::RangeInclusive::Empty { .. } => &[],
 955             ops::RangeInclusive::NonEmpty { start, end } => (start..end + 1).get_unchecked(slice),
 956         }
 957     }
 958
 959     #[inline]
 960     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
 961         match self {
 962             ops::RangeInclusive::Empty { .. } => &mut [],
 963             ops::RangeInclusive::NonEmpty { start, end } => {
 964                 (start..end + 1).get_unchecked_mut(slice)
 965             }
 966         }
 967     }
 968
 969     #[inline]
 970     fn index(self, slice: &[T]) -> &[T] {
 971         match self {
 972             ops::RangeInclusive::Empty { .. } => &[],
 973             ops::RangeInclusive::NonEmpty { end, .. } if end == usize::max_value() => {
 974                 panic!("attempted to index slice up to maximum usize");
 975             },
 976             ops::RangeInclusive::NonEmpty { start, end } => (start..end + 1).index(slice),
 977         }
 978     }
 979
 980     #[inline]
 981     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
 982         match self {
 983             ops::RangeInclusive::Empty { .. } => &mut [],
 984             ops::RangeInclusive::NonEmpty { end, .. } if end == usize::max_value() => {
 985                 panic!("attempted to index slice up to maximum usize");
 986             },
 987             ops::RangeInclusive::NonEmpty { start, end } => (start..end + 1).index_mut(slice),
 988         }
 989     }
 990 }
 991
 992 #[unstable(feature = "inclusive_range", reason = "recently added, follows RFC", issue = "28237")]
 993 impl<T> SliceIndex<[T]> for ops::RangeToInclusive<usize> {
 994     type Output = [T];
 995
 996     #[inline]
 997     fn get(self, slice: &[T]) -> Option<&[T]> {
 998         (0...self.end).get(slice)
 999     }
1000
1001     #[inline]
1002     fn get_mut(self, slice: &mut [T]) -> Option<&mut [T]> {
1003         (0...self.end).get_mut(slice)
1004     }
1005
1006     #[inline]
1007     unsafe fn get_unchecked(self, slice: &[T]) -> &[T] {
1008         (0...self.end).get_unchecked(slice)
1009     }
1010
1011     #[inline]
1012     unsafe fn get_unchecked_mut(self, slice: &mut [T]) -> &mut [T] {
1013         (0...self.end).get_unchecked_mut(slice)
1014     }
1015
1016     #[inline]
1017     fn index(self, slice: &[T]) -> &[T] {
1018         (0...self.end).index(slice)
1019     }
1020
1021     #[inline]
1022     fn index_mut(self, slice: &mut [T]) -> &mut [T] {
1023         (0...self.end).index_mut(slice)
1024     }
1025 }
1026
1027 ////////////////////////////////////////////////////////////////////////////////
1028 // Common traits
1029 ////////////////////////////////////////////////////////////////////////////////
1030
1031 #[stable(feature = "rust1", since = "1.0.0")]
1032 impl<'a, T> Default for &'a [T] {
1033     /// Creates an empty slice.
1034     fn default() -> &'a [T] { &[] }
1035 }
1036
1037 #[stable(feature = "mut_slice_default", since = "1.5.0")]
1038 impl<'a, T> Default for &'a mut [T] {
1039     /// Creates a mutable empty slice.
1040     fn default() -> &'a mut [T] { &mut [] }
1041 }
1042
1043 //
1044 // Iterators
1045 //
1046
1047 #[stable(feature = "rust1", since = "1.0.0")]
1048 impl<'a, T> IntoIterator for &'a [T] {
1049     type Item = &'a T;
1050     type IntoIter = Iter<'a, T>;
1051
1052     fn into_iter(self) -> Iter<'a, T> {
1053         self.iter()
1054     }
1055 }
1056
1057 #[stable(feature = "rust1", since = "1.0.0")]
1058 impl<'a, T> IntoIterator for &'a mut [T] {
1059     type Item = &'a mut T;
1060     type IntoIter = IterMut<'a, T>;
1061
1062     fn into_iter(self) -> IterMut<'a, T> {
1063         self.iter_mut()
1064     }
1065 }
1066
1067 #[inline(always)]
1068 fn size_from_ptr<T>(_: *const T) -> usize {
1069     mem::size_of::<T>()
1070 }
1071
1072 // The shared definition of the `Iter` and `IterMut` iterators
1073 macro_rules! iterator {
1074     (struct $name:ident -> $ptr:ty, $elem:ty, $mkref:ident) => {
1075         #[stable(feature = "rust1", since = "1.0.0")]
1076         impl<'a, T> Iterator for $name<'a, T> {
1077             type Item = $elem;
1078
1079             #[inline]
1080             fn next(&mut self) -> Option<$elem> {
1081                 // could be implemented with slices, but this avoids bounds checks
1082                 unsafe {
1083                     if mem::size_of::<T>() != 0 {
1084                         assume(!self.ptr.is_null());
1085                         assume(!self.end.is_null());
1086                     }
1087                     if self.ptr == self.end {
1088                         None
1089                     } else {
1090                         Some($mkref!(self.ptr.post_inc()))
1091                     }
1092                 }
1093             }
1094
1095             #[inline]
1096             fn size_hint(&self) -> (usize, Option<usize>) {
1097                 let exact = ptrdistance(self.ptr, self.end);
1098                 (exact, Some(exact))
1099             }
1100
1101             #[inline]
1102             fn count(self) -> usize {
1103                 self.len()
1104             }
1105
1106             #[inline]
1107             fn nth(&mut self, n: usize) -> Option<$elem> {
1108                 // Call helper method. Can't put the definition here because mut versus const.
1109                 self.iter_nth(n)
1110             }
1111
1112             #[inline]
1113             fn last(mut self) -> Option<$elem> {
1114                 self.next_back()
1115             }
1116
1117             fn all<F>(&mut self, mut predicate: F) -> bool
1118                 where F: FnMut(Self::Item) -> bool,
1119             {
1120                 self.search_while(true, move |elt| {
1121                     if predicate(elt) {
1122                         SearchWhile::Continue
1123                     } else {
1124                         SearchWhile::Done(false)
1125                     }
1126                 })
1127             }
1128
1129             fn any<F>(&mut self, mut predicate: F) -> bool
1130                 where F: FnMut(Self::Item) -> bool,
1131             {
1132                 !self.all(move |elt| !predicate(elt))
1133             }
1134
1135             fn find<F>(&mut self, mut predicate: F) -> Option<Self::Item>
1136                 where F: FnMut(&Self::Item) -> bool,
1137             {
1138                 self.search_while(None, move |elt| {
1139                     if predicate(&elt) {
1140                         SearchWhile::Done(Some(elt))
1141                     } else {
1142                         SearchWhile::Continue
1143                     }
1144                 })
1145             }
1146
1147             fn position<F>(&mut self, mut predicate: F) -> Option<usize>
1148                 where F: FnMut(Self::Item) -> bool,
1149             {
1150                 let mut index = 0;
1151                 self.search_while(None, move |elt| {
1152                     if predicate(elt) {
1153                         SearchWhile::Done(Some(index))
1154                     } else {
1155                         index += 1;
1156                         SearchWhile::Continue
1157                     }
1158                 })
1159             }
1160
1161             fn rposition<F>(&mut self, mut predicate: F) -> Option<usize>
1162                 where F: FnMut(Self::Item) -> bool,
1163             {
1164                 let mut index = self.len();
1165                 self.rsearch_while(None, move |elt| {
1166                     index -= 1;
1167                     if predicate(elt) {
1168                         SearchWhile::Done(Some(index))
1169                     } else {
1170                         SearchWhile::Continue
1171                     }
1172                 })
1173             }
1174         }
1175
1176         #[stable(feature = "rust1", since = "1.0.0")]
1177         impl<'a, T> DoubleEndedIterator for $name<'a, T> {
1178             #[inline]
1179             fn next_back(&mut self) -> Option<$elem> {
1180                 // could be implemented with slices, but this avoids bounds checks
1181                 unsafe {
1182                     if mem::size_of::<T>() != 0 {
1183                         assume(!self.ptr.is_null());
1184                         assume(!self.end.is_null());
1185                     }
1186                     if self.end == self.ptr {
1187                         None
1188                     } else {
1189                         Some($mkref!(self.end.pre_dec()))
1190                     }
1191                 }
1192             }
1193         }
1194
1195         // search_while is a generalization of the internal iteration methods.
1196         impl<'a, T> $name<'a, T> {
1197             // search through the iterator's element using the closure `g`.
1198             // if no element was found, return `default`.
1199             fn search_while<Acc, G>(&mut self, default: Acc, mut g: G) -> Acc
1200                 where Self: Sized,
1201                       G: FnMut($elem) -> SearchWhile<Acc>
1202             {
1203                 // manual unrolling is needed when there are conditional exits from the loop
1204                 unsafe {
1205                     while ptrdistance(self.ptr, self.end) >= 4 {
1206                         search_while!(g($mkref!(self.ptr.post_inc())));
1207                         search_while!(g($mkref!(self.ptr.post_inc())));
1208                         search_while!(g($mkref!(self.ptr.post_inc())));
1209                         search_while!(g($mkref!(self.ptr.post_inc())));
1210                     }
1211                     while self.ptr != self.end {
1212                         search_while!(g($mkref!(self.ptr.post_inc())));
1213                     }
1214                 }
1215                 default
1216             }
1217
1218             fn rsearch_while<Acc, G>(&mut self, default: Acc, mut g: G) -> Acc
1219                 where Self: Sized,
1220                       G: FnMut($elem) -> SearchWhile<Acc>
1221             {
1222                 unsafe {
1223                     while ptrdistance(self.ptr, self.end) >= 4 {
1224                         search_while!(g($mkref!(self.end.pre_dec())));
1225                         search_while!(g($mkref!(self.end.pre_dec())));
1226                         search_while!(g($mkref!(self.end.pre_dec())));
1227                         search_while!(g($mkref!(self.end.pre_dec())));
1228                     }
1229                     while self.ptr != self.end {
1230                         search_while!(g($mkref!(self.end.pre_dec())));
1231                     }
1232                 }
1233                 default
1234             }
1235         }
1236     }
1237 }
1238
1239 macro_rules! make_slice {
1240     ($start: expr, $end: expr) => {{
1241         let start = $start;
1242         let diff = ($end as usize).wrapping_sub(start as usize);
1243         if size_from_ptr(start) == 0 {
1244             // use a non-null pointer value
1245             unsafe { from_raw_parts(1 as *const _, diff) }
1246         } else {
1247             let len = diff / size_from_ptr(start);
1248             unsafe { from_raw_parts(start, len) }
1249         }
1250     }}
1251 }
1252
1253 macro_rules! make_mut_slice {
1254     ($start: expr, $end: expr) => {{
1255         let start = $start;
1256         let diff = ($end as usize).wrapping_sub(start as usize);
1257         if size_from_ptr(start) == 0 {
1258             // use a non-null pointer value
1259             unsafe { from_raw_parts_mut(1 as *mut _, diff) }
1260         } else {
1261             let len = diff / size_from_ptr(start);
1262             unsafe { from_raw_parts_mut(start, len) }
1263         }
1264     }}
1265 }
1266
1267 // An enum used for controlling the execution of `.search_while()`.
1268 enum SearchWhile<T> {
1269     // Continue searching
1270     Continue,
1271     // Fold is complete and will return this value
1272     Done(T),
1273 }
1274
1275 // helper macro for search while's control flow
1276 macro_rules! search_while {
1277     ($e:expr) => {
1278         match $e {
1279             SearchWhile::Continue => { }
1280             SearchWhile::Done(done) => return done,
1281         }
1282     }
1283 }
1284
1285 /// Immutable slice iterator
1286 ///
1287 /// This struct is created by the [`iter`] method on [slices].
1288 ///
1289 /// # Examples
1290 ///
1291 /// Basic usage:
1292 ///
1293 /// ```
1294 /// // First, we declare a type which has `iter` method to get the `Iter` struct (&[usize here]):
1295 /// let slice = &[1, 2, 3];
1296 ///
1297 /// // Then, we iterate over it:
1298 /// for element in slice.iter() {
1299 ///     println!("{}", element);
1300 /// }
1301 /// ```
1302 ///
1303 /// [`iter`]: ../../std/primitive.slice.html#method.iter
1304 /// [slices]: ../../std/primitive.slice.html
1305 #[stable(feature = "rust1", since = "1.0.0")]
1306 pub struct Iter<'a, T: 'a> {
1307     ptr: *const T,
1308     end: *const T,
1309     _marker: marker::PhantomData<&'a T>,
1310 }
1311
1312 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1313 impl<'a, T: 'a + fmt::Debug> fmt::Debug for Iter<'a, T> {
1314     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1315         f.debug_tuple("Iter")
1316             .field(&self.as_slice())
1317             .finish()
1318     }
1319 }
1320
1321 #[stable(feature = "rust1", since = "1.0.0")]
1322 unsafe impl<'a, T: Sync> Sync for Iter<'a, T> {}
1323 #[stable(feature = "rust1", since = "1.0.0")]
1324 unsafe impl<'a, T: Sync> Send for Iter<'a, T> {}
1325
1326 impl<'a, T> Iter<'a, T> {
1327     /// View the underlying data as a subslice of the original data.
1328     ///
1329     /// This has the same lifetime as the original slice, and so the
1330     /// iterator can continue to be used while this exists.
1331     ///
1332     /// # Examples
1333     ///
1334     /// Basic usage:
1335     ///
1336     /// ```
1337     /// // First, we declare a type which has the `iter` method to get the `Iter`
1338     /// // struct (&[usize here]):
1339     /// let slice = &[1, 2, 3];
1340     ///
1341     /// // Then, we get the iterator:
1342     /// let mut iter = slice.iter();
1343     /// // So if we print what `as_slice` method returns here, we have "[1, 2, 3]":
1344     /// println!("{:?}", iter.as_slice());
1345     ///
1346     /// // Next, we move to the second element of the slice:
1347     /// iter.next();
1348     /// // Now `as_slice` returns "[2, 3]":
1349     /// println!("{:?}", iter.as_slice());
1350     /// ```
1351     #[stable(feature = "iter_to_slice", since = "1.4.0")]
1352     pub fn as_slice(&self) -> &'a [T] {
1353         make_slice!(self.ptr, self.end)
1354     }
1355
1356     // Helper function for Iter::nth
1357     fn iter_nth(&mut self, n: usize) -> Option<&'a T> {
1358         match self.as_slice().get(n) {
1359             Some(elem_ref) => unsafe {
1360                 self.ptr = slice_offset!(self.ptr, (n as isize).wrapping_add(1));
1361                 Some(elem_ref)
1362             },
1363             None => {
1364                 self.ptr = self.end;
1365                 None
1366             }
1367         }
1368     }
1369 }
1370
1371 iterator!{struct Iter -> *const T, &'a T, make_ref}
1372
1373 #[stable(feature = "rust1", since = "1.0.0")]
1374 impl<'a, T> ExactSizeIterator for Iter<'a, T> {
1375     fn is_empty(&self) -> bool {
1376         self.ptr == self.end
1377     }
1378 }
1379
1380 #[unstable(feature = "fused", issue = "35602")]
1381 impl<'a, T> FusedIterator for Iter<'a, T> {}
1382
1383 #[unstable(feature = "trusted_len", issue = "37572")]
1384 unsafe impl<'a, T> TrustedLen for Iter<'a, T> {}
1385
1386 #[stable(feature = "rust1", since = "1.0.0")]
1387 impl<'a, T> Clone for Iter<'a, T> {
1388     fn clone(&self) -> Iter<'a, T> { Iter { ptr: self.ptr, end: self.end, _marker: self._marker } }
1389 }
1390
1391 #[stable(feature = "slice_iter_as_ref", since = "1.12.0")]
1392 impl<'a, T> AsRef<[T]> for Iter<'a, T> {
1393     fn as_ref(&self) -> &[T] {
1394         self.as_slice()
1395     }
1396 }
1397
1398 /// Mutable slice iterator.
1399 ///
1400 /// This struct is created by the [`iter_mut`] method on [slices].
1401 ///
1402 /// # Examples
1403 ///
1404 /// Basic usage:
1405 ///
1406 /// ```
1407 /// // First, we declare a type which has `iter_mut` method to get the `IterMut`
1408 /// // struct (&[usize here]):
1409 /// let mut slice = &mut [1, 2, 3];
1410 ///
1411 /// // Then, we iterate over it and increment each element value:
1412 /// for element in slice.iter_mut() {
1413 ///     *element += 1;
1414 /// }
1415 ///
1416 /// // We now have "[2, 3, 4]":
1417 /// println!("{:?}", slice);
1418 /// ```
1419 ///
1420 /// [`iter_mut`]: ../../std/primitive.slice.html#method.iter_mut
1421 /// [slices]: ../../std/primitive.slice.html
1422 #[stable(feature = "rust1", since = "1.0.0")]
1423 pub struct IterMut<'a, T: 'a> {
1424     ptr: *mut T,
1425     end: *mut T,
1426     _marker: marker::PhantomData<&'a mut T>,
1427 }
1428
1429 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1430 impl<'a, T: 'a + fmt::Debug> fmt::Debug for IterMut<'a, T> {
1431     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1432         f.debug_tuple("IterMut")
1433             .field(&make_slice!(self.ptr, self.end))
1434             .finish()
1435     }
1436 }
1437
1438 #[stable(feature = "rust1", since = "1.0.0")]
1439 unsafe impl<'a, T: Sync> Sync for IterMut<'a, T> {}
1440 #[stable(feature = "rust1", since = "1.0.0")]
1441 unsafe impl<'a, T: Send> Send for IterMut<'a, T> {}
1442
1443 impl<'a, T> IterMut<'a, T> {
1444     /// View the underlying data as a subslice of the original data.
1445     ///
1446     /// To avoid creating `&mut` references that alias, this is forced
1447     /// to consume the iterator. Consider using the `Slice` and
1448     /// `SliceMut` implementations for obtaining slices with more
1449     /// restricted lifetimes that do not consume the iterator.
1450     ///
1451     /// # Examples
1452     ///
1453     /// Basic usage:
1454     ///
1455     /// ```
1456     /// // First, we declare a type which has `iter_mut` method to get the `IterMut`
1457     /// // struct (&[usize here]):
1458     /// let mut slice = &mut [1, 2, 3];
1459     ///
1460     /// {
1461     ///     // Then, we get the iterator:
1462     ///     let mut iter = slice.iter_mut();
1463     ///     // We move to next element:
1464     ///     iter.next();
1465     ///     // So if we print what `into_slice` method returns here, we have "[2, 3]":
1466     ///     println!("{:?}", iter.into_slice());
1467     /// }
1468     ///
1469     /// // Now let's modify a value of the slice:
1470     /// {
1471     ///     // First we get back the iterator:
1472     ///     let mut iter = slice.iter_mut();
1473     ///     // We change the value of the first element of the slice returned by the `next` method:
1474     ///     *iter.next().unwrap() += 1;
1475     /// }
1476     /// // Now slice is "[2, 2, 3]":
1477     /// println!("{:?}", slice);
1478     /// ```
1479     #[stable(feature = "iter_to_slice", since = "1.4.0")]
1480     pub fn into_slice(self) -> &'a mut [T] {
1481         make_mut_slice!(self.ptr, self.end)
1482     }
1483
1484     // Helper function for IterMut::nth
1485     fn iter_nth(&mut self, n: usize) -> Option<&'a mut T> {
1486         match make_mut_slice!(self.ptr, self.end).get_mut(n) {
1487             Some(elem_ref) => unsafe {
1488                 self.ptr = slice_offset!(self.ptr, (n as isize).wrapping_add(1));
1489                 Some(elem_ref)
1490             },
1491             None => {
1492                 self.ptr = self.end;
1493                 None
1494             }
1495         }
1496     }
1497 }
1498
1499 iterator!{struct IterMut -> *mut T, &'a mut T, make_ref_mut}
1500
1501 #[stable(feature = "rust1", since = "1.0.0")]
1502 impl<'a, T> ExactSizeIterator for IterMut<'a, T> {
1503     fn is_empty(&self) -> bool {
1504         self.ptr == self.end
1505     }
1506 }
1507
1508 #[unstable(feature = "fused", issue = "35602")]
1509 impl<'a, T> FusedIterator for IterMut<'a, T> {}
1510
1511 #[unstable(feature = "trusted_len", issue = "37572")]
1512 unsafe impl<'a, T> TrustedLen for IterMut<'a, T> {}
1513
1514
1515 // Return the number of elements of `T` from `start` to `end`.
1516 // Return the arithmetic difference if `T` is zero size.
1517 #[inline(always)]
1518 fn ptrdistance<T>(start: *const T, end: *const T) -> usize {
1519     match start.offset_to(end) {
1520         Some(x) => x as usize,
1521         None => (end as usize).wrapping_sub(start as usize),
1522     }
1523 }
1524
1525 // Extension methods for raw pointers, used by the iterators
1526 trait PointerExt : Copy {
1527     unsafe fn slice_offset(self, i: isize) -> Self;
1528
1529     /// Increments `self` by 1, but returns the old value.
1530     #[inline(always)]
1531     unsafe fn post_inc(&mut self) -> Self {
1532         let current = *self;
1533         *self = self.slice_offset(1);
1534         current
1535     }
1536
1537     /// Decrements `self` by 1, and returns the new value.
1538     #[inline(always)]
1539     unsafe fn pre_dec(&mut self) -> Self {
1540         *self = self.slice_offset(-1);
1541         *self
1542     }
1543 }
1544
1545 impl<T> PointerExt for *const T {
1546     #[inline(always)]
1547     unsafe fn slice_offset(self, i: isize) -> Self {
1548         slice_offset!(self, i)
1549     }
1550 }
1551
1552 impl<T> PointerExt for *mut T {
1553     #[inline(always)]
1554     unsafe fn slice_offset(self, i: isize) -> Self {
1555         slice_offset!(self, i)
1556     }
1557 }
1558
1559 /// An internal abstraction over the splitting iterators, so that
1560 /// splitn, splitn_mut etc can be implemented once.
1561 #[doc(hidden)]
1562 trait SplitIter: DoubleEndedIterator {
1563     /// Marks the underlying iterator as complete, extracting the remaining
1564     /// portion of the slice.
1565     fn finish(&mut self) -> Option<Self::Item>;
1566 }
1567
1568 /// An iterator over subslices separated by elements that match a predicate
1569 /// function.
1570 ///
1571 /// This struct is created by the [`split`] method on [slices].
1572 ///
1573 /// [`split`]: ../../std/primitive.slice.html#method.split
1574 /// [slices]: ../../std/primitive.slice.html
1575 #[stable(feature = "rust1", since = "1.0.0")]
1576 pub struct Split<'a, T:'a, P> where P: FnMut(&T) -> bool {
1577     v: &'a [T],
1578     pred: P,
1579     finished: bool
1580 }
1581
1582 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1583 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for Split<'a, T, P> where P: FnMut(&T) -> bool {
1584     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1585         f.debug_struct("Split")
1586             .field("v", &self.v)
1587             .field("finished", &self.finished)
1588             .finish()
1589     }
1590 }
1591
1592 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1593 #[stable(feature = "rust1", since = "1.0.0")]
1594 impl<'a, T, P> Clone for Split<'a, T, P> where P: Clone + FnMut(&T) -> bool {
1595     fn clone(&self) -> Split<'a, T, P> {
1596         Split {
1597             v: self.v,
1598             pred: self.pred.clone(),
1599             finished: self.finished,
1600         }
1601     }
1602 }
1603
1604 #[stable(feature = "rust1", since = "1.0.0")]
1605 impl<'a, T, P> Iterator for Split<'a, T, P> where P: FnMut(&T) -> bool {
1606     type Item = &'a [T];
1607
1608     #[inline]
1609     fn next(&mut self) -> Option<&'a [T]> {
1610         if self.finished { return None; }
1611
1612         match self.v.iter().position(|x| (self.pred)(x)) {
1613             None => self.finish(),
1614             Some(idx) => {
1615                 let ret = Some(&self.v[..idx]);
1616                 self.v = &self.v[idx + 1..];
1617                 ret
1618             }
1619         }
1620     }
1621
1622     #[inline]
1623     fn size_hint(&self) -> (usize, Option<usize>) {
1624         if self.finished {
1625             (0, Some(0))
1626         } else {
1627             (1, Some(self.v.len() + 1))
1628         }
1629     }
1630 }
1631
1632 #[stable(feature = "rust1", since = "1.0.0")]
1633 impl<'a, T, P> DoubleEndedIterator for Split<'a, T, P> where P: FnMut(&T) -> bool {
1634     #[inline]
1635     fn next_back(&mut self) -> Option<&'a [T]> {
1636         if self.finished { return None; }
1637
1638         match self.v.iter().rposition(|x| (self.pred)(x)) {
1639             None => self.finish(),
1640             Some(idx) => {
1641                 let ret = Some(&self.v[idx + 1..]);
1642                 self.v = &self.v[..idx];
1643                 ret
1644             }
1645         }
1646     }
1647 }
1648
1649 impl<'a, T, P> SplitIter for Split<'a, T, P> where P: FnMut(&T) -> bool {
1650     #[inline]
1651     fn finish(&mut self) -> Option<&'a [T]> {
1652         if self.finished { None } else { self.finished = true; Some(self.v) }
1653     }
1654 }
1655
1656 #[unstable(feature = "fused", issue = "35602")]
1657 impl<'a, T, P> FusedIterator for Split<'a, T, P> where P: FnMut(&T) -> bool {}
1658
1659 /// An iterator over the subslices of the vector which are separated
1660 /// by elements that match `pred`.
1661 ///
1662 /// This struct is created by the [`split_mut`] method on [slices].
1663 ///
1664 /// [`split_mut`]: ../../std/primitive.slice.html#method.split_mut
1665 /// [slices]: ../../std/primitive.slice.html
1666 #[stable(feature = "rust1", since = "1.0.0")]
1667 pub struct SplitMut<'a, T:'a, P> where P: FnMut(&T) -> bool {
1668     v: &'a mut [T],
1669     pred: P,
1670     finished: bool
1671 }
1672
1673 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1674 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
1675     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1676         f.debug_struct("SplitMut")
1677             .field("v", &self.v)
1678             .field("finished", &self.finished)
1679             .finish()
1680     }
1681 }
1682
1683 impl<'a, T, P> SplitIter for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
1684     #[inline]
1685     fn finish(&mut self) -> Option<&'a mut [T]> {
1686         if self.finished {
1687             None
1688         } else {
1689             self.finished = true;
1690             Some(mem::replace(&mut self.v, &mut []))
1691         }
1692     }
1693 }
1694
1695 #[stable(feature = "rust1", since = "1.0.0")]
1696 impl<'a, T, P> Iterator for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
1697     type Item = &'a mut [T];
1698
1699     #[inline]
1700     fn next(&mut self) -> Option<&'a mut [T]> {
1701         if self.finished { return None; }
1702
1703         let idx_opt = { // work around borrowck limitations
1704             let pred = &mut self.pred;
1705             self.v.iter().position(|x| (*pred)(x))
1706         };
1707         match idx_opt {
1708             None => self.finish(),
1709             Some(idx) => {
1710                 let tmp = mem::replace(&mut self.v, &mut []);
1711                 let (head, tail) = tmp.split_at_mut(idx);
1712                 self.v = &mut tail[1..];
1713                 Some(head)
1714             }
1715         }
1716     }
1717
1718     #[inline]
1719     fn size_hint(&self) -> (usize, Option<usize>) {
1720         if self.finished {
1721             (0, Some(0))
1722         } else {
1723             // if the predicate doesn't match anything, we yield one slice
1724             // if it matches every element, we yield len+1 empty slices.
1725             (1, Some(self.v.len() + 1))
1726         }
1727     }
1728 }
1729
1730 #[stable(feature = "rust1", since = "1.0.0")]
1731 impl<'a, T, P> DoubleEndedIterator for SplitMut<'a, T, P> where
1732     P: FnMut(&T) -> bool,
1733 {
1734     #[inline]
1735     fn next_back(&mut self) -> Option<&'a mut [T]> {
1736         if self.finished { return None; }
1737
1738         let idx_opt = { // work around borrowck limitations
1739             let pred = &mut self.pred;
1740             self.v.iter().rposition(|x| (*pred)(x))
1741         };
1742         match idx_opt {
1743             None => self.finish(),
1744             Some(idx) => {
1745                 let tmp = mem::replace(&mut self.v, &mut []);
1746                 let (head, tail) = tmp.split_at_mut(idx);
1747                 self.v = head;
1748                 Some(&mut tail[1..])
1749             }
1750         }
1751     }
1752 }
1753
1754 #[unstable(feature = "fused", issue = "35602")]
1755 impl<'a, T, P> FusedIterator for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {}
1756
1757 /// An iterator over subslices separated by elements that match a predicate
1758 /// function, starting from the end of the slice.
1759 ///
1760 /// This struct is created by the [`rsplit`] method on [slices].
1761 ///
1762 /// [`rsplit`]: ../../std/primitive.slice.html#method.rsplit
1763 /// [slices]: ../../std/primitive.slice.html
1764 #[unstable(feature = "slice_rsplit", issue = "41020")]
1765 #[derive(Clone)] // Is this correct, or does it incorrectly require `T: Clone`?
1766 pub struct RSplit<'a, T:'a, P> where P: FnMut(&T) -> bool {
1767     inner: Split<'a, T, P>
1768 }
1769
1770 #[unstable(feature = "slice_rsplit", issue = "41020")]
1771 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for RSplit<'a, T, P> where P: FnMut(&T) -> bool {
1772     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1773         f.debug_struct("RSplit")
1774             .field("v", &self.inner.v)
1775             .field("finished", &self.inner.finished)
1776             .finish()
1777     }
1778 }
1779
1780 #[unstable(feature = "slice_rsplit", issue = "41020")]
1781 impl<'a, T, P> Iterator for RSplit<'a, T, P> where P: FnMut(&T) -> bool {
1782     type Item = &'a [T];
1783
1784     #[inline]
1785     fn next(&mut self) -> Option<&'a [T]> {
1786         self.inner.next_back()
1787     }
1788
1789     #[inline]
1790     fn size_hint(&self) -> (usize, Option<usize>) {
1791         self.inner.size_hint()
1792     }
1793 }
1794
1795 #[unstable(feature = "slice_rsplit", issue = "41020")]
1796 impl<'a, T, P> DoubleEndedIterator for RSplit<'a, T, P> where P: FnMut(&T) -> bool {
1797     #[inline]
1798     fn next_back(&mut self) -> Option<&'a [T]> {
1799         self.inner.next()
1800     }
1801 }
1802
1803 #[unstable(feature = "slice_rsplit", issue = "41020")]
1804 impl<'a, T, P> SplitIter for RSplit<'a, T, P> where P: FnMut(&T) -> bool {
1805     #[inline]
1806     fn finish(&mut self) -> Option<&'a [T]> {
1807         self.inner.finish()
1808     }
1809 }
1810
1811 //#[unstable(feature = "fused", issue = "35602")]
1812 #[unstable(feature = "slice_rsplit", issue = "41020")]
1813 impl<'a, T, P> FusedIterator for RSplit<'a, T, P> where P: FnMut(&T) -> bool {}
1814
1815 /// An iterator over the subslices of the vector which are separated
1816 /// by elements that match `pred`, starting from the end of the slice.
1817 ///
1818 /// This struct is created by the [`rsplit_mut`] method on [slices].
1819 ///
1820 /// [`rsplit_mut`]: ../../std/primitive.slice.html#method.rsplit_mut
1821 /// [slices]: ../../std/primitive.slice.html
1822 #[unstable(feature = "slice_rsplit", issue = "41020")]
1823 pub struct RSplitMut<'a, T:'a, P> where P: FnMut(&T) -> bool {
1824     inner: SplitMut<'a, T, P>
1825 }
1826
1827 #[unstable(feature = "slice_rsplit", issue = "41020")]
1828 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for RSplitMut<'a, T, P> where P: FnMut(&T) -> bool {
1829     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1830         f.debug_struct("RSplitMut")
1831             .field("v", &self.inner.v)
1832             .field("finished", &self.inner.finished)
1833             .finish()
1834     }
1835 }
1836
1837 #[unstable(feature = "slice_rsplit", issue = "41020")]
1838 impl<'a, T, P> SplitIter for RSplitMut<'a, T, P> where P: FnMut(&T) -> bool {
1839     #[inline]
1840     fn finish(&mut self) -> Option<&'a mut [T]> {
1841         self.inner.finish()
1842     }
1843 }
1844
1845 #[unstable(feature = "slice_rsplit", issue = "41020")]
1846 impl<'a, T, P> Iterator for RSplitMut<'a, T, P> where P: FnMut(&T) -> bool {
1847     type Item = &'a mut [T];
1848
1849     #[inline]
1850     fn next(&mut self) -> Option<&'a mut [T]> {
1851         self.inner.next_back()
1852     }
1853
1854     #[inline]
1855     fn size_hint(&self) -> (usize, Option<usize>) {
1856         self.inner.size_hint()
1857     }
1858 }
1859
1860 #[unstable(feature = "slice_rsplit", issue = "41020")]
1861 impl<'a, T, P> DoubleEndedIterator for RSplitMut<'a, T, P> where
1862     P: FnMut(&T) -> bool,
1863 {
1864     #[inline]
1865     fn next_back(&mut self) -> Option<&'a mut [T]> {
1866         self.inner.next()
1867     }
1868 }
1869
1870 //#[unstable(feature = "fused", issue = "35602")]
1871 #[unstable(feature = "slice_rsplit", issue = "41020")]
1872 impl<'a, T, P> FusedIterator for RSplitMut<'a, T, P> where P: FnMut(&T) -> bool {}
1873
1874 /// An private iterator over subslices separated by elements that
1875 /// match a predicate function, splitting at most a fixed number of
1876 /// times.
1877 #[derive(Debug)]
1878 struct GenericSplitN<I> {
1879     iter: I,
1880     count: usize,
1881 }
1882
1883 impl<T, I: SplitIter<Item=T>> Iterator for GenericSplitN<I> {
1884     type Item = T;
1885
1886     #[inline]
1887     fn next(&mut self) -> Option<T> {
1888         match self.count {
1889             0 => None,
1890             1 => { self.count -= 1; self.iter.finish() }
1891             _ => { self.count -= 1; self.iter.next() }
1892         }
1893     }
1894
1895     #[inline]
1896     fn size_hint(&self) -> (usize, Option<usize>) {
1897         let (lower, upper_opt) = self.iter.size_hint();
1898         (lower, upper_opt.map(|upper| cmp::min(self.count, upper)))
1899     }
1900 }
1901
1902 /// An iterator over subslices separated by elements that match a predicate
1903 /// function, limited to a given number of splits.
1904 ///
1905 /// This struct is created by the [`splitn`] method on [slices].
1906 ///
1907 /// [`splitn`]: ../../std/primitive.slice.html#method.splitn
1908 /// [slices]: ../../std/primitive.slice.html
1909 #[stable(feature = "rust1", since = "1.0.0")]
1910 pub struct SplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool {
1911     inner: GenericSplitN<Split<'a, T, P>>
1912 }
1913
1914 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1915 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for SplitN<'a, T, P> where P: FnMut(&T) -> bool {
1916     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1917         f.debug_struct("SplitN")
1918             .field("inner", &self.inner)
1919             .finish()
1920     }
1921 }
1922
1923 /// An iterator over subslices separated by elements that match a
1924 /// predicate function, limited to a given number of splits, starting
1925 /// from the end of the slice.
1926 ///
1927 /// This struct is created by the [`rsplitn`] method on [slices].
1928 ///
1929 /// [`rsplitn`]: ../../std/primitive.slice.html#method.rsplitn
1930 /// [slices]: ../../std/primitive.slice.html
1931 #[stable(feature = "rust1", since = "1.0.0")]
1932 pub struct RSplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool {
1933     inner: GenericSplitN<RSplit<'a, T, P>>
1934 }
1935
1936 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1937 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for RSplitN<'a, T, P> where P: FnMut(&T) -> bool {
1938     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1939         f.debug_struct("RSplitN")
1940             .field("inner", &self.inner)
1941             .finish()
1942     }
1943 }
1944
1945 /// An iterator over subslices separated by elements that match a predicate
1946 /// function, limited to a given number of splits.
1947 ///
1948 /// This struct is created by the [`splitn_mut`] method on [slices].
1949 ///
1950 /// [`splitn_mut`]: ../../std/primitive.slice.html#method.splitn_mut
1951 /// [slices]: ../../std/primitive.slice.html
1952 #[stable(feature = "rust1", since = "1.0.0")]
1953 pub struct SplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool {
1954     inner: GenericSplitN<SplitMut<'a, T, P>>
1955 }
1956
1957 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1958 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for SplitNMut<'a, T, P> where P: FnMut(&T) -> bool {
1959     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1960         f.debug_struct("SplitNMut")
1961             .field("inner", &self.inner)
1962             .finish()
1963     }
1964 }
1965
1966 /// An iterator over subslices separated by elements that match a
1967 /// predicate function, limited to a given number of splits, starting
1968 /// from the end of the slice.
1969 ///
1970 /// This struct is created by the [`rsplitn_mut`] method on [slices].
1971 ///
1972 /// [`rsplitn_mut`]: ../../std/primitive.slice.html#method.rsplitn_mut
1973 /// [slices]: ../../std/primitive.slice.html
1974 #[stable(feature = "rust1", since = "1.0.0")]
1975 pub struct RSplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool {
1976     inner: GenericSplitN<RSplitMut<'a, T, P>>
1977 }
1978
1979 #[stable(feature = "core_impl_debug", since = "1.9.0")]
1980 impl<'a, T: 'a + fmt::Debug, P> fmt::Debug for RSplitNMut<'a, T, P> where P: FnMut(&T) -> bool {
1981     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1982         f.debug_struct("RSplitNMut")
1983             .field("inner", &self.inner)
1984             .finish()
1985     }
1986 }
1987
1988 macro_rules! forward_iterator {
1989     ($name:ident: $elem:ident, $iter_of:ty) => {
1990         #[stable(feature = "rust1", since = "1.0.0")]
1991         impl<'a, $elem, P> Iterator for $name<'a, $elem, P> where
1992             P: FnMut(&T) -> bool
1993         {
1994             type Item = $iter_of;
1995
1996             #[inline]
1997             fn next(&mut self) -> Option<$iter_of> {
1998                 self.inner.next()
1999             }
2000
2001             #[inline]
2002             fn size_hint(&self) -> (usize, Option<usize>) {
2003                 self.inner.size_hint()
2004             }
2005         }
2006
2007         #[unstable(feature = "fused", issue = "35602")]
2008         impl<'a, $elem, P> FusedIterator for $name<'a, $elem, P>
2009             where P: FnMut(&T) -> bool {}
2010     }
2011 }
2012
2013 forward_iterator! { SplitN: T, &'a [T] }
2014 forward_iterator! { RSplitN: T, &'a [T] }
2015 forward_iterator! { SplitNMut: T, &'a mut [T] }
2016 forward_iterator! { RSplitNMut: T, &'a mut [T] }
2017
2018 /// An iterator over overlapping subslices of length `size`.
2019 ///
2020 /// This struct is created by the [`windows`] method on [slices].
2021 ///
2022 /// [`windows`]: ../../std/primitive.slice.html#method.windows
2023 /// [slices]: ../../std/primitive.slice.html
2024 #[derive(Debug)]
2025 #[stable(feature = "rust1", since = "1.0.0")]
2026 pub struct Windows<'a, T:'a> {
2027     v: &'a [T],
2028     size: usize
2029 }
2030
2031 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
2032 #[stable(feature = "rust1", since = "1.0.0")]
2033 impl<'a, T> Clone for Windows<'a, T> {
2034     fn clone(&self) -> Windows<'a, T> {
2035         Windows {
2036             v: self.v,
2037             size: self.size,
2038         }
2039     }
2040 }
2041
2042 #[stable(feature = "rust1", since = "1.0.0")]
2043 impl<'a, T> Iterator for Windows<'a, T> {
2044     type Item = &'a [T];
2045
2046     #[inline]
2047     fn next(&mut self) -> Option<&'a [T]> {
2048         if self.size > self.v.len() {
2049             None
2050         } else {
2051             let ret = Some(&self.v[..self.size]);
2052             self.v = &self.v[1..];
2053             ret
2054         }
2055     }
2056
2057     #[inline]
2058     fn size_hint(&self) -> (usize, Option<usize>) {
2059         if self.size > self.v.len() {
2060             (0, Some(0))
2061         } else {
2062             let size = self.v.len() - self.size + 1;
2063             (size, Some(size))
2064         }
2065     }
2066
2067     #[inline]
2068     fn count(self) -> usize {
2069         self.len()
2070     }
2071
2072     #[inline]
2073     fn nth(&mut self, n: usize) -> Option<Self::Item> {
2074         let (end, overflow) = self.size.overflowing_add(n);
2075         if end > self.v.len() || overflow {
2076             self.v = &[];
2077             None
2078         } else {
2079             let nth = &self.v[n..end];
2080             self.v = &self.v[n+1..];
2081             Some(nth)
2082         }
2083     }
2084
2085     #[inline]
2086     fn last(self) -> Option<Self::Item> {
2087         if self.size > self.v.len() {
2088             None
2089         } else {
2090             let start = self.v.len() - self.size;
2091             Some(&self.v[start..])
2092         }
2093     }
2094 }
2095
2096 #[stable(feature = "rust1", since = "1.0.0")]
2097 impl<'a, T> DoubleEndedIterator for Windows<'a, T> {
2098     #[inline]
2099     fn next_back(&mut self) -> Option<&'a [T]> {
2100         if self.size > self.v.len() {
2101             None
2102         } else {
2103             let ret = Some(&self.v[self.v.len()-self.size..]);
2104             self.v = &self.v[..self.v.len()-1];
2105             ret
2106         }
2107     }
2108 }
2109
2110 #[stable(feature = "rust1", since = "1.0.0")]
2111 impl<'a, T> ExactSizeIterator for Windows<'a, T> {}
2112
2113 #[unstable(feature = "fused", issue = "35602")]
2114 impl<'a, T> FusedIterator for Windows<'a, T> {}
2115
2116 /// An iterator over a slice in (non-overlapping) chunks (`size` elements at a
2117 /// time).
2118 ///
2119 /// When the slice len is not evenly divided by the chunk size, the last slice
2120 /// of the iteration will be the remainder.
2121 ///
2122 /// This struct is created by the [`chunks`] method on [slices].
2123 ///
2124 /// [`chunks`]: ../../std/primitive.slice.html#method.chunks
2125 /// [slices]: ../../std/primitive.slice.html
2126 #[derive(Debug)]
2127 #[stable(feature = "rust1", since = "1.0.0")]
2128 pub struct Chunks<'a, T:'a> {
2129     v: &'a [T],
2130     size: usize
2131 }
2132
2133 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
2134 #[stable(feature = "rust1", since = "1.0.0")]
2135 impl<'a, T> Clone for Chunks<'a, T> {
2136     fn clone(&self) -> Chunks<'a, T> {
2137         Chunks {
2138             v: self.v,
2139             size: self.size,
2140         }
2141     }
2142 }
2143
2144 #[stable(feature = "rust1", since = "1.0.0")]
2145 impl<'a, T> Iterator for Chunks<'a, T> {
2146     type Item = &'a [T];
2147
2148     #[inline]
2149     fn next(&mut self) -> Option<&'a [T]> {
2150         if self.v.is_empty() {
2151             None
2152         } else {
2153             let chunksz = cmp::min(self.v.len(), self.size);
2154             let (fst, snd) = self.v.split_at(chunksz);
2155             self.v = snd;
2156             Some(fst)
2157         }
2158     }
2159
2160     #[inline]
2161     fn size_hint(&self) -> (usize, Option<usize>) {
2162         if self.v.is_empty() {
2163             (0, Some(0))
2164         } else {
2165             let n = self.v.len() / self.size;
2166             let rem = self.v.len() % self.size;
2167             let n = if rem > 0 { n+1 } else { n };
2168             (n, Some(n))
2169         }
2170     }
2171
2172     #[inline]
2173     fn count(self) -> usize {
2174         self.len()
2175     }
2176
2177     #[inline]
2178     fn nth(&mut self, n: usize) -> Option<Self::Item> {
2179         let (start, overflow) = n.overflowing_mul(self.size);
2180         if start >= self.v.len() || overflow {
2181             self.v = &[];
2182             None
2183         } else {
2184             let end = match start.checked_add(self.size) {
2185                 Some(sum) => cmp::min(self.v.len(), sum),
2186                 None => self.v.len(),
2187             };
2188             let nth = &self.v[start..end];
2189             self.v = &self.v[end..];
2190             Some(nth)
2191         }
2192     }
2193
2194     #[inline]
2195     fn last(self) -> Option<Self::Item> {
2196         if self.v.is_empty() {
2197             None
2198         } else {
2199             let start = (self.v.len() - 1) / self.size * self.size;
2200             Some(&self.v[start..])
2201         }
2202     }
2203 }
2204
2205 #[stable(feature = "rust1", since = "1.0.0")]
2206 impl<'a, T> DoubleEndedIterator for Chunks<'a, T> {
2207     #[inline]
2208     fn next_back(&mut self) -> Option<&'a [T]> {
2209         if self.v.is_empty() {
2210             None
2211         } else {
2212             let remainder = self.v.len() % self.size;
2213             let chunksz = if remainder != 0 { remainder } else { self.size };
2214             let (fst, snd) = self.v.split_at(self.v.len() - chunksz);
2215             self.v = fst;
2216             Some(snd)
2217         }
2218     }
2219 }
2220
2221 #[stable(feature = "rust1", since = "1.0.0")]
2222 impl<'a, T> ExactSizeIterator for Chunks<'a, T> {}
2223
2224 #[unstable(feature = "fused", issue = "35602")]
2225 impl<'a, T> FusedIterator for Chunks<'a, T> {}
2226
2227 /// An iterator over a slice in (non-overlapping) mutable chunks (`size`
2228 /// elements at a time). When the slice len is not evenly divided by the chunk
2229 /// size, the last slice of the iteration will be the remainder.
2230 ///
2231 /// This struct is created by the [`chunks_mut`] method on [slices].
2232 ///
2233 /// [`chunks_mut`]: ../../std/primitive.slice.html#method.chunks_mut
2234 /// [slices]: ../../std/primitive.slice.html
2235 #[derive(Debug)]
2236 #[stable(feature = "rust1", since = "1.0.0")]
2237 pub struct ChunksMut<'a, T:'a> {
2238     v: &'a mut [T],
2239     chunk_size: usize
2240 }
2241
2242 #[stable(feature = "rust1", since = "1.0.0")]
2243 impl<'a, T> Iterator for ChunksMut<'a, T> {
2244     type Item = &'a mut [T];
2245
2246     #[inline]
2247     fn next(&mut self) -> Option<&'a mut [T]> {
2248         if self.v.is_empty() {
2249             None
2250         } else {
2251             let sz = cmp::min(self.v.len(), self.chunk_size);
2252             let tmp = mem::replace(&mut self.v, &mut []);
2253             let (head, tail) = tmp.split_at_mut(sz);
2254             self.v = tail;
2255             Some(head)
2256         }
2257     }
2258
2259     #[inline]
2260     fn size_hint(&self) -> (usize, Option<usize>) {
2261         if self.v.is_empty() {
2262             (0, Some(0))
2263         } else {
2264             let n = self.v.len() / self.chunk_size;
2265             let rem = self.v.len() % self.chunk_size;
2266             let n = if rem > 0 { n + 1 } else { n };
2267             (n, Some(n))
2268         }
2269     }
2270
2271     #[inline]
2272     fn count(self) -> usize {
2273         self.len()
2274     }
2275
2276     #[inline]
2277     fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
2278         let (start, overflow) = n.overflowing_mul(self.chunk_size);
2279         if start >= self.v.len() || overflow {
2280             self.v = &mut [];
2281             None
2282         } else {
2283             let end = match start.checked_add(self.chunk_size) {
2284                 Some(sum) => cmp::min(self.v.len(), sum),
2285                 None => self.v.len(),
2286             };
2287             let tmp = mem::replace(&mut self.v, &mut []);
2288             let (head, tail) = tmp.split_at_mut(end);
2289             let (_, nth) =  head.split_at_mut(start);
2290             self.v = tail;
2291             Some(nth)
2292         }
2293     }
2294
2295     #[inline]
2296     fn last(self) -> Option<Self::Item> {
2297         if self.v.is_empty() {
2298             None
2299         } else {
2300             let start = (self.v.len() - 1) / self.chunk_size * self.chunk_size;
2301             Some(&mut self.v[start..])
2302         }
2303     }
2304 }
2305
2306 #[stable(feature = "rust1", since = "1.0.0")]
2307 impl<'a, T> DoubleEndedIterator for ChunksMut<'a, T> {
2308     #[inline]
2309     fn next_back(&mut self) -> Option<&'a mut [T]> {
2310         if self.v.is_empty() {
2311             None
2312         } else {
2313             let remainder = self.v.len() % self.chunk_size;
2314             let sz = if remainder != 0 { remainder } else { self.chunk_size };
2315             let tmp = mem::replace(&mut self.v, &mut []);
2316             let tmp_len = tmp.len();
2317             let (head, tail) = tmp.split_at_mut(tmp_len - sz);
2318             self.v = head;
2319             Some(tail)
2320         }
2321     }
2322 }
2323
2324 #[stable(feature = "rust1", since = "1.0.0")]
2325 impl<'a, T> ExactSizeIterator for ChunksMut<'a, T> {}
2326
2327 #[unstable(feature = "fused", issue = "35602")]
2328 impl<'a, T> FusedIterator for ChunksMut<'a, T> {}
2329
2330 //
2331 // Free functions
2332 //
2333
2334 /// Forms a slice from a pointer and a length.
2335 ///
2336 /// The `len` argument is the number of **elements**, not the number of bytes.
2337 ///
2338 /// # Safety
2339 ///
2340 /// This function is unsafe as there is no guarantee that the given pointer is
2341 /// valid for `len` elements, nor whether the lifetime inferred is a suitable
2342 /// lifetime for the returned slice.
2343 ///
2344 /// `p` must be non-null, even for zero-length slices.
2345 ///
2346 /// # Caveat
2347 ///
2348 /// The lifetime for the returned slice is inferred from its usage. To
2349 /// prevent accidental misuse, it's suggested to tie the lifetime to whichever
2350 /// source lifetime is safe in the context, such as by providing a helper
2351 /// function taking the lifetime of a host value for the slice, or by explicit
2352 /// annotation.
2353 ///
2354 /// # Examples
2355 ///
2356 /// ```
2357 /// use std::slice;
2358 ///
2359 /// // manifest a slice out of thin air!
2360 /// let ptr = 0x1234 as *const usize;
2361 /// let amt = 10;
2362 /// unsafe {
2363 ///     let slice = slice::from_raw_parts(ptr, amt);
2364 /// }
2365 /// ```
2366 #[inline]
2367 #[stable(feature = "rust1", since = "1.0.0")]
2368 pub unsafe fn from_raw_parts<'a, T>(p: *const T, len: usize) -> &'a [T] {
2369     mem::transmute(Repr { data: p, len: len })
2370 }
2371
2372 /// Performs the same functionality as `from_raw_parts`, except that a mutable
2373 /// slice is returned.
2374 ///
2375 /// This function is unsafe for the same reasons as `from_raw_parts`, as well
2376 /// as not being able to provide a non-aliasing guarantee of the returned
2377 /// mutable slice.
2378 #[inline]
2379 #[stable(feature = "rust1", since = "1.0.0")]
2380 pub unsafe fn from_raw_parts_mut<'a, T>(p: *mut T, len: usize) -> &'a mut [T] {
2381     mem::transmute(Repr { data: p, len: len })
2382 }
2383
2384 // This function is public only because there is no other way to unit test heapsort.
2385 #[unstable(feature = "sort_internals", reason = "internal to sort module", issue = "0")]
2386 #[doc(hidden)]
2387 pub fn heapsort<T, F>(v: &mut [T], mut is_less: F)
2388     where F: FnMut(&T, &T) -> bool
2389 {
2390     sort::heapsort(v, &mut is_less);
2391 }
2392
2393 //
2394 // Comparison traits
2395 //
2396
2397 extern {
2398     /// Calls implementation provided memcmp.
2399     ///
2400     /// Interprets the data as u8.
2401     ///
2402     /// Returns 0 for equal, < 0 for less than and > 0 for greater
2403     /// than.
2404     // FIXME(#32610): Return type should be c_int
2405     fn memcmp(s1: *const u8, s2: *const u8, n: usize) -> i32;
2406 }
2407
2408 #[stable(feature = "rust1", since = "1.0.0")]
2409 impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> {
2410     fn eq(&self, other: &[B]) -> bool {
2411         SlicePartialEq::equal(self, other)
2412     }
2413
2414     fn ne(&self, other: &[B]) -> bool {
2415         SlicePartialEq::not_equal(self, other)
2416     }
2417 }
2418
2419 #[stable(feature = "rust1", since = "1.0.0")]
2420 impl<T: Eq> Eq for [T] {}
2421
2422 /// Implements comparison of vectors lexicographically.
2423 #[stable(feature = "rust1", since = "1.0.0")]
2424 impl<T: Ord> Ord for [T] {
2425     fn cmp(&self, other: &[T]) -> Ordering {
2426         SliceOrd::compare(self, other)
2427     }
2428 }
2429
2430 /// Implements comparison of vectors lexicographically.
2431 #[stable(feature = "rust1", since = "1.0.0")]
2432 impl<T: PartialOrd> PartialOrd for [T] {
2433     fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
2434         SlicePartialOrd::partial_compare(self, other)
2435     }
2436 }
2437
2438 #[doc(hidden)]
2439 // intermediate trait for specialization of slice's PartialEq
2440 trait SlicePartialEq<B> {
2441     fn equal(&self, other: &[B]) -> bool;
2442
2443     fn not_equal(&self, other: &[B]) -> bool { !self.equal(other) }
2444 }
2445
2446 // Generic slice equality
2447 impl<A, B> SlicePartialEq<B> for [A]
2448     where A: PartialEq<B>
2449 {
2450     default fn equal(&self, other: &[B]) -> bool {
2451         if self.len() != other.len() {
2452             return false;
2453         }
2454
2455         for i in 0..self.len() {
2456             if !self[i].eq(&other[i]) {
2457                 return false;
2458             }
2459         }
2460
2461         true
2462     }
2463 }
2464
2465 // Use memcmp for bytewise equality when the types allow
2466 impl<A> SlicePartialEq<A> for [A]
2467     where A: PartialEq<A> + BytewiseEquality
2468 {
2469     fn equal(&self, other: &[A]) -> bool {
2470         if self.len() != other.len() {
2471             return false;
2472         }
2473         if self.as_ptr() == other.as_ptr() {
2474             return true;
2475         }
2476         unsafe {
2477             let size = mem::size_of_val(self);
2478             memcmp(self.as_ptr() as *const u8,
2479                    other.as_ptr() as *const u8, size) == 0
2480         }
2481     }
2482 }
2483
2484 #[doc(hidden)]
2485 // intermediate trait for specialization of slice's PartialOrd
2486 trait SlicePartialOrd<B> {
2487     fn partial_compare(&self, other: &[B]) -> Option<Ordering>;
2488 }
2489
2490 impl<A> SlicePartialOrd<A> for [A]
2491     where A: PartialOrd
2492 {
2493     default fn partial_compare(&self, other: &[A]) -> Option<Ordering> {
2494         let l = cmp::min(self.len(), other.len());
2495
2496         // Slice to the loop iteration range to enable bound check
2497         // elimination in the compiler
2498         let lhs = &self[..l];
2499         let rhs = &other[..l];
2500
2501         for i in 0..l {
2502             match lhs[i].partial_cmp(&rhs[i]) {
2503                 Some(Ordering::Equal) => (),
2504                 non_eq => return non_eq,
2505             }
2506         }
2507
2508         self.len().partial_cmp(&other.len())
2509     }
2510 }
2511
2512 impl<A> SlicePartialOrd<A> for [A]
2513     where A: Ord
2514 {
2515     default fn partial_compare(&self, other: &[A]) -> Option<Ordering> {
2516         Some(SliceOrd::compare(self, other))
2517     }
2518 }
2519
2520 #[doc(hidden)]
2521 // intermediate trait for specialization of slice's Ord
2522 trait SliceOrd<B> {
2523     fn compare(&self, other: &[B]) -> Ordering;
2524 }
2525
2526 impl<A> SliceOrd<A> for [A]
2527     where A: Ord
2528 {
2529     default fn compare(&self, other: &[A]) -> Ordering {
2530         let l = cmp::min(self.len(), other.len());
2531
2532         // Slice to the loop iteration range to enable bound check
2533         // elimination in the compiler
2534         let lhs = &self[..l];
2535         let rhs = &other[..l];
2536
2537         for i in 0..l {
2538             match lhs[i].cmp(&rhs[i]) {
2539                 Ordering::Equal => (),
2540                 non_eq => return non_eq,
2541             }
2542         }
2543
2544         self.len().cmp(&other.len())
2545     }
2546 }
2547
2548 // memcmp compares a sequence of unsigned bytes lexicographically.
2549 // this matches the order we want for [u8], but no others (not even [i8]).
2550 impl SliceOrd<u8> for [u8] {
2551     #[inline]
2552     fn compare(&self, other: &[u8]) -> Ordering {
2553         let order = unsafe {
2554             memcmp(self.as_ptr(), other.as_ptr(),
2555                    cmp::min(self.len(), other.len()))
2556         };
2557         if order == 0 {
2558             self.len().cmp(&other.len())
2559         } else if order < 0 {
2560             Less
2561         } else {
2562             Greater
2563         }
2564     }
2565 }
2566
2567 #[doc(hidden)]
2568 /// Trait implemented for types that can be compared for equality using
2569 /// their bytewise representation
2570 trait BytewiseEquality { }
2571
2572 macro_rules! impl_marker_for {
2573     ($traitname:ident, $($ty:ty)*) => {
2574         $(
2575             impl $traitname for $ty { }
2576         )*
2577     }
2578 }
2579
2580 impl_marker_for!(BytewiseEquality,
2581                  u8 i8 u16 i16 u32 i32 u64 i64 usize isize char bool);
2582
2583 #[doc(hidden)]
2584 unsafe impl<'a, T> TrustedRandomAccess for Iter<'a, T> {
2585     unsafe fn get_unchecked(&mut self, i: usize) -> &'a T {
2586         &*self.ptr.offset(i as isize)
2587     }
2588     fn may_have_side_effect() -> bool { false }
2589 }
2590
2591 #[doc(hidden)]
2592 unsafe impl<'a, T> TrustedRandomAccess for IterMut<'a, T> {
2593     unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut T {
2594         &mut *self.ptr.offset(i as isize)
2595     }
2596     fn may_have_side_effect() -> bool { false }
2597 }