Hmm, this commit introduced a "problem" for me:

error: stack overflow (possible infinite recursion)

My test command:

nix-env -f . -qa --show-trace --drv-path >/dev/null

Note in particular that without --drv-path it succeeds, so it's probably not an infinite recursion but hitting a limit hardcoded in nix. I'm getting the same with both nix-1.11 and 1.12.

AFAIK this is mainly problem for borg's rebuild-amount estimation. /cc @grahamc.

At the moment I cannot think of any reason why this is occurring. The earlier introduced requiredPythonModules does (quite) some recursion, and this is one additional item that it tries to recurse into.

Hydra also does not evaluate this (as part of pkgs/top-level/release.nix):

hydra-eval-jobs returned exit code 1:
error: stack overflow (possible infinite recursion)

Let's revert and investigate.

Reverted in 19b82ec, will try to debug later today.

I can't reproduce the issue.

$ nix-info --sandbox --host-os
system: "x86_64-linux", host os: Linux 4.9.66, NixOS, 17.09.2281.b4a0c011e81 (Hummingbird), multi-user?: yes, sandbox: yes, version: nix-env (Nix) 1.12pre5732_fd10f6f2, channels(root): "nixos-17.09.2075.ac35504065", channels(freddy): "nixpkgs-unstable", nixpkgs: /nix/var/nix/profiles/per-user/root/channels/nixos/nixpkgs

@FRidh Would you be able to figure out a better fix for that? At least it would be possible to treat setuptools as a special case in hasPythonModule (ugly but would fix regression until better fix).

https://github.com/NixOS/nixpkgs/blob/master/pkgs/top-level/python-packages.nix#L90

And, obviously, thanks for everyone involved. I've been happy to learn how Python tooling in nixpkgs have got better.

Running both Nix 1.11.15 and Nix from today's master as nix-env -f . -qa --show-trace --drv-path -vvvvv >/dev/null on 859dc02 terminates with nix-env.log.

I think adding it instead to the passthru should solve the issue. buildPythonPackage and toPythonModule also add it to the passthru. In that case it won't end up in I think drvAttrs and as such also not in the passAsFile.

@vcunat @orivej can you check evaluation of https://github.com/FRidh/nixpkgs/tree/setuptools-fix.

@FRidh: infinite recursion again (tested 1.12 and 1.11).

Using nix-env -f . -qa --show-trace --drv-path -vvvvv >/dev/null I was able to reproduce the issue. The stack overflow is caused when creating the derivation ihaskell https://github.com/NixOS/nixpkgs/blob/staging/pkgs/top-level/all-packages.nix#L2734.

This derivation requires

jupyter = python3.withPackages (ps: [ ps.jupyter ps.notebook ]);

Currently, the function requiredPythonModules looks like this

  # Get list of required Python modules given a list of derivations.
  requiredPythonModules = drvs: let
    filterNull = list: filter (x: !isNull x) list;
    conditionalGetRecurse = attr: condition: drv: let f = conditionalGetRecurse attr condition; in
      (if (condition drv) then unique [drv]++(concatMap f (filterNull(getAttr attr drv))) else []);
    _required = drv: conditionalGetRecurse "propagatedBuildInputs" hasPythonModule drv;
  in [python] ++ (unique (concatMap _required (filterNull drvs)));

jupyter depends on notebook. The function is quite naive, not taking account that one leaf is in fact covered in the other. Writing

jupyter = python3.withPackages (ps: [ ps.jupyter ]);

still causes a stack overflow though.

Nix lacks tail call optimization (NixOS/nix#1150) and I think that's why we're getting these stack overflows. All buildPythonPackages derivations depend on setuptools so I think that was the drop that caused the overflow.

When increasing my stack limit from 8192 to 16384 the issue did not occur. That actually makes me wonder how much stack "space" we have left when evaluating the package set, considering the use also of fixed-point combinators.

I suppose what needs to be done is writing requiredPythonModules in such a way that it traverses the tree without using this much recursion.

The problem clearly isn't (just) in this particular commit. I recently got an overflow on a commit that didn't have this change, preventing my nixos system from evaluating. Maybe it will be best to increase the (default) stack limit, even if we take some precaution to reduce its usage.

I don't expect you to remember, but do you think it was before or after 40851a4 was introduced? That was about two weeks ago on staging.

@FRidh: it first happened on cdde22a, i.e. after that commit.

Running that nix-env command with NIX_SHOW_STATS=1 on 6ad7967 (the last master without 40851a4) and 0f50d5a (the master with it), we can not see the maximum recursion depth, but there is a drastic change in the number of allocated values:

 evaluation statistics:
-  time elapsed: 19.849
+  time elapsed: 21.567
   size of a value: 24
   size of an attr: 24
-  environments allocated: 6761687 (216992488 bytes)
+  environments allocated: 8910225 (268576824 bytes)
-  list elements: 90931824 (727454592 bytes)
+  list elements: 93226674 (745813392 bytes)
-  list concatenations: 750765
+  list concatenations: 748285
-  values allocated: 17074297 (409783128 bytes)
+  values allocated: 24961898 (599085552 bytes)
-  sets allocated: 2444900 (725028328 bytes)
+  sets allocated: 2438494 (724444184 bytes)
-  right-biased unions: 1148943
+  right-biased unions: 1145597
-  values copied in right-biased unions: 21635026
+  values copied in right-biased unions: 21619671
-  symbols in symbol table: 271644
+  symbols in symbol table: 271580
-  size of symbol table: 10706516
+  size of symbol table: 10705395
-  number of thunks: 12639646
+  number of thunks: 14629691
-  number of thunks avoided: 11357340
+  number of thunks avoided: 13443879
-  number of attr lookups: 6689281
+  number of attr lookups: 6708048
-  number of primop calls: 3753242
+  number of primop calls: 5754172
-  number of function calls: 5803498
+  number of function calls: 7944800
-  total allocations: 2079258536 bytes
+  total allocations: 2337919952 bytes
-  current Boehm heap size: 1715470336 bytes
+  current Boehm heap size: 1849688064 bytes
-  total Boehm heap allocations: 2610957824 bytes
+  total Boehm heap allocations: 2950226176 bytes

I have another implementation. Could you please test https://github.com/FRidh/nixpkgs/tree/pythonmodule.

Note there is a 30% increase of function calls and 50% increase of primop calls.