Rewrite pub's version solver.

Rewrite pub's version solver.

The idea of this change is to eagerly check, before selecting a package version,
whether that version is compatible with the existing dependencies. This avoids a
bunch of unnecessary backtracking, and makes the progression of the solver more
comprehensible when

R=rnystrom@google.com
BUG= dartbug.com/17429

Committed: https://code.google.com/p/dart/source/detail?r=45799

[Bob Nystrom, 2015-05-14 18:09:39]

This looks really nice.

However, I really would like to have a test case or two that hits the
pathological behavior this fixes. In the past, I've done that by hacking pub to
dump out the pubspecs its using on a real-world to something that matches the
version_solver_test DSL. Then I bring that in and try to winnow it down while
still preserving the bad behavior.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
File sdk/lib/_internal/pub/lib/src/package.dart (right):

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/package.dart:300: /// Magic packages are
unversioned pub constructs that have special semantics.
Given the name "magic", this really needs a more detailed explanation. Also, how
about moving it up to the "magic" constructor since that's where it first
appears?

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/package.dart:332: /// Creates a reference to a
magic package (see [isMagic]).
see [_PackageName.isMagic].

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/package.dart:362: /// Creates an ID for a magic
package (see [isMagic]).
Ditto.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
File sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:104: final
_versions = new List<VersionQueue>();
Why change to a constructor?

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:278: await
Future.doWhile(() async {
Add a TODO for the bug.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:297: if (!(await
_backtrack())) {
if (await _backtrack()) return true;

...

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:344: /// Gets all
versions of [ref] that might be selected, other than [locked].
"might" -> "could"?

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:398: var
foundVersion;
Initialize it to true here and remove the assignment below?

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:432: return
Future.doWhile(() async {
// TODO

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:566: /// Returns
the dependencies for the package identified by [id].
"for" -> "of"? "For" is kind of ambiguous to me. It could either be the
package's dependencies, or the dependencies onto the package.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:637: var prefix =
_selection.ids.skip(1).map((_) => '| ').join();
"| " * (_selection.ids.length - 1);

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
File sdk/lib/_internal/pub/lib/src/solver/unselected_package_queue.dart (right):

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/unselected_package_queue.dart:19: /// and
when. It's sorted so that the earliest packages should be selected
"sorted so" -> "ordered such that"

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/unselected_package_queue.dart:45: /// Adds
[ref] to the queue.
Mention that if [ref] is already in the queue, it won't be added again.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/unselected_package_queue.dart:107: if
(versions1 != versions2) return versions1 - versions2;
Instead of "-", I usually use versions1.compareTo(versions2);

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
File sdk/lib/_internal/pub/lib/src/solver/version_selection.dart (right):

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:23: /// A
[VersionSelection] is always expected to be internally consistent. That
Remove "expected to be".

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:24: /// is, all
selected packages will be compatible with dependencies on those
Future -> present tense.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:32: /// The packages
that have been selected, in the other they were selected.
"other" -> "order".

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:33: List<PackageId>
get ids => new UnmodifiableListView<PackageId>(_ids);
Is this worth doing?

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:34: final _ids = new
List<PackageId>();
<PackageId>[];

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:37: /// packages.
This sentence is a bit hard to unpack. How about something a bit more verbose,
like:

"Tracks all of the dependencies on a given package.

Each key is a package. The value is the list of dependencies placed on that
package."

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:52: /// Adds [id] to
the selection.
Maybe "select()"?

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:57: // TODO(nweiz):
Use a real for loop when issue 23394 is fixed.
How about:

// Add all of id's dependencies to the selection.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:59: var deps =
getDependencies(dep.name);
How about:

// Add the new dependency to the existing dependencies on id.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:77: Future
removeLast() async {
"unselectLast()"?

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:88: // If this was
the last pakage that depended on barback, get rid of
"pakage" -> "package"

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:135: /// Gets the
list of dependencies for package [name].
"dependencies for" -> "known dependencies on"

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:138:
List<Dependency> getDependencies(String name) =>
Maybe "getDependenciesOn"?

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/t...
File sdk/lib/_internal/pub/test/get/hosted/get_test.dart (right):

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/t...
sdk/lib/_internal/pub/test/get/hosted/get_test.dart:24: solo_integration('URL
encodes the package name', () {
Oops!

[nweiz, 2015-05-14 22:03:57]

Code review changes

[nweiz, 2015-05-14 22:08:01]

> However, I really would like to have a test case or two that hits the
> pathological behavior this fixes. In the past, I've done that by hacking pub
to
> dump out the pubspecs its using on a real-world to something that matches the
> version_solver_test DSL. Then I bring that in and try to winnow it down while
> still preserving the bad behavior.

I realized while poking around with this that I'd broken the attempted solution
counter. I fixed it, and it turned out that several of the existing tests that
expected a substantial amount of backtracking now use much less. So I think they
serve as adequate verification of the improvements in this CL.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
File sdk/lib/_internal/pub/lib/src/package.dart (right):

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/package.dart:300: /// Magic packages are
unversioned pub constructs that have special semantics.
On 2015/05/14 18:09:37, Bob Nystrom wrote:
> Given the name "magic", this really needs a more detailed explanation.

Done.

> Also, how
> about moving it up to the "magic" constructor since that's where it first
> appears?

I'd rather not do that, since it's shared across _PackageName subclasses and the
_PackageName constructor is private.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/package.dart:332: /// Creates a reference to a
magic package (see [isMagic]).
On 2015/05/14 18:09:38, Bob Nystrom wrote:
> see [_PackageName.isMagic].

I'm pretty sure linking to superclass methods is valid dartdoc? Also, it seems
weird to mention a private class in a doc comment for a public class.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
File sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:104: final
_versions = new List<VersionQueue>();
On 2015/05/14 18:09:38, Bob Nystrom wrote:
> Why change to a constructor?

I deleted this and re-created it, so I didn't remember what the original was. My
sense is that these days we usually use explicit constructors for instance
variables (maybe because it makes all instance collections look consistent), but
I could change it back if you prefer.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:278: await
Future.doWhile(() async {
On 2015/05/14 18:09:38, Bob Nystrom wrote:
> Add a TODO for the bug.

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:297: if (!(await
_backtrack())) {
On 2015/05/14 18:09:38, Bob Nystrom wrote:
> if (await _backtrack()) return true;
> 
> ...

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:344: /// Gets all
versions of [ref] that might be selected, other than [locked].
On 2015/05/14 18:09:38, Bob Nystrom wrote:
> "might" -> "could"?

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:398: var
foundVersion;
On 2015/05/14 18:09:38, Bob Nystrom wrote:
> Initialize it to true here and remove the assignment below?

Done, except with false.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:432: return
Future.doWhile(() async {
On 2015/05/14 18:09:38, Bob Nystrom wrote:
> // TODO

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:566: /// Returns
the dependencies for the package identified by [id].
On 2015/05/14 18:09:38, Bob Nystrom wrote:
> "for" -> "of"? "For" is kind of ambiguous to me. It could either be the
> package's dependencies, or the dependencies onto the package.

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:637: var prefix =
_selection.ids.skip(1).map((_) => '| ').join();
On 2015/05/14 18:09:38, Bob Nystrom wrote:
> "| " * (_selection.ids.length - 1);

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
File sdk/lib/_internal/pub/lib/src/solver/unselected_package_queue.dart (right):

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/unselected_package_queue.dart:19: /// and
when. It's sorted so that the earliest packages should be selected
On 2015/05/14 18:09:38, Bob Nystrom wrote:
> "sorted so" -> "ordered such that"

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/unselected_package_queue.dart:45: /// Adds
[ref] to the queue.
On 2015/05/14 18:09:38, Bob Nystrom wrote:
> Mention that if [ref] is already in the queue, it won't be added again.

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/unselected_package_queue.dart:107: if
(versions1 != versions2) return versions1 - versions2;
On 2015/05/14 18:09:38, Bob Nystrom wrote:
> Instead of "-", I usually use versions1.compareTo(versions2);

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
File sdk/lib/_internal/pub/lib/src/solver/version_selection.dart (right):

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:23: /// A
[VersionSelection] is always expected to be internally consistent. That
On 2015/05/14 18:09:38, Bob Nystrom wrote:
> Remove "expected to be".

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:24: /// is, all
selected packages will be compatible with dependencies on those
On 2015/05/14 18:09:39, Bob Nystrom wrote:
> Future -> present tense.

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:32: /// The packages
that have been selected, in the other they were selected.
On 2015/05/14 18:09:39, Bob Nystrom wrote:
> "other" -> "order".

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:33: List<PackageId>
get ids => new UnmodifiableListView<PackageId>(_ids);
On 2015/05/14 18:09:39, Bob Nystrom wrote:
> Is this worth doing?

Maybe not? I like doing it kind of as a matter of course, since I don't think it
adds much overhead at all.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:34: final _ids = new
List<PackageId>();
On 2015/05/14 18:09:38, Bob Nystrom wrote:
> <PackageId>[];

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:37: /// packages.
On 2015/05/14 18:09:39, Bob Nystrom wrote:
> This sentence is a bit hard to unpack. How about something a bit more verbose,
> like:
> 
> "Tracks all of the dependencies on a given package.
> 
> Each key is a package. The value is the list of dependencies placed on that
> package."

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:52: /// Adds [id] to
the selection.
On 2015/05/14 18:09:38, Bob Nystrom wrote:
> Maybe "select()"?

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:57: // TODO(nweiz):
Use a real for loop when issue 23394 is fixed.
On 2015/05/14 18:09:39, Bob Nystrom wrote:
> How about:
> 
> // Add all of id's dependencies to the selection.

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:59: var deps =
getDependencies(dep.name);
On 2015/05/14 18:09:39, Bob Nystrom wrote:
> How about:
> 
> // Add the new dependency to the existing dependencies on id.

I think this is redundant with the new comment on the loop.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:77: Future
removeLast() async {
On 2015/05/14 18:09:38, Bob Nystrom wrote:
> "unselectLast()"?

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:88: // If this was
the last pakage that depended on barback, get rid of
On 2015/05/14 18:09:39, Bob Nystrom wrote:
> "pakage" -> "package"

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:135: /// Gets the
list of dependencies for package [name].
On 2015/05/14 18:09:38, Bob Nystrom wrote:
> "dependencies for" -> "known dependencies on"

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:138:
List<Dependency> getDependencies(String name) =>
On 2015/05/14 18:09:39, Bob Nystrom wrote:
> Maybe "getDependenciesOn"?

Done.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/t...
File sdk/lib/_internal/pub/test/get/hosted/get_test.dart (right):

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/t...
sdk/lib/_internal/pub/test/get/hosted/get_test.dart:24: solo_integration('URL
encodes the package name', () {
On 2015/05/14 18:09:39, Bob Nystrom wrote:
> Oops!

Oops.

[Bob Nystrom, 2015-05-14 22:13:02]

> I realized while poking around with this that I'd broken the attempted
solution
> counter. I fixed it, and it turned out that several of the existing tests that
> expected a substantial amount of backtracking now use much less. So I think
they
> serve as adequate verification of the improvements in this CL.

SGTM.

LGTM!

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
File sdk/lib/_internal/pub/lib/src/package.dart (right):

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/package.dart:332: /// Creates a reference to a
magic package (see [isMagic]).
On 2015/05/14 22:08:00, nweiz wrote:
> On 2015/05/14 18:09:38, Bob Nystrom wrote:
> > see [_PackageName.isMagic].
> 
> I'm pretty sure linking to superclass methods is valid dartdoc? Also, it seems
> weird to mention a private class in a doc comment for a public class.

Oh, right. Forgot this was a subclass. :)

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
File sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:104: final
_versions = new List<VersionQueue>();
On 2015/05/14 22:08:00, nweiz wrote:
> On 2015/05/14 18:09:38, Bob Nystrom wrote:
> > Why change to a constructor?
> 
> I deleted this and re-created it, so I didn't remember what the original was.
My
> sense is that these days we usually use explicit constructors for instance
> variables (maybe because it makes all instance collections look consistent),
but
> I could change it back if you prefer.

Yeah, I always use the literal form when possible. It's terser.

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
File sdk/lib/_internal/pub/lib/src/solver/version_selection.dart (right):

https://codereview.chromium.org/1140083005/diff/20001/sdk/lib/_internal/pub/l...
sdk/lib/_internal/pub/lib/src/solver/version_selection.dart:33: List<PackageId>
get ids => new UnmodifiableListView<PackageId>(_ids);
On 2015/05/14 22:08:00, nweiz wrote:
> On 2015/05/14 18:09:39, Bob Nystrom wrote:
> > Is this worth doing?
> 
> Maybe not? I like doing it kind of as a matter of course, since I don't think
it
> adds much overhead at all.

<shrug>

In general, I don't worry too much about exposing mutable objects to other parts
of the same application (public library APIs are a different matter), but if you
think it aids maintainability, sure.

[nweiz, 2015-05-14 22:33:19]

Code review changes

[nweiz, 2015-05-14 22:33:43]

Committed patchset #4 (id:60001) manually as 45799 (presubmit successful).