1 files changed, 102 insertions, 214 deletions

diff --git a/dhall/src/syntax/ast/map.rs b/dhall/src/syntax/ast/map.rs
index c4c6126..8b896c0 100644
--- a/dhall/src/syntax/ast/map.rs
+++ b/dhall/src/syntax/ast/map.rs
@@ -2,136 +2,112 @@
 pub use dup_tree_map::DupTreeMap;
 pub use dup_tree_set::DupTreeSet;
 
-mod one_or_more {
-    use either::Either;
-    use std::{iter, slice, vec};
-
-    #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
-    pub enum OneOrMore<T> {
-        One(T),
-        More(Vec<T>),
+mod known_size_iter {
+    pub struct KnownSizeIterator<I> {
+        pub iter: I,
+        pub size: usize,
     }
 
-    pub type Iter<'a, T> = Either<slice::Iter<'a, T>, iter::Once<&'a T>>;
-    pub type IterMut<'a, T> =
-        Either<slice::IterMut<'a, T>, iter::Once<&'a mut T>>;
-    pub type IntoIter<T> = Either<vec::IntoIter<T>, iter::Once<T>>;
-
-    impl<T> OneOrMore<T> {
-        pub fn new(x: T) -> Self {
-            OneOrMore::One(x)
-        }
+    impl<I: Iterator> Iterator for KnownSizeIterator<I> {
+        type Item = I::Item;
 
-        pub fn push(&mut self, x: T) {
-            take_mut::take(self, |sef| match sef {
-                OneOrMore::More(mut vec) => {
-                    vec.push(x);
-                    OneOrMore::More(vec)
-                }
-                OneOrMore::One(one) => OneOrMore::More(vec![one, x]),
-            })
-        }
-
-        pub fn iter(&self) -> Iter<'_, T> {
-            match self {
-                OneOrMore::More(vec) => Either::Left(vec.iter()),
-                OneOrMore::One(x) => Either::Right(iter::once(x)),
+        fn next(&mut self) -> Option<Self::Item> {
+            let next = self.iter.next();
+            if next.is_some() {
+                self.size -= 1;
             }
+            next
         }
 
-        pub fn iter_mut(&mut self) -> IterMut<'_, T> {
-            match self {
-                OneOrMore::More(vec) => Either::Left(vec.iter_mut()),
-                OneOrMore::One(x) => Either::Right(iter::once(x)),
-            }
+        fn size_hint(&self) -> (usize, Option<usize>) {
+            (self.size, Some(self.size))
         }
     }
 
-    impl<T> IntoIterator for OneOrMore<T> {
-        type Item = T;
-        type IntoIter = IntoIter<T>;
+    // unsafe impl<I: Iterator> iter::TrustedLen for KnownSizeIterator<I> {}
+}
 
-        fn into_iter(self) -> Self::IntoIter {
-            match self {
-                OneOrMore::More(vec) => Either::Left(vec.into_iter()),
-                OneOrMore::One(x) => Either::Right(iter::once(x)),
-            }
-        }
+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::one_or_more;
-    use super::one_or_more::OneOrMore;
-    use std::collections::{btree_map, BTreeMap};
+    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: BTreeMap<K, OneOrMore<V>>,
+        map: DupTreeMapInternal<K, V>,
         size: usize,
     }
 
-    pub type IterInternalIntermediate<'a, K, V> =
-        iter::Zip<iter::Repeat<&'a K>, one_or_more::Iter<'a, V>>;
-    pub type IterInternal<'a, K, V> = iter::FlatMap<
-        btree_map::Iter<'a, K, OneOrMore<V>>,
-        IterInternalIntermediate<'a, K, V>,
-        for<'b> fn(
-            (&'b K, &'b OneOrMore<V>),
-        ) -> IterInternalIntermediate<'b, K, V>,
+    // 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,
     >;
-    pub struct Iter<'a, K, V> {
-        iter: IterInternal<'a, K, V>,
-        size: usize,
-    }
-    pub type IterMutInternalIntermediate<'a, K, V> =
-        iter::Zip<iter::Repeat<&'a K>, one_or_more::IterMut<'a, V>>;
-    pub type IterMutInternal<'a, K, V> = iter::FlatMap<
-        btree_map::IterMut<'a, K, OneOrMore<V>>,
-        IterMutInternalIntermediate<'a, K, V>,
-        for<'b> fn(
-            (&'b K, &'b mut OneOrMore<V>),
-        ) -> IterMutInternalIntermediate<'b, K, V>,
+    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>,
+        >,
     >;
-    pub struct IterMut<'a, K, V> {
-        iter: IterMutInternal<'a, K, V>,
-        size: usize,
+
+    fn zip_repeat<'a, K, I>((k, iter): (K, I)) -> ZipRepeatIter<(K, I)>
+    where
+        K: Clone,
+        I: IntoIterator,
+    {
+        iter::repeat(k).zip(iter.into_iter())
     }
-    pub type IntoIterInternalIntermediate<K, V> =
-        iter::Zip<iter::Repeat<K>, one_or_more::IntoIter<V>>;
-    pub type IntoIterInternal<K, V> = iter::FlatMap<
-        btree_map::IntoIter<K, OneOrMore<V>>,
-        IntoIterInternalIntermediate<K, V>,
-        fn((K, OneOrMore<V>)) -> IntoIterInternalIntermediate<K, V>,
-    >;
-    pub struct IntoIter<K: Clone, V> {
-        iter: IntoIterInternal<K, V>,
-        size: usize,
+
+    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,
+        }
     }
 
-    impl<K, V> DupTreeMap<K, V> {
-        pub fn new() -> Self
-        where
-            K: Ord,
-        {
+    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)
-        where
-            K: Ord,
-        {
-            use std::collections::btree_map::Entry;
-            match self.map.entry(key) {
-                Entry::Vacant(e) => {
-                    e.insert(OneOrMore::new(value));
-                }
-                Entry::Occupied(mut e) => e.get_mut().push(value),
-            }
+        pub fn insert(&mut self, key: K, value: V) {
+            self.map.entry(key).or_default().push(value);
             self.size += 1;
         }
 
@@ -142,34 +118,12 @@ mod dup_tree_map {
             self.size == 0
         }
 
-        pub fn iter(&self) -> Iter<'_, K, V>
-        where
-            K: Ord,
-        {
-            fn foo<'a, K, V>(
-                (k, oom): (&'a K, &'a OneOrMore<V>),
-            ) -> IterInternalIntermediate<'a, K, V> {
-                iter::repeat(k).zip(oom.iter())
-            }
-            Iter {
-                iter: self.map.iter().flat_map(foo),
-                size: self.size,
-            }
+        pub fn iter(&self) -> Iter<'_, K, V> {
+            make_map_iter(&self.map, self.size)
         }
 
-        pub fn iter_mut(&mut self) -> IterMut<'_, K, V>
-        where
-            K: Ord,
-        {
-            fn foo<'a, K, V>(
-                (k, oom): (&'a K, &'a mut OneOrMore<V>),
-            ) -> IterMutInternalIntermediate<'a, K, V> {
-                iter::repeat(k).zip(oom.iter_mut())
-            }
-            IterMut {
-                iter: self.map.iter_mut().flat_map(foo),
-                size: self.size,
-            }
+        pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
+            make_map_iter(&mut self.map, self.size)
         }
     }
 
@@ -190,24 +144,14 @@ mod dup_tree_map {
         type IntoIter = IntoIter<K, V>;
 
         fn into_iter(self) -> Self::IntoIter {
-            fn foo<K, V>(
-                (k, oom): (K, OneOrMore<V>),
-            ) -> IntoIterInternalIntermediate<K, V>
-            where
-                K: Clone,
-            {
-                iter::repeat(k).zip(oom.into_iter())
-            }
-            IntoIter {
-                iter: self.map.into_iter().flat_map(foo),
-                size: self.size,
-            }
+            make_map_iter(self.map, self.size)
         }
     }
 
     impl<'a, K, V> IntoIterator for &'a DupTreeMap<K, V>
     where
-        K: Ord,
+        K: Ord + 'a,
+        V: 'a,
     {
         type Item = (&'a K, &'a V);
         type IntoIter = Iter<'a, K, V>;
@@ -219,7 +163,8 @@ mod dup_tree_map {
 
     impl<'a, K, V> IntoIterator for &'a mut DupTreeMap<K, V>
     where
-        K: Ord,
+        K: Ord + 'a,
+        V: 'a,
     {
         type Item = (&'a K, &'a mut V);
         type IntoIter = IterMut<'a, K, V>;
@@ -244,62 +189,10 @@ mod dup_tree_map {
             map
         }
     }
-
-    impl<'a, K, V> Iterator for Iter<'a, K, V> {
-        type Item = (&'a K, &'a V);
-
-        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))
-        }
-    }
-
-    impl<'a, K, V> Iterator for IterMut<'a, K, V> {
-        type Item = (&'a K, &'a mut V);
-
-        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))
-        }
-    }
-
-    impl<K, V> Iterator for IntoIter<K, V>
-    where
-        K: Clone,
-    {
-        type Item = (K, V);
-
-        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<K, V> iter::TrustedLen for IntoIter<K, V> {}
 }
 
 mod dup_tree_set {
+    use super::tuple::Tuple;
     use super::DupTreeMap;
     use std::iter;
 
@@ -308,18 +201,22 @@ mod dup_tree_set {
         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,
+    type DupTreeSetIter<M> = iter::Map<
+        <M as IntoIterator>::IntoIter,
+        fn(
+            <M as IntoIterator>::Item,
+        ) -> <<M as IntoIterator>::Item as Tuple>::First,
     >;
-    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,
-        {
+    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(),
             }
@@ -332,14 +229,8 @@ mod dup_tree_set {
             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)
+        pub fn iter<'a>(&'a self) -> Iter<'a, K> {
+            self.map.iter().map(drop_second)
         }
     }
 
@@ -360,16 +251,13 @@ mod dup_tree_set {
         type IntoIter = IntoIter<K>;
 
         fn into_iter(self) -> Self::IntoIter {
-            fn foo<K>((k, ()): (K, ())) -> K {
-                k
-            }
-            self.map.into_iter().map(foo)
+            self.map.into_iter().map(drop_second)
         }
     }
 
     impl<'a, K> IntoIterator for &'a DupTreeSet<K>
     where
-        K: Ord,
+        K: Ord + 'a,
     {
         type Item = &'a K;
         type IntoIter = Iter<'a, K>;