Merge pull request #196 from Nadrieril/allow-mutation-in-normalization

2 files changed, 95 insertions, 149 deletions

diff --git a/dhall/src/operations/normalization.rs b/dhall/src/operations/normalization.rs
index dbd58f9..28375b2 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<Nir>) -> Ret {
+pub fn normalize_operation(opkind: OpKind<Nir>) -> Ret {
     use self::BinOp::RightBiasedRecordMerge;
     use NirKind::{
         EmptyListLit, EmptyOptionalLit, NEListLit, NEOptionalLit, Num, Op,
@@ -197,46 +195,45 @@ pub fn normalize_operation(opkind: &OpKind<Nir>) -> 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<Nir>) -> 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<Nir>) -> 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<Nir>) -> 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,73 +285,45 @@ pub fn normalize_operation(opkind: &OpKind<Nir>) -> 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<Nir> = Some(record.clone());
-            let mut visited: Vec<(&Label, HashMap<Label, Nir>)> = 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")
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<Type, TypeError> {
     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<Tir<'_>>,
+    opkind: OpKind<Tir<'_>>,
 ) -> Result<Type, TypeError> {
     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<Nir> =
-                Some(record.ty().as_nir().clone());
-            let mut visited: Vec<(&Label, HashMap<Label, Nir>)> = 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")