annotate vendor/nikic/php-parser/lib/PhpParser/Internal/Differ.php @ 19:fa3358dc1485 tip

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