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 +++++++++++++++++++++------------------- dhall_proc_macros/src/quote.rs | 15 +++++----- dhall_syntax/src/core/expr.rs | 9 +++--- dhall_syntax/src/core/visitor.rs | 22 +++++++------- dhall_syntax/src/parser.rs | 37 ++++++++++++++--------- 9 files changed, 124 insertions(+), 115 deletions(-) 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"); diff --git a/dhall_proc_macros/src/quote.rs b/dhall_proc_macros/src/quote.rs index 77ed5de..241ef66 100644 --- a/dhall_proc_macros/src/quote.rs +++ b/dhall_proc_macros/src/quote.rs @@ -3,7 +3,6 @@ use dhall_syntax::context::Context; use dhall_syntax::*; use proc_macro2::TokenStream; use quote::quote; -use std::collections::BTreeMap; pub fn expr(input: proc_macro::TokenStream) -> proc_macro::TokenStream { let input_str = input.to_string(); @@ -201,25 +200,27 @@ where quote! { vec![ #(#e),* ] } } -fn quote_map(m: BTreeMap) -> TokenStream +fn quote_map(m: impl IntoIterator) -> TokenStream where TS: quote::ToTokens + std::fmt::Debug, { let entries = m.into_iter().map(|(k, v)| { let k = quote_label(&k); - quote!(m.insert(#k, #v);) + quote!(m.push((#k, #v));) }); quote! { { - use std::collections::BTreeMap; - let mut m = BTreeMap::new(); + use std::vec::Vec; + let mut m = Vec::new(); #( #entries )* m } } } -fn quote_opt_map(m: BTreeMap>) -> TokenStream +fn quote_opt_map( + m: impl IntoIterator)>, +) -> TokenStream where TS: quote::ToTokens + std::fmt::Debug, { - quote_map(m.into_iter().map(|(k, v)| (k, quote_opt(v))).collect()) + quote_map(m.into_iter().map(|(k, v)| (k, quote_opt(v)))) } diff --git a/dhall_syntax/src/core/expr.rs b/dhall_syntax/src/core/expr.rs index 3bc7504..4bfd224 100644 --- a/dhall_syntax/src/core/expr.rs +++ b/dhall_syntax/src/core/expr.rs @@ -1,5 +1,4 @@ #![allow(non_snake_case)] -use std::collections::BTreeMap; use std::rc::Rc; use crate::visitor; @@ -202,13 +201,13 @@ pub enum ExprF { /// `Some e` SomeLit(SubExpr), /// `{ k1 : t1, k2 : t1 }` - RecordType(BTreeMap), + RecordType(Vec<(Label, SubExpr)>), /// `{ k1 = v1, k2 = v2 }` - RecordLit(BTreeMap), + RecordLit(Vec<(Label, SubExpr)>), /// `< k1 : t1, k2 >` - UnionType(BTreeMap>), + UnionType(Vec<(Label, Option)>), /// `< k1 = t1, k2 : t2, k3 >` - UnionLit(Label, SubExpr, BTreeMap>), + UnionLit(Label, SubExpr, Vec<(Label, Option)>), /// `merge x y : t` Merge(SubExpr, SubExpr, Option), /// `e.x` diff --git a/dhall_syntax/src/core/visitor.rs b/dhall_syntax/src/core/visitor.rs index 20bfc72..1377849 100644 --- a/dhall_syntax/src/core/visitor.rs +++ b/dhall_syntax/src/core/visitor.rs @@ -1,5 +1,3 @@ -use std::collections::BTreeMap; - use crate::*; /// A way too generic Visitor trait. @@ -68,10 +66,10 @@ where None => None, }) } - fn btmap<'a, V, Ret, SE, L, E>( - x: &'a BTreeMap, + fn vecmap<'a, V, Ret, SE, L, E>( + x: &'a Vec<(L, SE)>, mut v: V, - ) -> Result, V::Error> + ) -> Result, V::Error> where L: Ord, V::L2: Ord, @@ -81,10 +79,10 @@ where .map(|(k, x)| Ok((v.visit_label(k)?, v.visit_subexpr(x)?))) .collect() } - fn btoptmap<'a, V, Ret, SE, L, E>( - x: &'a BTreeMap>, + fn vecoptmap<'a, V, Ret, SE, L, E>( + x: &'a Vec<(L, Option)>, mut v: V, - ) -> Result>, V::Error> + ) -> Result)>, V::Error> where L: Ord, V::L2: Ord, @@ -147,13 +145,13 @@ where v.visit_subexpr(t)?, ), SomeLit(e) => SomeLit(v.visit_subexpr(e)?), - RecordType(kts) => RecordType(btmap(kts, v)?), - RecordLit(kvs) => RecordLit(btmap(kvs, v)?), - UnionType(kts) => UnionType(btoptmap(kts, v)?), + RecordType(kts) => RecordType(vecmap(kts, v)?), + RecordLit(kvs) => RecordLit(vecmap(kvs, v)?), + UnionType(kts) => UnionType(vecoptmap(kts, v)?), UnionLit(k, x, kts) => UnionLit( v.visit_label(k)?, v.visit_subexpr(x)?, - btoptmap(kts, v)?, + vecoptmap(kts, v)?, ), Merge(x, y, t) => Merge( v.visit_subexpr(x)?, diff --git a/dhall_syntax/src/parser.rs b/dhall_syntax/src/parser.rs index 607d19c..276510e 100644 --- a/dhall_syntax/src/parser.rs +++ b/dhall_syntax/src/parser.rs @@ -2,7 +2,6 @@ use itertools::Itertools; use pest::iterators::Pair; use pest::Parser; use std::borrow::Cow; -use std::collections::BTreeMap; use std::path::PathBuf; use std::rc::Rc; @@ -887,29 +886,33 @@ make_parser! { )); rule!(empty_record_literal as expression; span; - captured_str!(_) => spanned(span, RecordLit(BTreeMap::new())) + captured_str!(_) => spanned(span, RecordLit(Vec::new())) ); rule!(empty_record_type as expression; span; - captured_str!(_) => spanned(span, RecordType(BTreeMap::new())) + captured_str!(_) => spanned(span, RecordType(Vec::new())) ); rule!(non_empty_record_type_or_literal as expression; span; children!( [label(first_label), non_empty_record_type(rest)] => { let (first_expr, mut map) = rest; - map.insert(first_label, first_expr); + map.push((first_label, first_expr)); + // Sort until we stop using binary decode for parser tests + map.sort_by(|(l1, _), (l2, _)| l1.cmp(l2)); spanned(span, RecordType(map)) }, [label(first_label), non_empty_record_literal(rest)] => { let (first_expr, mut map) = rest; - map.insert(first_label, first_expr); + map.push((first_label, first_expr)); + // Sort until we stop using binary decode for parser tests + map.sort_by(|(l1, _), (l2, _)| l1.cmp(l2)); spanned(span, RecordLit(map)) }, )); rule!(non_empty_record_type - <(ParsedSubExpr, BTreeMap)>; children!( + <(ParsedSubExpr, Vec<(Label, ParsedSubExpr)>)>; children!( [expression(expr), record_type_entry(entries)..] => { (expr, entries.collect()) } @@ -920,7 +923,7 @@ make_parser! { )); rule!(non_empty_record_literal - <(ParsedSubExpr, BTreeMap)>; children!( + <(ParsedSubExpr, Vec<(Label, ParsedSubExpr)>)>; children!( [expression(expr), record_literal_entry(entries)..] => { (expr, entries.collect()) } @@ -932,12 +935,18 @@ make_parser! { rule!(union_type_or_literal as expression; span; children!( [empty_union_type(_)] => { - spanned(span, UnionType(BTreeMap::new())) + spanned(span, UnionType(Vec::new())) }, [non_empty_union_type_or_literal((Some((l, e)), entries))] => { + let mut entries = entries; + // Sort until we stop using binary decode for parser tests + entries.sort_by(|(l1, _), (l2, _)| l1.cmp(l2)); spanned(span, UnionLit(l, e, entries)) }, [non_empty_union_type_or_literal((None, entries))] => { + let mut entries = entries; + // Sort until we stop using binary decode for parser tests + entries.sort_by(|(l1, _), (l2, _)| l1.cmp(l2)); spanned(span, UnionType(entries)) }, )); @@ -946,20 +955,20 @@ make_parser! { rule!(non_empty_union_type_or_literal <(Option<(Label, ParsedSubExpr)>, - BTreeMap>)>; + Vec<(Label, Option)>)>; children!( [label(l), union_literal_variant_value((e, entries))] => { (Some((l, e)), entries) }, [label(l), union_type_or_literal_variant_type((e, rest))] => { let (x, mut entries) = rest; - entries.insert(l, e); + entries.push((l, e)); (x, entries) }, )); rule!(union_literal_variant_value - <(ParsedSubExpr, BTreeMap>)>; + <(ParsedSubExpr, Vec<(Label, Option)>)>; children!( [expression(e), union_type_entry(entries)..] => { (e, entries.collect()) @@ -975,19 +984,19 @@ make_parser! { rule!(union_type_or_literal_variant_type <(Option, (Option<(Label, ParsedSubExpr)>, - BTreeMap>))>; + Vec<(Label, Option)>))>; children!( [expression(e), non_empty_union_type_or_literal(rest)] => { (Some(e), rest) }, [expression(e)] => { - (Some(e), (None, BTreeMap::new())) + (Some(e), (None, Vec::new())) }, [non_empty_union_type_or_literal(rest)] => { (None, rest) }, [] => { - (None, (None, BTreeMap::new())) + (None, (None, Vec::new())) }, )); -- cgit v1.2.3