Switch to backtracking solver.

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.
 ///
@@ skipping 13 matching lines @@
 ///   package.
 ///
 /// - etc.
 ///
 /// then the current solution is invalid. It will then backtrack to the most
 /// recent speculative version choice and try the next one. That becomes the
 /// new in-progress solution and it tries to proceed from there. 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 exhausted.
-library version_solver2;
+library solver.backtracking_solver;
 
 import 'dart:async';
 import 'dart:collection' show Queue;
 
 import '../lock_file.dart';
 import '../log.dart' as log;
 import '../package.dart';
 import '../pubspec.dart';
 import '../sdk.dart' as sdk;
 import '../source.dart';
 import '../source_registry.dart';
 import '../utils.dart';
 import '../version.dart';
 import 'version_solver.dart';
 
 /// The top-level solver. Keeps track of the current potential solution, and
 /// the other possible versions for speculative package selections. Backtracks
 /// and advances to the next potential solution in the case of a failure.
-class BacktrackingVersionSolver extends VersionSolver {
+class BacktrackingSolver {
+  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>();
 
   /// 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.
   ///
   /// The solver 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 an already-selected package, 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.
+  /// The number of solutions the solver has tried so far.
   int get attemptedSolutions => _attemptedSolutions;
   var _attemptedSolutions = 1;
 
-  BacktrackingVersionSolver(SourceRegistry sources, Package root,
-      LockFile lockFile, List<String> useLatest)
-      : super(sources, root, lockFile, useLatest);
+  BacktrackingSolver(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);
+    }
+  }
+
+  /// 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();
+
+    return new Future(() {
+      stopwatch.start();
+
+      // Pre-cache the root package's known pubspec.
+      cache.cache(new PackageId.root(root), root.pubspec);
+
+      _validateSdkConstraint(root.pubspec);
+      return _traverseSolution();
+    }).then((packages) {
+      return new SolveResult(packages, null, attemptedSolutions);
+    }).catchError((error) {
+      if (error is! SolveFailure) throw error;
+
+      // Wrap a failure in a result so we can attach some other data.
+      return new SolveResult(null, 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);
+    });
+  }
 
   void forceLatestVersion(String package) {
     _forceLatest.add(package);
   }
 
-  Future<List<PackageId>> runSolver() {
-    return new Future.sync(() {
-      _validateSdkConstraint(root.pubspec);
-      return _traverseSolution();
-    });
-  }
-
   /// Adds [versions], which is the list of all allowed versions of a given
   /// package, to the set of versions to consider for solutions. The first item
   /// in the list 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;
   }
@@ skipping 145 matching lines @@
   }
 }
 
 /// 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;
+  final BacktrackingSolver _solver;
 
   /// The queue of 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 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>();
 
@@ skipping 276 matching lines @@
 /// Ensures that if [pubspec] has an SDK constraint, then it is compatible
 /// with the current SDK. Throws a [SolverFailure] if not.
 void _validateSdkConstraint(Pubspec pubspec) {
   if (pubspec.environment.sdkVersion.allows(sdk.version)) return;
 
   throw new CouldNotSolveException(
       'Package ${pubspec.name} requires SDK version '
       '${pubspec.environment.sdkVersion} but the current SDK is '
       '${sdk.version}.');
 }