function _DiffEngine::_shift_boundaries in Diff 7.2

Same name and namespace in other branches

1. 5.2 DiffEngine.php \_DiffEngine::_shift_boundaries()
2. 5 DiffEngine.php \_DiffEngine::_shift_boundaries()
3. 6.2 DiffEngine.php \_DiffEngine::_shift_boundaries()
4. 6 DiffEngine.php \_DiffEngine::_shift_boundaries()
5. 7.3 DiffEngine.php \_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).

1 call to _DiffEngine::_shift_boundaries()

_DiffEngine::diff in ./DiffEngine.php

File

./DiffEngine.php, line 448

A PHP diff engine for phpwiki. (Taken from phpwiki-1.3.3)

Class

_DiffEngine

Class used internally by Diff to actually compute the diffs.

Code

function _shift_boundaries($lines, &$changed, $other_changed) {
  $i = 0;
  $j = 0;
  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]) {
      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--;
        }
        USE_ASSERTS && assert('$j > 0');
        while ($other_changed[--$j]) {
          continue;
        }
        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++;
        }
        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;
      USE_ASSERTS && assert('$j > 0');
      while ($other_changed[--$j]) {
        continue;
      }
      USE_ASSERTS && assert('$j >= 0 && !$other_changed[$j]');
    }
  }
}