1
# Copyright (C) 2004, 2005 by Canonical Ltd
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.
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.
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
18
# mbp: "you know that thing where cvs gives you conflict markers?"
22
from difflib import SequenceMatcher
23
from bzrlib.errors import CantReprocessAndShowBase
24
from textfile import check_text_lines
26
def intersect(ra, rb):
27
"""Given two ranges return the range where they intersect or None.
29
>>> intersect((0, 10), (0, 6))
31
>>> intersect((0, 10), (5, 15))
33
>>> intersect((0, 10), (10, 15))
34
>>> intersect((0, 9), (10, 15))
35
>>> intersect((0, 9), (7, 15))
41
sa = max(ra[0], rb[0])
42
sb = min(ra[1], rb[1])
49
def compare_range(a, astart, aend, b, bstart, bend):
50
"""Compare a[astart:aend] == b[bstart:bend], without slicing.
52
if (aend-astart) != (bend-bstart):
54
for ia, ib in zip(xrange(astart, aend), xrange(bstart, bend)):
64
"""3-way merge of texts.
66
Given BASE, OTHER, THIS, tries to produce a combined text
67
incorporating the changes from both BASE->OTHER and BASE->THIS.
68
All three will typically be sequences of lines."""
69
def __init__(self, base, a, b):
70
check_text_lines(base)
83
start_marker='<<<<<<<',
88
"""Return merge in cvs-like form.
90
if base_marker and reprocess:
91
raise CantReprocessAndShowBase()
93
start_marker = start_marker + ' ' + name_a
95
end_marker = end_marker + ' ' + name_b
96
if name_base and base_marker:
97
base_marker = base_marker + ' ' + name_base
98
merge_regions = self.merge_regions()
100
merge_regions = self.reprocess_merge_regions(merge_regions)
101
for t in merge_regions:
103
if what == 'unchanged':
104
for i in range(t[1], t[2]):
106
elif what == 'a' or what == 'same':
107
for i in range(t[1], t[2]):
110
for i in range(t[1], t[2]):
112
elif what == 'conflict':
113
yield start_marker + '\n'
114
for i in range(t[3], t[4]):
116
if base_marker is not None:
117
yield base_marker + '\n'
118
for i in range(t[1], t[2]):
120
yield mid_marker + '\n'
121
for i in range(t[5], t[6]):
123
yield end_marker + '\n'
125
raise ValueError(what)
131
def merge_annotated(self):
132
"""Return merge with conflicts, showing origin of lines.
134
Most useful for debugging merge.
136
for t in self.merge_regions():
138
if what == 'unchanged':
139
for i in range(t[1], t[2]):
140
yield 'u | ' + self.base[i]
141
elif what == 'a' or what == 'same':
142
for i in range(t[1], t[2]):
143
yield what[0] + ' | ' + self.a[i]
145
for i in range(t[1], t[2]):
146
yield 'b | ' + self.b[i]
147
elif what == 'conflict':
149
for i in range(t[3], t[4]):
150
yield 'A | ' + self.a[i]
152
for i in range(t[5], t[6]):
153
yield 'B | ' + self.b[i]
156
raise ValueError(what)
162
def merge_groups(self):
163
"""Yield sequence of line groups. Each one is a tuple:
166
Lines unchanged from base
172
Lines taken from a (and equal to b)
177
'conflict', base_lines, a_lines, b_lines
178
Lines from base were changed to either a or b and conflict.
180
for t in self.merge_regions():
182
if what == 'unchanged':
183
yield what, self.base[t[1]:t[2]]
184
elif what == 'a' or what == 'same':
185
yield what, self.a[t[1]:t[2]]
187
yield what, self.b[t[1]:t[2]]
188
elif what == 'conflict':
190
self.base[t[1]:t[2]],
194
raise ValueError(what)
197
def merge_regions(self):
198
"""Return sequences of matching and conflicting regions.
200
This returns tuples, where the first value says what kind we
203
'unchanged', start, end
204
Take a region of base[start:end]
207
b and a are different from base but give the same result
210
Non-clashing insertion from a[start:end]
212
Method is as follows:
214
The two sequences align only on regions which match the base
215
and both descendents. These are found by doing a two-way diff
216
of each one against the base, and then finding the
217
intersections between those regions. These "sync regions"
218
are by definition unchanged in both and easily dealt with.
220
The regions in between can be in any of three cases:
221
conflicted, or changed on only one side.
224
# section a[0:ia] has been disposed of, etc
227
for zmatch, zend, amatch, aend, bmatch, bend in self.find_sync_regions():
228
#print 'match base [%d:%d]' % (zmatch, zend)
230
matchlen = zend - zmatch
232
assert matchlen == (aend - amatch)
233
assert matchlen == (bend - bmatch)
237
len_base = zmatch - iz
242
#print 'unmatched a=%d, b=%d' % (len_a, len_b)
245
# try to avoid actually slicing the lists
246
equal_a = compare_range(self.a, ia, amatch,
247
self.base, iz, zmatch)
248
equal_b = compare_range(self.b, ib, bmatch,
249
self.base, iz, zmatch)
250
same = compare_range(self.a, ia, amatch,
254
yield 'same', ia, amatch
255
elif equal_a and not equal_b:
256
yield 'b', ib, bmatch
257
elif equal_b and not equal_a:
258
yield 'a', ia, amatch
259
elif not equal_a and not equal_b:
260
yield 'conflict', iz, zmatch, ia, amatch, ib, bmatch
262
raise AssertionError("can't handle a=b=base but unmatched")
268
# if the same part of the base was deleted on both sides
269
# that's OK, we can just skip it.
277
yield 'unchanged', zmatch, zend
283
def reprocess_merge_regions(self, merge_regions):
284
"""Where there are conflict regions, remove the agreed lines.
286
Lines where both A and B have made the same changes are
289
for region in merge_regions:
290
if region[0] != "conflict":
293
type, iz, zmatch, ia, amatch, ib, bmatch = region
294
a_region = self.a[ia:amatch]
295
b_region = self.b[ib:bmatch]
296
matches = SequenceMatcher(None, a_region,
297
b_region).get_matching_blocks()
300
for region_ia, region_ib, region_len in matches[:-1]:
303
reg = self.mismatch_region(next_a, region_ia, next_b,
307
yield 'same', region_ia, region_len+region_ia
308
next_a = region_ia + region_len
309
next_b = region_ib + region_len
310
reg = self.mismatch_region(next_a, amatch, next_b, bmatch)
316
def mismatch_region(next_a, region_ia, next_b, region_ib):
317
if next_a < region_ia or next_b < region_ib:
318
return 'conflict', None, None, next_a, region_ia, next_b, region_ib
321
def find_sync_regions(self):
322
"""Return a list of sync regions, where both descendents match the base.
324
Generates a list of (base1, base2, a1, a2, b1, b2). There is
325
always a zero-length sync region at the end of all the files.
329
amatches = SequenceMatcher(None, self.base, self.a).get_matching_blocks()
330
bmatches = SequenceMatcher(None, self.base, self.b).get_matching_blocks()
331
len_a = len(amatches)
332
len_b = len(bmatches)
336
while ia < len_a and ib < len_b:
337
abase, amatch, alen = amatches[ia]
338
bbase, bmatch, blen = bmatches[ib]
340
# there is an unconflicted block at i; how long does it
341
# extend? until whichever one ends earlier.
342
i = intersect((abase, abase+alen), (bbase, bbase+blen))
346
intlen = intend - intbase
348
# found a match of base[i[0], i[1]]; this may be less than
349
# the region that matches in either one
350
assert intlen <= alen
351
assert intlen <= blen
352
assert abase <= intbase
353
assert bbase <= intbase
355
asub = amatch + (intbase - abase)
356
bsub = bmatch + (intbase - bbase)
360
assert self.base[intbase:intend] == self.a[asub:aend], \
361
(self.base[intbase:intend], self.a[asub:aend])
363
assert self.base[intbase:intend] == self.b[bsub:bend]
365
sl.append((intbase, intend,
369
# advance whichever one ends first in the base text
370
if (abase + alen) < (bbase + blen):
375
intbase = len(self.base)
378
sl.append((intbase, intbase, abase, abase, bbase, bbase))
384
def find_unconflicted(self):
385
"""Return a list of ranges in base that are not conflicted."""
389
# don't sync-up on lines containing only blanks or pounds
390
junk_re = re.compile(r'^[ \t#]*$')
392
am = SequenceMatcher(junk_re.match, self.base, self.a).get_matching_blocks()
393
bm = SequenceMatcher(junk_re.match, self.base, self.b).get_matching_blocks()
398
# there is an unconflicted block at i; how long does it
399
# extend? until whichever one ends earlier.
404
i = intersect((a1, a2), (b1, b2))
417
# as for diff3 and meld the syntax is "MINE BASE OTHER"
418
a = file(argv[1], 'rt').readlines()
419
base = file(argv[2], 'rt').readlines()
420
b = file(argv[3], 'rt').readlines()
422
m3 = Merge3(base, a, b)
424
#for sr in m3.find_sync_regions():
427
# sys.stdout.writelines(m3.merge_lines(name_a=argv[1], name_b=argv[3]))
428
sys.stdout.writelines(m3.merge_annotated())
431
if __name__ == '__main__':
433
sys.exit(main(sys.argv))
added
removed
bzrlib/merge3.py
