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..182b44a53971fe971981e8e99ebfffe0968a1dcd
--- /dev/null
+++ b/utils/pub/solver/backtracking_solver.dart
@@ -0,0 +1,437 @@
+// 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.
+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
+  /// 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
+  /// 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.
+  final _selected = <Queue<PackageId>>[];
+
+  /// The number of possible solutions that have been attempted.
+  int _attemptedSolutions = 0;
+
+  BacktrackingVersionSolver(SourceRegistry sources, Package root,
+      LockFile lockFile, List<String> useLatest)
+      : super(sources, root, lockFile, useLatest);
+
+  void forceLatestVersion(String package) {
+    _forceLatest.add(package);
+  }
+
+  Future<SolveResult> runSolver() {
+    var completer = new Completer<SolveResult>();
+    _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
+  /// will be tried if it the current selection fails. Returns the first
+  /// selected version.
+  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
+  /// concrete package has been selected with that name yet.
+  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
+  /// [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<SolveResult> completer) {
+    var oldLength = _selected.length;
+
+    _attemptedSolutions++;
+
+    new Propagator(this).propagate().then((packages) {
+      completer.complete(new SolveResult(packages, _attemptedSolutions));
+    }).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.
+  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
+/// selecting the best one and continuing.
+class Propagator {
+  final BacktrackingVersionSolver _solver;
+
+  /// The queue of packages left to traverse. We do a breadth-first traversal
+  /// 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 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.
+        _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.
+      _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.
+  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.
+    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.
+  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
+      // 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;
+  }
+}