From 7538e29275720407ac172bb05cdbc028d95ff921 Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Thu, 9 May 2019 16:32:30 +0200 Subject: Make shift fallible and improve shift ergonomics --- dhall/src/core/context.rs | 65 ++++++++++++----------- dhall/src/core/thunk.rs | 40 +++++++------- dhall/src/core/value.rs | 121 ++++++++++++++++++++++++------------------- dhall/src/core/var.rs | 39 +++++++++----- dhall/src/error/mod.rs | 1 + dhall/src/lib.rs | 1 + dhall/src/phase/mod.rs | 18 +++---- dhall/src/phase/typecheck.rs | 13 ++++- 8 files changed, 169 insertions(+), 129 deletions(-) (limited to 'dhall') diff --git a/dhall/src/core/context.rs b/dhall/src/core/context.rs index 236bebe..328bfdc 100644 --- a/dhall/src/core/context.rs +++ b/dhall/src/core/context.rs @@ -33,7 +33,7 @@ impl Context { T: Shift + Clone, { let mut vec = self.0.as_ref().clone(); - vec.push((x.clone(), CtxItem::Kept(x.into(), t.shift(1, &x.into())))); + vec.push((x.clone(), CtxItem::Kept(x.into(), t.under_binder(x)))); Context(Rc::new(vec)) } pub(crate) fn insert_replaced(&self, x: &Label, th: Thunk, t: T) -> Self @@ -51,11 +51,10 @@ impl Context { let mut var = var.clone(); let mut shift_map: HashMap = HashMap::new(); for (l, i) in self.0.iter().rev() { - if var == l.into() { - return Ok(i.shift0_multiple(&shift_map)); - } else { - var = var.shift(-1, &l.into()); - } + match var.over_binder(l) { + None => return Ok(i.under_multiple_binders(&shift_map)), + Some(newvar) => var = newvar, + }; if let CtxItem::Kept(_, _) = i { *shift_map.entry(l.clone()).or_insert(0) += 1; } @@ -67,11 +66,11 @@ impl Context { /// that the passed variable always makes sense in the context of the passed item. /// Once we pass the variable definition, the variable doesn't make sense anymore so we just /// copy the remaining items. - fn do_with_var( + fn do_with_var( &self, var: &AlphaVar, - mut f: impl FnMut(&AlphaVar, &CtxItem) -> CtxItem, - ) -> Self + mut f: impl FnMut(&AlphaVar, &CtxItem) -> Result, E>, + ) -> Result where T: Clone, { @@ -80,32 +79,32 @@ impl Context { let mut var = var.clone(); let mut iter = self.0.iter().rev(); for (l, i) in iter.by_ref() { - vec.push((l.clone(), f(&var, i))); + vec.push((l.clone(), f(&var, i)?)); if let CtxItem::Kept(_, _) = i { - if var == l.into() { - break; - } else { - var = var.shift(-1, &l.into()); - } + match var.over_binder(l) { + None => break, + Some(newvar) => var = newvar, + }; } } for (l, i) in iter { vec.push((l.clone(), (*i).clone())); } vec.reverse(); - Context(Rc::new(vec)) + Ok(Context(Rc::new(vec))) } - fn shift(&self, delta: isize, var: &AlphaVar) -> Self + fn shift(&self, delta: isize, var: &AlphaVar) -> Option where T: Clone + Shift, { - self.do_with_var(var, |var, i| i.shift(delta, &var)) + Some(self.do_with_var(var, |var, i| Ok(i.shift(delta, &var)?))?) } fn subst_shift(&self, var: &AlphaVar, val: &Typed) -> Self where T: Clone + Subst, { - self.do_with_var(var, |var, i| i.subst_shift(&var, val)) + self.do_with_var(var, |var, i| Ok::<_, !>(i.subst_shift(&var, val))) + .unwrap() } } @@ -158,27 +157,27 @@ impl TypecheckContext { } impl Shift for CtxItem { - fn shift(&self, delta: isize, var: &AlphaVar) -> Self { - match self { + fn shift(&self, delta: isize, var: &AlphaVar) -> Option { + Some(match self { CtxItem::Kept(v, t) => { - CtxItem::Kept(v.shift(delta, var), t.shift(delta, var)) + CtxItem::Kept(v.shift(delta, var)?, t.shift(delta, var)?) } CtxItem::Replaced(e, t) => { - CtxItem::Replaced(e.shift(delta, var), t.shift(delta, var)) + CtxItem::Replaced(e.shift(delta, var)?, t.shift(delta, var)?) } - } + }) } } impl Shift for Context { - fn shift(&self, delta: isize, var: &AlphaVar) -> Self { + fn shift(&self, delta: isize, var: &AlphaVar) -> Option { self.shift(delta, var) } } impl Shift for NormalizationContext { - fn shift(&self, delta: isize, var: &AlphaVar) -> Self { - NormalizationContext(self.0.shift(delta, var)) + fn shift(&self, delta: isize, var: &AlphaVar) -> Option { + Some(NormalizationContext(self.0.shift(delta, var)?)) } } @@ -189,12 +188,12 @@ impl> Subst for CtxItem { e.subst_shift(var, val), t.subst_shift(var, val), ), - CtxItem::Kept(v, t) if v == var => { - CtxItem::Replaced(val.to_thunk(), t.subst_shift(var, val)) - } - CtxItem::Kept(v, t) => { - CtxItem::Kept(v.shift(-1, var), t.subst_shift(var, val)) - } + CtxItem::Kept(v, t) => match v.shift(-1, var) { + None => { + CtxItem::Replaced(val.to_thunk(), t.subst_shift(var, val)) + } + Some(newvar) => CtxItem::Kept(newvar, t.subst_shift(var, val)), + }, } } } diff --git a/dhall/src/core/thunk.rs b/dhall/src/core/thunk.rs index a02d7ae..51922e1 100644 --- a/dhall/src/core/thunk.rs +++ b/dhall/src/core/thunk.rs @@ -264,38 +264,38 @@ impl TypeThunk { } impl Shift for Thunk { - fn shift(&self, delta: isize, var: &AlphaVar) -> Self { - self.0.borrow().shift(delta, var).into_thunk() + fn shift(&self, delta: isize, var: &AlphaVar) -> Option { + Some(self.0.borrow().shift(delta, var)?.into_thunk()) } } impl Shift for ThunkInternal { - fn shift(&self, delta: isize, var: &AlphaVar) -> Self { - match self { + fn shift(&self, delta: isize, var: &AlphaVar) -> Option { + Some(match self { ThunkInternal::Unnormalized(ctx, e) => { - ThunkInternal::Unnormalized(ctx.shift(delta, var), e.clone()) + ThunkInternal::Unnormalized(ctx.shift(delta, var)?, e.clone()) } ThunkInternal::PartialExpr(e) => ThunkInternal::PartialExpr( - e.map_ref_with_special_handling_of_binders( - |v| v.shift(delta, var), - |x, v| v.shift(delta, &var.shift(1, &x.into())), - X::clone, - Label::clone, - ), + e.traverse_ref_with_special_handling_of_binders( + |v| Ok(v.shift(delta, var)?), + |x, v| Ok(v.shift(delta, &var.under_binder(x))?), + |x| Ok(X::clone(x)), + |l| Ok(Label::clone(l)), + )?, ), ThunkInternal::Value(m, v) => { - ThunkInternal::Value(*m, v.shift(delta, var)) + ThunkInternal::Value(*m, v.shift(delta, var)?) } - } + }) } } impl Shift for TypeThunk { - fn shift(&self, delta: isize, var: &AlphaVar) -> Self { - match self { - TypeThunk::Thunk(th) => TypeThunk::Thunk(th.shift(delta, var)), - TypeThunk::Type(t) => TypeThunk::Type(t.shift(delta, var)), - } + fn shift(&self, delta: isize, var: &AlphaVar) -> Option { + Some(match self { + TypeThunk::Thunk(th) => TypeThunk::Thunk(th.shift(delta, var)?), + TypeThunk::Type(t) => TypeThunk::Type(t.shift(delta, var)?), + }) } } @@ -317,8 +317,8 @@ impl Subst for ThunkInternal { |v| v.subst_shift(var, val), |x, v| { v.subst_shift( - &var.shift(1, &x.into()), - &val.shift(1, &x.into()), + &var.under_binder(x), + &val.under_binder(x), ) }, X::clone, diff --git a/dhall/src/core/value.rs b/dhall/src/core/value.rs index 8fa24c7..e91b6bc 100644 --- a/dhall/src/core/value.rs +++ b/dhall/src/core/value.rs @@ -98,14 +98,14 @@ impl Value { } Value::ListConsClosure(a, None) => { // Avoid accidental capture of the new `x` variable - let a1 = a.shift(1, &Label::from("x").into()); + let a1 = a.under_binder(Label::from("x")); let a1 = a1.normalize_to_expr_maybe_alpha(alpha); let a = a.normalize_to_expr_maybe_alpha(alpha); dhall::subexpr!(λ(x : a) -> λ(xs : List a1) -> [ x ] # xs) } Value::ListConsClosure(n, Some(v)) => { // Avoid accidental capture of the new `xs` variable - let v = v.shift(1, &Label::from("xs").into()); + let v = v.under_binder(Label::from("xs")); let v = v.normalize_to_expr_maybe_alpha(alpha); let a = n.normalize_to_expr_maybe_alpha(alpha); dhall::subexpr!(λ(xs : List a) -> [ v ] # xs) @@ -322,102 +322,121 @@ impl Value { } impl Shift for Value { - fn shift(&self, delta: isize, var: &AlphaVar) -> Self { - match self { + fn shift(&self, delta: isize, var: &AlphaVar) -> Option { + Some(match self { Value::Lam(x, t, e) => Value::Lam( x.clone(), - t.shift(delta, var), - e.shift(delta, &var.shift(1, &x.into())), + t.shift(delta, var)?, + e.shift(delta, &var.under_binder(x))?, ), Value::AppliedBuiltin(b, args) => Value::AppliedBuiltin( *b, - args.iter().map(|v| v.shift(delta, var)).collect(), + args.iter() + .map(|v| Ok(v.shift(delta, var)?)) + .collect::>()?, ), Value::NaturalSuccClosure => Value::NaturalSuccClosure, Value::OptionalSomeClosure(tth) => { - Value::OptionalSomeClosure(tth.shift(delta, var)) + Value::OptionalSomeClosure(tth.shift(delta, var)?) } Value::ListConsClosure(t, v) => Value::ListConsClosure( - t.shift(delta, var), - v.as_ref().map(|v| v.shift(delta, var)), + t.shift(delta, var)?, + v.as_ref().map(|v| Ok(v.shift(delta, var)?)).transpose()?, ), Value::Pi(x, t, e) => Value::Pi( x.clone(), - t.shift(delta, var), - e.shift(delta, &var.shift(1, &x.into())), + t.shift(delta, var)?, + e.shift(delta, &var.under_binder(x))?, ), - Value::Var(v) => Value::Var(v.shift(delta, var)), + Value::Var(v) => Value::Var(v.shift(delta, var)?), Value::Const(c) => Value::Const(*c), Value::BoolLit(b) => Value::BoolLit(*b), Value::NaturalLit(n) => Value::NaturalLit(*n), Value::IntegerLit(n) => Value::IntegerLit(*n), Value::DoubleLit(n) => Value::DoubleLit(*n), Value::EmptyOptionalLit(tth) => { - Value::EmptyOptionalLit(tth.shift(delta, var)) + Value::EmptyOptionalLit(tth.shift(delta, var)?) } Value::NEOptionalLit(th) => { - Value::NEOptionalLit(th.shift(delta, var)) + Value::NEOptionalLit(th.shift(delta, var)?) } Value::EmptyListLit(tth) => { - Value::EmptyListLit(tth.shift(delta, var)) + Value::EmptyListLit(tth.shift(delta, var)?) } Value::NEListLit(elts) => Value::NEListLit( - elts.iter().map(|v| v.shift(delta, var)).collect(), + elts.iter() + .map(|v| Ok(v.shift(delta, var)?)) + .collect::>()?, ), Value::RecordLit(kvs) => Value::RecordLit( kvs.iter() - .map(|(k, v)| (k.clone(), v.shift(delta, var))) - .collect(), + .map(|(k, v)| Ok((k.clone(), v.shift(delta, var)?))) + .collect::>()?, ), Value::RecordType(kvs) => Value::RecordType( kvs.iter() - .map(|(k, v)| (k.clone(), v.shift(delta, var))) - .collect(), + .map(|(k, v)| Ok((k.clone(), v.shift(delta, var)?))) + .collect::>()?, ), Value::UnionType(kts) => Value::UnionType( kts.iter() .map(|(k, v)| { - (k.clone(), v.as_ref().map(|v| v.shift(delta, var))) + Ok(( + k.clone(), + v.as_ref() + .map(|v| Ok(v.shift(delta, var)?)) + .transpose()?, + )) }) - .collect(), + .collect::>()?, ), Value::UnionConstructor(x, kts) => Value::UnionConstructor( x.clone(), kts.iter() .map(|(k, v)| { - (k.clone(), v.as_ref().map(|v| v.shift(delta, var))) + Ok(( + k.clone(), + v.as_ref() + .map(|v| Ok(v.shift(delta, var)?)) + .transpose()?, + )) }) - .collect(), + .collect::>()?, ), Value::UnionLit(x, v, kts) => Value::UnionLit( x.clone(), - v.shift(delta, var), + v.shift(delta, var)?, kts.iter() .map(|(k, v)| { - (k.clone(), v.as_ref().map(|v| v.shift(delta, var))) + Ok(( + k.clone(), + v.as_ref() + .map(|v| Ok(v.shift(delta, var)?)) + .transpose()?, + )) }) - .collect(), + .collect::>()?, ), Value::TextLit(elts) => Value::TextLit( elts.iter() .map(|contents| { use InterpolatedTextContents::{Expr, Text}; - match contents { - Expr(th) => Expr(th.shift(delta, var)), + Ok(match contents { + Expr(th) => Expr(th.shift(delta, var)?), Text(s) => Text(s.clone()), - } + }) }) - .collect(), + .collect::>()?, ), - Value::PartialExpr(e) => { - Value::PartialExpr(e.map_ref_with_special_handling_of_binders( - |v| v.shift(delta, var), - |x, v| v.shift(delta, &var.shift(1, &x.into())), - X::clone, - Label::clone, - )) - } - } + Value::PartialExpr(e) => Value::PartialExpr( + e.traverse_ref_with_special_handling_of_binders( + |v| Ok(v.shift(delta, var)?), + |x, v| Ok(v.shift(delta, &var.under_binder(x))?), + |x| Ok(X::clone(x)), + |l| Ok(Label::clone(l)), + )?, + ), + }) } } @@ -435,8 +454,8 @@ impl Subst for Value { |v| v.subst_shift(var, val), |x, v| { v.subst_shift( - &var.shift(1, &x.into()), - &val.shift(1, &x.into()), + &var.under_binder(x), + &val.under_binder(x), ) }, X::clone, @@ -456,10 +475,7 @@ impl Subst for Value { Value::Lam(x, t, e) => Value::Lam( x.clone(), t.subst_shift(var, val), - e.subst_shift( - &var.shift(1, &x.into()), - &val.shift(1, &x.into()), - ), + e.subst_shift(&var.under_binder(x), &val.under_binder(x)), ), Value::NaturalSuccClosure => Value::NaturalSuccClosure, Value::OptionalSomeClosure(tth) => { @@ -472,13 +488,12 @@ impl Subst for Value { Value::Pi(x, t, e) => Value::Pi( x.clone(), t.subst_shift(var, val), - e.subst_shift( - &var.shift(1, &x.into()), - &val.shift(1, &x.into()), - ), + e.subst_shift(&var.under_binder(x), &val.under_binder(x)), ), - Value::Var(v) if v == var => val.to_value().clone(), - Value::Var(v) => Value::Var(v.shift(-1, var)), + Value::Var(v) => match v.shift(-1, var) { + None => val.to_value().clone(), + Some(newvar) => Value::Var(newvar), + }, Value::Const(c) => Value::Const(*c), Value::BoolLit(b) => Value::BoolLit(*b), Value::NaturalLit(n) => Value::NaturalLit(*n), diff --git a/dhall/src/core/var.rs b/dhall/src/core/var.rs index ba92172..ea7e55f 100644 --- a/dhall/src/core/var.rs +++ b/dhall/src/core/var.rs @@ -17,19 +17,34 @@ pub(crate) struct AlphaVar { pub(crate) struct AlphaLabel(Label); pub(crate) trait Shift: Sized { - fn shift(&self, delta: isize, var: &AlphaVar) -> Self; + // Shift an expression to move it around binders without changing the meaning of its free + // variables. Shift by 1 to move an expression under a binder. Shift by -1 to extract an + // expression from under a binder, if the expression does not refer to that bound variable. + // Returns None if delta was negative and the variable was free in the expression. + fn shift(&self, delta: isize, var: &AlphaVar) -> Option; - fn shift0(&self, delta: isize, x: &Label) -> Self { - self.shift(delta, &x.into()) + fn over_binder(&self, x: T) -> Option + where + T: Into, + { + self.shift(-1, &x.into()) } - fn shift0_multiple(&self, shift_map: &HashMap) -> Self + fn under_binder(&self, x: T) -> Self + where + T: Into, + { + // Can't fail since delta is positive + self.shift(1, &x.into()).unwrap() + } + + fn under_multiple_binders(&self, shift_map: &HashMap) -> Self where Self: Clone, { let mut v = self.clone(); for (x, n) in shift_map { - v = v.shift0(*n, x); + v = v.shift(*n as isize, &x.into()).unwrap(); } v } @@ -68,20 +83,20 @@ impl AlphaLabel { } impl Shift for AlphaVar { - fn shift(&self, delta: isize, var: &AlphaVar) -> Self { - AlphaVar { - normal: self.normal.shift(delta, &var.normal), + fn shift(&self, delta: isize, var: &AlphaVar) -> Option { + Some(AlphaVar { + normal: self.normal.shift(delta, &var.normal)?, alpha: match (&self.alpha, &var.alpha) { - (Some(x), Some(v)) => Some(x.shift(delta, v)), + (Some(x), Some(v)) => Some(x.shift(delta, v)?), _ => None, }, - } + }) } } impl Shift for () { - fn shift(&self, _delta: isize, _var: &AlphaVar) -> Self { - () + fn shift(&self, _delta: isize, _var: &AlphaVar) -> Option { + Some(()) } } diff --git a/dhall/src/error/mod.rs b/dhall/src/error/mod.rs index ff748bc..3f482f6 100644 --- a/dhall/src/error/mod.rs +++ b/dhall/src/error/mod.rs @@ -69,6 +69,7 @@ pub(crate) enum TypeMessage { MergeVariantMissingHandler(Label), MergeAnnotMismatch, MergeHandlerTypeMismatch, + MergeHandlerReturnTypeMustNotBeDependent, ProjectionMustBeRecord, ProjectionMissingEntry, Sort, diff --git a/dhall/src/lib.rs b/dhall/src/lib.rs index 8d1496a..b35b2ae 100644 --- a/dhall/src/lib.rs +++ b/dhall/src/lib.rs @@ -6,6 +6,7 @@ #![feature(bind_by_move_pattern_guards)] #![feature(try_trait)] #![feature(inner_deref)] +#![feature(never_type)] #![cfg_attr(test, feature(custom_inner_attributes))] #![allow( clippy::type_complexity, diff --git a/dhall/src/phase/mod.rs b/dhall/src/phase/mod.rs index db0a2b9..50103a0 100644 --- a/dhall/src/phase/mod.rs +++ b/dhall/src/phase/mod.rs @@ -238,26 +238,26 @@ impl Normalized { } impl Shift for Typed { - fn shift(&self, delta: isize, var: &AlphaVar) -> Self { - match self { + fn shift(&self, delta: isize, var: &AlphaVar) -> Option { + Some(match self { Typed::Value(th, t) => Typed::Value( - th.shift(delta, var), - t.as_ref().map(|x| x.shift(delta, var)), + th.shift(delta, var)?, + t.as_ref().map(|x| Ok(x.shift(delta, var)?)).transpose()?, ), Typed::Const(c) => Typed::Const(*c), - } + }) } } impl Shift for Type { - fn shift(&self, delta: isize, var: &AlphaVar) -> Self { - Type(Box::new(self.0.shift(delta, var))) + fn shift(&self, delta: isize, var: &AlphaVar) -> Option { + Some(Type(Box::new(self.0.shift(delta, var)?))) } } impl Shift for Normalized { - fn shift(&self, delta: isize, var: &AlphaVar) -> Self { - Normalized(self.0.shift(delta, var)) + fn shift(&self, delta: isize, var: &AlphaVar) -> Option { + Some(Normalized(self.0.shift(delta, var)?)) } } diff --git a/dhall/src/phase/typecheck.rs b/dhall/src/phase/typecheck.rs index 2c625fb..497a703 100644 --- a/dhall/src/phase/typecheck.rs +++ b/dhall/src/phase/typecheck.rs @@ -732,6 +732,7 @@ fn type_last_layer( ))) } }; + ensure_equal!(&variant_type, &tx, { mkerr(TypeMismatch( handler_type.to_typed(), @@ -739,8 +740,16 @@ fn type_last_layer( variant_type.to_typed(), )) }); - // TODO: check that x is not free in tb first - tb.shift(-1, &x.into()) + + // Extract `tb` from under the `x` binder. Fails is `x` was free in `tb`. + match tb.over_binder(x) { + Some(x) => x, + None => { + return Err(mkerr( + MergeHandlerReturnTypeMustNotBeDependent, + )) + } + } } // Union alternative without type Some(None) => handler.to_type(ctx)?, -- cgit v1.2.3