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