difflib.py (30554B)
1 #Embedded file name: C:\BuildAgent\work\20d73f1b24eed06e\eve\release\V24.01\carbon\common\stdlib\difflib.py 2 __all__ = ['get_close_matches', 3 'ndiff', 4 'restore', 5 'SequenceMatcher', 6 'Differ', 7 'IS_CHARACTER_JUNK', 8 'IS_LINE_JUNK', 9 'context_diff', 10 'unified_diff', 11 'HtmlDiff', 12 'Match'] 13 import heapq 14 from collections import namedtuple as _namedtuple 15 from functools import reduce 16 Match = _namedtuple('Match', 'a b size') 17 18 def _calculate_ratio(matches, length): 19 if length: 20 return 2.0 * matches / length 21 return 1.0 22 23 24 class SequenceMatcher(): 25 26 def __init__(self, isjunk = None, a = '', b = '', autojunk = True): 27 self.isjunk = isjunk 28 self.a = self.b = None 29 self.autojunk = autojunk 30 self.set_seqs(a, b) 31 32 def set_seqs(self, a, b): 33 self.set_seq1(a) 34 self.set_seq2(b) 35 36 def set_seq1(self, a): 37 if a is self.a: 38 return 39 self.a = a 40 self.matching_blocks = self.opcodes = None 41 42 def set_seq2(self, b): 43 if b is self.b: 44 return 45 self.b = b 46 self.matching_blocks = self.opcodes = None 47 self.fullbcount = None 48 self.__chain_b() 49 50 def __chain_b(self): 51 b = self.b 52 self.b2j = b2j = {} 53 for i, elt in enumerate(b): 54 indices = b2j.setdefault(elt, []) 55 indices.append(i) 56 57 junk = set() 58 isjunk = self.isjunk 59 if isjunk: 60 for elt in list(b2j.keys()): 61 if isjunk(elt): 62 junk.add(elt) 63 del b2j[elt] 64 65 popular = set() 66 n = len(b) 67 if self.autojunk and n >= 200: 68 ntest = n // 100 + 1 69 for elt, idxs in list(b2j.items()): 70 if len(idxs) > ntest: 71 popular.add(elt) 72 del b2j[elt] 73 74 self.isbjunk = junk.__contains__ 75 self.isbpopular = popular.__contains__ 76 77 def find_longest_match(self, alo, ahi, blo, bhi): 78 a, b, b2j, isbjunk = (self.a, 79 self.b, 80 self.b2j, 81 self.isbjunk) 82 besti, bestj, bestsize = alo, blo, 0 83 j2len = {} 84 nothing = [] 85 for i in xrange(alo, ahi): 86 j2lenget = j2len.get 87 newj2len = {} 88 for j in b2j.get(a[i], nothing): 89 if j < blo: 90 continue 91 if j >= bhi: 92 break 93 k = newj2len[j] = j2lenget(j - 1, 0) + 1 94 if k > bestsize: 95 besti, bestj, bestsize = i - k + 1, j - k + 1, k 96 97 j2len = newj2len 98 99 while besti > alo and bestj > blo and not isbjunk(b[bestj - 1]) and a[besti - 1] == b[bestj - 1]: 100 besti, bestj, bestsize = besti - 1, bestj - 1, bestsize + 1 101 102 while besti + bestsize < ahi and bestj + bestsize < bhi and not isbjunk(b[bestj + bestsize]) and a[besti + bestsize] == b[bestj + bestsize]: 103 bestsize += 1 104 105 while besti > alo and bestj > blo and isbjunk(b[bestj - 1]) and a[besti - 1] == b[bestj - 1]: 106 besti, bestj, bestsize = besti - 1, bestj - 1, bestsize + 1 107 108 while besti + bestsize < ahi and bestj + bestsize < bhi and isbjunk(b[bestj + bestsize]) and a[besti + bestsize] == b[bestj + bestsize]: 109 bestsize = bestsize + 1 110 111 return Match(besti, bestj, bestsize) 112 113 def get_matching_blocks(self): 114 if self.matching_blocks is not None: 115 return self.matching_blocks 116 la, lb = len(self.a), len(self.b) 117 queue = [(0, 118 la, 119 0, 120 lb)] 121 matching_blocks = [] 122 while queue: 123 alo, ahi, blo, bhi = queue.pop() 124 i, j, k = x = self.find_longest_match(alo, ahi, blo, bhi) 125 if k: 126 matching_blocks.append(x) 127 if alo < i and blo < j: 128 queue.append((alo, 129 i, 130 blo, 131 j)) 132 if i + k < ahi and j + k < bhi: 133 queue.append((i + k, 134 ahi, 135 j + k, 136 bhi)) 137 138 matching_blocks.sort() 139 i1 = j1 = k1 = 0 140 non_adjacent = [] 141 for i2, j2, k2 in matching_blocks: 142 if i1 + k1 == i2 and j1 + k1 == j2: 143 k1 += k2 144 else: 145 if k1: 146 non_adjacent.append((i1, j1, k1)) 147 i1, j1, k1 = i2, j2, k2 148 149 if k1: 150 non_adjacent.append((i1, j1, k1)) 151 non_adjacent.append((la, lb, 0)) 152 self.matching_blocks = non_adjacent 153 return map(Match._make, self.matching_blocks) 154 155 def get_opcodes(self): 156 if self.opcodes is not None: 157 return self.opcodes 158 i = j = 0 159 self.opcodes = answer = [] 160 for ai, bj, size in self.get_matching_blocks(): 161 tag = '' 162 if i < ai and j < bj: 163 tag = 'replace' 164 elif i < ai: 165 tag = 'delete' 166 elif j < bj: 167 tag = 'insert' 168 if tag: 169 answer.append((tag, 170 i, 171 ai, 172 j, 173 bj)) 174 i, j = ai + size, bj + size 175 if size: 176 answer.append(('equal', 177 ai, 178 i, 179 bj, 180 j)) 181 182 return answer 183 184 def get_grouped_opcodes(self, n = 3): 185 codes = self.get_opcodes() 186 if not codes: 187 codes = [('equal', 0, 1, 0, 1)] 188 if codes[0][0] == 'equal': 189 tag, i1, i2, j1, j2 = codes[0] 190 codes[0] = (tag, 191 max(i1, i2 - n), 192 i2, 193 max(j1, j2 - n), 194 j2) 195 if codes[-1][0] == 'equal': 196 tag, i1, i2, j1, j2 = codes[-1] 197 codes[-1] = (tag, 198 i1, 199 min(i2, i1 + n), 200 j1, 201 min(j2, j1 + n)) 202 nn = n + n 203 group = [] 204 for tag, i1, i2, j1, j2 in codes: 205 if tag == 'equal' and i2 - i1 > nn: 206 group.append((tag, 207 i1, 208 min(i2, i1 + n), 209 j1, 210 min(j2, j1 + n))) 211 yield group 212 group = [] 213 i1, j1 = max(i1, i2 - n), max(j1, j2 - n) 214 group.append((tag, 215 i1, 216 i2, 217 j1, 218 j2)) 219 220 if group and not (len(group) == 1 and group[0][0] == 'equal'): 221 yield group 222 223 def ratio(self): 224 matches = reduce(lambda sum, triple: sum + triple[-1], self.get_matching_blocks(), 0) 225 return _calculate_ratio(matches, len(self.a) + len(self.b)) 226 227 def quick_ratio(self): 228 if self.fullbcount is None: 229 self.fullbcount = fullbcount = {} 230 for elt in self.b: 231 fullbcount[elt] = fullbcount.get(elt, 0) + 1 232 233 fullbcount = self.fullbcount 234 avail = {} 235 availhas, matches = avail.__contains__, 0 236 for elt in self.a: 237 if availhas(elt): 238 numb = avail[elt] 239 else: 240 numb = fullbcount.get(elt, 0) 241 avail[elt] = numb - 1 242 if numb > 0: 243 matches = matches + 1 244 245 return _calculate_ratio(matches, len(self.a) + len(self.b)) 246 247 def real_quick_ratio(self): 248 la, lb = len(self.a), len(self.b) 249 return _calculate_ratio(min(la, lb), la + lb) 250 251 252 def get_close_matches(word, possibilities, n = 3, cutoff = 0.6): 253 if not n > 0: 254 raise ValueError('n must be > 0: %r' % (n,)) 255 if not 0.0 <= cutoff <= 1.0: 256 raise ValueError('cutoff must be in [0.0, 1.0]: %r' % (cutoff,)) 257 result = [] 258 s = SequenceMatcher() 259 s.set_seq2(word) 260 for x in possibilities: 261 s.set_seq1(x) 262 if s.real_quick_ratio() >= cutoff and s.quick_ratio() >= cutoff and s.ratio() >= cutoff: 263 result.append((s.ratio(), x)) 264 265 result = heapq.nlargest(n, result) 266 return [ x for score, x in result ] 267 268 269 def _count_leading(line, ch): 270 i, n = 0, len(line) 271 while i < n and line[i] == ch: 272 i += 1 273 274 return i 275 276 277 class Differ(): 278 279 def __init__(self, linejunk = None, charjunk = None): 280 self.linejunk = linejunk 281 self.charjunk = charjunk 282 283 def compare(self, a, b): 284 cruncher = SequenceMatcher(self.linejunk, a, b) 285 for tag, alo, ahi, blo, bhi in cruncher.get_opcodes(): 286 if tag == 'replace': 287 g = self._fancy_replace(a, alo, ahi, b, blo, bhi) 288 elif tag == 'delete': 289 g = self._dump('-', a, alo, ahi) 290 elif tag == 'insert': 291 g = self._dump('+', b, blo, bhi) 292 elif tag == 'equal': 293 g = self._dump(' ', a, alo, ahi) 294 else: 295 raise ValueError, 'unknown tag %r' % (tag,) 296 for line in g: 297 yield line 298 299 def _dump(self, tag, x, lo, hi): 300 for i in xrange(lo, hi): 301 yield '%s %s' % (tag, x[i]) 302 303 def _plain_replace(self, a, alo, ahi, b, blo, bhi): 304 if bhi - blo < ahi - alo: 305 first = self._dump('+', b, blo, bhi) 306 second = self._dump('-', a, alo, ahi) 307 else: 308 first = self._dump('-', a, alo, ahi) 309 second = self._dump('+', b, blo, bhi) 310 for g in (first, second): 311 for line in g: 312 yield line 313 314 def _fancy_replace(self, a, alo, ahi, b, blo, bhi): 315 best_ratio, cutoff = (0.74, 0.75) 316 cruncher = SequenceMatcher(self.charjunk) 317 eqi, eqj = (None, None) 318 for j in xrange(blo, bhi): 319 bj = b[j] 320 cruncher.set_seq2(bj) 321 for i in xrange(alo, ahi): 322 ai = a[i] 323 if ai == bj: 324 if eqi is None: 325 eqi, eqj = i, j 326 continue 327 cruncher.set_seq1(ai) 328 if cruncher.real_quick_ratio() > best_ratio and cruncher.quick_ratio() > best_ratio and cruncher.ratio() > best_ratio: 329 best_ratio, best_i, best_j = cruncher.ratio(), i, j 330 331 if best_ratio < cutoff: 332 if eqi is None: 333 for line in self._plain_replace(a, alo, ahi, b, blo, bhi): 334 yield line 335 336 return 337 best_i, best_j, best_ratio = eqi, eqj, 1.0 338 else: 339 eqi = None 340 for line in self._fancy_helper(a, alo, best_i, b, blo, best_j): 341 yield line 342 343 aelt, belt = a[best_i], b[best_j] 344 if eqi is None: 345 atags = btags = '' 346 cruncher.set_seqs(aelt, belt) 347 for tag, ai1, ai2, bj1, bj2 in cruncher.get_opcodes(): 348 la, lb = ai2 - ai1, bj2 - bj1 349 if tag == 'replace': 350 atags += '^' * la 351 btags += '^' * lb 352 elif tag == 'delete': 353 atags += '-' * la 354 elif tag == 'insert': 355 btags += '+' * lb 356 elif tag == 'equal': 357 atags += ' ' * la 358 btags += ' ' * lb 359 else: 360 raise ValueError, 'unknown tag %r' % (tag,) 361 362 for line in self._qformat(aelt, belt, atags, btags): 363 yield line 364 365 else: 366 yield ' ' + aelt 367 for line in self._fancy_helper(a, best_i + 1, ahi, b, best_j + 1, bhi): 368 yield line 369 370 def _fancy_helper(self, a, alo, ahi, b, blo, bhi): 371 g = [] 372 if alo < ahi: 373 if blo < bhi: 374 g = self._fancy_replace(a, alo, ahi, b, blo, bhi) 375 else: 376 g = self._dump('-', a, alo, ahi) 377 elif blo < bhi: 378 g = self._dump('+', b, blo, bhi) 379 for line in g: 380 yield line 381 382 def _qformat(self, aline, bline, atags, btags): 383 common = min(_count_leading(aline, '\t'), _count_leading(bline, '\t')) 384 common = min(common, _count_leading(atags[:common], ' ')) 385 common = min(common, _count_leading(btags[:common], ' ')) 386 atags = atags[common:].rstrip() 387 btags = btags[common:].rstrip() 388 yield '- ' + aline 389 if atags: 390 yield '? %s%s\n' % ('\t' * common, atags) 391 yield '+ ' + bline 392 if btags: 393 yield '? %s%s\n' % ('\t' * common, btags) 394 395 396 import re 397 398 def IS_LINE_JUNK(line, pat = re.compile('\\s*#?\\s*$').match): 399 return pat(line) is not None 400 401 402 def IS_CHARACTER_JUNK(ch, ws = ' \t'): 403 return ch in ws 404 405 406 def unified_diff(a, b, fromfile = '', tofile = '', fromfiledate = '', tofiledate = '', n = 3, lineterm = '\n'): 407 started = False 408 for group in SequenceMatcher(None, a, b).get_grouped_opcodes(n): 409 if not started: 410 fromdate = '\t%s' % fromfiledate if fromfiledate else '' 411 todate = '\t%s' % tofiledate if tofiledate else '' 412 yield '--- %s%s%s' % (fromfile, fromdate, lineterm) 413 yield '+++ %s%s%s' % (tofile, todate, lineterm) 414 started = True 415 i1, i2, j1, j2 = (group[0][1], 416 group[-1][2], 417 group[0][3], 418 group[-1][4]) 419 yield '@@ -%d,%d +%d,%d @@%s' % (i1 + 1, 420 i2 - i1, 421 j1 + 1, 422 j2 - j1, 423 lineterm) 424 for tag, i1, i2, j1, j2 in group: 425 if tag == 'equal': 426 for line in a[i1:i2]: 427 yield ' ' + line 428 429 continue 430 if tag == 'replace' or tag == 'delete': 431 for line in a[i1:i2]: 432 yield '-' + line 433 434 if tag == 'replace' or tag == 'insert': 435 for line in b[j1:j2]: 436 yield '+' + line 437 438 439 def context_diff(a, b, fromfile = '', tofile = '', fromfiledate = '', tofiledate = '', n = 3, lineterm = '\n'): 440 started = False 441 prefixmap = {'insert': '+ ', 442 'delete': '- ', 443 'replace': '! ', 444 'equal': ' '} 445 for group in SequenceMatcher(None, a, b).get_grouped_opcodes(n): 446 if not started: 447 fromdate = '\t%s' % fromfiledate if fromfiledate else '' 448 todate = '\t%s' % tofiledate if tofiledate else '' 449 yield '*** %s%s%s' % (fromfile, fromdate, lineterm) 450 yield '--- %s%s%s' % (tofile, todate, lineterm) 451 started = True 452 yield '***************%s' % (lineterm,) 453 if group[-1][2] - group[0][1] >= 2: 454 yield '*** %d,%d ****%s' % (group[0][1] + 1, group[-1][2], lineterm) 455 else: 456 yield '*** %d ****%s' % (group[-1][2], lineterm) 457 visiblechanges = [ e for e in group if e[0] in ('replace', 'delete') ] 458 if visiblechanges: 459 for tag, i1, i2, _, _ in group: 460 if tag != 'insert': 461 for line in a[i1:i2]: 462 yield prefixmap[tag] + line 463 464 if group[-1][4] - group[0][3] >= 2: 465 yield '--- %d,%d ----%s' % (group[0][3] + 1, group[-1][4], lineterm) 466 else: 467 yield '--- %d ----%s' % (group[-1][4], lineterm) 468 visiblechanges = [ e for e in group if e[0] in ('replace', 'insert') ] 469 if visiblechanges: 470 for tag, _, _, j1, j2 in group: 471 if tag != 'delete': 472 for line in b[j1:j2]: 473 yield prefixmap[tag] + line 474 475 476 def ndiff(a, b, linejunk = None, charjunk = IS_CHARACTER_JUNK): 477 return Differ(linejunk, charjunk).compare(a, b) 478 479 480 def _mdiff(fromlines, tolines, context = None, linejunk = None, charjunk = IS_CHARACTER_JUNK): 481 import re 482 change_re = re.compile('(\\++|\\-+|\\^+)') 483 diff_lines_iterator = ndiff(fromlines, tolines, linejunk, charjunk) 484 485 def _make_line(lines, format_key, side, num_lines = [0, 0]): 486 num_lines[side] += 1 487 if format_key is None: 488 return (num_lines[side], lines.pop(0)[2:]) 489 if format_key == '?': 490 text, markers = lines.pop(0), lines.pop(0) 491 sub_info = [] 492 493 def record_sub_info(match_object, sub_info = sub_info): 494 sub_info.append([match_object.group(1)[0], match_object.span()]) 495 return match_object.group(1) 496 497 change_re.sub(record_sub_info, markers) 498 for key, (begin, end) in sub_info[::-1]: 499 text = text[0:begin] + '\x00' + key + text[begin:end] + '\x01' + text[end:] 500 501 text = text[2:] 502 else: 503 text = lines.pop(0)[2:] 504 if not text: 505 text = ' ' 506 text = '\x00' + format_key + text + '\x01' 507 return (num_lines[side], text) 508 509 def _line_iterator(): 510 lines = [] 511 num_blanks_pending, num_blanks_to_yield = (0, 0) 512 while True: 513 while len(lines) < 4: 514 try: 515 lines.append(diff_lines_iterator.next()) 516 except StopIteration: 517 lines.append('X') 518 519 s = ''.join([ line[0] for line in lines ]) 520 if s.startswith('X'): 521 num_blanks_to_yield = num_blanks_pending 522 elif s.startswith('-?+?'): 523 yield (_make_line(lines, '?', 0), _make_line(lines, '?', 1), True) 524 continue 525 elif s.startswith('--++'): 526 num_blanks_pending -= 1 527 yield (_make_line(lines, '-', 0), None, True) 528 continue 529 elif s.startswith(('--?+', '--+', '- ')): 530 from_line, to_line = _make_line(lines, '-', 0), None 531 num_blanks_to_yield, num_blanks_pending = num_blanks_pending - 1, 0 532 elif s.startswith('-+?'): 533 yield (_make_line(lines, None, 0), _make_line(lines, '?', 1), True) 534 continue 535 elif s.startswith('-?+'): 536 yield (_make_line(lines, '?', 0), _make_line(lines, None, 1), True) 537 continue 538 elif s.startswith('-'): 539 num_blanks_pending -= 1 540 yield (_make_line(lines, '-', 0), None, True) 541 continue 542 elif s.startswith('+--'): 543 num_blanks_pending += 1 544 yield (None, _make_line(lines, '+', 1), True) 545 continue 546 elif s.startswith(('+ ', '+-')): 547 from_line, to_line = None, _make_line(lines, '+', 1) 548 num_blanks_to_yield, num_blanks_pending = num_blanks_pending + 1, 0 549 elif s.startswith('+'): 550 num_blanks_pending += 1 551 yield (None, _make_line(lines, '+', 1), True) 552 continue 553 elif s.startswith(' '): 554 yield (_make_line(lines[:], None, 0), _make_line(lines, None, 1), False) 555 continue 556 while num_blanks_to_yield < 0: 557 num_blanks_to_yield += 1 558 yield (None, ('', '\n'), True) 559 560 while num_blanks_to_yield > 0: 561 num_blanks_to_yield -= 1 562 yield (('', '\n'), None, True) 563 564 if s.startswith('X'): 565 raise StopIteration 566 else: 567 yield (from_line, to_line, True) 568 569 def _line_pair_iterator(): 570 line_iterator = _line_iterator() 571 fromlines, tolines = [], [] 572 while True: 573 while len(fromlines) == 0 or len(tolines) == 0: 574 from_line, to_line, found_diff = line_iterator.next() 575 if from_line is not None: 576 fromlines.append((from_line, found_diff)) 577 if to_line is not None: 578 tolines.append((to_line, found_diff)) 579 580 from_line, fromDiff = fromlines.pop(0) 581 to_line, to_diff = tolines.pop(0) 582 yield (from_line, to_line, fromDiff or to_diff) 583 584 line_pair_iterator = _line_pair_iterator() 585 if context is None: 586 while True: 587 yield line_pair_iterator.next() 588 589 else: 590 context += 1 591 lines_to_write = 0 592 while True: 593 index, contextLines = 0, [None] * context 594 found_diff = False 595 while found_diff is False: 596 from_line, to_line, found_diff = line_pair_iterator.next() 597 i = index % context 598 contextLines[i] = (from_line, to_line, found_diff) 599 index += 1 600 601 if index > context: 602 yield (None, None, None) 603 lines_to_write = context 604 else: 605 lines_to_write = index 606 index = 0 607 while lines_to_write: 608 i = index % context 609 index += 1 610 yield contextLines[i] 611 lines_to_write -= 1 612 613 lines_to_write = context - 1 614 while lines_to_write: 615 from_line, to_line, found_diff = line_pair_iterator.next() 616 if found_diff: 617 lines_to_write = context - 1 618 else: 619 lines_to_write -= 1 620 yield (from_line, to_line, found_diff) 621 622 623 _file_template = '\n<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"\n "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">\n\n<html>\n\n<head>\n <meta http-equiv="Content-Type"\n content="text/html; charset=ISO-8859-1" />\n <title></title>\n <style type="text/css">%(styles)s\n </style>\n</head>\n\n<body>\n %(table)s%(legend)s\n</body>\n\n</html>' 624 _styles = '\n table.diff {font-family:Courier; border:medium;}\n .diff_header {background-color:#e0e0e0}\n td.diff_header {text-align:right}\n .diff_next {background-color:#c0c0c0}\n .diff_add {background-color:#aaffaa}\n .diff_chg {background-color:#ffff77}\n .diff_sub {background-color:#ffaaaa}' 625 _table_template = '\n <table class="diff" id="difflib_chg_%(prefix)s_top"\n cellspacing="0" cellpadding="0" rules="groups" >\n <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>\n <colgroup></colgroup> <colgroup></colgroup> <colgroup></colgroup>\n %(header_row)s\n <tbody>\n%(data_rows)s </tbody>\n </table>' 626 _legend = '\n <table class="diff" summary="Legends">\n <tr> <th colspan="2"> Legends </th> </tr>\n <tr> <td> <table border="" summary="Colors">\n <tr><th> Colors </th> </tr>\n <tr><td class="diff_add"> Added </td></tr>\n <tr><td class="diff_chg">Changed</td> </tr>\n <tr><td class="diff_sub">Deleted</td> </tr>\n </table></td>\n <td> <table border="" summary="Links">\n <tr><th colspan="2"> Links </th> </tr>\n <tr><td>(f)irst change</td> </tr>\n <tr><td>(n)ext change</td> </tr>\n <tr><td>(t)op</td> </tr>\n </table></td> </tr>\n </table>' 627 628 class HtmlDiff(object): 629 _file_template = _file_template 630 _styles = _styles 631 _table_template = _table_template 632 _legend = _legend 633 _default_prefix = 0 634 635 def __init__(self, tabsize = 8, wrapcolumn = None, linejunk = None, charjunk = IS_CHARACTER_JUNK): 636 self._tabsize = tabsize 637 self._wrapcolumn = wrapcolumn 638 self._linejunk = linejunk 639 self._charjunk = charjunk 640 641 def make_file(self, fromlines, tolines, fromdesc = '', todesc = '', context = False, numlines = 5): 642 return self._file_template % dict(styles=self._styles, legend=self._legend, table=self.make_table(fromlines, tolines, fromdesc, todesc, context=context, numlines=numlines)) 643 644 def _tab_newline_replace(self, fromlines, tolines): 645 646 def expand_tabs(line): 647 line = line.replace(' ', '\x00') 648 line = line.expandtabs(self._tabsize) 649 line = line.replace(' ', '\t') 650 return line.replace('\x00', ' ').rstrip('\n') 651 652 fromlines = [ expand_tabs(line) for line in fromlines ] 653 tolines = [ expand_tabs(line) for line in tolines ] 654 return (fromlines, tolines) 655 656 def _split_line(self, data_list, line_num, text): 657 if not line_num: 658 data_list.append((line_num, text)) 659 return 660 size = len(text) 661 max = self._wrapcolumn 662 if size <= max or size - text.count('\x00') * 3 <= max: 663 data_list.append((line_num, text)) 664 return 665 i = 0 666 n = 0 667 mark = '' 668 while n < max and i < size: 669 if text[i] == '\x00': 670 i += 1 671 mark = text[i] 672 i += 1 673 elif text[i] == '\x01': 674 i += 1 675 mark = '' 676 else: 677 i += 1 678 n += 1 679 680 line1 = text[:i] 681 line2 = text[i:] 682 if mark: 683 line1 = line1 + '\x01' 684 line2 = '\x00' + mark + line2 685 data_list.append((line_num, line1)) 686 self._split_line(data_list, '>', line2) 687 688 def _line_wrapper(self, diffs): 689 for fromdata, todata, flag in diffs: 690 if flag is None: 691 yield (fromdata, todata, flag) 692 continue 693 (fromline, fromtext), (toline, totext) = fromdata, todata 694 fromlist, tolist = [], [] 695 self._split_line(fromlist, fromline, fromtext) 696 self._split_line(tolist, toline, totext) 697 while fromlist or tolist: 698 if fromlist: 699 fromdata = fromlist.pop(0) 700 else: 701 fromdata = ('', ' ') 702 if tolist: 703 todata = tolist.pop(0) 704 else: 705 todata = ('', ' ') 706 yield (fromdata, todata, flag) 707 708 def _collect_lines(self, diffs): 709 fromlist, tolist, flaglist = [], [], [] 710 for fromdata, todata, flag in diffs: 711 try: 712 fromlist.append(self._format_line(0, flag, *fromdata)) 713 tolist.append(self._format_line(1, flag, *todata)) 714 except TypeError: 715 fromlist.append(None) 716 tolist.append(None) 717 718 flaglist.append(flag) 719 720 return (fromlist, tolist, flaglist) 721 722 def _format_line(self, side, flag, linenum, text): 723 try: 724 linenum = '%d' % linenum 725 id = ' id="%s%s"' % (self._prefix[side], linenum) 726 except TypeError: 727 id = '' 728 729 text = text.replace('&', '&').replace('>', '>').replace('<', '<') 730 text = text.replace(' ', ' ').rstrip() 731 return '<td class="diff_header"%s>%s</td><td nowrap="nowrap">%s</td>' % (id, linenum, text) 732 733 def _make_prefix(self): 734 fromprefix = 'from%d_' % HtmlDiff._default_prefix 735 toprefix = 'to%d_' % HtmlDiff._default_prefix 736 HtmlDiff._default_prefix += 1 737 self._prefix = [fromprefix, toprefix] 738 739 def _convert_flags(self, fromlist, tolist, flaglist, context, numlines): 740 toprefix = self._prefix[1] 741 next_id = [''] * len(flaglist) 742 next_href = [''] * len(flaglist) 743 num_chg, in_change = 0, False 744 last = 0 745 for i, flag in enumerate(flaglist): 746 if flag: 747 if not in_change: 748 in_change = True 749 last = i 750 i = max([0, i - numlines]) 751 next_id[i] = ' id="difflib_chg_%s_%d"' % (toprefix, num_chg) 752 num_chg += 1 753 next_href[last] = '<a href="#difflib_chg_%s_%d">n</a>' % (toprefix, num_chg) 754 else: 755 in_change = False 756 757 if not flaglist: 758 flaglist = [False] 759 next_id = [''] 760 next_href = [''] 761 last = 0 762 if context: 763 fromlist = ['<td></td><td> No Differences Found </td>'] 764 tolist = fromlist 765 else: 766 fromlist = tolist = ['<td></td><td> Empty File </td>'] 767 if not flaglist[0]: 768 next_href[0] = '<a href="#difflib_chg_%s_0">f</a>' % toprefix 769 next_href[last] = '<a href="#difflib_chg_%s_top">t</a>' % toprefix 770 return (fromlist, 771 tolist, 772 flaglist, 773 next_href, 774 next_id) 775 776 def make_table(self, fromlines, tolines, fromdesc = '', todesc = '', context = False, numlines = 5): 777 self._make_prefix() 778 fromlines, tolines = self._tab_newline_replace(fromlines, tolines) 779 if context: 780 context_lines = numlines 781 else: 782 context_lines = None 783 diffs = _mdiff(fromlines, tolines, context_lines, linejunk=self._linejunk, charjunk=self._charjunk) 784 if self._wrapcolumn: 785 diffs = self._line_wrapper(diffs) 786 fromlist, tolist, flaglist = self._collect_lines(diffs) 787 fromlist, tolist, flaglist, next_href, next_id = self._convert_flags(fromlist, tolist, flaglist, context, numlines) 788 s = [] 789 fmt = ' <tr><td class="diff_next"%s>%s</td>%s' + '<td class="diff_next">%s</td>%s</tr>\n' 790 for i in range(len(flaglist)): 791 if flaglist[i] is None: 792 if i > 0: 793 s.append(' </tbody> \n <tbody>\n') 794 else: 795 s.append(fmt % (next_id[i], 796 next_href[i], 797 fromlist[i], 798 next_href[i], 799 tolist[i])) 800 801 if fromdesc or todesc: 802 header_row = '<thead><tr>%s%s%s%s</tr></thead>' % ('<th class="diff_next"><br /></th>', 803 '<th colspan="2" class="diff_header">%s</th>' % fromdesc, 804 '<th class="diff_next"><br /></th>', 805 '<th colspan="2" class="diff_header">%s</th>' % todesc) 806 else: 807 header_row = '' 808 table = self._table_template % dict(data_rows=''.join(s), header_row=header_row, prefix=self._prefix[1]) 809 return table.replace('\x00+', '<span class="diff_add">').replace('\x00-', '<span class="diff_sub">').replace('\x00^', '<span class="diff_chg">').replace('\x01', '</span>').replace('\t', ' ') 810 811 812 del re 813 814 def restore(delta, which): 815 try: 816 tag = {1: '- ', 817 2: '+ '}[int(which)] 818 except KeyError: 819 raise ValueError, 'unknown delta choice (must be 1 or 2): %r' % which 820 821 prefixes = (' ', tag) 822 for line in delta: 823 if line[:2] in prefixes: 824 yield line[2:] 825 826 827 def _test(): 828 import doctest, difflib 829 return doctest.testmod(difflib) 830 831 832 if __name__ == '__main__': 833 _test()