| 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 |