]>
Commit | Line | Data |
---|---|---|
107c1cdb ND |
1 | // Copyright 2017, The Go Authors. All rights reserved. |
2 | // Use of this source code is governed by a BSD-style | |
3 | // license that can be found in the LICENSE.md file. | |
4 | ||
5 | // Package diff implements an algorithm for producing edit-scripts. | |
6 | // The edit-script is a sequence of operations needed to transform one list | |
7 | // of symbols into another (or vice-versa). The edits allowed are insertions, | |
8 | // deletions, and modifications. The summation of all edits is called the | |
9 | // Levenshtein distance as this problem is well-known in computer science. | |
10 | // | |
11 | // This package prioritizes performance over accuracy. That is, the run time | |
12 | // is more important than obtaining a minimal Levenshtein distance. | |
13 | package diff | |
14 | ||
15 | // EditType represents a single operation within an edit-script. | |
16 | type EditType uint8 | |
17 | ||
18 | const ( | |
19 | // Identity indicates that a symbol pair is identical in both list X and Y. | |
20 | Identity EditType = iota | |
21 | // UniqueX indicates that a symbol only exists in X and not Y. | |
22 | UniqueX | |
23 | // UniqueY indicates that a symbol only exists in Y and not X. | |
24 | UniqueY | |
25 | // Modified indicates that a symbol pair is a modification of each other. | |
26 | Modified | |
27 | ) | |
28 | ||
29 | // EditScript represents the series of differences between two lists. | |
30 | type EditScript []EditType | |
31 | ||
32 | // String returns a human-readable string representing the edit-script where | |
33 | // Identity, UniqueX, UniqueY, and Modified are represented by the | |
34 | // '.', 'X', 'Y', and 'M' characters, respectively. | |
35 | func (es EditScript) String() string { | |
36 | b := make([]byte, len(es)) | |
37 | for i, e := range es { | |
38 | switch e { | |
39 | case Identity: | |
40 | b[i] = '.' | |
41 | case UniqueX: | |
42 | b[i] = 'X' | |
43 | case UniqueY: | |
44 | b[i] = 'Y' | |
45 | case Modified: | |
46 | b[i] = 'M' | |
47 | default: | |
48 | panic("invalid edit-type") | |
49 | } | |
50 | } | |
51 | return string(b) | |
52 | } | |
53 | ||
54 | // stats returns a histogram of the number of each type of edit operation. | |
55 | func (es EditScript) stats() (s struct{ NI, NX, NY, NM int }) { | |
56 | for _, e := range es { | |
57 | switch e { | |
58 | case Identity: | |
59 | s.NI++ | |
60 | case UniqueX: | |
61 | s.NX++ | |
62 | case UniqueY: | |
63 | s.NY++ | |
64 | case Modified: | |
65 | s.NM++ | |
66 | default: | |
67 | panic("invalid edit-type") | |
68 | } | |
69 | } | |
70 | return | |
71 | } | |
72 | ||
73 | // Dist is the Levenshtein distance and is guaranteed to be 0 if and only if | |
74 | // lists X and Y are equal. | |
75 | func (es EditScript) Dist() int { return len(es) - es.stats().NI } | |
76 | ||
77 | // LenX is the length of the X list. | |
78 | func (es EditScript) LenX() int { return len(es) - es.stats().NY } | |
79 | ||
80 | // LenY is the length of the Y list. | |
81 | func (es EditScript) LenY() int { return len(es) - es.stats().NX } | |
82 | ||
83 | // EqualFunc reports whether the symbols at indexes ix and iy are equal. | |
84 | // When called by Difference, the index is guaranteed to be within nx and ny. | |
85 | type EqualFunc func(ix int, iy int) Result | |
86 | ||
87 | // Result is the result of comparison. | |
863486a6 AG |
88 | // NumSame is the number of sub-elements that are equal. |
89 | // NumDiff is the number of sub-elements that are not equal. | |
90 | type Result struct{ NumSame, NumDiff int } | |
91 | ||
92 | // BoolResult returns a Result that is either Equal or not Equal. | |
93 | func BoolResult(b bool) Result { | |
94 | if b { | |
95 | return Result{NumSame: 1} // Equal, Similar | |
96 | } else { | |
97 | return Result{NumDiff: 2} // Not Equal, not Similar | |
98 | } | |
99 | } | |
107c1cdb ND |
100 | |
101 | // Equal indicates whether the symbols are equal. Two symbols are equal | |
863486a6 AG |
102 | // if and only if NumDiff == 0. If Equal, then they are also Similar. |
103 | func (r Result) Equal() bool { return r.NumDiff == 0 } | |
107c1cdb ND |
104 | |
105 | // Similar indicates whether two symbols are similar and may be represented | |
106 | // by using the Modified type. As a special case, we consider binary comparisons | |
107 | // (i.e., those that return Result{1, 0} or Result{0, 1}) to be similar. | |
108 | // | |
863486a6 | 109 | // The exact ratio of NumSame to NumDiff to determine similarity may change. |
107c1cdb | 110 | func (r Result) Similar() bool { |
863486a6 AG |
111 | // Use NumSame+1 to offset NumSame so that binary comparisons are similar. |
112 | return r.NumSame+1 >= r.NumDiff | |
107c1cdb ND |
113 | } |
114 | ||
115 | // Difference reports whether two lists of lengths nx and ny are equal | |
116 | // given the definition of equality provided as f. | |
117 | // | |
118 | // This function returns an edit-script, which is a sequence of operations | |
119 | // needed to convert one list into the other. The following invariants for | |
120 | // the edit-script are maintained: | |
121 | // • eq == (es.Dist()==0) | |
122 | // • nx == es.LenX() | |
123 | // • ny == es.LenY() | |
124 | // | |
125 | // This algorithm is not guaranteed to be an optimal solution (i.e., one that | |
126 | // produces an edit-script with a minimal Levenshtein distance). This algorithm | |
127 | // favors performance over optimality. The exact output is not guaranteed to | |
128 | // be stable and may change over time. | |
129 | func Difference(nx, ny int, f EqualFunc) (es EditScript) { | |
130 | // This algorithm is based on traversing what is known as an "edit-graph". | |
131 | // See Figure 1 from "An O(ND) Difference Algorithm and Its Variations" | |
132 | // by Eugene W. Myers. Since D can be as large as N itself, this is | |
133 | // effectively O(N^2). Unlike the algorithm from that paper, we are not | |
134 | // interested in the optimal path, but at least some "decent" path. | |
135 | // | |
136 | // For example, let X and Y be lists of symbols: | |
137 | // X = [A B C A B B A] | |
138 | // Y = [C B A B A C] | |
139 | // | |
140 | // The edit-graph can be drawn as the following: | |
141 | // A B C A B B A | |
142 | // ┌─────────────┐ | |
143 | // C │_|_|\|_|_|_|_│ 0 | |
144 | // B │_|\|_|_|\|\|_│ 1 | |
145 | // A │\|_|_|\|_|_|\│ 2 | |
146 | // B │_|\|_|_|\|\|_│ 3 | |
147 | // A │\|_|_|\|_|_|\│ 4 | |
148 | // C │ | |\| | | | │ 5 | |
149 | // └─────────────┘ 6 | |
150 | // 0 1 2 3 4 5 6 7 | |
151 | // | |
152 | // List X is written along the horizontal axis, while list Y is written | |
153 | // along the vertical axis. At any point on this grid, if the symbol in | |
154 | // list X matches the corresponding symbol in list Y, then a '\' is drawn. | |
155 | // The goal of any minimal edit-script algorithm is to find a path from the | |
156 | // top-left corner to the bottom-right corner, while traveling through the | |
157 | // fewest horizontal or vertical edges. | |
158 | // A horizontal edge is equivalent to inserting a symbol from list X. | |
159 | // A vertical edge is equivalent to inserting a symbol from list Y. | |
160 | // A diagonal edge is equivalent to a matching symbol between both X and Y. | |
161 | ||
162 | // Invariants: | |
163 | // • 0 ≤ fwdPath.X ≤ (fwdFrontier.X, revFrontier.X) ≤ revPath.X ≤ nx | |
164 | // • 0 ≤ fwdPath.Y ≤ (fwdFrontier.Y, revFrontier.Y) ≤ revPath.Y ≤ ny | |
165 | // | |
166 | // In general: | |
167 | // • fwdFrontier.X < revFrontier.X | |
168 | // • fwdFrontier.Y < revFrontier.Y | |
169 | // Unless, it is time for the algorithm to terminate. | |
170 | fwdPath := path{+1, point{0, 0}, make(EditScript, 0, (nx+ny)/2)} | |
171 | revPath := path{-1, point{nx, ny}, make(EditScript, 0)} | |
172 | fwdFrontier := fwdPath.point // Forward search frontier | |
173 | revFrontier := revPath.point // Reverse search frontier | |
174 | ||
175 | // Search budget bounds the cost of searching for better paths. | |
176 | // The longest sequence of non-matching symbols that can be tolerated is | |
177 | // approximately the square-root of the search budget. | |
178 | searchBudget := 4 * (nx + ny) // O(n) | |
179 | ||
180 | // The algorithm below is a greedy, meet-in-the-middle algorithm for | |
181 | // computing sub-optimal edit-scripts between two lists. | |
182 | // | |
183 | // The algorithm is approximately as follows: | |
184 | // • Searching for differences switches back-and-forth between | |
185 | // a search that starts at the beginning (the top-left corner), and | |
186 | // a search that starts at the end (the bottom-right corner). The goal of | |
187 | // the search is connect with the search from the opposite corner. | |
188 | // • As we search, we build a path in a greedy manner, where the first | |
189 | // match seen is added to the path (this is sub-optimal, but provides a | |
190 | // decent result in practice). When matches are found, we try the next pair | |
191 | // of symbols in the lists and follow all matches as far as possible. | |
192 | // • When searching for matches, we search along a diagonal going through | |
193 | // through the "frontier" point. If no matches are found, we advance the | |
194 | // frontier towards the opposite corner. | |
195 | // • This algorithm terminates when either the X coordinates or the | |
196 | // Y coordinates of the forward and reverse frontier points ever intersect. | |
197 | // | |
198 | // This algorithm is correct even if searching only in the forward direction | |
199 | // or in the reverse direction. We do both because it is commonly observed | |
200 | // that two lists commonly differ because elements were added to the front | |
201 | // or end of the other list. | |
202 | // | |
863486a6 AG |
203 | // Running the tests with the "cmp_debug" build tag prints a visualization |
204 | // of the algorithm running in real-time. This is educational for | |
205 | // understanding how the algorithm works. See debug_enable.go. | |
107c1cdb ND |
206 | f = debug.Begin(nx, ny, f, &fwdPath.es, &revPath.es) |
207 | for { | |
208 | // Forward search from the beginning. | |
209 | if fwdFrontier.X >= revFrontier.X || fwdFrontier.Y >= revFrontier.Y || searchBudget == 0 { | |
210 | break | |
211 | } | |
212 | for stop1, stop2, i := false, false, 0; !(stop1 && stop2) && searchBudget > 0; i++ { | |
213 | // Search in a diagonal pattern for a match. | |
214 | z := zigzag(i) | |
215 | p := point{fwdFrontier.X + z, fwdFrontier.Y - z} | |
216 | switch { | |
217 | case p.X >= revPath.X || p.Y < fwdPath.Y: | |
218 | stop1 = true // Hit top-right corner | |
219 | case p.Y >= revPath.Y || p.X < fwdPath.X: | |
220 | stop2 = true // Hit bottom-left corner | |
221 | case f(p.X, p.Y).Equal(): | |
222 | // Match found, so connect the path to this point. | |
223 | fwdPath.connect(p, f) | |
224 | fwdPath.append(Identity) | |
225 | // Follow sequence of matches as far as possible. | |
226 | for fwdPath.X < revPath.X && fwdPath.Y < revPath.Y { | |
227 | if !f(fwdPath.X, fwdPath.Y).Equal() { | |
228 | break | |
229 | } | |
230 | fwdPath.append(Identity) | |
231 | } | |
232 | fwdFrontier = fwdPath.point | |
233 | stop1, stop2 = true, true | |
234 | default: | |
235 | searchBudget-- // Match not found | |
236 | } | |
237 | debug.Update() | |
238 | } | |
239 | // Advance the frontier towards reverse point. | |
240 | if revPath.X-fwdFrontier.X >= revPath.Y-fwdFrontier.Y { | |
241 | fwdFrontier.X++ | |
242 | } else { | |
243 | fwdFrontier.Y++ | |
244 | } | |
245 | ||
246 | // Reverse search from the end. | |
247 | if fwdFrontier.X >= revFrontier.X || fwdFrontier.Y >= revFrontier.Y || searchBudget == 0 { | |
248 | break | |
249 | } | |
250 | for stop1, stop2, i := false, false, 0; !(stop1 && stop2) && searchBudget > 0; i++ { | |
251 | // Search in a diagonal pattern for a match. | |
252 | z := zigzag(i) | |
253 | p := point{revFrontier.X - z, revFrontier.Y + z} | |
254 | switch { | |
255 | case fwdPath.X >= p.X || revPath.Y < p.Y: | |
256 | stop1 = true // Hit bottom-left corner | |
257 | case fwdPath.Y >= p.Y || revPath.X < p.X: | |
258 | stop2 = true // Hit top-right corner | |
259 | case f(p.X-1, p.Y-1).Equal(): | |
260 | // Match found, so connect the path to this point. | |
261 | revPath.connect(p, f) | |
262 | revPath.append(Identity) | |
263 | // Follow sequence of matches as far as possible. | |
264 | for fwdPath.X < revPath.X && fwdPath.Y < revPath.Y { | |
265 | if !f(revPath.X-1, revPath.Y-1).Equal() { | |
266 | break | |
267 | } | |
268 | revPath.append(Identity) | |
269 | } | |
270 | revFrontier = revPath.point | |
271 | stop1, stop2 = true, true | |
272 | default: | |
273 | searchBudget-- // Match not found | |
274 | } | |
275 | debug.Update() | |
276 | } | |
277 | // Advance the frontier towards forward point. | |
278 | if revFrontier.X-fwdPath.X >= revFrontier.Y-fwdPath.Y { | |
279 | revFrontier.X-- | |
280 | } else { | |
281 | revFrontier.Y-- | |
282 | } | |
283 | } | |
284 | ||
285 | // Join the forward and reverse paths and then append the reverse path. | |
286 | fwdPath.connect(revPath.point, f) | |
287 | for i := len(revPath.es) - 1; i >= 0; i-- { | |
288 | t := revPath.es[i] | |
289 | revPath.es = revPath.es[:i] | |
290 | fwdPath.append(t) | |
291 | } | |
292 | debug.Finish() | |
293 | return fwdPath.es | |
294 | } | |
295 | ||
296 | type path struct { | |
297 | dir int // +1 if forward, -1 if reverse | |
298 | point // Leading point of the EditScript path | |
299 | es EditScript | |
300 | } | |
301 | ||
302 | // connect appends any necessary Identity, Modified, UniqueX, or UniqueY types | |
303 | // to the edit-script to connect p.point to dst. | |
304 | func (p *path) connect(dst point, f EqualFunc) { | |
305 | if p.dir > 0 { | |
306 | // Connect in forward direction. | |
307 | for dst.X > p.X && dst.Y > p.Y { | |
308 | switch r := f(p.X, p.Y); { | |
309 | case r.Equal(): | |
310 | p.append(Identity) | |
311 | case r.Similar(): | |
312 | p.append(Modified) | |
313 | case dst.X-p.X >= dst.Y-p.Y: | |
314 | p.append(UniqueX) | |
315 | default: | |
316 | p.append(UniqueY) | |
317 | } | |
318 | } | |
319 | for dst.X > p.X { | |
320 | p.append(UniqueX) | |
321 | } | |
322 | for dst.Y > p.Y { | |
323 | p.append(UniqueY) | |
324 | } | |
325 | } else { | |
326 | // Connect in reverse direction. | |
327 | for p.X > dst.X && p.Y > dst.Y { | |
328 | switch r := f(p.X-1, p.Y-1); { | |
329 | case r.Equal(): | |
330 | p.append(Identity) | |
331 | case r.Similar(): | |
332 | p.append(Modified) | |
333 | case p.Y-dst.Y >= p.X-dst.X: | |
334 | p.append(UniqueY) | |
335 | default: | |
336 | p.append(UniqueX) | |
337 | } | |
338 | } | |
339 | for p.X > dst.X { | |
340 | p.append(UniqueX) | |
341 | } | |
342 | for p.Y > dst.Y { | |
343 | p.append(UniqueY) | |
344 | } | |
345 | } | |
346 | } | |
347 | ||
348 | func (p *path) append(t EditType) { | |
349 | p.es = append(p.es, t) | |
350 | switch t { | |
351 | case Identity, Modified: | |
352 | p.add(p.dir, p.dir) | |
353 | case UniqueX: | |
354 | p.add(p.dir, 0) | |
355 | case UniqueY: | |
356 | p.add(0, p.dir) | |
357 | } | |
358 | debug.Update() | |
359 | } | |
360 | ||
361 | type point struct{ X, Y int } | |
362 | ||
363 | func (p *point) add(dx, dy int) { p.X += dx; p.Y += dy } | |
364 | ||
365 | // zigzag maps a consecutive sequence of integers to a zig-zag sequence. | |
366 | // [0 1 2 3 4 5 ...] => [0 -1 +1 -2 +2 ...] | |
367 | func zigzag(x int) int { | |
368 | if x&1 != 0 { | |
369 | x = ^x | |
370 | } | |
371 | return x >> 1 | |
372 | } |