Infinite loop (and memory usage)

[jneem]

When trying to export the following file, nickel gets stuck and starts using up all my memory:

{ y = { foo = y } }

[yannham]

I mean, it is an infinite loop, right? Although we should probably be able to detect that without black-holing, and I'm not sure why we don't.

What behavior do you think would be right?

[jneem]

I'd expect the same infinite recursion error that you get from, say let rec y = y in y

[yannham]

I haven't tested this hypothesis, but I believe it's to be expected that black-holing doesn't detect such loops. In fact, as long as you don't use deep_seq (but both nickel eval and nickel export do use it, which is why it's looping), this term doesn't loop, in that it's always productive: if we evaluate y, we get a lazy record {foo = y}. If we then evaluate foo, we get in one step the record {foo = y}, and so on. It's basically an infinite record { y = { foo = {foo = { foo = ...., which is - at each step - at most one variable substitution away from being in weak head normal form.

So, evaluating y always terminates, and doesn't trigger the infinite recursion detection.

However, this is different when forcing/deep_sequing the record, of course, because we are now trying to recurse into an infinite data structure. I wonder if we can extend the blackholing mechanism to handle this case, by forbidding thunks to be evaluated again while we're still forcing the children of this thunk.

[D-Brox]

Related to #1722

[yannham]

I think also related to #1967 - both the issue and the solution should be pretty similar.

[jneem]

I had a look at this today, but I couldn't figure out a version of:

forbidding thunks to be evaluated again while we're still forcing the children of this thunk

that works. For example, this input is fine:

{ y = { foo = z }, z = 1 }

but when forcing the child { foo = z }, we end up needing to re-evaluate the outermost thunk.

I guess one thing that might work (and maybe helps in #1967 too) is to have special handling for a field that evaluates to a parent thunk. I don't see how to fit this into the existing black-holing framework though; it seems like it might need an extra stack?

[yannham]

I have been looking at #1967 on my side actually 😅. My idea is to blackhole the thunk you're currently evaluating, that is the thunk of the field, not the thunk of the whole record. That is, before starting to evaluate y, peek at the value - unless it's a very simple constant it must be a Closure (it's an invariant of the evaluation) - and blackhole it. Of course it's a bit more complicated than that: if you just do that the evaluation will cause an immediate infinite recursion error, but I think we can make it work. I'll experiment and report back

[yannham]

Reproducing @jneem remark about using the result of #2055 to fix this issue as well but without a performance penalty: #2055 (review)