Use backtracking when solving dependency constraints.

utils/pub/solver/backtracking_solver.dart

Index: utils/pub/solver/backtracking_solver.dart
diff --git a/utils/pub/solver/backtracking_solver.dart b/utils/pub/solver/backtracking_solver.dart
new file mode 100644
index 0000000000000000000000000000000000000000..6e9a027d0785f70cab9b0d3b06b81c58c46300ac
--- /dev/null
+++ b/utils/pub/solver/backtracking_solver.dart
@@ -0,0 +1,432 @@
+// 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.
+
+/// A back-tracking depth-first solver. It is broken into two main components:
+///
+///  *  A [BacktrackingVersionSolver] iterates through the possible solutions
+///     until it finds a valid one, or runs out of ones to try.
+///
+///  *  A [Propagator] takes a given potential solution and walks the
+///     dependency graph to determine if the solution is complete and valid.
+///
+/// Note that internally this 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.
+library version_solver2;
+
+import 'dart:async';
+import 'dart:collection' show Queue;
+
+import '../lock_file.dart';
+import '../log.dart' as log;
+import '../package.dart';
+import '../source.dart';
+import '../source_registry.dart';
+import '../version.dart';
+import 'version_solver.dart';
+
+/// The top-level solver. This selects package versions from a list of valid
+/// options. It continues trying solutions and advancing until either a
+/// solution is found, or there are no other ones to try.

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

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).
You haven't defined "solution" yet. Also, what does "advancing" mean? Advancing
through what? How?
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.

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

Rewrote.

+class BacktrackingVersionSolver extends VersionSolver {
+  /// The set of packages that are being explicitly updated. The solver will
+  /// only allow the very latest version for each of these packages.
+  final _forceLatest = new Set<String>();
+
+  /// Every time a package is encountered when traversing the dependency graph,
+  /// the solver must select a version for it, sometimes when multiple are

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

"multiple" -> "multiple versions"

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

Done.

+  /// valid. This keeps track of which versions have been selected so far and
+  /// which remain to be tried.
+  ///
+  /// Each entry in the list represents all of the possible versions to try for
+  /// some named package. Each [Queue] is the ordered list of versions to try

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

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

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

Done.

+  /// for that package. The first item in the queue is the currently selected
+  /// version for that package. Packages are pushed onto the end of the list
+  /// and popped when the queue is empty.

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

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.

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

Done.

+  final _selected = <Queue<PackageId>>[];
+
+  BacktrackingVersionSolver(SourceRegistry sources, Package root,
+      LockFile lockFile, List<String> useLatest)
+      : super(sources, root, lockFile, useLatest);
+
+  void forceLatestVersion(String package) {
+    _forceLatest.add(package);
+  }
+
+  Future<List<PackageId>> runSolver() {
+    var completer = new Completer<List<PackageId>>();
+    _processState(completer);
+    return completer.future;
+  }
+
+  /// Adds [versions] to the set of possible versions. The first item in it
+  /// will be the currently selected version if that package. Subsequent items

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

"if" -> "of"

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

Done.

+  /// will be tried if it the current selection fails. Returns the first
+  /// selected version.

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

Make it clear that every id in "versions" is expected to refer to the same
package. Possibly even validate that in code.

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

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

+  PackageId select(Iterable<PackageId> versions) {
+    _selected.add(new Queue<PackageId>.from(versions));
+    logSolve();
+    return versions.first;
+  }
+
+  /// Returns the id for the currently selected package [name] or `null` if no

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

"the id for the currently selected package" -> "the currently selected id for
the package"

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

Done.

+  /// concrete package has been selected with that name yet.

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

"concrete package" -> "concrete version", "with that name" -> "for that package"

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

Done.

+  PackageId getSelected(String name) {
+    // Always prefer the root package.
+    if (root.name == name) return new PackageId.root(root);
+
+    // Look through the current selections.
+    for (var i = _selected.length - 1; i >= 0; i--) {
+      if (_selected[i].first.name == name) return _selected[i].first;
+    }
+
+    return null;
+  }
+
+  /// 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

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

"Processes" is vague here. You should use the same terminology you use for
Propagator (which shouldn't be "propagates").

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

Done.

+  /// [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 oldLength = _selected.length;
+
+    new Propagator(this).propagate().then((result) {
+      completer.complete(result);
+    }).catchError((error) {
+      if (error.error is! SolverFailure) {
+        completer.completeError(error);
+        return;
+      }
+
+      // If a new package was added, try it, or try the next selection.
+      if (oldLength != _selected.length || _advanceState()) {
+        _processState(completer);
+      } else {
+        // All out of solutions, so fail.
+        completer.completeError(error);
+      }
+    });
+  }
+
+  /// Advances to the next possible package selection. Returns `false` if there
+  /// are no more selections to try.

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

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.

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

Done.

+  bool _advanceState() {
+    while (!_selected.isEmpty) {
+      // Advance past the current version of the leaf-most package.
+      _selected.last.removeFirst();
+      if (!_selected.last.isEmpty) return true;
+
+      // That package has no more versions, so pop it and try the next one.
+      _selected.removeLast();
+    }
+
+    return false;
+  }
+
+  /// Logs [message] in the context of the current selected packages. If
+  /// [message] is omitted, just logs a description of leaf-most selection.
+  void logSolve([String message]) {
+    if (message == null) {
+      if (_selected.isEmpty) {
+        message = "* start at root";
+      } else {
+        message = "* select ${_selected.last.first}";
+      }
+    } else {
+      // Otherwise, indent it under the current selected package.
+      message = "| $message";
+    }
+
+    // Indent for the previous selections.
+    var buffer = new StringBuffer();
+    buffer.writeAll(_selected.skip(1).map((_) => '| '));
+    buffer.write(message);
+    log.solver(buffer);
+  }
+}
+
+/// Given the solver's current set of selected package versions, this tries to
+/// traverse the dependency graph and see if a complete set of valid versions
+/// has been chosen. If it reaches a conflict, it will fail and stop
+/// propagating. If it reaches a package that isn't selected it will refine the
+/// solution by adding that package's set of versions to the solver and then

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

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

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

Right. Added "allowed".

+/// selecting the best one and continuing.
+class Propagator {

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

I still think this belongs in its own file, and that "Propagator" isn't a great
name. What about "Validator"? "Traverser"?

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

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.

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

I generally like one file per class, but whatever floats your boat.

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

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

"packages" -> "package versions"

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

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

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

If you're going to use this term, you need to define it somewhere first.

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

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

+  /// 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

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

"packages" -> "package versions"

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

"concrete packages".

+  /// package multiple times, and to build the complete solution results.
+  final _visited = new Set<PackageId>();
+
+  /// The dependencies visited so far in the traversal. For each package name
+  /// (the map key) we track the list of dependencies that other packages have
+  /// placed on it so that we can calculate the complete constraint for shared
+  /// dependencies.
+  final _dependencies = <String, List<Dependency>>{};
+
+  Propagator(this._solver);
+
+  /// Walks the dependency graph starting at the root package and validates
+  /// that each reached package has a valid version selected.
+  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;
+  }
+
+  /// Traverses the next package in the queue. Completes [completer] with a
+  /// list of package IDs if the traversal completed successfully and found a
+  /// 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.cache.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
+      // real-world package graphs that require backtracking to see which
+      // heuristics work best for Dart.
+      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,
+                     String depender, Queue<PackageRef> refs) {
+    // Move onto the next package if we've traversed all of these references.
+    if (refs.isEmpty) {
+      _processPackage(completer);
+      return;
+    }
+
+    try {
+      var ref = refs.removeFirst();
+
+      _validateDependency(ref, depender);
+      var constraint = _addConstraint(ref, depender);
+
+      var selected = _validateSelected(ref, constraint);
+      if (selected != null) {
+        // The selected package is good, so enqueue it to traverse into it.

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

"package" -> "package version"

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

Done.

+        _packages.add(selected);
+        _traverseRefs(completer, depender, refs);
+        return;
+      }
+
+      // We haven't selected a version. Create a substate that tries all

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

"substate" doesn't really make sense here any more.

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

Reworded.

+      // versions that match the constraints we currently have for this
+      // package.
+      _selectPackage(ref, constraint).then((_) {
+        _traverseRefs(completer, depender, refs);
+      }).catchError((error) {
+        completer.completeError(error);
+      });
+    } catch (error, stackTrace) {
+      completer.completeError(error, stackTrace);
+    }
+  }
+
+  /// Ensures that dependency [ref] from [depender] is consistent with the
+  /// other dependencies on the same package. Throws a [SolverFailure]
+  /// exception if not.

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

Might be worth mentioning that this doesn't validate the consistency of the
version constraints.

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

Done.

+  void _validateDependency(PackageRef ref, String depender) {
+    // Make sure the dependencies agree on source and description.
+    var required = _getRequired(ref.name);
+    if (required == null) return;
+
+    // Make sure all of the existing sources match the new reference.
+    if (required.ref.source.name != ref.source.name) {
+      _solver.logSolve('source mismatch on ${ref.name}: ${required.ref.source} '
+                       '!= ${ref.source}');
+      throw new SourceMismatchException(ref.name,
+          required.depender, required.ref.source, depender, ref.source);
+    }
+
+    // Make sure all of the existing descriptions match the new reference.
+    if (!ref.descriptionEquals(required.ref)) {
+      _solver.logSolve('description mismatch on ${ref.name}: '
+                       '${required.ref.description} != ${ref.description}');
+      throw new DescriptionMismatchException(ref.name,
+          required.depender, required.ref.description,
+          depender, ref.description);
+    }
+  }
+
+  /// Adds the version constraint that [depender] places on [ref] to the
+  /// overall constraint that all shared dependencies place on [ref]. Throws a
+  /// [SolverFailure] if that results in an unsolvable constraints.
+  ///
+  /// Returns the combined [VersionConstraint] that all dependers place on the
+  /// package.
+  VersionConstraint _addConstraint(PackageRef ref, String depender) {
+    // Add the dependency.
+    var dependencies = _getDependencies(ref.name);
+    dependencies.add(new Dependency(depender, ref));
+
+    // Determine the overall version constraint.
+    var constraint = dependencies
+        .map((dep) => dep.ref.constraint)
+        .reduce(VersionConstraint.any, (a, b) => a.intersect(b));
+
+    // TODO(rnystrom): Currently we just backtrack to the previous state when
+    // a failure occurs here. Another option is back*jumping*. When we hit
+    // this, we could jump straight to the nearest selection that selects a
+    // depender that is causing this state to fail. Before doing that, though,
+    // we should:
+    //
+    // 1. Write some complex solver tests that validate which order packages
+    //    are downgraded to reach a solution.
+    // 2. Get some real-world data on which package graphs go pathological.
+
+    // 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.

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

This comment is confusing, since the check for NoVersionException is no longer
in this method.

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

Simplified.

+    if (constraint.isEmpty) {
+      _solver.logSolve('disjoint constraints on ${ref.name}');
+      throw new DisjointConstraintException(ref.name, dependencies);
+    }
+
+    return constraint;
+  }
+
+  /// Validates the currently selected package against the new dependency that
+  /// [ref] and [constraint] place on it. Returns `null` if there is no
+  /// currently selected package, throws a [SolverFailure] if the new reference
+  /// it not valid, or returns the selected package if successful.

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

"is not valid" -> "is not consistent with the selected package"

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

Done.

+  PackageId _validateSelected(PackageRef ref, VersionConstraint constraint) {
+    var selected = _solver.getSelected(ref.name);
+    if (selected == null) return null;
+
+    // Make sure it meets the constraint.
+    if (!ref.constraint.allows(selected.version)) {
+      _solver.logSolve('selection $selected does not match $constraint');
+      throw new NoVersionException(ref.name, constraint,
+                                   _getDependencies(ref.name));
+    }
+
+    return selected;
+  }
+
+  /// Tries to select a package that matches [ref] and [constraint]. Updates
+  /// the solver state so that we can backtrack from this decision if it turns
+  /// out wrong, but continues propagating with the new selection.
+  ///
+  /// Returns a future that completes with a [SolverFailure] if a version
+  /// could not be selected or that completes successfully if a package was
+  /// selected and propagation should continue.
+  Future _selectPackage(PackageRef ref, VersionConstraint constraint) {
+    return _solver.cache.getVersions(ref.name, ref.source, ref.description)
+        .then((versions) {
+      var allowed = versions.where((id) => constraint.allows(id.version));
+
+      // 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 = _getValidLocked(ref.name, constraint);
+      if (locked != null) {
+        allowed = allowed.where((ref) => ref.version != locked.version)
+            .toList();
+        allowed.insert(0, locked);
+      }
+
+      if (allowed.isEmpty) {
+        _solver.logSolve('no versions for ${ref.name} match $constraint');
+        throw new NoVersionException(ref.name, constraint,
+                                     _getDependencies(ref.name));
+      }
+
+      // If we're doing an upgrade on this package, only allow the latest
+      // version.
+      if (_solver._forceLatest.contains(ref.name)) allowed = [allowed.first];
+
+      // Store a checkpoint in case we fail, then try to keep solving using the

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

This is the only time you refer to an element of VersionSolver._selected as a
checkpoint, and it's confusing. 

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

Reworded.

+      // first package in the allowed set.
+      _packages.add(_solver.select(allowed));
+    });
+  }
+
+  /// Gets the list of dependencies for package [name]. Will create an empty
+  /// list if needed.
+  List<Dependency> _getDependencies(String name) {
+    return _dependencies.putIfAbsent(name, () => <Dependency>[]);
+  }
+
+  /// Gets a "required" reference to the package [name]. This is the first
+  /// non-root dependency on that package. All dependencies on a package must
+  /// 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.
+  ///
+  /// This is required because you may have a circular dependency back onto the
+  /// root package. That second dependency won't be a root dependency and it's
+  /// *that* one that other dependencies need to agree on. In other words, you
+  /// can have a bunch of dependencies back onto the root package as long as
+  /// they all agree with each other.
+  Dependency _getRequired(String name) {
+    return _getDependencies(name)
+        .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 _getValidLocked(String name, VersionConstraint constraint) {
+    var package = _solver.getLocked(name);
+    if (package == null) return null;
+
+    if (!constraint.allows(package.version)) return 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;
+  }
+}