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