From 6c90d356c9a4a5bbeb88f25ad0ab499ba1503eae Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Sun, 9 Feb 2020 11:53:55 +0000 Subject: Remove most TyExpr from normalization --- .../type-inference/failure/unit/AnnotationRecordWrongFieldName.txt | 4 ++-- .../type-inference/failure/unit/AnnotationRecordWrongFieldType.txt | 4 ++-- .../type-inference/failure/unit/CompletionMissingRequiredField.txt | 4 ++-- .../type-inference/failure/unit/CompletionWithWrongDefaultType.txt | 4 ++-- .../type-inference/failure/unit/CompletionWithWrongFieldName.txt | 4 ++-- .../type-inference/failure/unit/CompletionWithWrongOverridenType.txt | 4 ++-- dhall/tests/type-inference/failure/unit/LetWithWrongAnnotation.txt | 4 ++-- .../type-inference/failure/unit/OptionalDeprecatedSyntaxPresent.txt | 4 ++-- dhall/tests/type-inference/failure/unit/TypeAnnotationWrong.txt | 4 ++-- 9 files changed, 18 insertions(+), 18 deletions(-) (limited to 'dhall/tests') diff --git a/dhall/tests/type-inference/failure/unit/AnnotationRecordWrongFieldName.txt b/dhall/tests/type-inference/failure/unit/AnnotationRecordWrongFieldName.txt index 2a754fc..01a1f32 100644 --- a/dhall/tests/type-inference/failure/unit/AnnotationRecordWrongFieldName.txt +++ b/dhall/tests/type-inference/failure/unit/AnnotationRecordWrongFieldName.txt @@ -1,6 +1,6 @@ -Type error: error: annot mismatch: ({ x = 1 } : { x : Natural }) : { y : Natural } +Type error: error: annot mismatch: { x : Natural } != { y : Natural } --> :1:0 | 1 | { x = 1 } : { y : Natural } - | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ annot mismatch: ({ x = 1 } : { x : Natural }) : { y : Natural } + | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ annot mismatch: { x : Natural } != { y : Natural } | diff --git a/dhall/tests/type-inference/failure/unit/AnnotationRecordWrongFieldType.txt b/dhall/tests/type-inference/failure/unit/AnnotationRecordWrongFieldType.txt index e67edb8..5c10467 100644 --- a/dhall/tests/type-inference/failure/unit/AnnotationRecordWrongFieldType.txt +++ b/dhall/tests/type-inference/failure/unit/AnnotationRecordWrongFieldType.txt @@ -1,6 +1,6 @@ -Type error: error: annot mismatch: ({ x = 1 } : { x : Natural }) : { x : Text } +Type error: error: annot mismatch: { x : Natural } != { x : Text } --> :1:0 | 1 | { x = 1 } : { x : Text } - | ^^^^^^^^^^^^^^^^^^^^^^^^ annot mismatch: ({ x = 1 } : { x : Natural }) : { x : Text } + | ^^^^^^^^^^^^^^^^^^^^^^^^ annot mismatch: { x : Natural } != { x : Text } | diff --git a/dhall/tests/type-inference/failure/unit/CompletionMissingRequiredField.txt b/dhall/tests/type-inference/failure/unit/CompletionMissingRequiredField.txt index d0a9a01..7a4a12c 100644 --- a/dhall/tests/type-inference/failure/unit/CompletionMissingRequiredField.txt +++ b/dhall/tests/type-inference/failure/unit/CompletionMissingRequiredField.txt @@ -1,7 +1,7 @@ -Type error: error: annot mismatch: (Example.default ⫽ {=} : { id : Optional Natural }) : { id : Optional Natural, name : Text } +Type error: error: annot mismatch: { id : Optional Natural } != { id : Optional Natural, name : Text } --> :1:4 | ... 6 | in Example::{=} - | ^^^^^^^^^^^^ annot mismatch: (Example.default ⫽ {=} : { id : Optional Natural }) : { id : Optional Natural, name : Text } + | ^^^^^^^^^^^^ annot mismatch: { id : Optional Natural } != { id : Optional Natural, name : Text } | diff --git a/dhall/tests/type-inference/failure/unit/CompletionWithWrongDefaultType.txt b/dhall/tests/type-inference/failure/unit/CompletionWithWrongDefaultType.txt index d4639e9..9235ed4 100644 --- a/dhall/tests/type-inference/failure/unit/CompletionWithWrongDefaultType.txt +++ b/dhall/tests/type-inference/failure/unit/CompletionWithWrongDefaultType.txt @@ -1,7 +1,7 @@ -Type error: error: annot mismatch: (Example.default ⫽ {=} : { id : Optional Natural, name : Bool }) : { id : Optional Natural, name : Text } +Type error: error: annot mismatch: { id : Optional Natural, name : Bool } != { id : Optional Natural, name : Text } --> :1:4 | ... 6 | in Example::{=} - | ^^^^^^^^^^^^ annot mismatch: (Example.default ⫽ {=} : { id : Optional Natural, name : Bool }) : { id : Optional Natural, name : Text } + | ^^^^^^^^^^^^ annot mismatch: { id : Optional Natural, name : Bool } != { id : Optional Natural, name : Text } | diff --git a/dhall/tests/type-inference/failure/unit/CompletionWithWrongFieldName.txt b/dhall/tests/type-inference/failure/unit/CompletionWithWrongFieldName.txt index 0839742..6a6cd1e 100644 --- a/dhall/tests/type-inference/failure/unit/CompletionWithWrongFieldName.txt +++ b/dhall/tests/type-inference/failure/unit/CompletionWithWrongFieldName.txt @@ -1,7 +1,7 @@ -Type error: error: annot mismatch: (Example.default ⫽ { nam = "John Doe" } : { id : Optional Natural, nam : Text, name : Text }) : { id : Optional Natural, name : Text } +Type error: error: annot mismatch: { id : Optional Natural, nam : Text, name : Text } != { id : Optional Natural, name : Text } --> :1:4 | ... 6 | in Example::{ nam = "John Doe" } - | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ annot mismatch: (Example.default ⫽ { nam = "John Doe" } : { id : Optional Natural, nam : Text, name : Text }) : { id : Optional Natural, name : Text } + | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ annot mismatch: { id : Optional Natural, nam : Text, name : Text } != { id : Optional Natural, name : Text } | diff --git a/dhall/tests/type-inference/failure/unit/CompletionWithWrongOverridenType.txt b/dhall/tests/type-inference/failure/unit/CompletionWithWrongOverridenType.txt index 7edef95..b4fe726 100644 --- a/dhall/tests/type-inference/failure/unit/CompletionWithWrongOverridenType.txt +++ b/dhall/tests/type-inference/failure/unit/CompletionWithWrongOverridenType.txt @@ -1,7 +1,7 @@ -Type error: error: annot mismatch: (Example.default ⫽ { name = True } : { id : Optional Natural, name : Bool }) : { id : Optional Natural, name : Text } +Type error: error: annot mismatch: { id : Optional Natural, name : Bool } != { id : Optional Natural, name : Text } --> :1:4 | ... 6 | in Example::{ name = True } - | ^^^^^^^^^^^^^^^^^^^^^^^^ annot mismatch: (Example.default ⫽ { name = True } : { id : Optional Natural, name : Bool }) : { id : Optional Natural, name : Text } + | ^^^^^^^^^^^^^^^^^^^^^^^^ annot mismatch: { id : Optional Natural, name : Bool } != { id : Optional Natural, name : Text } | diff --git a/dhall/tests/type-inference/failure/unit/LetWithWrongAnnotation.txt b/dhall/tests/type-inference/failure/unit/LetWithWrongAnnotation.txt index 5ba4b35..2f75196 100644 --- a/dhall/tests/type-inference/failure/unit/LetWithWrongAnnotation.txt +++ b/dhall/tests/type-inference/failure/unit/LetWithWrongAnnotation.txt @@ -1,6 +1,6 @@ -Type error: error: annot mismatch: (True : Bool) : Natural +Type error: error: annot mismatch: Bool != Natural --> :1:8 | 1 | let x : Natural = True in True - | ^^^^^^^ annot mismatch: (True : Bool) : Natural + | ^^^^^^^ annot mismatch: Bool != Natural | diff --git a/dhall/tests/type-inference/failure/unit/OptionalDeprecatedSyntaxPresent.txt b/dhall/tests/type-inference/failure/unit/OptionalDeprecatedSyntaxPresent.txt index 5332fcb..066e4a3 100644 --- a/dhall/tests/type-inference/failure/unit/OptionalDeprecatedSyntaxPresent.txt +++ b/dhall/tests/type-inference/failure/unit/OptionalDeprecatedSyntaxPresent.txt @@ -1,6 +1,6 @@ -Type error: error: annot mismatch: ([1] : List Natural) : Optional Natural +Type error: error: annot mismatch: List Natural != Optional Natural --> :1:0 | 1 | [ 1 ] : Optional Natural - | ^^^^^^^^^^^^^^^^^^^^^^^^ annot mismatch: ([1] : List Natural) : Optional Natural + | ^^^^^^^^^^^^^^^^^^^^^^^^ annot mismatch: List Natural != Optional Natural | diff --git a/dhall/tests/type-inference/failure/unit/TypeAnnotationWrong.txt b/dhall/tests/type-inference/failure/unit/TypeAnnotationWrong.txt index 7360e68..e203d22 100644 --- a/dhall/tests/type-inference/failure/unit/TypeAnnotationWrong.txt +++ b/dhall/tests/type-inference/failure/unit/TypeAnnotationWrong.txt @@ -1,6 +1,6 @@ -Type error: error: annot mismatch: (1 : Natural) : Bool +Type error: error: annot mismatch: Natural != Bool --> :1:0 | 1 | 1 : Bool - | ^^^^^^^^ annot mismatch: (1 : Natural) : Bool + | ^^^^^^^^ annot mismatch: Natural != Bool | -- 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/tests') 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 f29a40fb55b898b3a3cc51f198e8522eaecf0777 Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Thu, 13 Feb 2020 20:17:41 +0000 Subject: Simplify conversions to/from TyExpr --- dhall/src/semantics/hir.rs | 8 +- dhall/src/semantics/nze/value.rs | 20 +-- dhall/src/semantics/tck/tyexpr.rs | 11 +- dhall/src/semantics/tck/typecheck.rs | 157 +++++++++------------ .../unit/RecursiveRecordMergeLhsNotRecord.txt | 5 + .../unit/RecursiveRecordMergeOverlapping.txt | 5 + .../unit/RecursiveRecordMergeRhsNotRecord.txt | 5 + .../unit/RecursiveRecordTypeMergeOverlapping.txt | 5 + 8 files changed, 108 insertions(+), 108 deletions(-) (limited to 'dhall/tests') diff --git a/dhall/src/semantics/hir.rs b/dhall/src/semantics/hir.rs index 288031c..f91aa73 100644 --- a/dhall/src/semantics/hir.rs +++ b/dhall/src/semantics/hir.rs @@ -1,5 +1,6 @@ #![allow(dead_code)] -use crate::semantics::{NameEnv, NzEnv, TyEnv, Value}; +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}; @@ -69,6 +70,11 @@ impl Hir { hir_to_expr(self, opts, &mut env) } + /// Typecheck the Hir. + pub fn typecheck(&self, env: &TyEnv) -> Result { + type_with(env, self) + } + /// Eval the Hir. It will actually get evaluated only as needed on demand. pub fn eval(&self, env: &NzEnv) -> Value { Value::new_thunk(env.clone(), self.clone()) diff --git a/dhall/src/semantics/nze/value.rs b/dhall/src/semantics/nze/value.rs index 2ae6852..0603fb5 100644 --- a/dhall/src/semantics/nze/value.rs +++ b/dhall/src/semantics/nze/value.rs @@ -1,12 +1,10 @@ use std::collections::HashMap; use std::rc::Rc; -use crate::error::TypeError; use crate::semantics::nze::lazy; use crate::semantics::{ - apply_any, normalize_hir_whnf, normalize_one_layer, squash_textlit, - type_with, Binder, BuiltinClosure, Hir, HirKind, NzEnv, NzVar, TyEnv, - TyExpr, VarEnv, + apply_any, normalize_hir_whnf, normalize_one_layer, squash_textlit, Binder, + BuiltinClosure, Hir, HirKind, NzEnv, NzVar, TyEnv, VarEnv, }; use crate::syntax::{ BinOp, Builtin, Const, ExprKind, InterpolatedTextContents, Label, LitKind, @@ -146,8 +144,7 @@ impl Value { if opts.normalize { self.normalize(); } - - self.to_tyexpr_noenv().to_expr(opts) + self.to_hir_noenv().to_expr(opts) } pub(crate) fn to_expr_tyenv(&self, tyenv: &TyEnv) -> NormalizedExpr { self.to_hir(tyenv.as_varenv()).to_expr_tyenv(tyenv) @@ -161,10 +158,6 @@ impl Value { Value::from_kind(apply_any(self.clone(), v)) } - pub(crate) fn get_type(&self, tyenv: &TyEnv) -> Result { - self.to_tyexpr_tyenv(tyenv).get_type() - } - pub fn to_hir(&self, venv: VarEnv) -> Hir { let map_uniontype = |kts: &HashMap>| { ExprKind::UnionType( @@ -270,13 +263,6 @@ impl Value { pub fn to_hir_noenv(&self) -> Hir { self.to_hir(VarEnv::new()) } - pub fn to_tyexpr_tyenv(&self, tyenv: &TyEnv) -> TyExpr { - 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()) - } } impl ValueInternal { diff --git a/dhall/src/semantics/tck/tyexpr.rs b/dhall/src/semantics/tck/tyexpr.rs index b49ea3e..dc14cd2 100644 --- a/dhall/src/semantics/tck/tyexpr.rs +++ b/dhall/src/semantics/tck/tyexpr.rs @@ -1,6 +1,6 @@ use crate::error::{TypeError, TypeMessage}; -use crate::semantics::{Hir, HirKind, NzEnv, Value,TyEnv}; -use crate::syntax::Span; +use crate::semantics::{Hir, HirKind, NzEnv, TyEnv, Value}; +use crate::syntax::{Const, Span}; use crate::{NormalizedExpr, ToExprOptions}; pub(crate) type Type = Value; @@ -33,7 +33,12 @@ impl TyExpr { } } pub fn get_type_tyexpr(&self, env: &TyEnv) -> Result { - Ok(self.get_type()?.to_tyexpr_tyenv(env)) + Ok(self.get_type()?.to_hir(env.as_varenv()).typecheck(env)?) + } + /// Get the kind (the type of the type) of this value + // TODO: avoid recomputing so much + pub fn get_kind(&self, env: &TyEnv) -> Result, TypeError> { + Ok(self.get_type_tyexpr(env)?.get_type()?.as_const()) } pub fn to_hir(&self) -> Hir { diff --git a/dhall/src/semantics/tck/typecheck.rs b/dhall/src/semantics/tck/typecheck.rs index c854552..794edcf 100644 --- a/dhall/src/semantics/tck/typecheck.rs +++ b/dhall/src/semantics/tck/typecheck.rs @@ -12,28 +12,6 @@ use crate::syntax::{ BinOp, Builtin, Const, ExprKind, InterpolatedTextContents, LitKind, Span, }; -fn type_of_recordtype<'a>( - span: Span, - tys: impl Iterator>, -) -> Result { - let span_err = |msg: &str| { - mkerr( - ErrorBuilder::new(msg.to_string()) - .span_err(span.clone(), msg.to_string()) - .format(), - ) - }; - // An empty record type has type Type - let mut k = Const::Type; - for t in tys { - match t.get_type()?.as_const() { - Some(c) => k = max(k, c), - None => return span_err("InvalidFieldType"), - } - } - Ok(Value::from_const(k)) -} - fn function_check(a: Const, b: Const) -> Const { if b == Const::Type { Const::Type @@ -42,8 +20,19 @@ fn function_check(a: Const, b: Const) -> Const { } } -pub fn mkerr(x: S) -> Result { - Err(TypeError::new(TypeMessage::Custom(x.to_string()))) +pub fn mkerr(msg: S) -> Result { + Err(TypeError::new(TypeMessage::Custom(msg.to_string()))) +} + +pub fn mk_span_err( + span: &Span, + msg: S, +) -> Result { + mkerr( + ErrorBuilder::new(msg.to_string()) + .span_err(span.clone(), msg.to_string()) + .format(), + ) } /// When all sub-expressions have been typed, check the remaining toplevel @@ -53,13 +42,7 @@ fn type_one_layer( ekind: ExprKind, span: Span, ) -> Result { - let span_err = |msg: &str| { - mkerr( - ErrorBuilder::new(msg.to_string()) - .span_err(span.clone(), msg.to_string()) - .format(), - ) - }; + let span_err = |msg: &str| mk_span_err(&span, msg); let ty = match &ekind { ExprKind::Import(..) => unreachable!( @@ -68,10 +51,9 @@ fn type_one_layer( ExprKind::Var(..) | ExprKind::Const(Const::Sort) => unreachable!(), // Handled in type_with ExprKind::Lam(binder, annot, body) => { - let body_ty = body.get_type()?; - let body_ty = body_ty.to_tyexpr_tyenv( + let body_ty = body.get_type_tyexpr( &env.insert_type(&binder.clone(), annot.eval(env)), - ); + )?; let pi_ekind = ExprKind::Pi(binder.clone(), annot.clone(), body_ty); type_one_layer(env, pi_ekind, Span::Artificial)?.eval(env) } @@ -157,19 +139,19 @@ fn type_one_layer( return span_err("InvalidListElement"); } } - let t = x.get_type()?; - if t.get_type(env)?.as_const() != Some(Const::Type) { + if x.get_kind(env)? != Some(Const::Type) { return span_err("InvalidListType"); } + let t = x.get_type()?; Value::from_builtin(Builtin::List).app(t) } ExprKind::SomeLit(x) => { - let t = x.get_type()?; - if t.get_type(env)?.as_const() != Some(Const::Type) { + if x.get_kind(env)? != Some(Const::Type) { return span_err("InvalidOptionalType"); } + let t = x.get_type()?; Value::from_builtin(Builtin::Optional).app(t) } ExprKind::RecordLit(kvs) => { @@ -183,18 +165,23 @@ fn type_one_layer( } Entry::Vacant(e) => e.insert(v.get_type()?), }; + + // Check that the fields have a valid kind + match v.get_kind(env)? { + Some(_) => {} + None => return span_err("InvalidFieldType"), + } } - type_of_recordtype( - span.clone(), - kts.iter().map(|(_, t)| Cow::Owned(t.to_tyexpr_tyenv(env))), - )?; Value::from_kind(ValueKind::RecordType(kts)) } ExprKind::RecordType(kts) => { use std::collections::hash_map::Entry; let mut seen_fields = HashMap::new(); - for (x, _) in kts { + // An empty record type has type Type + let mut k = Const::Type; + + for (x, t) in kts { // Check for duplicated entries match seen_fields.entry(x.clone()) { Entry::Occupied(_) => { @@ -202,12 +189,15 @@ fn type_one_layer( } Entry::Vacant(e) => e.insert(()), }; + + // Check the type is a Const and compute final type + match t.get_type()?.as_const() { + Some(c) => k = max(k, c), + None => return span_err("InvalidFieldType"), + } } - type_of_recordtype( - span.clone(), - kts.iter().map(|(_, t)| Cow::Borrowed(t)), - )? + Value::from_const(k) } ExprKind::UnionType(kts) => { use std::collections::hash_map::Entry; @@ -337,9 +327,7 @@ fn type_one_layer( if *x.get_type()?.kind() != ValueKind::from_builtin(Builtin::Bool) { return span_err("InvalidPredicate"); } - let y_ty = y.get_type()?; - let y_ty = y_ty.to_tyexpr_tyenv(env); - if y_ty.get_type()?.as_const() != Some(Const::Type) { + if y.get_kind(env)? != Some(Const::Type) { return span_err("IfBranchMustBeTerm"); } if y.get_type()? != z.get_type()? { @@ -369,45 +357,44 @@ fn type_one_layer( Ok(r_t.clone()) })?; - // Construct the final record type - type_of_recordtype( - span.clone(), - kts.iter().map(|(_, t)| Cow::Owned(t.to_tyexpr_tyenv(env))), - )?; Value::from_kind(ValueKind::RecordType(kts)) } ExprKind::BinOp(BinOp::RecursiveRecordMerge, x, y) => { let ekind = ExprKind::BinOp( BinOp::RecursiveRecordTypeMerge, - x.get_type()?.to_tyexpr_tyenv(env), - y.get_type()?.to_tyexpr_tyenv(env), + x.get_type_tyexpr(env)?, + y.get_type_tyexpr(env)?, ); - type_one_layer(env, ekind, Span::Artificial)?.eval(env) + type_one_layer(env, ekind, span.clone())?.eval(env) } ExprKind::BinOp(BinOp::RecursiveRecordTypeMerge, x, y) => { - let x_val = x.eval(env); - let y_val = y.eval(env); - let kts_x = match x_val.kind() { - ValueKind::RecordType(kts) => kts, - _ => return span_err("RecordTypeMergeRequiresRecordType"), - }; - let kts_y = match y_val.kind() { - ValueKind::RecordType(kts) => kts, - _ => return span_err("RecordTypeMergeRequiresRecordType"), - }; - for (k, tx) in kts_x { - if let Some(ty) = kts_y.get(k) { - type_one_layer( - env, - ExprKind::BinOp( - BinOp::RecursiveRecordTypeMerge, - tx.to_tyexpr_tyenv(env), - ty.to_tyexpr_tyenv(env), - ), - Span::Artificial, - )?; + fn check_rectymerge( + span: &Span, + env: &TyEnv, + x: Type, + y: Type, + ) -> Result<(), TypeError> { + let kts_x = match x.kind() { + ValueKind::RecordType(kts) => kts, + _ => return mk_span_err(span, "RecordTypeMergeRequiresRecordType"), + }; + let kts_y = match y.kind() { + ValueKind::RecordType(kts) => kts, + _ => return mk_span_err(span, "RecordTypeMergeRequiresRecordType"), + }; + for (k, tx) in kts_x { + if let Some(ty) = kts_y.get(k) { + check_rectymerge( + span, + env, + tx.clone(), + ty.clone(), + )?; + } } + Ok(()) } + check_rectymerge(&span, env, x.eval(env), y.eval(env))?; // A RecordType's type is always a const let xk = x.get_type()?.as_const().unwrap(); @@ -434,9 +421,7 @@ fn type_one_layer( if l.get_type()? != r.get_type()? { return span_err("EquivalenceTypeMismatch"); } - if l.get_type()?.to_tyexpr_tyenv(env).get_type()?.as_const() - != Some(Const::Type) - { + if l.get_kind(env)? != Some(Const::Type) { return span_err("EquivalenceArgumentsMustBeTerms"); } @@ -605,6 +590,9 @@ fn type_one_layer( } } ExprKind::ToMap(record, annot) => { + if record.get_kind(env)? != Some(Const::Type) { + return span_err("`toMap` only accepts records of type `Type`"); + } let record_t = record.get_type()?; let kts = match record_t.kind() { ValueKind::RecordType(kts) => kts, @@ -652,11 +640,6 @@ fn type_one_layer( annot_val } else { let entry_type = kts.iter().next().unwrap().1.clone(); - if entry_type.get_type(env)?.as_const() != Some(Const::Type) { - return span_err( - "`toMap` only accepts records of type `Type`", - ); - } for (_, t) in kts.iter() { if *t != entry_type { return span_err( diff --git a/dhall/tests/type-inference/failure/unit/RecursiveRecordMergeLhsNotRecord.txt b/dhall/tests/type-inference/failure/unit/RecursiveRecordMergeLhsNotRecord.txt index f74e839..02cf64f 100644 --- a/dhall/tests/type-inference/failure/unit/RecursiveRecordMergeLhsNotRecord.txt +++ b/dhall/tests/type-inference/failure/unit/RecursiveRecordMergeLhsNotRecord.txt @@ -1 +1,6 @@ Type error: error: RecordTypeMergeRequiresRecordType + --> :1:0 + | +1 | True ∧ {=} + | ^^^^^^^^^^ RecordTypeMergeRequiresRecordType + | diff --git a/dhall/tests/type-inference/failure/unit/RecursiveRecordMergeOverlapping.txt b/dhall/tests/type-inference/failure/unit/RecursiveRecordMergeOverlapping.txt index f74e839..202a3e5 100644 --- a/dhall/tests/type-inference/failure/unit/RecursiveRecordMergeOverlapping.txt +++ b/dhall/tests/type-inference/failure/unit/RecursiveRecordMergeOverlapping.txt @@ -1 +1,6 @@ Type error: error: RecordTypeMergeRequiresRecordType + --> :1:0 + | +1 | { x = True } ∧ { x = False } + | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ RecordTypeMergeRequiresRecordType + | diff --git a/dhall/tests/type-inference/failure/unit/RecursiveRecordMergeRhsNotRecord.txt b/dhall/tests/type-inference/failure/unit/RecursiveRecordMergeRhsNotRecord.txt index f74e839..a0b4676 100644 --- a/dhall/tests/type-inference/failure/unit/RecursiveRecordMergeRhsNotRecord.txt +++ b/dhall/tests/type-inference/failure/unit/RecursiveRecordMergeRhsNotRecord.txt @@ -1 +1,6 @@ Type error: error: RecordTypeMergeRequiresRecordType + --> :1:0 + | +1 | {=} ∧ True + | ^^^^^^^^^^ RecordTypeMergeRequiresRecordType + | diff --git a/dhall/tests/type-inference/failure/unit/RecursiveRecordTypeMergeOverlapping.txt b/dhall/tests/type-inference/failure/unit/RecursiveRecordTypeMergeOverlapping.txt index f74e839..769712b 100644 --- a/dhall/tests/type-inference/failure/unit/RecursiveRecordTypeMergeOverlapping.txt +++ b/dhall/tests/type-inference/failure/unit/RecursiveRecordTypeMergeOverlapping.txt @@ -1 +1,6 @@ Type error: error: RecordTypeMergeRequiresRecordType + --> :1:0 + | +1 | { x : Bool } ⩓ { x : Natural } + | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ RecordTypeMergeRequiresRecordType + | -- cgit v1.3.1 From e25b67906ce68e8726e8139c1d1855f3ab2518ce Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Thu, 13 Feb 2020 20:45:42 +0000 Subject: Rework annotation and Sort handling --- dhall/src/semantics/hir.rs | 2 +- dhall/src/semantics/tck/typecheck.rs | 143 +++++++++++---------- dhall/tests/type-inference/failure/SortInLet.txt | 7 +- .../type-inference/failure/hurkensParadox.txt | 8 +- .../tests/type-inference/failure/recordOfKind.txt | 2 +- .../unit/AnnotationRecordWrongFieldName.txt | 2 +- .../unit/AnnotationRecordWrongFieldType.txt | 2 +- .../failure/unit/FunctionTypeKindSort.txt | 7 +- .../failure/unit/FunctionTypeTypeSort.txt | 7 +- .../failure/unit/LetWithWrongAnnotation.txt | 4 +- .../unit/OptionalDeprecatedSyntaxPresent.txt | 2 +- .../failure/unit/RecordMixedKinds3.txt | 2 +- .../unit/RightBiasedRecordMergeMixedKinds2.txt | 2 +- .../unit/RightBiasedRecordMergeMixedKinds3.txt | 2 +- dhall/tests/type-inference/failure/unit/Sort.txt | 7 +- .../failure/unit/TypeAnnotationWrong.txt | 2 +- 16 files changed, 114 insertions(+), 87 deletions(-) (limited to 'dhall/tests') diff --git a/dhall/src/semantics/hir.rs b/dhall/src/semantics/hir.rs index f91aa73..e4e2a5f 100644 --- a/dhall/src/semantics/hir.rs +++ b/dhall/src/semantics/hir.rs @@ -72,7 +72,7 @@ impl Hir { /// Typecheck the Hir. pub fn typecheck(&self, env: &TyEnv) -> Result { - type_with(env, self) + type_with(env, self, None) } /// Eval the Hir. It will actually get evaluated only as needed on demand. diff --git a/dhall/src/semantics/tck/typecheck.rs b/dhall/src/semantics/tck/typecheck.rs index 794edcf..a4ab31f 100644 --- a/dhall/src/semantics/tck/typecheck.rs +++ b/dhall/src/semantics/tck/typecheck.rs @@ -24,13 +24,10 @@ pub fn mkerr(msg: S) -> Result { Err(TypeError::new(TypeMessage::Custom(msg.to_string()))) } -pub fn mk_span_err( - span: &Span, - msg: S, -) -> Result { +pub fn mk_span_err(span: Span, msg: S) -> Result { mkerr( ErrorBuilder::new(msg.to_string()) - .span_err(span.clone(), msg.to_string()) + .span_err(span, msg.to_string()) .format(), ) } @@ -40,22 +37,25 @@ pub fn mk_span_err( fn type_one_layer( env: &TyEnv, ekind: ExprKind, + annot: Option, span: Span, ) -> Result { - let span_err = |msg: &str| mk_span_err(&span, msg); + let span_err = |msg: &str| mk_span_err(span.clone(), msg); let ty = match &ekind { ExprKind::Import(..) => unreachable!( "There should remain no imports in a resolved expression" ), - ExprKind::Var(..) | ExprKind::Const(Const::Sort) => unreachable!(), // Handled in type_with + ExprKind::Var(..) + | ExprKind::Const(Const::Sort) + | ExprKind::Annot(..) => unreachable!(), // Handled in type_with ExprKind::Lam(binder, annot, body) => { let body_ty = body.get_type_tyexpr( &env.insert_type(&binder.clone(), annot.eval(env)), )?; let pi_ekind = ExprKind::Pi(binder.clone(), annot.clone(), body_ty); - type_one_layer(env, pi_ekind, Span::Artificial)?.eval(env) + type_one_layer(env, pi_ekind, None, Span::Artificial)?.eval(env) } ExprKind::Pi(_, annot, body) => { let ks = match annot.get_type()?.as_const() { @@ -253,18 +253,6 @@ fn type_one_layer( } // _ => span_err("NotARecord"), } } - ExprKind::Annot(x, t) => { - let t = t.eval(env); - let x_ty = x.get_type()?; - if x_ty != t { - return span_err(&format!( - "annot mismatch: {} != {}", - x_ty.to_expr_tyenv(env), - t.to_expr_tyenv(env) - )); - } - x_ty - } ExprKind::Assert(t) => { let t = t.eval(env); match &*t.kind() { @@ -365,7 +353,7 @@ fn type_one_layer( x.get_type_tyexpr(env)?, y.get_type_tyexpr(env)?, ); - type_one_layer(env, ekind, span.clone())?.eval(env) + type_one_layer(env, ekind, None, span.clone())?.eval(env) } ExprKind::BinOp(BinOp::RecursiveRecordTypeMerge, x, y) => { fn check_rectymerge( @@ -376,20 +364,25 @@ fn type_one_layer( ) -> Result<(), TypeError> { let kts_x = match x.kind() { ValueKind::RecordType(kts) => kts, - _ => return mk_span_err(span, "RecordTypeMergeRequiresRecordType"), + _ => { + return mk_span_err( + span.clone(), + "RecordTypeMergeRequiresRecordType", + ) + } }; let kts_y = match y.kind() { ValueKind::RecordType(kts) => kts, - _ => return mk_span_err(span, "RecordTypeMergeRequiresRecordType"), + _ => { + return mk_span_err( + span.clone(), + "RecordTypeMergeRequiresRecordType", + ) + } }; for (k, tx) in kts_x { if let Some(ty) = kts_y.get(k) { - check_rectymerge( - span, - env, - tx.clone(), - ty.clone(), - )?; + check_rectymerge(span, env, tx.clone(), ty.clone())?; } } Ok(()) @@ -717,30 +710,38 @@ fn type_one_layer( let ty_field_default = type_one_layer( env, ExprKind::Field(ty.clone(), "default".into()), + None, span.clone(), )?; let ty_field_type = type_one_layer( env, ExprKind::Field(ty.clone(), "Type".into()), + None, span.clone(), )?; - let merge = type_one_layer( + return type_one_layer( env, ExprKind::BinOp( BinOp::RightBiasedRecordMerge, ty_field_default, compl.clone(), ), - span.clone(), - )?; - return type_one_layer( - env, - ExprKind::Annot(merge, ty_field_type), + Some(ty_field_type.eval(env)), span.clone(), ); } }; + if let Some(annot) = annot { + if ty != annot { + return span_err(&format!( + "annot mismatch: {} != {}", + ty.to_expr_tyenv(env), + annot.to_expr_tyenv(env) + )); + } + } + Ok(TyExpr::new( HirKind::Expr(ekind.map_ref(|tye| tye.to_hir())), Some(ty), @@ -748,72 +749,78 @@ 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) => (HirKind::Var(*var), Some(env.lookup(var))), +/// `type_with` typechecks an expression in the provided environment. Optionally pass an annotation +/// to compare with. +pub(crate) fn type_with( + env: &TyEnv, + hir: &Hir, + annot: Option, +) -> Result { + match hir.kind() { + HirKind::Var(var) => Ok(TyExpr::new( + HirKind::Var(*var), + Some(env.lookup(var)), + hir.span(), + )), HirKind::Expr(ExprKind::Var(_)) => { unreachable!("Hir should contain no unresolved variables") } HirKind::Expr(ExprKind::Const(Const::Sort)) => { - (HirKind::Expr(ExprKind::Const(Const::Sort)), None) + mk_span_err(hir.span(), "Sort does not have a type") + } + HirKind::Expr(ExprKind::Annot(x, t)) => { + let t = match t.kind() { + HirKind::Expr(ExprKind::Const(Const::Sort)) => { + Value::from_const(Const::Sort) + } + _ => type_with(env, t, None)?.eval(env), + }; + type_with(env, x, Some(t)) } HirKind::Expr(ekind) => { let ekind = match ekind { ExprKind::Lam(binder, annot, body) => { - let annot = type_with(env, annot)?; + let annot = type_with(env, annot, None)?; let annot_nf = annot.eval(env); let body_env = env.insert_type(binder, annot_nf); - let body = type_with(&body_env, body)?; + let body = type_with(&body_env, body, None)?; ExprKind::Lam(binder.clone(), annot, body) } ExprKind::Pi(binder, annot, body) => { - let annot = type_with(env, annot)?; + let annot = type_with(env, annot, None)?; let annot_nf = annot.eval(env); let body_env = env.insert_type(binder, annot_nf); - let body = type_with(&body_env, body)?; + let body = type_with(&body_env, body, None)?; ExprKind::Pi(binder.clone(), annot, body) } ExprKind::Let(binder, annot, val, body) => { - let val = if let Some(t) = annot { - Hir::new( - HirKind::Expr(ExprKind::Annot( - val.clone(), - t.clone(), - )), - t.span(), - ) + let val_annot = if let Some(t) = annot { + Some(type_with(env, t, None)?.eval(env)) } else { - val.clone() + None }; - let val = type_with(env, &val)?; + let val = type_with(env, &val, val_annot)?; let val_ty = val.get_type()?; let val_nf = val.eval(env); let body_env = env.insert_value(&binder, val_nf, val_ty); - let body = type_with(&body_env, body)?; + let body = type_with(&body_env, body, None)?; ExprKind::Let(binder.clone(), None, val, body) } - _ => ekind.traverse_ref(|e| type_with(env, e))?, + _ => ekind.traverse_ref(|e| type_with(env, e, None))?, }; - return type_one_layer(env, ekind, hir.span()); + type_one_layer(env, ekind, annot, hir.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: &Hir) -> Result { - let res = type_with(&TyEnv::new(), e)?; - // Ensure that the inferred type exists (i.e. this is not Sort) - res.get_type()?; - Ok(res) +pub(crate) fn typecheck(hir: &Hir) -> Result { + type_with(&TyEnv::new(), hir, None) } /// Like `typecheck`, but additionally checks that the expression's type matches the provided type. 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) + let ty = typecheck(&ty)?.eval(&TyEnv::new()); + type_with(&TyEnv::new(), hir, Some(ty)) } diff --git a/dhall/tests/type-inference/failure/SortInLet.txt b/dhall/tests/type-inference/failure/SortInLet.txt index 5b88ff7..19bd26d 100644 --- a/dhall/tests/type-inference/failure/SortInLet.txt +++ b/dhall/tests/type-inference/failure/SortInLet.txt @@ -1 +1,6 @@ -Type error: Unhandled error: Sort +Type error: error: Sort does not have a type + --> :1:8 + | +1 | let x = Sort in 0 + | ^^^^ Sort does not have a type + | diff --git a/dhall/tests/type-inference/failure/hurkensParadox.txt b/dhall/tests/type-inference/failure/hurkensParadox.txt index 6b99615..5aacb80 100644 --- a/dhall/tests/type-inference/failure/hurkensParadox.txt +++ b/dhall/tests/type-inference/failure/hurkensParadox.txt @@ -1,15 +1,15 @@ Type error: error: wrong type of function argument - --> :6:23 + --> :6:15 | 1 | let bottom : Type = ∀(any : Type) → any 2 | 3 | in let not : Type → Type = λ(p : Type) → p → bottom 4 | ... + 9 | in let tau 10 | : pow (pow U) → U -11 | = λ(t : pow (pow U)) - | ^^^ this expects an argument of type: Kind - | ^ but this has type: Sort + | ^^^ this expects an argument of type: Kind + | ^ but this has type: Sort | = note: expected type `Kind` found type `Sort` diff --git a/dhall/tests/type-inference/failure/recordOfKind.txt b/dhall/tests/type-inference/failure/recordOfKind.txt index 5b88ff7..a5d2465 100644 --- a/dhall/tests/type-inference/failure/recordOfKind.txt +++ b/dhall/tests/type-inference/failure/recordOfKind.txt @@ -1 +1 @@ -Type error: Unhandled error: Sort +Type error: error: Sort does not have a type diff --git a/dhall/tests/type-inference/failure/unit/AnnotationRecordWrongFieldName.txt b/dhall/tests/type-inference/failure/unit/AnnotationRecordWrongFieldName.txt index 01a1f32..a39a0fb 100644 --- a/dhall/tests/type-inference/failure/unit/AnnotationRecordWrongFieldName.txt +++ b/dhall/tests/type-inference/failure/unit/AnnotationRecordWrongFieldName.txt @@ -2,5 +2,5 @@ Type error: error: annot mismatch: { x : Natural } != { y : Natural } --> :1:0 | 1 | { x = 1 } : { y : Natural } - | ^^^^^^^^^^^^^^^^^^^^^^^^^^^ annot mismatch: { x : Natural } != { y : Natural } + | ^^^^^^^^^ annot mismatch: { x : Natural } != { y : Natural } | diff --git a/dhall/tests/type-inference/failure/unit/AnnotationRecordWrongFieldType.txt b/dhall/tests/type-inference/failure/unit/AnnotationRecordWrongFieldType.txt index 5c10467..9ecc2a4 100644 --- a/dhall/tests/type-inference/failure/unit/AnnotationRecordWrongFieldType.txt +++ b/dhall/tests/type-inference/failure/unit/AnnotationRecordWrongFieldType.txt @@ -2,5 +2,5 @@ Type error: error: annot mismatch: { x : Natural } != { x : Text } --> :1:0 | 1 | { x = 1 } : { x : Text } - | ^^^^^^^^^^^^^^^^^^^^^^^^ annot mismatch: { x : Natural } != { x : Text } + | ^^^^^^^^^ annot mismatch: { x : Natural } != { x : Text } | diff --git a/dhall/tests/type-inference/failure/unit/FunctionTypeKindSort.txt b/dhall/tests/type-inference/failure/unit/FunctionTypeKindSort.txt index 5b88ff7..6f26607 100644 --- a/dhall/tests/type-inference/failure/unit/FunctionTypeKindSort.txt +++ b/dhall/tests/type-inference/failure/unit/FunctionTypeKindSort.txt @@ -1 +1,6 @@ -Type error: Unhandled error: Sort +Type error: error: Sort does not have a type + --> :1:7 + | +1 | Kind → Sort + | ^^^^ Sort does not have a type + | diff --git a/dhall/tests/type-inference/failure/unit/FunctionTypeTypeSort.txt b/dhall/tests/type-inference/failure/unit/FunctionTypeTypeSort.txt index 5b88ff7..169014b 100644 --- a/dhall/tests/type-inference/failure/unit/FunctionTypeTypeSort.txt +++ b/dhall/tests/type-inference/failure/unit/FunctionTypeTypeSort.txt @@ -1 +1,6 @@ -Type error: Unhandled error: Sort +Type error: error: Sort does not have a type + --> :1:7 + | +1 | Type → Sort + | ^^^^ Sort does not have a type + | diff --git a/dhall/tests/type-inference/failure/unit/LetWithWrongAnnotation.txt b/dhall/tests/type-inference/failure/unit/LetWithWrongAnnotation.txt index 2f75196..51279f2 100644 --- a/dhall/tests/type-inference/failure/unit/LetWithWrongAnnotation.txt +++ b/dhall/tests/type-inference/failure/unit/LetWithWrongAnnotation.txt @@ -1,6 +1,6 @@ Type error: error: annot mismatch: Bool != Natural - --> :1:8 + --> :1:18 | 1 | let x : Natural = True in True - | ^^^^^^^ annot mismatch: Bool != Natural + | ^^^^ annot mismatch: Bool != Natural | diff --git a/dhall/tests/type-inference/failure/unit/OptionalDeprecatedSyntaxPresent.txt b/dhall/tests/type-inference/failure/unit/OptionalDeprecatedSyntaxPresent.txt index 066e4a3..0cc4bba 100644 --- a/dhall/tests/type-inference/failure/unit/OptionalDeprecatedSyntaxPresent.txt +++ b/dhall/tests/type-inference/failure/unit/OptionalDeprecatedSyntaxPresent.txt @@ -2,5 +2,5 @@ Type error: error: annot mismatch: List Natural != Optional Natural --> :1:0 | 1 | [ 1 ] : Optional Natural - | ^^^^^^^^^^^^^^^^^^^^^^^^ annot mismatch: List Natural != Optional Natural + | ^^^^^ annot mismatch: List Natural != Optional Natural | diff --git a/dhall/tests/type-inference/failure/unit/RecordMixedKinds3.txt b/dhall/tests/type-inference/failure/unit/RecordMixedKinds3.txt index 5b88ff7..a5d2465 100644 --- a/dhall/tests/type-inference/failure/unit/RecordMixedKinds3.txt +++ b/dhall/tests/type-inference/failure/unit/RecordMixedKinds3.txt @@ -1 +1 @@ -Type error: Unhandled error: Sort +Type error: error: Sort does not have a type diff --git a/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds2.txt b/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds2.txt index 5b88ff7..a5d2465 100644 --- a/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds2.txt +++ b/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds2.txt @@ -1 +1 @@ -Type error: Unhandled error: Sort +Type error: error: Sort does not have a type diff --git a/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds3.txt b/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds3.txt index 5b88ff7..a5d2465 100644 --- a/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds3.txt +++ b/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds3.txt @@ -1 +1 @@ -Type error: Unhandled error: Sort +Type error: error: Sort does not have a type diff --git a/dhall/tests/type-inference/failure/unit/Sort.txt b/dhall/tests/type-inference/failure/unit/Sort.txt index 5b88ff7..e402127 100644 --- a/dhall/tests/type-inference/failure/unit/Sort.txt +++ b/dhall/tests/type-inference/failure/unit/Sort.txt @@ -1 +1,6 @@ -Type error: Unhandled error: Sort +Type error: error: Sort does not have a type + --> :1:0 + | +1 | Sort + | ^^^^ Sort does not have a type + | diff --git a/dhall/tests/type-inference/failure/unit/TypeAnnotationWrong.txt b/dhall/tests/type-inference/failure/unit/TypeAnnotationWrong.txt index e203d22..dffadb1 100644 --- a/dhall/tests/type-inference/failure/unit/TypeAnnotationWrong.txt +++ b/dhall/tests/type-inference/failure/unit/TypeAnnotationWrong.txt @@ -2,5 +2,5 @@ Type error: error: annot mismatch: Natural != Bool --> :1:0 | 1 | 1 : Bool - | ^^^^^^^^ annot mismatch: Natural != Bool + | ^ annot mismatch: Natural != Bool | -- cgit v1.3.1 From 130de8cea49c848a06174c61c747d9414a5c71b7 Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Sun, 16 Feb 2020 19:06:23 +0000 Subject: Start requiring Universe to build a Type --- dhall/src/semantics/nze/normalize.rs | 2 +- dhall/src/semantics/tck/tyexpr.rs | 117 +++++++-- dhall/src/semantics/tck/typecheck.rs | 263 +++++++++------------ dhall/src/syntax/ast/expr.rs | 7 + .../failure/unit/FunctionArgumentTypeNotAType.txt | 4 +- .../unit/FunctionTypeArgumentTypeNotAType.txt | 4 +- tests_buffer | 1 + 7 files changed, 218 insertions(+), 180 deletions(-) (limited to 'dhall/tests') diff --git a/dhall/src/semantics/nze/normalize.rs b/dhall/src/semantics/nze/normalize.rs index 0e09511..c2d2dc2 100644 --- a/dhall/src/semantics/nze/normalize.rs +++ b/dhall/src/semantics/nze/normalize.rs @@ -471,7 +471,7 @@ pub(crate) fn normalize_hir_whnf(env: &NzEnv, hir: &Hir) -> ValueKind { closure: Closure::new(env, body.clone()), } } - HirKind::Expr(ExprKind::Let(_, None, val, body)) => { + HirKind::Expr(ExprKind::Let(_, _, val, body)) => { let val = val.eval(env); body.eval(env.insert_value(val, ())).kind().clone() } diff --git a/dhall/src/semantics/tck/tyexpr.rs b/dhall/src/semantics/tck/tyexpr.rs index 4999899..3c47a81 100644 --- a/dhall/src/semantics/tck/tyexpr.rs +++ b/dhall/src/semantics/tck/tyexpr.rs @@ -1,8 +1,12 @@ -use crate::error::TypeError; -use crate::semantics::{Hir, HirKind, NzEnv, TyEnv, Value, ValueKind, VarEnv}; +use crate::error::{ErrorBuilder, TypeError}; +use crate::semantics::{mkerr, Hir, NzEnv, TyEnv, Value, ValueKind, VarEnv}; use crate::syntax::{Builtin, Const, Span}; use crate::{NormalizedExpr, ToExprOptions}; +/// The type of a type. 0 is `Type`, 1 is `Kind`, etc... +#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Default)] +pub(crate) struct Universe(u8); + /// An expression representing a type #[derive(Debug, Clone, PartialEq, Eq)] pub(crate) struct Type { @@ -16,12 +20,64 @@ pub(crate) struct TyExpr { ty: Type, } +impl Universe { + pub fn from_const(c: Const) -> Self { + Universe(match c { + Const::Type => 0, + Const::Kind => 1, + Const::Sort => 2, + }) + } + pub fn as_const(self) -> Option { + match self.0 { + 0 => Some(Const::Type), + 1 => Some(Const::Kind), + 2 => Some(Const::Sort), + _ => None, + } + } + pub fn next(self) -> Self { + Universe(self.0 + 1) + } + pub fn previous(self) -> Option { + if self.0 == 0 { + None + } else { + Some(Universe(self.0 - 1)) + } + } +} + impl Type { + pub fn new(val: Value, _u: Universe) -> Self { + Type { val } + } pub fn from_const(c: Const) -> Self { - Value::from_const(c).into() + Self::new(Value::from_const(c), c.to_universe().next()) } pub fn from_builtin(b: Builtin) -> Self { - Value::from_builtin(b).into() + use Builtin::*; + match b { + Bool | Natural | Integer | Double | Text => {} + _ => unreachable!("this builtin is not a type: {}", b), + } + + Self::new(Value::from_builtin(b), Universe::from_const(Const::Type)) + } + + /// Get the type of this type + // TODO: avoid recomputing so much + pub fn ty(&self, env: &TyEnv) -> Result, TypeError> { + Ok(self.to_hir(env.as_varenv()).typecheck(env)?.ty().as_const()) + } + /// Get the type of this type + // TODO: avoid recomputing so much + pub fn ty_univ(&self, env: &TyEnv) -> Result { + Ok(match self.ty(env)? { + Some(c) => c.to_universe(), + // TODO: hack, might explode + None => Const::Sort.to_universe().next(), + }) } pub fn to_value(&self) -> Value { @@ -49,9 +105,9 @@ impl Type { } impl TyExpr { - pub fn new(kind: HirKind, ty: Type, span: Span) -> Self { + pub fn from_hir(hir: &Hir, ty: Type) -> Self { TyExpr { - hir: Hir::new(kind, span), + hir: hir.clone(), ty, } } @@ -62,16 +118,6 @@ impl TyExpr { pub fn ty(&self) -> &Type { &self.ty } - /// Get the kind (the type of the type) of this value - // TODO: avoid recomputing so much - pub fn get_kind(&self, env: &TyEnv) -> Result, TypeError> { - Ok(self - .ty() - .to_hir(env.as_varenv()) - .typecheck(env)? - .ty() - .as_const()) - } pub fn to_hir(&self) -> Hir { self.as_hir().clone() @@ -79,18 +125,51 @@ impl TyExpr { pub fn as_hir(&self) -> &Hir { &self.hir } - /// Converts a value back to the corresponding AST expression. + /// Converts a closed expression back to the corresponding AST expression. pub fn to_expr(&self, opts: ToExprOptions) -> NormalizedExpr { self.as_hir().to_expr(opts) } + pub fn to_expr_tyenv(&self, env: &TyEnv) -> NormalizedExpr { + self.as_hir().to_expr_tyenv(env) + } /// Eval the TyExpr. It will actually get evaluated only as needed on demand. pub fn eval(&self, env: impl Into) -> Value { self.as_hir().eval(env.into()) } + pub fn ensure_is_type(&self, env: &TyEnv) -> Result<(), TypeError> { + if self.ty().as_const().is_none() { + return mkerr( + ErrorBuilder::new(format!( + "Expected a type, found: `{}`", + self.to_expr_tyenv(env), + )) + .span_err( + self.span(), + format!( + "this has type: `{}`", + self.ty().to_expr_tyenv(env) + ), + ) + .help(format!( + "An expression in type position must have type `Type`, \ + `Kind` or `Sort`", + )) + .format(), + ); + } + Ok(()) + } /// Evaluate to a Type. - pub fn eval_to_type(&self, env: impl Into) -> Type { - self.eval(env).into() + pub fn eval_to_type(&self, env: &TyEnv) -> Result { + self.ensure_is_type(env)?; + Ok(Type::new( + self.eval(env), + self.ty() + .as_const() + .expect("case handled in ensure_is_type") + .to_universe(), + )) } /// Eval a closed TyExpr (i.e. without free variables). It will actually get evaluated only as /// needed on demand. diff --git a/dhall/src/semantics/tck/typecheck.rs b/dhall/src/semantics/tck/typecheck.rs index dd996ae..1281045 100644 --- a/dhall/src/semantics/tck/typecheck.rs +++ b/dhall/src/semantics/tck/typecheck.rs @@ -15,8 +15,8 @@ use crate::syntax::{ fn check_rectymerge( span: &Span, env: &TyEnv, - x: Type, - y: Type, + x: Value, + y: Value, ) -> Result<(), TypeError> { let kts_x = match x.kind() { ValueKind::RecordType(kts) => kts, @@ -39,7 +39,7 @@ fn check_rectymerge( for (k, tx) in kts_x { if let Some(ty) = kts_y.get(k) { // TODO: store Type in RecordType ? - check_rectymerge(span, env, tx.clone().into(), ty.clone().into())?; + check_rectymerge(span, env, tx.clone(), ty.clone())?; } } Ok(()) @@ -70,9 +70,8 @@ pub fn mk_span_err(span: Span, msg: S) -> Result { fn type_one_layer( env: &TyEnv, ekind: ExprKind, - annot: Option, span: Span, -) -> Result { +) -> Result { let span_err = |msg: &str| mk_span_err(span.clone(), msg); let ty = match &ekind { @@ -81,84 +80,19 @@ fn type_one_layer( } ExprKind::Var(..) | ExprKind::Const(Const::Sort) + | ExprKind::Lam(..) + | ExprKind::Pi(..) + | ExprKind::Let(..) | ExprKind::Annot(..) => { unreachable!("This case should have been handled in type_with") } - ExprKind::Lam(binder, annot, body) => { - if annot.ty().as_const().is_none() { - return mkerr( - ErrorBuilder::new(format!( - "Invalid input type: `{}`", - annot.ty().to_expr_tyenv(env), - )) - .span_err( - annot.span(), - format!( - "this has type: `{}`", - annot.ty().to_expr_tyenv(env) - ), - ) - .help(format!( - "The input type of a function must have type `Type`, \ - `Kind` or `Sort`", - )) - .format(), - ); - } - let body_env = env.insert_type(&binder, annot.eval_to_type(env)); - if body.get_kind(&body_env)?.is_none() { - return span_err("Invalid output type"); - } - Hir::new( - HirKind::Expr(ExprKind::Pi( - binder.clone(), - annot.to_hir(), - body.ty().to_hir(body_env.as_varenv()), - )), - span.clone(), - ) - .eval_to_type(env) - } - ExprKind::Pi(_, annot, body) => { - let ks = match annot.ty().as_const() { - Some(k) => k, - _ => { - return mkerr( - ErrorBuilder::new(format!( - "Invalid input type: `{}`", - annot.ty().to_expr_tyenv(env), - )) - .span_err( - annot.span(), - format!( - "this has type: `{}`", - annot.ty().to_expr_tyenv(env) - ), - ) - .help(format!( - "The input type of a function must have type \ - `Type`, `Kind` or `Sort`", - )) - .format(), - ); - } - }; - let kt = match body.ty().as_const() { - Some(k) => k, - _ => return span_err("Invalid output type"), - }; - - Type::from_const(function_check(ks, kt)) - } - ExprKind::Let(_, _, _, body) => body.ty().clone(), - ExprKind::Const(Const::Type) => Type::from_const(Const::Kind), ExprKind::Const(Const::Kind) => Type::from_const(Const::Sort), ExprKind::Builtin(b) => { let t_hir = type_of_builtin(*b); let t_tyexpr = typecheck(&t_hir)?; - t_tyexpr.eval_to_type(env) + t_tyexpr.eval_to_type(env)? } ExprKind::Lit(LitKind::Bool(_)) => Type::from_builtin(Builtin::Bool), ExprKind::Lit(LitKind::Natural(_)) => { @@ -183,7 +117,7 @@ fn type_one_layer( text_type } ExprKind::EmptyListLit(t) => { - let t = t.eval_to_type(env); + let t = t.eval_to_type(env)?; match t.kind() { ValueKind::AppliedBuiltin(BuiltinClosure { b: Builtin::List, @@ -202,7 +136,7 @@ fn type_one_layer( return span_err("InvalidListElement"); } } - if x.get_kind(env)? != Some(Const::Type) { + if x.ty().ty(env)? != Some(Const::Type) { return span_err("InvalidListType"); } @@ -210,7 +144,7 @@ fn type_one_layer( Value::from_builtin(Builtin::List).app(t).to_type() } ExprKind::SomeLit(x) => { - if x.get_kind(env)? != Some(Const::Type) { + if x.ty().ty(env)? != Some(Const::Type) { return span_err("InvalidOptionalType"); } @@ -230,7 +164,7 @@ fn type_one_layer( }; // Check that the fields have a valid kind - match v.get_kind(env)? { + match v.ty().ty(env)? { Some(_) => {} None => return span_err("InvalidFieldType"), } @@ -297,7 +231,7 @@ fn type_one_layer( }, // TODO: branch here only when scrut.ty() is a Const _ => { - let scrut_nf = scrut.eval_to_type(env); + let scrut_nf = scrut.eval(env); match scrut_nf.kind() { ValueKind::UnionType(kts) => match kts.get(x) { // Constructor has type T -> < x: T, ... > @@ -305,13 +239,11 @@ fn type_one_layer( Value::from_kind(ValueKind::PiClosure { binder: Binder::new(x.clone()), annot: ty.clone(), - closure: Closure::new_constant( - scrut_nf.into_value(), - ), + closure: Closure::new_constant(scrut_nf), }) .to_type() } - Some(None) => scrut_nf, + Some(None) => scrut_nf.to_type(), None => return span_err("MissingUnionField"), }, _ => return span_err("NotARecord"), @@ -320,7 +252,7 @@ fn type_one_layer( } } ExprKind::Assert(t) => { - let t = t.eval_to_type(env); + let t = t.eval_to_type(env)?; match t.kind() { ValueKind::Equivalence(x, y) if x == y => {} ValueKind::Equivalence(..) => { @@ -382,7 +314,7 @@ fn type_one_layer( if *x.ty().kind() != ValueKind::from_builtin(Builtin::Bool) { return span_err("InvalidPredicate"); } - if y.get_kind(env)? != Some(Const::Type) { + if y.ty().ty(env)? != Some(Const::Type) { return span_err("IfBranchMustBeTerm"); } if y.ty() != z.ty() { @@ -415,25 +347,22 @@ fn type_one_layer( Value::from_kind(ValueKind::RecordType(kts)).to_type() } ExprKind::BinOp(BinOp::RecursiveRecordMerge, x, y) => { - check_rectymerge(&span, env, x.ty().clone(), y.ty().clone())?; + check_rectymerge(&span, env, x.ty().to_value(), y.ty().to_value())?; - Hir::new( + let hir = Hir::new( HirKind::Expr(ExprKind::BinOp( BinOp::RecursiveRecordTypeMerge, x.ty().to_hir(env.as_varenv()), y.ty().to_hir(env.as_varenv()), )), span.clone(), - ) - .eval_to_type(env) + ); + let x_u = x.ty().ty_univ(env)?; + let y_u = y.ty().ty_univ(env)?; + Type::new(hir.eval(env), max(x_u, y_u)) } ExprKind::BinOp(BinOp::RecursiveRecordTypeMerge, x, y) => { - check_rectymerge( - &span, - env, - x.eval_to_type(env), - y.eval_to_type(env), - )?; + check_rectymerge(&span, env, x.eval(env), y.eval(env))?; // A RecordType's type is always a const let xk = x.ty().as_const().unwrap(); @@ -459,7 +388,7 @@ fn type_one_layer( if l.ty() != r.ty() { return span_err("EquivalenceTypeMismatch"); } - if l.get_kind(env)? != Some(Const::Type) { + if l.ty().ty(env)? != Some(Const::Type) { return span_err("EquivalenceArgumentsMustBeTerms"); } @@ -614,7 +543,10 @@ fn type_one_layer( } } - let type_annot = type_annot.as_ref().map(|t| t.eval_to_type(env)); + let type_annot = type_annot + .as_ref() + .map(|t| t.eval_to_type(env)) + .transpose()?; match (inferred_type, type_annot) { (Some(t1), Some(t2)) => { if t1 != t2 { @@ -628,7 +560,7 @@ fn type_one_layer( } } ExprKind::ToMap(record, annot) => { - if record.get_kind(env)? != Some(Const::Type) { + if record.ty().ty(env)? != Some(Const::Type) { return span_err("`toMap` only accepts records of type `Type`"); } let record_t = record.ty(); @@ -648,7 +580,7 @@ fn type_one_layer( annotation", ); }; - let annot_val = annot.eval_to_type(env); + let annot_val = annot.eval_to_type(env)?; let err_msg = "The type of `toMap x` must be of the form \ `List { mapKey : Text, mapValue : T }`"; @@ -693,7 +625,7 @@ fn type_one_layer( .app(Value::from_kind(ValueKind::RecordType(kts))) .to_type(); if let Some(annot) = annot { - let annot_val = annot.eval_to_type(env); + let annot_val = annot.eval_to_type(env)?; if output_type != annot_val { return span_err("Annotation mismatch"); } @@ -733,7 +665,7 @@ fn type_one_layer( _ => return span_err("ProjectionMustBeRecord"), }; - let selection_val = selection.eval_to_type(env); + let selection_val = selection.eval_to_type(env)?; let sel_kts = match selection_val.kind() { ValueKind::RecordType(kts) => kts, _ => return span_err("ProjectionByExprTakesRecordType"), @@ -754,22 +686,7 @@ fn type_one_layer( } }; - if let Some(annot) = annot { - if ty != annot { - return span_err(&format!( - "annot mismatch: {} != {}", - ty.to_expr_tyenv(env), - annot.to_expr_tyenv(env) - )); - } - } - - // TODO: avoid retraversing - Ok(TyExpr::new( - HirKind::Expr(ekind.map_ref(|tye| tye.to_hir())), - ty, - span, - )) + Ok(ty) } /// `type_with` typechecks an expression in the provided environment. Optionally pass an annotation @@ -779,59 +696,93 @@ pub(crate) fn type_with( hir: &Hir, annot: Option, ) -> Result { - match hir.kind() { - HirKind::Var(var) => { - Ok(TyExpr::new(HirKind::Var(*var), env.lookup(var), hir.span())) - } + let tyexpr = match hir.kind() { + HirKind::Var(var) => TyExpr::from_hir(hir, env.lookup(var)), HirKind::Expr(ExprKind::Var(_)) => { unreachable!("Hir should contain no unresolved variables") } HirKind::Expr(ExprKind::Const(Const::Sort)) => { - mk_span_err(hir.span(), "Sort does not have a type") + return mk_span_err(hir.span(), "Sort does not have a type") } HirKind::Expr(ExprKind::Annot(x, t)) => { let t = match t.kind() { HirKind::Expr(ExprKind::Const(Const::Sort)) => { Type::from_const(Const::Sort) } - _ => type_with(env, t, None)?.eval_to_type(env), + _ => type_with(env, t, None)?.eval_to_type(env)?, }; - type_with(env, x, Some(t)) + type_with(env, x, Some(t))? } - HirKind::Expr(ekind) => { - let ekind = match ekind { - ExprKind::Lam(binder, annot, body) => { - let annot = type_with(env, annot, None)?; - let annot_nf = annot.eval_to_type(env); - let body_env = env.insert_type(binder, annot_nf); - let body = type_with(&body_env, body, None)?; - ExprKind::Lam(binder.clone(), annot, body) - } - ExprKind::Pi(binder, annot, body) => { - let annot = type_with(env, annot, None)?; - let annot_val = annot.eval_to_type(env); - let body_env = env.insert_type(binder, annot_val); - let body = type_with(&body_env, body, None)?; - ExprKind::Pi(binder.clone(), annot, body) - } - ExprKind::Let(binder, annot, val, body) => { - let val_annot = if let Some(t) = annot { - Some(type_with(env, t, None)?.eval_to_type(env)) - } else { - None - }; - let val = type_with(env, &val, val_annot)?; - let val_nf = val.eval(env); - let body_env = - env.insert_value(&binder, val_nf, val.ty().clone()); - let body = type_with(&body_env, body, None)?; - ExprKind::Let(binder.clone(), None, val, body) - } - _ => ekind.traverse_ref(|e| type_with(env, e, None))?, + + HirKind::Expr(ExprKind::Lam(binder, annot, body)) => { + let annot = type_with(env, annot, None)?; + let annot_nf = annot.eval_to_type(env)?; + let body_env = env.insert_type(binder, annot_nf); + let body = type_with(&body_env, body, None)?; + + let u_annot = annot.ty().as_const().unwrap(); + let u_body = match body.ty().ty(&body_env)? { + Some(k) => k, + _ => return mk_span_err(hir.span(), "Invalid output type"), }; - type_one_layer(env, ekind, annot, hir.span()) + let u = function_check(u_annot, u_body).to_universe(); + let ty_hir = Hir::new( + HirKind::Expr(ExprKind::Pi( + binder.clone(), + annot.to_hir(), + body.ty().to_hir(body_env.as_varenv()), + )), + hir.span(), + ); + let ty = Type::new(ty_hir.eval(env), u); + + TyExpr::from_hir(hir, ty) + } + HirKind::Expr(ExprKind::Pi(binder, annot, body)) => { + let annot = type_with(env, annot, None)?; + let annot_val = annot.eval_to_type(env)?; + let body_env = env.insert_type(binder, annot_val); + let body = type_with(&body_env, body, None)?; + body.ensure_is_type(env)?; + + let ks = annot.ty().as_const().unwrap(); + let kt = body.ty().as_const().unwrap(); + let ty = Type::from_const(function_check(ks, kt)); + TyExpr::from_hir(hir, ty) + } + HirKind::Expr(ExprKind::Let(binder, annot, val, body)) => { + let val_annot = annot + .as_ref() + .map(|t| Ok(type_with(env, t, None)?.eval_to_type(env)?)) + .transpose()?; + let val = type_with(env, &val, val_annot)?; + let val_nf = val.eval(env); + let body_env = env.insert_value(&binder, val_nf, val.ty().clone()); + let body = type_with(&body_env, body, None)?; + let ty = body.ty().clone(); + TyExpr::from_hir(hir, ty) + } + HirKind::Expr(ekind) => { + let ekind = ekind.traverse_ref(|e| type_with(env, e, None))?; + let ty = type_one_layer(env, ekind, hir.span())?; + TyExpr::from_hir(hir, ty) + } + }; + + if let Some(annot) = annot { + if *tyexpr.ty() != annot { + return mk_span_err( + hir.span(), + &format!( + "annot mismatch: {} != {}", + tyexpr.ty().to_expr_tyenv(env), + annot.to_expr_tyenv(env) + ), + ); } } + + Ok(tyexpr) } /// Typecheck an expression and return the expression annotated with types if type-checking @@ -842,6 +793,6 @@ pub(crate) fn typecheck(hir: &Hir) -> Result { /// Like `typecheck`, but additionally checks that the expression's type matches the provided type. pub(crate) fn typecheck_with(hir: &Hir, ty: Hir) -> Result { - let ty = typecheck(&ty)?.eval_to_type(&TyEnv::new()); + let ty = typecheck(&ty)?.eval_to_type(&TyEnv::new())?; type_with(&TyEnv::new(), hir, Some(ty)) } diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs index 18ec9fd..a479b53 100644 --- a/dhall/src/syntax/ast/expr.rs +++ b/dhall/src/syntax/ast/expr.rs @@ -1,3 +1,4 @@ +use crate::semantics::Universe; use crate::syntax::map::{DupTreeMap, DupTreeSet}; use crate::syntax::visitor; use crate::syntax::*; @@ -18,6 +19,12 @@ pub enum Const { Sort, } +impl Const { + pub(crate) fn to_universe(self) -> Universe { + Universe::from_const(self) + } +} + /// Bound variable /// /// The `Label` field is the variable's name (i.e. \"`x`\"). diff --git a/dhall/tests/type-inference/failure/unit/FunctionArgumentTypeNotAType.txt b/dhall/tests/type-inference/failure/unit/FunctionArgumentTypeNotAType.txt index e84eb15..ca5bbcd 100644 --- a/dhall/tests/type-inference/failure/unit/FunctionArgumentTypeNotAType.txt +++ b/dhall/tests/type-inference/failure/unit/FunctionArgumentTypeNotAType.txt @@ -1,7 +1,7 @@ -Type error: error: Invalid input type: `Natural` +Type error: error: Expected a type, found: `1` --> :1:6 | 1 | λ(_ : 1) → _ | ^ this has type: `Natural` | - = help: The input type of a function must have type `Type`, `Kind` or `Sort` + = help: An expression in type position must have type `Type`, `Kind` or `Sort` diff --git a/dhall/tests/type-inference/failure/unit/FunctionTypeArgumentTypeNotAType.txt b/dhall/tests/type-inference/failure/unit/FunctionTypeArgumentTypeNotAType.txt index 4aa0f4f..168ebb9 100644 --- a/dhall/tests/type-inference/failure/unit/FunctionTypeArgumentTypeNotAType.txt +++ b/dhall/tests/type-inference/failure/unit/FunctionTypeArgumentTypeNotAType.txt @@ -1,7 +1,7 @@ -Type error: error: Invalid input type: `Natural` +Type error: error: Expected a type, found: `2` --> :1:0 | 1 | 2 → _ | ^ this has type: `Natural` | - = help: The input type of a function must have type `Type`, `Kind` or `Sort` + = help: An expression in type position must have type `Type`, `Kind` or `Sort` diff --git a/tests_buffer b/tests_buffer index e8eb3d7..1c814ff 100644 --- a/tests_buffer +++ b/tests_buffer @@ -52,6 +52,7 @@ success/ (λ(T : Type) → let x = 0 in λ(x : T) → x) : ∀(T : Type) → ∀(x : T) → T failure/ \(_: Bool) -> assert : (\(_: Bool) -> _) === (\(x: Bool) -> _) + unit/FunctionTypeOutputTypeNotAType Bool -> 1 merge { x = λ(x : Bool) → x } (< x: Bool | y: Natural >.x True) merge { x = λ(_ : Bool) → _, y = 1 } < x = True | y > merge { x = True, y = 1 } < x | y >.x -- cgit v1.3.1 From c451c18103b871e563b12c524bc3feec5451154c Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Sun, 16 Feb 2020 19:48:35 +0000 Subject: Avoid recomputing universes in tck --- dhall/src/semantics/nze/value.rs | 6 +- dhall/src/semantics/tck/tyexpr.rs | 49 ++++++++------- dhall/src/semantics/tck/typecheck.rs | 73 +++++++++++++--------- .../tests/type-inference/failure/recordOfKind.txt | 7 ++- .../failure/unit/RecordMixedKinds3.txt | 7 ++- .../unit/RightBiasedRecordMergeMixedKinds2.txt | 7 ++- .../unit/RightBiasedRecordMergeMixedKinds3.txt | 7 ++- 7 files changed, 97 insertions(+), 59 deletions(-) (limited to 'dhall/tests') diff --git a/dhall/src/semantics/nze/value.rs b/dhall/src/semantics/nze/value.rs index f31fd6c..7084af6 100644 --- a/dhall/src/semantics/nze/value.rs +++ b/dhall/src/semantics/nze/value.rs @@ -4,7 +4,7 @@ use std::rc::Rc; use crate::semantics::nze::lazy; use crate::semantics::{ apply_any, normalize_hir_whnf, normalize_one_layer, squash_textlit, Binder, - BuiltinClosure, Hir, HirKind, NzEnv, NzVar, TyEnv, Type, VarEnv, + BuiltinClosure, Hir, HirKind, NzEnv, NzVar, TyEnv, Type, Universe, VarEnv, }; use crate::syntax::{ BinOp, Builtin, Const, ExprKind, InterpolatedTextContents, Label, LitKind, @@ -139,8 +139,8 @@ impl Value { self.0.kind() } - pub(crate) fn to_type(&self) -> Type { - self.clone().into() + pub(crate) fn to_type(&self, u: impl Into) -> Type { + Type::new(self.clone(), u.into()) } /// Converts a value back to the corresponding AST expression. pub(crate) fn to_expr(&self, opts: ToExprOptions) -> NormalizedExpr { diff --git a/dhall/src/semantics/tck/tyexpr.rs b/dhall/src/semantics/tck/tyexpr.rs index 3c47a81..f6591ba 100644 --- a/dhall/src/semantics/tck/tyexpr.rs +++ b/dhall/src/semantics/tck/tyexpr.rs @@ -11,6 +11,7 @@ pub(crate) struct Universe(u8); #[derive(Debug, Clone, PartialEq, Eq)] pub(crate) struct Type { val: Value, + univ: Universe, } /// A hir expression plus its inferred type. @@ -39,18 +40,28 @@ impl Universe { pub fn next(self) -> Self { Universe(self.0 + 1) } - pub fn previous(self) -> Option { - if self.0 == 0 { - None - } else { - Some(Universe(self.0 - 1)) - } - } } impl Type { - pub fn new(val: Value, _u: Universe) -> Self { - Type { val } + pub fn new(val: Value, univ: Universe) -> Self { + Type { val, univ } + } + /// Creates a new Type and infers its universe by re-typechecking its value. + /// TODO: ideally avoid this function altogether. Would need to store types in RecordType and + /// PiClosure. + pub fn new_infer_universe( + env: &TyEnv, + val: Value, + ) -> Result { + let c = val.to_hir(env.as_varenv()).typecheck(env)?.ty().as_const(); + let u = match c { + Some(c) => c.to_universe(), + None => unreachable!( + "internal type error: this is not a type: {:?}", + val + ), + }; + Ok(Type::new(val, u)) } pub fn from_const(c: Const) -> Self { Self::new(Value::from_const(c), c.to_universe().next()) @@ -66,18 +77,8 @@ impl Type { } /// Get the type of this type - // TODO: avoid recomputing so much - pub fn ty(&self, env: &TyEnv) -> Result, TypeError> { - Ok(self.to_hir(env.as_varenv()).typecheck(env)?.ty().as_const()) - } - /// Get the type of this type - // TODO: avoid recomputing so much - pub fn ty_univ(&self, env: &TyEnv) -> Result { - Ok(match self.ty(env)? { - Some(c) => c.to_universe(), - // TODO: hack, might explode - None => Const::Sort.to_universe().next(), - }) + pub fn ty(&self) -> Universe { + self.univ } pub fn to_value(&self) -> Value { @@ -184,8 +185,8 @@ impl TyExpr { } } -impl From for Type { - fn from(x: Value) -> Type { - Type { val: x } +impl From for Universe { + fn from(x: Const) -> Universe { + Universe::from_const(x) } } diff --git a/dhall/src/semantics/tck/typecheck.rs b/dhall/src/semantics/tck/typecheck.rs index 1281045..45b3168 100644 --- a/dhall/src/semantics/tck/typecheck.rs +++ b/dhall/src/semantics/tck/typecheck.rs @@ -136,24 +136,30 @@ fn type_one_layer( return span_err("InvalidListElement"); } } - if x.ty().ty(env)? != Some(Const::Type) { + if x.ty().ty().as_const() != Some(Const::Type) { return span_err("InvalidListType"); } let t = x.ty().to_value(); - Value::from_builtin(Builtin::List).app(t).to_type() + Value::from_builtin(Builtin::List) + .app(t) + .to_type(Const::Type) } ExprKind::SomeLit(x) => { - if x.ty().ty(env)? != Some(Const::Type) { + if x.ty().ty().as_const() != Some(Const::Type) { return span_err("InvalidOptionalType"); } let t = x.ty().to_value(); - Value::from_builtin(Builtin::Optional).app(t).to_type() + Value::from_builtin(Builtin::Optional) + .app(t) + .to_type(Const::Type) } ExprKind::RecordLit(kvs) => { use std::collections::hash_map::Entry; let mut kts = HashMap::new(); + // An empty record type has type Type + let mut k = Const::Type; for (x, v) in kvs { // Check for duplicated entries match kts.entry(x.clone()) { @@ -164,13 +170,13 @@ fn type_one_layer( }; // Check that the fields have a valid kind - match v.ty().ty(env)? { - Some(_) => {} + match v.ty().ty().as_const() { + Some(c) => k = max(k, c), None => return span_err("InvalidFieldType"), } } - Value::from_kind(ValueKind::RecordType(kts)).to_type() + Value::from_kind(ValueKind::RecordType(kts)).to_type(k) } ExprKind::RecordType(kts) => { use std::collections::hash_map::Entry; @@ -226,29 +232,31 @@ fn type_one_layer( ExprKind::Field(scrut, x) => { match scrut.ty().kind() { ValueKind::RecordType(kts) => match kts.get(&x) { - Some(val) => val.clone().to_type(), + Some(val) => Type::new_infer_universe(env, val.clone())?, None => return span_err("MissingRecordField"), }, - // TODO: branch here only when scrut.ty() is a Const - _ => { - let scrut_nf = scrut.eval(env); - match scrut_nf.kind() { + ValueKind::Const(_) => { + let scrut = scrut.eval_to_type(env)?; + match scrut.kind() { ValueKind::UnionType(kts) => match kts.get(x) { // Constructor has type T -> < x: T, ... > Some(Some(ty)) => { Value::from_kind(ValueKind::PiClosure { binder: Binder::new(x.clone()), annot: ty.clone(), - closure: Closure::new_constant(scrut_nf), + closure: Closure::new_constant( + scrut.to_value(), + ), }) - .to_type() + .to_type(scrut.ty()) } - Some(None) => scrut_nf.to_type(), + Some(None) => scrut, None => return span_err("MissingUnionField"), }, _ => return span_err("NotARecord"), } - } // _ => span_err("NotARecord"), + } + _ => return span_err("NotARecord"), } } ExprKind::Assert(t) => { @@ -295,7 +303,7 @@ fn type_one_layer( } let arg_nf = arg.eval(env); - closure.apply(arg_nf).to_type() + Type::new_infer_universe(env, closure.apply(arg_nf))? } _ => return mkerr( ErrorBuilder::new(format!( @@ -314,7 +322,7 @@ fn type_one_layer( if *x.ty().kind() != ValueKind::from_builtin(Builtin::Bool) { return span_err("InvalidPredicate"); } - if y.ty().ty(env)? != Some(Const::Type) { + if y.ty().ty().as_const() != Some(Const::Type) { return span_err("IfBranchMustBeTerm"); } if y.ty() != z.ty() { @@ -344,7 +352,8 @@ fn type_one_layer( Ok(r_t.clone()) })?; - Value::from_kind(ValueKind::RecordType(kts)).to_type() + let u = max(x.ty().ty(), y.ty().ty()); + Value::from_kind(ValueKind::RecordType(kts)).to_type(u) } ExprKind::BinOp(BinOp::RecursiveRecordMerge, x, y) => { check_rectymerge(&span, env, x.ty().to_value(), y.ty().to_value())?; @@ -357,8 +366,8 @@ fn type_one_layer( )), span.clone(), ); - let x_u = x.ty().ty_univ(env)?; - let y_u = y.ty().ty_univ(env)?; + let x_u = x.ty().ty(); + let y_u = y.ty().ty(); Type::new(hir.eval(env), max(x_u, y_u)) } ExprKind::BinOp(BinOp::RecursiveRecordTypeMerge, x, y) => { @@ -388,7 +397,7 @@ fn type_one_layer( if l.ty() != r.ty() { return span_err("EquivalenceTypeMismatch"); } - if l.ty().ty(env)? != Some(Const::Type) { + if l.ty().ty().as_const() != Some(Const::Type) { return span_err("EquivalenceArgumentsMustBeTerms"); } @@ -480,8 +489,11 @@ fn type_one_layer( ); } + // TODO: this actually doesn't check anything yet match closure.remove_binder() { - Ok(v) => v.to_type(), + Ok(v) => { + Type::new_infer_universe(env, v.clone())? + } Err(()) => { return span_err( "MergeReturnTypeIsDependent", @@ -525,7 +537,9 @@ fn type_one_layer( } }, // Union alternative without type - Some(None) => handler_type.clone().to_type(), + Some(None) => { + Type::new_infer_universe(env, handler_type.clone())? + } None => return span_err("MergeHandlerMissingVariant"), }; match &inferred_type { @@ -560,7 +574,7 @@ fn type_one_layer( } } ExprKind::ToMap(record, annot) => { - if record.ty().ty(env)? != Some(Const::Type) { + if record.ty().ty().as_const() != Some(Const::Type) { return span_err("`toMap` only accepts records of type `Type`"); } let record_t = record.ty(); @@ -623,7 +637,7 @@ fn type_one_layer( kts.insert("mapValue".into(), entry_type); let output_type: Type = Value::from_builtin(Builtin::List) .app(Value::from_kind(ValueKind::RecordType(kts))) - .to_type(); + .to_type(Const::Type); if let Some(annot) = annot { let annot_val = annot.eval_to_type(env)?; if output_type != annot_val { @@ -656,7 +670,10 @@ fn type_one_layer( }; } - Value::from_kind(ValueKind::RecordType(new_kts)).to_type() + Type::new_infer_universe( + env, + Value::from_kind(ValueKind::RecordType(new_kts)), + )? } ExprKind::ProjectionByExpr(record, selection) => { let record_type = record.ty(); @@ -721,7 +738,7 @@ pub(crate) fn type_with( let body = type_with(&body_env, body, None)?; let u_annot = annot.ty().as_const().unwrap(); - let u_body = match body.ty().ty(&body_env)? { + let u_body = match body.ty().ty().as_const() { Some(k) => k, _ => return mk_span_err(hir.span(), "Invalid output type"), }; diff --git a/dhall/tests/type-inference/failure/recordOfKind.txt b/dhall/tests/type-inference/failure/recordOfKind.txt index a5d2465..653fe0b 100644 --- a/dhall/tests/type-inference/failure/recordOfKind.txt +++ b/dhall/tests/type-inference/failure/recordOfKind.txt @@ -1 +1,6 @@ -Type error: error: Sort does not have a type +Type error: error: InvalidFieldType + --> :1:0 + | +1 | { a = Kind } + | ^^^^^^^^^^^^ InvalidFieldType + | diff --git a/dhall/tests/type-inference/failure/unit/RecordMixedKinds3.txt b/dhall/tests/type-inference/failure/unit/RecordMixedKinds3.txt index a5d2465..146018f 100644 --- a/dhall/tests/type-inference/failure/unit/RecordMixedKinds3.txt +++ b/dhall/tests/type-inference/failure/unit/RecordMixedKinds3.txt @@ -1 +1,6 @@ -Type error: error: Sort does not have a type +Type error: error: InvalidFieldType + --> :1:0 + | +1 | { x = Type, y = Kind } + | ^^^^^^^^^^^^^^^^^^^^^^ InvalidFieldType + | diff --git a/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds2.txt b/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds2.txt index a5d2465..521ae05 100644 --- a/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds2.txt +++ b/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds2.txt @@ -1 +1,6 @@ -Type error: error: Sort does not have a type +Type error: error: InvalidFieldType + --> :1:15 + | +1 | { x = Bool } ⫽ { x = Kind } + | ^^^^^^^^^^^^ InvalidFieldType + | diff --git a/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds3.txt b/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds3.txt index a5d2465..3abf62c 100644 --- a/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds3.txt +++ b/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds3.txt @@ -1 +1,6 @@ -Type error: error: Sort does not have a type +Type error: error: InvalidFieldType + --> :1:14 + | +1 | { x = {=} } ⫽ { x = Kind } + | ^^^^^^^^^^^^ InvalidFieldType + | -- cgit v1.3.1