5 * Copyright (c) 2002-2011, Sebastian Bergmann <sebastian@phpunit.de>.
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
12 * * Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
15 * * Redistributions in binary form must reproduce the above copyright
16 * notice, this list of conditions and the following disclaimer in
17 * the documentation and/or other materials provided with the
20 * * Neither the name of Sebastian Bergmann nor the names of his
21 * contributors may be used to endorse or promote products derived
22 * from this software without specific prior written permission.
24 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
27 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
28 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
29 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
30 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
31 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
32 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
34 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35 * POSSIBILITY OF SUCH DAMAGE.
39 * @author Sebastian Bergmann <sebastian@phpunit.de>
40 * @author Kore Nordmann <mail@kore-nordmann.de>
41 * @copyright 2002-2011 Sebastian Bergmann <sebastian@phpunit.de>
42 * @license http://www.opensource.org/licenses/bsd-license.php BSD License
43 * @link http://www.phpunit.de/
44 * @since File available since Release 3.4.0
48 * Diff implementation.
52 * @author Sebastian Bergmann <sebastian@phpunit.de>
53 * @author Kore Nordmann <mail@kore-nordmann.de>
54 * @copyright 2002-2011 Sebastian Bergmann <sebastian@phpunit.de>
55 * @license http://www.opensource.org/licenses/bsd-license.php BSD License
56 * @version Release: 3.5.14
57 * @link http://www.phpunit.de/
58 * @since Class available since Release 3.4.0
60 class PHPUnit_Util_Diff
63 * Returns the diff between two arrays or strings.
65 * @param array|string $from
66 * @param array|string $to
69 public static function diff($from, $to)
71 if (is_string($from)) {
72 $from = preg_split('(\r\n|\r|\n)', $from);
76 $to = preg_split('(\r\n|\r|\n)', $to);
79 $buffer = "--- Expected\n+++ Actual\n";
82 $fromLength = count($from);
83 $toLength = count($to);
84 $length = min($fromLength, $toLength);
86 for ($i = 0; $i < $length; ++$i) {
87 if ($from[$i] === $to[$i]) {
89 unset($from[$i], $to[$i]);
97 for ($i = 1; $i < $length; ++$i) {
98 if ($from[$fromLength - $i] === $to[$toLength - $i]) {
99 array_unshift($end, $from[$fromLength - $i]);
100 unset($from[$fromLength - $i], $to[$toLength - $i]);
106 $common = self::longestCommonSubsequence(
107 array_values($from), array_values($to)
113 foreach ($start as $token) {
114 $diff[] = array($token, 0 /* OLD */);
120 foreach ($common as $token) {
121 while ((($fromToken = reset($from)) !== $token)) {
122 $diff[] = array(array_shift($from), 2 /* REMOVED */);
125 while ((($toToken = reset($to)) !== $token)) {
126 $diff[] = array(array_shift($to), 1 /* ADDED */);
129 $diff[] = array($token, 0 /* OLD */);
135 while (($token = array_shift($from)) !== NULL) {
136 $diff[] = array($token, 2 /* REMOVED */);
139 while (($token = array_shift($to)) !== NULL) {
140 $diff[] = array($token, 1 /* ADDED */);
143 foreach ($end as $token) {
144 $diff[] = array($token, 0 /* OLD */);
151 foreach ($diff as $line) {
152 if ($line[1] === 0 /* OLD */) {
153 if ($inOld === FALSE) {
158 else if ($inOld !== FALSE) {
159 if (($i - $inOld) > 5) {
160 $old[$inOld] = $i - 1;
169 $start = isset($old[0]) ? $old[0] : 0;
173 if ($tmp = array_search($end, $old)) {
179 for ($i = $start; $i < $end; $i++) {
180 if (isset($old[$i])) {
187 // TODO: Implement chunk range information.
188 $buffer .= "@@ @@\n";
192 if ($diff[$i][1] === 1 /* ADDED */) {
193 $buffer .= '+' . $diff[$i][0] . "\n";
196 else if ($diff[$i][1] === 2 /* REMOVED */) {
197 $buffer .= '-' . $diff[$i][0] . "\n";
201 $buffer .= ' ' . $diff[$i][0] . "\n";
209 * Calculates the longest common subsequence of two arrays.
215 protected static function longestCommonSubsequence(array $from, array $to)
219 $fromLength = count($from);
220 $toLength = count($to);
222 for ($i = 0; $i <= $fromLength; ++$i) {
226 for ($j = 0; $j <= $toLength; ++$j) {
230 for ($i = 1; $i <= $fromLength; ++$i) {
231 for ($j = 1; $j <= $toLength; ++$j) {
232 $matrix[$i][$j] = max(
235 $from[$i-1] === $to[$j-1] ? $matrix[$i-1][$j-1] + 1 : 0
243 while ($i > 0 && $j > 0) {
244 if ($from[$i-1] === $to[$j-1]) {
245 array_unshift($common, $from[$i-1]);
250 else if ($matrix[$i][$j-1] > $matrix[$i-1][$j]) {