function _DiffEngine::diff in Diff 6

Same name and namespace in other branches

1. 5.2 DiffEngine.php \_DiffEngine::diff()
2. 5 DiffEngine.php \_DiffEngine::diff()
3. 6.2 DiffEngine.php \_DiffEngine::diff()
4. 7.3 DiffEngine.php \_DiffEngine::diff()
5. 7.2 DiffEngine.php \_DiffEngine::diff()

File

./DiffEngine.php, line 140

Class

_DiffEngine

Class used internally by Diff to actually compute the diffs.

Code

function diff($from_lines, $to_lines) {
  $n_from = sizeof($from_lines);
  $n_to = sizeof($to_lines);
  $this->xchanged = $this->ychanged = array();
  $this->xv = $this->yv = array();
  $this->xind = $this->yind = array();
  unset($this->seq);
  unset($this->in_seq);
  unset($this->lcs);

  // Skip leading common lines.
  for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) {
    if ($from_lines[$skip] !== $to_lines[$skip]) {
      break;
    }
    $this->xchanged[$skip] = $this->ychanged[$skip] = false;
  }

  // Skip trailing common lines.
  $xi = $n_from;
  $yi = $n_to;
  for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) {
    if ($from_lines[$xi] !== $to_lines[$yi]) {
      break;
    }
    $this->xchanged[$xi] = $this->ychanged[$yi] = false;
  }

  // Ignore lines which do not exist in both files.
  for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
    $xhash[$this
      ->_line_hash($from_lines[$xi])] = 1;
  }
  for ($yi = $skip; $yi < $n_to - $endskip; $yi++) {
    $line = $to_lines[$yi];
    if ($this->ychanged[$yi] = empty($xhash[$this
      ->_line_hash($line)])) {
      continue;
    }
    $yhash[$this
      ->_line_hash($line)] = 1;
    $this->yv[] = $line;
    $this->yind[] = $yi;
  }
  for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
    $line = $from_lines[$xi];
    if ($this->xchanged[$xi] = empty($yhash[$this
      ->_line_hash($line)])) {
      continue;
    }
    $this->xv[] = $line;
    $this->xind[] = $xi;
  }

  // Find the LCS.
  $this
    ->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv));

  // Merge edits when possible
  $this
    ->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged);
  $this
    ->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged);

  // Compute the edit operations.
  $edits = array();
  $xi = $yi = 0;
  while ($xi < $n_from || $yi < $n_to) {
    USE_ASSERTS && assert($yi < $n_to || $this->xchanged[$xi]);
    USE_ASSERTS && assert($xi < $n_from || $this->ychanged[$yi]);

    // Skip matching "snake".
    $copy = array();
    while ($xi < $n_from && $yi < $n_to && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {
      $copy[] = $from_lines[$xi++];
      ++$yi;
    }
    if ($copy) {
      $edits[] = new _DiffOp_Copy($copy);
    }

    // Find deletes & adds.
    $delete = array();
    while ($xi < $n_from && $this->xchanged[$xi]) {
      $delete[] = $from_lines[$xi++];
    }
    $add = array();
    while ($yi < $n_to && $this->ychanged[$yi]) {
      $add[] = $to_lines[$yi++];
    }
    if ($delete && $add) {
      $edits[] = new _DiffOp_Change($delete, $add);
    }
    elseif ($delete) {
      $edits[] = new _DiffOp_Delete($delete);
    }
    elseif ($add) {
      $edits[] = new _DiffOp_Add($add);
    }
  }
  return $edits;
}