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.
13
package diff
14

15
import (
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.
23
type EditType uint8
24

25
const (
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.
37
type 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.
42
func (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.
62
func (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.
82
func (es EditScript) Dist() int { return len(es) - es.stats().NI }
83

84
// LenX is the length of the X list.
85
func (es EditScript) LenX() int { return len(es) - es.stats().NY }
86

87
// LenY is the length of the Y list.
88
func (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.
92
type 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.
97
type Result struct{ NumSame, NumDiff int }
98

99
// BoolResult returns a Result that is either Equal or not Equal.
100
func 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.
110
func (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.
117
func (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

122
var 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.
138
func 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

229
forwardSearch:
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

271
reverseSearch:
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

313
finishSearch:
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

325
type 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.
333
func (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

377
func (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

390
type point struct{ X, Y int }
391

392
func (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 ...]
397
func zigzag(x int) int {
398
	if x&1 != 0 {
399
		x = ^x
400
	}
401
	return x >> 1
402
}
403

404