Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(246)

Side by Side Diff: lib/src/solver/backtracking_solver.dart

Issue 2044253003: Refactor Source and SourceRegistry. (Closed) Base URL: git@github.com:dart-lang/pub.git@master
Patch Set: Rename LiveSource to BoundSource. Created 4 years, 6 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
« no previous file with comments | « lib/src/package_graph.dart ('k') | lib/src/solver/version_solver.dart » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
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 26 matching lines...) Expand all
37 37
38 import 'package:pub_semver/pub_semver.dart'; 38 import 'package:pub_semver/pub_semver.dart';
39 39
40 import '../barback.dart' as barback; 40 import '../barback.dart' as barback;
41 import '../exceptions.dart'; 41 import '../exceptions.dart';
42 import '../lock_file.dart'; 42 import '../lock_file.dart';
43 import '../log.dart' as log; 43 import '../log.dart' as log;
44 import '../package.dart'; 44 import '../package.dart';
45 import '../pubspec.dart'; 45 import '../pubspec.dart';
46 import '../sdk.dart' as sdk; 46 import '../sdk.dart' as sdk;
47 import '../source_registry.dart';
48 import '../source/hosted.dart';
49 import '../source/unknown.dart'; 47 import '../source/unknown.dart';
48 import '../system_cache.dart';
50 import '../utils.dart'; 49 import '../utils.dart';
51 import 'version_queue.dart'; 50 import 'version_queue.dart';
52 import 'version_selection.dart'; 51 import 'version_selection.dart';
53 import 'version_solver.dart'; 52 import 'version_solver.dart';
54 53
55 /// The top-level solver. 54 /// The top-level solver.
56 /// 55 ///
57 /// Keeps track of the current potential solution, and the other possible 56 /// Keeps track of the current potential solution, and the other possible
58 /// versions for speculative package selections. Backtracks and advances to the 57 /// versions for speculative package selections. Backtracks and advances to the
59 /// next potential solution in the case of a failure. 58 /// next potential solution in the case of a failure.
60 class BacktrackingSolver { 59 class BacktrackingSolver {
61 final SolveType type; 60 final SolveType type;
62 final SourceRegistry sources; 61 final SystemCache systemCache;
63 final Package root; 62 final Package root;
64 63
65 /// The lockfile that was present before solving. 64 /// The lockfile that was present before solving.
66 final LockFile lockFile; 65 final LockFile lockFile;
67 66
68 /// A cache of data requested during solving. 67 /// A cache of data requested during solving.
69 final SolverCache cache; 68 final SolverCache cache;
70 69
71 /// The set of packages that are being explicitly upgraded. 70 /// The set of packages that are being explicitly upgraded.
72 /// 71 ///
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after
111 /// package, since it has only one valid version, but [_selection] does, since 110 /// package, since it has only one valid version, but [_selection] does, since
112 /// its dependencies are relevant. Second, when backtracking, [_versions] 111 /// its dependencies are relevant. Second, when backtracking, [_versions]
113 /// contains the version that's being backtracked, while [_selection] does 112 /// contains the version that's being backtracked, while [_selection] does
114 /// not. 113 /// not.
115 VersionSelection _selection; 114 VersionSelection _selection;
116 115
117 /// The number of solutions the solver has tried so far. 116 /// The number of solutions the solver has tried so far.
118 var _attemptedSolutions = 1; 117 var _attemptedSolutions = 1;
119 118
120 /// A pubspec for pub's implicit dependencies on barback and related packages. 119 /// A pubspec for pub's implicit dependencies on barback and related packages.
121 final Pubspec _implicitPubspec = () { 120 final Pubspec _implicitPubspec;
122 var dependencies = [];
123 barback.pubConstraints.forEach((name, constraint) {
124 dependencies.add(HostedSource.refFor(name).withConstraint(constraint));
125 });
126 121
127 return new Pubspec("pub itself", dependencies: dependencies); 122 BacktrackingSolver(SolveType type, SystemCache systemCache, this.root,
128 }();
129
130 BacktrackingSolver(SolveType type, SourceRegistry sources, this.root,
131 this.lockFile, List<String> useLatest) 123 this.lockFile, List<String> useLatest)
132 : type = type, 124 : type = type,
133 sources = sources, 125 systemCache = systemCache,
134 cache = new SolverCache(type, sources) { 126 cache = new SolverCache(type, systemCache),
127 _implicitPubspec = _makeImplicitPubspec(systemCache) {
135 _selection = new VersionSelection(this); 128 _selection = new VersionSelection(this);
136 129
137 for (var package in useLatest) { 130 for (var package in useLatest) {
138 _forceLatest.add(package); 131 _forceLatest.add(package);
139 } 132 }
140 133
141 for (var override in root.dependencyOverrides) { 134 for (var override in root.dependencyOverrides) {
142 _overrides[override.name] = override; 135 _overrides[override.name] = override;
143 } 136 }
144 } 137 }
145 138
139 /// Creates [_implicitPubspec].
140 static Pubspec _makeImplicitPubspec(SystemCache systemCache) {
141 var dependencies = [];
142 barback.pubConstraints.forEach((name, constraint) {
143 dependencies.add(
144 systemCache.sources.hosted.refFor(name)
145 .withConstraint(constraint));
146 });
147
148 return new Pubspec("pub itself", dependencies: dependencies);
149 }
150
146 /// Run the solver. 151 /// Run the solver.
147 /// 152 ///
148 /// Completes with a list of specific package versions if successful or an 153 /// Completes with a list of specific package versions if successful or an
149 /// error if it failed to find a solution. 154 /// error if it failed to find a solution.
150 Future<SolveResult> solve() async { 155 Future<SolveResult> solve() async {
151 var stopwatch = new Stopwatch(); 156 var stopwatch = new Stopwatch();
152 157
153 _logParameters(); 158 _logParameters();
154 159
155 // Sort the overrides by package name to make sure they're deterministic. 160 // Sort the overrides by package name to make sure they're deterministic.
(...skipping 10 matching lines...) Expand all
166 _validateSdkConstraint(root.pubspec); 171 _validateSdkConstraint(root.pubspec);
167 172
168 logSolve(); 173 logSolve();
169 var packages = await _solve(); 174 var packages = await _solve();
170 175
171 var pubspecs = {}; 176 var pubspecs = {};
172 for (var id in packages) { 177 for (var id in packages) {
173 pubspecs[id.name] = await _getPubspec(id); 178 pubspecs[id.name] = await _getPubspec(id);
174 } 179 }
175 180
176 return new SolveResult.success(sources, root, lockFile, packages, 181 return new SolveResult.success(systemCache.sources, root, lockFile,
177 overrides, pubspecs, _getAvailableVersions(packages), 182 packages, overrides, pubspecs, _getAvailableVersions(packages),
178 _attemptedSolutions); 183 _attemptedSolutions);
179 } on SolveFailure catch (error) { 184 } on SolveFailure catch (error) {
180 // Wrap a failure in a result so we can attach some other data. 185 // Wrap a failure in a result so we can attach some other data.
181 return new SolveResult.failure(sources, root, lockFile, overrides, 186 return new SolveResult.failure(systemCache.sources, root, lockFile,
182 error, _attemptedSolutions); 187 overrides, error, _attemptedSolutions);
183 } finally { 188 } finally {
184 // Gather some solving metrics. 189 // Gather some solving metrics.
185 var buffer = new StringBuffer(); 190 var buffer = new StringBuffer();
186 buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.'); 191 buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.');
187 buffer.writeln(cache.describeResults()); 192 buffer.writeln(cache.describeResults());
188 log.solver(buffer); 193 log.solver(buffer);
189 } 194 }
190 } 195 }
191 196
192 /// Generates a map containing all of the known available versions for each 197 /// Generates a map containing all of the known available versions for each
(...skipping 26 matching lines...) Expand all
219 /// 224 ///
220 /// Returns `null` if it isn't in the lockfile (or has been unlocked). 225 /// Returns `null` if it isn't in the lockfile (or has been unlocked).
221 PackageId getLocked(String package) { 226 PackageId getLocked(String package) {
222 if (type == SolveType.GET) return lockFile.packages[package]; 227 if (type == SolveType.GET) return lockFile.packages[package];
223 228
224 // When downgrading, we don't want to force the latest versions of 229 // When downgrading, we don't want to force the latest versions of
225 // non-hosted packages, since they don't support multiple versions and thus 230 // non-hosted packages, since they don't support multiple versions and thus
226 // can't be downgraded. 231 // can't be downgraded.
227 if (type == SolveType.DOWNGRADE) { 232 if (type == SolveType.DOWNGRADE) {
228 var locked = lockFile.packages[package]; 233 var locked = lockFile.packages[package];
229 if (locked != null && !sources[locked.source].hasMultipleVersions) { 234 if (locked != null &&
235 !systemCache.sources[locked.source].hasMultipleVersions) {
230 return locked; 236 return locked;
231 } 237 }
232 } 238 }
233 239
234 if (_forceLatest.isEmpty || _forceLatest.contains(package)) return null; 240 if (_forceLatest.isEmpty || _forceLatest.contains(package)) return null;
235 return lockFile.packages[package]; 241 return lockFile.packages[package];
236 } 242 }
237 243
238 /// Gets the package [name] that's currently contained in the lockfile if it 244 /// Gets the package [name] that's currently contained in the lockfile if it
239 /// matches the current constraint and has the same source and description as 245 /// matches the current constraint and has the same source and description as
240 /// other references to that package. 246 /// other references to that package.
241 /// 247 ///
242 /// Returns `null` otherwise. 248 /// Returns `null` otherwise.
243 PackageId _getValidLocked(String name) { 249 PackageId _getValidLocked(String name) {
244 var package = getLocked(name); 250 var package = getLocked(name);
245 if (package == null) return null; 251 if (package == null) return null;
246 252
247 var constraint = _selection.getConstraint(name); 253 var constraint = _selection.getConstraint(name);
248 if (!constraint.allows(package.version)) { 254 if (!constraint.allows(package.version)) {
249 logSolve('$package is locked but does not match $constraint'); 255 logSolve('$package is locked but does not match $constraint');
250 return null; 256 return null;
251 } else { 257 } else {
252 logSolve('$package is locked'); 258 logSolve('$package is locked');
253 } 259 }
254 260
255 var required = _selection.getRequiredDependency(name); 261 var required = _selection.getRequiredDependency(name);
256 if (required != null) { 262 if (required != null) {
257 if (package.source != required.dep.source) return null; 263 if (package.source != required.dep.source) return null;
258 264
259 var source = sources[package.source]; 265 var source = systemCache.sources[package.source];
260 if (!source.descriptionsEqual( 266 if (!source.descriptionsEqual(
261 package.description, required.dep.description)) return null; 267 package.description, required.dep.description)) return null;
262 } 268 }
263 269
264 return package; 270 return package;
265 } 271 }
266 272
267 /// Tries to find the best set of versions that meet the constraints. 273 /// Tries to find the best set of versions that meet the constraints.
268 /// 274 ///
269 /// Selects matching versions of unselected packages, or backtracks if there 275 /// Selects matching versions of unselected packages, or backtracks if there
(...skipping 253 matching lines...) Expand 10 before | Expand all | Expand 10 after
523 _fail(otherDep.depender.name); 529 _fail(otherDep.depender.name);
524 } 530 }
525 531
526 logSolve( 532 logSolve(
527 'inconsistent source "${dep.source}" for ${dep.name}:\n' 533 'inconsistent source "${dep.source}" for ${dep.name}:\n'
528 ' $dependency\n' + 534 ' $dependency\n' +
529 _selection.describeDependencies(dep.name)); 535 _selection.describeDependencies(dep.name));
530 throw new SourceMismatchException(dep.name, allDeps); 536 throw new SourceMismatchException(dep.name, allDeps);
531 } 537 }
532 538
533 var source = sources[dep.source]; 539 var source = systemCache.sources[dep.source];
534 if (!source.descriptionsEqual( 540 if (!source.descriptionsEqual(
535 dep.description, required.dep.description)) { 541 dep.description, required.dep.description)) {
536 // Mark the dependers as failing rather than the package itself, because 542 // Mark the dependers as failing rather than the package itself, because
537 // no version with this description will be compatible. 543 // no version with this description will be compatible.
538 for (var otherDep in _selection.getDependenciesOn(dep.name)) { 544 for (var otherDep in _selection.getDependenciesOn(dep.name)) {
539 _fail(otherDep.depender.name); 545 _fail(otherDep.depender.name);
540 } 546 }
541 547
542 logSolve( 548 logSolve(
543 'inconsistent description "${dep.description}" for ${dep.name}:\n' 549 'inconsistent description "${dep.description}" for ${dep.name}:\n'
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after
582 // Not overridden. 588 // Not overridden.
583 return dep; 589 return dep;
584 }).toSet(); 590 }).toSet();
585 } else { 591 } else {
586 // Ignore any overridden dependencies. 592 // Ignore any overridden dependencies.
587 deps.removeWhere((dep) => _overrides.containsKey(dep.name)); 593 deps.removeWhere((dep) => _overrides.containsKey(dep.name));
588 } 594 }
589 595
590 // Make sure the package doesn't have any bad dependencies. 596 // Make sure the package doesn't have any bad dependencies.
591 for (var dep in deps.toSet()) { 597 for (var dep in deps.toSet()) {
592 if (!dep.isRoot && sources[dep.source] is UnknownSource) { 598 if (!dep.isRoot && systemCache.sources[dep.source] is UnknownSource) {
593 throw new UnknownSourceException(id.name, [new Dependency(id, dep)]); 599 throw new UnknownSourceException(id.name, [new Dependency(id, dep)]);
594 } 600 }
595 601
596 if (dep.name == 'barback') { 602 if (dep.name == 'barback') {
597 deps.add(new PackageDep.magic('pub itself')); 603 deps.add(new PackageDep.magic('pub itself'));
598 } 604 }
599 } 605 }
600 606
601 return deps; 607 return deps;
602 } 608 }
603 609
604 /// Loads and returns the pubspec for [id]. 610 /// Loads and returns the pubspec for [id].
605 Future<Pubspec> _getPubspec(PackageId id) async { 611 Future<Pubspec> _getPubspec(PackageId id) async {
606 if (id.isRoot) return root.pubspec; 612 if (id.isRoot) return root.pubspec;
607 if (id.isMagic && id.name == 'pub itself') return _implicitPubspec; 613 if (id.isMagic && id.name == 'pub itself') return _implicitPubspec;
608 614 return await systemCache.source(id.source).describe(id);
609 var source = sources[id.source];
610 return await source.describe(id);
611 } 615 }
612 616
613 /// Logs the initial parameters to the solver. 617 /// Logs the initial parameters to the solver.
614 void _logParameters() { 618 void _logParameters() {
615 var buffer = new StringBuffer(); 619 var buffer = new StringBuffer();
616 buffer.writeln("Solving dependencies:"); 620 buffer.writeln("Solving dependencies:");
617 for (var package in root.dependencies) { 621 for (var package in root.dependencies) {
618 buffer.write("- $package"); 622 buffer.write("- $package");
619 var locked = getLocked(package.name); 623 var locked = getLocked(package.name);
620 if (_forceLatest.contains(package.name)) { 624 if (_forceLatest.contains(package.name)) {
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after
654 void _validateSdkConstraint(Pubspec pubspec) { 658 void _validateSdkConstraint(Pubspec pubspec) {
655 if (_overrides.containsKey(pubspec.name)) return; 659 if (_overrides.containsKey(pubspec.name)) return;
656 if (pubspec.environment.sdkVersion.allows(sdk.version)) return; 660 if (pubspec.environment.sdkVersion.allows(sdk.version)) return;
657 661
658 throw new BadSdkVersionException(pubspec.name, 662 throw new BadSdkVersionException(pubspec.name,
659 'Package ${pubspec.name} requires SDK version ' 663 'Package ${pubspec.name} requires SDK version '
660 '${pubspec.environment.sdkVersion} but the current SDK is ' 664 '${pubspec.environment.sdkVersion} but the current SDK is '
661 '${sdk.version}.'); 665 '${sdk.version}.');
662 } 666 }
663 } 667 }
OLDNEW
« no previous file with comments | « lib/src/package_graph.dart ('k') | lib/src/solver/version_solver.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698