diff options
Diffstat (limited to 'dhall/src/syntax/ast')
| -rw-r--r-- | dhall/src/syntax/ast/expr.rs | 134 | ||||
| -rw-r--r-- | dhall/src/syntax/ast/map.rs | 282 | ||||
| -rw-r--r-- | dhall/src/syntax/ast/mod.rs | 1 | ||||
| -rw-r--r-- | dhall/src/syntax/ast/visitor.rs | 100 |
4 files changed, 57 insertions, 460 deletions
diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs index 9e935dc..9d216a7 100644 --- a/dhall/src/syntax/ast/expr.rs +++ b/dhall/src/syntax/ast/expr.rs @@ -1,8 +1,9 @@ use std::collections::BTreeMap; +use crate::builtins::Builtin; use crate::error::Error; +use crate::operations::OpKind; use crate::semantics::Universe; -use crate::syntax::map::{DupTreeMap, DupTreeSet}; use crate::syntax::visitor; use crate::syntax::*; @@ -36,74 +37,6 @@ impl Const { #[derive(Debug, Clone, PartialEq, Eq, Hash)] pub struct V(pub Label, pub usize); -// Definition order must match precedence order for -// pretty-printing to work correctly -#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] -pub enum BinOp { - /// `x ? y` - ImportAlt, - /// `x || y` - BoolOr, - /// `x + y` - NaturalPlus, - /// `x ++ y` - TextAppend, - /// `x # y` - ListAppend, - /// `x && y` - BoolAnd, - /// `x ∧ y` - RecursiveRecordMerge, - /// `x ⫽ y` - RightBiasedRecordMerge, - /// `x ⩓ y` - RecursiveRecordTypeMerge, - /// `x * y` - NaturalTimes, - /// `x == y` - BoolEQ, - /// `x != y` - BoolNE, - /// x === y - Equivalence, -} - -/// Built-ins -#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] -pub enum Builtin { - Bool, - Natural, - Integer, - Double, - Text, - List, - Optional, - OptionalNone, - NaturalBuild, - NaturalFold, - NaturalIsZero, - NaturalEven, - NaturalOdd, - NaturalToInteger, - NaturalShow, - NaturalSubtract, - IntegerToDouble, - IntegerShow, - IntegerNegate, - IntegerClamp, - DoubleShow, - ListBuild, - ListFold, - ListLength, - ListHead, - ListLast, - ListIndexed, - ListReverse, - OptionalFold, - OptionalBuild, - TextShow, -} - // Each node carries an annotation. #[derive(Debug, Clone)] pub struct Expr { @@ -132,57 +65,44 @@ pub enum NumKind { // smart pointers. #[derive(Debug, Clone, PartialEq, Eq, Hash)] pub enum ExprKind<SubExpr> { + /// `Type`, `Kind` and `Sort` Const(Const), + /// Numbers and booleans Num(NumKind), - /// `x` - /// `x@n` - Var(V), - /// `λ(x : A) -> b` - Lam(Label, SubExpr, SubExpr), - /// `A -> B` - /// `∀(x : A) -> B` - Pi(Label, SubExpr, SubExpr), - /// `f a` - App(SubExpr, SubExpr), - /// `let x = r in e` - /// `let x : t = r in e` - Let(Label, Option<SubExpr>, SubExpr, SubExpr), - /// `x : t` - Annot(SubExpr, SubExpr), - /// `assert : t` - Assert(SubExpr), - /// Built-in values + /// Built-in functions and types Builtin(Builtin), - // Binary operations - BinOp(BinOp, SubExpr, SubExpr), - /// `if x then y else z` - BoolIf(SubExpr, SubExpr, SubExpr), /// `"Some ${interpolated} text"` TextLit(InterpolatedText<SubExpr>), + /// `Some e` + SomeLit(SubExpr), /// `[] : t` EmptyListLit(SubExpr), /// `[x, y, z]` NEListLit(Vec<SubExpr>), - /// `Some e` - SomeLit(SubExpr), /// `{ k1 : t1, k2 : t1 }` - RecordType(DupTreeMap<Label, SubExpr>), + RecordType(BTreeMap<Label, SubExpr>), /// `{ k1 = v1, k2 = v2 }` RecordLit(BTreeMap<Label, SubExpr>), /// `< k1 : t1, k2 >` - UnionType(DupTreeMap<Label, Option<SubExpr>>), - /// `merge x y : t` - Merge(SubExpr, SubExpr, Option<SubExpr>), - /// `toMap x : t` - ToMap(SubExpr, Option<SubExpr>), - /// `e.x` - Field(SubExpr, Label), - /// `e.{ x, y, z }` - Projection(SubExpr, DupTreeSet<Label>), - /// `e.(t)` - ProjectionByExpr(SubExpr, SubExpr), - /// `x::y` - Completion(SubExpr, SubExpr), + UnionType(BTreeMap<Label, Option<SubExpr>>), + + /// `x`, `x@n` + Var(V), + /// `λ(x : A) -> b` + Lam(Label, SubExpr, SubExpr), + /// `A -> B`, `∀(x : A) -> B` + Pi(Label, SubExpr, SubExpr), + /// `let x : t = r in e` + Let(Label, Option<SubExpr>, SubExpr, SubExpr), + + /// Operations + Op(OpKind<SubExpr>), + + /// `x : t` + Annot(SubExpr, SubExpr), + /// `assert : t` + Assert(SubExpr), + /// `./some/path` Import(Import<SubExpr>), } diff --git a/dhall/src/syntax/ast/map.rs b/dhall/src/syntax/ast/map.rs deleted file mode 100644 index 7a88204..0000000 --- a/dhall/src/syntax/ast/map.rs +++ /dev/null @@ -1,282 +0,0 @@ -/// A sorted map that allows multiple values for each key. -pub use dup_tree_map::DupTreeMap; -pub use dup_tree_set::DupTreeSet; - -mod known_size_iter { - pub struct KnownSizeIterator<I> { - pub iter: I, - pub size: usize, - } - - impl<I: Iterator> Iterator for KnownSizeIterator<I> { - type Item = I::Item; - - 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<I: Iterator> iter::TrustedLen for KnownSizeIterator<I> {} -} - -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::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: DupTreeMapInternal<K, V>, - size: usize, - } - - // 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, - >; - 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>, - >, - >; - - fn zip_repeat<K, I>((k, iter): (K, I)) -> ZipRepeatIter<(K, I)> - where - K: Clone, - I: IntoIterator, - { - iter::repeat(k).zip(iter.into_iter()) - } - - 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, - } - } - - 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) { - self.map.entry(key).or_default().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> { - make_map_iter(&self.map, self.size) - } - - pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { - make_map_iter(&mut self.map, self.size) - } - } - - impl<K, V> Default for DupTreeMap<K, V> - where - K: Ord, - { - fn default() -> Self { - Self::new() - } - } - - impl<K, V> IntoIterator for DupTreeMap<K, V> - where - K: Ord + Clone, - { - type Item = (K, V); - type IntoIter = IntoIter<K, V>; - - fn into_iter(self) -> Self::IntoIter { - make_map_iter(self.map, self.size) - } - } - - impl<'a, K, V> IntoIterator for &'a DupTreeMap<K, V> - where - K: Ord + 'a, - V: 'a, - { - 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<K, V> - where - K: Ord + 'a, - V: 'a, - { - type Item = (&'a K, &'a mut V); - type IntoIter = IterMut<'a, K, V>; - - fn into_iter(self) -> Self::IntoIter { - self.iter_mut() - } - } - - impl<K, V> iter::FromIterator<(K, V)> for DupTreeMap<K, V> - where - K: Ord, - { - fn from_iter<T>(iter: T) -> Self - where - T: IntoIterator<Item = (K, V)>, - { - let mut map = DupTreeMap::new(); - for (k, v) in iter { - map.insert(k, v); - } - map - } - } -} - -mod dup_tree_set { - use super::tuple::Tuple; - use super::DupTreeMap; - use std::iter; - - #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] - pub struct DupTreeSet<K> { - map: DupTreeMap<K, ()>, - } - - type DupTreeSetIter<M> = iter::Map< - <M as IntoIterator>::IntoIter, - fn( - <M as IntoIterator>::Item, - ) -> <<M as IntoIterator>::Item as Tuple>::First, - >; - - 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(), - } - } - - pub fn len(&self) -> usize { - self.map.len() - } - pub fn is_empty(&self) -> bool { - self.map.is_empty() - } - - pub fn iter(&self) -> Iter<'_, K> { - self.map.iter().map(drop_second) - } - } - - impl<K> Default for DupTreeSet<K> - where - K: Ord, - { - fn default() -> Self { - Self::new() - } - } - - impl<K> IntoIterator for DupTreeSet<K> - where - K: Ord + Clone, - { - type Item = K; - type IntoIter = IntoIter<K>; - - fn into_iter(self) -> Self::IntoIter { - self.map.into_iter().map(drop_second) - } - } - - impl<'a, K> IntoIterator for &'a DupTreeSet<K> - where - K: Ord + 'a, - { - type Item = &'a K; - type IntoIter = Iter<'a, K>; - - fn into_iter(self) -> Self::IntoIter { - self.iter() - } - } - - impl<K> iter::FromIterator<K> for DupTreeSet<K> - where - K: Ord, - { - fn from_iter<T>(iter: T) -> Self - where - T: IntoIterator<Item = K>, - { - let map = iter.into_iter().map(|k| (k, ())).collect(); - DupTreeSet { map } - } - } -} diff --git a/dhall/src/syntax/ast/mod.rs b/dhall/src/syntax/ast/mod.rs index 1950154..c341af7 100644 --- a/dhall/src/syntax/ast/mod.rs +++ b/dhall/src/syntax/ast/mod.rs @@ -8,5 +8,4 @@ mod span; pub use span::*; mod text; pub use text::*; -pub mod map; pub mod visitor; diff --git a/dhall/src/syntax/ast/visitor.rs b/dhall/src/syntax/ast/visitor.rs index 0a0c5ef..7244d0a 100644 --- a/dhall/src/syntax/ast/visitor.rs +++ b/dhall/src/syntax/ast/visitor.rs @@ -1,22 +1,13 @@ +use itertools::Itertools; use std::iter::FromIterator; use crate::syntax::*; -fn vec<'a, T, U, Err>( - x: &'a [T], - f: impl FnMut(&'a T) -> Result<U, Err>, -) -> Result<Vec<U>, Err> { - x.iter().map(f).collect() -} - fn opt<'a, T, U, Err>( x: &'a Option<T>, f: impl FnOnce(&'a T) -> Result<U, Err>, ) -> Result<Option<U>, Err> { - Ok(match x { - Some(x) => Some(f(x)?), - None => None, - }) + x.as_ref().map(f).transpose() } fn dupmap<'a, SE1, SE2, T, Err>( @@ -30,27 +21,6 @@ where x.into_iter().map(|(k, x)| Ok((k.clone(), f(x)?))).collect() } -fn optdupmap<'a, SE1, SE2, T, Err>( - x: impl IntoIterator<Item = (&'a Label, &'a Option<SE1>)>, - mut f: impl FnMut(&'a SE1) -> Result<SE2, Err>, -) -> Result<T, Err> -where - SE1: 'a, - T: FromIterator<(Label, Option<SE2>)>, -{ - x.into_iter() - .map(|(k, x)| { - Ok(( - k.clone(), - match x { - Some(x) => Some(f(x)?), - None => None, - }, - )) - }) - .collect() -} - pub fn visit_ref<'a, F, SE1, SE2, Err>( input: &'a ExprKind<SE1>, mut f: F, @@ -60,54 +30,44 @@ where { // Can't use closures because of borrowing rules macro_rules! expr { + () => { + |e| Ok(expr!(e)) + }; ($e:expr) => { - f(None, $e) + f(None, $e)? }; ($l:expr, $e:expr) => { - f(Some($l), $e) + f(Some($l), $e)? + }; + } + macro_rules! opt { + () => { + |e| Ok(opt!(e)) + }; + ($e:expr) => { + opt($e, |e| Ok(expr!(e)))? }; } use crate::syntax::ExprKind::*; Ok(match input { Var(v) => Var(v.clone()), - Lam(l, t, e) => { - let t = expr!(t)?; - let e = expr!(l, e)?; - Lam(l.clone(), t, e) - } - Pi(l, t, e) => { - let t = expr!(t)?; - let e = expr!(l, e)?; - Pi(l.clone(), t, e) - } - Let(l, t, a, e) => { - let t = opt(t, &mut |e| expr!(e))?; - let a = expr!(a)?; - let e = expr!(l, e)?; - Let(l.clone(), t, a, e) - } - App(f, a) => App(expr!(f)?, expr!(a)?), - Annot(x, t) => Annot(expr!(x)?, expr!(t)?), + Lam(l, t, e) => Lam(l.clone(), expr!(t), expr!(l, e)), + Pi(l, t, e) => Pi(l.clone(), expr!(t), expr!(l, e)), + Let(l, t, a, e) => Let(l.clone(), opt!(t), expr!(a), expr!(l, e)), Const(k) => Const(*k), - Builtin(v) => Builtin(*v), Num(n) => Num(n.clone()), - TextLit(t) => TextLit(t.traverse_ref(|e| expr!(e))?), - BinOp(o, x, y) => BinOp(*o, expr!(x)?, expr!(y)?), - BoolIf(b, t, f) => BoolIf(expr!(b)?, expr!(t)?, expr!(f)?), - EmptyListLit(t) => EmptyListLit(expr!(t)?), - NEListLit(es) => NEListLit(vec(es, |e| expr!(e))?), - SomeLit(e) => SomeLit(expr!(e)?), - RecordType(kts) => RecordType(dupmap(kts, |e| expr!(e))?), - RecordLit(kvs) => RecordLit(dupmap(kvs, |e| expr!(e))?), - UnionType(kts) => UnionType(optdupmap(kts, |e| expr!(e))?), - Merge(x, y, t) => Merge(expr!(x)?, expr!(y)?, opt(t, |e| expr!(e))?), - ToMap(x, t) => ToMap(expr!(x)?, opt(t, |e| expr!(e))?), - Field(e, l) => Field(expr!(e)?, l.clone()), - Projection(e, ls) => Projection(expr!(e)?, ls.clone()), - ProjectionByExpr(e, x) => ProjectionByExpr(expr!(e)?, expr!(x)?), - Completion(e, x) => Completion(expr!(e)?, expr!(x)?), - Assert(e) => Assert(expr!(e)?), - Import(i) => Import(i.traverse_ref(|e| expr!(e))?), + Builtin(v) => Builtin(*v), + TextLit(t) => TextLit(t.traverse_ref(expr!())?), + SomeLit(e) => SomeLit(expr!(e)), + EmptyListLit(t) => EmptyListLit(expr!(t)), + NEListLit(es) => NEListLit(es.iter().map(expr!()).try_collect()?), + RecordType(kts) => RecordType(dupmap(kts, expr!())?), + RecordLit(kvs) => RecordLit(dupmap(kvs, expr!())?), + UnionType(kts) => UnionType(dupmap(kts, opt!())?), + Op(op) => Op(op.traverse_ref(expr!())?), + Annot(x, t) => Annot(expr!(x), expr!(t)), + Assert(e) => Assert(expr!(e)), + Import(i) => Import(i.traverse_ref(expr!())?), }) } |