Sort labels in projection expressions

3 files changed, 100 insertions, 5 deletions

diff --git a/dhall_syntax/src/core/expr.rs b/dhall_syntax/src/core/expr.rs
index 14dc165..668ab45 100644
--- a/dhall_syntax/src/core/expr.rs
+++ b/dhall_syntax/src/core/expr.rs
@@ -1,6 +1,6 @@
 use std::rc::Rc;
 
-use crate::map::DupTreeMap;
+use crate::map::{DupTreeMap, DupTreeSet};
 use crate::visitor;
 use crate::*;
 
@@ -209,7 +209,7 @@ pub enum ExprF<SubExpr, Embed> {
     ///  `e.x`
     Field(SubExpr, Label),
     ///  `e.{ x, y, z }`
-    Projection(SubExpr, Vec<Label>),
+    Projection(SubExpr, DupTreeSet<Label>),
     /// Embeds an import or the result of resolving the import
     Embed(Embed),
 }
diff --git a/dhall_syntax/src/core/map.rs b/dhall_syntax/src/core/map.rs
index 63f19cd..6a0ebda 100644
--- a/dhall_syntax/src/core/map.rs
+++ b/dhall_syntax/src/core/map.rs
@@ -1,5 +1,6 @@
 /// A sorted map that allows multiple values for each key.
 pub use dup_tree_map::DupTreeMap;
+pub use dup_tree_set::DupTreeSet;
 
 mod one_or_more {
     use either::Either;
@@ -232,3 +233,97 @@ mod dup_tree_map {
 
     // unsafe impl<K, V> iter::TrustedLen for IntoIter<K, V> {}
 }
+
+mod dup_tree_set {
+    use super::DupTreeMap;
+    use std::iter;
+
+    #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
+    pub struct DupTreeSet<K> {
+        map: DupTreeMap<K, ()>,
+    }
+
+    pub type Iter<'a, K> = iter::Map<
+        super::dup_tree_map::Iter<'a, K, ()>,
+        for<'b> fn((&'b K, &'b ())) -> &'b K,
+    >;
+    pub type IntoIter<K> =
+        iter::Map<super::dup_tree_map::IntoIter<K, ()>, fn((K, ())) -> K>;
+
+    impl<K> DupTreeSet<K> {
+        pub fn new() -> Self
+        where
+            K: Ord,
+        {
+            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>
+        where
+            K: Ord,
+        {
+            fn foo<'a, K>((k, ()): (&'a K, &'a ())) -> &'a K {
+                k
+            }
+            self.map.iter().map(foo)
+        }
+    }
+
+    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 {
+            fn foo<K>((k, ()): (K, ())) -> K {
+                k
+            }
+            self.map.into_iter().map(foo)
+        }
+    }
+
+    impl<'a, K> IntoIterator for &'a DupTreeSet<K>
+    where
+        K: Ord,
+    {
+        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_syntax/src/parser.rs b/dhall_syntax/src/parser.rs
index 8a84b00..5be8477 100644
--- a/dhall_syntax/src/parser.rs
+++ b/dhall_syntax/src/parser.rs
@@ -6,7 +6,7 @@ use std::rc::Rc;
 
 use dhall_generated_parser::{DhallParser, Rule};
 
-use crate::map::DupTreeMap;
+use crate::map::{DupTreeMap, DupTreeSet};
 use crate::ExprF::*;
 use crate::*;
 
@@ -894,13 +894,13 @@ make_parser! {
         }
     ));
 
-    rule!(selector<Either<Label, Vec<Label>>>; children!(
+    rule!(selector<Either<Label, DupTreeSet<Label>>>; children!(
         [label(l)] => Either::Left(l),
         [labels(ls)] => Either::Right(ls),
         [expression(e)] => unimplemented!("selection by expression"), // TODO
     ));
 
-    rule!(labels<Vec<Label>>; children!(
+    rule!(labels<DupTreeSet<Label>>; children!(
         [label(ls)..] => ls.collect(),
     ));