From a53fc6e6767bba80bf1697d732d88c4a1e0e9e42 Mon Sep 17 00:00:00 2001
From: FintanH
Date: Wed, 31 Jul 2019 12:05:48 +0100
Subject: Add the typechecking of RecursiveRecordMerge.

This introduces an external function for HashMaps to perform an outer
join so that you can do a unionWith but with more power by having a new
tagert type.

Using outer_join and recursively looking through records of records we
have an implementation for combining records.
---
 dhall/src/phase/normalize.rs | 53 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 53 insertions(+)

(limited to 'dhall/src/phase/normalize.rs')

diff --git a/dhall/src/phase/normalize.rs b/dhall/src/phase/normalize.rs
index be2ba51..e3c5d68 100644
--- a/dhall/src/phase/normalize.rs
+++ b/dhall/src/phase/normalize.rs
@@ -372,6 +372,59 @@ enum Ret<'a> {
     Expr(ExprF<Thunk, X>),
 }
 
+/// 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.
+///
+/// * `ftu` - 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 `ftu` 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 ftu: 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 kus = 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
+            ftu(k1, t, u)
+        } else {
+            // Key only exists in map1
+            ft(t)
+        };
+        kus.insert(k1.clone(), v);
+    }
+
+    for (k1, u) in map2 {
+        // Insert if key was missing in map1
+        kus.entry(k1.clone()).or_insert(fu(u));
+    }
+
+    kus
+}
+
 fn merge_maps<K, V>(
     map1: &HashMap<K, V>,
     map2: &HashMap<K, V>,
-- 
cgit v1.2.3