Use backtracking when solving dependency constraints.

utils/pub/solver/version_solver.dart

Index: utils/pub/solver/version_solver.dart
diff --git a/utils/pub/solver/version_solver.dart b/utils/pub/solver/version_solver.dart
new file mode 100644
index 0000000000000000000000000000000000000000..564eb504f3ea2f3f4673307e1a2ea69358b56491
--- /dev/null
+++ b/utils/pub/solver/version_solver.dart
@@ -0,0 +1,348 @@
+// 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.
+
+library version_solver;
+
+import 'dart:async';
+import 'dart:json' as json;
+
+import '../lock_file.dart';
+import '../log.dart' as log;
+import '../package.dart';
+import '../pubspec.dart';
+import '../source.dart';
+import '../source_registry.dart';
+import '../version.dart';
+import 'backtracking_solver.dart';
+import 'greedy_solver.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 [useLatest] is given, then only the latest versions of the referenced
+/// packages will be used. This is for forcing an update to one or more
+/// packages.
+///
+/// If [allowBacktracking] is `true` the backtracking version solver will be
+/// used. Otherwise, the non-backtracking one will be.
+Future<SolveResult> resolveVersions(SourceRegistry sources, Package root,
+    {LockFile lockFile, bool allowBacktracking, List<PackageRef> useLatest}) {
+  log.message('Resolving dependencies...');
+
+  if (allowBacktracking == null) allowBacktracking = false;
+  if (lockFile == null) lockFile = new LockFile.empty();
+  if (useLatest == null) useLatest = [];
+
+  var solver;
+  if (allowBacktracking) {
+    solver = new BacktrackingVersionSolver(sources, root, lockFile, useLatest);
+  } else {
+    solver = new GreedyVersionSolver(sources, root, lockFile, useLatest);
+  }
+
+  return solver.solve();
+}
+
+/// Writes [deps] to [buffer] as a bullet list.
+void writeDependencies(StringBuffer buffer, List<Dependency> deps) {

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

Shouldn't this be private?

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

Removed in latest patch.

+  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}");
+  }
+}
+
+/// Base class for an implementation of the version constraint solver.
+class VersionSolver {
+  final SourceRegistry sources;
+  final Package root;
+  final LockFile lockFile;
+  final PubspecCache cache;
+
+  VersionSolver(SourceRegistry sources, this.root, this.lockFile,
+                List<String> useLatest)
+      : sources = sources,
+        cache = new PubspecCache(sources) {
+    for (var package in useLatest) {
+      forceLatestVersion(package);
+      lockFile.packages.remove(package);
+    }
+  }
+
+  /// The number of solutions the solver has tried so far.
+  int get attemptedSolutions;
+
+  /// Force the solver to upgrade [package] to the latest available version.
+  void forceLatestVersion(String package);
+
+  /// Run the solver. Completes with a list of specific package versions if
+  /// successful or an error if it failed to find a solution.
+  Future<SolveResult> solve() {
+    var stopwatch = new Stopwatch();
+    stopwatch.start();
+
+    // Pre-cache the root package's known pubspec.
+    cache.cache(new PackageId.root(root), root.pubspec);
+
+    return runSolver().then((packages) {
+      return new SolveResult(packages, null, attemptedSolutions);
+    }).catchError((error) {
+      if (error.error is! SolveFailure) throw error;
+
+      // Wrap a failure in a result so we can attach some other data.
+      return new SolveResult(null, error.error, attemptedSolutions);
+    }).whenComplete(() {
+      // Gather some solving metrics.
+      var buffer = new StringBuffer();
+      buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.');
+      buffer.writeln(
+          '- Requested ${cache.versionCacheMisses} version lists');
+      buffer.writeln(
+          '- Looked up ${cache.versionCacheHits} cached version lists');
+      buffer.writeln(
+          '- Requested ${cache.pubspecCacheMisses} pubspecs');
+      buffer.writeln(
+          '- Looked up ${cache.pubspecCacheHits} cached pubspecs');
+      log.solver(buffer);
+    });
+  }
+
+  /// Entrypoint for subclasses to actually begin solving. External code should
+  /// call [solve()].
+  Future<List<PackageId>> runSolver();
+}
+
+/// The result of a successful version resolution. (If resolution fails, a
+/// [SolveFailure] will be thrown.

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

This comment is out-of-date; a failing resolution also returns a SolveResult.

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

Done.

+class SolveResult {
+  /// Whether the solver found a complete solution or failed.
+  bool get succeeded => error == null;
+
+  /// The list of concrete package versions that were selected for each package
+  /// reachable from the root, or `null` if the solver failed.
+  final List<PackageId> packages;
+
+  /// The error that prevented the solver from finding a solution or `null` if
+  /// it was successful.
+  final SolveFailure error;
+
+  /// The number of solutions that were attempted before a successful one was
+  /// found. In other words, one more than the number of times it had to
+  /// backtrack because it found an invalid solution.

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

Document what this means if no solution was found.

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

Done.

+  final int attemptedSolutions;
+
+  SolveResult(this.packages, this.error, this.attemptedSolutions);
+
+  String toString() {
+    if (!succeeded) {
+      return 'Failed to solve after $attemptedSolutions attempts:\n'
+             '$error';
+    }
+
+    return 'Took $attemptedSolutions tries to resolve to\n'
+           '- ${packages.join("\n- ")}';
+  }
+}
+
+/// 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<PackageId>>();
+  final _pubspecs = new Map<PackageId, Pubspec>();
+
+  /// The number of times a version list was requested and it wasn't cached and
+  /// had to be requested from the source.
+  int versionCacheMisses = 0;
+
+  /// The number of times a version list was requested and the cached version
+  /// was returned.
+  int versionCacheHits = 0;
+
+  /// The number of times a pubspec was requested and it wasn't cached and had
+  /// to be requested from the source.
+  int pubspecCacheMisses = 0;
+
+  /// The number of times a pubspec was requested and the cached version was
+  /// returned.
+  int pubspecCacheHits = 0;
+
+  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)) {
+      pubspecCacheHits++;
+      return new Future<Pubspec>.immediate(_pubspecs[id]);
+    }
+
+    pubspecCacheMisses++;
+    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.
+    // TODO(rnystrom): Create a separate type for (name, source, description)
+    // without a version.
+    var id = new PackageId(package, source, Version.none, description);
+
+    // See if we have it cached.
+    var versions = _versions[id];
+    if (versions != null) {
+      versionCacheHits++;
+      return new Future.immediate(versions);
+    }
+
+    versionCacheMisses++;
+    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 version list');
+      _versions[id] = ids;
+      return ids;
+    });
+  }
+}
+
+/// 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);
+}
+
+/// Base class for all failures that can occur while trying to resolve versions.
+class SolveFailure implements Exception {}
+
+/// Exception thrown when the [VersionSolver] fails to find a solution after a
+/// certain number of iterations.
+class CouldNotSolveException extends SolveFailure {
+  CouldNotSolveException();
+
+  String toString() =>
+      "Could not find a solution that met all version constraints.";
+}
+
+/// 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 SolveFailure {
+  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 extends SolveFailure {
+  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 SolveFailure {
+  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 SolveFailure {
+  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 SolveFailure {
+  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)}";
+  }
+}