simplemerge.py
397 lines
| 12.5 KiB
| text/x-python
|
PythonLexer
/ mercurial / simplemerge.py
|
r6002 | # Copyright (C) 2004, 2005 Canonical Ltd | ||
# | ||||
# This program is free software; you can redistribute it and/or modify | ||||
# it under the terms of the GNU General Public License as published by | ||||
# the Free Software Foundation; either version 2 of the License, or | ||||
# (at your option) any later version. | ||||
# | ||||
# This program is distributed in the hope that it will be useful, | ||||
# but WITHOUT ANY WARRANTY; without even the implied warranty of | ||||
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||||
# GNU General Public License for more details. | ||||
# | ||||
# You should have received a copy of the GNU General Public License | ||||
|
r15782 | # along with this program; if not, see <http://www.gnu.org/licenses/>. | ||
|
r6002 | |||
# mbp: "you know that thing where cvs gives you conflict markers?" | ||||
# s: "i hate that." | ||||
|
r25974 | from __future__ import absolute_import | ||
import os | ||||
import sys | ||||
from .i18n import _ | ||||
from . import ( | ||||
mdiff, | ||||
scmutil, | ||||
util, | ||||
) | ||||
|
r6002 | |||
class CantReprocessAndShowBase(Exception): | ||||
pass | ||||
def intersect(ra, rb): | ||||
"""Given two ranges return the range where they intersect or None. | ||||
>>> intersect((0, 10), (0, 6)) | ||||
(0, 6) | ||||
>>> intersect((0, 10), (5, 15)) | ||||
(5, 10) | ||||
>>> intersect((0, 10), (10, 15)) | ||||
>>> intersect((0, 9), (10, 15)) | ||||
>>> intersect((0, 9), (7, 15)) | ||||
(7, 9) | ||||
""" | ||||
assert ra[0] <= ra[1] | ||||
assert rb[0] <= rb[1] | ||||
sa = max(ra[0], rb[0]) | ||||
sb = min(ra[1], rb[1]) | ||||
if sa < sb: | ||||
return sa, sb | ||||
else: | ||||
return None | ||||
def compare_range(a, astart, aend, b, bstart, bend): | ||||
"""Compare a[astart:aend] == b[bstart:bend], without slicing. | ||||
""" | ||||
|
r10282 | if (aend - astart) != (bend - bstart): | ||
|
r6002 | return False | ||
for ia, ib in zip(xrange(astart, aend), xrange(bstart, bend)): | ||||
if a[ia] != b[ib]: | ||||
return False | ||||
else: | ||||
return True | ||||
class Merge3Text(object): | ||||
"""3-way merge of texts. | ||||
Given strings BASE, OTHER, THIS, tries to produce a combined text | ||||
incorporating the changes from both BASE->OTHER and BASE->THIS.""" | ||||
def __init__(self, basetext, atext, btext, base=None, a=None, b=None): | ||||
self.basetext = basetext | ||||
self.atext = atext | ||||
self.btext = btext | ||||
if base is None: | ||||
base = mdiff.splitnewlines(basetext) | ||||
if a is None: | ||||
a = mdiff.splitnewlines(atext) | ||||
if b is None: | ||||
b = mdiff.splitnewlines(btext) | ||||
self.base = base | ||||
self.a = a | ||||
self.b = b | ||||
def merge_lines(self, | ||||
name_a=None, | ||||
name_b=None, | ||||
name_base=None, | ||||
start_marker='<<<<<<<', | ||||
mid_marker='=======', | ||||
end_marker='>>>>>>>', | ||||
|
r22023 | base_marker=None): | ||
|
r6002 | """Return merge in cvs-like form. | ||
""" | ||||
self.conflicts = False | ||||
newline = '\n' | ||||
if len(self.a) > 0: | ||||
if self.a[0].endswith('\r\n'): | ||||
newline = '\r\n' | ||||
elif self.a[0].endswith('\r'): | ||||
newline = '\r' | ||||
if name_a: | ||||
start_marker = start_marker + ' ' + name_a | ||||
if name_b: | ||||
end_marker = end_marker + ' ' + name_b | ||||
if name_base and base_marker: | ||||
base_marker = base_marker + ' ' + name_base | ||||
merge_regions = self.merge_regions() | ||||
for t in merge_regions: | ||||
what = t[0] | ||||
if what == 'unchanged': | ||||
for i in range(t[1], t[2]): | ||||
yield self.base[i] | ||||
|
r12401 | elif what == 'a' or what == 'same': | ||
|
r6002 | for i in range(t[1], t[2]): | ||
yield self.a[i] | ||||
elif what == 'b': | ||||
for i in range(t[1], t[2]): | ||||
yield self.b[i] | ||||
elif what == 'conflict': | ||||
self.conflicts = True | ||||
yield start_marker + newline | ||||
for i in range(t[3], t[4]): | ||||
yield self.a[i] | ||||
if base_marker is not None: | ||||
yield base_marker + newline | ||||
for i in range(t[1], t[2]): | ||||
yield self.base[i] | ||||
yield mid_marker + newline | ||||
for i in range(t[5], t[6]): | ||||
yield self.b[i] | ||||
yield end_marker + newline | ||||
else: | ||||
raise ValueError(what) | ||||
def merge_groups(self): | ||||
"""Yield sequence of line groups. Each one is a tuple: | ||||
'unchanged', lines | ||||
Lines unchanged from base | ||||
'a', lines | ||||
Lines taken from a | ||||
'same', lines | ||||
Lines taken from a (and equal to b) | ||||
'b', lines | ||||
Lines taken from b | ||||
'conflict', base_lines, a_lines, b_lines | ||||
Lines from base were changed to either a or b and conflict. | ||||
""" | ||||
for t in self.merge_regions(): | ||||
what = t[0] | ||||
if what == 'unchanged': | ||||
yield what, self.base[t[1]:t[2]] | ||||
|
r12401 | elif what == 'a' or what == 'same': | ||
|
r6002 | yield what, self.a[t[1]:t[2]] | ||
elif what == 'b': | ||||
yield what, self.b[t[1]:t[2]] | ||||
elif what == 'conflict': | ||||
yield (what, | ||||
self.base[t[1]:t[2]], | ||||
self.a[t[3]:t[4]], | ||||
self.b[t[5]:t[6]]) | ||||
else: | ||||
raise ValueError(what) | ||||
def merge_regions(self): | ||||
"""Return sequences of matching and conflicting regions. | ||||
This returns tuples, where the first value says what kind we | ||||
have: | ||||
'unchanged', start, end | ||||
Take a region of base[start:end] | ||||
'same', astart, aend | ||||
b and a are different from base but give the same result | ||||
'a', start, end | ||||
Non-clashing insertion from a[start:end] | ||||
Method is as follows: | ||||
The two sequences align only on regions which match the base | ||||
|
r14549 | and both descendants. These are found by doing a two-way diff | ||
|
r6002 | of each one against the base, and then finding the | ||
intersections between those regions. These "sync regions" | ||||
are by definition unchanged in both and easily dealt with. | ||||
The regions in between can be in any of three cases: | ||||
conflicted, or changed on only one side. | ||||
""" | ||||
# section a[0:ia] has been disposed of, etc | ||||
iz = ia = ib = 0 | ||||
|
r16683 | for region in self.find_sync_regions(): | ||
zmatch, zend, amatch, aend, bmatch, bend = region | ||||
|
r6002 | #print 'match base [%d:%d]' % (zmatch, zend) | ||
matchlen = zend - zmatch | ||||
assert matchlen >= 0 | ||||
assert matchlen == (aend - amatch) | ||||
assert matchlen == (bend - bmatch) | ||||
len_a = amatch - ia | ||||
len_b = bmatch - ib | ||||
len_base = zmatch - iz | ||||
assert len_a >= 0 | ||||
assert len_b >= 0 | ||||
assert len_base >= 0 | ||||
#print 'unmatched a=%d, b=%d' % (len_a, len_b) | ||||
if len_a or len_b: | ||||
# try to avoid actually slicing the lists | ||||
equal_a = compare_range(self.a, ia, amatch, | ||||
self.base, iz, zmatch) | ||||
equal_b = compare_range(self.b, ib, bmatch, | ||||
self.base, iz, zmatch) | ||||
same = compare_range(self.a, ia, amatch, | ||||
self.b, ib, bmatch) | ||||
if same: | ||||
yield 'same', ia, amatch | ||||
elif equal_a and not equal_b: | ||||
yield 'b', ib, bmatch | ||||
elif equal_b and not equal_a: | ||||
yield 'a', ia, amatch | ||||
elif not equal_a and not equal_b: | ||||
yield 'conflict', iz, zmatch, ia, amatch, ib, bmatch | ||||
else: | ||||
raise AssertionError("can't handle a=b=base but unmatched") | ||||
ia = amatch | ||||
ib = bmatch | ||||
iz = zmatch | ||||
# if the same part of the base was deleted on both sides | ||||
# that's OK, we can just skip it. | ||||
if matchlen > 0: | ||||
assert ia == amatch | ||||
assert ib == bmatch | ||||
assert iz == zmatch | ||||
yield 'unchanged', zmatch, zend | ||||
iz = zend | ||||
ia = aend | ||||
ib = bend | ||||
def find_sync_regions(self): | ||||
|
r14549 | """Return a list of sync regions, where both descendants match the base. | ||
|
r6002 | |||
Generates a list of (base1, base2, a1, a2, b1, b2). There is | ||||
always a zero-length sync region at the end of all the files. | ||||
""" | ||||
ia = ib = 0 | ||||
amatches = mdiff.get_matching_blocks(self.basetext, self.atext) | ||||
bmatches = mdiff.get_matching_blocks(self.basetext, self.btext) | ||||
len_a = len(amatches) | ||||
len_b = len(bmatches) | ||||
sl = [] | ||||
while ia < len_a and ib < len_b: | ||||
abase, amatch, alen = amatches[ia] | ||||
bbase, bmatch, blen = bmatches[ib] | ||||
# there is an unconflicted block at i; how long does it | ||||
# extend? until whichever one ends earlier. | ||||
|
r10282 | i = intersect((abase, abase + alen), (bbase, bbase + blen)) | ||
|
r6002 | if i: | ||
intbase = i[0] | ||||
intend = i[1] | ||||
intlen = intend - intbase | ||||
# found a match of base[i[0], i[1]]; this may be less than | ||||
# the region that matches in either one | ||||
assert intlen <= alen | ||||
assert intlen <= blen | ||||
assert abase <= intbase | ||||
assert bbase <= intbase | ||||
asub = amatch + (intbase - abase) | ||||
bsub = bmatch + (intbase - bbase) | ||||
aend = asub + intlen | ||||
bend = bsub + intlen | ||||
assert self.base[intbase:intend] == self.a[asub:aend], \ | ||||
(self.base[intbase:intend], self.a[asub:aend]) | ||||
assert self.base[intbase:intend] == self.b[bsub:bend] | ||||
sl.append((intbase, intend, | ||||
asub, aend, | ||||
bsub, bend)) | ||||
# advance whichever one ends first in the base text | ||||
if (abase + alen) < (bbase + blen): | ||||
ia += 1 | ||||
else: | ||||
ib += 1 | ||||
intbase = len(self.base) | ||||
abase = len(self.a) | ||||
bbase = len(self.b) | ||||
sl.append((intbase, intbase, abase, abase, bbase, bbase)) | ||||
return sl | ||||
def find_unconflicted(self): | ||||
"""Return a list of ranges in base that are not conflicted.""" | ||||
am = mdiff.get_matching_blocks(self.basetext, self.atext) | ||||
bm = mdiff.get_matching_blocks(self.basetext, self.btext) | ||||
unc = [] | ||||
while am and bm: | ||||
# there is an unconflicted block at i; how long does it | ||||
# extend? until whichever one ends earlier. | ||||
a1 = am[0][0] | ||||
a2 = a1 + am[0][2] | ||||
b1 = bm[0][0] | ||||
b2 = b1 + bm[0][2] | ||||
i = intersect((a1, a2), (b1, b2)) | ||||
if i: | ||||
unc.append(i) | ||||
if a2 < b2: | ||||
del am[0] | ||||
else: | ||||
del bm[0] | ||||
return unc | ||||
|
r8269 | def simplemerge(ui, local, base, other, **opts): | ||
|
r6002 | def readfile(filename): | ||
f = open(filename, "rb") | ||||
text = f.read() | ||||
f.close() | ||||
if util.binary(text): | ||||
msg = _("%s looks like a binary file.") % filename | ||||
|
r14328 | if not opts.get('quiet'): | ||
ui.warn(_('warning: %s\n') % msg) | ||||
|
r6002 | if not opts.get('text'): | ||
raise util.Abort(msg) | ||||
return text | ||||
name_a = local | ||||
name_b = other | ||||
|
r22024 | name_base = None | ||
|
r6002 | labels = opts.get('label', []) | ||
|
r21272 | if len(labels) > 0: | ||
name_a = labels[0] | ||||
if len(labels) > 1: | ||||
name_b = labels[1] | ||||
if len(labels) > 2: | ||||
|
r22024 | name_base = labels[2] | ||
if len(labels) > 3: | ||||
raise util.Abort(_("can only specify three labels.")) | ||||
|
r6002 | |||
|
r14328 | try: | ||
localtext = readfile(local) | ||||
basetext = readfile(base) | ||||
othertext = readfile(other) | ||||
except util.Abort: | ||||
return 1 | ||||
|
r6002 | |||
|
r15381 | local = os.path.realpath(local) | ||
|
r6002 | if not opts.get('print'): | ||
|
r13970 | opener = scmutil.opener(os.path.dirname(local)) | ||
|
r6002 | out = opener(os.path.basename(local), "w", atomictemp=True) | ||
else: | ||||
out = sys.stdout | ||||
m3 = Merge3Text(basetext, localtext, othertext) | ||||
|
r22024 | extrakwargs = {} | ||
if name_base is not None: | ||||
extrakwargs['base_marker'] = '|||||||' | ||||
extrakwargs['name_base'] = name_base | ||||
for line in m3.merge_lines(name_a=name_a, name_b=name_b, **extrakwargs): | ||||
|
r6002 | out.write(line) | ||
if not opts.get('print'): | ||||
|
r15057 | out.close() | ||
|
r6002 | |||
if m3.conflicts: | ||||
if not opts.get('quiet'): | ||||
|
r8269 | ui.warn(_("warning: conflicts during merge.\n")) | ||
|
r6002 | return 1 | ||