| 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 48 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 59 /// versions for speculative package selections. Backtracks and advances to the | 59 /// versions for speculative package selections. Backtracks and advances to the |
| 60 /// next potential solution in the case of a failure. | 60 /// next potential solution in the case of a failure. |
| 61 class BacktrackingSolver { | 61 class BacktrackingSolver { |
| 62 final SolveType type; | 62 final SolveType type; |
| 63 final SourceRegistry sources; | 63 final SourceRegistry sources; |
| 64 final Package root; | 64 final Package root; |
| 65 | 65 |
| 66 /// The lockfile that was present before solving. | 66 /// The lockfile that was present before solving. |
| 67 final LockFile lockFile; | 67 final LockFile lockFile; |
| 68 | 68 |
| 69 final PubspecCache cache; | 69 /// A cache of data requested during solving. |
| 70 final SolverCache cache; |
| 70 | 71 |
| 71 /// The set of packages that are being explicitly upgraded. | 72 /// The set of packages that are being explicitly upgraded. |
| 72 /// | 73 /// |
| 73 /// The solver will only allow the very latest version for each of these | 74 /// The solver will only allow the very latest version for each of these |
| 74 /// packages. | 75 /// packages. |
| 75 final _forceLatest = new Set<String>(); | 76 final _forceLatest = new Set<String>(); |
| 76 | 77 |
| 77 /// The set of packages whose dependecy is being overridden by the root | 78 /// The set of packages whose dependecy is being overridden by the root |
| 78 /// package, keyed by the name of the package. | 79 /// package, keyed by the name of the package. |
| 79 /// | 80 /// |
| (...skipping 30 matching lines...) Expand all Loading... |
| 110 /// two differences. First, [_versions] doesn't have an entry for the root | 111 /// two differences. First, [_versions] doesn't have an entry for the root |
| 111 /// package, since it has only one valid version, but [_selection] does, since | 112 /// package, since it has only one valid version, but [_selection] does, since |
| 112 /// its dependencies are relevant. Second, when backtracking, [_versions] | 113 /// its dependencies are relevant. Second, when backtracking, [_versions] |
| 113 /// contains the version that's being backtracked, while [_selection] does | 114 /// contains the version that's being backtracked, while [_selection] does |
| 114 /// not. | 115 /// not. |
| 115 VersionSelection _selection; | 116 VersionSelection _selection; |
| 116 | 117 |
| 117 /// The number of solutions the solver has tried so far. | 118 /// The number of solutions the solver has tried so far. |
| 118 var _attemptedSolutions = 1; | 119 var _attemptedSolutions = 1; |
| 119 | 120 |
| 121 /// A pubspec for pub's implicit dependencies on barback and related packages. |
| 122 final Pubspec _implicitPubspec = () { |
| 123 var dependencies = []; |
| 124 barback.pubConstraints.forEach((name, constraint) { |
| 125 dependencies.add(new PackageDep(name, "hosted", constraint, name)); |
| 126 }); |
| 127 |
| 128 return new Pubspec("pub itself", dependencies: dependencies); |
| 129 }(); |
| 130 |
| 120 BacktrackingSolver(SolveType type, SourceRegistry sources, this.root, | 131 BacktrackingSolver(SolveType type, SourceRegistry sources, this.root, |
| 121 this.lockFile, List<String> useLatest) | 132 this.lockFile, List<String> useLatest) |
| 122 : type = type, | 133 : type = type, |
| 123 sources = sources, | 134 sources = sources, |
| 124 cache = new PubspecCache(type, sources) { | 135 cache = new SolverCache(type, sources) { |
| 125 _selection = new VersionSelection(this); | 136 _selection = new VersionSelection(this); |
| 126 | 137 |
| 127 for (var package in useLatest) { | 138 for (var package in useLatest) { |
| 128 _forceLatest.add(package); | 139 _forceLatest.add(package); |
| 129 } | 140 } |
| 130 | 141 |
| 131 for (var override in root.dependencyOverrides) { | 142 for (var override in root.dependencyOverrides) { |
| 132 _overrides[override.name] = override; | 143 _overrides[override.name] = override; |
| 133 } | 144 } |
| 134 } | 145 } |
| 135 | 146 |
| 136 /// Run the solver. | 147 /// Run the solver. |
| 137 /// | 148 /// |
| 138 /// Completes with a list of specific package versions if successful or an | 149 /// Completes with a list of specific package versions if successful or an |
| 139 /// error if it failed to find a solution. | 150 /// error if it failed to find a solution. |
| 140 Future<SolveResult> solve() async { | 151 Future<SolveResult> solve() async { |
| 141 var stopwatch = new Stopwatch(); | 152 var stopwatch = new Stopwatch(); |
| 142 | 153 |
| 143 _logParameters(); | 154 _logParameters(); |
| 144 | 155 |
| 145 // Sort the overrides by package name to make sure they're deterministic. | 156 // Sort the overrides by package name to make sure they're deterministic. |
| 146 var overrides = _overrides.values.toList(); | 157 var overrides = _overrides.values.toList(); |
| 147 overrides.sort((a, b) => a.name.compareTo(b.name)); | 158 overrides.sort((a, b) => a.name.compareTo(b.name)); |
| 148 | 159 |
| 149 try { | 160 try { |
| 150 stopwatch.start(); | 161 stopwatch.start(); |
| 151 | 162 |
| 152 // Pre-cache the root package's known pubspec. | 163 // Pre-cache the root package's known pubspec. |
| 153 var rootID = new PackageId.root(root); | 164 var rootID = new PackageId.root(root); |
| 154 cache.cache(rootID, root.pubspec); | |
| 155 cache.cache(new PackageId.magic('pub itself'), _implicitPubspec()); | |
| 156 await _selection.select(rootID); | 165 await _selection.select(rootID); |
| 157 | 166 |
| 158 _validateSdkConstraint(root.pubspec); | 167 _validateSdkConstraint(root.pubspec); |
| 159 | 168 |
| 160 logSolve(); | 169 logSolve(); |
| 161 var packages = await _solve(); | 170 var packages = await _solve(); |
| 162 | 171 |
| 163 var pubspecs = new Map.fromIterable(packages, | 172 var pubspecs = {}; |
| 164 key: (id) => id.name, | 173 for (var id in packages) { |
| 165 value: (id) => cache.getCachedPubspec(id)); | 174 pubspecs[id.name] = await _getPubspec(id); |
| 175 } |
| 166 | 176 |
| 167 var resolved = await Future.wait( | 177 var resolved = await Future.wait( |
| 168 packages.map((id) => sources[id.source].resolveId(id))); | 178 packages.map((id) => sources[id.source].resolveId(id))); |
| 169 | 179 |
| 170 return new SolveResult.success(sources, root, lockFile, resolved, | 180 return new SolveResult.success(sources, root, lockFile, resolved, |
| 171 overrides, pubspecs, _getAvailableVersions(resolved), | 181 overrides, pubspecs, _getAvailableVersions(resolved), |
| 172 _attemptedSolutions); | 182 _attemptedSolutions); |
| 173 } on SolveFailure catch (error) { | 183 } on SolveFailure catch (error) { |
| 174 // Wrap a failure in a result so we can attach some other data. | 184 // Wrap a failure in a result so we can attach some other data. |
| 175 return new SolveResult.failure(sources, root, lockFile, overrides, | 185 return new SolveResult.failure(sources, root, lockFile, overrides, |
| 176 error, _attemptedSolutions); | 186 error, _attemptedSolutions); |
| 177 } finally { | 187 } finally { |
| 178 // Gather some solving metrics. | 188 // Gather some solving metrics. |
| 179 var buffer = new StringBuffer(); | 189 var buffer = new StringBuffer(); |
| 180 buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.'); | 190 buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.'); |
| 181 buffer.writeln(cache.describeResults()); | 191 buffer.writeln(cache.describeResults()); |
| 182 log.solver(buffer); | 192 log.solver(buffer); |
| 183 } | 193 } |
| 184 } | 194 } |
| 185 | 195 |
| 186 /// Creates a pubspec for pub's implicit dependencies on barback and related | |
| 187 /// packages. | |
| 188 Pubspec _implicitPubspec() { | |
| 189 var dependencies = []; | |
| 190 barback.pubConstraints.forEach((name, constraint) { | |
| 191 dependencies.add(new PackageDep(name, "hosted", constraint, name)); | |
| 192 }); | |
| 193 | |
| 194 return new Pubspec("pub itself", dependencies: dependencies); | |
| 195 } | |
| 196 | |
| 197 /// Generates a map containing all of the known available versions for each | 196 /// Generates a map containing all of the known available versions for each |
| 198 /// package in [packages]. | 197 /// package in [packages]. |
| 199 /// | 198 /// |
| 200 /// The version list may not always be complete. If the package is the root | 199 /// The version list may not always be complete. If the package is the root |
| 201 /// root package, or if it's a package that we didn't unlock while solving | 200 /// root package, or if it's a package that we didn't unlock while solving |
| 202 /// because we weren't trying to upgrade it, we will just know the current | 201 /// because we weren't trying to upgrade it, we will just know the current |
| 203 /// version. | 202 /// version. |
| 204 Map<String, List<Version>> _getAvailableVersions(List<PackageId> packages) { | 203 Map<String, List<Version>> _getAvailableVersions(List<PackageId> packages) { |
| 205 var availableVersions = new Map<String, List<Version>>(); | 204 var availableVersions = new Map<String, List<Version>>(); |
| 206 for (var package in packages) { | 205 for (var package in packages) { |
| (...skipping 262 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 469 | 468 |
| 470 logSolve( | 469 logSolve( |
| 471 "version ${id.version} of ${id.name} doesn't match $constraint:\n" + | 470 "version ${id.version} of ${id.name} doesn't match $constraint:\n" + |
| 472 _selection.describeDependencies(id.name)); | 471 _selection.describeDependencies(id.name)); |
| 473 throw new NoVersionException( | 472 throw new NoVersionException( |
| 474 id.name, id.version, constraint, deps.toList()); | 473 id.name, id.version, constraint, deps.toList()); |
| 475 } | 474 } |
| 476 | 475 |
| 477 var pubspec; | 476 var pubspec; |
| 478 try { | 477 try { |
| 479 pubspec = await cache.getPubspec(id); | 478 pubspec = await _getPubspec(id); |
| 480 } on PackageNotFoundException { | 479 } on PackageNotFoundException { |
| 481 // We can only get here if the lockfile refers to a specific package | 480 // We can only get here if the lockfile refers to a specific package |
| 482 // version that doesn't exist (probably because it was yanked). | 481 // version that doesn't exist (probably because it was yanked). |
| 483 throw new NoVersionException(id.name, null, id.version, []); | 482 throw new NoVersionException(id.name, null, id.version, []); |
| 484 } | 483 } |
| 485 | 484 |
| 486 _validateSdkConstraint(pubspec); | 485 _validateSdkConstraint(pubspec); |
| 487 | 486 |
| 488 for (var dep in await depsFor(id)) { | 487 for (var dep in await depsFor(id)) { |
| 489 if (dep.isMagic) continue; | 488 if (dep.isMagic) continue; |
| (...skipping 72 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 562 // Don't mark the root package as failing because it's not in [_versions] | 561 // Don't mark the root package as failing because it's not in [_versions] |
| 563 // and there's only one version of it anyway. | 562 // and there's only one version of it anyway. |
| 564 if (name == root.name) return; | 563 if (name == root.name) return; |
| 565 _versions.firstWhere((queue) => queue.current.name == name).fail(); | 564 _versions.firstWhere((queue) => queue.current.name == name).fail(); |
| 566 } | 565 } |
| 567 | 566 |
| 568 /// Returns the dependencies of the package identified by [id]. | 567 /// Returns the dependencies of the package identified by [id]. |
| 569 /// | 568 /// |
| 570 /// This takes overrides and dev dependencies into account when neccessary. | 569 /// This takes overrides and dev dependencies into account when neccessary. |
| 571 Future<Set<PackageDep>> depsFor(PackageId id) async { | 570 Future<Set<PackageDep>> depsFor(PackageId id) async { |
| 572 var pubspec = await cache.getPubspec(id); | 571 var pubspec = await _getPubspec(id); |
| 573 var deps = pubspec.dependencies.toSet(); | 572 var deps = pubspec.dependencies.toSet(); |
| 574 if (id.isRoot) { | 573 if (id.isRoot) { |
| 575 // Include dev dependencies of the root package. | 574 // Include dev dependencies of the root package. |
| 576 deps.addAll(pubspec.devDependencies); | 575 deps.addAll(pubspec.devDependencies); |
| 577 | 576 |
| 578 // Add all overrides. This ensures a dependency only present as an | 577 // Add all overrides. This ensures a dependency only present as an |
| 579 // override is still included. | 578 // override is still included. |
| 580 deps.addAll(_overrides.values); | 579 deps.addAll(_overrides.values); |
| 581 | 580 |
| 582 // Replace any overridden dependencies. | 581 // Replace any overridden dependencies. |
| (...skipping 16 matching lines...) Expand all Loading... |
| 599 } | 598 } |
| 600 | 599 |
| 601 if (dep.name == 'barback') { | 600 if (dep.name == 'barback') { |
| 602 deps.add(new PackageDep.magic('pub itself')); | 601 deps.add(new PackageDep.magic('pub itself')); |
| 603 } | 602 } |
| 604 } | 603 } |
| 605 | 604 |
| 606 return deps; | 605 return deps; |
| 607 } | 606 } |
| 608 | 607 |
| 608 /// Loads and returns the pubspec for [id]. |
| 609 Future<Pubspec> _getPubspec(PackageId id) async { |
| 610 if (id.isRoot) return root.pubspec; |
| 611 if (id.isMagic && id.name == 'pub itself') return _implicitPubspec; |
| 612 |
| 613 var source = sources[id.source]; |
| 614 return await source.describe(id); |
| 615 } |
| 616 |
| 609 /// Logs the initial parameters to the solver. | 617 /// Logs the initial parameters to the solver. |
| 610 void _logParameters() { | 618 void _logParameters() { |
| 611 var buffer = new StringBuffer(); | 619 var buffer = new StringBuffer(); |
| 612 buffer.writeln("Solving dependencies:"); | 620 buffer.writeln("Solving dependencies:"); |
| 613 for (var package in root.dependencies) { | 621 for (var package in root.dependencies) { |
| 614 buffer.write("- $package"); | 622 buffer.write("- $package"); |
| 615 var locked = getLocked(package.name); | 623 var locked = getLocked(package.name); |
| 616 if (_forceLatest.contains(package.name)) { | 624 if (_forceLatest.contains(package.name)) { |
| 617 buffer.write(" (use latest)"); | 625 buffer.write(" (use latest)"); |
| 618 } else if (locked != null) { | 626 } else if (locked != null) { |
| (...skipping 31 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 650 void _validateSdkConstraint(Pubspec pubspec) { | 658 void _validateSdkConstraint(Pubspec pubspec) { |
| 651 if (_overrides.containsKey(pubspec.name)) return; | 659 if (_overrides.containsKey(pubspec.name)) return; |
| 652 if (pubspec.environment.sdkVersion.allows(sdk.version)) return; | 660 if (pubspec.environment.sdkVersion.allows(sdk.version)) return; |
| 653 | 661 |
| 654 throw new BadSdkVersionException(pubspec.name, | 662 throw new BadSdkVersionException(pubspec.name, |
| 655 'Package ${pubspec.name} requires SDK version ' | 663 'Package ${pubspec.name} requires SDK version ' |
| 656 '${pubspec.environment.sdkVersion} but the current SDK is ' | 664 '${pubspec.environment.sdkVersion} but the current SDK is ' |
| 657 '${sdk.version}.'); | 665 '${sdk.version}.'); |
| 658 } | 666 } |
| 659 } | 667 } |
| OLD | NEW |