# Written by Bram Cohen
# see LICENSE.txt for license information
from sets import Set
def find_conflict(local, local_line_points, local_points, remote, remote_line_points, remote_points):
return _find_conflict(local, local_line_points, local_points, remote, remote_line_points, remote_points)[0]
def find_conflict_safe(local, local_line_points, local_points, remote, remote_line_points, remote_points):
return find_conflict_multiple_safe([(local, local_line_points, local_points), (remote, remote_line_points, remote_points)])[:2]
def find_conflict_multiple_safe(precursors):
olds = precursors[:]
lines, line_points, points = olds.pop(0)
while olds:
nlines, nlinepoints, npoints = olds.pop(0)
lines, line_points = _find_conflict(lines, line_points, points, nlines, nlinepoints, npoints)
points = _union(points, npoints)
if None in line_points:
return (None, None, None)
return lines, line_points, points
def _is_applied(ll, pdict):
for i in ll:
for j in i:
if j in pdict:
break
else:
return 0
return 1
def _find_conflict(local, local_line_points, local_points, remote, remote_line_points, remote_points):
assert len(local_line_points) == len(local) + 1
assert len(remote_line_points) == len(remote) + 1
lpdict = Set(local_points)
for i in local_line_points:
for point in i:
assert point in lpdict
rpdict = Set(remote_points)
for i in remote_line_points:
for point in i:
assert point in rpdict
result = []
result_line_points = []
lastl, lastr = 0, 0
for (lpos, rpos, matchlen) in _find_matches(local, remote) + [(len(local), len(remote), 0)]:
rapplied = _is_applied(remote_line_points[lastr:rpos + 1], lpdict)
lapplied = _is_applied(local_line_points[lastl:lpos + 1], rpdict)
if rapplied and not lapplied:
result.extend(local[lastl:lpos + matchlen])
result_line_points.extend(local_line_points[lastl:lpos + 1])
elif lapplied and not rapplied:
result.extend(remote[lastr:rpos + matchlen])
result_line_points.extend(remote_line_points[lastr:rpos + 1])
elif (lastl, lastr) == (len(local), len(remote)):
result_line_points.append(_union(local_line_points[-1], remote_line_points[-1]))
elif (lpos, rpos) == (0, 0):
result.extend(local[:matchlen])
result_line_points.append(_union(local_line_points[0], remote_line_points[0]))
else:
result.append((local[lastl:lpos], remote[lastr:rpos]))
result.extend(local[lpos:lpos + matchlen])
result_line_points.append((local_line_points[lastl:lpos + 1], remote_line_points[lastr:rpos + 1]))
result_line_points.append(None)
for i in xrange(1, matchlen):
result_line_points.append(_union(local_line_points[lpos + i], remote_line_points[rpos + i]))
lastl, lastr = lpos + matchlen, rpos + matchlen
return (result, result_line_points)
def _union(la, lb):
lc = la[:]
for i in lb:
if i not in lc:
lc.append(i)
return lc
def test_conflict():
# conflict at begin
## local zero
### local wins
assert _find_conflict(['aaa', 'bbb'], [['b'], ['a'], ['a']], ['a', 'b', 'c'], ['x', 'aaa', 'bbb'], [['a'], ['c'], ['a'], ['a']], ['a', 'c']) == (['aaa', 'bbb'], [['b'], ['a'], ['a']])
### remote wins
#### remote violate at begin
assert _find_conflict(['aaa', 'bbb'], [['a'], ['a'], ['a']], ['a'], ['x', 'y', 'aaa', 'bbb'], [['b'], ['a'], ['a'], ['a'], ['a']], ['a', 'b']) == (['x', 'y', 'aaa', 'bbb'], [['b'], ['a'], ['a'], ['a'], ['a']])
#### remote violate at end
assert _find_conflict(['aaa', 'bbb'], [['a'], ['a'], ['a']], ['a'], ['x', 'y', 'aaa', 'bbb'], [['a'], ['a'], ['b'], ['a'], ['a']], ['a', 'b']) == (['x', 'y', 'aaa', 'bbb'], [['a'], ['a'], ['b'], ['a'], ['a']])
### neither win
#### remote violate at begin
assert _find_conflict(['aaa', 'bbb'], [['c'], ['a'], ['a']], ['a', 'c'], ['x', 'y', 'aaa', 'bbb'], [['b'], ['a'], ['a'], ['a'], ['a']], ['a', 'b']) == ([([], ['x', 'y']), 'aaa', 'bbb'], [([['c']], [['b'], ['a'], ['a']]), None, ['a'], ['a']])
#### remote violate at end
assert _find_conflict(['aaa', 'bbb'], [['c'], ['a'], ['a']], ['a', 'c'], ['x', 'y', 'aaa', 'bbb'], [['a'], ['a'], ['b'], ['a'], ['a']], ['a', 'b']) == ([([], ['x', 'y']), 'aaa', 'bbb'], [([['c']], [['a'], ['a'], ['b']]), None, ['a'], ['a']])
## remote zero
### local wins
assert _find_conflict(['x', 'aaa', 'bbb'], [['a'], ['b'], ['a'], ['a']], ['a', 'b'], ['aaa', 'bbb'], [['a'], ['a'], ['a']], ['a']) == (['x', 'aaa', 'bbb'], [['a'], ['b'], ['a'], ['a']])
### remote wins
assert _find_conflict(['x', 'aaa', 'bbb'], [['a'], ['b'], ['a'], ['a']], ['a', 'b'], ['aaa', 'bbb'], [['c'], ['a'], ['a']], ['a', 'b', 'c']) == (['aaa', 'bbb'], [['c'], ['a'], ['a']])
### neither win
#### local violate at begin
assert _find_conflict(['x', 'y', 'aaa', 'bbb'], [['b'], ['a'], ['a'], ['a'], ['a']], ['a', 'b'], ['aaa', 'bbb'], [['c'], ['a'], ['a']], ['a', 'c']) == ([(['x', 'y'], []), 'aaa', 'bbb'], [([['b'], ['a'], ['a']], [['c']]), None, ['a'], ['a']])
#### local violate at end
assert _find_conflict(['x', 'y', 'aaa', 'bbb'], [['a'], ['a'], ['b'], ['a'], ['a']], ['a', 'b'], ['aaa', 'bbb'], [['c'], ['a'], ['a']], ['a', 'c']) == ([(['x', 'y'], []), 'aaa', 'bbb'], [([['a'], ['a'], ['b']], [['c']]), None, ['a'], ['a']])
## neither zero
### local wins
assert _find_conflict(['x', 'y', 'aaa', 'bbb'], [['a'], ['b'], ['a'], ['a'], ['a']], ['a', 'b'], ['z', 'w', 'aaa', 'bbb'], [['a'], ['a'], ['a'], ['a'], ['a']], ['a']) == (['x', 'y', 'aaa', 'bbb'], [['a'], ['b'], ['a'], ['a'], ['a']])
### remote wins
#### violates at beginning
assert _find_conflict(['x', 'y', 'aaa', 'bbb'], [['a'], ['a'], ['a'], ['a'], ['a']], ['a'], ['z', 'w', 'aaa', 'bbb'], [['b'], ['a'], ['a'], ['a'], ['a']], ['a', 'b']) == (['z', 'w', 'aaa', 'bbb'], [['b'], ['a'], ['a'], ['a'], ['a']])
#### violates at end
assert _find_conflict(['x', 'y', 'aaa', 'bbb'], [['a'], ['a'], ['a'], ['a'], ['a']], ['a'], ['z', 'w', 'aaa', 'bbb'], [['a'], ['a'], ['b'], ['a'], ['a']], ['a', 'b']) == (['z', 'w', 'aaa', 'bbb'], [['a'], ['a'], ['b'], ['a'], ['a']])
### neither win
#### violates at begin
assert _find_conflict(['x', 'y', 'aaa', 'bbb'], [['c'], ['a'], ['a'], ['a'], ['a']], ['a', 'c'], ['z', 'w', 'aaa', 'bbb'], [['b'], ['a'], ['a'], ['a'], ['a']], ['a', 'b']) == ([(['x', 'y'], ['z', 'w']), 'aaa', 'bbb'], [([['c'], ['a'], ['a']], [['b'], ['a'], ['a']]), None, ['a'], ['a']])
#### violates at end
assert _find_conflict(['x', 'y', 'aaa', 'bbb'], [['a'], ['a'], ['c'], ['a'], ['a']], ['a', 'c'], ['z', 'w', 'aaa', 'bbb'], [['a'], ['a'], ['b'], ['a'], ['a']], ['a', 'b']) == ([(['x', 'y'], ['z', 'w']), 'aaa', 'bbb'], [([['a'], ['a'], ['c']], [['a'], ['a'], ['b']]), None, ['a'], ['a']])
# conflict in middle
## local zero
### local wins
assert _find_conflict(['aaa', 'bbb', 'ccc', 'ddd'], [['a'], ['a'], ['b'], ['a'], ['a']], ['a', 'b', 'c'], ['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['c'], ['c'], ['a'], ['a']], ['a', 'c']) == (['aaa', 'bbb', 'ccc', 'ddd'], [['a'], ['a'], ['b'], ['a'], ['a']])
### remote wins
#### violate at begin
assert _find_conflict(['aaa', 'bbb', 'ccc', 'ddd'], [['a'], ['a'], ['b'], ['a'], ['a']], ['a', 'b'], ['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['c'], ['a'], ['a'], ['a']], ['a', 'b', 'c']) == (['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['c'], ['a'], ['a'], ['a']])
#### violate at end
assert _find_conflict(['aaa', 'bbb', 'ccc', 'ddd'], [['a'], ['a'], ['b'], ['a'], ['a']], ['a', 'b'], ['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['a'], ['c'], ['a'], ['a']], ['a', 'b', 'c']) == (['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['a'], ['c'], ['a'], ['a']])
### neither win
#### remote violate at begin
assert _find_conflict(['aaa', 'bbb', 'ccc', 'ddd'], [['a'], ['a'], ['b'], ['a'], ['a']], ['a', 'b'], ['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['c'], ['a'], ['a'], ['a']], ['a', 'c']) == (['aaa', 'bbb', ([], ['x']), 'ccc', 'ddd'], [['a'], ['a'], ([['b']], [['c'], ['a']]), None, ['a'], ['a']])
#### remote violate at end
assert _find_conflict(['aaa', 'bbb', 'ccc', 'ddd'], [['a'], ['a'], ['b'], ['a'], ['a']], ['a', 'b'], ['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['a'], ['c'], ['a'], ['a']], ['a', 'c']) == (['aaa', 'bbb', ([], ['x']), 'ccc', 'ddd'], [['a'], ['a'], ([['b']], [['a'], ['c']]), None, ['a'], ['a']])
## remote zero
### local wins
assert _find_conflict(['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['x'], ['x'], ['a'], ['a']], ['a', 'x', 'c'], ['aaa', 'bbb', 'ccc', 'ddd'], [['a'], ['a'], ['c'], ['a'], ['a']], ['a', 'c']) == (['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['x'], ['x'], ['a'], ['a']])
### remote wins
assert _find_conflict(['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['x'], ['x'], ['a'], ['a']], ['a', 'x'], ['aaa', 'bbb', 'ccc', 'ddd'], [['a'], ['a'], ['c'], ['a'], ['a']], ['a', 'x', 'c']) == (['aaa', 'bbb', 'ccc', 'ddd'], [['a'], ['a'], ['c'], ['a'], ['a']])
### neither win
#### local violate at begin
assert _find_conflict(['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['x'], ['a'], ['a'], ['a']], ['a', 'x'], ['aaa', 'bbb', 'ccc', 'ddd'], [['a'], ['a'], ['c'], ['a'], ['a']], ['a', 'c']) == (['aaa', 'bbb', (['x'], []), 'ccc', 'ddd'], [['a'], ['a'], ([['x'], ['a']], [['c']]), None, ['a'], ['a']])
#### local violate at end
assert _find_conflict(['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['a'], ['x'], ['a'], ['a']], ['a', 'x'], ['aaa', 'bbb', 'ccc', 'ddd'], [['a'], ['a'], ['c'], ['a'], ['a']], ['a', 'c']) == (['aaa', 'bbb', (['x'], []), 'ccc', 'ddd'], [['a'], ['a'], ([['a'], ['x']], [['c']]), None, ['a'], ['a']])
## neither zero
### local wins
assert _find_conflict(['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['x'], ['x'], ['a'], ['a']], ['a', 'x', 'y'], ['aaa', 'bbb', 'y', 'ccc', 'ddd'], [['a'], ['a'], ['y'], ['y'], ['a'], ['a']], ['a', 'y']) == (['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['x'], ['x'], ['a'], ['a']])
### remote wins
#### violate at begin
assert _find_conflict(['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['x'], ['x'], ['a'], ['a']], ['a', 'x'], ['aaa', 'bbb', 'y', 'ccc', 'ddd'], [['a'], ['a'], ['y'], ['a'], ['a'], ['a']], ['a', 'x', 'y']) == (['aaa', 'bbb', 'y', 'ccc', 'ddd'], [['a'], ['a'], ['y'], ['a'], ['a'], ['a']])
#### violate at end
assert _find_conflict(['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['x'], ['x'], ['a'], ['a']], ['a', 'x'], ['aaa', 'bbb', 'y', 'ccc', 'ddd'], [['a'], ['a'], ['a'], ['y'], ['a'], ['a']], ['a', 'x', 'y']) == (['aaa', 'bbb', 'y', 'ccc', 'ddd'], [['a'], ['a'], ['a'], ['y'], ['a'], ['a']])
### neither win
#### violates at begin
assert _find_conflict(['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['x'], ['a'], ['a'], ['a']], ['a', 'x'], ['aaa', 'bbb', 'y', 'ccc', 'ddd'], [['a'], ['a'], ['y'], ['a'], ['a'], ['a']], ['a', 'y']) == (['aaa', 'bbb', (['x'], ['y']), 'ccc', 'ddd'], [['a'], ['a'], ([['x'], ['a']], [['y'], ['a']]), None, ['a'], ['a']])
#### violates at end
assert _find_conflict(['aaa', 'bbb', 'x', 'ccc', 'ddd'], [['a'], ['a'], ['a'], ['x'], ['a'], ['a']], ['a', 'x'], ['aaa', 'bbb', 'y', 'ccc', 'ddd'], [['a'], ['a'], ['a'], ['y'], ['a'], ['a']], ['a', 'y']) == (['aaa', 'bbb', (['x'], ['y']), 'ccc', 'ddd'], [['a'], ['a'], ([['a'], ['x']], [['a'], ['y']]), None, ['a'], ['a']])
# conflict at end
## local zero
### local wins
assert _find_conflict(['aaa', 'bbb'], [['a'], ['a'], ['b']], ['a', 'b', 'x'], ['aaa', 'bbb', 'x'], [['a'], ['a'], ['x'], ['x']], ['a', 'x']) == (['aaa', 'bbb'], [['a'], ['a'], ['b']])
### remote wins
#### violate at begin
assert _find_conflict(['aaa', 'bbb'], [['a'], ['a'], ['b']], ['a', 'b'], ['aaa', 'bbb', 'x'], [['a'], ['a'], ['x'], ['a']], ['a', 'b', 'x']) == (['aaa', 'bbb', 'x'], [['a'], ['a'], ['x'], ['a']])
#### violate at end
assert _find_conflict(['aaa', 'bbb'], [['a'], ['a'], ['b']], ['a', 'b'], ['aaa', 'bbb', 'x'], [['a'], ['a'], ['a'], ['x']], ['a', 'b', 'x']) == (['aaa', 'bbb', 'x'], [['a'], ['a'], ['a'], ['x']])
### neither win
#### remote violate at begin
assert _find_conflict(['aaa', 'bbb'], [['a'], ['a'], ['b']], ['a', 'b'], ['aaa', 'bbb', 'x'], [['a'], ['a'], ['x'], ['a']], ['a', 'x']) == (['aaa', 'bbb', ([], ['x'])], [['a'], ['a'], ([['b']], [['x'], ['a']]), None])
#### remote violate at end
assert _find_conflict(['aaa', 'bbb'], [['a'], ['a'], ['b']], ['a', 'b'], ['aaa', 'bbb', 'x'], [['a'], ['a'], ['a'], ['x']], ['a', 'x']) == (['aaa', 'bbb', ([], ['x'])], [['a'], ['a'], ([['b']], [['a'], ['x']]), None])
## remote zero
### local wins
assert _find_conflict(['aaa', 'bbb', 'x'], [['a'], ['a'], ['x'], ['x']], ['a', 'b', 'x'], ['aaa', 'bbb'], [['a'], ['a'], ['b']], ['a', 'b']) == (['aaa', 'bbb', 'x'], [['a'], ['a'], ['x'], ['x']])
### remote wins
assert _find_conflict(['aaa', 'bbb', 'x'], [['a'], ['a'], ['x'], ['x']], ['a', 'x'], ['aaa', 'bbb'], [['a'], ['a'], ['b']], ['a', 'b', 'x']) == (['aaa', 'bbb'], [['a'], ['a'], ['b']])
### neither win
#### local violate at begin
assert _find_conflict(['aaa', 'bbb', 'x'], [['a'], ['a'], ['x'], ['a']], ['a', 'x'], ['aaa', 'bbb'], [['a'], ['a'], ['b']], ['a', 'b']) == (['aaa', 'bbb', (['x'], [])], [['a'], ['a'], ([['x'], ['a']], [['b']]), None])
#### local violate at end
assert _find_conflict(['aaa', 'bbb', 'x'], [['a'], ['a'], ['a'], ['x']], ['a', 'x'], ['aaa', 'bbb'], [['a'], ['a'], ['b']], ['a', 'b']) == (['aaa', 'bbb', (['x'], [])], [['a'], ['a'], ([['a'], ['x']], [['b']]), None])
## neither zero
### local wins
assert _find_conflict(['aaa', 'bbb', 'x'], [['a'], ['a'], ['x'], ['x']], ['a', 'x', 'y'], ['aaa', 'bbb', 'y'], [['a'], ['a'], ['y'], ['y']], ['a', 'y']) == (['aaa', 'bbb', 'x'], [['a'], ['a'], ['x'], ['x']])
### remote wins
assert _find_conflict(['aaa', 'bbb', 'x'], [['a'], ['a'], ['x'], ['x']], ['a', 'x'], ['aaa', 'bbb', 'y'], [['a'], ['a'], ['y'], ['y']], ['a', 'x', 'y']) == (['aaa', 'bbb', 'y'], [['a'], ['a'], ['y'], ['y']])
### neither win
#### violates at begin
assert _find_conflict(['aaa', 'bbb', 'x'], [['a'], ['a'], ['x'], ['a']], ['a', 'x'], ['aaa', 'bbb', 'y'], [['a'], ['a'], ['y'], ['a']], ['a', 'y']) == (['aaa', 'bbb', (['x'], ['y'])], [['a'], ['a'], ([['x'], ['a']], [['y'], ['a']]), None])
#### violates at end
assert _find_conflict(['aaa', 'bbb', 'x'], [['a'], ['a'], ['a'], ['x']], ['a', 'x'], ['aaa', 'bbb', 'y'], [['a'], ['a'], ['a'], ['y']], ['a', 'y']) == (['aaa', 'bbb', (['x'], ['y'])], [['a'], ['a'], ([['a'], ['x']], [['a'], ['y']]), None])
# whole file conflict
## local zero
### local wins
assert _find_conflict([], [['a']], ['a', 'b'], ['x'], [['b'], ['b']], ['b']) == ([], [['a']])
### remote wins
#### violate at begin
assert _find_conflict([], [['a']], ['a'], ['x'], [['b'], ['a']], ['a', 'b']) == (['x'], [['b'], ['a']])
#### violate at end
assert _find_conflict([], [['a']], ['a'], ['x'], [['a'], ['b']], ['a', 'b']) == (['x'], [['a'], ['b']])
### neither win
#### remote violate at begin
assert _find_conflict([], [['a']], ['a', 'c'], ['x'], [['b'], ['c']], ['b', 'c']) == ([([], ['x'])], [([['a']], [['b'], ['c']]), None])
#### remote violate at end
assert _find_conflict([], [['a']], ['a', 'c'], ['x'], [['c'], ['b']], ['b', 'c']) == ([([], ['x'])], [([['a']], [['c'], ['b']]), None])
## remote zero
### local wins
assert _find_conflict(['a'], [['a'], ['a']], ['a', 'b'], [], [['b']], ['b']) == (['a'], [['a'], ['a']])
### remote wins
assert _find_conflict(['a'], [['a'], ['a']], ['a'], [], [['b']], ['a', 'b']) == ([], [['b']])
### neither win
#### local violate at begin
assert _find_conflict(['a'], [['a'], ['c']], ['a', 'c'], [], [['b']], ['b', 'c']) == ([(['a'], [])], [([['a'], ['c']], [['b']]), None])
#### local violate at end
assert _find_conflict(['a'], [['c'], ['a']], ['a', 'c'], [], [['b']], ['b', 'c']) == ([(['a'], [])], [([['c'], ['a']], [['b']]), None])
## neither zero
### local wins
assert _find_conflict(['a'], [['a'], ['a']], ['a', 'b'], ['b'], [['b'], ['b']], ['b']) == (['a'], [['a'], ['a']])
### remote wins
assert _find_conflict(['a'], [['a'], ['a']], ['a'], ['b'], [['b'], ['b']], ['a', 'b']) == (['b'], [['b'], ['b']])
### neither win
#### violate at begin
assert _find_conflict(['a'], [['a'], ['c']], ['a', 'c'], ['b'], [['b'], ['c']], ['c', 'b']) == ([(['a'], ['b'])], [([['a'], ['c']], [['b'], ['c']]), None])
#### violate at end
assert _find_conflict(['a'], [['c'], ['a']], ['a', 'c'], ['b'], [['c'], ['b']], ['c', 'b']) == ([(['a'], ['b'])], [([['c'], ['a']], [['c'], ['b']]), None])
# union counts for either
assert _find_conflict(['aaa', 'bbb'], [['a'], ['a', 'b'], ['a']], ['a', 'b'], ['ccc', 'ddd'], [['a'], ['c'], ['a']], ['a', 'c']) == (['ccc', 'ddd'], [['a'], ['c'], ['a']])
# coincidental matches
## begin
assert _find_conflict(['aaa', 'bbb'], [['b'], ['a'], ['a']], ['a', 'b'], ['aaa', 'bbb'], [['c'], ['a'], ['a']], ['a', 'c']) == (['aaa', 'bbb'], [['b', 'c'], ['a'], ['a']])
## middle
assert _find_conflict(['aaa', 'bbb'], [['a'], ['b'], ['a']], ['a', 'b'], ['aaa', 'bbb'], [['a'], ['c'], ['a']], ['a', 'c']) == (['aaa', 'bbb'], [['a'], ['b', 'c'], ['a']])
## end
assert _find_conflict(['aaa', 'bbb'], [['a'], ['a'], ['b']], ['a', 'b'], ['aaa', 'bbb'], [['a'], ['a'], ['c']], ['a', 'c']) == (['aaa', 'bbb'], [['a'], ['a'], ['b', 'c']])
# multiple conflicts, different resolutions
assert _find_conflict(['x', 'aaa', 'bbb', 'y', 'ccc', 'ddd', 'z'], [['x'], ['x'], ['a'], ['y'], ['y'], ['a'], ['z'], ['z']], ['a', 'x', 'y', 'z', 'p'], ['p', 'aaa', 'bbb', 'q', 'ccc', 'ddd', 'r'], [['p'], ['p'], ['a'], ['q'], ['q'], ['a'], ['r'], ['r']], ['a', 'p', 'q', 'r', 'z']) == (['x', 'aaa', 'bbb', (['y'], ['q']), 'ccc', 'ddd', 'r'], [['x'], ['x'], ['a'], ([['y'], ['y']], [['q'], ['q']]), None, ['a'], ['r'], ['r']])
def _find_matches(local, remote):
if local == remote:
return [(0, 0, len(local))]
bdict = {}
for i in xrange(0, len(remote)):
bdict.setdefault(remote[i], []).append(i)
return _fm(local, 0, len(local), remote, 0, len(remote), bdict)
def _fm(linesa, abegin, aend, linesb, bbegin, bend, bdict):
bestlen = 0
for i in xrange(abegin, aend):
if i + bestlen >= aend:
break
for j in bdict.get(linesa[i], []):
if j < bbegin:
continue
if j + bestlen >= bend:
break
if i > abegin and j > bbegin and linesa[i - 1] == linesb[j - 1]:
continue
if linesa[i + bestlen] != linesb[j + bestlen]:
continue
count = 0
k = 0
while i + k < aend and j + k < bend and linesa[i + k] == linesb[j + k]:
if count < 2 and len(linesa[i + k].strip()) > 2:
count += 1
k += 1
if k > bestlen and count >= 2:
besta = i
bestb = j
bestlen = k
if i + bestlen >= aend:
break
if bestlen == 0:
return []
return _fm(linesa, abegin, besta, linesb, bbegin, bestb, bdict) + [(besta, bestb, bestlen)] + _fm(linesa, besta + bestlen, aend, linesb, bestb + bestlen, bend, bdict)
def test_find_matches():
assert _find_matches(['x', 'aaa', 'y'], ['z', 'aaa', 'y']) == []
assert _find_matches(['a'], ['a']) == [(0, 0, 1)]
assert _find_matches(['aaa', 'aaa', 'ppp'], ['aaa', 'aaa', 'qqq']) == [(0, 0, 2)]
assert _find_matches(['ppp', 'aaa', 'aaa'], ['qqq', 'aaa', 'aaa']) == [(1, 1, 2)]
assert _find_matches(['ppp', 'aaa', 'aaa', 'ppp'], ['qqq', 'aaa', 'aaa', 'qqq']) == [(1, 1, 2)]
assert _find_matches(['aaa', 'aaa', 'bbb', 'ccc', 'aaa', 'aaa', 'aaa'], ['aaa', 'aaa', 'bbb', 'aaa', 'aaa', 'aaa', 'ccc']) == [(0, 0, 3), (4, 3, 3)]
assert _find_matches(['aaa', 'aaa', 'bbb', 'aaa', 'aaa', 'aaa', 'ccc'], ['aaa', 'aaa', 'bbb', 'ccc', 'aaa', 'aaa', 'aaa']) == [(0, 0, 3), (3, 4, 3)]
assert _find_matches(['aaa', 'aaa', 'aaa', 'bbb', 'ccc', 'aaa', 'aaa', 'aaa'], ['bbb', 'aaa', 'aaa', 'aaa', 'ccc', 'aaa', 'aaa', 'aaa']) == [(0, 1, 3), (4, 4, 4)]
assert _find_matches(['bbb', 'aaa', 'aaa', 'aaa', 'ccc', 'aaa', 'aaa', 'aaa'], ['aaa', 'aaa', 'aaa', 'bbb', 'ccc', 'aaa', 'aaa', 'aaa']) == [(1, 0, 3), (4, 4, 4)]
assert _find_matches(['aaa', 'aaa', 'bbb', 'bbb'], ['bbb', 'bbb', 'aaa', 'aaa']) == [(0, 2, 2)]
assert _find_matches(['aaa', 'aaa', 'bbb', 'bbb', 'bbb'], ['bbb', 'bbb', 'bbb', 'aaa', 'aaa']) == [(2, 0, 3)]
def find_resolution(precursors, resolution):
all = []
for i in xrange(len(precursors)):
for (matchold, matchnew, matchlen) in _find_matches(precursors[i][0], resolution):
all.append((matchlen, i, matchold, matchnew))
all.sort()
ms = [[] for i in xrange(len(precursors))]
result = [[] for i in xrange(len(resolution) + 1)]
for (matchlen, i, matchold, matchnew) in all:
pre = precursors[i][0]
pre_line_points = precursors[i][1]
(begina, beginb, mlen) = (matchold + 1, matchnew + 1, matchlen - 1)
if (matchold, matchnew) == (0, 0):
(begina, beginb, mlen) = (0, 0, mlen + 1)
if (matchold + matchlen, matchnew + matchlen) == (len(pre), len(resolution)):
mlen += 1
for j in xrange(mlen):
for v in pre_line_points[begina + j]:
if v not in result[beginb + j]:
result[beginb + j].append(v)
ms[i].append((matchold, matchnew, matchlen))
#for x in result:
# x.sort()
for x in ms:
x.sort()
hits = [False] * len(resolution)
for i in xrange(len(ms)):
for (matchold, matchnew, matchlen) in ms[i]:
for j in xrange(matchlen):
hits[matchnew + j] = True
newlines = []
pos = 0
while pos < len(hits):
if hits[pos]:
pos += 1
else:
n = []
j = pos
while j < len(hits) and not hits[j]:
n.append(resolution[j])
j += 1
newlines.append((pos, n))
pos = j
return (result, ms, newlines)
def test_resolve():
assert find_resolution([(['aaa', 'bbb', 'ccc'], [['x'], ['y'], ['z'], ['w']]), (['aaa', 'bbb', 'ccc'], [['p'], ['q'], ['z'], ['w']])], ['aaa', 'bbb', 'ccc'])[0] == [['p', 'x'], ['q', 'y'], ['z'], ['w']]
assert find_resolution([(['aaa', 'bbb', 'qqq'], [['a'], ['b'], ['c'], ['d']]), (['qqq', 'bbb', 'ccc'], [['e'], ['f'], ['g'], ['h']])], ['aaa', 'bbb', 'ccc'])[0] == [['a'], ['b'], ['g'], ['h']]
assert find_resolution([(['aaa'], [['a'], ['a']])], ['bbb'])[0] == [[], []]
assert find_resolution([(['aaa'], [['x'], ['x']]), (['aaa'], [['x'], ['x']])], ['aaa'])[1] == [[(0, 0, 1)], []]
assert find_resolution([(['aaa'], [['x'], ['x']]), (['aaa'], [['x'], ['y']])], ['aaa'])[1] == [[(0, 0, 1)], [(0, 0, 1)]]
assert find_resolution([(['aaa', 'aaa'], [['x'], ['x'], ['x']])], ['aaa', 'aaa', 'bbb', 'ccc'])[2] == [(2, ['bbb', 'ccc'])]
assert find_resolution([(['aaa', 'aaa'], [['x'], ['x'], ['x']])], ['bbb', 'ccc', 'aaa', 'aaa'])[2] == [(0, ['bbb', 'ccc'])]
assert find_resolution([(['aaa', 'aaa'], [['x'], ['x'], ['x']])], ['bbb', 'ccc'])[2] == [(0, ['bbb', 'ccc'])]
def replay(precursors, matches, newlines, current_point):
resultlength = 0
for i in matches:
if not len(i):
continue
matchold, matchnew, matchlen = i[-1]
if matchnew + matchlen > resultlength:
resultlength = matchnew + matchlen
try:
foo = newlines[-1][0] + len(newlines[-1][1])
if foo > resultlength:
resultlength = foo
except IndexError:
pass
r = [None] * resultlength
rpoints = [None] * (resultlength + 1)
def addrp(pos, vs, rpoints = rpoints):
if rpoints[pos] is None:
rpoints[pos] = vs[:]
return
rp = rpoints[pos]
for v in vs:
if v not in rp:
rp.append(v)
return
delpoints = [0]
for i in xrange(len(matches)):
try:
if matches[i][0][0] == 0 and matches[i][0][1] == 0:
addrp(0, precursors[i][1][0])
except IndexError:
pass
try:
matchold, matchnew, matchlen = matches[i][-1]
if matchnew + matchlen == resultlength and matchold + matchlen == len(precursors[i][0]):
addrp(resultlength, precursors[i][1][-1])
except IndexError:
pass
for (matchold, matchnew, matchlen) in matches[i]:
foo = precursors[i][0]
if matchold + matchlen > len(foo):
raise MergeError, 'match too long'
for j in xrange(matchlen):
pos = matchnew + j
v = foo[matchold + j]
if r[pos] is not None and r[pos] != v:
raise MergeError, 'conflicting values'
r[pos] = v
delpoints.append(matchnew + matchlen)
foo = precursors[i][1]
for j in xrange(1, matchlen):
addrp(matchnew + j, foo[matchold + j])
foo = [current_point]
for (begin, lines) in newlines:
for i in xrange(len(lines)):
if r[begin + i] is not None:
raise MergeError, 'match covers newline'
r[begin + i] = lines[i]
for i in xrange(len(lines) + 1):
addrp(begin + i, foo)
for index in delpoints:
if rpoints[index] is None:
addrp(index, foo)
if None in r:
raise MergeError, 'unfilled line'
if None in rpoints:
raise MergeError, 'unset line point'
return (r, rpoints)
class MergeError(StandardError):
pass
def test_replay():
assert replay([(['aaa', 'bbb'], [['a'], ['b'], ['c']])], [[(0, 0, 2)]], [(2, ['ccc', 'ddd'])], 'z') == (['aaa', 'bbb', 'ccc', 'ddd'], [['a'], ['b'], ['z'], ['z'], ['z']])
assert replay([(['aaa', 'bbb'], [['a'], ['b'], ['c']])], [[(0, 2, 2)]], [(0, ['ccc', 'ddd'])], 'z') == (['ccc', 'ddd', 'aaa', 'bbb'], [['z'], ['z'], ['z'], ['b'], ['c']])
assert replay([(['aaa', 'bbb', 'ccc', 'ddd'], [['a'], ['b'], ['c'], ['d'], ['e']]), (['bbb', 'ccc', 'ddd', 'eee'], [['f'], ['c'], ['g'], ['h'], ['i']])], [[(0, 0, 4)], [(0, 1, 4)]], [], 'z') == (['aaa', 'bbb', 'ccc', 'ddd', 'eee'], [['a'], ['b'], ['c'], ['d', 'g'], ['h'], ['i']])
assert replay([(['aaa', 'bbb', 'ccc', 'ddd', 'eee'], [['a'], ['a'], ['a'], ['a'], ['a'], ['a']])], [[(0, 0, 2), (3, 2, 2)]], [], 'z') == (['aaa', 'bbb', 'ddd', 'eee'], [['a'], ['a'], ['z'], ['a'], ['a']])
assert replay([(['aaa', 'bbb', 'ccc', 'ddd'], [['a'], ['a'], ['a'], ['a'], ['a']])], [[(2, 0, 2)]], [], 'z') == (['ccc', 'ddd'], [['z'], ['a'], ['a']])
assert replay([(['aaa', 'bbb', 'ccc', 'ddd'], [['a'], ['a'], ['a'], ['a'], ['a']])], [[(0, 0, 2)]], [], 'z') == (['aaa', 'bbb'], [['a'], ['a'], ['z']])
try:
import psyco
psyco.bind(replay)
psyco.bind(_find_matches)
except ImportError:
pass
syntax highlighted by Code2HTML, v. 0.9.1