From 5b2b95ff81281f88c8a5674d471d9aaec775eb5b Mon Sep 17 00:00:00 2001 From: =?utf8?q?Tim=20D=C3=BCsterhus?= Date: Thu, 16 Oct 2014 22:38:45 +0200 Subject: [PATCH] Fix edge case in Diff.class.php causing it to error out Previously it was possible for the startOffset and endOffset to overlap for certain arrays, causing the algorithm to completely fall apart. --- wcfsetup/install/files/lib/util/Diff.class.php | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) diff --git a/wcfsetup/install/files/lib/util/Diff.class.php b/wcfsetup/install/files/lib/util/Diff.class.php index ca0bce8cf6..e09b939e63 100644 --- a/wcfsetup/install/files/lib/util/Diff.class.php +++ b/wcfsetup/install/files/lib/util/Diff.class.php @@ -83,7 +83,7 @@ class Diff { 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]) { + while ($offsetEnd < ($this->sizeA - $offsetStart) && $offsetEnd < ($this->sizeB - $offsetStart) && $this->a[$this->sizeA - 1 - $offsetEnd] === $this->b[$this->sizeB - 1 - $offsetEnd]) { $offsetEnd++; } @@ -108,6 +108,7 @@ class Diff { // 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); @@ -139,12 +140,12 @@ class Diff { $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); + $lcs = new \SplFixedArray($lcsLength + $offsetStart + $offsetEnd); // until no more items are left in the LCS + $i = 0; while ($table[$y][$x] !== 0) { // go to the very left of the current length if ($table[$y][$x - 1] === $table[$y][$x]) { -- 2.20.1