108
def recurse_matches(a, b, ahi, bhi, answer, maxrecursion):
106
def recurse_matches_py(a, b, alo, blo, ahi, bhi, answer, maxrecursion):
109
107
"""Find all of the matching text in the lines of a and b.
111
109
:param a: A sequence
112
110
: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
124
123
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]
134
128
if alo == ahi or blo == bhi:
136
for apos, bpos in unique_lcs(a[alo:ahi], b[blo:bhi]):
132
for apos, bpos in unique_lcs_py(a[alo:ahi], b[blo:bhi]):
137
133
# recurse between lines which are unique in each file and match
140
recurse_matches(a, b, apos, bpos, answer, maxrecursion - 1)
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)
141
142
answer.append((apos, bpos))
142
143
if len(answer) > oldlength:
143
144
# find matches between the last match and the end
144
recurse_matches(a, b, ahi, bhi, answer, maxrecursion - 1)
145
recurse_matches_py(a, b, last_a_pos+1, last_b_pos+1,
146
ahi, bhi, answer, maxrecursion - 1)
145
147
elif a[alo] == b[blo]:
146
148
# find matching lines at the very beginning
147
149
while alo < ahi and blo < bhi and a[alo] == b[blo]:
148
150
answer.append((alo, blo))
151
recurse_matches(a, b, ahi, bhi, answer, maxrecursion - 1)
153
recurse_matches_py(a, b, alo, blo,
154
ahi, bhi, answer, maxrecursion - 1)
152
155
elif a[ahi - 1] == b[bhi - 1]:
153
156
# find matching lines at the very end
156
159
while nahi > alo and nbhi > blo and a[nahi - 1] == b[nbhi - 1]:
159
recurse_matches(a, b, nahi, nbhi, answer, maxrecursion - 1)
162
recurse_matches_py(a, b, last_a_pos+1, last_b_pos+1,
163
nahi, nbhi, answer, maxrecursion - 1)
160
164
for i in xrange(ahi - nahi):
161
165
answer.append((nahi + i, nbhi + i))
164
class SequenceMatcher(difflib.SequenceMatcher):
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:
200
assert a >= next_a, 'Non increasing matches for a'
201
assert b >= next_b, 'Not increasing matches for b'
202
next_a = a + match_len
203
next_b = b + match_len
206
class PatienceSequenceMatcher_py(difflib.SequenceMatcher):
165
207
"""Compare a pair of sequences using longest common subset."""
209
_do_check_consistency = True
167
211
def __init__(self, isjunk=None, a='', b=''):
168
212
if isjunk is not None:
169
213
raise NotImplementedError('Currently we do not support'
170
214
' isjunk for sequence matching')
171
215
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
217
def get_matching_blocks(self):
218
"""Return list of triples describing matching subsequences.
220
Each triple is of the form (i, j, n), and means that
221
a[i:i+n] == b[j:j+n]. The triples are monotonically increasing in
224
The last triple is a dummy, (len(a), len(b), 0), and is the only
227
>>> s = PatienceSequenceMatcher(None, "abxcd", "abcd")
228
>>> s.get_matching_blocks()
229
[(0, 0, 2), (3, 2, 2), (5, 4, 0)]
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):
231
# jam 20060525 This is the python 2.4.1 difflib get_matching_blocks
232
# implementation which uses __helper. 2.4.3 got rid of helper for
233
# doing it inline with a queue.
234
# We should consider doing the same for recurse_matches
236
if self.matching_blocks is not None:
237
return self.matching_blocks
212
recurse_matches(a, b, len(a), len(b), matches, 10)
240
recurse_matches_py(self.a, self.b, 0, 0,
241
len(self.a), len(self.b), matches, 10)
213
242
# Matches now has individual line pairs of
214
243
# line A matches line B, at the given offsets
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:]))
244
self.matching_blocks = _collapse_sequences(matches)
245
self.matching_blocks.append( (len(self.a), len(self.b), 0) )
246
if PatienceSequenceMatcher_py._do_check_consistency:
248
_check_consistency(self.matching_blocks)
250
return self.matching_blocks
added
removed
bzrlib/_patiencediff_py.py
