← 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: 2007-05-31 20:29:04 UTC
  • mto: This revision was merged to the branch mainline in revision 2499.
  • Revision ID: john@arbash-meinel.com-20070531202904-34h7ygudo7qq9ha1
Update the code so that symlinks aren't cached at incorrect times
and fix the tests so that they don't assume files and symlinks
get cached even when the timestamp doesn't declare them 'safe'.

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,
108
95
            elif self.a[0].endswith('\r'):
109
96
                newline = '\r'
110
97
        if base_marker and reprocess:
111
 
            raise errors.CantReprocessAndShowBase()
 
98
            raise CantReprocessAndShowBase()
112
99
        if name_a:
113
100
            start_marker = start_marker + ' ' + name_a
114
101
        if name_b:
143
130
                yield end_marker + newline
144
131
            else:
145
132
                raise ValueError(what)
 
133
        
 
134
        
 
135
 
 
136
 
146
137
 
147
138
    def merge_annotated(self):
148
139
        """Return merge with conflicts, showing origin of lines.
149
140
 
150
 
        Most useful for debugging merge.
 
141
        Most useful for debugging merge.        
151
142
        """
152
143
        for t in self.merge_regions():
153
144
            what = t[0]
170
161
                yield '>>>>\n'
171
162
            else:
172
163
                raise ValueError(what)
 
164
        
 
165
        
 
166
 
 
167
 
173
168
 
174
169
    def merge_groups(self):
175
170
        """Yield sequence of line groups.  Each one is a tuple:
205
200
            else:
206
201
                raise ValueError(what)
207
202
 
 
203
 
208
204
    def merge_regions(self):
209
205
        """Return sequences of matching and conflicting regions.
210
206
 
234
230
 
235
231
        # section a[0:ia] has been disposed of, etc
236
232
        iz = ia = ib = 0
237
 
 
 
233
        
238
234
        for zmatch, zend, amatch, aend, bmatch, bend in self.find_sync_regions():
 
235
            #print 'match base [%d:%d]' % (zmatch, zend)
 
236
            
239
237
            matchlen = zend - zmatch
240
 
            # invariants:
241
 
            #   matchlen >= 0
242
 
            #   matchlen == (aend - amatch)
243
 
            #   matchlen == (bend - bmatch)
 
238
            assert matchlen >= 0
 
239
            assert matchlen == (aend - amatch)
 
240
            assert matchlen == (bend - bmatch)
 
241
            
244
242
            len_a = amatch - ia
245
243
            len_b = bmatch - ib
246
244
            len_base = zmatch - iz
247
 
            # invariants:
248
 
            # assert len_a >= 0
249
 
            # assert len_b >= 0
250
 
            # assert len_base >= 0
 
245
            assert len_a >= 0
 
246
            assert len_b >= 0
 
247
            assert len_base >= 0
251
248
 
252
249
            #print 'unmatched a=%d, b=%d' % (len_a, len_b)
253
250
 
254
251
            if len_a or len_b:
255
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)
256
257
                same = compare_range(self.a, ia, amatch,
257
258
                                     self.b, ib, bmatch)
258
259
 
259
260
                if same:
260
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
261
268
                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")
 
269
                    raise AssertionError("can't handle a=b=base but unmatched")
280
270
 
281
271
                ia = amatch
282
272
                ib = bmatch
285
275
            # if the same part of the base was deleted on both sides
286
276
            # that's OK, we can just skip it.
287
277
 
 
278
                
288
279
            if matchlen > 0:
289
 
                # invariants:
290
 
                # assert ia == amatch
291
 
                # assert ib == bmatch
292
 
                # assert iz == zmatch
293
 
 
 
280
                assert ia == amatch
 
281
                assert ib == bmatch
 
282
                assert iz == zmatch
 
283
                
294
284
                yield 'unchanged', zmatch, zend
295
285
                iz = zend
296
286
                ia = aend
297
287
                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)
 
288
    
338
289
 
339
290
    def reprocess_merge_regions(self, merge_regions):
340
291
        """Where there are conflict regions, remove the agreed lines.
341
292
 
342
 
        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 
343
294
        eliminated.
344
295
        """
345
296
        for region in merge_regions:
349
300
            type, iz, zmatch, ia, amatch, ib, bmatch = region
350
301
            a_region = self.a[ia:amatch]
351
302
            b_region = self.b[ib:bmatch]
352
 
            matches = patiencediff.PatienceSequenceMatcher(
 
303
            matches = bzrlib.patiencediff.PatienceSequenceMatcher(
353
304
                    None, a_region, b_region).get_matching_blocks()
354
305
            next_a = ia
355
306
            next_b = ib
367
318
            if reg is not None:
368
319
                yield reg
369
320
 
 
321
 
370
322
    @staticmethod
371
323
    def mismatch_region(next_a, region_ia,  next_b, region_ib):
372
324
        if next_a < region_ia or next_b < region_ib:
373
325
            return 'conflict', None, None, next_a, region_ia, next_b, region_ib
 
326
            
374
327
 
375
328
    def find_sync_regions(self):
376
329
        """Return a list of sync regions, where both descendents match the base.
380
333
        """
381
334
 
382
335
        ia = ib = 0
383
 
        amatches = patiencediff.PatienceSequenceMatcher(
 
336
        amatches = bzrlib.patiencediff.PatienceSequenceMatcher(
384
337
                None, self.base, self.a).get_matching_blocks()
385
 
        bmatches = patiencediff.PatienceSequenceMatcher(
 
338
        bmatches = bzrlib.patiencediff.PatienceSequenceMatcher(
386
339
                None, self.base, self.b).get_matching_blocks()
387
340
        len_a = len(amatches)
388
341
        len_b = len(bmatches)
403
356
 
404
357
                # found a match of base[i[0], i[1]]; this may be less than
405
358
                # the region that matches in either one
406
 
                # assert intlen <= alen
407
 
                # assert intlen <= blen
408
 
                # assert abase <= intbase
409
 
                # assert bbase <= intbase
 
359
                assert intlen <= alen
 
360
                assert intlen <= blen
 
361
                assert abase <= intbase
 
362
                assert bbase <= intbase
410
363
 
411
364
                asub = amatch + (intbase - abase)
412
365
                bsub = bmatch + (intbase - bbase)
413
366
                aend = asub + intlen
414
367
                bend = bsub + intlen
415
368
 
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]
 
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]
419
373
 
420
374
                sl.append((intbase, intend,
421
375
                           asub, aend,
422
376
                           bsub, bend))
 
377
 
423
378
            # advance whichever one ends first in the base text
424
379
            if (abase + alen) < (bbase + blen):
425
380
                ia += 1
426
381
            else:
427
382
                ib += 1
428
 
 
 
383
            
429
384
        intbase = len(self.base)
430
385
        abase = len(self.a)
431
386
        bbase = len(self.b)
433
388
 
434
389
        return sl
435
390
 
 
391
 
 
392
 
436
393
    def find_unconflicted(self):
437
394
        """Return a list of ranges in base that are not conflicted."""
438
 
        am = patiencediff.PatienceSequenceMatcher(
 
395
        am = bzrlib.patiencediff.PatienceSequenceMatcher(
439
396
                None, self.base, self.a).get_matching_blocks()
440
 
        bm = patiencediff.PatienceSequenceMatcher(
 
397
        bm = bzrlib.patiencediff.PatienceSequenceMatcher(
441
398
                None, self.base, self.b).get_matching_blocks()
442
399
 
443
400
        unc = []
457
414
                del am[0]
458
415
            else:
459
416
                del bm[0]
460
 
 
 
417
                
461
418
        return unc
462
419
 
463
420