Package version resolve from registry is not deterministic

[blexrob]

This issue is a bug.

** Summary **

The package version resolving mechanism (resolving a pattern to a actual version) in package-request/package-resolver.js is not deterministic. Specifically, the order of the responses to version request can influence the resolving of a pattern.

** Analysis **

In package-request.js, the following code (in find) is relevant:

    const resolved: ?Manifest = this.resolver.getHighestRangeVersionMatch(name, range);
    if (resolved) {
      this.reportResolvedRangeMatch(info, resolved);

Let's say we have a package X with three requested patterns:
A. [email protected]
B. X@^1.0.0
C. [email protected]

If the version requests come back in order ABC, the following happens:

1. A resolves to version 1.1.0, and is stored in the requester.
2. B resolves to 1.2.0, but is also a match with 1.1.0, so 1.1.0 is used.
3. C resolves to 1.2.0, not a match with 1.2.0, so 1.2.0 is used and stored.

But, if the versions requests resolve in order ACB, the following happens:

1. A resolves to version 1.1.0, and is stored in the requester.
2. C resolves to 1.2.0, not a match with 1.2.0, so 1.2.0 is used and stored.
3. B resolves to 1.2.0, which is also the highest match in the resolver.

So, depending on the order of the package version resolves, the resolved version can change.
(in this case, ^1.0.0 can resolve to either 1.1.0 or 1.2.0)

Repro:
Create the following package.json

{ "dependencies": {
     "graceful-fs": "4.1.10",
     "write-file-atomic": "1.3.4",
     "path-type": "1.1.0"
     }
}

and run the following command several times:

rm -rf node_modules/ yarn.lock ; /opt/src/yarn/bin/yarn && /opt/src/yarn/bin/yarn check

Sometimes yarn check will report errors, if the resolver got different versions for graceful-fs than the previous yarn run (requested versions: '4.1.10', '^4.1.2' and '4.1.11').

Versions:
Fedora 25
Node 7.10.0
yarn: git commit 67fe99, from 20170519

[bestander]

Thanks for the steps and analysis!
This is a hi pri issue, we need to sort it out ASAP.
Anyone wants to help?