| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 /// A back-tracking depth-first solver. | |
| 6 /// | |
| 7 /// Attempts to find the best solution for a root package's transitive | |
| 8 /// dependency graph, where a "solution" is a set of concrete package versions. | |
| 9 /// A valid solution will select concrete versions for every package reached | |
| 10 /// from the root package's dependency graph, and each of those packages will | |
| 11 /// fit the version constraints placed on it. | |
| 12 /// | |
| 13 /// The solver builds up a solution incrementally by traversing the dependency | |
| 14 /// graph starting at the root package. When it reaches a new package, it gets | |
| 15 /// the set of versions that meet the current constraint placed on it. It | |
| 16 /// *speculatively* selects one version from that set and adds it to the | |
| 17 /// current solution and then proceeds. If it fully traverses the dependency | |
| 18 /// graph, the solution is valid and it stops. | |
| 19 /// | |
| 20 /// If it reaches an error because: | |
| 21 /// | |
| 22 /// - A new dependency is placed on a package that's already been selected in | |
| 23 /// the solution and the selected version doesn't match the new constraint. | |
| 24 /// | |
| 25 /// - There are no versions available that meet the constraint placed on a | |
| 26 /// package. | |
| 27 /// | |
| 28 /// - etc. | |
| 29 /// | |
| 30 /// then the current solution is invalid. It will then backtrack to the most | |
| 31 /// recent speculative version choice and try the next one. That becomes the | |
| 32 /// new in-progress solution and it tries to proceed from there. It will keep | |
| 33 /// doing this, traversing and then backtracking when it meets a failure until | |
| 34 /// a valid solution has been found or until all possible options for all | |
| 35 /// speculative choices have been exhausted. | |
| 36 library pub.solver.backtracking_solver; | |
| 37 | |
| 38 import 'dart:async'; | |
| 39 import 'dart:collection' show Queue; | |
| 40 | |
| 41 import 'package:pub_semver/pub_semver.dart'; | |
| 42 | |
| 43 import '../barback.dart' as barback; | |
| 44 import '../exceptions.dart'; | |
| 45 import '../lock_file.dart'; | |
| 46 import '../log.dart' as log; | |
| 47 import '../package.dart'; | |
| 48 import '../pubspec.dart'; | |
| 49 import '../sdk.dart' as sdk; | |
| 50 import '../source_registry.dart'; | |
| 51 import '../source/unknown.dart'; | |
| 52 import '../utils.dart'; | |
| 53 import 'dependency_queue.dart'; | |
| 54 import 'version_queue.dart'; | |
| 55 import 'version_solver.dart'; | |
| 56 | |
| 57 /// The top-level solver. | |
| 58 /// | |
| 59 /// Keeps track of the current potential solution, and the other possible | |
| 60 /// versions for speculative package selections. Backtracks and advances to the | |
| 61 /// next potential solution in the case of a failure. | |
| 62 class BacktrackingSolver { | |
| 63 final SolveType type; | |
| 64 final SourceRegistry sources; | |
| 65 final Package root; | |
| 66 | |
| 67 /// The lockfile that was present before solving. | |
| 68 final LockFile lockFile; | |
| 69 | |
| 70 final PubspecCache cache; | |
| 71 | |
| 72 /// The set of packages that are being explicitly upgraded. | |
| 73 /// | |
| 74 /// The solver will only allow the very latest version for each of these | |
| 75 /// packages. | |
| 76 final _forceLatest = new Set<String>(); | |
| 77 | |
| 78 /// The set of packages whose dependecy is being overridden by the root | |
| 79 /// package, keyed by the name of the package. | |
| 80 /// | |
| 81 /// Any dependency on a package that appears in this map will be overriden | |
| 82 /// to use the one here. | |
| 83 final _overrides = new Map<String, PackageDep>(); | |
| 84 | |
| 85 /// The package versions currently selected by the solver, along with the | |
| 86 /// versions which are remaining to be tried. | |
| 87 /// | |
| 88 /// Every time a package is encountered when traversing the dependency graph, | |
| 89 /// the solver must select a version for it, sometimes when multiple versions | |
| 90 /// are valid. This keeps track of which versions have been selected so far | |
| 91 /// and which remain to be tried. | |
| 92 /// | |
| 93 /// Each entry in the list is a [VersionQueue], which is an ordered queue of | |
| 94 /// versions to try for a single package. It maintains the currently selected | |
| 95 /// version for that package. When a new dependency is encountered, a queue | |
| 96 /// of versions of that dependency is pushed onto the end of the list. A | |
| 97 /// queue is removed from the list once it's empty, indicating that none of | |
| 98 /// the versions provided a solution. | |
| 99 /// | |
| 100 /// The solver tries versions in depth-first order, so only the last queue in | |
| 101 /// the list will have items removed from it. When a new constraint is placed | |
| 102 /// on an already-selected package, and that constraint doesn't match the | |
| 103 /// selected version, that will cause the current solution to fail and | |
| 104 /// trigger backtracking. | |
| 105 final _selected = <VersionQueue>[]; | |
| 106 | |
| 107 /// The number of solutions the solver has tried so far. | |
| 108 int get attemptedSolutions => _attemptedSolutions; | |
| 109 var _attemptedSolutions = 1; | |
| 110 | |
| 111 BacktrackingSolver(SolveType type, SourceRegistry sources, this.root, | |
| 112 this.lockFile, List<String> useLatest) | |
| 113 : type = type, | |
| 114 sources = sources, | |
| 115 cache = new PubspecCache(type, sources) { | |
| 116 for (var package in useLatest) { | |
| 117 _forceLatest.add(package); | |
| 118 } | |
| 119 | |
| 120 for (var override in root.dependencyOverrides) { | |
| 121 _overrides[override.name] = override; | |
| 122 } | |
| 123 } | |
| 124 | |
| 125 /// Run the solver. | |
| 126 /// | |
| 127 /// Completes with a list of specific package versions if successful or an | |
| 128 /// error if it failed to find a solution. | |
| 129 Future<SolveResult> solve() { | |
| 130 var stopwatch = new Stopwatch(); | |
| 131 | |
| 132 _logParameters(); | |
| 133 | |
| 134 // Sort the overrides by package name to make sure they're deterministic. | |
| 135 var overrides = _overrides.values.toList(); | |
| 136 overrides.sort((a, b) => a.name.compareTo(b.name)); | |
| 137 | |
| 138 // TODO(nweiz): Use async/await here once | |
| 139 // https://github.com/dart-lang/async_await/issues/79 is fixed. | |
| 140 return new Future.sync(() { | |
| 141 stopwatch.start(); | |
| 142 | |
| 143 // Pre-cache the root package's known pubspec. | |
| 144 cache.cache(new PackageId.root(root), root.pubspec); | |
| 145 | |
| 146 _validateSdkConstraint(root.pubspec); | |
| 147 return _traverseSolution(); | |
| 148 }).then((packages) { | |
| 149 var pubspecs = new Map.fromIterable( | |
| 150 packages, | |
| 151 key: (id) => id.name, | |
| 152 value: (id) => cache.getCachedPubspec(id)); | |
| 153 | |
| 154 return Future.wait( | |
| 155 packages.map((id) => sources[id.source].resolveId(id))).then((packages
) { | |
| 156 return new SolveResult.success( | |
| 157 sources, | |
| 158 root, | |
| 159 lockFile, | |
| 160 packages, | |
| 161 overrides, | |
| 162 pubspecs, | |
| 163 _getAvailableVersions(packages), | |
| 164 attemptedSolutions); | |
| 165 }); | |
| 166 }).catchError((error) { | |
| 167 if (error is! SolveFailure) throw error; | |
| 168 // Wrap a failure in a result so we can attach some other data. | |
| 169 return new SolveResult.failure( | |
| 170 sources, | |
| 171 root, | |
| 172 lockFile, | |
| 173 overrides, | |
| 174 error, | |
| 175 attemptedSolutions); | |
| 176 }).whenComplete(() { | |
| 177 // Gather some solving metrics. | |
| 178 var buffer = new StringBuffer(); | |
| 179 buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.'); | |
| 180 buffer.writeln(cache.describeResults()); | |
| 181 log.solver(buffer); | |
| 182 }); | |
| 183 } | |
| 184 | |
| 185 /// Generates a map containing all of the known available versions for each | |
| 186 /// package in [packages]. | |
| 187 /// | |
| 188 /// The version list may not always be complete. The the package is the root | |
| 189 /// root package, or its a package that we didn't unlock while solving | |
| 190 /// because we weren't trying to upgrade it, we will just know the current | |
| 191 /// version. | |
| 192 Map<String, List<Version>> _getAvailableVersions(List<PackageId> packages) { | |
| 193 var availableVersions = new Map<String, List<Version>>(); | |
| 194 for (var package in packages) { | |
| 195 var cached = cache.getCachedVersions(package.toRef()); | |
| 196 var versions; | |
| 197 if (cached != null) { | |
| 198 versions = cached.map((id) => id.version).toList(); | |
| 199 } else { | |
| 200 // If the version list was never requested, just use the one known | |
| 201 // version. | |
| 202 versions = [package.version]; | |
| 203 } | |
| 204 | |
| 205 availableVersions[package.name] = versions; | |
| 206 } | |
| 207 | |
| 208 return availableVersions; | |
| 209 } | |
| 210 | |
| 211 /// Adds [versions], which is the list of all allowed versions of a given | |
| 212 /// package, to the set of versions to consider for solutions. | |
| 213 /// | |
| 214 /// The first item in the list will be the currently selected version of that | |
| 215 /// package. Subsequent items will be tried if it the current selection fails. | |
| 216 /// Returns the first selected version. | |
| 217 PackageId select(VersionQueue versions) { | |
| 218 _selected.add(versions); | |
| 219 logSolve(); | |
| 220 return versions.current; | |
| 221 } | |
| 222 | |
| 223 /// Returns the the currently selected id for the package [name] or `null` if | |
| 224 /// no concrete version has been selected for that package yet. | |
| 225 PackageId getSelected(String name) { | |
| 226 // Always prefer the root package. | |
| 227 if (root.name == name) return new PackageId.root(root); | |
| 228 | |
| 229 // Look through the current selections. | |
| 230 for (var i = _selected.length - 1; i >= 0; i--) { | |
| 231 if (_selected[i].current.name == name) return _selected[i].current; | |
| 232 } | |
| 233 | |
| 234 return null; | |
| 235 } | |
| 236 | |
| 237 /// Gets the version of [package] currently locked in the lock file. | |
| 238 /// | |
| 239 /// Returns `null` if it isn't in the lockfile (or has been unlocked). | |
| 240 PackageId getLocked(String package) { | |
| 241 if (type == SolveType.GET) return lockFile.packages[package]; | |
| 242 | |
| 243 // When downgrading, we don't want to force the latest versions of | |
| 244 // non-hosted packages, since they don't support multiple versions and thus | |
| 245 // can't be downgraded. | |
| 246 if (type == SolveType.DOWNGRADE) { | |
| 247 var locked = lockFile.packages[package]; | |
| 248 if (locked != null && !sources[locked.source].hasMultipleVersions) { | |
| 249 return locked; | |
| 250 } | |
| 251 } | |
| 252 | |
| 253 if (_forceLatest.isEmpty || _forceLatest.contains(package)) return null; | |
| 254 return lockFile.packages[package]; | |
| 255 } | |
| 256 | |
| 257 /// Traverses the root package's dependency graph using the current potential | |
| 258 /// solution. | |
| 259 /// | |
| 260 /// If successful, completes to the solution. If not, backtracks to the most | |
| 261 /// recently selected version of a package and tries the next version of it. | |
| 262 /// If there are no more versions, continues to backtrack to previous | |
| 263 /// selections, and so on. If there is nothing left to backtrack to, | |
| 264 /// completes to the last failure that occurred. | |
| 265 Future<List<PackageId>> _traverseSolution() => resetStack(() { | |
| 266 return new Traverser(this).traverse().catchError((error) { | |
| 267 if (error is! SolveFailure) throw error; | |
| 268 | |
| 269 return _backtrack(error).then((canTry) { | |
| 270 if (canTry) { | |
| 271 _attemptedSolutions++; | |
| 272 return _traverseSolution(); | |
| 273 } | |
| 274 | |
| 275 // All out of solutions, so fail. | |
| 276 throw error; | |
| 277 }); | |
| 278 }); | |
| 279 }); | |
| 280 | |
| 281 /// Backtracks from the current failed solution and determines the next | |
| 282 /// solution to try. | |
| 283 /// | |
| 284 /// If possible, it will backjump based on the cause of the [failure] to | |
| 285 /// minize backtracking. Otherwise, it will simply backtrack to the next | |
| 286 /// possible solution. | |
| 287 /// | |
| 288 /// Returns `true` if there is a new solution to try. | |
| 289 Future<bool> _backtrack(SolveFailure failure) { | |
| 290 // Bail if there is nothing to backtrack to. | |
| 291 if (_selected.isEmpty) return new Future.value(false); | |
| 292 | |
| 293 // Mark any packages that may have led to this failure so that we know to | |
| 294 // consider them when backtracking. | |
| 295 var dependers = _getTransitiveDependers(failure.package); | |
| 296 | |
| 297 for (var selected in _selected) { | |
| 298 if (dependers.contains(selected.current.name)) { | |
| 299 selected.fail(); | |
| 300 } | |
| 301 } | |
| 302 | |
| 303 // Advance past the current version of the leaf-most package. | |
| 304 advanceVersion() { | |
| 305 _backjump(failure); | |
| 306 var previous = _selected.last.current; | |
| 307 return _selected.last.advance().then((success) { | |
| 308 if (success) { | |
| 309 logSolve(); | |
| 310 return true; | |
| 311 } | |
| 312 | |
| 313 logSolve('$previous is last version, backtracking'); | |
| 314 | |
| 315 // That package has no more versions, so pop it and try the next one. | |
| 316 _selected.removeLast(); | |
| 317 if (_selected.isEmpty) return false; | |
| 318 | |
| 319 // If we got here, the leafmost package was discarded so we need to | |
| 320 // advance the next one. | |
| 321 return advanceVersion(); | |
| 322 }); | |
| 323 } | |
| 324 | |
| 325 return advanceVersion(); | |
| 326 } | |
| 327 | |
| 328 /// Walks the selected packages from most to least recent to determine which | |
| 329 /// ones can be ignored and jumped over by the backtracker. | |
| 330 /// | |
| 331 /// The only packages we need to backtrack to are ones that led (possibly | |
| 332 /// indirectly) to the failure. Everything else can be skipped. | |
| 333 void _backjump(SolveFailure failure) { | |
| 334 for (var i = _selected.length - 1; i >= 0; i--) { | |
| 335 // Each queue will never be empty since it gets discarded by _backtrack() | |
| 336 // when that happens. | |
| 337 var selected = _selected[i].current; | |
| 338 | |
| 339 // If the failure is a disjoint version range, then no possible versions | |
| 340 // for that package can match and there's no reason to try them. Instead, | |
| 341 // just backjump past it. | |
| 342 if (failure is DisjointConstraintException && | |
| 343 selected.name == failure.package) { | |
| 344 logSolve("skipping past disjoint selected ${selected.name}"); | |
| 345 continue; | |
| 346 } | |
| 347 | |
| 348 if (_selected[i].hasFailed) { | |
| 349 logSolve('backjump to ${selected.name}'); | |
| 350 _selected.removeRange(i + 1, _selected.length); | |
| 351 return; | |
| 352 } | |
| 353 } | |
| 354 | |
| 355 // If we got here, we walked the entire list without finding a package that | |
| 356 // could lead to another solution, so discard everything. This will happen | |
| 357 // if every package that led to the failure has no other versions that it | |
| 358 // can try to select. | |
| 359 _selected.removeRange(1, _selected.length); | |
| 360 } | |
| 361 | |
| 362 /// Gets the set of currently selected packages that depend on [dependency] | |
| 363 /// either directly or indirectly. | |
| 364 /// | |
| 365 /// When backtracking, it's only useful to consider changing the version of | |
| 366 /// packages who have a dependency on the failed package that triggered | |
| 367 /// backtracking. This is used to determine those packages. | |
| 368 /// | |
| 369 /// We calculate the full set up front before backtracking because during | |
| 370 /// backtracking, we will unselect packages and start to lose this | |
| 371 /// information in the middle of the process. | |
| 372 /// | |
| 373 /// For example, consider dependencies A -> B -> C. We've selected A and B | |
| 374 /// then encounter a problem with C. We start backtracking. B has no more | |
| 375 /// versions so we discard it and keep backtracking to A. When we get there, | |
| 376 /// since we've unselected B, we no longer realize that A had a transitive | |
| 377 /// dependency on C. We would end up backjumping over A and failing. | |
| 378 /// | |
| 379 /// Calculating the dependency set up front before we start backtracking | |
| 380 /// solves that. | |
| 381 Set<String> _getTransitiveDependers(String dependency) { | |
| 382 // Generate a reverse dependency graph. For each package, create edges to | |
| 383 // each package that depends on it. | |
| 384 var dependers = new Map<String, Set<String>>(); | |
| 385 | |
| 386 addDependencies(name, deps) { | |
| 387 dependers.putIfAbsent(name, () => new Set<String>()); | |
| 388 for (var dep in deps) { | |
| 389 dependers.putIfAbsent(dep.name, () => new Set<String>()).add(name); | |
| 390 } | |
| 391 } | |
| 392 | |
| 393 for (var i = 0; i < _selected.length; i++) { | |
| 394 var id = _selected[i].current; | |
| 395 var pubspec = cache.getCachedPubspec(id); | |
| 396 if (pubspec != null) addDependencies(id.name, pubspec.dependencies); | |
| 397 } | |
| 398 | |
| 399 // Include the root package's dependencies. | |
| 400 addDependencies(root.name, root.immediateDependencies); | |
| 401 | |
| 402 // Now walk the depending graph to see which packages transitively depend | |
| 403 // on [dependency]. | |
| 404 var visited = new Set<String>(); | |
| 405 walk(String package) { | |
| 406 // Don't get stuck in cycles. | |
| 407 if (visited.contains(package)) return; | |
| 408 visited.add(package); | |
| 409 var depender = dependers[package].forEach(walk); | |
| 410 } | |
| 411 | |
| 412 walk(dependency); | |
| 413 return visited; | |
| 414 } | |
| 415 | |
| 416 /// Logs the initial parameters to the solver. | |
| 417 void _logParameters() { | |
| 418 var buffer = new StringBuffer(); | |
| 419 buffer.writeln("Solving dependencies:"); | |
| 420 for (var package in root.dependencies) { | |
| 421 buffer.write("- $package"); | |
| 422 var locked = getLocked(package.name); | |
| 423 if (_forceLatest.contains(package.name)) { | |
| 424 buffer.write(" (use latest)"); | |
| 425 } else if (locked != null) { | |
| 426 var version = locked.version; | |
| 427 buffer.write(" (locked to $version)"); | |
| 428 } | |
| 429 buffer.writeln(); | |
| 430 } | |
| 431 log.solver(buffer.toString().trim()); | |
| 432 } | |
| 433 | |
| 434 /// Logs [message] in the context of the current selected packages. | |
| 435 /// | |
| 436 /// If [message] is omitted, just logs a description of leaf-most selection. | |
| 437 void logSolve([String message]) { | |
| 438 if (message == null) { | |
| 439 if (_selected.isEmpty) { | |
| 440 message = "* start at root"; | |
| 441 } else { | |
| 442 message = "* select ${_selected.last.current}"; | |
| 443 } | |
| 444 } else { | |
| 445 // Otherwise, indent it under the current selected package. | |
| 446 message = prefixLines(message); | |
| 447 } | |
| 448 | |
| 449 // Indent for the previous selections. | |
| 450 var prefix = _selected.skip(1).map((_) => '| ').join(); | |
| 451 log.solver(prefixLines(message, prefix: prefix)); | |
| 452 } | |
| 453 } | |
| 454 | |
| 455 /// Given the solver's current set of selected package versions, this tries to | |
| 456 /// traverse the dependency graph and see if a complete set of valid versions | |
| 457 /// has been chosen. | |
| 458 /// | |
| 459 /// If it reaches a conflict, it fails and stops traversing. If it reaches a | |
| 460 /// package that isn't selected, it refines the solution by adding that | |
| 461 /// package's set of allowed versions to the solver and then select the best | |
| 462 /// one and continuing. | |
| 463 class Traverser { | |
| 464 final BacktrackingSolver _solver; | |
| 465 | |
| 466 /// The queue of packages left to traverse. | |
| 467 /// | |
| 468 /// We do a breadth-first traversal using an explicit queue just to avoid the | |
| 469 /// code complexity of a recursive asynchronous traversal. | |
| 470 final _packages = new Queue<PackageId>(); | |
| 471 | |
| 472 /// The packages we have already traversed. | |
| 473 /// | |
| 474 /// Used to avoid traversing the same package multiple times, and to build | |
| 475 /// the complete solution results. | |
| 476 final _visited = new Set<PackageId>(); | |
| 477 | |
| 478 /// The dependencies visited so far in the traversal. | |
| 479 /// | |
| 480 /// For each package name (the map key) we track the list of dependencies | |
| 481 /// that other packages have placed on it so that we can calculate the | |
| 482 /// complete constraint for shared dependencies. | |
| 483 final _dependencies = <String, List<Dependency>>{}; | |
| 484 | |
| 485 Traverser(this._solver); | |
| 486 | |
| 487 /// Walks the dependency graph starting at the root package and validates | |
| 488 /// that each reached package has a valid version selected. | |
| 489 Future<List<PackageId>> traverse() { | |
| 490 // Start at the root. | |
| 491 _packages.add(new PackageId.root(_solver.root)); | |
| 492 return _traversePackage(); | |
| 493 } | |
| 494 | |
| 495 /// Traverses the next package in the queue. | |
| 496 /// | |
| 497 /// Completes to a list of package IDs if the traversal completed | |
| 498 /// successfully and found a solution. Completes to an error if the traversal | |
| 499 /// failed. Otherwise, recurses to the next package in the queue, etc. | |
| 500 Future<List<PackageId>> _traversePackage() { | |
| 501 if (_packages.isEmpty) { | |
| 502 // We traversed the whole graph. If we got here, we successfully found | |
| 503 // a solution. | |
| 504 return new Future<List<PackageId>>.value(_visited.toList()); | |
| 505 } | |
| 506 | |
| 507 var id = _packages.removeFirst(); | |
| 508 | |
| 509 // Don't visit the same package twice. | |
| 510 if (_visited.contains(id)) { | |
| 511 return _traversePackage(); | |
| 512 } | |
| 513 _visited.add(id); | |
| 514 | |
| 515 return _solver.cache.getPubspec(id).then((pubspec) { | |
| 516 _validateSdkConstraint(pubspec); | |
| 517 | |
| 518 var deps = pubspec.dependencies.toSet(); | |
| 519 | |
| 520 if (id.isRoot) { | |
| 521 // Include dev dependencies of the root package. | |
| 522 deps.addAll(pubspec.devDependencies); | |
| 523 | |
| 524 // Add all overrides. This ensures a dependency only present as an | |
| 525 // override is still included. | |
| 526 deps.addAll(_solver._overrides.values); | |
| 527 } | |
| 528 | |
| 529 // Replace any overridden dependencies. | |
| 530 deps = deps.map((dep) { | |
| 531 var override = _solver._overrides[dep.name]; | |
| 532 if (override != null) return override; | |
| 533 | |
| 534 // Not overridden. | |
| 535 return dep; | |
| 536 }).toSet(); | |
| 537 | |
| 538 // Make sure the package doesn't have any bad dependencies. | |
| 539 for (var dep in deps) { | |
| 540 if (!dep.isRoot && _solver.sources[dep.source] is UnknownSource) { | |
| 541 throw new UnknownSourceException( | |
| 542 id.name, | |
| 543 [new Dependency(id.name, id.version, dep)]); | |
| 544 } | |
| 545 } | |
| 546 | |
| 547 return _traverseDeps(id, new DependencyQueue(_solver, deps)); | |
| 548 }).catchError((error) { | |
| 549 if (error is! PackageNotFoundException) throw error; | |
| 550 | |
| 551 // We can only get here if the lockfile refers to a specific package | |
| 552 // version that doesn't exist (probably because it was yanked). | |
| 553 throw new NoVersionException(id.name, null, id.version, []); | |
| 554 }); | |
| 555 } | |
| 556 | |
| 557 /// Traverses the references that [depender] depends on, stored in [deps]. | |
| 558 /// | |
| 559 /// Desctructively modifies [deps]. Completes to a list of packages if the | |
| 560 /// traversal is complete. Completes it to an error if a failure occurred. | |
| 561 /// Otherwise, recurses. | |
| 562 Future<List<PackageId>> _traverseDeps(PackageId depender, | |
| 563 DependencyQueue deps) { | |
| 564 // Move onto the next package if we've traversed all of these references. | |
| 565 if (deps.isEmpty) return _traversePackage(); | |
| 566 | |
| 567 return resetStack(() { | |
| 568 return deps.advance().then((dep) { | |
| 569 var dependency = new Dependency(depender.name, depender.version, dep); | |
| 570 return _registerDependency(dependency).then((_) { | |
| 571 if (dep.name == "barback") return _addImplicitDependencies(); | |
| 572 }); | |
| 573 }).then((_) => _traverseDeps(depender, deps)); | |
| 574 }); | |
| 575 } | |
| 576 | |
| 577 /// Register [dependency]'s constraints on the package it depends on and | |
| 578 /// enqueues the package for processing if necessary. | |
| 579 Future _registerDependency(Dependency dependency) { | |
| 580 return new Future.sync(() { | |
| 581 _validateDependency(dependency); | |
| 582 | |
| 583 var dep = dependency.dep; | |
| 584 var dependencies = _getDependencies(dep.name); | |
| 585 dependencies.add(dependency); | |
| 586 | |
| 587 var constraint = _getConstraint(dep.name); | |
| 588 | |
| 589 // See if it's possible for a package to match that constraint. | |
| 590 if (constraint.isEmpty) { | |
| 591 var constraints = dependencies.map( | |
| 592 (dep) => " ${dep.dep.constraint} from ${dep.depender}").join('\n'); | |
| 593 _solver.logSolve('disjoint constraints on ${dep.name}:\n$constraints'); | |
| 594 throw new DisjointConstraintException(dep.name, dependencies); | |
| 595 } | |
| 596 | |
| 597 var selected = _validateSelected(dep, constraint); | |
| 598 if (selected != null) { | |
| 599 // The selected package version is good, so enqueue it to traverse | |
| 600 // into it. | |
| 601 _packages.add(selected); | |
| 602 return null; | |
| 603 } | |
| 604 | |
| 605 // We haven't selected a version. Try all of the versions that match | |
| 606 // the constraints we currently have for this package. | |
| 607 var locked = _getValidLocked(dep.name); | |
| 608 | |
| 609 return VersionQueue.create(locked, () { | |
| 610 return _getAllowedVersions(dep); | |
| 611 }).then((versions) => _packages.add(_solver.select(versions))); | |
| 612 }); | |
| 613 } | |
| 614 | |
| 615 /// Gets all versions of [dep] that match the current constraints placed on | |
| 616 /// it. | |
| 617 Future<Iterable<PackageId>> _getAllowedVersions(PackageDep dep) { | |
| 618 var constraint = _getConstraint(dep.name); | |
| 619 return _solver.cache.getVersions(dep.toRef()).then((versions) { | |
| 620 var allowed = versions.where((id) => constraint.allows(id.version)); | |
| 621 | |
| 622 if (allowed.isEmpty) { | |
| 623 _solver.logSolve('no versions for ${dep.name} match $constraint'); | |
| 624 throw new NoVersionException( | |
| 625 dep.name, | |
| 626 null, | |
| 627 constraint, | |
| 628 _getDependencies(dep.name)); | |
| 629 } | |
| 630 | |
| 631 // If we're doing an upgrade on this package, only allow the latest | |
| 632 // version. | |
| 633 if (_solver._forceLatest.contains(dep.name)) allowed = [allowed.first]; | |
| 634 | |
| 635 // Remove the locked version, if any, since that was already handled. | |
| 636 var locked = _getValidLocked(dep.name); | |
| 637 if (locked != null) { | |
| 638 allowed = allowed.where((dep) => dep.version != locked.version); | |
| 639 } | |
| 640 | |
| 641 return allowed; | |
| 642 }).catchError((error, stackTrace) { | |
| 643 if (error is PackageNotFoundException) { | |
| 644 // Show the user why the package was being requested. | |
| 645 throw new DependencyNotFoundException( | |
| 646 dep.name, | |
| 647 error, | |
| 648 _getDependencies(dep.name)); | |
| 649 } | |
| 650 | |
| 651 throw error; | |
| 652 }); | |
| 653 } | |
| 654 | |
| 655 /// Ensures that dependency [dep] from [depender] is consistent with the | |
| 656 /// other dependencies on the same package. | |
| 657 /// | |
| 658 /// Throws a [SolveFailure] exception if not. Only validates sources and | |
| 659 /// descriptions, not the version. | |
| 660 void _validateDependency(Dependency dependency) { | |
| 661 var dep = dependency.dep; | |
| 662 | |
| 663 // Make sure the dependencies agree on source and description. | |
| 664 var required = _getRequired(dep.name); | |
| 665 if (required == null) return; | |
| 666 | |
| 667 // Make sure all of the existing sources match the new reference. | |
| 668 if (required.dep.source != dep.source) { | |
| 669 _solver.logSolve( | |
| 670 'source mismatch on ${dep.name}: ${required.dep.source} ' '!= ${dep.so
urce}'); | |
| 671 throw new SourceMismatchException(dep.name, [required, dependency]); | |
| 672 } | |
| 673 | |
| 674 // Make sure all of the existing descriptions match the new reference. | |
| 675 var source = _solver.sources[dep.source]; | |
| 676 if (!source.descriptionsEqual(dep.description, required.dep.description)) { | |
| 677 _solver.logSolve( | |
| 678 'description mismatch on ${dep.name}: ' | |
| 679 '${required.dep.description} != ${dep.description}'); | |
| 680 throw new DescriptionMismatchException(dep.name, [required, dependency]); | |
| 681 } | |
| 682 } | |
| 683 | |
| 684 /// Validates the currently selected package against the new dependency that | |
| 685 /// [dep] and [constraint] place on it. | |
| 686 /// | |
| 687 /// Returns `null` if there is no currently selected package, throws a | |
| 688 /// [SolveFailure] if the new reference it not does not allow the previously | |
| 689 /// selected version, or returns the selected package if successful. | |
| 690 PackageId _validateSelected(PackageDep dep, VersionConstraint constraint) { | |
| 691 var selected = _solver.getSelected(dep.name); | |
| 692 if (selected == null) return null; | |
| 693 | |
| 694 // Make sure it meets the constraint. | |
| 695 if (!dep.constraint.allows(selected.version)) { | |
| 696 _solver.logSolve('selection $selected does not match $constraint'); | |
| 697 throw new NoVersionException( | |
| 698 dep.name, | |
| 699 selected.version, | |
| 700 constraint, | |
| 701 _getDependencies(dep.name)); | |
| 702 } | |
| 703 | |
| 704 return selected; | |
| 705 } | |
| 706 | |
| 707 /// Register pub's implicit dependencies. | |
| 708 /// | |
| 709 /// Pub has an implicit version constraint on barback and various other | |
| 710 /// packages used in barback's plugin isolate. | |
| 711 Future _addImplicitDependencies() { | |
| 712 /// Ensure we only add the barback dependency once. | |
| 713 if (_getDependencies("barback").length != 1) return new Future.value(); | |
| 714 | |
| 715 return Future.wait(barback.pubConstraints.keys.map((depName) { | |
| 716 var constraint = barback.pubConstraints[depName]; | |
| 717 _solver.logSolve( | |
| 718 'add implicit $constraint pub dependency on ' '$depName'); | |
| 719 | |
| 720 var override = _solver._overrides[depName]; | |
| 721 | |
| 722 // Use the same source and description as the dependency override if one | |
| 723 // exists. This is mainly used by the pkgbuild tests, which use dependency | |
| 724 // overrides for all repo packages. | |
| 725 var pubDep = override == null ? | |
| 726 new PackageDep(depName, "hosted", constraint, depName) : | |
| 727 override.withConstraint(constraint); | |
| 728 return _registerDependency( | |
| 729 new Dependency("pub itself", Version.none, pubDep)); | |
| 730 })); | |
| 731 } | |
| 732 | |
| 733 /// Gets the list of dependencies for package [name]. | |
| 734 /// | |
| 735 /// Creates an empty list if needed. | |
| 736 List<Dependency> _getDependencies(String name) { | |
| 737 return _dependencies.putIfAbsent(name, () => <Dependency>[]); | |
| 738 } | |
| 739 | |
| 740 /// Gets a "required" reference to the package [name]. | |
| 741 /// | |
| 742 /// This is the first non-root dependency on that package. All dependencies | |
| 743 /// on a package must agree on source and description, except for references | |
| 744 /// to the root package. This will return a reference to that "canonical" | |
| 745 /// source and description, or `null` if there is no required reference yet. | |
| 746 /// | |
| 747 /// This is required because you may have a circular dependency back onto the | |
| 748 /// root package. That second dependency won't be a root dependency and it's | |
| 749 /// *that* one that other dependencies need to agree on. In other words, you | |
| 750 /// can have a bunch of dependencies back onto the root package as long as | |
| 751 /// they all agree with each other. | |
| 752 Dependency _getRequired(String name) { | |
| 753 return _getDependencies( | |
| 754 name).firstWhere((dep) => !dep.dep.isRoot, orElse: () => null); | |
| 755 } | |
| 756 | |
| 757 /// Gets the combined [VersionConstraint] currently being placed on package | |
| 758 /// [name]. | |
| 759 VersionConstraint _getConstraint(String name) { | |
| 760 var constraint = _getDependencies( | |
| 761 name).map( | |
| 762 (dep) => | |
| 763 dep.dep.constraint).fold(VersionConstraint.any, (a, b) => a.inte
rsect(b)); | |
| 764 | |
| 765 return constraint; | |
| 766 } | |
| 767 | |
| 768 /// Gets the package [name] that's currently contained in the lockfile if it | |
| 769 /// meets [constraint] and has the same source and description as other | |
| 770 /// references to that package. | |
| 771 /// | |
| 772 /// Returns `null` otherwise. | |
| 773 PackageId _getValidLocked(String name) { | |
| 774 var package = _solver.getLocked(name); | |
| 775 if (package == null) return null; | |
| 776 | |
| 777 var constraint = _getConstraint(name); | |
| 778 if (!constraint.allows(package.version)) { | |
| 779 _solver.logSolve('$package is locked but does not match $constraint'); | |
| 780 return null; | |
| 781 } else { | |
| 782 _solver.logSolve('$package is locked'); | |
| 783 } | |
| 784 | |
| 785 var required = _getRequired(name); | |
| 786 if (required != null) { | |
| 787 if (package.source != required.dep.source) return null; | |
| 788 | |
| 789 var source = _solver.sources[package.source]; | |
| 790 if (!source.descriptionsEqual( | |
| 791 package.description, | |
| 792 required.dep.description)) return null; | |
| 793 } | |
| 794 | |
| 795 return package; | |
| 796 } | |
| 797 } | |
| 798 | |
| 799 /// Ensures that if [pubspec] has an SDK constraint, then it is compatible | |
| 800 /// with the current SDK. | |
| 801 /// | |
| 802 /// Throws a [SolveFailure] if not. | |
| 803 void _validateSdkConstraint(Pubspec pubspec) { | |
| 804 if (pubspec.environment.sdkVersion.allows(sdk.version)) return; | |
| 805 | |
| 806 throw new BadSdkVersionException( | |
| 807 pubspec.name, | |
| 808 'Package ${pubspec.name} requires SDK version ' | |
| 809 '${pubspec.environment.sdkVersion} but the current SDK is ' '${sdk.ver
sion}.'); | |
| 810 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 937243002:
Revert "Revert "Use native async/await support in pub."" (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart