diff options
Diffstat (limited to 'dhall')
-rw-r--r-- | dhall/Cargo.toml | 2 | ||||
-rw-r--r-- | dhall/src/syntax/ast/map.rs | 99 |
2 files changed, 23 insertions, 78 deletions
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), |