src/libcore/slice.rs

   1 // Copyright 2012-2014 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 `std::slice`.
  14
  15 #![stable(feature = "rust1", since = "1.0.0")]
  16 #![doc(primitive = "slice")]
  17
  18 // How this module is organized.
  19 //
  20 // The library infrastructure for slices is fairly messy. There's
  21 // a lot of stuff defined here. Let's keep it clean.
  22 //
  23 // Since slices don't support inherent methods; all operations
  24 // on them are defined on traits, which are then reexported from
  25 // the prelude for convenience. So there are a lot of traits here.
  26 //
  27 // The layout of this file is thus:
  28 //
  29 // * Slice-specific 'extension' traits and their implementations. This
  30 //   is where most of the slice API resides.
  31 // * Implementations of a few common traits with important slice ops.
  32 // * Definitions of a bunch of iterators.
  33 // * Free functions.
  34 // * The `raw` and `bytes` submodules.
  35 // * Boilerplate trait implementations.
  36
  37 use mem::transmute;
  38 use clone::Clone;
  39 use cmp::{Ordering, PartialEq, PartialOrd, Eq, Ord};
  40 use cmp::Ordering::{Less, Equal, Greater};
  41 use cmp;
  42 use default::Default;
  43 use intrinsics::assume;
  44 use iter::*;
  45 use ops::{FnMut, self, Index};
  46 use ops::RangeFull;
  47 use option::Option;
  48 use option::Option::{None, Some};
  49 use result::Result;
  50 use result::Result::{Ok, Err};
  51 use ptr;
  52 use mem;
  53 use mem::size_of;
  54 use marker::{Send, Sync, self};
  55 use raw::Repr;
  56 // Avoid conflicts with *both* the Slice trait (buggy) and the `slice::raw` module.
  57 use raw::Slice as RawSlice;
  58
  59
  60 //
  61 // Extension traits
  62 //
  63
  64 /// Extension methods for slices.
  65 #[allow(missing_docs)] // docs in libcollections
  66 #[doc(hidden)]
  67 #[unstable(feature = "core_slice_ext",
  68            reason = "stable interface provided by `impl [T]` in later crates")]
  69 pub trait SliceExt {
  70     type Item;
  71
  72     fn split_at<'a>(&'a self, mid: usize) -> (&'a [Self::Item], &'a [Self::Item]);
  73     fn iter<'a>(&'a self) -> Iter<'a, Self::Item>;
  74     fn split<'a, P>(&'a self, pred: P) -> Split<'a, Self::Item, P>
  75                     where P: FnMut(&Self::Item) -> bool;
  76     fn splitn<'a, P>(&'a self, n: usize, pred: P) -> SplitN<'a, Self::Item, P>
  77                      where P: FnMut(&Self::Item) -> bool;
  78     fn rsplitn<'a, P>(&'a self,  n: usize, pred: P) -> RSplitN<'a, Self::Item, P>
  79                       where P: FnMut(&Self::Item) -> bool;
  80     fn windows<'a>(&'a self, size: usize) -> Windows<'a, Self::Item>;
  81     fn chunks<'a>(&'a self, size: usize) -> Chunks<'a, Self::Item>;
  82     fn get<'a>(&'a self, index: usize) -> Option<&'a Self::Item>;
  83     fn first<'a>(&'a self) -> Option<&'a Self::Item>;
  84     fn tail<'a>(&'a self) -> &'a [Self::Item];
  85     fn init<'a>(&'a self) -> &'a [Self::Item];
  86     fn last<'a>(&'a self) -> Option<&'a Self::Item>;
  87     unsafe fn get_unchecked<'a>(&'a self, index: usize) -> &'a Self::Item;
  88     fn as_ptr(&self) -> *const Self::Item;
  89     fn binary_search_by<F>(&self, f: F) -> Result<usize, usize> where
  90         F: FnMut(&Self::Item) -> Ordering;
  91     fn len(&self) -> usize;
  92     fn is_empty(&self) -> bool { self.len() == 0 }
  93     fn get_mut<'a>(&'a mut self, index: usize) -> Option<&'a mut Self::Item>;
  94     fn iter_mut<'a>(&'a mut self) -> IterMut<'a, Self::Item>;
  95     fn first_mut<'a>(&'a mut self) -> Option<&'a mut Self::Item>;
  96     fn tail_mut<'a>(&'a mut self) -> &'a mut [Self::Item];
  97     fn init_mut<'a>(&'a mut self) -> &'a mut [Self::Item];
  98     fn last_mut<'a>(&'a mut self) -> Option<&'a mut Self::Item>;
  99     fn split_mut<'a, P>(&'a mut self, pred: P) -> SplitMut<'a, Self::Item, P>
 100                         where P: FnMut(&Self::Item) -> bool;
 101     fn splitn_mut<P>(&mut self, n: usize, pred: P) -> SplitNMut<Self::Item, P>
 102                      where P: FnMut(&Self::Item) -> bool;
 103     fn rsplitn_mut<P>(&mut self,  n: usize, pred: P) -> RSplitNMut<Self::Item, P>
 104                       where P: FnMut(&Self::Item) -> bool;
 105     fn chunks_mut<'a>(&'a mut self, chunk_size: usize) -> ChunksMut<'a, Self::Item>;
 106     fn swap(&mut self, a: usize, b: usize);
 107     fn split_at_mut<'a>(&'a mut self, mid: usize) -> (&'a mut [Self::Item], &'a mut [Self::Item]);
 108     fn reverse(&mut self);
 109     unsafe fn get_unchecked_mut<'a>(&'a mut self, index: usize) -> &'a mut Self::Item;
 110     fn as_mut_ptr(&mut self) -> *mut Self::Item;
 111
 112     fn position_elem(&self, t: &Self::Item) -> Option<usize> where Self::Item: PartialEq;
 113
 114     fn rposition_elem(&self, t: &Self::Item) -> Option<usize> where Self::Item: PartialEq;
 115
 116     fn contains(&self, x: &Self::Item) -> bool where Self::Item: PartialEq;
 117
 118     fn starts_with(&self, needle: &[Self::Item]) -> bool where Self::Item: PartialEq;
 119
 120     fn ends_with(&self, needle: &[Self::Item]) -> bool where Self::Item: PartialEq;
 121
 122     fn binary_search(&self, x: &Self::Item) -> Result<usize, usize> where Self::Item: Ord;
 123     fn next_permutation(&mut self) -> bool where Self::Item: Ord;
 124     fn prev_permutation(&mut self) -> bool where Self::Item: Ord;
 125
 126     fn clone_from_slice(&mut self, &[Self::Item]) -> usize where Self::Item: Clone;
 127 }
 128
 129 // Use macros to be generic over const/mut
 130 macro_rules! slice_offset {
 131     ($ptr:expr, $by:expr) => {{
 132         let ptr = $ptr;
 133         if size_from_ptr(ptr) == 0 {
 134             ::intrinsics::arith_offset(ptr as *mut i8, $by) as *mut _
 135         } else {
 136             ptr.offset($by)
 137         }
 138     }};
 139 }
 140
 141 macro_rules! slice_ref {
 142     ($ptr:expr) => {{
 143         let ptr = $ptr;
 144         if size_from_ptr(ptr) == 0 {
 145             // Use a non-null pointer value
 146             &mut *(1 as *mut _)
 147         } else {
 148             transmute(ptr)
 149         }
 150     }};
 151 }
 152
 153 impl<T> SliceExt for [T] {
 154     type Item = T;
 155
 156     #[inline]
 157     fn split_at(&self, mid: usize) -> (&[T], &[T]) {
 158         (&self[..mid], &self[mid..])
 159     }
 160
 161     #[inline]
 162     fn iter<'a>(&'a self) -> Iter<'a, T> {
 163         unsafe {
 164             let p = if mem::size_of::<T>() == 0 {
 165                 1 as *const _
 166             } else {
 167                 let p = self.as_ptr();
 168                 assume(!p.is_null());
 169                 p
 170             };
 171
 172             Iter {
 173                 ptr: p,
 174                 end: slice_offset!(p, self.len() as isize),
 175                 _marker: marker::PhantomData
 176             }
 177         }
 178     }
 179
 180     #[inline]
 181     fn split<'a, P>(&'a self, pred: P) -> Split<'a, T, P> where P: FnMut(&T) -> bool {
 182         Split {
 183             v: self,
 184             pred: pred,
 185             finished: false
 186         }
 187     }
 188
 189     #[inline]
 190     fn splitn<'a, P>(&'a self, n: usize, pred: P) -> SplitN<'a, T, P> where
 191         P: FnMut(&T) -> bool,
 192     {
 193         SplitN {
 194             inner: GenericSplitN {
 195                 iter: self.split(pred),
 196                 count: n,
 197                 invert: false
 198             }
 199         }
 200     }
 201
 202     #[inline]
 203     fn rsplitn<'a, P>(&'a self, n: usize, pred: P) -> RSplitN<'a, T, P> where
 204         P: FnMut(&T) -> bool,
 205     {
 206         RSplitN {
 207             inner: GenericSplitN {
 208                 iter: self.split(pred),
 209                 count: n,
 210                 invert: true
 211             }
 212         }
 213     }
 214
 215     #[inline]
 216     fn windows(&self, size: usize) -> Windows<T> {
 217         assert!(size != 0);
 218         Windows { v: self, size: size }
 219     }
 220
 221     #[inline]
 222     fn chunks(&self, size: usize) -> Chunks<T> {
 223         assert!(size != 0);
 224         Chunks { v: self, size: size }
 225     }
 226
 227     #[inline]
 228     fn get(&self, index: usize) -> Option<&T> {
 229         if index < self.len() { Some(&self[index]) } else { None }
 230     }
 231
 232     #[inline]
 233     fn first(&self) -> Option<&T> {
 234         if self.is_empty() { None } else { Some(&self[0]) }
 235     }
 236
 237     #[inline]
 238     fn tail(&self) -> &[T] { &self[1..] }
 239
 240     #[inline]
 241     fn init(&self) -> &[T] {
 242         &self[..self.len() - 1]
 243     }
 244
 245     #[inline]
 246     fn last(&self) -> Option<&T> {
 247         if self.is_empty() { None } else { Some(&self[self.len() - 1]) }
 248     }
 249
 250     #[inline]
 251     unsafe fn get_unchecked(&self, index: usize) -> &T {
 252         transmute(self.repr().data.offset(index as isize))
 253     }
 254
 255     #[inline]
 256     fn as_ptr(&self) -> *const T {
 257         self.repr().data
 258     }
 259
 260     fn binary_search_by<F>(&self, mut f: F) -> Result<usize, usize> where
 261         F: FnMut(&T) -> Ordering
 262     {
 263         let mut base : usize = 0;
 264         let mut lim : usize = self.len();
 265
 266         while lim != 0 {
 267             let ix = base + (lim >> 1);
 268             match f(&self[ix]) {
 269                 Equal => return Ok(ix),
 270                 Less => {
 271                     base = ix + 1;
 272                     lim -= 1;
 273                 }
 274                 Greater => ()
 275             }
 276             lim >>= 1;
 277         }
 278         Err(base)
 279     }
 280
 281     #[inline]
 282     fn len(&self) -> usize { self.repr().len }
 283
 284     #[inline]
 285     fn get_mut(&mut self, index: usize) -> Option<&mut T> {
 286         if index < self.len() { Some(&mut self[index]) } else { None }
 287     }
 288
 289     #[inline]
 290     fn split_at_mut(&mut self, mid: usize) -> (&mut [T], &mut [T]) {
 291         unsafe {
 292             let self2: &mut [T] = mem::transmute_copy(&self);
 293
 294             (ops::IndexMut::index_mut(self, ops::RangeTo { end: mid } ),
 295              ops::IndexMut::index_mut(self2, ops::RangeFrom { start: mid } ))
 296         }
 297     }
 298
 299     #[inline]
 300     fn iter_mut<'a>(&'a mut self) -> IterMut<'a, T> {
 301         unsafe {
 302             let p = if mem::size_of::<T>() == 0 {
 303                 1 as *mut _
 304             } else {
 305                 let p = self.as_mut_ptr();
 306                 assume(!p.is_null());
 307                 p
 308             };
 309
 310             IterMut {
 311                 ptr: p,
 312                 end: slice_offset!(p, self.len() as isize),
 313                 _marker: marker::PhantomData
 314             }
 315         }
 316     }
 317
 318     #[inline]
 319     fn last_mut(&mut self) -> Option<&mut T> {
 320         let len = self.len();
 321         if len == 0 { return None; }
 322         Some(&mut self[len - 1])
 323     }
 324
 325     #[inline]
 326     fn first_mut(&mut self) -> Option<&mut T> {
 327         if self.is_empty() { None } else { Some(&mut self[0]) }
 328     }
 329
 330     #[inline]
 331     fn tail_mut(&mut self) -> &mut [T] {
 332         &mut self[1 ..]
 333     }
 334
 335     #[inline]
 336     fn init_mut(&mut self) -> &mut [T] {
 337         let len = self.len();
 338         &mut self[.. (len - 1)]
 339     }
 340
 341     #[inline]
 342     fn split_mut<'a, P>(&'a mut self, pred: P) -> SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
 343         SplitMut { v: self, pred: pred, finished: false }
 344     }
 345
 346     #[inline]
 347     fn splitn_mut<'a, P>(&'a mut self, n: usize, pred: P) -> SplitNMut<'a, T, P> where
 348         P: FnMut(&T) -> bool
 349     {
 350         SplitNMut {
 351             inner: GenericSplitN {
 352                 iter: self.split_mut(pred),
 353                 count: n,
 354                 invert: false
 355             }
 356         }
 357     }
 358
 359     #[inline]
 360     fn rsplitn_mut<'a, P>(&'a mut self, n: usize, pred: P) -> RSplitNMut<'a, T, P> where
 361         P: FnMut(&T) -> bool,
 362     {
 363         RSplitNMut {
 364             inner: GenericSplitN {
 365                 iter: self.split_mut(pred),
 366                 count: n,
 367                 invert: true
 368             }
 369         }
 370    }
 371
 372     #[inline]
 373     fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<T> {
 374         assert!(chunk_size > 0);
 375         ChunksMut { v: self, chunk_size: chunk_size }
 376     }
 377
 378     #[inline]
 379     fn swap(&mut self, a: usize, b: usize) {
 380         unsafe {
 381             // Can't take two mutable loans from one vector, so instead just cast
 382             // them to their raw pointers to do the swap
 383             let pa: *mut T = &mut self[a];
 384             let pb: *mut T = &mut self[b];
 385             ptr::swap(pa, pb);
 386         }
 387     }
 388
 389     fn reverse(&mut self) {
 390         let mut i: usize = 0;
 391         let ln = self.len();
 392         while i < ln / 2 {
 393             // Unsafe swap to avoid the bounds check in safe swap.
 394             unsafe {
 395                 let pa: *mut T = self.get_unchecked_mut(i);
 396                 let pb: *mut T = self.get_unchecked_mut(ln - i - 1);
 397                 ptr::swap(pa, pb);
 398             }
 399             i += 1;
 400         }
 401     }
 402
 403     #[inline]
 404     unsafe fn get_unchecked_mut(&mut self, index: usize) -> &mut T {
 405         transmute((self.repr().data as *mut T).offset(index as isize))
 406     }
 407
 408     #[inline]
 409     fn as_mut_ptr(&mut self) -> *mut T {
 410         self.repr().data as *mut T
 411     }
 412
 413     #[inline]
 414     fn position_elem(&self, x: &T) -> Option<usize> where T: PartialEq {
 415         self.iter().position(|y| *x == *y)
 416     }
 417
 418     #[inline]
 419     fn rposition_elem(&self, t: &T) -> Option<usize> where T: PartialEq {
 420         self.iter().rposition(|x| *x == *t)
 421     }
 422
 423     #[inline]
 424     fn contains(&self, x: &T) -> bool where T: PartialEq {
 425         self.iter().any(|elt| *x == *elt)
 426     }
 427
 428     #[inline]
 429     fn starts_with(&self, needle: &[T]) -> bool where T: PartialEq {
 430         let n = needle.len();
 431         self.len() >= n && needle == &self[..n]
 432     }
 433
 434     #[inline]
 435     fn ends_with(&self, needle: &[T]) -> bool where T: PartialEq {
 436         let (m, n) = (self.len(), needle.len());
 437         m >= n && needle == &self[m-n..]
 438     }
 439
 440     fn binary_search(&self, x: &T) -> Result<usize, usize> where T: Ord {
 441         self.binary_search_by(|p| p.cmp(x))
 442     }
 443
 444     fn next_permutation(&mut self) -> bool where T: Ord {
 445         // These cases only have 1 permutation each, so we can't do anything.
 446         if self.len() < 2 { return false; }
 447
 448         // Step 1: Identify the longest, rightmost weakly decreasing part of the vector
 449         let mut i = self.len() - 1;
 450         while i > 0 && self[i-1] >= self[i] {
 451             i -= 1;
 452         }
 453
 454         // If that is the entire vector, this is the last-ordered permutation.
 455         if i == 0 {
 456             return false;
 457         }
 458
 459         // Step 2: Find the rightmost element larger than the pivot (i-1)
 460         let mut j = self.len() - 1;
 461         while j >= i && self[j] <= self[i-1]  {
 462             j -= 1;
 463         }
 464
 465         // Step 3: Swap that element with the pivot
 466         self.swap(j, i-1);
 467
 468         // Step 4: Reverse the (previously) weakly decreasing part
 469         self[i..].reverse();
 470
 471         true
 472     }
 473
 474     fn prev_permutation(&mut self) -> bool where T: Ord {
 475         // These cases only have 1 permutation each, so we can't do anything.
 476         if self.len() < 2 { return false; }
 477
 478         // Step 1: Identify the longest, rightmost weakly increasing part of the vector
 479         let mut i = self.len() - 1;
 480         while i > 0 && self[i-1] <= self[i] {
 481             i -= 1;
 482         }
 483
 484         // If that is the entire vector, this is the first-ordered permutation.
 485         if i == 0 {
 486             return false;
 487         }
 488
 489         // Step 2: Reverse the weakly increasing part
 490         self[i..].reverse();
 491
 492         // Step 3: Find the rightmost element equal to or bigger than the pivot (i-1)
 493         let mut j = self.len() - 1;
 494         while j >= i && self[j-1] < self[i-1]  {
 495             j -= 1;
 496         }
 497
 498         // Step 4: Swap that element with the pivot
 499         self.swap(i-1, j);
 500
 501         true
 502     }
 503
 504     #[inline]
 505     fn clone_from_slice(&mut self, src: &[T]) -> usize where T: Clone {
 506         let min = cmp::min(self.len(), src.len());
 507         let dst = &mut self[.. min];
 508         let src = &src[.. min];
 509         for i in 0..min {
 510             dst[i].clone_from(&src[i]);
 511         }
 512         min
 513     }
 514 }
 515
 516 #[stable(feature = "rust1", since = "1.0.0")]
 517 impl<T> ops::Index<usize> for [T] {
 518     type Output = T;
 519
 520     fn index(&self, index: usize) -> &T {
 521         assert!(index < self.len());
 522
 523         unsafe { mem::transmute(self.repr().data.offset(index as isize)) }
 524     }
 525 }
 526
 527 #[stable(feature = "rust1", since = "1.0.0")]
 528 impl<T> ops::IndexMut<usize> for [T] {
 529     #[inline]
 530     fn index_mut(&mut self, index: usize) -> &mut T {
 531         assert!(index < self.len());
 532
 533         unsafe { mem::transmute(self.repr().data.offset(index as isize)) }
 534     }
 535 }
 536
 537 #[stable(feature = "rust1", since = "1.0.0")]
 538 impl<T> ops::Index<ops::Range<usize>> for [T] {
 539     type Output = [T];
 540
 541     #[inline]
 542     fn index(&self, index: ops::Range<usize>) -> &[T] {
 543         assert!(index.start <= index.end);
 544         assert!(index.end <= self.len());
 545         unsafe {
 546             from_raw_parts (
 547                 self.as_ptr().offset(index.start as isize),
 548                 index.end - index.start
 549             )
 550         }
 551     }
 552 }
 553 #[stable(feature = "rust1", since = "1.0.0")]
 554 impl<T> ops::Index<ops::RangeTo<usize>> for [T] {
 555     type Output = [T];
 556
 557     #[inline]
 558     fn index(&self, index: ops::RangeTo<usize>) -> &[T] {
 559         self.index(ops::Range{ start: 0, end: index.end })
 560     }
 561 }
 562 #[stable(feature = "rust1", since = "1.0.0")]
 563 impl<T> ops::Index<ops::RangeFrom<usize>> for [T] {
 564     type Output = [T];
 565
 566     #[inline]
 567     fn index(&self, index: ops::RangeFrom<usize>) -> &[T] {
 568         self.index(ops::Range{ start: index.start, end: self.len() })
 569     }
 570 }
 571 #[stable(feature = "rust1", since = "1.0.0")]
 572 impl<T> ops::Index<RangeFull> for [T] {
 573     type Output = [T];
 574
 575     #[inline]
 576     fn index(&self, _index: RangeFull) -> &[T] {
 577         self
 578     }
 579 }
 580
 581 #[stable(feature = "rust1", since = "1.0.0")]
 582 impl<T> ops::IndexMut<ops::Range<usize>> for [T] {
 583     #[inline]
 584     fn index_mut(&mut self, index: ops::Range<usize>) -> &mut [T] {
 585         assert!(index.start <= index.end);
 586         assert!(index.end <= self.len());
 587         unsafe {
 588             from_raw_parts_mut(
 589                 self.as_mut_ptr().offset(index.start as isize),
 590                 index.end - index.start
 591             )
 592         }
 593     }
 594 }
 595 #[stable(feature = "rust1", since = "1.0.0")]
 596 impl<T> ops::IndexMut<ops::RangeTo<usize>> for [T] {
 597     #[inline]
 598     fn index_mut(&mut self, index: ops::RangeTo<usize>) -> &mut [T] {
 599         self.index_mut(ops::Range{ start: 0, end: index.end })
 600     }
 601 }
 602 #[stable(feature = "rust1", since = "1.0.0")]
 603 impl<T> ops::IndexMut<ops::RangeFrom<usize>> for [T] {
 604     #[inline]
 605     fn index_mut(&mut self, index: ops::RangeFrom<usize>) -> &mut [T] {
 606         let len = self.len();
 607         self.index_mut(ops::Range{ start: index.start, end: len })
 608     }
 609 }
 610 #[stable(feature = "rust1", since = "1.0.0")]
 611 impl<T> ops::IndexMut<RangeFull> for [T] {
 612     #[inline]
 613     fn index_mut(&mut self, _index: RangeFull) -> &mut [T] {
 614         self
 615     }
 616 }
 617
 618
 619 ////////////////////////////////////////////////////////////////////////////////
 620 // Common traits
 621 ////////////////////////////////////////////////////////////////////////////////
 622
 623 #[stable(feature = "rust1", since = "1.0.0")]
 624 impl<'a, T> Default for &'a [T] {
 625     #[stable(feature = "rust1", since = "1.0.0")]
 626     fn default() -> &'a [T] { &[] }
 627 }
 628
 629 //
 630 // Iterators
 631 //
 632
 633 #[stable(feature = "rust1", since = "1.0.0")]
 634 impl<'a, T> IntoIterator for &'a [T] {
 635     type Item = &'a T;
 636     type IntoIter = Iter<'a, T>;
 637
 638     fn into_iter(self) -> Iter<'a, T> {
 639         self.iter()
 640     }
 641 }
 642
 643 #[stable(feature = "rust1", since = "1.0.0")]
 644 impl<'a, T> IntoIterator for &'a mut [T] {
 645     type Item = &'a mut T;
 646     type IntoIter = IterMut<'a, T>;
 647
 648     fn into_iter(self) -> IterMut<'a, T> {
 649         self.iter_mut()
 650     }
 651 }
 652
 653 #[inline(always)]
 654 fn size_from_ptr<T>(_: *const T) -> usize {
 655     mem::size_of::<T>()
 656 }
 657
 658 // The shared definition of the `Iter` and `IterMut` iterators
 659 macro_rules! iterator {
 660     (struct $name:ident -> $ptr:ty, $elem:ty) => {
 661         #[stable(feature = "rust1", since = "1.0.0")]
 662         impl<'a, T> Iterator for $name<'a, T> {
 663             type Item = $elem;
 664
 665             #[inline]
 666             fn next(&mut self) -> Option<$elem> {
 667                 // could be implemented with slices, but this avoids bounds checks
 668                 unsafe {
 669                     if mem::size_of::<T>() != 0 {
 670                         assume(!self.ptr.is_null());
 671                         assume(!self.end.is_null());
 672                     }
 673                     if self.ptr == self.end {
 674                         None
 675                     } else {
 676                         let old = self.ptr;
 677                         self.ptr = slice_offset!(self.ptr, 1);
 678                         Some(slice_ref!(old))
 679                     }
 680                 }
 681             }
 682
 683             #[inline]
 684             fn size_hint(&self) -> (usize, Option<usize>) {
 685                 let diff = (self.end as usize).wrapping_sub(self.ptr as usize);
 686                 let size = mem::size_of::<T>();
 687                 let exact = diff / (if size == 0 {1} else {size});
 688                 (exact, Some(exact))
 689             }
 690
 691             #[inline]
 692             fn count(self) -> usize {
 693                 self.size_hint().0
 694             }
 695
 696             #[inline]
 697             fn nth(&mut self, n: usize) -> Option<$elem> {
 698                 // Call helper method. Can't put the definition here because mut versus const.
 699                 self.iter_nth(n)
 700             }
 701
 702             #[inline]
 703             fn last(mut self) -> Option<$elem> {
 704                 self.next_back()
 705             }
 706         }
 707
 708         #[stable(feature = "rust1", since = "1.0.0")]
 709         impl<'a, T> DoubleEndedIterator for $name<'a, T> {
 710             #[inline]
 711             fn next_back(&mut self) -> Option<$elem> {
 712                 // could be implemented with slices, but this avoids bounds checks
 713                 unsafe {
 714                     if mem::size_of::<T>() != 0 {
 715                         assume(!self.ptr.is_null());
 716                         assume(!self.end.is_null());
 717                     }
 718                     if self.end == self.ptr {
 719                         None
 720                     } else {
 721                         self.end = slice_offset!(self.end, -1);
 722                         Some(slice_ref!(self.end))
 723                     }
 724                 }
 725             }
 726         }
 727     }
 728 }
 729
 730 macro_rules! make_slice {
 731     ($start: expr, $end: expr) => {{
 732         let start = $start;
 733         let diff = ($end as usize).wrapping_sub(start as usize);
 734         if size_from_ptr(start) == 0 {
 735             // use a non-null pointer value
 736             unsafe { from_raw_parts(1 as *const _, diff) }
 737         } else {
 738             let len = diff / size_from_ptr(start);
 739             unsafe { from_raw_parts(start, len) }
 740         }
 741     }}
 742 }
 743
 744 macro_rules! make_mut_slice {
 745     ($start: expr, $end: expr) => {{
 746         let start = $start;
 747         let diff = ($end as usize).wrapping_sub(start as usize);
 748         if size_from_ptr(start) == 0 {
 749             // use a non-null pointer value
 750             unsafe { from_raw_parts_mut(1 as *mut _, diff) }
 751         } else {
 752             let len = diff / size_from_ptr(start);
 753             unsafe { from_raw_parts_mut(start, len) }
 754         }
 755     }}
 756 }
 757
 758 /// Immutable slice iterator
 759 #[stable(feature = "rust1", since = "1.0.0")]
 760 pub struct Iter<'a, T: 'a> {
 761     ptr: *const T,
 762     end: *const T,
 763     _marker: marker::PhantomData<&'a T>,
 764 }
 765
 766 unsafe impl<'a, T: Sync> Sync for Iter<'a, T> {}
 767 unsafe impl<'a, T: Sync> Send for Iter<'a, T> {}
 768
 769 impl<'a, T> Iter<'a, T> {
 770     /// View the underlying data as a subslice of the original data.
 771     ///
 772     /// This has the same lifetime as the original slice, and so the
 773     /// iterator can continue to be used while this exists.
 774     #[unstable(feature = "iter_to_slice")]
 775     pub fn as_slice(&self) -> &'a [T] {
 776         make_slice!(self.ptr, self.end)
 777     }
 778
 779     // Helper function for Iter::nth
 780     fn iter_nth(&mut self, n: usize) -> Option<&'a T> {
 781         match self.as_slice().get(n) {
 782             Some(elem_ref) => unsafe {
 783                 self.ptr = slice_offset!(self.ptr, (n as isize).wrapping_add(1));
 784                 Some(elem_ref)
 785             },
 786             None => {
 787                 self.ptr = self.end;
 788                 None
 789             }
 790         }
 791     }
 792 }
 793
 794 iterator!{struct Iter -> *const T, &'a T}
 795
 796 #[stable(feature = "rust1", since = "1.0.0")]
 797 impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
 798
 799 #[stable(feature = "rust1", since = "1.0.0")]
 800 impl<'a, T> Clone for Iter<'a, T> {
 801     fn clone(&self) -> Iter<'a, T> { Iter { ptr: self.ptr, end: self.end, _marker: self._marker } }
 802 }
 803
 804 #[unstable(feature = "iter_idx", reason = "trait is experimental")]
 805 impl<'a, T> RandomAccessIterator for Iter<'a, T> {
 806     #[inline]
 807     fn indexable(&self) -> usize {
 808         let (exact, _) = self.size_hint();
 809         exact
 810     }
 811
 812     #[inline]
 813     fn idx(&mut self, index: usize) -> Option<&'a T> {
 814         unsafe {
 815             if index < self.indexable() {
 816                 Some(slice_ref!(self.ptr.offset(index as isize)))
 817             } else {
 818                 None
 819             }
 820         }
 821     }
 822 }
 823
 824 /// Mutable slice iterator.
 825 #[stable(feature = "rust1", since = "1.0.0")]
 826 pub struct IterMut<'a, T: 'a> {
 827     ptr: *mut T,
 828     end: *mut T,
 829     _marker: marker::PhantomData<&'a mut T>,
 830 }
 831
 832 unsafe impl<'a, T: Sync> Sync for IterMut<'a, T> {}
 833 unsafe impl<'a, T: Send> Send for IterMut<'a, T> {}
 834
 835 impl<'a, T> IterMut<'a, T> {
 836     /// View the underlying data as a subslice of the original data.
 837     ///
 838     /// To avoid creating `&mut` references that alias, this is forced
 839     /// to consume the iterator. Consider using the `Slice` and
 840     /// `SliceMut` implementations for obtaining slices with more
 841     /// restricted lifetimes that do not consume the iterator.
 842     #[unstable(feature = "iter_to_slice")]
 843     pub fn into_slice(self) -> &'a mut [T] {
 844         make_mut_slice!(self.ptr, self.end)
 845     }
 846
 847     // Helper function for IterMut::nth
 848     fn iter_nth(&mut self, n: usize) -> Option<&'a mut T> {
 849         match make_mut_slice!(self.ptr, self.end).get_mut(n) {
 850             Some(elem_ref) => unsafe {
 851                 self.ptr = slice_offset!(self.ptr, (n as isize).wrapping_add(1));
 852                 Some(elem_ref)
 853             },
 854             None => {
 855                 self.ptr = self.end;
 856                 None
 857             }
 858         }
 859     }
 860 }
 861
 862 iterator!{struct IterMut -> *mut T, &'a mut T}
 863
 864 #[stable(feature = "rust1", since = "1.0.0")]
 865 impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
 866
 867 /// An internal abstraction over the splitting iterators, so that
 868 /// splitn, splitn_mut etc can be implemented once.
 869 trait SplitIter: DoubleEndedIterator {
 870     /// Mark the underlying iterator as complete, extracting the remaining
 871     /// portion of the slice.
 872     fn finish(&mut self) -> Option<Self::Item>;
 873 }
 874
 875 /// An iterator over subslices separated by elements that match a predicate
 876 /// function.
 877 #[stable(feature = "rust1", since = "1.0.0")]
 878 pub struct Split<'a, T:'a, P> where P: FnMut(&T) -> bool {
 879     v: &'a [T],
 880     pred: P,
 881     finished: bool
 882 }
 883
 884 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
 885 #[stable(feature = "rust1", since = "1.0.0")]
 886 impl<'a, T, P> Clone for Split<'a, T, P> where P: Clone + FnMut(&T) -> bool {
 887     fn clone(&self) -> Split<'a, T, P> {
 888         Split {
 889             v: self.v,
 890             pred: self.pred.clone(),
 891             finished: self.finished,
 892         }
 893     }
 894 }
 895
 896 #[stable(feature = "rust1", since = "1.0.0")]
 897 impl<'a, T, P> Iterator for Split<'a, T, P> where P: FnMut(&T) -> bool {
 898     type Item = &'a [T];
 899
 900     #[inline]
 901     fn next(&mut self) -> Option<&'a [T]> {
 902         if self.finished { return None; }
 903
 904         match self.v.iter().position(|x| (self.pred)(x)) {
 905             None => self.finish(),
 906             Some(idx) => {
 907                 let ret = Some(&self.v[..idx]);
 908                 self.v = &self.v[idx + 1..];
 909                 ret
 910             }
 911         }
 912     }
 913
 914     #[inline]
 915     fn size_hint(&self) -> (usize, Option<usize>) {
 916         if self.finished {
 917             (0, Some(0))
 918         } else {
 919             (1, Some(self.v.len() + 1))
 920         }
 921     }
 922 }
 923
 924 #[stable(feature = "rust1", since = "1.0.0")]
 925 impl<'a, T, P> DoubleEndedIterator for Split<'a, T, P> where P: FnMut(&T) -> bool {
 926     #[inline]
 927     fn next_back(&mut self) -> Option<&'a [T]> {
 928         if self.finished { return None; }
 929
 930         match self.v.iter().rposition(|x| (self.pred)(x)) {
 931             None => self.finish(),
 932             Some(idx) => {
 933                 let ret = Some(&self.v[idx + 1..]);
 934                 self.v = &self.v[..idx];
 935                 ret
 936             }
 937         }
 938     }
 939 }
 940
 941 impl<'a, T, P> SplitIter for Split<'a, T, P> where P: FnMut(&T) -> bool {
 942     #[inline]
 943     fn finish(&mut self) -> Option<&'a [T]> {
 944         if self.finished { None } else { self.finished = true; Some(self.v) }
 945     }
 946 }
 947
 948 /// An iterator over the subslices of the vector which are separated
 949 /// by elements that match `pred`.
 950 #[stable(feature = "rust1", since = "1.0.0")]
 951 pub struct SplitMut<'a, T:'a, P> where P: FnMut(&T) -> bool {
 952     v: &'a mut [T],
 953     pred: P,
 954     finished: bool
 955 }
 956
 957 impl<'a, T, P> SplitIter for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
 958     #[inline]
 959     fn finish(&mut self) -> Option<&'a mut [T]> {
 960         if self.finished {
 961             None
 962         } else {
 963             self.finished = true;
 964             Some(mem::replace(&mut self.v, &mut []))
 965         }
 966     }
 967 }
 968
 969 #[stable(feature = "rust1", since = "1.0.0")]
 970 impl<'a, T, P> Iterator for SplitMut<'a, T, P> where P: FnMut(&T) -> bool {
 971     type Item = &'a mut [T];
 972
 973     #[inline]
 974     fn next(&mut self) -> Option<&'a mut [T]> {
 975         if self.finished { return None; }
 976
 977         let idx_opt = { // work around borrowck limitations
 978             let pred = &mut self.pred;
 979             self.v.iter().position(|x| (*pred)(x))
 980         };
 981         match idx_opt {
 982             None => self.finish(),
 983             Some(idx) => {
 984                 let tmp = mem::replace(&mut self.v, &mut []);
 985                 let (head, tail) = tmp.split_at_mut(idx);
 986                 self.v = &mut tail[1..];
 987                 Some(head)
 988             }
 989         }
 990     }
 991
 992     #[inline]
 993     fn size_hint(&self) -> (usize, Option<usize>) {
 994         if self.finished {
 995             (0, Some(0))
 996         } else {
 997             // if the predicate doesn't match anything, we yield one slice
 998             // if it matches every element, we yield len+1 empty slices.
 999             (1, Some(self.v.len() + 1))
1000         }
1001     }
1002 }
1003
1004 #[stable(feature = "rust1", since = "1.0.0")]
1005 impl<'a, T, P> DoubleEndedIterator for SplitMut<'a, T, P> where
1006     P: FnMut(&T) -> bool,
1007 {
1008     #[inline]
1009     fn next_back(&mut self) -> Option<&'a mut [T]> {
1010         if self.finished { return None; }
1011
1012         let idx_opt = { // work around borrowck limitations
1013             let pred = &mut self.pred;
1014             self.v.iter().rposition(|x| (*pred)(x))
1015         };
1016         match idx_opt {
1017             None => self.finish(),
1018             Some(idx) => {
1019                 let tmp = mem::replace(&mut self.v, &mut []);
1020                 let (head, tail) = tmp.split_at_mut(idx);
1021                 self.v = head;
1022                 Some(&mut tail[1..])
1023             }
1024         }
1025     }
1026 }
1027
1028 /// An private iterator over subslices separated by elements that
1029 /// match a predicate function, splitting at most a fixed number of
1030 /// times.
1031 struct GenericSplitN<I> {
1032     iter: I,
1033     count: usize,
1034     invert: bool
1035 }
1036
1037 impl<T, I: SplitIter<Item=T>> Iterator for GenericSplitN<I> {
1038     type Item = T;
1039
1040     #[inline]
1041     fn next(&mut self) -> Option<T> {
1042         match self.count {
1043             0 => None,
1044             1 => { self.count -= 1; self.iter.finish() }
1045             _ => {
1046                 self.count -= 1;
1047                 if self.invert {self.iter.next_back()} else {self.iter.next()}
1048             }
1049         }
1050     }
1051
1052     #[inline]
1053     fn size_hint(&self) -> (usize, Option<usize>) {
1054         let (lower, upper_opt) = self.iter.size_hint();
1055         (lower, upper_opt.map(|upper| cmp::min(self.count, upper)))
1056     }
1057 }
1058
1059 /// An iterator over subslices separated by elements that match a predicate
1060 /// function, limited to a given number of splits.
1061 #[stable(feature = "rust1", since = "1.0.0")]
1062 pub struct SplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool {
1063     inner: GenericSplitN<Split<'a, T, P>>
1064 }
1065
1066 /// An iterator over subslices separated by elements that match a
1067 /// predicate function, limited to a given number of splits, starting
1068 /// from the end of the slice.
1069 #[stable(feature = "rust1", since = "1.0.0")]
1070 pub struct RSplitN<'a, T: 'a, P> where P: FnMut(&T) -> bool {
1071     inner: GenericSplitN<Split<'a, T, P>>
1072 }
1073
1074 /// An iterator over subslices separated by elements that match a predicate
1075 /// function, limited to a given number of splits.
1076 #[stable(feature = "rust1", since = "1.0.0")]
1077 pub struct SplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool {
1078     inner: GenericSplitN<SplitMut<'a, T, P>>
1079 }
1080
1081 /// An iterator over subslices separated by elements that match a
1082 /// predicate function, limited to a given number of splits, starting
1083 /// from the end of the slice.
1084 #[stable(feature = "rust1", since = "1.0.0")]
1085 pub struct RSplitNMut<'a, T: 'a, P> where P: FnMut(&T) -> bool {
1086     inner: GenericSplitN<SplitMut<'a, T, P>>
1087 }
1088
1089 macro_rules! forward_iterator {
1090     ($name:ident: $elem:ident, $iter_of:ty) => {
1091         #[stable(feature = "rust1", since = "1.0.0")]
1092         impl<'a, $elem, P> Iterator for $name<'a, $elem, P> where
1093             P: FnMut(&T) -> bool
1094         {
1095             type Item = $iter_of;
1096
1097             #[inline]
1098             fn next(&mut self) -> Option<$iter_of> {
1099                 self.inner.next()
1100             }
1101
1102             #[inline]
1103             fn size_hint(&self) -> (usize, Option<usize>) {
1104                 self.inner.size_hint()
1105             }
1106         }
1107     }
1108 }
1109
1110 forward_iterator! { SplitN: T, &'a [T] }
1111 forward_iterator! { RSplitN: T, &'a [T] }
1112 forward_iterator! { SplitNMut: T, &'a mut [T] }
1113 forward_iterator! { RSplitNMut: T, &'a mut [T] }
1114
1115 /// An iterator over overlapping subslices of length `size`.
1116 #[stable(feature = "rust1", since = "1.0.0")]
1117 pub struct Windows<'a, T:'a> {
1118     v: &'a [T],
1119     size: usize
1120 }
1121
1122 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1123 #[stable(feature = "rust1", since = "1.0.0")]
1124 impl<'a, T> Clone for Windows<'a, T> {
1125     fn clone(&self) -> Windows<'a, T> {
1126         Windows {
1127             v: self.v,
1128             size: self.size,
1129         }
1130     }
1131 }
1132
1133 #[stable(feature = "rust1", since = "1.0.0")]
1134 impl<'a, T> Iterator for Windows<'a, T> {
1135     type Item = &'a [T];
1136
1137     #[inline]
1138     fn next(&mut self) -> Option<&'a [T]> {
1139         if self.size > self.v.len() {
1140             None
1141         } else {
1142             let ret = Some(&self.v[..self.size]);
1143             self.v = &self.v[1..];
1144             ret
1145         }
1146     }
1147
1148     #[inline]
1149     fn size_hint(&self) -> (usize, Option<usize>) {
1150         if self.size > self.v.len() {
1151             (0, Some(0))
1152         } else {
1153             let size = self.v.len() - self.size + 1;
1154             (size, Some(size))
1155         }
1156     }
1157 }
1158
1159 #[stable(feature = "rust1", since = "1.0.0")]
1160 impl<'a, T> DoubleEndedIterator for Windows<'a, T> {
1161     #[inline]
1162     fn next_back(&mut self) -> Option<&'a [T]> {
1163         if self.size > self.v.len() {
1164             None
1165         } else {
1166             let ret = Some(&self.v[self.v.len()-self.size..]);
1167             self.v = &self.v[..self.v.len()-1];
1168             ret
1169         }
1170     }
1171 }
1172
1173 #[stable(feature = "rust1", since = "1.0.0")]
1174 impl<'a, T> ExactSizeIterator for Windows<'a, T> {}
1175
1176 #[unstable(feature = "iter_idx", reason = "trait is experimental")]
1177 impl<'a, T> RandomAccessIterator for Windows<'a, T> {
1178     #[inline]
1179     fn indexable(&self) -> usize {
1180         self.size_hint().0
1181     }
1182
1183     #[inline]
1184     fn idx(&mut self, index: usize) -> Option<&'a [T]> {
1185         if index + self.size > self.v.len() {
1186             None
1187         } else {
1188             Some(&self.v[index .. index+self.size])
1189         }
1190     }
1191 }
1192
1193 /// An iterator over a slice in (non-overlapping) chunks (`size` elements at a
1194 /// time).
1195 ///
1196 /// When the slice len is not evenly divided by the chunk size, the last slice
1197 /// of the iteration will be the remainder.
1198 #[stable(feature = "rust1", since = "1.0.0")]
1199 pub struct Chunks<'a, T:'a> {
1200     v: &'a [T],
1201     size: usize
1202 }
1203
1204 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1205 #[stable(feature = "rust1", since = "1.0.0")]
1206 impl<'a, T> Clone for Chunks<'a, T> {
1207     fn clone(&self) -> Chunks<'a, T> {
1208         Chunks {
1209             v: self.v,
1210             size: self.size,
1211         }
1212     }
1213 }
1214
1215 #[stable(feature = "rust1", since = "1.0.0")]
1216 impl<'a, T> Iterator for Chunks<'a, T> {
1217     type Item = &'a [T];
1218
1219     #[inline]
1220     fn next(&mut self) -> Option<&'a [T]> {
1221         if self.v.is_empty() {
1222             None
1223         } else {
1224             let chunksz = cmp::min(self.v.len(), self.size);
1225             let (fst, snd) = self.v.split_at(chunksz);
1226             self.v = snd;
1227             Some(fst)
1228         }
1229     }
1230
1231     #[inline]
1232     fn size_hint(&self) -> (usize, Option<usize>) {
1233         if self.v.is_empty() {
1234             (0, Some(0))
1235         } else {
1236             let n = self.v.len() / self.size;
1237             let rem = self.v.len() % self.size;
1238             let n = if rem > 0 { n+1 } else { n };
1239             (n, Some(n))
1240         }
1241     }
1242 }
1243
1244 #[stable(feature = "rust1", since = "1.0.0")]
1245 impl<'a, T> DoubleEndedIterator for Chunks<'a, T> {
1246     #[inline]
1247     fn next_back(&mut self) -> Option<&'a [T]> {
1248         if self.v.is_empty() {
1249             None
1250         } else {
1251             let remainder = self.v.len() % self.size;
1252             let chunksz = if remainder != 0 { remainder } else { self.size };
1253             let (fst, snd) = self.v.split_at(self.v.len() - chunksz);
1254             self.v = fst;
1255             Some(snd)
1256         }
1257     }
1258 }
1259
1260 #[stable(feature = "rust1", since = "1.0.0")]
1261 impl<'a, T> ExactSizeIterator for Chunks<'a, T> {}
1262
1263 #[unstable(feature = "iter_idx", reason = "trait is experimental")]
1264 impl<'a, T> RandomAccessIterator for Chunks<'a, T> {
1265     #[inline]
1266     fn indexable(&self) -> usize {
1267         self.v.len()/self.size + if self.v.len() % self.size != 0 { 1 } else { 0 }
1268     }
1269
1270     #[inline]
1271     fn idx(&mut self, index: usize) -> Option<&'a [T]> {
1272         if index < self.indexable() {
1273             let lo = index * self.size;
1274             let mut hi = lo + self.size;
1275             if hi < lo || hi > self.v.len() { hi = self.v.len(); }
1276
1277             Some(&self.v[lo..hi])
1278         } else {
1279             None
1280         }
1281     }
1282 }
1283
1284 /// An iterator over a slice in (non-overlapping) mutable chunks (`size`
1285 /// elements at a time). When the slice len is not evenly divided by the chunk
1286 /// size, the last slice of the iteration will be the remainder.
1287 #[stable(feature = "rust1", since = "1.0.0")]
1288 pub struct ChunksMut<'a, T:'a> {
1289     v: &'a mut [T],
1290     chunk_size: usize
1291 }
1292
1293 #[stable(feature = "rust1", since = "1.0.0")]
1294 impl<'a, T> Iterator for ChunksMut<'a, T> {
1295     type Item = &'a mut [T];
1296
1297     #[inline]
1298     fn next(&mut self) -> Option<&'a mut [T]> {
1299         if self.v.is_empty() {
1300             None
1301         } else {
1302             let sz = cmp::min(self.v.len(), self.chunk_size);
1303             let tmp = mem::replace(&mut self.v, &mut []);
1304             let (head, tail) = tmp.split_at_mut(sz);
1305             self.v = tail;
1306             Some(head)
1307         }
1308     }
1309
1310     #[inline]
1311     fn size_hint(&self) -> (usize, Option<usize>) {
1312         if self.v.is_empty() {
1313             (0, Some(0))
1314         } else {
1315             let n = self.v.len() / self.chunk_size;
1316             let rem = self.v.len() % self.chunk_size;
1317             let n = if rem > 0 { n + 1 } else { n };
1318             (n, Some(n))
1319         }
1320     }
1321 }
1322
1323 #[stable(feature = "rust1", since = "1.0.0")]
1324 impl<'a, T> DoubleEndedIterator for ChunksMut<'a, T> {
1325     #[inline]
1326     fn next_back(&mut self) -> Option<&'a mut [T]> {
1327         if self.v.is_empty() {
1328             None
1329         } else {
1330             let remainder = self.v.len() % self.chunk_size;
1331             let sz = if remainder != 0 { remainder } else { self.chunk_size };
1332             let tmp = mem::replace(&mut self.v, &mut []);
1333             let tmp_len = tmp.len();
1334             let (head, tail) = tmp.split_at_mut(tmp_len - sz);
1335             self.v = head;
1336             Some(tail)
1337         }
1338     }
1339 }
1340
1341 #[stable(feature = "rust1", since = "1.0.0")]
1342 impl<'a, T> ExactSizeIterator for ChunksMut<'a, T> {}
1343
1344 //
1345 // Free functions
1346 //
1347
1348 /// Converts a pointer to A into a slice of length 1 (without copying).
1349 #[unstable(feature = "ref_slice")]
1350 pub fn ref_slice<'a, A>(s: &'a A) -> &'a [A] {
1351     unsafe {
1352         from_raw_parts(s, 1)
1353     }
1354 }
1355
1356 /// Converts a pointer to A into a slice of length 1 (without copying).
1357 #[unstable(feature = "ref_slice")]
1358 pub fn mut_ref_slice<'a, A>(s: &'a mut A) -> &'a mut [A] {
1359     unsafe {
1360         from_raw_parts_mut(s, 1)
1361     }
1362 }
1363
1364 /// Forms a slice from a pointer and a length.
1365 ///
1366 /// The `len` argument is the number of **elements**, not the number of bytes.
1367 ///
1368 /// This function is unsafe as there is no guarantee that the given pointer is
1369 /// valid for `len` elements, nor whether the lifetime inferred is a suitable
1370 /// lifetime for the returned slice.
1371 ///
1372 /// # Caveat
1373 ///
1374 /// The lifetime for the returned slice is inferred from its usage. To
1375 /// prevent accidental misuse, it's suggested to tie the lifetime to whichever
1376 /// source lifetime is safe in the context, such as by providing a helper
1377 /// function taking the lifetime of a host value for the slice, or by explicit
1378 /// annotation.
1379 ///
1380 /// # Examples
1381 ///
1382 /// ```
1383 /// use std::slice;
1384 ///
1385 /// // manifest a slice out of thin air!
1386 /// let ptr = 0x1234 as *const usize;
1387 /// let amt = 10;
1388 /// unsafe {
1389 ///     let slice = slice::from_raw_parts(ptr, amt);
1390 /// }
1391 /// ```
1392 #[inline]
1393 #[stable(feature = "rust1", since = "1.0.0")]
1394 pub unsafe fn from_raw_parts<'a, T>(p: *const T, len: usize) -> &'a [T] {
1395     transmute(RawSlice { data: p, len: len })
1396 }
1397
1398 /// Performs the same functionality as `from_raw_parts`, except that a mutable
1399 /// slice is returned.
1400 ///
1401 /// This function is unsafe for the same reasons as `from_raw_parts`, as well
1402 /// as not being able to provide a non-aliasing guarantee of the returned
1403 /// mutable slice.
1404 #[inline]
1405 #[stable(feature = "rust1", since = "1.0.0")]
1406 pub unsafe fn from_raw_parts_mut<'a, T>(p: *mut T, len: usize) -> &'a mut [T] {
1407     transmute(RawSlice { data: p, len: len })
1408 }
1409
1410 //
1411 // Submodules
1412 //
1413
1414 /// Operations on `[u8]`.
1415 #[unstable(feature = "slice_bytes", reason = "needs review")]
1416 pub mod bytes {
1417     use ptr;
1418     use slice::SliceExt;
1419
1420     /// A trait for operations on mutable `[u8]`s.
1421     pub trait MutableByteVector {
1422         /// Sets all bytes of the receiver to the given value.
1423         fn set_memory(&mut self, value: u8);
1424     }
1425
1426     impl MutableByteVector for [u8] {
1427         #[inline]
1428         fn set_memory(&mut self, value: u8) {
1429             unsafe { ptr::write_bytes(self.as_mut_ptr(), value, self.len()) };
1430         }
1431     }
1432
1433     /// Copies data from `src` to `dst`
1434     ///
1435     /// Panics if the length of `dst` is less than the length of `src`.
1436     #[inline]
1437     pub fn copy_memory(src: &[u8], dst: &mut [u8]) {
1438         let len_src = src.len();
1439         assert!(dst.len() >= len_src);
1440         // `dst` is unaliasable, so we know statically it doesn't overlap
1441         // with `src`.
1442         unsafe {
1443             ptr::copy_nonoverlapping(src.as_ptr(),
1444                                      dst.as_mut_ptr(),
1445                                      len_src);
1446         }
1447     }
1448 }
1449
1450
1451
1452 //
1453 // Boilerplate traits
1454 //
1455
1456 #[stable(feature = "rust1", since = "1.0.0")]
1457 impl<A, B> PartialEq<[B]> for [A] where A: PartialEq<B> {
1458     fn eq(&self, other: &[B]) -> bool {
1459         self.len() == other.len() &&
1460             order::eq(self.iter(), other.iter())
1461     }
1462     fn ne(&self, other: &[B]) -> bool {
1463         self.len() != other.len() ||
1464             order::ne(self.iter(), other.iter())
1465     }
1466 }
1467
1468 #[stable(feature = "rust1", since = "1.0.0")]
1469 impl<T: Eq> Eq for [T] {}
1470
1471 #[stable(feature = "rust1", since = "1.0.0")]
1472 impl<T: Ord> Ord for [T] {
1473     fn cmp(&self, other: &[T]) -> Ordering {
1474         order::cmp(self.iter(), other.iter())
1475     }
1476 }
1477
1478 #[stable(feature = "rust1", since = "1.0.0")]
1479 impl<T: PartialOrd> PartialOrd for [T] {
1480     #[inline]
1481     fn partial_cmp(&self, other: &[T]) -> Option<Ordering> {
1482         order::partial_cmp(self.iter(), other.iter())
1483     }
1484     #[inline]
1485     fn lt(&self, other: &[T]) -> bool {
1486         order::lt(self.iter(), other.iter())
1487     }
1488     #[inline]
1489     fn le(&self, other: &[T]) -> bool {
1490         order::le(self.iter(), other.iter())
1491     }
1492     #[inline]
1493     fn ge(&self, other: &[T]) -> bool {
1494         order::ge(self.iter(), other.iter())
1495     }
1496     #[inline]
1497     fn gt(&self, other: &[T]) -> bool {
1498         order::gt(self.iter(), other.iter())
1499     }
1500 }
1501
1502 /// Extension methods for slices containing integers.
1503 #[unstable(feature = "int_slice")]
1504 pub trait IntSliceExt<U, S> {
1505     /// Converts the slice to an immutable slice of unsigned integers with the same width.
1506     fn as_unsigned<'a>(&'a self) -> &'a [U];
1507     /// Converts the slice to an immutable slice of signed integers with the same width.
1508     fn as_signed<'a>(&'a self) -> &'a [S];
1509
1510     /// Converts the slice to a mutable slice of unsigned integers with the same width.
1511     fn as_unsigned_mut<'a>(&'a mut self) -> &'a mut [U];
1512     /// Converts the slice to a mutable slice of signed integers with the same width.
1513     fn as_signed_mut<'a>(&'a mut self) -> &'a mut [S];
1514 }
1515
1516 macro_rules! impl_int_slice {
1517     ($u:ty, $s:ty, $t:ty) => {
1518         #[unstable(feature = "int_slice")]
1519         impl IntSliceExt<$u, $s> for [$t] {
1520             #[inline]
1521             fn as_unsigned(&self) -> &[$u] { unsafe { transmute(self) } }
1522             #[inline]
1523             fn as_signed(&self) -> &[$s] { unsafe { transmute(self) } }
1524             #[inline]
1525             fn as_unsigned_mut(&mut self) -> &mut [$u] { unsafe { transmute(self) } }
1526             #[inline]
1527             fn as_signed_mut(&mut self) -> &mut [$s] { unsafe { transmute(self) } }
1528         }
1529     }
1530 }
1531
1532 macro_rules! impl_int_slices {
1533     ($u:ty, $s:ty) => {
1534         impl_int_slice! { $u, $s, $u }
1535         impl_int_slice! { $u, $s, $s }
1536     }
1537 }
1538
1539 impl_int_slices! { u8,   i8  }
1540 impl_int_slices! { u16,  i16 }
1541 impl_int_slices! { u32,  i32 }
1542 impl_int_slices! { u64,  i64 }
1543 impl_int_slices! { usize, isize }