Use smallvec instead of custom struct

3 files changed, 30 insertions, 79 deletions

diff --git a/Cargo.lock b/Cargo.lock
index d7e61e7..8a95325 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -69,7 +69,6 @@ name = "dhall"
 version = "0.1.0"
 dependencies = [
  "abnf_to_pest 0.1.1",
- "either 1.5.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "hex 0.3.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "itertools 0.8.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "lazy_static 1.4.0 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -79,6 +78,7 @@ dependencies = [
  "pretty_assertions 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde 1.0.99 (registry+https://github.com/rust-lang/crates.io-index)",
  "serde_cbor 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "smallvec 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
  "take_mut 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)",
  "walkdir 2.2.9 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
@@ -356,6 +356,11 @@ dependencies = [
 ]
 
 [[package]]
+name = "smallvec"
+version = "1.0.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "syn"
 version = "1.0.5"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -472,6 +477,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
 "checksum serde_cbor 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)" = "45cd6d95391b16cd57e88b68be41d504183b7faae22030c0cc3b3f73dd57b2fd"
 "checksum serde_derive 1.0.99 (registry+https://github.com/rust-lang/crates.io-index)" = "cb4dc18c61206b08dc98216c98faa0232f4337e1e1b8574551d5bad29ea1b425"
 "checksum sha-1 0.8.1 (registry+https://github.com/rust-lang/crates.io-index)" = "23962131a91661d643c98940b20fcaffe62d776a823247be80a48fcb8b6fce68"
+"checksum smallvec 1.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "4ecf3b85f68e8abaa7555aa5abdb1153079387e60b718283d732f03897fcfc86"
 "checksum syn 1.0.5 (registry+https://github.com/rust-lang/crates.io-index)" = "66850e97125af79138385e9b88339cbcd037e3f28ceab8c5ad98e64f0f1f80bf"
 "checksum take_mut 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "f764005d11ee5f36500a149ace24e00e3da98b0158b3e2d53a7495660d3f4d60"
 "checksum typed-arena 1.5.0 (registry+https://github.com/rust-lang/crates.io-index)" = "7f70f5c346cc11bc044ae427ab2feae213350dca9e2d637047797d5ff316a646"
diff --git a/dhall/Cargo.toml b/dhall/Cargo.toml
index 00b8a32..a93153d 100644
--- a/dhall/Cargo.toml
+++ b/dhall/Cargo.toml
@@ -7,7 +7,6 @@ edition = "2018"
 build = "build.rs"
 
 [dependencies]
-either = "1.5.2"
 itertools = "0.8.0"
 hex = "0.3.2"
 lazy_static = "1.4.0"
@@ -17,6 +16,7 @@ pest = "2.1"
 pest_consume = "1.0"
 serde = { version = "1.0" }
 serde_cbor = "0.9.0"
+smallvec = "1.0.0"
 take_mut = "0.2.2"
 
 [dev-dependencies]
diff --git a/dhall/src/syntax/ast/map.rs b/dhall/src/syntax/ast/map.rs
index c4c6126..1077dca 100644
--- a/dhall/src/syntax/ast/map.rs
+++ b/dhall/src/syntax/ast/map.rs
@@ -2,83 +2,26 @@
 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>),
-    }
-
-    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)
-        }
-
-        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)),
-            }
-        }
-
-        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)),
-            }
-        }
-    }
-
-    impl<T> IntoIterator for OneOrMore<T> {
-        type Item = T;
-        type IntoIter = IntoIter<T>;
-
-        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 dup_tree_map {
-    use super::one_or_more;
-    use super::one_or_more::OneOrMore;
+    use smallvec as svec;
+    use smallvec::smallvec;
     use std::collections::{btree_map, BTreeMap};
     use std::iter;
+    use std::{slice, vec};
 
     #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
     pub struct DupTreeMap<K, V> {
-        map: BTreeMap<K, OneOrMore<V>>,
+        map: BTreeMap<K, smallvec::SmallVec<[V; 1]>>,
         size: usize,
     }
 
     pub type IterInternalIntermediate<'a, K, V> =
-        iter::Zip<iter::Repeat<&'a K>, one_or_more::Iter<'a, V>>;
+        iter::Zip<iter::Repeat<&'a K>, slice::Iter<'a, V>>;
     pub type IterInternal<'a, K, V> = iter::FlatMap<
-        btree_map::Iter<'a, K, OneOrMore<V>>,
+        btree_map::Iter<'a, K, smallvec::SmallVec<[V; 1]>>,
         IterInternalIntermediate<'a, K, V>,
         for<'b> fn(
-            (&'b K, &'b OneOrMore<V>),
+            (&'b K, &'b smallvec::SmallVec<[V; 1]>),
         ) -> IterInternalIntermediate<'b, K, V>,
     >;
     pub struct Iter<'a, K, V> {
@@ -86,12 +29,12 @@ mod dup_tree_map {
         size: usize,
     }
     pub type IterMutInternalIntermediate<'a, K, V> =
-        iter::Zip<iter::Repeat<&'a K>, one_or_more::IterMut<'a, V>>;
+        iter::Zip<iter::Repeat<&'a K>, slice::IterMut<'a, V>>;
     pub type IterMutInternal<'a, K, V> = iter::FlatMap<
-        btree_map::IterMut<'a, K, OneOrMore<V>>,
+        btree_map::IterMut<'a, K, smallvec::SmallVec<[V; 1]>>,
         IterMutInternalIntermediate<'a, K, V>,
         for<'b> fn(
-            (&'b K, &'b mut OneOrMore<V>),
+            (&'b K, &'b mut smallvec::SmallVec<[V; 1]>),
         ) -> IterMutInternalIntermediate<'b, K, V>,
     >;
     pub struct IterMut<'a, K, V> {
@@ -99,11 +42,13 @@ mod dup_tree_map {
         size: usize,
     }
     pub type IntoIterInternalIntermediate<K, V> =
-        iter::Zip<iter::Repeat<K>, one_or_more::IntoIter<V>>;
+        iter::Zip<iter::Repeat<K>, svec::IntoIter<[V; 1]>>;
     pub type IntoIterInternal<K, V> = iter::FlatMap<
-        btree_map::IntoIter<K, OneOrMore<V>>,
+        btree_map::IntoIter<K, smallvec::SmallVec<[V; 1]>>,
         IntoIterInternalIntermediate<K, V>,
-        fn((K, OneOrMore<V>)) -> IntoIterInternalIntermediate<K, V>,
+        fn(
+            (K, smallvec::SmallVec<[V; 1]>),
+        ) -> IntoIterInternalIntermediate<K, V>,
     >;
     pub struct IntoIter<K: Clone, V> {
         iter: IntoIterInternal<K, V>,
@@ -128,7 +73,7 @@ mod dup_tree_map {
             use std::collections::btree_map::Entry;
             match self.map.entry(key) {
                 Entry::Vacant(e) => {
-                    e.insert(OneOrMore::new(value));
+                    e.insert(smallvec![value]);
                 }
                 Entry::Occupied(mut e) => e.get_mut().push(value),
             }
@@ -147,9 +92,9 @@ mod dup_tree_map {
             K: Ord,
         {
             fn foo<'a, K, V>(
-                (k, oom): (&'a K, &'a OneOrMore<V>),
+                (k, vec): (&'a K, &'a smallvec::SmallVec<[V; 1]>),
             ) -> IterInternalIntermediate<'a, K, V> {
-                iter::repeat(k).zip(oom.iter())
+                iter::repeat(k).zip(vec.iter())
             }
             Iter {
                 iter: self.map.iter().flat_map(foo),
@@ -162,9 +107,9 @@ mod dup_tree_map {
             K: Ord,
         {
             fn foo<'a, K, V>(
-                (k, oom): (&'a K, &'a mut OneOrMore<V>),
+                (k, vec): (&'a K, &'a mut smallvec::SmallVec<[V; 1]>),
             ) -> IterMutInternalIntermediate<'a, K, V> {
-                iter::repeat(k).zip(oom.iter_mut())
+                iter::repeat(k).zip(vec.iter_mut())
             }
             IterMut {
                 iter: self.map.iter_mut().flat_map(foo),
@@ -191,12 +136,12 @@ mod dup_tree_map {
 
         fn into_iter(self) -> Self::IntoIter {
             fn foo<K, V>(
-                (k, oom): (K, OneOrMore<V>),
+                (k, vec): (K, smallvec::SmallVec<[V; 1]>),
             ) -> IntoIterInternalIntermediate<K, V>
             where
                 K: Clone,
             {
-                iter::repeat(k).zip(oom.into_iter())
+                iter::repeat(k).zip(vec.into_iter())
             }
             IntoIter {
                 iter: self.map.into_iter().flat_map(foo),