diff options
Diffstat (limited to 'dhall/src')
| -rw-r--r-- | dhall/src/lib.rs | 4 | ||||
| -rw-r--r-- | dhall/src/syntax/core/context.rs | 80 | ||||
| -rw-r--r-- | dhall/src/syntax/core/expr.rs | 377 | ||||
| -rw-r--r-- | dhall/src/syntax/core/import.rs | 130 | ||||
| -rw-r--r-- | dhall/src/syntax/core/label.rs | 34 | ||||
| -rw-r--r-- | dhall/src/syntax/core/map.rs | 394 | ||||
| -rw-r--r-- | dhall/src/syntax/core/mod.rs | 13 | ||||
| -rw-r--r-- | dhall/src/syntax/core/span.rs | 81 | ||||
| -rw-r--r-- | dhall/src/syntax/core/text.rs | 181 | ||||
| -rw-r--r-- | dhall/src/syntax/core/visitor.rs | 360 | ||||
| -rw-r--r-- | dhall/src/syntax/mod.rs | 15 | ||||
| -rw-r--r-- | dhall/src/syntax/parser.rs | 942 | ||||
| -rw-r--r-- | dhall/src/syntax/printer.rs | 500 |
13 files changed, 3108 insertions, 3 deletions
diff --git a/dhall/src/lib.rs b/dhall/src/lib.rs index 86af98f..0991375 100644 --- a/dhall/src/lib.rs +++ b/dhall/src/lib.rs @@ -13,6 +13,4 @@ mod tests; pub mod semantics; -pub mod syntax { - pub use dhall_syntax::*; -} +pub mod syntax; diff --git a/dhall/src/syntax/core/context.rs b/dhall/src/syntax/core/context.rs new file mode 100644 index 0000000..6844baa --- /dev/null +++ b/dhall/src/syntax/core/context.rs @@ -0,0 +1,80 @@ +use std::cmp::Eq; +use std::collections::HashMap; +use std::hash::Hash; + +/// A `(Context a)` associates `Text` labels with values of type `a` +/// +/// The `Context` is used for type-checking when `(a = Expr)` +/// +/// * You create a `Context` using `empty` and `insert` +/// * You transform a `Context` using `fmap` +/// * You consume a `Context` using `lookup` and `toList` +/// +/// The difference between a `Context` and a `Map` is that a `Context` lets you +/// have multiple ordered occurrences of the same key and you can query for the +/// `n`th occurrence of a given key. +/// +#[derive(Debug, Clone)] +pub struct Context<K: Eq + Hash, T>(HashMap<K, Vec<T>>); + +impl<K: Hash + Eq + Clone, T> Context<K, T> { + /// An empty context with no key-value pairs + pub fn new() -> Self { + Context(HashMap::new()) + } + + /// Look up a key by name and index + /// + /// ```c + /// lookup _ _ empty = Nothing + /// lookup k 0 (insert k v c) = Just v + /// lookup k n (insert k v c) = lookup k (n - 1) c -- 1 <= n + /// lookup k n (insert j v c) = lookup k n c -- k /= j + /// ``` + pub fn lookup<'a>(&'a self, k: &K, n: usize) -> Option<&'a T> { + self.0.get(k).and_then(|v| { + if n < v.len() { + v.get(v.len() - 1 - n) + } else { + None + } + }) + } + + pub fn map<U, F: Fn(&K, &T) -> U>(&self, f: F) -> Context<K, U> { + Context( + self.0 + .iter() + .map(|(k, vs)| { + ((*k).clone(), vs.iter().map(|v| f(k, v)).collect()) + }) + .collect(), + ) + } + + pub fn lookup_all<'a>(&'a self, k: &K) -> impl Iterator<Item = &T> { + self.0.get(k).into_iter().flat_map(|v| v.iter()) + } + + pub fn iter(&self) -> impl Iterator<Item = (&K, &T)> { + self.0 + .iter() + .flat_map(|(k, vs)| vs.iter().map(move |v| (k, v))) + } + + pub fn iter_keys(&self) -> impl Iterator<Item = (&K, &Vec<T>)> { + self.0.iter() + } +} + +impl<K: Hash + Eq + Clone, T: Clone> Context<K, T> { + /// Add a key-value pair to the `Context` + pub fn insert(&self, k: K, v: T) -> Self { + let mut ctx = (*self).clone(); + { + let m = ctx.0.entry(k).or_insert_with(Vec::new); + m.push(v); + } + ctx + } +} diff --git a/dhall/src/syntax/core/expr.rs b/dhall/src/syntax/core/expr.rs new file mode 100644 index 0000000..7972283 --- /dev/null +++ b/dhall/src/syntax/core/expr.rs @@ -0,0 +1,377 @@ +use crate::syntax::map::{DupTreeMap, DupTreeSet}; +use crate::syntax::visitor::{self, ExprFMutVisitor, ExprFVisitor}; +use crate::syntax::*; + +pub type Integer = isize; +pub type Natural = usize; +pub type Double = NaiveDouble; + +pub fn trivial_result<T>(x: Result<T, !>) -> T { + match x { + Ok(x) => x, + Err(e) => e, + } +} + +/// Double with bitwise equality +#[derive(Debug, Copy, Clone)] +pub struct NaiveDouble(f64); + +impl PartialEq for NaiveDouble { + fn eq(&self, other: &Self) -> bool { + self.0.to_bits() == other.0.to_bits() + } +} + +impl Eq for NaiveDouble {} + +impl std::hash::Hash for NaiveDouble { + fn hash<H>(&self, state: &mut H) + where + H: std::hash::Hasher, + { + self.0.to_bits().hash(state) + } +} + +impl From<f64> for NaiveDouble { + fn from(x: f64) -> Self { + NaiveDouble(x) + } +} + +impl From<NaiveDouble> for f64 { + fn from(x: NaiveDouble) -> f64 { + x.0 + } +} + +/// Constants for a pure type system +#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] +pub enum Const { + Type, + Kind, + Sort, +} + +/// Bound variable +/// +/// The `Label` field is the variable's name (i.e. \"`x`\"). +/// The `Int` field is a DeBruijn index. +/// See dhall-lang/standard/semantics.md for details +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct V<Label>(pub Label, pub usize); + +// This is only for the specific `Label` type, not generic +impl From<Label> for V<Label> { + fn from(x: Label) -> V<Label> { + V(x, 0) + } +} +impl<'a> From<&'a Label> for V<Label> { + fn from(x: &'a Label) -> V<Label> { + V(x.clone(), 0) + } +} + +// 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, + DoubleShow, + ListBuild, + ListFold, + ListLength, + ListHead, + ListLast, + ListIndexed, + ListReverse, + OptionalFold, + OptionalBuild, + TextShow, +} + +// Each node carries an annotation. +#[derive(Debug, Clone)] +pub struct Expr<Embed>(Box<(RawExpr<Embed>, Span)>); + +pub type RawExpr<Embed> = ExprF<Expr<Embed>, Embed>; + +impl<Embed: PartialEq> std::cmp::PartialEq for Expr<Embed> { + fn eq(&self, other: &Self) -> bool { + self.0.as_ref().0 == other.0.as_ref().0 + } +} + +impl<Embed: Eq> std::cmp::Eq for Expr<Embed> {} + +impl<Embed: std::hash::Hash> std::hash::Hash for Expr<Embed> { + fn hash<H>(&self, state: &mut H) + where + H: std::hash::Hasher, + { + (self.0).0.hash(state) + } +} + +/// Syntax tree for expressions +// Having the recursion out of the enum definition enables writing +// much more generic code and improves pattern-matching behind +// smart pointers. +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub enum ExprF<SubExpr, Embed> { + Const(Const), + /// `x` + /// `x@n` + Var(V<Label>), + /// `λ(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 + Builtin(Builtin), + // Binary operations + BinOp(BinOp, SubExpr, SubExpr), + /// `True` + BoolLit(bool), + /// `if x then y else z` + BoolIf(SubExpr, SubExpr, SubExpr), + /// `1` + NaturalLit(Natural), + /// `+2` + IntegerLit(Integer), + /// `3.24` + DoubleLit(Double), + /// `"Some ${interpolated} text"` + TextLit(InterpolatedText<SubExpr>), + /// `[] : t` + EmptyListLit(SubExpr), + /// `[x, y, z]` + NEListLit(Vec<SubExpr>), + /// `Some e` + SomeLit(SubExpr), + /// `{ k1 : t1, k2 : t1 }` + RecordType(DupTreeMap<Label, SubExpr>), + /// `{ k1 = v1, k2 = v2 }` + RecordLit(DupTreeMap<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), + /// `./some/path` + Import(Import<SubExpr>), + /// Embeds the result of resolving an import + Embed(Embed), +} + +impl<SE, E> ExprF<SE, E> { + pub fn traverse_ref_with_special_handling_of_binders<'a, SE2, Err>( + &'a self, + visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>, + visit_under_binder: impl FnOnce(&'a Label, &'a SE) -> Result<SE2, Err>, + ) -> Result<ExprF<SE2, E>, Err> + where + E: Clone, + { + visitor::TraverseRefWithBindersVisitor { + visit_subexpr, + visit_under_binder, + } + .visit(self) + } + + fn traverse_ref<'a, SE2, Err>( + &'a self, + visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>, + ) -> Result<ExprF<SE2, E>, Err> + where + E: Clone, + { + visitor::TraverseRefVisitor { visit_subexpr }.visit(self) + } + + fn traverse_mut<'a, Err>( + &'a mut self, + visit_subexpr: impl FnMut(&'a mut SE) -> Result<(), Err>, + ) -> Result<(), Err> { + visitor::TraverseMutVisitor { visit_subexpr }.visit(self) + } + + pub fn map_ref_with_special_handling_of_binders<'a, SE2>( + &'a self, + mut map_subexpr: impl FnMut(&'a SE) -> SE2, + mut map_under_binder: impl FnMut(&'a Label, &'a SE) -> SE2, + ) -> ExprF<SE2, E> + where + E: Clone, + { + trivial_result(self.traverse_ref_with_special_handling_of_binders( + |x| Ok(map_subexpr(x)), + |l, x| Ok(map_under_binder(l, x)), + )) + } + + pub fn map_ref<'a, SE2>( + &'a self, + mut map_subexpr: impl FnMut(&'a SE) -> SE2, + ) -> ExprF<SE2, E> + where + E: Clone, + { + trivial_result(self.traverse_ref(|x| Ok(map_subexpr(x)))) + } + + pub fn map_mut<'a>(&'a mut self, mut map_subexpr: impl FnMut(&'a mut SE)) { + trivial_result(self.traverse_mut(|x| Ok(map_subexpr(x)))) + } +} + +impl<E> Expr<E> { + pub fn as_ref(&self) -> &RawExpr<E> { + &self.0.as_ref().0 + } + pub fn as_mut(&mut self) -> &mut RawExpr<E> { + &mut self.0.as_mut().0 + } + pub fn span(&self) -> Span { + self.0.as_ref().1.clone() + } + + pub fn new(x: RawExpr<E>, n: Span) -> Self { + Expr(Box::new((x, n))) + } + + pub fn rewrap<E2>(&self, x: RawExpr<E2>) -> Expr<E2> { + Expr(Box::new((x, (self.0).1.clone()))) + } + + pub fn traverse_resolve_mut<Err, F1>( + &mut self, + f: &mut F1, + ) -> Result<(), Err> + where + E: Clone, + F1: FnMut(Import<Expr<E>>) -> Result<E, Err>, + { + match self.as_mut() { + ExprF::BinOp(BinOp::ImportAlt, l, r) => { + let garbage_expr = ExprF::BoolLit(false); + let new_self = if l.traverse_resolve_mut(f).is_ok() { + l + } else { + r.traverse_resolve_mut(f)?; + r + }; + *self.as_mut() = + std::mem::replace(new_self.as_mut(), garbage_expr); + } + _ => { + self.as_mut().traverse_mut(|e| e.traverse_resolve_mut(f))?; + if let ExprF::Import(import) = self.as_mut() { + let garbage_import = Import { + mode: ImportMode::Code, + location: ImportLocation::Missing, + hash: None, + }; + // Move out of &mut import + let import = std::mem::replace(import, garbage_import); + *self.as_mut() = ExprF::Embed(f(import)?); + } + } + } + Ok(()) + } +} + +/// Add an isize to an usize +/// Panics on over/underflow +fn add_ui(u: usize, i: isize) -> Option<usize> { + Some(if i < 0 { + u.checked_sub(i.checked_neg()? as usize)? + } else { + u.checked_add(i as usize)? + }) +} + +impl<Label: PartialEq + Clone> V<Label> { + pub fn shift(&self, delta: isize, var: &V<Label>) -> Option<Self> { + let V(x, n) = var; + let V(y, m) = self; + Some(if x == y && n <= m { + V(y.clone(), add_ui(*m, delta)?) + } else { + V(y.clone(), *m) + }) + } + + pub fn over_binder(&self, x: &Label) -> Option<Self> { + self.shift(-1, &V(x.clone(), 0)) + } +} diff --git a/dhall/src/syntax/core/import.rs b/dhall/src/syntax/core/import.rs new file mode 100644 index 0000000..da3e99b --- /dev/null +++ b/dhall/src/syntax/core/import.rs @@ -0,0 +1,130 @@ +/// The beginning of a file path which anchors subsequent path components +#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] +pub enum FilePrefix { + /// Absolute path + Absolute, + /// Path relative to . + Here, + /// Path relative to .. + Parent, + /// Path relative to ~ + Home, +} + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct FilePath { + pub file_path: Vec<String>, +} + +/// The location of import (i.e. local vs. remote vs. environment) +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub enum ImportLocation<SubExpr> { + Local(FilePrefix, FilePath), + Remote(URL<SubExpr>), + Env(String), + Missing, +} + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct URL<SubExpr> { + pub scheme: Scheme, + pub authority: String, + pub path: FilePath, + pub query: Option<String>, + pub headers: Option<SubExpr>, +} + +#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] +pub enum Scheme { + HTTP, + HTTPS, +} + +/// How to interpret the import's contents (i.e. as Dhall code or raw text) +#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)] +pub enum ImportMode { + Code, + RawText, + Location, +} + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub enum Hash { + SHA256(Vec<u8>), +} + +/// Reference to an external resource +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct Import<SubExpr> { + pub mode: ImportMode, + pub location: ImportLocation<SubExpr>, + pub hash: Option<Hash>, +} + +impl<SE> URL<SE> { + pub fn traverse_ref<'a, Err, SE2>( + &'a self, + f: impl FnOnce(&'a SE) -> Result<SE2, Err>, + ) -> Result<URL<SE2>, Err> { + let headers = self.headers.as_ref().map(f).transpose()?; + Ok(URL { + scheme: self.scheme, + authority: self.authority.clone(), + path: self.path.clone(), + query: self.query.clone(), + headers, + }) + } + pub fn traverse_mut<'a, Err>( + &'a mut self, + f: impl FnOnce(&'a mut SE) -> Result<(), Err>, + ) -> Result<(), Err> { + if let Some(header) = &mut self.headers { + f(header)?; + } + Ok(()) + } +} + +impl<SE> ImportLocation<SE> { + pub fn traverse_ref<'a, Err, SE2>( + &'a self, + f: impl FnOnce(&'a SE) -> Result<SE2, Err>, + ) -> Result<ImportLocation<SE2>, Err> { + use ImportLocation::*; + Ok(match self { + Local(prefix, path) => Local(*prefix, path.clone()), + Remote(url) => Remote(url.traverse_ref(f)?), + Env(env) => Env(env.clone()), + Missing => Missing, + }) + } + pub fn traverse_mut<'a, Err>( + &'a mut self, + f: impl FnOnce(&'a mut SE) -> Result<(), Err>, + ) -> Result<(), Err> { + if let ImportLocation::Remote(url) = self { + url.traverse_mut(f)?; + } + Ok(()) + } +} + +impl<SE> Import<SE> { + pub fn traverse_ref<'a, Err, SE2>( + &'a self, + f: impl FnOnce(&'a SE) -> Result<SE2, Err>, + ) -> Result<Import<SE2>, Err> { + Ok(Import { + mode: self.mode, + location: self.location.traverse_ref(f)?, + hash: self.hash.clone(), + }) + } + pub fn traverse_mut<'a, Err>( + &'a mut self, + f: impl FnOnce(&'a mut SE) -> Result<(), Err>, + ) -> Result<(), Err> { + self.location.traverse_mut(f) + } +} diff --git a/dhall/src/syntax/core/label.rs b/dhall/src/syntax/core/label.rs new file mode 100644 index 0000000..43c3f53 --- /dev/null +++ b/dhall/src/syntax/core/label.rs @@ -0,0 +1,34 @@ +use std::rc::Rc; + +// The type for labels throughout the AST +// It owns the data because otherwise lifetimes would make recursive imports impossible +#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)] +pub struct Label(Rc<str>); + +impl From<String> for Label { + fn from(s: String) -> Self { + let s: &str = &s; + Label(s.into()) + } +} + +impl<'a> From<&'a str> for Label { + fn from(s: &'a str) -> Self { + Label(Rc::from(s)) + } +} + +impl From<&Label> for String { + fn from(x: &Label) -> String { + x.0.as_ref().to_owned() + } +} + +impl Label { + pub fn from_str(s: &str) -> Label { + Label(s.into()) + } + pub fn as_ref(&self) -> &str { + self.0.as_ref() + } +} diff --git a/dhall/src/syntax/core/map.rs b/dhall/src/syntax/core/map.rs new file mode 100644 index 0000000..c4c6126 --- /dev/null +++ b/dhall/src/syntax/core/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<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 std::collections::{btree_map, BTreeMap}; + use std::iter; + + #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] + pub struct DupTreeMap<K, V> { + map: BTreeMap<K, OneOrMore<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>, + >; + 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>, + >; + pub struct IterMut<'a, K, V> { + iter: IterMutInternal<'a, K, V>, + size: usize, + } + 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, + } + + impl<K, V> DupTreeMap<K, V> { + 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<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_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, + } + } + } + + 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 { + 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, + } + } + } + + impl<'a, K, V> IntoIterator for &'a DupTreeMap<K, V> + 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<K, V> + 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<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 + } + } + + 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::DupTreeMap; + use std::iter; + + #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)] + pub struct DupTreeSet<K> { + 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, + >; + 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, + { + 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<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 { + fn foo<K>((k, ()): (K, ())) -> K { + k + } + self.map.into_iter().map(foo) + } + } + + impl<'a, K> IntoIterator for &'a DupTreeSet<K> + where + K: Ord, + { + 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/core/mod.rs b/dhall/src/syntax/core/mod.rs new file mode 100644 index 0000000..66bf229 --- /dev/null +++ b/dhall/src/syntax/core/mod.rs @@ -0,0 +1,13 @@ +mod expr; +pub use expr::*; +mod import; +pub use import::*; +mod label; +pub use label::*; +mod span; +pub use span::*; +mod text; +pub use text::*; +pub mod context; +pub mod map; +pub mod visitor; diff --git a/dhall/src/syntax/core/span.rs b/dhall/src/syntax/core/span.rs new file mode 100644 index 0000000..f9c7008 --- /dev/null +++ b/dhall/src/syntax/core/span.rs @@ -0,0 +1,81 @@ +use std::rc::Rc; + +/// A location in the source text +#[derive(Debug, Clone)] +pub struct ParsedSpan { + input: Rc<str>, + /// # Safety + /// + /// Must be a valid character boundary index into `input`. + start: usize, + /// # Safety + /// + /// Must be a valid character boundary index into `input`. + end: usize, +} + +#[derive(Debug, Clone)] +pub enum Span { + /// A location in the source text + Parsed(ParsedSpan), + /// For expressions obtained from decoding binary + Decoded, + /// For expressions constructed during normalization/typecheck + Artificial, +} + +impl Span { + pub(crate) fn make(input: Rc<str>, sp: pest::Span) -> Self { + Span::Parsed(ParsedSpan { + input, + start: sp.start(), + end: sp.end(), + }) + } + + /// Takes the union of the two spans, i.e. the range of input covered by the two spans plus any + /// input between them. Assumes that the spans come from the same input. Fails if one of the + /// spans does not point to an input location. + pub fn union(&self, other: &Span) -> Self { + use std::cmp::{max, min}; + use Span::*; + match (self, other) { + (Parsed(x), Parsed(y)) if Rc::ptr_eq(&x.input, &y.input) => { + Parsed(ParsedSpan { + input: x.input.clone(), + start: min(x.start, y.start), + end: max(x.end, y.end), + }) + } + _ => panic!( + "Tried to union incompatible spans: {:?} and {:?}", + self, other + ), + } + } + + /// Merges two spans assumed to point to a similar thing. If only one of them points to an + /// input location, use that one. + pub fn merge(&self, other: &Span) -> Self { + use Span::*; + match (self, other) { + (Parsed(x), _) | (_, Parsed(x)) => Parsed(x.clone()), + (Artificial, _) | (_, Artificial) => Artificial, + (Decoded, Decoded) => Decoded, + } + } + + pub fn error(&self, message: impl Into<String>) -> String { + use pest::error::{Error, ErrorVariant}; + use pest::Span; + let message: String = message.into(); + let span = match self { + self::Span::Parsed(span) => span, + _ => return format!("[unknown location] {}", message), + }; + let span = Span::new(&*span.input, span.start, span.end).unwrap(); + let err: ErrorVariant<!> = ErrorVariant::CustomError { message }; + let err = Error::new_from_span(err, span); + format!("{}", err) + } +} diff --git a/dhall/src/syntax/core/text.rs b/dhall/src/syntax/core/text.rs new file mode 100644 index 0000000..fb390ee --- /dev/null +++ b/dhall/src/syntax/core/text.rs @@ -0,0 +1,181 @@ +use std::iter::FromIterator; + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct InterpolatedText<SubExpr> { + head: String, + tail: Vec<(SubExpr, String)>, +} + +impl<SubExpr> From<(String, Vec<(SubExpr, String)>)> + for InterpolatedText<SubExpr> +{ + fn from(x: (String, Vec<(SubExpr, String)>)) -> Self { + InterpolatedText { + head: x.0, + tail: x.1, + } + } +} + +impl<SubExpr> From<String> for InterpolatedText<SubExpr> { + fn from(s: String) -> Self { + InterpolatedText { + head: s, + tail: vec![], + } + } +} + +#[derive(Debug, Clone, PartialEq, Eq)] +pub enum InterpolatedTextContents<SubExpr> { + Text(String), + Expr(SubExpr), +} + +impl<SubExpr> InterpolatedTextContents<SubExpr> { + pub fn is_empty(&self) -> bool { + use InterpolatedTextContents::{Expr, Text}; + match self { + Expr(_) => false, + Text(s) => s.is_empty(), + } + } + + pub fn traverse_ref<'a, SubExpr2, E, F>( + &'a self, + mut f: F, + ) -> Result<InterpolatedTextContents<SubExpr2>, E> + where + F: FnMut(&'a SubExpr) -> Result<SubExpr2, E>, + { + use InterpolatedTextContents::{Expr, Text}; + Ok(match self { + Expr(e) => Expr(f(e)?), + Text(s) => Text(s.clone()), + }) + } + pub fn traverse_mut<'a, E, F>(&'a mut self, mut f: F) -> Result<(), E> + where + F: FnMut(&'a mut SubExpr) -> Result<(), E>, + { + use InterpolatedTextContents::Expr; + if let Expr(e) = self { + f(e)?; + } + Ok(()) + } + pub fn map_ref<'a, SubExpr2, F>( + &'a self, + mut f: F, + ) -> InterpolatedTextContents<SubExpr2> + where + F: FnMut(&'a SubExpr) -> SubExpr2, + { + use InterpolatedTextContents::{Expr, Text}; + match self { + Expr(e) => Expr(f(e)), + Text(s) => Text(s.clone()), + } + } + pub fn map_mut<'a, F>(&'a mut self, mut f: F) + where + F: FnMut(&'a mut SubExpr), + { + use InterpolatedTextContents::Expr; + if let Expr(e) = self { + f(e); + } + } +} + +impl<SubExpr> InterpolatedText<SubExpr> { + pub fn len(&self) -> usize { + 1 + 2 * self.tail.len() + } + + pub fn head(&self) -> &str { + &self.head + } + + pub fn head_mut(&mut self) -> &mut String { + &mut self.head + } + + pub fn is_empty(&self) -> bool { + self.head.is_empty() && self.tail.is_empty() + } + + pub fn traverse_ref<'a, SubExpr2, E, F>( + &'a self, + mut f: F, + ) -> Result<InterpolatedText<SubExpr2>, E> + where + F: FnMut(&'a SubExpr) -> Result<SubExpr2, E>, + { + Ok(InterpolatedText { + head: self.head.clone(), + tail: self + .tail + .iter() + .map(|(e, s)| Ok((f(e)?, s.clone()))) + .collect::<Result<_, _>>()?, + }) + } + + pub fn traverse_mut<'a, E, F>(&'a mut self, mut f: F) -> Result<(), E> + where + F: FnMut(&'a mut SubExpr) -> Result<(), E>, + { + for (e, _) in &mut self.tail { + f(e)? + } + Ok(()) + } + + pub fn iter<'a>( + &'a self, + ) -> impl Iterator<Item = InterpolatedTextContents<&'a SubExpr>> + 'a { + use std::iter::once; + use InterpolatedTextContents::{Expr, Text}; + let exprs = self.tail.iter().map(|(e, _)| Expr(e)); + let texts = self.tail.iter().map(|(_, s)| Text(s.clone())); + once(Text(self.head.clone())).chain(itertools::interleave(exprs, texts)) + } + + pub fn into_iter( + self, + ) -> impl Iterator<Item = InterpolatedTextContents<SubExpr>> { + use std::iter::once; + use InterpolatedTextContents::{Expr, Text}; + once(Text(self.head)).chain( + self.tail + .into_iter() + .flat_map(|(e, s)| once(Expr(e)).chain(once(Text(s)))), + ) + } +} + +impl<SubExpr> FromIterator<InterpolatedTextContents<SubExpr>> + for InterpolatedText<SubExpr> +{ + fn from_iter<T>(iter: T) -> Self + where + T: IntoIterator<Item = InterpolatedTextContents<SubExpr>>, + { + let mut res = InterpolatedText { + head: String::new(), + tail: Vec::new(), + }; + let mut crnt_str = &mut res.head; + for x in iter.into_iter() { + match x { + InterpolatedTextContents::Text(s) => crnt_str.push_str(&s), + InterpolatedTextContents::Expr(e) => { + res.tail.push((e, String::new())); + crnt_str = &mut res.tail.last_mut().unwrap().1; + } + } + } + res + } +} diff --git a/dhall/src/syntax/core/visitor.rs b/dhall/src/syntax/core/visitor.rs new file mode 100644 index 0000000..b76d037 --- /dev/null +++ b/dhall/src/syntax/core/visitor.rs @@ -0,0 +1,360 @@ +use crate::syntax::*; +use std::iter::FromIterator; + +/// A visitor trait that can be used to traverse `ExprF`s. We need this pattern so that Rust lets +/// us have as much mutability as we can. +/// For example, `traverse_ref_with_special_handling_of_binders` cannot be made using only +/// `traverse_ref`, because `traverse_ref` takes a `FnMut` so we would need to pass multiple +/// mutable reverences to this argument to `traverse_ref`. But Rust's ownership system is all about +/// preventing exactly this ! So we have to be more clever. The visitor pattern allows us to have +/// only one mutable thing the whole time: the visitor itself. The visitor can then carry around +/// multiple closures or just one, and Rust is ok with either. See for example TraverseRefVisitor. +pub trait ExprFVisitor<'a, SE1, SE2, E1, E2>: Sized { + type Error; + + fn visit_subexpr(&mut self, subexpr: &'a SE1) -> Result<SE2, Self::Error>; + fn visit_embed(self, embed: &'a E1) -> Result<E2, Self::Error>; + + fn visit_subexpr_under_binder( + mut self, + _label: &'a Label, + subexpr: &'a SE1, + ) -> Result<SE2, Self::Error> { + self.visit_subexpr(subexpr) + } + + fn visit( + self, + input: &'a ExprF<SE1, E1>, + ) -> Result<ExprF<SE2, E2>, Self::Error> { + visit_ref(self, input) + } +} + +/// Like `ExprFVisitor`, but by mutable reference +pub trait ExprFMutVisitor<'a, SE, E>: Sized { + type Error; + + fn visit_subexpr(&mut self, subexpr: &'a mut SE) + -> Result<(), Self::Error>; + fn visit_embed(self, _embed: &'a mut E) -> Result<(), Self::Error> { + Ok(()) + } + + fn visit_subexpr_under_binder( + mut self, + _label: &'a mut Label, + subexpr: &'a mut SE, + ) -> Result<(), Self::Error> { + self.visit_subexpr(subexpr) + } + + fn visit(self, input: &'a mut ExprF<SE, E>) -> Result<(), Self::Error> { + visit_mut(self, input) + } +} + +fn visit_ref<'a, V, SE1, SE2, E1, E2>( + mut v: V, + input: &'a ExprF<SE1, E1>, +) -> Result<ExprF<SE2, E2>, V::Error> +where + V: ExprFVisitor<'a, SE1, SE2, E1, E2>, +{ + fn vec<'a, T, U, Err, F: FnMut(&'a T) -> Result<U, Err>>( + x: &'a [T], + f: F, + ) -> Result<Vec<U>, Err> { + x.iter().map(f).collect() + } + fn opt<'a, T, U, Err, F: FnOnce(&'a T) -> Result<U, Err>>( + x: &'a Option<T>, + f: F, + ) -> Result<Option<U>, Err> { + Ok(match x { + Some(x) => Some(f(x)?), + None => None, + }) + } + fn dupmap<'a, V, SE1, SE2, E1, E2, T>( + x: impl IntoIterator<Item = (&'a Label, &'a SE1)>, + mut v: V, + ) -> Result<T, V::Error> + where + SE1: 'a, + T: FromIterator<(Label, SE2)>, + V: ExprFVisitor<'a, SE1, SE2, E1, E2>, + { + x.into_iter() + .map(|(k, x)| Ok((k.clone(), v.visit_subexpr(x)?))) + .collect() + } + fn optdupmap<'a, V, SE1, SE2, E1, E2, T>( + x: impl IntoIterator<Item = (&'a Label, &'a Option<SE1>)>, + mut v: V, + ) -> Result<T, V::Error> + where + SE1: 'a, + T: FromIterator<(Label, Option<SE2>)>, + V: ExprFVisitor<'a, SE1, SE2, E1, E2>, + { + x.into_iter() + .map(|(k, x)| { + Ok(( + k.clone(), + match x { + Some(x) => Some(v.visit_subexpr(x)?), + None => None, + }, + )) + }) + .collect() + } + + use crate::syntax::ExprF::*; + Ok(match input { + Var(v) => Var(v.clone()), + Lam(l, t, e) => { + let t = v.visit_subexpr(t)?; + let e = v.visit_subexpr_under_binder(l, e)?; + Lam(l.clone(), t, e) + } + Pi(l, t, e) => { + let t = v.visit_subexpr(t)?; + let e = v.visit_subexpr_under_binder(l, e)?; + Pi(l.clone(), t, e) + } + Let(l, t, a, e) => { + let t = opt(t, &mut |e| v.visit_subexpr(e))?; + let a = v.visit_subexpr(a)?; + let e = v.visit_subexpr_under_binder(l, e)?; + Let(l.clone(), t, a, e) + } + App(f, a) => App(v.visit_subexpr(f)?, v.visit_subexpr(a)?), + Annot(x, t) => Annot(v.visit_subexpr(x)?, v.visit_subexpr(t)?), + Const(k) => Const(*k), + Builtin(v) => Builtin(*v), + BoolLit(b) => BoolLit(*b), + NaturalLit(n) => NaturalLit(*n), + IntegerLit(n) => IntegerLit(*n), + DoubleLit(n) => DoubleLit(*n), + TextLit(t) => TextLit(t.traverse_ref(|e| v.visit_subexpr(e))?), + BinOp(o, x, y) => BinOp(*o, v.visit_subexpr(x)?, v.visit_subexpr(y)?), + BoolIf(b, t, f) => BoolIf( + v.visit_subexpr(b)?, + v.visit_subexpr(t)?, + v.visit_subexpr(f)?, + ), + EmptyListLit(t) => EmptyListLit(v.visit_subexpr(t)?), + NEListLit(es) => NEListLit(vec(es, |e| v.visit_subexpr(e))?), + SomeLit(e) => SomeLit(v.visit_subexpr(e)?), + RecordType(kts) => RecordType(dupmap(kts, v)?), + RecordLit(kvs) => RecordLit(dupmap(kvs, v)?), + UnionType(kts) => UnionType(optdupmap(kts, v)?), + Merge(x, y, t) => Merge( + v.visit_subexpr(x)?, + v.visit_subexpr(y)?, + opt(t, |e| v.visit_subexpr(e))?, + ), + ToMap(x, t) => { + ToMap(v.visit_subexpr(x)?, opt(t, |e| v.visit_subexpr(e))?) + } + Field(e, l) => Field(v.visit_subexpr(e)?, l.clone()), + Projection(e, ls) => Projection(v.visit_subexpr(e)?, ls.clone()), + ProjectionByExpr(e, x) => { + ProjectionByExpr(v.visit_subexpr(e)?, v.visit_subexpr(x)?) + } + Assert(e) => Assert(v.visit_subexpr(e)?), + Import(i) => Import(i.traverse_ref(|e| v.visit_subexpr(e))?), + Embed(a) => Embed(v.visit_embed(a)?), + }) +} + +fn visit_mut<'a, V, SE, E>( + mut v: V, + input: &'a mut ExprF<SE, E>, +) -> Result<(), V::Error> +where + V: ExprFMutVisitor<'a, SE, E>, +{ + fn vec<'a, V, SE, E>(v: &mut V, x: &'a mut Vec<SE>) -> Result<(), V::Error> + where + V: ExprFMutVisitor<'a, SE, E>, + { + for x in x { + v.visit_subexpr(x)?; + } + Ok(()) + } + fn opt<'a, V, SE, E>( + v: &mut V, + x: &'a mut Option<SE>, + ) -> Result<(), V::Error> + where + V: ExprFMutVisitor<'a, SE, E>, + { + if let Some(x) = x { + v.visit_subexpr(x)?; + } + Ok(()) + } + fn dupmap<'a, V, SE, E>( + mut v: V, + x: impl IntoIterator<Item = (&'a Label, &'a mut SE)>, + ) -> Result<(), V::Error> + where + SE: 'a, + V: ExprFMutVisitor<'a, SE, E>, + { + for (_, x) in x { + v.visit_subexpr(x)?; + } + Ok(()) + } + fn optdupmap<'a, V, SE, E>( + mut v: V, + x: impl IntoIterator<Item = (&'a Label, &'a mut Option<SE>)>, + ) -> Result<(), V::Error> + where + SE: 'a, + V: ExprFMutVisitor<'a, SE, E>, + { + for (_, x) in x { + opt(&mut v, x)?; + } + Ok(()) + } + + use crate::syntax::ExprF::*; + match input { + Var(_) | Const(_) | Builtin(_) | BoolLit(_) | NaturalLit(_) + | IntegerLit(_) | DoubleLit(_) => {} + Lam(l, t, e) => { + v.visit_subexpr(t)?; + v.visit_subexpr_under_binder(l, e)?; + } + Pi(l, t, e) => { + v.visit_subexpr(t)?; + v.visit_subexpr_under_binder(l, e)?; + } + Let(l, t, a, e) => { + opt(&mut v, t)?; + v.visit_subexpr(a)?; + v.visit_subexpr_under_binder(l, e)?; + } + App(f, a) => { + v.visit_subexpr(f)?; + v.visit_subexpr(a)?; + } + Annot(x, t) => { + v.visit_subexpr(x)?; + v.visit_subexpr(t)?; + } + TextLit(t) => t.traverse_mut(|e| v.visit_subexpr(e))?, + BinOp(_, x, y) => { + v.visit_subexpr(x)?; + v.visit_subexpr(y)?; + } + BoolIf(b, t, f) => { + v.visit_subexpr(b)?; + v.visit_subexpr(t)?; + v.visit_subexpr(f)?; + } + EmptyListLit(t) => v.visit_subexpr(t)?, + NEListLit(es) => vec(&mut v, es)?, + SomeLit(e) => v.visit_subexpr(e)?, + RecordType(kts) => dupmap(v, kts)?, + RecordLit(kvs) => dupmap(v, kvs)?, + UnionType(kts) => optdupmap(v, kts)?, + Merge(x, y, t) => { + v.visit_subexpr(x)?; + v.visit_subexpr(y)?; + opt(&mut v, t)?; + } + ToMap(x, t) => { + v.visit_subexpr(x)?; + opt(&mut v, t)?; + } + Field(e, _) => v.visit_subexpr(e)?, + Projection(e, _) => v.visit_subexpr(e)?, + ProjectionByExpr(e, x) => { + v.visit_subexpr(e)?; + v.visit_subexpr(x)?; + } + Assert(e) => v.visit_subexpr(e)?, + Import(i) => i.traverse_mut(|e| v.visit_subexpr(e))?, + Embed(a) => v.visit_embed(a)?, + } + Ok(()) +} + +pub struct TraverseRefWithBindersVisitor<F1, F2> { + pub visit_subexpr: F1, + pub visit_under_binder: F2, +} + +impl<'a, SE, E, SE2, Err, F1, F2> ExprFVisitor<'a, SE, SE2, E, E> + for TraverseRefWithBindersVisitor<F1, F2> +where + SE: 'a, + E: 'a + Clone, + F1: FnMut(&'a SE) -> Result<SE2, Err>, + F2: FnOnce(&'a Label, &'a SE) -> Result<SE2, Err>, +{ + type Error = Err; + + fn visit_subexpr(&mut self, subexpr: &'a SE) -> Result<SE2, Self::Error> { + (self.visit_subexpr)(subexpr) + } + fn visit_subexpr_under_binder( + self, + label: &'a Label, + subexpr: &'a SE, + ) -> Result<SE2, Self::Error> { + (self.visit_under_binder)(label, subexpr) + } + fn visit_embed(self, embed: &'a E) -> Result<E, Self::Error> { + Ok(embed.clone()) + } +} + +pub struct TraverseRefVisitor<F1> { + pub visit_subexpr: F1, +} + +impl<'a, SE, E, SE2, Err, F1> ExprFVisitor<'a, SE, SE2, E, E> + for TraverseRefVisitor<F1> +where + SE: 'a, + E: 'a + Clone, + F1: FnMut(&'a SE) -> Result<SE2, Err>, +{ + type Error = Err; + + fn visit_subexpr(&mut self, subexpr: &'a SE) -> Result<SE2, Self::Error> { + (self.visit_subexpr)(subexpr) + } + fn visit_embed(self, embed: &'a E) -> Result<E, Self::Error> { + Ok(embed.clone()) + } +} + +pub struct TraverseMutVisitor<F1> { + pub visit_subexpr: F1, +} + +impl<'a, SE, E, Err, F1> ExprFMutVisitor<'a, SE, E> for TraverseMutVisitor<F1> +where + SE: 'a, + E: 'a, + F1: FnMut(&'a mut SE) -> Result<(), Err>, +{ + type Error = Err; + + fn visit_subexpr( + &mut self, + subexpr: &'a mut SE, + ) -> Result<(), Self::Error> { + (self.visit_subexpr)(subexpr) + } +} diff --git a/dhall/src/syntax/mod.rs b/dhall/src/syntax/mod.rs new file mode 100644 index 0000000..177c4f1 --- /dev/null +++ b/dhall/src/syntax/mod.rs @@ -0,0 +1,15 @@ +#![allow( + clippy::many_single_char_names, + clippy::should_implement_trait, + clippy::new_without_default, + clippy::type_complexity +)] + +mod core; +pub use crate::syntax::core::context; +pub use crate::syntax::core::visitor; +pub use crate::syntax::core::*; +mod printer; +pub use crate::syntax::printer::*; +mod parser; +pub use crate::syntax::parser::*; diff --git a/dhall/src/syntax/parser.rs b/dhall/src/syntax/parser.rs new file mode 100644 index 0000000..2f589fe --- /dev/null +++ b/dhall/src/syntax/parser.rs @@ -0,0 +1,942 @@ +use itertools::Itertools; +use pest::prec_climber as pcl; +use pest::prec_climber::PrecClimber; +use std::rc::Rc; + +use pest_consume::{match_nodes, Parser}; + +use crate::syntax::map::{DupTreeMap, DupTreeSet}; +use crate::syntax::ExprF::*; +use crate::syntax::*; + +// This file consumes the parse tree generated by pest and turns it into +// our own AST. All those custom macros should eventually moved into +// their own crate because they are quite general and useful. For now they +// are here and hopefully you can figure out how they work. + +type ParsedText<E> = InterpolatedText<Expr<E>>; +type ParsedTextContents<E> = InterpolatedTextContents<Expr<E>>; +type ParseInput<'input> = pest_consume::Node<'input, Rule, Rc<str>>; + +pub type ParseError = pest::error::Error<Rule>; +pub type ParseResult<T> = Result<T, ParseError>; + +#[derive(Debug)] +enum Selector<E> { + Field(Label), + Projection(DupTreeSet<Label>), + ProjectionByExpr(Expr<E>), +} + +impl crate::syntax::Builtin { + pub fn parse(s: &str) -> Option<Self> { + use crate::syntax::Builtin::*; + match s { + "Bool" => Some(Bool), + "Natural" => Some(Natural), + "Integer" => Some(Integer), + "Double" => Some(Double), + "Text" => Some(Text), + "List" => Some(List), + "Optional" => Some(Optional), + "None" => Some(OptionalNone), + "Natural/build" => Some(NaturalBuild), + "Natural/fold" => Some(NaturalFold), + "Natural/isZero" => Some(NaturalIsZero), + "Natural/even" => Some(NaturalEven), + "Natural/odd" => Some(NaturalOdd), + "Natural/toInteger" => Some(NaturalToInteger), + "Natural/show" => Some(NaturalShow), + "Natural/subtract" => Some(NaturalSubtract), + "Integer/toDouble" => Some(IntegerToDouble), + "Integer/show" => Some(IntegerShow), + "Double/show" => Some(DoubleShow), + "List/build" => Some(ListBuild), + "List/fold" => Some(ListFold), + "List/length" => Some(ListLength), + "List/head" => Some(ListHead), + "List/last" => Some(ListLast), + "List/indexed" => Some(ListIndexed), + "List/reverse" => Some(ListReverse), + "Optional/fold" => Some(OptionalFold), + "Optional/build" => Some(OptionalBuild), + "Text/show" => Some(TextShow), + _ => None, + } + } +} + +fn input_to_span(input: ParseInput) -> Span { + Span::make(input.user_data().clone(), input.as_pair().as_span()) +} +fn spanned<E>(input: ParseInput, x: RawExpr<E>) -> Expr<E> { + Expr::new(x, input_to_span(input)) +} +fn spanned_union<E>(span1: Span, span2: Span, x: RawExpr<E>) -> Expr<E> { + Expr::new(x, span1.union(&span2)) +} + +// Trim the shared indent off of a vec of lines, as defined by the Dhall semantics of multiline +// literals. +fn trim_indent<E: Clone>(lines: &mut Vec<ParsedText<E>>) { + let is_indent = |c: char| c == ' ' || c == '\t'; + + // There is at least one line so this is safe + let last_line_head = lines.last().unwrap().head(); + let indent_chars = last_line_head + .char_indices() + .take_while(|(_, c)| is_indent(*c)); + let mut min_indent_idx = match indent_chars.last() { + Some((i, _)) => i, + // If there is no indent char, then no indent needs to be stripped + None => return, + }; + + for line in lines.iter() { + // Ignore empty lines + if line.is_empty() { + continue; + } + // Take chars from line while they match the current minimum indent. + let indent_chars = last_line_head[0..=min_indent_idx] + .char_indices() + .zip(line.head().chars()) + .take_while(|((_, c1), c2)| c1 == c2); + match indent_chars.last() { + Some(((i, _), _)) => min_indent_idx = i, + // If there is no indent char, then no indent needs to be stripped + None => return, + }; + } + + // Remove the shared indent from non-empty lines + for line in lines.iter_mut() { + if !line.is_empty() { + line.head_mut().replace_range(0..=min_indent_idx, ""); + } + } +} + +lazy_static::lazy_static! { + static ref PRECCLIMBER: PrecClimber<Rule> = { + use Rule::*; + // In order of precedence + let operators = vec![ + import_alt, + bool_or, + natural_plus, + text_append, + list_append, + bool_and, + combine, + prefer, + combine_types, + natural_times, + bool_eq, + bool_ne, + equivalent, + ]; + PrecClimber::new( + operators + .into_iter() + .map(|op| pcl::Operator::new(op, pcl::Assoc::Left)) + .collect(), + ) + }; +} + +#[derive(Parser)] +#[grammar = "../../dhall_syntax/src/dhall.pest"] +struct DhallParser; + +#[pest_consume::parser(parser = DhallParser, rule = Rule)] +impl DhallParser { + fn EOI(_input: ParseInput) -> ParseResult<()> { + Ok(()) + } + + #[alias(label)] + fn simple_label(input: ParseInput) -> ParseResult<Label> { + Ok(Label::from(input.as_str())) + } + #[alias(label)] + fn quoted_label(input: ParseInput) -> ParseResult<Label> { + Ok(Label::from(input.as_str())) + } + + fn double_quote_literal<E: Clone>( + input: ParseInput, + ) -> ParseResult<ParsedText<E>> { + Ok(match_nodes!(input.into_children(); + [double_quote_chunk(chunks)..] => { + chunks.collect() + } + )) + } + + fn double_quote_chunk<E: Clone>( + input: ParseInput, + ) -> ParseResult<ParsedTextContents<E>> { + Ok(match_nodes!(input.into_children(); + [expression(e)] => { + InterpolatedTextContents::Expr(e) + }, + [double_quote_char(s)] => { + InterpolatedTextContents::Text(s) + }, + )) + } + #[alias(double_quote_char)] + fn double_quote_escaped(input: ParseInput) -> ParseResult<String> { + Ok(match input.as_str() { + "\"" => "\"".to_owned(), + "$" => "$".to_owned(), + "\\" => "\\".to_owned(), + "/" => "/".to_owned(), + "b" => "\u{0008}".to_owned(), + "f" => "\u{000C}".to_owned(), + "n" => "\n".to_owned(), + "r" => "\r".to_owned(), + "t" => "\t".to_owned(), + // "uXXXX" or "u{XXXXX}" + s => { + use std::convert::{TryFrom, TryInto}; + + let s = &s[1..]; + let s = if &s[0..1] == "{" { + &s[1..s.len() - 1] + } else { + &s[0..s.len()] + }; + + if s.len() > 8 { + Err(input.error(format!( + "Escape sequences can't have more than 8 chars: \"{}\"", + s + )))? + } + + // pad with zeroes + let s: String = std::iter::repeat('0') + .take(8 - s.len()) + .chain(s.chars()) + .collect(); + + // `s` has length 8, so `bytes` has length 4 + let bytes: &[u8] = &hex::decode(s).unwrap(); + let i = u32::from_be_bytes(bytes.try_into().unwrap()); + let c = char::try_from(i).unwrap(); + match i { + 0xD800..=0xDFFF => { + let c_ecapsed = c.escape_unicode(); + Err(input.error(format!("Escape sequences can't contain surrogate pairs: \"{}\"", c_ecapsed)))? + } + 0x0FFFE..=0x0FFFF + | 0x1FFFE..=0x1FFFF + | 0x2FFFE..=0x2FFFF + | 0x3FFFE..=0x3FFFF + | 0x4FFFE..=0x4FFFF + | 0x5FFFE..=0x5FFFF + | 0x6FFFE..=0x6FFFF + | 0x7FFFE..=0x7FFFF + | 0x8FFFE..=0x8FFFF + | 0x9FFFE..=0x9FFFF + | 0xAFFFE..=0xAFFFF + | 0xBFFFE..=0xBFFFF + | 0xCFFFE..=0xCFFFF + | 0xDFFFE..=0xDFFFF + | 0xEFFFE..=0xEFFFF + | 0xFFFFE..=0xFFFFF + | 0x10_FFFE..=0x10_FFFF => { + let c_ecapsed = c.escape_unicode(); + Err(input.error(format!("Escape sequences can't contain non-characters: \"{}\"", c_ecapsed)))? + } + _ => {} + } + std::iter::once(c).collect() + } + }) + } + fn double_quote_char(input: ParseInput) -> ParseResult<String> { + Ok(input.as_str().to_owned()) + } + + fn single_quote_literal<E: Clone>( + input: ParseInput, + ) -> ParseResult<ParsedText<E>> { + Ok(match_nodes!(input.into_children(); + [single_quote_continue(lines)] => { + let newline: ParsedText<E> = "\n".to_string().into(); + + // Reverse lines and chars in each line + let mut lines: Vec<ParsedText<E>> = lines + .into_iter() + .rev() + .map(|l| l.into_iter().rev().collect::<ParsedText<E>>()) + .collect(); + + trim_indent(&mut lines); + + lines + .into_iter() + .intersperse(newline) + .flat_map(InterpolatedText::into_iter) + .collect::<ParsedText<E>>() + } + )) + } + fn single_quote_char(input: ParseInput) -> ParseResult<&str> { + Ok(input.as_str()) + } + #[alias(single_quote_char)] + fn escaped_quote_pair(_input: ParseInput) -> ParseResult<&str> { + Ok("''") + } + #[alias(single_quote_char)] + fn escaped_interpolation(_input: ParseInput) -> ParseResult<&str> { + Ok("${") + } + + // Returns a vec of lines in reversed order, where each line is also in reversed order. + fn single_quote_continue<E: Clone>( + input: ParseInput, + ) -> ParseResult<Vec<Vec<ParsedTextContents<E>>>> { + Ok(match_nodes!(input.into_children(); + [expression(e), single_quote_continue(lines)] => { + let c = InterpolatedTextContents::Expr(e); + let mut lines = lines; + lines.last_mut().unwrap().push(c); + lines + }, + [single_quote_char(c), single_quote_continue(lines)] => { + let mut lines = lines; + if c == "\n" || c == "\r\n" { + lines.push(vec![]); + } else { + // TODO: don't allocate for every char + let c = InterpolatedTextContents::Text(c.to_owned()); + lines.last_mut().unwrap().push(c); + } + lines + }, + [] => { + vec![vec![]] + }, + )) + } + + #[alias(expression)] + fn builtin<E: Clone>(input: ParseInput) -> ParseResult<Expr<E>> { + let s = input.as_str(); + let e = match crate::syntax::Builtin::parse(s) { + Some(b) => Builtin(b), + None => match s { + "True" => BoolLit(true), + "False" => BoolLit(false), + "Type" => Const(crate::syntax::Const::Type), + "Kind" => Const(crate::syntax::Const::Kind), + "Sort" => Const(crate::syntax::Const::Sort), + _ => { + Err(input.error(format!("Unrecognized builtin: '{}'", s)))? + } + }, + }; + Ok(spanned(input, e)) + } + + #[alias(double_literal)] + fn NaN(_input: ParseInput) -> ParseResult<core::Double> { + Ok(std::f64::NAN.into()) + } + #[alias(double_literal)] + fn minus_infinity_literal(_input: ParseInput) -> ParseResult<core::Double> { + Ok(std::f64::NEG_INFINITY.into()) + } + #[alias(double_literal)] + fn plus_infinity_literal(_input: ParseInput) -> ParseResult<core::Double> { + Ok(std::f64::INFINITY.into()) + } + + #[alias(double_literal)] + fn numeric_double_literal(input: ParseInput) -> ParseResult<core::Double> { + let s = input.as_str().trim(); + match s.parse::<f64>() { + Ok(x) if x.is_infinite() => Err(input.error(format!( + "Overflow while parsing double literal '{}'", + s + ))), + Ok(x) => Ok(NaiveDouble::from(x)), + Err(e) => Err(input.error(format!("{}", e))), + } + } + + fn natural_literal(input: ParseInput) -> ParseResult<core::Natural> { + input + .as_str() + .trim() + .parse() + .map_err(|e| input.error(format!("{}", e))) + } + + fn integer_literal(input: ParseInput) -> ParseResult<core::Integer> { + input + .as_str() + .trim() + .parse() + .map_err(|e| input.error(format!("{}", e))) + } + + #[alias(expression, shortcut = true)] + fn identifier<E: Clone>(input: ParseInput) -> ParseResult<Expr<E>> { + Ok(match_nodes!(input.children(); + [variable(v)] => spanned(input, Var(v)), + [expression(e)] => e, + )) + } + + fn variable(input: ParseInput) -> ParseResult<V<Label>> { + Ok(match_nodes!(input.into_children(); + [label(l), natural_literal(idx)] => V(l, idx), + [label(l)] => V(l, 0), + )) + } + + #[alias(path_component)] + fn unquoted_path_component(input: ParseInput) -> ParseResult<String> { + Ok(input.as_str().to_string()) + } + #[alias(path_component)] + fn quoted_path_component(input: ParseInput) -> ParseResult<String> { + #[rustfmt::skip] + const RESERVED: &percent_encoding::AsciiSet = + &percent_encoding::CONTROLS + .add(b'=').add(b':').add(b'/').add(b'?') + .add(b'#').add(b'[').add(b']').add(b'@') + .add(b'!').add(b'$').add(b'&').add(b'\'') + .add(b'(').add(b')').add(b'*').add(b'+') + .add(b',').add(b';'); + Ok(input + .as_str() + .chars() + .map(|c| { + // Percent-encode ascii chars + if c.is_ascii() { + percent_encoding::utf8_percent_encode( + &c.to_string(), + RESERVED, + ) + .to_string() + } else { + c.to_string() + } + }) + .collect()) + } + fn path(input: ParseInput) -> ParseResult<FilePath> { + Ok(match_nodes!(input.into_children(); + [path_component(components)..] => { + FilePath { file_path: components.collect() } + } + )) + } + + #[alias(import_type)] + fn local<E: Clone>( + input: ParseInput, + ) -> ParseResult<ImportLocation<Expr<E>>> { + Ok(match_nodes!(input.into_children(); + [local_path((prefix, p))] => ImportLocation::Local(prefix, p), + )) + } + + #[alias(local_path)] + fn parent_path(input: ParseInput) -> ParseResult<(FilePrefix, FilePath)> { + Ok(match_nodes!(input.into_children(); + [path(p)] => (FilePrefix::Parent, p) + )) + } + #[alias(local_path)] + fn here_path(input: ParseInput) -> ParseResult<(FilePrefix, FilePath)> { + Ok(match_nodes!(input.into_children(); + [path(p)] => (FilePrefix::Here, p) + )) + } + #[alias(local_path)] + fn home_path(input: ParseInput) -> ParseResult<(FilePrefix, FilePath)> { + Ok(match_nodes!(input.into_children(); + [path(p)] => (FilePrefix::Home, p) + )) + } + #[alias(local_path)] + fn absolute_path(input: ParseInput) -> ParseResult<(FilePrefix, FilePath)> { + Ok(match_nodes!(input.into_children(); + [path(p)] => (FilePrefix::Absolute, p) + )) + } + + fn scheme(input: ParseInput) -> ParseResult<Scheme> { + Ok(match input.as_str() { + "http" => Scheme::HTTP, + "https" => Scheme::HTTPS, + _ => unreachable!(), + }) + } + + fn http_raw<E: Clone>(input: ParseInput) -> ParseResult<URL<Expr<E>>> { + Ok(match_nodes!(input.into_children(); + [scheme(sch), authority(auth), path(p)] => URL { + scheme: sch, + authority: auth, + path: p, + query: None, + headers: None, + }, + [scheme(sch), authority(auth), path(p), query(q)] => URL { + scheme: sch, + authority: auth, + path: p, + query: Some(q), + headers: None, + }, + )) + } + + fn authority(input: ParseInput) -> ParseResult<String> { + Ok(input.as_str().to_owned()) + } + + fn query(input: ParseInput) -> ParseResult<String> { + Ok(input.as_str().to_owned()) + } + + #[alias(import_type)] + fn http<E: Clone>( + input: ParseInput, + ) -> ParseResult<ImportLocation<Expr<E>>> { + Ok(ImportLocation::Remote(match_nodes!(input.into_children(); + [http_raw(url)] => url, + [http_raw(url), expression(e)] => URL { headers: Some(e), ..url }, + ))) + } + + #[alias(import_type)] + fn env<E: Clone>( + input: ParseInput, + ) -> ParseResult<ImportLocation<Expr<E>>> { + Ok(match_nodes!(input.into_children(); + [environment_variable(v)] => ImportLocation::Env(v), + )) + } + #[alias(environment_variable)] + fn bash_environment_variable(input: ParseInput) -> ParseResult<String> { + Ok(input.as_str().to_owned()) + } + #[alias(environment_variable)] + fn posix_environment_variable(input: ParseInput) -> ParseResult<String> { + Ok(match_nodes!(input.into_children(); + [posix_environment_variable_character(chars)..] => { + chars.collect() + }, + )) + } + fn posix_environment_variable_character( + input: ParseInput, + ) -> ParseResult<&str> { + Ok(match input.as_str() { + "\\\"" => "\"", + "\\\\" => "\\", + "\\a" => "\u{0007}", + "\\b" => "\u{0008}", + "\\f" => "\u{000C}", + "\\n" => "\n", + "\\r" => "\r", + "\\t" => "\t", + "\\v" => "\u{000B}", + s => s, + }) + } + + #[alias(import_type)] + fn missing<E: Clone>( + _input: ParseInput, + ) -> ParseResult<ImportLocation<Expr<E>>> { + Ok(ImportLocation::Missing) + } + + fn hash(input: ParseInput) -> ParseResult<Hash> { + let s = input.as_str().trim(); + let protocol = &s[..6]; + let hash = &s[7..]; + if protocol != "sha256" { + Err(input.error(format!("Unknown hashing protocol '{}'", protocol)))? + } + Ok(Hash::SHA256(hex::decode(hash).unwrap())) + } + + fn import_hashed<E: Clone>( + input: ParseInput, + ) -> ParseResult<crate::syntax::Import<Expr<E>>> { + use crate::syntax::Import; + let mode = ImportMode::Code; + Ok(match_nodes!(input.into_children(); + [import_type(location)] => Import { mode, location, hash: None }, + [import_type(location), hash(h)] => Import { mode, location, hash: Some(h) }, + )) + } + + #[alias(import_mode)] + fn Text(_input: ParseInput) -> ParseResult<ImportMode> { + Ok(ImportMode::RawText) + } + #[alias(import_mode)] + fn Location(_input: ParseInput) -> ParseResult<ImportMode> { + Ok(ImportMode::Location) + } + + #[alias(expression)] + fn import<E: Clone>(input: ParseInput) -> ParseResult<Expr<E>> { + use crate::syntax::Import; + let import = match_nodes!(input.children(); + [import_hashed(imp)] => { + Import { mode: ImportMode::Code, ..imp } + }, + [import_hashed(imp), import_mode(mode)] => { + Import { mode, ..imp } + }, + ); + Ok(spanned(input, Import(import))) + } + + fn lambda(_input: ParseInput) -> ParseResult<()> { + Ok(()) + } + fn forall(_input: ParseInput) -> ParseResult<()> { + Ok(()) + } + fn arrow(_input: ParseInput) -> ParseResult<()> { + Ok(()) + } + fn merge(_input: ParseInput) -> ParseResult<()> { + Ok(()) + } + fn assert(_input: ParseInput) -> ParseResult<()> { + Ok(()) + } + fn if_(_input: ParseInput) -> ParseResult<()> { + Ok(()) + } + fn toMap(_input: ParseInput) -> ParseResult<()> { + Ok(()) + } + + #[alias(expression)] + fn empty_list_literal<E: Clone>(input: ParseInput) -> ParseResult<Expr<E>> { + Ok(match_nodes!(input.children(); + [expression(e)] => spanned(input, EmptyListLit(e)), + )) + } + + fn expression<E: Clone>(input: ParseInput) -> ParseResult<Expr<E>> { + Ok(match_nodes!(input.children(); + [lambda(()), label(l), expression(typ), + arrow(()), expression(body)] => { + spanned(input, Lam(l, typ, body)) + }, + [if_(()), expression(cond), expression(left), + expression(right)] => { + spanned(input, BoolIf(cond, left, right)) + }, + [let_binding(bindings).., expression(final_expr)] => { + bindings.rev().fold( + final_expr, + |acc, x| { + spanned_union( + acc.span(), + x.3, + Let(x.0, x.1, x.2, acc) + ) + } + ) + }, + [forall(()), label(l), expression(typ), + arrow(()), expression(body)] => { + spanned(input, Pi(l, typ, body)) + }, + [expression(typ), arrow(()), expression(body)] => { + spanned(input, Pi("_".into(), typ, body)) + }, + [merge(()), expression(x), expression(y), expression(z)] => { + spanned(input, Merge(x, y, Some(z))) + }, + [assert(()), expression(x)] => { + spanned(input, Assert(x)) + }, + [toMap(()), expression(x), expression(y)] => { + spanned(input, ToMap(x, Some(y))) + }, + [expression(e), expression(annot)] => { + spanned(input, Annot(e, annot)) + }, + [expression(e)] => e, + )) + } + + fn let_binding<E: Clone>( + input: ParseInput, + ) -> ParseResult<(Label, Option<Expr<E>>, Expr<E>, Span)> { + Ok(match_nodes!(input.children(); + [label(name), expression(annot), expression(expr)] => + (name, Some(annot), expr, input_to_span(input)), + [label(name), expression(expr)] => + (name, None, expr, input_to_span(input)), + )) + } + + #[alias(expression, shortcut = true)] + #[prec_climb(expression, PRECCLIMBER)] + fn operator_expression<E: Clone>( + l: Expr<E>, + op: ParseInput, + r: Expr<E>, + ) -> ParseResult<Expr<E>> { + use crate::syntax::BinOp::*; + use Rule::*; + let op = match op.as_rule() { + import_alt => ImportAlt, + bool_or => BoolOr, + natural_plus => NaturalPlus, + text_append => TextAppend, + list_append => ListAppend, + bool_and => BoolAnd, + combine => RecursiveRecordMerge, + prefer => RightBiasedRecordMerge, + combine_types => RecursiveRecordTypeMerge, + natural_times => NaturalTimes, + bool_eq => BoolEQ, + bool_ne => BoolNE, + equivalent => Equivalence, + r => Err(op.error(format!("Rule {:?} isn't an operator", r)))?, + }; + + Ok(spanned_union(l.span(), r.span(), BinOp(op, l, r))) + } + + fn Some_(_input: ParseInput) -> ParseResult<()> { + Ok(()) + } + + #[alias(expression, shortcut = true)] + fn application_expression<E: Clone>( + input: ParseInput, + ) -> ParseResult<Expr<E>> { + Ok(match_nodes!(input.children(); + [expression(e)] => e, + [expression(first), expression(rest)..] => { + rest.fold( + first, + |acc, e| { + spanned_union( + acc.span(), + e.span(), + App(acc, e) + ) + } + ) + }, + )) + } + + #[alias(expression, shortcut = true)] + fn first_application_expression<E: Clone>( + input: ParseInput, + ) -> ParseResult<Expr<E>> { + Ok(match_nodes!(input.children(); + [Some_(()), expression(e)] => { + spanned(input, SomeLit(e)) + }, + [merge(()), expression(x), expression(y)] => { + spanned(input, Merge(x, y, None)) + }, + [toMap(()), expression(x)] => { + spanned(input, ToMap(x, None)) + }, + [expression(e)] => e, + )) + } + + #[alias(expression, shortcut = true)] + fn selector_expression<E: Clone>( + input: ParseInput, + ) -> ParseResult<Expr<E>> { + Ok(match_nodes!(input.children(); + [expression(e)] => e, + [expression(first), selector(rest)..] => { + rest.fold( + first, + |acc, e| { + spanned_union( + acc.span(), + e.1, + match e.0 { + Selector::Field(l) => Field(acc, l), + Selector::Projection(ls) => Projection(acc, ls), + Selector::ProjectionByExpr(e) => ProjectionByExpr(acc, e) + } + ) + } + ) + }, + )) + } + + fn selector<E: Clone>( + input: ParseInput, + ) -> ParseResult<(Selector<E>, Span)> { + let stor = match_nodes!(input.children(); + [label(l)] => Selector::Field(l), + [labels(ls)] => Selector::Projection(ls), + [expression(e)] => Selector::ProjectionByExpr(e), + ); + Ok((stor, input_to_span(input))) + } + + fn labels(input: ParseInput) -> ParseResult<DupTreeSet<Label>> { + Ok(match_nodes!(input.into_children(); + [label(ls)..] => ls.collect(), + )) + } + + #[alias(expression, shortcut = true)] + fn primitive_expression<E: Clone>( + input: ParseInput, + ) -> ParseResult<Expr<E>> { + Ok(match_nodes!(input.children(); + [double_literal(n)] => spanned(input, DoubleLit(n)), + [natural_literal(n)] => spanned(input, NaturalLit(n)), + [integer_literal(n)] => spanned(input, IntegerLit(n)), + [double_quote_literal(s)] => spanned(input, TextLit(s)), + [single_quote_literal(s)] => spanned(input, TextLit(s)), + [expression(e)] => e, + )) + } + + #[alias(expression)] + fn empty_record_literal<E: Clone>( + input: ParseInput, + ) -> ParseResult<Expr<E>> { + Ok(spanned(input, RecordLit(Default::default()))) + } + + #[alias(expression)] + fn empty_record_type<E: Clone>(input: ParseInput) -> ParseResult<Expr<E>> { + Ok(spanned(input, RecordType(Default::default()))) + } + + #[alias(expression)] + fn non_empty_record_type_or_literal<E: Clone>( + input: ParseInput, + ) -> ParseResult<Expr<E>> { + let e = match_nodes!(input.children(); + [label(first_label), non_empty_record_type(rest)] => { + let (first_expr, mut map) = rest; + map.insert(first_label, first_expr); + RecordType(map) + }, + [label(first_label), non_empty_record_literal(rest)] => { + let (first_expr, mut map) = rest; + map.insert(first_label, first_expr); + RecordLit(map) + }, + ); + Ok(spanned(input, e)) + } + + fn non_empty_record_type<E: Clone>( + input: ParseInput, + ) -> ParseResult<(Expr<E>, DupTreeMap<Label, Expr<E>>)> { + Ok(match_nodes!(input.into_children(); + [expression(expr), record_type_entry(entries)..] => { + (expr, entries.collect()) + } + )) + } + + fn record_type_entry<E: Clone>( + input: ParseInput, + ) -> ParseResult<(Label, Expr<E>)> { + Ok(match_nodes!(input.into_children(); + [label(name), expression(expr)] => (name, expr) + )) + } + + fn non_empty_record_literal<E: Clone>( + input: ParseInput, + ) -> ParseResult<(Expr<E>, DupTreeMap<Label, Expr<E>>)> { + Ok(match_nodes!(input.into_children(); + [expression(expr), record_literal_entry(entries)..] => { + (expr, entries.collect()) + } + )) + } + + fn record_literal_entry<E: Clone>( + input: ParseInput, + ) -> ParseResult<(Label, Expr<E>)> { + Ok(match_nodes!(input.into_children(); + [label(name), expression(expr)] => (name, expr) + )) + } + + #[alias(expression)] + fn union_type<E: Clone>(input: ParseInput) -> ParseResult<Expr<E>> { + let map = match_nodes!(input.children(); + [empty_union_type(_)] => Default::default(), + [union_type_entry(entries)..] => entries.collect(), + ); + Ok(spanned(input, UnionType(map))) + } + + fn empty_union_type(_input: ParseInput) -> ParseResult<()> { + Ok(()) + } + + fn union_type_entry<E: Clone>( + input: ParseInput, + ) -> ParseResult<(Label, Option<Expr<E>>)> { + Ok(match_nodes!(input.children(); + [label(name), expression(expr)] => (name, Some(expr)), + [label(name)] => (name, None), + )) + } + + #[alias(expression)] + fn non_empty_list_literal<E: Clone>( + input: ParseInput, + ) -> ParseResult<Expr<E>> { + Ok(match_nodes!(input.children(); + [expression(items)..] => spanned( + input, + NEListLit(items.collect()) + ) + )) + } + + #[alias(expression)] + fn final_expression<E: Clone>(input: ParseInput) -> ParseResult<Expr<E>> { + Ok(match_nodes!(input.into_children(); + [expression(e), EOI(_)] => e + )) + } +} + +pub fn parse_expr<E: Clone>(input_str: &str) -> ParseResult<Expr<E>> { + let rc_input_str = input_str.to_string().into(); + let inputs = DhallParser::parse_with_userdata( + Rule::final_expression, + input_str, + rc_input_str, + )?; + Ok(match_nodes!(<DhallParser>; inputs; + [expression(e)] => e, + )) +} diff --git a/dhall/src/syntax/printer.rs b/dhall/src/syntax/printer.rs new file mode 100644 index 0000000..8df456b --- /dev/null +++ b/dhall/src/syntax/printer.rs @@ -0,0 +1,500 @@ +use crate::syntax::*; +use itertools::Itertools; +use std::fmt::{self, Display}; + +/// Generic instance that delegates to subexpressions +impl<SE: Display + Clone, E: Display> Display for ExprF<SE, E> { + fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> { + use crate::syntax::ExprF::*; + match self { + Lam(a, b, c) => { + write!(f, "λ({} : {}) → {}", a, b, c)?; + } + BoolIf(a, b, c) => { + write!(f, "if {} then {} else {}", a, b, c)?; + } + Pi(a, b, c) if &String::from(a) == "_" => { + write!(f, "{} → {}", b, c)?; + } + Pi(a, b, c) => { + write!(f, "∀({} : {}) → {}", a, b, c)?; + } + Let(a, b, c, d) => { + write!(f, "let {}", a)?; + if let Some(b) = b { + write!(f, " : {}", b)?; + } + write!(f, " = {} in {}", c, d)?; + } + EmptyListLit(t) => { + write!(f, "[] : {}", t)?; + } + NEListLit(es) => { + fmt_list("[", ", ", "]", es, f, Display::fmt)?; + } + SomeLit(e) => { + write!(f, "Some {}", e)?; + } + Merge(a, b, c) => { + write!(f, "merge {} {}", a, b)?; + if let Some(c) = c { + write!(f, " : {}", c)?; + } + } + ToMap(a, b) => { + write!(f, "toMap {}", a)?; + if let Some(b) = b { + write!(f, " : {}", b)?; + } + } + Annot(a, b) => { + write!(f, "{} : {}", a, b)?; + } + Assert(a) => { + write!(f, "assert : {}", a)?; + } + ExprF::BinOp(op, a, b) => { + write!(f, "{} {} {}", a, op, b)?; + } + ExprF::App(a, b) => { + write!(f, "{} {}", a, b)?; + } + Field(a, b) => { + write!(f, "{}.{}", a, b)?; + } + Projection(e, ls) => { + write!(f, "{}.", e)?; + fmt_list("{ ", ", ", " }", ls, f, Display::fmt)?; + } + ProjectionByExpr(a, b) => { + write!(f, "{}.({})", a, b)?; + } + Var(a) => a.fmt(f)?, + Const(k) => k.fmt(f)?, + Builtin(v) => v.fmt(f)?, + BoolLit(true) => f.write_str("True")?, + BoolLit(false) => f.write_str("False")?, + NaturalLit(a) => a.fmt(f)?, + IntegerLit(a) if *a >= 0 => { + f.write_str("+")?; + a.fmt(f)?; + } + IntegerLit(a) => a.fmt(f)?, + DoubleLit(a) => a.fmt(f)?, + TextLit(a) => a.fmt(f)?, + RecordType(a) if a.is_empty() => f.write_str("{}")?, + RecordType(a) => fmt_list("{ ", ", ", " }", a, f, |(k, t), f| { + write!(f, "{} : {}", k, t) + })?, + RecordLit(a) if a.is_empty() => f.write_str("{=}")?, + RecordLit(a) => fmt_list("{ ", ", ", " }", a, f, |(k, v), f| { + write!(f, "{} = {}", k, v) + })?, + UnionType(a) => fmt_list("< ", " | ", " >", a, f, |(k, v), f| { + write!(f, "{}", k)?; + if let Some(v) = v { + write!(f, ": {}", v)?; + } + Ok(()) + })?, + Import(a) => a.fmt(f)?, + Embed(a) => a.fmt(f)?, + } + Ok(()) + } +} + +// There is a one-to-one correspondence between the formatter and the grammar. Each phase is +// named after a corresponding grammar group, and the structure of the formatter reflects +// the relationship between the corresponding grammar rules. This leads to the nice property +// of automatically getting all the parentheses and precedences right. +#[derive(Debug, Copy, Clone, Ord, PartialOrd, Eq, PartialEq)] +enum PrintPhase { + Base, + Operator, + BinOp(core::BinOp), + App, + Import, + Primitive, +} + +// Wraps an Expr with a phase, so that phase selsction can be done +// separate from the actual printing +#[derive(Clone)] +struct PhasedExpr<'a, A>(&'a Expr<A>, PrintPhase); + +impl<'a, A: Display + Clone> Display for PhasedExpr<'a, A> { + fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> { + self.0.as_ref().fmt_phase(f, self.1) + } +} + +impl<'a, A: Display + Clone> PhasedExpr<'a, A> { + fn phase(self, phase: PrintPhase) -> PhasedExpr<'a, A> { + PhasedExpr(self.0, phase) + } +} + +impl<A: Display + Clone> RawExpr<A> { + fn fmt_phase( + &self, + f: &mut fmt::Formatter, + phase: PrintPhase, + ) -> Result<(), fmt::Error> { + use crate::syntax::ExprF::*; + use PrintPhase::*; + + let needs_paren = match self { + Lam(_, _, _) + | BoolIf(_, _, _) + | Pi(_, _, _) + | Let(_, _, _, _) + | EmptyListLit(_) + | NEListLit(_) + | SomeLit(_) + | Merge(_, _, _) + | ToMap(_, _) + | Annot(_, _) + if phase > Base => + { + true + } + // Precedence is magically handled by the ordering of BinOps. + ExprF::BinOp(op, _, _) if phase > PrintPhase::BinOp(*op) => true, + ExprF::App(_, _) if phase > PrintPhase::App => true, + Field(_, _) | Projection(_, _) | ProjectionByExpr(_, _) + if phase > PrintPhase::Import => + { + true + } + _ => false, + }; + + // Annotate subexpressions with the appropriate phase, defaulting to Base + let phased_self = match self.map_ref(|e| PhasedExpr(e, Base)) { + Pi(a, b, c) => { + if &String::from(&a) == "_" { + Pi(a, b.phase(Operator), c) + } else { + Pi(a, b, c) + } + } + Merge(a, b, c) => Merge( + a.phase(PrintPhase::Import), + b.phase(PrintPhase::Import), + c.map(|x| x.phase(PrintPhase::App)), + ), + ToMap(a, b) => ToMap( + a.phase(PrintPhase::Import), + b.map(|x| x.phase(PrintPhase::App)), + ), + Annot(a, b) => Annot(a.phase(Operator), b), + ExprF::BinOp(op, a, b) => ExprF::BinOp( + op, + a.phase(PrintPhase::BinOp(op)), + b.phase(PrintPhase::BinOp(op)), + ), + SomeLit(e) => SomeLit(e.phase(PrintPhase::Import)), + ExprF::App(f, a) => ExprF::App( + f.phase(PrintPhase::Import), + a.phase(PrintPhase::Import), + ), + Field(a, b) => Field(a.phase(Primitive), b), + Projection(e, ls) => Projection(e.phase(Primitive), ls), + ProjectionByExpr(a, b) => ProjectionByExpr(a.phase(Primitive), b), + e => e, + }; + + if needs_paren { + f.write_str("(")?; + } + + // Uses the ExprF<PhasedExpr<_>, _> instance + phased_self.fmt(f)?; + + if needs_paren { + f.write_str(")")?; + } + Ok(()) + } +} + +impl<A: Display + Clone> Display for Expr<A> { + fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> { + self.as_ref().fmt_phase(f, PrintPhase::Base) + } +} + +fn fmt_list<T, I, F>( + open: &str, + sep: &str, + close: &str, + it: I, + f: &mut fmt::Formatter, + func: F, +) -> Result<(), fmt::Error> +where + I: IntoIterator<Item = T>, + F: Fn(T, &mut fmt::Formatter) -> Result<(), fmt::Error>, +{ + f.write_str(open)?; + for (i, x) in it.into_iter().enumerate() { + if i > 0 { + f.write_str(sep)?; + } + func(x, f)?; + } + f.write_str(close) +} + +impl<SubExpr: Display> Display for InterpolatedText<SubExpr> { + fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> { + f.write_str("\"")?; + for x in self.iter() { + match x { + InterpolatedTextContents::Text(a) => { + for c in a.chars() { + match c { + '\\' => f.write_str("\\\\"), + '"' => f.write_str("\\\""), + '$' => f.write_str("\\u0024"), + '\u{0008}' => f.write_str("\\b"), + '\u{000C}' => f.write_str("\\f"), + '\n' => f.write_str("\\n"), + '\r' => f.write_str("\\r"), + '\t' => f.write_str("\\t"), + '\u{0000}'..='\u{001F}' => { + // Escape to an explicit "\u{XXXX}" form + let escaped: String = + c.escape_default().collect(); + // Print as "\uXXXX" + write!( + f, + "\\u{:0>4}", + &escaped[3..escaped.len() - 1] + ) + } + c => write!(f, "{}", c), + }?; + } + } + InterpolatedTextContents::Expr(e) => { + f.write_str("${ ")?; + e.fmt(f)?; + f.write_str(" }")?; + } + } + } + f.write_str("\"")?; + Ok(()) + } +} + +impl Display for Const { + fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> { + <Self as fmt::Debug>::fmt(self, f) + } +} + +impl Display for BinOp { + fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> { + use crate::syntax::BinOp::*; + f.write_str(match self { + BoolOr => "||", + TextAppend => "++", + NaturalPlus => "+", + BoolAnd => "&&", + RecursiveRecordMerge => "∧", + NaturalTimes => "*", + BoolEQ => "==", + BoolNE => "!=", + RecursiveRecordTypeMerge => "⩓", + ImportAlt => "?", + RightBiasedRecordMerge => "⫽", + ListAppend => "#", + Equivalence => "≡", + }) + } +} + +impl Display for NaiveDouble { + fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> { + let v = f64::from(*self); + if v == std::f64::INFINITY { + f.write_str("Infinity") + } else if v == std::f64::NEG_INFINITY { + f.write_str("-Infinity") + } else if v.is_nan() { + f.write_str("NaN") + } else { + let s = format!("{}", v); + if s.contains('e') || s.contains('.') { + f.write_str(&s) + } else { + write!(f, "{}.0", s) + } + } + } +} + +impl Display for Label { + fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> { + // TODO: distinguish between reserved and nonreserved locations for quoting builtins + let s = String::from(self); + let is_reserved = match s.as_str() { + "let" | "in" | "if" | "then" | "else" | "Type" | "Kind" + | "Sort" | "True" | "False" => true, + _ => crate::syntax::Builtin::parse(&s).is_some(), + }; + if !is_reserved && s.chars().all(|c| c.is_ascii_alphanumeric()) { + write!(f, "{}", s) + } else { + write!(f, "`{}`", s) + } + } +} + +impl Display for Hash { + fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> { + match self { + Hash::SHA256(hash) => write!(f, "sha256:{}", hex::encode(hash)), + } + } +} +impl<SubExpr: Display> Display for Import<SubExpr> { + fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> { + use FilePrefix::*; + use ImportLocation::*; + use ImportMode::*; + let quote_if_needed = |s: &str| -> String { + if s.chars().all(|c| c.is_ascii_alphanumeric()) { + s.to_string() + } else { + format!("\"{}\"", s) + } + }; + + match &self.location { + Local(prefix, path) => { + let prefix = match prefix { + Here => ".", + Parent => "..", + Home => "~", + Absolute => "", + }; + write!(f, "{}/", prefix)?; + let path: String = path + .file_path + .iter() + .map(|c| quote_if_needed(&*c)) + .join("/"); + f.write_str(&path)?; + } + Remote(url) => { + write!(f, "{}://{}/", url.scheme, url.authority,)?; + let path: String = url.path.file_path.iter().join("/"); + f.write_str(&path)?; + if let Some(q) = &url.query { + write!(f, "?{}", q)? + } + if let Some(h) = &url.headers { + write!(f, " using ({})", h)? + } + } + Env(s) => { + write!(f, "env:")?; + if s.chars().all(|c| c.is_ascii_alphanumeric()) { + write!(f, "{}", s)?; + } else { + write!(f, "\"")?; + for c in s.chars() { + match c { + '"' => f.write_str("\\\"")?, + '\\' => f.write_str("\\\\")?, + '\u{0007}' => f.write_str("\\a")?, + '\u{0008}' => f.write_str("\\b")?, + '\u{000C}' => f.write_str("\\f")?, + '\n' => f.write_str("\\n")?, + '\r' => f.write_str("\\r")?, + '\t' => f.write_str("\\t")?, + '\u{000B}' => f.write_str("\\v")?, + _ => write!(f, "{}", c)?, + } + } + write!(f, "\"")?; + } + } + Missing => { + write!(f, "missing")?; + } + } + if let Some(hash) = &self.hash { + write!(f, " ")?; + hash.fmt(f)?; + } + match self.mode { + Code => {} + RawText => write!(f, " as Text")?, + Location => write!(f, " as Location")?, + } + Ok(()) + } +} + +impl Display for Builtin { + fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> { + use crate::syntax::Builtin::*; + f.write_str(match *self { + Bool => "Bool", + Natural => "Natural", + Integer => "Integer", + Double => "Double", + Text => "Text", + List => "List", + Optional => "Optional", + OptionalNone => "None", + NaturalBuild => "Natural/build", + NaturalFold => "Natural/fold", + NaturalIsZero => "Natural/isZero", + NaturalEven => "Natural/even", + NaturalOdd => "Natural/odd", + NaturalToInteger => "Natural/toInteger", + NaturalShow => "Natural/show", + NaturalSubtract => "Natural/subtract", + IntegerToDouble => "Integer/toDouble", + IntegerShow => "Integer/show", + DoubleShow => "Double/show", + ListBuild => "List/build", + ListFold => "List/fold", + ListLength => "List/length", + ListHead => "List/head", + ListLast => "List/last", + ListIndexed => "List/indexed", + ListReverse => "List/reverse", + OptionalFold => "Optional/fold", + OptionalBuild => "Optional/build", + TextShow => "Text/show", + }) + } +} + +impl Display for Scheme { + fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> { + use crate::syntax::Scheme::*; + f.write_str(match *self { + HTTP => "http", + HTTPS => "https", + }) + } +} + +impl<Label: Display> Display for V<Label> { + fn fmt(&self, f: &mut fmt::Formatter) -> Result<(), fmt::Error> { + let V(x, n) = self; + x.fmt(f)?; + if *n != 0 { + write!(f, "@{}", n)?; + } + Ok(()) + } +} |