Evaluate <nixpkgs/lib>

[domenkozar]

$ ./result/bin/hnix --eval -E "import <nixpkgs/lib>" --strict
lib.zip is deprecated, use lib.zipAttrsWith instead
hnix: <<loop during normalization forcing <closure>>>

$ nix-instantiate --eval -E "import <nixpkgs/lib>" --strict
...

[matthewbauer]

Looking at the trace, it looks like its getting stuck on defaultTypeMerge here:

https://github.com/NixOS/nixpkgs/blob/master/lib/types.nix#L23

This is doing some recursive stuff that maybe interferes with strict?

[jwiegley]

This is a great test case, I'm looking at now. The question is which piece of this puzzle are we being too strict about.

[jwiegley]

@matthewbauer This demonstrates the problem:

let
  mkOptionType = { name }: {
    type = types."${name}";
  };
  types = {
    unspecified = mkOptionType {
      name = "unspecified";
    };
  };
in types

For hnix it's an error to evaluate this into normal form, but apparently not for nix:

nix-instantiate --eval bug.nix --strict
{ unspecified = { type = { type = <CYCLE>; }; }; }

I will introduce an NVCycle :: NValue m -> NValueNF m value constructor to represent these. It also means we may want to track values during normalization so that we can detect the cycle immediately, rather than waiting for an arbitrary cutoff as we do now.

[jwiegley]

Or better, change NValueNF from:

type NValueNF m = Fix (NValueF m)

to

type NValueNF m = Fix (Compose (Either (NValue m)) (NValueF m))
  -- ^ aka, Free (NValueF m) (NValue m)

To indicate when cycles have been detected during normalization. Or an equivalent expressive data type to capture this possibility. This will keep representation of cycles out of the non-normalized representation.

[matthewbauer]

Sounds good! I think this is related to how Nix handles a lot of different things like the builtins.builtins.builtins... case.

[jwiegley]

@matthewbauer I've finished changing NValueNF to use Free instead of Fix, and that has allowed the evaluation to succeed. I need to implement the value tracking, though, because the "depth 2000 cutoff" is causing the output to be huge, since we don't identify the cycle immediately when it begins.

[jwiegley]

@matthewbauer This work is on the free-nf branch for now, in case you have an idea on how to detect cycles. I was thinking of just using a HashMap for the first approximation, even though it will be slow and inefficient.

[matthewbauer]

Yes HashMap sounds okay. Nix actually just uses a set of values it has visited:

https://github.com/NixOS/nix/blob/bc65e02d9671ef6af2c25b4cc7a0a34944d98a2d/src/libexpr/eval.cc#L47

It might make sense to just use Data.Set then.

[matthewbauer]

Here is an implementation of this: https://github.com/obsidiansystems/hnix/tree/cycles

@jwiegley It looks like the free stuff has broken a few tests though. Might be something with Eq instances?

[domenkozar]

@matthewbauer I tried your branch and it never finishes evaluation for me (OOMs).

$ ./result/bin/hnix --eval -E "(import <nixpkgs/lib>)" --strict -I nix=`pwd`/data/nix/corepkgs

[bqv]

I believe this can be closed

[sorki]

Yup, it evals correctly now.