Search moodle.org's
Developer Documentation
Developer Documentation
- Bug fixes for general core bugs in 3.10.x will end 8 November 2021 (12 months).
- Bug fixes for security issues in 3.10.x will end 9 May 2022 (18 months).
- PHP version: minimum PHP 7.2.0 Note: minimum PHP version has increased since Moodle 3.8. PHP 7.3.x and 7.4.x are supported too.
/mod/wiki/diff/ -> diff_nwiki.php (source)
1 <?php 2 3 4 # See diff.doc 5 6 // A PHP diff engine for phpwiki. (Taken from phpwiki-1.3.3) 7 // 8 // Copyright (C) 2000, 2001 Geoffrey T. Dairiki <dairiki@dairiki.org> 9 // You may copy this code freely under the conditions of the GPL. 10 // 11 12 define('USE_ASSERTS_IN_WIKI', function_exists('assert')); 13 14 class _WikiDiffOp { 15 var $type; 16 var $orig; 17 var $closing; 18 19 function reverse() { 20 trigger_error("pure virtual", E_USER_ERROR); 21 } 22 23 function norig() { 24 return $this->orig ? sizeof($this->orig) : 0; 25 } 26 27 function nclosing() { 28 return $this->closing ? sizeof($this->closing) : 0; 29 } 30 } 31 32 class _WikiDiffOp_Copy extends _WikiDiffOp { 33 var $type = 'copy'; 34 35 public function __construct ($orig, $closing = false) { 36 if (!is_array($closing)) 37 $closing = $orig; 38 $this->orig = $orig; 39 $this->closing = $closing; 40 } 41 42 function reverse() { 43 return new _WikiDiffOp_Copy($this->closing, $this->orig); 44 } 45 } 46 47 class _WikiDiffOp_Delete extends _WikiDiffOp { 48 var $type = 'delete'; 49 50 public function __construct ($lines) { 51 $this->orig = $lines; 52 $this->closing = false; 53 } 54 55 function reverse() { 56 return new _WikiDiffOp_Add($this->orig); 57 } 58 } 59 60 class _WikiDiffOp_Add extends _WikiDiffOp { 61 var $type = 'add'; 62 63 public function __construct ($lines) { 64 $this->closing = $lines; 65 $this->orig = false; 66 } 67 68 function reverse() { 69 return new _WikiDiffOp_Delete($this->closing); 70 } 71 } 72 73 class _WikiDiffOp_Change extends _WikiDiffOp { 74 var $type = 'change'; 75 76 public function __construct ($orig, $closing) { 77 $this->orig = $orig; 78 $this->closing = $closing; 79 } 80 81 function reverse() { 82 return new _WikiDiffOp_Change($this->closing, $this->orig); 83 } 84 } 85 86 87 /** 88 * Class used internally by Diff to actually compute the diffs. 89 * 90 * The algorithm used here is mostly lifted from the perl module 91 * Algorithm::Diff (version 1.06) by Ned Konz, which is available at: 92 * http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip 93 * 94 * More ideas are taken from: 95 * http://www.ics.uci.edu/~eppstein/161/960229.html 96 * 97 * Some ideas are (and a bit of code) are from from analyze.c, from GNU 98 * diffutils-2.7, which can be found at: 99 * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz 100 * 101 * closingly, some ideas (subdivision by NCHUNKS > 2, and some optimizations) 102 * are my own. 103 * 104 * @author Geoffrey T. Dairiki 105 * @access private 106 */ 107 class _WikiDiffEngine 108 { 109 function diff ($from_lines, $to_lines) { 110 $n_from = sizeof($from_lines); 111 $n_to = sizeof($to_lines); 112 113 $this->xchanged = $this->ychanged = array(); 114 $this->xv = $this->yv = array(); 115 $this->xind = $this->yind = array(); 116 unset($this->seq); 117 unset($this->in_seq); 118 unset($this->lcs); 119 120 // Skip leading common lines. 121 for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) { 122 if ($from_lines[$skip] != $to_lines[$skip]) 123 break; 124 $this->xchanged[$skip] = $this->ychanged[$skip] = false; 125 } 126 // Skip trailing common lines. 127 $xi = $n_from; $yi = $n_to; 128 for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) { 129 if ($from_lines[$xi] != $to_lines[$yi]) 130 break; 131 $this->xchanged[$xi] = $this->ychanged[$yi] = false; 132 } 133 134 // Ignore lines which do not exist in both files. 135 for ($xi = $skip; $xi < $n_from - $endskip; $xi++) 136 $xhash[$from_lines[$xi]] = 1; 137 for ($yi = $skip; $yi < $n_to - $endskip; $yi++) { 138 $line = $to_lines[$yi]; 139 if ( ($this->ychanged[$yi] = empty($xhash[$line])) ) 140 continue; 141 $yhash[$line] = 1; 142 $this->yv[] = $line; 143 $this->yind[] = $yi; 144 } 145 for ($xi = $skip; $xi < $n_from - $endskip; $xi++) { 146 $line = $from_lines[$xi]; 147 if ( ($this->xchanged[$xi] = empty($yhash[$line])) ) 148 continue; 149 $this->xv[] = $line; 150 $this->xind[] = $xi; 151 } 152 153 // Find the LCS. 154 $this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv)); 155 156 // Merge edits when possible 157 $this->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged); 158 $this->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged); 159 160 // Compute the edit operations. 161 $edits = array(); 162 $xi = $yi = 0; 163 while ($xi < $n_from || $yi < $n_to) { 164 USE_ASSERTS_IN_WIKI && assert($yi < $n_to || $this->xchanged[$xi]); 165 USE_ASSERTS_IN_WIKI && assert($xi < $n_from || $this->ychanged[$yi]); 166 167 // Skip matching "snake". 168 $copy = array(); 169 while ( $xi < $n_from && $yi < $n_to 170 && !$this->xchanged[$xi] && !$this->ychanged[$yi]) { 171 $copy[] = $from_lines[$xi++]; 172 ++$yi; 173 } 174 if ($copy) 175 $edits[] = new _WikiDiffOp_Copy($copy); 176 177 // Find deletes & adds. 178 $delete = array(); 179 while ($xi < $n_from && $this->xchanged[$xi]) 180 $delete[] = $from_lines[$xi++]; 181 182 $add = array(); 183 while ($yi < $n_to && $this->ychanged[$yi]) 184 $add[] = $to_lines[$yi++]; 185 186 if ($delete && $add) 187 $edits[] = new _WikiDiffOp_Change($delete, $add); 188 elseif ($delete) 189 $edits[] = new _WikiDiffOp_Delete($delete); 190 elseif ($add) 191 $edits[] = new _WikiDiffOp_Add($add); 192 } 193 return $edits; 194 } 195 196 197 /* Divide the Largest Common Subsequence (LCS) of the sequences 198 * [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally 199 * sized segments. 200 * 201 * Returns (LCS, PTS). LCS is the length of the LCS. PTS is an 202 * array of NCHUNKS+1 (X, Y) indexes giving the diving points between 203 * sub sequences. The first sub-sequence is contained in [X0, X1), 204 * [Y0, Y1), the second in [X1, X2), [Y1, Y2) and so on. Note 205 * that (X0, Y0) == (XOFF, YOFF) and 206 * (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM). 207 * 208 * This function assumes that the first lines of the specified portions 209 * of the two files do not match, and likewise that the last lines do not 210 * match. The caller must trim matching lines from the beginning and end 211 * of the portions it is going to specify. 212 */ 213 function _diag ($xoff, $xlim, $yoff, $ylim, $nchunks) { 214 $flip = false; 215 216 if ($xlim - $xoff > $ylim - $yoff) { 217 // Things seems faster (I'm not sure I understand why) 218 // when the shortest sequence in X. 219 $flip = true; 220 list ($xoff, $xlim, $yoff, $ylim) 221 = array( $yoff, $ylim, $xoff, $xlim); 222 } 223 224 if ($flip) 225 for ($i = $ylim - 1; $i >= $yoff; $i--) 226 $ymatches[$this->xv[$i]][] = $i; 227 else 228 for ($i = $ylim - 1; $i >= $yoff; $i--) 229 $ymatches[$this->yv[$i]][] = $i; 230 231 $this->lcs = 0; 232 $this->seq[0]= $yoff - 1; 233 $this->in_seq = array(); 234 $ymids[0] = array(); 235 236 $numer = $xlim - $xoff + $nchunks - 1; 237 $x = $xoff; 238 for ($chunk = 0; $chunk < $nchunks; $chunk++) { 239 if ($chunk > 0) 240 for ($i = 0; $i <= $this->lcs; $i++) 241 $ymids[$i][$chunk-1] = $this->seq[$i]; 242 243 $x1 = $xoff + (int)(($numer + ($xlim-$xoff)*$chunk) / $nchunks); 244 for ( ; $x < $x1; $x++) { 245 $line = $flip ? $this->yv[$x] : $this->xv[$x]; 246 if (empty($ymatches[$line])) 247 continue; 248 $matches = $ymatches[$line]; 249 reset($matches); 250 foreach ($matches as $y) 251 if (empty($this->in_seq[$y])) { 252 $k = $this->_lcs_pos($y); 253 USE_ASSERTS_IN_WIKI && assert($k > 0); 254 $ymids[$k] = $ymids[$k-1]; 255 break; 256 } 257 foreach ($matches as $y) { 258 if ($y > $this->seq[$k-1]) { 259 USE_ASSERTS_IN_WIKI && assert($y < $this->seq[$k]); 260 // Optimization: this is a common case: 261 // next match is just replacing previous match. 262 $this->in_seq[$this->seq[$k]] = false; 263 $this->seq[$k] = $y; 264 $this->in_seq[$y] = 1; 265 } 266 else if (empty($this->in_seq[$y])) { 267 $k = $this->_lcs_pos($y); 268 USE_ASSERTS_IN_WIKI && assert($k > 0); 269 $ymids[$k] = $ymids[$k-1]; 270 } 271 } 272 } 273 } 274 275 $seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff); 276 $ymid = $ymids[$this->lcs]; 277 for ($n = 0; $n < $nchunks - 1; $n++) { 278 $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks); 279 $y1 = $ymid[$n] + 1; 280 $seps[] = $flip ? array($y1, $x1) : array($x1, $y1); 281 } 282 $seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim); 283 284 return array($this->lcs, $seps); 285 } 286 287 function _lcs_pos ($ypos) { 288 $end = $this->lcs; 289 if ($end == 0 || $ypos > $this->seq[$end]) { 290 $this->seq[++$this->lcs] = $ypos; 291 $this->in_seq[$ypos] = 1; 292 return $this->lcs; 293 } 294 295 $beg = 1; 296 while ($beg < $end) { 297 $mid = (int)(($beg + $end) / 2); 298 if ( $ypos > $this->seq[$mid] ) 299 $beg = $mid + 1; 300 else 301 $end = $mid; 302 } 303 304 USE_ASSERTS_IN_WIKI && assert($ypos != $this->seq[$end]); 305 306 $this->in_seq[$this->seq[$end]] = false; 307 $this->seq[$end] = $ypos; 308 $this->in_seq[$ypos] = 1; 309 return $end; 310 } 311 312 /* Find LCS of two sequences. 313 * 314 * The results are recorded in the vectors $this->{x,y}changed[], by 315 * storing a 1 in the element for each line that is an insertion 316 * or deletion (ie. is not in the LCS). 317 * 318 * The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1. 319 * 320 * Note that XLIM, YLIM are exclusive bounds. 321 * All line numbers are origin-0 and discarded lines are not counted. 322 */ 323 function _compareseq ($xoff, $xlim, $yoff, $ylim) { 324 // Slide down the bottom initial diagonal. 325 while ($xoff < $xlim && $yoff < $ylim 326 && $this->xv[$xoff] == $this->yv[$yoff]) { 327 ++$xoff; 328 ++$yoff; 329 } 330 331 // Slide up the top initial diagonal. 332 while ($xlim > $xoff && $ylim > $yoff 333 && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) { 334 --$xlim; 335 --$ylim; 336 } 337 338 if ($xoff == $xlim || $yoff == $ylim) 339 $lcs = 0; 340 else { 341 // This is ad hoc but seems to work well. 342 //$nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5); 343 //$nchunks = max(2,min(8,(int)$nchunks)); 344 $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1; 345 list ($lcs, $seps) 346 = $this->_diag($xoff,$xlim,$yoff, $ylim,$nchunks); 347 } 348 349 if ($lcs == 0) { 350 // X and Y sequences have no common subsequence: 351 // mark all changed. 352 while ($yoff < $ylim) 353 $this->ychanged[$this->yind[$yoff++]] = 1; 354 while ($xoff < $xlim) 355 $this->xchanged[$this->xind[$xoff++]] = 1; 356 } 357 else { 358 // Use the partitions to split this problem into subproblems. 359 reset($seps); 360 $pt1 = $seps[0]; 361 while ($pt2 = next($seps)) { 362 $this->_compareseq ($pt1[0], $pt2[0], $pt1[1], $pt2[1]); 363 $pt1 = $pt2; 364 } 365 } 366 } 367 368 /* Adjust inserts/deletes of identical lines to join changes 369 * as much as possible. 370 * 371 * We do something when a run of changed lines include a 372 * line at one end and has an excluded, identical line at the other. 373 * We are free to choose which identical line is included. 374 * `compareseq' usually chooses the one at the beginning, 375 * but usually it is cleaner to consider the following identical line 376 * to be the "change". 377 * 378 * This is extracted verbatim from analyze.c (GNU diffutils-2.7). 379 */ 380 function _shift_boundaries ($lines, &$changed, $other_changed) { 381 $i = 0; 382 $j = 0; 383 384 USE_ASSERTS_IN_WIKI && assert('sizeof($lines) == sizeof($changed)'); 385 $len = sizeof($lines); 386 $other_len = sizeof($other_changed); 387 388 while (1) { 389 /* 390 * Scan forwards to find beginning of another run of changes. 391 * Also keep track of the corresponding point in the other file. 392 * 393 * Throughout this code, $i and $j are adjusted together so that 394 * the first $i elements of $changed and the first $j elements 395 * of $other_changed both contain the same number of zeros 396 * (unchanged lines). 397 * Furthermore, $j is always kept so that $j == $other_len or 398 * $other_changed[$j] == false. 399 */ 400 while ($j < $other_len && $other_changed[$j]) 401 $j++; 402 403 while ($i < $len && ! $changed[$i]) { 404 USE_ASSERTS_IN_WIKI && assert('$j < $other_len && ! $other_changed[$j]'); 405 $i++; $j++; 406 while ($j < $other_len && $other_changed[$j]) 407 $j++; 408 } 409 410 if ($i == $len) 411 break; 412 413 $start = $i; 414 415 // Find the end of this run of changes. 416 while (++$i < $len && $changed[$i]) 417 continue; 418 419 do { 420 /* 421 * Record the length of this run of changes, so that 422 * we can later determine whether the run has grown. 423 */ 424 $runlength = $i - $start; 425 426 /* 427 * Move the changed region back, so long as the 428 * previous unchanged line matches the last changed one. 429 * This merges with previous changed regions. 430 */ 431 while ($start > 0 && $lines[$start - 1] == $lines[$i - 1]) { 432 $changed[--$start] = 1; 433 $changed[--$i] = false; 434 while ($start > 0 && $changed[$start - 1]) 435 $start--; 436 USE_ASSERTS_IN_WIKI && assert('$j > 0'); 437 while ($other_changed[--$j]) 438 continue; 439 USE_ASSERTS_IN_WIKI && assert('$j >= 0 && !$other_changed[$j]'); 440 } 441 442 /* 443 * Set CORRESPONDING to the end of the changed run, at the last 444 * point where it corresponds to a changed run in the other file. 445 * CORRESPONDING == LEN means no such point has been found. 446 */ 447 $corresponding = $j < $other_len ? $i : $len; 448 449 /* 450 * Move the changed region forward, so long as the 451 * first changed line matches the following unchanged one. 452 * This merges with following changed regions. 453 * Do this second, so that if there are no merges, 454 * the changed region is moved forward as far as possible. 455 */ 456 while ($i < $len && $lines[$start] == $lines[$i]) { 457 $changed[$start++] = false; 458 $changed[$i++] = 1; 459 while ($i < $len && $changed[$i]) 460 $i++; 461 462 USE_ASSERTS_IN_WIKI && assert('$j < $other_len && ! $other_changed[$j]'); 463 $j++; 464 if ($j < $other_len && $other_changed[$j]) { 465 $corresponding = $i; 466 while ($j < $other_len && $other_changed[$j]) 467 $j++; 468 } 469 } 470 } while ($runlength != $i - $start); 471 472 /* 473 * If possible, move the fully-merged run of changes 474 * back to a corresponding run in the other file. 475 */ 476 while ($corresponding < $i) { 477 $changed[--$start] = 1; 478 $changed[--$i] = 0; 479 USE_ASSERTS_IN_WIKI && assert('$j > 0'); 480 while ($other_changed[--$j]) 481 continue; 482 USE_ASSERTS_IN_WIKI && assert('$j >= 0 && !$other_changed[$j]'); 483 } 484 } 485 } 486 } 487 488 /** 489 * Class representing a 'diff' between two sequences of strings. 490 */ 491 class WikiDiff 492 { 493 var $edits; 494 495 /** 496 * Constructor. 497 * Computes diff between sequences of strings. 498 * 499 * @param $from_lines array An array of strings. 500 * (Typically these are lines from a file.) 501 * @param $to_lines array An array of strings. 502 */ 503 public function __construct($from_lines, $to_lines) { 504 $eng = new _WikiDiffEngine; 505 $this->edits = $eng->diff($from_lines, $to_lines); 506 //$this->_check($from_lines, $to_lines); 507 } 508 509 /** 510 * Old syntax of class constructor. Deprecated in PHP7. 511 * 512 * @deprecated since Moodle 3.1 513 */ 514 public function WikiDiff($from_lines, $to_lines) { 515 debugging('Use of class name as constructor is deprecated', DEBUG_DEVELOPER); 516 self::__construct($from_lines, $to_lines); 517 } 518 519 /** 520 * Compute reversed WikiDiff. 521 * 522 * SYNOPSIS: 523 * 524 * $diff = new WikiDiff($lines1, $lines2); 525 * $rev = $diff->reverse(); 526 * @return object A WikiDiff object representing the inverse of the 527 * original diff. 528 */ 529 function reverse () { 530 $rev = $this; 531 $rev->edits = array(); 532 foreach ($this->edits as $edit) { 533 $rev->edits[] = $edit->reverse(); 534 } 535 return $rev; 536 } 537 538 /** 539 * Check for empty diff. 540 * 541 * @return bool True iff two sequences were identical. 542 */ 543 function isEmpty () { 544 foreach ($this->edits as $edit) { 545 if ($edit->type != 'copy') 546 return false; 547 } 548 return true; 549 } 550 551 /** 552 * Compute the length of the Longest Common Subsequence (LCS). 553 * 554 * This is mostly for diagnostic purposed. 555 * 556 * @return int The length of the LCS. 557 */ 558 function lcs () { 559 $lcs = 0; 560 foreach ($this->edits as $edit) { 561 if ($edit->type == 'copy') 562 $lcs += sizeof($edit->orig); 563 } 564 return $lcs; 565 } 566 567 /** 568 * Get the original set of lines. 569 * 570 * This reconstructs the $from_lines parameter passed to the 571 * constructor. 572 * 573 * @return array The original sequence of strings. 574 */ 575 function orig() { 576 $lines = array(); 577 578 foreach ($this->edits as $edit) { 579 if ($edit->orig) 580 array_splice($lines, sizeof($lines), 0, $edit->orig); 581 } 582 return $lines; 583 } 584 585 /** 586 * Get the closing set of lines. 587 * 588 * This reconstructs the $to_lines parameter passed to the 589 * constructor. 590 * 591 * @return array The sequence of strings. 592 */ 593 function closing() { 594 $lines = array(); 595 596 foreach ($this->edits as $edit) { 597 if ($edit->closing) 598 array_splice($lines, sizeof($lines), 0, $edit->closing); 599 } 600 return $lines; 601 } 602 603 /** 604 * Check a WikiDiff for validity. 605 * 606 * This is here only for debugging purposes. 607 */ 608 function _check ($from_lines, $to_lines) { 609 if (serialize($from_lines) != serialize($this->orig())) 610 trigger_error("Reconstructed original doesn't match", E_USER_ERROR); 611 if (serialize($to_lines) != serialize($this->closing())) 612 trigger_error("Reconstructed closing doesn't match", E_USER_ERROR); 613 614 $rev = $this->reverse(); 615 if (serialize($to_lines) != serialize($rev->orig())) 616 trigger_error("Reversed original doesn't match", E_USER_ERROR); 617 if (serialize($from_lines) != serialize($rev->closing())) 618 trigger_error("Reversed closing doesn't match", E_USER_ERROR); 619 620 621 $prevtype = 'none'; 622 foreach ($this->edits as $edit) { 623 if ( $prevtype == $edit->type ) 624 trigger_error("Edit sequence is non-optimal", E_USER_ERROR); 625 $prevtype = $edit->type; 626 } 627 628 $lcs = $this->lcs(); 629 trigger_error("WikiDiff okay: LCS = $lcs", E_USER_NOTICE); 630 } 631 } 632 633 /** 634 * FIXME: bad name. 635 */ 636 637 class MappedWikiDiff 638 extends WikiDiff 639 { 640 /** 641 * Constructor. 642 * 643 * Computes diff between sequences of strings. 644 * 645 * This can be used to compute things like 646 * case-insensitve diffs, or diffs which ignore 647 * changes in white-space. 648 * 649 * @param $from_lines array An array of strings. 650 * (Typically these are lines from a file.) 651 * 652 * @param $to_lines array An array of strings. 653 * 654 * @param $mapped_from_lines array This array should 655 * have the same size number of elements as $from_lines. 656 * The elements in $mapped_from_lines and 657 * $mapped_to_lines are what is actually compared 658 * when computing the diff. 659 * 660 * @param $mapped_to_lines array This array should 661 * have the same number of elements as $to_lines. 662 */ 663 public function __construct($from_lines, $to_lines, 664 $mapped_from_lines, $mapped_to_lines) { 665 666 assert(sizeof($from_lines) == sizeof($mapped_from_lines)); 667 assert(sizeof($to_lines) == sizeof($mapped_to_lines)); 668 669 parent::__construct($mapped_from_lines, $mapped_to_lines); 670 671 $xi = $yi = 0; 672 for ($i = 0; $i < sizeof($this->edits); $i++) { 673 $orig = &$this->edits[$i]->orig; 674 if (is_array($orig)) { 675 $orig = array_slice($from_lines, $xi, sizeof($orig)); 676 $xi += sizeof($orig); 677 } 678 679 $closing = &$this->edits[$i]->closing; 680 if (is_array($closing)) { 681 $closing = array_slice($to_lines, $yi, sizeof($closing)); 682 $yi += sizeof($closing); 683 } 684 } 685 } 686 } 687 688 /** 689 * A class to format WikiDiffs 690 * 691 * This class formats the diff in classic diff format. 692 * It is intended that this class be customized via inheritance, 693 * to obtain fancier outputs. 694 */ 695 class WikiDiffFormatter 696 { 697 /** 698 * Number of leading context "lines" to preserve. 699 * 700 * This should be left at zero for this class, but subclasses 701 * may want to set this to other values. 702 */ 703 var $leading_context_lines = 0; 704 705 /** 706 * Number of trailing context "lines" to preserve. 707 * 708 * This should be left at zero for this class, but subclasses 709 * may want to set this to other values. 710 */ 711 var $trailing_context_lines = 0; 712 713 /** 714 * Format a diff. 715 * 716 * @param $diff object A WikiDiff object. 717 * @return string The formatted output. 718 */ 719 function format($diff) { 720 721 $xi = $yi = 1; 722 $block = false; 723 $context = array(); 724 725 $nlead = $this->leading_context_lines; 726 $ntrail = $this->trailing_context_lines; 727 728 $this->_start_diff(); 729 730 foreach ($diff->edits as $edit) { 731 if ($edit->type == 'copy') { 732 if (is_array($block)) { 733 if (sizeof($edit->orig) <= $nlead + $ntrail) { 734 $block[] = $edit; 735 } 736 else{ 737 if ($ntrail) { 738 $context = array_slice($edit->orig, 0, $ntrail); 739 $block[] = new _WikiWikiDiffOp_Copy($context); 740 } 741 $this->_block($x0, $ntrail + $xi - $x0, 742 $y0, $ntrail + $yi - $y0, 743 $block); 744 $block = false; 745 } 746 } 747 $context = $edit->orig; 748 } 749 else { 750 if (! is_array($block)) { 751 $context = array_slice($context, sizeof($context) - $nlead); 752 $x0 = $xi - sizeof($context); 753 $y0 = $yi - sizeof($context); 754 $block = array(); 755 if ($context) 756 $block[] = new _WikiWikiDiffOp_Copy($context); 757 } 758 $block[] = $edit; 759 } 760 761 if ($edit->orig) 762 $xi += sizeof($edit->orig); 763 if ($edit->closing) 764 $yi += sizeof($edit->closing); 765 } 766 767 if (is_array($block)) 768 $this->_block($x0, $xi - $x0, 769 $y0, $yi - $y0, 770 $block); 771 772 return $this->_end_diff(); 773 } 774 775 function _block($xbeg, $xlen, $ybeg, $ylen, &$edits) { 776 $this->_start_block($this->_block_header($xbeg, $xlen, $ybeg, $ylen)); 777 foreach ($edits as $edit) { 778 if ($edit->type == 'copy') 779 $this->_context($edit->orig); 780 elseif ($edit->type == 'add') 781 $this->_added($edit->closing); 782 elseif ($edit->type == 'delete') 783 $this->_deleted($edit->orig); 784 elseif ($edit->type == 'change') 785 $this->_changed($edit->orig, $edit->closing); 786 else 787 trigger_error("Unknown edit type", E_USER_ERROR); 788 } 789 $this->_end_block(); 790 } 791 792 function _start_diff() { 793 ob_start(); 794 } 795 796 function _end_diff() { 797 $val = ob_get_contents(); 798 ob_end_clean(); 799 return $val; 800 } 801 802 function _block_header($xbeg, $xlen, $ybeg, $ylen) { 803 if ($xlen > 1) 804 $xbeg .= "," . ($xbeg + $xlen - 1); 805 if ($ylen > 1) 806 $ybeg .= "," . ($ybeg + $ylen - 1); 807 808 return $xbeg . ($xlen ? ($ylen ? 'c' : 'd') : 'a') . $ybeg; 809 } 810 811 function _start_block($header) { 812 echo $header; 813 } 814 815 function _end_block() { 816 } 817 818 function _lines($lines, $prefix = ' ') { 819 foreach ($lines as $line) 820 echo "$prefix $line\n"; 821 } 822 823 function _context($lines) { 824 $this->_lines($lines); 825 } 826 827 function _added($lines) { 828 $this->_lines($lines, ">"); 829 } 830 function _deleted($lines) { 831 $this->_lines($lines, "<"); 832 } 833 834 function _changed($orig, $closing) { 835 $this->_deleted($orig); 836 echo "---\n"; 837 $this->_added($closing); 838 } 839 } 840 841 842 /** 843 * Additions by Axel Boldt follow, partly taken from diff.php, phpwiki-1.3.3 844 * 845 */ 846 847 define('NBSP', ' '); // iso-8859-x non-breaking space. 848 849 class _WikiHWLDF_WordAccumulator { 850 public function __construct () { 851 $this->_lines = array(); 852 $this->_line = ''; 853 $this->_group = ''; 854 $this->_tag = ''; 855 } 856 857 function _flushGroup ($new_tag) { 858 if ($this->_group !== '') { 859 if ($this->_tag == 'mark') 860 $this->_line .= '<span class="diffchange">'.$this->_group.'</span>'; 861 else 862 $this->_line .= $this->_group; 863 } 864 $this->_group = ''; 865 $this->_tag = $new_tag; 866 } 867 868 function _flushLine ($new_tag) { 869 $this->_flushGroup($new_tag); 870 if ($this->_line != '') 871 $this->_lines[] = $this->_line; 872 $this->_line = ''; 873 } 874 875 function addWords ($words, $tag = '') { 876 if ($tag != $this->_tag) 877 $this->_flushGroup($tag); 878 879 foreach ($words as $word) { 880 // new-line should only come as first char of word. 881 if ($word == '') 882 continue; 883 if ($word[0] == "\n") { 884 $this->_group .= NBSP; 885 $this->_flushLine($tag); 886 $word = substr($word, 1); 887 } 888 assert(!strstr($word, "\n")); 889 $this->_group .= $word; 890 } 891 } 892 893 function getLines() { 894 $this->_flushLine('~done'); 895 return $this->_lines; 896 } 897 } 898 899 class WordLevelWikiDiff extends MappedWikiDiff 900 { 901 function __construct ($orig_lines, $closing_lines) { 902 list ($orig_words, $orig_stripped) = $this->_split($orig_lines); 903 list ($closing_words, $closing_stripped) = $this->_split($closing_lines); 904 905 906 parent::__construct($orig_words, $closing_words, 907 $orig_stripped, $closing_stripped); 908 } 909 910 function _split($lines) { 911 // FIXME: fix POSIX char class. 912 # if (!preg_match_all('/ ( [^\S\n]+ | [[:alnum:]]+ | . ) (?: (?!< \n) [^\S\n])? /xs', 913 if (!preg_match_all('/ ( [^\S\n]+ | [0-9_A-Za-z\x80-\xff]+ | . ) (?: (?!< \n) [^\S\n])? /xs', 914 implode("\n", $lines), 915 $m)) { 916 return array(array(''), array('')); 917 } 918 return array($m[0], $m[1]); 919 } 920 921 function orig () { 922 $orig = new _WikiHWLDF_WordAccumulator; 923 924 foreach ($this->edits as $edit) { 925 if ($edit->type == 'copy') 926 $orig->addWords($edit->orig); 927 elseif ($edit->orig) 928 $orig->addWords($edit->orig, 'mark'); 929 } 930 return $orig->getLines(); 931 } 932 933 function closing () { 934 $closing = new _WikiHWLDF_WordAccumulator; 935 936 foreach ($this->edits as $edit) { 937 if ($edit->type == 'copy') 938 $closing->addWords($edit->closing); 939 elseif ($edit->closing) 940 $closing->addWords($edit->closing, 'mark'); 941 } 942 return $closing->getLines(); 943 } 944 } 945 946 /** 947 * @TODO: Doc this class 948 */ 949 class TableWikiDiffFormatter extends WikiDiffFormatter 950 { 951 var $htmltable = array(); 952 953 public function __construct() { 954 $this->leading_context_lines = 2; 955 $this->trailing_context_lines = 2; 956 } 957 958 function _block_header( $xbeg, $xlen, $ybeg, $ylen) { 959 960 } 961 962 function _start_block ($header) { 963 964 } 965 966 function _end_block() { 967 968 } 969 970 function _lines($lines, $prefix=' ', $color="white") { 971 972 } 973 974 function _added($lines) { 975 global $htmltable; 976 foreach ($lines as $line) { 977 $htmltable[] = array('','+','<div class="wiki_diffadd">'.$line.'</div>'); 978 } 979 } 980 981 function _deleted($lines) { 982 global $htmltable; 983 foreach ($lines as $line) { 984 $htmltable[] = array('<div class="wiki_diffdel">'.$line.'</div>','-',''); 985 } 986 } 987 988 function _context($lines) { 989 global $htmltable; 990 foreach ($lines as $line) { 991 $htmltable[] = array($line,'',$line); 992 } 993 } 994 995 function _changed( $orig, $closing ) { 996 global $htmltable; 997 $diff = new WordLevelWikiDiff( $orig, $closing ); 998 $del = $diff->orig(); 999 $add = $diff->closing(); 1000 1001 while ( $line = array_shift( $del ) ) { 1002 $aline = array_shift( $add ); 1003 $htmltable[] = array('<div class="wiki_diffdel">'.$line.'</div>','-','<div class="wiki_diffadd">'.$aline.'</div>'); 1004 } 1005 $this->_added( $add ); # If any leftovers 1006 } 1007 1008 function get_result() { 1009 global $htmltable; 1010 return $htmltable; 1011 } 1012 1013 } 1014 1015 1016 /** 1017 * Wikipedia Table style diff formatter. 1018 * 1019 */ 1020 class TableWikiDiffFormatterOld extends WikiDiffFormatter 1021 { 1022 function TableWikiDiffFormatter() { 1023 $this->leading_context_lines = 2; 1024 $this->trailing_context_lines = 2; 1025 } 1026 1027 function _block_header( $xbeg, $xlen, $ybeg, $ylen ) { 1028 $l1 = wfMsg( "lineno", $xbeg ); 1029 $l2 = wfMsg( "lineno", $ybeg ); 1030 1031 $r = '<tr><td colspan="2" align="left"><strong>'.$l1."</strong></td>\n" . 1032 '<td colspan="2" align="left"><strong>'.$l2."</strong></td></tr>\n"; 1033 return $r; 1034 } 1035 1036 function _start_block( $header ) { 1037 global $wgOut; 1038 $wgOut->addHTML( $header ); 1039 } 1040 1041 function _end_block() { 1042 } 1043 1044 function _lines( $lines, $prefix=' ', $color="white" ) { 1045 } 1046 1047 function addedLine( $line ) { 1048 return '<td>+</td><td class="diff-addedline">' . 1049 $line.'</td>'; 1050 } 1051 1052 function deletedLine( $line ) { 1053 return '<td>-</td><td class="diff-deletedline">' . 1054 $line.'</td>'; 1055 } 1056 1057 function emptyLine() { 1058 return '<td colspan="2"> </td>'; 1059 } 1060 1061 function contextLine( $line ) { 1062 return '<td> </td><td class="diff-context">'.$line.'</td>'; 1063 } 1064 1065 function _added($lines) { 1066 global $wgOut; 1067 foreach ($lines as $line) { 1068 $wgOut->addHTML( '<tr>' . $this->emptyLine() . 1069 $this->addedLine( $line ) . "</tr>\n" ); 1070 } 1071 } 1072 1073 function _deleted($lines) { 1074 global $wgOut; 1075 foreach ($lines as $line) { 1076 $wgOut->addHTML( '<tr>' . $this->deletedLine( $line ) . 1077 $this->emptyLine() . "</tr>\n" ); 1078 } 1079 } 1080 1081 function _context( $lines ) { 1082 global $wgOut; 1083 foreach ($lines as $line) { 1084 $wgOut->addHTML( '<tr>' . $this->contextLine( $line ) . 1085 $this->contextLine( $line ) . "</tr>\n" ); 1086 } 1087 } 1088 1089 function _changed( $orig, $closing ) { 1090 global $wgOut; 1091 $diff = new WordLevelWikiDiff( $orig, $closing ); 1092 $del = $diff->orig(); 1093 $add = $diff->closing(); 1094 1095 while ( $line = array_shift( $del ) ) { 1096 $aline = array_shift( $add ); 1097 $wgOut->addHTML( '<tr>' . $this->deletedLine( $line ) . 1098 $this->addedLine( $aline ) . "</tr>\n" ); 1099 } 1100 $this->_added( $add ); # If any leftovers 1101 } 1102 } 1103
title
Description
Body
title
Description
Body
title
Description
Body
title
Body
