Version: current

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

[Raise a SilverStripe Framework issue/bug](https://github.com/silverstripe/silverstripe-framework/issues/new)
- [Raise a SilverStripe CMS issue/bug](https://github.com/silverstripe/silverstripe-cms/issues/new)
- Please use the Silverstripe Forums to ask development related questions. -