Detect duplicate record fields in typecheck

3 files changed, 71 insertions, 71 deletions

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<ParsedExpr, DecodeError> {
                 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<ParsedExpr, DecodeError> {
                 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<ParsedExpr, DecodeError> {
     }))
 }
 
-fn cbor_map_to_dhall_map(
-    map: &std::collections::BTreeMap<cbor::ObjectKey, cbor::Value>,
-) -> Result<std::collections::BTreeMap<Label, ParsedExpr>, 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::<Result<_, _>>()
+fn cbor_map_to_dhall_map<'a>(
+    map: impl Iterator<Item = (&'a cbor::ObjectKey, &'a cbor::Value)>,
+) -> Result<Vec<(Label, ParsedExpr)>, 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::<Result<_, _>>()
 }
 
-fn cbor_map_to_dhall_opt_map(
-    map: &std::collections::BTreeMap<cbor::ObjectKey, cbor::Value>,
-) -> Result<std::collections::BTreeMap<Label, Option<ParsedExpr>>, 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::<Result<_, _>>()
+fn cbor_map_to_dhall_opt_map<'a>(
+    map: impl Iterator<Item = (&'a cbor::ObjectKey, &'a cbor::Value)>,
+) -> Result<Vec<(Label, Option<ParsedExpr>)>, 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::<Result<_, _>>()
 }
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<Thunk>) -> 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<Thunk>) -> 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<K, V>(
-    map1: &BTreeMap<K, V>,
-    map2: &BTreeMap<K, V>,
+    map1: &HashMap<K, V>,
+    map2: &HashMap<K, V>,
     mut f: impl FnMut(&V, &V) -> V,
-) -> BTreeMap<K, V>
+) -> HashMap<K, V>
 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<Thunk, Label, X>) -> 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<Label, Type>),
-    UnionType(BTreeMap<Label, Option<Type>>),
+    RecordType(Vec<(Label, Type)>),
+    UnionType(Vec<(Label, Option<Type>)>),
     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::<Result<_, _>>()?;
             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::<Result<_, _>>()?;
             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");