<?php
/**
*
* @package build
* @copyright (c) 2000 Geoffrey T. Dairiki <dairiki@dairiki.org>
* @copyright (c) 2010 phpBB Group
* @license http://opensource.org/licenses/gpl-2.0.php GNU General Public License v2
*
*/
/**
* 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
{
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();
// 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; // fixme? what happens to yhash/xhash when
// there are two identical lines??
}
$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)
{
// 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 (!empty($endskip))
{
$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++)
{
$_index = $flip ? $this->yv[$x] : $this->xv[$x];
$matches = (isset($ymatches[$_index])) ? $ymatches[$_index] : array();
if (!$matches)
{
continue;
}
reset($matches);
while (list ($junk, $y) = each($matches))
{
if (!isset($this->in_seq[$y]) || !$this->in_seq[$y])
{
$k = $this->_lcs_pos($y);
//if (!$k) die('assertion "!$k" failed');
$ymids[$k] = $ymids[$k-1];
break;
}
}
while (list ($junk, $y) = each($matches))
{
if ($y > $this->seq[$k-1])
{
//if ($y >= $this->seq[$k]) die('assertion failed');
// 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 (!isset($this->in_seq[$y]) || !$this->in_seq[$y])
{
$k = $this->_lcs_pos($y);
//if (!$k) die('assertion "!$k" failed');
$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;
}
}
//if ($ypos == $this->seq[$end]) die("assertion failure");
$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 have 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;
$len = sizeof($lines);
while (1)
{
/*
* Scan forwards to find beginning of another run of changes.
* Also keep track of the corresponding point in the other file.
*/
while ($i < $len && $changed[$i] == 0)
{
while ($other_changed[$j++])
{
continue;
}
$i++;
}
if ($i == $len)
{
break;
}
$start = $i;
// Find the end of this run of changes.
while (isset($changed[++$i]))
{
continue;
}
while (isset($other_changed[$j]) && $other_changed[$j])
{
$j++;
}
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 && $lines[$start - 1] == $lines[$i - 1])
{
$changed[--$start] = 1;
$changed[--$i] = false;
while ($changed[$start - 1])
{
$start--;
}
while ($other_changed[--$j])
{
continue;
}
}
/*
* 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 = empty($other_changed[$j - 1]) ? $len : $i;
/*
* 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 ($changed[$i])
{
$i++;
}
while ($other_changed[++$j])
{
$corresponding = $i;
}
}
} 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;
while ($other_changed[--$j])
{
continue;
}
}
}
}
}
/**
* Class representing a diff between two files.
*/
class Diff
{
var $edits;
/**
* Compute diff between files (or deserialize serialized WikiDiff.)
*/
function Diff($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 Diff.
$this->edits = unserialize($from_lines);
}
else
{
$this->edits = array();
}
}
/**
* Compute reversed Diff.
*
* SYNOPSIS:
*
* $diff = new Diff($lines1, $lines2);
* $rev = $diff->reverse($lines1);
*
* // reconstruct $lines1 from $lines2:
* $out = $rev->apply($lines2);
*/
function reverse ($from_lines)
{
$x = 0;
$rev = new Diff;
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);
if ($nadd == 0)
{
die("assertion error");
}
$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) Diffs.
*
* SYNOPSIS:
*
* $diff1 = new Diff($lines1, $lines2);
* $diff2 = new Diff($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 Diff;
$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 Diff to a set of lines.
*
* SYNOPSIS:
*
* $diff = new Diff($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)
{
die(sprintf("Diff::apply: line count mismatch: %s != %s", $x, $xlim));
}
return $output;
}
/**
* Serialize a Diff.
*
* SYNOPSIS:
*
* $diff = new Diff($lines1, $lines2);
* $string = $diff->serialize;
*
* // recover Diff from serialized version:
* $diff2 = new Diff($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 Diff 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))
{
die("Diff::_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)
{
die("Diff::_check: edit sequence is non-optimal");
}
$prevtype = $type;
}
$lcs = $this->lcs();
echo "<strong>Diff Okay: LCS = $lcs</strong>\n";
}
}
/**
* A class to format a Diff as HTML.
*
* Usage:
*
* $diff = new Diff($lines1, $lines2); // compute diff.
*
* $fmt = new DiffFormatter;
* echo $fmt->format($diff, $lines1); // Output HTMLified standard diff.
*
* or to output reverse diff (diff's that would take $lines2 to $lines1):
*
* $fmt = new DiffFormatter(true);
* echo $fmt->format($diff, $lines1);
*/
class DiffFormatter
{
var $context_lines;
var $do_reverse_diff;
var $context_prefix, $deletes_prefix, $adds_prefix;
function DiffFormatter ($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 width="100%" bgcolor="black" cellspacing=2 cellpadding=2 border=0>' . "\n";
$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))
{
// Originally $ncopy > 2 * $this->context_lines, but we need to split as early as we can for creating MOD Text Templates. ;)
if (!$next || $ncopy > $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 bgcolor=\"$color\"><td><tt>$prefix</tt>";
$html .= "<tt>" . htmlspecialchars($line) . "</tt></td></tr>\n";
}
return $html;
}
function _emit_diff ($xbeg,$xlen,$ybeg,$ylen,$hunks)
{
// Save hunk...
$this->diff_hunks[] = $hunks;
$html = '<tr><td><table width="100%" bgcolor="white" cellspacing="0" border="0" cellpadding="4">
<tr bgcolor="#cccccc"><td><tt>' .
$this->_diff_header($xbeg, $xlen, $ybeg, $ylen) . '
</tt></td></tr>\n<tr><td>
<table width="100%" cellspacing="0" border="0" cellpadding="2">
';
$prefix = array('c' => $this->context_prefix, 'a' => $this->adds_prefix, 'd' => $this->deletes_prefix);
$color = array('c' => '#ffffff', 'a' => '#ffcccc', 'd' => '#ccffcc');
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, '#ccffcc');
}
if (!empty($hunk['a']))
{
$html .= $this->_emit_lines($hunk['a'], $this->adds_prefix, '#ffcccc');
}
}
$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 Diff as a pretty HTML unified diff.
*
* Usage:
*
* $diff = new Diff($lines1, $lines2); // compute diff.
*
* $fmt = new UnifiedDiffFormatter;
* echo $fmt->format($diff, $lines1); // Output HTMLified unified diff.
*/
class UnifiedDiffFormatter extends DiffFormatter
{
function UnifiedDiffFormatter ($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 @@";
}
}
/**
* A class to format a Diff as MOD Template instuctions.
*
* Usage:
*
* $diff = new Diff($lines1, $lines2); // compute diff.
*
* $fmt = new BBCodeDiffFormatter;
* echo $fmt->format($diff, $lines1); // Output MOD Actions.
*/
class BBCodeDiffFormatter extends DiffFormatter
{
function BBCodeDiffFormatter ($reverse = false, $context_lines = 3, $debug = false)
{
$this->do_reverse_diff = $reverse;
$this->context_lines = $context_lines;
$this->context_prefix = ' ';
$this->deletes_prefix = '-';
$this->adds_prefix = '+';
$this->debug = $debug;
}
function format ($diff, $from_lines)
{
$html = $this->_format($diff->edits, $from_lines);
return $html;
}
function skip_lines(&$order_array, &$ordering)
{
if (sizeof($order_array['find_c']))
{
$text = implode('', $order_array['find_c']);
if ($text === "\n" || $text === "\t" || $text === '')
{
if (isset($order_array['first_find_c'][0]) &&
is_array($order_array['first_find_c'][0]) &&
trim(implode('', $order_array['first_find_c'][0])) != '' &&
isset($order_array['replace']))
{
$order_array['add'] = $order_array['replace'];
unset($order_array['replace']);
// this is actually an after add
}
else
{
return true;
}
}
}
if (isset($order_array['add']) && sizeof($order_array['add']))
{
$text = implode('', $order_array['add']);
if ($text === "\n" || $text === "\t" || $text === '')
{
return true;
}
}
if (isset($order_array['replace']) && sizeof($order_array['replace']))
{
$text = implode('', $order_array['replace']);
if ($text === "\n" || $text === "\t" || $text === '')
{
return true;
}
}
}
function _emit_lines_bb($ybeg, &$ordering)
{
$html = '';
// Now adjust for bbcode display...
foreach ($ordering as $order_array)
{
// Skip useless empty lines...
if ($this->skip_lines($order_array, $ordering))
{
continue;
}
// Only include double-finds if the last find has very few code location indications...
if (isset($order_array['first_find_c']) && sizeof($order_array['first_find_c']))
{
$text = implode('', $order_array['find_c']);
if ($text === "\n" || $text === "\t" || $text === '')
{
// no real find, use first_find_c if possible!
//var_dump($order_array);
if (is_array($order_array['first_find_c'][0]))
{
$order_array['find_c'] = $order_array['first_find_c'][0];
}
else
{
if (isset($order_array['replace']) || isset($order_array['add']) || isset($order_array['delete']))
{
echo "skipped an edit!\n";
var_dump($order_array);
}
continue;
}
}
else
{
if (strlen(implode('', $order_array['find_c'])) < 50 && is_array($order_array['first_find_c'][0]))
{
$html .= "#\n#-----[ FIND ]---------------------------------------------\n# Around Line {$ybeg}\n";
$html .= implode("", $order_array['first_find_c'][0]);
$html .= "\n";
$ybeg += sizeof($order_array['first_find_c'][0]);
}
}
}
// still here but nothing to do? what the heck?
if (!isset($order_array['replace']) && !isset($order_array['add']) && !isset($order_array['delete']))
{
echo "skipped an edit!\n";
var_dump($order_array);
continue;
}
if (sizeof($order_array['find_c']))
{
$html .= "#\n#-----[ FIND ]---------------------------------------------\n# Around Line {$ybeg}\n";
$html .= implode("", $order_array['find_c']);
$html .= "\n";
}
if (isset($order_array['replace']))
{
$html .= "#\n#-----[ REPLACE WITH ]---------------------------------------------\n#\n";
$html .= implode("", $order_array['replace']);
$html .= "\n";
}
if (isset($order_array['add']))
{
$html .= "#\n#-----[ AFTER, ADD ]---------------------------------------------\n#\n";
$html .= implode("", $order_array['add']);
$html .= "\n";
}
// There is no DELETE. :o
// Let's try to adjust it then...
if (isset($order_array['delete']))
{
$text = implode('', $order_array['delete']);
if ($text === "\n" || $text === "\t" || $text === '')
{
continue;
}
$ybeg += sizeof($order_array['find_c']);
$html .= "#\n#-----[ FIND ]---------------------------------------------\n# Around Line {$ybeg}\n";
$html .= implode("", $order_array['delete']);
$html .= "\n";
$html .= "#\n#-----[ REPLACE WITH ]---------------------------------------------\n# Just remove/delete the lines (replacing with an empty line)\n";
$html .= "\n";
$html .= "\n";
}
}
return $html;
}
function format_open($filename)
{
$html = '';
$html .= "#\n#-----[ OPEN ]--------------------------------------------- \n#\n{$filename}\n\n";
return $html;
}
function format_close($filename)
{
return '';
}
function _emit_diff ($xbeg, $xlen, $ybeg, $ylen, $hunks)
{
// Go through the hunks to determine which method we are using (AFTER, ADD; REPLACE WITH or DELETE)
// Remove the header...
if (sizeof($hunks) <= 2 && !isset($hunks[1]['a']) && !isset($hunks[1]['d']))
{
$reorder = false;
$orig_hunks = $hunks;
foreach ($hunks as $key => $hunk)
{
if (isset($hunk['a']) && isset($hunk['d']))
{
/**/ if (sizeof($hunk['a']) == 1 && sizeof($hunk['d']) == 1)
{
if (preg_match('/\* @version \$Id:.+\$$/', $hunk['a'][0]) && preg_match('/\* @version \$Id:.+\$$/', $hunk['d'][0]))
{
// Only remove this sole hunk...
unset($hunks[$key]);
$reorder = true;
continue;
}
}/**/
// Compare the add and replace one...
$string_1 = rtrim(trim(implode('', $hunk['a'])));
$string_2 = rtrim(trim(implode('', $hunk['d'])));
if (strcmp($string_1, $string_2) === 0)
{
// Only remove this sole hunk...
unset($hunks[$key]);
$reorder = true;
continue;
}
}
}
if ($reorder)
{
// Now check if we have no more 'a' and 'd's
$hunks = array_merge($hunks, array());
}
}
else
{
$reorder = false;
$orig_hunks = $hunks;
foreach ($hunks as $key => $hunk)
{
if (isset($hunk['a']) && isset($hunk['d']))
{
/**/ if (sizeof($hunk['a']) == 1 && sizeof($hunk['d']) == 1)
{
if (preg_match('/\* @version \$Id:.+\$$/', $hunk['a'][0]) && preg_match('/\* @version \$Id:.+\$$/', $hunk['d'][0]))
{
// Only remove this sole hunk...
unset($hunks[$key]);
$reorder = true;
continue;
}
}/**/
// Compare the add and replace one...
$string_1 = rtrim(trim(implode('', $hunk['a'])));
$string_2 = rtrim(trim(implode('', $hunk['d'])));
if (strcmp($string_1, $string_2) === 0)
{
// Only remove this sole hunk...
unset($hunks[$key]);
$reorder = true;
continue;
}
}
}
if ($reorder)
{
$hunks = array_merge($hunks, array());
if (sizeof($hunks) == 1 && sizeof($hunks[0]) == 1 && isset($hunks[0]['c']))
{
return;
}
else
{
$hunks = $orig_hunks;
}
}
}
if (sizeof($hunks) == 1 && sizeof($hunks[0]) == 1 && isset($hunks[0]['c']))
{
return;
}
$replace = false;
foreach ($hunks as $key => $hunk)
{
if (isset($hunk['d']) && isset($hunk['a']))
{
$replace = true;
break;
}
}
$ordering = array();
$cur_pos = 0;
// Replace-block
if ($replace)
{
foreach ($hunks as $hunk)
{
if (!isset($hunk['a']) && !isset($hunk['d']))
{
continue;
}
if (!empty($hunk['c']))
{
if (!isset($ordering[$cur_pos]['find_c']))
{
$ordering[$cur_pos]['find_c'] = $hunk['c'];
}
else
{
$ordering[$cur_pos]['end_c'] = $hunk['c'];
}
}
// Make sure we begin fresh...
if (!isset($ordering[$cur_pos]['replace']))
{
$ordering[$cur_pos]['first_find_c'][] = $ordering[$cur_pos]['find_c'];
$ordering[$cur_pos]['find_c'] = array();
$ordering[$cur_pos]['replace'] = array();
}
// Add the middle part if one exist...
if (isset($ordering[$cur_pos]['end_c']))
{
$ordering[$cur_pos]['find_c'] = array_merge($ordering[$cur_pos]['find_c'], $ordering[$cur_pos]['end_c']);
$ordering[$cur_pos]['replace'] = array_merge($ordering[$cur_pos]['replace'], $ordering[$cur_pos]['end_c']);
unset($ordering[$cur_pos]['end_c']);
}
if (isset($hunk['d']))
{
$ordering[$cur_pos]['find_c'] = array_merge($ordering[$cur_pos]['find_c'], $hunk['d']);
}
if (isset($hunk['a']))
{
$ordering[$cur_pos]['replace'] = array_merge($ordering[$cur_pos]['replace'], $hunk['a']);
}
}
}
else
{
foreach ($hunks as $hunk)
{
if (!empty($hunk['c']))
{
if (!isset($ordering[$cur_pos]['find_c']))
{
$ordering[$cur_pos]['find_c'] = $hunk['c'];
}
else
{
$ordering[$cur_pos]['end_c'] = $hunk['c'];
}
}
if (!empty($hunk['a']))
{
if (isset($ordering[$cur_pos]['delete']))
{
// If ordering is set with an delete entry, we will actually begin a new ordering array (to seperate delete from add)
$cur_pos++;
$ordering[$cur_pos]['find_c'] = $ordering[($cur_pos - 1)]['end_c'];
$ordering[$cur_pos]['add'] = $hunk['a'];
}
else
{
if (isset($ordering[$cur_pos]['add']))
{
// Now, we really need to be quite careful here...
if (isset($ordering[$cur_pos]['end_c']) && isset($hunk['c']) && isset($hunk['a']) && sizeof($hunk) == 2)
{
// There is a new find/add entry we did not catch... let's try to add a new entry then... but first check the hunk[a] contents...
$text = trim(implode("\n", $hunk['c']));
if ($text == "\n" || !$text)
{
$ordering[$cur_pos]['add'] = array_merge($ordering[$cur_pos]['add'], array("\n"), $hunk['a']);
}
else if (sizeof($hunk['c']) > 2 || strlen(implode('', $hunk['c'])) > 20)
{
$cur_pos++;
$ordering[$cur_pos]['find_c'] = $ordering[($cur_pos - 1)]['end_c'];
$ordering[$cur_pos]['add'] = $hunk['a'];
}
else
{
$cur_pos++;
$ordering[$cur_pos]['find_c'] = $ordering[($cur_pos - 1)]['end_c'];
$ordering[$cur_pos]['add'] = $hunk['a'];
/* echo 'FIND STATEMENT TOO TINY';
echo ";".rawurlencode($text).";";
var_dump($hunk);
exit;*/
}
}
else
{
echo 'UNCATCHED ENTRY';
var_dump($hunks);
exit;
}
}
else
{
$ordering[$cur_pos]['add'] = $hunk['a'];
}
}
}
else if (!empty($hunk['d']))
{
if (isset($ordering[$cur_pos]['add']))
{
// If ordering is set with an add entry, we will actually begin a new ordering array (to seperate delete from add)
$cur_pos++;
$ordering[$cur_pos]['find_c'] = $ordering[($cur_pos - 1)]['end_c'];
$ordering[$cur_pos]['delete'] = $hunk['d'];
}
else
{
$ordering[$cur_pos]['delete'] = $hunk['d'];
}
}
}
}
$html = '';
return $this->_emit_lines_bb($ybeg, $ordering);
}
function _diff_header($xbeg, $xlen, $ybeg, $ylen)
{
}
}
/**
* A class to format a Diff as MOD Template instuctions.
*
* Usage:
*
* $diff = new Diff($lines1, $lines2); // compute diff.
*
* $fmt = new BBCodeDiffFormatter;
* echo $fmt->format($diff, $lines1); // Output MOD Actions.
*/
class MODXDiffFormatter extends BBCodeDiffFormatter
{
function MODXDiffFormatter ($reverse = false, $context_lines = 3, $debug = false)
{
$this->do_reverse_diff = $reverse;
$this->context_lines = $context_lines;
$this->context_prefix = ' ';
$this->deletes_prefix = '-';
$this->adds_prefix = '+';
$this->debug = $debug;
}
function _emit_lines_bb($ybeg, &$ordering)
{
$html = '';
// Now adjust for bbcode display...
foreach ($ordering as $order_array)
{
// Skip useless empty lines...
if ($this->skip_lines($order_array, $ordering))
{
continue;
}
// Only include double-finds if the last find has very few code location indications...
if (sizeof($order_array['first_find_c']))
{
$text = implode('', $order_array['find_c']);
if ($text === "\n" || $text === "\t" || $text === '')
{
continue;
}
if (strlen(implode('', $order_array['find_c'])) < 50)
{
if (substr($html, -8) !== '</find>' . "\n")
{
$html .= ' <edit>' . "\n";
}
$html .= ' <comment lang="en">Around Line ' . $ybeg . '</comment>' . "\n";
$html .= ' <find>' . htmlspecialchars(implode('', $order_array['first_find_c'][0])) . '</find>' . "\n";
$ybeg += sizeof($order_array['first_find_c'][0]);
}
}
if (sizeof($order_array['find_c']))
{
if (substr($html, -8) !== '</find>' . "\n")
{
$html .= ' <edit>' . "\n";
}
// $html .= ' <edit>' . "\n";
$html .= ' <comment lang="en">Around Line ' . $ybeg . '</comment>' . "\n";
$html .= ' <find>' . htmlspecialchars(implode('', $order_array['find_c'])) . '</find>' . "\n";
}
if (isset($order_array['replace']))
{
$html .= ' <action type="replace-with">' . htmlspecialchars(implode('', $order_array['replace'])) . '</action>' . "\n";
$html .= ' </edit>' . "\n";
}
if (isset($order_array['add']))
{
$html .= ' <action type="after-add">' . htmlspecialchars(implode('', $order_array['add'])) . '</action>' . "\n";
$html .= ' </edit>' . "\n";
}
// There is no DELETE. :o
// Let's try to adjust it then...
if (isset($order_array['delete']))
{
$text = implode('', $order_array['delete']);
if ($text === "\n" || $text === "\t" || $text === '')
{
continue;
}
$ybeg += sizeof($order_array['find_c']);
if (substr($html, -8) !== '</find>' . "\n")
{
$html .= ' <edit>' . "\n";
}
$html .= ' <comment lang="en">Around Line ' . $ybeg . ' / Just remove/delete the lines (replacing with an empty line)</comment>' . "\n";
$html .= ' <find>' . htmlspecialchars(implode('', $order_array['delete'])) . '</find>' . "\n";
$html .= ' <action type="replace-with"></action>' . "\n";
$html .= ' </edit>';
}
}
return $html;
}
function format_open($filename)
{
return '<open src="' . $filename . '">' . "\n";
}
function format_close($filename)
{
return '</open>' . "\n";
}
function _diff_header($xbeg, $xlen, $ybeg, $ylen)
{
}
}