From bbcb0c497dcf922d19bd529ceb936aff9d71a732 Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Sun, 9 Feb 2020 12:29:05 +0000 Subject: Introduce environment for import resolution --- dhall/src/semantics/resolve.rs | 87 +++++++++++++++++++++++++++--------------- 1 file changed, 56 insertions(+), 31 deletions(-) (limited to 'dhall/src/semantics/resolve.rs') diff --git a/dhall/src/semantics/resolve.rs b/dhall/src/semantics/resolve.rs index 3acf114..5ec6192 100644 --- a/dhall/src/semantics/resolve.rs +++ b/dhall/src/semantics/resolve.rs @@ -18,11 +18,42 @@ 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 to_import_stack(&self) -> ImportStack { + self.stack.clone() + } + pub fn check_cyclic_import(&self, import: &Import) -> bool { + self.stack.contains(import) + } + pub fn get_from_cache(&self, import: &Import) -> Option<&Normalized> { + self.cache.get(import) + } + pub fn push_on_stack(&mut self, import: Import) { + self.stack.push(import) + } + pub fn pop_from_stack(&mut self) { + self.stack.pop(); + } + pub fn insert_cache(&mut self, import: Import, expr: Normalized) { + self.cache.insert(import, expr); + } +} + fn resolve_import( + env: &mut ResolveEnv, import: &Import, root: &ImportRoot, - import_cache: &mut ImportCache, - import_stack: &ImportStack, ) -> Result { use self::ImportRoot::*; use syntax::FilePrefix::*; @@ -39,53 +70,47 @@ fn resolve_import( Here => cwd.join(path_buf), _ => unimplemented!("{:?}", import), }; - Ok(load_import(&path_buf, import_cache, import_stack).map_err( - |e| ImportError::Recursive(import.clone(), Box::new(e)), - )?) + Ok(load_import(env, &path_buf).map_err(|e| { + ImportError::Recursive(import.clone(), Box::new(e)) + })?) } _ => unimplemented!("{:?}", import), } } -fn load_import( - f: &Path, - import_cache: &mut ImportCache, - import_stack: &ImportStack, -) -> Result { - Ok( - do_resolve_expr(Parsed::parse_file(f)?, import_cache, import_stack)? - .typecheck()? - .normalize(), - ) +fn load_import(env: &mut ResolveEnv, f: &Path) -> Result { + Ok(do_resolve_expr(env, Parsed::parse_file(f)?)? + .typecheck()? + .normalize()) } fn do_resolve_expr( + env: &mut ResolveEnv, parsed: Parsed, - import_cache: &mut ImportCache, - import_stack: &ImportStack, ) -> Result { let Parsed(mut expr, root) = parsed; let mut resolve = |import: Import| -> Result { - if import_stack.contains(&import) { - return Err(ImportError::ImportCycle(import_stack.clone(), import)); + if env.check_cyclic_import(&import) { + return Err(ImportError::ImportCycle( + env.to_import_stack(), + import, + )); } - match import_cache.get(&import) { + match env.get_from_cache(&import) { Some(expr) => Ok(expr.clone()), None => { - // Copy the import stack and push the current import - let mut import_stack = import_stack.clone(); - import_stack.push(import.clone()); + // Push the current import on the stack + env.push_on_stack(import.clone()); // Resolve the import recursively - let expr = resolve_import( - &import, - &root, - import_cache, - &import_stack, - )?; + let expr = resolve_import(env, &import, &root)?; + + // Remove import from the stack. + env.pop_from_stack(); // Add the import to the cache - import_cache.insert(import, expr.clone()); + env.insert_cache(import, expr.clone()); + Ok(expr) } } @@ -95,7 +120,7 @@ fn do_resolve_expr( } pub(crate) fn resolve(e: Parsed) -> Result { - do_resolve_expr(e, &mut HashMap::new(), &Vec::new()) + do_resolve_expr(&mut ResolveEnv::new(), e) } pub(crate) fn skip_resolve_expr( -- cgit v1.3.1 From 5c342a5688fe7a4bb337ce0622968226d524022e Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Sun, 9 Feb 2020 15:32:27 +0000 Subject: Resolve by ref instead of by mut --- dhall/src/semantics/resolve.rs | 136 ++++++++++++++++++-------------- dhall/src/syntax/ast/expr.rs | 53 +------------ dhall/src/syntax/ast/visitor.rs | 166 ---------------------------------------- 3 files changed, 81 insertions(+), 274 deletions(-) (limited to 'dhall/src/semantics/resolve.rs') diff --git a/dhall/src/semantics/resolve.rs b/dhall/src/semantics/resolve.rs index 5ec6192..223cfa4 100644 --- a/dhall/src/semantics/resolve.rs +++ b/dhall/src/semantics/resolve.rs @@ -3,7 +3,7 @@ use std::path::{Path, PathBuf}; use crate::error::{Error, ImportError}; use crate::syntax; -use crate::syntax::{FilePath, ImportLocation, URL}; +use crate::syntax::{BinOp, Expr, ExprKind, FilePath, ImportLocation, URL}; use crate::{Normalized, NormalizedExpr, Parsed, Resolved}; type Import = syntax::Import; @@ -30,27 +30,40 @@ impl ResolveEnv { stack: Vec::new(), } } - pub fn to_import_stack(&self) -> ImportStack { - self.stack.clone() - } - pub fn check_cyclic_import(&self, import: &Import) -> bool { - self.stack.contains(import) - } - pub fn get_from_cache(&self, import: &Import) -> Option<&Normalized> { - self.cache.get(import) - } - pub fn push_on_stack(&mut self, import: Import) { - self.stack.push(import) - } - pub fn pop_from_stack(&mut self) { - self.stack.pop(); - } - pub fn insert_cache(&mut self, import: Import, expr: Normalized) { - self.cache.insert(import, expr); + + 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)); + } + 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_import( +fn resolve_one_import( env: &mut ResolveEnv, import: &Import, root: &ImportRoot, @@ -79,59 +92,64 @@ fn resolve_import( } fn load_import(env: &mut ResolveEnv, f: &Path) -> Result { - Ok(do_resolve_expr(env, Parsed::parse_file(f)?)? - .typecheck()? - .normalize()) + let parsed = Parsed::parse_file(f)?; + Ok(resolve_with_env(env, parsed)?.typecheck()?.normalize()) } -fn do_resolve_expr( +/// Traverse the expression, handling import alternatives and passing +/// found imports to the provided function. +fn traverse_resolve_expr( + expr: &Expr, + f: &mut impl FnMut(Import) -> Result, +) -> Result, ImportError> { + Ok(match expr.kind() { + ExprKind::BinOp(BinOp::ImportAlt, l, r) => { + match traverse_resolve_expr(l, f) { + Ok(l) => l, + Err(_) => { + match traverse_resolve_expr(r, f) { + Ok(r) => r, + // TODO: keep track of the other error too + Err(e) => return Err(e), + } + } + } + } + kind => { + let kind = kind.traverse_ref(|e| traverse_resolve_expr(e, f))?; + expr.rewrap(match kind { + ExprKind::Import(import) => ExprKind::Embed(f(import)?), + kind => kind, + }) + } + }) +} + +fn resolve_with_env( env: &mut ResolveEnv, parsed: Parsed, ) -> Result { - let Parsed(mut expr, root) = parsed; - let mut resolve = |import: Import| -> Result { - if env.check_cyclic_import(&import) { - return Err(ImportError::ImportCycle( - env.to_import_stack(), - import, - )); - } - match env.get_from_cache(&import) { - Some(expr) => Ok(expr.clone()), - None => { - // Push the current import on the stack - env.push_on_stack(import.clone()); - - // Resolve the import recursively - let expr = resolve_import(env, &import, &root)?; - - // Remove import from the stack. - env.pop_from_stack(); - - // Add the import to the cache - env.insert_cache(import, expr.clone()); - - Ok(expr) - } - } - }; - expr.traverse_resolve_mut(&mut resolve)?; - Ok(Resolved(expr)) + 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) + }) + })?; + Ok(Resolved(resolved)) } -pub(crate) fn resolve(e: Parsed) -> Result { - do_resolve_expr(&mut ResolveEnv::new(), e) +pub(crate) fn resolve(parsed: Parsed) -> Result { + resolve_with_env(&mut ResolveEnv::new(), parsed) } pub(crate) fn skip_resolve_expr( parsed: Parsed, ) -> Result { - let mut expr = parsed.0; - let mut resolve = |import: Import| -> Result { + let Parsed(expr, _) = parsed; + let resolved = traverse_resolve_expr(&expr, &mut |import| { Err(ImportError::UnexpectedImport(import)) - }; - expr.traverse_resolve_mut(&mut resolve)?; - Ok(Resolved(expr)) + })?; + Ok(Resolved(resolved)) } pub trait Canonicalize { diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs index b493fdb..420df5b 100644 --- a/dhall/src/syntax/ast/expr.rs +++ b/dhall/src/syntax/ast/expr.rs @@ -1,5 +1,5 @@ use crate::syntax::map::{DupTreeMap, DupTreeSet}; -use crate::syntax::visitor::{self, ExprKindMutVisitor, ExprKindVisitor}; +use crate::syntax::visitor::{self, ExprKindVisitor}; use crate::syntax::*; pub type Integer = isize; @@ -208,13 +208,6 @@ impl ExprKind { self.traverse_ref_maybe_binder(|_, e| visit_subexpr(e)) } - fn traverse_mut<'a, Err>( - &'a mut self, - visit_subexpr: impl FnMut(&'a mut SE) -> Result<(), Err>, - ) -> Result<(), Err> { - visitor::TraverseMutVisitor { visit_subexpr }.visit(self) - } - pub fn map_ref_maybe_binder<'a, SE2>( &'a self, mut map: impl FnMut(Option<&'a Label>, &'a SE) -> SE2, @@ -248,16 +241,15 @@ impl ExprKind { { self.map_ref_maybe_binder(|_, e| map_subexpr(e)) } - - pub fn map_mut<'a>(&'a mut self, mut map_subexpr: impl FnMut(&'a mut SE)) { - trivial_result(self.traverse_mut(|x| Ok(map_subexpr(x)))) - } } impl Expr { pub fn as_ref(&self) -> &UnspannedExpr { &self.kind } + pub fn kind(&self) -> &UnspannedExpr { + &self.kind + } pub fn span(&self) -> Span { self.span.clone() } @@ -281,43 +273,6 @@ impl Expr { span, } } - - pub fn traverse_resolve_mut( - &mut self, - f: &mut F1, - ) -> Result<(), Err> - where - E: Clone, - F1: FnMut(Import>) -> Result, - { - match self.kind.as_mut() { - ExprKind::BinOp(BinOp::ImportAlt, l, r) => { - let garbage_expr = ExprKind::BoolLit(false); - let new_self = if l.traverse_resolve_mut(f).is_ok() { - l - } else { - r.traverse_resolve_mut(f)?; - r - }; - *self.kind = - std::mem::replace(new_self.kind.as_mut(), garbage_expr); - } - _ => { - self.kind.traverse_mut(|e| e.traverse_resolve_mut(f))?; - if let ExprKind::Import(import) = self.kind.as_mut() { - let garbage_import = Import { - mode: ImportMode::Code, - location: ImportLocation::Missing, - hash: None, - }; - // Move out of &mut import - let import = std::mem::replace(import, garbage_import); - *self.kind = ExprKind::Embed(f(import)?); - } - } - } - Ok(()) - } } pub fn trivial_result(x: Result) -> T { diff --git a/dhall/src/syntax/ast/visitor.rs b/dhall/src/syntax/ast/visitor.rs index 6a1ce7d..c09b8d4 100644 --- a/dhall/src/syntax/ast/visitor.rs +++ b/dhall/src/syntax/ast/visitor.rs @@ -32,29 +32,6 @@ pub trait ExprKindVisitor<'a, SE1, SE2, E1, E2>: Sized { } } -/// Like `ExprKindVisitor`, but by mutable reference -pub trait ExprKindMutVisitor<'a, SE, E>: Sized { - type Error; - - fn visit_subexpr(&mut self, subexpr: &'a mut SE) - -> Result<(), Self::Error>; - fn visit_embed(self, _embed: &'a mut E) -> Result<(), Self::Error> { - Ok(()) - } - - fn visit_subexpr_under_binder( - mut self, - _label: &'a mut Label, - subexpr: &'a mut SE, - ) -> Result<(), Self::Error> { - self.visit_subexpr(subexpr) - } - - fn visit(self, input: &'a mut ExprKind) -> Result<(), Self::Error> { - visit_mut(self, input) - } -} - fn visit_ref<'a, V, SE1, SE2, E1, E2>( mut v: V, input: &'a ExprKind, @@ -174,128 +151,6 @@ where }) } -fn visit_mut<'a, V, SE, E>( - mut v: V, - input: &'a mut ExprKind, -) -> Result<(), V::Error> -where - V: ExprKindMutVisitor<'a, SE, E>, -{ - fn vec<'a, V, SE, E>(v: &mut V, x: &'a mut Vec) -> Result<(), V::Error> - where - V: ExprKindMutVisitor<'a, SE, E>, - { - for x in x { - v.visit_subexpr(x)?; - } - Ok(()) - } - fn opt<'a, V, SE, E>( - v: &mut V, - x: &'a mut Option, - ) -> Result<(), V::Error> - where - V: ExprKindMutVisitor<'a, SE, E>, - { - if let Some(x) = x { - v.visit_subexpr(x)?; - } - Ok(()) - } - fn dupmap<'a, V, SE, E>( - mut v: V, - x: impl IntoIterator, - ) -> Result<(), V::Error> - where - SE: 'a, - V: ExprKindMutVisitor<'a, SE, E>, - { - for (_, x) in x { - v.visit_subexpr(x)?; - } - Ok(()) - } - fn optdupmap<'a, V, SE, E>( - mut v: V, - x: impl IntoIterator)>, - ) -> Result<(), V::Error> - where - SE: 'a, - V: ExprKindMutVisitor<'a, SE, E>, - { - for (_, x) in x { - opt(&mut v, x)?; - } - Ok(()) - } - - use crate::syntax::ExprKind::*; - match input { - Var(_) | Const(_) | Builtin(_) | BoolLit(_) | NaturalLit(_) - | IntegerLit(_) | DoubleLit(_) => {} - Lam(l, t, e) => { - v.visit_subexpr(t)?; - v.visit_subexpr_under_binder(l, e)?; - } - Pi(l, t, e) => { - v.visit_subexpr(t)?; - v.visit_subexpr_under_binder(l, e)?; - } - Let(l, t, a, e) => { - opt(&mut v, t)?; - v.visit_subexpr(a)?; - v.visit_subexpr_under_binder(l, e)?; - } - App(f, a) => { - v.visit_subexpr(f)?; - v.visit_subexpr(a)?; - } - Annot(x, t) => { - v.visit_subexpr(x)?; - v.visit_subexpr(t)?; - } - TextLit(t) => t.traverse_mut(|e| v.visit_subexpr(e))?, - BinOp(_, x, y) => { - v.visit_subexpr(x)?; - v.visit_subexpr(y)?; - } - BoolIf(b, t, f) => { - v.visit_subexpr(b)?; - v.visit_subexpr(t)?; - v.visit_subexpr(f)?; - } - EmptyListLit(t) => v.visit_subexpr(t)?, - NEListLit(es) => vec(&mut v, es)?, - SomeLit(e) => v.visit_subexpr(e)?, - RecordType(kts) => dupmap(v, kts)?, - RecordLit(kvs) => dupmap(v, kvs)?, - UnionType(kts) => optdupmap(v, kts)?, - Merge(x, y, t) => { - v.visit_subexpr(x)?; - v.visit_subexpr(y)?; - opt(&mut v, t)?; - } - ToMap(x, t) => { - v.visit_subexpr(x)?; - opt(&mut v, t)?; - } - Field(e, _) => v.visit_subexpr(e)?, - Projection(e, _) => v.visit_subexpr(e)?, - ProjectionByExpr(e, x) => { - v.visit_subexpr(e)?; - v.visit_subexpr(x)?; - } - Completion(x, y) => { - v.visit_subexpr(x)?; - v.visit_subexpr(y)?; - } - Assert(e) => v.visit_subexpr(e)?, - Import(i) => i.traverse_mut(|e| v.visit_subexpr(e))?, - Embed(a) => v.visit_embed(a)?, - } - Ok(()) -} - pub struct TraverseRefMaybeBinderVisitor(pub F); impl<'a, SE, E, SE2, Err, F> ExprKindVisitor<'a, SE, SE2, E, E> @@ -321,24 +176,3 @@ where Ok(embed.clone()) } } - -pub struct TraverseMutVisitor { - pub visit_subexpr: F1, -} - -impl<'a, SE, E, Err, F1> ExprKindMutVisitor<'a, SE, E> - for TraverseMutVisitor -where - SE: 'a, - E: 'a, - F1: FnMut(&'a mut SE) -> Result<(), Err>, -{ - type Error = Err; - - fn visit_subexpr( - &mut self, - subexpr: &'a mut SE, - ) -> Result<(), Self::Error> { - (self.visit_subexpr)(subexpr) - } -} -- cgit v1.3.1 From a709c65eb28f1b6a666f15bfc2255da7bc7105ab Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Sun, 9 Feb 2020 21:38:37 +0000 Subject: Resolve variables alongside import resolution --- dhall/src/error/mod.rs | 56 ++++++++++------ dhall/src/lib.rs | 25 ++++--- dhall/src/semantics/hir.rs | 36 +++++++++-- dhall/src/semantics/resolve.rs | 93 ++++++++++++++++----------- dhall/src/semantics/tck/typecheck.rs | 2 +- dhall/src/tests.rs | 22 ++++--- dhall/tests/import/failure/cycle.txt | 2 +- dhall/tests/import/failure/importBoundary.txt | 8 ++- 8 files changed, 161 insertions(+), 83 deletions(-) (limited to 'dhall/src/semantics/resolve.rs') 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,17 +1,22 @@ 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::*; pub type Result = std::result::Result; +#[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, Box), - UnexpectedImport(Import), - ImportCycle(ImportStack, Import), +pub(crate) enum ImportError { + UnexpectedImport(Import), + ImportCycle(ImportStack, Import), } #[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 for Error { + fn from(kind: ErrorKind) -> Error { + Error::new(kind) + } +} impl From for Error { fn from(err: IOError) -> Error { - Error::IO(err) + ErrorKind::IO(err).into() } } impl From for Error { fn from(err: ParseError) -> Error { - Error::Parse(err) + ErrorKind::Parse(err).into() } } impl From for Error { fn from(err: DecodeError) -> Error { - Error::Decode(err) + ErrorKind::Decode(err).into() } } impl From for Error { fn from(err: EncodeError) -> Error { - Error::Encode(err) + ErrorKind::Encode(err).into() } } impl From for Error { fn from(err: ImportError) -> Error { - Error::Resolve(err) + ErrorKind::Resolve(err).into() } } impl From 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 { + pub fn resolve(self) -> Result { resolve::resolve(self) } - pub fn skip_resolve(self) -> Result { + pub fn skip_resolve(self) -> Result { resolve::skip_resolve_expr(self) } @@ -92,14 +94,14 @@ impl Parsed { impl Resolved { pub fn typecheck(&self) -> Result { - Ok(Typed(typecheck(&self.0)?)) + Ok(Typed(typecheck(&self.to_expr())?)) } pub fn typecheck_with(self, ty: &Normalized) -> Result { - 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(&self, state: &mut H) @@ -231,6 +232,12 @@ impl From 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(&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; +type Import = syntax::Import; /// 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, - ) -> Result { + mut do_resolve: impl FnMut(&mut Self, &Import) -> Result, + ) -> Result { 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 { +) -> Result { 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 { /// 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, ImportError> { - Ok(match expr.kind() { + f: &mut impl FnMut(Import) -> Result, +) -> Result { + 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 { +) -> Result { 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 { +pub(crate) fn resolve(parsed: Parsed) -> Result { resolve_with_env(&mut ResolveEnv::new(), parsed) } -pub(crate) fn skip_resolve_expr( - parsed: Parsed, -) -> Result { +pub(crate) fn skip_resolve_expr(parsed: Parsed) -> Result { 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(x: S) -> Result { +pub fn mkerr(x: S) -> Result { 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 { Ok(self.parse()?.resolve()?) } + /// Parse, resolve and tck the target file + pub fn typecheck(&self) -> Result { + Ok(self.resolve()?.typecheck()?) + } /// Parse, resolve, tck and normalize the target file pub fn normalize(&self) -> Result { - 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 --> :1:0\n |\n...\n3 | x\n | ^ not found in this scope\n |") })) +Type error: error: unbound variable `x` + --> :1:0 + | +... +3 | x + | ^ not found in this scope + | -- cgit v1.3.1 From 21db63d3e614554f258526182c7ed89a2c244b65 Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Sun, 9 Feb 2020 21:58:28 +0000 Subject: Take Hir for typecheck --- dhall/src/lib.rs | 10 ++++-- dhall/src/semantics/builtins.rs | 12 +++++--- dhall/src/semantics/mod.rs | 1 + dhall/src/semantics/nze/value.rs | 7 +++-- dhall/src/semantics/resolve.rs | 13 +++----- dhall/src/semantics/tck/env.rs | 12 +++----- dhall/src/semantics/tck/typecheck.rs | 60 +++++++++++++++++------------------- 7 files changed, 58 insertions(+), 57 deletions(-) (limited to 'dhall/src/semantics/resolve.rs') diff --git a/dhall/src/lib.rs b/dhall/src/lib.rs index c2a2f19..2d261f9 100644 --- a/dhall/src/lib.rs +++ b/dhall/src/lib.rs @@ -79,7 +79,7 @@ impl Parsed { resolve::resolve(self) } pub fn skip_resolve(self) -> Result { - resolve::skip_resolve_expr(self) + Ok(Resolved(resolve::skip_resolve(&self.0)?)) } pub fn encode(&self) -> Result, EncodeError> { @@ -94,10 +94,10 @@ impl Parsed { impl Resolved { pub fn typecheck(&self) -> Result { - Ok(Typed(typecheck(&self.to_expr())?)) + Ok(Typed(typecheck(&self.0)?)) } pub fn typecheck_with(self, ty: &Normalized) -> Result { - Ok(Typed(typecheck_with(&self.to_expr(), ty.to_expr())?)) + Ok(Typed(typecheck_with(&self.0, ty.to_hir())?)) } /// Converts a value back to the corresponding AST expression. pub fn to_expr(&self) -> ResolvedExpr { @@ -136,6 +136,10 @@ impl Normalized { normalize: false, }) } + /// Converts a value back to the corresponding Hir expression. + pub(crate) fn to_hir(&self) -> Hir { + self.0.to_hir_noenv() + } /// Converts a value back to the corresponding AST expression, alpha-normalizing in the process. pub(crate) fn to_expr_alpha(&self) -> NormalizedExpr { self.0.to_expr(ToExprOptions { diff --git a/dhall/src/semantics/builtins.rs b/dhall/src/semantics/builtins.rs index 715e045..b1d12aa 100644 --- a/dhall/src/semantics/builtins.rs +++ b/dhall/src/semantics/builtins.rs @@ -1,5 +1,5 @@ use crate::semantics::{ - typecheck, Hir, HirKind, NzEnv, Value, ValueKind, VarEnv, + skip_resolve, typecheck, Hir, HirKind, NzEnv, Value, ValueKind, VarEnv, }; use crate::syntax::map::DupTreeMap; use crate::syntax::Const::Type; @@ -115,9 +115,9 @@ macro_rules! make_type { }; } -pub(crate) fn type_of_builtin(b: Builtin) -> Expr { +pub(crate) fn type_of_builtin(b: Builtin) -> Hir { use Builtin::*; - match b { + let expr = match b { Bool | Natural | Integer | Double | Text => make_type!(Type), List | Optional => make_type!( Type -> Type @@ -200,7 +200,8 @@ pub(crate) fn type_of_builtin(b: Builtin) -> Expr { OptionalNone => make_type!( forall (A: Type) -> Optional A ), - } + }; + skip_resolve(&expr).unwrap() } // Ad-hoc macro to help construct closures @@ -264,7 +265,8 @@ fn apply_builtin(b: Builtin, args: Vec, env: NzEnv) -> ValueKind { Value(Value), DoneAsIs, } - let make_closure = |e| typecheck(&e).unwrap().eval(&env); + let make_closure = + |e| typecheck(&skip_resolve(&e).unwrap()).unwrap().eval(&env); let ret = match (b, args.as_slice()) { (OptionalNone, [t]) => Ret::ValueKind(EmptyOptionalLit(t.clone())), diff --git a/dhall/src/semantics/mod.rs b/dhall/src/semantics/mod.rs index a8c0659..ffa16ca 100644 --- a/dhall/src/semantics/mod.rs +++ b/dhall/src/semantics/mod.rs @@ -7,4 +7,5 @@ pub mod tck; pub(crate) use self::builtins::*; pub(crate) use self::hir::*; pub(crate) use self::nze::*; +pub(crate) use self::resolve::*; pub(crate) use self::tck::*; diff --git a/dhall/src/semantics/nze/value.rs b/dhall/src/semantics/nze/value.rs index a771b91..48acdb5 100644 --- a/dhall/src/semantics/nze/value.rs +++ b/dhall/src/semantics/nze/value.rs @@ -327,9 +327,12 @@ impl Value { Hir::new(hir, self.0.span.clone()) } + pub fn to_hir_noenv(&self) -> Hir { + self.to_hir(VarEnv::new()) + } pub fn to_tyexpr_tyenv(&self, tyenv: &TyEnv) -> TyExpr { - let expr = self.to_hir(tyenv.as_varenv()).to_expr_tyenv(tyenv); - type_with(tyenv, &expr).unwrap() + let hir = self.to_hir(tyenv.as_varenv()); + type_with(tyenv, &hir).unwrap() } pub fn to_tyexpr_noenv(&self) -> TyExpr { self.to_tyexpr_tyenv(&TyEnv::new()) diff --git a/dhall/src/semantics/resolve.rs b/dhall/src/semantics/resolve.rs index e12e892..8c9bb05 100644 --- a/dhall/src/semantics/resolve.rs +++ b/dhall/src/semantics/resolve.rs @@ -6,7 +6,7 @@ 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, Parsed, Resolved}; +use crate::{Normalized, Parsed, ParsedExpr, Resolved}; type Import = syntax::Import; @@ -162,13 +162,10 @@ pub(crate) fn resolve(parsed: Parsed) -> Result { resolve_with_env(&mut ResolveEnv::new(), parsed) } -pub(crate) fn skip_resolve_expr(parsed: Parsed) -> Result { - let Parsed(expr, _) = parsed; - let resolved = - traverse_resolve_expr(&mut NameEnv::new(), &expr, &mut |import| { - Err(ImportError::UnexpectedImport(import).into()) - })?; - Ok(Resolved(resolved)) +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 { diff --git a/dhall/src/semantics/tck/env.rs b/dhall/src/semantics/tck/env.rs index af955f4..3b02074 100644 --- a/dhall/src/semantics/tck/env.rs +++ b/dhall/src/semantics/tck/env.rs @@ -21,9 +21,9 @@ pub(crate) struct TyEnv { } impl VarEnv { - // pub fn new() -> Self { - // VarEnv { size: 0 } - // } + pub fn new() -> Self { + VarEnv { size: 0 } + } pub fn size(&self) -> usize { self.size } @@ -116,9 +116,7 @@ impl TyEnv { items: self.items.insert_value(e, ty), } } - pub fn lookup(&self, var: &V) -> Option<(AlphaVar, Type)> { - let var = self.names.unlabel_var(var)?; - let ty = self.items.lookup_ty(&var); - Some((var, ty)) + pub fn lookup(&self, var: &AlphaVar) -> Type { + self.items.lookup_ty(&var) } } diff --git a/dhall/src/semantics/tck/typecheck.rs b/dhall/src/semantics/tck/typecheck.rs index eb6a58c..ac113cd 100644 --- a/dhall/src/semantics/tck/typecheck.rs +++ b/dhall/src/semantics/tck/typecheck.rs @@ -5,11 +5,11 @@ use std::collections::HashMap; use crate::error::{ErrorBuilder, TypeError, TypeMessage}; use crate::semantics::merge_maps; use crate::semantics::{ - type_of_builtin, Binder, BuiltinClosure, Closure, TyEnv, TyExpr, - TyExprKind, Type, Value, ValueKind, + type_of_builtin, Binder, BuiltinClosure, Closure, Hir, HirKind, TyEnv, + TyExpr, TyExprKind, Type, Value, ValueKind, }; use crate::syntax::{ - BinOp, Builtin, Const, Expr, ExprKind, InterpolatedTextContents, Span, + BinOp, Builtin, Const, ExprKind, InterpolatedTextContents, Span, }; use crate::Normalized; @@ -115,8 +115,8 @@ fn type_one_layer( ExprKind::Const(Const::Type) => Value::from_const(Const::Kind), ExprKind::Const(Const::Kind) => Value::from_const(Const::Sort), ExprKind::Builtin(b) => { - let t_expr = type_of_builtin(*b); - let t_tyexpr = type_with(env, &t_expr)?; + let t_hir = type_of_builtin(*b); + let t_tyexpr = typecheck(&t_hir)?; t_tyexpr.eval(env.as_nzenv()) } ExprKind::BoolLit(_) => Value::from_builtin(Builtin::Bool), @@ -761,25 +761,16 @@ fn type_one_layer( } /// `type_with` typechecks an expressio in the provided environment. -pub(crate) fn type_with( - env: &TyEnv, - expr: &Expr, -) -> Result { - let (tyekind, ty) = match expr.as_ref() { - ExprKind::Var(var) => match env.lookup(&var) { - Some((v, ty)) => (TyExprKind::Var(v), Some(ty)), - None => { - return mkerr( - ErrorBuilder::new(format!("unbound variable `{}`", var)) - .span_err(expr.span(), "not found in this scope") - .format(), - ) - } - }, - ExprKind::Const(Const::Sort) => { +pub(crate) fn type_with(env: &TyEnv, hir: &Hir) -> Result { + let (tyekind, ty) = match hir.kind() { + HirKind::Var(var) => (TyExprKind::Var(*var), Some(env.lookup(&var))), + HirKind::Expr(ExprKind::Var(_)) => { + unreachable!("Hir should contain no unresolved variables") + } + HirKind::Expr(ExprKind::Const(Const::Sort)) => { (TyExprKind::Expr(ExprKind::Const(Const::Sort)), None) } - ExprKind::Embed(p) => { + HirKind::Expr(ExprKind::Embed(p)) => { let val = p.clone().into_value(); ( val.to_tyexpr_noenv().kind().clone(), @@ -787,7 +778,7 @@ pub(crate) fn type_with( ) // return Ok(p.clone().into_value().to_tyexpr_noenv()) } - ekind => { + HirKind::Expr(ekind) => { let ekind = match ekind { ExprKind::Lam(binder, annot, body) => { let annot = type_with(env, annot)?; @@ -805,7 +796,13 @@ pub(crate) fn type_with( } ExprKind::Let(binder, annot, val, body) => { let val = if let Some(t) = annot { - t.rewrap(ExprKind::Annot(val.clone(), t.clone())) + Hir::new( + HirKind::Expr(ExprKind::Annot( + val.clone(), + t.clone(), + )), + t.span(), + ) } else { val.clone() }; @@ -818,16 +815,16 @@ pub(crate) fn type_with( } _ => ekind.traverse_ref(|e| type_with(env, e))?, }; - return type_one_layer(env, ekind, expr.span()); + return type_one_layer(env, ekind, hir.span()); } }; - Ok(TyExpr::new(tyekind, ty, expr.span())) + Ok(TyExpr::new(tyekind, ty, hir.span())) } /// Typecheck an expression and return the expression annotated with types if type-checking /// succeeded, or an error if type-checking failed. -pub(crate) fn typecheck(e: &Expr) -> Result { +pub(crate) fn typecheck(e: &Hir) -> Result { let res = type_with(&TyEnv::new(), e)?; // Ensure that the inferred type exists (i.e. this is not Sort) res.get_type()?; @@ -835,9 +832,8 @@ pub(crate) fn typecheck(e: &Expr) -> Result { } /// Like `typecheck`, but additionally checks that the expression's type matches the provided type. -pub(crate) fn typecheck_with( - expr: &Expr, - ty: Expr, -) -> Result { - typecheck(&expr.rewrap(ExprKind::Annot(expr.clone(), ty))) +pub(crate) fn typecheck_with(hir: &Hir, ty: Hir) -> Result { + let hir = + Hir::new(HirKind::Expr(ExprKind::Annot(hir.clone(), ty)), hir.span()); + typecheck(&hir) } -- cgit v1.3.1 From c3ed75dc4b354becac0821e4288105dc2a300c4c Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Mon, 10 Feb 2020 19:14:07 +0000 Subject: Remove need for Embed This was an archaic leftover from copying the Haskell datatypes anyway --- dhall/src/semantics/hir.rs | 1 + dhall/src/semantics/nze/env.rs | 6 ++++++ dhall/src/semantics/resolve.rs | 25 ++++++++++++++----------- dhall/src/semantics/tck/typecheck.rs | 10 +--------- 4 files changed, 22 insertions(+), 20 deletions(-) (limited to 'dhall/src/semantics/resolve.rs') diff --git a/dhall/src/semantics/hir.rs b/dhall/src/semantics/hir.rs index 9ad7374..b45851f 100644 --- a/dhall/src/semantics/hir.rs +++ b/dhall/src/semantics/hir.rs @@ -11,6 +11,7 @@ pub struct AlphaVar { #[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, Embed Expr(ExprKind), diff --git a/dhall/src/semantics/nze/env.rs b/dhall/src/semantics/nze/env.rs index 5b036f0..241af40 100644 --- a/dhall/src/semantics/nze/env.rs +++ b/dhall/src/semantics/nze/env.rs @@ -86,3 +86,9 @@ impl ValEnv { } } } + +impl<'a> From<&'a NzEnv> for NzEnv { + fn from(x: &'a NzEnv) -> Self { + x.clone() + } +} diff --git a/dhall/src/semantics/resolve.rs b/dhall/src/semantics/resolve.rs index 8c9bb05..80e5132 100644 --- a/dhall/src/semantics/resolve.rs +++ b/dhall/src/semantics/resolve.rs @@ -16,7 +16,7 @@ pub(crate) enum ImportRoot { LocalDir(PathBuf), } -type ImportCache = HashMap; +type ImportCache = HashMap; pub(crate) type ImportStack = Vec; @@ -36,8 +36,8 @@ impl ResolveEnv { pub fn handle_import( &mut self, import: Import, - mut do_resolve: impl FnMut(&mut Self, &Import) -> Result, - ) -> Result { + mut do_resolve: impl FnMut(&mut Self, &Import) -> Result, + ) -> Result { if self.stack.contains(&import) { return Err( ImportError::ImportCycle(self.stack.clone(), import).into() @@ -68,7 +68,7 @@ fn resolve_one_import( env: &mut ResolveEnv, import: &Import, root: &ImportRoot, -) -> Result { +) -> Result { use self::ImportRoot::*; use syntax::FilePrefix::*; use syntax::ImportLocation::*; @@ -90,9 +90,12 @@ fn resolve_one_import( } } -fn load_import(env: &mut ResolveEnv, f: &Path) -> Result { +fn load_import(env: &mut ResolveEnv, f: &Path) -> Result { let parsed = Parsed::parse_file(f)?; - Ok(resolve_with_env(env, parsed)?.typecheck()?.normalize()) + Ok(resolve_with_env(env, parsed)? + .typecheck()? + .normalize() + .to_hir()) } /// Traverse the expression, handling import alternatives and passing @@ -100,7 +103,7 @@ fn load_import(env: &mut ResolveEnv, f: &Path) -> Result { fn traverse_resolve_expr( name_env: &mut NameEnv, expr: &Expr, - f: &mut impl FnMut(Import) -> Result, + f: &mut impl FnMut(Import) -> Result, ) -> Result { let kind = match expr.kind() { ExprKind::Var(var) => match name_env.unlabel_var(&var) { @@ -134,10 +137,10 @@ fn traverse_resolve_expr( } Ok::<_, Error>(hir) })?; - HirKind::Expr(match kind { - ExprKind::Import(import) => ExprKind::Embed(f(import)?), - kind => kind, - }) + match kind { + ExprKind::Import(import) => f(import)?.kind().clone(), + kind => HirKind::Expr(kind), + } } }; diff --git a/dhall/src/semantics/tck/typecheck.rs b/dhall/src/semantics/tck/typecheck.rs index 7f02832..4e45637 100644 --- a/dhall/src/semantics/tck/typecheck.rs +++ b/dhall/src/semantics/tck/typecheck.rs @@ -761,21 +761,13 @@ fn type_one_layer( /// `type_with` typechecks an expressio in the provided environment. pub(crate) fn type_with(env: &TyEnv, hir: &Hir) -> Result { let (tyekind, ty) = match hir.kind() { - HirKind::Var(var) => (TyExprKind::Var(*var), Some(env.lookup(&var))), + HirKind::Var(var) => (TyExprKind::Var(*var), Some(env.lookup(var))), HirKind::Expr(ExprKind::Var(_)) => { unreachable!("Hir should contain no unresolved variables") } HirKind::Expr(ExprKind::Const(Const::Sort)) => { (TyExprKind::Expr(ExprKind::Const(Const::Sort)), None) } - HirKind::Expr(ExprKind::Embed(p)) => { - let val = p.clone().into_value(); - ( - val.to_tyexpr_noenv().kind().clone(), - Some(val.get_type(&TyEnv::new())?), - ) - // return Ok(p.clone().into_value().to_tyexpr_noenv()) - } HirKind::Expr(ekind) => { let ekind = match ekind { ExprKind::Lam(binder, annot, body) => { -- cgit v1.3.1 From 5a2538d174fd36a8ed7f4fa344b9583fc48bd977 Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Tue, 11 Feb 2020 13:12:13 +0000 Subject: Remove the Embed variant from ExprKind --- dhall/src/lib.rs | 8 ++--- dhall/src/semantics/builtins.rs | 2 +- dhall/src/semantics/hir.rs | 8 ++--- dhall/src/semantics/nze/normalize.rs | 6 ++-- dhall/src/semantics/nze/value.rs | 16 ++++------ dhall/src/semantics/resolve.rs | 4 +-- dhall/src/semantics/tck/tyexpr.rs | 3 +- dhall/src/semantics/tck/typecheck.rs | 7 ++--- dhall/src/syntax/ast/expr.rs | 58 ++++++++++++------------------------ dhall/src/syntax/ast/visitor.rs | 30 ++++++++----------- dhall/src/syntax/binary/decode.rs | 2 +- dhall/src/syntax/binary/encode.rs | 44 ++++++++++----------------- dhall/src/syntax/text/parser.rs | 10 ++----- dhall/src/syntax/text/printer.rs | 17 +++++------ serde_dhall/src/serde.rs | 2 +- 15 files changed, 80 insertions(+), 137 deletions(-) (limited to 'dhall/src/semantics/resolve.rs') diff --git a/dhall/src/lib.rs b/dhall/src/lib.rs index 2d261f9..2f0ed4b 100644 --- a/dhall/src/lib.rs +++ b/dhall/src/lib.rs @@ -28,10 +28,10 @@ use crate::semantics::{ use crate::syntax::binary; use crate::syntax::{Builtin, Expr}; -pub type ParsedExpr = Expr; -pub type DecodedExpr = Expr; -pub type ResolvedExpr = Expr; -pub type NormalizedExpr = Expr; +pub type ParsedExpr = Expr; +pub type DecodedExpr = Expr; +pub type ResolvedExpr = Expr; +pub type NormalizedExpr = Expr; #[derive(Debug, Clone)] pub struct Parsed(ParsedExpr, ImportRoot); diff --git a/dhall/src/semantics/builtins.rs b/dhall/src/semantics/builtins.rs index d9a3599..cbb5a6e 100644 --- a/dhall/src/semantics/builtins.rs +++ b/dhall/src/semantics/builtins.rs @@ -55,7 +55,7 @@ impl BuiltinClosure { } } -pub(crate) fn rc(x: UnspannedExpr) -> Expr { +pub(crate) fn rc(x: UnspannedExpr) -> Expr { Expr::new(x, Span::Artificial) } diff --git a/dhall/src/semantics/hir.rs b/dhall/src/semantics/hir.rs index b45851f..288031c 100644 --- a/dhall/src/semantics/hir.rs +++ b/dhall/src/semantics/hir.rs @@ -1,7 +1,7 @@ #![allow(dead_code)] use crate::semantics::{NameEnv, NzEnv, TyEnv, Value}; -use crate::syntax::{ExprKind, Span, V}; -use crate::{Expr, Normalized, NormalizedExpr, ToExprOptions}; +use crate::syntax::{Expr, ExprKind, Span, V}; +use crate::{NormalizedExpr, ToExprOptions}; /// Stores an alpha-normalized variable. #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] @@ -13,8 +13,8 @@ pub struct AlphaVar { pub(crate) enum HirKind { /// A resolved variable (i.e. a DeBruijn index) Var(AlphaVar), - // Forbidden ExprKind variants: Var, Import, Embed - Expr(ExprKind), + // Forbidden ExprKind variants: Var, Import + Expr(ExprKind), } // An expression with resolved variables and imports. diff --git a/dhall/src/semantics/nze/normalize.rs b/dhall/src/semantics/nze/normalize.rs index d12146a..03b91a5 100644 --- a/dhall/src/semantics/nze/normalize.rs +++ b/dhall/src/semantics/nze/normalize.rs @@ -6,7 +6,6 @@ use crate::semantics::{ Binder, BuiltinClosure, Closure, Hir, HirKind, TextLit, Value, ValueKind, }; use crate::syntax::{BinOp, Builtin, ExprKind, InterpolatedTextContents}; -use crate::Normalized; pub(crate) fn apply_any(f: Value, a: Value) -> ValueKind { match f.kind() { @@ -90,7 +89,7 @@ enum Ret<'a> { ValueKind(ValueKind), Value(Value), ValueRef(&'a Value), - Expr(ExprKind), + Expr(ExprKind), } fn apply_binop<'a>(o: BinOp, x: &'a Value, y: &'a Value) -> Option> { @@ -215,7 +214,7 @@ fn apply_binop<'a>(o: BinOp, x: &'a Value, y: &'a Value) -> Option> { } pub(crate) fn normalize_one_layer( - expr: ExprKind, + expr: ExprKind, env: &NzEnv, ) -> ValueKind { use ValueKind::{ @@ -233,7 +232,6 @@ pub(crate) fn normalize_one_layer( ExprKind::Lam(..) | ExprKind::Pi(..) | ExprKind::Let(..) - | ExprKind::Embed(_) | ExprKind::Var(_) => { unreachable!("This case should have been handled in typecheck") } diff --git a/dhall/src/semantics/nze/value.rs b/dhall/src/semantics/nze/value.rs index a60be9d..0df3c74 100644 --- a/dhall/src/semantics/nze/value.rs +++ b/dhall/src/semantics/nze/value.rs @@ -12,7 +12,7 @@ use crate::syntax::{ BinOp, Builtin, Const, ExprKind, Integer, InterpolatedTextContents, Label, NaiveDouble, Natural, Span, }; -use crate::{Normalized, NormalizedExpr, ToExprOptions}; +use crate::{NormalizedExpr, ToExprOptions}; /// Stores a possibly unevaluated value. Gets (partially) normalized on-demand, sharing computation /// automatically. Uses a Rc to share computation. @@ -34,10 +34,7 @@ pub(crate) enum Thunk { /// A completely unnormalized expression. Thunk { env: NzEnv, body: Hir }, /// A partially normalized expression that may need to go through `normalize_one_layer`. - PartialExpr { - env: NzEnv, - expr: ExprKind, - }, + PartialExpr { env: NzEnv, expr: ExprKind }, } /// An unevaluated subexpression that takes an argument. @@ -96,7 +93,7 @@ pub(crate) enum ValueKind { TextLit(TextLit), Equivalence(Value, Value), /// Invariant: evaluation must not be able to progress with `normalize_one_layer`? - PartialExpr(ExprKind), + PartialExpr(ExprKind), } impl Value { @@ -106,7 +103,7 @@ impl Value { ValueInternal::from_thunk(Thunk::new(env, hir), span).into_value() } /// Construct a Value from a partially normalized expression that's not in WHNF. - pub(crate) fn from_partial_expr(e: ExprKind) -> Value { + pub(crate) fn from_partial_expr(e: ExprKind) -> Value { // TODO: env let env = NzEnv::new(); ValueInternal::from_thunk( @@ -389,10 +386,7 @@ impl Thunk { fn new(env: NzEnv, body: Hir) -> Self { Thunk::Thunk { env, body } } - fn from_partial_expr( - env: NzEnv, - expr: ExprKind, - ) -> Self { + fn from_partial_expr(env: NzEnv, expr: ExprKind) -> Self { Thunk::PartialExpr { env, expr } } fn eval(self) -> ValueKind { diff --git a/dhall/src/semantics/resolve.rs b/dhall/src/semantics/resolve.rs index 80e5132..fac88d2 100644 --- a/dhall/src/semantics/resolve.rs +++ b/dhall/src/semantics/resolve.rs @@ -6,7 +6,7 @@ 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, Parsed, ParsedExpr, Resolved}; +use crate::{Parsed, ParsedExpr, Resolved}; type Import = syntax::Import; @@ -102,7 +102,7 @@ fn load_import(env: &mut ResolveEnv, f: &Path) -> Result { /// found imports to the provided function. fn traverse_resolve_expr( name_env: &mut NameEnv, - expr: &Expr, + expr: &Expr, f: &mut impl FnMut(Import) -> Result, ) -> Result { let kind = match expr.kind() { diff --git a/dhall/src/semantics/tck/tyexpr.rs b/dhall/src/semantics/tck/tyexpr.rs index a1666a4..d46ab87 100644 --- a/dhall/src/semantics/tck/tyexpr.rs +++ b/dhall/src/semantics/tck/tyexpr.rs @@ -1,7 +1,6 @@ use crate::error::{TypeError, TypeMessage}; use crate::semantics::{AlphaVar, Hir, HirKind, NzEnv, Value}; use crate::syntax::{ExprKind, Span}; -use crate::Normalized; use crate::{NormalizedExpr, ToExprOptions}; pub(crate) type Type = Value; @@ -10,7 +9,7 @@ pub(crate) type Type = Value; pub(crate) enum TyExprKind { Var(AlphaVar), // Forbidden ExprKind variants: Var, Import, Embed - Expr(ExprKind), + Expr(ExprKind), } // An expression with inferred types at every node and resolved variables. diff --git a/dhall/src/semantics/tck/typecheck.rs b/dhall/src/semantics/tck/typecheck.rs index 4e45637..f9ff3d3 100644 --- a/dhall/src/semantics/tck/typecheck.rs +++ b/dhall/src/semantics/tck/typecheck.rs @@ -11,7 +11,6 @@ use crate::semantics::{ use crate::syntax::{ BinOp, Builtin, Const, ExprKind, InterpolatedTextContents, Span, }; -use crate::Normalized; fn type_of_recordtype<'a>( span: Span, @@ -51,7 +50,7 @@ pub fn mkerr(x: S) -> Result { /// layer. fn type_one_layer( env: &TyEnv, - ekind: ExprKind, + ekind: ExprKind, span: Span, ) -> Result { let span_err = |msg: &str| { @@ -66,9 +65,7 @@ fn type_one_layer( ExprKind::Import(..) => unreachable!( "There should remain no imports in a resolved expression" ), - ExprKind::Var(..) - | ExprKind::Const(Const::Sort) - | ExprKind::Embed(..) => unreachable!(), // Handled in type_with + ExprKind::Var(..) | ExprKind::Const(Const::Sort) => unreachable!(), // Handled in type_with ExprKind::Lam(binder, annot, body) => { let body_ty = body.get_type()?; diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs index 420df5b..722630f 100644 --- a/dhall/src/syntax/ast/expr.rs +++ b/dhall/src/syntax/ast/expr.rs @@ -96,19 +96,19 @@ pub enum Builtin { // Each node carries an annotation. #[derive(Debug, Clone)] -pub struct Expr { - kind: Box, Embed>>, +pub struct Expr { + kind: Box>, span: Span, } -pub type UnspannedExpr = ExprKind, Embed>; +pub type UnspannedExpr = ExprKind; /// Syntax tree for expressions // Having the recursion out of the enum definition enables writing // much more generic code and improves pattern-matching behind // smart pointers. #[derive(Debug, Clone, PartialEq, Eq, Hash)] -pub enum ExprKind { +pub enum ExprKind { Const(Const), /// `x` /// `x@n` @@ -169,18 +169,13 @@ pub enum ExprKind { Completion(SubExpr, SubExpr), /// `./some/path` Import(Import), - /// Embeds the result of resolving an import - Embed(Embed), } -impl ExprKind { +impl ExprKind { pub fn traverse_ref_maybe_binder<'a, SE2, Err>( &'a self, visit: impl FnMut(Option<&'a Label>, &'a SE) -> Result, - ) -> Result, Err> - where - E: Clone, - { + ) -> Result, Err> { visitor::TraverseRefMaybeBinderVisitor(visit).visit(self) } @@ -188,10 +183,7 @@ impl ExprKind { &'a self, mut visit_subexpr: impl FnMut(&'a SE) -> Result, mut visit_under_binder: impl FnMut(&'a Label, &'a SE) -> Result, - ) -> Result, Err> - where - E: Clone, - { + ) -> Result, Err> { self.traverse_ref_maybe_binder(|l, x| match l { None => visit_subexpr(x), Some(l) => visit_under_binder(l, x), @@ -201,20 +193,14 @@ impl ExprKind { pub(crate) fn traverse_ref<'a, SE2, Err>( &'a self, mut visit_subexpr: impl FnMut(&'a SE) -> Result, - ) -> Result, Err> - where - E: Clone, - { + ) -> Result, Err> { self.traverse_ref_maybe_binder(|_, e| visit_subexpr(e)) } pub fn map_ref_maybe_binder<'a, SE2>( &'a self, mut map: impl FnMut(Option<&'a Label>, &'a SE) -> SE2, - ) -> ExprKind - where - E: Clone, - { + ) -> ExprKind { trivial_result(self.traverse_ref_maybe_binder(|l, x| Ok(map(l, x)))) } @@ -222,10 +208,7 @@ impl ExprKind { &'a self, mut map_subexpr: impl FnMut(&'a SE) -> SE2, mut map_under_binder: impl FnMut(&'a Label, &'a SE) -> SE2, - ) -> ExprKind - where - E: Clone, - { + ) -> ExprKind { self.map_ref_maybe_binder(|l, x| match l { None => map_subexpr(x), Some(l) => map_under_binder(l, x), @@ -235,33 +218,30 @@ impl ExprKind { pub fn map_ref<'a, SE2>( &'a self, mut map_subexpr: impl FnMut(&'a SE) -> SE2, - ) -> ExprKind - where - E: Clone, - { + ) -> ExprKind { self.map_ref_maybe_binder(|_, e| map_subexpr(e)) } } -impl Expr { - pub fn as_ref(&self) -> &UnspannedExpr { +impl Expr { + pub fn as_ref(&self) -> &UnspannedExpr { &self.kind } - pub fn kind(&self) -> &UnspannedExpr { + pub fn kind(&self) -> &UnspannedExpr { &self.kind } pub fn span(&self) -> Span { self.span.clone() } - pub fn new(kind: UnspannedExpr, span: Span) -> Self { + pub fn new(kind: UnspannedExpr, span: Span) -> Self { Expr { kind: Box::new(kind), span, } } - pub fn rewrap(&self, kind: UnspannedExpr) -> Expr { + pub fn rewrap(&self, kind: UnspannedExpr) -> Expr { Expr { kind: Box::new(kind), span: self.span.clone(), @@ -317,15 +297,15 @@ impl From