Detect duplicate record fields in typecheck

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<Thunk>),
-    RecordLit(BTreeMap<Label, Thunk>),
-    RecordType(BTreeMap<Label, TypeThunk>),
-    UnionType(BTreeMap<Label, Option<TypeThunk>>),
-    UnionConstructor(Label, BTreeMap<Label, Option<TypeThunk>>),
-    UnionLit(Label, Thunk, BTreeMap<Label, Option<TypeThunk>>),
+    RecordLit(HashMap<Label, Thunk>),
+    RecordType(HashMap<Label, TypeThunk>),
+    UnionType(HashMap<Label, Option<TypeThunk>>),
+    UnionConstructor(Label, HashMap<Label, Option<TypeThunk>>),
+    UnionLit(Label, Thunk, HashMap<Label, Option<TypeThunk>>),
     // Invariant: this must not contain interpolations that are themselves TextLits, and
     // contiguous text values must be merged.
     TextLit(Vec<InterpolatedTextContents<Thunk>>),
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<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");
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<TS>(m: BTreeMap<Label, TS>) -> TokenStream
+fn quote_map<TS>(m: impl IntoIterator<Item = (Label, TS)>) -> 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<TS>(m: BTreeMap<Label, Option<TS>>) -> TokenStream
+fn quote_opt_map<TS>(
+    m: impl IntoIterator<Item = (Label, Option<TS>)>,
+) -> 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<SubExpr, Label, Embed> {
     ///  `Some e`
     SomeLit(SubExpr),
     ///  `{ k1 : t1, k2 : t1 }`
-    RecordType(BTreeMap<Label, SubExpr>),
+    RecordType(Vec<(Label, SubExpr)>),
     ///  `{ k1 = v1, k2 = v2 }`
-    RecordLit(BTreeMap<Label, SubExpr>),
+    RecordLit(Vec<(Label, SubExpr)>),
     ///  `< k1 : t1, k2 >`
-    UnionType(BTreeMap<Label, Option<SubExpr>>),
+    UnionType(Vec<(Label, Option<SubExpr>)>),
     ///  `< k1 = t1, k2 : t2, k3 >`
-    UnionLit(Label, SubExpr, BTreeMap<Label, Option<SubExpr>>),
+    UnionLit(Label, SubExpr, Vec<(Label, Option<SubExpr>)>),
     ///  `merge x y : t`
     Merge(SubExpr, SubExpr, Option<SubExpr>),
     ///  `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<L, SE>,
+        fn vecmap<'a, V, Ret, SE, L, E>(
+            x: &'a Vec<(L, SE)>,
             mut v: V,
-        ) -> Result<BTreeMap<V::L2, V::SE2>, V::Error>
+        ) -> Result<Vec<(V::L2, V::SE2)>, 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<L, Option<SE>>,
+        fn vecoptmap<'a, V, Ret, SE, L, E>(
+            x: &'a Vec<(L, Option<SE>)>,
             mut v: V,
-        ) -> Result<BTreeMap<V::L2, Option<V::SE2>>, V::Error>
+        ) -> Result<Vec<(V::L2, Option<V::SE2>)>, 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<ParsedSubExpr> as expression; span;
-        captured_str!(_) => spanned(span, RecordLit(BTreeMap::new()))
+        captured_str!(_) => spanned(span, RecordLit(Vec::new()))
     );
 
     rule!(empty_record_type<ParsedSubExpr> as expression; span;
-        captured_str!(_) => spanned(span, RecordType(BTreeMap::new()))
+        captured_str!(_) => spanned(span, RecordType(Vec::new()))
     );
 
     rule!(non_empty_record_type_or_literal<ParsedSubExpr> 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<Label, ParsedSubExpr>)>; 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<Label, ParsedSubExpr>)>; 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<ParsedSubExpr> 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<Label, Option<ParsedSubExpr>>)>;
+            Vec<(Label, Option<ParsedSubExpr>)>)>;
             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<Label, Option<ParsedSubExpr>>)>;
+          <(ParsedSubExpr, Vec<(Label, Option<ParsedSubExpr>)>)>;
             children!(
         [expression(e), union_type_entry(entries)..] => {
             (e, entries.collect())
@@ -975,19 +984,19 @@ make_parser! {
     rule!(union_type_or_literal_variant_type
           <(Option<ParsedSubExpr>,
             (Option<(Label, ParsedSubExpr)>,
-             BTreeMap<Label, Option<ParsedSubExpr>>))>;
+             Vec<(Label, Option<ParsedSubExpr>)>))>;
                 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()))
         },
     ));