lib/difflib.php

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