Backjump on a source or description mismatch.

sdk/lib/_internal/pub/lib/src/solver/backtracking_solver.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.
 
 /// A back-tracking depth-first solver. Attempts to find the best solution for
 /// a root package's transitive dependency graph, where a "solution" is a set
 /// of concrete package versions. A valid solution will select concrete
 /// versions for every package reached from the root package's dependency graph,
 /// and each of those packages will fit the version constraints placed on it.
 ///
@@ skipping 175 matching lines @@
   /// solution to try. If possible, it will backjump based on the cause of the
   /// [failure] to minize backtracking. Otherwise, it will simply backtrack to
   /// the next possible solution.
   ///
   /// Returns `true` if there is a new solution to try.
   bool _backtrack(SolveFailure failure) {
     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;
-        }
+      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.
       var previous = _selected.last.removeFirst();
       if (!_selected.last.isEmpty) {
         logSolve();
         return true;
       }
 
       logSolve('$previous is last version, backtracking');
 
       // That package has no more versions, so pop it and try the next one.
       _selected.removeLast();
     }
 
     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
   /// there is no dependency.
   String _getDependencyPath(PackageId depender, String dependent) {
     // TODO(rnystrom): This is O(n^2) where n is the number of selected
     // packages. Could store the reverse dependency graph to address that. If
     // we do that, we need to make sure it gets correctly rolled back when
     // backtracking occurs.
     var visited = new Set<String>();
@@ skipping 347 matching lines @@
   // know what they're doing.
   if (sdk.isBleedingEdge) return;
 
   if (pubspec.environment.sdkVersion.allows(sdk.version)) return;
 
   throw new CouldNotSolveException(
       'Package ${pubspec.name} requires SDK version '
       '${pubspec.environment.sdkVersion} but the current SDK is '
       '${sdk.version}.');
 }