Text_Diff_Engine_native::_shiftBoundaries

Advertisement

Summery Summery

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

Syntax Syntax

Text_Diff_Engine_native::_shiftBoundaries( $lines,  $changed,  $other_changed )

Description Description

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

Source Source

File: wp-includes/Text/Diff/Engine/native.php

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

Advertisement

Advertisement

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.