Subversion Repositories Applications.papyrus

Rev

Go to most recent revision | Details | Last modification | View Log | RSS feed

Rev Author Line No. Line
439 ddelon 1
<?php
2
/*
3
diff.php
4
 
5
Copyright (C) 1992 Free Software Foundation, Inc. Francois Pinard <pinard@iro.umontreal.ca>.
6
Copyright (C) 2000, 2001 Geoffrey T. Dairiki <dairiki@dairiki.org>
7
Copyright 2002,2003,2004  David DELON
8
Copyright 2002  Patrick PAUL
9
Copyright 2003  Eric FELDSTEIN
10
 
11
This program is free software; you can redistribute it and/or modify
12
it under the terms of the GNU General Public License as published by
13
the Free Software Foundation; either version 2 of the License, or
14
(at your option) any later version.
15
 
16
This program is distributed in the hope that it will be useful,
17
but WITHOUT ANY WARRANTY; without even the implied warranty of
18
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19
GNU General Public License for more details.
20
 
21
You should have received a copy of the GNU General Public License
22
along with this program; if not, write to the Free Software
23
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
24
 
25
original diff.php
26
Copyright (c) 2002, Hendrik Mans <hendrik@mans.de>
27
All rights reserved.
28
Redistribution and use in source and binary forms, with or without
29
modification, are permitted provided that the following conditions
30
are met:
31
1. Redistributions of source code must retain the above copyright
32
notice, this list of conditions and the following disclaimer.
33
2. Redistributions in binary form must reproduce the above copyright
34
notice, this list of conditions and the following disclaimer in the
35
documentation and/or other materials provided with the distribution.
36
3. The name of the author may not be used to endorse or promote products
37
derived from this software without specific prior written permission.
38
 
39
THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
40
IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
41
OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
42
IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
43
INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
44
NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
45
DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
46
THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
47
(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
48
THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
49
*/
50
 
51
 
52
//vérification de sécurité
53
if (!eregi("wakka.php", $_SERVER['PHP_SELF'])) {
54
    die ("acc&egrave;s direct interdit");
55
}
56
echo $this->Header();
57
?>
58
<div class="page">
59
<?php
60
 
61
if ($this->HasAccess("read"))
62
{
63
 
64
// If asked, call original diff
65
 
66
	if ($_REQUEST["fastdiff"]) {
67
 
68
		/* NOTE: This is a really cheap way to do it. I think it may be more intelligent to write the two pages to temporary files and run /usr/bin/diff over them. Then again, maybe not.        */
69
		// load pages
70
		  $pageA = $this->LoadPageById($_REQUEST["a"]);
71
		  $pageB = $this->LoadPageById($_REQUEST["b"]);
72
 
73
		// prepare bodies
74
		  $bodyA = explode("\n", $pageA["body"]);
75
		  $bodyB = explode("\n", $pageB["body"]);
76
 
77
		  $added = array_diff($bodyA, $bodyB);
78
		  $deleted = array_diff($bodyB, $bodyA);
79
 
80
		  $output .= "<b>Comparaison de <a href=\"".$this->href("", "", "time=".urlencode($pageA["time"]))."\">".$pageA["time"]."</a> &agrave; <a href=\"".$this->href("", "", "time=".urlencode($pageB["time"]))."\">".$pageB["time"]."</a></b><br />\n";
81
 
82
		  if ($added)
83
		  {
84
			// remove blank lines
85
			$output .= "<br />\n<b>Ajouts:</b><br />\n";
86
			$output .= "<div class=\"additions\">".$this->Format(implode("\n", $added))."</div>";
87
		  }
88
 
89
		  if ($deleted)
90
		  {
91
			$output .= "<br />\n<b>Suppressions:</b><br />\n";
92
			$output .= "<div class=\"deletions\">".$this->Format(implode("\n", $deleted))."</div>";
93
		  }
94
 
95
		  if (!$added && !$deleted)
96
		  {
97
			$output .= "<br />\nPas de diff&eacute;rences.";
98
		  }
99
		  echo $output;
100
 
101
	}
102
 
103
	else {
104
 
105
	// load pages
106
 
107
		$pageA = $this->LoadPageById($_REQUEST["b"]);
108
		$pageB = $this->LoadPageById($_REQUEST["a"]);
109
 
110
		// extract text from bodies
111
		$textA = $pageA["body"];
112
		$textB = $pageB["body"];
113
 
114
		$sideA = new Side($textA);
115
		$sideB = new Side($textB);
116
 
117
		$bodyA='';
118
		$sideA->split_file_into_words($bodyA);
119
 
120
		$bodyB='';
121
		$sideB->split_file_into_words($bodyB);
122
 
123
		// diff on these two file
124
		$diff = new Diff(split("\n",$bodyA),split("\n",$bodyB));
125
 
126
		// format output
127
		$fmt = new DiffFormatter();
128
 
129
		$sideO = new Side($fmt->format($diff));
130
 
131
		$resync_left=0;
132
		$resync_right=0;
133
 
134
		$count_total_right=$sideB->getposition() ;
135
 
136
		$sideA->init();
137
		$sideB->init();
138
 
139
		$output='';
140
 
141
		  while (1) {
142
 
143
		      $sideO->skip_line();
144
		      if ($sideO->isend()) {
145
			  break;
146
		      }
147
 
148
		      if ($sideO->decode_directive_line()) {
149
			$argument=$sideO->getargument();
150
			$letter=$sideO->getdirective();
151
		      switch ($letter) {
152
			    case 'a':
153
			      $resync_left = $argument[0];
154
			      $resync_right = $argument[2] - 1;
155
			      break;
156
 
157
			    case 'd':
158
			      $resync_left = $argument[0] - 1;
159
			      $resync_right = $argument[2];
160
			      break;
161
 
162
			    case 'c':
163
			      $resync_left = $argument[0] - 1;
164
			      $resync_right = $argument[2] - 1;
165
			      break;
166
 
167
			    }
168
 
169
			    $sideA->skip_until_ordinal($resync_left);
170
			    $sideB->copy_until_ordinal($resync_right,$output);
171
 
172
	// deleted word
173
 
174
			    if (($letter=='d') || ($letter=='c')) {
175
			      $sideA->copy_whitespace($output);
176
			      $output .="@@";
177
			      $sideA->copy_word($output);
178
			      $sideA->copy_until_ordinal($argument[1],$output);
179
			      $output .="@@";
180
			    }
181
 
182
	// inserted word
183
			    if ($letter == 'a' || $letter == 'c') {
184
				$sideB->copy_whitespace($output);
185
				$output .="££";
186
				$sideB->copy_word($output);
187
				$sideB->copy_until_ordinal($argument[3],$output);
188
				$output .="££";
189
			    }
190
 
191
		  }
192
 
193
		}
194
 
195
		  $sideB->copy_until_ordinal($count_total_right,$output);
196
		  $sideB->copy_whitespace($output);
197
		  $out=$this->Format($output);
198
		  echo $out;
199
 
200
	}
201
 
202
}
203
else{
204
	echo "<i>Vous n'&ecirc;tes pas autoris&eacute; &agrave; lire cette page.</i>" ;
205
}
206
 
207
	// Side : a string for wdiff
208
 
209
	class Side {
210
	    var $position;
211
	    var $cursor;
212
	    var $content;
213
	    var $character;
214
	    var $directive;
215
	    var $argument;
216
	    var $length;
217
 
218
	    function Side($content) {
219
	       $this->content=$content;
220
	       $this->position=0;
221
	       $this->cursor=0;
222
	       $this->directive='';
223
	       $this->argument=array();
224
	       $this->length=strlen($this->content);
225
	       $this->character=substr($this->content,0,1);
226
 
227
	    }
228
 
229
	    function getposition() {
230
	       return $this->position;
231
	    }
232
 
233
	    function getcharacter() {
234
	       return $this->character;
235
	    }
236
 
237
	    function getdirective() {
238
	       return $this->directive;
239
	    }
240
 
241
	    function getargument() {
242
	       return $this->argument;
243
	    }
244
 
245
	    function nextchar() {
246
	       $this->cursor++;
247
	       $this->character=substr($this->content,$this->cursor,1);
248
	    }
249
 
250
	    function copy_until_ordinal($ordinal,&$out)  {
251
	       while ($this->position < $ordinal) {
252
		  $this->copy_whitespace($out);
253
		  $this->copy_word($out);
254
	       }
255
	    }
256
 
257
	    function skip_until_ordinal($ordinal) {
258
	       while ($this->position < $ordinal) {
259
		  $this->skip_whitespace();
260
		  $this->skip_word();
261
	       }
262
	    }
263
 
264
	    function split_file_into_words (&$out) {
265
	       while (!$this->isend()) {
266
		 $this->skip_whitespace();
267
		 if ($this->isend()) {
268
		   break;
269
		 }
270
		 $this->copy_word($out);
271
		 $out .="\n";
272
	       }
273
	    }
274
 
275
	    function init() {
276
	       $this->position=0;
277
	       $this->cursor=0;
278
	       $this->directive='';
279
	       $this->argument=array();
280
	       $this->character=substr($this->content,0,1);
281
	    }
282
 
283
	    function isspace($char) {
284
	       if (ereg('[[:space:]]',$char)) {
285
		  return true;
286
	       }
287
	       else {
288
		  return false;
289
	       }
290
	    }
291
 
292
	    function isdigit($char) {
293
	       if (ereg('[[:digit:]]',$char)) {
294
		  return true;
295
	       }
296
	       else {
297
		  return false;
298
	       }
299
	    }
300
 
301
	    function isend() {
302
	       if (($this->cursor)>=($this->length)) {
303
		  return true;
304
	       }
305
	       else {
306
		  return false;
307
	       }
308
	    }
309
 
310
 
311
 
312
	    function copy_whitespace(&$out)  {
313
		 while (!$this->isend() && $this->isspace($this->character)) {
314
		    $out .=$this->character;
315
		    $this->nextchar();
316
		 }
317
	    }
318
 
319
	    function skip_whitespace()  {
320
		 while (!$this->isend() && $this->isspace($this->character)) {
321
		    $this->nextchar();
322
		 }
323
	    }
324
 
325
	    function skip_line()  {
326
	      while (!$this->isend() && !$this->isdigit($this->character)) {
327
		  while (!$this->isend() && $this->character!="\n")
328
		  $this->nextchar();
329
		  if($this->character=="\n")
330
		      $this->nextchar();
331
	       }
332
	     }
333
 
334
 
335
 
336
	     function copy_word(&$out) {
337
		 while (!$this->isend() && !($this->isspace($this->character))) {
338
		    $out.=$this->character;
339
		    $this->nextchar();
340
		 }
341
		 $this->position++;
342
	     }
343
 
344
	     function skip_word() {
345
 
346
		 while (!$this->isend() && !($this->isspace($this->character))) {
347
		    $this->nextchar();
348
		 }
349
		 $this->position++;
350
	     }
351
 
352
 
353
	 function decode_directive_line() {
354
 
355
	  $value=0;
356
	  $state=0;
357
	  $error=0;
358
 
359
	  while (!$error && $state < 4) {
360
	      if ($this->isdigit($this->character)) {
361
		  $value = 0;
362
		  while($this->isdigit($this->character)) {
363
		      $value = 10 * $value + $this->character - '0';
364
		      $this->nextchar();
365
		  }
366
	      }
367
	      else if ($state != 1 && $state != 3)
368
	      $error = 1;
369
 
370
	      /* Assign the proper value.  */
371
 
372
	      $this->argument[$state] = $value;
373
 
374
	      /* Skip the following character.  */
375
 
376
	      switch ($state) {
377
		case 0:
378
		case 2:
379
		  if ($this->character == ',')
380
		     $this->nextchar();
381
		  break;
382
 
383
		case 1:
384
		  if ($this->character == 'a' || $this->character == 'd' || $this->character == 'c') {
385
		      $this->directive = $this->character;
386
		      $this->nextchar();
387
		    }
388
		  else
389
		    $error = 1;
390
		  break;
391
 
392
		  case 3:
393
		  if ($this->character != "\n")
394
		    $error = 1;
395
		    break;
396
		  }
397
		 $state++;
398
	      }
399
 
400
	  /* Complete reading of the line and return success value.  */
401
 
402
	  while ((!$this->isend()) && ($this->character != "\n")) {
403
	      $this->nextchar();
404
	  }
405
	  if ($this->character == "\n")
406
	      $this->nextchar();
407
 
408
	  return !$error;
409
	}
410
 
411
 
412
 
413
	}
414
 
415
	// difflib
416
	//
417
	// A PHP diff engine for phpwiki.
418
	//
419
	// Copyright (C) 2000, 2001 Geoffrey T. Dairiki <dairiki@dairiki.org>
420
	// You may copy this code freely under the conditions of the GPL.
421
	//
422
 
423
 
424
	// PHP3 does not have assert()
425
	define('USE_ASSERTS', function_exists('assert'));
426
 
427
	class _DiffOp {
428
	    var $type;
429
	    var $orig;
430
	    var $final;
431
 
432
 
433
	    function norig() {
434
		return $this->orig ? sizeof($this->orig) : 0;
435
	    }
436
 
437
	    function nfinal() {
438
		return $this->final ? sizeof($this->final) : 0;
439
	    }
440
	}
441
 
442
	class _DiffOp_Copy extends _DiffOp {
443
	    var $type = 'copy';
444
 
445
	    function _DiffOp_Copy ($orig, $final = false) {
446
		if (!is_array($final))
447
		    $final = $orig;
448
		$this->orig = $orig;
449
		$this->final = $final;
450
	    }
451
 
452
	}
453
 
454
	class _DiffOp_Delete extends _DiffOp {
455
	    var $type = 'delete';
456
 
457
	    function _DiffOp_Delete ($lines) {
458
		$this->orig = $lines;
459
		$this->final = false;
460
	    }
461
 
462
	}
463
 
464
	class _DiffOp_Add extends _DiffOp {
465
	    var $type = 'add';
466
 
467
	    function _DiffOp_Add ($lines) {
468
		$this->final = $lines;
469
		$this->orig = false;
470
	    }
471
 
472
	}
473
 
474
	class _DiffOp_Change extends _DiffOp {
475
	    var $type = 'change';
476
 
477
	    function _DiffOp_Change ($orig, $final) {
478
		$this->orig = $orig;
479
		$this->final = $final;
480
	    }
481
 
482
	}
483
 
484
 
485
	/**
486
	 * Class used internally by Diff to actually compute the diffs.
487
	 *
488
	 * The algorithm used here is mostly lifted from the perl module
489
	 * Algorithm::Diff (version 1.06) by Ned Konz, which is available at:
490
	 *   http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip
491
	 *
492
	 * More ideas are taken from:
493
	 *   http://www.ics.uci.edu/~eppstein/161/960229.html
494
	 *
495
	 * Some ideas are (and a bit of code) are from from analyze.c, from GNU
496
	 * diffutils-2.7, which can be found at:
497
	 *   ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
498
	 *
499
	 * Finally, some ideas (subdivision by NCHUNKS > 2, and some optimizations)
500
	 * are my own.
501
	 *
502
	 * @author Geoffrey T. Dairiki
503
	 * @access private
504
	 */
505
	class _DiffEngine
506
	{
507
	    function diff ($from_lines, $to_lines) {
508
		$n_from = sizeof($from_lines);
509
		$n_to = sizeof($to_lines);
510
 
511
		$this->xchanged = $this->ychanged = array();
512
		$this->xv = $this->yv = array();
513
		$this->xind = $this->yind = array();
514
		unset($this->seq);
515
		unset($this->in_seq);
516
		unset($this->lcs);
517
 
518
		// Skip leading common lines.
519
		for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) {
520
		    if ($from_lines[$skip] != $to_lines[$skip])
521
			break;
522
		    $this->xchanged[$skip] = $this->ychanged[$skip] = false;
523
		}
524
		// Skip trailing common lines.
525
		$xi = $n_from; $yi = $n_to;
526
		for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) {
527
		    if ($from_lines[$xi] != $to_lines[$yi])
528
			break;
529
		    $this->xchanged[$xi] = $this->ychanged[$yi] = false;
530
		}
531
 
532
		// Ignore lines which do not exist in both files.
533
		for ($xi = $skip; $xi < $n_from - $endskip; $xi++)
534
		    $xhash[$from_lines[$xi]] = 1;
535
		for ($yi = $skip; $yi < $n_to - $endskip; $yi++) {
536
		    $line = $to_lines[$yi];
537
		    if ( ($this->ychanged[$yi] = empty($xhash[$line])) )
538
			continue;
539
		    $yhash[$line] = 1;
540
		    $this->yv[] = $line;
541
		    $this->yind[] = $yi;
542
		}
543
		for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
544
		    $line = $from_lines[$xi];
545
		    if ( ($this->xchanged[$xi] = empty($yhash[$line])) )
546
			continue;
547
		    $this->xv[] = $line;
548
		    $this->xind[] = $xi;
549
		}
550
 
551
		// Find the LCS.
552
		$this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv));
553
 
554
		// Merge edits when possible
555
		$this->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged);
556
		$this->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged);
557
 
558
		// Compute the edit operations.
559
		$edits = array();
560
		$xi = $yi = 0;
561
		while ($xi < $n_from || $yi < $n_to) {
562
		    USE_ASSERTS && assert($yi < $n_to || $this->xchanged[$xi]);
563
		    USE_ASSERTS && assert($xi < $n_from || $this->ychanged[$yi]);
564
 
565
		    // Skip matching "snake".
566
		    $copy = array();
567
		    while ( $xi < $n_from && $yi < $n_to
568
			    && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {
569
			$copy[] = $from_lines[$xi++];
570
			++$yi;
571
		    }
572
		    if ($copy)
573
			$edits[] = new _DiffOp_Copy($copy);
574
 
575
		    // Find deletes & adds.
576
		    $delete = array();
577
		    while ($xi < $n_from && $this->xchanged[$xi])
578
			$delete[] = $from_lines[$xi++];
579
 
580
		    $add = array();
581
		    while ($yi < $n_to && $this->ychanged[$yi])
582
			$add[] = $to_lines[$yi++];
583
 
584
		    if ($delete && $add)
585
			$edits[] = new _DiffOp_Change($delete, $add);
586
		    elseif ($delete)
587
			$edits[] = new _DiffOp_Delete($delete);
588
		    elseif ($add)
589
			$edits[] = new _DiffOp_Add($add);
590
		}
591
		return $edits;
592
	    }
593
 
594
 
595
	    /* Divide the Largest Common Subsequence (LCS) of the sequences
596
	     * [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally
597
	     * sized segments.
598
	     *
599
	     * Returns (LCS, PTS).  LCS is the length of the LCS. PTS is an
600
	     * array of NCHUNKS+1 (X, Y) indexes giving the diving points between
601
	     * sub sequences.  The first sub-sequence is contained in [X0, X1),
602
	     * [Y0, Y1), the second in [X1, X2), [Y1, Y2) and so on.  Note
603
	     * that (X0, Y0) == (XOFF, YOFF) and
604
	     * (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM).
605
	     *
606
	     * This function assumes that the first lines of the specified portions
607
	     * of the two files do not match, and likewise that the last lines do not
608
	     * match.  The caller must trim matching lines from the beginning and end
609
	     * of the portions it is going to specify.
610
	     */
611
	    function _diag ($xoff, $xlim, $yoff, $ylim, $nchunks) {
612
		$flip = false;
613
 
614
		if ($xlim - $xoff > $ylim - $yoff) {
615
		    // Things seems faster (I'm not sure I understand why)
616
		    // when the shortest sequence in X.
617
		    $flip = true;
618
		    list ($xoff, $xlim, $yoff, $ylim)
619
			= array( $yoff, $ylim, $xoff, $xlim);
620
		}
621
 
622
		if ($flip)
623
		    for ($i = $ylim - 1; $i >= $yoff; $i--)
624
			$ymatches[$this->xv[$i]][] = $i;
625
		else
626
		    for ($i = $ylim - 1; $i >= $yoff; $i--)
627
			$ymatches[$this->yv[$i]][] = $i;
628
 
629
		$this->lcs = 0;
630
		$this->seq[0]= $yoff - 1;
631
		$this->in_seq = array();
632
		$ymids[0] = array();
633
 
634
		$numer = $xlim - $xoff + $nchunks - 1;
635
		$x = $xoff;
636
		for ($chunk = 0; $chunk < $nchunks; $chunk++) {
637
		    if ($chunk > 0)
638
			for ($i = 0; $i <= $this->lcs; $i++)
639
			    $ymids[$i][$chunk-1] = $this->seq[$i];
640
 
641
		    $x1 = $xoff + (int)(($numer + ($xlim-$xoff)*$chunk) / $nchunks);
642
		    for ( ; $x < $x1; $x++) {
643
			$line = $flip ? $this->yv[$x] : $this->xv[$x];
644
			if (empty($ymatches[$line]))
645
			    continue;
646
			$matches = $ymatches[$line];
647
			reset($matches);
648
			while (list ($junk, $y) = each($matches))
649
			    if (empty($this->in_seq[$y])) {
650
				$k = $this->_lcs_pos($y);
651
				USE_ASSERTS && assert($k > 0);
652
				$ymids[$k] = $ymids[$k-1];
653
				break;
654
			    }
655
			while (list ($junk, $y) = each($matches)) {
656
			    if ($y > $this->seq[$k-1]) {
657
				USE_ASSERTS && assert($y < $this->seq[$k]);
658
				// Optimization: this is a common case:
659
				//  next match is just replacing previous match.
660
				$this->in_seq[$this->seq[$k]] = false;
661
				$this->seq[$k] = $y;
662
				$this->in_seq[$y] = 1;
663
			    }
664
			    else if (empty($this->in_seq[$y])) {
665
				$k = $this->_lcs_pos($y);
666
				USE_ASSERTS && assert($k > 0);
667
				$ymids[$k] = $ymids[$k-1];
668
			    }
669
			}
670
		    }
671
		}
672
 
673
		$seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff);
674
		$ymid = $ymids[$this->lcs];
675
		for ($n = 0; $n < $nchunks - 1; $n++) {
676
		    $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks);
677
		    $y1 = $ymid[$n] + 1;
678
		    $seps[] = $flip ? array($y1, $x1) : array($x1, $y1);
679
		}
680
		$seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim);
681
 
682
		return array($this->lcs, $seps);
683
	    }
684
 
685
	    function _lcs_pos ($ypos) {
686
		$end = $this->lcs;
687
		if ($end == 0 || $ypos > $this->seq[$end]) {
688
		    $this->seq[++$this->lcs] = $ypos;
689
		    $this->in_seq[$ypos] = 1;
690
		    return $this->lcs;
691
		}
692
 
693
		$beg = 1;
694
		while ($beg < $end) {
695
		    $mid = (int)(($beg + $end) / 2);
696
		    if ( $ypos > $this->seq[$mid] )
697
			$beg = $mid + 1;
698
		    else
699
			$end = $mid;
700
		}
701
 
702
		USE_ASSERTS && assert($ypos != $this->seq[$end]);
703
 
704
		$this->in_seq[$this->seq[$end]] = false;
705
		$this->seq[$end] = $ypos;
706
		$this->in_seq[$ypos] = 1;
707
		return $end;
708
	    }
709
 
710
	    /* Find LCS of two sequences.
711
	     *
712
	     * The results are recorded in the vectors $this->{x,y}changed[], by
713
	     * storing a 1 in the element for each line that is an insertion
714
	     * or deletion (ie. is not in the LCS).
715
	     *
716
	     * The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1.
717
	     *
718
	     * Note that XLIM, YLIM are exclusive bounds.
719
	     * All line numbers are origin-0 and discarded lines are not counted.
720
	     */
721
	    function _compareseq ($xoff, $xlim, $yoff, $ylim) {
722
		// Slide down the bottom initial diagonal.
723
		while ($xoff < $xlim && $yoff < $ylim
724
		       && $this->xv[$xoff] == $this->yv[$yoff]) {
725
		    ++$xoff;
726
		    ++$yoff;
727
		}
728
 
729
		// Slide up the top initial diagonal.
730
		while ($xlim > $xoff && $ylim > $yoff
731
		       && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) {
732
		    --$xlim;
733
		    --$ylim;
734
		}
735
 
736
		if ($xoff == $xlim || $yoff == $ylim)
737
		    $lcs = 0;
738
		else {
739
		    // This is ad hoc but seems to work well.
740
		    //$nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5);
741
		    //$nchunks = max(2,min(8,(int)$nchunks));
742
		    $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1;
743
		    list ($lcs, $seps)
744
			= $this->_diag($xoff,$xlim,$yoff, $ylim,$nchunks);
745
		}
746
 
747
		if ($lcs == 0) {
748
		    // X and Y sequences have no common subsequence:
749
		    // mark all changed.
750
		    while ($yoff < $ylim)
751
			$this->ychanged[$this->yind[$yoff++]] = 1;
752
		    while ($xoff < $xlim)
753
			$this->xchanged[$this->xind[$xoff++]] = 1;
754
		}
755
		else {
756
		    // Use the partitions to split this problem into subproblems.
757
		    reset($seps);
758
		    $pt1 = $seps[0];
759
		    while ($pt2 = next($seps)) {
760
			$this->_compareseq ($pt1[0], $pt2[0], $pt1[1], $pt2[1]);
761
			$pt1 = $pt2;
762
		    }
763
		}
764
	    }
765
 
766
	    /* Adjust inserts/deletes of identical lines to join changes
767
	     * as much as possible.
768
	     *
769
	     * We do something when a run of changed lines include a
770
	     * line at one end and has an excluded, identical line at the other.
771
	     * We are free to choose which identical line is included.
772
	     * `compareseq' usually chooses the one at the beginning,
773
	     * but usually it is cleaner to consider the following identical line
774
	     * to be the "change".
775
	     *
776
	     * This is extracted verbatim from analyze.c (GNU diffutils-2.7).
777
	     */
778
	    function _shift_boundaries ($lines, &$changed, $other_changed) {
779
		$i = 0;
780
		$j = 0;
781
 
782
		USE_ASSERTS && assert('sizeof($lines) == sizeof($changed)');
783
		$len = sizeof($lines);
784
		$other_len = sizeof($other_changed);
785
 
786
		while (1) {
787
		    /*
788
		     * Scan forwards to find beginning of another run of changes.
789
		     * Also keep track of the corresponding point in the other file.
790
		     *
791
		     * Throughout this code, $i and $j are adjusted together so that
792
		     * the first $i elements of $changed and the first $j elements
793
		     * of $other_changed both contain the same number of zeros
794
		     * (unchanged lines).
795
		     * Furthermore, $j is always kept so that $j == $other_len or
796
		     * $other_changed[$j] == false.
797
		     */
798
		    while ($j < $other_len && $other_changed[$j])
799
			$j++;
800
 
801
		    while ($i < $len && ! $changed[$i]) {
802
			USE_ASSERTS && assert('$j < $other_len && ! $other_changed[$j]');
803
			$i++; $j++;
804
			while ($j < $other_len && $other_changed[$j])
805
			    $j++;
806
		    }
807
 
808
		    if ($i == $len)
809
			break;
810
 
811
		    $start = $i;
812
 
813
		    // Find the end of this run of changes.
814
		    while (++$i < $len && $changed[$i])
815
			continue;
816
 
817
		    do {
818
			/*
819
			 * Record the length of this run of changes, so that
820
			 * we can later determine whether the run has grown.
821
			 */
822
			$runlength = $i - $start;
823
 
824
			/*
825
			 * Move the changed region back, so long as the
826
			 * previous unchanged line matches the last changed one.
827
			 * This merges with previous changed regions.
828
			 */
829
			while ($start > 0 && $lines[$start - 1] == $lines[$i - 1]) {
830
			    $changed[--$start] = 1;
831
			    $changed[--$i] = false;
832
			    while ($start > 0 && $changed[$start - 1])
833
				$start--;
834
			    USE_ASSERTS && assert('$j > 0');
835
			    while ($other_changed[--$j])
836
				continue;
837
			    USE_ASSERTS && assert('$j >= 0 && !$other_changed[$j]');
838
			}
839
 
840
			/*
841
			 * Set CORRESPONDING to the end of the changed run, at the last
842
			 * point where it corresponds to a changed run in the other file.
843
			 * CORRESPONDING == LEN means no such point has been found.
844
			 */
845
			$corresponding = $j < $other_len ? $i : $len;
846
 
847
			/*
848
			 * Move the changed region forward, so long as the
849
			 * first changed line matches the following unchanged one.
850
			 * This merges with following changed regions.
851
			 * Do this second, so that if there are no merges,
852
			 * the changed region is moved forward as far as possible.
853
			 */
854
			while ($i < $len && $lines[$start] == $lines[$i]) {
855
			    $changed[$start++] = false;
856
			    $changed[$i++] = 1;
857
			    while ($i < $len && $changed[$i])
858
				$i++;
859
 
860
			    USE_ASSERTS && assert('$j < $other_len && ! $other_changed[$j]');
861
			    $j++;
862
			    if ($j < $other_len && $other_changed[$j]) {
863
				$corresponding = $i;
864
				while ($j < $other_len && $other_changed[$j])
865
				    $j++;
866
			    }
867
			}
868
		    } while ($runlength != $i - $start);
869
 
870
		    /*
871
		     * If possible, move the fully-merged run of changes
872
		     * back to a corresponding run in the other file.
873
		     */
874
		    while ($corresponding < $i) {
875
			$changed[--$start] = 1;
876
			$changed[--$i] = 0;
877
			USE_ASSERTS && assert('$j > 0');
878
			while ($other_changed[--$j])
879
			    continue;
880
			USE_ASSERTS && assert('$j >= 0 && !$other_changed[$j]');
881
		    }
882
		}
883
	    }
884
	}
885
 
886
	/**
887
	 * Class representing a 'diff' between two sequences of strings.
888
	 */
889
	class Diff
890
	{
891
	    var $edits;
892
 
893
	    /**
894
	     * Constructor.
895
	     * Computes diff between sequences of strings.
896
	     *
897
	     * @param $from_lines array An array of strings.
898
	     *        (Typically these are lines from a file.)
899
	     * @param $to_lines array An array of strings.
900
	     */
901
	    function Diff($from_lines, $to_lines) {
902
		$eng = new _DiffEngine;
903
		$this->edits = $eng->diff($from_lines, $to_lines);
904
	    }
905
 
906
	}
907
 
908
 
909
 
910
	/**
911
	 * A class to format Diffs
912
	 *
913
	 * This class formats the diff in classic diff format.
914
	 * It is intended that this class be customized via inheritance,
915
	 * to obtain fancier outputs.
916
	 */
917
	class DiffFormatter
918
	{
919
 
920
	    /**
921
	     * Format a diff.
922
	     *
923
	     * @param $diff object A Diff object.
924
	     * @return string The formatted output.
925
	     */
926
	    function format($diff) {
927
 
928
		$xi = $yi = 1;
929
		$block = false;
930
		$context = array();
931
 
932
		$this->_start_diff();
933
 
934
		foreach ($diff->edits as $edit) {
935
		    if ($edit->type == 'copy') {
936
			if (is_array($block)) {
937
			    if (sizeof($edit->orig) <= 0) {
938
				$block[] = $edit;
939
			    }
940
			    else{
941
				$this->_block($x0, + $xi - $x0,
942
					      $y0, + $yi - $y0,
943
					      $block);
944
				$block = false;
945
			    }
946
			}
947
		    }
948
		    else {
949
			if (! is_array($block)) {
950
			    $x0 = $xi;
951
			    $y0 = $yi;
952
			    $block = array();
953
			}
954
			$block[] = $edit;
955
		    }
956
 
957
		    if ($edit->orig)
958
			$xi += sizeof($edit->orig);
959
		    if ($edit->final)
960
			$yi += sizeof($edit->final);
961
		}
962
 
963
		if (is_array($block))
964
		    $this->_block($x0, $xi - $x0,
965
				  $y0, $yi - $y0,
966
				  $block);
967
 
968
		return $this->_end_diff();
969
	    }
970
 
971
	    function _block($xbeg, $xlen, $ybeg, $ylen, &$edits) {
972
		$this->_start_block($this->_block_header($xbeg, $xlen, $ybeg, $ylen));
973
	    }
974
 
975
	    function _start_diff() {
976
		ob_start();
977
	    }
978
 
979
	    function _end_diff() {
980
		$val = ob_get_contents();
981
		ob_end_clean();
982
		return $val;
983
	    }
984
 
985
	    function _block_header($xbeg, $xlen, $ybeg, $ylen) {
986
		if ($xlen > 1)
987
		    $xbeg .= "," . ($xbeg + $xlen - 1);
988
		if ($ylen > 1)
989
		    $ybeg .= "," . ($ybeg + $ylen - 1);
990
 
991
		return $xbeg . ($xlen ? ($ylen ? 'c' : 'd') : 'a') . $ybeg;
992
	    }
993
 
994
	    function _start_block($header) {
995
		echo $header."\n";
996
	    }
997
 
998
	}
999
 
1000
 
1001
?>
1002
</div>
1003
<?php echo $this->Footer(); ?>