From 2020d41874f7681ba948a40d8e8f8993d651a81c Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Thu, 9 May 2019 12:48:41 +0200 Subject: Detect duplicate record fields in typecheck --- dhall/src/core/value.rs | 12 ++++----- dhall/src/error/mod.rs | 2 ++ dhall/src/phase/binary.rs | 61 ++++++++++++++++++++---------------------- dhall/src/phase/normalize.rs | 18 ++++++------- dhall/src/phase/typecheck.rs | 63 +++++++++++++++++++++++--------------------- 5 files changed, 79 insertions(+), 77 deletions(-) (limited to 'dhall') diff --git a/dhall/src/core/value.rs b/dhall/src/core/value.rs index 72949be..8fa24c7 100644 --- a/dhall/src/core/value.rs +++ b/dhall/src/core/value.rs @@ -1,4 +1,4 @@ -use std::collections::BTreeMap; +use std::collections::HashMap; use dhall_proc_macros as dhall; use dhall_syntax::{ @@ -49,11 +49,11 @@ pub(crate) enum Value { NEOptionalLit(Thunk), EmptyListLit(TypeThunk), NEListLit(Vec), - RecordLit(BTreeMap), - RecordType(BTreeMap), - UnionType(BTreeMap>), - UnionConstructor(Label, BTreeMap>), - UnionLit(Label, Thunk, BTreeMap>), + RecordLit(HashMap), + RecordType(HashMap), + UnionType(HashMap>), + UnionConstructor(Label, HashMap>), + UnionLit(Label, Thunk, HashMap>), // Invariant: this must not contain interpolations that are themselves TextLits, and // contiguous text values must be merged. TextLit(Vec>), diff --git a/dhall/src/error/mod.rs b/dhall/src/error/mod.rs index 89568a3..ff748bc 100644 --- a/dhall/src/error/mod.rs +++ b/dhall/src/error/mod.rs @@ -72,6 +72,8 @@ pub(crate) enum TypeMessage { ProjectionMustBeRecord, ProjectionMissingEntry, Sort, + RecordTypeDuplicateField, + UnionTypeDuplicateField, Unimplemented, } diff --git a/dhall/src/phase/binary.rs b/dhall/src/phase/binary.rs index 249d7c7..5110241 100644 --- a/dhall/src/phase/binary.rs +++ b/dhall/src/phase/binary.rs @@ -131,11 +131,11 @@ fn cbor_value_to_dhall(data: &cbor::Value) -> Result { Merge(x, y, Some(z)) } [U64(7), Object(map)] => { - let map = cbor_map_to_dhall_map(map)?; + let map = cbor_map_to_dhall_map(map.iter())?; RecordType(map) } [U64(8), Object(map)] => { - let map = cbor_map_to_dhall_map(map)?; + let map = cbor_map_to_dhall_map(map.iter())?; RecordLit(map) } [U64(9), x, String(l)] => { @@ -144,11 +144,11 @@ fn cbor_value_to_dhall(data: &cbor::Value) -> Result { Field(x, l) } [U64(11), Object(map)] => { - let map = cbor_map_to_dhall_opt_map(map)?; + let map = cbor_map_to_dhall_opt_map(map.iter())?; UnionType(map) } [U64(12), String(l), x, Object(map)] => { - let map = cbor_map_to_dhall_opt_map(map)?; + let map = cbor_map_to_dhall_opt_map(map.iter())?; let x = cbor_value_to_dhall(&x)?; let l = Label::from(l.as_str()); UnionLit(l, x, map) @@ -331,34 +331,31 @@ fn cbor_value_to_dhall(data: &cbor::Value) -> Result { })) } -fn cbor_map_to_dhall_map( - map: &std::collections::BTreeMap, -) -> Result, DecodeError> { - map.iter() - .map(|(k, v)| -> Result<(_, _), _> { - let k = k.as_string().ok_or_else(|| { - DecodeError::WrongFormatError("map/key".to_owned()) - })?; - let v = cbor_value_to_dhall(v)?; - Ok((Label::from(k.as_ref()), v)) - }) - .collect::>() +fn cbor_map_to_dhall_map<'a>( + map: impl Iterator, +) -> Result, DecodeError> { + map.map(|(k, v)| -> Result<(_, _), _> { + let k = k.as_string().ok_or_else(|| { + DecodeError::WrongFormatError("map/key".to_owned()) + })?; + let v = cbor_value_to_dhall(v)?; + Ok((Label::from(k.as_ref()), v)) + }) + .collect::>() } -fn cbor_map_to_dhall_opt_map( - map: &std::collections::BTreeMap, -) -> Result>, DecodeError> -{ - map.iter() - .map(|(k, v)| -> Result<(_, _), _> { - let k = k.as_string().ok_or_else(|| { - DecodeError::WrongFormatError("map/key".to_owned()) - })?; - let v = match v { - cbor::Value::Null => None, - _ => Some(cbor_value_to_dhall(v)?), - }; - Ok((Label::from(k.as_ref()), v)) - }) - .collect::>() +fn cbor_map_to_dhall_opt_map<'a>( + map: impl Iterator, +) -> Result)>, DecodeError> { + map.map(|(k, v)| -> Result<(_, _), _> { + let k = k.as_string().ok_or_else(|| { + DecodeError::WrongFormatError("map/key".to_owned()) + })?; + let v = match v { + cbor::Value::Null => None, + _ => Some(cbor_value_to_dhall(v)?), + }; + Ok((Label::from(k.as_ref()), v)) + }) + .collect::>() } diff --git a/dhall/src/phase/normalize.rs b/dhall/src/phase/normalize.rs index e4d4d57..52c1666 100644 --- a/dhall/src/phase/normalize.rs +++ b/dhall/src/phase/normalize.rs @@ -1,4 +1,4 @@ -use std::collections::BTreeMap; +use std::collections::HashMap; use dhall_syntax::{ BinOp, Builtin, ExprF, InterpolatedText, InterpolatedTextContents, Label, @@ -118,7 +118,7 @@ pub(crate) fn apply_builtin(b: Builtin, args: Vec) -> Value { }, (ListIndexed, [_, l, r..]) => match &*l.as_value() { EmptyListLit(t) => { - let mut kts = BTreeMap::new(); + let mut kts = HashMap::new(); kts.insert( "index".into(), TypeThunk::from_value(Value::from_builtin(Natural)), @@ -132,7 +132,7 @@ pub(crate) fn apply_builtin(b: Builtin, args: Vec) -> Value { .enumerate() .map(|(i, e)| { let i = NaturalLit(i); - let mut kvs = BTreeMap::new(); + let mut kvs = HashMap::new(); kvs.insert("index".into(), Thunk::from_value(i)); kvs.insert("value".into(), e.clone()); Thunk::from_value(RecordLit(kvs)) @@ -376,15 +376,15 @@ enum Ret<'a> { } fn merge_maps( - map1: &BTreeMap, - map2: &BTreeMap, + map1: &HashMap, + map2: &HashMap, mut f: impl FnMut(&V, &V) -> V, -) -> BTreeMap +) -> HashMap where - K: Ord + Clone, + K: std::hash::Hash + Eq + Clone, V: Clone, { - let mut kvs = BTreeMap::new(); + let mut kvs = HashMap::new(); for (x, v2) in map2 { let newv = if let Some(v1) = map1.get(x) { f(v1, v2) @@ -619,7 +619,7 @@ pub(crate) fn normalize_one_layer(expr: ExprF) -> Value { }, ExprF::Projection(_, ls) if ls.is_empty() => { - RetValue(RecordLit(std::collections::BTreeMap::new())) + RetValue(RecordLit(HashMap::new())) } ExprF::Projection(ref v, ref ls) => { let v_borrow = v.as_value(); diff --git a/dhall/src/phase/typecheck.rs b/dhall/src/phase/typecheck.rs index 265ce08..2c625fb 100644 --- a/dhall/src/phase/typecheck.rs +++ b/dhall/src/phase/typecheck.rs @@ -1,6 +1,6 @@ #![allow(non_snake_case)] use std::borrow::Borrow; -use std::collections::BTreeMap; +use std::collections::HashMap; use dhall_proc_macros as dhall; use dhall_syntax::{ @@ -36,8 +36,8 @@ macro_rules! ensure_simple_type { #[derive(Debug, Clone, PartialEq, Eq)] pub(crate) enum TypeIntermediate { Pi(Label, Type, Type), - RecordType(BTreeMap), - UnionType(BTreeMap>), + RecordType(Vec<(Label, Type)>), + UnionType(Vec<(Label, Option)>), ListType(Type), OptionalType(Type), } @@ -102,6 +102,7 @@ impl TypeIntermediate { ) } TypeIntermediate::RecordType(kts) => { + let mut new_kts = HashMap::new(); // Check that all types are the same const let mut k = None; for (x, t) in kts { @@ -115,23 +116,27 @@ impl TypeIntermediate { )) } } + use std::collections::hash_map::Entry; + let entry = new_kts.entry(x.clone()); + match &entry { + Entry::Occupied(_) => { + return Err(mkerr(ctx, RecordTypeDuplicateField)) + } + Entry::Vacant(_) => { + entry.or_insert(TypeThunk::from_type(t.clone())) + } + }; } // An empty record type has type Type let k = k.unwrap_or(dhall_syntax::Const::Type); Typed::from_thunk_and_type( - Value::RecordType( - kts.iter() - .map(|(k, t)| { - (k.clone(), TypeThunk::from_type(t.clone())) - }) - .collect(), - ) - .into_thunk(), + Value::RecordType(new_kts).into_thunk(), Type::from_const(k), ) } TypeIntermediate::UnionType(kts) => { + let mut new_kts = HashMap::new(); // Check that all types are the same const let mut k = None; for (x, t) in kts { @@ -147,6 +152,16 @@ impl TypeIntermediate { } } } + use std::collections::hash_map::Entry; + let entry = new_kts.entry(x.clone()); + match &entry { + Entry::Occupied(_) => { + return Err(mkerr(ctx, UnionTypeDuplicateField)) + } + Entry::Vacant(_) => entry.or_insert( + t.as_ref().map(|t| TypeThunk::from_type(t.clone())), + ), + }; } // An empty union type has type Type; @@ -154,19 +169,7 @@ impl TypeIntermediate { let k = k.unwrap_or(dhall_syntax::Const::Type); Typed::from_thunk_and_type( - Value::UnionType( - kts.iter() - .map(|(k, t)| { - ( - k.clone(), - t.as_ref().map(|t| { - TypeThunk::from_type(t.clone()) - }), - ) - }) - .collect(), - ) - .into_thunk(), + Value::UnionType(new_kts).into_thunk(), Type::from_const(k), ) } @@ -546,14 +549,14 @@ fn type_last_layer( Ok(RetTypeIntermediate(TypeIntermediate::OptionalType(t))) } RecordType(kts) => { - let kts: BTreeMap<_, _> = kts + let kts = kts .iter() .map(|(x, t)| Ok((x.clone(), t.to_type()))) .collect::>()?; Ok(RetTyped(TypeIntermediate::RecordType(kts).typecheck(ctx)?)) } UnionType(kts) => { - let kts: BTreeMap<_, _> = kts + let kts = kts .iter() .map(|(x, t)| { Ok(( @@ -575,7 +578,7 @@ fn type_last_layer( Ok(RetTypeIntermediate(TypeIntermediate::RecordType(kts))) } UnionLit(x, v, kvs) => { - let mut kts: std::collections::BTreeMap<_, _> = kvs + let mut kts: Vec<_> = kvs .iter() .map(|(x, v)| { let t = match v { @@ -586,7 +589,7 @@ fn type_last_layer( }) .collect::>()?; let t = v.get_type()?.into_owned(); - kts.insert(x.clone(), Some(t)); + kts.push((x.clone(), Some(t))); Ok(RetTypeIntermediate(TypeIntermediate::UnionType(kts))) } Field(r, x) => { @@ -782,7 +785,7 @@ fn type_last_layer( _ => return Err(mkerr(ProjectionMustBeRecord)), }; - let mut new_kts = BTreeMap::new(); + let mut new_kts = HashMap::new(); for l in labels { match kts.get(l) { None => return Err(mkerr(ProjectionMissingEntry)), @@ -1005,7 +1008,7 @@ mod spec_tests { tc_success!(tc_success_simple_unionsOfTypes, "simple/unionsOfTypes"); tc_failure!(tc_failure_combineMixedRecords, "combineMixedRecords"); - // tc_failure!(tc_failure_duplicateFields, "duplicateFields"); + tc_failure!(tc_failure_duplicateFields, "duplicateFields"); tc_failure!(tc_failure_hurkensParadox, "hurkensParadox"); // tc_failure!(tc_failure_importBoundary, "importBoundary"); tc_failure!(tc_failure_mixedUnions, "mixedUnions"); -- cgit v1.2.3