← Back to branch summary

~azzar1/unity/add-show-desktop-key

« back to all changes in this revision

Viewing changes to www/php/phpBB3/includes/diff/engine.php

  • Committer: William Grant
  • Date: 2009-02-23 23:47:02 UTC
  • mfrom: (1099.1.211 new-dispatch)
  • Revision ID: grantw@unimelb.edu.au-20090223234702-db4b1llly46ignwo
Merge from lp:~ivle-dev/ivle/new-dispatch.

Pretty much everything changes. Reread the setup docs. Backup your databases.
Every file is now in a different installed location, the configuration system
is rewritten, the dispatch system is rewritten, URLs are different, the
database is different, worksheets and exercises are no longer on the
filesystem, we use a templating engine, jail service protocols are rewritten,
we don't repeat ourselves, we have authorization rewritten, phpBB is gone,
and probably lots of other things that I cannot remember.

This is certainly the biggest commit I have ever made, and hopefully
the largest I ever will.

Show diffs side-by-side

added added

removed removed

Lines of Context:
www/php/phpBB3/includes/diff/engine.php
1
 
<?php
2
 
/**
3
 
*
4
 
* @package diff
5
 
* @version $Id: engine.php,v 1.7 2007/10/05 14:36:33 acydburn Exp $
6
 
* @copyright (c) 2006 phpBB Group
7
 
* @license http://opensource.org/licenses/gpl-license.php GNU Public License
8
 
*
9
 
*/
10
 
 
11
 
/**
12
 
* @ignore
13
 
*/
14
 
if (!defined('IN_PHPBB'))
15
 
{
16
 
        exit;
17
 
}
18
 
 
19
 
/**
20
 
* Code from pear.php.net, Text_Diff-0.2.1 (beta) package
21
 
* http://pear.php.net/package/Text_Diff/
22
 
*
23
 
* Modified by phpBB Group to meet our coding standards
24
 
* and being able to integrate into phpBB
25
 
*
26
 
* Class used internally by Diff to actually compute the diffs.  This class is
27
 
* implemented using native PHP code.
28
 
*
29
 
* The algorithm used here is mostly lifted from the perl module
30
 
* Algorithm::Diff (version 1.06) by Ned Konz, which is available at:
31
 
* http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip
32
 
*
33
 
* More ideas are taken from:
34
 
* http://www.ics.uci.edu/~eppstein/161/960229.html
35
 
*
36
 
* Some ideas (and a bit of code) are taken from analyze.c, of GNU
37
 
* diffutils-2.7, which can be found at:
38
 
* ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
39
 
*
40
 
* Some ideas (subdivision by NCHUNKS > 2, and some optimizations) are from
41
 
* Geoffrey T. Dairiki <dairiki@dairiki.org>. The original PHP version of this
42
 
* code was written by him, and is used/adapted with his permission.
43
 
*
44
 
* @author  Geoffrey T. Dairiki <dairiki@dairiki.org>
45
 
* @package diff
46
 
*
47
 
* @access private
48
 
*/
49
 
class diff_engine
50
 
{
51
 
        function diff(&$from_lines, &$to_lines, $preserve_cr = true)
52
 
        {
53
 
                // Remove empty lines...
54
 
                // If preserve_cr is true, we basically only change \r\n and bare \r to \n to get the same carriage returns for both files
55
 
                // If it is false, we try to only use \n once per line and ommit all empty lines to be able to get a proper data diff
56
 
 
57
 
                if (is_array($from_lines))
58
 
                {
59
 
                        $from_lines = implode("\n", $from_lines);
60
 
                }
61
 
 
62
 
                if (is_array($to_lines))
63
 
                {
64
 
                        $to_lines = implode("\n", $to_lines);
65
 
                }
66
 
 
67
 
                if ($preserve_cr)
68
 
                {
69
 
                        $from_lines = explode("\n", str_replace("\r", "\n", str_replace("\r\n", "\n", $from_lines)));
70
 
                        $to_lines = explode("\n", str_replace("\r", "\n", str_replace("\r\n", "\n", $to_lines)));
71
 
                }
72
 
                else
73
 
                {
74
 
                        $from_lines = explode("\n", preg_replace('#[\n\r]+#', "\n", $from_lines));
75
 
                        $to_lines = explode("\n", preg_replace('#[\n\r]+#', "\n", $to_lines));
76
 
                }
77
 
 
78
 
                $n_from = sizeof($from_lines);
79
 
                $n_to = sizeof($to_lines);
80
 
 
81
 
                $this->xchanged = $this->ychanged = $this->xv = $this->yv = $this->xind = $this->yind = array();
82
 
                unset($this->seq, $this->in_seq, $this->lcs);
83
 
 
84
 
                // Skip leading common lines.
85
 
                for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++)
86
 
                {
87
 
                        if ($from_lines[$skip] !== $to_lines[$skip])
88
 
                        {
89
 
                                break;
90
 
                        }
91
 
                        $this->xchanged[$skip] = $this->ychanged[$skip] = false;
92
 
                }
93
 
 
94
 
                // Skip trailing common lines.
95
 
                $xi = $n_from;
96
 
                $yi = $n_to;
97
 
 
98
 
                for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++)
99
 
                {
100
 
                        if ($from_lines[$xi] !== $to_lines[$yi])
101
 
                        {
102
 
                                break;
103
 
                        }
104
 
                        $this->xchanged[$xi] = $this->ychanged[$yi] = false;
105
 
                }
106
 
 
107
 
                // Ignore lines which do not exist in both files.
108
 
                for ($xi = $skip; $xi < $n_from - $endskip; $xi++)
109
 
                {
110
 
                        $xhash[$from_lines[$xi]] = 1;
111
 
                }
112
 
 
113
 
                for ($yi = $skip; $yi < $n_to - $endskip; $yi++)
114
 
                {
115
 
                        $line = $to_lines[$yi];
116
 
 
117
 
                        if (($this->ychanged[$yi] = empty($xhash[$line])))
118
 
                        {
119
 
                                continue;
120
 
                        }
121
 
                        $yhash[$line] = 1;
122
 
                        $this->yv[] = $line;
123
 
                        $this->yind[] = $yi;
124
 
                }
125
 
 
126
 
                for ($xi = $skip; $xi < $n_from - $endskip; $xi++)
127
 
                {
128
 
                        $line = $from_lines[$xi];
129
 
 
130
 
                        if (($this->xchanged[$xi] = empty($yhash[$line])))
131
 
                        {
132
 
                                continue;
133
 
                        }
134
 
                        $this->xv[] = $line;
135
 
                        $this->xind[] = $xi;
136
 
                }
137
 
 
138
 
                // Find the LCS.
139
 
                $this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv));
140
 
 
141
 
                // Merge edits when possible.
142
 
                $this->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged);
143
 
                $this->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged);
144
 
 
145
 
                // Compute the edit operations.
146
 
                $edits = array();
147
 
                $xi = $yi = 0;
148
 
 
149
 
                while ($xi < $n_from || $yi < $n_to)
150
 
                {
151
 
                        // Skip matching "snake".
152
 
                        $copy = array();
153
 
 
154
 
                        while ($xi < $n_from && $yi < $n_to && !$this->xchanged[$xi] && !$this->ychanged[$yi])
155
 
                        {
156
 
                                $copy[] = $from_lines[$xi++];
157
 
                                $yi++;
158
 
                        }
159
 
 
160
 
                        if ($copy)
161
 
                        {
162
 
                                $edits[] = &new diff_op_copy($copy);
163
 
                        }
164
 
 
165
 
                        // Find deletes & adds.
166
 
                        $delete = array();
167
 
                        while ($xi < $n_from && $this->xchanged[$xi])
168
 
                        {
169
 
                                $delete[] = $from_lines[$xi++];
170
 
                        }
171
 
 
172
 
                        $add = array();
173
 
                        while ($yi < $n_to && $this->ychanged[$yi])
174
 
                        {
175
 
                                $add[] = $to_lines[$yi++];
176
 
                        }
177
 
 
178
 
                        if ($delete && $add)
179
 
                        {
180
 
                                $edits[] = &new diff_op_change($delete, $add);
181
 
                        }
182
 
                        else if ($delete)
183
 
                        {
184
 
                                $edits[] = &new diff_op_delete($delete);
185
 
                        }
186
 
                        else if ($add)
187
 
                        {
188
 
                                $edits[] = &new diff_op_add($add);
189
 
                        }
190
 
                }
191
 
 
192
 
                return $edits;
193
 
        }
194
 
 
195
 
        /**
196
 
        * Divides the Largest Common Subsequence (LCS) of the sequences (XOFF,
197
 
        * XLIM) and (YOFF, YLIM) into NCHUNKS approximately equally sized segments.
198
 
        *
199
 
        * Returns (LCS, PTS).  LCS is the length of the LCS. PTS is an array of
200
 
        * NCHUNKS+1 (X, Y) indexes giving the diving points between sub
201
 
        * sequences.  The first sub-sequence is contained in (X0, X1), (Y0, Y1),
202
 
        * the second in (X1, X2), (Y1, Y2) and so on.  Note that (X0, Y0) ==
203
 
        * (XOFF, YOFF) and (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM).
204
 
        *
205
 
        * This function assumes that the first lines of the specified portions of
206
 
        * the two files do not match, and likewise that the last lines do not
207
 
        * match.  The caller must trim matching lines from the beginning and end
208
 
        * of the portions it is going to specify.
209
 
        */
210
 
        function _diag($xoff, $xlim, $yoff, $ylim, $nchunks)
211
 
        {
212
 
                $flip = false;
213
 
 
214
 
                if ($xlim - $xoff > $ylim - $yoff)
215
 
                {
216
 
                        // Things seems faster (I'm not sure I understand why) when the shortest sequence is in X.
217
 
                        $flip = true;
218
 
                        list($xoff, $xlim, $yoff, $ylim) = array($yoff, $ylim, $xoff, $xlim);
219
 
                }
220
 
 
221
 
                if ($flip)
222
 
                {
223
 
                        for ($i = $ylim - 1; $i >= $yoff; $i--)
224
 
                        {
225
 
                                $ymatches[$this->xv[$i]][] = $i;
226
 
                        }
227
 
                }
228
 
                else
229
 
                {
230
 
                        for ($i = $ylim - 1; $i >= $yoff; $i--)
231
 
                        {
232
 
                                $ymatches[$this->yv[$i]][] = $i;
233
 
                        }
234
 
                }
235
 
 
236
 
                $this->lcs = 0;
237
 
                $this->seq[0]= $yoff - 1;
238
 
                $this->in_seq = array();
239
 
                $ymids[0] = array();
240
 
 
241
 
                $numer = $xlim - $xoff + $nchunks - 1;
242
 
                $x = $xoff;
243
 
 
244
 
                for ($chunk = 0; $chunk < $nchunks; $chunk++)
245
 
                {
246
 
                        if ($chunk > 0)
247
 
                        {
248
 
                                for ($i = 0; $i <= $this->lcs; $i++)
249
 
                                {
250
 
                                        $ymids[$i][$chunk - 1] = $this->seq[$i];
251
 
                                }
252
 
                        }
253
 
 
254
 
                        $x1 = $xoff + (int)(($numer + ($xlim-$xoff)*$chunk) / $nchunks);
255
 
 
256
 
                        for (; $x < $x1; $x++)
257
 
                        {
258
 
                                $line = $flip ? $this->yv[$x] : $this->xv[$x];
259
 
                                if (empty($ymatches[$line]))
260
 
                                {
261
 
                                        continue;
262
 
                                }
263
 
                                $matches = $ymatches[$line];
264
 
 
265
 
                                foreach ($matches as $y)
266
 
                                {
267
 
                                        if (empty($this->in_seq[$y]))
268
 
                                        {
269
 
                                                $k = $this->_lcs_pos($y);
270
 
                                                $ymids[$k] = $ymids[$k - 1];
271
 
                                                break;
272
 
                                        }
273
 
                                }
274
 
 
275
 
                                // no reset() here
276
 
                                while (list($junk, $y) = each($matches))
277
 
                                {
278
 
                                        if ($y > $this->seq[$k - 1])
279
 
                                        {
280
 
                                                // Optimization: this is a common case: next match is just replacing previous match.
281
 
                                                $this->in_seq[$this->seq[$k]] = false;
282
 
                                                $this->seq[$k] = $y;
283
 
                                                $this->in_seq[$y] = 1;
284
 
                                        }
285
 
                                        else if (empty($this->in_seq[$y]))
286
 
                                        {
287
 
                                                $k = $this->_lcs_pos($y);
288
 
                                                $ymids[$k] = $ymids[$k - 1];
289
 
                                        }
290
 
                                }
291
 
                        }
292
 
                }
293
 
 
294
 
                $seps[] = $flip ? array($yoff, $xoff) : array($xoff, $yoff);
295
 
                $ymid = $ymids[$this->lcs];
296
 
 
297
 
                for ($n = 0; $n < $nchunks - 1; $n++)
298
 
                {
299
 
                        $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks);
300
 
                        $y1 = $ymid[$n] + 1;
301
 
                        $seps[] = $flip ? array($y1, $x1) : array($x1, $y1);
302
 
                }
303
 
                $seps[] = $flip ? array($ylim, $xlim) : array($xlim, $ylim);
304
 
 
305
 
                return array($this->lcs, $seps);
306
 
        }
307
 
 
308
 
        function _lcs_pos($ypos)
309
 
        {
310
 
                $end = $this->lcs;
311
 
 
312
 
                if ($end == 0 || $ypos > $this->seq[$end])
313
 
                {
314
 
                        $this->seq[++$this->lcs] = $ypos;
315
 
                        $this->in_seq[$ypos] = 1;
316
 
                        return $this->lcs;
317
 
                }
318
 
 
319
 
                $beg = 1;
320
 
                while ($beg < $end)
321
 
                {
322
 
                        $mid = (int)(($beg + $end) / 2);
323
 
                        if ($ypos > $this->seq[$mid])
324
 
                        {
325
 
                                $beg = $mid + 1;
326
 
                        }
327
 
                        else
328
 
                        {
329
 
                                $end = $mid;
330
 
                        }
331
 
                }
332
 
 
333
 
                $this->in_seq[$this->seq[$end]] = false;
334
 
                $this->seq[$end] = $ypos;
335
 
                $this->in_seq[$ypos] = 1;
336
 
 
337
 
                return $end;
338
 
        }
339
 
 
340
 
        /**
341
 
        * Finds LCS of two sequences.
342
 
        *
343
 
        * The results are recorded in the vectors $this->{x,y}changed[], by
344
 
        * storing a 1 in the element for each line that is an insertion or
345
 
        * deletion (ie. is not in the LCS).
346
 
        *
347
 
        * The subsequence of file 0 is (XOFF, XLIM) and likewise for file 1.
348
 
        *
349
 
        * Note that XLIM, YLIM are exclusive bounds.  All line numbers are
350
 
        * origin-0 and discarded lines are not counted.
351
 
        */
352
 
        function _compareseq($xoff, $xlim, $yoff, $ylim)
353
 
        {
354
 
                // Slide down the bottom initial diagonal.
355
 
                while ($xoff < $xlim && $yoff < $ylim && $this->xv[$xoff] == $this->yv[$yoff])
356
 
                {
357
 
                        ++$xoff;
358
 
                        ++$yoff;
359
 
                }
360
 
 
361
 
                // Slide up the top initial diagonal.
362
 
                while ($xlim > $xoff && $ylim > $yoff && $this->xv[$xlim - 1] == $this->yv[$ylim - 1])
363
 
                {
364
 
                        --$xlim;
365
 
                        --$ylim;
366
 
                }
367
 
 
368
 
                if ($xoff == $xlim || $yoff == $ylim)
369
 
                {
370
 
                        $lcs = 0;
371
 
                }
372
 
                else
373
 
                {
374
 
                        // This is ad hoc but seems to work well.
375
 
                        // $nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5);
376
 
                        // $nchunks = max(2,min(8,(int)$nchunks));
377
 
                        $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1;
378
 
                        list($lcs, $seps) = $this->_diag($xoff, $xlim, $yoff, $ylim, $nchunks);
379
 
                }
380
 
 
381
 
                if ($lcs == 0)
382
 
                {
383
 
                        // X and Y sequences have no common subsequence: mark all changed.
384
 
                        while ($yoff < $ylim)
385
 
                        {
386
 
                                $this->ychanged[$this->yind[$yoff++]] = 1;
387
 
                        }
388
 
 
389
 
                        while ($xoff < $xlim)
390
 
                        {
391
 
                                $this->xchanged[$this->xind[$xoff++]] = 1;
392
 
                        }
393
 
                }
394
 
                else
395
 
                {
396
 
                        // Use the partitions to split this problem into subproblems.
397
 
                        reset($seps);
398
 
                        $pt1 = $seps[0];
399
 
 
400
 
                        while ($pt2 = next($seps))
401
 
                        {
402
 
                                $this->_compareseq($pt1[0], $pt2[0], $pt1[1], $pt2[1]);
403
 
                                $pt1 = $pt2;
404
 
                        }
405
 
                }
406
 
        }
407
 
 
408
 
        /**
409
 
        * Adjusts inserts/deletes of identical lines to join changes as much as possible.
410
 
        *
411
 
        * We do something when a run of changed lines include a line at one end
412
 
        * and has an excluded, identical line at the other.  We are free to
413
 
        * choose which identical line is included. 'compareseq' usually chooses
414
 
        * the one at the beginning, but usually it is cleaner to consider the
415
 
        * following identical line to be the "change".
416
 
        *
417
 
        * This is extracted verbatim from analyze.c (GNU diffutils-2.7).
418
 
        */
419
 
        function _shift_boundaries($lines, &$changed, $other_changed)
420
 
        {
421
 
                $i = 0;
422
 
                $j = 0;
423
 
 
424
 
                $len = sizeof($lines);
425
 
                $other_len = sizeof($other_changed);
426
 
 
427
 
                while (1)
428
 
                {
429
 
                        // Scan forward to find the beginning of another run of
430
 
                        // changes. Also keep track of the corresponding point in the other file.
431
 
                        //
432
 
                        // Throughout this code, $i and $j are adjusted together so that
433
 
                        // the first $i elements of $changed and the first $j elements of
434
 
                        // $other_changed both contain the same number of zeros (unchanged lines).
435
 
                        //
436
 
                        // Furthermore, $j is always kept so that $j == $other_len or $other_changed[$j] == false.
437
 
                        while ($j < $other_len && $other_changed[$j])
438
 
                        {
439
 
                                $j++;
440
 
                        }
441
 
 
442
 
                        while ($i < $len && ! $changed[$i])
443
 
                        {
444
 
                                $i++;
445
 
                                $j++;
446
 
 
447
 
                                while ($j < $other_len && $other_changed[$j])
448
 
                                {
449
 
                                        $j++;
450
 
                                }
451
 
                        }
452
 
 
453
 
                        if ($i == $len)
454
 
                        {
455
 
                                break;
456
 
                        }
457
 
 
458
 
                        $start = $i;
459
 
 
460
 
                        // Find the end of this run of changes.
461
 
                        while (++$i < $len && $changed[$i])
462
 
                        {
463
 
                                continue;
464
 
                        }
465
 
 
466
 
                        do
467
 
                        {
468
 
                                // Record the length of this run of changes, so that we can later determine whether the run has grown.
469
 
                                $runlength = $i - $start;
470
 
 
471
 
                                // Move the changed region back, so long as the previous unchanged line matches the last changed one.
472
 
                                // This merges with previous changed regions.
473
 
                                while ($start > 0 && $lines[$start - 1] == $lines[$i - 1])
474
 
                                {
475
 
                                        $changed[--$start] = 1;
476
 
                                        $changed[--$i] = false;
477
 
 
478
 
                                        while ($start > 0 && $changed[$start - 1])
479
 
                                        {
480
 
                                                $start--;
481
 
                                        }
482
 
 
483
 
                                        while ($other_changed[--$j])
484
 
                                        {
485
 
                                                continue;
486
 
                                        }
487
 
                                }
488
 
 
489
 
                                // Set CORRESPONDING to the end of the changed run, at the last point where it corresponds to a changed run in the
490
 
                                // other file. CORRESPONDING == LEN means no such point has been found.
491
 
                                $corresponding = $j < $other_len ? $i : $len;
492
 
 
493
 
                                // Move the changed region forward, so long as the first changed line matches the following unchanged one.
494
 
                                // This merges with following changed regions.
495
 
                                // Do this second, so that if there are no merges, the changed region is moved forward as far as possible.
496
 
                                while ($i < $len && $lines[$start] == $lines[$i])
497
 
                                {
498
 
                                        $changed[$start++] = false;
499
 
                                        $changed[$i++] = 1;
500
 
 
501
 
                                        while ($i < $len && $changed[$i])
502
 
                                        {
503
 
                                                $i++;
504
 
                                        }
505
 
 
506
 
                                        $j++;
507
 
                                        if ($j < $other_len && $other_changed[$j])
508
 
                                        {
509
 
                                                $corresponding = $i;
510
 
                                                while ($j < $other_len && $other_changed[$j])
511
 
                                                {
512
 
                                                        $j++;
513
 
                                                }
514
 
                                        }
515
 
                                }
516
 
                        }
517
 
                        while ($runlength != $i - $start);
518
 
 
519
 
                        // If possible, move the fully-merged run of changes back to a corresponding run in the other file.
520
 
                        while ($corresponding < $i)
521
 
                        {
522
 
                                $changed[--$start] = 1;
523
 
                                $changed[--$i] = 0;
524
 
 
525
 
                                while ($other_changed[--$j])
526
 
                                {
527
 
                                        continue;
528
 
                                }
529
 
                        }
530
 
                }
531
 
        }
532
 
}
533
 
 
534
 
?>
 
 
b'\\ No newline at end of file'