function RuleWatchGraph::propagateLiteral

Propagates a decision on a literal to all rules watching the literal

If a decision, e.g. +A has been made, then all rules containing -A, e.g. (-A|+B|+C) now need to satisfy at least one of the other literals, so that the rule as a whole becomes true, since with +A applied the rule is now (false|+B|+C) so essentially (+B|+C).

This means that all rules watching the literal -A need to be updated to watch 2 other literals which can still be satisfied instead. So literals that conflict with previously made decisions are not an option.

Alternatively it can occur that a unit clause results: e.g. if in the above example the rule was (-A|+B), then A turning true means that B must now be decided true as well.

Parameters

int $decidedLiteral The literal which was decided (A in our example):

int $level The level at which the decision took place and at which: all resulting decisions should be made.

Decisions $decisions Used to check previous decisions and to: register decisions resulting from propagation

Return value

Rule|null If a conflict is found the conflicting rule is returned

File

vendor/composer/composer/src/Composer/DependencyResolver/RuleWatchGraph.php, line 90

Class

RuleWatchGraph

The RuleWatchGraph efficiently propagates decisions to other rules

Namespace

Composer\DependencyResolver

Code

public function propagateLiteral(int $decidedLiteral, int $level, Decisions $decisions) : ?Rule {
    // we invert the decided literal here, example:
    // A was decided => (-A|B) now requires B to be true, so we look for
    // rules which are fulfilled by -A, rather than A.
    $literal = -$decidedLiteral;
    if (!isset($this->watchChains[$literal])) {
        return null;
    }
    $chain = $this->watchChains[$literal];
    $chain->rewind();
    while ($chain->valid()) {
        $node = $chain->current();
        if (!$node->getRule() instanceof MultiConflictRule) {
            $otherWatch = $node->getOtherWatch($literal);
            if (!$node->getRule()
                ->isDisabled() && !$decisions->satisfy($otherWatch)) {
                $ruleLiterals = $node->getRule()
                    ->getLiterals();
                $alternativeLiterals = array_filter($ruleLiterals, static function ($ruleLiteral) use ($literal, $otherWatch, $decisions) : bool {
                    return $literal !== $ruleLiteral && $otherWatch !== $ruleLiteral && !$decisions->conflict($ruleLiteral);
                });
                if (\count($alternativeLiterals) > 0) {
                    reset($alternativeLiterals);
                    $this->moveWatch($literal, current($alternativeLiterals), $node);
                    continue;
                }
                if ($decisions->conflict($otherWatch)) {
                    return $node->getRule();
                }
                $decisions->decide($otherWatch, $level, $node->getRule());
            }
        }
        else {
            foreach ($node->getRule()
                ->getLiterals() as $otherLiteral) {
                if ($literal !== $otherLiteral && !$decisions->satisfy($otherLiteral)) {
                    if ($decisions->conflict($otherLiteral)) {
                        return $node->getRule();
                    }
                    $decisions->decide($otherLiteral, $level, $node->getRule());
                }
            }
        }
        $chain->next();
    }
    return null;
}