| // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| library pub.solver.version_solver; |
| |
| import 'dart:async'; |
| import "dart:convert"; |
| |
| import '../lock_file.dart'; |
| import '../log.dart' as log; |
| import '../package.dart'; |
| import '../pubspec.dart'; |
| import '../source.dart'; |
| import '../source_registry.dart'; |
| import '../version.dart'; |
| import '../utils.dart'; |
| import 'backtracking_solver.dart'; |
| |
| /// Attempts to select the best concrete versions for all of the transitive |
| /// dependencies of [root] taking into account all of the [VersionConstraint]s |
| /// that those dependencies place on each other and the requirements imposed by |
| /// [lockFile]. |
| /// |
| /// If [useLatest] is given, then only the latest versions of the referenced |
| /// packages will be used. This is for forcing an update to one or more |
| /// packages. |
| Future<SolveResult> resolveVersions(SourceRegistry sources, Package root, |
| {LockFile lockFile, List<String> useLatest}) { |
| if (lockFile == null) lockFile = new LockFile.empty(); |
| if (useLatest == null) useLatest = []; |
| |
| return log.progress('Resolving dependencies', () { |
| return new BacktrackingSolver(sources, root, lockFile, useLatest).solve(); |
| }); |
| } |
| |
| /// The result of a version resolution. |
| class SolveResult { |
| /// Whether the solver found a complete solution or failed. |
| bool get succeeded => error == null; |
| |
| /// The list of concrete package versions that were selected for each package |
| /// reachable from the root, or `null` if the solver failed. |
| final List<PackageId> packages; |
| |
| /// The error that prevented the solver from finding a solution or `null` if |
| /// it was successful. |
| final SolveFailure error; |
| |
| /// The number of solutions that were attempted before either finding a |
| /// successful solution or exhausting all options. In other words, one more |
| /// than the number of times it had to backtrack because it found an invalid |
| /// solution. |
| final int attemptedSolutions; |
| |
| SolveResult(this.packages, this.error, this.attemptedSolutions); |
| |
| String toString() { |
| if (!succeeded) { |
| return 'Failed to solve after $attemptedSolutions attempts:\n' |
| '$error'; |
| } |
| |
| return 'Took $attemptedSolutions tries to resolve to\n' |
| '- ${packages.join("\n- ")}'; |
| } |
| } |
| |
| /// Maintains a cache of previously-requested data: pubspecs and version lists. |
| /// Used to avoid requesting the same pubspec from the server repeatedly. |
| class PubspecCache { |
| final SourceRegistry _sources; |
| |
| /// The already-requested cached version lists. |
| final _versions = new Map<PackageRef, List<PackageId>>(); |
| |
| /// The already-requested cached pubspecs. |
| final _pubspecs = new Map<PackageId, Pubspec>(); |
| |
| /// The number of times a version list was requested and it wasn't cached and |
| /// had to be requested from the source. |
| int versionCacheMisses = 0; |
| |
| /// The number of times a version list was requested and the cached version |
| /// was returned. |
| int versionCacheHits = 0; |
| |
| /// The number of times a pubspec was requested and it wasn't cached and had |
| /// to be requested from the source. |
| int pubspecCacheMisses = 0; |
| |
| /// The number of times a pubspec was requested and the cached version was |
| /// returned. |
| int pubspecCacheHits = 0; |
| |
| PubspecCache(this._sources); |
| |
| /// Caches [pubspec] as the [Pubspec] for the package identified by [id]. |
| void cache(PackageId id, Pubspec pubspec) { |
| _pubspecs[id] = pubspec; |
| } |
| |
| /// Loads the pubspec for the package identified by [id]. |
| Future<Pubspec> getPubspec(PackageId id) { |
| // Complete immediately if it's already cached. |
| if (_pubspecs.containsKey(id)) { |
| pubspecCacheHits++; |
| return new Future<Pubspec>.value(_pubspecs[id]); |
| } |
| |
| pubspecCacheMisses++; |
| |
| var source = _sources[id.source]; |
| return source.describe(id).then((pubspec) { |
| _pubspecs[id] = pubspec; |
| return pubspec; |
| }); |
| } |
| |
| /// Returns the previously cached pubspec for the package identified by [id] |
| /// or returns `null` if not in the cache. |
| Pubspec getCachedPubspec(PackageId id) => _pubspecs[id]; |
| |
| /// Gets the list of versions for [package] in descending order. |
| Future<List<PackageId>> getVersions(PackageRef package) { |
| if (package.isRoot) { |
| throw new StateError("Cannot get versions for root package $package."); |
| } |
| |
| // See if we have it cached. |
| var versions = _versions[package]; |
| if (versions != null) { |
| versionCacheHits++; |
| return new Future.value(versions); |
| } |
| |
| versionCacheMisses++; |
| |
| var source = _sources[package.source]; |
| return source.getVersions(package.name, package.description) |
| .then((versions) { |
| // Sort by descending version so we try newer versions first. |
| versions.sort((a, b) => b.compareTo(a)); |
| |
| var ids = versions.map((version) => package.atVersion(version)).toList(); |
| _versions[package] = ids; |
| return ids; |
| }); |
| } |
| } |
| |
| /// A reference from a depending package to a package that it depends on. |
| class Dependency { |
| /// The name of the package that has this dependency. |
| final String depender; |
| |
| /// The package being depended on. |
| final PackageDep dep; |
| |
| Dependency(this.depender, this.dep); |
| |
| String toString() => '$depender -> $dep'; |
| } |
| |
| /// Base class for all failures that can occur while trying to resolve versions. |
| abstract class SolveFailure implements ApplicationException { |
| /// The name of the package whose version could not be solved. Will be `null` |
| /// if the failure is not specific to one package. |
| final String package; |
| |
| /// The known dependencies on [package] at the time of the failure. Will be |
| /// an empty collection if the failure is not specific to one package. |
| final Iterable<Dependency> dependencies; |
| |
| SolveFailure(this.package, Iterable<Dependency> dependencies) |
| : dependencies = dependencies != null ? dependencies : <Dependency>[]; |
| |
| String toString() { |
| if (dependencies.isEmpty) return _message; |
| |
| var buffer = new StringBuffer(); |
| buffer.writeln("$_message:"); |
| |
| var map = {}; |
| for (var dep in dependencies) { |
| map[dep.depender] = dep.dep; |
| } |
| |
| var names = ordered(map.keys); |
| |
| buffer.writeAll(names.map( |
| (name) => "- '$name' ${_describeDependency(map[name])}"), '\n'); |
| |
| return buffer.toString(); |
| } |
| |
| String get message => toString(); |
| |
| /// A message describing the specific kind of solve failure. |
| String get _message { |
| throw new UnimplementedError("Must override _message or toString()."); |
| } |
| |
| /// Describes a dependencie's reference in the output message. Override this |
| /// to highlight which aspect of [dep] led to the failure. |
| String _describeDependency(PackageDep dep) => |
| "depends on version ${dep.constraint}"; |
| } |
| |
| /// Exception thrown when the current SDK's version does not match a package's |
| /// constraint on it. |
| class BadSdkVersionException extends SolveFailure { |
| BadSdkVersionException(String package, String message) |
| : super(package, null), |
| _message = message; |
| |
| /// A message describing the specific kind of solve failure. |
| final String _message; |
| } |
| |
| /// Exception thrown when the [VersionConstraint] used to match a package is |
| /// valid (i.e. non-empty), but there are no available versions of the package |
| /// that fit that constraint. |
| class NoVersionException extends SolveFailure { |
| final VersionConstraint constraint; |
| |
| NoVersionException(String package, this.constraint, |
| Iterable<Dependency> dependencies) |
| : super(package, dependencies); |
| |
| String get _message => "Package '$package' has no versions that match " |
| "$constraint derived from"; |
| } |
| |
| // TODO(rnystrom): Report the list of depending packages and their constraints. |
| /// Exception thrown when the most recent version of [package] must be selected, |
| /// but doesn't match the [VersionConstraint] imposed on the package. |
| class CouldNotUpdateException extends SolveFailure { |
| final VersionConstraint constraint; |
| final Version best; |
| |
| CouldNotUpdateException(String package, this.constraint, this.best) |
| : super(package, null); |
| |
| String get _message => |
| "The latest version of '$package', $best, does not match $constraint."; |
| } |
| |
| /// Exception thrown when the [VersionConstraint] used to match a package is |
| /// the empty set: in other words, multiple packages depend on it and have |
| /// conflicting constraints that have no overlap. |
| class DisjointConstraintException extends SolveFailure { |
| DisjointConstraintException(String package, Iterable<Dependency> dependencies) |
| : super(package, dependencies); |
| |
| String get _message => "Incompatible version constraints on '$package'"; |
| } |
| |
| /// Exception thrown when two packages with the same name but different sources |
| /// are depended upon. |
| class SourceMismatchException extends SolveFailure { |
| SourceMismatchException(String package, Iterable<Dependency> dependencies) |
| : super(package, dependencies); |
| |
| String get _message => "Incompatible dependencies on '$package'"; |
| |
| String _describeDependency(PackageDep dep) => |
| "depends on it from source ${dep.source}"; |
| } |
| |
| /// Exception thrown when a dependency on an unknown source name is found. |
| class UnknownSourceException extends SolveFailure { |
| UnknownSourceException(String package, Iterable<Dependency> dependencies) |
| : super(package, dependencies); |
| |
| String toString() { |
| var dep = only(dependencies); |
| return "Package '${dep.depender}' depends on '${dep.dep.name}' from " |
| "unknown source '${dep.dep.source}'."; |
| } |
| } |
| |
| /// Exception thrown when two packages with the same name and source but |
| /// different descriptions are depended upon. |
| class DescriptionMismatchException extends SolveFailure { |
| DescriptionMismatchException(String package, |
| Iterable<Dependency> dependencies) |
| : super(package, dependencies); |
| |
| String get _message => "Incompatible dependencies on '$package'"; |
| |
| String _describeDependency(PackageDep dep) { |
| // TODO(nweiz): Dump descriptions to YAML when that's supported. |
| return "depends on it with description ${JSON.encode(dep.description)}"; |
| } |
| } |