| // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| /// A back-tracking depth-first solver. Attempts to find the best solution for |
| /// a root package's transitive dependency graph, where a "solution" is a set |
| /// of concrete package versions. A valid solution will select concrete |
| /// versions for every package reached from the root package's dependency graph, |
| /// and each of those packages will fit the version constraints placed on it. |
| /// |
| /// The solver builds up a solution incrementally by traversing the dependency |
| /// graph starting at the root package. When it reaches a new package, it gets |
| /// the set of versions that meet the current constraint placed on it. It |
| /// *speculatively* selects one version from that set and adds it to the |
| /// current solution and then proceeds. If it fully traverses the dependency |
| /// graph, the solution is valid and it stops. |
| /// |
| /// If it reaches an error because: |
| /// |
| /// - A new dependency is placed on a package that's already been selected in |
| /// the solution and the selected version doesn't match the new constraint. |
| /// |
| /// - There are no versions available that meet the constraint placed on a |
| /// package. |
| /// |
| /// - etc. |
| /// |
| /// then the current solution is invalid. It will then backtrack to the most |
| /// recent speculative version choice and try the next one. That becomes the |
| /// new in-progress solution and it tries to proceed from there. It will keep |
| /// doing this, traversing and then backtracking when it meets a failure until |
| /// a valid solution has been found or until all possible options for all |
| /// speculative choices have been exhausted. |
| library solver.backtracking_solver; |
| |
| import 'dart:async'; |
| import 'dart:collection' show Queue; |
| |
| import '../lock_file.dart'; |
| import '../log.dart' as log; |
| import '../package.dart'; |
| import '../pubspec.dart'; |
| import '../sdk.dart' as sdk; |
| import '../source.dart'; |
| import '../source_registry.dart'; |
| import '../utils.dart'; |
| import '../version.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 SourceRegistry sources; |
| final Package root; |
| final LockFile lockFile; |
| final PubspecCache cache; |
| |
| /// The set of packages that are being explicitly updated. The solver will |
| /// only allow the very latest version for each of these packages. |
| final _forceLatest = new Set<String>(); |
| |
| /// 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 an ordered [Queue] of versions to try for a |
| /// single package. The first item in the queue is 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 = <Queue<PackageId>>[]; |
| |
| /// The number of solutions the solver has tried so far. |
| int get attemptedSolutions => _attemptedSolutions; |
| var _attemptedSolutions = 1; |
| |
| BacktrackingSolver(SourceRegistry sources, this.root, this.lockFile, |
| List<String> useLatest) |
| : sources = sources, |
| cache = new PubspecCache(sources) { |
| for (var package in useLatest) { |
| forceLatestVersion(package); |
| lockFile.packages.remove(package); |
| } |
| } |
| |
| /// 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(); |
| |
| return new Future(() { |
| 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) { |
| return new SolveResult(packages, null, 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(null, error, attemptedSolutions); |
| }).whenComplete(() { |
| // Gather some solving metrics. |
| var buffer = new StringBuffer(); |
| buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.'); |
| buffer.writeln( |
| '- Requested ${cache.versionCacheMisses} version lists'); |
| buffer.writeln( |
| '- Looked up ${cache.versionCacheHits} cached version lists'); |
| buffer.writeln( |
| '- Requested ${cache.pubspecCacheMisses} pubspecs'); |
| buffer.writeln( |
| '- Looked up ${cache.pubspecCacheHits} cached pubspecs'); |
| log.solver(buffer); |
| }); |
| } |
| |
| void forceLatestVersion(String package) { |
| _forceLatest.add(package); |
| } |
| |
| /// 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(Iterable<PackageId> versions) { |
| _selected.add(new Queue<PackageId>.from(versions)); |
| logSolve(); |
| return versions.first; |
| } |
| |
| /// 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].first.name == name) return _selected[i].first; |
| } |
| |
| 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) => 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; |
| |
| if (_backtrack(error)) { |
| _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. |
| bool _backtrack(SolveFailure failure) { |
| var dependers = failure.dependencies.map((dep) => dep.depender).toSet(); |
| |
| while (!_selected.isEmpty) { |
| _backjump(failure); |
| |
| // Advance past the current version of the leaf-most package. |
| var previous = _selected.last.removeFirst(); |
| if (!_selected.last.isEmpty) { |
| logSolve(); |
| return true; |
| } |
| |
| logSolve('$previous is last version, backtracking'); |
| |
| // That package has no more versions, so pop it and try the next one. |
| _selected.removeLast(); |
| } |
| |
| return false; |
| } |
| |
| /// Walks the selected packages from most to least recent to determine which |
| /// ones can be ignored and jumped over by the backtracker. The only packages |
| /// we need to backtrack to are ones that have other versions to try and that |
| /// led (possibly indirectly) to the failure. Everything else can be skipped. |
| void _backjump(SolveFailure failure) { |
| for (var i = _selected.length - 1; i >= 0; i--) { |
| // Each queue will never be empty since it gets discarded by _backtrack() |
| // when that happens. |
| var selected = _selected[i].first; |
| |
| // If the package has no more versions, we can jump over it. |
| if (_selected[i].length == 1) continue; |
| |
| // If we get to the package that failed, backtrack to here. |
| if (selected.name == failure.package) { |
| logSolve('backjump to failed package ${selected.name}'); |
| _selected.removeRange(i + 1, _selected.length); |
| return; |
| } |
| |
| // If we get to a package that depends on the failing package, backtrack |
| // to here. |
| var path = _getDependencyPath(selected, failure.package); |
| if (path != null) { |
| logSolve('backjump to ${selected.name} because it depends on ' |
| '${failure.package} along $path'); |
| _selected.removeRange(i + 1, _selected.length); |
| return; |
| } |
| } |
| |
| // If we got here, 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); |
| } |
| |
| /// Determines if [depender] has a direct or indirect dependency on |
| /// [dependent] based on the currently selected versions of all packages. |
| /// Returns a string describing the dependency chain if it does, or `null` if |
| /// there is no dependency. |
| String _getDependencyPath(PackageId depender, String dependent) { |
| // TODO(rnystrom): This is O(n^2) where n is the number of selected |
| // packages. Could store the reverse dependency graph to address that. If |
| // we do that, we need to make sure it gets correctly rolled back when |
| // backtracking occurs. |
| var visited = new Set<String>(); |
| |
| walkDeps(PackageId package, String currentPath) { |
| if (visited.contains(package.name)) return null; |
| visited.add(package.name); |
| |
| var pubspec = cache.getCachedPubspec(package); |
| if (pubspec == null) return null; |
| |
| for (var dep in pubspec.dependencies) { |
| if (dep.name == dependent) return currentPath; |
| |
| var selected = getSelected(dep.name); |
| // Ignore unselected dependencies. We haven't traversed into them yet, |
| // so they can't affect backjumping. |
| if (selected == null) continue; |
| |
| var depPath = walkDeps(selected, '$currentPath -> ${dep.name}'); |
| if (depPath != null) return depPath; |
| } |
| |
| return null; |
| } |
| |
| return walkDeps(depender, depender.name); |
| } |
| |
| /// 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 { |
| var count = _selected.last.length; |
| message = "* select ${_selected.last.first} ($count versions)"; |
| } |
| } else { |
| // Otherwise, indent it under the current selected package. |
| message = "| $message"; |
| } |
| |
| // Indent for the previous selections. |
| var buffer = new StringBuffer(); |
| buffer.writeAll(_selected.skip(1).map((_) => '| ')); |
| buffer.write(message); |
| log.solver(buffer); |
| } |
| } |
| |
| /// 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 will fail and stop |
| /// traversing. If it reaches a package that isn't selected it will refine the |
| /// solution by adding that package's set of allowed versions to the solver and |
| /// then select the best one and continue. |
| 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.toList(); |
| |
| // Include dev dependencies of the root package. |
| if (id.isRoot) deps.addAll(pubspec.devDependencies); |
| |
| // Given a package dep, returns a future that completes to a pair of the |
| // dep and the number of versions available for it. |
| getNumVersions(PackageDep dep) { |
| // There is only ever one version of the root package. |
| if (dep.isRoot) { |
| return new Future.value(new Pair<PackageDep, int>(dep, 1)); |
| } |
| |
| return _solver.cache.getVersions(dep.toRef()).then((versions) { |
| return new Pair<PackageDep, int>(dep, versions.length); |
| }).catchError((error) { |
| // If it fails for any reason, just treat that as no versions. This |
| // will sort this reference higher so that we can traverse into it |
| // and report the error more properly. |
| log.solver("Could not get versions for $dep:\n$error\n\n" |
| "${getAttachedStackTrace(error)}"); |
| return new Pair<PackageDep, int>(dep, 0); |
| }); |
| } |
| |
| return Future.wait(deps.map(getNumVersions)).then((pairs) { |
| // Future.wait() returns an immutable list, so make a copy. |
| pairs = pairs.toList(); |
| |
| // Sort in best-first order to minimize backtracking. |
| pairs.sort((a, b) { |
| // Traverse into packages we've already selected first. |
| var aIsSelected = _solver.getSelected(a.first.name) != null; |
| var bIsSelected = _solver.getSelected(b.first.name) != null; |
| if (aIsSelected && !bIsSelected) return -1; |
| if (!aIsSelected && bIsSelected) return 1; |
| |
| // Traverse into packages with fewer versions since they will lead to |
| // less backtracking. |
| if (a.last != b.last) return a.last.compareTo(b.last); |
| |
| // Otherwise, just sort by name so that it's deterministic. |
| return a.first.name.compareTo(b.first.name); |
| }); |
| |
| var queue = new Queue<PackageDep>.from(pairs.map((pair) => pair.first)); |
| return _traverseDeps(id.name, queue); |
| }); |
| }); |
| } |
| |
| /// Traverses the references that [depender] depends on, stored in [refs]. |
| /// Desctructively modifies [refs]. 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(String depender, |
| Queue<PackageDep> deps) { |
| // Move onto the next package if we've traversed all of these references. |
| if (deps.isEmpty) return _traversePackage(); |
| |
| return resetStack(() { |
| var dep = deps.removeFirst(); |
| |
| _validateDependency(dep, depender); |
| var constraint = _addConstraint(dep, depender); |
| |
| 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 _traverseDeps(depender, deps); |
| } |
| |
| // We haven't selected a version. Get all of the versions that match the |
| // constraints we currently have for this package and add them to the |
| // set of solutions to try. |
| return _selectPackage(dep, constraint).then( |
| (_) => _traverseDeps(depender, deps)); |
| }); |
| } |
| |
| /// Ensures that dependency [dep] from [depender] is consistent with the |
| /// other dependencies on the same package. Throws a [SolverFailure] |
| /// exception if not. Only validates sources and descriptions, not the |
| /// version. |
| void _validateDependency(PackageDep dep, String depender) { |
| // 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.name != dep.source.name) { |
| _solver.logSolve('source mismatch on ${dep.name}: ${required.dep.source} ' |
| '!= ${dep.source}'); |
| throw new SourceMismatchException(dep.name, |
| [required, new Dependency(depender, dep)]); |
| } |
| |
| // Make sure all of the existing descriptions match the new reference. |
| if (!dep.descriptionEquals(required.dep)) { |
| _solver.logSolve('description mismatch on ${dep.name}: ' |
| '${required.dep.description} != ${dep.description}'); |
| throw new DescriptionMismatchException(dep.name, |
| [required, new Dependency(depender, dep)]); |
| } |
| } |
| |
| /// Adds the version constraint that [depender] places on [dep] to the |
| /// overall constraint that all shared dependencies place on [dep]. Throws a |
| /// [SolverFailure] if that results in an unsolvable constraints. |
| /// |
| /// Returns the combined [VersionConstraint] that all dependers place on the |
| /// package. |
| VersionConstraint _addConstraint(PackageDep dep, String depender) { |
| // Add the dependency. |
| var dependencies = _getDependencies(dep.name); |
| dependencies.add(new Dependency(depender, dep)); |
| |
| // Determine the overall version constraint. |
| var constraint = dependencies |
| .map((dep) => dep.dep.constraint) |
| .fold(VersionConstraint.any, (a, b) => a.intersect(b)); |
| |
| // See if it's possible for a package to match that constraint. |
| if (constraint.isEmpty) { |
| _solver.logSolve('disjoint constraints on ${dep.name}'); |
| throw new DisjointConstraintException(dep.name, dependencies); |
| } |
| |
| return constraint; |
| } |
| |
| /// 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 [SolverFailure] 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, constraint, |
| _getDependencies(dep.name)); |
| } |
| |
| return selected; |
| } |
| |
| /// Tries to select a package that matches [dep] and [constraint]. Updates |
| /// the solver state so that we can backtrack from this decision if it turns |
| /// out wrong, but continues traversing with the new selection. |
| /// |
| /// Returns a future that completes with a [SolverFailure] if a version |
| /// could not be selected or that completes successfully if a package was |
| /// selected and traversing should continue. |
| Future _selectPackage(PackageDep dep, VersionConstraint constraint) { |
| return _solver.cache.getVersions(dep.toRef()).then((versions) { |
| var allowed = versions.where((id) => constraint.allows(id.version)); |
| |
| // See if it's in the lockfile. If so, try that version first. If the |
| // locked version doesn't match our constraint, just ignore it. |
| var locked = _getValidLocked(dep.name, constraint); |
| if (locked != null) { |
| allowed = allowed.where((dep) => dep.version != locked.version) |
| .toList(); |
| allowed.insert(0, locked); |
| } |
| |
| if (allowed.isEmpty) { |
| _solver.logSolve('no versions for ${dep.name} match $constraint'); |
| throw new NoVersionException(dep.name, 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]; |
| |
| // Try the first package in the allowed set and keep track of the list of |
| // other possible versions in case that fails. |
| _packages.add(_solver.select(allowed)); |
| }); |
| } |
| |
| /// Gets the list of dependencies for package [name]. Will create 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 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, VersionConstraint constraint) { |
| var package = _solver.getLocked(name); |
| if (package == null) return null; |
| |
| 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.name != required.dep.source.name) return null; |
| if (!package.descriptionEquals(required.dep)) return null; |
| } |
| |
| return package; |
| } |
| } |
| |
| /// Ensures that if [pubspec] has an SDK constraint, then it is compatible |
| /// with the current SDK. Throws a [SolverFailure] if not. |
| void _validateSdkConstraint(Pubspec pubspec) { |
| // If the user is running a continouous build of the SDK, just disable SDK |
| // constraint checking entirely. The actual version number you get is |
| // impossibly old and not correct. We'll just assume users on continuous |
| // know what they're doing. |
| if (sdk.isBleedingEdge) return; |
| |
| if (pubspec.environment.sdkVersion.allows(sdk.version)) return; |
| |
| throw new BadSdkVersionException(pubspec.name, |
| 'Package ${pubspec.name} requires SDK version ' |
| '${pubspec.environment.sdkVersion} but the current SDK is ' |
| '${sdk.version}.'); |
| } |