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_solver1; | |
37 | |
38 import 'dart:async'; | |
39 import 'dart:collection' show Queue; | |
40 import 'dart:math' as math; | |
41 | |
42 import '../lock_file.dart'; | |
43 import '../log.dart' as log; | |
44 import '../package.dart'; | |
45 import '../source.dart'; | |
46 import '../source_registry.dart'; | |
47 import '../version.dart'; | |
48 import 'version_solver.dart'; | |
49 | |
50 class GreedyVersionSolver extends VersionSolver { | |
51 final _packages = <String, DependencyNode>{}; | |
52 final _work = new Queue<WorkItem>(); | |
53 int _numIterations = 0; | |
54 | |
55 GreedyVersionSolver(SourceRegistry sources, Package root, LockFile lockFile, | |
56 List<String> useLatest) | |
57 : super(sources, root, lockFile, useLatest); | |
58 | |
59 /// The non-backtracking solver always only tries one solution. | |
60 int get attemptedSolutions => 1; | |
61 | |
62 void forceLatestVersion(String package) { | |
63 // TODO(nweiz): How do we want to detect and handle unknown dependencies | |
64 // here? | |
65 getDependency(package).useLatestVersion = true; | |
66 } | |
67 | |
68 Future<List<PackageId>> runSolver() { | |
69 // Kick off the work by adding the root package at its concrete version to | |
70 // the dependency graph. | |
71 enqueue(new AddConstraint('(entrypoint)', new PackageRef.root(root))); | |
72 | |
73 Future processNextWorkItem(_) { | |
74 while (true) { | |
75 // Stop if we are done. | |
76 if (_work.isEmpty) return new Future.value(buildResults()); | |
77 | |
78 // If we appear to be stuck in a loop, then we probably have an unstable | |
79 // graph, bail. We guess this based on a rough heuristic that it should | |
80 // only take a certain number of steps to solve a graph with a given | |
81 // number of connections. | |
82 // TODO(rnystrom): These numbers here are magic and arbitrary. Tune | |
83 // when we have a better picture of real-world package topologies. | |
84 _numIterations++; | |
85 if (_numIterations > math.max(50, _packages.length * 5)) { | |
86 throw new CouldNotSolveException(); | |
87 } | |
88 | |
89 // Run the first work item. | |
90 var future = _work.removeFirst().process(this); | |
91 | |
92 // If we have an async operation to perform, chain the loop to resume | |
93 // when it's done. Otherwise, just loop synchronously. | |
94 if (future != null) { | |
95 return future.then(processNextWorkItem); | |
96 } | |
97 } | |
98 } | |
99 | |
100 return processNextWorkItem(null); | |
101 } | |
102 | |
103 void enqueue(WorkItem work) { | |
104 _work.add(work); | |
105 } | |
106 | |
107 DependencyNode getDependency(String package) { | |
108 // There can be unused dependencies in the graph, so just create an empty | |
109 // one if needed. | |
110 _packages.putIfAbsent(package, () => new DependencyNode(package)); | |
111 return _packages[package]; | |
112 } | |
113 | |
114 /// Sets the best selected version of [package] to [version]. | |
115 void setVersion(String package, Version version) { | |
116 _packages[package].version = version; | |
117 } | |
118 | |
119 /// Returns the most recent version of [dependency] that satisfies all of its | |
120 /// version constraints. | |
121 Future<Version> getBestVersion(DependencyNode dependency) { | |
122 return cache.getVersions(dependency.name, | |
123 dependency.source, dependency.description).then((versions) { | |
124 var best = null; | |
125 for (var ref in versions) { | |
126 if (dependency.useLatestVersion || | |
127 dependency.constraint.allows(ref.version)) { | |
128 if (best == null || ref.version > best) best = ref.version; | |
129 } | |
130 } | |
131 | |
132 // TODO(rnystrom): Better exception. | |
133 if (best == null) { | |
134 if (tryUnlockDepender(dependency)) return null; | |
135 throw new NoVersionException(dependency.name, dependency.constraint, | |
136 dependency.toList()); | |
137 } else if (!dependency.constraint.allows(best)) { | |
138 if (tryUnlockDepender(dependency)) return null; | |
139 throw new CouldNotUpdateException( | |
140 dependency.name, dependency.constraint, best); | |
141 } | |
142 | |
143 return best; | |
144 }); | |
145 } | |
146 | |
147 /// Looks for a package that depends (transitively) on [dependency] and has | |
148 /// its version locked in the lockfile. If one is found, enqueues an | |
149 /// [UnlockPackage] work item for it and returns true. Otherwise, returns | |
150 /// false. | |
151 /// | |
152 /// This does a breadth-first search; immediate dependers will be unlocked | |
153 /// first, followed by transitive dependers. | |
154 bool tryUnlockDepender(DependencyNode dependency, [Set<String> seen]) { | |
155 if (seen == null) seen = new Set(); | |
156 // Avoid an infinite loop if there are circular dependencies. | |
157 if (seen.contains(dependency.name)) return false; | |
158 seen.add(dependency.name); | |
159 | |
160 for (var dependerName in dependency.dependers) { | |
161 var depender = getDependency(dependerName); | |
162 var locked = lockFile.packages[dependerName]; | |
163 if (locked != null && depender.version == locked.version && | |
164 depender.source.name == locked.source.name) { | |
165 enqueue(new UnlockPackage(depender)); | |
166 return true; | |
167 } | |
168 } | |
169 | |
170 return dependency.dependers.map(getDependency).any((subdependency) => | |
171 tryUnlockDepender(subdependency, seen)); | |
172 } | |
173 | |
174 List<PackageId> buildResults() { | |
175 return _packages.values | |
176 .where((dep) => dep.isDependedOn) | |
177 .map(_dependencyToPackageId) | |
178 .toList(); | |
179 } | |
180 | |
181 PackageId _dependencyToPackageId(DependencyNode dep) { | |
182 var description = dep.description; | |
183 | |
184 // If the lockfile contains a fully-resolved description for the package, | |
185 // use that. This allows e.g. Git to ensure that the same commit is used. | |
186 var lockedPackage = lockFile.packages[dep.name]; | |
187 if (lockedPackage != null && lockedPackage.version == dep.version && | |
188 lockedPackage.source.name == dep.source.name && | |
189 dep.source.descriptionsEqual( | |
190 description, lockedPackage.description)) { | |
191 description = lockedPackage.description; | |
192 } | |
193 | |
194 return new PackageId(dep.name, dep.source, dep.version, description); | |
195 } | |
196 } | |
197 | |
198 /// The constraint solver works by iteratively processing a queue of work items. | |
199 /// Each item is a single atomic change to the dependency graph. Handling them | |
200 /// in a queue lets us handle asynchrony (resolving versions requires | |
201 /// information from servers) as well as avoid deeply nested recursion. | |
202 abstract class WorkItem { | |
203 /// Processes this work item. Returns a future that completes when the work is | |
204 /// done. If `null` is returned, that means the work has completed | |
205 /// synchronously and the next item can be started immediately. | |
206 Future process(GreedyVersionSolver solver); | |
207 } | |
208 | |
209 /// The best selected version for a package has changed to [version]. If the | |
210 /// previous version of the package is `null`, that means the package is being | |
211 /// added to the graph. If [version] is `null`, it is being removed. | |
212 class ChangeVersion implements WorkItem { | |
213 /// The name of the package whose version is being changed. | |
214 final String package; | |
215 | |
216 /// The source of the package whose version is changing. | |
217 final Source source; | |
218 | |
219 /// The description identifying the package whose version is changing. | |
220 final description; | |
221 | |
222 /// The new selected version. | |
223 final Version version; | |
224 | |
225 ChangeVersion(this.package, this.source, this.description, this.version); | |
226 | |
227 Future process(GreedyVersionSolver solver) { | |
228 log.fine("Changing $package to version $version."); | |
229 | |
230 var dependency = solver.getDependency(package); | |
231 var oldVersion = dependency.version; | |
232 solver.setVersion(package, version); | |
233 | |
234 // The dependencies between the old and new version may be different. Walk | |
235 // them both and update any constraints that differ between the two. | |
236 return Future.wait([ | |
237 getDependencyRefs(solver, oldVersion), | |
238 getDependencyRefs(solver, version)]).then((list) { | |
239 var oldDependencyRefs = list[0]; | |
240 var newDependencyRefs = list[1]; | |
241 | |
242 for (var oldRef in oldDependencyRefs.values) { | |
243 if (newDependencyRefs.containsKey(oldRef.name)) { | |
244 // The dependency is in both versions of this package, but its | |
245 // constraint may have changed. | |
246 var newRef = newDependencyRefs.remove(oldRef.name); | |
247 solver.enqueue(new AddConstraint(package, newRef)); | |
248 } else { | |
249 // The dependency is not in the new version of the package, so just | |
250 // remove its constraint. | |
251 solver.enqueue(new RemoveConstraint(package, oldRef.name)); | |
252 } | |
253 } | |
254 | |
255 // Everything that's left is a depdendency that's only in the new | |
256 // version of the package. | |
257 for (var newRef in newDependencyRefs.values) { | |
258 solver.enqueue(new AddConstraint(package, newRef)); | |
259 } | |
260 }); | |
261 } | |
262 | |
263 /// Get the dependencies at [version] of the package being changed. | |
264 Future<Map<String, PackageRef>> getDependencyRefs(VersionSolver solver, | |
265 Version version) { | |
266 // If there is no version, it means no package, so no dependencies. | |
267 if (version == null) { | |
268 return new Future<Map<String, PackageRef>>.value(<String, PackageRef>{}); | |
269 } | |
270 | |
271 var id = new PackageId(package, source, version, description); | |
272 return solver.cache.getPubspec(id).then((pubspec) { | |
273 var dependencies = <String, PackageRef>{}; | |
274 for (var dependency in pubspec.dependencies) { | |
275 dependencies[dependency.name] = dependency; | |
276 } | |
277 | |
278 // Include dev dependencies only from the root package. | |
279 if (id.isRoot) { | |
280 for (var dependency in pubspec.devDependencies) { | |
281 dependencies[dependency.name] = dependency; | |
282 } | |
283 } | |
284 | |
285 return dependencies; | |
286 }); | |
287 } | |
288 } | |
289 | |
290 /// A constraint that a depending package places on a dependent package has | |
291 /// changed. | |
292 /// | |
293 /// This is an abstract class that contains logic for updating the dependency | |
294 /// graph once a dependency has changed. Changing the dependency is the | |
295 /// responsibility of subclasses. | |
296 abstract class ChangeConstraint implements WorkItem { | |
297 Future process(GreedyVersionSolver solver); | |
298 | |
299 void undo(GreedyVersionSolver solver); | |
300 | |
301 Future _processChange(GreedyVersionSolver solver, | |
302 DependencyNode oldDependency, | |
303 DependencyNode newDependency) { | |
304 var name = newDependency.name; | |
305 var source = oldDependency.source != null ? | |
306 oldDependency.source : newDependency.source; | |
307 var description = oldDependency.description != null ? | |
308 oldDependency.description : newDependency.description; | |
309 var oldConstraint = oldDependency.constraint; | |
310 var newConstraint = newDependency.constraint; | |
311 | |
312 // If the package is over-constrained, i.e. the packages depending have | |
313 // disjoint constraints, then try unlocking a depender that's locked by the | |
314 // lockfile. If there are no remaining locked dependencies, throw an error. | |
315 if (newConstraint != null && newConstraint.isEmpty) { | |
316 if (solver.tryUnlockDepender(newDependency)) { | |
317 undo(solver); | |
318 return null; | |
319 } | |
320 | |
321 throw new DisjointConstraintException(name, newDependency.toList()); | |
322 } | |
323 | |
324 // If this constraint change didn't cause the overall constraint on the | |
325 // package to change, then we don't need to do any further work. | |
326 if (oldConstraint == newConstraint) return null; | |
327 | |
328 // If the dependency has been cut free from the graph, just remove it. | |
329 if (!newDependency.isDependedOn) { | |
330 solver.enqueue(new ChangeVersion(name, source, description, null)); | |
331 return null; | |
332 } | |
333 | |
334 // If the dependency is on the root package, then we don't need to do | |
335 // anything since it's already at the best version. | |
336 if (name == solver.root.name) { | |
337 solver.enqueue(new ChangeVersion( | |
338 name, source, description, solver.root.version)); | |
339 return null; | |
340 } | |
341 | |
342 // If the dependency is on a package in the lockfile, use the lockfile's | |
343 // version for that package if it's valid given the other constraints. | |
344 var lockedPackage = solver.lockFile.packages[name]; | |
345 if (lockedPackage != null && newDependency.source == lockedPackage.source) { | |
346 var lockedVersion = lockedPackage.version; | |
347 if (newConstraint.allows(lockedVersion)) { | |
348 solver.enqueue( | |
349 new ChangeVersion(name, source, description, lockedVersion)); | |
350 return null; | |
351 } | |
352 } | |
353 | |
354 // The constraint has changed, so see what the best version of the package | |
355 // that meets the new constraint is. | |
356 return solver.getBestVersion(newDependency).then((best) { | |
357 if (best == null) { | |
358 undo(solver); | |
359 } else if (newDependency.version != best) { | |
360 solver.enqueue(new ChangeVersion(name, source, description, best)); | |
361 } | |
362 }); | |
363 } | |
364 } | |
365 | |
366 /// The constraint given by [ref] is being placed by [depender]. | |
367 class AddConstraint extends ChangeConstraint { | |
368 /// The package that has the dependency. | |
369 final String depender; | |
370 | |
371 /// The package being depended on and the constraints being placed on it. The | |
372 /// source, version, and description in this ref are all considered | |
373 /// constraints on the dependent package. | |
374 final PackageRef ref; | |
375 | |
376 AddConstraint(this.depender, this.ref); | |
377 | |
378 Future process(GreedyVersionSolver solver) { | |
379 log.fine("Adding $depender's constraint $ref."); | |
380 | |
381 var dependency = solver.getDependency(ref.name); | |
382 var oldDependency = dependency.clone(); | |
383 dependency.placeConstraint(depender, ref); | |
384 return _processChange(solver, oldDependency, dependency); | |
385 } | |
386 | |
387 void undo(GreedyVersionSolver solver) { | |
388 solver.getDependency(ref.name).removeConstraint(depender); | |
389 } | |
390 } | |
391 | |
392 /// [depender] is no longer placing a constraint on [dependent]. | |
393 class RemoveConstraint extends ChangeConstraint { | |
394 /// The package that was placing a constraint on [dependent]. | |
395 String depender; | |
396 | |
397 /// The package that was being depended on. | |
398 String dependent; | |
399 | |
400 /// The constraint that was removed. | |
401 PackageRef _removed; | |
402 | |
403 RemoveConstraint(this.depender, this.dependent); | |
404 | |
405 Future process(GreedyVersionSolver solver) { | |
406 log.fine("Removing $depender's constraint ($_removed) on $dependent."); | |
407 | |
408 var dependency = solver.getDependency(dependent); | |
409 var oldDependency = dependency.clone(); | |
410 _removed = dependency.removeConstraint(depender); | |
411 return _processChange(solver, oldDependency, dependency); | |
412 } | |
413 | |
414 void undo(GreedyVersionSolver solver) { | |
415 solver.getDependency(dependent).placeConstraint(depender, _removed); | |
416 } | |
417 } | |
418 | |
419 /// [package]'s version is no longer constrained by the lockfile. | |
420 class UnlockPackage implements WorkItem { | |
421 /// The package being unlocked. | |
422 DependencyNode package; | |
423 | |
424 UnlockPackage(this.package); | |
425 | |
426 Future process(GreedyVersionSolver solver) { | |
427 log.fine("Unlocking ${package.name}."); | |
428 | |
429 solver.lockFile.packages.remove(package.name); | |
430 return solver.getBestVersion(package).then((best) { | |
431 if (best == null) return null; | |
432 solver.enqueue(new ChangeVersion( | |
433 package.name, package.source, package.description, best)); | |
434 }); | |
435 } | |
436 } | |
437 | |
438 /// Describes one [Package] in the [DependencyGraph] and keeps track of which | |
439 /// packages depend on it and what constraints they place on it. | |
440 class DependencyNode { | |
441 /// The name of the this dependency's package. | |
442 final String name; | |
443 | |
444 /// The [PackageRefs] that represent constraints that depending packages have | |
445 /// placed on this one. | |
446 final Map<String, PackageRef> _refs; | |
447 | |
448 /// The currently-selected best version for this dependency. | |
449 Version version; | |
450 | |
451 /// Whether this dependency should always select the latest version. | |
452 bool useLatestVersion = false; | |
453 | |
454 /// Gets whether or not any other packages are currently depending on this | |
455 /// one. If `false`, then it means this package is not part of the dependency | |
456 /// graph and should be omitted. | |
457 bool get isDependedOn => !_refs.isEmpty; | |
458 | |
459 /// The names of all the packages that depend on this dependency. | |
460 Iterable<String> get dependers => _refs.keys; | |
461 | |
462 /// Gets the overall constraint that all packages are placing on this one. | |
463 /// If no packages have a constraint on this one (which can happen when this | |
464 /// package is in the process of being added to the graph), returns `null`. | |
465 VersionConstraint get constraint { | |
466 if (_refs.isEmpty) return null; | |
467 return new VersionConstraint.intersection( | |
468 _refs.values.map((ref) => ref.constraint)); | |
469 } | |
470 | |
471 /// The source of this dependency's package. | |
472 Source get source { | |
473 var canonical = _canonicalRef(); | |
474 if (canonical == null) return null; | |
475 return canonical.source; | |
476 } | |
477 | |
478 /// The description of this dependency's package. | |
479 get description { | |
480 var canonical = _canonicalRef(); | |
481 if (canonical == null) return null; | |
482 return canonical.description; | |
483 } | |
484 | |
485 /// Return the PackageRef that has the canonical source and description for | |
486 /// this package. If any dependency is on the root package, that will be used; | |
487 /// otherwise, it will be the source and description that all dependencies | |
488 /// agree upon. | |
489 PackageRef _canonicalRef() { | |
490 if (_refs.isEmpty) return null; | |
491 var refs = _refs.values; | |
492 for (var ref in refs) { | |
493 if (ref.isRoot) return ref; | |
494 } | |
495 return refs.first; | |
496 } | |
497 | |
498 DependencyNode(this.name) | |
499 : _refs = <String, PackageRef>{}; | |
500 | |
501 DependencyNode._clone(DependencyNode other) | |
502 : name = other.name, | |
503 version = other.version, | |
504 _refs = new Map<String, PackageRef>.from(other._refs); | |
505 | |
506 /// Creates a copy of this dependency. | |
507 DependencyNode clone() => new DependencyNode._clone(this); | |
508 | |
509 /// Places [ref] as a constraint from [package] onto this. | |
510 void placeConstraint(String package, PackageRef ref) { | |
511 var requiredDepender = _requiredDepender(); | |
512 if (requiredDepender != null) { | |
513 var required = _refs[requiredDepender]; | |
514 if (required.source.name != ref.source.name) { | |
515 throw new SourceMismatchException(name, [ | |
516 new Dependency(requiredDepender, required), | |
517 new Dependency(package, ref)]); | |
518 } else if (!required.descriptionEquals(ref)) { | |
519 throw new DescriptionMismatchException(name, [ | |
520 new Dependency(requiredDepender, required), | |
521 new Dependency(package, ref)]); | |
522 } | |
523 } | |
524 | |
525 _refs[package] = ref; | |
526 } | |
527 | |
528 /// Returns the name of a package whose constraint source and description | |
529 /// all other constraints must match. Returns null if there are no | |
530 /// requirements on new constraints. | |
531 String _requiredDepender() { | |
532 if (_refs.isEmpty) return null; | |
533 | |
534 var dependers = _refs.keys.toList(); | |
535 if (dependers.length == 1) { | |
536 var depender = dependers[0]; | |
537 if (_refs[depender].isRoot) return null; | |
538 return depender; | |
539 } | |
540 | |
541 return dependers[1]; | |
542 } | |
543 | |
544 /// Removes the constraint from [package] onto this. | |
545 PackageRef removeConstraint(String package) => _refs.remove(package); | |
546 | |
547 /// Converts this to a list of [Dependency] objects like the error types | |
548 /// expect. | |
549 List<Dependency> toList() { | |
550 var result = <Dependency>[]; | |
551 _refs.forEach((name, ref) { | |
552 result.add(new Dependency(name, ref)); | |
553 }); | |
554 return result; | |
555 } | |
556 } | |
OLD | NEW |