{"thread":{"id":"33825","subject":"Lines missing from git diff-tree -p -c output?","startedAt":"2013-05-15T14:35:08Z","lastAt":"2013-05-15T19:13:26Z","messageCount":8,"participants":["Matthijs Kooijman","Junio C Hamano"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"217438","messageId":"20130515143508.GO25742@login.drsnuggles.stderr.nl","threadId":"33825","inReplyTo":null,"subject":"Lines missing from git diff-tree -p -c output?","fromName":"Matthijs Kooijman","fromEmail":"matthijs@stdin.nl","sentAt":"2013-05-15T14:35:08Z","receivedAt":"2013-05-15T14:35:08Z","isPatch":false,"sender":{"key":"matthijs@stdin.nl","avatar":"https://avatars.githubusercontent.com/u/194491?v=4"},"body":"Hi folks,\n\nwhile trying to parse git diff-tree output, I found out that in some\ncases it appears to generate an incorrect diff (AFAICT). I orginally\nfound this in a 5-way merge commit in the Linux kernel, but managed to\nreduce this to something a lot more managable (an ordinary 2-way merge\non a 6-line file).\n\nTo start with the wrong-ness, this is the diff generated:\n\n$ git diff-tree -p -c HEAD\nd945a51b6ca22e6e8e550c53980d026f11b05158\ndiff --combined file\nindex 3404f54,0eab113..e8c8c18\n--- a/file\n+++ b/file\n@@@ -1,7 -1,5 +1,6 @@@\n +LEFT\n BASE2\n BASE3\n BASE4\n- BASE5\n+ BASE5MODIFIED\n BASE6\n\nHere, the header claims that the first head has 7 lines, but there really are\nonly 6 (5 lines of context and one delete line). The numbers for the others\nheads are incorrect. In the original diff, the difference was bigger\n(first head was stated to have 28 lines, while the output was similar to\nthe above).\n\nTo find out what's going on, we can look at the -m output, which is\ncorrect (or look at the original file contents at the end of this mail).\n\n$ git diff-tree -m -p HEAD\nd945a51b6ca22e6e8e550c53980d026f11b05158\ndiff --git a/file b/file\nindex 3404f54..e8c8c18 100644\n--- a/file\n+++ b/file\n@@ -1,7 +1,6 @@\n LEFT\n-BASE1\n BASE2\n BASE3\n BASE4\n-BASE5\n+BASE5MODIFIED\n BASE6\nd945a51b6ca22e6e8e550c53980d026f11b05158\ndiff --git a/file b/file\nindex 0eab113..e8c8c18 100644\n--- a/file\n+++ b/file\n@@ -1,3 +1,4 @@\n+LEFT\n BASE2\n BASE3\n BASE4\n\nAs you can see here, first head added \"LEFT\", and the second head removed\n\"BASE1\" and modified \"BASE5\". In the -c diff-tree output above, this removal of\n\"BASE1\" is not shown, but it is counted in the number of lines, causing this\nbreakage.\n\n\nNote that to trigger this behaviour, the number of context lines between the\nBASE1 and BASE5 must be _exactly_ 3, more or less prevents this bug from\noccuring. Also, the \"LEFT\" line introduced does not seem to be\nessential, but there needed to be some change from both sides in order\nto generate a diff at all.\n\nI haven't looked into the code, though I might give that a go later.\nAnyone got any clue why this is happening? Is this really a bug, or am I\nmisunderstanding here?\n\nTo recreate the above situation, you can use the following commands:\n\ngit init\ncat > file < file < file < file < $ git diff-tree -p -c HEAD\n> d945a51b6ca22e6e8e550c53980d026f11b05158\n> diff --combined file\n> index 3404f54,0eab113..e8c8c18\n> --- a/file\n> +++ b/file\n> @@@ -1,7 -1,5 +1,6 @@@\n> +LEFT\n> BASE2\n> BASE3\n> BASE4\n> - BASE5\n> + BASE5MODIFIED\n> BASE6\n\nI found the spot in the code where this is going wrong, there is an\nincorrectly set \"no_pre_delete\" flag for the context lines before each\nhunk. Since a patch says more than a thousand words, here's what I think\nwill fix this problem:\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 77d7872..d36bfcf 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -518,8 +518,11 @@ static int give_context(struct sline *sline, unsigned long cnt, int num_parent)\n unsigned long k;\n \n /* Paint a few lines before the first interesting line. */\n- while (j < i)\n- sline[j++].flag |= mark | no_pre_delete;\n+ while (j < i) {\n+ if (!(sline[j++].flag & mark))\n+ sline[j++].flag |= no_pre_delete;\n+ sline[j++].flag |= mark;\n+ }\n \n again:\n /* we know up to i is to be included. where does the\n\nI'll see if I can write up a testcase and then submit this as a proper\npatch, but I wanted to at least send this over now lest someone wastes\ntime coming to the same conclusion as I did.\n\nGr.\n\nMatthijs\n"},{"id":"217454","messageId":"7vhai4cgco.fsf@alter.siamese.dyndns.org","threadId":"33825","inReplyTo":"20130515143508.GO25742@login.drsnuggles.stderr.nl","subject":"Re: Lines missing from git diff-tree -p -c output?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-15T17:17:43Z","receivedAt":"2013-05-15T17:17:43Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Matthijs Kooijman writes:\n\n> $ git diff-tree -p -c HEAD\n> d945a51b6ca22e6e8e550c53980d026f11b05158\n> diff --combined file\n> index 3404f54,0eab113..e8c8c18\n> --- a/file\n> +++ b/file\n> @@@ -1,7 -1,5 +1,6 @@@\n> +LEFT\n> BASE2\n> BASE3\n> BASE4\n> - BASE5\n> + BASE5MODIFIED\n> BASE6\n>\n> Here, the header claims that the first head has 7 lines, but there really are\n> only 6 (5 lines of context and one delete line). The numbers for the others\n> heads are incorrect. In the original diff, the difference was bigger\n> (first head was stated to have 28 lines, while the output was similar to\n> the above).\n\nThe count and the output does look inconsistent. The hunk header\nclaims that it is showing:\n\n - range 1,7 for the first parent but it should be 1,5 (2, 3, 4, 5 and 6) \n to match the output.\n - range 1,5 for the second parent (left, 2, 3, 4, 5mod, and 6 -- correct)\n - range 1,6 for the result (left, 2, 3, 4, 5mod and 6 -- correct)\n\nIf we resurrect the loss of \"BASE1\" from the output, then the\noutput should have shown:\n\n +LEFT\n - BASE1\n BASE2\n BASE3\n BASE4\n - BASE5\n + BASE5MODIFIED\n BASE6\n\nwhich means the numbers shown for the first parent (1, 2, 3, 4, 5\nand 6) should be 1,6.\n\n> Note that to trigger this behaviour, the number of context lines between the\n> BASE1 and BASE5 must be _exactly_ 3, more or less prevents this bug from\n> occuring.\n\nI think the coalescing of two adjacent hunks into one is painting\nleading lines \"interesting to show context but not worth showing\ndeletion before it\" incorrectly.\n\nDoes this patch fix the issue?\n\n combine-diff.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 77d7872..7359b84 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -533,7 +533,7 @@ static int give_context(struct sline *sline, unsigned long cnt, int num_parent)\n \t\tk = find_next(sline, mark, j, cnt, 0);\n \t\tj = adjust_hunk_tail(sline, all_mask, i, j);\n \n-\t\tif (k < j + context) {\n+\t\tif (k <= j + context) {\n \t\t\t/* k is interesting and [j,k) are not, but\n \t\t\t * paint them interesting because the gap is small.\n \t\t\t */\n"},{"id":"217457","messageId":"20130515173312.GR25742@login.drsnuggles.stderr.nl","threadId":"33825","inReplyTo":"7vhai4cgco.fsf@alter.siamese.dyndns.org","subject":"Re: Lines missing from git diff-tree -p -c output?","fromName":"Matthijs Kooijman","fromEmail":"matthijs@stdin.nl","sentAt":"2013-05-15T17:33:12Z","receivedAt":"2013-05-15T17:33:12Z","isPatch":false,"sender":{"key":"matthijs@stdin.nl","avatar":"https://avatars.githubusercontent.com/u/194491?v=4"},"body":"Hi Junio,\n\n> I think the coalescing of two adjacent hunks into one is painting\n> leading lines \"interesting to show context but not worth showing\n> deletion before it\" incorrectly.\nYup, that seems to be the case.\n\n> Does this patch fix the issue?\n\nYes, it fixes the issue. However, I think that this patch actually hides\nthe real problem (in a way that will always work with the current code,\nthough).\n\nI had come up with a different fix myself (similar to the one I sent to\nthe list as a followup, but that one still had a bug), which I think\nmight be better. In any case, it includes a testcase for this bug which\nseems good to include.\n\nI'll send my patch as a followup in a minute, feel free to use it\nentirely or only partially.\n\nGr.\n\nMatthijs\n"},{"id":"217462","messageId":"1368639734-27746-1-git-send-email-matthijs@stdin.nl","threadId":"33825","inReplyTo":"20130515173312.GR25742@login.drsnuggles.stderr.nl","subject":"[PATCH] combine-diff.c: Fix output when changes are exactly 3 lines apart","fromName":"Matthijs Kooijman","fromEmail":"matthijs@stdin.nl","sentAt":"2013-05-15T17:42:14Z","receivedAt":"2013-05-15T17:42:14Z","isPatch":true,"sender":{"key":"matthijs@stdin.nl","avatar":"https://avatars.githubusercontent.com/u/194491?v=4"},"body":"When a deletion is followed by exactly 3 (or whatever the number of\ncontext lines) unchanged lines, followed by another change, the combined\ndiff output would hide the first deletion, resulting in a malformed\ndiff.\n\nThis happened because the 3 lines before each change are painted\ninteresting, but also marked as no_pre_delete to prevent showing deletes\nthat were previously marked as uninteresting. This behaviour was\nintroduced in c86fbe53 (diff -c/--cc: do not include uninteresting\ndeletion before leading context). However, as a side effect, this could\nalso mark deletes that were already interesting as no_pre_delete. This\nwould happen only if the delete was exactly 3 lines away from the next\nchange, since lines farther away would not be touched by the \"paint\nthree lines before the change\" code and lines closer would be painted\nby the \"merge two adjacent hunks\" code instead, which does not set the\nno_pre_delete flag.\n\nThis commit fixes this problem by only setting the no_pre_delete flag\nfor changes that were previously uninteresting.\n\nSigned-off-by: Matthijs Kooijman \n---\n combine-diff.c | 7 +++++--\n t/t4038-diff-combined.sh | 47 +++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 52 insertions(+), 2 deletions(-)\n\ndiff --git a/combine-diff.c b/combine-diff.c\nindex 77d7872..3e8bb17 100644\n--- a/combine-diff.c\n+++ b/combine-diff.c\n@@ -518,8 +518,11 @@ static int give_context(struct sline *sline, unsigned long cnt, int num_parent)\n \t\tunsigned long k;\n \n \t\t/* Paint a few lines before the first interesting line. */\n-\t\twhile (j < i)\n-\t\t\tsline[j++].flag |= mark | no_pre_delete;\n+\t\twhile (j < i) {\n+\t\t\tif (!(sline[j].flag & mark))\n+\t\t\t\tsline[j].flag |= no_pre_delete;\n+\t\t\tsline[j++].flag |= mark;\n+\t\t}\n \n \tagain:\n \t\t/* we know up to i is to be included. where does the\ndiff --git a/t/t4038-diff-combined.sh b/t/t4038-diff-combined.sh\nindex 1261dbb..a23ca7e 100755\n--- a/t/t4038-diff-combined.sh\n+++ b/t/t4038-diff-combined.sh\n@@ -353,4 +353,51 @@ test_expect_failure 'combine diff coalesce three parents' '\n \tcompare_diff_patch expected actual\n '\n \n+# Test for a bug reported at\n+# http://thread.gmane.org/gmane.comp.version-control.git/224410\n+# where a delete lines were missing from combined diff output when they\n+# occurred exactly before the context lines of a later change.\n+test_expect_success 'combine diff missing delete bug' '\n+\tgit commit -m initial --allow-empty &&\n+\tcat <<-\\EOF >test &&\n+\t1\n+\t2\n+\t3\n+\t4\n+\tEOF\n+\tgit add test\n+\tgit commit -a -m side1 &&\n+\tgit checkout -B side1 &&\n+\tgit checkout HEAD^ &&\n+\tcat <<-\\EOF >test &&\n+\t0\n+\t1\n+\t2\n+\t3\n+\t4modified\n+\tEOF\n+\tgit commit -a -m side2 &&\n+\tgit branch -f side2 &&\n+\ttest_must_fail git merge --no-commit side1 &&\n+\tcat <<-\\EOF >test &&\n+\t1\n+\t2\n+\t3\n+\t4modified\n+\tEOF\n+\tgit add test &&\n+\tgit commit -a -m merge &&\n+\tgit diff-tree -c -p HEAD >actual.tmp &&\n+\tsed -e \"1,/^@@@/d\" < actual.tmp >actual &&\n+\ttr -d Q <<-\\EOF >expected &&\n+\t- 0\n+\t 1\n+\t 2\n+\t 3\n+\t -4\n+\t +4modified\n+\tEOF\n+\tcompare_diff_patch expected actual\n+'\n+\n test_done\n-- \n1.8.3.rc1\n"},{"id":"217459","messageId":"7v4ne4cexm.fsf@alter.siamese.dyndns.org","threadId":"33825","inReplyTo":"20130515173312.GR25742@login.drsnuggles.stderr.nl","subject":"Re: Lines missing from git diff-tree -p -c output?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-15T17:48:21Z","receivedAt":"2013-05-15T17:48:21Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Matthijs Kooijman writes:\n\n> Hi Junio,\n>\n>> I think the coalescing of two adjacent hunks into one is painting\n>> leading lines \"interesting to show context but not worth showing\n>> deletion before it\" incorrectly.\n> Yup, that seems to be the case.\n>\n>> Does this patch fix the issue?\n>\n> Yes, it fixes the issue. However, I think that this patch actually hides\n> the real problem (in a way that will always work with the current code,\n> though).\n\nCould you explain why you think it hides the real problem, and what\nkind of future enhancement may break it?\n\nThis is *not* my usual rhetorical question \"Please explain yourself,\nbecause I think you are wrong\", but is \"I do not understand the\nreasoning behind your statement, and I (and the reasoning behind my\npatch) must be missing something important, so please enlighten me\nby pointing out where I am wrong, so that I won't stick to my flawed\npatch\".\n\nThe painting with no_pre_delete is applied when we extend the common\ncontext back to lines we _know_ otherwise not worth showing (because\nthere is no difference) only because we want to show them as the\ncontext lines and we do not need to show deletions that come before\nthese common context. By forcing (k == j + context) case, that is,\nthere are exactly \"context\" number of lines between the end of the\ncurrent hunk and the next hunk, which the old code would have showed\n\"context\" lines at the beginning of the next hunk, to go back to the\n\"again\" label, we are coalescing the two hunks that _should_ have\nbeen shown together anyway, without painting the context lines\nincorrectly with \"before this line, do not show deletion\" mark.\n\n> I had come up with a different fix myself (similar to the one I sent to\n> the list as a followup, but that one still had a bug), which I think\n> might be better. In any case, it includes a testcase for this bug which\n> seems good to include.\n>\n> I'll send my patch as a followup in a minute, feel free to use it\n> entirely or only partially.\n>\n> Gr.\n>\n> Matthijs\n"},{"id":"217465","messageId":"20130515181734.GT25742@login.drsnuggles.stderr.nl","threadId":"33825","inReplyTo":"7v4ne4cexm.fsf@alter.siamese.dyndns.org","subject":"Re: Lines missing from git diff-tree -p -c output?","fromName":"Matthijs Kooijman","fromEmail":"matthijs@stdin.nl","sentAt":"2013-05-15T18:17:34Z","receivedAt":"2013-05-15T18:17:34Z","isPatch":false,"sender":{"key":"matthijs@stdin.nl","avatar":"https://avatars.githubusercontent.com/u/194491?v=4"},"body":"Hi Junio,\n\n> Could you explain why you think it hides the real problem, and what\n> kind of future enhancement may break it?\nI think the differences is mostly in the locality of the fix. In my\nproposed patch, the no_pre_delete flag is never set on an interesting\nline because it is checked in the line before it. In your patch, it\nnever happens because the control flow guarantees the \"context\" lines\nbefore each change must be uninteresting.\n\nThe net effect is of course identical, but I'm arguing that depending on\nthe control flow and some code a doze lines down is easier to break than\ndepending on a previous line.\n\nHaving said that: I'm not sure if the difference is significant enough\nto convince me in either direction.\n\n\n\nHowever, thinking about this a bit more (and getting sidetracked on a\ncompletely separate issue/question), I wonder why the coalescing-hunks\ncode is there in the first place? e.g., why not leave out these lines?\n\n\tif (k < j + context) {\n\t\t/* k is interesting and [j,k) are not, but\n\t\t * paint them interesting because the gap is small.\n\t\t */\n\t\twhile (j < k)\n\t\t\tsline[j++].flag |= mark;\n\t\ti = k;\n\t\tgoto again;\n\t}\n\nIf the \"context\" lines before and after each group of changes are\npainted interesting, then these lines in between will also be painted\ninteresting. Of course, this could cause some lines to be painted as\ninteresting twice and it needs my fix for the no_pre_delete thing, but\nit would work just as well?\n\nHowever, I can imagine that this code is present to prevent painting\nlines twice, which would of course be a bit of a performance loss. But\nif this really was the motivation, why is the first if not something\nlike:\n\n\tif (k <= j + 2 * context) {\n\nSince IIUC, the current code can still paint a few context lines twice\nwhen they are exacly \"context\" lines apart, once by the \"paint before\"\nand one by the \"paint after\" code (which is also what happens in my bug\nexample, I think). The above should \"fix\" that as well (the first part\nof the test suite hasn't complained so far).\n\nGr.\n\nMatthijs\n"},{"id":"217469","messageId":"7vd2ssawfd.fsf@alter.siamese.dyndns.org","threadId":"33825","inReplyTo":"20130515181734.GT25742@login.drsnuggles.stderr.nl","subject":"Re: Lines missing from git diff-tree -p -c output?","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-15T19:13:26Z","receivedAt":"2013-05-15T19:13:26Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Matthijs Kooijman writes:\n\n>> Could you explain why you think it hides the real problem, and what\n>> kind of future enhancement may break it?\n> I think the differences is mostly in the locality of the fix. In my\n> proposed patch, the no_pre_delete flag is never set on an interesting\n> line because it is checked in the line before it. In your patch, it\n> never happens because the control flow guarantees the \"context\" lines\n> before each change must be uninteresting.\n>\n> The net effect is of course identical, but I'm arguing that depending on\n> the control flow and some code a doze lines down is easier to break than\n> depending on a previous line.\n\nYeah, that sounds like a reasonable reasoning.\n"}]}