summaryrefslogtreecommitdiff
path: root/dhall/src/syntax/ast
diff options
context:
space:
mode:
Diffstat (limited to 'dhall/src/syntax/ast')
-rw-r--r--dhall/src/syntax/ast/expr.rs377
-rw-r--r--dhall/src/syntax/ast/import.rs130
-rw-r--r--dhall/src/syntax/ast/label.rs34
-rw-r--r--dhall/src/syntax/ast/map.rs394
-rw-r--r--dhall/src/syntax/ast/mod.rs12
-rw-r--r--dhall/src/syntax/ast/span.rs81
-rw-r--r--dhall/src/syntax/ast/text.rs181
-rw-r--r--dhall/src/syntax/ast/visitor.rs360
8 files changed, 1569 insertions, 0 deletions
diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
new file mode 100644
index 0000000..5b9f401
--- /dev/null
+++ b/dhall/src/syntax/ast/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
+/// Returns `None` 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/ast/import.rs b/dhall/src/syntax/ast/import.rs
new file mode 100644
index 0000000..da3e99b
--- /dev/null
+++ b/dhall/src/syntax/ast/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/ast/label.rs b/dhall/src/syntax/ast/label.rs
new file mode 100644
index 0000000..43c3f53
--- /dev/null
+++ b/dhall/src/syntax/ast/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/ast/map.rs b/dhall/src/syntax/ast/map.rs
new file mode 100644
index 0000000..c4c6126
--- /dev/null
+++ b/dhall/src/syntax/ast/map.rs
@@ -0,0 +1,394 @@
+/// A sorted map that allows multiple values for each key.
+pub use dup_tree_map::DupTreeMap;
+pub use dup_tree_set::DupTreeSet;
+
+mod one_or_more {
+ use either::Either;
+ use std::{iter, slice, vec};
+
+ #[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord, Hash)]
+ pub enum OneOrMore<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/ast/mod.rs b/dhall/src/syntax/ast/mod.rs
new file mode 100644
index 0000000..1950154
--- /dev/null
+++ b/dhall/src/syntax/ast/mod.rs
@@ -0,0 +1,12 @@
+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 map;
+pub mod visitor;
diff --git a/dhall/src/syntax/ast/span.rs b/dhall/src/syntax/ast/span.rs
new file mode 100644
index 0000000..f9c7008
--- /dev/null
+++ b/dhall/src/syntax/ast/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/ast/text.rs b/dhall/src/syntax/ast/text.rs
new file mode 100644
index 0000000..fb390ee
--- /dev/null
+++ b/dhall/src/syntax/ast/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/ast/visitor.rs b/dhall/src/syntax/ast/visitor.rs
new file mode 100644
index 0000000..b76d037
--- /dev/null
+++ b/dhall/src/syntax/ast/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)
+ }
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-23 23:41:23 +0000