Use backtracking when solving dependency constraints.

utils/tests/pub/version_solver_test.dart

Index: utils/tests/pub/version_solver_test.dart
diff --git a/utils/tests/pub/version_solver_test.dart b/utils/tests/pub/version_solver_test.dart
index 835139a34ccb90bbf482e8d06ca85eff658885f5..a2bca7f708f7828a7ff218505c9c545073e14b39 100644
--- a/utils/tests/pub/version_solver_test.dart
+++ b/utils/tests/pub/version_solver_test.dart
@@ -17,7 +17,7 @@ import '../../pub/source_registry.dart';
 import '../../pub/system_cache.dart';
 import '../../pub/utils.dart';
 import '../../pub/version.dart';
-import '../../pub/version_solver.dart';
+import '../../pub/solver/version_solver.dart';
 import 'test_pub.dart';
 
 Matcher noVersion(List<String> packages) {
@@ -52,8 +52,11 @@ Matcher descriptionMismatch(String package1, String package2) {
   }, "is a DescriptionMismatchException");
 }
 
-final couldNotSolve = predicate((x) => x is CouldNotSolveException,
-    "is a CouldNotSolveException");
+// If no solution can be found, the solver just reports the last failure that
+// happened during propagation. Since we don't specify the order that solutions
+// are tried, this just validates that *some* failure occurred, but not which.
+final couldNotSolve = predicate((x) => x is SolverFailure,
+    "is a SolverFailure");
 
 Matcher sourceMismatch(String package1, String package2) {
   return predicate((x) {
@@ -205,6 +208,35 @@ main() {
     'bar': '1.0.2'
   });
 
+  testResolve('unlocks dependencies if necessary to ensure that a new '
+      'dependency is satisfied', {
+    'myapp 0.0.0': {
+      'foo': 'any',
+      'newdep': 'any'
+    },
+    'foo 1.0.0': { 'bar': '<2.0.0' },
+    'bar 1.0.0': { 'baz': '<2.0.0' },
+    'baz 1.0.0': { 'qux': '<2.0.0' },
+    'qux 1.0.0': {},
+    'foo 2.0.0': { 'bar': '<3.0.0' },
+    'bar 2.0.0': { 'baz': '<3.0.0' },
+    'baz 2.0.0': { 'qux': '<3.0.0' },
+    'qux 2.0.0': {},
+    'newdep 2.0.0': { 'baz': '>=1.5.0' }
+  }, lockfile: {
+    'foo': '1.0.0',
+    'bar': '1.0.0',
+    'baz': '1.0.0',
+    'qux': '1.0.0'
+  }, result: {
+    'myapp from root': '0.0.0',
+    'foo': '2.0.0',
+    'bar': '2.0.0',
+    'baz': '2.0.0',
+    'qux': '1.0.0',
+    'newdep': '2.0.0'
+  });
+
   testResolve('circular dependency', {
     'myapp 1.0.0': {
       'foo': '1.0.0'
@@ -265,7 +297,7 @@ main() {
     'foo 1.0.0': {
       'myapp': '<1.0.0'
     }
-  }, error: disjointConstraint(['foo']));
+  }, error: couldNotSolve);
 
   testResolve('no version that matches requirement', {
     'myapp 0.0.0': {
@@ -335,7 +367,7 @@ main() {
     'shared 1.0.0 from mock2': {}
   }, error: sourceMismatch('foo', 'bar'));
 
-  testResolve('unstable dependency graph', {
+  testResolve('circular dependency on older version', {
     'myapp 0.0.0': {
       'a': '>=1.0.0'
     },
@@ -346,6 +378,28 @@ main() {
     'b 1.0.0': {
       'a': '1.0.0'
     }
+  }, result: {
+    'myapp from root': '0.0.0',
+    'a': '1.0.0'
+  }, requiresBacktracking: true);
+
+  testResolve('unsolvable', {
+    'myapp 0.0.0': {
+      'a': 'any',
+      'b': 'any'
+    },
+    'a 1.0.0': {
+      'b': '1.0.0'
+    },
+    'a 2.0.0': {
+      'b': '2.0.0'
+    },
+    'b 1.0.0': {
+      'a': '2.0.0'
+    },
+    'b 2.0.0': {
+      'a': '1.0.0'
+    }
   }, error: couldNotSolve);
 
   group('dev dependencies', () {
@@ -389,14 +443,82 @@ main() {
       'foo': '1.0.0'
     });
   });
+
+  // Only one version of baz, so foo and bar will have to downgrade until they
+  // reach it.
+  testResolve('simple backtracking', {
+    'myapp 0.0.0': {'foo': 'any'},
+    'foo 1.0.0': {'bar': '1.0.0'},
+    'foo 2.0.0': {'bar': '2.0.0'},
+    'foo 3.0.0': {'bar': '3.0.0'},
+    'bar 1.0.0': {'baz': 'any'},
+    'bar 2.0.0': {'baz': '2.0.0'},
+    'bar 3.0.0': {'baz': '3.0.0'},
+    'baz 1.0.0': {}
+  }, result: {
+    'myapp from root': '0.0.0',
+    'foo': '1.0.0',
+    'bar': '1.0.0',
+    'baz': '1.0.0'
+  }, requiresBacktracking: true);
+
+  // This sets up a hundred versions of foo and bar, 0.0.0 through 9.9.0. Each
+  // version of foo depends on a baz with the same major version. Each version
+  // of bar depends on a baz with the same minor version. There is only one
+  // version of baz, 0.0.0, so only older versions of foo and bar will
+  // satisfy it.
+  var map = {
+    'myapp 0.0.0': {
+      'foo': 'any',
+      'bar': 'any'
+    },
+    'baz 0.0.0': {}
+  };
+
+  for (var i = 0; i < 10; i++) {
+    for (var j = 0; j < 10; j++) {
+      map['foo $i.$j.0'] = {'baz': '$i.0.0'};
+      map['bar $i.$j.0'] = {'baz': '0.$j.0'};
+    }
+  }
+
+  testResolve('complex backtrack', map, result: {
+    'myapp from root': '0.0.0',
+    'foo': '0.9.0',
+    'bar': '9.0.0',
+    'baz': '0.0.0'
+  }, requiresBacktracking: true);
 }
 
 // TODO(rnystrom): More stuff to test:
 // - Depending on a non-existent package.
-// - Test that only a certain number requests are sent to the mock source so we
-//   can keep track of server traffic.
 
-testResolve(description, packages, {lockfile, result, Matcher error}) {
+testResolve(description, packages,
+            {lockfile, result, Matcher error, bool requiresBacktracking}) {
+  _testResolveWithSolver(description, packages,
+      allowBacktracking: false, lockfile: lockfile, result: result, error: error,
+      requiresBacktracking: requiresBacktracking);
+  _testResolveWithSolver(description, packages,
+      allowBacktracking: true, lockfile: lockfile, result: result, error: error,
+      requiresBacktracking: requiresBacktracking);
+}
+
+_testResolveWithSolver(description, packages, {bool allowBacktracking, lockfile,
+                       result, Matcher error, bool requiresBacktracking}) {
+  if (requiresBacktracking == null) requiresBacktracking = false;
+
+  if (allowBacktracking) {
+    description = 'backtracking solver $description';
+  } else {
+    description = 'greedy solver $description';
+
+    // The greedy solver should fail any graph that does require backtracking.
+    if (requiresBacktracking) {
+      result = null;
+      error = couldNotSolve;
+    }
+  }
+
   test(description, () {
     var cache = new SystemCache('.');
     source1 = new MockSource('mock1');
@@ -413,14 +535,14 @@ testResolve(description, packages, {lockfile, result, Matcher error}) {
         var name = parts[0];
         var version = parts[1];
 
-        var package = source1.mockPackage(name, version, dependencies);
+        var package = mockPackage(name, version, dependencies);
         if (name == 'myapp') {
           // Don't add the root package to the server, so we can verify that Pub
           // doesn't try to look up information about the local package on the
           // remote server.
           root = package;
         } else {
-          source.addPackage(package);
+          source.addPackage(name, package);
         }
       });
     });
@@ -447,7 +569,8 @@ testResolve(description, packages, {lockfile, result, Matcher error}) {
     }
 
     // Resolve the versions.
-    var future = resolveVersions(cache.sources, root, realLockFile);
+    var future = resolveVersions(cache.sources, root,
+        allowBacktracking: allowBacktracking, lockFile: realLockFile);
 
     if (result != null) {
       expect(future, completion(predicate((actualResult) {
@@ -472,21 +595,51 @@ testResolve(description, packages, {lockfile, result, Matcher error}) {
 /// string and stripping off any trailing hyphen followed by non-hyphen
 /// characters.
 class MockSource extends Source {
-  final Map<String, Map<Version, Package>> _packages;
+  final _packages = <String, Map<Version, Package>>{};
+
+  /// Keeps track of which package version lists have been requested. Ensures
+  /// that a source is only hit once for a given package and that pub
+  /// internally caches the results.
+  final _requestedVersions = new Set<String>();
+
+  /// Keeps track of which package pubspecs have been requested. Ensures that a
+  /// source is only hit once for a given package and that pub internally
+  /// caches the results.
+  final _requestedPubspecs = new Map<String, Set<Version>>();
 
   final String name;
   bool get shouldCache => true;
 
-  MockSource(this.name)
-      : _packages = <String, Map<Version, Package>>{};
+  MockSource(this.name);
 
   Future<List<Version>> getVersions(String name, String description) {
-    return defer(() => _packages[description].keys.toList());
+    return defer(() {
+      // Make sure the solver doesn't request the same thing twice.
+      if (_requestedVersions.contains(description)) {
+        throw 'Version list for $description was already requested.';
+      }
+
+      _requestedVersions.add(description);
+
+      if (!_packages.containsKey(description)){
+        throw 'MockSource does not have a package matching "$description".';
+      }
+      return _packages[description].keys.toList();
+    });
   }
 
   Future<Pubspec> describe(PackageId id) {
     return defer(() {
-      return _packages[id.name][id.version].pubspec;
+      // Make sure the solver doesn't request the same thing twice.
+      if (_requestedPubspecs.containsKey(id.description) &&
+          _requestedPubspecs[id.description].contains(id.version)) {
+        throw 'Pubspec for $id was already requested.';
+      }
+
+      _requestedPubspecs.putIfAbsent(id.description, () => new Set<Version>());
+      _requestedPubspecs[id.description].add(id.version);
+
+      return _packages[id.description][id.version].pubspec;
     });
   }
 
@@ -494,36 +647,37 @@ class MockSource extends Source {
     throw 'no';
   }
 
-  Package mockPackage(String description, String version,
-      Map dependencyStrings) {
-    // Build the pubspec dependencies.
-    var dependencies = <PackageRef>[];
-    var devDependencies = <PackageRef>[];
-
-    dependencyStrings.forEach((name, constraint) {
-      parseSource(name, (isDev, name, source) {
-        var packageName = name.replaceFirst(new RegExp(r"-[^-]+$"), "");
-        var ref = new PackageRef(packageName, source,
-            new VersionConstraint.parse(constraint), name);
+  void addPackage(String description, Package package) {
+    _packages.putIfAbsent(description, () => new Map<Version, Package>());
+    _packages[description][package.version] = package;
+  }
+}
 
-        if (isDev) {
-          devDependencies.add(ref);
-        } else {
-          dependencies.add(ref);
-        }
-      });
+Package mockPackage(String description, String version,
+                    Map dependencyStrings) {
+  // Build the pubspec dependencies.
+  var dependencies = <PackageRef>[];
+  var devDependencies = <PackageRef>[];
+
+  dependencyStrings.forEach((name, constraint) {
+    parseSource(name, (isDev, name, source) {
+      var packageName = name.replaceFirst(new RegExp(r"-[^-]+$"), "");
+      var ref = new PackageRef(packageName, source,
+          new VersionConstraint.parse(constraint), name);
+
+      if (isDev) {
+        devDependencies.add(ref);
+      } else {
+        dependencies.add(ref);
+      }
     });
+  });
 
-    var pubspec = new Pubspec(
-        description, new Version.parse(version), dependencies, devDependencies,
-        new PubspecEnvironment());
-    return new Package.inMemory(pubspec);
-  }
-
-  void addPackage(Package package) {
-    _packages.putIfAbsent(package.name, () => new Map<Version, Package>());
-    _packages[package.name][package.version] = package;
-  }
+  var name = description.replaceFirst(new RegExp(r"-[^-]+$"), "");
+  var pubspec = new Pubspec(
+      name, new Version.parse(version), dependencies, devDependencies,
+      new PubspecEnvironment());
+  return new Package.inMemory(pubspec);
 }
 
 void parseSource(String description,