Verzeichnisstruktur phpBB-3.0.0
- Veröffentlicht
- 12.12.2007
So funktioniert es
|
|
Auf das letzte Element klicken. Dies geht jeweils ein Schritt zurück |
Auf das Icon klicken, dies öffnet das Verzeichnis. Nochmal klicken schließt das Verzeichnis. |
|
|
(Beispiel Datei-Icons)
|
Auf das Icon klicken um den Quellcode anzuzeigen |
engine.php
001 <?php
002 /**
003 *
004 * @package diff
005 * @version $Id$
006 * @copyright (c) 2006 phpBB Group
007 * @license http://opensource.org/licenses/gpl-license.php GNU Public License
008 *
009 */
010
011 /**
012 * @ignore
013 */
014 if (!defined('IN_PHPBB'))
015 {
016 exit;
017 }
018
019 /**
020 * Code from pear.php.net, Text_Diff-0.2.1 (beta) package
021 * http://pear.php.net/package/Text_Diff/
022 *
023 * Modified by phpBB Group to meet our coding standards
024 * and being able to integrate into phpBB
025 *
026 * Class used internally by Diff to actually compute the diffs. This class is
027 * implemented using native PHP code.
028 *
029 * The algorithm used here is mostly lifted from the perl module
030 * Algorithm::Diff (version 1.06) by Ned Konz, which is available at:
031 * http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip
032 *
033 * More ideas are taken from:
034 * http://www.ics.uci.edu/~eppstein/161/960229.html
035 *
036 * Some ideas (and a bit of code) are taken from analyze.c, of GNU
037 * diffutils-2.7, which can be found at:
038 * ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
039 *
040 * Some ideas (subdivision by NCHUNKS > 2, and some optimizations) are from
041 * Geoffrey T. Dairiki <dairiki@dairiki.org>. The original PHP version of this
042 * code was written by him, and is used/adapted with his permission.
043 *
044 * @author Geoffrey T. Dairiki <dairiki@dairiki.org>
045 * @package diff
046 *
047 * @access private
048 */
049 class diff_engine
050 {
051 function diff(&$from_lines, &$to_lines, $preserve_cr = true)
052 {
053 // Remove empty lines...
054 // 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
055 // 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
056
057 if (is_array($from_lines))
058 {
059 $from_lines = implode("\n", $from_lines);
060 }
061
062 if (is_array($to_lines))
063 {
064 $to_lines = implode("\n", $to_lines);
065 }
066
067 if ($preserve_cr)
068 {
069 $from_lines = explode("\n", str_replace("\r", "\n", str_replace("\r\n", "\n", $from_lines)));
070 $to_lines = explode("\n", str_replace("\r", "\n", str_replace("\r\n", "\n", $to_lines)));
071 }
072 else
073 {
074 $from_lines = explode("\n", preg_replace('#[\n\r]+#', "\n", $from_lines));
075 $to_lines = explode("\n", preg_replace('#[\n\r]+#', "\n", $to_lines));
076 }
077
078 $n_from = sizeof($from_lines);
079 $n_to = sizeof($to_lines);
080
081 $this->xchanged = $this->ychanged = $this->xv = $this->yv = $this->xind = $this->yind = array();
082 unset($this->seq, $this->in_seq, $this->lcs);
083
084 // Skip leading common lines.
085 for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++)
086 {
087 if ($from_lines[$skip] !== $to_lines[$skip])
088 {
089 break;
090 }
091 $this->xchanged[$skip] = $this->ychanged[$skip] = false;
092 }
093
094 // Skip trailing common lines.
095 $xi = $n_from;
096 $yi = $n_to;
097
098 for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++)
099 {
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 ?>