Issue 13095015: Use backtracking when solving dependency constraints.

Bob Nystrom

This isn't ready to go in yet, but I wanted to start getting feedback on ...

7 years, 9 months ago (2013-03-26 22:07:56 UTC) #1

Bob Nystrom

OK, it's at a point where I'd like to start landing this now: - Both ...

7 years, 9 months ago (2013-03-28 18:15:43 UTC) #2

nweiz

As we discussed offline, I would like to see backjumping implemented before this code gets ...

7 years, 9 months ago (2013-03-29 01:58:25 UTC) #3

Bob Nystrom

Thanks! https://codereview.chromium.org/13095015/diff/4001/utils/pub/package.dart File utils/pub/package.dart (right): https://codereview.chromium.org/13095015/diff/4001/utils/pub/package.dart#newcode162 utils/pub/package.dart:162: /// Returns `true` of this references description matches ...

7 years, 8 months ago (2013-03-30 00:15:55 UTC) #4

Thanks!

https://codereview.chromium.org/13095015/diff/4001/utils/pub/package.dart
File utils/pub/package.dart (right):

https://codereview.chromium.org/13095015/diff/4001/utils/pub/package.dart#new...
utils/pub/package.dart:162: /// Returns `true` of this references description
matches [other]'s.
On 2013/03/29 01:58:25, nweiz wrote:
> "of" -> "if", "references" -> "id's"

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/package.dart#new...
utils/pub/package.dart:209: /// Returns `true` of this references description
matches [other]'s.
On 2013/03/29 01:58:25, nweiz wrote:
> "of" -> "if", "references" -> "reference's"

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/path_source.dart
File utils/pub/path_source.dart (right):

https://codereview.chromium.org/13095015/diff/4001/utils/pub/path_source.dart...
utils/pub/path_source.dart:36: try {
On 2013/03/29 01:58:25, nweiz wrote:
> I don't understand why this change is in this CL.

The previous code will fail if you call descriptionsEqual() and either path
doesn't exist. We have tests specifically for working with path deps to
non-existent paths. I believe they passed coincidentally because the old solver
happened to not hit this before it failed to find a solution, but the new solver
does end up comparing descriptions and would crash.

I think this change is a decent one: I don't think descriptionsEqual() should
ever throw given valid arguments.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/path_source.dart...
utils/pub/path_source.dart:42: // If either of the files couldn't be found,
fallback to just comparing
On 2013/03/29 01:58:25, nweiz wrote:
> "fallback" -> "fall back"

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/path_source.dart...
utils/pub/path_source.dart:45: var path2 = path.normalize(description2["path"]);
On 2013/03/29 01:58:25, nweiz wrote:
> Shouldn't you make these absolute here?

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
File utils/pub/version_solver2.dart (right):

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:11: /// piles of memory for both the futures and
the stack traces.
On 2013/03/29 01:58:25, nweiz wrote:
> If you're iterating enough that this becomes a serious problem, you're
iterating
> too much.

The only case where I've seen it be a problem is the pathological test that's
designed to force it to go through a bunch of states.

In normal package graphs the future chain would be as deep as the number of
package's in the dependency graph. That's still kind of nasty when you're trying
to debug, though.

> That said, Futures shouldn't take up stack space proportional to the length of
> the future chain.

They don't take up space on the stack. They take up memory on the heap for the
captured stack traces (and the closure and other state the futures hold).

> What that ultimately means is that they'll take up stack space
> proportional to the length of your program, rather than its depth. File a bug
> about that.

I don't think it's a bug. I think it's a natural consequence of this looping
pattern:

Future process(Queue items) {
  if (items.isEmpty) return new Future.immediate('done');
  return doSomethingWith(items.removeFirst()).then((_) => process(items));
}

The old solver uses the same idiom and it does lead to ugly then chains.

> This also isn't the best way to work around the issue. The stack will reset as
> soon as you pump the event loop, so doing that every now and then will keep it
> from getting too big while still allowing you to use real futures.

See above. It's about the chained futures, not the actual stack.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:30: /// [lockFile]. If successful, completes to a
[Map] that maps package names to
On 2013/03/29 01:58:25, nweiz wrote:
> The type annotation says it completes to a List, not a Map.

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:40: class VersionSolver {
On 2013/03/29 01:58:25, nweiz wrote:
> This needs a lot more explanation of the structure and methodology of what's
> going on. You have scattered comments about this, but it's very difficult to
> piece together a big picture of what's actually going on.

Added lots more docs.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:47: /// only allow the very latest version for
each of these packages.
On 2013/03/29 01:58:25, nweiz wrote:
> I don't know if you care, but this isn't how bundler behaves. It will
backtrack
> even an explicit update.

I do care. The previous solver will always use the absolute latest version or
fail, so I didn't add support for backtracking here. If you'd like, that's
doable (and should be easy). But that will need more tests so I'd like to do
that in a separate patch if that's OK.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:101: var propagator = new Propagator(this,
state);
On 2013/03/29 01:58:25, nweiz wrote:
> There's no need for a variable here.

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:135: /// has been selected.
On 2013/03/29 01:58:25, nweiz wrote:
> This description implies that this just examines the SolveState, when in fact
it
> also modifies the VersionSolver by enqueuing new SolveStates.

Added better docs.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:136: class Propagator {
On 2013/03/29 01:58:25, nweiz wrote:
> Move this and most of the other classes below into their own files. The errors
> can all go in the same file.

Reorganized stuff. version_solver.dart is now the shared stuff (errors,
VersionSolver base class, and cache). version_solver1.dart is the old solver,
version_solver2.dart is the new one.

> 
> This name is also not great. What is being propagated? Along what?

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:139: /// The queue of packages left to traverse.
We do a bread-first traversal
On 2013/03/29 01:58:25, nweiz wrote:
> "bread" -> "breadth"

I would love it if it actually was bread first. I <3 bread.

Fixed.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:148: /// The known dependencies visited so far.
On 2013/03/29 01:58:25, nweiz wrote:
> This isn't a very descriptive comment. What are the keys? What does it mean
that
> there are multiple dependencies for each key?

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:165: void trace([String message]) {
On 2013/03/29 01:58:25, nweiz wrote:
> "trace" is a confusing name. Maybe "printLog" or "printTrace"? Even just "log"
> would be better.

"log" collides with the library prefix. Changed to logSolve().

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:168: if (!log.isEnabled(log.Level.SOLVER))
return;
On 2013/03/29 01:58:25, nweiz wrote:
> This is unnecessary optimization, and we don't do it anywhere else we build
log
> messages.

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:185: /// list of package IDs if the traversal
completely successfully and found a
On 2013/03/29 01:58:25, nweiz wrote:
> "completely" -> "completed"

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:233: void
_traverseRefs(Completer<List<PackageId>> completer,
On 2013/03/29 01:58:25, nweiz wrote:
> This function is gigantic. Split it up?

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:256: required.depender, required.ref.source,
depender, ref.source));
On 2013/03/29 01:58:25, nweiz wrote:
> Never call completeError without a stack trace. The same goes for the rest of
> the errors in this method.

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:297: // Traverse into it.
On 2013/03/29 01:58:25, nweiz wrote:
> You're not actually traversing into the new version here, you're just
enqueueing
> it to get traversed later.

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:329: // Try to continue solving with the first
selected package.
On 2013/03/29 01:58:25, nweiz wrote:
> This doesn't just try the first selected package. This tries every package in
> `allowed`.

This Propagator will only try the first one. Reworded.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:337: print(error);
On 2013/03/29 01:58:25, nweiz wrote:
> Left over from debugging?

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:342: /// Gets the currently selected package
named [package] or `null` if no
On 2013/03/29 01:58:25, nweiz wrote:
> "Gets" -> "Returns", "package named" -> "id for the package named",
"[package]"
> -> "[name]"

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:355: /// non-root dependency on that package. All
dependencies on a package must
On 2013/03/29 01:58:25, nweiz wrote:
> I don't understand "non-root" here. You're only checking that the package
being
> referred to isn't the root package. As I understand it, if that's the case,
all
> [PackageRef]s in the [dependencies] list will be to the root package as well,

All refs will be to the root package, but they may not all be root refs (only
one will be). The other solver has this logic too, it's to handle references
back onto the root package, like:

# myapp
dependencies:
  foo:

# foo
dependencies:
  myapp:

#bar
dependencies:
  myapp:

Here, there will be two references onto myapp, the root one and the hosted one
from foo. In that case, the hosted one is the one we want to return because
that's the one bar's dependency on myapp will have to agree with.

I'll clarify the docs. (It confused me in the old solver when you added this
then.)

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:370: PackageId _getLocked(String name,
VersionConstraint constraint) {
On 2013/03/29 01:58:25, nweiz wrote:
> It's confusing that this has the same name as [VersionSolver.getLocked] but
> slightly different semantics. Change it to something like "_maybeGetLocked" or
> "_getLockedIfCompatible"?

Changed to _getValidLocked().

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:376: var dependencies = _dependencies[name];
On 2013/03/29 01:58:25, nweiz wrote:
> Unused variable.

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:390: /// reflects one of a set of speculative
choices that may turn out to be wrong.
On 2013/03/29 01:58:25, nweiz wrote:
> "possible solution tree" is confusing. Is this just one out of many possible
> trees, each of which represents a solution? Is it a tree, each node of which
is
> a possible solution?
> 
> As I understand it, neither of these is actually the case. It's a tree of
> SolveStates, but a single SolveState doesn't represent a solution, nor does it
> represent a single choice. Instead, each SolveState represents multiple
concrete
> versions of a given package over time.
> 
> The mutability of the SolveStates makes all of this harder to reason about,
> especially since you describe it in terms of exploring static data structures.
> 
> I'm also not convinced that you ever actually build a tree of SolveStates. It
> looks like you just use them as a linked list. It would be good to make that
> more explicit in the structure of the code as well as the documentation.

Removed this class entirely.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:407: if (!log.isEnabled(log.Level.SOLVER))
return;
On 2013/03/29 01:58:25, nweiz wrote:
> Unnecessary optimization.

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:467: final _versions = new Map<PackageId,
List<Version>>();
On 2013/03/29 01:58:25, nweiz wrote:
> The type of the map is wrong. The value type should be List<PackageId>.

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:473: void cache(PackageId id, Pubspec pubspec) {
On 2013/03/29 01:58:25, nweiz wrote:
> This is never called.

The previous solver uses it. This class is unified in the latest code.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:494: Future<List<PackageId>> getVersions(String
package, Source source, description) {
On 2013/03/29 01:58:25, nweiz wrote:
> long line

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:496: var id = new PackageId(package, source,
Version.none, description);
On 2013/03/29 01:58:25, nweiz wrote:
> I don't like using PackageId here just because a subset of its fields happen
to
> be relevant. A PackageId represents a specific version of a package, and
that's
> not what you're using it for.
> 
> Using PackageRef with VersionConstraint.any would be a little better, but
maybe
> it's time to split PackageId into PackageId (without a version) and
> PackageVersionId (which is a PackageId + version).

I'm fine with doing this split, but I would like to not do it in this already
very large patch. Added a TODO.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:504: .map((version) => new PackageId(package,
source, version, description))
On 2013/03/29 01:58:25, nweiz wrote:
> long line

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:521: void _writeDependencies(StringBuffer buffer,
List<Dependency> deps) {
On 2013/03/29 01:58:25, nweiz wrote:
> There's no particular reason for this to be an instance method, is there?

Not really. It keeps it out of global scope but makes it accessible to the
subclasses. Would you rather it be top level?

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:559: class CouldNotUpdateException implements
Exception {
On 2013/03/29 01:58:25, nweiz wrote:
> Why is this commented out? Isn't this a state the solver can get into?

The new solver doesn't seem to use it. As far as I can tell the old solver
doesn't have any tests that hit it either.

In the latest code, this isn't commented out. It should be doable to come up
with a test that hits this.

https://codereview.chromium.org/13095015/diff/4001/utils/tests/pub/install/gi...
File utils/tests/pub/install/git/check_out_and_update_test.dart (right):

https://codereview.chromium.org/13095015/diff/4001/utils/tests/pub/install/gi...
utils/tests/pub/install/git/check_out_and_update_test.dart:13: initConfig();
On 2013/03/29 01:58:25, nweiz wrote:
> In the future, it would be nice to put stuff like this in a separate commit.
> It's hard to tell which test files actually got changed.

Sorry. The only test with actual changes is version_solver.

https://codereview.chromium.org/13095015/diff/4001/utils/tests/pub/version_so...
File utils/tests/pub/version_solver_test.dart (right):

https://codereview.chromium.org/13095015/diff/4001/utils/tests/pub/version_so...
utils/tests/pub/version_solver_test.dart:481: // TODO(rnystrom): Document
better.
On 2013/03/29 01:58:25, nweiz wrote:
> Please do. I don't understand the purpose of this test.

Added better docs.

https://codereview.chromium.org/13095015/diff/7001/utils/pub/version_solver.dart
File utils/pub/version_solver.dart (right):

https://codereview.chromium.org/13095015/diff/7001/utils/pub/version_solver.d...
utils/pub/version_solver.dart:20: import 'version_solver2.dart' as v2;
On 2013/03/29 01:58:25, nweiz wrote:
> Name these after the type of version solver they contain. Also probably make a
> subdirectory for all the version_solver-related files.

Done.

https://codereview.chromium.org/13095015/diff/7001/utils/pub/version_solver.d...
utils/pub/version_solver.dart:28: /// [CouldNotSolveException].
On 2013/03/29 01:58:25, nweiz wrote:
> Document the new arguments.

Done.

https://codereview.chromium.org/13095015/diff/7001/utils/pub/version_solver.d...
utils/pub/version_solver.dart:30: {int solver, LockFile lockFile,
List<PackageRef> useLatest}) {
On 2013/03/29 01:58:25, nweiz wrote:
> Make solver an enum.

Changed to a bool.

https://codereview.chromium.org/13095015/diff/7001/utils/pub/version_solver.d...
utils/pub/version_solver.dart:33: if (solver == null) solver = 2;
On 2013/03/29 01:58:25, nweiz wrote:
> Let's make the existing solver the default for now.

I'll do that if you'll let me submit this patch before implementing backjumping
and whatever other hoops you want me to jump through to convince you this won't
end the world. :)

https://codereview.chromium.org/13095015/diff/7001/utils/pub/version_solver.d...
utils/pub/version_solver.dart:35: if (useLatest == null) useLatest = [];
On 2013/03/29 01:58:25, nweiz wrote:
> Is our style to just avoid using default values other than null?

Yeah, I prefer to avoid them.

https://codereview.chromium.org/13095015/diff/7001/utils/pub/version_solver.d...
utils/pub/version_solver.dart:56: }
On 2013/03/29 01:58:25, nweiz wrote:
> Debugging function, remove it.

Done.

https://codereview.chromium.org/13095015/diff/7001/utils/pub/version_solver.d...
utils/pub/version_solver.dart:145: log.solver('requested ${id} pubspec');
On 2013/03/29 01:58:25, nweiz wrote:
> "${id}" => "$id"

Done.

https://codereview.chromium.org/13095015/diff/7001/utils/pub/version_solver2....
File utils/pub/version_solver2.dart (right):

https://codereview.chromium.org/13095015/diff/7001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:32: const _MAX_BACKTRACKING = 10000;
On 2013/03/29 01:58:25, nweiz wrote:
> As discussed offline, I don't like having an iteration cap.

Done.

Bob Nystrom

The tests now verify the upper limit for backtracking to reach a solution. PTAL.

7 years, 8 months ago (2013-04-02 21:34:41 UTC) #5

nweiz

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2.dart File utils/pub/version_solver2.dart (right): https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2.dart#newcode11 utils/pub/version_solver2.dart:11: /// piles of memory for both the futures and ...

7 years, 8 months ago (2013-04-03 00:28:42 UTC) #6

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
File utils/pub/version_solver2.dart (right):

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:11: /// piles of memory for both the futures and
the stack traces.
On 2013/03/30 00:15:55, Bob Nystrom wrote:
> On 2013/03/29 01:58:25, nweiz wrote:
> > If you're iterating enough that this becomes a serious problem, you're
> iterating
> > too much.
> 
> The only case where I've seen it be a problem is the pathological test that's
> designed to force it to go through a bunch of states.
> 
> In normal package graphs the future chain would be as deep as the number of
> package's in the dependency graph. That's still kind of nasty when you're
trying
> to debug, though.

If the issue is the aesthetics of the stack traces, we have the means to clean
them up outside this code. If the issue is efficiency, there are better ways
around it, as I'll demonstrate below. In neither case does it warrant ugly code.

> They don't take up space on the stack. They take up memory on the heap for the
> captured stack traces (and the closure and other state the futures hold).

This is false. See issue 9583.

Also, Futures don't capture stack traces.

> I don't think it's a bug. I think it's a natural consequence of this looping
> pattern:
> 
> Future process(Queue items) {
>   if (items.isEmpty) return new Future.immediate('done');
>   return doSomethingWith(items.removeFirst()).then((_) => process(items));
> }
> 
> The old solver uses the same idiom and it does lead to ugly then chains.

It's definitely a bug. You shouldn't get a stack overflow unless your code
actually has a call stack a few thousand frames deep. The notion of a "call
stack" is fuzzier when doing async, but even in the most pathological case your
traversal would never go deeper than the number of packages (not package
versions) in the dependency tree.

> See above. It's about the chained futures, not the actual stack.

See my workaround function in issue 9583.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:40: class VersionSolver {
On 2013/03/30 00:15:55, Bob Nystrom wrote:
> On 2013/03/29 01:58:25, nweiz wrote:
> > This needs a lot more explanation of the structure and methodology of what's
> > going on. You have scattered comments about this, but it's very difficult to
> > piece together a big picture of what's actually going on.
> 
> Added lots more docs.

These are lots better, but I've added some more comments.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:47: /// only allow the very latest version for
each of these packages.
On 2013/03/30 00:15:55, Bob Nystrom wrote:
> On 2013/03/29 01:58:25, nweiz wrote:
> > I don't know if you care, but this isn't how bundler behaves. It will
> backtrack
> > even an explicit update.
> 
> I do care. The previous solver will always use the absolute latest version or
> fail, so I didn't add support for backtracking here. If you'd like, that's
> doable (and should be easy). But that will need more tests so I'd like to do
> that in a separate patch if that's OK.

My preference would be to use the current behavior, not bundler's. I think it's
always sort of confusing when bundler selects an old version of a package.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:521: void _writeDependencies(StringBuffer buffer,
List<Dependency> deps) {
On 2013/03/30 00:15:55, Bob Nystrom wrote:
> On 2013/03/29 01:58:25, nweiz wrote:
> > There's no particular reason for this to be an instance method, is there?
> 
> Not really. It keeps it out of global scope but makes it accessible to the
> subclasses. Would you rather it be top level?

Yes, I think so.

https://codereview.chromium.org/13095015/diff/4001/utils/tests/pub/version_so...
File utils/tests/pub/version_solver_test.dart (right):

https://codereview.chromium.org/13095015/diff/4001/utils/tests/pub/version_so...
utils/tests/pub/version_solver_test.dart:503: });
On 2013/03/29 01:58:25, nweiz wrote:
> It seems like a lot more tests are necessarily to fully exercise the new
solver.
> You should at least test that every kind of solution error triggers
backtracking
> and that backtracking finds the "best" solution in various cases where such a
> thing might be ambiguous. I would also like to see tests that measure the
number
> of steps being taken, either by testing the solver logs against an expected
> string or by tracking some sort of counter.

You don't necessarily need to add these in this CL, but if you don't add a TODO
about it.

https://codereview.chromium.org/13095015/diff/7001/utils/pub/version_solver.dart
File utils/pub/version_solver.dart (right):

https://codereview.chromium.org/13095015/diff/7001/utils/pub/version_solver.d...
utils/pub/version_solver.dart:33: if (solver == null) solver = 2;
On 2013/03/30 00:15:55, Bob Nystrom wrote:
> On 2013/03/29 01:58:25, nweiz wrote:
> > Let's make the existing solver the default for now.
> 
> I'll do that if you'll let me submit this patch before implementing
backjumping
> and whatever other hoops you want me to jump through to convince you this
won't
> end the world. :)

I'm willing to LGTM without the backjumper, on the understanding that I'm not
LGTMing the user-visible use of the backtracking solver.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
File utils/pub/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:33: /// solution is found, or there
are no other ones to try.
> This selects package versions from a list of valid options.

This is confusing. The user doesn't pass in a list of valid options. There isn't
anything in the class that looks like a list of valid options. There's nothing
in my knowledge of the algorithm that fits this description (that is, is a
static list of possible versions that the solver chooses from).

> It continues trying solutions and advancing

You haven't defined "solution" yet. Also, what does "advancing" mean? Advancing
through what? How?

> until either a solution is found, or there are no other ones to try.

You're using "solution" to mean two different things in the same sentence. First
you say you're "trying solutions", implying that a solution is a
potentially-valid set of package versions. Then you say "until a solution is
found", implying that a solution is an actually-valid thing you're going to
return to a user.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:40: /// the solver must select a
version for it, sometimes when multiple are
"multiple" -> "multiple versions"

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:45: /// some named package. Each
[Queue] is the ordered list of versions to try
I think you can merge the first two sentences. Something like "Each entry in the
list is an ordered [Queue] of versions to try for a single package."

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:48: /// and popped when the queue is
empty.
The last sentence is less clear than it could be. Maybe "When a new dependency
is encountered, a queue of versions of that dependency is pushed onto the end of
the list. A queue is removed from the list once it's empty, indicating that none
of the versions provided a solution."

Also, it's worth mentioning that only the last queue will have ids removed from
it, and how new version constraints on existing packages are handled.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:66: /// will be the currently selected
version if that package. Subsequent items
"if" -> "of"

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:68: /// selected version.
Make it clear that every id in "versions" is expected to refer to the same
package. Possibly even validate that in code.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:75: /// Returns the id for the
currently selected package [name] or `null` if no
"the id for the currently selected package" -> "the currently selected id for
the package"

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:76: /// concrete package has been
selected with that name yet.
"concrete package" -> "concrete version", "with that name" -> "for that package"

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:93: /// Processes the current possible
solution state. If successful, completes
"Processes" is vague here. You should use the same terminology you use for
Propagator (which shouldn't be "propagates").

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:118: /// are no more selections to
try.
The terminology "package selection" is confusing. Make it more explicit that
this chooses the next-oldest version of the most recent selected package, and
that if we're already using the oldest version, it selects the previous package.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:158: /// solution by adding that
package's set of versions to the solver and then
"that package's set of versions" is confusing, because it won't add all of the
versions for that package -- just the versions that fit the version constraint.
Right?

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:160: class Propagator {
I still think this belongs in its own file, and that "Propagator" isn't a great
name. What about "Validator"? "Traverser"?

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:163: /// The queue of packages left to
traverse. We do a breadth-first traversal
"packages" -> "package versions"

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:168: /// The packages we have already
traversed. Used to avoid traversing the same
"packages" -> "package versions"

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:255: // The selected package is good,
so enqueue it to traverse into it.
"package" -> "package version"

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:261: // We haven't selected a version.
Create a substate that tries all
"substate" doesn't really make sense here any more.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:276: /// exception if not.
Might be worth mentioning that this doesn't validate the consistency of the
version constraints.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:329: // constraint.
This comment is confusing, since the check for NoVersionException is no longer
in this method.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:341: /// it not valid, or returns the
selected package if successful.
"is not valid" -> "is not consistent with the selected package"

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:387: // Store a checkpoint in case we
fail, then try to keep solving using the
This is the only time you refer to an element of VersionSolver._selected as a
checkpoint, and it's confusing.

https://codereview.chromium.org/13095015/diff/36001/utils/pub/solver/version_...
File utils/pub/solver/version_solver.dart (right):

https://codereview.chromium.org/13095015/diff/36001/utils/pub/solver/version_...
utils/pub/solver/version_solver.dart:100: class SolveResult {
Document this.

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
File utils/tests/pub/version_solver_test.dart (right):

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:76: var allowBacktracking;
Declare this as a bool, since it doesn't have an initial value.

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:92: allowBacktracking = 'wtf';
wtf?

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:171: }, maxTries: 3, hasGreedySolution:
true);
This case will take about N iterations for the backtracking solver, where N is
the number of versions of foo that are allowed by myapp but not by bar -- or
would if "bar" came alphabetically after "foo". We should have tests that verify
behavior like that.

Also, what happens when there's another dependency from myapp that's traversed
between foo and bar? I think for M such dependencies, this will take N^M
iterations to solve.

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:273: }, maxTries: 5, hasGreedySolution:
true);
These numbers feel very opaque to me. Could you include a short explanation of
where the iterations are coming from?

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:366: unsolvable() {
Iteration counts seem very relevant for testing these against the backtracking
solver.

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:519: // of bar depends on a baz with
the same minor version. There is only one
"the same minor version" is inaccurate; foo depends on a version of baz with the
same major version.

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:557: if (maxTries > 1 &&
!hasGreedySolution) {
It would be more readable if you assigned hasGreedySolution to "maxTries > 1" by
default.

Bob Nystrom

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2.dart File utils/pub/version_solver2.dart (right): https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2.dart#newcode11 utils/pub/version_solver2.dart:11: /// piles of memory for both the futures and ...

7 years, 8 months ago (2013-04-08 22:12:59 UTC) #7

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
File utils/pub/version_solver2.dart (right):

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:11: /// piles of memory for both the futures and
the stack traces.
On 2013/04/03 00:28:42, nweiz wrote:
> On 2013/03/30 00:15:55, Bob Nystrom wrote:
> > On 2013/03/29 01:58:25, nweiz wrote:
> > > If you're iterating enough that this becomes a serious problem, you're
> > iterating
> > > too much.
> > 
> > The only case where I've seen it be a problem is the pathological test
that's
> > designed to force it to go through a bunch of states.
> > 
> > In normal package graphs the future chain would be as deep as the number of
> > package's in the dependency graph. That's still kind of nasty when you're
> trying
> > to debug, though.
> 
> If the issue is the aesthetics of the stack traces, we have the means to clean
> them up outside this code. If the issue is efficiency, there are better ways
> around it, as I'll demonstrate below. In neither case does it warrant ugly
code.
> 
> > They don't take up space on the stack. They take up memory on the heap for
the
> > captured stack traces (and the closure and other state the futures hold).
> 
> This is false. See issue 9583.
> 
> Also, Futures don't capture stack traces.
> 
> > I don't think it's a bug. I think it's a natural consequence of this looping
> > pattern:
> > 
> > Future process(Queue items) {
> >   if (items.isEmpty) return new Future.immediate('done');
> >   return doSomethingWith(items.removeFirst()).then((_) => process(items));
> > }
> > 
> > The old solver uses the same idiom and it does lead to ugly then chains.
> 
> It's definitely a bug. You shouldn't get a stack overflow unless your code
> actually has a call stack a few thousand frames deep. The notion of a "call
> stack" is fuzzier when doing async, but even in the most pathological case
your
> traversal would never go deeper than the number of packages (not package
> versions) in the dependency tree.
> 
> > See above. It's about the chained futures, not the actual stack.
> 
> See my workaround function in issue 9583.

Your workaround fixes the stack traces, which is good, but it doesn't actually
shorten the future chains. Take this program:

void main() {
  var future = new Future.immediate(null);
  for (var i = 0; i < N; i++) {
    future = resetStack(future).then((_) => null);
  }

  future.then((_) => print("done!"));
}

Now make _FutureImpl._setValue() print. You'll see N prints as it walks the very
long future chain to complete the value.

Using an explicit completer avoids that.

I personally don't find the code here any harder to reason about or read so I
think this is generally an improvement.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:47: /// only allow the very latest version for
each of these packages.
On 2013/04/03 00:28:42, nweiz wrote:
> On 2013/03/30 00:15:55, Bob Nystrom wrote:
> > On 2013/03/29 01:58:25, nweiz wrote:
> > > I don't know if you care, but this isn't how bundler behaves. It will
> > backtrack
> > > even an explicit update.
> > 
> > I do care. The previous solver will always use the absolute latest version
or
> > fail, so I didn't add support for backtracking here. If you'd like, that's
> > doable (and should be easy). But that will need more tests so I'd like to do
> > that in a separate patch if that's OK.
> 
> My preference would be to use the current behavior, not bundler's. I think
it's
> always sort of confusing when bundler selects an old version of a package.

Works for me.

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:521: void _writeDependencies(StringBuffer buffer,
List<Dependency> deps) {
On 2013/04/03 00:28:42, nweiz wrote:
> On 2013/03/30 00:15:55, Bob Nystrom wrote:
> > On 2013/03/29 01:58:25, nweiz wrote:
> > > There's no particular reason for this to be an instance method, is there?
> > 
> > Not really. It keeps it out of global scope but makes it accessible to the
> > subclasses. Would you rather it be top level?
> 
> Yes, I think so.

Done.

https://codereview.chromium.org/13095015/diff/4001/utils/tests/pub/version_so...
File utils/tests/pub/version_solver_test.dart (right):

https://codereview.chromium.org/13095015/diff/4001/utils/tests/pub/version_so...
utils/tests/pub/version_solver_test.dart:503: });
On 2013/03/29 01:58:25, nweiz wrote:
> It seems like a lot more tests are necessarily to fully exercise the new
solver.

Agreed. I've added some, but I'd like to add more once I have a clearer picture
of what kinds of tests trigger interesting behavior.

> You should at least test that every kind of solution error triggers
backtracking
> and that backtracking finds the "best" solution in various cases where such a
> thing might be ambiguous.

Good idea. Added a TODO.

> I would also like to see tests that measure the number
> of steps being taken, either by testing the solver logs against an expected
> string or by tracking some sort of counter.

Done. Any test that requires backtracking now specifies the maximum number of
solution attempts it can try. If it goes over, the test fails.

https://codereview.chromium.org/13095015/diff/4001/utils/tests/pub/version_so...
utils/tests/pub/version_solver_test.dart:503: });
On 2013/04/03 00:28:42, nweiz wrote:
> On 2013/03/29 01:58:25, nweiz wrote:
> > It seems like a lot more tests are necessarily to fully exercise the new
> solver.
> > You should at least test that every kind of solution error triggers
> backtracking
> > and that backtracking finds the "best" solution in various cases where such
a
> > thing might be ambiguous. I would also like to see tests that measure the
> number
> > of steps being taken, either by testing the solver logs against an expected
> > string or by tracking some sort of counter.
> 
> You don't necessarily need to add these in this CL, but if you don't add a
TODO
> about it.

Done.

https://codereview.chromium.org/13095015/diff/7001/utils/pub/version_solver.dart
File utils/pub/version_solver.dart (right):

https://codereview.chromium.org/13095015/diff/7001/utils/pub/version_solver.d...
utils/pub/version_solver.dart:33: if (solver == null) solver = 2;
On 2013/04/03 00:28:43, nweiz wrote:
> On 2013/03/30 00:15:55, Bob Nystrom wrote:
> > On 2013/03/29 01:58:25, nweiz wrote:
> > > Let's make the existing solver the default for now.
> > 
> > I'll do that if you'll let me submit this patch before implementing
> backjumping
> > and whatever other hoops you want me to jump through to convince you this
> won't
> > end the world. :)
> 
> I'm willing to LGTM without the backjumper, on the understanding that I'm not
> LGTMing the user-visible use of the backtracking solver.

OK, I'll default to the old solver for now. We'll need to switch to the new one
to land SDK constraint solving, though, so I'll work on backjumping and some
tests that use it in a patch soon.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
File utils/pub/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:33: /// solution is found, or there
are no other ones to try.
On 2013/04/03 00:28:43, nweiz wrote:
> > This selects package versions from a list of valid options.
> 
> This is confusing. The user doesn't pass in a list of valid options. There
isn't
> anything in the class that looks like a list of valid options. There's nothing
> in my knowledge of the algorithm that fits this description (that is, is a
> static list of possible versions that the solver chooses from).
> 
> > It continues trying solutions and advancing
> 
> You haven't defined "solution" yet. Also, what does "advancing" mean?
Advancing
> through what? How?
> 
> > until either a solution is found, or there are no other ones to try.
> 
> You're using "solution" to mean two different things in the same sentence.
First
> you say you're "trying solutions", implying that a solution is a
> potentially-valid set of package versions. Then you say "until a solution is
> found", implying that a solution is an actually-valid thing you're going to
> return to a user.

Rewrote.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:40: /// the solver must select a
version for it, sometimes when multiple are
On 2013/04/03 00:28:43, nweiz wrote:
> "multiple" -> "multiple versions"

Done.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:45: /// some named package. Each
[Queue] is the ordered list of versions to try
On 2013/04/03 00:28:43, nweiz wrote:
> I think you can merge the first two sentences. Something like "Each entry in
the
> list is an ordered [Queue] of versions to try for a single package."

Done.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:48: /// and popped when the queue is
empty.
On 2013/04/03 00:28:43, nweiz wrote:
> The last sentence is less clear than it could be. Maybe "When a new dependency
> is encountered, a queue of versions of that dependency is pushed onto the end
of
> the list. A queue is removed from the list once it's empty, indicating that
none
> of the versions provided a solution."
> 
> Also, it's worth mentioning that only the last queue will have ids removed
from
> it, and how new version constraints on existing packages are handled.

Done.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:66: /// will be the currently selected
version if that package. Subsequent items
On 2013/04/03 00:28:43, nweiz wrote:
> "if" -> "of"

Done.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:68: /// selected version.
On 2013/04/03 00:28:43, nweiz wrote:
> Make it clear that every id in "versions" is expected to refer to the same
> package. Possibly even validate that in code.

Reworded. I think validating the entire collection in code is probably overkill.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:75: /// Returns the id for the
currently selected package [name] or `null` if no
On 2013/04/03 00:28:43, nweiz wrote:
> "the id for the currently selected package" -> "the currently selected id for
> the package"

Done.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:76: /// concrete package has been
selected with that name yet.
On 2013/04/03 00:28:43, nweiz wrote:
> "concrete package" -> "concrete version", "with that name" -> "for that
package"

Done.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:93: /// Processes the current possible
solution state. If successful, completes
On 2013/04/03 00:28:43, nweiz wrote:
> "Processes" is vague here. You should use the same terminology you use for
> Propagator (which shouldn't be "propagates").

Done.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:118: /// are no more selections to
try.
On 2013/04/03 00:28:43, nweiz wrote:
> The terminology "package selection" is confusing. Make it more explicit that
> this chooses the next-oldest version of the most recent selected package, and
> that if we're already using the oldest version, it selects the previous
package.

Done.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:158: /// solution by adding that
package's set of versions to the solver and then
On 2013/04/03 00:28:43, nweiz wrote:
> "that package's set of versions" is confusing, because it won't add all of the
> versions for that package -- just the versions that fit the version
constraint.
> Right?

Right. Added "allowed".

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:160: class Propagator {
On 2013/04/03 00:28:43, nweiz wrote:
> I still think this belongs in its own file, and that "Propagator" isn't a
great
> name. What about "Validator"? "Traverser"?

Good idea. Changed to Traverser. This file is still pretty manageable (< 500
lines), and I kind of like it all in one place, so I'll leave it here. If it
gets much bigger, I'm down with splitting things up.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:163: /// The queue of packages left to
traverse. We do a breadth-first traversal
On 2013/04/03 00:28:43, nweiz wrote:
> "packages" -> "package versions"

Changed to "concrete packages". Adding "versions" is a bit confusing to me
because it isn't traversing different versions of the same package.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:168: /// The packages we have already
traversed. Used to avoid traversing the same
On 2013/04/03 00:28:43, nweiz wrote:
> "packages" -> "package versions"

"concrete packages".

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:255: // The selected package is good,
so enqueue it to traverse into it.
On 2013/04/03 00:28:43, nweiz wrote:
> "package" -> "package version"

Done.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:261: // We haven't selected a version.
Create a substate that tries all
On 2013/04/03 00:28:43, nweiz wrote:
> "substate" doesn't really make sense here any more.

Reworded.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:276: /// exception if not.
On 2013/04/03 00:28:43, nweiz wrote:
> Might be worth mentioning that this doesn't validate the consistency of the
> version constraints.

Done.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:329: // constraint.
On 2013/04/03 00:28:43, nweiz wrote:
> This comment is confusing, since the check for NoVersionException is no longer
> in this method.

Simplified.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:341: /// it not valid, or returns the
selected package if successful.
On 2013/04/03 00:28:43, nweiz wrote:
> "is not valid" -> "is not consistent with the selected package"

Done.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:387: // Store a checkpoint in case we
fail, then try to keep solving using the
On 2013/04/03 00:28:43, nweiz wrote:
> This is the only time you refer to an element of VersionSolver._selected as a
> checkpoint, and it's confusing. 

Reworded.

https://codereview.chromium.org/13095015/diff/36001/utils/pub/solver/version_...
File utils/pub/solver/version_solver.dart (right):

https://codereview.chromium.org/13095015/diff/36001/utils/pub/solver/version_...
utils/pub/solver/version_solver.dart:100: class SolveResult {
On 2013/04/03 00:28:43, nweiz wrote:
> Document this.

Done.

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
File utils/tests/pub/version_solver_test.dart (right):

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:76: var allowBacktracking;
On 2013/04/03 00:28:43, nweiz wrote:
> Declare this as a bool, since it doesn't have an initial value.

Done.

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:92: allowBacktracking = 'wtf';
On 2013/04/03 00:28:43, nweiz wrote:
> wtf?

Heh. Debug code. Removed. :)

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:171: }, maxTries: 3, hasGreedySolution:
true);
On 2013/04/03 00:28:43, nweiz wrote:
> This case will take about N iterations for the backtracking solver, where N is
> the number of versions of foo that are allowed by myapp but not by bar -- or
> would if "bar" came alphabetically after "foo". We should have tests that
verify
> behavior like that.
> 
> Also, what happens when there's another dependency from myapp that's traversed
> between foo and bar? I think for M such dependencies, this will take N^M
> iterations to solve.

That sounds about right though I think it gets more complicated based on the
details of the shape of the dependency graph and the version constraints. Also,
the order that dependencies are traversed will affect things.

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:273: }, maxTries: 5, hasGreedySolution:
true);
On 2013/04/03 00:28:43, nweiz wrote:
> These numbers feel very opaque to me. Could you include a short explanation of
> where the iterations are coming from?

Explaining where the iterations come from would basically just be restating what
the implementation does. I think that should be documented in the solver and not
here. The tests should be declarative: what the expected behavior is, and not a
description of the imperative steps it took to get there.

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:366: unsolvable() {
On 2013/04/03 00:28:43, nweiz wrote:
> Iteration counts seem very relevant for testing these against the backtracking
> solver.

Done.

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:519: // of bar depends on a baz with
the same minor version. There is only one
On 2013/04/03 00:28:43, nweiz wrote:
> "the same minor version" is inaccurate; foo depends on a version of baz with
the
> same major version.

Done.

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:557: if (maxTries > 1 &&
!hasGreedySolution) {
On 2013/04/03 00:28:43, nweiz wrote:
> It would be more readable if you assigned hasGreedySolution to "maxTries > 1"
by
> default.

Done.

nweiz

After looking over Bundler's sort criteria again, I think it's reasonable to integrate most of ...

7 years, 8 months ago (2013-04-10 22:56:34 UTC) #9

Bob Nystrom

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2.dart File utils/pub/version_solver2.dart (right): https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2.dart#newcode11 utils/pub/version_solver2.dart:11: /// piles of memory for both the futures and ...

7 years, 8 months ago (2013-04-11 00:55:10 UTC) #10

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
File utils/pub/version_solver2.dart (right):

https://codereview.chromium.org/13095015/diff/4001/utils/pub/version_solver2....
utils/pub/version_solver2.dart:11: /// piles of memory for both the futures and
the stack traces.
On 2013/04/10 22:56:34, nweiz wrote:
> On 2013/04/08 22:12:59, Bob Nystrom wrote:
> > Your workaround fixes the stack traces, which is good, but it doesn't
actually
> > shorten the future chains. Take this program:
> > 
> > void main() {
> >   var future = new Future.immediate(null);
> >   for (var i = 0; i < N; i++) {
> >     future = resetStack(future).then((_) => null);
> >   }
> > 
> >   future.then((_) => print("done!"));
> > }
> > 
> > Now make _FutureImpl._setValue() print. You'll see N prints as it walks the
> very
> > long future chain to complete the value.
> 
> Of course there are N calls to setValue.

Right. I'm not crazy about building up a linked list of Futures that's N levels
deep.

But, I converted it back to Futures, so done.

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
File utils/pub/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/13095015/diff/29001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:163: /// The queue of packages left to
traverse. We do a breadth-first traversal
On 2013/04/10 22:56:34, nweiz wrote:
> On 2013/04/08 22:12:59, Bob Nystrom wrote:
> > On 2013/04/03 00:28:43, nweiz wrote:
> > > "packages" -> "package versions"
> > 
> > Changed to "concrete packages". Adding "versions" is a bit confusing to me
> > because it isn't traversing different versions of the same package.
> 
> If you're going to use this term, you need to define it somewhere first.

Changed it back to just "packages". The PackageId type annotation should clarify
it here.

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
File utils/tests/pub/version_solver_test.dart (right):

https://codereview.chromium.org/13095015/diff/36001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:273: }, maxTries: 5, hasGreedySolution:
true);
On 2013/04/10 22:56:34, nweiz wrote:
> On 2013/04/08 22:13:00, Bob Nystrom wrote:
> > On 2013/04/03 00:28:43, nweiz wrote:
> > > These numbers feel very opaque to me. Could you include a short
explanation
> of
> > > where the iterations are coming from?
> > 
> > Explaining where the iterations come from would basically just be restating
> what
> > the implementation does. I think that should be documented in the solver and
> not
> > here. The tests should be declarative: what the expected behavior is, and
not
> a
> > description of the imperative steps it took to get there.
> 
> The generalized behavior of the solver is very complex and difficult to reason
> about. Explaining the behavior in a specific instance, even if you're just
> walking through the steps the solver takes, is useful.

It's useful, but I think that documentation belongs in the solver, not here. We
don't have any docs here that walk through the equally complex steps the old
solver takes, and if I change implementation details of the solver, I don't want
to have up update docs in the tests.

The implementation is the "how", tests should just be "what".

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
File utils/pub/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:11: /// It builds up a solution
incrementally by traversing the dependency graph
On 2013/04/10 22:56:34, nweiz wrote:
> "It" -> "the solver"

Done.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:18: /// If it reaches an error:
On 2013/04/10 22:56:34, nweiz wrote:
> "If it reaches an error because:"

Done.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:29: /// recent speculative version
choice is selected and try the next one. That
On 2013/04/10 22:56:34, nweiz wrote:
> Remove "is selected"

Done.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:30: /// becomes the new current
solution and it tries to solve it again. It will
On 2013/04/10 22:56:34, nweiz wrote:
> You're still using "solution" to mean both a complete and consistent set of
> versions and the possibly-incomplete or -inconsistent intermediate set of
> versions you build up while finding a complete solution. I suggest you refer
to
> the latter as "partial solutions" instead.

Changed to "potential".

> 
> "solve it again" -> "proceed from there"

Done.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:33: /// speculative choices have been
found.
On 2013/04/10 22:56:34, nweiz wrote:
> "found" -> "exhausted"

Done.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:53: /// The top-level solver. Keeps
track of the current solution, and the other
On 2013/04/10 22:56:34, nweiz wrote:
> "current solution" -> "current partial solution"

"potential" but done.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:55: /// advances to the next possible
solution in the case of a failure.
On 2013/04/10 22:56:34, nweiz wrote:
> "possible solution" -> "possible partial solution"

Done.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:73: /// It tries versions in
depth-first order, so only the last queue in the
On 2013/04/10 22:56:34, nweiz wrote:
> "It" -> "The solver"

Done.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:75: /// a package already selected,
and that constraint doesn't match the
On 2013/04/10 22:56:34, nweiz wrote:
> "a package already selected" -> "an already-selected package"

Done.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:81: int _attemptedSolutions = 0;
On 2013/04/10 22:56:34, nweiz wrote:
> I missed this last time, but "int" is redundant here.

Done.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:87: int get attemptedSolutions =>
_attemptedSolutions;
On 2013/04/10 22:56:34, nweiz wrote:
> Move this right above _attemptedSolutions.

Done.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:99: /// Adds [versions], which are the
list of all allowed versions of a given
On 2013/04/10 22:56:34, nweiz wrote:
> "are" -> "is"

Done.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:100: /// package to the set of
versions to consider for solutions. The first item
On 2013/04/10 22:56:34, nweiz wrote:
> "package" -> "package,"

Done.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:101: /// in the will be the currently
selected version of that package. Subsequent
On 2013/04/10 22:56:34, nweiz wrote:
> "in the" -> "in the list"

Done.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:128: /// Traverses the root package's
dependency graph using the current possible
On 2013/04/10 22:56:34, nweiz wrote:
> "possible solution" -> "partial solution"

Changed to "potential". "partial" implies it's known to not be complete, which
isn't the case.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/version_...
File utils/pub/solver/version_solver.dart (right):

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/version_...
utils/pub/solver/version_solver.dart:50: void writeDependencies(StringBuffer
buffer, List<Dependency> deps) {
On 2013/04/10 22:56:34, nweiz wrote:
> Shouldn't this be private?

Removed in latest patch.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/version_...
utils/pub/solver/version_solver.dart:125: /// [SolveFailure] will be thrown.
On 2013/04/10 22:56:34, nweiz wrote:
> This comment is out-of-date; a failing resolution also returns a SolveResult.

Done.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/version_...
utils/pub/solver/version_solver.dart:140: /// backtrack because it found an
invalid solution.
On 2013/04/10 22:56:34, nweiz wrote:
> Document what this means if no solution was found.

Done.

https://codereview.chromium.org/13095015/diff/47001/utils/tests/pub/version_s...
File utils/tests/pub/version_solver_test.dart (right):

https://codereview.chromium.org/13095015/diff/47001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:665: return true;
On 2013/04/10 22:56:34, nweiz wrote:
> I'm worried that early errors will clobber later ones. Is it possible to
display
> all the errors at once?

I ordered them in terms of most significant first so that that's less of an
issue. I haven't had any trouble debugging failing tests with this output, but I
can do more here if you think it's worth the effort.

https://codereview.chromium.org/13095015/diff/47001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:675: final Iterable<String> _expected;
On 2013/04/10 22:56:34, nweiz wrote:
> This seems to be used just as a list of packages. I'd either make that its
> explicit semantics or pass in more detailed error message strings to validate.

This is preserving the existing behavior of the old predicate matchers. I can do
something more sophisticated here if you think it's important.

https://codereview.chromium.org/13095015/diff/57001/utils/pub/solver/backtrac...
File utils/pub/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/13095015/diff/57001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:163: var dependers =
failure.dependencies.map((dep) => dep.depender).toSet();
On 2013/04/10 22:56:35, nweiz wrote:
> This is a somewhat different algorithm than the one Bundler uses. Bundler will
> always try to adjust the version of the package that introduced the failing
> version constraint. Why aren't we doing the same?

I didn't follow this. Can you walk me through the difference?

https://codereview.chromium.org/13095015/diff/57001/utils/pub/solver/version_...
File utils/pub/solver/version_solver.dart (right):

https://codereview.chromium.org/13095015/diff/57001/utils/pub/solver/version_...
utils/pub/solver/version_solver.dart:293: "Could not find a solution that met
all constraints.";
On 2013/04/10 22:56:35, nweiz wrote:
> Why is the default message the message for CouldNotSolveException? Why not
just
> make this abstract?

Done.

https://codereview.chromium.org/13095015/diff/57001/utils/pub/solver/version_...
utils/pub/solver/version_solver.dart:366: String get _message => "Incompatible
dependency descriptions on '$package'";
On 2013/04/10 22:56:35, nweiz wrote:
> I'm skeptical that users will understand what "description" means in this
> context.

Changed back to old message.

https://codereview.chromium.org/13095015/diff/57001/utils/tests/pub/version_s...
File utils/tests/pub/version_solver_test.dart (right):

https://codereview.chromium.org/13095015/diff/57001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:486: }, maxTries: 2);
On 2013/04/10 22:56:35, nweiz wrote:
> This would pass if you used bundler's sort heuristic without using backjumping
> at all, since d would be checked before b.

Sorting by number of versions will require us to download the version lists for
all dependencies of a package before we can start traversing into any of them.

I can do that, but it will add complexity to the solver. In the absense of
empirical data that it will help users, I prefer to keep it simple.

> If you make a dependency on "c
> 4.0.0-nonexistent", that might avoid the issue, depending on how b and c were
> sorted relative to one another. I think if you add another version of c that
> would ensure that it gets sorted after b.

Done, though that doesn't currently affect the sorting.

https://codereview.chromium.org/13095015/diff/57001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:513: }, maxTries: 100);
On 2013/04/10 22:56:35, nweiz wrote:
> woo

Yes, much better.

nweiz

A few more comments, but lgtm. https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtracking_solver.dart File utils/pub/solver/backtracking_solver.dart (right): https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtracking_solver.dart#newcode30 utils/pub/solver/backtracking_solver.dart:30: /// becomes the ...

7 years, 8 months ago (2013-04-11 22:12:04 UTC) #11

A few more comments, but lgtm.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
File utils/pub/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:30: /// becomes the new current
solution and it tries to solve it again. It will
On 2013/04/11 00:55:11, Bob Nystrom wrote:
> Changed to "potential".

"potential solution" does a good job of conveying that it may be inconsistent,
but doesn't convey that it may be incomplete. In fact, in this instance, it's
almost certainly incomplete, since the older package version you've selected
probably has dependencies that need to be satisfied.

https://codereview.chromium.org/13095015/diff/47001/utils/tests/pub/version_s...
File utils/tests/pub/version_solver_test.dart (right):

https://codereview.chromium.org/13095015/diff/47001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:665: return true;
On 2013/04/11 00:55:11, Bob Nystrom wrote:
> On 2013/04/10 22:56:34, nweiz wrote:
> > I'm worried that early errors will clobber later ones. Is it possible to
> display
> > all the errors at once?
> 
> I ordered them in terms of most significant first so that that's less of an
> issue. I haven't had any trouble debugging failing tests with this output, but
I
> can do more here if you think it's worth the effort.

I do. Unittest does this when displaying errors for collections, and it results
in a really frustrating lack of context (e.g. "expected [a, b] but had 4
elements" is not a good error message).

https://codereview.chromium.org/13095015/diff/47001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:675: final Iterable<String> _expected;
On 2013/04/11 00:55:11, Bob Nystrom wrote:
> On 2013/04/10 22:56:34, nweiz wrote:
> > This seems to be used just as a list of packages. I'd either make that its
> > explicit semantics or pass in more detailed error message strings to
validate.
> 
> This is preserving the existing behavior of the old predicate matchers. I can
do
> something more sophisticated here if you think it's important.

It's not especially important, just a neatness thing.

https://codereview.chromium.org/13095015/diff/57001/utils/pub/solver/backtrac...
File utils/pub/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/13095015/diff/57001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:163: var dependers =
failure.dependencies.map((dep) => dep.depender).toSet();
On 2013/04/11 00:55:11, Bob Nystrom wrote:
> On 2013/04/10 22:56:35, nweiz wrote:
> > This is a somewhat different algorithm than the one Bundler uses. Bundler
will
> > always try to adjust the version of the package that introduced the failing
> > version constraint. Why aren't we doing the same?
> 
> I didn't follow this. Can you walk me through the difference?

Here, when an error is encountered, you record a set of "relevant" Dependencies
-- usually all the Dependencies that put a version constraint on that package.
Then you backjump to the most recent package that is a depender of one of these
dependencies, or to the package itself that had a conflict, whichever comes
first.

Bundler doesn't jump back to the first package that has some relevance to the
error; it jumps back specifically to the package whose dependency caused the
conflict (that is, the dependency we had just added when the error occurred).

https://codereview.chromium.org/13095015/diff/57001/utils/tests/pub/version_s...
File utils/tests/pub/version_solver_test.dart (right):

https://codereview.chromium.org/13095015/diff/57001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:486: }, maxTries: 2);
On 2013/04/11 00:55:11, Bob Nystrom wrote:
> On 2013/04/10 22:56:35, nweiz wrote:
> > This would pass if you used bundler's sort heuristic without using
backjumping
> > at all, since d would be checked before b.
> 
> Sorting by number of versions will require us to download the version lists
for
> all dependencies of a package before we can start traversing into any of them.
> 
> I can do that, but it will add complexity to the solver. In the absense of
> empirical data that it will help users, I prefer to keep it simple.
> 
> > If you make a dependency on "c
> > 4.0.0-nonexistent", that might avoid the issue, depending on how b and c
were
> > sorted relative to one another. I think if you add another version of c that
> > would ensure that it gets sorted after b.
> 
> Done, though that doesn't currently affect the sorting.

For this test, I was pointing it out from a black-box perspective; with no
knowledge of the actual implementation, this test could pass either because of
backjumping or because of sort order. That's still the case, BTW, unless you
have "a" depend on "c" instead of "d".

In general, it's pretty clear that sorting by the number of available packages
will help avoid exponential cases. I don't think this requires empirical
evidence; it's not something that's dependent on any practical conditions other
than some packages having different numbers of available versions than others,
which is clearly going to be the case.

I don't think downloading version lists early is a problem. We're probably going
to download those version lists anyway at some point. We should be batching more
requests anyway, since bandwidth is cheap but requests are expensive.

https://codereview.chromium.org/13095015/diff/71001/utils/pub/solver/backtrac...
File utils/pub/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/13095015/diff/71001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:244: Future<List<PackageId>>
_traversePackage() {
What do you think of wrapping the whole method in Future.of? That lets you avoid
awkward Future.immediate calls and also behaves nicely if unexpected errors
occur in the body.

https://codereview.chromium.org/13095015/diff/71001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:284: Future<List<PackageId>>
_traverseRefs(String depender,
Shouldn't there be a call to [resetStack] somewhere around here?

Bob Nystrom

Revised the backjumper. It now takes into account transitive dependencies, which allows it to still ...

7 years, 8 months ago (2013-04-16 18:34:16 UTC) #12

Revised the backjumper. It now takes into account transitive dependencies, which
allows it to still backjump but makes sure it doesn't jump past a package that
is actually relevant to the error.

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
File utils/pub/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/13095015/diff/47001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:30: /// becomes the new current
solution and it tries to solve it again. It will
On 2013/04/11 22:12:04, nweiz wrote:
> On 2013/04/11 00:55:11, Bob Nystrom wrote:
> > Changed to "potential".
> 
> "potential solution" does a good job of conveying that it may be inconsistent,
> but doesn't convey that it may be incomplete. In fact, in this instance, it's
> almost certainly incomplete, since the older package version you've selected
> probably has dependencies that need to be satisfied.

Changed to "in-progress".

https://codereview.chromium.org/13095015/diff/47001/utils/tests/pub/version_s...
File utils/tests/pub/version_solver_test.dart (right):

https://codereview.chromium.org/13095015/diff/47001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:665: return true;
On 2013/04/11 22:12:04, nweiz wrote:
> On 2013/04/11 00:55:11, Bob Nystrom wrote:
> > On 2013/04/10 22:56:34, nweiz wrote:
> > > I'm worried that early errors will clobber later ones. Is it possible to
> > display
> > > all the errors at once?
> > 
> > I ordered them in terms of most significant first so that that's less of an
> > issue. I haven't had any trouble debugging failing tests with this output,
but
> I
> > can do more here if you think it's worth the effort.
> 
> I do. Unittest does this when displaying errors for collections, and it
results
> in a really frustrating lack of context (e.g. "expected [a, b] but had 4
> elements" is not a good error message).

Done.

https://codereview.chromium.org/13095015/diff/47001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:675: final Iterable<String> _expected;
On 2013/04/11 22:12:04, nweiz wrote:
> On 2013/04/11 00:55:11, Bob Nystrom wrote:
> > On 2013/04/10 22:56:34, nweiz wrote:
> > > This seems to be used just as a list of packages. I'd either make that its
> > > explicit semantics or pass in more detailed error message strings to
> validate.
> > 
> > This is preserving the existing behavior of the old predicate matchers. I
can
> do
> > something more sophisticated here if you think it's important.
> 
> It's not especially important, just a neatness thing.

Added a TODO.

https://codereview.chromium.org/13095015/diff/57001/utils/pub/solver/backtrac...
File utils/pub/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/13095015/diff/57001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:163: var dependers =
failure.dependencies.map((dep) => dep.depender).toSet();
On 2013/04/11 22:12:04, nweiz wrote:
> On 2013/04/11 00:55:11, Bob Nystrom wrote:
> > On 2013/04/10 22:56:35, nweiz wrote:
> > > This is a somewhat different algorithm than the one Bundler uses. Bundler
> will
> > > always try to adjust the version of the package that introduced the
failing
> > > version constraint. Why aren't we doing the same?
> > 
> > I didn't follow this. Can you walk me through the difference?
> 
> Here, when an error is encountered, you record a set of "relevant"
Dependencies
> -- usually all the Dependencies that put a version constraint on that package.
> Then you backjump to the most recent package that is a depender of one of
these
> dependencies, or to the package itself that had a conflict, whichever comes
> first.
> 
> Bundler doesn't jump back to the first package that has some relevance to the
> error; it jumps back specifically to the package whose dependency caused the
> conflict (that is, the dependency we had just added when the error occurred).

I could be wrong, but I believe this solver will do the same thing. It will
backtrack on a conflict as soon as it occurs, which means that the package it
first backjumps to should be the one that just caused that conflict.

If I'm understanding this wrong, though, I'm definitely up for later adding a
test that validates this and tweaking the solver to handle it better.

https://codereview.chromium.org/13095015/diff/57001/utils/tests/pub/version_s...
File utils/tests/pub/version_solver_test.dart (right):

https://codereview.chromium.org/13095015/diff/57001/utils/tests/pub/version_s...
utils/tests/pub/version_solver_test.dart:486: }, maxTries: 2);
On 2013/04/11 22:12:04, nweiz wrote:
> On 2013/04/11 00:55:11, Bob Nystrom wrote:
> > On 2013/04/10 22:56:35, nweiz wrote:
> > > This would pass if you used bundler's sort heuristic without using
> backjumping
> > > at all, since d would be checked before b.
> > 
> > Sorting by number of versions will require us to download the version lists
> for
> > all dependencies of a package before we can start traversing into any of
them.
> > 
> > I can do that, but it will add complexity to the solver. In the absense of
> > empirical data that it will help users, I prefer to keep it simple.
> > 
> > > If you make a dependency on "c
> > > 4.0.0-nonexistent", that might avoid the issue, depending on how b and c
> were
> > > sorted relative to one another. I think if you add another version of c
that
> > > would ensure that it gets sorted after b.
> > 
> > Done, though that doesn't currently affect the sorting.
> 
> For this test, I was pointing it out from a black-box perspective; with no
> knowledge of the actual implementation, this test could pass either because of
> backjumping or because of sort order. That's still the case, BTW, unless you
> have "a" depend on "c" instead of "d".

Added some more documentation and revised the test.

> In general, it's pretty clear that sorting by the number of available packages
> will help avoid exponential cases. I don't think this requires empirical
> evidence; it's not something that's dependent on any practical conditions
other
> than some packages having different numbers of available versions than others,
> which is clearly going to be the case.
> 
> I don't think downloading version lists early is a problem. We're probably
going
> to download those version lists anyway at some point. We should be batching
more
> requests anyway, since bandwidth is cheap but requests are expensive.

Agreed, done.

https://codereview.chromium.org/13095015/diff/71001/utils/pub/solver/backtrac...
File utils/pub/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/13095015/diff/71001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:244: Future<List<PackageId>>
_traversePackage() {
On 2013/04/11 22:12:05, nweiz wrote:
> What do you think of wrapping the whole method in Future.of? That lets you
avoid
> awkward Future.immediate calls and also behaves nicely if unexpected errors
> occur in the body.

If there were more .immediate() calls I would but as it is this is a pretty
deeply nested function and I'd hate to indent it more.

Any errors that occur in the body are programmatic ones, so I'm OK if they just
take down the VM. (We do the same thing for stuff like ArgumentError in async
methods.)

https://codereview.chromium.org/13095015/diff/71001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:284: Future<List<PackageId>>
_traverseRefs(String depender,
On 2013/04/11 22:12:05, nweiz wrote:
> Shouldn't there be a call to [resetStack] somewhere around here?

Will the Future.of() here accomplish the same thing?

Bob Nystrom

Committed patchset #10 manually as r21563 (presubmit successful).

7 years, 8 months ago (2013-04-16 18:34:53 UTC) #13

nweiz

https://codereview.chromium.org/13095015/diff/71001/utils/pub/solver/backtracking_solver.dart File utils/pub/solver/backtracking_solver.dart (right): https://codereview.chromium.org/13095015/diff/71001/utils/pub/solver/backtracking_solver.dart#newcode284 utils/pub/solver/backtracking_solver.dart:284: Future<List<PackageId>> _traverseRefs(String depender, On 2013/04/16 18:34:17, Bob Nystrom wrote: ...

7 years, 8 months ago (2013-04-16 23:20:38 UTC) #14

Bob Nystrom

Thanks! Revised here: https://codereview.chromium.org/14249006/ https://codereview.chromium.org/13095015/diff/71001/utils/pub/solver/backtracking_solver.dart File utils/pub/solver/backtracking_solver.dart (right): https://codereview.chromium.org/13095015/diff/71001/utils/pub/solver/backtracking_solver.dart#newcode284 utils/pub/solver/backtracking_solver.dart:284: Future<List<PackageId>> _traverseRefs(String depender, On 2013/04/16 ...

7 years, 8 months ago (2013-04-16 23:58:45 UTC) #15

Message was sent while issue was closed.

Thanks! Revised here: https://codereview.chromium.org/14249006/

https://codereview.chromium.org/13095015/diff/71001/utils/pub/solver/backtrac...
File utils/pub/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/13095015/diff/71001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:284: Future<List<PackageId>>
_traverseRefs(String depender,
On 2013/04/16 23:20:38, nweiz wrote:
> On 2013/04/16 18:34:17, Bob Nystrom wrote:
> > On 2013/04/11 22:12:05, nweiz wrote:
> > > Shouldn't there be a call to [resetStack] somewhere around here?
> > 
> > Will the Future.of() here accomplish the same thing?
> 
> No. Future.of (now Future.sync) is synchronous, so it doesn't reset the stack.
> 
> The 0-arg Future constructor will work, though.

Yes, it's using the latter now. I was using the old pre-M4 terminology here.

https://codereview.chromium.org/13095015/diff/83001/utils/pub/solver/backtrac...
File utils/pub/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/13095015/diff/83001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:158: break;
On 2013/04/16 23:20:38, nweiz wrote:
> I'm pretty sure jumping to the package itself is incorrect. Unless it
> transitively depends on the package that caused the error, changing its
version
> isn't going to change the fact that its version constraints (or source or
> description) are in conflict.

True, though I believe this case may be useful when SDK constraint checking is
in. In that case the package itself is in error.

https://codereview.chromium.org/13095015/diff/83001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:178: logSolve('${previous} is last
version, backtracking');
On 2013/04/16 23:20:38, nweiz wrote:
> $previous

Done.

https://codereview.chromium.org/13095015/diff/83001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:191: String
_getDependencyPath(PackageId depender, String dependent) {
On 2013/04/16 23:20:38, nweiz wrote:
> This is O(N) for the size of `selected`, which makes `_backtrack` O(N^2). You
> should be able to build up dependency paths incrementally as you select
packages
> to make this O(1).

Yes, I can do that, but making sure that cached mutable state is correctly
rolled back when backtracking occurs is a little complex.

The current solution is O(n^2) but n will never be larger than the largest
package graph. I think that's OK for now. Added a TODO.

https://codereview.chromium.org/13095015/diff/83001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:194: var currentPath =
'${depender.name}';
On 2013/04/16 23:20:38, nweiz wrote:
> "'${depender.name}'" => "depender.name"

Done.

> It's confusing that you have a local variable out here that you're modifying
in
> walkDeps. It would be clearer to pass a path string as an argument and return
> that string on success.

Done.

https://codereview.chromium.org/13095015/diff/83001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:240: }
On 2013/04/16 23:20:38, nweiz wrote:
> I think I'd rather see verbose-but-complete output when I'm running this with
> logging enabled.

Changed to just show the number of versions. The full version list can be long
enough to make the log hard to read.

https://codereview.chromium.org/13095015/diff/83001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:326: }).catchError((error) {
On 2013/04/16 23:20:38, nweiz wrote:
> Log this.

Done.

https://codereview.chromium.org/13095015/diff/83001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:369: return new Future(() {
On 2013/04/16 23:20:38, nweiz wrote:
> Add a comment explaining that this works around issue 9583.

That's actually not the main intent here. It's to catch the errors that
_validateDependency() and _validateSelected() may throw.

nweiz

https://codereview.chromium.org/13095015/diff/83001/utils/pub/solver/backtracking_solver.dart File utils/pub/solver/backtracking_solver.dart (right): https://codereview.chromium.org/13095015/diff/83001/utils/pub/solver/backtracking_solver.dart#newcode369 utils/pub/solver/backtracking_solver.dart:369: return new Future(() { On 2013/04/16 23:58:46, Bob Nystrom ...

7 years, 8 months ago (2013-04-17 00:51:46 UTC) #16

Bob Nystrom

7 years, 8 months ago (2013-04-17 17:07:01 UTC) #17

Message was sent while issue was closed.

I'll update this in the other code review.

https://codereview.chromium.org/13095015/diff/83001/utils/pub/solver/backtrac...
File utils/pub/solver/backtracking_solver.dart (right):

https://codereview.chromium.org/13095015/diff/83001/utils/pub/solver/backtrac...
utils/pub/solver/backtracking_solver.dart:369: return new Future(() {
On 2013/04/17 00:51:46, nweiz wrote:
> On 2013/04/16 23:58:46, Bob Nystrom wrote:
> > On 2013/04/16 23:20:38, nweiz wrote:
> > > Add a comment explaining that this works around issue 9583.
> > 
> > That's actually not the main intent here. It's to catch the errors that
> > _validateDependency() and _validateSelected() may throw.
> 
> The normal way to do that would be to use [Future.sync()]. It warrants
> explaining why you need to use the asynchronous [Future()] constructor instead
> here.

Done.

Issue 13095015: Use backtracking when solving dependency constraints. (Closed)

Description

Patch Set 1 #

Patch Set 2 : Clean up a bit. #

Patch Set 3 : Clean up some test code. #

Patch Set 4 : Allow both solvers to coexist. #

Patch Set 5 : Respond to review. #

Patch Set 6 : Track amount of backtracking used in solver tests. #

Patch Set 7 : Revised. #

Patch Set 8 : Backjumping. #

Patch Set 9 : Revised. #

Patch Set 10 : Revise, update to latest corelib, and make backtracker default. #

Messages