Use backtracking when solving dependency constraints.

utils/pub/version_solver2.dart

Index: utils/pub/version_solver2.dart
diff --git a/utils/pub/version_solver2.dart b/utils/pub/version_solver2.dart
new file mode 100644
index 0000000000000000000000000000000000000000..8e2b3c58654aa77952d4eedc6a266db3e387f867
--- /dev/null
+++ b/utils/pub/version_solver2.dart
@@ -0,0 +1,627 @@
+// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+/// Pub's constraint solver. It is a back-tracking depth-first solver.
+///
+/// Note that internally it uses explicit [Completer]s instead of chaining
+/// futures like most async code. This is to avoid accumulating very long
+/// chains of futures. Since this may iterate through many states, hanging an
+/// increasing long series of `.then()` calls off each other can end up eating
+/// piles of memory for both the futures and the stack traces.

[nweiz, 2013/03/29 01:58:25]

If you're iterating enough that this becomes a serious problem, you're iterating
too much.

That said, Futures shouldn't take up stack space proportional to the length of
the future chain. 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.

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.

[Bob Nystrom, 2013/03/30 00:15:55]

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.
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).
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.
See above. It's about the chained futures, not the actual stack.

[nweiz, 2013/04/03 00:28:42]

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.
This is false. See issue 9583.

Also, Futures don't capture stack traces.
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 my workaround function in issue 9583.

[Bob Nystrom, 2013/04/08 22:12:59]

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.

[nweiz, 2013/04/10 22:56:34]

Of course there are N calls to setValue. The value is still being passed along N
times. That doesn't mean the stack becomes N levels deep. You can N arbitrarily
high, and you won't get a stack overflow. Also, if you throw an error in the
`then` clause, catch it, and examine the stack trace, you'll notice it's only
about a dozen frames large, as opposed to about 3N without the use of
resetStack.
Ugh, really? It looks atrocious to me. You're effectively just going back to
manual callbacks, with the added downside of having to integrate awkwardly with
other methods returning futures.

[Bob Nystrom, 2013/04/11 00:55:10]

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.

+library version_solver2;
+
+import 'dart:async';
+import 'dart:collection' show Queue;
+import 'dart:json' as json;
+import 'dart:math';
+import 'lock_file.dart';
+import 'log.dart' as log;
+import 'package.dart';
+import 'pubspec.dart';
+import 'source.dart';
+import 'source_registry.dart';
+import 'utils.dart';
+import 'version.dart';
+
+/// Attempts to select the best concrete versions for all of the transitive
+/// dependencies of [root] taking into account all of the [VersionConstraint]s
+/// that those dependencies place on each other and the requirements imposed by
+/// [lockFile]. If successful, completes to a [Map] that maps package names to

[nweiz, 2013/03/29 01:58:25]

The type annotation says it completes to a List, not a Map.

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+/// the selected version for that package. If it fails, the future will complete
+/// with a [NoVersionException], [DisjointConstraintException], or
+/// [CouldNotSolveException].
+Future<List<PackageId>> resolveVersions(SourceRegistry sources, Package root,
+    LockFile lockFile) {
+  log.message('Resolving dependencies...');
+  return new VersionSolver(sources, root, lockFile).solve();
+}
+
+class VersionSolver {

[nweiz, 2013/03/29 01:58:25]

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.

[Bob Nystrom, 2013/03/30 00:15:55]

Added lots more docs.

[nweiz, 2013/04/03 00:28:42]

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

+  final SourceRegistry _sources;
+  final Package _root;
+  final LockFile _lockFile;
+  final PubspecCache _cache;
+
+  /// The set of packages that are being explicitly updated. The solver will
+  /// only allow the very latest version for each of these packages.

[nweiz, 2013/03/29 01:58:25]

I don't know if you care, but this isn't how bundler behaves. It will backtrack
even an explicit update.

[Bob Nystrom, 2013/03/30 00:15:55]

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.

[nweiz, 2013/04/03 00:28:42]

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.

[Bob Nystrom, 2013/04/08 22:12:59]

Works for me.

+  final _forceLatest = new Set<String>();
+
+  /// The current state being explored. Its parent links enable us to walk
+  /// back up the tree to other earlier states.
+  SolveState _state;
+
+  VersionSolver(SourceRegistry sources, this._root, this._lockFile)
+      : _sources = sources,
+        _cache = new PubspecCache(sources);
+
+  void useLatestVersion(String package) {
+    _forceLatest.add(package);
+    _lockFile.packages.remove(package);
+  }
+
+  Future<List<PackageId>> solve() {
+    var completer = new Completer<List<PackageId>>();
+    _processState(completer);
+    return completer.future;
+  }
+
+  /// Creates a new node in the solution space that tries [versions] for
+  /// package [name]. Returns the new node.
+  SolveState push(String name, List<Version> versions) {
+    _state = new SolveState(_state, name, versions);
+    _state.trace();
+    return _state;
+  }
+
+  /// Loads the pubspec for the package identified by [id].
+  Future<Pubspec> getPubspec(PackageId id) {
+    // The root package doesn't have a source, so special case it.
+    if (id.isRoot) return new Future.immediate(_root.pubspec);
+
+    return _cache.getPubspec(id);
+  }
+
+  /// Gets the list of versions for [package].
+  Future<List<PackageId>> getVersions(String package, Source source,
+      description) {
+    return _cache.getVersions(package, source, description);
+  }
+
+  /// Gets the version of [package] currently locked in the lock file. Returns
+  /// `null` if it isn't in the lockfile (or has been unlocked).
+  PackageId getLocked(String package) => _lockFile.packages[package];
+
+  /// Processes the current possible solution state. If successful, completes
+  /// [completer] with the solution. If not, tries the next state (and so on).
+  /// If there are no more states, completes to the last error that occurred.
+  void _processState(Completer<List<PackageId>> completer) {
+    var state = _state;
+
+    var propagator = new Propagator(this, state);

[nweiz, 2013/03/29 01:58:25]

There's no need for a variable here.

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+    propagator.propagate().then((result) {
+      completer.complete(result);
+    }).catchError((error) {
+      if (error.error is! SolverFailure) {
+        completer.completeError(error);
+        return;
+      }
+
+      // Try the next state, if there is one.
+      if (state != _state || _advanceState()) {
+        _processState(completer);
+      } else {
+        // All out of solutions, so fail.
+        completer.completeError(error);
+      }
+    });
+  }
+
+  /// Advances to the next node in the possible solution tree.
+  bool _advanceState() {
+    while (_state != null) {
+      if (_state.advance()) return true;
+
+      // The current state is done, so pop it and try the parent.
+      _state = _state._parent;
+    }
+
+    return false;
+  }
+}
+
+/// Given a [SolveState] that selects a set of package versions, this tries to
+/// traverse the dependency graph and see if a complete set of valid versions
+/// has been selected.

[nweiz, 2013/03/29 01:58:25]

This description implies that this just examines the SolveState, when in fact it
also modifies the VersionSolver by enqueuing new SolveStates.

[Bob Nystrom, 2013/03/30 00:15:55]

Added better docs.

+class Propagator {

[nweiz, 2013/03/29 01:58:25]

Move this and most of the other classes below into their own files. The errors
can all go in the same file.

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

[Bob Nystrom, 2013/03/30 00:15:55]

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.

+  final VersionSolver _solver;
+
+  /// The queue of packages left to traverse. We do a bread-first traversal

[nweiz, 2013/03/29 01:58:25]

"bread" -> "breadth"

[Bob Nystrom, 2013/03/30 00:15:55]

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

Fixed.

+  /// using an explicit queue just to avoid the code complexity of a recursive
+  /// asynchronous traversal.
+  final _packages = new Queue<PackageId>();
+
+  /// The packages we have already traversed. Used to avoid traversing the same
+  /// package multiple times, and to build the complete solution results.
+  final _visited = new Set<PackageId>();
+
+  /// The known dependencies visited so far.

[nweiz, 2013/03/29 01:58:25]

This isn't a very descriptive comment. What are the keys? What does it mean that
there are multiple dependencies for each key?

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+  final _dependencies = <String, List<Dependency>>{};
+
+  /// The solution being tested.
+  SolveState _state;
+
+  Propagator(this._solver, this._state);
+
+  Future<List<PackageId>> propagate() {
+    // Start at the root.
+    _packages.add(new PackageId.root(_solver._root));
+
+    var completer = new Completer<List<PackageId>>();
+    _processPackage(completer);
+    return completer.future;
+  }
+
+  void trace([String message]) {

[nweiz, 2013/03/29 01:58:25]

"trace" is a confusing name. Maybe "printLog" or "printTrace"? Even just "log"
would be better.

[Bob Nystrom, 2013/03/30 00:15:55]

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

+    if (_state == null) {
+      // Don't waste time building the string if it will be ignored.
+      if (!log.isEnabled(log.Level.SOLVER)) return;

[nweiz, 2013/03/29 01:58:25]

This is unnecessary optimization, and we don't do it anywhere else we build log
messages.

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+
+      // No message means just describe the current state.
+      if (message == null) {
+        message = "* start at root";
+      } else {
+        // Otherwise, indent it under the current state.
+        message = "| $message";
+      }
+
+      log.solver("| $message");
+    } else {
+      _state.trace(message);
+    }
+  }
+
+  /// Traverses the next package in the queue. Completes [completer] with a
+  /// list of package IDs if the traversal completely successfully and found a

[nweiz, 2013/03/29 01:58:25]

"completely" -> "completed"

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+  /// solution. Completes to an error if the traversal failed. Otherwise,
+  /// recurses to the next package in the queue, etc.
+  void _processPackage(Completer<List<PackageId>> completer) {
+    if (_packages.isEmpty) {
+      // We traversed the whole graph. If we got here, we successfully found
+      // a solution.
+      completer.complete(_visited.toList());
+      return;
+    }
+
+    var id = _packages.removeFirst();
+
+    // Don't visit the same package twice.
+    if (_visited.contains(id)) {
+      _processPackage(completer);
+      return;
+    }
+    _visited.add(id);
+
+    _solver.getPubspec(id).then((pubspec) {
+      var refs = pubspec.dependencies.toList();
+
+      // Include dev dependencies of the root package.
+      if (id.isRoot) {
+        refs.addAll(pubspec.devDependencies);
+      }
+
+      // TODO(rnystrom): Sort in some best-first order to minimize backtracking.
+      // Bundler's model is:
+      // Easiest to resolve is defined by:
+      //   1) Is this gem already activated?
+      //   2) Do the version requirements include prereleased gems?
+      //   3) Sort by number of gems available in the source.
+      // Can probably do something similar, but we should profile against
+      // actual package graphs first.
+      refs.sort((a, b) => a.name.compareTo(b.name));
+
+      _traverseRefs(completer, id.name, new Queue<PackageRef>.from(refs));
+    }).catchError((error){
+      completer.completeError(error);
+    });
+  }
+
+  /// Traverses the references that [depender] depends on, stored in [refs].
+  /// Desctructively modifies [refs]. Completes [completer] to a list of
+  /// packages if the traversal is complete. Completes it to an error if a
+  /// failure occurred. Otherwise, recurses.
+  void _traverseRefs(Completer<List<PackageId>> completer,

[nweiz, 2013/03/29 01:58:25]

This function is gigantic. Split it up?

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+                     String depender, Queue<PackageRef> refs) {
+    // Move onto the next package if we've traversed all of these references.
+    if (refs.isEmpty) {
+      _processPackage(completer);
+      return;
+    }
+
+    var ref = refs.removeFirst();
+
+    // Note the dependency.
+    var dependencies = _dependencies.putIfAbsent(ref.name,
+        () => <Dependency>[]);
+    dependencies.add(new Dependency(depender, ref));
+
+    // Make sure the dependencies agree on source and description.
+    var required = _getRequired(ref.name);
+    if (required != null) {
+      // Make sure all of the existing sources match the new reference.
+      if (required.ref.source.name != ref.source.name) {
+        trace('source mismatch on ${ref.name}: ${required.ref.source} '
+              '!= ${ref.source}');
+        completer.completeError(new SourceMismatchException(ref.name,
+            required.depender, required.ref.source, depender, ref.source));

[nweiz, 2013/03/29 01:58:25]

Never call completeError without a stack trace. The same goes for the rest of
the errors in this method.

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+        return;
+      }
+
+      // Make sure all of the existing descriptions match the new reference.
+      if (!ref.descriptionEquals(required.ref)) {
+        trace('description mismatch on ${ref.name}: '
+              '${required.ref.description} != ${ref.description}');
+        completer.completeError(new DescriptionMismatchException(ref.name,
+            required.depender, required.ref.description,
+            depender, ref.description));
+        return;
+      }
+    }
+
+    // Determine the overall version constraint.
+    var constraint = dependencies
+        .map((dep) => dep.ref.constraint)
+        .reduce(VersionConstraint.any, (a, b) => a.intersect(b));
+
+    // See if it's possible for a package to match that constraint. We
+    // check this first so that this error is preferred over "no versions"
+    // which can be thrown if the current selection does not match the
+    // constraint.
+    if (constraint.isEmpty) {
+      trace('disjoint constraints on ${ref.name}');
+      completer.completeError(
+          new DisjointConstraintException(ref.name, dependencies));
+      return;
+    }
+
+    var selected = _getSelected(ref.name);
+    if (selected != null) {
+      // Make sure it meets the constraint.
+      if (!ref.constraint.allows(selected.version)) {
+        trace('selection $selected does not match $constraint');
+        completer.completeError(
+            new NoVersionException(ref.name, constraint, dependencies));
+        return;
+      }
+
+      // Traverse into it.

[nweiz, 2013/03/29 01:58:25]

You're not actually traversing into the new version here, you're just enqueueing
it to get traversed later.

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+      _packages.add(selected);
+      _traverseRefs(completer, depender, refs);
+      return;
+    }
+
+    // We haven't selected a version. Create a substate that tries all
+    // versions that match the constraints we currently have for this
+    // package.
+    _solver.getVersions(ref.name, ref.source, ref.description).then((versions) {
+      var allowed = versions.where(
+          (id) => constraint.allows(id.version)).toList();
+
+      // See if it's in the lockfile. If so, try that version first. If the
+      // locked version doesn't match our constraint, just ignore it.
+      var locked = _getLocked(ref.name, constraint);
+      if (locked != null) {
+        allowed.removeWhere((ref) => ref.version == locked.version);
+        allowed.insert(0, locked);
+      }
+
+      if (allowed.isEmpty) {
+        trace('no versions for ${ref.name} match $constraint');
+        completer.completeError(new NoVersionException(ref.name, constraint,
+            dependencies));
+        return;
+      }
+
+      // If we're doing an upgrade on this package, only allow the latest
+      // version.
+      if (_solver._forceLatest.contains(ref.name)) allowed = [allowed.first];
+
+      // Try to continue solving with the first selected package.

[nweiz, 2013/03/29 01:58:25]

This doesn't just try the first selected package. This tries every package in
`allowed`.

[Bob Nystrom, 2013/03/30 00:15:55]

This Propagator will only try the first one. Reworded.

+      _state = _solver.push(ref.name, allowed);
+      selected = _getSelected(ref.name);
+      assert(selected != null);
+
+      _packages.add(selected);
+      _traverseRefs(completer, depender, refs);
+    }).catchError((error) {
+      print(error);

[nweiz, 2013/03/29 01:58:25]

Left over from debugging?

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+      completer.completeError(error);
+    });
+  }
+
+  /// Gets the currently selected package named [package] or `null` if no

[nweiz, 2013/03/29 01:58:25]

"Gets" -> "Returns", "package named" -> "id for the package named", "[package]"
-> "[name]"

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+  /// concrete package has been selected with that name yet.
+  PackageId _getSelected(String name) {
+    // Always prefer the root package.
+    if (_solver._root.name == name) return new PackageId.root(_solver._root);
+
+    // Nothing is selected if we're in the starting state.
+    if (_state == null) return null;
+
+    return _state.getSelected(name);
+  }
+
+  /// Gets a "required" reference to the package [name]. This is the first
+  /// non-root dependency on that package. All dependencies on a package must

[nweiz, 2013/03/29 01:58:25]

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,
and this is guaranteed to return null. Is that not the case?

[Bob Nystrom, 2013/03/30 00:15:55]

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.)

+  /// agree on source and description, except for references to the root
+  /// package. This will return a reference to that "canonical" source and
+  /// description, or `null` if there is no required reference yet.
+  Dependency _getRequired(String name) {
+    var dependencies = _dependencies[name];
+    assert(dependencies != null);
+
+    return dependencies
+        .firstWhere((dep) => !dep.ref.isRoot, orElse: () => null);
+  }
+
+  /// Gets the package [name] that's currently contained in the lockfile if it
+  /// meets [constraint] and has the same source and description as other
+  /// references to that package. Returns `null` otherwise.
+  PackageId _getLocked(String name, VersionConstraint constraint) {

[nweiz, 2013/03/29 01:58:25]

It's confusing that this has the same name as [VersionSolver.getLocked] but
slightly different semantics. Change it to something like "_maybeGetLocked" or
"_getLockedIfCompatible"?

[Bob Nystrom, 2013/03/30 00:15:55]

Changed to _getValidLocked().

+    var package = _solver.getLocked(name);
+    if (package == null) return null;
+
+    if (!constraint.allows(package.version)) return null;
+
+    var dependencies = _dependencies[name];

[nweiz, 2013/03/29 01:58:25]

Unused variable.

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+    assert(dependencies != null);
+
+    var required = _getRequired(name);
+    if (required != null) {
+      if (package.source.name != required.ref.source.name) return null;
+      if (!package.descriptionEquals(required.ref)) return null;
+    }
+
+    return package;
+  }
+}
+
+/// One node in the possible solution tree that is being traversed. Each node
+/// reflects one of a set of speculative choices that may turn out to be wrong.

[nweiz, 2013/03/29 01:58:25]

"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.

[Bob Nystrom, 2013/03/30 00:15:55]

Removed this class entirely.

+class SolveState {
+  final SolveState _parent;
+
+  /// The name of the package this state selects.
+  final String _package;
+
+  /// The list of versions that can possibly be selected.
+  final List<PackageId> _possible;
+
+  /// The currently selected version in [_possible].
+  int _current = 0;
+
+  SolveState(this._parent, this._package, this._possible);
+
+  void trace([Object message]) {
+    // Don't waste time building the string if it will be ignored.
+    if (!log.isEnabled(log.Level.SOLVER)) return;

[nweiz, 2013/03/29 01:58:25]

Unnecessary optimization.

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+
+    // No message means just describe the current state.
+    if (message == null) {
+      message = "* select ${_possible[_current]} "
+                "($_current/${_possible.length})";
+    } else {
+      // Otherwise, indent it under the current state.
+      message = "| $message";
+    }
+
+    var buffer = new StringBuffer();
+
+    // Indent for the parent states.
+    var state = _parent;
+    while (state != null) {
+      buffer.write('| ');
+      state = state._parent;
+    }
+
+    buffer.write(message);
+    log.solver(buffer);
+  }
+
+  /// Tries to move to the next version in the list. Returns `false` if there
+  /// are no more versions.
+  bool advance() {
+    _current++;
+    if (_current < _possible.length) {
+      trace();
+      return true;
+    } else {
+      return false;
+    }
+  }
+
+  /// Gets the selected version of [package]. If no version has been selected
+  /// yet, returns `null`.
+  PackageId getSelected(String package) {
+    if (_package == package) return _possible[_current];
+    if (_parent == null) return null;
+    return _parent.getSelected(package);
+  }
+}
+
+/// A reference from a depending package to a package that it depends on.
+class Dependency {
+  /// The name of the package that has this dependency.
+  final String depender;
+
+  /// The referenced dependent package.
+  final PackageRef ref;
+
+  Dependency(this.depender, this.ref);
+}
+
+/// Maintains a cache of previously-requested data: pubspecs and version lists.
+/// Used to avoid requesting the same pubspec from the server repeatedly.
+class PubspecCache {
+  final SourceRegistry _sources;
+  final _versions = new Map<PackageId, List<Version>>();

[nweiz, 2013/03/29 01:58:25]

The type of the map is wrong. The value type should be List<PackageId>.

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+  final _pubspecs = new Map<PackageId, Pubspec>();
+
+  PubspecCache(this._sources);
+
+  /// Caches [pubspec] as the [Pubspec] for the package identified by [id].
+  void cache(PackageId id, Pubspec pubspec) {

[nweiz, 2013/03/29 01:58:25]

This is never called.

[Bob Nystrom, 2013/03/30 00:15:55]

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

+    _pubspecs[id] = pubspec;
+  }
+
+  /// Loads the pubspec for the package identified by [id].
+  Future<Pubspec> getPubspec(PackageId id) {
+    // Complete immediately if it's already cached.
+    if (_pubspecs.containsKey(id)) {
+      return new Future<Pubspec>.immediate(_pubspecs[id]);
+    }
+
+    return id.describe().then((pubspec) {
+      log.solver('requested ${id} pubspec');
+
+      // Cache it.
+      _pubspecs[id] = pubspec;
+      return pubspec;
+    });
+  }
+
+  /// Gets the list of versions for [package] in descending order.
+  Future<List<PackageId>> getVersions(String package, Source source, description) {

[nweiz, 2013/03/29 01:58:25]

long line

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+    // Create a fake ID to use as a key.
+    var id = new PackageId(package, source, Version.none, description);

[nweiz, 2013/03/29 01:58:25]

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).

[Bob Nystrom, 2013/03/30 00:15:55]

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

+
+    // See if we have it cached.
+    var versions = _versions[id];
+    if (versions != null) return new Future.immediate(versions);
+
+    return source.getVersions(package, description).then((versions) {
+      var ids = versions
+          .map((version) => new PackageId(package, source, version, description))

[nweiz, 2013/03/29 01:58:25]

long line

[Bob Nystrom, 2013/03/30 00:15:55]

Done.

+          .toList();
+
+      // Sort by descending version so we try newer versions first.
+      ids.sort((a, b) => b.version.compareTo(a.version));
+
+      log.solver('requested $package versions: ${ids.join(", ")}');
+      _versions[id] = ids;
+      return ids;
+    });
+  }
+}
+
+
+/// Base class for all failures that can occur while trying to resolve versions.
+class SolverFailure implements Exception {
+  /// Writes [deps] to [buffer] as a bullet list.
+  void _writeDependencies(StringBuffer buffer, List<Dependency> deps) {

[nweiz, 2013/03/29 01:58:25]

There's no particular reason for this to be an instance method, is there?

[Bob Nystrom, 2013/03/30 00:15:55]

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

[nweiz, 2013/04/03 00:28:42]

Yes, I think so.

[Bob Nystrom, 2013/04/08 22:12:59]

Done.

+    var map = {};
+    for (var dep in deps) {
+      map[dep.depender] = dep.ref;
+    }
+
+    var names = map.keys.toList();
+    names.sort();
+
+    for (var name in names) {
+      buffer.writeln("- '$name' depends on version ${map[name].constraint}");
+    }
+  }
+}
+
+/// Exception thrown when the [VersionConstraint] used to match a package is
+/// valid (i.e. non-empty), but there are no available versions of the package
+/// that fit that constraint.
+class NoVersionException extends SolverFailure {
+  final String package;
+  final VersionConstraint constraint;
+  final List<Dependency> _dependencies;
+
+  NoVersionException(this.package, this.constraint, this._dependencies);
+
+  String toString() {
+    var buffer = new StringBuffer();
+    buffer.write("Package '$package' has no versions that match $constraint "
+        "derived from:\n");
+    _writeDependencies(buffer, _dependencies);
+    return buffer.toString();
+  }
+}
+
+/*
+// TODO(rnystrom): Report the list of depending packages and their constraints.
+/// Exception thrown when the most recent version of [package] must be selected,
+/// but doesn't match the [VersionConstraint] imposed on the package.
+class CouldNotUpdateException implements Exception {

[nweiz, 2013/03/29 01:58:25]

Why is this commented out? Isn't this a state the solver can get into?

[Bob Nystrom, 2013/03/30 00:15:55]

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.

+  final String package;
+  final VersionConstraint constraint;
+  final Version best;
+
+  CouldNotUpdateException(this.package, this.constraint, this.best);
+
+  String toString() =>
+      "The latest version of '$package', $best, does not match $constraint.";
+}
+*/
+
+/// Exception thrown when the [VersionConstraint] used to match a package is
+/// the empty set: in other words, multiple packages depend on it and have
+/// conflicting constraints that have no overlap.
+class DisjointConstraintException extends SolverFailure {
+  final String package;
+  final List<Dependency> _dependencies;
+
+  DisjointConstraintException(this.package, this._dependencies);
+
+  String toString() {
+    var buffer = new StringBuffer();
+    buffer.write("Incompatible version constraints on '$package':\n");
+    _writeDependencies(buffer, _dependencies);
+    return buffer.toString();
+  }
+}
+
+/// Exception thrown when two packages with the same name but different sources
+/// are depended upon.
+class SourceMismatchException extends SolverFailure {
+  final String package;
+  final String depender1;
+  final Source source1;
+  final String depender2;
+  final Source source2;
+
+  SourceMismatchException(this.package, this.depender1, this.source1,
+      this.depender2, this.source2);
+
+  String toString() {
+    return "Incompatible dependencies on '$package':\n"
+        "- '$depender1' depends on it from source '$source1'\n"
+        "- '$depender2' depends on it from source '$source2'";
+  }
+}
+
+/// Exception thrown when two packages with the same name and source but
+/// different descriptions are depended upon.
+class DescriptionMismatchException extends SolverFailure {
+  final String package;
+  final String depender1;
+  final description1;
+  final String depender2;
+  final description2;
+
+  DescriptionMismatchException(this.package, this.depender1, this.description1,
+      this.depender2, this.description2);
+
+  String toString() {
+    // TODO(nweiz): Dump descriptions to YAML when that's supported.
+    return "Incompatible dependencies on '$package':\n"
+        "- '$depender1' depends on it with description "
+        "${json.stringify(description1)}\n"
+        "- '$depender2' depends on it with description "
+        "${json.stringify(description2)}";
+  }
+}