lib/difflib.php

   1 <?php
   2
   3 // difflib.php
   4 //
   5 // A PHP diff engine for phpwiki.
   6 //
   7 // Copyright (C) 2000, 2001 Geoffrey T. Dairiki <dairiki@dairiki.org>
   8 // You may copy this code freely under the conditions of the GPL.
   9 //
  10
  11 class _DiffOp {
  12     var $type;
  13     var $orig;
  14     var $final;
  15
  16     function reverse() {
  17         trigger_error("pure virtual", E_USER_ERROR);
  18     }
  19
  20     function norig() {
  21         return $this->orig ? sizeof($this->orig) : 0;
  22     }
  23
  24     function nfinal() {
  25         return $this->final ? sizeof($this->final) : 0;
  26     }
  27 }
  28
  29 class _DiffOp_Copy extends _DiffOp {
  30     var $type = 'copy';
  31
  32     function _DiffOp_Copy ($orig, $final = false) {
  33         if (!is_array($final))
  34             $final = $orig;
  35         $this->orig = $orig;
  36         $this->final = $final;
  37     }
  38
  39     function reverse() {
  40         return new _DiffOp_Copy($this->final, $this->orig);
  41     }
  42 }
  43
  44 class _DiffOp_Delete extends _DiffOp {
  45     var $type = 'delete';
  46
  47     function _DiffOp_Delete ($lines) {
  48         $this->orig = $lines;
  49         $this->final = false;
  50     }
  51
  52     function reverse() {
  53         return new _DiffOp_Add($this->orig);
  54     }
  55 }
  56
  57 class _DiffOp_Add extends _DiffOp {
  58     var $type = 'add';
  59
  60     function _DiffOp_Add ($lines) {
  61         $this->final = $lines;
  62         $this->orig = false;
  63     }
  64
  65     function reverse() {
  66         return new _DiffOp_Delete($this->final);
  67     }
  68 }
  69
  70 class _DiffOp_Change extends _DiffOp {
  71     var $type = 'change';
  72
  73     function _DiffOp_Change ($orig, $final) {
  74         $this->orig = $orig;
  75         $this->final = $final;
  76     }
  77
  78     function reverse() {
  79         return new _DiffOp_Change($this->final, $this->orig);
  80     }
  81 }
  82
  83 /**
  84  * Class used internally by Diff to actually compute the diffs.
  85  *
  86  * The algorithm used here is mostly lifted from the perl module
  87  * Algorithm::Diff (version 1.06) by Ned Konz, which is available at:
  88  *   http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip
  89  *
  90  * More ideas are taken from:
  91  *   http://www.ics.uci.edu/~eppstein/161/960229.html
  92  *
  93  * Some ideas are (and a bit of code) are from from analyze.c, from GNU
  94  * diffutils-2.7, which can be found at:
  95  *   ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
  96  *
  97  * Finally, some ideas (subdivision by NCHUNKS > 2, and some optimizations)
  98  * are my own.
  99  *
 100  * @author Geoffrey T. Dairiki
 101  * @access private
 102  */
 103 class _DiffEngine
 104 {
 105     function diff ($from_lines, $to_lines) {
 106         $n_from = sizeof($from_lines);
 107         $n_to = sizeof($to_lines);
 108
 109         $this->xchanged = $this->ychanged = array();
 110         $this->xv = $this->yv = array();
 111         $this->xind = $this->yind = array();
 112         unset($this->seq);
 113         unset($this->in_seq);
 114         unset($this->lcs);
 115
 116         // Skip leading common lines.
 117         for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) {
 118             if ($from_lines[$skip] != $to_lines[$skip])
 119                 break;
 120             $this->xchanged[$skip] = $this->ychanged[$skip] = false;
 121         }
 122         // Skip trailing common lines.
 123         $xi = $n_from; $yi = $n_to;
 124         for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) {
 125             if ($from_lines[$xi] != $to_lines[$yi])
 126                 break;
 127             $this->xchanged[$xi] = $this->ychanged[$yi] = false;
 128         }
 129
 130         // Ignore lines which do not exist in both files.
 131         for ($xi = $skip; $xi < $n_from - $endskip; $xi++)
 132             $xhash[$from_lines[$xi]] = 1;
 133         for ($yi = $skip; $yi < $n_to - $endskip; $yi++) {
 134             $line = $to_lines[$yi];
 135             if ( ($this->ychanged[$yi] = empty($xhash[$line])) )
 136                 continue;
 137             $yhash[$line] = 1;
 138             $this->yv[] = $line;
 139             $this->yind[] = $yi;
 140         }
 141         for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
 142             $line = $from_lines[$xi];
 143             if ( ($this->xchanged[$xi] = empty($yhash[$line])) )
 144                 continue;
 145             $this->xv[] = $line;
 146             $this->xind[] = $xi;
 147         }
 148
 149         // Find the LCS.
 150         $this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv));
 151
 152         // Merge edits when possible
 153         $this->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged);
 154         $this->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged);
 155
 156         // Compute the edit operations.
 157         $edits = array();
 158         $xi = $yi = 0;
 159         while ($xi < $n_from || $yi < $n_to) {
 160             assert($yi < $n_to || $this->xchanged[$xi]);
 161             assert($xi < $n_from || $this->ychanged[$yi]);
 162
 163             // Skip matching "snake".
 164             $copy = array();
 165             while ( $xi < $n_from && $yi < $n_to
 166                     && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {
 167                 $copy[] = $from_lines[$xi++];
 168                 ++$yi;
 169             }
 170             if ($copy)
 171                 $edits[] = new _DiffOp_Copy($copy);
 172
 173             // Find deletes & adds.
 174             $delete = array();
 175             while ($xi < $n_from && $this->xchanged[$xi])
 176                 $delete[] = $from_lines[$xi++];
 177
 178             $add = array();
 179             while ($yi < $n_to && $this->ychanged[$yi])
 180                 $add[] = $to_lines[$yi++];
 181
 182             if ($delete && $add)
 183                 $edits[] = new _DiffOp_Change($delete, $add);
 184             elseif ($delete)
 185                 $edits[] = new _DiffOp_Delete($delete);
 186             elseif ($add)
 187                 $edits[] = new _DiffOp_Add($add);
 188         }
 189         return $edits;
 190     }
 191
 192     /* Divide the Largest Common Subsequence (LCS) of the sequences
 193      * [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally
 194      * sized segments.
 195      *
 196      * Returns (LCS, PTS).  LCS is the length of the LCS. PTS is an
 197      * array of NCHUNKS+1 (X, Y) indexes giving the diving points between
 198      * sub sequences.  The first sub-sequence is contained in [X0, X1),
 199      * [Y0, Y1), the second in [X1, X2), [Y1, Y2) and so on.  Note
 200      * that (X0, Y0) == (XOFF, YOFF) and
 201      * (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM).
 202      *
 203      * This function assumes that the first lines of the specified portions
 204      * of the two files do not match, and likewise that the last lines do not
 205      * match.  The caller must trim matching lines from the beginning and end
 206      * of the portions it is going to specify.
 207      */
 208     function _diag ($xoff, $xlim, $yoff, $ylim, $nchunks) {
 209     $flip = false;
 210
 211     if ($xlim - $xoff > $ylim - $yoff) {
 212         // Things seems faster (I'm not sure I understand why)
 213             // when the shortest sequence in X.
 214             $flip = true;
 215         list ($xoff, $xlim, $yoff, $ylim)
 216         = array( $yoff, $ylim, $xoff, $xlim);
 217         }
 218
 219     if ($flip)
 220         for ($i = $ylim - 1; $i >= $yoff; $i--)
 221         $ymatches[$this->xv[$i]][] = $i;
 222     else
 223         for ($i = $ylim - 1; $i >= $yoff; $i--)
 224         $ymatches[$this->yv[$i]][] = $i;
 225
 226     $this->lcs = 0;
 227     $this->seq[0]= $yoff - 1;
 228     $this->in_seq = array();
 229     $ymids[0] = array();
 230
 231     $numer = $xlim - $xoff + $nchunks - 1;
 232     $x = $xoff;
 233     for ($chunk = 0; $chunk < $nchunks; $chunk++) {
 234         if ($chunk > 0)
 235         for ($i = 0; $i <= $this->lcs; $i++)
 236             $ymids[$i][$chunk-1] = $this->seq[$i];
 237
 238         $x1 = $xoff + (int)(($numer + ($xlim-$xoff)*$chunk) / $nchunks);
 239         for ( ; $x < $x1; $x++) {
 240                 $line = $flip ? $this->yv[$x] : $this->xv[$x];
 241                 if (empty($ymatches[$line]))
 242             continue;
 243         $matches = $ymatches[$line];
 244                 reset($matches);
 245         while (list ($junk, $y) = each($matches))
 246             if (empty($this->in_seq[$y])) {
 247             $k = $this->_lcs_pos($y);
 248             assert($k > 0);
 249             $ymids[$k] = $ymids[$k-1];
 250             break;
 251                     }
 252         while (list ($junk, $y) = each($matches)) {
 253             if ($y > $this->seq[$k-1]) {
 254             assert($y < $this->seq[$k]);
 255             // Optimization: this is a common case:
 256             //  next match is just replacing previous match.
 257             $this->in_seq[$this->seq[$k]] = false;
 258             $this->seq[$k] = $y;
 259             $this->in_seq[$y] = 1;
 260                     }
 261             else if (empty($this->in_seq[$y])) {
 262             $k = $this->_lcs_pos($y);
 263             assert($k > 0);
 264             $ymids[$k] = $ymids[$k-1];
 265                     }
 266                 }
 267             }
 268         }
 269
 270     $seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff);
 271     $ymid = $ymids[$this->lcs];
 272     for ($n = 0; $n < $nchunks - 1; $n++) {
 273         $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks);
 274         $y1 = $ymid[$n] + 1;
 275         $seps[] = $flip ? array($y1, $x1) : array($x1, $y1);
 276         }
 277     $seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim);
 278
 279     return array($this->lcs, $seps);
 280     }
 281
 282     function _lcs_pos ($ypos) {
 283     $end = $this->lcs;
 284     if ($end == 0 || $ypos > $this->seq[$end]) {
 285         $this->seq[++$this->lcs] = $ypos;
 286         $this->in_seq[$ypos] = 1;
 287         return $this->lcs;
 288         }
 289
 290     $beg = 1;
 291     while ($beg < $end) {
 292         $mid = (int)(($beg + $end) / 2);
 293         if ( $ypos > $this->seq[$mid] )
 294         $beg = $mid + 1;
 295         else
 296         $end = $mid;
 297         }
 298
 299     assert($ypos != $this->seq[$end]);
 300
 301     $this->in_seq[$this->seq[$end]] = false;
 302     $this->seq[$end] = $ypos;
 303     $this->in_seq[$ypos] = 1;
 304     return $end;
 305     }
 306
 307     /* Find LCS of two sequences.
 308      *
 309      * The results are recorded in the vectors $this->{x,y}changed[], by
 310      * storing a 1 in the element for each line that is an insertion
 311      * or deletion (ie. is not in the LCS).
 312      *
 313      * The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1.
 314      *
 315      * Note that XLIM, YLIM are exclusive bounds.
 316      * All line numbers are origin-0 and discarded lines are not counted.
 317      */
 318     function _compareseq ($xoff, $xlim, $yoff, $ylim) {
 319     // Slide down the bottom initial diagonal.
 320     while ($xoff < $xlim && $yoff < $ylim
 321                && $this->xv[$xoff] == $this->yv[$yoff]) {
 322         ++$xoff;
 323         ++$yoff;
 324         }
 325
 326     // Slide up the top initial diagonal.
 327     while ($xlim > $xoff && $ylim > $yoff
 328                && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) {
 329         --$xlim;
 330         --$ylim;
 331         }
 332
 333     if ($xoff == $xlim || $yoff == $ylim)
 334         $lcs = 0;
 335     else {
 336         // This is ad hoc but seems to work well.
 337         //$nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5);
 338         //$nchunks = max(2,min(8,(int)$nchunks));
 339         $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1;
 340         list ($lcs, $seps)
 341         = $this->_diag($xoff,$xlim,$yoff, $ylim,$nchunks);
 342         }
 343
 344     if ($lcs == 0) {
 345         // X and Y sequences have no common subsequence:
 346         // mark all changed.
 347         while ($yoff < $ylim)
 348         $this->ychanged[$this->yind[$yoff++]] = 1;
 349         while ($xoff < $xlim)
 350         $this->xchanged[$this->xind[$xoff++]] = 1;
 351         }
 352     else {
 353         // Use the partitions to split this problem into subproblems.
 354         reset($seps);
 355         $pt1 = $seps[0];
 356         while ($pt2 = next($seps)) {
 357         $this->_compareseq ($pt1[0], $pt2[0], $pt1[1], $pt2[1]);
 358         $pt1 = $pt2;
 359             }
 360         }
 361     }
 362
 363     /* Adjust inserts/deletes of identical lines to join changes
 364      * as much as possible.
 365      *
 366      * We do something when a run of changed lines include a
 367      * line at one end and has an excluded, identical line at the other.
 368      * We are free to choose which identical line is included.
 369      * `compareseq' usually chooses the one at the beginning,
 370      * but usually it is cleaner to consider the following identical line
 371      * to be the "change".
 372      *
 373      * This is extracted verbatim from analyze.c (GNU diffutils-2.7).
 374      */
 375     function _shift_boundaries ($lines, &$changed, $other_changed) {
 376     $i = 0;
 377     $j = 0;
 378
 379     assert('sizeof($lines) == sizeof($changed)');
 380     $len = sizeof($lines);
 381     $other_len = sizeof($other_changed);
 382
 383     while (1) {
 384         /*
 385          * Scan forwards to find beginning of another run of changes.
 386          * Also keep track of the corresponding point in the other file.
 387          *
 388          * Throughout this code, $i and $j are adjusted together so that
 389          * the first $i elements of $changed and the first $j elements
 390          * of $other_changed both contain the same number of zeros
 391          * (unchanged lines).
 392          * Furthermore, $j is always kept so that $j == $other_len or
 393          * $other_changed[$j] == false.
 394          */
 395         while ($j < $other_len && $other_changed[$j])
 396         $j++;
 397
 398         while ($i < $len && ! $changed[$i]) {
 399         assert('$j < $other_len && ! $other_changed[$j]');
 400         $i++; $j++;
 401         while ($j < $other_len && $other_changed[$j])
 402             $j++;
 403             }
 404
 405         if ($i == $len)
 406         break;
 407
 408         $start = $i;
 409
 410         // Find the end of this run of changes.
 411         while (++$i < $len && $changed[$i])
 412         continue;
 413
 414         do {
 415         /*
 416          * Record the length of this run of changes, so that
 417          * we can later determine whether the run has grown.
 418          */
 419         $runlength = $i - $start;
 420
 421         /*
 422          * Move the changed region back, so long as the
 423          * previous unchanged line matches the last changed one.
 424          * This merges with previous changed regions.
 425          */
 426         while ($start > 0 && $lines[$start - 1] == $lines[$i - 1]) {
 427             $changed[--$start] = 1;
 428             $changed[--$i] = false;
 429             while ($start > 0 && $changed[$start - 1])
 430             $start--;
 431             assert('$j > 0');
 432             while ($other_changed[--$j])
 433             continue;
 434             assert('$j >= 0 && !$other_changed[$j]');
 435                 }
 436
 437         /*
 438          * Set CORRESPONDING to the end of the changed run, at the last
 439          * point where it corresponds to a changed run in the other file.
 440          * CORRESPONDING == LEN means no such point has been found.
 441          */
 442         $corresponding = $j < $other_len ? $i : $len;
 443
 444         /*
 445          * Move the changed region forward, so long as the
 446          * first changed line matches the following unchanged one.
 447          * This merges with following changed regions.
 448          * Do this second, so that if there are no merges,
 449          * the changed region is moved forward as far as possible.
 450          */
 451         while ($i < $len && $lines[$start] == $lines[$i]) {
 452             $changed[$start++] = false;
 453             $changed[$i++] = 1;
 454             while ($i < $len && $changed[$i])
 455             $i++;
 456
 457             assert('$j < $other_len && ! $other_changed[$j]');
 458             $j++;
 459             if ($j < $other_len && $other_changed[$j]) {
 460             $corresponding = $i;
 461             while ($j < $other_len && $other_changed[$j])
 462                 $j++;
 463                     }
 464                 }
 465             } while ($runlength != $i - $start);
 466
 467         /*
 468          * If possible, move the fully-merged run of changes
 469          * back to a corresponding run in the other file.
 470          */
 471         while ($corresponding < $i) {
 472         $changed[--$start] = 1;
 473         $changed[--$i] = 0;
 474         assert('$j > 0');
 475         while ($other_changed[--$j])
 476             continue;
 477         assert('$j >= 0 && !$other_changed[$j]');
 478             }
 479         }
 480     }
 481 }
 482
 483 /**
 484  * Class representing a 'diff' between two sequences of strings.
 485  */
 486 class Diff
 487 {
 488     var $edits;
 489
 490     /**
 491      * Constructor.
 492      * Computes diff between sequences of strings.
 493      *
 494      * @param $from_lines array An array of strings.
 495      *        (Typically these are lines from a file.)
 496      * @param $to_lines array An array of strings.
 497      */
 498     function Diff($from_lines, $to_lines) {
 499         $eng = new _DiffEngine;
 500         $this->edits = $eng->diff($from_lines, $to_lines);
 501         //$this->_check($from_lines, $to_lines);
 502     }
 503
 504     /**
 505      * Compute reversed Diff.
 506      *
 507      * SYNOPSIS:
 508      *
 509      *  $diff = new Diff($lines1, $lines2);
 510      *  $rev = $diff->reverse();
 511      * @return object A Diff object representing the inverse of the
 512      *                original diff.
 513      */
 514     function reverse () {
 515     $rev = $this;
 516         $rev->edits = array();
 517         foreach ($this->edits as $edit) {
 518             $rev->edits[] = $edit->reverse();
 519         }
 520     return $rev;
 521     }
 522
 523     /**
 524      * Check for empty diff.
 525      *
 526      * @return bool True iff two sequences were identical.
 527      */
 528     function isEmpty () {
 529         foreach ($this->edits as $edit) {
 530             if ($edit->type != 'copy')
 531                 return false;
 532         }
 533         return true;
 534     }
 535
 536     /**
 537      * Compute the length of the Longest Common Subsequence (LCS).
 538      *
 539      * This is mostly for diagnostic purposed.
 540      *
 541      * @return int The length of the LCS.
 542      */
 543     function lcs () {
 544     $lcs = 0;
 545         foreach ($this->edits as $edit) {
 546             if ($edit->type == 'copy')
 547                 $lcs += sizeof($edit->orig);
 548         }
 549     return $lcs;
 550     }
 551
 552     /**
 553      * Get the original set of lines.
 554      *
 555      * This reconstructs the $from_lines parameter passed to the
 556      * constructor.
 557      *
 558      * @return array The original sequence of strings.
 559      */
 560     function orig() {
 561         $lines = array();
 562
 563         foreach ($this->edits as $edit) {
 564             if ($edit->orig)
 565                 array_splice($lines, sizeof($lines), 0, $edit->orig);
 566         }
 567         return $lines;
 568     }
 569
 570     /**
 571      * Get the final set of lines.
 572      *
 573      * This reconstructs the $to_lines parameter passed to the
 574      * constructor.
 575      *
 576      * @return array The sequence of strings.
 577      */
 578     function _final() {
 579         $lines = array();
 580
 581         foreach ($this->edits as $edit) {
 582             if ($edit->final)
 583                 array_splice($lines, sizeof($lines), 0, $edit->final);
 584         }
 585         return $lines;
 586     }
 587
 588     /**
 589      * Check a Diff for validity.
 590      *
 591      * This is here only for debugging purposes.
 592      */
 593     function _check ($from_lines, $to_lines) {
 594         if (serialize($from_lines) != serialize($this->orig()))
 595             trigger_error("Reconstructed original doesn't match", E_USER_ERROR);
 596         if (serialize($to_lines) != serialize($this->_final()))
 597             trigger_error("Reconstructed final doesn't match", E_USER_ERROR);
 598
 599         $rev = $this->reverse();
 600         if (serialize($to_lines) != serialize($rev->orig()))
 601             trigger_error("Reversed original doesn't match", E_USER_ERROR);
 602         if (serialize($from_lines) != serialize($rev->_final()))
 603             trigger_error("Reversed final doesn't match", E_USER_ERROR);
 604
 605         $prevtype = 'none';
 606         foreach ($this->edits as $edit) {
 607             if ( $prevtype == $edit->type )
 608                 trigger_error("Edit sequence is non-optimal", E_USER_ERROR);
 609             $prevtype = $edit->type;
 610         }
 611
 612         $lcs = $this->lcs();
 613         trigger_error("Diff okay: LCS = $lcs", E_USER_NOTICE);
 614     }
 615 }
 616
 617 /**
 618  * FIXME: bad name.
 619  */
 620 class MappedDiff
 621 extends Diff
 622 {
 623     /**
 624      * Constructor.
 625      *
 626      * Computes diff between sequences of strings.
 627      *
 628      * This can be used to compute things like
 629      * case-insensitve diffs, or diffs which ignore
 630      * changes in white-space.
 631      *
 632      * @param $from_lines array An array of strings.
 633      *  (Typically these are lines from a file.)
 634      *
 635      * @param $to_lines array An array of strings.
 636      *
 637      * @param $mapped_from_lines array This array should
 638      *  have the same size number of elements as $from_lines.
 639      *  The elements in $mapped_from_lines and
 640      *  $mapped_to_lines are what is actually compared
 641      *  when computing the diff.
 642      *
 643      * @param $mapped_to_lines array This array should
 644      *  have the same number of elements as $to_lines.
 645      */
 646     function MappedDiff($from_lines, $to_lines,
 647                         $mapped_from_lines, $mapped_to_lines) {
 648
 649         assert(sizeof($from_lines) == sizeof($mapped_from_lines));
 650         assert(sizeof($to_lines) == sizeof($mapped_to_lines));
 651
 652         $this->Diff($mapped_from_lines, $mapped_to_lines);
 653
 654         $xi = $yi = 0;
 655         // Optimizing loop invariants:
 656         // http://phplens.com/lens/php-book/optimizing-debugging-php.php
 657         for ($i = 0, $max = sizeof($this->edits); $i < $max; $i++) {
 658             $orig = &$this->edits[$i]->orig;
 659             if (is_array($orig)) {
 660                 $orig = array_slice($from_lines, $xi, sizeof($orig));
 661                 $xi += sizeof($orig);
 662             }
 663
 664             $final = &$this->edits[$i]->final;
 665             if (is_array($final)) {
 666                 $final = array_slice($to_lines, $yi, sizeof($final));
 667                 $yi += sizeof($final);
 668             }
 669         }
 670     }
 671 }
 672
 673 /**
 674  * A class to format Diffs
 675  *
 676  * This class formats the diff in classic diff format.
 677  * It is intended that this class be customized via inheritance,
 678  * to obtain fancier outputs.
 679  */
 680 class DiffFormatter
 681 {
 682     /**
 683      * Number of leading context "lines" to preserve.
 684      *
 685      * This should be left at zero for this class, but subclasses
 686      * may want to set this to other values.
 687      */
 688     var $leading_context_lines = 0;
 689
 690     /**
 691      * Number of trailing context "lines" to preserve.
 692      *
 693      * This should be left at zero for this class, but subclasses
 694      * may want to set this to other values.
 695      */
 696     var $trailing_context_lines = 0;
 697
 698     /**
 699      * Format a diff.
 700      *
 701      * @param $diff object A Diff object.
 702      * @return string The formatted output.
 703      */
 704     function format($diff) {
 705
 706         $xi = $yi = 1;
 707         $block = false;
 708         $context = array();
 709
 710         $nlead = $this->leading_context_lines;
 711         $ntrail = $this->trailing_context_lines;
 712
 713         $this->_start_diff();
 714
 715         foreach ($diff->edits as $edit) {
 716             if ($edit->type == 'copy') {
 717                 if (is_array($block)) {
 718                     if (sizeof($edit->orig) <= $nlead + $ntrail) {
 719                         $block[] = $edit;
 720                     }
 721                     else{
 722                         if ($ntrail) {
 723                             $context = array_slice($edit->orig, 0, $ntrail);
 724                             $block[] = new _DiffOp_Copy($context);
 725                         }
 726                         $this->_block($x0, $ntrail + $xi - $x0,
 727                                       $y0, $ntrail + $yi - $y0,
 728                                       $block);
 729                         $block = false;
 730                     }
 731                 }
 732                 $context = $edit->orig;
 733             }
 734             else {
 735                 if (! is_array($block)) {
 736                     $context = array_slice($context, max(0, sizeof($context) - $nlead));
 737                     $x0 = $xi - sizeof($context);
 738                     $y0 = $yi - sizeof($context);
 739                     $block = array();
 740                     if ($context)
 741                         $block[] = new _DiffOp_Copy($context);
 742                 }
 743                 $block[] = $edit;
 744             }
 745
 746             if ($edit->orig)
 747                 $xi += sizeof($edit->orig);
 748             if ($edit->final)
 749                 $yi += sizeof($edit->final);
 750         }
 751
 752         if (is_array($block))
 753             $this->_block($x0, $xi - $x0,
 754                           $y0, $yi - $y0,
 755                           $block);
 756
 757         return $this->_end_diff();
 758     }
 759
 760     function _block($xbeg, $xlen, $ybeg, $ylen, &$edits) {
 761         $this->_start_block($this->_block_header($xbeg, $xlen, $ybeg, $ylen));
 762         foreach ($edits as $edit) {
 763             if ($edit->type == 'copy')
 764                 $this->_context($edit->orig);
 765             elseif ($edit->type == 'add')
 766                 $this->_added($edit->final);
 767             elseif ($edit->type == 'delete')
 768                 $this->_deleted($edit->orig);
 769             elseif ($edit->type == 'change')
 770                 $this->_changed($edit->orig, $edit->final);
 771             else
 772                 trigger_error("Unknown edit type", E_USER_ERROR);
 773         }
 774         $this->_end_block();
 775     }
 776
 777     function _start_diff() {
 778         ob_start();
 779     }
 780
 781     function _end_diff() {
 782         $val = ob_get_contents();
 783         ob_end_clean();
 784         return $val;
 785     }
 786
 787     function _block_header($xbeg, $xlen, $ybeg, $ylen) {
 788         if ($xlen > 1)
 789             $xbeg .= "," . ($xbeg + $xlen - 1);
 790         if ($ylen > 1)
 791             $ybeg .= "," . ($ybeg + $ylen - 1);
 792
 793         return $xbeg . ($xlen ? ($ylen ? 'c' : 'd') : 'a') . $ybeg;
 794     }
 795
 796     function _start_block($header) {
 797         echo $header;
 798     }
 799
 800     function _end_block() {
 801     }
 802
 803     function _lines($lines, $prefix = ' ') {
 804         foreach ($lines as $line)
 805             echo "$prefix $line\n";
 806     }
 807
 808     function _context($lines) {
 809         $this->_lines($lines);
 810     }
 811
 812     function _added($lines) {
 813         $this->_lines($lines, ">");
 814     }
 815     function _deleted($lines) {
 816         $this->_lines($lines, "<");
 817     }
 818
 819     function _changed($orig, $final) {
 820         $this->_deleted($orig);
 821         echo "---\n";
 822         $this->_added($final);
 823     }
 824 }
 825
 826 /**
 827  * "Unified" diff formatter.
 828  *
 829  * This class formats the diff in classic "unified diff" format.
 830  */
 831 class UnifiedDiffFormatter extends DiffFormatter
 832 {
 833     function UnifiedDiffFormatter($context_lines = 4) {
 834         $this->leading_context_lines = $context_lines;
 835         $this->trailing_context_lines = $context_lines;
 836     }
 837
 838     function _block_header($xbeg, $xlen, $ybeg, $ylen) {
 839         if ($xlen != 1)
 840             $xbeg .= "," . $xlen;
 841         if ($ylen != 1)
 842             $ybeg .= "," . $ylen;
 843         return "@@ -$xbeg +$ybeg @@\n";
 844     }
 845
 846     function _added($lines) {
 847         $this->_lines($lines, "+");
 848     }
 849     function _deleted($lines) {
 850         $this->_lines($lines, "-");
 851     }
 852     function _changed($orig, $final) {
 853         $this->_deleted($orig);
 854         $this->_added($final);
 855     }
 856 }
 857
 858 /**
 859  * block conflict diff formatter.
 860  *
 861  * This class will format a diff identical to Diff3 (i.e. editpage
 862  * conflicts), but when there are only two source files. To be used by
 863  * future enhancements to reloading / upgrading pgsrc.
 864  *
 865  * Functional but not finished yet, need to eliminate redundant block
 866  * suffixes (i.e. "=======" immediately followed by another prefix)
 867  * see class LoadFileConflictPageEditor
 868  */
 869 class BlockDiffFormatter extends DiffFormatter
 870 {
 871     function BlockDiffFormatter($context_lines = 4) {
 872         $this->leading_context_lines = $context_lines;
 873         $this->trailing_context_lines = $context_lines;
 874     }
 875     function _lines($lines, $prefix = '') {
 876         if (! $prefix == '')
 877             echo "$prefix\n";
 878         foreach ($lines as $line)
 879             echo "$line\n";
 880         if (! $prefix == '')
 881             echo "$prefix\n";
 882     }
 883     function _added($lines) {
 884         $this->_lines($lines, ">>>>>>>");
 885     }
 886     function _deleted($lines) {
 887         $this->_lines($lines, "<<<<<<<");
 888     }
 889     function _block_header($xbeg, $xlen, $ybeg, $ylen) {
 890         return "";
 891     }
 892     function _changed($orig, $final) {
 893         $this->_deleted($orig);
 894         $this->_added($final);
 895     }
 896 }
 897
 898 // Local Variables:
 899 // mode: php
 900 // tab-width: 8
 901 // c-basic-offset: 4
 902 // c-hanging-comment-ender-p: nil
 903 // indent-tabs-mode: nil
 904 // End: