code.kerkeslager.com Git - sandbox/blob - diff/diff.py

   1 import collections
   2 import functools
   3 import sys
   4
   5 def memoize(f):
   6     memo = {}
   7     sentinel = object()
   8
   9     @functools.wraps(f)
  10     def wrapped(*args):
  11         result = memo.get(args, sentinel)
  12
  13         if result is sentinel:
  14             result = f(*args)
  15             memo[args] = result
  16
  17         return result
  18
  19     return wrapped
  20
  21 @memoize
  22 def lcs(a, b, i=None, j=None):
  23     if i is None and j is None:
  24         i = len(a)
  25         j = len(b)
  26
  27     if i == 0 or j == 0:
  28         return ()
  29
  30     if a[i - 1] == b[j - 1]:
  31         return lcs(a, b, i - 1, j - 1) + (a[i - 1],)
  32
  33     x = lcs(a, b, i, j - 1)
  34     y = lcs(a, b, i - 1, j)
  35
  36     if len(x) > len(y):
  37         return x
  38     else:
  39         return y
  40
  41 def changes(a, b, c):
  42     c = lcs(a, b)
  43
  44     i, j, k = 0, 0, 0
  45
  46     while i < len(a) or j < len(b):
  47         while i < len(a) and (k == len(c) or a[i] != c[k]):
  48             yield ('d', i, a[i])
  49             i += 1
  50
  51         while j < len(b) and (k == len(c) or b[j] != c[k]):
  52             yield ('a', j, b[j])
  53             j += 1
  54
  55         while i < len(a) and j < len(b) and a[i] == b[j]:
  56             assert a[i] == c[k]
  57             assert b[j] == c[k]
  58
  59             i += 1
  60             j += 1
  61             k += 1
  62
  63 Block = collections.namedtuple(
  64     'Block',
  65     (
  66         'kind',
  67         'start',
  68         'finish',
  69         'lines',
  70     ),
  71 )
  72
  73 def compress_block(b):
  74     return Block(
  75         kind=b[0][0],
  76         start=b[0][1],
  77         finish=b[-1][1],
  78         lines=tuple(ch[2] for ch in b),
  79     )
  80
  81 def format_block(b):
  82     direction = '>' if b.kind == 'a' else '<'
  83
  84     def format_line(l):
  85         return '{} {}'.format(direction, l)
  86
  87     return '{}{},{}\n{}'.format(
  88         b.kind,
  89         b.start,
  90         b.finish,
  91         '\n'.join(format_line(l) for l in b.lines),
  92     )
  93
  94 def diff(a, b):
  95     c = lcs(a, b)
  96
  97     block = []
  98     i = 0
  99
 100     for change in changes(a, b, c):
 101         if len(block) == 0:
 102             block.append(change)
 103
 104         elif block[-1][0] == change[0] and block[-1][1] + 1 == change[1]:
 105             block.append(change)
 106
 107         else:
 108             yield compress_block(block)
 109             block = [change]
 110
 111     yield compress_block(block)
 112
 113 before_file_path = sys.argv[1]
 114 after_file_path = sys.argv[2]
 115
 116 with open(before_file_path, 'r') as before_file:
 117     before = tuple(l.rstrip() for l in before_file.readlines())
 118
 119 with open(after_file_path, 'r') as after_file:
 120     after = tuple(l.rstrip() for l in after_file.readlines())
 121
 122 for block in diff(before, after):
 123     print(format_block(block))