1 /* 2 Package difflib is a partial port of Python difflib module. 3 4 Original source: https://github.com/pmezard/go-difflib 5 6 This file is trimmed to only the parts used by this repository. 7 */ 8 package difflib // import "gotest.tools/v3/internal/difflib" 9 10 func minInt(a, b int) int { 11 if a < b { 12 return a 13 } 14 return b 15 } 16 17 func maxInt(a, b int) int { 18 if a > b { 19 return a 20 } 21 return b 22 } 23 24 // Match stores line numbers of size of match 25 type Match struct { 26 A int 27 B int 28 Size int 29 } 30 31 // OpCode identifies the type of diff 32 type OpCode struct { 33 Tag byte 34 I1 int 35 I2 int 36 J1 int 37 J2 int 38 } 39 40 // SequenceMatcher compares sequence of strings. The basic 41 // algorithm predates, and is a little fancier than, an algorithm 42 // published in the late 1980's by Ratcliff and Obershelp under the 43 // hyperbolic name "gestalt pattern matching". The basic idea is to find 44 // the longest contiguous matching subsequence that contains no "junk" 45 // elements (R-O doesn't address junk). The same idea is then applied 46 // recursively to the pieces of the sequences to the left and to the right 47 // of the matching subsequence. This does not yield minimal edit 48 // sequences, but does tend to yield matches that "look right" to people. 49 // 50 // SequenceMatcher tries to compute a "human-friendly diff" between two 51 // sequences. Unlike e.g. UNIX(tm) diff, the fundamental notion is the 52 // longest *contiguous* & junk-free matching subsequence. That's what 53 // catches peoples' eyes. The Windows(tm) windiff has another interesting 54 // notion, pairing up elements that appear uniquely in each sequence. 55 // That, and the method here, appear to yield more intuitive difference 56 // reports than does diff. This method appears to be the least vulnerable 57 // to synching up on blocks of "junk lines", though (like blank lines in 58 // ordinary text files, or maybe "<P>" lines in HTML files). That may be 59 // because this is the only method of the 3 that has a *concept* of 60 // "junk" <wink>. 61 // 62 // Timing: Basic R-O is cubic time worst case and quadratic time expected 63 // case. SequenceMatcher is quadratic time for the worst case and has 64 // expected-case behavior dependent in a complicated way on how many 65 // elements the sequences have in common; best case time is linear. 66 type SequenceMatcher struct { 67 a []string 68 b []string 69 b2j map[string][]int 70 IsJunk func(string) bool 71 autoJunk bool 72 bJunk map[string]struct{} 73 matchingBlocks []Match 74 fullBCount map[string]int 75 bPopular map[string]struct{} 76 opCodes []OpCode 77 } 78 79 // NewMatcher returns a new SequenceMatcher 80 func NewMatcher(a, b []string) *SequenceMatcher { 81 m := SequenceMatcher{autoJunk: true} 82 m.SetSeqs(a, b) 83 return &m 84 } 85 86 // SetSeqs sets two sequences to be compared. 87 func (m *SequenceMatcher) SetSeqs(a, b []string) { 88 m.SetSeq1(a) 89 m.SetSeq2(b) 90 } 91 92 // SetSeq1 sets the first sequence to be compared. The second sequence to be compared is 93 // not changed. 94 // 95 // SequenceMatcher computes and caches detailed information about the second 96 // sequence, so if you want to compare one sequence S against many sequences, 97 // use .SetSeq2(s) once and call .SetSeq1(x) repeatedly for each of the other 98 // sequences. 99 // 100 // See also SetSeqs() and SetSeq2(). 101 func (m *SequenceMatcher) SetSeq1(a []string) { 102 if &a == &m.a { 103 return 104 } 105 m.a = a 106 m.matchingBlocks = nil 107 m.opCodes = nil 108 } 109 110 // SetSeq2 sets the second sequence to be compared. The first sequence to be compared is 111 // not changed. 112 func (m *SequenceMatcher) SetSeq2(b []string) { 113 if &b == &m.b { 114 return 115 } 116 m.b = b 117 m.matchingBlocks = nil 118 m.opCodes = nil 119 m.fullBCount = nil 120 m.chainB() 121 } 122 123 func (m *SequenceMatcher) chainB() { 124 // Populate line -> index mapping 125 b2j := map[string][]int{} 126 for i, s := range m.b { 127 indices := b2j[s] 128 indices = append(indices, i) 129 b2j[s] = indices 130 } 131 132 // Purge junk elements 133 m.bJunk = map[string]struct{}{} 134 if m.IsJunk != nil { 135 junk := m.bJunk 136 for s := range b2j { 137 if m.IsJunk(s) { 138 junk[s] = struct{}{} 139 } 140 } 141 for s := range junk { 142 delete(b2j, s) 143 } 144 } 145 146 // Purge remaining popular elements 147 popular := map[string]struct{}{} 148 n := len(m.b) 149 if m.autoJunk && n >= 200 { 150 ntest := n/100 + 1 151 for s, indices := range b2j { 152 if len(indices) > ntest { 153 popular[s] = struct{}{} 154 } 155 } 156 for s := range popular { 157 delete(b2j, s) 158 } 159 } 160 m.bPopular = popular 161 m.b2j = b2j 162 } 163 164 func (m *SequenceMatcher) isBJunk(s string) bool { 165 _, ok := m.bJunk[s] 166 return ok 167 } 168 169 // Find longest matching block in a[alo:ahi] and b[blo:bhi]. 170 // 171 // If IsJunk is not defined: 172 // 173 // Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where 174 // 175 // alo <= i <= i+k <= ahi 176 // blo <= j <= j+k <= bhi 177 // 178 // and for all (i',j',k') meeting those conditions, 179 // 180 // k >= k' 181 // i <= i' 182 // and if i == i', j <= j' 183 // 184 // In other words, of all maximal matching blocks, return one that 185 // starts earliest in a, and of all those maximal matching blocks that 186 // start earliest in a, return the one that starts earliest in b. 187 // 188 // If IsJunk is defined, first the longest matching block is 189 // determined as above, but with the additional restriction that no 190 // junk element appears in the block. Then that block is extended as 191 // far as possible by matching (only) junk elements on both sides. So 192 // the resulting block never matches on junk except as identical junk 193 // happens to be adjacent to an "interesting" match. 194 // 195 // If no blocks match, return (alo, blo, 0). 196 func (m *SequenceMatcher) findLongestMatch(alo, ahi, blo, bhi int) Match { 197 // CAUTION: stripping common prefix or suffix would be incorrect. 198 // E.g., 199 // ab 200 // acab 201 // Longest matching block is "ab", but if common prefix is 202 // stripped, it's "a" (tied with "b"). UNIX(tm) diff does so 203 // strip, so ends up claiming that ab is changed to acab by 204 // inserting "ca" in the middle. That's minimal but unintuitive: 205 // "it's obvious" that someone inserted "ac" at the front. 206 // Windiff ends up at the same place as diff, but by pairing up 207 // the unique 'b's and then matching the first two 'a's. 208 besti, bestj, bestsize := alo, blo, 0 209 210 // find longest junk-free match 211 // during an iteration of the loop, j2len[j] = length of longest 212 // junk-free match ending with a[i-1] and b[j] 213 j2len := map[int]int{} 214 for i := alo; i != ahi; i++ { 215 // look at all instances of a[i] in b; note that because 216 // b2j has no junk keys, the loop is skipped if a[i] is junk 217 newj2len := map[int]int{} 218 for _, j := range m.b2j[m.a[i]] { 219 // a[i] matches b[j] 220 if j < blo { 221 continue 222 } 223 if j >= bhi { 224 break 225 } 226 k := j2len[j-1] + 1 227 newj2len[j] = k 228 if k > bestsize { 229 besti, bestj, bestsize = i-k+1, j-k+1, k 230 } 231 } 232 j2len = newj2len 233 } 234 235 // Extend the best by non-junk elements on each end. In particular, 236 // "popular" non-junk elements aren't in b2j, which greatly speeds 237 // the inner loop above, but also means "the best" match so far 238 // doesn't contain any junk *or* popular non-junk elements. 239 for besti > alo && bestj > blo && !m.isBJunk(m.b[bestj-1]) && 240 m.a[besti-1] == m.b[bestj-1] { 241 besti, bestj, bestsize = besti-1, bestj-1, bestsize+1 242 } 243 for besti+bestsize < ahi && bestj+bestsize < bhi && 244 !m.isBJunk(m.b[bestj+bestsize]) && 245 m.a[besti+bestsize] == m.b[bestj+bestsize] { 246 bestsize += 1 247 } 248 249 // Now that we have a wholly interesting match (albeit possibly 250 // empty!), we may as well suck up the matching junk on each 251 // side of it too. Can't think of a good reason not to, and it 252 // saves post-processing the (possibly considerable) expense of 253 // figuring out what to do with it. In the case of an empty 254 // interesting match, this is clearly the right thing to do, 255 // because no other kind of match is possible in the regions. 256 for besti > alo && bestj > blo && m.isBJunk(m.b[bestj-1]) && 257 m.a[besti-1] == m.b[bestj-1] { 258 besti, bestj, bestsize = besti-1, bestj-1, bestsize+1 259 } 260 for besti+bestsize < ahi && bestj+bestsize < bhi && 261 m.isBJunk(m.b[bestj+bestsize]) && 262 m.a[besti+bestsize] == m.b[bestj+bestsize] { 263 bestsize += 1 264 } 265 266 return Match{A: besti, B: bestj, Size: bestsize} 267 } 268 269 // GetMatchingBlocks returns a list of triples describing matching subsequences. 270 // 271 // Each triple is of the form (i, j, n), and means that 272 // a[i:i+n] == b[j:j+n]. The triples are monotonically increasing in 273 // i and in j. It's also guaranteed that if (i, j, n) and (i', j', n') are 274 // adjacent triples in the list, and the second is not the last triple in the 275 // list, then i+n != i' or j+n != j'. IOW, adjacent triples never describe 276 // adjacent equal blocks. 277 // 278 // The last triple is a dummy, (len(a), len(b), 0), and is the only 279 // triple with n==0. 280 func (m *SequenceMatcher) GetMatchingBlocks() []Match { 281 if m.matchingBlocks != nil { 282 return m.matchingBlocks 283 } 284 285 var matchBlocks func(alo, ahi, blo, bhi int, matched []Match) []Match 286 matchBlocks = func(alo, ahi, blo, bhi int, matched []Match) []Match { 287 match := m.findLongestMatch(alo, ahi, blo, bhi) 288 i, j, k := match.A, match.B, match.Size 289 if match.Size > 0 { 290 if alo < i && blo < j { 291 matched = matchBlocks(alo, i, blo, j, matched) 292 } 293 matched = append(matched, match) 294 if i+k < ahi && j+k < bhi { 295 matched = matchBlocks(i+k, ahi, j+k, bhi, matched) 296 } 297 } 298 return matched 299 } 300 matched := matchBlocks(0, len(m.a), 0, len(m.b), nil) 301 302 // It's possible that we have adjacent equal blocks in the 303 // matching_blocks list now. 304 nonAdjacent := []Match{} 305 i1, j1, k1 := 0, 0, 0 306 for _, b := range matched { 307 // Is this block adjacent to i1, j1, k1? 308 i2, j2, k2 := b.A, b.B, b.Size 309 if i1+k1 == i2 && j1+k1 == j2 { 310 // Yes, so collapse them -- this just increases the length of 311 // the first block by the length of the second, and the first 312 // block so lengthened remains the block to compare against. 313 k1 += k2 314 } else { 315 // Not adjacent. Remember the first block (k1==0 means it's 316 // the dummy we started with), and make the second block the 317 // new block to compare against. 318 if k1 > 0 { 319 nonAdjacent = append(nonAdjacent, Match{i1, j1, k1}) 320 } 321 i1, j1, k1 = i2, j2, k2 322 } 323 } 324 if k1 > 0 { 325 nonAdjacent = append(nonAdjacent, Match{i1, j1, k1}) 326 } 327 328 nonAdjacent = append(nonAdjacent, Match{len(m.a), len(m.b), 0}) 329 m.matchingBlocks = nonAdjacent 330 return m.matchingBlocks 331 } 332 333 // GetOpCodes returns a list of 5-tuples describing how to turn a into b. 334 // 335 // Each tuple is of the form (tag, i1, i2, j1, j2). The first tuple 336 // has i1 == j1 == 0, and remaining tuples have i1 == the i2 from the 337 // tuple preceding it, and likewise for j1 == the previous j2. 338 // 339 // The tags are characters, with these meanings: 340 // 341 // 'r' (replace): a[i1:i2] should be replaced by b[j1:j2] 342 // 343 // 'd' (delete): a[i1:i2] should be deleted, j1==j2 in this case. 344 // 345 // 'i' (insert): b[j1:j2] should be inserted at a[i1:i1], i1==i2 in this case. 346 // 347 // 'e' (equal): a[i1:i2] == b[j1:j2] 348 func (m *SequenceMatcher) GetOpCodes() []OpCode { 349 if m.opCodes != nil { 350 return m.opCodes 351 } 352 i, j := 0, 0 353 matching := m.GetMatchingBlocks() 354 opCodes := make([]OpCode, 0, len(matching)) 355 for _, m := range matching { 356 // invariant: we've pumped out correct diffs to change 357 // a[:i] into b[:j], and the next matching block is 358 // a[ai:ai+size] == b[bj:bj+size]. So we need to pump 359 // out a diff to change a[i:ai] into b[j:bj], pump out 360 // the matching block, and move (i,j) beyond the match 361 ai, bj, size := m.A, m.B, m.Size 362 tag := byte(0) 363 if i < ai && j < bj { 364 tag = 'r' 365 } else if i < ai { 366 tag = 'd' 367 } else if j < bj { 368 tag = 'i' 369 } 370 if tag > 0 { 371 opCodes = append(opCodes, OpCode{tag, i, ai, j, bj}) 372 } 373 i, j = ai+size, bj+size 374 // the list of matching blocks is terminated by a 375 // sentinel with size 0 376 if size > 0 { 377 opCodes = append(opCodes, OpCode{'e', ai, i, bj, j}) 378 } 379 } 380 m.opCodes = opCodes 381 return m.opCodes 382 } 383 384 // GetGroupedOpCodes isolates change clusters by eliminating ranges with no changes. 385 // 386 // Return a generator of groups with up to n lines of context. 387 // Each group is in the same format as returned by GetOpCodes(). 388 func (m *SequenceMatcher) GetGroupedOpCodes(n int) [][]OpCode { 389 if n < 0 { 390 n = 3 391 } 392 codes := m.GetOpCodes() 393 if len(codes) == 0 { 394 codes = []OpCode{{'e', 0, 1, 0, 1}} 395 } 396 // Fixup leading and trailing groups if they show no changes. 397 if codes[0].Tag == 'e' { 398 c := codes[0] 399 i1, i2, j1, j2 := c.I1, c.I2, c.J1, c.J2 400 codes[0] = OpCode{c.Tag, maxInt(i1, i2-n), i2, maxInt(j1, j2-n), j2} 401 } 402 if codes[len(codes)-1].Tag == 'e' { 403 c := codes[len(codes)-1] 404 i1, i2, j1, j2 := c.I1, c.I2, c.J1, c.J2 405 codes[len(codes)-1] = OpCode{c.Tag, i1, minInt(i2, i1+n), j1, minInt(j2, j1+n)} 406 } 407 nn := n + n 408 groups := [][]OpCode{} 409 group := []OpCode{} 410 for _, c := range codes { 411 i1, i2, j1, j2 := c.I1, c.I2, c.J1, c.J2 412 // End the current group and start a new one whenever 413 // there is a large range with no changes. 414 if c.Tag == 'e' && i2-i1 > nn { 415 group = append(group, OpCode{c.Tag, i1, minInt(i2, i1+n), 416 j1, minInt(j2, j1+n)}) 417 groups = append(groups, group) 418 group = []OpCode{} 419 i1, j1 = maxInt(i1, i2-n), maxInt(j1, j2-n) 420 } 421 group = append(group, OpCode{c.Tag, i1, i2, j1, j2}) 422 } 423 if len(group) > 0 && !(len(group) == 1 && group[0].Tag == 'e') { 424 groups = append(groups, group) 425 } 426 return groups 427 } 428