← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge3.py

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2007-03-28 06:58:22 UTC
  • mfrom: (2379.2.3 hpss-chroot)
  • Revision ID: pqm@pqm.ubuntu.com-20070328065822-999550a858a3ced3
(robertc) Fix chroot urls to not expose the url of the transport they are protecting, allowing regular url operations to work on them. (Robert Collins, Andrew Bennetts)

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