~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/patiencediff.py

  • Committer: Wouter van Heyst
  • Date: 2006-06-07 17:23:59 UTC
  • mto: This revision was merged to the branch mainline in revision 1752.
  • Revision ID: larstiq@larstiq.dyndns.org-20060607172359-6023dec74344453d
more code cleanup

Show diffs side-by-side

added added

removed removed

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