From 055e70f52bb0d8740ce6ac00b98ae856c29642b2 Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Mon, 2 Nov 2020 01:03:59 +0000 Subject: Try to keep ownership of `Nir`s when convenient The goal is that we might avoid cloning internals in the common case where a value is not shared --- dhall/src/operations/normalization.rs | 105 +++++++++++++++++----------------- 1 file changed, 51 insertions(+), 54 deletions(-) (limited to 'dhall/src/operations') diff --git a/dhall/src/operations/normalization.rs b/dhall/src/operations/normalization.rs index dbd58f9..e9ae825 100644 --- a/dhall/src/operations/normalization.rs +++ b/dhall/src/operations/normalization.rs @@ -8,52 +8,52 @@ use crate::semantics::{ }; use crate::syntax::{ExprKind, Label, NumKind}; -fn normalize_binop(o: BinOp, x: &Nir, y: &Nir) -> Ret { +fn normalize_binop(o: BinOp, x: Nir, y: Nir) -> Ret { use BinOp::*; use NirKind::{EmptyListLit, NEListLit, Num, RecordLit, RecordType}; use NumKind::{Bool, Natural}; match (o, x.kind(), y.kind()) { - (BoolAnd, Num(Bool(true)), _) => ret_ref(y), - (BoolAnd, _, Num(Bool(true))) => ret_ref(x), + (BoolAnd, Num(Bool(true)), _) => ret_nir(y), + (BoolAnd, _, Num(Bool(true))) => ret_nir(x), (BoolAnd, Num(Bool(false)), _) => ret_kind(Num(Bool(false))), (BoolAnd, _, Num(Bool(false))) => ret_kind(Num(Bool(false))), - (BoolAnd, _, _) if x == y => ret_ref(x), + (BoolAnd, _, _) if x == y => ret_nir(x), (BoolOr, Num(Bool(true)), _) => ret_kind(Num(Bool(true))), (BoolOr, _, Num(Bool(true))) => ret_kind(Num(Bool(true))), - (BoolOr, Num(Bool(false)), _) => ret_ref(y), - (BoolOr, _, Num(Bool(false))) => ret_ref(x), - (BoolOr, _, _) if x == y => ret_ref(x), - (BoolEQ, Num(Bool(true)), _) => ret_ref(y), - (BoolEQ, _, Num(Bool(true))) => ret_ref(x), + (BoolOr, Num(Bool(false)), _) => ret_nir(y), + (BoolOr, _, Num(Bool(false))) => ret_nir(x), + (BoolOr, _, _) if x == y => ret_nir(x), + (BoolEQ, Num(Bool(true)), _) => ret_nir(y), + (BoolEQ, _, Num(Bool(true))) => ret_nir(x), (BoolEQ, Num(Bool(x)), Num(Bool(y))) => ret_kind(Num(Bool(x == y))), (BoolEQ, _, _) if x == y => ret_kind(Num(Bool(true))), - (BoolNE, Num(Bool(false)), _) => ret_ref(y), - (BoolNE, _, Num(Bool(false))) => ret_ref(x), + (BoolNE, Num(Bool(false)), _) => ret_nir(y), + (BoolNE, _, Num(Bool(false))) => ret_nir(x), (BoolNE, Num(Bool(x)), Num(Bool(y))) => ret_kind(Num(Bool(x != y))), (BoolNE, _, _) if x == y => ret_kind(Num(Bool(false))), - (NaturalPlus, Num(Natural(0)), _) => ret_ref(y), - (NaturalPlus, _, Num(Natural(0))) => ret_ref(x), + (NaturalPlus, Num(Natural(0)), _) => ret_nir(y), + (NaturalPlus, _, Num(Natural(0))) => ret_nir(x), (NaturalPlus, Num(Natural(x)), Num(Natural(y))) => { ret_kind(Num(Natural(x + y))) } (NaturalTimes, Num(Natural(0)), _) => ret_kind(Num(Natural(0))), (NaturalTimes, _, Num(Natural(0))) => ret_kind(Num(Natural(0))), - (NaturalTimes, Num(Natural(1)), _) => ret_ref(y), - (NaturalTimes, _, Num(Natural(1))) => ret_ref(x), + (NaturalTimes, Num(Natural(1)), _) => ret_nir(y), + (NaturalTimes, _, Num(Natural(1))) => ret_nir(x), (NaturalTimes, Num(Natural(x)), Num(Natural(y))) => { ret_kind(Num(Natural(x * y))) } - (ListAppend, EmptyListLit(_), _) => ret_ref(y), - (ListAppend, _, EmptyListLit(_)) => ret_ref(x), + (ListAppend, EmptyListLit(_), _) => ret_nir(y), + (ListAppend, _, EmptyListLit(_)) => ret_nir(x), (ListAppend, NEListLit(xs), NEListLit(ys)) => { ret_kind(NEListLit(xs.iter().chain(ys.iter()).cloned().collect())) } - (TextAppend, NirKind::TextLit(x), _) if x.is_empty() => ret_ref(y), - (TextAppend, _, NirKind::TextLit(y)) if y.is_empty() => ret_ref(x), + (TextAppend, NirKind::TextLit(x), _) if x.is_empty() => ret_nir(y), + (TextAppend, _, NirKind::TextLit(y)) if y.is_empty() => ret_nir(x), (TextAppend, NirKind::TextLit(x), NirKind::TextLit(y)) => { ret_kind(NirKind::TextLit(x.concat(y))) } @@ -65,10 +65,10 @@ fn normalize_binop(o: BinOp, x: &Nir, y: &Nir) -> Ret { )), (RightBiasedRecordMerge, _, RecordLit(kvs)) if kvs.is_empty() => { - ret_ref(x) + ret_nir(x) } (RightBiasedRecordMerge, RecordLit(kvs), _) if kvs.is_empty() => { - ret_ref(y) + ret_nir(y) } (RightBiasedRecordMerge, RecordLit(kvs1), RecordLit(kvs2)) => { let mut kvs = kvs2.clone(); @@ -78,13 +78,13 @@ fn normalize_binop(o: BinOp, x: &Nir, y: &Nir) -> Ret { } ret_kind(RecordLit(kvs)) } - (RightBiasedRecordMerge, _, _) if x == y => ret_ref(y), + (RightBiasedRecordMerge, _, _) if x == y => ret_nir(y), (RecursiveRecordMerge, _, RecordLit(kvs)) if kvs.is_empty() => { - ret_ref(x) + ret_nir(x) } (RecursiveRecordMerge, RecordLit(kvs), _) if kvs.is_empty() => { - ret_ref(y) + ret_nir(y) } (RecursiveRecordMerge, RecordLit(kvs1), RecordLit(kvs2)) => { let kvs = merge_maps(kvs1, kvs2, |_, v1, v2| { @@ -113,11 +113,9 @@ fn normalize_binop(o: BinOp, x: &Nir, y: &Nir) -> Ret { ret_kind(RecordType(kts)) } - (Equivalence, _, _) => { - ret_kind(NirKind::Equivalence(x.clone(), y.clone())) - } + (Equivalence, _, _) => ret_kind(NirKind::Equivalence(x, y)), - _ => ret_op(OpKind::BinOp(o, x.clone(), y.clone())), + _ => ret_op(OpKind::BinOp(o, x, y)), } } @@ -189,7 +187,7 @@ fn normalize_field(v: &Nir, field: &Label) -> Ret { } } -pub fn normalize_operation(opkind: &OpKind) -> Ret { +pub fn normalize_operation(opkind: OpKind) -> Ret { use self::BinOp::RightBiasedRecordMerge; use NirKind::{ EmptyListLit, EmptyOptionalLit, NEListLit, NEOptionalLit, Num, Op, @@ -197,46 +195,45 @@ pub fn normalize_operation(opkind: &OpKind) -> Ret { }; use NumKind::Bool; use OpKind::*; - let nothing_to_do = || ret_op(opkind.clone()); match opkind { - App(v, a) => ret_kind(v.app_to_kind(a.clone())), - BinOp(o, x, y) => normalize_binop(*o, x, y), + App(v, a) => ret_kind(v.app_to_kind(a)), + BinOp(o, x, y) => normalize_binop(o, x, y), BoolIf(b, e1, e2) => { match b.kind() { - Num(Bool(true)) => ret_ref(e1), - Num(Bool(false)) => ret_ref(e2), + Num(Bool(true)) => ret_nir(e1), + Num(Bool(false)) => ret_nir(e2), _ => { match (e1.kind(), e2.kind()) { // Simplify `if b then True else False` - (Num(Bool(true)), Num(Bool(false))) => ret_ref(b), - _ if e1 == e2 => ret_ref(e1), - _ => nothing_to_do(), + (Num(Bool(true)), Num(Bool(false))) => ret_nir(b), + _ if e1 == e2 => ret_nir(e1), + _ => ret_op(BoolIf(b, e1, e2)), } } } } - Merge(handlers, variant, _) => match handlers.kind() { + Merge(handlers, variant, ty) => match handlers.kind() { RecordLit(kvs) => match variant.kind() { UnionConstructor(l, _) => match kvs.get(l) { Some(h) => ret_ref(h), - None => nothing_to_do(), + None => ret_op(Merge(handlers, variant, ty)), }, UnionLit(l, v, _) => match kvs.get(l) { Some(h) => ret_kind(h.app_to_kind(v.clone())), - None => nothing_to_do(), + None => ret_op(Merge(handlers, variant, ty)), }, EmptyOptionalLit(_) => match kvs.get("None") { Some(h) => ret_ref(h), - None => nothing_to_do(), + None => ret_op(Merge(handlers, variant, ty)), }, NEOptionalLit(v) => match kvs.get("Some") { Some(h) => ret_kind(h.app_to_kind(v.clone())), - None => nothing_to_do(), + None => ret_op(Merge(handlers, variant, ty)), }, - _ => nothing_to_do(), + _ => ret_op(Merge(handlers, variant, ty)), }, - _ => nothing_to_do(), + _ => ret_op(Merge(handlers, variant, ty)), }, ToMap(v, annot) => match v.kind() { RecordLit(kvs) if kvs.is_empty() => { @@ -244,7 +241,7 @@ pub fn normalize_operation(opkind: &OpKind) -> Ret { Some(NirKind::ListType(t)) => { ret_kind(EmptyListLit(t.clone())) } - _ => nothing_to_do(), + _ => ret_op(ToMap(v, annot)), } } RecordLit(kvs) => ret_kind(NEListLit( @@ -258,9 +255,9 @@ pub fn normalize_operation(opkind: &OpKind) -> Ret { }) .collect(), )), - _ => nothing_to_do(), + _ => ret_op(ToMap(v, annot)), }, - Field(v, field) => normalize_field(v, field), + Field(v, field) => normalize_field(&v, &field), Projection(_, ls) if ls.is_empty() => { ret_kind(RecordLit(HashMap::new())) } @@ -271,12 +268,12 @@ pub fn normalize_operation(opkind: &OpKind) -> Ret { .collect(), )), Op(Projection(v2, _)) => { - normalize_operation(&Projection(v2.clone(), ls.clone())) + normalize_operation(Projection(v2.clone(), ls)) } Op(BinOp(RightBiasedRecordMerge, l, r)) => match r.kind() { RecordLit(kvs) => { let r_keys = kvs.keys().cloned().collect(); - normalize_operation(&BinOp( + normalize_operation(BinOp( RightBiasedRecordMerge, Nir::from_partial_expr(ExprKind::Op(Projection( l.clone(), @@ -288,16 +285,16 @@ pub fn normalize_operation(opkind: &OpKind) -> Ret { ))), )) } - _ => nothing_to_do(), + _ => ret_op(Projection(v, ls)), }, - _ => nothing_to_do(), + _ => ret_op(Projection(v, ls)), }, ProjectionByExpr(v, t) => match t.kind() { - RecordType(kts) => normalize_operation(&Projection( - v.clone(), + RecordType(kts) => normalize_operation(Projection( + v, kts.keys().cloned().collect(), )), - _ => nothing_to_do(), + _ => ret_op(ProjectionByExpr(v, t)), }, With(record, labels, expr) => { let mut current_nir: Option = Some(record.clone()); -- cgit v1.2.3 From 9e8ae42b2742e27a70a7fb8ea79ae21060d43fc1 Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Mon, 2 Nov 2020 03:47:15 +0000 Subject: Normalize `with` by mutation. This is Cow-style mutation: we clone only what's shared and then mutate it. This it more legible and more efficient than the immutable version. --- dhall/src/operations/normalization.rs | 76 +++++++++++------------------------ 1 file changed, 24 insertions(+), 52 deletions(-) (limited to 'dhall/src/operations') diff --git a/dhall/src/operations/normalization.rs b/dhall/src/operations/normalization.rs index e9ae825..28375b2 100644 --- a/dhall/src/operations/normalization.rs +++ b/dhall/src/operations/normalization.rs @@ -296,62 +296,34 @@ pub fn normalize_operation(opkind: OpKind) -> Ret { )), _ => ret_op(ProjectionByExpr(v, t)), }, - With(record, labels, expr) => { - let mut current_nir: Option = Some(record.clone()); - let mut visited: Vec<(&Label, HashMap)> = Vec::new(); - let mut to_create = Vec::new(); - - // To be used when an abstract entry is reached - let mut abstract_nir = None; - - for label in labels { - match current_nir { - None => to_create.push(label.clone()), - Some(nir) => match nir.kind() { - RecordLit(kvs) => { - current_nir = kvs.get(label).cloned(); - visited.push((label, kvs.clone())); - } - // Handle partially abstract case - _ => { - abstract_nir = Some(nir); - to_create.push(label.clone()); - current_nir = None; - } - }, + With(mut record, labels, expr) => { + let mut labels = labels.into_iter(); + let mut current = &mut record; + // We dig through the current record with the provided labels. + while let RecordLit(kvs) = current.kind_mut() { + if let Some(label) = labels.next() { + // Get existing entry or insert empty record into it. + let nir = kvs.entry(label).or_insert_with(|| { + Nir::from_kind(RecordLit(HashMap::new())) + }); + // Disgusting, but the normal assignment works with -Zpolonius, so this + // is safe. See https://github.com/rust-lang/rust/issues/70255 . + current = unsafe { &mut *(nir as *mut _) }; + } else { + break; } } - // Create Nir for record bottom up - let mut nir = expr.clone(); - - match abstract_nir { - // No abstract nir, creating singleton records - None => { - while let Some(label) = to_create.pop() { - let rec = - RecordLit(once((label.clone(), nir)).collect()); - nir = Nir::from_kind(rec); - } - } - // Abstract nir, creating with op - Some(abstract_nir) => { - nir = Nir::from_kind(Op(OpKind::With( - abstract_nir, - to_create, - nir, - ))); - } - } - - // Update visited records - while let Some((label, mut kvs)) = visited.pop() { - kvs.insert(label.clone(), nir); - let rec = RecordLit(kvs); - nir = Nir::from_kind(rec); - } + // If there are still some fields to dig through, we need to create a `with` expression + // with the remaining fields. + let labels: Vec<_> = labels.collect(); + *current = if labels.is_empty() { + expr + } else { + Nir::from_kind(Op(OpKind::With(current.clone(), labels, expr))) + }; - ret_nir(nir) + ret_nir(record) } Completion(..) => { unreachable!("This case should have been handled in resolution") -- cgit v1.2.3 From 85d946016d67515aa70fa01338512e3fd7df408e Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Mon, 2 Nov 2020 04:06:05 +0000 Subject: Typecheck `with` using mutation --- dhall/src/operations/typecheck.rs | 63 +++++++++++++-------------------------- 1 file changed, 20 insertions(+), 43 deletions(-) (limited to 'dhall/src/operations') diff --git a/dhall/src/operations/typecheck.rs b/dhall/src/operations/typecheck.rs index 9329aff..3016fea 100644 --- a/dhall/src/operations/typecheck.rs +++ b/dhall/src/operations/typecheck.rs @@ -48,8 +48,8 @@ fn typecheck_binop( env: &TyEnv, span: Span, op: BinOp, - l: &Tir<'_>, - r: &Tir<'_>, + l: Tir<'_>, + r: Tir<'_>, ) -> Result { let span_err = |msg: &str| mk_span_err(span.clone(), msg); use BinOp::*; @@ -290,7 +290,7 @@ fn typecheck_merge( pub fn typecheck_operation( env: &TyEnv, span: Span, - opkind: &OpKind>, + opkind: OpKind>, ) -> Result { let span_err = |msg: &str| mk_span_err(span.clone(), msg); use NirKind::{ListType, PiClosure, RecordType, UnionType}; @@ -345,7 +345,7 @@ pub fn typecheck_operation( ), } } - BinOp(o, l, r) => typecheck_binop(env, span, *o, l, r)?, + BinOp(o, l, r) => typecheck_binop(env, span, o, l, r)?, BoolIf(x, y, z) => { if *x.ty().kind() != NirKind::from_builtin(Builtin::Bool) { return span_err("InvalidPredicate"); @@ -360,7 +360,7 @@ pub fn typecheck_operation( y.ty().clone() } Merge(record, scrut, type_annot) => { - typecheck_merge(env, span, record, scrut, type_annot.as_ref())? + typecheck_merge(env, span, &record, &scrut, type_annot.as_ref())? } ToMap(record, annot) => { if record.ty().ty().as_const() != Some(Const::Type) { @@ -434,14 +434,14 @@ pub fn typecheck_operation( } Field(scrut, x) => { match scrut.ty().kind() { - RecordType(kts) => match kts.get(x) { + RecordType(kts) => match kts.get(&x) { Some(val) => Type::new_infer_universe(env, val.clone())?, None => return span_err("MissingRecordField"), }, NirKind::Const(_) => { let scrut = scrut.eval_to_type(env)?; match scrut.kind() { - UnionType(kts) => match kts.get(x) { + UnionType(kts) => match kts.get(&x) { // Constructor has type T -> < x: T, ... > Some(Some(ty)) => Nir::from_kind(PiClosure { binder: Binder::new(x.clone()), @@ -467,7 +467,7 @@ pub fn typecheck_operation( let mut new_kts = HashMap::new(); for l in labels { - match kts.get(l) { + match kts.get(&l) { None => return span_err("ProjectionMissingEntry"), Some(t) => { new_kts.insert(l.clone(), t.clone()); @@ -504,45 +504,22 @@ pub fn typecheck_operation( selection_val } With(record, labels, expr) => { - use crate::syntax::Label; - use std::iter::once; - - let mut current_nir: Option = - Some(record.ty().as_nir().clone()); - let mut visited: Vec<(&Label, HashMap)> = Vec::new(); - let mut to_create = Vec::new(); - + let mut record_ty = record.into_ty().into_nir(); + let mut current = &mut record_ty; + // We dig through the current record type with the provided labels. for label in labels { - match current_nir { - None => to_create.push(label), - Some(nir) => { - let kts = (match nir.kind() { - NirKind::RecordType(kts) => Ok(kts.clone()), - _ => mk_span_err(span.clone(), "WithMustBeRecord"), // TODO better error - })?; - - current_nir = kts.get(label).cloned(); - visited.push((label, kts)); - } + if let RecordType(kts) = current.kind_mut() { + // Get existing entry or insert empty record type into it. + current = kts.entry(label).or_insert_with(|| { + Nir::from_kind(RecordType(HashMap::new())) + }); + } else { + return mk_span_err(span.clone(), "WithMustBeRecord"); } } + *current = expr.into_ty().into_nir(); - // Create Nir for record type bottom up - let mut nir = expr.ty().as_nir().clone(); - - while let Some(label) = to_create.pop() { - let rec = RecordType(once((label.clone(), nir)).collect()); - nir = Nir::from_kind(rec); - } - - // Update visited records - while let Some((label, mut kts)) = visited.pop() { - kts.insert(label.clone(), nir); - let rec = RecordType(kts); - nir = Nir::from_kind(rec); - } - - Type::new_infer_universe(env, nir)? + Type::new_infer_universe(env, record_ty)? } Completion(..) => { unreachable!("This case should have been handled in resolution") -- cgit v1.2.3