{"thread":{"id":"3858","subject":"[RFH] shifting xdiff hunks?","startedAt":"2006-04-13T06:30:03Z","lastAt":"2006-04-13T23:31:58Z","messageCount":5,"participants":["Junio C Hamano","Davide Libenzi","Jakub Narebski"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"18602","messageId":"7vmzeqyolw.fsf@assigned-by-dhcp.cox.net","threadId":"3858","inReplyTo":null,"subject":"[RFH] shifting xdiff hunks?","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-13T06:30:03Z","receivedAt":"2006-04-13T06:30:03Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I was looking at one diff produced from my work-in-progress,\nwhich looked like this...\n\n    diff --git a/Documentation/git.txt b/Documentation/git.txt\n    index 06b2e53..f72abfc 100644\n    --- a/Documentation/git.txt\n    +++ b/Documentation/git.txt\n    @@ -265,6 +265,9 @@ gitlink:git-checkout[1]::\n     gitlink:git-cherry-pick[1]::\n            Cherry-pick the effect of an existing commit.\n\n    +gitlink:git-clean[1]::\n    +       Remove untracked files from the working tree.\n    +\n     gitlink:git-clone[1]::\n            Clones a repository into a new directory.\n\n    @@ -318,6 +321,9 @@ gitlink:git-resolve[1]::\n\n     gitlink:git-revert[1]::\n            Revert an existing commit.\n    +\n    +gitlink:git-rm[1]::\n    +       Remove files from the working tree and from the index.\n\n     gitlink:git-shortlog[1]::\n            Summarizes 'git log' output.\n\nThe first hunk begins by an addition of a couple of non-blank\nline followed by an addition of a blank line.  The second hunk,\nwhile it does the same thing, is shown differently.\n\nNow, from correctness point of view, this is not a problem at\nall, but I am wondering if xdiff can help to always shift the\nhunk down or up to consistently produce one way or another\n(personally I feel the former is easier to read).\n\nHere is a rough sketch of what I think I want.  When we have\nadditions, as long as the first line added happens to match the\nfirst line that is common between the versions that comes after\nthe added hunk (that is, in the case of the second hunk above,\nthe empty line before \"gitlink:git-rm[1]\" happens to match the\nempty line after the added three lines), roll the hunk down by\none, until you cannot roll it down anymore.\n\nJust in case I get misinterpreted, I am not talking about\ntreating empty lines in any special way.  It is more about\n\"starting the hunk with actually changed line\".  The first hunk\nabove clearly begins with something added, while the second one\ndoes not.\n\nIs this something easy to do with the xdiff code?\n"},{"id":"18603","messageId":"Pine.LNX.4.64.0604122348010.7104@alien.or.mcafeemobile.com","threadId":"3858","inReplyTo":"7vmzeqyolw.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFH] shifting xdiff hunks?","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-04-13T06:52:34Z","receivedAt":"2006-04-13T06:52:34Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Wed, 12 Apr 2006, Junio C Hamano wrote:\n\n> The first hunk begins by an addition of a couple of non-blank\n> line followed by an addition of a blank line.  The second hunk,\n> while it does the same thing, is shown differently.\n>\n> Now, from correctness point of view, this is not a problem at\n> all, but I am wondering if xdiff can help to always shift the\n> hunk down or up to consistently produce one way or another\n> (personally I feel the former is easier to read).\n\nNext on your screens, Junio and Linus in the new commedy \"Pickier and Pickiest\" :)\n\n\n\n> Here is a rough sketch of what I think I want.  When we have\n> additions, as long as the first line added happens to match the\n> first line that is common between the versions that comes after\n> the added hunk (that is, in the case of the second hunk above,\n> the empty line before \"gitlink:git-rm[1]\" happens to match the\n> empty line after the added three lines), roll the hunk down by\n> one, until you cannot roll it down anymore.\n>\n> Just in case I get misinterpreted, I am not talking about\n> treating empty lines in any special way.  It is more about\n> \"starting the hunk with actually changed line\".  The first hunk\n> above clearly begins with something added, while the second one\n> does not.\n>\n> Is this something easy to do with the xdiff code?\n\nYes, this is what GNU diff does. It's a post-process of the edit script. \nNot a problem at all. Till this weekend (included) I'm pretty booked, but \nI'll do that in the following days.\n\n\n\n- Davide\n"},{"id":"18606","messageId":"e1kvft$4r2$1@sea.gmane.org","threadId":"3858","inReplyTo":"7vmzeqyolw.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFH] shifting xdiff hunks?","fromName":"Jakub Narebski","fromEmail":"jnareb@gmail.com","sentAt":"2006-04-13T07:44:13Z","receivedAt":"2006-04-13T07:44:13Z","isPatch":false,"sender":{"key":"jnareb@gmail.com","avatar":"https://avatars.githubusercontent.com/u/2706?v=4"},"body":"Junio C. Hamano wrote:\n \n> Now, from correctness point of view, this is not a problem at\n> all, but I am wondering if xdiff can help to always shift the\n> hunk down or up to consistently produce one way or another\n> (personally I feel the former is easier to read).\n\nThis would also help with adding new functions, as sometimes diff begins\nwith the closing brace of the preceding function, instead of ending with\nclosing brace of the added function.\n\nJust my own 0.2 eurocents.\n\n-- \nJakub Narebski\nWarsaw, Poland\n"},{"id":"18626","messageId":"Pine.LNX.4.64.0604131452250.10564@alien.or.mcafeemobile.com","threadId":"3858","inReplyTo":"Pine.LNX.4.64.0604122348010.7104@alien.or.mcafeemobile.com","subject":"Re: [RFH] shifting xdiff hunks?","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-04-13T21:55:48Z","receivedAt":"2006-04-13T21:55:48Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Wed, 12 Apr 2006, Davide Libenzi wrote:\n\n> Yes, this is what GNU diff does. It's a post-process of the edit script. Not \n> a problem at all. Till this weekend (included) I'm pretty booked, but I'll do \n> that in the following days.\n\nDang, that was a short weekend. I found a lunch-time hour for this. Would \nyou try to see if this libxdiff-based diff merges on your tree?\nSee also how it looks for you.\n\n\n\n- Davide\n\n\n\n--- a/xdiffi.c\n+++ b/xdiffi.c\n@@ -45,6 +45,8 @@\n \t\t      long *kvdf, long *kvdb, int need_min, xdpsplit_t *spl,\n \t\t      xdalgoenv_t *xenv);\n static xdchange_t *xdl_add_change(xdchange_t *xscr, long i1, long i2, long chg1, long chg2);\n+static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo);\n+\n \n \n \n@@ -394,6 +396,110 @@\n }\n \n \n+static int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo) {\n+\tlong ix, ixo, ixs, ixref, grpsiz, nrec = xdf->nrec;\n+\tchar *rchg = xdf->rchg, *rchgo = xdfo->rchg;\n+\txrecord_t **recs = xdf->recs;\n+\n+\t/*\n+\t * This is the same of what GNU diff does. Move back and forward\n+\t * change groups for a consistent and pretty diff output. This also\n+\t * helps in finding joineable change groups and reduce the diff size.\n+\t */\n+\tfor (ix = ixo = 0;;) {\n+\t\t/*\n+\t\t * Find the first changed line in the to-be-compacted file.\n+\t\t * We need to keep track of both indexes, so if we find a\n+\t\t * changed lines group on the other file, while scanning the\n+\t\t * to-be-compacted file, we need to skip it properly. Note\n+\t\t * that loops that are testing for changed lines on rchg* do\n+\t\t * not need index bounding since the array is prepared with\n+\t\t * a zero at position -1 and N.\n+\t\t */\n+\t\tfor (; ix < nrec && !rchg[ix]; ix++)\n+\t\t\twhile (rchgo[ixo++]);\n+\t\tif (ix == nrec)\n+\t\t\tbreak;\n+\n+\t\t/*\n+\t\t * Record the start of a changed-group in the to-be-compacted file\n+\t\t * and find the end of it, on both to-be-compacted and other file\n+\t\t * indexes (ix and ixo).\n+\t\t */\n+\t\tixs = ix;\n+\t\tfor (ix++; rchg[ix]; ix++);\n+\t\tfor (; rchgo[ixo]; ixo++);\n+\n+\t\tdo {\n+\t\t\tgrpsiz = ix - ixs;\n+\n+\t\t\t/*\n+\t\t\t * If the line before the current change group, is equal to\n+\t\t\t * the last line of the current change group, shift backward\n+\t\t\t * the group.\n+\t\t\t */\n+\t\t\twhile (ixs > 0 && recs[ixs - 1]->ha == recs[ix - 1]->ha &&\n+\t\t\t       XDL_RECMATCH(recs[ixs - 1], recs[ix - 1])) {\n+\t\t\t\trchg[--ixs] = 1;\n+\t\t\t\trchg[--ix] = 0;\n+\n+\t\t\t\t/*\n+\t\t\t\t * This change might have joined two change groups,\n+\t\t\t\t * so we try to take this scenario in account by moving\n+\t\t\t\t * the start index accordingly (and so the other-file\n+\t\t\t\t * end-of-group index).\n+\t\t\t\t */\n+\t\t\t\tfor (; rchg[ixs - 1]; ixs--);\n+\t\t\t\twhile (rchgo[--ixo]);\n+\t\t\t}\n+\n+\t\t\t/*\n+\t\t\t * Record the end-of-group position in case we are matched\n+\t\t\t * with a group of changes in the other file (that is, the\n+\t\t\t * change record before the enf-of-group index in the other\n+\t\t\t * file is set).\n+\t\t\t */\n+\t\t\tixref = rchgo[ixo - 1] ? ix: nrec;\n+\n+\t\t\t/*\n+\t\t\t * If the first line of the current change group, is equal to\n+\t\t\t * the line next of the current change group, shift forward\n+\t\t\t * the group.\n+\t\t\t */\n+\t\t\twhile (ix < nrec && recs[ixs]->ha == recs[ix]->ha &&\n+\t\t\t       XDL_RECMATCH(recs[ixs], recs[ix])) {\n+\t\t\t\trchg[ixs++] = 0;\n+\t\t\t\trchg[ix++] = 1;\n+\n+\t\t\t\t/*\n+\t\t\t\t * This change might have joined two change groups,\n+\t\t\t\t * so we try to take this scenario in account by moving\n+\t\t\t\t * the start index accordingly (and so the other-file\n+\t\t\t\t * end-of-group index). Keep tracking the reference\n+\t\t\t\t * index in case we are shifting together with a\n+\t\t\t\t * corresponding group of changes in the other file.\n+\t\t\t\t */\n+\t\t\t\tfor (; rchg[ix]; ix++);\n+\t\t\t\twhile (rchgo[++ixo])\n+\t\t\t\t\tixref = ix;\n+\t\t\t}\n+\t\t} while (grpsiz != ix - ixs);\n+\n+\t\t/*\n+\t\t * Try to move back the possibly merged group of changes, to match\n+\t\t * the recorded postion in the other file.\n+\t\t */\n+\t\twhile (ixref < ix) {\n+\t\t\trchg[--ixs] = 1;\n+\t\t\trchg[--ix] = 0;\n+\t\t\twhile (rchgo[--ixo]);\n+\t\t}\n+\t}\n+\n+\treturn 0;\n+}\n+\n+\n int xdl_build_script(xdfenv_t *xe, xdchange_t **xscr) {\n \txdchange_t *cscr = NULL, *xch;\n \tchar *rchg1 = xe->xdf1.rchg, *rchg2 = xe->xdf2.rchg;\n@@ -439,13 +545,13 @@\n \n \t\treturn -1;\n \t}\n-\n-\tif (xdl_build_script(&xe, &xscr) < 0) {\n+\tif (xdl_change_compact(&xe.xdf1, &xe.xdf2) < 0 ||\n+\t    xdl_change_compact(&xe.xdf2, &xe.xdf1) < 0 ||\n+\t    xdl_build_script(&xe, &xscr) < 0) {\n \n \t\txdl_free_env(&xe);\n \t\treturn -1;\n \t}\n-\n \tif (xscr) {\n \t\tif (xdl_emit_diff(&xe, xscr, ecb, xecfg) < 0) {\n \n@@ -453,10 +559,8 @@\n \t\t\txdl_free_env(&xe);\n \t\t\treturn -1;\n \t\t}\n-\n \t\txdl_free_script(xscr);\n \t}\n-\n \txdl_free_env(&xe);\n \n \treturn 0;\n\n\n\n"},{"id":"18630","messageId":"7vslohvyq9.fsf@assigned-by-dhcp.cox.net","threadId":"3858","inReplyTo":"Pine.LNX.4.64.0604131452250.10564@alien.or.mcafeemobile.com","subject":"Re: [RFH] shifting xdiff hunks?","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-13T23:31:58Z","receivedAt":"2006-04-13T23:31:58Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Davide Libenzi <davidel@xmailserver.org> writes:\n\n> On Wed, 12 Apr 2006, Davide Libenzi wrote:\n>\n>> Yes, this is what GNU diff does. It's a post-process of the edit\n>> script. Not a problem at all. Till this weekend (included) I'm\n>> pretty booked, but I'll do that in the following days.\n>\n> Dang, that was a short weekend. I found a lunch-time hour for\n> this. Would you try to see if this libxdiff-based diff merges on your\n> tree?\n> See also how it looks for you.\n\nVery impressed, and pleased with the result.  I've only taken a\ncursory look, but with a very limited number of tests, it looks\nmuch better.  Thanks.\n\nFor the sake of full disclosure, the reason I wanted consistency\nwas not for the diff output I quoted earlier, but to help making\nthe combined patch output cleaner.  It does reduce false match\nfrom the infamous 12-way Octopus by Len Brown:\n\n\tgit diff-tree --cc 9fdb62af92c741addbea15545f214a6e89460865\n"}]}