Subversion-Projekte lars-tiefland.laravel_shop

Revision

Details | Letzte Änderung | Log anzeigen | RSS feed

Revision Autor Zeilennr. Zeile
148 lars 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 
}