Repository: tweag/nickel (rust)

Issue:
Cyclic imports make the interpreter loop
**Describe the bug**
Cyclic imports make the binary overflow its stack. It's not evaluation, as it already happens just with typechecking. Spotted because of #407.

**To Reproduce**

```
echo 'let x = import "b.ncl" in null' > a.ncl
echo 'let x = import "c.ncl" in x' > b.ncl
echo 'let x = import "b.ncl" in x' > c.ncl
nickel -f a.ncl typecheck
```

**Expected behavior**
The program should evaluate successfully on `null`. Cyclic imports shouldn't be a problem. They weren't originally.

**Environment**
 - OS name + version: Linux 5.10.0-8-amd64 SMP Debian 5.10.46-4 (2021-08-03) x86_64 GNU/Linux
 - Version of the code: 269ead2a58ded6b1939e70dcd23550e92304277f

**Additional context**

A git bisect shows that the offending commit is b029763736dfa954e82bc65370b35c24117f6848
cc @francois-caddet 


Pull request description:
Fix looping typechecking of cyclic imports
Fix #409.

Do not make `type_check` functions transitively typecheck imports anymore. They now just peek at the toplevel node of the imports to see the apparent type, in order to be able to decide the type of an expression `import "foo.ncl"`, but they restrain from recursing inside `foo.ncl`.

It is now the responsibility of the caller (in practice, the cache) to call `type_check` on transitive imports of a source file, and the cache is able to see the imports it has already processed, which eliminates the loop.

Did small code cleaning on the way (such as removing the `Result` from `transform`'s return type, as now that transform does not perform import resolution, it isn't fallible anymore).

Patch:
diff --git a/src/cache.rs b/src/cache.rs
index 27829588..f5ad4814 100644
--- a/src/cache.rs
+++ b/src/cache.rs
@@ -1,13 +1,11 @@
 //! Source cache.
 
 use crate::error::{Error, ImportError, ParseError, TypecheckError};
-use crate::identifier::Ident;
 use crate::parser::lexer::Lexer;
 use crate::position::TermPos;
 use crate::stdlib as nickel_stdlib;
 use crate::term::{RichTerm, Term};
-use crate::typecheck::linearization::StubHost;
-use crate::typecheck::type_check;
+use crate::typecheck::{linearization::StubHost, type_check};
 use crate::{eval, parser, transformations};
 use codespan::{FileId, Files};
 use io::Read;
@@ -89,15 +87,28 @@ pub struct NameIdEntry {
 }
 
 /// The state of an entry of the term cache.
+///
+/// # Imports
+///
+/// Usually, when applying a procedure to an entry (typechecking, transformation, ...), we process
+/// all of its transitive imports as well. We start by processing the entry, updating the state to
+/// `XXXing` (ex: `Typechecking`) upon success. Only when all the imports have been successfully
+/// processed, the state is updated to `XXXed` (ex: `Typechecked`).
 #[derive(Eq, PartialEq, Ord, PartialOrd, Debug, Copy, Clone)]
 pub enum EntryState {
     /// The term have just been parsed.
     Parsed,
-    /// The term has been parsed and the imports resolved
+    /// The imports of the entry have been resolved, and the imports of its (transitive) imports are being resolved.
+    ImportsResolving,
+    /// The imports of the entry and its transitive dependencies has been resolved.
     ImportsResolved,
-    /// The term have been parsed and typechecked.
+    /// The entry have been typechecked, and its (transitive) imports are being typechecked.
+    Typechecking,
+    /// The entry and its transitive imports have been typechecked.
     Typechecked,
-    /// The term have been parsed, possibly typechecked (but not necessarily), and transformed.
+    /// The entry have been transformed, and its (transitive) imports are being transformed.
+    Transforming,
+    /// The entry and its transitive imports have been transformed.
     Transformed,
 }
 
@@ -290,7 +301,7 @@ impl Cache {
     }
 
     /// Parse a source and populate the corresponding entry in the cache, or do nothing if the
-    /// entry has already been parsed.
+    /// entry has already been parsed. Support multiple formats.
     pub fn parse_multi(
         &mut self,
         file_id: FileId,
@@ -341,26 +352,30 @@ impl Cache {
 
     /// Typecheck an entry of the cache and update its state accordingly, or do nothing if the
     /// entry has already been typechecked. Require that the corresponding source has been parsed.
+    /// If the source contains imports, recursively typecheck on the imports too.
     pub fn typecheck(
         &mut self,
         file_id: FileId,
         global_env: &eval::Environment,
     ) -> Result<CacheOp<()>, CacheError<TypecheckError>> {
-        if !self.terms.contains_key(&file_id) {
-            return Err(CacheError::NotParsed);
-        }
+        match self.terms.get(&file_id) {
+            Some((_, state)) if *state >= EntryState::Typechecked => Ok(CacheOp::Cached(())),
+            Some((t, state)) if *state >= EntryState::Parsed => {
+                if *state < EntryState::Typechecking {
+                    type_check(t, global_env, self, StubHost::<(), _>::new())?;
+                    self.update_state(file_id, EntryState::Typechecking);
+                }
 
-        // After self.parse(), the cache must be populated
-        let (t, state) = self.terms.get(&file_id).unwrap();
+                if let Some(imports) = self.imports.get(&file_id).cloned() {
+                    for f in imports.into_iter() {
+                        self.typecheck(f, global_env)?;
+                    }
+                }
 
-        if *state > EntryState::Typechecked {
-            Ok(CacheOp::Cached(()))
-        } else if *state >= EntryState::Parsed {
-            type_check(t, global_env, self, StubHost::<(), _>::new())?;
-            self.update_state(file_id, EntryState::Typechecked);
-            Ok(CacheOp::Done(()))
-        } else {
-            panic!()
+                self.update_state(file_id, EntryState::Typechecked);
+                Ok(CacheOp::Done(()))
+            }
+            _ => Err(CacheError::NotParsed),
         }
     }
 
@@ -368,21 +383,26 @@ impl Cache {
     /// or do nothing if the entry has already been transformed. Require that the corresponding
     /// source has been parsed.
     /// If the source contains imports, recursively perform transformations on the imports too.
-    pub fn transform(&mut self, file_id: FileId) -> Result<CacheOp<()>, CacheError<ImportError>> {
+    pub fn transform(&mut self, file_id: FileId) -> Result<CacheOp<()>, CacheError<()>> {
         match self.entry_state(file_id) {
-            Some(EntryState::Transformed) => Ok(CacheOp::Cached(())),
-            Some(_) => {
-                let (t, _) = self.terms.remove(&file_id).unwrap();
+            Some(state) if state >= EntryState::Transformed => Ok(CacheOp::Cached(())),
+            Some(state) if state >= EntryState::Parsed => {
+                if state < EntryState::Transforming {
+                    let (t, _) = self.terms.remove(&file_id).unwrap();
+                    let t = transformations::transform(t);
+                    self.terms.insert(file_id, (t, EntryState::Transforming));
+                }
+
                 if let Some(imports) = self.imports.get(&file_id).cloned() {
-                    for f in imports.iter() {
-                        self.transform(*f)?;
+                    for f in imports.into_iter() {
+                        self.transform(f)?;
                     }
                 }
-                let t = transformations::transform(t)?;
-                self.terms.insert(file_id, (t, EntryState::Transformed));
+
+                self.update_state(file_id, EntryState::Transformed);
                 Ok(CacheOp::Done(()))
             }
-            None => Err(CacheError::NotParsed),
+            _ => Err(CacheError::NotParsed),
         }
     }
 
@@ -406,73 +426,89 @@ impl Cache {
         file_id: FileId,
     ) -> Result<CacheOp<()>, CacheError<ImportError>> {
         match self.entry_state(file_id) {
-            Some(EntryState::Transformed) => Ok(CacheOp::Cached(())),
+            Some(state) if state >= EntryState::Transformed => Ok(CacheOp::Cached(())),
             Some(_) => {
-                let (mut t, _) = self.terms.remove(&file_id).unwrap();
-                match t.term.as_mut() {
-                    Term::Record(ref mut map, _) => {
-                        let map_res: Result<HashMap<Ident, RichTerm>, ImportError> =
-                            std::mem::replace(map, HashMap::new())
+                let (mut t, state) = self.terms.remove(&file_id).unwrap();
+
+                if state < EntryState::Transforming {
+                    match t.term.as_mut() {
+                        Term::Record(ref mut map, _) => {
+                            let map_res = std::mem::replace(map, HashMap::new())
                                 .into_iter()
-                                .map(|(id, t)| {
-                                    transformations::transform(t).map(|t_ok| (id.clone(), t_ok))
-                                })
+                                .map(|(id, t)| (id.clone(), transformations::transform(t)))
                                 .collect();
-                        *map = map_res?;
-                    }
-                    Term::RecRecord(ref mut map, ref mut dyn_fields, _) => {
-                        let map_res: Result<HashMap<Ident, RichTerm>, ImportError> =
-                            std::mem::replace(map, HashMap::new())
+                            *map = map_res;
+                        }
+                        Term::RecRecord(ref mut map, ref mut dyn_fields, _) => {
+                            let map_res = std::mem::replace(map, HashMap::new())
                                 .into_iter()
-                                .map(|(id, t)| {
-                                    transformations::transform(t).map(|t_ok| (id.clone(), t_ok))
-                                })
+                                .map(|(id, t)| (id.clone(), transformations::transform(t)))
                                 .collect();
 
-                        let dyn_fields_res: Result<Vec<(RichTerm, RichTerm)>, ImportError> =
-                            std::mem::replace(dyn_fields, Vec::new())
+                            let dyn_fields_res = std::mem::replace(dyn_fields, Vec::new())
                                 .into_iter()
                                 .map(|(id_t, t)| {
-                                    Ok((
-                                        transformations::transform(id_t)?,
-                                        transformations::transform(t)?,
-                                    ))
+                                    (
+                                        transformations::transform(id_t),
+                                        transformations::transform(t),
+                                    )
                                 })
                                 .collect();
 
-                        *map = map_res?;
-                        *dyn_fields = dyn_fields_res?;
+                            *map = map_res;
+                            *dyn_fields = dyn_fields_res;
+                        }
+                        _ => panic!("cache::transform_inner(): not a record"),
+                    }
+
+                    self.terms.insert(file_id, (t, EntryState::Transforming));
+                }
+
+                if let Some(imports) = self.imports.get(&file_id).cloned() {
+                    for f in imports.into_iter() {
+                        self.transform(f).map_err(|_| CacheError::NotParsed)?;
                     }
-                    _ => panic!("cache::transform_inner(): not a record"),
                 }
 
-                self.terms.insert(file_id, (t, EntryState::Transformed));
+                self.update_state(file_id, EntryState::Transformed);
                 Ok(CacheOp::Done(()))
             }
             None => Err(CacheError::NotParsed),
         }
     }
 
-    /// Resolve every imports of an entry of the cache, and update its state accordingly,
-    /// or do nothing if the entry has already been transformed. Require that the corresponding
-    /// source has been parsed.
+    /// Resolve every imports of an entry of the cache, and update its state accordingly, or do
+    /// nothing if the imports of the entry have already been resolved. Require that the
+    /// corresponding source has been parsed.
     /// If resolved imports contain imports themselves, resolve them recursively.
     pub fn resolve_imports(
         &mut self,
         file_id: FileId,
     ) -> Result<CacheOp<()>, CacheError<ImportError>> {
         match self.entry_state(file_id) {
-            Some(EntryState::ImportsResolved) => Ok(CacheOp::Cached(())),
-            Some(_) => {
-                let (t, _) = self.terms.remove(&file_id).unwrap();
-                let (t, pending) = transformations::resolve_imports(t, self)?;
-                for id in pending {
-                    self.resolve_imports(id)?;
+            Some(state) if state >= EntryState::ImportsResolved => Ok(CacheOp::Cached(())),
+            Some(state) if state >= EntryState::Parsed => {
+                if state < EntryState::ImportsResolving {
+                    let (t, _) = self.terms.remove(&file_id).unwrap();
+                    let (t, pending) = transformations::resolve_imports(t, self)?;
+                    self.terms
+                        .insert(file_id, (t, EntryState::ImportsResolving));
+
+                    for id in pending {
+                        self.resolve_imports(id)?;
+                    }
+                } else {
+                    let pending = self.imports.get(&file_id).cloned().unwrap_or_default();
+
+                    for id in pending {
+                        self.resolve_imports(id)?;
+                    }
                 }
-                self.terms.insert(file_id, (t, EntryState::ImportsResolved));
+
+                self.update_state(file_id, EntryState::ImportsResolved);
                 Ok(CacheOp::Done(()))
             }
-            None => Err(CacheError::NotParsed),
+            _ => Err(CacheError::NotParsed),
         }
     }
 
@@ -507,11 +543,10 @@ impl Cache {
             result = CacheOp::Done(());
         };
 
-        let transform_res = self.transform(file_id).map_err(|cache_err| {
-            cache_err.unwrap_error(
-                "cache::prepare(): expected source to be parsed before transformations",
-            )
-        })?;
+        let transform_res = self.transform(file_id).unwrap_or_else(|_| {
+            panic!("cache::prepare(): expected source to be parsed before transformations",)
+        });
+
         if transform_res == CacheOp::Done(()) {
             result = CacheOp::Done(());
         };
@@ -533,7 +568,7 @@ impl Cache {
         let term = self.parse_nocache(file_id)?;
         let (term, pending) = transformations::resolve_imports(term, self)?;
         type_check(&term, global_env, self, StubHost::<(), _>::new())?;
-        let term = transformations::transform(term)?;
+        let term = transformations::transform(term);
         Ok((term, pending))
     }
 
@@ -642,7 +677,7 @@ impl Cache {
     /// Typecheck the standard library. Currently only used in the test suite.
     pub fn typecheck_stdlib(&mut self) -> Result<CacheOp<()>, CacheError<TypecheckError>> {
         // We have a small bootstraping problem: to typecheck the global environment, we already
-        // need a global evaluation environment, since stdlib parts may reference each other). But
+        // need a global evaluation environment, since stdlib parts may reference each other. But
         // typechecking is performed before program transformations, so this environment is not
         // final one. We have create a temporary global environment just for typechecking, which is dropped
         // right after. However:
diff --git a/src/repl/mod.rs b/src/repl/mod.rs
index 74521f3f..d28eb844 100644
--- a/src/repl/mod.rs
+++ b/src/repl/mod.rs
@@ -73,6 +73,9 @@ pub struct REPLImpl {
     /// The eval environment. Contain the global environment with the stdlib, plus toplevel
     /// declarations and loadings made inside the REPL.
     eval_env: eval::Environment,
+    /// The initial eval environment, without the toplevel declarations made inside the REPL. Used
+    /// to typecheck imports in a fresh environment.
+    init_eval_env: eval::Environment,
     /// The typing environment, counterpart of the eval environment for typechecking. Entries are
     /// [`TypeWrapper`](../typecheck/enum.TypeWrapper.html) for the ease of interacting with the
     /// typechecker, but there are not any unification variable in it.
@@ -86,6 +89,7 @@ impl REPLImpl {
             cache: Cache::new(),
             parser: grammar::ExtendedTermParser::new(),
             eval_env: eval::Environment::new(),
+            init_eval_env: eval::Environment::new(),
             type_env: typecheck::Environment::new(),
         }
     }
@@ -96,6 +100,7 @@ impl REPLImpl {
         self.cache.prepare_stdlib()?;
 
         self.eval_env = self.cache.mk_global_env().unwrap();
+        self.init_eval_env = self.eval_env.clone();
         self.type_env = typecheck::Envs::mk_global(&self.eval_env);
         Ok(())
     }
@@ -117,16 +122,30 @@ impl REPLImpl {
             .parse(file_id, lexer::Lexer::new(exp))
             .map_err(|err| ParseError::from_lalrpop(err, file_id))?
         {
+            // Because we don't use the cache for input, we have to perform recursive import
+            // resolution/typechecking/transformation by oursleves.
             ExtendedTerm::RichTerm(t) => {
                 let (t, pending) = transformations::resolve_imports(t, &mut self.cache)?;
                 for id in &pending {
                     self.cache.resolve_imports(*id).unwrap();
                 }
+
                 typecheck::type_check_in_env(&t, &self.type_env, &self.cache)?;
                 for id in &pending {
-                    self.cache.transform(*id).unwrap();
+                    self.cache
+                        .typecheck(*id, &self.init_eval_env)
+                        .map_err(|cache_err| {
+                            cache_err.unwrap_error("repl::eval_(): expected imports to be parsed")
+                        })?;
+                }
+
+                let t = transformations::transform(t);
+                for id in &pending {
+                    self.cache
+                        .transform(*id)
+                        .unwrap_or_else(|_| panic!("repl::eval_(): expected imports to be parsed"));
                 }
-                let t = transformations::transform(t)?;
+
                 Ok(eval_function(t, &self.eval_env, &mut self.cache)?.into())
             }
             ExtendedTerm::ToplevelLet(id, t) => {
@@ -134,13 +153,23 @@ impl REPLImpl {
                 for id in &pending {
                     self.cache.resolve_imports(*id).unwrap();
                 }
+
                 typecheck::type_check_in_env(&t, &self.type_env, &self.cache)?;
                 typecheck::Envs::env_add(&mut self.type_env, id.clone(), &t);
                 for id in &pending {
-                    self.cache.transform(*id).unwrap();
+                    self.cache
+                        .typecheck(*id, &self.init_eval_env)
+                        .map_err(|cache_err| {
+                            cache_err.unwrap_error("repl::eval_(): expected imports to be parsed")
+                        })?;
                 }
 
-                let t = transformations::transform(t)?;
+                let t = transformations::transform(t);
+                for id in &pending {
+                    self.cache
+                        .transform(*id)
+                        .unwrap_or_else(|_| panic!("repl::eval_(): expected imports to be parsed"));
+                }
 
                 let local_env = self.eval_env.clone();
                 eval::env_add(&mut self.eval_env, id.clone(), t, local_env);
diff --git a/src/transformations.rs b/src/transformations.rs
index 93d7879a..a1a067db 100644
--- a/src/transformations.rs
+++ b/src/transformations.rs
@@ -265,9 +265,9 @@ struct ImportsResolutionState<'a, R> {
 /// If needed, either do it yourself using pending imports returned by
 /// [`resolve_imports`](../fn.resolve_imports.html)
 /// or use the [`Cache`](../../cache/struct.Cache.html)
-pub fn transform(rt: RichTerm) -> Result<RichTerm, ImportError> {
+pub fn transform(rt: RichTerm) -> RichTerm {
     rt.traverse(
-        &mut |rt: RichTerm, _| -> Result<RichTerm, ImportError> {
+        &mut |rt: RichTerm, _| -> Result<RichTerm, ()> {
             // We need to do contract generation before wrapping stuff in variables
             let rt = apply_contracts::transform_one(rt);
             let rt = share_normal_form::transform_one(rt);
@@ -275,6 +275,7 @@ pub fn transform(rt: RichTerm) -> Result<RichTerm, ImportError> {
         },
         &mut (),
     )
+    .unwrap()
 }
 
 /// import resolution.
diff --git a/src/typecheck/mod.rs b/src/typecheck/mod.rs
index 0ba4adaf..13d2e700 100644
--- a/src/typecheck/mod.rs
+++ b/src/typecheck/mod.rs
@@ -449,6 +449,9 @@ pub struct State<'a> {
 ///
 /// Return the inferred type in case of success. This is just a wrapper that calls
 /// [`type_check_`](fn.type_check_.html) with a fresh unification variable as goal.
+///
+/// Note that this function doesn't recursively typecheck imports (anymore), but just the current
+/// file. It however still needs the resolver to get the apparent type of imports.
 pub fn type_check<L>(
     t: &RichTerm,
     global_eval_env: &eval::Environment,
@@ -810,14 +813,13 @@ fn type_check_<S, E>(
         },
         Term::Import(_) => unify(state, strict, ty, mk_typewrapper::dynamic())
             .map_err(|err| err.into_typecheck_err(state, rt.pos)),
-        // We typecheck the import in a fresh typing environment, and then use its apparent type
-        // for checking. 
+        // We use the apparent type of the import for checking. This function doesn't recursively
+        // typecheck imports: this is the responsibility of the caller.
         Term::ResolvedImport(file_id) => {
             let t = state
                 .resolver
                 .get(*file_id)
                 .expect("Internal error: resolved import not found ({:?}) during typechecking.");
-            let _ = type_check_in_env(&t, envs.global, state.resolver)?;
             let ty_import : TypeWrapper = apparent_type(t.as_ref(), Some(&Envs::from_envs(&envs))).into();
             unify(state, strict, ty, ty_import).map_err(|err| err.into_typecheck_err(state, rt.pos))
         }


Test patch:
diff --git a/tests/imports.rs b/tests/imports.rs
index b16aca79..19aa3ba5 100644
--- a/tests/imports.rs
+++ b/tests/imports.rs
@@ -1,6 +1,7 @@
 use assert_matches::assert_matches;
 use nickel::error::{Error, EvalError, TypecheckError};
 use nickel::program::Program;
+use nickel::term::Term;
 use std::io::BufReader;
 use std::path::PathBuf;
 
@@ -15,7 +16,6 @@ fn mk_import(file: &str) -> String {
 
 #[test]
 fn nested() {
-    use nickel::term::Term;
     let mut prog = Program::new_from_source(
         BufReader::new(mk_import("nested.ncl").as_bytes()),
         "should_be = 3",
@@ -26,7 +26,6 @@ fn nested() {
 
 #[test]
 fn root_path() {
-    use nickel::term::Term;
     let mut prog = Program::new_from_source(
         BufReader::new(mk_import("root_path.ncl").as_bytes()),
         "should_be = 44",
@@ -37,7 +36,6 @@ fn root_path() {
 
 #[test]
 fn multi_imports() {
-    use nickel::term::Term;
     let mut prog = Program::new_from_source(
         BufReader::new(mk_import("multi_imports.ncl").as_bytes()),
         "should_be = 5",
@@ -102,19 +100,12 @@ fn serialize() {
     assert_eq!(prog.eval(), Ok(Term::Bool(true)));
 }
 
-// TODO produce a stack overflow
-//#[test]
-//fn circular_imports_fail() {
-//    let mut prog = Program::new_from_source(
-//        BufReader::new(mk_import("cycle.ncl").as_bytes()),
-//        "should_fail",
-//    )
-//    .unwrap();
-//    prog.eval()
-//        .map_err(|e| match e {
-//            Error::TypecheckError(TypecheckError::TypeMismatch(..)) => Ok(()),
-//            r => Err(r),
-//        })
-//        .unwrap_err()
-//        .unwrap();
-//}
+#[test]
+fn circular_imports_fail() {
+    let mut prog = Program::new_from_source(
+        BufReader::new(mk_import("cycle.ncl").as_bytes()),
+        "should_fail",
+    )
+    .unwrap();
+    assert_matches!(prog.eval(), Ok(Term::RecRecord(..)) | Ok(Term::Record(..)));
+}
diff --git a/tests/imports/cycle.ncl b/tests/imports/cycle.ncl
index e67ce7a0..e698a6d4 100644
--- a/tests/imports/cycle.ncl
+++ b/tests/imports/cycle.ncl
@@ -1,2 +1,1 @@
-
 let x = import "cycle_b.ncl" in {a = 1, b = x.a}
diff --git a/tests/imports/cycle_b.ncl b/tests/imports/cycle_b.ncl
index 29971bf2..8160ca44 100644
--- a/tests/imports/cycle_b.ncl
+++ b/tests/imports/cycle_b.ncl
@@ -1,2 +1,1 @@
-
 let x = import "cycle.ncl" in {a = x.a}