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