<s> """<STR_LIT>""" <EOL> __all__ = [ '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' , <EOL> '<STR_LIT>' , '<STR_LIT>' ] <EOL> import heapq <EOL> def _calculate_ratio ( matches , length ) : <EOL> if length : <EOL> return <NUM_LIT> * matches / length <EOL> return <NUM_LIT:1.0> <EOL> class SequenceMatcher : <EOL> """<STR_LIT>""" <EOL> def __init__ ( self , isjunk = None , a = '<STR_LIT>' , b = '<STR_LIT>' ) : <EOL> """<STR_LIT>""" <EOL> self . isjunk = isjunk <EOL> self . a = self . b = None <EOL> self . set_seqs ( a , b ) <EOL> def set_seqs ( self , a , b ) : <EOL> """<STR_LIT>""" <EOL> self . set_seq1 ( a ) <EOL> self . set_seq2 ( b ) <EOL> def set_seq1 ( self , a ) : <EOL> """<STR_LIT>""" <EOL> if a is self . a : <EOL> return <EOL> self . a = a <EOL> self . matching_blocks = self . opcodes = None <EOL> def set_seq2 ( self , b ) : <EOL> """<STR_LIT>""" <EOL> if b is self . b : <EOL> return <EOL> self . b = b <EOL> self . matching_blocks = self . opcodes = None <EOL> self . fullbcount = None <EOL> self . __chain_b ( ) <EOL> def __chain_b ( self ) : <EOL> b = self . b <EOL> n = len ( b ) <EOL> self . b2j = b2j = { } <EOL> populardict = { } <EOL> for i , elt in enumerate ( b ) : <EOL> if elt in b2j : <EOL> indices = b2j [ elt ] <EOL> if n >= <NUM_LIT:200> and len ( indices ) * <NUM_LIT:100> > n : <EOL> populardict [ elt ] = <NUM_LIT:1> <EOL> del indices [ : ] <EOL> else : <EOL> indices . append ( i ) <EOL> else : <EOL> b2j [ elt ] = [ i ] <EOL> for elt in populardict : <EOL> del b2j [ elt ] <EOL> isjunk = self . isjunk <EOL> junkdict = { } <EOL> if isjunk : <EOL> for d in populardict , b2j : <EOL> for elt in d . keys ( ) : <EOL> if isjunk ( elt ) : <EOL> junkdict [ elt ] = <NUM_LIT:1> <EOL> del d [ elt ] <EOL> self . isbjunk = junkdict . has_key <EOL> self . isbpopular = populardict . has_key <EOL> def find_longest_match ( self , alo , ahi , blo , bhi ) : <EOL> """<STR_LIT>""" <EOL> a , b , b2j , isbjunk = self . a , self . b , self . b2j , self . isbjunk <EOL> besti , bestj , bestsize = alo , blo , <NUM_LIT:0> <EOL> j2len = { } <EOL> nothing = [ ] <EOL> for i in xrange ( alo , ahi ) : <EOL> j2lenget = j2len . get <EOL> newj2len = { } <EOL> for j in b2j . get ( a [ i ] , nothing ) : <EOL> if j < blo : <EOL> continue <EOL> if j >= bhi : <EOL> break <EOL> k = newj2len [ j ] = j2lenget ( j - <NUM_LIT:1> , <NUM_LIT:0> ) + <NUM_LIT:1> <EOL> if k > bestsize : <EOL> besti , bestj , bestsize = i - k + <NUM_LIT:1> , j - k + <NUM_LIT:1> , k <EOL> j2len = newj2len <EOL> while besti > alo and bestj > blo and not isbjunk ( b [ bestj - <NUM_LIT:1> ] ) and a [ besti - <NUM_LIT:1> ] == b [ bestj - <NUM_LIT:1> ] : <EOL> besti , bestj , bestsize = besti - <NUM_LIT:1> , bestj - <NUM_LIT:1> , bestsize + <NUM_LIT:1> <EOL> while besti + bestsize < ahi and bestj + bestsize < bhi and not isbjunk ( b [ bestj + bestsize ] ) and a [ besti + bestsize ] == b [ bestj + bestsize ] : <EOL> bestsize += <NUM_LIT:1> <EOL> while besti > alo and bestj > blo and isbjunk ( b [ bestj - <NUM_LIT:1> ] ) and a [ besti - <NUM_LIT:1> ] == b [ bestj - <NUM_LIT:1> ] : <EOL> besti , bestj , bestsize = besti - <NUM_LIT:1> , bestj - <NUM_LIT:1> , bestsize + <NUM_LIT:1> <EOL> while besti + bestsize < ahi and bestj + bestsize < bhi and isbjunk ( b [ bestj + bestsize ] ) and a [ besti + bestsize ] == b [ bestj + bestsize ] : <EOL> bestsize = bestsize + <NUM_LIT:1> <EOL> return besti , bestj , bestsize <EOL> def get_matching_blocks ( self ) : <EOL> """<STR_LIT>""" <EOL> if self . matching_blocks is not None : <EOL> return self . matching_blocks <EOL> la , lb = len ( self . a ) , len ( self . b ) <EOL> queue = [ ( <NUM_LIT:0> , la , <NUM_LIT:0> , lb ) ] <EOL> matching_blocks = [ ] <EOL> while queue : <EOL> alo , ahi , blo , bhi = queue . pop ( ) <EOL> i , j , k = x = self . find_longest_match ( alo , ahi , blo , bhi ) <EOL> if k : <EOL> matching_blocks . append ( x ) <EOL> if alo < i and blo < j : <EOL> queue . append ( ( alo , i , blo , j ) ) <EOL> if i + k < ahi and j + k < bhi : <EOL> queue . append ( ( i + k , ahi , j + k , bhi ) ) <EOL> matching_blocks . sort ( ) <EOL> i1 = j1 = k1 = <NUM_LIT:0> <EOL> non_adjacent = [ ] <EOL> for i2 , j2 , k2 in matching_blocks : <EOL> if i1 + k1 == i2 and j1 + k1 == j2 : <EOL> k1 += k2 <EOL> else : <EOL> if k1 : <EOL> non_adjacent . append ( ( i1 , j1 , k1 ) ) <EOL> i1 , j1 , k1 = i2 , j2 , k2 <EOL> if k1 : <EOL> non_adjacent . append ( ( i1 , j1 , k1 ) ) <EOL> non_adjacent . append ( ( la , lb , <NUM_LIT:0> ) ) <EOL> self . matching_blocks = non_adjacent <EOL> return self . matching_blocks <EOL> def get_opcodes ( self ) : <EOL> """<STR_LIT>""" <EOL> if self . opcodes is not None : <EOL> return self . opcodes <EOL> i = j = <NUM_LIT:0> <EOL> self . opcodes = answer = [ ] <EOL> for ai , bj , size in self . get_matching_blocks ( ) : <EOL> tag = '<STR_LIT>' <EOL> if i < ai and j < bj : <EOL> tag = '<STR_LIT:replace>' <EOL> elif i < ai : <EOL> tag = '<STR_LIT>' <EOL> elif j < bj : <EOL> tag = '<STR_LIT>' <EOL> if tag : <EOL> answer . append ( ( tag , i , ai , j , bj ) ) <EOL> i , j = ai + size , bj + size <EOL> if size : <EOL> answer . append ( ( '<STR_LIT>' , ai , i , bj , j ) ) <EOL> return answer <EOL> def get_grouped_opcodes ( self , n = <NUM_LIT:3> ) : <EOL> """<STR_LIT>""" <EOL> codes = self . get_opcodes ( ) <EOL> if not codes : <EOL> codes = [ ( "<STR_LIT>" , <NUM_LIT:0> , <NUM_LIT:1> , <NUM_LIT:0> , <NUM_LIT:1> ) ] <EOL> if codes [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] == '<STR_LIT>' : <EOL> tag , i1 , i2 , j1 , j2 = codes [ <NUM_LIT:0> ] <EOL> codes [ <NUM_LIT:0> ] = tag , max ( i1 , i2 - n ) , i2 , max ( j1 , j2 - n ) , j2 <EOL> if codes [ - <NUM_LIT:1> ] [ <NUM_LIT:0> ] == '<STR_LIT>' : <EOL> tag , i1 , i2 , j1 , j2 = codes [ - <NUM_LIT:1> ] <EOL> codes [ - <NUM_LIT:1> ] = tag , i1 , min ( i2 , i1 + n ) , j1 , min ( j2 , j1 + n ) <EOL> nn = n + n <EOL> group = [ ] <EOL> for tag , i1 , i2 , j1 , j2 in codes : <EOL> if tag == '<STR_LIT>' and i2 - i1 > nn : <EOL> group . append ( ( tag , i1 , min ( i2 , i1 + n ) , j1 , min ( j2 , j1 + n ) ) ) <EOL> yield group <EOL> group = [ ] <EOL> i1 , j1 = max ( i1 , i2 - n ) , max ( j1 , j2 - n ) <EOL> group . append ( ( tag , i1 , i2 , j1 , j2 ) ) <EOL> if group and not ( len ( group ) == <NUM_LIT:1> and group [ <NUM_LIT:0> ] [ <NUM_LIT:0> ] == '<STR_LIT>' ) : <EOL> yield group <EOL> def ratio ( self ) : <EOL> """<STR_LIT>""" <EOL> matches = reduce ( lambda sum , triple : sum + triple [ - <NUM_LIT:1> ] , <EOL> self . get_matching_blocks ( ) , <NUM_LIT:0> ) <EOL> return _calculate_ratio ( matches , len ( self . a ) + len ( self . b ) ) <EOL> def quick_ratio ( self ) : <EOL> """<STR_LIT>""" <EOL> if self . fullbcount is None : <EOL> self . fullbcount = fullbcount = { } <EOL> for elt in self . b : <EOL> fullbcount [ elt ] = fullbcount . get ( elt , <NUM_LIT:0> ) + <NUM_LIT:1> <EOL> fullbcount = self . fullbcount <EOL> avail = { } <EOL> availhas , matches = avail . has_key , <NUM_LIT:0> <EOL> for elt in self . a : <EOL> if availhas ( elt ) : <EOL> numb = avail [ elt ] <EOL> else : <EOL> numb = fullbcount . get ( elt , <NUM_LIT:0> ) <EOL> avail [ elt ] = numb - <NUM_LIT:1> <EOL> if numb > <NUM_LIT:0> : <EOL> matches = matches + <NUM_LIT:1> <EOL> return _calculate_ratio ( matches , len ( self . a ) + len ( self . b ) ) <EOL> def real_quick_ratio ( self ) : <EOL> """<STR_LIT>""" <EOL> la , lb = len ( self . a ) , len ( self . b ) <EOL> return _calculate_ratio ( min ( la , lb ) , la + lb ) <EOL> def get_close_matches ( word , possibilities , n = <NUM_LIT:3> , cutoff = <NUM_LIT> ) : <EOL> """<STR_LIT>""" <EOL> if not n > <NUM_LIT:0> : <EOL> raise ValueError ( "<STR_LIT>" % ( n , ) ) <EOL> if not <NUM_LIT:0.0> <= cutoff <= <NUM_LIT:1.0> : <EOL> raise ValueError ( "<STR_LIT>" % ( cutoff , ) ) <EOL> result = [ ] <EOL> s = SequenceMatcher ( ) <EOL> s . set_seq2 ( word ) <EOL> for x in possibilities : <EOL> s . set_seq1 ( x ) <EOL> if s . real_quick_ratio ( ) >= cutoff and s . quick_ratio ( ) >= cutoff and s . ratio ( ) >= cutoff : <EOL> result . append ( ( s . ratio ( ) , x ) ) <EOL> result = heapq . nlargest ( n , result ) <EOL> return [ x for score , x in result ] <EOL> def _count_leading ( line , ch ) : <EOL> """<STR_LIT>""" <EOL> i , n = <NUM_LIT:0> , len ( line ) <EOL> while i < n and line [ i ] == ch : <EOL> i += <NUM_LIT:1> <EOL> return i <EOL> class Differ : <EOL> r"""<STR_LIT>""" <EOL> def __init__ ( self , linejunk = None , charjunk = None ) : <EOL> """<STR_LIT>""" <EOL> self . linejunk = linejunk <EOL> self . charjunk = charjunk <EOL> def compare ( self , a , b ) : <EOL> r"""<STR_LIT>""" <EOL> cruncher = SequenceMatcher ( self . linejunk , a , b ) <EOL> for tag , alo , ahi , blo , bhi in cruncher . get_opcodes ( ) : <EOL> if tag == '<STR_LIT:replace>' : <EOL> g = self . _fancy_replace ( a , alo , ahi , b , blo , bhi ) <EOL> elif tag == '<STR_LIT>' : <EOL> g = self . _dump ( '<STR_LIT:->' , a , alo , ahi ) <EOL> elif tag == '<STR_LIT>' : <EOL> g = self . _dump ( '<STR_LIT:+>' , b , blo , bhi ) <EOL> elif tag == '<STR_LIT>' : <EOL> g = self . _dump ( '<STR_LIT:U+0020>' , a , alo , ahi ) <EOL> else : <EOL> raise ValueError , '<STR_LIT>' % ( tag , ) <EOL> for line in g : <EOL> yield line <EOL> def _dump ( self , tag , x , lo , hi ) : <EOL> """<STR_LIT>""" <EOL> for i in xrange ( lo , hi ) : <EOL> yield '<STR_LIT>' % ( tag , x [ i ] ) <EOL> def _plain_replace ( self , a , alo , ahi , b , blo , bhi ) : <EOL> assert alo < ahi and blo < bhi <EOL> if bhi - blo < ahi - alo : <EOL> first = self . _dump ( '<STR_LIT:+>' , b , blo , bhi ) <EOL> second = self . _dump ( '<STR_LIT:->' , a , alo , ahi ) <EOL> else : <EOL> first = self . _dump ( '<STR_LIT:->' , a , alo , ahi ) <EOL> second = self . _dump ( '<STR_LIT:+>' , b , blo , bhi ) <EOL> for g in first , second : <EOL> for line in g : <EOL> yield line <EOL> def _fancy_replace ( self , a , alo , ahi , b , blo , bhi ) : <EOL> r"""<STR_LIT>""" <EOL> best_ratio , cutoff = <NUM_LIT> , <NUM_LIT> <EOL> cruncher = SequenceMatcher ( self . charjunk ) <EOL> eqi , eqj = None , None <EOL> for j in xrange ( blo , bhi ) : <EOL> bj = b [ j ] <EOL> cruncher . set_seq2 ( bj ) <EOL> for i in xrange ( alo , ahi ) : <EOL> ai = a [ i ] <EOL> if ai == bj : <EOL> if eqi is None : <EOL> eqi , eqj = i , j <EOL> continue <EOL> cruncher . set_seq1 ( ai ) <EOL> if cruncher . real_quick_ratio ( ) > best_ratio and cruncher . quick_ratio ( ) > best_ratio and cruncher . ratio ( ) > best_ratio : <EOL> best_ratio , best_i , best_j = cruncher . ratio ( ) , i , j <EOL> if best_ratio < cutoff : <EOL> if eqi is None : <EOL> for line in self . _plain_replace ( a , alo , ahi , b , blo , bhi ) : <EOL> yield line <EOL> return <EOL> best_i , best_j , best_ratio = eqi , eqj , <NUM_LIT:1.0> <EOL> else : <EOL> eqi = None <EOL> for line in self . _fancy_helper ( a , alo , best_i , b , blo , best_j ) : <EOL> yield line <EOL> aelt , belt = a [ best_i ] , b [ best_j ] <EOL> if eqi is None : <EOL> atags = btags = "<STR_LIT>" <EOL> cruncher . set_seqs ( aelt , belt ) <EOL> for tag , ai1 , ai2 , bj1 , bj2 in cruncher . get_opcodes ( ) : <EOL> la , lb = ai2 - ai1 , bj2 - bj1 <EOL> if tag == '<STR_LIT:replace>' : <EOL> atags += '<STR_LIT>' * la <EOL> btags += '<STR_LIT>' * lb <EOL> elif tag == '<STR_LIT>' : <EOL> atags += '<STR_LIT:->' * la <EOL> elif tag == '<STR_LIT>' : <EOL> btags += '<STR_LIT:+>' * lb <EOL> elif tag == '<STR_LIT>' : <EOL> atags += '<STR_LIT:U+0020>' * la <EOL> btags += '<STR_LIT:U+0020>' * lb <EOL> else : <EOL> raise ValueError , '<STR_LIT>' % ( tag , ) <EOL> for line in self . _qformat ( aelt , belt , atags , btags ) : <EOL> yield line <EOL> else : <EOL> yield '<STR_LIT:U+0020>' + aelt <EOL> for line in self . _fancy_helper ( a , best_i + <NUM_LIT:1> , ahi , b , best_j + <NUM_LIT:1> , bhi ) : <EOL> yield line <EOL> def _fancy_helper ( self , a , alo , ahi , b , blo , bhi ) : <EOL> g = [ ] <EOL> if alo < ahi : <EOL> if blo < bhi : <EOL> g = self . _fancy_replace ( a , alo , ahi , b , blo , bhi ) <EOL> else : <EOL> g = self . _dump ( '<STR_LIT:->' , a , alo , ahi ) <EOL> elif blo < bhi : <EOL> g = self . _dump ( '<STR_LIT:+>' , b , blo , bhi ) <EOL> for line in g : <EOL> yield line <EOL> def _qformat ( self , aline , bline , atags , btags ) : <EOL> r"""<STR_LIT>""" <EOL> common = min ( _count_leading ( aline , "<STR_LIT:\t>" ) , <EOL> _count_leading ( bline , "<STR_LIT:\t>" ) ) <EOL> common = min ( common , _count_leading ( atags [ : common ] , "<STR_LIT:U+0020>" ) ) <EOL> atags = atags [ common : ] . rstrip ( ) <EOL> btags = btags [ common : ] . rstrip ( ) <EOL> yield "<STR_LIT>" + aline <EOL> if atags : <EOL> yield "<STR_LIT>" % ( "<STR_LIT:\t>" * common , atags ) <EOL> yield "<STR_LIT>" + bline <EOL> if btags : <EOL> yield "<STR_LIT>" % ( "<STR_LIT:\t>" * common , btags ) <EOL> import re <EOL> def IS_LINE_JUNK ( line , pat = re . compile ( r"<STR_LIT>" ) . match ) : <EOL> r"""<STR_LIT>""" <EOL> return pat ( line ) is not None <EOL> def IS_CHARACTER_JUNK ( ch , ws = "<STR_LIT>" ) : <EOL> r"""<STR_LIT>""" <EOL> return ch in ws <EOL> def unified_diff ( a , b , fromfile = '<STR_LIT>' , tofile = '<STR_LIT>' , fromfiledate = '<STR_LIT>' , <EOL> tofiledate = '<STR_LIT>' , n = <NUM_LIT:3> , lineterm = '<STR_LIT:\n>' ) : <EOL> r"""<STR_LIT>""" <EOL> started = False <EOL> for group in SequenceMatcher ( None , a , b ) . get_grouped_opcodes ( n ) : <EOL> if not started : <EOL> yield '<STR_LIT>' % ( fromfile , fromfiledate , lineterm ) <EOL> yield '<STR_LIT>' % ( tofile , tofiledate , lineterm ) <EOL> started = True <EOL> i1 , i2 , j1 , j2 = group [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] , group [ - <NUM_LIT:1> ] [ <NUM_LIT:2> ] , group [ <NUM_LIT:0> ] [ <NUM_LIT:3> ] , group [ - <NUM_LIT:1> ] [ <NUM_LIT:4> ] <EOL> yield "<STR_LIT>" % ( i1 + <NUM_LIT:1> , i2 - i1 , j1 + <NUM_LIT:1> , j2 - j1 , lineterm ) <EOL> for tag , i1 , i2 , j1 , j2 in group : <EOL> if tag == '<STR_LIT>' : <EOL> for line in a [ i1 : i2 ] : <EOL> yield '<STR_LIT:U+0020>' + line <EOL> continue <EOL> if tag == '<STR_LIT:replace>' or tag == '<STR_LIT>' : <EOL> for line in a [ i1 : i2 ] : <EOL> yield '<STR_LIT:->' + line <EOL> if tag == '<STR_LIT:replace>' or tag == '<STR_LIT>' : <EOL> for line in b [ j1 : j2 ] : <EOL> yield '<STR_LIT:+>' + line <EOL> def context_diff ( a , b , fromfile = '<STR_LIT>' , tofile = '<STR_LIT>' , <EOL> fromfiledate = '<STR_LIT>' , tofiledate = '<STR_LIT>' , n = <NUM_LIT:3> , lineterm = '<STR_LIT:\n>' ) : <EOL> r"""<STR_LIT>""" <EOL> started = False <EOL> prefixmap = { '<STR_LIT>' : '<STR_LIT>' , '<STR_LIT>' : '<STR_LIT>' , '<STR_LIT:replace>' : '<STR_LIT>' , '<STR_LIT>' : '<STR_LIT:U+0020>' } <EOL> for group in SequenceMatcher ( None , a , b ) . get_grouped_opcodes ( n ) : <EOL> if not started : <EOL> yield '<STR_LIT>' % ( fromfile , fromfiledate , lineterm ) <EOL> yield '<STR_LIT>' % ( tofile , tofiledate , lineterm ) <EOL> started = True <EOL> yield '<STR_LIT>' % ( lineterm , ) <EOL> if group [ - <NUM_LIT:1> ] [ <NUM_LIT:2> ] - group [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] >= <NUM_LIT:2> : <EOL> yield '<STR_LIT>' % ( group [ <NUM_LIT:0> ] [ <NUM_LIT:1> ] + <NUM_LIT:1> , group [ - <NUM_LIT:1> ] [ <NUM_LIT:2> ] , lineterm ) <EOL> else : <EOL> yield '<STR_LIT>' % ( group [ - <NUM_LIT:1> ] [ <NUM_LIT:2> ] , lineterm ) <EOL> visiblechanges = [ e for e in group if e [ <NUM_LIT:0> ] in ( '<STR_LIT:replace>' , '<STR_LIT>' ) ] <EOL> if visiblechanges : <EOL> for tag , i1 , i2 , _ , _ in group : <EOL> if tag != '<STR_LIT>' : <EOL> for line in a [ i1 : i2 ] : <EOL> yield prefixmap [ tag ] + line <EOL> if group [ - <NUM_LIT:1> ] [ <NUM_LIT:4> ] - group [ <NUM_LIT:0> ] [ <NUM_LIT:3> ] >= <NUM_LIT:2> : <EOL> yield '<STR_LIT>' % ( group [ <NUM_LIT:0> ] [ <NUM_LIT:3> ] + <NUM_LIT:1> , group [ - <NUM_LIT:1> ] [ <NUM_LIT:4> ] , lineterm ) <EOL> else : <EOL> yield '<STR_LIT>' % ( group [ - <NUM_LIT:1> ] [ <NUM_LIT:4> ] , lineterm ) <EOL> visiblechanges = [ e for e in group if e [ <NUM_LIT:0> ] in ( '<STR_LIT:replace>' , '<STR_LIT>' ) ] <EOL> if visiblechanges : <EOL> for tag , _ , _ , j1 , j2 in group : <EOL> if tag != '<STR_LIT>' : <EOL> for line in b [ j1 : j2 ] : <EOL> yield prefixmap [ tag ] + line <EOL> def ndiff ( a , b , linejunk = None , charjunk = IS_CHARACTER_JUNK ) : <EOL> r"""<STR_LIT>""" <EOL> return Differ ( linejunk , charjunk ) . compare ( a , b ) <EOL> def _mdiff ( fromlines , tolines , context = None , linejunk = None , <EOL> charjunk = IS_CHARACTER_JUNK ) : <EOL> r"""<STR_LIT>""" <EOL> import re <EOL> change_re = re . compile ( '<STR_LIT>' ) <EOL> diff_lines_iterator = ndiff ( fromlines , tolines , linejunk , charjunk ) <EOL> def _make_line ( lines , format_key , side , num_lines = [ <NUM_LIT:0> , <NUM_LIT:0> ] ) : <EOL> """<STR_LIT>""" <EOL> num_lines [ side ] += <NUM_LIT:1> <EOL> if format_key is None : <EOL> return ( num_lines [ side ] , lines . pop ( <NUM_LIT:0> ) [ <NUM_LIT:2> : ] ) <EOL> if format_key == '<STR_LIT:?>' : <EOL> text , markers = lines . pop ( <NUM_LIT:0> ) , lines . pop ( <NUM_LIT:0> ) <EOL> sub_info = [ ] <EOL> def record_sub_info ( match_object , sub_info = sub_info ) : <EOL> sub_info . append ( [ match_object . group ( <NUM_LIT:1> ) [ <NUM_LIT:0> ] , match_object . span ( ) ] ) <EOL> return match_object . group ( <NUM_LIT:1> ) <EOL> change_re . sub ( record_sub_info , markers ) <EOL> for key , ( begin , end ) in sub_info [ : : - <NUM_LIT:1> ] : <EOL> text = text [ <NUM_LIT:0> : begin ] + '<STR_LIT>' + key + text [ begin : end ] + '<STR_LIT>' + text [ end : ] <EOL> text = text [ <NUM_LIT:2> : ] <EOL> else : <EOL> text = lines . pop ( <NUM_LIT:0> ) [ <NUM_LIT:2> : ] <EOL> if not text : <EOL> text = '<STR_LIT:U+0020>' <EOL> text = '<STR_LIT>' + format_key + text + '<STR_LIT>' <EOL> return ( num_lines [ side ] , text ) <EOL> def _line_iterator ( ) : <EOL> """<STR_LIT>""" <EOL> lines = [ ] <EOL> num_blanks_pending , num_blanks_to_yield = <NUM_LIT:0> , <NUM_LIT:0> <EOL> while True : <EOL> while len ( lines ) < <NUM_LIT:4> : <EOL> try : <EOL> lines . append ( diff_lines_iterator . next ( ) ) <EOL> except StopIteration : <EOL> lines . append ( '<STR_LIT:X>' ) <EOL> s = '<STR_LIT>' . join ( [ line [ <NUM_LIT:0> ] for line in lines ] ) <EOL> if s . startswith ( '<STR_LIT:X>' ) : <EOL> num_blanks_to_yield = num_blanks_pending <EOL> elif s . startswith ( '<STR_LIT>' ) : <EOL> yield _make_line ( lines , '<STR_LIT:?>' , <NUM_LIT:0> ) , _make_line ( lines , '<STR_LIT:?>' , <NUM_LIT:1> ) , True <EOL> continue <EOL> elif s . startswith ( '<STR_LIT>' ) : <EOL> num_blanks_pending -= <NUM_LIT:1> <EOL> yield _make_line ( lines , '<STR_LIT:->' , <NUM_LIT:0> ) , None , True <EOL> continue <EOL> elif s . startswith ( ( '<STR_LIT>' , '<STR_LIT>' , '<STR_LIT>' ) ) : <EOL> from_line , to_line = _make_line ( lines , '<STR_LIT:->' , <NUM_LIT:0> ) , None <EOL> num_blanks_to_yield , num_blanks_pending = num_blanks_pending - <NUM_LIT:1> , <NUM_LIT:0> <EOL> elif s . startswith ( '<STR_LIT>' ) : <EOL> yield _make_line ( lines , None , <NUM_LIT:0> ) , _make_line ( lines , '<STR_LIT:?>' , <NUM_LIT:1> ) , True <EOL> continue <EOL> elif s . startswith ( '<STR_LIT>' ) : <EOL> yield _make_line ( lines , '<STR_LIT:?>' , <NUM_LIT:0> ) , _make_line ( lines , None , <NUM_LIT:1> ) , True <EOL> continue <EOL> elif s . startswith ( '<STR_LIT:->' ) : <EOL> num_blanks_pending -= <NUM_LIT:1> <EOL> yield _make_line ( lines , '<STR_LIT:->' , <NUM_LIT:0> ) , None , True <EOL> continue <EOL> elif s . startswith ( '<STR_LIT>' ) : <EOL> num_blanks_pending += <NUM_LIT:1> <EOL> yield None , _make_line ( lines , '<STR_LIT:+>' , <NUM_LIT:1> ) , True <EOL> continue <EOL> elif s . startswith ( ( '<STR_LIT>' , '<STR_LIT>' ) ) : <EOL> from_line , to_line = None , _make_line ( lines , '<STR_LIT:+>' , <NUM_LIT:1> ) <EOL> num_blanks_to_yield , num_blanks_pending = num_blanks_pending + <NUM_LIT:1> , <NUM_LIT:0> <EOL> elif s . startswith ( '<STR_LIT:+>' ) : <EOL> num_blanks_pending += <NUM_LIT:1> <EOL> yield None , _make_line ( lines , '<STR_LIT:+>' , <NUM_LIT:1> ) , True <EOL> continue <EOL> elif s . startswith ( '<STR_LIT:U+0020>' ) : <EOL> yield _make_line ( lines [ : ] , None , <NUM_LIT:0> ) , _make_line ( lines , None , <NUM_LIT:1> ) , False <EOL> continue <EOL> while ( num_blanks_to_yield < <NUM_LIT:0> ) : <EOL> num_blanks_to_yield += <NUM_LIT:1> <EOL> yield None , ( '<STR_LIT>' , '<STR_LIT:\n>' ) , True <EOL> while ( num_blanks_to_yield > <NUM_LIT:0> ) : <EOL> num_blanks_to_yield -= <NUM_LIT:1> <EOL> yield ( '<STR_LIT>' , '<STR_LIT:\n>' ) , None , True <EOL> if s . startswith ( '<STR_LIT:X>' ) : <EOL> raise StopIteration <EOL> else : <EOL> yield from_line , to_line , True <EOL> def _line_pair_iterator ( ) : <EOL> """<STR_LIT>""" <EOL> line_iterator = _line_iterator ( ) <EOL> fromlines , tolines = [ ] , [ ] <EOL> while True : <EOL> while ( len ( fromlines ) == <NUM_LIT:0> or len ( tolines ) == <NUM_LIT:0> ) : <EOL> from_line , to_line , found_diff = line_iterator . next ( ) <EOL> if from_line is not None : <EOL> fromlines . append ( ( from_line , found_diff ) ) <EOL> if to_line is not None : <EOL> tolines . append ( ( to_line , found_diff ) ) <EOL> from_line , fromDiff = fromlines . pop ( <NUM_LIT:0> ) <EOL> to_line , to_diff = tolines . pop ( <NUM_LIT:0> ) <EOL> yield ( from_line , to_line , fromDiff or to_diff ) <EOL> line_pair_iterator = _line_pair_iterator ( ) <EOL> if context is None : <EOL> while True : <EOL> yield line_pair_iterator . next ( ) <EOL> else : <EOL> context += <NUM_LIT:1> <EOL> lines_to_write = <NUM_LIT:0> <EOL> while True : <EOL> index , contextLines = <NUM_LIT:0> , [ None ] * ( context ) <EOL> found_diff = False <EOL> while ( found_diff is False ) : <EOL> from_line , to_line , found_diff = line_pair_iterator . next ( ) <EOL> i = index % context <EOL> contextLines [ i ] = ( from_line , to_line , found_diff ) <EOL> index += <NUM_LIT:1> <EOL> if index > context : <EOL> yield None , None , None <EOL> lines_to_write = context <EOL> else : <EOL> lines_to_write = index <EOL> index = <NUM_LIT:0> <EOL> while ( lines_to_write ) : <EOL> i = index % context <EOL> index += <NUM_LIT:1> <EOL> yield contextLines [ i ] <EOL> lines_to_write -= <NUM_LIT:1> <EOL> lines_to_write = context - <NUM_LIT:1> <EOL> while ( lines_to_write ) : <EOL> from_line , to_line , found_diff = line_pair_iterator . next ( ) <EOL> if found_diff : <EOL> lines_to_write = context - <NUM_LIT:1> <EOL> else : <EOL> lines_to_write -= <NUM_LIT:1> <EOL> yield from_line , to_line , found_diff <EOL> _file_template = """<STR_LIT>""" <EOL> _styles = """<STR_LIT>""" <EOL> _table_template = """<STR_LIT>""" <EOL> _legend = """<STR_LIT>""" <EOL> class HtmlDiff ( object ) : <EOL> """<STR_LIT>""" <EOL> _file_template = _file_template <EOL> _styles = _styles <EOL> _table_template = _table_template <EOL> _legend = _legend <EOL> _default_prefix = <NUM_LIT:0> <EOL> def __init__ ( self , tabsize = <NUM_LIT:8> , wrapcolumn = None , linejunk = None , <EOL> charjunk = IS_CHARACTER_JUNK ) : <EOL> """<STR_LIT>""" <EOL> self . _tabsize = tabsize <EOL> self . _wrapcolumn = wrapcolumn <EOL> self . _linejunk = linejunk <EOL> self . _charjunk = charjunk <EOL> def make_file ( self , fromlines , tolines , fromdesc = '<STR_LIT>' , todesc = '<STR_LIT>' , context = False , <EOL> numlines = <NUM_LIT:5> ) : <EOL> """<STR_LIT>""" <EOL> return self . _file_template % dict ( <EOL> styles = self . _styles , <EOL> legend = self . _legend , <EOL> table = self . make_table ( fromlines , tolines , fromdesc , todesc , <EOL> context = context , numlines = numlines ) ) <EOL> def _tab_newline_replace ( self , fromlines , tolines ) : <EOL> """<STR_LIT>""" <EOL> def expand_tabs ( line ) : <EOL> line = line . replace ( '<STR_LIT:U+0020>' , '<STR_LIT>' ) <EOL> line = line . expandtabs ( self . _tabsize ) <EOL> line = line . replace ( '<STR_LIT:U+0020>' , '<STR_LIT:\t>' ) <EOL> return line . replace ( '<STR_LIT>' , '<STR_LIT:U+0020>' ) . rstrip ( '<STR_LIT:\n>' ) <EOL> fromlines = [ expand_tabs ( line ) for line in fromlines ] <EOL> tolines = [ expand_tabs ( line ) for line in tolines ] <EOL> return fromlines , tolines <EOL> def _split_line ( self , data_list , line_num , text ) : <EOL> """<STR_LIT>""" <EOL> if not line_num : <EOL> data_list . append ( ( line_num , text ) ) <EOL> return <EOL> size = len ( text ) <EOL> max = self . _wrapcolumn <EOL> if ( size <= max ) or ( ( size - ( text . count ( '<STR_LIT>' ) * <NUM_LIT:3> ) ) <= max ) : <EOL> data_list . append ( ( line_num , text ) ) <EOL> return <EOL> i = <NUM_LIT:0> <EOL> n = <NUM_LIT:0> <EOL> mark = '<STR_LIT>' <EOL> while n < max and i < size : <EOL> if text [ i ] == '<STR_LIT>' : <EOL> i += <NUM_LIT:1> <EOL> mark = text [ i ] <EOL> i += <NUM_LIT:1> <EOL> elif text [ i ] == '<STR_LIT>' : <EOL> i += <NUM_LIT:1> <EOL> mark = '<STR_LIT>' <EOL> else : <EOL> i += <NUM_LIT:1> <EOL> n += <NUM_LIT:1> <EOL> line1 = text [ : i ] <EOL> line2 = text [ i : ] <EOL> if mark : <EOL> line1 = line1 + '<STR_LIT>' <EOL> line2 = '<STR_LIT>' + mark + line2 <EOL> data_list . append ( ( line_num , line1 ) ) <EOL> self . _split_line ( data_list , '<STR_LIT:>>' , line2 ) <EOL> def _line_wrapper ( self , diffs ) : <EOL> """<STR_LIT>""" <EOL> for fromdata , todata , flag in diffs : <EOL> if flag is None : <EOL> yield fromdata , todata , flag <EOL> continue <EOL> ( fromline , fromtext ) , ( toline , totext ) = fromdata , todata <EOL> fromlist , tolist = [ ] , [ ] <EOL> self . _split_line ( fromlist , fromline , fromtext ) <EOL> self . _split_line ( tolist , toline , totext ) <EOL> while fromlist or tolist : <EOL> if fromlist : <EOL> fromdata = fromlist . pop ( <NUM_LIT:0> ) <EOL> else : <EOL> fromdata = ( '<STR_LIT>' , '<STR_LIT:U+0020>' ) <EOL> if tolist : <EOL> todata = tolist . pop ( <NUM_LIT:0> ) <EOL> else : <EOL> todata = ( '<STR_LIT>' , '<STR_LIT:U+0020>' ) <EOL> yield fromdata , todata , flag <EOL> def _collect_lines ( self , diffs ) : <EOL> """<STR_LIT>""" <EOL> fromlist , tolist , flaglist = [ ] , [ ] , [ ] <EOL> for fromdata , todata , flag in diffs : <EOL> try : <EOL> fromlist . append ( self . _format_line ( <NUM_LIT:0> , flag , * fromdata ) ) <EOL> tolist . append ( self . _format_line ( <NUM_LIT:1> , flag , * todata ) ) <EOL> except TypeError : <EOL> fromlist . append ( None ) <EOL> tolist . append ( None ) <EOL> flaglist . append ( flag ) <EOL> return fromlist , tolist , flaglist <EOL> def _format_line ( self , side , flag , linenum , text ) : <EOL> """<STR_LIT>""" <EOL> try : <EOL> linenum = '<STR_LIT>' % linenum <EOL> id = '<STR_LIT>' % ( self . _prefix [ side ] , linenum ) <EOL> except TypeError : <EOL> id = '<STR_LIT>' <EOL> text = text . replace ( "<STR_LIT:&>" , "<STR_LIT>" ) . replace ( "<STR_LIT:>>" , "<STR_LIT>" ) . replace ( "<STR_LIT:<>" , "<STR_LIT>" ) <EOL> text = text . replace ( '<STR_LIT:U+0020>' , '<STR_LIT>' ) . rstrip ( ) <EOL> return '<STR_LIT>' % ( id , linenum , text ) <EOL> def _make_prefix ( self ) : <EOL> """<STR_LIT>""" <EOL> fromprefix = "<STR_LIT>" % HtmlDiff . _default_prefix <EOL> toprefix = "<STR_LIT>" % HtmlDiff . _default_prefix <EOL> HtmlDiff . _default_prefix += <NUM_LIT:1> <EOL> self . _prefix = [ fromprefix , toprefix ] <EOL> def _convert_flags ( self , fromlist , tolist , flaglist , context , numlines ) : <EOL> """<STR_LIT>""" <EOL> toprefix = self . _prefix [ <NUM_LIT:1> ] <EOL> next_id = [ '<STR_LIT>' ] * len ( flaglist ) <EOL> next_href = [ '<STR_LIT>' ] * len ( flaglist ) <EOL> num_chg , in_change = <NUM_LIT:0> , False <EOL> last = <NUM_LIT:0> <EOL> for i , flag in enumerate ( flaglist ) : <EOL> if flag : <EOL> if not in_change : <EOL> in_change = True <EOL> last = i <EOL> i = max ( [ <NUM_LIT:0> , i - numlines ] ) <EOL> next_id [ i ] = '<STR_LIT>' % ( toprefix , num_chg ) <EOL> num_chg += <NUM_LIT:1> <EOL> next_href [ last ] = '<STR_LIT>' % ( <EOL> toprefix , num_chg ) <EOL> else : <EOL> in_change = False <EOL> if not flaglist : <EOL> flaglist = [ False ] <EOL> next_id = [ '<STR_LIT>' ] <EOL> next_href = [ '<STR_LIT>' ] <EOL> last = <NUM_LIT:0> <EOL> if context : <EOL> fromlist = [ '<STR_LIT>' ] <EOL> tolist = fromlist <EOL> else : <EOL> fromlist = tolist = [ '<STR_LIT>' ] <EOL> if not flaglist [ <NUM_LIT:0> ] : <EOL> next_href [ <NUM_LIT:0> ] = '<STR_LIT>' % toprefix <EOL> next_href [ last ] = '<STR_LIT>' % ( toprefix ) <EOL> return fromlist , tolist , flaglist , next_href , next_id <EOL> def make_table ( self , fromlines , tolines , fromdesc = '<STR_LIT>' , todesc = '<STR_LIT>' , context = False , <EOL> numlines = <NUM_LIT:5> ) : <EOL> """<STR_LIT>""" <EOL> self . _make_prefix ( ) <EOL> fromlines , tolines = self . _tab_newline_replace ( fromlines , tolines ) <EOL> if context : <EOL> context_lines = numlines <EOL> else : <EOL> context_lines = None <EOL> diffs = _mdiff ( fromlines , tolines , context_lines , linejunk = self . _linejunk , <EOL> charjunk = self . _charjunk ) <EOL> if self . _wrapcolumn : <EOL> diffs = self . _line_wrapper ( diffs ) <EOL> fromlist , tolist , flaglist = self . _collect_lines ( diffs ) <EOL> fromlist , tolist , flaglist , next_href , next_id = self . _convert_flags ( <EOL> fromlist , tolist , flaglist , context , numlines ) <EOL> s = [ ] <EOL> fmt = '<STR_LIT>' + '<STR_LIT>' <EOL> for i in range ( len ( flaglist ) ) : <EOL> if flaglist [ i ] is None : <EOL> if i > <NUM_LIT:0> : <EOL> s . append ( '<STR_LIT>' ) <EOL> else : <EOL> s . append ( fmt % ( next_id [ i ] , next_href [ i ] , fromlist [ i ] , <EOL> next_href [ i ] , tolist [ i ] ) ) <EOL> if fromdesc or todesc : <EOL> header_row = '<STR_LIT>' % ( <EOL> '<STR_LIT>' , <EOL> '<STR_LIT>' % fromdesc , <EOL> '<STR_LIT>' , <EOL> '<STR_LIT>' % todesc ) <EOL> else : <EOL> header_row = '<STR_LIT>' <EOL> table = self . _table_template % dict ( <EOL> data_rows = '<STR_LIT>' . join ( s ) , <EOL> header_row = header_row , <EOL> prefix = self . _prefix [ <NUM_LIT:1> ] ) <EOL> return table . replace ( '<STR_LIT>' , '<STR_LIT>' ) . replace ( '<STR_LIT>' , '<STR_LIT>' ) . replace ( '<STR_LIT>' , '<STR_LIT>' ) . replace ( '<STR_LIT>' , '<STR_LIT>' ) . replace ( '<STR_LIT:\t>' , '<STR_LIT>' ) <EOL> del re <EOL> def restore ( delta , which ) : <EOL> r"""<STR_LIT>""" <EOL> try : <EOL> tag = { <NUM_LIT:1> : "<STR_LIT>" , <NUM_LIT:2> : "<STR_LIT>" } [ int ( which ) ] <EOL> except KeyError : <EOL> raise ValueError , ( '<STR_LIT>' <EOL> % which ) <EOL> prefixes = ( "<STR_LIT:U+0020>" , tag ) <EOL> for line in delta : <EOL> if line [ : <NUM_LIT:2> ] in prefixes : <EOL> yield line [ <NUM_LIT:2> : ] <EOL> def _test ( ) : <EOL> import doctest , difflib <EOL> return doctest . testmod ( difflib ) <EOL> if __name__ == "<STR_LIT:__main__>" : <EOL> _test ( ) </s>
