summaryrefslogtreecommitdiff
path: root/dhall/src/phase
diff options
context:
space:
mode:
authorNadrieril2019-08-20 11:52:46 +0200
committerNadrieril2019-08-20 11:52:46 +0200
commitf6d30f42bd3a6762b1f53b34a249c877260951bb (patch)
tree25f6f1cec4afaf514813c6f8a02f9720a6114c52 /dhall/src/phase
parent85cbed46aa6a5c76902576dcf2beb323bedb25b1 (diff)
Reuse work to avoid complicated recursion in record merging
Diffstat (limited to 'dhall/src/phase')
-rw-r--r--dhall/src/phase/normalize.rs54
-rw-r--r--dhall/src/phase/typecheck.rs121
2 files changed, 25 insertions, 150 deletions
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))
}