# Possible bug: identical lines added/removed in git diff 9 messages from 2018-08-27 to 2018-09-01. Participants: Gabriel Holodak, Stefan Beller, Jeff King, Johannes Schindelin. Thread: https://gitlist.dev/t/49222 ## Gabriel Holodak, 2018-08-27 01:54 Subject: Possible bug: identical lines added/removed in git diff Message-ID: URL: https://gitlist.dev/e/CAE6%3DWB_4_PhjfQpubFcYkNKejfDr22s-y0nPQKw5Yd4GVaN4Yw%40mail.gmail.com ``` I think I'm running into a bug with git diff on v2.18.0. When I diff the attached files, part of the diff ends up looking like: ... STARTCHAR U+00F0 ENCODING 240 SWIDTH 500 0 -DWIDTH 8 0 -BBX 7 12 1 0 -BITMAP -12 -0C -14 -22 -02 -3E -42 -42 -82 -84 -84 -78 +DWIDTH 8 0 +BBX 8 12 0 0 +BITMAP +1B +0E +1E +33 +03 +3F +63 +63 +C3 +C6 +C6 +7C ENDCHAR STARTCHAR U+00F1 ... where the "DWIDTH 8 0" and "BITMAP" lines are removed and added, despite being identical. It only seems to be happening around this section of the file, for the U+00F0 character. This also seems close to a minimal reproduction of the issue. If I git add --patch and stage a few hunks, then the duplicated lines seem to disappear. Steps to reproduce: git diff --no-index unitera_bold_italic.bdf.old unitera_bold_italic.bdf.new (It also happens inside a repo, this just seemed the easiest way to demonstrate.) Gabriel Holodak ``` ## Stefan Beller, 2018-08-27 17:47 Subject: Re: Possible bug: identical lines added/removed in git diff Message-ID: URL: https://gitlist.dev/e/CAGZ79kZ1BVTLnNYSs%2BNjEO1T1-PySSdZzVU-0ZfivjT_pfvviQ%40mail.gmail.com In-Reply-To: ``` On Sun, Aug 26, 2018 at 6:54 PM Gabriel Holodak wrote: > > I think I'm running into a bug with git diff on v2.18.0. I cannot reproduce with the two files attached. I suspected you might have a different diff algorithm configured, so I tested git diff --no-index old new git diff --patience --no-index old new git diff --histogram --no-index old new all of which do not reproduce the issue. Are there any encoding issues locally (Which platform are you on?) or in transit (Could you re-download the files from [1] and confirm it still produces this bug?) [1] https://public-inbox.org/git/CAE6=WB_4_PhjfQpubFcYkNKejfDr22s-y0nPQKw5Yd4GVaN4Yw@mail.gmail.com/ > where the "DWIDTH 8 0" and "BITMAP" lines are removed and added, > despite being identical. It only seems to be happening around this > section of the file, for the U+00F0 character. This also seems close > to a minimal reproduction of the issue. Could you cut down to a real minimal reproduction, i.e. just these 20 lines or so? > If I git add --patch and stage > a few hunks, then the duplicated lines seem to disappear. Do you have any smudge filters or configuration regarding line endings? Are the lines really different or the same ? (Can you inspect with a hex editor, maybe there are different kinds of invisible white spaces?) > Steps to reproduce: > git diff --no-index unitera_bold_italic.bdf.old unitera_bold_italic.bdf.new > (It also happens inside a repo, this just seemed the easiest way to > demonstrate.) Thanks, Stefan ``` ## Gabriel Holodak, 2018-08-30 02:10 Subject: Re: Possible bug: identical lines added/removed in git diff Message-ID: URL: https://gitlist.dev/e/CAE6%3DWB_t7zG3jtELiMfggqxjvD4jJyJ02pNPmV3fey%3D3nSejuA%40mail.gmail.com In-Reply-To: ``` I did have some possibly interfering settings in my .gitconfig previously. I removed everything, so all the commands I'll describe were run with an empty config. On Mon, Aug 27, 2018 at 1:47 PM Stefan Beller wrote: > I suspected you might have a different diff algorithm configured, > so I tested > git diff --no-index old new > git diff --patience --no-index old new > git diff --histogram --no-index old new > > all of which do not reproduce the issue. I don't believe I had any settings to change the algorithm. Using any of --minimal, --patience, or --histogram seems to fix the issue. It still occurs with --diff-algorithm=default. I also tried --no-indent-heuristic, which had no effect. > Are there any encoding issues locally (Which platform > are you on?) or in transit (Could you re-download the files > from [1] and confirm it still produces this bug?) > > [1] https://public-inbox.org/git/CAE6=WB_4_PhjfQpubFcYkNKejfDr22s-y0nPQKw5Yd4GVaN4Yw@mail.gmail.com/ I should have mentioned before, this is on Arch Linux. I can reproduce from the downloaded files. I can also reproduce on macOS 10.13.6, with git 2.18.0. > Could you cut down to a real minimal reproduction, i.e. just these 20 > lines or so? I'm working on getting down to a minimal reproduction, a few lines at a time. One thing that seems strange: as I've removed lines, there are a bunch of lines that don't matter. Then I'll find some lines that, if removed, completely fix the issue. But the ordering for these apparently important lines doesn't matter. They just have to be somewhere in the file to cause the duplicated diffs. I'll upload again when I've figured out all the unimportant lines to remove. > Do you have any smudge filters or configuration regarding > line endings? No filters, I did have core.autocrlf = input. But as I mentioned, I can also reproduce with an empty config. > Are the lines really different or the same ? (Can you inspect with a > hex editor, maybe there are different kinds of invisible white spaces?) Yep, the lines in question are identical. Thanks for looking into this. Gabriel ``` ## Jeff King, 2018-08-30 02:54 Subject: Re: Possible bug: identical lines added/removed in git diff Message-ID: <20180830025457.GA665@sigill.intra.peff.net> URL: https://gitlist.dev/e/20180830025457.GA665%40sigill.intra.peff.net In-Reply-To: ``` On Wed, Aug 29, 2018 at 10:10:25PM -0400, Gabriel Holodak wrote: > > Could you cut down to a real minimal reproduction, i.e. just these 20 > > lines or so? > > I'm working on getting down to a minimal reproduction, a few lines at > a time. One thing that seems strange: as I've removed lines, there are > a bunch of lines that don't matter. Then I'll find some lines that, if > removed, completely fix the issue. But the ordering for these > apparently important lines doesn't matter. They just have to be > somewhere in the file to cause the duplicated diffs. > > I'll upload again when I've figured out all the unimportant lines to remove. Yeah, I reproduced based on your initial post, but noticed that when I cut it down the problem went away. An easy and pretty mechanical reproduction is: git diff --no-index unitera_bold_italic.bdf.{old,new} | sed -ne '/STARTCHAR U+00F0/,/ENDCHAR/p' which shows a hunk that could easily be reduced by its first line ("DWIDTH 8 0"), and which has a common line in the middle of -/+ run. But if we cut it down to the lines in that hunk, like this: for i in unitera_bold_italic.bdf.{old,new}; do sed -ne '/STARTCHAR U+00F0/,/ENDCHAR/p' <$i >$i.cut done git diff --no-index unitera_bold_italic.bdf.{old,new}.cut then those two lines become context. I note also that GNU "diff -u" gets this case right. > > Do you have any smudge filters or configuration regarding > > line endings? > > No filters, I did have core.autocrlf = input. But as I mentioned, I > can also reproduce with an empty config. Me too. Amusingly, if you have diff.colorMoved configured, the context lines appear as moves, showing that we really do know they're the same (but that happens as post-diff processing, so I am not at all surprised that it is orthogonal to the original issue). -Peff ``` ## Stefan Beller, 2018-08-30 19:16 Subject: Re: Possible bug: identical lines added/removed in git diff Message-ID: URL: https://gitlist.dev/e/CAGZ79kZNVw4-q9KYAi9G3axb7-Ggpc2EAK8ZxAZoPEnZvEL-DQ%40mail.gmail.com In-Reply-To: <20180830025457.GA665@sigill.intra.peff.net> ``` On Wed, Aug 29, 2018 at 7:54 PM Jeff King wrote: > > On Wed, Aug 29, 2018 at 10:10:25PM -0400, Gabriel Holodak wrote: > > > > Could you cut down to a real minimal reproduction, i.e. just these 20 > > > lines or so? > > > > I'm working on getting down to a minimal reproduction, a few lines at > > a time. One thing that seems strange: as I've removed lines, there are > > a bunch of lines that don't matter. Then I'll find some lines that, if > > removed, completely fix the issue. But the ordering for these > > apparently important lines doesn't matter. They just have to be > > somewhere in the file to cause the duplicated diffs. > > > > I'll upload again when I've figured out all the unimportant lines to remove. > > Yeah, I reproduced based on your initial post, but noticed that when I > cut it down the problem went away. Oh, I had to look further down than I did initially. Now I can reproduce it from the initial data as well. Note that it goes away with --minimal. I have a patch cooking (which was sent out as https://public-inbox.org/git/20180810221857.87399-1-sbeller@google.com/) and one of the weaknesses in that patch is the lack of explanation on when the heuristic is applied as I have not fully understood it yet. ``` ## Jeff King, 2018-08-30 19:20 Subject: Re: Possible bug: identical lines added/removed in git diff Message-ID: <20180830192019.GB19685@sigill.intra.peff.net> URL: https://gitlist.dev/e/20180830192019.GB19685%40sigill.intra.peff.net In-Reply-To: ``` On Thu, Aug 30, 2018 at 12:16:22PM -0700, Stefan Beller wrote: > On Wed, Aug 29, 2018 at 7:54 PM Jeff King wrote: > > > > On Wed, Aug 29, 2018 at 10:10:25PM -0400, Gabriel Holodak wrote: > > > > > > Could you cut down to a real minimal reproduction, i.e. just these 20 > > > > lines or so? > > > > > > I'm working on getting down to a minimal reproduction, a few lines at > > > a time. One thing that seems strange: as I've removed lines, there are > > > a bunch of lines that don't matter. Then I'll find some lines that, if > > > removed, completely fix the issue. But the ordering for these > > > apparently important lines doesn't matter. They just have to be > > > somewhere in the file to cause the duplicated diffs. > > > > > > I'll upload again when I've figured out all the unimportant lines to remove. > > > > Yeah, I reproduced based on your initial post, but noticed that when I > > cut it down the problem went away. > > Oh, I had to look further down than I did initially. Now I can reproduce it > from the initial data as well. > > Note that it goes away with --minimal. That's interesting. I did wonder if this was in fact a bug, or simply that Myers does not promise to find the absolute minimal diff. I'm _still_ not sure, especially because the minimization is so obvious in this case (literally the first "-" and the first "+" line of a contiguous hunk are identical). > I have a patch cooking (which was sent out as > https://public-inbox.org/git/20180810221857.87399-1-sbeller@google.com/) > > and one of the weaknesses in that patch is the lack of explanation on > when the heuristic is applied as I have not fully understood it yet. I'm not sure I understand it either. But at least knowing that --minimal changes the output gives a lead for investigation (I don't really have time to dig into it in the next few days, though). -Peff ``` ## Stefan Beller, 2018-08-30 19:28 Subject: Re: Possible bug: identical lines added/removed in git diff Message-ID: URL: https://gitlist.dev/e/CAGZ79kYVLNM4fMwXAw9FbKFNJ1tTR7e04nBqKdnYPX3wYveUfg%40mail.gmail.com In-Reply-To: <20180830192019.GB19685@sigill.intra.peff.net> ``` On Thu, Aug 30, 2018 at 12:20 PM Jeff King wrote: > > On Thu, Aug 30, 2018 at 12:16:22PM -0700, Stefan Beller wrote: > > > On Wed, Aug 29, 2018 at 7:54 PM Jeff King wrote: > > > > > > On Wed, Aug 29, 2018 at 10:10:25PM -0400, Gabriel Holodak wrote: > > > > > > > > Could you cut down to a real minimal reproduction, i.e. just these 20 > > > > > lines or so? > > > > > > > > I'm working on getting down to a minimal reproduction, a few lines at > > > > a time. One thing that seems strange: as I've removed lines, there are > > > > a bunch of lines that don't matter. Then I'll find some lines that, if > > > > removed, completely fix the issue. But the ordering for these > > > > apparently important lines doesn't matter. They just have to be > > > > somewhere in the file to cause the duplicated diffs. > > > > > > > > I'll upload again when I've figured out all the unimportant lines to remove. > > > > > > Yeah, I reproduced based on your initial post, but noticed that when I > > > cut it down the problem went away. > > > > Oh, I had to look further down than I did initially. Now I can reproduce it > > from the initial data as well. > > > > Note that it goes away with --minimal. > > That's interesting. I did wonder if this was in fact a bug, or simply > that Myers does not promise to find the absolute minimal diff. I'm > _still_ not sure, especially because the minimization is so obvious in > this case (literally the first "-" and the first "+" line of a > contiguous hunk are identical). The `Myers` (our default) diff algorithm is really the Myers algorithm + a heuristic that cuts off the long tail when it is very costly to compute the minimal diff. The `minimal` diff is the true Myers algorithm and I'd vouch for its correctness and being the minimal number of lines in the diff output. The Myers is implemented before https://github.com/git/git/blob/master/xdiff/xdiffi.c#L135 and the heuristics is after that line. > > I have a patch cooking (which was sent out as > > https://public-inbox.org/git/20180810221857.87399-1-sbeller@google.com/) > > > > and one of the weaknesses in that patch is the lack of explanation on > > when the heuristic is applied as I have not fully understood it yet. > > I'm not sure I understand it either. But at least knowing that --minimal > changes the output gives a lead for investigation (I don't really have > time to dig into it in the next few days, though). An interesting (to me) approach for digging into that would include finding these examples at scale, which I presented in https://public-inbox.org/git/20180810001010.58870-1-sbeller@google.com/ but I guess reading the code would work just as fine. Thanks, Stefan ``` ## Johannes Schindelin, 2018-08-31 21:38 Subject: Re: Possible bug: identical lines added/removed in git diff Message-ID: URL: https://gitlist.dev/e/nycvar.QRO.7.76.6.1808312336270.71%40tvgsbejvaqbjf.bet In-Reply-To: ``` Hi, On Thu, 30 Aug 2018, Stefan Beller wrote: > On Thu, Aug 30, 2018 at 12:20 PM Jeff King wrote: > > > > [...] Myers does not promise to find the absolute minimal diff. [...] > > The `Myers` (our default) diff algorithm is really the Myers algorithm + > a heuristic that cuts off the long tail when it is very costly to compute > the minimal diff. IIRC Myers promises minimal diffs only for -U0. As soon as you add context, Myers might in fact end up with a suboptimal diff, even without that heuristic. Ciao, Dscho ``` ## Stefan Beller, 2018-09-01 15:23 Subject: Re: Possible bug: identical lines added/removed in git diff Message-ID: URL: https://gitlist.dev/e/CAGZ79kbi0Y%2B1j836Lc-Kp6xd3ihabhODLLMj9rrZH_Mxs3PB8w%40mail.gmail.com In-Reply-To: ``` On Fri, Aug 31, 2018 at 2:39 PM Johannes Schindelin wrote: > > Hi, > > On Thu, 30 Aug 2018, Stefan Beller wrote: > > > On Thu, Aug 30, 2018 at 12:20 PM Jeff King wrote: > > > > > > [...] Myers does not promise to find the absolute minimal diff. [...] > > > > The `Myers` (our default) diff algorithm is really the Myers algorithm + > > a heuristic that cuts off the long tail when it is very costly to compute > > the minimal diff. > > IIRC Myers (the original, which we spell `minimal`) > promises minimal diffs only for -U0. As soon as you add > context, Myers might in fact end up with a suboptimal diff, even without > that heuristic. ah, the last 4 words made it clear. I have debated the cost function for diffs some time ago and came to the conclusion that having one line added/removed costing a flat price of 1 in the search of the 'lowest cost diff' is pretty good as it does an ok job in the broad world, it is not 'overfitting' assumptions on a problem. For example in some patches I pay more attention to the lines removed than to the lines added, or vice versa, so assigning different costs to added/removed lines would make sense. (It depend on the type of patch, but that cannot be deduced at the low level of diff machinery) Starting a new hunk (i.e. add cost to -U for n >0) could be costly. In fact we have an after-Myers optimization in the xdiff code that checks if hunks can be coalesced together, but if we could have that cost at diff computation time, this might make for better diffs already. Another example is number of changes between added/removed/context parts. If I have to review only one large added part and one large removed part, it may be more understandable than having interleaved adds/removes. (I think --patience goes in that direction, but does optimize for a different metric) Stefan ```