Repository: tweag/nickel
Pull request #1142 (2023-02-23 19:51:35)

[Fix] Direct import loop causing stack overflow
Fix https://github.com/tweag/nickel/pull/1135#issuecomment-1440005721.

The issue was indeed during typechecking (the evaluation still loops, but as expected, and without overflowing). When peeking at the apparent type of the imports, we would unwrap direct import chains until we find a different term. In the case of a trivial import loop, we don't. This PR adds a hashset to remember seen imports, as well as a regression test.


Patch:
diff --git a/src/typecheck/mod.rs b/src/typecheck/mod.rs
index 9f644b5f..4adcbb8a 100644
--- a/src/typecheck/mod.rs
+++ b/src/typecheck/mod.rs
@@ -1743,34 +1743,57 @@ pub fn apparent_type(
     env: Option<&Environment>,
     resolver: Option<&dyn ImportResolver>,
 ) -> ApparentType {
-    match t {
-        Term::Annotated(annot, value) => annot
-            .first()
-            .map(|labeled_ty| ApparentType::Annotated(labeled_ty.types.clone()))
-            .unwrap_or_else(|| apparent_type(value.as_ref(), env, resolver)),
-        Term::Num(_) => ApparentType::Inferred(Types(TypeF::Num)),
-        Term::Bool(_) => ApparentType::Inferred(Types(TypeF::Bool)),
-        Term::SealingKey(_) => ApparentType::Inferred(Types(TypeF::Sym)),
-        Term::Str(_) | Term::StrChunks(_) => ApparentType::Inferred(Types(TypeF::Str)),
-        Term::Array(..) => {
-            ApparentType::Approximated(Types(TypeF::Array(Box::new(Types(TypeF::Dyn)))))
-        }
-        Term::Var(id) => env
-            .and_then(|envs| envs.get(id).cloned())
-            .map(ApparentType::FromEnv)
-            .unwrap_or(ApparentType::Approximated(Types(TypeF::Dyn))),
-        Term::ResolvedImport(f) => {
-            if let Some(r) = resolver {
-                let t = r
-                    .get(*f)
-                    .expect("Internal error: resolved import not found during typechecking.");
-                apparent_type(&t.term, env, Some(r))
-            } else {
-                ApparentType::Approximated(Types(TypeF::Dyn))
+    use codespan::FileId;
+
+    // Check the apparent type while avoiding cycling through direct imports loops. Indeed,
+    // `apparent_type` tries to see through imported terms. But doing so can lead to an infinite
+    // loop, for example with the trivial program which imports itself:
+    //
+    // ```nickel
+    // # foo.ncl
+    // import "foo.ncl"
+    // ```
+    //
+    // The following function thus remembers what imports have been seen already, and simply
+    // returns `Dyn` if it detects a cycle.
+    fn apparent_type_check_cycle(
+        t: &Term,
+        env: Option<&Environment>,
+        resolver: Option<&dyn ImportResolver>,
+        mut imports_seen: HashSet<FileId>,
+    ) -> ApparentType {
+        match t {
+            Term::Annotated(annot, value) => annot
+                .first()
+                .map(|labeled_ty| ApparentType::Annotated(labeled_ty.types.clone()))
+                .unwrap_or_else(|| apparent_type(value.as_ref(), env, resolver)),
+            Term::Num(_) => ApparentType::Inferred(Types(TypeF::Num)),
+            Term::Bool(_) => ApparentType::Inferred(Types(TypeF::Bool)),
+            Term::SealingKey(_) => ApparentType::Inferred(Types(TypeF::Sym)),
+            Term::Str(_) | Term::StrChunks(_) => ApparentType::Inferred(Types(TypeF::Str)),
+            Term::Array(..) => {
+                ApparentType::Approximated(Types(TypeF::Array(Box::new(Types(TypeF::Dyn)))))
             }
+            Term::Var(id) => env
+                .and_then(|envs| envs.get(id).cloned())
+                .map(ApparentType::FromEnv)
+                .unwrap_or(ApparentType::Approximated(Types(TypeF::Dyn))),
+            Term::ResolvedImport(file_id) => match resolver {
+                Some(r) if !imports_seen.contains(file_id) => {
+                    imports_seen.insert(*file_id);
+
+                    let t = r
+                        .get(*file_id)
+                        .expect("Internal error: resolved import not found during typechecking.");
+                    apparent_type_check_cycle(&t.term, env, Some(r), imports_seen)
+                }
+                _ => ApparentType::Approximated(Types(TypeF::Dyn)),
+            },
+            _ => ApparentType::Approximated(Types(TypeF::Dyn)),
         }
-        _ => ApparentType::Approximated(Types(TypeF::Dyn)),
     }
+
+    apparent_type_check_cycle(t, env, resolver, HashSet::new())
 }
 
 /// Infer the type of a non annotated record by gathering the apparent type of the fields. It's


Test patch:
diff --git a/tests/integration/imports.rs b/tests/integration/imports.rs
index 28f8ec30..70c7a880 100644
--- a/tests/integration/imports.rs
+++ b/tests/integration/imports.rs
@@ -178,3 +178,15 @@ fn nested_syntax_error() {
         Err(Error::ImportError(ImportError::ParseErrors(..)))
     );
 }
+
+// Regression test for simple import loop making the typechecker overflow
+#[test]
+fn direct_import_loop() {
+    let mut prog = TestProgram::new_from_source(
+        BufReader::new(mk_import("direct_import_loop.ncl").as_bytes()),
+        "should_typecheck",
+    )
+    .unwrap();
+
+    assert_matches!(prog.typecheck(), Ok(()));
+}
diff --git a/tests/integration/imports/direct_import_loop.ncl b/tests/integration/imports/direct_import_loop.ncl
new file mode 100644
index 00000000..84920118
--- /dev/null
+++ b/tests/integration/imports/direct_import_loop.ncl
@@ -0,0 +1,1 @@
+import "direct_import_loop.ncl"