1
# Copyright (C) 2005-2010 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
17
from __future__ import absolute_import
19
# mbp: "you know that thing where cvs gives you conflict markers?"
31
class CantReprocessAndShowBase(errors.BzrError):
33
_fmt = ("Can't reprocess and show base, because reprocessing obscures "
34
"the relationship of conflicting lines to the base")
37
def intersect(ra, rb):
38
"""Given two ranges return the range where they intersect or None.
40
>>> intersect((0, 10), (0, 6))
42
>>> intersect((0, 10), (5, 15))
44
>>> intersect((0, 10), (10, 15))
45
>>> intersect((0, 9), (10, 15))
46
>>> intersect((0, 9), (7, 15))
49
# preconditions: (ra[0] <= ra[1]) and (rb[0] <= rb[1])
51
sa = max(ra[0], rb[0])
52
sb = min(ra[1], rb[1])
59
def compare_range(a, astart, aend, b, bstart, bend):
60
"""Compare a[astart:aend] == b[bstart:bend], without slicing.
62
if (aend - astart) != (bend - bstart):
64
for ia, ib in zip(range(astart, aend), range(bstart, bend)):
72
"""3-way merge of texts.
74
Given BASE, OTHER, THIS, tries to produce a combined text
75
incorporating the changes from both BASE->OTHER and BASE->THIS.
76
All three will typically be sequences of lines."""
78
def __init__(self, base, a, b, is_cherrypick=False, allow_objects=False):
81
:param base: lines in BASE
84
:param is_cherrypick: flag indicating if this merge is a cherrypick.
85
When cherrypicking b => a, matches with b and base do not conflict.
86
:param allow_objects: if True, do not require that base, a and b are
87
plain Python strs. Also prevents BinaryFile from being raised.
88
Lines can be any sequence of comparable and hashable Python
92
textfile.check_text_lines(base)
93
textfile.check_text_lines(a)
94
textfile.check_text_lines(b)
98
self.is_cherrypick = is_cherrypick
100
def merge_lines(self,
104
start_marker=b'<<<<<<<',
105
mid_marker=b'=======',
106
end_marker=b'>>>>>>>',
109
"""Return merge in cvs-like form.
113
if self.a[0].endswith(b'\r\n'):
115
elif self.a[0].endswith(b'\r'):
117
if base_marker and reprocess:
118
raise CantReprocessAndShowBase()
120
start_marker = start_marker + b' ' + name_a
122
end_marker = end_marker + b' ' + name_b
123
if name_base and base_marker:
124
base_marker = base_marker + b' ' + name_base
125
merge_regions = self.merge_regions()
126
if reprocess is True:
127
merge_regions = self.reprocess_merge_regions(merge_regions)
128
for t in merge_regions:
130
if what == 'unchanged':
131
for i in range(t[1], t[2]):
133
elif what == 'a' or what == 'same':
134
for i in range(t[1], t[2]):
137
for i in range(t[1], t[2]):
139
elif what == 'conflict':
140
yield start_marker + newline
141
for i in range(t[3], t[4]):
143
if base_marker is not None:
144
yield base_marker + newline
145
for i in range(t[1], t[2]):
147
yield mid_marker + newline
148
for i in range(t[5], t[6]):
150
yield end_marker + newline
152
raise ValueError(what)
154
def merge_annotated(self):
155
"""Return merge with conflicts, showing origin of lines.
157
Most useful for debugging merge.
159
for t in self.merge_regions():
161
if what == 'unchanged':
162
for i in range(t[1], t[2]):
163
yield 'u | ' + self.base[i]
164
elif what == 'a' or what == 'same':
165
for i in range(t[1], t[2]):
166
yield what[0] + ' | ' + self.a[i]
168
for i in range(t[1], t[2]):
169
yield 'b | ' + self.b[i]
170
elif what == 'conflict':
172
for i in range(t[3], t[4]):
173
yield 'A | ' + self.a[i]
175
for i in range(t[5], t[6]):
176
yield 'B | ' + self.b[i]
179
raise ValueError(what)
181
def merge_groups(self):
182
"""Yield sequence of line groups. Each one is a tuple:
185
Lines unchanged from base
191
Lines taken from a (and equal to b)
196
'conflict', base_lines, a_lines, b_lines
197
Lines from base were changed to either a or b and conflict.
199
for t in self.merge_regions():
201
if what == 'unchanged':
202
yield what, self.base[t[1]:t[2]]
203
elif what == 'a' or what == 'same':
204
yield what, self.a[t[1]:t[2]]
206
yield what, self.b[t[1]:t[2]]
207
elif what == 'conflict':
209
self.base[t[1]:t[2]],
213
raise ValueError(what)
215
def merge_regions(self):
216
"""Return sequences of matching and conflicting regions.
218
This returns tuples, where the first value says what kind we
221
'unchanged', start, end
222
Take a region of base[start:end]
225
b and a are different from base but give the same result
228
Non-clashing insertion from a[start:end]
230
Method is as follows:
232
The two sequences align only on regions which match the base
233
and both descendents. These are found by doing a two-way diff
234
of each one against the base, and then finding the
235
intersections between those regions. These "sync regions"
236
are by definition unchanged in both and easily dealt with.
238
The regions in between can be in any of three cases:
239
conflicted, or changed on only one side.
242
# section a[0:ia] has been disposed of, etc
245
for zmatch, zend, amatch, aend, bmatch, bend in self.find_sync_regions():
246
matchlen = zend - zmatch
249
# matchlen == (aend - amatch)
250
# matchlen == (bend - bmatch)
257
# print 'unmatched a=%d, b=%d' % (len_a, len_b)
260
# try to avoid actually slicing the lists
261
same = compare_range(self.a, ia, amatch,
265
yield 'same', ia, amatch
267
equal_a = compare_range(self.a, ia, amatch,
268
self.base, iz, zmatch)
269
equal_b = compare_range(self.b, ib, bmatch,
270
self.base, iz, zmatch)
271
if equal_a and not equal_b:
272
yield 'b', ib, bmatch
273
elif equal_b and not equal_a:
274
yield 'a', ia, amatch
275
elif not equal_a and not equal_b:
276
if self.is_cherrypick:
277
for node in self._refine_cherrypick_conflict(
278
iz, zmatch, ia, amatch,
282
yield ('conflict', iz, zmatch, ia, amatch, ib,
285
raise AssertionError(
286
"can't handle a=b=base but unmatched")
292
# if the same part of the base was deleted on both sides
293
# that's OK, we can just skip it.
297
# assert ia == amatch
298
# assert ib == bmatch
299
# assert iz == zmatch
301
yield 'unchanged', zmatch, zend
306
def _refine_cherrypick_conflict(self, zstart, zend, astart, aend, bstart,
308
"""When cherrypicking b => a, ignore matches with b and base."""
309
# Do not emit regions which match, only regions which do not match
310
matches = patiencediff.PatienceSequenceMatcher(
311
None, self.base[zstart:zend], self.b[bstart:bend]
312
).get_matching_blocks()
317
for base_idx, b_idx, match_len in matches:
318
conflict_b_len = b_idx - last_b_idx
319
if conflict_b_len == 0:
320
# There are no lines in b which conflict, so skip it
325
zstart + last_base_idx, zstart + base_idx,
326
aend, aend, bstart + last_b_idx, bstart + b_idx)
328
# The first conflict gets the a-range
330
yield ('conflict', zstart + last_base_idx, zstart +
332
astart, aend, bstart + last_b_idx, bstart + b_idx)
333
last_base_idx = base_idx + match_len
334
last_b_idx = b_idx + match_len
335
if last_base_idx != zend - zstart or last_b_idx != bend - bstart:
337
yield ('conflict', zstart + last_base_idx, zstart + base_idx,
338
aend, aend, bstart + last_b_idx, bstart + b_idx)
340
# The first conflict gets the a-range
342
yield ('conflict', zstart + last_base_idx, zstart + base_idx,
343
astart, aend, bstart + last_b_idx, bstart + b_idx)
345
yield ('conflict', zstart, zend, astart, aend, bstart, bend)
347
def reprocess_merge_regions(self, merge_regions):
348
"""Where there are conflict regions, remove the agreed lines.
350
Lines where both A and B have made the same changes are
353
for region in merge_regions:
354
if region[0] != "conflict":
357
type, iz, zmatch, ia, amatch, ib, bmatch = region
358
a_region = self.a[ia:amatch]
359
b_region = self.b[ib:bmatch]
360
matches = patiencediff.PatienceSequenceMatcher(
361
None, a_region, b_region).get_matching_blocks()
364
for region_ia, region_ib, region_len in matches[:-1]:
367
reg = self.mismatch_region(next_a, region_ia, next_b,
371
yield 'same', region_ia, region_len + region_ia
372
next_a = region_ia + region_len
373
next_b = region_ib + region_len
374
reg = self.mismatch_region(next_a, amatch, next_b, bmatch)
379
def mismatch_region(next_a, region_ia, next_b, region_ib):
380
if next_a < region_ia or next_b < region_ib:
381
return 'conflict', None, None, next_a, region_ia, next_b, region_ib
383
def find_sync_regions(self):
384
"""Return a list of sync regions, where both descendents match the base.
386
Generates a list of (base1, base2, a1, a2, b1, b2). There is
387
always a zero-length sync region at the end of all the files.
391
amatches = patiencediff.PatienceSequenceMatcher(
392
None, self.base, self.a).get_matching_blocks()
393
bmatches = patiencediff.PatienceSequenceMatcher(
394
None, self.base, self.b).get_matching_blocks()
395
len_a = len(amatches)
396
len_b = len(bmatches)
400
while ia < len_a and ib < len_b:
401
abase, amatch, alen = amatches[ia]
402
bbase, bmatch, blen = bmatches[ib]
404
# there is an unconflicted block at i; how long does it
405
# extend? until whichever one ends earlier.
406
i = intersect((abase, abase + alen), (bbase, bbase + blen))
410
intlen = intend - intbase
412
# found a match of base[i[0], i[1]]; this may be less than
413
# the region that matches in either one
414
# assert intlen <= alen
415
# assert intlen <= blen
416
# assert abase <= intbase
417
# assert bbase <= intbase
419
asub = amatch + (intbase - abase)
420
bsub = bmatch + (intbase - bbase)
424
# assert self.base[intbase:intend] == self.a[asub:aend], \
425
# (self.base[intbase:intend], self.a[asub:aend])
426
# assert self.base[intbase:intend] == self.b[bsub:bend]
428
sl.append((intbase, intend,
431
# advance whichever one ends first in the base text
432
if (abase + alen) < (bbase + blen):
437
intbase = len(self.base)
440
sl.append((intbase, intbase, abase, abase, bbase, bbase))
444
def find_unconflicted(self):
445
"""Return a list of ranges in base that are not conflicted."""
446
am = patiencediff.PatienceSequenceMatcher(
447
None, self.base, self.a).get_matching_blocks()
448
bm = patiencediff.PatienceSequenceMatcher(
449
None, self.base, self.b).get_matching_blocks()
454
# there is an unconflicted block at i; how long does it
455
# extend? until whichever one ends earlier.
460
i = intersect((a1, a2), (b1, b2))
473
# as for diff3 and meld the syntax is "MINE BASE OTHER"
474
with open(argv[1], 'rt') as f:
476
with open(argv[2], 'rt') as f:
478
with open(argv[3], 'rt') as f:
481
m3 = Merge3(base, a, b)
483
# for sr in m3.find_sync_regions():
486
# sys.stdout.writelines(m3.merge_lines(name_a=argv[1], name_b=argv[3]))
487
sys.stdout.writelines(m3.merge_annotated())
490
if __name__ == '__main__':
492
sys.exit(main(sys.argv))
added
removed
breezy/merge3.py
