Merge pull request #204 from Nadrieril/source-id

4 files changed, 342 insertions, 171 deletions

diff --git a/dhall/src/semantics/resolve/cache.rs b/dhall/src/semantics/resolve/cache.rs
index b00a2d5..1fc8dd3 100644
--- a/dhall/src/semantics/resolve/cache.rs
+++ b/dhall/src/semantics/resolve/cache.rs
@@ -5,7 +5,7 @@ use std::path::{Path, PathBuf};
 use crate::error::{CacheError, Error};
 use crate::parse::parse_binary;
 use crate::syntax::{binary, Hash};
-use crate::Typed;
+use crate::{Ctxt, Typed};
 use std::ffi::OsStr;
 use std::fs::File;
 
@@ -52,9 +52,13 @@ impl Cache {
         self.cache_dir.join(filename_for_hash(hash))
     }
 
-    pub fn get(&self, hash: &Hash) -> Result<Typed, Error> {
+    pub fn get<'cx>(
+        &self,
+        cx: Ctxt<'cx>,
+        hash: &Hash,
+    ) -> Result<Typed<'cx>, Error> {
         let path = self.entry_path(hash);
-        let res = read_cache_file(&path, hash);
+        let res = read_cache_file(cx, &path, hash);
         if res.is_err() && path.exists() {
             // Delete cache file since it's invalid. We ignore the error.
             let _ = std::fs::remove_file(&path);
@@ -62,14 +66,23 @@ impl Cache {
         res
     }
 
-    pub fn insert(&self, hash: &Hash, expr: &Typed) -> Result<(), Error> {
+    pub fn insert<'cx>(
+        &self,
+        cx: Ctxt<'cx>,
+        hash: &Hash,
+        expr: &Typed<'cx>,
+    ) -> Result<(), Error> {
         let path = self.entry_path(hash);
-        write_cache_file(&path, expr)
+        write_cache_file(cx, &path, expr)
     }
 }
 
 /// Read a file from the cache, also checking that its hash is valid.
-fn read_cache_file(path: &Path, hash: &Hash) -> Result<Typed, Error> {
+fn read_cache_file<'cx>(
+    cx: Ctxt<'cx>,
+    path: &Path,
+    hash: &Hash,
+) -> Result<Typed<'cx>, Error> {
     let data = crate::utils::read_binary_file(path)?;
 
     match hash {
@@ -81,12 +94,16 @@ fn read_cache_file(path: &Path, hash: &Hash) -> Result<Typed, Error> {
         }
     }
 
-    Ok(parse_binary(&data)?.skip_resolve()?.typecheck()?)
+    Ok(parse_binary(&data)?.resolve(cx)?.typecheck(cx)?)
 }
 
 /// Write a file to the cache.
-fn write_cache_file(path: &Path, expr: &Typed) -> Result<(), Error> {
-    let data = binary::encode(&expr.to_expr())?;
+fn write_cache_file<'cx>(
+    cx: Ctxt<'cx>,
+    path: &Path,
+    expr: &Typed<'cx>,
+) -> Result<(), Error> {
+    let data = binary::encode(&expr.to_expr(cx))?;
     File::create(path)?.write_all(data.as_slice())?;
     Ok(())
 }
diff --git a/dhall/src/semantics/resolve/env.rs b/dhall/src/semantics/resolve/env.rs
index 29dd16b..bde99d1 100644
--- a/dhall/src/semantics/resolve/env.rs
+++ b/dhall/src/semantics/resolve/env.rs
@@ -1,9 +1,9 @@
 use std::collections::HashMap;
 
 use crate::error::{Error, ImportError};
-use crate::semantics::{AlphaVar, Cache, ImportLocation, VarEnv};
+use crate::semantics::{check_hash, AlphaVar, Cache, ImportLocation, VarEnv};
 use crate::syntax::{Hash, Label, V};
-use crate::Typed;
+use crate::{Ctxt, ImportId, ImportResultId, Typed};
 
 /// Environment for resolving names.
 #[derive(Debug, Clone, Default)]
@@ -11,14 +11,13 @@ pub struct NameEnv {
     names: Vec<Label>,
 }
 
-pub type MemCache = HashMap<ImportLocation, Typed>;
 pub type CyclesStack = Vec<ImportLocation>;
 
 /// Environment for resolving imports
-#[derive(Debug)]
-pub struct ImportEnv {
-    disk_cache: Option<Cache>, // Missing if it failed to initialize
-    mem_cache: MemCache,
+pub struct ImportEnv<'cx> {
+    cx: Ctxt<'cx>,
+    disk_cache: Option<Cache>, // `None` if it failed to initialize
+    mem_cache: HashMap<ImportLocation, ImportResultId<'cx>>,
     stack: CyclesStack,
 }
 
@@ -66,43 +65,61 @@ impl NameEnv {
     }
 }
 
-impl ImportEnv {
-    pub fn new() -> Self {
+impl<'cx> ImportEnv<'cx> {
+    pub fn new(cx: Ctxt<'cx>) -> Self {
         ImportEnv {
+            cx,
             disk_cache: Cache::new().ok(),
             mem_cache: Default::default(),
             stack: Default::default(),
         }
     }
 
+    pub fn cx(&self) -> Ctxt<'cx> {
+        self.cx
+    }
+
     pub fn get_from_mem_cache(
-        &mut self,
+        &self,
         location: &ImportLocation,
-    ) -> Option<Typed> {
-        Some(self.mem_cache.get(location)?.clone())
+    ) -> Option<ImportResultId<'cx>> {
+        Some(*self.mem_cache.get(location)?)
     }
 
     pub fn get_from_disk_cache(
-        &mut self,
+        &self,
         hash: &Option<Hash>,
-    ) -> Option<Typed> {
+    ) -> Option<Typed<'cx>> {
         let hash = hash.as_ref()?;
-        let expr = self.disk_cache.as_ref()?.get(hash).ok()?;
+        let expr = self.disk_cache.as_ref()?.get(self.cx(), hash).ok()?;
         Some(expr)
     }
 
+    pub fn check_hash(
+        &self,
+        import: ImportId<'cx>,
+        result: ImportResultId<'cx>,
+    ) -> Result<(), Error> {
+        check_hash(self.cx(), import, result)
+    }
+
     pub fn write_to_mem_cache(
         &mut self,
         location: ImportLocation,
-        expr: Typed,
+        result: ImportResultId<'cx>,
     ) {
-        self.mem_cache.insert(location, expr);
+        self.mem_cache.insert(location, result);
     }
 
-    pub fn write_to_disk_cache(&mut self, hash: &Option<Hash>, expr: &Typed) {
+    pub fn write_to_disk_cache(
+        &self,
+        hash: &Option<Hash>,
+        result: ImportResultId<'cx>,
+    ) {
         if let Some(disk_cache) = self.disk_cache.as_ref() {
             if let Some(hash) = hash {
-                let _ = disk_cache.insert(hash, &expr);
+                let expr = &self.cx()[result];
+                let _ = disk_cache.insert(self.cx(), hash, expr);
             }
         }
     }
@@ -110,8 +127,8 @@ impl ImportEnv {
     pub fn with_cycle_detection(
         &mut self,
         location: ImportLocation,
-        do_resolve: impl FnOnce(&mut Self) -> Result<Typed, Error>,
-    ) -> Result<Typed, Error> {
+        do_resolve: impl FnOnce(&mut Self) -> Result<Typed<'cx>, Error>,
+    ) -> Result<Typed<'cx>, Error> {
         if self.stack.contains(&location) {
             return Err(
                 ImportError::ImportCycle(self.stack.clone(), location).into()
diff --git a/dhall/src/semantics/resolve/hir.rs b/dhall/src/semantics/resolve/hir.rs
index 8869915..8baad10 100644
--- a/dhall/src/semantics/resolve/hir.rs
+++ b/dhall/src/semantics/resolve/hir.rs
@@ -1,7 +1,7 @@
 use crate::error::TypeError;
-use crate::semantics::{type_with, NameEnv, Nir, NzEnv, Tir, TyEnv, Type};
+use crate::semantics::{type_with, typecheck, NameEnv, Nir, NzEnv, Tir, TyEnv};
 use crate::syntax::{Expr, ExprKind, Span, V};
-use crate::ToExprOptions;
+use crate::{Ctxt, ImportAlternativeId, ImportId, ToExprOptions};
 
 /// Stores an alpha-normalized variable.
 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
@@ -10,19 +10,23 @@ pub struct AlphaVar {
 }
 
 #[derive(Debug, Clone, PartialEq, Eq)]
-pub enum HirKind {
+pub enum HirKind<'cx> {
     /// A resolved variable (i.e. a DeBruijn index)
     Var(AlphaVar),
-    /// Result of resolving an import.
-    Import(Hir, Type),
+    /// A variable that couldn't be resolved. Detected during resolution, but causes an error during typeck.
+    MissingVar(V),
+    /// An import. It must have been resolved after resolution.
+    Import(ImportId<'cx>),
+    /// An import alternative. It must have been decided after resolution.
+    ImportAlternative(ImportAlternativeId<'cx>, Hir<'cx>, Hir<'cx>),
     // Forbidden ExprKind variants: Var, Import, Completion
-    Expr(ExprKind<Hir>),
+    Expr(ExprKind<Hir<'cx>>),
 }
 
 // An expression with resolved variables and imports.
 #[derive(Debug, Clone)]
-pub struct Hir {
-    kind: Box<HirKind>,
+pub struct Hir<'cx> {
+    kind: Box<HirKind<'cx>>,
     span: Span,
 }
 
@@ -35,15 +39,15 @@ impl AlphaVar {
     }
 }
 
-impl Hir {
-    pub fn new(kind: HirKind, span: Span) -> Self {
+impl<'cx> Hir<'cx> {
+    pub fn new(kind: HirKind<'cx>, span: Span) -> Self {
         Hir {
             kind: Box::new(kind),
             span,
         }
     }
 
-    pub fn kind(&self) -> &HirKind {
+    pub fn kind(&self) -> &HirKind<'cx> {
         &*self.kind
     }
     pub fn span(&self) -> Span {
@@ -51,59 +55,78 @@ impl Hir {
     }
 
     /// Converts a closed Hir expr back to the corresponding AST expression.
-    pub fn to_expr(&self, opts: ToExprOptions) -> Expr {
-        hir_to_expr(self, opts, &mut NameEnv::new())
+    pub fn to_expr(&self, cx: Ctxt<'cx>, opts: ToExprOptions) -> Expr {
+        hir_to_expr(cx, self, opts, &mut NameEnv::new())
     }
     /// Converts a closed Hir expr back to the corresponding AST expression.
-    pub fn to_expr_noopts(&self) -> Expr {
+    pub fn to_expr_noopts(&self, cx: Ctxt<'cx>) -> Expr {
         let opts = ToExprOptions { alpha: false };
-        self.to_expr(opts)
+        self.to_expr(cx, opts)
     }
-    pub fn to_expr_alpha(&self) -> Expr {
+    pub fn to_expr_alpha(&self, cx: Ctxt<'cx>) -> Expr {
         let opts = ToExprOptions { alpha: true };
-        self.to_expr(opts)
+        self.to_expr(cx, opts)
     }
-    pub fn to_expr_tyenv(&self, env: &TyEnv) -> Expr {
+    pub fn to_expr_tyenv(&self, env: &TyEnv<'cx>) -> Expr {
         let opts = ToExprOptions { alpha: false };
+        let cx = env.cx();
         let mut env = env.as_nameenv().clone();
-        hir_to_expr(self, opts, &mut env)
+        hir_to_expr(cx, self, opts, &mut env)
     }
 
     /// Typecheck the Hir.
     pub fn typecheck<'hir>(
         &'hir self,
-        env: &TyEnv,
-    ) -> Result<Tir<'hir>, TypeError> {
+        env: &TyEnv<'cx>,
+    ) -> Result<Tir<'cx, 'hir>, TypeError> {
         type_with(env, self, None)
     }
-    pub fn typecheck_noenv<'hir>(&'hir self) -> Result<Tir<'hir>, TypeError> {
-        self.typecheck(&TyEnv::new())
+    pub fn typecheck_noenv<'hir>(
+        &'hir self,
+        cx: Ctxt<'cx>,
+    ) -> Result<Tir<'cx, 'hir>, TypeError> {
+        typecheck(cx, self)
     }
 
     /// Eval the Hir. It will actually get evaluated only as needed on demand.
-    pub fn eval(&self, env: impl Into<NzEnv>) -> Nir {
+    pub fn eval(&self, env: impl Into<NzEnv<'cx>>) -> Nir<'cx> {
         Nir::new_thunk(env.into(), self.clone())
     }
     /// Eval a closed Hir (i.e. without free variables). It will actually get evaluated only as
     /// needed on demand.
-    pub fn eval_closed_expr(&self) -> Nir {
-        self.eval(NzEnv::new())
+    pub fn eval_closed_expr(&self, cx: Ctxt<'cx>) -> Nir<'cx> {
+        self.eval(NzEnv::new(cx))
     }
 }
 
-fn hir_to_expr(hir: &Hir, opts: ToExprOptions, env: &mut NameEnv) -> Expr {
+fn hir_to_expr<'cx>(
+    cx: Ctxt<'cx>,
+    hir: &Hir<'cx>,
+    opts: ToExprOptions,
+    env: &mut NameEnv,
+) -> Expr {
     let kind = match hir.kind() {
         HirKind::Var(v) if opts.alpha => ExprKind::Var(V("_".into(), v.idx())),
         HirKind::Var(v) => ExprKind::Var(env.label_var(*v)),
-        HirKind::Import(hir, _) => {
-            return hir_to_expr(hir, opts, &mut NameEnv::new())
+        HirKind::MissingVar(v) => ExprKind::Var(v.clone()),
+        HirKind::Import(import) => {
+            let typed = cx[import].unwrap_result();
+            return hir_to_expr(cx, &typed.hir, opts, &mut NameEnv::new());
+        }
+        HirKind::ImportAlternative(alt, left, right) => {
+            let hir = if cx[alt].unwrap_selected() {
+                left
+            } else {
+                right
+            };
+            return hir_to_expr(cx, hir, opts, env);
         }
         HirKind::Expr(e) => {
             let e = e.map_ref_maybe_binder(|l, hir| {
                 if let Some(l) = l {
                     env.insert_mut(l);
                 }
-                let e = hir_to_expr(hir, opts, env);
+                let e = hir_to_expr(cx, hir, opts, env);
                 if l.is_some() {
                     env.remove_mut();
                 }
@@ -124,9 +147,9 @@ fn hir_to_expr(hir: &Hir, opts: ToExprOptions, env: &mut NameEnv) -> Expr {
     Expr::new(kind, hir.span())
 }
 
-impl std::cmp::PartialEq for Hir {
+impl<'cx> std::cmp::PartialEq for Hir<'cx> {
     fn eq(&self, other: &Self) -> bool {
         self.kind == other.kind
     }
 }
-impl std::cmp::Eq for Hir {}
+impl<'cx> std::cmp::Eq for Hir<'cx> {}
diff --git a/dhall/src/semantics/resolve/resolve.rs b/dhall/src/semantics/resolve/resolve.rs
index 16987de..116e1a5 100644
--- a/dhall/src/semantics/resolve/resolve.rs
+++ b/dhall/src/semantics/resolve/resolve.rs
@@ -15,7 +15,10 @@ use crate::syntax::{
     Expr, ExprKind, FilePath, FilePrefix, Hash, ImportMode, ImportTarget, Span,
     UnspannedExpr, URL,
 };
-use crate::{Parsed, Resolved, Typed};
+use crate::{
+    Ctxt, ImportAlternativeId, ImportId, ImportResultId, Parsed, Resolved,
+    Typed,
+};
 
 // TODO: evaluate import headers
 pub type Import = syntax::Import<()>;
@@ -29,8 +32,10 @@ enum ImportLocationKind {
     Remote(Url),
     /// Environment variable
     Env(String),
-    /// Data without a location
+    /// Data without a location; chaining will start from current directory.
     Missing,
+    /// Token to signal that thi sfile should contain no imports.
+    NoImport,
 }
 
 /// The location of some data.
@@ -101,6 +106,7 @@ impl ImportLocationKind {
                 url = url.join(&path.file_path.join("/"))?;
                 ImportLocationKind::Remote(url)
             }
+            ImportLocationKind::NoImport => unreachable!(),
         })
     }
 
@@ -120,6 +126,7 @@ impl ImportLocationKind {
             ImportLocationKind::Missing => {
                 return Err(ImportError::Missing.into())
             }
+            ImportLocationKind::NoImport => unreachable!(),
         })
     }
 
@@ -134,6 +141,7 @@ impl ImportLocationKind {
             ImportLocationKind::Missing => {
                 return Err(ImportError::Missing.into())
             }
+            ImportLocationKind::NoImport => unreachable!(),
         })
     }
 
@@ -149,6 +157,7 @@ impl ImportLocationKind {
                 ("Environment", Some(name.clone()))
             }
             ImportLocationKind::Missing => ("Missing", None),
+            ImportLocationKind::NoImport => unreachable!(),
         };
 
         let asloc_ty = make_aslocation_uniontype();
@@ -171,6 +180,12 @@ impl ImportLocation {
             mode: ImportMode::Code,
         }
     }
+    pub fn dhall_code_without_imports() -> Self {
+        ImportLocation {
+            kind: ImportLocationKind::NoImport,
+            mode: ImportMode::Code,
+        }
+    }
     pub fn local_dhall_code(path: PathBuf) -> Self {
         ImportLocation {
             kind: ImportLocationKind::Local(path),
@@ -191,6 +206,10 @@ impl ImportLocation {
     fn chain(&self, import: &Import) -> Result<ImportLocation, Error> {
         // Makes no sense to chain an import if the current file is not a dhall file.
         assert!(matches!(self.mode, ImportMode::Code));
+        if matches!(self.kind, ImportLocationKind::NoImport) {
+            Err(ImportError::UnexpectedImport(import.clone()))?;
+        }
+
         let kind = match &import.location {
             ImportTarget::Local(prefix, path) => {
                 self.kind.chain_local(*prefix, path)?
@@ -227,30 +246,42 @@ impl ImportLocation {
     }
 
     /// Fetches the expression corresponding to this location.
-    fn fetch(&self, env: &mut ImportEnv, span: Span) -> Result<Typed, Error> {
-        let (hir, ty) = match self.mode {
+    fn fetch<'cx>(
+        &self,
+        env: &mut ImportEnv<'cx>,
+        span: Span,
+    ) -> Result<Typed<'cx>, Error> {
+        let cx = env.cx();
+        let typed = match self.mode {
             ImportMode::Code => {
                 let parsed = self.kind.fetch_dhall()?;
-                let typed = resolve_with_env(env, parsed)?.typecheck()?;
-                let hir = typed.normalize().to_hir();
-                (hir, typed.ty)
+                let typed = parsed.resolve_with_env(env)?.typecheck(cx)?;
+                Typed {
+                    // TODO: manage to keep the Nir around. Will need fixing variables.
+                    hir: typed.normalize(cx).to_hir(),
+                    ty: typed.ty,
+                }
             }
             ImportMode::RawText => {
                 let text = self.kind.fetch_text()?;
-                let hir = Hir::new(
-                    HirKind::Expr(ExprKind::TextLit(text.into())),
-                    span,
-                );
-                (hir, Type::from_builtin(Builtin::Text))
+                Typed {
+                    hir: Hir::new(
+                        HirKind::Expr(ExprKind::TextLit(text.into())),
+                        span,
+                    ),
+                    ty: Type::from_builtin(cx, Builtin::Text),
+                }
             }
             ImportMode::Location => {
                 let expr = self.kind.to_location();
-                let hir = skip_resolve_expr(&expr)?;
-                let ty = hir.typecheck_noenv()?.ty().clone();
-                (hir, ty)
+                Parsed::from_expr_without_imports(expr)
+                    .resolve(cx)
+                    .unwrap()
+                    .typecheck(cx)
+                    .unwrap()
             }
         };
-        Ok(Typed { hir, ty })
+        Ok(typed)
     }
 }
 
@@ -282,15 +313,21 @@ fn make_aslocation_uniontype() -> Expr {
     mkexpr(ExprKind::UnionType(union))
 }
 
-fn check_hash(import: &Import, typed: &Typed, span: Span) -> Result<(), Error> {
+pub fn check_hash<'cx>(
+    cx: Ctxt<'cx>,
+    import: ImportId<'cx>,
+    result: ImportResultId<'cx>,
+) -> Result<(), Error> {
+    let import = &cx[import];
     if let (ImportMode::Code, Some(Hash::SHA256(hash))) =
-        (import.mode, &import.hash)
+        (import.import.mode, &import.import.hash)
     {
-        let actual_hash = typed.hir.to_expr_alpha().sha256_hash()?;
+        let expr = cx[result].hir.to_expr_alpha(cx);
+        let actual_hash = expr.sha256_hash()?;
         if hash[..] != actual_hash[..] {
             mkerr(
                 ErrorBuilder::new("hash mismatch")
-                    .span_err(span, "hash mismatch")
+                    .span_err(import.span.clone(), "hash mismatch")
                     .note(format!("Expected sha256:{}", hex::encode(hash)))
                     .note(format!(
                         "Found    sha256:{}",
@@ -332,127 +369,204 @@ fn desugar(expr: &Expr) -> Cow<'_, Expr> {
     }
 }
 
-/// Traverse the expression, handling import alternatives and passing
-/// found imports to the provided function. Also resolving names.
-fn traverse_resolve_expr(
+/// Fetch the import and store the result in the global context.
+fn fetch_import<'cx>(
+    env: &mut ImportEnv<'cx>,
+    import_id: ImportId<'cx>,
+) -> Result<ImportResultId<'cx>, Error> {
+    let cx = env.cx();
+    let import = &cx[import_id].import;
+    let span = cx[import_id].span.clone();
+    let location = cx[import_id].base_location.chain(import)?;
+
+    // If the import is in the in-memory cache, or the hash is in the on-disk cache, return
+    // the cached contents.
+    if let Some(res_id) = env.get_from_mem_cache(&location) {
+        // The same location may be used with different or no hashes. Thus we need to check
+        // the hashes every time.
+        env.check_hash(import_id, res_id)?;
+        env.write_to_disk_cache(&import.hash, res_id);
+        return Ok(res_id);
+    }
+    if let Some(typed) = env.get_from_disk_cache(&import.hash) {
+        // No need to check the hash, it was checked before reading the file.
+        // We also don't write to the in-memory cache, because the location might be completely
+        // unrelated to the cached file (e.g. `missing sha256:...` is valid).
+        // This actually means that importing many times a same hashed import will take
+        // longer than importing many times a same non-hashed import.
+        let res_id = cx.push_import_result(typed);
+        return Ok(res_id);
+    }
+
+    // Resolve this import, making sure that recursive imports don't cycle back to the
+    // current one.
+    let res = env.with_cycle_detection(location.clone(), |env| {
+        location.fetch(env, span.clone())
+    });
+    let typed = match res {
+        Ok(typed) => typed,
+        Err(e) => mkerr(
+            ErrorBuilder::new("error")
+                .span_err(span.clone(), e.to_string())
+                .format(),
+        )?,
+    };
+
+    // Add the resolved import to the caches
+    let res_id = cx.push_import_result(typed);
+    env.check_hash(import_id, res_id)?;
+    env.write_to_disk_cache(&import.hash, res_id);
+    // Cache the mapping from this location to the result.
+    env.write_to_mem_cache(location, res_id);
+
+    Ok(res_id)
+}
+
+/// Part of a tree of imports.
+#[derive(Debug, Clone, Copy)]
+pub enum ImportNode<'cx> {
+    Import(ImportId<'cx>),
+    Alternative(ImportAlternativeId<'cx>),
+}
+
+/// Traverse the expression and replace each import and import alternative by an id into the global
+/// context. The ids are also accumulated into `nodes` so that we can resolve them afterwards.
+fn traverse_accumulate<'cx>(
+    env: &mut ImportEnv<'cx>,
     name_env: &mut NameEnv,
+    nodes: &mut Vec<ImportNode<'cx>>,
+    base_location: &ImportLocation,
     expr: &Expr,
-    f: &mut impl FnMut(Import, Span) -> Result<Typed, Error>,
-) -> Result<Hir, Error> {
+) -> Hir<'cx> {
+    let cx = env.cx();
     let expr = desugar(expr);
-    Ok(match expr.kind() {
+    let kind = match expr.kind() {
         ExprKind::Var(var) => match name_env.unlabel_var(&var) {
-            Some(v) => Hir::new(HirKind::Var(v), expr.span()),
-            None => mkerr(
-                ErrorBuilder::new(format!("unbound variable `{}`", var))
-                    .span_err(expr.span(), "not found in this scope")
-                    .format(),
-            )?,
+            Some(v) => HirKind::Var(v),
+            None => HirKind::MissingVar(var.clone()),
         },
         ExprKind::Op(OpKind::BinOp(BinOp::ImportAlt, l, r)) => {
-            match traverse_resolve_expr(name_env, l, f) {
-                Ok(l) => l,
-                Err(_) => {
-                    match traverse_resolve_expr(name_env, r, f) {
-                        Ok(r) => r,
-                        // TODO: keep track of the other error too
-                        Err(e) => return Err(e),
-                    }
-                }
-            }
+            let mut imports_l = Vec::new();
+            let l = traverse_accumulate(
+                env,
+                name_env,
+                &mut imports_l,
+                base_location,
+                l,
+            );
+            let mut imports_r = Vec::new();
+            let r = traverse_accumulate(
+                env,
+                name_env,
+                &mut imports_r,
+                base_location,
+                r,
+            );
+            let alt =
+                cx.push_import_alternative(imports_l.into(), imports_r.into());
+            nodes.push(ImportNode::Alternative(alt));
+            HirKind::ImportAlternative(alt, l, r)
         }
         kind => {
-            let kind = kind.traverse_ref_maybe_binder(|l, e| {
+            let kind = kind.map_ref_maybe_binder(|l, e| {
                 if let Some(l) = l {
                     name_env.insert_mut(l);
                 }
-                let hir = traverse_resolve_expr(name_env, e, f)?;
+                let hir =
+                    traverse_accumulate(env, name_env, nodes, base_location, e);
                 if l.is_some() {
                     name_env.remove_mut();
                 }
-                Ok::<_, Error>(hir)
-            })?;
-            let kind = match kind {
+                hir
+            });
+            match kind {
                 ExprKind::Import(import) => {
                     // TODO: evaluate import headers
-                    let import = import.traverse_ref(|_| Ok::<_, Error>(()))?;
-                    let imported = f(import, expr.span())?;
-                    HirKind::Import(imported.hir, imported.ty)
+                    let import = import.map_ref(|_| ());
+                    let import_id = cx.push_import(
+                        base_location.clone(),
+                        import,
+                        expr.span(),
+                    );
+                    nodes.push(ImportNode::Import(import_id));
+                    HirKind::Import(import_id)
                 }
                 kind => HirKind::Expr(kind),
-            };
-            Hir::new(kind, expr.span())
+            }
         }
-    })
+    };
+    Hir::new(kind, expr.span())
 }
 
-fn resolve_with_env(
-    env: &mut ImportEnv,
+/// Take a list of nodes and recursively resolve them.
+fn resolve_nodes<'cx>(
+    env: &mut ImportEnv<'cx>,
+    nodes: &[ImportNode<'cx>],
+) -> Result<(), Error> {
+    for &node in nodes {
+        match node {
+            ImportNode::Import(import) => {
+                let res_id = fetch_import(env, import)?;
+                env.cx()[import].set_resultid(res_id);
+            }
+            ImportNode::Alternative(alt) => {
+                let alt = &env.cx()[alt];
+                if resolve_nodes(env, &alt.left_imports).is_ok() {
+                    alt.set_selected(true);
+                } else {
+                    resolve_nodes(env, &alt.right_imports)?;
+                    alt.set_selected(false);
+                }
+            }
+        }
+    }
+    Ok(())
+}
+
+fn resolve_with_env<'cx>(
+    env: &mut ImportEnv<'cx>,
     parsed: Parsed,
-) -> Result<Resolved, Error> {
+) -> Result<Resolved<'cx>, Error> {
     let Parsed(expr, base_location) = parsed;
-    let resolved = traverse_resolve_expr(
+    let mut nodes = Vec::new();
+    // First we collect all imports.
+    let resolved = traverse_accumulate(
+        env,
         &mut NameEnv::new(),
+        &mut nodes,
+        &base_location,
         &expr,
-        &mut |import, span| {
-            let location = base_location.chain(&import)?;
-
-            // If the import is in the in-memory cache, or the hash is in the on-disk cache, return
-            // the cached contents.
-            if let Some(typed) = env.get_from_mem_cache(&location) {
-                // The same location may be used with different or no hashes. Thus we need to check
-                // the hashes every time.
-                check_hash(&import, &typed, span)?;
-                env.write_to_disk_cache(&import.hash, &typed);
-                return Ok(typed);
-            }
-            if let Some(typed) = env.get_from_disk_cache(&import.hash) {
-                // No need to check the hash, it was checked before reading the file. We also don't
-                // write to the in-memory cache, because the location might be completely unrelated
-                // to the cached file (e.g. `missing sha256:...` is valid).
-                // This actually means that importing many times a same hashed import will take
-                // longer than importing many times a same non-hashed import.
-                return Ok(typed);
-            }
-
-            // Resolve this import, making sure that recursive imports don't cycle back to the
-            // current one.
-            let res = env.with_cycle_detection(location.clone(), |env| {
-                location.fetch(env, span.clone())
-            });
-            let typed = match res {
-                Ok(typed) => typed,
-                Err(e) => mkerr(
-                    ErrorBuilder::new("error")
-                        .span_err(span.clone(), e.to_string())
-                        .format(),
-                )?,
-            };
-
-            // Add the resolved import to the caches
-            check_hash(&import, &typed, span)?;
-            env.write_to_disk_cache(&import.hash, &typed);
-            env.write_to_mem_cache(location, typed.clone());
-            Ok(typed)
-        },
-    )?;
+    );
+    // Then we resolve them and choose sides for the alternatives.
+    resolve_nodes(env, &nodes)?;
     Ok(Resolved(resolved))
 }
 
-pub fn resolve(parsed: Parsed) -> Result<Resolved, Error> {
-    resolve_with_env(&mut ImportEnv::new(), parsed)
+/// Resolves all imports and names. Returns errors if importing failed. Name errors are deferred to
+/// typechecking.
+pub fn resolve<'cx>(
+    cx: Ctxt<'cx>,
+    parsed: Parsed,
+) -> Result<Resolved<'cx>, Error> {
+    parsed.resolve_with_env(&mut ImportEnv::new(cx))
 }
 
-pub fn skip_resolve_expr(expr: &Expr) -> Result<Hir, Error> {
-    traverse_resolve_expr(&mut NameEnv::new(), expr, &mut |import, _span| {
-        Err(ImportError::UnexpectedImport(import).into())
-    })
+/// Resolves names, and errors if we find any imports.
+pub fn skip_resolve<'cx>(
+    cx: Ctxt<'cx>,
+    parsed: Parsed,
+) -> Result<Resolved<'cx>, Error> {
+    let parsed = Parsed::from_expr_without_imports(parsed.0);
+    Ok(resolve(cx, parsed)?)
 }
 
-pub fn skip_resolve(parsed: Parsed) -> Result<Resolved, Error> {
-    let Parsed(expr, _) = parsed;
-    let resolved = skip_resolve_expr(&expr)?;
-    Ok(Resolved(resolved))
+impl Parsed {
+    fn resolve_with_env<'cx>(
+        self,
+        env: &mut ImportEnv<'cx>,
+    ) -> Result<Resolved<'cx>, Error> {
+        resolve_with_env(env, self)
+    }
 }
 
 pub trait Canonicalize {