www.aleph1.co.uk Git - yaffs-website/blob - vendor/nikic/php-parser/lib/PhpParser/Internal/Differ.php

   1 <?php declare(strict_types=1);
   2
   3 namespace PhpParser\Internal;
   4
   5 /**
   6  * Implements the Myers diff algorithm.
   7  *
   8  * Myers, Eugene W. "An O (ND) difference algorithm and its variations."
   9  * Algorithmica 1.1 (1986): 251-266.
  10  *
  11  * @internal
  12  */
  13 class Differ
  14 {
  15     private $isEqual;
  16
  17     /**
  18      * Create differ over the given equality relation.
  19      *
  20      * @param callable $isEqual Equality relation with signature function($a, $b) : bool
  21      */
  22     public function __construct(callable $isEqual) {
  23         $this->isEqual = $isEqual;
  24     }
  25
  26     /**
  27      * Calculate diff (edit script) from $old to $new.
  28      *
  29      * @param array $old Original array
  30      * @param array $new New array
  31      *
  32      * @return DiffElem[] Diff (edit script)
  33      */
  34     public function diff(array $old, array $new) {
  35         list($trace, $x, $y) = $this->calculateTrace($old, $new);
  36         return $this->extractDiff($trace, $x, $y, $old, $new);
  37     }
  38
  39     /**
  40      * Calculate diff, including "replace" operations.
  41      *
  42      * If a sequence of remove operations is followed by the same number of add operations, these
  43      * will be coalesced into replace operations.
  44      *
  45      * @param array $old Original array
  46      * @param array $new New array
  47      *
  48      * @return DiffElem[] Diff (edit script), including replace operations
  49      */
  50     public function diffWithReplacements(array $old, array $new) {
  51         return $this->coalesceReplacements($this->diff($old, $new));
  52     }
  53
  54     private function calculateTrace(array $a, array $b) {
  55         $n = \count($a);
  56         $m = \count($b);
  57         $max = $n + $m;
  58         $v = [1 => 0];
  59         $trace = [];
  60         for ($d = 0; $d <= $max; $d++) {
  61             $trace[] = $v;
  62             for ($k = -$d; $k <= $d; $k += 2) {
  63                 if ($k === -$d || ($k !== $d && $v[$k-1] < $v[$k+1])) {
  64                     $x = $v[$k+1];
  65                 } else {
  66                     $x = $v[$k-1] + 1;
  67                 }
  68
  69                 $y = $x - $k;
  70                 while ($x < $n && $y < $m && ($this->isEqual)($a[$x], $b[$y])) {
  71                     $x++;
  72                     $y++;
  73                 }
  74
  75                 $v[$k] = $x;
  76                 if ($x >= $n && $y >= $m) {
  77                     return [$trace, $x, $y];
  78                 }
  79             }
  80         }
  81         throw new \Exception('Should not happen');
  82     }
  83
  84     private function extractDiff(array $trace, int $x, int $y, array $a, array $b) {
  85         $result = [];
  86         for ($d = \count($trace) - 1; $d >= 0; $d--) {
  87             $v = $trace[$d];
  88             $k = $x - $y;
  89
  90             if ($k === -$d || ($k !== $d && $v[$k-1] < $v[$k+1])) {
  91                 $prevK = $k + 1;
  92             } else {
  93                 $prevK = $k - 1;
  94             }
  95
  96             $prevX = $v[$prevK];
  97             $prevY = $prevX - $prevK;
  98
  99             while ($x > $prevX && $y > $prevY) {
 100                 $result[] = new DiffElem(DiffElem::TYPE_KEEP, $a[$x-1], $b[$y-1]);
 101                 $x--;
 102                 $y--;
 103             }
 104
 105             if ($d === 0) {
 106                 break;
 107             }
 108
 109             while ($x > $prevX) {
 110                 $result[] = new DiffElem(DiffElem::TYPE_REMOVE, $a[$x-1], null);
 111                 $x--;
 112             }
 113
 114             while ($y > $prevY) {
 115                 $result[] = new DiffElem(DiffElem::TYPE_ADD, null, $b[$y-1]);
 116                 $y--;
 117             }
 118         }
 119         return array_reverse($result);
 120     }
 121
 122     /**
 123      * Coalesce equal-length sequences of remove+add into a replace operation.
 124      *
 125      * @param DiffElem[] $diff
 126      * @return DiffElem[]
 127      */
 128     private function coalesceReplacements(array $diff) {
 129         $newDiff = [];
 130         $c = \count($diff);
 131         for ($i = 0; $i < $c; $i++) {
 132             $diffType = $diff[$i]->type;
 133             if ($diffType !== DiffElem::TYPE_REMOVE) {
 134                 $newDiff[] = $diff[$i];
 135                 continue;
 136             }
 137
 138             $j = $i;
 139             while ($j < $c && $diff[$j]->type === DiffElem::TYPE_REMOVE) {
 140                 $j++;
 141             }
 142
 143             $k = $j;
 144             while ($k < $c && $diff[$k]->type === DiffElem::TYPE_ADD) {
 145                 $k++;
 146             }
 147
 148             if ($j - $i === $k - $j) {
 149                 $len = $j - $i;
 150                 for ($n = 0; $n < $len; $n++) {
 151                     $newDiff[] = new DiffElem(
 152                         DiffElem::TYPE_REPLACE, $diff[$i + $n]->old, $diff[$j + $n]->new
 153                     );
 154                 }
 155             } else {
 156                 for (; $i < $k; $i++) {
 157                     $newDiff[] = $diff[$i];
 158                 }
 159             }
 160             $i = $k - 1;
 161         }
 162         return $newDiff;
 163     }
 164 }