Add typechecking for RecursiveRecordTypeMerge.

The implementation brings with it intersection_with_key over HashMaps to
help with the type checking of records of records.

The implementation first checks that the Const values line up with the
LHS and RHS. Then checks that combining the records does not result in a
FieldCollision. It will finally return the shared Const type of the
arguments.

1 files changed, 32 insertions, 0 deletions

diff --git a/dhall/src/phase/normalize.rs b/dhall/src/phase/normalize.rs
index be2ba51..653f415 100644
--- a/dhall/src/phase/normalize.rs
+++ b/dhall/src/phase/normalize.rs
@@ -372,6 +372,38 @@ enum Ret<'a> {
     Expr(ExprF<Thunk, X>),
 }
 
+/// Performs an intersection of two HashMaps.
+///
+/// # Arguments
+///
+/// * `f` - Will compute the final value from the intersecting
+///         key and the values from both maps.
+///
+/// # Description
+///
+/// If the key is present in both maps then the final value for
+/// that key is computed via the `f` function.
+///
+/// The final map will contain the shared keys from the
+/// two input maps with the final computed value from `f`.
+pub(crate) fn intersection_with_key<K, T, U, V>(
+    mut f: 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 (k, t) in map1 {
+        // Only insert in the final map if the key exists in both
+        if let Some(u) = map2.get(k) { kvs.insert(k.clone(), f(k, t, u)); }
+    }
+
+    kvs
+}
+
 fn merge_maps<K, V>(
     map1: &HashMap<K, V>,
     map2: &HashMap<K, V>,