Passed
Pull Request — master (#9)
by Michael
03:24
created

Text_Diff_Op::norig()   A

Complexity

Conditions 2
Paths 2

Size

Total Lines 3
Code Lines 1

Duplication

Lines 0
Ratio 0 %

Importance

Changes 0
Metric Value
eloc 1
dl 0
loc 3
rs 10
c 0
b 0
f 0
cc 2
nc 2
nop 0
1
<?php
2
3
namespace XoopsModules\Mylinks;
4
5
/**
6
 * Text_Diff
7
 *
8
 * General API for generating and formatting diffs - the differences between
9
 * two sequences of strings.
10
 *
11
 * The PHP diff code used in this package was originally written by Geoffrey
12
 * T. Dairiki and is used with his permission.
13
 *
14
 * $Horde: framework/Text_Diff/Diff.php,v 1.13 2005/05/26 20:26:06 selsky Exp $
15
 *
16
 * @package Text_Diff
17
 * @author  Geoffrey T. Dairiki <[email protected]>
18
 */
19
class Text_Diff
20
{
21
    /**
22
     * Array of changes.
23
     *
24
     * @var array
25
     */
26
    public $_edits;
27
28
    /**
29
     * Computes diffs between sequences of strings.
30
     *
31
     * @param array $from_lines An array of strings.  Typically these are
32
     *                          lines from a file.
33
     * @param array $to_lines   An array of strings.
34
     */
35
    public function __construct($from_lines, $to_lines)
36
    {
37
        array_walk($from_lines, [$this, '_trimNewlines']);
38
        array_walk($to_lines, [$this, '_trimNewlines']);
39
40
        if (extension_loaded('xdiff')) {
41
            $engine = new Text_Diff_Engine_xdiff();
42
        } else {
43
            $engine = new Text_Diff_Engine_native();
44
        }
45
46
        $this->_edits = $engine->diff($from_lines, $to_lines);
47
    }
48
49
    /**
50
     * Returns the array of differences.
51
     */
52
    public function getDiff()
53
    {
54
        return $this->_edits;
55
    }
56
57
    /**
58
     * Computes a reversed diff.
59
     *
60
     * Example:
61
     * <code>
62
     * $diff = new Text_Diff($lines1, $lines2);
63
     * $rev = $diff->reverse();
64
     * </code>
65
     *
66
     * @return Text_Diff A Diff object representing the inverse of the
67
     *                   original diff.  Note that we purposely don't return a
68
     *                   reference here, since this essentially is a clone()
69
     *                   method.
70
     */
71
    public function reverse()
72
    {
73
        if (version_compare(zend_version(), '2', '>')) {
74
            $rev = clone $this;
75
        } else {
76
            $rev = $this;
77
        }
78
        $rev->_edits = [];
79
        foreach ($this->_edits as $edit) {
80
            $rev->_edits[] = $edit->reverse();
81
        }
82
83
        return $rev;
84
    }
85
86
    /**
87
     * Checks for an empty diff.
88
     *
89
     * @return bool True if two sequences were identical.
90
     */
91
    public function isEmpty()
92
    {
93
        foreach ($this->_edits as $edit) {
94
            if (!is_a($edit, 'Text_Diff_Op_copy')) {
95
                return false;
96
            }
97
        }
98
99
        return true;
100
    }
101
102
    /**
103
     * Computes the length of the Longest Common Subsequence (LCS).
104
     *
105
     * This is mostly for diagnostic purposes.
106
     *
107
     * @return int The length of the LCS.
108
     */
109
    public function lcs()
110
    {
111
        $lcs = 0;
112
        foreach ($this->_edits as $edit) {
113
            if (is_a($edit, 'Text_Diff_Op_copy')) {
114
                $lcs += count($edit->orig);
115
            }
116
        }
117
118
        return $lcs;
119
    }
120
121
    /**
122
     * Gets the original set of lines.
123
     *
124
     * This reconstructs the $from_lines parameter passed to the constructor.
125
     *
126
     * @return array The original sequence of strings.
127
     */
128
    public function getOriginal()
129
    {
130
        $lines = [];
131
        foreach ($this->_edits as $edit) {
132
            if ($edit->orig) {
133
                array_splice($lines, count($lines), 0, $edit->orig);
134
            }
135
        }
136
137
        return $lines;
138
    }
139
140
    /**
141
     * Gets the final set of lines.
142
     *
143
     * This reconstructs the $to_lines parameter passed to the constructor.
144
     *
145
     * @return array The sequence of strings.
146
     */
147
    public function getFinal()
148
    {
149
        $lines = [];
150
        foreach ($this->_edits as $edit) {
151
            if ($edit->final) {
152
                array_splice($lines, count($lines), 0, $edit->final);
153
            }
154
        }
155
156
        return $lines;
157
    }
158
159
    /**
160
     * Removes trailing newlines from a line of text. This is meant to be used
161
     * with array_walk().
162
     *
163
     * @param string $line The line to trim.
164
     * @param int    $key  The index of the line in the array. Not used.
165
     */
166
    public function _trimNewlines(&$line, $key)
0 ignored issues
show
Unused Code introduced by
The parameter $key is not used and could be removed. ( Ignorable by Annotation )

If this is a false-positive, you can also ignore this issue in your code via the ignore-unused  annotation

166
    public function _trimNewlines(&$line, /** @scrutinizer ignore-unused */ $key)

This check looks for parameters that have been defined for a function or method, but which are not used in the method body.

Loading history...
167
    {
168
        $line = str_replace(["\n", "\r"], '', $line);
169
    }
170
171
    /**
172
     * Checks a diff for validity.
173
     *
174
     * This is here only for debugging purposes.
175
     * @param $from_lines
176
     * @param $to_lines
177
     * @return bool
178
     */
179
    public function _check($from_lines, $to_lines)
180
    {
181
        if (serialize($from_lines) != serialize($this->getOriginal())) {
182
            trigger_error("Reconstructed original doesn't match", E_USER_ERROR);
183
        }
184
        if (serialize($to_lines) != serialize($this->getFinal())) {
185
            trigger_error("Reconstructed final doesn't match", E_USER_ERROR);
186
        }
187
188
        $rev = $this->reverse();
189
        if (serialize($to_lines) != serialize($rev->getOriginal())) {
190
            trigger_error("Reversed original doesn't match", E_USER_ERROR);
191
        }
192
        if (serialize($from_lines) != serialize($rev->getFinal())) {
193
            trigger_error("Reversed final doesn't match", E_USER_ERROR);
194
        }
195
196
        $prevtype = null;
197
        foreach ($this->_edits as $edit) {
198
            if ($prevtype == get_class($edit)) {
199
                trigger_error('Edit sequence is non-optimal', E_USER_ERROR);
200
            }
201
            $prevtype = get_class($edit);
202
        }
203
204
        return true;
205
    }
206
}
207
208
/**
209
 * $Horde: framework/Text_Diff/Diff.php,v 1.13 2005/05/26 20:26:06 selsky Exp $
210
 *
211
 * @package Text_Diff
212
 * @author  Geoffrey T. Dairiki <[email protected]>
213
 */
214
class Text_MappedDiff extends Text_Diff
215
{
216
    /**
217
     * Computes a diff between sequences of strings.
218
     *
219
     * This can be used to compute things like case-insensitve diffs, or diffs
220
     * which ignore changes in white-space.
221
     *
222
     * @param array $from_lines        An array of strings.
223
     * @param array $to_lines          An array of strings.
224
     * @param array $mapped_from_lines This array should have the same size
225
     *                                 number of elements as $from_lines.  The
226
     *                                 elements in $mapped_from_lines and
227
     *                                 $mapped_to_lines are what is actually
228
     *                                 compared when computing the diff.
229
     * @param array $mapped_to_lines   This array should have the same number
230
     *                                 of elements as $to_lines.
231
     */
232
    public function __construct($from_lines, $to_lines, $mapped_from_lines, $mapped_to_lines)
233
    {
234
        assert(count($from_lines) == count($mapped_from_lines));
235
        assert(count($to_lines) == count($mapped_to_lines));
236
237
        parent::__construct($mapped_from_lines, $mapped_to_lines);
238
239
        $xi = $yi = 0;
240
        for ($i = 0, $iMax = count($this->_edits); $i < $iMax; ++$i) {
241
            $orig = &$this->_edits[$i]->orig;
242
            if (is_array($orig)) {
243
                $orig = array_slice($from_lines, $xi, count($orig));
244
                $xi   += count($orig);
245
            }
246
247
            $final = &$this->_edits[$i]->final;
248
            if (is_array($final)) {
249
                $final = array_slice($to_lines, $yi, count($final));
250
                $yi    += count($final);
251
            }
252
        }
253
    }
254
}
255
256
/**
257
 * Class used internally by Diff to actually compute the diffs.  This class
258
 * uses the xdiff PECL package (http://pecl.php.net/package/xdiff) to compute
259
 * the differences between the two input arrays.
260
 *
261
 * @author  Jon Parise <[email protected]>
262
 * @package Text_Diff
263
 *
264
 * @access  private
265
 */
266
class Text_Diff_Engine_xdiff
267
{
268
    /**
269
     * @param $from_lines
270
     * @param $to_lines
271
     * @return array
272
     */
273
    public function diff($from_lines, $to_lines)
274
    {
275
        /* Convert the two input arrays into strings for xdiff processing. */
276
        $from_string = implode("\n", $from_lines);
277
        $to_string   = implode("\n", $to_lines);
278
279
        /* Diff the two strings and convert the result to an array. */
280
        $diff = xdiff_string_diff($from_string, $to_string, count($to_lines));
0 ignored issues
show
Bug introduced by
The function xdiff_string_diff was not found. Maybe you did not declare it correctly or list all dependencies? ( Ignorable by Annotation )

If this is a false-positive, you can also ignore this issue in your code via the ignore-call  annotation

280
        $diff = /** @scrutinizer ignore-call */ xdiff_string_diff($from_string, $to_string, count($to_lines));
Loading history...
281
        $diff = explode("\n", $diff);
282
283
        /* Walk through the diff one line at a time.  We build the $edits
284
         * array of diff operations by reading the first character of the
285
         * xdiff output (which is in the "unified diff" format).
286
         *
287
         * Note that we don't have enough information to detect "changed"
288
         * lines using this approach, so we can't add Text_Diff_Op_changed
289
         * instances to the $edits array.  The result is still perfectly
290
         * valid, albeit a little less descriptive and efficient. */
291
        $edits = [];
292
        foreach ($diff as $line) {
293
            switch ($line[0]) {
294
                case ' ':
295
                    $edits[] = new Text_Diff_Op_copy([mb_substr($line, 1)]);
296
                    break;
297
                case '+':
298
                    $edits[] = new Text_Diff_Op_add([mb_substr($line, 1)]);
299
                    break;
300
                case '-':
301
                    $edits[] = new Text_Diff_Op_delete([mb_substr($line, 1)]);
302
                    break;
303
            }
304
        }
305
306
        return $edits;
307
    }
308
}
309
310
/**
311
 * Class used internally by Diff to actually compute the diffs.  This class is
312
 * implemented using native PHP code.
313
 *
314
 * The algorithm used here is mostly lifted from the perl module
315
 * Algorithm::Diff (version 1.06) by Ned Konz, which is available at:
316
 * http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip
317
 *
318
 * More ideas are taken from:
319
 * http://www.ics.uci.edu/~eppstein/161/960229.html
320
 *
321
 * Some ideas (and a bit of code) are taken from analyze.c, of GNU
322
 * diffutils-2.7, which can be found at:
323
 * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
324
 *
325
 * Some ideas (subdivision by NCHUNKS > 2, and some optimizations) are from
326
 * Geoffrey T. Dairiki <[email protected]>. The original PHP version of this
327
 * code was written by him, and is used/adapted with his permission.
328
 *
329
 * @author  Geoffrey T. Dairiki <[email protected]>
330
 * @package Text_Diff
331
 *
332
 * @access  private
333
 */
334
class Text_Diff_Engine_native
335
{
336
    /**
337
     * @param $from_lines
338
     * @param $to_lines
339
     * @return array
340
     */
341
    public function diff($from_lines, $to_lines)
342
    {
343
        $n_from = count($from_lines);
344
        $n_to   = count($to_lines);
345
346
        $this->xchanged = $this->ychanged = [];
0 ignored issues
show
Bug Best Practice introduced by
The property xchanged does not exist. Although not strictly required by PHP, it is generally a best practice to declare properties explicitly.
Loading history...
Bug Best Practice introduced by
The property ychanged does not exist. Although not strictly required by PHP, it is generally a best practice to declare properties explicitly.
Loading history...
347
        $this->xv       = $this->yv = [];
0 ignored issues
show
Bug Best Practice introduced by
The property xv does not exist. Although not strictly required by PHP, it is generally a best practice to declare properties explicitly.
Loading history...
Bug Best Practice introduced by
The property yv does not exist. Although not strictly required by PHP, it is generally a best practice to declare properties explicitly.
Loading history...
348
        $this->xind     = $this->yind = [];
0 ignored issues
show
Bug Best Practice introduced by
The property xind does not exist. Although not strictly required by PHP, it is generally a best practice to declare properties explicitly.
Loading history...
Bug Best Practice introduced by
The property yind does not exist. Although not strictly required by PHP, it is generally a best practice to declare properties explicitly.
Loading history...
349
        unset($this->seq, $this->in_seq, $this->lcs);
350
351
        // Skip leading common lines.
352
        for ($skip = 0; $skip < $n_from && $skip < $n_to; ++$skip) {
353
            if ($from_lines[$skip] != $to_lines[$skip]) {
354
                break;
355
            }
356
            $this->xchanged[$skip] = $this->ychanged[$skip] = false;
357
        }
358
359
        // Skip trailing common lines.
360
        $xi = $n_from;
361
        $yi = $n_to;
362
        for ($endskip = 0; --$xi > $skip && --$yi > $skip; ++$endskip) {
363
            if ($from_lines[$xi] != $to_lines[$yi]) {
364
                break;
365
            }
366
            $this->xchanged[$xi] = $this->ychanged[$yi] = false;
367
        }
368
369
        // Ignore lines which do not exist in both files.
370
        for ($xi = $skip; $xi < $n_from - $endskip; ++$xi) {
371
            $xhash[$from_lines[$xi]] = 1;
372
        }
373
        for ($yi = $skip; $yi < $n_to - $endskip; ++$yi) {
374
            $line                = $to_lines[$yi];
375
            $this->ychanged[$yi] = empty($xhash[$line]);
376
            if ($this->ychanged[$yi]) {
377
                continue;
378
            }
379
            $yhash[$line] = 1;
380
            $this->yv[]   = $line;
381
            $this->yind[] = $yi;
382
        }
383
        for ($xi = $skip; $xi < $n_from - $endskip; ++$xi) {
384
            $line                = $from_lines[$xi];
385
            $this->xchanged[$xi] = empty($yhash[$line]);
386
            if ($this->xchanged[$xi]) {
387
                continue;
388
            }
389
            $this->xv[]   = $line;
390
            $this->xind[] = $xi;
391
        }
392
393
        // Find the LCS.
394
        $this->_compareseq(0, count($this->xv), 0, count($this->yv));
395
396
        // Merge edits when possible.
397
        $this->_shiftBoundaries($from_lines, $this->xchanged, $this->ychanged);
398
        $this->_shiftBoundaries($to_lines, $this->ychanged, $this->xchanged);
399
400
        // Compute the edit operations.
401
        $edits = [];
402
        $xi    = $yi = 0;
403
        while ($xi < $n_from || $yi < $n_to) {
404
            assert($yi < $n_to || $this->xchanged[$xi]);
405
            assert($xi < $n_from || $this->ychanged[$yi]);
406
407
            // Skip matching "snake".
408
            $copy = [];
409
            while ($xi < $n_from && $yi < $n_to && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {
410
                $copy[] = $from_lines[$xi++];
411
                ++$yi;
412
            }
413
            if ($copy) {
414
                $edits[] = new Text_Diff_Op_copy($copy);
415
            }
416
417
            // Find deletes & adds.
418
            $delete = [];
419
            while ($xi < $n_from && $this->xchanged[$xi]) {
420
                $delete[] = $from_lines[$xi++];
421
            }
422
423
            $add = [];
424
            while ($yi < $n_to && $this->ychanged[$yi]) {
425
                $add[] = $to_lines[$yi++];
426
            }
427
428
            if ($delete && $add) {
429
                $edits[] = new Text_Diff_Op_change($delete, $add);
430
            } elseif ($delete) {
431
                $edits[] = new Text_Diff_Op_delete($delete);
432
            } elseif ($add) {
433
                $edits[] = new Text_Diff_Op_add($add);
434
            }
435
        }
436
437
        return $edits;
438
    }
439
440
    /**
441
     * Divides the Largest Common Subsequence (LCS) of the sequences (XOFF,
442
     * XLIM) and (YOFF, YLIM) into NCHUNKS approximately equally sized
443
     * segments.
444
     *
445
     * Returns (LCS, PTS).  LCS is the length of the LCS. PTS is an array of
446
     * NCHUNKS+1 (X, Y) indexes giving the diving points between sub
447
     * sequences.  The first sub-sequence is contained in (X0, X1), (Y0, Y1),
448
     * the second in (X1, X2), (Y1, Y2) and so on.  Note that (X0, Y0) ==
449
     * (XOFF, YOFF) and (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM).
450
     *
451
     * This function assumes that the first lines of the specified portions of
452
     * the two files do not match, and likewise that the last lines do not
453
     * match.  The caller must trim matching lines from the beginning and end
454
     * of the portions it is going to specify.
455
     * @param $xoff
456
     * @param $xlim
457
     * @param $yoff
458
     * @param $ylim
459
     * @param $nchunks
460
     * @return array
461
     */
462
    public function _diag($xoff, $xlim, $yoff, $ylim, $nchunks)
463
    {
464
        $flip = false;
465
466
        if ($xlim - $xoff > $ylim - $yoff) {
467
            /* Things seems faster (I'm not sure I understand why) when the
468
             * shortest sequence is in X. */
469
            $flip = true;
470
            list($xoff, $xlim, $yoff, $ylim) = [$yoff, $ylim, $xoff, $xlim];
471
        }
472
473
        if ($flip) {
474
            for ($i = $ylim - 1; $i >= $yoff; $i--) {
475
                $ymatches[$this->xv[$i]][] = $i;
476
            }
477
        } else {
478
            for ($i = $ylim - 1; $i >= $yoff; $i--) {
479
                $ymatches[$this->yv[$i]][] = $i;
480
            }
481
        }
482
483
        $this->lcs    = 0;
0 ignored issues
show
Bug Best Practice introduced by
The property lcs does not exist. Although not strictly required by PHP, it is generally a best practice to declare properties explicitly.
Loading history...
484
        $this->seq[0] = $yoff - 1;
0 ignored issues
show
Bug Best Practice introduced by
The property seq does not exist. Although not strictly required by PHP, it is generally a best practice to declare properties explicitly.
Loading history...
485
        $this->in_seq = [];
0 ignored issues
show
Bug Best Practice introduced by
The property in_seq does not exist. Although not strictly required by PHP, it is generally a best practice to declare properties explicitly.
Loading history...
486
        $ymids[0]     = [];
0 ignored issues
show
Comprehensibility Best Practice introduced by
$ymids was never initialized. Although not strictly required by PHP, it is generally a good practice to add $ymids = array(); before regardless.
Loading history...
487
488
        $numer = $xlim - $xoff + $nchunks - 1;
489
        $x     = $xoff;
490
        for ($chunk = 0; $chunk < $nchunks; ++$chunk) {
491
            if ($chunk > 0) {
492
                for ($i = 0; $i <= $this->lcs; ++$i) {
493
                    $ymids[$i][$chunk - 1] = $this->seq[$i];
494
                }
495
            }
496
497
            $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $chunk) / $nchunks);
498
            for (; $x < $x1; ++$x) {
499
                $line = $flip ? $this->yv[$x] : $this->xv[$x];
500
                if (empty($ymatches[$line])) {
501
                    continue;
502
                }
503
                $matches = $ymatches[$line];
504
                foreach ($matches as $y) {
505
                    if (empty($this->in_seq[$y])) {
506
                        $k = $this->_lcsPos($y);
507
                        assert($k > 0);
508
                        $ymids[$k] = $ymids[$k - 1];
509
                        break;
510
                    }
511
                }
512
513
                //                while (list($junk, $y) = each($matches)) {
514
                foreach ($matches as $junk => $y) {
515
                    if ($y > $this->seq[$k - 1]) {
0 ignored issues
show
Comprehensibility Best Practice introduced by
The variable $k does not seem to be defined for all execution paths leading up to this point.
Loading history...
516
                        assert($y < $this->seq[$k]);
517
                        /* Optimization: this is a common case: next match is
518
                         * just replacing previous match. */
519
                        $this->in_seq[$this->seq[$k]] = false;
520
                        $this->seq[$k]                = $y;
521
                        $this->in_seq[$y]             = 1;
522
                    } elseif (empty($this->in_seq[$y])) {
523
                        $k = $this->_lcsPos($y);
524
                        assert($k > 0);
525
                        $ymids[$k] = $ymids[$k - 1];
526
                    }
527
                }
528
            }
529
        }
530
531
        $seps[] = $flip ? [$yoff, $xoff] : [$xoff, $yoff];
0 ignored issues
show
Comprehensibility Best Practice introduced by
$seps was never initialized. Although not strictly required by PHP, it is generally a good practice to add $seps = array(); before regardless.
Loading history...
532
        $ymid   = $ymids[$this->lcs];
533
        for ($n = 0; $n < $nchunks - 1; ++$n) {
534
            $x1     = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks);
535
            $y1     = $ymid[$n] + 1;
536
            $seps[] = $flip ? [$y1, $x1] : [$x1, $y1];
537
        }
538
539
        $seps[] = $flip ? [$ylim, $xlim] : [$xlim, $ylim];
540
541
        return [$this->lcs, $seps];
542
    }
543
544
    /**
545
     * @param $ypos
546
     * @return int
547
     */
548
    public function _lcsPos($ypos)
549
    {
550
        $end = $this->lcs;
551
        if (0 == $end || $ypos > $this->seq[$end]) {
552
            $this->seq[++$this->lcs] = $ypos;
0 ignored issues
show
Bug Best Practice introduced by
The property seq does not exist. Although not strictly required by PHP, it is generally a best practice to declare properties explicitly.
Loading history...
553
            $this->in_seq[$ypos]     = 1;
0 ignored issues
show
Bug Best Practice introduced by
The property in_seq does not exist. Although not strictly required by PHP, it is generally a best practice to declare properties explicitly.
Loading history...
554
555
            return $this->lcs;
556
        }
557
558
        $beg = 1;
559
        while ($beg < $end) {
560
            $mid = (int)(($beg + $end) / 2);
561
            if ($ypos > $this->seq[$mid]) {
562
                $beg = $mid + 1;
563
            } else {
564
                $end = $mid;
565
            }
566
        }
567
568
        assert($ypos != $this->seq[$end]);
569
570
        $this->in_seq[$this->seq[$end]] = false;
571
        $this->seq[$end]                = $ypos;
572
        $this->in_seq[$ypos]            = 1;
573
574
        return $end;
575
    }
576
577
    /**
578
     * Finds LCS of two sequences.
579
     *
580
     * The results are recorded in the vectors $this->{x,y}changed[], by
581
     * storing a 1 in the element for each line that is an insertion or
582
     * deletion (ie. is not in the LCS).
583
     *
584
     * The subsequence of file 0 is (XOFF, XLIM) and likewise for file 1.
585
     *
586
     * Note that XLIM, YLIM are exclusive bounds.  All line numbers are
587
     * origin-0 and discarded lines are not counted.
588
     * @param $xoff
589
     * @param $xlim
590
     * @param $yoff
591
     * @param $ylim
592
     */
593
    public function _compareseq($xoff, $xlim, $yoff, $ylim)
594
    {
595
        /* Slide down the bottom initial diagonal. */
596
        while ($xoff < $xlim && $yoff < $ylim && $this->xv[$xoff] == $this->yv[$yoff]) {
597
            ++$xoff;
598
            ++$yoff;
599
        }
600
601
        /* Slide up the top initial diagonal. */
602
        while ($xlim > $xoff && $ylim > $yoff && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) {
603
            --$xlim;
604
            --$ylim;
605
        }
606
607
        if ($xoff == $xlim || $yoff == $ylim) {
608
            $lcs = 0;
609
        } else {
610
            /* This is ad hoc but seems to work well.  $nchunks =
611
             * sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5); $nchunks =
612
             * max(2,min(8,(int) $nchunks)); */
613
            $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1;
614
            list($lcs, $seps) = $this->_diag($xoff, $xlim, $yoff, $ylim, $nchunks);
615
        }
616
617
        if (0 == $lcs) {
618
            /* X and Y sequences have no common subsequence: mark all
619
             * changed. */
620
            while ($yoff < $ylim) {
621
                $this->ychanged[$this->yind[$yoff++]] = 1;
0 ignored issues
show
Bug Best Practice introduced by
The property ychanged does not exist. Although not strictly required by PHP, it is generally a best practice to declare properties explicitly.
Loading history...
622
            }
623
            while ($xoff < $xlim) {
624
                $this->xchanged[$this->xind[$xoff++]] = 1;
0 ignored issues
show
Bug Best Practice introduced by
The property xchanged does not exist. Although not strictly required by PHP, it is generally a best practice to declare properties explicitly.
Loading history...
625
            }
626
        } else {
627
            /* Use the partitions to split this problem into subproblems. */
628
            reset($seps);
629
            $pt1 = $seps[0];
630
            while ($pt2 = next($seps)) {
631
                $this->_compareseq($pt1[0], $pt2[0], $pt1[1], $pt2[1]);
632
                $pt1 = $pt2;
633
            }
634
        }
635
    }
636
637
    /**
638
     * Adjusts inserts/deletes of identical lines to join changes as much as
639
     * possible.
640
     *
641
     * We do something when a run of changed lines include a line at one end
642
     * and has an excluded, identical line at the other.  We are free to
643
     * choose which identical line is included.  `compareseq' usually chooses
644
     * the one at the beginning, but usually it is cleaner to consider the
645
     * following identical line to be the "change".
646
     *
647
     * This is extracted verbatim from analyze.c (GNU diffutils-2.7).
648
     * @param $lines
649
     * @param $changed
650
     * @param $other_changed
651
     */
652
    public function _shiftBoundaries($lines, &$changed, $other_changed)
653
    {
654
        $i = 0;
655
        $j = 0;
656
657
        assert(count($lines) == count($changed));
658
        $len       = count($lines);
659
        $other_len = count($other_changed);
660
661
        while (1) {
662
            /* Scan forward to find the beginning of another run of
663
             * changes. Also keep track of the corresponding point in the
664
             * other file.
665
             *
666
             * Throughout this code, $i and $j are adjusted together so that
667
             * the first $i elements of $changed and the first $j elements of
668
             * $other_changed both contain the same number of zeros (unchanged
669
             * lines).
670
             *
671
             * Furthermore, $j is always kept so that $j == $other_len or
672
             * $other_changed[$j] === false. */
673
            while ($j < $other_len && $other_changed[$j]) {
674
                ++$j;
675
            }
676
677
            while ($i < $len && !$changed[$i]) {
678
                assert($j < $other_len && !$other_changed[$j]);
679
                ++$i;
680
                ++$j;
681
                while ($j < $other_len && $other_changed[$j]) {
682
                    ++$j;
683
                }
684
            }
685
686
            if ($i == $len) {
687
                break;
688
            }
689
690
            $start = $i;
691
692
            /* Find the end of this run of changes. */
693
            while (++$i < $len && $changed[$i]) {
694
                continue;
695
            }
696
697
            do {
698
                /* Record the length of this run of changes, so that we can
699
                 * later determine whether the run has grown. */
700
                $runlength = $i - $start;
701
702
                /* Move the changed region back, so long as the previous
703
                 * unchanged line matches the last changed one.  This merges
704
                 * with previous changed regions. */
705
                while ($start > 0 && $lines[$start - 1] == $lines[$i - 1]) {
706
                    $changed[--$start] = 1;
707
                    $changed[--$i]     = false;
708
                    while ($start > 0 && $changed[$start - 1]) {
709
                        $start--;
710
                    }
711
                    assert($j > 0);
712
                    while ($other_changed[--$j]) {
713
                        continue;
714
                    }
715
                    assert($j >= 0 && !$other_changed[$j]);
716
                }
717
718
                /* Set CORRESPONDING to the end of the changed run, at the
719
                 * last point where it corresponds to a changed run in the
720
                 * other file. CORRESPONDING == LEN means no such point has
721
                 * been found. */
722
                $corresponding = $j < $other_len ? $i : $len;
723
724
                /* Move the changed region forward, so long as the first
725
                 * changed line matches the following unchanged one.  This
726
                 * merges with following changed regions.  Do this second, so
727
                 * that if there are no merges, the changed region is moved
728
                 * forward as far as possible. */
729
                while ($i < $len && $lines[$start] == $lines[$i]) {
730
                    $changed[$start++] = false;
731
                    $changed[$i++]     = 1;
732
                    while ($i < $len && $changed[$i]) {
733
                        ++$i;
734
                    }
735
736
                    assert($j < $other_len && !$other_changed[$j]);
737
                    ++$j;
738
                    if ($j < $other_len && $other_changed[$j]) {
739
                        $corresponding = $i;
740
                        while ($j < $other_len && $other_changed[$j]) {
741
                            ++$j;
742
                        }
743
                    }
744
                }
745
            } while ($runlength != $i - $start);
746
747
            /* If possible, move the fully-merged run of changes back to a
748
             * corresponding run in the other file. */
749
            while ($corresponding < $i) {
750
                $changed[--$start] = 1;
751
                $changed[--$i]     = 0;
752
                assert($j > 0);
753
                while ($other_changed[--$j]) {
754
                    continue;
755
                }
756
                assert($j >= 0 && !$other_changed[$j]);
757
            }
758
        }
759
    }
760
}
761
762
/**
763
 * @package Text_Diff
764
 * @author  Geoffrey T. Dairiki <[email protected]>
765
 *
766
 * @access  private
767
 */
768
class Text_Diff_Op
769
{
770
    public $orig;
771
    public $final;
772
773
    public function reverse()
774
    {
775
        trigger_error('Abstract method', E_USER_ERROR);
776
    }
777
778
    /**
779
     * @return int|void
780
     */
781
    public function norig()
782
    {
783
        return $this->orig ? count($this->orig) : 0;
784
    }
785
786
    /**
787
     * @return int|void
788
     */
789
    public function nfinal()
790
    {
791
        return $this->final ? count($this->final) : 0;
792
    }
793
}
794
795
/**
796
 * @package Text_Diff
797
 * @author  Geoffrey T. Dairiki <[email protected]>
798
 *
799
 * @access  private
800
 */
801
class Text_Diff_Op_copy extends Text_Diff_Op
802
{
803
    /**
804
     * Text_Diff_Op_copy constructor.
805
     * @param      $orig
806
     * @param bool $final
807
     */
808
    public function __construct($orig, $final = false)
809
    {
810
        if (!is_array($final)) {
0 ignored issues
show
introduced by
The condition is_array($final) is always false.
Loading history...
811
            $final = $orig;
812
        }
813
        $this->orig  = $orig;
814
        $this->final = $final;
815
    }
816
817
    /**
818
     * @return Text_Diff_Op_copy
819
     */
820
    public function reverse()
821
    {
822
        return $reverse = new self($this->final, $this->orig);
0 ignored issues
show
Unused Code introduced by
The assignment to $reverse is dead and can be removed.
Loading history...
823
    }
824
}
825
826
/**
827
 * @package Text_Diff
828
 * @author  Geoffrey T. Dairiki <[email protected]>
829
 *
830
 * @access  private
831
 */
832
class Text_Diff_Op_delete extends Text_Diff_Op
833
{
834
    /**
835
     * Text_Diff_Op_delete constructor.
836
     * @param $lines
837
     */
838
    public function __construct($lines)
839
    {
840
        $this->orig  = $lines;
841
        $this->final = false;
842
    }
843
844
    /**
845
     * @return Text_Diff_Op_add
846
     */
847
    public function reverse()
848
    {
849
        return $reverse = new Text_Diff_Op_add($this->orig);
0 ignored issues
show
Unused Code introduced by
The assignment to $reverse is dead and can be removed.
Loading history...
850
    }
851
}
852
853
/**
854
 * @package Text_Diff
855
 * @author  Geoffrey T. Dairiki <[email protected]>
856
 *
857
 * @access  private
858
 */
859
class Text_Diff_Op_add extends Text_Diff_Op
860
{
861
    /**
862
     * Text_Diff_Op_add constructor.
863
     * @param $lines
864
     */
865
    public function __construct($lines)
866
    {
867
        $this->final = $lines;
868
        $this->orig  = false;
869
    }
870
871
    /**
872
     * @return Text_Diff_Op_delete
873
     */
874
    public function reverse()
875
    {
876
        return $reverse = new Text_Diff_Op_delete($this->final);
0 ignored issues
show
Unused Code introduced by
The assignment to $reverse is dead and can be removed.
Loading history...
877
    }
878
}
879
880
/**
881
 * @package Text_Diff
882
 * @author  Geoffrey T. Dairiki <[email protected]>
883
 *
884
 * @access  private
885
 */
886
class Text_Diff_Op_change extends Text_Diff_Op
887
{
888
    /**
889
     * Text_Diff_Op_change constructor.
890
     * @param $orig
891
     * @param $final
892
     */
893
    public function __construct($orig, $final)
894
    {
895
        $this->orig  = $orig;
896
        $this->final = $final;
897
    }
898
899
    /**
900
     * @return Text_Diff_Op_change
901
     */
902
    public function reverse()
903
    {
904
        return $reverse = new self($this->final, $this->orig);
0 ignored issues
show
Unused Code introduced by
The assignment to $reverse is dead and can be removed.
Loading history...
905
    }
906
}
907