blob: f72bd3dd025d8cdb1c00e0b4c909f96d360ef7ac [file] [log] [blame]
// 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) {
for (var override in root.dependencyOverrides) {
_overrides[] = 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');
// Even more deeply nested pathological example.
if (javaBooleanAnd(
_isEqualTokens(node.period, toNode.period)),
_isEqualNodes(node.parameters, toNode.parameters)),
_isEqualTokens(node.separator, toNode.separator)),
_isEqualNodeLists(node.initializers, toNode.initializers)),
node.redirectedConstructor, toNode.redirectedConstructor)),
_isEqualNodes(node.body, toNode.body))) {
toNode.element = node.element;
/// 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();
// Sort the overrides by package name to make sure they're deterministic.
var overrides = _overrides.values.toList();
overrides.sort((a, b) =>;
return newFuture(() {
// Pre-cache the root package's known pubspec.
cache.cache(new PackageId.root(root), root.pubspec);
return _traverseSolution();
}).then((packages) {
var pubspecs = new Map.fromIterable(packages,
key: (id) =>, value: (id) => cache.getCachedPubspec(id));
return new SolveResult.success(
}).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.');
/// 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 = => id.version).toList();
} else {
// If the version list was never requested, just use the one known
// version.
versions = [package.version];
availableVersions[] = 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) {
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 ( == name) return new PackageId.root(root);
// Look through the current selections.
for (var i = _selected.length - 1; i >= 0; i--) {
if (_selected[i] == 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) {
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( {;
// Advance past the current version of the leaf-most package.
advanceVersion() {
var previous = _selected.last.current;
return _selected.last.advance().then((success) {
if (success) {
return true;
logSolve('$previous is last version, backtracking');
// That package has no more versions, so pop it and try the next one.
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 && == failure.package) {
logSolve("skipping past disjoint selected ${}");
if (_selected[i].hasFailed) {
logSolve('backjump to ${}');
_selected.removeRange(i + 1, _selected.length);
// 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(, () => 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(, pubspec.dependencies);
// Include the root package's dependencies.
addDependencies(, 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;
var depender = dependers[package].forEach(walk);
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(;
if (_forceLatest.contains( {
buffer.write(" (use latest)");
} else if (locked != null) {
var version = locked.version;
buffer.write(" (locked to $version)");
/// 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>>{};
/// 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();
return _solver.cache.getPubspec(id).then((pubspec) {
var deps = pubspec.dependencies.toSet();
if (id.isRoot) {
// Include dev dependencies of the root package.
// Add all overrides. This ensures a dependency only present as an
// override is still included.
// Replace any overridden dependencies.
deps = {
var override = _solver._overrides[];
if (override != null) return override;
// Not overridden.
return dep;
// 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(, [new Dependency(, 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(, 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.version, dep);
return _registerDependency(dependency).then((_) {
if ( == "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(() {
var dep = dependency.dep;
var dependencies = _getDependencies(;
var constraint = _getConstraint(;
// 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}")
_solver.logSolve('disjoint constraints on ${}:\n$constraints');
throw new DisjointConstraintException(, dependencies);
var selected = _validateSelected(dep, constraint);
if (selected != null) {
// The selected package version is good, so enqueue it to traverse
// into it.
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(;
return VersionQueue.create(locked, () {
return _getAllowedVersions(dep);
}).then((versions) => _packages.add(;
/// Gets all versions of [dep] that match the current constraints placed on
/// it.
Future<Iterable<PackageId>> _getAllowedVersions(PackageDep dep) {
var constraint = _getConstraint(;
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 ${} match $constraint');
throw new NoVersionException(, null, constraint, _getDependencies(;
// If we're doing an upgrade on this package, only allow the latest
// version.
if (_solver._forceLatest.contains( allowed = [allowed.first];
// Remove the locked version, if any, since that was already handled.
var locked = _getValidLocked(;
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(, error, _getDependencies(;
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(;
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 ${}: ${required.dep.source} '
'!= ${dep.source}');
throw new SourceMismatchException(, [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 ${}: '
'${required.dep.description} != ${dep.description}');
throw new DescriptionMismatchException(, [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(;
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(, selected.version, constraint, _getDependencies(;
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( {
var constraint = barback.pubConstraints[depName];
.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 =;
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'),
_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(,
'Package ${} requires SDK version '
'${pubspec.environment.sdkVersion} but the current SDK is '