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 94a7c58a4c76c57785887945e003e3b89682eab2..ab3f62629c88c29aa194385582410b833cf1da36 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) {
@@ -70,9 +73,26 @@ Matcher sourceMismatch(String package1, String package2) {
 MockSource source1;
 MockSource source2;
 
+var allowBacktracking;

[nweiz, 2013/04/03 00:28:43]

Declare this as a bool, since it doesn't have an initial value.

[Bob Nystrom, 2013/04/08 22:13:00]

Done.

+
 main() {
   initConfig();
 
+  for (allowBacktracking in [false, true]) {
+    group(allowBacktracking ? 'BackTrackingSolver' : 'GreedySolver', () {
+      group('basic graph', basicGraph);
+      group('with lockfile', withLockFile);
+      group('root dependency', rootDependency);
+      group('dev dependency', devDependency);
+      group('unsolvable', unsolvable);
+      group('backtracking', backtracking);
+    });
+  }
+
+  allowBacktracking = 'wtf';

[nweiz, 2013/04/03 00:28:43]

wtf?

[Bob Nystrom, 2013/04/08 22:13:00]

Heh. Debug code. Removed. :)

+}
+
+void basicGraph() {
   testResolve('no dependencies', {
     'myapp 0.0.0': {}
   }, result: {
@@ -148,8 +168,26 @@ main() {
     'foo': '1.0.1',
     'bar': '1.0.0',
     'bang': '1.0.0'
+  }, maxTries: 3, hasGreedySolution: true);

[nweiz, 2013/04/03 00:28:43]

This case will take about N iterations for the backtracking solver, where N is
the number of versions of foo that are allowed by myapp but not by bar -- or
would if "bar" came alphabetically after "foo". We should have tests that verify
behavior like that.

Also, what happens when there's another dependency from myapp that's traversed
between foo and bar? I think for M such dependencies, this will take N^M
iterations to solve.

[Bob Nystrom, 2013/04/08 22:13:00]

That sounds about right though I think it gets more complicated based on the
details of the shape of the dependency graph and the version constraints. Also,
the order that dependencies are traversed will affect things.

+
+  testResolve('circular dependency', {
+    'myapp 1.0.0': {
+      'foo': '1.0.0'
+    },
+    'foo 1.0.0': {
+      'bar': '1.0.0'
+    },
+    'bar 1.0.0': {
+      'foo': '1.0.0'
+    }
+  }, result: {
+    'myapp from root': '1.0.0',
+    'foo': '1.0.0',
+    'bar': '1.0.0'
   });
+}
 
+withLockFile() {
   testResolve('with compatible locked dependency', {
     'myapp 0.0.0': {
       'foo': 'any'
@@ -205,23 +243,38 @@ main() {
     'bar': '1.0.2'
   });
 
-  testResolve('circular dependency', {
-    'myapp 1.0.0': {
-      'foo': '1.0.0'
-    },
-    'foo 1.0.0': {
-      'bar': '1.0.0'
-    },
-    'bar 1.0.0': {
-      'foo': '1.0.0'
-    }
-  }, result: {
-    'myapp from root': '1.0.0',
+  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'
-  });
+    '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'
+  }, maxTries: 5, hasGreedySolution: true);

[nweiz, 2013/04/03 00:28:43]

These numbers feel very opaque to me. Could you include a short explanation of
where the iterations are coming from?

[Bob Nystrom, 2013/04/08 22:13:00]

Explaining where the iterations come from would basically just be restating what
the implementation does. I think that should be documented in the solver and not
here. The tests should be declarative: what the expected behavior is, and not a
description of the imperative steps it took to get there.

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

The generalized behavior of the solver is very complex and difficult to reason
about. Explaining the behavior in a specific instance, even if you're just
walking through the steps the solver takes, is useful.

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

It's useful, but I think that documentation belongs in the solver, not here. We
don't have any docs here that walk through the equally complex steps the old
solver takes, and if I change implementation details of the solver, I don't want
to have up update docs in the tests.

The implementation is the "how", tests should just be "what".

+}
 
-  testResolve('dependency back onto root package', {
+rootDependency() {
+  testResolve('with root source', {
     'myapp 1.0.0': {
       'foo': '1.0.0'
     },
@@ -233,7 +286,7 @@ main() {
     'foo': '1.0.0'
   });
 
-  testResolve('dependency back onto root package with different source', {
+  testResolve('with different source', {
     'myapp 1.0.0': {
       'foo': '1.0.0'
     },
@@ -245,7 +298,7 @@ main() {
     'foo': '1.0.0'
   });
 
-  testResolve('mismatched dependencies back onto root package', {
+  testResolve('with mismatched sources', {
     'myapp 1.0.0': {
       'foo': '1.0.0',
       'bar': '1.0.0'
@@ -258,15 +311,59 @@ main() {
     }
   }, error: sourceMismatch('foo', 'bar'));
 
-  testResolve('dependency back onto root package with wrong version', {
+  testResolve('with wrong version', {
     'myapp 1.0.0': {
       'foo': '1.0.0'
     },
     'foo 1.0.0': {
       'myapp': '<1.0.0'
     }
-  }, error: disjointConstraint(['foo']));
+  }, error: couldNotSolve);
+}
+
+devDependency() {
+  testResolve("includes root package's dev dependencies", {
+    'myapp 1.0.0': {
+      '(dev) foo': '1.0.0',
+      '(dev) bar': '1.0.0'
+    },
+    'foo 1.0.0': {},
+    'bar 1.0.0': {}
+  }, result: {
+    'myapp from root': '1.0.0',
+    'foo': '1.0.0',
+    'bar': '1.0.0'
+  });
+
+  testResolve("includes dev dependency's transitive dependencies", {
+    'myapp 1.0.0': {
+      '(dev) foo': '1.0.0'
+    },
+    'foo 1.0.0': {
+      'bar': '1.0.0'
+    },
+    'bar 1.0.0': {}
+  }, result: {
+    'myapp from root': '1.0.0',
+    'foo': '1.0.0',
+    'bar': '1.0.0'
+  });
+
+  testResolve("ignores transitive dependency's dev dependencies", {
+    'myapp 1.0.0': {
+      'foo': '1.0.0'
+    },
+    'foo 1.0.0': {
+      '(dev) bar': '1.0.0'
+    },
+    'bar 1.0.0': {}
+  }, result: {
+    'myapp from root': '1.0.0',
+    'foo': '1.0.0'
+  });
+}
 
+unsolvable() {

[nweiz, 2013/04/03 00:28:43]

Iteration counts seem very relevant for testing these against the backtracking
solver.

[Bob Nystrom, 2013/04/08 22:13:00]

Done.

   testResolve('no version that matches requirement', {
     'myapp 0.0.0': {
       'foo': '>=1.0.0 <2.0.0'
@@ -335,7 +432,28 @@ main() {
     'shared 1.0.0 from mock2': {}
   }, error: sourceMismatch('foo', 'bar'));
 
-  testResolve('unstable dependency graph', {
+  testResolve('no valid solution', {
+    '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);
+}
+
+backtracking() {
+  testResolve('circular dependency on older version', {
     'myapp 0.0.0': {
       'a': '>=1.0.0'
     },
@@ -346,57 +464,102 @@ main() {
     'b 1.0.0': {
       'a': '1.0.0'
     }
-  }, error: couldNotSolve);
+  }, result: {
+    'myapp from root': '0.0.0',
+    'a': '1.0.0'
+  }, maxTries: 3);
 
-  group('dev dependencies', () {
-    testResolve("includes root package's dev dependencies", {
-      'myapp 1.0.0': {
-        '(dev) foo': '1.0.0',
-        '(dev) bar': '1.0.0'
-      },
-      'foo 1.0.0': {},
-      'bar 1.0.0': {}
-    }, result: {
-      'myapp from root': '1.0.0',
-      'foo': '1.0.0',
-      'bar': '1.0.0'
-    });
+  /// The latest versions of a and b disagree on c. An older version of either
+  /// will resolve the problem. This test validates that b, which is farther
+  /// in the dependency graph from myapp is downgraded first.
+  testResolve('rolls back leaf versions first', {
+    'myapp 0.0.0': {
+      'a': 'any'
+    },
+    'a 1.0.0': {
+      'b': 'any'
+    },
+    'a 2.0.0': {
+      'b': 'any',
+      'c': '2.0.0'
+    },
+    'b 1.0.0': {},
+    'b 2.0.0': {
+      'c': '1.0.0'
+    },
+    'c 1.0.0': {},
+    'c 2.0.0': {}
+  }, result: {
+    'myapp from root': '0.0.0',
+    'a': '2.0.0',
+    'b': '1.0.0',
+    'c': '2.0.0'
+  }, maxTries: 3);
+
+  // Only one version of baz, so foo and bar will have to downgrade until they
+  // reach it.
+  testResolve('simple transitive', {
+    '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'
+  }, maxTries: 5);
+
+  // 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

[nweiz, 2013/04/03 00:28:43]

"the same minor version" is inaccurate; foo depends on a version of baz with the
same major version.

[Bob Nystrom, 2013/04/08 22:13:00]

Done.

+  // 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': {}
+  };
 
-    testResolve("includes dev dependency's transitive dependencies", {
-      'myapp 1.0.0': {
-        '(dev) foo': '1.0.0'
-      },
-      'foo 1.0.0': {
-        'bar': '1.0.0'
-      },
-      'bar 1.0.0': {}
-    }, result: {
-      'myapp from root': '1.0.0',
-      'foo': '1.0.0',
-      'bar': '1.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("ignores transitive dependency's dev dependencies", {
-      'myapp 1.0.0': {
-        'foo': '1.0.0'
-      },
-      'foo 1.0.0': {
-        '(dev) bar': '1.0.0'
-      },
-      'bar 1.0.0': {}
-    }, result: {
-      'myapp from root': '1.0.0',
-      'foo': '1.0.0'
-    });
-  });
+  testResolve('complex backtrack', map, result: {
+    'myapp from root': '0.0.0',
+    'foo': '0.9.0',
+    'bar': '9.0.0',
+    'baz': '0.0.0'
+  }, maxTries: 1090); // TODO(rnystrom): Is this acceptable?
 }
 
-// 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, int maxTries,
+             bool hasGreedySolution}) {
+  // Close over the top-level variable since it will be mutated.
+  var allowBacktracking_ = allowBacktracking;
+
+  if (maxTries == null) maxTries = 1;
+  if (hasGreedySolution == null) hasGreedySolution = false;
+
+  if (!allowBacktracking_) {
+    // The greedy solver should fail any graph that does expect multiple tries
+    // and isn't explicitly annotated to have a greedy solution.
+    if (maxTries > 1 && !hasGreedySolution) {

[nweiz, 2013/04/03 00:28:43]

It would be more readable if you assigned hasGreedySolution to "maxTries > 1" by
default.

[Bob Nystrom, 2013/04/08 22:13:00]

Done.

+      result = null;
+      error = couldNotSolve;
+    }
+  }
 
-testResolve(description, packages, {lockfile, result, Matcher error}) {
   test(description, () {
     var cache = new SystemCache('.');
     source1 = new MockSource('mock1');
@@ -413,14 +576,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,17 +610,24 @@ 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) {
-        for (var actualId in actualResult) {
+      expect(future, completion(predicate((actual) {
+        for (var actualId in actual.packages) {
           if (!result.containsKey(actualId.name)) return false;
           var expectedId = result.remove(actualId.name);
           if (actualId != expectedId) return false;
         }
+
         return result.isEmpty;
+
       }, 'packages to match $result')));
+
+      expect(future, completion(predicate(
+          (actual) => actual.attemptedSolutions <= maxTries,
+          'does not backtrack too much')));
     } else if (error != null) {
       expect(future, throwsA(error));
     }
@@ -472,56 +642,89 @@ 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 new Future.of(() => _packages[description].keys.toList());
+    return new Future.of(() {
+      // 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 new Future.of(() => _packages[id.name][id.version].pubspec);
+    return new Future.of(() {
+      // 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;
+    });
   }
 
   Future<bool> install(PackageId id, String path) {
     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,