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..ede3fe789ffa5c12a4df36b4a9d3be0141563d9d
--- /dev/null
+++ b/utils/pub/solver/version_solver.dart
@@ -0,0 +1,307 @@
+// 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 successful, completes to a list of selected [PackageId]s. If
+/// it fails, the future will complete with a [SolverFailure].
+///
+/// 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` (or omitted), the backtracking version
+/// solver will be used. Otherwise, the non-backtracking one will be.
+Future<List<PackageId>> resolveVersions(SourceRegistry sources, Package root,
+    {LockFile lockFile, bool allowBacktracking, List<PackageRef> useLatest}) {
+  log.message('Resolving dependencies...');
+
+  if (allowBacktracking == null) allowBacktracking = true;
+  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();
+}
+
+/// 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);
+    }
+  }
+
+  /// 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<List<PackageId>> solve() {
+    var stopwatch = new Stopwatch();
+    stopwatch.start();
+
+    // Pre-cache the root package's known pubspec.
+    cache.cache(new PackageId.root(root), root.pubspec);
+
+    // Gather some solving metrics.
+    return runSolver().whenComplete(() {
+      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();
+}
+
+/// 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 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 [VersionSolver] fails to find a solution after a
+/// certain number of iterations.
+class CouldNotSolveException extends SolverFailure {
+  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 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 extends SolverFailure {
+  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)}";
+  }
+}