From fee07e9b0f9d06b74fe9c616b7a7cb5f4957c578 Mon Sep 17 00:00:00 2001 From: dairiki Date: Thu, 13 Dec 2001 05:10:04 +0000 Subject: [PATCH] Refactor diff code: o Code clean-up and refactor. o Split the PhpWiki-independent part of the code into lib/difflib.php. o New CSS-formatted unified diff output replaces old table-heavy format. o Add character-level diffs. Issues: o New CSS-formatted diffs are very ugly in NS4 (and probably other oldish browsers.) o Character-level diffs may be overkill. Maybe back off to word-level diffs? git-svn-id: svn://svn.code.sf.net/p/phpwiki/code/trunk@759 96ab9672-09ca-45d6-a79d-3d69d39ca109 --- lib/diff.php | 1136 ++++++----------------------------------------- lib/difflib.php | 756 +++++++++++++++++++++++++++++++ phpwiki.css | 35 +- 3 files changed, 915 insertions(+), 1012 deletions(-) create mode 100644 lib/difflib.php diff --git a/lib/diff.php b/lib/diff.php index de008eaad..5e1240f77 100644 --- a/lib/diff.php +++ b/lib/diff.php @@ -1,1026 +1,160 @@ +// Copyright (C) 2000, 2001 Geoffrey T. Dairiki // You may copy this code freely under the conditions of the GPL. // -// FIXME: possibly remove assert()'s for production version? +require_once('lib/difflib.php'); -// PHP3 does not have assert() -define('USE_ASSERTS', function_exists('assert')); - - -/** - * Class used internally by WikiDiff to actually compute the diffs. - * - * The algorithm used here is mostly lifted from the perl module - * Algorithm::Diff (version 1.06) by Ned Konz, which is available at: - * http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip - * - * More ideas are taken from: - * http://www.ics.uci.edu/~eppstein/161/960229.html - * - * Some ideas are (and a bit of code) are from from analyze.c, from GNU - * diffutils-2.7, which can be found at: - * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz - * - * Finally, some ideas (subdivision by NCHUNKS > 2, and some optimizations) - * are my own. - */ -class _WikiDiffEngine +class HtmlUnifiedDiffFormatter extends UnifiedDiffFormatter { - var $edits; // List of editing operation to convert XV to YV. - var $xv = array(), $yv = array(); - - function _WikiDiffEngine ($from_lines, $to_lines) - { - $n_from = sizeof($from_lines); - $n_to = sizeof($to_lines); - $endskip = 0; - - // Ignore trailing and leading matching lines. - while ($n_from > 0 && $n_to > 0) - { - if ($from_lines[$n_from - 1] != $to_lines[$n_to - 1]) - break; - $n_from--; - $n_to--; - $endskip++; - } - for ( $skip = 0; $skip < min($n_from, $n_to); $skip++) - if ($from_lines[$skip] != $to_lines[$skip]) - break; - $n_from -= $skip; - $n_to -= $skip; - - $xlines = array(); - $ylines = array(); - $this->xchanged = array(); - $this->ychanged = array(); - - // Ignore lines which do not exist in both files. - for ($x = 0; $x < $n_from; $x++) - $xhash[$from_lines[$x + $skip]] = 1; - for ($y = 0; $y < $n_to; $y++) - { - $line = $to_lines[$y + $skip]; - $ylines[] = $line; - if ( ($this->ychanged[$y] = empty($xhash[$line])) ) - continue; - $yhash[$line] = 1; - $this->yv[] = $line; - $this->yind[] = $y; - } - for ($x = 0; $x < $n_from; $x++) - { - $line = $from_lines[$x + $skip]; - $xlines[] = $line; - if ( ($this->xchanged[$x] = empty($yhash[$line])) ) - continue; - $this->xv[] = $line; - $this->xind[] = $x; - } - - // Find the LCS. - $this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv)); - - // Merge edits when possible - $this->_shift_boundaries($xlines, $this->xchanged, $this->ychanged); - $this->_shift_boundaries($ylines, $this->ychanged, $this->xchanged); - - // Compute the edit operations. - $this->edits = array(); - if ($skip) - $this->edits[] = $skip; - - $x = 0; - $y = 0; - while ($x < $n_from || $y < $n_to) - { - USE_ASSERTS && assert($y < $n_to || $this->xchanged[$x]); - USE_ASSERTS && assert($x < $n_from || $this->ychanged[$y]); - - // Skip matching "snake". - $x0 = $x; - $ncopy = 0; - - while ( $x < $n_from && $y < $n_to - && !$this->xchanged[$x] && !$this->ychanged[$y]) - { - ++$x; - ++$y; - ++$ncopy; - } - if ($x > $x0) - $this->edits[] = $x - $x0; - - // Find deletes. - $x0 = $x; - $ndelete = 0; - while ($x < $n_from && $this->xchanged[$x]) - { - ++$x; - ++$ndelete; - } - if ($x > $x0) - $this->edits[] = -($x - $x0); + function HtmlUnifiedDiffFormatter($context_lines = 4) { + $this->UnifiedDiffFormatter($context_lines); + } - // Find adds. - if (!empty($this->ychanged[$y])) - { - $adds = array(); - while ($y < $n_to && $this->ychanged[$y]) - $adds[] = "" . $ylines[$y++]; - $this->edits[] = $adds; - } - } - if ($endskip != 0) - $this->edits[] = $endskip; - } + function _start_diff() { + echo "
\n"; + } + function _end_diff() { + echo "
\n"; + } + + function _start_block($header) { + echo "
\n"; + echo QElement('tt', $header); + } - /* Divide the Largest Common Subsequence (LCS) of the sequences - * [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally - * sized segments. - * - * Returns (LCS, PTS). LCS is the length of the LCS. PTS is an - * array of NCHUNKS+1 (X, Y) indexes giving the diving points between - * sub sequences. The first sub-sequence is contained in [X0, X1), - * [Y0, Y1), the second in [X1, X2), [Y1, Y2) and so on. Note - * that (X0, Y0) == (XOFF, YOFF) and - * (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM). - * - * This function assumes that the first lines of the specified portions - * of the two files do not match, and likewise that the last lines do not - * match. The caller must trim matching lines from the beginning and end - * of the portions it is going to specify. - */ - function _diag ($xoff, $xlim, $yoff, $ylim, $nchunks) - { - $flip = false; - - if ($xlim - $xoff > $ylim - $yoff) - { - // Things seems faster (I'm not sure I understand why) - // when the shortest sequence in X. - $flip = true; - list ($xoff, $xlim, $yoff, $ylim) - = array( $yoff, $ylim, $xoff, $xlim); - } + function _end_block() { + echo "
\n"; + } - if ($flip) - for ($i = $ylim - 1; $i >= $yoff; $i--) - $ymatches[$this->xv[$i]][] = $i; - else - for ($i = $ylim - 1; $i >= $yoff; $i--) - $ymatches[$this->yv[$i]][] = $i; + function _lines($lines, $class, $prefix = ' ', $elem = false) { + foreach ($lines as $line) { + if (!trim($line)) + $line = ' '; + elseif ($elem) + $line = QElement($elem, $line); + + echo Element('div', array('class' => $class), + Element('tt', array('class' => 'prefix'), $prefix) + . " $line") . "\n"; + } + } - $this->lcs = 0; - $this->seq[0]= $yoff - 1; - $this->in_seq = array(); - $ymids[0] = array(); - - $numer = $xlim - $xoff + $nchunks - 1; - $x = $xoff; - for ($chunk = 0; $chunk < $nchunks; $chunk++) { - if ($chunk > 0) - for ($i = 0; $i <= $this->lcs; $i++) - $ymids[$i][$chunk-1] = $this->seq[$i]; + function _context($lines) { + $this->_lines($lines, 'context'); + } + function _deleted($lines) { + $this->_lines($lines, 'deleted', '-', 'del'); + } + function _added($lines) { + $this->_lines($lines, 'added', '+', 'ins'); + } - $x1 = $xoff + (int)(($numer + ($xlim-$xoff)*$chunk) / $nchunks); - for ( ; $x < $x1; $x++) { - $line = $flip ? $this->yv[$x] : $this->xv[$x]; - if (empty($ymatches[$line])) - continue; - $matches = $ymatches[$line]; - reset($matches); - while (list ($junk, $y) = each($matches)) - if (empty($this->in_seq[$y])) - { - $k = $this->_lcs_pos($y); - USE_ASSERTS && assert($k > 0); - $ymids[$k] = $ymids[$k-1]; - break; - } - while (list ($junk, $y) = each($matches)) - { - if ($y > $this->seq[$k-1]) - { - USE_ASSERTS && assert($y < $this->seq[$k]); - // Optimization: this is a common case: - // next match is just replacing previous match. - $this->in_seq[$this->seq[$k]] = false; - $this->seq[$k] = $y; - $this->in_seq[$y] = 1; - } - else if (empty($this->in_seq[$y])) - { - $k = $this->_lcs_pos($y); - USE_ASSERTS && assert($k > 0); - $ymids[$k] = $ymids[$k-1]; - } - } + function _pack_in_span($chars, $elem) { + $end_span = ""; + $packed = ''; + foreach ($chars as $c) { + if ($c == "\n") { + $packed .= $end_span; + $end_span = ""; } + elseif (!$end_span) { + $packed .= "<$elem>"; + $end_span = ""; + } + $packed .= htmlspecialchars($c); } - - $seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff); - $ymid = $ymids[$this->lcs]; - for ($n = 0; $n < $nchunks - 1; $n++) - { - $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks); - $y1 = $ymid[$n] + 1; - $seps[] = $flip ? array($y1, $x1) : array($x1, $y1); - } - $seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim); - - return array($this->lcs, $seps); - } - - function _lcs_pos ($ypos) - { - $end = $this->lcs; - if ($end == 0 || $ypos > $this->seq[$end]) - { - $this->seq[++$this->lcs] = $ypos; - $this->in_seq[$ypos] = 1; - return $this->lcs; - } - - $beg = 1; - while ($beg < $end) - { - $mid = (int)(($beg + $end) / 2); - if ( $ypos > $this->seq[$mid] ) - $beg = $mid + 1; - else - $end = $mid; - } - - USE_ASSERTS && assert($ypos != $this->seq[$end]); - - $this->in_seq[$this->seq[$end]] = false; - $this->seq[$end] = $ypos; - $this->in_seq[$ypos] = 1; - return $end; - } - - /* Find LCS of two sequences. - * - * The results are recorded in the vectors $this->{x,y}changed[], by - * storing a 1 in the element for each line that is an insertion - * or deletion (ie. is not in the LCS). - * - * The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1. - * - * Note that XLIM, YLIM are exclusive bounds. - * All line numbers are origin-0 and discarded lines are not counted. - */ - function _compareseq ($xoff, $xlim, $yoff, $ylim) - { - // Slide down the bottom initial diagonal. - while ($xoff < $xlim && $yoff < $ylim - && $this->xv[$xoff] == $this->yv[$yoff]) - { - ++$xoff; - ++$yoff; - } - - // Slide up the top initial diagonal. - while ($xlim > $xoff && $ylim > $yoff - && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) - { - --$xlim; - --$ylim; - } - - if ($xoff == $xlim || $yoff == $ylim) - $lcs = 0; - else - { - // This is ad hoc but seems to work well. - //$nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5); - //$nchunks = max(2,min(8,(int)$nchunks)); - $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1; - list ($lcs, $seps) - = $this->_diag($xoff,$xlim,$yoff, $ylim,$nchunks); - } - - if ($lcs == 0) - { - // X and Y sequences have no common subsequence: - // mark all changed. - while ($yoff < $ylim) - $this->ychanged[$this->yind[$yoff++]] = 1; - while ($xoff < $xlim) - $this->xchanged[$this->xind[$xoff++]] = 1; - } - else - { - // Use the partitions to split this problem into subproblems. - reset($seps); - $pt1 = $seps[0]; - while ($pt2 = next($seps)) - { - $this->_compareseq ($pt1[0], $pt2[0], $pt1[1], $pt2[1]); - $pt1 = $pt2; - } - } - } - - /* 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). - */ - 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]'); - } - } - } -} - -/** - * Class representing a diff between two files. - */ -class WikiDiff -{ - var $edits; - - /** - * Compute diff between files (or deserialize serialized WikiDiff.) - */ - function WikiDiff($from_lines = false, $to_lines = false) - { - if ($from_lines && $to_lines) - { - $compute = new _WikiDiffEngine($from_lines, $to_lines); - $this->edits = $compute->edits; - } - else if ($from_lines) - { - // $from_lines is not really from_lines, but rather - // a serialized WikiDiff. - $this->edits = unserialize($from_lines); - } - else - { - $this->edits = array(); - } - } - - /** - * Compute reversed WikiDiff. - * - * SYNOPSIS: - * - * $diff = new WikiDiff($lines1, $lines2); - * $rev = $diff->reverse($lines1); - * - * // reconstruct $lines1 from $lines2: - * $out = $rev->apply($lines2); - */ - function reverse ($from_lines) - { - $x = 0; - $rev = new WikiDiff; - - for ( reset($this->edits); - $edit = current($this->edits); - next($this->edits) ) - { - if (is_array($edit)) - { // Was an add, turn it into a delete. - $nadd = sizeof($edit); - USE_ASSERTS && assert ($nadd > 0); - $edit = -$nadd; - } - else if ($edit > 0) - { - // Was a copy --- just pass it through. } - $x += $edit; - } - else if ($edit < 0) - { // Was a delete, turn it into an add. - $ndelete = -$edit; - $edit = array(); - while ($ndelete-- > 0) - $edit[] = "" . $from_lines[$x++]; - } - else - trigger_error("assertion error", E_USER_ERROR); - - $rev->edits[] = $edit; - } - - return $rev; - } - - /** - * Compose (concatenate) WikiDiffs. - * - * SYNOPSIS: - * - * $diff1 = new WikiDiff($lines1, $lines2); - * $diff2 = new WikiDiff($lines2, $lines3); - * $comp = $diff1->compose($diff2); - * - * // reconstruct $lines3 from $lines1: - * $out = $comp->apply($lines1); - */ - function compose ($that) - { - reset($this->edits); - reset($that->edits); - - $comp = new WikiDiff; - $left = current($this->edits); - $right = current($that->edits); - - while ($left || $right) - { - if (!is_array($left) && $left < 0) - { // Left op is a delete. - $newop = $left; - $left = next($this->edits); - } - else if (is_array($right)) - { // Right op is an add. - $newop = $right; - $right = next($that->edits); - } - else if (!$left || !$right) - trigger_error("assertion error", E_USER_ERROR); - else if (!is_array($left) && $left > 0) - { // Left op is a copy. - if ($left <= abs($right)) - { - $newop = $right > 0 ? $left : -$left; - $right -= $newop; - if ($right == 0) - $right = next($that->edits); - $left = next($this->edits); - } - else - { - $newop = $right; - $left -= abs($right); - $right = next($that->edits); - } - } - else - { // Left op is an add. - assert('is_array($left)'); - $nleft = sizeof($left); - if ($nleft <= abs($right)) - { - if ($right > 0) - { // Right op is copy - $newop = $left; - $right -= $nleft; - } - else // Right op is delete - { - $newop = false; - $right += $nleft; - } - if ($right == 0) - $right = next($that->edits); - $left = next($this->edits); - } - else - { - unset($newop); - if ($right > 0) - for ($i = 0; $i < $right; $i++) - $newop[] = $left[$i]; - - $tmp = array(); - for ($i = abs($right); $i < $nleft; $i++) - $tmp[] = $left[$i]; - $left = $tmp; - $right = next($that->edits); - } - } - if (!$op) - { - $op = $newop; - continue; - } - if (! $newop) - continue; - - if (is_array($op) && is_array($newop)) - { - // Both $op and $newop are adds. - for ($i = 0; $i < sizeof($newop); $i++) - $op[] = $newop[$i]; - } - else if (($op > 0 && $newop > 0) || ($op < 0 && $newop < 0)) - { // $op and $newop are both either deletes or copies. - $op += $newop; - } - else - { - $comp->edits[] = $op; - $op = $newop; - } - } - if ($op) - $comp->edits[] = $op; - - return $comp; - } - - /* Debugging only: - function _dump () - { - echo "
    "; - for (reset($this->edits); - $edit = current($this->edits); - next($this->edits)) - { - echo "
  1. "; - if ($edit > 0) - echo "Copy $edit"; - else if ($edit < 0) - echo "Delete " . -$edit; - else if (is_array($edit)) - { - echo "Add " . sizeof($edit) . "
      "; - for ($i = 0; $i < sizeof($edit); $i++) - echo "
    • " . htmlspecialchars($edit[$i]); - echo "
    "; - } - else - trigger_error("assertion error", E_USER_ERROR); - } - echo "
"; - } - */ - - /** - * Apply a WikiDiff to a set of lines. - * - * SYNOPSIS: - * - * $diff = new WikiDiff($lines1, $lines2); - * - * // reconstruct $lines2 from $lines1: - * $out = $diff->apply($lines1); - */ - function apply ($from_lines) - { - $x = 0; - $xlim = sizeof($from_lines); - - for ( reset($this->edits); - $edit = current($this->edits); - next($this->edits) ) - { - if (is_array($edit)) - { - reset($edit); - while (list ($junk, $line) = each($edit)) - $output[] = $line; - } - else if ($edit > 0) - while ($edit--) - $output[] = $from_lines[$x++]; - else - $x += -$edit; - } - if ($x != $xlim) - ExitWiki(sprintf(gettext ("WikiDiff::apply: line count mismatch: %s != %s"), $x, $xlim)); - return $output; - } - - /** - * Serialize a WikiDiff. - * - * SYNOPSIS: - * - * $diff = new WikiDiff($lines1, $lines2); - * $string = $diff->serialize; - * - * // recover WikiDiff from serialized version: - * $diff2 = new WikiDiff($string); - */ - function serialize () - { - return serialize($this->edits); - } - - /** - * Return true if two files were equal. - */ - function isEmpty () - { - if (sizeof($this->edits) > 1) - return false; - if (sizeof($this->edits) == 0) - return true; - // Test for: only edit is a copy. - return !is_array($this->edits[0]) && $this->edits[0] > 0; - } - - /** - * Compute the length of the Longest Common Subsequence (LCS). - * - * This is mostly for diagnostic purposed. - */ - function lcs () - { - $lcs = 0; - for (reset($this->edits); - $edit = current($this->edits); - next($this->edits)) - { - if (!is_array($edit) && $edit > 0) - $lcs += $edit; - } - return $lcs; - } + return $packed . $end_span; + } + + function _split_to_chars($lines) { + // Split into characters --- there must be a better way ... + $joined = implode("\n", $lines); + $split = array(); + for ($i = 0; $i < strlen($joined); $i++) + $split[$i] = $joined[$i]; + return $split; + } - /** - * Check a WikiDiff for validity. - * - * This is here only for debugging purposes. - */ - function _check ($from_lines, $to_lines) - { - $test = $this->apply($from_lines); - if (serialize($test) != serialize($to_lines)) - ExitWiki(gettext ("WikiDiff::_check: failed")); - - reset($this->edits); - $prev = current($this->edits); - $prevtype = is_array($prev) ? 'a' : ($prev > 0 ? 'c' : 'd'); + + function _changed($orig, $final) { + // Compute character-wise diff in changed region. + $diff = new Diff($this->_split_to_chars($orig), + $this->_split_to_chars($final)); + + $orig = $final = ''; + foreach ($diff->edits as $edit) { + switch ($edit->type) { + case 'copy': + $packed = implode('', $edit->orig); + $orig .= $packed; + $final .= $packed; + break; + case 'add': + $final .= $this->_pack_in_span($edit->final, 'ins'); + break; + case 'delete': + $orig .= $this->_pack_in_span($edit->orig, 'del'); + break; + case 'change': + $orig .= $this->_pack_in_span($edit->orig, 'del'); + $final .= $this->_pack_in_span($edit->final, 'ins'); + break; + } + } - while ($edit = next($this->edits)) - { - $type = is_array($edit) ? 'a' : ($edit > 0 ? 'c' : 'd'); - if ( $prevtype == $type ) - ExitWiki(gettext ("WikiDiff::_check: edit sequence is non-optimal")); - $prevtype = $type; - } - $lcs = $this->lcs(); - printf ("" . gettext ("WikiDiff Okay: LCS = %s") . "\n", $lcs); - } + $this->_lines(explode("\n", $orig), 'changed', '-'); + $this->_lines(explode("\n", $final), 'changed', '+'); + } } - -/** - * A class to format a WikiDiff as HTML. - * - * Usage: - * - * $diff = new WikiDiff($lines1, $lines2); // compute diff. - * - * $fmt = new WikiDiffFormatter; - * echo $fmt->format($diff, $lines1); // Output HTMLified standard diff. - * - * or to output reverse diff (diff's that would take $lines2 to $lines1): - * - * $fmt = new WikiDiffFormatter('reversed'); - * echo $fmt->format($diff, $lines1); - */ -class WikiDiffFormatter +class TableUnifiedDiffFormatter extends HtmlUnifiedDiffFormatter { - var $context_lines; - var $do_reverse_diff; - var $context_prefix, $deletes_prefix, $adds_prefix; - - function WikiDiffFormatter ($reverse = false) - { - $this->do_reverse_diff = $reverse; - $this->context_lines = 0; - $this->context_prefix = '  '; - $this->deletes_prefix = '< '; - $this->adds_prefix = '> '; - } + function TableUnifiedDiffFormatter($context_lines = 4) { + $this->HtmlUnifiedDiffFormatter($context_lines); + } - function format ($diff, $from_lines) - { - return Element('table', - array('width' => '100%', - 'bgcolor' => 'black', - 'cellspacing' => 2, - 'cellpadding' => 2, - 'border' => 0), - $this->_format($diff->edits, $from_lines)); - } + function _start_diff() { + echo "\n\n"; + } + function _end_diff() { + echo "
\n"; + } - function _format ($edits, $from_lines) - { - $rows = ''; - $x = 0; $y = 0; - $xlim = sizeof($from_lines); - - reset($edits); - while ($edit = current($edits)) - { - if (!is_array($edit) && $edit >= 0) - { // Edit op is a copy. - $ncopy = $edit; - } - else - { - $ncopy = 0; - if (empty($hunk)) - { - // Start of an output hunk. - $xoff = max(0, $x - $this->context_lines); - $yoff = $xoff + $y - $x; - if ($xoff < $x) - { - // Get leading context. - $context = array(); - for ($i = $xoff; $i < $x; $i++) - $context[] = $from_lines[$i]; - $hunk['c'] = $context; - } - } - if (is_array($edit)) - { // Edit op is an add. - $y += sizeof($edit); - $hunk[$this->do_reverse_diff ? 'd' : 'a'] = $edit; - } - else - { // Edit op is a delete - $deletes = array(); - while ($edit++ < 0) - $deletes[] = $from_lines[$x++]; - $hunk[$this->do_reverse_diff ? 'a' : 'd'] = $deletes; - } - } - - $next = next($edits); - if (!empty($hunk)) - { - if ( !$next || $ncopy > 2 * $this->context_lines) - { - // End of an output hunk. - $hunks[] = $hunk; - unset($hunk); - - $xend = min($x + $this->context_lines, $xlim); - if ($x < $xend) - { - // Get trailing context. - $context = array(); - for ($i = $x; $i < $xend; $i++) - $context[] = $from_lines[$i]; - $hunks[] = array('c' => $context); - } - - $xlen = $xend - $xoff; - $ylen = $xend + $y - $x - $yoff; - $xbeg = $xlen ? $xoff + 1 : $xoff; - $ybeg = $ylen ? $yoff + 1 : $yoff; - - if ($this->do_reverse_diff) - list ($xbeg, $xlen, $ybeg, $ylen) - = array($ybeg, $ylen, $xbeg, $xlen); - - $rows .= $this->_emit_diff($xbeg,$xlen,$ybeg,$ylen, $hunks); - unset($hunks); - } - else if ($ncopy) - { - $hunks[] = $hunk; - - // Copy context. - $context = array(); - for ($i = $x; $i < $x + $ncopy; $i++) - $context[] = $from_lines[$i]; - $hunk = array('c' => $context); - } - } - - $x += $ncopy; - $y += $ncopy; - } - return $rows; - } - - function _emit_lines($lines, $prefix, $color) - { - $html = ''; - $prefix = Element('td', array('class' => 'diff-notation', 'width' => "1%"), $prefix); - reset($lines); - while (list ($junk, $line) = each($lines)) - { - $line = rtrim($line); - $line = empty($line) ? ' ' : htmlspecialchars($line); - $html .= Element('tr', array('valign' => 'top'), - $prefix . Element('td', array('class' => $color), - Element('tt', $line))); - } - return $html; - } - - function _emit_diff ($xbeg,$xlen,$ybeg,$ylen,$hunks) - { - $header = Element('tr', array('bgcolor' => '#cccccc'), - Element('td', array('colspan' => 2), - QElement('tt', - $this->_diff_header($xbeg, $xlen, $ybeg, $ylen)))); - - $prefix = array('c' => $this->context_prefix, - 'a' => $this->adds_prefix, - 'd' => $this->deletes_prefix); - $color = array('c' => 'diff-unchanged', - 'a' => 'diff-added', - 'd' => 'diff-deleted'); - - $diff = ''; - for (reset($hunks); $hunk = current($hunks); next($hunks)) - { - if (!empty($hunk['c'])) - $diff .= $this->_emit_lines($hunk['c'], - $this->context_prefix, 'diff-unchanged'); - if (!empty($hunk['d'])) - $diff .= $this->_emit_lines($hunk['d'], - $this->deletes_prefix, 'diff-deleted'); - if (!empty($hunk['a'])) - $diff .= $this->_emit_lines($hunk['a'], - $this->adds_prefix, 'diff-added'); - } - - - return Element('tr', Element('td', - Element('table', - array('width' => '100%', - 'bgcolor' => 'white', - 'cellspacing' => 0, - 'cellpadding' => 1, - 'border' => 0), - $header. $diff))); - - } + function _start_block($header) { + echo "\n"; + echo Element('tr', + Element('td', array('colspan' => 2), + QElement('tt', $header))) . "\n"; + } - function _diff_header ($xbeg,$xlen,$ybeg,$ylen) - { - $what = $xlen ? ($ylen ? 'c' : 'd') : 'a'; - $xlen = $xlen > 1 ? "," . ($xbeg + $xlen - 1) : ''; - $ylen = $ylen > 1 ? "," . ($ybeg + $ylen - 1) : ''; + function _end_block() { + echo "
\n"; + } - return "$xbeg$xlen$what$ybeg$ylen"; - } + function _lines($lines, $class, $prefix = ' ', $elem = false) { + $prefix = Element('td', array('class' => 'prefix', 'width' => "1%"), $prefix); + foreach ($lines as $line) { + if (! trim($line)) + $line = ' '; + elseif ($elem) + $line = QElement($elem, $line); + + echo Element('tr', array('valign' => 'top'), + $prefix . Element('td', array('class' => $class), + $line)) . "\n"; + } + } } -/** - * A class to format a WikiDiff as a pretty HTML unified diff. - * - * Usage: - * - * $diff = new WikiDiff($lines1, $lines2); // compute diff. - * - * $fmt = new WikiUnifiedDiffFormatter; - * echo $fmt->format($diff, $lines1); // Output HTMLified unified diff. - */ -class WikiUnifiedDiffFormatter extends WikiDiffFormatter -{ - function WikiUnifiedDiffFormatter ($reverse = false, $context_lines = 3) - { - $this->do_reverse_diff = $reverse; - $this->context_lines = $context_lines; - $this->context_prefix = ' '; - $this->deletes_prefix = '-'; - $this->adds_prefix = '+'; - } - function _diff_header ($xbeg,$xlen,$ybeg,$ylen) - { - $xlen = $xlen == 1 ? '' : ",$xlen"; - $ylen = $ylen == 1 ? '' : ",$ylen"; - - return "@@ -$xbeg$xlen +$ybeg$ylen @@"; - } -} - - - ///////////////////////////////////////////////////////////////// function PageInfoRow ($pagename, $label, $rev) @@ -1136,15 +270,19 @@ function showDiff ($dbi, $request) { if ($new && $old) { - $diff = new WikiDiff($old->getContent(), $new->getContent()); + $diff = new Diff($old->getContent(), $new->getContent()); + if ($diff->isEmpty()) { $html .= Element('hr'); $html .= QElement('p', '[' . gettext ("Versions are identical") . ']'); } else { - //$fmt = new WikiDiffFormatter; - $fmt = new WikiUnifiedDiffFormatter; - $html .= $fmt->format($diff, $old->getContent()); + // New CSS formatted unified diffs (ugly in NS4). + $fmt = new HtmlUnifiedDiffFormatter; + + // Use this for old table-formatted diffs. + //$fmt = new TableUnifiedDiffFormatter; + $html .= $fmt->format($diff); } } diff --git a/lib/difflib.php b/lib/difflib.php new file mode 100644 index 000000000..8efd179d8 --- /dev/null +++ b/lib/difflib.php @@ -0,0 +1,756 @@ + +// You may copy this code freely under the conditions of the GPL. +// + +// FIXME: possibly remove assert()'s for production version? + +// PHP3 does not have assert() +define('USE_ASSERTS', function_exists('assert')); + +class _DiffOp { + var $type; + var $orig; + var $final; + + function _DiffOp () { + trigger_error("pure virtual", E_USER_ERROR); + } + + function reverse() { + trigger_error("pure virtual", E_USER_ERROR); + } +} + +class _DiffOp_Copy extends _DiffOp { + var $type = 'copy'; + + function _DiffOp_Copy ($lines) { + $this->orig = $lines; + $this->final = &$this->orig; + } + + function reverse() { + return $this; + } +} + +class _DiffOp_Delete extends _DiffOp { + var $type = 'delete'; + + function _DiffOp_Delete ($lines) { + $this->orig = $lines; + $this->final = false; + } + + function reverse() { + return new _DiffOp_Add($this->orig); + } +} + +class _DiffOp_Add extends _DiffOp { + var $type = 'add'; + + function _DiffOp_Add ($lines) { + $this->final = $lines; + $this->orig = false; + } + + function reverse() { + return new _DiffOp_Delete($this->final); + } +} + +class _DiffOp_Change extends _DiffOp { + var $type = 'change'; + + function _DiffOp_Change ($orig, $final) { + $this->orig = $orig; + $this->final = $final; + } + + function reverse() { + return new _DiffOp_Change($this->final, $this->orig); + } +} + + +/** + * Class used internally by Diff to actually compute the diffs. + * + * The algorithm used here is mostly lifted from the perl module + * Algorithm::Diff (version 1.06) by Ned Konz, which is available at: + * http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip + * + * More ideas are taken from: + * http://www.ics.uci.edu/~eppstein/161/960229.html + * + * Some ideas are (and a bit of code) are from from analyze.c, from GNU + * diffutils-2.7, which can be found at: + * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz + * + * Finally, some ideas (subdivision by NCHUNKS > 2, and some optimizations) + * are my own. + */ +class _DiffEngine +{ + var $xv = array(), $yv = array(); + + function diff ($from_lines, $to_lines) { + $n_from = sizeof($from_lines); + $n_to = sizeof($to_lines); + + + // 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[$from_lines[$xi]] = 1; + for ($yi = $skip; $yi < $n_to - $endskip; $yi++) { + $line = $to_lines[$yi]; + if ( ($this->ychanged[$yi] = empty($xhash[$line])) ) + continue; + $yhash[$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[$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; + } + + + /* Divide the Largest Common Subsequence (LCS) of the sequences + * [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally + * sized segments. + * + * Returns (LCS, PTS). LCS is the length of the LCS. PTS is an + * array of NCHUNKS+1 (X, Y) indexes giving the diving points between + * sub sequences. The first sub-sequence is contained in [X0, X1), + * [Y0, Y1), the second in [X1, X2), [Y1, Y2) and so on. Note + * that (X0, Y0) == (XOFF, YOFF) and + * (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM). + * + * This function assumes that the first lines of the specified portions + * of the two files do not match, and likewise that the last lines do not + * match. The caller must trim matching lines from the beginning and end + * of the portions it is going to specify. + */ + function _diag ($xoff, $xlim, $yoff, $ylim, $nchunks) { + $flip = false; + + if ($xlim - $xoff > $ylim - $yoff) { + // Things seems faster (I'm not sure I understand why) + // when the shortest sequence in X. + $flip = true; + list ($xoff, $xlim, $yoff, $ylim) + = array( $yoff, $ylim, $xoff, $xlim); + } + + if ($flip) + for ($i = $ylim - 1; $i >= $yoff; $i--) + $ymatches[$this->xv[$i]][] = $i; + else + for ($i = $ylim - 1; $i >= $yoff; $i--) + $ymatches[$this->yv[$i]][] = $i; + + $this->lcs = 0; + $this->seq[0]= $yoff - 1; + $this->in_seq = array(); + $ymids[0] = array(); + + $numer = $xlim - $xoff + $nchunks - 1; + $x = $xoff; + for ($chunk = 0; $chunk < $nchunks; $chunk++) { + if ($chunk > 0) + for ($i = 0; $i <= $this->lcs; $i++) + $ymids[$i][$chunk-1] = $this->seq[$i]; + + $x1 = $xoff + (int)(($numer + ($xlim-$xoff)*$chunk) / $nchunks); + for ( ; $x < $x1; $x++) { + $line = $flip ? $this->yv[$x] : $this->xv[$x]; + if (empty($ymatches[$line])) + continue; + $matches = $ymatches[$line]; + reset($matches); + while (list ($junk, $y) = each($matches)) + if (empty($this->in_seq[$y])) { + $k = $this->_lcs_pos($y); + USE_ASSERTS && assert($k > 0); + $ymids[$k] = $ymids[$k-1]; + break; + } + while (list ($junk, $y) = each($matches)) { + if ($y > $this->seq[$k-1]) { + USE_ASSERTS && assert($y < $this->seq[$k]); + // Optimization: this is a common case: + // next match is just replacing previous match. + $this->in_seq[$this->seq[$k]] = false; + $this->seq[$k] = $y; + $this->in_seq[$y] = 1; + } + else if (empty($this->in_seq[$y])) { + $k = $this->_lcs_pos($y); + USE_ASSERTS && assert($k > 0); + $ymids[$k] = $ymids[$k-1]; + } + } + } + } + + $seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff); + $ymid = $ymids[$this->lcs]; + for ($n = 0; $n < $nchunks - 1; $n++) { + $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks); + $y1 = $ymid[$n] + 1; + $seps[] = $flip ? array($y1, $x1) : array($x1, $y1); + } + $seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim); + + return array($this->lcs, $seps); + } + + function _lcs_pos ($ypos) { + $end = $this->lcs; + if ($end == 0 || $ypos > $this->seq[$end]) { + $this->seq[++$this->lcs] = $ypos; + $this->in_seq[$ypos] = 1; + return $this->lcs; + } + + $beg = 1; + while ($beg < $end) { + $mid = (int)(($beg + $end) / 2); + if ( $ypos > $this->seq[$mid] ) + $beg = $mid + 1; + else + $end = $mid; + } + + USE_ASSERTS && assert($ypos != $this->seq[$end]); + + $this->in_seq[$this->seq[$end]] = false; + $this->seq[$end] = $ypos; + $this->in_seq[$ypos] = 1; + return $end; + } + + /* Find LCS of two sequences. + * + * The results are recorded in the vectors $this->{x,y}changed[], by + * storing a 1 in the element for each line that is an insertion + * or deletion (ie. is not in the LCS). + * + * The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1. + * + * Note that XLIM, YLIM are exclusive bounds. + * All line numbers are origin-0 and discarded lines are not counted. + */ + function _compareseq ($xoff, $xlim, $yoff, $ylim) { + // Slide down the bottom initial diagonal. + while ($xoff < $xlim && $yoff < $ylim + && $this->xv[$xoff] == $this->yv[$yoff]) { + ++$xoff; + ++$yoff; + } + + // Slide up the top initial diagonal. + while ($xlim > $xoff && $ylim > $yoff + && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) { + --$xlim; + --$ylim; + } + + if ($xoff == $xlim || $yoff == $ylim) + $lcs = 0; + else { + // This is ad hoc but seems to work well. + //$nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5); + //$nchunks = max(2,min(8,(int)$nchunks)); + $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1; + list ($lcs, $seps) + = $this->_diag($xoff,$xlim,$yoff, $ylim,$nchunks); + } + + if ($lcs == 0) { + // X and Y sequences have no common subsequence: + // mark all changed. + while ($yoff < $ylim) + $this->ychanged[$this->yind[$yoff++]] = 1; + while ($xoff < $xlim) + $this->xchanged[$this->xind[$xoff++]] = 1; + } + else { + // Use the partitions to split this problem into subproblems. + reset($seps); + $pt1 = $seps[0]; + while ($pt2 = next($seps)) { + $this->_compareseq ($pt1[0], $pt2[0], $pt1[1], $pt2[1]); + $pt1 = $pt2; + } + } + } + + /* 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). + */ + 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]'); + } + } + } +} + +/** + * Class representing a diff between two files. + */ +class Diff +{ + var $edits; + + /** + * Compute diff between lists of strings. + */ + function Diff($from_lines, $to_lines) { + $eng = new _DiffEngine; + $this->edits = $eng->diff($from_lines, $to_lines); + //$this->_check($from_lines, $to_lines); + } + + /** + * Compute reversed Diff. + * + * SYNOPSIS: + * + * $diff = new Diff($lines1, $lines2); + * $rev = $diff->reverse(); + * + * // reconstruct $lines1 from $lines2: + * $out = $rev->apply($lines2); + */ + function reverse () { + $rev = $this; + $rev->edits = array(); + foreach ($this->edits as $edit) { + $rev->edits[] = $edit->reverse(); + } + return $rev; + } + + /** + * Return true if two files were equal. + */ + function isEmpty () { + foreach ($this->edits as $edit) { + if ($edit->type != 'copy') + return false; + } + return true; + } + + /** + * Compute the length of the Longest Common Subsequence (LCS). + * + * This is mostly for diagnostic purposed. + */ + function lcs () { + $lcs = 0; + foreach ($this->edits as $edit) { + if ($edit->type == 'copy') + $lcs += sizeof($edit->orig); + } + return $lcs; + } + + /** + * Get the original set of lines. + */ + function orig() { + $lines = array(); + + foreach ($this->edits as $edit) { + if ($edit->orig) + array_splice($lines, sizeof($lines), 0, $edit->orig); + } + return $lines; + } + + /** + * Get the final set of lines. + */ + function final() { + $lines = array(); + + foreach ($this->edits as $edit) { + if ($edit->final) + array_splice($lines, sizeof($lines), 0, $edit->final); + } + return $lines; + } + + /** + * Check a Diff for validity. + * + * This is here only for debugging purposes. + */ + function _check ($from_lines, $to_lines) { + if (serialize($from_lines) != serialize($this->orig())) + trigger_error("Reconstructed original doesn't match", E_USER_ERROR); + if (serialize($to_lines) != serialize($this->final())) + trigger_error("Reconstructed final doesn't match", E_USER_ERROR); + + $rev = $this->reverse(); + if (serialize($to_lines) != serialize($rev->orig())) + trigger_error("Reversed original doesn't match", E_USER_ERROR); + if (serialize($from_lines) != serialize($rev->final())) + trigger_error("Reversed final doesn't match", E_USER_ERROR); + + + $prevtype = 'none'; + foreach ($this->edits as $edit) { + if ( $prevtype == $edit->type ) + trigger_error("Edit sequence is non-optimal", E_USER_ERROR); + $prevtype = $edit->type; + } + + $lcs = $this->lcs(); + trigger_error("Diff okay: LCS = $lcs", E_USER_NOTICE); + } +} + +class DiffFormatter +{ + var $leading_context_lines = 0; + var $trailing_context_lines = 0; + + function format($diff) { + + $xi = $yi = 1; + $block = false; + $context = array(); + + $nlead = $this->leading_context_lines; + $ntrail = $this->trailing_context_lines; + + ob_start(); + $this->_start_diff(); + + foreach ($diff->edits as $edit) { + if ($edit->type == 'copy') { + if (is_array($block)) { + if (sizeof($edit->orig) <= $nlead + $ntrail) { + $block[] = $edit; + } + else{ + if ($ntrail) { + $context = array_slice($edit->orig, 0, $ntrail); + $block[] = new _DiffOp_Copy($context); + } + $this->_block($x0, $ntrail + $xi - $x0, + $y0, $ntrail + $yi - $y0, + $block); + $block = false; + } + } + $context = $edit->orig; + } + else { + if (! is_array($block)) { + $context = array_slice($context, sizeof($context) - $nlead); + $x0 = $xi - sizeof($context); + $y0 = $yi - sizeof($context); + $block = array(); + if ($context) + $block[] = new _DiffOp_Copy($context); + } + $block[] = $edit; + } + + if ($edit->orig) + $xi += sizeof($edit->orig); + if ($edit->final) + $yi += sizeof($edit->final); + } + + if (is_array($block)) + $this->_block($x0, $xi - $x0, + $y0, $yi - $y0, + $block); + + $this->_end_diff(); + + $val = ob_get_contents(); + ob_end_clean(); + return $val; + } + + function _block($xbeg, $xlen, $ybeg, $ylen, &$edits) { + $this->_start_block($this->_block_header($xbeg, $xlen, $ybeg, $ylen)); + foreach ($edits as $edit) { + if ($edit->type == 'copy') + $this->_context($edit->orig); + elseif ($edit->type == 'add') + $this->_added($edit->final); + elseif ($edit->type == 'delete') + $this->_deleted($edit->orig); + elseif ($edit->type == 'change') + $this->_changed($edit->orig, $edit->final); + else + trigger_error("Unknown edit type", E_USER_ERROR); + } + $this->_end_block(); + } + + function _start_diff() { + } + + function _end_diff() { + } + + function _block_header($xbeg, $xlen, $ybeg, $ylen) { + if ($xlen > 1) + $xbeg .= "," . ($xbeg + $xlen - 1); + if ($ylen > 1) + $ybeg .= "," . ($ybeg + $ylen - 1); + + return $xbeg . ($xlen ? ($ylen ? 'c' : 'd') : 'a') . $ybeg; + } + + function _start_block($header) { + echo $header; + } + + function _end_block() { + } + + function _lines($lines, $prefix = ' ') { + foreach ($lines as $line) + echo "$prefix $line\n"; + } + + function _context($lines) { + $this->_lines($lines); + } + + function _added($lines) { + $this->_lines($lines, ">"); + } + function _deleted($lines) { + $this->_lines($lines, "<"); + } + + function _changed($orig, $final) { + $this->_deleted($orig); + echo "---\n"; + $this->_added($final); + } +} + +class UnifiedDiffFormatter extends DiffFormatter +{ + function UnifiedDiffFormatter($context_lines = 4) { + $this->leading_context_lines = $context_lines; + $this->trailing_context_lines = $context_lines; + } + + function _block_header($xbeg, $xlen, $ybeg, $ylen) { + if ($xlen != 1) + $xbeg .= "," . $xlen; + if ($ylen != 1) + $ybeg .= "," . $ylen; + return "@@ -$xbeg +$ybeg @@"; + } + + function _added($lines) { + $this->_lines($lines, "+"); + } + function _deleted($lines) { + $this->_lines($lines, "-"); + } + function _changed($orig, $final) { + $this->_deleted($orig); + $this->_added($final); + } +} + +// Local Variables: +// mode: php +// tab-width: 8 +// c-basic-offset: 4 +// c-hanging-comment-ender-p: nil +// indent-tabs-mode: nil +// End: +?> diff --git a/phpwiki.css b/phpwiki.css index 0da238ca1..eee3792db 100644 --- a/phpwiki.css +++ b/phpwiki.css @@ -224,19 +224,28 @@ div.transclusion { padding-bottom: 0px; margin: 0.5ex 0px; } - -.diff-added { - background: #cfc; -} -.diff-deleted { - background: #fcc; -} -.diff-unchanged { - background: white; -} -.diff-notation { - background: #ccc; -} + +/* Diff output */ +.diff .block { + padding: 0.5ex 0.5em; + margin: 0.5ex 0; + border: 0.1px; /* hack for NS4 to get background color filled in whole div */ +} +.diff .block tt { font-weight: bold; } + +.diff .block div { position: relative; padding-left: 1.5em; } +.diff .prefix { position: absolute; left: 0.5em; top: 0; } + +.diff .block { background: #ccc; } + +.diff .context { background: white; } +.diff .deleted { background: #fee; } +.diff .added { background: #efe; } +.diff .changed { background: #ffb; } + +.diff del { background: #fbb; font-weight: bold; text-decoration: none; } +.diff ins { background: #bfb; font-weight: bold; text-decoration: none; } + /* For emacs users * -- 2.45.0