1
# Copyright (C) 2004, 2005 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 bzrlib.errors import CantReprocessAndShowBase
23
import bzrlib.patiencediff
24
from bzrlib.textfile import check_text_lines
27
def intersect(ra, rb):
28
"""Given two ranges return the range where they intersect or None.
30
>>> intersect((0, 10), (0, 6))
32
>>> intersect((0, 10), (5, 15))
34
>>> intersect((0, 10), (10, 15))
35
>>> intersect((0, 9), (10, 15))
36
>>> intersect((0, 9), (7, 15))
42
sa = max(ra[0], rb[0])
43
sb = min(ra[1], rb[1])
50
def compare_range(a, astart, aend, b, bstart, bend):
51
"""Compare a[astart:aend] == b[bstart:bend], without slicing.
53
if (aend-astart) != (bend-bstart):
55
for ia, ib in zip(xrange(astart, aend), xrange(bstart, bend)):
65
"""3-way merge of texts.
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)
84
start_marker='<<<<<<<',
89
"""Return merge in cvs-like form.
93
if self.a[0].endswith('\r\n'):
95
elif self.a[0].endswith('\r'):
97
if base_marker and reprocess:
98
raise CantReprocessAndShowBase()
100
start_marker = start_marker + ' ' + name_a
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:
110
if what == 'unchanged':
111
for i in range(t[1], t[2]):
113
elif what == 'a' or what == 'same':
114
for i in range(t[1], t[2]):
117
for i in range(t[1], t[2]):
119
elif what == 'conflict':
120
yield start_marker + newline
121
for i in range(t[3], t[4]):
123
if base_marker is not None:
124
yield base_marker + newline
125
for i in range(t[1], t[2]):
127
yield mid_marker + newline
128
for i in range(t[5], t[6]):
130
yield end_marker + newline
132
raise ValueError(what)
138
def merge_annotated(self):
139
"""Return merge with conflicts, showing origin of lines.
141
Most useful for debugging merge.
143
for t in self.merge_regions():
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]
152
for i in range(t[1], t[2]):
153
yield 'b | ' + self.b[i]
154
elif what == 'conflict':
156
for i in range(t[3], t[4]):
157
yield 'A | ' + self.a[i]
159
for i in range(t[5], t[6]):
160
yield 'B | ' + self.b[i]
163
raise ValueError(what)
169
def merge_groups(self):
170
"""Yield sequence of line groups. Each one is a tuple:
173
Lines unchanged from base
179
Lines taken from a (and equal to b)
184
'conflict', base_lines, a_lines, b_lines
185
Lines from base were changed to either a or b and conflict.
187
for t in self.merge_regions():
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]]
194
yield what, self.b[t[1]:t[2]]
195
elif what == 'conflict':
197
self.base[t[1]:t[2]],
201
raise ValueError(what)
204
def merge_regions(self):
205
"""Return sequences of matching and conflicting regions.
207
This returns tuples, where the first value says what kind we
210
'unchanged', start, end
211
Take a region of base[start:end]
214
b and a are different from base but give the same result
217
Non-clashing insertion from a[start:end]
219
Method is as follows:
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.
227
The regions in between can be in any of three cases:
228
conflicted, or changed on only one side.
231
# section a[0:ia] has been disposed of, etc
234
for zmatch, zend, amatch, aend, bmatch, bend in self.find_sync_regions():
235
#print 'match base [%d:%d]' % (zmatch, zend)
237
matchlen = zend - zmatch
239
assert matchlen == (aend - amatch)
240
assert matchlen == (bend - bmatch)
244
len_base = zmatch - iz
249
#print 'unmatched a=%d, b=%d' % (len_a, 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,
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
269
raise AssertionError("can't handle a=b=base but unmatched")
275
# if the same part of the base was deleted on both sides
276
# that's OK, we can just skip it.
284
yield 'unchanged', zmatch, zend
290
def reprocess_merge_regions(self, merge_regions):
291
"""Where there are conflict regions, remove the agreed lines.
293
Lines where both A and B have made the same changes are
296
for region in merge_regions:
297
if region[0] != "conflict":
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()
307
for region_ia, region_ib, region_len in matches[:-1]:
310
reg = self.mismatch_region(next_a, region_ia, next_b,
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)
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
328
def find_sync_regions(self):
329
"""Return a list of sync regions, where both descendents match the base.
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.
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)
345
while ia < len_a and ib < len_b:
346
abase, amatch, alen = amatches[ia]
347
bbase, bmatch, blen = bmatches[ib]
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))
355
intlen = intend - intbase
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
364
asub = amatch + (intbase - abase)
365
bsub = bmatch + (intbase - bbase)
369
assert self.base[intbase:intend] == self.a[asub:aend], \
370
(self.base[intbase:intend], self.a[asub:aend])
372
assert self.base[intbase:intend] == self.b[bsub:bend]
374
sl.append((intbase, intend,
378
# advance whichever one ends first in the base text
379
if (abase + alen) < (bbase + blen):
384
intbase = len(self.base)
387
sl.append((intbase, intbase, abase, abase, bbase, bbase))
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()
403
# there is an unconflicted block at i; how long does it
404
# extend? until whichever one ends earlier.
409
i = intersect((a1, a2), (b1, b2))
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()
427
m3 = Merge3(base, a, b)
429
#for sr in m3.find_sync_regions():
432
# sys.stdout.writelines(m3.merge_lines(name_a=argv[1], name_b=argv[3]))
433
sys.stdout.writelines(m3.merge_annotated())
436
if __name__ == '__main__':
438
sys.exit(main(sys.argv))
added
removed
bzrlib/merge3.py
