blob: 198114d987aac453f25ace1006cf71dc31396b96 [file] [log] [blame]
Tim Peters9ae21482001-02-10 08:00:53 +00001#! /usr/bin/env python
2
3"""
4Module difflib -- helpers for computing deltas between objects.
5
6Function get_close_matches(word, possibilities, n=3, cutoff=0.6):
Tim Peters9ae21482001-02-10 08:00:53 +00007 Use SequenceMatcher to return list of the best "good enough" matches.
8
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00009Function context_diff(a, b):
10 For two lists of strings, return a delta in context diff format.
11
Tim Peters5e824c32001-08-12 22:25:01 +000012Function ndiff(a, b):
13 Return a delta: the difference between `a` and `b` (lists of strings).
Tim Peters9ae21482001-02-10 08:00:53 +000014
Tim Peters5e824c32001-08-12 22:25:01 +000015Function restore(delta, which):
16 Return one of the two sequences that generated an ndiff delta.
Tim Peters9ae21482001-02-10 08:00:53 +000017
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +000018Function unified_diff(a, b):
19 For two lists of strings, return a delta in unified diff format.
20
Tim Peters5e824c32001-08-12 22:25:01 +000021Class SequenceMatcher:
22 A flexible class for comparing pairs of sequences of any type.
Tim Peters9ae21482001-02-10 08:00:53 +000023
Tim Peters5e824c32001-08-12 22:25:01 +000024Class Differ:
25 For producing human-readable deltas from sequences of lines of text.
Tim Peters9ae21482001-02-10 08:00:53 +000026"""
27
Tim Peters5e824c32001-08-12 22:25:01 +000028__all__ = ['get_close_matches', 'ndiff', 'restore', 'SequenceMatcher',
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +000029 'Differ','IS_CHARACTER_JUNK', 'IS_LINE_JUNK', 'context_diff',
30 'unified_diff']
Tim Peters5e824c32001-08-12 22:25:01 +000031
Tim Peters9ae21482001-02-10 08:00:53 +000032class SequenceMatcher:
Tim Peters5e824c32001-08-12 22:25:01 +000033
34 """
35 SequenceMatcher is a flexible class for comparing pairs of sequences of
36 any type, so long as the sequence elements are hashable. The basic
37 algorithm predates, and is a little fancier than, an algorithm
38 published in the late 1980's by Ratcliff and Obershelp under the
39 hyperbolic name "gestalt pattern matching". The basic idea is to find
40 the longest contiguous matching subsequence that contains no "junk"
41 elements (R-O doesn't address junk). The same idea is then applied
42 recursively to the pieces of the sequences to the left and to the right
43 of the matching subsequence. This does not yield minimal edit
44 sequences, but does tend to yield matches that "look right" to people.
45
46 SequenceMatcher tries to compute a "human-friendly diff" between two
47 sequences. Unlike e.g. UNIX(tm) diff, the fundamental notion is the
48 longest *contiguous* & junk-free matching subsequence. That's what
49 catches peoples' eyes. The Windows(tm) windiff has another interesting
50 notion, pairing up elements that appear uniquely in each sequence.
51 That, and the method here, appear to yield more intuitive difference
52 reports than does diff. This method appears to be the least vulnerable
53 to synching up on blocks of "junk lines", though (like blank lines in
54 ordinary text files, or maybe "<P>" lines in HTML files). That may be
55 because this is the only method of the 3 that has a *concept* of
56 "junk" <wink>.
57
58 Example, comparing two strings, and considering blanks to be "junk":
59
60 >>> s = SequenceMatcher(lambda x: x == " ",
61 ... "private Thread currentThread;",
62 ... "private volatile Thread currentThread;")
63 >>>
64
65 .ratio() returns a float in [0, 1], measuring the "similarity" of the
66 sequences. As a rule of thumb, a .ratio() value over 0.6 means the
67 sequences are close matches:
68
69 >>> print round(s.ratio(), 3)
70 0.866
71 >>>
72
73 If you're only interested in where the sequences match,
74 .get_matching_blocks() is handy:
75
76 >>> for block in s.get_matching_blocks():
77 ... print "a[%d] and b[%d] match for %d elements" % block
78 a[0] and b[0] match for 8 elements
79 a[8] and b[17] match for 6 elements
80 a[14] and b[23] match for 15 elements
81 a[29] and b[38] match for 0 elements
82
83 Note that the last tuple returned by .get_matching_blocks() is always a
84 dummy, (len(a), len(b), 0), and this is the only case in which the last
85 tuple element (number of elements matched) is 0.
86
87 If you want to know how to change the first sequence into the second,
88 use .get_opcodes():
89
90 >>> for opcode in s.get_opcodes():
91 ... print "%6s a[%d:%d] b[%d:%d]" % opcode
92 equal a[0:8] b[0:8]
93 insert a[8:8] b[8:17]
94 equal a[8:14] b[17:23]
95 equal a[14:29] b[23:38]
96
97 See the Differ class for a fancy human-friendly file differencer, which
98 uses SequenceMatcher both to compare sequences of lines, and to compare
99 sequences of characters within similar (near-matching) lines.
100
101 See also function get_close_matches() in this module, which shows how
102 simple code building on SequenceMatcher can be used to do useful work.
103
104 Timing: Basic R-O is cubic time worst case and quadratic time expected
105 case. SequenceMatcher is quadratic time for the worst case and has
106 expected-case behavior dependent in a complicated way on how many
107 elements the sequences have in common; best case time is linear.
108
109 Methods:
110
111 __init__(isjunk=None, a='', b='')
112 Construct a SequenceMatcher.
113
114 set_seqs(a, b)
115 Set the two sequences to be compared.
116
117 set_seq1(a)
118 Set the first sequence to be compared.
119
120 set_seq2(b)
121 Set the second sequence to be compared.
122
123 find_longest_match(alo, ahi, blo, bhi)
124 Find longest matching block in a[alo:ahi] and b[blo:bhi].
125
126 get_matching_blocks()
127 Return list of triples describing matching subsequences.
128
129 get_opcodes()
130 Return list of 5-tuples describing how to turn a into b.
131
132 ratio()
133 Return a measure of the sequences' similarity (float in [0,1]).
134
135 quick_ratio()
136 Return an upper bound on .ratio() relatively quickly.
137
138 real_quick_ratio()
139 Return an upper bound on ratio() very quickly.
140 """
141
Tim Peters9ae21482001-02-10 08:00:53 +0000142 def __init__(self, isjunk=None, a='', b=''):
143 """Construct a SequenceMatcher.
144
145 Optional arg isjunk is None (the default), or a one-argument
146 function that takes a sequence element and returns true iff the
Tim Peters5e824c32001-08-12 22:25:01 +0000147 element is junk. None is equivalent to passing "lambda x: 0", i.e.
Fred Drakef1da6282001-02-19 19:30:05 +0000148 no elements are considered to be junk. For example, pass
Tim Peters9ae21482001-02-10 08:00:53 +0000149 lambda x: x in " \\t"
150 if you're comparing lines as sequences of characters, and don't
151 want to synch up on blanks or hard tabs.
152
153 Optional arg a is the first of two sequences to be compared. By
154 default, an empty string. The elements of a must be hashable. See
155 also .set_seqs() and .set_seq1().
156
157 Optional arg b is the second of two sequences to be compared. By
Fred Drakef1da6282001-02-19 19:30:05 +0000158 default, an empty string. The elements of b must be hashable. See
Tim Peters9ae21482001-02-10 08:00:53 +0000159 also .set_seqs() and .set_seq2().
160 """
161
162 # Members:
163 # a
164 # first sequence
165 # b
166 # second sequence; differences are computed as "what do
167 # we need to do to 'a' to change it into 'b'?"
168 # b2j
169 # for x in b, b2j[x] is a list of the indices (into b)
170 # at which x appears; junk elements do not appear
Tim Peters9ae21482001-02-10 08:00:53 +0000171 # fullbcount
172 # for x in b, fullbcount[x] == the number of times x
173 # appears in b; only materialized if really needed (used
174 # only for computing quick_ratio())
175 # matching_blocks
176 # a list of (i, j, k) triples, where a[i:i+k] == b[j:j+k];
177 # ascending & non-overlapping in i and in j; terminated by
178 # a dummy (len(a), len(b), 0) sentinel
179 # opcodes
180 # a list of (tag, i1, i2, j1, j2) tuples, where tag is
181 # one of
182 # 'replace' a[i1:i2] should be replaced by b[j1:j2]
183 # 'delete' a[i1:i2] should be deleted
184 # 'insert' b[j1:j2] should be inserted
185 # 'equal' a[i1:i2] == b[j1:j2]
186 # isjunk
187 # a user-supplied function taking a sequence element and
188 # returning true iff the element is "junk" -- this has
189 # subtle but helpful effects on the algorithm, which I'll
190 # get around to writing up someday <0.9 wink>.
191 # DON'T USE! Only __chain_b uses this. Use isbjunk.
192 # isbjunk
193 # for x in b, isbjunk(x) == isjunk(x) but much faster;
194 # it's really the has_key method of a hidden dict.
195 # DOES NOT WORK for x in a!
Tim Peters81b92512002-04-29 01:37:32 +0000196 # isbpopular
197 # for x in b, isbpopular(x) is true iff b is reasonably long
198 # (at least 200 elements) and x accounts for more than 1% of
199 # its elements. DOES NOT WORK for x in a!
Tim Peters9ae21482001-02-10 08:00:53 +0000200
201 self.isjunk = isjunk
202 self.a = self.b = None
203 self.set_seqs(a, b)
204
205 def set_seqs(self, a, b):
206 """Set the two sequences to be compared.
207
208 >>> s = SequenceMatcher()
209 >>> s.set_seqs("abcd", "bcde")
210 >>> s.ratio()
211 0.75
212 """
213
214 self.set_seq1(a)
215 self.set_seq2(b)
216
217 def set_seq1(self, a):
218 """Set the first sequence to be compared.
219
220 The second sequence to be compared is not changed.
221
222 >>> s = SequenceMatcher(None, "abcd", "bcde")
223 >>> s.ratio()
224 0.75
225 >>> s.set_seq1("bcde")
226 >>> s.ratio()
227 1.0
228 >>>
229
230 SequenceMatcher computes and caches detailed information about the
231 second sequence, so if you want to compare one sequence S against
232 many sequences, use .set_seq2(S) once and call .set_seq1(x)
233 repeatedly for each of the other sequences.
234
235 See also set_seqs() and set_seq2().
236 """
237
238 if a is self.a:
239 return
240 self.a = a
241 self.matching_blocks = self.opcodes = None
242
243 def set_seq2(self, b):
244 """Set the second sequence to be compared.
245
246 The first sequence to be compared is not changed.
247
248 >>> s = SequenceMatcher(None, "abcd", "bcde")
249 >>> s.ratio()
250 0.75
251 >>> s.set_seq2("abcd")
252 >>> s.ratio()
253 1.0
254 >>>
255
256 SequenceMatcher computes and caches detailed information about the
257 second sequence, so if you want to compare one sequence S against
258 many sequences, use .set_seq2(S) once and call .set_seq1(x)
259 repeatedly for each of the other sequences.
260
261 See also set_seqs() and set_seq1().
262 """
263
264 if b is self.b:
265 return
266 self.b = b
267 self.matching_blocks = self.opcodes = None
268 self.fullbcount = None
269 self.__chain_b()
270
271 # For each element x in b, set b2j[x] to a list of the indices in
272 # b where x appears; the indices are in increasing order; note that
273 # the number of times x appears in b is len(b2j[x]) ...
274 # when self.isjunk is defined, junk elements don't show up in this
275 # map at all, which stops the central find_longest_match method
276 # from starting any matching block at a junk element ...
277 # also creates the fast isbjunk function ...
Tim Peters81b92512002-04-29 01:37:32 +0000278 # b2j also does not contain entries for "popular" elements, meaning
279 # elements that account for more than 1% of the total elements, and
280 # when the sequence is reasonably large (>= 200 elements); this can
281 # be viewed as an adaptive notion of semi-junk, and yields an enormous
282 # speedup when, e.g., comparing program files with hundreds of
283 # instances of "return NULL;" ...
Tim Peters9ae21482001-02-10 08:00:53 +0000284 # note that this is only called when b changes; so for cross-product
285 # kinds of matches, it's best to call set_seq2 once, then set_seq1
286 # repeatedly
287
288 def __chain_b(self):
289 # Because isjunk is a user-defined (not C) function, and we test
290 # for junk a LOT, it's important to minimize the number of calls.
291 # Before the tricks described here, __chain_b was by far the most
292 # time-consuming routine in the whole module! If anyone sees
293 # Jim Roskind, thank him again for profile.py -- I never would
294 # have guessed that.
295 # The first trick is to build b2j ignoring the possibility
296 # of junk. I.e., we don't call isjunk at all yet. Throwing
297 # out the junk later is much cheaper than building b2j "right"
298 # from the start.
299 b = self.b
Tim Peters81b92512002-04-29 01:37:32 +0000300 n = len(b)
Tim Peters9ae21482001-02-10 08:00:53 +0000301 self.b2j = b2j = {}
Tim Peters81b92512002-04-29 01:37:32 +0000302 populardict = {}
303 for i, elt in enumerate(b):
304 if elt in b2j:
305 indices = b2j[elt]
306 if n >= 200 and len(indices) * 100 > n:
307 populardict[elt] = 1
308 del indices[:]
309 else:
310 indices.append(i)
Tim Peters9ae21482001-02-10 08:00:53 +0000311 else:
312 b2j[elt] = [i]
313
Tim Peters81b92512002-04-29 01:37:32 +0000314 # Purge leftover indices for popular elements.
315 for elt in populardict:
316 del b2j[elt]
317
Tim Peters9ae21482001-02-10 08:00:53 +0000318 # Now b2j.keys() contains elements uniquely, and especially when
319 # the sequence is a string, that's usually a good deal smaller
320 # than len(string). The difference is the number of isjunk calls
321 # saved.
Tim Peters81b92512002-04-29 01:37:32 +0000322 isjunk = self.isjunk
323 junkdict = {}
Tim Peters9ae21482001-02-10 08:00:53 +0000324 if isjunk:
Tim Peters81b92512002-04-29 01:37:32 +0000325 for d in populardict, b2j:
326 for elt in d.keys():
327 if isjunk(elt):
328 junkdict[elt] = 1
329 del d[elt]
Tim Peters9ae21482001-02-10 08:00:53 +0000330
Raymond Hettinger54f02222002-06-01 14:18:47 +0000331 # Now for x in b, isjunk(x) == x in junkdict, but the
Tim Peters9ae21482001-02-10 08:00:53 +0000332 # latter is much faster. Note too that while there may be a
333 # lot of junk in the sequence, the number of *unique* junk
334 # elements is probably small. So the memory burden of keeping
335 # this dict alive is likely trivial compared to the size of b2j.
336 self.isbjunk = junkdict.has_key
Tim Peters81b92512002-04-29 01:37:32 +0000337 self.isbpopular = populardict.has_key
Tim Peters9ae21482001-02-10 08:00:53 +0000338
339 def find_longest_match(self, alo, ahi, blo, bhi):
340 """Find longest matching block in a[alo:ahi] and b[blo:bhi].
341
342 If isjunk is not defined:
343
344 Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
345 alo <= i <= i+k <= ahi
346 blo <= j <= j+k <= bhi
347 and for all (i',j',k') meeting those conditions,
348 k >= k'
349 i <= i'
350 and if i == i', j <= j'
351
352 In other words, of all maximal matching blocks, return one that
353 starts earliest in a, and of all those maximal matching blocks that
354 start earliest in a, return the one that starts earliest in b.
355
356 >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
357 >>> s.find_longest_match(0, 5, 0, 9)
358 (0, 4, 5)
359
360 If isjunk is defined, first the longest matching block is
361 determined as above, but with the additional restriction that no
362 junk element appears in the block. Then that block is extended as
363 far as possible by matching (only) junk elements on both sides. So
364 the resulting block never matches on junk except as identical junk
365 happens to be adjacent to an "interesting" match.
366
367 Here's the same example as before, but considering blanks to be
368 junk. That prevents " abcd" from matching the " abcd" at the tail
369 end of the second sequence directly. Instead only the "abcd" can
370 match, and matches the leftmost "abcd" in the second sequence:
371
372 >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
373 >>> s.find_longest_match(0, 5, 0, 9)
374 (1, 0, 4)
375
376 If no blocks match, return (alo, blo, 0).
377
378 >>> s = SequenceMatcher(None, "ab", "c")
379 >>> s.find_longest_match(0, 2, 0, 1)
380 (0, 0, 0)
381 """
382
383 # CAUTION: stripping common prefix or suffix would be incorrect.
384 # E.g.,
385 # ab
386 # acab
387 # Longest matching block is "ab", but if common prefix is
388 # stripped, it's "a" (tied with "b"). UNIX(tm) diff does so
389 # strip, so ends up claiming that ab is changed to acab by
390 # inserting "ca" in the middle. That's minimal but unintuitive:
391 # "it's obvious" that someone inserted "ac" at the front.
392 # Windiff ends up at the same place as diff, but by pairing up
393 # the unique 'b's and then matching the first two 'a's.
394
395 a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.isbjunk
396 besti, bestj, bestsize = alo, blo, 0
397 # find longest junk-free match
398 # during an iteration of the loop, j2len[j] = length of longest
399 # junk-free match ending with a[i-1] and b[j]
400 j2len = {}
401 nothing = []
402 for i in xrange(alo, ahi):
403 # look at all instances of a[i] in b; note that because
404 # b2j has no junk keys, the loop is skipped if a[i] is junk
405 j2lenget = j2len.get
406 newj2len = {}
407 for j in b2j.get(a[i], nothing):
408 # a[i] matches b[j]
409 if j < blo:
410 continue
411 if j >= bhi:
412 break
413 k = newj2len[j] = j2lenget(j-1, 0) + 1
414 if k > bestsize:
415 besti, bestj, bestsize = i-k+1, j-k+1, k
416 j2len = newj2len
417
Tim Peters81b92512002-04-29 01:37:32 +0000418 # Extend the best by non-junk elements on each end. In particular,
419 # "popular" non-junk elements aren't in b2j, which greatly speeds
420 # the inner loop above, but also means "the best" match so far
421 # doesn't contain any junk *or* popular non-junk elements.
422 while besti > alo and bestj > blo and \
423 not isbjunk(b[bestj-1]) and \
424 a[besti-1] == b[bestj-1]:
425 besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
426 while besti+bestsize < ahi and bestj+bestsize < bhi and \
427 not isbjunk(b[bestj+bestsize]) and \
428 a[besti+bestsize] == b[bestj+bestsize]:
429 bestsize += 1
430
Tim Peters9ae21482001-02-10 08:00:53 +0000431 # Now that we have a wholly interesting match (albeit possibly
432 # empty!), we may as well suck up the matching junk on each
433 # side of it too. Can't think of a good reason not to, and it
434 # saves post-processing the (possibly considerable) expense of
435 # figuring out what to do with it. In the case of an empty
436 # interesting match, this is clearly the right thing to do,
437 # because no other kind of match is possible in the regions.
438 while besti > alo and bestj > blo and \
439 isbjunk(b[bestj-1]) and \
440 a[besti-1] == b[bestj-1]:
441 besti, bestj, bestsize = besti-1, bestj-1, bestsize+1
442 while besti+bestsize < ahi and bestj+bestsize < bhi and \
443 isbjunk(b[bestj+bestsize]) and \
444 a[besti+bestsize] == b[bestj+bestsize]:
445 bestsize = bestsize + 1
446
Tim Peters9ae21482001-02-10 08:00:53 +0000447 return besti, bestj, bestsize
448
449 def get_matching_blocks(self):
450 """Return list of triples describing matching subsequences.
451
452 Each triple is of the form (i, j, n), and means that
453 a[i:i+n] == b[j:j+n]. The triples are monotonically increasing in
454 i and in j.
455
456 The last triple is a dummy, (len(a), len(b), 0), and is the only
457 triple with n==0.
458
459 >>> s = SequenceMatcher(None, "abxcd", "abcd")
460 >>> s.get_matching_blocks()
461 [(0, 0, 2), (3, 2, 2), (5, 4, 0)]
462 """
463
464 if self.matching_blocks is not None:
465 return self.matching_blocks
466 self.matching_blocks = []
467 la, lb = len(self.a), len(self.b)
468 self.__helper(0, la, 0, lb, self.matching_blocks)
469 self.matching_blocks.append( (la, lb, 0) )
Tim Peters9ae21482001-02-10 08:00:53 +0000470 return self.matching_blocks
471
472 # builds list of matching blocks covering a[alo:ahi] and
473 # b[blo:bhi], appending them in increasing order to answer
474
475 def __helper(self, alo, ahi, blo, bhi, answer):
476 i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)
477 # a[alo:i] vs b[blo:j] unknown
478 # a[i:i+k] same as b[j:j+k]
479 # a[i+k:ahi] vs b[j+k:bhi] unknown
480 if k:
481 if alo < i and blo < j:
482 self.__helper(alo, i, blo, j, answer)
483 answer.append(x)
484 if i+k < ahi and j+k < bhi:
485 self.__helper(i+k, ahi, j+k, bhi, answer)
486
487 def get_opcodes(self):
488 """Return list of 5-tuples describing how to turn a into b.
489
490 Each tuple is of the form (tag, i1, i2, j1, j2). The first tuple
491 has i1 == j1 == 0, and remaining tuples have i1 == the i2 from the
492 tuple preceding it, and likewise for j1 == the previous j2.
493
494 The tags are strings, with these meanings:
495
496 'replace': a[i1:i2] should be replaced by b[j1:j2]
497 'delete': a[i1:i2] should be deleted.
498 Note that j1==j2 in this case.
499 'insert': b[j1:j2] should be inserted at a[i1:i1].
500 Note that i1==i2 in this case.
501 'equal': a[i1:i2] == b[j1:j2]
502
503 >>> a = "qabxcd"
504 >>> b = "abycdf"
505 >>> s = SequenceMatcher(None, a, b)
506 >>> for tag, i1, i2, j1, j2 in s.get_opcodes():
507 ... print ("%7s a[%d:%d] (%s) b[%d:%d] (%s)" %
508 ... (tag, i1, i2, a[i1:i2], j1, j2, b[j1:j2]))
509 delete a[0:1] (q) b[0:0] ()
510 equal a[1:3] (ab) b[0:2] (ab)
511 replace a[3:4] (x) b[2:3] (y)
512 equal a[4:6] (cd) b[3:5] (cd)
513 insert a[6:6] () b[5:6] (f)
514 """
515
516 if self.opcodes is not None:
517 return self.opcodes
518 i = j = 0
519 self.opcodes = answer = []
520 for ai, bj, size in self.get_matching_blocks():
521 # invariant: we've pumped out correct diffs to change
522 # a[:i] into b[:j], and the next matching block is
523 # a[ai:ai+size] == b[bj:bj+size]. So we need to pump
524 # out a diff to change a[i:ai] into b[j:bj], pump out
525 # the matching block, and move (i,j) beyond the match
526 tag = ''
527 if i < ai and j < bj:
528 tag = 'replace'
529 elif i < ai:
530 tag = 'delete'
531 elif j < bj:
532 tag = 'insert'
533 if tag:
534 answer.append( (tag, i, ai, j, bj) )
535 i, j = ai+size, bj+size
536 # the list of matching blocks is terminated by a
537 # sentinel with size 0
538 if size:
539 answer.append( ('equal', ai, i, bj, j) )
540 return answer
541
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +0000542 def get_grouped_opcodes(self, n=3):
543 """ Isolate change clusters by eliminating ranges with no changes.
544
545 Return a generator of groups with upto n lines of context.
546 Each group is in the same format as returned by get_opcodes().
547
548 >>> from pprint import pprint
549 >>> a = map(str, range(1,40))
550 >>> b = a[:]
551 >>> b[8:8] = ['i'] # Make an insertion
552 >>> b[20] += 'x' # Make a replacement
553 >>> b[23:28] = [] # Make a deletion
554 >>> b[30] += 'y' # Make another replacement
555 >>> pprint(list(SequenceMatcher(None,a,b).get_grouped_opcodes()))
556 [[('equal', 5, 8, 5, 8), ('insert', 8, 8, 8, 9), ('equal', 8, 11, 9, 12)],
557 [('equal', 16, 19, 17, 20),
558 ('replace', 19, 20, 20, 21),
559 ('equal', 20, 22, 21, 23),
560 ('delete', 22, 27, 23, 23),
561 ('equal', 27, 30, 23, 26)],
562 [('equal', 31, 34, 27, 30),
563 ('replace', 34, 35, 30, 31),
564 ('equal', 35, 38, 31, 34)]]
565 """
566
567 codes = self.get_opcodes()
568 # Fixup leading and trailing groups if they show no changes.
569 if codes[0][0] == 'equal':
570 tag, i1, i2, j1, j2 = codes[0]
571 codes[0] = tag, max(i1, i2-n), i2, max(j1, j2-n), j2
572 if codes[-1][0] == 'equal':
573 tag, i1, i2, j1, j2 = codes[-1]
574 codes[-1] = tag, i1, min(i2, i1+n), j1, min(j2, j1+n)
575
576 nn = n + n
577 group = []
578 for tag, i1, i2, j1, j2 in codes:
579 # End the current group and start a new one whenever
580 # there is a large range with no changes.
581 if tag == 'equal' and i2-i1 > nn:
582 group.append((tag, i1, min(i2, i1+n), j1, min(j2, j1+n)))
583 yield group
584 group = []
585 i1, j1 = max(i1, i2-n), max(j1, j2-n)
586 group.append((tag, i1, i2, j1 ,j2))
587 if group and not (len(group)==1 and group[0][0] == 'equal'):
588 yield group
589
Tim Peters9ae21482001-02-10 08:00:53 +0000590 def ratio(self):
591 """Return a measure of the sequences' similarity (float in [0,1]).
592
593 Where T is the total number of elements in both sequences, and
594 M is the number of matches, this is 2,0*M / T.
595 Note that this is 1 if the sequences are identical, and 0 if
596 they have nothing in common.
597
598 .ratio() is expensive to compute if you haven't already computed
599 .get_matching_blocks() or .get_opcodes(), in which case you may
600 want to try .quick_ratio() or .real_quick_ratio() first to get an
601 upper bound.
602
603 >>> s = SequenceMatcher(None, "abcd", "bcde")
604 >>> s.ratio()
605 0.75
606 >>> s.quick_ratio()
607 0.75
608 >>> s.real_quick_ratio()
609 1.0
610 """
611
612 matches = reduce(lambda sum, triple: sum + triple[-1],
613 self.get_matching_blocks(), 0)
614 return 2.0 * matches / (len(self.a) + len(self.b))
615
616 def quick_ratio(self):
617 """Return an upper bound on ratio() relatively quickly.
618
619 This isn't defined beyond that it is an upper bound on .ratio(), and
620 is faster to compute.
621 """
622
623 # viewing a and b as multisets, set matches to the cardinality
624 # of their intersection; this counts the number of matches
625 # without regard to order, so is clearly an upper bound
626 if self.fullbcount is None:
627 self.fullbcount = fullbcount = {}
628 for elt in self.b:
629 fullbcount[elt] = fullbcount.get(elt, 0) + 1
630 fullbcount = self.fullbcount
631 # avail[x] is the number of times x appears in 'b' less the
632 # number of times we've seen it in 'a' so far ... kinda
633 avail = {}
634 availhas, matches = avail.has_key, 0
635 for elt in self.a:
636 if availhas(elt):
637 numb = avail[elt]
638 else:
639 numb = fullbcount.get(elt, 0)
640 avail[elt] = numb - 1
641 if numb > 0:
642 matches = matches + 1
643 return 2.0 * matches / (len(self.a) + len(self.b))
644
645 def real_quick_ratio(self):
646 """Return an upper bound on ratio() very quickly.
647
648 This isn't defined beyond that it is an upper bound on .ratio(), and
649 is faster to compute than either .ratio() or .quick_ratio().
650 """
651
652 la, lb = len(self.a), len(self.b)
653 # can't have more matches than the number of elements in the
654 # shorter sequence
655 return 2.0 * min(la, lb) / (la + lb)
656
657def get_close_matches(word, possibilities, n=3, cutoff=0.6):
658 """Use SequenceMatcher to return list of the best "good enough" matches.
659
660 word is a sequence for which close matches are desired (typically a
661 string).
662
663 possibilities is a list of sequences against which to match word
664 (typically a list of strings).
665
666 Optional arg n (default 3) is the maximum number of close matches to
667 return. n must be > 0.
668
669 Optional arg cutoff (default 0.6) is a float in [0, 1]. Possibilities
670 that don't score at least that similar to word are ignored.
671
672 The best (no more than n) matches among the possibilities are returned
673 in a list, sorted by similarity score, most similar first.
674
675 >>> get_close_matches("appel", ["ape", "apple", "peach", "puppy"])
676 ['apple', 'ape']
Tim Peters5e824c32001-08-12 22:25:01 +0000677 >>> import keyword as _keyword
678 >>> get_close_matches("wheel", _keyword.kwlist)
Tim Peters9ae21482001-02-10 08:00:53 +0000679 ['while']
Tim Peters5e824c32001-08-12 22:25:01 +0000680 >>> get_close_matches("apple", _keyword.kwlist)
Tim Peters9ae21482001-02-10 08:00:53 +0000681 []
Tim Peters5e824c32001-08-12 22:25:01 +0000682 >>> get_close_matches("accept", _keyword.kwlist)
Tim Peters9ae21482001-02-10 08:00:53 +0000683 ['except']
684 """
685
686 if not n > 0:
Fred Drakef1da6282001-02-19 19:30:05 +0000687 raise ValueError("n must be > 0: " + `n`)
Tim Peters9ae21482001-02-10 08:00:53 +0000688 if not 0.0 <= cutoff <= 1.0:
Fred Drakef1da6282001-02-19 19:30:05 +0000689 raise ValueError("cutoff must be in [0.0, 1.0]: " + `cutoff`)
Tim Peters9ae21482001-02-10 08:00:53 +0000690 result = []
691 s = SequenceMatcher()
692 s.set_seq2(word)
693 for x in possibilities:
694 s.set_seq1(x)
695 if s.real_quick_ratio() >= cutoff and \
696 s.quick_ratio() >= cutoff and \
697 s.ratio() >= cutoff:
698 result.append((s.ratio(), x))
699 # Sort by score.
700 result.sort()
701 # Retain only the best n.
702 result = result[-n:]
703 # Move best-scorer to head of list.
704 result.reverse()
705 # Strip scores.
706 return [x for score, x in result]
707
Tim Peters5e824c32001-08-12 22:25:01 +0000708
709def _count_leading(line, ch):
710 """
711 Return number of `ch` characters at the start of `line`.
712
713 Example:
714
715 >>> _count_leading(' abc', ' ')
716 3
717 """
718
719 i, n = 0, len(line)
720 while i < n and line[i] == ch:
721 i += 1
722 return i
723
724class Differ:
725 r"""
726 Differ is a class for comparing sequences of lines of text, and
727 producing human-readable differences or deltas. Differ uses
728 SequenceMatcher both to compare sequences of lines, and to compare
729 sequences of characters within similar (near-matching) lines.
730
731 Each line of a Differ delta begins with a two-letter code:
732
733 '- ' line unique to sequence 1
734 '+ ' line unique to sequence 2
735 ' ' line common to both sequences
736 '? ' line not present in either input sequence
737
738 Lines beginning with '? ' attempt to guide the eye to intraline
739 differences, and were not present in either input sequence. These lines
740 can be confusing if the sequences contain tab characters.
741
742 Note that Differ makes no claim to produce a *minimal* diff. To the
743 contrary, minimal diffs are often counter-intuitive, because they synch
744 up anywhere possible, sometimes accidental matches 100 pages apart.
745 Restricting synch points to contiguous matches preserves some notion of
746 locality, at the occasional cost of producing a longer diff.
747
748 Example: Comparing two texts.
749
750 First we set up the texts, sequences of individual single-line strings
751 ending with newlines (such sequences can also be obtained from the
752 `readlines()` method of file-like objects):
753
754 >>> text1 = ''' 1. Beautiful is better than ugly.
755 ... 2. Explicit is better than implicit.
756 ... 3. Simple is better than complex.
757 ... 4. Complex is better than complicated.
758 ... '''.splitlines(1)
759 >>> len(text1)
760 4
761 >>> text1[0][-1]
762 '\n'
763 >>> text2 = ''' 1. Beautiful is better than ugly.
764 ... 3. Simple is better than complex.
765 ... 4. Complicated is better than complex.
766 ... 5. Flat is better than nested.
767 ... '''.splitlines(1)
768
769 Next we instantiate a Differ object:
770
771 >>> d = Differ()
772
773 Note that when instantiating a Differ object we may pass functions to
774 filter out line and character 'junk'. See Differ.__init__ for details.
775
776 Finally, we compare the two:
777
Tim Peters8a9c2842001-09-22 21:30:22 +0000778 >>> result = list(d.compare(text1, text2))
Tim Peters5e824c32001-08-12 22:25:01 +0000779
780 'result' is a list of strings, so let's pretty-print it:
781
782 >>> from pprint import pprint as _pprint
783 >>> _pprint(result)
784 [' 1. Beautiful is better than ugly.\n',
785 '- 2. Explicit is better than implicit.\n',
786 '- 3. Simple is better than complex.\n',
787 '+ 3. Simple is better than complex.\n',
788 '? ++\n',
789 '- 4. Complex is better than complicated.\n',
790 '? ^ ---- ^\n',
791 '+ 4. Complicated is better than complex.\n',
792 '? ++++ ^ ^\n',
793 '+ 5. Flat is better than nested.\n']
794
795 As a single multi-line string it looks like this:
796
797 >>> print ''.join(result),
798 1. Beautiful is better than ugly.
799 - 2. Explicit is better than implicit.
800 - 3. Simple is better than complex.
801 + 3. Simple is better than complex.
802 ? ++
803 - 4. Complex is better than complicated.
804 ? ^ ---- ^
805 + 4. Complicated is better than complex.
806 ? ++++ ^ ^
807 + 5. Flat is better than nested.
808
809 Methods:
810
811 __init__(linejunk=None, charjunk=None)
812 Construct a text differencer, with optional filters.
813
814 compare(a, b)
Tim Peters8a9c2842001-09-22 21:30:22 +0000815 Compare two sequences of lines; generate the resulting delta.
Tim Peters5e824c32001-08-12 22:25:01 +0000816 """
817
818 def __init__(self, linejunk=None, charjunk=None):
819 """
820 Construct a text differencer, with optional filters.
821
822 The two optional keyword parameters are for filter functions:
823
824 - `linejunk`: A function that should accept a single string argument,
825 and return true iff the string is junk. The module-level function
826 `IS_LINE_JUNK` may be used to filter out lines without visible
Tim Peters81b92512002-04-29 01:37:32 +0000827 characters, except for at most one splat ('#'). It is recommended
828 to leave linejunk None; as of Python 2.3, the underlying
829 SequenceMatcher class has grown an adaptive notion of "noise" lines
830 that's better than any static definition the author has ever been
831 able to craft.
Tim Peters5e824c32001-08-12 22:25:01 +0000832
833 - `charjunk`: A function that should accept a string of length 1. The
834 module-level function `IS_CHARACTER_JUNK` may be used to filter out
835 whitespace characters (a blank or tab; **note**: bad idea to include
Tim Peters81b92512002-04-29 01:37:32 +0000836 newline in this!). Use of IS_CHARACTER_JUNK is recommended.
Tim Peters5e824c32001-08-12 22:25:01 +0000837 """
838
839 self.linejunk = linejunk
840 self.charjunk = charjunk
Tim Peters5e824c32001-08-12 22:25:01 +0000841
842 def compare(self, a, b):
843 r"""
Tim Peters8a9c2842001-09-22 21:30:22 +0000844 Compare two sequences of lines; generate the resulting delta.
Tim Peters5e824c32001-08-12 22:25:01 +0000845
846 Each sequence must contain individual single-line strings ending with
847 newlines. Such sequences can be obtained from the `readlines()` method
Tim Peters8a9c2842001-09-22 21:30:22 +0000848 of file-like objects. The delta generated also consists of newline-
849 terminated strings, ready to be printed as-is via the writeline()
Tim Peters5e824c32001-08-12 22:25:01 +0000850 method of a file-like object.
851
852 Example:
853
854 >>> print ''.join(Differ().compare('one\ntwo\nthree\n'.splitlines(1),
855 ... 'ore\ntree\nemu\n'.splitlines(1))),
856 - one
857 ? ^
858 + ore
859 ? ^
860 - two
861 - three
862 ? -
863 + tree
864 + emu
865 """
866
867 cruncher = SequenceMatcher(self.linejunk, a, b)
868 for tag, alo, ahi, blo, bhi in cruncher.get_opcodes():
869 if tag == 'replace':
Tim Peters8a9c2842001-09-22 21:30:22 +0000870 g = self._fancy_replace(a, alo, ahi, b, blo, bhi)
Tim Peters5e824c32001-08-12 22:25:01 +0000871 elif tag == 'delete':
Tim Peters8a9c2842001-09-22 21:30:22 +0000872 g = self._dump('-', a, alo, ahi)
Tim Peters5e824c32001-08-12 22:25:01 +0000873 elif tag == 'insert':
Tim Peters8a9c2842001-09-22 21:30:22 +0000874 g = self._dump('+', b, blo, bhi)
Tim Peters5e824c32001-08-12 22:25:01 +0000875 elif tag == 'equal':
Tim Peters8a9c2842001-09-22 21:30:22 +0000876 g = self._dump(' ', a, alo, ahi)
Tim Peters5e824c32001-08-12 22:25:01 +0000877 else:
878 raise ValueError, 'unknown tag ' + `tag`
Tim Peters8a9c2842001-09-22 21:30:22 +0000879
880 for line in g:
881 yield line
Tim Peters5e824c32001-08-12 22:25:01 +0000882
883 def _dump(self, tag, x, lo, hi):
Tim Peters8a9c2842001-09-22 21:30:22 +0000884 """Generate comparison results for a same-tagged range."""
Tim Peters5e824c32001-08-12 22:25:01 +0000885 for i in xrange(lo, hi):
Tim Peters8a9c2842001-09-22 21:30:22 +0000886 yield '%s %s' % (tag, x[i])
Tim Peters5e824c32001-08-12 22:25:01 +0000887
888 def _plain_replace(self, a, alo, ahi, b, blo, bhi):
889 assert alo < ahi and blo < bhi
890 # dump the shorter block first -- reduces the burden on short-term
891 # memory if the blocks are of very different sizes
892 if bhi - blo < ahi - alo:
Tim Peters8a9c2842001-09-22 21:30:22 +0000893 first = self._dump('+', b, blo, bhi)
894 second = self._dump('-', a, alo, ahi)
Tim Peters5e824c32001-08-12 22:25:01 +0000895 else:
Tim Peters8a9c2842001-09-22 21:30:22 +0000896 first = self._dump('-', a, alo, ahi)
897 second = self._dump('+', b, blo, bhi)
898
899 for g in first, second:
900 for line in g:
901 yield line
Tim Peters5e824c32001-08-12 22:25:01 +0000902
903 def _fancy_replace(self, a, alo, ahi, b, blo, bhi):
904 r"""
905 When replacing one block of lines with another, search the blocks
906 for *similar* lines; the best-matching pair (if any) is used as a
907 synch point, and intraline difference marking is done on the
908 similar pair. Lots of work, but often worth it.
909
910 Example:
911
912 >>> d = Differ()
913 >>> d._fancy_replace(['abcDefghiJkl\n'], 0, 1, ['abcdefGhijkl\n'], 0, 1)
914 >>> print ''.join(d.results),
915 - abcDefghiJkl
916 ? ^ ^ ^
917 + abcdefGhijkl
918 ? ^ ^ ^
919 """
920
Tim Peters5e824c32001-08-12 22:25:01 +0000921 # don't synch up unless the lines have a similarity score of at
922 # least cutoff; best_ratio tracks the best score seen so far
923 best_ratio, cutoff = 0.74, 0.75
924 cruncher = SequenceMatcher(self.charjunk)
925 eqi, eqj = None, None # 1st indices of equal lines (if any)
926
927 # search for the pair that matches best without being identical
928 # (identical lines must be junk lines, & we don't want to synch up
929 # on junk -- unless we have to)
930 for j in xrange(blo, bhi):
931 bj = b[j]
932 cruncher.set_seq2(bj)
933 for i in xrange(alo, ahi):
934 ai = a[i]
935 if ai == bj:
936 if eqi is None:
937 eqi, eqj = i, j
938 continue
939 cruncher.set_seq1(ai)
940 # computing similarity is expensive, so use the quick
941 # upper bounds first -- have seen this speed up messy
942 # compares by a factor of 3.
943 # note that ratio() is only expensive to compute the first
944 # time it's called on a sequence pair; the expensive part
945 # of the computation is cached by cruncher
946 if cruncher.real_quick_ratio() > best_ratio and \
947 cruncher.quick_ratio() > best_ratio and \
948 cruncher.ratio() > best_ratio:
949 best_ratio, best_i, best_j = cruncher.ratio(), i, j
950 if best_ratio < cutoff:
951 # no non-identical "pretty close" pair
952 if eqi is None:
953 # no identical pair either -- treat it as a straight replace
Tim Peters8a9c2842001-09-22 21:30:22 +0000954 for line in self._plain_replace(a, alo, ahi, b, blo, bhi):
955 yield line
Tim Peters5e824c32001-08-12 22:25:01 +0000956 return
957 # no close pair, but an identical pair -- synch up on that
958 best_i, best_j, best_ratio = eqi, eqj, 1.0
959 else:
960 # there's a close pair, so forget the identical pair (if any)
961 eqi = None
962
963 # a[best_i] very similar to b[best_j]; eqi is None iff they're not
964 # identical
Tim Peters5e824c32001-08-12 22:25:01 +0000965
966 # pump out diffs from before the synch point
Tim Peters8a9c2842001-09-22 21:30:22 +0000967 for line in self._fancy_helper(a, alo, best_i, b, blo, best_j):
968 yield line
Tim Peters5e824c32001-08-12 22:25:01 +0000969
970 # do intraline marking on the synch pair
971 aelt, belt = a[best_i], b[best_j]
972 if eqi is None:
973 # pump out a '-', '?', '+', '?' quad for the synched lines
974 atags = btags = ""
975 cruncher.set_seqs(aelt, belt)
976 for tag, ai1, ai2, bj1, bj2 in cruncher.get_opcodes():
977 la, lb = ai2 - ai1, bj2 - bj1
978 if tag == 'replace':
979 atags += '^' * la
980 btags += '^' * lb
981 elif tag == 'delete':
982 atags += '-' * la
983 elif tag == 'insert':
984 btags += '+' * lb
985 elif tag == 'equal':
986 atags += ' ' * la
987 btags += ' ' * lb
988 else:
989 raise ValueError, 'unknown tag ' + `tag`
Tim Peters8a9c2842001-09-22 21:30:22 +0000990 for line in self._qformat(aelt, belt, atags, btags):
991 yield line
Tim Peters5e824c32001-08-12 22:25:01 +0000992 else:
993 # the synch pair is identical
Tim Peters8a9c2842001-09-22 21:30:22 +0000994 yield ' ' + aelt
Tim Peters5e824c32001-08-12 22:25:01 +0000995
996 # pump out diffs from after the synch point
Tim Peters8a9c2842001-09-22 21:30:22 +0000997 for line in self._fancy_helper(a, best_i+1, ahi, b, best_j+1, bhi):
998 yield line
Tim Peters5e824c32001-08-12 22:25:01 +0000999
1000 def _fancy_helper(self, a, alo, ahi, b, blo, bhi):
Tim Peters8a9c2842001-09-22 21:30:22 +00001001 g = []
Tim Peters5e824c32001-08-12 22:25:01 +00001002 if alo < ahi:
1003 if blo < bhi:
Tim Peters8a9c2842001-09-22 21:30:22 +00001004 g = self._fancy_replace(a, alo, ahi, b, blo, bhi)
Tim Peters5e824c32001-08-12 22:25:01 +00001005 else:
Tim Peters8a9c2842001-09-22 21:30:22 +00001006 g = self._dump('-', a, alo, ahi)
Tim Peters5e824c32001-08-12 22:25:01 +00001007 elif blo < bhi:
Tim Peters8a9c2842001-09-22 21:30:22 +00001008 g = self._dump('+', b, blo, bhi)
1009
1010 for line in g:
1011 yield line
Tim Peters5e824c32001-08-12 22:25:01 +00001012
1013 def _qformat(self, aline, bline, atags, btags):
1014 r"""
1015 Format "?" output and deal with leading tabs.
1016
1017 Example:
1018
1019 >>> d = Differ()
1020 >>> d._qformat('\tabcDefghiJkl\n', '\t\tabcdefGhijkl\n',
1021 ... ' ^ ^ ^ ', '+ ^ ^ ^ ')
1022 >>> for line in d.results: print repr(line)
1023 ...
1024 '- \tabcDefghiJkl\n'
1025 '? \t ^ ^ ^\n'
1026 '+ \t\tabcdefGhijkl\n'
1027 '? \t ^ ^ ^\n'
1028 """
1029
1030 # Can hurt, but will probably help most of the time.
1031 common = min(_count_leading(aline, "\t"),
1032 _count_leading(bline, "\t"))
1033 common = min(common, _count_leading(atags[:common], " "))
1034 atags = atags[common:].rstrip()
1035 btags = btags[common:].rstrip()
1036
Tim Peters8a9c2842001-09-22 21:30:22 +00001037 yield "- " + aline
Tim Peters5e824c32001-08-12 22:25:01 +00001038 if atags:
Tim Peters527e64f2001-10-04 05:36:56 +00001039 yield "? %s%s\n" % ("\t" * common, atags)
Tim Peters5e824c32001-08-12 22:25:01 +00001040
Tim Peters8a9c2842001-09-22 21:30:22 +00001041 yield "+ " + bline
Tim Peters5e824c32001-08-12 22:25:01 +00001042 if btags:
Tim Peters8a9c2842001-09-22 21:30:22 +00001043 yield "? %s%s\n" % ("\t" * common, btags)
Tim Peters5e824c32001-08-12 22:25:01 +00001044
1045# With respect to junk, an earlier version of ndiff simply refused to
1046# *start* a match with a junk element. The result was cases like this:
1047# before: private Thread currentThread;
1048# after: private volatile Thread currentThread;
1049# If you consider whitespace to be junk, the longest contiguous match
1050# not starting with junk is "e Thread currentThread". So ndiff reported
1051# that "e volatil" was inserted between the 't' and the 'e' in "private".
1052# While an accurate view, to people that's absurd. The current version
1053# looks for matching blocks that are entirely junk-free, then extends the
1054# longest one of those as far as possible but only with matching junk.
1055# So now "currentThread" is matched, then extended to suck up the
1056# preceding blank; then "private" is matched, and extended to suck up the
1057# following blank; then "Thread" is matched; and finally ndiff reports
1058# that "volatile " was inserted before "Thread". The only quibble
1059# remaining is that perhaps it was really the case that " volatile"
1060# was inserted after "private". I can live with that <wink>.
1061
1062import re
1063
1064def IS_LINE_JUNK(line, pat=re.compile(r"\s*#?\s*$").match):
1065 r"""
1066 Return 1 for ignorable line: iff `line` is blank or contains a single '#'.
1067
1068 Examples:
1069
1070 >>> IS_LINE_JUNK('\n')
Guido van Rossum77f6a652002-04-03 22:41:51 +00001071 True
Tim Peters5e824c32001-08-12 22:25:01 +00001072 >>> IS_LINE_JUNK(' # \n')
Guido van Rossum77f6a652002-04-03 22:41:51 +00001073 True
Tim Peters5e824c32001-08-12 22:25:01 +00001074 >>> IS_LINE_JUNK('hello\n')
Guido van Rossum77f6a652002-04-03 22:41:51 +00001075 False
Tim Peters5e824c32001-08-12 22:25:01 +00001076 """
1077
1078 return pat(line) is not None
1079
1080def IS_CHARACTER_JUNK(ch, ws=" \t"):
1081 r"""
1082 Return 1 for ignorable character: iff `ch` is a space or tab.
1083
1084 Examples:
1085
1086 >>> IS_CHARACTER_JUNK(' ')
Guido van Rossum77f6a652002-04-03 22:41:51 +00001087 True
Tim Peters5e824c32001-08-12 22:25:01 +00001088 >>> IS_CHARACTER_JUNK('\t')
Guido van Rossum77f6a652002-04-03 22:41:51 +00001089 True
Tim Peters5e824c32001-08-12 22:25:01 +00001090 >>> IS_CHARACTER_JUNK('\n')
Guido van Rossum77f6a652002-04-03 22:41:51 +00001091 False
Tim Peters5e824c32001-08-12 22:25:01 +00001092 >>> IS_CHARACTER_JUNK('x')
Guido van Rossum77f6a652002-04-03 22:41:51 +00001093 False
Tim Peters5e824c32001-08-12 22:25:01 +00001094 """
1095
1096 return ch in ws
1097
1098del re
1099
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001100
1101def unified_diff(a, b, fromfile='', tofile='', fromfiledate='',
1102 tofiledate='', n=3, lineterm='\n'):
1103 r"""
1104 Compare two sequences of lines; generate the delta as a unified diff.
1105
1106 Unified diffs are a compact way of showing line changes and a few
1107 lines of context. The number of context lines is set by 'n' which
1108 defaults to three.
1109
Raymond Hettinger0887c732003-06-17 16:53:25 +00001110 By default, the diff control lines (those with ---, +++, or @@) are
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001111 created with a trailing newline. This is helpful so that inputs
1112 created from file.readlines() result in diffs that are suitable for
1113 file.writelines() since both the inputs and outputs have trailing
1114 newlines.
1115
1116 For inputs that do not have trailing newlines, set the lineterm
1117 argument to "" so that the output will be uniformly newline free.
1118
1119 The unidiff format normally has a header for filenames and modification
1120 times. Any or all of these may be specified using strings for
1121 'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'. The modification
1122 times are normally expressed in the format returned by time.ctime().
1123
1124 Example:
1125
1126 >>> for line in unified_diff('one two three four'.split(),
1127 ... 'zero one tree four'.split(), 'Original', 'Current',
1128 ... 'Sat Jan 26 23:30:50 1991', 'Fri Jun 06 10:20:52 2003',
1129 ... lineterm=''):
1130 ... print line
1131 --- Original Sat Jan 26 23:30:50 1991
1132 +++ Current Fri Jun 06 10:20:52 2003
1133 @@ -1,4 +1,4 @@
1134 +zero
1135 one
1136 -two
1137 -three
1138 +tree
1139 four
1140 """
1141
1142 started = False
1143 for group in SequenceMatcher(None,a,b).get_grouped_opcodes(n):
1144 if not started:
1145 yield '--- %s %s%s' % (fromfile, fromfiledate, lineterm)
1146 yield '+++ %s %s%s' % (tofile, tofiledate, lineterm)
1147 started = True
1148 i1, i2, j1, j2 = group[0][1], group[-1][2], group[0][3], group[-1][4]
1149 yield "@@ -%d,%d +%d,%d @@%s" % (i1+1, i2-i1, j1+1, j2-j1, lineterm)
1150 for tag, i1, i2, j1, j2 in group:
1151 if tag == 'equal':
1152 for line in a[i1:i2]:
1153 yield ' ' + line
1154 continue
1155 if tag == 'replace' or tag == 'delete':
1156 for line in a[i1:i2]:
1157 yield '-' + line
1158 if tag == 'replace' or tag == 'insert':
1159 for line in b[j1:j2]:
1160 yield '+' + line
1161
1162# See http://www.unix.org/single_unix_specification/
1163def context_diff(a, b, fromfile='', tofile='',
1164 fromfiledate='', tofiledate='', n=3, lineterm='\n'):
1165 r"""
1166 Compare two sequences of lines; generate the delta as a context diff.
1167
1168 Context diffs are a compact way of showing line changes and a few
1169 lines of context. The number of context lines is set by 'n' which
1170 defaults to three.
1171
1172 By default, the diff control lines (those with *** or ---) are
1173 created with a trailing newline. This is helpful so that inputs
1174 created from file.readlines() result in diffs that are suitable for
1175 file.writelines() since both the inputs and outputs have trailing
1176 newlines.
1177
1178 For inputs that do not have trailing newlines, set the lineterm
1179 argument to "" so that the output will be uniformly newline free.
1180
1181 The context diff format normally has a header for filenames and
1182 modification times. Any or all of these may be specified using
1183 strings for 'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'.
1184 The modification times are normally expressed in the format returned
1185 by time.ctime(). If not specified, the strings default to blanks.
1186
1187 Example:
1188
1189 >>> print ''.join(context_diff('one\ntwo\nthree\nfour\n'.splitlines(1),
1190 ... 'zero\none\ntree\nfour\n'.splitlines(1), 'Original', 'Current',
1191 ... 'Sat Jan 26 23:30:50 1991', 'Fri Jun 06 10:22:46 2003')),
1192 *** Original Sat Jan 26 23:30:50 1991
1193 --- Current Fri Jun 06 10:22:46 2003
1194 ***************
1195 *** 1,4 ****
1196 one
1197 ! two
1198 ! three
1199 four
1200 --- 1,4 ----
1201 + zero
1202 one
1203 ! tree
1204 four
1205 """
1206
1207 started = False
Raymond Hettinger7f2d3022003-06-08 19:38:42 +00001208 prefixmap = {'insert':'+ ', 'delete':'- ', 'replace':'! ', 'equal':' '}
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001209 for group in SequenceMatcher(None,a,b).get_grouped_opcodes(n):
1210 if not started:
1211 yield '*** %s %s%s' % (fromfile, fromfiledate, lineterm)
1212 yield '--- %s %s%s' % (tofile, tofiledate, lineterm)
1213 started = True
Raymond Hettinger7f2d3022003-06-08 19:38:42 +00001214
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001215 yield '***************%s' % (lineterm,)
1216 if group[-1][2] - group[0][1] >= 2:
1217 yield '*** %d,%d ****%s' % (group[0][1]+1, group[-1][2], lineterm)
1218 else:
1219 yield '*** %d ****%s' % (group[-1][2], lineterm)
Raymond Hettinger7f2d3022003-06-08 19:38:42 +00001220 visiblechanges = [e for e in group if e[0] in ('replace', 'delete')]
1221 if visiblechanges:
1222 for tag, i1, i2, _, _ in group:
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001223 if tag != 'insert':
1224 for line in a[i1:i2]:
1225 yield prefixmap[tag] + line
Raymond Hettinger7f2d3022003-06-08 19:38:42 +00001226
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001227 if group[-1][4] - group[0][3] >= 2:
1228 yield '--- %d,%d ----%s' % (group[0][3]+1, group[-1][4], lineterm)
1229 else:
1230 yield '--- %d ----%s' % (group[-1][4], lineterm)
Raymond Hettinger7f2d3022003-06-08 19:38:42 +00001231 visiblechanges = [e for e in group if e[0] in ('replace', 'insert')]
1232 if visiblechanges:
1233 for tag, _, _, j1, j2 in group:
Raymond Hettingerf0b1a1f2003-06-08 11:07:08 +00001234 if tag != 'delete':
1235 for line in b[j1:j2]:
1236 yield prefixmap[tag] + line
1237
Tim Peters81b92512002-04-29 01:37:32 +00001238def ndiff(a, b, linejunk=None, charjunk=IS_CHARACTER_JUNK):
Tim Peters5e824c32001-08-12 22:25:01 +00001239 r"""
1240 Compare `a` and `b` (lists of strings); return a `Differ`-style delta.
1241
1242 Optional keyword parameters `linejunk` and `charjunk` are for filter
1243 functions (or None):
1244
1245 - linejunk: A function that should accept a single string argument, and
Tim Peters81b92512002-04-29 01:37:32 +00001246 return true iff the string is junk. The default is None, and is
1247 recommended; as of Python 2.3, an adaptive notion of "noise" lines is
1248 used that does a good job on its own.
Tim Peters5e824c32001-08-12 22:25:01 +00001249
1250 - charjunk: A function that should accept a string of length 1. The
1251 default is module-level function IS_CHARACTER_JUNK, which filters out
1252 whitespace characters (a blank or tab; note: bad idea to include newline
1253 in this!).
1254
1255 Tools/scripts/ndiff.py is a command-line front-end to this function.
1256
1257 Example:
1258
1259 >>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
1260 ... 'ore\ntree\nemu\n'.splitlines(1))
1261 >>> print ''.join(diff),
1262 - one
1263 ? ^
1264 + ore
1265 ? ^
1266 - two
1267 - three
1268 ? -
1269 + tree
1270 + emu
1271 """
1272 return Differ(linejunk, charjunk).compare(a, b)
1273
1274def restore(delta, which):
1275 r"""
Tim Peters8a9c2842001-09-22 21:30:22 +00001276 Generate one of the two sequences that generated a delta.
Tim Peters5e824c32001-08-12 22:25:01 +00001277
1278 Given a `delta` produced by `Differ.compare()` or `ndiff()`, extract
1279 lines originating from file 1 or 2 (parameter `which`), stripping off line
1280 prefixes.
1281
1282 Examples:
1283
1284 >>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
1285 ... 'ore\ntree\nemu\n'.splitlines(1))
Tim Peters8a9c2842001-09-22 21:30:22 +00001286 >>> diff = list(diff)
Tim Peters5e824c32001-08-12 22:25:01 +00001287 >>> print ''.join(restore(diff, 1)),
1288 one
1289 two
1290 three
1291 >>> print ''.join(restore(diff, 2)),
1292 ore
1293 tree
1294 emu
1295 """
1296 try:
1297 tag = {1: "- ", 2: "+ "}[int(which)]
1298 except KeyError:
1299 raise ValueError, ('unknown delta choice (must be 1 or 2): %r'
1300 % which)
1301 prefixes = (" ", tag)
Tim Peters5e824c32001-08-12 22:25:01 +00001302 for line in delta:
1303 if line[:2] in prefixes:
Tim Peters8a9c2842001-09-22 21:30:22 +00001304 yield line[2:]
Tim Peters5e824c32001-08-12 22:25:01 +00001305
Tim Peters9ae21482001-02-10 08:00:53 +00001306def _test():
1307 import doctest, difflib
1308 return doctest.testmod(difflib)
1309
1310if __name__ == "__main__":
1311 _test()