systemsdk / phpcpd / #34

Committed 08 Mar 2026 04:27PM UTC coverage: 80.785% (+2.4%) from 78.378%

Build # #34

Build Type

push

Committed by DKravtsov

Commit Message

phpcpd 9.0.0 release.

Coverage Stats

55 of 63 new or added lines in 12 files covered. (87.3%)

782 of 968 relevant lines covered (80.79%)

9.03 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

97.06

/src/Detector/Strategy/SuffixTree/ApproximateCloneDetectingSuffixTree.php

<?php

declare(strict_types=1);

namespace Systemsdk\PhpCPD\Detector\Strategy\SuffixTree;

use Systemsdk\PhpCPD\Exceptions\ProcessingResultException;

use function count;
use function sprintf;

/**
 * An extension of the suffix tree adding an algorithm for finding approximate clones, i.e. substrings which are similar
 */
class ApproximateCloneDetectingSuffixTree extends SuffixTree
{
    /**
     * This is the distance between two entries in the {@link #cloneInfos} map.
     */
    private const int INDEX_SPREAD = 10;

    /**
     * The maximal length of a clone. This influences the size of the (quadratic) {@link #edBuffer}.
     */
    private const int MAX_LENGTH = 1024;

    /**
     * The minimal length of clones to return.
     */
    protected int $minLength = 70;

    /**
     * The number of leaves reachable from the given node (1 for leaves).
     *
     * @var int[]
     * */
    private array $leafCount;

    /**
     * This map stores for each position the relevant clone infos.
     *
     * @var array<CloneInfo[]>
     */
    private array $cloneInfos = [];

    /**
     * Buffer used for calculating edit distance.
     *
     * @var array<int[]>
     */
    private array $edBuffer;

    /**
     * Number of units that must be equal at the start of a clone.
     */
    private int $headEquality = 10;

    /**
     * Create a new suffix tree from a given word. The word given as parameter is used internally and should
     * not be modified anymore, so copy it before if required.
     * <p>
     * This only word correctly if the given word is closed using a sentinel character.
     *
     * @param AbstractToken[] $word List of tokens to analyze
     */
    public function __construct(array $word)
    {
        parent::__construct($word);

        $arr = array_fill(0, self::MAX_LENGTH, 0);
        $this->edBuffer = array_fill(0, self::MAX_LENGTH, $arr);
        $this->ensureChildLists();
        $this->leafCount = array_fill(0, $this->numNodes, 0);
        $this->initLeafCount(0);
    }

    /**
     * Finds all clones in the string (List) used in the constructor.
     *
     * TODO: Add options: --min-lines
     * TODO: Possibly add consumer from original code.
     *
     * @param int $minLength the minimal length of a clone in tokens (not lines)
     * @param int $maxErrors the maximal number of errors/gaps allowed
     * @param int $headEquality the number of elements which have to be the same at the beginning of a clone
     *
     * @throws ProcessingResultException
     *
     * @return CloneInfo[]
     */
    public function findClones(int $minLength, int $maxErrors, int $headEquality): array
    {
        $this->minLength = $minLength;
        $this->headEquality = $headEquality;
        $this->cloneInfos = [];

        for ($i = 0, $count = count($this->word); $i < $count; $i++) {
            // Do quick start, as first character has to match anyway.
            $node = $this->nextNode->get(0, $this->word[$i]);

            if ($node < 0 || $this->leafCount[$node] <= 1) {
                continue;
            }

            // we know that we have an exact match of at least 'length'
            // characters, as the word itself is part of the suffix tree.
            $length = $this->nodeWordEnd[$node] - $this->nodeWordBegin[$node];
            $numReported = 0;

            for ($e = $this->nodeChildFirst[$node]; $e >= 0; $e = $this->nodeChildNext[$e]) {
                if ($this->matchWord($i, $i + $length, $this->nodeChildNode[$e], $length, $maxErrors)) {
                    $numReported++;
                }
            }

            if ($length >= $this->minLength && $numReported !== 1) {
                $this->reportClone($i, $i + $length, $node, $length, $length);
            }
        }

        $map = [];

        for ($index = 0, $count = count($this->word); $index <= $count; $index++) {
            /** @var CloneInfo[] $existingClones */
            $existingClones = $this->cloneInfos[$index] ?? null;

            if (!empty($existingClones)) {
                foreach ($existingClones as $ci) {
                    // length = number of tokens
                    if ($ci->length > $minLength) {
                        $previousCi = $map[$ci->token->line] ?? null;

                        if ($previousCi === null) {
                            $map[$ci->token->line] = $ci;
                        } elseif ($ci->length > $previousCi->length) {
                            $map[$ci->token->line] = $ci;
                        }
                    }
                }
            }
        }

        /** @var CloneInfo[] $values */
        $values = array_values($map);
        usort($values, static function (CloneInfo $a, CloneInfo $b): int {
            return $b->length - $a->length;
        });

        return $values;
    }

    /**
     * This should return true, if the provided character is not allowed to match with anything
     * else (e.g. is a sentinel).
     */
    protected function mayNotMatch(AbstractToken $token): bool
    {
        return $token instanceof Sentinel;
    }

    /**
     * This method is called whenever the {@link #MAX_LENGTH} is to small and hence the {@link #edBuffer} was not
     * large enough. This may cause that a really large clone is reported in multiple chunks of size{@link #MAX_LENGTH}
     * and potentially minor parts of such a clone might be lost.
     *
     * @throws ProcessingResultException
     */
    protected function reportBufferShortage(int $leafStart, int $leafLength): void
    {
        throw new ProcessingResultException(sprintf('Encountered buffer shortage: %d %d', $leafStart, $leafLength));
    }

    /**
     * Initializes the {@link #leafCount} array which given for each node the number of leaves reachable from it
     * (where leaves obtain a value of 1).
     */
    private function initLeafCount(int $node): void
    {
        $this->leafCount[$node] = 0;

        for ($e = $this->nodeChildFirst[$node]; $e >= 0; $e = $this->nodeChildNext[$e]) {
            $this->initLeafCount($this->nodeChildNode[$e]);
            $this->leafCount[$node] += $this->leafCount[$this->nodeChildNode[$e]];
        }

        if ($this->leafCount[$node] === 0) {
            $this->leafCount[$node] = 1;
        }
    }

    /**
     * Performs the approximative matching between the input word and the tree.
     *
     * @param int $wordStart the start position of the currently matched word (position in the input word)
     * @param int $wordPosition the current position along the input word
     * @param int $node the node we are currently at (i.e. the edge leading to this node is relevant to us).
     * @param int $nodeWordLength the length of the word found along the nodes (this may be different from the length
     *                            along the input word due to gaps)
     * @param int $maxErrors the number of errors still allowed
     *
     * @throws ProcessingResultException
     *
     * @return bool whether some clone was reported
     */
    private function matchWord(int $wordStart, int $wordPosition, int $node, int $nodeWordLength, int $maxErrors): bool
    {
        // We are aware that this method is longer than desirable for code
        // reading. However, we currently do not see a refactoring that has a
        // sensible cost-benefit ratio. Suggestions are welcome!

        // self match?
        if ($this->leafCount[$node] === 1 && $this->nodeWordBegin[$node] === $wordPosition) {
            return false;
        }

        $currentNodeWordLength = min($this->nodeWordEnd[$node] - $this->nodeWordBegin[$node], self::MAX_LENGTH - 1);

        // Do min edit distance
        $currentLength = $this->calculateMaxLength(
            $wordStart,
            $wordPosition,
            $node,
            $maxErrors,
            $currentNodeWordLength
        );

        if ($currentLength === 0) {
            return false;
        }

        if ($currentLength >= self::MAX_LENGTH - 1) {
            $this->reportBufferShortage($this->nodeWordBegin[$node], $currentNodeWordLength);
        }

        // calculate cheapest match
        $best = $maxErrors + 42;
        $iBest = 0;
        $jBest = 0;

        for ($k = 0; $k <= $currentLength; $k++) {
            $i = $currentLength - $k;
            $j = $currentLength;

            if ($this->edBuffer[$i][$j] < $best) {
                $best = $this->edBuffer[$i][$j];
                $iBest = $i;
                $jBest = $j;
            }

            $i = $currentLength;
            $j = $currentLength - $k;

            if ($this->edBuffer[$i][$j] < $best) {
                $best = $this->edBuffer[$i][$j];
                $iBest = $i;
                $jBest = $j;
            }
        }

        while (
            $wordPosition + $iBest < count($this->word)
            && $jBest < $currentNodeWordLength
            && $this->word[$wordPosition + $iBest] !== $this->word[$this->nodeWordBegin[$node] + $jBest]
            && $this->word[$wordPosition + $iBest]->equals($this->word[$this->nodeWordBegin[$node] + $jBest])
        ) {
            $iBest++;
            $jBest++;
        }

        $numReported = 0;

        if ($currentLength === $currentNodeWordLength) {
            // we may proceed
            for ($e = $this->nodeChildFirst[$node]; $e >= 0; $e = $this->nodeChildNext[$e]) {
                if (
                    $this->matchWord(
                        $wordStart,
                        $wordPosition + $iBest,
                        $this->nodeChildNode[$e],
                        $nodeWordLength + $jBest,
                        $maxErrors - $best
                    )
                ) {
                    $numReported++;
                }
            }
        }

        // do not report locally if had reports in exactly one subtree (would be pure subclone)
        if ($numReported === 1) {
            return true;
        }

        // disallow tail changes
        while (
            $iBest > 0
            && $jBest > 0
            && !$this->word[$wordPosition + $iBest - 1]->equals($this->word[$this->nodeWordBegin[$node] + $jBest - 1])
        ) {
            if (
                $iBest > 1
                &&
                    $this->word[$wordPosition + $iBest - 2]->equals(
                        $this->word[$this->nodeWordBegin[$node] + $jBest - 1]
                    )
            ) {
                $iBest--;
            } elseif (
                $jBest > 1
                && $this->word[$wordPosition + $iBest - 1]->equals(
                    $this->word[$this->nodeWordBegin[$node] + $jBest - 2]
                )
            ) {
                $jBest--;
            } else {
                $iBest--;
                $jBest--;
            }
        }

        // report if real clone
        if ($iBest > 0 && $jBest > 0) {
            $numReported++;
            $this->reportClone($wordStart, $wordPosition + $iBest, $node, $jBest, $nodeWordLength + $jBest);
        }

        return $numReported > 0;
    }

    /**
     * Calculates the maximum length we may take along the word to the current $node
     * (respecting the number of errors to make). *.
     *
     * @param int $wordStart the start position of the currently matched word (position in the input word)
     * @param int $wordPosition the current position along the input word
     * @param int $node the node we are currently at (i.e. the edge leading to this node is relevant to us).
     * @param int $maxErrors the number of errors still allowed
     * @param int $currentNodeWordLength the length of the word found along the nodes (this may be different from the
     *                                   actual length due to buffer limits)
     *
     * @return int the maximal length that can be taken
     */
    private function calculateMaxLength(
        int $wordStart,
        int $wordPosition,
        int $node,
        int $maxErrors,
        int $currentNodeWordLength
    ): int {
        $this->edBuffer[0][0] = 0;

        for ($currentLength = 1; $currentLength <= $currentNodeWordLength; $currentLength++) {
            /** @var int<1, max> $best */
            $best = $currentLength;
            $this->edBuffer[0][$currentLength] = $currentLength;
            $this->edBuffer[$currentLength][0] = $currentLength;

            if ($wordPosition + $currentLength >= count($this->word)) {
                break;
            }

            // deal with case that character may not be matched (sentinel!)
            $iChar = $this->word[$wordPosition + $currentLength - 1];
            $jChar = $this->word[$this->nodeWordBegin[$node] + $currentLength - 1];

            if ($this->mayNotMatch($iChar) || $this->mayNotMatch($jChar)) {
                break;
            }

            // usual matrix completion for edit distance
            for ($k = 1; $k < $currentLength; $k++) {
                $best = min(
                    $best,
                    $this->fillEDBuffer(
                        $k,
                        $currentLength,
                        $wordPosition,
                        $this->nodeWordBegin[$node]
                    )
                );
            }

            for ($k = 1; $k < $currentLength; $k++) {
                $best = min(
                    $best,
                    $this->fillEDBuffer(
                        $currentLength,
                        $k,
                        $wordPosition,
                        $this->nodeWordBegin[$node]
                    )
                );
            }
            $best = min(
                $best,
                $this->fillEDBuffer(
                    $currentLength,
                    $currentLength,
                    $wordPosition,
                    $this->nodeWordBegin[$node]
                )
            );

            if (
                $best > $maxErrors
                || $wordPosition - $wordStart + $currentLength <= $this->headEquality && $best > 0
            ) {
                break;
            }
        }
        $currentLength--;

        return $currentLength;
    }

    private function reportClone(
        int $wordBegin,
        int $wordEnd,
        int $currentNode,
        int $nodeWordPos,
        int $nodeWordLength
    ): void {
        $length = $wordEnd - $wordBegin;

        if ($length < $this->minLength || $nodeWordLength < $this->minLength) {
            return;
        }

        $otherClones = new PairList(16);
        $this->findRemainingClones(
            $otherClones,
            $nodeWordLength,
            $currentNode,
            $this->nodeWordEnd[$currentNode] - $this->nodeWordBegin[$currentNode] - $nodeWordPos,
            $wordBegin
        );

        $occurrences = 1 + $otherClones->size();

        // check whether we may start from here
        $t = $this->word[$wordBegin];
        $newInfo = new CloneInfo($length, $wordBegin, $occurrences, $t, $otherClones);

        for ($index = max(0, $wordBegin - self::INDEX_SPREAD + 1); $index <= $wordBegin; $index++) {
            $existingClones = $this->cloneInfos[$index] ?? null;

            if (
                $existingClones !== null
                && array_any(
                    $existingClones,
                    static fn (CloneInfo $cloneInfo): bool => $cloneInfo->dominates($newInfo, $wordBegin - $index)
                )
            ) {
                // we already have a dominating clone, so ignore
                return;
            }
        }

        // add clone to $otherClones to avoid getting more duplicates
        for ($i = $wordBegin; $i < $wordEnd; $i += self::INDEX_SPREAD) {
            $this->cloneInfos[$i][]
                = new CloneInfo($length - ($i - $wordBegin), $wordBegin, $occurrences, $t, $otherClones);
        }
        $t = $this->word[$wordBegin];

        for ($clone = 0; $clone < $otherClones->size(); $clone++) {
            $start = $otherClones->getFirst($clone);
            $otherLength = $otherClones->getSecond($clone);

            for ($i = 0; $i < $otherLength; $i += self::INDEX_SPREAD) {
                $this->cloneInfos[$start + $i][]
                    = new CloneInfo($otherLength - $i, $wordBegin, $occurrences, $t, $otherClones);
            }
        }
    }

    /**
     * Fills the edit distance buffer at position (i,j).
     *
     * @param int $i the first index of the buffer
     * @param int $j the second index of the buffer
     * @param int $iOffset the offset where the word described by $i starts
     * @param int $jOffset the offset where the word described by $j starts
     *
     * @return int the value inserted into the buffer
     */
    private function fillEDBuffer(int $i, int $j, int $iOffset, int $jOffset): int
    {
        $iChar = $this->word[$iOffset + $i - 1];
        $jChar = $this->word[$jOffset + $j - 1];

        $insertDelete = 1 + min($this->edBuffer[$i - 1][$j], $this->edBuffer[$i][$j - 1]);
        $change = $this->edBuffer[$i - 1][$j - 1] + ($iChar->equals($jChar) ? 0 : 1);

        return $this->edBuffer[$i][$j] = min($insertDelete, $change);
    }

    /**
     * Fills a list of pairs giving the start positions and lengths of the remaining clones.
     *
     * @param PairList $clonePositions the clone positions being filled (start position and length)
     * @param int $nodeWordLength the length of the word along the nodes
     * @param int $currentNode the node we are currently at
     * @param int $distance  the distance along the word leading to the current node
     * @param int $wordStart the start of the currently searched word
     */
    private function findRemainingClones(
        PairList $clonePositions,
        int $nodeWordLength,
        int $currentNode,
        int $distance,
        int $wordStart
    ): void {
        for (
            $nextNode = $this->nodeChildFirst[$currentNode];
            $nextNode >= 0;
            $nextNode = $this->nodeChildNext[$nextNode]
        ) {
            $node = $this->nodeChildNode[$nextNode];
            $this->findRemainingClones($clonePositions, $nodeWordLength, $node, $distance
                    + $this->nodeWordEnd[$node] - $this->nodeWordBegin[$node], $wordStart);
        }

        if ($this->nodeChildFirst[$currentNode] < 0) {
            $start = count($this->word) - $distance - $nodeWordLength;

            if ($start !== $wordStart) {
                $clonePositions->add($start, $nodeWordLength);
            }
        }
    }
}

1	<?php
2
3	declare(strict_types=1);
4
5	namespace Systemsdk\PhpCPD\Detector\Strategy\SuffixTree;
6
7	use Systemsdk\PhpCPD\Exceptions\ProcessingResultException;
8
9	use function count;
10	use function sprintf;
11
12	/**
13	* An extension of the suffix tree adding an algorithm for finding approximate clones, i.e. substrings which are similar
14	*/
15	class ApproximateCloneDetectingSuffixTree extends SuffixTree
16	{
17	/**
18	* This is the distance between two entries in the {@link #cloneInfos} map.
19	*/
20	private const int INDEX_SPREAD = 10;
21
22	/**
23	* The maximal length of a clone. This influences the size of the (quadratic) {@link #edBuffer}.
24	*/
25	private const int MAX_LENGTH = 1024;
26
27	/**
28	* The minimal length of clones to return.
29	*/
30	protected int $minLength = 70;
31
32	/**
33	* The number of leaves reachable from the given node (1 for leaves).
34	*
35	* @var int[]
36	* */
37	private array $leafCount;
38
39	/**
40	* This map stores for each position the relevant clone infos.
41	*
42	* @var array<CloneInfo[]>
43	*/
44	private array $cloneInfos = [];
45
46	/**
47	* Buffer used for calculating edit distance.
48	*
49	* @var array<int[]>
50	*/
51	private array $edBuffer;
52
53	/**
54	* Number of units that must be equal at the start of a clone.
55	*/
56	private int $headEquality = 10;
57
58	/**
59	* Create a new suffix tree from a given word. The word given as parameter is used internally and should
60	* not be modified anymore, so copy it before if required.
61	* <p>
62	* This only word correctly if the given word is closed using a sentinel character.
63	*
64	* @param AbstractToken[] $word List of tokens to analyze
65	*/
66	public function __construct(array $word)
67	{
68	parent::__construct($word);	11✔
69
70	$arr = array_fill(0, self::MAX_LENGTH, 0);	11✔
71	$this->edBuffer = array_fill(0, self::MAX_LENGTH, $arr);	11✔
72	$this->ensureChildLists();	11✔
73	$this->leafCount = array_fill(0, $this->numNodes, 0);	11✔
74	$this->initLeafCount(0);	11✔
75	}
76
77	/**
78	* Finds all clones in the string (List) used in the constructor.
79	*
80	* TODO: Add options: --min-lines
81	* TODO: Possibly add consumer from original code.
82	*
83	* @param int $minLength the minimal length of a clone in tokens (not lines)
84	* @param int $maxErrors the maximal number of errors/gaps allowed
85	* @param int $headEquality the number of elements which have to be the same at the beginning of a clone
86	*
87	* @throws ProcessingResultException
88	*
89	* @return CloneInfo[]
90	*/
91	public function findClones(int $minLength, int $maxErrors, int $headEquality): array
92	{
93	$this->minLength = $minLength;	11✔
94	$this->headEquality = $headEquality;	11✔
95	$this->cloneInfos = [];	11✔
96
97	for ($i = 0, $count = count($this->word); $i < $count; $i++) {	11✔
98	// Do quick start, as first character has to match anyway.
99	$node = $this->nextNode->get(0, $this->word[$i]);	11✔
100
101	if ($node < 0 \|\| $this->leafCount[$node] <= 1) {	11✔
102	continue;	11✔
103	}
104
105	// we know that we have an exact match of at least 'length'
106	// characters, as the word itself is part of the suffix tree.
107	$length = $this->nodeWordEnd[$node] - $this->nodeWordBegin[$node];	11✔
108	$numReported = 0;	11✔
109
110	for ($e = $this->nodeChildFirst[$node]; $e >= 0; $e = $this->nodeChildNext[$e]) {	11✔
111	if ($this->matchWord($i, $i + $length, $this->nodeChildNode[$e], $length, $maxErrors)) {	11✔
112	$numReported++;	9✔
113	}
114	}
115
116	if ($length >= $this->minLength && $numReported !== 1) {	11✔
117	$this->reportClone($i, $i + $length, $node, $length, $length);	5✔
118	}
119	}
120
121	$map = [];	11✔
122
123	for ($index = 0, $count = count($this->word); $index <= $count; $index++) {	11✔
124	/** @var CloneInfo[] $existingClones */
125	$existingClones = $this->cloneInfos[$index] ?? null;	11✔
126
127	if (!empty($existingClones)) {	11✔
128	foreach ($existingClones as $ci) {	7✔
129	// length = number of tokens
130	if ($ci->length > $minLength) {	7✔
131	$previousCi = $map[$ci->token->line] ?? null;	7✔
132
133	if ($previousCi === null) {	7✔
134	$map[$ci->token->line] = $ci;	7✔
135	} elseif ($ci->length > $previousCi->length) {	7✔
136	$map[$ci->token->line] = $ci;	1✔
137	}
138	}
139	}
140	}
141	}
142
143	/** @var CloneInfo[] $values */
144	$values = array_values($map);	11✔
145	usort($values, static function (CloneInfo $a, CloneInfo $b): int {	11✔
146	return $b->length - $a->length;	2✔
147	});	11✔
148
149	return $values;	11✔
150	}
151
152	/**
153	* This should return true, if the provided character is not allowed to match with anything
154	* else (e.g. is a sentinel).
155	*/
156	protected function mayNotMatch(AbstractToken $token): bool
157	{
158	return $token instanceof Sentinel;	11✔
159	}
160
161	/**
162	* This method is called whenever the {@link #MAX_LENGTH} is to small and hence the {@link #edBuffer} was not
163	* large enough. This may cause that a really large clone is reported in multiple chunks of size{@link #MAX_LENGTH}
164	* and potentially minor parts of such a clone might be lost.
165	*
166	* @throws ProcessingResultException
167	*/
168	protected function reportBufferShortage(int $leafStart, int $leafLength): void
169	{
NEW 170	throw new ProcessingResultException(sprintf('Encountered buffer shortage: %d %d', $leafStart, $leafLength));	×
171	}
172
173	/**
174	* Initializes the {@link #leafCount} array which given for each node the number of leaves reachable from it
175	* (where leaves obtain a value of 1).
176	*/
177	private function initLeafCount(int $node): void
178	{
179	$this->leafCount[$node] = 0;	11✔
180
181	for ($e = $this->nodeChildFirst[$node]; $e >= 0; $e = $this->nodeChildNext[$e]) {	11✔
182	$this->initLeafCount($this->nodeChildNode[$e]);	11✔
183	$this->leafCount[$node] += $this->leafCount[$this->nodeChildNode[$e]];	11✔
184	}
185
186	if ($this->leafCount[$node] === 0) {	11✔
187	$this->leafCount[$node] = 1;	11✔
188	}
189	}
190
191	/**
192	* Performs the approximative matching between the input word and the tree.
193	*
194	* @param int $wordStart the start position of the currently matched word (position in the input word)
195	* @param int $wordPosition the current position along the input word
196	* @param int $node the node we are currently at (i.e. the edge leading to this node is relevant to us).
197	* @param int $nodeWordLength the length of the word found along the nodes (this may be different from the length
198	* along the input word due to gaps)
199	* @param int $maxErrors the number of errors still allowed
200	*
201	* @throws ProcessingResultException
202	*
203	* @return bool whether some clone was reported
204	*/
205	private function matchWord(int $wordStart, int $wordPosition, int $node, int $nodeWordLength, int $maxErrors): bool
206	{
207	// We are aware that this method is longer than desirable for code
208	// reading. However, we currently do not see a refactoring that has a
209	// sensible cost-benefit ratio. Suggestions are welcome!
210
211	// self match?
212	if ($this->leafCount[$node] === 1 && $this->nodeWordBegin[$node] === $wordPosition) {	11✔
213	return false;	11✔
214	}
215
216	$currentNodeWordLength = min($this->nodeWordEnd[$node] - $this->nodeWordBegin[$node], self::MAX_LENGTH - 1);	11✔
217
218	// Do min edit distance
219	$currentLength = $this->calculateMaxLength(	11✔
220	$wordStart,	11✔
221	$wordPosition,	11✔
222	$node,	11✔
223	$maxErrors,	11✔
224	$currentNodeWordLength	11✔
225	);	11✔
226
227	if ($currentLength === 0) {	11✔
228	return false;	11✔
229	}
230
231	if ($currentLength >= self::MAX_LENGTH - 1) {	9✔
232	$this->reportBufferShortage($this->nodeWordBegin[$node], $currentNodeWordLength);	×
233	}
234
235	// calculate cheapest match
236	$best = $maxErrors + 42;	9✔
237	$iBest = 0;	9✔
238	$jBest = 0;	9✔
239
240	for ($k = 0; $k <= $currentLength; $k++) {	9✔
241	$i = $currentLength - $k;	9✔
242	$j = $currentLength;	9✔
243
244	if ($this->edBuffer[$i][$j] < $best) {	9✔
245	$best = $this->edBuffer[$i][$j];	9✔
246	$iBest = $i;	9✔
247	$jBest = $j;	9✔
248	}
249
250	$i = $currentLength;	9✔
251	$j = $currentLength - $k;	9✔
252
253	if ($this->edBuffer[$i][$j] < $best) {	9✔
254	$best = $this->edBuffer[$i][$j];	1✔
255	$iBest = $i;	1✔
256	$jBest = $j;	1✔
257	}
258	}
259
260	while (
261	$wordPosition + $iBest < count($this->word)	9✔
262	&& $jBest < $currentNodeWordLength	9✔
263	&& $this->word[$wordPosition + $iBest] !== $this->word[$this->nodeWordBegin[$node] + $jBest]	9✔
264	&& $this->word[$wordPosition + $iBest]->equals($this->word[$this->nodeWordBegin[$node] + $jBest])	9✔
265	) {
266	$iBest++;	×
267	$jBest++;	×
268	}
269
270	$numReported = 0;	9✔
271
272	if ($currentLength === $currentNodeWordLength) {	9✔
273	// we may proceed
274	for ($e = $this->nodeChildFirst[$node]; $e >= 0; $e = $this->nodeChildNext[$e]) {	9✔
275	if (
276	$this->matchWord(	9✔
277	$wordStart,	9✔
278	$wordPosition + $iBest,	9✔
279	$this->nodeChildNode[$e],	9✔
280	$nodeWordLength + $jBest,	9✔
281	$maxErrors - $best	9✔
282	)	9✔
283	) {
284	$numReported++;	6✔
285	}
286	}
287	}
288
289	// do not report locally if had reports in exactly one subtree (would be pure subclone)
290	if ($numReported === 1) {	9✔
291	return true;	6✔
292	}
293
294	// disallow tail changes
295	while (
296	$iBest > 0	9✔
297	&& $jBest > 0	9✔
298	&& !$this->word[$wordPosition + $iBest - 1]->equals($this->word[$this->nodeWordBegin[$node] + $jBest - 1])	9✔
299	) {
300	if (
301	$iBest > 1	1✔
302	&&
303	$this->word[$wordPosition + $iBest - 2]->equals(	1✔
304	$this->word[$this->nodeWordBegin[$node] + $jBest - 1]	1✔
305	)	1✔
306	) {
307	$iBest--;	×
308	} elseif (
309	$jBest > 1	1✔
310	&& $this->word[$wordPosition + $iBest - 1]->equals(	1✔
311	$this->word[$this->nodeWordBegin[$node] + $jBest - 2]	1✔
312	)	1✔
313	) {
314	$jBest--;	×
315	} else {
316	$iBest--;	1✔
317	$jBest--;	1✔
318	}
319	}
320
321	// report if real clone
322	if ($iBest > 0 && $jBest > 0) {	9✔
323	$numReported++;	9✔
324	$this->reportClone($wordStart, $wordPosition + $iBest, $node, $jBest, $nodeWordLength + $jBest);	9✔
325	}
326
327	return $numReported > 0;	9✔
328	}
329
330	/**
331	* Calculates the maximum length we may take along the word to the current $node
332	* (respecting the number of errors to make). *.
333	*
334	* @param int $wordStart the start position of the currently matched word (position in the input word)
335	* @param int $wordPosition the current position along the input word
336	* @param int $node the node we are currently at (i.e. the edge leading to this node is relevant to us).
337	* @param int $maxErrors the number of errors still allowed
338	* @param int $currentNodeWordLength the length of the word found along the nodes (this may be different from the
339	* actual length due to buffer limits)
340	*
341	* @return int the maximal length that can be taken
342	*/
343	private function calculateMaxLength(
344	int $wordStart,
345	int $wordPosition,
346	int $node,
347	int $maxErrors,
348	int $currentNodeWordLength
349	): int {
350	$this->edBuffer[0][0] = 0;	11✔
351
352	for ($currentLength = 1; $currentLength <= $currentNodeWordLength; $currentLength++) {	11✔
353	/** @var int<1, max> $best */
354	$best = $currentLength;	11✔
355	$this->edBuffer[0][$currentLength] = $currentLength;	11✔
356	$this->edBuffer[$currentLength][0] = $currentLength;	11✔
357
358	if ($wordPosition + $currentLength >= count($this->word)) {	11✔
359	break;	9✔
360	}
361
362	// deal with case that character may not be matched (sentinel!)
363	$iChar = $this->word[$wordPosition + $currentLength - 1];	11✔
364	$jChar = $this->word[$this->nodeWordBegin[$node] + $currentLength - 1];	11✔
365
366	if ($this->mayNotMatch($iChar) \|\| $this->mayNotMatch($jChar)) {	11✔
367	break;	9✔
368	}
369
370	// usual matrix completion for edit distance
371	for ($k = 1; $k < $currentLength; $k++) {	11✔
372	$best = min(	8✔
373	$best,	8✔
374	$this->fillEDBuffer(	8✔
375	$k,	8✔
376	$currentLength,	8✔
377	$wordPosition,	8✔
378	$this->nodeWordBegin[$node]	8✔
379	)	8✔
380	);	8✔
381	}
382
383	for ($k = 1; $k < $currentLength; $k++) {	11✔
384	$best = min(	8✔
385	$best,	8✔
386	$this->fillEDBuffer(	8✔
387	$currentLength,	8✔
388	$k,	8✔
389	$wordPosition,	8✔
390	$this->nodeWordBegin[$node]	8✔
391	)	8✔
392	);	8✔
393	}
394	$best = min(	11✔
395	$best,	11✔
396	$this->fillEDBuffer(	11✔
397	$currentLength,	11✔
398	$currentLength,	11✔
399	$wordPosition,	11✔
400	$this->nodeWordBegin[$node]	11✔
401	)	11✔
402	);	11✔
403
404	if (
405	$best > $maxErrors	11✔
406	\|\| $wordPosition - $wordStart + $currentLength <= $this->headEquality && $best > 0	11✔
407	) {
408	break;	11✔
409	}
410	}
411	$currentLength--;	11✔
412
413	return $currentLength;	11✔
414	}
415
416	private function reportClone(
417	int $wordBegin,
418	int $wordEnd,
419	int $currentNode,
420	int $nodeWordPos,
421	int $nodeWordLength
422	): void {
423	$length = $wordEnd - $wordBegin;	9✔
424
425	if ($length < $this->minLength \|\| $nodeWordLength < $this->minLength) {	9✔
426	return;	9✔
427	}
428
429	$otherClones = new PairList(16);	7✔
430	$this->findRemainingClones(	7✔
431	$otherClones,	7✔
432	$nodeWordLength,	7✔
433	$currentNode,	7✔
434	$this->nodeWordEnd[$currentNode] - $this->nodeWordBegin[$currentNode] - $nodeWordPos,	7✔
435	$wordBegin	7✔
436	);	7✔
437
438	$occurrences = 1 + $otherClones->size();	7✔
439
440	// check whether we may start from here
441	$t = $this->word[$wordBegin];	7✔
442	$newInfo = new CloneInfo($length, $wordBegin, $occurrences, $t, $otherClones);	7✔
443
444	for ($index = max(0, $wordBegin - self::INDEX_SPREAD + 1); $index <= $wordBegin; $index++) {	7✔
445	$existingClones = $this->cloneInfos[$index] ?? null;	7✔
446
447	if (
448	$existingClones !== null	7✔
449	&& array_any(	7✔
450	$existingClones,	7✔
451	static fn (CloneInfo $cloneInfo): bool => $cloneInfo->dominates($newInfo, $wordBegin - $index)	7✔
452	)	7✔
453	) {
454	// we already have a dominating clone, so ignore
455	return;	7✔
456	}
457	}
458
459	// add clone to $otherClones to avoid getting more duplicates
460	for ($i = $wordBegin; $i < $wordEnd; $i += self::INDEX_SPREAD) {	7✔
461	$this->cloneInfos[$i][]	7✔
462	= new CloneInfo($length - ($i - $wordBegin), $wordBegin, $occurrences, $t, $otherClones);	7✔
463	}
464	$t = $this->word[$wordBegin];	7✔
465
466	for ($clone = 0; $clone < $otherClones->size(); $clone++) {	7✔
467	$start = $otherClones->getFirst($clone);	7✔
468	$otherLength = $otherClones->getSecond($clone);	7✔
469
470	for ($i = 0; $i < $otherLength; $i += self::INDEX_SPREAD) {	7✔
471	$this->cloneInfos[$start + $i][]	7✔
472	= new CloneInfo($otherLength - $i, $wordBegin, $occurrences, $t, $otherClones);	7✔
473	}
474	}
475	}
476
477	/**
478	* Fills the edit distance buffer at position (i,j).
479	*
480	* @param int $i the first index of the buffer
481	* @param int $j the second index of the buffer
482	* @param int $iOffset the offset where the word described by $i starts
483	* @param int $jOffset the offset where the word described by $j starts
484	*
485	* @return int the value inserted into the buffer
486	*/
487	private function fillEDBuffer(int $i, int $j, int $iOffset, int $jOffset): int
488	{
489	$iChar = $this->word[$iOffset + $i - 1];	11✔
490	$jChar = $this->word[$jOffset + $j - 1];	11✔
491
492	$insertDelete = 1 + min($this->edBuffer[$i - 1][$j], $this->edBuffer[$i][$j - 1]);	11✔
493	$change = $this->edBuffer[$i - 1][$j - 1] + ($iChar->equals($jChar) ? 0 : 1);	11✔
494
495	return $this->edBuffer[$i][$j] = min($insertDelete, $change);	11✔
496	}
497
498	/**
499	* Fills a list of pairs giving the start positions and lengths of the remaining clones.
500	*
501	* @param PairList $clonePositions the clone positions being filled (start position and length)
502	* @param int $nodeWordLength the length of the word along the nodes
503	* @param int $currentNode the node we are currently at
504	* @param int $distance the distance along the word leading to the current node
505	* @param int $wordStart the start of the currently searched word
506	*/
507	private function findRemainingClones(
508	PairList $clonePositions,
509	int $nodeWordLength,
510	int $currentNode,
511	int $distance,
512	int $wordStart
513	): void {
514	for (
515	$nextNode = $this->nodeChildFirst[$currentNode];	7✔
516	$nextNode >= 0;	7✔
517	$nextNode = $this->nodeChildNext[$nextNode]	7✔
518	) {
519	$node = $this->nodeChildNode[$nextNode];	6✔
520	$this->findRemainingClones($clonePositions, $nodeWordLength, $node, $distance	6✔
521	+ $this->nodeWordEnd[$node] - $this->nodeWordBegin[$node], $wordStart);	6✔
522	}
523
524	if ($this->nodeChildFirst[$currentNode] < 0) {	7✔
525	$start = count($this->word) - $distance - $nodeWordLength;	7✔
526
527	if ($start !== $wordStart) {	7✔
528	$clonePositions->add($start, $nodeWordLength);	7✔
529	}
530	}
531	}
532	}

systemsdk / phpcpd / #34

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous