/brz/remove-bazaar

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/brz/remove-bazaar

« back to all changes in this revision

Viewing changes to bzrlib/merge3.py

  • Committer: wang
  • Date: 2006-10-29 13:41:32 UTC
  • mto: (2104.4.1 wang_65714)
  • mto: This revision was merged to the branch mainline in revision 2109.
  • Revision ID: wang@ubuntu-20061029134132-3d7f4216f20c4aef
Replace python's difflib by patiencediff because the worst case 
performance is cubic for difflib and people commiting large data 
files are often hurt by this. The worst case performance of patience is 
quadratic. Fix bug 65714.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge3.py
1
 
# Copyright (C) 2005-2010 Canonical Ltd
 
1
# Copyright (C) 2004, 2005 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
12
12
#
13
13
# You should have received a copy of the GNU General Public License
14
14
# along with this program; if not, write to the Free Software
15
 
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
15
# Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
16
16
 
17
17
 
18
18
# mbp: "you know that thing where cvs gives you conflict markers?"
19
19
# s: "i hate that."
20
20
 
21
 
from bzrlib import (
22
 
    errors,
23
 
    patiencediff,
24
 
    textfile,
25
 
    )
 
21
 
 
22
from bzrlib.errors import CantReprocessAndShowBase
 
23
import bzrlib.patiencediff
 
24
from bzrlib.textfile import check_text_lines
26
25
 
27
26
 
28
27
def intersect(ra, rb):
37
36
    >>> intersect((0, 9), (7, 15))
38
37
    (7, 9)
39
38
    """
40
 
    # preconditions: (ra[0] <= ra[1]) and (rb[0] <= rb[1])
41
 
 
 
39
    assert ra[0] <= ra[1]
 
40
    assert rb[0] <= rb[1]
 
41
    
42
42
    sa = max(ra[0], rb[0])
43
43
    sb = min(ra[1], rb[1])
44
44
    if sa < sb:
57
57
            return False
58
58
    else:
59
59
        return True
60
 
 
 
60
        
61
61
 
62
62
 
63
63
 
67
67
    Given BASE, OTHER, THIS, tries to produce a combined text
68
68
    incorporating the changes from both BASE->OTHER and BASE->THIS.
69
69
    All three will typically be sequences of lines."""
70
 
 
71
 
    def __init__(self, base, a, b, is_cherrypick=False, allow_objects=False):
72
 
        """Constructor.
73
 
 
74
 
        :param base: lines in BASE
75
 
        :param a: lines in A
76
 
        :param b: lines in B
77
 
        :param is_cherrypick: flag indicating if this merge is a cherrypick.
78
 
            When cherrypicking b => a, matches with b and base do not conflict.
79
 
        :param allow_objects: if True, do not require that base, a and b are
80
 
            plain Python strs.  Also prevents BinaryFile from being raised.
81
 
            Lines can be any sequence of comparable and hashable Python
82
 
            objects.
83
 
        """
84
 
        if not allow_objects:
85
 
            textfile.check_text_lines(base)
86
 
            textfile.check_text_lines(a)
87
 
            textfile.check_text_lines(b)
 
70
    def __init__(self, base, a, b):
 
71
        check_text_lines(base)
 
72
        check_text_lines(a)
 
73
        check_text_lines(b)
88
74
        self.base = base
89
75
        self.a = a
90
76
        self.b = b
91
 
        self.is_cherrypick = is_cherrypick
 
77
 
 
78
 
92
79
 
93
80
    def merge_lines(self,
94
81
                    name_a=None,
101
88
                    reprocess=False):
102
89
        """Return merge in cvs-like form.
103
90
        """
104
 
        newline = '\n'
105
 
        if len(self.a) > 0:
106
 
            if self.a[0].endswith('\r\n'):
107
 
                newline = '\r\n'
108
 
            elif self.a[0].endswith('\r'):
109
 
                newline = '\r'
110
91
        if base_marker and reprocess:
111
 
            raise errors.CantReprocessAndShowBase()
 
92
            raise CantReprocessAndShowBase()
112
93
        if name_a:
113
94
            start_marker = start_marker + ' ' + name_a
114
95
        if name_b:
130
111
                for i in range(t[1], t[2]):
131
112
                    yield self.b[i]
132
113
            elif what == 'conflict':
133
 
                yield start_marker + newline
 
114
                yield start_marker + '\n'
134
115
                for i in range(t[3], t[4]):
135
116
                    yield self.a[i]
136
117
                if base_marker is not None:
137
 
                    yield base_marker + newline
 
118
                    yield base_marker + '\n'
138
119
                    for i in range(t[1], t[2]):
139
120
                        yield self.base[i]
140
 
                yield mid_marker + newline
 
121
                yield mid_marker + '\n'
141
122
                for i in range(t[5], t[6]):
142
123
                    yield self.b[i]
143
 
                yield end_marker + newline
 
124
                yield end_marker + '\n'
144
125
            else:
145
126
                raise ValueError(what)
 
127
        
 
128
        
 
129
 
 
130
 
146
131
 
147
132
    def merge_annotated(self):
148
133
        """Return merge with conflicts, showing origin of lines.
149
134
 
150
 
        Most useful for debugging merge.
 
135
        Most useful for debugging merge.        
151
136
        """
152
137
        for t in self.merge_regions():
153
138
            what = t[0]
170
155
                yield '>>>>\n'
171
156
            else:
172
157
                raise ValueError(what)
 
158
        
 
159
        
 
160
 
 
161
 
173
162
 
174
163
    def merge_groups(self):
175
164
        """Yield sequence of line groups.  Each one is a tuple:
205
194
            else:
206
195
                raise ValueError(what)
207
196
 
 
197
 
208
198
    def merge_regions(self):
209
199
        """Return sequences of matching and conflicting regions.
210
200
 
234
224
 
235
225
        # section a[0:ia] has been disposed of, etc
236
226
        iz = ia = ib = 0
237
 
 
 
227
        
238
228
        for zmatch, zend, amatch, aend, bmatch, bend in self.find_sync_regions():
 
229
            #print 'match base [%d:%d]' % (zmatch, zend)
 
230
            
239
231
            matchlen = zend - zmatch
240
 
            # invariants:
241
 
            #   matchlen >= 0
242
 
            #   matchlen == (aend - amatch)
243
 
            #   matchlen == (bend - bmatch)
 
232
            assert matchlen >= 0
 
233
            assert matchlen == (aend - amatch)
 
234
            assert matchlen == (bend - bmatch)
 
235
            
244
236
            len_a = amatch - ia
245
237
            len_b = bmatch - ib
246
238
            len_base = zmatch - iz
247
 
            # invariants:
248
 
            # assert len_a >= 0
249
 
            # assert len_b >= 0
250
 
            # assert len_base >= 0
 
239
            assert len_a >= 0
 
240
            assert len_b >= 0
 
241
            assert len_base >= 0
251
242
 
252
243
            #print 'unmatched a=%d, b=%d' % (len_a, len_b)
253
244
 
254
245
            if len_a or len_b:
255
246
                # try to avoid actually slicing the lists
 
247
                equal_a = compare_range(self.a, ia, amatch,
 
248
                                        self.base, iz, zmatch)
 
249
                equal_b = compare_range(self.b, ib, bmatch,
 
250
                                        self.base, iz, zmatch)
256
251
                same = compare_range(self.a, ia, amatch,
257
252
                                     self.b, ib, bmatch)
258
253
 
259
254
                if same:
260
255
                    yield 'same', ia, amatch
 
256
                elif equal_a and not equal_b:
 
257
                    yield 'b', ib, bmatch
 
258
                elif equal_b and not equal_a:
 
259
                    yield 'a', ia, amatch
 
260
                elif not equal_a and not equal_b:
 
261
                    yield 'conflict', iz, zmatch, ia, amatch, ib, bmatch
261
262
                else:
262
 
                    equal_a = compare_range(self.a, ia, amatch,
263
 
                                            self.base, iz, zmatch)
264
 
                    equal_b = compare_range(self.b, ib, bmatch,
265
 
                                            self.base, iz, zmatch)
266
 
                    if equal_a and not equal_b:
267
 
                        yield 'b', ib, bmatch
268
 
                    elif equal_b and not equal_a:
269
 
                        yield 'a', ia, amatch
270
 
                    elif not equal_a and not equal_b:
271
 
                        if self.is_cherrypick:
272
 
                            for node in self._refine_cherrypick_conflict(
273
 
                                                    iz, zmatch, ia, amatch,
274
 
                                                    ib, bmatch):
275
 
                                yield node
276
 
                        else:
277
 
                            yield 'conflict', iz, zmatch, ia, amatch, ib, bmatch
278
 
                    else:
279
 
                        raise AssertionError("can't handle a=b=base but unmatched")
 
263
                    raise AssertionError("can't handle a=b=base but unmatched")
280
264
 
281
265
                ia = amatch
282
266
                ib = bmatch
285
269
            # if the same part of the base was deleted on both sides
286
270
            # that's OK, we can just skip it.
287
271
 
 
272
                
288
273
            if matchlen > 0:
289
 
                # invariants:
290
 
                # assert ia == amatch
291
 
                # assert ib == bmatch
292
 
                # assert iz == zmatch
293
 
 
 
274
                assert ia == amatch
 
275
                assert ib == bmatch
 
276
                assert iz == zmatch
 
277
                
294
278
                yield 'unchanged', zmatch, zend
295
279
                iz = zend
296
280
                ia = aend
297
281
                ib = bend
298
 
 
299
 
    def _refine_cherrypick_conflict(self, zstart, zend, astart, aend, bstart, bend):
300
 
        """When cherrypicking b => a, ignore matches with b and base."""
301
 
        # Do not emit regions which match, only regions which do not match
302
 
        matches = patiencediff.PatienceSequenceMatcher(None,
303
 
            self.base[zstart:zend], self.b[bstart:bend]).get_matching_blocks()
304
 
        last_base_idx = 0
305
 
        last_b_idx = 0
306
 
        last_b_idx = 0
307
 
        yielded_a = False
308
 
        for base_idx, b_idx, match_len in matches:
309
 
            conflict_z_len = base_idx - last_base_idx
310
 
            conflict_b_len = b_idx - last_b_idx
311
 
            if conflict_b_len == 0: # There are no lines in b which conflict,
312
 
                                    # so skip it
313
 
                pass
314
 
            else:
315
 
                if yielded_a:
316
 
                    yield ('conflict',
317
 
                           zstart + last_base_idx, zstart + base_idx,
318
 
                           aend, aend, bstart + last_b_idx, bstart + b_idx)
319
 
                else:
320
 
                    # The first conflict gets the a-range
321
 
                    yielded_a = True
322
 
                    yield ('conflict', zstart + last_base_idx, zstart +
323
 
                    base_idx,
324
 
                           astart, aend, bstart + last_b_idx, bstart + b_idx)
325
 
            last_base_idx = base_idx + match_len
326
 
            last_b_idx = b_idx + match_len
327
 
        if last_base_idx != zend - zstart or last_b_idx != bend - bstart:
328
 
            if yielded_a:
329
 
                yield ('conflict', zstart + last_base_idx, zstart + base_idx,
330
 
                       aend, aend, bstart + last_b_idx, bstart + b_idx)
331
 
            else:
332
 
                # The first conflict gets the a-range
333
 
                yielded_a = True
334
 
                yield ('conflict', zstart + last_base_idx, zstart + base_idx,
335
 
                       astart, aend, bstart + last_b_idx, bstart + b_idx)
336
 
        if not yielded_a:
337
 
            yield ('conflict', zstart, zend, astart, aend, bstart, bend)
 
282
    
338
283
 
339
284
    def reprocess_merge_regions(self, merge_regions):
340
285
        """Where there are conflict regions, remove the agreed lines.
341
286
 
342
 
        Lines where both A and B have made the same changes are
 
287
        Lines where both A and B have made the same changes are 
343
288
        eliminated.
344
289
        """
345
290
        for region in merge_regions:
349
294
            type, iz, zmatch, ia, amatch, ib, bmatch = region
350
295
            a_region = self.a[ia:amatch]
351
296
            b_region = self.b[ib:bmatch]
352
 
            matches = patiencediff.PatienceSequenceMatcher(
 
297
            matches = bzrlib.patiencediff.PatienceSequenceMatcher(
353
298
                    None, a_region, b_region).get_matching_blocks()
354
299
            next_a = ia
355
300
            next_b = ib
367
312
            if reg is not None:
368
313
                yield reg
369
314
 
 
315
 
370
316
    @staticmethod
371
317
    def mismatch_region(next_a, region_ia,  next_b, region_ib):
372
318
        if next_a < region_ia or next_b < region_ib:
373
319
            return 'conflict', None, None, next_a, region_ia, next_b, region_ib
 
320
            
374
321
 
375
322
    def find_sync_regions(self):
376
323
        """Return a list of sync regions, where both descendents match the base.
380
327
        """
381
328
 
382
329
        ia = ib = 0
383
 
        amatches = patiencediff.PatienceSequenceMatcher(
 
330
        amatches = bzrlib.patiencediff.PatienceSequenceMatcher(
384
331
                None, self.base, self.a).get_matching_blocks()
385
 
        bmatches = patiencediff.PatienceSequenceMatcher(
 
332
        bmatches = bzrlib.patiencediff.PatienceSequenceMatcher(
386
333
                None, self.base, self.b).get_matching_blocks()
387
334
        len_a = len(amatches)
388
335
        len_b = len(bmatches)
403
350
 
404
351
                # found a match of base[i[0], i[1]]; this may be less than
405
352
                # the region that matches in either one
406
 
                # assert intlen <= alen
407
 
                # assert intlen <= blen
408
 
                # assert abase <= intbase
409
 
                # assert bbase <= intbase
 
353
                assert intlen <= alen
 
354
                assert intlen <= blen
 
355
                assert abase <= intbase
 
356
                assert bbase <= intbase
410
357
 
411
358
                asub = amatch + (intbase - abase)
412
359
                bsub = bmatch + (intbase - bbase)
413
360
                aend = asub + intlen
414
361
                bend = bsub + intlen
415
362
 
416
 
                # assert self.base[intbase:intend] == self.a[asub:aend], \
417
 
                #       (self.base[intbase:intend], self.a[asub:aend])
418
 
                # assert self.base[intbase:intend] == self.b[bsub:bend]
 
363
                assert self.base[intbase:intend] == self.a[asub:aend], \
 
364
                       (self.base[intbase:intend], self.a[asub:aend])
 
365
 
 
366
                assert self.base[intbase:intend] == self.b[bsub:bend]
419
367
 
420
368
                sl.append((intbase, intend,
421
369
                           asub, aend,
422
370
                           bsub, bend))
 
371
 
423
372
            # advance whichever one ends first in the base text
424
373
            if (abase + alen) < (bbase + blen):
425
374
                ia += 1
426
375
            else:
427
376
                ib += 1
428
 
 
 
377
            
429
378
        intbase = len(self.base)
430
379
        abase = len(self.a)
431
380
        bbase = len(self.b)
433
382
 
434
383
        return sl
435
384
 
 
385
 
 
386
 
436
387
    def find_unconflicted(self):
437
388
        """Return a list of ranges in base that are not conflicted."""
438
 
        am = patiencediff.PatienceSequenceMatcher(
 
389
        am = bzrlib.patiencediff.PatienceSequenceMatcher(
439
390
                None, self.base, self.a).get_matching_blocks()
440
 
        bm = patiencediff.PatienceSequenceMatcher(
 
391
        bm = bzrlib.patiencediff.PatienceSequenceMatcher(
441
392
                None, self.base, self.b).get_matching_blocks()
442
393
 
443
394
        unc = []
457
408
                del am[0]
458
409
            else:
459
410
                del bm[0]
460
 
 
 
411
                
461
412
        return unc
462
413
 
463
414