| 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 20 matching lines...) Expand all Loading... |
| 31 * of the constraints that its depending packages place on it. If that overall | 31 * of the constraints that its depending packages place on it. If that overall |
| 32 * constraint changes (say from "<3.0.0" to "<2.5.0"), then the currently | 32 * constraint changes (say from "<3.0.0" to "<2.5.0"), then the currently |
| 33 * picked version for that package may fall outside of the new constraint. If | 33 * picked version for that package may fall outside of the new constraint. If |
| 34 * that happens, we find the new best version that meets the updated constraint | 34 * that happens, we find the new best version that meets the updated constraint |
| 35 * and then the change the package to use that version. That cycles back up to | 35 * and then the change the package to use that version. That cycles back up to |
| 36 * the beginning again. | 36 * the beginning again. |
| 37 */ | 37 */ |
| 38 #library('version_solver'); | 38 #library('version_solver'); |
| 39 | 39 |
| 40 #import('dart:json'); | 40 #import('dart:json'); |
| 41 #import('lock_file.dart'); | |
| 42 #import('package.dart'); | 41 #import('package.dart'); |
| 43 #import('pubspec.dart'); | 42 #import('pubspec.dart'); |
| 44 #import('root_source.dart'); | 43 #import('root_source.dart'); |
| 45 #import('source.dart'); | 44 #import('source.dart'); |
| 46 #import('source_registry.dart'); | 45 #import('source_registry.dart'); |
| 47 #import('utils.dart'); | 46 #import('utils.dart'); |
| 48 #import('version.dart'); | 47 #import('version.dart'); |
| 49 | 48 |
| 50 /** | 49 /** |
| 51 * Attempts to select the best concrete versions for all of the transitive | 50 * Attempts to select the best concrete versions for all of the transitive |
| 52 * dependencies of [root] taking into account all of the [VersionConstraint]s | 51 * dependencies of [root] taking into account all of the [VersionConstraint]s |
| 53 * that those dependencies place on each other and the requirements imposed by | 52 * that those dependencies place on each other. If successful, completes to a |
| 54 * [lockFile]. If successful, completes to a [Map] that maps package names to | 53 * [Map] that maps package names to the selected version for that package. If |
| 55 * the selected version for that package. If it fails, the future will complete | 54 * it fails, the future will complete with a [NoVersionException], |
| 56 * with a [NoVersionException], [DisjointConstraintException], or | 55 * [DisjointConstraintException], or [CouldNotSolveException]. |
| 57 * [CouldNotSolveException]. | |
| 58 */ | 56 */ |
| 59 Future<List<PackageId>> resolveVersions(SourceRegistry sources, Package root, | 57 Future<List<PackageId>> resolveVersions(SourceRegistry sources, Package root) { |
| 60 LockFile lockFile) { | 58 return new VersionSolver(sources, root).solve(); |
| 61 return new VersionSolver(sources, root, lockFile).solve(); | |
| 62 } | 59 } |
| 63 | 60 |
| 64 class VersionSolver { | 61 class VersionSolver { |
| 65 final SourceRegistry _sources; | 62 final SourceRegistry _sources; |
| 66 final Package _root; | 63 final Package _root; |
| 67 final LockFile lockFile; | |
| 68 final PubspecCache _pubspecs; | 64 final PubspecCache _pubspecs; |
| 69 final Map<String, Dependency> _packages; | 65 final Map<String, Dependency> _packages; |
| 70 final Queue<WorkItem> _work; | 66 final Queue<WorkItem> _work; |
| 71 int _numIterations = 0; | 67 int _numIterations = 0; |
| 72 | 68 |
| 73 VersionSolver(SourceRegistry sources, this._root, this.lockFile) | 69 VersionSolver(SourceRegistry sources, Package root) |
| 74 : _sources = sources, | 70 : _sources = sources, |
| 71 _root = root, |
| 75 _pubspecs = new PubspecCache(sources), | 72 _pubspecs = new PubspecCache(sources), |
| 76 _packages = <Dependency>{}, | 73 _packages = <Dependency>{}, |
| 77 _work = new Queue<WorkItem>(); | 74 _work = new Queue<WorkItem>(); |
| 78 | 75 |
| 79 Future<List<PackageId>> solve() { | 76 Future<List<PackageId>> solve() { |
| 80 // Kick off the work by adding the root package at its concrete version to | 77 // Kick off the work by adding the root package at its concrete version to |
| 81 // the dependency graph. | 78 // the dependency graph. |
| 82 var ref = new PackageRef(new RootSource(_root), _root.version, _root.name); | 79 var ref = new PackageRef(new RootSource(_root), _root.version, _root.name); |
| 83 enqueue(new AddConstraint('(entrypoint)', ref)); | 80 enqueue(new AddConstraint('(entrypoint)', ref)); |
| 84 _pubspecs.cache(ref.atVersion(_root.version), _root.pubspec); | 81 _pubspecs.cache(ref.atVersion(_root.version), _root.pubspec); |
| (...skipping 40 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 125 } | 122 } |
| 126 | 123 |
| 127 /** | 124 /** |
| 128 * Sets the best selected version of [package] to [version]. | 125 * Sets the best selected version of [package] to [version]. |
| 129 */ | 126 */ |
| 130 void setVersion(String package, Version version) { | 127 void setVersion(String package, Version version) { |
| 131 _packages[package].version = version; | 128 _packages[package].version = version; |
| 132 } | 129 } |
| 133 | 130 |
| 134 List<PackageId> buildResults() { | 131 List<PackageId> buildResults() { |
| 135 return _packages.getValues().filter((dep) => dep.isDependedOn).map((dep) { | 132 return _packages.getValues() |
| 136 var description = dep.description; | 133 .filter((dep) => dep.isDependedOn) |
| 137 | 134 .map((dep) => new PackageId(dep.source, dep.version, dep.description)); |
| 138 // If the lockfile contains a fully-resolved description for the package, | |
| 139 // use that. This allows e.g. Git to ensure that the same commit is used. | |
| 140 var lockedPackage = lockFile.packages[dep.name]; | |
| 141 if (lockedPackage != null && lockedPackage.version == dep.version && | |
| 142 lockedPackage.source.name == dep.source.name && | |
| 143 dep.source.descriptionsEqual( | |
| 144 description, lockedPackage.description)) { | |
| 145 description = lockedPackage.description; | |
| 146 } | |
| 147 | |
| 148 return new PackageId(dep.source, dep.version, description); | |
| 149 }); | |
| 150 } | 135 } |
| 151 } | 136 } |
| 152 | 137 |
| 153 /** | 138 /** |
| 154 * The constraint solver works by iteratively processing a queue of work items. | 139 * The constraint solver works by iteratively processing a queue of work items. |
| 155 * Each item is a single atomic change to the dependency graph. Handling them | 140 * Each item is a single atomic change to the dependency graph. Handling them |
| 156 * in a queue lets us handle asynchrony (resolving versions requires information | 141 * in a queue lets us handle asynchrony (resolving versions requires information |
| 157 * from servers) as well as avoid deeply nested recursion. | 142 * from servers) as well as avoid deeply nested recursion. |
| 158 */ | 143 */ |
| 159 interface WorkItem { | 144 interface WorkItem { |
| (...skipping 123 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 283 } | 268 } |
| 284 | 269 |
| 285 // If the dependency is on the root package, then we don't need to do | 270 // If the dependency is on the root package, then we don't need to do |
| 286 // anything since it's already at the best version. | 271 // anything since it's already at the best version. |
| 287 if (name == solver._root.name) { | 272 if (name == solver._root.name) { |
| 288 solver.enqueue(new ChangeVersion( | 273 solver.enqueue(new ChangeVersion( |
| 289 source, description, solver._root.version)); | 274 source, description, solver._root.version)); |
| 290 return null; | 275 return null; |
| 291 } | 276 } |
| 292 | 277 |
| 293 // If the dependency is on a package in the lockfile, use the lockfile's | |
| 294 // version for that package if it's valid given the other constraints. | |
| 295 var lockedPackage = solver.lockFile.packages[name]; | |
| 296 if (lockedPackage != null) { | |
| 297 var lockedVersion = lockedPackage.version; | |
| 298 if (newConstraint.allows(lockedVersion)) { | |
| 299 solver.enqueue(new ChangeVersion(source, description, lockedVersion)); | |
| 300 return null; | |
| 301 } | |
| 302 } | |
| 303 | |
| 304 // The constraint has changed, so see what the best version of the package | 278 // The constraint has changed, so see what the best version of the package |
| 305 // that meets the new constraint is. | 279 // that meets the new constraint is. |
| 306 return source.getVersions(description).transform((versions) { | 280 return source.getVersions(description).transform((versions) { |
| 307 var best = null; | 281 var best = null; |
| 308 for (var version in versions) { | 282 for (var version in versions) { |
| 309 if (newConstraint.allows(version)) { | 283 if (newConstraint.allows(version)) { |
| 310 if (best == null || version > best) best = version; | 284 if (best == null || version > best) best = version; |
| 311 } | 285 } |
| 312 } | 286 } |
| 313 | 287 |
| (...skipping 258 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 572 final description1; | 546 final description1; |
| 573 final description2; | 547 final description2; |
| 574 | 548 |
| 575 DescriptionMismatchException(this.package, this.description1, | 549 DescriptionMismatchException(this.package, this.description1, |
| 576 this.description2); | 550 this.description2); |
| 577 | 551 |
| 578 // TODO(nweiz): Dump to YAML when that's supported | 552 // TODO(nweiz): Dump to YAML when that's supported |
| 579 String toString() => "Package '$package' has conflicting descriptions " | 553 String toString() => "Package '$package' has conflicting descriptions " |
| 580 "'${JSON.stringify(description1)}' and '${JSON.stringify(description2)}'"; | 554 "'${JSON.stringify(description1)}' and '${JSON.stringify(description2)}'"; |
| 581 } | 555 } |
| OLD | NEW |