`shellFor` evaluation is quadratic in the number of selected packages

[michaelpj]

We have a list of selected packages. We get all their dependencies, and then filter it to remove any of the selected packages. The filtering works by... traversing the list of selected packages.

So assuming the selected packages have >=1 dependency, this is at least quadratic in the number of selected packages. (Actually more like O(number of packages * number of dependencies per package), but that's even worse).

[michaelpj]

I'm not sure how to fix this without having a type with better characteristics for set membership. Perhaps we can abuse attribute sets? What's the complexity of a ? b?

[rvl]

Yeah.

I looked for some builtins that may be helpful. Perhaps this one, but I haven't measured its complexity:

nix-repl> builtins.intersectAttrs { a = 4; b = 5; } { a = 3; c = 6; }
{ a = 3; }

[michaelpj]

I think this actually got fixed.