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