| OLD | NEW |
| 1 // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file | 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 | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 /** | 5 /** |
| 6 * Attempts to resolve a set of version constraints for a package dependency | 6 * Attempts to resolve a set of version constraints for a package dependency |
| 7 * graph and select an appropriate set of best specific versions for all | 7 * graph and select an appropriate set of best specific versions for all |
| 8 * dependent packages. It works iteratively and tries to reach a stable | 8 * dependent packages. It works iteratively and tries to reach a stable |
| 9 * solution where the constraints of all dependencies are met. If it fails to | 9 * solution where the constraints of all dependencies are met. If it fails to |
| 10 * reach a solution after a certain number of iterations, it assumes the | 10 * reach a solution after a certain number of iterations, it assumes the |
| (...skipping 75 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 86 void useLatestVersion(String package) { | 86 void useLatestVersion(String package) { |
| 87 // TODO(nweiz): How do we want to detect and handle unknown dependencies | 87 // TODO(nweiz): How do we want to detect and handle unknown dependencies |
| 88 // here? | 88 // here? |
| 89 getDependency(package).useLatestVersion = true; | 89 getDependency(package).useLatestVersion = true; |
| 90 lockFile.packages.remove(package); | 90 lockFile.packages.remove(package); |
| 91 } | 91 } |
| 92 | 92 |
| 93 Future<List<PackageId>> solve() { | 93 Future<List<PackageId>> solve() { |
| 94 // Kick off the work by adding the root package at its concrete version to | 94 // Kick off the work by adding the root package at its concrete version to |
| 95 // the dependency graph. | 95 // the dependency graph. |
| 96 var ref = new PackageRef(new RootSource(_root), _root.version, _root.name); | 96 var ref = new PackageRef( |
| 97 _root.name, new RootSource(_root), _root.version, _root.name); |
| 97 enqueue(new AddConstraint('(entrypoint)', ref)); | 98 enqueue(new AddConstraint('(entrypoint)', ref)); |
| 98 _pubspecs.cache(ref.atVersion(_root.version), _root.pubspec); | 99 _pubspecs.cache(ref.atVersion(_root.version), _root.pubspec); |
| 99 | 100 |
| 100 Future processNextWorkItem(_) { | 101 Future processNextWorkItem(_) { |
| 101 while (true) { | 102 while (true) { |
| 102 // Stop if we are done. | 103 // Stop if we are done. |
| 103 if (_work.isEmpty()) return new Future.immediate(buildResults()); | 104 if (_work.isEmpty()) return new Future.immediate(buildResults()); |
| 104 | 105 |
| 105 // If we appear to be stuck in a loop, then we probably have an unstable | 106 // If we appear to be stuck in a loop, then we probably have an unstable |
| 106 // graph, bail. We guess this based on a rough heuristic that it should | 107 // graph, bail. We guess this based on a rough heuristic that it should |
| (...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 143 */ | 144 */ |
| 144 void setVersion(String package, Version version) { | 145 void setVersion(String package, Version version) { |
| 145 _packages[package].version = version; | 146 _packages[package].version = version; |
| 146 } | 147 } |
| 147 | 148 |
| 148 /** | 149 /** |
| 149 * Returns the most recent version of [dependency] that satisfies all of its | 150 * Returns the most recent version of [dependency] that satisfies all of its |
| 150 * version constraints. | 151 * version constraints. |
| 151 */ | 152 */ |
| 152 Future<Version> getBestVersion(Dependency dependency) { | 153 Future<Version> getBestVersion(Dependency dependency) { |
| 153 return dependency.source.getVersions(dependency.description) | 154 return dependency.getVersions().transform((versions) { |
| 154 .transform((versions) { | |
| 155 var best = null; | 155 var best = null; |
| 156 for (var version in versions) { | 156 for (var version in versions) { |
| 157 if (dependency.useLatestVersion || | 157 if (dependency.useLatestVersion || |
| 158 dependency.constraint.allows(version)) { | 158 dependency.constraint.allows(version)) { |
| 159 if (best == null || version > best) best = version; | 159 if (best == null || version > best) best = version; |
| 160 } | 160 } |
| 161 } | 161 } |
| 162 | 162 |
| 163 // TODO(rnystrom): Better exception. | 163 // TODO(rnystrom): Better exception. |
| 164 if (best == null) { | 164 if (best == null) { |
| (...skipping 37 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 202 // If the lockfile contains a fully-resolved description for the package, | 202 // If the lockfile contains a fully-resolved description for the package, |
| 203 // use that. This allows e.g. Git to ensure that the same commit is used. | 203 // use that. This allows e.g. Git to ensure that the same commit is used. |
| 204 var lockedPackage = lockFile.packages[dep.name]; | 204 var lockedPackage = lockFile.packages[dep.name]; |
| 205 if (lockedPackage != null && lockedPackage.version == dep.version && | 205 if (lockedPackage != null && lockedPackage.version == dep.version && |
| 206 lockedPackage.source.name == dep.source.name && | 206 lockedPackage.source.name == dep.source.name && |
| 207 dep.source.descriptionsEqual( | 207 dep.source.descriptionsEqual( |
| 208 description, lockedPackage.description)) { | 208 description, lockedPackage.description)) { |
| 209 description = lockedPackage.description; | 209 description = lockedPackage.description; |
| 210 } | 210 } |
| 211 | 211 |
| 212 return new PackageId(dep.source, dep.version, description); | 212 return new PackageId(dep.name, dep.source, dep.version, description); |
| 213 }); | 213 }); |
| 214 } | 214 } |
| 215 } | 215 } |
| 216 | 216 |
| 217 /** | 217 /** |
| 218 * The constraint solver works by iteratively processing a queue of work items. | 218 * The constraint solver works by iteratively processing a queue of work items. |
| 219 * Each item is a single atomic change to the dependency graph. Handling them | 219 * Each item is a single atomic change to the dependency graph. Handling them |
| 220 * in a queue lets us handle asynchrony (resolving versions requires information | 220 * in a queue lets us handle asynchrony (resolving versions requires information |
| 221 * from servers) as well as avoid deeply nested recursion. | 221 * from servers) as well as avoid deeply nested recursion. |
| 222 */ | 222 */ |
| 223 abstract class WorkItem { | 223 abstract class WorkItem { |
| 224 /** | 224 /** |
| 225 * Processes this work item. Returns a future that completes when the work is | 225 * Processes this work item. Returns a future that completes when the work is |
| 226 * done. If `null` is returned, that means the work has completed | 226 * done. If `null` is returned, that means the work has completed |
| 227 * synchronously and the next item can be started immediately. | 227 * synchronously and the next item can be started immediately. |
| 228 */ | 228 */ |
| 229 Future process(VersionSolver solver); | 229 Future process(VersionSolver solver); |
| 230 } | 230 } |
| 231 | 231 |
| 232 /** | 232 /** |
| 233 * The best selected version for a package has changed to [version]. If the | 233 * The best selected version for a package has changed to [version]. If the |
| 234 * previous version of the package is `null`, that means the package is being | 234 * previous version of the package is `null`, that means the package is being |
| 235 * added to the graph. If [version] is `null`, it is being removed. | 235 * added to the graph. If [version] is `null`, it is being removed. |
| 236 */ | 236 */ |
| 237 class ChangeVersion implements WorkItem { | 237 class ChangeVersion implements WorkItem { |
| 238 /// The name of the package whose version is being changed. |
| 239 final String package; |
| 240 |
| 238 /** | 241 /** |
| 239 * The source of the package whose version is changing. | 242 * The source of the package whose version is changing. |
| 240 */ | 243 */ |
| 241 final Source source; | 244 final Source source; |
| 242 | 245 |
| 243 /** | 246 /** |
| 244 * The description identifying the package whose version is changing. | 247 * The description identifying the package whose version is changing. |
| 245 */ | 248 */ |
| 246 final description; | 249 final description; |
| 247 | 250 |
| 248 /** | 251 /** |
| 249 * The new selected version. | 252 * The new selected version. |
| 250 */ | 253 */ |
| 251 final Version version; | 254 final Version version; |
| 252 | 255 |
| 253 /** | 256 ChangeVersion(this.package, this.source, this.description, this.version) { |
| 254 * The name of the package whose version is changing. | |
| 255 */ | |
| 256 String get package => source.packageName(description); | |
| 257 | |
| 258 ChangeVersion(this.source, this.description, this.version) { | |
| 259 if (source == null) throw "null source"; | 257 if (source == null) throw "null source"; |
| 260 } | 258 } |
| 261 | 259 |
| 262 Future process(VersionSolver solver) { | 260 Future process(VersionSolver solver) { |
| 263 var dependency = solver.getDependency(package); | 261 var dependency = solver.getDependency(package); |
| 264 var oldVersion = dependency.version; | 262 var oldVersion = dependency.version; |
| 265 solver.setVersion(package, version); | 263 solver.setVersion(package, version); |
| 266 | 264 |
| 267 // The dependencies between the old and new version may be different. Walk | 265 // The dependencies between the old and new version may be different. Walk |
| 268 // them both and update any constraints that differ between the two. | 266 // them both and update any constraints that differ between the two. |
| (...skipping 28 matching lines...) Expand all Loading... |
| 297 * Get the dependencies at [version] of the package being changed. | 295 * Get the dependencies at [version] of the package being changed. |
| 298 */ | 296 */ |
| 299 Future<Map<String, PackageRef>> getDependencyRefs(VersionSolver solver, | 297 Future<Map<String, PackageRef>> getDependencyRefs(VersionSolver solver, |
| 300 Version version) { | 298 Version version) { |
| 301 // If there is no version, it means no package, so no dependencies. | 299 // If there is no version, it means no package, so no dependencies. |
| 302 if (version == null) { | 300 if (version == null) { |
| 303 return | 301 return |
| 304 new Future<Map<String, PackageRef>>.immediate(<String, PackageRef>{}); | 302 new Future<Map<String, PackageRef>>.immediate(<String, PackageRef>{}); |
| 305 } | 303 } |
| 306 | 304 |
| 307 var id = new PackageId(source, version, description); | 305 var id = new PackageId(package, source, version, description); |
| 308 return solver._pubspecs.load(id).transform((pubspec) { | 306 return solver._pubspecs.load(id).transform((pubspec) { |
| 309 var dependencies = <String, PackageRef>{}; | 307 var dependencies = <String, PackageRef>{}; |
| 310 for (var dependency in pubspec.dependencies) { | 308 for (var dependency in pubspec.dependencies) { |
| 311 dependencies[dependency.name] = dependency; | 309 dependencies[dependency.name] = dependency; |
| 312 } | 310 } |
| 313 return dependencies; | 311 return dependencies; |
| 314 }); | 312 }); |
| 315 } | 313 } |
| 316 } | 314 } |
| 317 | 315 |
| (...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 349 | 347 |
| 350 throw new DisjointConstraintException(name); | 348 throw new DisjointConstraintException(name); |
| 351 } | 349 } |
| 352 | 350 |
| 353 // If this constraint change didn't cause the overall constraint on the | 351 // If this constraint change didn't cause the overall constraint on the |
| 354 // package to change, then we don't need to do any further work. | 352 // package to change, then we don't need to do any further work. |
| 355 if (oldConstraint == newConstraint) return null; | 353 if (oldConstraint == newConstraint) return null; |
| 356 | 354 |
| 357 // If the dependency has been cut free from the graph, just remove it. | 355 // If the dependency has been cut free from the graph, just remove it. |
| 358 if (!newDependency.isDependedOn) { | 356 if (!newDependency.isDependedOn) { |
| 359 solver.enqueue(new ChangeVersion(source, description, null)); | 357 solver.enqueue(new ChangeVersion(name, source, description, null)); |
| 360 return null; | 358 return null; |
| 361 } | 359 } |
| 362 | 360 |
| 363 // If the dependency is on the root package, then we don't need to do | 361 // If the dependency is on the root package, then we don't need to do |
| 364 // anything since it's already at the best version. | 362 // anything since it's already at the best version. |
| 365 if (name == solver._root.name) { | 363 if (name == solver._root.name) { |
| 366 solver.enqueue(new ChangeVersion( | 364 solver.enqueue(new ChangeVersion( |
| 367 source, description, solver._root.version)); | 365 name, source, description, solver._root.version)); |
| 368 return null; | 366 return null; |
| 369 } | 367 } |
| 370 | 368 |
| 371 // If the dependency is on a package in the lockfile, use the lockfile's | 369 // If the dependency is on a package in the lockfile, use the lockfile's |
| 372 // version for that package if it's valid given the other constraints. | 370 // version for that package if it's valid given the other constraints. |
| 373 var lockedPackage = solver.lockFile.packages[name]; | 371 var lockedPackage = solver.lockFile.packages[name]; |
| 374 if (lockedPackage != null) { | 372 if (lockedPackage != null) { |
| 375 var lockedVersion = lockedPackage.version; | 373 var lockedVersion = lockedPackage.version; |
| 376 if (newConstraint.allows(lockedVersion)) { | 374 if (newConstraint.allows(lockedVersion)) { |
| 377 solver.enqueue(new ChangeVersion(source, description, lockedVersion)); | 375 solver.enqueue( |
| 376 new ChangeVersion(name, source, description, lockedVersion)); |
| 378 return null; | 377 return null; |
| 379 } | 378 } |
| 380 } | 379 } |
| 381 | 380 |
| 382 // The constraint has changed, so see what the best version of the package | 381 // The constraint has changed, so see what the best version of the package |
| 383 // that meets the new constraint is. | 382 // that meets the new constraint is. |
| 384 return solver.getBestVersion(newDependency).transform((best) { | 383 return solver.getBestVersion(newDependency).transform((best) { |
| 385 if (best == null) { | 384 if (best == null) { |
| 386 undo(solver); | 385 undo(solver); |
| 387 } else if (newDependency.version != best) { | 386 } else if (newDependency.version != best) { |
| 388 solver.enqueue(new ChangeVersion(source, description, best)); | 387 solver.enqueue(new ChangeVersion(name, source, description, best)); |
| 389 } | 388 } |
| 390 }); | 389 }); |
| 391 } | 390 } |
| 392 } | 391 } |
| 393 | 392 |
| 394 /** | 393 /** |
| 395 * The constraint given by [ref] is being placed by [depender]. | 394 * The constraint given by [ref] is being placed by [depender]. |
| 396 */ | 395 */ |
| 397 class AddConstraint extends ChangeConstraint { | 396 class AddConstraint extends ChangeConstraint { |
| 398 /** | 397 /** |
| (...skipping 58 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 457 /** The package being unlocked. */ | 456 /** The package being unlocked. */ |
| 458 Dependency package; | 457 Dependency package; |
| 459 | 458 |
| 460 UnlockPackage(this.package); | 459 UnlockPackage(this.package); |
| 461 | 460 |
| 462 Future process(VersionSolver solver) { | 461 Future process(VersionSolver solver) { |
| 463 solver.lockFile.packages.remove(package.name); | 462 solver.lockFile.packages.remove(package.name); |
| 464 return solver.getBestVersion(package).transform((best) { | 463 return solver.getBestVersion(package).transform((best) { |
| 465 if (best == null) return null; | 464 if (best == null) return null; |
| 466 solver.enqueue(new ChangeVersion( | 465 solver.enqueue(new ChangeVersion( |
| 467 package.source, package.description, best)); | 466 package.name, package.source, package.description, best)); |
| 468 }); | 467 }); |
| 469 } | 468 } |
| 470 } | 469 } |
| 471 | 470 |
| 472 // TODO(rnystrom): Instead of always pulling from the source (which will mean | 471 // TODO(rnystrom): Instead of always pulling from the source (which will mean |
| 473 // hitting a server), we should consider caching pubspecs of uninstalled | 472 // hitting a server), we should consider caching pubspecs of uninstalled |
| 474 // packages in the system cache. | 473 // packages in the system cache. |
| 475 /** | 474 /** |
| 476 * Maintains a cache of previously-loaded pubspecs. Used to avoid requesting | 475 * Maintains a cache of previously-loaded pubspecs. Used to avoid requesting |
| 477 * the same pubspec from the server repeatedly. | 476 * the same pubspec from the server repeatedly. |
| (...skipping 97 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 575 Dependency._clone(Dependency other) | 574 Dependency._clone(Dependency other) |
| 576 : name = other.name, | 575 : name = other.name, |
| 577 source = other.source, | 576 source = other.source, |
| 578 description = other.description, | 577 description = other.description, |
| 579 version = other.version, | 578 version = other.version, |
| 580 _refs = new Map<String, PackageRef>.from(other._refs); | 579 _refs = new Map<String, PackageRef>.from(other._refs); |
| 581 | 580 |
| 582 /** Creates a copy of this dependency. */ | 581 /** Creates a copy of this dependency. */ |
| 583 Dependency clone() => new Dependency._clone(this); | 582 Dependency clone() => new Dependency._clone(this); |
| 584 | 583 |
| 584 /// Return a list of available versions for this dependency. |
| 585 Future<List<Version>> getVersions() => source.getVersions(name, description); |
| 586 |
| 585 /** | 587 /** |
| 586 * Places [ref] as a constraint from [package] onto this. | 588 * Places [ref] as a constraint from [package] onto this. |
| 587 */ | 589 */ |
| 588 void placeConstraint(String package, PackageRef ref) { | 590 void placeConstraint(String package, PackageRef ref) { |
| 589 // If this isn't the first constraint placed on this package, make sure it | 591 // If this isn't the first constraint placed on this package, make sure it |
| 590 // matches the source and description of past constraints. | 592 // matches the source and description of past constraints. |
| 591 if (_refs.isEmpty()) { | 593 if (_refs.isEmpty()) { |
| 592 source = ref.source; | 594 source = ref.source; |
| 593 description = ref.description; | 595 description = ref.description; |
| 594 } else if (source.name != ref.source.name) { | 596 } else if (source.name != ref.source.name) { |
| (...skipping 105 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 700 final description1; | 702 final description1; |
| 701 final description2; | 703 final description2; |
| 702 | 704 |
| 703 DescriptionMismatchException(this.package, this.description1, | 705 DescriptionMismatchException(this.package, this.description1, |
| 704 this.description2); | 706 this.description2); |
| 705 | 707 |
| 706 // TODO(nweiz): Dump to YAML when that's supported | 708 // TODO(nweiz): Dump to YAML when that's supported |
| 707 String toString() => "Package '$package' has conflicting descriptions " | 709 String toString() => "Package '$package' has conflicting descriptions " |
| 708 "'${JSON.stringify(description1)}' and '${JSON.stringify(description2)}'"; | 710 "'${JSON.stringify(description1)}' and '${JSON.stringify(description2)}'"; |
| 709 } | 711 } |
| OLD | NEW |