| 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 /// Attempts to resolve a set of version constraints for a package dependency | |
| 6 /// graph and select an appropriate set of best specific versions for all | |
| 7 /// dependent packages. It works iteratively and tries to reach a stable | |
| 8 /// solution where the constraints of all dependencies are met. If it fails to | |
| 9 /// reach a solution after a certain number of iterations, it assumes the | |
| 10 /// dependency graph is unstable and reports and error. | |
| 11 /// | |
| 12 /// There are two fundamental operations in the process of iterating over the | |
| 13 /// graph: | |
| 14 /// | |
| 15 /// 1. Changing the selected concrete version of some package. (This includes | |
| 16 /// adding and removing a package too, which is considering changing the | |
| 17 /// version to or from "none".) In other words, a node has changed. | |
| 18 /// 2. Changing the version constraint that one package places on another. In | |
| 19 /// other words, and edge has changed. | |
| 20 /// | |
| 21 /// Both of these events have a corresponding (potentional) async operation and | |
| 22 /// roughly cycle back and forth between each other. When we change the version | |
| 23 /// of package changes, we asynchronously load the pubspec for the new version. | |
| 24 /// When that's done, we compare the dependencies of the new version versus the | |
| 25 /// old one. For everything that differs, we change those constraints between | |
| 26 /// this package and that dependency. | |
| 27 /// | |
| 28 /// When a constraint on a package changes, we re-calculate the overall | |
| 29 /// constraint on that package. I.e. with a shared dependency, we intersect all | |
| 30 /// of the constraints that its depending packages place on it. If that overall | |
| 31 /// constraint changes (say from "<3.0.0" to "<2.5.0"), then the currently | |
| 32 /// picked version for that package may fall outside of the new constraint. If | |
| 33 /// that happens, we find the new best version that meets the updated constraint | |
| 34 /// and then the change the package to use that version. That cycles back up to | |
| 35 /// the beginning again. | |
| 36 library version_solver; | |
| 37 | |
| 38 import 'dart:async'; | |
| 39 import 'dart:collection' show Queue; | |
| 40 import 'dart:json' as json; | |
| 41 import 'dart:math'; | |
| 42 import 'lock_file.dart'; | |
| 43 import 'log.dart' as log; | |
| 44 import 'package.dart'; | |
| 45 import 'pubspec.dart'; | |
| 46 import 'source.dart'; | |
| 47 import 'source_registry.dart'; | |
| 48 import 'utils.dart'; | |
| 49 import 'version.dart'; | |
| 50 | |
| 51 /// Attempts to select the best concrete versions for all of the transitive | |
| 52 /// dependencies of [root] taking into account all of the [VersionConstraint]s | |
| 53 /// that those dependencies place on each other and the requirements imposed by | |
| 54 /// [lockFile]. If successful, completes to a [Map] that maps package names to | |
| 55 /// the selected version for that package. If it fails, the future will complete | |
| 56 /// with a [NoVersionException], [DisjointConstraintException], or | |
| 57 /// [CouldNotSolveException]. | |
| 58 Future<List<PackageId>> resolveVersions(SourceRegistry sources, Package root, | |
| 59 LockFile lockFile) { | |
| 60 log.message('Resolving dependencies...'); | |
| 61 return new VersionSolver(sources, root, lockFile).solve(); | |
| 62 } | |
| 63 | |
| 64 class VersionSolver { | |
| 65 final SourceRegistry _sources; | |
| 66 final Package _root; | |
| 67 final LockFile lockFile; | |
| 68 final PubspecCache _pubspecs; | |
| 69 final Map<String, Dependency> _packages; | |
| 70 final Queue<WorkItem> _work; | |
| 71 int _numIterations = 0; | |
| 72 | |
| 73 VersionSolver(SourceRegistry sources, this._root, this.lockFile) | |
| 74 : _sources = sources, | |
| 75 _pubspecs = new PubspecCache(sources), | |
| 76 _packages = <String, Dependency>{}, | |
| 77 _work = new Queue<WorkItem>(); | |
| 78 | |
| 79 /// Tell the version solver to use the most recent version of [package] that | |
| 80 /// exists in whatever source it's installed from. If that version violates | |
| 81 /// constraints imposed by other dependencies, an error will be raised when | |
| 82 /// solving the versions, even if an earlier compatible version exists. | |
| 83 void useLatestVersion(String package) { | |
| 84 // TODO(nweiz): How do we want to detect and handle unknown dependencies | |
| 85 // here? | |
| 86 getDependency(package).useLatestVersion = true; | |
| 87 lockFile.packages.remove(package); | |
| 88 } | |
| 89 | |
| 90 Future<List<PackageId>> solve() { | |
| 91 // Kick off the work by adding the root package at its concrete version to | |
| 92 // the dependency graph. | |
| 93 var ref = new PackageRef.root(_root); | |
| 94 enqueue(new AddConstraint('(entrypoint)', ref)); | |
| 95 _pubspecs.cache(ref.atVersion(_root.version), _root.pubspec); | |
| 96 | |
| 97 Future processNextWorkItem(_) { | |
| 98 while (true) { | |
| 99 // Stop if we are done. | |
| 100 if (_work.isEmpty) return new Future.value(buildResults()); | |
| 101 | |
| 102 // If we appear to be stuck in a loop, then we probably have an unstable | |
| 103 // graph, bail. We guess this based on a rough heuristic that it should | |
| 104 // only take a certain number of steps to solve a graph with a given | |
| 105 // number of connections. | |
| 106 // TODO(rnystrom): These numbers here are magic and arbitrary. Tune | |
| 107 // when we have a better picture of real-world package topologies. | |
| 108 _numIterations++; | |
| 109 if (_numIterations > max(50, _packages.length * 5)) { | |
| 110 throw new CouldNotSolveException(); | |
| 111 } | |
| 112 | |
| 113 // Run the first work item. | |
| 114 var future = _work.removeFirst().process(this); | |
| 115 | |
| 116 // If we have an async operation to perform, chain the loop to resume | |
| 117 // when it's done. Otherwise, just loop synchronously. | |
| 118 if (future != null) { | |
| 119 return future.then(processNextWorkItem); | |
| 120 } | |
| 121 } | |
| 122 } | |
| 123 | |
| 124 return processNextWorkItem(null); | |
| 125 } | |
| 126 | |
| 127 void enqueue(WorkItem work) { | |
| 128 _work.add(work); | |
| 129 } | |
| 130 | |
| 131 Dependency getDependency(String package) { | |
| 132 // There can be unused dependencies in the graph, so just create an empty | |
| 133 // one if needed. | |
| 134 _packages.putIfAbsent(package, () => new Dependency(package)); | |
| 135 return _packages[package]; | |
| 136 } | |
| 137 | |
| 138 /// Sets the best selected version of [package] to [version]. | |
| 139 void setVersion(String package, Version version) { | |
| 140 _packages[package].version = version; | |
| 141 } | |
| 142 | |
| 143 /// Returns the most recent version of [dependency] that satisfies all of its | |
| 144 /// version constraints. | |
| 145 Future<Version> getBestVersion(Dependency dependency) { | |
| 146 return dependency.getVersions().then((versions) { | |
| 147 var best = null; | |
| 148 for (var version in versions) { | |
| 149 if (dependency.useLatestVersion || | |
| 150 dependency.constraint.allows(version)) { | |
| 151 if (best == null || version > best) best = version; | |
| 152 } | |
| 153 } | |
| 154 | |
| 155 // TODO(rnystrom): Better exception. | |
| 156 if (best == null) { | |
| 157 if (tryUnlockDepender(dependency)) return null; | |
| 158 throw new NoVersionException(dependency.name, dependency.constraint, | |
| 159 dependency._refs); | |
| 160 } else if (!dependency.constraint.allows(best)) { | |
| 161 if (tryUnlockDepender(dependency)) return null; | |
| 162 throw new CouldNotUpdateException( | |
| 163 dependency.name, dependency.constraint, best); | |
| 164 } | |
| 165 | |
| 166 return best; | |
| 167 }); | |
| 168 } | |
| 169 | |
| 170 /// Looks for a package that depends (transitively) on [dependency] and has | |
| 171 /// its version locked in the lockfile. If one is found, enqueues an | |
| 172 /// [UnlockPackage] work item for it and returns true. Otherwise, returns | |
| 173 /// false. | |
| 174 /// | |
| 175 /// This does a breadth-first search; immediate dependers will be unlocked | |
| 176 /// first, followed by transitive dependers. | |
| 177 bool tryUnlockDepender(Dependency dependency, [Set<String> seen]) { | |
| 178 if (seen == null) seen = new Set(); | |
| 179 // Avoid an infinite loop if there are circular dependencies. | |
| 180 if (seen.contains(dependency.name)) return false; | |
| 181 seen.add(dependency.name); | |
| 182 | |
| 183 for (var dependerName in dependency.dependers) { | |
| 184 var depender = getDependency(dependerName); | |
| 185 var locked = lockFile.packages[dependerName]; | |
| 186 if (locked != null && depender.version == locked.version && | |
| 187 depender.source.name == locked.source.name) { | |
| 188 enqueue(new UnlockPackage(depender)); | |
| 189 return true; | |
| 190 } | |
| 191 } | |
| 192 | |
| 193 return dependency.dependers.map(getDependency).any((subdependency) => | |
| 194 tryUnlockDepender(subdependency, seen)); | |
| 195 } | |
| 196 | |
| 197 List<PackageId> buildResults() { | |
| 198 return _packages.values.where((dep) => dep.isDependedOn).map((dep) { | |
| 199 var description = dep.description; | |
| 200 | |
| 201 // If the lockfile contains a fully-resolved description for the package, | |
| 202 // use that. This allows e.g. Git to ensure that the same commit is used. | |
| 203 var lockedPackage = lockFile.packages[dep.name]; | |
| 204 if (lockedPackage != null && lockedPackage.version == dep.version && | |
| 205 lockedPackage.source.name == dep.source.name && | |
| 206 dep.source.descriptionsEqual( | |
| 207 description, lockedPackage.description)) { | |
| 208 description = lockedPackage.description; | |
| 209 } | |
| 210 | |
| 211 return new PackageId(dep.name, dep.source, dep.version, description); | |
| 212 }) | |
| 213 .toList(); | |
| 214 } | |
| 215 } | |
| 216 | |
| 217 /// The constraint solver works by iteratively processing a queue of work items. | |
| 218 /// Each item is a single atomic change to the dependency graph. Handling them | |
| 219 /// in a queue lets us handle asynchrony (resolving versions requires | |
| 220 /// information from servers) as well as avoid deeply nested recursion. | |
| 221 abstract class WorkItem { | |
| 222 /// Processes this work item. Returns a future that completes when the work is | |
| 223 /// done. If `null` is returned, that means the work has completed | |
| 224 /// synchronously and the next item can be started immediately. | |
| 225 Future process(VersionSolver solver); | |
| 226 } | |
| 227 | |
| 228 /// The best selected version for a package has changed to [version]. If the | |
| 229 /// previous version of the package is `null`, that means the package is being | |
| 230 /// added to the graph. If [version] is `null`, it is being removed. | |
| 231 class ChangeVersion implements WorkItem { | |
| 232 /// The name of the package whose version is being changed. | |
| 233 final String package; | |
| 234 | |
| 235 /// The source of the package whose version is changing. | |
| 236 final Source source; | |
| 237 | |
| 238 /// The description identifying the package whose version is changing. | |
| 239 final description; | |
| 240 | |
| 241 /// The new selected version. | |
| 242 final Version version; | |
| 243 | |
| 244 ChangeVersion(this.package, this.source, this.description, this.version); | |
| 245 | |
| 246 Future process(VersionSolver solver) { | |
| 247 log.fine("Changing $package to version $version."); | |
| 248 | |
| 249 var dependency = solver.getDependency(package); | |
| 250 var oldVersion = dependency.version; | |
| 251 solver.setVersion(package, version); | |
| 252 | |
| 253 // The dependencies between the old and new version may be different. Walk | |
| 254 // them both and update any constraints that differ between the two. | |
| 255 return Future.wait([ | |
| 256 getDependencyRefs(solver, oldVersion), | |
| 257 getDependencyRefs(solver, version)]).then((list) { | |
| 258 var oldDependencyRefs = list[0]; | |
| 259 var newDependencyRefs = list[1]; | |
| 260 | |
| 261 for (var oldRef in oldDependencyRefs.values) { | |
| 262 if (newDependencyRefs.containsKey(oldRef.name)) { | |
| 263 // The dependency is in both versions of this package, but its | |
| 264 // constraint may have changed. | |
| 265 var newRef = newDependencyRefs.remove(oldRef.name); | |
| 266 solver.enqueue(new AddConstraint(package, newRef)); | |
| 267 } else { | |
| 268 // The dependency is not in the new version of the package, so just | |
| 269 // remove its constraint. | |
| 270 solver.enqueue(new RemoveConstraint(package, oldRef.name)); | |
| 271 } | |
| 272 } | |
| 273 | |
| 274 // Everything that's left is a depdendency that's only in the new | |
| 275 // version of the package. | |
| 276 for (var newRef in newDependencyRefs.values) { | |
| 277 solver.enqueue(new AddConstraint(package, newRef)); | |
| 278 } | |
| 279 }); | |
| 280 } | |
| 281 | |
| 282 /// Get the dependencies at [version] of the package being changed. | |
| 283 Future<Map<String, PackageRef>> getDependencyRefs(VersionSolver solver, | |
| 284 Version version) { | |
| 285 // If there is no version, it means no package, so no dependencies. | |
| 286 if (version == null) { | |
| 287 return new Future<Map<String, PackageRef>>.value(<String, PackageRef>{}); | |
| 288 } | |
| 289 | |
| 290 var id = new PackageId(package, source, version, description); | |
| 291 return solver._pubspecs.load(id).then((pubspec) { | |
| 292 var dependencies = <String, PackageRef>{}; | |
| 293 for (var dependency in pubspec.dependencies) { | |
| 294 dependencies[dependency.name] = dependency; | |
| 295 } | |
| 296 | |
| 297 // Include dev dependencies only from the root package. | |
| 298 if (id.isRoot) { | |
| 299 for (var dependency in pubspec.devDependencies) { | |
| 300 dependencies[dependency.name] = dependency; | |
| 301 } | |
| 302 } | |
| 303 | |
| 304 return dependencies; | |
| 305 }); | |
| 306 } | |
| 307 } | |
| 308 | |
| 309 /// A constraint that a depending package places on a dependent package has | |
| 310 /// changed. | |
| 311 /// | |
| 312 /// This is an abstract class that contains logic for updating the dependency | |
| 313 /// graph once a dependency has changed. Changing the dependency is the | |
| 314 /// responsibility of subclasses. | |
| 315 abstract class ChangeConstraint implements WorkItem { | |
| 316 Future process(VersionSolver solver); | |
| 317 | |
| 318 void undo(VersionSolver solver); | |
| 319 | |
| 320 Future _processChange(VersionSolver solver, Dependency oldDependency, | |
| 321 Dependency newDependency) { | |
| 322 var name = newDependency.name; | |
| 323 var source = oldDependency.source != null ? | |
| 324 oldDependency.source : newDependency.source; | |
| 325 var description = oldDependency.description != null ? | |
| 326 oldDependency.description : newDependency.description; | |
| 327 var oldConstraint = oldDependency.constraint; | |
| 328 var newConstraint = newDependency.constraint; | |
| 329 | |
| 330 // If the package is over-constrained, i.e. the packages depending have | |
| 331 // disjoint constraints, then try unlocking a depender that's locked by the | |
| 332 // lockfile. If there are no remaining locked dependencies, throw an error. | |
| 333 if (newConstraint != null && newConstraint.isEmpty) { | |
| 334 if (solver.tryUnlockDepender(newDependency)) { | |
| 335 undo(solver); | |
| 336 return null; | |
| 337 } | |
| 338 | |
| 339 throw new DisjointConstraintException(name, newDependency._refs); | |
| 340 } | |
| 341 | |
| 342 // If this constraint change didn't cause the overall constraint on the | |
| 343 // package to change, then we don't need to do any further work. | |
| 344 if (oldConstraint == newConstraint) return null; | |
| 345 | |
| 346 // If the dependency has been cut free from the graph, just remove it. | |
| 347 if (!newDependency.isDependedOn) { | |
| 348 solver.enqueue(new ChangeVersion(name, source, description, null)); | |
| 349 return null; | |
| 350 } | |
| 351 | |
| 352 // If the dependency is on the root package, then we don't need to do | |
| 353 // anything since it's already at the best version. | |
| 354 if (name == solver._root.name) { | |
| 355 solver.enqueue(new ChangeVersion( | |
| 356 name, source, description, solver._root.version)); | |
| 357 return null; | |
| 358 } | |
| 359 | |
| 360 // If the dependency is on a package in the lockfile, use the lockfile's | |
| 361 // version for that package if it's valid given the other constraints. | |
| 362 var lockedPackage = solver.lockFile.packages[name]; | |
| 363 if (lockedPackage != null && newDependency.source == lockedPackage.source) { | |
| 364 var lockedVersion = lockedPackage.version; | |
| 365 if (newConstraint.allows(lockedVersion)) { | |
| 366 solver.enqueue( | |
| 367 new ChangeVersion(name, source, description, lockedVersion)); | |
| 368 return null; | |
| 369 } | |
| 370 } | |
| 371 | |
| 372 // The constraint has changed, so see what the best version of the package | |
| 373 // that meets the new constraint is. | |
| 374 return solver.getBestVersion(newDependency).then((best) { | |
| 375 if (best == null) { | |
| 376 undo(solver); | |
| 377 } else if (newDependency.version != best) { | |
| 378 solver.enqueue(new ChangeVersion(name, source, description, best)); | |
| 379 } | |
| 380 }); | |
| 381 } | |
| 382 } | |
| 383 | |
| 384 /// The constraint given by [ref] is being placed by [depender]. | |
| 385 class AddConstraint extends ChangeConstraint { | |
| 386 /// The package that has the dependency. | |
| 387 final String depender; | |
| 388 | |
| 389 /// The package being depended on and the constraints being placed on it. The | |
| 390 /// source, version, and description in this ref are all considered | |
| 391 /// constraints on the dependent package. | |
| 392 final PackageRef ref; | |
| 393 | |
| 394 AddConstraint(this.depender, this.ref); | |
| 395 | |
| 396 Future process(VersionSolver solver) { | |
| 397 log.fine("Adding $depender's constraint $ref."); | |
| 398 | |
| 399 var dependency = solver.getDependency(ref.name); | |
| 400 var oldDependency = dependency.clone(); | |
| 401 dependency.placeConstraint(depender, ref); | |
| 402 return _processChange(solver, oldDependency, dependency); | |
| 403 } | |
| 404 | |
| 405 void undo(VersionSolver solver) { | |
| 406 solver.getDependency(ref.name).removeConstraint(depender); | |
| 407 } | |
| 408 } | |
| 409 | |
| 410 /// [depender] is no longer placing a constraint on [dependent]. | |
| 411 class RemoveConstraint extends ChangeConstraint { | |
| 412 /// The package that was placing a constraint on [dependent]. | |
| 413 String depender; | |
| 414 | |
| 415 /// The package that was being depended on. | |
| 416 String dependent; | |
| 417 | |
| 418 /// The constraint that was removed. | |
| 419 PackageRef _removed; | |
| 420 | |
| 421 RemoveConstraint(this.depender, this.dependent); | |
| 422 | |
| 423 Future process(VersionSolver solver) { | |
| 424 log.fine("Removing $depender's constraint ($_removed) on $dependent."); | |
| 425 | |
| 426 var dependency = solver.getDependency(dependent); | |
| 427 var oldDependency = dependency.clone(); | |
| 428 _removed = dependency.removeConstraint(depender); | |
| 429 return _processChange(solver, oldDependency, dependency); | |
| 430 } | |
| 431 | |
| 432 void undo(VersionSolver solver) { | |
| 433 solver.getDependency(dependent).placeConstraint(depender, _removed); | |
| 434 } | |
| 435 } | |
| 436 | |
| 437 /// [package]'s version is no longer constrained by the lockfile. | |
| 438 class UnlockPackage implements WorkItem { | |
| 439 /// The package being unlocked. | |
| 440 Dependency package; | |
| 441 | |
| 442 UnlockPackage(this.package); | |
| 443 | |
| 444 Future process(VersionSolver solver) { | |
| 445 log.fine("Unlocking ${package.name}."); | |
| 446 | |
| 447 solver.lockFile.packages.remove(package.name); | |
| 448 return solver.getBestVersion(package).then((best) { | |
| 449 if (best == null) return null; | |
| 450 solver.enqueue(new ChangeVersion( | |
| 451 package.name, package.source, package.description, best)); | |
| 452 }); | |
| 453 } | |
| 454 } | |
| 455 | |
| 456 // TODO(rnystrom): Instead of always pulling from the source (which will mean | |
| 457 // hitting a server), we should consider caching pubspecs of uninstalled | |
| 458 // packages in the system cache. | |
| 459 /// Maintains a cache of previously-loaded pubspecs. Used to avoid requesting | |
| 460 /// the same pubspec from the server repeatedly. | |
| 461 class PubspecCache { | |
| 462 final SourceRegistry _sources; | |
| 463 final Map<PackageId, Pubspec> _pubspecs; | |
| 464 | |
| 465 PubspecCache(this._sources) | |
| 466 : _pubspecs = new Map<PackageId, Pubspec>(); | |
| 467 | |
| 468 /// Caches [pubspec] as the [Pubspec] for the package identified by [id]. | |
| 469 void cache(PackageId id, Pubspec pubspec) { | |
| 470 _pubspecs[id] = pubspec; | |
| 471 } | |
| 472 | |
| 473 /// Loads the pubspec for the package identified by [id]. | |
| 474 Future<Pubspec> load(PackageId id) { | |
| 475 // Complete immediately if it's already cached. | |
| 476 if (_pubspecs.containsKey(id)) { | |
| 477 return new Future<Pubspec>.value(_pubspecs[id]); | |
| 478 } | |
| 479 | |
| 480 return id.describe().then((pubspec) { | |
| 481 // Cache it. | |
| 482 _pubspecs[id] = pubspec; | |
| 483 return pubspec; | |
| 484 }); | |
| 485 } | |
| 486 } | |
| 487 | |
| 488 /// Describes one [Package] in the [DependencyGraph] and keeps track of which | |
| 489 /// packages depend on it and what constraints they place on it. | |
| 490 class Dependency { | |
| 491 /// The name of the this dependency's package. | |
| 492 final String name; | |
| 493 | |
| 494 /// The [PackageRefs] that represent constraints that depending packages have | |
| 495 /// placed on this one. | |
| 496 final Map<String, PackageRef> _refs; | |
| 497 | |
| 498 /// The currently-selected best version for this dependency. | |
| 499 Version version; | |
| 500 | |
| 501 /// Whether this dependency should always select the latest version. | |
| 502 bool useLatestVersion = false; | |
| 503 | |
| 504 /// Gets whether or not any other packages are currently depending on this | |
| 505 /// one. If `false`, then it means this package is not part of the dependency | |
| 506 /// graph and should be omitted. | |
| 507 bool get isDependedOn => !_refs.isEmpty; | |
| 508 | |
| 509 /// The names of all the packages that depend on this dependency. | |
| 510 Iterable<String> get dependers => _refs.keys; | |
| 511 | |
| 512 /// Gets the overall constraint that all packages are placing on this one. | |
| 513 /// If no packages have a constraint on this one (which can happen when this | |
| 514 /// package is in the process of being added to the graph), returns `null`. | |
| 515 VersionConstraint get constraint { | |
| 516 if (_refs.isEmpty) return null; | |
| 517 return new VersionConstraint.intersection( | |
| 518 _refs.values.map((ref) => ref.constraint)); | |
| 519 } | |
| 520 | |
| 521 /// The source of this dependency's package. | |
| 522 Source get source { | |
| 523 var canonical = _canonicalRef(); | |
| 524 if (canonical == null) return null; | |
| 525 return canonical.source; | |
| 526 } | |
| 527 | |
| 528 /// The description of this dependency's package. | |
| 529 get description { | |
| 530 var canonical = _canonicalRef(); | |
| 531 if (canonical == null) return null; | |
| 532 return canonical.description; | |
| 533 } | |
| 534 | |
| 535 /// Return the PackageRef that has the canonical source and description for | |
| 536 /// this package. If any dependency is on the root package, that will be used; | |
| 537 /// otherwise, it will be the source and description that all dependencies | |
| 538 /// agree upon. | |
| 539 PackageRef _canonicalRef() { | |
| 540 if (_refs.isEmpty) return null; | |
| 541 var refs = _refs.values; | |
| 542 for (var ref in refs) { | |
| 543 if (ref.isRoot) return ref; | |
| 544 } | |
| 545 return refs.first; | |
| 546 } | |
| 547 | |
| 548 Dependency(this.name) | |
| 549 : _refs = <String, PackageRef>{}; | |
| 550 | |
| 551 Dependency._clone(Dependency other) | |
| 552 : name = other.name, | |
| 553 version = other.version, | |
| 554 _refs = new Map<String, PackageRef>.from(other._refs); | |
| 555 | |
| 556 /// Creates a copy of this dependency. | |
| 557 Dependency clone() => new Dependency._clone(this); | |
| 558 | |
| 559 /// Return a list of available versions for this dependency. | |
| 560 Future<List<Version>> getVersions() => source.getVersions(name, description); | |
| 561 | |
| 562 /// Places [ref] as a constraint from [package] onto this. | |
| 563 void placeConstraint(String package, PackageRef ref) { | |
| 564 var requiredDepender = _requiredDepender(); | |
| 565 if (requiredDepender != null) { | |
| 566 var required = _refs[requiredDepender]; | |
| 567 if (required.source.name != ref.source.name) { | |
| 568 throw new SourceMismatchException(name, | |
| 569 requiredDepender, required.source, package, ref.source); | |
| 570 } else if (!required.source.descriptionsEqual( | |
| 571 required.description, ref.description)) { | |
| 572 throw new DescriptionMismatchException(name, | |
| 573 requiredDepender, required.description, package, ref.description); | |
| 574 } | |
| 575 } | |
| 576 | |
| 577 _refs[package] = ref; | |
| 578 } | |
| 579 | |
| 580 /// Returns the name of a package whose constraint source and description | |
| 581 /// all other constraints must match. Returns null if there are no | |
| 582 /// requirements on new constraints. | |
| 583 String _requiredDepender() { | |
| 584 if (_refs.isEmpty) return null; | |
| 585 | |
| 586 var dependers = _refs.keys.toList(); | |
| 587 if (dependers.length == 1) { | |
| 588 var depender = dependers[0]; | |
| 589 if (_refs[depender].isRoot) return null; | |
| 590 return depender; | |
| 591 } | |
| 592 | |
| 593 return dependers[1]; | |
| 594 } | |
| 595 | |
| 596 /// Removes the constraint from [package] onto this. | |
| 597 PackageRef removeConstraint(String package) => _refs.remove(package); | |
| 598 } | |
| 599 | |
| 600 /// Exception thrown when the [VersionConstraint] used to match a package is | |
| 601 /// valid (i.e. non-empty), but there are no released versions of the package | |
| 602 /// that fit that constraint. | |
| 603 class NoVersionException implements Exception { | |
| 604 final String package; | |
| 605 final VersionConstraint constraint; | |
| 606 final Map<String, PackageRef> _dependencies; | |
| 607 | |
| 608 NoVersionException(this.package, this.constraint, this._dependencies); | |
| 609 | |
| 610 String toString() { | |
| 611 var buffer = new StringBuffer(); | |
| 612 buffer.write("Package '$package' has no versions that match $constraint " | |
| 613 "derived from:\n"); | |
| 614 | |
| 615 var keys = new List.from(_dependencies.keys); | |
| 616 keys.sort(); | |
| 617 | |
| 618 for (var key in keys) { | |
| 619 buffer.write("- '$key' depends on version " | |
| 620 "${_dependencies[key].constraint}\n"); | |
| 621 } | |
| 622 | |
| 623 return buffer.toString(); | |
| 624 } | |
| 625 } | |
| 626 | |
| 627 // TODO(rnystrom): Report the list of depending packages and their constraints. | |
| 628 /// Exception thrown when the most recent version of [package] must be selected, | |
| 629 /// but doesn't match the [VersionConstraint] imposed on the package. | |
| 630 class CouldNotUpdateException implements Exception { | |
| 631 final String package; | |
| 632 final VersionConstraint constraint; | |
| 633 final Version best; | |
| 634 | |
| 635 CouldNotUpdateException(this.package, this.constraint, this.best); | |
| 636 | |
| 637 String toString() => | |
| 638 "The latest version of '$package', $best, does not match $constraint."; | |
| 639 } | |
| 640 | |
| 641 /// Exception thrown when the [VersionConstraint] used to match a package is | |
| 642 /// the empty set: in other words, multiple packages depend on it and have | |
| 643 /// conflicting constraints that have no overlap. | |
| 644 class DisjointConstraintException implements Exception { | |
| 645 final String package; | |
| 646 final Map<String, PackageRef> _dependencies; | |
| 647 | |
| 648 DisjointConstraintException(this.package, this._dependencies); | |
| 649 | |
| 650 String toString() { | |
| 651 var buffer = new StringBuffer(); | |
| 652 buffer.write("Incompatible version constraints on '$package':\n"); | |
| 653 | |
| 654 var keys = new List.from(_dependencies.keys); | |
| 655 keys.sort(); | |
| 656 | |
| 657 for (var key in keys) { | |
| 658 buffer.write("- '$key' depends on version " | |
| 659 "${_dependencies[key].constraint}\n"); | |
| 660 } | |
| 661 | |
| 662 return buffer.toString(); | |
| 663 } | |
| 664 } | |
| 665 | |
| 666 /// Exception thrown when the [VersionSolver] fails to find a solution after a | |
| 667 /// certain number of iterations. | |
| 668 class CouldNotSolveException implements Exception { | |
| 669 CouldNotSolveException(); | |
| 670 | |
| 671 String toString() => | |
| 672 "Could not find a solution that met all version constraints."; | |
| 673 } | |
| 674 | |
| 675 /// Exception thrown when two packages with the same name but different sources | |
| 676 /// are depended upon. | |
| 677 class SourceMismatchException implements Exception { | |
| 678 final String package; | |
| 679 final String depender1; | |
| 680 final Source source1; | |
| 681 final String depender2; | |
| 682 final Source source2; | |
| 683 | |
| 684 SourceMismatchException(this.package, this.depender1, this.source1, | |
| 685 this.depender2, this.source2); | |
| 686 | |
| 687 String toString() { | |
| 688 return "Incompatible dependencies on '$package':\n" | |
| 689 "- '$depender1' depends on it from source '$source1'\n" | |
| 690 "- '$depender2' depends on it from source '$source2'"; | |
| 691 } | |
| 692 } | |
| 693 | |
| 694 /// Exception thrown when two packages with the same name and source but | |
| 695 /// different descriptions are depended upon. | |
| 696 class DescriptionMismatchException implements Exception { | |
| 697 final String package; | |
| 698 final String depender1; | |
| 699 final description1; | |
| 700 final String depender2; | |
| 701 final description2; | |
| 702 | |
| 703 DescriptionMismatchException(this.package, this.depender1, this.description1, | |
| 704 this.depender2, this.description2); | |
| 705 | |
| 706 String toString() { | |
| 707 // TODO(nweiz): Dump descriptions to YAML when that's supported. | |
| 708 return "Incompatible dependencies on '$package':\n" | |
| 709 "- '$depender1' depends on it with description " | |
| 710 "${json.stringify(description1)}\n" | |
| 711 "- '$depender2' depends on it with description " | |
| 712 "${json.stringify(description2)}"; | |
| 713 } | |
| 714 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 13095015:
Use backtracking when solving dependency constraints. (Closed)
Base URL: https://dart.googlecode.com/svn/branches/bleeding_edge/dart