Rollup merge of #47126 - sdroege:exact-chunks, r=bluss

Add slice::ExactChunks and ::ExactChunksMut iterators

These guarantee that always the requested slice size will be returned
and any leftoever elements at the end will be ignored. It allows llvm to
get rid of bounds checks in the code using the iterator.

This is inspired by the same iterators provided by ndarray.

Fixes https://github.com/rust-lang/rust/issues/47115

I'll add unit tests for all this if the general idea and behaviour makes sense for everybody.
Also see https://github.com/rust-lang/rust/issues/47115#issuecomment-354715511 for an example what this improves.

1 files changed, 225 insertions, 0 deletions

diff --git a/src/libcore/slice/mod.rs b/src/libcore/slice/mod.rs
index e6b79314aa9..48e82666d35 100644
--- a/src/libcore/slice/mod.rs
+++ b/src/libcore/slice/mod.rs
@@ -104,6 +104,9 @@ pub trait SliceExt {
     #[stable(feature = "core", since = "1.6.0")]
     fn chunks(&self, size: usize) -> Chunks<Self::Item>;
 
+    #[unstable(feature = "exact_chunks", issue = "47115")]
+    fn exact_chunks(&self, size: usize) -> ExactChunks<Self::Item>;
+
     #[stable(feature = "core", since = "1.6.0")]
     fn get<I>(&self, index: I) -> Option<&I::Output>
         where I: SliceIndex<Self>;
@@ -181,6 +184,9 @@ pub trait SliceExt {
     #[stable(feature = "core", since = "1.6.0")]
     fn chunks_mut(&mut self, chunk_size: usize) -> ChunksMut<Self::Item>;
 
+    #[unstable(feature = "exact_chunks", issue = "47115")]
+    fn exact_chunks_mut(&mut self, size: usize) -> ExactChunksMut<Self::Item>;
+
     #[stable(feature = "core", since = "1.6.0")]
     fn swap(&mut self, a: usize, b: usize);
 
@@ -357,6 +363,14 @@ impl<T> SliceExt for [T] {
     }
 
     #[inline]
+    fn exact_chunks(&self, chunk_size: usize) -> ExactChunks<T> {
+        assert!(chunk_size != 0);
+        let rem = self.len() % chunk_size;
+        let len = self.len() - rem;
+        ExactChunks { v: &self[..len], chunk_size: chunk_size}
+    }
+
+    #[inline]
     fn get<I>(&self, index: I) -> Option<&I::Output>
         where I: SliceIndex<[T]>
     {
@@ -540,6 +554,14 @@ impl<T> SliceExt for [T] {
     }
 
     #[inline]
+    fn exact_chunks_mut(&mut self, chunk_size: usize) -> ExactChunksMut<T> {
+        assert!(chunk_size != 0);
+        let rem = self.len() % chunk_size;
+        let len = self.len() - rem;
+        ExactChunksMut { v: &mut self[..len], chunk_size: chunk_size}
+    }
+
+    #[inline]
     fn swap(&mut self, a: usize, b: usize) {
         unsafe {
             // Can't take two mutable loans from one vector, so instead just cast
@@ -2378,6 +2400,209 @@ unsafe impl<'a, T> TrustedRandomAccess for ChunksMut<'a, T> {
     fn may_have_side_effect() -> bool { false }
 }
 
+/// An iterator over a slice in (non-overlapping) chunks (`chunk_size` elements at a
+/// time).
+///
+/// When the slice len is not evenly divided by the chunk size, the last
+/// up to `chunk_size-1` elements will be omitted.
+///
+/// This struct is created by the [`exact_chunks`] method on [slices].
+///
+/// [`exact_chunks`]: ../../std/primitive.slice.html#method.exact_chunks
+/// [slices]: ../../std/primitive.slice.html
+#[derive(Debug)]
+#[unstable(feature = "exact_chunks", issue = "47115")]
+pub struct ExactChunks<'a, T:'a> {
+    v: &'a [T],
+    chunk_size: usize
+}
+
+// FIXME(#26925) Remove in favor of `#[derive(Clone)]`
+#[unstable(feature = "exact_chunks", issue = "47115")]
+impl<'a, T> Clone for ExactChunks<'a, T> {
+    fn clone(&self) -> ExactChunks<'a, T> {
+        ExactChunks {
+            v: self.v,
+            chunk_size: self.chunk_size,
+        }
+    }
+}
+
+#[unstable(feature = "exact_chunks", issue = "47115")]
+impl<'a, T> Iterator for ExactChunks<'a, T> {
+    type Item = &'a [T];
+
+    #[inline]
+    fn next(&mut self) -> Option<&'a [T]> {
+        if self.v.len() < self.chunk_size {
+            None
+        } else {
+            let (fst, snd) = self.v.split_at(self.chunk_size);
+            self.v = snd;
+            Some(fst)
+        }
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let n = self.v.len() / self.chunk_size;
+        (n, Some(n))
+    }
+
+    #[inline]
+    fn count(self) -> usize {
+        self.len()
+    }
+
+    #[inline]
+    fn nth(&mut self, n: usize) -> Option<Self::Item> {
+        let (start, overflow) = n.overflowing_mul(self.chunk_size);
+        if start >= self.v.len() || overflow {
+            self.v = &[];
+            None
+        } else {
+            let (_, snd) = self.v.split_at(start);
+            self.v = snd;
+            self.next()
+        }
+    }
+
+    #[inline]
+    fn last(mut self) -> Option<Self::Item> {
+        self.next_back()
+    }
+}
+
+#[unstable(feature = "exact_chunks", issue = "47115")]
+impl<'a, T> DoubleEndedIterator for ExactChunks<'a, T> {
+    #[inline]
+    fn next_back(&mut self) -> Option<&'a [T]> {
+        if self.v.len() < self.chunk_size {
+            None
+        } else {
+            let (fst, snd) = self.v.split_at(self.v.len() - self.chunk_size);
+            self.v = fst;
+            Some(snd)
+        }
+    }
+}
+
+#[unstable(feature = "exact_chunks", issue = "47115")]
+impl<'a, T> ExactSizeIterator for ExactChunks<'a, T> {
+    fn is_empty(&self) -> bool {
+        self.v.is_empty()
+    }
+}
+
+#[unstable(feature = "fused", issue = "35602")]
+impl<'a, T> FusedIterator for ExactChunks<'a, T> {}
+
+#[doc(hidden)]
+unsafe impl<'a, T> TrustedRandomAccess for ExactChunks<'a, T> {
+    unsafe fn get_unchecked(&mut self, i: usize) -> &'a [T] {
+        let start = i * self.chunk_size;
+        from_raw_parts(self.v.as_ptr().offset(start as isize), self.chunk_size)
+    }
+    fn may_have_side_effect() -> bool { false }
+}
+
+/// An iterator over a slice in (non-overlapping) mutable chunks (`chunk_size`
+/// elements at a time). When the slice len is not evenly divided by the chunk
+/// size, the last up to `chunk_size-1` elements will be omitted.
+///
+/// This struct is created by the [`exact_chunks_mut`] method on [slices].
+///
+/// [`exact_chunks_mut`]: ../../std/primitive.slice.html#method.exact_chunks_mut
+/// [slices]: ../../std/primitive.slice.html
+#[derive(Debug)]
+#[unstable(feature = "exact_chunks", issue = "47115")]
+pub struct ExactChunksMut<'a, T:'a> {
+    v: &'a mut [T],
+    chunk_size: usize
+}
+
+#[unstable(feature = "exact_chunks", issue = "47115")]
+impl<'a, T> Iterator for ExactChunksMut<'a, T> {
+    type Item = &'a mut [T];
+
+    #[inline]
+    fn next(&mut self) -> Option<&'a mut [T]> {
+        if self.v.len() < self.chunk_size {
+            None
+        } else {
+            let tmp = mem::replace(&mut self.v, &mut []);
+            let (head, tail) = tmp.split_at_mut(self.chunk_size);
+            self.v = tail;
+            Some(head)
+        }
+    }
+
+    #[inline]
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let n = self.v.len() / self.chunk_size;
+        (n, Some(n))
+    }
+
+    #[inline]
+    fn count(self) -> usize {
+        self.len()
+    }
+
+    #[inline]
+    fn nth(&mut self, n: usize) -> Option<&'a mut [T]> {
+        let (start, overflow) = n.overflowing_mul(self.chunk_size);
+        if start >= self.v.len() || overflow {
+            self.v = &mut [];
+            None
+        } else {
+            let tmp = mem::replace(&mut self.v, &mut []);
+            let (_, snd) = tmp.split_at_mut(start);
+            self.v = snd;
+            self.next()
+        }
+    }
+
+    #[inline]
+    fn last(mut self) -> Option<Self::Item> {
+        self.next_back()
+    }
+}
+
+#[unstable(feature = "exact_chunks", issue = "47115")]
+impl<'a, T> DoubleEndedIterator for ExactChunksMut<'a, T> {
+    #[inline]
+    fn next_back(&mut self) -> Option<&'a mut [T]> {
+        if self.v.len() < self.chunk_size {
+            None
+        } else {
+            let tmp = mem::replace(&mut self.v, &mut []);
+            let tmp_len = tmp.len();
+            let (head, tail) = tmp.split_at_mut(tmp_len - self.chunk_size);
+            self.v = head;
+            Some(tail)
+        }
+    }
+}
+
+#[unstable(feature = "exact_chunks", issue = "47115")]
+impl<'a, T> ExactSizeIterator for ExactChunksMut<'a, T> {
+    fn is_empty(&self) -> bool {
+        self.v.is_empty()
+    }
+}
+
+#[unstable(feature = "fused", issue = "35602")]
+impl<'a, T> FusedIterator for ExactChunksMut<'a, T> {}
+
+#[doc(hidden)]
+unsafe impl<'a, T> TrustedRandomAccess for ExactChunksMut<'a, T> {
+    unsafe fn get_unchecked(&mut self, i: usize) -> &'a mut [T] {
+        let start = i * self.chunk_size;
+        from_raw_parts_mut(self.v.as_mut_ptr().offset(start as isize), self.chunk_size)
+    }
+    fn may_have_side_effect() -> bool { false }
+}
+
 //
 // Free functions
 //