diff --git a/benchmark/after.dart.txt b/benchmark/after.dart.txt
new file mode 100644
index 0000000..d1a2a92
--- /dev/null
+++ b/benchmark/after.dart.txt
@@ -0,0 +1,791 @@
+// 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.
+
+library pub.solver.backtracking_solver;
+
+import 'dart:async';
+import 'dart:collection' show Queue;
+
+import '../barback.dart' as barback;
+import '../exceptions.dart';
+import '../lock_file.dart';
+import '../log.dart' as log;
+import '../package.dart';
+import '../pubspec.dart';
+import '../sdk.dart' as sdk;
+import '../source_registry.dart';
+import '../source/unknown.dart';
+import '../utils.dart';
+import '../version.dart';
+import 'dependency_queue.dart';
+import 'version_queue.dart';
+import 'version_solver.dart';
+
+/// The top-level solver.
+///
+/// Keeps track of the current potential solution, and the other possible
+/// versions for speculative package selections. Backtracks and advances to the
+/// next potential solution in the case of a failure.
+class BacktrackingSolver {
+  final SolveType type;
+  final SourceRegistry sources;
+  final Package root;
+
+  /// The lockfile that was present before solving.
+  final LockFile lockFile;
+
+  final PubspecCache cache;
+
+  /// The set of packages that are being explicitly upgraded.
+  ///
+  /// The solver will only allow the very latest version for each of these
+  /// packages.
+  final _forceLatest = new Set<String>();
+
+  /// The set of packages whose dependecy is being overridden by the root
+  /// package, keyed by the name of the package.
+  ///
+  /// Any dependency on a package that appears in this map will be overriden
+  /// to use the one here.
+  final _overrides = new Map<String, PackageDep>();
+
+  /// The package versions currently selected by the solver, along with the
+  /// versions which are remaining to be tried.
+  ///
+  /// Every time a package is encountered when traversing the dependency graph,
+  /// the solver must select a version for it, sometimes when multiple versions
+  /// are valid. This keeps track of which versions have been selected so far
+  /// and which remain to be tried.
+  ///
+  /// Each entry in the list is a [VersionQueue], which is an ordered queue of
+  /// versions to try for a single package. It maintains the currently selected
+  /// version for that package. When a new dependency is encountered, a queue
+  /// of versions of that dependency is pushed onto the end of the list. A
+  /// queue is removed from the list once it's empty, indicating that none of
+  /// the versions provided a solution.
+  ///
+  /// The solver tries versions in depth-first order, so only the last queue in
+  /// the list will have items removed from it. When a new constraint is placed
+  /// on an already-selected package, and that constraint doesn't match the
+  /// selected version, that will cause the current solution to fail and
+  /// trigger backtracking.
+  final _selected = <VersionQueue>[];
+
+  /// The number of solutions the solver has tried so far.
+  int get attemptedSolutions => _attemptedSolutions;
+  var _attemptedSolutions = 1;
+
+  BacktrackingSolver(SolveType type, SourceRegistry sources, this.root,
+      this.lockFile, List<String> useLatest)
+      : type = type,
+        sources = sources,
+        cache = new PubspecCache(type, sources) {
+    for (var package in useLatest) {
+      _forceLatest.add(package);
+    }
+
+    for (var override in root.dependencyOverrides) {
+      _overrides[override.name] = override;
+    }
+
+    // A deeply nested statement that's hard on the formatter.
+    isTwoWay = !isEvent &&
+        bindings.isWhole &&
+        (isCustomTag ||
+            tag == 'input' && (name == 'value' || name == 'checked') ||
+            tag == 'select' && (name == 'selectedindex' || name == 'value') ||
+            tag == 'textarea' && name == 'value');
+  }
+
+  /// Run the solver.
+  ///
+  /// Completes with a list of specific package versions if successful or an
+  /// error if it failed to find a solution.
+  Future<SolveResult> solve() {
+    var stopwatch = new Stopwatch();
+
+    _logParameters();
+
+    // Sort the overrides by package name to make sure they're deterministic.
+    var overrides = _overrides.values.toList();
+    overrides.sort((a, b) => a.name.compareTo(b.name));
+
+    return newFuture(() {
+      stopwatch.start();
+
+      // Pre-cache the root package's known pubspec.
+      cache.cache(new PackageId.root(root), root.pubspec);
+
+      _validateSdkConstraint(root.pubspec);
+      return _traverseSolution();
+    }).then((packages) {
+      var pubspecs = new Map.fromIterable(packages,
+          key: (id) => id.name, value: (id) => cache.getCachedPubspec(id));
+
+      return new SolveResult.success(sources, root, lockFile, packages,
+          overrides, pubspecs, _getAvailableVersions(packages),
+          attemptedSolutions);
+    }).catchError((error) {
+      if (error is! SolveFailure) throw error;
+
+      // Wrap a failure in a result so we can attach some other data.
+      return new SolveResult.failure(
+          sources, root, lockFile, overrides, error, attemptedSolutions);
+    }).whenComplete(() {
+      // Gather some solving metrics.
+      var buffer = new StringBuffer();
+      buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.');
+      buffer.writeln(cache.describeResults());
+      log.solver(buffer);
+    });
+  }
+
+  /// Generates a map containing all of the known available versions for each
+  /// package in [packages].
+  ///
+  /// The version list may not always be complete. The the package is the root
+  /// root package, or its a package that we didn't unlock while solving
+  /// because we weren't trying to upgrade it, we will just know the current
+  /// version.
+  Map<String, List<Version>> _getAvailableVersions(List<PackageId> packages) {
+    var availableVersions = new Map<String, List<Version>>();
+    for (var package in packages) {
+      var cached = cache.getCachedVersions(package.toRef());
+      var versions;
+      if (cached != null) {
+        versions = cached.map((id) => id.version).toList();
+      } else {
+        // If the version list was never requested, just use the one known
+        // version.
+        versions = [package.version];
+      }
+
+      availableVersions[package.name] = versions;
+    }
+
+    return availableVersions;
+  }
+
+  /// Adds [versions], which is the list of all allowed versions of a given
+  /// package, to the set of versions to consider for solutions.
+  ///
+  /// The first item in the list will be the currently selected version of that
+  /// package. Subsequent items will be tried if it the current selection fails.
+  /// Returns the first selected version.
+  PackageId select(VersionQueue versions) {
+    _selected.add(versions);
+    logSolve();
+    return versions.current;
+  }
+
+  /// Returns the the currently selected id for the package [name] or `null` if
+  /// no concrete version has been selected for that package yet.
+  PackageId getSelected(String name) {
+    // Always prefer the root package.
+    if (root.name == name) return new PackageId.root(root);
+
+    // Look through the current selections.
+    for (var i = _selected.length - 1; i >= 0; i--) {
+      if (_selected[i].current.name == name) return _selected[i].current;
+    }
+
+    return null;
+  }
+
+  /// Gets the version of [package] currently locked in the lock file.
+  ///
+  /// Returns `null` if it isn't in the lockfile (or has been unlocked).
+  PackageId getLocked(String package) {
+    if (type == SolveType.GET) return lockFile.packages[package];
+
+    // When downgrading, we don't want to force the latest versions of
+    // non-hosted packages, since they don't support multiple versions and thus
+    // can't be downgraded.
+    if (type == SolveType.DOWNGRADE) {
+      var locked = lockFile.packages[package];
+      if (locked != null && !sources[locked.source].hasMultipleVersions) {
+        return locked;
+      }
+    }
+
+    if (_forceLatest.isEmpty || _forceLatest.contains(package)) return null;
+    return lockFile.packages[package];
+  }
+
+  /// Traverses the root package's dependency graph using the current potential
+  /// solution.
+  ///
+  /// If successful, completes to the solution. If not, backtracks to the most
+  /// recently selected version of a package and tries the next version of it.
+  /// If there are no more versions, continues to backtrack to previous
+  /// selections, and so on. If there is nothing left to backtrack to,
+  /// completes to the last failure that occurred.
+  Future<List<PackageId>> _traverseSolution() => resetStack(() {
+    return new Traverser(this).traverse().catchError((error) {
+      if (error is! SolveFailure) throw error;
+
+      return _backtrack(error).then((canTry) {
+        if (canTry) {
+          _attemptedSolutions++;
+          return _traverseSolution();
+        }
+
+        // All out of solutions, so fail.
+        throw error;
+      });
+    });
+  });
+
+  /// 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.
+  Future<bool> _backtrack(SolveFailure failure) {
+    // Bail if there is nothing to backtrack to.
+    if (_selected.isEmpty) return new Future.value(false);
+
+    // Mark any packages that may have led to this failure so that we know to
+    // consider them when backtracking.
+    var dependers = _getTransitiveDependers(failure.package);
+
+    for (var selected in _selected) {
+      if (dependers.contains(selected.current.name)) {
+        selected.fail();
+      }
+    }
+
+    // Advance past the current version of the leaf-most package.
+    advanceVersion() {
+      _backjump(failure);
+      var previous = _selected.last.current;
+      return _selected.last.advance().then((success) {
+        if (success) {
+          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();
+        if (_selected.isEmpty) return false;
+
+        // If we got here, the leafmost package was discarded so we need to
+        // advance the next one.
+        return advanceVersion();
+      });
+    }
+
+    return advanceVersion();
+  }
+
+  /// 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 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].current;
+
+      // If the failure is a disjoint version range, then no possible versions
+      // for that package can match and there's no reason to try them. Instead,
+      // just backjump past it.
+      if (failure is DisjointConstraintException &&
+          selected.name == failure.package) {
+        logSolve("skipping past disjoint selected ${selected.name}");
+        continue;
+      }
+
+      if (_selected[i].hasFailed) {
+        logSolve('backjump to ${selected.name}');
+        _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);
+  }
+
+  /// Gets the set of currently selected packages that depend on [dependency]
+  /// either directly or indirectly.
+  ///
+  /// When backtracking, it's only useful to consider changing the version of
+  /// packages who have a dependency on the failed package that triggered
+  /// backtracking. This is used to determine those packages.
+  ///
+  /// We calculate the full set up front before backtracking because during
+  /// backtracking, we will unselect packages and start to lose this
+  /// information in the middle of the process.
+  ///
+  /// For example, consider dependencies A -> B -> C. We've selected A and B
+  /// then encounter a problem with C. We start backtracking. B has no more
+  /// versions so we discard it and keep backtracking to A. When we get there,
+  /// since we've unselected B, we no longer realize that A had a transitive
+  /// dependency on C. We would end up backjumping over A and failing.
+  ///
+  /// Calculating the dependency set up front before we start backtracking
+  /// solves that.
+  Set<String> _getTransitiveDependers(String dependency) {
+    // Generate a reverse dependency graph. For each package, create edges to
+    // each package that depends on it.
+    var dependers = new Map<String, Set<String>>();
+
+    addDependencies(name, deps) {
+      dependers.putIfAbsent(name, () => new Set<String>());
+      for (var dep in deps) {
+        dependers.putIfAbsent(dep.name, () => new Set<String>()).add(name);
+      }
+    }
+
+    for (var i = 0; i < _selected.length; i++) {
+      var id = _selected[i].current;
+      var pubspec = cache.getCachedPubspec(id);
+      if (pubspec != null) addDependencies(id.name, pubspec.dependencies);
+    }
+
+    // Include the root package's dependencies.
+    addDependencies(root.name, root.immediateDependencies);
+
+    // Now walk the depending graph to see which packages transitively depend
+    // on [dependency].
+    var visited = new Set<String>();
+    walk(String package) {
+      // Don't get stuck in cycles.
+      if (visited.contains(package)) return;
+      visited.add(package);
+      var depender = dependers[package].forEach(walk);
+    }
+
+    walk(dependency);
+    return visited;
+  }
+
+  /// Logs the initial parameters to the solver.
+  void _logParameters() {
+    var buffer = new StringBuffer();
+    buffer.writeln("Solving dependencies:");
+    for (var package in root.dependencies) {
+      buffer.write("- $package");
+      var locked = getLocked(package.name);
+      if (_forceLatest.contains(package.name)) {
+        buffer.write(" (use latest)");
+      } else if (locked != null) {
+        var version = locked.version;
+        buffer.write(" (locked to $version)");
+      }
+      buffer.writeln();
+    }
+    log.solver(buffer.toString().trim());
+  }
+
+  /// Logs [message] in the context of the current selected packages.
+  ///
+  /// If [message] is omitted, just logs a description of leaf-most selection.
+  void logSolve([String message]) {
+    if (message == null) {
+      if (_selected.isEmpty) {
+        message = "* start at root";
+      } else {
+        message = "* select ${_selected.last.current}";
+      }
+    } else {
+      // Otherwise, indent it under the current selected package.
+      message = prefixLines(message);
+    }
+
+    // Indent for the previous selections.
+    var prefix = _selected.skip(1).map((_) => '| ').join();
+    log.solver(prefixLines(message, prefix: prefix));
+  }
+}
+
+/// Given the solver's current set of selected package versions, this tries to
+/// traverse the dependency graph and see if a complete set of valid versions
+/// has been chosen.
+///
+/// If it reaches a conflict, it fails and stops traversing. If it reaches a
+/// package that isn't selected, it refines the solution by adding that
+/// package's set of allowed versions to the solver and then select the best
+/// one and continuing.
+class Traverser {
+  final BacktrackingSolver _solver;
+
+  /// The queue of packages left to traverse.
+  ///
+  /// We do a breadth-first traversal using an explicit queue just to avoid the
+  /// code complexity of a recursive asynchronous traversal.
+  final _packages = new Queue<PackageId>();
+
+  /// The packages we have already traversed.
+  ///
+  /// Used to avoid traversing the same package multiple times, and to build
+  /// the complete solution results.
+  final _visited = new Set<PackageId>();
+
+  /// The dependencies visited so far in the traversal.
+  ///
+  /// For each package name (the map key) we track the list of dependencies
+  /// that other packages have placed on it so that we can calculate the
+  /// complete constraint for shared dependencies.
+  final _dependencies = <String, List<Dependency>>{};
+
+  Traverser(this._solver);
+
+  /// Walks the dependency graph starting at the root package and validates
+  /// that each reached package has a valid version selected.
+  Future<List<PackageId>> traverse() {
+    // Start at the root.
+    _packages.add(new PackageId.root(_solver.root));
+    return _traversePackage();
+  }
+
+  /// Traverses the next package in the queue.
+  ///
+  /// Completes to a list of package IDs if the traversal completed
+  /// successfully and found a solution. Completes to an error if the traversal
+  /// failed. Otherwise, recurses to the next package in the queue, etc.
+  Future<List<PackageId>> _traversePackage() {
+    if (_packages.isEmpty) {
+      // We traversed the whole graph. If we got here, we successfully found
+      // a solution.
+      return new Future<List<PackageId>>.value(_visited.toList());
+    }
+
+    var id = _packages.removeFirst();
+
+    // Don't visit the same package twice.
+    if (_visited.contains(id)) {
+      return _traversePackage();
+    }
+    _visited.add(id);
+
+    return _solver.cache.getPubspec(id).then((pubspec) {
+      _validateSdkConstraint(pubspec);
+
+      var deps = pubspec.dependencies.toSet();
+
+      if (id.isRoot) {
+        // Include dev dependencies of the root package.
+        deps.addAll(pubspec.devDependencies);
+
+        // Add all overrides. This ensures a dependency only present as an
+        // override is still included.
+        deps.addAll(_solver._overrides.values);
+      }
+
+      // Replace any overridden dependencies.
+      deps = deps.map((dep) {
+        var override = _solver._overrides[dep.name];
+        if (override != null) return override;
+
+        // Not overridden.
+        return dep;
+      }).toSet();
+
+      // Make sure the package doesn't have any bad dependencies.
+      for (var dep in deps) {
+        if (!dep.isRoot && _solver.sources[dep.source] is UnknownSource) {
+          throw new UnknownSourceException(
+              id.name, [new Dependency(id.name, id.version, dep)]);
+        }
+      }
+
+      return _traverseDeps(id, new DependencyQueue(_solver, deps));
+    }).catchError((error) {
+      if (error is! PackageNotFoundException) throw error;
+
+      // We can only get here if the lockfile refers to a specific package
+      // version that doesn't exist (probably because it was yanked).
+      throw new NoVersionException(id.name, null, id.version, []);
+    });
+  }
+
+  /// Traverses the references that [depender] depends on, stored in [deps].
+  ///
+  /// Desctructively modifies [deps]. Completes to a list of packages if the
+  /// traversal is complete. Completes it to an error if a failure occurred.
+  /// Otherwise, recurses.
+  Future<List<PackageId>> _traverseDeps(
+      PackageId depender, DependencyQueue deps) {
+    // Move onto the next package if we've traversed all of these references.
+    if (deps.isEmpty) return _traversePackage();
+
+    return resetStack(() {
+      return deps.advance().then((dep) {
+        var dependency = new Dependency(depender.name, depender.version, dep);
+        return _registerDependency(dependency).then((_) {
+          if (dep.name == "barback") return _addImplicitDependencies();
+        });
+      }).then((_) => _traverseDeps(depender, deps));
+    });
+  }
+
+  /// Register [dependency]'s constraints on the package it depends on and
+  /// enqueues the package for processing if necessary.
+  Future _registerDependency(Dependency dependency) {
+    return new Future.sync(() {
+      _validateDependency(dependency);
+
+      var dep = dependency.dep;
+      var dependencies = _getDependencies(dep.name);
+      dependencies.add(dependency);
+
+      var constraint = _getConstraint(dep.name);
+
+      // See if it's possible for a package to match that constraint.
+      if (constraint.isEmpty) {
+        var constraints = dependencies
+            .map((dep) => "  ${dep.dep.constraint} from ${dep.depender}")
+            .join('\n');
+        _solver.logSolve('disjoint constraints on ${dep.name}:\n$constraints');
+        throw new DisjointConstraintException(dep.name, dependencies);
+      }
+
+      var selected = _validateSelected(dep, constraint);
+      if (selected != null) {
+        // The selected package version is good, so enqueue it to traverse
+        // into it.
+        _packages.add(selected);
+        return null;
+      }
+
+      // We haven't selected a version. Try all of the versions that match
+      // the constraints we currently have for this package.
+      var locked = _getValidLocked(dep.name);
+
+      return VersionQueue.create(locked, () {
+        return _getAllowedVersions(dep);
+      }).then((versions) => _packages.add(_solver.select(versions)));
+    });
+  }
+
+  /// Gets all versions of [dep] that match the current constraints placed on
+  /// it.
+  Future<Iterable<PackageId>> _getAllowedVersions(PackageDep dep) {
+    var constraint = _getConstraint(dep.name);
+    return _solver.cache.getVersions(dep.toRef()).then((versions) {
+      var allowed = versions.where((id) => constraint.allows(id.version));
+
+      if (allowed.isEmpty) {
+        _solver.logSolve('no versions for ${dep.name} match $constraint');
+        throw new NoVersionException(
+            dep.name, null, constraint, _getDependencies(dep.name));
+      }
+
+      // If we're doing an upgrade on this package, only allow the latest
+      // version.
+      if (_solver._forceLatest.contains(dep.name)) allowed = [allowed.first];
+
+      // Remove the locked version, if any, since that was already handled.
+      var locked = _getValidLocked(dep.name);
+      if (locked != null) {
+        allowed = allowed.where((dep) => dep.version != locked.version);
+      }
+
+      return allowed;
+    }).catchError((error, stackTrace) {
+      if (error is PackageNotFoundException) {
+        // Show the user why the package was being requested.
+        throw new DependencyNotFoundException(
+            dep.name, error, _getDependencies(dep.name));
+      }
+
+      throw error;
+    });
+  }
+
+  /// Ensures that dependency [dep] from [depender] is consistent with the
+  /// other dependencies on the same package.
+  ///
+  /// Throws a [SolveFailure] exception if not. Only validates sources and
+  /// descriptions, not the version.
+  void _validateDependency(Dependency dependency) {
+    var dep = dependency.dep;
+
+    // Make sure the dependencies agree on source and description.
+    var required = _getRequired(dep.name);
+    if (required == null) return;
+
+    // Make sure all of the existing sources match the new reference.
+    if (required.dep.source != dep.source) {
+      _solver.logSolve(
+          'source mismatch on ${dep.name}: ${required.dep.source} ' '!= ${dep.source}');
+      throw new SourceMismatchException(dep.name, [required, dependency]);
+    }
+
+    // Make sure all of the existing descriptions match the new reference.
+    var source = _solver.sources[dep.source];
+    if (!source.descriptionsEqual(dep.description, required.dep.description)) {
+      _solver.logSolve('description mismatch on ${dep.name}: '
+          '${required.dep.description} != ${dep.description}');
+      throw new DescriptionMismatchException(dep.name, [required, dependency]);
+    }
+  }
+
+  /// Validates the currently selected package against the new dependency that
+  /// [dep] and [constraint] place on it.
+  ///
+  /// Returns `null` if there is no currently selected package, throws a
+  /// [SolveFailure] if the new reference it not does not allow the previously
+  /// selected version, or returns the selected package if successful.
+  PackageId _validateSelected(PackageDep dep, VersionConstraint constraint) {
+    var selected = _solver.getSelected(dep.name);
+    if (selected == null) return null;
+
+    // Make sure it meets the constraint.
+    if (!dep.constraint.allows(selected.version)) {
+      _solver.logSolve('selection $selected does not match $constraint');
+      throw new NoVersionException(
+          dep.name, selected.version, constraint, _getDependencies(dep.name));
+    }
+
+    return selected;
+  }
+
+  /// Register pub's implicit dependencies.
+  ///
+  /// Pub has an implicit version constraint on barback and various other
+  /// packages used in barback's plugin isolate.
+  Future _addImplicitDependencies() {
+    /// Ensure we only add the barback dependency once.
+    if (_getDependencies("barback").length != 1) return new Future.value();
+
+    return Future.wait(barback.pubConstraints.keys.map((depName) {
+      var constraint = barback.pubConstraints[depName];
+      _solver
+          .logSolve('add implicit $constraint pub dependency on ' '$depName');
+
+      var override = _solver._overrides[depName];
+
+      // Use the same source and description as the dependency override if one
+      // exists. This is mainly used by the pkgbuild tests, which use dependency
+      // overrides for all repo packages.
+      var pubDep = override == null
+          ? new PackageDep(depName, "hosted", constraint, depName)
+          : override.withConstraint(constraint);
+      return _registerDependency(
+          new Dependency("pub itself", Version.none, pubDep));
+    }));
+  }
+
+  /// Gets the list of dependencies for package [name].
+  ///
+  /// Creates an empty list if needed.
+  List<Dependency> _getDependencies(String name) {
+    return _dependencies.putIfAbsent(name, () => <Dependency>[]);
+  }
+
+  /// Gets a "required" reference to the package [name].
+  ///
+  /// This is the first non-root dependency on that package. All dependencies
+  /// on a package must agree on source and description, except for references
+  /// to the root package. This will return a reference to that "canonical"
+  /// source and description, or `null` if there is no required reference yet.
+  ///
+  /// This is required because you may have a circular dependency back onto the
+  /// root package. That second dependency won't be a root dependency and it's
+  /// *that* one that other dependencies need to agree on. In other words, you
+  /// can have a bunch of dependencies back onto the root package as long as
+  /// they all agree with each other.
+  Dependency _getRequired(String name) {
+    return _getDependencies(name).firstWhere((dep) => !dep.dep.isRoot,
+        orElse: () => null);
+  }
+
+  /// Gets the combined [VersionConstraint] currently being placed on package
+  /// [name].
+  VersionConstraint _getConstraint(String name) {
+    var constraint = _getDependencies(name)
+        .map((dep) => dep.dep.constraint)
+        .fold(VersionConstraint.any, (a, b) => a.intersect(b));
+
+    return constraint;
+  }
+
+  /// Gets the package [name] that's currently contained in the lockfile if it
+  /// meets [constraint] and has the same source and description as other
+  /// references to that package.
+  ///
+  /// Returns `null` otherwise.
+  PackageId _getValidLocked(String name) {
+    var package = _solver.getLocked(name);
+    if (package == null) return null;
+
+    var constraint = _getConstraint(name);
+    if (!constraint.allows(package.version)) {
+      _solver.logSolve('$package is locked but does not match $constraint');
+      return null;
+    } else {
+      _solver.logSolve('$package is locked');
+    }
+
+    var required = _getRequired(name);
+    if (required != null) {
+      if (package.source != required.dep.source) return null;
+
+      var source = _solver.sources[package.source];
+      if (!source.descriptionsEqual(
+          package.description, required.dep.description)) return null;
+    }
+
+    return package;
+  }
+
+  /// Run the dart2js compiler.
+  Future _doCompilation(Transform transform) {
+    var provider = new _BarbackCompilerProvider(_environment, transform,
+        generateSourceMaps: _generateSourceMaps);
+
+    // Create a "path" to the entrypoint script. The entrypoint may not actually
+    // be on disk, but this gives dart2js a root to resolve relative paths
+    // against.
+    var id = transform.primaryInput.id;
+
+    var entrypoint = _environment.graph.packages[id.package].path(id.path);
+
+    // Should have more sophisticated error-handling here. Need
+    // to report compile errors to the user in an easily visible way. Need to
+    // make sure paths in errors are mapped to the original source path so they
+    // can understand them.
+    return dart.compile(entrypoint, provider,
+        commandLineOptions: _configCommandLineOptions,
+        csp: _configBool('csp'),
+        checked: _configBool('checked'),
+        minify: _configBool('minify',
+            defaultsTo: _settings.mode == BarbackMode.RELEASE),
+        verbose: _configBool('verbose'),
+        environment: _configEnvironment,
+        packageRoot: _environment.rootPackage.path("packages"),
+        analyzeAll: _configBool('analyzeAll'),
+        suppressWarnings: _configBool('suppressWarnings'),
+        suppressHints: _configBool('suppressHints'),
+        suppressPackageWarnings: _configBool('suppressPackageWarnings',
+            defaultsTo: true),
+        terse: _configBool('terse'),
+        includeSourceMapUrls: _settings.mode != BarbackMode.RELEASE);
+  }
+}
+
+/// Ensures that if [pubspec] has an SDK constraint, then it is compatible
+/// with the current SDK.
+///
+/// Throws a [SolveFailure] if not.
+void _validateSdkConstraint(Pubspec pubspec) {
+  if (pubspec.environment.sdkVersion.allows(sdk.version)) return;
+
+  throw new BadSdkVersionException(pubspec.name,
+      'Package ${pubspec.name} requires SDK version '
+      '${pubspec.environment.sdkVersion} but the current SDK is ' '${sdk.version}.');
+}
diff --git a/benchmark/before.dart.txt b/benchmark/before.dart.txt
new file mode 100644
index 0000000..8a0e053
--- /dev/null
+++ b/benchmark/before.dart.txt
@@ -0,0 +1,815 @@
+// 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.
+
+library pub.solver.backtracking_solver;
+
+import 'dart:async';
+import 'dart:collection' show Queue;
+
+import '../barback.dart' as barback;
+import '../exceptions.dart';
+import '../lock_file.dart';
+import '../log.dart' as log;
+import '../package.dart';
+import '../pubspec.dart';
+import '../sdk.dart' as sdk;
+import '../source_registry.dart';
+import '../source/unknown.dart';
+import '../utils.dart';
+import '../version.dart';
+import 'dependency_queue.dart';
+import 'version_queue.dart';
+import 'version_solver.dart';
+
+/// The top-level solver.
+///
+/// Keeps track of the current potential solution, and the other possible
+/// versions for speculative package selections. Backtracks and advances to the
+/// next potential solution in the case of a failure.
+class BacktrackingSolver {
+  final SolveType type;
+  final SourceRegistry sources;
+  final Package root;
+
+  /// The lockfile that was present before solving.
+  final LockFile lockFile;
+
+  final PubspecCache cache;
+
+  /// The set of packages that are being explicitly upgraded.
+  ///
+  /// The solver will only allow the very latest version for each of these
+  /// packages.
+  final _forceLatest = new Set<String>();
+
+  /// The set of packages whose dependecy is being overridden by the root
+  /// package, keyed by the name of the package.
+  ///
+  /// Any dependency on a package that appears in this map will be overriden
+  /// to use the one here.
+  final _overrides = new Map<String, PackageDep>();
+
+  /// The package versions currently selected by the solver, along with the
+  /// versions which are remaining to be tried.
+  ///
+  /// Every time a package is encountered when traversing the dependency graph,
+  /// the solver must select a version for it, sometimes when multiple versions
+  /// are valid. This keeps track of which versions have been selected so far
+  /// and which remain to be tried.
+  ///
+  /// Each entry in the list is a [VersionQueue], which is an ordered queue of
+  /// versions to try for a single package. It maintains the currently selected
+  /// version for that package. When a new dependency is encountered, a queue
+  /// of versions of that dependency is pushed onto the end of the list. A
+  /// queue is removed from the list once it's empty, indicating that none of
+  /// the versions provided a solution.
+  ///
+  /// The solver tries versions in depth-first order, so only the last queue in
+  /// the list will have items removed from it. When a new constraint is placed
+  /// on an already-selected package, and that constraint doesn't match the
+  /// selected version, that will cause the current solution to fail and
+  /// trigger backtracking.
+  final _selected = <VersionQueue>[];
+
+  /// The number of solutions the solver has tried so far.
+  int get attemptedSolutions => _attemptedSolutions;
+  var _attemptedSolutions = 1;
+
+  BacktrackingSolver(SolveType type, SourceRegistry sources, this.root,
+      this.lockFile, List<String> useLatest)
+      : type = type,
+        sources = sources,
+        cache = new PubspecCache(type, sources) {
+    for (var package in useLatest) {
+      _forceLatest.add(package);
+    }
+
+    for (var override in root.dependencyOverrides) {
+      _overrides[override.name] = override;
+    }
+
+    // A deeply nested statement that's hard on the formatter.
+    isTwoWay = !isEvent && bindings.isWhole && (isCustomTag ||
+        tag == 'input' && (name == 'value' || name =='checked') ||
+        tag == 'select' && (name == 'selectedindex' || name == 'value') ||
+        tag == 'textarea' && name == 'value');
+  }
+
+  /// Run the solver.
+  ///
+  /// Completes with a list of specific package versions if successful or an
+  /// error if it failed to find a solution.
+  Future<SolveResult> solve() {
+    var stopwatch = new Stopwatch();
+
+    _logParameters();
+
+    // Sort the overrides by package name to make sure they're deterministic.
+    var overrides = _overrides.values.toList();
+    overrides.sort((a, b) => a.name.compareTo(b.name));
+
+    return newFuture(() {
+      stopwatch.start();
+
+      // Pre-cache the root package's known pubspec.
+      cache.cache(new PackageId.root(root), root.pubspec);
+
+      _validateSdkConstraint(root.pubspec);
+      return _traverseSolution();
+    }).then((packages) {
+      var pubspecs = new Map.fromIterable(
+          packages,
+          key: (id) => id.name,
+          value: (id) => cache.getCachedPubspec(id));
+
+      return new SolveResult.success(
+          sources,
+          root,
+          lockFile,
+          packages,
+          overrides,
+          pubspecs,
+          _getAvailableVersions(packages),
+          attemptedSolutions);
+    }).catchError((error) {
+      if (error is! SolveFailure) throw error;
+
+      // Wrap a failure in a result so we can attach some other data.
+      return new SolveResult.failure(
+          sources,
+          root,
+          lockFile,
+          overrides,
+          error,
+          attemptedSolutions);
+    }).whenComplete(() {
+      // Gather some solving metrics.
+      var buffer = new StringBuffer();
+      buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.');
+      buffer.writeln(cache.describeResults());
+      log.solver(buffer);
+    });
+  }
+
+  /// Generates a map containing all of the known available versions for each
+  /// package in [packages].
+  ///
+  /// The version list may not always be complete. The the package is the root
+  /// root package, or its a package that we didn't unlock while solving
+  /// because we weren't trying to upgrade it, we will just know the current
+  /// version.
+  Map<String, List<Version>> _getAvailableVersions(List<PackageId> packages) {
+    var availableVersions = new Map<String, List<Version>>();
+    for (var package in packages) {
+      var cached = cache.getCachedVersions(package.toRef());
+      var versions;
+      if (cached != null) {
+        versions = cached.map((id) => id.version).toList();
+      } else {
+        // If the version list was never requested, just use the one known
+        // version.
+        versions = [package.version];
+      }
+
+      availableVersions[package.name] = versions;
+    }
+
+    return availableVersions;
+  }
+
+  /// Adds [versions], which is the list of all allowed versions of a given
+  /// package, to the set of versions to consider for solutions.
+  ///
+  /// The first item in the list will be the currently selected version of that
+  /// package. Subsequent items will be tried if it the current selection fails.
+  /// Returns the first selected version.
+  PackageId select(VersionQueue versions) {
+    _selected.add(versions);
+    logSolve();
+    return versions.current;
+  }
+
+  /// Returns the the currently selected id for the package [name] or `null` if
+  /// no concrete version has been selected for that package yet.
+  PackageId getSelected(String name) {
+    // Always prefer the root package.
+    if (root.name == name) return new PackageId.root(root);
+
+    // Look through the current selections.
+    for (var i = _selected.length - 1; i >= 0; i--) {
+      if (_selected[i].current.name == name) return _selected[i].current;
+    }
+
+    return null;
+  }
+
+  /// Gets the version of [package] currently locked in the lock file.
+  ///
+  /// Returns `null` if it isn't in the lockfile (or has been unlocked).
+  PackageId getLocked(String package) {
+    if (type == SolveType.GET) return lockFile.packages[package];
+
+    // When downgrading, we don't want to force the latest versions of
+    // non-hosted packages, since they don't support multiple versions and thus
+    // can't be downgraded.
+    if (type == SolveType.DOWNGRADE) {
+      var locked = lockFile.packages[package];
+      if (locked != null && !sources[locked.source].hasMultipleVersions) {
+        return locked;
+      }
+    }
+
+    if (_forceLatest.isEmpty || _forceLatest.contains(package)) return null;
+    return lockFile.packages[package];
+  }
+
+  /// Traverses the root package's dependency graph using the current potential
+  /// solution.
+  ///
+  /// If successful, completes to the solution. If not, backtracks to the most
+  /// recently selected version of a package and tries the next version of it.
+  /// If there are no more versions, continues to backtrack to previous
+  /// selections, and so on. If there is nothing left to backtrack to,
+  /// completes to the last failure that occurred.
+  Future<List<PackageId>> _traverseSolution() => resetStack(() {
+    return new Traverser(this).traverse().catchError((error) {
+      if (error is! SolveFailure) throw error;
+
+      return _backtrack(error).then((canTry) {
+        if (canTry) {
+          _attemptedSolutions++;
+          return _traverseSolution();
+        }
+
+        // All out of solutions, so fail.
+        throw error;
+      });
+    });
+  });
+
+  /// 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.
+  Future<bool> _backtrack(SolveFailure failure) {
+    // Bail if there is nothing to backtrack to.
+    if (_selected.isEmpty) return new Future.value(false);
+
+    // Mark any packages that may have led to this failure so that we know to
+    // consider them when backtracking.
+    var dependers = _getTransitiveDependers(failure.package);
+
+    for (var selected in _selected) {
+      if (dependers.contains(selected.current.name)) {
+        selected.fail();
+      }
+    }
+
+    // Advance past the current version of the leaf-most package.
+    advanceVersion() {
+      _backjump(failure);
+      var previous = _selected.last.current;
+      return _selected.last.advance().then((success) {
+        if (success) {
+          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();
+        if (_selected.isEmpty) return false;
+
+        // If we got here, the leafmost package was discarded so we need to
+        // advance the next one.
+        return advanceVersion();
+      });
+    }
+
+    return advanceVersion();
+  }
+
+  /// 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 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].current;
+
+      // If the failure is a disjoint version range, then no possible versions
+      // for that package can match and there's no reason to try them. Instead,
+      // just backjump past it.
+      if (failure is DisjointConstraintException &&
+          selected.name == failure.package) {
+        logSolve("skipping past disjoint selected ${selected.name}");
+        continue;
+      }
+
+      if (_selected[i].hasFailed) {
+        logSolve('backjump to ${selected.name}');
+        _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);
+  }
+
+  /// Gets the set of currently selected packages that depend on [dependency]
+  /// either directly or indirectly.
+  ///
+  /// When backtracking, it's only useful to consider changing the version of
+  /// packages who have a dependency on the failed package that triggered
+  /// backtracking. This is used to determine those packages.
+  ///
+  /// We calculate the full set up front before backtracking because during
+  /// backtracking, we will unselect packages and start to lose this
+  /// information in the middle of the process.
+  ///
+  /// For example, consider dependencies A -> B -> C. We've selected A and B
+  /// then encounter a problem with C. We start backtracking. B has no more
+  /// versions so we discard it and keep backtracking to A. When we get there,
+  /// since we've unselected B, we no longer realize that A had a transitive
+  /// dependency on C. We would end up backjumping over A and failing.
+  ///
+  /// Calculating the dependency set up front before we start backtracking
+  /// solves that.
+  Set<String> _getTransitiveDependers(String dependency) {
+    // Generate a reverse dependency graph. For each package, create edges to
+    // each package that depends on it.
+    var dependers = new Map<String, Set<String>>();
+
+    addDependencies(name, deps) {
+      dependers.putIfAbsent(name, () => new Set<String>());
+      for (var dep in deps) {
+        dependers.putIfAbsent(dep.name, () => new Set<String>()).add(name);
+      }
+    }
+
+    for (var i = 0; i < _selected.length; i++) {
+      var id = _selected[i].current;
+      var pubspec = cache.getCachedPubspec(id);
+      if (pubspec != null) addDependencies(id.name, pubspec.dependencies);
+    }
+
+    // Include the root package's dependencies.
+    addDependencies(root.name, root.immediateDependencies);
+
+    // Now walk the depending graph to see which packages transitively depend
+    // on [dependency].
+    var visited = new Set<String>();
+    walk(String package) {
+      // Don't get stuck in cycles.
+      if (visited.contains(package)) return;
+      visited.add(package);
+      var depender = dependers[package].forEach(walk);
+    }
+
+    walk(dependency);
+    return visited;
+  }
+
+  /// Logs the initial parameters to the solver.
+  void _logParameters() {
+    var buffer = new StringBuffer();
+    buffer.writeln("Solving dependencies:");
+    for (var package in root.dependencies) {
+      buffer.write("- $package");
+      var locked = getLocked(package.name);
+      if (_forceLatest.contains(package.name)) {
+        buffer.write(" (use latest)");
+      } else if (locked != null) {
+        var version = locked.version;
+        buffer.write(" (locked to $version)");
+      }
+      buffer.writeln();
+    }
+    log.solver(buffer.toString().trim());
+  }
+
+  /// Logs [message] in the context of the current selected packages.
+  ///
+  /// If [message] is omitted, just logs a description of leaf-most selection.
+  void logSolve([String message]) {
+    if (message == null) {
+      if (_selected.isEmpty) {
+        message = "* start at root";
+      } else {
+        message = "* select ${_selected.last.current}";
+      }
+    } else {
+      // Otherwise, indent it under the current selected package.
+      message = prefixLines(message);
+    }
+
+    // Indent for the previous selections.
+    var prefix = _selected.skip(1).map((_) => '| ').join();
+    log.solver(prefixLines(message, prefix: prefix));
+  }
+}
+
+/// Given the solver's current set of selected package versions, this tries to
+/// traverse the dependency graph and see if a complete set of valid versions
+/// has been chosen.
+///
+/// If it reaches a conflict, it fails and stops traversing. If it reaches a
+/// package that isn't selected, it refines the solution by adding that
+/// package's set of allowed versions to the solver and then select the best
+/// one and continuing.
+class Traverser {
+  final BacktrackingSolver _solver;
+
+  /// The queue of packages left to traverse.
+  ///
+  /// We do a breadth-first traversal using an explicit queue just to avoid the
+  /// code complexity of a recursive asynchronous traversal.
+  final _packages = new Queue<PackageId>();
+
+  /// The packages we have already traversed.
+  ///
+  /// Used to avoid traversing the same package multiple times, and to build
+  /// the complete solution results.
+  final _visited = new Set<PackageId>();
+
+  /// The dependencies visited so far in the traversal.
+  ///
+  /// For each package name (the map key) we track the list of dependencies
+  /// that other packages have placed on it so that we can calculate the
+  /// complete constraint for shared dependencies.
+  final _dependencies = <String, List<Dependency>>{};
+
+  Traverser(this._solver);
+
+  /// Walks the dependency graph starting at the root package and validates
+  /// that each reached package has a valid version selected.
+  Future<List<PackageId>> traverse() {
+    // Start at the root.
+    _packages.add(new PackageId.root(_solver.root));
+    return _traversePackage();
+  }
+
+  /// Traverses the next package in the queue.
+  ///
+  /// Completes to a list of package IDs if the traversal completed
+  /// successfully and found a solution. Completes to an error if the traversal
+  /// failed. Otherwise, recurses to the next package in the queue, etc.
+  Future<List<PackageId>> _traversePackage() {
+    if (_packages.isEmpty) {
+      // We traversed the whole graph. If we got here, we successfully found
+      // a solution.
+      return new Future<List<PackageId>>.value(_visited.toList());
+    }
+
+    var id = _packages.removeFirst();
+
+    // Don't visit the same package twice.
+    if (_visited.contains(id)) {
+      return _traversePackage();
+    }
+    _visited.add(id);
+
+    return _solver.cache.getPubspec(id).then((pubspec) {
+      _validateSdkConstraint(pubspec);
+
+      var deps = pubspec.dependencies.toSet();
+
+      if (id.isRoot) {
+        // Include dev dependencies of the root package.
+        deps.addAll(pubspec.devDependencies);
+
+        // Add all overrides. This ensures a dependency only present as an
+        // override is still included.
+        deps.addAll(_solver._overrides.values);
+      }
+
+      // Replace any overridden dependencies.
+      deps = deps.map((dep) {
+        var override = _solver._overrides[dep.name];
+        if (override != null) return override;
+
+        // Not overridden.
+        return dep;
+      }).toSet();
+
+      // Make sure the package doesn't have any bad dependencies.
+      for (var dep in deps) {
+        if (!dep.isRoot && _solver.sources[dep.source] is UnknownSource) {
+          throw new UnknownSourceException(
+              id.name,
+              [new Dependency(id.name, id.version, dep)]);
+        }
+      }
+
+      return _traverseDeps(id, new DependencyQueue(_solver, deps));
+    }).catchError((error) {
+      if (error is! PackageNotFoundException) throw error;
+
+      // We can only get here if the lockfile refers to a specific package
+      // version that doesn't exist (probably because it was yanked).
+      throw new NoVersionException(id.name, null, id.version, []);
+    });
+  }
+
+  /// Traverses the references that [depender] depends on, stored in [deps].
+  ///
+  /// Desctructively modifies [deps]. Completes to a list of packages if the
+  /// traversal is complete. Completes it to an error if a failure occurred.
+  /// Otherwise, recurses.
+  Future<List<PackageId>> _traverseDeps(PackageId depender,
+      DependencyQueue deps) {
+    // Move onto the next package if we've traversed all of these references.
+    if (deps.isEmpty) return _traversePackage();
+
+    return resetStack(() {
+      return deps.advance().then((dep) {
+        var dependency = new Dependency(depender.name, depender.version, dep);
+        return _registerDependency(dependency).then((_) {
+          if (dep.name == "barback") return _addImplicitDependencies();
+        });
+      }).then((_) => _traverseDeps(depender, deps));
+    });
+  }
+
+  /// Register [dependency]'s constraints on the package it depends on and
+  /// enqueues the package for processing if necessary.
+  Future _registerDependency(Dependency dependency) {
+    return new Future.sync(() {
+      _validateDependency(dependency);
+
+      var dep = dependency.dep;
+      var dependencies = _getDependencies(dep.name);
+      dependencies.add(dependency);
+
+      var constraint = _getConstraint(dep.name);
+
+      // See if it's possible for a package to match that constraint.
+      if (constraint.isEmpty) {
+        var constraints = dependencies.map(
+            (dep) => "  ${dep.dep.constraint} from ${dep.depender}").join('\n');
+        _solver.logSolve('disjoint constraints on ${dep.name}:\n$constraints');
+        throw new DisjointConstraintException(dep.name, dependencies);
+      }
+
+      var selected = _validateSelected(dep, constraint);
+      if (selected != null) {
+        // The selected package version is good, so enqueue it to traverse
+        // into it.
+        _packages.add(selected);
+        return null;
+      }
+
+      // We haven't selected a version. Try all of the versions that match
+      // the constraints we currently have for this package.
+      var locked = _getValidLocked(dep.name);
+
+      return VersionQueue.create(locked, () {
+        return _getAllowedVersions(dep);
+      }).then((versions) => _packages.add(_solver.select(versions)));
+    });
+  }
+
+  /// Gets all versions of [dep] that match the current constraints placed on
+  /// it.
+  Future<Iterable<PackageId>> _getAllowedVersions(PackageDep dep) {
+    var constraint = _getConstraint(dep.name);
+    return _solver.cache.getVersions(dep.toRef()).then((versions) {
+      var allowed = versions.where((id) => constraint.allows(id.version));
+
+      if (allowed.isEmpty) {
+        _solver.logSolve('no versions for ${dep.name} match $constraint');
+        throw new NoVersionException(
+            dep.name,
+            null,
+            constraint,
+            _getDependencies(dep.name));
+      }
+
+      // If we're doing an upgrade on this package, only allow the latest
+      // version.
+      if (_solver._forceLatest.contains(dep.name)) allowed = [allowed.first];
+
+      // Remove the locked version, if any, since that was already handled.
+      var locked = _getValidLocked(dep.name);
+      if (locked != null) {
+        allowed = allowed.where((dep) => dep.version != locked.version);
+      }
+
+      return allowed;
+    }).catchError((error, stackTrace) {
+      if (error is PackageNotFoundException) {
+        // Show the user why the package was being requested.
+        throw new DependencyNotFoundException(
+            dep.name,
+            error,
+            _getDependencies(dep.name));
+      }
+
+      throw error;
+    });
+  }
+
+  /// Ensures that dependency [dep] from [depender] is consistent with the
+  /// other dependencies on the same package.
+  ///
+  /// Throws a [SolveFailure] exception if not. Only validates sources and
+  /// descriptions, not the version.
+  void _validateDependency(Dependency dependency) {
+    var dep = dependency.dep;
+
+    // Make sure the dependencies agree on source and description.
+    var required = _getRequired(dep.name);
+    if (required == null) return;
+
+    // Make sure all of the existing sources match the new reference.
+    if (required.dep.source != dep.source) {
+      _solver.logSolve(
+          'source mismatch on ${dep.name}: ${required.dep.source} ' '!= ${dep.source}');
+      throw new SourceMismatchException(dep.name, [required, dependency]);
+    }
+
+    // Make sure all of the existing descriptions match the new reference.
+    var source = _solver.sources[dep.source];
+    if (!source.descriptionsEqual(dep.description, required.dep.description)) {
+      _solver.logSolve(
+          'description mismatch on ${dep.name}: '
+              '${required.dep.description} != ${dep.description}');
+      throw new DescriptionMismatchException(dep.name, [required, dependency]);
+    }
+  }
+
+  /// Validates the currently selected package against the new dependency that
+  /// [dep] and [constraint] place on it.
+  ///
+  /// Returns `null` if there is no currently selected package, throws a
+  /// [SolveFailure] if the new reference it not does not allow the previously
+  /// selected version, or returns the selected package if successful.
+  PackageId _validateSelected(PackageDep dep, VersionConstraint constraint) {
+    var selected = _solver.getSelected(dep.name);
+    if (selected == null) return null;
+
+    // Make sure it meets the constraint.
+    if (!dep.constraint.allows(selected.version)) {
+      _solver.logSolve('selection $selected does not match $constraint');
+      throw new NoVersionException(
+          dep.name,
+          selected.version,
+          constraint,
+          _getDependencies(dep.name));
+    }
+
+    return selected;
+  }
+
+  /// Register pub's implicit dependencies.
+  ///
+  /// Pub has an implicit version constraint on barback and various other
+  /// packages used in barback's plugin isolate.
+  Future _addImplicitDependencies() {
+    /// Ensure we only add the barback dependency once.
+    if (_getDependencies("barback").length != 1) return new Future.value();
+
+    return Future.wait(barback.pubConstraints.keys.map((depName) {
+      var constraint = barback.pubConstraints[depName];
+      _solver.logSolve(
+          'add implicit $constraint pub dependency on ' '$depName');
+
+      var override = _solver._overrides[depName];
+
+      // Use the same source and description as the dependency override if one
+      // exists. This is mainly used by the pkgbuild tests, which use dependency
+      // overrides for all repo packages.
+      var pubDep = override == null ?
+          new PackageDep(depName, "hosted", constraint, depName) :
+          override.withConstraint(constraint);
+      return _registerDependency(
+          new Dependency("pub itself", Version.none, pubDep));
+    }));
+  }
+
+  /// Gets the list of dependencies for package [name].
+  ///
+  /// Creates an empty list if needed.
+  List<Dependency> _getDependencies(String name) {
+    return _dependencies.putIfAbsent(name, () => <Dependency>[]);
+  }
+
+  /// Gets a "required" reference to the package [name].
+  ///
+  /// This is the first non-root dependency on that package. All dependencies
+  /// on a package must agree on source and description, except for references
+  /// to the root package. This will return a reference to that "canonical"
+  /// source and description, or `null` if there is no required reference yet.
+  ///
+  /// This is required because you may have a circular dependency back onto the
+  /// root package. That second dependency won't be a root dependency and it's
+  /// *that* one that other dependencies need to agree on. In other words, you
+  /// can have a bunch of dependencies back onto the root package as long as
+  /// they all agree with each other.
+  Dependency _getRequired(String name) {
+    return _getDependencies(
+        name).firstWhere((dep) => !dep.dep.isRoot, orElse: () => null);
+  }
+
+  /// Gets the combined [VersionConstraint] currently being placed on package
+  /// [name].
+  VersionConstraint _getConstraint(String name) {
+    var constraint = _getDependencies(
+        name).map(
+            (dep) =>
+                dep.dep.constraint).fold(VersionConstraint.any, (a, b) => a.intersect(b));
+
+    return constraint;
+  }
+
+  /// Gets the package [name] that's currently contained in the lockfile if it
+  /// meets [constraint] and has the same source and description as other
+  /// references to that package.
+  ///
+  /// Returns `null` otherwise.
+  PackageId _getValidLocked(String name) {
+    var package = _solver.getLocked(name);
+    if (package == null) return null;
+
+    var constraint = _getConstraint(name);
+    if (!constraint.allows(package.version)) {
+      _solver.logSolve('$package is locked but does not match $constraint');
+      return null;
+    } else {
+      _solver.logSolve('$package is locked');
+    }
+
+    var required = _getRequired(name);
+    if (required != null) {
+      if (package.source != required.dep.source) return null;
+
+      var source = _solver.sources[package.source];
+      if (!source.descriptionsEqual(
+          package.description,
+          required.dep.description)) return null;
+    }
+
+    return package;
+  }
+
+  /// Run the dart2js compiler.
+  Future _doCompilation(Transform transform) {
+    var provider = new _BarbackCompilerProvider(_environment, transform,
+        generateSourceMaps: _generateSourceMaps);
+
+    // Create a "path" to the entrypoint script. The entrypoint may not actually
+    // be on disk, but this gives dart2js a root to resolve relative paths
+    // against.
+    var id = transform.primaryInput.id;
+
+    var entrypoint = _environment.graph.packages[id.package].path(id.path);
+
+    // Should have more sophisticated error-handling here. Need
+    // to report compile errors to the user in an easily visible way. Need to
+    // make sure paths in errors are mapped to the original source path so they
+    // can understand them.
+    return dart.compile(
+        entrypoint, provider,
+        commandLineOptions: _configCommandLineOptions,
+        csp: _configBool('csp'),
+        checked: _configBool('checked'),
+        minify: _configBool(
+            'minify', defaultsTo: _settings.mode == BarbackMode.RELEASE),
+        verbose: _configBool('verbose'),
+        environment: _configEnvironment,
+        packageRoot: _environment.rootPackage.path("packages"),
+        analyzeAll: _configBool('analyzeAll'),
+        suppressWarnings: _configBool('suppressWarnings'),
+        suppressHints: _configBool('suppressHints'),
+        suppressPackageWarnings: _configBool(
+            'suppressPackageWarnings', defaultsTo: true),
+        terse: _configBool('terse'),
+        includeSourceMapUrls: _settings.mode != BarbackMode.RELEASE);
+  }
+}
+
+/// Ensures that if [pubspec] has an SDK constraint, then it is compatible
+/// with the current SDK.
+///
+/// Throws a [SolveFailure] if not.
+void _validateSdkConstraint(Pubspec pubspec) {
+  if (pubspec.environment.sdkVersion.allows(sdk.version)) return;
+
+  throw new BadSdkVersionException(
+      pubspec.name,
+      'Package ${pubspec.name} requires SDK version '
+          '${pubspec.environment.sdkVersion} but the current SDK is ' '${sdk.version}.');
+}
\ No newline at end of file
diff --git a/benchmark/benchmark.dart b/benchmark/benchmark.dart
index 3ab9d48..11a3e50 100644
--- a/benchmark/benchmark.dart
+++ b/benchmark/benchmark.dart
@@ -6,11 +6,19 @@
 
 import 'dart:io';
 
+import 'package:path/path.dart' as p;
+
 import 'package:dart_style/dart_style.dart';
 
 const NUM_TRIALS = 100;
 const FORMATS_PER_TRIAL = 30;
 
+/// Note, these files use ".txt" because while they can be *parsed* correctly,
+/// they don't resolve without error. That's OK because the formatter doesn't
+/// care about that.
+final source = loadFile("before.dart.txt");
+final expected = loadFile("after.dart.txt");
+
 void main(List<String> args) {
   var best = 99999999.0;
 
@@ -20,8 +28,9 @@
     var start = new DateTime.now();
 
     // For a single benchmark, format the source multiple times.
+    var result;
     for (var j = 0; j < FORMATS_PER_TRIAL; j++) {
-      formatSource();
+      result = formatSource();
     }
 
     var elapsed = new DateTime.now()
@@ -31,6 +40,13 @@
     if (elapsed >= best) continue;
     best = elapsed;
 
+    // Sanity check to make sure the output is what we expect and to make sure
+    // the VM doesn't optimize "dead" code away.
+    if (result != expected) {
+      print("Incorrect output:\n$result");
+      exit(1);
+    }
+
     // Don't print the first run. It's always terrible since the VM hasn't
     // warmed up yet.
     if (i == 0) continue;
@@ -40,6 +56,11 @@
   printResult("Best   ", best);
 }
 
+String loadFile(String name) {
+  var path = p.join(p.dirname(p.fromUri(Platform.script)), name);
+  return new File(path).readAsStringSync();
+}
+
 void printResult(String label, double time) {
   print("$label: ${padLeft(time.toStringAsFixed(2), 4)}ms "
       "${'=' * ((time * 5).toInt())}");
@@ -54,832 +75,7 @@
   return result;
 }
 
-void formatSource() {
+String formatSource() {
   var formatter = new DartFormatter();
-  var result = formatter.format(source);
-
-  // Sanity check to make sure the output is what we expect and to make sure
-  // the VM doesn't optimize "dead" code away.
-  if (result.length != 29791) {
-    print("Incorrect output (length ${result.length}):\n$result");
-    exit(1);
-  }
+  return formatter.format(source);
 }
-
-const source = r"""
-// 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.
-
-library pub.solver.backtracking_solver;
-
-import 'dart:async';
-import 'dart:collection' show Queue;
-
-import '../barback.dart' as barback;
-import '../exceptions.dart';
-import '../lock_file.dart';
-import '../log.dart' as log;
-import '../package.dart';
-import '../pubspec.dart';
-import '../sdk.dart' as sdk;
-import '../source_registry.dart';
-import '../source/unknown.dart';
-import '../utils.dart';
-import '../version.dart';
-import 'dependency_queue.dart';
-import 'version_queue.dart';
-import 'version_solver.dart';
-
-/// The top-level solver.
-///
-/// Keeps track of the current potential solution, and the other possible
-/// versions for speculative package selections. Backtracks and advances to the
-/// next potential solution in the case of a failure.
-class BacktrackingSolver {
-  final SolveType type;
-  final SourceRegistry sources;
-  final Package root;
-
-  /// The lockfile that was present before solving.
-  final LockFile lockFile;
-
-  final PubspecCache cache;
-
-  /// The set of packages that are being explicitly upgraded.
-  ///
-  /// The solver will only allow the very latest version for each of these
-  /// packages.
-  final _forceLatest = new Set<String>();
-
-  /// The set of packages whose dependecy is being overridden by the root
-  /// package, keyed by the name of the package.
-  ///
-  /// Any dependency on a package that appears in this map will be overriden
-  /// to use the one here.
-  final _overrides = new Map<String, PackageDep>();
-
-  /// The package versions currently selected by the solver, along with the
-  /// versions which are remaining to be tried.
-  ///
-  /// Every time a package is encountered when traversing the dependency graph,
-  /// the solver must select a version for it, sometimes when multiple versions
-  /// are valid. This keeps track of which versions have been selected so far
-  /// and which remain to be tried.
-  ///
-  /// Each entry in the list is a [VersionQueue], which is an ordered queue of
-  /// versions to try for a single package. It maintains the currently selected
-  /// version for that package. When a new dependency is encountered, a queue
-  /// of versions of that dependency is pushed onto the end of the list. A
-  /// queue is removed from the list once it's empty, indicating that none of
-  /// the versions provided a solution.
-  ///
-  /// The solver tries versions in depth-first order, so only the last queue in
-  /// the list will have items removed from it. When a new constraint is placed
-  /// on an already-selected package, and that constraint doesn't match the
-  /// selected version, that will cause the current solution to fail and
-  /// trigger backtracking.
-  final _selected = <VersionQueue>[];
-
-  /// The number of solutions the solver has tried so far.
-  int get attemptedSolutions => _attemptedSolutions;
-  var _attemptedSolutions = 1;
-
-  BacktrackingSolver(SolveType type, SourceRegistry sources, this.root,
-      this.lockFile, List<String> useLatest)
-      : type = type,
-        sources = sources,
-        cache = new PubspecCache(type, sources) {
-    for (var package in useLatest) {
-      _forceLatest.add(package);
-    }
-
-    for (var override in root.dependencyOverrides) {
-      _overrides[override.name] = override;
-    }
-
-    // A deeply nested statement that's hard on the formatter.
-    isTwoWay = !isEvent && bindings.isWhole && (isCustomTag ||
-        tag == 'input' && (name == 'value' || name =='checked') ||
-        tag == 'select' && (name == 'selectedindex' || name == 'value') ||
-        tag == 'textarea' && name == 'value');
-  }
-
-  /// Run the solver.
-  ///
-  /// Completes with a list of specific package versions if successful or an
-  /// error if it failed to find a solution.
-  Future<SolveResult> solve() {
-    var stopwatch = new Stopwatch();
-
-    _logParameters();
-
-    // Sort the overrides by package name to make sure they're deterministic.
-    var overrides = _overrides.values.toList();
-    overrides.sort((a, b) => a.name.compareTo(b.name));
-
-    return newFuture(() {
-      stopwatch.start();
-
-      // Pre-cache the root package's known pubspec.
-      cache.cache(new PackageId.root(root), root.pubspec);
-
-      _validateSdkConstraint(root.pubspec);
-      return _traverseSolution();
-    }).then((packages) {
-      var pubspecs = new Map.fromIterable(
-          packages,
-          key: (id) => id.name,
-          value: (id) => cache.getCachedPubspec(id));
-
-      return new SolveResult.success(
-          sources,
-          root,
-          lockFile,
-          packages,
-          overrides,
-          pubspecs,
-          _getAvailableVersions(packages),
-          attemptedSolutions);
-    }).catchError((error) {
-      if (error is! SolveFailure) throw error;
-
-      // Wrap a failure in a result so we can attach some other data.
-      return new SolveResult.failure(
-          sources,
-          root,
-          lockFile,
-          overrides,
-          error,
-          attemptedSolutions);
-    }).whenComplete(() {
-      // Gather some solving metrics.
-      var buffer = new StringBuffer();
-      buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.');
-      buffer.writeln(cache.describeResults());
-      log.solver(buffer);
-    });
-  }
-
-  /// Generates a map containing all of the known available versions for each
-  /// package in [packages].
-  ///
-  /// The version list may not always be complete. The the package is the root
-  /// root package, or its a package that we didn't unlock while solving
-  /// because we weren't trying to upgrade it, we will just know the current
-  /// version.
-  Map<String, List<Version>> _getAvailableVersions(List<PackageId> packages) {
-    var availableVersions = new Map<String, List<Version>>();
-    for (var package in packages) {
-      var cached = cache.getCachedVersions(package.toRef());
-      var versions;
-      if (cached != null) {
-        versions = cached.map((id) => id.version).toList();
-      } else {
-        // If the version list was never requested, just use the one known
-        // version.
-        versions = [package.version];
-      }
-
-      availableVersions[package.name] = versions;
-    }
-
-    return availableVersions;
-  }
-
-  /// Adds [versions], which is the list of all allowed versions of a given
-  /// package, to the set of versions to consider for solutions.
-  ///
-  /// The first item in the list will be the currently selected version of that
-  /// package. Subsequent items will be tried if it the current selection fails.
-  /// Returns the first selected version.
-  PackageId select(VersionQueue versions) {
-    _selected.add(versions);
-    logSolve();
-    return versions.current;
-  }
-
-  /// Returns the the currently selected id for the package [name] or `null` if
-  /// no concrete version has been selected for that package yet.
-  PackageId getSelected(String name) {
-    // Always prefer the root package.
-    if (root.name == name) return new PackageId.root(root);
-
-    // Look through the current selections.
-    for (var i = _selected.length - 1; i >= 0; i--) {
-      if (_selected[i].current.name == name) return _selected[i].current;
-    }
-
-    return null;
-  }
-
-  /// Gets the version of [package] currently locked in the lock file.
-  ///
-  /// Returns `null` if it isn't in the lockfile (or has been unlocked).
-  PackageId getLocked(String package) {
-    if (type == SolveType.GET) return lockFile.packages[package];
-
-    // When downgrading, we don't want to force the latest versions of
-    // non-hosted packages, since they don't support multiple versions and thus
-    // can't be downgraded.
-    if (type == SolveType.DOWNGRADE) {
-      var locked = lockFile.packages[package];
-      if (locked != null && !sources[locked.source].hasMultipleVersions) {
-        return locked;
-      }
-    }
-
-    if (_forceLatest.isEmpty || _forceLatest.contains(package)) return null;
-    return lockFile.packages[package];
-  }
-
-  /// Traverses the root package's dependency graph using the current potential
-  /// solution.
-  ///
-  /// If successful, completes to the solution. If not, backtracks to the most
-  /// recently selected version of a package and tries the next version of it.
-  /// If there are no more versions, continues to backtrack to previous
-  /// selections, and so on. If there is nothing left to backtrack to,
-  /// completes to the last failure that occurred.
-  Future<List<PackageId>> _traverseSolution() => resetStack(() {
-    return new Traverser(this).traverse().catchError((error) {
-      if (error is! SolveFailure) throw error;
-
-      return _backtrack(error).then((canTry) {
-        if (canTry) {
-          _attemptedSolutions++;
-          return _traverseSolution();
-        }
-
-        // All out of solutions, so fail.
-        throw error;
-      });
-    });
-  });
-
-  /// 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.
-  Future<bool> _backtrack(SolveFailure failure) {
-    // Bail if there is nothing to backtrack to.
-    if (_selected.isEmpty) return new Future.value(false);
-
-    // Mark any packages that may have led to this failure so that we know to
-    // consider them when backtracking.
-    var dependers = _getTransitiveDependers(failure.package);
-
-    for (var selected in _selected) {
-      if (dependers.contains(selected.current.name)) {
-        selected.fail();
-      }
-    }
-
-    // Advance past the current version of the leaf-most package.
-    advanceVersion() {
-      _backjump(failure);
-      var previous = _selected.last.current;
-      return _selected.last.advance().then((success) {
-        if (success) {
-          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();
-        if (_selected.isEmpty) return false;
-
-        // If we got here, the leafmost package was discarded so we need to
-        // advance the next one.
-        return advanceVersion();
-      });
-    }
-
-    return advanceVersion();
-  }
-
-  /// 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 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].current;
-
-      // If the failure is a disjoint version range, then no possible versions
-      // for that package can match and there's no reason to try them. Instead,
-      // just backjump past it.
-      if (failure is DisjointConstraintException &&
-          selected.name == failure.package) {
-        logSolve("skipping past disjoint selected ${selected.name}");
-        continue;
-      }
-
-      if (_selected[i].hasFailed) {
-        logSolve('backjump to ${selected.name}');
-        _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);
-  }
-
-  /// Gets the set of currently selected packages that depend on [dependency]
-  /// either directly or indirectly.
-  ///
-  /// When backtracking, it's only useful to consider changing the version of
-  /// packages who have a dependency on the failed package that triggered
-  /// backtracking. This is used to determine those packages.
-  ///
-  /// We calculate the full set up front before backtracking because during
-  /// backtracking, we will unselect packages and start to lose this
-  /// information in the middle of the process.
-  ///
-  /// For example, consider dependencies A -> B -> C. We've selected A and B
-  /// then encounter a problem with C. We start backtracking. B has no more
-  /// versions so we discard it and keep backtracking to A. When we get there,
-  /// since we've unselected B, we no longer realize that A had a transitive
-  /// dependency on C. We would end up backjumping over A and failing.
-  ///
-  /// Calculating the dependency set up front before we start backtracking
-  /// solves that.
-  Set<String> _getTransitiveDependers(String dependency) {
-    // Generate a reverse dependency graph. For each package, create edges to
-    // each package that depends on it.
-    var dependers = new Map<String, Set<String>>();
-
-    addDependencies(name, deps) {
-      dependers.putIfAbsent(name, () => new Set<String>());
-      for (var dep in deps) {
-        dependers.putIfAbsent(dep.name, () => new Set<String>()).add(name);
-      }
-    }
-
-    for (var i = 0; i < _selected.length; i++) {
-      var id = _selected[i].current;
-      var pubspec = cache.getCachedPubspec(id);
-      if (pubspec != null) addDependencies(id.name, pubspec.dependencies);
-    }
-
-    // Include the root package's dependencies.
-    addDependencies(root.name, root.immediateDependencies);
-
-    // Now walk the depending graph to see which packages transitively depend
-    // on [dependency].
-    var visited = new Set<String>();
-    walk(String package) {
-      // Don't get stuck in cycles.
-      if (visited.contains(package)) return;
-      visited.add(package);
-      var depender = dependers[package].forEach(walk);
-    }
-
-    walk(dependency);
-    return visited;
-  }
-
-  /// Logs the initial parameters to the solver.
-  void _logParameters() {
-    var buffer = new StringBuffer();
-    buffer.writeln("Solving dependencies:");
-    for (var package in root.dependencies) {
-      buffer.write("- $package");
-      var locked = getLocked(package.name);
-      if (_forceLatest.contains(package.name)) {
-        buffer.write(" (use latest)");
-      } else if (locked != null) {
-        var version = locked.version;
-        buffer.write(" (locked to $version)");
-      }
-      buffer.writeln();
-    }
-    log.solver(buffer.toString().trim());
-  }
-
-  /// Logs [message] in the context of the current selected packages.
-  ///
-  /// If [message] is omitted, just logs a description of leaf-most selection.
-  void logSolve([String message]) {
-    if (message == null) {
-      if (_selected.isEmpty) {
-        message = "* start at root";
-      } else {
-        message = "* select ${_selected.last.current}";
-      }
-    } else {
-      // Otherwise, indent it under the current selected package.
-      message = prefixLines(message);
-    }
-
-    // Indent for the previous selections.
-    var prefix = _selected.skip(1).map((_) => '| ').join();
-    log.solver(prefixLines(message, prefix: prefix));
-  }
-}
-
-/// Given the solver's current set of selected package versions, this tries to
-/// traverse the dependency graph and see if a complete set of valid versions
-/// has been chosen.
-///
-/// If it reaches a conflict, it fails and stops traversing. If it reaches a
-/// package that isn't selected, it refines the solution by adding that
-/// package's set of allowed versions to the solver and then select the best
-/// one and continuing.
-class Traverser {
-  final BacktrackingSolver _solver;
-
-  /// The queue of packages left to traverse.
-  ///
-  /// We do a breadth-first traversal using an explicit queue just to avoid the
-  /// code complexity of a recursive asynchronous traversal.
-  final _packages = new Queue<PackageId>();
-
-  /// The packages we have already traversed.
-  ///
-  /// Used to avoid traversing the same package multiple times, and to build
-  /// the complete solution results.
-  final _visited = new Set<PackageId>();
-
-  /// The dependencies visited so far in the traversal.
-  ///
-  /// For each package name (the map key) we track the list of dependencies
-  /// that other packages have placed on it so that we can calculate the
-  /// complete constraint for shared dependencies.
-  final _dependencies = <String, List<Dependency>>{};
-
-  Traverser(this._solver);
-
-  /// Walks the dependency graph starting at the root package and validates
-  /// that each reached package has a valid version selected.
-  Future<List<PackageId>> traverse() {
-    // Start at the root.
-    _packages.add(new PackageId.root(_solver.root));
-    return _traversePackage();
-  }
-
-  /// Traverses the next package in the queue.
-  ///
-  /// Completes to a list of package IDs if the traversal completed
-  /// successfully and found a solution. Completes to an error if the traversal
-  /// failed. Otherwise, recurses to the next package in the queue, etc.
-  Future<List<PackageId>> _traversePackage() {
-    if (_packages.isEmpty) {
-      // We traversed the whole graph. If we got here, we successfully found
-      // a solution.
-      return new Future<List<PackageId>>.value(_visited.toList());
-    }
-
-    var id = _packages.removeFirst();
-
-    // Don't visit the same package twice.
-    if (_visited.contains(id)) {
-      return _traversePackage();
-    }
-    _visited.add(id);
-
-    return _solver.cache.getPubspec(id).then((pubspec) {
-      _validateSdkConstraint(pubspec);
-
-      var deps = pubspec.dependencies.toSet();
-
-      if (id.isRoot) {
-        // Include dev dependencies of the root package.
-        deps.addAll(pubspec.devDependencies);
-
-        // Add all overrides. This ensures a dependency only present as an
-        // override is still included.
-        deps.addAll(_solver._overrides.values);
-      }
-
-      // Replace any overridden dependencies.
-      deps = deps.map((dep) {
-        var override = _solver._overrides[dep.name];
-        if (override != null) return override;
-
-        // Not overridden.
-        return dep;
-      }).toSet();
-
-      // Make sure the package doesn't have any bad dependencies.
-      for (var dep in deps) {
-        if (!dep.isRoot && _solver.sources[dep.source] is UnknownSource) {
-          throw new UnknownSourceException(
-              id.name,
-              [new Dependency(id.name, id.version, dep)]);
-        }
-      }
-
-      return _traverseDeps(id, new DependencyQueue(_solver, deps));
-    }).catchError((error) {
-      if (error is! PackageNotFoundException) throw error;
-
-      // We can only get here if the lockfile refers to a specific package
-      // version that doesn't exist (probably because it was yanked).
-      throw new NoVersionException(id.name, null, id.version, []);
-    });
-  }
-
-  /// Traverses the references that [depender] depends on, stored in [deps].
-  ///
-  /// Desctructively modifies [deps]. Completes to a list of packages if the
-  /// traversal is complete. Completes it to an error if a failure occurred.
-  /// Otherwise, recurses.
-  Future<List<PackageId>> _traverseDeps(PackageId depender,
-      DependencyQueue deps) {
-    // Move onto the next package if we've traversed all of these references.
-    if (deps.isEmpty) return _traversePackage();
-
-    return resetStack(() {
-      return deps.advance().then((dep) {
-        var dependency = new Dependency(depender.name, depender.version, dep);
-        return _registerDependency(dependency).then((_) {
-          if (dep.name == "barback") return _addImplicitDependencies();
-        });
-      }).then((_) => _traverseDeps(depender, deps));
-    });
-  }
-
-  /// Register [dependency]'s constraints on the package it depends on and
-  /// enqueues the package for processing if necessary.
-  Future _registerDependency(Dependency dependency) {
-    return new Future.sync(() {
-      _validateDependency(dependency);
-
-      var dep = dependency.dep;
-      var dependencies = _getDependencies(dep.name);
-      dependencies.add(dependency);
-
-      var constraint = _getConstraint(dep.name);
-
-      // See if it's possible for a package to match that constraint.
-      if (constraint.isEmpty) {
-        var constraints = dependencies.map(
-            (dep) => "  ${dep.dep.constraint} from ${dep.depender}").join('\n');
-        _solver.logSolve('disjoint constraints on ${dep.name}:\n$constraints');
-        throw new DisjointConstraintException(dep.name, dependencies);
-      }
-
-      var selected = _validateSelected(dep, constraint);
-      if (selected != null) {
-        // The selected package version is good, so enqueue it to traverse
-        // into it.
-        _packages.add(selected);
-        return null;
-      }
-
-      // We haven't selected a version. Try all of the versions that match
-      // the constraints we currently have for this package.
-      var locked = _getValidLocked(dep.name);
-
-      return VersionQueue.create(locked, () {
-        return _getAllowedVersions(dep);
-      }).then((versions) => _packages.add(_solver.select(versions)));
-    });
-  }
-
-  /// Gets all versions of [dep] that match the current constraints placed on
-  /// it.
-  Future<Iterable<PackageId>> _getAllowedVersions(PackageDep dep) {
-    var constraint = _getConstraint(dep.name);
-    return _solver.cache.getVersions(dep.toRef()).then((versions) {
-      var allowed = versions.where((id) => constraint.allows(id.version));
-
-      if (allowed.isEmpty) {
-        _solver.logSolve('no versions for ${dep.name} match $constraint');
-        throw new NoVersionException(
-            dep.name,
-            null,
-            constraint,
-            _getDependencies(dep.name));
-      }
-
-      // If we're doing an upgrade on this package, only allow the latest
-      // version.
-      if (_solver._forceLatest.contains(dep.name)) allowed = [allowed.first];
-
-      // Remove the locked version, if any, since that was already handled.
-      var locked = _getValidLocked(dep.name);
-      if (locked != null) {
-        allowed = allowed.where((dep) => dep.version != locked.version);
-      }
-
-      return allowed;
-    }).catchError((error, stackTrace) {
-      if (error is PackageNotFoundException) {
-        // Show the user why the package was being requested.
-        throw new DependencyNotFoundException(
-            dep.name,
-            error,
-            _getDependencies(dep.name));
-      }
-
-      throw error;
-    });
-  }
-
-  /// Ensures that dependency [dep] from [depender] is consistent with the
-  /// other dependencies on the same package.
-  ///
-  /// Throws a [SolveFailure] exception if not. Only validates sources and
-  /// descriptions, not the version.
-  void _validateDependency(Dependency dependency) {
-    var dep = dependency.dep;
-
-    // Make sure the dependencies agree on source and description.
-    var required = _getRequired(dep.name);
-    if (required == null) return;
-
-    // Make sure all of the existing sources match the new reference.
-    if (required.dep.source != dep.source) {
-      _solver.logSolve(
-          'source mismatch on ${dep.name}: ${required.dep.source} ' '!= ${dep.source}');
-      throw new SourceMismatchException(dep.name, [required, dependency]);
-    }
-
-    // Make sure all of the existing descriptions match the new reference.
-    var source = _solver.sources[dep.source];
-    if (!source.descriptionsEqual(dep.description, required.dep.description)) {
-      _solver.logSolve(
-          'description mismatch on ${dep.name}: '
-              '${required.dep.description} != ${dep.description}');
-      throw new DescriptionMismatchException(dep.name, [required, dependency]);
-    }
-  }
-
-  /// Validates the currently selected package against the new dependency that
-  /// [dep] and [constraint] place on it.
-  ///
-  /// Returns `null` if there is no currently selected package, throws a
-  /// [SolveFailure] if the new reference it not does not allow the previously
-  /// selected version, or returns the selected package if successful.
-  PackageId _validateSelected(PackageDep dep, VersionConstraint constraint) {
-    var selected = _solver.getSelected(dep.name);
-    if (selected == null) return null;
-
-    // Make sure it meets the constraint.
-    if (!dep.constraint.allows(selected.version)) {
-      _solver.logSolve('selection $selected does not match $constraint');
-      throw new NoVersionException(
-          dep.name,
-          selected.version,
-          constraint,
-          _getDependencies(dep.name));
-    }
-
-    return selected;
-  }
-
-  /// Register pub's implicit dependencies.
-  ///
-  /// Pub has an implicit version constraint on barback and various other
-  /// packages used in barback's plugin isolate.
-  Future _addImplicitDependencies() {
-    /// Ensure we only add the barback dependency once.
-    if (_getDependencies("barback").length != 1) return new Future.value();
-
-    return Future.wait(barback.pubConstraints.keys.map((depName) {
-      var constraint = barback.pubConstraints[depName];
-      _solver.logSolve(
-          'add implicit $constraint pub dependency on ' '$depName');
-
-      var override = _solver._overrides[depName];
-
-      // Use the same source and description as the dependency override if one
-      // exists. This is mainly used by the pkgbuild tests, which use dependency
-      // overrides for all repo packages.
-      var pubDep = override == null ?
-          new PackageDep(depName, "hosted", constraint, depName) :
-          override.withConstraint(constraint);
-      return _registerDependency(
-          new Dependency("pub itself", Version.none, pubDep));
-    }));
-  }
-
-  /// Gets the list of dependencies for package [name].
-  ///
-  /// Creates an empty list if needed.
-  List<Dependency> _getDependencies(String name) {
-    return _dependencies.putIfAbsent(name, () => <Dependency>[]);
-  }
-
-  /// Gets a "required" reference to the package [name].
-  ///
-  /// This is the first non-root dependency on that package. All dependencies
-  /// on a package must agree on source and description, except for references
-  /// to the root package. This will return a reference to that "canonical"
-  /// source and description, or `null` if there is no required reference yet.
-  ///
-  /// This is required because you may have a circular dependency back onto the
-  /// root package. That second dependency won't be a root dependency and it's
-  /// *that* one that other dependencies need to agree on. In other words, you
-  /// can have a bunch of dependencies back onto the root package as long as
-  /// they all agree with each other.
-  Dependency _getRequired(String name) {
-    return _getDependencies(
-        name).firstWhere((dep) => !dep.dep.isRoot, orElse: () => null);
-  }
-
-  /// Gets the combined [VersionConstraint] currently being placed on package
-  /// [name].
-  VersionConstraint _getConstraint(String name) {
-    var constraint = _getDependencies(
-        name).map(
-            (dep) =>
-                dep.dep.constraint).fold(VersionConstraint.any, (a, b) => a.intersect(b));
-
-    return constraint;
-  }
-
-  /// Gets the package [name] that's currently contained in the lockfile if it
-  /// meets [constraint] and has the same source and description as other
-  /// references to that package.
-  ///
-  /// Returns `null` otherwise.
-  PackageId _getValidLocked(String name) {
-    var package = _solver.getLocked(name);
-    if (package == null) return null;
-
-    var constraint = _getConstraint(name);
-    if (!constraint.allows(package.version)) {
-      _solver.logSolve('$package is locked but does not match $constraint');
-      return null;
-    } else {
-      _solver.logSolve('$package is locked');
-    }
-
-    var required = _getRequired(name);
-    if (required != null) {
-      if (package.source != required.dep.source) return null;
-
-      var source = _solver.sources[package.source];
-      if (!source.descriptionsEqual(
-          package.description,
-          required.dep.description)) return null;
-    }
-
-    return package;
-  }
-
-  /// Run the dart2js compiler.
-  Future _doCompilation(Transform transform) {
-    var provider = new _BarbackCompilerProvider(_environment, transform,
-        generateSourceMaps: _generateSourceMaps);
-
-    // Create a "path" to the entrypoint script. The entrypoint may not actually
-    // be on disk, but this gives dart2js a root to resolve relative paths
-    // against.
-    var id = transform.primaryInput.id;
-
-    var entrypoint = _environment.graph.packages[id.package].path(id.path);
-
-    // Should have more sophisticated error-handling here. Need
-    // to report compile errors to the user in an easily visible way. Need to
-    // make sure paths in errors are mapped to the original source path so they
-    // can understand them.
-    return dart.compile(
-        entrypoint, provider,
-        commandLineOptions: _configCommandLineOptions,
-        csp: _configBool('csp'),
-        checked: _configBool('checked'),
-        minify: _configBool(
-            'minify', defaultsTo: _settings.mode == BarbackMode.RELEASE),
-        verbose: _configBool('verbose'),
-        environment: _configEnvironment,
-        packageRoot: _environment.rootPackage.path("packages"),
-        analyzeAll: _configBool('analyzeAll'),
-        suppressWarnings: _configBool('suppressWarnings'),
-        suppressHints: _configBool('suppressHints'),
-        suppressPackageWarnings: _configBool(
-            'suppressPackageWarnings', defaultsTo: true),
-        terse: _configBool('terse'),
-        includeSourceMapUrls: _settings.mode != BarbackMode.RELEASE);
-  }
-}
-
-/// Ensures that if [pubspec] has an SDK constraint, then it is compatible
-/// with the current SDK.
-///
-/// Throws a [SolveFailure] if not.
-void _validateSdkConstraint(Pubspec pubspec) {
-  if (pubspec.environment.sdkVersion.allows(sdk.version)) return;
-
-  throw new BadSdkVersionException(
-      pubspec.name,
-      'Package ${pubspec.name} requires SDK version '
-          '${pubspec.environment.sdkVersion} but the current SDK is ' '${sdk.version}.');
-}
-""";