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