Chris@13: <?php declare(strict_types=1);
Chris@13: 
Chris@13: namespace PhpParser\Internal;
Chris@13: 
Chris@13: /**
Chris@13:  * Implements the Myers diff algorithm.
Chris@13:  *
Chris@13:  * Myers, Eugene W. "An O (ND) difference algorithm and its variations."
Chris@13:  * Algorithmica 1.1 (1986): 251-266.
Chris@13:  *
Chris@13:  * @internal
Chris@13:  */
Chris@13: class Differ
Chris@13: {
Chris@13:     private $isEqual;
Chris@13: 
Chris@13:     /**
Chris@13:      * Create differ over the given equality relation.
Chris@13:      *
Chris@13:      * @param callable $isEqual Equality relation with signature function($a, $b) : bool
Chris@13:      */
Chris@13:     public function __construct(callable $isEqual) {
Chris@13:         $this->isEqual = $isEqual;
Chris@13:     }
Chris@13: 
Chris@13:     /**
Chris@13:      * Calculate diff (edit script) from $old to $new.
Chris@13:      *
Chris@13:      * @param array $old Original array
Chris@13:      * @param array $new New array
Chris@13:      *
Chris@13:      * @return DiffElem[] Diff (edit script)
Chris@13:      */
Chris@13:     public function diff(array $old, array $new) {
Chris@13:         list($trace, $x, $y) = $this->calculateTrace($old, $new);
Chris@13:         return $this->extractDiff($trace, $x, $y, $old, $new);
Chris@13:     }
Chris@13: 
Chris@13:     /**
Chris@13:      * Calculate diff, including "replace" operations.
Chris@13:      *
Chris@13:      * If a sequence of remove operations is followed by the same number of add operations, these
Chris@13:      * will be coalesced into replace operations.
Chris@13:      *
Chris@13:      * @param array $old Original array
Chris@13:      * @param array $new New array
Chris@13:      *
Chris@13:      * @return DiffElem[] Diff (edit script), including replace operations
Chris@13:      */
Chris@13:     public function diffWithReplacements(array $old, array $new) {
Chris@13:         return $this->coalesceReplacements($this->diff($old, $new));
Chris@13:     }
Chris@13: 
Chris@13:     private function calculateTrace(array $a, array $b) {
Chris@13:         $n = \count($a);
Chris@13:         $m = \count($b);
Chris@13:         $max = $n + $m;
Chris@13:         $v = [1 => 0];
Chris@13:         $trace = [];
Chris@13:         for ($d = 0; $d <= $max; $d++) {
Chris@13:             $trace[] = $v;
Chris@13:             for ($k = -$d; $k <= $d; $k += 2) {
Chris@13:                 if ($k === -$d || ($k !== $d && $v[$k-1] < $v[$k+1])) {
Chris@13:                     $x = $v[$k+1];
Chris@13:                 } else {
Chris@13:                     $x = $v[$k-1] + 1;
Chris@13:                 }
Chris@13: 
Chris@13:                 $y = $x - $k;
Chris@13:                 while ($x < $n && $y < $m && ($this->isEqual)($a[$x], $b[$y])) {
Chris@13:                     $x++;
Chris@13:                     $y++;
Chris@13:                 }
Chris@13: 
Chris@13:                 $v[$k] = $x;
Chris@13:                 if ($x >= $n && $y >= $m) {
Chris@13:                     return [$trace, $x, $y];
Chris@13:                 }
Chris@13:             }
Chris@13:         }
Chris@13:         throw new \Exception('Should not happen');
Chris@13:     }
Chris@13: 
Chris@13:     private function extractDiff(array $trace, int $x, int $y, array $a, array $b) {
Chris@13:         $result = [];
Chris@13:         for ($d = \count($trace) - 1; $d >= 0; $d--) {
Chris@13:             $v = $trace[$d];
Chris@13:             $k = $x - $y;
Chris@13: 
Chris@13:             if ($k === -$d || ($k !== $d && $v[$k-1] < $v[$k+1])) {
Chris@13:                 $prevK = $k + 1;
Chris@13:             } else {
Chris@13:                 $prevK = $k - 1;
Chris@13:             }
Chris@13: 
Chris@13:             $prevX = $v[$prevK];
Chris@13:             $prevY = $prevX - $prevK;
Chris@13: 
Chris@13:             while ($x > $prevX && $y > $prevY) {
Chris@13:                 $result[] = new DiffElem(DiffElem::TYPE_KEEP, $a[$x-1], $b[$y-1]);
Chris@13:                 $x--;
Chris@13:                 $y--;
Chris@13:             }
Chris@13: 
Chris@13:             if ($d === 0) {
Chris@13:                 break;
Chris@13:             }
Chris@13: 
Chris@13:             while ($x > $prevX) {
Chris@13:                 $result[] = new DiffElem(DiffElem::TYPE_REMOVE, $a[$x-1], null);
Chris@13:                 $x--;
Chris@13:             }
Chris@13: 
Chris@13:             while ($y > $prevY) {
Chris@13:                 $result[] = new DiffElem(DiffElem::TYPE_ADD, null, $b[$y-1]);
Chris@13:                 $y--;
Chris@13:             }
Chris@13:         }
Chris@13:         return array_reverse($result);
Chris@13:     }
Chris@13: 
Chris@13:     /**
Chris@13:      * Coalesce equal-length sequences of remove+add into a replace operation.
Chris@13:      *
Chris@13:      * @param DiffElem[] $diff
Chris@13:      * @return DiffElem[]
Chris@13:      */
Chris@13:     private function coalesceReplacements(array $diff) {
Chris@13:         $newDiff = [];
Chris@13:         $c = \count($diff);
Chris@13:         for ($i = 0; $i < $c; $i++) {
Chris@13:             $diffType = $diff[$i]->type;
Chris@13:             if ($diffType !== DiffElem::TYPE_REMOVE) {
Chris@13:                 $newDiff[] = $diff[$i];
Chris@13:                 continue;
Chris@13:             }
Chris@13: 
Chris@13:             $j = $i;
Chris@13:             while ($j < $c && $diff[$j]->type === DiffElem::TYPE_REMOVE) {
Chris@13:                 $j++;
Chris@13:             }
Chris@13: 
Chris@13:             $k = $j;
Chris@13:             while ($k < $c && $diff[$k]->type === DiffElem::TYPE_ADD) {
Chris@13:                 $k++;
Chris@13:             }
Chris@13: 
Chris@13:             if ($j - $i === $k - $j) {
Chris@13:                 $len = $j - $i;
Chris@13:                 for ($n = 0; $n < $len; $n++) {
Chris@13:                     $newDiff[] = new DiffElem(
Chris@13:                         DiffElem::TYPE_REPLACE, $diff[$i + $n]->old, $diff[$j + $n]->new
Chris@13:                     );
Chris@13:                 }
Chris@13:             } else {
Chris@13:                 for (; $i < $k; $i++) {
Chris@13:                     $newDiff[] = $diff[$i];
Chris@13:                 }
Chris@13:             }
Chris@13:             $i = $k - 1;
Chris@13:         }
Chris@13:         return $newDiff;
Chris@13:     }
Chris@13: }