Use backtracking when solving dependency constraints.

utils/tests/pub/version_solver_test.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.
 
 library pub_update_test;
 
 import 'dart:async';
 import 'dart:io';
 
 import '../../../pkg/unittest/lib/unittest.dart';
 
 import '../../pub/lock_file.dart';
 import '../../pub/package.dart';
 import '../../pub/pubspec.dart';
 import '../../pub/source.dart';
 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/version_solver2.dart';
 import 'test_pub.dart';
 
 Matcher noVersion(List<String> packages) {
   return predicate((x) {
     if (x is! NoVersionException) return false;
 
     // Make sure the error string mentions the conflicting dependers.
     var message = x.toString();
     return packages.every((package) => message.contains(package));
   }, "is a NoVersionException");
@@ skipping 14 matching lines @@
     if (x is! DescriptionMismatchException) return false;
 
     // Make sure the error string mentions the conflicting dependers.
     if (!x.toString().contains(package1)) return false;
     if (!x.toString().contains(package2)) return false;
 
     return true;
   }, "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) {
     if (x is! SourceMismatchException) return false;
 
     // Make sure the error string mentions the conflicting dependers.
     if (!x.toString().contains(package1)) return false;
     if (!x.toString().contains(package2)) return false;
 
     return true;
@@ skipping 131 matching lines @@
     'bar 1.0.2': {},
     'baz 1.0.0': {}
   }, lockfile: {
     'baz': '1.0.0'
   }, result: {
     'myapp from root': '0.0.0',
     'foo': '1.0.2',
     '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'
     },
     'foo 1.0.0': {
       'bar': '1.0.0'
     },
     'bar 1.0.0': {
       'foo': '1.0.0'
     }
@@ skipping 40 matching lines @@
     }
   }, error: sourceMismatch('foo', 'bar'));
 
   testResolve('dependency back onto root package with wrong version', {
     'myapp 1.0.0': {
       'foo': '1.0.0'
     },
     'foo 1.0.0': {
       'myapp': '<1.0.0'
     }
-  }, error: disjointConstraint(['foo']));
+  }, error: noVersion(['foo']));
 
   testResolve('no version that matches requirement', {
     'myapp 0.0.0': {
       'foo': '>=1.0.0 <2.0.0'
     },
     'foo 2.0.0': {},
     'foo 2.1.3': {}
   }, error: noVersion(['myapp']));
 
   testResolve('no version that matches combined constraint', {
@@ skipping 49 matching lines @@
     'foo 1.0.0': {
       'shared': '1.0.0'
     },
     'bar 1.0.0': {
       'shared from mock2': '1.0.0'
     },
     'shared 1.0.0': {},
     'shared 1.0.0 from mock2': {}
   }, error: sourceMismatch('foo', 'bar'));
 
-  testResolve('unstable dependency graph', {
+  // This used to fail on the old solver because it requires downgrading an
+  // earlier-selected dependency (a) in order to find a solution.
+  testResolve('circular dependency on older version', {
     'myapp 0.0.0': {
       'a': '>=1.0.0'
     },
     'a 1.0.0': {},
     'a 2.0.0': {
       'b': '1.0.0'
     },
     'b 1.0.0': {
       'a': '1.0.0'
     }
+  }, result: {
+    'myapp from root': '0.0.0',
+    'a': '1.0.0'
+  });
+
+  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', () {
     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': {}
@@ skipping 23 matching lines @@
       },
       'foo 1.0.0': {
         '(dev) bar': '1.0.0'
       },
       'bar 1.0.0': {}
     }, result: {
       'myapp from root': '1.0.0',
       'foo': '1.0.0'
     });
   });
+
+  group('backtracking', () {
+    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'
+    });
+
+    // Pathological example.

[nweiz, 2013/03/29 01:58:25]

Pathological in what sense?

+    // TODO(rnystrom): Document better.

[nweiz, 2013/03/29 01:58:25]

Please do. I don't understand the purpose of this test.

[Bob Nystrom, 2013/03/30 00:15:55]

Added better docs.

+    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('nasty backtrack', map, result: {
+      'myapp from root': '0.0.0',
+      'foo': '0.9.0',
+      'bar': '9.0.0',
+      'baz': '0.0.0'
+    });
+  });

[nweiz, 2013/03/29 01:58:25]

It seems like a lot more tests are necessarily to fully exercise the new solver.
You should at least test that every kind of solution error triggers backtracking
and that backtracking finds the "best" solution in various cases where such a
thing might be ambiguous. I would also like to see tests that measure the number
of steps being taken, either by testing the solver logs against an expected
string or by tracking some sort of counter.

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

You don't necessarily need to add these in this CL, but if you don't add a TODO
about it.

[Bob Nystrom, 2013/04/08 22:12:59]

Agreed. I've added some, but I'd like to add more once I have a clearer picture
of what kinds of tests trigger interesting behavior.
Good idea. Added a TODO.
Done. Any test that requires backtracking now specifies the maximum number of
solution attempts it can try. If it goes over, the test fails.

[Bob Nystrom, 2013/04/08 22:12:59]

Done.

 }
 
 // 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.
 
+solo_testResolve(description, packages, {lockfile, result, Matcher error}) {
+  _testResolve(solo_test, description, packages,
+      lockfile: lockfile, result: result, error: error);
+}
+
 testResolve(description, packages, {lockfile, result, Matcher error}) {
-  test(description, () {
+  _testResolve(test, description, packages,
+      lockfile: lockfile, result: result, error: error);
+}
+
+_testResolve(testFn, description, packages, {lockfile, result, Matcher error}) {
+  testFn(description, () {
     var cache = new SystemCache('.');
     source1 = new MockSource('mock1');
     source2 = new MockSource('mock2');
     cache.register(source1);
     cache.register(source2);
     cache.sources.setDefault(source1.name);
 
     // Build the test package graph.
     var root;
     packages.forEach((nameVersion, dependencies) {
       var parsed = parseSource(nameVersion, (isDev, nameVersion, source) {
         var parts = nameVersion.split(' ');
         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);
         }
       });
     });
 
     // Clean up the expectation.
     if (result != null) {
       var newResult = {};
       result.forEach((name, version) {
         parseSource(name, (isDev, name, source) {
           version = new Version.parse(version);
@@ skipping 31 matching lines @@
 }
 
 /// A source used for testing. This both creates mock package objects and acts
 /// as a source for them.
 ///
 /// In order to support testing packages that have the same name but different
 /// descriptions, a package's name is calculated by taking the description
 /// 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;
     });
   }
 
   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);
-
-        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;
+  void addPackage(String description, Package package) {
+    _packages.putIfAbsent(description, () => new Map<Version, Package>());
+    _packages[description][package.version] = package;
   }
 }
 
+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 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,
     callback(bool isDev, String name, Source source)) {
   var isDev = false;
 
   if (description.startsWith("(dev) ")) {
     description = description.substring("(dev) ".length);
     isDev = true;
   }
 
   var name = description;
   var source = source1;
 
   var sourceNames = {
     'mock1': source1,
     'mock2': source2,
     'root': null
   };
 
   var match = new RegExp(r"(.*) from (.*)").firstMatch(description);
   if (match != null) {
     name = match[1];
     source = sourceNames[match[2]];
   }
 
   callback(isDev, name, source);
 }