Move hir and resolve into a module

4 files changed, 400 insertions, 0 deletions

diff --git a/dhall/src/semantics/resolve/env.rs b/dhall/src/semantics/resolve/env.rs
new file mode 100644
index 0000000..e69de29
--- /dev/null
+++ b/dhall/src/semantics/resolve/env.rs
diff --git a/dhall/src/semantics/resolve/hir.rs b/dhall/src/semantics/resolve/hir.rs
new file mode 100644
index 0000000..b5db66f
--- /dev/null
+++ b/dhall/src/semantics/resolve/hir.rs
@@ -0,0 +1,130 @@
+use crate::error::TypeError;
+use crate::semantics::{type_with, NameEnv, NzEnv, TyEnv, TyExpr, Value};
+use crate::syntax::{Expr, ExprKind, Span, V};
+use crate::{NormalizedExpr, ToExprOptions};
+
+/// Stores an alpha-normalized variable.
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+pub struct AlphaVar {
+    idx: usize,
+}
+
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub(crate) enum HirKind {
+    /// A resolved variable (i.e. a DeBruijn index)
+    Var(AlphaVar),
+    // Forbidden ExprKind variants: Var, Import, Completion
+    Expr(ExprKind<Hir>),
+}
+
+// An expression with resolved variables and imports.
+#[derive(Debug, Clone)]
+pub(crate) struct Hir {
+    kind: Box<HirKind>,
+    span: Span,
+}
+
+impl AlphaVar {
+    pub(crate) fn new(idx: usize) -> Self {
+        AlphaVar { idx }
+    }
+    pub(crate) fn idx(&self) -> usize {
+        self.idx
+    }
+}
+
+impl Hir {
+    pub fn new(kind: HirKind, span: Span) -> Self {
+        Hir {
+            kind: Box::new(kind),
+            span,
+        }
+    }
+
+    pub fn kind(&self) -> &HirKind {
+        &*self.kind
+    }
+    pub fn span(&self) -> Span {
+        self.span.clone()
+    }
+
+    /// Converts a HIR expr back to the corresponding AST expression.
+    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,
+            alpha: false,
+        };
+        let mut env = env.as_nameenv().clone();
+        hir_to_expr(self, opts, &mut env)
+    }
+
+    /// Typecheck the Hir.
+    pub fn typecheck(&self, env: &TyEnv) -> Result<TyExpr, TypeError> {
+        type_with(env, self, None)
+    }
+
+    /// Eval the Hir. It will actually get evaluated only as needed on demand.
+    pub fn eval(&self, env: impl Into<NzEnv>) -> Value {
+        Value::new_thunk(env.into(), self.clone())
+    }
+}
+
+fn hir_to_expr(
+    hir: &Hir,
+    opts: ToExprOptions,
+    env: &mut NameEnv,
+) -> NormalizedExpr {
+    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) => {
+            let e = e.map_ref_maybe_binder(|l, hir| {
+                if let Some(l) = l {
+                    env.insert_mut(l);
+                }
+                let e = hir_to_expr(hir, opts, env);
+                if let Some(_) = l {
+                    env.remove_mut();
+                }
+                e
+            });
+
+            match e {
+                ExprKind::Lam(_, t, e) if opts.alpha => {
+                    ExprKind::Lam("_".into(), t, e)
+                }
+                ExprKind::Pi(_, t, e) if opts.alpha => {
+                    ExprKind::Pi("_".into(), t, e)
+                }
+                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/mod.rs b/dhall/src/semantics/resolve/mod.rs
new file mode 100644
index 0000000..c0486dd
--- /dev/null
+++ b/dhall/src/semantics/resolve/mod.rs
@@ -0,0 +1,6 @@
+pub mod env;
+pub mod resolve;
+pub mod hir;
+pub(crate) use env::*;
+pub(crate) use resolve::*;
+pub(crate) use hir::*;
diff --git a/dhall/src/semantics/resolve/resolve.rs b/dhall/src/semantics/resolve/resolve.rs
new file mode 100644
index 0000000..3038597
--- /dev/null
+++ b/dhall/src/semantics/resolve/resolve.rs
@@ -0,0 +1,264 @@
+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::{Parsed, ParsedExpr, Resolved};
+
+type Import = syntax::Import<Hir>;
+
+/// A root from which to resolve relative imports.
+#[derive(Debug, Clone, PartialEq, Eq)]
+pub(crate) enum ImportRoot {
+    LocalDir(PathBuf),
+}
+
+type ImportCache = HashMap<Import, Hir>;
+
+pub(crate) type ImportStack = Vec<Import>;
+
+struct ResolveEnv {
+    cache: ImportCache,
+    stack: ImportStack,
+}
+
+impl ResolveEnv {
+    pub fn new() -> Self {
+        ResolveEnv {
+            cache: HashMap::new(),
+            stack: Vec::new(),
+        }
+    }
+
+    pub fn handle_import(
+        &mut self,
+        import: Import,
+        mut do_resolve: impl FnMut(&mut Self, &Import) -> Result<Hir, Error>,
+    ) -> Result<Hir, Error> {
+        if self.stack.contains(&import) {
+            return Err(
+                ImportError::ImportCycle(self.stack.clone(), import).into()
+            );
+        }
+        Ok(match self.cache.get(&import) {
+            Some(expr) => expr.clone(),
+            None => {
+                // Push the current import on the stack
+                self.stack.push(import.clone());
+
+                // Resolve the import recursively
+                let expr = do_resolve(self, &import)?;
+
+                // Remove import from the stack.
+                self.stack.pop();
+
+                // Add the import to the cache
+                self.cache.insert(import, expr.clone());
+
+                expr
+            }
+        })
+    }
+}
+
+fn resolve_one_import(
+    env: &mut ResolveEnv,
+    import: &Import,
+    root: &ImportRoot,
+) -> Result<Hir, Error> {
+    use self::ImportRoot::*;
+    use syntax::FilePrefix::*;
+    use syntax::ImportLocation::*;
+    let cwd = match root {
+        LocalDir(cwd) => cwd,
+    };
+    match &import.location {
+        Local(prefix, path) => {
+            let path_buf: PathBuf = path.file_path.iter().collect();
+            let path_buf = match prefix {
+                // TODO: fail gracefully
+                Parent => cwd.parent().unwrap().join(path_buf),
+                Here => cwd.join(path_buf),
+                _ => unimplemented!("{:?}", import),
+            };
+            Ok(load_import(env, &path_buf)?)
+        }
+        _ => unimplemented!("{:?}", import),
+    }
+}
+
+fn load_import(env: &mut ResolveEnv, f: &Path) -> Result<Hir, Error> {
+    let parsed = Parsed::parse_file(f)?;
+    Ok(resolve_with_env(env, parsed)?
+        .typecheck()?
+        .normalize()
+        .to_hir())
+}
+
+/// Traverse the expression, handling import alternatives and passing
+/// found imports to the provided function.
+fn traverse_resolve_expr(
+    name_env: &mut NameEnv,
+    expr: &Expr,
+    f: &mut impl FnMut(Import) -> Result<Hir, Error>,
+) -> Result<Hir, Error> {
+    Ok(match expr.kind() {
+        ExprKind::Var(var) => match name_env.unlabel_var(&var) {
+            Some(v) => Hir::new(HirKind::Var(v), expr.span()),
+            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(name_env, l, f) {
+                Ok(l) => l,
+                Err(_) => {
+                    match traverse_resolve_expr(name_env, r, f) {
+                        Ok(r) => r,
+                        // TODO: keep track of the other error too
+                        Err(e) => return Err(e),
+                    }
+                }
+            }
+        }
+        // Desugar
+        ExprKind::Completion(ty, compl) => {
+            let ty_field_default = Expr::new(
+                ExprKind::Field(ty.clone(), "default".into()),
+                expr.span(),
+            );
+            let merged = Expr::new(
+                ExprKind::BinOp(
+                    BinOp::RightBiasedRecordMerge,
+                    ty_field_default,
+                    compl.clone(),
+                ),
+                expr.span(),
+            );
+            let ty_field_type = Expr::new(
+                ExprKind::Field(ty.clone(), "Type".into()),
+                expr.span(),
+            );
+            let desugared =
+                Expr::new(ExprKind::Annot(merged, ty_field_type), expr.span());
+            traverse_resolve_expr(name_env, &desugared, f)?
+        }
+        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)
+            })?;
+            let kind = match kind {
+                ExprKind::Import(import) => f(import)?.kind().clone(),
+                kind => HirKind::Expr(kind),
+            };
+            Hir::new(kind, expr.span())
+        }
+    })
+}
+
+fn resolve_with_env(
+    env: &mut ResolveEnv,
+    parsed: Parsed,
+) -> Result<Resolved, Error> {
+    let Parsed(expr, root) = parsed;
+    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, Error> {
+    resolve_with_env(&mut ResolveEnv::new(), parsed)
+}
+
+pub(crate) fn skip_resolve(expr: &ParsedExpr) -> Result<Hir, Error> {
+    traverse_resolve_expr(&mut NameEnv::new(), expr, &mut |import| {
+        Err(ImportError::UnexpectedImport(import).into())
+    })
+}
+
+pub trait Canonicalize {
+    fn canonicalize(&self) -> Self;
+}
+
+impl Canonicalize for FilePath {
+    fn canonicalize(&self) -> FilePath {
+        let mut file_path = Vec::new();
+        let mut file_path_components = self.file_path.clone().into_iter();
+
+        loop {
+            let component = file_path_components.next();
+            match component.as_ref() {
+                // ───────────────────
+                // canonicalize(ε) = ε
+                None => break,
+
+                // canonicalize(directory₀) = directory₁
+                // ───────────────────────────────────────
+                // canonicalize(directory₀/.) = directory₁
+                Some(c) if c == "." => continue,
+
+                Some(c) if c == ".." => match file_path_components.next() {
+                    // canonicalize(directory₀) = ε
+                    // ────────────────────────────
+                    // canonicalize(directory₀/..) = /..
+                    None => file_path.push("..".to_string()),
+
+                    // canonicalize(directory₀) = directory₁/..
+                    // ──────────────────────────────────────────────
+                    // canonicalize(directory₀/..) = directory₁/../..
+                    Some(ref c) if c == ".." => {
+                        file_path.push("..".to_string());
+                        file_path.push("..".to_string());
+                    }
+
+                    // canonicalize(directory₀) = directory₁/component
+                    // ───────────────────────────────────────────────  ; If "component" is not
+                    // canonicalize(directory₀/..) = directory₁         ; ".."
+                    Some(_) => continue,
+                },
+
+                // canonicalize(directory₀) = directory₁
+                // ─────────────────────────────────────────────────────────  ; If no other
+                // canonicalize(directory₀/component) = directory₁/component  ; rule matches
+                Some(c) => file_path.push(c.clone()),
+            }
+        }
+
+        FilePath { file_path }
+    }
+}
+
+impl<SE: Copy> Canonicalize for ImportLocation<SE> {
+    fn canonicalize(&self) -> ImportLocation<SE> {
+        match self {
+            ImportLocation::Local(prefix, file) => {
+                ImportLocation::Local(*prefix, file.canonicalize())
+            }
+            ImportLocation::Remote(url) => ImportLocation::Remote(URL {
+                scheme: url.scheme,
+                authority: url.authority.clone(),
+                path: url.path.canonicalize(),
+                query: url.query.clone(),
+                headers: url.headers.clone(),
+            }),
+            ImportLocation::Env(name) => ImportLocation::Env(name.to_string()),
+            ImportLocation::Missing => ImportLocation::Missing,
+        }
+    }
+}