function Differ::calculateTrace

Same name in this branch

11.1.x vendor/phpstan/phpdoc-parser/src/Printer/Differ.php \PHPStan\PhpDocParser\Printer\Differ::calculateTrace()

Parameters

T[] $old:

T[] $new:

Return value

array{array<int, array<int, int>>, int, int}

1 call to Differ::calculateTrace()

Differ::diff in vendor/nikic/php-parser/lib/PhpParser/Internal/Differ.php: Calculate diff (edit script) from $old to $new.

File

vendor/nikic/php-parser/lib/PhpParser/Internal/Differ.php, line 62

Class

Differ: Implements the Myers diff algorithm.

Namespace

PhpParser\Internal

Code

private function calculateTrace(array $old, array $new) : array {
    $n = \count($old);
    $m = \count($new);
    $max = $n + $m;
    $v = [
        1 => 0,
    ];
    $trace = [];
    for ($d = 0; $d <= $max; $d++) {
        $trace[] = $v;
        for ($k = -$d; $k <= $d; $k += 2) {
            if ($k === -$d || $k !== $d && $v[$k - 1] < $v[$k + 1]) {
                $x = $v[$k + 1];
            }
            else {
                $x = $v[$k - 1] + 1;
            }
            $y = $x - $k;
            while ($x < $n && $y < $m && ($this->isEqual)($old[$x], $new[$y])) {
                $x++;
                $y++;
            }
            $v[$k] = $x;
            if ($x >= $n && $y >= $m) {
                return [
                    $trace,
                    $x,
                    $y,
                ];
            }
        }
    }
    throw new \Exception('Should not happen');
}