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 329 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
340 | 340 |
341 // Don't visit the same package twice. | 341 // Don't visit the same package twice. |
342 if (_visited.contains(id)) { | 342 if (_visited.contains(id)) { |
343 return _traversePackage(); | 343 return _traversePackage(); |
344 } | 344 } |
345 _visited.add(id); | 345 _visited.add(id); |
346 | 346 |
347 return _solver.cache.getPubspec(id).then((pubspec) { | 347 return _solver.cache.getPubspec(id).then((pubspec) { |
348 _validateSdkConstraint(pubspec); | 348 _validateSdkConstraint(pubspec); |
349 | 349 |
350 var refs = pubspec.dependencies.toList(); | 350 var deps = pubspec.dependencies.toList(); |
351 | 351 |
352 // Include dev dependencies of the root package. | 352 // Include dev dependencies of the root package. |
353 if (id.isRoot) refs.addAll(pubspec.devDependencies); | 353 if (id.isRoot) deps.addAll(pubspec.devDependencies); |
354 | 354 |
355 // Given a package ref, returns a future that completes to a pair of the | 355 // Given a package dep, returns a future that completes to a pair of the |
356 // ref and the number of versions available for it. | 356 // dep and the number of versions available for it. |
357 getNumVersions(PackageRef ref) { | 357 getNumVersions(PackageDep dep) { |
358 // There is only ever one version of the root package. | 358 // There is only ever one version of the root package. |
359 if (ref.isRoot) { | 359 if (dep.isRoot) { |
360 return new Future.value(new Pair<PackageRef, int>(ref, 1)); | 360 return new Future.value(new Pair<PackageDep, int>(dep, 1)); |
361 } | 361 } |
362 | 362 |
363 return _solver.cache.getVersions(ref.name, ref.source, ref.description) | 363 return _solver.cache.getVersions(dep.toRef()).then((versions) { |
364 .then((versions) { | 364 return new Pair<PackageDep, int>(dep, versions.length); |
365 return new Pair<PackageRef, int>(ref, versions.length); | |
366 }).catchError((error) { | 365 }).catchError((error) { |
367 // If it fails for any reason, just treat that as no versions. This | 366 // If it fails for any reason, just treat that as no versions. This |
368 // will sort this reference higher so that we can traverse into it | 367 // will sort this reference higher so that we can traverse into it |
369 // and report the error more properly. | 368 // and report the error more properly. |
370 log.solver("Could not get versions for $ref:\n$error\n\n" | 369 log.solver("Could not get versions for $dep:\n$error\n\n" |
371 "${getAttachedStackTrace(error)}"); | 370 "${getAttachedStackTrace(error)}"); |
372 return new Pair<PackageRef, int>(ref, 0); | 371 return new Pair<PackageDep, int>(dep, 0); |
373 }); | 372 }); |
374 } | 373 } |
375 | 374 |
376 return Future.wait(refs.map(getNumVersions)).then((pairs) { | 375 return Future.wait(deps.map(getNumVersions)).then((pairs) { |
377 // Future.wait() returns an immutable list, so make a copy. | 376 // Future.wait() returns an immutable list, so make a copy. |
378 pairs = pairs.toList(); | 377 pairs = pairs.toList(); |
379 | 378 |
380 // Sort in best-first order to minimize backtracking. | 379 // Sort in best-first order to minimize backtracking. |
381 pairs.sort((a, b) { | 380 pairs.sort((a, b) { |
382 // Traverse into packages we've already selected first. | 381 // Traverse into packages we've already selected first. |
383 var aIsSelected = _solver.getSelected(a.first.name) != null; | 382 var aIsSelected = _solver.getSelected(a.first.name) != null; |
384 var bIsSelected = _solver.getSelected(b.first.name) != null; | 383 var bIsSelected = _solver.getSelected(b.first.name) != null; |
385 if (aIsSelected && !bIsSelected) return -1; | 384 if (aIsSelected && !bIsSelected) return -1; |
386 if (!aIsSelected && bIsSelected) return 1; | 385 if (!aIsSelected && bIsSelected) return 1; |
387 | 386 |
388 // Traverse into packages with fewer versions since they will lead to | 387 // Traverse into packages with fewer versions since they will lead to |
389 // less backtracking. | 388 // less backtracking. |
390 if (a.last != b.last) return a.last.compareTo(b.last); | 389 if (a.last != b.last) return a.last.compareTo(b.last); |
391 | 390 |
392 // Otherwise, just sort by name so that it's deterministic. | 391 // Otherwise, just sort by name so that it's deterministic. |
393 return a.first.name.compareTo(b.first.name); | 392 return a.first.name.compareTo(b.first.name); |
394 }); | 393 }); |
395 | 394 |
396 var queue = new Queue<PackageRef>.from(pairs.map((pair) => pair.first)); | 395 var queue = new Queue<PackageDep>.from(pairs.map((pair) => pair.first)); |
397 return _traverseRefs(id.name, queue); | 396 return _traverseDeps(id.name, queue); |
398 }); | 397 }); |
399 }); | 398 }); |
400 } | 399 } |
401 | 400 |
402 /// Traverses the references that [depender] depends on, stored in [refs]. | 401 /// Traverses the references that [depender] depends on, stored in [refs]. |
403 /// Desctructively modifies [refs]. Completes to a list of packages if the | 402 /// Desctructively modifies [refs]. Completes to a list of packages if the |
404 /// traversal is complete. Completes it to an error if a failure occurred. | 403 /// traversal is complete. Completes it to an error if a failure occurred. |
405 /// Otherwise, recurses. | 404 /// Otherwise, recurses. |
406 Future<List<PackageId>> _traverseRefs(String depender, | 405 Future<List<PackageId>> _traverseDeps(String depender, |
407 Queue<PackageRef> refs) { | 406 Queue<PackageDep> deps) { |
408 // Move onto the next package if we've traversed all of these references. | 407 // Move onto the next package if we've traversed all of these references. |
409 if (refs.isEmpty) return _traversePackage(); | 408 if (deps.isEmpty) return _traversePackage(); |
410 | 409 |
411 // Pump the event loop to flatten the stack trace and workaround #9583. | 410 // Pump the event loop to flatten the stack trace and workaround #9583. |
412 // If that bug is fixed, this can be Future.sync() instead. | 411 // If that bug is fixed, this can be Future.sync() instead. |
413 return new Future(() { | 412 return new Future(() { |
414 var ref = refs.removeFirst(); | 413 var dep = deps.removeFirst(); |
415 | 414 |
416 _validateDependency(ref, depender); | 415 _validateDependency(dep, depender); |
417 var constraint = _addConstraint(ref, depender); | 416 var constraint = _addConstraint(dep, depender); |
418 | 417 |
419 var selected = _validateSelected(ref, constraint); | 418 var selected = _validateSelected(dep, constraint); |
420 if (selected != null) { | 419 if (selected != null) { |
421 // The selected package version is good, so enqueue it to traverse into | 420 // The selected package version is good, so enqueue it to traverse into |
422 // it. | 421 // it. |
423 _packages.add(selected); | 422 _packages.add(selected); |
424 return _traverseRefs(depender, refs); | 423 return _traverseDeps(depender, deps); |
425 } | 424 } |
426 | 425 |
427 // We haven't selected a version. Get all of the versions that match the | 426 // We haven't selected a version. Get all of the versions that match the |
428 // constraints we currently have for this package and add them to the | 427 // constraints we currently have for this package and add them to the |
429 // set of solutions to try. | 428 // set of solutions to try. |
430 return _selectPackage(ref, constraint).then( | 429 return _selectPackage(dep, constraint).then( |
431 (_) => _traverseRefs(depender, refs)); | 430 (_) => _traverseDeps(depender, deps)); |
432 }); | 431 }); |
433 } | 432 } |
434 | 433 |
435 /// Ensures that dependency [ref] from [depender] is consistent with the | 434 /// Ensures that dependency [dep] from [depender] is consistent with the |
436 /// other dependencies on the same package. Throws a [SolverFailure] | 435 /// other dependencies on the same package. Throws a [SolverFailure] |
437 /// exception if not. Only validates sources and descriptions, not the | 436 /// exception if not. Only validates sources and descriptions, not the |
438 /// version. | 437 /// version. |
439 void _validateDependency(PackageRef ref, String depender) { | 438 void _validateDependency(PackageDep dep, String depender) { |
440 // Make sure the dependencies agree on source and description. | 439 // Make sure the dependencies agree on source and description. |
441 var required = _getRequired(ref.name); | 440 var required = _getRequired(dep.name); |
442 if (required == null) return; | 441 if (required == null) return; |
443 | 442 |
444 // Make sure all of the existing sources match the new reference. | 443 // Make sure all of the existing sources match the new reference. |
445 if (required.ref.source.name != ref.source.name) { | 444 if (required.dep.source.name != dep.source.name) { |
446 _solver.logSolve('source mismatch on ${ref.name}: ${required.ref.source} ' | 445 _solver.logSolve('source mismatch on ${dep.name}: ${required.dep.source} ' |
447 '!= ${ref.source}'); | 446 '!= ${dep.source}'); |
448 throw new SourceMismatchException(ref.name, | 447 throw new SourceMismatchException(dep.name, |
449 [required, new Dependency(depender, ref)]); | 448 [required, new Dependency(depender, dep)]); |
450 } | 449 } |
451 | 450 |
452 // Make sure all of the existing descriptions match the new reference. | 451 // Make sure all of the existing descriptions match the new reference. |
453 if (!ref.descriptionEquals(required.ref)) { | 452 if (!dep.descriptionEquals(required.dep)) { |
454 _solver.logSolve('description mismatch on ${ref.name}: ' | 453 _solver.logSolve('description mismatch on ${dep.name}: ' |
455 '${required.ref.description} != ${ref.description}'); | 454 '${required.dep.description} != ${dep.description}'); |
456 throw new DescriptionMismatchException(ref.name, | 455 throw new DescriptionMismatchException(dep.name, |
457 [required, new Dependency(depender, ref)]); | 456 [required, new Dependency(depender, dep)]); |
458 } | 457 } |
459 } | 458 } |
460 | 459 |
461 /// Adds the version constraint that [depender] places on [ref] to the | 460 /// Adds the version constraint that [depender] places on [dep] to the |
462 /// overall constraint that all shared dependencies place on [ref]. Throws a | 461 /// overall constraint that all shared dependencies place on [dep]. Throws a |
463 /// [SolverFailure] if that results in an unsolvable constraints. | 462 /// [SolverFailure] if that results in an unsolvable constraints. |
464 /// | 463 /// |
465 /// Returns the combined [VersionConstraint] that all dependers place on the | 464 /// Returns the combined [VersionConstraint] that all dependers place on the |
466 /// package. | 465 /// package. |
467 VersionConstraint _addConstraint(PackageRef ref, String depender) { | 466 VersionConstraint _addConstraint(PackageDep dep, String depender) { |
468 // Add the dependency. | 467 // Add the dependency. |
469 var dependencies = _getDependencies(ref.name); | 468 var dependencies = _getDependencies(dep.name); |
470 dependencies.add(new Dependency(depender, ref)); | 469 dependencies.add(new Dependency(depender, dep)); |
471 | 470 |
472 // Determine the overall version constraint. | 471 // Determine the overall version constraint. |
473 var constraint = dependencies | 472 var constraint = dependencies |
474 .map((dep) => dep.ref.constraint) | 473 .map((dep) => dep.dep.constraint) |
475 .fold(VersionConstraint.any, (a, b) => a.intersect(b)); | 474 .fold(VersionConstraint.any, (a, b) => a.intersect(b)); |
476 | 475 |
477 // See if it's possible for a package to match that constraint. | 476 // See if it's possible for a package to match that constraint. |
478 if (constraint.isEmpty) { | 477 if (constraint.isEmpty) { |
479 _solver.logSolve('disjoint constraints on ${ref.name}'); | 478 _solver.logSolve('disjoint constraints on ${dep.name}'); |
480 throw new DisjointConstraintException(ref.name, dependencies); | 479 throw new DisjointConstraintException(dep.name, dependencies); |
481 } | 480 } |
482 | 481 |
483 return constraint; | 482 return constraint; |
484 } | 483 } |
485 | 484 |
486 /// Validates the currently selected package against the new dependency that | 485 /// Validates the currently selected package against the new dependency that |
487 /// [ref] and [constraint] place on it. Returns `null` if there is no | 486 /// [dep] and [constraint] place on it. Returns `null` if there is no |
488 /// currently selected package, throws a [SolverFailure] if the new reference | 487 /// currently selected package, throws a [SolverFailure] if the new reference |
489 /// it not does not allow the previously selected version, or returns the | 488 /// it not does not allow the previously selected version, or returns the |
490 /// selected package if successful. | 489 /// selected package if successful. |
491 PackageId _validateSelected(PackageRef ref, VersionConstraint constraint) { | 490 PackageId _validateSelected(PackageDep dep, VersionConstraint constraint) { |
492 var selected = _solver.getSelected(ref.name); | 491 var selected = _solver.getSelected(dep.name); |
493 if (selected == null) return null; | 492 if (selected == null) return null; |
494 | 493 |
495 // Make sure it meets the constraint. | 494 // Make sure it meets the constraint. |
496 if (!ref.constraint.allows(selected.version)) { | 495 if (!dep.constraint.allows(selected.version)) { |
497 _solver.logSolve('selection $selected does not match $constraint'); | 496 _solver.logSolve('selection $selected does not match $constraint'); |
498 throw new NoVersionException(ref.name, constraint, | 497 throw new NoVersionException(dep.name, constraint, |
499 _getDependencies(ref.name)); | 498 _getDependencies(dep.name)); |
500 } | 499 } |
501 | 500 |
502 return selected; | 501 return selected; |
503 } | 502 } |
504 | 503 |
505 /// Tries to select a package that matches [ref] and [constraint]. Updates | 504 /// Tries to select a package that matches [dep] and [constraint]. Updates |
506 /// the solver state so that we can backtrack from this decision if it turns | 505 /// the solver state so that we can backtrack from this decision if it turns |
507 /// out wrong, but continues traversing with the new selection. | 506 /// out wrong, but continues traversing with the new selection. |
508 /// | 507 /// |
509 /// Returns a future that completes with a [SolverFailure] if a version | 508 /// Returns a future that completes with a [SolverFailure] if a version |
510 /// could not be selected or that completes successfully if a package was | 509 /// could not be selected or that completes successfully if a package was |
511 /// selected and traversing should continue. | 510 /// selected and traversing should continue. |
512 Future _selectPackage(PackageRef ref, VersionConstraint constraint) { | 511 Future _selectPackage(PackageDep dep, VersionConstraint constraint) { |
513 return _solver.cache.getVersions(ref.name, ref.source, ref.description) | 512 return _solver.cache.getVersions(dep.toRef()).then((versions) { |
514 .then((versions) { | |
515 var allowed = versions.where((id) => constraint.allows(id.version)); | 513 var allowed = versions.where((id) => constraint.allows(id.version)); |
516 | 514 |
517 // See if it's in the lockfile. If so, try that version first. If the | 515 // See if it's in the lockfile. If so, try that version first. If the |
518 // locked version doesn't match our constraint, just ignore it. | 516 // locked version doesn't match our constraint, just ignore it. |
519 var locked = _getValidLocked(ref.name, constraint); | 517 var locked = _getValidLocked(dep.name, constraint); |
520 if (locked != null) { | 518 if (locked != null) { |
521 allowed = allowed.where((ref) => ref.version != locked.version) | 519 allowed = allowed.where((dep) => dep.version != locked.version) |
522 .toList(); | 520 .toList(); |
523 allowed.insert(0, locked); | 521 allowed.insert(0, locked); |
524 } | 522 } |
525 | 523 |
526 if (allowed.isEmpty) { | 524 if (allowed.isEmpty) { |
527 _solver.logSolve('no versions for ${ref.name} match $constraint'); | 525 _solver.logSolve('no versions for ${dep.name} match $constraint'); |
528 throw new NoVersionException(ref.name, constraint, | 526 throw new NoVersionException(dep.name, constraint, |
529 _getDependencies(ref.name)); | 527 _getDependencies(dep.name)); |
530 } | 528 } |
531 | 529 |
532 // If we're doing an upgrade on this package, only allow the latest | 530 // If we're doing an upgrade on this package, only allow the latest |
533 // version. | 531 // version. |
534 if (_solver._forceLatest.contains(ref.name)) allowed = [allowed.first]; | 532 if (_solver._forceLatest.contains(dep.name)) allowed = [allowed.first]; |
535 | 533 |
536 // Try the first package in the allowed set and keep track of the list of | 534 // Try the first package in the allowed set and keep track of the list of |
537 // other possible versions in case that fails. | 535 // other possible versions in case that fails. |
538 _packages.add(_solver.select(allowed)); | 536 _packages.add(_solver.select(allowed)); |
539 }); | 537 }); |
540 } | 538 } |
541 | 539 |
542 /// Gets the list of dependencies for package [name]. Will create an empty | 540 /// Gets the list of dependencies for package [name]. Will create an empty |
543 /// list if needed. | 541 /// list if needed. |
544 List<Dependency> _getDependencies(String name) { | 542 List<Dependency> _getDependencies(String name) { |
nweiz
2013/04/25 21:07:19
We're always passing `dep.name` here. Maybe this s
Bob Nystrom
2013/04/26 22:17:49
_getRequired() calls it with just a string.
| |
545 return _dependencies.putIfAbsent(name, () => <Dependency>[]); | 543 return _dependencies.putIfAbsent(name, () => <Dependency>[]); |
546 } | 544 } |
547 | 545 |
548 /// Gets a "required" reference to the package [name]. This is the first | 546 /// Gets a "required" reference to the package [name]. This is the first |
549 /// non-root dependency on that package. All dependencies on a package must | 547 /// non-root dependency on that package. All dependencies on a package must |
550 /// agree on source and description, except for references to the root | 548 /// agree on source and description, except for references to the root |
551 /// package. This will return a reference to that "canonical" source and | 549 /// package. This will return a reference to that "canonical" source and |
552 /// description, or `null` if there is no required reference yet. | 550 /// description, or `null` if there is no required reference yet. |
553 /// | 551 /// |
554 /// This is required because you may have a circular dependency back onto the | 552 /// This is required because you may have a circular dependency back onto the |
555 /// root package. That second dependency won't be a root dependency and it's | 553 /// root package. That second dependency won't be a root dependency and it's |
556 /// *that* one that other dependencies need to agree on. In other words, you | 554 /// *that* one that other dependencies need to agree on. In other words, you |
557 /// can have a bunch of dependencies back onto the root package as long as | 555 /// can have a bunch of dependencies back onto the root package as long as |
558 /// they all agree with each other. | 556 /// they all agree with each other. |
559 Dependency _getRequired(String name) { | 557 Dependency _getRequired(String name) { |
560 return _getDependencies(name) | 558 return _getDependencies(name) |
561 .firstWhere((dep) => !dep.ref.isRoot, orElse: () => null); | 559 .firstWhere((dep) => !dep.dep.isRoot, orElse: () => null); |
562 } | 560 } |
563 | 561 |
564 /// Gets the package [name] that's currently contained in the lockfile if it | 562 /// Gets the package [name] that's currently contained in the lockfile if it |
565 /// meets [constraint] and has the same source and description as other | 563 /// meets [constraint] and has the same source and description as other |
566 /// references to that package. Returns `null` otherwise. | 564 /// references to that package. Returns `null` otherwise. |
567 PackageId _getValidLocked(String name, VersionConstraint constraint) { | 565 PackageId _getValidLocked(String name, VersionConstraint constraint) { |
568 var package = _solver.getLocked(name); | 566 var package = _solver.getLocked(name); |
569 if (package == null) return null; | 567 if (package == null) return null; |
570 | 568 |
571 if (!constraint.allows(package.version)) { | 569 if (!constraint.allows(package.version)) { |
572 _solver.logSolve('$package is locked but does not match $constraint'); | 570 _solver.logSolve('$package is locked but does not match $constraint'); |
573 return null; | 571 return null; |
574 } else { | 572 } else { |
575 _solver.logSolve('$package is locked'); | 573 _solver.logSolve('$package is locked'); |
576 } | 574 } |
577 | 575 |
578 var required = _getRequired(name); | 576 var required = _getRequired(name); |
579 if (required != null) { | 577 if (required != null) { |
580 if (package.source.name != required.ref.source.name) return null; | 578 if (package.source.name != required.dep.source.name) return null; |
581 if (!package.descriptionEquals(required.ref)) return null; | 579 if (!package.descriptionEquals(required.dep)) return null; |
582 } | 580 } |
583 | 581 |
584 return package; | 582 return package; |
585 } | 583 } |
586 } | 584 } |
587 | 585 |
588 /// Ensures that if [pubspec] has an SDK constraint, then it is compatible | 586 /// Ensures that if [pubspec] has an SDK constraint, then it is compatible |
589 /// with the current SDK. Throws a [SolverFailure] if not. | 587 /// with the current SDK. Throws a [SolverFailure] if not. |
590 void _validateSdkConstraint(Pubspec pubspec) { | 588 void _validateSdkConstraint(Pubspec pubspec) { |
591 // If the user is running a continouous build of the SDK, just disable SDK | 589 // If the user is running a continouous build of the SDK, just disable SDK |
592 // constraint checking entirely. The actual version number you get is | 590 // constraint checking entirely. The actual version number you get is |
593 // impossibly old and not correct. We'll just assume users on continuous | 591 // impossibly old and not correct. We'll just assume users on continuous |
594 // know what they're doing. | 592 // know what they're doing. |
595 if (sdk.isBleedingEdge) return; | 593 if (sdk.isBleedingEdge) return; |
596 | 594 |
597 if (pubspec.environment.sdkVersion.allows(sdk.version)) return; | 595 if (pubspec.environment.sdkVersion.allows(sdk.version)) return; |
598 | 596 |
599 throw new CouldNotSolveException( | 597 throw new CouldNotSolveException( |
600 'Package ${pubspec.name} requires SDK version ' | 598 'Package ${pubspec.name} requires SDK version ' |
601 '${pubspec.environment.sdkVersion} but the current SDK is ' | 599 '${pubspec.environment.sdkVersion} but the current SDK is ' |
602 '${sdk.version}.'); | 600 '${sdk.version}.'); |
603 } | 601 } |
OLD | NEW |