/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: Martin Pool
  • Date: 2005-08-24 08:59:32 UTC
  • Revision ID: mbp@sourcefrog.net-20050824085932-c61f1f1f1c930e13
- Add a simple UIFactory 

  The idea of this is to let a client of bzrlib set some 
  policy about how output is displayed.

  In this revision all that's done is that progress bars
  are constructed by a policy established by the application
  rather than being randomly constructed in the library 
  or passed down the calls.  This avoids progress bars
  popping up while running the test suite and cleans up
  some code.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge3.py
1
 
# Copyright (C) 2005-2010 Canonical Ltd
2
 
#
 
1
# Copyright (C) 2004, 2005 by 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., 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
 
    )
26
21
 
27
22
 
28
23
def intersect(ra, rb):
37
32
    >>> intersect((0, 9), (7, 15))
38
33
    (7, 9)
39
34
    """
40
 
    # preconditions: (ra[0] <= ra[1]) and (rb[0] <= rb[1])
41
 
 
 
35
    assert ra[0] <= ra[1]
 
36
    assert rb[0] <= rb[1]
 
37
    
42
38
    sa = max(ra[0], rb[0])
43
39
    sb = min(ra[1], rb[1])
44
40
    if sa < sb:
57
53
            return False
58
54
    else:
59
55
        return True
60
 
 
 
56
        
61
57
 
62
58
 
63
59
 
67
63
    Given BASE, OTHER, THIS, tries to produce a combined text
68
64
    incorporating the changes from both BASE->OTHER and BASE->THIS.
69
65
    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)
 
66
    def __init__(self, base, a, b):
88
67
        self.base = base
89
68
        self.a = a
90
69
        self.b = b
91
 
        self.is_cherrypick = is_cherrypick
 
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
 
92
75
 
93
76
    def merge_lines(self,
94
77
                    name_a=None,
95
78
                    name_b=None,
96
 
                    name_base=None,
97
 
                    start_marker='<<<<<<<',
98
 
                    mid_marker='=======',
99
 
                    end_marker='>>>>>>>',
100
 
                    base_marker=None,
101
 
                    reprocess=False):
 
79
                    start_marker='<<<<<<<<',
 
80
                    mid_marker='========',
 
81
                    end_marker='>>>>>>>>',
 
82
                    show_base=False):
102
83
        """Return merge in cvs-like form.
103
84
        """
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
 
        if base_marker and reprocess:
111
 
            raise errors.CantReprocessAndShowBase()
112
85
        if name_a:
113
86
            start_marker = start_marker + ' ' + name_a
114
87
        if name_b:
115
88
            end_marker = end_marker + ' ' + name_b
116
 
        if name_base and base_marker:
117
 
            base_marker = base_marker + ' ' + name_base
118
 
        merge_regions = self.merge_regions()
119
 
        if reprocess is True:
120
 
            merge_regions = self.reprocess_merge_regions(merge_regions)
121
 
        for t in merge_regions:
 
89
            
 
90
        for t in self.merge_regions():
122
91
            what = t[0]
123
92
            if what == 'unchanged':
124
93
                for i in range(t[1], t[2]):
130
99
                for i in range(t[1], t[2]):
131
100
                    yield self.b[i]
132
101
            elif what == 'conflict':
133
 
                yield start_marker + newline
 
102
                yield start_marker + '\n'
134
103
                for i in range(t[3], t[4]):
135
104
                    yield self.a[i]
136
 
                if base_marker is not None:
137
 
                    yield base_marker + newline
138
 
                    for i in range(t[1], t[2]):
139
 
                        yield self.base[i]
140
 
                yield mid_marker + newline
 
105
                yield mid_marker + '\n'
141
106
                for i in range(t[5], t[6]):
142
107
                    yield self.b[i]
143
 
                yield end_marker + newline
 
108
                yield end_marker + '\n'
144
109
            else:
145
110
                raise ValueError(what)
 
111
        
 
112
        
 
113
 
 
114
 
146
115
 
147
116
    def merge_annotated(self):
148
117
        """Return merge with conflicts, showing origin of lines.
149
118
 
150
 
        Most useful for debugging merge.
 
119
        Most useful for debugging merge.        
151
120
        """
152
121
        for t in self.merge_regions():
153
122
            what = t[0]
170
139
                yield '>>>>\n'
171
140
            else:
172
141
                raise ValueError(what)
 
142
        
 
143
        
 
144
 
 
145
 
173
146
 
174
147
    def merge_groups(self):
175
148
        """Yield sequence of line groups.  Each one is a tuple:
205
178
            else:
206
179
                raise ValueError(what)
207
180
 
 
181
 
208
182
    def merge_regions(self):
209
183
        """Return sequences of matching and conflicting regions.
210
184
 
234
208
 
235
209
        # section a[0:ia] has been disposed of, etc
236
210
        iz = ia = ib = 0
237
 
 
 
211
        
238
212
        for zmatch, zend, amatch, aend, bmatch, bend in self.find_sync_regions():
 
213
            #print 'match base [%d:%d]' % (zmatch, zend)
 
214
            
239
215
            matchlen = zend - zmatch
240
 
            # invariants:
241
 
            #   matchlen >= 0
242
 
            #   matchlen == (aend - amatch)
243
 
            #   matchlen == (bend - bmatch)
 
216
            assert matchlen >= 0
 
217
            assert matchlen == (aend - amatch)
 
218
            assert matchlen == (bend - bmatch)
 
219
            
244
220
            len_a = amatch - ia
245
221
            len_b = bmatch - ib
246
222
            len_base = zmatch - iz
247
 
            # invariants:
248
 
            # assert len_a >= 0
249
 
            # assert len_b >= 0
250
 
            # assert len_base >= 0
 
223
            assert len_a >= 0
 
224
            assert len_b >= 0
 
225
            assert len_base >= 0
251
226
 
252
227
            #print 'unmatched a=%d, b=%d' % (len_a, len_b)
253
228
 
254
229
            if len_a or len_b:
255
230
                # 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)
256
235
                same = compare_range(self.a, ia, amatch,
257
236
                                     self.b, ib, bmatch)
258
237
 
259
238
                if same:
260
239
                    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
261
246
                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")
 
247
                    raise AssertionError("can't handle a=b=base but unmatched")
280
248
 
281
249
                ia = amatch
282
250
                ib = bmatch
285
253
            # if the same part of the base was deleted on both sides
286
254
            # that's OK, we can just skip it.
287
255
 
 
256
                
288
257
            if matchlen > 0:
289
 
                # invariants:
290
 
                # assert ia == amatch
291
 
                # assert ib == bmatch
292
 
                # assert iz == zmatch
293
 
 
 
258
                assert ia == amatch
 
259
                assert ib == bmatch
 
260
                assert iz == zmatch
 
261
                
294
262
                yield 'unchanged', zmatch, zend
295
263
                iz = zend
296
264
                ia = aend
297
265
                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)
338
 
 
339
 
    def reprocess_merge_regions(self, merge_regions):
340
 
        """Where there are conflict regions, remove the agreed lines.
341
 
 
342
 
        Lines where both A and B have made the same changes are
343
 
        eliminated.
344
 
        """
345
 
        for region in merge_regions:
346
 
            if region[0] != "conflict":
347
 
                yield region
348
 
                continue
349
 
            type, iz, zmatch, ia, amatch, ib, bmatch = region
350
 
            a_region = self.a[ia:amatch]
351
 
            b_region = self.b[ib:bmatch]
352
 
            matches = patiencediff.PatienceSequenceMatcher(
353
 
                    None, a_region, b_region).get_matching_blocks()
354
 
            next_a = ia
355
 
            next_b = ib
356
 
            for region_ia, region_ib, region_len in matches[:-1]:
357
 
                region_ia += ia
358
 
                region_ib += ib
359
 
                reg = self.mismatch_region(next_a, region_ia, next_b,
360
 
                                           region_ib)
361
 
                if reg is not None:
362
 
                    yield reg
363
 
                yield 'same', region_ia, region_len+region_ia
364
 
                next_a = region_ia + region_len
365
 
                next_b = region_ib + region_len
366
 
            reg = self.mismatch_region(next_a, amatch, next_b, bmatch)
367
 
            if reg is not None:
368
 
                yield reg
369
 
 
370
 
    @staticmethod
371
 
    def mismatch_region(next_a, region_ia,  next_b, region_ib):
372
 
        if next_a < region_ia or next_b < region_ib:
373
 
            return 'conflict', None, None, next_a, region_ia, next_b, region_ib
374
 
 
 
266
        
 
267
 
 
268
        
375
269
    def find_sync_regions(self):
376
270
        """Return a list of sync regions, where both descendents match the base.
377
271
 
378
272
        Generates a list of (base1, base2, a1, a2, b1, b2).  There is
379
273
        always a zero-length sync region at the end of all the files.
380
274
        """
 
275
        from difflib import SequenceMatcher
381
276
 
382
277
        ia = ib = 0
383
 
        amatches = patiencediff.PatienceSequenceMatcher(
384
 
                None, self.base, self.a).get_matching_blocks()
385
 
        bmatches = patiencediff.PatienceSequenceMatcher(
386
 
                None, self.base, self.b).get_matching_blocks()
 
278
        amatches = SequenceMatcher(None, self.base, self.a).get_matching_blocks()
 
279
        bmatches = SequenceMatcher(None, self.base, self.b).get_matching_blocks()
387
280
        len_a = len(amatches)
388
281
        len_b = len(bmatches)
389
282
 
403
296
 
404
297
                # found a match of base[i[0], i[1]]; this may be less than
405
298
                # the region that matches in either one
406
 
                # assert intlen <= alen
407
 
                # assert intlen <= blen
408
 
                # assert abase <= intbase
409
 
                # assert bbase <= intbase
 
299
                assert intlen <= alen
 
300
                assert intlen <= blen
 
301
                assert abase <= intbase
 
302
                assert bbase <= intbase
410
303
 
411
304
                asub = amatch + (intbase - abase)
412
305
                bsub = bmatch + (intbase - bbase)
413
306
                aend = asub + intlen
414
307
                bend = bsub + intlen
415
308
 
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]
 
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]
419
313
 
420
314
                sl.append((intbase, intend,
421
315
                           asub, aend,
422
316
                           bsub, bend))
 
317
 
423
318
            # advance whichever one ends first in the base text
424
319
            if (abase + alen) < (bbase + blen):
425
320
                ia += 1
426
321
            else:
427
322
                ib += 1
428
 
 
 
323
            
429
324
        intbase = len(self.base)
430
325
        abase = len(self.a)
431
326
        bbase = len(self.b)
433
328
 
434
329
        return sl
435
330
 
 
331
 
 
332
 
436
333
    def find_unconflicted(self):
437
334
        """Return a list of ranges in base that are not conflicted."""
438
 
        am = patiencediff.PatienceSequenceMatcher(
439
 
                None, self.base, self.a).get_matching_blocks()
440
 
        bm = patiencediff.PatienceSequenceMatcher(
441
 
                None, self.base, self.b).get_matching_blocks()
 
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()
442
344
 
443
345
        unc = []
444
346
 
457
359
                del am[0]
458
360
            else:
459
361
                del bm[0]
460
 
 
 
362
                
461
363
        return unc
462
364
 
463
365