[BUG] Peer dependency semver ranges is not respected

[ktalebian]

The new npm7 is installing and resolving peer dependencies automatically, but it looks like it has some bug with resolving dependencies that are in multiple packages. Take a look at this error:

npm ERR! Could not resolve dependency:
npm ERR! peer react@"^16.14.0" from [email protected]
npm ERR! node_modules/enzyme-adapter-react-16/node_modules/react-test-renderer
npm ERR!   react-test-renderer@"^16.0.0-0" from [email protected]
npm ERR!   node_modules/enzyme-adapter-react-16
npm ERR!     enzyme-adapter-react-16@"^1.14.0" from [email protected]
npm ERR!     node_modules/flex-plugin-test
npm ERR!       flex-plugin-test@"^4.3.5-beta.0" from [email protected]
npm ERR!       node_modules/flex-plugin-scripts

The package.json's dependencies in this example are:

"dependencies": {
    "flex-plugin-scripts": "^4.3.5-beta.0",
    "react": "16.5.2",
    "react-dom": "16.5.2"
}

Now, flex-plugin-scripts installs flex-plugin-test which installs enzyme-adapter-react-16 which installs react-test-renderer which is requiring [email protected].

Now, the latest version of react-test-renderer 16.14.0 does have a peerDependency of "react": "^16.14.0" (I have filed a separate PR on Jest GitHub as their GitHub tags are all messed up - to verify these versions you may want to check the packages by installing them locally; you wouldn't get the right link on GitHub). However, lower versinoed react-test-renderer do have a "react": "^16.0.0".

So npm is choosing to install the latest version of react-test-renderer (even though the range is `^16.0.0) which is causing it to install react 16.14.0 which then conflicts with my pinned version.

Steps to reproduce

1. Install npm7 `npm install -g npm@next-7
2. Copy/paste the following package.json:

{
  "name": "plugin-npm",
  "version": "0.0.0",
  "scripts": {
    "postinstall": "flex-plugin pre-script-check"
  },
  "dependencies": {
    "flex-plugin-scripts": "^4.3.5-beta.0",
    "react": "16.5.2",
    "react-dom": "16.5.2"
  },
  "devDependencies": {
    "@twilio/flex-ui": "^1"
  }
}

3. Run npm install

Environment:

➜ node  -v
v12.18.3
➜ npm -v
7.0.10

[ljharb]

I think this is related to the bug that npm/arborist#182 fixes?

[ktalebian]

@ljharb looks like it

[isaacs]

This is not fixed by npm/arborist#182. The issue here is a bit more subtle.

This is a class of problem that we don't address currently. Consider a set of dependencies like this:

a -> b
b -> c
c -> d
...
o -> p
p@1 -> q@1
p@2 -> q@2
q@1 -> r@1
q@2 -> r@2
...
y@1 -> z@1
y@2 -> z@2
z@1 -> PEER(dep@1)
z@2 -> PEER(dep@2)

a depends on any version of b, b on some version of c and so on. p@1 depends on q@1, p@2 depends on q@2, effectively "splitting" the chain. At that point, choosing p@1 will result in dep@1 eventually having to be installed, and choosing p@2 will result in dep@2 having to be installed.

Then root project, let's say, depends on a, dep@1.

In order to address this, we'd have to walk all the way back up the dependency chain looking for a path that doesn't eventually lead to dep@2. And part of the challenge is even knowing where to branch! (The fact that it seems obvious to you that react-test-renderer is the thing to downgrade, is part of why human brains are so amazing. We're uncannily good at finding one-off solutions to NP-hard problems! Evolution is cool ;) Not so helpful for designing general solutions in software, tough.)

While this is theoretically possible, it's also an unbounded graph traversal problem, and NP-hard. And it will often be the case that, even after any arbitrary number of steps, we still have not found a solution, while a prohibitively large search space still remains.

I've thought of some heuristics that could be interesting to apply here, in future npm versions, building on the PubGrub algorithm. In a nutshell:

1. Make a note that z@2 cannot coexist with dep@1.
2. Find all deps that depend on z, and flag any depending exclusively on z@2 as cannot coexist with dep@1 (flags y@2).
3. Continue until we find a dependent that does not exclusively rely on something flagged (o -> p), and restart the resolution from that point.

In this case, that would then avoid p@2, and all would be well. We could also limit this to some arbitrary amount, to say, "I tried 1000 passes and still couldn't find a solution, if you want me to try harder, run with --try-harder enabled".

This is not far off from the algorithm used to resolve audit advisories. But, it's worth noting, doing that audit resolution can be rather costly a lot of the time, which is exactly why we now cache the meta-vulnerability information so extensively.

In the meantime, I recommend pinning to a lower version of react-test-renderer, or updating your app to use react 16.14.0.

Closing sadly as "wontfix", but also, "is provably impossible to fix". Sorry. :(