"""

def __init__(self, isjunk=None, a='', b='', autojunk=True):

"""Construct a SequenceMatcher.

# Members:

# a

# first sequence

# b

# second sequence; differences are computed as "what do

# we need to do to 'a' to change it into 'b'?"

# b2j

# for x in b, b2j[x] is a list of the indices (into b)

# at which x appears; junk and popular elements do not appear

# fullbcount

# for x in b, fullbcount[x] == the number of times x

# appears in b; only materialized if really needed (used

# only for computing quick_ratio())

# matching_blocks

# a list of (i, j, k) triples, where a[i:i+k] == b[j:j+k];

# ascending & non-overlapping in i and in j; terminated by

# a dummy (len(a), len(b), 0) sentinel

# opcodes

# a list of (tag, i1, i2, j1, j2) tuples, where tag is

# one of

# 'replace' a[i1:i2] should be replaced by b[j1:j2]

# 'delete' a[i1:i2] should be deleted

# 'insert' b[j1:j2] should be inserted

# 'equal' a[i1:i2] == b[j1:j2]

# isjunk

# a user-supplied function taking a sequence element and

# returning true iff the element is "junk" -- this has

# subtle but helpful effects on the algorithm, which I'll

# get around to writing up someday <0.9 wink>.

# DON'T USE! Only __chain_b uses this. Use "in self.bjunk".

# bjunk

# the items in b for which isjunk is True.

# bpopular

# nonjunk items in b treated as junk by the heuristic (if used).

self.isjunk = isjunk

self.a = self.b = None

self.autojunk = autojunk

self.set_seqs(a, b)

def set_seqs(self, a, b):

"""Set the two sequences to be compared.

self.set_seq1(a)

self.set_seq2(b)

def set_seq1(self, a):

"""Set the first sequence to be compared.

if a is self.a:

return

self.a = a

self.matching_blocks = self.opcodes = None

def set_seq2(self, b):

"""Set the second sequence to be compared.

if b is self.b:

return

self.b = b

self.matching_blocks = self.opcodes = None

self.fullbcount = None

self.__chain_b()

# For each element x in b, set b2j[x] to a list of the indices in

# b where x appears; the indices are in increasing order; note that

# the number of times x appears in b is len(b2j[x]) ...

# when self.isjunk is defined, junk elements don't show up in this

# map at all, which stops the central find_longest_match method

# from starting any matching block at a junk element ...

# b2j also does not contain entries for "popular" elements, meaning

# elements that account for more than 1 + 1% of the total elements, and

# when the sequence is reasonably large (>= 200 elements); this can

# be viewed as an adaptive notion of semi-junk, and yields an enormous

# speedup when, e.g., comparing program files with hundreds of

# instances of "return NULL;" ...

# note that this is only called when b changes; so for cross-product

# kinds of matches, it's best to call set_seq2 once, then set_seq1

# repeatedly

def __chain_b(self):

# Because isjunk is a user-defined (not C) function, and we test

# for junk a LOT, it's important to minimize the number of calls.

# Before the tricks described here, __chain_b was by far the most

# time-consuming routine in the whole module! If anyone sees

# Jim Roskind, thank him again for profile.py -- I never would

# have guessed that.

# The first trick is to build b2j ignoring the possibility

# of junk. I.e., we don't call isjunk at all yet. Throwing

# out the junk later is much cheaper than building b2j "right"

# from the start.

b = self.b

self.b2j = b2j = {}

for i, elt in enumerate(b):

indices = b2j.setdefault(elt, [])

indices.append(i)

# Purge junk elements

self.bjunk = junk = set()

isjunk = self.isjunk

if isjunk:

for elt in b2j.keys():

if isjunk(elt):

junk.add(elt)

for elt in junk: # separate loop avoids separate list of keys

del b2j[elt]

# Purge popular elements that are not junk

self.bpopular = popular = set()

n = len(b)

if self.autojunk and n >= 200:

ntest = n // 100 + 1

for elt, idxs in b2j.items():

if len(idxs) > ntest:

popular.add(elt)

for elt in popular: # ditto; as fast for 1% deletion

del b2j[elt]

def find_longest_match(self, alo=0, ahi=None, blo=0, bhi=None):

"""Find longest matching block in a[alo:ahi] and b[blo:bhi].

# CAUTION: stripping common prefix or suffix would be incorrect.

# E.g.,

# ab

# acab

# Longest matching block is "ab", but if common prefix is

# stripped, it's "a" (tied with "b"). UNIX(tm) diff does so

# strip, so ends up claiming that ab is changed to acab by

# inserting "ca" in the middle. That's minimal but unintuitive:

# "it's obvious" that someone inserted "ac" at the front.

# Windiff ends up at the same place as diff, but by pairing up

# the unique 'b's and then matching the first two 'a's.

a, b, b2j, isbjunk = self.a, self.b, self.b2j, self.bjunk.__contains__

if ahi is None:

ahi = len(a)

if bhi is None:

bhi = len(b)

besti, bestj, bestsize = alo, blo, 0

# find longest junk-free match

# during an iteration of the loop, j2len[j] = length of longest

# junk-free match ending with a[i-1] and b[j]

j2len = {}

nothing = []

for i in range(alo, ahi):

# look at all instances of a[i] in b; note that because

# b2j has no junk keys, the loop is skipped if a[i] is junk

j2lenget = j2len.get

newj2len = {}

for j in b2j.get(a[i], nothing):

# a[i] matches b[j]

if j < blo:

continue

if j >= bhi:

break

k = newj2len[j] = j2lenget(j-1, 0) + 1

if k > bestsize:

besti, bestj, bestsize = i-k+1, j-k+1, k

j2len = newj2len

# Extend the best by non-junk elements on each end. In particular,

# "popular" non-junk elements aren't in b2j, which greatly speeds

# the inner loop above, but also means "the best" match so far

# doesn't contain any junk *or* popular non-junk elements.

while besti > alo and bestj > blo and \

not isbjunk(b[bestj-1]) and \

a[besti-1] == b[bestj-1]:

besti, bestj, bestsize = besti-1, bestj-1, bestsize+1

while besti+bestsize < ahi and bestj+bestsize < bhi and \

not isbjunk(b[bestj+bestsize]) and \

a[besti+bestsize] == b[bestj+bestsize]:

bestsize += 1

# Now that we have a wholly interesting match (albeit possibly

# empty!), we may as well suck up the matching junk on each

# side of it too. Can't think of a good reason not to, and it

# saves post-processing the (possibly considerable) expense of

# figuring out what to do with it. In the case of an empty

# interesting match, this is clearly the right thing to do,

# because no other kind of match is possible in the regions.

while besti > alo and bestj > blo and \

isbjunk(b[bestj-1]) and \

a[besti-1] == b[bestj-1]:

besti, bestj, bestsize = besti-1, bestj-1, bestsize+1

while besti+bestsize < ahi and bestj+bestsize < bhi and \

isbjunk(b[bestj+bestsize]) and \

a[besti+bestsize] == b[bestj+bestsize]:

bestsize = bestsize + 1

return Match(besti, bestj, bestsize)

def get_matching_blocks(self):

"""Return list of triples describing matching subsequences.

if self.matching_blocks is not None:

return self.matching_blocks

la, lb = len(self.a), len(self.b)

# This is most naturally expressed as a recursive algorithm, but

# at least one user bumped into extreme use cases that exceeded

# the recursion limit on their box. So, now we maintain a list

# ('queue`) of blocks we still need to look at, and append partial

# results to `matching_blocks` in a loop; the matches are sorted

# at the end.

queue = [(0, la, 0, lb)]

matching_blocks = []

while queue:

alo, ahi, blo, bhi = queue.pop()

i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi)

# a[alo:i] vs b[blo:j] unknown

# a[i:i+k] same as b[j:j+k]

# a[i+k:ahi] vs b[j+k:bhi] unknown

if k: # if k is 0, there was no matching block

matching_blocks.append(x)

if alo < i and blo < j:

queue.append((alo, i, blo, j))

if i+k < ahi and j+k < bhi:

queue.append((i+k, ahi, j+k, bhi))

matching_blocks.sort()

# It's possible that we have adjacent equal blocks in the

# matching_blocks list now. Starting with 2.5, this code was added

# to collapse them.

i1 = j1 = k1 = 0

non_adjacent = []

for i2, j2, k2 in matching_blocks:

# Is this block adjacent to i1, j1, k1?

if i1 + k1 == i2 and j1 + k1 == j2:

# Yes, so collapse them -- this just increases the length of

# the first block by the length of the second, and the first

# block so lengthened remains the block to compare against.

k1 += k2

else:

# Not adjacent. Remember the first block (k1==0 means it's

# the dummy we started with), and make the second block the

# new block to compare against.

if k1:

non_adjacent.append((i1, j1, k1))

i1, j1, k1 = i2, j2, k2

if k1:

non_adjacent.append((i1, j1, k1))

non_adjacent.append( (la, lb, 0) )

self.matching_blocks = list(map(Match._make, non_adjacent))

return self.matching_blocks

def get_opcodes(self):

"""Return list of 5-tuples describing how to turn a into b.

if self.opcodes is not None:

return self.opcodes

i = j = 0

self.opcodes = answer = []

for ai, bj, size in self.get_matching_blocks():

# invariant: we've pumped out correct diffs to change

# a[:i] into b[:j], and the next matching block is

# a[ai:ai+size] == b[bj:bj+size]. So we need to pump

# out a diff to change a[i:ai] into b[j:bj], pump out

# the matching block, and move (i,j) beyond the match

tag = ''

if i < ai and j < bj:

tag = 'replace'

elif i < ai:

tag = 'delete'

elif j < bj:

tag = 'insert'

if tag:

answer.append( (tag, i, ai, j, bj) )

i, j = ai+size, bj+size

# the list of matching blocks is terminated by a

# sentinel with size 0

if size:

answer.append( ('equal', ai, i, bj, j) )

return answer

def get_grouped_opcodes(self, n=3):

""" Isolate change clusters by eliminating ranges with no changes.

codes = self.get_opcodes()

if not codes:

codes = [("equal", 0, 1, 0, 1)]

# Fixup leading and trailing groups if they show no changes.

if codes[0][0] == 'equal':

tag, i1, i2, j1, j2 = codes[0]

codes[0] = tag, max(i1, i2-n), i2, max(j1, j2-n), j2

if codes[-1][0] == 'equal':

tag, i1, i2, j1, j2 = codes[-1]

codes[-1] = tag, i1, min(i2, i1+n), j1, min(j2, j1+n)

nn = n + n

group = []

for tag, i1, i2, j1, j2 in codes:

# End the current group and start a new one whenever

# there is a large range with no changes.

if tag == 'equal' and i2-i1 > nn:

group.append((tag, i1, min(i2, i1+n), j1, min(j2, j1+n)))

yield group

group = []

i1, j1 = max(i1, i2-n), max(j1, j2-n)

group.append((tag, i1, i2, j1 ,j2))

if group and not (len(group)==1 and group[0][0] == 'equal'):

yield group

def ratio(self):

"""Return a measure of the sequences' similarity (float in [0,1]).

matches = sum(triple[-1] for triple in self.get_matching_blocks())

return _calculate_ratio(matches, len(self.a) + len(self.b))

def quick_ratio(self):

"""Return an upper bound on ratio() relatively quickly.

# viewing a and b as multisets, set matches to the cardinality

# of their intersection; this counts the number of matches

# without regard to order, so is clearly an upper bound

if self.fullbcount is None:

self.fullbcount = fullbcount = {}

for elt in self.b:

fullbcount[elt] = fullbcount.get(elt, 0) + 1

fullbcount = self.fullbcount

# avail[x] is the number of times x appears in 'b' less the

# number of times we've seen it in 'a' so far ... kinda

avail = {}

matches = 0

for elt in self.a:

if elt in avail:

numb = avail[elt]

else:

numb = fullbcount.get(elt, 0)

avail[elt] = numb - 1

if numb > 0:

matches += 1

return _calculate_ratio(matches, len(self.a) + len(self.b))

def real_quick_ratio(self):

"""Return an upper bound on ratio() very quickly.

la, lb = len(self.a), len(self.b)

# can't have more matches than the number of elements in the

# shorter sequence

return _calculate_ratio(min(la, lb), la + lb)

"""Use SequenceMatcher to return list of the best "good enough" matches.

if not n > 0:

raise ValueError("n must be > 0: %r" % (n,))

if not 0.0 <= cutoff <= 1.0:

raise ValueError("cutoff must be in [0.0, 1.0]: %r" % (cutoff,))

result = []

s = SequenceMatcher()

s.set_seq2(word)

for x in possibilities:

s.set_seq1(x)

if s.real_quick_ratio() < cutoff or s.quick_ratio() < cutoff:

continue

ratio = s.ratio()

if ratio >= cutoff:

result.append((ratio, x))

# Move the best scorers to head of list

result = _nlargest(n, result)

# Strip scores for the best n matches

"""Replace whitespace with the original whitespace characters in `s`"""

return ''.join(

c if tag_c == " " and c.isspace() else tag_c

for c, tag_c in zip(s, tag_s)

r"""

def __init__(self, linejunk=None, charjunk=None):

"""

self.linejunk = linejunk

self.charjunk = charjunk

def compare(self, a, b):

r"""

cruncher = SequenceMatcher(self.linejunk, a, b)

for tag, alo, ahi, blo, bhi in cruncher.get_opcodes():

if tag == 'replace':

g = self._fancy_replace(a, alo, ahi, b, blo, bhi)

elif tag == 'delete':

g = self._dump('-', a, alo, ahi)

elif tag == 'insert':

g = self._dump('+', b, blo, bhi)

elif tag == 'equal':

g = self._dump(' ', a, alo, ahi)

else:

raise ValueError('unknown tag %r' % (tag,))

yield from g

def _dump(self, tag, x, lo, hi):

"""Generate comparison results for a same-tagged range."""

for i in range(lo, hi):

yield '%s %s' % (tag, x[i])

def _plain_replace(self, a, alo, ahi, b, blo, bhi):

assert alo < ahi and blo < bhi

# dump the shorter block first -- reduces the burden on short-term

# memory if the blocks are of very different sizes

if bhi - blo < ahi - alo:

first = self._dump('+', b, blo, bhi)

second = self._dump('-', a, alo, ahi)

else:

first = self._dump('-', a, alo, ahi)

second = self._dump('+', b, blo, bhi)

for g in first, second:

yield from g

def _fancy_replace(self, a, alo, ahi, b, blo, bhi):

r"""

# Don't synch up unless the lines have a similarity score above

# cutoff. Previously only the smallest pair was handled here,

# and if there are many pairs with the best ratio, recursion

# could grow very deep, and runtime cubic. See:

# https://github.com/python/cpython/issues/119105

#

# Later, more pathological cases prompted removing recursion

# entirely.

cutoff = 0.74999

cruncher = SequenceMatcher(self.charjunk)

crqr = cruncher.real_quick_ratio

cqr = cruncher.quick_ratio

cr = cruncher.ratio

WINDOW = 10

best_i = best_j = None

dump_i, dump_j = alo, blo # smallest indices not yet resolved

for j in range(blo, bhi):

cruncher.set_seq2(b[j])

# Search the corresponding i's within WINDOW for rhe highest

# ratio greater than `cutoff`.

aequiv = alo + (j - blo)

arange = range(max(aequiv - WINDOW, dump_i),

min(aequiv + WINDOW + 1, ahi))

if not arange: # likely exit if `a` is shorter than `b`

break

best_ratio = cutoff

for i in arange:

cruncher.set_seq1(a[i])

# Ordering by cheapest to most expensive ratio is very

# valuable, most often getting out early.

if crqr() <= best_ratio or cqr() <= best_ratio:

continue

ratio = cr()

if ratio > best_ratio:

best_i, best_j, best_ratio = i, j, ratio

if best_i is None:

# found nothing to synch on yet - move to next j

continue

# pump out straight replace from before this synch pair

yield from self._fancy_helper(a, dump_i, best_i,

b, dump_j, best_j)

# do intraline marking on the synch pair

aelt, belt = a[best_i], b[best_j]

if aelt != belt:

# pump out a '-', '?', '+', '?' quad for the synched lines

atags = btags = ""

cruncher.set_seqs(aelt, belt)

for tag, ai1, ai2, bj1, bj2 in cruncher.get_opcodes():

la, lb = ai2 - ai1, bj2 - bj1

if tag == 'replace':

atags += '^' * la

btags += '^' * lb

elif tag == 'delete':

atags += '-' * la

elif tag == 'insert':

btags += '+' * lb

elif tag == 'equal':

atags += ' ' * la

btags += ' ' * lb

else:

raise ValueError('unknown tag %r' % (tag,))

yield from self._qformat(aelt, belt, atags, btags)

else:

# the synch pair is identical

yield ' ' + aelt

dump_i, dump_j = best_i + 1, best_j + 1

best_i = best_j = None

# pump out straight replace from after the last synch pair

yield from self._fancy_helper(a, dump_i, ahi,

b, dump_j, bhi)

def _fancy_helper(self, a, alo, ahi, b, blo, bhi):

g = []

if alo < ahi:

if blo < bhi:

g = self._plain_replace(a, alo, ahi, b, blo, bhi)

else:

g = self._dump('-', a, alo, ahi)