| 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. Attempts to find the best solution for | |
| 6 /// a root package's transitive dependency graph, where a "solution" is a set | |
| 7 /// of concrete package versions. A valid solution will select concrete | |
| 8 /// versions for every package reached from the root package's dependency graph, | |
| 9 /// and each of those packages will fit the version constraints placed on it. | |
| 10 /// | |
| 11 /// The solver builds up a solution incrementally by traversing the dependency | |
| 12 /// graph starting at the root package. When it reaches a new package, it gets | |
| 13 /// the set of versions that meet the current constraint placed on it. It | |
| 14 /// *speculatively* selects one version from that set and adds it to the | |
| 15 /// current solution and then proceeds. If it fully traverses the dependency | |
| 16 /// graph, the solution is valid and it stops. | |
| 17 /// | |
| 18 /// If it reaches an error because: | |
| 19 /// | |
| 20 /// - A new dependency is placed on a package that's already been selected in | |
| 21 /// the solution and the selected version doesn't match the new constraint. | |
| 22 /// | |
| 23 /// - There are no versions available that meet the constraint placed on a | |
| 24 /// package. | |
| 25 /// | |
| 26 /// - etc. | |
| 27 /// | |
| 28 /// then the current solution is invalid. It will then backtrack to the most | |
| 29 /// recent speculative version choice and try the next one. That becomes the | |
| 30 /// new in-progress solution and it tries to proceed from there. It will keep | |
| 31 /// doing this, traversing and then backtracking when it meets a failure until | |
| 32 /// a valid solution has been found or until all possible options for all | |
| 33 /// speculative choices have been exhausted. | |
| 34 library solver.backtracking_solver; | |
| 35 | |
| 36 import 'dart:async'; | |
| 37 import 'dart:collection' show Queue; | |
| 38 | |
| 39 import '../lock_file.dart'; | |
| 40 import '../log.dart' as log; | |
| 41 import '../package.dart'; | |
| 42 import '../pubspec.dart'; | |
| 43 import '../sdk.dart' as sdk; | |
| 44 import '../source.dart'; | |
| 45 import '../source_registry.dart'; | |
| 46 import '../utils.dart'; | |
| 47 import '../version.dart'; | |
| 48 import 'version_solver.dart'; | |
| 49 | |
| 50 /// The top-level solver. Keeps track of the current potential solution, and | |
| 51 /// the other possible versions for speculative package selections. Backtracks | |
| 52 /// and advances to the next potential solution in the case of a failure. | |
| 53 class BacktrackingSolver { | |
| 54 final SourceRegistry sources; | |
| 55 final Package root; | |
| 56 final LockFile lockFile; | |
| 57 final PubspecCache cache; | |
| 58 | |
| 59 /// The set of packages that are being explicitly updated. The solver will | |
| 60 /// only allow the very latest version for each of these packages. | |
| 61 final _forceLatest = new Set<String>(); | |
| 62 | |
| 63 /// Every time a package is encountered when traversing the dependency graph, | |
| 64 /// the solver must select a version for it, sometimes when multiple versions | |
| 65 /// are valid. This keeps track of which versions have been selected so far | |
| 66 /// and which remain to be tried. | |
| 67 /// | |
| 68 /// Each entry in the list is an ordered [Queue] of versions to try for a | |
| 69 /// single package. The first item in the queue is the currently selected | |
| 70 /// version for that package. When a new dependency is encountered, a queue | |
| 71 /// of versions of that dependency is pushed onto the end of the list. A | |
| 72 /// queue is removed from the list once it's empty, indicating that none of | |
| 73 /// the versions provided a solution. | |
| 74 /// | |
| 75 /// The solver tries versions in depth-first order, so only the last queue in | |
| 76 /// the list will have items removed from it. When a new constraint is placed | |
| 77 /// on an already-selected package, and that constraint doesn't match the | |
| 78 /// selected version, that will cause the current solution to fail and | |
| 79 /// trigger backtracking. | |
| 80 final _selected = <Queue<PackageId>>[]; | |
| 81 | |
| 82 /// The number of solutions the solver has tried so far. | |
| 83 int get attemptedSolutions => _attemptedSolutions; | |
| 84 var _attemptedSolutions = 1; | |
| 85 | |
| 86 BacktrackingSolver(SourceRegistry sources, this.root, this.lockFile, | |
| 87 List<String> useLatest) | |
| 88 : sources = sources, | |
| 89 cache = new PubspecCache(sources) { | |
| 90 for (var package in useLatest) { | |
| 91 forceLatestVersion(package); | |
| 92 lockFile.packages.remove(package); | |
| 93 } | |
| 94 } | |
| 95 | |
| 96 /// Run the solver. Completes with a list of specific package versions if | |
| 97 /// successful or an error if it failed to find a solution. | |
| 98 Future<SolveResult> solve() { | |
| 99 var stopwatch = new Stopwatch(); | |
| 100 | |
| 101 return new Future(() { | |
| 102 stopwatch.start(); | |
| 103 | |
| 104 // Pre-cache the root package's known pubspec. | |
| 105 cache.cache(new PackageId.root(root), root.pubspec); | |
| 106 | |
| 107 _validateSdkConstraint(root.pubspec); | |
| 108 return _traverseSolution(); | |
| 109 }).then((packages) { | |
| 110 return new SolveResult(packages, null, attemptedSolutions); | |
| 111 }).catchError((error) { | |
| 112 if (error is! SolveFailure) throw error; | |
| 113 | |
| 114 // Wrap a failure in a result so we can attach some other data. | |
| 115 return new SolveResult(null, error, attemptedSolutions); | |
| 116 }).whenComplete(() { | |
| 117 // Gather some solving metrics. | |
| 118 var buffer = new StringBuffer(); | |
| 119 buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.'); | |
| 120 buffer.writeln( | |
| 121 '- Requested ${cache.versionCacheMisses} version lists'); | |
| 122 buffer.writeln( | |
| 123 '- Looked up ${cache.versionCacheHits} cached version lists'); | |
| 124 buffer.writeln( | |
| 125 '- Requested ${cache.pubspecCacheMisses} pubspecs'); | |
| 126 buffer.writeln( | |
| 127 '- Looked up ${cache.pubspecCacheHits} cached pubspecs'); | |
| 128 log.solver(buffer); | |
| 129 }); | |
| 130 } | |
| 131 | |
| 132 void forceLatestVersion(String package) { | |
| 133 _forceLatest.add(package); | |
| 134 } | |
| 135 | |
| 136 /// Adds [versions], which is the list of all allowed versions of a given | |
| 137 /// package, to the set of versions to consider for solutions. The first item | |
| 138 /// in the list will be the currently selected version of that package. | |
| 139 /// Subsequent items will be tried if it the current selection fails. Returns | |
| 140 /// the first selected version. | |
| 141 PackageId select(Iterable<PackageId> versions) { | |
| 142 _selected.add(new Queue<PackageId>.from(versions)); | |
| 143 logSolve(); | |
| 144 return versions.first; | |
| 145 } | |
| 146 | |
| 147 /// Returns the the currently selected id for the package [name] or `null` if | |
| 148 /// no concrete version has been selected for that package yet. | |
| 149 PackageId getSelected(String name) { | |
| 150 // Always prefer the root package. | |
| 151 if (root.name == name) return new PackageId.root(root); | |
| 152 | |
| 153 // Look through the current selections. | |
| 154 for (var i = _selected.length - 1; i >= 0; i--) { | |
| 155 if (_selected[i].first.name == name) return _selected[i].first; | |
| 156 } | |
| 157 | |
| 158 return null; | |
| 159 } | |
| 160 | |
| 161 /// Gets the version of [package] currently locked in the lock file. Returns | |
| 162 /// `null` if it isn't in the lockfile (or has been unlocked). | |
| 163 PackageId getLocked(String package) => lockFile.packages[package]; | |
| 164 | |
| 165 /// Traverses the root package's dependency graph using the current potential | |
| 166 /// solution. If successful, completes to the solution. If not, backtracks | |
| 167 /// to the most recently selected version of a package and tries the next | |
| 168 /// version of it. If there are no more versions, continues to backtrack to | |
| 169 /// previous selections, and so on. If there is nothing left to backtrack to, | |
| 170 /// completes to the last failure that occurred. | |
| 171 Future<List<PackageId>> _traverseSolution() { | |
| 172 return new Traverser(this).traverse().catchError((error) { | |
| 173 if (error is! SolveFailure) throw error; | |
| 174 | |
| 175 if (_backtrack(error)) { | |
| 176 _attemptedSolutions++; | |
| 177 return _traverseSolution(); | |
| 178 } | |
| 179 | |
| 180 // All out of solutions, so fail. | |
| 181 throw error; | |
| 182 }); | |
| 183 } | |
| 184 | |
| 185 /// Backtracks from the current failed solution and determines the next | |
| 186 /// solution to try. If possible, it will backjump based on the cause of the | |
| 187 /// [failure] to minize backtracking. Otherwise, it will simply backtrack to | |
| 188 /// the next possible solution. | |
| 189 /// | |
| 190 /// Returns `true` if there is a new solution to try. | |
| 191 bool _backtrack(SolveFailure failure) { | |
| 192 var dependers = failure.dependencies.map((dep) => dep.depender).toSet(); | |
| 193 | |
| 194 while (!_selected.isEmpty) { | |
| 195 // Look for a relevant selection to jump back to. | |
| 196 for (var i = _selected.length - 1; i >= 0; i--) { | |
| 197 // Can't jump to a package that has no more alternatives. | |
| 198 if (_selected[i].length == 1) continue; | |
| 199 | |
| 200 var selected = _selected[i].first; | |
| 201 | |
| 202 // If we find the package itself that failed, jump to it. | |
| 203 if (selected.name == failure.package) { | |
| 204 logSolve('jump to selected package ${failure.package}'); | |
| 205 _selected.removeRange(i + 1, _selected.length); | |
| 206 break; | |
| 207 } | |
| 208 | |
| 209 // See if this package directly or indirectly depends on [package]. | |
| 210 var path = _getDependencyPath(selected, failure.package); | |
| 211 if (path != null) { | |
| 212 logSolve('backjump to ${selected.name} because it depends on ' | |
| 213 '${failure.package} by $path'); | |
| 214 _selected.removeRange(i + 1, _selected.length); | |
| 215 break; | |
| 216 } | |
| 217 } | |
| 218 | |
| 219 // Advance past the current version of the leaf-most package. | |
| 220 var previous = _selected.last.removeFirst(); | |
| 221 if (!_selected.last.isEmpty) { | |
| 222 logSolve(); | |
| 223 return true; | |
| 224 } | |
| 225 | |
| 226 logSolve('$previous is last version, backtracking'); | |
| 227 | |
| 228 // That package has no more versions, so pop it and try the next one. | |
| 229 _selected.removeLast(); | |
| 230 } | |
| 231 | |
| 232 return false; | |
| 233 } | |
| 234 | |
| 235 /// Determines if [depender] has a direct or indirect dependency on | |
| 236 /// [dependent] based on the currently selected versions of all packages. | |
| 237 /// Returns a string describing the dependency chain if it does, or `null` if | |
| 238 /// there is no dependency. | |
| 239 String _getDependencyPath(PackageId depender, String dependent) { | |
| 240 // TODO(rnystrom): This is O(n^2) where n is the number of selected | |
| 241 // packages. Could store the reverse dependency graph to address that. If | |
| 242 // we do that, we need to make sure it gets correctly rolled back when | |
| 243 // backtracking occurs. | |
| 244 var visited = new Set<String>(); | |
| 245 | |
| 246 walkDeps(PackageId package, String currentPath) { | |
| 247 if (visited.contains(package.name)) return null; | |
| 248 visited.add(package.name); | |
| 249 | |
| 250 var pubspec = cache.getCachedPubspec(package); | |
| 251 if (pubspec == null) return null; | |
| 252 | |
| 253 for (var dep in pubspec.dependencies) { | |
| 254 if (dep.name == dependent) return currentPath; | |
| 255 | |
| 256 var selected = getSelected(dep.name); | |
| 257 // Ignore unselected dependencies. We haven't traversed into them yet, | |
| 258 // so they can't affect backjumping. | |
| 259 if (selected == null) continue; | |
| 260 | |
| 261 var depPath = walkDeps(selected, '$currentPath -> ${dep.name}'); | |
| 262 if (depPath != null) return depPath; | |
| 263 } | |
| 264 | |
| 265 return null; | |
| 266 } | |
| 267 | |
| 268 return walkDeps(depender, depender.name); | |
| 269 } | |
| 270 | |
| 271 /// Logs [message] in the context of the current selected packages. If | |
| 272 /// [message] is omitted, just logs a description of leaf-most selection. | |
| 273 void logSolve([String message]) { | |
| 274 if (message == null) { | |
| 275 if (_selected.isEmpty) { | |
| 276 message = "* start at root"; | |
| 277 } else { | |
| 278 var count = _selected.last.length; | |
| 279 message = "* select ${_selected.last.first} ($count versions)"; | |
| 280 } | |
| 281 } else { | |
| 282 // Otherwise, indent it under the current selected package. | |
| 283 message = "| $message"; | |
| 284 } | |
| 285 | |
| 286 // Indent for the previous selections. | |
| 287 var buffer = new StringBuffer(); | |
| 288 buffer.writeAll(_selected.skip(1).map((_) => '| ')); | |
| 289 buffer.write(message); | |
| 290 log.solver(buffer); | |
| 291 } | |
| 292 } | |
| 293 | |
| 294 /// Given the solver's current set of selected package versions, this tries to | |
| 295 /// traverse the dependency graph and see if a complete set of valid versions | |
| 296 /// has been chosen. If it reaches a conflict, it will fail and stop | |
| 297 /// traversing. If it reaches a package that isn't selected it will refine the | |
| 298 /// solution by adding that package's set of allowed versions to the solver and | |
| 299 /// then select the best one and continue. | |
| 300 class Traverser { | |
| 301 final BacktrackingSolver _solver; | |
| 302 | |
| 303 /// The queue of packages left to traverse. We do a breadth-first traversal | |
| 304 /// using an explicit queue just to avoid the code complexity of a recursive | |
| 305 /// asynchronous traversal. | |
| 306 final _packages = new Queue<PackageId>(); | |
| 307 | |
| 308 /// The packages we have already traversed. Used to avoid traversing the same | |
| 309 /// package multiple times, and to build the complete solution results. | |
| 310 final _visited = new Set<PackageId>(); | |
| 311 | |
| 312 /// The dependencies visited so far in the traversal. For each package name | |
| 313 /// (the map key) we track the list of dependencies that other packages have | |
| 314 /// placed on it so that we can calculate the complete constraint for shared | |
| 315 /// dependencies. | |
| 316 final _dependencies = <String, List<Dependency>>{}; | |
| 317 | |
| 318 Traverser(this._solver); | |
| 319 | |
| 320 /// Walks the dependency graph starting at the root package and validates | |
| 321 /// that each reached package has a valid version selected. | |
| 322 Future<List<PackageId>> traverse() { | |
| 323 // Start at the root. | |
| 324 _packages.add(new PackageId.root(_solver.root)); | |
| 325 return _traversePackage(); | |
| 326 } | |
| 327 | |
| 328 /// Traverses the next package in the queue. Completes to a list of package | |
| 329 /// IDs if the traversal completed successfully and found a solution. | |
| 330 /// Completes to an error if the traversal failed. Otherwise, recurses to the | |
| 331 /// next package in the queue, etc. | |
| 332 Future<List<PackageId>> _traversePackage() { | |
| 333 if (_packages.isEmpty) { | |
| 334 // We traversed the whole graph. If we got here, we successfully found | |
| 335 // a solution. | |
| 336 return new Future<List<PackageId>>.value(_visited.toList()); | |
| 337 } | |
| 338 | |
| 339 var id = _packages.removeFirst(); | |
| 340 | |
| 341 // Don't visit the same package twice. | |
| 342 if (_visited.contains(id)) { | |
| 343 return _traversePackage(); | |
| 344 } | |
| 345 _visited.add(id); | |
| 346 | |
| 347 return _solver.cache.getPubspec(id).then((pubspec) { | |
| 348 _validateSdkConstraint(pubspec); | |
| 349 | |
| 350 var refs = pubspec.dependencies.toList(); | |
| 351 | |
| 352 // Include dev dependencies of the root package. | |
| 353 if (id.isRoot) refs.addAll(pubspec.devDependencies); | |
| 354 | |
| 355 // Given a package ref, returns a future that completes to a pair of the | |
| 356 // ref and the number of versions available for it. | |
| 357 getNumVersions(PackageRef ref) { | |
| 358 // There is only ever one version of the root package. | |
| 359 if (ref.isRoot) { | |
| 360 return new Future.value(new Pair<PackageRef, int>(ref, 1)); | |
| 361 } | |
| 362 | |
| 363 return _solver.cache.getVersions(ref.name, ref.source, ref.description) | |
| 364 .then((versions) { | |
| 365 return new Pair<PackageRef, int>(ref, versions.length); | |
| 366 }).catchError((error) { | |
| 367 // If it fails for any reason, just treat that as no versions. This | |
| 368 // will sort this reference higher so that we can traverse into it | |
| 369 // and report the error more properly. | |
| 370 log.solver("Could not get versions for $ref:\n$error\n\n" | |
| 371 "${getAttachedStackTrace(error)}"); | |
| 372 return new Pair<PackageRef, int>(ref, 0); | |
| 373 }); | |
| 374 } | |
| 375 | |
| 376 return Future.wait(refs.map(getNumVersions)).then((pairs) { | |
| 377 // Future.wait() returns an immutable list, so make a copy. | |
| 378 pairs = pairs.toList(); | |
| 379 | |
| 380 // Sort in best-first order to minimize backtracking. | |
| 381 pairs.sort((a, b) { | |
| 382 // Traverse into packages we've already selected first. | |
| 383 var aIsSelected = _solver.getSelected(a.first.name) != null; | |
| 384 var bIsSelected = _solver.getSelected(b.first.name) != null; | |
| 385 if (aIsSelected && !bIsSelected) return -1; | |
| 386 if (!aIsSelected && bIsSelected) return 1; | |
| 387 | |
| 388 // Traverse into packages with fewer versions since they will lead to | |
| 389 // less backtracking. | |
| 390 if (a.last != b.last) return a.last.compareTo(b.last); | |
| 391 | |
| 392 // Otherwise, just sort by name so that it's deterministic. | |
| 393 return a.first.name.compareTo(b.first.name); | |
| 394 }); | |
| 395 | |
| 396 var queue = new Queue<PackageRef>.from(pairs.map((pair) => pair.first)); | |
| 397 return _traverseRefs(id.name, queue); | |
| 398 }); | |
| 399 }); | |
| 400 } | |
| 401 | |
| 402 /// Traverses the references that [depender] depends on, stored in [refs]. | |
| 403 /// Desctructively modifies [refs]. Completes to a list of packages if the | |
| 404 /// traversal is complete. Completes it to an error if a failure occurred. | |
| 405 /// Otherwise, recurses. | |
| 406 Future<List<PackageId>> _traverseRefs(String depender, | |
| 407 Queue<PackageRef> refs) { | |
| 408 // Move onto the next package if we've traversed all of these references. | |
| 409 if (refs.isEmpty) return _traversePackage(); | |
| 410 | |
| 411 // Pump the event loop to flatten the stack trace and workaround #9583. | |
| 412 // If that bug is fixed, this can be Future.sync() instead. | |
| 413 return new Future(() { | |
| 414 var ref = refs.removeFirst(); | |
| 415 | |
| 416 _validateDependency(ref, depender); | |
| 417 var constraint = _addConstraint(ref, depender); | |
| 418 | |
| 419 var selected = _validateSelected(ref, constraint); | |
| 420 if (selected != null) { | |
| 421 // The selected package version is good, so enqueue it to traverse into | |
| 422 // it. | |
| 423 _packages.add(selected); | |
| 424 return _traverseRefs(depender, refs); | |
| 425 } | |
| 426 | |
| 427 // We haven't selected a version. Get all of the versions that match the | |
| 428 // constraints we currently have for this package and add them to the | |
| 429 // set of solutions to try. | |
| 430 return _selectPackage(ref, constraint).then( | |
| 431 (_) => _traverseRefs(depender, refs)); | |
| 432 }); | |
| 433 } | |
| 434 | |
| 435 /// Ensures that dependency [ref] from [depender] is consistent with the | |
| 436 /// other dependencies on the same package. Throws a [SolverFailure] | |
| 437 /// exception if not. Only validates sources and descriptions, not the | |
| 438 /// version. | |
| 439 void _validateDependency(PackageRef ref, String depender) { | |
| 440 // Make sure the dependencies agree on source and description. | |
| 441 var required = _getRequired(ref.name); | |
| 442 if (required == null) return; | |
| 443 | |
| 444 // Make sure all of the existing sources match the new reference. | |
| 445 if (required.ref.source.name != ref.source.name) { | |
| 446 _solver.logSolve('source mismatch on ${ref.name}: ${required.ref.source} ' | |
| 447 '!= ${ref.source}'); | |
| 448 throw new SourceMismatchException(ref.name, | |
| 449 [required, new Dependency(depender, ref)]); | |
| 450 } | |
| 451 | |
| 452 // Make sure all of the existing descriptions match the new reference. | |
| 453 if (!ref.descriptionEquals(required.ref)) { | |
| 454 _solver.logSolve('description mismatch on ${ref.name}: ' | |
| 455 '${required.ref.description} != ${ref.description}'); | |
| 456 throw new DescriptionMismatchException(ref.name, | |
| 457 [required, new Dependency(depender, ref)]); | |
| 458 } | |
| 459 } | |
| 460 | |
| 461 /// Adds the version constraint that [depender] places on [ref] to the | |
| 462 /// overall constraint that all shared dependencies place on [ref]. Throws a | |
| 463 /// [SolverFailure] if that results in an unsolvable constraints. | |
| 464 /// | |
| 465 /// Returns the combined [VersionConstraint] that all dependers place on the | |
| 466 /// package. | |
| 467 VersionConstraint _addConstraint(PackageRef ref, String depender) { | |
| 468 // Add the dependency. | |
| 469 var dependencies = _getDependencies(ref.name); | |
| 470 dependencies.add(new Dependency(depender, ref)); | |
| 471 | |
| 472 // Determine the overall version constraint. | |
| 473 var constraint = dependencies | |
| 474 .map((dep) => dep.ref.constraint) | |
| 475 .fold(VersionConstraint.any, (a, b) => a.intersect(b)); | |
| 476 | |
| 477 // See if it's possible for a package to match that constraint. | |
| 478 if (constraint.isEmpty) { | |
| 479 _solver.logSolve('disjoint constraints on ${ref.name}'); | |
| 480 throw new DisjointConstraintException(ref.name, dependencies); | |
| 481 } | |
| 482 | |
| 483 return constraint; | |
| 484 } | |
| 485 | |
| 486 /// Validates the currently selected package against the new dependency that | |
| 487 /// [ref] and [constraint] place on it. Returns `null` if there is no | |
| 488 /// currently selected package, throws a [SolverFailure] if the new reference | |
| 489 /// it not does not allow the previously selected version, or returns the | |
| 490 /// selected package if successful. | |
| 491 PackageId _validateSelected(PackageRef ref, VersionConstraint constraint) { | |
| 492 var selected = _solver.getSelected(ref.name); | |
| 493 if (selected == null) return null; | |
| 494 | |
| 495 // Make sure it meets the constraint. | |
| 496 if (!ref.constraint.allows(selected.version)) { | |
| 497 _solver.logSolve('selection $selected does not match $constraint'); | |
| 498 throw new NoVersionException(ref.name, constraint, | |
| 499 _getDependencies(ref.name)); | |
| 500 } | |
| 501 | |
| 502 return selected; | |
| 503 } | |
| 504 | |
| 505 /// Tries to select a package that matches [ref] and [constraint]. Updates | |
| 506 /// the solver state so that we can backtrack from this decision if it turns | |
| 507 /// out wrong, but continues traversing with the new selection. | |
| 508 /// | |
| 509 /// Returns a future that completes with a [SolverFailure] if a version | |
| 510 /// could not be selected or that completes successfully if a package was | |
| 511 /// selected and traversing should continue. | |
| 512 Future _selectPackage(PackageRef ref, VersionConstraint constraint) { | |
| 513 return _solver.cache.getVersions(ref.name, ref.source, ref.description) | |
| 514 .then((versions) { | |
| 515 var allowed = versions.where((id) => constraint.allows(id.version)); | |
| 516 | |
| 517 // See if it's in the lockfile. If so, try that version first. If the | |
| 518 // locked version doesn't match our constraint, just ignore it. | |
| 519 var locked = _getValidLocked(ref.name, constraint); | |
| 520 if (locked != null) { | |
| 521 allowed = allowed.where((ref) => ref.version != locked.version) | |
| 522 .toList(); | |
| 523 allowed.insert(0, locked); | |
| 524 } | |
| 525 | |
| 526 if (allowed.isEmpty) { | |
| 527 _solver.logSolve('no versions for ${ref.name} match $constraint'); | |
| 528 throw new NoVersionException(ref.name, constraint, | |
| 529 _getDependencies(ref.name)); | |
| 530 } | |
| 531 | |
| 532 // If we're doing an upgrade on this package, only allow the latest | |
| 533 // version. | |
| 534 if (_solver._forceLatest.contains(ref.name)) allowed = [allowed.first]; | |
| 535 | |
| 536 // Try the first package in the allowed set and keep track of the list of | |
| 537 // other possible versions in case that fails. | |
| 538 _packages.add(_solver.select(allowed)); | |
| 539 }); | |
| 540 } | |
| 541 | |
| 542 /// Gets the list of dependencies for package [name]. Will create an empty | |
| 543 /// list if needed. | |
| 544 List<Dependency> _getDependencies(String name) { | |
| 545 return _dependencies.putIfAbsent(name, () => <Dependency>[]); | |
| 546 } | |
| 547 | |
| 548 /// Gets a "required" reference to the package [name]. This is the first | |
| 549 /// non-root dependency on that package. All dependencies on a package must | |
| 550 /// agree on source and description, except for references to the root | |
| 551 /// package. This will return a reference to that "canonical" source and | |
| 552 /// description, or `null` if there is no required reference yet. | |
| 553 /// | |
| 554 /// This is required because you may have a circular dependency back onto the | |
| 555 /// root package. That second dependency won't be a root dependency and it's | |
| 556 /// *that* one that other dependencies need to agree on. In other words, you | |
| 557 /// can have a bunch of dependencies back onto the root package as long as | |
| 558 /// they all agree with each other. | |
| 559 Dependency _getRequired(String name) { | |
| 560 return _getDependencies(name) | |
| 561 .firstWhere((dep) => !dep.ref.isRoot, orElse: () => null); | |
| 562 } | |
| 563 | |
| 564 /// Gets the package [name] that's currently contained in the lockfile if it | |
| 565 /// meets [constraint] and has the same source and description as other | |
| 566 /// references to that package. Returns `null` otherwise. | |
| 567 PackageId _getValidLocked(String name, VersionConstraint constraint) { | |
| 568 var package = _solver.getLocked(name); | |
| 569 if (package == null) return null; | |
| 570 | |
| 571 if (!constraint.allows(package.version)) { | |
| 572 _solver.logSolve('$package is locked but does not match $constraint'); | |
| 573 return null; | |
| 574 } else { | |
| 575 _solver.logSolve('$package is locked'); | |
| 576 } | |
| 577 | |
| 578 var required = _getRequired(name); | |
| 579 if (required != null) { | |
| 580 if (package.source.name != required.ref.source.name) return null; | |
| 581 if (!package.descriptionEquals(required.ref)) return null; | |
| 582 } | |
| 583 | |
| 584 return package; | |
| 585 } | |
| 586 } | |
| 587 | |
| 588 /// Ensures that if [pubspec] has an SDK constraint, then it is compatible | |
| 589 /// with the current SDK. Throws a [SolverFailure] if not. | |
| 590 void _validateSdkConstraint(Pubspec pubspec) { | |
| 591 // If the user is running a continouous build of the SDK, just disable SDK | |
| 592 // constraint checking entirely. The actual version number you get is | |
| 593 // impossibly old and not correct. We'll just assume users on continuous | |
| 594 // know what they're doing. | |
| 595 if (sdk.isBleedingEdge) return; | |
| 596 | |
| 597 if (pubspec.environment.sdkVersion.allows(sdk.version)) return; | |
| 598 | |
| 599 throw new CouldNotSolveException( | |
| 600 'Package ${pubspec.name} requires SDK version ' | |
| 601 '${pubspec.environment.sdkVersion} but the current SDK is ' | |
| 602 '${sdk.version}.'); | |
| 603 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 14297021:
Move pub into sdk/lib/_internal. (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart