This file is indexed.

/usr/share/php/Composer/DependencyResolver/RuleWatchGraph.php is in composer 1.0.0~beta2-1.

This file is owned by root:root, with mode 0o644.

The actual contents of the file can be viewed below.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
<?php

/*
 * This file is part of Composer.
 *
 * (c) Nils Adermann <naderman@naderman.de>
 *     Jordi Boggiano <j.boggiano@seld.be>
 *
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 */

namespace Composer\DependencyResolver;

/**
 * The RuleWatchGraph efficiently propagates decisions to other rules
 *
 * All rules generated for solving a SAT problem should be inserted into the
 * graph. When a decision on a literal is made, the graph can be used to
 * propagate the decision to all other rules involving the literal, leading to
 * other trivial decisions resulting from unit clauses.
 *
 * @author Nils Adermann <naderman@naderman.de>
 */
class RuleWatchGraph
{
    protected $watchChains = array();

    /**
     * Inserts a rule node into the appropriate chains within the graph
     *
     * The node is prepended to the watch chains for each of the two literals it
     * watches.
     *
     * Assertions are skipped because they only depend on a single package and
     * have no alternative literal that could be true, so there is no need to
     * watch changes in any literals.
     *
     * @param RuleWatchNode $node The rule node to be inserted into the graph
     */
    public function insert(RuleWatchNode $node)
    {
        if ($node->getRule()->isAssertion()) {
            return;
        }

        foreach (array($node->watch1, $node->watch2) as $literal) {
            if (!isset($this->watchChains[$literal])) {
                $this->watchChains[$literal] = new RuleWatchChain;
            }

            $this->watchChains[$literal]->unshift($node);
        }
    }

    /**
     * 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.
     *
     * @param  int       $decidedLiteral The literal which was decided (A in our example)
     * @param  int       $level          The level at which the decision took place and at which
     *                                   all resulting decisions should be made.
     * @param  Decisions $decisions      Used to check previous decisions and to
     *                                   register decisions resulting from propagation
     * @return Rule|null If a conflict is found the conflicting rule is returned
     */
    public function propagateLiteral($decidedLiteral, $level, $decisions)
    {
        // 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();
            $otherWatch = $node->getOtherWatch($literal);

            if (!$node->getRule()->isDisabled() && !$decisions->satisfy($otherWatch)) {
                $ruleLiterals = $node->getRule()->literals;

                $alternativeLiterals = array_filter($ruleLiterals, function ($ruleLiteral) use ($literal, $otherWatch, $decisions) {
                    return $literal !== $ruleLiteral &&
                        $otherWatch !== $ruleLiteral &&
                        !$decisions->conflict($ruleLiteral);
                });

                if ($alternativeLiterals) {
                    reset($alternativeLiterals);
                    $this->moveWatch($literal, current($alternativeLiterals), $node);
                    continue;
                }

                if ($decisions->conflict($otherWatch)) {
                    return $node->getRule();
                }

                $decisions->decide($otherWatch, $level, $node->getRule());
            }

            $chain->next();
        }

        return null;
    }

    /**
     * Moves a rule node from one watch chain to another
     *
     * The rule node's watched literals are updated accordingly.
     *
     * @param $fromLiteral mixed A literal the node used to watch
     * @param $toLiteral mixed A literal the node should watch now
     * @param $node mixed The rule node to be moved
     */
    protected function moveWatch($fromLiteral, $toLiteral, $node)
    {
        if (!isset($this->watchChains[$toLiteral])) {
            $this->watchChains[$toLiteral] = new RuleWatchChain;
        }

        $node->moveWatch($fromLiteral, $toLiteral);
        $this->watchChains[$fromLiteral]->remove();
        $this->watchChains[$toLiteral]->unshift($node);
    }
}