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 174 matching lines @@
   /// Backtracks from the current failed solution and determines the next
   /// 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;
-        }
-      }
+      _backjump(failure);
 
       // 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;
   }
 
+  /// 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--) {
+      var selected = _selected[i].first;

[nweiz, 2013/05/01 01:17:52]

Might be nice to add a comment or assertion here explaining that _selected[i]
should always have at least one element.

[Bob Nystrom, 2013/05/01 01:38:57]

Done.

+
+      // 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, stop there.
+      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, try stop
+      // there.
+      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, every selection can be jumped over (except for the first
+    // root package one).
+    _selected.removeRange(1, _selected.length);

[nweiz, 2013/05/01 01:17:52]

I'm not 100% clear what's going on here. How did we make it through all of the
selected package versions without hitting any that caused [failure]?

[Bob Nystrom, 2013/05/01 01:38:57]

Added some comments.

+  }
+
   /// 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 342 matching lines @@
 /// with the current SDK. Throws a [SolverFailure] if not.
 void _validateSdkConstraint(Pubspec pubspec) {
   // If the user is running a continouous build of the SDK, just disable SDK
   // constraint checking entirely. The actual version number you get is
   // impossibly old and not correct. We'll just assume users on continuous
   // know what they're doing.
   if (sdk.isBleedingEdge) return;
 
   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}.');
 }