Auto merge of #22715 - edwardw:send-sync-audit, r=alexcrichton

In the process, also replaces two raw mutable pointers with `Unique` to
spell out the ownership semantics.

cc #22709

7 files changed, 131 insertions, 30 deletions

diff --git a/src/libcollections/btree/node.rs b/src/libcollections/btree/node.rs
index b8703f6e7d9..4a80d75575e 100644
--- a/src/libcollections/btree/node.rs
+++ b/src/libcollections/btree/node.rs
@@ -1085,7 +1085,7 @@ impl<K, V> Node<K, V> {
                     vals: RawItems::from_slice(self.vals()),
                     edges: RawItems::from_slice(self.edges()),
 
-                    ptr: *self.keys as *mut u8,
+                    ptr: Unique::new(*self.keys as *mut u8),
                     capacity: self.capacity(),
                     is_leaf: self.is_leaf()
                 },
@@ -1354,11 +1354,14 @@ struct MoveTraversalImpl<K, V> {
     edges: RawItems<Node<K, V>>,
 
     // For deallocation when we are done iterating.
-    ptr: *mut u8,
+    ptr: Unique<u8>,
     capacity: usize,
     is_leaf: bool
 }
 
+unsafe impl<K: Sync, V: Sync> Sync for MoveTraversalImpl<K, V> {}
+unsafe impl<K: Send, V: Send> Send for MoveTraversalImpl<K, V> {}
+
 impl<K, V> TraversalImpl for MoveTraversalImpl<K, V> {
     type Item = (K, V);
     type Edge = Node<K, V>;
@@ -1401,7 +1404,7 @@ impl<K, V> Drop for MoveTraversalImpl<K, V> {
 
         let (alignment, size) =
                 calculate_allocation_generic::<K, V>(self.capacity, self.is_leaf);
-        unsafe { heap::deallocate(self.ptr, size, alignment) };
+        unsafe { heap::deallocate(*self.ptr, size, alignment) };
     }
 }
 
@@ -1425,12 +1428,12 @@ pub enum TraversalItem<K, V, E> {
 /// A traversal over a node's entries and edges
 pub type Traversal<'a, K, V> = AbsTraversal<ElemsAndEdges<Zip<slice::Iter<'a, K>,
                                                               slice::Iter<'a, V>>,
-                                                              slice::Iter<'a, Node<K, V>>>>;
+                                                          slice::Iter<'a, Node<K, V>>>>;
 
 /// A mutable traversal over a node's entries and edges
 pub type MutTraversal<'a, K, V> = AbsTraversal<ElemsAndEdges<Zip<slice::Iter<'a, K>,
                                                                  slice::IterMut<'a, V>>,
-                                                                 slice::IterMut<'a, Node<K, V>>>>;
+                                                             slice::IterMut<'a, Node<K, V>>>>;
 
 /// An owning traversal over a node's entries and edges
 pub type MoveTraversal<K, V> = AbsTraversal<MoveTraversalImpl<K, V>>;
diff --git a/src/libcollections/linked_list.rs b/src/libcollections/linked_list.rs
index 3d68bb13db8..9b5fbfc2511 100644
--- a/src/libcollections/linked_list.rs
+++ b/src/libcollections/linked_list.rs
@@ -51,8 +51,8 @@ struct Rawlink<T> {
 }
 
 impl<T> Copy for Rawlink<T> {}
-unsafe impl<T:'static+Send> Send for Rawlink<T> {}
-unsafe impl<T:Send+Sync> Sync for Rawlink<T> {}
+unsafe impl<T:Send> Send for Rawlink<T> {}
+unsafe impl<T:Sync> Sync for Rawlink<T> {}
 
 struct Node<T> {
     next: Link<T>,
diff --git a/src/libcollections/vec.rs b/src/libcollections/vec.rs
index 6d4541b5bde..e18fa8c3082 100644
--- a/src/libcollections/vec.rs
+++ b/src/libcollections/vec.rs
@@ -1755,6 +1755,9 @@ pub struct Drain<'a, T:'a> {
     marker: PhantomData<&'a T>,
 }
 
+unsafe impl<'a, T: Sync> Sync for Drain<'a, T> {}
+unsafe impl<'a, T: Send> Send for Drain<'a, T> {}
+
 #[stable(feature = "rust1", since = "1.0.0")]
 impl<'a, T> Iterator for Drain<'a, T> {
     type Item = T;
diff --git a/src/libcollections/vec_deque.rs b/src/libcollections/vec_deque.rs
index e99d44551d5..abcc0cef9f1 100644
--- a/src/libcollections/vec_deque.rs
+++ b/src/libcollections/vec_deque.rs
@@ -24,7 +24,6 @@ use core::cmp::Ordering;
 use core::default::Default;
 use core::fmt;
 use core::iter::{self, repeat, FromIterator, IntoIterator, RandomAccessIterator};
-use core::marker;
 use core::mem;
 use core::num::{Int, UnsignedInt};
 use core::ops::{Index, IndexMut};
@@ -60,12 +59,6 @@ pub struct VecDeque<T> {
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
-unsafe impl<T: Send> Send for VecDeque<T> {}
-
-#[stable(feature = "rust1", since = "1.0.0")]
-unsafe impl<T: Sync> Sync for VecDeque<T> {}
-
-#[stable(feature = "rust1", since = "1.0.0")]
 impl<T: Clone> Clone for VecDeque<T> {
     fn clone(&self) -> VecDeque<T> {
         self.iter().cloned().collect()
@@ -545,9 +538,7 @@ impl<T> VecDeque<T> {
         IterMut {
             tail: self.tail,
             head: self.head,
-            cap: self.cap,
-            ptr: *self.ptr,
-            marker: marker::PhantomData,
+            ring: unsafe { self.buffer_as_mut_slice() },
         }
     }
 
@@ -1515,17 +1506,12 @@ impl<'a, T> RandomAccessIterator for Iter<'a, T> {
     }
 }
 
-// FIXME This was implemented differently from Iter because of a problem
-//       with returning the mutable reference. I couldn't find a way to
-//       make the lifetime checker happy so, but there should be a way.
 /// `VecDeque` mutable iterator.
 #[stable(feature = "rust1", since = "1.0.0")]
 pub struct IterMut<'a, T:'a> {
-    ptr: *mut T,
+    ring: &'a mut [T],
     tail: usize,
     head: usize,
-    cap: usize,
-    marker: marker::PhantomData<&'a mut T>,
 }
 
 #[stable(feature = "rust1", since = "1.0.0")]
@@ -1538,16 +1524,17 @@ impl<'a, T> Iterator for IterMut<'a, T> {
             return None;
         }
         let tail = self.tail;
-        self.tail = wrap_index(self.tail + 1, self.cap);
+        self.tail = wrap_index(self.tail + 1, self.ring.len());
 
         unsafe {
-            Some(&mut *self.ptr.offset(tail as isize))
+            let elem = self.ring.get_unchecked_mut(tail);
+            Some(&mut *(elem as *mut _))
         }
     }
 
     #[inline]
     fn size_hint(&self) -> (usize, Option<usize>) {
-        let len = count(self.tail, self.head, self.cap);
+        let len = count(self.tail, self.head, self.ring.len());
         (len, Some(len))
     }
 }
@@ -1559,10 +1546,11 @@ impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
         if self.tail == self.head {
             return None;
         }
-        self.head = wrap_index(self.head - 1, self.cap);
+        self.head = wrap_index(self.head - 1, self.ring.len());
 
         unsafe {
-            Some(&mut *self.ptr.offset(self.head as isize))
+            let elem = self.ring.get_unchecked_mut(self.head);
+            Some(&mut *(elem as *mut _))
         }
     }
 }
diff --git a/src/libcore/iter.rs b/src/libcore/iter.rs
index b4ccf930437..8f767e62678 100644
--- a/src/libcore/iter.rs
+++ b/src/libcore/iter.rs
@@ -68,7 +68,7 @@ use num::{ToPrimitive, Int};
 use ops::{Add, Deref, FnMut};
 use option::Option;
 use option::Option::{Some, None};
-use marker::Sized;
+use marker::{Send, Sized, Sync};
 use usize;
 
 /// An interface for dealing with "external iterators". These types of iterators
@@ -1786,6 +1786,10 @@ pub struct Peekable<I: Iterator> {
     peeked: Option<I::Item>,
 }
 
+// FIXME: after #22828 being fixed, the following unsafe impl should be removed
+unsafe impl<I: Iterator> Sync for Peekable<I> where I: Sync, I::Item: Sync {}
+unsafe impl<I: Iterator> Send for Peekable<I> where I: Send, I::Item: Send {}
+
 impl<I: Iterator + Clone> Clone for Peekable<I> where I::Item: Clone {
     fn clone(&self) -> Peekable<I> {
         Peekable {
diff --git a/src/libcore/slice.rs b/src/libcore/slice.rs
index ae64a57a390..91cad4330f2 100644
--- a/src/libcore/slice.rs
+++ b/src/libcore/slice.rs
@@ -51,7 +51,7 @@ use ptr;
 use ptr::PtrExt;
 use mem;
 use mem::size_of;
-use marker::{Sized, self};
+use marker::{Send, Sized, Sync, self};
 use raw::Repr;
 // Avoid conflicts with *both* the Slice trait (buggy) and the `slice::raw` module.
 use raw::Slice as RawSlice;
@@ -740,6 +740,9 @@ pub struct Iter<'a, T: 'a> {
     _marker: marker::PhantomData<&'a T>,
 }
 
+unsafe impl<'a, T: Sync> Sync for Iter<'a, T> {}
+unsafe impl<'a, T: Sync> Send for Iter<'a, T> {}
+
 #[unstable(feature = "core")]
 impl<'a, T> ops::Index<ops::Range<usize>> for Iter<'a, T> {
     type Output = [T];
@@ -830,6 +833,8 @@ pub struct IterMut<'a, T: 'a> {
     _marker: marker::PhantomData<&'a mut T>,
 }
 
+unsafe impl<'a, T: Sync> Sync for IterMut<'a, T> {}
+unsafe impl<'a, T: Send> Send for IterMut<'a, T> {}
 
 #[unstable(feature = "core")]
 impl<'a, T> ops::Index<ops::Range<usize>> for IterMut<'a, T> {
diff --git a/src/test/run-pass/sync-send-iterators-in-libcollections.rs b/src/test/run-pass/sync-send-iterators-in-libcollections.rs
new file mode 100644
index 00000000000..6d29d5f2b3e
--- /dev/null
+++ b/src/test/run-pass/sync-send-iterators-in-libcollections.rs
@@ -0,0 +1,98 @@
+// 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.
+
+#![allow(unused_mut)]
+#![feature(collections)]
+
+extern crate collections;
+
+use collections::BinaryHeap;
+use collections::{BitSet, BitVec};
+use collections::{BTreeMap, BTreeSet};
+use collections::EnumSet;
+use collections::LinkedList;
+use collections::Vec;
+use collections::VecDeque;
+use collections::VecMap;
+
+use collections::Bound::Included;
+use collections::enum_set::CLike;
+use std::mem;
+
+fn is_sync<T>(_: T) where T: Sync {}
+fn is_send<T>(_: T) where T: Send {}
+
+macro_rules! all_sync_send {
+    ($ctor:expr, $($iter:ident),+) => ({
+        $(
+            let mut x = $ctor;
+            is_sync(x.$iter());
+            let mut y = $ctor;
+            is_send(y.$iter());
+        )+
+    })
+}
+
+macro_rules! is_sync_send {
+    ($ctor:expr, $iter:ident($($param:expr),+)) => ({
+        let mut x = $ctor;
+        is_sync(x.$iter($( $param ),+));
+        let mut y = $ctor;
+        is_send(y.$iter($( $param ),+));
+    })
+}
+
+fn main() {
+    // The iterator "generator" list should exhaust what corresponding
+    // implementations have where `Sync` and `Send` semantics apply.
+    all_sync_send!(BinaryHeap::<usize>::new(), iter, drain, into_iter);
+
+    all_sync_send!(BitVec::new(), iter);
+
+    all_sync_send!(BitSet::new(), iter);
+    is_sync_send!(BitSet::new(), union(&BitSet::new()));
+    is_sync_send!(BitSet::new(), intersection(&BitSet::new()));
+    is_sync_send!(BitSet::new(), difference(&BitSet::new()));
+    is_sync_send!(BitSet::new(), symmetric_difference(&BitSet::new()));
+
+    all_sync_send!(BTreeMap::<usize, usize>::new(), iter, iter_mut, into_iter, keys, values);
+    is_sync_send!(BTreeMap::<usize, usize>::new(), range(Included(&0), Included(&9)));
+    is_sync_send!(BTreeMap::<usize, usize>::new(), range_mut(Included(&0), Included(&9)));
+
+    all_sync_send!(BTreeSet::<usize>::new(), iter, into_iter);
+    is_sync_send!(BTreeSet::<usize>::new(), range(Included(&0), Included(&9)));
+    is_sync_send!(BTreeSet::<usize>::new(), difference(&BTreeSet::<usize>::new()));
+    is_sync_send!(BTreeSet::<usize>::new(), symmetric_difference(&BTreeSet::<usize>::new()));
+    is_sync_send!(BTreeSet::<usize>::new(), intersection(&BTreeSet::<usize>::new()));
+    is_sync_send!(BTreeSet::<usize>::new(), union(&BTreeSet::<usize>::new()));
+
+    all_sync_send!(LinkedList::<usize>::new(), iter, iter_mut, into_iter);
+
+    #[derive(Copy)]
+    #[repr(usize)]
+    #[allow(dead_code)]
+    enum Foo { A, B, C }
+    impl CLike for Foo {
+        fn to_usize(&self) -> usize {
+            *self as usize
+        }
+
+        fn from_usize(v: usize) -> Foo {
+            unsafe { mem::transmute(v) }
+        }
+    }
+    all_sync_send!(EnumSet::<Foo>::new(), iter);
+
+    all_sync_send!(VecDeque::<usize>::new(), iter, iter_mut, drain, into_iter);
+
+    all_sync_send!(VecMap::<usize>::new(), iter, iter_mut, drain, into_iter, keys, values);
+
+    all_sync_send!(Vec::<usize>::new(), into_iter, drain);
+}