From bef5fb06ceb398b5dda71522a12027ede265359a Mon Sep 17 00:00:00 2001 From: =?utf8?q?Tim=20D=C3=BCsterhus?= Date: Tue, 10 Jun 2014 17:48:44 +0200 Subject: [PATCH] Add Diff.class.php --- .../install/files/lib/util/Diff.class.php | 304 ++++++++++++++++++ 1 file changed, 304 insertions(+) create mode 100644 wcfsetup/install/files/lib/util/Diff.class.php diff --git a/wcfsetup/install/files/lib/util/Diff.class.php b/wcfsetup/install/files/lib/util/Diff.class.php new file mode 100644 index 0000000000..f13634a02c --- /dev/null +++ b/wcfsetup/install/files/lib/util/Diff.class.php @@ -0,0 +1,304 @@ + + * @package com.woltlab.wcf + * @subpackage util + * @category Community Framework + */ +class Diff { + /** + * identifier for added lines + * @var string + */ + const ADDED = '+'; + + /** + * identifier for removed lines + * @var string + */ + const REMOVED = '-'; + + /** + * indentifier for unchanged lines + * @var string + */ + const SAME = ' '; + + /** + * original array, as given by the user + * @var array + */ + protected $a = array(); + + /** + * modified array, as given by the user + * @var array + */ + protected $b = array(); + + /** + * size of a + * @var integer + */ + protected $sizeA = 0; + + /** + * size of b + * @var integer + */ + protected $sizeB = 0; + + /** + * calculated diff + * @var array + */ + protected $d = null; + + public function __construct(array $a, array $b) { + $this->a = $a; + $this->b = $b; + + $this->sizeA = count($a); + $this->sizeB = count($b); + } + + /** + * Calculates the longest common subsequence of `$this->a` + * and `$this->b` and returns it as an SplFixedArray. + * + * @return \SplFixedArray Array of all the items in the longest common subsequence. + */ + public function getLCS() { + // skip all items at the beginning and the end that are the same + // this reduces the size of the table and improves performance + $offsetStart = $offsetEnd = 0; + while ($offsetStart < $this->sizeA && $offsetStart < $this->sizeB && $this->a[$offsetStart] === $this->b[$offsetStart]) { + $offsetStart++; + } + while ($offsetEnd < $this->sizeA && $offsetEnd < $this->sizeB && $this->a[$this->sizeA - 1 - $offsetEnd] === $this->b[$this->sizeB - 1 - $offsetEnd]) { + $offsetEnd++; + } + + // both arrays are the same + if ($offsetStart === $offsetEnd) { + return \SplFixedArray::fromArray($this->a); + } + + // allocate table that keeps track of the subsequence lengths + // add 1 to fit the line of zeroes at the top and at the left + $tableHeight = $this->sizeA + 1 - $offsetStart - $offsetEnd; + $tableWidth = $this->sizeB + 1 - $offsetStart - $offsetEnd; + $table = new \SplFixedArray($tableHeight); + for ($i = 0; $i < $tableHeight; $i++) { + $table[$i] = new \SplFixedArray($tableWidth); + } + + // begin calculating the length of the LCS + for ($y = 0; $y < $tableHeight; $y++) { + for ($x = 0; $x < $tableWidth; $x++) { + // the first row and first column are simply zero + if ($y === 0 || $x === 0) { + $table[$y][$x] = 0; + continue; + } + + $valueA = $this->a[$y - 1 + $offsetStart]; + $valueB = $this->b[$x - 1 + $offsetStart]; + + if ($valueA === $valueB) { + // both items match, the subsequence becomes longer + $table[$y][$x] = $table[$y - 1][$x - 1] + 1; + } + else { + // otherwise the length is the greater length of the entry above and the entry left + $table[$y][$x] = max($table[$y][$x - 1], $table[$y - 1][$x]); + } + } + } + + $x = $this->sizeB - $offsetStart - $offsetEnd; + $y = $this->sizeA - $offsetStart - $offsetEnd; + $lcsLength = $table[$y][$x]; + $i = 0; + + // allocate array of the length of the LCS + $lcs = new \SplFixedArray($table[$y][$x] + $offsetStart + $offsetEnd); + + // until no more items are left in the LCS + while ($table[$y][$x] !== 0) { + // go to the very left of the current length + if ($table[$y][$x - 1] === $table[$y][$x]) { + $x--; + continue; + } + + // go to the very top of the current length + if ($table[$y - 1][$x] === $table[$y][$x]) { + $y--; + continue; + } + + // add the item that incremented the length to the LCS + // we save the items in reverse order as we traverse the table from the back + $lcs[$lcsLength + $offsetStart - (++$i)] = $this->a[$y - 1 + $offsetStart]; + + // and go diagonally to the upper left entry + $x--; + $y--; + } + + for ($i = 0; $i < $offsetStart; $i++) $lcs[$i] = $this->a[$i]; + for ($i = 0; $i < $offsetEnd; $i++) $lcs[$lcsLength + $offsetStart + $i] = $this->a[$this->sizeA - 1 - ($offsetEnd - 1 - $i)]; + + return $lcs; + } + + /** + * Builds the diff out of the longest common subsequence of `$this->a` + * and `$this->b` and saves it in `$this->d`. + */ + protected function calculateDiff() { + if ($this->d !== null) return; + $lcs = $this->getLCS(); + + $this->d = array(); + $positionA = 0; + $positionB = 0; + foreach ($lcs as $item) { + // find next matching item in a, every item in between must be removed + while ($positionA < $this->sizeA && $this->a[$positionA] !== $item) { + $this->d[] = array(self::REMOVED, $this->a[$positionA++]); + } + + // find next matching item in b, every item in between must be removed + while ($positionB < $this->sizeB && $this->b[$positionB] !== $item) { + $this->d[] = array(self::ADDED, $this->b[$positionB++]); + } + + // we are back in our longest common subsequence + $this->d[] = array(self::SAME, $item); + $positionA++; + $positionB++; + } + + // append remaining items of `a` and `b` + while ($positionA < $this->sizeA) { + $this->d[] = array(self::REMOVED, $this->a[$positionA++]); + } + while ($positionB < $this->sizeB) { + $this->d[] = array(self::ADDED, $this->b[$positionB++]); + } + } + + /** + * Returns the raw difference array. + * + * @return array + */ + public function getRawDiff() { + $this->calculateDiff(); + + return $this->d; + } + + /** + * Returns a string like the one generated by unix diff. + * + * @return string + */ + public function getUnixDiff($context = 2) { + $d = $this->getRawDiff(); + + $result = array(); + $result[] = "--- a"; + $result[] = "+++ b"; + + $inContext = 0; + $leftStart = 1; + $rightStart = 1; + for ($i = 0, $max = count($d); $i < $max; $i++) { + list($type, $line) = $d[$i]; + + if ($type == self::REMOVED || $type == self::ADDED) { + // calculate start of context + $start = max($i - $context, 0); + + // calculate start in left array + $leftStart -= $i - $start; + // ... and in right array + $rightStart -= $i - $start; + + // set current context size + $inContext = $context; + + // search the end of the current window + $plus = $minus = 0; + for ($j = $start; $j < $max; $j++) { + list($type, $line) = $d[$j]; + + switch ($type) { + case self::REMOVED: + // reset context size + $inContext = $context; + $minus++; + break; + case self::ADDED: + // reset context size + $inContext = $context; + $plus++; + break; + case self::SAME: + if ($inContext) { + // decrement remaining context + $inContext--; + } + else { + // context is zero, but this isn't an addition or removal + // check whether the next context would overlap + for ($k = $j; $k < $max && $k <= $j + $context; $k++) { + if ($d[$k][0] != self::SAME) { + $inContext = $k - $j; + continue 2; + } + } + break 2; + } + break; + } + } + + // calculate marker + $result[] = '@@ -'.($leftStart).(($j - $plus - $start) > 1 ? ','.($j - $plus - $start) : '').' +'.($rightStart).(($j - $minus - $start) > 1 ? ','.($j - $minus - $start) : '').' @@'; + + // append lines + foreach (array_slice($d, $start, $j - $start) as $item) $result[] = implode('', $item); + + // shift the offset by the shown lines + $i = $j; + $leftStart += $j - $start - $plus; + $rightStart += $j - $start - $minus; + } + + // line is skipped + $leftStart++; + $rightStart++; + } + + return implode("\n", $result); + } + + /** + * @see Diff::getUnixDiff() + */ + public function __toString() { + return $this->getUnixDiff(); + } +} -- 2.20.1