Use backtracking when solving dependency constraints.

utils/pub/solver/backtracking_solver.dart

+// 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. Attempts to find the best solution for
+/// a root package's transitive dependency graph, where a "solution" is a set
+/// of concrete package versions. A valid solution will select concrete
+/// versions for every package reached from the root package's dependency graph,
+/// and each of those packages will fit the version constraints placed on it.
+///
+/// It builds up a solution incrementally by traversing the dependency graph
+/// starting at the root package. When it reaches a new package, it gets the
+/// set of versions that meet the current constraint placed on it. It
+/// *speculatively* selects one version from that set and adds it to the
+/// current solution and then proceeds. If it fully traverses the dependency
+/// graph, the solution is valid and it stops.
+///
+/// If it reaches an error:
+///
+/// - A new dependency is placed on a package that's already been selected in
+///   the solution and the selected version doesn't match the new constraint.
+///
+/// - There are no versions available that meet the constraint placed on a
+///   package.
+///
+/// - etc.
+///
+/// then the current solution is invalid. It will then backtrack to the most
+/// recent speculative version choice is selected and try the next one. That
+/// becomes the new current solution and it tries to solve it again. It will
+/// keep doing this, traversing and then backtracking when it meets a failure
+/// until a valid solution has been found or until all possible options for all
+/// speculative choices have been found.
+///
+/// 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. Keeps track of the current solution, and the other
+/// possible versions for speculative package selections. Backtracks and
+/// advances to the next possible solution in the case of a failure.
+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 versions
+  /// are valid. This keeps track of which versions have been selected so far
+  /// and which remain to be tried.
+  ///
+  /// Each entry in the list is an ordered [Queue] of versions to try for a
+  /// single package. The first item in the queue is the currently selected
+  /// version for that package. 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.
+  ///
+  /// It tries versions in depth-first order, so only the last queue in the
+  /// list will have items removed from it. When a new constraint is placed on
+  /// a package already selected, and that constraint doesn't match the
+  /// selected version, that will cause the current solution to fail and
+  /// trigger backtracking.
+  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);
+
+  int get attemptedSolutions => _attemptedSolutions;
+
+  void forceLatestVersion(String package) {
+    _forceLatest.add(package);
+  }
+
+  Future<List<PackageId>> runSolver() {
+    var completer = new Completer<List<PackageId>>();
+    _traverseSolution(completer);
+    return completer.future;
+  }
+
+  /// Adds [versions], which are the list of all allowed versions of a given
+  /// package to the set of versions to consider for solutions. The first item
+  /// in the will be the currently selected version of 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 the currently selected id for the package [name] or `null` if
+  /// no concrete version has been selected for that package 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];
+
+  /// Traverses the root package's dependency graph using the current possible
+  /// solution. If successful, completes [completer] with the solution. If not,
+  /// backtracks to the most recently selected version of a package and tries
+  /// the next version of it. If there are no more versions, continues to
+  /// backtrack to previous selections, and so on. If there is nothing left to
+  /// backtrack to, completes to the last failure that occurred.
+  void _traverseSolution(Completer<List<PackageId>> completer) {
+    _attemptedSolutions++;
+
+    new Traverser(this).traverse().then((packages) {
+      completer.complete(packages);
+    }).catchError((error) {
+      if (error.error is! SolveFailure) {
+        completer.completeError(error);
+        return;
+      }
+
+      if (_backtrack(error.error)) {
+        _traverseSolution(completer);
+      } else {
+        // All out of solutions, so fail.
+        completer.completeError(error);
+      }
+    });
+  }
+
+  /// Backtracks from the current failed solution and determines the next
+  /// solution to try. If possible, it will backjump based on the cause of the
+  /// [failure] to minize backtracking. Otherwise, it will simply backtrack to
+  /// the next possible solution.
+  ///
+  /// Returns `true` if there is a new solution to try.
+  bool _backtrack(SolveFailure failure) {
+    // Look for the most recently selected relevant backjumping point.
+    var jumpTo;
+    var dependers = failure.dependencies.map((dep) => dep.depender).toSet();

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

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?

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

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

[nweiz, 2013/04/11 22:12:04]

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

[Bob Nystrom, 2013/04/16 18:34:17]

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.

+    for (var i = _selected.length - 1; i >= 0; i--) {
+      var name = _selected[i].first.name;
+
+      // If we reach the package that failed, backjump to there.
+      if (failure.package == name) {
+        logSolve('jump to failing package $name');
+        jumpTo = i;
+        break;
+      }
+
+      // If we reach a package whose dependency led to the failing package,
+      // backjump to there.
+      if (dependers.contains(name)) {
+        logSolve('jump to depending package $name');
+        jumpTo = i;
+        break;
+      }
+    }
+
+    if (jumpTo != null) {
+      _selected.removeRange(jumpTo + 1, _selected.length - jumpTo - 1);
+    }
+
+    while (!_selected.isEmpty) {
+      // Advance past the current version of the leaf-most package.
+      _selected.last.removeFirst();
+      if (!_selected.last.isEmpty) {
+        logSolve();
+        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
+/// traversing. If it reaches a package that isn't selected it will refine the
+/// solution by adding that package's set of allowed versions to the solver and
+/// then select the best one and continue.
+class Traverser {
+  final BacktrackingVersionSolver _solver;
+
+  /// The queue of concrete 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 concrete 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>>{};
+
+  Traverser(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>> traverse() {
+    // Start at the root.
+    _packages.add(new PackageId.root(_solver.root));
+
+    var completer = new Completer<List<PackageId>>();
+    _traversePackage(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 _traversePackage(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)) {
+      _traversePackage(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) {
+      _traversePackage(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 version is good, so enqueue it to traverse into
+        // it.
+        _packages.add(selected);
+        _traverseRefs(completer, depender, refs);
+        return;
+      }
+
+      // We haven't selected a version. Get all of the versions that match the
+      // constraints we currently have for this package and add them to the
+      // set of solutions to try.
+      _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. Only validates sources and descriptions, not the
+  /// version.
+  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, new Dependency(depender, ref)]);
+    }
+
+    // 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, new Dependency(depender, ref)]);
+    }
+  }
+
+  /// 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.
+    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 does not allow the previously selected version, 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 traversing 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 traversing 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];
+
+      // Try the first package in the allowed set and keep track of the list of
+      // other possible versions in case that fails.
+      _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;
+  }
+}