From 881248d2c4f0b4556a23d671d355bb7258adf8bb Mon Sep 17 00:00:00 2001 From: Nadrieril Date: Tue, 17 Dec 2019 14:33:06 +0000 Subject: Rename syntax::core to syntax::ast --- dhall/src/syntax/ast/map.rs | 394 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 394 insertions(+) create mode 100644 dhall/src/syntax/ast/map.rs (limited to 'dhall/src/syntax/ast/map.rs') diff --git a/dhall/src/syntax/ast/map.rs b/dhall/src/syntax/ast/map.rs new file mode 100644 index 0000000..c4c6126 --- /dev/null +++ b/dhall/src/syntax/ast/map.rs @@ -0,0 +1,394 @@ +/// A sorted map that allows multiple values for each key. +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 std::collections::{btree_map, BTreeMap}; + use std::iter; + + #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] + pub struct DupTreeMap { + map: BTreeMap>, + size: usize, + } + + pub type IterInternalIntermediate<'a, K, V> = + iter::Zip, one_or_more::Iter<'a, V>>; + pub type IterInternal<'a, K, V> = iter::FlatMap< + btree_map::Iter<'a, K, OneOrMore>, + IterInternalIntermediate<'a, K, V>, + for<'b> fn( + (&'b K, &'b OneOrMore), + ) -> IterInternalIntermediate<'b, K, V>, + >; + pub struct Iter<'a, K, V> { + iter: IterInternal<'a, K, V>, + size: usize, + } + pub type IterMutInternalIntermediate<'a, K, V> = + iter::Zip, one_or_more::IterMut<'a, V>>; + pub type IterMutInternal<'a, K, V> = iter::FlatMap< + btree_map::IterMut<'a, K, OneOrMore>, + IterMutInternalIntermediate<'a, K, V>, + for<'b> fn( + (&'b K, &'b mut OneOrMore), + ) -> IterMutInternalIntermediate<'b, K, V>, + >; + pub struct IterMut<'a, K, V> { + iter: IterMutInternal<'a, K, V>, + size: usize, + } + pub type IntoIterInternalIntermediate = + iter::Zip, one_or_more::IntoIter>; + pub type IntoIterInternal = iter::FlatMap< + btree_map::IntoIter>, + IntoIterInternalIntermediate, + fn((K, OneOrMore)) -> IntoIterInternalIntermediate, + >; + pub struct IntoIter { + iter: IntoIterInternal, + size: usize, + } + + impl DupTreeMap { + pub fn new() -> Self + where + K: Ord, + { + 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), + } + self.size += 1; + } + + pub fn len(&self) -> usize { + self.size + } + pub fn is_empty(&self) -> bool { + self.size == 0 + } + + pub fn iter(&self) -> Iter<'_, K, V> + where + K: Ord, + { + fn foo<'a, K, V>( + (k, oom): (&'a K, &'a OneOrMore), + ) -> IterInternalIntermediate<'a, K, V> { + iter::repeat(k).zip(oom.iter()) + } + Iter { + iter: self.map.iter().flat_map(foo), + size: 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), + ) -> IterMutInternalIntermediate<'a, K, V> { + iter::repeat(k).zip(oom.iter_mut()) + } + IterMut { + iter: self.map.iter_mut().flat_map(foo), + size: self.size, + } + } + } + + impl Default for DupTreeMap + where + K: Ord, + { + fn default() -> Self { + Self::new() + } + } + + impl IntoIterator for DupTreeMap + where + K: Ord + Clone, + { + type Item = (K, V); + type IntoIter = IntoIter; + + fn into_iter(self) -> Self::IntoIter { + fn foo( + (k, oom): (K, OneOrMore), + ) -> IntoIterInternalIntermediate + where + K: Clone, + { + iter::repeat(k).zip(oom.into_iter()) + } + IntoIter { + iter: self.map.into_iter().flat_map(foo), + size: self.size, + } + } + } + + impl<'a, K, V> IntoIterator for &'a DupTreeMap + where + K: Ord, + { + type Item = (&'a K, &'a V); + type IntoIter = Iter<'a, K, V>; + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } + } + + impl<'a, K, V> IntoIterator for &'a mut DupTreeMap + where + K: Ord, + { + type Item = (&'a K, &'a mut V); + type IntoIter = IterMut<'a, K, V>; + + fn into_iter(self) -> Self::IntoIter { + self.iter_mut() + } + } + + impl iter::FromIterator<(K, V)> for DupTreeMap + where + K: Ord, + { + fn from_iter(iter: T) -> Self + where + T: IntoIterator, + { + let mut map = DupTreeMap::new(); + for (k, v) in iter { + map.insert(k, v); + } + 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::DupTreeMap; + use std::iter; + + #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] + pub struct DupTreeSet { + map: DupTreeMap, + } + + pub type Iter<'a, K> = iter::Map< + super::dup_tree_map::Iter<'a, K, ()>, + for<'b> fn((&'b K, &'b ())) -> &'b K, + >; + pub type IntoIter = + iter::Map, fn((K, ())) -> K>; + + impl DupTreeSet { + pub fn new() -> Self + where + K: Ord, + { + DupTreeSet { + map: DupTreeMap::new(), + } + } + + pub fn len(&self) -> usize { + self.map.len() + } + pub fn is_empty(&self) -> bool { + 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) + } + } + + impl Default for DupTreeSet + where + K: Ord, + { + fn default() -> Self { + Self::new() + } + } + + impl IntoIterator for DupTreeSet + where + K: Ord + Clone, + { + type Item = K; + type IntoIter = IntoIter; + + fn into_iter(self) -> Self::IntoIter { + fn foo((k, ()): (K, ())) -> K { + k + } + self.map.into_iter().map(foo) + } + } + + impl<'a, K> IntoIterator for &'a DupTreeSet + where + K: Ord, + { + type Item = &'a K; + type IntoIter = Iter<'a, K>; + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } + } + + impl iter::FromIterator for DupTreeSet + where + K: Ord, + { + fn from_iter(iter: T) -> Self + where + T: IntoIterator, + { + let map = iter.into_iter().map(|k| (k, ())).collect(); + DupTreeSet { map } + } + } +} -- cgit v1.2.3