{"thread":{"id":"6159","subject":"[PATCH] Fix yet another subtle xdl_merge() bug","startedAt":"2006-12-31T01:07:41Z","lastAt":"2006-12-31T01:07:41Z","messageCount":1,"participants":["Johannes Schindelin"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"30519","messageId":"Pine.LNX.4.63.0612310138540.19693@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"6159","inReplyTo":null,"subject":"[PATCH] Fix yet another subtle xdl_merge() bug","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2006-12-31T01:07:41Z","receivedAt":"2006-12-31T01:07:41Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"In very obscure cases, a merge can hit an unexpected code path (where the \noriginal code went as far as saying that this was a bug). This failing \nmerge was noticed by Alexandre Juillard.\n\nThe problem is that the original file contains something like this:\n\n-- snip --\ntwo non-empty lines\nbefore two empty lines\n\n\nafter two empty lines\n-- snap --\n\nand this snippet is reduced to _one_ empty line in _both_ new files. \nHowever, it is ambiguous as to which hunk takes the empty line: the first \nor the second one?\n\nIndeed in Alexandre's example files, the xdiff algorithm attributes the \nempty line to the first hunk in one case, and to the second hunk in the \nother case.\n\n(Trimming down the example files _changes_ that behaviour!)\n\nThus, the call to xdl_merge_cmp_lines() has no chance to realize that the \nchange is actually identical in both new files. Therefore, \nxdl_refine_conflicts() finds an empty diff script, which was not expected \nthere, because (the original author of xdl_merge() thought) \nxdl_merge_cmp_lines() would catch that case earlier.\n\nSigned-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>\n---\n\n\tAlexandre sent me this set of files where xdl_merge() returns \n\t-1 instead of performing as expected. With his permission, I \n\tattached them to this mail.\n\n\tOn Thu, 28 Dec 2006, Alexandre Julliard wrote:\n\t\n\t> I'm still unable to complete the merge though, it dies a bit \n\t> later with:\n\t> \n\t> ...\n\t> Auto-merging dlls/ntdll/virtual.c\n\t> fatal: Failed to execute internal merge\n\t> Merge with strategy recursive failed.\n\t> \n\t> Apparently xdl_merge() returns -1 for that one. I've attached \n\t> the corresponding files.\n\n\tI tried for about 20 hours total to concoct a short test case for \n\tthis, still failing. I give up.\n\n\tTrying to find out what happens led me to an interesting hunt for \n\ta bug which is not there. The code is even more elegant than I \n\tthought: it took me 10 hours of staring into my laptop, scribbling \n\ton my notepad and trying several examples, to find out why it \n\tworks.\n\n\tThe code in question is where two conflicts overlap, i.e. the \n\toriginal lines affected by both diff scripts overlap. The \n\tinteresting case is when the overlapping regions are \n\tnot identical.\n\n\txdl_do_merge() enlarges the smaller region, and adds the same \n\tamount of lines _to the corresponding region in the new file_.\n\n\tThis seems wrong, as there can be modifications in that region, \n\ttoo! Why does the code perform correctly, then?\n\n\tIt is a feature/obscure behaviour of xdl_append_merge() that it \n\ttries to combine conflicts. And if said problem occurs, it _will_ \n\tmodify the last conflict, but _only_ the end of the regions! Thus, \n\tit does not matter if the first line passed to xdl_append_merge() \n\tis actually wrong, as long as it is guaranteed to overlap the old \n\tconflict (which is the case: if it would not overlap, there would \n\tbe no modification in that part of the original file!).\n\n\tThe same holds for the last line: if it is wrong, it will get \n\tfixed in a subsequent call to xdl_append_merge().\n\n\tIf this sounds confused, it is because I thought too long and hard \n\tabout it, _and_ I just had a lovely poker night (my first one!). \n\tBut please, if you want to understand it, but my explanation is \n\tnot satisfactory, you may bug me for a better description, and I \n\twill do it. Though it has to wait until 2nd of January.\n\n\tHappy new year!\n\n xdiff/xmerge.c |    7 +++++--\n 1 files changed, 5 insertions(+), 2 deletions(-)\n\ndiff --git a/xdiff/xmerge.c b/xdiff/xmerge.c\nindex 294450b..b83b334 100644\n--- a/xdiff/xmerge.c\n+++ b/xdiff/xmerge.c\n@@ -166,6 +166,8 @@ static int xdl_fill_merge_buffer(xdfenv_t *xe1, const char *name1,\n \t\t\tsize += xdl_recs_copy(xe2, m->i2 - m->i1 + i1,\n \t\t\t\t\tm->i1 + m->chg2 - i1, 0,\n \t\t\t\t\tdest ? dest + size : NULL);\n+\t\telse\n+\t\t\tcontinue;\n \t\ti1 = m->i1 + m->chg1;\n \t}\n \tsize += xdl_recs_copy(xe1, i1, xe1->xdf2.nrec - i1, 0,\n@@ -213,9 +215,10 @@ static int xdl_refine_conflicts(xdfenv_t *xe1, xdfenv_t *xe2, xdmerge_t *m,\n \t\t\treturn -1;\n \t\t}\n \t\tif (!xscr) {\n-\t\t\t/* If this happens, it's a bug. */\n+\t\t\t/* If this happens, the changes are identical. */\n \t\t\txdl_free_env(&xe);\n-\t\t\treturn -2;\n+\t\t\tm->mode = 4;\n+\t\t\tcontinue;\n \t\t}\n \t\tx = xscr;\n \t\tm->i1 = xscr->i1 + i1;\n\n"}]}