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. 13package diff 14 15// EditType represents a single operation within an edit-script. 16type EditType uint8 17 18const ( 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. 30type 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. 35func (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. 55func (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. 75func (es EditScript) Dist() int { return len(es) - es.stats().NI } 76 77// LenX is the length of the X list. 78func (es EditScript) LenX() int { return len(es) - es.stats().NY } 79 80// LenY is the length of the Y list. 81func (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. 85type EqualFunc func(ix int, iy int) Result 86 87// Result is the result of comparison. 88// NumSame is the number of sub-elements that are equal. 89// NumDiff is the number of sub-elements that are not equal. 90type Result struct{ NumSame, NumDiff int } 91 92// BoolResult returns a Result that is either Equal or not Equal. 93func 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} 100 101// Equal indicates whether the symbols are equal. Two symbols are equal 102// if and only if NumDiff == 0. If Equal, then they are also Similar. 103func (r Result) Equal() bool { return r.NumDiff == 0 } 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// 109// The exact ratio of NumSame to NumDiff to determine similarity may change. 110func (r Result) Similar() bool { 111 // Use NumSame+1 to offset NumSame so that binary comparisons are similar. 112 return r.NumSame+1 >= r.NumDiff 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. 129func 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 // 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. 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 296type 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. 304func (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 348func (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 361type point struct{ X, Y int } 362 363func (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 ...] 367func zigzag(x int) int { 368 if x&1 != 0 { 369 x = ^x 370 } 371 return x >> 1 372} 373