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