/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: Michael Ellerman
  • Date: 2005-10-26 10:03:47 UTC
  • mfrom: (1185.16.116)
  • mto: (1185.16.126)
  • mto: This revision was merged to the branch mainline in revision 1488.
  • Revision ID: michael@ellerman.id.au-20051026100347-bb0b2bd42f7953f2
Merge mainline.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/merge3.py
 
1
# Copyright (C) 2004, 2005 by 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
 
 
23
def intersect(ra, rb):
 
24
    """Given two ranges return the range where they intersect or None.
 
25
 
 
26
    >>> intersect((0, 10), (0, 6))
 
27
    (0, 6)
 
28
    >>> intersect((0, 10), (5, 15))
 
29
    (5, 10)
 
30
    >>> intersect((0, 10), (10, 15))
 
31
    >>> intersect((0, 9), (10, 15))
 
32
    >>> intersect((0, 9), (7, 15))
 
33
    (7, 9)
 
34
    """
 
35
    assert ra[0] <= ra[1]
 
36
    assert rb[0] <= rb[1]
 
37
    
 
38
    sa = max(ra[0], rb[0])
 
39
    sb = min(ra[1], rb[1])
 
40
    if sa < sb:
 
41
        return sa, sb
 
42
    else:
 
43
        return None
 
44
 
 
45
 
 
46
def compare_range(a, astart, aend, b, bstart, bend):
 
47
    """Compare a[astart:aend] == b[bstart:bend], without slicing.
 
48
    """
 
49
    if (aend-astart) != (bend-bstart):
 
50
        return False
 
51
    for ia, ib in zip(xrange(astart, aend), xrange(bstart, bend)):
 
52
        if a[ia] != b[ib]:
 
53
            return False
 
54
    else:
 
55
        return True
 
56
        
 
57
 
 
58
 
 
59
 
 
60
class Merge3(object):
 
61
    """3-way merge of texts.
 
62
 
 
63
    Given BASE, OTHER, THIS, tries to produce a combined text
 
64
    incorporating the changes from both BASE->OTHER and BASE->THIS.
 
65
    All three will typically be sequences of lines."""
 
66
    def __init__(self, base, a, b):
 
67
        self.base = base
 
68
        self.a = a
 
69
        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
 
 
75
 
 
76
    def merge_lines(self,
 
77
                    name_a=None,
 
78
                    name_b=None,
 
79
                    name_base=None,
 
80
                    start_marker='<<<<<<<',
 
81
                    mid_marker='=======',
 
82
                    end_marker='>>>>>>>',
 
83
                    base_marker=None):
 
84
        """Return merge in cvs-like form.
 
85
        """
 
86
        if name_a:
 
87
            start_marker = start_marker + ' ' + name_a
 
88
        if name_b:
 
89
            end_marker = end_marker + ' ' + name_b
 
90
        if name_base and base_marker:
 
91
            base_marker = base_marker + ' ' + name_base
 
92
            
 
93
        for t in self.merge_regions():
 
94
            what = t[0]
 
95
            if what == 'unchanged':
 
96
                for i in range(t[1], t[2]):
 
97
                    yield self.base[i]
 
98
            elif what == 'a' or what == 'same':
 
99
                for i in range(t[1], t[2]):
 
100
                    yield self.a[i]
 
101
            elif what == 'b':
 
102
                for i in range(t[1], t[2]):
 
103
                    yield self.b[i]
 
104
            elif what == 'conflict':
 
105
                yield start_marker + '\n'
 
106
                for i in range(t[3], t[4]):
 
107
                    yield self.a[i]
 
108
                if base_marker is not None:
 
109
                    yield base_marker + '\n'
 
110
                    for i in range(t[1], t[2]):
 
111
                        yield self.base[i]
 
112
                yield mid_marker + '\n'
 
113
                for i in range(t[5], t[6]):
 
114
                    yield self.b[i]
 
115
                yield end_marker + '\n'
 
116
            else:
 
117
                raise ValueError(what)
 
118
        
 
119
        
 
120
 
 
121
 
 
122
 
 
123
    def merge_annotated(self):
 
124
        """Return merge with conflicts, showing origin of lines.
 
125
 
 
126
        Most useful for debugging merge.        
 
127
        """
 
128
        for t in self.merge_regions():
 
129
            what = t[0]
 
130
            if what == 'unchanged':
 
131
                for i in range(t[1], t[2]):
 
132
                    yield 'u | ' + self.base[i]
 
133
            elif what == 'a' or what == 'same':
 
134
                for i in range(t[1], t[2]):
 
135
                    yield what[0] + ' | ' + self.a[i]
 
136
            elif what == 'b':
 
137
                for i in range(t[1], t[2]):
 
138
                    yield 'b | ' + self.b[i]
 
139
            elif what == 'conflict':
 
140
                yield '<<<<\n'
 
141
                for i in range(t[3], t[4]):
 
142
                    yield 'A | ' + self.a[i]
 
143
                yield '----\n'
 
144
                for i in range(t[5], t[6]):
 
145
                    yield 'B | ' + self.b[i]
 
146
                yield '>>>>\n'
 
147
            else:
 
148
                raise ValueError(what)
 
149
        
 
150
        
 
151
 
 
152
 
 
153
 
 
154
    def merge_groups(self):
 
155
        """Yield sequence of line groups.  Each one is a tuple:
 
156
 
 
157
        'unchanged', lines
 
158
             Lines unchanged from base
 
159
 
 
160
        'a', lines
 
161
             Lines taken from a
 
162
 
 
163
        'same', lines
 
164
             Lines taken from a (and equal to b)
 
165
 
 
166
        'b', lines
 
167
             Lines taken from b
 
168
 
 
169
        'conflict', base_lines, a_lines, b_lines
 
170
             Lines from base were changed to either a or b and conflict.
 
171
        """
 
172
        for t in self.merge_regions():
 
173
            what = t[0]
 
174
            if what == 'unchanged':
 
175
                yield what, self.base[t[1]:t[2]]
 
176
            elif what == 'a' or what == 'same':
 
177
                yield what, self.a[t[1]:t[2]]
 
178
            elif what == 'b':
 
179
                yield what, self.b[t[1]:t[2]]
 
180
            elif what == 'conflict':
 
181
                yield (what,
 
182
                       self.base[t[1]:t[2]],
 
183
                       self.a[t[3]:t[4]],
 
184
                       self.b[t[5]:t[6]])
 
185
            else:
 
186
                raise ValueError(what)
 
187
 
 
188
 
 
189
    def merge_regions(self):
 
190
        """Return sequences of matching and conflicting regions.
 
191
 
 
192
        This returns tuples, where the first value says what kind we
 
193
        have:
 
194
 
 
195
        'unchanged', start, end
 
196
             Take a region of base[start:end]
 
197
 
 
198
        'same', astart, aend
 
199
             b and a are different from base but give the same result
 
200
 
 
201
        'a', start, end
 
202
             Non-clashing insertion from a[start:end]
 
203
 
 
204
        Method is as follows:
 
205
 
 
206
        The two sequences align only on regions which match the base
 
207
        and both descendents.  These are found by doing a two-way diff
 
208
        of each one against the base, and then finding the
 
209
        intersections between those regions.  These "sync regions"
 
210
        are by definition unchanged in both and easily dealt with.
 
211
 
 
212
        The regions in between can be in any of three cases:
 
213
        conflicted, or changed on only one side.
 
214
        """
 
215
 
 
216
        # section a[0:ia] has been disposed of, etc
 
217
        iz = ia = ib = 0
 
218
        
 
219
        for zmatch, zend, amatch, aend, bmatch, bend in self.find_sync_regions():
 
220
            #print 'match base [%d:%d]' % (zmatch, zend)
 
221
            
 
222
            matchlen = zend - zmatch
 
223
            assert matchlen >= 0
 
224
            assert matchlen == (aend - amatch)
 
225
            assert matchlen == (bend - bmatch)
 
226
            
 
227
            len_a = amatch - ia
 
228
            len_b = bmatch - ib
 
229
            len_base = zmatch - iz
 
230
            assert len_a >= 0
 
231
            assert len_b >= 0
 
232
            assert len_base >= 0
 
233
 
 
234
            #print 'unmatched a=%d, b=%d' % (len_a, len_b)
 
235
 
 
236
            if len_a or len_b:
 
237
                # try to avoid actually slicing the lists
 
238
                equal_a = compare_range(self.a, ia, amatch,
 
239
                                        self.base, iz, zmatch)
 
240
                equal_b = compare_range(self.b, ib, bmatch,
 
241
                                        self.base, iz, zmatch)
 
242
                same = compare_range(self.a, ia, amatch,
 
243
                                     self.b, ib, bmatch)
 
244
 
 
245
                if same:
 
246
                    yield 'same', ia, amatch
 
247
                elif equal_a and not equal_b:
 
248
                    yield 'b', ib, bmatch
 
249
                elif equal_b and not equal_a:
 
250
                    yield 'a', ia, amatch
 
251
                elif not equal_a and not equal_b:
 
252
                    yield 'conflict', iz, zmatch, ia, amatch, ib, bmatch
 
253
                else:
 
254
                    raise AssertionError("can't handle a=b=base but unmatched")
 
255
 
 
256
                ia = amatch
 
257
                ib = bmatch
 
258
            iz = zmatch
 
259
 
 
260
            # if the same part of the base was deleted on both sides
 
261
            # that's OK, we can just skip it.
 
262
 
 
263
                
 
264
            if matchlen > 0:
 
265
                assert ia == amatch
 
266
                assert ib == bmatch
 
267
                assert iz == zmatch
 
268
                
 
269
                yield 'unchanged', zmatch, zend
 
270
                iz = zend
 
271
                ia = aend
 
272
                ib = bend
 
273
        
 
274
 
 
275
        
 
276
    def find_sync_regions(self):
 
277
        """Return a list of sync regions, where both descendents match the base.
 
278
 
 
279
        Generates a list of (base1, base2, a1, a2, b1, b2).  There is
 
280
        always a zero-length sync region at the end of all the files.
 
281
        """
 
282
        from difflib import SequenceMatcher
 
283
 
 
284
        ia = ib = 0
 
285
        amatches = SequenceMatcher(None, self.base, self.a).get_matching_blocks()
 
286
        bmatches = SequenceMatcher(None, self.base, self.b).get_matching_blocks()
 
287
        len_a = len(amatches)
 
288
        len_b = len(bmatches)
 
289
 
 
290
        sl = []
 
291
 
 
292
        while ia < len_a and ib < len_b:
 
293
            abase, amatch, alen = amatches[ia]
 
294
            bbase, bmatch, blen = bmatches[ib]
 
295
 
 
296
            # there is an unconflicted block at i; how long does it
 
297
            # extend?  until whichever one ends earlier.
 
298
            i = intersect((abase, abase+alen), (bbase, bbase+blen))
 
299
            if i:
 
300
                intbase = i[0]
 
301
                intend = i[1]
 
302
                intlen = intend - intbase
 
303
 
 
304
                # found a match of base[i[0], i[1]]; this may be less than
 
305
                # the region that matches in either one
 
306
                assert intlen <= alen
 
307
                assert intlen <= blen
 
308
                assert abase <= intbase
 
309
                assert bbase <= intbase
 
310
 
 
311
                asub = amatch + (intbase - abase)
 
312
                bsub = bmatch + (intbase - bbase)
 
313
                aend = asub + intlen
 
314
                bend = bsub + intlen
 
315
 
 
316
                assert self.base[intbase:intend] == self.a[asub:aend], \
 
317
                       (self.base[intbase:intend], self.a[asub:aend])
 
318
 
 
319
                assert self.base[intbase:intend] == self.b[bsub:bend]
 
320
 
 
321
                sl.append((intbase, intend,
 
322
                           asub, aend,
 
323
                           bsub, bend))
 
324
 
 
325
            # advance whichever one ends first in the base text
 
326
            if (abase + alen) < (bbase + blen):
 
327
                ia += 1
 
328
            else:
 
329
                ib += 1
 
330
            
 
331
        intbase = len(self.base)
 
332
        abase = len(self.a)
 
333
        bbase = len(self.b)
 
334
        sl.append((intbase, intbase, abase, abase, bbase, bbase))
 
335
 
 
336
        return sl
 
337
 
 
338
 
 
339
 
 
340
    def find_unconflicted(self):
 
341
        """Return a list of ranges in base that are not conflicted."""
 
342
        from difflib import SequenceMatcher
 
343
 
 
344
        import re
 
345
 
 
346
        # don't sync-up on lines containing only blanks or pounds
 
347
        junk_re = re.compile(r'^[ \t#]*$')
 
348
        
 
349
        am = SequenceMatcher(junk_re.match, self.base, self.a).get_matching_blocks()
 
350
        bm = SequenceMatcher(junk_re.match, self.base, self.b).get_matching_blocks()
 
351
 
 
352
        unc = []
 
353
 
 
354
        while am and bm:
 
355
            # there is an unconflicted block at i; how long does it
 
356
            # extend?  until whichever one ends earlier.
 
357
            a1 = am[0][0]
 
358
            a2 = a1 + am[0][2]
 
359
            b1 = bm[0][0]
 
360
            b2 = b1 + bm[0][2]
 
361
            i = intersect((a1, a2), (b1, b2))
 
362
            if i:
 
363
                unc.append(i)
 
364
 
 
365
            if a2 < b2:
 
366
                del am[0]
 
367
            else:
 
368
                del bm[0]
 
369
                
 
370
        return unc
 
371
 
 
372
 
 
373
def main(argv):
 
374
    # as for diff3 and meld the syntax is "MINE BASE OTHER"
 
375
    a = file(argv[1], 'rt').readlines()
 
376
    base = file(argv[2], 'rt').readlines()
 
377
    b = file(argv[3], 'rt').readlines()
 
378
 
 
379
    m3 = Merge3(base, a, b)
 
380
 
 
381
    #for sr in m3.find_sync_regions():
 
382
    #    print sr
 
383
 
 
384
    # sys.stdout.writelines(m3.merge_lines(name_a=argv[1], name_b=argv[3]))
 
385
    sys.stdout.writelines(m3.merge_annotated())
 
386
 
 
387
 
 
388
if __name__ == '__main__':
 
389
    import sys
 
390
    sys.exit(main(sys.argv))