No detection of infinite recursion during evaluation of imports

[D-Brox]

Describe the bug

When a Nickel file attempts to do recursive imports, the evaluation process may hang indefinitely, and sometimes consumes all available RAM. This could happen due to user error.

To Reproduce

1. Create a Nickel file (e.g., recursive_import.ncl) with the following content:

# recursive_import.ncl
# This only hangs
import "./recursive_import.ncl"

# recursive_import.ncl
# This hangs and consumes all RAM
let a = import "./recursive_import.ncl" in a

2. Attempt to evaluate the file using Nickel.

nickel eval ./recursive_import.ncl

Expected behavior

Nickel should detect recursive imports and gracefully handle them, either by preventing the evaluation recursion or by providing a clear error message, to avoid hanging during evaluation and consuming excessive resources.

Environment

• OS name + version: Pop_OS! 22.04 (Ubuntu Jammy)
• Version of the code: nickel-lang-cli nickel 1.3.0 (rev cargore)

Additional context

The example above is a simplified way of showing this bug. This issue was found during testing on my use case, with 2 files, due to a typo:

• File A evaluates to a list of records from imports, and a list of functions.
• File B requires some of those functions, and it's resulting record is present in file A's record list.

This wouldn't necessarily cause an evaluation recursion by itself, but I mistyped something and the imports did result in a recursion, and that crashed my PC by consuming all the RAM (and swap).

In comparison, Nix detects such recursions and reports it with the following error:

# recursive_import.nix
let a = import ./recursive_import.nix; in a

$ nix eval --file ./recursive_import.nix        
error: stack overflow (possible infinite recursion)

[yannham]

I think that wouldn't be too hard to detect. We could use the same mechanism as for thunks (blackholing), which already gives you something like:

$ nickel repl
nickel> {x = y, y = x}
error: infinite recursion
  ┌─ <repl-input-0>:1:13
  │
1 │ {x = y, y = x}
  │             ^ recursive reference

In fact, I believe we should just put imports inside thunks, so that their evaluation is shared anyway. Which would get this infinite recursion detection, as in the example above, for free.

It's fun that you write:

Nix detects such recursions and reports it with the following error

I think it's just that when evaluating the loop, the Nix evaluator happens to run out of stack space, but it's not really what I would call detection. Maybe incidental detection? On the other hand, the loop runs in constant stack space in Nickel, which makes it just...loop.

Anyway, those cases of simple loops can be easily detected, and I agree we should avoid eating all the CPU if we can.

[yannham]

Note also that in general cyclic imports work fine in Nickel. That is, as long as there is no loop in the evaluation, you can import yourself. More precisely, as long as you don't need to evaluate the "import yourself" before producing a lazy value. For example:

# foo.ncl
let x = import "foo.ncl" in
{
  # the function is there to guard the recursive evaluation
  unroll = fun _var => x,
}

$ nickel eval foo.ncl 
{ unroll = fun _var => x, }

$ nickel repl
nickel> let foo = import "foo.ncl"
nickel> foo.unroll null
{ unroll = fun _var => x, }

nickel> (foo.unroll null).unroll null
{ unroll = fun _var => x, }

This just gives you an infinite structure that you could write without imports as let rec self = { unroll = fun _var => self } in self

[D-Brox]

Maybe incidental detection?

Yep, that's true, nix "detects" the loop by giving up, and hat's why it reports it as possible infinite recursion.

Note also that in general cyclic imports work fine in Nickel

And, in fact, I was counting on that.

I was actually experimenting with nickel to see it's viability for use in a package manager targeted specifically towards Ubuntu/Debian. Some packages would require dependencies to be defined in nickel, and the main file of a repository would reference all the packages in it, so this would possibly require a cyclical import.

The only thing really missing here is external/remote imports (tho I've seen you guys have been recently discussing about it), but I could manage to do that in a custom fork if I need to while it is not supported here on upstream.

[yannham]

The only thing really missing here is external/remote imports (tho I've seen you guys have been recently discussing about it), but I could manage to do that in a custom fork if I need to while it is not supported here on upstream.

Indeed, cf #1585. By the way, recent commits to master (#1716, #1721 to be merged) add a NICKEL_PATH (the name might be subject to change) environment variable, and once the second one is merged, a corresponding CLI argument to look for imports. Of course it doesn't replace proper package management but it can make a basic external layer easier to add, without having to fork the repo even?

[D-Brox]

True, NICKEL_PATH could partially solve it, but that would require knowing what files I would need to fetch before even evaluating the package definitions. Of course, I could clone the whole package repository and add it as the path, for example, but that would not scalable in the long run.