Reuse work to avoid complicated recursion in record merging

3 files changed, 25 insertions, 151 deletions

diff --git a/dhall/src/error/mod.rs b/dhall/src/error/mod.rs
index b34c3a2..3445768 100644
--- a/dhall/src/error/mod.rs
+++ b/dhall/src/error/mod.rs
@@ -55,7 +55,6 @@ pub(crate) enum TypeMessage {
     TypeMismatch(Value, Value, Value),
     AnnotMismatch(Value, Value),
     Untyped,
-    FieldCollision(Label),
     InvalidListElement(usize, Value, Value),
     InvalidListType(Value),
     InvalidOptionalType(Value),
diff --git a/dhall/src/phase/normalize.rs b/dhall/src/phase/normalize.rs
index 821c5fd..76349e4 100644
--- a/dhall/src/phase/normalize.rs
+++ b/dhall/src/phase/normalize.rs
@@ -425,60 +425,6 @@ where
     kvs
 }
 
-/// Performs an outer join of two HashMaps.
-///
-/// # Arguments
-///
-/// * `ft` - Will convert the values of the first map
-///          into the target value.
-///
-/// * `fu` - Will convert the values of the second map
-///          into the target value.
-///
-/// * `fktu` - Will convert the key and values from both maps
-///           into the target type.
-///
-/// # Description
-///
-/// If the key is present in both maps then the final value for
-/// that key is computed via the `fktu` function. Otherwise, the
-/// final value will be calculated by either the `ft` or `fu` value
-/// depending on which map the key is present in.
-///
-/// The final map will contain all keys from the two input maps with
-/// also values computed as per above.
-pub(crate) fn outer_join<K, T, U, V>(
-    mut ft: impl FnMut(&T) -> V,
-    mut fu: impl FnMut(&U) -> V,
-    mut fktu: impl FnMut(&K, &T, &U) -> V,
-    map1: &HashMap<K, T>,
-    map2: &HashMap<K, U>,
-) -> HashMap<K, V>
-where
-    K: std::hash::Hash + Eq + Clone,
-{
-    let mut kvs = HashMap::new();
-
-    for (k1, t) in map1 {
-        let v = if let Some(u) = map2.get(k1) {
-            // The key exists in both maps
-            // so use all values for computation
-            fktu(k1, t, u)
-        } else {
-            // Key only exists in map1
-            ft(t)
-        };
-        kvs.insert(k1.clone(), v);
-    }
-
-    for (k1, u) in map2 {
-        // Insert if key was missing in map1
-        kvs.entry(k1.clone()).or_insert(fu(u));
-    }
-
-    kvs
-}
-
 pub(crate) fn merge_maps<K, V>(
     map1: &HashMap<K, V>,
     map2: &HashMap<K, V>,
diff --git a/dhall/src/phase/typecheck.rs b/dhall/src/phase/typecheck.rs
index 40017ee..77ef689 100644
--- a/dhall/src/phase/typecheck.rs
+++ b/dhall/src/phase/typecheck.rs
@@ -582,49 +582,6 @@ fn type_last_layer(
             )?)
         }
         BinOp(RecursiveRecordMerge, l, r) => {
-            // A recursive function to dig down into
-            // records of records when merging.
-            fn combine_record_types(
-                ctx: &TypecheckContext,
-                kts_l: &HashMap<Label, Value>,
-                kts_r: &HashMap<Label, Value>,
-            ) -> Result<Value, TypeError> {
-                use crate::phase::normalize::outer_join;
-
-                // If the Label exists for both records and the values
-                // are records themselves, then we hit the recursive case.
-                // Otherwise we have a field collision.
-                let combine = |k: &Label,
-                               inner_l: &Value,
-                               inner_r: &Value|
-                 -> Result<Value, TypeError> {
-                    match (&*inner_l.as_whnf(), &*inner_r.as_whnf()) {
-                        (
-                            ValueF::RecordType(inner_l_kvs),
-                            ValueF::RecordType(inner_r_kvs),
-                        ) => {
-                            combine_record_types(ctx, inner_l_kvs, inner_r_kvs)
-                        }
-                        (_, _) => {
-                            Err(TypeError::new(ctx, FieldCollision(k.clone())))
-                        }
-                    }
-                };
-
-                let kts: HashMap<Label, Result<Value, TypeError>> = outer_join(
-                    |l| Ok(l.clone()),
-                    |r| Ok(r.clone()),
-                    combine,
-                    kts_l,
-                    kts_r,
-                );
-
-                tck_record_type(
-                    ctx,
-                    kts.into_iter().map(|(x, v)| v.map(|r| (x.clone(), r))),
-                )
-            };
-
             let l_type = l.get_type()?;
             let l_kind = l_type.get_type()?;
             let r_type = r.get_type()?;
@@ -637,60 +594,17 @@ fn type_last_layer(
                 return mkerr(RecordMismatch(l.clone(), r.clone()));
             }
 
-            // Extract the LHS record type
-            let l_type_borrow = l_type.as_whnf();
-            let kts_x = match &*l_type_borrow {
-                ValueF::RecordType(kts) => kts,
-                _ => return mkerr(MustCombineRecord(l.clone())),
-            };
-
-            // Extract the RHS record type
-            let r_type_borrow = r_type.as_whnf();
-            let kts_y = match &*r_type_borrow {
-                ValueF::RecordType(kts) => kts,
-                _ => return mkerr(MustCombineRecord(r.clone())),
-            };
-
-            let r = combine_record_types(ctx, kts_x, kts_y)?;
-            RetTypeOnly(r)
+            RetTypeOnly(type_last_layer(
+                ctx,
+                ExprF::BinOp(
+                    RecursiveRecordTypeMerge,
+                    l_type.into_owned(),
+                    r_type.into_owned(),
+                ),
+            )?)
         }
         BinOp(RecursiveRecordTypeMerge, l, r) => {
-            // A recursive function to dig down into
-            // records of records when merging.
-            fn combine_record_types(
-                ctx: &TypecheckContext,
-                kts_l: &HashMap<Label, Value>,
-                kts_r: &HashMap<Label, Value>,
-            ) -> Result<Value, TypeError> {
-                use crate::phase::normalize::intersection_with_key;
-
-                // If the Label exists for both records and the values
-                // are records themselves, then we hit the recursive case.
-                // Otherwise we have a field collision.
-                let combine = |k: &Label,
-                               kts_l_inner: &Value,
-                               kts_r_inner: &Value|
-                 -> Result<Value, TypeError> {
-                    match (&*kts_l_inner.as_whnf(), &*kts_r_inner.as_whnf()) {
-                        (
-                            ValueF::RecordType(kvs_l_inner),
-                            ValueF::RecordType(kvs_r_inner),
-                        ) => {
-                            combine_record_types(ctx, kvs_l_inner, kvs_r_inner)
-                        }
-                        (_, _) => {
-                            Err(TypeError::new(ctx, FieldCollision(k.clone())))
-                        }
-                    }
-                };
-
-                let kts = intersection_with_key(combine, kts_l, kts_r);
-
-                tck_record_type(
-                    ctx,
-                    kts.into_iter().map(|(x, v)| v.map(|r| (x.clone(), r))),
-                )
-            };
+            use crate::phase::normalize::intersection_with_key;
 
             // Extract the Const of the LHS
             let k_l = match l.get_type()?.as_const() {
@@ -739,7 +653,22 @@ fn type_last_layer(
             };
 
             // Ensure that the records combine without a type error
-            combine_record_types(ctx, kts_x, kts_y)?;
+            let kts = intersection_with_key(
+                // If the Label exists for both records, then we hit the recursive case.
+                |_: &Label, l: &Value, r: &Value| {
+                    type_last_layer(
+                        ctx,
+                        ExprF::BinOp(
+                            RecursiveRecordTypeMerge,
+                            l.clone(),
+                            r.clone(),
+                        ),
+                    )
+                },
+                kts_x,
+                kts_y,
+            );
+            tck_record_type(ctx, kts.into_iter().map(|(x, v)| Ok((x, v?))))?;
 
             RetTypeOnly(Value::from_const(k))
         }