From f6d30f42bd3a6762b1f53b34a249c877260951bb Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Tue, 20 Aug 2019 11:52:46 +0200 Subject: Reuse work to avoid complicated recursion in record merging --- dhall/src/error/mod.rs | 1 - dhall/src/phase/normalize.rs | 54 ------------------- dhall/src/phase/typecheck.rs | 121 +++++++++---------------------------------- 3 files changed, 25 insertions(+), 151 deletions(-) (limited to 'dhall/src') 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( - mut ft: impl FnMut(&T) -> V, - mut fu: impl FnMut(&U) -> V, - mut fktu: impl FnMut(&K, &T, &U) -> V, - map1: &HashMap, - map2: &HashMap, -) -> HashMap -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( map1: &HashMap, map2: &HashMap, 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, - kts_r: &HashMap, - ) -> Result { - 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 { - 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> = 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, - kts_r: &HashMap, - ) -> Result { - 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 { - 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)) } -- cgit v1.2.3