← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/patiencediff.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2007-03-27 08:18:02 UTC
  • mfrom: (2378.1.1 integration)
  • Revision ID: pqm@pqm.ubuntu.com-20070327081802-271be0d343108f4f
(robertc) Merge bzrlib.strace module which adds support for stracing individual callables from within bzrlib.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/patiencediff.py
13
13
#
14
14
# You should have received a copy of the GNU General Public License
15
15
# along with this program; if not, write to the Free Software
16
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
16
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
17
17
 
18
 
from __future__ import absolute_import
19
18
 
20
19
from bisect import bisect
21
20
import difflib
 
21
import os
 
22
import sys
 
23
import time
22
24
 
23
25
from bzrlib.trace import mutter
24
26
 
26
28
__all__ = ['PatienceSequenceMatcher', 'unified_diff', 'unified_diff_files']
27
29
 
28
30
 
29
 
def unique_lcs_py(a, b):
 
31
def unique_lcs(a, b):
30
32
    """Find the longest common subset for unique lines.
31
33
 
32
34
    :param a: An indexable object (such as string or list of strings)
50
52
        else:
51
53
            index[line]= i
52
54
    # make btoa[i] = position of line i in a, unless
53
 
    # that line doesn't occur exactly once in both,
 
55
    # that line doesn't occur exactly once in both, 
54
56
    # in which case it's set to None
55
57
    btoa = [None] * len(b)
56
58
    index2 = {}
80
82
            k = len(stacks)
81
83
        # as an optimization, check if the next line comes right after
82
84
        # the previous line, because usually it does
83
 
        elif stacks and stacks[k] < apos and (k == len(stacks) - 1 or
 
85
        elif stacks and stacks[k] < apos and (k == len(stacks) - 1 or 
84
86
                                              stacks[k+1] > apos):
85
87
            k += 1
86
88
        else:
104
106
    return result
105
107
 
106
108
 
107
 
def recurse_matches_py(a, b, alo, blo, ahi, bhi, answer, maxrecursion):
 
109
def recurse_matches(a, b, alo, blo, ahi, bhi, answer, maxrecursion):
108
110
    """Find all of the matching text in the lines of a and b.
109
111
 
110
112
    :param a: A sequence
130
132
        return
131
133
    last_a_pos = alo-1
132
134
    last_b_pos = blo-1
133
 
    for apos, bpos in unique_lcs_py(a[alo:ahi], b[blo:bhi]):
 
135
    for apos, bpos in unique_lcs(a[alo:ahi], b[blo:bhi]):
134
136
        # recurse between lines which are unique in each file and match
135
137
        apos += alo
136
138
        bpos += blo
137
139
        # Most of the time, you will have a sequence of similar entries
138
140
        if last_a_pos+1 != apos or last_b_pos+1 != bpos:
139
 
            recurse_matches_py(a, b, last_a_pos+1, last_b_pos+1,
 
141
            recurse_matches(a, b, last_a_pos+1, last_b_pos+1,
140
142
                apos, bpos, answer, maxrecursion - 1)
141
143
        last_a_pos = apos
142
144
        last_b_pos = bpos
143
145
        answer.append((apos, bpos))
144
146
    if len(answer) > oldlength:
145
147
        # find matches between the last match and the end
146
 
        recurse_matches_py(a, b, last_a_pos+1, last_b_pos+1,
147
 
                           ahi, bhi, answer, maxrecursion - 1)
 
148
        recurse_matches(a, b, last_a_pos+1, last_b_pos+1,
 
149
                        ahi, bhi, answer, maxrecursion - 1)
148
150
    elif a[alo] == b[blo]:
149
151
        # find matching lines at the very beginning
150
152
        while alo < ahi and blo < bhi and a[alo] == b[blo]:
151
153
            answer.append((alo, blo))
152
154
            alo += 1
153
155
            blo += 1
154
 
        recurse_matches_py(a, b, alo, blo,
155
 
                           ahi, bhi, answer, maxrecursion - 1)
 
156
        recurse_matches(a, b, alo, blo,
 
157
                        ahi, bhi, answer, maxrecursion - 1)
156
158
    elif a[ahi - 1] == b[bhi - 1]:
157
159
        # find matching lines at the very end
158
160
        nahi = ahi - 1
160
162
        while nahi > alo and nbhi > blo and a[nahi - 1] == b[nbhi - 1]:
161
163
            nahi -= 1
162
164
            nbhi -= 1
163
 
        recurse_matches_py(a, b, last_a_pos+1, last_b_pos+1,
164
 
                           nahi, nbhi, answer, maxrecursion - 1)
 
165
        recurse_matches(a, b, last_a_pos+1, last_b_pos+1,
 
166
                        nahi, nbhi, answer, maxrecursion - 1)
165
167
        for i in xrange(ahi - nahi):
166
168
            answer.append((nahi + i, nbhi + i))
167
169
 
177
179
    length = 0
178
180
    for i_a, i_b in matches:
179
181
        if (start_a is not None
180
 
            and (i_a == start_a + length)
 
182
            and (i_a == start_a + length) 
181
183
            and (i_b == start_b + length)):
182
184
            length += 1
183
185
        else:
197
199
    # For consistency sake, make sure all matches are only increasing
198
200
    next_a = -1
199
201
    next_b = -1
200
 
    for (a, b, match_len) in answer:
201
 
        if a < next_a:
202
 
            raise ValueError('Non increasing matches for a')
203
 
        if b < next_b:
204
 
            raise ValueError('Non increasing matches for b')
 
202
    for a,b,match_len in answer:
 
203
        assert a >= next_a, 'Non increasing matches for a'
 
204
        assert b >= next_b, 'Not increasing matches for b'
205
205
        next_a = a + match_len
206
206
        next_b = b + match_len
207
207
 
208
208
 
209
 
class PatienceSequenceMatcher_py(difflib.SequenceMatcher):
 
209
class PatienceSequenceMatcher(difflib.SequenceMatcher):
210
210
    """Compare a pair of sequences using longest common subset."""
211
211
 
212
212
    _do_check_consistency = True
231
231
        >>> s.get_matching_blocks()
232
232
        [(0, 0, 2), (3, 2, 2), (5, 4, 0)]
233
233
        """
234
 
        # jam 20060525 This is the python 2.4.1 difflib get_matching_blocks
 
234
        # jam 20060525 This is the python 2.4.1 difflib get_matching_blocks 
235
235
        # implementation which uses __helper. 2.4.3 got rid of helper for
236
236
        # doing it inline with a queue.
237
237
        # We should consider doing the same for recurse_matches
240
240
            return self.matching_blocks
241
241
 
242
242
        matches = []
243
 
        recurse_matches_py(self.a, self.b, 0, 0,
244
 
                           len(self.a), len(self.b), matches, 10)
 
243
        recurse_matches(self.a, self.b, 0, 0,
 
244
                        len(self.a), len(self.b), matches, 10)
245
245
        # Matches now has individual line pairs of
246
246
        # line A matches line B, at the given offsets
247
247
        self.matching_blocks = _collapse_sequences(matches)
248
248
        self.matching_blocks.append( (len(self.a), len(self.b), 0) )
249
 
        if PatienceSequenceMatcher_py._do_check_consistency:
 
249
        if PatienceSequenceMatcher._do_check_consistency:
250
250
            if __debug__:
251
251
                _check_consistency(self.matching_blocks)
252
252
 
253
253
        return self.matching_blocks
 
254
 
 
255
 
 
256
# This is a version of unified_diff which only adds a factory parameter
 
257
# so that you can override the default SequenceMatcher
 
258
# this has been submitted as a patch to python
 
259
def unified_diff(a, b, fromfile='', tofile='', fromfiledate='',
 
260
                 tofiledate='', n=3, lineterm='\n',
 
261
                 sequencematcher=None):
 
262
    r"""
 
263
    Compare two sequences of lines; generate the delta as a unified diff.
 
264
 
 
265
    Unified diffs are a compact way of showing line changes and a few
 
266
    lines of context.  The number of context lines is set by 'n' which
 
267
    defaults to three.
 
268
 
 
269
    By default, the diff control lines (those with ---, +++, or @@) are
 
270
    created with a trailing newline.  This is helpful so that inputs
 
271
    created from file.readlines() result in diffs that are suitable for
 
272
    file.writelines() since both the inputs and outputs have trailing
 
273
    newlines.
 
274
 
 
275
    For inputs that do not have trailing newlines, set the lineterm
 
276
    argument to "" so that the output will be uniformly newline free.
 
277
 
 
278
    The unidiff format normally has a header for filenames and modification
 
279
    times.  Any or all of these may be specified using strings for
 
280
    'fromfile', 'tofile', 'fromfiledate', and 'tofiledate'.  The modification
 
281
    times are normally expressed in the format returned by time.ctime().
 
282
 
 
283
    Example:
 
284
 
 
285
    >>> for line in unified_diff('one two three four'.split(),
 
286
    ...             'zero one tree four'.split(), 'Original', 'Current',
 
287
    ...             'Sat Jan 26 23:30:50 1991', 'Fri Jun 06 10:20:52 2003',
 
288
    ...             lineterm=''):
 
289
    ...     print line
 
290
    --- Original Sat Jan 26 23:30:50 1991
 
291
    +++ Current Fri Jun 06 10:20:52 2003
 
292
    @@ -1,4 +1,4 @@
 
293
    +zero
 
294
     one
 
295
    -two
 
296
    -three
 
297
    +tree
 
298
     four
 
299
    """
 
300
    if sequencematcher is None:
 
301
        sequencematcher = difflib.SequenceMatcher
 
302
 
 
303
    started = False
 
304
    for group in sequencematcher(None,a,b).get_grouped_opcodes(n):
 
305
        if not started:
 
306
            yield '--- %s %s%s' % (fromfile, fromfiledate, lineterm)
 
307
            yield '+++ %s %s%s' % (tofile, tofiledate, lineterm)
 
308
            started = True
 
309
        i1, i2, j1, j2 = group[0][1], group[-1][2], group[0][3], group[-1][4]
 
310
        yield "@@ -%d,%d +%d,%d @@%s" % (i1+1, i2-i1, j1+1, j2-j1, lineterm)
 
311
        for tag, i1, i2, j1, j2 in group:
 
312
            if tag == 'equal':
 
313
                for line in a[i1:i2]:
 
314
                    yield ' ' + line
 
315
                continue
 
316
            if tag == 'replace' or tag == 'delete':
 
317
                for line in a[i1:i2]:
 
318
                    yield '-' + line
 
319
            if tag == 'replace' or tag == 'insert':
 
320
                for line in b[j1:j2]:
 
321
                    yield '+' + line
 
322
 
 
323
 
 
324
def unified_diff_files(a, b, sequencematcher=None):
 
325
    """Generate the diff for two files.
 
326
    """
 
327
    # Should this actually be an error?
 
328
    if a == b:
 
329
        return []
 
330
    if a == '-':
 
331
        file_a = sys.stdin
 
332
        time_a = time.time()
 
333
    else:
 
334
        file_a = open(a, 'rb')
 
335
        time_a = os.stat(a).st_mtime
 
336
 
 
337
    if b == '-':
 
338
        file_b = sys.stdin
 
339
        time_b = time.time()
 
340
    else:
 
341
        file_b = open(b, 'rb')
 
342
        time_b = os.stat(b).st_mtime
 
343
 
 
344
    # TODO: Include fromfiledate and tofiledate
 
345
    return unified_diff(file_a.readlines(), file_b.readlines(),
 
346
                        fromfile=a, tofile=b,
 
347
                        sequencematcher=sequencematcher)
 
348
 
 
349
 
 
350
def main(args):
 
351
    import optparse
 
352
    p = optparse.OptionParser(usage='%prog [options] file_a file_b'
 
353
                                    '\nFiles can be "-" to read from stdin')
 
354
    p.add_option('--patience', dest='matcher', action='store_const', const='patience',
 
355
                 default='patience', help='Use the patience difference algorithm')
 
356
    p.add_option('--difflib', dest='matcher', action='store_const', const='difflib',
 
357
                 default='patience', help='Use python\'s difflib algorithm')
 
358
 
 
359
    algorithms = {'patience':PatienceSequenceMatcher, 'difflib':difflib.SequenceMatcher}
 
360
 
 
361
    (opts, args) = p.parse_args(args)
 
362
    matcher = algorithms[opts.matcher]
 
363
 
 
364
    if len(args) != 2:
 
365
        print 'You must supply 2 filenames to diff'
 
366
        return -1
 
367
 
 
368
    for line in unified_diff_files(args[0], args[1], sequencematcher=matcher):
 
369
        sys.stdout.write(line)
 
370
    
 
371
if __name__ == '__main__':
 
372
    sys.exit(main(sys.argv[1:]))