| // 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'; | |
| class HttpRequest extends $pb.GeneratedMessage { | |
| static final $pb.BuilderInfo _i = $pb.BuilderInfo( | |
| const $core.bool.fromEnvironment('protobuf.omit_message_names') | |
| ? '' | |
| : 'HttpRequest', | |
| package: const $pb.PackageName( | |
| const $core.bool.fromEnvironment('protobuf.omit_message_names') | |
| ? '' | |
| : 'google.logging.type'), | |
| createEmptyInstance: create) | |
| ..aOS( | |
| 1, | |
| const $core.bool.fromEnvironment('protobuf.omit_field_names') | |
| ? '' | |
| : 'requestMethod') | |
| ..aOS( | |
| 2, | |
| const $core.bool.fromEnvironment('protobuf.omit_field_names') | |
| ? '' | |
| : 'requestUrl') | |
| ..aInt64( | |
| 3, | |
| const $core.bool.fromEnvironment('protobuf.omit_field_names') | |
| ? '' | |
| : 'requestSize') | |
| ..a<$core.int>( | |
| 4, | |
| const $core.bool.fromEnvironment('protobuf.omit_field_names') | |
| ? '' | |
| : 'status', | |
| $pb.PbFieldType.O3) | |
| ..aInt64( | |
| 5, | |
| const $core.bool.fromEnvironment('protobuf.omit_field_names') | |
| ? '' | |
| : 'responseSize') | |
| ..aOS( | |
| 6, | |
| const $core.bool.fromEnvironment('protobuf.omit_field_names') | |
| ? '' | |
| : 'userAgent') | |
| ..aOS( | |
| 7, | |
| const $core.bool.fromEnvironment('protobuf.omit_field_names') | |
| ? '' | |
| : 'remoteIp') | |
| ..aOS( | |
| 8, | |
| const $core.bool.fromEnvironment('protobuf.omit_field_names') | |
| ? '' | |
| : 'referer') | |
| ..aOB( | |
| 9, | |
| const $core.bool.fromEnvironment('protobuf.omit_field_names') | |
| ? '' | |
| : 'cacheHit') | |
| ..aOB( | |
| 10, | |
| const $core.bool.fromEnvironment('protobuf.omit_field_names') | |
| ? '' | |
| : 'cacheValidatedWithOriginServer') | |
| ..aOB( | |
| 11, | |
| const $core.bool.fromEnvironment('protobuf.omit_field_names') | |
| ? '' | |
| : 'cacheLookup') | |
| ..aInt64( | |
| 12, | |
| const $core.bool.fromEnvironment('protobuf.omit_field_names') | |
| ? '' | |
| : 'cacheFillBytes') | |
| ..aOS( | |
| 13, | |
| const $core.bool.fromEnvironment('protobuf.omit_field_names') | |
| ? '' | |
| : 'serverIp') | |
| ..aOM<$0.Duration>( | |
| 14, | |
| const $core.bool.fromEnvironment('protobuf.omit_field_names') | |
| ? '' | |
| : 'latency', | |
| subBuilder: $0.Duration.create) | |
| ..aOS( | |
| 15, | |
| const $core.bool.fromEnvironment('protobuf.omit_field_names') | |
| ? '' | |
| : 'protocol') | |
| ..hasRequiredFields = false; | |
| } | |
| /// 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 dependency 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 overridden | |
| /// 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) { | |
| // A fairly large switch statement. | |
| switch (region) { | |
| case Region.everywhere: | |
| return 0.45; | |
| case Region.n: | |
| return lerpDouble(pos.y, 0, height, min, max); | |
| case Region.ne: | |
| var distance = math.max(width - pos.x - 1, pos.y); | |
| var range = math.min(width, height); | |
| return lerpDouble(distance, 0, range, min, max); | |
| case Region.e: | |
| return lerpDouble(pos.x, 0, width, min, max); | |
| case Region.se: | |
| var distance = math.max(width - pos.x - 1, height - pos.y - 1); | |
| var range = math.min(width, height); | |
| return lerpDouble(distance, 0, range, min, max); | |
| case Region.s: | |
| return lerpDouble(pos.y, 0, height, max, min); | |
| case Region.sw: | |
| var distance = math.max(pos.x, height - pos.y - 1); | |
| var range = math.min(width, height); | |
| return lerpDouble(distance, 0, range, min, max); | |
| case Region.w: | |
| return lerpDouble(pos.x, 0, width, max, min); | |
| case Region.nw: | |
| var distance = math.max(pos.x, pos.y); | |
| var range = math.min(width, height); | |
| return lerpDouble(distance, 0, range, min, max); | |
| case Region.everywhere: | |
| return 0.45; | |
| case Region.n: | |
| return lerpDouble(pos.y, 0, height, min, max); | |
| case Region.ne: | |
| var distance = math.max(width - pos.x - 1, pos.y); | |
| var range = math.min(width, height); | |
| return lerpDouble(distance, 0, range, min, max); | |
| case Region.e: | |
| return lerpDouble(pos.x, 0, width, min, max); | |
| case Region.se: | |
| var distance = math.max(width - pos.x - 1, height - pos.y - 1); | |
| var range = math.min(width, height); | |
| return lerpDouble(distance, 0, range, min, max); | |
| case Region.s: | |
| return lerpDouble(pos.y, 0, height, max, min); | |
| case Region.sw: | |
| var distance = math.max(pos.x, height - pos.y - 1); | |
| var range = math.min(width, height); | |
| return lerpDouble(distance, 0, range, min, max); | |
| case Region.w: | |
| return lerpDouble(pos.x, 0, width, max, min); | |
| case Region.nw: | |
| var distance = math.max(pos.x, pos.y); | |
| var range = math.min(width, height); | |
| return lerpDouble(distance, 0, range, min, max); | |
| case Region.everywhere: | |
| return 0.45; | |
| case Region.n: | |
| return lerpDouble(pos.y, 0, height, min, max); | |
| case Region.ne: | |
| var distance = math.max(width - pos.x - 1, pos.y); | |
| var range = math.min(width, height); | |
| return lerpDouble(distance, 0, range, min, max); | |
| case Region.e: | |
| return lerpDouble(pos.x, 0, width, min, max); | |
| case Region.se: | |
| var distance = math.max(width - pos.x - 1, height - pos.y - 1); | |
| var range = math.min(width, height); | |
| return lerpDouble(distance, 0, range, min, max); | |
| case Region.s: | |
| return lerpDouble(pos.y, 0, height, max, min); | |
| case Region.sw: | |
| var distance = math.max(pos.x, height - pos.y - 1); | |
| var range = math.min(width, height); | |
| return lerpDouble(distance, 0, range, min, max); | |
| case Region.w: | |
| return lerpDouble(pos.x, 0, width, max, min); | |
| case Region.nw: | |
| var distance = math.max(pos.x, pos.y); | |
| var range = math.min(width, height); | |
| return lerpDouble(distance, 0, range, min, max); | |
| case Region.everywhere: | |
| return 0.45; | |
| case Region.n: | |
| return lerpDouble(pos.y, 0, height, min, max); | |
| case Region.ne: | |
| var distance = math.max(width - pos.x - 1, pos.y); | |
| var range = math.min(width, height); | |
| return lerpDouble(distance, 0, range, min, max); | |
| case Region.e: | |
| return lerpDouble(pos.x, 0, width, min, max); | |
| case Region.se: | |
| var distance = math.max(width - pos.x - 1, height - pos.y - 1); | |
| var range = math.min(width, height); | |
| return lerpDouble(distance, 0, range, min, max); | |
| case Region.s: | |
| return lerpDouble(pos.y, 0, height, max, min); | |
| case Region.sw: | |
| var distance = math.max(pos.x, height - pos.y - 1); | |
| var range = math.min(width, height); | |
| return lerpDouble(distance, 0, range, min, max); | |
| case Region.w: | |
| return lerpDouble(pos.x, 0, width, max, min); | |
| case Region.nw: | |
| var distance = math.max(pos.x, pos.y); | |
| var range = math.min(width, height); | |
| return lerpDouble(distance, 0, range, min, max); | |
| } | |
| 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'); | |
| // Even more deeply nested pathological example. | |
| if (javaBooleanAnd( | |
| javaBooleanAnd( | |
| javaBooleanAnd( | |
| javaBooleanAnd( | |
| javaBooleanAnd( | |
| javaBooleanAnd( | |
| javaBooleanAnd( | |
| javaBooleanAnd(), | |
| _isEqualTokens( | |
| node.period, | |
| toNode.period)), | |
| _isEqualNodes( | |
| node.name, | |
| toNode.name)), | |
| _isEqualNodes( | |
| node.parameters, | |
| toNode.parameters)), | |
| _isEqualTokens( | |
| node.separator, | |
| toNode.separator)), | |
| _isEqualNodeLists(node.initializers, toNode.initializers)), | |
| _isEqualNodes( | |
| 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(); | |
| _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 package is the root | |
| /// root package, or it's 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 the current selection fails. | |
| /// Returns the first selected version. | |
| PackageId select(VersionQueue versions) { | |
| _selected.add(versions); | |
| logSolve(); | |
| return versions.current; | |
| } | |
| /// Returns 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]. | |
| /// | |
| /// Destructively 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}.'); | |
| } |