aleph1.co.uk Git - yaffs-website/blob - web/core/lib/Drupal/Component/Diff/Engine/DiffEngine.php

   1 <?php
   2
   3 namespace Drupal\Component\Diff\Engine;
   4
   5 /**
   6  * Class used internally by Diff to actually compute the diffs.
   7  *
   8  * The algorithm used here is mostly lifted from the perl module
   9  * Algorithm::Diff (version 1.06) by Ned Konz, which is available at:
  10  *   http://www.perl.com/CPAN/authors/id/N/NE/NEDKONZ/Algorithm-Diff-1.06.zip
  11  *
  12  * More ideas are taken from:
  13  *   http://www.ics.uci.edu/~eppstein/161/960229.html
  14  *
  15  * Some ideas (and a bit of code) are from analyze.c, from GNU
  16  * diffutils-2.7, which can be found at:
  17  *   ftp://gnudist.gnu.org/pub/gnu/diffutils/diffutils-2.7.tar.gz
  18  *
  19  * closingly, some ideas (subdivision by NCHUNKS > 2, and some optimizations)
  20  * are my own.
  21  *
  22  * Line length limits for robustness added by Tim Starling, 2005-08-31
  23  *
  24  * @author Geoffrey T. Dairiki, Tim Starling
  25  * @private
  26  * @subpackage DifferenceEngine
  27  */
  28 class DiffEngine {
  29
  30   const USE_ASSERTS = FALSE;
  31
  32   const MAX_XREF_LENGTH = 10000;
  33
  34   public function diff($from_lines, $to_lines) {
  35
  36     $n_from = sizeof($from_lines);
  37     $n_to = sizeof($to_lines);
  38
  39     $this->xchanged = $this->ychanged = [];
  40     $this->xv = $this->yv = [];
  41     $this->xind = $this->yind = [];
  42     unset($this->seq);
  43     unset($this->in_seq);
  44     unset($this->lcs);
  45
  46     // Skip leading common lines.
  47     for ($skip = 0; $skip < $n_from && $skip < $n_to; $skip++) {
  48       if ($from_lines[$skip] !== $to_lines[$skip]) {
  49         break;
  50       }
  51       $this->xchanged[$skip] = $this->ychanged[$skip] = FALSE;
  52     }
  53     // Skip trailing common lines.
  54     $xi = $n_from;
  55     $yi = $n_to;
  56     for ($endskip = 0; --$xi > $skip && --$yi > $skip; $endskip++) {
  57       if ($from_lines[$xi] !== $to_lines[$yi]) {
  58         break;
  59       }
  60       $this->xchanged[$xi] = $this->ychanged[$yi] = FALSE;
  61     }
  62
  63     // Ignore lines which do not exist in both files.
  64     for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
  65       $xhash[$this->_line_hash($from_lines[$xi])] = 1;
  66     }
  67
  68     for ($yi = $skip; $yi < $n_to - $endskip; $yi++) {
  69       $line = $to_lines[$yi];
  70       if ($this->ychanged[$yi] = empty($xhash[$this->_line_hash($line)])) {
  71         continue;
  72       }
  73       $yhash[$this->_line_hash($line)] = 1;
  74       $this->yv[] = $line;
  75       $this->yind[] = $yi;
  76     }
  77     for ($xi = $skip; $xi < $n_from - $endskip; $xi++) {
  78       $line = $from_lines[$xi];
  79       if ($this->xchanged[$xi] = empty($yhash[$this->_line_hash($line)])) {
  80         continue;
  81       }
  82       $this->xv[] = $line;
  83       $this->xind[] = $xi;
  84     }
  85
  86     // Find the LCS.
  87     $this->_compareseq(0, sizeof($this->xv), 0, sizeof($this->yv));
  88
  89     // Merge edits when possible
  90     $this->_shift_boundaries($from_lines, $this->xchanged, $this->ychanged);
  91     $this->_shift_boundaries($to_lines, $this->ychanged, $this->xchanged);
  92
  93     // Compute the edit operations.
  94     $edits = [];
  95     $xi = $yi = 0;
  96     while ($xi < $n_from || $yi < $n_to) {
  97       $this::USE_ASSERTS && assert($yi < $n_to || $this->xchanged[$xi]);
  98       $this::USE_ASSERTS && assert($xi < $n_from || $this->ychanged[$yi]);
  99
 100       // Skip matching "snake".
 101       $copy = [];
 102       while ( $xi < $n_from && $yi < $n_to && !$this->xchanged[$xi] && !$this->ychanged[$yi]) {
 103         $copy[] = $from_lines[$xi++];
 104         ++$yi;
 105       }
 106       if ($copy) {
 107         $edits[] = new DiffOpCopy($copy);
 108       }
 109       // Find deletes & adds.
 110       $delete = [];
 111       while ($xi < $n_from && $this->xchanged[$xi]) {
 112         $delete[] = $from_lines[$xi++];
 113       }
 114       $add = [];
 115       while ($yi < $n_to && $this->ychanged[$yi]) {
 116         $add[] = $to_lines[$yi++];
 117       }
 118       if ($delete && $add) {
 119         $edits[] = new DiffOpChange($delete, $add);
 120       }
 121       elseif ($delete) {
 122         $edits[] = new DiffOpDelete($delete);
 123       }
 124       elseif ($add) {
 125         $edits[] = new DiffOpAdd($add);
 126       }
 127     }
 128     return $edits;
 129   }
 130
 131   /**
 132    * Returns the whole line if it's small enough, or the MD5 hash otherwise.
 133    */
 134   protected function _line_hash($line) {
 135     if (mb_strlen($line) > $this::MAX_XREF_LENGTH) {
 136       return md5($line);
 137     }
 138     else {
 139       return $line;
 140     }
 141   }
 142
 143
 144   /**
 145    * Divide the Largest Common Subsequence (LCS) of the sequences
 146    * [XOFF, XLIM) and [YOFF, YLIM) into NCHUNKS approximately equally
 147    * sized segments.
 148    *
 149    * Returns (LCS, PTS).  LCS is the length of the LCS. PTS is an
 150    * array of NCHUNKS+1 (X, Y) indexes giving the diving points between
 151    * sub sequences.  The first sub-sequence is contained in [X0, X1),
 152    * [Y0, Y1), the second in [X1, X2), [Y1, Y2) and so on.  Note
 153    * that (X0, Y0) == (XOFF, YOFF) and
 154    * (X[NCHUNKS], Y[NCHUNKS]) == (XLIM, YLIM).
 155    *
 156    * This function assumes that the first lines of the specified portions
 157    * of the two files do not match, and likewise that the last lines do not
 158    * match.  The caller must trim matching lines from the beginning and end
 159    * of the portions it is going to specify.
 160    */
 161   protected function _diag($xoff, $xlim, $yoff, $ylim, $nchunks) {
 162     $flip = FALSE;
 163
 164     if ($xlim - $xoff > $ylim - $yoff) {
 165       // Things seems faster (I'm not sure I understand why)
 166       // when the shortest sequence in X.
 167       $flip = TRUE;
 168       list($xoff, $xlim, $yoff, $ylim) = [$yoff, $ylim, $xoff, $xlim];
 169     }
 170
 171     if ($flip) {
 172       for ($i = $ylim - 1; $i >= $yoff; $i--) {
 173         $ymatches[$this->xv[$i]][] = $i;
 174       }
 175     }
 176     else {
 177       for ($i = $ylim - 1; $i >= $yoff; $i--) {
 178         $ymatches[$this->yv[$i]][] = $i;
 179       }
 180     }
 181     $this->lcs = 0;
 182     $this->seq[0] = $yoff - 1;
 183     $this->in_seq = [];
 184     $ymids[0] = [];
 185
 186     $numer = $xlim - $xoff + $nchunks - 1;
 187     $x = $xoff;
 188     for ($chunk = 0; $chunk < $nchunks; $chunk++) {
 189       if ($chunk > 0) {
 190         for ($i = 0; $i <= $this->lcs; $i++) {
 191           $ymids[$i][$chunk - 1] = $this->seq[$i];
 192         }
 193       }
 194
 195       $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $chunk) / $nchunks);
 196       for (; $x < $x1; $x++) {
 197         $line = $flip ? $this->yv[$x] : $this->xv[$x];
 198         if (empty($ymatches[$line])) {
 199           continue;
 200         }
 201         $matches = $ymatches[$line];
 202         $found_empty = FALSE;
 203         foreach ($matches as $y) {
 204           if (!$found_empty) {
 205             if (empty($this->in_seq[$y])) {
 206               $k = $this->_lcs_pos($y);
 207               $this::USE_ASSERTS && assert($k > 0);
 208               $ymids[$k] = $ymids[$k - 1];
 209               $found_empty = TRUE;
 210             }
 211           }
 212           else {
 213             if ($y > $this->seq[$k - 1]) {
 214               $this::USE_ASSERTS && assert($y < $this->seq[$k]);
 215               // Optimization: this is a common case:
 216               // next match is just replacing previous match.
 217               $this->in_seq[$this->seq[$k]] = FALSE;
 218               $this->seq[$k] = $y;
 219               $this->in_seq[$y] = 1;
 220             }
 221             elseif (empty($this->in_seq[$y])) {
 222               $k = $this->_lcs_pos($y);
 223               $this::USE_ASSERTS && assert($k > 0);
 224               $ymids[$k] = $ymids[$k - 1];
 225             }
 226           }
 227         }
 228       }
 229     }
 230
 231     $seps[] = $flip ? [$yoff, $xoff] : [$xoff, $yoff];
 232     $ymid = $ymids[$this->lcs];
 233     for ($n = 0; $n < $nchunks - 1; $n++) {
 234       $x1 = $xoff + (int)(($numer + ($xlim - $xoff) * $n) / $nchunks);
 235       $y1 = $ymid[$n] + 1;
 236       $seps[] = $flip ? [$y1, $x1] : [$x1, $y1];
 237     }
 238     $seps[] = $flip ? [$ylim, $xlim] : [$xlim, $ylim];
 239
 240     return [$this->lcs, $seps];
 241   }
 242
 243   protected function _lcs_pos($ypos) {
 244
 245     $end = $this->lcs;
 246     if ($end == 0 || $ypos > $this->seq[$end]) {
 247       $this->seq[++$this->lcs] = $ypos;
 248       $this->in_seq[$ypos] = 1;
 249       return $this->lcs;
 250     }
 251
 252     $beg = 1;
 253     while ($beg < $end) {
 254       $mid = (int)(($beg + $end) / 2);
 255       if ($ypos > $this->seq[$mid]) {
 256         $beg = $mid + 1;
 257       }
 258       else {
 259         $end = $mid;
 260       }
 261     }
 262
 263     $this::USE_ASSERTS && assert($ypos != $this->seq[$end]);
 264
 265     $this->in_seq[$this->seq[$end]] = FALSE;
 266     $this->seq[$end] = $ypos;
 267     $this->in_seq[$ypos] = 1;
 268     return $end;
 269   }
 270
 271   /**
 272    * Find LCS of two sequences.
 273    *
 274    * The results are recorded in the vectors $this->{x,y}changed[], by
 275    * storing a 1 in the element for each line that is an insertion
 276    * or deletion (ie. is not in the LCS).
 277    *
 278    * The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1.
 279    *
 280    * Note that XLIM, YLIM are exclusive bounds.
 281    * All line numbers are origin-0 and discarded lines are not counted.
 282    */
 283   protected function _compareseq($xoff, $xlim, $yoff, $ylim) {
 284
 285     // Slide down the bottom initial diagonal.
 286     while ($xoff < $xlim && $yoff < $ylim && $this->xv[$xoff] == $this->yv[$yoff]) {
 287       ++$xoff;
 288       ++$yoff;
 289     }
 290
 291     // Slide up the top initial diagonal.
 292     while ($xlim > $xoff && $ylim > $yoff && $this->xv[$xlim - 1] == $this->yv[$ylim - 1]) {
 293       --$xlim;
 294       --$ylim;
 295     }
 296
 297     if ($xoff == $xlim || $yoff == $ylim) {
 298       $lcs = 0;
 299     }
 300     else {
 301       // This is ad hoc but seems to work well.
 302       //$nchunks = sqrt(min($xlim - $xoff, $ylim - $yoff) / 2.5);
 303       //$nchunks = max(2, min(8, (int)$nchunks));
 304       $nchunks = min(7, $xlim - $xoff, $ylim - $yoff) + 1;
 305       list($lcs, $seps) = $this->_diag($xoff, $xlim, $yoff, $ylim, $nchunks);
 306     }
 307
 308     if ($lcs == 0) {
 309       // X and Y sequences have no common subsequence:
 310       // mark all changed.
 311       while ($yoff < $ylim) {
 312         $this->ychanged[$this->yind[$yoff++]] = 1;
 313       }
 314       while ($xoff < $xlim) {
 315         $this->xchanged[$this->xind[$xoff++]] = 1;
 316       }
 317     }
 318     else {
 319       // Use the partitions to split this problem into subproblems.
 320       reset($seps);
 321       $pt1 = $seps[0];
 322       while ($pt2 = next($seps)) {
 323         $this->_compareseq ($pt1[0], $pt2[0], $pt1[1], $pt2[1]);
 324         $pt1 = $pt2;
 325       }
 326     }
 327   }
 328
 329   /**
 330    * Adjust inserts/deletes of identical lines to join changes
 331    * as much as possible.
 332    *
 333    * We do something when a run of changed lines include a
 334    * line at one end and has an excluded, identical line at the other.
 335    * We are free to choose which identical line is included.
 336    * `compareseq' usually chooses the one at the beginning,
 337    * but usually it is cleaner to consider the following identical line
 338    * to be the "change".
 339    *
 340    * This is extracted verbatim from analyze.c (GNU diffutils-2.7).
 341    */
 342   protected function _shift_boundaries($lines, &$changed, $other_changed) {
 343     $i = 0;
 344     $j = 0;
 345
 346     $this::USE_ASSERTS && assert(sizeof($lines) == sizeof($changed));
 347     $len = sizeof($lines);
 348     $other_len = sizeof($other_changed);
 349
 350     while (1) {
 351       /*
 352        * Scan forwards to find beginning of another run of changes.
 353        * Also keep track of the corresponding point in the other file.
 354        *
 355        * Throughout this code, $i and $j are adjusted together so that
 356        * the first $i elements of $changed and the first $j elements
 357        * of $other_changed both contain the same number of zeros
 358        * (unchanged lines).
 359        * Furthermore, $j is always kept so that $j == $other_len or
 360        * $other_changed[$j] == FALSE.
 361        */
 362       while ($j < $other_len && $other_changed[$j]) {
 363         $j++;
 364       }
 365       while ($i < $len && !$changed[$i]) {
 366         $this::USE_ASSERTS && assert($j < $other_len && ! $other_changed[$j]);
 367         $i++;
 368         $j++;
 369         while ($j < $other_len && $other_changed[$j]) {
 370           $j++;
 371         }
 372       }
 373
 374       if ($i == $len) {
 375         break;
 376       }
 377       $start = $i;
 378
 379       // Find the end of this run of changes.
 380       while (++$i < $len && $changed[$i]) {
 381         continue;
 382       }
 383
 384       do {
 385         /*
 386          * Record the length of this run of changes, so that
 387          * we can later determine whether the run has grown.
 388          */
 389         $runlength = $i - $start;
 390
 391         /*
 392          * Move the changed region back, so long as the
 393          * previous unchanged line matches the last changed one.
 394          * This merges with previous changed regions.
 395          */
 396         while ($start > 0 && $lines[$start - 1] == $lines[$i - 1]) {
 397           $changed[--$start] = 1;
 398           $changed[--$i] = FALSE;
 399           while ($start > 0 && $changed[$start - 1]) {
 400             $start--;
 401           }
 402           $this::USE_ASSERTS && assert($j > 0);
 403           while ($other_changed[--$j]) {
 404             continue;
 405           }
 406           $this::USE_ASSERTS && assert($j >= 0 && !$other_changed[$j]);
 407         }
 408
 409         /*
 410          * Set CORRESPONDING to the end of the changed run, at the last
 411          * point where it corresponds to a changed run in the other file.
 412          * CORRESPONDING == LEN means no such point has been found.
 413          */
 414         $corresponding = $j < $other_len ? $i : $len;
 415
 416         /*
 417          * Move the changed region forward, so long as the
 418          * first changed line matches the following unchanged one.
 419          * This merges with following changed regions.
 420          * Do this second, so that if there are no merges,
 421          * the changed region is moved forward as far as possible.
 422          */
 423         while ($i < $len && $lines[$start] == $lines[$i]) {
 424           $changed[$start++] = FALSE;
 425           $changed[$i++] = 1;
 426           while ($i < $len && $changed[$i]) {
 427             $i++;
 428           }
 429           $this::USE_ASSERTS && assert($j < $other_len && ! $other_changed[$j]);
 430           $j++;
 431           if ($j < $other_len && $other_changed[$j]) {
 432             $corresponding = $i;
 433             while ($j < $other_len && $other_changed[$j]) {
 434               $j++;
 435             }
 436           }
 437         }
 438       } while ($runlength != $i - $start);
 439
 440       /*
 441        * If possible, move the fully-merged run of changes
 442        * back to a corresponding run in the other file.
 443        */
 444       while ($corresponding < $i) {
 445         $changed[--$start] = 1;
 446         $changed[--$i] = 0;
 447         $this::USE_ASSERTS && assert($j > 0);
 448         while ($other_changed[--$j]) {
 449           continue;
 450         }
 451         $this::USE_ASSERTS && assert($j >= 0 && !$other_changed[$j]);
 452       }
 453     }
 454   }
 455
 456 }