106
def recurse_matches_py(a, b, alo, blo, ahi, bhi, answer, maxrecursion):
108
def recurse_matches(a, b, ahi, bhi, answer, maxrecursion):
107
109
"""Find all of the matching text in the lines of a and b.
109
111
:param a: A sequence
110
112
:param b: Another sequence
111
:param alo: The start location of a to check, typically 0
112
:param ahi: The start location of b to check, typically 0
113
113
:param ahi: The maximum length of a to check, typically len(a)
114
114
:param bhi: The maximum length of b to check, typically len(b)
115
115
:param answer: The return array. Will be filled with tuples
116
indicating [(line_in_a, line_in_b)]
116
indicating [(line_in_a), (line_in_b)]
117
117
:param maxrecursion: The maximum depth to recurse.
118
118
Must be a positive integer.
119
119
:return: None, the return value is in the parameter answer, which
123
124
if maxrecursion < 0:
124
mutter('max recursion depth reached')
125
125
# this will never happen normally, this check is to prevent DOS attacks
127
127
oldlength = len(answer)
131
alo, blo = answer[-1]
128
134
if alo == ahi or blo == bhi:
132
for apos, bpos in unique_lcs_py(a[alo:ahi], b[blo:bhi]):
136
for apos, bpos in unique_lcs(a[alo:ahi], b[blo:bhi]):
133
137
# recurse between lines which are unique in each file and match
136
# Most of the time, you will have a sequence of similar entries
137
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)
140
recurse_matches(a, b, apos, bpos, answer, maxrecursion - 1)
142
141
answer.append((apos, bpos))
143
142
if len(answer) > oldlength:
144
143
# 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)
144
recurse_matches(a, b, ahi, bhi, answer, maxrecursion - 1)
147
145
elif a[alo] == b[blo]:
148
146
# find matching lines at the very beginning
149
147
while alo < ahi and blo < bhi and a[alo] == b[blo]:
150
148
answer.append((alo, blo))
153
recurse_matches_py(a, b, alo, blo,
154
ahi, bhi, answer, maxrecursion - 1)
151
recurse_matches(a, b, ahi, bhi, answer, maxrecursion - 1)
155
152
elif a[ahi - 1] == b[bhi - 1]:
156
153
# find matching lines at the very end
159
156
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)
159
recurse_matches(a, b, nahi, nbhi, answer, maxrecursion - 1)
164
160
for i in xrange(ahi - nahi):
165
161
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):
164
class SequenceMatcher(difflib.SequenceMatcher):
209
165
"""Compare a pair of sequences using longest common subset."""
211
_do_check_consistency = True
213
167
def __init__(self, isjunk=None, a='', b=''):
214
168
if isjunk is not None:
215
169
raise NotImplementedError('Currently we do not support'
216
170
' isjunk for sequence matching')
217
171
difflib.SequenceMatcher.__init__(self, isjunk, a, b)
219
def get_matching_blocks(self):
220
"""Return list of triples describing matching subsequences.
222
Each triple is of the form (i, j, n), and means that
223
a[i:i+n] == b[j:j+n]. The triples are monotonically increasing in
226
The last triple is a dummy, (len(a), len(b), 0), and is the only
229
>>> s = PatienceSequenceMatcher(None, "abxcd", "abcd")
230
>>> s.get_matching_blocks()
231
[(0, 0, 2), (3, 2, 2), (5, 4, 0)]
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
233
# jam 20060525 This is the python 2.4.1 difflib get_matching_blocks
234
# implementation which uses __helper. 2.4.3 got rid of helper for
235
# doing it inline with a queue.
236
# We should consider doing the same for recurse_matches
238
if self.matching_blocks is not None:
239
return self.matching_blocks
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 __helper(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)
212
recurse_matches(a, b, len(a), len(b), matches, 10)
244
213
# Matches now has individual line pairs of
245
214
# 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
216
start_a = start_b = None
218
for i_a, i_b in matches:
219
if (start_a is not None
220
and (i_a == start_a + length)
221
and (i_b == start_b + length)):
226
# We need to check from 0,0 until the current match
227
self._check_with_diff(alo-1, i_a+alo, blo-1, i_b+blo,
230
answer.append((start_a+alo, start_b+blo, length))
231
self._check_with_diff(start_a+alo+length, i_a+alo,
232
start_b+blo+length, i_b+blo,
240
answer.append((start_a+alo, start_b+blo, length))
241
self._check_with_diff(start_a+alo+length, ahi+1,
242
start_b+blo+length, bhi+1,
245
# Nothing matched, so we need to send the complete text
246
self._check_with_diff(alo-1, ahi+1, blo-1, bhi+1, answer)
248
# For consistency sake, make sure all matches are only increasing
252
for a,b,match_len in answer:
253
assert a >= next_a, 'Non increasing matches for a'
254
assert b >= next_b, 'Not increasing matches for b'
255
next_a = a + match_len
256
next_b = b + match_len
259
# This is a version of unified_diff which only adds a factory parameter
260
# so that you can override the default SequenceMatcher
261
# this has been submitted as a patch to python
262
def unified_diff(a, b, fromfile='', tofile='', fromfiledate='',
263
tofiledate='', n=3, lineterm='\n',
264
sequencematcher=None):
266
Compare two sequences of lines; generate the delta as a unified diff.
268
Unified diffs are a compact way of showing line changes and a few
269
lines of context. The number of context lines is set by 'n' which
272
By default, the diff control lines (those with ---, +++, or @@) are
273
created with a trailing newline. This is helpful so that inputs
274
created from file.readlines() result in diffs that are suitable for
275
file.writelines() since both the inputs and outputs have trailing
278
For inputs that do not have trailing newlines, set the lineterm
279
argument to "" so that the output will be uniformly newline free.
281
The unidiff format normally has a header for filenames and modification
282
times. Any or all of these may be specified using strings for
283
'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'. The modification
284
times are normally expressed in the format returned by time.ctime().
288
>>> for line in unified_diff('one two three four'.split(),
289
... 'zero one tree four'.split(), 'Original', 'Current',
290
... 'Sat Jan 26 23:30:50 1991', 'Fri Jun 06 10:20:52 2003',
293
--- Original Sat Jan 26 23:30:50 1991
294
+++ Current Fri Jun 06 10:20:52 2003
303
if sequencematcher is None:
304
sequencematcher = difflib.SequenceMatcher
307
for group in sequencematcher(None,a,b).get_grouped_opcodes(n):
309
yield '--- %s %s%s' % (fromfile, fromfiledate, lineterm)
310
yield '+++ %s %s%s' % (tofile, tofiledate, lineterm)
312
i1, i2, j1, j2 = group[0][1], group[-1][2], group[0][3], group[-1][4]
313
yield "@@ -%d,%d +%d,%d @@%s" % (i1+1, i2-i1, j1+1, j2-j1, lineterm)
314
for tag, i1, i2, j1, j2 in group:
316
for line in a[i1:i2]:
319
if tag == 'replace' or tag == 'delete':
320
for line in a[i1:i2]:
322
if tag == 'replace' or tag == 'insert':
323
for line in b[j1:j2]:
327
def unified_diff_files(a, b, sequencematcher=None):
328
"""Generate the diff for two files.
330
# Should this actually be an error?
337
file_a = open(a, 'rb')
338
time_a = os.stat(a).st_mtime
344
file_b = open(b, 'rb')
345
time_b = os.stat(b).st_mtime
347
# TODO: Include fromfiledate and tofiledate
348
return unified_diff(file_a.readlines(), file_b.readlines(),
349
fromfile=a, tofile=b,
350
sequencematcher=sequencematcher)
355
p = optparse.OptionParser(usage='%prog [options] file_a file_b'
356
'\nFiles can be "-" to read from stdin')
357
p.add_option('--cdv', dest='matcher', action='store_const', const='cdv',
358
default='cdv', help='Use the cdv difference algorithm')
359
p.add_option('--difflib', dest='matcher', action='store_const', const='difflib',
360
default='cdv', help='Use python\'s difflib algorithm')
362
algorithms = {'cdv':SequenceMatcher, 'difflib':difflib.SequenceMatcher}
364
(opts, args) = p.parse_args(args)
365
matcher = algorithms[opts.matcher]
368
print 'You must supply 2 filenames to diff'
371
for line in unified_diff_files(args[0], args[1], sequencematcher=matcher):
372
sys.stdout.write(line)
374
if __name__ == '__main__':
375
sys.exit(main(sys.argv[1:]))
added
removed
bzrlib/patiencediff.py
