/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: Aaron Bentley
  • Date: 2005-10-22 23:23:56 UTC
  • mto: (1185.25.1)
  • mto: This revision was merged to the branch mainline in revision 1488.
  • Revision ID: aaron.bentley@utoronto.ca-20051022232356-861a8b02872b132f
Added mode preservation to AtomicFile

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