← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/patiencediff.py

  • Committer: Alexander Belchenko
  • Date: 2006-07-30 16:43:12 UTC
  • mto: (1711.2.111 jam-integration)
  • mto: This revision was merged to the branch mainline in revision 1906.
  • Revision ID: bialix@ukr.net-20060730164312-b025fd3ff0cee59e
rename  gpl.txt => COPYING.txt

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
18
 
19
19
from bisect import bisect
20
20
import difflib
 
21
import os
 
22
import sys
 
23
import time
21
24
 
22
25
from bzrlib.trace import mutter
23
26
 
25
28
__all__ = ['PatienceSequenceMatcher', 'unified_diff', 'unified_diff_files']
26
29
 
27
30
 
28
 
def unique_lcs_py(a, b):
 
31
def unique_lcs(a, b):
29
32
    """Find the longest common subset for unique lines.
30
33
 
31
34
    :param a: An indexable object (such as string or list of strings)
40
43
    http://en.wikipedia.org/wiki/Patience_sorting
41
44
    """
42
45
    # set index[line in a] = position of line in a unless
43
 
    # a is a duplicate, in which case it's set to None
 
46
    # unless a is a duplicate, in which case it's set to None
44
47
    index = {}
45
48
    for i in xrange(len(a)):
46
49
        line = a[i]
49
52
        else:
50
53
            index[line]= i
51
54
    # make btoa[i] = position of line i in a, unless
52
 
    # that line doesn't occur exactly once in both,
 
55
    # that line doesn't occur exactly once in both, 
53
56
    # in which case it's set to None
54
57
    btoa = [None] * len(b)
55
58
    index2 = {}
79
82
            k = len(stacks)
80
83
        # as an optimization, check if the next line comes right after
81
84
        # the previous line, because usually it does
82
 
        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 
83
86
                                              stacks[k+1] > apos):
84
87
            k += 1
85
88
        else:
103
106
    return result
104
107
 
105
108
 
106
 
def recurse_matches_py(a, b, alo, blo, ahi, bhi, answer, maxrecursion):
 
109
def recurse_matches(a, b, alo, blo, ahi, bhi, answer, maxrecursion):
107
110
    """Find all of the matching text in the lines of a and b.
108
111
 
109
112
    :param a: A sequence
129
132
        return
130
133
    last_a_pos = alo-1
131
134
    last_b_pos = blo-1
132
 
    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]):
133
136
        # recurse between lines which are unique in each file and match
134
137
        apos += alo
135
138
        bpos += blo
136
139
        # Most of the time, you will have a sequence of similar entries
137
140
        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,
 
141
            recurse_matches(a, b, last_a_pos+1, last_b_pos+1,
139
142
                apos, bpos, answer, maxrecursion - 1)
140
143
        last_a_pos = apos
141
144
        last_b_pos = bpos
142
145
        answer.append((apos, bpos))
143
146
    if len(answer) > oldlength:
144
147
        # 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)
 
148
        recurse_matches(a, b, last_a_pos+1, last_b_pos+1,
 
149
                        ahi, bhi, answer, maxrecursion - 1)
147
150
    elif a[alo] == b[blo]:
148
151
        # find matching lines at the very beginning
149
152
        while alo < ahi and blo < bhi and a[alo] == b[blo]:
150
153
            answer.append((alo, blo))
151
154
            alo += 1
152
155
            blo += 1
153
 
        recurse_matches_py(a, b, alo, blo,
154
 
                           ahi, bhi, answer, maxrecursion - 1)
 
156
        recurse_matches(a, b, alo, blo,
 
157
                        ahi, bhi, answer, maxrecursion - 1)
155
158
    elif a[ahi - 1] == b[bhi - 1]:
156
159
        # find matching lines at the very end
157
160
        nahi = ahi - 1
159
162
        while nahi > alo and nbhi > blo and a[nahi - 1] == b[nbhi - 1]:
160
163
            nahi -= 1
161
164
            nbhi -= 1
162
 
        recurse_matches_py(a, b, last_a_pos+1, last_b_pos+1,
163
 
                           nahi, nbhi, answer, maxrecursion - 1)
 
165
        recurse_matches(a, b, last_a_pos+1, last_b_pos+1,
 
166
                        nahi, nbhi, answer, maxrecursion - 1)
164
167
        for i in xrange(ahi - nahi):
165
168
            answer.append((nahi + i, nbhi + i))
166
169
 
176
179
    length = 0
177
180
    for i_a, i_b in matches:
178
181
        if (start_a is not None
179
 
            and (i_a == start_a + length)
 
182
            and (i_a == start_a + length) 
180
183
            and (i_b == start_b + length)):
181
184
            length += 1
182
185
        else:
196
199
    # For consistency sake, make sure all matches are only increasing
197
200
    next_a = -1
198
201
    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')
 
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'
204
205
        next_a = a + match_len
205
206
        next_b = b + match_len
206
207
 
207
208
 
208
 
class PatienceSequenceMatcher_py(difflib.SequenceMatcher):
 
209
class PatienceSequenceMatcher(difflib.SequenceMatcher):
209
210
    """Compare a pair of sequences using longest common subset."""
210
211
 
211
212
    _do_check_consistency = True
230
231
        >>> s.get_matching_blocks()
231
232
        [(0, 0, 2), (3, 2, 2), (5, 4, 0)]
232
233
        """
233
 
        # 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 
234
235
        # implementation which uses __helper. 2.4.3 got rid of helper for
235
236
        # doing it inline with a queue.
236
237
        # We should consider doing the same for recurse_matches
239
240
            return self.matching_blocks
240
241
 
241
242
        matches = []
242
 
        recurse_matches_py(self.a, self.b, 0, 0,
243
 
                           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)
244
245
        # Matches now has individual line pairs of
245
246
        # line A matches line B, at the given offsets
246
247
        self.matching_blocks = _collapse_sequences(matches)
247
248
        self.matching_blocks.append( (len(self.a), len(self.b), 0) )
248
 
        if PatienceSequenceMatcher_py._do_check_consistency:
 
249
        if PatienceSequenceMatcher._do_check_consistency:
249
250
            if __debug__:
250
251
                _check_consistency(self.matching_blocks)
251
252
 
252
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:]))