4 Module difflib -- helpers for computing deltas between objects.
6 Function get_close_matches(word, possibilities, n=3, cutoff=0.6):
7 Use SequenceMatcher to return list of the best "good enough" matches.
9 Function context_diff(a, b):
10 For two lists of strings, return a delta in context diff format.
13 Return a delta: the difference between `a` and `b` (lists of strings).
15 Function restore(delta, which):
16 Return one of the two sequences that generated an ndiff delta.
18 Function unified_diff(a, b):
19 For two lists of strings, return a delta in unified diff format.
21 Class SequenceMatcher:
22 A flexible class for comparing pairs of sequences of any type.
25 For producing human-readable deltas from sequences of lines of text.
28 For producing HTML side by side comparison with change highlights.
31 __all__
= ['get_close_matches', 'ndiff', 'restore', 'SequenceMatcher',
32 'Differ','IS_CHARACTER_JUNK', 'IS_LINE_JUNK', 'context_diff',
33 'unified_diff', 'HtmlDiff', 'Match']
36 from collections
import namedtuple
as _namedtuple
37 from functools
import reduce
39 Match
= _namedtuple('Match', 'a b size')
41 def _calculate_ratio(matches
, length
):
43 return 2.0 * matches
/ length
46 class SequenceMatcher
:
49 SequenceMatcher is a flexible class for comparing pairs of sequences of
50 any type, so long as the sequence elements are hashable. The basic
51 algorithm predates, and is a little fancier than, an algorithm
52 published in the late 1980's by Ratcliff and Obershelp under the
53 hyperbolic name "gestalt pattern matching". The basic idea is to find
54 the longest contiguous matching subsequence that contains no "junk"
55 elements (R-O doesn't address junk). The same idea is then applied
56 recursively to the pieces of the sequences to the left and to the right
57 of the matching subsequence. This does not yield minimal edit
58 sequences, but does tend to yield matches that "look right" to people.
60 SequenceMatcher tries to compute a "human-friendly diff" between two
61 sequences. Unlike e.g. UNIX(tm) diff, the fundamental notion is the
62 longest *contiguous* & junk-free matching subsequence. That's what
63 catches peoples' eyes. The Windows(tm) windiff has another interesting
64 notion, pairing up elements that appear uniquely in each sequence.
65 That, and the method here, appear to yield more intuitive difference
66 reports than does diff. This method appears to be the least vulnerable
67 to synching up on blocks of "junk lines", though (like blank lines in
68 ordinary text files, or maybe "<P>" lines in HTML files). That may be
69 because this is the only method of the 3 that has a *concept* of
72 Example, comparing two strings, and considering blanks to be "junk":
74 >>> s = SequenceMatcher(lambda x: x == " ",
75 ... "private Thread currentThread;",
76 ... "private volatile Thread currentThread;")
79 .ratio() returns a float in [0, 1], measuring the "similarity" of the
80 sequences. As a rule of thumb, a .ratio() value over 0.6 means the
81 sequences are close matches:
83 >>> print round(s.ratio(), 3)
87 If you're only interested in where the sequences match,
88 .get_matching_blocks() is handy:
90 >>> for block in s.get_matching_blocks():
91 ... print "a[%d] and b[%d] match for %d elements" % block
92 a[0] and b[0] match for 8 elements
93 a[8] and b[17] match for 21 elements
94 a[29] and b[38] match for 0 elements
96 Note that the last tuple returned by .get_matching_blocks() is always a
97 dummy, (len(a), len(b), 0), and this is the only case in which the last
98 tuple element (number of elements matched) is 0.
100 If you want to know how to change the first sequence into the second,
103 >>> for opcode in s.get_opcodes():
104 ... print "%6s a[%d:%d] b[%d:%d]" % opcode
106 insert a[8:8] b[8:17]
107 equal a[8:29] b[17:38]
109 See the Differ class for a fancy human-friendly file differencer, which
110 uses SequenceMatcher both to compare sequences of lines, and to compare
111 sequences of characters within similar (near-matching) lines.
113 See also function get_close_matches() in this module, which shows how
114 simple code building on SequenceMatcher can be used to do useful work.
116 Timing: Basic R-O is cubic time worst case and quadratic time expected
117 case. SequenceMatcher is quadratic time for the worst case and has
118 expected-case behavior dependent in a complicated way on how many
119 elements the sequences have in common; best case time is linear.
123 __init__(isjunk=None, a='', b='')
124 Construct a SequenceMatcher.
127 Set the two sequences to be compared.
130 Set the first sequence to be compared.
133 Set the second sequence to be compared.
135 find_longest_match(alo, ahi, blo, bhi)
136 Find longest matching block in a[alo:ahi] and b[blo:bhi].
138 get_matching_blocks()
139 Return list of triples describing matching subsequences.
142 Return list of 5-tuples describing how to turn a into b.
145 Return a measure of the sequences' similarity (float in [0,1]).
148 Return an upper bound on .ratio() relatively quickly.
151 Return an upper bound on ratio() very quickly.
154 def __init__(self
, isjunk
=None, a
='', b
=''):
155 """Construct a SequenceMatcher.
157 Optional arg isjunk is None (the default), or a one-argument
158 function that takes a sequence element and returns true iff the
159 element is junk. None is equivalent to passing "lambda x: 0", i.e.
160 no elements are considered to be junk. For example, pass
161 lambda x: x in " \\t"
162 if you're comparing lines as sequences of characters, and don't
163 want to synch up on blanks or hard tabs.
165 Optional arg a is the first of two sequences to be compared. By
166 default, an empty string. The elements of a must be hashable. See
167 also .set_seqs() and .set_seq1().
169 Optional arg b is the second of two sequences to be compared. By
170 default, an empty string. The elements of b must be hashable. See
171 also .set_seqs() and .set_seq2().
178 # second sequence; differences are computed as "what do
179 # we need to do to 'a' to change it into 'b'?"
181 # for x in b, b2j[x] is a list of the indices (into b)
182 # at which x appears; junk elements do not appear
184 # for x in b, fullbcount[x] == the number of times x
185 # appears in b; only materialized if really needed (used
186 # only for computing quick_ratio())
188 # a list of (i, j, k) triples, where a[i:i+k] == b[j:j+k];
189 # ascending & non-overlapping in i and in j; terminated by
190 # a dummy (len(a), len(b), 0) sentinel
192 # a list of (tag, i1, i2, j1, j2) tuples, where tag is
194 # 'replace' a[i1:i2] should be replaced by b[j1:j2]
195 # 'delete' a[i1:i2] should be deleted
196 # 'insert' b[j1:j2] should be inserted
197 # 'equal' a[i1:i2] == b[j1:j2]
199 # a user-supplied function taking a sequence element and
200 # returning true iff the element is "junk" -- this has
201 # subtle but helpful effects on the algorithm, which I'll
202 # get around to writing up someday <0.9 wink>.
203 # DON'T USE! Only __chain_b uses this. Use isbjunk.
205 # for x in b, isbjunk(x) == isjunk(x) but much faster;
206 # it's really the __contains__ method of a hidden dict.
207 # DOES NOT WORK for x in a!
209 # for x in b, isbpopular(x) is true iff b is reasonably long
210 # (at least 200 elements) and x accounts for more than 1% of
211 # its elements. DOES NOT WORK for x in a!
214 self
.a
= self
.b
= None
217 def set_seqs(self
, a
, b
):
218 """Set the two sequences to be compared.
220 >>> s = SequenceMatcher()
221 >>> s.set_seqs("abcd", "bcde")
229 def set_seq1(self
, a
):
230 """Set the first sequence to be compared.
232 The second sequence to be compared is not changed.
234 >>> s = SequenceMatcher(None, "abcd", "bcde")
237 >>> s.set_seq1("bcde")
242 SequenceMatcher computes and caches detailed information about the
243 second sequence, so if you want to compare one sequence S against
244 many sequences, use .set_seq2(S) once and call .set_seq1(x)
245 repeatedly for each of the other sequences.
247 See also set_seqs() and set_seq2().
253 self
.matching_blocks
= self
.opcodes
= None
255 def set_seq2(self
, b
):
256 """Set the second sequence to be compared.
258 The first sequence to be compared is not changed.
260 >>> s = SequenceMatcher(None, "abcd", "bcde")
263 >>> s.set_seq2("abcd")
268 SequenceMatcher computes and caches detailed information about the
269 second sequence, so if you want to compare one sequence S against
270 many sequences, use .set_seq2(S) once and call .set_seq1(x)
271 repeatedly for each of the other sequences.
273 See also set_seqs() and set_seq1().
279 self
.matching_blocks
= self
.opcodes
= None
280 self
.fullbcount
= None
283 # For each element x in b, set b2j[x] to a list of the indices in
284 # b where x appears; the indices are in increasing order; note that
285 # the number of times x appears in b is len(b2j[x]) ...
286 # when self.isjunk is defined, junk elements don't show up in this
287 # map at all, which stops the central find_longest_match method
288 # from starting any matching block at a junk element ...
289 # also creates the fast isbjunk function ...
290 # b2j also does not contain entries for "popular" elements, meaning
291 # elements that account for more than 1% of the total elements, and
292 # when the sequence is reasonably large (>= 200 elements); this can
293 # be viewed as an adaptive notion of semi-junk, and yields an enormous
294 # speedup when, e.g., comparing program files with hundreds of
295 # instances of "return NULL;" ...
296 # note that this is only called when b changes; so for cross-product
297 # kinds of matches, it's best to call set_seq2 once, then set_seq1
301 # Because isjunk is a user-defined (not C) function, and we test
302 # for junk a LOT, it's important to minimize the number of calls.
303 # Before the tricks described here, __chain_b was by far the most
304 # time-consuming routine in the whole module! If anyone sees
305 # Jim Roskind, thank him again for profile.py -- I never would
307 # The first trick is to build b2j ignoring the possibility
308 # of junk. I.e., we don't call isjunk at all yet. Throwing
309 # out the junk later is much cheaper than building b2j "right"
315 for i
, elt
in enumerate(b
):
318 if n
>= 200 and len(indices
) * 100 > n
:
326 # Purge leftover indices for popular elements.
327 for elt
in populardict
:
330 # Now b2j.keys() contains elements uniquely, and especially when
331 # the sequence is a string, that's usually a good deal smaller
332 # than len(string). The difference is the number of isjunk calls
337 for d
in populardict
, b2j
:
343 # Now for x in b, isjunk(x) == x in junkdict, but the
344 # latter is much faster. Note too that while there may be a
345 # lot of junk in the sequence, the number of *unique* junk
346 # elements is probably small. So the memory burden of keeping
347 # this dict alive is likely trivial compared to the size of b2j.
348 self
.isbjunk
= junkdict
.__contains
__
349 self
.isbpopular
= populardict
.__contains
__
351 def find_longest_match(self
, alo
, ahi
, blo
, bhi
):
352 """Find longest matching block in a[alo:ahi] and b[blo:bhi].
354 If isjunk is not defined:
356 Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
357 alo <= i <= i+k <= ahi
358 blo <= j <= j+k <= bhi
359 and for all (i',j',k') meeting those conditions,
362 and if i == i', j <= j'
364 In other words, of all maximal matching blocks, return one that
365 starts earliest in a, and of all those maximal matching blocks that
366 start earliest in a, return the one that starts earliest in b.
368 >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
369 >>> s.find_longest_match(0, 5, 0, 9)
370 Match(a=0, b=4, size=5)
372 If isjunk is defined, first the longest matching block is
373 determined as above, but with the additional restriction that no
374 junk element appears in the block. Then that block is extended as
375 far as possible by matching (only) junk elements on both sides. So
376 the resulting block never matches on junk except as identical junk
377 happens to be adjacent to an "interesting" match.
379 Here's the same example as before, but considering blanks to be
380 junk. That prevents " abcd" from matching the " abcd" at the tail
381 end of the second sequence directly. Instead only the "abcd" can
382 match, and matches the leftmost "abcd" in the second sequence:
384 >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
385 >>> s.find_longest_match(0, 5, 0, 9)
386 Match(a=1, b=0, size=4)
388 If no blocks match, return (alo, blo, 0).
390 >>> s = SequenceMatcher(None, "ab", "c")
391 >>> s.find_longest_match(0, 2, 0, 1)
392 Match(a=0, b=0, size=0)
395 # CAUTION: stripping common prefix or suffix would be incorrect.
399 # Longest matching block is "ab", but if common prefix is
400 # stripped, it's "a" (tied with "b"). UNIX(tm) diff does so
401 # strip, so ends up claiming that ab is changed to acab by
402 # inserting "ca" in the middle. That's minimal but unintuitive:
403 # "it's obvious" that someone inserted "ac" at the front.
404 # Windiff ends up at the same place as diff, but by pairing up
405 # the unique 'b's and then matching the first two 'a's.
407 a
, b
, b2j
, isbjunk
= self
.a
, self
.b
, self
.b2j
, self
.isbjunk
408 besti
, bestj
, bestsize
= alo
, blo
, 0
409 # find longest junk-free match
410 # during an iteration of the loop, j2len[j] = length of longest
411 # junk-free match ending with a[i-1] and b[j]
414 for i
in xrange(alo
, ahi
):
415 # look at all instances of a[i] in b; note that because
416 # b2j has no junk keys, the loop is skipped if a[i] is junk
419 for j
in b2j
.get(a
[i
], nothing
):
425 k
= newj2len
[j
] = j2lenget(j
-1, 0) + 1
427 besti
, bestj
, bestsize
= i
-k
+1, j
-k
+1, k
430 # Extend the best by non-junk elements on each end. In particular,
431 # "popular" non-junk elements aren't in b2j, which greatly speeds
432 # the inner loop above, but also means "the best" match so far
433 # doesn't contain any junk *or* popular non-junk elements.
434 while besti
> alo
and bestj
> blo
and \
435 not isbjunk(b
[bestj
-1]) and \
436 a
[besti
-1] == b
[bestj
-1]:
437 besti
, bestj
, bestsize
= besti
-1, bestj
-1, bestsize
+1
438 while besti
+bestsize
< ahi
and bestj
+bestsize
< bhi
and \
439 not isbjunk(b
[bestj
+bestsize
]) and \
440 a
[besti
+bestsize
] == b
[bestj
+bestsize
]:
443 # Now that we have a wholly interesting match (albeit possibly
444 # empty!), we may as well suck up the matching junk on each
445 # side of it too. Can't think of a good reason not to, and it
446 # saves post-processing the (possibly considerable) expense of
447 # figuring out what to do with it. In the case of an empty
448 # interesting match, this is clearly the right thing to do,
449 # because no other kind of match is possible in the regions.
450 while besti
> alo
and bestj
> blo
and \
451 isbjunk(b
[bestj
-1]) and \
452 a
[besti
-1] == b
[bestj
-1]:
453 besti
, bestj
, bestsize
= besti
-1, bestj
-1, bestsize
+1
454 while besti
+bestsize
< ahi
and bestj
+bestsize
< bhi
and \
455 isbjunk(b
[bestj
+bestsize
]) and \
456 a
[besti
+bestsize
] == b
[bestj
+bestsize
]:
457 bestsize
= bestsize
+ 1
459 return Match(besti
, bestj
, bestsize
)
461 def get_matching_blocks(self
):
462 """Return list of triples describing matching subsequences.
464 Each triple is of the form (i, j, n), and means that
465 a[i:i+n] == b[j:j+n]. The triples are monotonically increasing in
466 i and in j. New in Python 2.5, it's also guaranteed that if
467 (i, j, n) and (i', j', n') are adjacent triples in the list, and
468 the second is not the last triple in the list, then i+n != i' or
469 j+n != j'. IOW, adjacent triples never describe adjacent equal
472 The last triple is a dummy, (len(a), len(b), 0), and is the only
475 >>> s = SequenceMatcher(None, "abxcd", "abcd")
476 >>> s.get_matching_blocks()
477 [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
480 if self
.matching_blocks
is not None:
481 return self
.matching_blocks
482 la
, lb
= len(self
.a
), len(self
.b
)
484 # This is most naturally expressed as a recursive algorithm, but
485 # at least one user bumped into extreme use cases that exceeded
486 # the recursion limit on their box. So, now we maintain a list
487 # ('queue`) of blocks we still need to look at, and append partial
488 # results to `matching_blocks` in a loop; the matches are sorted
490 queue
= [(0, la
, 0, lb
)]
493 alo
, ahi
, blo
, bhi
= queue
.pop()
494 i
, j
, k
= x
= self
.find_longest_match(alo
, ahi
, blo
, bhi
)
495 # a[alo:i] vs b[blo:j] unknown
496 # a[i:i+k] same as b[j:j+k]
497 # a[i+k:ahi] vs b[j+k:bhi] unknown
498 if k
: # if k is 0, there was no matching block
499 matching_blocks
.append(x
)
500 if alo
< i
and blo
< j
:
501 queue
.append((alo
, i
, blo
, j
))
502 if i
+k
< ahi
and j
+k
< bhi
:
503 queue
.append((i
+k
, ahi
, j
+k
, bhi
))
504 matching_blocks
.sort()
506 # It's possible that we have adjacent equal blocks in the
507 # matching_blocks list now. Starting with 2.5, this code was added
511 for i2
, j2
, k2
in matching_blocks
:
512 # Is this block adjacent to i1, j1, k1?
513 if i1
+ k1
== i2
and j1
+ k1
== j2
:
514 # Yes, so collapse them -- this just increases the length of
515 # the first block by the length of the second, and the first
516 # block so lengthened remains the block to compare against.
519 # Not adjacent. Remember the first block (k1==0 means it's
520 # the dummy we started with), and make the second block the
521 # new block to compare against.
523 non_adjacent
.append((i1
, j1
, k1
))
524 i1
, j1
, k1
= i2
, j2
, k2
526 non_adjacent
.append((i1
, j1
, k1
))
528 non_adjacent
.append( (la
, lb
, 0) )
529 self
.matching_blocks
= non_adjacent
530 return map(Match
._make
, self
.matching_blocks
)
532 def get_opcodes(self
):
533 """Return list of 5-tuples describing how to turn a into b.
535 Each tuple is of the form (tag, i1, i2, j1, j2). The first tuple
536 has i1 == j1 == 0, and remaining tuples have i1 == the i2 from the
537 tuple preceding it, and likewise for j1 == the previous j2.
539 The tags are strings, with these meanings:
541 'replace': a[i1:i2] should be replaced by b[j1:j2]
542 'delete': a[i1:i2] should be deleted.
543 Note that j1==j2 in this case.
544 'insert': b[j1:j2] should be inserted at a[i1:i1].
545 Note that i1==i2 in this case.
546 'equal': a[i1:i2] == b[j1:j2]
550 >>> s = SequenceMatcher(None, a, b)
551 >>> for tag, i1, i2, j1, j2 in s.get_opcodes():
552 ... print ("%7s a[%d:%d] (%s) b[%d:%d] (%s)" %
553 ... (tag, i1, i2, a[i1:i2], j1, j2, b[j1:j2]))
554 delete a[0:1] (q) b[0:0] ()
555 equal a[1:3] (ab) b[0:2] (ab)
556 replace a[3:4] (x) b[2:3] (y)
557 equal a[4:6] (cd) b[3:5] (cd)
558 insert a[6:6] () b[5:6] (f)
561 if self
.opcodes
is not None:
564 self
.opcodes
= answer
= []
565 for ai
, bj
, size
in self
.get_matching_blocks():
566 # invariant: we've pumped out correct diffs to change
567 # a[:i] into b[:j], and the next matching block is
568 # a[ai:ai+size] == b[bj:bj+size]. So we need to pump
569 # out a diff to change a[i:ai] into b[j:bj], pump out
570 # the matching block, and move (i,j) beyond the match
572 if i
< ai
and j
< bj
:
579 answer
.append( (tag
, i
, ai
, j
, bj
) )
580 i
, j
= ai
+size
, bj
+size
581 # the list of matching blocks is terminated by a
582 # sentinel with size 0
584 answer
.append( ('equal', ai
, i
, bj
, j
) )
587 def get_grouped_opcodes(self
, n
=3):
588 """ Isolate change clusters by eliminating ranges with no changes.
590 Return a generator of groups with upto n lines of context.
591 Each group is in the same format as returned by get_opcodes().
593 >>> from pprint import pprint
594 >>> a = map(str, range(1,40))
596 >>> b[8:8] = ['i'] # Make an insertion
597 >>> b[20] += 'x' # Make a replacement
598 >>> b[23:28] = [] # Make a deletion
599 >>> b[30] += 'y' # Make another replacement
600 >>> pprint(list(SequenceMatcher(None,a,b).get_grouped_opcodes()))
601 [[('equal', 5, 8, 5, 8), ('insert', 8, 8, 8, 9), ('equal', 8, 11, 9, 12)],
602 [('equal', 16, 19, 17, 20),
603 ('replace', 19, 20, 20, 21),
604 ('equal', 20, 22, 21, 23),
605 ('delete', 22, 27, 23, 23),
606 ('equal', 27, 30, 23, 26)],
607 [('equal', 31, 34, 27, 30),
608 ('replace', 34, 35, 30, 31),
609 ('equal', 35, 38, 31, 34)]]
612 codes
= self
.get_opcodes()
614 codes
= [("equal", 0, 1, 0, 1)]
615 # Fixup leading and trailing groups if they show no changes.
616 if codes
[0][0] == 'equal':
617 tag
, i1
, i2
, j1
, j2
= codes
[0]
618 codes
[0] = tag
, max(i1
, i2
-n
), i2
, max(j1
, j2
-n
), j2
619 if codes
[-1][0] == 'equal':
620 tag
, i1
, i2
, j1
, j2
= codes
[-1]
621 codes
[-1] = tag
, i1
, min(i2
, i1
+n
), j1
, min(j2
, j1
+n
)
625 for tag
, i1
, i2
, j1
, j2
in codes
:
626 # End the current group and start a new one whenever
627 # there is a large range with no changes.
628 if tag
== 'equal' and i2
-i1
> nn
:
629 group
.append((tag
, i1
, min(i2
, i1
+n
), j1
, min(j2
, j1
+n
)))
632 i1
, j1
= max(i1
, i2
-n
), max(j1
, j2
-n
)
633 group
.append((tag
, i1
, i2
, j1
,j2
))
634 if group
and not (len(group
)==1 and group
[0][0] == 'equal'):
638 """Return a measure of the sequences' similarity (float in [0,1]).
640 Where T is the total number of elements in both sequences, and
641 M is the number of matches, this is 2.0*M / T.
642 Note that this is 1 if the sequences are identical, and 0 if
643 they have nothing in common.
645 .ratio() is expensive to compute if you haven't already computed
646 .get_matching_blocks() or .get_opcodes(), in which case you may
647 want to try .quick_ratio() or .real_quick_ratio() first to get an
650 >>> s = SequenceMatcher(None, "abcd", "bcde")
655 >>> s.real_quick_ratio()
659 matches
= reduce(lambda sum, triple
: sum + triple
[-1],
660 self
.get_matching_blocks(), 0)
661 return _calculate_ratio(matches
, len(self
.a
) + len(self
.b
))
663 def quick_ratio(self
):
664 """Return an upper bound on ratio() relatively quickly.
666 This isn't defined beyond that it is an upper bound on .ratio(), and
667 is faster to compute.
670 # viewing a and b as multisets, set matches to the cardinality
671 # of their intersection; this counts the number of matches
672 # without regard to order, so is clearly an upper bound
673 if self
.fullbcount
is None:
674 self
.fullbcount
= fullbcount
= {}
676 fullbcount
[elt
] = fullbcount
.get(elt
, 0) + 1
677 fullbcount
= self
.fullbcount
678 # avail[x] is the number of times x appears in 'b' less the
679 # number of times we've seen it in 'a' so far ... kinda
681 availhas
, matches
= avail
.__contains
__, 0
686 numb
= fullbcount
.get(elt
, 0)
687 avail
[elt
] = numb
- 1
689 matches
= matches
+ 1
690 return _calculate_ratio(matches
, len(self
.a
) + len(self
.b
))
692 def real_quick_ratio(self
):
693 """Return an upper bound on ratio() very quickly.
695 This isn't defined beyond that it is an upper bound on .ratio(), and
696 is faster to compute than either .ratio() or .quick_ratio().
699 la
, lb
= len(self
.a
), len(self
.b
)
700 # can't have more matches than the number of elements in the
702 return _calculate_ratio(min(la
, lb
), la
+ lb
)
704 def get_close_matches(word
, possibilities
, n
=3, cutoff
=0.6):
705 """Use SequenceMatcher to return list of the best "good enough" matches.
707 word is a sequence for which close matches are desired (typically a
710 possibilities is a list of sequences against which to match word
711 (typically a list of strings).
713 Optional arg n (default 3) is the maximum number of close matches to
714 return. n must be > 0.
716 Optional arg cutoff (default 0.6) is a float in [0, 1]. Possibilities
717 that don't score at least that similar to word are ignored.
719 The best (no more than n) matches among the possibilities are returned
720 in a list, sorted by similarity score, most similar first.
722 >>> get_close_matches("appel", ["ape", "apple", "peach", "puppy"])
724 >>> import keyword as _keyword
725 >>> get_close_matches("wheel", _keyword.kwlist)
727 >>> get_close_matches("apple", _keyword.kwlist)
729 >>> get_close_matches("accept", _keyword.kwlist)
734 raise ValueError("n must be > 0: %r" % (n
,))
735 if not 0.0 <= cutoff
<= 1.0:
736 raise ValueError("cutoff must be in [0.0, 1.0]: %r" % (cutoff
,))
738 s
= SequenceMatcher()
740 for x
in possibilities
:
742 if s
.real_quick_ratio() >= cutoff
and \
743 s
.quick_ratio() >= cutoff
and \
745 result
.append((s
.ratio(), x
))
747 # Move the best scorers to head of list
748 result
= heapq
.nlargest(n
, result
)
749 # Strip scores for the best n matches
750 return [x
for score
, x
in result
]
752 def _count_leading(line
, ch
):
754 Return number of `ch` characters at the start of `line`.
758 >>> _count_leading(' abc', ' ')
763 while i
< n
and line
[i
] == ch
:
769 Differ is a class for comparing sequences of lines of text, and
770 producing human-readable differences or deltas. Differ uses
771 SequenceMatcher both to compare sequences of lines, and to compare
772 sequences of characters within similar (near-matching) lines.
774 Each line of a Differ delta begins with a two-letter code:
776 '- ' line unique to sequence 1
777 '+ ' line unique to sequence 2
778 ' ' line common to both sequences
779 '? ' line not present in either input sequence
781 Lines beginning with '? ' attempt to guide the eye to intraline
782 differences, and were not present in either input sequence. These lines
783 can be confusing if the sequences contain tab characters.
785 Note that Differ makes no claim to produce a *minimal* diff. To the
786 contrary, minimal diffs are often counter-intuitive, because they synch
787 up anywhere possible, sometimes accidental matches 100 pages apart.
788 Restricting synch points to contiguous matches preserves some notion of
789 locality, at the occasional cost of producing a longer diff.
791 Example: Comparing two texts.
793 First we set up the texts, sequences of individual single-line strings
794 ending with newlines (such sequences can also be obtained from the
795 `readlines()` method of file-like objects):
797 >>> text1 = ''' 1. Beautiful is better than ugly.
798 ... 2. Explicit is better than implicit.
799 ... 3. Simple is better than complex.
800 ... 4. Complex is better than complicated.
801 ... '''.splitlines(1)
806 >>> text2 = ''' 1. Beautiful is better than ugly.
807 ... 3. Simple is better than complex.
808 ... 4. Complicated is better than complex.
809 ... 5. Flat is better than nested.
810 ... '''.splitlines(1)
812 Next we instantiate a Differ object:
816 Note that when instantiating a Differ object we may pass functions to
817 filter out line and character 'junk'. See Differ.__init__ for details.
819 Finally, we compare the two:
821 >>> result = list(d.compare(text1, text2))
823 'result' is a list of strings, so let's pretty-print it:
825 >>> from pprint import pprint as _pprint
827 [' 1. Beautiful is better than ugly.\n',
828 '- 2. Explicit is better than implicit.\n',
829 '- 3. Simple is better than complex.\n',
830 '+ 3. Simple is better than complex.\n',
832 '- 4. Complex is better than complicated.\n',
834 '+ 4. Complicated is better than complex.\n',
836 '+ 5. Flat is better than nested.\n']
838 As a single multi-line string it looks like this:
840 >>> print ''.join(result),
841 1. Beautiful is better than ugly.
842 - 2. Explicit is better than implicit.
843 - 3. Simple is better than complex.
844 + 3. Simple is better than complex.
846 - 4. Complex is better than complicated.
848 + 4. Complicated is better than complex.
850 + 5. Flat is better than nested.
854 __init__(linejunk=None, charjunk=None)
855 Construct a text differencer, with optional filters.
858 Compare two sequences of lines; generate the resulting delta.
861 def __init__(self
, linejunk
=None, charjunk
=None):
863 Construct a text differencer, with optional filters.
865 The two optional keyword parameters are for filter functions:
867 - `linejunk`: A function that should accept a single string argument,
868 and return true iff the string is junk. The module-level function
869 `IS_LINE_JUNK` may be used to filter out lines without visible
870 characters, except for at most one splat ('#'). It is recommended
871 to leave linejunk None; as of Python 2.3, the underlying
872 SequenceMatcher class has grown an adaptive notion of "noise" lines
873 that's better than any static definition the author has ever been
876 - `charjunk`: A function that should accept a string of length 1. The
877 module-level function `IS_CHARACTER_JUNK` may be used to filter out
878 whitespace characters (a blank or tab; **note**: bad idea to include
879 newline in this!). Use of IS_CHARACTER_JUNK is recommended.
882 self
.linejunk
= linejunk
883 self
.charjunk
= charjunk
885 def compare(self
, a
, b
):
887 Compare two sequences of lines; generate the resulting delta.
889 Each sequence must contain individual single-line strings ending with
890 newlines. Such sequences can be obtained from the `readlines()` method
891 of file-like objects. The delta generated also consists of newline-
892 terminated strings, ready to be printed as-is via the writeline()
893 method of a file-like object.
897 >>> print ''.join(Differ().compare('one\ntwo\nthree\n'.splitlines(1),
898 ... 'ore\ntree\nemu\n'.splitlines(1))),
910 cruncher
= SequenceMatcher(self
.linejunk
, a
, b
)
911 for tag
, alo
, ahi
, blo
, bhi
in cruncher
.get_opcodes():
913 g
= self
._fancy
_replace
(a
, alo
, ahi
, b
, blo
, bhi
)
914 elif tag
== 'delete':
915 g
= self
._dump
('-', a
, alo
, ahi
)
916 elif tag
== 'insert':
917 g
= self
._dump
('+', b
, blo
, bhi
)
919 g
= self
._dump
(' ', a
, alo
, ahi
)
921 raise ValueError, 'unknown tag %r' % (tag
,)
926 def _dump(self
, tag
, x
, lo
, hi
):
927 """Generate comparison results for a same-tagged range."""
928 for i
in xrange(lo
, hi
):
929 yield '%s %s' % (tag
, x
[i
])
931 def _plain_replace(self
, a
, alo
, ahi
, b
, blo
, bhi
):
932 assert alo
< ahi
and blo
< bhi
933 # dump the shorter block first -- reduces the burden on short-term
934 # memory if the blocks are of very different sizes
935 if bhi
- blo
< ahi
- alo
:
936 first
= self
._dump
('+', b
, blo
, bhi
)
937 second
= self
._dump
('-', a
, alo
, ahi
)
939 first
= self
._dump
('-', a
, alo
, ahi
)
940 second
= self
._dump
('+', b
, blo
, bhi
)
942 for g
in first
, second
:
946 def _fancy_replace(self
, a
, alo
, ahi
, b
, blo
, bhi
):
948 When replacing one block of lines with another, search the blocks
949 for *similar* lines; the best-matching pair (if any) is used as a
950 synch point, and intraline difference marking is done on the
951 similar pair. Lots of work, but often worth it.
956 >>> results = d._fancy_replace(['abcDefghiJkl\n'], 0, 1,
957 ... ['abcdefGhijkl\n'], 0, 1)
958 >>> print ''.join(results),
965 # don't synch up unless the lines have a similarity score of at
966 # least cutoff; best_ratio tracks the best score seen so far
967 best_ratio
, cutoff
= 0.74, 0.75
968 cruncher
= SequenceMatcher(self
.charjunk
)
969 eqi
, eqj
= None, None # 1st indices of equal lines (if any)
971 # search for the pair that matches best without being identical
972 # (identical lines must be junk lines, & we don't want to synch up
973 # on junk -- unless we have to)
974 for j
in xrange(blo
, bhi
):
976 cruncher
.set_seq2(bj
)
977 for i
in xrange(alo
, ahi
):
983 cruncher
.set_seq1(ai
)
984 # computing similarity is expensive, so use the quick
985 # upper bounds first -- have seen this speed up messy
986 # compares by a factor of 3.
987 # note that ratio() is only expensive to compute the first
988 # time it's called on a sequence pair; the expensive part
989 # of the computation is cached by cruncher
990 if cruncher
.real_quick_ratio() > best_ratio
and \
991 cruncher
.quick_ratio() > best_ratio
and \
992 cruncher
.ratio() > best_ratio
:
993 best_ratio
, best_i
, best_j
= cruncher
.ratio(), i
, j
994 if best_ratio
< cutoff
:
995 # no non-identical "pretty close" pair
997 # no identical pair either -- treat it as a straight replace
998 for line
in self
._plain
_replace
(a
, alo
, ahi
, b
, blo
, bhi
):
1001 # no close pair, but an identical pair -- synch up on that
1002 best_i
, best_j
, best_ratio
= eqi
, eqj
, 1.0
1004 # there's a close pair, so forget the identical pair (if any)
1007 # a[best_i] very similar to b[best_j]; eqi is None iff they're not
1010 # pump out diffs from before the synch point
1011 for line
in self
._fancy
_helper
(a
, alo
, best_i
, b
, blo
, best_j
):
1014 # do intraline marking on the synch pair
1015 aelt
, belt
= a
[best_i
], b
[best_j
]
1017 # pump out a '-', '?', '+', '?' quad for the synched lines
1019 cruncher
.set_seqs(aelt
, belt
)
1020 for tag
, ai1
, ai2
, bj1
, bj2
in cruncher
.get_opcodes():
1021 la
, lb
= ai2
- ai1
, bj2
- bj1
1022 if tag
== 'replace':
1025 elif tag
== 'delete':
1027 elif tag
== 'insert':
1029 elif tag
== 'equal':
1033 raise ValueError, 'unknown tag %r' % (tag
,)
1034 for line
in self
._qformat
(aelt
, belt
, atags
, btags
):
1037 # the synch pair is identical
1040 # pump out diffs from after the synch point
1041 for line
in self
._fancy
_helper
(a
, best_i
+1, ahi
, b
, best_j
+1, bhi
):
1044 def _fancy_helper(self
, a
, alo
, ahi
, b
, blo
, bhi
):
1048 g
= self
._fancy
_replace
(a
, alo
, ahi
, b
, blo
, bhi
)
1050 g
= self
._dump
('-', a
, alo
, ahi
)
1052 g
= self
._dump
('+', b
, blo
, bhi
)
1057 def _qformat(self
, aline
, bline
, atags
, btags
):
1059 Format "?" output and deal with leading tabs.
1064 >>> results = d._qformat('\tabcDefghiJkl\n', '\tabcdefGhijkl\n',
1065 ... ' ^ ^ ^ ', ' ^ ^ ^ ')
1066 >>> for line in results: print repr(line)
1068 '- \tabcDefghiJkl\n'
1070 '+ \tabcdefGhijkl\n'
1074 # Can hurt, but will probably help most of the time.
1075 common
= min(_count_leading(aline
, "\t"),
1076 _count_leading(bline
, "\t"))
1077 common
= min(common
, _count_leading(atags
[:common
], " "))
1078 common
= min(common
, _count_leading(btags
[:common
], " "))
1079 atags
= atags
[common
:].rstrip()
1080 btags
= btags
[common
:].rstrip()
1084 yield "? %s%s\n" % ("\t" * common
, atags
)
1088 yield "? %s%s\n" % ("\t" * common
, btags
)
1090 # With respect to junk, an earlier version of ndiff simply refused to
1091 # *start* a match with a junk element. The result was cases like this:
1092 # before: private Thread currentThread;
1093 # after: private volatile Thread currentThread;
1094 # If you consider whitespace to be junk, the longest contiguous match
1095 # not starting with junk is "e Thread currentThread". So ndiff reported
1096 # that "e volatil" was inserted between the 't' and the 'e' in "private".
1097 # While an accurate view, to people that's absurd. The current version
1098 # looks for matching blocks that are entirely junk-free, then extends the
1099 # longest one of those as far as possible but only with matching junk.
1100 # So now "currentThread" is matched, then extended to suck up the
1101 # preceding blank; then "private" is matched, and extended to suck up the
1102 # following blank; then "Thread" is matched; and finally ndiff reports
1103 # that "volatile " was inserted before "Thread". The only quibble
1104 # remaining is that perhaps it was really the case that " volatile"
1105 # was inserted after "private". I can live with that <wink>.
1109 def IS_LINE_JUNK(line
, pat
=re
.compile(r
"\s*#?\s*$").match
):
1111 Return 1 for ignorable line: iff `line` is blank or contains a single '#'.
1115 >>> IS_LINE_JUNK('\n')
1117 >>> IS_LINE_JUNK(' # \n')
1119 >>> IS_LINE_JUNK('hello\n')
1123 return pat(line
) is not None
1125 def IS_CHARACTER_JUNK(ch
, ws
=" \t"):
1127 Return 1 for ignorable character: iff `ch` is a space or tab.
1131 >>> IS_CHARACTER_JUNK(' ')
1133 >>> IS_CHARACTER_JUNK('\t')
1135 >>> IS_CHARACTER_JUNK('\n')
1137 >>> IS_CHARACTER_JUNK('x')
1144 def unified_diff(a
, b
, fromfile
='', tofile
='', fromfiledate
='',
1145 tofiledate
='', n
=3, lineterm
='\n'):
1147 Compare two sequences of lines; generate the delta as a unified diff.
1149 Unified diffs are a compact way of showing line changes and a few
1150 lines of context. The number of context lines is set by 'n' which
1153 By default, the diff control lines (those with ---, +++, or @@) are
1154 created with a trailing newline. This is helpful so that inputs
1155 created from file.readlines() result in diffs that are suitable for
1156 file.writelines() since both the inputs and outputs have trailing
1159 For inputs that do not have trailing newlines, set the lineterm
1160 argument to "" so that the output will be uniformly newline free.
1162 The unidiff format normally has a header for filenames and modification
1163 times. Any or all of these may be specified using strings for
1164 'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'.
1165 The modification times are normally expressed in the ISO 8601 format.
1169 >>> for line in unified_diff('one two three four'.split(),
1170 ... 'zero one tree four'.split(), 'Original', 'Current',
1171 ... '2005-01-26 23:30:50', '2010-04-02 10:20:52',
1173 ... print line # doctest: +NORMALIZE_WHITESPACE
1174 --- Original 2005-01-26 23:30:50
1175 +++ Current 2010-04-02 10:20:52
1186 for group
in SequenceMatcher(None,a
,b
).get_grouped_opcodes(n
):
1188 fromdate
= '\t%s' % fromfiledate
if fromfiledate
else ''
1189 todate
= '\t%s' % tofiledate
if tofiledate
else ''
1190 yield '--- %s%s%s' % (fromfile
, fromdate
, lineterm
)
1191 yield '+++ %s%s%s' % (tofile
, todate
, lineterm
)
1193 i1
, i2
, j1
, j2
= group
[0][1], group
[-1][2], group
[0][3], group
[-1][4]
1194 yield "@@ -%d,%d +%d,%d @@%s" % (i1
+1, i2
-i1
, j1
+1, j2
-j1
, lineterm
)
1195 for tag
, i1
, i2
, j1
, j2
in group
:
1197 for line
in a
[i1
:i2
]:
1200 if tag
== 'replace' or tag
== 'delete':
1201 for line
in a
[i1
:i2
]:
1203 if tag
== 'replace' or tag
== 'insert':
1204 for line
in b
[j1
:j2
]:
1207 # See http://www.unix.org/single_unix_specification/
1208 def context_diff(a
, b
, fromfile
='', tofile
='',
1209 fromfiledate
='', tofiledate
='', n
=3, lineterm
='\n'):
1211 Compare two sequences of lines; generate the delta as a context diff.
1213 Context diffs are a compact way of showing line changes and a few
1214 lines of context. The number of context lines is set by 'n' which
1217 By default, the diff control lines (those with *** or ---) are
1218 created with a trailing newline. This is helpful so that inputs
1219 created from file.readlines() result in diffs that are suitable for
1220 file.writelines() since both the inputs and outputs have trailing
1223 For inputs that do not have trailing newlines, set the lineterm
1224 argument to "" so that the output will be uniformly newline free.
1226 The context diff format normally has a header for filenames and
1227 modification times. Any or all of these may be specified using
1228 strings for 'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'.
1229 The modification times are normally expressed in the ISO 8601 format.
1230 If not specified, the strings default to blanks.
1234 >>> print ''.join(context_diff('one\ntwo\nthree\nfour\n'.splitlines(1),
1235 ... 'zero\none\ntree\nfour\n'.splitlines(1), 'Original', 'Current')),
1252 prefixmap
= {'insert':'+ ', 'delete':'- ', 'replace':'! ', 'equal':' '}
1253 for group
in SequenceMatcher(None,a
,b
).get_grouped_opcodes(n
):
1255 fromdate
= '\t%s' % fromfiledate
if fromfiledate
else ''
1256 todate
= '\t%s' % tofiledate
if tofiledate
else ''
1257 yield '*** %s%s%s' % (fromfile
, fromdate
, lineterm
)
1258 yield '--- %s%s%s' % (tofile
, todate
, lineterm
)
1261 yield '***************%s' % (lineterm
,)
1262 if group
[-1][2] - group
[0][1] >= 2:
1263 yield '*** %d,%d ****%s' % (group
[0][1]+1, group
[-1][2], lineterm
)
1265 yield '*** %d ****%s' % (group
[-1][2], lineterm
)
1266 visiblechanges
= [e
for e
in group
if e
[0] in ('replace', 'delete')]
1268 for tag
, i1
, i2
, _
, _
in group
:
1270 for line
in a
[i1
:i2
]:
1271 yield prefixmap
[tag
] + line
1273 if group
[-1][4] - group
[0][3] >= 2:
1274 yield '--- %d,%d ----%s' % (group
[0][3]+1, group
[-1][4], lineterm
)
1276 yield '--- %d ----%s' % (group
[-1][4], lineterm
)
1277 visiblechanges
= [e
for e
in group
if e
[0] in ('replace', 'insert')]
1279 for tag
, _
, _
, j1
, j2
in group
:
1281 for line
in b
[j1
:j2
]:
1282 yield prefixmap
[tag
] + line
1284 def ndiff(a
, b
, linejunk
=None, charjunk
=IS_CHARACTER_JUNK
):
1286 Compare `a` and `b` (lists of strings); return a `Differ`-style delta.
1288 Optional keyword parameters `linejunk` and `charjunk` are for filter
1289 functions (or None):
1291 - linejunk: A function that should accept a single string argument, and
1292 return true iff the string is junk. The default is None, and is
1293 recommended; as of Python 2.3, an adaptive notion of "noise" lines is
1294 used that does a good job on its own.
1296 - charjunk: A function that should accept a string of length 1. The
1297 default is module-level function IS_CHARACTER_JUNK, which filters out
1298 whitespace characters (a blank or tab; note: bad idea to include newline
1301 Tools/scripts/ndiff.py is a command-line front-end to this function.
1305 >>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
1306 ... 'ore\ntree\nemu\n'.splitlines(1))
1307 >>> print ''.join(diff),
1318 return Differ(linejunk
, charjunk
).compare(a
, b
)
1320 def _mdiff(fromlines
, tolines
, context
=None, linejunk
=None,
1321 charjunk
=IS_CHARACTER_JUNK
):
1322 r
"""Returns generator yielding marked up from/to side by side differences.
1325 fromlines -- list of text lines to compared to tolines
1326 tolines -- list of text lines to be compared to fromlines
1327 context -- number of context lines to display on each side of difference,
1328 if None, all from/to text lines will be generated.
1329 linejunk -- passed on to ndiff (see ndiff documentation)
1330 charjunk -- passed on to ndiff (see ndiff documentation)
1332 This function returns an interator which returns a tuple:
1333 (from line tuple, to line tuple, boolean flag)
1335 from/to line tuple -- (line num, line text)
1336 line num -- integer or None (to indicate a context separation)
1337 line text -- original line text with following markers inserted:
1338 '\0+' -- marks start of added text
1339 '\0-' -- marks start of deleted text
1340 '\0^' -- marks start of changed text
1341 '\1' -- marks end of added/deleted/changed text
1343 boolean flag -- None indicates context separation, True indicates
1344 either "from" or "to" line contains a change, otherwise False.
1346 This function/iterator was originally developed to generate side by side
1347 file difference for making HTML pages (see HtmlDiff class for example
1350 Note, this function utilizes the ndiff function to generate the side by
1351 side difference markup. Optional ndiff arguments may be passed to this
1352 function and they in turn will be passed to ndiff.
1356 # regular expression for finding intraline change indices
1357 change_re
= re
.compile('(\++|\-+|\^+)')
1359 # create the difference iterator to generate the differences
1360 diff_lines_iterator
= ndiff(fromlines
,tolines
,linejunk
,charjunk
)
1362 def _make_line(lines
, format_key
, side
, num_lines
=[0,0]):
1363 """Returns line of text with user's change markup and line formatting.
1365 lines -- list of lines from the ndiff generator to produce a line of
1366 text from. When producing the line of text to return, the
1367 lines used are removed from this list.
1368 format_key -- '+' return first line in list with "add" markup around
1370 '-' return first line in list with "delete" markup around
1372 '?' return first line in list with add/delete/change
1373 intraline markup (indices obtained from second line)
1374 None return first line in list with no markup
1375 side -- indice into the num_lines list (0=from,1=to)
1376 num_lines -- from/to current line number. This is NOT intended to be a
1377 passed parameter. It is present as a keyword argument to
1378 maintain memory of the current line numbers between calls
1381 Note, this function is purposefully not defined at the module scope so
1382 that data it needs from its parent function (within whose context it
1383 is defined) does not need to be of module scope.
1385 num_lines
[side
] += 1
1386 # Handle case where no user markup is to be added, just return line of
1387 # text with user's line format to allow for usage of the line number.
1388 if format_key
is None:
1389 return (num_lines
[side
],lines
.pop(0)[2:])
1390 # Handle case of intraline changes
1391 if format_key
== '?':
1392 text
, markers
= lines
.pop(0), lines
.pop(0)
1393 # find intraline changes (store change type and indices in tuples)
1395 def record_sub_info(match_object
,sub_info
=sub_info
):
1396 sub_info
.append([match_object
.group(1)[0],match_object
.span()])
1397 return match_object
.group(1)
1398 change_re
.sub(record_sub_info
,markers
)
1399 # process each tuple inserting our special marks that won't be
1400 # noticed by an xml/html escaper.
1401 for key
,(begin
,end
) in sub_info
[::-1]:
1402 text
= text
[0:begin
]+'\0'+key
+text
[begin
:end
]+'\1'+text
[end
:]
1404 # Handle case of add/delete entire line
1406 text
= lines
.pop(0)[2:]
1407 # if line of text is just a newline, insert a space so there is
1408 # something for the user to highlight and see.
1411 # insert marks that won't be noticed by an xml/html escaper.
1412 text
= '\0' + format_key
+ text
+ '\1'
1413 # Return line of text, first allow user's line formatter to do its
1414 # thing (such as adding the line number) then replace the special
1415 # marks with what the user's change markup.
1416 return (num_lines
[side
],text
)
1418 def _line_iterator():
1419 """Yields from/to lines of text with a change indication.
1421 This function is an iterator. It itself pulls lines from a
1422 differencing iterator, processes them and yields them. When it can
1423 it yields both a "from" and a "to" line, otherwise it will yield one
1424 or the other. In addition to yielding the lines of from/to text, a
1425 boolean flag is yielded to indicate if the text line(s) have
1426 differences in them.
1428 Note, this function is purposefully not defined at the module scope so
1429 that data it needs from its parent function (within whose context it
1430 is defined) does not need to be of module scope.
1433 num_blanks_pending
, num_blanks_to_yield
= 0, 0
1435 # Load up next 4 lines so we can look ahead, create strings which
1436 # are a concatenation of the first character of each of the 4 lines
1437 # so we can do some very readable comparisons.
1438 while len(lines
) < 4:
1440 lines
.append(diff_lines_iterator
.next())
1441 except StopIteration:
1443 s
= ''.join([line
[0] for line
in lines
])
1444 if s
.startswith('X'):
1445 # When no more lines, pump out any remaining blank lines so the
1446 # corresponding add/delete lines get a matching blank line so
1447 # all line pairs get yielded at the next level.
1448 num_blanks_to_yield
= num_blanks_pending
1449 elif s
.startswith('-?+?'):
1450 # simple intraline change
1451 yield _make_line(lines
,'?',0), _make_line(lines
,'?',1), True
1453 elif s
.startswith('--++'):
1454 # in delete block, add block coming: we do NOT want to get
1455 # caught up on blank lines yet, just process the delete line
1456 num_blanks_pending
-= 1
1457 yield _make_line(lines
,'-',0), None, True
1459 elif s
.startswith(('--?+', '--+', '- ')):
1460 # in delete block and see a intraline change or unchanged line
1461 # coming: yield the delete line and then blanks
1462 from_line
,to_line
= _make_line(lines
,'-',0), None
1463 num_blanks_to_yield
,num_blanks_pending
= num_blanks_pending
-1,0
1464 elif s
.startswith('-+?'):
1466 yield _make_line(lines
,None,0), _make_line(lines
,'?',1), True
1468 elif s
.startswith('-?+'):
1470 yield _make_line(lines
,'?',0), _make_line(lines
,None,1), True
1472 elif s
.startswith('-'):
1474 num_blanks_pending
-= 1
1475 yield _make_line(lines
,'-',0), None, True
1477 elif s
.startswith('+--'):
1478 # in add block, delete block coming: we do NOT want to get
1479 # caught up on blank lines yet, just process the add line
1480 num_blanks_pending
+= 1
1481 yield None, _make_line(lines
,'+',1), True
1483 elif s
.startswith(('+ ', '+-')):
1484 # will be leaving an add block: yield blanks then add line
1485 from_line
, to_line
= None, _make_line(lines
,'+',1)
1486 num_blanks_to_yield
,num_blanks_pending
= num_blanks_pending
+1,0
1487 elif s
.startswith('+'):
1488 # inside an add block, yield the add line
1489 num_blanks_pending
+= 1
1490 yield None, _make_line(lines
,'+',1), True
1492 elif s
.startswith(' '):
1493 # unchanged text, yield it to both sides
1494 yield _make_line(lines
[:],None,0),_make_line(lines
,None,1),False
1496 # Catch up on the blank lines so when we yield the next from/to
1497 # pair, they are lined up.
1498 while(num_blanks_to_yield
< 0):
1499 num_blanks_to_yield
+= 1
1500 yield None,('','\n'),True
1501 while(num_blanks_to_yield
> 0):
1502 num_blanks_to_yield
-= 1
1503 yield ('','\n'),None,True
1504 if s
.startswith('X'):
1507 yield from_line
,to_line
,True
1509 def _line_pair_iterator():
1510 """Yields from/to lines of text with a change indication.
1512 This function is an iterator. It itself pulls lines from the line
1513 iterator. Its difference from that iterator is that this function
1514 always yields a pair of from/to text lines (with the change
1515 indication). If necessary it will collect single from/to lines
1516 until it has a matching pair from/to pair to yield.
1518 Note, this function is purposefully not defined at the module scope so
1519 that data it needs from its parent function (within whose context it
1520 is defined) does not need to be of module scope.
1522 line_iterator
= _line_iterator()
1523 fromlines
,tolines
=[],[]
1525 # Collecting lines of text until we have a from/to pair
1526 while (len(fromlines
)==0 or len(tolines
)==0):
1527 from_line
, to_line
, found_diff
=line_iterator
.next()
1528 if from_line
is not None:
1529 fromlines
.append((from_line
,found_diff
))
1530 if to_line
is not None:
1531 tolines
.append((to_line
,found_diff
))
1532 # Once we have a pair, remove them from the collection and yield it
1533 from_line
, fromDiff
= fromlines
.pop(0)
1534 to_line
, to_diff
= tolines
.pop(0)
1535 yield (from_line
,to_line
,fromDiff
or to_diff
)
1537 # Handle case where user does not want context differencing, just yield
1538 # them up without doing anything else with them.
1539 line_pair_iterator
= _line_pair_iterator()
1542 yield line_pair_iterator
.next()
1543 # Handle case where user wants context differencing. We must do some
1544 # storage of lines until we know for sure that they are to be yielded.
1549 # Store lines up until we find a difference, note use of a
1550 # circular queue because we only need to keep around what
1551 # we need for context.
1552 index
, contextLines
= 0, [None]*(context
)
1554 while(found_diff
is False):
1555 from_line
, to_line
, found_diff
= line_pair_iterator
.next()
1557 contextLines
[i
] = (from_line
, to_line
, found_diff
)
1559 # Yield lines that we have collected so far, but first yield
1560 # the user's separator.
1562 yield None, None, None
1563 lines_to_write
= context
1565 lines_to_write
= index
1567 while(lines_to_write
):
1570 yield contextLines
[i
]
1572 # Now yield the context lines after the change
1573 lines_to_write
= context
-1
1574 while(lines_to_write
):
1575 from_line
, to_line
, found_diff
= line_pair_iterator
.next()
1576 # If another change within the context, extend the context
1578 lines_to_write
= context
-1
1581 yield from_line
, to_line
, found_diff
1584 _file_template
= """
1585 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
1586 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
1591 <meta http-equiv="Content-Type"
1592 content="text/html; charset=ISO-8859-1" />
1594 <style type="text/css">%(styles)s
1605 table.diff {font-family:Courier; border:medium;}
1606 .diff_header {background-color:#e0e0e0}
1607 td.diff_header {text-align:right}
1608 .diff_next {background-color:#c0c0c0}
1609 .diff_add {background-color:#aaffaa}
1610 .diff_chg {background-color:#ffff77}
1611 .diff_sub {background-color:#ffaaaa}"""
1613 _table_template
= """
1614 <table class="diff" id="difflib_chg_%(prefix)s_top"
1615 cellspacing="0" cellpadding="0" rules="groups" >
1616 <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>
1617 <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>
1620 %(data_rows)s </tbody>
1624 <table class="diff" summary="Legends">
1625 <tr> <th colspan="2"> Legends </th> </tr>
1626 <tr> <td> <table border="" summary="Colors">
1627 <tr><th> Colors </th> </tr>
1628 <tr><td class="diff_add"> Added </td></tr>
1629 <tr><td class="diff_chg">Changed</td> </tr>
1630 <tr><td class="diff_sub">Deleted</td> </tr>
1632 <td> <table border="" summary="Links">
1633 <tr><th colspan="2"> Links </th> </tr>
1634 <tr><td>(f)irst change</td> </tr>
1635 <tr><td>(n)ext change</td> </tr>
1636 <tr><td>(t)op</td> </tr>
1640 class HtmlDiff(object):
1641 """For producing HTML side by side comparison with change highlights.
1643 This class can be used to create an HTML table (or a complete HTML file
1644 containing the table) showing a side by side, line by line comparison
1645 of text with inter-line and intra-line change highlights. The table can
1646 be generated in either full or contextual difference mode.
1648 The following methods are provided for HTML generation:
1650 make_table -- generates HTML for a single side by side table
1651 make_file -- generates complete HTML file with a single side by side table
1653 See tools/scripts/diff.py for an example usage of this class.
1656 _file_template
= _file_template
1658 _table_template
= _table_template
1662 def __init__(self
,tabsize
=8,wrapcolumn
=None,linejunk
=None,
1663 charjunk
=IS_CHARACTER_JUNK
):
1664 """HtmlDiff instance initializer
1667 tabsize -- tab stop spacing, defaults to 8.
1668 wrapcolumn -- column number where lines are broken and wrapped,
1669 defaults to None where lines are not wrapped.
1670 linejunk,charjunk -- keyword arguments passed into ndiff() (used to by
1671 HtmlDiff() to generate the side by side HTML differences). See
1672 ndiff() documentation for argument default values and descriptions.
1674 self
._tabsize
= tabsize
1675 self
._wrapcolumn
= wrapcolumn
1676 self
._linejunk
= linejunk
1677 self
._charjunk
= charjunk
1679 def make_file(self
,fromlines
,tolines
,fromdesc
='',todesc
='',context
=False,
1681 """Returns HTML file of side by side comparison with change highlights
1684 fromlines -- list of "from" lines
1685 tolines -- list of "to" lines
1686 fromdesc -- "from" file column header string
1687 todesc -- "to" file column header string
1688 context -- set to True for contextual differences (defaults to False
1689 which shows full differences).
1690 numlines -- number of context lines. When context is set True,
1691 controls number of lines displayed before and after the change.
1692 When context is False, controls the number of lines to place
1693 the "next" link anchors before the next change (so click of
1694 "next" link jumps to just before the change).
1697 return self
._file
_template
% dict(
1698 styles
= self
._styles
,
1699 legend
= self
._legend
,
1700 table
= self
.make_table(fromlines
,tolines
,fromdesc
,todesc
,
1701 context
=context
,numlines
=numlines
))
1703 def _tab_newline_replace(self
,fromlines
,tolines
):
1704 """Returns from/to line lists with tabs expanded and newlines removed.
1706 Instead of tab characters being replaced by the number of spaces
1707 needed to fill in to the next tab stop, this function will fill
1708 the space with tab characters. This is done so that the difference
1709 algorithms can identify changes in a file when tabs are replaced by
1710 spaces and vice versa. At the end of the HTML generation, the tab
1711 characters will be replaced with a nonbreakable space.
1713 def expand_tabs(line
):
1715 line
= line
.replace(' ','\0')
1716 # expand tabs into spaces
1717 line
= line
.expandtabs(self
._tabsize
)
1718 # relace spaces from expanded tabs back into tab characters
1719 # (we'll replace them with markup after we do differencing)
1720 line
= line
.replace(' ','\t')
1721 return line
.replace('\0',' ').rstrip('\n')
1722 fromlines
= [expand_tabs(line
) for line
in fromlines
]
1723 tolines
= [expand_tabs(line
) for line
in tolines
]
1724 return fromlines
,tolines
1726 def _split_line(self
,data_list
,line_num
,text
):
1727 """Builds list of text lines by splitting text lines at wrap point
1729 This function will determine if the input text line needs to be
1730 wrapped (split) into separate lines. If so, the first wrap point
1731 will be determined and the first line appended to the output
1732 text line list. This function is used recursively to handle
1733 the second part of the split line to further split it.
1735 # if blank line or context separator, just add it to the output list
1737 data_list
.append((line_num
,text
))
1740 # if line text doesn't need wrapping, just add it to the output list
1742 max = self
._wrapcolumn
1743 if (size
<= max) or ((size
-(text
.count('\0')*3)) <= max):
1744 data_list
.append((line_num
,text
))
1747 # scan text looking for the wrap point, keeping track if the wrap
1748 # point is inside markers
1752 while n
< max and i
< size
:
1757 elif text
[i
] == '\1':
1764 # wrap point is inside text, break it up into separate lines
1768 # if wrap point is inside markers, place end marker at end of first
1769 # line and start marker at beginning of second line because each
1770 # line will have its own table tag markup around it.
1772 line1
= line1
+ '\1'
1773 line2
= '\0' + mark
+ line2
1775 # tack on first line onto the output list
1776 data_list
.append((line_num
,line1
))
1778 # use this routine again to wrap the remaining text
1779 self
._split
_line
(data_list
,'>',line2
)
1781 def _line_wrapper(self
,diffs
):
1782 """Returns iterator that splits (wraps) mdiff text lines"""
1784 # pull from/to data and flags from mdiff iterator
1785 for fromdata
,todata
,flag
in diffs
:
1786 # check for context separators and pass them through
1788 yield fromdata
,todata
,flag
1790 (fromline
,fromtext
),(toline
,totext
) = fromdata
,todata
1791 # for each from/to line split it at the wrap column to form
1792 # list of text lines.
1793 fromlist
,tolist
= [],[]
1794 self
._split
_line
(fromlist
,fromline
,fromtext
)
1795 self
._split
_line
(tolist
,toline
,totext
)
1796 # yield from/to line in pairs inserting blank lines as
1797 # necessary when one side has more wrapped lines
1798 while fromlist
or tolist
:
1800 fromdata
= fromlist
.pop(0)
1804 todata
= tolist
.pop(0)
1807 yield fromdata
,todata
,flag
1809 def _collect_lines(self
,diffs
):
1810 """Collects mdiff output into separate lists
1812 Before storing the mdiff from/to data into a list, it is converted
1813 into a single line of text with HTML markup.
1816 fromlist
,tolist
,flaglist
= [],[],[]
1817 # pull from/to data and flags from mdiff style iterator
1818 for fromdata
,todata
,flag
in diffs
:
1820 # store HTML markup of the lines into the lists
1821 fromlist
.append(self
._format
_line
(0,flag
,*fromdata
))
1822 tolist
.append(self
._format
_line
(1,flag
,*todata
))
1824 # exceptions occur for lines where context separators go
1825 fromlist
.append(None)
1827 flaglist
.append(flag
)
1828 return fromlist
,tolist
,flaglist
1830 def _format_line(self
,side
,flag
,linenum
,text
):
1831 """Returns HTML markup of "from" / "to" text lines
1833 side -- 0 or 1 indicating "from" or "to" text
1834 flag -- indicates if difference on line
1835 linenum -- line number (used for line number column)
1836 text -- line text to be marked up
1839 linenum
= '%d' % linenum
1840 id = ' id="%s%s"' % (self
._prefix
[side
],linenum
)
1842 # handle blank lines where linenum is '>' or ''
1844 # replace those things that would get confused with HTML symbols
1845 text
=text
.replace("&","&").replace(">",">").replace("<","<")
1847 # make space non-breakable so they don't get compressed or line wrapped
1848 text
= text
.replace(' ',' ').rstrip()
1850 return '<td class="diff_header"%s>%s</td><td nowrap="nowrap">%s</td>' \
1853 def _make_prefix(self
):
1854 """Create unique anchor prefixes"""
1856 # Generate a unique anchor prefix so multiple tables
1857 # can exist on the same HTML page without conflicts.
1858 fromprefix
= "from%d_" % HtmlDiff
._default
_prefix
1859 toprefix
= "to%d_" % HtmlDiff
._default
_prefix
1860 HtmlDiff
._default
_prefix
+= 1
1861 # store prefixes so line format method has access
1862 self
._prefix
= [fromprefix
,toprefix
]
1864 def _convert_flags(self
,fromlist
,tolist
,flaglist
,context
,numlines
):
1865 """Makes list of "next" links"""
1867 # all anchor names will be generated using the unique "to" prefix
1868 toprefix
= self
._prefix
[1]
1870 # process change flags, generating middle column of next anchors/links
1871 next_id
= ['']*len(flaglist
)
1872 next_href
= ['']*len(flaglist
)
1873 num_chg
, in_change
= 0, False
1875 for i
,flag
in enumerate(flaglist
):
1880 # at the beginning of a change, drop an anchor a few lines
1881 # (the context lines) before the change for the previous
1883 i
= max([0,i
-numlines
])
1884 next_id
[i
] = ' id="difflib_chg_%s_%d"' % (toprefix
,num_chg
)
1885 # at the beginning of a change, drop a link to the next
1888 next_href
[last
] = '<a href="#difflib_chg_%s_%d">n</a>' % (
1892 # check for cases where there is no content to avoid exceptions
1899 fromlist
= ['<td></td><td> No Differences Found </td>']
1902 fromlist
= tolist
= ['<td></td><td> Empty File </td>']
1903 # if not a change on first line, drop a link
1905 next_href
[0] = '<a href="#difflib_chg_%s_0">f</a>' % toprefix
1906 # redo the last link to link to the top
1907 next_href
[last
] = '<a href="#difflib_chg_%s_top">t</a>' % (toprefix
)
1909 return fromlist
,tolist
,flaglist
,next_href
,next_id
1911 def make_table(self
,fromlines
,tolines
,fromdesc
='',todesc
='',context
=False,
1913 """Returns HTML table of side by side comparison with change highlights
1916 fromlines -- list of "from" lines
1917 tolines -- list of "to" lines
1918 fromdesc -- "from" file column header string
1919 todesc -- "to" file column header string
1920 context -- set to True for contextual differences (defaults to False
1921 which shows full differences).
1922 numlines -- number of context lines. When context is set True,
1923 controls number of lines displayed before and after the change.
1924 When context is False, controls the number of lines to place
1925 the "next" link anchors before the next change (so click of
1926 "next" link jumps to just before the change).
1929 # make unique anchor prefixes so that multiple tables may exist
1930 # on the same page without conflict.
1933 # change tabs to spaces before it gets more difficult after we insert
1935 fromlines
,tolines
= self
._tab
_newline
_replace
(fromlines
,tolines
)
1937 # create diffs iterator which generates side by side from/to data
1939 context_lines
= numlines
1941 context_lines
= None
1942 diffs
= _mdiff(fromlines
,tolines
,context_lines
,linejunk
=self
._linejunk
,
1943 charjunk
=self
._charjunk
)
1945 # set up iterator to wrap lines that exceed desired width
1946 if self
._wrapcolumn
:
1947 diffs
= self
._line
_wrapper
(diffs
)
1949 # collect up from/to lines and flags into lists (also format the lines)
1950 fromlist
,tolist
,flaglist
= self
._collect
_lines
(diffs
)
1952 # process change flags, generating middle column of next anchors/links
1953 fromlist
,tolist
,flaglist
,next_href
,next_id
= self
._convert
_flags
(
1954 fromlist
,tolist
,flaglist
,context
,numlines
)
1957 fmt
= ' <tr><td class="diff_next"%s>%s</td>%s' + \
1958 '<td class="diff_next">%s</td>%s</tr>\n'
1959 for i
in range(len(flaglist
)):
1960 if flaglist
[i
] is None:
1961 # mdiff yields None on separator lines skip the bogus ones
1962 # generated for the first line
1964 s
.append(' </tbody> \n <tbody>\n')
1966 s
.append( fmt
% (next_id
[i
],next_href
[i
],fromlist
[i
],
1967 next_href
[i
],tolist
[i
]))
1968 if fromdesc
or todesc
:
1969 header_row
= '<thead><tr>%s%s%s%s</tr></thead>' % (
1970 '<th class="diff_next"><br /></th>',
1971 '<th colspan="2" class="diff_header">%s</th>' % fromdesc
,
1972 '<th class="diff_next"><br /></th>',
1973 '<th colspan="2" class="diff_header">%s</th>' % todesc
)
1977 table
= self
._table
_template
% dict(
1978 data_rows
=''.join(s
),
1979 header_row
=header_row
,
1980 prefix
=self
._prefix
[1])
1982 return table
.replace('\0+','<span class="diff_add">'). \
1983 replace('\0-','<span class="diff_sub">'). \
1984 replace('\0^','<span class="diff_chg">'). \
1985 replace('\1','</span>'). \
1986 replace('\t',' ')
1990 def restore(delta
, which
):
1992 Generate one of the two sequences that generated a delta.
1994 Given a `delta` produced by `Differ.compare()` or `ndiff()`, extract
1995 lines originating from file 1 or 2 (parameter `which`), stripping off line
2000 >>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
2001 ... 'ore\ntree\nemu\n'.splitlines(1))
2002 >>> diff = list(diff)
2003 >>> print ''.join(restore(diff, 1)),
2007 >>> print ''.join(restore(diff, 2)),
2013 tag
= {1: "- ", 2: "+ "}[int(which
)]
2015 raise ValueError, ('unknown delta choice (must be 1 or 2): %r'
2017 prefixes
= (" ", tag
)
2019 if line
[:2] in prefixes
:
2023 import doctest
, difflib
2024 return doctest
.testmod(difflib
)
2026 if __name__
== "__main__":