blob: b6f486b9c90ea1ca6f47c0a7a9e3697f20deb308 [file] [log] [blame]
Matteo Scandoloabf872d2020-12-14 08:22:06 -10001/*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}