Re: [RFH] xdiff shows trivially redundant diff.

On Sun, 2 Apr 2006, Junio C Hamano wrote:

I should have tried your pristine xdiff code myself before
bothering you, but I haven't (sorry).

The problem is from the "stripped down" version we use in git,
so you may or may not see the problem in your version.  Attached
are the files.

Yes, it does even vanilla libxdiff ;) It's not a problem though, since it 
is created in xdl_cleanup_records() that tries to do a fast pass over the 
records to try to simplify the real diff operation. In trying to be fast, 
only hashes are compared, and it happens that the hash for "'')" collides 
with another one (try to replace one of the "'')" chars with another one). 
Why is this not a problem? Because what this lead to is only lines to be 
marked as changed, with a probability of about N/2^(8 * sizeof(long) - 1), 
even though they are not. And this happens only during sequential groups 
of lines changed, that is when the hash-colliding line is either at the 
begin or the end of the run.



- Davide