/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: 2007-08-16 04:42:31 UTC
  • mfrom: (2701.1.3 remove-should-cache)
  • Revision ID: pqm@pqm.ubuntu.com-20070816044231-k9pvlics7hlhxuw5
Remove Transport.should_cache.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge3.py
 
1
# Copyright (C) 2004, 2005 Canonical Ltd
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
#
 
13
# You should have received a copy of the GNU General Public License
 
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
 
16
 
 
17
 
 
18
# mbp: "you know that thing where cvs gives you conflict markers?"
 
19
# s: "i hate that."
 
20
 
 
21
 
 
22
from bzrlib.errors import CantReprocessAndShowBase
 
23
import bzrlib.patiencediff
 
24
from bzrlib.textfile import check_text_lines
 
25
 
 
26
 
 
27
def intersect(ra, rb):
 
28
    """Given two ranges return the range where they intersect or None.
 
29
 
 
30
    >>> intersect((0, 10), (0, 6))
 
31
    (0, 6)
 
32
    >>> intersect((0, 10), (5, 15))
 
33
    (5, 10)
 
34
    >>> intersect((0, 10), (10, 15))
 
35
    >>> intersect((0, 9), (10, 15))
 
36
    >>> intersect((0, 9), (7, 15))
 
37
    (7, 9)
 
38
    """
 
39
    assert ra[0] <= ra[1]
 
40
    assert rb[0] <= rb[1]
 
41
    
 
42
    sa = max(ra[0], rb[0])
 
43
    sb = min(ra[1], rb[1])
 
44
    if sa < sb:
 
45
        return sa, sb
 
46
    else:
 
47
        return None
 
48
 
 
49
 
 
50
def compare_range(a, astart, aend, b, bstart, bend):
 
51
    """Compare a[astart:aend] == b[bstart:bend], without slicing.
 
52
    """
 
53
    if (aend-astart) != (bend-bstart):
 
54
        return False
 
55
    for ia, ib in zip(xrange(astart, aend), xrange(bstart, bend)):
 
56
        if a[ia] != b[ib]:
 
57
            return False
 
58
    else:
 
59
        return True
 
60
        
 
61
 
 
62
 
 
63
 
 
64
class Merge3(object):
 
65
    """3-way merge of texts.
 
66
 
 
67
    Given BASE, OTHER, THIS, tries to produce a combined text
 
68
    incorporating the changes from both BASE->OTHER and BASE->THIS.
 
69
    All three will typically be sequences of lines."""
 
70
    def __init__(self, base, a, b):
 
71
        check_text_lines(base)
 
72
        check_text_lines(a)
 
73
        check_text_lines(b)
 
74
        self.base = base
 
75
        self.a = a
 
76
        self.b = b
 
77
 
 
78
 
 
79
 
 
80
    def merge_lines(self,
 
81
                    name_a=None,
 
82
                    name_b=None,
 
83
                    name_base=None,
 
84
                    start_marker='<<<<<<<',
 
85
                    mid_marker='=======',
 
86
                    end_marker='>>>>>>>',
 
87
                    base_marker=None,
 
88
                    reprocess=False):
 
89
        """Return merge in cvs-like form.
 
90
        """
 
91
        newline = '\n'
 
92
        if len(self.a) > 0:
 
93
            if self.a[0].endswith('\r\n'):
 
94
                newline = '\r\n'
 
95
            elif self.a[0].endswith('\r'):
 
96
                newline = '\r'
 
97
        if base_marker and reprocess:
 
98
            raise CantReprocessAndShowBase()
 
99
        if name_a:
 
100
            start_marker = start_marker + ' ' + name_a
 
101
        if name_b:
 
102
            end_marker = end_marker + ' ' + name_b
 
103
        if name_base and base_marker:
 
104
            base_marker = base_marker + ' ' + name_base
 
105
        merge_regions = self.merge_regions()
 
106
        if reprocess is True:
 
107
            merge_regions = self.reprocess_merge_regions(merge_regions)
 
108
        for t in merge_regions:
 
109
            what = t[0]
 
110
            if what == 'unchanged':
 
111
                for i in range(t[1], t[2]):
 
112
                    yield self.base[i]
 
113
            elif what == 'a' or what == 'same':
 
114
                for i in range(t[1], t[2]):
 
115
                    yield self.a[i]
 
116
            elif what == 'b':
 
117
                for i in range(t[1], t[2]):
 
118
                    yield self.b[i]
 
119
            elif what == 'conflict':
 
120
                yield start_marker + newline
 
121
                for i in range(t[3], t[4]):
 
122
                    yield self.a[i]
 
123
                if base_marker is not None:
 
124
                    yield base_marker + newline
 
125
                    for i in range(t[1], t[2]):
 
126
                        yield self.base[i]
 
127
                yield mid_marker + newline
 
128
                for i in range(t[5], t[6]):
 
129
                    yield self.b[i]
 
130
                yield end_marker + newline
 
131
            else:
 
132
                raise ValueError(what)
 
133
        
 
134
        
 
135
 
 
136
 
 
137
 
 
138
    def merge_annotated(self):
 
139
        """Return merge with conflicts, showing origin of lines.
 
140
 
 
141
        Most useful for debugging merge.        
 
142
        """
 
143
        for t in self.merge_regions():
 
144
            what = t[0]
 
145
            if what == 'unchanged':
 
146
                for i in range(t[1], t[2]):
 
147
                    yield 'u | ' + self.base[i]
 
148
            elif what == 'a' or what == 'same':
 
149
                for i in range(t[1], t[2]):
 
150
                    yield what[0] + ' | ' + self.a[i]
 
151
            elif what == 'b':
 
152
                for i in range(t[1], t[2]):
 
153
                    yield 'b | ' + self.b[i]
 
154
            elif what == 'conflict':
 
155
                yield '<<<<\n'
 
156
                for i in range(t[3], t[4]):
 
157
                    yield 'A | ' + self.a[i]
 
158
                yield '----\n'
 
159
                for i in range(t[5], t[6]):
 
160
                    yield 'B | ' + self.b[i]
 
161
                yield '>>>>\n'
 
162
            else:
 
163
                raise ValueError(what)
 
164
        
 
165
        
 
166
 
 
167
 
 
168
 
 
169
    def merge_groups(self):
 
170
        """Yield sequence of line groups.  Each one is a tuple:
 
171
 
 
172
        'unchanged', lines
 
173
             Lines unchanged from base
 
174
 
 
175
        'a', lines
 
176
             Lines taken from a
 
177
 
 
178
        'same', lines
 
179
             Lines taken from a (and equal to b)
 
180
 
 
181
        'b', lines
 
182
             Lines taken from b
 
183
 
 
184
        'conflict', base_lines, a_lines, b_lines
 
185
             Lines from base were changed to either a or b and conflict.
 
186
        """
 
187
        for t in self.merge_regions():
 
188
            what = t[0]
 
189
            if what == 'unchanged':
 
190
                yield what, self.base[t[1]:t[2]]
 
191
            elif what == 'a' or what == 'same':
 
192
                yield what, self.a[t[1]:t[2]]
 
193
            elif what == 'b':
 
194
                yield what, self.b[t[1]:t[2]]
 
195
            elif what == 'conflict':
 
196
                yield (what,
 
197
                       self.base[t[1]:t[2]],
 
198
                       self.a[t[3]:t[4]],
 
199
                       self.b[t[5]:t[6]])
 
200
            else:
 
201
                raise ValueError(what)
 
202
 
 
203
 
 
204
    def merge_regions(self):
 
205
        """Return sequences of matching and conflicting regions.
 
206
 
 
207
        This returns tuples, where the first value says what kind we
 
208
        have:
 
209
 
 
210
        'unchanged', start, end
 
211
             Take a region of base[start:end]
 
212
 
 
213
        'same', astart, aend
 
214
             b and a are different from base but give the same result
 
215
 
 
216
        'a', start, end
 
217
             Non-clashing insertion from a[start:end]
 
218
 
 
219
        Method is as follows:
 
220
 
 
221
        The two sequences align only on regions which match the base
 
222
        and both descendents.  These are found by doing a two-way diff
 
223
        of each one against the base, and then finding the
 
224
        intersections between those regions.  These "sync regions"
 
225
        are by definition unchanged in both and easily dealt with.
 
226
 
 
227
        The regions in between can be in any of three cases:
 
228
        conflicted, or changed on only one side.
 
229
        """
 
230
 
 
231
        # section a[0:ia] has been disposed of, etc
 
232
        iz = ia = ib = 0
 
233
        
 
234
        for zmatch, zend, amatch, aend, bmatch, bend in self.find_sync_regions():
 
235
            #print 'match base [%d:%d]' % (zmatch, zend)
 
236
            
 
237
            matchlen = zend - zmatch
 
238
            assert matchlen >= 0
 
239
            assert matchlen == (aend - amatch)
 
240
            assert matchlen == (bend - bmatch)
 
241
            
 
242
            len_a = amatch - ia
 
243
            len_b = bmatch - ib
 
244
            len_base = zmatch - iz
 
245
            assert len_a >= 0
 
246
            assert len_b >= 0
 
247
            assert len_base >= 0
 
248
 
 
249
            #print 'unmatched a=%d, b=%d' % (len_a, len_b)
 
250
 
 
251
            if len_a or len_b:
 
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
                same = compare_range(self.a, ia, amatch,
 
258
                                     self.b, ib, bmatch)
 
259
 
 
260
                if same:
 
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
 
268
                else:
 
269
                    raise AssertionError("can't handle a=b=base but unmatched")
 
270
 
 
271
                ia = amatch
 
272
                ib = bmatch
 
273
            iz = zmatch
 
274
 
 
275
            # if the same part of the base was deleted on both sides
 
276
            # that's OK, we can just skip it.
 
277
 
 
278
                
 
279
            if matchlen > 0:
 
280
                assert ia == amatch
 
281
                assert ib == bmatch
 
282
                assert iz == zmatch
 
283
                
 
284
                yield 'unchanged', zmatch, zend
 
285
                iz = zend
 
286
                ia = aend
 
287
                ib = bend
 
288
    
 
289
 
 
290
    def reprocess_merge_regions(self, merge_regions):
 
291
        """Where there are conflict regions, remove the agreed lines.
 
292
 
 
293
        Lines where both A and B have made the same changes are 
 
294
        eliminated.
 
295
        """
 
296
        for region in merge_regions:
 
297
            if region[0] != "conflict":
 
298
                yield region
 
299
                continue
 
300
            type, iz, zmatch, ia, amatch, ib, bmatch = region
 
301
            a_region = self.a[ia:amatch]
 
302
            b_region = self.b[ib:bmatch]
 
303
            matches = bzrlib.patiencediff.PatienceSequenceMatcher(
 
304
                    None, a_region, b_region).get_matching_blocks()
 
305
            next_a = ia
 
306
            next_b = ib
 
307
            for region_ia, region_ib, region_len in matches[:-1]:
 
308
                region_ia += ia
 
309
                region_ib += ib
 
310
                reg = self.mismatch_region(next_a, region_ia, next_b,
 
311
                                           region_ib)
 
312
                if reg is not None:
 
313
                    yield reg
 
314
                yield 'same', region_ia, region_len+region_ia
 
315
                next_a = region_ia + region_len
 
316
                next_b = region_ib + region_len
 
317
            reg = self.mismatch_region(next_a, amatch, next_b, bmatch)
 
318
            if reg is not None:
 
319
                yield reg
 
320
 
 
321
 
 
322
    @staticmethod
 
323
    def mismatch_region(next_a, region_ia,  next_b, region_ib):
 
324
        if next_a < region_ia or next_b < region_ib:
 
325
            return 'conflict', None, None, next_a, region_ia, next_b, region_ib
 
326
            
 
327
 
 
328
    def find_sync_regions(self):
 
329
        """Return a list of sync regions, where both descendents match the base.
 
330
 
 
331
        Generates a list of (base1, base2, a1, a2, b1, b2).  There is
 
332
        always a zero-length sync region at the end of all the files.
 
333
        """
 
334
 
 
335
        ia = ib = 0
 
336
        amatches = bzrlib.patiencediff.PatienceSequenceMatcher(
 
337
                None, self.base, self.a).get_matching_blocks()
 
338
        bmatches = bzrlib.patiencediff.PatienceSequenceMatcher(
 
339
                None, self.base, self.b).get_matching_blocks()
 
340
        len_a = len(amatches)
 
341
        len_b = len(bmatches)
 
342
 
 
343
        sl = []
 
344
 
 
345
        while ia < len_a and ib < len_b:
 
346
            abase, amatch, alen = amatches[ia]
 
347
            bbase, bmatch, blen = bmatches[ib]
 
348
 
 
349
            # there is an unconflicted block at i; how long does it
 
350
            # extend?  until whichever one ends earlier.
 
351
            i = intersect((abase, abase+alen), (bbase, bbase+blen))
 
352
            if i:
 
353
                intbase = i[0]
 
354
                intend = i[1]
 
355
                intlen = intend - intbase
 
356
 
 
357
                # found a match of base[i[0], i[1]]; this may be less than
 
358
                # the region that matches in either one
 
359
                assert intlen <= alen
 
360
                assert intlen <= blen
 
361
                assert abase <= intbase
 
362
                assert bbase <= intbase
 
363
 
 
364
                asub = amatch + (intbase - abase)
 
365
                bsub = bmatch + (intbase - bbase)
 
366
                aend = asub + intlen
 
367
                bend = bsub + intlen
 
368
 
 
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]
 
373
 
 
374
                sl.append((intbase, intend,
 
375
                           asub, aend,
 
376
                           bsub, bend))
 
377
 
 
378
            # advance whichever one ends first in the base text
 
379
            if (abase + alen) < (bbase + blen):
 
380
                ia += 1
 
381
            else:
 
382
                ib += 1
 
383
            
 
384
        intbase = len(self.base)
 
385
        abase = len(self.a)
 
386
        bbase = len(self.b)
 
387
        sl.append((intbase, intbase, abase, abase, bbase, bbase))
 
388
 
 
389
        return sl
 
390
 
 
391
 
 
392
 
 
393
    def find_unconflicted(self):
 
394
        """Return a list of ranges in base that are not conflicted."""
 
395
        am = bzrlib.patiencediff.PatienceSequenceMatcher(
 
396
                None, self.base, self.a).get_matching_blocks()
 
397
        bm = bzrlib.patiencediff.PatienceSequenceMatcher(
 
398
                None, self.base, self.b).get_matching_blocks()
 
399
 
 
400
        unc = []
 
401
 
 
402
        while am and bm:
 
403
            # there is an unconflicted block at i; how long does it
 
404
            # extend?  until whichever one ends earlier.
 
405
            a1 = am[0][0]
 
406
            a2 = a1 + am[0][2]
 
407
            b1 = bm[0][0]
 
408
            b2 = b1 + bm[0][2]
 
409
            i = intersect((a1, a2), (b1, b2))
 
410
            if i:
 
411
                unc.append(i)
 
412
 
 
413
            if a2 < b2:
 
414
                del am[0]
 
415
            else:
 
416
                del bm[0]
 
417
                
 
418
        return unc
 
419
 
 
420
 
 
421
def main(argv):
 
422
    # as for diff3 and meld the syntax is "MINE BASE OTHER"
 
423
    a = file(argv[1], 'rt').readlines()
 
424
    base = file(argv[2], 'rt').readlines()
 
425
    b = file(argv[3], 'rt').readlines()
 
426
 
 
427
    m3 = Merge3(base, a, b)
 
428
 
 
429
    #for sr in m3.find_sync_regions():
 
430
    #    print sr
 
431
 
 
432
    # sys.stdout.writelines(m3.merge_lines(name_a=argv[1], name_b=argv[3]))
 
433
    sys.stdout.writelines(m3.merge_annotated())
 
434
 
 
435
 
 
436
if __name__ == '__main__':
 
437
    import sys
 
438
    sys.exit(main(sys.argv))