125
127
# this will never happen normally, this check is to prevent DOS attacks
127
129
oldlength = len(answer)
133
alo, blo = answer[-1]
128
136
if alo == ahi or blo == bhi:
132
for apos, bpos in unique_lcs_py(a[alo:ahi], b[blo:bhi]):
140
for apos, bpos in unique_lcs(a[alo:ahi], b[blo:bhi]):
133
141
# recurse between lines which are unique in each file and match
136
144
# Most of the time, you will have a sequence of similar entries
137
145
if last_a_pos+1 != apos or last_b_pos+1 != bpos:
138
recurse_matches_py(a, b, last_a_pos+1, last_b_pos+1,
139
apos, bpos, answer, maxrecursion - 1)
146
recurse_matches(a, b, apos, bpos, answer, maxrecursion - 1)
140
147
last_a_pos = apos
141
148
last_b_pos = bpos
142
149
answer.append((apos, bpos))
143
150
if len(answer) > oldlength:
144
151
# find matches between the last match and the end
145
recurse_matches_py(a, b, last_a_pos+1, last_b_pos+1,
146
ahi, bhi, answer, maxrecursion - 1)
152
recurse_matches(a, b, ahi, bhi, answer, maxrecursion - 1)
147
153
elif a[alo] == b[blo]:
148
154
# find matching lines at the very beginning
149
155
while alo < ahi and blo < bhi and a[alo] == b[blo]:
150
156
answer.append((alo, blo))
153
recurse_matches_py(a, b, alo, blo,
154
ahi, bhi, answer, maxrecursion - 1)
159
recurse_matches(a, b, ahi, bhi, answer, maxrecursion - 1)
155
160
elif a[ahi - 1] == b[bhi - 1]:
156
161
# find matching lines at the very end
159
164
while nahi > alo and nbhi > blo and a[nahi - 1] == b[nbhi - 1]:
162
recurse_matches_py(a, b, last_a_pos+1, last_b_pos+1,
163
nahi, nbhi, answer, maxrecursion - 1)
167
recurse_matches(a, b, nahi, nbhi, answer, maxrecursion - 1)
164
168
for i in xrange(ahi - nahi):
165
169
answer.append((nahi + i, nbhi + i))
168
def _collapse_sequences(matches):
169
"""Find sequences of lines.
171
Given a sequence of [(line_in_a, line_in_b),]
172
find regions where they both increment at the same time
175
start_a = start_b = None
177
for i_a, i_b in matches:
178
if (start_a is not None
179
and (i_a == start_a + length)
180
and (i_b == start_b + length)):
183
if start_a is not None:
184
answer.append((start_a, start_b, length))
190
answer.append((start_a, start_b, length))
195
def _check_consistency(answer):
196
# For consistency sake, make sure all matches are only increasing
199
for (a, b, match_len) in answer:
201
raise ValueError('Non increasing matches for a')
203
raise ValueError('Non increasing matches for b')
204
next_a = a + match_len
205
next_b = b + match_len
208
class PatienceSequenceMatcher_py(difflib.SequenceMatcher):
172
class PatienceSequenceMatcher(difflib.SequenceMatcher):
209
173
"""Compare a pair of sequences using longest common subset."""
211
_do_check_consistency = True
213
175
def __init__(self, isjunk=None, a='', b=''):
214
176
if isjunk is not None:
215
177
raise NotImplementedError('Currently we do not support'
216
178
' isjunk for sequence matching')
217
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,
219
216
def get_matching_blocks(self):
220
217
"""Return list of triples describing matching subsequences.
230
227
>>> s.get_matching_blocks()
231
228
[(0, 0, 2), (3, 2, 2), (5, 4, 0)]
233
# jam 20060525 This is the python 2.4.1 difflib get_matching_blocks
230
# jam 20060525 This is the python 2.4.1 difflib get_matching_blocks
234
231
# implementation which uses __helper. 2.4.3 got rid of helper for
235
232
# doing it inline with a queue.
236
233
# We should consider doing the same for recurse_matches
238
235
if self.matching_blocks is not None:
239
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):
242
recurse_matches_py(self.a, self.b, 0, 0,
243
len(self.a), len(self.b), matches, 10)
247
recurse_matches(a, b, len(a), len(b), matches, 10)
244
248
# Matches now has individual line pairs of
245
249
# line A matches line B, at the given offsets
246
self.matching_blocks = _collapse_sequences(matches)
247
self.matching_blocks.append( (len(self.a), len(self.b), 0) )
248
if PatienceSequenceMatcher_py._do_check_consistency:
250
_check_consistency(self.matching_blocks)
252
return self.matching_blocks
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
