lib/src/solver/partial_solution.dart

// 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 https://github.com/dart-lang/pub/tree/main/doc/solver.md#partial-solution.
class PartialSolution {
  /// The canonical [PackageRef]s of workspace root packages, keyed by package
  /// name.
  ///
  /// A dependency on any member of a workspace is treated as a dependency on
  /// that workspace's root package, so all solver operations canonicalize
  /// member references through this map before registering or relating terms.
  final Map<String, PackageRef> _rootRefs;

  PartialSolution([this._rootRefs = const {}]);

  /// 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(term.package.name))
      .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.name] = package;
    _assign(Assignment.decision(package, decisionLevel, _assignments.length));
  }

  /// Adds an assignment of [package] as a derivation.
  void derive(PackageRange package, bool isPositive, Incompatibility cause) {
    package = canonicalize(package);
    _assign(
      Assignment.derivation(
        package,
        isPositive,
        cause,
        decisionLevel,
        _assignments.length,
      ),
    );
  }

  /// Adds [assignment] to [_assignments] and [_positive] or [_negative].
  void _assign(Assignment assignment) {
    _assignments.add(assignment);
    _register(assignment);
  }

  /// Resets the current decision level to [decisionLevel], and removes all
  /// assignments made after that level.
  void backtrack(int decisionLevel) {
    _backtracking = true;

    final packages = <String>{};
    while (_assignments.last.decisionLevel > decisionLevel) {
      final removed = _assignments.removeLast();
      packages.add(removed.package.name);
      if (removed.isDecision) _decisions.remove(removed.package.name);
    }

    // Re-compute [_positive] and [_negative] for the packages that were
    // removed.
    for (var package in packages) {
      _positive.remove(package);
      _negative.remove(package);
    }

    for (var assignment in _assignments) {
      if (packages.contains(assignment.package.name)) {
        _register(assignment);
      }
    }
  }

  /// Registers [assignment] in [_positive] or [_negative].
  void _register(Assignment assignment) {
    final name = assignment.package.name;
    final oldPositive = _positive[name];
    if (oldPositive != null) {
      // Decisions and derivations are always consistent with the existing
      // positive assignment, so the intersection is never empty.
      _positive[name] =
          oldPositive.intersect(assignment) ??
          (throw StateError('[BUG] $assignment contradicts $oldPositive.'));
      return;
    }

    final ref = assignment.package.toRef();
    final negativeByRef = _negative[name];
    final oldNegative = negativeByRef == null ? null : negativeByRef[ref];
    final term =
        oldNegative == null ? assignment : assignment.intersect(oldNegative)!;

    if (term.isPositive) {
      _negative.remove(name);
      _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) {
    final prefix = PartialSolution(_rootRefs);
    for (var assignment in _assignments) {
      if (assignment.package.name != term.package.name) continue;

      prefix._register(assignment);
      if (prefix.satisfies(term)) return assignment;
    }

    throw StateError('[BUG] $term is not satisfied.');
  }

  /// Returns whether `this` satisfies [term].
  ///
  /// That is, whether [term] 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) {
    term = Term(canonicalize(term.package), term.isPositive);
    final positive = _positive[term.package.name];
    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].
    final byRef = _negative[term.package.name];
    if (byRef == null) return SetRelation.overlapping;

    final negative = byRef[term.package.toRef()];
    if (negative == null) return SetRelation.overlapping;

    return negative.relation(term);
  }

  /// Returns [package] with its workspace root reference, if it has one.
  PackageRange canonicalize(PackageRange package) =>
      _rootRefs[package.name]?.withConstraint(package.constraint) ?? package;
}