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 /// A back-tracking depth-first solver. | 5 /// A back-tracking depth-first solver. |
6 /// | 6 /// |
7 /// Attempts to find the best solution for a root package's transitive | 7 /// Attempts to find the best solution for a root package's transitive |
8 /// dependency graph, where a "solution" is a set of concrete package versions. | 8 /// dependency graph, where a "solution" is a set of concrete package versions. |
9 /// A valid solution will select concrete versions for every package reached | 9 /// A valid solution will select concrete versions for every package reached |
10 /// from the root package's dependency graph, and each of those packages will | 10 /// from the root package's dependency graph, and each of those packages will |
(...skipping 26 matching lines...) Expand all Loading... | |
37 | 37 |
38 import 'package:pub_semver/pub_semver.dart'; | 38 import 'package:pub_semver/pub_semver.dart'; |
39 | 39 |
40 import '../barback.dart' as barback; | 40 import '../barback.dart' as barback; |
41 import '../exceptions.dart'; | 41 import '../exceptions.dart'; |
42 import '../lock_file.dart'; | 42 import '../lock_file.dart'; |
43 import '../log.dart' as log; | 43 import '../log.dart' as log; |
44 import '../package.dart'; | 44 import '../package.dart'; |
45 import '../pubspec.dart'; | 45 import '../pubspec.dart'; |
46 import '../sdk.dart' as sdk; | 46 import '../sdk.dart' as sdk; |
47 import '../source_registry.dart'; | |
48 import '../source/hosted.dart'; | |
49 import '../source/unknown.dart'; | 47 import '../source/unknown.dart'; |
48 import '../system_cache.dart'; | |
50 import '../utils.dart'; | 49 import '../utils.dart'; |
51 import 'version_queue.dart'; | 50 import 'version_queue.dart'; |
52 import 'version_selection.dart'; | 51 import 'version_selection.dart'; |
53 import 'version_solver.dart'; | 52 import 'version_solver.dart'; |
54 | 53 |
55 /// The top-level solver. | 54 /// The top-level solver. |
56 /// | 55 /// |
57 /// Keeps track of the current potential solution, and the other possible | 56 /// Keeps track of the current potential solution, and the other possible |
58 /// versions for speculative package selections. Backtracks and advances to the | 57 /// versions for speculative package selections. Backtracks and advances to the |
59 /// next potential solution in the case of a failure. | 58 /// next potential solution in the case of a failure. |
60 class BacktrackingSolver { | 59 class BacktrackingSolver { |
61 final SolveType type; | 60 final SolveType type; |
62 final SourceRegistry sources; | 61 final SystemCache systemCache; |
63 final Package root; | 62 final Package root; |
64 | 63 |
65 /// The lockfile that was present before solving. | 64 /// The lockfile that was present before solving. |
66 final LockFile lockFile; | 65 final LockFile lockFile; |
67 | 66 |
68 /// A cache of data requested during solving. | 67 /// A cache of data requested during solving. |
69 final SolverCache cache; | 68 final SolverCache cache; |
70 | 69 |
71 /// The set of packages that are being explicitly upgraded. | 70 /// The set of packages that are being explicitly upgraded. |
72 /// | 71 /// |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
111 /// package, since it has only one valid version, but [_selection] does, since | 110 /// package, since it has only one valid version, but [_selection] does, since |
112 /// its dependencies are relevant. Second, when backtracking, [_versions] | 111 /// its dependencies are relevant. Second, when backtracking, [_versions] |
113 /// contains the version that's being backtracked, while [_selection] does | 112 /// contains the version that's being backtracked, while [_selection] does |
114 /// not. | 113 /// not. |
115 VersionSelection _selection; | 114 VersionSelection _selection; |
116 | 115 |
117 /// The number of solutions the solver has tried so far. | 116 /// The number of solutions the solver has tried so far. |
118 var _attemptedSolutions = 1; | 117 var _attemptedSolutions = 1; |
119 | 118 |
120 /// A pubspec for pub's implicit dependencies on barback and related packages. | 119 /// A pubspec for pub's implicit dependencies on barback and related packages. |
121 final Pubspec _implicitPubspec = () { | 120 final Pubspec _implicitPubspec; |
122 var dependencies = []; | |
123 barback.pubConstraints.forEach((name, constraint) { | |
124 dependencies.add(HostedSource.refFor(name).withConstraint(constraint)); | |
125 }); | |
126 | 121 |
127 return new Pubspec("pub itself", dependencies: dependencies); | 122 BacktrackingSolver(SolveType type, SystemCache systemCache, this.root, |
128 }(); | |
129 | |
130 BacktrackingSolver(SolveType type, SourceRegistry sources, this.root, | |
131 this.lockFile, List<String> useLatest) | 123 this.lockFile, List<String> useLatest) |
132 : type = type, | 124 : type = type, |
133 sources = sources, | 125 systemCache = systemCache, |
134 cache = new SolverCache(type, sources) { | 126 cache = new SolverCache(type, systemCache), |
127 _implicitPubspec = (() { | |
128 var dependencies = []; | |
129 barback.pubConstraints.forEach((name, constraint) { | |
130 dependencies.add( | |
131 systemCache.sources.hosted.refFor(name).withConstraint(constrain t)); | |
Bob Nystrom
2016/06/14 23:21:55
Long line.
nweiz
2016/06/20 20:46:08
Done.
| |
132 }); | |
133 | |
134 return new Pubspec("pub itself", dependencies: dependencies); | |
135 })() { | |
Bob Nystrom
2016/06/14 23:21:55
Stuffing a giant immediately invoked function in h
nweiz
2016/06/20 20:46:08
Made it a static method instead.
I really hate us
| |
135 _selection = new VersionSelection(this); | 136 _selection = new VersionSelection(this); |
136 | 137 |
137 for (var package in useLatest) { | 138 for (var package in useLatest) { |
138 _forceLatest.add(package); | 139 _forceLatest.add(package); |
139 } | 140 } |
140 | 141 |
141 for (var override in root.dependencyOverrides) { | 142 for (var override in root.dependencyOverrides) { |
142 _overrides[override.name] = override; | 143 _overrides[override.name] = override; |
143 } | 144 } |
144 } | 145 } |
(...skipping 21 matching lines...) Expand all Loading... | |
166 _validateSdkConstraint(root.pubspec); | 167 _validateSdkConstraint(root.pubspec); |
167 | 168 |
168 logSolve(); | 169 logSolve(); |
169 var packages = await _solve(); | 170 var packages = await _solve(); |
170 | 171 |
171 var pubspecs = {}; | 172 var pubspecs = {}; |
172 for (var id in packages) { | 173 for (var id in packages) { |
173 pubspecs[id.name] = await _getPubspec(id); | 174 pubspecs[id.name] = await _getPubspec(id); |
174 } | 175 } |
175 | 176 |
176 return new SolveResult.success(sources, root, lockFile, packages, | 177 return new SolveResult.success(systemCache.sources, root, lockFile, |
177 overrides, pubspecs, _getAvailableVersions(packages), | 178 packages, overrides, pubspecs, _getAvailableVersions(packages), |
178 _attemptedSolutions); | 179 _attemptedSolutions); |
179 } on SolveFailure catch (error) { | 180 } on SolveFailure catch (error) { |
180 // Wrap a failure in a result so we can attach some other data. | 181 // Wrap a failure in a result so we can attach some other data. |
181 return new SolveResult.failure(sources, root, lockFile, overrides, | 182 return new SolveResult.failure(systemCache.sources, root, lockFile, |
182 error, _attemptedSolutions); | 183 overrides, error, _attemptedSolutions); |
183 } finally { | 184 } finally { |
184 // Gather some solving metrics. | 185 // Gather some solving metrics. |
185 var buffer = new StringBuffer(); | 186 var buffer = new StringBuffer(); |
186 buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.'); | 187 buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.'); |
187 buffer.writeln(cache.describeResults()); | 188 buffer.writeln(cache.describeResults()); |
188 log.solver(buffer); | 189 log.solver(buffer); |
189 } | 190 } |
190 } | 191 } |
191 | 192 |
192 /// Generates a map containing all of the known available versions for each | 193 /// Generates a map containing all of the known available versions for each |
(...skipping 26 matching lines...) Expand all Loading... | |
219 /// | 220 /// |
220 /// Returns `null` if it isn't in the lockfile (or has been unlocked). | 221 /// Returns `null` if it isn't in the lockfile (or has been unlocked). |
221 PackageId getLocked(String package) { | 222 PackageId getLocked(String package) { |
222 if (type == SolveType.GET) return lockFile.packages[package]; | 223 if (type == SolveType.GET) return lockFile.packages[package]; |
223 | 224 |
224 // When downgrading, we don't want to force the latest versions of | 225 // When downgrading, we don't want to force the latest versions of |
225 // non-hosted packages, since they don't support multiple versions and thus | 226 // non-hosted packages, since they don't support multiple versions and thus |
226 // can't be downgraded. | 227 // can't be downgraded. |
227 if (type == SolveType.DOWNGRADE) { | 228 if (type == SolveType.DOWNGRADE) { |
228 var locked = lockFile.packages[package]; | 229 var locked = lockFile.packages[package]; |
229 if (locked != null && !sources[locked.source].hasMultipleVersions) { | 230 if (locked != null && |
231 !systemCache.sources[locked.source].hasMultipleVersions) { | |
230 return locked; | 232 return locked; |
231 } | 233 } |
232 } | 234 } |
233 | 235 |
234 if (_forceLatest.isEmpty || _forceLatest.contains(package)) return null; | 236 if (_forceLatest.isEmpty || _forceLatest.contains(package)) return null; |
235 return lockFile.packages[package]; | 237 return lockFile.packages[package]; |
236 } | 238 } |
237 | 239 |
238 /// Gets the package [name] that's currently contained in the lockfile if it | 240 /// Gets the package [name] that's currently contained in the lockfile if it |
239 /// matches the current constraint and has the same source and description as | 241 /// matches the current constraint and has the same source and description as |
240 /// other references to that package. | 242 /// other references to that package. |
241 /// | 243 /// |
242 /// Returns `null` otherwise. | 244 /// Returns `null` otherwise. |
243 PackageId _getValidLocked(String name) { | 245 PackageId _getValidLocked(String name) { |
244 var package = getLocked(name); | 246 var package = getLocked(name); |
245 if (package == null) return null; | 247 if (package == null) return null; |
246 | 248 |
247 var constraint = _selection.getConstraint(name); | 249 var constraint = _selection.getConstraint(name); |
248 if (!constraint.allows(package.version)) { | 250 if (!constraint.allows(package.version)) { |
249 logSolve('$package is locked but does not match $constraint'); | 251 logSolve('$package is locked but does not match $constraint'); |
250 return null; | 252 return null; |
251 } else { | 253 } else { |
252 logSolve('$package is locked'); | 254 logSolve('$package is locked'); |
253 } | 255 } |
254 | 256 |
255 var required = _selection.getRequiredDependency(name); | 257 var required = _selection.getRequiredDependency(name); |
256 if (required != null) { | 258 if (required != null) { |
257 if (package.source != required.dep.source) return null; | 259 if (package.source != required.dep.source) return null; |
258 | 260 |
259 var source = sources[package.source]; | 261 var source = systemCache.sources[package.source]; |
260 if (!source.descriptionsEqual( | 262 if (!source.descriptionsEqual( |
261 package.description, required.dep.description)) return null; | 263 package.description, required.dep.description)) return null; |
262 } | 264 } |
263 | 265 |
264 return package; | 266 return package; |
265 } | 267 } |
266 | 268 |
267 /// Tries to find the best set of versions that meet the constraints. | 269 /// Tries to find the best set of versions that meet the constraints. |
268 /// | 270 /// |
269 /// Selects matching versions of unselected packages, or backtracks if there | 271 /// Selects matching versions of unselected packages, or backtracks if there |
(...skipping 253 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
523 _fail(otherDep.depender.name); | 525 _fail(otherDep.depender.name); |
524 } | 526 } |
525 | 527 |
526 logSolve( | 528 logSolve( |
527 'inconsistent source "${dep.source}" for ${dep.name}:\n' | 529 'inconsistent source "${dep.source}" for ${dep.name}:\n' |
528 ' $dependency\n' + | 530 ' $dependency\n' + |
529 _selection.describeDependencies(dep.name)); | 531 _selection.describeDependencies(dep.name)); |
530 throw new SourceMismatchException(dep.name, allDeps); | 532 throw new SourceMismatchException(dep.name, allDeps); |
531 } | 533 } |
532 | 534 |
533 var source = sources[dep.source]; | 535 var source = systemCache.sources[dep.source]; |
534 if (!source.descriptionsEqual( | 536 if (!source.descriptionsEqual( |
535 dep.description, required.dep.description)) { | 537 dep.description, required.dep.description)) { |
536 // Mark the dependers as failing rather than the package itself, because | 538 // Mark the dependers as failing rather than the package itself, because |
537 // no version with this description will be compatible. | 539 // no version with this description will be compatible. |
538 for (var otherDep in _selection.getDependenciesOn(dep.name)) { | 540 for (var otherDep in _selection.getDependenciesOn(dep.name)) { |
539 _fail(otherDep.depender.name); | 541 _fail(otherDep.depender.name); |
540 } | 542 } |
541 | 543 |
542 logSolve( | 544 logSolve( |
543 'inconsistent description "${dep.description}" for ${dep.name}:\n' | 545 'inconsistent description "${dep.description}" for ${dep.name}:\n' |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
582 // Not overridden. | 584 // Not overridden. |
583 return dep; | 585 return dep; |
584 }).toSet(); | 586 }).toSet(); |
585 } else { | 587 } else { |
586 // Ignore any overridden dependencies. | 588 // Ignore any overridden dependencies. |
587 deps.removeWhere((dep) => _overrides.containsKey(dep.name)); | 589 deps.removeWhere((dep) => _overrides.containsKey(dep.name)); |
588 } | 590 } |
589 | 591 |
590 // Make sure the package doesn't have any bad dependencies. | 592 // Make sure the package doesn't have any bad dependencies. |
591 for (var dep in deps.toSet()) { | 593 for (var dep in deps.toSet()) { |
592 if (!dep.isRoot && sources[dep.source] is UnknownSource) { | 594 if (!dep.isRoot && systemCache.sources[dep.source] is UnknownSource) { |
593 throw new UnknownSourceException(id.name, [new Dependency(id, dep)]); | 595 throw new UnknownSourceException(id.name, [new Dependency(id, dep)]); |
594 } | 596 } |
595 | 597 |
596 if (dep.name == 'barback') { | 598 if (dep.name == 'barback') { |
597 deps.add(new PackageDep.magic('pub itself')); | 599 deps.add(new PackageDep.magic('pub itself')); |
598 } | 600 } |
599 } | 601 } |
600 | 602 |
601 return deps; | 603 return deps; |
602 } | 604 } |
603 | 605 |
604 /// Loads and returns the pubspec for [id]. | 606 /// Loads and returns the pubspec for [id]. |
605 Future<Pubspec> _getPubspec(PackageId id) async { | 607 Future<Pubspec> _getPubspec(PackageId id) async { |
606 if (id.isRoot) return root.pubspec; | 608 if (id.isRoot) return root.pubspec; |
607 if (id.isMagic && id.name == 'pub itself') return _implicitPubspec; | 609 if (id.isMagic && id.name == 'pub itself') return _implicitPubspec; |
608 | 610 return await systemCache.liveSource(id.source).describe(id); |
609 var source = sources[id.source]; | |
610 return await source.describe(id); | |
611 } | 611 } |
612 | 612 |
613 /// Logs the initial parameters to the solver. | 613 /// Logs the initial parameters to the solver. |
614 void _logParameters() { | 614 void _logParameters() { |
615 var buffer = new StringBuffer(); | 615 var buffer = new StringBuffer(); |
616 buffer.writeln("Solving dependencies:"); | 616 buffer.writeln("Solving dependencies:"); |
617 for (var package in root.dependencies) { | 617 for (var package in root.dependencies) { |
618 buffer.write("- $package"); | 618 buffer.write("- $package"); |
619 var locked = getLocked(package.name); | 619 var locked = getLocked(package.name); |
620 if (_forceLatest.contains(package.name)) { | 620 if (_forceLatest.contains(package.name)) { |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
654 void _validateSdkConstraint(Pubspec pubspec) { | 654 void _validateSdkConstraint(Pubspec pubspec) { |
655 if (_overrides.containsKey(pubspec.name)) return; | 655 if (_overrides.containsKey(pubspec.name)) return; |
656 if (pubspec.environment.sdkVersion.allows(sdk.version)) return; | 656 if (pubspec.environment.sdkVersion.allows(sdk.version)) return; |
657 | 657 |
658 throw new BadSdkVersionException(pubspec.name, | 658 throw new BadSdkVersionException(pubspec.name, |
659 'Package ${pubspec.name} requires SDK version ' | 659 'Package ${pubspec.name} requires SDK version ' |
660 '${pubspec.environment.sdkVersion} but the current SDK is ' | 660 '${pubspec.environment.sdkVersion} but the current SDK is ' |
661 '${sdk.version}.'); | 661 '${sdk.version}.'); |
662 } | 662 } |
663 } | 663 } |
OLD | NEW |