tests/PHPUnit/PHPUnit/Util/Diff.php

   1 <?php
   2 /**
   3  * PHPUnit
   4  *
   5  * Copyright (c) 2002-2011, 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  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
  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  2002-2011 Sebastian Bergmann <sebastian@phpunit.de>
  55  * @license    http://www.opensource.org/licenses/bsd-license.php  BSD License
  56  * @version    Release: 3.5.13
  57  * @link       http://www.phpunit.de/
  58  * @since      Class available since Release 3.4.0
  59  */
  60 class PHPUnit_Util_Diff
  61 {
  62     /**
  63      * Returns the diff between two arrays or strings.
  64      *
  65      * @param  array|string $from
  66      * @param  array|string $to
  67      * @return string
  68      */
  69     public static function diff($from, $to)
  70     {
  71         if (is_string($from)) {
  72             $from = preg_split('(\r\n|\r|\n)', $from);
  73         }
  74
  75         if (is_string($to)) {
  76             $to = preg_split('(\r\n|\r|\n)', $to);
  77         }
  78
  79         $buffer     = "--- Expected\n+++ Actual\n";
  80         $start      = array();
  81         $end        = array();
  82         $fromLength = count($from);
  83         $toLength   = count($to);
  84         $length     = min($fromLength, $toLength);
  85
  86         for ($i = 0; $i < $length; ++$i) {
  87             if ($from[$i] === $to[$i]) {
  88                 $start[] = $from[$i];
  89                 unset($from[$i], $to[$i]);
  90             } else {
  91                 break;
  92             }
  93         }
  94
  95         $length -= $i;
  96
  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]);
 101             } else {
 102                 break;
 103             }
 104         }
 105
 106         $common = self::longestCommonSubsequence(
 107           array_values($from), array_values($to)
 108         );
 109
 110         $diff = array();
 111         $line = 0;
 112
 113         foreach ($start as $token) {
 114             $diff[] = array($token, 0 /* OLD */);
 115         }
 116
 117         reset($from);
 118         reset($to);
 119
 120         foreach ($common as $token) {
 121             while ((($fromToken = reset($from)) !== $token)) {
 122                 $diff[] = array(array_shift($from), 2 /* REMOVED */);
 123             }
 124
 125             while ((($toToken = reset($to)) !== $token)) {
 126                 $diff[] = array(array_shift($to), 1 /* ADDED */);
 127             }
 128
 129             $diff[] = array($token, 0 /* OLD */);
 130
 131             array_shift($from);
 132             array_shift($to);
 133         }
 134
 135         while (($token = array_shift($from)) !== NULL) {
 136             $diff[] = array($token, 2 /* REMOVED */);
 137         }
 138
 139         while (($token = array_shift($to)) !== NULL) {
 140             $diff[] = array($token, 1 /* ADDED */);
 141         }
 142
 143         foreach ($end as $token) {
 144             $diff[] = array($token, 0 /* OLD */);
 145         }
 146
 147         $inOld = FALSE;
 148         $i     = 0;
 149         $old   = array();
 150
 151         foreach ($diff as $line) {
 152             if ($line[1] === 0 /* OLD */) {
 153                 if ($inOld === FALSE) {
 154                     $inOld = $i;
 155                 }
 156             }
 157
 158             else if ($inOld !== FALSE) {
 159                 if (($i - $inOld) > 5) {
 160                     $old[$inOld] = $i - 1;
 161                 }
 162
 163                 $inOld = FALSE;
 164             }
 165
 166             ++$i;
 167         }
 168
 169         $start = isset($old[0]) ? $old[0] : 0;
 170         $end   = count($diff);
 171         $i     = 0;
 172
 173         if ($tmp = array_search($end, $old)) {
 174             $end = $tmp;
 175         }
 176
 177         $newChunk = TRUE;
 178
 179         for ($i = $start; $i < $end; $i++) {
 180             if (isset($old[$i])) {
 181                 $buffer  .= "\n";
 182                 $newChunk = TRUE;
 183                 $i        = $old[$i];
 184             }
 185
 186             if ($newChunk) {
 187                 // TODO: Implement chunk range information.
 188                 $buffer  .= "@@ @@\n";
 189                 $newChunk = FALSE;
 190             }
 191
 192             if ($diff[$i][1] === 1 /* ADDED */) {
 193                 $buffer .= '+' . $diff[$i][0] . "\n";
 194             }
 195
 196             else if ($diff[$i][1] === 2 /* REMOVED */) {
 197                 $buffer .= '-' . $diff[$i][0] . "\n";
 198             }
 199
 200             else {
 201                 $buffer .= ' ' . $diff[$i][0] . "\n";
 202             }
 203         }
 204
 205         return $buffer;
 206     }
 207
 208     /**
 209      * Calculates the longest common subsequence of two arrays.
 210      *
 211      * @param  array $from
 212      * @param  array $to
 213      * @return array
 214      */
 215     protected static function longestCommonSubsequence(array $from, array $to)
 216     {
 217         $common     = array();
 218         $matrix     = array();
 219         $fromLength = count($from);
 220         $toLength   = count($to);
 221
 222         for ($i = 0; $i <= $fromLength; ++$i) {
 223             $matrix[$i][0] = 0;
 224         }
 225
 226         for ($j = 0; $j <= $toLength; ++$j) {
 227             $matrix[0][$j] = 0;
 228         }
 229
 230         for ($i = 1; $i <= $fromLength; ++$i) {
 231             for ($j = 1; $j <= $toLength; ++$j) {
 232                 $matrix[$i][$j] = max(
 233                   $matrix[$i-1][$j],
 234                   $matrix[$i][$j-1],
 235                   $from[$i-1] === $to[$j-1] ? $matrix[$i-1][$j-1] + 1 : 0
 236                 );
 237             }
 238         }
 239
 240         $i = $fromLength;
 241         $j = $toLength;
 242
 243         while ($i > 0 && $j > 0) {
 244             if ($from[$i-1] === $to[$j-1]) {
 245                 array_unshift($common, $from[$i-1]);
 246                 --$i;
 247                 --$j;
 248             }
 249
 250             else if ($matrix[$i][$j-1] > $matrix[$i-1][$j]) {
 251                 --$j;
 252             }
 253
 254             else {
 255                 --$i;
 256             }
 257         }
 258
 259         return $common;
 260     }
 261 }