cyclic dependencies need grouping #198
Comments
|
There are different strategies on finding sets of edges to remove to break cycles. I'm not sure if there is a clear right or wrong solution. It always depends on what you try to do afterwards I think the current algorithm tries to remove the edges with the highest distance from the root. Though I see that problem that we now depend on the Therefore, I'm interested in what you manage to achieve with your new build logic. If it is an improvement over the old one, I'm open to have it changed. |
|
Hmm - for nodejs I just group all the modules that are part of a cycle group together. You cannot have eslint without having trimend and trimstart in its package under lib/node_modules. If you wanted trimend by itself, you would still need eslint, and therefore you would still need trimstart. You cannot separate them. In the end you need a single store package that includes all modules that have cycles between them. So that's why I think the original resolution is wrong, you should not be able to have a cyclee in multiple groups. |
As long as any of its parents/ancestors contain this dependency, it is fine, which is why the current logic works. Anyways, I just pasted a flake in another thread, that demonstrates that eslint works just fine with the current dream2nix. I think we waste our time continuing this discussion. You could prove your point very easily, by just providing a flake with a failing build. |
I'll try this later, I encountered the cyclic problem in my branch because it doesn't use the symlink resolving flag, between node-sp-auth and node-sp-auth-config IIRC. Anyway, the eslint example you gave doesn't have eslint in node_modules: |
|
Whereas with #195: (the null is a bug, I'll fix it) As you can see, eslint and eslint-utils are together in the same store path |
All of that is just because eslint-config-eslint is for some reason detected as the default package of this flake, and therefore the default devShell is also for That's a bug and we should fix it. > nix develop .#devShells.x86_64-linux.eslint -L
> ls node_modules
> nix develop .#devShells.x86_64-linux.eslint -L
> ls node_modules
ajv escape-string-regexp eslint-visitor-keys globals karma memfs npm-license shelljs
@babel @eslint eslump glob-parent karma-chrome-launcher metascraper null sinon
babel-loader eslint-config-eslint espree got karma-mocha metascraper-description nyc strip-ansi
chai eslint-plugin-eslint-comments esprima gray-matter karma-mocha-reporter metascraper-image optionator strip-json-comments
chalk eslint-plugin-eslint-plugin esquery @humanwhocodes karma-webpack metascraper-logo pirates temp
cheerio eslint-plugin-internal-rules esutils ignore levn metascraper-logo-favicon progress text-table
common-tags eslint-plugin-jsdoc fast-deep-equal import-fresh lint-staged metascraper-title proxyquire v8-compile-cache
core-js eslint-plugin-node fast-glob imurmurhash load-perf minimatch puppeteer webpack
cross-spawn eslint-plugin-unicorn file-entry-cache is-glob lodash.merge mocha recast webpack-cli
debug eslint-release fs-teardown jsdoc markdownlint mocha-junit-reporter regenerator-runtime yorkie
doctrine eslint-scope functional-red-black-tree json-stable-stringify-without-jsonify markdownlint-cli natural-compare regexpp
ejs eslint-utils glob js-yaml marked node-polyfill-webpack-plugin semver |
|
The reason it detects eslint-utils is because it considers eslint a cyclee. And actually, eslint-utils should have eslint in its node_modules here and it doesn't. So that's a cyclic bug. |
Not sure what you mean.
That has nothing to do with cycles. # podman run -it node:16 bash
# git clone --depth 1 https://github.com/eslint/eslint
# cd eslint
# npm install
# ls node_modules/eslint-utils/node_modules/
eslint-visitor-keys
The issue we're running into with the current dream2nix is a peerDependency issue. |
|
it's a peer dep but also a cycle. Because it's a cycle it's been semi-randomly selected as the default package. The alternative is what npm does, creating a full copy of all packages, but that's wasteful in diskspace and time. pnpm does symlinks and it does it similarly as in #195. |
|
ok, here's a breaking cycle test: node-sp-auth-config can't load node-sp-auth, and both modules require eachother, so both fail to load. |
|
Thinking some more about this, it's not that the results are wrong per se, but that they don't get grouped. If A<=>B and B<=>C then the group should be ABC but instead we get AB and BC. Note also that if A and C are different versions of the same package, the graph is technically speaking invalid but npm doesn't care. This actually happens in my example, it has two versions of node-sp-auth-config. My v2 branch handles this case and refuses to build; when I fix the versions it builds a correct combined package. |
|
How about this recursive algorithm: (pretend versions are part of dep)
Call the algorithm on pkg with Not quite sure how to implement this in Nix, especially the shared cycles list and the cycle merging. |
I think it should be fine to have different versions of the same package within on dependency tree. NPM is fine with that as well. Just to make sure, we are talking about the same thing when we talk about cycles: I think if you'd force the whole closure to only contain one version of every package, you will loose compatibility to existing lock file formats because they do expect you to be able to install multiple versions of a package. You would have to re-resolve the dependency tree, which is a hard problem as you may know. |
|
Right- I was on mobile and couldn't express subtlety, sorry. Indeed multiple versions of the same package within one tree are completely fine. It's just with the example I gave, node-sp-auth-config=* ends up being version 3.0.2 (C2) and and node-sp-auth (N1) pinned version 3.0.1 (C1). So requiring N1 would require C1, then requiring C2 requires N1 which requires C1. So then any module scope data you put on C2 wouldn't be visible to C1, and N1 might be misconfigured. Therefore, the complete cycle package N+C can only contain singular versions. It is simply a (rare) configuration error to have 2 versions of this cycled package in a project IMHO. The only "problem" you get with the fixed builder is that some projects incorrectly expect modules to be visible that they didn't request. This has been a long-standing issue and most projects figured it out, plus, as I understand, you can override dependencies in the flake file to fix these situations, right? |
|
This issue has been mentioned on NixOS Discourse. There might be relevant details there: |
|
I thought of a slightly different way - group cycles after every recursion call. Since all cycles can be represented by any member, arbitrarily select the first member you find as "the name of the cycle". Then, as you return from a recursive call, return a set of Then, gather the cycles of all your deps, and merge them by replacing the firstdep in the set you're adding with whatever it might be pointing to in the set you already have. |
|
Another thoought: Having multiple versions of the same package in a cycle isn't necessarily a problem for some languages, so it should be handled in the builder (like in JS) |
|
I got as far as generating a set of cycle members so far. Now I need to merge them to cycles named for the shortest member {
mergeCycles = left: right:
left
// (b.mapAttrs (dep: firstDep:
if left ? "${dep}"
then left.${dep}
else if left ? "${firstDep}"
then left.${firstDep}
else firstDep)
right);
getCycles = pkg: seen: let
deps = dependencyGraph."${pkg.name}"."${pkg.version}";
pkgTag = "${pkg.name}#${pkg.version}";
in
b.foldl' mergeCycles {}
(b.map (
dep: let
depTag = "${dep.name}#${dep.version}";
in
if seen ? "${depTag}"
then lib.listToAttrs [(lib.nameValuePair depTag depTag) (lib.nameValuePair pkgTag depTag)]
else getCycles dep (seen // lib.listToAttrs [(lib.nameValuePair pkgTag true)])
)
deps);
}example output { "@babel/core#7.18.5" = "@babel/core#7.18.5"; "@babel/helper-compilation-targets#7.18.6" = "@babel/core#7.18.5"; "@webassemblyjs/ast#1.9.0" = "@webassemblyjs/ast#1.9.0"; "@webassemblyjs/helper-code-frame#1.9.0" = "@webassemblyjs/ast#1.9.0"; "@webassemblyjs/helper-module-context#1.9.0" = "@webassemblyjs/ast#1.9.0"; "@webassemblyjs/wast-parser#1.9.0" = "@webassemblyjs/ast#1.9.0"; "@webassemblyjs/wast-printer#1.9.0" = "@webassemblyjs/ast#1.9.0"; "babel-plugin-styled-components#2.0.7" = "styled-components#5.3.1"; "browserslist#4.21.2" = "browserslist#4.21.2"; "d#1.0.1" = "d#1.0.1"; "es-abstract#1.20.1" = "es-abstract#1.20.1"; "es5-ext#0.10.61" = "es5-ext#0.10.61"; "es6-iterator#2.0.3" = "d#1.0.1"; "es6-symbol#3.1.3" = "es6-symbol#3.1.3"; "eslint#8.18.0" = "eslint-utils#3.0.0"; "eslint-utils#3.0.0" = "eslint-utils#3.0.0"; "function.prototype.name#1.1.5" = "es-abstract#1.20.1"; "global-modules#1.0.0" = "resolve-dir#1.0.1"; "jest-pnp-resolver#1.2.2" = "jest-resolve#28.1.3"; "jest-resolve#28.1.3" = "jest-resolve#28.1.3"; "listr#0.14.3" = "listr#0.14.3"; "listr-update-renderer#0.5.0" = "listr#0.14.3"; "resolve-dir#1.0.1" = "resolve-dir#1.0.1"; "slate-react#0.22.9" = "slate-react#0.22.9"; "slate-react-placeholder#0.2.9" = "slate-react#0.22.9"; "string.prototype.trimend#1.0.5" = "es-abstract#1.20.1"; "string.prototype.trimstart#1.0.5" = "es-abstract#1.20.1"; "styled-components#5.3.1" = "styled-components#5.3.1"; "terser-webpack-plugin#1.4.5" = "webpack#4.44.1"; "update-browserslist-db#1.0.4" = "browserslist#4.21.2"; "webpack#4.44.1" = "webpack#4.44.1"; }and { "eslint#8.19.0" = "eslint#8.19.0"; "eslint-utils#3.0.0" = "eslint#8.19.0"; }To convert it to a set of cycles: l.zipAttrs (l.mapAttrsToList (n: v: l.listToAttrs [(l.nameValuePair v n)]) x)example {
"@babel/core#7.18.5" = [ "@babel/core#7.18.5" "@babel/helper-compilation-targets#7.18.6" ];
"@webassemblyjs/ast#1.9.0" = [ "@webassemblyjs/ast#1.9.0" "@webassemblyjs/helper-code-frame#1.9.0" "@webassemblyjs/helper-module-context#1.9.0" "@webassemblyjs/wast-parser#1.9.0" "@webassemblyjs/wast-printer#1.9.0" ];
"browserslist#4.21.2" = [ "browserslist#4.21.2" "update-browserslist-db#1.0.4" ];
"d#1.0.1" = [ "d#1.0.1" "es6-iterator#2.0.3" ];
"es-abstract#1.20.1" = [ "es-abstract#1.20.1" "function.prototype.name#1.1.5" "string.prototype.trimend#1.0.5" "string.prototype.trimstart#1.0.5" ];
"es5-ext#0.10.61" = [ "es5-ext#0.10.61" ];
"es6-symbol#3.1.3" = [ "es6-symbol#3.1.3" ];
"eslint-utils#3.0.0" = [ "eslint#8.18.0" "eslint-utils#3.0.0" ];
"jest-resolve#28.1.3" = [ "jest-pnp-resolver#1.2.2" "jest-resolve#28.1.3" ];
"listr#0.14.3" = [ "listr#0.14.3" "listr-update-renderer#0.5.0" ];
"resolve-dir#1.0.1" = [ "global-modules#1.0.0" "resolve-dir#1.0.1" ];
"slate-react#0.22.9" = [ "slate-react#0.22.9" "slate-react-placeholder#0.2.9" ];
"styled-components#5.3.1" = [ "babel-plugin-styled-components#2.0.7" "styled-components#5.3.1" ];
"webpack#4.44.1" = [ "terser-webpack-plugin#1.4.5" "webpack#4.44.1" ];
}I won't be able to work on this for a few days. |
The problem is, that nix will crash with an infinite recursion if the builder iterates of the dependency graph. Therefore I decided to have some kind of cycle protection by default. But I agree that the exact algorithm might be ecosystem specific. Therefore I think that it might be a good idea for you to implement this on the builder level instead of modifying |
|
This algorithm gives a more accurate result than the current one and it seems fast ( For JS multi versions, I'm specifically talking about a case like (example): In Node.js this is just wrong because you can't have all the references pointing to the correct objects, since in JS you can't request a version when requiring (you can with URL imports of course). So when building a node_modules for Node.js, this situation is an error and the builder should fail (and it does). |
|
(I updated the example above btw) |
|
🤔 hmm there's still an error in the algo - es5-ext should be part of the d and es6-sybol cycle. UPDATE: ah yes, the problem is in mergeCycles, when you have { a=a; b=a; } on the left and { c=c; b=c; } on the right. This will merge to { a=a; b=a; } // { c=c; b=a; }. c=c should become c=a instead. (remember, b=a means b is member of cycle group "a") |
|
It is now fully working with f52019b Here's a comparison of the output, as you can see it is backwards compatible. {
"@babel/helper-compilation-targets" = {
"7.18.6" = [
{ name = "@babel/core"; version = "7.18.5"; }
];
};
"@webassemblyjs/ast" = {
"1.9.0" = [
{ name = "@webassemblyjs/wast-parser"; version = "1.9.0"; }
{ name = "@webassemblyjs/wast-printer"; version = "1.9.0"; }
{ name = "@webassemblyjs/helper-module-context"; version = "1.9.0"; }
];
};
browserslist = {
"4.21.2" = [
{ name = "update-browserslist-db"; version = "1.0.4"; }
];
};
es-abstract = {
"1.20.1" = [
{ name = "function.prototype.name"; version = "1.1.5"; }
{ name = "string.prototype.trimend"; version = "1.0.5"; }
{ name = "string.prototype.trimstart"; version = "1.0.5"; }
];
};
es6-symbol = {
"3.1.3" = [
{ name = "es6-iterator"; version = "2.0.3"; }
{ name = "d"; version = "1.0.1"; }
{ name = "es5-ext"; version = "0.10.61"; }
];
};
eslint = {
"8.18.0" = [
{ name = "eslint-utils"; version = "3.0.0"; }
];
};
jest-resolve = {
"28.1.3" = [
{ name = "jest-pnp-resolver"; version = "1.2.2"; }
];
};
listr-update-renderer = {
"0.5.0" = [
{ name = "listr"; version = "0.14.3"; }
];
};
resolve-dir = {
"1.0.1" = [
{ name = "global-modules"; version = "1.0.0"; }
];
};
slate-react = {
"0.22.9" = [
{ name = "slate-react-placeholder"; version = "0.2.9"; }
];
};
styled-components = {
"5.3.1" = [
{ name = "babel-plugin-styled-components"; version = "2.0.7"; }
];
};
webpack = {
"4.44.1" = [
{ name = "terser-webpack-plugin"; version = "1.4.5"; }
];
};
}original: {
"@babel/helper-compilation-targets" = {
"7.18.6" = [
{ name = "@babel/core"; version = "7.18.5"; }
];
};
"@webassemblyjs/helper-code-frame" = {
"1.9.0" = [
{ name = "@webassemblyjs/wast-printer"; version = "1.9.0"; }
];
};
"@webassemblyjs/helper-module-context" = {
"1.9.0" = [
{ name = "@webassemblyjs/ast"; version = "1.9.0"; }
];
};
"@webassemblyjs/wast-parser" = {
"1.9.0" = [
{ name = "@webassemblyjs/ast"; version = "1.9.0"; }
];
};
"@webassemblyjs/wast-printer" = {
"1.9.0" = [
{ name = "@webassemblyjs/ast"; version = "1.9.0"; }
{ name = "@webassemblyjs/wast-parser"; version = "1.9.0"; }
];
};
babel-plugin-styled-components = {
"2.0.7" = [
{ name = "styled-components"; version = "5.3.1"; }
];
};
es5-ext = {
"0.10.61" = [
{ name = "es6-symbol"; version = "3.1.3"; }
];
};
es6-iterator = {
"2.0.3" = [
{ name = "d"; version = "1.0.1"; }
{ name = "es5-ext"; version = "0.10.61"; }
{ name = "es6-symbol"; version = "3.1.3"; }
];
};
eslint = {
"8.18.0" = [
{ name = "eslint-utils"; version = "3.0.0"; }
];
};
"function.prototype.name" = {
"1.1.5" = [
{ name = "es-abstract"; version = "1.20.1"; }
];
};
global-modules = {
"1.0.0" = [
{ name = "resolve-dir"; version = "1.0.1"; }
];
};
jest-pnp-resolver = {
"1.2.2" = [
{ name = "jest-resolve"; version = "28.1.3"; }
];
};
listr-update-renderer = {
"0.5.0" = [
{ name = "listr"; version = "0.14.3"; }
];
};
slate-react-placeholder = {
"0.2.9" = [
{ name = "slate-react"; version = "0.22.9"; }
];
};
"string.prototype.trimend" = {
"1.0.5" = [
{ name = "es-abstract"; version = "1.20.1"; }
];
};
"string.prototype.trimstart" = {
"1.0.5" = [
{ name = "es-abstract"; version = "1.20.1"; }
];
};
terser-webpack-plugin = {
"1.4.5" = [
{ name = "webpack"; version = "4.44.1"; }
];
};
update-browserslist-db = {
"1.0.4" = [
{ name = "browserslist"; version = "4.21.2"; }
];
};
} |
I see that nothing handles cyclic deps. I took a stab at it because it's breaking for me, but I notice that the cyclic dep resolver isn't working properly. When I install es-abstract, I get in the dream lock (trimmed example):
{ "string.prototype.trimend": { "1.0.5": [ [ "es-abstract", "1.20.1" ] ] }, "string.prototype.trimstart": { "1.0.5": [ [ "es-abstract", "1.20.1" ] ] }, }Obviously, all cyclic dependencies should be grouped together and a parent dep should be picked (probably the one with the shortest name)
So it should be:
{ "es-abstract": { "1.20.1": { ["string.prototype.trimend", "1.0.5"], ["string.prototype.trimstart", "1.0.5"] } } }The text was updated successfully, but these errors were encountered: