function DiffEngine::_shift_boundaries

Adjust inserts/deletes of identical lines to join changes as much as possible.

We do something when a run of changed lines include a line at one end and has an excluded, identical line at the other. We are free to choose which identical line is included. `compareseq' usually chooses the one at the beginning, but usually it is cleaner to consider the following identical line to be the "change".

This is extracted verbatim from analyze.c (GNU diffutils-2.7).

File

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

Class

DiffEngine

Class used internally by Diff to actually compute the diffs.

Namespace

Code

protected function _shift_boundaries($lines, &$changed, $other_changed) {
    $i = 0;
    $j = 0;
    $this::USE_ASSERTS && assert(sizeof($lines) == sizeof($changed));
    $len = sizeof($lines);
    $other_len = sizeof($other_changed);
    while (1) {
        
        /*
         * Scan forwards to find beginning of another run of changes.
         * Also keep track of the corresponding point in the other file.
         *
         * Throughout this code, $i and $j are adjusted together so that
         * the first $i elements of $changed and the first $j elements
         * of $other_changed both contain the same number of zeros
         * (unchanged lines).
         * Furthermore, $j is always kept so that $j == $other_len or
         * $other_changed[$j] == FALSE.
         */
        while ($j < $other_len && $other_changed[$j]) {
            $j++;
        }
        while ($i < $len && !$changed[$i]) {
            $this::USE_ASSERTS && assert($j < $other_len && !$other_changed[$j]);
            $i++;
            $j++;
            while ($j < $other_len && $other_changed[$j]) {
                $j++;
            }
        }
        if ($i == $len) {
            break;
        }
        $start = $i;
        // Find the end of this run of changes.
        while (++$i < $len && $changed[$i]) {
            continue;
        }
        do {
            
            /*
             * Record the length of this run of changes, so that
             * we can later determine whether the run has grown.
             */
            $runlength = $i - $start;
            
            /*
             * Move the changed region back, so long as the
             * previous unchanged line matches the last changed one.
             * This merges with previous changed regions.
             */
            while ($start > 0 && $lines[$start - 1] == $lines[$i - 1]) {
                $changed[--$start] = 1;
                $changed[--$i] = FALSE;
                while ($start > 0 && $changed[$start - 1]) {
                    $start--;
                }
                $this::USE_ASSERTS && assert($j > 0);
                while ($other_changed[--$j]) {
                    continue;
                }
                $this::USE_ASSERTS && assert($j >= 0 && !$other_changed[$j]);
            }
            
            /*
             * Set CORRESPONDING to the end of the changed run, at the last
             * point where it corresponds to a changed run in the other file.
             * CORRESPONDING == LEN means no such point has been found.
             */
            $corresponding = $j < $other_len ? $i : $len;
            
            /*
             * Move the changed region forward, so long as the
             * first changed line matches the following unchanged one.
             * This merges with following changed regions.
             * Do this second, so that if there are no merges,
             * the changed region is moved forward as far as possible.
             */
            while ($i < $len && $lines[$start] == $lines[$i]) {
                $changed[$start++] = FALSE;
                $changed[$i++] = 1;
                while ($i < $len && $changed[$i]) {
                    $i++;
                }
                $this::USE_ASSERTS && assert($j < $other_len && !$other_changed[$j]);
                $j++;
                if ($j < $other_len && $other_changed[$j]) {
                    $corresponding = $i;
                    while ($j < $other_len && $other_changed[$j]) {
                        $j++;
                    }
                }
            }
        } while ($runlength != $i - $start);
        
        /*
         * If possible, move the fully-merged run of changes
         * back to a corresponding run in the other file.
         */
        while ($corresponding < $i) {
            $changed[--$start] = 1;
            $changed[--$i] = 0;
            $this::USE_ASSERTS && assert($j > 0);
            while ($other_changed[--$j]) {
                continue;
            }
            $this::USE_ASSERTS && assert($j >= 0 && !$other_changed[$j]);
        }
    }
}