search

nix-community / dream2nix

Simplified nix packaging for various programming language ecosystems [maintainer=@DavHau]
https://dream2nix.dev
MIT License
1.03k stars 124 forks source link

cyclic dependencies need grouping #198

Open wmertens opened 2 years ago

wmertens commented 2 years ago

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"]
    }
  }
}
DavHau commented 2 years ago

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. For the current nodejs builder, this fits really nicely, because it guarantees that the children of removed edges, will at the same time be ancestors. As the nodejs module resolution also searches ancestors, we can just ignore all removed dependencies during installation, and everything will still work out.

Though I see that problem that we now depend on the preserveSymlinks which is not handled well by default in many build tools.

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.

wmertens commented 2 years ago

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.

DavHau commented 2 years ago

You cannot have eslint without having trimend and trimstart in its package under lib/node_modules.

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.

wmertens commented 2 years ago

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:

$ ll
total 4
-rw-r--r-- 1 wmertens 491 Jul 15 12:05 flake.nix

$ cat flake.nix 
{
  inputs.dream2nix.url = "github:nix-community/dream2nix";
  inputs.src = {flake = false; url = "github:eslint/eslint";};
  outputs = inp:
    let
      l = inp.dream2nix.inputs.nixpkgs.lib // builtins;
    in
    inp.dream2nix.lib.makeFlakeOutputs {
      # modify according to your supported systems
      systems = ["x86_64-linux"];
      config.projectRoot = ./.;
      source = l.path {
        path = inp.src;
        filter = path: _: ! l.hasInfix "/tests/" path;
      };
    };
}

$ nix develop
warning: creating lock file '/home/wmertens/lkjh/es/flake.lock'
$ tree -a node_modules
node_modules@
`-- .bin/

1 directory, 0 files
$ nix build
$ tree -a result
result@
`-- lib/
    `-- node_modules/
        `-- eslint-config-eslint/
            |-- LICENSE
            |-- README.md
            |-- default.yml
            |-- index.js
            |-- node_modules/
            |-- package.json
            `-- package.json.bak

4 directories, 6 files
$ node -r eslint
internal/modules/cjs/loader.js:905
  throw err;
  ^

Error: Cannot find module 'eslint'
Require stack:
- internal/preload
    at Function.Module._resolveFilename (internal/modules/cjs/loader.js:902:15)
    at Function.Module._load (internal/modules/cjs/loader.js:746:27)
    at Module.require (internal/modules/cjs/loader.js:974:19)
    at Module._preloadModules (internal/modules/cjs/loader.js:1244:12)
    at loadPreloadModules (internal/bootstrap/pre_execution.js:475:5)
    at prepareMainThreadExecution (internal/bootstrap/pre_execution.js:72:3)
    at internal/main/repl.js:19:1 {
  code: 'MODULE_NOT_FOUND',
  requireStack: [ 'internal/preload' ]
}
wmertens commented 2 years ago

Whereas with #195:

$ ll
total 76
-rw-r--r-- 1 wmertens   341 Jul 15 13:28 flake.nix
-rw-r--r-- 1 wmertens   245 Jul 15 13:19 package.json

$ cat package.json 
{
  "name": "es",
  "version": "1.0.0",
  "description": "",
  "main": "index.js",
  "scripts": {
    "test": "echo \"Error: no test specified\" && exit 1"
  },
  "dependencies": {"eslint": "*"},
  "author": "Wout Mertens",
  "license": "ISC"
}

$ cat flake.nix  
{
  inputs.dream2nix.url = "github:wmertens/dream2nix/devShells";
  outputs = inp:
    let
      l = inp.dream2nix.inputs.nixpkgs.lib // builtins;
    in
    inp.dream2nix.lib.makeFlakeOutputs {
      # modify according to your supported systems
      systems = ["x86_64-linux"];
      config.projectRoot = ./.;
      source = ./.;
    };
}

$ nix run .#resolveImpure
warning: creating lock file '/home/wmertens/lkjh/es/flake.lock'
Resolving:: Name: es; Subsystem: nodejs; relPath: 

up to date, audited 84 packages in 4s

13 packages are looking for funding
  run `npm fund` for details

found 0 vulnerabilities
adding file to git: dream2nix-packages/es/dream-lock.json

$ nix build

$ tree result/
result//
`-- lib/
    `-- node_modules/
        `-- es/
            |-- dream2nix-packages/
            |   `-- es/
            |       `-- dream-lock.json
            |-- flake.lock
            |-- flake.nix
            |-- node_modules -> /nix/store/64ikwh1156a7lrcfwvn529zgn8gpp3ia-node_modules-es/
            `-- package.json

6 directories, 4 files

$ tree result/lib/node_modules/es/node_modules
result/lib/node_modules/es/node_modules@
|-- eslint -> /nix/store/a8dlwp74bz1lm7mcgl9fp08y5yb1940g-eslint-utils-3.0.0/lib/node_modules/eslint/
|-- eslint-utils -> /nix/store/a8dlwp74bz1lm7mcgl9fp08y5yb1940g-eslint-utils-3.0.0/lib/node_modules/eslint-utils/
`-- null -> /nix/store/0rv6w1bn3sz4fl88qdlgl6diwg6kikdk-null-2.0.0/lib/node_modules/null/

3 directories, 0 files

(the null is a bug, I'll fix it)

As you can see, eslint and eslint-utils are together in the same store path

DavHau commented 2 years ago

Anyway, the eslint example you gave doesn't have eslint in node_modules:

$ ll
total 4
-rw-r--r-- 1 wmertens 491 Jul 15 12:05 flake.nix

$ cat flake.nix 
{
  inputs.dream2nix.url = "github:nix-community/dream2nix";
  inputs.src = {flake = false; url = "github:eslint/eslint";};
  outputs = inp:
    let
      l = inp.dream2nix.inputs.nixpkgs.lib // builtins;
    in
    inp.dream2nix.lib.makeFlakeOutputs {
      # modify according to your supported systems
      systems = ["x86_64-linux"];
      config.projectRoot = ./.;
      source = l.path {
        path = inp.src;
        filter = path: _: ! l.hasInfix "/tests/" path;
      };
    };
}

$ nix develop
warning: creating lock file '/home/wmertens/lkjh/es/flake.lock'
$ tree -a node_modules
node_modules@
`-- .bin/

1 directory, 0 files
$ nix build
$ tree -a result
result@
`-- lib/
    `-- node_modules/
        `-- eslint-config-eslint/
            |-- LICENSE
            |-- README.md
            |-- default.yml
            |-- index.js
            |-- node_modules/
            |-- package.json
            `-- package.json.bak

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 eslint-config-eslint.

That's a bug and we should fix it. Though the node_modules logic seems just fine if I enter the correct devShell:

> 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
wmertens commented 2 years ago

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.

DavHau commented 2 years ago

The reason it detects eslint-utils is because it considers eslint a cyclee.

Not sure what you mean. eslint-utils is a direct dependency of eslint. It is installed as it should be.

And actually, eslint-utils should have eslint in its node_modules here and it doesn't. So that's a cyclic bug.

That has nothing to do with cycles. Upstream NPM does not put eslint inside eslint-utils node_modules as well:

# 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

eslint-utils doesn't need to have eslint in its node_modules as eslint already exists in the parent node_modules.

The issue we're running into with the current dream2nix is a peerDependency issue. eslint-utils is declaring eslint as a peerDependency and peer dependenceis are not part of the v1 lockfile which we are parsing. This is a problem we should think about, but it's not a problem introduced by cycles.

wmertens commented 2 years ago

it's a peer dep but also a cycle. Because it's a cycle it's been semi-randomly selected as the default package. When using a tree of symlinks as we do, all the peer deps have to be present in eslint-utils' node_modules as well.

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.

wmertens commented 2 years ago

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.

$ ll
total 16
-rw-r--r-- 1 wmertens  336 Jul 15 15:31 flake.nix
-rw-r--r-- 1 wmertens  108 Jul 15 15:41 package.json

$ cat *
{
  inputs.dream2nix.url = "github:nix-community/dream2nix";
  outputs = inp:
    let
      l = inp.dream2nix.inputs.nixpkgs.lib // builtins;
    in
    inp.dream2nix.lib.makeFlakeOutputs {
      # modify according to your supported systems
      systems = ["x86_64-linux"];
      config.projectRoot = ./.;
      source = ./.;
    };
}
{
  "name": "cycle-test",
  "dependencies": {
    "node-sp-auth": "*",
    "node-sp-auth-config": "*"
  }
}

$ npm i --package-lock-only 
npm WARN deprecated request@2.88.2: request has been deprecated, see https://github.com/request/request/issues/3142
npm WARN deprecated har-validator@5.1.5: this library is no longer supported
npm notice created a lockfile as package-lock.json. You should commit this file.
npm WARN cycle-test@ No description
npm WARN cycle-test@ No repository field.
npm WARN cycle-test@ No license field.

added 173 packages and audited 173 packages in 2.62s
found 2 moderate severity vulnerabilities
  run `npm audit fix` to fix them, or `npm audit` for details

$ nix develop

$ ll node_modules/
total 8
lrwxrwxrwx 3 root  92 Jan  1  1970 node-sp-auth -> /nix/store/l7jdi0r6q7snv51wiyl0pbdbjhffp0p1-node-sp-auth-3.0.5/lib/node_modules/node-sp-auth/
lrwxrwxrwx 2 root 106 Jan  1  1970 node-sp-auth-config -> /nix/store/ciy6555da7a8kigzp8ikasjmz7z5hpm5-node-sp-auth-config-3.0.2/lib/node_modules/node-sp-auth-config/

$ node -r node-sp-auth-config
internal/modules/cjs/loader.js:905
  throw err;
  ^

Error: Cannot find module 'node-sp-auth'
Require stack:
- /nix/store/xddgcymm08qmcj9cf2a61waapc4m71ag-node-sp-auth-config-3.0.1/lib/node_modules/node-sp-auth-config/dist/index.js
- /nix/store/l7jdi0r6q7snv51wiyl0pbdbjhffp0p1-node-sp-auth-3.0.5/lib/node_modules/node-sp-auth/lib/src/auth/resolvers/FileConfig.js
- /nix/store/l7jdi0r6q7snv51wiyl0pbdbjhffp0p1-node-sp-auth-3.0.5/lib/node_modules/node-sp-auth/lib/src/auth/AuthResolverFactory.js
- /nix/store/l7jdi0r6q7snv51wiyl0pbdbjhffp0p1-node-sp-auth-3.0.5/lib/node_modules/node-sp-auth/lib/src/index.js
- /nix/store/ciy6555da7a8kigzp8ikasjmz7z5hpm5-node-sp-auth-config-3.0.2/lib/node_modules/node-sp-auth-config/dist/index.js
- internal/preload
    at Function.Module._resolveFilename (internal/modules/cjs/loader.js:902:15)
    at Function.Module._load (internal/modules/cjs/loader.js:746:27)
    at Module.require (internal/modules/cjs/loader.js:974:19)
    at require (internal/modules/cjs/helpers.js:101:18)
    at Object.<anonymous> (/nix/store/xddgcymm08qmcj9cf2a61waapc4m71ag-node-sp-auth-config-3.0.1/lib/node_modules/node-sp-auth-config/dist/index.js:65:22)
    at Module._compile (internal/modules/cjs/loader.js:1085:14)
    at Object.Module._extensions..js (internal/modules/cjs/loader.js:1114:10)
    at Module.load (internal/modules/cjs/loader.js:950:32)
    at Function.Module._load (internal/modules/cjs/loader.js:790:12)
    at Module.require (internal/modules/cjs/loader.js:974:19) {
  code: 'MODULE_NOT_FOUND',
  requireStack: [
    '/nix/store/xddgcymm08qmcj9cf2a61waapc4m71ag-node-sp-auth-config-3.0.1/lib/node_modules/node-sp-auth-config/dist/index.js',
    '/nix/store/l7jdi0r6q7snv51wiyl0pbdbjhffp0p1-node-sp-auth-3.0.5/lib/node_modules/node-sp-auth/lib/src/auth/resolvers/FileConfig.js',
    '/nix/store/l7jdi0r6q7snv51wiyl0pbdbjhffp0p1-node-sp-auth-3.0.5/lib/node_modules/node-sp-auth/lib/src/auth/AuthResolverFactory.js',
    '/nix/store/l7jdi0r6q7snv51wiyl0pbdbjhffp0p1-node-sp-auth-3.0.5/lib/node_modules/node-sp-auth/lib/src/index.js',
    '/nix/store/ciy6555da7a8kigzp8ikasjmz7z5hpm5-node-sp-auth-config-3.0.2/lib/node_modules/node-sp-auth-config/dist/index.js',
    'internal/preload'
  ]
}

$ node -r node-sp-auth       
internal/modules/cjs/loader.js:905
  throw err;
  ^

Error: Cannot find module 'node-sp-auth'
Require stack:
- /nix/store/xddgcymm08qmcj9cf2a61waapc4m71ag-node-sp-auth-config-3.0.1/lib/node_modules/node-sp-auth-config/dist/index.js
- /nix/store/l7jdi0r6q7snv51wiyl0pbdbjhffp0p1-node-sp-auth-3.0.5/lib/node_modules/node-sp-auth/lib/src/auth/resolvers/FileConfig.js
- /nix/store/l7jdi0r6q7snv51wiyl0pbdbjhffp0p1-node-sp-auth-3.0.5/lib/node_modules/node-sp-auth/lib/src/auth/AuthResolverFactory.js
- /nix/store/l7jdi0r6q7snv51wiyl0pbdbjhffp0p1-node-sp-auth-3.0.5/lib/node_modules/node-sp-auth/lib/src/index.js
- internal/preload
    at Function.Module._resolveFilename (internal/modules/cjs/loader.js:902:15)
    at Function.Module._load (internal/modules/cjs/loader.js:746:27)
    at Module.require (internal/modules/cjs/loader.js:974:19)
    at require (internal/modules/cjs/helpers.js:101:18)
    at Object.<anonymous> (/nix/store/xddgcymm08qmcj9cf2a61waapc4m71ag-node-sp-auth-config-3.0.1/lib/node_modules/node-sp-auth-config/dist/index.js:65:22)
    at Module._compile (internal/modules/cjs/loader.js:1085:14)
    at Object.Module._extensions..js (internal/modules/cjs/loader.js:1114:10)
    at Module.load (internal/modules/cjs/loader.js:950:32)
    at Function.Module._load (internal/modules/cjs/loader.js:790:12)
    at Module.require (internal/modules/cjs/loader.js:974:19) {
  code: 'MODULE_NOT_FOUND',
  requireStack: [
    '/nix/store/xddgcymm08qmcj9cf2a61waapc4m71ag-node-sp-auth-config-3.0.1/lib/node_modules/node-sp-auth-config/dist/index.js',
    '/nix/store/l7jdi0r6q7snv51wiyl0pbdbjhffp0p1-node-sp-auth-3.0.5/lib/node_modules/node-sp-auth/lib/src/auth/resolvers/FileConfig.js',
    '/nix/store/l7jdi0r6q7snv51wiyl0pbdbjhffp0p1-node-sp-auth-3.0.5/lib/node_modules/node-sp-auth/lib/src/auth/AuthResolverFactory.js',
    '/nix/store/l7jdi0r6q7snv51wiyl0pbdbjhffp0p1-node-sp-auth-3.0.5/lib/node_modules/node-sp-auth/lib/src/index.js',
    'internal/preload'
  ]
}
wmertens commented 2 years ago

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.

wmertens commented 2 years ago

How about this recursive algorithm: (pretend versions are part of dep)

Call the algorithm on pkg with seen = {}.

Not quite sure how to implement this in Nix, especially the shared cycles list and the cycle merging. I think this will result in correct set of cycles, and then the packages closest to the start + shortest name should be picked as the set leaders.

DavHau commented 2 years ago

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.

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: Our dependency tree consists of nodes of candidates, where each candidate is a (pname, version) tuple, or in other words, a specific version of a specific package. A candidate is the basic element for which we want to prevent cycles. A candidate should not end up depending on itself. But it can depend on another version of the same package without any problem. For example prettier always depends on an older version of itself, because they want to format their code with their own tool. That is completely fine. No cycle here.

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.

wmertens commented 2 years ago

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?

nixos-discourse commented 2 years ago

This issue has been mentioned on NixOS Discourse. There might be relevant details there:

https://discourse.nixos.org/t/how-to-implement-this-recursive-algorithm-in-nix-shared-object-being-built-up/20384/1

wmertens commented 2 years ago

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 {"dep#ver"="firstdep#ver";} with every dep mentioned and the firstdep pointing to itself.

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.

wmertens commented 2 years ago

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)

wmertens commented 2 years ago

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.

DavHau commented 2 years ago

Another thought: 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)

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 dream-lock.nix. If we later come to the conclusion that this algorithm will be superior for most ecosystems, we can still move it to dream-lock.nix.

wmertens commented 2 years ago

This algorithm gives a more accurate result than the current one and it seems fast (O(n)). I think this belongs in src/utils/translator.nix once it returns the same format? The other code won't notice a difference IMHO.

For JS multi versions, I'm specifically talking about a case like (example):

  "eslint-utils#3.0.0" = [ "eslint#8.18.0" "eslint-utils#3.0.0" "eslint-utils#3.0.1" ];

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).

wmertens commented 2 years ago

(I updated the example above btw)

wmertens commented 2 years ago

:thinking: 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")

wmertens commented 2 years ago

It is now fully working with https://github.com/nix-community/dream2nix/pull/195/commits/f52019be5595c6d31043496e7d246e0703fcf163

Here's a comparison of the output, as you can see it is backwards compatible. new:

{
    "@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"; }
      ];
    };
}