path: root/xdiff/xmerge.c
AgeCommit message (Collapse)Author
2006-12-31Fix yet another subtle xdl_merge() bugJohannes Schindelin
In very obscure cases, a merge can hit an unexpected code path (where the original code went as far as saying that this was a bug). This failing merge was noticed by Alexandre Juillard. The problem is that the original file contains something like this: -- snip -- two non-empty lines before two empty lines after two empty lines -- snap -- and this snippet is reduced to _one_ empty line in _both_ new files. However, it is ambiguous as to which hunk takes the empty line: the first or the second one? Indeed in Alexandre's example files, the xdiff algorithm attributes the empty line to the first hunk in one case, and to the second hunk in the other case. (Trimming down the example files _changes_ that behaviour!) Thus, the call to xdl_merge_cmp_lines() has no chance to realize that the change is actually identical in both new files. Therefore, xdl_refine_conflicts() finds an empty diff script, which was not expected there, because (the original author of xdl_merge() thought) xdl_merge_cmp_lines() would catch that case earlier. Signed-off-by: Johannes Schindelin <> Signed-off-by: Junio C Hamano <>
2006-12-28xdl_merge(): fix a segmentation fault when refining conflictsJohannes Schindelin
The function xdl_refine_conflicts() tries to break down huge conflicts by doing a diff on the conflicting regions. However, this does not make sense when one side is empty. Worse, when one side is not only empty, but after EOF, the code accessed unmapped memory. Noticed by Luben Tuikov, Shawn Pearce and Alexandre Julliard, the latter providing a test case. Signed-off-by: Johannes Schindelin <> Signed-off-by: Junio C Hamano <>
2006-12-05xdl_merge(): fix and simplify conflict handlingJohannes Schindelin
Suppose you have changes in new1 to the original lines 10-20, and changes in new2 to the original lines 15-25, then the changes to 10-25 conflict. But it is possible that the next changes in new1 still overlap with this change to new2. So, in the next iteration we have to look at the same change to new2 again. The old code tried to be a bit too clever. The new code is shorter and more to the point: do not fiddle with the ranges at all. Also, xdl_append_merge() tries harder to combine conflicts. This is necessary, because with the above simplification, some conflicts would not be recognized as conflicts otherwise: In the above scenario, it is possible that there is no other change to new1. Absent the combine logic, the change in new2 would be recorded _again_, but as a non-conflict. Signed-off-by: Johannes Schindelin <>
2006-12-03xdl_merge(): fix thinkoJohannes Schindelin
If one side's block (of changed lines) ends later than the other side's block, the former should be tested against the next block of the other side, not vice versa. Signed-off-by: Johannes Schindelin <> Signed-off-by: Junio C Hamano <>
2006-12-03xdl_merge(): fix an off-by-one bugJohannes Schindelin
The line range is i1 .. (i1 + chg1 - 1), not i1 .. (i1 + chg1). Signed-off-by: Johannes Schindelin <> Signed-off-by: Junio C Hamano <>
2006-12-03xmerge: make return value from xdl_merge() more usable.Junio C Hamano
The callers would want to know if the resulting merge is clean; do not discard that information away after calling xdl_do_merge(). Signed-off-by: Junio C Hamano <>
2006-12-03xdiff: add xdl_merge()Johannes Schindelin
This new function implements the functionality of RCS merge, but in-memory. It returns < 0 on error, otherwise the number of conflicts. Finding the conflicting lines can be a very expensive task. You can control the eagerness of this algorithm: - a level value of 0 means that all overlapping changes are treated as conflicts, - a value of 1 means that if the overlapping changes are identical, it is not treated as a conflict. - If you set level to 2, overlapping changes will be analyzed, so that almost identical changes will not result in huge conflicts. Rather, only the conflicting lines will be shown inside conflict markers. With each increasing level, the algorithm gets slower, but more accurate. Note that the code for level 2 depends on the simple definition of mmfile_t specific to git, and therefore it will be harder to port that to LibXDiff. Signed-off-by: Johannes Schindelin <> Signed-off-by: Junio C Hamano <>