Repository: gluon-lang/gluon
Pull request #676 (2019-01-11 22:18:45)

Increase performance all over the compiler
Many small performance improvements focused on just simplifying code and doing less work.


Patch:
diff --git a/base/src/ast.rs b/base/src/ast.rs
index bfed2d13..a7915956 100644
--- a/base/src/ast.rs
+++ b/base/src/ast.rs
@@ -12,11 +12,11 @@ use either::Either;
 use itertools::Itertools;
 
 use crate::metadata::{Comment, Metadata};
-use ordered_float::NotNan;
 use crate::pos::{self, BytePos, HasSpan, Span, Spanned};
 use crate::resolve::remove_aliases_cow;
 use crate::symbol::Symbol;
 use crate::types::{self, Alias, AliasData, ArcType, ArgType, Type, TypeEnv};
+use ordered_float::NotNan;
 
 pub trait DisplayEnv {
     type Ident;
@@ -939,6 +939,10 @@ fn get_return_type(
 }
 
 pub fn is_operator_char(c: char) -> bool {
+    (c as u32) < 128 && is_operator_byte(c as u8)
+}
+
+pub fn is_operator_byte(c: u8) -> bool {
     macro_rules! match_token {
         ($($x: pat),*) => {
             match c {
@@ -948,26 +952,26 @@ pub fn is_operator_char(c: char) -> bool {
         }
     }
     match_token! {
-        '!',
-        '#',
-        '$',
-        '%',
-        '&',
-        '*',
-        '+',
-        '-',
-        '.',
-        '/',
-        '<',
-        '=',
-        '>',
-        '?',
-        '@',
-        '\\',
-        '^',
-        '|',
-        '~',
-        ':'
+        b'!',
+        b'#',
+        b'$',
+        b'%',
+        b'&',
+        b'*',
+        b'+',
+        b'-',
+        b'.',
+        b'/',
+        b'<',
+        b'=',
+        b'>',
+        b'?',
+        b'@',
+        b'\\',
+        b'^',
+        b'|',
+        b'~',
+        b':'
     }
 }
 
diff --git a/base/src/pos.rs b/base/src/pos.rs
index 31bf463c..09176eaa 100644
--- a/base/src/pos.rs
+++ b/base/src/pos.rs
@@ -18,15 +18,14 @@ pub struct Location {
 }
 
 impl Location {
-    pub fn shift(mut self, ch: char) -> Location {
-        if ch == '\n' {
+    pub fn shift(&mut self, ch: u8) {
+        if ch == b'\n' {
             self.line += LineOffset(1);
             self.column = Column(1);
         } else {
             self.column += ColumnOffset(1);
         }
-        self.absolute += ByteOffset(ch.len_utf8() as i64);
-        self
+        self.absolute += ByteOffset(1);
     }
 }
 
diff --git a/base/src/scoped_map.rs b/base/src/scoped_map.rs
index 71e83a69..32dab4db 100644
--- a/base/src/scoped_map.rs
+++ b/base/src/scoped_map.rs
@@ -164,10 +164,7 @@ impl<K: Eq + Hash + Clone, V> ScopedMap<K, V> {
 
     /// Swaps the value stored at key, or inserts it if it is not present
     pub fn swap(&mut self, k: K, v: V) -> Option<V> {
-        let vec = match self.map.entry(k.clone()) {
-            hash_map::Entry::Occupied(v) => v.into_mut(),
-            hash_map::Entry::Vacant(v) => v.insert(Vec::new()),
-        };
+        let vec = self.map.entry(k.clone()).or_default();
         if vec.is_empty() {
             vec.push(v);
             self.scopes.push(Some(k));
@@ -203,10 +200,7 @@ impl<K: Eq + Hash + Clone, V> ScopedMap<K, V> {
     }
 
     pub fn insert(&mut self, k: K, v: V) -> bool {
-        let vec = match self.map.entry(k.clone()) {
-            hash_map::Entry::Occupied(v) => v.into_mut(),
-            hash_map::Entry::Vacant(v) => v.insert(Vec::new()),
-        };
+        let vec = self.map.entry(k.clone()).or_default();
         vec.push(v);
         self.scopes.push(Some(k));
         vec.len() == 1
diff --git a/benches/parser.rs b/benches/parser.rs
index 45924427..94754336 100644
--- a/benches/parser.rs
+++ b/benches/parser.rs
@@ -9,7 +9,7 @@ use bencher::{black_box, Bencher};
 use crate::base::symbol::{SymbolModule, Symbols};
 use crate::base::types::TypeCache;
 
-fn prelude(b: &mut Bencher) {
+fn parse_prelude(b: &mut Bencher) {
     use std::fs::File;
     use std::io::Read;
     let mut text = String::new();
@@ -26,5 +26,5 @@ fn prelude(b: &mut Bencher) {
     })
 }
 
-benchmark_group!(parser, prelude);
+benchmark_group!(parser, parse_prelude);
 benchmark_main!(parser);
diff --git a/check/src/substitution.rs b/check/src/substitution.rs
index 429f703f..fc35a081 100644
--- a/check/src/substitution.rs
+++ b/check/src/substitution.rs
@@ -336,7 +336,7 @@ impl<T: Substitutable> Substitution<T> {
 pub fn is_variable_unified(subs: &Substitution<ArcType>, var: &ArcType) -> bool {
     match **var {
         Type::Variable(ref var) => subs.find_type_for_var(var.id).is_some(),
-        _ => unreachable!(),
+        _ => false,
     }
 }
 
diff --git a/check/src/typecheck.rs b/check/src/typecheck.rs
index 4bae2d58..0b888574 100644
--- a/check/src/typecheck.rs
+++ b/check/src/typecheck.rs
@@ -12,9 +12,9 @@ use codespan_reporting::Diagnostic;
 
 use crate::base::{
     ast::{
-        self, Argument, AstType, DisplayEnv, Do, Expr, IdentEnv, Literal, MutVisitor, Pattern,
-        PatternField, SpannedExpr, SpannedIdent, SpannedPattern, TypeBinding, Typed, TypedIdent,
-        ValueBinding, ValueBindings,
+        Argument, AstType, DisplayEnv, Do, Expr, IdentEnv, Literal, Pattern, PatternField,
+        SpannedExpr, SpannedIdent, SpannedPattern, TypeBinding, Typed, TypedIdent, ValueBinding,
+        ValueBindings,
     },
     error::{AsDiagnostic, Errors},
     fnv::{FnvMap, FnvSet},
@@ -26,8 +26,8 @@ use crate::base::{
     scoped_map::ScopedMap,
     symbol::{Symbol, SymbolModule, SymbolRef, Symbols},
     types::{
-        self, Alias, AliasRef, AppVec, ArcType, ArgType, BuiltinType, Field, Filter, Generic,
-        PrimitiveEnv, Skolem, Type, TypeCache, TypeEnv, TypeFormatter, TypeVariable,
+        self, Alias, AliasRef, ArcType, ArgType, Field, Filter, Generic, PrimitiveEnv, Skolem,
+        Type, TypeCache, TypeEnv, TypeFormatter, TypeVariable,
     },
 };
 
@@ -39,6 +39,10 @@ use crate::{
     unify_type::{self, new_skolem_scope, Error as UnifyTypeError},
 };
 
+use self::generalize::TypeGeneralizer;
+
+mod generalize;
+
 /// Type representing a single error when checking a type
 #[derive(Debug, PartialEq)]
 pub enum TypeError<I> {
@@ -727,10 +731,11 @@ impl<'a> Typecheck<'a> {
         let mut typ = self.typecheck_opt(expr, expected_type);
         {
             if let Some(expected_type) = expected_type {
+                let type_cache = &self.type_cache;
                 self.type_variables.extend(
                     expected_type
                         .forall_params()
-                        .map(|param| (param.id.clone(), Type::hole())),
+                        .map(|param| (param.id.clone(), type_cache.hole())),
                 );
             }
             // Only the 'tail' expression need to be generalized at this point as all bindings
@@ -740,7 +745,6 @@ impl<'a> Typecheck<'a> {
             self.generalize_variables(0, &mut [].iter_mut(), tail);
 
             self.generalize_type(0, &mut typ, tail.span);
-            typ = types::walk_move_type(typ, &mut unroll_typ);
         }
 
         if self.errors.has_errors() {
@@ -2424,7 +2428,8 @@ impl<'a> Typecheck<'a> {
             }
             Type::Forall(ref params, ref typ, _) => {
                 for param in params {
-                    self.type_variables.insert(param.id.clone(), typ.clone());
+                    self.type_variables
+                        .insert(param.id.clone(), self.type_cache.hole());
                 }
                 let result = self.create_unifiable_signature_(typ);
                 // Remove any implicit variables inserted inside the forall since
@@ -3100,427 +3105,3 @@ fn expr_check_span(e: &SpannedExpr<Symbol>) -> Span<BytePos> {
         _ => e.span,
     }
 }
-
-/// Removes layers of `Type::App` and `Type::Record` by packing them into a single `Type::App` or
-/// `Type::Record`
-///
-/// Example:
-///
-/// ```rust
-/// #[macro_use]
-/// extern crate collect_mac;
-/// extern crate gluon_base;
-/// extern crate gluon_check;
-///
-/// use gluon_base::types::{Type, ArcType, BuiltinType};
-/// use gluon_check::typecheck::unroll_typ;
-///
-/// # fn main() {
-/// let i: ArcType = Type::int();
-/// let s: ArcType = Type::string();
-/// 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(), collect![i.clone()]), collect![s.clone()])),
-///            Some(Type::function(collect![i.clone()], s.clone())));
-/// # }
-/// ```
-pub fn unroll_typ(typ: &ArcType) -> Option<ArcType> {
-    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
-            // an application that is identical to `typ`
-            match **l {
-                Type::App(..) => (),
-                _ => return None,
-            }
-            args.extend(rest.iter().rev().cloned());
-            l
-        }
-        _ => return unroll_record(typ),
-    };
-    while let Type::App(ref l, ref rest) = **current {
-        args.extend(rest.iter().rev().cloned());
-        current = l;
-    }
-    if args.is_empty() {
-        None
-    } else {
-        args.reverse();
-        match **current {
-            Type::Builtin(BuiltinType::Function) if args.len() == 2 => {
-                let ret = args.pop().unwrap();
-                Some(Type::function(args.into_iter().collect(), ret))
-            }
-            _ => Some(Type::app(current.clone(), args)),
-        }
-    }
-}
-
-fn unroll_record(typ: &Type<Symbol>) -> Option<ArcType> {
-    let mut new_types = Vec::new();
-    let mut new_fields = Vec::new();
-    let mut current = match *typ {
-        Type::ExtendRow {
-            ref types,
-            ref fields,
-            ref rest,
-        } => match **rest {
-            Type::ExtendRow { .. } => {
-                new_types.extend_from_slice(types);
-                new_fields.extend_from_slice(fields);
-                rest
-            }
-            _ => return None,
-        },
-        _ => return None,
-    };
-    while let Type::ExtendRow {
-        ref types,
-        ref fields,
-        ref rest,
-    } = **current
-    {
-        new_types.extend_from_slice(types);
-        new_fields.extend_from_slice(fields);
-        current = rest;
-    }
-    if new_types.is_empty() && new_fields.is_empty() {
-        None
-    } else {
-        Some(Type::extend_row(new_types, new_fields, current.clone()))
-    }
-}
-
-struct TypeGeneralizer<'a, 'b: 'a> {
-    level: u32,
-    unbound_variables: FnvMap<Symbol, Generic<Symbol>>,
-    variable_generator: TypeVariableGenerator,
-    tc: &'a mut Typecheck<'b>,
-    context: ArcType,
-    span: Span<BytePos>,
-}
-
-impl<'a, 'b> ::std::ops::Deref for TypeGeneralizer<'a, 'b> {
-    type Target = Typecheck<'b>;
-    fn deref(&self) -> &Typecheck<'b> {
-        self.tc
-    }
-}
-
-impl<'a, 'b> ::std::ops::DerefMut for TypeGeneralizer<'a, 'b> {
-    fn deref_mut(&mut self) -> &mut Typecheck<'b> {
-        self.tc
-    }
-}
-
-impl<'a, 'b> TypeGeneralizer<'a, 'b> {
-    fn new(
-        level: u32,
-        tc: &'a mut Typecheck<'b>,
-        typ: &ArcType,
-        span: Span<BytePos>,
-    ) -> TypeGeneralizer<'a, 'b> {
-        TypeGeneralizer {
-            level,
-            unbound_variables: FnvMap::default(),
-            variable_generator: TypeVariableGenerator::new(level, &tc.subs, typ),
-            tc,
-            context: typ.clone(),
-            span,
-        }
-    }
-
-    /// Generalizing updates all variables which are above `level` into "generic variables". A
-    /// generic variable is instantiated with a fresh type variable each time it is refered to.
-    ///
-    /// Generalzing is a crucial part when inferring types as types will otherwise be less general
-    /// than they need to. Consider the following expression.
-    /// ```f#
-    /// let id x = x
-    /// in id 2
-    /// ```
-    /// If the variable in `id` was not generalized before the `id 2` call the variable would be
-    /// unified to an `Int` which is not what we want. Generalazing before checking the body of the
-    /// `let` basically infers that the variables in `id` does not refer to anything outside the
-    /// `let` scope and can thus be "generalized" into `a -> a` which is instantiated with a fresh
-    /// type variable in the `id 2` call.
-    fn generalize_variables<'i>(
-        &mut self,
-        args: &mut Iterator<Item = &'i mut SpannedIdent<Symbol>>,
-        expr: &mut SpannedExpr<Symbol>,
-    ) {
-        self.tc.type_variables.enter_scope();
-
-        // Replaces all type variables with their inferred types
-        struct ReplaceVisitor<'a: 'c, 'b: 'a, 'c> {
-            generalizer: &'c mut TypeGeneralizer<'a, 'b>,
-        }
-
-        impl<'a, 'b, 'c, 'd> MutVisitor<'d> for ReplaceVisitor<'a, 'b, 'c> {
-            type Ident = Symbol;
-
-            fn visit_expr(&mut self, e: &'d mut SpannedExpr<Self::Ident>) {
-                self.generalizer.tc.type_variables.enter_scope();
-                self.generalizer.span = e.span;
-                ast::walk_mut_expr(self, e);
-                self.generalizer.tc.type_variables.exit_scope();
-            }
-
-            fn visit_spanned_typed_ident(&mut self, id: &mut SpannedIdent<Symbol>) {
-                self.generalizer.span = id.span;
-                self.visit_ident(&mut id.value)
-            }
-            fn visit_typ(&mut self, typ: &mut ArcType) {
-                {
-                    let type_cache = &self.generalizer.tc.type_cache;
-                    self.generalizer.tc.type_variables.extend(
-                        typ.forall_params()
-                            .map(|param| (param.id.clone(), type_cache.hole())),
-                    );
-                }
-                if let Some(finished) = self.generalizer.generalize_type(typ) {
-                    *typ = finished;
-                }
-            }
-        }
-
-        {
-            let mut visitor = ReplaceVisitor { generalizer: self };
-            visitor.visit_expr(expr);
-            for arg in &mut *args {
-                visitor.visit_typ(&mut arg.value.typ)
-            }
-        }
-
-        self.tc.type_variables.exit_scope();
-    }
-
-    fn generalize_type_top(&mut self, typ: &mut ArcType) {
-        self.tc.type_variables.enter_scope();
-
-        let mut result_type = self.generalize_type(typ);
-
-        self.tc.type_variables.exit_scope();
-
-        if result_type.is_none() && !self.unbound_variables.is_empty() {
-            result_type = Some(typ.clone());
-        }
-
-        result_type = result_type.map(|typ| {
-            let mut params = self
-                .unbound_variables
-                .drain()
-                .map(|(_, generic)| generic)
-                .collect::<Vec<_>>();
-            params.sort_unstable_by(|l, r| l.id.declared_name().cmp(r.id.declared_name()));
-
-            Type::forall(params, typ)
-        });
-        if let Some(finished) = result_type {
-            *typ = finished;
-        }
-        debug!("End generalize {}", typ);
-    }
-
-    fn generalize_type(&mut self, typ: &ArcType) -> Option<ArcType> {
-        let replacement = self.subs.replace_variable(typ);
-        let mut typ = typ;
-        if let Some(ref t) = replacement {
-            typ = t;
-        }
-        match **typ {
-            Type::Variable(ref var) if self.subs.get_level(var.id) >= self.level => {
-                // Create a prefix if none exists
-                let id = self.variable_generator.next_variable(self.tc);
-
-                let gen: ArcType = Type::generic(Generic::new(id.clone(), var.kind.clone()));
-                debug!("Gen {} to {}", var.id, gen);
-                self.subs.insert(var.id, gen.clone());
-
-                self.unbound_variables
-                    .insert(id.clone(), Generic::new(id, var.kind.clone()));
-
-                Some(gen)
-            }
-            Type::ExtendRow {
-                ref types,
-                ref fields,
-                ref rest,
-            } => {
-                let new_fields = types::walk_move_types(fields, |field| {
-                    // Make a new name base for any unbound variables in the record field
-                    // Gives { id : a0 -> a0, const : b0 -> b1 -> b1 }
-                    // instead of { id : a0 -> a0, const : a1 -> a2 -> a2 }
-                    self.generalize_type(&field.typ)
-                        .map(|typ| Field::new(field.name.clone(), typ))
-                });
-                let new_rest = self.generalize_type(rest);
-                merge::merge(fields, new_fields, rest, new_rest, |fields, rest| {
-                    Type::extend_row(types.clone(), fields, rest)
-                })
-                .or_else(|| replacement.clone())
-            }
-
-            Type::Forall(ref params, ref typ, Some(ref vars)) => {
-                use crate::substitution::is_variable_unified;
-                trace!("Generalize `{}` {:?}", typ, vars);
-                let typ = {
-                    let subs = &self.tc.subs;
-                    self.tc.named_variables.clear();
-                    self.tc.named_variables.extend(
-                        params
-                            .iter()
-                            .zip(vars)
-                            .filter(|&(_, var)| is_variable_unified(subs, var))
-                            .map(|(param, var)| (param.id.clone(), var.clone())),
-                    );;
-                    typ.instantiate_generics_(&mut self.tc.named_variables)
-                        .unwrap_or(typ.clone())
-                };
-
-                self.type_variables.enter_scope();
-                self.type_variables.extend(
-                    params
-                        .iter()
-                        .zip(vars)
-                        .map(|(param, var)| (param.id.clone(), var.clone())),
-                );
-
-                trace!("Generalize forall => `{}`", typ);
-
-                let new_type = self.generalize_type(&typ);
-                self.type_variables.exit_scope();
-
-                Some(Type::forall(
-                    params
-                        .iter()
-                        .zip(vars)
-                        .filter(|&(_, var)| !is_variable_unified(&self.subs, var))
-                        .map(|(param, _)| param.clone())
-                        .collect(),
-                    new_type.unwrap_or_else(|| typ.clone()),
-                ))
-            }
-
-            Type::Skolem(ref skolem) => {
-                if !self.type_variables.contains_key(&skolem.name) {
-                    self.tc.error(
-                        self.span,
-                        TypeError::Message(format!(
-                            "Skolem variable `{}` would escape as it is not bound in `{}`",
-                            skolem.name, self.context
-                        )),
-                    );
-                }
-                if self.subs.get_level(skolem.id) >= self.level {
-                    let generic = Generic {
-                        id: skolem.name.clone(),
-                        kind: skolem.kind.clone(),
-                    };
-
-                    if self.type_variables.get(&generic.id).is_none() {
-                        self.unbound_variables
-                            .insert(generic.id.clone(), generic.clone());
-                    }
-
-                    Some(Type::generic(generic))
-                } else {
-                    None
-                }
-            }
-
-            _ => {
-                if let Type::Forall(ref params, _, None) = **typ {
-                    self.type_variables
-                        .extend(params.iter().map(|param| (param.id.clone(), typ.clone())));
-                }
-
-                let new_type = types::walk_move_type_opt(
-                    typ,
-                    &mut types::ControlVisitation(|typ: &ArcType| self.generalize_type(typ)),
-                );
-                match **typ {
-                    Type::Generic(ref generic)
-                        if self.type_variables.get(&generic.id).is_none() =>
-                    {
-                        self.unbound_variables
-                            .insert(generic.id.clone(), generic.clone());
-                    }
-                    _ => (),
-                }
-                new_type
-                    .map(|t| unroll_typ(&t).unwrap_or(t))
-                    .or_else(|| replacement.clone())
-            }
-        }
-    }
-}
-
-struct TypeVariableGenerator {
-    map: FnvSet<Symbol>,
-    level: u32,
-    name: String,
-    i: u32,
-}
-
-impl TypeVariableGenerator {
-    fn new(level: u32, subs: &Substitution<ArcType>, typ: &ArcType) -> TypeVariableGenerator {
-        fn gather_foralls(map: &mut FnvSet<Symbol>, subs: &Substitution<ArcType>, typ: &ArcType) {
-            let typ = subs.real(typ);
-            if let Type::Forall(ref params, _, _) = **typ {
-                map.extend(params.iter().map(|param| param.id.clone()));
-            }
-            types::walk_move_type_opt(
-                typ,
-                &mut types::ControlVisitation(|typ: &ArcType| {
-                    gather_foralls(map, subs, typ);
-                    None
-                }),
-            );
-        }
-        let mut map = FnvSet::default();
-        gather_foralls(&mut map, subs, typ);
-        TypeVariableGenerator {
-            map,
-            name: "".to_string(),
-            i: 0,
-            level,
-        }
-    }
-    /// Generate a generic variable name which is not used in the current scope
-    fn next_variable(&mut self, tc: &mut Typecheck) -> Symbol {
-        let symbol = if self.name.is_empty() {
-            self.next_variable_(tc)
-        } else {
-            let name = format!("{}{}", self.name, self.i);
-            self.i += 1;
-            tc.symbols.symbol(&name[..])
-        };
-        self.map.insert(symbol.clone());
-        tc.type_variables.insert(
-            symbol.clone(),
-            Type::variable(TypeVariable {
-                id: self.level,
-                kind: tc.kind_cache.typ(),
-            }),
-        );
-        symbol
-    }
-
-    fn next_variable_(&mut self, tc: &mut Typecheck) -> Symbol {
-        for c in b'a'..(b'z' + 1) {
-            self.name.push(c as char);
-            let symbol = tc.symbols.symbol(&self.name[..]);
-            if !self.map.contains(&symbol) && tc.type_variables.get(&symbol).is_none() {
-                return symbol;
-            }
-            self.name.pop();
-        }
-        self.name.push('a');
-        self.next_variable_(tc)
-    }
-}
diff --git a/check/src/typecheck/generalize.rs b/check/src/typecheck/generalize.rs
new file mode 100644
index 00000000..732d9b6e
--- /dev/null
+++ b/check/src/typecheck/generalize.rs
@@ -0,0 +1,426 @@
+use crate::base::{
+    ast::{self, MutVisitor, SpannedExpr, SpannedIdent},
+    fnv::{FnvMap, FnvSet},
+    merge,
+    pos::{BytePos, Span},
+    symbol::Symbol,
+    types::{self, AppVec, ArcType, BuiltinType, Field, Generic, Type},
+};
+
+use crate::{
+    substitution::{is_variable_unified, Substitution},
+    typecheck::{TypeError, Typecheck},
+};
+
+pub(crate) struct TypeGeneralizer<'a, 'b: 'a> {
+    level: u32,
+    unbound_variables: FnvMap<Symbol, Generic<Symbol>>,
+    variable_generator: TypeVariableGenerator,
+    tc: &'a mut Typecheck<'b>,
+    context: ArcType,
+    span: Span<BytePos>,
+}
+
+impl<'a, 'b> ::std::ops::Deref for TypeGeneralizer<'a, 'b> {
+    type Target = Typecheck<'b>;
+    fn deref(&self) -> &Typecheck<'b> {
+        self.tc
+    }
+}
+
+impl<'a, 'b> ::std::ops::DerefMut for TypeGeneralizer<'a, 'b> {
+    fn deref_mut(&mut self) -> &mut Typecheck<'b> {
+        self.tc
+    }
+}
+
+impl<'a, 'b> TypeGeneralizer<'a, 'b> {
+    pub(crate) fn new(
+        level: u32,
+        tc: &'a mut Typecheck<'b>,
+        typ: &ArcType,
+        span: Span<BytePos>,
+    ) -> TypeGeneralizer<'a, 'b> {
+        TypeGeneralizer {
+            level,
+            unbound_variables: FnvMap::default(),
+            variable_generator: TypeVariableGenerator::new(&tc.subs, typ),
+            tc,
+            context: typ.clone(),
+            span,
+        }
+    }
+
+    /// Generalizing updates all variables which are above `level` into "generic variables". A
+    /// generic variable is instantiated with a fresh type variable each time it is refered to.
+    ///
+    /// Generalzing is a crucial part when inferring types as types will otherwise be less general
+    /// than they need to. Consider the following expression.
+    /// ```f#
+    /// let id x = x
+    /// in id 2
+    /// ```
+    /// If the variable in `id` was not generalized before the `id 2` call the variable would be
+    /// unified to an `Int` which is not what we want. Generalazing before checking the body of the
+    /// `let` basically infers that the variables in `id` does not refer to anything outside the
+    /// `let` scope and can thus be "generalized" into `a -> a` which is instantiated with a fresh
+    /// type variable in the `id 2` call.
+    pub(crate) fn generalize_variables<'i>(
+        &mut self,
+        args: &mut Iterator<Item = &'i mut SpannedIdent<Symbol>>,
+        expr: &mut SpannedExpr<Symbol>,
+    ) {
+        self.tc.type_variables.enter_scope();
+
+        // Replaces all type variables with their inferred types
+        struct ReplaceVisitor<'a: 'c, 'b: 'a, 'c> {
+            generalizer: &'c mut TypeGeneralizer<'a, 'b>,
+        }
+
+        impl<'a, 'b, 'c, 'd> MutVisitor<'d> for ReplaceVisitor<'a, 'b, 'c> {
+            type Ident = Symbol;
+
+            fn visit_expr(&mut self, e: &'d mut SpannedExpr<Self::Ident>) {
+                self.generalizer.tc.type_variables.enter_scope();
+                self.generalizer.span = e.span;
+                ast::walk_mut_expr(self, e);
+                self.generalizer.tc.type_variables.exit_scope();
+            }
+
+            fn visit_spanned_typed_ident(&mut self, id: &mut SpannedIdent<Symbol>) {
+                self.generalizer.span = id.span;
+                self.visit_ident(&mut id.value)
+            }
+            fn visit_typ(&mut self, typ: &mut ArcType) {
+                {
+                    let type_cache = &self.generalizer.tc.type_cache;
+                    self.generalizer.tc.type_variables.extend(
+                        typ.forall_params()
+                            .map(|param| (param.id.clone(), type_cache.hole())),
+                    );
+                }
+                if let Some(finished) = self.generalizer.generalize_type(typ) {
+                    *typ = finished;
+                }
+            }
+        }
+
+        {
+            let mut visitor = ReplaceVisitor { generalizer: self };
+            visitor.visit_expr(expr);
+            for arg in &mut *args {
+                visitor.visit_typ(&mut arg.value.typ)
+            }
+        }
+
+        self.tc.type_variables.exit_scope();
+    }
+
+    pub(crate) fn generalize_type_top(&mut self, typ: &mut ArcType) {
+        self.tc.type_variables.enter_scope();
+
+        let mut result_type = self.generalize_type(typ);
+
+        self.tc.type_variables.exit_scope();
+
+        if result_type.is_none() && !self.unbound_variables.is_empty() {
+            result_type = Some(typ.clone());
+        }
+
+        result_type = result_type.map(|typ| {
+            let mut params = self
+                .unbound_variables
+                .drain()
+                .map(|(_, generic)| generic)
+                .collect::<Vec<_>>();
+            params.sort_unstable_by(|l, r| l.id.declared_name().cmp(r.id.declared_name()));
+
+            Type::forall(params, typ)
+        });
+        if let Some(finished) = result_type {
+            *typ = finished;
+        }
+        debug!("End generalize {}", typ);
+    }
+
+    pub(crate) fn generalize_type(&mut self, typ: &ArcType) -> Option<ArcType> {
+        let replacement = self.subs.replace_variable(typ);
+        let mut typ = typ;
+        if let Some(ref t) = replacement {
+            typ = t;
+        }
+        match **typ {
+            Type::Variable(ref var) if self.subs.get_level(var.id) >= self.level => {
+                // Create a prefix if none exists
+                let id = self.variable_generator.next_variable(self.tc);
+
+                let gen: ArcType = Type::generic(Generic::new(id.clone(), var.kind.clone()));
+                debug!("Gen {} to {}", var.id, gen);
+                self.subs.insert(var.id, gen.clone());
+
+                self.unbound_variables
+                    .insert(id.clone(), Generic::new(id, var.kind.clone()));
+
+                Some(gen)
+            }
+
+            Type::Forall(ref params, ref typ, Some(ref vars)) => {
+                trace!("Generalize `{}` {:?}", typ, vars);
+
+                let mut new_params = Vec::new();
+                let typ = {
+                    let subs = &self.tc.subs;
+                    self.tc.named_variables.clear();
+                    for (param, var) in params.iter().zip(vars) {
+                        if is_variable_unified(subs, var) {
+                            self.tc
+                                .named_variables
+                                .insert(param.id.clone(), var.clone());
+                        } else {
+                            new_params.push(param.clone());
+                        }
+                    }
+
+                    if self.tc.named_variables.is_empty() {
+                        typ.clone()
+                    } else {
+                        typ.instantiate_generics_(&mut self.tc.named_variables)
+                            .unwrap_or(typ.clone())
+                    }
+                };
+
+                self.type_variables.enter_scope();
+                self.type_variables.extend(
+                    params
+                        .iter()
+                        .zip(vars)
+                        .map(|(param, var)| (param.id.clone(), var.clone())),
+                );
+
+                trace!("Generalize forall => `{}`", typ);
+
+                let new_type = self.generalize_type(&typ);
+                self.type_variables.exit_scope();
+
+                Some(Type::forall(
+                    new_params,
+                    new_type.unwrap_or_else(|| typ.clone()),
+                ))
+            }
+
+            Type::Skolem(ref skolem) => {
+                let in_scope = self.type_variables.contains_key(&skolem.name);
+                if !in_scope {
+                    self.tc.error(
+                        self.span,
+                        TypeError::Message(format!(
+                            "Skolem variable `{}` would escape as it is not bound in `{}`",
+                            skolem.name, self.context
+                        )),
+                    );
+                }
+                if self.subs.get_level(skolem.id) >= self.level {
+                    let generic = Generic {
+                        id: skolem.name.clone(),
+                        kind: skolem.kind.clone(),
+                    };
+
+                    if !in_scope {
+                        self.unbound_variables
+                            .insert(generic.id.clone(), generic.clone());
+                    }
+
+                    Some(Type::generic(generic))
+                } else {
+                    replacement
+                }
+            }
+
+            _ => {
+                if let Type::Forall(ref params, _, None) = **typ {
+                    let type_cache = &self.tc.type_cache;
+                    self.tc.type_variables.extend(
+                        params
+                            .iter()
+                            .map(|param| (param.id.clone(), type_cache.hole())),
+                    );
+                }
+
+                let new_type = types::walk_move_type_opt(
+                    typ,
+                    &mut types::ControlVisitation(|typ: &ArcType| self.generalize_type(typ)),
+                );
+                match **typ {
+                    Type::Generic(ref generic)
+                        if self.type_variables.get(&generic.id).is_none() =>
+                    {
+                        self.unbound_variables
+                            .insert(generic.id.clone(), generic.clone());
+                    }
+                    _ => (),
+                }
+                new_type
+                    .map(|t| unroll_typ(&t).unwrap_or(t))
+                    .or_else(|| replacement.clone())
+            }
+        }
+    }
+}
+
+struct TypeVariableGenerator {
+    map: FnvSet<Symbol>,
+    name: String,
+    i: u32,
+}
+
+impl TypeVariableGenerator {
+    fn new(subs: &Substitution<ArcType>, typ: &ArcType) -> TypeVariableGenerator {
+        fn gather_foralls(map: &mut FnvSet<Symbol>, subs: &Substitution<ArcType>, typ: &ArcType) {
+            let typ = subs.real(typ);
+            if let Type::Forall(ref params, _, _) = **typ {
+                map.extend(params.iter().map(|param| param.id.clone()));
+            }
+            types::walk_move_type_opt(
+                typ,
+                &mut types::ControlVisitation(|typ: &ArcType| {
+                    gather_foralls(map, subs, typ);
+                    None
+                }),
+            );
+        }
+        let mut map = FnvSet::default();
+        gather_foralls(&mut map, subs, typ);
+        TypeVariableGenerator {
+            map,
+            name: "".to_string(),
+            i: 0,
+        }
+    }
+    /// Generate a generic variable name which is not used in the current scope
+    fn next_variable(&mut self, tc: &mut Typecheck) -> Symbol {
+        let symbol = if self.name.is_empty() {
+            self.next_variable_(tc)
+        } else {
+            let name = format!("{}{}", self.name, self.i);
+            self.i += 1;
+            tc.symbols.symbol(&name[..])
+        };
+        self.map.insert(symbol.clone());
+        tc.type_variables.insert(symbol.clone(), Type::hole());
+        symbol
+    }
+
+    fn next_variable_(&mut self, tc: &mut Typecheck) -> Symbol {
+        for c in b'a'..(b'z' + 1) {
+            self.name.push(c as char);
+            let symbol = tc.symbols.symbol(&self.name[..]);
+            if !self.map.contains(&symbol) && tc.type_variables.get(&symbol).is_none() {
+                return symbol;
+            }
+            self.name.pop();
+        }
+        self.name.push('a');
+        self.next_variable_(tc)
+    }
+}
+
+fn unroll_typ(typ: &ArcType) -> Option<ArcType> {
+    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
+            // an application that is identical to `typ`
+            match **l {
+                Type::App(..) => (),
+                _ => return None,
+            }
+            args.extend(rest.iter().rev().cloned());
+            l
+        }
+        _ => return unroll_record(typ),
+    };
+    while let Type::App(ref l, ref rest) = **current {
+        args.extend(rest.iter().rev().cloned());
+        current = l;
+    }
+    if args.is_empty() {
+        None
+    } else {
+        args.reverse();
+        match **current {
+            Type::Builtin(BuiltinType::Function) if args.len() == 2 => {
+                let ret = args.pop().unwrap();
+                Some(Type::function(args.into_iter().collect(), ret))
+            }
+            _ => Some(Type::app(current.clone(), args)),
+        }
+    }
+}
+
+fn unroll_record(typ: &Type<Symbol>) -> Option<ArcType> {
+    let mut new_types = Vec::new();
+    let mut new_fields = Vec::new();
+    let mut current = match *typ {
+        Type::ExtendRow {
+            ref types,
+            ref fields,
+            ref rest,
+        } => match **rest {
+            Type::ExtendRow { .. } => {
+                new_types.extend_from_slice(types);
+                new_fields.extend_from_slice(fields);
+                rest
+            }
+            _ => return None,
+        },
+        _ => return None,
+    };
+    while let Type::ExtendRow {
+        ref types,
+        ref fields,
+        ref rest,
+    } = **current
+    {
+        new_types.extend_from_slice(types);
+        new_fields.extend_from_slice(fields);
+        current = rest;
+    }
+    if new_types.is_empty() && new_fields.is_empty() {
+        None
+    } else {
+        Some(Type::extend_row(new_types, new_fields, current.clone()))
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn unroll_typ_test() {
+        let i: ArcType = Type::int();
+        let s: ArcType = Type::string();
+        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(), collect![i.clone()]),
+                collect![s.clone()]
+            )),
+            Some(Type::function(collect![i.clone()], s.clone()))
+        );
+    }
+}
diff --git a/parser/src/grammar.lalrpop b/parser/src/grammar.lalrpop
index f4f661e0..d8b3626e 100644
--- a/parser/src/grammar.lalrpop
+++ b/parser/src/grammar.lalrpop
@@ -829,8 +829,8 @@ pub TopExpr: SpannedExpr<Id> = {
     "shebang line"? <expr: SpExpr> SkipExtraTokens => expr,
 };
 
-pub ReplLine: Option<ReplLine<Id>> = {
-    <TopExpr> => Some(ReplLine::Expr(<>)),
-    "block open" <PlainValueBinding> "block close" => Some(ReplLine::Let(<>)),
+pub ReplLine: Option<Box<ReplLine<Id>>> = {
+    <TopExpr> => Some(Box::new(ReplLine::Expr(<>))),
+    "block open" <PlainValueBinding> "block close" => Some(Box::new(ReplLine::Let(<>))),
     => None,
 };
diff --git a/parser/src/lib.rs b/parser/src/lib.rs
index 73d25f55..2d49cd28 100644
--- a/parser/src/lib.rs
+++ b/parser/src/lib.rs
@@ -48,6 +48,7 @@ lalrpop_mod!(
 
 pub mod infix;
 mod layout;
+mod str_suffix;
 mod token;
 
 fn new_ident<Id>(type_cache: &TypeCache<Id, ArcType<Id>>, name: Id) -> TypedIdent<Id> {
@@ -475,6 +476,7 @@ where
 
     match result {
         Ok(repl_line) => {
+            let repl_line = repl_line.map(|b| *b);
             if parse_errors.has_errors() {
                 Err((repl_line, transform_errors(input.span(), parse_errors)))
             } else {
diff --git a/parser/src/str_suffix.rs b/parser/src/str_suffix.rs
new file mode 100644
index 00000000..26377882
--- /dev/null
+++ b/parser/src/str_suffix.rs
@@ -0,0 +1,122 @@
+#![allow(unused)]
+
+use std::{mem, str};
+
+/// Str-like type where the first 0-2 bytes may point into a UTF-8 characters but all bytes
+/// following those are guaranteed to represent a valid UTF-8 string (`str`). Relying on this
+/// property we can iterate over the `StrSuffix` byte-by-byte as we would on a `[u8]` without
+/// needing an expensive validation when going back to a `str` as checking any part of a
+/// `StrSuffix` for UTF-8-ness only requires a char boundary check (same as a slicing a `str`).
+#[repr(transparent)]
+pub struct StrSuffix([u8]);
+
+impl StrSuffix {
+    pub fn new(s: &str) -> &Self {
+        unsafe { mem::transmute(s.as_bytes()) }
+    }
+
+    pub fn len(&self) -> usize {
+        self.0.len()
+    }
+
+    pub fn is_empty(&self) -> bool {
+        self.0.is_empty()
+    }
+
+    pub fn first(&self) -> Option<u8> {
+        self.0.first().cloned()
+    }
+
+    pub fn split_first(&self) -> Option<(u8, &Self)> {
+        if self.is_empty() {
+            None
+        } else {
+            Some((self.0[0], self.suffix(1)))
+        }
+    }
+
+    pub fn try_as_str(&self) -> Option<&str> {
+        self.get(0)
+    }
+
+    fn get(&self, index: usize) -> Option<&str> {
+        if self.is_char_boundary(index) {
+            Some(unsafe { str::from_utf8_unchecked(&self.0) })
+        } else {
+            None
+        }
+    }
+
+    #[inline(always)]
+    fn is_char_boundary_byte(b: u8) -> bool {
+        // This is bit magic equivalent to: b < 128 || b >= 192
+        (b as i8) >= -0x40
+    }
+
+    fn is_char_boundary(&self, index: usize) -> bool {
+        // From std::str::is_char_boundary
+        if index == 0 || index == self.len() {
+            return true;
+        }
+        match self.as_bytes().get(index) {
+            None => false,
+            Some(&b) => Self::is_char_boundary_byte(b),
+        }
+    }
+
+    fn bytes_prefix(&self) -> &[u8] {
+        for i in 0..(self.len().min(3)) {
+            if Self::is_char_boundary_byte(self.0[i]) {
+                return &self.0[..i];
+            }
+        }
+        &self.0[..0]
+    }
+
+    pub fn restore_char(&self, prefix: &[u8]) -> char {
+        assert!(prefix.len() <= 4);
+        let mut buf = [0; 4];
+        buf[..prefix.len()].copy_from_slice(prefix);
+        let suffix = self.bytes_prefix();
+        buf[prefix.len()..(prefix.len() + suffix.len())].copy_from_slice(suffix);
+        str::from_utf8(&buf)
+            .expect("UTF-8 string")
+            .chars()
+            .next()
+            .expect("char")
+    }
+
+    fn suffix(&self, index: usize) -> &Self {
+        // Any suffix of a StrSuffix is a valid StrSuffix
+        unsafe { mem::transmute(&self.0[index..]) }
+    }
+
+    pub fn as_bytes(&self) -> &[u8] {
+        &self.0
+    }
+
+    pub fn iter(&self) -> Iter {
+        Iter(self)
+    }
+}
+
+pub struct Iter<'a>(&'a StrSuffix);
+
+impl<'a> Iterator for Iter<'a> {
+    type Item = u8;
+
+    fn next(&mut self) -> Option<u8> {
+        if let Some((b, rest)) = self.0.split_first() {
+            self.0 = rest;
+            Some(b)
+        } else {
+            None
+        }
+    }
+}
+
+impl<'a> Iter<'a> {
+    pub fn as_str_suffix(&self) -> &'a StrSuffix {
+        self.0
+    }
+}
diff --git a/parser/src/token.rs b/parser/src/token.rs
index 1426c9a5..3864485f 100644
--- a/parser/src/token.rs
+++ b/parser/src/token.rs
@@ -1,13 +1,15 @@
-use crate::base::ast::is_operator_char;
+use crate::base::ast::is_operator_byte;
 use crate::base::metadata::{Comment, CommentType};
 use crate::base::pos::{self, BytePos, Column, Line, Location, Spanned};
-use std::fmt;
-use std::str::Chars;
+
+use std::{fmt, str};
 
 use codespan::ByteOffset;
 
 use self::Error::*;
 
+use crate::str_suffix::{self, StrSuffix};
+
 #[derive(Clone, PartialEq, Debug)]
 pub enum Token<'input> {
     ShebangLine(&'input str),
@@ -173,33 +175,33 @@ fn error<T>(location: Location, code: Error) -> Result<T, SpError> {
     Err(pos::spanned2(location, location, code))
 }
 
-fn is_ident_start(ch: char) -> bool {
+fn is_ident_start(ch: u8) -> bool {
     // TODO: Unicode?
     match ch {
-        '_' | 'a'...'z' | 'A'...'Z' => true,
+        b'_' | b'a'...b'z' | b'A'...b'Z' => true,
         _ => false,
     }
 }
 
-fn is_ident_continue(ch: char) -> bool {
+fn is_ident_continue(ch: u8) -> bool {
     // TODO: Unicode?
     match ch {
-        '0'...'9' | '\'' => true,
+        b'0'...b'9' | b'\'' => true,
         ch => is_ident_start(ch),
     }
 }
 
-fn is_digit(ch: char) -> bool {
-    ch.is_digit(10)
+fn is_digit(ch: u8) -> bool {
+    (ch as char).is_digit(10)
 }
 
-fn is_hex(ch: char) -> bool {
-    ch.is_digit(16)
+fn is_hex(ch: u8) -> bool {
+    (ch as char).is_digit(16)
 }
 
 struct CharLocations<'input> {
     location: Location,
-    chars: Chars<'input>,
+    chars: str_suffix::Iter<'input>,
 }
 
 impl<'input> CharLocations<'input> {
@@ -213,18 +215,18 @@ impl<'input> CharLocations<'input> {
                 column: Column::from(1),
                 absolute: input.start_index(),
             },
-            chars: input.src().chars(),
+            chars: StrSuffix::new(input.src()).iter(),
         }
     }
 }
 
 impl<'input> Iterator for CharLocations<'input> {
-    type Item = (Location, char);
+    type Item = (Location, u8);
 
-    fn next(&mut self) -> Option<(Location, char)> {
+    fn next(&mut self) -> Option<(Location, u8)> {
         self.chars.next().map(|ch| {
             let location = self.location;
-            self.location = self.location.shift(ch);
+            self.location.shift(ch);
             // HACK: The layout algorithm expects `1` indexing for columns -
             // this could be altered in the future though
             if self.location.column == Column::from(0) {
@@ -238,7 +240,6 @@ impl<'input> Iterator for CharLocations<'input> {
 pub struct Tokenizer<'input> {
     input: &'input str,
     chars: CharLocations<'input>,
-    lookahead: Option<(Location, char)>,
     start_index: BytePos,
 }
 
@@ -247,24 +248,25 @@ impl<'input> Tokenizer<'input> {
     where
         S: ?Sized + crate::ParserSource,
     {
-        let mut chars = CharLocations::new(input);
+        let chars = CharLocations::new(input);
 
         Tokenizer {
             input: input.src(),
-            lookahead: chars.next(),
-            chars: chars,
+            chars,
             start_index: input.start_index(),
         }
     }
 
-    fn bump(&mut self) -> Option<(Location, char)> {
-        match self.lookahead {
-            Some((location, ch)) => {
-                self.lookahead = self.chars.next();
-                Some((location, ch))
-            }
-            None => None,
-        }
+    fn bump(&mut self) -> Option<(Location, u8)> {
+        self.chars.next()
+    }
+
+    fn lookahead(&self) -> Option<(Location, u8)> {
+        self.chars
+            .chars
+            .as_str_suffix()
+            .first()
+            .map(|b| (self.chars.location, b))
     }
 
     fn skip_to_end(&mut self) {
@@ -277,7 +279,9 @@ impl<'input> Tokenizer<'input> {
     }
 
     fn next_loc(&self) -> Location {
-        self.lookahead.as_ref().map_or(self.chars.location, |l| l.0)
+        self.lookahead()
+            .as_ref()
+            .map_or(self.chars.location, |l| l.0)
     }
 
     fn eof_error<T>(&mut self) -> Result<T, SpError> {
@@ -294,16 +298,16 @@ impl<'input> Tokenizer<'input> {
 
     fn take_while<F>(&mut self, start: Location, mut keep_going: F) -> (Location, &'input str)
     where
-        F: FnMut(char) -> bool,
+        F: FnMut(u8) -> bool,
     {
         self.take_until(start, |c| !keep_going(c))
     }
 
     fn take_until<F>(&mut self, start: Location, mut terminate: F) -> (Location, &'input str)
     where
-        F: FnMut(char) -> bool,
+        F: FnMut(u8) -> bool,
     {
-        while let Some((end, ch)) = self.lookahead {
+        while let Some((end, ch)) = self.lookahead() {
             if terminate(ch) {
                 return (end, self.slice(start, end));
             } else {
@@ -315,13 +319,13 @@ impl<'input> Tokenizer<'input> {
 
     fn test_lookahead<F>(&self, mut test: F) -> bool
     where
-        F: FnMut(char) -> bool,
+        F: FnMut(u8) -> bool,
     {
-        self.lookahead.map_or(false, |(_, ch)| test(ch))
+        self.lookahead().map_or(false, |(_, ch)| test(ch))
     }
 
     fn line_comment(&mut self, start: Location) -> Option<SpannedToken<'input>> {
-        let (end, comment) = self.take_until(start, |ch| ch == '\n');
+        let (end, comment) = self.take_until(start, |ch| ch == b'\n');
 
         if comment.starts_with("///") {
             let skip = if comment.starts_with("/// ") { 4 } else { 3 };
@@ -336,13 +340,13 @@ impl<'input> Tokenizer<'input> {
     }
 
     fn block_comment(&mut self, start: Location) -> Result<Option<SpannedToken<'input>>, SpError> {
-        self.bump(); // Skip first '*'
+        self.bump(); // Skip first b'*'
 
         loop {
-            let (_, comment) = self.take_until(start, |ch| ch == '*');
-            self.bump(); // Skip next '*'
-            match self.lookahead {
-                Some((_, '/')) => {
+            let (_, comment) = self.take_until(start, |ch| ch == b'*');
+            self.bump(); // Skip next b'*'
+            match self.lookahead() {
+                Some((_, b'/')) => {
                     self.bump();
                     let end = self.next_loc();
                     if comment.starts_with("/**") && comment != "/**" {
@@ -363,7 +367,7 @@ impl<'input> Tokenizer<'input> {
     }
 
     fn operator(&mut self, start: Location) -> SpannedToken<'input> {
-        let (end, op) = self.take_while(start, is_operator_char);
+        let (end, op) = self.take_while(start, is_operator_byte);
 
         let token = match op {
             "@" => Token::At,
@@ -376,7 +380,7 @@ impl<'input> Tokenizer<'input> {
             "#" => {
                 // Is this too permissive?
                 self.take_while(start, is_ident_start);
-                let (_, op) = self.take_while(start, is_operator_char);
+                let (_, op) = self.take_while(start, is_operator_byte);
                 Token::Operator(op)
             }
             op => Token::Operator(op),
@@ -385,33 +389,41 @@ impl<'input> Tokenizer<'input> {
         pos::spanned2(start, end, token)
     }
 
-    fn escape_code(&mut self) -> Result<char, SpError> {
+    fn escape_code(&mut self) -> Result<u8, SpError> {
         match self.bump() {
-            Some((_, '\'')) => Ok('\''),
-            Some((_, '"')) => Ok('"'),
-            Some((_, '\\')) => Ok('\\'),
-            Some((_, '/')) => Ok('/'),
-            Some((_, 'n')) => Ok('\n'),
-            Some((_, 'r')) => Ok('\r'),
-            Some((_, 't')) => Ok('\t'),
+            Some((_, b'\'')) => Ok(b'\''),
+            Some((_, b'"')) => Ok(b'"'),
+            Some((_, b'\\')) => Ok(b'\\'),
+            Some((_, b'/')) => Ok(b'/'),
+            Some((_, b'n')) => Ok(b'\n'),
+            Some((_, b'r')) => Ok(b'\r'),
+            Some((_, b't')) => Ok(b'\t'),
             // TODO: Unicode escape codes
-            Some((start, ch)) => self.error(start, UnexpectedEscapeCode(ch)),
+            Some((start, ch)) => {
+                let ch = self.chars.chars.as_str_suffix().restore_char(&[ch]);
+                self.error(start, UnexpectedEscapeCode(ch))
+            }
             None => self.eof_error(),
         }
     }
 
     fn string_literal(&mut self, start: Location) -> Result<SpannedToken<'input>, SpError> {
         let mut string = String::new();
-
-        while let Some((_, ch)) = self.bump() {
-            match ch {
-                '\\' => string.push(self.escape_code()?),
-                '"' => {
+        loop {
+            let content_start = self.next_loc();
+            let (_end, s) = self.take_until(content_start, |b| b == b'"' || b == b'\\');
+            string.push_str(s);
+            match self.bump() {
+                Some((_, b'\\')) => {
+                    string.push(self.escape_code()? as char);
+                }
+                Some((_, b'"')) => {
                     let end = self.next_loc();
+
                     let token = Token::StringLiteral(string);
                     return Ok(pos::spanned2(start, end, token));
                 }
-                ch => string.push(ch),
+                _ => break,
             }
         }
 
@@ -419,39 +431,39 @@ impl<'input> Tokenizer<'input> {
     }
 
     fn raw_string_literal(&mut self, start: Location) -> Result<SpannedToken<'input>, SpError> {
-        let mut string = String::new();
-
         let mut delimiters = 0;
         while let Some((_, ch)) = self.bump() {
             match ch {
-                '#' => delimiters += 1,
-                '"' => break,
+                b'#' => delimiters += 1,
+                b'"' => break,
                 _ => return self.error(start, InvalidRawStringDelimiter),
             }
         }
 
-        while let Some((_, ch)) = self.bump() {
-            match ch {
-                '"' => {
-                    string.push(ch);
+        let content_start = self.next_loc();
+        loop {
+            self.take_until(content_start, |b| b == b'"');
+            match self.bump() {
+                Some((_, b'"')) => {
                     let mut found_delimiters = 0;
                     while let Some((_, ch)) = self.bump() {
-                        string.push(ch);
                         match ch {
-                            '#' => found_delimiters += 1,
-                            '"' => found_delimiters = 0,
+                            b'#' => found_delimiters += 1,
+                            b'"' => found_delimiters = 0,
                             _ => break,
                         }
                         if found_delimiters == delimiters {
-                            let real_string_len = string.len() - 1 - delimiters;
-                            string.truncate(real_string_len);
                             let end = self.next_loc();
+                            let mut content_end = end;
+                            content_end.absolute.0 -= delimiters + 1;
+                            let string = self.slice(content_start, content_end).into();
+
                             let token = Token::StringLiteral(string);
                             return Ok(pos::spanned2(start, end, token));
                         }
                     }
                 }
-                ch => string.push(ch),
+                _ => break,
             }
         }
 
@@ -459,7 +471,7 @@ impl<'input> Tokenizer<'input> {
     }
 
     fn shebang_line(&mut self, start: Location) -> Option<SpannedToken<'input>> {
-        let (end, line) = self.take_until(start, |ch| ch == '\n');
+        let (end, line) = self.take_until(start, |ch| ch == b'\n');
 
         if line.starts_with("#!") {
             let skip = 2;
@@ -473,18 +485,21 @@ impl<'input> Tokenizer<'input> {
 
     fn char_literal(&mut self, start: Location) -> Result<SpannedToken<'input>, SpError> {
         let ch = match self.bump() {
-            Some((_, '\\')) => self.escape_code()?,
-            Some((_, '\'')) => return self.error(start, EmptyCharLiteral),
+            Some((_, b'\\')) => self.escape_code()?,
+            Some((_, b'\'')) => return self.error(start, EmptyCharLiteral),
             Some((_, ch)) => ch,
             None => return self.eof_error(),
         };
 
         match self.bump() {
-            Some((_, '\'')) => Ok(pos::spanned2(
-                start,
-                self.next_loc(),
-                Token::CharLiteral(ch),
-            )),
+            Some((_, b'\'')) => {
+                let ch = self.chars.chars.as_str_suffix().restore_char(&[ch]);
+                Ok(pos::spanned2(
+                    start,
+                    self.next_loc(),
+                    Token::CharLiteral(ch),
+                ))
+            }
             Some((_, _)) => self.error(start, UnterminatedCharLiteral), // UnexpectedEscapeCode?
             None => self.eof_error(),
         }
@@ -493,24 +508,26 @@ impl<'input> Tokenizer<'input> {
     fn numeric_literal(&mut self, start: Location) -> Result<SpannedToken<'input>, SpError> {
         let (end, int) = self.take_while(start, is_digit);
 
-        let (start, end, token) = match self.lookahead {
-            Some((_, '.')) => {
-                self.bump(); // Skip '.'
+        let (start, end, token) = match self.lookahead() {
+            Some((_, b'.')) => {
+                self.bump(); // Skip b'.'
                 let (end, float) = self.take_while(start, is_digit);
-                match self.lookahead {
+                match self.lookahead() {
                     Some((_, ch)) if is_ident_start(ch) => {
+                        let ch = self.chars.chars.as_str_suffix().restore_char(&[ch]);
                         return self.error(end, UnexpectedChar(ch));
                     }
                     _ => (start, end, Token::FloatLiteral(float.parse().unwrap())),
                 }
             }
-            Some((_, 'x')) => {
-                self.bump(); // Skip 'x'
+            Some((_, b'x')) => {
+                self.bump(); // Skip b'x'
                 let int_start = self.next_loc();
                 let (end, hex) = self.take_while(int_start, is_hex);
                 match int {
-                    "0" | "-0" => match self.lookahead {
+                    "0" | "-0" => match self.lookahead() {
                         Some((_, ch)) if is_ident_start(ch) => {
+                            let ch = self.chars.chars.as_str_suffix().restore_char(&[ch]);
                             return self.error(end, UnexpectedChar(ch));
                         }
                         _ => {
@@ -527,11 +544,12 @@ impl<'input> Tokenizer<'input> {
                     _ => return self.error(start, HexLiteralWrongPrefix),
                 }
             }
-            Some((_, 'b')) => {
-                self.bump(); // Skip 'b'
+            Some((_, b'b')) => {
+                self.bump(); // Skip b'b'
                 let end = self.next_loc();
-                match self.lookahead {
+                match self.lookahead() {
                     Some((pos, ch)) if is_ident_start(ch) => {
+                        let ch = self.chars.chars.as_str_suffix().restore_char(&[ch]);
                         return self.error(pos, UnexpectedChar(ch));
                     }
                     _ => {
@@ -543,7 +561,10 @@ impl<'input> Tokenizer<'input> {
                     }
                 }
             }
-            Some((start, ch)) if is_ident_start(ch) => return self.error(start, UnexpectedChar(ch)),
+            Some((start, ch)) if is_ident_start(ch) => {
+                let ch = self.chars.chars.as_str_suffix().restore_char(&[ch]);
+                return self.error(start, UnexpectedChar(ch));
+            }
             None | Some(_) => {
                 if let Ok(val) = int.parse() {
                     (start, end, Token::IntLiteral(val))
@@ -558,8 +579,8 @@ impl<'input> Tokenizer<'input> {
 
     fn identifier(&mut self, start: Location) -> Result<SpannedToken<'input>, SpError> {
         let (mut end, mut ident) = self.take_while(start, is_ident_continue);
-        match self.lookahead {
-            Some((_, c)) if c == '!' => {
+        match self.lookahead() {
+            Some((_, c)) if c == b'!' => {
                 self.bump();
                 end.column += 1.into();
                 end.absolute += 1.into();
@@ -595,33 +616,33 @@ impl<'input> Iterator for Tokenizer<'input> {
     fn next(&mut self) -> Option<Result<SpannedToken<'input>, SpError>> {
         while let Some((start, ch)) = self.bump() {
             return match ch {
-                ',' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::Comma))),
-                '\\' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::Lambda))),
-                '{' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::LBrace))),
-                '[' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::LBracket))),
-                '(' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::LParen))),
-                '}' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::RBrace))),
-                ']' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::RBracket))),
-                ')' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::RParen))),
-                '?' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::Question))),
-
-                'r' if self.test_lookahead(|ch| ch == '"' || ch == '#') => {
+                b',' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::Comma))),
+                b'\\' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::Lambda))),
+                b'{' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::LBrace))),
+                b'[' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::LBracket))),
+                b'(' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::LParen))),
+                b'}' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::RBrace))),
+                b']' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::RBracket))),
+                b')' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::RParen))),
+                b'?' => Some(Ok(pos::spanned2(start, self.next_loc(), Token::Question))),
+
+                b'r' if self.test_lookahead(|ch| ch == b'"' || ch == b'#') => {
                     Some(self.raw_string_literal(start))
                 }
-                '"' => Some(self.string_literal(start)),
-                '\'' => Some(self.char_literal(start)),
+                b'"' => Some(self.string_literal(start)),
+                b'\'' => Some(self.char_literal(start)),
 
-                '/' if self.test_lookahead(|ch| ch == '/') => match self.line_comment(start) {
+                b'/' if self.test_lookahead(|ch| ch == b'/') => match self.line_comment(start) {
                     Some(token) => Some(Ok(token)),
                     None => continue,
                 },
-                '/' if self.test_lookahead(|ch| ch == '*') => match self.block_comment(start) {
+                b'/' if self.test_lookahead(|ch| ch == b'*') => match self.block_comment(start) {
                     Ok(Some(token)) => Some(Ok(token)),
                     Ok(None) => continue,
                     Err(err) => Some(Err(err)),
                 },
-                '#' if start.absolute == self.start_index
-                    && self.test_lookahead(|ch| ch == '!') =>
+                b'#' if start.absolute == self.start_index
+                    && self.test_lookahead(|ch| ch == b'!') =>
                 {
                     match self.shebang_line(start) {
                         Some(token) => Some(Ok(token)),
@@ -629,7 +650,7 @@ impl<'input> Iterator for Tokenizer<'input> {
                     }
                 }
 
-                '#' if self.test_lookahead(|ch| ch == '[') => {
+                b'#' if self.test_lookahead(|ch| ch == b'[') => {
                     self.bump();
                     Some(Ok(pos::spanned2(
                         start,
@@ -638,13 +659,16 @@ impl<'input> Iterator for Tokenizer<'input> {
                     )))
                 }
                 ch if is_ident_start(ch) => Some(self.identifier(start)),
-                ch if is_digit(ch) || (ch == '-' && self.test_lookahead(is_digit)) => {
+                ch if is_digit(ch) || (ch == b'-' && self.test_lookahead(is_digit)) => {
                     Some(self.numeric_literal(start))
                 }
-                ch if is_operator_char(ch) => Some(Ok(self.operator(start))),
-                ch if ch.is_whitespace() => continue,
+                ch if is_operator_byte(ch) => Some(Ok(self.operator(start))),
+                ch if (ch as char).is_whitespace() => continue, // TODO Unicode whitespace
 
-                ch => Some(self.error(start, UnexpectedChar(ch))),
+                ch => {
+                    let ch = self.chars.chars.as_str_suffix().restore_char(&[ch]);
+                    Some(self.error(start, UnexpectedChar(ch)))
+                }
             };
         }
         // Return EOF instead of None so that the layout algorithm receives the eof location
diff --git a/vm/src/compiler.rs b/vm/src/compiler.rs
index 78d476fb..d1a80879 100644
--- a/vm/src/compiler.rs
+++ b/vm/src/compiler.rs
@@ -6,7 +6,7 @@ use crate::base::resolve;
 use crate::base::scoped_map::ScopedMap;
 use crate::base::source::Source;
 use crate::base::symbol::{Symbol, SymbolModule, SymbolRef};
-use crate::base::types::{self, Alias, ArcType, BuiltinType, Type, TypeEnv};
+use crate::base::types::{Alias, ArcType, BuiltinType, Type, TypeEnv};
 use crate::core::{self, CExpr, Expr, Pattern};
 use crate::interner::InternedStr;
 use crate::source_map::{LocalMap, SourceMap};
@@ -205,7 +205,6 @@ impl FunctionEnvs {
 
     fn start_function(&mut self, compiler: &mut Compiler, args: VmIndex, id: Symbol, typ: ArcType) {
         compiler.stack_types.enter_scope();
-        compiler.stack_constructors.enter_scope();
         self.envs.push(FunctionEnv::new(
             args,
             id,
@@ -217,7 +216,6 @@ impl FunctionEnvs {
 
     fn end_function(&mut self, compiler: &mut Compiler, current_line: Option<Line>) -> FunctionEnv {
         compiler.stack_types.exit_scope();
-        compiler.stack_constructors.exit_scope();
         let instructions = self.function.instructions.len();
 
         if compiler.emit_debug_info {
@@ -431,7 +429,6 @@ pub struct Compiler<'a> {
     globals: &'a (CompilerEnv + 'a),
     vm: &'a GlobalVmState,
     symbols: SymbolModule<'a>,
-    stack_constructors: ScopedMap<Symbol, ArcType>,
     stack_types: ScopedMap<Symbol, Alias<Symbol, ArcType>>,
     source: &'a ::codespan::FileMap,
     source_name: String,
@@ -475,7 +472,6 @@ impl<'a> Compiler<'a> {
             vm: vm,
             empty_symbol: symbols.symbol(""),
             symbols: symbols,
-            stack_constructors: ScopedMap::new(),
             stack_types: ScopedMap::new(),
             source: source,
             source_name: source_name,
@@ -488,39 +484,21 @@ impl<'a> Compiler<'a> {
     }
 
     fn find(&self, id: &Symbol, current: &mut FunctionEnvs) -> Option<Variable<VmIndex>> {
-        self.stack_constructors
-            .iter()
-            .filter_map(|(_, typ)| match **typ {
-                Type::Variant(ref row) => row
-                    .row_iter()
-                    .enumerate()
-                    .find(|&(_, field)| field.name == *id),
-                _ => None,
-            })
-            .next()
-            .map(|(tag, field)| {
-                Constructor(
-                    tag as VmIndex,
-                    types::row_iter(&field.typ).count() as VmIndex,
-                )
-            })
+        current
+            .stack
+            .get(id)
+            .map(|&(index, _)| Stack(index))
             .or_else(|| {
-                current
-                    .stack
-                    .get(id)
-                    .map(|&(index, _)| Stack(index))
-                    .or_else(|| {
-                        let i = current.envs.len() - 1;
-                        let (rest, current) = current.envs.split_at_mut(i);
-                        rest.iter()
-                            .rev()
-                            .filter_map(|env| {
-                                env.stack
-                                    .get(id)
-                                    .map(|&(_, ref typ)| UpVar(current[0].upvar(id, typ)))
-                            })
-                            .next()
+                let i = current.envs.len() - 1;
+                let (rest, current) = current.envs.split_at_mut(i);
+                rest.iter()
+                    .rev()
+                    .filter_map(|env| {
+                        env.stack
+                            .get(id)
+                            .map(|&(_, ref typ)| UpVar(current[0].upvar(id, typ)))
                     })
+                    .next()
             })
             .or_else(|| {
                 self.globals
@@ -663,7 +641,6 @@ impl<'a> Compiler<'a> {
             },
             Expr::Ident(ref id, _) => self.load_identifier(&id.name, function)?,
             Expr::Let(ref let_binding, ref body) => {
-                self.stack_constructors.enter_scope();
                 let stack_start = function.stack_size;
                 // Index where the instruction to create the first closure should be at
                 let first_index = function.function.instructions.len();
@@ -867,7 +844,6 @@ impl<'a> Compiler<'a> {
                 // after the alternative
                 let mut end_jumps = Vec::new();
                 for (alt, &start_index) in alts.iter().zip(start_jumps.iter()) {
-                    self.stack_constructors.enter_scope();
                     function.stack.enter_scope();
                     match alt.pattern {
                         Pattern::Constructor(_, ref args) => {
@@ -896,7 +872,6 @@ impl<'a> Compiler<'a> {
                     }
                     self.compile(&alt.expr, function, tail_position)?;
                     let count = function.exit_scope(self);
-                    self.stack_constructors.exit_scope();
                     function.emit(Slide(count));
                     end_jumps.push(function.function.instructions.len());
                     function.emit(Jump(0));
@@ -1054,16 +1029,16 @@ impl<'a> Compiler<'a> {
                                 function.emit(Push(record_index));
                                 function.emit_field(self, &typ, &pattern_field.0.name)?;
 
-                                let field = typ
-                                    .row_iter()
-                                    .find(|field| field.name.name_eq(&pattern_field.0.name))
-                                    .expect("ICE: Record field does not exist");
                                 let field_name = pattern_field
                                     .1
                                     .as_ref()
                                     .unwrap_or(&pattern_field.0.name)
                                     .clone();
-                                function.new_stack_var(self, field_name, field.typ.clone());
+                                function.new_stack_var(
+                                    self,
+                                    field_name,
+                                    pattern_field.0.typ.clone(),
+                                );
                             }
                         } else {
                             function.emit(Split);
diff --git a/vm/src/core/mod.rs b/vm/src/core/mod.rs
index 6c990f0d..8e4ac49e 100644
--- a/vm/src/core/mod.rs
+++ b/vm/src/core/mod.rs
@@ -896,7 +896,7 @@ enum CType {
 
 use self::optimize::*;
 struct ReplaceVariables<'a, 'b> {
-    replacements: &'b HashMap<Symbol, Symbol>,
+    replacements: &'b FnvMap<Symbol, Symbol>,
     allocator: &'a Allocator<'a>,
 }
 
@@ -924,7 +924,7 @@ impl<'a, 'b> Visitor<'a, 'a> for ReplaceVariables<'a, 'b> {
 
 fn replace_variables<'a, 'b>(
     allocator: &'a Allocator<'a>,
-    replacements: &'b HashMap<Symbol, Symbol>,
+    replacements: &'b FnvMap<Symbol, Symbol>,
     expr: &'a Expr<'a>,
 ) -> &'a Expr<'a> {
     if replacements.is_empty() {
@@ -990,7 +990,7 @@ impl<'a, 'e> PatternTranslator<'a, 'e> {
                     .map(|equation| *equation.patterns.first().unwrap())
             };
 
-            let (pattern, replacements) = self.pattern_identifiers(first_iter());
+            let (core_pattern, replacements) = self.pattern_identifiers(first_iter());
 
             // Gather the inner patterns so we can prepend them to equations
             let temp = first_iter()
@@ -1000,22 +1000,41 @@ impl<'a, 'e> PatternTranslator<'a, 'e> {
                         ref fields,
                         ..
                     } => {
-                        let record_type = remove_aliases_cow(&self.0.env, typ);
-
+                        let mut record_type = None;
+                        // Core fields appear in the same order as the normal pattern so we can
+                        // get the types from it cheaply
+                        let core_fields = match &core_pattern {
+                            Pattern::Record(core_fields) => core_fields,
+                            _ => unreachable!(),
+                        };
                         fields
                             .iter()
-                            .map(|field| {
+                            .zip(core_fields)
+                            .map(|(field, core_field)| {
                                 field.value.as_ref().map(Cow::Borrowed).unwrap_or_else(|| {
-                                    let field_type = record_type
-                                        .row_iter()
-                                        .find(|f| f.name.name_eq(&field.name.value))
-                                        .map(|f| f.typ.clone())
-                                        .unwrap_or_else(|| Type::hole());
+                                    let typ = if field.name.value == core_field.0.name {
+                                        core_field.0.typ.clone()
+                                    } else {
+                                        // If the field has been renamed we need to go the slo path
+                                        // and do a lookup but this should be rare
+                                        if record_type.is_none() {
+                                            record_type =
+                                                Some(remove_aliases_cow(&self.0.env, typ));
+                                        }
+                                        record_type
+                                            .as_ref()
+                                            .unwrap()
+                                            .row_iter()
+                                            .find(|f| f.name.name_eq(&field.name.value))
+                                            .map(|f| f.typ.clone())
+                                            .unwrap_or_else(Type::hole)
+                                    };
+
                                     Cow::Owned(spanned(
                                         Span::default(),
                                         ast::Pattern::Ident(TypedIdent {
                                             name: field.name.value.clone(),
-                                            typ: field_type,
+                                            typ,
                                         }),
                                     ))
                                 })
@@ -1045,13 +1064,13 @@ impl<'a, 'e> PatternTranslator<'a, 'e> {
                 })
                 .collect::<Vec<_>>();
 
-            let new_variables = self.insert_new_variables(&pattern, variables);
+            let new_variables = self.insert_new_variables(&core_pattern, variables);
 
             let expr = self.translate(default, &new_variables, &new_equations);
             let expr = replace_variables(&self.0.allocator, &replacements, expr);
 
             Alternative {
-                pattern: pattern,
+                pattern: core_pattern,
                 expr: expr,
             }
         };
@@ -1211,7 +1230,9 @@ impl<'a, 'e> PatternTranslator<'a, 'e> {
         // // ==>
         // EXPR // with `y`s replaced by `x`
         match (&alt.pattern, variables[0]) {
-            (&Pattern::Ident(ref id), &Expr::Ident(ref expr_id, _)) => {
+            (&Pattern::Ident(ref id), &Expr::Ident(ref expr_id, _))
+                if !expr_id.name.is_global() =>
+            {
                 return replace_variables(
                     &self.0.allocator,
                     &collect![(id.name.clone(), expr_id.name.clone())],
@@ -1456,7 +1477,7 @@ impl<'a, 'e> PatternTranslator<'a, 'e> {
     // Gather all the identifiers of top level pattern of each of the `patterns` and create a core
     // pattern.
     // Nested patterns are ignored here.
-    fn pattern_identifiers<'b, 'p: 'b, I>(&self, patterns: I) -> (Pattern, HashMap<Symbol, Symbol>)
+    fn pattern_identifiers<'b, 'p: 'b, I>(&self, patterns: I) -> (Pattern, FnvMap<Symbol, Symbol>)
     where
         I: IntoIterator<Item = &'b SpannedPattern<Symbol>>,
     {
@@ -1466,7 +1487,7 @@ impl<'a, 'e> PatternTranslator<'a, 'e> {
     fn pattern_identifiers_<'b, 'p: 'b>(
         &self,
         patterns: &mut Iterator<Item = &'b SpannedPattern<Symbol>>,
-    ) -> (Pattern, HashMap<Symbol, Symbol>) {
+    ) -> (Pattern, FnvMap<Symbol, Symbol>) {
         let mut identifiers: Vec<TypedIdent<Symbol>> = Vec::new();
         let mut record_fields: Vec<(TypedIdent<Symbol>, _)> = Vec::new();
         let mut core_pattern = None;
@@ -1479,7 +1500,7 @@ impl<'a, 'e> PatternTranslator<'a, 'e> {
         let mut replacements = HashMap::default();
 
         fn add_duplicate_ident(
-            replacements: &mut HashMap<Symbol, Symbol>,
+            replacements: &mut FnvMap<Symbol, Symbol>,
             record_fields: &mut Vec<(TypedIdent<Symbol>, Option<Symbol>)>,
             field: &Symbol,
             pattern: Option<&SpannedPattern<Symbol>>,
@@ -1553,6 +1574,8 @@ impl<'a, 'e> PatternTranslator<'a, 'e> {
                     ref fields,
                     ..
                 } => {
+                    let typ = remove_aliases_cow(&self.0.env, typ);
+
                     for (i, field) in fields.iter().enumerate() {
                         if !add_duplicate_ident(
                             &mut replacements,
@@ -1564,7 +1587,7 @@ impl<'a, 'e> PatternTranslator<'a, 'e> {
                                 .value
                                 .as_ref()
                                 .map(|pattern| self.extract_ident(i, &pattern.value).name);
-                            let field_type = remove_aliases_cow(&self.0.env, typ)
+                            let field_type = typ
                                 .row_iter()
                                 .find(|f| f.name.name_eq(&field.name.value))
                                 .map(|f| f.typ.clone())
diff --git a/vm/src/lib.rs b/vm/src/lib.rs
index e02296f2..cbe2d900 100644
--- a/vm/src/lib.rs
+++ b/vm/src/lib.rs
@@ -96,7 +96,7 @@ use crate::base::symbol::Symbol;
 use crate::base::types::ArcType;
 use crate::stack::Stacktrace;
 use crate::thread::{RootedThread, RootedValue, Thread};
-use crate::types::VmIndex;
+use crate::types::{VmIndex, VmInt};
 use crate::value::{Value, ValueRepr};
 
 unsafe fn forget_lifetime<'a, 'b, T: ?Sized>(x: &'a T) -> &'b T {
@@ -118,6 +118,10 @@ impl<'a> Variants<'a> {
         Variants(value.get_repr(), PhantomData)
     }
 
+    pub(crate) fn int(i: VmInt) -> Self {
+        Variants(ValueRepr::Int(i), PhantomData)
+    }
+
     pub fn get_value(&self) -> Value {
         self.0.into()
     }
diff --git a/vm/src/stack.rs b/vm/src/stack.rs
index d1c59276..5cdc01f0 100644
--- a/vm/src/stack.rs
+++ b/vm/src/stack.rs
@@ -13,6 +13,16 @@ use crate::Variants;
 
 pub trait StackPrimitive {
     fn push_to(&self, stack: &mut Stack);
+
+    fn extend_to<'b, I>(iter: I, stack: &mut Stack)
+    where
+        I: IntoIterator<Item = &'b Self>,
+        Self: 'b,
+    {
+        for item in iter {
+            item.push_to(stack);
+        }
+    }
 }
 
 impl<'a, T: StackPrimitive + 'a> StackPrimitive for &'a T {
@@ -20,6 +30,14 @@ impl<'a, T: StackPrimitive + 'a> StackPrimitive for &'a T {
     fn push_to(&self, stack: &mut Stack) {
         (**self).push_to(stack)
     }
+
+    fn extend_to<'b, I>(iter: I, stack: &mut Stack)
+    where
+        I: IntoIterator<Item = &'b Self>,
+        Self: 'b,
+    {
+        StackPrimitive::extend_to(iter.into_iter().map(|i| *i), stack)
+    }
 }
 
 impl<'a> StackPrimitive for Variants<'a> {
@@ -27,6 +45,16 @@ impl<'a> StackPrimitive for Variants<'a> {
     fn push_to(&self, stack: &mut Stack) {
         self.0.push_to(stack)
     }
+
+    fn extend_to<'b, I>(iter: I, stack: &mut Stack)
+    where
+        I: IntoIterator<Item = &'b Self>,
+        Self: 'b,
+    {
+        stack
+            .values
+            .extend(iter.into_iter().map(|i| Value::from(i.0)))
+    }
 }
 
 impl StackPrimitive for ValueRepr {
@@ -34,6 +62,15 @@ impl StackPrimitive for ValueRepr {
     fn push_to(&self, stack: &mut Stack) {
         stack.values.push(Value::from(*self))
     }
+
+    fn extend_to<'b, I>(iter: I, stack: &mut Stack)
+    where
+        I: IntoIterator<Item = &'b Self>,
+    {
+        stack
+            .values
+            .extend(iter.into_iter().map(|i| Value::from(*i)))
+    }
 }
 
 impl StackPrimitive for Value {
@@ -41,6 +78,15 @@ impl StackPrimitive for Value {
     fn push_to(&self, stack: &mut Stack) {
         stack.values.push(Value::from(self.get_repr()))
     }
+
+    fn extend_to<'b, I>(iter: I, stack: &mut Stack)
+    where
+        I: IntoIterator<Item = &'b Self>,
+    {
+        stack
+            .values
+            .extend(iter.into_iter().map(|i| Value::from(i.get_repr())))
+    }
 }
 
 #[derive(Copy, Clone, Debug, PartialEq)]
@@ -266,9 +312,12 @@ impl Stack {
     }
 
     pub fn pop_many(&mut self, count: VmIndex) {
-        for _ in 0..count {
-            self.values.pop();
-        }
+        let len = self.values.len();
+        self.values.truncate(len - count as usize);
+    }
+
+    pub fn clear(&mut self) {
+        self.values.clear();
     }
 
     pub fn slide(&mut self, count: VmIndex) {
@@ -522,6 +571,11 @@ where
         self.stack.pop_many(count);
     }
 
+    pub fn clear(&mut self) {
+        let len = self.len();
+        self.stack.pop_many(len);
+    }
+
     pub fn slide(&mut self, count: VmIndex) {
         self.stack.slide(count);
     }
@@ -774,6 +828,31 @@ where
     }
 }
 
+impl<'c, T> Extend<&'c T> for Stack
+where
+    T: StackPrimitive + 'c,
+{
+    fn extend<I>(&mut self, iter: I)
+    where
+        I: IntoIterator<Item = &'c T>,
+    {
+        T::extend_to(iter, self)
+    }
+}
+
+impl<'b, 'c, T, S> Extend<&'c T> for StackFrame<'b, S>
+where
+    T: StackPrimitive + 'c,
+    S: StackState,
+{
+    fn extend<I>(&mut self, iter: I)
+    where
+        I: IntoIterator<Item = &'c T>,
+    {
+        T::extend_to(iter, &mut self.stack)
+    }
+}
+
 #[derive(Debug, PartialEq, Clone)]
 pub struct StacktraceFrame {
     pub name: Symbol,
diff --git a/vm/src/thread.rs b/vm/src/thread.rs
index a150985e..6d20abdc 100644
--- a/vm/src/thread.rs
+++ b/vm/src/thread.rs
@@ -314,9 +314,7 @@ impl<'b> Roots<'b> {
         let mut locks: Vec<(_, _, GcPtr<Thread>)> = Vec::new();
 
         let child_threads = self.vm.child_threads.read().unwrap();
-        for child in &*child_threads {
-            Vec::push(&mut stack, *child);
-        }
+        stack.extend(child_threads.iter().cloned());
 
         while let Some(thread_ptr) = stack.pop() {
             if locks.iter().any(|&(_, _, lock_thread)| {
@@ -327,9 +325,7 @@ impl<'b> Roots<'b> {
 
             let thread = mem::transmute::<&Thread, &'static Thread>(&*thread_ptr);
             let child_threads = thread.child_threads.read().unwrap();
-            for child in &*child_threads {
-                Vec::push(&mut stack, *child);
-            }
+            stack.extend(child_threads.iter().cloned());
 
             let context = thread.context.lock().unwrap();
 
@@ -975,10 +971,9 @@ impl ThreadInternal for Thread {
         debug!("Run IO {:?}", value);
         let mut context = self.context();
         // Dummy value to fill the place of the function for TailCall
-        context.stack.push(Int(0));
-
-        context.stack.push(value);
-        context.stack.push(Int(0));
+        context
+            .stack
+            .extend(&[Variants::int(0), value, Variants::int(0)]);
 
         context.borrow_mut().enter_scope(2, State::Unknown);
         context = match try_future!(self.call_function(context, 1), Either::A) {
@@ -989,9 +984,7 @@ impl ThreadInternal for Thread {
         context.stack.pop();
         {
             let mut context = context.borrow_mut();
-            while context.stack.len() > 0 {
-                context.stack.pop();
-            }
+            context.stack.clear();
         }
         let _ = context.exit_scope();
         Either::A(future::ok(result))
@@ -1787,9 +1780,7 @@ impl<'b> ExecuteContext<'b> {
                         match self.stack.excess_args() {
                             Some(excess) => {
                                 debug!("TailCall: Push excess args {:?}", excess.fields);
-                                for value in &excess.fields {
-                                    self.stack.push(value);
-                                }
+                                self.stack.extend(&excess.fields);
                                 args += excess.fields.len() as VmIndex;
                             }
                             None => ice!("Expected excess args"),
@@ -1873,9 +1864,7 @@ impl<'b> ExecuteContext<'b> {
                             }
                         }
                     };
-                    for _ in 0..args {
-                        self.stack.pop();
-                    }
+                    self.stack.pop_many(args);
                     self.stack.push(d);
                 }
                 NewVariant { tag, args } => {
@@ -1944,9 +1933,7 @@ impl<'b> ExecuteContext<'b> {
                             crate::value::ArrayDef(fields),
                         )?
                     };
-                    for _ in 0..args {
-                        self.stack.pop();
-                    }
+                    self.stack.pop_many(args);
                     self.stack.push(ValueRepr::Array(d));
                 }
                 GetOffset(i) => match self.stack.pop().get_repr() {
@@ -2013,9 +2000,7 @@ impl<'b> ExecuteContext<'b> {
                 Split => {
                     match self.stack.pop().get_repr() {
                         Data(data) => {
-                            for field in &data.fields {
-                                self.stack.push(field);
-                            }
+                            self.stack.extend(&data.fields);
                         }
                         // Zero argument variant
                         ValueRepr::Tag(_) => (),
@@ -2150,9 +2135,7 @@ impl<'b> ExecuteContext<'b> {
                 Data(excess) => {
                     debug!("Push excess args {:?}", &excess.fields);
                     context.stack.push(result);
-                    for value in &excess.fields {
-                        context.stack.push(value);
-                    }
+                    context.stack.extend(&excess.fields);
                     context
                         .do_call(excess.fields.len() as VmIndex)
                         .map(|x| Async::Ready(Some(x)))
@@ -2376,8 +2359,7 @@ where
         (T::from_value(vm, l), T::from_value(vm, r))
     };
     let result = f(l, r);
-    stack.pop();
-    stack.pop();
+    stack.pop_many(2);
     stack.stack.push(result);
 }
 


Test patch:
diff --git a/check/tests/fail.rs b/check/tests/fail.rs
index bfb0ef68..209d1e8c 100644
--- a/check/tests/fail.rs
+++ b/check/tests/fail.rs
@@ -513,19 +513,17 @@ Found:
     );
 }
 
-#[test]
-fn undefined_field_after_overload() {
-    let _ = ::env_logger::try_init();
-    let text = r#"
+test_check_err! {
+    undefined_field_after_overload,
+    r#"
 let f =
     \x g ->
         let { x } = g x
         x
 let r = f { x = 0 } (\r -> { x = r.x #Int+ 1 })
 r.y
-"#;
-    let result = support::typecheck(text);
-    assert_err!(result, InvalidProjection(..));
+"#,
+    InvalidProjection(..)
 }
 
 #[test]
diff --git a/check/tests/implicits.rs b/check/tests/implicits.rs
index 217797dd..9d15b37b 100644
--- a/check/tests/implicits.rs
+++ b/check/tests/implicits.rs
@@ -874,7 +874,7 @@ f 1
 }
 
 test_check_err! {
-break_infinte_implicit_resolve_early,
+break_infinite_implicit_resolve_early,
     r#"
 #[implicit]
 type Implicit a = { f : a -> String } 
diff --git a/check/tests/pass.rs b/check/tests/pass.rs
index 8162b6b2..e2a0ef97 100644
--- a/check/tests/pass.rs
+++ b/check/tests/pass.rs
@@ -1005,3 +1005,18 @@ Group
     "#,
     "String -> test.TestCase"
 }
+
+#[test]
+fn infix_env_type_of() {
+    let _ = env_logger::try_init();
+
+    let text = r#"
+#[infix(left, 4)]
+let (+) x y : a -> a -> a = y
+2 + 2
+"#;
+    let (expr, result) = support::typecheck_expr(text);
+
+    assert!(result.is_ok(), "{}", result.unwrap_err());
+    assert_eq!(expr.env_type_of(&MockEnv::new()).to_string(), "Int");
+}
diff --git a/parser/tests/error_handling.rs b/parser/tests/error_handling.rs
index a51b8b26..dfb05754 100644
--- a/parser/tests/error_handling.rs
+++ b/parser/tests/error_handling.rs
@@ -323,7 +323,7 @@ fn incomplete_let_binding_3() {
     "#;
     let result = parse(expr);
     assert!(result.is_err());
-    let (expr, err) = result.unwrap_err();
+    let (expr, _err) = result.unwrap_err();
     assert_eq!(
         clear_span(expr.unwrap()),
         let_("test", no_loc(Expr::Error(None)), int(1),)
diff --git a/tests/debug.rs b/tests/debug.rs
index b6e4245c..563b2207 100644
--- a/tests/debug.rs
+++ b/tests/debug.rs
@@ -468,6 +468,6 @@ fn implicit_prelude_variable_names() {
                 .row_iter()
                 .any(|field| field.name.declared_name() == "+"));
         }
-        _ => panic!(),
+        _ => panic!("{:#?}", f[0]),
     }
 }