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 |