Resolve imports by mutating Expr instead of cloning it

6 files changed, 421 insertions, 244 deletions

diff --git a/dhall/src/phase/resolve.rs b/dhall/src/phase/resolve.rs
index a58f5e4..32e90c8 100644
--- a/dhall/src/phase/resolve.rs
+++ b/dhall/src/phase/resolve.rs
@@ -58,18 +58,16 @@ fn load_import(
 }
 
 fn do_resolve_expr(
-    Parsed(expr, root): Parsed,
+    parsed: Parsed,
     import_cache: &mut ImportCache,
     import_stack: &ImportStack,
 ) -> Result<Resolved, ImportError> {
-    let resolve = |import: &Import| -> Result<Normalized, ImportError> {
-        if import_stack.contains(import) {
-            return Err(ImportError::ImportCycle(
-                import_stack.clone(),
-                import.clone(),
-            ));
+    let Parsed(mut expr, root) = parsed;
+    let mut resolve = |import: Import| -> Result<Normalized, ImportError> {
+        if import_stack.contains(&import) {
+            return Err(ImportError::ImportCycle(import_stack.clone(), import));
         }
-        match import_cache.get(import) {
+        match import_cache.get(&import) {
             Some(expr) => Ok(expr.clone()),
             None => {
                 // Copy the import stack and push the current import
@@ -77,16 +75,20 @@ fn do_resolve_expr(
                 import_stack.push(import.clone());
 
                 // Resolve the import recursively
-                let expr =
-                    resolve_import(import, &root, import_cache, &import_stack)?;
+                let expr = resolve_import(
+                    &import,
+                    &root,
+                    import_cache,
+                    &import_stack,
+                )?;
 
                 // Add the import to the cache
-                import_cache.insert(import.clone(), expr.clone());
+                import_cache.insert(import, expr.clone());
                 Ok(expr)
             }
         }
     };
-    let expr = expr.traverse_resolve(resolve)?;
+    expr.traverse_resolve_mut(&mut resolve)?;
     Ok(Resolved(expr))
 }
 
@@ -95,12 +97,13 @@ pub(crate) fn resolve(e: Parsed) -> Result<Resolved, ImportError> {
 }
 
 pub(crate) fn skip_resolve_expr(
-    Parsed(expr, _root): Parsed,
+    parsed: Parsed,
 ) -> Result<Resolved, ImportError> {
-    let resolve = |import: &Import| -> Result<Normalized, ImportError> {
-        Err(ImportError::UnexpectedImport(import.clone()))
+    let mut expr = parsed.0;
+    let mut resolve = |import: Import| -> Result<Normalized, ImportError> {
+        Err(ImportError::UnexpectedImport(import))
     };
-    let expr = expr.traverse_resolve(resolve)?;
+    expr.traverse_resolve_mut(&mut resolve)?;
     Ok(Resolved(expr))
 }
 
@@ -131,9 +134,9 @@ mod spec_tests {
     // import_success!(success_alternativeEnvNatural, "alternativeEnvNatural");
     // import_success!(success_alternativeEnvSimple, "alternativeEnvSimple");
     // import_success!(success_alternativeHashMismatch, "alternativeHashMismatch");
-    // import_success!(success_alternativeNatural, "alternativeNatural");
-    // import_success!(success_alternativeParseError, "alternativeParseError");
-    // import_success!(success_alternativeTypeError, "alternativeTypeError");
+    import_success!(success_alternativeNatural, "alternativeNatural");
+    import_success!(success_alternativeParseError, "alternativeParseError");
+    import_success!(success_alternativeTypeError, "alternativeTypeError");
     // import_success!(success_asLocation, "asLocation");
     // import_success!(success_asText, "asText");
     // import_success!(success_customHeaders, "customHeaders");
diff --git a/dhall_syntax/src/core/expr.rs b/dhall_syntax/src/core/expr.rs
index f46cafb..2cb23c9 100644
--- a/dhall_syntax/src/core/expr.rs
+++ b/dhall_syntax/src/core/expr.rs
@@ -1,7 +1,7 @@
 use std::rc::Rc;
 
 use crate::map::{DupTreeMap, DupTreeSet};
-use crate::visitor;
+use crate::visitor::{self, ExprFMutVisitor, ExprFVisitor};
 use crate::*;
 
 pub type Integer = isize;
@@ -256,13 +256,6 @@ pub enum ExprF<SubExpr, Embed> {
 }
 
 impl<SE, E> ExprF<SE, E> {
-    pub(crate) fn visit<'a, V, Return>(&'a self, v: V) -> Return
-    where
-        V: visitor::GenericVisitor<&'a ExprF<SE, E>, Return>,
-    {
-        v.visit(self)
-    }
-
     pub fn traverse_ref_with_special_handling_of_binders<'a, SE2, Err>(
         &'a self,
         visit_subexpr: impl FnMut(&'a SE) -> Result<SE2, Err>,
@@ -271,10 +264,11 @@ impl<SE, E> ExprF<SE, E> {
     where
         E: Clone,
     {
-        self.visit(visitor::TraverseRefWithBindersVisitor {
+        visitor::TraverseRefWithBindersVisitor {
             visit_subexpr,
             visit_under_binder,
-        })
+        }
+        .visit(self)
     }
 
     fn traverse_ref<'a, SE2, Err>(
@@ -284,7 +278,14 @@ impl<SE, E> ExprF<SE, E> {
     where
         E: Clone,
     {
-        self.visit(visitor::TraverseRefVisitor { visit_subexpr })
+        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>(
@@ -310,42 +311,9 @@ impl<SE, E> ExprF<SE, E> {
     {
         trivial_result(self.traverse_ref(|x| Ok(map_subexpr(x))))
     }
-}
-
-impl<E> RawExpr<E> {
-    pub fn traverse_resolve<Err>(
-        &self,
-        visit_import: impl FnMut(&Import<Expr<E>>) -> Result<E, Err>,
-    ) -> Result<RawExpr<E>, Err>
-    where
-        E: Clone,
-    {
-        self.traverse_resolve_with_visitor(&mut visitor::ResolveVisitor(
-            visit_import,
-        ))
-    }
 
-    pub(crate) fn traverse_resolve_with_visitor<Err, F1>(
-        &self,
-        visitor: &mut visitor::ResolveVisitor<F1>,
-    ) -> Result<RawExpr<E>, Err>
-    where
-        E: Clone,
-        F1: FnMut(&Import<Expr<E>>) -> Result<E, Err>,
-    {
-        match self {
-            ExprF::BinOp(BinOp::ImportAlt, l, r) => l
-                .as_ref()
-                .traverse_resolve_with_visitor(visitor)
-                .or_else(|_| r.as_ref().traverse_resolve_with_visitor(visitor)),
-            _ => {
-                let e = self.visit(&mut *visitor)?;
-                Ok(match &e {
-                    ExprF::Import(import) => ExprF::Embed((visitor.0)(import)?),
-                    _ => 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))))
     }
 }
 
@@ -353,6 +321,9 @@ 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 new(x: RawExpr<E>, n: Span) -> Self {
         Expr(Box::new((x, Some(n))))
@@ -369,17 +340,42 @@ impl<E> Expr<E> {
     pub fn rewrap<E2>(&self, x: RawExpr<E2>) -> Expr<E2> {
         Expr(Box::new((x, (self.0).1.clone())))
     }
-}
 
-impl<E> Expr<E> {
-    pub fn traverse_resolve<Err>(
-        &self,
-        visit_import: impl FnMut(&Import<Expr<E>>) -> Result<E, Err>,
-    ) -> Result<Expr<E>, Err>
+    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>,
     {
-        Ok(self.rewrap(self.as_ref().traverse_resolve(visit_import)?))
+        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(())
     }
 }
 
diff --git a/dhall_syntax/src/core/import.rs b/dhall_syntax/src/core/import.rs
index d1f3fca..43597df 100644
--- a/dhall_syntax/src/core/import.rs
+++ b/dhall_syntax/src/core/import.rs
@@ -57,7 +57,7 @@ pub struct Import<SubExpr> {
 }
 
 impl<SE> URL<SE> {
-    pub fn visit_subexpr<'a, Err, SE2>(
+    pub fn traverse_ref<'a, Err, SE2>(
         &'a self,
         f: impl FnOnce(&'a SE) -> Result<SE2, Err>,
     ) -> Result<URL<SE2>, Err> {
@@ -70,32 +70,56 @@ 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> {
-    pub fn visit_subexpr<'a, Err, SE2>(
+    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.visit_subexpr(f)?),
+            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 visit_subexpr<'a, Err, SE2>(
+    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.visit_subexpr(f)?,
+            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_syntax/src/core/map.rs b/dhall_syntax/src/core/map.rs
index 6a0ebda..c4c6126 100644
--- a/dhall_syntax/src/core/map.rs
+++ b/dhall_syntax/src/core/map.rs
@@ -13,6 +13,8 @@ mod one_or_more {
     }
 
     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> {
@@ -36,6 +38,13 @@ mod one_or_more {
                 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> {
@@ -76,6 +85,19 @@ mod dup_tree_map {
         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<
@@ -134,6 +156,21 @@ mod dup_tree_map {
                 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>
@@ -180,6 +217,18 @@ mod dup_tree_map {
         }
     }
 
+    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,
@@ -212,6 +261,22 @@ mod dup_tree_map {
         }
     }
 
+    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,
diff --git a/dhall_syntax/src/core/text.rs b/dhall_syntax/src/core/text.rs
index 10fd68a..e17f00f 100644
--- a/dhall_syntax/src/core/text.rs
+++ b/dhall_syntax/src/core/text.rs
@@ -76,6 +76,16 @@ impl<SubExpr> InterpolatedText<SubExpr> {
         })
     }
 
+    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 {
diff --git a/dhall_syntax/src/core/visitor.rs b/dhall_syntax/src/core/visitor.rs
index addb282..39a027f 100644
--- a/dhall_syntax/src/core/visitor.rs
+++ b/dhall_syntax/src/core/visitor.rs
@@ -1,11 +1,6 @@
 use crate::*;
 use std::iter::FromIterator;
 
-/// A way too generic Visitor trait.
-pub trait GenericVisitor<Input, Output>: Sized {
-    fn visit(self, input: Input) -> Output;
-}
-
 /// 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
@@ -14,7 +9,7 @@ pub trait GenericVisitor<Input, Output>: Sized {
 /// 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 ExprFFallibleVisitor<'a, SE1, SE2, E1, E2>: Sized {
+pub trait ExprFVisitor<'a, SE1, SE2, E1, E2>: Sized {
     type Error;
 
     fn visit_subexpr(&mut self, subexpr: &'a SE1) -> Result<SE2, Self::Error>;
@@ -27,174 +22,263 @@ pub trait ExprFFallibleVisitor<'a, SE1, SE2, E1, E2>: Sized {
     ) -> 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 ExprFFallibleVisitor, but without the error handling.
-pub trait ExprFInFallibleVisitor<'a, SE1, SE2, E1, E2>: Sized {
-    fn visit_subexpr(&mut self, subexpr: &'a SE1) -> SE2;
-    fn visit_embed(self, embed: &'a E1) -> E2;
+/// 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 Label,
-        subexpr: &'a SE1,
-    ) -> SE2 {
+        _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)
+    }
 }
 
-impl<'a, T, SE1, SE2, E1, E2>
-    GenericVisitor<&'a ExprF<SE1, E1>, Result<ExprF<SE2, E2>, T::Error>> for T
+fn visit_ref<'a, V, SE1, SE2, E1, E2>(
+    mut v: V,
+    input: &'a ExprF<SE1, E1>,
+) -> Result<ExprF<SE2, E2>, V::Error>
 where
-    T: ExprFFallibleVisitor<'a, SE1, SE2, E1, E2>,
+    V: ExprFVisitor<'a, SE1, SE2, E1, E2>,
 {
-    fn visit(
-        self,
-        input: &'a ExprF<SE1, E1>,
-    ) -> Result<ExprF<SE2, E2>, 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 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::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)
         }
-        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: ExprFFallibleVisitor<'a, SE1, SE2, E1, E2>,
-        {
-            x.into_iter()
-                .map(|(k, x)| Ok((k.clone(), v.visit_subexpr(x)?)))
-                .collect()
+        Pi(l, t, e) => {
+            let t = v.visit_subexpr(t)?;
+            let e = v.visit_subexpr_under_binder(l, e)?;
+            Pi(l.clone(), t, e)
         }
-        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: ExprFFallibleVisitor<'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()
+        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)
         }
-
-        let mut v = self;
-        use crate::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()),
-            Assert(e) => Assert(v.visit_subexpr(e)?),
-            Import(i) => Import(i.visit_subexpr(|e| v.visit_subexpr(e))?),
-            Embed(a) => Embed(v.visit_embed(a)?),
-        })
-    }
+        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()),
+        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)?),
+    })
 }
 
-impl<'a, T, SE1, SE2, E1, E2> GenericVisitor<&'a ExprF<SE1, E1>, ExprF<SE2, E2>>
-    for T
+fn visit_mut<'a, V, SE, E>(
+    mut v: V,
+    input: &'a mut ExprF<SE, E>,
+) -> Result<(), V::Error>
 where
-    T: ExprFInFallibleVisitor<'a, SE1, SE2, E1, E2>,
+    V: ExprFMutVisitor<'a, SE, E>,
 {
-    fn visit(self, input: &'a ExprF<SE1, E1>) -> ExprF<SE2, E2> {
-        trivial_result(InfallibleWrapper(self).visit(input))
+    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(())
     }
-}
-
-struct InfallibleWrapper<T>(T);
-
-impl<'a, T, SE1, SE2, E1, E2> ExprFFallibleVisitor<'a, SE1, SE2, E1, E2>
-    for InfallibleWrapper<T>
-where
-    T: ExprFInFallibleVisitor<'a, SE1, SE2, E1, E2>,
-{
-    type Error = !;
-
-    fn visit_subexpr(&mut self, subexpr: &'a SE1) -> Result<SE2, Self::Error> {
-        Ok(self.0.visit_subexpr(subexpr))
+    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 visit_embed(self, embed: &'a E1) -> Result<E2, Self::Error> {
-        Ok(self.0.visit_embed(embed))
+    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(())
     }
 
-    fn visit_subexpr_under_binder(
-        self,
-        label: &'a Label,
-        subexpr: &'a SE1,
-    ) -> Result<SE2, Self::Error> {
-        Ok(self.0.visit_subexpr_under_binder(label, subexpr))
+    use crate::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)?,
+        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> {
@@ -202,7 +286,7 @@ pub struct TraverseRefWithBindersVisitor<F1, F2> {
     pub visit_under_binder: F2,
 }
 
-impl<'a, SE, E, SE2, Err, F1, F2> ExprFFallibleVisitor<'a, SE, SE2, E, E>
+impl<'a, SE, E, SE2, Err, F1, F2> ExprFVisitor<'a, SE, SE2, E, E>
     for TraverseRefWithBindersVisitor<F1, F2>
 where
     SE: 'a,
@@ -231,7 +315,7 @@ pub struct TraverseRefVisitor<F1> {
     pub visit_subexpr: F1,
 }
 
-impl<'a, SE, E, SE2, Err, F1> ExprFFallibleVisitor<'a, SE, SE2, E, E>
+impl<'a, SE, E, SE2, Err, F1> ExprFVisitor<'a, SE, SE2, E, E>
     for TraverseRefVisitor<F1>
 where
     SE: 'a,
@@ -248,27 +332,22 @@ where
     }
 }
 
-pub struct ResolveVisitor<F1>(pub F1);
+pub struct TraverseMutVisitor<F1> {
+    pub visit_subexpr: F1,
+}
 
-impl<'a, 'b, E, Err, F1> ExprFFallibleVisitor<'a, Expr<E>, Expr<E>, E, E>
-    for &'b mut ResolveVisitor<F1>
+impl<'a, SE, E, Err, F1> ExprFMutVisitor<'a, SE, E> for TraverseMutVisitor<F1>
 where
-    E: Clone,
-    F1: FnMut(&Import<Expr<E>>) -> Result<E, Err>,
+    SE: 'a,
+    E: 'a,
+    F1: FnMut(&'a mut SE) -> Result<(), Err>,
 {
     type Error = Err;
 
     fn visit_subexpr(
         &mut self,
-        subexpr: &'a Expr<E>,
-    ) -> Result<Expr<E>, Self::Error> {
-        Ok(subexpr.rewrap(
-            subexpr
-                .as_ref()
-                .traverse_resolve_with_visitor(&mut **self)?,
-        ))
-    }
-    fn visit_embed(self, embed: &'a E) -> Result<E, Self::Error> {
-        Ok(embed.clone())
+        subexpr: &'a mut SE,
+    ) -> Result<(), Self::Error> {
+        (self.visit_subexpr)(subexpr)
     }
 }