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
27
__all__ = ['PatienceSequenceMatcher', 'unified_diff', 'unified_diff_files']
31
"""Find the longest common subset for unique lines.
33
:param a: An indexable object (such as string or list of strings)
34
:param b: Another indexable object (such as string or list of strings)
35
:return: A list of tuples, one for each line which is matched.
36
[(line_in_a, line_in_b), ...]
38
This only matches lines which are unique on both sides.
39
This helps prevent common lines from over influencing match
41
The longest common subset uses the Patience Sorting algorithm:
42
http://en.wikipedia.org/wiki/Patience_sorting
44
# set index[line in a] = position of line in a unless
45
# unless a is a duplicate, in which case it's set to None
47
for i in xrange(len(a)):
53
# make btoa[i] = position of line i in a, unless
54
# that line doesn't occur exactly once in both,
55
# in which case it's set to None
56
btoa = [None] * len(b)
58
for pos, line in enumerate(b):
59
next = index.get(line)
62
# unset the previous mapping, which we now know to
63
# be invalid because the line isn't unique
64
btoa[index2[line]] = None
69
# this is the Patience sorting algorithm
70
# see http://en.wikipedia.org/wiki/Patience_sorting
71
backpointers = [None] * len(b)
75
for bpos, apos in enumerate(btoa):
78
# as an optimization, check if the next line comes at the end,
79
# because it usually does
80
if stacks and stacks[-1] < apos:
82
# as an optimization, check if the next line comes right after
83
# the previous line, because usually it does
84
elif stacks and stacks[k] < apos and (k == len(stacks) - 1 or
88
k = bisect(stacks, apos)
90
backpointers[bpos] = lasts[k-1]
102
result.append((btoa[k], k))
108
def recurse_matches(a, b, ahi, bhi, answer, maxrecursion):
109
"""Find all of the matching text in the lines of a and b.
112
:param b: Another sequence
113
:param ahi: The maximum length of a to check, typically len(a)
114
:param bhi: The maximum length of b to check, typically len(b)
115
:param answer: The return array. Will be filled with tuples
116
indicating [(line_in_a), (line_in_b)]
117
:param maxrecursion: The maximum depth to recurse.
118
Must be a positive integer.
119
:return: None, the return value is in the parameter answer, which
125
# this will never happen normally, this check is to prevent DOS attacks
127
oldlength = len(answer)
131
alo, blo = answer[-1]
134
if alo == ahi or blo == bhi:
136
for apos, bpos in unique_lcs(a[alo:ahi], b[blo:bhi]):
137
# recurse between lines which are unique in each file and match
140
recurse_matches(a, b, apos, bpos, answer, maxrecursion - 1)
141
answer.append((apos, bpos))
142
if len(answer) > oldlength:
143
# find matches between the last match and the end
144
recurse_matches(a, b, ahi, bhi, answer, maxrecursion - 1)
145
elif a[alo] == b[blo]:
146
# find matching lines at the very beginning
147
while alo < ahi and blo < bhi and a[alo] == b[blo]:
148
answer.append((alo, blo))
151
recurse_matches(a, b, ahi, bhi, answer, maxrecursion - 1)
152
elif a[ahi - 1] == b[bhi - 1]:
153
# find matching lines at the very end
156
while nahi > alo and nbhi > blo and a[nahi - 1] == b[nbhi - 1]:
159
recurse_matches(a, b, nahi, nbhi, answer, maxrecursion - 1)
160
for i in xrange(ahi - nahi):
161
answer.append((nahi + i, nbhi + i))
164
class PatienceSequenceMatcher(difflib.SequenceMatcher):
165
"""Compare a pair of sequences using longest common subset."""
167
def __init__(self, isjunk=None, a='', b=''):
168
if isjunk is not None:
169
raise NotImplementedError('Currently we do not support'
170
' isjunk for sequence matching')
171
difflib.SequenceMatcher.__init__(self, isjunk, a, b)
173
def _check_with_diff(self, alo, ahi, blo, bhi, answer):
174
"""Use the original diff algorithm on an unmatched section.
176
This will check to make sure the range is worth checking,
177
before doing any work.
179
:param alo: The last line that actually matched
180
:param ahi: The next line that actually matches
181
:param blo: Same as alo, only for the 'b' set
182
:param bhi: Same as ahi
183
:param answer: An array which will have the new ranges appended to it
187
# recurse_matches has an implementation design
188
# which does not match non-unique lines in the
189
# if they do not touch matching unique lines
190
# so we rerun the regular diff algorithm
191
# if find a large enough chunk.
193
# recurse_matches already looked at the direct
194
# neighbors, so we only need to run if there is
195
# enough space to do so
196
if ahi - alo > 2 and bhi - blo > 2:
197
a = self.a[alo+1:ahi-1]
198
b = self.b[blo+1:bhi-1]
199
m = difflib.SequenceMatcher(None, a, b)
200
new_blocks = m.get_matching_blocks()
201
# difflib always adds a final match
203
for blk in new_blocks:
204
answer.append((blk[0]+alo+1,
208
def get_matching_blocks(self):
209
"""Return list of triples describing matching subsequences.
211
Each triple is of the form (i, j, n), and means that
212
a[i:i+n] == b[j:j+n]. The triples are monotonically increasing in
215
The last triple is a dummy, (len(a), len(b), 0), and is the only
218
>>> s = PatienceSequenceMatcher(None, "abxcd", "abcd")
219
>>> s.get_matching_blocks()
220
[(0, 0, 2), (3, 2, 2), (5, 4, 0)]
222
# jam 20060525 This is the python 2.4.1 difflib get_matching_blocks
223
# implementation which uses __helper. 2.4.3 got rid of helper for
224
# doing it inline with a queue.
225
# We should consider doing the same for recurse_matches
227
if self.matching_blocks is not None:
228
return self.matching_blocks
229
self.matching_blocks = []
230
la, lb = len(self.a), len(self.b)
231
self.__helper(0, la, 0, lb, self.matching_blocks)
232
self.matching_blocks.append( (la, lb, 0) )
233
return self.matching_blocks
235
def __helper(self, alo, ahi, blo, bhi, answer):
239
recurse_matches(a, b, len(a), len(b), matches, 10)
240
# Matches now has individual line pairs of
241
# line A matches line B, at the given offsets
243
start_a = start_b = None
245
for i_a, i_b in matches:
246
if (start_a is not None
247
and (i_a == start_a + length)
248
and (i_b == start_b + length)):
253
# We need to check from 0,0 until the current match
254
self._check_with_diff(alo-1, i_a+alo, blo-1, i_b+blo,
257
answer.append((start_a+alo, start_b+blo, length))
258
self._check_with_diff(start_a+alo+length, i_a+alo,
259
start_b+blo+length, i_b+blo,
267
answer.append((start_a+alo, start_b+blo, length))
268
self._check_with_diff(start_a+alo+length, ahi+1,
269
start_b+blo+length, bhi+1,
272
# Nothing matched, so we need to send the complete text
273
self._check_with_diff(alo-1, ahi+1, blo-1, bhi+1, answer)
275
# For consistency sake, make sure all matches are only increasing
279
for a,b,match_len in answer:
280
assert a >= next_a, 'Non increasing matches for a'
281
assert b >= next_b, 'Not increasing matches for b'
282
next_a = a + match_len
283
next_b = b + match_len
286
# This is a version of unified_diff which only adds a factory parameter
287
# so that you can override the default SequenceMatcher
288
# this has been submitted as a patch to python
289
def unified_diff(a, b, fromfile='', tofile='', fromfiledate='',
290
tofiledate='', n=3, lineterm='\n',
291
sequencematcher=None):
293
Compare two sequences of lines; generate the delta as a unified diff.
295
Unified diffs are a compact way of showing line changes and a few
296
lines of context. The number of context lines is set by 'n' which
299
By default, the diff control lines (those with ---, +++, or @@) are
300
created with a trailing newline. This is helpful so that inputs
301
created from file.readlines() result in diffs that are suitable for
302
file.writelines() since both the inputs and outputs have trailing
305
For inputs that do not have trailing newlines, set the lineterm
306
argument to "" so that the output will be uniformly newline free.
308
The unidiff format normally has a header for filenames and modification
309
times. Any or all of these may be specified using strings for
310
'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'. The modification
311
times are normally expressed in the format returned by time.ctime().
315
>>> for line in unified_diff('one two three four'.split(),
316
... 'zero one tree four'.split(), 'Original', 'Current',
317
... 'Sat Jan 26 23:30:50 1991', 'Fri Jun 06 10:20:52 2003',
320
--- Original Sat Jan 26 23:30:50 1991
321
+++ Current Fri Jun 06 10:20:52 2003
330
if sequencematcher is None:
331
sequencematcher = difflib.SequenceMatcher
334
for group in sequencematcher(None,a,b).get_grouped_opcodes(n):
336
yield '--- %s %s%s' % (fromfile, fromfiledate, lineterm)
337
yield '+++ %s %s%s' % (tofile, tofiledate, lineterm)
339
i1, i2, j1, j2 = group[0][1], group[-1][2], group[0][3], group[-1][4]
340
yield "@@ -%d,%d +%d,%d @@%s" % (i1+1, i2-i1, j1+1, j2-j1, lineterm)
341
for tag, i1, i2, j1, j2 in group:
343
for line in a[i1:i2]:
346
if tag == 'replace' or tag == 'delete':
347
for line in a[i1:i2]:
349
if tag == 'replace' or tag == 'insert':
350
for line in b[j1:j2]:
354
def unified_diff_files(a, b, sequencematcher=None):
355
"""Generate the diff for two files.
357
# Should this actually be an error?
364
file_a = open(a, 'rb')
365
time_a = os.stat(a).st_mtime
371
file_b = open(b, 'rb')
372
time_b = os.stat(b).st_mtime
374
# TODO: Include fromfiledate and tofiledate
375
return unified_diff(file_a.readlines(), file_b.readlines(),
376
fromfile=a, tofile=b,
377
sequencematcher=sequencematcher)
382
p = optparse.OptionParser(usage='%prog [options] file_a file_b'
383
'\nFiles can be "-" to read from stdin')
384
p.add_option('--patience', dest='matcher', action='store_const', const='patience',
385
default='patience', help='Use the patience difference algorithm')
386
p.add_option('--difflib', dest='matcher', action='store_const', const='difflib',
387
default='patience', help='Use python\'s difflib algorithm')
389
algorithms = {'patience':PatienceSequenceMatcher, 'difflib':difflib.SequenceMatcher}
391
(opts, args) = p.parse_args(args)
392
matcher = algorithms[opts.matcher]
395
print 'You must supply 2 filenames to diff'
398
for line in unified_diff_files(args[0], args[1], sequencematcher=matcher):
399
sys.stdout.write(line)
401
if __name__ == '__main__':
402
sys.exit(main(sys.argv[1:]))
added
removed
bzrlib/patiencediff.py
