diff options
Diffstat (limited to 'includes/diff.php')
| -rw-r--r-- | includes/diff.php | 1027 |
1 files changed, 1027 insertions, 0 deletions
diff --git a/includes/diff.php b/includes/diff.php new file mode 100644 index 0000000..8b57d32 --- /dev/null +++ b/includes/diff.php @@ -0,0 +1,1027 @@ +<?php +/** + * $Header$ + * + * A PHP diff engine for phpwiki. + * + * Copyright (c) 2004 bitweaver.org + * Copyright (c) 2003 tikwiki.org + * Copyright (c) 2000 Geoffrey T. Dairiki <dairiki@dairiki.org> + * All Rights Reserved. See below for details and a complete list of authors. + * Licensed under the GNU LESSER GENERAL PUBLIC LICENSE. See http://www.gnu.org/copyleft/lesser.html for details + * + * $Id$ + * @package util + */ + +/** + * required setup + */ +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. + * @package util + * @subpackage WikiDiffEngine + */ +class _WikiDiffEngine +{ + public $edits; // List of editing operation to convert XV to YV. + public $xv = array(), $yv = array(); + public $xchanged, $ychanged; + function _WikiDiffEngine ($from_lines, $to_lines) + { + $n_from = sizeof($from_lines); + $n_to = sizeof($to_lines); + $endskip = 0; + // Ignore differences in line endings + for ($i = 0; $i < $n_from; $i++) + { + $from_lines[$i] = rtrim($from_lines[$i]); + } + for ($i = 0; $i < $n_to; $i++) + { + $to_lines[$i] = rtrim($to_lines[$i]); + } + // 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(); + // 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); + // Find adds. + if (isset($this->ychanged[$y]) && $this->ychanged[$y]) + { + $adds = array(); + while ($y < $n_to && $this->ychanged[$y]) + $adds[] = "" . $ylines[$y++]; + $this->edits[] = $adds; + } + } + if ($endskip != 0) + $this->edits[] = $endskip; + } + /* 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++) + { + $matches = $ymatches[$flip ? $this->yv[$x] : $this->xv[$x]]; + if (!$matches) + continue; + 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. + * + * @package wiki + * @subpackage WikiDiff + */ +class WikiDiff +{ + public $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 die("assertion 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) + die ("assertion 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. + if (!is_array($left)) die('assertion error'); + $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 "<ol>"; + for (reset($this->edits); + $edit = current($this->edits); + next($this->edits)) + { + echo "<li>"; + if ($edit > 0) + echo "Copy $edit"; + else if ($edit < 0) + echo "Delete " . -$edit; + else if (is_array($edit)) + { + echo "Add " . sizeof($edit) . "<ul>"; + for ($i = 0; $i < sizeof($edit); $i++) + echo "<li>" . htmlspecialchars($edit[$i]); + echo "</ul>"; + } + else + die("assertion error"); + } + echo "</ol>"; + } + */ + /** + * 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(tra ("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; + } + /** + * 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(tra ("WikiDiff::_check: failed")); + reset($this->edits); + $prev = current($this->edits); + $prevtype = is_array($prev) ? 'a' : ($prev > 0 ? 'c' : 'd'); + while ($edit = next($this->edits)) + { + $type = is_array($edit) ? 'a' : ($edit > 0 ? 'c' : 'd'); + if ( $prevtype == $type ) + ExitWiki(tra ("WikiDiff::_check: edit sequence is non-optimal")); + $prevtype = $type; + } + $lcs = $this->lcs(); + printf ("<strong>" . tra ("WikiDiff Okay: LCS = %s") . "</strong>\n", $lcs); + } +} +/** + * 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); + * + * @package wiki + * @subpackage WikiDiffFormatter + */ +class WikiDiffFormatter +{ + public $context_lines; + public $do_reverse_diff; + public $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 format ($diff, $from_lines) + { + $html = '<table style="background-color: black" ' . + 'cellspacing="2" cellpadding="2" border="0"><br />'; + $html .= $this->_format($diff->edits, $from_lines); + $html .= "</table>\n"; + return $html; + } + function _format ($edits, $from_lines) + { + $html = ''; + $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); + $html .= $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 $html; + } + function _emit_lines($lines, $prefix, $color) + { + $html = ''; + reset($lines); + while (list ($junk, $line) = each($lines)) + { + $html .= "<tr style=\"background-color: $color\"><td><tt>$prefix</tt>"; + $html .= "<tt>" . htmlspecialchars($line) . "</tt></td></tr>\n"; + } + return $html; + } + function _emit_diff ($xbeg,$xlen,$ybeg,$ylen,$hunks) + { + $html = '<tr><td><table style="background-color: white"' + . ' cellspacing="0" border="0" cellpadding="4"><br />' + . '<tr bgcolor="#cccccc"><td><tt>' + . $this->_diff_header($xbeg, $xlen, $ybeg, $ylen) + . "</tt></td></tr>\n<tr><td>\n" + . '<table cellspacing="0" border="0" cellpadding="2"><br />'; + $prefix = array('c' => $this->context_prefix, + 'a' => $this->adds_prefix, + 'd' => $this->deletes_prefix); + $color = array('c' => '#ffffff', + 'a' => '#ccffcc', + 'd' => '#ffcccc'); + for (reset($hunks); $hunk = current($hunks); next($hunks)) + { + if (!empty($hunk['c'])) + $html .= $this->_emit_lines($hunk['c'], + $this->context_prefix, '#ffffff'); + if (!empty($hunk['d'])) + $html .= $this->_emit_lines($hunk['d'], + $this->deletes_prefix, '#ffcccc'); + if (!empty($hunk['a'])) + $html .= $this->_emit_lines($hunk['a'], + $this->adds_prefix, '#ccffcc'); + } + $html .= "</table></td></tr></table></td></tr>\n"; + return $html; + } + 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) : ''; + return "$xbeg$xlen$what$ybeg$ylen"; + } +} +/** + * 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. + * + * @package wiki + * @subpackage WikiUnifiedDiffFormatter + */ + +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 @@"; + } +} +///////////////////////////////////////////////////////////////// +/* +if ($diff) +{ + if (get_magic_quotes_gpc()) { + $diff = stripslashes($diff); + } + $pagename = $diff; + $wiki = RetrievePage($dbi, $pagename, $WikiPageStore); +// $dba = OpenDataBase($ArchivePageStore); + $archive= RetrievePage($dbi, $pagename, $ArchivePageStore); + $html = '<table><tr><td align="right">'; + $html .= tra ("Current page:"); + $html .= '</td>'; + if (is_array($wiki)) { + $html .= "<td>"; + $html .= sprintf(tra ("version %s"), $wiki['version']); + $html .= "</td><td>"; + $html .= sprintf(tra ("last modified on %s"), + date($datetimeformat, $wiki['lastmodified'])); + $html .= "</td><td>"; + $html .= sprintf (tra ("by %s"), $wiki['author']); + $html .= "</td>"; + } else { + $html .= "<td colspan=3><em>"; + $html .= tra ("None"); + $html .= "</em></td>"; + } + $html .= "</tr>\n"; + $html .= '<tr><td align="right">'; + $html .= tra ("Archived page:"); + $html .= '</td>'; + if (is_array($archive)) { + $html .= "<td>"; + $html .= sprintf(tra ("version %s"), $archive['version']); + $html .= "</td><td>"; + $html .= sprintf(tra ("last modified on %s"), + date($datetimeformat, $archive['lastmodified'])); + $html .= "</td><td>"; + $html .= sprintf(tra ("by %s"), $archive['author']); + $html .= "</td>"; + } else { + $html .= "<td colspan=3><em>"; + $html .= tra ("None"); + $html .= "</em></td>"; + } + $html .= "</tr></table><p>\n"; + if (is_array($wiki) && is_array($archive)) + { + $diff = new WikiDiff($archive['content'], $wiki['content']); + if ($diff->isEmpty()) { + $html .= '<hr>[' . tra ("Versions are identical") . ']'; + } else { + //$fmt = new WikiDiffFormatter; + $fmt = new WikiUnifiedDiffFormatter; + $html .= $fmt->format($diff, $archive['content']); + } + } + GeneratePage('MESSAGE', $html, sprintf(tra ("Diff of %s."), + htmlspecialchars($pagename)), 0); +} +*/ + + + // \todo remove html hardcoded in diff2 + function diff2($page1, $page2) { + $page1 = split("\n", $page1); + $page2 = split("\n", $page2); + $z = new WikiDiff($page1, $page2); + if ($z->isEmpty()) { + $html = '<hr><br />[' . tra("Versions are identical"). ']<br /><br />'; + } else { + //$fmt = new WikiDiffFormatter; + $fmt = new WikiUnifiedDiffFormatter; + $html = $fmt->format($z, $page1); + } + return $html; + } + +?> |