1<?php
2/**
3 * PHPUnit
4 *
5 * Copyright (c) 2001-2012, Sebastian Bergmann <sebastian@phpunit.de>.
6 * All rights reserved.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 *   * Redistributions of source code must retain the above copyright
13 *     notice, this list of conditions and the following disclaimer.
14 *
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
18 *     distribution.
19 *
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.
23 *
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.
36 *
37 * @package    PHPUnit
38 * @subpackage Util
39 * @author     Sebastian Bergmann <sebastian@phpunit.de>
40 * @author     Kore Nordmann <mail@kore-nordmann.de>
41 * @copyright  2001-2012 Sebastian Bergmann <sebastian@phpunit.de>
42 * @license    http://www.opensource.org/licenses/BSD-3-Clause  The BSD 3-Clause License
43 * @link       http://www.phpunit.de/
44 * @since      File available since Release 3.4.0
45 */
46
47/**
48 * Diff implementation.
49 *
50 * @package    PHPUnit
51 * @subpackage Util
52 * @author     Sebastian Bergmann <sebastian@phpunit.de>
53 * @author     Kore Nordmann <mail@kore-nordmann.de>
54 * @copyright  2001-2012 Sebastian Bergmann <sebastian@phpunit.de>
55 * @license    http://www.opensource.org/licenses/BSD-3-Clause  The BSD 3-Clause License
56 * @version    Release: @package_version@
57 * @link       http://www.phpunit.de/
58 * @since      Class available since Release 3.4.0
59 */
60class PHPUnit_Util_Diff
61{
62    /**
63     * Returns the diff between two arrays or strings as string.
64     *
65     * @param  array|string $from
66     * @param  array|string $to
67     * @return string
68     */
69    public static function diff($from, $to)
70    {
71        $buffer= "--- Expected\n+++ Actual\n";
72        $diff  = self::diffToArray($from,$to);
73
74        $inOld = FALSE;
75        $i     = 0;
76        $old   = array();
77
78        foreach ($diff as $line) {
79            if ($line[1] ===  0 /* OLD */) {
80                if ($inOld === FALSE) {
81                    $inOld = $i;
82                }
83            }
84
85            else if ($inOld !== FALSE) {
86                if (($i - $inOld) > 5) {
87                    $old[$inOld] = $i - 1;
88                }
89
90                $inOld = FALSE;
91            }
92
93            ++$i;
94        }
95
96        $start = isset($old[0]) ? $old[0] : 0;
97        $end   = count($diff);
98        $i     = 0;
99
100        if ($tmp = array_search($end, $old)) {
101            $end = $tmp;
102        }
103
104        $newChunk = TRUE;
105
106        for ($i = $start; $i < $end; $i++) {
107            if (isset($old[$i])) {
108                $buffer  .= "\n";
109                $newChunk = TRUE;
110                $i        = $old[$i];
111            }
112
113            if ($newChunk) {
114                $buffer  .= "@@ @@\n";
115                $newChunk = FALSE;
116            }
117
118            if ($diff[$i][1] === 1 /* ADDED */) {
119                $buffer .= '+' . $diff[$i][0] . "\n";
120            }
121
122            else if ($diff[$i][1] === 2 /* REMOVED */) {
123                $buffer .= '-' . $diff[$i][0] . "\n";
124            }
125
126            else {
127                $buffer .= ' ' . $diff[$i][0] . "\n";
128            }
129        }
130
131        return $buffer;
132    }
133
134    /**
135     * Returns the diff between two arrays or strings as array.
136     *
137     * every array-entry containts two elements:
138     *   - [0] => string $token
139     *   - [1] => 2|1|0
140     *
141     * - 2: REMOVED: $token was removed from $from
142     * - 1: ADDED: $token was added to $from
143     * - 0: OLD: $token is not changed in $to
144     *
145     * @param  array|string $from
146     * @param  array|string $to
147     * @return array
148     */
149    public static function diffToArray($from, $to)
150    {
151        preg_match_all('(\r\n|\r|\n)', $from, $fromMatches);
152        preg_match_all('(\r\n|\r|\n)', $to, $toMatches);
153
154        if (is_string($from)) {
155            $from = preg_split('(\r\n|\r|\n)', $from);
156        }
157
158        if (is_string($to)) {
159            $to = preg_split('(\r\n|\r|\n)', $to);
160        }
161
162        $start      = array();
163        $end        = array();
164        $fromLength = count($from);
165        $toLength   = count($to);
166        $length     = min($fromLength, $toLength);
167
168        for ($i = 0; $i < $length; ++$i) {
169            if ($from[$i] === $to[$i]) {
170                $start[] = $from[$i];
171                unset($from[$i], $to[$i]);
172            } else {
173                break;
174            }
175        }
176
177        $length -= $i;
178
179        for ($i = 1; $i < $length; ++$i) {
180            if ($from[$fromLength - $i] === $to[$toLength - $i]) {
181                array_unshift($end, $from[$fromLength - $i]);
182                unset($from[$fromLength - $i], $to[$toLength - $i]);
183            } else {
184                break;
185            }
186        }
187
188        $common = self::longestCommonSubsequence(
189          array_values($from), array_values($to)
190        );
191
192        $diff = array();
193        $line = 0;
194
195        if (isset($fromMatches[0]) && $toMatches[0] &&
196            count($fromMatches[0]) === count($toMatches[0]) &&
197            $fromMatches[0] !== $toMatches[0]) {
198            $diff[] = array(
199              '#Warning: Strings contain different line endings!', 0
200            );
201        }
202
203        foreach ($start as $token) {
204            $diff[] = array($token, 0 /* OLD */);
205        }
206
207        reset($from);
208        reset($to);
209
210        foreach ($common as $token) {
211            while ((($fromToken = reset($from)) !== $token)) {
212                $diff[] = array(array_shift($from), 2 /* REMOVED */);
213            }
214
215            while ((($toToken = reset($to)) !== $token)) {
216                $diff[] = array(array_shift($to), 1 /* ADDED */);
217            }
218
219            $diff[] = array($token, 0 /* OLD */);
220
221            array_shift($from);
222            array_shift($to);
223        }
224
225        while (($token = array_shift($from)) !== NULL) {
226            $diff[] = array($token, 2 /* REMOVED */);
227        }
228
229        while (($token = array_shift($to)) !== NULL) {
230            $diff[] = array($token, 1 /* ADDED */);
231        }
232
233        foreach ($end as $token) {
234            $diff[] = array($token, 0 /* OLD */);
235        }
236
237        return $diff;
238    }
239
240    /**
241     * Calculates the longest common subsequence of two arrays.
242     *
243     * @param  array $from
244     * @param  array $to
245     * @return array
246     */
247    protected static function longestCommonSubsequence(array $from, array $to)
248    {
249        $common     = array();
250        $matrix     = array();
251        $fromLength = count($from);
252        $toLength   = count($to);
253
254        for ($i = 0; $i <= $fromLength; ++$i) {
255            $matrix[$i][0] = 0;
256        }
257
258        for ($j = 0; $j <= $toLength; ++$j) {
259            $matrix[0][$j] = 0;
260        }
261
262        for ($i = 1; $i <= $fromLength; ++$i) {
263            for ($j = 1; $j <= $toLength; ++$j) {
264                $matrix[$i][$j] = max(
265                  $matrix[$i-1][$j],
266                  $matrix[$i][$j-1],
267                  $from[$i-1] === $to[$j-1] ? $matrix[$i-1][$j-1] + 1 : 0
268                );
269            }
270        }
271
272        $i = $fromLength;
273        $j = $toLength;
274
275        while ($i > 0 && $j > 0) {
276            if ($from[$i-1] === $to[$j-1]) {
277                array_unshift($common, $from[$i-1]);
278                --$i;
279                --$j;
280            }
281
282            else if ($matrix[$i][$j-1] > $matrix[$i-1][$j]) {
283                --$j;
284            }
285
286            else {
287                --$i;
288            }
289        }
290
291        return $common;
292    }
293}
294