[ Index ] |
PHP Cross Reference of WordPress |
[Summary view] [Print] [Text view]
1 <?php 2 /** 3 * Class used internally by Text_Diff to actually compute the diffs. 4 * 5 * This class is implemented using native PHP code. 6 * 7 * The algorithm used here is mostly lifted from the perl module 8 * Algorithm::Diff (version 1.06) by Ned Konz, which is available at: 9 * http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip 10 * 11 * More ideas are taken from: http://www.ics.uci.edu/~eppstein/161/960229.html 12 * 13 * Some ideas (and a bit of code) are taken from analyze.c, of GNU 14 * diffutils-2.7, which can be found at: 15 * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz 16 * 17 * Some ideas (subdivision by NCHUNKS > 2, and some optimizations) are from 18 * Geoffrey T. Dairiki <dairiki@dairiki.org>. The original PHP version of this 19 * code was written by him, and is used/adapted with his permission. 20 * 21 * Copyright 2004-2010 The Horde Project (http://www.horde.org/) 22 * 23 * See the enclosed file COPYING for license information (LGPL). If you did 24 * not receive this file, see http://opensource.org/licenses/lgpl-license.php. 25 * 26 * @author Geoffrey T. Dairiki <dairiki@dairiki.org> 27 * @package Text_Diff 28 */ 29 class Text_Diff_Engine_native { 30 31 function diff($from_lines, $to_lines) 32 { 33 array_walk($from_lines, array('Text_Diff', 'trimNewlines')); 34 array_walk($to_lines, array('Text_Diff', 'trimNewlines')); 35 36 $n_from = count($from_lines); 37 $n_to = count($to_lines); 38 39 $this->xchanged = $this->ychanged = array(); 40 $this->xv = $this->yv = array(); 41 $this->xind = $this->yind = array(); 42 unset($this->seq); 43 unset($this->in_seq); 44 unset($this->lcs); 45 46 // Skip leading common lines. 47 for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) { 48 if ($from_lines[$skip] !== $to_lines[$skip]) { 49 break; 50 } 51 $this->xchanged[$skip] = $this->ychanged[$skip] = false; 52 } 53 54 // Skip trailing common lines. 55 $xi = $n_from; $yi = $n_to; 56 for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) { 57 if ($from_lines[$xi] !== $to_lines[$yi]) { 58 break; 59 } 60 $this->xchanged[$xi] = $this->ychanged[$yi] = false; 61 } 62 63 // Ignore lines which do not exist in both files. 64 for ($xi = $skip; $xi < $n_from - $endskip; $xi++) { 65 $xhash[$from_lines[$xi]] = 1; 66 } 67 for ($yi = $skip; $yi < $n_to - $endskip; $yi++) { 68 $line = $to_lines[$yi]; 69 if (($this->ychanged[$yi] = empty($xhash[$line]))) { 70 continue; 71 } 72 $yhash[$line] = 1; 73 $this->yv[] = $line; 74 $this->yind[] = $yi; 75 } 76 for ($xi = $skip; $xi < $n_from - $endskip; $xi++) { 77 $line = $from_lines[$xi]; 78 if (($this->xchanged[$xi] = empty($yhash[$line]))) { 79 continue; 80 } 81 $this->xv[] = $line; 82 $this->xind[] = $xi; 83 } 84 85 // Find the LCS. 86 $this->_compareseq(0, count($this->xv), 0, count($this->yv)); 87 88 // Merge edits when possible. 89 $this->_shiftBoundaries($from_lines, $this->xchanged, $this->ychanged); 90 $this->_shiftBoundaries($to_lines, $this->ychanged, $this->xchanged); 91 92 // Compute the edit operations. 93 $edits = array(); 94 $xi = $yi = 0; 95 while ($xi < $n_from || $yi < $n_to) { 96 assert($yi < $n_to || $this->xchanged[$xi]); 97 assert($xi < $n_from || $this->ychanged[$yi]); 98 99 // Skip matching "snake". 100 $copy = array(); 101 while ($xi < $n_from && $yi < $n_to 102 && !$this->xchanged[$xi] && !$this->ychanged[$yi]) { 103 $copy[] = $from_lines[$xi++]; 104 ++$yi; 105 } 106 if ($copy) { 107 $edits[] = new Text_Diff_Op_copy($copy); 108 } 109 110 // Find deletes & adds. 111 $delete = array(); 112 while ($xi < $n_from && $this->xchanged[$xi]) { 113 $delete[] = $from_lines[$xi++]; 114 } 115 116 $add = array(); 117 while ($yi < $n_to && $this->ychanged[$yi]) { 118 $add[] = $to_lines[$yi++]; 119 } 120 121 if ($delete && $add) { 122 $edits[] = new Text_Diff_Op_change($delete, $add); 123 } elseif ($delete) { 124 $edits[] = new Text_Diff_Op_delete($delete); 125 } elseif ($add) { 126 $edits[] = new Text_Diff_Op_add($add); 127 } 128 } 129 130 return $edits; 131 } 132 133 /** 134 * Divides the Largest Common Subsequence (LCS) of the sequences (XOFF, 135 * XLIM) and (YOFF, YLIM) into NCHUNKS approximately equally sized 136 * segments. 137 * 138 * Returns (LCS, PTS). LCS is the length of the LCS. PTS is an array of 139 * NCHUNKS+1 (X, Y) indexes giving the diving points between sub 140 * sequences. The first sub-sequence is contained in (X0, X1), (Y0, Y1), 141 * the second in (X1, X2), (Y1, Y2) and so on. Note that (X0, Y0) == 142 * (XOFF, YOFF) and (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM). 143 * 144 * This function assumes that the first lines of the specified portions of 145 * the two files do not match, and likewise that the last lines do not 146 * match. The caller must trim matching lines from the beginning and end 147 * of the portions it is going to specify. 148 */ 149 function _diag ($xoff, $xlim, $yoff, $ylim, $nchunks) 150 { 151 $flip = false; 152 153 if ($xlim - $xoff > $ylim - $yoff) { 154 /* Things seems faster (I'm not sure I understand why) when the 155 * shortest sequence is in X. */ 156 $flip = true; 157 list ($xoff, $xlim, $yoff, $ylim) 158 = array($yoff, $ylim, $xoff, $xlim); 159 } 160 161 if ($flip) { 162 for ($i = $ylim - 1; $i >= $yoff; $i--) { 163 $ymatches[$this->xv[$i]][] = $i; 164 } 165 } else { 166 for ($i = $ylim - 1; $i >= $yoff; $i--) { 167 $ymatches[$this->yv[$i]][] = $i; 168 } 169 } 170 171 $this->lcs = 0; 172 $this->seq[0]= $yoff - 1; 173 $this->in_seq = array(); 174 $ymids[0] = array(); 175 176 $numer = $xlim - $xoff + $nchunks - 1; 177 $x = $xoff; 178 for ($chunk = 0; $chunk < $nchunks; $chunk++) { 179 if ($chunk > 0) { 180 for ($i = 0; $i <= $this->lcs; $i++) { 181 $ymids[$i][$chunk - 1] = $this->seq[$i]; 182 } 183 } 184 185 $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $chunk) / $nchunks); 186 for (; $x < $x1; $x++) { 187 $line = $flip ? $this->yv[$x] : $this->xv[$x]; 188 if (empty($ymatches[$line])) { 189 continue; 190 } 191 $matches = $ymatches[$line]; 192 reset($matches); 193 while ($y = current($matches)) { 194 if (empty($this->in_seq[$y])) { 195 $k = $this->_lcsPos($y); 196 assert($k > 0); 197 $ymids[$k] = $ymids[$k - 1]; 198 break; 199 } 200 next($matches); 201 } 202 while ($y = current($matches)) { 203 if ($y > $this->seq[$k - 1]) { 204 assert($y <= $this->seq[$k]); 205 /* Optimization: this is a common case: next match is 206 * just replacing previous match. */ 207 $this->in_seq[$this->seq[$k]] = false; 208 $this->seq[$k] = $y; 209 $this->in_seq[$y] = 1; 210 } elseif (empty($this->in_seq[$y])) { 211 $k = $this->_lcsPos($y); 212 assert($k > 0); 213 $ymids[$k] = $ymids[$k - 1]; 214 } 215 next($matches); 216 } 217 } 218 } 219 220 $seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff); 221 $ymid = $ymids[$this->lcs]; 222 for ($n = 0; $n < $nchunks - 1; $n++) { 223 $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks); 224 $y1 = $ymid[$n] + 1; 225 $seps[] = $flip ? array($y1, $x1) : array($x1, $y1); 226 } 227 $seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim); 228 229 return array($this->lcs, $seps); 230 } 231 232 function _lcsPos($ypos) 233 { 234 $end = $this->lcs; 235 if ($end == 0 || $ypos > $this->seq[$end]) { 236 $this->seq[++$this->lcs] = $ypos; 237 $this->in_seq[$ypos] = 1; 238 return $this->lcs; 239 } 240 241 $beg = 1; 242 while ($beg < $end) { 243 $mid = (int)(($beg + $end) / 2); 244 if ($ypos > $this->seq[$mid]) { 245 $beg = $mid + 1; 246 } else { 247 $end = $mid; 248 } 249 } 250 251 assert($ypos != $this->seq[$end]); 252 253 $this->in_seq[$this->seq[$end]] = false; 254 $this->seq[$end] = $ypos; 255 $this->in_seq[$ypos] = 1; 256 return $end; 257 } 258 259 /** 260 * Finds LCS of two sequences. 261 * 262 * The results are recorded in the vectors $this->{x,y}changed[], by 263 * storing a 1 in the element for each line that is an insertion or 264 * deletion (ie. is not in the LCS). 265 * 266 * The subsequence of file 0 is (XOFF, XLIM) and likewise for file 1. 267 * 268 * Note that XLIM, YLIM are exclusive bounds. All line numbers are 269 * origin-0 and discarded lines are not counted. 270 */ 271 function _compareseq ($xoff, $xlim, $yoff, $ylim) 272 { 273 /* Slide down the bottom initial diagonal. */ 274 while ($xoff < $xlim && $yoff < $ylim 275 && $this->xv[$xoff] == $this->yv[$yoff]) { 276 ++$xoff; 277 ++$yoff; 278 } 279 280 /* Slide up the top initial diagonal. */ 281 while ($xlim > $xoff && $ylim > $yoff 282 && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) { 283 --$xlim; 284 --$ylim; 285 } 286 287 if ($xoff == $xlim || $yoff == $ylim) { 288 $lcs = 0; 289 } else { 290 /* This is ad hoc but seems to work well. $nchunks = 291 * sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5); $nchunks = 292 * max(2,min(8,(int)$nchunks)); */ 293 $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1; 294 list($lcs, $seps) 295 = $this->_diag($xoff, $xlim, $yoff, $ylim, $nchunks); 296 } 297 298 if ($lcs == 0) { 299 /* X and Y sequences have no common subsequence: mark all 300 * changed. */ 301 while ($yoff < $ylim) { 302 $this->ychanged[$this->yind[$yoff++]] = 1; 303 } 304 while ($xoff < $xlim) { 305 $this->xchanged[$this->xind[$xoff++]] = 1; 306 } 307 } else { 308 /* Use the partitions to split this problem into subproblems. */ 309 reset($seps); 310 $pt1 = $seps[0]; 311 while ($pt2 = next($seps)) { 312 $this->_compareseq ($pt1[0], $pt2[0], $pt1[1], $pt2[1]); 313 $pt1 = $pt2; 314 } 315 } 316 } 317 318 /** 319 * Adjusts inserts/deletes of identical lines to join changes as much as 320 * possible. 321 * 322 * We do something when a run of changed lines include a line at one end 323 * and has an excluded, identical line at the other. We are free to 324 * choose which identical line is included. `compareseq' usually chooses 325 * the one at the beginning, but usually it is cleaner to consider the 326 * following identical line to be the "change". 327 * 328 * This is extracted verbatim from analyze.c (GNU diffutils-2.7). 329 */ 330 function _shiftBoundaries($lines, &$changed, $other_changed) 331 { 332 $i = 0; 333 $j = 0; 334 335 assert(count($lines) == count($changed)); 336 $len = count($lines); 337 $other_len = count($other_changed); 338 339 while (1) { 340 /* Scan forward to find the beginning of another run of 341 * changes. Also keep track of the corresponding point in the 342 * other file. 343 * 344 * Throughout this code, $i and $j are adjusted together so that 345 * the first $i elements of $changed and the first $j elements of 346 * $other_changed both contain the same number of zeros (unchanged 347 * lines). 348 * 349 * Furthermore, $j is always kept so that $j == $other_len or 350 * $other_changed[$j] == false. */ 351 while ($j < $other_len && $other_changed[$j]) { 352 $j++; 353 } 354 355 while ($i < $len && ! $changed[$i]) { 356 assert($j < $other_len && ! $other_changed[$j]); 357 $i++; $j++; 358 while ($j < $other_len && $other_changed[$j]) { 359 $j++; 360 } 361 } 362 363 if ($i == $len) { 364 break; 365 } 366 367 $start = $i; 368 369 /* Find the end of this run of changes. */ 370 while (++$i < $len && $changed[$i]) { 371 continue; 372 } 373 374 do { 375 /* Record the length of this run of changes, so that we can 376 * later determine whether the run has grown. */ 377 $runlength = $i - $start; 378 379 /* Move the changed region back, so long as the previous 380 * unchanged line matches the last changed one. This merges 381 * with previous changed regions. */ 382 while ($start > 0 && $lines[$start - 1] == $lines[$i - 1]) { 383 $changed[--$start] = 1; 384 $changed[--$i] = false; 385 while ($start > 0 && $changed[$start - 1]) { 386 $start--; 387 } 388 assert($j > 0); 389 while ($other_changed[--$j]) { 390 continue; 391 } 392 assert($j >= 0 && !$other_changed[$j]); 393 } 394 395 /* Set CORRESPONDING to the end of the changed run, at the 396 * last point where it corresponds to a changed run in the 397 * other file. CORRESPONDING == LEN means no such point has 398 * been found. */ 399 $corresponding = $j < $other_len ? $i : $len; 400 401 /* Move the changed region forward, so long as the first 402 * changed line matches the following unchanged one. This 403 * merges with following changed regions. Do this second, so 404 * that if there are no merges, the changed region is moved 405 * forward as far as possible. */ 406 while ($i < $len && $lines[$start] == $lines[$i]) { 407 $changed[$start++] = false; 408 $changed[$i++] = 1; 409 while ($i < $len && $changed[$i]) { 410 $i++; 411 } 412 413 assert($j < $other_len && ! $other_changed[$j]); 414 $j++; 415 if ($j < $other_len && $other_changed[$j]) { 416 $corresponding = $i; 417 while ($j < $other_len && $other_changed[$j]) { 418 $j++; 419 } 420 } 421 } 422 } while ($runlength != $i - $start); 423 424 /* If possible, move the fully-merged run of changes back to a 425 * corresponding run in the other file. */ 426 while ($corresponding < $i) { 427 $changed[--$start] = 1; 428 $changed[--$i] = 0; 429 assert($j > 0); 430 while ($other_changed[--$j]) { 431 continue; 432 } 433 assert($j >= 0 && !$other_changed[$j]); 434 } 435 } 436 } 437 438 }
title
Description
Body
title
Description
Body
title
Description
Body
title
Body
Generated: Sat Dec 7 01:00:02 2024 | Cross-referenced by PHPXref 0.7.1 |