blob: 980a87a2704eedfbb060dcb29c57f06a1c56c6b0 [file] [log] [blame]
// Copyright (c) 2017, 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.
import '../package_name.dart';
import 'assignment.dart';
import 'incompatibility.dart';
import 'set_relation.dart';
import 'term.dart';
/// A list of [Assignment]s that represent the solver's current best guess about
/// what's true for the eventual set of package versions that will comprise the
/// total solution.
/// See
class PartialSolution {
/// The assignments that have been made so far, in the order they were
/// assigned.
final _assignments = <Assignment>[];
/// The decisions made for each package.
final _decisions = <String, PackageId>{};
/// The intersection of all positive [Assignment]s for each package, minus any
/// negative [Assignment]s that refer to that package.
/// This is derived from [_assignments].
final _positive = <String, Term>{};
/// The union of all negative [Assignment]s for each package.
/// If a package has any positive [Assignment]s, it doesn't appear in this
/// map.
/// This is derived from [_assignments].
final _negative = <String, Map<PackageRef, Term>>{};
/// Returns all the decisions that have been made in this partial solution.
Iterable<PackageId> get decisions => _decisions.values;
/// Returns all [PackageRange]s that have been assigned but are not yet
/// satisfied.
Iterable<PackageRange> get unsatisfied => _positive.values
.where((term) => !_decisions.containsKey(
.map((term) => term.package);
// The current decision level—that is, the length of [decisions].
int get decisionLevel => _decisions.length;
/// The number of distinct solutions that have been attempted so far.
int get attemptedSolutions => _attemptedSolutions;
var _attemptedSolutions = 1;
/// Whether the solver is currently backtracking.
var _backtracking = false;
/// Adds an assignment of [package] as a decision and increments the
/// [decisionLevel].
void decide(PackageId package) {
// When we make a new decision after backtracking, count an additional
// attempted solution. If we backtrack multiple times in a row, though, we
// only want to count one, since we haven't actually started attempting a
// new solution.
if (_backtracking) _attemptedSolutions++;
_backtracking = false;
_decisions[] = package;
_assign(Assignment.decision(package, decisionLevel, _assignments.length));
/// Adds an assignment of [package] as a derivation.
void derive(PackageName package, bool isPositive, Incompatibility cause) {
package, isPositive, cause, decisionLevel, _assignments.length));
/// Adds [assignment] to [_assignments] and [_positive] or [_negative].
void _assign(Assignment assignment) {
/// Resets the current decision level to [decisionLevel], and removes all
/// assignments made after that level.
void backtrack(int decisionLevel) {
_backtracking = true;
var packages = <String>{};
while (_assignments.last.decisionLevel > decisionLevel) {
var removed = _assignments.removeLast();
if (removed.isDecision) _decisions.remove(;
// Re-compute [_positive] and [_negative] for the packages that were removed.
for (var package in packages) {
for (var assignment in _assignments) {
if (packages.contains( {
/// Registers [assignment] in [_positive] or [_negative].
void _register(Assignment assignment) {
var name =;
var oldPositive = _positive[name];
if (oldPositive != null) {
_positive[name] = oldPositive.intersect(assignment);
var ref = assignment.package.toRef();
var negativeByRef = _negative[name];
var oldNegative = negativeByRef == null ? null : negativeByRef[ref];
var term =
oldNegative == null ? assignment : assignment.intersect(oldNegative);
if (term.isPositive) {
_positive[name] = term;
} else {
_negative.putIfAbsent(name, () => {})[ref] = term;
/// Returns the first [Assignment] in this solution such that the sublist of
/// assignments up to and including that entry collectively satisfies [term].
/// Throws a [StateError] if [term] isn't satisfied by [this].
Assignment satisfier(Term term) {
Term assignedTerm;
for (var assignment in _assignments) {
if ( != continue;
if (!assignment.package.isRoot &&
!assignment.package.samePackage(term.package)) {
// not foo from hosted has no bearing on foo from git
if (!assignment.isPositive) continue;
// foo from hosted satisfies not foo from git
return assignment;
assignedTerm = assignedTerm == null
? assignment
: assignedTerm.intersect(assignment);
// As soon as we have enough assignments to satisfy [term], return them.
if (assignedTerm.satisfies(term)) return assignment;
throw StateError('[BUG] $term is not satisfied.');
/// Returns whether [this] satisfies [other].
/// That is, whether [other] must be true given the assignments in this
/// partial solution.
bool satisfies(Term term) => relation(term) == SetRelation.subset;
/// Returns the relationship between the package versions allowed by all
/// assignments in [this] and those allowed by [term].
SetRelation relation(Term term) {
var positive = _positive[];
if (positive != null) return positive.relation(term);
// If there are no assignments related to [term], that means the
// assignments allow any version of any package, which is a superset of
// [term].
var byRef = _negative[];
if (byRef == null) return SetRelation.overlapping;
// not foo from git is a superset of foo from hosted
// not foo from git overlaps not foo from hosted
var negative = byRef[term.package.toRef()];
if (negative == null) return SetRelation.overlapping;
return negative.relation(term);