Backjump on a source or description mismatch.

sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart

Index: sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart
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 c5580a901ed1204142842aef2aa577a07c13b84b..9efb562ebce68367eb5cc68bb8a32ce011d34406 100644
--- a/sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart
+++ b/sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.dart
@@ -193,27 +193,10 @@ class BacktrackingSolver {
 
     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;
-        }
+      if (failure.mayHaveTransitiveCause) {

[nweiz, 2013/04/30 22:00:29]

I don't understand this distinction. Why can't source/description mismatches be
transitively caused? If A depends on B depends on C from git, and X depends on Y
depends on C from hosted, don't we want to try rolling back A and/or X if
rolling back B and/or C fails?

[Bob Nystrom, 2013/05/01 01:06:15]

After putting on my thinking cap, I've got a cleaner solution and a better
understanding of why the current code went exponential, I think.

Removed this mayHaveTransitiveCause garbage.

+        _backjumpToDependency(failure.package);
+      } else {
+        _backjumpToPackage(failure.dependencies);
       }
 
       // Advance past the current version of the leaf-most package.
@@ -232,6 +215,47 @@ class BacktrackingSolver {
     return false;
   }
 
+  /// Backjumps to the most recently selected package in [dependencies]. Does
+  /// not consider dependent or related packages. This is used for failures
+  /// like [SourceMismatchException] where one of the packages explicitly in
+  /// that list is known to be a direct cause of the failure.
+  void _backjumpToPackage(Iterable<Dependency> dependencies) {
+    for (var i = _selected.length - 1; i >= 0; i--) {
+      var selected = _selected[i].first;
+
+      for (var dep in dependencies) {
+        if (selected.name == dep.dep.name) {
+          logSolve('backjump to ${selected.name} because it caused conflict');
+          _selected.removeRange(i + 1, _selected.length);
+          return;
+        }
+      }
+    }
+  }
+
+  /// Backjumps to the most recently selected package that directly or
+  /// indirectly depends on [package]. This is used for failures like
+  /// [NoVersionException] where we failed to find a version for [package] and
+  /// any package along the dependency graph leading to it could have caused
+  /// that failure.
+  void _backjumpToDependency(String package) {
+    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;
+
+      // See if this package directly or indirectly depends on [package].
+      var path = _getDependencyPath(selected, package);
+      if (path != null) {
+        logSolve('backjump to ${selected.name} because it depends on '
+        '${package} by $path');

[nweiz, 2013/04/30 22:00:29]

indentation

[Bob Nystrom, 2013/05/01 01:06:15]

Done.

+        _selected.removeRange(i + 1, _selected.length);
+        return;
+      }
+    }
+  }
+
   /// 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