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 __contains__ 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
:
337 for elt
in list(d
.keys()):
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
.__contains
__
348 self
.isbpopular
= populardict
.__contains
__
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 range(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 >>> list(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 = list(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
= sum(triple
[-1] for triple
in self
.get_matching_blocks())
659 return _calculate_ratio(matches
, len(self
.a
) + len(self
.b
))
661 def quick_ratio(self
):
662 """Return an upper bound on ratio() relatively quickly.
664 This isn't defined beyond that it is an upper bound on .ratio(), and
665 is faster to compute.
668 # viewing a and b as multisets, set matches to the cardinality
669 # of their intersection; this counts the number of matches
670 # without regard to order, so is clearly an upper bound
671 if self
.fullbcount
is None:
672 self
.fullbcount
= fullbcount
= {}
674 fullbcount
[elt
] = fullbcount
.get(elt
, 0) + 1
675 fullbcount
= self
.fullbcount
676 # avail[x] is the number of times x appears in 'b' less the
677 # number of times we've seen it in 'a' so far ... kinda
679 availhas
, matches
= avail
.__contains
__, 0
684 numb
= fullbcount
.get(elt
, 0)
685 avail
[elt
] = numb
- 1
687 matches
= matches
+ 1
688 return _calculate_ratio(matches
, len(self
.a
) + len(self
.b
))
690 def real_quick_ratio(self
):
691 """Return an upper bound on ratio() very quickly.
693 This isn't defined beyond that it is an upper bound on .ratio(), and
694 is faster to compute than either .ratio() or .quick_ratio().
697 la
, lb
= len(self
.a
), len(self
.b
)
698 # can't have more matches than the number of elements in the
700 return _calculate_ratio(min(la
, lb
), la
+ lb
)
702 def get_close_matches(word
, possibilities
, n
=3, cutoff
=0.6):
703 """Use SequenceMatcher to return list of the best "good enough" matches.
705 word is a sequence for which close matches are desired (typically a
708 possibilities is a list of sequences against which to match word
709 (typically a list of strings).
711 Optional arg n (default 3) is the maximum number of close matches to
712 return. n must be > 0.
714 Optional arg cutoff (default 0.6) is a float in [0, 1]. Possibilities
715 that don't score at least that similar to word are ignored.
717 The best (no more than n) matches among the possibilities are returned
718 in a list, sorted by similarity score, most similar first.
720 >>> get_close_matches("appel", ["ape", "apple", "peach", "puppy"])
722 >>> import keyword as _keyword
723 >>> get_close_matches("wheel", _keyword.kwlist)
725 >>> get_close_matches("Apple", _keyword.kwlist)
727 >>> get_close_matches("accept", _keyword.kwlist)
732 raise ValueError("n must be > 0: %r" % (n
,))
733 if not 0.0 <= cutoff
<= 1.0:
734 raise ValueError("cutoff must be in [0.0, 1.0]: %r" % (cutoff
,))
736 s
= SequenceMatcher()
738 for x
in possibilities
:
740 if s
.real_quick_ratio() >= cutoff
and \
741 s
.quick_ratio() >= cutoff
and \
743 result
.append((s
.ratio(), x
))
745 # Move the best scorers to head of list
746 result
= heapq
.nlargest(n
, result
)
747 # Strip scores for the best n matches
748 return [x
for score
, x
in result
]
750 def _count_leading(line
, ch
):
752 Return number of `ch` characters at the start of `line`.
756 >>> _count_leading(' abc', ' ')
761 while i
< n
and line
[i
] == ch
:
767 Differ is a class for comparing sequences of lines of text, and
768 producing human-readable differences or deltas. Differ uses
769 SequenceMatcher both to compare sequences of lines, and to compare
770 sequences of characters within similar (near-matching) lines.
772 Each line of a Differ delta begins with a two-letter code:
774 '- ' line unique to sequence 1
775 '+ ' line unique to sequence 2
776 ' ' line common to both sequences
777 '? ' line not present in either input sequence
779 Lines beginning with '? ' attempt to guide the eye to intraline
780 differences, and were not present in either input sequence. These lines
781 can be confusing if the sequences contain tab characters.
783 Note that Differ makes no claim to produce a *minimal* diff. To the
784 contrary, minimal diffs are often counter-intuitive, because they synch
785 up anywhere possible, sometimes accidental matches 100 pages apart.
786 Restricting synch points to contiguous matches preserves some notion of
787 locality, at the occasional cost of producing a longer diff.
789 Example: Comparing two texts.
791 First we set up the texts, sequences of individual single-line strings
792 ending with newlines (such sequences can also be obtained from the
793 `readlines()` method of file-like objects):
795 >>> text1 = ''' 1. Beautiful is better than ugly.
796 ... 2. Explicit is better than implicit.
797 ... 3. Simple is better than complex.
798 ... 4. Complex is better than complicated.
799 ... '''.splitlines(1)
804 >>> text2 = ''' 1. Beautiful is better than ugly.
805 ... 3. Simple is better than complex.
806 ... 4. Complicated is better than complex.
807 ... 5. Flat is better than nested.
808 ... '''.splitlines(1)
810 Next we instantiate a Differ object:
814 Note that when instantiating a Differ object we may pass functions to
815 filter out line and character 'junk'. See Differ.__init__ for details.
817 Finally, we compare the two:
819 >>> result = list(d.compare(text1, text2))
821 'result' is a list of strings, so let's pretty-print it:
823 >>> from pprint import pprint as _pprint
825 [' 1. Beautiful is better than ugly.\n',
826 '- 2. Explicit is better than implicit.\n',
827 '- 3. Simple is better than complex.\n',
828 '+ 3. Simple is better than complex.\n',
830 '- 4. Complex is better than complicated.\n',
832 '+ 4. Complicated is better than complex.\n',
834 '+ 5. Flat is better than nested.\n']
836 As a single multi-line string it looks like this:
838 >>> print(''.join(result), end="")
839 1. Beautiful is better than ugly.
840 - 2. Explicit is better than implicit.
841 - 3. Simple is better than complex.
842 + 3. Simple is better than complex.
844 - 4. Complex is better than complicated.
846 + 4. Complicated is better than complex.
848 + 5. Flat is better than nested.
852 __init__(linejunk=None, charjunk=None)
853 Construct a text differencer, with optional filters.
856 Compare two sequences of lines; generate the resulting delta.
859 def __init__(self
, linejunk
=None, charjunk
=None):
861 Construct a text differencer, with optional filters.
863 The two optional keyword parameters are for filter functions:
865 - `linejunk`: A function that should accept a single string argument,
866 and return true iff the string is junk. The module-level function
867 `IS_LINE_JUNK` may be used to filter out lines without visible
868 characters, except for at most one splat ('#'). It is recommended
869 to leave linejunk None; as of Python 2.3, the underlying
870 SequenceMatcher class has grown an adaptive notion of "noise" lines
871 that's better than any static definition the author has ever been
874 - `charjunk`: A function that should accept a string of length 1. The
875 module-level function `IS_CHARACTER_JUNK` may be used to filter out
876 whitespace characters (a blank or tab; **note**: bad idea to include
877 newline in this!). Use of IS_CHARACTER_JUNK is recommended.
880 self
.linejunk
= linejunk
881 self
.charjunk
= charjunk
883 def compare(self
, a
, b
):
885 Compare two sequences of lines; generate the resulting delta.
887 Each sequence must contain individual single-line strings ending with
888 newlines. Such sequences can be obtained from the `readlines()` method
889 of file-like objects. The delta generated also consists of newline-
890 terminated strings, ready to be printed as-is via the writeline()
891 method of a file-like object.
895 >>> print(''.join(Differ().compare('one\ntwo\nthree\n'.splitlines(1),
896 ... '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 range(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), end="")
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 range(blo
, bhi
):
975 cruncher
.set_seq2(bj
)
976 for i
in range(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', '\tabcdefGhijkl\n',
1064 ... ' ^ ^ ^ ', ' ^ ^ ^ ')
1065 >>> for line in results: print(repr(line))
1067 '- \tabcDefghiJkl\n'
1069 '+ \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 common
= min(common
, _count_leading(btags
[:common
], " "))
1078 atags
= atags
[common
:].rstrip()
1079 btags
= btags
[common
:].rstrip()
1083 yield "? %s%s\n" % ("\t" * common
, atags
)
1087 yield "? %s%s\n" % ("\t" * common
, btags
)
1089 # With respect to junk, an earlier version of ndiff simply refused to
1090 # *start* a match with a junk element. The result was cases like this:
1091 # before: private Thread currentThread;
1092 # after: private volatile Thread currentThread;
1093 # If you consider whitespace to be junk, the longest contiguous match
1094 # not starting with junk is "e Thread currentThread". So ndiff reported
1095 # that "e volatil" was inserted between the 't' and the 'e' in "private".
1096 # While an accurate view, to people that's absurd. The current version
1097 # looks for matching blocks that are entirely junk-free, then extends the
1098 # longest one of those as far as possible but only with matching junk.
1099 # So now "currentThread" is matched, then extended to suck up the
1100 # preceding blank; then "private" is matched, and extended to suck up the
1101 # following blank; then "Thread" is matched; and finally ndiff reports
1102 # that "volatile " was inserted before "Thread". The only quibble
1103 # remaining is that perhaps it was really the case that " volatile"
1104 # was inserted after "private". I can live with that <wink>.
1108 def IS_LINE_JUNK(line
, pat
=re
.compile(r
"\s*#?\s*$").match
):
1110 Return 1 for ignorable line: iff `line` is blank or contains a single '#'.
1114 >>> IS_LINE_JUNK('\n')
1116 >>> IS_LINE_JUNK(' # \n')
1118 >>> IS_LINE_JUNK('hello\n')
1122 return pat(line
) is not None
1124 def IS_CHARACTER_JUNK(ch
, ws
=" \t"):
1126 Return 1 for ignorable character: iff `ch` is a space or tab.
1130 >>> IS_CHARACTER_JUNK(' ')
1132 >>> IS_CHARACTER_JUNK('\t')
1134 >>> IS_CHARACTER_JUNK('\n')
1136 >>> IS_CHARACTER_JUNK('x')
1143 def unified_diff(a
, b
, fromfile
='', tofile
='', fromfiledate
='',
1144 tofiledate
='', n
=3, lineterm
='\n'):
1146 Compare two sequences of lines; generate the delta as a unified diff.
1148 Unified diffs are a compact way of showing line changes and a few
1149 lines of context. The number of context lines is set by 'n' which
1152 By default, the diff control lines (those with ---, +++, or @@) are
1153 created with a trailing newline. This is helpful so that inputs
1154 created from file.readlines() result in diffs that are suitable for
1155 file.writelines() since both the inputs and outputs have trailing
1158 For inputs that do not have trailing newlines, set the lineterm
1159 argument to "" so that the output will be uniformly newline free.
1161 The unidiff format normally has a header for filenames and modification
1162 times. Any or all of these may be specified using strings for
1163 'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'. The modification
1164 times are normally expressed in the format returned by time.ctime().
1168 >>> for line in unified_diff('one two three four'.split(),
1169 ... 'zero one tree four'.split(), 'Original', 'Current',
1170 ... 'Sat Jan 26 23:30:50 1991', 'Fri Jun 06 10:20:52 2003',
1173 --- Original Sat Jan 26 23:30:50 1991
1174 +++ Current Fri Jun 06 10:20:52 2003
1185 for group
in SequenceMatcher(None,a
,b
).get_grouped_opcodes(n
):
1187 yield '--- %s %s%s' % (fromfile
, fromfiledate
, lineterm
)
1188 yield '+++ %s %s%s' % (tofile
, tofiledate
, lineterm
)
1190 i1
, i2
, j1
, j2
= group
[0][1], group
[-1][2], group
[0][3], group
[-1][4]
1191 yield "@@ -%d,%d +%d,%d @@%s" % (i1
+1, i2
-i1
, j1
+1, j2
-j1
, lineterm
)
1192 for tag
, i1
, i2
, j1
, j2
in group
:
1194 for line
in a
[i1
:i2
]:
1197 if tag
== 'replace' or tag
== 'delete':
1198 for line
in a
[i1
:i2
]:
1200 if tag
== 'replace' or tag
== 'insert':
1201 for line
in b
[j1
:j2
]:
1204 # See http://www.unix.org/single_unix_specification/
1205 def context_diff(a
, b
, fromfile
='', tofile
='',
1206 fromfiledate
='', tofiledate
='', n
=3, lineterm
='\n'):
1208 Compare two sequences of lines; generate the delta as a context diff.
1210 Context diffs are a compact way of showing line changes and a few
1211 lines of context. The number of context lines is set by 'n' which
1214 By default, the diff control lines (those with *** or ---) are
1215 created with a trailing newline. This is helpful so that inputs
1216 created from file.readlines() result in diffs that are suitable for
1217 file.writelines() since both the inputs and outputs have trailing
1220 For inputs that do not have trailing newlines, set the lineterm
1221 argument to "" so that the output will be uniformly newline free.
1223 The context diff format normally has a header for filenames and
1224 modification times. Any or all of these may be specified using
1225 strings for 'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'.
1226 The modification times are normally expressed in the format returned
1227 by time.ctime(). If not specified, the strings default to blanks.
1231 >>> print(''.join(context_diff('one\ntwo\nthree\nfour\n'.splitlines(1),
1232 ... 'zero\none\ntree\nfour\n'.splitlines(1), 'Original', 'Current',
1233 ... 'Sat Jan 26 23:30:50 1991', 'Fri Jun 06 10:22:46 2003')),
1235 *** Original Sat Jan 26 23:30:50 1991
1236 --- Current Fri Jun 06 10:22:46 2003
1251 prefixmap
= {'insert':'+ ', 'delete':'- ', 'replace':'! ', 'equal':' '}
1252 for group
in SequenceMatcher(None,a
,b
).get_grouped_opcodes(n
):
1254 yield '*** %s %s%s' % (fromfile
, fromfiledate
, lineterm
)
1255 yield '--- %s %s%s' % (tofile
, tofiledate
, lineterm
)
1258 yield '***************%s' % (lineterm
,)
1259 if group
[-1][2] - group
[0][1] >= 2:
1260 yield '*** %d,%d ****%s' % (group
[0][1]+1, group
[-1][2], lineterm
)
1262 yield '*** %d ****%s' % (group
[-1][2], lineterm
)
1263 visiblechanges
= [e
for e
in group
if e
[0] in ('replace', 'delete')]
1265 for tag
, i1
, i2
, _
, _
in group
:
1267 for line
in a
[i1
:i2
]:
1268 yield prefixmap
[tag
] + line
1270 if group
[-1][4] - group
[0][3] >= 2:
1271 yield '--- %d,%d ----%s' % (group
[0][3]+1, group
[-1][4], lineterm
)
1273 yield '--- %d ----%s' % (group
[-1][4], lineterm
)
1274 visiblechanges
= [e
for e
in group
if e
[0] in ('replace', 'insert')]
1276 for tag
, _
, _
, j1
, j2
in group
:
1278 for line
in b
[j1
:j2
]:
1279 yield prefixmap
[tag
] + line
1281 def ndiff(a
, b
, linejunk
=None, charjunk
=IS_CHARACTER_JUNK
):
1283 Compare `a` and `b` (lists of strings); return a `Differ`-style delta.
1285 Optional keyword parameters `linejunk` and `charjunk` are for filter
1286 functions (or None):
1288 - linejunk: A function that should accept a single string argument, and
1289 return true iff the string is junk. The default is None, and is
1290 recommended; as of Python 2.3, an adaptive notion of "noise" lines is
1291 used that does a good job on its own.
1293 - charjunk: A function that should accept a string of length 1. The
1294 default is module-level function IS_CHARACTER_JUNK, which filters out
1295 whitespace characters (a blank or tab; note: bad idea to include newline
1298 Tools/scripts/ndiff.py is a command-line front-end to this function.
1302 >>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
1303 ... 'ore\ntree\nemu\n'.splitlines(1))
1304 >>> print(''.join(diff), end="")
1315 return Differ(linejunk
, charjunk
).compare(a
, b
)
1317 def _mdiff(fromlines
, tolines
, context
=None, linejunk
=None,
1318 charjunk
=IS_CHARACTER_JUNK
):
1319 r
"""Returns generator yielding marked up from/to side by side differences.
1322 fromlines -- list of text lines to compared to tolines
1323 tolines -- list of text lines to be compared to fromlines
1324 context -- number of context lines to display on each side of difference,
1325 if None, all from/to text lines will be generated.
1326 linejunk -- passed on to ndiff (see ndiff documentation)
1327 charjunk -- passed on to ndiff (see ndiff documentation)
1329 This function returns an interator which returns a tuple:
1330 (from line tuple, to line tuple, boolean flag)
1332 from/to line tuple -- (line num, line text)
1333 line num -- integer or None (to indicate a context separation)
1334 line text -- original line text with following markers inserted:
1335 '\0+' -- marks start of added text
1336 '\0-' -- marks start of deleted text
1337 '\0^' -- marks start of changed text
1338 '\1' -- marks end of added/deleted/changed text
1340 boolean flag -- None indicates context separation, True indicates
1341 either "from" or "to" line contains a change, otherwise False.
1343 This function/iterator was originally developed to generate side by side
1344 file difference for making HTML pages (see HtmlDiff class for example
1347 Note, this function utilizes the ndiff function to generate the side by
1348 side difference markup. Optional ndiff arguments may be passed to this
1349 function and they in turn will be passed to ndiff.
1353 # regular expression for finding intraline change indices
1354 change_re
= re
.compile('(\++|\-+|\^+)')
1356 # create the difference iterator to generate the differences
1357 diff_lines_iterator
= ndiff(fromlines
,tolines
,linejunk
,charjunk
)
1359 def _make_line(lines
, format_key
, side
, num_lines
=[0,0]):
1360 """Returns line of text with user's change markup and line formatting.
1362 lines -- list of lines from the ndiff generator to produce a line of
1363 text from. When producing the line of text to return, the
1364 lines used are removed from this list.
1365 format_key -- '+' return first line in list with "add" markup around
1367 '-' return first line in list with "delete" markup around
1369 '?' return first line in list with add/delete/change
1370 intraline markup (indices obtained from second line)
1371 None return first line in list with no markup
1372 side -- indice into the num_lines list (0=from,1=to)
1373 num_lines -- from/to current line number. This is NOT intended to be a
1374 passed parameter. It is present as a keyword argument to
1375 maintain memory of the current line numbers between calls
1378 Note, this function is purposefully not defined at the module scope so
1379 that data it needs from its parent function (within whose context it
1380 is defined) does not need to be of module scope.
1382 num_lines
[side
] += 1
1383 # Handle case where no user markup is to be added, just return line of
1384 # text with user's line format to allow for usage of the line number.
1385 if format_key
is None:
1386 return (num_lines
[side
],lines
.pop(0)[2:])
1387 # Handle case of intraline changes
1388 if format_key
== '?':
1389 text
, markers
= lines
.pop(0), lines
.pop(0)
1390 # find intraline changes (store change type and indices in tuples)
1392 def record_sub_info(match_object
,sub_info
=sub_info
):
1393 sub_info
.append([match_object
.group(1)[0],match_object
.span()])
1394 return match_object
.group(1)
1395 change_re
.sub(record_sub_info
,markers
)
1396 # process each tuple inserting our special marks that won't be
1397 # noticed by an xml/html escaper.
1398 for key
,(begin
,end
) in sub_info
[::-1]:
1399 text
= text
[0:begin
]+'\0'+key
+text
[begin
:end
]+'\1'+text
[end
:]
1401 # Handle case of add/delete entire line
1403 text
= lines
.pop(0)[2:]
1404 # if line of text is just a newline, insert a space so there is
1405 # something for the user to highlight and see.
1408 # insert marks that won't be noticed by an xml/html escaper.
1409 text
= '\0' + format_key
+ text
+ '\1'
1410 # Return line of text, first allow user's line formatter to do its
1411 # thing (such as adding the line number) then replace the special
1412 # marks with what the user's change markup.
1413 return (num_lines
[side
],text
)
1415 def _line_iterator():
1416 """Yields from/to lines of text with a change indication.
1418 This function is an iterator. It itself pulls lines from a
1419 differencing iterator, processes them and yields them. When it can
1420 it yields both a "from" and a "to" line, otherwise it will yield one
1421 or the other. In addition to yielding the lines of from/to text, a
1422 boolean flag is yielded to indicate if the text line(s) have
1423 differences in them.
1425 Note, this function is purposefully not defined at the module scope so
1426 that data it needs from its parent function (within whose context it
1427 is defined) does not need to be of module scope.
1430 num_blanks_pending
, num_blanks_to_yield
= 0, 0
1432 # Load up next 4 lines so we can look ahead, create strings which
1433 # are a concatenation of the first character of each of the 4 lines
1434 # so we can do some very readable comparisons.
1435 while len(lines
) < 4:
1437 lines
.append(next(diff_lines_iterator
))
1438 except StopIteration:
1440 s
= ''.join([line
[0] for line
in lines
])
1441 if s
.startswith('X'):
1442 # When no more lines, pump out any remaining blank lines so the
1443 # corresponding add/delete lines get a matching blank line so
1444 # all line pairs get yielded at the next level.
1445 num_blanks_to_yield
= num_blanks_pending
1446 elif s
.startswith('-?+?'):
1447 # simple intraline change
1448 yield _make_line(lines
,'?',0), _make_line(lines
,'?',1), True
1450 elif s
.startswith('--++'):
1451 # in delete block, add block coming: we do NOT want to get
1452 # caught up on blank lines yet, just process the delete line
1453 num_blanks_pending
-= 1
1454 yield _make_line(lines
,'-',0), None, True
1456 elif s
.startswith(('--?+', '--+', '- ')):
1457 # in delete block and see a intraline change or unchanged line
1458 # coming: yield the delete line and then blanks
1459 from_line
,to_line
= _make_line(lines
,'-',0), None
1460 num_blanks_to_yield
,num_blanks_pending
= num_blanks_pending
-1,0
1461 elif s
.startswith('-+?'):
1463 yield _make_line(lines
,None,0), _make_line(lines
,'?',1), True
1465 elif s
.startswith('-?+'):
1467 yield _make_line(lines
,'?',0), _make_line(lines
,None,1), True
1469 elif s
.startswith('-'):
1471 num_blanks_pending
-= 1
1472 yield _make_line(lines
,'-',0), None, True
1474 elif s
.startswith('+--'):
1475 # in add block, delete block coming: we do NOT want to get
1476 # caught up on blank lines yet, just process the add line
1477 num_blanks_pending
+= 1
1478 yield None, _make_line(lines
,'+',1), True
1480 elif s
.startswith(('+ ', '+-')):
1481 # will be leaving an add block: yield blanks then add line
1482 from_line
, to_line
= None, _make_line(lines
,'+',1)
1483 num_blanks_to_yield
,num_blanks_pending
= num_blanks_pending
+1,0
1484 elif s
.startswith('+'):
1485 # inside an add block, yield the add line
1486 num_blanks_pending
+= 1
1487 yield None, _make_line(lines
,'+',1), True
1489 elif s
.startswith(' '):
1490 # unchanged text, yield it to both sides
1491 yield _make_line(lines
[:],None,0),_make_line(lines
,None,1),False
1493 # Catch up on the blank lines so when we yield the next from/to
1494 # pair, they are lined up.
1495 while(num_blanks_to_yield
< 0):
1496 num_blanks_to_yield
+= 1
1497 yield None,('','\n'),True
1498 while(num_blanks_to_yield
> 0):
1499 num_blanks_to_yield
-= 1
1500 yield ('','\n'),None,True
1501 if s
.startswith('X'):
1504 yield from_line
,to_line
,True
1506 def _line_pair_iterator():
1507 """Yields from/to lines of text with a change indication.
1509 This function is an iterator. It itself pulls lines from the line
1510 iterator. Its difference from that iterator is that this function
1511 always yields a pair of from/to text lines (with the change
1512 indication). If necessary it will collect single from/to lines
1513 until it has a matching pair from/to pair to yield.
1515 Note, this function is purposefully not defined at the module scope so
1516 that data it needs from its parent function (within whose context it
1517 is defined) does not need to be of module scope.
1519 line_iterator
= _line_iterator()
1520 fromlines
,tolines
=[],[]
1522 # Collecting lines of text until we have a from/to pair
1523 while (len(fromlines
)==0 or len(tolines
)==0):
1524 from_line
, to_line
, found_diff
= next(line_iterator
)
1525 if from_line
is not None:
1526 fromlines
.append((from_line
,found_diff
))
1527 if to_line
is not None:
1528 tolines
.append((to_line
,found_diff
))
1529 # Once we have a pair, remove them from the collection and yield it
1530 from_line
, fromDiff
= fromlines
.pop(0)
1531 to_line
, to_diff
= tolines
.pop(0)
1532 yield (from_line
,to_line
,fromDiff
or to_diff
)
1534 # Handle case where user does not want context differencing, just yield
1535 # them up without doing anything else with them.
1536 line_pair_iterator
= _line_pair_iterator()
1539 yield next(line_pair_iterator
)
1540 # Handle case where user wants context differencing. We must do some
1541 # storage of lines until we know for sure that they are to be yielded.
1546 # Store lines up until we find a difference, note use of a
1547 # circular queue because we only need to keep around what
1548 # we need for context.
1549 index
, contextLines
= 0, [None]*(context
)
1551 while(found_diff
is False):
1552 from_line
, to_line
, found_diff
= next(line_pair_iterator
)
1554 contextLines
[i
] = (from_line
, to_line
, found_diff
)
1556 # Yield lines that we have collected so far, but first yield
1557 # the user's separator.
1559 yield None, None, None
1560 lines_to_write
= context
1562 lines_to_write
= index
1564 while(lines_to_write
):
1567 yield contextLines
[i
]
1569 # Now yield the context lines after the change
1570 lines_to_write
= context
-1
1571 while(lines_to_write
):
1572 from_line
, to_line
, found_diff
= next(line_pair_iterator
)
1573 # If another change within the context, extend the context
1575 lines_to_write
= context
-1
1578 yield from_line
, to_line
, found_diff
1581 _file_template
= """
1582 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
1583 "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
1588 <meta http-equiv="Content-Type"
1589 content="text/html; charset=ISO-8859-1" />
1591 <style type="text/css">%(styles)s
1602 table.diff {font-family:Courier; border:medium;}
1603 .diff_header {background-color:#e0e0e0}
1604 td.diff_header {text-align:right}
1605 .diff_next {background-color:#c0c0c0}
1606 .diff_add {background-color:#aaffaa}
1607 .diff_chg {background-color:#ffff77}
1608 .diff_sub {background-color:#ffaaaa}"""
1610 _table_template
= """
1611 <table class="diff" id="difflib_chg_%(prefix)s_top"
1612 cellspacing="0" cellpadding="0" rules="groups" >
1613 <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>
1614 <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>
1617 %(data_rows)s </tbody>
1621 <table class="diff" summary="Legends">
1622 <tr> <th colspan="2"> Legends </th> </tr>
1623 <tr> <td> <table border="" summary="Colors">
1624 <tr><th> Colors </th> </tr>
1625 <tr><td class="diff_add"> Added </td></tr>
1626 <tr><td class="diff_chg">Changed</td> </tr>
1627 <tr><td class="diff_sub">Deleted</td> </tr>
1629 <td> <table border="" summary="Links">
1630 <tr><th colspan="2"> Links </th> </tr>
1631 <tr><td>(f)irst change</td> </tr>
1632 <tr><td>(n)ext change</td> </tr>
1633 <tr><td>(t)op</td> </tr>
1637 class HtmlDiff(object):
1638 """For producing HTML side by side comparison with change highlights.
1640 This class can be used to create an HTML table (or a complete HTML file
1641 containing the table) showing a side by side, line by line comparison
1642 of text with inter-line and intra-line change highlights. The table can
1643 be generated in either full or contextual difference mode.
1645 The following methods are provided for HTML generation:
1647 make_table -- generates HTML for a single side by side table
1648 make_file -- generates complete HTML file with a single side by side table
1650 See tools/scripts/diff.py for an example usage of this class.
1653 _file_template
= _file_template
1655 _table_template
= _table_template
1659 def __init__(self
,tabsize
=8,wrapcolumn
=None,linejunk
=None,
1660 charjunk
=IS_CHARACTER_JUNK
):
1661 """HtmlDiff instance initializer
1664 tabsize -- tab stop spacing, defaults to 8.
1665 wrapcolumn -- column number where lines are broken and wrapped,
1666 defaults to None where lines are not wrapped.
1667 linejunk,charjunk -- keyword arguments passed into ndiff() (used to by
1668 HtmlDiff() to generate the side by side HTML differences). See
1669 ndiff() documentation for argument default values and descriptions.
1671 self
._tabsize
= tabsize
1672 self
._wrapcolumn
= wrapcolumn
1673 self
._linejunk
= linejunk
1674 self
._charjunk
= charjunk
1676 def make_file(self
,fromlines
,tolines
,fromdesc
='',todesc
='',context
=False,
1678 """Returns HTML file of side by side comparison with change highlights
1681 fromlines -- list of "from" lines
1682 tolines -- list of "to" lines
1683 fromdesc -- "from" file column header string
1684 todesc -- "to" file column header string
1685 context -- set to True for contextual differences (defaults to False
1686 which shows full differences).
1687 numlines -- number of context lines. When context is set True,
1688 controls number of lines displayed before and after the change.
1689 When context is False, controls the number of lines to place
1690 the "next" link anchors before the next change (so click of
1691 "next" link jumps to just before the change).
1694 return self
._file
_template
% dict(
1695 styles
= self
._styles
,
1696 legend
= self
._legend
,
1697 table
= self
.make_table(fromlines
,tolines
,fromdesc
,todesc
,
1698 context
=context
,numlines
=numlines
))
1700 def _tab_newline_replace(self
,fromlines
,tolines
):
1701 """Returns from/to line lists with tabs expanded and newlines removed.
1703 Instead of tab characters being replaced by the number of spaces
1704 needed to fill in to the next tab stop, this function will fill
1705 the space with tab characters. This is done so that the difference
1706 algorithms can identify changes in a file when tabs are replaced by
1707 spaces and vice versa. At the end of the HTML generation, the tab
1708 characters will be replaced with a nonbreakable space.
1710 def expand_tabs(line
):
1712 line
= line
.replace(' ','\0')
1713 # expand tabs into spaces
1714 line
= line
.expandtabs(self
._tabsize
)
1715 # relace spaces from expanded tabs back into tab characters
1716 # (we'll replace them with markup after we do differencing)
1717 line
= line
.replace(' ','\t')
1718 return line
.replace('\0',' ').rstrip('\n')
1719 fromlines
= [expand_tabs(line
) for line
in fromlines
]
1720 tolines
= [expand_tabs(line
) for line
in tolines
]
1721 return fromlines
,tolines
1723 def _split_line(self
,data_list
,line_num
,text
):
1724 """Builds list of text lines by splitting text lines at wrap point
1726 This function will determine if the input text line needs to be
1727 wrapped (split) into separate lines. If so, the first wrap point
1728 will be determined and the first line appended to the output
1729 text line list. This function is used recursively to handle
1730 the second part of the split line to further split it.
1732 # if blank line or context separator, just add it to the output list
1734 data_list
.append((line_num
,text
))
1737 # if line text doesn't need wrapping, just add it to the output list
1739 max = self
._wrapcolumn
1740 if (size
<= max) or ((size
-(text
.count('\0')*3)) <= max):
1741 data_list
.append((line_num
,text
))
1744 # scan text looking for the wrap point, keeping track if the wrap
1745 # point is inside markers
1749 while n
< max and i
< size
:
1754 elif text
[i
] == '\1':
1761 # wrap point is inside text, break it up into separate lines
1765 # if wrap point is inside markers, place end marker at end of first
1766 # line and start marker at beginning of second line because each
1767 # line will have its own table tag markup around it.
1769 line1
= line1
+ '\1'
1770 line2
= '\0' + mark
+ line2
1772 # tack on first line onto the output list
1773 data_list
.append((line_num
,line1
))
1775 # use this routine again to wrap the remaining text
1776 self
._split
_line
(data_list
,'>',line2
)
1778 def _line_wrapper(self
,diffs
):
1779 """Returns iterator that splits (wraps) mdiff text lines"""
1781 # pull from/to data and flags from mdiff iterator
1782 for fromdata
,todata
,flag
in diffs
:
1783 # check for context separators and pass them through
1785 yield fromdata
,todata
,flag
1787 (fromline
,fromtext
),(toline
,totext
) = fromdata
,todata
1788 # for each from/to line split it at the wrap column to form
1789 # list of text lines.
1790 fromlist
,tolist
= [],[]
1791 self
._split
_line
(fromlist
,fromline
,fromtext
)
1792 self
._split
_line
(tolist
,toline
,totext
)
1793 # yield from/to line in pairs inserting blank lines as
1794 # necessary when one side has more wrapped lines
1795 while fromlist
or tolist
:
1797 fromdata
= fromlist
.pop(0)
1801 todata
= tolist
.pop(0)
1804 yield fromdata
,todata
,flag
1806 def _collect_lines(self
,diffs
):
1807 """Collects mdiff output into separate lists
1809 Before storing the mdiff from/to data into a list, it is converted
1810 into a single line of text with HTML markup.
1813 fromlist
,tolist
,flaglist
= [],[],[]
1814 # pull from/to data and flags from mdiff style iterator
1815 for fromdata
,todata
,flag
in diffs
:
1817 # store HTML markup of the lines into the lists
1818 fromlist
.append(self
._format
_line
(0,flag
,*fromdata
))
1819 tolist
.append(self
._format
_line
(1,flag
,*todata
))
1821 # exceptions occur for lines where context separators go
1822 fromlist
.append(None)
1824 flaglist
.append(flag
)
1825 return fromlist
,tolist
,flaglist
1827 def _format_line(self
,side
,flag
,linenum
,text
):
1828 """Returns HTML markup of "from" / "to" text lines
1830 side -- 0 or 1 indicating "from" or "to" text
1831 flag -- indicates if difference on line
1832 linenum -- line number (used for line number column)
1833 text -- line text to be marked up
1836 linenum
= '%d' % linenum
1837 id = ' id="%s%s"' % (self
._prefix
[side
],linenum
)
1839 # handle blank lines where linenum is '>' or ''
1841 # replace those things that would get confused with HTML symbols
1842 text
=text
.replace("&","&").replace(">",">").replace("<","<")
1844 # make space non-breakable so they don't get compressed or line wrapped
1845 text
= text
.replace(' ',' ').rstrip()
1847 return '<td class="diff_header"%s>%s</td><td nowrap="nowrap">%s</td>' \
1850 def _make_prefix(self
):
1851 """Create unique anchor prefixes"""
1853 # Generate a unique anchor prefix so multiple tables
1854 # can exist on the same HTML page without conflicts.
1855 fromprefix
= "from%d_" % HtmlDiff
._default
_prefix
1856 toprefix
= "to%d_" % HtmlDiff
._default
_prefix
1857 HtmlDiff
._default
_prefix
+= 1
1858 # store prefixes so line format method has access
1859 self
._prefix
= [fromprefix
,toprefix
]
1861 def _convert_flags(self
,fromlist
,tolist
,flaglist
,context
,numlines
):
1862 """Makes list of "next" links"""
1864 # all anchor names will be generated using the unique "to" prefix
1865 toprefix
= self
._prefix
[1]
1867 # process change flags, generating middle column of next anchors/links
1868 next_id
= ['']*len(flaglist
)
1869 next_href
= ['']*len(flaglist
)
1870 num_chg
, in_change
= 0, False
1872 for i
,flag
in enumerate(flaglist
):
1877 # at the beginning of a change, drop an anchor a few lines
1878 # (the context lines) before the change for the previous
1880 i
= max([0,i
-numlines
])
1881 next_id
[i
] = ' id="difflib_chg_%s_%d"' % (toprefix
,num_chg
)
1882 # at the beginning of a change, drop a link to the next
1885 next_href
[last
] = '<a href="#difflib_chg_%s_%d">n</a>' % (
1889 # check for cases where there is no content to avoid exceptions
1896 fromlist
= ['<td></td><td> No Differences Found </td>']
1899 fromlist
= tolist
= ['<td></td><td> Empty File </td>']
1900 # if not a change on first line, drop a link
1902 next_href
[0] = '<a href="#difflib_chg_%s_0">f</a>' % toprefix
1903 # redo the last link to link to the top
1904 next_href
[last
] = '<a href="#difflib_chg_%s_top">t</a>' % (toprefix
)
1906 return fromlist
,tolist
,flaglist
,next_href
,next_id
1908 def make_table(self
,fromlines
,tolines
,fromdesc
='',todesc
='',context
=False,
1910 """Returns HTML table of side by side comparison with change highlights
1913 fromlines -- list of "from" lines
1914 tolines -- list of "to" lines
1915 fromdesc -- "from" file column header string
1916 todesc -- "to" file column header string
1917 context -- set to True for contextual differences (defaults to False
1918 which shows full differences).
1919 numlines -- number of context lines. When context is set True,
1920 controls number of lines displayed before and after the change.
1921 When context is False, controls the number of lines to place
1922 the "next" link anchors before the next change (so click of
1923 "next" link jumps to just before the change).
1926 # make unique anchor prefixes so that multiple tables may exist
1927 # on the same page without conflict.
1930 # change tabs to spaces before it gets more difficult after we insert
1932 fromlines
,tolines
= self
._tab
_newline
_replace
(fromlines
,tolines
)
1934 # create diffs iterator which generates side by side from/to data
1936 context_lines
= numlines
1938 context_lines
= None
1939 diffs
= _mdiff(fromlines
,tolines
,context_lines
,linejunk
=self
._linejunk
,
1940 charjunk
=self
._charjunk
)
1942 # set up iterator to wrap lines that exceed desired width
1943 if self
._wrapcolumn
:
1944 diffs
= self
._line
_wrapper
(diffs
)
1946 # collect up from/to lines and flags into lists (also format the lines)
1947 fromlist
,tolist
,flaglist
= self
._collect
_lines
(diffs
)
1949 # process change flags, generating middle column of next anchors/links
1950 fromlist
,tolist
,flaglist
,next_href
,next_id
= self
._convert
_flags
(
1951 fromlist
,tolist
,flaglist
,context
,numlines
)
1954 fmt
= ' <tr><td class="diff_next"%s>%s</td>%s' + \
1955 '<td class="diff_next">%s</td>%s</tr>\n'
1956 for i
in range(len(flaglist
)):
1957 if flaglist
[i
] is None:
1958 # mdiff yields None on separator lines skip the bogus ones
1959 # generated for the first line
1961 s
.append(' </tbody> \n <tbody>\n')
1963 s
.append( fmt
% (next_id
[i
],next_href
[i
],fromlist
[i
],
1964 next_href
[i
],tolist
[i
]))
1965 if fromdesc
or todesc
:
1966 header_row
= '<thead><tr>%s%s%s%s</tr></thead>' % (
1967 '<th class="diff_next"><br /></th>',
1968 '<th colspan="2" class="diff_header">%s</th>' % fromdesc
,
1969 '<th class="diff_next"><br /></th>',
1970 '<th colspan="2" class="diff_header">%s</th>' % todesc
)
1974 table
= self
._table
_template
% dict(
1975 data_rows
=''.join(s
),
1976 header_row
=header_row
,
1977 prefix
=self
._prefix
[1])
1979 return table
.replace('\0+','<span class="diff_add">'). \
1980 replace('\0-','<span class="diff_sub">'). \
1981 replace('\0^','<span class="diff_chg">'). \
1982 replace('\1','</span>'). \
1983 replace('\t',' ')
1987 def restore(delta
, which
):
1989 Generate one of the two sequences that generated a delta.
1991 Given a `delta` produced by `Differ.compare()` or `ndiff()`, extract
1992 lines originating from file 1 or 2 (parameter `which`), stripping off line
1997 >>> diff = ndiff('one\ntwo\nthree\n'.splitlines(1),
1998 ... 'ore\ntree\nemu\n'.splitlines(1))
1999 >>> diff = list(diff)
2000 >>> print(''.join(restore(diff, 1)), end="")
2004 >>> print(''.join(restore(diff, 2)), end="")
2010 tag
= {1: "- ", 2: "+ "}[int(which
)]
2012 raise ValueError('unknown delta choice (must be 1 or 2): %r'
2014 prefixes
= (" ", tag
)
2016 if line
[:2] in prefixes
:
2020 import doctest
, difflib
2021 return doctest
.testmod(difflib
)
2023 if __name__
== "__main__":