private function DiffEngine::shiftBoundaries

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/includes/diff.inc, line 513

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

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