Use backtracking when solving dependency constraints.

utils/pub/version_solver2.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.
+
+/// 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.
+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';
+import 'version_solver.dart';
+
+/// How many times we allow the solver to backtrack looking for a solution
+/// before giving up.
+// TODO(rnystrom): What value should this have? Should it be based on graph
+// size?
+const _MAX_BACKTRACKING = 10000;

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

As discussed offline, I don't like having an iteration cap.

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

Done.

+
+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>();
+
+  /// The current state being explored. Its parent links enable us to walk
+  /// back up the tree to other earlier states.
+  SolveState _state;
+
+  /// The number of solutions we've tried so far.
+  int _iterations = 0;
+
+  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;
+  }
+
+  /// 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) {
+    if (_iterations++ > _MAX_BACKTRACKING) {
+      completer.completeError(new CouldNotSolveException());
+    }
+
+    var state = _state;
+
+    var propagator = new Propagator(this, state);
+    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.
+class Propagator {
+  final BacktrackingVersionSolver _solver;
+
+  /// The queue of packages left to traverse. We do a bread-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 known dependencies visited so far.
+  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]) {
+    if (_state == null) {
+      // Don't waste time building the string if it will be ignored.
+      if (!log.isEnabled(log.Level.SOLVER)) return;
+
+      // 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
+  /// 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
+      // 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;
+    }
+
+    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));
+        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));
+
+    // 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 SolveState 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) {
+      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.
+      _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.
+      _state = _solver.push(ref.name, allowed);
+      selected = _getSelected(ref.name);
+      assert(selected != null);
+
+      _packages.add(selected);
+      _traverseRefs(completer, depender, refs);
+    }).catchError((error) {
+      print(error);
+      completer.completeError(error);
+    });
+  }
+
+  /// Gets the currently selected package named [package] or `null` if no
+  /// 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
+  /// 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) {
+    var package = _solver.getLocked(name);
+    if (package == null) return null;
+
+    if (!constraint.allows(package.version)) return null;
+
+    var dependencies = _dependencies[name];
+    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.
+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;
+
+    // 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);
+  }
+}