Merge pull request #131 from Nadrieril/hir

Decouple main expression types

3 files changed, 127 insertions, 434 deletions

diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index b493fdb..a479b53 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -1,5 +1,6 @@
+use crate::semantics::Universe;
 use crate::syntax::map::{DupTreeMap, DupTreeSet};
-use crate::syntax::visitor::{self, ExprKindMutVisitor, ExprKindVisitor};
+use crate::syntax::visitor;
 use crate::syntax::*;
 
 pub type Integer = isize;
@@ -18,6 +19,12 @@ pub enum Const {
     Sort,
 }
 
+impl Const {
+    pub(crate) fn to_universe(self) -> Universe {
+        Universe::from_const(self)
+    }
+}
+
 /// Bound variable
 ///
 /// The `Label` field is the variable's name (i.e. \"`x`\").
@@ -96,20 +103,34 @@ pub enum Builtin {
 
 // Each node carries an annotation.
 #[derive(Debug, Clone)]
-pub struct Expr<Embed> {
-    kind: Box<ExprKind<Expr<Embed>, Embed>>,
+pub struct Expr {
+    kind: Box<ExprKind<Expr>>,
     span: Span,
 }
 
-pub type UnspannedExpr<Embed> = ExprKind<Expr<Embed>, Embed>;
+pub type UnspannedExpr = ExprKind<Expr>;
+
+/// Simple literals
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
+pub enum LitKind {
+    ///  `True`
+    Bool(bool),
+    ///  `1`
+    Natural(Natural),
+    ///  `+2`
+    Integer(Integer),
+    ///  `3.24`
+    Double(Double),
+}
 
 /// 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 ExprKind<SubExpr, Embed> {
+pub enum ExprKind<SubExpr> {
     Const(Const),
+    Lit(LitKind),
     ///  `x`
     ///  `x@n`
     Var(V),
@@ -131,16 +152,8 @@ pub enum ExprKind<SubExpr, Embed> {
     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`
@@ -169,29 +182,21 @@ pub enum ExprKind<SubExpr, Embed> {
     Completion(SubExpr, SubExpr),
     /// `./some/path`
     Import(Import<SubExpr>),
-    /// Embeds the result of resolving an import
-    Embed(Embed),
 }
 
-impl<SE, E> ExprKind<SE, E> {
+impl<SE> ExprKind<SE> {
     pub fn traverse_ref_maybe_binder<'a, SE2, Err>(
         &'a self,
         visit: impl FnMut(Option<&'a Label>, &'a SE) -> Result<SE2, Err>,
-    ) -> Result<ExprKind<SE2, E>, Err>
-    where
-        E: Clone,
-    {
-        visitor::TraverseRefMaybeBinderVisitor(visit).visit(self)
+    ) -> Result<ExprKind<SE2>, Err> {
+        visitor::visit_ref(self, visit)
     }
 
     pub fn traverse_ref_with_special_handling_of_binders<'a, SE2, Err>(
         &'a self,
         mut visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
         mut visit_under_binder: impl FnMut(&'a Label, &'a SE) -> Result<SE2, Err>,
-    ) -> Result<ExprKind<SE2, E>, Err>
-    where
-        E: Clone,
-    {
+    ) -> Result<ExprKind<SE2>, Err> {
         self.traverse_ref_maybe_binder(|l, x| match l {
             None => visit_subexpr(x),
             Some(l) => visit_under_binder(l, x),
@@ -201,27 +206,14 @@ impl<SE, E> ExprKind<SE, E> {
     pub(crate) fn traverse_ref<'a, SE2, Err>(
         &'a self,
         mut visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
-    ) -> Result<ExprKind<SE2, E>, Err>
-    where
-        E: Clone,
-    {
+    ) -> Result<ExprKind<SE2>, Err> {
         self.traverse_ref_maybe_binder(|_, e| visit_subexpr(e))
     }
 
-    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_maybe_binder<'a, SE2>(
         &'a self,
         mut map: impl FnMut(Option<&'a Label>, &'a SE) -> SE2,
-    ) -> ExprKind<SE2, E>
-    where
-        E: Clone,
-    {
+    ) -> ExprKind<SE2> {
         trivial_result(self.traverse_ref_maybe_binder(|l, x| Ok(map(l, x))))
     }
 
@@ -229,10 +221,7 @@ impl<SE, E> ExprKind<SE, E> {
         &'a self,
         mut map_subexpr: impl FnMut(&'a SE) -> SE2,
         mut map_under_binder: impl FnMut(&'a Label, &'a SE) -> SE2,
-    ) -> ExprKind<SE2, E>
-    where
-        E: Clone,
-    {
+    ) -> ExprKind<SE2> {
         self.map_ref_maybe_binder(|l, x| match l {
             None => map_subexpr(x),
             Some(l) => map_under_binder(l, x),
@@ -242,34 +231,30 @@ impl<SE, E> ExprKind<SE, E> {
     pub fn map_ref<'a, SE2>(
         &'a self,
         mut map_subexpr: impl FnMut(&'a SE) -> SE2,
-    ) -> ExprKind<SE2, E>
-    where
-        E: Clone,
-    {
+    ) -> ExprKind<SE2> {
         self.map_ref_maybe_binder(|_, e| map_subexpr(e))
     }
-
-    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) -> &UnspannedExpr<E> {
+impl Expr {
+    pub fn as_ref(&self) -> &UnspannedExpr {
+        &self.kind
+    }
+    pub fn kind(&self) -> &UnspannedExpr {
         &self.kind
     }
     pub fn span(&self) -> Span {
         self.span.clone()
     }
 
-    pub fn new(kind: UnspannedExpr<E>, span: Span) -> Self {
+    pub fn new(kind: UnspannedExpr, span: Span) -> Self {
         Expr {
             kind: Box::new(kind),
             span,
         }
     }
 
-    pub fn rewrap<E2>(&self, kind: UnspannedExpr<E2>) -> Expr<E2> {
+    pub fn rewrap(&self, kind: UnspannedExpr) -> Expr {
         Expr {
             kind: Box::new(kind),
             span: self.span.clone(),
@@ -281,43 +266,6 @@ impl<E> Expr<E> {
             span,
         }
     }
-
-    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.kind.as_mut() {
-            ExprKind::BinOp(BinOp::ImportAlt, l, r) => {
-                let garbage_expr = ExprKind::BoolLit(false);
-                let new_self = if l.traverse_resolve_mut(f).is_ok() {
-                    l
-                } else {
-                    r.traverse_resolve_mut(f)?;
-                    r
-                };
-                *self.kind =
-                    std::mem::replace(new_self.kind.as_mut(), garbage_expr);
-            }
-            _ => {
-                self.kind.traverse_mut(|e| e.traverse_resolve_mut(f))?;
-                if let ExprKind::Import(import) = self.kind.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.kind = ExprKind::Embed(f(import)?);
-                }
-            }
-        }
-        Ok(())
-    }
 }
 
 pub fn trivial_result<T>(x: Result<T, !>) -> T {
@@ -362,15 +310,15 @@ impl From<Label> for V {
     }
 }
 
-impl<Embed: PartialEq> std::cmp::PartialEq for Expr<Embed> {
+impl std::cmp::PartialEq for Expr {
     fn eq(&self, other: &Self) -> bool {
         self.kind == other.kind
     }
 }
 
-impl<Embed: Eq> std::cmp::Eq for Expr<Embed> {}
+impl std::cmp::Eq for Expr {}
 
-impl<Embed: std::hash::Hash> std::hash::Hash for Expr<Embed> {
+impl std::hash::Hash for Expr {
     fn hash<H>(&self, state: &mut H)
     where
         H: std::hash::Hasher,
diff --git a/dhall/src/syntax/ast/import.rs b/dhall/src/syntax/ast/import.rs
index da3e99b..7bde6e0 100644
--- a/dhall/src/syntax/ast/import.rs
+++ b/dhall/src/syntax/ast/import.rs
@@ -75,15 +75,6 @@ impl<SE> URL<SE> {
             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> {
@@ -99,15 +90,6 @@ impl<SE> ImportLocation<SE> {
             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> {
@@ -121,10 +103,4 @@ impl<SE> Import<SE> {
             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/visitor.rs b/dhall/src/syntax/ast/visitor.rs
index 6a1ce7d..c361bc1 100644
--- a/dhall/src/syntax/ast/visitor.rs
+++ b/dhall/src/syntax/ast/visitor.rs
@@ -2,343 +2,112 @@ use std::iter::FromIterator;
 
 use crate::syntax::*;
 
-/// A visitor trait that can be used to traverse `ExprKind`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 ExprKindVisitor<'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 ExprKind<SE1, E1>,
-    ) -> Result<ExprKind<SE2, E2>, Self::Error> {
-        visit_ref(self, input)
-    }
+fn vec<'a, T, U, Err>(
+    x: &'a [T],
+    f: impl FnMut(&'a T) -> Result<U, Err>,
+) -> Result<Vec<U>, Err> {
+    x.iter().map(f).collect()
 }
 
-/// Like `ExprKindVisitor`, but by mutable reference
-pub trait ExprKindMutVisitor<'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 opt<'a, T, U, Err>(
+    x: &'a Option<T>,
+    f: impl FnOnce(&'a T) -> Result<U, Err>,
+) -> Result<Option<U>, Err> {
+    Ok(match x {
+        Some(x) => Some(f(x)?),
+        None => None,
+    })
+}
 
-    fn visit(self, input: &'a mut ExprKind<SE, E>) -> Result<(), Self::Error> {
-        visit_mut(self, input)
-    }
+fn dupmap<'a, SE1, SE2, T, Err>(
+    x: impl IntoIterator<Item = (&'a Label, &'a SE1)>,
+    mut f: impl FnMut(&'a SE1) -> Result<SE2, Err>,
+) -> Result<T, Err>
+where
+    SE1: 'a,
+    T: FromIterator<(Label, SE2)>,
+{
+    x.into_iter().map(|(k, x)| Ok((k.clone(), f(x)?))).collect()
 }
 
-fn visit_ref<'a, V, SE1, SE2, E1, E2>(
-    mut v: V,
-    input: &'a ExprKind<SE1, E1>,
-) -> Result<ExprKind<SE2, E2>, V::Error>
+fn optdupmap<'a, SE1, SE2, T, Err>(
+    x: impl IntoIterator<Item = (&'a Label, &'a Option<SE1>)>,
+    mut f: impl FnMut(&'a SE1) -> Result<SE2, Err>,
+) -> Result<T, Err>
 where
-    V: ExprKindVisitor<'a, SE1, SE2, E1, E2>,
+    SE1: 'a,
+    T: FromIterator<(Label, Option<SE2>)>,
 {
-    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,
+    x.into_iter()
+        .map(|(k, x)| {
+            Ok((
+                k.clone(),
+                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: ExprKindVisitor<'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: ExprKindVisitor<'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()
+        .collect()
+}
+
+pub(crate) fn visit_ref<'a, F, SE1, SE2, Err>(
+    input: &'a ExprKind<SE1>,
+    mut f: F,
+) -> Result<ExprKind<SE2>, Err>
+where
+    F: FnMut(Option<&'a Label>, &'a SE1) -> Result<SE2, Err>,
+{
+    // Can't use closures because of borrowing rules
+    macro_rules! expr {
+        ($e:expr) => {
+            f(None, $e)
+        };
+        ($l:expr, $e:expr) => {
+            f(Some($l), $e)
+        };
     }
 
     use crate::syntax::ExprKind::*;
     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)?;
+            let t = expr!(t)?;
+            let e = expr!(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)?;
+            let t = expr!(t)?;
+            let e = expr!(l, e)?;
             Pi(l.clone(), t, e)
         }
         Let(l, t, a, e) => {
-            let t = opt(t, &mut |e| v.visit_subexpr(e))?;
-            let a = v.visit_subexpr(a)?;
-            let e = v.visit_subexpr_under_binder(l, e)?;
+            let t = opt(t, &mut |e| expr!(e))?;
+            let a = expr!(a)?;
+            let e = expr!(l, e)?;
             Let(l.clone(), t, a, e)
         }
-        App(f, a) => App(v.visit_subexpr(f)?, v.visit_subexpr(a)?),
-        Annot(x, t) => Annot(v.visit_subexpr(x)?, v.visit_subexpr(t)?),
+        App(f, a) => App(expr!(f)?, expr!(a)?),
+        Annot(x, t) => Annot(expr!(x)?, expr!(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)?)
-        }
-        Completion(e, x) => {
-            Completion(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)?),
+        Lit(l) => Lit(l.clone()),
+        TextLit(t) => TextLit(t.traverse_ref(|e| expr!(e))?),
+        BinOp(o, x, y) => BinOp(*o, expr!(x)?, expr!(y)?),
+        BoolIf(b, t, f) => BoolIf(expr!(b)?, expr!(t)?, expr!(f)?),
+        EmptyListLit(t) => EmptyListLit(expr!(t)?),
+        NEListLit(es) => NEListLit(vec(es, |e| expr!(e))?),
+        SomeLit(e) => SomeLit(expr!(e)?),
+        RecordType(kts) => RecordType(dupmap(kts, |e| expr!(e))?),
+        RecordLit(kvs) => RecordLit(dupmap(kvs, |e| expr!(e))?),
+        UnionType(kts) => UnionType(optdupmap(kts, |e| expr!(e))?),
+        Merge(x, y, t) => Merge(expr!(x)?, expr!(y)?, opt(t, |e| expr!(e))?),
+        ToMap(x, t) => ToMap(expr!(x)?, opt(t, |e| expr!(e))?),
+        Field(e, l) => Field(expr!(e)?, l.clone()),
+        Projection(e, ls) => Projection(expr!(e)?, ls.clone()),
+        ProjectionByExpr(e, x) => ProjectionByExpr(expr!(e)?, expr!(x)?),
+        Completion(e, x) => Completion(expr!(e)?, expr!(x)?),
+        Assert(e) => Assert(expr!(e)?),
+        Import(i) => Import(i.traverse_ref(|e| expr!(e))?),
     })
 }
-
-fn visit_mut<'a, V, SE, E>(
-    mut v: V,
-    input: &'a mut ExprKind<SE, E>,
-) -> Result<(), V::Error>
-where
-    V: ExprKindMutVisitor<'a, SE, E>,
-{
-    fn vec<'a, V, SE, E>(v: &mut V, x: &'a mut Vec<SE>) -> Result<(), V::Error>
-    where
-        V: ExprKindMutVisitor<'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: ExprKindMutVisitor<'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: ExprKindMutVisitor<'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: ExprKindMutVisitor<'a, SE, E>,
-    {
-        for (_, x) in x {
-            opt(&mut v, x)?;
-        }
-        Ok(())
-    }
-
-    use crate::syntax::ExprKind::*;
-    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)?;
-        }
-        Completion(x, y) => {
-            v.visit_subexpr(x)?;
-            v.visit_subexpr(y)?;
-        }
-        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 TraverseRefMaybeBinderVisitor<F>(pub F);
-
-impl<'a, SE, E, SE2, Err, F> ExprKindVisitor<'a, SE, SE2, E, E>
-    for TraverseRefMaybeBinderVisitor<F>
-where
-    SE: 'a,
-    E: 'a + Clone,
-    F: FnMut(Option<&'a Label>, &'a SE) -> Result<SE2, Err>,
-{
-    type Error = Err;
-
-    fn visit_subexpr(&mut self, subexpr: &'a SE) -> Result<SE2, Self::Error> {
-        (self.0)(None, subexpr)
-    }
-    fn visit_subexpr_under_binder(
-        mut self,
-        label: &'a Label,
-        subexpr: &'a SE,
-    ) -> Result<SE2, Self::Error> {
-        (self.0)(Some(label), 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> ExprKindMutVisitor<'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)
-    }
-}