Auto merge of #25300 - kballard:core-slice-overflow, r=Gankro

core::slice was originally written to tolerate overflow (notably, with
slices of zero-sized elements), but it was never updated to use wrapping
arithmetic when overflow traps were added.

Also correctly handle the case of calling .nth() on an Iter with a
zero-sized element type. The iterator was assuming that the pointer
value of the returned reference was meaningful, but that's not true for
zero-sized elements.

Fixes #25016.

2 files changed, 105 insertions, 64 deletions

diff --git a/src/libcore/slice.rs b/src/libcore/slice.rs
index 56dee303487..9db1ceddf0d 100644
--- a/src/libcore/slice.rs
+++ b/src/libcore/slice.rs
@@ -140,7 +140,7 @@ impl<T> SliceExt for [T] {
             assume(!p.is_null());
             if mem::size_of::<T>() == 0 {
                 Iter {ptr: p,
-                      end: (p as usize + self.len()) as *const T,
+                      end: ((p as usize).wrapping_add(self.len())) as *const T,
                       _marker: marker::PhantomData}
             } else {
                 Iter {ptr: p,
@@ -277,7 +277,7 @@ impl<T> SliceExt for [T] {
             assume(!p.is_null());
             if mem::size_of::<T>() == 0 {
                 IterMut {ptr: p,
-                         end: (p as usize + self.len()) as *mut T,
+                         end: ((p as usize).wrapping_add(self.len())) as *mut T,
                          _marker: marker::PhantomData}
             } else {
                 IterMut {ptr: p,
@@ -632,35 +632,17 @@ fn size_from_ptr<T>(_: *const T) -> usize {
 
 
 // Use macros to be generic over const/mut
-//
-// They require non-negative `$by` because otherwise the expression
-// `(ptr as usize + $by)` would interpret `-1` as `usize::MAX` (and
-// thus trigger a panic when overflow checks are on).
-
-// Use this to do `$ptr + $by`, where `$by` is non-negative.
-macro_rules! slice_add_offset {
+macro_rules! slice_offset {
     ($ptr:expr, $by:expr) => {{
         let ptr = $ptr;
         if size_from_ptr(ptr) == 0 {
-            transmute(ptr as usize + $by)
+            transmute((ptr as isize).wrapping_add($by))
         } else {
             ptr.offset($by)
         }
     }};
 }
 
-// Use this to do `$ptr - $by`, where `$by` is non-negative.
-macro_rules! slice_sub_offset {
-    ($ptr:expr, $by:expr) => {{
-        let ptr = $ptr;
-        if size_from_ptr(ptr) == 0 {
-            transmute(ptr as usize - $by)
-        } else {
-            ptr.offset(-$by)
-        }
-    }};
-}
-
 macro_rules! slice_ref {
     ($ptr:expr) => {{
         let ptr = $ptr;
@@ -683,14 +665,16 @@ macro_rules! iterator {
             #[inline]
             fn next(&mut self) -> Option<$elem> {
                 // could be implemented with slices, but this avoids bounds checks
-                unsafe {
-                    ::intrinsics::assume(!self.ptr.is_null());
-                    ::intrinsics::assume(!self.end.is_null());
-                    if self.ptr == self.end {
-                        None
-                    } else {
+                if self.ptr == self.end {
+                    None
+                } else {
+                    unsafe {
+                        if mem::size_of::<T>() != 0 {
+                            ::intrinsics::assume(!self.ptr.is_null());
+                            ::intrinsics::assume(!self.end.is_null());
+                        }
                         let old = self.ptr;
-                        self.ptr = slice_add_offset!(self.ptr, 1);
+                        self.ptr = slice_offset!(self.ptr, 1);
                         Some(slice_ref!(old))
                     }
                 }
@@ -698,7 +682,7 @@ macro_rules! iterator {
 
             #[inline]
             fn size_hint(&self) -> (usize, Option<usize>) {
-                let diff = (self.end as usize) - (self.ptr as usize);
+                let diff = (self.end as usize).wrapping_sub(self.ptr as usize);
                 let size = mem::size_of::<T>();
                 let exact = diff / (if size == 0 {1} else {size});
                 (exact, Some(exact))
@@ -726,13 +710,15 @@ macro_rules! iterator {
             #[inline]
             fn next_back(&mut self) -> Option<$elem> {
                 // could be implemented with slices, but this avoids bounds checks
-                unsafe {
-                    ::intrinsics::assume(!self.ptr.is_null());
-                    ::intrinsics::assume(!self.end.is_null());
-                    if self.end == self.ptr {
-                        None
-                    } else {
-                        self.end = slice_sub_offset!(self.end, 1);
+                if self.end == self.ptr {
+                    None
+                } else {
+                    unsafe {
+                        self.end = slice_offset!(self.end, -1);
+                        if mem::size_of::<T>() != 0 {
+                            ::intrinsics::assume(!self.ptr.is_null());
+                            ::intrinsics::assume(!self.end.is_null());
+                        }
                         Some(slice_ref!(self.end))
                     }
                 }
@@ -742,29 +728,29 @@ macro_rules! iterator {
 }
 
 macro_rules! make_slice {
-    ($t: ty => $result: ty: $start: expr, $end: expr) => {{
-        let diff = $end as usize - $start as usize;
-        let len = if mem::size_of::<T>() == 0 {
-            diff
+    ($start: expr, $end: expr) => {{
+        let start = $start;
+        let diff = ($end as usize).wrapping_sub(start as usize);
+        if size_from_ptr(start) == 0 {
+            // use a non-null pointer value
+            unsafe { from_raw_parts(1 as *const _, diff) }
         } else {
-            diff / mem::size_of::<$t>()
-        };
-        unsafe {
-            from_raw_parts($start, len)
+            let len = diff / size_from_ptr(start);
+            unsafe { from_raw_parts(start, len) }
         }
     }}
 }
 
 macro_rules! make_mut_slice {
-    ($t: ty => $result: ty: $start: expr, $end: expr) => {{
-        let diff = $end as usize - $start as usize;
-        let len = if mem::size_of::<T>() == 0 {
-            diff
+    ($start: expr, $end: expr) => {{
+        let start = $start;
+        let diff = ($end as usize).wrapping_sub(start as usize);
+        if size_from_ptr(start) == 0 {
+            // use a non-null pointer value
+            unsafe { from_raw_parts_mut(1 as *mut _, diff) }
         } else {
-            diff / mem::size_of::<$t>()
-        };
-        unsafe {
-            from_raw_parts_mut($start, len)
+            let len = diff / size_from_ptr(start);
+            unsafe { from_raw_parts_mut(start, len) }
         }
     }}
 }
@@ -787,14 +773,14 @@ impl<'a, T> Iter<'a, T> {
     /// iterator can continue to be used while this exists.
     #[unstable(feature = "core")]
     pub fn as_slice(&self) -> &'a [T] {
-        make_slice!(T => &'a [T]: self.ptr, self.end)
+        make_slice!(self.ptr, self.end)
     }
 
     // Helper function for Iter::nth
     fn iter_nth(&mut self, n: usize) -> Option<&'a T> {
         match self.as_slice().get(n) {
             Some(elem_ref) => unsafe {
-                self.ptr = slice_add_offset!(elem_ref as *const _, 1);
+                self.ptr = slice_offset!(self.ptr, (n as isize).wrapping_add(1));
                 Some(slice_ref!(elem_ref))
             },
             None => {
@@ -827,12 +813,7 @@ impl<'a, T> RandomAccessIterator for Iter<'a, T> {
     fn idx(&mut self, index: usize) -> Option<&'a T> {
         unsafe {
             if index < self.indexable() {
-                if mem::size_of::<T>() == 0 {
-                    // Use a non-null pointer value
-                    Some(&mut *(1 as *mut _))
-                } else {
-                    Some(transmute(self.ptr.offset(index as isize)))
-                }
+                Some(slice_ref!(self.ptr.offset(index as isize)))
             } else {
                 None
             }
@@ -860,14 +841,14 @@ impl<'a, T> IterMut<'a, T> {
     /// restricted lifetimes that do not consume the iterator.
     #[unstable(feature = "core")]
     pub fn into_slice(self) -> &'a mut [T] {
-        make_mut_slice!(T => &'a mut [T]: self.ptr, self.end)
+        make_mut_slice!(self.ptr, self.end)
     }
 
     // Helper function for IterMut::nth
     fn iter_nth(&mut self, n: usize) -> Option<&'a mut T> {
-        match make_mut_slice!(T => &'a mut [T]: self.ptr, self.end).get_mut(n) {
+        match make_mut_slice!(self.ptr, self.end).get_mut(n) {
             Some(elem_ref) => unsafe {
-                self.ptr = slice_add_offset!(elem_ref as *mut _, 1);
+                self.ptr = slice_offset!(self.ptr, (n as isize).wrapping_add(1));
                 Some(slice_ref!(elem_ref))
             },
             None => {
diff --git a/src/test/run-pass/slice-of-zero-size-elements.rs b/src/test/run-pass/slice-of-zero-size-elements.rs
new file mode 100644
index 00000000000..6fe510586c7
--- /dev/null
+++ b/src/test/run-pass/slice-of-zero-size-elements.rs
@@ -0,0 +1,60 @@
+// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+// compile-flags: -C debug-assertions
+
+#![feature(core)]
+
+use std::slice;
+
+fn foo<T>(v: &[T]) -> Option<&[T]> {
+    let mut it = v.iter();
+    for _ in 0..5 {
+        let _ = it.next();
+    }
+    Some(it.as_slice())
+}
+
+fn foo_mut<T>(v: &mut [T]) -> Option<&mut [T]> {
+    let mut it = v.iter_mut();
+    for _ in 0..5 {
+        let _ = it.next();
+    }
+    Some(it.into_slice())
+}
+
+pub fn main() {
+    // In a slice of zero-size elements the pointer is meaningless.
+    // Ensure iteration still works even if the pointer is at the end of the address space.
+    let slice: &[()] = unsafe { slice::from_raw_parts(-5isize as *const (), 10) };
+    assert_eq!(slice.len(), 10);
+    assert_eq!(slice.iter().count(), 10);
+
+    // .nth() on the iterator should also behave correctly
+    let mut it = slice.iter();
+    assert!(it.nth(5).is_some());
+    assert_eq!(it.count(), 4);
+
+    // Converting Iter to a slice should never have a null pointer
+    assert!(foo(slice).is_some());
+
+    // Test mutable iterators as well
+    let slice: &mut [()] = unsafe { slice::from_raw_parts_mut(-5isize as *mut (), 10) };
+    assert_eq!(slice.len(), 10);
+    assert_eq!(slice.iter_mut().count(), 10);
+
+    {
+        let mut it = slice.iter_mut();
+        assert!(it.nth(5).is_some());
+        assert_eq!(it.count(), 4);
+    }
+
+    assert!(foo_mut(slice).is_some())
+}