simplemerge.py
542 lines
| 17.1 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 | ||
from .i18n import _ | ||||
from . import ( | ||||
|
r26587 | error, | ||
|
r25974 | mdiff, | ||
|
r33017 | pycompat, | ||
|
r37102 | ) | ||
|
r43346 | from .utils import stringutil | ||
|
r6002 | |||
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 | ||||
|
r43346 | |||
|
r6002 | def compare_range(a, astart, aend, b, bstart, bend): | ||
|
r46554 | """Compare a[astart:aend] == b[bstart:bend], without slicing.""" | ||
|
r10282 | if (aend - astart) != (bend - bstart): | ||
|
r6002 | return False | ||
|
r43346 | for ia, ib in zip( | ||
pycompat.xrange(astart, aend), pycompat.xrange(bstart, bend) | ||||
): | ||||
|
r6002 | if a[ia] != b[ib]: | ||
return False | ||||
else: | ||||
return True | ||||
|
r43346 | |||
|
r6002 | 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.""" | ||||
|
r43346 | |||
|
r6002 | 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_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 | ||||
|
r49379 | 'conflict', (base_lines, a_lines, b_lines) | ||
|
r6002 | Lines from base were changed to either a or b and conflict. | ||
""" | ||||
for t in self.merge_regions(): | ||||
what = t[0] | ||||
|
r43347 | if what == b'unchanged': | ||
|
r43346 | yield what, self.base[t[1] : t[2]] | ||
|
r43347 | elif what == b'a' or what == b'same': | ||
|
r43346 | yield what, self.a[t[1] : t[2]] | ||
|
r43347 | elif what == b'b': | ||
|
r43346 | yield what, self.b[t[1] : t[2]] | ||
|
r43347 | elif what == b'conflict': | ||
|
r43346 | yield ( | ||
what, | ||||
|
r49379 | ( | ||
self.base[t[1] : t[2]], | ||||
self.a[t[3] : t[4]], | ||||
self.b[t[5] : t[6]], | ||||
), | ||||
|
r43346 | ) | ||
|
r6002 | 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] | ||||
|
r28070 | 'conflict', zstart, zend, astart, aend, bstart, bend | ||
Conflict between a and b, with z as common ancestor | ||||
|
r6002 | 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 | ||||
|
r43346 | # print 'match base [%d:%d]' % (zmatch, zend) | ||
|
r6002 | |||
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 | ||||
|
r43346 | # print 'unmatched a=%d, b=%d' % (len_a, len_b) | ||
|
r6002 | |||
if len_a or len_b: | ||||
# try to avoid actually slicing the lists | ||||
|
r43346 | 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) | ||||
|
r6002 | |||
if same: | ||||
|
r43347 | yield b'same', ia, amatch | ||
|
r6002 | elif equal_a and not equal_b: | ||
|
r43347 | yield b'b', ib, bmatch | ||
|
r6002 | elif equal_b and not equal_a: | ||
|
r43347 | yield b'a', ia, amatch | ||
|
r6002 | elif not equal_a and not equal_b: | ||
|
r43347 | yield b'conflict', iz, zmatch, ia, amatch, ib, bmatch | ||
|
r6002 | else: | ||
|
r43347 | raise AssertionError(b"can't handle a=b=base but unmatched") | ||
|
r6002 | |||
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 | ||||
|
r43347 | yield b'unchanged', zmatch, zend | ||
|
r6002 | 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 | ||||
|
r41925 | assert self.base[intbase:intend] == self.a[asub:aend], ( | ||
|
r43346 | self.base[intbase:intend], | ||
self.a[asub:aend], | ||||
) | ||||
|
r6002 | |||
assert self.base[intbase:intend] == self.b[bsub:bend] | ||||
|
r43346 | sl.append((intbase, intend, asub, aend, bsub, bend)) | ||
|
r6002 | |||
# 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 | ||||
|
r43346 | |||
|
r49598 | def _verifytext(input): | ||
|
r33824 | """verifies that text is non-binary (unless opts[text] is passed, | ||
then we just warn)""" | ||||
|
r49598 | if stringutil.binary(input.text()): | ||
msg = _(b"%s looks like a binary file.") % input.fctx.path() | ||||
raise error.Abort(msg) | ||||
|
r33824 | |||
|
r43346 | |||
|
r49427 | def _format_labels(*inputs): | ||
|
r49433 | pad = max(len(input.label) if input.label else 0 for input in inputs) | ||
|
r49427 | labels = [] | ||
for input in inputs: | ||||
if input.label: | ||||
|
r49433 | if input.label_detail: | ||
label = ( | ||||
(input.label + b':').ljust(pad + 1) | ||||
+ b' ' | ||||
+ input.label_detail | ||||
) | ||||
else: | ||||
label = input.label | ||||
# 8 for the prefix of conflict marker lines (e.g. '<<<<<<< ') | ||||
labels.append(stringutil.ellipsis(label, 80 - 8)) | ||||
|
r49427 | else: | ||
labels.append(None) | ||||
return labels | ||||
|
r33829 | |||
|
r43346 | |||
|
r49408 | def _detect_newline(m3): | ||
if len(m3.a) > 0: | ||||
if m3.a[0].endswith(b'\r\n'): | ||||
return b'\r\n' | ||||
elif m3.a[0].endswith(b'\r'): | ||||
return b'\r' | ||||
return b'\n' | ||||
|
r49413 | def _minimize(a_lines, b_lines): | ||
|
r49412 | """Trim conflict regions of lines where A and B sides match. | ||
Lines where both A and B have made the same changes at the beginning | ||||
or the end of each merge region are eliminated from the conflict | ||||
region and are instead considered the same. | ||||
""" | ||||
|
r49413 | alen = len(a_lines) | ||
blen = len(b_lines) | ||||
|
r49412 | |||
|
r49413 | # find matches at the front | ||
ii = 0 | ||||
while ii < alen and ii < blen and a_lines[ii] == b_lines[ii]: | ||||
ii += 1 | ||||
startmatches = ii | ||||
|
r49412 | |||
|
r49413 | # find matches at the end | ||
ii = 0 | ||||
while ii < alen and ii < blen and a_lines[-ii - 1] == b_lines[-ii - 1]: | ||||
ii += 1 | ||||
endmatches = ii | ||||
|
r49412 | |||
|
r49413 | lines_before = a_lines[:startmatches] | ||
new_a_lines = a_lines[startmatches : alen - endmatches] | ||||
new_b_lines = b_lines[startmatches : blen - endmatches] | ||||
lines_after = a_lines[alen - endmatches :] | ||||
return lines_before, new_a_lines, new_b_lines, lines_after | ||||
|
r49412 | |||
|
r49411 | def render_minimized( | ||
|
r49406 | m3, | ||
name_a=None, | ||||
name_b=None, | ||||
start_marker=b'<<<<<<<', | ||||
mid_marker=b'=======', | ||||
end_marker=b'>>>>>>>', | ||||
): | ||||
"""Return merge in cvs-like form.""" | ||||
|
r49408 | newline = _detect_newline(m3) | ||
|
r49406 | conflicts = False | ||
|
r49411 | if name_a: | ||
|
r49406 | start_marker = start_marker + b' ' + name_a | ||
|
r49411 | if name_b: | ||
|
r49406 | end_marker = end_marker + b' ' + name_b | ||
merge_groups = m3.merge_groups() | ||||
lines = [] | ||||
for what, group_lines in merge_groups: | ||||
if what == b'conflict': | ||||
|
r49413 | conflicts = True | ||
|
r49406 | base_lines, a_lines, b_lines = group_lines | ||
|
r49413 | minimized = _minimize(a_lines, b_lines) | ||
lines_before, a_lines, b_lines, lines_after = minimized | ||||
lines.extend(lines_before) | ||||
|
r49411 | lines.append(start_marker + newline) | ||
|
r49406 | lines.extend(a_lines) | ||
|
r49411 | lines.append(mid_marker + newline) | ||
|
r49406 | lines.extend(b_lines) | ||
|
r49411 | lines.append(end_marker + newline) | ||
|
r49413 | lines.extend(lines_after) | ||
|
r49406 | else: | ||
lines.extend(group_lines) | ||||
return lines, conflicts | ||||
|
r49410 | def render_merge3(m3, name_a, name_b, name_base): | ||
"""Render conflicts as 3-way conflict markers.""" | ||||
newline = _detect_newline(m3) | ||||
conflicts = False | ||||
lines = [] | ||||
for what, group_lines in m3.merge_groups(): | ||||
if what == b'conflict': | ||||
base_lines, a_lines, b_lines = group_lines | ||||
conflicts = True | ||||
lines.append(b'<<<<<<< ' + name_a + newline) | ||||
lines.extend(a_lines) | ||||
lines.append(b'||||||| ' + name_base + newline) | ||||
lines.extend(base_lines) | ||||
lines.append(b'=======' + newline) | ||||
lines.extend(b_lines) | ||||
lines.append(b'>>>>>>> ' + name_b + newline) | ||||
else: | ||||
lines.extend(group_lines) | ||||
return lines, conflicts | ||||
|
r49407 | def render_mergediff(m3, name_a, name_b, name_base): | ||
|
r49410 | """Render conflicts as conflict markers with one snapshot and one diff.""" | ||
|
r49408 | newline = _detect_newline(m3) | ||
|
r46724 | lines = [] | ||
conflicts = False | ||||
|
r49379 | for what, group_lines in m3.merge_groups(): | ||
if what == b'conflict': | ||||
base_lines, a_lines, b_lines = group_lines | ||||
|
r46724 | base_text = b''.join(base_lines) | ||
b_blocks = list( | ||||
mdiff.allblocks( | ||||
base_text, | ||||
b''.join(b_lines), | ||||
lines1=base_lines, | ||||
lines2=b_lines, | ||||
) | ||||
) | ||||
a_blocks = list( | ||||
mdiff.allblocks( | ||||
base_text, | ||||
b''.join(a_lines), | ||||
lines1=base_lines, | ||||
lines2=b_lines, | ||||
) | ||||
) | ||||
def matching_lines(blocks): | ||||
return sum( | ||||
block[1] - block[0] | ||||
for block, kind in blocks | ||||
if kind == b'=' | ||||
) | ||||
def diff_lines(blocks, lines1, lines2): | ||||
for block, kind in blocks: | ||||
if kind == b'=': | ||||
for line in lines1[block[0] : block[1]]: | ||||
yield b' ' + line | ||||
else: | ||||
for line in lines1[block[0] : block[1]]: | ||||
yield b'-' + line | ||||
for line in lines2[block[2] : block[3]]: | ||||
yield b'+' + line | ||||
|
r49408 | lines.append(b"<<<<<<<" + newline) | ||
|
r46724 | if matching_lines(a_blocks) < matching_lines(b_blocks): | ||
|
r49408 | lines.append(b"======= " + name_a + newline) | ||
|
r46724 | lines.extend(a_lines) | ||
|
r49408 | lines.append(b"------- " + name_base + newline) | ||
lines.append(b"+++++++ " + name_b + newline) | ||||
|
r46724 | lines.extend(diff_lines(b_blocks, base_lines, b_lines)) | ||
else: | ||||
|
r49408 | lines.append(b"------- " + name_base + newline) | ||
lines.append(b"+++++++ " + name_a + newline) | ||||
|
r46724 | lines.extend(diff_lines(a_blocks, base_lines, a_lines)) | ||
|
r49408 | lines.append(b"======= " + name_b + newline) | ||
|
r46724 | lines.extend(b_lines) | ||
|
r49408 | lines.append(b">>>>>>>" + newline) | ||
|
r46724 | conflicts = True | ||
else: | ||||
|
r49379 | lines.extend(group_lines) | ||
|
r46724 | return lines, conflicts | ||
|
r49345 | def _resolve(m3, sides): | ||
lines = [] | ||||
|
r49379 | for what, group_lines in m3.merge_groups(): | ||
if what == b'conflict': | ||||
|
r49345 | for side in sides: | ||
|
r49379 | lines.extend(group_lines[side]) | ||
|
r49345 | else: | ||
|
r49379 | lines.extend(group_lines) | ||
|
r49345 | return lines | ||
|
r49427 | class MergeInput(object): | ||
|
r49594 | def __init__(self, fctx, label=None, label_detail=None): | ||
self.fctx = fctx | ||||
self.label = label | ||||
# If the "detail" part is set, then that is rendered after the label and | ||||
# separated by a ':'. The label is padded to make the ':' aligned among | ||||
# all merge inputs. | ||||
self.label_detail = label_detail | ||||
|
r49595 | self._text = None | ||
def text(self): | ||||
if self._text is None: | ||||
# Merges were always run in the working copy before, which means | ||||
# they used decoded data, if the user defined any repository | ||||
# filters. | ||||
# | ||||
# Maintain that behavior today for BC, though perhaps in the future | ||||
# it'd be worth considering whether merging encoded data (what the | ||||
# repository usually sees) might be more useful. | ||||
self._text = self.fctx.decodeddata() | ||||
return self._text | ||||
|
r49427 | |||
|
r49593 | def simplemerge( | ||
ui, | ||||
local, | ||||
base, | ||||
other, | ||||
mode=b'merge', | ||||
quiet=False, | ||||
allow_binary=False, | ||||
print_result=False, | ||||
): | ||||
|
r33827 | """Performs the simplemerge algorithm. | ||
|
r33908 | The merged result is written into `localctx`. | ||
|
r33906 | """ | ||
|
r35369 | |||
|
r49598 | if not allow_binary: | ||
_verifytext(local) | ||||
_verifytext(base) | ||||
_verifytext(other) | ||||
|
r33827 | |||
|
r49598 | m3 = Merge3Text(base.text(), local.text(), other.text()) | ||
|
r49345 | conflicts = False | ||
|
r43347 | if mode == b'union': | ||
|
r49345 | lines = _resolve(m3, (1, 2)) | ||
|
r49340 | elif mode == b'local': | ||
|
r49345 | lines = _resolve(m3, (1,)) | ||
|
r49340 | elif mode == b'other': | ||
|
r49345 | lines = _resolve(m3, (2,)) | ||
|
r46724 | else: | ||
|
r49347 | if mode == b'mergediff': | ||
|
r49427 | labels = _format_labels(local, other, base) | ||
lines, conflicts = render_mergediff(m3, *labels) | ||||
|
r49410 | elif mode == b'merge3': | ||
|
r49427 | labels = _format_labels(local, other, base) | ||
lines, conflicts = render_merge3(m3, *labels) | ||||
|
r49347 | else: | ||
|
r49427 | labels = _format_labels(local, other) | ||
lines, conflicts = render_minimized(m3, *labels) | ||||
|
r6002 | |||
|
r46716 | mergedtext = b''.join(lines) | ||
|
r49593 | if print_result: | ||
|
r46716 | ui.fout.write(mergedtext) | ||
else: | ||||
|
r49427 | # local.fctx.flags() already has the merged flags (done in | ||
|
r49338 | # mergestate.resolve()) | ||
|
r49427 | local.fctx.write(mergedtext, local.fctx.flags()) | ||
|
r6002 | |||
|
r49415 | return conflicts | ||