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
38 Match
= _namedtuple('Match', 'a b size')
40 def _calculate_ratio(matches
, length
):
42 return 2.0 * matches
/ length
45 class SequenceMatcher
:
48 SequenceMatcher is a flexible class for comparing pairs of sequences of
49 any type, so long as the sequence elements are hashable. The basic
50 algorithm predates, and is a little fancier than, an algorithm
51 published in the late 1980's by Ratcliff and Obershelp under the
52 hyperbolic name "gestalt pattern matching". The basic idea is to find
53 the longest contiguous matching subsequence that contains no "junk"
54 elements (R-O doesn't address junk). The same idea is then applied
55 recursively to the pieces of the sequences to the left and to the right
56 of the matching subsequence. This does not yield minimal edit
57 sequences, but does tend to yield matches that "look right" to people.
59 SequenceMatcher tries to compute a "human-friendly diff" between two
60 sequences. Unlike e.g. UNIX(tm) diff, the fundamental notion is the
61 longest *contiguous* & junk-free matching subsequence. That's what
62 catches peoples' eyes. The Windows(tm) windiff has another interesting
63 notion, pairing up elements that appear uniquely in each sequence.
64 That, and the method here, appear to yield more intuitive difference
65 reports than does diff. This method appears to be the least vulnerable
66 to synching up on blocks of "junk lines", though (like blank lines in
67 ordinary text files, or maybe "<P>" lines in HTML files). That may be
68 because this is the only method of the 3 that has a *concept* of
71 Example, comparing two strings, and considering blanks to be "junk":
73 >>> s = SequenceMatcher(lambda x: x == " ",
74 ... "private Thread currentThread;",
75 ... "private volatile Thread currentThread;")
78 .ratio() returns a float in [0, 1], measuring the "similarity" of the
79 sequences. As a rule of thumb, a .ratio() value over 0.6 means the
80 sequences are close matches:
82 >>> print round(s.ratio(), 3)
86 If you're only interested in where the sequences match,
87 .get_matching_blocks() is handy:
89 >>> for block in s.get_matching_blocks():
90 ... print "a[%d] and b[%d] match for %d elements" % block
91 a[0] and b[0] match for 8 elements
92 a[8] and b[17] match for 21 elements
93 a[29] and b[38] match for 0 elements
95 Note that the last tuple returned by .get_matching_blocks() is always a
96 dummy, (len(a), len(b), 0), and this is the only case in which the last
97 tuple element (number of elements matched) is 0.
99 If you want to know how to change the first sequence into the second,
102 >>> for opcode in s.get_opcodes():
103 ... print "%6s a[%d:%d] b[%d:%d]" % opcode
105 insert a[8:8] b[8:17]
106 equal a[8:29] b[17:38]
108 See the Differ class for a fancy human-friendly file differencer, which
109 uses SequenceMatcher both to compare sequences of lines, and to compare
110 sequences of characters within similar (near-matching) lines.
112 See also function get_close_matches() in this module, which shows how
113 simple code building on SequenceMatcher can be used to do useful work.
115 Timing: Basic R-O is cubic time worst case and quadratic time expected
116 case. SequenceMatcher is quadratic time for the worst case and has
117 expected-case behavior dependent in a complicated way on how many
118 elements the sequences have in common; best case time is linear.
122 __init__(isjunk=None, a='', b='')
123 Construct a SequenceMatcher.
126 Set the two sequences to be compared.
129 Set the first sequence to be compared.
132 Set the second sequence to be compared.
134 find_longest_match(alo, ahi, blo, bhi)
135 Find longest matching block in a[alo:ahi] and b[blo:bhi].
137 get_matching_blocks()
138 Return list of triples describing matching subsequences.
141 Return list of 5-tuples describing how to turn a into b.
144 Return a measure of the sequences' similarity (float in [0,1]).
147 Return an upper bound on .ratio() relatively quickly.
150 Return an upper bound on ratio() very quickly.
153 def __init__(self
, isjunk
=None, a
='', b
=''):
154 """Construct a SequenceMatcher.
156 Optional arg isjunk is None (the default), or a one-argument
157 function that takes a sequence element and returns true iff the
158 element is junk. None is equivalent to passing "lambda x: 0", i.e.
159 no elements are considered to be junk. For example, pass
160 lambda x: x in " \\t"
161 if you're comparing lines as sequences of characters, and don't
162 want to synch up on blanks or hard tabs.
164 Optional arg a is the first of two sequences to be compared. By
165 default, an empty string. The elements of a must be hashable. See
166 also .set_seqs() and .set_seq1().
168 Optional arg b is the second of two sequences to be compared. By
169 default, an empty string. The elements of b must be hashable. See
170 also .set_seqs() and .set_seq2().
177 # second sequence; differences are computed as "what do
178 # we need to do to 'a' to change it into 'b'?"
180 # for x in b, b2j[x] is a list of the indices (into b)
181 # at which x appears; junk elements do not appear
183 # for x in b, fullbcount[x] == the number of times x
184 # appears in b; only materialized if really needed (used
185 # only for computing quick_ratio())
187 # a list of (i, j, k) triples, where a[i:i+k] == b[j:j+k];
188 # ascending & non-overlapping in i and in j; terminated by
189 # a dummy (len(a), len(b), 0) sentinel
191 # a list of (tag, i1, i2, j1, j2) tuples, where tag is
193 # 'replace' a[i1:i2] should be replaced by b[j1:j2]
194 # 'delete' a[i1:i2] should be deleted
195 # 'insert' b[j1:j2] should be inserted
196 # 'equal' a[i1:i2] == b[j1:j2]
198 # a user-supplied function taking a sequence element and
199 # returning true iff the element is "junk" -- this has
200 # subtle but helpful effects on the algorithm, which I'll
201 # get around to writing up someday <0.9 wink>.
202 # DON'T USE! Only __chain_b uses this. Use isbjunk.
204 # for x in b, isbjunk(x) == isjunk(x) but much faster;
205 # it's really the has_key method of a hidden dict.
206 # DOES NOT WORK for x in a!
208 # for x in b, isbpopular(x) is true iff b is reasonably long
209 # (at least 200 elements) and x accounts for more than 1% of
210 # its elements. DOES NOT WORK for x in a!
213 self
.a
= self
.b
= None
216 def set_seqs(self
, a
, b
):
217 """Set the two sequences to be compared.
219 >>> s = SequenceMatcher()
220 >>> s.set_seqs("abcd", "bcde")
228 def set_seq1(self
, a
):
229 """Set the first sequence to be compared.
231 The second sequence to be compared is not changed.
233 >>> s = SequenceMatcher(None, "abcd", "bcde")
236 >>> s.set_seq1("bcde")
241 SequenceMatcher computes and caches detailed information about the
242 second sequence, so if you want to compare one sequence S against
243 many sequences, use .set_seq2(S) once and call .set_seq1(x)
244 repeatedly for each of the other sequences.
246 See also set_seqs() and set_seq2().
252 self
.matching_blocks
= self
.opcodes
= None
254 def set_seq2(self
, b
):
255 """Set the second sequence to be compared.
257 The first sequence to be compared is not changed.
259 >>> s = SequenceMatcher(None, "abcd", "bcde")
262 >>> s.set_seq2("abcd")
267 SequenceMatcher computes and caches detailed information about the
268 second sequence, so if you want to compare one sequence S against
269 many sequences, use .set_seq2(S) once and call .set_seq1(x)
270 repeatedly for each of the other sequences.
272 See also set_seqs() and set_seq1().
278 self
.matching_blocks
= self
.opcodes
= None
279 self
.fullbcount
= None
282 # For each element x in b, set b2j[x] to a list of the indices in
283 # b where x appears; the indices are in increasing order; note that
284 # the number of times x appears in b is len(b2j[x]) ...
285 # when self.isjunk is defined, junk elements don't show up in this
286 # map at all, which stops the central find_longest_match method
287 # from starting any matching block at a junk element ...
288 # also creates the fast isbjunk function ...
289 # b2j also does not contain entries for "popular" elements, meaning
290 # elements that account for more than 1% of the total elements, and
291 # when the sequence is reasonably large (>= 200 elements); this can
292 # be viewed as an adaptive notion of semi-junk, and yields an enormous
293 # speedup when, e.g., comparing program files with hundreds of
294 # instances of "return NULL;" ...
295 # note that this is only called when b changes; so for cross-product
296 # kinds of matches, it's best to call set_seq2 once, then set_seq1
300 # Because isjunk is a user-defined (not C) function, and we test
301 # for junk a LOT, it's important to minimize the number of calls.
302 # Before the tricks described here, __chain_b was by far the most
303 # time-consuming routine in the whole module! If anyone sees
304 # Jim Roskind, thank him again for profile.py -- I never would
306 # The first trick is to build b2j ignoring the possibility
307 # of junk. I.e., we don't call isjunk at all yet. Throwing
308 # out the junk later is much cheaper than building b2j "right"
314 for i
, elt
in enumerate(b
):
317 if n
>= 200 and len(indices
) * 100 > n
:
325 # Purge leftover indices for popular elements.
326 for elt
in populardict
:
329 # Now b2j.keys() contains elements uniquely, and especially when
330 # the sequence is a string, that's usually a good deal smaller
331 # than len(string). The difference is the number of isjunk calls
336 for d
in populardict
, b2j
:
342 # Now for x in b, isjunk(x) == x in junkdict, but the
343 # latter is much faster. Note too that while there may be a
344 # lot of junk in the sequence, the number of *unique* junk
345 # elements is probably small. So the memory burden of keeping
346 # this dict alive is likely trivial compared to the size of b2j.
347 self
.isbjunk
= junkdict
.has_key
348 self
.isbpopular
= populardict
.has_key
350 def find_longest_match(self
, alo
, ahi
, blo
, bhi
):
351 """Find longest matching block in a[alo:ahi] and b[blo:bhi].
353 If isjunk is not defined:
355 Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where
356 alo <= i <= i+k <= ahi
357 blo <= j <= j+k <= bhi
358 and for all (i',j',k') meeting those conditions,
361 and if i == i', j <= j'
363 In other words, of all maximal matching blocks, return one that
364 starts earliest in a, and of all those maximal matching blocks that
365 start earliest in a, return the one that starts earliest in b.
367 >>> s = SequenceMatcher(None, " abcd", "abcd abcd")
368 >>> s.find_longest_match(0, 5, 0, 9)
369 Match(a=0, b=4, size=5)
371 If isjunk is defined, first the longest matching block is
372 determined as above, but with the additional restriction that no
373 junk element appears in the block. Then that block is extended as
374 far as possible by matching (only) junk elements on both sides. So
375 the resulting block never matches on junk except as identical junk
376 happens to be adjacent to an "interesting" match.
378 Here's the same example as before, but considering blanks to be
379 junk. That prevents " abcd" from matching the " abcd" at the tail
380 end of the second sequence directly. Instead only the "abcd" can
381 match, and matches the leftmost "abcd" in the second sequence:
383 >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")
384 >>> s.find_longest_match(0, 5, 0, 9)
385 Match(a=1, b=0, size=4)
387 If no blocks match, return (alo, blo, 0).
389 >>> s = SequenceMatcher(None, "ab", "c")
390 >>> s.find_longest_match(0, 2, 0, 1)
391 Match(a=0, b=0, size=0)
394 # CAUTION: stripping common prefix or suffix would be incorrect.
398 # Longest matching block is "ab", but if common prefix is
399 # stripped, it's "a" (tied with "b"). UNIX(tm) diff does so
400 # strip, so ends up claiming that ab is changed to acab by
401 # inserting "ca" in the middle. That's minimal but unintuitive:
402 # "it's obvious" that someone inserted "ac" at the front.
403 # Windiff ends up at the same place as diff, but by pairing up
404 # the unique 'b's and then matching the first two 'a's.
406 a
, b
, b2j
, isbjunk
= self
.a
, self
.b
, self
.b2j
, self
.isbjunk
407 besti
, bestj
, bestsize
= alo
, blo
, 0
408 # find longest junk-free match
409 # during an iteration of the loop, j2len[j] = length of longest
410 # junk-free match ending with a[i-1] and b[j]
413 for i
in xrange(alo
, ahi
):
414 # look at all instances of a[i] in b; note that because
415 # b2j has no junk keys, the loop is skipped if a[i] is junk
418 for j
in b2j
.get(a
[i
], nothing
):
424 k
= newj2len
[j
] = j2lenget(j
-1, 0) + 1
426 besti
, bestj
, bestsize
= i
-k
+1, j
-k
+1, k
429 # Extend the best by non-junk elements on each end. In particular,
430 # "popular" non-junk elements aren't in b2j, which greatly speeds
431 # the inner loop above, but also means "the best" match so far
432 # doesn't contain any junk *or* popular non-junk elements.
433 while besti
> alo
and bestj
> blo
and \
434 not isbjunk(b
[bestj
-1]) and \
435 a
[besti
-1] == b
[bestj
-1]:
436 besti
, bestj
, bestsize
= besti
-1, bestj
-1, bestsize
+1
437 while besti
+bestsize
< ahi
and bestj
+bestsize
< bhi
and \
438 not isbjunk(b
[bestj
+bestsize
]) and \
439 a
[besti
+bestsize
] == b
[bestj
+bestsize
]:
442 # Now that we have a wholly interesting match (albeit possibly
443 # empty!), we may as well suck up the matching junk on each
444 # side of it too. Can't think of a good reason not to, and it
445 # saves post-processing the (possibly considerable) expense of
446 # figuring out what to do with it. In the case of an empty
447 # interesting match, this is clearly the right thing to do,
448 # because no other kind of match is possible in the regions.
449 while besti
> alo
and bestj
> blo
and \
450 isbjunk(b
[bestj
-1]) and \
451 a
[besti
-1] == b
[bestj
-1]:
452 besti
, bestj
, bestsize
= besti
-1, bestj
-1, bestsize
+1
453 while besti
+bestsize
< ahi
and bestj
+bestsize
< bhi
and \
454 isbjunk(b
[bestj
+bestsize
]) and \
455 a
[besti
+bestsize
] == b
[bestj
+bestsize
]:
456 bestsize
= bestsize
+ 1
458 return Match(besti
, bestj
, bestsize
)
460 def get_matching_blocks(self
):
461 """Return list of triples describing matching subsequences.
463 Each triple is of the form (i, j, n), and means that
464 a[i:i+n] == b[j:j+n]. The triples are monotonically increasing in
465 i and in j. New in Python 2.5, it's also guaranteed that if
466 (i, j, n) and (i', j', n') are adjacent triples in the list, and
467 the second is not the last triple in the list, then i+n != i' or
468 j+n != j'. IOW, adjacent triples never describe adjacent equal
471 The last triple is a dummy, (len(a), len(b), 0), and is the only
474 >>> s = SequenceMatcher(None, "abxcd", "abcd")
475 >>> s.get_matching_blocks()
476 [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]
479 if self
.matching_blocks
is not None:
480 return self
.matching_blocks
481 la
, lb
= len(self
.a
), len(self
.b
)
483 # This is most naturally expressed as a recursive algorithm, but
484 # at least one user bumped into extreme use cases that exceeded
485 # the recursion limit on their box. So, now we maintain a list
486 # ('queue`) of blocks we still need to look at, and append partial
487 # results to `matching_blocks` in a loop; the matches are sorted
489 queue
= [(0, la
, 0, lb
)]
492 alo
, ahi
, blo
, bhi
= queue
.pop()
493 i
, j
, k
= x
= self
.find_longest_match(alo
, ahi
, blo
, bhi
)
494 # a[alo:i] vs b[blo:j] unknown
495 # a[i:i+k] same as b[j:j+k]
496 # a[i+k:ahi] vs b[j+k:bhi] unknown
497 if k
: # if k is 0, there was no matching block
498 matching_blocks
.append(x
)
499 if alo
< i
and blo
< j
:
500 queue
.append((alo
, i
, blo
, j
))
501 if i
+k
< ahi
and j
+k
< bhi
:
502 queue
.append((i
+k
, ahi
, j
+k
, bhi
))
503 matching_blocks
.sort()
505 # It's possible that we have adjacent equal blocks in the
506 # matching_blocks list now. Starting with 2.5, this code was added
510 for i2
, j2
, k2
in matching_blocks
:
511 # Is this block adjacent to i1, j1, k1?
512 if i1
+ k1
== i2
and j1
+ k1
== j2
:
513 # Yes, so collapse them -- this just increases the length of
514 # the first block by the length of the second, and the first
515 # block so lengthened remains the block to compare against.
518 # Not adjacent. Remember the first block (k1==0 means it's
519 # the dummy we started with), and make the second block the
520 # new block to compare against.
522 non_adjacent
.append((i1
, j1
, k1
))
523 i1
, j1
, k1
= i2
, j2
, k2
525 non_adjacent
.append((i1
, j1
, k1
))
527 non_adjacent
.append( (la
, lb
, 0) )
528 self
.matching_blocks
= non_adjacent
529 return map(Match
._make
, self
.matching_blocks
)
531 def get_opcodes(self
):
532 """Return list of 5-tuples describing how to turn a into b.
534 Each tuple is of the form (tag, i1, i2, j1, j2). The first tuple
535 has i1 == j1 == 0, and remaining tuples have i1 == the i2 from the
536 tuple preceding it, and likewise for j1 == the previous j2.
538 The tags are strings, with these meanings:
540 'replace': a[i1:i2] should be replaced by b[j1:j2]
541 'delete': a[i1:i2] should be deleted.
542 Note that j1==j2 in this case.
543 'insert': b[j1:j2] should be inserted at a[i1:i1].
544 Note that i1==i2 in this case.
545 'equal': a[i1:i2] == b[j1:j2]
549 >>> s = SequenceMatcher(None, a, b)
550 >>> for tag, i1, i2, j1, j2 in s.get_opcodes():
551 ... print ("%7s a[%d:%d] (%s) b[%d:%d] (%s)" %
552 ... (tag, i1, i2, a[i1:i2], j1, j2, b[j1:j2]))
553 delete a[0:1] (q) b[0:0] ()
554 equal a[1:3] (ab) b[0:2] (ab)
555 replace a[3:4] (x) b[2:3] (y)
556 equal a[4:6] (cd) b[3:5] (cd)
557 insert a[6:6] () b[5:6] (f)
560 if self
.opcodes
is not None:
563 self
.opcodes
= answer
= []
564 for ai
, bj
, size
in self
.get_matching_blocks():
565 # invariant: we've pumped out correct diffs to change
566 # a[:i] into b[:j], and the next matching block is
567 # a[ai:ai+size] == b[bj:bj+size]. So we need to pump
568 # out a diff to change a[i:ai] into b[j:bj], pump out
569 # the matching block, and move (i,j) beyond the match
571 if i
< ai
and j
< bj
:
578 answer
.append( (tag
, i
, ai
, j
, bj
) )
579 i
, j
= ai
+size
, bj
+size
580 # the list of matching blocks is terminated by a
581 # sentinel with size 0
583 answer
.append( ('equal', ai
, i
, bj
, j
) )
586 def get_grouped_opcodes(self
, n
=3):
587 """ Isolate change clusters by eliminating ranges with no changes.
589 Return a generator of groups with upto n lines of context.
590 Each group is in the same format as returned by get_opcodes().
592 >>> from pprint import pprint
593 >>> a = map(str, range(1,40))
595 >>> b[8:8] = ['i'] # Make an insertion
596 >>> b[20] += 'x' # Make a replacement
597 >>> b[23:28] = [] # Make a deletion
598 >>> b[30] += 'y' # Make another replacement
599 >>> pprint(list(SequenceMatcher(None,a,b).get_grouped_opcodes()))
600 [[('equal', 5, 8, 5, 8), ('insert', 8, 8, 8, 9), ('equal', 8, 11, 9, 12)],
601 [('equal', 16, 19, 17, 20),
602 ('replace', 19, 20, 20, 21),
603 ('equal', 20, 22, 21, 23),
604 ('delete', 22, 27, 23, 23),
605 ('equal', 27, 30, 23, 26)],
606 [('equal', 31, 34, 27, 30),
607 ('replace', 34, 35, 30, 31),
608 ('equal', 35, 38, 31, 34)]]
611 codes
= self
.get_opcodes()
613 codes
= [("equal", 0, 1, 0, 1)]
614 # Fixup leading and trailing groups if they show no changes.
615 if codes
[0][0] == 'equal':
616 tag
, i1
, i2
, j1
, j2
= codes
[0]
617 codes
[0] = tag
, max(i1
, i2
-n
), i2
, max(j1
, j2
-n
), j2
618 if codes
[-1][0] == 'equal':
619 tag
, i1
, i2
, j1
, j2
= codes
[-1]
620 codes
[-1] = tag
, i1
, min(i2
, i1
+n
), j1
, min(j2
, j1
+n
)
624 for tag
, i1
, i2
, j1
, j2
in codes
:
625 # End the current group and start a new one whenever
626 # there is a large range with no changes.
627 if tag
== 'equal' and i2
-i1
> nn
:
628 group
.append((tag
, i1
, min(i2
, i1
+n
), j1
, min(j2
, j1
+n
)))
631 i1
, j1
= max(i1
, i2
-n
), max(j1
, j2
-n
)
632 group
.append((tag
, i1
, i2
, j1
,j2
))
633 if group
and not (len(group
)==1 and group
[0][0] == 'equal'):
637 """Return a measure of the sequences' similarity (float in [0,1]).
639 Where T is the total number of elements in both sequences, and
640 M is the number of matches, this is 2.0*M / T.
641 Note that this is 1 if the sequences are identical, and 0 if
642 they have nothing in common.
644 .ratio() is expensive to compute if you haven't already computed
645 .get_matching_blocks() or .get_opcodes(), in which case you may
646 want to try .quick_ratio() or .real_quick_ratio() first to get an
649 >>> s = SequenceMatcher(None, "abcd", "bcde")
654 >>> s.real_quick_ratio()
658 matches
= reduce(lambda sum, triple
: sum + triple
[-1],
659 self
.get_matching_blocks(), 0)
660 return _calculate_ratio(matches
, len(self
.a
) + len(self
.b
))
662 def quick_ratio(self
):
663 """Return an upper bound on ratio() relatively quickly.
665 This isn't defined beyond that it is an upper bound on .ratio(), and
666 is faster to compute.
669 # viewing a and b as multisets, set matches to the cardinality
670 # of their intersection; this counts the number of matches
671 # without regard to order, so is clearly an upper bound
672 if self
.fullbcount
is None:
673 self
.fullbcount
= fullbcount
= {}
675 fullbcount
[elt
] = fullbcount
.get(elt
, 0) + 1
676 fullbcount
= self
.fullbcount
677 # avail[x] is the number of times x appears in 'b' less the
678 # number of times we've seen it in 'a' so far ... kinda
680 availhas
, matches
= avail
.has_key
, 0
685 numb
= fullbcount
.get(elt
, 0)
686 avail
[elt
] = numb
- 1
688 matches
= matches
+ 1
689 return _calculate_ratio(matches
, len(self
.a
) + len(self
.b
))
691 def real_quick_ratio(self
):
692 """Return an upper bound on ratio() very quickly.
694 This isn't defined beyond that it is an upper bound on .ratio(), and
695 is faster to compute than either .ratio() or .quick_ratio().
698 la
, lb
= len(self
.a
), len(self
.b
)
699 # can't have more matches than the number of elements in the
701 return _calculate_ratio(min(la
, lb
), la
+ lb
)
703 def get_close_matches(word
, possibilities
, n
=3, cutoff
=0.6):
704 """Use SequenceMatcher to return list of the best "good enough" matches.
706 word is a sequence for which close matches are desired (typically a
709 possibilities is a list of sequences against which to match word
710 (typically a list of strings).
712 Optional arg n (default 3) is the maximum number of close matches to
713 return. n must be > 0.
715 Optional arg cutoff (default 0.6) is a float in [0, 1]. Possibilities
716 that don't score at least that similar to word are ignored.
718 The best (no more than n) matches among the possibilities are returned
719 in a list, sorted by similarity score, most similar first.
721 >>> get_close_matches("appel", ["ape", "apple", "peach", "puppy"])
723 >>> import keyword as _keyword
724 >>> get_close_matches("wheel", _keyword.kwlist)
726 >>> get_close_matches("apple", _keyword.kwlist)
728 >>> get_close_matches("accept", _keyword.kwlist)
733 raise ValueError("n must be > 0: %r" % (n
,))
734 if not 0.0 <= cutoff
<= 1.0:
735 raise ValueError("cutoff must be in [0.0, 1.0]: %r" % (cutoff
,))
737 s
= SequenceMatcher()
739 for x
in possibilities
:
741 if s
.real_quick_ratio() >= cutoff
and \
742 s
.quick_ratio() >= cutoff
and \
744 result
.append((s
.ratio(), x
))
746 # Move the best scorers to head of list
747 result
= heapq
.nlargest(n
, result
)
748 # Strip scores for the best n matches
749 return [x
for score
, x
in result
]
751 def _count_leading(line
, ch
):
753 Return number of `ch` characters at the start of `line`.
757 >>> _count_leading(' abc', ' ')
762 while i
< n
and line
[i
] == ch
:
768 Differ is a class for comparing sequences of lines of text, and
769 producing human-readable differences or deltas. Differ uses
770 SequenceMatcher both to compare sequences of lines, and to compare
771 sequences of characters within similar (near-matching) lines.
773 Each line of a Differ delta begins with a two-letter code:
775 '- ' line unique to sequence 1
776 '+ ' line unique to sequence 2
777 ' ' line common to both sequences
778 '? ' line not present in either input sequence
780 Lines beginning with '? ' attempt to guide the eye to intraline
781 differences, and were not present in either input sequence. These lines
782 can be confusing if the sequences contain tab characters.
784 Note that Differ makes no claim to produce a *minimal* diff. To the
785 contrary, minimal diffs are often counter-intuitive, because they synch
786 up anywhere possible, sometimes accidental matches 100 pages apart.
787 Restricting synch points to contiguous matches preserves some notion of
788 locality, at the occasional cost of producing a longer diff.
790 Example: Comparing two texts.
792 First we set up the texts, sequences of individual single-line strings
793 ending with newlines (such sequences can also be obtained from the
794 `readlines()` method of file-like objects):
796 >>> text1 = ''' 1. Beautiful is better than ugly.
797 ... 2. Explicit is better than implicit.
798 ... 3. Simple is better than complex.
799 ... 4. Complex is better than complicated.
800 ... '''.splitlines(1)
805 >>> text2 = ''' 1. Beautiful is better than ugly.
806 ... 3. Simple is better than complex.
807 ... 4. Complicated is better than complex.
808 ... 5. Flat is better than nested.
809 ... '''.splitlines(1)
811 Next we instantiate a Differ object:
815 Note that when instantiating a Differ object we may pass functions to
816 filter out line and character 'junk'. See Differ.__init__ for details.
818 Finally, we compare the two:
820 >>> result = list(d.compare(text1, text2))
822 'result' is a list of strings, so let's pretty-print it:
824 >>> from pprint import pprint as _pprint
826 [' 1. Beautiful is better than ugly.\n',
827 '- 2. Explicit is better than implicit.\n',
828 '- 3. Simple is better than complex.\n',
829 '+ 3. Simple is better than complex.\n',
831 '- 4. Complex is better than complicated.\n',
833 '+ 4. Complicated is better than complex.\n',
835 '+ 5. Flat is better than nested.\n']
837 As a single multi-line string it looks like this:
839 >>> print ''.join(result),
840 1. Beautiful is better than ugly.
841 - 2. Explicit is better than implicit.
842 - 3. Simple is better than complex.
843 + 3. Simple is better than complex.
845 - 4. Complex is better than complicated.
847 + 4. Complicated is better than complex.
849 + 5. Flat is better than nested.
853 __init__(linejunk=None, charjunk=None)
854 Construct a text differencer, with optional filters.
857 Compare two sequences of lines; generate the resulting delta.
860 def __init__(self
, linejunk
=None, charjunk
=None):
862 Construct a text differencer, with optional filters.
864 The two optional keyword parameters are for filter functions:
866 - `linejunk`: A function that should accept a single string argument,
867 and return true iff the string is junk. The module-level function
868 `IS_LINE_JUNK` may be used to filter out lines without visible
869 characters, except for at most one splat ('#'). It is recommended
870 to leave linejunk None; as of Python 2.3, the underlying
871 SequenceMatcher class has grown an adaptive notion of "noise" lines
872 that's better than any static definition the author has ever been
875 - `charjunk`: A function that should accept a string of length 1. The
876 module-level function `IS_CHARACTER_JUNK` may be used to filter out
877 whitespace characters (a blank or tab; **note**: bad idea to include
878 newline in this!). Use of IS_CHARACTER_JUNK is recommended.
881 self
.linejunk
= linejunk
882 self
.charjunk
= charjunk
884 def compare(self
, a
, b
):
886 Compare two sequences of lines; generate the resulting delta.
888 Each sequence must contain individual single-line strings ending with
889 newlines. Such sequences can be obtained from the `readlines()` method
890 of file-like objects. The delta generated also consists of newline-
891 terminated strings, ready to be printed as-is via the writeline()
892 method of a file-like object.
896 >>> print ''.join(Differ().compare('one\ntwo\nthree\n'.splitlines(1),
897 ... 'ore\ntree\nemu\n'.splitlines(1))),
909 cruncher
= SequenceMatcher(self
.linejunk
, a
, b
)
910 for tag
, alo
, ahi
, blo
, bhi
in cruncher
.get_opcodes():
912 g
= self
._fancy
_replace
(a
, alo
, ahi
, b
, blo
, bhi
)
913 elif tag
== 'delete':
914 g
= self
._dump
('-', a
, alo
, ahi
)
915 elif tag
== 'insert':
916 g
= self
._dump
('+', b
, blo
, bhi
)
918 g
= self
._dump
(' ', a
, alo
, ahi
)
920 raise ValueError, 'unknown tag %r' % (tag
,)
925 def _dump(self
, tag
, x
, lo
, hi
):
926 """Generate comparison results for a same-tagged range."""
927 for i
in xrange(lo
, hi
):
928 yield '%s %s' % (tag
, x
[i
])
930 def _plain_replace(self
, a
, alo
, ahi
, b
, blo
, bhi
):
931 assert alo
< ahi
and blo
< bhi
932 # dump the shorter block first -- reduces the burden on short-term
933 # memory if the blocks are of very different sizes
934 if bhi
- blo
< ahi
- alo
:
935 first
= self
._dump
('+', b
, blo
, bhi
)
936 second
= self
._dump
('-', a
, alo
, ahi
)
938 first
= self
._dump
('-', a
, alo
, ahi
)
939 second
= self
._dump
('+', b
, blo
, bhi
)
941 for g
in first
, second
:
945 def _fancy_replace(self
, a
, alo
, ahi
, b
, blo
, bhi
):
947 When replacing one block of lines with another, search the blocks
948 for *similar* lines; the best-matching pair (if any) is used as a
949 synch point, and intraline difference marking is done on the
950 similar pair. Lots of work, but often worth it.
955 >>> results = d._fancy_replace(['abcDefghiJkl\n'], 0, 1,
956 ... ['abcdefGhijkl\n'], 0, 1)
957 >>> print ''.join(results),
964 # don't synch up unless the lines have a similarity score of at
965 # least cutoff; best_ratio tracks the best score seen so far
966 best_ratio
, cutoff
= 0.74, 0.75
967 cruncher
= SequenceMatcher(self
.charjunk
)
968 eqi
, eqj
= None, None # 1st indices of equal lines (if any)
970 # search for the pair that matches best without being identical
971 # (identical lines must be junk lines, & we don't want to synch up
972 # on junk -- unless we have to)
973 for j
in xrange(blo
, bhi
):
975 cruncher
.set_seq2(bj
)
976 for i
in xrange(alo
, ahi
):
982 cruncher
.set_seq1(ai
)
983 # computing similarity is expensive, so use the quick
984 # upper bounds first -- have seen this speed up messy
985 # compares by a factor of 3.
986 # note that ratio() is only expensive to compute the first
987 # time it's called on a sequence pair; the expensive part
988 # of the computation is cached by cruncher
989 if cruncher
.real_quick_ratio() > best_ratio
and \
990 cruncher
.quick_ratio() > best_ratio
and \
991 cruncher
.ratio() > best_ratio
:
992 best_ratio
, best_i
, best_j
= cruncher
.ratio(), i
, j
993 if best_ratio
< cutoff
:
994 # no non-identical "pretty close" pair
996 # no identical pair either -- treat it as a straight replace
997 for line
in self
._plain
_replace
(a
, alo
, ahi
, b
, blo
, bhi
):
1000 # no close pair, but an identical pair -- synch up on that
1001 best_i
, best_j
, best_ratio
= eqi
, eqj
, 1.0
1003 # there's a close pair, so forget the identical pair (if any)
1006 # a[best_i] very similar to b[best_j]; eqi is None iff they're not
1009 # pump out diffs from before the synch point
1010 for line
in self
._fancy
_helper
(a
, alo
, best_i
, b
, blo
, best_j
):
1013 # do intraline marking on the synch pair
1014 aelt
, belt
= a
[best_i
], b
[best_j
]
1016 # pump out a '-', '?', '+', '?' quad for the synched lines
1018 cruncher
.set_seqs(aelt
, belt
)
1019 for tag
, ai1
, ai2
, bj1
, bj2
in cruncher
.get_opcodes():
1020 la
, lb
= ai2
- ai1
, bj2
- bj1
1021 if tag
== 'replace':
1024 elif tag
== 'delete':
1026 elif tag
== 'insert':
1028 elif tag
== 'equal':
1032 raise ValueError, 'unknown tag %r' % (tag
,)
1033 for line
in self
._qformat
(aelt
, belt
, atags
, btags
):
1036 # the synch pair is identical
1039 # pump out diffs from after the synch point
1040 for line
in self
._fancy
_helper
(a
, best_i
+1, ahi
, b
, best_j
+1, bhi
):
1043 def _fancy_helper(self
, a
, alo
, ahi
, b
, blo
, bhi
):
1047 g
= self
._fancy
_replace
(a
, alo
, ahi
, b
, blo
, bhi
)
1049 g
= self
._dump
('-', a
, alo
, ahi
)
1051 g
= self
._dump
('+', b
, blo
, bhi
)
1056 def _qformat(self
, aline
, bline
, atags
, btags
):
1058 Format "?" output and deal with leading tabs.
1063 >>> results = d._qformat('\tabcDefghiJkl\n', '\t\tabcdefGhijkl\n',
1064 ... ' ^ ^ ^ ', '+ ^ ^ ^ ')
1065 >>> for line in results: print repr(line)
1067 '- \tabcDefghiJkl\n'
1069 '+ \t\tabcdefGhijkl\n'
1073 # Can hurt, but will probably help most of the time.
1074 common
= min(_count_leading(aline
, "\t"),
1075 _count_leading(bline
, "\t"))
1076 common
= min(common
, _count_leading(atags
[:common
], " "))
1077 atags
= atags
[common
:].rstrip()
1078 btags
= btags
[common
:].rstrip()
1082 yield "? %s%s\n" % ("\t" * common
, atags
)
1086 yield "? %s%s\n" % ("\t" * common
, btags
)
1088 # With respect to junk, an earlier version of ndiff simply refused to
1089 # *start* a match with a junk element. The result was cases like this:
1090 # before: private Thread currentThread;
1091 # after: private volatile Thread currentThread;
1092 # If you consider whitespace to be junk, the longest contiguous match
1093 # not starting with junk is "e Thread currentThread". So ndiff reported
1094 # that "e volatil" was inserted between the 't' and the 'e' in "private".
1095 # While an accurate view, to people that's absurd. The current version
1096 # looks for matching blocks that are entirely junk-free, then extends the
1097 # longest one of those as far as possible but only with matching junk.
1098 # So now "currentThread" is matched, then extended to suck up the
1099 # preceding blank; then "private" is matched, and extended to suck up the
1100 # following blank; then "Thread" is matched; and finally ndiff reports
1101 # that "volatile " was inserted before "Thread". The only quibble
1102 # remaining is that perhaps it was really the case that " volatile"
1103 # was inserted after "private". I can live with that <wink>.
1107 def IS_LINE_JUNK(line
, pat
=re
.compile(r
"\s*#?\s*$").match
):
1109 Return 1 for ignorable line: iff `line` is blank or contains a single '#'.
1113 >>> IS_LINE_JUNK('\n')
1115 >>> IS_LINE_JUNK(' # \n')
1117 >>> IS_LINE_JUNK('hello\n')
1121 return pat(line
) is not None
1123 def IS_CHARACTER_JUNK(ch
, ws
=" \t"):
1125 Return 1 for ignorable character: iff `ch` is a space or tab.
1129 >>> IS_CHARACTER_JUNK(' ')
1131 >>> IS_CHARACTER_JUNK('\t')
1133 >>> IS_CHARACTER_JUNK('\n')
1135 >>> IS_CHARACTER_JUNK('x')
1142 def unified_diff(a
, b
, fromfile
='', tofile
='', fromfiledate
='',
1143 tofiledate
='', n
=3, lineterm
='\n'):
1145 Compare two sequences of lines; generate the delta as a unified diff.
1147 Unified diffs are a compact way of showing line changes and a few
1148 lines of context. The number of context lines is set by 'n' which
1151 By default, the diff control lines (those with ---, +++, or @@) are
1152 created with a trailing newline. This is helpful so that inputs
1153 created from file.readlines() result in diffs that are suitable for
1154 file.writelines() since both the inputs and outputs have trailing
1157 For inputs that do not have trailing newlines, set the lineterm
1158 argument to "" so that the output will be uniformly newline free.
1160 The unidiff format normally has a header for filenames and modification
1161 times. Any or all of these may be specified using strings for
1162 'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'. The modification
1163 times are normally expressed in the format returned by time.ctime().
1167 >>> for line in unified_diff('one two three four'.split(),
1168 ... 'zero one tree four'.split(), 'Original', 'Current',
1169 ... 'Sat Jan 26 23:30:50 1991', 'Fri Jun 06 10:20:52 2003',
1172 --- Original Sat Jan 26 23:30:50 1991
1173 +++ Current Fri Jun 06 10:20:52 2003
1184 for group
in SequenceMatcher(None,a
,b
).get_grouped_opcodes(n
):
1186 yield '--- %s %s%s' % (fromfile
, fromfiledate
, lineterm
)
1187 yield '+++ %s %s%s' % (tofile
, tofiledate
, lineterm
)
1189 i1
, i2
, j1
, j2
= group
[0][1], group
[-1][2], group
[0][3], group
[-1][4]
1190 yield "@@ -%d,%d +%d,%d @@%s" % (i1
+1, i2
-i1
, j1
+1, j2
-j1
, lineterm
)
1191 for tag
, i1
, i2
, j1
, j2
in group
:
1193 for line
in a
[i1
:i2
]:
1196 if tag
== 'replace' or tag
== 'delete':
1197 for line
in a
[i1
:i2
]:
1199 if tag
== 'replace' or tag
== 'insert':
1200 for line
in b
[j1
:j2
]:
1203 # See http://www.unix.org/single_unix_specification/
1204 def context_diff(a
, b
, fromfile
='', tofile
='',
1205 fromfiledate
='', tofiledate
='', n
=3, lineterm
='\n'):
1207 Compare two sequences of lines; generate the delta as a context diff.
1209 Context diffs are a compact way of showing line changes and a few
1210 lines of context. The number of context lines is set by 'n' which
1213 By default, the diff control lines (those with *** or ---) are
1214 created with a trailing newline. This is helpful so that inputs
1215 created from file.readlines() result in diffs that are suitable for
1216 file.writelines() since both the inputs and outputs have trailing
1219 For inputs that do not have trailing newlines, set the lineterm
1220 argument to "" so that the output will be uniformly newline free.
1222 The context diff format normally has a header for filenames and
1223 modification times. Any or all of these may be specified using
1224 strings for 'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'.
1225 The modification times are normally expressed in the format returned
1226 by time.ctime(). If not specified, the strings default to blanks.
1230 >>> print ''.join(context_diff('one\ntwo\nthree\nfour\n'.splitlines(1),
1231 ... 'zero\none\ntree\nfour\n'.splitlines(1), 'Original', 'Current',
1232 ... 'Sat Jan 26 23:30:50 1991', 'Fri Jun 06 10:22:46 2003')),
1233 *** Original Sat Jan 26 23:30:50 1991
1234 --- Current Fri Jun 06 10:22:46 2003
1249 prefixmap
= {'insert':'+ ', 'delete':'- ', 'replace':'! ', 'equal':' '}
1250 for group
in SequenceMatcher(None,a
,b
).get_grouped_opcodes(n
):
1252 yield '*** %s %s%s' % (fromfile
, fromfiledate
, lineterm
)
1253 yield '--- %s %s%s' % (tofile
, tofiledate
, lineterm
)
1256 yield '***************%s' % (lineterm
,)
1257 if group
[-1][2] - group
[0][1] >= 2:
1258 yield '*** %d,%d ****%s' % (group
[0][1]+1, group
[-1][2], lineterm
)
1260 yield '*** %d ****%s' % (group
[-1][2], lineterm
)
1261 visiblechanges
= [e
for e
in group
if e
[0] in ('replace', 'delete')]
1263 for tag
, i1
, i2
, _
, _
in group
:
1265 for line
in a
[i1
:i2
]:
1266 yield prefixmap
[tag
] + line
1268 if group
[-1][4] - group
[0][3] >= 2:
1269 yield '--- %d,%d ----%s' % (group
[0][3]+1, group
[-1][4], lineterm
)
1271 yield '--- %d ----%s' % (group
[-1][4], lineterm
)
1272 visiblechanges
= [e
for e
in group
if e
[0] in ('replace', 'insert')]
1274 for tag
, _
, _
, j1
, j2
in group
:
1276 for line
in b
[j1
:j2
]:
1277 yield prefixmap
[tag
] + line
1279 def ndiff(a
, b
, linejunk
=None, charjunk
=IS_CHARACTER_JUNK
):
1281 Compare `a` and `b` (lists of strings); return a `Differ`-style delta.
1283 Optional keyword parameters `linejunk` and `charjunk` are for filter
1284 functions (or None):
1286 - linejunk: A function that should accept a single string argument, and
1287 return true iff the string is junk. The default is None, and is
1288 recommended; as of Python 2.3, an adaptive notion of "noise" lines is
1289 used that does a good job on its own.
1291 - charjunk: A function that should accept a string of length 1. The
1292 default is module-level function IS_CHARACTER_JUNK, which filters out
1293 whitespace characters (a blank or tab; note: bad idea to include newline
1296 Tools/scripts/ndiff.py is a command-line front-end to this function.
1300 >>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
1301 ... 'ore\ntree\nemu\n'.splitlines(1))
1302 >>> print ''.join(diff),
1313 return Differ(linejunk
, charjunk
).compare(a
, b
)
1315 def _mdiff(fromlines
, tolines
, context
=None, linejunk
=None,
1316 charjunk
=IS_CHARACTER_JUNK
):
1317 r
"""Returns generator yielding marked up from/to side by side differences.
1320 fromlines -- list of text lines to compared to tolines
1321 tolines -- list of text lines to be compared to fromlines
1322 context -- number of context lines to display on each side of difference,
1323 if None, all from/to text lines will be generated.
1324 linejunk -- passed on to ndiff (see ndiff documentation)
1325 charjunk -- passed on to ndiff (see ndiff documentation)
1327 This function returns an interator which returns a tuple:
1328 (from line tuple, to line tuple, boolean flag)
1330 from/to line tuple -- (line num, line text)
1331 line num -- integer or None (to indicate a context seperation)
1332 line text -- original line text with following markers inserted:
1333 '\0+' -- marks start of added text
1334 '\0-' -- marks start of deleted text
1335 '\0^' -- marks start of changed text
1336 '\1' -- marks end of added/deleted/changed text
1338 boolean flag -- None indicates context separation, True indicates
1339 either "from" or "to" line contains a change, otherwise False.
1341 This function/iterator was originally developed to generate side by side
1342 file difference for making HTML pages (see HtmlDiff class for example
1345 Note, this function utilizes the ndiff function to generate the side by
1346 side difference markup. Optional ndiff arguments may be passed to this
1347 function and they in turn will be passed to ndiff.
1351 # regular expression for finding intraline change indices
1352 change_re
= re
.compile('(\++|\-+|\^+)')
1354 # create the difference iterator to generate the differences
1355 diff_lines_iterator
= ndiff(fromlines
,tolines
,linejunk
,charjunk
)
1357 def _make_line(lines
, format_key
, side
, num_lines
=[0,0]):
1358 """Returns line of text with user's change markup and line formatting.
1360 lines -- list of lines from the ndiff generator to produce a line of
1361 text from. When producing the line of text to return, the
1362 lines used are removed from this list.
1363 format_key -- '+' return first line in list with "add" markup around
1365 '-' return first line in list with "delete" markup around
1367 '?' return first line in list with add/delete/change
1368 intraline markup (indices obtained from second line)
1369 None return first line in list with no markup
1370 side -- indice into the num_lines list (0=from,1=to)
1371 num_lines -- from/to current line number. This is NOT intended to be a
1372 passed parameter. It is present as a keyword argument to
1373 maintain memory of the current line numbers between calls
1376 Note, this function is purposefully not defined at the module scope so
1377 that data it needs from its parent function (within whose context it
1378 is defined) does not need to be of module scope.
1380 num_lines
[side
] += 1
1381 # Handle case where no user markup is to be added, just return line of
1382 # text with user's line format to allow for usage of the line number.
1383 if format_key
is None:
1384 return (num_lines
[side
],lines
.pop(0)[2:])
1385 # Handle case of intraline changes
1386 if format_key
== '?':
1387 text
, markers
= lines
.pop(0), lines
.pop(0)
1388 # find intraline changes (store change type and indices in tuples)
1390 def record_sub_info(match_object
,sub_info
=sub_info
):
1391 sub_info
.append([match_object
.group(1)[0],match_object
.span()])
1392 return match_object
.group(1)
1393 change_re
.sub(record_sub_info
,markers
)
1394 # process each tuple inserting our special marks that won't be
1395 # noticed by an xml/html escaper.
1396 for key
,(begin
,end
) in sub_info
[::-1]:
1397 text
= text
[0:begin
]+'\0'+key
+text
[begin
:end
]+'\1'+text
[end
:]
1399 # Handle case of add/delete entire line
1401 text
= lines
.pop(0)[2:]
1402 # if line of text is just a newline, insert a space so there is
1403 # something for the user to highlight and see.
1406 # insert marks that won't be noticed by an xml/html escaper.
1407 text
= '\0' + format_key
+ text
+ '\1'
1408 # Return line of text, first allow user's line formatter to do its
1409 # thing (such as adding the line number) then replace the special
1410 # marks with what the user's change markup.
1411 return (num_lines
[side
],text
)
1413 def _line_iterator():
1414 """Yields from/to lines of text with a change indication.
1416 This function is an iterator. It itself pulls lines from a
1417 differencing iterator, processes them and yields them. When it can
1418 it yields both a "from" and a "to" line, otherwise it will yield one
1419 or the other. In addition to yielding the lines of from/to text, a
1420 boolean flag is yielded to indicate if the text line(s) have
1421 differences in them.
1423 Note, this function is purposefully not defined at the module scope so
1424 that data it needs from its parent function (within whose context it
1425 is defined) does not need to be of module scope.
1428 num_blanks_pending
, num_blanks_to_yield
= 0, 0
1430 # Load up next 4 lines so we can look ahead, create strings which
1431 # are a concatenation of the first character of each of the 4 lines
1432 # so we can do some very readable comparisons.
1433 while len(lines
) < 4:
1435 lines
.append(diff_lines_iterator
.next())
1436 except StopIteration:
1438 s
= ''.join([line
[0] for line
in lines
])
1439 if s
.startswith('X'):
1440 # When no more lines, pump out any remaining blank lines so the
1441 # corresponding add/delete lines get a matching blank line so
1442 # all line pairs get yielded at the next level.
1443 num_blanks_to_yield
= num_blanks_pending
1444 elif s
.startswith('-?+?'):
1445 # simple intraline change
1446 yield _make_line(lines
,'?',0), _make_line(lines
,'?',1), True
1448 elif s
.startswith('--++'):
1449 # in delete block, add block coming: we do NOT want to get
1450 # caught up on blank lines yet, just process the delete line
1451 num_blanks_pending
-= 1
1452 yield _make_line(lines
,'-',0), None, True
1454 elif s
.startswith(('--?+', '--+', '- ')):
1455 # in delete block and see a intraline change or unchanged line
1456 # coming: yield the delete line and then blanks
1457 from_line
,to_line
= _make_line(lines
,'-',0), None
1458 num_blanks_to_yield
,num_blanks_pending
= num_blanks_pending
-1,0
1459 elif s
.startswith('-+?'):
1461 yield _make_line(lines
,None,0), _make_line(lines
,'?',1), True
1463 elif s
.startswith('-?+'):
1465 yield _make_line(lines
,'?',0), _make_line(lines
,None,1), True
1467 elif s
.startswith('-'):
1469 num_blanks_pending
-= 1
1470 yield _make_line(lines
,'-',0), None, True
1472 elif s
.startswith('+--'):
1473 # in add block, delete block coming: we do NOT want to get
1474 # caught up on blank lines yet, just process the add line
1475 num_blanks_pending
+= 1
1476 yield None, _make_line(lines
,'+',1), True
1478 elif s
.startswith(('+ ', '+-')):
1479 # will be leaving an add block: yield blanks then add line
1480 from_line
, to_line
= None, _make_line(lines
,'+',1)
1481 num_blanks_to_yield
,num_blanks_pending
= num_blanks_pending
+1,0
1482 elif s
.startswith('+'):
1483 # inside an add block, yield the add line
1484 num_blanks_pending
+= 1
1485 yield None, _make_line(lines
,'+',1), True
1487 elif s
.startswith(' '):
1488 # unchanged text, yield it to both sides
1489 yield _make_line(lines
[:],None,0),_make_line(lines
,None,1),False
1491 # Catch up on the blank lines so when we yield the next from/to
1492 # pair, they are lined up.
1493 while(num_blanks_to_yield
< 0):
1494 num_blanks_to_yield
+= 1
1495 yield None,('','\n'),True
1496 while(num_blanks_to_yield
> 0):
1497 num_blanks_to_yield
-= 1
1498 yield ('','\n'),None,True
1499 if s
.startswith('X'):
1502 yield from_line
,to_line
,True
1504 def _line_pair_iterator():
1505 """Yields from/to lines of text with a change indication.
1507 This function is an iterator. It itself pulls lines from the line
1508 iterator. Its difference from that iterator is that this function
1509 always yields a pair of from/to text lines (with the change
1510 indication). If necessary it will collect single from/to lines
1511 until it has a matching pair from/to pair to yield.
1513 Note, this function is purposefully not defined at the module scope so
1514 that data it needs from its parent function (within whose context it
1515 is defined) does not need to be of module scope.
1517 line_iterator
= _line_iterator()
1518 fromlines
,tolines
=[],[]
1520 # Collecting lines of text until we have a from/to pair
1521 while (len(fromlines
)==0 or len(tolines
)==0):
1522 from_line
, to_line
, found_diff
=line_iterator
.next()
1523 if from_line
is not None:
1524 fromlines
.append((from_line
,found_diff
))
1525 if to_line
is not None:
1526 tolines
.append((to_line
,found_diff
))
1527 # Once we have a pair, remove them from the collection and yield it
1528 from_line
, fromDiff
= fromlines
.pop(0)
1529 to_line
, to_diff
= tolines
.pop(0)
1530 yield (from_line
,to_line
,fromDiff
or to_diff
)
1532 # Handle case where user does not want context differencing, just yield
1533 # them up without doing anything else with them.
1534 line_pair_iterator
= _line_pair_iterator()
1537 yield line_pair_iterator
.next()
1538 # Handle case where user wants context differencing. We must do some
1539 # storage of lines until we know for sure that they are to be yielded.
1544 # Store lines up until we find a difference, note use of a
1545 # circular queue because we only need to keep around what
1546 # we need for context.
1547 index
, contextLines
= 0, [None]*(context
)
1549 while(found_diff
is False):
1550 from_line
, to_line
, found_diff
= line_pair_iterator
.next()
1552 contextLines
[i
] = (from_line
, to_line
, found_diff
)
1554 # Yield lines that we have collected so far, but first yield
1555 # the user's separator.
1557 yield None, None, None
1558 lines_to_write
= context
1560 lines_to_write
= index
1562 while(lines_to_write
):
1565 yield contextLines
[i
]
1567 # Now yield the context lines after the change
1568 lines_to_write
= context
-1
1569 while(lines_to_write
):
1570 from_line
, to_line
, found_diff
= line_pair_iterator
.next()
1571 # If another change within the context, extend the context
1573 lines_to_write
= context
-1
1576 yield from_line
, to_line
, found_diff
1579 _file_template
= """
1580 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
1581 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
1586 <meta http-equiv="Content-Type"
1587 content="text/html; charset=ISO-8859-1" />
1589 <style type="text/css">%(styles)s
1600 table.diff {font-family:Courier; border:medium;}
1601 .diff_header {background-color:#e0e0e0}
1602 td.diff_header {text-align:right}
1603 .diff_next {background-color:#c0c0c0}
1604 .diff_add {background-color:#aaffaa}
1605 .diff_chg {background-color:#ffff77}
1606 .diff_sub {background-color:#ffaaaa}"""
1608 _table_template
= """
1609 <table class="diff" id="difflib_chg_%(prefix)s_top"
1610 cellspacing="0" cellpadding="0" rules="groups" >
1611 <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>
1612 <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>
1615 %(data_rows)s </tbody>
1619 <table class="diff" summary="Legends">
1620 <tr> <th colspan="2"> Legends </th> </tr>
1621 <tr> <td> <table border="" summary="Colors">
1622 <tr><th> Colors </th> </tr>
1623 <tr><td class="diff_add"> Added </td></tr>
1624 <tr><td class="diff_chg">Changed</td> </tr>
1625 <tr><td class="diff_sub">Deleted</td> </tr>
1627 <td> <table border="" summary="Links">
1628 <tr><th colspan="2"> Links </th> </tr>
1629 <tr><td>(f)irst change</td> </tr>
1630 <tr><td>(n)ext change</td> </tr>
1631 <tr><td>(t)op</td> </tr>
1635 class HtmlDiff(object):
1636 """For producing HTML side by side comparison with change highlights.
1638 This class can be used to create an HTML table (or a complete HTML file
1639 containing the table) showing a side by side, line by line comparison
1640 of text with inter-line and intra-line change highlights. The table can
1641 be generated in either full or contextual difference mode.
1643 The following methods are provided for HTML generation:
1645 make_table -- generates HTML for a single side by side table
1646 make_file -- generates complete HTML file with a single side by side table
1648 See tools/scripts/diff.py for an example usage of this class.
1651 _file_template
= _file_template
1653 _table_template
= _table_template
1657 def __init__(self
,tabsize
=8,wrapcolumn
=None,linejunk
=None,
1658 charjunk
=IS_CHARACTER_JUNK
):
1659 """HtmlDiff instance initializer
1662 tabsize -- tab stop spacing, defaults to 8.
1663 wrapcolumn -- column number where lines are broken and wrapped,
1664 defaults to None where lines are not wrapped.
1665 linejunk,charjunk -- keyword arguments passed into ndiff() (used to by
1666 HtmlDiff() to generate the side by side HTML differences). See
1667 ndiff() documentation for argument default values and descriptions.
1669 self
._tabsize
= tabsize
1670 self
._wrapcolumn
= wrapcolumn
1671 self
._linejunk
= linejunk
1672 self
._charjunk
= charjunk
1674 def make_file(self
,fromlines
,tolines
,fromdesc
='',todesc
='',context
=False,
1676 """Returns HTML file of side by side comparison with change highlights
1679 fromlines -- list of "from" lines
1680 tolines -- list of "to" lines
1681 fromdesc -- "from" file column header string
1682 todesc -- "to" file column header string
1683 context -- set to True for contextual differences (defaults to False
1684 which shows full differences).
1685 numlines -- number of context lines. When context is set True,
1686 controls number of lines displayed before and after the change.
1687 When context is False, controls the number of lines to place
1688 the "next" link anchors before the next change (so click of
1689 "next" link jumps to just before the change).
1692 return self
._file
_template
% dict(
1693 styles
= self
._styles
,
1694 legend
= self
._legend
,
1695 table
= self
.make_table(fromlines
,tolines
,fromdesc
,todesc
,
1696 context
=context
,numlines
=numlines
))
1698 def _tab_newline_replace(self
,fromlines
,tolines
):
1699 """Returns from/to line lists with tabs expanded and newlines removed.
1701 Instead of tab characters being replaced by the number of spaces
1702 needed to fill in to the next tab stop, this function will fill
1703 the space with tab characters. This is done so that the difference
1704 algorithms can identify changes in a file when tabs are replaced by
1705 spaces and vice versa. At the end of the HTML generation, the tab
1706 characters will be replaced with a nonbreakable space.
1708 def expand_tabs(line
):
1710 line
= line
.replace(' ','\0')
1711 # expand tabs into spaces
1712 line
= line
.expandtabs(self
._tabsize
)
1713 # relace spaces from expanded tabs back into tab characters
1714 # (we'll replace them with markup after we do differencing)
1715 line
= line
.replace(' ','\t')
1716 return line
.replace('\0',' ').rstrip('\n')
1717 fromlines
= [expand_tabs(line
) for line
in fromlines
]
1718 tolines
= [expand_tabs(line
) for line
in tolines
]
1719 return fromlines
,tolines
1721 def _split_line(self
,data_list
,line_num
,text
):
1722 """Builds list of text lines by splitting text lines at wrap point
1724 This function will determine if the input text line needs to be
1725 wrapped (split) into separate lines. If so, the first wrap point
1726 will be determined and the first line appended to the output
1727 text line list. This function is used recursively to handle
1728 the second part of the split line to further split it.
1730 # if blank line or context separator, just add it to the output list
1732 data_list
.append((line_num
,text
))
1735 # if line text doesn't need wrapping, just add it to the output list
1737 max = self
._wrapcolumn
1738 if (size
<= max) or ((size
-(text
.count('\0')*3)) <= max):
1739 data_list
.append((line_num
,text
))
1742 # scan text looking for the wrap point, keeping track if the wrap
1743 # point is inside markers
1747 while n
< max and i
< size
:
1752 elif text
[i
] == '\1':
1759 # wrap point is inside text, break it up into separate lines
1763 # if wrap point is inside markers, place end marker at end of first
1764 # line and start marker at beginning of second line because each
1765 # line will have its own table tag markup around it.
1767 line1
= line1
+ '\1'
1768 line2
= '\0' + mark
+ line2
1770 # tack on first line onto the output list
1771 data_list
.append((line_num
,line1
))
1773 # use this routine again to wrap the remaining text
1774 self
._split
_line
(data_list
,'>',line2
)
1776 def _line_wrapper(self
,diffs
):
1777 """Returns iterator that splits (wraps) mdiff text lines"""
1779 # pull from/to data and flags from mdiff iterator
1780 for fromdata
,todata
,flag
in diffs
:
1781 # check for context separators and pass them through
1783 yield fromdata
,todata
,flag
1785 (fromline
,fromtext
),(toline
,totext
) = fromdata
,todata
1786 # for each from/to line split it at the wrap column to form
1787 # list of text lines.
1788 fromlist
,tolist
= [],[]
1789 self
._split
_line
(fromlist
,fromline
,fromtext
)
1790 self
._split
_line
(tolist
,toline
,totext
)
1791 # yield from/to line in pairs inserting blank lines as
1792 # necessary when one side has more wrapped lines
1793 while fromlist
or tolist
:
1795 fromdata
= fromlist
.pop(0)
1799 todata
= tolist
.pop(0)
1802 yield fromdata
,todata
,flag
1804 def _collect_lines(self
,diffs
):
1805 """Collects mdiff output into separate lists
1807 Before storing the mdiff from/to data into a list, it is converted
1808 into a single line of text with HTML markup.
1811 fromlist
,tolist
,flaglist
= [],[],[]
1812 # pull from/to data and flags from mdiff style iterator
1813 for fromdata
,todata
,flag
in diffs
:
1815 # store HTML markup of the lines into the lists
1816 fromlist
.append(self
._format
_line
(0,flag
,*fromdata
))
1817 tolist
.append(self
._format
_line
(1,flag
,*todata
))
1819 # exceptions occur for lines where context separators go
1820 fromlist
.append(None)
1822 flaglist
.append(flag
)
1823 return fromlist
,tolist
,flaglist
1825 def _format_line(self
,side
,flag
,linenum
,text
):
1826 """Returns HTML markup of "from" / "to" text lines
1828 side -- 0 or 1 indicating "from" or "to" text
1829 flag -- indicates if difference on line
1830 linenum -- line number (used for line number column)
1831 text -- line text to be marked up
1834 linenum
= '%d' % linenum
1835 id = ' id="%s%s"' % (self
._prefix
[side
],linenum
)
1837 # handle blank lines where linenum is '>' or ''
1839 # replace those things that would get confused with HTML symbols
1840 text
=text
.replace("&","&").replace(">",">").replace("<","<")
1842 # make space non-breakable so they don't get compressed or line wrapped
1843 text
= text
.replace(' ',' ').rstrip()
1845 return '<td class="diff_header"%s>%s</td><td nowrap="nowrap">%s</td>' \
1848 def _make_prefix(self
):
1849 """Create unique anchor prefixes"""
1851 # Generate a unique anchor prefix so multiple tables
1852 # can exist on the same HTML page without conflicts.
1853 fromprefix
= "from%d_" % HtmlDiff
._default
_prefix
1854 toprefix
= "to%d_" % HtmlDiff
._default
_prefix
1855 HtmlDiff
._default
_prefix
+= 1
1856 # store prefixes so line format method has access
1857 self
._prefix
= [fromprefix
,toprefix
]
1859 def _convert_flags(self
,fromlist
,tolist
,flaglist
,context
,numlines
):
1860 """Makes list of "next" links"""
1862 # all anchor names will be generated using the unique "to" prefix
1863 toprefix
= self
._prefix
[1]
1865 # process change flags, generating middle column of next anchors/links
1866 next_id
= ['']*len(flaglist
)
1867 next_href
= ['']*len(flaglist
)
1868 num_chg
, in_change
= 0, False
1870 for i
,flag
in enumerate(flaglist
):
1875 # at the beginning of a change, drop an anchor a few lines
1876 # (the context lines) before the change for the previous
1878 i
= max([0,i
-numlines
])
1879 next_id
[i
] = ' id="difflib_chg_%s_%d"' % (toprefix
,num_chg
)
1880 # at the beginning of a change, drop a link to the next
1883 next_href
[last
] = '<a href="#difflib_chg_%s_%d">n</a>' % (
1887 # check for cases where there is no content to avoid exceptions
1894 fromlist
= ['<td></td><td> No Differences Found </td>']
1897 fromlist
= tolist
= ['<td></td><td> Empty File </td>']
1898 # if not a change on first line, drop a link
1900 next_href
[0] = '<a href="#difflib_chg_%s_0">f</a>' % toprefix
1901 # redo the last link to link to the top
1902 next_href
[last
] = '<a href="#difflib_chg_%s_top">t</a>' % (toprefix
)
1904 return fromlist
,tolist
,flaglist
,next_href
,next_id
1906 def make_table(self
,fromlines
,tolines
,fromdesc
='',todesc
='',context
=False,
1908 """Returns HTML table of side by side comparison with change highlights
1911 fromlines -- list of "from" lines
1912 tolines -- list of "to" lines
1913 fromdesc -- "from" file column header string
1914 todesc -- "to" file column header string
1915 context -- set to True for contextual differences (defaults to False
1916 which shows full differences).
1917 numlines -- number of context lines. When context is set True,
1918 controls number of lines displayed before and after the change.
1919 When context is False, controls the number of lines to place
1920 the "next" link anchors before the next change (so click of
1921 "next" link jumps to just before the change).
1924 # make unique anchor prefixes so that multiple tables may exist
1925 # on the same page without conflict.
1928 # change tabs to spaces before it gets more difficult after we insert
1930 fromlines
,tolines
= self
._tab
_newline
_replace
(fromlines
,tolines
)
1932 # create diffs iterator which generates side by side from/to data
1934 context_lines
= numlines
1936 context_lines
= None
1937 diffs
= _mdiff(fromlines
,tolines
,context_lines
,linejunk
=self
._linejunk
,
1938 charjunk
=self
._charjunk
)
1940 # set up iterator to wrap lines that exceed desired width
1941 if self
._wrapcolumn
:
1942 diffs
= self
._line
_wrapper
(diffs
)
1944 # collect up from/to lines and flags into lists (also format the lines)
1945 fromlist
,tolist
,flaglist
= self
._collect
_lines
(diffs
)
1947 # process change flags, generating middle column of next anchors/links
1948 fromlist
,tolist
,flaglist
,next_href
,next_id
= self
._convert
_flags
(
1949 fromlist
,tolist
,flaglist
,context
,numlines
)
1952 fmt
= ' <tr><td class="diff_next"%s>%s</td>%s' + \
1953 '<td class="diff_next">%s</td>%s</tr>\n'
1954 for i
in range(len(flaglist
)):
1955 if flaglist
[i
] is None:
1956 # mdiff yields None on separator lines skip the bogus ones
1957 # generated for the first line
1959 s
.append(' </tbody> \n <tbody>\n')
1961 s
.append( fmt
% (next_id
[i
],next_href
[i
],fromlist
[i
],
1962 next_href
[i
],tolist
[i
]))
1963 if fromdesc
or todesc
:
1964 header_row
= '<thead><tr>%s%s%s%s</tr></thead>' % (
1965 '<th class="diff_next"><br /></th>',
1966 '<th colspan="2" class="diff_header">%s</th>' % fromdesc
,
1967 '<th class="diff_next"><br /></th>',
1968 '<th colspan="2" class="diff_header">%s</th>' % todesc
)
1972 table
= self
._table
_template
% dict(
1973 data_rows
=''.join(s
),
1974 header_row
=header_row
,
1975 prefix
=self
._prefix
[1])
1977 return table
.replace('\0+','<span class="diff_add">'). \
1978 replace('\0-','<span class="diff_sub">'). \
1979 replace('\0^','<span class="diff_chg">'). \
1980 replace('\1','</span>'). \
1981 replace('\t',' ')
1985 def restore(delta
, which
):
1987 Generate one of the two sequences that generated a delta.
1989 Given a `delta` produced by `Differ.compare()` or `ndiff()`, extract
1990 lines originating from file 1 or 2 (parameter `which`), stripping off line
1995 >>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
1996 ... 'ore\ntree\nemu\n'.splitlines(1))
1997 >>> diff = list(diff)
1998 >>> print ''.join(restore(diff, 1)),
2002 >>> print ''.join(restore(diff, 2)),
2008 tag
= {1: "- ", 2: "+ "}[int(which
)]
2010 raise ValueError, ('unknown delta choice (must be 1 or 2): %r'
2012 prefixes
= (" ", tag
)
2014 if line
[:2] in prefixes
:
2018 import doctest
, difflib
2019 return doctest
.testmod(difflib
)
2021 if __name__
== "__main__":