<?php
class XenForo_Diff3
{
const UPDATE = 'u';
const CONFLICT = 'c';
const EQUAL = 'e';
const MINE = 'm';
const YOURS = 'y';
const BOTH = 'b';
/**
* @var XenForo_Diff
*/
protected $_comparer;
protected $_currentOrig;
protected $_currentMine;
protected $_currentYours;
protected $_bigConflicts = true;
public function __construct(XenForo_Diff $comparer = null)
{
if (!$comparer)
{
$comparer = new XenForo_Diff();
}
$this->_comparer = $comparer;
}
protected function _initBlock()
{
$this->_currentOrig = $this->_currentMine = $this->_currentYours = array();
}
protected function _appendOrig(array $blocks)
{
array_splice($this->_currentOrig, count($this->_currentOrig), 0, $blocks);
}
protected function _appendMine(array $blocks)
{
array_splice($this->_currentMine, count($this->_currentMine), 0, $blocks);
}
protected function _appendYours(array $blocks)
{
array_splice($this->_currentYours, count($this->_currentYours), 0, $blocks);
}
protected function _finishBlock(array &$output, $init = true)
{
if ($this->_currentMine || $this->_currentYours || $this->_currentOrig)
{
if ($this->_currentMine == $this->_currentYours)
{
if ($this->_currentMine == $this->_currentOrig)
{
$output[] = array(self::EQUAL, $this->_currentMine);
}
else
{
$output[] = array(self::UPDATE, $this->_currentMine, $this->_currentOrig, self::BOTH);
}
}
else if ($this->_currentMine == $this->_currentOrig)
{
$output[] = array(self::UPDATE, $this->_currentYours, $this->_currentOrig, self::YOURS);
}
else if ($this->_currentYours == $this->_currentOrig)
{
$output[] = array(self::UPDATE, $this->_currentMine, $this->_currentOrig, self::MINE);
}
else
{
// potential conflict - try to resolve prefixes
$cM = $this->_currentMine;
$cY = $this->_currentYours;
$cO = $this->_currentOrig;
if ($init)
{
$childOutput = array();
}
else
{
$childOutput =& $output;
}
if ($i = $this->_getMatchLength($this->_currentMine, $this->_currentYours))
{
$update = array_splice($this->_currentMine, 0, $i);
array_splice($this->_currentYours, 0, $i);
$childOutput[] = array(self::UPDATE, $update, array(), self::BOTH);
$this->_finishBlock($childOutput, false);
}
else if ($i = $this->_getMatchLength($this->_currentMine, $this->_currentOrig))
{
$update = array_splice($this->_currentMine, 0, $i);
array_splice($this->_currentOrig, 0, $i);
$childOutput[] = array(self::UPDATE, array(), $update, self::YOURS);
$this->_finishBlock($childOutput, false);
}
else if ($i = $this->_getMatchLength($this->_currentYours, $this->_currentOrig))
{
$update = array_splice($this->_currentYours, 0, $i);
array_splice($this->_currentOrig, 0, $i);
$childOutput[] = array(self::UPDATE, array(), $update, self::MINE);
$this->_finishBlock($childOutput, false);
}
else if ($i = $this->_getEndMatchLength($this->_currentMine, $this->_currentYours))
{
$update = array_splice($this->_currentMine, -$i);
array_splice($this->_currentYours, -$i);
$this->_finishBlock($childOutput, false);
$childOutput[] = array(self::UPDATE, $update, array(), self::BOTH);
}
else if ($i = $this->_getEndMatchLength($this->_currentMine, $this->_currentOrig))
{
$update = array_splice($this->_currentMine, -$i);
array_splice($this->_currentOrig, -$i);
$this->_finishBlock($childOutput, false);
$childOutput[] = array(self::UPDATE, array(), $update, self::YOURS);
}
else if ($i = $this->_getEndMatchLength($this->_currentYours, $this->_currentOrig))
{
$update = array_splice($this->_currentYours, -$i);
array_splice($this->_currentOrig, -$i);
$this->_finishBlock($childOutput, false);
$childOutput[] = array(self::UPDATE, array(), $update, self::MINE);
}
else if (!$init)
{
$childOutput[] = array(self::CONFLICT, $this->_currentMine, $this->_currentOrig, $this->_currentYours);
}
if ($init)
{
if ($childOutput)
{
$hasConflict = false;
foreach ($childOutput AS $child)
{
if ($child[0] == self::CONFLICT)
{
$hasConflict = true;
break;
}
}
if ($hasConflict && $this->_bigConflicts)
{
// still have a conflict, just mark the whole thing as it originally was
$output[] = array(self::CONFLICT, $cM, $cO, $cY);
}
else
{
// no longer have a conflict or we want the small conflicts
array_splice($output, count($output), 0, $childOutput);
}
}
else
{
// couldn't find any matching bits
$output[] = array(self::CONFLICT, $this->_currentMine, $this->_currentOrig, $this->_currentYours);
}
}
}
}
if ($init)
{
$this->_initBlock();
}
}
protected function _getMatchLength(array $blocks1, array $blocks2)
{
$i = 0;
while (isset($blocks1[$i]) && isset($blocks2[$i]) && $blocks1[$i] === $blocks2[$i])
{
$i++;
}
return $i;
}
protected function _getEndMatchLength(array $blocks1, array $blocks2)
{
$match = 0;
$end1 = count($blocks1) - 1;
$end2 = count($blocks2) - 1;
while (isset($blocks1[$end1]) && isset($blocks2[$end2]) && $blocks1[$end1] === $blocks2[$end2])
{
$match++;
$end1--;
$end2--;
}
return $match;
}
public function findDifferences($mine, $original, $yours, $type = XenForo_Diff::DIFF_TYPE_LINE)
{
$mineDiff = $this->_comparer->findDifferences($original, $mine, $type);
$yourDiff = $this->_comparer->findDifferences($original, $yours, $type);
$output = array();
$this->_initBlock();
$m = reset($mineDiff);
$y = reset($yourDiff);
while ($m || $y)
{
if ($m && $y)
{
$mType = $m[0];
$mBlocks =& $m[1];
$yType = $y[0];
$yBlocks =& $y[1];
if ($mType == XenForo_Diff::EQUAL && $yType == XenForo_Diff::EQUAL)
{
$this->_finishBlock($output);
$i = $this->_getMatchLength($mBlocks, $yBlocks);
if (!$i)
{
throw new Exception("Both equal but no leading match?");
}
$matches = array_splice($mBlocks, 0, $i);
$output[] = array(self::EQUAL, $matches);
array_splice($yBlocks, 0, $i);
if (!$mBlocks)
{
$m = next($mineDiff);
}
if (!$yBlocks)
{
$y = next($yourDiff);
}
}
else if ($mType == XenForo_Diff::INSERT)
{
$this->_appendMine($mBlocks);
$m = next($mineDiff);
}
else if ($yType == XenForo_Diff::INSERT)
{
$this->_appendYours($yBlocks);
$y = next($yourDiff);
}
else if ($mType == XenForo_Diff::DELETE && $yType == XenForo_Diff::DELETE)
{
$this->_finishBlock($output);
$i = $this->_getMatchLength($mBlocks, $yBlocks);
if (!$i)
{
throw new Exception("Both deletes but no leading match?");
}
$this->_appendOrig(array_splice($mBlocks, 0, $i));
array_splice($yBlocks, 0, $i);
if (!$mBlocks)
{
$m = next($mineDiff);
}
if (!$yBlocks)
{
$y = next($yourDiff);
}
}
else if ($mType == XenForo_Diff::DELETE && $yType == XenForo_Diff::EQUAL)
{
$min = min(count($mBlocks), count($yBlocks));
array_splice($mBlocks, 0, $min); // removed
$block = array_splice($yBlocks, 0, $min);
$this->_appendOrig($block);
$this->_appendYours($block);
if (!$mBlocks)
{
$m = next($mineDiff);
}
if (!$yBlocks)
{
$y = next($yourDiff);
}
}
else if ($yType == XenForo_Diff::DELETE && $mType == XenForo_Diff::EQUAL)
{
$min = min(count($mBlocks), count($yBlocks));
array_splice($yBlocks, 0, $min); // removed
$block = array_splice($mBlocks, 0, $min);
$this->_appendOrig($block);
$this->_appendMine($block);
if (!$mBlocks)
{
$m = next($mineDiff);
}
if (!$yBlocks)
{
$y = next($yourDiff);
}
}
}
else if ($m)
{
if ($m[0] != XenForo_Diff::INSERT)
{
throw new Exception("Had m only but wasn't insert");
}
$this->_appendMine($m[1]);
$m = next($mineDiff);
}
else if ($y)
{
if ($y[0] != XenForo_Diff::INSERT)
{
throw new Exception("Had y only but wasn't insert");
}
$this->_appendYours($y[1]);
$y = next($yourDiff);
}
}
$this->_finishBlock($output);
return $this->_finalize($output);
}
protected function _finalize(array $output)
{
$newOutput = array();
$i = -1;
$lastType = null;
foreach ($output AS $hunk)
{
if ($hunk[0] == self::CONFLICT && $lastType === self::CONFLICT)
{
// back to back conflicts: merge
$newOutput[$i][1] = array_merge($newOutput[$i][1], $hunk[1]);
$newOutput[$i][2] = array_merge($newOutput[$i][2], $hunk[2]);
$newOutput[$i][3] = array_merge($newOutput[$i][3], $hunk[3]);
}
else
{
$i++;
$newOutput[$i] = $hunk;
$lastType = $hunk[0];
}
}
return $newOutput;
}
public function mergeToFinal($mine, $original, $yours, $type = XenForo_Diff::DIFF_TYPE_LINE)
{
$diffs = $this->findDifferences($mine, $original, $yours, $type);
$output = array();
foreach ($diffs AS $diff)
{
if ($diff[0] == self::CONFLICT)
{
return false;
}
array_splice($output, count($output), 0, $diff[1]);
}
switch ($type)
{
case XenForo_Diff::DIFF_TYPE_CHAR:
$joiner = '';
break;
case XenForo_Diff::DIFF_TYPE_WORD:
$joiner = ' ';
break;
case XenForo_Diff::DIFF_TYPE_LINE:
default:
$joiner = "\n";
}
return implode($joiner, $output);
}
}