← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/merge3.py

  • Committer: John Arbash Meinel
  • Date: 2010-02-16 16:08:40 UTC
  • mfrom: (4797.2.15 2.1)
  • mto: (4797.2.16 2.1)
  • mto: This revision was merged to the branch mainline in revision 5037.
  • Revision ID: john@arbash-meinel.com-20100216160840-xwbpuu0v89gq8lej
Tags: bzr-2.1.0
bring in the latest 2.1 changes

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge3.py
1
 
# Copyright (C) 2004, 2005 by Canonical Ltd
2
 
 
 
1
# Copyright (C) 2004, 2005 Canonical Ltd
 
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
5
5
# the Free Software Foundation; either version 2 of the License, or
6
6
# (at your option) any later version.
7
 
 
 
7
#
8
8
# This program is distributed in the hope that it will be useful,
9
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
10
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11
11
# GNU General Public License for more details.
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., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
17
17
 
18
18
# mbp: "you know that thing where cvs gives you conflict markers?"
20
20
 
21
21
 
22
22
from bzrlib.errors import CantReprocessAndShowBase
23
 
from bzrlib.patiencediff import SequenceMatcher
 
23
import bzrlib.patiencediff
24
24
from bzrlib.textfile import check_text_lines
25
25
 
 
26
 
26
27
def intersect(ra, rb):
27
28
    """Given two ranges return the range where they intersect or None.
28
29
 
35
36
    >>> intersect((0, 9), (7, 15))
36
37
    (7, 9)
37
38
    """
38
 
    assert ra[0] <= ra[1]
39
 
    assert rb[0] <= rb[1]
40
 
    
 
39
    # preconditions: (ra[0] <= ra[1]) and (rb[0] <= rb[1])
 
40
 
41
41
    sa = max(ra[0], rb[0])
42
42
    sb = min(ra[1], rb[1])
43
43
    if sa < sb:
56
56
            return False
57
57
    else:
58
58
        return True
59
 
        
 
59
 
60
60
 
61
61
 
62
62
 
66
66
    Given BASE, OTHER, THIS, tries to produce a combined text
67
67
    incorporating the changes from both BASE->OTHER and BASE->THIS.
68
68
    All three will typically be sequences of lines."""
69
 
    def __init__(self, base, a, b):
 
69
    def __init__(self, base, a, b, is_cherrypick=False):
70
70
        check_text_lines(base)
71
71
        check_text_lines(a)
72
72
        check_text_lines(b)
73
73
        self.base = base
74
74
        self.a = a
75
75
        self.b = b
76
 
 
77
 
 
 
76
        self.is_cherrypick = is_cherrypick
78
77
 
79
78
    def merge_lines(self,
80
79
                    name_a=None,
87
86
                    reprocess=False):
88
87
        """Return merge in cvs-like form.
89
88
        """
 
89
        newline = '\n'
 
90
        if len(self.a) > 0:
 
91
            if self.a[0].endswith('\r\n'):
 
92
                newline = '\r\n'
 
93
            elif self.a[0].endswith('\r'):
 
94
                newline = '\r'
90
95
        if base_marker and reprocess:
91
96
            raise CantReprocessAndShowBase()
92
97
        if name_a:
110
115
                for i in range(t[1], t[2]):
111
116
                    yield self.b[i]
112
117
            elif what == 'conflict':
113
 
                yield start_marker + '\n'
 
118
                yield start_marker + newline
114
119
                for i in range(t[3], t[4]):
115
120
                    yield self.a[i]
116
121
                if base_marker is not None:
117
 
                    yield base_marker + '\n'
 
122
                    yield base_marker + newline
118
123
                    for i in range(t[1], t[2]):
119
124
                        yield self.base[i]
120
 
                yield mid_marker + '\n'
 
125
                yield mid_marker + newline
121
126
                for i in range(t[5], t[6]):
122
127
                    yield self.b[i]
123
 
                yield end_marker + '\n'
 
128
                yield end_marker + newline
124
129
            else:
125
130
                raise ValueError(what)
126
 
        
127
 
        
128
 
 
129
 
 
130
131
 
131
132
    def merge_annotated(self):
132
133
        """Return merge with conflicts, showing origin of lines.
133
134
 
134
 
        Most useful for debugging merge.        
 
135
        Most useful for debugging merge.
135
136
        """
136
137
        for t in self.merge_regions():
137
138
            what = t[0]
154
155
                yield '>>>>\n'
155
156
            else:
156
157
                raise ValueError(what)
157
 
        
158
 
        
159
 
 
160
 
 
161
158
 
162
159
    def merge_groups(self):
163
160
        """Yield sequence of line groups.  Each one is a tuple:
193
190
            else:
194
191
                raise ValueError(what)
195
192
 
196
 
 
197
193
    def merge_regions(self):
198
194
        """Return sequences of matching and conflicting regions.
199
195
 
223
219
 
224
220
        # section a[0:ia] has been disposed of, etc
225
221
        iz = ia = ib = 0
226
 
        
 
222
 
227
223
        for zmatch, zend, amatch, aend, bmatch, bend in self.find_sync_regions():
228
 
            #print 'match base [%d:%d]' % (zmatch, zend)
229
 
            
230
224
            matchlen = zend - zmatch
231
 
            assert matchlen >= 0
232
 
            assert matchlen == (aend - amatch)
233
 
            assert matchlen == (bend - bmatch)
234
 
            
 
225
            # invariants:
 
226
            #   matchlen >= 0
 
227
            #   matchlen == (aend - amatch)
 
228
            #   matchlen == (bend - bmatch)
235
229
            len_a = amatch - ia
236
230
            len_b = bmatch - ib
237
231
            len_base = zmatch - iz
238
 
            assert len_a >= 0
239
 
            assert len_b >= 0
240
 
            assert len_base >= 0
 
232
            # invariants:
 
233
            # assert len_a >= 0
 
234
            # assert len_b >= 0
 
235
            # assert len_base >= 0
241
236
 
242
237
            #print 'unmatched a=%d, b=%d' % (len_a, len_b)
243
238
 
244
239
            if len_a or len_b:
245
240
                # try to avoid actually slicing the lists
246
 
                equal_a = compare_range(self.a, ia, amatch,
247
 
                                        self.base, iz, zmatch)
248
 
                equal_b = compare_range(self.b, ib, bmatch,
249
 
                                        self.base, iz, zmatch)
250
241
                same = compare_range(self.a, ia, amatch,
251
242
                                     self.b, ib, bmatch)
252
243
 
253
244
                if same:
254
245
                    yield 'same', ia, amatch
255
 
                elif equal_a and not equal_b:
256
 
                    yield 'b', ib, bmatch
257
 
                elif equal_b and not equal_a:
258
 
                    yield 'a', ia, amatch
259
 
                elif not equal_a and not equal_b:
260
 
                    yield 'conflict', iz, zmatch, ia, amatch, ib, bmatch
261
246
                else:
262
 
                    raise AssertionError("can't handle a=b=base but unmatched")
 
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)
 
251
                    if equal_a and not equal_b:
 
252
                        yield 'b', ib, bmatch
 
253
                    elif equal_b and not equal_a:
 
254
                        yield 'a', ia, amatch
 
255
                    elif not equal_a and not equal_b:
 
256
                        if self.is_cherrypick:
 
257
                            for node in self._refine_cherrypick_conflict(
 
258
                                                    iz, zmatch, ia, amatch,
 
259
                                                    ib, bmatch):
 
260
                                yield node
 
261
                        else:
 
262
                            yield 'conflict', iz, zmatch, ia, amatch, ib, bmatch
 
263
                    else:
 
264
                        raise AssertionError("can't handle a=b=base but unmatched")
263
265
 
264
266
                ia = amatch
265
267
                ib = bmatch
268
270
            # if the same part of the base was deleted on both sides
269
271
            # that's OK, we can just skip it.
270
272
 
271
 
                
272
273
            if matchlen > 0:
273
 
                assert ia == amatch
274
 
                assert ib == bmatch
275
 
                assert iz == zmatch
276
 
                
 
274
                # invariants:
 
275
                # assert ia == amatch
 
276
                # assert ib == bmatch
 
277
                # assert iz == zmatch
 
278
 
277
279
                yield 'unchanged', zmatch, zend
278
280
                iz = zend
279
281
                ia = aend
280
282
                ib = bend
281
 
    
 
283
 
 
284
    def _refine_cherrypick_conflict(self, zstart, zend, astart, aend, bstart, bend):
 
285
        """When cherrypicking b => a, ignore matches with b and base."""
 
286
        # Do not emit regions which match, only regions which do not match
 
287
        matches = bzrlib.patiencediff.PatienceSequenceMatcher(None,
 
288
            self.base[zstart:zend], self.b[bstart:bend]).get_matching_blocks()
 
289
        last_base_idx = 0
 
290
        last_b_idx = 0
 
291
        last_b_idx = 0
 
292
        yielded_a = False
 
293
        for base_idx, b_idx, match_len in matches:
 
294
            conflict_z_len = base_idx - last_base_idx
 
295
            conflict_b_len = b_idx - last_b_idx
 
296
            if conflict_b_len == 0: # There are no lines in b which conflict,
 
297
                                    # so skip it
 
298
                pass
 
299
            else:
 
300
                if yielded_a:
 
301
                    yield ('conflict',
 
302
                           zstart + last_base_idx, zstart + base_idx,
 
303
                           aend, aend, bstart + last_b_idx, bstart + b_idx)
 
304
                else:
 
305
                    # The first conflict gets the a-range
 
306
                    yielded_a = True
 
307
                    yield ('conflict', zstart + last_base_idx, zstart +
 
308
                    base_idx,
 
309
                           astart, aend, bstart + last_b_idx, bstart + b_idx)
 
310
            last_base_idx = base_idx + match_len
 
311
            last_b_idx = b_idx + match_len
 
312
        if last_base_idx != zend - zstart or last_b_idx != bend - bstart:
 
313
            if yielded_a:
 
314
                yield ('conflict', zstart + last_base_idx, zstart + base_idx,
 
315
                       aend, aend, bstart + last_b_idx, bstart + b_idx)
 
316
            else:
 
317
                # The first conflict gets the a-range
 
318
                yielded_a = True
 
319
                yield ('conflict', zstart + last_base_idx, zstart + base_idx,
 
320
                       astart, aend, bstart + last_b_idx, bstart + b_idx)
 
321
        if not yielded_a:
 
322
            yield ('conflict', zstart, zend, astart, aend, bstart, bend)
282
323
 
283
324
    def reprocess_merge_regions(self, merge_regions):
284
325
        """Where there are conflict regions, remove the agreed lines.
285
326
 
286
 
        Lines where both A and B have made the same changes are 
 
327
        Lines where both A and B have made the same changes are
287
328
        eliminated.
288
329
        """
289
330
        for region in merge_regions:
293
334
            type, iz, zmatch, ia, amatch, ib, bmatch = region
294
335
            a_region = self.a[ia:amatch]
295
336
            b_region = self.b[ib:bmatch]
296
 
            matches = SequenceMatcher(None, a_region, 
297
 
                                      b_region).get_matching_blocks()
 
337
            matches = bzrlib.patiencediff.PatienceSequenceMatcher(
 
338
                    None, a_region, b_region).get_matching_blocks()
298
339
            next_a = ia
299
340
            next_b = ib
300
341
            for region_ia, region_ib, region_len in matches[:-1]:
311
352
            if reg is not None:
312
353
                yield reg
313
354
 
314
 
 
315
355
    @staticmethod
316
356
    def mismatch_region(next_a, region_ia,  next_b, region_ib):
317
357
        if next_a < region_ia or next_b < region_ib:
318
358
            return 'conflict', None, None, next_a, region_ia, next_b, region_ib
319
 
            
320
359
 
321
360
    def find_sync_regions(self):
322
361
        """Return a list of sync regions, where both descendents match the base.
326
365
        """
327
366
 
328
367
        ia = ib = 0
329
 
        amatches = SequenceMatcher(None, self.base, self.a).get_matching_blocks()
330
 
        bmatches = SequenceMatcher(None, self.base, self.b).get_matching_blocks()
 
368
        amatches = bzrlib.patiencediff.PatienceSequenceMatcher(
 
369
                None, self.base, self.a).get_matching_blocks()
 
370
        bmatches = bzrlib.patiencediff.PatienceSequenceMatcher(
 
371
                None, self.base, self.b).get_matching_blocks()
331
372
        len_a = len(amatches)
332
373
        len_b = len(bmatches)
333
374
 
347
388
 
348
389
                # found a match of base[i[0], i[1]]; this may be less than
349
390
                # the region that matches in either one
350
 
                assert intlen <= alen
351
 
                assert intlen <= blen
352
 
                assert abase <= intbase
353
 
                assert bbase <= intbase
 
391
                # assert intlen <= alen
 
392
                # assert intlen <= blen
 
393
                # assert abase <= intbase
 
394
                # assert bbase <= intbase
354
395
 
355
396
                asub = amatch + (intbase - abase)
356
397
                bsub = bmatch + (intbase - bbase)
357
398
                aend = asub + intlen
358
399
                bend = bsub + intlen
359
400
 
360
 
                assert self.base[intbase:intend] == self.a[asub:aend], \
361
 
                       (self.base[intbase:intend], self.a[asub:aend])
362
 
 
363
 
                assert self.base[intbase:intend] == self.b[bsub:bend]
 
401
                # assert self.base[intbase:intend] == self.a[asub:aend], \
 
402
                #       (self.base[intbase:intend], self.a[asub:aend])
 
403
                # assert self.base[intbase:intend] == self.b[bsub:bend]
364
404
 
365
405
                sl.append((intbase, intend,
366
406
                           asub, aend,
367
407
                           bsub, bend))
368
 
 
369
408
            # advance whichever one ends first in the base text
370
409
            if (abase + alen) < (bbase + blen):
371
410
                ia += 1
372
411
            else:
373
412
                ib += 1
374
 
            
 
413
 
375
414
        intbase = len(self.base)
376
415
        abase = len(self.a)
377
416
        bbase = len(self.b)
379
418
 
380
419
        return sl
381
420
 
382
 
 
383
 
 
384
421
    def find_unconflicted(self):
385
422
        """Return a list of ranges in base that are not conflicted."""
386
 
        am = SequenceMatcher(None, self.base, self.a).get_matching_blocks()
387
 
        bm = SequenceMatcher(None, self.base, self.b).get_matching_blocks()
 
423
        am = bzrlib.patiencediff.PatienceSequenceMatcher(
 
424
                None, self.base, self.a).get_matching_blocks()
 
425
        bm = bzrlib.patiencediff.PatienceSequenceMatcher(
 
426
                None, self.base, self.b).get_matching_blocks()
388
427
 
389
428
        unc = []
390
429
 
403
442
                del am[0]
404
443
            else:
405
444
                del bm[0]
406
 
                
 
445
 
407
446
        return unc
408
447
 
409
448