Avoid network requests while resolving versions when possible.

Avoid network requests while resolving versions when possible.

BUG=https://code.google.com/p/dart/issues/detail?id=10807
R=nweiz@google.com

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

[nweiz, 2013-11-21 22:28:26]

It would be nice to have a test where some but not all of the packages have
requests made for them.

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

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:81: /// the
versions provided a solution.
Update this comment to describe the new contents of [_selected].

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:225: return new
Future.value(true);
[Future.value] here and below seems unnecessary, since this is in a [then]
callback.

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:292: ///
depenedncy on C. We would end up backjumping over A and failing.
"depenedncy" -> "dependency"

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:323: }
This is still O(n^2) in the number of selected packages. We can make it O(n) by
just reversing the graph here and following the dependency chain backwards
through the reversed graph.

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:394:
Future<Iterable<PackageId>> getAllowedVersions(PackageDep dep,
It feels icky to me to expose this publicly and pass the Traverser into the
VersionQueue.

The semantics that are going on here are that the traverser is passing the
VersionQueue a list of versions, but this list should only be computed once the
VersionQueue requests it. What do you think about abstracting this pattern into
a Thunk<T> class? For example:

    class Thunk<T> {
      Future<T> get value;
      Thunk(Future<T> compute());
    }

Then VersionQueue could take a Thunk<Iterable<PackageId>> and avoid being
tightly coupled to Traverser, and this code could remain internal. This would
also make it clearer what the configuration surface between Traverser and
VersionQueue is.

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:603: PackageId
getValidLocked(String name, VersionConstraint constraint) {
This is another method that I'd rather see remain private and have the result
passed in to [VersionQueue].

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
File sdk/lib/_internal/pub/lib/src/solver/dependency_queue.dart (right):

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/dependency_queue.dart:20: /// single
version to consider.
This behavior isn't just for performance, is it? Isn't it also important to
ensure that locked package versions are preferred to un-locked versions?

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/dependency_queue.dart:41: final
List<PackageDep> _remaining;
If we're calling `removeAt(0)` on this repeatedly, it should probably also be a
Queue.

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/dependency_queue.dart:80: if (!_isSorted)
return _sort().then((_) => _remaining.removeAt(0));
Currently I think this will behave pretty badly if [advance] is called multiple
times while [_isSorted] is false. We should probably cache the sorting future to
make that case behave correctly.

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
File sdk/lib/_internal/pub/lib/src/solver/version_queue.dart (right):

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/version_queue.dart:26: /// If [_locked] is
not `null`, this will initially be empty until we
"initially be `null`"

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/version_queue.dart:78: var locked =
_locked;
Unused variable

[Bob Nystrom, 2013-11-22 21:40:13]

Added a test of a partially complete lock file too.

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

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:81: /// the
versions provided a solution.
On 2013/11/21 22:28:26, nweiz wrote:
> Update this comment to describe the new contents of [_selected].

Tweaked a bit. The semantics are the same, it's just a real class now.

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:225: return new
Future.value(true);
On 2013/11/21 22:28:26, nweiz wrote:
> [Future.value] here and below seems unnecessary, since this is in a [then]
> callback.

Done.

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:292: ///
depenedncy on C. We would end up backjumping over A and failing.
On 2013/11/21 22:28:26, nweiz wrote:
> "depenedncy" -> "dependency"

Done.

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:323: }
On 2013/11/21 22:28:26, nweiz wrote:
> This is still O(n^2) in the number of selected packages. We can make it O(n)
by
> just reversing the graph here and following the dependency chain backwards
> through the reversed graph.

Done.

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:394:
Future<Iterable<PackageId>> getAllowedVersions(PackageDep dep,
On 2013/11/21 22:28:26, nweiz wrote:
> It feels icky to me to expose this publicly and pass the Traverser into the
> VersionQueue.
> 
> The semantics that are going on here are that the traverser is passing the
> VersionQueue a list of versions, but this list should only be computed once
the
> VersionQueue requests it. 

Yup, but I like that at least some of the code for determining what that list is
is moved into VersionQueue itself. It makes Traverser a bit less monolithic.

> What do you think about abstracting this pattern into
> a Thunk<T> class? For example:
> 
>     class Thunk<T> {
>       Future<T> get value;
>       Thunk(Future<T> compute());
>     }
> 
> Then VersionQueue could take a Thunk<Iterable<PackageId>> and avoid being
> tightly coupled to Traverser, and this code could remain internal. This would
> also make it clearer what the configuration surface between Traverser and
> VersionQueue is.

Done, more or less. I didn't both making a separate Thunk class.

I like that VersionQueue is less visibly coupled to Traverser now, but I'm not
crazy about how that coupling is still there, it's just invisibly hidden in a
closure. <shrug>

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:603: PackageId
getValidLocked(String name, VersionConstraint constraint) {
On 2013/11/21 22:28:26, nweiz wrote:
> This is another method that I'd rather see remain private and have the result
> passed in to [VersionQueue].

Done.

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
File sdk/lib/_internal/pub/lib/src/solver/dependency_queue.dart (right):

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/dependency_queue.dart:20: /// single
version to consider.
On 2013/11/21 22:28:26, nweiz wrote:
> This behavior isn't just for performance, is it? Isn't it also important to
> ensure that locked package versions are preferred to un-locked versions?

Yup. Reworded.

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/dependency_queue.dart:41: final
List<PackageDep> _remaining;
On 2013/11/21 22:28:26, nweiz wrote:
> If we're calling `removeAt(0)` on this repeatedly, it should probably also be
a
> Queue.

It actually adds a fair bit of complexity to make this a queue. Given that items
are pulled off asynchronously, I don't think it's worth optimizing for.

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/dependency_queue.dart:80: if (!_isSorted)
return _sort().then((_) => _remaining.removeAt(0));
On 2013/11/21 22:28:26, nweiz wrote:
> Currently I think this will behave pretty badly if [advance] is called
multiple
> times while [_isSorted] is false. We should probably cache the sorting future
to
> make that case behave correctly.

Lots of other things would be in a bad state if you called advance() in a
re-entrant way. That would violate lots of assumptions about how the solver
works. I'll document that this is not re-entrant.

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
File sdk/lib/_internal/pub/lib/src/solver/version_queue.dart (right):

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/version_queue.dart:26: /// If [_locked] is
not `null`, this will initially be empty until we
On 2013/11/21 22:28:26, nweiz wrote:
> "initially be `null`"

Done.

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/version_queue.dart:78: var locked =
_locked;
On 2013/11/21 22:28:26, nweiz wrote:
> Unused variable

Done.

[nweiz, 2013-11-26 21:00:43]

A few more suggestions, but lgtm

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
File sdk/lib/_internal/pub/lib/src/solver/dependency_queue.dart (right):

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/dependency_queue.dart:80: if (!_isSorted)
return _sort().then((_) => _remaining.removeAt(0));
On 2013/11/22 21:40:13, Bob Nystrom wrote:
> On 2013/11/21 22:28:26, nweiz wrote:
> > Currently I think this will behave pretty badly if [advance] is called
> multiple
> > times while [_isSorted] is false. We should probably cache the sorting
future
> to
> > make that case behave correctly.
> 
> Lots of other things would be in a bad state if you called advance() in a
> re-entrant way. That would violate lots of assumptions about how the solver
> works. I'll document that this is not re-entrant.

Please at least track the old future enough to throw an error if this is called
re-entrantly. It seems like an easy mistake to make unintentionally.

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

https://codereview.chromium.org/79983002/diff/80001/sdk/lib/_internal/pub/lib...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:76: /// Each entry
in the list is [VersionQueue], which is an ordered queue of
"is [VersionQueue]" -> "is a [VersionQueue]"

https://codereview.chromium.org/79983002/diff/80001/sdk/lib/_internal/pub/lib...
File sdk/lib/_internal/pub/lib/src/solver/version_queue.dart (right):

https://codereview.chromium.org/79983002/diff/80001/sdk/lib/_internal/pub/lib...
sdk/lib/_internal/pub/lib/src/solver/version_queue.dart:49: /// versions
asynchronously before we can determine what the first one is.
Update this documentation to reflect the new parameters.

[Bob Nystrom, 2013-11-26 22:12:44]

Committed patchset #2 manually as r30681 (presubmit successful).

[Bob Nystrom, 2013-11-26 22:16:10]

Thanks!

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
File sdk/lib/_internal/pub/lib/src/solver/dependency_queue.dart (right):

https://codereview.chromium.org/79983002/diff/1/sdk/lib/_internal/pub/lib/src...
sdk/lib/_internal/pub/lib/src/solver/dependency_queue.dart:80: if (!_isSorted)
return _sort().then((_) => _remaining.removeAt(0));
On 2013/11/26 21:00:43, nweiz wrote:
> On 2013/11/22 21:40:13, Bob Nystrom wrote:
> > On 2013/11/21 22:28:26, nweiz wrote:
> > > Currently I think this will behave pretty badly if [advance] is called
> > multiple
> > > times while [_isSorted] is false. We should probably cache the sorting
> future
> > to
> > > make that case behave correctly.
> > 
> > Lots of other things would be in a bad state if you called advance() in a
> > re-entrant way. That would violate lots of assumptions about how the solver
> > works. I'll document that this is not re-entrant.
> 
> Please at least track the old future enough to throw an error if this is
called
> re-entrantly. It seems like an easy mistake to make unintentionally.

Done.

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

https://codereview.chromium.org/79983002/diff/80001/sdk/lib/_internal/pub/lib...
sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart:76: /// Each entry
in the list is [VersionQueue], which is an ordered queue of
On 2013/11/26 21:00:43, nweiz wrote:
> "is [VersionQueue]" -> "is a [VersionQueue]"

Done.

https://codereview.chromium.org/79983002/diff/80001/sdk/lib/_internal/pub/lib...
File sdk/lib/_internal/pub/lib/src/solver/version_queue.dart (right):

https://codereview.chromium.org/79983002/diff/80001/sdk/lib/_internal/pub/lib...
sdk/lib/_internal/pub/lib/src/solver/version_queue.dart:49: /// versions
asynchronously before we can determine what the first one is.
On 2013/11/26 21:00:43, nweiz wrote:
> Update this documentation to reflect the new parameters.

Done.