/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: Canonical.com Patch Queue Manager
  • Date: 2009-07-20 08:56:45 UTC
  • mfrom: (4526.9.23 apply-inventory-delta)
  • Revision ID: pqm@pqm.ubuntu.com-20090720085645-54mtgybxua0yx6hw
(robertc) Add checks for inventory deltas which try to ensure that
        deltas that are not an exact fit are not applied. (Robert
        Collins, bug 397705, bug 367633)

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?"
19
19
# s: "i hate that."
20
20
 
21
21
 
 
22
from bzrlib.errors import CantReprocessAndShowBase
 
23
import bzrlib.patiencediff
 
24
from bzrlib.textfile import check_text_lines
 
25
 
22
26
 
23
27
def intersect(ra, rb):
24
28
    """Given two ranges return the range where they intersect or None.
32
36
    >>> intersect((0, 9), (7, 15))
33
37
    (7, 9)
34
38
    """
35
 
    assert ra[0] <= ra[1]
36
 
    assert rb[0] <= rb[1]
37
 
    
 
39
    # preconditions: (ra[0] <= ra[1]) and (rb[0] <= rb[1])
 
40
 
38
41
    sa = max(ra[0], rb[0])
39
42
    sb = min(ra[1], rb[1])
40
43
    if sa < sb:
53
56
            return False
54
57
    else:
55
58
        return True
56
 
        
 
59
 
57
60
 
58
61
 
59
62
 
63
66
    Given BASE, OTHER, THIS, tries to produce a combined text
64
67
    incorporating the changes from both BASE->OTHER and BASE->THIS.
65
68
    All three will typically be sequences of lines."""
66
 
    def __init__(self, base, a, b):
 
69
    def __init__(self, base, a, b, is_cherrypick=False):
 
70
        check_text_lines(base)
 
71
        check_text_lines(a)
 
72
        check_text_lines(b)
67
73
        self.base = base
68
74
        self.a = a
69
75
        self.b = b
70
 
        from difflib import SequenceMatcher
71
 
        self.a_ops = SequenceMatcher(None, base, a).get_opcodes()
72
 
        self.b_ops = SequenceMatcher(None, base, b).get_opcodes()
73
 
 
74
 
 
 
76
        self.is_cherrypick = is_cherrypick
75
77
 
76
78
    def merge_lines(self,
77
79
                    name_a=None,
78
80
                    name_b=None,
79
 
                    start_marker='<<<<<<<<',
80
 
                    mid_marker='========',
81
 
                    end_marker='>>>>>>>>',
82
 
                    show_base=False):
 
81
                    name_base=None,
 
82
                    start_marker='<<<<<<<',
 
83
                    mid_marker='=======',
 
84
                    end_marker='>>>>>>>',
 
85
                    base_marker=None,
 
86
                    reprocess=False):
83
87
        """Return merge in cvs-like form.
84
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'
 
95
        if base_marker and reprocess:
 
96
            raise CantReprocessAndShowBase()
85
97
        if name_a:
86
98
            start_marker = start_marker + ' ' + name_a
87
99
        if name_b:
88
100
            end_marker = end_marker + ' ' + name_b
89
 
            
90
 
        for t in self.merge_regions():
 
101
        if name_base and base_marker:
 
102
            base_marker = base_marker + ' ' + name_base
 
103
        merge_regions = self.merge_regions()
 
104
        if reprocess is True:
 
105
            merge_regions = self.reprocess_merge_regions(merge_regions)
 
106
        for t in merge_regions:
91
107
            what = t[0]
92
108
            if what == 'unchanged':
93
109
                for i in range(t[1], t[2]):
99
115
                for i in range(t[1], t[2]):
100
116
                    yield self.b[i]
101
117
            elif what == 'conflict':
102
 
                yield start_marker + '\n'
 
118
                yield start_marker + newline
103
119
                for i in range(t[3], t[4]):
104
120
                    yield self.a[i]
105
 
                yield mid_marker + '\n'
 
121
                if base_marker is not None:
 
122
                    yield base_marker + newline
 
123
                    for i in range(t[1], t[2]):
 
124
                        yield self.base[i]
 
125
                yield mid_marker + newline
106
126
                for i in range(t[5], t[6]):
107
127
                    yield self.b[i]
108
 
                yield end_marker + '\n'
 
128
                yield end_marker + newline
109
129
            else:
110
130
                raise ValueError(what)
111
 
        
112
 
        
113
 
 
114
 
 
115
131
 
116
132
    def merge_annotated(self):
117
133
        """Return merge with conflicts, showing origin of lines.
118
134
 
119
 
        Most useful for debugging merge.        
 
135
        Most useful for debugging merge.
120
136
        """
121
137
        for t in self.merge_regions():
122
138
            what = t[0]
139
155
                yield '>>>>\n'
140
156
            else:
141
157
                raise ValueError(what)
142
 
        
143
 
        
144
 
 
145
 
 
146
158
 
147
159
    def merge_groups(self):
148
160
        """Yield sequence of line groups.  Each one is a tuple:
178
190
            else:
179
191
                raise ValueError(what)
180
192
 
181
 
 
182
193
    def merge_regions(self):
183
194
        """Return sequences of matching and conflicting regions.
184
195
 
208
219
 
209
220
        # section a[0:ia] has been disposed of, etc
210
221
        iz = ia = ib = 0
211
 
        
 
222
 
212
223
        for zmatch, zend, amatch, aend, bmatch, bend in self.find_sync_regions():
213
 
            #print 'match base [%d:%d]' % (zmatch, zend)
214
 
            
215
224
            matchlen = zend - zmatch
216
 
            assert matchlen >= 0
217
 
            assert matchlen == (aend - amatch)
218
 
            assert matchlen == (bend - bmatch)
219
 
            
 
225
            # invariants:
 
226
            #   matchlen >= 0
 
227
            #   matchlen == (aend - amatch)
 
228
            #   matchlen == (bend - bmatch)
220
229
            len_a = amatch - ia
221
230
            len_b = bmatch - ib
222
231
            len_base = zmatch - iz
223
 
            assert len_a >= 0
224
 
            assert len_b >= 0
225
 
            assert len_base >= 0
 
232
            # invariants:
 
233
            # assert len_a >= 0
 
234
            # assert len_b >= 0
 
235
            # assert len_base >= 0
226
236
 
227
237
            #print 'unmatched a=%d, b=%d' % (len_a, len_b)
228
238
 
229
239
            if len_a or len_b:
230
240
                # try to avoid actually slicing the lists
231
 
                equal_a = compare_range(self.a, ia, amatch,
232
 
                                        self.base, iz, zmatch)
233
 
                equal_b = compare_range(self.b, ib, bmatch,
234
 
                                        self.base, iz, zmatch)
235
241
                same = compare_range(self.a, ia, amatch,
236
242
                                     self.b, ib, bmatch)
237
243
 
238
244
                if same:
239
245
                    yield 'same', ia, amatch
240
 
                elif equal_a and not equal_b:
241
 
                    yield 'b', ib, bmatch
242
 
                elif equal_b and not equal_a:
243
 
                    yield 'a', ia, amatch
244
 
                elif not equal_a and not equal_b:
245
 
                    yield 'conflict', iz, zmatch, ia, amatch, ib, bmatch
246
246
                else:
247
 
                    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")
248
265
 
249
266
                ia = amatch
250
267
                ib = bmatch
253
270
            # if the same part of the base was deleted on both sides
254
271
            # that's OK, we can just skip it.
255
272
 
256
 
                
257
273
            if matchlen > 0:
258
 
                assert ia == amatch
259
 
                assert ib == bmatch
260
 
                assert iz == zmatch
261
 
                
 
274
                # invariants:
 
275
                # assert ia == amatch
 
276
                # assert ib == bmatch
 
277
                # assert iz == zmatch
 
278
 
262
279
                yield 'unchanged', zmatch, zend
263
280
                iz = zend
264
281
                ia = aend
265
282
                ib = bend
266
 
        
267
 
 
268
 
        
 
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)
 
323
 
 
324
    def reprocess_merge_regions(self, merge_regions):
 
325
        """Where there are conflict regions, remove the agreed lines.
 
326
 
 
327
        Lines where both A and B have made the same changes are
 
328
        eliminated.
 
329
        """
 
330
        for region in merge_regions:
 
331
            if region[0] != "conflict":
 
332
                yield region
 
333
                continue
 
334
            type, iz, zmatch, ia, amatch, ib, bmatch = region
 
335
            a_region = self.a[ia:amatch]
 
336
            b_region = self.b[ib:bmatch]
 
337
            matches = bzrlib.patiencediff.PatienceSequenceMatcher(
 
338
                    None, a_region, b_region).get_matching_blocks()
 
339
            next_a = ia
 
340
            next_b = ib
 
341
            for region_ia, region_ib, region_len in matches[:-1]:
 
342
                region_ia += ia
 
343
                region_ib += ib
 
344
                reg = self.mismatch_region(next_a, region_ia, next_b,
 
345
                                           region_ib)
 
346
                if reg is not None:
 
347
                    yield reg
 
348
                yield 'same', region_ia, region_len+region_ia
 
349
                next_a = region_ia + region_len
 
350
                next_b = region_ib + region_len
 
351
            reg = self.mismatch_region(next_a, amatch, next_b, bmatch)
 
352
            if reg is not None:
 
353
                yield reg
 
354
 
 
355
    @staticmethod
 
356
    def mismatch_region(next_a, region_ia,  next_b, region_ib):
 
357
        if next_a < region_ia or next_b < region_ib:
 
358
            return 'conflict', None, None, next_a, region_ia, next_b, region_ib
 
359
 
269
360
    def find_sync_regions(self):
270
361
        """Return a list of sync regions, where both descendents match the base.
271
362
 
272
363
        Generates a list of (base1, base2, a1, a2, b1, b2).  There is
273
364
        always a zero-length sync region at the end of all the files.
274
365
        """
275
 
        from difflib import SequenceMatcher
276
366
 
277
367
        ia = ib = 0
278
 
        amatches = SequenceMatcher(None, self.base, self.a).get_matching_blocks()
279
 
        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()
280
372
        len_a = len(amatches)
281
373
        len_b = len(bmatches)
282
374
 
296
388
 
297
389
                # found a match of base[i[0], i[1]]; this may be less than
298
390
                # the region that matches in either one
299
 
                assert intlen <= alen
300
 
                assert intlen <= blen
301
 
                assert abase <= intbase
302
 
                assert bbase <= intbase
 
391
                # assert intlen <= alen
 
392
                # assert intlen <= blen
 
393
                # assert abase <= intbase
 
394
                # assert bbase <= intbase
303
395
 
304
396
                asub = amatch + (intbase - abase)
305
397
                bsub = bmatch + (intbase - bbase)
306
398
                aend = asub + intlen
307
399
                bend = bsub + intlen
308
400
 
309
 
                assert self.base[intbase:intend] == self.a[asub:aend], \
310
 
                       (self.base[intbase:intend], self.a[asub:aend])
311
 
 
312
 
                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]
313
404
 
314
405
                sl.append((intbase, intend,
315
406
                           asub, aend,
316
407
                           bsub, bend))
317
 
 
318
408
            # advance whichever one ends first in the base text
319
409
            if (abase + alen) < (bbase + blen):
320
410
                ia += 1
321
411
            else:
322
412
                ib += 1
323
 
            
 
413
 
324
414
        intbase = len(self.base)
325
415
        abase = len(self.a)
326
416
        bbase = len(self.b)
328
418
 
329
419
        return sl
330
420
 
331
 
 
332
 
 
333
421
    def find_unconflicted(self):
334
422
        """Return a list of ranges in base that are not conflicted."""
335
 
        from difflib import SequenceMatcher
336
 
 
337
 
        import re
338
 
 
339
 
        # don't sync-up on lines containing only blanks or pounds
340
 
        junk_re = re.compile(r'^[ \t#]*$')
341
 
        
342
 
        am = SequenceMatcher(junk_re.match, self.base, self.a).get_matching_blocks()
343
 
        bm = SequenceMatcher(junk_re.match, 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()
344
427
 
345
428
        unc = []
346
429
 
359
442
                del am[0]
360
443
            else:
361
444
                del bm[0]
362
 
                
 
445
 
363
446
        return unc
364
447
 
365
448