Repository: gluon-lang/gluon
Pull request #129 (2016-08-24 19:50:51)

perf: Use SmallVec in the Type::App variant
Since applications are usually done on just a few argument it is usually unnecessary to allocate a `Vec`. Using `SmallVec` this heap allocation can be avoided for applications with only a few arguments which should cover most of the cases.
#50



Patch:
diff --git a/.travis.yml b/.travis.yml
index 22f2a219..711f16e8 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -12,13 +12,6 @@ rust:
 - stable
 os:
 - linux
-- osx
-matrix:
-  exclude:
-  - os: osx
-    rust: nightly
-  - os: osx
-    rust: beta
 before_script:
 - |
   pip install 'travis-cargo<0.2' --user &&
diff --git a/base/Cargo.toml b/base/Cargo.toml
index 5033f293..63a3dd7f 100644
--- a/base/Cargo.toml
+++ b/base/Cargo.toml
@@ -15,3 +15,5 @@ log = "0.3.6"
 quick-error = "1.0.0"
 fnv = "1.0.3"
 pretty = "0.1.0"
+smallvec = "0.2.1"
+collect-mac = "0.1.0"
diff --git a/base/src/instantiate.rs b/base/src/instantiate.rs
index cf3b79a6..2f0e69c6 100644
--- a/base/src/instantiate.rs
+++ b/base/src/instantiate.rs
@@ -2,7 +2,7 @@ use std::borrow::Cow;
 use std::collections::hash_map::Entry;
 
 use types;
-use types::{AliasData, Type, Generic, ArcType, TypeEnv};
+use types::{AliasData, AppVec, Type, Generic, ArcType, TypeEnv};
 use symbol::Symbol;
 use fnv::FnvMap;
 
@@ -134,7 +134,7 @@ pub fn type_of_alias(alias: &AliasData<Symbol, ArcType>, args: &[ArcType]) -> Op
                 .count();
             if alias_args.len() - args.len() <= allowed_missing_args {
                 // Remove the args at the end of the aliased type
-                let arg_types: Vec<_> = arg_types.iter()
+                let arg_types: AppVec<_> = arg_types.iter()
                     .take(arg_types.len() - (alias_args.len() - args.len()))
                     .cloned()
                     .collect();
diff --git a/base/src/lib.rs b/base/src/lib.rs
index f9c9c696..5e5d2bf4 100644
--- a/base/src/lib.rs
+++ b/base/src/lib.rs
@@ -6,6 +6,9 @@ extern crate log;
 #[macro_use]
 extern crate quick_error;
 extern crate pretty;
+extern crate smallvec;
+#[macro_use]
+extern crate collect_mac;
 
 pub mod ast;
 pub mod error;
diff --git a/base/src/types.rs b/base/src/types.rs
index 48431f16..2efc13b3 100644
--- a/base/src/types.rs
+++ b/base/src/types.rs
@@ -1,11 +1,13 @@
 use std::borrow::ToOwned;
 use std::fmt;
-use std::ops::Deref;
+use std::ops::{Deref, DerefMut};
 use std::sync::Arc;
 use std::marker::PhantomData;
 
 use pretty::{DocAllocator, Arena, DocBuilder};
 
+use smallvec::{SmallVec, VecLike};
+
 use ast::{self, DisplayEnv};
 use kind::{ArcKind, Kind, KindEnv};
 use symbol::{Symbol, SymbolRef};
@@ -214,6 +216,12 @@ pub struct Field<Id, T = ArcType<Id>> {
     pub typ: T,
 }
 
+/// SmallVec used in the `Type::App` constructor to avoid alloacting a `Vec` for every applied
+/// type. If `Type` is changed in a way that changes its size it is likely a good idea to change
+/// the number of elements in the `SmallVec` so that it fills out the entire `Type` enum while not
+/// increasing the size of `Type`.
+pub type AppVec<T> = SmallVec<[T; 2]>;
+
 /// The representation of gluon's types.
 ///
 /// For efficency this enum is not stored directly but instead a pointer wrapper which derefs to
@@ -230,7 +238,7 @@ pub enum Type<Id, T = ArcType<Id>> {
     Builtin(BuiltinType),
     /// A type application with multiple arguments. For example,
     /// `Map String Int` would be represented as `App(Map, [String, Int])`.
-    App(T, Vec<T>),
+    App(T, AppVec<T>),
     /// Record constructor, of kind `Row -> Type`
     Record(T),
     /// Variant constructor, of kind `Row -> Type`
@@ -274,10 +282,10 @@ impl<Id, T> Type<Id, T>
     }
 
     pub fn array(typ: T) -> T {
-        Type::app(Type::builtin(BuiltinType::Array), vec![typ])
+        Type::app(Type::builtin(BuiltinType::Array), collect![typ])
     }
 
-    pub fn app(id: T, args: Vec<T>) -> T {
+    pub fn app(id: T, args: AppVec<T>) -> T {
         if args.is_empty() {
             id
         } else {
@@ -330,7 +338,7 @@ impl<Id, T> Type<Id, T>
         args.into_iter()
             .rev()
             .fold(ret,
-                  |body, arg| Type::app(function.clone(), vec![arg, body]))
+                  |body, arg| Type::app(function.clone(), collect![arg, body]))
     }
 
     pub fn generic(typ: Generic<Id>) -> T {
@@ -1077,12 +1085,13 @@ pub fn walk_move_type_opt<F: ?Sized, I, T>(typ: &Type<I, T>, f: &mut F) -> Optio
     }
 }
 
-pub fn walk_move_types<'a, I, F, T>(types: I, mut f: F) -> Option<Vec<T>>
+pub fn walk_move_types<'a, I, F, T, R>(types: I, mut f: F) -> Option<R>
     where I: IntoIterator<Item = &'a T>,
           F: FnMut(&'a T) -> Option<T>,
           T: Clone + 'a,
+          R: Default + VecLike<T> + DerefMut<Target = [T]>,
 {
-    let mut out = Vec::new();
+    let mut out = R::default();
     walk_move_types2(types.into_iter(), false, &mut out, &mut f);
     if out.is_empty() {
         None
@@ -1091,11 +1100,11 @@ pub fn walk_move_types<'a, I, F, T>(types: I, mut f: F) -> Option<Vec<T>>
         Some(out)
     }
 }
-
-fn walk_move_types2<'a, I, F, T>(mut types: I, replaced: bool, output: &mut Vec<T>, f: &mut F)
+fn walk_move_types2<'a, I, F, T, R>(mut types: I, replaced: bool, output: &mut R, f: &mut F)
     where I: Iterator<Item = &'a T>,
           F: FnMut(&'a T) -> Option<T>,
           T: Clone + 'a,
+          R: VecLike<T> + DerefMut<Target = [T]>,
 {
     if let Some(typ) = types.next() {
         let new = f(typ);
diff --git a/check/Cargo.toml b/check/Cargo.toml
index 32dea577..10cdf669 100644
--- a/check/Cargo.toml
+++ b/check/Cargo.toml
@@ -14,8 +14,13 @@ documentation = "https://docs.rs/gluon"
 env_logger = { version = "0.3.4", optional = true }
 log = "0.3.6"
 union-find = "0.3.1"
+smallvec = "0.2.1"
 gluon_base = { path = "../base", version = "0.2.2" }
 gluon_parser = { path = "../parser", version = "0.2.2", optional = true }
 
+[dev-dependencies]
+collect-mac = "0.1.0"
+
 [features]
 test = ["gluon_parser", "env_logger"]
+
diff --git a/check/src/kindcheck.rs b/check/src/kindcheck.rs
index 96af6e58..e83d53ec 100644
--- a/check/src/kindcheck.rs
+++ b/check/src/kindcheck.rs
@@ -3,7 +3,7 @@ use std::fmt;
 use base::ast;
 use base::kind::{self, ArcKind, Kind, KindEnv};
 use base::symbol::Symbol;
-use base::types::{self, ArcType, BuiltinType, Field, Generic, Type, Walker};
+use base::types::{self, AppVec, ArcType, BuiltinType, Field, Generic, Type, Walker};
 
 use substitution::{Substitution, Substitutable};
 use unify;
@@ -172,7 +172,7 @@ impl<'a> KindCheck<'a> {
             Type::Builtin(builtin_typ) => Ok((self.builtin_kind(builtin_typ), typ.clone())),
             Type::App(ref ctor, ref args) => {
                 let (mut kind, ctor) = try!(self.kindcheck(ctor));
-                let mut new_args = Vec::new();
+                let mut new_args = AppVec::new();
                 for arg in args {
                     let f = Kind::function(self.subs.new_var(), self.subs.new_var());
                     kind = try!(self.unify(&f, kind));
diff --git a/check/src/lib.rs b/check/src/lib.rs
index e8eef764..c3e5eedf 100644
--- a/check/src/lib.rs
+++ b/check/src/lib.rs
@@ -9,6 +9,7 @@ extern crate log;
 #[cfg(test)]
 extern crate env_logger;
 extern crate union_find;
+extern crate smallvec;
 
 extern crate gluon_base as base;
 
diff --git a/check/src/typecheck.rs b/check/src/typecheck.rs
index 057b1ee2..9b25cfa3 100644
--- a/check/src/typecheck.rs
+++ b/check/src/typecheck.rs
@@ -13,7 +13,7 @@ use base::instantiate::{self, Instantiator};
 use base::kind::{Kind, KindEnv, ArcKind};
 use base::pos::{BytePos, Span, Spanned};
 use base::symbol::{Symbol, SymbolRef, SymbolModule, Symbols};
-use base::types::{self, Alias, AliasData, ArcType, Field, Generic};
+use base::types::{self, Alias, AliasData, AppVec, ArcType, Field, Generic};
 use base::types::{PrimitiveEnv, Type, TypeEnv, TypeVariable};
 use kindcheck::{self, KindCheck};
 use substitution::Substitution;
@@ -299,7 +299,6 @@ impl<'a> Typecheck<'a> {
                 self.stack_var(field.name, field.typ);
             }
         }
-
         let generic_args = alias.args.iter().cloned().map(Type::generic).collect();
         let typ = Type::<_, ArcType>::app(alias.as_ref().clone(), generic_args);
         {
@@ -1446,6 +1445,8 @@ fn primitive_type(op_type: &str) -> ArcType {
 /// Example:
 ///
 /// ```rust
+/// #[macro_use]
+/// extern crate collect_mac;
 /// extern crate gluon_base;
 /// extern crate gluon_check;
 ///
@@ -1455,17 +1456,17 @@ fn primitive_type(op_type: &str) -> ArcType {
 /// # fn main() {
 /// let i: ArcType = Type::int();
 /// let s: ArcType = Type::string();
-/// assert_eq!(unroll_typ(&*Type::app(Type::app(i.clone(), vec![s.clone()]), vec![i.clone()])),
-///            Some(Type::app(i.clone(), vec![s.clone(), i.clone()])));
-/// assert_eq!(unroll_typ(&*Type::app(Type::app(i.clone(), vec![i.clone()]), vec![s.clone()])),
-///            Some(Type::app(i.clone(), vec![i.clone(), s.clone()])));
+/// assert_eq!(unroll_typ(&*Type::app(Type::app(i.clone(), collect![s.clone()]), collect![i.clone()])),
+///            Some(Type::app(i.clone(), collect![s.clone(), i.clone()])));
+/// assert_eq!(unroll_typ(&*Type::app(Type::app(i.clone(), collect![i.clone()]), collect![s.clone()])),
+///            Some(Type::app(i.clone(), collect![i.clone(), s.clone()])));
 /// let f: ArcType = Type::builtin(BuiltinType::Function);
-/// assert_eq!(unroll_typ(&*Type::app(Type::app(f.clone(), vec![i.clone()]), vec![s.clone()])),
-///            Some(Type::function(vec![i.clone()], s.clone())));
+/// assert_eq!(unroll_typ(&*Type::app(Type::app(f.clone(), collect![i.clone()]), collect![s.clone()])),
+///            Some(Type::function(collect![i.clone()], s.clone())));
 /// # }
 /// ```
 pub fn unroll_typ(typ: &Type<Symbol>) -> Option<ArcType> {
-    let mut args = Vec::new();
+    let mut args = AppVec::new();
     let mut current = match *typ {
         Type::App(ref l, ref rest) => {
             // No need to unroll if `l` is not an application as that will just result in returning
diff --git a/check/src/unify_type.rs b/check/src/unify_type.rs
index ad16fff2..ea9f9c6e 100644
--- a/check/src/unify_type.rs
+++ b/check/src/unify_type.rs
@@ -1,8 +1,10 @@
 use std::fmt;
 use std::mem;
 
+use smallvec::VecLike;
+
 use base::error::Errors;
-use base::types::{self, ArcType, Field, Type, TypeVariable, TypeEnv, merge};
+use base::types::{self, AppVec, ArcType, Field, Type, TypeVariable, TypeEnv, merge};
 use base::symbol::{Symbol, SymbolRef};
 use base::instantiate;
 use base::scoped_map::ScopedMap;
@@ -170,31 +172,7 @@ fn do_zip_match<'a, U>(self_: &ArcType,
     debug!("Unifying:\n{:?} <=> {:?}", self_, other);
     match (&**self_, &**other) {
         (&Type::App(ref l, ref l_args), &Type::App(ref r, ref r_args)) => {
-            use std::cmp::Ordering::*;
-            match l_args.len().cmp(&r_args.len()) {
-                Equal => {
-                    let new_type = unifier.try_match(l, r);
-                    let new_args = walk_move_types(l_args.iter().zip(r_args),
-                                                   |l, r| unifier.try_match(l, r));
-                    Ok(merge(l, new_type, l_args, new_args, Type::app))
-                }
-                Less => {
-                    let offset = r_args.len() - l_args.len();
-                    let new_type =
-                        unifier.try_match(l, &Type::app(r.clone(), r_args[..offset].into()));
-                    let new_args = walk_move_types(l_args.iter().zip(&r_args[offset..]),
-                                                   |l, r| unifier.try_match(l, r));
-                    Ok(merge(l, new_type, l_args, new_args, Type::app))
-                }
-                Greater => {
-                    let offset = l_args.len() - r_args.len();
-                    let new_type =
-                        unifier.try_match(&Type::app(l.clone(), l_args[..offset].into()), r);
-                    let new_args = walk_move_types(l_args[offset..].iter().zip(r_args),
-                                                   |l, r| unifier.try_match(l, r));
-                    Ok(merge(r, new_type, r_args, new_args, Type::app))
-                }
-            }
+            unify_app(unifier, l, l_args, r, r_args)
         }
         (&Type::Record(ref l_row), &Type::Record(ref r_row)) => {
             // Store the current records so that they can be used when displaying field errors
@@ -277,6 +255,53 @@ fn do_zip_match<'a, U>(self_: &ArcType,
     }
 }
 
+fn unify_app<'a, U>(unifier: &mut UnifierState<'a, U>,
+                    l: &ArcType,
+                    l_args: &AppVec<ArcType>,
+                    r: &ArcType,
+                    r_args: &AppVec<ArcType>)
+                    -> Result<Option<ArcType>, Error<Symbol>>
+    where U: Unifier<State<'a>, ArcType>,
+{
+    use std::cmp::Ordering::*;
+    // Applications are curried `a b c d` == `((a b) c) d` we need to unify the last
+    // argument which eachother followed by the second last etc.
+    // If the number of arguments are not equal, the application with fewer arguments are
+    // unified with the other type applied on its remaining arguments
+    // a b c <> d e
+    // Unifies:
+    // c <> e
+    // a b <> d
+    match l_args.len().cmp(&r_args.len()) {
+        Equal => {
+            let new_type = unifier.try_match(l, r);
+            let new_args = walk_move_types(l_args.iter().zip(r_args),
+                                           |l, r| unifier.try_match(l, r));
+            Ok(merge(l, new_type, l_args, new_args, Type::app))
+        }
+        Less => {
+            let offset = r_args.len() - l_args.len();
+
+            let reduced_r = Type::app(r.clone(), r_args[..offset].iter().cloned().collect());
+            let new_type = unifier.try_match(l, &reduced_r);
+
+            let new_args = walk_move_types(l_args.iter().zip(&r_args[offset..]),
+                                           |l, r| unifier.try_match(l, r));
+            Ok(merge(l, new_type, l_args, new_args, Type::app))
+        }
+        Greater => {
+            let offset = l_args.len() - r_args.len();
+
+            let reduced_l = Type::app(l.clone(), l_args[..offset].iter().cloned().collect());
+            let new_type = unifier.try_match(&reduced_l, r);
+
+            let new_args = walk_move_types(l_args[offset..].iter().zip(r_args),
+                                           |l, r| unifier.try_match(l, r));
+            Ok(merge(r, new_type, r_args, new_args, Type::app))
+        }
+    }
+}
+
 fn gather_fields<'a, I, J, T>
     (l: I,
      r: J)
@@ -338,7 +363,7 @@ fn unify_rows<'a, U>(unifier: &mut UnifierState<'a, U>,
     });
 
     // Pack all fields from both records into a single `Type::ExtendRow` value
-    let mut fields = match new_both {
+    let mut fields: Vec<_> = match new_both {
         Some(fields) => fields,
         None => both.iter().map(|pair| pair.0.clone()).collect(),
     };
@@ -541,24 +566,26 @@ fn try_with_alias<'a, U>(unifier: &mut UnifierState<'a, U>,
     }
 }
 
-fn walk_move_types<'a, I, F, T>(types: I, mut f: F) -> Option<Vec<T>>
+fn walk_move_types<'a, I, F, T, R>(types: I, mut f: F) -> Option<R>
     where I: Iterator<Item = (&'a T, &'a T)>,
           F: FnMut(&'a T, &'a T) -> Option<T>,
           T: Clone + 'a,
+          R: Default + VecLike<T>,
 {
-    let mut out = Vec::new();
+    let mut out = R::default();
     walk_move_types2(types, false, &mut out, &mut f);
-    if out.is_empty() {
+    if out[..].is_empty() {
         None
     } else {
-        out.reverse();
+        out[..].reverse();
         Some(out)
     }
 }
-fn walk_move_types2<'a, I, F, T>(mut types: I, replaced: bool, output: &mut Vec<T>, f: &mut F)
+fn walk_move_types2<'a, I, F, T, R>(mut types: I, replaced: bool, output: &mut R, f: &mut F)
     where I: Iterator<Item = (&'a T, &'a T)>,
           F: FnMut(&'a T, &'a T) -> Option<T>,
           T: Clone + 'a,
+          R: VecLike<T>,
 {
     if let Some((l, r)) = types.next() {
         let new = f(l, r);
@@ -567,7 +594,7 @@ fn walk_move_types2<'a, I, F, T>(mut types: I, replaced: bool, output: &mut Vec<
             Some(typ) => {
                 output.push(typ);
             }
-            None if replaced || !output.is_empty() => {
+            None if replaced || !output[..].is_empty() => {
                 output.push(l.clone());
             }
             None => (),
diff --git a/parser/Cargo.toml b/parser/Cargo.toml
index dc60f30a..afb41d36 100644
--- a/parser/Cargo.toml
+++ b/parser/Cargo.toml
@@ -16,6 +16,7 @@ combine = "=2.0.0-beta3"
 env_logger = { version = "0.3.4", optional = true }
 log = "0.3.6"
 gluon_base = { path = "../base", version = "0.2.2" }
+collect-mac = "0.1.0"
 
 [features]
 test = ["env_logger"]
diff --git a/parser/src/lib.rs b/parser/src/lib.rs
index 1b40a017..822c3b11 100644
--- a/parser/src/lib.rs
+++ b/parser/src/lib.rs
@@ -21,7 +21,7 @@ use base::kind::Kind;
 use base::error::Errors;
 use base::pos::{self, BytePos, Span, Spanned};
 use base::symbol::{Name, Symbol};
-use base::types::{Alias, ArcType, Generic, Field, Type};
+use base::types::{Alias, AppVec, ArcType, Generic, Field, Type};
 
 use combine::primitives::{Consumed, Stream, StreamOnce, Error as CombineError, Info,
                           BufferedStream};
@@ -280,7 +280,7 @@ impl<'input, I, Id, F> ParserEnv<I, F>
     fn parse_type(&self, input: I) -> ParseResult<ArcType<Id>, I> {
         (many1(self.parser(ParserEnv::<I, F>::type_arg)),
          optional(token(Token::RightArrow).with(self.typ())))
-            .map(|(mut arg, ret): (Vec<_>, _)| {
+            .map(|(mut arg, ret): (AppVec<_>, _)| {
                 let arg = if arg.len() == 1 {
                     arg.pop().unwrap()
                 } else {
@@ -381,18 +381,18 @@ impl<'input, I, Id, F> ParserEnv<I, F>
 
     fn type_binding(&self, input: I) -> ParseResult<TypeBinding<Id>, I> {
         (self.ident(), many(self.ident()))
-            .then(|(name, args): (Id, Vec<Id>)| {
-                let arg_types = args.iter()
-                    .map(|id| {
-                        Type::generic(Generic {
-                            kind: Kind::variable(0),
-                            id: id.clone(),
-                        })
-                    })
-                    .collect();
+            .then(|(name, args): (Id, AppVec<Id>)| {
                 let return_type = if args.is_empty() {
                     Type::ident(name.clone())
                 } else {
+                    let arg_types = args.iter()
+                        .map(|id| {
+                            Type::generic(Generic {
+                                kind: Kind::variable(0),
+                                id: id.clone(),
+                            })
+                        })
+                        .collect();
                     Type::app(Type::ident(name.clone()), arg_types)
                 };
                 token(Token::Equal)
diff --git a/vm/Cargo.toml b/vm/Cargo.toml
index 22ac964f..0745da6d 100644
--- a/vm/Cargo.toml
+++ b/vm/Cargo.toml
@@ -15,6 +15,7 @@ env_logger = { version = "0.3.4", optional = true }
 log = "0.3.6"
 quick-error = "1.1.0"
 mopa = "0.2.2"
+collect-mac = "0.1.0"
 gluon_base = { path = "../base", version = "0.2.2" }
 
 [features]
diff --git a/vm/src/api.rs b/vm/src/api.rs
index 3c1bb394..b59b0b4c 100644
--- a/vm/src/api.rs
+++ b/vm/src/api.rs
@@ -557,7 +557,7 @@ impl VmType for Ordering {
     type Type = Self;
     fn make_type(vm: &Thread) -> ArcType {
         let symbol = vm.find_type_info("std.types.Ordering").unwrap().name.clone();
-        Type::app(Type::ident(symbol), vec![])
+        Type::app(Type::ident(symbol), collect![])
     }
 }
 impl<'vm> Pushable<'vm> for Ordering {
@@ -744,7 +744,7 @@ impl<T: VmType> VmType for Option<T>
     type Type = Option<T::Type>;
     fn make_type(vm: &Thread) -> ArcType {
         let symbol = vm.find_type_info("std.types.Option").unwrap().name.clone();
-        Type::app(Type::ident(symbol), vec![T::make_type(vm)])
+        Type::app(Type::ident(symbol), collect![T::make_type(vm)])
     }
 }
 impl<'vm, T: Pushable<'vm>> Pushable<'vm> for Option<T> {
@@ -787,7 +787,7 @@ impl<T: VmType, E: VmType> VmType for StdResult<T, E>
     fn make_type(vm: &Thread) -> ArcType {
         let symbol = vm.find_type_info("std.types.Result").unwrap().name.clone();
         Type::app(Type::ident(symbol),
-                  vec![E::make_type(vm), T::make_type(vm)])
+                  collect![E::make_type(vm), T::make_type(vm)])
     }
 }
 
@@ -857,7 +857,7 @@ impl<T> VmType for IO<T>
     fn make_type(vm: &Thread) -> ArcType {
         let env = vm.global_env().get_env();
         let alias = env.find_type_info("IO").unwrap().into_owned();
-        Type::app(alias.into_type(), vec![T::make_type(vm)])
+        Type::app(alias.into_type(), collect![T::make_type(vm)])
     }
     fn extra_args() -> VmIndex {
         1
@@ -1506,7 +1506,7 @@ impl <$($args: VmType,)* R: VmType> VmType for fn ($($args),*) -> R {
     type Type = fn ($($args::Type),*) -> R::Type;
     #[allow(non_snake_case)]
     fn make_type(vm: &Thread) -> ArcType {
-        let args = vec![$(make_type::<$args>(vm)),*];
+        let args = collect![$(make_type::<$args>(vm)),*];
         Type::function(args, make_type::<R>(vm))
     }
 }
diff --git a/vm/src/channel.rs b/vm/src/channel.rs
index 3781d507..7a99e570 100644
--- a/vm/src/channel.rs
+++ b/vm/src/channel.rs
@@ -81,7 +81,7 @@ impl<T: VmType> VmType for Sender<T>
     type Type = Sender<T::Type>;
     fn make_type(vm: &Thread) -> ArcType {
         let symbol = vm.global_env().get_env().find_type_info("Sender").unwrap().name.clone();
-        Type::app(Type::ident(symbol), vec![T::make_type(vm)])
+        Type::app(Type::ident(symbol), collect![T::make_type(vm)])
     }
 }
 
@@ -91,7 +91,7 @@ impl<T: VmType> VmType for Receiver<T>
     type Type = Receiver<T::Type>;
     fn make_type(vm: &Thread) -> ArcType {
         let symbol = vm.global_env().get_env().find_type_info("Receiver").unwrap().name.clone();
-        Type::app(Type::ident(symbol), vec![T::make_type(vm)])
+        Type::app(Type::ident(symbol), collect![T::make_type(vm)])
     }
 }
 
diff --git a/vm/src/lazy.rs b/vm/src/lazy.rs
index 7954fa9e..c2f5c531 100644
--- a/vm/src/lazy.rs
+++ b/vm/src/lazy.rs
@@ -76,7 +76,7 @@ impl<T> VmType for Lazy<T>
         let env = vm.global_env().get_env();
         let symbol = env.find_type_info("Lazy").unwrap().name.clone();
         let ctor = Type::ident(symbol);
-        types::Type::app(ctor, vec![T::make_type(vm)])
+        types::Type::app(ctor, collect![T::make_type(vm)])
     }
 }
 
diff --git a/vm/src/lib.rs b/vm/src/lib.rs
index be67a24b..5af368e6 100644
--- a/vm/src/lib.rs
+++ b/vm/src/lib.rs
@@ -8,6 +8,8 @@ extern crate env_logger;
 extern crate quick_error;
 #[macro_use]
 extern crate mopa;
+#[macro_use]
+extern crate collect_mac;
 
 extern crate gluon_base as base;
 
diff --git a/vm/src/reference.rs b/vm/src/reference.rs
index 751d7b4f..404888c2 100644
--- a/vm/src/reference.rs
+++ b/vm/src/reference.rs
@@ -60,7 +60,7 @@ impl<T> VmType for Reference<T>
         let env = vm.global_env().get_env();
         let symbol = env.find_type_info("Ref").unwrap().name.clone();
         let ctor = Type::ident(symbol);
-        Type::app(ctor, vec![T::make_type(vm)])
+        Type::app(ctor, collect![T::make_type(vm)])
     }
 }
 
diff --git a/vm/src/vm.rs b/vm/src/vm.rs
index 8a43cebd..ef4822fa 100644
--- a/vm/src/vm.rs
+++ b/vm/src/vm.rs
@@ -9,7 +9,7 @@ use base::fnv::FnvMap;
 use base::kind::{ArcKind, Kind, KindEnv};
 use base::metadata::{Metadata, MetadataEnv};
 use base::symbol::{Name, Symbol, SymbolRef};
-use base::types::{Alias, AliasData, ArcType, Generic, PrimitiveEnv, Type, TypeEnv};
+use base::types::{Alias, AliasData, AppVec, ArcType, Generic, PrimitiveEnv, Type, TypeEnv};
 
 use macros::MacroEnv;
 use {Error, Result};
@@ -422,7 +422,7 @@ impl GlobalVmState {
             Err(Error::TypeAlreadyExists(name.into()))
         } else {
             let id = TypeId::of::<T>();
-            let arg_types: Vec<_> = args.iter().map(|g| self.get_generic(g)).collect();
+            let arg_types: AppVec<_> = args.iter().map(|g| self.get_generic(g)).collect();
             let args = arg_types.iter()
                 .map(|g| match **g {
                     Type::Generic(ref g) => g.clone(),


Test patch:
diff --git a/base/tests/types.rs b/base/tests/types.rs
index adb7c9e5..2e62d0fd 100644
--- a/base/tests/types.rs
+++ b/base/tests/types.rs
@@ -1,4 +1,6 @@
 extern crate gluon_base as base;
+#[macro_use]
+extern crate collect_mac;
 
 use std::ops::Deref;
 
@@ -18,7 +20,7 @@ fn type_con<I, T>(s: I, args: Vec<T>) -> Type<I, T>
                 id: s,
             })
         }
-        Err(()) => Type::App(Type::ident(s), args),
+        Err(()) => Type::App(Type::ident(s), args.into_iter().collect()),
     }
 }
 
diff --git a/check/tests/completion.rs b/check/tests/completion.rs
index f6f83d48..c71fff89 100644
--- a/check/tests/completion.rs
+++ b/check/tests/completion.rs
@@ -1,3 +1,5 @@
+#[macro_use]
+extern crate collect_mac;
 extern crate env_logger;
 
 extern crate gluon_base as base;
diff --git a/check/tests/fail.rs b/check/tests/fail.rs
index f2a7d9b8..e6b24b19 100644
--- a/check/tests/fail.rs
+++ b/check/tests/fail.rs
@@ -1,3 +1,5 @@
+#[macro_use]
+extern crate collect_mac;
 extern crate env_logger;
 
 extern crate gluon_base as base;
diff --git a/check/tests/metadata.rs b/check/tests/metadata.rs
index a681a777..b1e61ce1 100644
--- a/check/tests/metadata.rs
+++ b/check/tests/metadata.rs
@@ -1,3 +1,5 @@
+#[macro_use]
+extern crate collect_mac;
 extern crate env_logger;
 
 extern crate gluon_base as base;
diff --git a/check/tests/pass.rs b/check/tests/pass.rs
index b1d694c6..ab178ac0 100644
--- a/check/tests/pass.rs
+++ b/check/tests/pass.rs
@@ -1,3 +1,5 @@
+#[macro_use]
+extern crate collect_mac;
 extern crate env_logger;
 
 extern crate gluon_base as base;
@@ -287,7 +289,7 @@ in eq_Int
                                         name: support::intern_unscoped("=="),
                                         typ: Type::function(vec![typ("a"), typ("a")], bool),
                                     }]));
-    let expected = Ok(Type::app(eq, vec![typ("Int")]));
+    let expected = Ok(Type::app(eq, collect![typ("Int")]));
 
     assert_eq!(result, expected);
 }
@@ -320,7 +322,8 @@ in option_Functor.map (\x -> x #Int- 1) (Some 2)
                                                                                   vec![typ("a")])),
                                       }]);
     let option = alias("Option", &["a"], variants);
-    let expected = Ok(Type::app(option, vec![typ("Int")]));
+
+    let expected = Ok(Type::app(option, collect![typ("Int")]));
 
     assert_eq!(result, expected);
 }
@@ -359,7 +362,7 @@ test
                                                                    support::typ_a("Test",
                                                                                   vec![typ("a")])),
                                       }]);
-    let expected = Ok(Type::app(alias("Test", &["a"], variants), vec![Type::unit()]));
+    let expected = Ok(Type::app(alias("Test", &["a"], variants), collect![Type::unit()]));
 
     assert_eq!(result, expected);
 }
@@ -409,7 +412,7 @@ in f
 ";
     let result = support::typecheck(text);
     let function = alias("Fn", &["a", "b"], Type::function(vec![typ("a")], typ("b")));
-    let args = vec![typ("String"), typ("Int")];
+    let args = collect![typ("String"), typ("Int")];
     let expected = Ok(Type::app(function, args));
 
     assert_eq!(result, expected);
@@ -539,7 +542,7 @@ return 1
         Type::variant(vec![Field {
                                name: intern(name),
                                typ: Type::function(vec![typ("a")],
-                                                        Type::app(typ(name), vec![typ("a")])),
+                                                        Type::app(typ(name), collect![typ("a")])),
                            }])
     };
     let test = alias("Test", &["a"], variant("Test"));
@@ -557,8 +560,9 @@ return 1
                                    id: intern("a"),
                                },
                             ],
-                           Type::app(Type::generic(m), vec![Type::app(id, vec![typ("a")])]));
-    let expected = Ok(Type::app(id_t, vec![test, typ("Int")]));
+                           Type::app(Type::generic(m),
+                                     collect![Type::app(id, collect![typ("a")])]));
+    let expected = Ok(Type::app(id_t, collect![test, typ("Int")]));
 
     assert_eq!(result, expected);
 }
diff --git a/check/tests/row_polymorphism.rs b/check/tests/row_polymorphism.rs
index b34dcc5c..04744f3e 100644
--- a/check/tests/row_polymorphism.rs
+++ b/check/tests/row_polymorphism.rs
@@ -1,3 +1,5 @@
+#[macro_use]
+extern crate collect_mac;
 extern crate env_logger;
 
 extern crate gluon_base as base;
diff --git a/check/tests/stack_overflow.rs b/check/tests/stack_overflow.rs
index 7b7a1b23..6aeb5bf6 100644
--- a/check/tests/stack_overflow.rs
+++ b/check/tests/stack_overflow.rs
@@ -1,3 +1,6 @@
+#[macro_use]
+extern crate collect_mac;
+
 extern crate gluon_base as base;
 extern crate gluon_parser as parser;
 extern crate gluon_check as check;
diff --git a/check/tests/support/mod.rs b/check/tests/support/mod.rs
index 8eb94473..308d1936 100644
--- a/check/tests/support/mod.rs
+++ b/check/tests/support/mod.rs
@@ -60,7 +60,7 @@ impl MockEnv {
         let mut interner = interner.borrow_mut();
 
         let bool_sym = interner.symbol("Bool");
-        let bool_ty = Type::app(Type::ident(bool_sym.clone()), vec![]);
+        let bool_ty = Type::app(Type::ident(bool_sym.clone()), collect![]);
 
         MockEnv { bool: Alias::new(bool_sym, vec![], bool_ty) }
     }
@@ -182,7 +182,7 @@ pub fn typ_a<T>(s: &str, args: Vec<T>) -> T
             if args.len() == 0 {
                 Type::ident(intern(s))
             } else {
-                Type::app(Type::ident(intern(s)), args)
+                Type::app(Type::ident(intern(s)), args.into_iter().collect())
             }
         }
     }
diff --git a/parser/tests/basic.rs b/parser/tests/basic.rs
index fac2f644..9d0963c0 100644
--- a/parser/tests/basic.rs
+++ b/parser/tests/basic.rs
@@ -3,6 +3,8 @@ extern crate gluon_parser as parser;
 extern crate env_logger;
 #[macro_use]
 extern crate log;
+#[macro_use]
+extern crate collect_mac;
 
 mod support;
 
@@ -296,7 +298,7 @@ fn op_identifier() {
 fn variant_type() {
     let _ = ::env_logger::init();
     let e = parse_new!("type Option a = | None | Some a in Some 1");
-    let option = Type::app(typ("Option"), vec![typ("a")]);
+    let option = Type::app(typ("Option"), collect![typ("a")]);
     let none = Type::function(vec![], option.clone());
     let some = Type::function(vec![typ("a")], option.clone());
     assert_eq!(e,
@@ -612,7 +614,7 @@ x
                                                     comment: None,
                                                     name: no_loc(Pattern::Ident(TypedIdent::new(intern("x")))),
                                                     typ: Type::app(typ("->"),
-                                                                   vec![typ("Int"), typ("Int")]),
+                                                                   collect![typ("Int"), typ("Int")]),
                                                     args: vec![],
                                                     expr: id("x"),
                                                 }],