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

8 files changed, 75 insertions, 268 deletions

diff --git a/src/libsyntax/Cargo.toml b/src/libsyntax/Cargo.toml
index 8b61e1b0d3a..0b38f5450b6 100644
--- a/src/libsyntax/Cargo.toml
+++ b/src/libsyntax/Cargo.toml
@@ -14,3 +14,4 @@ log = { path = "../liblog" }
 rustc_bitflags = { path = "../librustc_bitflags" }
 syntax_pos = { path = "../libsyntax_pos" }
 rustc_errors = { path = "../librustc_errors" }
+rustc_data_structures = { path = "../librustc_data_structures" }
diff --git a/src/libsyntax/config.rs b/src/libsyntax/config.rs
index 946257a16d5..02429f02738 100644
--- a/src/libsyntax/config.rs
+++ b/src/libsyntax/config.rs
@@ -277,7 +277,7 @@ impl<'a> fold::Folder for StripUnconfigured<'a> {
     fn fold_stmt(&mut self, stmt: ast::Stmt) -> SmallVector<ast::Stmt> {
         match self.configure_stmt(stmt) {
             Some(stmt) => fold::noop_fold_stmt(stmt, self),
-            None => return SmallVector::zero(),
+            None => return SmallVector::new(),
         }
     }
 
diff --git a/src/libsyntax/ext/base.rs b/src/libsyntax/ext/base.rs
index 63eee7df9e8..b4ac576f57a 100644
--- a/src/libsyntax/ext/base.rs
+++ b/src/libsyntax/ext/base.rs
@@ -440,7 +440,7 @@ impl MacResult for DummyResult {
         if self.expr_only {
             None
         } else {
-            Some(SmallVector::zero())
+            Some(SmallVector::new())
         }
     }
 
@@ -448,7 +448,7 @@ impl MacResult for DummyResult {
         if self.expr_only {
             None
         } else {
-            Some(SmallVector::zero())
+            Some(SmallVector::new())
         }
     }
 
@@ -456,7 +456,7 @@ impl MacResult for DummyResult {
         if self.expr_only {
             None
         } else {
-            Some(SmallVector::zero())
+            Some(SmallVector::new())
         }
     }
 
diff --git a/src/libsyntax/ext/expand.rs b/src/libsyntax/ext/expand.rs
index c3608aac0b4..877b312539f 100644
--- a/src/libsyntax/ext/expand.rs
+++ b/src/libsyntax/ext/expand.rs
@@ -89,7 +89,7 @@ macro_rules! expansions {
                     Expansion::OptExpr(Some(ref expr)) => visitor.visit_expr(expr),
                     Expansion::OptExpr(None) => {}
                     $($( Expansion::$kind(ref ast) => visitor.$visit(ast), )*)*
-                    $($( Expansion::$kind(ref ast) => for ast in ast.as_slice() {
+                    $($( Expansion::$kind(ref ast) => for ast in &ast[..] {
                         visitor.$visit_elt(ast);
                     }, )*)*
                 }
@@ -511,28 +511,28 @@ impl<'a> Parser<'a> {
                            -> PResult<'a, Expansion> {
         Ok(match kind {
             ExpansionKind::Items => {
-                let mut items = SmallVector::zero();
+                let mut items = SmallVector::new();
                 while let Some(item) = self.parse_item()? {
                     items.push(item);
                 }
                 Expansion::Items(items)
             }
             ExpansionKind::TraitItems => {
-                let mut items = SmallVector::zero();
+                let mut items = SmallVector::new();
                 while self.token != token::Eof {
                     items.push(self.parse_trait_item()?);
                 }
                 Expansion::TraitItems(items)
             }
             ExpansionKind::ImplItems => {
-                let mut items = SmallVector::zero();
+                let mut items = SmallVector::new();
                 while self.token != token::Eof {
                     items.push(self.parse_impl_item()?);
                 }
                 Expansion::ImplItems(items)
             }
             ExpansionKind::Stmts => {
-                let mut stmts = SmallVector::zero();
+                let mut stmts = SmallVector::new();
                 while self.token != token::Eof &&
                       // won't make progress on a `}`
                       self.token != token::CloseDelim(token::Brace) {
@@ -573,7 +573,7 @@ macro_rules! fully_configure {
     ($this:ident, $node:ident, $noop_fold:ident) => {
         match $noop_fold($node, &mut $this.cfg).pop() {
             Some(node) => node,
-            None => return SmallVector::zero(),
+            None => return SmallVector::new(),
         }
     }
 }
@@ -689,7 +689,7 @@ impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
     fn fold_stmt(&mut self, stmt: ast::Stmt) -> SmallVector<ast::Stmt> {
         let stmt = match self.cfg.configure_stmt(stmt) {
             Some(stmt) => stmt,
-            None => return SmallVector::zero(),
+            None => return SmallVector::new(),
         };
 
         let (mac, style, attrs) = if let StmtKind::Mac(mac) = stmt.node {
diff --git a/src/libsyntax/ext/source_util.rs b/src/libsyntax/ext/source_util.rs
index ec48cae3f76..bda84cdaf39 100644
--- a/src/libsyntax/ext/source_util.rs
+++ b/src/libsyntax/ext/source_util.rs
@@ -104,7 +104,7 @@ pub fn expand_include<'cx>(cx: &'cx mut ExtCtxt, sp: Span, tts: &[tokenstream::T
         }
         fn make_items(mut self: Box<ExpandResult<'a>>)
                       -> Option<SmallVector<P<ast::Item>>> {
-            let mut ret = SmallVector::zero();
+            let mut ret = SmallVector::new();
             while self.p.token != token::Eof {
                 match panictry!(self.p.parse_item()) {
                     Some(item) => ret.push(item),
diff --git a/src/libsyntax/lib.rs b/src/libsyntax/lib.rs
index feed400897c..34280812421 100644
--- a/src/libsyntax/lib.rs
+++ b/src/libsyntax/lib.rs
@@ -45,6 +45,7 @@ extern crate libc;
 extern crate rustc_unicode;
 pub extern crate rustc_errors as errors;
 extern crate syntax_pos;
+extern crate rustc_data_structures;
 
 extern crate serialize as rustc_serialize; // used by deriving
 
diff --git a/src/libsyntax/util/move_map.rs b/src/libsyntax/util/move_map.rs
index e1078b719bf..fe05e2958b3 100644
--- a/src/libsyntax/util/move_map.rs
+++ b/src/libsyntax/util/move_map.rs
@@ -10,6 +10,8 @@
 
 use std::ptr;
 
+use util::small_vector::SmallVector;
+
 pub trait MoveMap<T>: Sized {
     fn move_map<F>(self, mut f: F) -> Self where F: FnMut(T) -> T {
         self.move_flat_map(|e| Some(f(e)))
@@ -75,3 +77,50 @@ impl<T> MoveMap<T> for ::ptr::P<[T]> {
         ::ptr::P::from_vec(self.into_vec().move_flat_map(f))
     }
 }
+
+impl<T> MoveMap<T> for SmallVector<T> {
+    fn move_flat_map<F, I>(mut self, mut f: F) -> Self
+        where F: FnMut(T) -> I,
+              I: IntoIterator<Item=T>
+    {
+        let mut read_i = 0;
+        let mut write_i = 0;
+        unsafe {
+            let mut old_len = self.len();
+            self.set_len(0); // make sure we just leak elements in case of panic
+
+            while read_i < old_len {
+                // move the read_i'th item out of the vector and map it
+                // to an iterator
+                let e = ptr::read(self.get_unchecked(read_i));
+                let mut iter = f(e).into_iter();
+                read_i += 1;
+
+                while let Some(e) = iter.next() {
+                    if write_i < read_i {
+                        ptr::write(self.get_unchecked_mut(write_i), e);
+                        write_i += 1;
+                    } else {
+                        // If this is reached we ran out of space
+                        // in the middle of the vector.
+                        // However, the vector is in a valid state here,
+                        // so we just do a somewhat inefficient insert.
+                        self.set_len(old_len);
+                        self.insert(write_i, e);
+
+                        old_len = self.len();
+                        self.set_len(0);
+
+                        read_i += 1;
+                        write_i += 1;
+                    }
+                }
+            }
+
+            // write_i tracks the number of actually written new items.
+            self.set_len(write_i);
+        }
+
+        self
+    }
+}
diff --git a/src/libsyntax/util/small_vector.rs b/src/libsyntax/util/small_vector.rs
index 9be7dbd6817..31e675836fc 100644
--- a/src/libsyntax/util/small_vector.rs
+++ b/src/libsyntax/util/small_vector.rs
@@ -8,253 +8,9 @@
 // option. This file may not be copied, modified, or distributed
 // except according to those terms.
 
-use self::SmallVectorRepr::*;
-use self::IntoIterRepr::*;
+use rustc_data_structures::small_vec::SmallVec;
 
-use core::ops;
-use std::iter::{IntoIterator, FromIterator};
-use std::mem;
-use std::slice;
-use std::vec;
-
-use util::move_map::MoveMap;
-
-/// A vector type optimized for cases where the size is almost always 0 or 1
-#[derive(Clone)]
-pub struct SmallVector<T> {
-    repr: SmallVectorRepr<T>,
-}
-
-#[derive(Clone)]
-enum SmallVectorRepr<T> {
-    Zero,
-    One(T),
-    Many(Vec<T>),
-}
-
-impl<T> Default for SmallVector<T> {
-    fn default() -> Self {
-        SmallVector { repr: Zero }
-    }
-}
-
-impl<T> Into<Vec<T>> for SmallVector<T> {
-    fn into(self) -> Vec<T> {
-        match self.repr {
-            Zero => Vec::new(),
-            One(t) => vec![t],
-            Many(vec) => vec,
-        }
-    }
-}
-
-impl<T> FromIterator<T> for SmallVector<T> {
-    fn from_iter<I: IntoIterator<Item=T>>(iter: I) -> SmallVector<T> {
-        let mut v = SmallVector::zero();
-        v.extend(iter);
-        v
-    }
-}
-
-impl<T> Extend<T> for SmallVector<T> {
-    fn extend<I: IntoIterator<Item=T>>(&mut self, iter: I) {
-        for val in iter {
-            self.push(val);
-        }
-    }
-}
-
-impl<T> SmallVector<T> {
-    pub fn zero() -> SmallVector<T> {
-        SmallVector { repr: Zero }
-    }
-
-    pub fn one(v: T) -> SmallVector<T> {
-        SmallVector { repr: One(v) }
-    }
-
-    pub fn many(vs: Vec<T>) -> SmallVector<T> {
-        SmallVector { repr: Many(vs) }
-    }
-
-    pub fn as_slice(&self) -> &[T] {
-        self
-    }
-
-    pub fn as_mut_slice(&mut self) -> &mut [T] {
-        self
-    }
-
-    pub fn pop(&mut self) -> Option<T> {
-        match self.repr {
-            Zero => None,
-            One(..) => {
-                let one = mem::replace(&mut self.repr, Zero);
-                match one {
-                    One(v1) => Some(v1),
-                    _ => unreachable!()
-                }
-            }
-            Many(ref mut vs) => vs.pop(),
-        }
-    }
-
-    pub fn push(&mut self, v: T) {
-        match self.repr {
-            Zero => self.repr = One(v),
-            One(..) => {
-                let one = mem::replace(&mut self.repr, Zero);
-                match one {
-                    One(v1) => mem::replace(&mut self.repr, Many(vec![v1, v])),
-                    _ => unreachable!()
-                };
-            }
-            Many(ref mut vs) => vs.push(v)
-        }
-    }
-
-    pub fn push_all(&mut self, other: SmallVector<T>) {
-        for v in other.into_iter() {
-            self.push(v);
-        }
-    }
-
-    pub fn get(&self, idx: usize) -> &T {
-        match self.repr {
-            One(ref v) if idx == 0 => v,
-            Many(ref vs) => &vs[idx],
-            _ => panic!("out of bounds access")
-        }
-    }
-
-    pub fn expect_one(self, err: &'static str) -> T {
-        match self.repr {
-            One(v) => v,
-            Many(v) => {
-                if v.len() == 1 {
-                    v.into_iter().next().unwrap()
-                } else {
-                    panic!(err)
-                }
-            }
-            _ => panic!(err)
-        }
-    }
-
-    pub fn len(&self) -> usize {
-        match self.repr {
-            Zero => 0,
-            One(..) => 1,
-            Many(ref vals) => vals.len()
-        }
-    }
-
-    pub fn is_empty(&self) -> bool { self.len() == 0 }
-
-    pub fn map<U, F: FnMut(T) -> U>(self, mut f: F) -> SmallVector<U> {
-        let repr = match self.repr {
-            Zero => Zero,
-            One(t) => One(f(t)),
-            Many(vec) => Many(vec.into_iter().map(f).collect()),
-        };
-        SmallVector { repr: repr }
-    }
-}
-
-impl<T> ops::Deref for SmallVector<T> {
-    type Target = [T];
-
-    fn deref(&self) -> &[T] {
-        match self.repr {
-            Zero => {
-                let result: &[T] = &[];
-                result
-            }
-            One(ref v) => {
-                unsafe { slice::from_raw_parts(v, 1) }
-            }
-            Many(ref vs) => vs
-        }
-    }
-}
-
-impl<T> ops::DerefMut for SmallVector<T> {
-    fn deref_mut(&mut self) -> &mut [T] {
-        match self.repr {
-            Zero => {
-                let result: &mut [T] = &mut [];
-                result
-            }
-            One(ref mut v) => {
-                unsafe { slice::from_raw_parts_mut(v, 1) }
-            }
-            Many(ref mut vs) => vs
-        }
-    }
-}
-
-impl<T> IntoIterator for SmallVector<T> {
-    type Item = T;
-    type IntoIter = IntoIter<T>;
-    fn into_iter(self) -> Self::IntoIter {
-        let repr = match self.repr {
-            Zero => ZeroIterator,
-            One(v) => OneIterator(v),
-            Many(vs) => ManyIterator(vs.into_iter())
-        };
-        IntoIter { repr: repr }
-    }
-}
-
-pub struct IntoIter<T> {
-    repr: IntoIterRepr<T>,
-}
-
-enum IntoIterRepr<T> {
-    ZeroIterator,
-    OneIterator(T),
-    ManyIterator(vec::IntoIter<T>),
-}
-
-impl<T> Iterator for IntoIter<T> {
-    type Item = T;
-
-    fn next(&mut self) -> Option<T> {
-        match self.repr {
-            ZeroIterator => None,
-            OneIterator(..) => {
-                let mut replacement = ZeroIterator;
-                mem::swap(&mut self.repr, &mut replacement);
-                match replacement {
-                    OneIterator(v) => Some(v),
-                    _ => unreachable!()
-                }
-            }
-            ManyIterator(ref mut inner) => inner.next()
-        }
-    }
-
-    fn size_hint(&self) -> (usize, Option<usize>) {
-        match self.repr {
-            ZeroIterator => (0, Some(0)),
-            OneIterator(..) => (1, Some(1)),
-            ManyIterator(ref inner) => inner.size_hint()
-        }
-    }
-}
-
-impl<T> MoveMap<T> for SmallVector<T> {
-    fn move_flat_map<F, I>(self, mut f: F) -> Self
-        where F: FnMut(T) -> I,
-              I: IntoIterator<Item=T>
-    {
-        match self.repr {
-            Zero => Self::zero(),
-            One(v) => f(v).into_iter().collect(),
-            Many(vs) => SmallVector { repr: Many(vs.move_flat_map(f)) },
-        }
-    }
-}
+pub type SmallVector<T> = SmallVec<[T; 1]>;
 
 #[cfg(test)]
 mod tests {
@@ -262,7 +18,7 @@ mod tests {
 
     #[test]
     fn test_len() {
-        let v: SmallVector<isize> = SmallVector::zero();
+        let v: SmallVector<isize> = SmallVector::new();
         assert_eq!(0, v.len());
 
         assert_eq!(1, SmallVector::one(1).len());
@@ -271,30 +27,30 @@ mod tests {
 
     #[test]
     fn test_push_get() {
-        let mut v = SmallVector::zero();
+        let mut v = SmallVector::new();
         v.push(1);
         assert_eq!(1, v.len());
-        assert_eq!(&1, v.get(0));
+        assert_eq!(1, v[0]);
         v.push(2);
         assert_eq!(2, v.len());
-        assert_eq!(&2, v.get(1));
+        assert_eq!(2, v[1]);
         v.push(3);
         assert_eq!(3, v.len());
-        assert_eq!(&3, v.get(2));
+        assert_eq!(3, v[2]);
     }
 
     #[test]
     fn test_from_iter() {
         let v: SmallVector<isize> = (vec![1, 2, 3]).into_iter().collect();
         assert_eq!(3, v.len());
-        assert_eq!(&1, v.get(0));
-        assert_eq!(&2, v.get(1));
-        assert_eq!(&3, v.get(2));
+        assert_eq!(1, v[0]);
+        assert_eq!(2, v[1]);
+        assert_eq!(3, v[2]);
     }
 
     #[test]
     fn test_move_iter() {
-        let v = SmallVector::zero();
+        let v = SmallVector::new();
         let v: Vec<isize> = v.into_iter().collect();
         assert_eq!(v, Vec::new());
 
@@ -308,7 +64,7 @@ mod tests {
     #[test]
     #[should_panic]
     fn test_expect_one_zero() {
-        let _: isize = SmallVector::zero().expect_one("");
+        let _: isize = SmallVector::new().expect_one("");
     }
 
     #[test]