diff-colorize: diff-colorize.py annotate

annotate diff-colorize.py @ 20:b4caea436f4d

Improve the highlighting of differences using a longest common subsequence algorithm.

author	Peter Hosey <hg@boredzo.org>
date	Wed, 05 Jan 2011 16:21:37 -0800
parents	b709258a2fc2
children	929a488c4960

rev	line source
0 2df4ed64a388 Initial check-in of first working version. Peter Hosey parents: diff changeset	1 #!/usr/bin/env python
2df4ed64a388 Initial check-in of first working version. Peter Hosey parents: diff changeset	2
6 d58b4e2e12d4 Moved the imports of sys and fileinput, so that all the imports are together. Peter Hosey parents: 5 diff changeset	3 import sys
4 b8b2d1931a9e Get our color constants from the environment, if possible. Peter Hosey parents: 3 diff changeset	4 import os
6 d58b4e2e12d4 Moved the imports of sys and fileinput, so that all the imports are together. Peter Hosey parents: 5 diff changeset	5 import fileinput
4 b8b2d1931a9e Get our color constants from the environment, if possible. Peter Hosey parents: 3 diff changeset	6
15 a7214992f904 Added a different set of default color codes and a different colorization format string. Both of these are to support 16-color mode (which is all Terminal supports). Peter Hosey parents: 13 diff changeset	7 has_256_color = (os.environ.get('TERM', None) == 'xterm-256color')
a7214992f904 Added a different set of default color codes and a different colorization format string. Both of these are to support 16-color mode (which is all Terminal supports). Peter Hosey parents: 13 diff changeset	8
a7214992f904 Added a different set of default color codes and a different colorization format string. Both of these are to support 16-color mode (which is all Terminal supports). Peter Hosey parents: 13 diff changeset	9 index_color = int(os.environ.get('DIFF_INDEX_COLOR',
a7214992f904 Added a different set of default color codes and a different colorization format string. Both of these are to support 16-color mode (which is all Terminal supports). Peter Hosey parents: 13 diff changeset	10 32 if has_256_color else 36))
a7214992f904 Added a different set of default color codes and a different colorization format string. Both of these are to support 16-color mode (which is all Terminal supports). Peter Hosey parents: 13 diff changeset	11 old_mode_color = int(os.environ.get('DIFF_OLD_MODE_COLOR',
a7214992f904 Added a different set of default color codes and a different colorization format string. Both of these are to support 16-color mode (which is all Terminal supports). Peter Hosey parents: 13 diff changeset	12 88 if has_256_color else 31))
a7214992f904 Added a different set of default color codes and a different colorization format string. Both of these are to support 16-color mode (which is all Terminal supports). Peter Hosey parents: 13 diff changeset	13 new_mode_color = int(os.environ.get('DIFF_NEW_MODE_COLOR',
a7214992f904 Added a different set of default color codes and a different colorization format string. Both of these are to support 16-color mode (which is all Terminal supports). Peter Hosey parents: 13 diff changeset	14 28 if has_256_color else 32))
a7214992f904 Added a different set of default color codes and a different colorization format string. Both of these are to support 16-color mode (which is all Terminal supports). Peter Hosey parents: 13 diff changeset	15 removed_color = int(os.environ.get('DIFF_REMOVED_COLOR',
a7214992f904 Added a different set of default color codes and a different colorization format string. Both of these are to support 16-color mode (which is all Terminal supports). Peter Hosey parents: 13 diff changeset	16 160 if has_256_color else 31))
a7214992f904 Added a different set of default color codes and a different colorization format string. Both of these are to support 16-color mode (which is all Terminal supports). Peter Hosey parents: 13 diff changeset	17 added_color = int(os.environ.get('DIFF_ADDED_COLOR',
a7214992f904 Added a different set of default color codes and a different colorization format string. Both of these are to support 16-color mode (which is all Terminal supports). Peter Hosey parents: 13 diff changeset	18 2 if has_256_color else 32))
a7214992f904 Added a different set of default color codes and a different colorization format string. Both of these are to support 16-color mode (which is all Terminal supports). Peter Hosey parents: 13 diff changeset	19 hunk_start_color = int(os.environ.get('DIFF_HUNK_START_COLOR',
a7214992f904 Added a different set of default color codes and a different colorization format string. Both of these are to support 16-color mode (which is all Terminal supports). Peter Hosey parents: 13 diff changeset	20 32 if has_256_color else 36))
0 2df4ed64a388 Initial check-in of first working version. Peter Hosey parents: diff changeset	21
3 10948e4fd070 Move the color constants above the format strings, since the color constants are more editable. Peter Hosey parents: 2 diff changeset	22 RESET_FORMAT = '\033[0m'
15 a7214992f904 Added a different set of default color codes and a different colorization format string. Both of these are to support 16-color mode (which is all Terminal supports). Peter Hosey parents: 13 diff changeset	23 COLOR_FORMAT_256 = '\033[38;5;%um'
a7214992f904 Added a different set of default color codes and a different colorization format string. Both of these are to support 16-color mode (which is all Terminal supports). Peter Hosey parents: 13 diff changeset	24 COLOR_FORMAT_16 = '\033[38;%um'
a7214992f904 Added a different set of default color codes and a different colorization format string. Both of these are to support 16-color mode (which is all Terminal supports). Peter Hosey parents: 13 diff changeset	25 COLOR_FORMAT = COLOR_FORMAT_256 if has_256_color else COLOR_FORMAT_16
3 10948e4fd070 Move the color constants above the format strings, since the color constants are more editable. Peter Hosey parents: 2 diff changeset	26 BEGIN_REVERSE_FORMAT = '\033[7m'
10948e4fd070 Move the color constants above the format strings, since the color constants are more editable. Peter Hosey parents: 2 diff changeset	27 END_REVERSE_FORMAT = '\033[27m'
10948e4fd070 Move the color constants above the format strings, since the color constants are more editable. Peter Hosey parents: 2 diff changeset	28
9 cce6b860a98d Added usage information. Peter Hosey parents: 8 diff changeset	29 USAGE = """
cce6b860a98d Added usage information. Peter Hosey parents: 8 diff changeset	30 Usage: diff ... \| diff-colorize
cce6b860a98d Added usage information. Peter Hosey parents: 8 diff changeset	31 or: diff-colorize < foo.diff
cce6b860a98d Added usage information. Peter Hosey parents: 8 diff changeset	32
cce6b860a98d Added usage information. Peter Hosey parents: 8 diff changeset	33 Reads unified or git-style diff data from standard input, colorizes it, and writes the result to standard output.
cce6b860a98d Added usage information. Peter Hosey parents: 8 diff changeset	34
cce6b860a98d Added usage information. Peter Hosey parents: 8 diff changeset	35 You can customize the color numbers used by setting these variables in your environment:
cce6b860a98d Added usage information. Peter Hosey parents: 8 diff changeset	36 * DIFF_INDEX_COLOR (lines starting with "Index: " or "diff --git ")
cce6b860a98d Added usage information. Peter Hosey parents: 8 diff changeset	37 * DIFF_OLD_MODE_COLOR (lines starting with "old mode"; these only appear in git-style diffs)
cce6b860a98d Added usage information. Peter Hosey parents: 8 diff changeset	38 * DIFF_NEW_MODE_COLOR (lines starting with "new mode"; these only appear in git-style diffs)
cce6b860a98d Added usage information. Peter Hosey parents: 8 diff changeset	39 * DIFF_REMOVED_COLOR (lines starting with "-")
cce6b860a98d Added usage information. Peter Hosey parents: 8 diff changeset	40 * DIFF_ADDED_COLOR (lines starting with "+")
cce6b860a98d Added usage information. Peter Hosey parents: 8 diff changeset	41 * DIFF_HUNK_START_COLOR (lines starting with "@@")
cce6b860a98d Added usage information. Peter Hosey parents: 8 diff changeset	42 """.strip()
cce6b860a98d Added usage information. Peter Hosey parents: 8 diff changeset	43
18 83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	44 def interleave(*sequences):
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	45 "Generator that yields one object from each sequence in turn."
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	46
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	47 def zip_pad(iterables, *kw):
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	48 "Downloaded from http://code.activestate.com/recipes/497007/"
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	49 from itertools import izip, chain
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	50 if kw:
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	51 assert len(kw) == 1
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	52 pad = kw["pad"]
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	53 else:
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	54 pad = None
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	55 done = [len(iterables)-1]
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	56 def pad_iter():
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	57 if not done[0]:
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	58 return
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	59 done[0] -= 1
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	60 while 1:
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	61 yield pad
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	62 iterables = [chain(seq, pad_iter()) for seq in iterables]
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	63 return izip(*iterables)
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	64
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	65 for objects in zip_pad(*sequences):
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	66 for obj in objects:
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	67 if obj is not None:
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	68 yield obj
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	69
19 b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	70 class Substring(object):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	71 def __init__(self, a, a_start, a_stop, b, b_start, b_stop):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	72 self.a = a
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	73 self.a_start = a_start
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	74 self.a_stop = a_stop
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	75 self.b = b
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	76 self.b_start = b_start
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	77 self.b_stop = b_stop
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	78
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	79 def before_a_substring(self):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	80 return self.a[:self.a_start]
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	81 def before_b_substring(self):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	82 return self.b[:self.b_start]
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	83 def substring(self):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	84 return ''.join(self.a[self.a_start:self.a_stop])
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	85 a_substring = substring
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	86 b_substring = substring
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	87 def after_a_substring(self):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	88 return self.a[self.a_stop:]
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	89 def after_b_substring(self):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	90 return self.b[self.b_stop:]
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	91
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	92 def __hash__(self):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	93 return hash(self.substring())
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	94 def __cmp__(self, other):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	95 return cmp(self.a_start, other.a_start)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	96 def __eq__(self, other):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	97 return self.substring() == other.substring()
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	98 def __str__(self):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	99 return self.substring()
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	100 def __repr__(self):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	101 return 'Substring(%r)' % (self.substring(),)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	102 return 'Substring(%r from %r, %r, %r, %r, %r, %r)' % (
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	103 self.substring(),
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	104 self.a, self.a_start, self.a_stop,
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	105 self.b, self.b_start, self.b_stop,
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	106 )
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	107
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	108 def longest_common_substring(a, b):
20 b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	109 """Returns the longest common substring between a and b, which can be any finite indexable sliceable sequences, as a Substring object. Returns None if there is no substring between the sequences.
19 b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	110
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	111 Clarified and slightly modified (to use a special Substring object) from http://en.wikibooks.org/w/index.php?title=Algorithm_implementation/Strings/Longest_common_substring&oldid=1419225#Python
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	112 """
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	113 a_len = len(a)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	114 b_len = len(b)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	115 lengths = [[0] * (b_len + 1) for i in xrange(a_len + 1)]
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	116 substrings = set()
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	117 greatest_length = current_run_length = 0
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	118 for a_idx in xrange(a_len):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	119 for b_idx in xrange(b_len):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	120 if a[a_idx] == b[b_idx]:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	121 current_run_length = lengths[a_idx][b_idx] + 1
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	122 lengths[a_idx+1][b_idx+1] = current_run_length
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	123 if current_run_length > greatest_length:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	124 greatest_length = current_run_length
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	125 substrings.clear()
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	126 if current_run_length == greatest_length:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	127 # substrings.add(a[a_idx - current_run_length + 1:a_idx + 1])
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	128 substrings.add(Substring(a, a_idx - current_run_length + 1, a_idx + 1, b, b_idx - current_run_length + 1, b_idx + 1))
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	129 else:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	130 if current_run_length > 0:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	131 substrings.add(Substring(a, a_idx - current_run_length + 1, a_idx + 1, b, b_idx - current_run_length + 1, b_idx + 1))
20 b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	132 try:
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	133 return substrings.pop()
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	134 except KeyError:
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	135 return None
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	136
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	137 def common_subsequence(a, b):
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	138 "Returns all common substrings between a and b, which can be any finite indexable sliceable sequences, as Substring objects. Determines this by recursively calling itself on slices of a and b before and after each longest common substring."
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	139 # Inspired by http://en.wikibooks.org/w/index.php?title=Algorithm_Implementation/Strings/Longest_common_subsequence&oldid=1912924#Python
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	140 def LCS_length_matrix(a, b):
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	141 matrix = [[0] * (len(b) + 1) for i in xrange(len(a) + 1)]
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	142 for i, a_ch in enumerate(a):
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	143 for j, b_ch in enumerate(b):
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	144 if a_ch == b_ch:
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	145 matrix[i + 1][j + 1] = matrix[i][j] + 1
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	146 else:
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	147 matrix[i + 1][j + 1] = max(matrix[i + 1][j], matrix[i][j + 1])
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	148 return matrix
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	149
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	150 def recursive_build_subsequence(a, b, matrix=None, i=None, j=None):
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	151 if matrix is None:
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	152 matrix = LCS_length_matrix(a, b)
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	153 if i is None:
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	154 i = len(a)
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	155 if j is None:
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	156 j = len(b)
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	157
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	158 if i == 0 or j == 0:
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	159 return []
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	160 elif a[i - 1] == b[j - 1]:
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	161 return recursive_build_subsequence(a, b, matrix, i - 1, j - 1) + [Substring(a, i - 1, i, b, j - 1, j)]
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	162 else:
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	163 if matrix[i][j - 1] > matrix[i - 1][j]:
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	164 return recursive_build_subsequence(a, b, matrix, i, j - 1)
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	165 else:
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	166 return recursive_build_subsequence(a, b, matrix, i - 1, j)
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	167
b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	168 return recursive_build_subsequence(a, b)
19 b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	169
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	170 def common_and_distinct_substrings(a, b):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	171 "Takes two strings, a and b, tokenizes them, and returns a linked list whose nodes contain runs of either common or unique tokens."
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	172 def tokenize(a):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	173 "Each token is an identifier, a number, or a single character."
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	174 import re
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	175 # Identifier, binary number, hex number, decimal number, operator, other punctuation.
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	176 token_exp = re.compile('[_a-zA-Z][_a-zA-Z0-9]+:?\|0b[01]+\|0[xX][0-9A-Fa-f]+\|[0-9]+\|[-+*\|&^/%\[\]<=>,]\|[()\\\\;`{}]')
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	177 start = 0
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	178 for match in token_exp.finditer(a):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	179 for ch in a[start:match.start()]:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	180 yield ch
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	181 yield match.group(0)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	182 start = match.end()
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	183
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	184 remainder = a[start:]
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	185 if remainder:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	186 yield remainder
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	187
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	188 a = list(tokenize(a))
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	189 b = list(tokenize(b))
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	190
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	191 class DualPayloadLinkedListNode(object):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	192 "This linked list gives each node two next pointers."
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	193 def __init__(self, a, b, differ=None):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	194 self.a = a
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	195 self.b = b
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	196 self.next = None
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	197 if differ is None:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	198 differ = (self.a != self.b)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	199 self.differ = differ
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	200 def __iter__(self):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	201 def walk_linked_list(x):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	202 while x is not None:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	203 yield x
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	204 x = x.next
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	205 return walk_linked_list(self)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	206 def __repr__(self):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	207 return repr([('(%r, %r)' % (x.a, x.b)) if x.differ else repr(x.a) for x in self])
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	208
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	209 # Linked-list nodes for common substrings will have a single Substring object in both payloads.
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	210 # Nodes for difference runs will have a string in each payload.
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	211 empty_substring = Substring(a, 0, 0, b, 0, 0)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	212 chunks_head = DualPayloadLinkedListNode(empty_substring, empty_substring, False)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	213 # This node is used when the input strings have no common substrings. When they do have common substrings, this node will be replaced with a real node.
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	214 chunks_head.next = DualPayloadLinkedListNode(empty_substring, empty_substring, False)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	215 # Not chunks_head.next, since it will be replaced.
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	216 chunks_tail = chunks_head
20 b4caea436f4d Improve the highlighting of differences using a longest common subsequence algorithm. Peter Hosey <hg@boredzo.org> parents: 19 diff changeset	217 for sub in sorted(common_subsequence(a, b)):
19 b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	218 last_sub = chunks_tail.a
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	219 a_dif_run = ''.join(a[last_sub.a_stop:sub.a_start])
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	220 b_dif_run = ''.join(b[last_sub.b_stop:sub.b_start])
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	221 if a_dif_run or b_dif_run:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	222 chunks_tail.next = DualPayloadLinkedListNode(a_dif_run, b_dif_run, True)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	223 chunks_tail = chunks_tail.next
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	224 chunks_tail.next = DualPayloadLinkedListNode(sub, sub, False)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	225 chunks_tail = chunks_tail.next
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	226 else:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	227 # Get what comes after the last substring, if anything.
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	228 last_sub = chunks_tail.a
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	229 a_dif_run = ''.join(a[last_sub.a_stop:])
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	230 b_dif_run = ''.join(b[last_sub.b_stop:])
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	231 if a_dif_run or b_dif_run:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	232 chunks_tail.next = DualPayloadLinkedListNode(a_dif_run, b_dif_run, True)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	233
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	234 return chunks_head.next
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	235
7 c6337f653d9b Added some comments documenting the OrderedDict class and our instance's contents. Peter Hosey parents: 6 diff changeset	236 # Everything in the unified diff format is identified by a prefix. The prefixes are:
c6337f653d9b Added some comments documenting the OrderedDict class and our instance's contents. Peter Hosey parents: 6 diff changeset	237 # 'Index: ': File marker (unified diff)
c6337f653d9b Added some comments documenting the OrderedDict class and our instance's contents. Peter Hosey parents: 6 diff changeset	238 # 'diff --git': File marker (git-style diff)
c6337f653d9b Added some comments documenting the OrderedDict class and our instance's contents. Peter Hosey parents: 6 diff changeset	239 # 'old mode': File permissions mode before change
c6337f653d9b Added some comments documenting the OrderedDict class and our instance's contents. Peter Hosey parents: 6 diff changeset	240 # 'new mode': File permissions mode after change
c6337f653d9b Added some comments documenting the OrderedDict class and our instance's contents. Peter Hosey parents: 6 diff changeset	241 # '---': Defining '-' (giving the name and modification date of the file before change)
c6337f653d9b Added some comments documenting the OrderedDict class and our instance's contents. Peter Hosey parents: 6 diff changeset	242 # '+++': Defining '+' (giving the name and modification date of the file after change)
c6337f653d9b Added some comments documenting the OrderedDict class and our instance's contents. Peter Hosey parents: 6 diff changeset	243 # '-': Line before change (i.e., removed)
c6337f653d9b Added some comments documenting the OrderedDict class and our instance's contents. Peter Hosey parents: 6 diff changeset	244 # '+': Line after change (i.e., added)
c6337f653d9b Added some comments documenting the OrderedDict class and our instance's contents. Peter Hosey parents: 6 diff changeset	245 # ' ': Line that hasn't changed
c6337f653d9b Added some comments documenting the OrderedDict class and our instance's contents. Peter Hosey parents: 6 diff changeset	246 # '@@': Hunk start (@@ -start,length +start, length @@)
c6337f653d9b Added some comments documenting the OrderedDict class and our instance's contents. Peter Hosey parents: 6 diff changeset	247 #
c6337f653d9b Added some comments documenting the OrderedDict class and our instance's contents. Peter Hosey parents: 6 diff changeset	248 # We need to look for these prefixes in order, in order to handle '---'/'+++' before '-'/'+'. Hence the OrderedDict.
1 44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	249 class OrderedDict(dict):
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	250 def __init__(self, input=None):
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	251 if input is None:
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	252 self.keys = []
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	253 super(OrderedDict, self).__init__()
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	254 elif isinstance(input, dict):
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	255 self.keys = list(input)
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	256 super(OrderedDict, self).__init__(input)
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	257 else:
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	258 self.keys = [k for k, v in input]
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	259 super(OrderedDict, self).__init__(input)
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	260 def __iter__(self):
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	261 return iter(self.keys)
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	262 def __setitem__(self, k, v):
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	263 if k not in self:
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	264 self.keys.append(k)
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	265 super(OrderedDict, self).__setitem__(k, v)
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	266 def __delitem__(self, k):
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	267 super(OrderedDict, self).__delitem__(k)
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	268 self.keys.remove(k)
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	269
7 c6337f653d9b Added some comments documenting the OrderedDict class and our instance's contents. Peter Hosey parents: 6 diff changeset	270 # Each value includes not only the terminal-config characters, but also the key, somewhere within it (possibly between two terminal-config strings).
c6337f653d9b Added some comments documenting the OrderedDict class and our instance's contents. Peter Hosey parents: 6 diff changeset	271 # Theoretically, you could replace the key with some other string or leave it out entirely, if you wanted to, but I wouldn't recommend it.
1 44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	272 prefixes = OrderedDict()
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	273 prefixes['---'] = (
8 4bb2557d24cd Now that these can come from the environment, they are variables. Lowercasing their names for this reason. Peter Hosey parents: 7 diff changeset	274 COLOR_FORMAT % (removed_color,)
1 44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	275 + BEGIN_REVERSE_FORMAT
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	276 + '---'
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	277 + END_REVERSE_FORMAT
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	278 )
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	279 prefixes['+++'] = (
8 4bb2557d24cd Now that these can come from the environment, they are variables. Lowercasing their names for this reason. Peter Hosey parents: 7 diff changeset	280 COLOR_FORMAT % (added_color,)
1 44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	281 + BEGIN_REVERSE_FORMAT
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	282 + '+++'
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	283 + END_REVERSE_FORMAT
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	284 )
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	285 prefixes['-'] = (
8 4bb2557d24cd Now that these can come from the environment, they are variables. Lowercasing their names for this reason. Peter Hosey parents: 7 diff changeset	286 COLOR_FORMAT % (removed_color,)
1 44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	287 + BEGIN_REVERSE_FORMAT
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	288 + '-'
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	289 + END_REVERSE_FORMAT
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	290 )
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	291 prefixes['+'] = (
8 4bb2557d24cd Now that these can come from the environment, they are variables. Lowercasing their names for this reason. Peter Hosey parents: 7 diff changeset	292 COLOR_FORMAT % (added_color,)
1 44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	293 + BEGIN_REVERSE_FORMAT
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	294 + '+'
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	295 + END_REVERSE_FORMAT
44f86539d245 Refactored to allow me to more easily add new prefixes. Peter Hosey parents: 0 diff changeset	296 )
5 fa7cd4c2716b Added prefixes “old mode” and “new mode”, found in Git-style diffs, along with new color constants for them. We treat these the same way we treat “---” and “+++”. Peter Hosey parents: 4 diff changeset	297 prefixes['old mode'] = ( # Git-style diffs only
8 4bb2557d24cd Now that these can come from the environment, they are variables. Lowercasing their names for this reason. Peter Hosey parents: 7 diff changeset	298 COLOR_FORMAT % (old_mode_color,)
5 fa7cd4c2716b Added prefixes “old mode” and “new mode”, found in Git-style diffs, along with new color constants for them. We treat these the same way we treat “---” and “+++”. Peter Hosey parents: 4 diff changeset	299 + BEGIN_REVERSE_FORMAT
fa7cd4c2716b Added prefixes “old mode” and “new mode”, found in Git-style diffs, along with new color constants for them. We treat these the same way we treat “---” and “+++”. Peter Hosey parents: 4 diff changeset	300 + 'old mode'
fa7cd4c2716b Added prefixes “old mode” and “new mode”, found in Git-style diffs, along with new color constants for them. We treat these the same way we treat “---” and “+++”. Peter Hosey parents: 4 diff changeset	301 + END_REVERSE_FORMAT
fa7cd4c2716b Added prefixes “old mode” and “new mode”, found in Git-style diffs, along with new color constants for them. We treat these the same way we treat “---” and “+++”. Peter Hosey parents: 4 diff changeset	302 )
fa7cd4c2716b Added prefixes “old mode” and “new mode”, found in Git-style diffs, along with new color constants for them. We treat these the same way we treat “---” and “+++”. Peter Hosey parents: 4 diff changeset	303 prefixes['new mode'] = ( # Git-style diffs only
8 4bb2557d24cd Now that these can come from the environment, they are variables. Lowercasing their names for this reason. Peter Hosey parents: 7 diff changeset	304 COLOR_FORMAT % (new_mode_color,)
5 fa7cd4c2716b Added prefixes “old mode” and “new mode”, found in Git-style diffs, along with new color constants for them. We treat these the same way we treat “---” and “+++”. Peter Hosey parents: 4 diff changeset	305 + BEGIN_REVERSE_FORMAT
fa7cd4c2716b Added prefixes “old mode” and “new mode”, found in Git-style diffs, along with new color constants for them. We treat these the same way we treat “---” and “+++”. Peter Hosey parents: 4 diff changeset	306 + 'new mode'
fa7cd4c2716b Added prefixes “old mode” and “new mode”, found in Git-style diffs, along with new color constants for them. We treat these the same way we treat “---” and “+++”. Peter Hosey parents: 4 diff changeset	307 + END_REVERSE_FORMAT
fa7cd4c2716b Added prefixes “old mode” and “new mode”, found in Git-style diffs, along with new color constants for them. We treat these the same way we treat “---” and “+++”. Peter Hosey parents: 4 diff changeset	308 )
8 4bb2557d24cd Now that these can come from the environment, they are variables. Lowercasing their names for this reason. Peter Hosey parents: 7 diff changeset	309 prefixes['Index: '] = COLOR_FORMAT % (index_color,) + 'Index: '
4bb2557d24cd Now that these can come from the environment, they are variables. Lowercasing their names for this reason. Peter Hosey parents: 7 diff changeset	310 prefixes['diff --git '] = COLOR_FORMAT % (index_color,) + 'diff --git '
2 9eda9139d627 Added support for hunk start markers (@@…@@). For these, we set the whole line in reverse video, in the same color we use for index lines. Peter Hosey parents: 1 diff changeset	311 prefixes['@@'] = (
8 4bb2557d24cd Now that these can come from the environment, they are variables. Lowercasing their names for this reason. Peter Hosey parents: 7 diff changeset	312 COLOR_FORMAT % (hunk_start_color,)
2 9eda9139d627 Added support for hunk start markers (@@…@@). For these, we set the whole line in reverse video, in the same color we use for index lines. Peter Hosey parents: 1 diff changeset	313 + BEGIN_REVERSE_FORMAT
9eda9139d627 Added support for hunk start markers (@@…@@). For these, we set the whole line in reverse video, in the same color we use for index lines. Peter Hosey parents: 1 diff changeset	314 + '@@'
9eda9139d627 Added support for hunk start markers (@@…@@). For these, we set the whole line in reverse video, in the same color we use for index lines. Peter Hosey parents: 1 diff changeset	315 )
0 2df4ed64a388 Initial check-in of first working version. Peter Hosey parents: diff changeset	316
17 54a209909531 Make the file importable for debugging purposes by wrapping the main-program-only bits in an if __name__ == "__main__" block. Peter Hosey <hg@boredzo.org> parents: 15 diff changeset	317 if __name__ == "__main__":
54a209909531 Make the file importable for debugging purposes by wrapping the main-program-only bits in an if __name__ == "__main__" block. Peter Hosey <hg@boredzo.org> parents: 15 diff changeset	318 if sys.stdin.isatty():
54a209909531 Make the file importable for debugging purposes by wrapping the main-program-only bits in an if __name__ == "__main__" block. Peter Hosey <hg@boredzo.org> parents: 15 diff changeset	319 # Standard input is a TTY, meaning that the user ran 'diff-colorize' at the shell prompt, without redirecting anything into it. Print usage info and exit.
54a209909531 Make the file importable for debugging purposes by wrapping the main-program-only bits in an if __name__ == "__main__" block. Peter Hosey <hg@boredzo.org> parents: 15 diff changeset	320 sys.exit(USAGE)
9 cce6b860a98d Added usage information. Peter Hosey parents: 8 diff changeset	321
18 83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	322 # Buffers to support interleaving old and new lines that were contiguous runs.
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	323 buffer_old = [] # '-' lines
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	324 buffer_new = [] # '+' lines
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	325
19 b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	326 def flush_buffers(buffer_old, buffer_new):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	327 "Flush the buffers, interleaving the lines and highlighting differences between them."
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	328 def print_single_line(buffered_line):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	329 prefix = '-' if buffered_line.startswith('-') else '+'
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	330 buffered_line = buffered_line[len(prefix):]
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	331
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	332 sys.stdout.write(prefixes[prefix])
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	333 sys.stdout.write(buffered_line)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	334 sys.stdout.write(RESET_FORMAT)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	335
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	336 last_line_if_old = None
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	337 for buffered_line in interleave(buffer_old, buffer_new):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	338 if buffered_line.startswith('-'):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	339 if last_line_if_old is not None:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	340 print_single_line(last_line_if_old)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	341 last_line_if_old = buffered_line
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	342 else:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	343 if last_line_if_old is None:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	344 # No old line immediately preceding this, so just print it.
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	345 print_single_line(buffered_line)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	346 else:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	347 old_line = last_line_if_old
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	348 new_line = buffered_line
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	349
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	350 old_line_output = [prefixes['-']]
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	351 new_line_output = [prefixes['+']]
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	352 for node in common_and_distinct_substrings(old_line[1:], new_line[1:]):
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	353 if node.differ:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	354 old_line_output.append(BEGIN_REVERSE_FORMAT)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	355 old_line_output.append(str(node.a))
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	356 old_line_output.append(END_REVERSE_FORMAT)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	357
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	358 new_line_output.append(BEGIN_REVERSE_FORMAT)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	359 new_line_output.append(str(node.b))
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	360 new_line_output.append(END_REVERSE_FORMAT)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	361 else:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	362 old_line_output.append(str(node.a))
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	363 new_line_output.append(str(node.b))
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	364
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	365 last_line_if_old = None
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	366 sys.stdout.writelines(''.join(old_line_output))
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	367 sys.stdout.writelines(''.join(new_line_output))
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	368 else:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	369 if last_line_if_old is not None:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	370 print_single_line(last_line_if_old)
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	371
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	372 del buffer_old[:]
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	373 del buffer_new[:]
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	374
17 54a209909531 Make the file importable for debugging purposes by wrapping the main-program-only bits in an if __name__ == "__main__" block. Peter Hosey <hg@boredzo.org> parents: 15 diff changeset	375 for line in fileinput.input():
18 83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	376 if line.startswith('-') and not line.startswith('---'):
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	377 buffer_old.append(line)
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	378 continue
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	379 elif line.startswith('+') and not line.startswith('+++'):
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	380 buffer_new.append(line)
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	381 continue
83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	382 else:
19 b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	383 flush_buffers(buffer_old, buffer_new)
18 83d58ccc70bf Interleave adjacent runs of consecutive old and new lines into alternating old and new lines. Peter Hosey <hg@boredzo.org> parents: 17 diff changeset	384
17 54a209909531 Make the file importable for debugging purposes by wrapping the main-program-only bits in an if __name__ == "__main__" block. Peter Hosey <hg@boredzo.org> parents: 15 diff changeset	385 for prefix_to_test in prefixes:
54a209909531 Make the file importable for debugging purposes by wrapping the main-program-only bits in an if __name__ == "__main__" block. Peter Hosey <hg@boredzo.org> parents: 15 diff changeset	386 if line.startswith(prefix_to_test):
54a209909531 Make the file importable for debugging purposes by wrapping the main-program-only bits in an if __name__ == "__main__" block. Peter Hosey <hg@boredzo.org> parents: 15 diff changeset	387 sys.stdout.write(prefixes[prefix_to_test])
54a209909531 Make the file importable for debugging purposes by wrapping the main-program-only bits in an if __name__ == "__main__" block. Peter Hosey <hg@boredzo.org> parents: 15 diff changeset	388 line = line[len(prefix_to_test):]
0 2df4ed64a388 Initial check-in of first working version. Peter Hosey parents: diff changeset	389
17 54a209909531 Make the file importable for debugging purposes by wrapping the main-program-only bits in an if __name__ == "__main__" block. Peter Hosey <hg@boredzo.org> parents: 15 diff changeset	390 sys.stdout.write(line)
0 2df4ed64a388 Initial check-in of first working version. Peter Hosey parents: diff changeset	391
17 54a209909531 Make the file importable for debugging purposes by wrapping the main-program-only bits in an if __name__ == "__main__" block. Peter Hosey <hg@boredzo.org> parents: 15 diff changeset	392 sys.stdout.write(RESET_FORMAT)
19 b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	393 else:
b709258a2fc2 Added highlighting differences between consecutive old and new lines. Peter Hosey <hg@boredzo.org> parents: 18 diff changeset	394 flush_buffers(buffer_old, buffer_new)

Mercurial > diff-colorize

annotate diff-colorize.py @ 20:b4caea436f4d