Text_Diff_Engine_native::_shiftBoundaries() │ public │ WP 1.0

Adjusts 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).

Method of the class: Text_Diff_Engine_native{}

No Hooks.

Return

null. Nothing (null).

Usage

$Text_Diff_Engine_native = new Text_Diff_Engine_native();
$Text_Diff_Engine_native->_shiftBoundaries( $lines, $changed, $other_changed );

$lines (required)

-

$changed (required) (passed by reference — &)

-

$other_changed (required)

-

Text_Diff_Engine_native::_shiftBoundaries() Text Diff Engine native:: shiftBoundaries code ^{WP 6.6.2}

function _shiftBoundaries($lines, &$changed, $other_changed)
{
    $i = 0;
    $j = 0;

    assert(count($lines) == count($changed));
    $len = count($lines);
    $other_len = count($other_changed);

    while (1) {
        /* Scan forward to find the 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]) {
            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--;
                }
                assert($j > 0);
                while ($other_changed[--$j]) {
                    continue;
                }
                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++;
                }

                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;
            assert($j > 0);
            while ($other_changed[--$j]) {
                continue;
            }
            assert($j >= 0 && !$other_changed[$j]);
        }
    }
}