2
# Copyright (C) 2005 Bram Cohen, Copyright (C) 2005, 2006 Canonical Ltd
4
# This program is free software; you can redistribute it and/or modify
5
# it under the terms of the GNU General Public License as published by
6
# the Free Software Foundation; either version 2 of the License, or
7
# (at your option) any later version.
9
# This program is distributed in the hope that it will be useful,
10
# but WITHOUT ANY WARRANTY; without even the implied warranty of
11
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12
# GNU General Public License for more details.
14
# You should have received a copy of the GNU General Public License
15
# along with this program; if not, write to the Free Software
16
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19
from bisect import bisect
26
from bzrlib.trace import mutter
29
__all__ = ['PatienceSequenceMatcher', 'unified_diff', 'unified_diff_files']
33
"""Find the longest common subset for unique lines.
35
:param a: An indexable object (such as string or list of strings)
36
:param b: Another indexable object (such as string or list of strings)
37
:return: A list of tuples, one for each line which is matched.
38
[(line_in_a, line_in_b), ...]
40
This only matches lines which are unique on both sides.
41
This helps prevent common lines from over influencing match
43
The longest common subset uses the Patience Sorting algorithm:
44
http://en.wikipedia.org/wiki/Patience_sorting
46
# set index[line in a] = position of line in a unless
47
# unless a is a duplicate, in which case it's set to None
49
for i in xrange(len(a)):
55
# make btoa[i] = position of line i in a, unless
56
# that line doesn't occur exactly once in both,
57
# in which case it's set to None
58
btoa = [None] * len(b)
60
for pos, line in enumerate(b):
61
next = index.get(line)
64
# unset the previous mapping, which we now know to
65
# be invalid because the line isn't unique
66
btoa[index2[line]] = None
71
# this is the Patience sorting algorithm
72
# see http://en.wikipedia.org/wiki/Patience_sorting
73
backpointers = [None] * len(b)
77
for bpos, apos in enumerate(btoa):
80
# as an optimization, check if the next line comes at the end,
81
# because it usually does
82
if stacks and stacks[-1] < apos:
84
# as an optimization, check if the next line comes right after
85
# the previous line, because usually it does
86
elif stacks and stacks[k] < apos and (k == len(stacks) - 1 or
90
k = bisect(stacks, apos)
92
backpointers[bpos] = lasts[k-1]
104
result.append((btoa[k], k))
110
def recurse_matches(a, b, ahi, bhi, answer, maxrecursion):
111
"""Find all of the matching text in the lines of a and b.
114
:param b: Another sequence
115
:param ahi: The maximum length of a to check, typically len(a)
116
:param bhi: The maximum length of b to check, typically len(b)
117
:param answer: The return array. Will be filled with tuples
118
indicating [(line_in_a, line_in_b)]
119
:param maxrecursion: The maximum depth to recurse.
120
Must be a positive integer.
121
:return: None, the return value is in the parameter answer, which
126
mutter('max recursion depth reached')
127
# this will never happen normally, this check is to prevent DOS attacks
129
oldlength = len(answer)
133
alo, blo = answer[-1]
136
if alo == ahi or blo == bhi:
140
for apos, bpos in unique_lcs(a[alo:ahi], b[blo:bhi]):
141
# recurse between lines which are unique in each file and match
144
# Most of the time, you will have a sequence of similar entries
145
if last_a_pos+1 != apos or last_b_pos+1 != bpos:
146
recurse_matches(a, b, apos, bpos, answer, maxrecursion - 1)
149
answer.append((apos, bpos))
150
if len(answer) > oldlength:
151
# find matches between the last match and the end
152
recurse_matches(a, b, ahi, bhi, answer, maxrecursion - 1)
153
elif a[alo] == b[blo]:
154
# find matching lines at the very beginning
155
while alo < ahi and blo < bhi and a[alo] == b[blo]:
156
answer.append((alo, blo))
159
recurse_matches(a, b, ahi, bhi, answer, maxrecursion - 1)
160
elif a[ahi - 1] == b[bhi - 1]:
161
# find matching lines at the very end
164
while nahi > alo and nbhi > blo and a[nahi - 1] == b[nbhi - 1]:
167
recurse_matches(a, b, nahi, nbhi, answer, maxrecursion - 1)
168
for i in xrange(ahi - nahi):
169
answer.append((nahi + i, nbhi + i))
172
class PatienceSequenceMatcher(difflib.SequenceMatcher):
173
"""Compare a pair of sequences using longest common subset."""
175
def __init__(self, isjunk=None, a='', b=''):
176
if isjunk is not None:
177
raise NotImplementedError('Currently we do not support'
178
' isjunk for sequence matching')
179
difflib.SequenceMatcher.__init__(self, isjunk, a, b)
181
def _check_with_diff(self, alo, ahi, blo, bhi, answer):
182
"""Use the original diff algorithm on an unmatched section.
184
This will check to make sure the range is worth checking,
185
before doing any work.
187
:param alo: The last line that actually matched
188
:param ahi: The next line that actually matches
189
:param blo: Same as alo, only for the 'b' set
190
:param bhi: Same as ahi
191
:param answer: An array which will have the new ranges appended to it
195
# recurse_matches has an implementation design
196
# which does not match non-unique lines in the
197
# if they do not touch matching unique lines
198
# so we rerun the regular diff algorithm
199
# if find a large enough chunk.
201
# recurse_matches already looked at the direct
202
# neighbors, so we only need to run if there is
203
# enough space to do so
204
if ahi - alo > 2 and bhi - blo > 2:
205
a = self.a[alo+1:ahi-1]
206
b = self.b[blo+1:bhi-1]
207
m = difflib.SequenceMatcher(None, a, b)
208
new_blocks = m.get_matching_blocks()
209
# difflib always adds a final match
211
for blk in new_blocks:
212
answer.append((blk[0]+alo+1,
216
def get_matching_blocks(self):
217
"""Return list of triples describing matching subsequences.
219
Each triple is of the form (i, j, n), and means that
220
a[i:i+n] == b[j:j+n]. The triples are monotonically increasing in
223
The last triple is a dummy, (len(a), len(b), 0), and is the only
226
>>> s = PatienceSequenceMatcher(None, "abxcd", "abcd")
227
>>> s.get_matching_blocks()
228
[(0, 0, 2), (3, 2, 2), (5, 4, 0)]
230
# jam 20060525 This is the python 2.4.1 difflib get_matching_blocks
231
# implementation which uses __helper. 2.4.3 got rid of helper for
232
# doing it inline with a queue.
233
# We should consider doing the same for recurse_matches
235
if self.matching_blocks is not None:
236
return self.matching_blocks
237
self.matching_blocks = []
238
la, lb = len(self.a), len(self.b)
239
self._find_matching_blocks(0, la, 0, lb, self.matching_blocks)
240
self.matching_blocks.append( (la, lb, 0) )
241
return self.matching_blocks
243
def _find_matching_blocks(self, alo, ahi, blo, bhi, answer):
247
recurse_matches(a, b, len(a), len(b), matches, 10)
248
# Matches now has individual line pairs of
249
# line A matches line B, at the given offsets
251
start_a = start_b = None
253
for i_a, i_b in matches:
254
if (start_a is not None
255
and (i_a == start_a + length)
256
and (i_b == start_b + length)):
261
# We need to check from 0,0 until the current match
262
self._check_with_diff(alo-1, i_a+alo, blo-1, i_b+blo,
265
answer.append((start_a+alo, start_b+blo, length))
266
self._check_with_diff(start_a+alo+length, i_a+alo,
267
start_b+blo+length, i_b+blo,
275
answer.append((start_a+alo, start_b+blo, length))
276
self._check_with_diff(start_a+alo+length, ahi+1,
277
start_b+blo+length, bhi+1,
280
# Nothing matched, so we need to send the complete text
281
self._check_with_diff(alo-1, ahi+1, blo-1, bhi+1, answer)
283
# For consistency sake, make sure all matches are only increasing
287
for a,b,match_len in answer:
288
assert a >= next_a, 'Non increasing matches for a'
289
assert b >= next_b, 'Not increasing matches for b'
290
next_a = a + match_len
291
next_b = b + match_len
294
# This is a version of unified_diff which only adds a factory parameter
295
# so that you can override the default SequenceMatcher
296
# this has been submitted as a patch to python
297
def unified_diff(a, b, fromfile='', tofile='', fromfiledate='',
298
tofiledate='', n=3, lineterm='\n',
299
sequencematcher=None):
301
Compare two sequences of lines; generate the delta as a unified diff.
303
Unified diffs are a compact way of showing line changes and a few
304
lines of context. The number of context lines is set by 'n' which
307
By default, the diff control lines (those with ---, +++, or @@) are
308
created with a trailing newline. This is helpful so that inputs
309
created from file.readlines() result in diffs that are suitable for
310
file.writelines() since both the inputs and outputs have trailing
313
For inputs that do not have trailing newlines, set the lineterm
314
argument to "" so that the output will be uniformly newline free.
316
The unidiff format normally has a header for filenames and modification
317
times. Any or all of these may be specified using strings for
318
'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'. The modification
319
times are normally expressed in the format returned by time.ctime().
323
>>> for line in unified_diff('one two three four'.split(),
324
... 'zero one tree four'.split(), 'Original', 'Current',
325
... 'Sat Jan 26 23:30:50 1991', 'Fri Jun 06 10:20:52 2003',
328
--- Original Sat Jan 26 23:30:50 1991
329
+++ Current Fri Jun 06 10:20:52 2003
338
if sequencematcher is None:
339
sequencematcher = difflib.SequenceMatcher
342
for group in sequencematcher(None,a,b).get_grouped_opcodes(n):
344
yield '--- %s %s%s' % (fromfile, fromfiledate, lineterm)
345
yield '+++ %s %s%s' % (tofile, tofiledate, lineterm)
347
i1, i2, j1, j2 = group[0][1], group[-1][2], group[0][3], group[-1][4]
348
yield "@@ -%d,%d +%d,%d @@%s" % (i1+1, i2-i1, j1+1, j2-j1, lineterm)
349
for tag, i1, i2, j1, j2 in group:
351
for line in a[i1:i2]:
354
if tag == 'replace' or tag == 'delete':
355
for line in a[i1:i2]:
357
if tag == 'replace' or tag == 'insert':
358
for line in b[j1:j2]:
362
def unified_diff_files(a, b, sequencematcher=None):
363
"""Generate the diff for two files.
365
# Should this actually be an error?
372
file_a = open(a, 'rb')
373
time_a = os.stat(a).st_mtime
379
file_b = open(b, 'rb')
380
time_b = os.stat(b).st_mtime
382
# TODO: Include fromfiledate and tofiledate
383
return unified_diff(file_a.readlines(), file_b.readlines(),
384
fromfile=a, tofile=b,
385
sequencematcher=sequencematcher)
390
p = optparse.OptionParser(usage='%prog [options] file_a file_b'
391
'\nFiles can be "-" to read from stdin')
392
p.add_option('--patience', dest='matcher', action='store_const', const='patience',
393
default='patience', help='Use the patience difference algorithm')
394
p.add_option('--difflib', dest='matcher', action='store_const', const='difflib',
395
default='patience', help='Use python\'s difflib algorithm')
397
algorithms = {'patience':PatienceSequenceMatcher, 'difflib':difflib.SequenceMatcher}
399
(opts, args) = p.parse_args(args)
400
matcher = algorithms[opts.matcher]
403
print 'You must supply 2 filenames to diff'
406
for line in unified_diff_files(args[0], args[1], sequencematcher=matcher):
407
sys.stdout.write(line)
409
if __name__ == '__main__':
410
sys.exit(main(sys.argv[1:]))
added
removed
bzrlib/patiencediff.py
