diff.go 13 KB

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