From a0a240c0bcba01d6420da86c31101578aeeca495 Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Fri, 3 May 2019 22:32:24 +0200 Subject: Rework normalization to reduce expensive Value copying --- dhall/src/normalize.rs | 951 +++++++++++++++++++++++++------------------------ 1 file changed, 494 insertions(+), 457 deletions(-) (limited to 'dhall') diff --git a/dhall/src/normalize.rs b/dhall/src/normalize.rs index 1c90c77..13a3678 100644 --- a/dhall/src/normalize.rs +++ b/dhall/src/normalize.rs @@ -4,7 +4,7 @@ use std::rc::Rc; use dhall_core::context::Context; use dhall_core::{ - rc, Builtin, Const, ExprF, Integer, InterpolatedText, + rc, BinOp, Builtin, Const, ExprF, Integer, InterpolatedText, InterpolatedTextContents, Label, Natural, SubExpr, V, X, }; use dhall_generator as dhall; @@ -59,194 +59,6 @@ impl<'a> Typed<'a> { } } -fn apply_builtin(b: Builtin, args: Vec) -> Value { - use dhall_core::Builtin::*; - use Value::*; - - // Return Ok((unconsumed args, returned value)), or Err(()) if value could not be produced. - let ret = match (b, args.as_slice()) { - (OptionalNone, [t, r..]) => { - Ok((r, EmptyOptionalLit(TypeThunk::from_thunk(t.clone())))) - } - (NaturalIsZero, [n, r..]) => match &*n.as_value() { - NaturalLit(n) => Ok((r, BoolLit(*n == 0))), - _ => Err(()), - }, - (NaturalEven, [n, r..]) => match &*n.as_value() { - NaturalLit(n) => Ok((r, BoolLit(*n % 2 == 0))), - _ => Err(()), - }, - (NaturalOdd, [n, r..]) => match &*n.as_value() { - NaturalLit(n) => Ok((r, BoolLit(*n % 2 != 0))), - _ => Err(()), - }, - (NaturalToInteger, [n, r..]) => match &*n.as_value() { - NaturalLit(n) => Ok((r, IntegerLit(*n as isize))), - _ => Err(()), - }, - (NaturalShow, [n, r..]) => match &*n.as_value() { - NaturalLit(n) => Ok(( - r, - TextLit(vec![InterpolatedTextContents::Text(n.to_string())]), - )), - _ => Err(()), - }, - (ListLength, [_, l, r..]) => match &*l.as_value() { - EmptyListLit(_) => Ok((r, NaturalLit(0))), - NEListLit(xs) => Ok((r, NaturalLit(xs.len()))), - _ => Err(()), - }, - (ListHead, [_, l, r..]) => match &*l.as_value() { - EmptyListLit(n) => Ok((r, EmptyOptionalLit(n.clone()))), - NEListLit(xs) => { - Ok((r, NEOptionalLit(xs.iter().next().unwrap().clone()))) - } - _ => Err(()), - }, - (ListLast, [_, l, r..]) => match &*l.as_value() { - EmptyListLit(n) => Ok((r, EmptyOptionalLit(n.clone()))), - NEListLit(xs) => { - Ok((r, NEOptionalLit(xs.iter().rev().next().unwrap().clone()))) - } - _ => Err(()), - }, - (ListReverse, [_, l, r..]) => match &*l.as_value() { - EmptyListLit(n) => Ok((r, EmptyListLit(n.clone()))), - NEListLit(xs) => { - Ok((r, NEListLit(xs.iter().rev().cloned().collect()))) - } - _ => Err(()), - }, - (ListIndexed, [_, l, r..]) => match &*l.as_value() { - EmptyListLit(t) => { - let mut kts = BTreeMap::new(); - kts.insert( - "index".into(), - TypeThunk::from_whnf(Value::from_builtin(Natural)), - ); - kts.insert("value".into(), t.clone()); - Ok((r, EmptyListLit(TypeThunk::from_whnf(RecordType(kts))))) - } - NEListLit(xs) => { - let xs = xs - .iter() - .enumerate() - .map(|(i, e)| { - let i = NaturalLit(i); - let mut kvs = BTreeMap::new(); - kvs.insert("index".into(), Thunk::from_whnf(i)); - kvs.insert("value".into(), e.clone()); - Thunk::from_whnf(RecordLit(kvs)) - }) - .collect(); - Ok((r, NEListLit(xs))) - } - _ => Err(()), - }, - (ListBuild, [t, f, r..]) => match &*f.as_value() { - // fold/build fusion - Value::AppliedBuiltin(ListFold, args) => { - if args.len() >= 2 { - Ok((r, args[1].to_value())) - } else { - // Do we really need to handle this case ? - unimplemented!() - } - } - _ => Ok(( - r, - f.app_val(Value::from_builtin(List).app_thunk(t.clone())) - .app_val(ListConsClosure( - TypeThunk::from_thunk(t.clone()), - None, - )) - .app_val(EmptyListLit(TypeThunk::from_thunk(t.clone()))), - )), - }, - (ListFold, [_, l, _, cons, nil, r..]) => match &*l.as_value() { - EmptyListLit(_) => Ok((r, nil.to_value())), - NEListLit(xs) => { - let mut v = nil.clone(); - for x in xs.iter().rev() { - v = cons - .clone() - .app_thunk(x.clone()) - .app_thunk(v) - .into_thunk(); - } - Ok((r, v.to_value())) - } - _ => Err(()), - }, - (OptionalBuild, [t, f, r..]) => match &*f.as_value() { - // fold/build fusion - Value::AppliedBuiltin(OptionalFold, args) => { - if args.len() >= 2 { - Ok((r, args[1].to_value())) - } else { - // Do we really need to handle this case ? - unimplemented!() - } - } - _ => Ok(( - r, - f.app_val(Value::from_builtin(Optional).app_thunk(t.clone())) - .app_val(OptionalSomeClosure(TypeThunk::from_thunk( - t.clone(), - ))) - .app_val(EmptyOptionalLit(TypeThunk::from_thunk( - t.clone(), - ))), - )), - }, - (OptionalFold, [_, v, _, just, nothing, r..]) => match &*v.as_value() { - EmptyOptionalLit(_) => Ok((r, nothing.to_value())), - NEOptionalLit(x) => Ok((r, just.app_thunk(x.clone()))), - _ => Err(()), - }, - (NaturalBuild, [f, r..]) => match &*f.as_value() { - // fold/build fusion - Value::AppliedBuiltin(NaturalFold, args) => { - if args.len() >= 1 { - Ok((r, args[0].to_value())) - } else { - // Do we really need to handle this case ? - unimplemented!() - } - } - _ => Ok(( - r, - f.app_val(Value::from_builtin(Natural)) - .app_val(NaturalSuccClosure) - .app_val(NaturalLit(0)), - )), - }, - (NaturalFold, [n, t, succ, zero, r..]) => match &*n.as_value() { - NaturalLit(0) => Ok((r, zero.to_value())), - NaturalLit(n) => { - let fold = Value::from_builtin(NaturalFold) - .app(NaturalLit(n - 1)) - .app_thunk(t.clone()) - .app_thunk(succ.clone()) - .app_thunk(zero.clone()); - Ok((r, succ.app_val(fold))) - } - _ => Err(()), - }, - _ => Err(()), - }; - match ret { - Ok((unconsumed_args, mut v)) => { - let n_consumed_args = args.len() - unconsumed_args.len(); - for x in args.into_iter().skip(n_consumed_args) { - v = v.app_thunk(x); - } - v - } - Err(()) => AppliedBuiltin(b, args), - } -} - #[derive(Debug, Clone)] enum EnvItem { Thunk(Thunk), @@ -282,11 +94,6 @@ impl NormalizationContext { pub(crate) fn new() -> Self { NormalizationContext(Rc::new(Context::new())) } - fn insert(&self, x: &Label, e: Thunk) -> Self { - NormalizationContext(Rc::new( - self.0.insert(x.clone(), EnvItem::Thunk(e)), - )) - } fn skip(&self, x: &Label) -> Self { NormalizationContext(Rc::new( self.0 @@ -297,7 +104,7 @@ impl NormalizationContext { fn lookup(&self, var: &V