Chromium Code Reviews

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

Issue 1459733002: Move pubspec caching into each source. (Closed) Base URL: git@github.com:dart-lang/pub.git@master
Patch Set: Code review changes Created 5 years ago
Use n/p to move between diff chunks; N/P to move between comments.
Jump to:
View unified diff |
« no previous file with comments | « lib/src/command/cache_add.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 48 matching lines...)
59 /// versions for speculative package selections. Backtracks and advances to the 59 /// versions for speculative package selections. Backtracks and advances to the
60 /// next potential solution in the case of a failure. 60 /// next potential solution in the case of a failure.
61 class BacktrackingSolver { 61 class BacktrackingSolver {
62 final SolveType type; 62 final SolveType type;
63 final SourceRegistry sources; 63 final SourceRegistry sources;
64 final Package root; 64 final Package root;
65 65
66 /// The lockfile that was present before solving. 66 /// The lockfile that was present before solving.
67 final LockFile lockFile; 67 final LockFile lockFile;
68 68
69 final PubspecCache cache; 69 /// A cache of data requested during solving.
70 final SolverCache cache;
70 71
71 /// The set of packages that are being explicitly upgraded. 72 /// The set of packages that are being explicitly upgraded.
72 /// 73 ///
73 /// The solver will only allow the very latest version for each of these 74 /// The solver will only allow the very latest version for each of these
74 /// packages. 75 /// packages.
75 final _forceLatest = new Set<String>(); 76 final _forceLatest = new Set<String>();
76 77
77 /// The set of packages whose dependecy is being overridden by the root 78 /// The set of packages whose dependecy is being overridden by the root
78 /// package, keyed by the name of the package. 79 /// package, keyed by the name of the package.
79 /// 80 ///
(...skipping 30 matching lines...)
110 /// two differences. First, [_versions] doesn't have an entry for the root 111 /// two differences. First, [_versions] doesn't have an entry for the root
111 /// package, since it has only one valid version, but [_selection] does, since 112 /// package, since it has only one valid version, but [_selection] does, since
112 /// its dependencies are relevant. Second, when backtracking, [_versions] 113 /// its dependencies are relevant. Second, when backtracking, [_versions]
113 /// contains the version that's being backtracked, while [_selection] does 114 /// contains the version that's being backtracked, while [_selection] does
114 /// not. 115 /// not.
115 VersionSelection _selection; 116 VersionSelection _selection;
116 117
117 /// The number of solutions the solver has tried so far. 118 /// The number of solutions the solver has tried so far.
118 var _attemptedSolutions = 1; 119 var _attemptedSolutions = 1;
119 120
121 /// A pubspec for pub's implicit dependencies on barback and related packages.
122 final Pubspec _implicitPubspec = () {
123 var dependencies = [];
124 barback.pubConstraints.forEach((name, constraint) {
125 dependencies.add(new PackageDep(name, "hosted", constraint, name));
126 });
127
128 return new Pubspec("pub itself", dependencies: dependencies);
129 }();
130
120 BacktrackingSolver(SolveType type, SourceRegistry sources, this.root, 131 BacktrackingSolver(SolveType type, SourceRegistry sources, this.root,
121 this.lockFile, List<String> useLatest) 132 this.lockFile, List<String> useLatest)
122 : type = type, 133 : type = type,
123 sources = sources, 134 sources = sources,
124 cache = new PubspecCache(type, sources) { 135 cache = new SolverCache(type, sources) {
125 _selection = new VersionSelection(this); 136 _selection = new VersionSelection(this);
126 137
127 for (var package in useLatest) { 138 for (var package in useLatest) {
128 _forceLatest.add(package); 139 _forceLatest.add(package);
129 } 140 }
130 141
131 for (var override in root.dependencyOverrides) { 142 for (var override in root.dependencyOverrides) {
132 _overrides[override.name] = override; 143 _overrides[override.name] = override;
133 } 144 }
134 } 145 }
135 146
136 /// Run the solver. 147 /// Run the solver.
137 /// 148 ///
138 /// Completes with a list of specific package versions if successful or an 149 /// Completes with a list of specific package versions if successful or an
139 /// error if it failed to find a solution. 150 /// error if it failed to find a solution.
140 Future<SolveResult> solve() async { 151 Future<SolveResult> solve() async {
141 var stopwatch = new Stopwatch(); 152 var stopwatch = new Stopwatch();
142 153
143 _logParameters(); 154 _logParameters();
144 155
145 // Sort the overrides by package name to make sure they're deterministic. 156 // Sort the overrides by package name to make sure they're deterministic.
146 var overrides = _overrides.values.toList(); 157 var overrides = _overrides.values.toList();
147 overrides.sort((a, b) => a.name.compareTo(b.name)); 158 overrides.sort((a, b) => a.name.compareTo(b.name));
148 159
149 try { 160 try {
150 stopwatch.start(); 161 stopwatch.start();
151 162
152 // Pre-cache the root package's known pubspec. 163 // Pre-cache the root package's known pubspec.
153 var rootID = new PackageId.root(root); 164 var rootID = new PackageId.root(root);
154 cache.cache(rootID, root.pubspec);
155 cache.cache(new PackageId.magic('pub itself'), _implicitPubspec());
156 await _selection.select(rootID); 165 await _selection.select(rootID);
157 166
158 _validateSdkConstraint(root.pubspec); 167 _validateSdkConstraint(root.pubspec);
159 168
160 logSolve(); 169 logSolve();
161 var packages = await _solve(); 170 var packages = await _solve();
162 171
163 var pubspecs = new Map.fromIterable(packages, 172 var pubspecs = {};
164 key: (id) => id.name, 173 for (var id in packages) {
165 value: (id) => cache.getCachedPubspec(id)); 174 pubspecs[id.name] = await _getPubspec(id);
175 }
166 176
167 var resolved = await Future.wait( 177 var resolved = await Future.wait(
168 packages.map((id) => sources[id.source].resolveId(id))); 178 packages.map((id) => sources[id.source].resolveId(id)));
169 179
170 return new SolveResult.success(sources, root, lockFile, resolved, 180 return new SolveResult.success(sources, root, lockFile, resolved,
171 overrides, pubspecs, _getAvailableVersions(resolved), 181 overrides, pubspecs, _getAvailableVersions(resolved),
172 _attemptedSolutions); 182 _attemptedSolutions);
173 } on SolveFailure catch (error) { 183 } on SolveFailure catch (error) {
174 // Wrap a failure in a result so we can attach some other data. 184 // Wrap a failure in a result so we can attach some other data.
175 return new SolveResult.failure(sources, root, lockFile, overrides, 185 return new SolveResult.failure(sources, root, lockFile, overrides,
176 error, _attemptedSolutions); 186 error, _attemptedSolutions);
177 } finally { 187 } finally {
178 // Gather some solving metrics. 188 // Gather some solving metrics.
179 var buffer = new StringBuffer(); 189 var buffer = new StringBuffer();
180 buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.'); 190 buffer.writeln('${runtimeType} took ${stopwatch.elapsed} seconds.');
181 buffer.writeln(cache.describeResults()); 191 buffer.writeln(cache.describeResults());
182 log.solver(buffer); 192 log.solver(buffer);
183 } 193 }
184 } 194 }
185 195
186 /// Creates a pubspec for pub's implicit dependencies on barback and related
187 /// packages.
188 Pubspec _implicitPubspec() {
189 var dependencies = [];
190 barback.pubConstraints.forEach((name, constraint) {
191 dependencies.add(new PackageDep(name, "hosted", constraint, name));
192 });
193
194 return new Pubspec("pub itself", dependencies: dependencies);
195 }
196
197 /// Generates a map containing all of the known available versions for each 196 /// Generates a map containing all of the known available versions for each
198 /// package in [packages]. 197 /// package in [packages].
199 /// 198 ///
200 /// The version list may not always be complete. If the package is the root 199 /// The version list may not always be complete. If the package is the root
201 /// root package, or if it's a package that we didn't unlock while solving 200 /// root package, or if it's a package that we didn't unlock while solving
202 /// because we weren't trying to upgrade it, we will just know the current 201 /// because we weren't trying to upgrade it, we will just know the current
203 /// version. 202 /// version.
204 Map<String, List<Version>> _getAvailableVersions(List<PackageId> packages) { 203 Map<String, List<Version>> _getAvailableVersions(List<PackageId> packages) {
205 var availableVersions = new Map<String, List<Version>>(); 204 var availableVersions = new Map<String, List<Version>>();
206 for (var package in packages) { 205 for (var package in packages) {
(...skipping 262 matching lines...)
469 468
470 logSolve( 469 logSolve(
471 "version ${id.version} of ${id.name} doesn't match $constraint:\n" + 470 "version ${id.version} of ${id.name} doesn't match $constraint:\n" +
472 _selection.describeDependencies(id.name)); 471 _selection.describeDependencies(id.name));
473 throw new NoVersionException( 472 throw new NoVersionException(
474 id.name, id.version, constraint, deps.toList()); 473 id.name, id.version, constraint, deps.toList());
475 } 474 }
476 475
477 var pubspec; 476 var pubspec;
478 try { 477 try {
479 pubspec = await cache.getPubspec(id); 478 pubspec = await _getPubspec(id);
480 } on PackageNotFoundException { 479 } on PackageNotFoundException {
481 // We can only get here if the lockfile refers to a specific package 480 // We can only get here if the lockfile refers to a specific package
482 // version that doesn't exist (probably because it was yanked). 481 // version that doesn't exist (probably because it was yanked).
483 throw new NoVersionException(id.name, null, id.version, []); 482 throw new NoVersionException(id.name, null, id.version, []);
484 } 483 }
485 484
486 _validateSdkConstraint(pubspec); 485 _validateSdkConstraint(pubspec);
487 486
488 for (var dep in await depsFor(id)) { 487 for (var dep in await depsFor(id)) {
489 if (dep.isMagic) continue; 488 if (dep.isMagic) continue;
(...skipping 72 matching lines...)
562 // Don't mark the root package as failing because it's not in [_versions] 561 // Don't mark the root package as failing because it's not in [_versions]
563 // and there's only one version of it anyway. 562 // and there's only one version of it anyway.
564 if (name == root.name) return; 563 if (name == root.name) return;
565 _versions.firstWhere((queue) => queue.current.name == name).fail(); 564 _versions.firstWhere((queue) => queue.current.name == name).fail();
566 } 565 }
567 566
568 /// Returns the dependencies of the package identified by [id]. 567 /// Returns the dependencies of the package identified by [id].
569 /// 568 ///
570 /// This takes overrides and dev dependencies into account when neccessary. 569 /// This takes overrides and dev dependencies into account when neccessary.
571 Future<Set<PackageDep>> depsFor(PackageId id) async { 570 Future<Set<PackageDep>> depsFor(PackageId id) async {
572 var pubspec = await cache.getPubspec(id); 571 var pubspec = await _getPubspec(id);
573 var deps = pubspec.dependencies.toSet(); 572 var deps = pubspec.dependencies.toSet();
574 if (id.isRoot) { 573 if (id.isRoot) {
575 // Include dev dependencies of the root package. 574 // Include dev dependencies of the root package.
576 deps.addAll(pubspec.devDependencies); 575 deps.addAll(pubspec.devDependencies);
577 576
578 // Add all overrides. This ensures a dependency only present as an 577 // Add all overrides. This ensures a dependency only present as an
579 // override is still included. 578 // override is still included.
580 deps.addAll(_overrides.values); 579 deps.addAll(_overrides.values);
581 580
582 // Replace any overridden dependencies. 581 // Replace any overridden dependencies.
(...skipping 16 matching lines...)
599 } 598 }
600 599
601 if (dep.name == 'barback') { 600 if (dep.name == 'barback') {
602 deps.add(new PackageDep.magic('pub itself')); 601 deps.add(new PackageDep.magic('pub itself'));
603 } 602 }
604 } 603 }
605 604
606 return deps; 605 return deps;
607 } 606 }
608 607
608 /// Loads and returns the pubspec for [id].
609 Future<Pubspec> _getPubspec(PackageId id) async {
610 if (id.isRoot) return root.pubspec;
611 if (id.isMagic && id.name == 'pub itself') return _implicitPubspec;
612
613 var source = sources[id.source];
614 return await source.describe(id);
615 }
616
609 /// Logs the initial parameters to the solver. 617 /// Logs the initial parameters to the solver.
610 void _logParameters() { 618 void _logParameters() {
611 var buffer = new StringBuffer(); 619 var buffer = new StringBuffer();
612 buffer.writeln("Solving dependencies:"); 620 buffer.writeln("Solving dependencies:");
613 for (var package in root.dependencies) { 621 for (var package in root.dependencies) {
614 buffer.write("- $package"); 622 buffer.write("- $package");
615 var locked = getLocked(package.name); 623 var locked = getLocked(package.name);
616 if (_forceLatest.contains(package.name)) { 624 if (_forceLatest.contains(package.name)) {
617 buffer.write(" (use latest)"); 625 buffer.write(" (use latest)");
618 } else if (locked != null) { 626 } else if (locked != null) {
(...skipping 31 matching lines...)
650 void _validateSdkConstraint(Pubspec pubspec) { 658 void _validateSdkConstraint(Pubspec pubspec) {
651 if (_overrides.containsKey(pubspec.name)) return; 659 if (_overrides.containsKey(pubspec.name)) return;
652 if (pubspec.environment.sdkVersion.allows(sdk.version)) return; 660 if (pubspec.environment.sdkVersion.allows(sdk.version)) return;
653 661
654 throw new BadSdkVersionException(pubspec.name, 662 throw new BadSdkVersionException(pubspec.name,
655 'Package ${pubspec.name} requires SDK version ' 663 'Package ${pubspec.name} requires SDK version '
656 '${pubspec.environment.sdkVersion} but the current SDK is ' 664 '${pubspec.environment.sdkVersion} but the current SDK is '
657 '${sdk.version}.'); 665 '${sdk.version}.');
658 } 666 }
659 } 667 }
OLDNEW
« no previous file with comments | « lib/src/command/cache_add.dart ('k') | lib/src/solver/version_solver.dart » ('j') | no next file with comments »

Powered by Google App Engine