Skip to content

Instantly share code, notes, and snippets.

@jorendorff
Last active January 12, 2023 04:52
Show Gist options
  • Star 10 You must be signed in to star a gist
  • Fork 5 You must be signed in to fork a gist
  • Save jorendorff/5040491 to your computer and use it in GitHub Desktop.
Save jorendorff/5040491 to your computer and use it in GitHub Desktop.
A primitive `diff` in 50 lines of Python. Explained here: http://pynash.org/2013/02/26/diff-in-50-lines.html
""" Usage: python diff.py FILE1 FILE2
A primitive `diff` in 50 lines of Python.
Explained here: http://pynash.org/2013/02/26/diff-in-50-lines.html
"""
def longest_matching_slice(a, a0, a1, b, b0, b1):
sa, sb, n = a0, b0, 0
runs = {}
for i in range(a0, a1):
new_runs = {}
for j in range(b0, b1):
if a[i] == b[j]:
k = new_runs[j] = runs.get(j-1, 0) + 1
if k > n:
sa, sb, n = i-k+1, j-k+1, k
runs = new_runs
assert a[sa:sa+n] == b[sb:sb+n]
return sa, sb, n
def matching_slices(a, a0, a1, b, b0, b1):
sa, sb, n = longest_matching_slice(a, a0, a1, b, b0, b1)
if n == 0:
return []
return (matching_slices(a, a0, sa, b, b0, sb) +
[(sa, sb, n)] +
matching_slices(a, sa+n, a1, b, sb+n, b1))
def print_diff(a, b):
ia = ib = 0
slices = matching_slices(a, 0, len(a), b, 0, len(b))
slices.append((len(a), len(b), 0))
for sa, sb, n in slices:
for line in a[ia:sa]:
print "-" + line
for line in b[ib:sb]:
print "+" + line
for line in a[sa:sa+n]:
print " " + line
ia = sa + n
ib = sb + n
if __name__ == '__main__':
import sys
def lines(filename):
with open(filename) as f:
return [line.rstrip('\n') for line in f.readlines()]
print_diff(lines(sys.argv[1]), lines(sys.argv[2]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment