Possible bug: identical lines added/removed in git diff

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

On Sun, Aug 26, 2018 at 6:54 PM Gabriel Holodak <gthepiper@gmail.com> wrote:

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/

Could you cut down to a real minimal reproduction, i.e. just these 20 lines or so?

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?)

Thanks, Stefan

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 <sbeller@google.com> wrote:

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.

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.

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.

No filters, I did have core.autocrlf = input. But as I mentioned, I can also reproduce with an empty config.

Yep, the lines in question are identical.

Thanks for looking into this. Gabriel

On Wed, Aug 29, 2018 at 10:10:25PM -0400, Gabriel Holodak wrote:

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.

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

On Wed, Aug 29, 2018 at 7:54 PM Jeff King <peff@peff.net> wrote:

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.

On Thu, Aug 30, 2018 at 12:16:22PM -0700, Stefan Beller wrote:

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'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

On Thu, Aug 30, 2018 at 12:20 PM Jeff King <peff@peff.net> wrote:

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.

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

Hi,

On Thu, 30 Aug 2018, Stefan Beller wrote:

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

On Fri, Aug 31, 2018 at 2:39 PM Johannes Schindelin <Johannes.Schindelin@gmx.de> wrote:

(the original, which we spell `minimal`)

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<n> 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