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

4 files changed, 495 insertions, 16 deletions

diff --git a/src/librustc_data_structures/accumulate_vec.rs b/src/librustc_data_structures/accumulate_vec.rs
index 3894db40277..937cb3f6007 100644
--- a/src/librustc_data_structures/accumulate_vec.rs
+++ b/src/librustc_data_structures/accumulate_vec.rs
@@ -11,22 +11,68 @@
 //! A vector type intended to be used for collecting from iterators onto the stack.
 //!
 //! Space for up to N elements is provided on the stack.  If more elements are collected, Vec is
-//! used to store the values on the heap. This type does not support re-allocating onto the heap,
-//! and there is no way to push more elements onto the existing storage.
+//! used to store the values on the heap.
 //!
 //! The N above is determined by Array's implementor, by way of an associatated constant.
 
-use std::ops::Deref;
-use std::iter::{IntoIterator, FromIterator};
+use std::ops::{Deref, DerefMut};
+use std::iter::{self, IntoIterator, FromIterator};
+use std::slice;
+use std::vec;
 
-use array_vec::{Array, ArrayVec};
+use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
 
-#[derive(Debug)]
+use array_vec::{self, Array, ArrayVec};
+
+#[derive(PartialEq, Eq, Hash, Debug)]
 pub enum AccumulateVec<A: Array> {
     Array(ArrayVec<A>),
     Heap(Vec<A::Element>)
 }
 
+impl<A> Clone for AccumulateVec<A>
+    where A: Array,
+          A::Element: Clone {
+    fn clone(&self) -> Self {
+        match *self {
+            AccumulateVec::Array(ref arr) => AccumulateVec::Array(arr.clone()),
+            AccumulateVec::Heap(ref vec) => AccumulateVec::Heap(vec.clone()),
+        }
+    }
+}
+
+impl<A: Array> AccumulateVec<A> {
+    pub fn new() -> AccumulateVec<A> {
+        AccumulateVec::Array(ArrayVec::new())
+    }
+
+    pub fn one(el: A::Element) -> Self {
+        iter::once(el).collect()
+    }
+
+    pub fn many<I: IntoIterator<Item=A::Element>>(iter: I) -> Self {
+        iter.into_iter().collect()
+    }
+
+    pub fn len(&self) -> usize {
+        match *self {
+            AccumulateVec::Array(ref arr) => arr.len(),
+            AccumulateVec::Heap(ref vec) => vec.len(),
+        }
+    }
+
+    pub fn is_empty(&self) -> bool {
+        self.len() == 0
+    }
+
+    pub fn pop(&mut self) -> Option<A::Element> {
+        match *self {
+            AccumulateVec::Array(ref mut arr) => arr.pop(),
+            AccumulateVec::Heap(ref mut vec) => vec.pop(),
+        }
+    }
+}
+
 impl<A: Array> Deref for AccumulateVec<A> {
     type Target = [A::Element];
     fn deref(&self) -> &Self::Target {
@@ -37,6 +83,15 @@ impl<A: Array> Deref for AccumulateVec<A> {
     }
 }
 
+impl<A: Array> DerefMut for AccumulateVec<A> {
+    fn deref_mut(&mut self) -> &mut [A::Element] {
+        match *self {
+            AccumulateVec::Array(ref mut v) => &mut v[..],
+            AccumulateVec::Heap(ref mut v) => &mut v[..],
+        }
+    }
+}
+
 impl<A: Array> FromIterator<A::Element> for AccumulateVec<A> {
     fn from_iter<I>(iter: I) -> AccumulateVec<A> where I: IntoIterator<Item=A::Element> {
         let iter = iter.into_iter();
@@ -50,3 +105,94 @@ impl<A: Array> FromIterator<A::Element> for AccumulateVec<A> {
     }
 }
 
+pub struct IntoIter<A: Array> {
+    repr: IntoIterRepr<A>,
+}
+
+enum IntoIterRepr<A: Array> {
+    Array(array_vec::Iter<A>),
+    Heap(vec::IntoIter<A::Element>),
+}
+
+impl<A: Array> Iterator for IntoIter<A> {
+    type Item = A::Element;
+
+    fn next(&mut self) -> Option<A::Element> {
+        match self.repr {
+            IntoIterRepr::Array(ref mut arr) => arr.next(),
+            IntoIterRepr::Heap(ref mut iter) => iter.next(),
+        }
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        match self.repr {
+            IntoIterRepr::Array(ref iter) => iter.size_hint(),
+            IntoIterRepr::Heap(ref iter) => iter.size_hint(),
+        }
+    }
+}
+
+impl<A: Array> IntoIterator for AccumulateVec<A> {
+    type Item = A::Element;
+    type IntoIter = IntoIter<A>;
+    fn into_iter(self) -> Self::IntoIter {
+        IntoIter {
+            repr: match self {
+                AccumulateVec::Array(arr) => IntoIterRepr::Array(arr.into_iter()),
+                AccumulateVec::Heap(vec) => IntoIterRepr::Heap(vec.into_iter()),
+            }
+        }
+    }
+}
+
+impl<'a, A: Array> IntoIterator for &'a AccumulateVec<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 AccumulateVec<A> {
+    type Item = &'a mut A::Element;
+    type IntoIter = slice::IterMut<'a, A::Element>;
+    fn into_iter(self) -> Self::IntoIter {
+        self.iter_mut()
+    }
+}
+
+impl<A: Array> From<Vec<A::Element>> for AccumulateVec<A> {
+    fn from(v: Vec<A::Element>) -> AccumulateVec<A> {
+        AccumulateVec::many(v)
+    }
+}
+
+impl<A: Array> Default for AccumulateVec<A> {
+    fn default() -> AccumulateVec<A> {
+        AccumulateVec::new()
+    }
+}
+
+impl<A> Encodable for AccumulateVec<A>
+    where A: Array,
+          A::Element: Encodable {
+    fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
+        s.emit_seq(self.len(), |s| {
+            for (i, e) in self.iter().enumerate() {
+                try!(s.emit_seq_elt(i, |s| e.encode(s)));
+            }
+            Ok(())
+        })
+    }
+}
+
+impl<A> Decodable for AccumulateVec<A>
+    where A: Array,
+          A::Element: Decodable {
+    fn decode<D: Decoder>(d: &mut D) -> Result<AccumulateVec<A>, D::Error> {
+        d.read_seq(|d, len| {
+            Ok(try!((0..len).map(|i| d.read_seq_elt(i, |d| Decodable::decode(d))).collect()))
+        })
+    }
+}
+
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()
     }
 }
 
diff --git a/src/librustc_data_structures/lib.rs b/src/librustc_data_structures/lib.rs
index fdcbec6bac1..2e4206d2ee1 100644
--- a/src/librustc_data_structures/lib.rs
+++ b/src/librustc_data_structures/lib.rs
@@ -46,6 +46,7 @@ extern crate libc;
 
 pub mod array_vec;
 pub mod accumulate_vec;
+pub mod small_vec;
 pub mod bitslice;
 pub mod blake2b;
 pub mod bitvec;
diff --git a/src/librustc_data_structures/small_vec.rs b/src/librustc_data_structures/small_vec.rs
new file mode 100644
index 00000000000..565a3c443a3
--- /dev/null
+++ b/src/librustc_data_structures/small_vec.rs
@@ -0,0 +1,203 @@
+// Copyright 2016 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.
+
+//! A vector type intended to be used for collecting from iterators onto the stack.
+//!
+//! Space for up to N elements is provided on the stack.  If more elements are collected, Vec is
+//! used to store the values on the heap. SmallVec is similar to AccumulateVec, but adds
+//! the ability to push elements.
+//!
+//! The N above is determined by Array's implementor, by way of an associatated constant.
+
+use std::ops::{Deref, DerefMut};
+use std::iter::{IntoIterator, FromIterator};
+use std::fmt::{self, Debug};
+use std::mem;
+use std::ptr;
+
+use rustc_serialize::{Encodable, Encoder, Decodable, Decoder};
+
+use accumulate_vec::{IntoIter, AccumulateVec};
+use array_vec::Array;
+
+pub struct SmallVec<A: Array>(AccumulateVec<A>);
+
+impl<A> Clone for SmallVec<A>
+    where A: Array,
+          A::Element: Clone {
+    fn clone(&self) -> Self {
+        SmallVec(self.0.clone())
+    }
+}
+
+impl<A> Debug for SmallVec<A>
+    where A: Array + Debug,
+          A::Element: Debug {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        f.debug_tuple("SmallVec").field(&self.0).finish()
+    }
+}
+
+impl<A: Array> SmallVec<A> {
+    pub fn new() -> Self {
+        SmallVec(AccumulateVec::new())
+    }
+
+    pub fn with_capacity(cap: usize) -> Self {
+        let mut vec = SmallVec::new();
+        vec.reserve(cap);
+        vec
+    }
+
+    pub fn one(el: A::Element) -> Self {
+        SmallVec(AccumulateVec::one(el))
+    }
+
+    pub fn many<I: IntoIterator<Item=A::Element>>(els: I) -> Self {
+        SmallVec(AccumulateVec::many(els))
+    }
+
+    pub fn expect_one(self, err: &'static str) -> A::Element {
+        assert!(self.len() == 1, err);
+        match self.0 {
+            AccumulateVec::Array(arr) => arr.into_iter().next().unwrap(),
+            AccumulateVec::Heap(vec) => vec.into_iter().next().unwrap(),
+        }
+    }
+
+    /// Will reallocate onto the heap if needed.
+    pub fn push(&mut self, el: A::Element) {
+        self.reserve(1);
+        match self.0 {
+            AccumulateVec::Array(ref mut array) => array.push(el),
+            AccumulateVec::Heap(ref mut vec) => vec.push(el),
+        }
+    }
+
+    pub fn reserve(&mut self, n: usize) {
+        match self.0 {
+            AccumulateVec::Array(_) => {
+                if self.len() + n > A::LEN {
+                    let len = self.len();
+                    let array = mem::replace(&mut self.0,
+                            AccumulateVec::Heap(Vec::with_capacity(len + n)));
+                    if let AccumulateVec::Array(array) = array {
+                        match self.0 {
+                            AccumulateVec::Heap(ref mut vec) => vec.extend(array),
+                            _ => unreachable!()
+                        }
+                    }
+                }
+            }
+            AccumulateVec::Heap(ref mut vec) => vec.reserve(n)
+        }
+    }
+
+    pub unsafe fn set_len(&mut self, len: usize) {
+        match self.0 {
+            AccumulateVec::Array(ref mut arr) => arr.set_len(len),
+            AccumulateVec::Heap(ref mut vec) => vec.set_len(len),
+        }
+    }
+
+    pub fn insert(&mut self, index: usize, element: A::Element) {
+        let len = self.len();
+
+        // Reserve space for shifting elements to the right
+        self.reserve(1);
+
+        assert!(index <= len);
+
+        unsafe {
+            // infallible
+            // The spot to put the new value
+            {
+                let p = self.as_mut_ptr().offset(index as isize);
+                // Shift everything over to make space. (Duplicating the
+                // `index`th element into two consecutive places.)
+                ptr::copy(p, p.offset(1), len - index);
+                // Write it in, overwriting the first copy of the `index`th
+                // element.
+                ptr::write(p, element);
+            }
+            self.set_len(len + 1);
+        }
+    }
+}
+
+impl<A: Array> Deref for SmallVec<A> {
+    type Target = AccumulateVec<A>;
+    fn deref(&self) -> &Self::Target {
+        &self.0
+    }
+}
+
+impl<A: Array> DerefMut for SmallVec<A> {
+    fn deref_mut(&mut self) -> &mut AccumulateVec<A> {
+        &mut self.0
+    }
+}
+
+impl<A: Array> FromIterator<A::Element> for SmallVec<A> {
+    fn from_iter<I>(iter: I) -> Self where I: IntoIterator<Item=A::Element> {
+        SmallVec(iter.into_iter().collect())
+    }
+}
+
+impl<A: Array> Extend<A::Element> for SmallVec<A> {
+    fn extend<I: IntoIterator<Item=A::Element>>(&mut self, iter: I) {
+        let iter = iter.into_iter();
+        self.reserve(iter.size_hint().0);
+        for el in iter {
+            self.push(el);
+        }
+    }
+}
+
+impl<A: Array> IntoIterator for SmallVec<A> {
+    type Item = A::Element;
+    type IntoIter = IntoIter<A>;
+    fn into_iter(self) -> Self::IntoIter {
+        self.0.into_iter()
+    }
+}
+
+impl<A: Array> Default for SmallVec<A> {
+    fn default() -> SmallVec<A> {
+        SmallVec::new()
+    }
+}
+
+impl<A> Encodable for SmallVec<A>
+    where A: Array,
+          A::Element: Encodable {
+    fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
+        s.emit_seq(self.len(), |s| {
+            for (i, e) in self.iter().enumerate() {
+                try!(s.emit_seq_elt(i, |s| e.encode(s)));
+            }
+            Ok(())
+        })
+    }
+}
+
+impl<A> Decodable for SmallVec<A>
+    where A: Array,
+          A::Element: Decodable {
+    fn decode<D: Decoder>(d: &mut D) -> Result<SmallVec<A>, D::Error> {
+        d.read_seq(|d, len| {
+            let mut vec = SmallVec::with_capacity(len);
+            for i in 0..len {
+                vec.push(try!(d.read_seq_elt(i, |d| Decodable::decode(d))));
+            }
+            Ok(vec)
+        })
+    }
+}