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 157 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
168 } | 168 } |
169 } | 169 } |
170 | 170 |
171 // Advance past the current version of the leaf-most package. | 171 // Advance past the current version of the leaf-most package. |
172 var previous = _selected.last.removeFirst(); | 172 var previous = _selected.last.removeFirst(); |
173 if (!_selected.last.isEmpty) { | 173 if (!_selected.last.isEmpty) { |
174 logSolve(); | 174 logSolve(); |
175 return true; | 175 return true; |
176 } | 176 } |
177 | 177 |
178 logSolve('${previous} is last version, backtracking'); | 178 logSolve('$previous is last version, backtracking'); |
179 | 179 |
180 // That package has no more versions, so pop it and try the next one. | 180 // That package has no more versions, so pop it and try the next one. |
181 _selected.removeLast(); | 181 _selected.removeLast(); |
182 } | 182 } |
183 | 183 |
184 return false; | 184 return false; |
185 } | 185 } |
186 | 186 |
187 /// Determines if [depender] has a direct or indirect dependency on | 187 /// Determines if [depender] has a direct or indirect dependency on |
188 /// [dependent] based on the currently selected versions of all packages. | 188 /// [dependent] based on the currently selected versions of all packages. |
189 /// Returns a string describing the dependency chain if it does, or `null` if | 189 /// Returns a string describing the dependency chain if it does, or `null` if |
190 /// there is no dependency. | 190 /// there is no dependency. |
191 String _getDependencyPath(PackageId depender, String dependent) { | 191 String _getDependencyPath(PackageId depender, String dependent) { |
| 192 // TODO(rnystrom): This is O(n^2) where n is the number of selected |
| 193 // packages. Could store the reverse dependency graph to address that. If |
| 194 // we do that, we need to make sure it gets correctly rolled back when |
| 195 // backtracking occurs. |
192 var visited = new Set<String>(); | 196 var visited = new Set<String>(); |
193 var resultPath; | |
194 var currentPath = '${depender.name}'; | |
195 | 197 |
196 walkDeps(PackageId package) { | 198 walkDeps(PackageId package, String currentPath) { |
197 if (visited.contains(package.name)) return false; | 199 if (visited.contains(package.name)) return null; |
198 visited.add(package.name); | 200 visited.add(package.name); |
199 | 201 |
200 var pubspec = cache.getCachedPubspec(package); | 202 var pubspec = cache.getCachedPubspec(package); |
201 if (pubspec == null) return false; | 203 if (pubspec == null) return null; |
202 | 204 |
203 for (var dep in pubspec.dependencies) { | 205 for (var dep in pubspec.dependencies) { |
204 var previousPath = currentPath; | 206 if (dep.name == dependent) return currentPath; |
205 currentPath = '$currentPath -> ${dep.name}'; | |
206 | |
207 if (dep.name == dependent) { | |
208 resultPath = currentPath; | |
209 return true; | |
210 } | |
211 | 207 |
212 var selected = getSelected(dep.name); | 208 var selected = getSelected(dep.name); |
213 // Ignore unselected dependencies. We haven't traversed into them yet, | 209 // Ignore unselected dependencies. We haven't traversed into them yet, |
214 // so they can't affect backjumping. | 210 // so they can't affect backjumping. |
215 if (selected == null) continue; | 211 if (selected == null) continue; |
216 | 212 |
217 if (walkDeps(selected)) return true; | 213 var depPath = walkDeps(selected, '$currentPath -> ${dep.name}'); |
218 | 214 if (depPath != null) return depPath; |
219 currentPath = previousPath; | |
220 } | 215 } |
221 | 216 |
222 return false; | 217 return null; |
223 } | 218 } |
224 | 219 |
225 return walkDeps(depender) ? resultPath : null; | 220 return walkDeps(depender, depender.name); |
226 } | 221 } |
227 | 222 |
228 /// Logs [message] in the context of the current selected packages. If | 223 /// Logs [message] in the context of the current selected packages. If |
229 /// [message] is omitted, just logs a description of leaf-most selection. | 224 /// [message] is omitted, just logs a description of leaf-most selection. |
230 void logSolve([String message]) { | 225 void logSolve([String message]) { |
231 if (message == null) { | 226 if (message == null) { |
232 if (_selected.isEmpty) { | 227 if (_selected.isEmpty) { |
233 message = "* start at root"; | 228 message = "* start at root"; |
234 } else { | 229 } else { |
235 var versions = _selected.last.map((id) => id.version).toList(); | 230 var count = _selected.last.length; |
236 if (versions.length > 5) { | 231 message = "* select ${_selected.last.first} ($count versions)"; |
237 versions = versions.take(5).join(', ') + '...'; | |
238 } else { | |
239 versions = versions.join(', '); | |
240 } | |
241 message = "* select ${_selected.last.first} (from $versions)"; | |
242 } | 232 } |
243 } else { | 233 } else { |
244 // Otherwise, indent it under the current selected package. | 234 // Otherwise, indent it under the current selected package. |
245 message = "| $message"; | 235 message = "| $message"; |
246 } | 236 } |
247 | 237 |
248 // Indent for the previous selections. | 238 // Indent for the previous selections. |
249 var buffer = new StringBuffer(); | 239 var buffer = new StringBuffer(); |
250 buffer.writeAll(_selected.skip(1).map((_) => '| ')); | 240 buffer.writeAll(_selected.skip(1).map((_) => '| ')); |
251 buffer.write(message); | 241 buffer.write(message); |
(...skipping 68 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
320 return new Future.value(new Pair<PackageRef, int>(ref, 1)); | 310 return new Future.value(new Pair<PackageRef, int>(ref, 1)); |
321 } | 311 } |
322 | 312 |
323 return _solver.cache.getVersions(ref.name, ref.source, ref.description) | 313 return _solver.cache.getVersions(ref.name, ref.source, ref.description) |
324 .then((versions) { | 314 .then((versions) { |
325 return new Pair<PackageRef, int>(ref, versions.length); | 315 return new Pair<PackageRef, int>(ref, versions.length); |
326 }).catchError((error) { | 316 }).catchError((error) { |
327 // If it fails for any reason, just treat that as no versions. This | 317 // If it fails for any reason, just treat that as no versions. This |
328 // will sort this reference higher so that we can traverse into it | 318 // will sort this reference higher so that we can traverse into it |
329 // and report the error more properly. | 319 // and report the error more properly. |
| 320 log.solver("Could not get versions for $ref:\n$error\n\n" |
| 321 "${getAttachedStackTrace(error)}"); |
330 return new Pair<PackageRef, int>(ref, 0); | 322 return new Pair<PackageRef, int>(ref, 0); |
331 }); | 323 }); |
332 } | 324 } |
333 | 325 |
334 return Future.wait(refs.map(getNumVersions)).then((pairs) { | 326 return Future.wait(refs.map(getNumVersions)).then((pairs) { |
335 // Future.wait() returns an immutable list, so make a copy. | 327 // Future.wait() returns an immutable list, so make a copy. |
336 pairs = pairs.toList(); | 328 pairs = pairs.toList(); |
337 | 329 |
338 // Sort in best-first order to minimize backtracking. | 330 // Sort in best-first order to minimize backtracking. |
339 pairs.sort((a, b) { | 331 pairs.sort((a, b) { |
(...skipping 19 matching lines...) Expand all Loading... |
359 | 351 |
360 /// Traverses the references that [depender] depends on, stored in [refs]. | 352 /// Traverses the references that [depender] depends on, stored in [refs]. |
361 /// Desctructively modifies [refs]. Completes to a list of packages if the | 353 /// Desctructively modifies [refs]. Completes to a list of packages if the |
362 /// traversal is complete. Completes it to an error if a failure occurred. | 354 /// traversal is complete. Completes it to an error if a failure occurred. |
363 /// Otherwise, recurses. | 355 /// Otherwise, recurses. |
364 Future<List<PackageId>> _traverseRefs(String depender, | 356 Future<List<PackageId>> _traverseRefs(String depender, |
365 Queue<PackageRef> refs) { | 357 Queue<PackageRef> refs) { |
366 // Move onto the next package if we've traversed all of these references. | 358 // Move onto the next package if we've traversed all of these references. |
367 if (refs.isEmpty) return _traversePackage(); | 359 if (refs.isEmpty) return _traversePackage(); |
368 | 360 |
| 361 // Pump the event loop to flatten the stack trace and workaround #9583. |
| 362 // If that bug is fixed, this can be Future.sync() instead. |
369 return new Future(() { | 363 return new Future(() { |
370 var ref = refs.removeFirst(); | 364 var ref = refs.removeFirst(); |
371 | 365 |
372 _validateDependency(ref, depender); | 366 _validateDependency(ref, depender); |
373 var constraint = _addConstraint(ref, depender); | 367 var constraint = _addConstraint(ref, depender); |
374 | 368 |
375 var selected = _validateSelected(ref, constraint); | 369 var selected = _validateSelected(ref, constraint); |
376 if (selected != null) { | 370 if (selected != null) { |
377 // The selected package version is good, so enqueue it to traverse into | 371 // The selected package version is good, so enqueue it to traverse into |
378 // it. | 372 // it. |
(...skipping 154 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
533 | 527 |
534 var required = _getRequired(name); | 528 var required = _getRequired(name); |
535 if (required != null) { | 529 if (required != null) { |
536 if (package.source.name != required.ref.source.name) return null; | 530 if (package.source.name != required.ref.source.name) return null; |
537 if (!package.descriptionEquals(required.ref)) return null; | 531 if (!package.descriptionEquals(required.ref)) return null; |
538 } | 532 } |
539 | 533 |
540 return package; | 534 return package; |
541 } | 535 } |
542 } | 536 } |
OLD | NEW |