function Differ::calculateTrace

Same name in this branch

11.1.x vendor/nikic/php-parser/lib/PhpParser/Internal/Differ.php \PhpParser\Internal\Differ::calculateTrace()

Parameters

T[] $old: * @param T[] $new * @return array{array<int, array<int, int>>, int, int}

1 call to Differ::calculateTrace()

Differ::diff in vendor/phpstan/phpdoc-parser/src/Printer/Differ.php: * Calculate diff (edit script) from $old to $new. * *

File

vendor/phpstan/phpdoc-parser/src/Printer/Differ.php, line 74

Class

Differ: Inspired by https://github.com/nikic/PHP-Parser/tree/36a6dcd04e7b0285e8f0868f44bd49…

Namespace

PHPStan\PhpDocParser\Printer

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');
}