Repository: gluon-lang/gluon
Pull request #195 (2016-10-29 09:17:35)

fix: Track from where a part of the AST originated
This is an attempt of a less hacky alternative to #190. By tracking the source of an expression the completion requests can skip over expanded expressions (like the implicit prelude) and only search in the non expanded expressions.

This increases the size of `Span<BytePos>` by 50% which, being a frequently used type, is rather unfortunate. We could maybe do some trickery to reduce this but this could be done later if it is necessary.

(Supersedes)
Closes #190


brendanzab: Got some merge conflicts that need to be resolved

Patch:
diff --git a/base/src/ast.rs b/base/src/ast.rs
index d2ae0ae5..5a44b1b8 100644
--- a/base/src/ast.rs
+++ b/base/src/ast.rs
@@ -171,14 +171,14 @@ pub trait MutVisitor {
 pub fn walk_mut_expr<V: ?Sized + MutVisitor>(v: &mut V, e: &mut SpannedExpr<V::Ident>) {
     match e.value {
         Expr::IfElse(ref mut pred, ref mut if_true, ref mut if_false) => {
-            v.visit_expr(&mut **pred);
-            v.visit_expr(&mut **if_true);
-            v.visit_expr(&mut **if_false);
+            v.visit_expr(pred);
+            v.visit_expr(if_true);
+            v.visit_expr(if_false);
         }
         Expr::Infix(ref mut lhs, ref mut id, ref mut rhs) => {
-            v.visit_expr(&mut **lhs);
+            v.visit_expr(lhs);
             v.visit_typ(&mut id.typ);
-            v.visit_expr(&mut **rhs);
+            v.visit_expr(rhs);
         }
         Expr::LetBindings(ref mut bindings, ref mut body) => {
             for bind in bindings {
@@ -186,21 +186,21 @@ pub fn walk_mut_expr<V: ?Sized + MutVisitor>(v: &mut V, e: &mut SpannedExpr<V::I
                 v.visit_expr(&mut bind.expr);
                 v.visit_typ(&mut bind.typ);
             }
-            v.visit_expr(&mut **body);
+            v.visit_expr(body);
         }
         Expr::App(ref mut func, ref mut args) => {
-            v.visit_expr(&mut **func);
+            v.visit_expr(func);
             for arg in args {
                 v.visit_expr(arg);
             }
         }
         Expr::Projection(ref mut expr, _, ref mut typ) => {
-            v.visit_expr(&mut **expr);
+            v.visit_expr(expr);
             v.visit_typ(typ);
         }
         Expr::Match(ref mut expr, ref mut alts) => {
-            v.visit_expr(&mut **expr);
-            for alt in alts.iter_mut() {
+            v.visit_expr(expr);
+            for alt in alts {
                 v.visit_pattern(&mut alt.pattern);
                 v.visit_expr(&mut alt.expr);
             }
@@ -226,9 +226,9 @@ pub fn walk_mut_expr<V: ?Sized + MutVisitor>(v: &mut V, e: &mut SpannedExpr<V::I
         }
         Expr::Lambda(ref mut lambda) => {
             v.visit_typ(&mut lambda.id.typ);
-            v.visit_expr(&mut *lambda.body);
+            v.visit_expr(&mut lambda.body);
         }
-        Expr::TypeBindings(_, ref mut expr) => v.visit_expr(&mut *expr),
+        Expr::TypeBindings(_, ref mut expr) => v.visit_expr(expr),
         Expr::Ident(ref mut id) => v.visit_typ(&mut id.typ),
         Expr::Literal(..) => (),
         Expr::Block(ref mut exprs) => {
@@ -255,6 +255,107 @@ pub fn walk_mut_pattern<V: ?Sized + MutVisitor>(v: &mut V, p: &mut Pattern<V::Id
     }
 }
 
+pub trait Visitor {
+    type Ident;
+
+    fn visit_expr(&mut self, e: &SpannedExpr<Self::Ident>) {
+        walk_expr(self, e);
+    }
+
+    fn visit_pattern(&mut self, e: &SpannedPattern<Self::Ident>) {
+        walk_pattern(self, &e.value);
+    }
+
+    fn visit_typ(&mut self, _: &ArcType<Self::Ident>) {}
+}
+
+pub fn walk_expr<V: ?Sized + Visitor>(v: &mut V, e: &SpannedExpr<V::Ident>) {
+    match e.value {
+        Expr::IfElse(ref pred, ref if_true, ref if_false) => {
+            v.visit_expr(pred);
+            v.visit_expr(if_true);
+            v.visit_expr(if_false);
+        }
+        Expr::Infix(ref lhs, ref id, ref rhs) => {
+            v.visit_expr(lhs);
+            v.visit_typ(&id.typ);
+            v.visit_expr(rhs);
+        }
+        Expr::LetBindings(ref bindings, ref body) => {
+            for bind in bindings {
+                v.visit_pattern(&bind.name);
+                v.visit_expr(&bind.expr);
+                v.visit_typ(&bind.typ);
+            }
+            v.visit_expr(&body);
+        }
+        Expr::App(ref func, ref args) => {
+            v.visit_expr(func);
+            for arg in args {
+                v.visit_expr(arg);
+            }
+        }
+        Expr::Projection(ref expr, _, ref typ) => {
+            v.visit_expr(expr);
+            v.visit_typ(typ);
+        }
+        Expr::Match(ref expr, ref alts) => {
+            v.visit_expr(expr);
+            for alt in alts {
+                v.visit_pattern(&alt.pattern);
+                v.visit_expr(&alt.expr);
+            }
+        }
+        Expr::Array(ref a) => {
+            v.visit_typ(&a.typ);
+            for expr in &a.exprs {
+                v.visit_expr(expr);
+            }
+        }
+        Expr::Record { ref typ, ref exprs, .. } => {
+            v.visit_typ(typ);
+            for field in exprs {
+                if let Some(ref expr) = field.1 {
+                    v.visit_expr(expr);
+                }
+            }
+        }
+        Expr::Tuple(ref exprs) => {
+            for expr in exprs {
+                v.visit_expr(expr);
+            }
+        }
+        Expr::Lambda(ref lambda) => {
+            v.visit_typ(&lambda.id.typ);
+            v.visit_expr(&lambda.body);
+        }
+        Expr::TypeBindings(_, ref expr) => v.visit_expr(expr),
+        Expr::Ident(ref id) => v.visit_typ(&id.typ),
+        Expr::Literal(..) => (),
+        Expr::Block(ref exprs) => {
+            for expr in exprs {
+                v.visit_expr(expr);
+            }
+        }
+    }
+}
+
+/// Walks a pattern, calling `visit_*` on all relevant elements
+pub fn walk_pattern<V: ?Sized + Visitor>(v: &mut V, p: &Pattern<V::Ident>) {
+    match *p {
+        Pattern::Constructor(ref id, ref args) => {
+            v.visit_typ(&id.typ);
+            for arg in args {
+                v.visit_typ(&arg.typ);
+            }
+        }
+        Pattern::Record { ref typ, .. } => {
+            v.visit_typ(typ);
+        }
+        Pattern::Ident(ref id) => v.visit_typ(&id.typ),
+    }
+}
+
 /// Trait which abstracts over things that have a type.
 /// It is not guaranteed that the correct type is returned until after typechecking
 pub trait Typed {
diff --git a/base/src/error.rs b/base/src/error.rs
index 4a2fb3dd..87c50f03 100644
--- a/base/src/error.rs
+++ b/base/src/error.rs
@@ -5,7 +5,7 @@ use std::any::Any;
 use std::error::Error as StdError;
 use std::fmt;
 
-use pos::{BytePos, Location, Span, Spanned};
+use pos::{BytePos, Location, Span, Spanned, spanned2};
 use source::Source;
 
 /// An error type which can represent multiple errors.
@@ -60,13 +60,7 @@ impl<E> SourceContext<E> {
 
         SourceContext {
             line: line.to_string(),
-            error: Spanned {
-                span: Span {
-                    start: start,
-                    end: end,
-                },
-                value: error.value,
-            },
+            error: spanned2(start, end, error.value),
         }
     }
 }
@@ -103,7 +97,7 @@ impl<E: fmt::Display> InFile<E> {
 impl<E: fmt::Display> fmt::Display for InFile<E> {
     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
         for error in &self.error.errors {
-            let Span { start, end } = error.error.span;
+            let Span { start, end, .. } = error.error.span;
 
             try!(write!(f, "{}:{}\n{}\n", self.source_name, error.error, error.line));
 
diff --git a/base/src/pos.rs b/base/src/pos.rs
index f63aab98..64914172 100644
--- a/base/src/pos.rs
+++ b/base/src/pos.rs
@@ -9,7 +9,7 @@ use std::ops::{Add, AddAssign, Sub, SubAssign};
 macro_rules! pos_struct {
     (#[$doc:meta] pub struct $Pos:ident($T:ty);) => {
         #[$doc]
-        #[derive(Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
+        #[derive(Clone, Copy, Default, PartialEq, Eq, Hash, PartialOrd, Ord, Debug)]
         pub struct $Pos($T);
 
         impl $Pos {
@@ -118,14 +118,69 @@ impl fmt::Display for Location {
     }
 }
 
+/// An expansion identifier tracks wheter a span originated from a macro expansion or not
+#[derive(Copy, Clone, Default, Ord, PartialOrd, Eq, PartialEq, Debug)]
+pub struct ExpansionId(pub u32);
+
+pub const NO_EXPANSION: ExpansionId = ExpansionId(0);
+
+pub const UNKNOWN_EXPANSION: ExpansionId = ExpansionId(1);
+
 /// A span between two locations in a source file
-#[derive(Copy, Clone, Ord, PartialOrd, Eq, PartialEq, Debug)]
+#[derive(Copy, Clone, Default, Eq, Debug)]
 pub struct Span<Pos> {
     pub start: Pos,
     pub end: Pos,
+    pub expansion_id: ExpansionId,
+}
+
+impl<Pos> PartialEq for Span<Pos>
+    where Pos: PartialEq,
+{
+    fn eq(&self, other: &Span<Pos>) -> bool {
+        self.start == other.start && self.end == other.end
+    }
 }
 
+impl<Pos> PartialOrd for Span<Pos>
+    where Pos: PartialOrd,
+{
+    fn partial_cmp(&self, other: &Span<Pos>) -> Option<Ordering> {
+        self.start
+            .partial_cmp(&other.start)
+            .and_then(|ord| {
+                if ord == Ordering::Equal {
+                    self.end.partial_cmp(&self.end)
+                } else {
+                    Some(ord)
+                }
+            })
+    }
+}
+
+impl<Pos> Ord for Span<Pos>
+    where Pos: Ord,
+{
+    fn cmp(&self, other: &Span<Pos>) -> Ordering {
+        let ord = self.start.cmp(&other.start);
+        if ord == Ordering::Equal {
+            self.end.cmp(&self.end)
+        } else {
+            ord
+        }
+    }
+}
+
+
 impl<Pos: Ord> Span<Pos> {
+    pub fn new(start: Pos, end: Pos) -> Span<Pos> {
+        Span {
+            start: start,
+            end: end,
+            expansion_id: NO_EXPANSION,
+        }
+    }
+
     pub fn contains(self, other: Span<Pos>) -> bool {
         self.start <= other.start && other.end <= self.end
     }
@@ -149,11 +204,13 @@ impl<Pos: Ord> Span<Pos> {
     }
 
     pub fn merge(self, other: Span<Pos>) -> Option<Span<Pos>> {
+        assert!(self.expansion_id == other.expansion_id);
         if (self.start <= other.start && self.end > other.start) ||
            (self.start >= other.start && self.start < other.end) {
             Some(Span {
                 start: cmp::min(self.start, other.start),
                 end: cmp::max(self.end, other.end),
+                expansion_id: self.expansion_id,
             })
         } else {
             None
@@ -191,6 +248,7 @@ pub fn spanned2<T, Pos>(start: Pos, end: Pos, value: T) -> Spanned<T, Pos> {
         span: Span {
             start: start,
             end: end,
+            expansion_id: NO_EXPANSION,
         },
         value: value,
     }
diff --git a/check/src/completion.rs b/check/src/completion.rs
index 1732bb29..31df78ae 100644
--- a/check/src/completion.rs
+++ b/check/src/completion.rs
@@ -3,9 +3,10 @@
 use std::iter::once;
 use std::cmp::Ordering;
 
-use base::ast::{Expr, SpannedExpr, SpannedPattern, Pattern, TypedIdent, Typed};
+use base::ast::{Expr, SpannedExpr, SpannedPattern, Pattern, TypedIdent, Typed, Visitor, walk_expr,
+                walk_pattern};
 use base::instantiate;
-use base::pos::{BytePos, Span};
+use base::pos::{BytePos, Span, NO_EXPANSION};
 use base::scoped_map::ScopedMap;
 use base::symbol::Symbol;
 use base::types::{ArcType, Type, TypeEnv};
@@ -25,6 +26,8 @@ trait OnFound {
 
     /// Location points to whitespace
     fn nothing(&mut self);
+
+    fn found(&self) -> bool;
 }
 
 struct GetType<E> {
@@ -42,6 +45,10 @@ impl<E: TypeEnv> OnFound for GetType<E> {
     }
 
     fn nothing(&mut self) {}
+
+    fn found(&self) -> bool {
+        self.typ.is_some()
+    }
 }
 
 pub struct Suggestion {
@@ -120,6 +127,10 @@ impl<E: TypeEnv> OnFound for Suggest<E> {
             }
         }));
     }
+
+    fn found(&self) -> bool {
+        !self.result.is_empty()
+    }
 }
 
 struct FindVisitor<F> {
@@ -156,6 +167,32 @@ impl<F> FindVisitor<F> {
     }
 }
 
+struct VisitUnExpanded<'e, F: 'e>(&'e mut FindVisitor<F>);
+
+impl<'e, F> Visitor for VisitUnExpanded<'e, F>
+    where F: OnFound,
+{
+    type Ident = Symbol;
+
+    fn visit_expr(&mut self, e: &SpannedExpr<Self::Ident>) {
+        if !self.0.on_found.found() {
+            if e.span.expansion_id == NO_EXPANSION {
+                self.0.visit_expr(e);
+            } else {
+                walk_expr(self, e);
+            }
+        }
+    }
+
+    fn visit_pattern(&mut self, e: &SpannedPattern<Self::Ident>) {
+        if e.span.expansion_id == NO_EXPANSION {
+            self.0.visit_pattern(e);
+        } else {
+            walk_pattern(self, &e.value);
+        }
+    }
+}
+
 impl<F> FindVisitor<F>
     where F: OnFound,
 {
@@ -171,6 +208,11 @@ impl<F> FindVisitor<F>
     }
 
     fn visit_expr(&mut self, current: &SpannedExpr<Symbol>) {
+        // When inside a macro expanded expression we do a exhaustive search for an unexpanded expression
+        if current.span.expansion_id != NO_EXPANSION {
+            VisitUnExpanded(self).visit_expr(current);
+            return;
+        }
         match current.value {
             Expr::Ident(_) | Expr::Literal(_) => {
                 if current.span.containment(&self.pos) == Ordering::Equal {
diff --git a/parser/src/lexer.rs b/parser/src/lexer.rs
index c73b266e..5bf4247c 100644
--- a/parser/src/lexer.rs
+++ b/parser/src/lexer.rs
@@ -2,7 +2,7 @@ use std::cmp::Ordering;
 use std::fmt;
 
 use base::ast::is_operator_char;
-use base::pos::{BytePos, Column, Line, Location, Span, Spanned};
+use base::pos::{BytePos, Column, Line, Location, Span, Spanned, NO_EXPANSION};
 
 use combine::primitives::{Consumed, Error as CombineError, RangeStream};
 use combine::combinator::EnvParser;
@@ -464,6 +464,7 @@ impl<'input, I> Lexer<'input, I>
                     span: Span {
                         start: loc,
                         end: loc,
+                        expansion_id: NO_EXPANSION,
                     },
                     value: Token::EOF,
                 };
@@ -484,6 +485,7 @@ impl<'input, I> Lexer<'input, I>
                     span: Span {
                         start: start,
                         end: end,
+                        expansion_id: NO_EXPANSION,
                     },
                     value: token,
                 }
@@ -494,6 +496,7 @@ impl<'input, I> Lexer<'input, I>
                 let span = Span {
                     start: start,
                     end: start,
+                    expansion_id: NO_EXPANSION,
                 };
                 self.end_span = Some(span);
                 SpannedToken {
@@ -680,6 +683,7 @@ impl<'input, I> Lexer<'input, I>
                     self.end_span = Some(Span {
                         start: loc,
                         end: loc,
+                        expansion_id: NO_EXPANSION,
                     });
                 }
                 Err(err)
diff --git a/parser/src/lib.rs b/parser/src/lib.rs
index c4a4fc21..1b40a017 100644
--- a/parser/src/lib.rs
+++ b/parser/src/lib.rs
@@ -102,6 +102,7 @@ impl<'input, 'lexer> StreamOnce for Wrapper<'input, 'lexer> {
         Span {
             start: span.start.absolute,
             end: span.end.absolute,
+            expansion_id: pos::NO_EXPANSION,
         }
     }
 }
@@ -438,8 +439,7 @@ impl<'input, I, Id, F> ParserEnv<I, F>
     /// Parses an expression which could be an argument to a function
     fn parse_arg(&self, input: I) -> ParseResult<SpannedExpr<Id>, I> {
         debug!("Expr start: {:?}", input.clone().uncons());
-        let span = input.position();
-        let loc = |expr| pos::spanned(span, expr);
+        let start = input.position().start;
 
         // To prevent stack overflows we push all binding groups (which are commonly deeply nested)
         // to a stack and construct the expressions afterwards
@@ -448,7 +448,15 @@ impl<'input, I, Id, F> ParserEnv<I, F>
         let mut input = input;
         let mut declaration_parser = self.parser(ParserEnv::<I, F>::type_decl)
             .or(self.parser(ParserEnv::<I, F>::let_in))
-            .map(loc);
+            .and(parser(move |input: I| {
+                let span = Span {
+                    start: start,
+                    end: input.position().end,
+                    expansion_id: pos::NO_EXPANSION,
+                };
+                Ok((span, Consumed::Empty(input)))
+            }))
+            .map(|(decl, span)| pos::spanned(span, decl));
         loop {
             match declaration_parser.parse_lazy(input.clone()) {
                 ConsumedOk((bindings, new_input)) |
@@ -725,11 +733,9 @@ impl<'input, I, Id, F> ParserEnv<I, F>
          token(Token::Else),
          self.expr())
             .map(|(_, b, _, t, _, f)| {
-                pos::spanned(Span {
-                                 start: start,
-                                 end: f.span.end,
-                             },
-                             Expr::IfElse(Box::new(b), Box::new(t), Box::new(f)))
+                pos::spanned2(start,
+                              f.span.end,
+                              Expr::IfElse(Box::new(b), Box::new(t), Box::new(f)))
             })
             .parse_stream(input)
     }
diff --git a/src/lib.rs b/src/lib.rs
index c39976d7..d5e5de3c 100644
--- a/src/lib.rs
+++ b/src/lib.rs
@@ -295,25 +295,31 @@ impl Compiler {
             return;
         }
 
-        let prelude_import = r#"
-    let __implicit_prelude = import "std/prelude.glu"
-    and { Num, Eq, Ord, Show, Functor, Monad, Bool, Option, Result, not } = __implicit_prelude
+        let prelude_expr = self.parse_expr("", PRELUDE).unwrap();
+        let original_expr = mem::replace(expr, prelude_expr);
 
-    let { (+), (-), (*), (/) } = __implicit_prelude.num_Int
-    and { (==) } = __implicit_prelude.eq_Int
-    and { (<), (<=), (>=), (>) } = __implicit_prelude.make_Ord __implicit_prelude.ord_Int
+        // Set all spans in the prelude expression to -1 so that completion requests always
+        // skips searching the implicit prelude
+        use base::ast::{MutVisitor, SpannedPattern, walk_mut_expr, walk_mut_pattern};
+        use base::pos::{ExpansionId, UNKNOWN_EXPANSION};
+        struct ExpandedSpans;
 
-    let { (+), (-), (*), (/) } = __implicit_prelude.num_Float
-    and { (==) } = __implicit_prelude.eq_Float
-    and { (<), (<=), (>=), (>) } = __implicit_prelude.make_Ord __implicit_prelude.ord_Float
+        impl MutVisitor for ExpandedSpans {
+            type Ident = Symbol;
 
-    let { (==) } = __implicit_prelude.eq_Char
-    and { (<), (<=), (>=), (>) } = __implicit_prelude.make_Ord __implicit_prelude.ord_Char
+            fn visit_expr(&mut self, e: &mut SpannedExpr<Self::Ident>) {
+                e.span.expansion_id = UNKNOWN_EXPANSION;
+                walk_mut_expr(self, e);
+            }
 
-    in 0
-    "#;
-        let prelude_expr = self.parse_expr("", prelude_import).unwrap();
-        let original_expr = mem::replace(expr, prelude_expr);
+            fn visit_pattern(&mut self, p: &mut SpannedPattern<Self::Ident>) {
+                p.span.expansion_id = UNKNOWN_EXPANSION;
+                walk_mut_pattern(self, &mut p.value);
+            }
+        }
+        ExpandedSpans.visit_expr(expr);
+
+        // Replace the 0 in the prelude with the actual expression
         fn assign_last_body(l: &mut SpannedExpr<Symbol>, original_expr: SpannedExpr<Symbol>) {
             match l.value {
                 ast::Expr::LetBindings(_, ref mut e) => {
@@ -326,6 +332,24 @@ impl Compiler {
     }
 }
 
+pub const PRELUDE: &'static str = r#"
+let __implicit_prelude = import "std/prelude.glu"
+and { Num, Eq, Ord, Show, Functor, Monad, Bool, Option, Result, not } = __implicit_prelude
+
+let { (+), (-), (*), (/) } = __implicit_prelude.num_Int
+and { (==) } = __implicit_prelude.eq_Int
+and { (<), (<=), (>=), (>) } = __implicit_prelude.make_Ord __implicit_prelude.ord_Int
+
+let { (+), (-), (*), (/) } = __implicit_prelude.num_Float
+and { (==) } = __implicit_prelude.eq_Float
+and { (<), (<=), (>=), (>) } = __implicit_prelude.make_Ord __implicit_prelude.ord_Float
+
+let { (==) } = __implicit_prelude.eq_Char
+and { (<), (<=), (>=), (>) } = __implicit_prelude.make_Ord __implicit_prelude.ord_Char
+
+in 0
+"#;
+
 pub fn filename_to_module(filename: &str) -> StdString {
     use std::path::Path;
     let path = Path::new(filename);
diff --git a/vm/src/thread.rs b/vm/src/thread.rs
index 3bb2d920..784672d8 100644
--- a/vm/src/thread.rs
+++ b/vm/src/thread.rs
@@ -1346,7 +1346,7 @@ fn binop<'b, F, T>(vm: &'b Thread, stack: &mut StackFrame<'b>, f: F)
             // pushing numbers should never return an error so unwrap
             stack.stack.push(result);
         }
-        (l, r) => panic!("{:?} `op` {:?}", l, r),
+        _ => panic!("{:?} `op` {:?}", l, r),
     }
 }
 


Test patch:
diff --git a/check/tests/completion.rs b/check/tests/completion.rs
index f5c62670..f6f83d48 100644
--- a/check/tests/completion.rs
+++ b/check/tests/completion.rs
@@ -80,6 +80,21 @@ and g x = "asd"
     assert_eq!(result, expected);
 }
 
+#[test]
+fn let_in_let() {
+    let result = find_type(r#"
+let f =
+    let g y =
+        123
+    g
+f
+"#,
+                           BytePos::from(33));
+    let expected = Ok(typ("Int"));
+
+    assert_eq!(result, expected);
+}
+
 #[test]
 fn function_app() {
     let _ = env_logger::init();
diff --git a/check/tests/pass.rs b/check/tests/pass.rs
index 90024b40..b1d694c6 100644
--- a/check/tests/pass.rs
+++ b/check/tests/pass.rs
@@ -730,10 +730,7 @@ in f "123"
     let err = result.unwrap_err();
     assert_eq!(err.errors.len(), 1);
     assert_eq!(err.errors[0].span,
-               Span {
-                   start: BytePos::from(26),
-                   end: BytePos::from(31),
-               });
+               Span::new(BytePos::from(26), BytePos::from(31)));
 }
 
 /// Test that overload resolution selects the closest implementation that matches even if another
diff --git a/parser/tests/basic.rs b/parser/tests/basic.rs
index 6fb4401a..fac2f644 100644
--- a/parser/tests/basic.rs
+++ b/parser/tests/basic.rs
@@ -20,11 +20,7 @@ pub fn intern(s: &str) -> String {
 type SpExpr = SpannedExpr<String>;
 
 fn no_loc<T>(value: T) -> Spanned<T, BytePos> {
-    pos::spanned(Span {
-                     start: BytePos::from(0),
-                     end: BytePos::from(0),
-                 },
-                 value)
+    pos::spanned(Span::default(), value)
 }
 
 fn binop(l: SpExpr, s: &str, r: SpExpr) -> SpExpr {
@@ -412,24 +408,15 @@ fn span_identifier() {
     let _ = ::env_logger::init();
 
     let e = parse_new!("test");
-    assert_eq!(e.span,
-               Span {
-                   start: BytePos::from(0),
-                   end: BytePos::from(4),
-               });
+    assert_eq!(e.span, Span::new(BytePos::from(0), BytePos::from(4)));
 }
 
-
 #[test]
 fn span_integer() {
     let _ = ::env_logger::init();
 
     let e = parse_new!("1234");
-    assert_eq!(e.span,
-               Span {
-                   start: BytePos::from(0),
-                   end: BytePos::from(4),
-               });
+    assert_eq!(e.span, Span::new(BytePos::from(0), BytePos::from(4)));
 }
 
 // FIXME The span of string literals includes the spaces after them
@@ -439,11 +426,7 @@ fn span_string_literal() {
     let _ = ::env_logger::init();
 
     let e = parse_new!(r#" "test" "#);
-    assert_eq!(e.span,
-               Span {
-                   start: BytePos::from(1),
-                   end: BytePos::from(7),
-               });
+    assert_eq!(e.span, Span::new(BytePos::from(1), BytePos::from(7)));
 }
 
 #[test]
@@ -451,11 +434,7 @@ fn span_app() {
     let _ = ::env_logger::init();
 
     let e = parse_new!(r#" f 123 "asd""#);
-    assert_eq!(e.span,
-               Span {
-                   start: BytePos::from(1),
-                   end: BytePos::from(12),
-               });
+    assert_eq!(e.span, Span::new(BytePos::from(1), BytePos::from(12)));
 }
 
 #[test]
@@ -467,11 +446,7 @@ match False with
     | True -> "asd"
     | False -> ""
 "#);
-    assert_eq!(e.span,
-               Span {
-                   start: BytePos::from(1),
-                   end: BytePos::from(55),
-               });
+    assert_eq!(e.span, Span::new(BytePos::from(1), BytePos::from(55)));
 }
 
 #[test]
@@ -484,11 +459,7 @@ if True then
 else
     123.45
 "#);
-    assert_eq!(e.span,
-               Span {
-                   start: BytePos::from(1),
-                   end: BytePos::from(35),
-               });
+    assert_eq!(e.span, Span::new(BytePos::from(1), BytePos::from(35)));
 }
 
 #[test]
@@ -496,29 +467,17 @@ fn span_byte() {
     let _ = ::env_logger::init();
 
     let e = parse_new!(r#"124b"#);
-    assert_eq!(e.span,
-               Span {
-                   start: BytePos::from(0),
-                   end: BytePos::from(4),
-               });
+    assert_eq!(e.span, Span::new(BytePos::from(0), BytePos::from(4)));
 }
 
 #[test]
 fn span_field_access() {
     let _ = ::env_logger::init();
     let expr = parse_new!("record.x");
-    assert_eq!(expr.span,
-               Span {
-                   start: BytePos::from(0),
-                   end: BytePos::from(8),
-               });
+    assert_eq!(expr.span, Span::new(BytePos::from(0), BytePos::from(8)));
     match expr.value {
         Expr::Projection(ref e, _, _) => {
-            assert_eq!(e.span,
-                       Span {
-                           start: BytePos::from(0),
-                           end: BytePos::from(6),
-                       });
+            assert_eq!(e.span, Span::new(BytePos::from(0), BytePos::from(6)));
         }
         _ => panic!(),
     }
@@ -613,10 +572,7 @@ fn partial_field_access() {
     assert!(e.is_err());
     assert_eq!(e.unwrap_err().0,
                Some(Spanned {
-                   span: Span {
-                       start: BytePos::from(0),
-                       end: BytePos::from(0),
-                   },
+                   span: Span::default(),
                    value: Expr::Projection(Box::new(id("test")), intern(""), Type::hole()),
                }));
 }
@@ -632,15 +588,9 @@ test
     assert!(e.is_err());
     assert_eq!(e.unwrap_err().0,
                Some(Spanned {
-                   span: Span {
-                       start: BytePos::from(0),
-                       end: BytePos::from(0),
-                   },
+                   span: Span::default(),
                    value: Expr::Block(vec![Spanned {
-                                               span: Span {
-                                                   start: BytePos::from(0),
-                                                   end: BytePos::from(0),
-                                               },
+                                               span: Span::new(BytePos::from(0), BytePos::from(0)),
                                                value: Expr::Projection(Box::new(id("test")),
                                                                        intern(""),
                                                                        Type::hole()),
diff --git a/tests/vm.rs b/tests/vm.rs
index 71d0d5bf..01061e7c 100644
--- a/tests/vm.rs
+++ b/tests/vm.rs
@@ -6,6 +6,9 @@ mod support;
 
 use support::*;
 
+use gluon::base::pos::BytePos;
+use gluon::base::types::Type;
+use gluon::check::completion;
 use gluon::vm::api::{FunctionRef, Hole, IO, OpaqueValue, ValueRef};
 use gluon::vm::thread::{Thread, ThreadInternal};
 use gluon::vm::internal::Value;
@@ -753,6 +756,55 @@ g 10
         Ok(_) => panic!("Expected an error"),
     }
 }
+#[test]
+fn completion_with_prelude() {
+    let _ = ::env_logger::init();
+    let vm = make_vm();
+
+    let expr = r#"
+let prelude = import "std/prelude.glu"
+and { Option, Num } = prelude
+and { (+) } = prelude.num_Int
+
+type Stream_ a =
+    | Value a (Stream a)
+    | Empty
+and Stream a = Lazy (Stream_ a)
+
+let from f : (Int -> Option a) -> Stream a =
+        let from_ i =
+                lazy (\_ ->
+                    match f i with
+                        | Some x -> Value x (from_ (i + 1))
+                        | None -> Empty
+                )
+        in from_ 0
+
+{ from }
+"#;
+
+    let (expr, _) = Compiler::new()
+        .typecheck_str(&vm, "example", expr, None)
+        .unwrap_or_else(|err| panic!("{}", err));
+
+    let result = completion::find(&*vm.get_env(), &expr, BytePos::from(311));
+    assert_eq!(result, Ok(Type::int()));
+}
+
+#[test]
+fn completion_with_prelude_at_0() {
+    let _ = ::env_logger::init();
+    let vm = make_vm();
+
+    let expr = "1";
+
+    let (expr, _) = Compiler::new()
+        .typecheck_str(&vm, "example", expr, None)
+        .unwrap_or_else(|err| panic!("{}", err));
+
+    let result = completion::find(&*vm.get_env(), &expr, BytePos::from(0));
+    assert_eq!(result, Ok(Type::int()));
+}
 
 #[test]
 fn value_size() {