Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 1 | // Copyright 2017, The Go Authors. All rights reserved. |
| 2 | // Use of this source code is governed by a BSD-style |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame^] | 3 | // license that can be found in the LICENSE file. |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 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 | |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame^] | 15 | import ( |
| 16 | "math/rand" |
| 17 | "time" |
| 18 | |
| 19 | "github.com/google/go-cmp/cmp/internal/flags" |
| 20 | ) |
| 21 | |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 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. |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 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 | } |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 107 | |
| 108 | // Equal indicates whether the symbols are equal. Two symbols are equal |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 109 | // if and only if NumDiff == 0. If Equal, then they are also Similar. |
| 110 | func (r Result) Equal() bool { return r.NumDiff == 0 } |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 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 | // |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 116 | // The exact ratio of NumSame to NumDiff to determine similarity may change. |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 117 | func (r Result) Similar() bool { |
Pragya Arya | 324337e | 2020-02-20 14:35:08 +0530 | [diff] [blame] | 118 | // Use NumSame+1 to offset NumSame so that binary comparisons are similar. |
| 119 | return r.NumSame+1 >= r.NumDiff |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 120 | } |
| 121 | |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame^] | 122 | var randBool = rand.New(rand.NewSource(time.Now().Unix())).Intn(2) == 0 |
| 123 | |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 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 | // Unless, it is time for the algorithm to terminate. |
| 179 | fwdPath := path{+1, point{0, 0}, make(EditScript, 0, (nx+ny)/2)} |
| 180 | revPath := path{-1, point{nx, ny}, make(EditScript, 0)} |
| 181 | fwdFrontier := fwdPath.point // Forward search frontier |
| 182 | revFrontier := revPath.point // Reverse search frontier |
| 183 | |
| 184 | // Search budget bounds the cost of searching for better paths. |
| 185 | // The longest sequence of non-matching symbols that can be tolerated is |
| 186 | // approximately the square-root of the search budget. |
| 187 | searchBudget := 4 * (nx + ny) // O(n) |
| 188 | |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame^] | 189 | // Running the tests with the "cmp_debug" build tag prints a visualization |
| 190 | // of the algorithm running in real-time. This is educational for |
| 191 | // understanding how the algorithm works. See debug_enable.go. |
| 192 | f = debug.Begin(nx, ny, f, &fwdPath.es, &revPath.es) |
| 193 | |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 194 | // The algorithm below is a greedy, meet-in-the-middle algorithm for |
| 195 | // computing sub-optimal edit-scripts between two lists. |
| 196 | // |
| 197 | // The algorithm is approximately as follows: |
| 198 | // • Searching for differences switches back-and-forth between |
| 199 | // a search that starts at the beginning (the top-left corner), and |
| 200 | // a search that starts at the end (the bottom-right corner). The goal of |
| 201 | // the search is connect with the search from the opposite corner. |
| 202 | // • As we search, we build a path in a greedy manner, where the first |
| 203 | // match seen is added to the path (this is sub-optimal, but provides a |
| 204 | // decent result in practice). When matches are found, we try the next pair |
| 205 | // of symbols in the lists and follow all matches as far as possible. |
| 206 | // • When searching for matches, we search along a diagonal going through |
| 207 | // through the "frontier" point. If no matches are found, we advance the |
| 208 | // frontier towards the opposite corner. |
| 209 | // • This algorithm terminates when either the X coordinates or the |
| 210 | // Y coordinates of the forward and reverse frontier points ever intersect. |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame^] | 211 | |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 212 | // This algorithm is correct even if searching only in the forward direction |
| 213 | // or in the reverse direction. We do both because it is commonly observed |
| 214 | // that two lists commonly differ because elements were added to the front |
| 215 | // or end of the other list. |
| 216 | // |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame^] | 217 | // Non-deterministically start with either the forward or reverse direction |
| 218 | // to introduce some deliberate instability so that we have the flexibility |
| 219 | // to change this algorithm in the future. |
| 220 | if flags.Deterministic || randBool { |
| 221 | goto forwardSearch |
| 222 | } else { |
| 223 | goto reverseSearch |
| 224 | } |
| 225 | |
| 226 | forwardSearch: |
| 227 | { |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 228 | // Forward search from the beginning. |
| 229 | if fwdFrontier.X >= revFrontier.X || fwdFrontier.Y >= revFrontier.Y || searchBudget == 0 { |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame^] | 230 | goto finishSearch |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 231 | } |
| 232 | for stop1, stop2, i := false, false, 0; !(stop1 && stop2) && searchBudget > 0; i++ { |
| 233 | // Search in a diagonal pattern for a match. |
| 234 | z := zigzag(i) |
| 235 | p := point{fwdFrontier.X + z, fwdFrontier.Y - z} |
| 236 | switch { |
| 237 | case p.X >= revPath.X || p.Y < fwdPath.Y: |
| 238 | stop1 = true // Hit top-right corner |
| 239 | case p.Y >= revPath.Y || p.X < fwdPath.X: |
| 240 | stop2 = true // Hit bottom-left corner |
| 241 | case f(p.X, p.Y).Equal(): |
| 242 | // Match found, so connect the path to this point. |
| 243 | fwdPath.connect(p, f) |
| 244 | fwdPath.append(Identity) |
| 245 | // Follow sequence of matches as far as possible. |
| 246 | for fwdPath.X < revPath.X && fwdPath.Y < revPath.Y { |
| 247 | if !f(fwdPath.X, fwdPath.Y).Equal() { |
| 248 | break |
| 249 | } |
| 250 | fwdPath.append(Identity) |
| 251 | } |
| 252 | fwdFrontier = fwdPath.point |
| 253 | stop1, stop2 = true, true |
| 254 | default: |
| 255 | searchBudget-- // Match not found |
| 256 | } |
| 257 | debug.Update() |
| 258 | } |
| 259 | // Advance the frontier towards reverse point. |
| 260 | if revPath.X-fwdFrontier.X >= revPath.Y-fwdFrontier.Y { |
| 261 | fwdFrontier.X++ |
| 262 | } else { |
| 263 | fwdFrontier.Y++ |
| 264 | } |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame^] | 265 | goto reverseSearch |
| 266 | } |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 267 | |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame^] | 268 | reverseSearch: |
| 269 | { |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 270 | // Reverse search from the end. |
| 271 | if fwdFrontier.X >= revFrontier.X || fwdFrontier.Y >= revFrontier.Y || searchBudget == 0 { |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame^] | 272 | goto finishSearch |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 273 | } |
| 274 | for stop1, stop2, i := false, false, 0; !(stop1 && stop2) && searchBudget > 0; i++ { |
| 275 | // Search in a diagonal pattern for a match. |
| 276 | z := zigzag(i) |
| 277 | p := point{revFrontier.X - z, revFrontier.Y + z} |
| 278 | switch { |
| 279 | case fwdPath.X >= p.X || revPath.Y < p.Y: |
| 280 | stop1 = true // Hit bottom-left corner |
| 281 | case fwdPath.Y >= p.Y || revPath.X < p.X: |
| 282 | stop2 = true // Hit top-right corner |
| 283 | case f(p.X-1, p.Y-1).Equal(): |
| 284 | // Match found, so connect the path to this point. |
| 285 | revPath.connect(p, f) |
| 286 | revPath.append(Identity) |
| 287 | // Follow sequence of matches as far as possible. |
| 288 | for fwdPath.X < revPath.X && fwdPath.Y < revPath.Y { |
| 289 | if !f(revPath.X-1, revPath.Y-1).Equal() { |
| 290 | break |
| 291 | } |
| 292 | revPath.append(Identity) |
| 293 | } |
| 294 | revFrontier = revPath.point |
| 295 | stop1, stop2 = true, true |
| 296 | default: |
| 297 | searchBudget-- // Match not found |
| 298 | } |
| 299 | debug.Update() |
| 300 | } |
| 301 | // Advance the frontier towards forward point. |
| 302 | if revFrontier.X-fwdPath.X >= revFrontier.Y-fwdPath.Y { |
| 303 | revFrontier.X-- |
| 304 | } else { |
| 305 | revFrontier.Y-- |
| 306 | } |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame^] | 307 | goto forwardSearch |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 308 | } |
| 309 | |
David K. Bainbridge | c415efe | 2021-08-19 13:05:21 +0000 | [diff] [blame^] | 310 | finishSearch: |
Matteo Scandolo | a6a3aee | 2019-11-26 13:30:14 -0700 | [diff] [blame] | 311 | // Join the forward and reverse paths and then append the reverse path. |
| 312 | fwdPath.connect(revPath.point, f) |
| 313 | for i := len(revPath.es) - 1; i >= 0; i-- { |
| 314 | t := revPath.es[i] |
| 315 | revPath.es = revPath.es[:i] |
| 316 | fwdPath.append(t) |
| 317 | } |
| 318 | debug.Finish() |
| 319 | return fwdPath.es |
| 320 | } |
| 321 | |
| 322 | type path struct { |
| 323 | dir int // +1 if forward, -1 if reverse |
| 324 | point // Leading point of the EditScript path |
| 325 | es EditScript |
| 326 | } |
| 327 | |
| 328 | // connect appends any necessary Identity, Modified, UniqueX, or UniqueY types |
| 329 | // to the edit-script to connect p.point to dst. |
| 330 | func (p *path) connect(dst point, f EqualFunc) { |
| 331 | if p.dir > 0 { |
| 332 | // Connect in forward direction. |
| 333 | for dst.X > p.X && dst.Y > p.Y { |
| 334 | switch r := f(p.X, p.Y); { |
| 335 | case r.Equal(): |
| 336 | p.append(Identity) |
| 337 | case r.Similar(): |
| 338 | p.append(Modified) |
| 339 | case dst.X-p.X >= dst.Y-p.Y: |
| 340 | p.append(UniqueX) |
| 341 | default: |
| 342 | p.append(UniqueY) |
| 343 | } |
| 344 | } |
| 345 | for dst.X > p.X { |
| 346 | p.append(UniqueX) |
| 347 | } |
| 348 | for dst.Y > p.Y { |
| 349 | p.append(UniqueY) |
| 350 | } |
| 351 | } else { |
| 352 | // Connect in reverse direction. |
| 353 | for p.X > dst.X && p.Y > dst.Y { |
| 354 | switch r := f(p.X-1, p.Y-1); { |
| 355 | case r.Equal(): |
| 356 | p.append(Identity) |
| 357 | case r.Similar(): |
| 358 | p.append(Modified) |
| 359 | case p.Y-dst.Y >= p.X-dst.X: |
| 360 | p.append(UniqueY) |
| 361 | default: |
| 362 | p.append(UniqueX) |
| 363 | } |
| 364 | } |
| 365 | for p.X > dst.X { |
| 366 | p.append(UniqueX) |
| 367 | } |
| 368 | for p.Y > dst.Y { |
| 369 | p.append(UniqueY) |
| 370 | } |
| 371 | } |
| 372 | } |
| 373 | |
| 374 | func (p *path) append(t EditType) { |
| 375 | p.es = append(p.es, t) |
| 376 | switch t { |
| 377 | case Identity, Modified: |
| 378 | p.add(p.dir, p.dir) |
| 379 | case UniqueX: |
| 380 | p.add(p.dir, 0) |
| 381 | case UniqueY: |
| 382 | p.add(0, p.dir) |
| 383 | } |
| 384 | debug.Update() |
| 385 | } |
| 386 | |
| 387 | type point struct{ X, Y int } |
| 388 | |
| 389 | func (p *point) add(dx, dy int) { p.X += dx; p.Y += dy } |
| 390 | |
| 391 | // zigzag maps a consecutive sequence of integers to a zig-zag sequence. |
| 392 | // [0 1 2 3 4 5 ...] => [0 -1 +1 -2 +2 ...] |
| 393 | func zigzag(x int) int { |
| 394 | if x&1 != 0 { |
| 395 | x = ^x |
| 396 | } |
| 397 | return x >> 1 |
| 398 | } |