Backjump on a source or description mismatch.
BUG=https://code.google.com/p/dart/issues/detail?id=10229
R=nweiz@google.com
Review URL: https://codereview.chromium.org//14685002
git-svn-id: https://dart.googlecode.com/svn/branches/bleeding_edge/dart@22220 260f80e4-7a28-3924-810f-c04153c831b5
diff --git a/sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart b/sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart
index 69230e7..efb6fba 100644
--- a/sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart
+++ b/sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart
@@ -192,29 +192,7 @@
var dependers = failure.dependencies.map((dep) => dep.depender).toSet();
while (!_selected.isEmpty) {
- // Look for a relevant selection to jump back to.
- for (var i = _selected.length - 1; i >= 0; i--) {
- // Can't jump to a package that has no more alternatives.
- if (_selected[i].length == 1) continue;
-
- var selected = _selected[i].first;
-
- // If we find the package itself that failed, jump to it.
- if (selected.name == failure.package) {
- logSolve('jump to selected package ${failure.package}');
- _selected.removeRange(i + 1, _selected.length);
- break;
- }
-
- // See if this package directly or indirectly depends on [package].
- var path = _getDependencyPath(selected, failure.package);
- if (path != null) {
- logSolve('backjump to ${selected.name} because it depends on '
- '${failure.package} by $path');
- _selected.removeRange(i + 1, _selected.length);
- break;
- }
- }
+ _backjump(failure);
// Advance past the current version of the leaf-most package.
var previous = _selected.last.removeFirst();
@@ -232,6 +210,44 @@
return false;
}
+ /// Walks the selected packages from most to least recent to determine which
+ /// ones can be ignored and jumped over by the backtracker. The only packages
+ /// we need to backtrack to are ones that have other versions to try and that
+ /// led (possibly indirectly) to the failure. Everything else can be skipped.
+ void _backjump(SolveFailure failure) {
+ for (var i = _selected.length - 1; i >= 0; i--) {
+ // Each queue will never be empty since it gets discarded by _backtrack()
+ // when that happens.
+ var selected = _selected[i].first;
+
+ // If the package has no more versions, we can jump over it.
+ if (_selected[i].length == 1) continue;
+
+ // If we get to the package that failed, backtrack to here.
+ if (selected.name == failure.package) {
+ logSolve('backjump to failed package ${selected.name}');
+ _selected.removeRange(i + 1, _selected.length);
+ return;
+ }
+
+ // If we get to a package that depends on the failing package, backtrack
+ // to here.
+ var path = _getDependencyPath(selected, failure.package);
+ if (path != null) {
+ logSolve('backjump to ${selected.name} because it depends on '
+ '${failure.package} along $path');
+ _selected.removeRange(i + 1, _selected.length);
+ return;
+ }
+ }
+
+ // If we got here, we walked the entire list without finding a package that
+ // could lead to another solution, so discard everything. This will happen
+ // if every package that led to the failure has no other versions that it
+ // can try to select.
+ _selected.removeRange(1, _selected.length);
+ }
+
/// Determines if [depender] has a direct or indirect dependency on
/// [dependent] based on the currently selected versions of all packages.
/// Returns a string describing the dependency chain if it does, or `null` if
@@ -592,7 +608,7 @@
if (pubspec.environment.sdkVersion.allows(sdk.version)) return;
- throw new CouldNotSolveException(
+ throw new BadSdkVersionException(pubspec.name,
'Package ${pubspec.name} requires SDK version '
'${pubspec.environment.sdkVersion} but the current SDK is '
'${sdk.version}.');
diff --git a/sdk/lib/_internal/pub/lib/src/solver/version_solver.dart b/sdk/lib/_internal/pub/lib/src/solver/version_solver.dart
index efd9e85..885acdc 100644
--- a/sdk/lib/_internal/pub/lib/src/solver/version_solver.dart
+++ b/sdk/lib/_internal/pub/lib/src/solver/version_solver.dart
@@ -218,13 +218,12 @@
"depends on version ${dep.constraint}";
}
-/// Exception thrown when the [VersionSolver] fails to find a solution after a
-/// certain number of iterations.
-class CouldNotSolveException extends SolveFailure {
- CouldNotSolveException([String message])
- : super(null, null),
- _message = (message != null) ? message :
- "Could not find a solution that met all constraints.";
+/// Exception thrown when the current SDK's version does not match a package's
+/// constraint on it.
+class BadSdkVersionException extends SolveFailure {
+ BadSdkVersionException(String package, String message)
+ : super(package, null),
+ _message = message;
/// A message describing the specific kind of solve failure.
final String _message;
diff --git a/sdk/lib/_internal/pub/test/version_solver_test.dart b/sdk/lib/_internal/pub/test/version_solver_test.dart
index 6c2cb22..35af3ac 100644
--- a/sdk/lib/_internal/pub/test/version_solver_test.dart
+++ b/sdk/lib/_internal/pub/test/version_solver_test.dart
@@ -10,6 +10,7 @@
import 'package:unittest/unittest.dart';
import '../lib/src/lock_file.dart';
+import '../lib/src/log.dart' as log;
import '../lib/src/package.dart';
import '../lib/src/pubspec.dart';
import '../lib/src/sdk.dart' as sdk;
@@ -27,6 +28,9 @@
main() {
initConfig();
+ // Uncomment this to debug failing tests.
+ // log.showSolver();
+
// Since this test isn't run from the SDK, it can't find the "version" file
// to load. Instead, just manually inject a version.
sdk.version = new Version(1, 2, 3);
@@ -484,6 +488,111 @@
'c': '1.0.0'
}, maxTries: 2);
+ // Tests that the backjumper will jump past unrelated selections when a
+ // source conflict occurs. This test selects, in order:
+ // - myapp -> a
+ // - myapp -> b
+ // - myapp -> c (1 of 5)
+ // - b -> a
+ // It selects a and b first because they have fewer versions than c. It
+ // traverses b's dependency on a after selecting a version of c because
+ // dependencies are traversed breadth-first (all of myapps's immediate deps
+ // before any other their deps).
+ //
+ // This means it doesn't discover the source conflict until after selecting
+ // c. When that happens, it should backjump past c instead of trying older
+ // versions of it since they aren't related to the conflict.
+ testResolve('backjump to conflicting source', {
+ 'myapp 0.0.0': {
+ 'a': 'any',
+ 'b': 'any',
+ 'c': 'any'
+ },
+ 'a 1.0.0': {},
+ 'a 1.0.0 from mock2': {},
+ 'b 1.0.0': {
+ 'a': 'any'
+ },
+ 'b 2.0.0': {
+ 'a from mock2': 'any'
+ },
+ 'c 1.0.0': {},
+ 'c 2.0.0': {},
+ 'c 3.0.0': {},
+ 'c 4.0.0': {},
+ 'c 5.0.0': {},
+ }, result: {
+ 'myapp from root': '0.0.0',
+ 'a': '1.0.0',
+ 'b': '1.0.0',
+ 'c': '5.0.0'
+ }, maxTries: 2);
+
+ // Like the above test, but for a conflicting description.
+ testResolve('backjump to conflicting description', {
+ 'myapp 0.0.0': {
+ 'a-x': 'any',
+ 'b': 'any',
+ 'c': 'any'
+ },
+ 'a-x 1.0.0': {},
+ 'a-y 1.0.0': {},
+ 'b 1.0.0': {
+ 'a-x': 'any'
+ },
+ 'b 2.0.0': {
+ 'a-y': 'any'
+ },
+ 'c 1.0.0': {},
+ 'c 2.0.0': {},
+ 'c 3.0.0': {},
+ 'c 4.0.0': {},
+ 'c 5.0.0': {},
+ }, result: {
+ 'myapp from root': '0.0.0',
+ 'a': '1.0.0',
+ 'b': '1.0.0',
+ 'c': '5.0.0'
+ }, maxTries: 2);
+
+ // Similar to the above two tests but where there is no solution. It should
+ // fail in this case with no backtracking.
+ testResolve('backjump to conflicting source', {
+ 'myapp 0.0.0': {
+ 'a': 'any',
+ 'b': 'any',
+ 'c': 'any'
+ },
+ 'a 1.0.0': {},
+ 'a 1.0.0 from mock2': {},
+ 'b 1.0.0': {
+ 'a from mock2': 'any'
+ },
+ 'c 1.0.0': {},
+ 'c 2.0.0': {},
+ 'c 3.0.0': {},
+ 'c 4.0.0': {},
+ 'c 5.0.0': {},
+ }, error: sourceMismatch('myapp', 'b'), maxTries: 1);
+
+ testResolve('backjump to conflicting description', {
+ 'myapp 0.0.0': {
+ 'a-x': 'any',
+ 'b': 'any',
+ 'c': 'any'
+ },
+ 'a-x 1.0.0': {},
+ 'a-y 1.0.0': {},
+ 'b 1.0.0': {
+ 'a-y': 'any'
+ },
+ 'c 1.0.0': {},
+ 'c 2.0.0': {},
+ 'c 3.0.0': {},
+ 'c 4.0.0': {},
+ 'c 5.0.0': {},
+ }, error: descriptionMismatch('myapp', 'b'), maxTries: 1);
+
// Dependencies are ordered so that packages with fewer versions are tried
// first. Here, there are two valid solutions (either a or b must be
// downgraded once). The chosen one depends on which dep is traversed first.
@@ -619,13 +728,31 @@
}, useBleedingEdgeSdkVersion: true);
}
-testResolve(description, packages,
- {lockfile, result, FailMatcherBuilder error, int maxTries,
+testResolve(description, packages, {
+ lockfile, result, FailMatcherBuilder error, int maxTries,
+ bool useBleedingEdgeSdkVersion}) {
+ _testResolve(test, description, packages, lockfile: lockfile, result: result,
+ error: error, maxTries: maxTries,
+ useBleedingEdgeSdkVersion: useBleedingEdgeSdkVersion);
+}
+
+solo_testResolve(description, packages, {
+ lockfile, result, FailMatcherBuilder error, int maxTries,
+ bool useBleedingEdgeSdkVersion}) {
+ log.showSolver();
+ _testResolve(solo_test, description, packages, lockfile: lockfile,
+ result: result, error: error, maxTries: maxTries,
+ useBleedingEdgeSdkVersion: useBleedingEdgeSdkVersion);
+}
+
+_testResolve(void testFn(String description, Function body),
+ description, packages, {
+ lockfile, result, FailMatcherBuilder error, int maxTries,
bool useBleedingEdgeSdkVersion}) {
if (maxTries == null) maxTries = 1;
if (useBleedingEdgeSdkVersion == null) useBleedingEdgeSdkVersion = false;
- test(description, () {
+ testFn(description, () {
var cache = new SystemCache('.');
source1 = new MockSource('mock1');
source2 = new MockSource('mock2');
