Resolve variables alongside import resolution

8 files changed, 161 insertions, 83 deletions

diff --git a/dhall/src/error/mod.rs b/dhall/src/error/mod.rs
index 13b61fa..9cb8a41 100644
--- a/dhall/src/error/mod.rs
+++ b/dhall/src/error/mod.rs
@@ -1,8 +1,8 @@
 use std::io::Error as IOError;
 
 use crate::semantics::resolve::ImportStack;
+use crate::semantics::Hir;
 use crate::syntax::{Import, ParseError};
-use crate::NormalizedExpr;
 
 mod builder;
 pub(crate) use builder::*;
@@ -10,8 +10,13 @@ pub(crate) use builder::*;
 pub type Result<T> = std::result::Result<T, Error>;
 
 #[derive(Debug)]
+pub struct Error {
+    kind: ErrorKind,
+}
+
+#[derive(Debug)]
 #[non_exhaustive]
-pub enum Error {
+pub(crate) enum ErrorKind {
     IO(IOError),
     Parse(ParseError),
     Decode(DecodeError),
@@ -21,10 +26,9 @@ pub enum Error {
 }
 
 #[derive(Debug)]
-pub enum ImportError {
-    Recursive(Import<NormalizedExpr>, Box<Error>),
-    UnexpectedImport(Import<NormalizedExpr>),
-    ImportCycle(ImportStack, Import<NormalizedExpr>),
+pub(crate) enum ImportError {
+    UnexpectedImport(Import<Hir>),
+    ImportCycle(ImportStack, Import<Hir>),
 }
 
 #[derive(Debug)]
@@ -51,6 +55,15 @@ pub(crate) enum TypeMessage {
     Custom(String),
 }
 
+impl Error {
+    pub(crate) fn new(kind: ErrorKind) -> Self {
+        Error { kind }
+    }
+    pub(crate) fn kind(&self) -> &ErrorKind {
+        &self.kind
+    }
+}
+
 impl TypeError {
     pub(crate) fn new(message: TypeMessage) -> Self {
         TypeError { message }
@@ -72,45 +85,50 @@ impl std::error::Error for TypeError {}
 
 impl std::fmt::Display for Error {
     fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
-        match self {
-            Error::IO(err) => write!(f, "{}", err),
-            Error::Parse(err) => write!(f, "{}", err),
-            Error::Decode(err) => write!(f, "{:?}", err),
-            Error::Encode(err) => write!(f, "{:?}", err),
-            Error::Resolve(err) => write!(f, "{:?}", err),
-            Error::Typecheck(err) => write!(f, "{}", err),
+        match &self.kind {
+            ErrorKind::IO(err) => write!(f, "{}", err),
+            ErrorKind::Parse(err) => write!(f, "{}", err),
+            ErrorKind::Decode(err) => write!(f, "{:?}", err),
+            ErrorKind::Encode(err) => write!(f, "{:?}", err),
+            ErrorKind::Resolve(err) => write!(f, "{:?}", err),
+            ErrorKind::Typecheck(err) => write!(f, "{}", err),
         }
     }
 }
 
 impl std::error::Error for Error {}
+impl From<ErrorKind> for Error {
+    fn from(kind: ErrorKind) -> Error {
+        Error::new(kind)
+    }
+}
 impl From<IOError> for Error {
     fn from(err: IOError) -> Error {
-        Error::IO(err)
+        ErrorKind::IO(err).into()
     }
 }
 impl From<ParseError> for Error {
     fn from(err: ParseError) -> Error {
-        Error::Parse(err)
+        ErrorKind::Parse(err).into()
     }
 }
 impl From<DecodeError> for Error {
     fn from(err: DecodeError) -> Error {
-        Error::Decode(err)
+        ErrorKind::Decode(err).into()
     }
 }
 impl From<EncodeError> for Error {
     fn from(err: EncodeError) -> Error {
-        Error::Encode(err)
+        ErrorKind::Encode(err).into()
     }
 }
 impl From<ImportError> for Error {
     fn from(err: ImportError) -> Error {
-        Error::Resolve(err)
+        ErrorKind::Resolve(err).into()
     }
 }
 impl From<TypeError> for Error {
     fn from(err: TypeError) -> Error {
-        Error::Typecheck(err)
+        ErrorKind::Typecheck(err).into()
     }
 }
diff --git a/dhall/src/lib.rs b/dhall/src/lib.rs
index 48d4d96..c2a2f19 100644
--- a/dhall/src/lib.rs
+++ b/dhall/src/lib.rs
@@ -18,11 +18,13 @@ pub mod syntax;
 use std::fmt::Display;
 use std::path::Path;
 
-use crate::error::{EncodeError, Error, ImportError, TypeError};
+use crate::error::{EncodeError, Error, TypeError};
 use crate::semantics::parse;
 use crate::semantics::resolve;
 use crate::semantics::resolve::ImportRoot;
-use crate::semantics::{typecheck, typecheck_with, TyExpr, Value, ValueKind};
+use crate::semantics::{
+    typecheck, typecheck_with, Hir, TyExpr, Value, ValueKind,
+};
 use crate::syntax::binary;
 use crate::syntax::{Builtin, Expr};
 
@@ -38,7 +40,7 @@ pub struct Parsed(ParsedExpr, ImportRoot);
 ///
 /// Invariant: there must be no `Import` nodes or `ImportAlt` operations left.
 #[derive(Debug, Clone)]
-pub struct Resolved(ResolvedExpr);
+pub struct Resolved(Hir);
 
 /// A typed expression
 #[derive(Debug, Clone)]
@@ -73,10 +75,10 @@ impl Parsed {
         parse::parse_binary(data)
     }
 
-    pub fn resolve(self) -> Result<Resolved, ImportError> {
+    pub fn resolve(self) -> Result<Resolved, Error> {
         resolve::resolve(self)
     }
-    pub fn skip_resolve(self) -> Result<Resolved, ImportError> {
+    pub fn skip_resolve(self) -> Result<Resolved, Error> {
         resolve::skip_resolve_expr(self)
     }
 
@@ -92,14 +94,14 @@ impl Parsed {
 
 impl Resolved {
     pub fn typecheck(&self) -> Result<Typed, TypeError> {
-        Ok(Typed(typecheck(&self.0)?))
+        Ok(Typed(typecheck(&self.to_expr())?))
     }
     pub fn typecheck_with(self, ty: &Normalized) -> Result<Typed, TypeError> {
-        Ok(Typed(typecheck_with(&self.0, ty.to_expr())?))
+        Ok(Typed(typecheck_with(&self.to_expr(), ty.to_expr())?))
     }
     /// Converts a value back to the corresponding AST expression.
     pub fn to_expr(&self) -> ResolvedExpr {
-        self.0.clone()
+        self.0.to_expr_noopts()
     }
 }
 
@@ -207,7 +209,6 @@ macro_rules! derive_traits_for_wrapper_struct {
 }
 
 derive_traits_for_wrapper_struct!(Parsed);
-derive_traits_for_wrapper_struct!(Resolved);
 
 impl std::hash::Hash for Normalized {
     fn hash<H>(&self, state: &mut H)
@@ -231,6 +232,12 @@ impl From<Normalized> for NormalizedExpr {
     }
 }
 
+impl Display for Resolved {
+    fn fmt(&self, f: &mut std::fmt::Formatter) -> Result<(), std::fmt::Error> {
+        self.to_expr().fmt(f)
+    }
+}
+
 impl Eq for Typed {}
 impl PartialEq for Typed {
     fn eq(&self, other: &Self) -> bool {
diff --git a/dhall/src/semantics/hir.rs b/dhall/src/semantics/hir.rs
index 683dbbb..80d17fb 100644
--- a/dhall/src/semantics/hir.rs
+++ b/dhall/src/semantics/hir.rs
@@ -1,15 +1,15 @@
 #![allow(dead_code)]
-use crate::semantics::{rc, NameEnv, NzEnv, TyEnv, Value};
+use crate::semantics::{NameEnv, NzEnv, TyEnv, Value};
 use crate::syntax::{ExprKind, Span, V};
-use crate::{Normalized, NormalizedExpr, ToExprOptions};
+use crate::{Expr, Normalized, NormalizedExpr, ToExprOptions};
 
 /// Stores an alpha-normalized variable.
-#[derive(Debug, Clone, Copy)]
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
 pub struct AlphaVar {
     idx: usize,
 }
 
-#[derive(Debug, Clone)]
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub(crate) enum HirKind {
     Var(AlphaVar),
     // Forbidden ExprKind variants: Var, Import, Embed
@@ -51,6 +51,14 @@ impl Hir {
     pub fn to_expr(&self, opts: ToExprOptions) -> NormalizedExpr {
         hir_to_expr(self, opts, &mut NameEnv::new())
     }
+    /// Converts a HIR expr back to the corresponding AST expression.
+    pub fn to_expr_noopts(&self) -> NormalizedExpr {
+        let opts = ToExprOptions {
+            normalize: false,
+            alpha: false,
+        };
+        self.to_expr(opts)
+    }
     pub fn to_expr_tyenv(&self, env: &TyEnv) -> NormalizedExpr {
         let opts = ToExprOptions {
             normalize: true,
@@ -82,7 +90,7 @@ fn hir_to_expr(
     opts: ToExprOptions,
     env: &mut NameEnv,
 ) -> NormalizedExpr {
-    rc(match hir.kind() {
+    let kind = match hir.kind() {
         HirKind::Var(v) if opts.alpha => ExprKind::Var(V("_".into(), v.idx())),
         HirKind::Var(v) => ExprKind::Var(env.label_var(v)),
         HirKind::Expr(e) => {
@@ -107,5 +115,21 @@ fn hir_to_expr(
                 e => e,
             }
         }
-    })
+    };
+    Expr::new(kind, hir.span())
+}
+
+impl std::cmp::PartialEq for Hir {
+    fn eq(&self, other: &Self) -> bool {
+        self.kind == other.kind
+    }
+}
+impl std::cmp::Eq for Hir {}
+impl std::hash::Hash for Hir {
+    fn hash<H>(&self, state: &mut H)
+    where
+        H: std::hash::Hasher,
+    {
+        self.kind.hash(state)
+    }
 }
diff --git a/dhall/src/semantics/resolve.rs b/dhall/src/semantics/resolve.rs
index 223cfa4..e12e892 100644
--- a/dhall/src/semantics/resolve.rs
+++ b/dhall/src/semantics/resolve.rs
@@ -1,12 +1,14 @@
 use std::collections::HashMap;
 use std::path::{Path, PathBuf};
 
+use crate::error::ErrorBuilder;
 use crate::error::{Error, ImportError};
+use crate::semantics::{mkerr, Hir, HirKind, NameEnv};
 use crate::syntax;
 use crate::syntax::{BinOp, Expr, ExprKind, FilePath, ImportLocation, URL};
-use crate::{Normalized, NormalizedExpr, Parsed, Resolved};
+use crate::{Normalized, Parsed, Resolved};
 
-type Import = syntax::Import<NormalizedExpr>;
+type Import = syntax::Import<Hir>;
 
 /// A root from which to resolve relative imports.
 #[derive(Debug, Clone, PartialEq, Eq)]
@@ -34,13 +36,12 @@ impl ResolveEnv {
     pub fn handle_import(
         &mut self,
         import: Import,
-        mut do_resolve: impl FnMut(
-            &mut Self,
-            &Import,
-        ) -> Result<Normalized, ImportError>,
-    ) -> Result<Normalized, ImportError> {
+        mut do_resolve: impl FnMut(&mut Self, &Import) -> Result<Normalized, Error>,
+    ) -> Result<Normalized, Error> {
         if self.stack.contains(&import) {
-            return Err(ImportError::ImportCycle(self.stack.clone(), import));
+            return Err(
+                ImportError::ImportCycle(self.stack.clone(), import).into()
+            );
         }
         Ok(match self.cache.get(&import) {
             Some(expr) => expr.clone(),
@@ -67,7 +68,7 @@ fn resolve_one_import(
     env: &mut ResolveEnv,
     import: &Import,
     root: &ImportRoot,
-) -> Result<Normalized, ImportError> {
+) -> Result<Normalized, Error> {
     use self::ImportRoot::*;
     use syntax::FilePrefix::*;
     use syntax::ImportLocation::*;
@@ -83,9 +84,7 @@ fn resolve_one_import(
                 Here => cwd.join(path_buf),
                 _ => unimplemented!("{:?}", import),
             };
-            Ok(load_import(env, &path_buf).map_err(|e| {
-                ImportError::Recursive(import.clone(), Box::new(e))
-            })?)
+            Ok(load_import(env, &path_buf)?)
         }
         _ => unimplemented!("{:?}", import),
     }
@@ -99,56 +98,76 @@ fn load_import(env: &mut ResolveEnv, f: &Path) -> Result<Normalized, Error> {
 /// Traverse the expression, handling import alternatives and passing
 /// found imports to the provided function.
 fn traverse_resolve_expr(
+    name_env: &mut NameEnv,
     expr: &Expr<Normalized>,
-    f: &mut impl FnMut(Import) -> Result<Normalized, ImportError>,
-) -> Result<Expr<Normalized>, ImportError> {
-    Ok(match expr.kind() {
+    f: &mut impl FnMut(Import) -> Result<Normalized, Error>,
+) -> Result<Hir, Error> {
+    let kind = match expr.kind() {
+        ExprKind::Var(var) => match name_env.unlabel_var(&var) {
+            Some(v) => HirKind::Var(v),
+            None => mkerr(
+                ErrorBuilder::new(format!("unbound variable `{}`", var))
+                    .span_err(expr.span(), "not found in this scope")
+                    .format(),
+            )?,
+        },
         ExprKind::BinOp(BinOp::ImportAlt, l, r) => {
-            match traverse_resolve_expr(l, f) {
-                Ok(l) => l,
+            return match traverse_resolve_expr(name_env, l, f) {
+                Ok(l) => Ok(l),
                 Err(_) => {
-                    match traverse_resolve_expr(r, f) {
-                        Ok(r) => r,
+                    match traverse_resolve_expr(name_env, r, f) {
+                        Ok(r) => Ok(r),
                         // TODO: keep track of the other error too
-                        Err(e) => return Err(e),
+                        Err(e) => Err(e),
                     }
                 }
-            }
+            };
         }
         kind => {
-            let kind = kind.traverse_ref(|e| traverse_resolve_expr(e, f))?;
-            expr.rewrap(match kind {
+            let kind = kind.traverse_ref_maybe_binder(|l, e| {
+                if let Some(l) = l {
+                    name_env.insert_mut(l);
+                }
+                let hir = traverse_resolve_expr(name_env, e, f)?;
+                if let Some(_) = l {
+                    name_env.remove_mut();
+                }
+                Ok::<_, Error>(hir)
+            })?;
+            HirKind::Expr(match kind {
                 ExprKind::Import(import) => ExprKind::Embed(f(import)?),
                 kind => kind,
             })
         }
-    })
+    };
+
+    Ok(Hir::new(kind, expr.span()))
 }
 
 fn resolve_with_env(
     env: &mut ResolveEnv,
     parsed: Parsed,
-) -> Result<Resolved, ImportError> {
+) -> Result<Resolved, Error> {
     let Parsed(expr, root) = parsed;
-    let resolved = traverse_resolve_expr(&expr, &mut |import| {
-        env.handle_import(import, |env, import| {
-            resolve_one_import(env, import, &root)
-        })
-    })?;
+    let resolved =
+        traverse_resolve_expr(&mut NameEnv::new(), &expr, &mut |import| {
+            env.handle_import(import, |env, import| {
+                resolve_one_import(env, import, &root)
+            })
+        })?;
     Ok(Resolved(resolved))
 }
 
-pub(crate) fn resolve(parsed: Parsed) -> Result<Resolved, ImportError> {
+pub(crate) fn resolve(parsed: Parsed) -> Result<Resolved, Error> {
     resolve_with_env(&mut ResolveEnv::new(), parsed)
 }
 
-pub(crate) fn skip_resolve_expr(
-    parsed: Parsed,
-) -> Result<Resolved, ImportError> {
+pub(crate) fn skip_resolve_expr(parsed: Parsed) -> Result<Resolved, Error> {
     let Parsed(expr, _) = parsed;
-    let resolved = traverse_resolve_expr(&expr, &mut |import| {
-        Err(ImportError::UnexpectedImport(import))
-    })?;
+    let resolved =
+        traverse_resolve_expr(&mut NameEnv::new(), &expr, &mut |import| {
+            Err(ImportError::UnexpectedImport(import).into())
+        })?;
     Ok(Resolved(resolved))
 }
 
diff --git a/dhall/src/semantics/tck/typecheck.rs b/dhall/src/semantics/tck/typecheck.rs
index 5b233f8..eb6a58c 100644
--- a/dhall/src/semantics/tck/typecheck.rs
+++ b/dhall/src/semantics/tck/typecheck.rs
@@ -43,7 +43,7 @@ fn function_check(a: Const, b: Const) -> Const {
     }
 }
 
-fn mkerr<T, S: ToString>(x: S) -> Result<T, TypeError> {
+pub fn mkerr<T, S: ToString>(x: S) -> Result<T, TypeError> {
     Err(TypeError::new(TypeMessage::Custom(x.to_string())))
 }
 
diff --git a/dhall/src/tests.rs b/dhall/src/tests.rs
index 6a67ddc..ad5fee5 100644
--- a/dhall/src/tests.rs
+++ b/dhall/src/tests.rs
@@ -48,9 +48,9 @@ use std::fs::{create_dir_all, read_to_string, File};
 use std::io::{Read, Write};
 use std::path::PathBuf;
 
-use crate::error::{Error, Result};
+use crate::error::{Error, ErrorKind, Result};
 use crate::syntax::binary;
-use crate::{Normalized, NormalizedExpr, Parsed, Resolved};
+use crate::{Normalized, NormalizedExpr, Parsed, Resolved, Typed};
 
 #[allow(dead_code)]
 enum Test {
@@ -96,9 +96,13 @@ impl TestFile {
     pub fn resolve(&self) -> Result<Resolved> {
         Ok(self.parse()?.resolve()?)
     }
+    /// Parse, resolve and tck the target file
+    pub fn typecheck(&self) -> Result<Typed> {
+        Ok(self.resolve()?.typecheck()?)
+    }
     /// Parse, resolve, tck and normalize the target file
     pub fn normalize(&self) -> Result<Normalized> {
-        Ok(self.resolve()?.typecheck()?.normalize())
+        Ok(self.typecheck()?.normalize())
     }
 
     /// If UPDATE_TEST_FILES=1, we overwrite the output files with our own output.
@@ -246,11 +250,11 @@ fn run_test(test: Test) -> Result<()> {
             expected.compare_debug(expr)?;
         }
         ParserFailure(expr, expected) => {
-            use std::io::ErrorKind;
+            use std::io;
             let err = expr.parse().unwrap_err();
-            match &err {
-                Error::Parse(_) => {}
-                Error::IO(e) if e.kind() == ErrorKind::InvalidData => {}
+            match err.kind() {
+                ErrorKind::Parse(_) => {}
+                ErrorKind::IO(e) if e.kind() == io::ErrorKind::InvalidData => {}
                 e => panic!("Expected parse error, got: {:?}", e),
             }
             expected.compare_ui(err)?;
@@ -282,11 +286,11 @@ fn run_test(test: Test) -> Result<()> {
             expected.compare_ui(err)?;
         }
         TypeInferenceSuccess(expr, expected) => {
-            let ty = expr.resolve()?.typecheck()?.get_type()?;
+            let ty = expr.typecheck()?.get_type()?;
             expected.compare(ty)?;
         }
         TypeInferenceFailure(expr, expected) => {
-            let err = expr.resolve()?.typecheck().unwrap_err();
+            let err = expr.typecheck().unwrap_err();
             expected.compare_ui(err)?;
         }
         Normalization(expr, expected) => {
diff --git a/dhall/tests/import/failure/cycle.txt b/dhall/tests/import/failure/cycle.txt
index 0a20503..4e9488e 100644
--- a/dhall/tests/import/failure/cycle.txt
+++ b/dhall/tests/import/failure/cycle.txt
@@ -1 +1 @@
-Recursive(Import { mode: Code, location: Local(Parent, FilePath { file_path: ["data", "cycle.dhall"] }), hash: None }, Resolve(Recursive(Import { mode: Code, location: Local(Parent, FilePath { file_path: ["failure", "cycle.dhall"] }), hash: None }, Resolve(ImportCycle([Import { mode: Code, location: Local(Parent, FilePath { file_path: ["data", "cycle.dhall"] }), hash: None }, Import { mode: Code, location: Local(Parent, FilePath { file_path: ["failure", "cycle.dhall"] }), hash: None }], Import { mode: Code, location: Local(Parent, FilePath { file_path: ["data", "cycle.dhall"] }), hash: None })))))
+ImportCycle([Import { mode: Code, location: Local(Parent, FilePath { file_path: ["data", "cycle.dhall"] }), hash: None }, Import { mode: Code, location: Local(Parent, FilePath { file_path: ["failure", "cycle.dhall"] }), hash: None }], Import { mode: Code, location: Local(Parent, FilePath { file_path: ["data", "cycle.dhall"] }), hash: None })
diff --git a/dhall/tests/import/failure/importBoundary.txt b/dhall/tests/import/failure/importBoundary.txt
index 8f78e48..6f0615d 100644
--- a/dhall/tests/import/failure/importBoundary.txt
+++ b/dhall/tests/import/failure/importBoundary.txt
@@ -1 +1,7 @@
-Recursive(Import { mode: Code, location: Local(Parent, FilePath { file_path: ["data", "importBoundary.dhall"] }), hash: None }, Typecheck(TypeError { message: Custom("error: unbound variable `x`\n --> <current file>:1:0\n  |\n...\n3 | x\n  | ^ not found in this scope\n  |") }))
+Type error: error: unbound variable `x`
+ --> <current file>:1:0
+  |
+...
+3 | x
+  | ^ not found in this scope
+  |