Change implementation of syntax::util::SmallVector to use data_structures::SmallVec.

1 files changed, 139 insertions, 10 deletions

diff --git a/src/librustc_data_structures/array_vec.rs b/src/librustc_data_structures/array_vec.rs
index f87426cee59..631cf2cfcf6 100644
--- a/src/librustc_data_structures/array_vec.rs
+++ b/src/librustc_data_structures/array_vec.rs
@@ -9,15 +9,15 @@
 // except according to those terms.
 
 //! A stack-allocated vector, allowing storage of N elements on the stack.
-//!
-//! Currently, only the N = 8 case is supported (due to Array only being impl-ed for [T; 8]).
 
 use std::marker::Unsize;
 use std::iter::Extend;
-use std::ptr::drop_in_place;
-use std::ops::{Deref, DerefMut};
+use std::ptr::{self, drop_in_place};
+use std::ops::{Deref, DerefMut, Range};
+use std::hash::{Hash, Hasher};
 use std::slice;
 use std::fmt;
+use std::mem;
 
 pub unsafe trait Array {
     type Element;
@@ -25,6 +25,12 @@ pub unsafe trait Array {
     const LEN: usize;
 }
 
+unsafe impl<T> Array for [T; 1] {
+    type Element = T;
+    type PartialStorage = [ManuallyDrop<T>; 1];
+    const LEN: usize = 1;
+}
+
 unsafe impl<T> Array for [T; 8] {
     type Element = T;
     type PartialStorage = [ManuallyDrop<T>; 8];
@@ -36,6 +42,32 @@ pub struct ArrayVec<A: Array> {
     values: A::PartialStorage
 }
 
+impl<A> Hash for ArrayVec<A>
+    where A: Array,
+          A::Element: Hash {
+    fn hash<H>(&self, state: &mut H) where H: Hasher {
+        (&self[..]).hash(state);
+    }
+}
+
+impl<A: Array> PartialEq for ArrayVec<A> {
+    fn eq(&self, other: &Self) -> bool {
+        self == other
+    }
+}
+
+impl<A: Array> Eq for ArrayVec<A> {}
+
+impl<A> Clone for ArrayVec<A>
+    where A: Array,
+          A::Element: Clone {
+    fn clone(&self) -> Self {
+        let mut v = ArrayVec::new();
+        v.extend(self.iter().cloned());
+        v
+    }
+}
+
 impl<A: Array> ArrayVec<A> {
     pub fn new() -> Self {
         ArrayVec {
@@ -43,6 +75,41 @@ impl<A: Array> ArrayVec<A> {
             values: Default::default(),
         }
     }
+
+    pub fn len(&self) -> usize {
+        self.count
+    }
+
+    pub unsafe fn set_len(&mut self, len: usize) {
+        self.count = len;
+    }
+
+    /// Panics when the stack vector is full.
+    pub fn push(&mut self, el: A::Element) {
+        let arr = &mut self.values as &mut [ManuallyDrop<_>];
+        arr[self.count] = ManuallyDrop { value: el };
+        self.count += 1;
+    }
+
+    pub fn pop(&mut self) -> Option<A::Element> {
+        if self.count > 0 {
+            let arr = &mut self.values as &mut [ManuallyDrop<_>];
+            self.count -= 1;
+            unsafe {
+                let value = ptr::read(&arr[self.count]);
+                Some(value.value)
+            }
+        } else {
+            None
+        }
+    }
+}
+
+impl<A> Default for ArrayVec<A>
+    where A: Array {
+    fn default() -> Self {
+        ArrayVec::new()
+    }
 }
 
 impl<A> fmt::Debug for ArrayVec<A>
@@ -81,15 +148,69 @@ impl<A: Array> Drop for ArrayVec<A> {
 impl<A: Array> Extend<A::Element> for ArrayVec<A> {
     fn extend<I>(&mut self, iter: I) where I: IntoIterator<Item=A::Element> {
         for el in iter {
-            unsafe {
-                let arr = &mut self.values as &mut [ManuallyDrop<_>];
-                arr[self.count].value = el;
-            }
-            self.count += 1;
+            self.push(el);
+        }
+    }
+}
+
+pub struct Iter<A: Array> {
+    indices: Range<usize>,
+    store: A::PartialStorage,
+}
+
+impl<A: Array> Drop for Iter<A> {
+    fn drop(&mut self) {
+        for _ in self {}
+    }
+}
+
+impl<A: Array> Iterator for Iter<A> {
+    type Item = A::Element;
+
+    fn next(&mut self) -> Option<A::Element> {
+        let arr = &self.store as &[ManuallyDrop<_>];
+        unsafe {
+            self.indices.next().map(|i| ptr::read(&arr[i]).value)
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.indices.size_hint()
+    }
+}
+
+impl<A: Array> IntoIterator for ArrayVec<A> {
+    type Item = A::Element;
+    type IntoIter = Iter<A>;
+    fn into_iter(self) -> Self::IntoIter {
+        let store = unsafe {
+            ptr::read(&self.values)
+        };
+        let indices = 0..self.count;
+        mem::forget(self);
+        Iter {
+            indices: indices,
+            store: store,
         }
     }
 }
 
+impl<'a, A: Array> IntoIterator for &'a ArrayVec<A> {
+    type Item = &'a A::Element;
+    type IntoIter = slice::Iter<'a, A::Element>;
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter()
+    }
+}
+
+impl<'a, A: Array> IntoIterator for &'a mut ArrayVec<A> {
+    type Item = &'a mut A::Element;
+    type IntoIter = slice::IterMut<'a, A::Element>;
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter_mut()
+    }
+}
+
 // FIXME: This should use repr(transparent) from rust-lang/rfcs#1758.
 #[allow(unions_with_drop_fields)]
 pub union ManuallyDrop<T> {
@@ -98,9 +219,17 @@ pub union ManuallyDrop<T> {
     empty: (),
 }
 
+impl<T> ManuallyDrop<T> {
+    fn new() -> ManuallyDrop<T> {
+        ManuallyDrop {
+            empty: ()
+        }
+    }
+}
+
 impl<T> Default for ManuallyDrop<T> {
     fn default() -> Self {
-        ManuallyDrop { empty: () }
+        ManuallyDrop::new()
     }
 }