{"thread":{"id":"49222","subject":"Possible bug: identical lines added/removed in git diff","startedAt":"2018-08-27T01:54:52Z","lastAt":"2018-09-01T15:23:49Z","messageCount":9,"participants":["Gabriel Holodak","Stefan Beller","Jeff King","Johannes Schindelin"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"356567","messageId":"CAE6=WB_4_PhjfQpubFcYkNKejfDr22s-y0nPQKw5Yd4GVaN4Yw@mail.gmail.com","threadId":"49222","inReplyTo":null,"subject":"Possible bug: identical lines added/removed in git diff","fromName":"Gabriel Holodak","fromEmail":"gthepiper@gmail.com","sentAt":"2018-08-27T01:54:33Z","receivedAt":"2018-08-27T01:54:52Z","isPatch":false,"sender":{"key":"gthepiper@gmail.com","avatar":null},"body":"I think I'm running into a bug with git diff on v2.18.0. When I diff\nthe attached files, part of the diff ends up looking like:\n...\n STARTCHAR U+00F0\n ENCODING 240\n SWIDTH 500 0\n-DWIDTH 8 0\n-BBX 7 12 1 0\n-BITMAP\n-12\n-0C\n-14\n-22\n-02\n-3E\n-42\n-42\n-82\n-84\n-84\n-78\n+DWIDTH 8 0\n+BBX 8 12 0 0\n+BITMAP\n+1B\n+0E\n+1E\n+33\n+03\n+3F\n+63\n+63\n+C3\n+C6\n+C6\n+7C\n ENDCHAR\n STARTCHAR U+00F1\n...\nwhere the \"DWIDTH 8 0\" and \"BITMAP\" lines are removed and added,\ndespite being identical. It only seems to be happening around this\nsection of the file, for the U+00F0 character. This also seems close\nto a minimal reproduction of the issue. If I git add --patch and stage\na few hunks, then the duplicated lines seem to disappear.\n\nSteps to reproduce:\ngit diff --no-index unitera_bold_italic.bdf.old unitera_bold_italic.bdf.new\n(It also happens inside a repo, this just seemed the easiest way to\ndemonstrate.)\n\nGabriel Holodak\n"},{"id":"356595","messageId":"CAGZ79kZ1BVTLnNYSs+NjEO1T1-PySSdZzVU-0ZfivjT_pfvviQ@mail.gmail.com","threadId":"49222","inReplyTo":"CAE6=WB_4_PhjfQpubFcYkNKejfDr22s-y0nPQKw5Yd4GVaN4Yw@mail.gmail.com","subject":"Re: Possible bug: identical lines added/removed in git diff","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-08-27T17:47:09Z","receivedAt":"2018-08-27T17:47:24Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Sun, Aug 26, 2018 at 6:54 PM Gabriel Holodak wrote:\n>\n> I think I'm running into a bug with git diff on v2.18.0.\n\nI cannot reproduce with the two files attached.\n\nI suspected you might have a different diff algorithm configured,\nso I tested\n git diff --no-index old new\n git diff --patience --no-index old new\n git diff --histogram --no-index old new\n\nall of which do not reproduce the issue.\n\nAre there any encoding issues locally (Which platform\nare you on?) or in transit (Could you re-download the files\nfrom [1] and confirm it still produces this bug?)\n\n[1] https://public-inbox.org/git/CAE6=WB_4_PhjfQpubFcYkNKejfDr22s-y0nPQKw5Yd4GVaN4Yw@mail.gmail.com/\n\n\n> where the \"DWIDTH 8 0\" and \"BITMAP\" lines are removed and added,\n> despite being identical. It only seems to be happening around this\n> section of the file, for the U+00F0 character. This also seems close\n> to a minimal reproduction of the issue.\n\nCould you cut down to a real minimal reproduction, i.e. just these 20\nlines or so?\n\n> If I git add --patch and stage\n> a few hunks, then the duplicated lines seem to disappear.\n\nDo you have any smudge filters or configuration regarding\nline endings?\n\nAre the lines really different or the same ? (Can you inspect with a\nhex editor, maybe there are different kinds of invisible white spaces?)\n\n> Steps to reproduce:\n> git diff --no-index unitera_bold_italic.bdf.old unitera_bold_italic.bdf.new\n> (It also happens inside a repo, this just seemed the easiest way to\n> demonstrate.)\n\nThanks,\nStefan\n"},{"id":"356924","messageId":"CAE6=WB_t7zG3jtELiMfggqxjvD4jJyJ02pNPmV3fey=3nSejuA@mail.gmail.com","threadId":"49222","inReplyTo":"CAGZ79kZ1BVTLnNYSs+NjEO1T1-PySSdZzVU-0ZfivjT_pfvviQ@mail.gmail.com","subject":"Re: Possible bug: identical lines added/removed in git diff","fromName":"Gabriel Holodak","fromEmail":"gthepiper@gmail.com","sentAt":"2018-08-30T02:10:25Z","receivedAt":"2018-08-30T02:10:36Z","isPatch":false,"sender":{"key":"gthepiper@gmail.com","avatar":null},"body":"I did have some possibly interfering settings in my .gitconfig\npreviously. I removed everything, so all the commands I'll describe\nwere run with an empty config.\n\nOn Mon, Aug 27, 2018 at 1:47 PM Stefan Beller wrote:\n> I suspected you might have a different diff algorithm configured,\n> so I tested\n> git diff --no-index old new\n> git diff --patience --no-index old new\n> git diff --histogram --no-index old new\n>\n> all of which do not reproduce the issue.\n\nI don't believe I had any settings to change the algorithm. Using any\nof --minimal, --patience, or --histogram seems to fix the issue. It\nstill occurs with --diff-algorithm=default. I also tried\n--no-indent-heuristic, which had no effect.\n\n> Are there any encoding issues locally (Which platform\n> are you on?) or in transit (Could you re-download the files\n> from [1] and confirm it still produces this bug?)\n>\n> [1] https://public-inbox.org/git/CAE6=WB_4_PhjfQpubFcYkNKejfDr22s-y0nPQKw5Yd4GVaN4Yw@mail.gmail.com/\n\nI should have mentioned before, this is on Arch Linux. I can reproduce\nfrom the downloaded files. I can also reproduce on macOS 10.13.6, with\ngit 2.18.0.\n\n> Could you cut down to a real minimal reproduction, i.e. just these 20\n> lines or so?\n\nI'm working on getting down to a minimal reproduction, a few lines at\na time. One thing that seems strange: as I've removed lines, there are\na bunch of lines that don't matter. Then I'll find some lines that, if\nremoved, completely fix the issue. But the ordering for these\napparently important lines doesn't matter. They just have to be\nsomewhere in the file to cause the duplicated diffs.\n\nI'll upload again when I've figured out all the unimportant lines to remove.\n\n> Do you have any smudge filters or configuration regarding\n> line endings?\n\nNo filters, I did have core.autocrlf = input. But as I mentioned, I\ncan also reproduce with an empty config.\n\n> Are the lines really different or the same ? (Can you inspect with a\n> hex editor, maybe there are different kinds of invisible white spaces?)\n\nYep, the lines in question are identical.\n\nThanks for looking into this.\nGabriel\n"},{"id":"356929","messageId":"20180830025457.GA665@sigill.intra.peff.net","threadId":"49222","inReplyTo":"CAE6=WB_t7zG3jtELiMfggqxjvD4jJyJ02pNPmV3fey=3nSejuA@mail.gmail.com","subject":"Re: Possible bug: identical lines added/removed in git diff","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-30T02:54:57Z","receivedAt":"2018-08-30T02:55:00Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Aug 29, 2018 at 10:10:25PM -0400, Gabriel Holodak wrote:\n\n> > Could you cut down to a real minimal reproduction, i.e. just these 20\n> > lines or so?\n> \n> I'm working on getting down to a minimal reproduction, a few lines at\n> a time. One thing that seems strange: as I've removed lines, there are\n> a bunch of lines that don't matter. Then I'll find some lines that, if\n> removed, completely fix the issue. But the ordering for these\n> apparently important lines doesn't matter. They just have to be\n> somewhere in the file to cause the duplicated diffs.\n> \n> I'll upload again when I've figured out all the unimportant lines to remove.\n\nYeah, I reproduced based on your initial post, but noticed that when I\ncut it down the problem went away.\n\nAn easy and pretty mechanical reproduction is:\n\n git diff --no-index unitera_bold_italic.bdf.{old,new} |\n sed -ne '/STARTCHAR U+00F0/,/ENDCHAR/p'\n\nwhich shows a hunk that could easily be reduced by its first line\n(\"DWIDTH 8 0\"), and which has a common line in the middle of -/+ run.\nBut if we cut it down to the lines in that hunk, like this:\n\n for i in unitera_bold_italic.bdf.{old,new}; do\n sed -ne '/STARTCHAR U+00F0/,/ENDCHAR/p' <$i >$i.cut\n done\n git diff --no-index unitera_bold_italic.bdf.{old,new}.cut\n\nthen those two lines become context.\n\nI note also that GNU \"diff -u\" gets this case right.\n\n> > Do you have any smudge filters or configuration regarding\n> > line endings?\n> \n> No filters, I did have core.autocrlf = input. But as I mentioned, I\n> can also reproduce with an empty config.\n\nMe too. Amusingly, if you have diff.colorMoved configured, the context\nlines appear as moves, showing that we really do know they're the same\n(but that happens as post-diff processing, so I am not at all surprised\nthat it is orthogonal to the original issue).\n\n-Peff\n"},{"id":"357003","messageId":"CAGZ79kZNVw4-q9KYAi9G3axb7-Ggpc2EAK8ZxAZoPEnZvEL-DQ@mail.gmail.com","threadId":"49222","inReplyTo":"20180830025457.GA665@sigill.intra.peff.net","subject":"Re: Possible bug: identical lines added/removed in git diff","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-08-30T19:16:22Z","receivedAt":"2018-08-30T19:16:36Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Wed, Aug 29, 2018 at 7:54 PM Jeff King wrote:\n>\n> On Wed, Aug 29, 2018 at 10:10:25PM -0400, Gabriel Holodak wrote:\n>\n> > > Could you cut down to a real minimal reproduction, i.e. just these 20\n> > > lines or so?\n> >\n> > I'm working on getting down to a minimal reproduction, a few lines at\n> > a time. One thing that seems strange: as I've removed lines, there are\n> > a bunch of lines that don't matter. Then I'll find some lines that, if\n> > removed, completely fix the issue. But the ordering for these\n> > apparently important lines doesn't matter. They just have to be\n> > somewhere in the file to cause the duplicated diffs.\n> >\n> > I'll upload again when I've figured out all the unimportant lines to remove.\n>\n> Yeah, I reproduced based on your initial post, but noticed that when I\n> cut it down the problem went away.\n\nOh, I had to look further down than I did initially. Now I can reproduce it\nfrom the initial data as well.\n\nNote that it goes away with --minimal.\n\nI have a patch cooking (which was sent out as\nhttps://public-inbox.org/git/20180810221857.87399-1-sbeller@google.com/)\n\nand one of the weaknesses in that patch is the lack of explanation on\nwhen the heuristic is applied as I have not fully understood it yet.\n"},{"id":"357004","messageId":"20180830192019.GB19685@sigill.intra.peff.net","threadId":"49222","inReplyTo":"CAGZ79kZNVw4-q9KYAi9G3axb7-Ggpc2EAK8ZxAZoPEnZvEL-DQ@mail.gmail.com","subject":"Re: Possible bug: identical lines added/removed in git diff","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2018-08-30T19:20:19Z","receivedAt":"2018-08-30T19:20:23Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Thu, Aug 30, 2018 at 12:16:22PM -0700, Stefan Beller wrote:\n\n> On Wed, Aug 29, 2018 at 7:54 PM Jeff King wrote:\n> >\n> > On Wed, Aug 29, 2018 at 10:10:25PM -0400, Gabriel Holodak wrote:\n> >\n> > > > Could you cut down to a real minimal reproduction, i.e. just these 20\n> > > > lines or so?\n> > >\n> > > I'm working on getting down to a minimal reproduction, a few lines at\n> > > a time. One thing that seems strange: as I've removed lines, there are\n> > > a bunch of lines that don't matter. Then I'll find some lines that, if\n> > > removed, completely fix the issue. But the ordering for these\n> > > apparently important lines doesn't matter. They just have to be\n> > > somewhere in the file to cause the duplicated diffs.\n> > >\n> > > I'll upload again when I've figured out all the unimportant lines to remove.\n> >\n> > Yeah, I reproduced based on your initial post, but noticed that when I\n> > cut it down the problem went away.\n> \n> Oh, I had to look further down than I did initially. Now I can reproduce it\n> from the initial data as well.\n> \n> Note that it goes away with --minimal.\n\nThat's interesting. I did wonder if this was in fact a bug, or simply\nthat Myers does not promise to find the absolute minimal diff. I'm\n_still_ not sure, especially because the minimization is so obvious in\nthis case (literally the first \"-\" and the first \"+\" line of a\ncontiguous hunk are identical).\n\n> I have a patch cooking (which was sent out as\n> https://public-inbox.org/git/20180810221857.87399-1-sbeller@google.com/)\n> \n> and one of the weaknesses in that patch is the lack of explanation on\n> when the heuristic is applied as I have not fully understood it yet.\n\nI'm not sure I understand it either. But at least knowing that --minimal\nchanges the output gives a lead for investigation (I don't really have\ntime to dig into it in the next few days, though).\n\n-Peff\n"},{"id":"357006","messageId":"CAGZ79kYVLNM4fMwXAw9FbKFNJ1tTR7e04nBqKdnYPX3wYveUfg@mail.gmail.com","threadId":"49222","inReplyTo":"20180830192019.GB19685@sigill.intra.peff.net","subject":"Re: Possible bug: identical lines added/removed in git diff","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-08-30T19:28:24Z","receivedAt":"2018-08-30T19:28:38Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Thu, Aug 30, 2018 at 12:20 PM Jeff King wrote:\n>\n> On Thu, Aug 30, 2018 at 12:16:22PM -0700, Stefan Beller wrote:\n>\n> > On Wed, Aug 29, 2018 at 7:54 PM Jeff King wrote:\n> > >\n> > > On Wed, Aug 29, 2018 at 10:10:25PM -0400, Gabriel Holodak wrote:\n> > >\n> > > > > Could you cut down to a real minimal reproduction, i.e. just these 20\n> > > > > lines or so?\n> > > >\n> > > > I'm working on getting down to a minimal reproduction, a few lines at\n> > > > a time. One thing that seems strange: as I've removed lines, there are\n> > > > a bunch of lines that don't matter. Then I'll find some lines that, if\n> > > > removed, completely fix the issue. But the ordering for these\n> > > > apparently important lines doesn't matter. They just have to be\n> > > > somewhere in the file to cause the duplicated diffs.\n> > > >\n> > > > I'll upload again when I've figured out all the unimportant lines to remove.\n> > >\n> > > Yeah, I reproduced based on your initial post, but noticed that when I\n> > > cut it down the problem went away.\n> >\n> > Oh, I had to look further down than I did initially. Now I can reproduce it\n> > from the initial data as well.\n> >\n> > Note that it goes away with --minimal.\n>\n> That's interesting. I did wonder if this was in fact a bug, or simply\n> that Myers does not promise to find the absolute minimal diff. I'm\n> _still_ not sure, especially because the minimization is so obvious in\n> this case (literally the first \"-\" and the first \"+\" line of a\n> contiguous hunk are identical).\n\nThe `Myers` (our default) diff algorithm is really the Myers algorithm +\na heuristic that cuts off the long tail when it is very costly to compute\nthe minimal diff.\n\nThe `minimal` diff is the true Myers algorithm and I'd vouch for its\ncorrectness and being the minimal number of lines in the diff output.\n\nThe Myers is implemented before\nhttps://github.com/git/git/blob/master/xdiff/xdiffi.c#L135\nand the heuristics is after that line.\n\n> > I have a patch cooking (which was sent out as\n> > https://public-inbox.org/git/20180810221857.87399-1-sbeller@google.com/)\n> >\n> > and one of the weaknesses in that patch is the lack of explanation on\n> > when the heuristic is applied as I have not fully understood it yet.\n>\n> I'm not sure I understand it either. But at least knowing that --minimal\n> changes the output gives a lead for investigation (I don't really have\n> time to dig into it in the next few days, though).\n\nAn interesting (to me) approach for digging into that would include\nfinding these examples at scale, which I presented in\nhttps://public-inbox.org/git/20180810001010.58870-1-sbeller@google.com/\nbut I guess reading the code would work just as fine.\n\nThanks,\nStefan\n"},{"id":"357136","messageId":"nycvar.QRO.7.76.6.1808312336270.71@tvgsbejvaqbjf.bet","threadId":"49222","inReplyTo":"CAGZ79kYVLNM4fMwXAw9FbKFNJ1tTR7e04nBqKdnYPX3wYveUfg@mail.gmail.com","subject":"Re: Possible bug: identical lines added/removed in git diff","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2018-08-31T21:38:59Z","receivedAt":"2018-08-31T21:39:14Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 30 Aug 2018, Stefan Beller wrote:\n\n> On Thu, Aug 30, 2018 at 12:20 PM Jeff King wrote:\n> >\n> > [...] Myers does not promise to find the absolute minimal diff. [...]\n> \n> The `Myers` (our default) diff algorithm is really the Myers algorithm +\n> a heuristic that cuts off the long tail when it is very costly to compute\n> the minimal diff.\n\nIIRC Myers promises minimal diffs only for -U0. As soon as you add\ncontext, Myers might in fact end up with a suboptimal diff, even without\nthat heuristic.\n\nCiao,\nDscho\n"},{"id":"357160","messageId":"CAGZ79kbi0Y+1j836Lc-Kp6xd3ihabhODLLMj9rrZH_Mxs3PB8w@mail.gmail.com","threadId":"49222","inReplyTo":"nycvar.QRO.7.76.6.1808312336270.71@tvgsbejvaqbjf.bet","subject":"Re: Possible bug: identical lines added/removed in git diff","fromName":"Stefan Beller","fromEmail":"sbeller@google.com","sentAt":"2018-09-01T15:23:26Z","receivedAt":"2018-09-01T15:23:49Z","isPatch":false,"sender":{"key":"stefanbeller@gmail.com","avatar":"https://avatars.githubusercontent.com/u/455868?v=4"},"body":"On Fri, Aug 31, 2018 at 2:39 PM Johannes Schindelin\n wrote:\n>\n> Hi,\n>\n> On Thu, 30 Aug 2018, Stefan Beller wrote:\n>\n> > On Thu, Aug 30, 2018 at 12:20 PM Jeff King wrote:\n> > >\n> > > [...] Myers does not promise to find the absolute minimal diff. [...]\n> >\n> > The `Myers` (our default) diff algorithm is really the Myers algorithm +\n> > a heuristic that cuts off the long tail when it is very costly to compute\n> > the minimal diff.\n>\n> IIRC Myers\n\n(the original, which we spell `minimal`)\n\n> promises minimal diffs only for -U0. As soon as you add\n> context, Myers might in fact end up with a suboptimal diff, even without\n> that heuristic.\n\nah, the last 4 words made it clear.\n\nI have debated the cost function for diffs some time ago and\ncame to the conclusion that having one line added/removed costing\na flat price of 1 in the search of the 'lowest cost diff' is pretty good\nas it does an ok job in the broad world, it is not 'overfitting' assumptions\non a problem.\n\nFor example in some patches I pay more attention to the lines\nremoved than to the lines added, or vice versa, so assigning\ndifferent costs to added/removed lines would make sense.\n(It depend on the type of patch, but that cannot be deduced\nat the low level of diff machinery)\n\nStarting a new hunk (i.e. add cost to -U for n >0) could be\ncostly. In fact we have an after-Myers optimization in the xdiff\ncode that checks if hunks can be coalesced together, but\nif we could have that cost at diff computation time, this might\nmake for better diffs already.\n\nAnother example is number of changes between\nadded/removed/context parts. If I have to review only\none large added part and one large removed part, it may\nbe more understandable than having interleaved adds/removes.\n(I think --patience goes in that direction, but does optimize for\na different metric)\n\nStefan\n"}]}