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.
+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
+/// 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 {
+  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.
+  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);
+    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 VersionSolver _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
+      // 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,
+                     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));
+
+    // 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);
+  }
+}
+
+/// 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>>();
+  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) {
+    _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) {
+    // Create a fake ID to use as a key.
+    var id = new PackageId(package, source, Version.none, description);
+
+    // 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))
+          .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) {
+    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 {
+  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)}";
+  }
+}