From 0afd14903127ba73bca9b5a1461c2fec7f4440ef Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Fri, 20 Dec 2019 21:39:38 +0000 Subject: Use smallvec instead of custom struct --- dhall/src/syntax/ast/map.rs | 99 ++++++++++----------------------------------- 1 file changed, 22 insertions(+), 77 deletions(-) (limited to 'dhall/src') 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 { - One(T), - More(Vec), - } - - pub type Iter<'a, T> = Either, iter::Once<&'a T>>; - pub type IterMut<'a, T> = - Either, iter::Once<&'a mut T>>; - pub type IntoIter = Either, iter::Once>; - - impl OneOrMore { - 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 IntoIterator for OneOrMore { - type Item = T; - type IntoIter = IntoIter; - - 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 { - map: BTreeMap>, + map: BTreeMap>, size: usize, } pub type IterInternalIntermediate<'a, K, V> = - iter::Zip, one_or_more::Iter<'a, V>>; + iter::Zip, slice::Iter<'a, V>>; pub type IterInternal<'a, K, V> = iter::FlatMap< - btree_map::Iter<'a, K, OneOrMore>, + btree_map::Iter<'a, K, smallvec::SmallVec<[V; 1]>>, IterInternalIntermediate<'a, K, V>, for<'b> fn( - (&'b K, &'b OneOrMore), + (&'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, one_or_more::IterMut<'a, V>>; + iter::Zip, slice::IterMut<'a, V>>; pub type IterMutInternal<'a, K, V> = iter::FlatMap< - btree_map::IterMut<'a, K, OneOrMore>, + btree_map::IterMut<'a, K, smallvec::SmallVec<[V; 1]>>, IterMutInternalIntermediate<'a, K, V>, for<'b> fn( - (&'b K, &'b mut OneOrMore), + (&'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 = - iter::Zip, one_or_more::IntoIter>; + iter::Zip, svec::IntoIter<[V; 1]>>; pub type IntoIterInternal = iter::FlatMap< - btree_map::IntoIter>, + btree_map::IntoIter>, IntoIterInternalIntermediate, - fn((K, OneOrMore)) -> IntoIterInternalIntermediate, + fn( + (K, smallvec::SmallVec<[V; 1]>), + ) -> IntoIterInternalIntermediate, >; pub struct IntoIter { iter: IntoIterInternal, @@ -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), + (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), + (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, oom): (K, OneOrMore), + (k, vec): (K, smallvec::SmallVec<[V; 1]>), ) -> IntoIterInternalIntermediate 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), -- cgit v1.2.3 From fbe93508fade189020d6229901802edb351501f3 Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Fri, 20 Dec 2019 22:55:59 +0000 Subject: Simplify iterator impls for DupTreeMap --- dhall/src/syntax/ast/map.rs | 287 ++++++++++++++++++-------------------------- 1 file changed, 115 insertions(+), 172 deletions(-) (limited to 'dhall/src') diff --git a/dhall/src/syntax/ast/map.rs b/dhall/src/syntax/ast/map.rs index 1077dca..8b896c0 100644 --- a/dhall/src/syntax/ast/map.rs +++ b/dhall/src/syntax/ast/map.rs @@ -2,81 +2,112 @@ pub use dup_tree_map::DupTreeMap; pub use dup_tree_set::DupTreeSet; +mod known_size_iter { + pub struct KnownSizeIterator { + pub iter: I, + pub size: usize, + } + + impl Iterator for KnownSizeIterator { + type Item = I::Item; + + fn next(&mut self) -> Option { + let next = self.iter.next(); + if next.is_some() { + self.size -= 1; + } + next + } + + fn size_hint(&self) -> (usize, Option) { + (self.size, Some(self.size)) + } + } + + // unsafe impl iter::TrustedLen for KnownSizeIterator {} +} + +mod tuple { + mod sealed { + pub trait Sealed {} + } + pub trait Tuple: sealed::Sealed { + type First; + type Second; + } + impl sealed::Sealed for (A, B) {} + impl Tuple for (A, B) { + type First = A; + type Second = B; + } +} + mod dup_tree_map { - use smallvec as svec; - use smallvec::smallvec; - 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; - use std::{slice, vec}; + + type OneOrMore = SmallVec<[V; 1]>; + type DupTreeMapInternal = BTreeMap>; #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] pub struct DupTreeMap { - map: BTreeMap>, + map: DupTreeMapInternal, size: usize, } - pub type IterInternalIntermediate<'a, K, V> = - iter::Zip, slice::Iter<'a, V>>; - pub type IterInternal<'a, K, V> = iter::FlatMap< - btree_map::Iter<'a, K, smallvec::SmallVec<[V; 1]>>, - IterInternalIntermediate<'a, K, V>, - for<'b> fn( - (&'b K, &'b smallvec::SmallVec<[V; 1]>), - ) -> IterInternalIntermediate<'b, K, V>, + // Generic types and functions to construct the iterators for this struct. + type ZipRepeatIter = iter::Zip< + iter::Repeat<::First>, + <::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, slice::IterMut<'a, V>>; - pub type IterMutInternal<'a, K, V> = iter::FlatMap< - btree_map::IterMut<'a, K, smallvec::SmallVec<[V; 1]>>, - IterMutInternalIntermediate<'a, K, V>, - for<'b> fn( - (&'b K, &'b mut smallvec::SmallVec<[V; 1]>), - ) -> IterMutInternalIntermediate<'b, K, V>, + type DupTreeMapIter = KnownSizeIterator< + iter::FlatMap< + ::IntoIter, + ZipRepeatIter<::Item>, + fn( + ::Item, + ) -> ZipRepeatIter<::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 = - iter::Zip, svec::IntoIter<[V; 1]>>; - pub type IntoIterInternal = iter::FlatMap< - btree_map::IntoIter>, - IntoIterInternalIntermediate, - fn( - (K, smallvec::SmallVec<[V; 1]>), - ) -> IntoIterInternalIntermediate, - >; - pub struct IntoIter { - iter: IntoIterInternal, - size: usize, + + fn make_map_iter(map: M, size: usize) -> DupTreeMapIter + where + M: IntoIterator, + K: Clone, + I: IntoIterator, + { + KnownSizeIterator { + iter: map.into_iter().flat_map(zip_repeat), + size, + } } - impl DupTreeMap { - pub fn new() -> Self - where - K: Ord, - { + pub type IterMut<'a, K, V> = + DupTreeMapIter<&'a mut DupTreeMapInternal>; + pub type Iter<'a, K, V> = DupTreeMapIter<&'a DupTreeMapInternal>; + pub type IntoIter = DupTreeMapIter>; + + impl DupTreeMap { + 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(smallvec![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; } @@ -87,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, vec): (&'a K, &'a smallvec::SmallVec<[V; 1]>), - ) -> IterInternalIntermediate<'a, K, V> { - iter::repeat(k).zip(vec.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, vec): (&'a K, &'a mut smallvec::SmallVec<[V; 1]>), - ) -> IterMutInternalIntermediate<'a, K, V> { - iter::repeat(k).zip(vec.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) } } @@ -135,24 +144,14 @@ mod dup_tree_map { type IntoIter = IntoIter; fn into_iter(self) -> Self::IntoIter { - fn foo( - (k, vec): (K, smallvec::SmallVec<[V; 1]>), - ) -> IntoIterInternalIntermediate - where - K: Clone, - { - iter::repeat(k).zip(vec.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 where - K: Ord, + K: Ord + 'a, + V: 'a, { type Item = (&'a K, &'a V); type IntoIter = Iter<'a, K, V>; @@ -164,7 +163,8 @@ mod dup_tree_map { impl<'a, K, V> IntoIterator for &'a mut DupTreeMap where - K: Ord, + K: Ord + 'a, + V: 'a, { type Item = (&'a K, &'a mut V); type IntoIter = IterMut<'a, K, V>; @@ -189,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 { - let next = self.iter.next(); - if next.is_some() { - self.size -= 1; - } - next - } - - fn size_hint(&self) -> (usize, Option) { - (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 { - let next = self.iter.next(); - if next.is_some() { - self.size -= 1; - } - next - } - - fn size_hint(&self) -> (usize, Option) { - (self.size, Some(self.size)) - } - } - - impl Iterator for IntoIter - where - K: Clone, - { - type Item = (K, V); - - fn next(&mut self) -> Option { - let next = self.iter.next(); - if next.is_some() { - self.size -= 1; - } - next - } - - fn size_hint(&self) -> (usize, Option) { - (self.size, Some(self.size)) - } - } - - // unsafe impl iter::TrustedLen for IntoIter {} } mod dup_tree_set { + use super::tuple::Tuple; use super::DupTreeMap; use std::iter; @@ -253,18 +201,22 @@ mod dup_tree_set { map: DupTreeMap, } - pub type Iter<'a, K> = iter::Map< - super::dup_tree_map::Iter<'a, K, ()>, - for<'b> fn((&'b K, &'b ())) -> &'b K, + type DupTreeSetIter = iter::Map< + ::IntoIter, + fn( + ::Item, + ) -> <::Item as Tuple>::First, >; - pub type IntoIter = - iter::Map, fn((K, ())) -> K>; - impl DupTreeSet { - pub fn new() -> Self - where - K: Ord, - { + pub type Iter<'a, K> = DupTreeSetIter<&'a DupTreeMap>; + pub type IntoIter = DupTreeSetIter>; + + fn drop_second((a, _): (A, B)) -> A { + a + } + + impl DupTreeSet { + pub fn new() -> Self { DupTreeSet { map: DupTreeMap::new(), } @@ -277,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) } } @@ -305,16 +251,13 @@ mod dup_tree_set { type IntoIter = IntoIter; fn into_iter(self) -> Self::IntoIter { - fn foo((k, ()): (K, ())) -> K { - k - } - self.map.into_iter().map(foo) + self.map.into_iter().map(drop_second) } } impl<'a, K> IntoIterator for &'a DupTreeSet where - K: Ord, + K: Ord + 'a, { type Item = &'a K; type IntoIter = Iter<'a, K>; -- cgit v1.2.3