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