| [ Index ] |
|
Code source de WikiNi 0.4.4 |
1 <?php 2 /* 3 diff.php 4 5 Copyright (C) 1992 Free Software Foundation, Inc. Francois Pinard <pinard@iro.umontreal.ca>. 6 Copyright (C) 2000, 2001 Geoffrey T. Dairiki <dairiki@dairiki.org> 7 Copyright 2002,2003,2004 David DELON 8 Copyright 2002 Patrick PAUL 9 Copyright 2003 Eric FELDSTEIN 10 11 This program is free software; you can redistribute it and/or modify 12 it under the terms of the GNU General Public License as published by 13 the Free Software Foundation; either version 2 of the License, or 14 (at your option) any later version. 15 16 This program is distributed in the hope that it will be useful, 17 but WITHOUT ANY WARRANTY; without even the implied warranty of 18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 19 GNU General Public License for more details. 20 21 You should have received a copy of the GNU General Public License 22 along with this program; if not, write to the Free Software 23 Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 24 25 original diff.php 26 Copyright (c) 2002, Hendrik Mans <hendrik@mans.de> 27 All rights reserved. 28 Redistribution and use in source and binary forms, with or without 29 modification, are permitted provided that the following conditions 30 are met: 31 1. Redistributions of source code must retain the above copyright 32 notice, this list of conditions and the following disclaimer. 33 2. Redistributions in binary form must reproduce the above copyright 34 notice, this list of conditions and the following disclaimer in the 35 documentation and/or other materials provided with the distribution. 36 3. The name of the author may not be used to endorse or promote products 37 derived from this software without specific prior written permission. 38 39 THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR 40 IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 41 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 42 IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, 43 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT 44 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 45 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 46 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 47 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 48 THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 49 */ 50 51 52 //vérification de sécurité 53 if (!eregi("wakka.php", $_SERVER['PHP_SELF'])) { 54 die ("accès direct interdit"); 55 } 56 echo $this->Header(); 57 ?> 58 <div class="page"> 59 <?php 60 61 if ($this->HasAccess("read")) 62 { 63 64 // If asked, call original diff 65 66 if (!empty($_REQUEST["fastdiff"])) { 67 68 /* NOTE: This is a really cheap way to do it. I think it may be more intelligent to write the two pages to temporary files and run /usr/bin/diff over them. Then again, maybe not. */ 69 // load pages 70 $pageA = $this->LoadPageById($_REQUEST["a"]); 71 $pageB = $this->LoadPageById($_REQUEST["b"]); 72 73 // prepare bodies 74 $bodyA = explode("\n", $pageA["body"]); 75 $bodyB = explode("\n", $pageB["body"]); 76 77 $added = array_diff($bodyA, $bodyB); 78 $deleted = array_diff($bodyB, $bodyA); 79 80 $output .= "<b>Comparaison de <a href=\"".$this->href("", "", "time=".urlencode($pageA["time"]))."\">".$pageA["time"]."</a> à <a href=\"".$this->href("", "", "time=".urlencode($pageB["time"]))."\">".$pageB["time"]."</a></b><br />\n"; 81 82 if ($added) 83 { 84 // remove blank lines 85 $output .= "<br />\n<b>Ajouts:</b><br />\n"; 86 $output .= "<div class=\"additions\">".$this->Format(implode("\n", $added))."</div>"; 87 } 88 89 if ($deleted) 90 { 91 $output .= "<br />\n<b>Suppressions:</b><br />\n"; 92 $output .= "<div class=\"deletions\">".$this->Format(implode("\n", $deleted))."</div>"; 93 } 94 95 if (!$added && !$deleted) 96 { 97 $output .= "<br />\nPas de différences."; 98 } 99 echo $output; 100 101 } 102 103 else { 104 105 // load pages 106 107 $pageA = $this->LoadPageById($_REQUEST["b"]); 108 $pageB = $this->LoadPageById($_REQUEST["a"]); 109 110 // extract text from bodies 111 $textA = $pageA["body"]; 112 $textB = $pageB["body"]; 113 114 $sideA = new Side($textA); 115 $sideB = new Side($textB); 116 117 $bodyA=''; 118 $sideA->split_file_into_words($bodyA); 119 120 $bodyB=''; 121 $sideB->split_file_into_words($bodyB); 122 123 // diff on these two file 124 $diff = new Diff(split("\n",$bodyA),split("\n",$bodyB)); 125 126 // format output 127 $fmt = new DiffFormatter(); 128 129 $sideO = new Side($fmt->format($diff)); 130 131 $resync_left=0; 132 $resync_right=0; 133 134 $count_total_right=$sideB->getposition() ; 135 136 $sideA->init(); 137 $sideB->init(); 138 139 $output=''; 140 141 while (1) { 142 143 $sideO->skip_line(); 144 if ($sideO->isend()) { 145 break; 146 } 147 148 if ($sideO->decode_directive_line()) { 149 $argument=$sideO->getargument(); 150 $letter=$sideO->getdirective(); 151 switch ($letter) { 152 case 'a': 153 $resync_left = $argument[0]; 154 $resync_right = $argument[2] - 1; 155 break; 156 157 case 'd': 158 $resync_left = $argument[0] - 1; 159 $resync_right = $argument[2]; 160 break; 161 162 case 'c': 163 $resync_left = $argument[0] - 1; 164 $resync_right = $argument[2] - 1; 165 break; 166 167 } 168 169 $sideA->skip_until_ordinal($resync_left); 170 $sideB->copy_until_ordinal($resync_right,$output); 171 172 // deleted word 173 174 if (($letter=='d') || ($letter=='c')) { 175 $sideA->copy_whitespace($output); 176 $output .="@@"; 177 $sideA->copy_word($output); 178 $sideA->copy_until_ordinal($argument[1],$output); 179 $output .="@@"; 180 } 181 182 // inserted word 183 if ($letter == 'a' || $letter == 'c') { 184 $sideB->copy_whitespace($output); 185 $output .="££"; 186 $sideB->copy_word($output); 187 $sideB->copy_until_ordinal($argument[3],$output); 188 $output .="££"; 189 } 190 191 } 192 193 } 194 195 $sideB->copy_until_ordinal($count_total_right,$output); 196 $sideB->copy_whitespace($output); 197 $out=$this->Format($output); 198 echo $out; 199 200 } 201 202 } 203 else{ 204 echo "<i>Vous n'êtes pas autorisé à lire cette page.</i>" ; 205 } 206 207 // Side : a string for wdiff 208 209 class Side { 210 var $position; 211 var $cursor; 212 var $content; 213 var $character; 214 var $directive; 215 var $argument; 216 var $length; 217 218 function Side($content) { 219 $this->content=$content; 220 $this->position=0; 221 $this->cursor=0; 222 $this->directive=''; 223 $this->argument=array(); 224 $this->length=strlen($this->content); 225 $this->character=substr($this->content,0,1); 226 227 } 228 229 function getposition() { 230 return $this->position; 231 } 232 233 function getcharacter() { 234 return $this->character; 235 } 236 237 function getdirective() { 238 return $this->directive; 239 } 240 241 function getargument() { 242 return $this->argument; 243 } 244 245 function nextchar() { 246 $this->cursor++; 247 $this->character=substr($this->content,$this->cursor,1); 248 } 249 250 function copy_until_ordinal($ordinal,&$out) { 251 while ($this->position < $ordinal) { 252 $this->copy_whitespace($out); 253 $this->copy_word($out); 254 } 255 } 256 257 function skip_until_ordinal($ordinal) { 258 while ($this->position < $ordinal) { 259 $this->skip_whitespace(); 260 $this->skip_word(); 261 } 262 } 263 264 function split_file_into_words (&$out) { 265 while (!$this->isend()) { 266 $this->skip_whitespace(); 267 if ($this->isend()) { 268 break; 269 } 270 $this->copy_word($out); 271 $out .="\n"; 272 } 273 } 274 275 function init() { 276 $this->position=0; 277 $this->cursor=0; 278 $this->directive=''; 279 $this->argument=array(); 280 $this->character=substr($this->content,0,1); 281 } 282 283 function isspace($char) { 284 if (ereg('[[:space:]]',$char)) { 285 return true; 286 } 287 else { 288 return false; 289 } 290 } 291 292 function isdigit($char) { 293 if (ereg('[[:digit:]]',$char)) { 294 return true; 295 } 296 else { 297 return false; 298 } 299 } 300 301 function isend() { 302 if (($this->cursor)>=($this->length)) { 303 return true; 304 } 305 else { 306 return false; 307 } 308 } 309 310 311 312 function copy_whitespace(&$out) { 313 while (!$this->isend() && $this->isspace($this->character)) { 314 $out .=$this->character; 315 $this->nextchar(); 316 } 317 } 318 319 function skip_whitespace() { 320 while (!$this->isend() && $this->isspace($this->character)) { 321 $this->nextchar(); 322 } 323 } 324 325 function skip_line() { 326 while (!$this->isend() && !$this->isdigit($this->character)) { 327 while (!$this->isend() && $this->character!="\n") 328 $this->nextchar(); 329 if($this->character=="\n") 330 $this->nextchar(); 331 } 332 } 333 334 335 336 function copy_word(&$out) { 337 while (!$this->isend() && !($this->isspace($this->character))) { 338 $out.=$this->character; 339 $this->nextchar(); 340 } 341 $this->position++; 342 } 343 344 function skip_word() { 345 346 while (!$this->isend() && !($this->isspace($this->character))) { 347 $this->nextchar(); 348 } 349 $this->position++; 350 } 351 352 353 function decode_directive_line() { 354 355 $value=0; 356 $state=0; 357 $error=0; 358 359 while (!$error && $state < 4) { 360 if ($this->isdigit($this->character)) { 361 $value = 0; 362 while($this->isdigit($this->character)) { 363 $value = 10 * $value + $this->character - '0'; 364 $this->nextchar(); 365 } 366 } 367 else if ($state != 1 && $state != 3) 368 $error = 1; 369 370 /* Assign the proper value. */ 371 372 $this->argument[$state] = $value; 373 374 /* Skip the following character. */ 375 376 switch ($state) { 377 case 0: 378 case 2: 379 if ($this->character == ',') 380 $this->nextchar(); 381 break; 382 383 case 1: 384 if ($this->character == 'a' || $this->character == 'd' || $this->character == 'c') { 385 $this->directive = $this->character; 386 $this->nextchar(); 387 } 388 else 389 $error = 1; 390 break; 391 392 case 3: 393 if ($this->character != "\n") 394 $error = 1; 395 break; 396 } 397 $state++; 398 } 399 400 /* Complete reading of the line and return success value. */ 401 402 while ((!$this->isend()) && ($this->character != "\n")) { 403 $this->nextchar(); 404 } 405 if ($this->character == "\n") 406 $this->nextchar(); 407 408 return !$error; 409 } 410 411 412 413 } 414 415 // difflib 416 // 417 // A PHP diff engine for phpwiki. 418 // 419 // Copyright (C) 2000, 2001 Geoffrey T. Dairiki <dairiki@dairiki.org> 420 // You may copy this code freely under the conditions of the GPL. 421 // 422 423 class _DiffOp { 424 var $type; 425 var $orig; 426 var $final; 427 428 429 function norig() { 430 return $this->orig ? sizeof($this->orig) : 0; 431 } 432 433 function nfinal() { 434 return $this->final ? sizeof($this->final) : 0; 435 } 436 } 437 438 class _DiffOp_Copy extends _DiffOp { 439 var $type = 'copy'; 440 441 function _DiffOp_Copy ($orig, $final = false) { 442 if (!is_array($final)) 443 $final = $orig; 444 $this->orig = $orig; 445 $this->final = $final; 446 } 447 448 } 449 450 class _DiffOp_Delete extends _DiffOp { 451 var $type = 'delete'; 452 453 function _DiffOp_Delete ($lines) { 454 $this->orig = $lines; 455 $this->final = false; 456 } 457 458 } 459 460 class _DiffOp_Add extends _DiffOp { 461 var $type = 'add'; 462 463 function _DiffOp_Add ($lines) { 464 $this->final = $lines; 465 $this->orig = false; 466 } 467 468 } 469 470 class _DiffOp_Change extends _DiffOp { 471 var $type = 'change'; 472 473 function _DiffOp_Change ($orig, $final) { 474 $this->orig = $orig; 475 $this->final = $final; 476 } 477 478 } 479 480 481 /** 482 * Class used internally by Diff to actually compute the diffs. 483 * 484 * The algorithm used here is mostly lifted from the perl module 485 * Algorithm::Diff (version 1.06) by Ned Konz, which is available at: 486 * http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip 487 * 488 * More ideas are taken from: 489 * http://www.ics.uci.edu/~eppstein/161/960229.html 490 * 491 * Some ideas are (and a bit of code) are from from analyze.c, from GNU 492 * diffutils-2.7, which can be found at: 493 * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz 494 * 495 * Finally, some ideas (subdivision by NCHUNKS > 2, and some optimizations) 496 * are my own. 497 * 498 * @author Geoffrey T. Dairiki 499 * @access private 500 */ 501 class _DiffEngine 502 { 503 function diff ($from_lines, $to_lines) { 504 $n_from = sizeof($from_lines); 505 $n_to = sizeof($to_lines); 506 507 $this->xchanged = $this->ychanged = array(); 508 $this->xv = $this->yv = array(); 509 $this->xind = $this->yind = array(); 510 unset($this->seq); 511 unset($this->in_seq); 512 unset($this->lcs); 513 514 // Skip leading common lines. 515 for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) { 516 if ($from_lines[$skip] != $to_lines[$skip]) 517 break; 518 $this->xchanged[$skip] = $this->ychanged[$skip] = false; 519 } 520 // Skip trailing common lines. 521 $xi = $n_from; $yi = $n_to; 522 for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) { 523 if ($from_lines[$xi] != $to_lines[$yi]) 524 break; 525 $this->xchanged[$xi] = $this->ychanged[$yi] = false; 526 } 527 528 // Ignore lines which do not exist in both files. 529 for ($xi = $skip; $xi < $n_from - $endskip; $xi++) 530 $xhash[$from_lines[$xi]] = 1; 531 for ($yi = $skip; $yi < $n_to - $endskip; $yi++) { 532 $line = $to_lines[$yi]; 533 if ( ($this->ychanged[$yi] = empty($xhash[$line])) ) 534 continue; 535 $yhash[$line] = 1; 536 $this->yv[] = $line; 537 $this->yind[] = $yi; 538 } 539 for ($xi = $skip; $xi < $n_from - $endskip; $xi++) { 540 $line = $from_lines[$xi]; 541 if ( ($this->xchanged[$xi] = empty($yhash[$line])) ) 542 continue; 543 $this->xv[] = $line; 544 $this->xind[] = $xi; 545 } 546 547 // Find the LCS. 548 $this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv)); 549 550 // Merge edits when possible 551 $this->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged); 552 $this->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged); 553 554 // Compute the edit operations. 555 $edits = array(); 556 $xi = $yi = 0; 557 while ($xi < $n_from || $yi < $n_to) { 558 assert($yi < $n_to || $this->xchanged[$xi]); 559 assert($xi < $n_from || $this->ychanged[$yi]); 560 561 // Skip matching "snake". 562 $copy = array(); 563 while ( $xi < $n_from && $yi < $n_to 564 && !$this->xchanged[$xi] && !$this->ychanged[$yi]) { 565 $copy[] = $from_lines[$xi++]; 566 ++$yi; 567 } 568 if ($copy) 569 $edits[] = new _DiffOp_Copy($copy); 570 571 // Find deletes & adds. 572 $delete = array(); 573 while ($xi < $n_from && $this->xchanged[$xi]) 574 $delete[] = $from_lines[$xi++]; 575 576 $add = array(); 577 while ($yi < $n_to && $this->ychanged[$yi]) 578 $add[] = $to_lines[$yi++]; 579 580 if ($delete && $add) 581 $edits[] = new _DiffOp_Change($delete, $add); 582 elseif ($delete) 583 $edits[] = new _DiffOp_Delete($delete); 584 elseif ($add) 585 $edits[] = new _DiffOp_Add($add); 586 } 587 return $edits; 588 } 589 590 591 /* Divide the Largest Common Subsequence (LCS) of the sequences 592 * [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally 593 * sized segments. 594 * 595 * Returns (LCS, PTS). LCS is the length of the LCS. PTS is an 596 * array of NCHUNKS+1 (X, Y) indexes giving the diving points between 597 * sub sequences. The first sub-sequence is contained in [X0, X1), 598 * [Y0, Y1), the second in [X1, X2), [Y1, Y2) and so on. Note 599 * that (X0, Y0) == (XOFF, YOFF) and 600 * (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM). 601 * 602 * This function assumes that the first lines of the specified portions 603 * of the two files do not match, and likewise that the last lines do not 604 * match. The caller must trim matching lines from the beginning and end 605 * of the portions it is going to specify. 606 */ 607 function _diag ($xoff, $xlim, $yoff, $ylim, $nchunks) { 608 $flip = false; 609 610 if ($xlim - $xoff > $ylim - $yoff) { 611 // Things seems faster (I'm not sure I understand why) 612 // when the shortest sequence in X. 613 $flip = true; 614 list ($xoff, $xlim, $yoff, $ylim) 615 = array( $yoff, $ylim, $xoff, $xlim); 616 } 617 618 if ($flip) 619 for ($i = $ylim - 1; $i >= $yoff; $i--) 620 $ymatches[$this->xv[$i]][] = $i; 621 else 622 for ($i = $ylim - 1; $i >= $yoff; $i--) 623 $ymatches[$this->yv[$i]][] = $i; 624 625 $this->lcs = 0; 626 $this->seq[0]= $yoff - 1; 627 $this->in_seq = array(); 628 $ymids[0] = array(); 629 630 $numer = $xlim - $xoff + $nchunks - 1; 631 $x = $xoff; 632 for ($chunk = 0; $chunk < $nchunks; $chunk++) { 633 if ($chunk > 0) 634 for ($i = 0; $i <= $this->lcs; $i++) 635 $ymids[$i][$chunk-1] = $this->seq[$i]; 636 637 $x1 = $xoff + (int)(($numer + ($xlim-$xoff)*$chunk) / $nchunks); 638 for ( ; $x < $x1; $x++) { 639 $line = $flip ? $this->yv[$x] : $this->xv[$x]; 640 if (empty($ymatches[$line])) 641 continue; 642 $matches = $ymatches[$line]; 643 reset($matches); 644 while (list ($junk, $y) = each($matches)) 645 if (empty($this->in_seq[$y])) { 646 $k = $this->_lcs_pos($y); 647 assert($k > 0); 648 $ymids[$k] = $ymids[$k-1]; 649 break; 650 } 651 while (list ($junk, $y) = each($matches)) { 652 if ($y > $this->seq[$k-1]) { 653 assert($y < $this->seq[$k]); 654 // Optimization: this is a common case: 655 // next match is just replacing previous match. 656 $this->in_seq[$this->seq[$k]] = false; 657 $this->seq[$k] = $y; 658 $this->in_seq[$y] = 1; 659 } 660 else if (empty($this->in_seq[$y])) { 661 $k = $this->_lcs_pos($y); 662 assert($k > 0); 663 $ymids[$k] = $ymids[$k-1]; 664 } 665 } 666 } 667 } 668 669 $seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff); 670 $ymid = $ymids[$this->lcs]; 671 for ($n = 0; $n < $nchunks - 1; $n++) { 672 $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks); 673 $y1 = $ymid[$n] + 1; 674 $seps[] = $flip ? array($y1, $x1) : array($x1, $y1); 675 } 676 $seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim); 677 678 return array($this->lcs, $seps); 679 } 680 681 function _lcs_pos ($ypos) { 682 $end = $this->lcs; 683 if ($end == 0 || $ypos > $this->seq[$end]) { 684 $this->seq[++$this->lcs] = $ypos; 685 $this->in_seq[$ypos] = 1; 686 return $this->lcs; 687 } 688 689 $beg = 1; 690 while ($beg < $end) { 691 $mid = (int)(($beg + $end) / 2); 692 if ( $ypos > $this->seq[$mid] ) 693 $beg = $mid + 1; 694 else 695 $end = $mid; 696 } 697 698 assert($ypos != $this->seq[$end]); 699 700 $this->in_seq[$this->seq[$end]] = false; 701 $this->seq[$end] = $ypos; 702 $this->in_seq[$ypos] = 1; 703 return $end; 704 } 705 706 /* Find LCS of two sequences. 707 * 708 * The results are recorded in the vectors $this->{x,y}changed[], by 709 * storing a 1 in the element for each line that is an insertion 710 * or deletion (ie. is not in the LCS). 711 * 712 * The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1. 713 * 714 * Note that XLIM, YLIM are exclusive bounds. 715 * All line numbers are origin-0 and discarded lines are not counted. 716 */ 717 function _compareseq ($xoff, $xlim, $yoff, $ylim) { 718 // Slide down the bottom initial diagonal. 719 while ($xoff < $xlim && $yoff < $ylim 720 && $this->xv[$xoff] == $this->yv[$yoff]) { 721 ++$xoff; 722 ++$yoff; 723 } 724 725 // Slide up the top initial diagonal. 726 while ($xlim > $xoff && $ylim > $yoff 727 && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) { 728 --$xlim; 729 --$ylim; 730 } 731 732 if ($xoff == $xlim || $yoff == $ylim) 733 $lcs = 0; 734 else { 735 // This is ad hoc but seems to work well. 736 //$nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5); 737 //$nchunks = max(2,min(8,(int)$nchunks)); 738 $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1; 739 list ($lcs, $seps) 740 = $this->_diag($xoff,$xlim,$yoff, $ylim,$nchunks); 741 } 742 743 if ($lcs == 0) { 744 // X and Y sequences have no common subsequence: 745 // mark all changed. 746 while ($yoff < $ylim) 747 $this->ychanged[$this->yind[$yoff++]] = 1; 748 while ($xoff < $xlim) 749 $this->xchanged[$this->xind[$xoff++]] = 1; 750 } 751 else { 752 // Use the partitions to split this problem into subproblems. 753 reset($seps); 754 $pt1 = $seps[0]; 755 while ($pt2 = next($seps)) { 756 $this->_compareseq ($pt1[0], $pt2[0], $pt1[1], $pt2[1]); 757 $pt1 = $pt2; 758 } 759 } 760 } 761 762 /* Adjust inserts/deletes of identical lines to join changes 763 * as much as possible. 764 * 765 * We do something when a run of changed lines include a 766 * line at one end and has an excluded, identical line at the other. 767 * We are free to choose which identical line is included. 768 * `compareseq' usually chooses the one at the beginning, 769 * but usually it is cleaner to consider the following identical line 770 * to be the "change". 771 * 772 * This is extracted verbatim from analyze.c (GNU diffutils-2.7). 773 */ 774 function _shift_boundaries ($lines, &$changed, $other_changed) { 775 $i = 0; 776 $j = 0; 777 778 assert('sizeof($lines) == sizeof($changed)'); 779 $len = sizeof($lines); 780 $other_len = sizeof($other_changed); 781 782 while (1) { 783 /* 784 * Scan forwards to find beginning of another run of changes. 785 * Also keep track of the corresponding point in the other file. 786 * 787 * Throughout this code, $i and $j are adjusted together so that 788 * the first $i elements of $changed and the first $j elements 789 * of $other_changed both contain the same number of zeros 790 * (unchanged lines). 791 * Furthermore, $j is always kept so that $j == $other_len or 792 * $other_changed[$j] == false. 793 */ 794 while ($j < $other_len && $other_changed[$j]) 795 $j++; 796 797 while ($i < $len && ! $changed[$i]) { 798 assert('$j < $other_len && ! $other_changed[$j]'); 799 $i++; $j++; 800 while ($j < $other_len && $other_changed[$j]) 801 $j++; 802 } 803 804 if ($i == $len) 805 break; 806 807 $start = $i; 808 809 // Find the end of this run of changes. 810 while (++$i < $len && $changed[$i]) 811 continue; 812 813 do { 814 /* 815 * Record the length of this run of changes, so that 816 * we can later determine whether the run has grown. 817 */ 818 $runlength = $i - $start; 819 820 /* 821 * Move the changed region back, so long as the 822 * previous unchanged line matches the last changed one. 823 * This merges with previous changed regions. 824 */ 825 while ($start > 0 && $lines[$start - 1] == $lines[$i - 1]) { 826 $changed[--$start] = 1; 827 $changed[--$i] = false; 828 while ($start > 0 && $changed[$start - 1]) 829 $start--; 830 assert('$j > 0'); 831 while ($other_changed[--$j]) 832 continue; 833 assert('$j >= 0 && !$other_changed[$j]'); 834 } 835 836 /* 837 * Set CORRESPONDING to the end of the changed run, at the last 838 * point where it corresponds to a changed run in the other file. 839 * CORRESPONDING == LEN means no such point has been found. 840 */ 841 $corresponding = $j < $other_len ? $i : $len; 842 843 /* 844 * Move the changed region forward, so long as the 845 * first changed line matches the following unchanged one. 846 * This merges with following changed regions. 847 * Do this second, so that if there are no merges, 848 * the changed region is moved forward as far as possible. 849 */ 850 while ($i < $len && $lines[$start] == $lines[$i]) { 851 $changed[$start++] = false; 852 $changed[$i++] = 1; 853 while ($i < $len && $changed[$i]) 854 $i++; 855 856 assert('$j < $other_len && ! $other_changed[$j]'); 857 $j++; 858 if ($j < $other_len && $other_changed[$j]) { 859 $corresponding = $i; 860 while ($j < $other_len && $other_changed[$j]) 861 $j++; 862 } 863 } 864 } while ($runlength != $i - $start); 865 866 /* 867 * If possible, move the fully-merged run of changes 868 * back to a corresponding run in the other file. 869 */ 870 while ($corresponding < $i) { 871 $changed[--$start] = 1; 872 $changed[--$i] = 0; 873 assert('$j > 0'); 874 while ($other_changed[--$j]) 875 continue; 876 assert('$j >= 0 && !$other_changed[$j]'); 877 } 878 } 879 } 880 } 881 882 /** 883 * Class representing a 'diff' between two sequences of strings. 884 */ 885 class Diff 886 { 887 var $edits; 888 889 /** 890 * Constructor. 891 * Computes diff between sequences of strings. 892 * 893 * @param $from_lines array An array of strings. 894 * (Typically these are lines from a file.) 895 * @param $to_lines array An array of strings. 896 */ 897 function Diff($from_lines, $to_lines) { 898 $eng = new _DiffEngine; 899 $this->edits = $eng->diff($from_lines, $to_lines); 900 } 901 902 } 903 904 905 906 /** 907 * A class to format Diffs 908 * 909 * This class formats the diff in classic diff format. 910 * It is intended that this class be customized via inheritance, 911 * to obtain fancier outputs. 912 */ 913 class DiffFormatter 914 { 915 916 /** 917 * Format a diff. 918 * 919 * @param $diff object A Diff object. 920 * @return string The formatted output. 921 */ 922 function format($diff) { 923 924 $xi = $yi = 1; 925 $block = false; 926 $context = array(); 927 928 $this->_start_diff(); 929 930 foreach ($diff->edits as $edit) { 931 if ($edit->type == 'copy') { 932 if (is_array($block)) { 933 if (sizeof($edit->orig) <= 0) { 934 $block[] = $edit; 935 } 936 else{ 937 $this->_block($x0, + $xi - $x0, 938 $y0, + $yi - $y0, 939 $block); 940 $block = false; 941 } 942 } 943 } 944 else { 945 if (! is_array($block)) { 946 $x0 = $xi; 947 $y0 = $yi; 948 $block = array(); 949 } 950 $block[] = $edit; 951 } 952 953 if ($edit->orig) 954 $xi += sizeof($edit->orig); 955 if ($edit->final) 956 $yi += sizeof($edit->final); 957 } 958 959 if (is_array($block)) 960 $this->_block($x0, $xi - $x0, 961 $y0, $yi - $y0, 962 $block); 963 964 return $this->_end_diff(); 965 } 966 967 function _block($xbeg, $xlen, $ybeg, $ylen, &$edits) { 968 $this->_start_block($this->_block_header($xbeg, $xlen, $ybeg, $ylen)); 969 } 970 971 function _start_diff() { 972 ob_start(); 973 } 974 975 function _end_diff() { 976 $val = ob_get_contents(); 977 ob_end_clean(); 978 return $val; 979 } 980 981 function _block_header($xbeg, $xlen, $ybeg, $ylen) { 982 if ($xlen > 1) 983 $xbeg .= "," . ($xbeg + $xlen - 1); 984 if ($ylen > 1) 985 $ybeg .= "," . ($ybeg + $ylen - 1); 986 987 return $xbeg . ($xlen ? ($ylen ? 'c' : 'd') : 'a') . $ybeg; 988 } 989 990 function _start_block($header) { 991 echo $header."\n"; 992 } 993 994 } 995 996 997 ?> 998 </div> 999 <?php echo $this->Footer(); ?>
titre
Description
Corps
titre
Description
Corps
titre
Description
Corps
titre
Corps
| Généré le : Mon Nov 26 12:05:46 2007 | par Balluche grâce à PHPXref 0.7 |
|
|