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. Attempts to find the best solution for | 5 /// A back-tracking depth-first solver. Attempts to find the best solution for |
6 /// a root package's transitive dependency graph, where a "solution" is a set | 6 /// a root package's transitive dependency graph, where a "solution" is a set |
7 /// of concrete package versions. A valid solution will select concrete | 7 /// of concrete package versions. A valid solution will select concrete |
8 /// versions for every package reached from the root package's dependency graph, | 8 /// versions for every package reached from the root package's dependency graph, |
9 /// and each of those packages will fit the version constraints placed on it. | 9 /// and each of those packages will fit the version constraints placed on it. |
10 /// | 10 /// |
(...skipping 174 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
185 /// Backtracks from the current failed solution and determines the next | 185 /// Backtracks from the current failed solution and determines the next |
186 /// solution to try. If possible, it will backjump based on the cause of the | 186 /// solution to try. If possible, it will backjump based on the cause of the |
187 /// [failure] to minize backtracking. Otherwise, it will simply backtrack to | 187 /// [failure] to minize backtracking. Otherwise, it will simply backtrack to |
188 /// the next possible solution. | 188 /// the next possible solution. |
189 /// | 189 /// |
190 /// Returns `true` if there is a new solution to try. | 190 /// Returns `true` if there is a new solution to try. |
191 bool _backtrack(SolveFailure failure) { | 191 bool _backtrack(SolveFailure failure) { |
192 var dependers = failure.dependencies.map((dep) => dep.depender).toSet(); | 192 var dependers = failure.dependencies.map((dep) => dep.depender).toSet(); |
193 | 193 |
194 while (!_selected.isEmpty) { | 194 while (!_selected.isEmpty) { |
195 // Look for a relevant selection to jump back to. | 195 _backjump(failure); |
196 for (var i = _selected.length - 1; i >= 0; i--) { | |
197 // Can't jump to a package that has no more alternatives. | |
198 if (_selected[i].length == 1) continue; | |
199 | |
200 var selected = _selected[i].first; | |
201 | |
202 // If we find the package itself that failed, jump to it. | |
203 if (selected.name == failure.package) { | |
204 logSolve('jump to selected package ${failure.package}'); | |
205 _selected.removeRange(i + 1, _selected.length); | |
206 break; | |
207 } | |
208 | |
209 // See if this package directly or indirectly depends on [package]. | |
210 var path = _getDependencyPath(selected, failure.package); | |
211 if (path != null) { | |
212 logSolve('backjump to ${selected.name} because it depends on ' | |
213 '${failure.package} by $path'); | |
214 _selected.removeRange(i + 1, _selected.length); | |
215 break; | |
216 } | |
217 } | |
218 | 196 |
219 // Advance past the current version of the leaf-most package. | 197 // Advance past the current version of the leaf-most package. |
220 var previous = _selected.last.removeFirst(); | 198 var previous = _selected.last.removeFirst(); |
221 if (!_selected.last.isEmpty) { | 199 if (!_selected.last.isEmpty) { |
222 logSolve(); | 200 logSolve(); |
223 return true; | 201 return true; |
224 } | 202 } |
225 | 203 |
226 logSolve('$previous is last version, backtracking'); | 204 logSolve('$previous is last version, backtracking'); |
227 | 205 |
228 // That package has no more versions, so pop it and try the next one. | 206 // That package has no more versions, so pop it and try the next one. |
229 _selected.removeLast(); | 207 _selected.removeLast(); |
230 } | 208 } |
231 | 209 |
232 return false; | 210 return false; |
233 } | 211 } |
234 | 212 |
| 213 /// Walks the selected packages from most to least recent to determine which |
| 214 /// ones can be ignored and jumped over by the backtracker. The only packages |
| 215 /// we need to backtrack to are ones that have other versions to try and that |
| 216 /// led (possibly indirectly) to the failure. Everything else can be skipped. |
| 217 void _backjump(SolveFailure failure) { |
| 218 for (var i = _selected.length - 1; i >= 0; i--) { |
| 219 // Each queue will never be empty since it gets discarded by _backtrack() |
| 220 // when that happens. |
| 221 var selected = _selected[i].first; |
| 222 |
| 223 // If the package has no more versions, we can jump over it. |
| 224 if (_selected[i].length == 1) continue; |
| 225 |
| 226 // If we get to the package that failed, backtrack to here. |
| 227 if (selected.name == failure.package) { |
| 228 logSolve('backjump to failed package ${selected.name}'); |
| 229 _selected.removeRange(i + 1, _selected.length); |
| 230 return; |
| 231 } |
| 232 |
| 233 // If we get to a package that depends on the failing package, backtrack |
| 234 // to here. |
| 235 var path = _getDependencyPath(selected, failure.package); |
| 236 if (path != null) { |
| 237 logSolve('backjump to ${selected.name} because it depends on ' |
| 238 '${failure.package} along $path'); |
| 239 _selected.removeRange(i + 1, _selected.length); |
| 240 return; |
| 241 } |
| 242 } |
| 243 |
| 244 // If we got here, we walked the entire list without finding a package that |
| 245 // could lead to another solution, so discard everything. This will happen |
| 246 // if every package that led to the failure has no other versions that it |
| 247 // can try to select. |
| 248 _selected.removeRange(1, _selected.length); |
| 249 } |
| 250 |
235 /// Determines if [depender] has a direct or indirect dependency on | 251 /// Determines if [depender] has a direct or indirect dependency on |
236 /// [dependent] based on the currently selected versions of all packages. | 252 /// [dependent] based on the currently selected versions of all packages. |
237 /// Returns a string describing the dependency chain if it does, or `null` if | 253 /// Returns a string describing the dependency chain if it does, or `null` if |
238 /// there is no dependency. | 254 /// there is no dependency. |
239 String _getDependencyPath(PackageId depender, String dependent) { | 255 String _getDependencyPath(PackageId depender, String dependent) { |
240 // TODO(rnystrom): This is O(n^2) where n is the number of selected | 256 // TODO(rnystrom): This is O(n^2) where n is the number of selected |
241 // packages. Could store the reverse dependency graph to address that. If | 257 // packages. Could store the reverse dependency graph to address that. If |
242 // we do that, we need to make sure it gets correctly rolled back when | 258 // we do that, we need to make sure it gets correctly rolled back when |
243 // backtracking occurs. | 259 // backtracking occurs. |
244 var visited = new Set<String>(); | 260 var visited = new Set<String>(); |
(...skipping 342 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
587 /// with the current SDK. Throws a [SolverFailure] if not. | 603 /// with the current SDK. Throws a [SolverFailure] if not. |
588 void _validateSdkConstraint(Pubspec pubspec) { | 604 void _validateSdkConstraint(Pubspec pubspec) { |
589 // If the user is running a continouous build of the SDK, just disable SDK | 605 // If the user is running a continouous build of the SDK, just disable SDK |
590 // constraint checking entirely. The actual version number you get is | 606 // constraint checking entirely. The actual version number you get is |
591 // impossibly old and not correct. We'll just assume users on continuous | 607 // impossibly old and not correct. We'll just assume users on continuous |
592 // know what they're doing. | 608 // know what they're doing. |
593 if (sdk.isBleedingEdge) return; | 609 if (sdk.isBleedingEdge) return; |
594 | 610 |
595 if (pubspec.environment.sdkVersion.allows(sdk.version)) return; | 611 if (pubspec.environment.sdkVersion.allows(sdk.version)) return; |
596 | 612 |
597 throw new CouldNotSolveException( | 613 throw new BadSdkVersionException(pubspec.name, |
598 'Package ${pubspec.name} requires SDK version ' | 614 'Package ${pubspec.name} requires SDK version ' |
599 '${pubspec.environment.sdkVersion} but the current SDK is ' | 615 '${pubspec.environment.sdkVersion} but the current SDK is ' |
600 '${sdk.version}.'); | 616 '${sdk.version}.'); |
601 } | 617 } |
OLD | NEW |