From 8264df65c21b5ad508c5faf96c4a1f9d732449cc Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Mon, 17 Feb 2020 17:50:22 +0000 Subject: Move hir and resolve into a module --- dhall/src/semantics/resolve/resolve.rs | 264 +++++++++++++++++++++++++++++++++ 1 file changed, 264 insertions(+) create mode 100644 dhall/src/semantics/resolve/resolve.rs (limited to 'dhall/src/semantics/resolve/resolve.rs') 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; + +/// A root from which to resolve relative imports. +#[derive(Debug, Clone, PartialEq, Eq)] +pub(crate) enum ImportRoot { + LocalDir(PathBuf), +} + +type ImportCache = HashMap; + +pub(crate) type ImportStack = Vec; + +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, + ) -> Result { + 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 { + 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 { + 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, +) -> Result { + 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 { + 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 { + resolve_with_env(&mut ResolveEnv::new(), parsed) +} + +pub(crate) fn skip_resolve(expr: &ParsedExpr) -> Result { + 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 Canonicalize for ImportLocation { + fn canonicalize(&self) -> ImportLocation { + 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, + } + } +} -- cgit v1.2.3 From 8da4445e6d06cf79d43112042b69c798f86884f3 Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Mon, 17 Feb 2020 17:58:03 +0000 Subject: Extract resolve-relevant envs together --- dhall/src/semantics/resolve/resolve.rs | 63 ++++------------------------------ 1 file changed, 7 insertions(+), 56 deletions(-) (limited to 'dhall/src/semantics/resolve/resolve.rs') diff --git a/dhall/src/semantics/resolve/resolve.rs b/dhall/src/semantics/resolve/resolve.rs index 3038597..e3db014 100644 --- a/dhall/src/semantics/resolve/resolve.rs +++ b/dhall/src/semantics/resolve/resolve.rs @@ -1,14 +1,13 @@ -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::semantics::{mkerr, Hir, HirKind, ImportEnv, NameEnv}; use crate::syntax; use crate::syntax::{BinOp, Expr, ExprKind, FilePath, ImportLocation, URL}; use crate::{Parsed, ParsedExpr, Resolved}; -type Import = syntax::Import; +pub(crate) type Import = syntax::Import; /// A root from which to resolve relative imports. #[derive(Debug, Clone, PartialEq, Eq)] @@ -16,56 +15,8 @@ pub(crate) enum ImportRoot { LocalDir(PathBuf), } -type ImportCache = HashMap; - -pub(crate) type ImportStack = Vec; - -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, - ) -> Result { - 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, + env: &mut ImportEnv, import: &Import, root: &ImportRoot, ) -> Result { @@ -90,7 +41,7 @@ fn resolve_one_import( } } -fn load_import(env: &mut ResolveEnv, f: &Path) -> Result { +fn load_import(env: &mut ImportEnv, f: &Path) -> Result { let parsed = Parsed::parse_file(f)?; Ok(resolve_with_env(env, parsed)? .typecheck()? @@ -99,7 +50,7 @@ fn load_import(env: &mut ResolveEnv, f: &Path) -> Result { } /// Traverse the expression, handling import alternatives and passing -/// found imports to the provided function. +/// found imports to the provided function. Also resolving names. fn traverse_resolve_expr( name_env: &mut NameEnv, expr: &Expr, @@ -169,7 +120,7 @@ fn traverse_resolve_expr( } fn resolve_with_env( - env: &mut ResolveEnv, + env: &mut ImportEnv, parsed: Parsed, ) -> Result { let Parsed(expr, root) = parsed; @@ -183,7 +134,7 @@ fn resolve_with_env( } pub(crate) fn resolve(parsed: Parsed) -> Result { - resolve_with_env(&mut ResolveEnv::new(), parsed) + resolve_with_env(&mut ImportEnv::new(), parsed) } pub(crate) fn skip_resolve(expr: &ParsedExpr) -> Result { -- cgit v1.2.3 From 06714f925a6588ef5c262bb7a9cf3f9e40f13120 Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Mon, 17 Feb 2020 18:06:34 +0000 Subject: Factor out desugaring from resolve --- dhall/src/semantics/resolve/resolve.rs | 53 ++++++++++++++++++++-------------- 1 file changed, 31 insertions(+), 22 deletions(-) (limited to 'dhall/src/semantics/resolve/resolve.rs') diff --git a/dhall/src/semantics/resolve/resolve.rs b/dhall/src/semantics/resolve/resolve.rs index e3db014..22fb1a0 100644 --- a/dhall/src/semantics/resolve/resolve.rs +++ b/dhall/src/semantics/resolve/resolve.rs @@ -1,3 +1,4 @@ +use std::borrow::Cow; use std::path::{Path, PathBuf}; use crate::error::ErrorBuilder; @@ -49,6 +50,35 @@ fn load_import(env: &mut ImportEnv, f: &Path) -> Result { .to_hir()) } +/// Desugar the first level of the expression. +fn desugar(expr: &Expr) -> Cow<'_, Expr> { + match expr.kind() { + 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(), + ); + Cow::Owned(Expr::new( + ExprKind::Annot(merged, ty_field_type), + expr.span(), + )) + } + _ => Cow::Borrowed(expr), + } +} + /// Traverse the expression, handling import alternatives and passing /// found imports to the provided function. Also resolving names. fn traverse_resolve_expr( @@ -56,6 +86,7 @@ fn traverse_resolve_expr( expr: &Expr, f: &mut impl FnMut(Import) -> Result, ) -> Result { + let expr = desugar(expr); Ok(match expr.kind() { ExprKind::Var(var) => match name_env.unlabel_var(&var) { Some(v) => Hir::new(HirKind::Var(v), expr.span()), @@ -77,28 +108,6 @@ fn traverse_resolve_expr( } } } - // 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 { -- cgit v1.2.3 From a3990858840a737d7831be45953b38bd67361fb7 Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Tue, 18 Feb 2020 19:08:53 +0000 Subject: Discard import headers while we don't use them --- dhall/src/semantics/resolve/resolve.rs | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) (limited to 'dhall/src/semantics/resolve/resolve.rs') diff --git a/dhall/src/semantics/resolve/resolve.rs b/dhall/src/semantics/resolve/resolve.rs index 22fb1a0..23d4c3d 100644 --- a/dhall/src/semantics/resolve/resolve.rs +++ b/dhall/src/semantics/resolve/resolve.rs @@ -8,7 +8,8 @@ use crate::syntax; use crate::syntax::{BinOp, Expr, ExprKind, FilePath, ImportLocation, URL}; use crate::{Parsed, ParsedExpr, Resolved}; -pub(crate) type Import = syntax::Import; +// TODO: evaluate import headers +pub(crate) type Import = syntax::Import<()>; /// A root from which to resolve relative imports. #[derive(Debug, Clone, PartialEq, Eq)] @@ -120,7 +121,11 @@ fn traverse_resolve_expr( Ok::<_, Error>(hir) })?; let kind = match kind { - ExprKind::Import(import) => f(import)?.kind().clone(), + ExprKind::Import(import) => { + // TODO: evaluate import headers + let import = import.traverse_ref(|_| Ok::<_, Error>(()))?; + f(import)?.kind().clone() + } kind => HirKind::Expr(kind), }; Hir::new(kind, expr.span()) -- cgit v1.2.3 From 7cbfc1a0d32766a383d1f48902502adaa2234d2f Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Tue, 18 Feb 2020 19:12:31 +0000 Subject: Avoid re-typechecking after import --- dhall/src/semantics/resolve/resolve.rs | 20 +++++++++++--------- 1 file changed, 11 insertions(+), 9 deletions(-) (limited to 'dhall/src/semantics/resolve/resolve.rs') diff --git a/dhall/src/semantics/resolve/resolve.rs b/dhall/src/semantics/resolve/resolve.rs index 23d4c3d..82800ec 100644 --- a/dhall/src/semantics/resolve/resolve.rs +++ b/dhall/src/semantics/resolve/resolve.rs @@ -3,7 +3,7 @@ use std::path::{Path, PathBuf}; use crate::error::ErrorBuilder; use crate::error::{Error, ImportError}; -use crate::semantics::{mkerr, Hir, HirKind, ImportEnv, NameEnv}; +use crate::semantics::{mkerr, Hir, HirKind, ImportEnv, NameEnv, Type}; use crate::syntax; use crate::syntax::{BinOp, Expr, ExprKind, FilePath, ImportLocation, URL}; use crate::{Parsed, ParsedExpr, Resolved}; @@ -11,6 +11,9 @@ use crate::{Parsed, ParsedExpr, Resolved}; // TODO: evaluate import headers pub(crate) type Import = syntax::Import<()>; +/// Owned Hir with a type. Different from Tir because the Hir is owned. +pub(crate) type TypedHir = (Hir, Type); + /// A root from which to resolve relative imports. #[derive(Debug, Clone, PartialEq, Eq)] pub(crate) enum ImportRoot { @@ -21,7 +24,7 @@ fn resolve_one_import( env: &mut ImportEnv, import: &Import, root: &ImportRoot, -) -> Result { +) -> Result { use self::ImportRoot::*; use syntax::FilePrefix::*; use syntax::ImportLocation::*; @@ -43,12 +46,10 @@ fn resolve_one_import( } } -fn load_import(env: &mut ImportEnv, f: &Path) -> Result { +fn load_import(env: &mut ImportEnv, f: &Path) -> Result { let parsed = Parsed::parse_file(f)?; - Ok(resolve_with_env(env, parsed)? - .typecheck()? - .normalize() - .to_hir()) + let typed = resolve_with_env(env, parsed)?.typecheck()?; + Ok((typed.normalize().to_hir(), typed.ty().clone())) } /// Desugar the first level of the expression. @@ -85,7 +86,7 @@ fn desugar(expr: &Expr) -> Cow<'_, Expr> { fn traverse_resolve_expr( name_env: &mut NameEnv, expr: &Expr, - f: &mut impl FnMut(Import) -> Result, + f: &mut impl FnMut(Import) -> Result, ) -> Result { let expr = desugar(expr); Ok(match expr.kind() { @@ -124,7 +125,8 @@ fn traverse_resolve_expr( ExprKind::Import(import) => { // TODO: evaluate import headers let import = import.traverse_ref(|_| Ok::<_, Error>(()))?; - f(import)?.kind().clone() + let imported = f(import)?; + HirKind::Import(imported.0, imported.1) } kind => HirKind::Expr(kind), }; -- cgit v1.2.3