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') 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.2.3