codekingpro/portable-devtools
114k
1"""2Module difflib -- helpers for computing deltas between objects.3 4Function get_close_matches(word, possibilities, n=3, cutoff=0.6):5 Use SequenceMatcher to return list of the best "good enough" matches.6 7Function context_diff(a, b):8 For two lists of strings, return a delta in context diff format.9 10Function ndiff(a, b):11 Return a delta: the difference between `a` and `b` (lists of strings).12 13Function restore(delta, which):14 Return one of the two sequences that generated an ndiff delta.15 16Function unified_diff(a, b):17 For two lists of strings, return a delta in unified diff format.18 19Class SequenceMatcher:20 A flexible class for comparing pairs of sequences of any type.21 22Class Differ:23 For producing human-readable deltas from sequences of lines of text.24 25Class HtmlDiff:26 For producing HTML side by side comparison with change highlights.27"""28 29__all__ = ['get_close_matches', 'ndiff', 'restore', 'SequenceMatcher',30 'Differ','IS_CHARACTER_JUNK', 'IS_LINE_JUNK', 'context_diff',31 'unified_diff', 'diff_bytes', 'HtmlDiff', 'Match']32 33from heapq import nlargest as _nlargest34from collections import namedtuple as _namedtuple35from types import GenericAlias36 37Match = _namedtuple('Match', 'a b size')38 39def _calculate_ratio(matches, length):40 if length:41 return 2.0 * matches / length42 return 1.043 44class SequenceMatcher:45 46 """47 SequenceMatcher is a flexible class for comparing pairs of sequences of48 any type, so long as the sequence elements are hashable. The basic49 algorithm predates, and is a little fancier than, an algorithm50 published in the late 1980's by Ratcliff and Obershelp under the51 hyperbolic name "gestalt pattern matching". The basic idea is to find52 the longest contiguous matching subsequence that contains no "junk"53 elements (R-O doesn't address junk). The same idea is then applied54 recursively to the pieces of the sequences to the left and to the right55 of the matching subsequence. This does not yield minimal edit56 sequences, but does tend to yield matches that "look right" to people.57 58 SequenceMatcher tries to compute a "human-friendly diff" between two59 sequences. Unlike e.g. UNIX(tm) diff, the fundamental notion is the60 longest *contiguous* & junk-free matching subsequence. That's what61 catches peoples' eyes. The Windows(tm) windiff has another interesting62 notion, pairing up elements that appear uniquely in each sequence.63 That, and the method here, appear to yield more intuitive difference64 reports than does diff. This method appears to be the least vulnerable65 to syncing up on blocks of "junk lines", though (like blank lines in66 ordinary text files, or maybe "<P>" lines in HTML files). That may be67 because this is the only method of the 3 that has a *concept* of68 "junk" <wink>.69 70 Example, comparing two strings, and considering blanks to be "junk":71 72 >>> s = SequenceMatcher(lambda x: x == " ",73 ... "private Thread currentThread;",74 ... "private volatile Thread currentThread;")75 >>>76 77 .ratio() returns a float in [0, 1], measuring the "similarity" of the78 sequences. As a rule of thumb, a .ratio() value over 0.6 means the79 sequences are close matches:80 81 >>> print(round(s.ratio(), 2))82 0.8783 >>>84 85 If you're only interested in where the sequences match,86 .get_matching_blocks() is handy:87 88 >>> for block in s.get_matching_blocks():89 ... print("a[%d] and b[%d] match for %d elements" % block)90 a[0] and b[0] match for 8 elements91 a[8] and b[17] match for 21 elements92 a[29] and b[38] match for 0 elements93 94 Note that the last tuple returned by .get_matching_blocks() is always a95 dummy, (len(a), len(b), 0), and this is the only case in which the last96 tuple element (number of elements matched) is 0.97 98 If you want to know how to change the first sequence into the second,99 use .get_opcodes():100 101 >>> for opcode in s.get_opcodes():102 ... print("%6s a[%d:%d] b[%d:%d]" % opcode)103 equal a[0:8] b[0:8]104 insert a[8:8] b[8:17]105 equal a[8:29] b[17:38]106 107 See the Differ class for a fancy human-friendly file differencer, which108 uses SequenceMatcher both to compare sequences of lines, and to compare109 sequences of characters within similar (near-matching) lines.110 111 See also function get_close_matches() in this module, which shows how112 simple code building on SequenceMatcher can be used to do useful work.113 114 Timing: Basic R-O is cubic time worst case and quadratic time expected115 case. SequenceMatcher is quadratic time for the worst case and has116 expected-case behavior dependent in a complicated way on how many117 elements the sequences have in common; best case time is linear.118 """119 120 def __init__(self, isjunk=None, a='', b='', autojunk=True):121 """Construct a SequenceMatcher.122 123 Optional arg isjunk is None (the default), or a one-argument124 function that takes a sequence element and returns true iff the125 element is junk. None is equivalent to passing "lambda x: 0", i.e.126 no elements are considered to be junk. For example, pass127 lambda x: x in " \\t"128 if you're comparing lines as sequences of characters, and don't129 want to synch up on blanks or hard tabs.130 131 Optional arg a is the first of two sequences to be compared. By132 default, an empty string. The elements of a must be hashable. See133 also .set_seqs() and .set_seq1().134 135 Optional arg b is the second of two sequences to be compared. By136 default, an empty string. The elements of b must be hashable. See137 also .set_seqs() and .set_seq2().138 139 Optional arg autojunk should be set to False to disable the140 "automatic junk heuristic" that treats popular elements as junk141 (see module documentation for more information).142 """143 144 # Members:145 # a146 # first sequence147 # b148 # second sequence; differences are computed as "what do149 # we need to do to 'a' to change it into 'b'?"150 # b2j151 # for x in b, b2j[x] is a list of the indices (into b)152 # at which x appears; junk and popular elements do not appear153 # fullbcount154 # for x in b, fullbcount[x] == the number of times x155 # appears in b; only materialized if really needed (used156 # only for computing quick_ratio())157 # matching_blocks158 # a list of (i, j, k) triples, where a[i:i+k] == b[j:j+k];159 # ascending & non-overlapping in i and in j; terminated by160 # a dummy (len(a), len(b), 0) sentinel161 # opcodes162 # a list of (tag, i1, i2, j1, j2) tuples, where tag is163 # one of164 # 'replace' a[i1:i2] should be replaced by b[j1:j2]165 # 'delete' a[i1:i2] should be deleted166 # 'insert' b[j1:j2] should be inserted167 # 'equal' a[i1:i2] == b[j1:j2]168 # isjunk169 # a user-supplied function taking a sequence element and170 # returning true iff the element is "junk" -- this has171 # subtle but helpful effects on the algorithm, which I'll172 # get around to writing up someday <0.9 wink>.173 # DON'T USE! Only __chain_b uses this. Use "in self.bjunk".174 # bjunk175 # the items in b for which isjunk is True.176 # bpopular177 # nonjunk items in b treated as junk by the heuristic (if used).178 179 self.isjunk = isjunk180 self.a = self.b = None181 self.autojunk = autojunk182 self.set_seqs(a, b)183 184 def set_seqs(self, a, b):185 """Set the two sequences to be compared.186 187 >>> s = SequenceMatcher()188 >>> s.set_seqs("abcd", "bcde")189 >>> s.ratio()190 0.75191 """192 193 self.set_seq1(a)194 self.set_seq2(b)195 196 def set_seq1(self, a):197 """Set the first sequence to be compared.198 199 The second sequence to be compared is not changed.200 201 >>> s = SequenceMatcher(None, "abcd", "bcde")202 >>> s.ratio()203 0.75204 >>> s.set_seq1("bcde")205 >>> s.ratio()206 1.0207 >>>208 209 SequenceMatcher computes and caches detailed information about the210 second sequence, so if you want to compare one sequence S against211 many sequences, use .set_seq2(S) once and call .set_seq1(x)212 repeatedly for each of the other sequences.213 214 See also set_seqs() and set_seq2().215 """216 217 if a is self.a:218 return219 self.a = a220 self.matching_blocks = self.opcodes = None221 222 def set_seq2(self, b):223 """Set the second sequence to be compared.224 225 The first sequence to be compared is not changed.226 227 >>> s = SequenceMatcher(None, "abcd", "bcde")228 >>> s.ratio()229 0.75230 >>> s.set_seq2("abcd")231 >>> s.ratio()232 1.0233 >>>234 235 SequenceMatcher computes and caches detailed information about the236 second sequence, so if you want to compare one sequence S against237 many sequences, use .set_seq2(S) once and call .set_seq1(x)238 repeatedly for each of the other sequences.239 240 See also set_seqs() and set_seq1().241 """242 243 if b is self.b:244 return245 self.b = b246 self.matching_blocks = self.opcodes = None247 self.fullbcount = None248 self.__chain_b()249 250 # For each element x in b, set b2j[x] to a list of the indices in251 # b where x appears; the indices are in increasing order; note that252 # the number of times x appears in b is len(b2j[x]) ...253 # when self.isjunk is defined, junk elements don't show up in this254 # map at all, which stops the central find_longest_match method255 # from starting any matching block at a junk element ...256 # b2j also does not contain entries for "popular" elements, meaning257 # elements that account for more than 1 + 1% of the total elements, and258 # when the sequence is reasonably large (>= 200 elements); this can259 # be viewed as an adaptive notion of semi-junk, and yields an enormous260 # speedup when, e.g., comparing program files with hundreds of261 # instances of "return NULL;" ...262 # note that this is only called when b changes; so for cross-product263 # kinds of matches, it's best to call set_seq2 once, then set_seq1264 # repeatedly265 266 def __chain_b(self):267 # Because isjunk is a user-defined (not C) function, and we test268 # for junk a LOT, it's important to minimize the number of calls.269 # Before the tricks described here, __chain_b was by far the most270 # time-consuming routine in the whole module! If anyone sees271 # Jim Roskind, thank him again for profile.py -- I never would272 # have guessed that.273 # The first trick is to build b2j ignoring the possibility274 # of junk. I.e., we don't call isjunk at all yet. Throwing275 # out the junk later is much cheaper than building b2j "right"276 # from the start.277 b = self.b278 self.b2j = b2j = {}279 280 for i, elt in enumerate(b):281 indices = b2j.setdefault(elt, [])282 indices.append(i)283 284 # Purge junk elements285 self.bjunk = junk = set()286 isjunk = self.isjunk287 if isjunk:288 for elt in b2j.keys():289 if isjunk(elt):290 junk.add(elt)291 for elt in junk: # separate loop avoids separate list of keys292 del b2j[elt]293 294 # Purge popular elements that are not junk295 self.bpopular = popular = set()296 n = len(b)297 if self.autojunk and n >= 200:298 ntest = n // 100 + 1299 for elt, idxs in b2j.items():300 if len(idxs) > ntest:301 popular.add(elt)302 for elt in popular: # ditto; as fast for 1% deletion303 del b2j[elt]304 305 def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):306 """Find longest matching block in a[alo:ahi] and b[blo:bhi].307 308 By default it will find the longest match in the entirety of a and b.309 310 If isjunk is not defined:311 312 Return (i,j,k) such that a[i:i+k] is equal to b[j:j+k], where313 alo <= i <= i+k <= ahi314 blo <= j <= j+k <= bhi315 and for all (i',j',k') meeting those conditions,316 k >= k'317 i <= i'318 and if i == i', j <= j'319 320 In other words, of all maximal matching blocks, return one that321 starts earliest in a, and of all those maximal matching blocks that322 start earliest in a, return the one that starts earliest in b.323 324 >>> s = SequenceMatcher(None, " abcd", "abcd abcd")325 >>> s.find_longest_match(0, 5, 0, 9)326 Match(a=0, b=4, size=5)327 328 If isjunk is defined, first the longest matching block is329 determined as above, but with the additional restriction that no330 junk element appears in the block. Then that block is extended as331 far as possible by matching (only) junk elements on both sides. So332 the resulting block never matches on junk except as identical junk333 happens to be adjacent to an "interesting" match.334 335 Here's the same example as before, but considering blanks to be336 junk. That prevents " abcd" from matching the " abcd" at the tail337 end of the second sequence directly. Instead only the "abcd" can338 match, and matches the leftmost "abcd" in the second sequence:339 340 >>> s = SequenceMatcher(lambda x: x==" ", " abcd", "abcd abcd")341 >>> s.find_longest_match(0, 5, 0, 9)342 Match(a=1, b=0, size=4)343 344 If no blocks match, return (alo, blo, 0).345 346 >>> s = SequenceMatcher(None, "ab", "c")347 >>> s.find_longest_match(0, 2, 0, 1)348 Match(a=0, b=0, size=0)349 """350 351 # CAUTION: stripping common prefix or suffix would be incorrect.352 # E.g.,353 # ab354 # acab355 # Longest matching block is "ab", but if common prefix is356 # stripped, it's "a" (tied with "b"). UNIX(tm) diff does so357 # strip, so ends up claiming that ab is changed to acab by358 # inserting "ca" in the middle. That's minimal but unintuitive:359 # "it's obvious" that someone inserted "ac" at the front.360 # Windiff ends up at the same place as diff, but by pairing up361 # the unique 'b's and then matching the first two 'a's.362 363 a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__364 if ahi is None:365 ahi = len(a)366 if bhi is None:367 bhi = len(b)368 besti, bestj, bestsize = alo, blo, 0369 # find longest junk-free match370 # during an iteration of the loop, j2len[j] = length of longest371 # junk-free match ending with a[i-1] and b[j]372 j2len = {}373 nothing = []374 for i in range(alo, ahi):375 # look at all instances of a[i] in b; note that because376 # b2j has no junk keys, the loop is skipped if a[i] is junk377 j2lenget = j2len.get378 newj2len = {}379 for j in b2j.get(a[i], nothing):380 # a[i] matches b[j]381 if j < blo:382 continue383 if j >= bhi:384 break385 k = newj2len[j] = j2lenget(j-1, 0) + 1386 if k > bestsize:387 besti, bestj, bestsize = i-k+1, j-k+1, k388 j2len = newj2len389 390 # Extend the best by non-junk elements on each end. In particular,391 # "popular" non-junk elements aren't in b2j, which greatly speeds392 # the inner loop above, but also means "the best" match so far393 # doesn't contain any junk *or* popular non-junk elements.394 while besti > alo and bestj > blo and \395 not isbjunk(b[bestj-1]) and \396 a[besti-1] == b[bestj-1]:397 besti, bestj, bestsize = besti-1, bestj-1, bestsize+1398 while besti+bestsize < ahi and bestj+bestsize < bhi and \399 not isbjunk(b[bestj+bestsize]) and \400 a[besti+bestsize] == b[bestj+bestsize]:401 bestsize += 1402 403 # Now that we have a wholly interesting match (albeit possibly404 # empty!), we may as well suck up the matching junk on each405 # side of it too. Can't think of a good reason not to, and it406 # saves post-processing the (possibly considerable) expense of407 # figuring out what to do with it. In the case of an empty408 # interesting match, this is clearly the right thing to do,409 # because no other kind of match is possible in the regions.410 while besti > alo and bestj > blo and \411 isbjunk(b[bestj-1]) and \412 a[besti-1] == b[bestj-1]:413 besti, bestj, bestsize = besti-1, bestj-1, bestsize+1414 while besti+bestsize < ahi and bestj+bestsize < bhi and \415 isbjunk(b[bestj+bestsize]) and \416 a[besti+bestsize] == b[bestj+bestsize]:417 bestsize = bestsize + 1418 419 return Match(besti, bestj, bestsize)420 421 def get_matching_blocks(self):422 """Return list of triples describing matching subsequences.423 424 Each triple is of the form (i, j, n), and means that425 a[i:i+n] == b[j:j+n]. The triples are monotonically increasing in426 i and in j. New in Python 2.5, it's also guaranteed that if427 (i, j, n) and (i', j', n') are adjacent triples in the list, and428 the second is not the last triple in the list, then i+n != i' or429 j+n != j'. IOW, adjacent triples never describe adjacent equal430 blocks.431 432 The last triple is a dummy, (len(a), len(b), 0), and is the only433 triple with n==0.434 435 >>> s = SequenceMatcher(None, "abxcd", "abcd")436 >>> list(s.get_matching_blocks())437 [Match(a=0, b=0, size=2), Match(a=3, b=2, size=2), Match(a=5, b=4, size=0)]438 """439 440 if self.matching_blocks is not None:441 return self.matching_blocks442 la, lb = len(self.a), len(self.b)443 444 # This is most naturally expressed as a recursive algorithm, but445 # at least one user bumped into extreme use cases that exceeded446 # the recursion limit on their box. So, now we maintain a list447 # ('queue`) of blocks we still need to look at, and append partial448 # results to `matching_blocks` in a loop; the matches are sorted449 # at the end.450 queue = [(0, la, 0, lb)]451 matching_blocks = []452 while queue:453 alo, ahi, blo, bhi = queue.pop()454 i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)455 # a[alo:i] vs b[blo:j] unknown456 # a[i:i+k] same as b[j:j+k]457 # a[i+k:ahi] vs b[j+k:bhi] unknown458 if k: # if k is 0, there was no matching block459 matching_blocks.append(x)460 if alo < i and blo < j:461 queue.append((alo, i, blo, j))462 if i+k < ahi and j+k < bhi:463 queue.append((i+k, ahi, j+k, bhi))464 matching_blocks.sort()465 466 # It's possible that we have adjacent equal blocks in the467 # matching_blocks list now. Starting with 2.5, this code was added468 # to collapse them.469 i1 = j1 = k1 = 0470 non_adjacent = []471 for i2, j2, k2 in matching_blocks:472 # Is this block adjacent to i1, j1, k1?473 if i1 + k1 == i2 and j1 + k1 == j2:474 # Yes, so collapse them -- this just increases the length of475 # the first block by the length of the second, and the first476 # block so lengthened remains the block to compare against.477 k1 += k2478 else:479 # Not adjacent. Remember the first block (k1==0 means it's480 # the dummy we started with), and make the second block the481 # new block to compare against.482 if k1:483 non_adjacent.append((i1, j1, k1))484 i1, j1, k1 = i2, j2, k2485 if k1:486 non_adjacent.append((i1, j1, k1))487 488 non_adjacent.append( (la, lb, 0) )489 self.matching_blocks = list(map(Match._make, non_adjacent))490 return self.matching_blocks491 492 def get_opcodes(self):493 """Return list of 5-tuples describing how to turn a into b.494 495 Each tuple is of the form (tag, i1, i2, j1, j2). The first tuple496 has i1 == j1 == 0, and remaining tuples have i1 == the i2 from the497 tuple preceding it, and likewise for j1 == the previous j2.498 499 The tags are strings, with these meanings:500 501 'replace': a[i1:i2] should be replaced by b[j1:j2]502 'delete': a[i1:i2] should be deleted.503 Note that j1==j2 in this case.504 'insert': b[j1:j2] should be inserted at a[i1:i1].505 Note that i1==i2 in this case.506 'equal': a[i1:i2] == b[j1:j2]507 508 >>> a = "qabxcd"509 >>> b = "abycdf"510 >>> s = SequenceMatcher(None, a, b)511 >>> for tag, i1, i2, j1, j2 in s.get_opcodes():512 ... print(("%7s a[%d:%d] (%s) b[%d:%d] (%s)" %513 ... (tag, i1, i2, a[i1:i2], j1, j2, b[j1:j2])))514 delete a[0:1] (q) b[0:0] ()515 equal a[1:3] (ab) b[0:2] (ab)516 replace a[3:4] (x) b[2:3] (y)517 equal a[4:6] (cd) b[3:5] (cd)518 insert a[6:6] () b[5:6] (f)519 """520 521 if self.opcodes is not None:522 return self.opcodes523 i = j = 0524 self.opcodes = answer = []525 for ai, bj, size in self.get_matching_blocks():526 # invariant: we've pumped out correct diffs to change527 # a[:i] into b[:j], and the next matching block is528 # a[ai:ai+size] == b[bj:bj+size]. So we need to pump529 # out a diff to change a[i:ai] into b[j:bj], pump out530 # the matching block, and move (i,j) beyond the match531 tag = ''532 if i < ai and j < bj:533 tag = 'replace'534 elif i < ai:535 tag = 'delete'536 elif j < bj:537 tag = 'insert'538 if tag:539 answer.append( (tag, i, ai, j, bj) )540 i, j = ai+size, bj+size541 # the list of matching blocks is terminated by a542 # sentinel with size 0543 if size:544 answer.append( ('equal', ai, i, bj, j) )545 return answer546 547 def get_grouped_opcodes(self, n=3):548 """ Isolate change clusters by eliminating ranges with no changes.549 550 Return a generator of groups with up to n lines of context.551 Each group is in the same format as returned by get_opcodes().552 553 >>> from pprint import pprint554 >>> a = list(map(str, range(1,40)))555 >>> b = a[:]556 >>> b[8:8] = ['i'] # Make an insertion557 >>> b[20] += 'x' # Make a replacement558 >>> b[23:28] = [] # Make a deletion559 >>> b[30] += 'y' # Make another replacement560 >>> pprint(list(SequenceMatcher(None,a,b).get_grouped_opcodes()))561 [[('equal', 5, 8, 5, 8), ('insert', 8, 8, 8, 9), ('equal', 8, 11, 9, 12)],562 [('equal', 16, 19, 17, 20),563 ('replace', 19, 20, 20, 21),564 ('equal', 20, 22, 21, 23),565 ('delete', 22, 27, 23, 23),566 ('equal', 27, 30, 23, 26)],567 [('equal', 31, 34, 27, 30),568 ('replace', 34, 35, 30, 31),569 ('equal', 35, 38, 31, 34)]]570 """571 572 codes = self.get_opcodes()573 if not codes:574 codes = [("equal", 0, 1, 0, 1)]575 # Fixup leading and trailing groups if they show no changes.576 if codes[0][0] == 'equal':577 tag, i1, i2, j1, j2 = codes[0]578 codes[0] = tag, max(i1, i2-n), i2, max(j1, j2-n), j2579 if codes[-1][0] == 'equal':580 tag, i1, i2, j1, j2 = codes[-1]581 codes[-1] = tag, i1, min(i2, i1+n), j1, min(j2, j1+n)582 583 nn = n + n584 group = []585 for tag, i1, i2, j1, j2 in codes:586 # End the current group and start a new one whenever587 # there is a large range with no changes.588 if tag == 'equal' and i2-i1 > nn:589 group.append((tag, i1, min(i2, i1+n), j1, min(j2, j1+n)))590 yield group591 group = []592 i1, j1 = max(i1, i2-n), max(j1, j2-n)593 group.append((tag, i1, i2, j1 ,j2))594 if group and not (len(group)==1 and group[0][0] == 'equal'):595 yield group596 597 def ratio(self):598 """Return a measure of the sequences' similarity (float in [0,1]).599 600 Where T is the total number of elements in both sequences, and601 M is the number of matches, this is 2.0*M / T.602 Note that this is 1 if the sequences are identical, and 0 if603 they have nothing in common.604 605 .ratio() is expensive to compute if you haven't already computed606 .get_matching_blocks() or .get_opcodes(), in which case you may607 want to try .quick_ratio() or .real_quick_ratio() first to get an608 upper bound.609 610 >>> s = SequenceMatcher(None, "abcd", "bcde")611 >>> s.ratio()612 0.75613 >>> s.quick_ratio()614 0.75615 >>> s.real_quick_ratio()616 1.0617 """618 619 matches = sum(triple[-1] for triple in self.get_matching_blocks())620 return _calculate_ratio(matches, len(self.a) + len(self.b))621 622 def quick_ratio(self):623 """Return an upper bound on ratio() relatively quickly.624 625 This isn't defined beyond that it is an upper bound on .ratio(), and626 is faster to compute.627 """628 629 # viewing a and b as multisets, set matches to the cardinality630 # of their intersection; this counts the number of matches631 # without regard to order, so is clearly an upper bound632 if self.fullbcount is None:633 self.fullbcount = fullbcount = {}634 for elt in self.b:635 fullbcount[elt] = fullbcount.get(elt, 0) + 1636 fullbcount = self.fullbcount637 # avail[x] is the number of times x appears in 'b' less the638 # number of times we've seen it in 'a' so far ... kinda639 avail = {}640 availhas, matches = avail.__contains__, 0641 for elt in self.a:642 if availhas(elt):643 numb = avail[elt]644 else:645 numb = fullbcount.get(elt, 0)646 avail[elt] = numb - 1647 if numb > 0:648 matches = matches + 1649 return _calculate_ratio(matches, len(self.a) + len(self.b))650 651 def real_quick_ratio(self):652 """Return an upper bound on ratio() very quickly.653 654 This isn't defined beyond that it is an upper bound on .ratio(), and655 is faster to compute than either .ratio() or .quick_ratio().656 """657 658 la, lb = len(self.a), len(self.b)659 # can't have more matches than the number of elements in the660 # shorter sequence661 return _calculate_ratio(min(la, lb), la + lb)662 663 __class_getitem__ = classmethod(GenericAlias)664 665 666def get_close_matches(word, possibilities, n=3, cutoff=0.6):667 """Use SequenceMatcher to return list of the best "good enough" matches.668 669 word is a sequence for which close matches are desired (typically a670 string).671 672 possibilities is a list of sequences against which to match word673 (typically a list of strings).674 675 Optional arg n (default 3) is the maximum number of close matches to676 return. n must be > 0.677 678 Optional arg cutoff (default 0.6) is a float in [0, 1]. Possibilities679 that don't score at least that similar to word are ignored.680 681 The best (no more than n) matches among the possibilities are returned682 in a list, sorted by similarity score, most similar first.683 684 >>> get_close_matches("appel", ["ape", "apple", "peach", "puppy"])685 ['apple', 'ape']686 >>> import keyword as _keyword687 >>> get_close_matches("wheel", _keyword.kwlist)688 ['while']689 >>> get_close_matches("Apple", _keyword.kwlist)690 []691 >>> get_close_matches("accept", _keyword.kwlist)692 ['except']693 """694 695 if not n > 0:696 raise ValueError("n must be > 0: %r" % (n,))697 if not 0.0 <= cutoff <= 1.0:698 raise ValueError("cutoff must be in [0.0, 1.0]: %r" % (cutoff,))699 result = []700 s = SequenceMatcher()701 s.set_seq2(word)702 for x in possibilities:703 s.set_seq1(x)704 if s.real_quick_ratio() >= cutoff and \705 s.quick_ratio() >= cutoff and \706 s.ratio() >= cutoff:707 result.append((s.ratio(), x))708 709 # Move the best scorers to head of list710 result = _nlargest(n, result)711 # Strip scores for the best n matches712 return [x for score, x in result]713 714 715def _keep_original_ws(s, tag_s):716 """Replace whitespace with the original whitespace characters in `s`"""717 return ''.join(718 c if tag_c == " " and c.isspace() else tag_c719 for c, tag_c in zip(s, tag_s)720 )721 722 723 724class Differ:725 r"""726 Differ is a class for comparing sequences of lines of text, and727 producing human-readable differences or deltas. Differ uses728 SequenceMatcher both to compare sequences of lines, and to compare729 sequences of characters within similar (near-matching) lines.730 731 Each line of a Differ delta begins with a two-letter code:732 733 '- ' line unique to sequence 1734 '+ ' line unique to sequence 2735 ' ' line common to both sequences736 '? ' line not present in either input sequence737 738 Lines beginning with '? ' attempt to guide the eye to intraline739 differences, and were not present in either input sequence. These lines740 can be confusing if the sequences contain tab characters.741 742 Note that Differ makes no claim to produce a *minimal* diff. To the743 contrary, minimal diffs are often counter-intuitive, because they synch744 up anywhere possible, sometimes accidental matches 100 pages apart.745 Restricting synch points to contiguous matches preserves some notion of746 locality, at the occasional cost of producing a longer diff.747 748 Example: Comparing two texts.749 750 First we set up the texts, sequences of individual single-line strings751 ending with newlines (such sequences can also be obtained from the752 `readlines()` method of file-like objects):753 754 >>> text1 = ''' 1. Beautiful is better than ugly.755 ... 2. Explicit is better than implicit.756 ... 3. Simple is better than complex.757 ... 4. Complex is better than complicated.758 ... '''.splitlines(keepends=True)759 >>> len(text1)760 4761 >>> text1[0][-1]762 '\n'763 >>> text2 = ''' 1. Beautiful is better than ugly.764 ... 3. Simple is better than complex.765 ... 4. Complicated is better than complex.766 ... 5. Flat is better than nested.767 ... '''.splitlines(keepends=True)768 769 Next we instantiate a Differ object:770 771 >>> d = Differ()772 773 Note that when instantiating a Differ object we may pass functions to774 filter out line and character 'junk'. See Differ.__init__ for details.775 776 Finally, we compare the two:777 778 >>> result = list(d.compare(text1, text2))779 780 'result' is a list of strings, so let's pretty-print it:781 782 >>> from pprint import pprint as _pprint783 >>> _pprint(result)784 [' 1. Beautiful is better than ugly.\n',785 '- 2. Explicit is better than implicit.\n',786 '- 3. Simple is better than complex.\n',787 '+ 3. Simple is better than complex.\n',788 '? ++\n',789 '- 4. Complex is better than complicated.\n',790 '? ^ ---- ^\n',791 '+ 4. Complicated is better than complex.\n',792 '? ++++ ^ ^\n',793 '+ 5. Flat is better than nested.\n']794 795 As a single multi-line string it looks like this:796 797 >>> print(''.join(result), end="")798 1. Beautiful is better than ugly.799 - 2. Explicit is better than implicit.800 - 3. Simple is better than complex.801 + 3. Simple is better than complex.802 ? ++803 - 4. Complex is better than complicated.804 ? ^ ---- ^805 + 4. Complicated is better than complex.806 ? ++++ ^ ^807 + 5. Flat is better than nested.808 """809 810 def __init__(self, linejunk=None, charjunk=None):811 """812 Construct a text differencer, with optional filters.813 814 The two optional keyword parameters are for filter functions:815 816 - `linejunk`: A function that should accept a single string argument,817 and return true iff the string is junk. The module-level function818 `IS_LINE_JUNK` may be used to filter out lines without visible819 characters, except for at most one splat ('#'). It is recommended820 to leave linejunk None; the underlying SequenceMatcher class has821 an adaptive notion of "noise" lines that's better than any static822 definition the author has ever been able to craft.823 824 - `charjunk`: A function that should accept a string of length 1. The825 module-level function `IS_CHARACTER_JUNK` may be used to filter out826 whitespace characters (a blank or tab; **note**: bad idea to include827 newline in this!). Use of IS_CHARACTER_JUNK is recommended.828 """829 830 self.linejunk = linejunk831 self.charjunk = charjunk832 833 def compare(self, a, b):834 r"""835 Compare two sequences of lines; generate the resulting delta.836 837 Each sequence must contain individual single-line strings ending with838 newlines. Such sequences can be obtained from the `readlines()` method839 of file-like objects. The delta generated also consists of newline-840 terminated strings, ready to be printed as-is via the writelines()841 method of a file-like object.842 843 Example:844 845 >>> print(''.join(Differ().compare('one\ntwo\nthree\n'.splitlines(True),846 ... 'ore\ntree\nemu\n'.splitlines(True))),847 ... end="")848 - one849 ? ^850 + ore851 ? ^852 - two853 - three854 ? -855 + tree856 + emu857 """858 859 cruncher = SequenceMatcher(self.linejunk, a, b)860 for tag, alo, ahi, blo, bhi in cruncher.get_opcodes():861 if tag == 'replace':862 g = self._fancy_replace(a, alo, ahi, b, blo, bhi)863 elif tag == 'delete':864 g = self._dump('-', a, alo, ahi)865 elif tag == 'insert':866 g = self._dump('+', b, blo, bhi)867 elif tag == 'equal':868 g = self._dump(' ', a, alo, ahi)869 else:870 raise ValueError('unknown tag %r' % (tag,))871 872 yield from g873 874 def _dump(self, tag, x, lo, hi):875 """Generate comparison results for a same-tagged range."""876 for i in range(lo, hi):877 yield '%s %s' % (tag, x[i])878 879 def _plain_replace(self, a, alo, ahi, b, blo, bhi):880 assert alo < ahi and blo < bhi881 # dump the shorter block first -- reduces the burden on short-term882 # memory if the blocks are of very different sizes883 if bhi - blo < ahi - alo:884 first = self._dump('+', b, blo, bhi)885 second = self._dump('-', a, alo, ahi)886 else:887 first = self._dump('-', a, alo, ahi)888 second = self._dump('+', b, blo, bhi)889 890 for g in first, second:891 yield from g892 893 def _fancy_replace(self, a, alo, ahi, b, blo, bhi):894 r"""895 When replacing one block of lines with another, search the blocks896 for *similar* lines; the best-matching pair (if any) is used as a897 synch point, and intraline difference marking is done on the898 similar pair. Lots of work, but often worth it.899 900 Example:901 902 >>> d = Differ()903 >>> results = d._fancy_replace(['abcDefghiJkl\n'], 0, 1,904 ... ['abcdefGhijkl\n'], 0, 1)905 >>> print(''.join(results), end="")906 - abcDefghiJkl907 ? ^ ^ ^908 + abcdefGhijkl909 ? ^ ^ ^910 """911 # Don't synch up unless the lines have a similarity score above912 # cutoff. Previously only the smallest pair was handled here,913 # and if there are many pairs with the best ratio, recursion914 # could grow very deep, and runtime cubic. See:915 # https://github.com/python/cpython/issues/119105916 #917 # Later, more pathological cases prompted removing recursion918 # entirely.919 cutoff = 0.74999920 cruncher = SequenceMatcher(self.charjunk)921 crqr = cruncher.real_quick_ratio922 cqr = cruncher.quick_ratio923 cr = cruncher.ratio924 925 WINDOW = 10926 best_i = best_j = None927 dump_i, dump_j = alo, blo # smallest indices not yet resolved928 for j in range(blo, bhi):929 cruncher.set_seq2(b[j])930 # Search the corresponding i's within WINDOW for rhe highest931 # ratio greater than `cutoff`.932 aequiv = alo + (j - blo)933 arange = range(max(aequiv - WINDOW, dump_i),934 min(aequiv + WINDOW + 1, ahi))935 if not arange: # likely exit if `a` is shorter than `b`936 break937 best_ratio = cutoff938 for i in arange:939 cruncher.set_seq1(a[i])940 # Ordering by cheapest to most expensive ratio is very941 # valuable, most often getting out early.942 if (crqr() > best_ratio943 and cqr() > best_ratio944 and cr() > best_ratio):945 best_i, best_j, best_ratio = i, j, cr()946 947 if best_i is None:948 # found nothing to synch on yet - move to next j949 continue950 951 # pump out straight replace from before this synch pair952 yield from self._fancy_helper(a, dump_i, best_i,953 b, dump_j, best_j)954 # do intraline marking on the synch pair955 aelt, belt = a[best_i], b[best_j]956 if aelt != belt:957 # pump out a '-', '?', '+', '?' quad for the synched lines958 atags = btags = ""959 cruncher.set_seqs(aelt, belt)960 for tag, ai1, ai2, bj1, bj2 in cruncher.get_opcodes():961 la, lb = ai2 - ai1, bj2 - bj1962 if tag == 'replace':963 atags += '^' * la964 btags += '^' * lb965 elif tag == 'delete':966 atags += '-' * la967 elif tag == 'insert':968 btags += '+' * lb969 elif tag == 'equal':970 atags += ' ' * la971 btags += ' ' * lb972 else:973 raise ValueError('unknown tag %r' % (tag,))974 yield from self._qformat(aelt, belt, atags, btags)975 else:976 # the synch pair is identical977 yield ' ' + aelt978 dump_i, dump_j = best_i + 1, best_j + 1979 best_i = best_j = None980 981 # pump out straight replace from after the last synch pair982 yield from self._fancy_helper(a, dump_i, ahi,983 b, dump_j, bhi)984 985 def _fancy_helper(self, a, alo, ahi, b, blo, bhi):986 g = []987 if alo < ahi:988 if blo < bhi:989 g = self._plain_replace(a, alo, ahi, b, blo, bhi)990 else:991 g = self._dump('-', a, alo, ahi)992 elif blo < bhi:993 g = self._dump('+', b, blo, bhi)994 995 yield from g996 997 def _qformat(self, aline, bline, atags, btags):998 r"""999 Format "?" output and deal with tabs.1000 1001 Example:1002 1003 >>> d = Differ()1004 >>> results = d._qformat('\tabcDefghiJkl\n', '\tabcdefGhijkl\n',1005 ... ' ^ ^ ^ ', ' ^ ^ ^ ')1006 >>> for line in results: print(repr(line))1007 ...1008 '- \tabcDefghiJkl\n'1009 '? \t ^ ^ ^\n'1010 '+ \tabcdefGhijkl\n'1011 '? \t ^ ^ ^\n'1012 """1013 atags = _keep_original_ws(aline, atags).rstrip()1014 btags = _keep_original_ws(bline, btags).rstrip()1015 1016 yield "- " + aline1017 if atags:1018 yield f"? {atags}\n"1019 1020 yield "+ " + bline1021 if btags:1022 yield f"? {btags}\n"1023 1024# With respect to junk, an earlier version of ndiff simply refused to1025# *start* a match with a junk element. The result was cases like this:1026# before: private Thread currentThread;1027# after: private volatile Thread currentThread;1028# If you consider whitespace to be junk, the longest contiguous match1029# not starting with junk is "e Thread currentThread". So ndiff reported1030# that "e volatil" was inserted between the 't' and the 'e' in "private".1031# While an accurate view, to people that's absurd. The current version1032# looks for matching blocks that are entirely junk-free, then extends the1033# longest one of those as far as possible but only with matching junk.1034# So now "currentThread" is matched, then extended to suck up the1035# preceding blank; then "private" is matched, and extended to suck up the1036# following blank; then "Thread" is matched; and finally ndiff reports1037# that "volatile " was inserted before "Thread". The only quibble1038# remaining is that perhaps it was really the case that " volatile"1039# was inserted after "private". I can live with that <wink>.1040 1041def IS_LINE_JUNK(line, pat=None):1042 r"""1043 Return True for ignorable line: if `line` is blank or contains a single '#'.1044 1045 Examples:1046 1047 >>> IS_LINE_JUNK('\n')1048 True1049 >>> IS_LINE_JUNK(' # \n')1050 True1051 >>> IS_LINE_JUNK('hello\n')1052 False1053 """1054 1055 if pat is None:1056 # Default: match '#' or the empty string1057 return line.strip() in '#'1058 # Previous versions used the undocumented parameter 'pat' as a1059 # match function. Retain this behaviour for compatibility.1060 return pat(line) is not None1061 1062def IS_CHARACTER_JUNK(ch, ws=" \t"):1063 r"""1064 Return True for ignorable character: iff `ch` is a space or tab.1065 1066 Examples:1067 1068 >>> IS_CHARACTER_JUNK(' ')1069 True1070 >>> IS_CHARACTER_JUNK('\t')1071 True1072 >>> IS_CHARACTER_JUNK('\n')1073 False1074 >>> IS_CHARACTER_JUNK('x')1075 False1076 """1077 1078 return ch in ws1079 1080 1081########################################################################1082### Unified Diff1083########################################################################1084 1085def _format_range_unified(start, stop):1086 'Convert range to the "ed" format'1087 # Per the diff spec at http://www.unix.org/single_unix_specification/1088 beginning = start + 1 # lines start numbering with one1089 length = stop - start1090 if length == 1:1091 return '{}'.format(beginning)1092 if not length:1093 beginning -= 1 # empty ranges begin at line just before the range1094 return '{},{}'.format(beginning, length)1095 1096def unified_diff(a, b, fromfile='', tofile='', fromfiledate='',1097 tofiledate='', n=3, lineterm='\n'):1098 r"""1099 Compare two sequences of lines; generate the delta as a unified diff.1100 1101 Unified diffs are a compact way of showing line changes and a few1102 lines of context. The number of context lines is set by 'n' which1103 defaults to three.1104 1105 By default, the diff control lines (those with ---, +++, or @@) are1106 created with a trailing newline. This is helpful so that inputs1107 created from file.readlines() result in diffs that are suitable for1108 file.writelines() since both the inputs and outputs have trailing1109 newlines.1110 1111 For inputs that do not have trailing newlines, set the lineterm1112 argument to "" so that the output will be uniformly newline free.1113 1114 The unidiff format normally has a header for filenames and modification1115 times. Any or all of these may be specified using strings for1116 'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'.1117 The modification times are normally expressed in the ISO 8601 format.1118 1119 Example:1120 1121 >>> for line in unified_diff('one two three four'.split(),1122 ... 'zero one tree four'.split(), 'Original', 'Current',1123 ... '2005-01-26 23:30:50', '2010-04-02 10:20:52',1124 ... lineterm=''):1125 ... print(line) # doctest: +NORMALIZE_WHITESPACE1126 --- Original 2005-01-26 23:30:501127 +++ Current 2010-04-02 10:20:521128 @@ -1,4 +1,4 @@1129 +zero1130 one1131 -two1132 -three1133 +tree1134 four1135 """1136 1137 _check_types(a, b, fromfile, tofile, fromfiledate, tofiledate, lineterm)1138 started = False1139 for group in SequenceMatcher(None,a,b).get_grouped_opcodes(n):1140 if not started:1141 started = True1142 fromdate = '\t{}'.format(fromfiledate) if fromfiledate else ''1143 todate = '\t{}'.format(tofiledate) if tofiledate else ''1144 yield '--- {}{}{}'.format(fromfile, fromdate, lineterm)1145 yield '+++ {}{}{}'.format(tofile, todate, lineterm)1146 1147 first, last = group[0], group[-1]1148 file1_range = _format_range_unified(first[1], last[2])1149 file2_range = _format_range_unified(first[3], last[4])1150 yield '@@ -{} +{} @@{}'.format(file1_range, file2_range, lineterm)1151 1152 for tag, i1, i2, j1, j2 in group:1153 if tag == 'equal':1154 for line in a[i1:i2]:1155 yield ' ' + line1156 continue1157 if tag in {'replace', 'delete'}:1158 for line in a[i1:i2]:1159 yield '-' + line1160 if tag in {'replace', 'insert'}:1161 for line in b[j1:j2]:1162 yield '+' + line1163 1164 1165########################################################################1166### Context Diff1167########################################################################1168 1169def _format_range_context(start, stop):1170 'Convert range to the "ed" format'1171 # Per the diff spec at http://www.unix.org/single_unix_specification/1172 beginning = start + 1 # lines start numbering with one1173 length = stop - start1174 if not length:1175 beginning -= 1 # empty ranges begin at line just before the range1176 if length <= 1:1177 return '{}'.format(beginning)1178 return '{},{}'.format(beginning, beginning + length - 1)1179 1180# See http://www.unix.org/single_unix_specification/1181def context_diff(a, b, fromfile='', tofile='',1182 fromfiledate='', tofiledate='', n=3, lineterm='\n'):1183 r"""1184 Compare two sequences of lines; generate the delta as a context diff.1185 1186 Context diffs are a compact way of showing line changes and a few1187 lines of context. The number of context lines is set by 'n' which1188 defaults to three.1189 1190 By default, the diff control lines (those with *** or ---) are1191 created with a trailing newline. This is helpful so that inputs1192 created from file.readlines() result in diffs that are suitable for1193 file.writelines() since both the inputs and outputs have trailing1194 newlines.1195 1196 For inputs that do not have trailing newlines, set the lineterm1197 argument to "" so that the output will be uniformly newline free.1198 1199 The context diff format normally has a header for filenames and1200 modification times. Any or all of these may be specified using