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