From 092b7208ffd22f8facc7af387ac307e59208d52c Mon Sep 17 00:00:00 2001
From: Nadrieril
Date: Tue, 7 Apr 2020 11:19:36 +0100
Subject: Move duplicate field checking to parser

---
 dhall/src/builtins.rs                              |   8 +-
 dhall/src/operations.rs                            |  13 +-
 dhall/src/semantics/resolve/resolve.rs             |   4 +-
 dhall/src/semantics/tck/typecheck.rs               |  61 ++---
 dhall/src/syntax/ast/expr.rs                       |   5 +-
 dhall/src/syntax/ast/map.rs                        | 282 ---------------------
 dhall/src/syntax/ast/mod.rs                        |   1 -
 dhall/src/syntax/binary/encode.rs                  |  13 +-
 dhall/src/syntax/text/parser.rs                    |  64 ++++-
 dhall/tests/type-inference/failure/mixedUnions.txt |   6 +-
 .../tests/type-inference/failure/recordOfKind.txt  |   4 +-
 .../failure/unit/RecordMixedKinds3.txt             |   4 +-
 .../unit/RecordProjectionDuplicateFields.txt       |   8 +-
 .../failure/unit/RecordTypeDuplicateFields.txt     |   8 +-
 .../failure/unit/RecordTypeValueMember.txt         |   4 +-
 .../unit/RightBiasedRecordMergeMixedKinds2.txt     |   4 +-
 .../unit/RightBiasedRecordMergeMixedKinds3.txt     |   4 +-
 .../failure/unit/UnionTypeDuplicateVariants1.txt   |   8 +-
 .../failure/unit/UnionTypeDuplicateVariants2.txt   |   8 +-
 .../failure/unit/UnionTypeMixedKinds.txt           |   6 +-
 .../failure/unit/UnionTypeMixedKinds2.txt          |   6 +-
 .../failure/unit/UnionTypeMixedKinds3.txt          |   6 +-
 .../failure/unit/UnionTypeNotType.txt              |   6 +-
 tests_buffer                                       |   1 +
 24 files changed, 132 insertions(+), 402 deletions(-)
 delete mode 100644 dhall/src/syntax/ast/map.rs

diff --git a/dhall/src/builtins.rs b/dhall/src/builtins.rs
index bb8173c..67929a0 100644
--- a/dhall/src/builtins.rs
+++ b/dhall/src/builtins.rs
@@ -1,15 +1,15 @@
+use std::collections::{BTreeMap, HashMap};
+use std::convert::TryInto;
+
 use crate::operations::{BinOp, OpKind};
 use crate::semantics::{
     skip_resolve_expr, typecheck, Hir, HirKind, Nir, NirKind, NzEnv, VarEnv,
 };
-use crate::syntax::map::DupTreeMap;
 use crate::syntax::Const::Type;
 use crate::syntax::{
     Const, Expr, ExprKind, InterpolatedText, InterpolatedTextContents, Label,
     NaiveDouble, NumKind, Span, UnspannedExpr, V,
 };
-use std::collections::HashMap;
-use std::convert::TryInto;
 
 /// Built-ins
 #[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
@@ -147,7 +147,7 @@ macro_rules! make_type {
         )))
     };
     ({ $($label:ident : $ty:ident),* }) => {{
-        let mut kts = DupTreeMap::new();
+        let mut kts = BTreeMap::new();
         $(
             kts.insert(
                 Label::from(stringify!($label)),
diff --git a/dhall/src/operations.rs b/dhall/src/operations.rs
index 1ebf288..8b5fa10 100644
--- a/dhall/src/operations.rs
+++ b/dhall/src/operations.rs
@@ -1,7 +1,7 @@
 use itertools::Itertools;
 use std::borrow::Cow;
 use std::cmp::max;
-use std::collections::HashMap;
+use std::collections::{BTreeSet, HashMap};
 
 use crate::builtins::Builtin;
 use crate::error::{ErrorBuilder, TypeError};
@@ -9,7 +9,6 @@ use crate::semantics::{
     merge_maps, mk_span_err, mkerr, ret_kind, ret_op, ret_ref, Binder, Closure,
     Hir, HirKind, Nir, NirKind, Ret, TextLit, Tir, TyEnv, Type,
 };
-use crate::syntax::map::DupTreeSet;
 use crate::syntax::{trivial_result, Const, ExprKind, Label, NumKind, Span};
 
 // Definition order must match precedence order for
@@ -60,7 +59,7 @@ pub enum OpKind<SubExpr> {
     ///  `e.x`
     Field(SubExpr, Label),
     ///  `e.{ x, y, z }`
-    Projection(SubExpr, DupTreeSet<Label>),
+    Projection(SubExpr, BTreeSet<Label>),
     ///  `e.(t)`
     ProjectionByExpr(SubExpr, SubExpr),
     ///  `x::y`
@@ -565,13 +564,7 @@ pub fn typecheck_operation(
                 match kts.get(l) {
                     None => return span_err("ProjectionMissingEntry"),
                     Some(t) => {
-                        use std::collections::hash_map::Entry;
-                        match new_kts.entry(l.clone()) {
-                            Entry::Occupied(_) => {
-                                return span_err("ProjectionDuplicateField")
-                            }
-                            Entry::Vacant(e) => e.insert(t.clone()),
-                        }
+                        new_kts.insert(l.clone(), t.clone());
                     }
                 };
             }
diff --git a/dhall/src/semantics/resolve/resolve.rs b/dhall/src/semantics/resolve/resolve.rs
index cd5232a..e96f16b 100644
--- a/dhall/src/semantics/resolve/resolve.rs
+++ b/dhall/src/semantics/resolve/resolve.rs
@@ -1,5 +1,6 @@
 use itertools::Itertools;
 use std::borrow::Cow;
+use std::collections::BTreeMap;
 use std::env;
 use std::path::PathBuf;
 use url::Url;
@@ -10,7 +11,6 @@ use crate::error::{Error, ImportError};
 use crate::operations::{BinOp, OpKind};
 use crate::semantics::{mkerr, Hir, HirKind, ImportEnv, NameEnv, Type};
 use crate::syntax;
-use crate::syntax::map::DupTreeMap;
 use crate::syntax::{
     Expr, ExprKind, FilePath, FilePrefix, Hash, ImportMode, ImportTarget, Span,
     UnspannedExpr, URL,
@@ -199,7 +199,7 @@ fn mkexpr(kind: UnspannedExpr) -> Expr {
 
 fn make_aslocation_uniontype() -> Expr {
     let text_type = mkexpr(ExprKind::Builtin(Builtin::Text));
-    let mut union = DupTreeMap::default();
+    let mut union = BTreeMap::default();
     union.insert("Local".into(), Some(text_type.clone()));
     union.insert("Remote".into(), Some(text_type.clone()));
     union.insert("Environment".into(), Some(text_type));
diff --git a/dhall/src/semantics/tck/typecheck.rs b/dhall/src/semantics/tck/typecheck.rs
index c6300d9..45a3055 100644
--- a/dhall/src/semantics/tck/typecheck.rs
+++ b/dhall/src/semantics/tck/typecheck.rs
@@ -1,5 +1,4 @@
 use std::cmp::max;
-use std::collections::HashMap;
 
 use crate::builtins::{type_of_builtin, Builtin};
 use crate::error::{ErrorBuilder, TypeError, TypeMessage};
@@ -107,71 +106,55 @@ fn type_one_layer(
             Nir::from_builtin(Builtin::List).app(t).to_type(Const::Type)
         }
         ExprKind::RecordLit(kvs) => {
-            use std::collections::hash_map::Entry;
-            let mut kts = HashMap::new();
             // An empty record type has type Type
             let mut k = Const::Type;
-            for (x, v) in kvs {
-                // Check for duplicated entries
-                match kts.entry(x.clone()) {
-                    Entry::Occupied(_) => {
-                        return span_err("RecordTypeDuplicateField")
-                    }
-                    Entry::Vacant(e) => e.insert(v.ty().to_nir()),
-                };
-
+            for (_, v) in kvs {
                 // Check that the fields have a valid kind
                 match v.ty().ty().as_const() {
                     Some(c) => k = max(k, c),
-                    None => return span_err("InvalidFieldType"),
+                    None => return mk_span_err(v.span(), "InvalidFieldType"),
                 }
             }
 
+            let kts = kvs
+                .iter()
+                .map(|(x, v)| (x.clone(), v.ty().to_nir()))
+                .collect();
+
             Nir::from_kind(NirKind::RecordType(kts)).to_type(k)
         }
         ExprKind::RecordType(kts) => {
-            use std::collections::hash_map::Entry;
-            let mut seen_fields = HashMap::new();
             // An empty record type has type Type
             let mut k = Const::Type;
-
-            for (x, t) in kts {
-                // Check for duplicated entries
-                match seen_fields.entry(x.clone()) {
-                    Entry::Occupied(_) => {
-                        return span_err("RecordTypeDuplicateField")
-                    }
-                    Entry::Vacant(e) => e.insert(()),
-                };
-
+            for (_, t) in kts {
                 // Check the type is a Const and compute final type
                 match t.ty().as_const() {
                     Some(c) => k = max(k, c),
-                    None => return span_err("InvalidFieldType"),
+                    None => return mk_span_err(t.span(), "InvalidFieldType"),
                 }
             }
 
             Type::from_const(k)
         }
         ExprKind::UnionType(kts) => {
-            use std::collections::hash_map::Entry;
-            let mut seen_fields = HashMap::new();
             // Check that all types are the same const
             let mut k = None;
-            for (x, t) in kts {
+            for (_, t) in kts {
                 if let Some(t) = t {
-                    match (k, t.ty().as_const()) {
-                        (None, Some(k2)) => k = Some(k2),
-                        (Some(k1), Some(k2)) if k1 == k2 => {}
-                        _ => return span_err("InvalidFieldType"),
+                    let c = match t.ty().as_const() {
+                        Some(c) => c,
+                        None => {
+                            return mk_span_err(t.span(), "InvalidVariantType")
+                        }
+                    };
+                    match k {
+                        None => k = Some(c),
+                        Some(k) if k == c => {}
+                        _ => {
+                            return mk_span_err(t.span(), "InvalidVariantType")
+                        }
                     }
                 }
-                match seen_fields.entry(x) {
-                    Entry::Occupied(_) => {
-                        return span_err("UnionTypeDuplicateField")
-                    }
-                    Entry::Vacant(e) => e.insert(()),
-                };
             }
 
             // An empty union type has type Type;
diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index 8f55540..9d216a7 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -4,7 +4,6 @@ use crate::builtins::Builtin;
 use crate::error::Error;
 use crate::operations::OpKind;
 use crate::semantics::Universe;
-use crate::syntax::map::DupTreeMap;
 use crate::syntax::visitor;
 use crate::syntax::*;
 
@@ -81,11 +80,11 @@ pub enum ExprKind<SubExpr> {
     ///  `[x, y, z]`
     NEListLit(Vec<SubExpr>),
     ///  `{ k1 : t1, k2 : t1 }`
-    RecordType(DupTreeMap<Label, SubExpr>),
+    RecordType(BTreeMap<Label, SubExpr>),
     ///  `{ k1 = v1, k2 = v2 }`
     RecordLit(BTreeMap<Label, SubExpr>),
     ///  `< k1 : t1, k2 >`
-    UnionType(DupTreeMap<Label, Option<SubExpr>>),
+    UnionType(BTreeMap<Label, Option<SubExpr>>),
 
     ///  `x`, `x@n`
     Var(V),
diff --git a/dhall/src/syntax/ast/map.rs b/dhall/src/syntax/ast/map.rs
deleted file mode 100644
index 7a88204..0000000
--- a/dhall/src/syntax/ast/map.rs
+++ /dev/null
@@ -1,282 +0,0 @@
-/// A sorted map that allows multiple values for each key.
-pub use dup_tree_map::DupTreeMap;
-pub use dup_tree_set::DupTreeSet;
-
-mod known_size_iter {
-    pub struct KnownSizeIterator<I> {
-        pub iter: I,
-        pub size: usize,
-    }
-
-    impl<I: Iterator> Iterator for KnownSizeIterator<I> {
-        type Item = I::Item;
-
-        fn next(&mut self) -> Option<Self::Item> {
-            let next = self.iter.next();
-            if next.is_some() {
-                self.size -= 1;
-            }
-            next
-        }
-
-        fn size_hint(&self) -> (usize, Option<usize>) {
-            (self.size, Some(self.size))
-        }
-    }
-
-    // unsafe impl<I: Iterator> iter::TrustedLen for KnownSizeIterator<I> {}
-}
-
-mod tuple {
-    mod sealed {
-        pub trait Sealed {}
-    }
-    pub trait Tuple: sealed::Sealed {
-        type First;
-        type Second;
-    }
-    impl<A, B> sealed::Sealed for (A, B) {}
-    impl<A, B> Tuple for (A, B) {
-        type First = A;
-        type Second = B;
-    }
-}
-
-mod dup_tree_map {
-    use super::known_size_iter::KnownSizeIterator;
-    use super::tuple::Tuple;
-    use smallvec::SmallVec;
-    use std::collections::BTreeMap;
-    use std::iter;
-
-    type OneOrMore<V> = SmallVec<[V; 1]>;
-    type DupTreeMapInternal<K, V> = BTreeMap<K, OneOrMore<V>>;
-
-    #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
-    pub struct DupTreeMap<K, V> {
-        map: DupTreeMapInternal<K, V>,
-        size: usize,
-    }
-
-    // Generic types and functions to construct the iterators for this struct.
-    type ZipRepeatIter<T> = iter::Zip<
-        iter::Repeat<<T as Tuple>::First>,
-        <<T as Tuple>::Second as IntoIterator>::IntoIter,
-    >;
-    type DupTreeMapIter<M> = KnownSizeIterator<
-        iter::FlatMap<
-            <M as IntoIterator>::IntoIter,
-            ZipRepeatIter<<M as IntoIterator>::Item>,
-            fn(
-                <M as IntoIterator>::Item,
-            ) -> ZipRepeatIter<<M as IntoIterator>::Item>,
-        >,
-    >;
-
-    fn zip_repeat<K, I>((k, iter): (K, I)) -> ZipRepeatIter<(K, I)>
-    where
-        K: Clone,
-        I: IntoIterator,
-    {
-        iter::repeat(k).zip(iter.into_iter())
-    }
-
-    fn make_map_iter<M, K, I>(map: M, size: usize) -> DupTreeMapIter<M>
-    where
-        M: IntoIterator<Item = (K, I)>,
-        K: Clone,
-        I: IntoIterator,
-    {
-        KnownSizeIterator {
-            iter: map.into_iter().flat_map(zip_repeat),
-            size,
-        }
-    }
-
-    pub type IterMut<'a, K, V> =
-        DupTreeMapIter<&'a mut DupTreeMapInternal<K, V>>;
-    pub type Iter<'a, K, V> = DupTreeMapIter<&'a DupTreeMapInternal<K, V>>;
-    pub type IntoIter<K, V> = DupTreeMapIter<DupTreeMapInternal<K, V>>;
-
-    impl<K: Ord, V> DupTreeMap<K, V> {
-        pub fn new() -> Self {
-            DupTreeMap {
-                map: BTreeMap::new(),
-                size: 0,
-            }
-        }
-
-        pub fn insert(&mut self, key: K, value: V) {
-            self.map.entry(key).or_default().push(value);
-            self.size += 1;
-        }
-
-        pub fn len(&self) -> usize {
-            self.size
-        }
-        pub fn is_empty(&self) -> bool {
-            self.size == 0
-        }
-
-        pub fn iter(&self) -> Iter<'_, K, V> {
-            make_map_iter(&self.map, self.size)
-        }
-
-        pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
-            make_map_iter(&mut self.map, self.size)
-        }
-    }
-
-    impl<K, V> Default for DupTreeMap<K, V>
-    where
-        K: Ord,
-    {
-        fn default() -> Self {
-            Self::new()
-        }
-    }
-
-    impl<K, V> IntoIterator for DupTreeMap<K, V>
-    where
-        K: Ord + Clone,
-    {
-        type Item = (K, V);
-        type IntoIter = IntoIter<K, V>;
-
-        fn into_iter(self) -> Self::IntoIter {
-            make_map_iter(self.map, self.size)
-        }
-    }
-
-    impl<'a, K, V> IntoIterator for &'a DupTreeMap<K, V>
-    where
-        K: Ord + 'a,
-        V: 'a,
-    {
-        type Item = (&'a K, &'a V);
-        type IntoIter = Iter<'a, K, V>;
-
-        fn into_iter(self) -> Self::IntoIter {
-            self.iter()
-        }
-    }
-
-    impl<'a, K, V> IntoIterator for &'a mut DupTreeMap<K, V>
-    where
-        K: Ord + 'a,
-        V: 'a,
-    {
-        type Item = (&'a K, &'a mut V);
-        type IntoIter = IterMut<'a, K, V>;
-
-        fn into_iter(self) -> Self::IntoIter {
-            self.iter_mut()
-        }
-    }
-
-    impl<K, V> iter::FromIterator<(K, V)> for DupTreeMap<K, V>
-    where
-        K: Ord,
-    {
-        fn from_iter<T>(iter: T) -> Self
-        where
-            T: IntoIterator<Item = (K, V)>,
-        {
-            let mut map = DupTreeMap::new();
-            for (k, v) in iter {
-                map.insert(k, v);
-            }
-            map
-        }
-    }
-}
-
-mod dup_tree_set {
-    use super::tuple::Tuple;
-    use super::DupTreeMap;
-    use std::iter;
-
-    #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
-    pub struct DupTreeSet<K> {
-        map: DupTreeMap<K, ()>,
-    }
-
-    type DupTreeSetIter<M> = iter::Map<
-        <M as IntoIterator>::IntoIter,
-        fn(
-            <M as IntoIterator>::Item,
-        ) -> <<M as IntoIterator>::Item as Tuple>::First,
-    >;
-
-    pub type Iter<'a, K> = DupTreeSetIter<&'a DupTreeMap<K, ()>>;
-    pub type IntoIter<K> = DupTreeSetIter<DupTreeMap<K, ()>>;
-
-    fn drop_second<A, B>((a, _): (A, B)) -> A {
-        a
-    }
-
-    impl<K: Ord> DupTreeSet<K> {
-        pub fn new() -> Self {
-            DupTreeSet {
-                map: DupTreeMap::new(),
-            }
-        }
-
-        pub fn len(&self) -> usize {
-            self.map.len()
-        }
-        pub fn is_empty(&self) -> bool {
-            self.map.is_empty()
-        }
-
-        pub fn iter(&self) -> Iter<'_, K> {
-            self.map.iter().map(drop_second)
-        }
-    }
-
-    impl<K> Default for DupTreeSet<K>
-    where
-        K: Ord,
-    {
-        fn default() -> Self {
-            Self::new()
-        }
-    }
-
-    impl<K> IntoIterator for DupTreeSet<K>
-    where
-        K: Ord + Clone,
-    {
-        type Item = K;
-        type IntoIter = IntoIter<K>;
-
-        fn into_iter(self) -> Self::IntoIter {
-            self.map.into_iter().map(drop_second)
-        }
-    }
-
-    impl<'a, K> IntoIterator for &'a DupTreeSet<K>
-    where
-        K: Ord + 'a,
-    {
-        type Item = &'a K;
-        type IntoIter = Iter<'a, K>;
-
-        fn into_iter(self) -> Self::IntoIter {
-            self.iter()
-        }
-    }
-
-    impl<K> iter::FromIterator<K> for DupTreeSet<K>
-    where
-        K: Ord,
-    {
-        fn from_iter<T>(iter: T) -> Self
-        where
-            T: IntoIterator<Item = K>,
-        {
-            let map = iter.into_iter().map(|k| (k, ())).collect();
-            DupTreeSet { map }
-        }
-    }
-}
diff --git a/dhall/src/syntax/ast/mod.rs b/dhall/src/syntax/ast/mod.rs
index 1950154..c341af7 100644
--- a/dhall/src/syntax/ast/mod.rs
+++ b/dhall/src/syntax/ast/mod.rs
@@ -8,5 +8,4 @@ mod span;
 pub use span::*;
 mod text;
 pub use text::*;
-pub mod map;
 pub mod visitor;
diff --git a/dhall/src/syntax/binary/encode.rs b/dhall/src/syntax/binary/encode.rs
index 913dd67..b6bbabe 100644
--- a/dhall/src/syntax/binary/encode.rs
+++ b/dhall/src/syntax/binary/encode.rs
@@ -6,7 +6,6 @@ use crate::builtins::Builtin;
 use crate::error::EncodeError;
 use crate::operations::{BinOp, OpKind};
 use crate::syntax;
-use crate::syntax::map::DupTreeMap;
 use crate::syntax::{
     Expr, ExprKind, FilePrefix, Hash, Import, ImportMode, ImportTarget, Label,
     Scheme, V,
@@ -21,8 +20,7 @@ enum Serialize<'a> {
     Expr(&'a Expr),
     CBOR(cbor::Value),
     RecordMap(&'a BTreeMap<Label, Expr>),
-    RecordDupMap(&'a DupTreeMap<Label, Expr>),
-    UnionMap(&'a DupTreeMap<Label, Option<Expr>>),
+    UnionMap(&'a BTreeMap<Label, Option<Expr>>),
 }
 
 macro_rules! count {
@@ -52,7 +50,7 @@ where
     use syntax::NumKind::*;
     use OpKind::*;
 
-    use self::Serialize::{RecordDupMap, RecordMap, UnionMap};
+    use self::Serialize::{RecordMap, UnionMap};
     fn expr(x: &Expr) -> self::Serialize<'_> {
         self::Serialize::Expr(x)
     }
@@ -133,7 +131,7 @@ where
                 Text(x) => cbor(String(x)),
             })))
         }
-        RecordType(map) => ser_seq!(ser; tag(7), RecordDupMap(map)),
+        RecordType(map) => ser_seq!(ser; tag(7), RecordMap(map)),
         RecordLit(map) => ser_seq!(ser; tag(8), RecordMap(map)),
         UnionType(map) => ser_seq!(ser; tag(11), UnionMap(map)),
         Op(Field(x, l)) => ser_seq!(ser; tag(9), expr(x), label(l)),
@@ -266,11 +264,6 @@ impl<'a> serde::ser::Serialize for Serialize<'a> {
         match self {
             Serialize::Expr(e) => serialize_subexpr(ser, e),
             Serialize::CBOR(v) => v.serialize(ser),
-            Serialize::RecordDupMap(map) => {
-                ser.collect_map(map.iter().map(|(k, v)| {
-                    (cbor::Value::String(k.into()), Serialize::Expr(v))
-                }))
-            }
             Serialize::RecordMap(map) => {
                 ser.collect_map(map.iter().map(|(k, v)| {
                     (cbor::Value::String(k.into()), Serialize::Expr(v))
diff --git a/dhall/src/syntax/text/parser.rs b/dhall/src/syntax/text/parser.rs
index dbf5c75..dcaf5e4 100644
--- a/dhall/src/syntax/text/parser.rs
+++ b/dhall/src/syntax/text/parser.rs
@@ -1,14 +1,13 @@
 use itertools::Itertools;
 use pest::prec_climber as pcl;
 use pest::prec_climber::PrecClimber;
-use std::collections::BTreeMap;
+use std::collections::{BTreeMap, BTreeSet};
 use std::iter::once;
 use std::rc::Rc;
 
 use pest_consume::{match_nodes, Parser};
 
 use crate::operations::OpKind::*;
-use crate::syntax::map::{DupTreeMap, DupTreeSet};
 use crate::syntax::ExprKind::*;
 use crate::syntax::NumKind::*;
 use crate::syntax::{
@@ -32,7 +31,7 @@ pub type ParseResult<T> = Result<T, ParseError>;
 #[derive(Debug)]
 enum Selector {
     Field(Label),
-    Projection(DupTreeSet<Label>),
+    Projection(BTreeSet<Label>),
     ProjectionByExpr(Expr),
 }
 
@@ -879,9 +878,20 @@ impl DhallParser {
         Ok((stor, input_to_span(input)))
     }
 
-    fn labels(input: ParseInput) -> ParseResult<DupTreeSet<Label>> {
-        Ok(match_nodes!(input.into_children();
-            [label(ls)..] => ls.collect(),
+    fn labels(input: ParseInput) -> ParseResult<BTreeSet<Label>> {
+        Ok(match_nodes!(input.children();
+            [label(ls)..] => {
+                let mut set = BTreeSet::default();
+                for l in ls {
+                    if set.contains(&l) {
+                        return Err(
+                            input.error(format!("Duplicate field in projection"))
+                        )
+                    }
+                    set.insert(l);
+                }
+                set
+            },
         ))
     }
 
@@ -921,9 +931,26 @@ impl DhallParser {
 
     fn non_empty_record_type(
         input: ParseInput,
-    ) -> ParseResult<DupTreeMap<Label, Expr>> {
-        Ok(match_nodes!(input.into_children();
-            [record_type_entry(entries)..] => entries.collect()
+    ) -> ParseResult<BTreeMap<Label, Expr>> {
+        Ok(match_nodes!(input.children();
+            [record_type_entry(entries)..] => {
+                let mut map = BTreeMap::default();
+                for (l, t) in entries {
+                    use std::collections::btree_map::Entry;
+                    match map.entry(l) {
+                        Entry::Occupied(_) => {
+                            return Err(input.error(
+                                "Duplicate field in record type"
+                                    .to_string(),
+                            ));
+                        }
+                        Entry::Vacant(e) => {
+                            e.insert(t);
+                        }
+                    }
+                }
+                map
+            },
         ))
     }
 
@@ -972,7 +999,24 @@ impl DhallParser {
     fn union_type(input: ParseInput) -> ParseResult<UnspannedExpr> {
         let map = match_nodes!(input.children();
             [empty_union_type(_)] => Default::default(),
-            [union_type_entry(entries)..] => entries.collect(),
+            [union_type_entry(entries)..] => {
+                let mut map = BTreeMap::default();
+                for (l, t) in entries {
+                    use std::collections::btree_map::Entry;
+                    match map.entry(l) {
+                        Entry::Occupied(_) => {
+                            return Err(input.error(
+                                "Duplicate variant in union type"
+                                    .to_string(),
+                            ));
+                        }
+                        Entry::Vacant(e) => {
+                            e.insert(t);
+                        }
+                    }
+                }
+                map
+            },
         );
         Ok(UnionType(map))
     }
diff --git a/dhall/tests/type-inference/failure/mixedUnions.txt b/dhall/tests/type-inference/failure/mixedUnions.txt
index a6ca913..2b307d0 100644
--- a/dhall/tests/type-inference/failure/mixedUnions.txt
+++ b/dhall/tests/type-inference/failure/mixedUnions.txt
@@ -1,6 +1,6 @@
-Type error: error: InvalidFieldType
- --> <current file>:1:1
+Type error: error: InvalidVariantType
+ --> <current file>:1:28
   |
 1 | < Left : Natural | Right : Type >
-  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ InvalidFieldType
+  |                            ^^^^ InvalidVariantType
   |
diff --git a/dhall/tests/type-inference/failure/recordOfKind.txt b/dhall/tests/type-inference/failure/recordOfKind.txt
index 7dcbe4f..9a243c3 100644
--- a/dhall/tests/type-inference/failure/recordOfKind.txt
+++ b/dhall/tests/type-inference/failure/recordOfKind.txt
@@ -1,6 +1,6 @@
 Type error: error: InvalidFieldType
- --> <current file>:1:1
+ --> <current file>:1:7
   |
 1 | { a = Kind }
-  | ^^^^^^^^^^^^ InvalidFieldType
+  |       ^^^^ InvalidFieldType
   |
diff --git a/dhall/tests/type-inference/failure/unit/RecordMixedKinds3.txt b/dhall/tests/type-inference/failure/unit/RecordMixedKinds3.txt
index fa8b153..a83bb4f 100644
--- a/dhall/tests/type-inference/failure/unit/RecordMixedKinds3.txt
+++ b/dhall/tests/type-inference/failure/unit/RecordMixedKinds3.txt
@@ -1,6 +1,6 @@
 Type error: error: InvalidFieldType
- --> <current file>:1:1
+ --> <current file>:1:17
   |
 1 | { x = Type, y = Kind }
-  | ^^^^^^^^^^^^^^^^^^^^^^ InvalidFieldType
+  |                 ^^^^ InvalidFieldType
   |
diff --git a/dhall/tests/type-inference/failure/unit/RecordProjectionDuplicateFields.txt b/dhall/tests/type-inference/failure/unit/RecordProjectionDuplicateFields.txt
index 05c3eed..7b35481 100644
--- a/dhall/tests/type-inference/failure/unit/RecordProjectionDuplicateFields.txt
+++ b/dhall/tests/type-inference/failure/unit/RecordProjectionDuplicateFields.txt
@@ -1,6 +1,6 @@
-Type error: error: ProjectionDuplicateField
- --> <current file>:1:1
+ --> 1:11
   |
-1 | { x = 1 }.{ x, x }
-  | ^^^^^^^^^^^^^^^^^^ ProjectionDuplicateField
+1 | { x = 1 }.{ x, x }␊
+  |           ^------^
   |
+  = Duplicate field in projection
diff --git a/dhall/tests/type-inference/failure/unit/RecordTypeDuplicateFields.txt b/dhall/tests/type-inference/failure/unit/RecordTypeDuplicateFields.txt
index d8bec44..aced8a9 100644
--- a/dhall/tests/type-inference/failure/unit/RecordTypeDuplicateFields.txt
+++ b/dhall/tests/type-inference/failure/unit/RecordTypeDuplicateFields.txt
@@ -1,6 +1,6 @@
-Type error: error: RecordTypeDuplicateField
- --> <current file>:1:1
+ --> 1:3
   |
-1 | { x: Natural, x: Natural }
-  | ^^^^^^^^^^^^^^^^^^^^^^^^^^ RecordTypeDuplicateField
+1 | { x: Natural, x: Natural }␊
+  |   ^--------------------^
   |
+  = Duplicate field in record type
diff --git a/dhall/tests/type-inference/failure/unit/RecordTypeValueMember.txt b/dhall/tests/type-inference/failure/unit/RecordTypeValueMember.txt
index 81815a2..c6c274c 100644
--- a/dhall/tests/type-inference/failure/unit/RecordTypeValueMember.txt
+++ b/dhall/tests/type-inference/failure/unit/RecordTypeValueMember.txt
@@ -1,6 +1,6 @@
 Type error: error: InvalidFieldType
- --> <current file>:1:1
+ --> <current file>:1:7
   |
 1 | { x : True }
-  | ^^^^^^^^^^^^ InvalidFieldType
+  |       ^^^^ InvalidFieldType
   |
diff --git a/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds2.txt b/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds2.txt
index 146bf7f..6a6da80 100644
--- a/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds2.txt
+++ b/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds2.txt
@@ -1,6 +1,6 @@
 Type error: error: InvalidFieldType
- --> <current file>:1:16
+ --> <current file>:1:22
   |
 1 | { x = Bool } ⫽ { x = Kind }
-  |                ^^^^^^^^^^^^ InvalidFieldType
+  |                      ^^^^ InvalidFieldType
   |
diff --git a/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds3.txt b/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds3.txt
index 71914e1..322e7f4 100644
--- a/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds3.txt
+++ b/dhall/tests/type-inference/failure/unit/RightBiasedRecordMergeMixedKinds3.txt
@@ -1,6 +1,6 @@
 Type error: error: InvalidFieldType
- --> <current file>:1:15
+ --> <current file>:1:21
   |
 1 | { x = {=} } ⫽ { x = Kind }
-  |               ^^^^^^^^^^^^ InvalidFieldType
+  |                     ^^^^ InvalidFieldType
   |
diff --git a/dhall/tests/type-inference/failure/unit/UnionTypeDuplicateVariants1.txt b/dhall/tests/type-inference/failure/unit/UnionTypeDuplicateVariants1.txt
index 84bfe4d..9984693 100644
--- a/dhall/tests/type-inference/failure/unit/UnionTypeDuplicateVariants1.txt
+++ b/dhall/tests/type-inference/failure/unit/UnionTypeDuplicateVariants1.txt
@@ -1,6 +1,6 @@
-Type error: error: UnionTypeDuplicateField
- --> <current file>:1:1
+ --> 1:2
   |
-1 | <x | x>
-  | ^^^^^^^ UnionTypeDuplicateField
+1 | <x | x>␊
+  |  ^---^
   |
+  = Duplicate variant in union type
diff --git a/dhall/tests/type-inference/failure/unit/UnionTypeDuplicateVariants2.txt b/dhall/tests/type-inference/failure/unit/UnionTypeDuplicateVariants2.txt
index eb20b12..fdf6dc0 100644
--- a/dhall/tests/type-inference/failure/unit/UnionTypeDuplicateVariants2.txt
+++ b/dhall/tests/type-inference/failure/unit/UnionTypeDuplicateVariants2.txt
@@ -1,6 +1,6 @@
-Type error: error: UnionTypeDuplicateField
- --> <current file>:1:1
+ --> 1:2
   |
-1 | <x | x: Natural>
-  | ^^^^^^^^^^^^^^^^ UnionTypeDuplicateField
+1 | <x | x: Natural>␊
+  |  ^------------^
   |
+  = Duplicate variant in union type
diff --git a/dhall/tests/type-inference/failure/unit/UnionTypeMixedKinds.txt b/dhall/tests/type-inference/failure/unit/UnionTypeMixedKinds.txt
index 44ce7a3..ae6c845 100644
--- a/dhall/tests/type-inference/failure/unit/UnionTypeMixedKinds.txt
+++ b/dhall/tests/type-inference/failure/unit/UnionTypeMixedKinds.txt
@@ -1,6 +1,6 @@
-Type error: error: InvalidFieldType
- --> <current file>:1:1
+Type error: error: InvalidVariantType
+ --> <current file>:1:18
   |
 1 | < x : Bool | y : Type >
-  | ^^^^^^^^^^^^^^^^^^^^^^^ InvalidFieldType
+  |                  ^^^^ InvalidVariantType
   |
diff --git a/dhall/tests/type-inference/failure/unit/UnionTypeMixedKinds2.txt b/dhall/tests/type-inference/failure/unit/UnionTypeMixedKinds2.txt
index 01f706d..faf81a9 100644
--- a/dhall/tests/type-inference/failure/unit/UnionTypeMixedKinds2.txt
+++ b/dhall/tests/type-inference/failure/unit/UnionTypeMixedKinds2.txt
@@ -1,6 +1,6 @@
-Type error: error: InvalidFieldType
- --> <current file>:1:1
+Type error: error: InvalidVariantType
+ --> <current file>:1:18
   |
 1 | < x : Kind | y : Type >
-  | ^^^^^^^^^^^^^^^^^^^^^^^ InvalidFieldType
+  |                  ^^^^ InvalidVariantType
   |
diff --git a/dhall/tests/type-inference/failure/unit/UnionTypeMixedKinds3.txt b/dhall/tests/type-inference/failure/unit/UnionTypeMixedKinds3.txt
index 496462d..bbfb1f3 100644
--- a/dhall/tests/type-inference/failure/unit/UnionTypeMixedKinds3.txt
+++ b/dhall/tests/type-inference/failure/unit/UnionTypeMixedKinds3.txt
@@ -1,6 +1,6 @@
-Type error: error: InvalidFieldType
- --> <current file>:1:1
+Type error: error: InvalidVariantType
+ --> <current file>:1:18
   |
 1 | < x : Kind | y : Bool >
-  | ^^^^^^^^^^^^^^^^^^^^^^^ InvalidFieldType
+  |                  ^^^^ InvalidVariantType
   |
diff --git a/dhall/tests/type-inference/failure/unit/UnionTypeNotType.txt b/dhall/tests/type-inference/failure/unit/UnionTypeNotType.txt
index 450a3dd..cedf06e 100644
--- a/dhall/tests/type-inference/failure/unit/UnionTypeNotType.txt
+++ b/dhall/tests/type-inference/failure/unit/UnionTypeNotType.txt
@@ -1,6 +1,6 @@
-Type error: error: InvalidFieldType
- --> <current file>:1:1
+Type error: error: InvalidVariantType
+ --> <current file>:1:7
   |
 1 | < x : True >
-  | ^^^^^^^^^^^^ InvalidFieldType
+  |       ^^^^ InvalidVariantType
   |
diff --git a/tests_buffer b/tests_buffer
index afb270f..bd76d36 100644
--- a/tests_buffer
+++ b/tests_buffer
@@ -35,5 +35,6 @@ failure/
     merge { x = True, y = 1 } < x | y >.x
     merge {x=...,y=...} <x>.x
     merge {x=...,y=...} <x:T>.x
+fix unit_RightBiasedRecordMergeMixedKinds3 & 2 & unit_RecordMixedKinds3
 
 equivalence:
-- 
cgit v1.2.3