« back to all changes in this revision
Viewing changes to bzrlib/patiencediff.py
- browse files at revision 1733
- compare with another revision
- compare with revision 5814
- download diff
- download tarball
- view history from revision 1733
- Committer: Canonical.com Patch Queue Manager
- Date: 2006-05-29 23:15:16 UTC
- mfrom: (1711.2.25 jam-integration)
- Revision ID: pqm@pqm.ubuntu.com-20060529231516-cad98b5042ea75f3
(jam) Updates to PatienceDiff for performance, and other cleanups.
added
removed
bzrlib/patiencediff.py
23
23
import sys
24
24
import time
25
25
26
27
__all__ = ['SequenceMatcher', 'unified_diff', 'unified_diff_files']
26
from bzrlib.trace import mutter
27
28
29
__all__ = ['PatienceSequenceMatcher', 'unified_diff', 'unified_diff_files']
28
30
29
31
30
32
def unique_lcs(a, b):
105
107
return result
106
108
107
109
108
def recurse_matches(a, b, ahi, bhi, answer, maxrecursion):
110
def recurse_matches(a, b, alo, blo, ahi, bhi, answer, maxrecursion):
109
111
"""Find all of the matching text in the lines of a and b.
110
112
111
113
:param a: A sequence
112
114
:param b: Another sequence
115
:param alo: The start location of a to check, typically 0
116
:param ahi: The start location of b to check, typically 0
113
117
:param ahi: The maximum length of a to check, typically len(a)
114
118
:param bhi: The maximum length of b to check, typically len(b)
115
119
:param answer: The return array. Will be filled with tuples
116
indicating [(line_in_a), (line_in_b)]
120
indicating [(line_in_a, line_in_b)]
117
121
:param maxrecursion: The maximum depth to recurse.
118
122
Must be a positive integer.
119
123
:return: None, the return value is in the parameter answer, which
120
124
should be a list
121
125
122
126
"""
123
oldlen = len(answer)
124
127
if maxrecursion < 0:
128
mutter('max recursion depth reached')
125
129
# this will never happen normally, this check is to prevent DOS attacks
126
130
return
127
131
oldlength = len(answer)
128
if len(answer) == 0:
129
alo, blo = 0, 0
130
else:
131
alo, blo = answer[-1]
132
alo += 1
133
blo += 1
134
132
if alo == ahi or blo == bhi:
135
133
return
134
last_a_pos = alo-1
135
last_b_pos = blo-1
136
136
for apos, bpos in unique_lcs(a[alo:ahi], b[blo:bhi]):
137
137
# recurse between lines which are unique in each file and match
138
138
apos += alo
139
139
bpos += blo
140
recurse_matches(a, b, apos, bpos, answer, maxrecursion - 1)
140
# Most of the time, you will have a sequence of similar entries
141
if last_a_pos+1 != apos or last_b_pos+1 != bpos:
142
recurse_matches(a, b, last_a_pos+1, last_b_pos+1,
143
apos, bpos, answer, maxrecursion - 1)
144
last_a_pos = apos
145
last_b_pos = bpos
141
146
answer.append((apos, bpos))
142
147
if len(answer) > oldlength:
143
148
# find matches between the last match and the end
144
recurse_matches(a, b, ahi, bhi, answer, maxrecursion - 1)
149
recurse_matches(a, b, last_a_pos+1, last_b_pos+1,
150
ahi, bhi, answer, maxrecursion - 1)
145
151
elif a[alo] == b[blo]:
146
152
# find matching lines at the very beginning
147
153
while alo < ahi and blo < bhi and a[alo] == b[blo]:
148
154
answer.append((alo, blo))
149
155
alo += 1
150
156
blo += 1
151
recurse_matches(a, b, ahi, bhi, answer, maxrecursion - 1)
157
recurse_matches(a, b, alo, blo,
158
ahi, bhi, answer, maxrecursion - 1)
152
159
elif a[ahi - 1] == b[bhi - 1]:
153
160
# find matching lines at the very end
154
161
nahi = ahi - 1
156
163
while nahi > alo and nbhi > blo and a[nahi - 1] == b[nbhi - 1]:
157
164
nahi -= 1
158
165
nbhi -= 1
159
recurse_matches(a, b, nahi, nbhi, answer, maxrecursion - 1)
166
recurse_matches(a, b, last_a_pos+1, last_b_pos+1,
167
nahi, nbhi, answer, maxrecursion - 1)
160
168
for i in xrange(ahi - nahi):
161
169
answer.append((nahi + i, nbhi + i))
162
170
163
171
164
class SequenceMatcher(difflib.SequenceMatcher):
172
def _collapse_sequences(matches):
173
"""Find sequences of lines.
174
175
Given a sequence of [(line_in_a, line_in_b),]
176
find regions where they both increment at the same time
177
"""
178
answer = []
179
start_a = start_b = None
180
length = 0
181
for i_a, i_b in matches:
182
if (start_a is not None
183
and (i_a == start_a + length)
184
and (i_b == start_b + length)):
185
length += 1
186
else:
187
if start_a is not None:
188
answer.append((start_a, start_b, length))
189
start_a = i_a
190
start_b = i_b
191
length = 1
192
193
if length != 0:
194
answer.append((start_a, start_b, length))
195
196
return answer
197
198
199
def _check_consistency(answer):
200
# For consistency sake, make sure all matches are only increasing
201
next_a = -1
202
next_b = -1
203
for a,b,match_len in answer:
204
assert a >= next_a, 'Non increasing matches for a'
205
assert b >= next_b, 'Not increasing matches for b'
206
next_a = a + match_len
207
next_b = b + match_len
208
209
210
class PatienceSequenceMatcher(difflib.SequenceMatcher):
165
211
"""Compare a pair of sequences using longest common subset."""
166
212
213
_do_check_consistency = True
214
167
215
def __init__(self, isjunk=None, a='', b=''):
168
216
if isjunk is not None:
169
217
raise NotImplementedError('Currently we do not support'
170
218
' isjunk for sequence matching')
171
219
difflib.SequenceMatcher.__init__(self, isjunk, a, b)
172
220
173
def _check_with_diff(self, alo, ahi, blo, bhi, answer):
174
"""Use the original diff algorithm on an unmatched section.
175
176
This will check to make sure the range is worth checking,
177
before doing any work.
178
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
184
:return: None
221
def get_matching_blocks(self):
222
"""Return list of triples describing matching subsequences.
223
224
Each triple is of the form (i, j, n), and means that
225
a[i:i+n] == b[j:j+n]. The triples are monotonically increasing in
226
i and in j.
227
228
The last triple is a dummy, (len(a), len(b), 0), and is the only
229
triple with n==0.
230
231
>>> s = PatienceSequenceMatcher(None, "abxcd", "abcd")
232
>>> s.get_matching_blocks()
233
[(0, 0, 2), (3, 2, 2), (5, 4, 0)]
185
234
"""
186
# WORKAROUND
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.
192
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
202
new_blocks.pop()
203
for blk in new_blocks:
204
answer.append((blk[0]+alo+1,
205
blk[1]+blo+1,
206
blk[2]))
207
208
def __helper(self, alo, ahi, blo, bhi, answer):
235
# jam 20060525 This is the python 2.4.1 difflib get_matching_blocks
236
# implementation which uses __helper. 2.4.3 got rid of helper for
237
# doing it inline with a queue.
238
# We should consider doing the same for recurse_matches
239
240
if self.matching_blocks is not None:
241
return self.matching_blocks
242
209
243
matches = []
210
a = self.a[alo:ahi]
211
b = self.b[blo:bhi]
212
recurse_matches(a, b, len(a), len(b), matches, 10)
244
recurse_matches(self.a, self.b, 0, 0,
245
len(self.a), len(self.b), matches, 10)
213
246
# Matches now has individual line pairs of
214
247
# line A matches line B, at the given offsets
215
216
start_a = start_b = None
217
length = 0
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)):
222
length += 1
223
else:
224
# New block
225
if start_a is None:
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,
228
answer)
229
else:
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,
233
answer)
234
235
start_a = i_a
236
start_b = i_b
237
length = 1
238
239
if length != 0:
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,
243
answer)
244
if not matches:
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)
247
248
# For consistency sake, make sure all matches are only increasing
249
if __debug__:
250
next_a = -1
251
next_b = -1
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
248
self.matching_blocks = _collapse_sequences(matches)
249
self.matching_blocks.append( (len(self.a), len(self.b), 0) )
250
if PatienceSequenceMatcher._do_check_consistency:
251
if __debug__:
252
_check_consistency(self.matching_blocks)
253
254
return self.matching_blocks
257
255
258
256
259
257
# This is a version of unified_diff which only adds a factory parameter
354
352
import optparse
355
353
p = optparse.OptionParser(usage='%prog [options] file_a file_b'
356
354
'\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')
355
p.add_option('--patience', dest='matcher', action='store_const', const='patience',
356
default='patience', help='Use the patience difference algorithm')
359
357
p.add_option('--difflib', dest='matcher', action='store_const', const='difflib',
360
default='cdv', help='Use python\'s difflib algorithm')
358
default='patience', help='Use python\'s difflib algorithm')
361
359
362
algorithms = {'cdv':SequenceMatcher, 'difflib':difflib.SequenceMatcher}
360
algorithms = {'patience':PatienceSequenceMatcher, 'difflib':difflib.SequenceMatcher}
363
361
364
362
(opts, args) = p.parse_args(args)
365
363
matcher = algorithms[opts.matcher]
Loggerhead is a web-based interface for Breezy
Version: 2.0.1