function DiffEngine::diff

File

core/lib/Drupal/Component/Diff/Engine/DiffEngine.php, line 35

Class

DiffEngine

Class used internally by Diff to actually compute the diffs.

Namespace

Code

public function diff($from_lines, $to_lines) {
    $n_from = sizeof($from_lines);
    $n_to = sizeof($to_lines);
    $this->xchanged = $this->ychanged = [];
    $this->xv = $this->yv = [];
    $this->xind = $this->yind = [];
    unset($this->seq);
    unset($this->in_seq);
    unset($this->lcs);
    // Skip leading common lines.
    for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) {
        if ($from_lines[$skip] !== $to_lines[$skip]) {
            break;
        }
        $this->xchanged[$skip] = $this->ychanged[$skip] = FALSE;
    }
    // Skip trailing common lines.
    $xi = $n_from;
    $yi = $n_to;
    for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) {
        if ($from_lines[$xi] !== $to_lines[$yi]) {
            break;
        }
        $this->xchanged[$xi] = $this->ychanged[$yi] = FALSE;
    }
    // Ignore lines which do not exist in both files.
    for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
        $xhash[$this->_line_hash($from_lines[$xi])] = 1;
    }
    for ($yi = $skip; $yi < $n_to - $endskip; $yi++) {
        $line = $to_lines[$yi];
        if ($this->ychanged[$yi] = empty($xhash[$this->_line_hash($line)])) {
            continue;
        }
        $yhash[$this->_line_hash($line)] = 1;
        $this->yv[] = $line;
        $this->yind[] = $yi;
    }
    for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
        $line = $from_lines[$xi];
        if ($this->xchanged[$xi] = empty($yhash[$this->_line_hash($line)])) {
            continue;
        }
        $this->xv[] = $line;
        $this->xind[] = $xi;
    }
    // Find the LCS.
    $this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv));
    // Merge edits when possible
    $this->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged);
    $this->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged);
    // Compute the edit operations.
    $edits = [];
    $xi = $yi = 0;
    while ($xi < $n_from || $yi < $n_to) {
        $this::USE_ASSERTS && assert($yi < $n_to || $this->xchanged[$xi]);
        $this::USE_ASSERTS && assert($xi < $n_from || $this->ychanged[$yi]);
        // Skip matching "snake".
        $copy = [];
        while ($xi < $n_from && $yi < $n_to && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {
            $copy[] = $from_lines[$xi++];
            ++$yi;
        }
        if ($copy) {
            $edits[] = new DiffOpCopy($copy);
        }
        // Find deletes & adds.
        $delete = [];
        while ($xi < $n_from && $this->xchanged[$xi]) {
            $delete[] = $from_lines[$xi++];
        }
        $add = [];
        while ($yi < $n_to && $this->ychanged[$yi]) {
            $add[] = $to_lines[$yi++];
        }
        if ($delete && $add) {
            $edits[] = new DiffOpChange($delete, $add);
        }
        elseif ($delete) {
            $edits[] = new DiffOpDelete($delete);
        }
        elseif ($add) {
            $edits[] = new DiffOpAdd($add);
        }
    }
    return $edits;
}