diff options
Diffstat (limited to 'dhall_syntax/src/core')
-rw-r--r-- | dhall_syntax/src/core/context.rs | 80 | ||||
-rw-r--r-- | dhall_syntax/src/core/expr.rs | 464 | ||||
-rw-r--r-- | dhall_syntax/src/core/import.rs | 64 | ||||
-rw-r--r-- | dhall_syntax/src/core/label.rs | 34 | ||||
-rw-r--r-- | dhall_syntax/src/core/mod.rs | 10 | ||||
-rw-r--r-- | dhall_syntax/src/core/text.rs | 116 | ||||
-rw-r--r-- | dhall_syntax/src/core/visitor.rs | 458 |
7 files changed, 1226 insertions, 0 deletions
diff --git a/dhall_syntax/src/core/context.rs b/dhall_syntax/src/core/context.rs new file mode 100644 index 0000000..55bfff5 --- /dev/null +++ b/dhall_syntax/src/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 X)` +/// +/// * 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<'a>(&'a self) -> impl Iterator<Item = (&K, &T)> { + self.0 + .iter() + .flat_map(|(k, vs)| vs.iter().map(move |v| (k, v))) + } + + pub fn iter_keys<'a>(&'a 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_syntax/src/core/expr.rs b/dhall_syntax/src/core/expr.rs new file mode 100644 index 0000000..2b76b9a --- /dev/null +++ b/dhall_syntax/src/core/expr.rs @@ -0,0 +1,464 @@ +#![allow(non_snake_case)] +use std::collections::BTreeMap; +use std::rc::Rc; + +use crate::visitor; +use crate::*; + +pub type Integer = isize; +pub type Natural = usize; +pub type Double = NaiveDouble; + +/// An empty type +#[derive(Debug, Copy, Clone, PartialEq, Eq)] +pub enum X {} + +pub fn trivial_result<T>(x: Result<T, X>) -> T { + match x { + Ok(x) => x, + Err(e) => match 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 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)] +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)] +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)] +pub enum BinOp { + /// x ? y + ImportAlt, + /// x || y` + BoolOr, + /// x + y` + NaturalPlus, + /// x ++ y` + TextAppend, + /// x # y + ListAppend, + /// x && y` + BoolAnd, + /// x ∧ y` + Combine, + /// x // y + Prefer, + /// x //\\ y + CombineTypes, + /// x * y` + NaturalTimes, + /// x == y` + BoolEQ, + /// x != y` + BoolNE, +} + +/// Built-ins +#[derive(Debug, Copy, Clone, PartialEq, Eq)] +pub enum Builtin { + Bool, + Natural, + Integer, + Double, + Text, + List, + Optional, + OptionalNone, + NaturalBuild, + NaturalFold, + NaturalIsZero, + NaturalEven, + NaturalOdd, + NaturalToInteger, + NaturalShow, + IntegerToDouble, + IntegerShow, + DoubleShow, + ListBuild, + ListFold, + ListLength, + ListHead, + ListLast, + ListIndexed, + ListReverse, + OptionalFold, + OptionalBuild, + TextShow, +} + +pub type ParsedExpr = SubExpr<X, Import>; +pub type ResolvedExpr = SubExpr<X, X>; +pub type DhallExpr = ResolvedExpr; + +// Each node carries an annotation. In practice it's either X (no annotation) or a Span. +#[derive(Debug)] +pub struct SubExpr<Note, Embed>(Rc<(Expr<Note, Embed>, Option<Note>)>); + +impl<Note, Embed: PartialEq> std::cmp::PartialEq for SubExpr<Note, Embed> { + fn eq(&self, other: &Self) -> bool { + self.0.as_ref().0 == other.0.as_ref().0 + } +} + +impl<Note, Embed: Eq> std::cmp::Eq for SubExpr<Note, Embed> {} + +pub type Expr<Note, Embed> = ExprF<SubExpr<Note, Embed>, Label, Embed>; + +/// 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)] +pub enum ExprF<SubExpr, Label, 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), + /// 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>), + /// `[] : List t` + EmptyListLit(SubExpr), + /// `[x, y, z]` + NEListLit(Vec<SubExpr>), + /// Deprecated Optional literal form + /// `[] : Optional a` + /// `[x] : Optional a` + OldOptionalLit(Option<SubExpr>, SubExpr), + /// `Some e` + SomeLit(SubExpr), + /// `{ k1 : t1, k2 : t1 }` + RecordType(BTreeMap<Label, SubExpr>), + /// `{ k1 = v1, k2 = v2 }` + RecordLit(BTreeMap<Label, SubExpr>), + /// `< k1 : t1, k2 >` + UnionType(BTreeMap<Label, Option<SubExpr>>), + /// `< k1 = t1, k2 : t2, k3 >` + UnionLit(Label, SubExpr, BTreeMap<Label, Option<SubExpr>>), + /// `merge x y : t` + Merge(SubExpr, SubExpr, Option<SubExpr>), + /// `e.x` + Field(SubExpr, Label), + /// `e.{ x, y, z }` + Projection(SubExpr, Vec<Label>), + /// Embeds an import or the result of resolving the import + Embed(Embed), +} + +impl<SE, L, E> ExprF<SE, L, E> { + pub(crate) fn visit<'a, V, Return>(&'a self, v: V) -> Return + where + V: visitor::GenericVisitor<&'a ExprF<SE, L, E>, Return>, + { + v.visit(self) + } + + fn traverse_ref_with_special_handling_of_binders<'a, SE2, L2, E2, Err>( + &'a self, + visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>, + visit_under_binder: impl FnOnce(&'a L, &'a SE) -> Result<SE2, Err>, + visit_embed: impl FnOnce(&'a E) -> Result<E2, Err>, + visit_label: impl FnMut(&'a L) -> Result<L2, Err>, + ) -> Result<ExprF<SE2, L2, E2>, Err> + where + L: Ord, + L2: Ord, + { + self.visit(visitor::TraverseRefWithBindersVisitor { + visit_subexpr, + visit_under_binder, + visit_embed, + visit_label, + }) + } + + fn traverse_ref<'a, SE2, L2, E2, Err>( + &'a self, + visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>, + visit_embed: impl FnOnce(&'a E) -> Result<E2, Err>, + visit_label: impl FnMut(&'a L) -> Result<L2, Err>, + ) -> Result<ExprF<SE2, L2, E2>, Err> + where + L: Ord, + L2: Ord, + { + self.visit(visitor::TraverseRefVisitor { + visit_subexpr, + visit_embed, + visit_label, + }) + } + + pub fn map_ref_with_special_handling_of_binders<'a, SE2, L2, E2>( + &'a self, + mut map_subexpr: impl FnMut(&'a SE) -> SE2, + mut map_under_binder: impl FnMut(&'a L, &'a SE) -> SE2, + map_embed: impl FnOnce(&'a E) -> E2, + mut map_label: impl FnMut(&'a L) -> L2, + ) -> ExprF<SE2, L2, E2> + where + L: Ord, + L2: Ord, + { + trivial_result(self.traverse_ref_with_special_handling_of_binders( + |x| Ok(map_subexpr(x)), + |l, x| Ok(map_under_binder(l, x)), + |x| Ok(map_embed(x)), + |x| Ok(map_label(x)), + )) + } + + pub fn map_ref<'a, SE2, L2, E2>( + &'a self, + mut map_subexpr: impl FnMut(&'a SE) -> SE2, + map_embed: impl FnOnce(&'a E) -> E2, + mut map_label: impl FnMut(&'a L) -> L2, + ) -> ExprF<SE2, L2, E2> + where + L: Ord, + L2: Ord, + { + trivial_result(self.traverse_ref( + |x| Ok(map_subexpr(x)), + |x| Ok(map_embed(x)), + |x| Ok(map_label(x)), + )) + } + + pub fn traverse_ref_simple<'a, SE2, Err>( + &'a self, + visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>, + ) -> Result<ExprF<SE2, L, E>, Err> + where + L: Ord + Clone, + E: Clone, + { + self.traverse_ref( + visit_subexpr, + |x| Ok(E::clone(x)), + |x| Ok(L::clone(x)), + ) + } + + pub fn map_ref_simple<'a, SE2>( + &'a self, + map_subexpr: impl Fn(&'a SE) -> SE2, + ) -> ExprF<SE2, L, E> + where + L: Ord + Clone, + E: Clone, + { + self.map_ref(map_subexpr, E::clone, L::clone) + } +} + +impl<N, E> Expr<N, E> { + fn traverse_embed<E2, Err>( + &self, + visit_embed: impl FnMut(&E) -> Result<E2, Err>, + ) -> Result<Expr<N, E2>, Err> + where + N: Clone, + { + self.visit(&mut visitor::TraverseEmbedVisitor(visit_embed)) + } + + fn map_embed<E2>(&self, mut map_embed: impl FnMut(&E) -> E2) -> Expr<N, E2> + where + N: Clone, + { + trivial_result(self.traverse_embed(|x| Ok(map_embed(x)))) + } +} + +impl Expr<X, X> { + pub fn absurd<N, E>(&self) -> Expr<N, E> { + self.visit(&mut visitor::AbsurdVisitor) + } +} + +impl<E: Clone> Expr<X, E> { + pub fn note_absurd<N>(&self) -> Expr<N, E> { + self.visit(&mut visitor::NoteAbsurdVisitor) + } +} + +impl<N, E> SubExpr<N, E> { + pub fn as_ref(&self) -> &Expr<N, E> { + &self.0.as_ref().0 + } + + pub fn new(x: Expr<N, E>, n: N) -> Self { + SubExpr(Rc::new((x, Some(n)))) + } + + pub fn from_expr_no_note(x: Expr<N, E>) -> Self { + SubExpr(Rc::new((x, None))) + } + + pub fn rewrap<E2>(&self, x: Expr<N, E2>) -> SubExpr<N, E2> + where + N: Clone, + { + SubExpr(Rc::new((x, (self.0).1.clone()))) + } + + pub fn traverse_embed<E2, Err>( + &self, + visit_embed: impl FnMut(&E) -> Result<E2, Err>, + ) -> Result<SubExpr<N, E2>, Err> + where + N: Clone, + { + Ok(self.rewrap(self.as_ref().traverse_embed(visit_embed)?)) + } + + pub fn map_embed<E2>( + &self, + map_embed: impl FnMut(&E) -> E2, + ) -> SubExpr<N, E2> + where + N: Clone, + { + self.rewrap(self.as_ref().map_embed(map_embed)) + } + + pub fn map_subexprs_with_special_handling_of_binders<'a>( + &'a self, + map_expr: impl FnMut(&'a Self) -> Self, + map_under_binder: impl FnMut(&'a Label, &'a Self) -> Self, + ) -> Self + where + N: Clone, + { + match self.as_ref() { + ExprF::Embed(_) => SubExpr::clone(self), + // This calls ExprF::map_ref + e => self.rewrap(e.map_ref_with_special_handling_of_binders( + map_expr, + map_under_binder, + |_| unreachable!(), + Label::clone, + )), + } + } +} + +impl SubExpr<X, X> { + pub fn absurd<N: Clone, T>(&self) -> SubExpr<N, T> { + SubExpr::from_expr_no_note(self.as_ref().absurd()) + } +} + +impl<E: Clone> SubExpr<X, E> { + pub fn note_absurd<N>(&self) -> SubExpr<N, E> { + SubExpr::from_expr_no_note(self.as_ref().note_absurd()) + } +} + +impl<N, E> Clone for SubExpr<N, E> { + fn clone(&self) -> Self { + SubExpr(Rc::clone(&self.0)) + } +} + +// Should probably rename this +pub fn rc<E>(x: Expr<X, E>) -> SubExpr<X, E> { + SubExpr::from_expr_no_note(x) +} + +/// Add an isize to an usize +/// Panics on over/underflow +fn add_ui(u: usize, i: isize) -> usize { + if i < 0 { + u.checked_sub(i.checked_neg().unwrap() as usize).unwrap() + } else { + u.checked_add(i as usize).unwrap() + } +} + +impl<Label: PartialEq + Clone> V<Label> { + pub fn shift(&self, delta: isize, var: &V<Label>) -> Self { + let V(x, n) = var; + let V(y, m) = self; + if x == y && n <= m { + V(y.clone(), add_ui(*m, delta)) + } else { + V(y.clone(), *m) + } + } +} diff --git a/dhall_syntax/src/core/import.rs b/dhall_syntax/src/core/import.rs new file mode 100644 index 0000000..00f293c --- /dev/null +++ b/dhall_syntax/src/core/import.rs @@ -0,0 +1,64 @@ +use std::path::PathBuf; + +/// 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, +} + +/// The location of import (i.e. local vs. remote vs. environment) +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub enum ImportLocation { + Local(FilePrefix, PathBuf), + Remote(URL), + Env(String), + Missing, +} + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct URL { + pub scheme: Scheme, + pub authority: String, + pub path: PathBuf, + pub query: Option<String>, + pub headers: Option<Box<ImportHashed>>, +} + +#[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, +} + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct Hash { + pub protocol: String, + pub hash: String, +} + +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct ImportHashed { + pub location: ImportLocation, + pub hash: Option<Hash>, +} + +/// Reference to an external resource +#[derive(Debug, Clone, PartialEq, Eq, Hash)] +pub struct Import { + pub mode: ImportMode, + pub location_hashed: ImportHashed, +} diff --git a/dhall_syntax/src/core/label.rs b/dhall_syntax/src/core/label.rs new file mode 100644 index 0000000..43c3f53 --- /dev/null +++ b/dhall_syntax/src/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_syntax/src/core/mod.rs b/dhall_syntax/src/core/mod.rs new file mode 100644 index 0000000..7762479 --- /dev/null +++ b/dhall_syntax/src/core/mod.rs @@ -0,0 +1,10 @@ +mod expr; +pub use expr::*; +mod import; +pub use import::*; +mod label; +pub use label::*; +mod text; +pub use text::*; +pub mod context; +pub mod visitor; diff --git a/dhall_syntax/src/core/text.rs b/dhall_syntax/src/core/text.rs new file mode 100644 index 0000000..83643d9 --- /dev/null +++ b/dhall_syntax/src/core/text.rs @@ -0,0 +1,116 @@ +use std::iter::FromIterator; + +#[derive(Debug, Clone, PartialEq, Eq)] +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(), + } + } +} + +impl<SubExpr> InterpolatedText<SubExpr> { + 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 iter<'a>( + &'a self, + ) -> impl Iterator<Item = InterpolatedTextContents<SubExpr>> + 'a + where + SubExpr: Clone, + { + use std::iter::once; + use InterpolatedTextContents::{Expr, Text}; + once(Text(self.head.clone())) + .chain(self.tail.iter().flat_map(|(e, s)| { + once(Expr(SubExpr::clone(e))).chain(once(Text(s.clone()))) + })) + .filter(|c| !c.is_empty()) + } + + 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)))), + ) + .filter(|c| !c.is_empty()) + } +} + +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_syntax/src/core/visitor.rs b/dhall_syntax/src/core/visitor.rs new file mode 100644 index 0000000..20bfc72 --- /dev/null +++ b/dhall_syntax/src/core/visitor.rs @@ -0,0 +1,458 @@ +use std::collections::BTreeMap; + +use crate::*; + +/// A way too generic Visitor trait. +pub trait GenericVisitor<Input, Return>: Sized { + fn visit(self, input: Input) -> Return; +} + +/// 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_embed` 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 +/// and TraverseEmbedVisitor. +/// This is very generic. For a more legible trait, see ExprFInFallibleVisitor +pub trait ExprFVeryGenericVisitor<'a, Ret, SE1, L1, E1>: Sized { + type Error; + type SE2; + type L2; + type E2; + + fn visit_subexpr( + &mut self, + subexpr: &'a SE1, + ) -> Result<Self::SE2, Self::Error>; + fn visit_label(&mut self, label: &'a L1) -> Result<Self::L2, Self::Error>; + + fn visit_binder( + self, + label: &'a L1, + subexpr: &'a SE1, + ) -> Result<(Self::L2, Self::SE2), Self::Error>; + + fn visit_embed_squash(self, embed: &'a E1) -> Result<Ret, Self::Error>; + + // Called with the result of the map, in the non-embed case. + // Useful to change the result type, and/or avoid some loss of info + fn visit_resulting_exprf( + result: ExprF<Self::SE2, Self::L2, Self::E2>, + ) -> Result<Ret, Self::Error>; +} + +impl<'a, T, Ret, SE1, L1, E1> + GenericVisitor<&'a ExprF<SE1, L1, E1>, Result<Ret, T::Error>> for T +where + L1: Ord, + T::L2: Ord, + T: ExprFVeryGenericVisitor<'a, Ret, SE1, L1, E1>, +{ + fn visit(self, input: &'a ExprF<SE1, L1, E1>) -> Result<Ret, T::Error> { + 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 btmap<'a, V, Ret, SE, L, E>( + x: &'a BTreeMap<L, SE>, + mut v: V, + ) -> Result<BTreeMap<V::L2, V::SE2>, V::Error> + where + L: Ord, + V::L2: Ord, + V: ExprFVeryGenericVisitor<'a, Ret, SE, L, E>, + { + x.iter() + .map(|(k, x)| Ok((v.visit_label(k)?, v.visit_subexpr(x)?))) + .collect() + } + fn btoptmap<'a, V, Ret, SE, L, E>( + x: &'a BTreeMap<L, Option<SE>>, + mut v: V, + ) -> Result<BTreeMap<V::L2, Option<V::SE2>>, V::Error> + where + L: Ord, + V::L2: Ord, + V: ExprFVeryGenericVisitor<'a, Ret, SE, L, E>, + { + x.iter() + .map(|(k, x)| { + Ok(( + v.visit_label(k)?, + match x { + Some(x) => Some(v.visit_subexpr(x)?), + None => None, + }, + )) + }) + .collect() + } + + let mut v = self; + use crate::ExprF::*; + T::visit_resulting_exprf(match input { + Var(V(l, n)) => Var(V(v.visit_label(l)?, *n)), + Lam(l, t, e) => { + let t = v.visit_subexpr(t)?; + let (l, e) = v.visit_binder(l, e)?; + Lam(l, t, e) + } + Pi(l, t, e) => { + let t = v.visit_subexpr(t)?; + let (l, e) = v.visit_binder(l, e)?; + Pi(l, t, e) + } + Let(l, t, a, e) => { + let t = opt(t, &mut |e| v.visit_subexpr(e))?; + let a = v.visit_subexpr(a)?; + let (l, e) = v.visit_binder(l, e)?; + Let(l, 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))?), + OldOptionalLit(x, t) => OldOptionalLit( + opt(x, |e| v.visit_subexpr(e))?, + v.visit_subexpr(t)?, + ), + SomeLit(e) => SomeLit(v.visit_subexpr(e)?), + RecordType(kts) => RecordType(btmap(kts, v)?), + RecordLit(kvs) => RecordLit(btmap(kvs, v)?), + UnionType(kts) => UnionType(btoptmap(kts, v)?), + UnionLit(k, x, kts) => UnionLit( + v.visit_label(k)?, + v.visit_subexpr(x)?, + btoptmap(kts, v)?, + ), + Merge(x, y, t) => Merge( + v.visit_subexpr(x)?, + v.visit_subexpr(y)?, + opt(t, |e| v.visit_subexpr(e))?, + ), + Field(e, l) => Field(v.visit_subexpr(e)?, v.visit_label(l)?), + Projection(e, ls) => { + Projection(v.visit_subexpr(e)?, vec(ls, |l| v.visit_label(l))?) + } + Embed(a) => return v.visit_embed_squash(a), + }) + } +} + +/// Like ExprFVeryGenericVisitor, but sets the return +/// type to ExprF<_> +pub trait ExprFFallibleVisitor<'a, SE1, SE2, L1, L2, E1, E2>: Sized { + type Error; + + fn visit_subexpr(&mut self, subexpr: &'a SE1) -> Result<SE2, Self::Error>; + fn visit_label(&mut self, label: &'a L1) -> Result<L2, Self::Error>; + fn visit_embed(self, embed: &'a E1) -> Result<E2, Self::Error>; + + fn visit_subexpr_under_binder( + mut self, + _label: &'a L1, + subexpr: &'a SE1, + ) -> Result<SE2, Self::Error> { + self.visit_subexpr(subexpr) + } + + fn visit_binder( + mut self, + label: &'a L1, + subexpr: &'a SE1, + ) -> Result<(L2, SE2), Self::Error> { + Ok(( + self.visit_label(label)?, + self.visit_subexpr_under_binder(label, subexpr)?, + )) + } + + fn visit_embed_squash( + self, + embed: &'a E1, + ) -> Result<ExprF<SE2, L2, E2>, Self::Error> { + Ok(ExprF::Embed(self.visit_embed(embed)?)) + } +} + +impl<'a, T, SE1, SE2, L1, L2, E1, E2> + ExprFVeryGenericVisitor<'a, ExprF<SE2, L2, E2>, SE1, L1, E1> for T +where + T: ExprFFallibleVisitor<'a, SE1, SE2, L1, L2, E1, E2>, +{ + type Error = T::Error; + type SE2 = SE2; + type L2 = L2; + type E2 = E2; + + fn visit_subexpr( + &mut self, + subexpr: &'a SE1, + ) -> Result<Self::SE2, Self::Error> { + self.visit_subexpr(subexpr) + } + + fn visit_label(&mut self, label: &'a L1) -> Result<Self::L2, Self::Error> { + self.visit_label(label) + } + + fn visit_binder( + self, + label: &'a L1, + subexpr: &'a SE1, + ) -> Result<(Self::L2, Self::SE2), Self::Error> { + self.visit_binder(label, subexpr) + } + + fn visit_embed_squash( + self, + embed: &'a E1, + ) -> Result<ExprF<SE2, L2, E2>, Self::Error> { + self.visit_embed_squash(embed) + } + + // Called with the result of the map, in the non-embed case. + // Useful to change the result type, and/or avoid some loss of info + fn visit_resulting_exprf( + result: ExprF<Self::SE2, Self::L2, Self::E2>, + ) -> Result<ExprF<SE2, L2, E2>, Self::Error> { + Ok(result) + } +} + +/// Like ExprFFallibleVisitor, but without the error handling. +pub trait ExprFInFallibleVisitor<'a, SE1, SE2, L1, L2, E1, E2>: Sized { + fn visit_subexpr(&mut self, subexpr: &'a SE1) -> SE2; + fn visit_label(&mut self, label: &'a L1) -> L2; + fn visit_embed(self, embed: &'a E1) -> E2; + + fn visit_subexpr_under_binder( + mut self, + _label: &'a L1, + subexpr: &'a SE1, + ) -> SE2 { + self.visit_subexpr(subexpr) + } + + fn visit_binder(mut self, label: &'a L1, subexpr: &'a SE1) -> (L2, SE2) { + ( + self.visit_label(label), + self.visit_subexpr_under_binder(label, subexpr), + ) + } + + fn visit_embed_squash(self, embed: &'a E1) -> ExprF<SE2, L2, E2> { + ExprF::Embed(self.visit_embed(embed)) + } +} + +struct InfallibleWrapper<T>(T); + +impl<'a, T, SE1, SE2, L1, L2, E1, E2> + ExprFFallibleVisitor<'a, SE1, SE2, L1, L2, E1, E2> for InfallibleWrapper<T> +where + T: ExprFInFallibleVisitor<'a, SE1, SE2, L1, L2, E1, E2>, +{ + type Error = X; + + fn visit_subexpr(&mut self, subexpr: &'a SE1) -> Result<SE2, Self::Error> { + Ok(self.0.visit_subexpr(subexpr)) + } + fn visit_label(&mut self, label: &'a L1) -> Result<L2, Self::Error> { + Ok(self.0.visit_label(label)) + } + fn visit_embed(self, embed: &'a E1) -> Result<E2, Self::Error> { + Ok(self.0.visit_embed(embed)) + } + + fn visit_binder( + self, + label: &'a L1, + subexpr: &'a SE1, + ) -> Result<(L2, SE2), Self::Error> { + Ok(self.0.visit_binder(label, subexpr)) + } + + fn visit_embed_squash( + self, + embed: &'a E1, + ) -> Result<ExprF<SE2, L2, E2>, Self::Error> { + Ok(self.0.visit_embed_squash(embed)) + } +} + +impl<'a, T, SE1, SE2, L1, L2, E1, E2> + GenericVisitor<&'a ExprF<SE1, L1, E1>, ExprF<SE2, L2, E2>> for T +where + L1: Ord, + L2: Ord, + T: ExprFInFallibleVisitor<'a, SE1, SE2, L1, L2, E1, E2>, +{ + fn visit(self, input: &'a ExprF<SE1, L1, E1>) -> ExprF<SE2, L2, E2> { + trivial_result(InfallibleWrapper(self).visit(input)) + } +} + +pub struct TraverseRefWithBindersVisitor<F1, F2, F4, F5> { + pub visit_subexpr: F1, + pub visit_under_binder: F2, + pub visit_embed: F4, + pub visit_label: F5, +} + +impl<'a, SE, L, E, SE2, L2, E2, Err, F1, F2, F4, F5> + ExprFFallibleVisitor<'a, SE, SE2, L, L2, E, E2> + for TraverseRefWithBindersVisitor<F1, F2, F4, F5> +where + SE: 'a, + L: 'a, + E: 'a, + L: Ord, + L2: Ord, + F1: FnMut(&'a SE) -> Result<SE2, Err>, + F2: FnOnce(&'a L, &'a SE) -> Result<SE2, Err>, + F4: FnOnce(&'a E) -> Result<E2, Err>, + F5: FnMut(&'a L) -> Result<L2, 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 L, + subexpr: &'a SE, + ) -> Result<SE2, Self::Error> { + (self.visit_under_binder)(label, subexpr) + } + fn visit_embed(self, embed: &'a E) -> Result<E2, Self::Error> { + (self.visit_embed)(embed) + } + fn visit_label(&mut self, label: &'a L) -> Result<L2, Self::Error> { + (self.visit_label)(label) + } +} + +pub struct TraverseRefVisitor<F1, F3, F4> { + pub visit_subexpr: F1, + pub visit_embed: F3, + pub visit_label: F4, +} + +impl<'a, SE, L, E, SE2, L2, E2, Err, F1, F3, F4> + ExprFFallibleVisitor<'a, SE, SE2, L, L2, E, E2> + for TraverseRefVisitor<F1, F3, F4> +where + SE: 'a, + L: 'a, + E: 'a, + L: Ord, + L2: Ord, + F1: FnMut(&'a SE) -> Result<SE2, Err>, + F3: FnOnce(&'a E) -> Result<E2, Err>, + F4: FnMut(&'a L) -> Result<L2, 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<E2, Self::Error> { + (self.visit_embed)(embed) + } + fn visit_label(&mut self, label: &'a L) -> Result<L2, Self::Error> { + (self.visit_label)(label) + } +} + +pub struct TraverseEmbedVisitor<F1>(pub F1); + +impl<'a, 'b, N, E, E2, Err, F1> + ExprFFallibleVisitor<'a, SubExpr<N, E>, SubExpr<N, E2>, Label, Label, E, E2> + for &'b mut TraverseEmbedVisitor<F1> +where + N: Clone + 'a, + F1: FnMut(&E) -> Result<E2, Err>, +{ + type Error = Err; + + fn visit_subexpr( + &mut self, + subexpr: &'a SubExpr<N, E>, + ) -> Result<SubExpr<N, E2>, Self::Error> { + Ok(subexpr.rewrap(subexpr.as_ref().visit(&mut **self)?)) + } + fn visit_embed(self, embed: &'a E) -> Result<E2, Self::Error> { + (self.0)(embed) + } + fn visit_label(&mut self, label: &'a Label) -> Result<Label, Self::Error> { + Ok(Label::clone(label)) + } +} + +pub struct NoteAbsurdVisitor; + +impl<'a, 'b, N, E> + ExprFInFallibleVisitor<'a, SubExpr<X, E>, SubExpr<N, E>, Label, Label, E, E> + for &'b mut NoteAbsurdVisitor +where + E: Clone + 'a, +{ + fn visit_subexpr(&mut self, subexpr: &'a SubExpr<X, E>) -> SubExpr<N, E> { + SubExpr::from_expr_no_note(subexpr.as_ref().visit(&mut **self)) + } + fn visit_embed(self, embed: &'a E) -> E { + E::clone(embed) + } + fn visit_label(&mut self, label: &'a Label) -> Label { + Label::clone(label) + } +} + +pub struct AbsurdVisitor; + +impl<'a, 'b, N, E> + ExprFInFallibleVisitor<'a, SubExpr<X, X>, SubExpr<N, E>, Label, Label, X, E> + for &'b mut AbsurdVisitor +{ + fn visit_subexpr(&mut self, subexpr: &'a SubExpr<X, X>) -> SubExpr<N, E> { + SubExpr::from_expr_no_note(subexpr.as_ref().visit(&mut **self)) + } + fn visit_embed(self, embed: &'a X) -> E { + match *embed {} + } + fn visit_label(&mut self, label: &'a Label) -> Label { + Label::clone(label) + } +} |