summaryrefslogtreecommitdiff
path: root/dhall/src
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--dhall/src/syntax/ast/map.rs316
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>;