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 = _makeImplicitPubspec(systemCache) { |
135 _selection = new VersionSelection(this); | 128 _selection = new VersionSelection(this); |
136 | 129 |
137 for (var package in useLatest) { | 130 for (var package in useLatest) { |
138 _forceLatest.add(package); | 131 _forceLatest.add(package); |
139 } | 132 } |
140 | 133 |
141 for (var override in root.dependencyOverrides) { | 134 for (var override in root.dependencyOverrides) { |
142 _overrides[override.name] = override; | 135 _overrides[override.name] = override; |
143 } | 136 } |
144 } | 137 } |
145 | 138 |
| 139 /// Creates [_implicitPubspec]. |
| 140 static Pubspec _makeImplicitPubspec(SystemCache systemCache) { |
| 141 var dependencies = []; |
| 142 barback.pubConstraints.forEach((name, constraint) { |
| 143 dependencies.add( |
| 144 systemCache.sources.hosted.refFor(name) |
| 145 .withConstraint(constraint)); |
| 146 }); |
| 147 |
| 148 return new Pubspec("pub itself", dependencies: dependencies); |
| 149 } |
| 150 |
146 /// Run the solver. | 151 /// Run the solver. |
147 /// | 152 /// |
148 /// Completes with a list of specific package versions if successful or an | 153 /// Completes with a list of specific package versions if successful or an |
149 /// error if it failed to find a solution. | 154 /// error if it failed to find a solution. |
150 Future<SolveResult> solve() async { | 155 Future<SolveResult> solve() async { |
151 var stopwatch = new Stopwatch(); | 156 var stopwatch = new Stopwatch(); |
152 | 157 |
153 _logParameters(); | 158 _logParameters(); |
154 | 159 |
155 // Sort the overrides by package name to make sure they're deterministic. | 160 // Sort the overrides by package name to make sure they're deterministic. |
(...skipping 10 matching lines...) Expand all Loading... |
166 _validateSdkConstraint(root.pubspec); | 171 _validateSdkConstraint(root.pubspec); |
167 | 172 |
168 logSolve(); | 173 logSolve(); |
169 var packages = await _solve(); | 174 var packages = await _solve(); |
170 | 175 |
171 var pubspecs = {}; | 176 var pubspecs = {}; |
172 for (var id in packages) { | 177 for (var id in packages) { |
173 pubspecs[id.name] = await _getPubspec(id); | 178 pubspecs[id.name] = await _getPubspec(id); |
174 } | 179 } |
175 | 180 |
176 return new SolveResult.success(sources, root, lockFile, packages, | 181 return new SolveResult.success(systemCache.sources, root, lockFile, |
177 overrides, pubspecs, _getAvailableVersions(packages), | 182 packages, overrides, pubspecs, _getAvailableVersions(packages), |
178 _attemptedSolutions); | 183 _attemptedSolutions); |
179 } on SolveFailure catch (error) { | 184 } on SolveFailure catch (error) { |
180 // Wrap a failure in a result so we can attach some other data. | 185 // Wrap a failure in a result so we can attach some other data. |
181 return new SolveResult.failure(sources, root, lockFile, overrides, | 186 return new SolveResult.failure(systemCache.sources, root, lockFile, |
182 error, _attemptedSolutions); | 187 overrides, error, _attemptedSolutions); |
183 } finally { | 188 } finally { |
184 // Gather some solving metrics. | 189 // Gather some solving metrics. |
185 var buffer = new StringBuffer(); | 190 var buffer = new StringBuffer(); |
186 buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.'); | 191 buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.'); |
187 buffer.writeln(cache.describeResults()); | 192 buffer.writeln(cache.describeResults()); |
188 log.solver(buffer); | 193 log.solver(buffer); |
189 } | 194 } |
190 } | 195 } |
191 | 196 |
192 /// Generates a map containing all of the known available versions for each | 197 /// Generates a map containing all of the known available versions for each |
(...skipping 26 matching lines...) Expand all Loading... |
219 /// | 224 /// |
220 /// Returns `null` if it isn't in the lockfile (or has been unlocked). | 225 /// Returns `null` if it isn't in the lockfile (or has been unlocked). |
221 PackageId getLocked(String package) { | 226 PackageId getLocked(String package) { |
222 if (type == SolveType.GET) return lockFile.packages[package]; | 227 if (type == SolveType.GET) return lockFile.packages[package]; |
223 | 228 |
224 // When downgrading, we don't want to force the latest versions of | 229 // 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 | 230 // non-hosted packages, since they don't support multiple versions and thus |
226 // can't be downgraded. | 231 // can't be downgraded. |
227 if (type == SolveType.DOWNGRADE) { | 232 if (type == SolveType.DOWNGRADE) { |
228 var locked = lockFile.packages[package]; | 233 var locked = lockFile.packages[package]; |
229 if (locked != null && !sources[locked.source].hasMultipleVersions) { | 234 if (locked != null && |
| 235 !systemCache.sources[locked.source].hasMultipleVersions) { |
230 return locked; | 236 return locked; |
231 } | 237 } |
232 } | 238 } |
233 | 239 |
234 if (_forceLatest.isEmpty || _forceLatest.contains(package)) return null; | 240 if (_forceLatest.isEmpty || _forceLatest.contains(package)) return null; |
235 return lockFile.packages[package]; | 241 return lockFile.packages[package]; |
236 } | 242 } |
237 | 243 |
238 /// Gets the package [name] that's currently contained in the lockfile if it | 244 /// 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 | 245 /// matches the current constraint and has the same source and description as |
240 /// other references to that package. | 246 /// other references to that package. |
241 /// | 247 /// |
242 /// Returns `null` otherwise. | 248 /// Returns `null` otherwise. |
243 PackageId _getValidLocked(String name) { | 249 PackageId _getValidLocked(String name) { |
244 var package = getLocked(name); | 250 var package = getLocked(name); |
245 if (package == null) return null; | 251 if (package == null) return null; |
246 | 252 |
247 var constraint = _selection.getConstraint(name); | 253 var constraint = _selection.getConstraint(name); |
248 if (!constraint.allows(package.version)) { | 254 if (!constraint.allows(package.version)) { |
249 logSolve('$package is locked but does not match $constraint'); | 255 logSolve('$package is locked but does not match $constraint'); |
250 return null; | 256 return null; |
251 } else { | 257 } else { |
252 logSolve('$package is locked'); | 258 logSolve('$package is locked'); |
253 } | 259 } |
254 | 260 |
255 var required = _selection.getRequiredDependency(name); | 261 var required = _selection.getRequiredDependency(name); |
256 if (required != null) { | 262 if (required != null) { |
257 if (package.source != required.dep.source) return null; | 263 if (package.source != required.dep.source) return null; |
258 | 264 |
259 var source = sources[package.source]; | 265 var source = systemCache.sources[package.source]; |
260 if (!source.descriptionsEqual( | 266 if (!source.descriptionsEqual( |
261 package.description, required.dep.description)) return null; | 267 package.description, required.dep.description)) return null; |
262 } | 268 } |
263 | 269 |
264 return package; | 270 return package; |
265 } | 271 } |
266 | 272 |
267 /// Tries to find the best set of versions that meet the constraints. | 273 /// Tries to find the best set of versions that meet the constraints. |
268 /// | 274 /// |
269 /// Selects matching versions of unselected packages, or backtracks if there | 275 /// 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); | 529 _fail(otherDep.depender.name); |
524 } | 530 } |
525 | 531 |
526 logSolve( | 532 logSolve( |
527 'inconsistent source "${dep.source}" for ${dep.name}:\n' | 533 'inconsistent source "${dep.source}" for ${dep.name}:\n' |
528 ' $dependency\n' + | 534 ' $dependency\n' + |
529 _selection.describeDependencies(dep.name)); | 535 _selection.describeDependencies(dep.name)); |
530 throw new SourceMismatchException(dep.name, allDeps); | 536 throw new SourceMismatchException(dep.name, allDeps); |
531 } | 537 } |
532 | 538 |
533 var source = sources[dep.source]; | 539 var source = systemCache.sources[dep.source]; |
534 if (!source.descriptionsEqual( | 540 if (!source.descriptionsEqual( |
535 dep.description, required.dep.description)) { | 541 dep.description, required.dep.description)) { |
536 // Mark the dependers as failing rather than the package itself, because | 542 // Mark the dependers as failing rather than the package itself, because |
537 // no version with this description will be compatible. | 543 // no version with this description will be compatible. |
538 for (var otherDep in _selection.getDependenciesOn(dep.name)) { | 544 for (var otherDep in _selection.getDependenciesOn(dep.name)) { |
539 _fail(otherDep.depender.name); | 545 _fail(otherDep.depender.name); |
540 } | 546 } |
541 | 547 |
542 logSolve( | 548 logSolve( |
543 'inconsistent description "${dep.description}" for ${dep.name}:\n' | 549 'inconsistent description "${dep.description}" for ${dep.name}:\n' |
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
582 // Not overridden. | 588 // Not overridden. |
583 return dep; | 589 return dep; |
584 }).toSet(); | 590 }).toSet(); |
585 } else { | 591 } else { |
586 // Ignore any overridden dependencies. | 592 // Ignore any overridden dependencies. |
587 deps.removeWhere((dep) => _overrides.containsKey(dep.name)); | 593 deps.removeWhere((dep) => _overrides.containsKey(dep.name)); |
588 } | 594 } |
589 | 595 |
590 // Make sure the package doesn't have any bad dependencies. | 596 // Make sure the package doesn't have any bad dependencies. |
591 for (var dep in deps.toSet()) { | 597 for (var dep in deps.toSet()) { |
592 if (!dep.isRoot && sources[dep.source] is UnknownSource) { | 598 if (!dep.isRoot && systemCache.sources[dep.source] is UnknownSource) { |
593 throw new UnknownSourceException(id.name, [new Dependency(id, dep)]); | 599 throw new UnknownSourceException(id.name, [new Dependency(id, dep)]); |
594 } | 600 } |
595 | 601 |
596 if (dep.name == 'barback') { | 602 if (dep.name == 'barback') { |
597 deps.add(new PackageDep.magic('pub itself')); | 603 deps.add(new PackageDep.magic('pub itself')); |
598 } | 604 } |
599 } | 605 } |
600 | 606 |
601 return deps; | 607 return deps; |
602 } | 608 } |
603 | 609 |
604 /// Loads and returns the pubspec for [id]. | 610 /// Loads and returns the pubspec for [id]. |
605 Future<Pubspec> _getPubspec(PackageId id) async { | 611 Future<Pubspec> _getPubspec(PackageId id) async { |
606 if (id.isRoot) return root.pubspec; | 612 if (id.isRoot) return root.pubspec; |
607 if (id.isMagic && id.name == 'pub itself') return _implicitPubspec; | 613 if (id.isMagic && id.name == 'pub itself') return _implicitPubspec; |
608 | 614 return await systemCache.source(id.source).describe(id); |
609 var source = sources[id.source]; | |
610 return await source.describe(id); | |
611 } | 615 } |
612 | 616 |
613 /// Logs the initial parameters to the solver. | 617 /// Logs the initial parameters to the solver. |
614 void _logParameters() { | 618 void _logParameters() { |
615 var buffer = new StringBuffer(); | 619 var buffer = new StringBuffer(); |
616 buffer.writeln("Solving dependencies:"); | 620 buffer.writeln("Solving dependencies:"); |
617 for (var package in root.dependencies) { | 621 for (var package in root.dependencies) { |
618 buffer.write("- $package"); | 622 buffer.write("- $package"); |
619 var locked = getLocked(package.name); | 623 var locked = getLocked(package.name); |
620 if (_forceLatest.contains(package.name)) { | 624 if (_forceLatest.contains(package.name)) { |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
654 void _validateSdkConstraint(Pubspec pubspec) { | 658 void _validateSdkConstraint(Pubspec pubspec) { |
655 if (_overrides.containsKey(pubspec.name)) return; | 659 if (_overrides.containsKey(pubspec.name)) return; |
656 if (pubspec.environment.sdkVersion.allows(sdk.version)) return; | 660 if (pubspec.environment.sdkVersion.allows(sdk.version)) return; |
657 | 661 |
658 throw new BadSdkVersionException(pubspec.name, | 662 throw new BadSdkVersionException(pubspec.name, |
659 'Package ${pubspec.name} requires SDK version ' | 663 'Package ${pubspec.name} requires SDK version ' |
660 '${pubspec.environment.sdkVersion} but the current SDK is ' | 664 '${pubspec.environment.sdkVersion} but the current SDK is ' |
661 '${sdk.version}.'); | 665 '${sdk.version}.'); |
662 } | 666 } |
663 } | 667 } |
OLD | NEW |