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.
Auf den Verzeichnisnamen klicken, dies zeigt nur das Verzeichnis mit Inhalt an

(Beispiel Datei-Icons)

Auf das Icon klicken um den Quellcode anzuzeigen

engine.php

Zuletzt modifiziert: 09.10.2024, 12:51 - Dateigröße: 12.68 KiB


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  ?>