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

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: 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
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 = (() {
128 var dependencies = [];
129 barback.pubConstraints.forEach((name, constraint) {
130 dependencies.add(
131 systemCache.sources.hosted.refFor(name).withConstraint(constrain t));
Bob Nystrom 2016/06/14 23:21:55 Long line.
nweiz 2016/06/20 20:46:08 Done.
132 });
133
134 return new Pubspec("pub itself", dependencies: dependencies);
135 })() {
Bob Nystrom 2016/06/14 23:21:55 Stuffing a giant immediately invoked function in h
nweiz 2016/06/20 20:46:08 Made it a static method instead. I really hate us
135 _selection = new VersionSelection(this); 136 _selection = new VersionSelection(this);
136 137
137 for (var package in useLatest) { 138 for (var package in useLatest) {
138 _forceLatest.add(package); 139 _forceLatest.add(package);
139 } 140 }
140 141
141 for (var override in root.dependencyOverrides) { 142 for (var override in root.dependencyOverrides) {
142 _overrides[override.name] = override; 143 _overrides[override.name] = override;
143 } 144 }
144 } 145 }
(...skipping 21 matching lines...) Expand all
166 _validateSdkConstraint(root.pubspec); 167 _validateSdkConstraint(root.pubspec);
167 168
168 logSolve(); 169 logSolve();
169 var packages = await _solve(); 170 var packages = await _solve();
170 171
171 var pubspecs = {}; 172 var pubspecs = {};
172 for (var id in packages) { 173 for (var id in packages) {
173 pubspecs[id.name] = await _getPubspec(id); 174 pubspecs[id.name] = await _getPubspec(id);
174 } 175 }
175 176
176 return new SolveResult.success(sources, root, lockFile, packages, 177 return new SolveResult.success(systemCache.sources, root, lockFile,
177 overrides, pubspecs, _getAvailableVersions(packages), 178 packages, overrides, pubspecs, _getAvailableVersions(packages),
178 _attemptedSolutions); 179 _attemptedSolutions);
179 } on SolveFailure catch (error) { 180 } on SolveFailure catch (error) {
180 // Wrap a failure in a result so we can attach some other data. 181 // Wrap a failure in a result so we can attach some other data.
181 return new SolveResult.failure(sources, root, lockFile, overrides, 182 return new SolveResult.failure(systemCache.sources, root, lockFile,
182 error, _attemptedSolutions); 183 overrides, error, _attemptedSolutions);
183 } finally { 184 } finally {
184 // Gather some solving metrics. 185 // Gather some solving metrics.
185 var buffer = new StringBuffer(); 186 var buffer = new StringBuffer();
186 buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.'); 187 buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.');
187 buffer.writeln(cache.describeResults()); 188 buffer.writeln(cache.describeResults());
188 log.solver(buffer); 189 log.solver(buffer);
189 } 190 }
190 } 191 }
191 192
192 /// Generates a map containing all of the known available versions for each 193 /// Generates a map containing all of the known available versions for each
(...skipping 26 matching lines...) Expand all
219 /// 220 ///
220 /// Returns `null` if it isn't in the lockfile (or has been unlocked). 221 /// Returns `null` if it isn't in the lockfile (or has been unlocked).
221 PackageId getLocked(String package) { 222 PackageId getLocked(String package) {
222 if (type == SolveType.GET) return lockFile.packages[package]; 223 if (type == SolveType.GET) return lockFile.packages[package];
223 224
224 // When downgrading, we don't want to force the latest versions of 225 // 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 226 // non-hosted packages, since they don't support multiple versions and thus
226 // can't be downgraded. 227 // can't be downgraded.
227 if (type == SolveType.DOWNGRADE) { 228 if (type == SolveType.DOWNGRADE) {
228 var locked = lockFile.packages[package]; 229 var locked = lockFile.packages[package];
229 if (locked != null && !sources[locked.source].hasMultipleVersions) { 230 if (locked != null &&
231 !systemCache.sources[locked.source].hasMultipleVersions) {
230 return locked; 232 return locked;
231 } 233 }
232 } 234 }
233 235
234 if (_forceLatest.isEmpty || _forceLatest.contains(package)) return null; 236 if (_forceLatest.isEmpty || _forceLatest.contains(package)) return null;
235 return lockFile.packages[package]; 237 return lockFile.packages[package];
236 } 238 }
237 239
238 /// Gets the package [name] that's currently contained in the lockfile if it 240 /// 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 241 /// matches the current constraint and has the same source and description as
240 /// other references to that package. 242 /// other references to that package.
241 /// 243 ///
242 /// Returns `null` otherwise. 244 /// Returns `null` otherwise.
243 PackageId _getValidLocked(String name) { 245 PackageId _getValidLocked(String name) {
244 var package = getLocked(name); 246 var package = getLocked(name);
245 if (package == null) return null; 247 if (package == null) return null;
246 248
247 var constraint = _selection.getConstraint(name); 249 var constraint = _selection.getConstraint(name);
248 if (!constraint.allows(package.version)) { 250 if (!constraint.allows(package.version)) {
249 logSolve('$package is locked but does not match $constraint'); 251 logSolve('$package is locked but does not match $constraint');
250 return null; 252 return null;
251 } else { 253 } else {
252 logSolve('$package is locked'); 254 logSolve('$package is locked');
253 } 255 }
254 256
255 var required = _selection.getRequiredDependency(name); 257 var required = _selection.getRequiredDependency(name);
256 if (required != null) { 258 if (required != null) {
257 if (package.source != required.dep.source) return null; 259 if (package.source != required.dep.source) return null;
258 260
259 var source = sources[package.source]; 261 var source = systemCache.sources[package.source];
260 if (!source.descriptionsEqual( 262 if (!source.descriptionsEqual(
261 package.description, required.dep.description)) return null; 263 package.description, required.dep.description)) return null;
262 } 264 }
263 265
264 return package; 266 return package;
265 } 267 }
266 268
267 /// Tries to find the best set of versions that meet the constraints. 269 /// Tries to find the best set of versions that meet the constraints.
268 /// 270 ///
269 /// Selects matching versions of unselected packages, or backtracks if there 271 /// 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); 525 _fail(otherDep.depender.name);
524 } 526 }
525 527
526 logSolve( 528 logSolve(
527 'inconsistent source "${dep.source}" for ${dep.name}:\n' 529 'inconsistent source "${dep.source}" for ${dep.name}:\n'
528 ' $dependency\n' + 530 ' $dependency\n' +
529 _selection.describeDependencies(dep.name)); 531 _selection.describeDependencies(dep.name));
530 throw new SourceMismatchException(dep.name, allDeps); 532 throw new SourceMismatchException(dep.name, allDeps);
531 } 533 }
532 534
533 var source = sources[dep.source]; 535 var source = systemCache.sources[dep.source];
534 if (!source.descriptionsEqual( 536 if (!source.descriptionsEqual(
535 dep.description, required.dep.description)) { 537 dep.description, required.dep.description)) {
536 // Mark the dependers as failing rather than the package itself, because 538 // Mark the dependers as failing rather than the package itself, because
537 // no version with this description will be compatible. 539 // no version with this description will be compatible.
538 for (var otherDep in _selection.getDependenciesOn(dep.name)) { 540 for (var otherDep in _selection.getDependenciesOn(dep.name)) {
539 _fail(otherDep.depender.name); 541 _fail(otherDep.depender.name);
540 } 542 }
541 543
542 logSolve( 544 logSolve(
543 'inconsistent description "${dep.description}" for ${dep.name}:\n' 545 'inconsistent description "${dep.description}" for ${dep.name}:\n'
(...skipping 38 matching lines...) Expand 10 before | Expand all | Expand 10 after
582 // Not overridden. 584 // Not overridden.
583 return dep; 585 return dep;
584 }).toSet(); 586 }).toSet();
585 } else { 587 } else {
586 // Ignore any overridden dependencies. 588 // Ignore any overridden dependencies.
587 deps.removeWhere((dep) => _overrides.containsKey(dep.name)); 589 deps.removeWhere((dep) => _overrides.containsKey(dep.name));
588 } 590 }
589 591
590 // Make sure the package doesn't have any bad dependencies. 592 // Make sure the package doesn't have any bad dependencies.
591 for (var dep in deps.toSet()) { 593 for (var dep in deps.toSet()) {
592 if (!dep.isRoot && sources[dep.source] is UnknownSource) { 594 if (!dep.isRoot && systemCache.sources[dep.source] is UnknownSource) {
593 throw new UnknownSourceException(id.name, [new Dependency(id, dep)]); 595 throw new UnknownSourceException(id.name, [new Dependency(id, dep)]);
594 } 596 }
595 597
596 if (dep.name == 'barback') { 598 if (dep.name == 'barback') {
597 deps.add(new PackageDep.magic('pub itself')); 599 deps.add(new PackageDep.magic('pub itself'));
598 } 600 }
599 } 601 }
600 602
601 return deps; 603 return deps;
602 } 604 }
603 605
604 /// Loads and returns the pubspec for [id]. 606 /// Loads and returns the pubspec for [id].
605 Future<Pubspec> _getPubspec(PackageId id) async { 607 Future<Pubspec> _getPubspec(PackageId id) async {
606 if (id.isRoot) return root.pubspec; 608 if (id.isRoot) return root.pubspec;
607 if (id.isMagic && id.name == 'pub itself') return _implicitPubspec; 609 if (id.isMagic && id.name == 'pub itself') return _implicitPubspec;
608 610 return await systemCache.liveSource(id.source).describe(id);
609 var source = sources[id.source];
610 return await source.describe(id);
611 } 611 }
612 612
613 /// Logs the initial parameters to the solver. 613 /// Logs the initial parameters to the solver.
614 void _logParameters() { 614 void _logParameters() {
615 var buffer = new StringBuffer(); 615 var buffer = new StringBuffer();
616 buffer.writeln("Solving dependencies:"); 616 buffer.writeln("Solving dependencies:");
617 for (var package in root.dependencies) { 617 for (var package in root.dependencies) {
618 buffer.write("- $package"); 618 buffer.write("- $package");
619 var locked = getLocked(package.name); 619 var locked = getLocked(package.name);
620 if (_forceLatest.contains(package.name)) { 620 if (_forceLatest.contains(package.name)) {
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after
654 void _validateSdkConstraint(Pubspec pubspec) { 654 void _validateSdkConstraint(Pubspec pubspec) {
655 if (_overrides.containsKey(pubspec.name)) return; 655 if (_overrides.containsKey(pubspec.name)) return;
656 if (pubspec.environment.sdkVersion.allows(sdk.version)) return; 656 if (pubspec.environment.sdkVersion.allows(sdk.version)) return;
657 657
658 throw new BadSdkVersionException(pubspec.name, 658 throw new BadSdkVersionException(pubspec.name,
659 'Package ${pubspec.name} requires SDK version ' 659 'Package ${pubspec.name} requires SDK version '
660 '${pubspec.environment.sdkVersion} but the current SDK is ' 660 '${pubspec.environment.sdkVersion} but the current SDK is '
661 '${sdk.version}.'); 661 '${sdk.version}.');
662 } 662 }
663 } 663 }
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698