Resolve by ref instead of by mut

3 files changed, 81 insertions, 274 deletions

diff --git a/dhall/src/semantics/resolve.rs b/dhall/src/semantics/resolve.rs
index 5ec6192..223cfa4 100644
--- a/dhall/src/semantics/resolve.rs
+++ b/dhall/src/semantics/resolve.rs
@@ -3,7 +3,7 @@ use std::path::{Path, PathBuf};
 
 use crate::error::{Error, ImportError};
 use crate::syntax;
-use crate::syntax::{FilePath, ImportLocation, URL};
+use crate::syntax::{BinOp, Expr, ExprKind, FilePath, ImportLocation, URL};
 use crate::{Normalized, NormalizedExpr, Parsed, Resolved};
 
 type Import = syntax::Import<NormalizedExpr>;
@@ -30,27 +30,40 @@ impl ResolveEnv {
             stack: Vec::new(),
         }
     }
-    pub fn to_import_stack(&self) -> ImportStack {
-        self.stack.clone()
-    }
-    pub fn check_cyclic_import(&self, import: &Import) -> bool {
-        self.stack.contains(import)
-    }
-    pub fn get_from_cache(&self, import: &Import) -> Option<&Normalized> {
-        self.cache.get(import)
-    }
-    pub fn push_on_stack(&mut self, import: Import) {
-        self.stack.push(import)
-    }
-    pub fn pop_from_stack(&mut self) {
-        self.stack.pop();
-    }
-    pub fn insert_cache(&mut self, import: Import, expr: Normalized) {
-        self.cache.insert(import, expr);
+
+    pub fn handle_import(
+        &mut self,
+        import: Import,
+        mut do_resolve: impl FnMut(
+            &mut Self,
+            &Import,
+        ) -> Result<Normalized, ImportError>,
+    ) -> Result<Normalized, ImportError> {
+        if self.stack.contains(&import) {
+            return Err(ImportError::ImportCycle(self.stack.clone(), import));
+        }
+        Ok(match self.cache.get(&import) {
+            Some(expr) => expr.clone(),
+            None => {
+                // Push the current import on the stack
+                self.stack.push(import.clone());
+
+                // Resolve the import recursively
+                let expr = do_resolve(self, &import)?;
+
+                // Remove import from the stack.
+                self.stack.pop();
+
+                // Add the import to the cache
+                self.cache.insert(import, expr.clone());
+
+                expr
+            }
+        })
     }
 }
 
-fn resolve_import(
+fn resolve_one_import(
     env: &mut ResolveEnv,
     import: &Import,
     root: &ImportRoot,
@@ -79,59 +92,64 @@ fn resolve_import(
 }
 
 fn load_import(env: &mut ResolveEnv, f: &Path) -> Result<Normalized, Error> {
-    Ok(do_resolve_expr(env, Parsed::parse_file(f)?)?
-        .typecheck()?
-        .normalize())
+    let parsed = Parsed::parse_file(f)?;
+    Ok(resolve_with_env(env, parsed)?.typecheck()?.normalize())
 }
 
-fn do_resolve_expr(
+/// Traverse the expression, handling import alternatives and passing
+/// found imports to the provided function.
+fn traverse_resolve_expr(
+    expr: &Expr<Normalized>,
+    f: &mut impl FnMut(Import) -> Result<Normalized, ImportError>,
+) -> Result<Expr<Normalized>, ImportError> {
+    Ok(match expr.kind() {
+        ExprKind::BinOp(BinOp::ImportAlt, l, r) => {
+            match traverse_resolve_expr(l, f) {
+                Ok(l) => l,
+                Err(_) => {
+                    match traverse_resolve_expr(r, f) {
+                        Ok(r) => r,
+                        // TODO: keep track of the other error too
+                        Err(e) => return Err(e),
+                    }
+                }
+            }
+        }
+        kind => {
+            let kind = kind.traverse_ref(|e| traverse_resolve_expr(e, f))?;
+            expr.rewrap(match kind {
+                ExprKind::Import(import) => ExprKind::Embed(f(import)?),
+                kind => kind,
+            })
+        }
+    })
+}
+
+fn resolve_with_env(
     env: &mut ResolveEnv,
     parsed: Parsed,
 ) -> Result<Resolved, ImportError> {
-    let Parsed(mut expr, root) = parsed;
-    let mut resolve = |import: Import| -> Result<Normalized, ImportError> {
-        if env.check_cyclic_import(&import) {
-            return Err(ImportError::ImportCycle(
-                env.to_import_stack(),
-                import,
-            ));
-        }
-        match env.get_from_cache(&import) {
-            Some(expr) => Ok(expr.clone()),
-            None => {
-                // Push the current import on the stack
-                env.push_on_stack(import.clone());
-
-                // Resolve the import recursively
-                let expr = resolve_import(env, &import, &root)?;
-
-                // Remove import from the stack.
-                env.pop_from_stack();
-
-                // Add the import to the cache
-                env.insert_cache(import, expr.clone());
-
-                Ok(expr)
-            }
-        }
-    };
-    expr.traverse_resolve_mut(&mut resolve)?;
-    Ok(Resolved(expr))
+    let Parsed(expr, root) = parsed;
+    let resolved = traverse_resolve_expr(&expr, &mut |import| {
+        env.handle_import(import, |env, import| {
+            resolve_one_import(env, import, &root)
+        })
+    })?;
+    Ok(Resolved(resolved))
 }
 
-pub(crate) fn resolve(e: Parsed) -> Result<Resolved, ImportError> {
-    do_resolve_expr(&mut ResolveEnv::new(), e)
+pub(crate) fn resolve(parsed: Parsed) -> Result<Resolved, ImportError> {
+    resolve_with_env(&mut ResolveEnv::new(), parsed)
 }
 
 pub(crate) fn skip_resolve_expr(
     parsed: Parsed,
 ) -> Result<Resolved, ImportError> {
-    let mut expr = parsed.0;
-    let mut resolve = |import: Import| -> Result<Normalized, ImportError> {
+    let Parsed(expr, _) = parsed;
+    let resolved = traverse_resolve_expr(&expr, &mut |import| {
         Err(ImportError::UnexpectedImport(import))
-    };
-    expr.traverse_resolve_mut(&mut resolve)?;
-    Ok(Resolved(expr))
+    })?;
+    Ok(Resolved(resolved))
 }
 
 pub trait Canonicalize {
diff --git a/dhall/src/syntax/ast/expr.rs b/dhall/src/syntax/ast/expr.rs
index b493fdb..420df5b 100644
--- a/dhall/src/syntax/ast/expr.rs
+++ b/dhall/src/syntax/ast/expr.rs
@@ -1,5 +1,5 @@
 use crate::syntax::map::{DupTreeMap, DupTreeSet};
-use crate::syntax::visitor::{self, ExprKindMutVisitor, ExprKindVisitor};
+use crate::syntax::visitor::{self, ExprKindVisitor};
 use crate::syntax::*;
 
 pub type Integer = isize;
@@ -208,13 +208,6 @@ impl<SE, E> ExprKind<SE, E> {
         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,
@@ -248,16 +241,15 @@ impl<SE, E> ExprKind<SE, E> {
     {
         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> {
         &self.kind
     }
+    pub fn kind(&self) -> &UnspannedExpr<E> {
+        &self.kind
+    }
     pub fn span(&self) -> Span {
         self.span.clone()
     }
@@ -281,43 +273,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 {
diff --git a/dhall/src/syntax/ast/visitor.rs b/dhall/src/syntax/ast/visitor.rs
index 6a1ce7d..c09b8d4 100644
--- a/dhall/src/syntax/ast/visitor.rs
+++ b/dhall/src/syntax/ast/visitor.rs
@@ -32,29 +32,6 @@ pub trait ExprKindVisitor<'a, SE1, SE2, E1, E2>: Sized {
     }
 }
 
-/// 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 visit(self, input: &'a mut ExprKind<SE, E>) -> Result<(), Self::Error> {
-        visit_mut(self, input)
-    }
-}
-
 fn visit_ref<'a, V, SE1, SE2, E1, E2>(
     mut v: V,
     input: &'a ExprKind<SE1, E1>,
@@ -174,128 +151,6 @@ where
     })
 }
 
-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>
@@ -321,24 +176,3 @@ where
         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)
-    }
-}