Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(472)

Unified Diff: utils/tests/pub/version_solver_test.dart

Issue 13095015: Use backtracking when solving dependency constraints. (Closed) Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart
Patch Set: Clean up some test code. Created 7 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
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 bdec057bc2af7bf4d69b6ae5e6025fb6c90ee5ae..706b80a526b6e17aa5727aca67700a680189013b 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/version_solver2.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: noVersion(['foo']));
testResolve('no version that matches requirement', {
'myapp 0.0.0': {
@@ -335,7 +367,9 @@ main() {
'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'
},
@@ -346,6 +380,28 @@ main() {
'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', () {
@@ -389,6 +445,62 @@ main() {
'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
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
nweiz 2013/04/03 00:28:42 You don't necessarily need to add these in this CL
Bob Nystrom 2013/04/08 22:12:59 Agreed. I've added some, but I'd like to add more
Bob Nystrom 2013/04/08 22:12:59 Done.
}
// TODO(rnystrom): More stuff to test:
@@ -396,8 +508,18 @@ main() {
// - 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');
@@ -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);
}
});
});
@@ -472,21 +594,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 +646,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,

Powered by Google App Engine
This is Rietveld 408576698