Chromium Code Reviews| 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 |