threads / patch / 8754

patchIgnore end-of-line style when computing similarity score for rename detection

Subject: [PATCH] Ignore end-of-line style when computing similarity score for rename detection

## tl;dr

11 messages between Jun 28, 2007 and Jun 29, 2007. Diffs are folded; open one to read it.

replies: 10people: 5as markdown or json

Steven Grimm· Jun 28, 2007, 02:39 UTC · lore
Signed-off-by: Steven Grimm <koreth@midwinter.com>
---
A couple of source files got checked into my code base with DOS-style 
end-of-line characters. I converted them to UNIX-style (the convention 
for this project) in my branch. Then later, I renamed a couple of them.

Meanwhile, back in the original branch, someone else fixed a bug in one of the files and checked it in, still with DOS-style line endings.

When I merged that change into my branch, git didn't detect the rename because the fact that every line has a change (the end-of-line character) dropped the similarity score way too low.

This patch teaches git to ignore end-of-line style when looking for potential rename candidates. A separate question, which I expect may be more controversial, is what to do with conflict markers; with this patch, the entire file is still marked as in conflict if the end-of-line style changes (but it's still an improvement in that we at least detect the rename now.)

 diffcore-delta.c |    9 ++++++---
 1 files changed, 6 insertions(+), 3 deletions(-)
Show changes to diffcore-delta.c +6 −3
diff --git a/diffcore-delta.c b/diffcore-delta.c
index 7338a40..10bbf95 100644
--- a/diffcore-delta.c
+++ b/diffcore-delta.c
@@ -143,9 +143,12 @@ static struct spanhash_top *hash_chars(unsigned 
char *buf, unsigned int sz)
                unsigned int c = *buf++;
                unsigned int old_1 = accum1;
                sz--;
-               accum1 = (accum1 << 7) ^ (accum2 >> 25);
-               accum2 = (accum2 << 7) ^ (old_1 >> 25);
-               accum1 += c;
+               /* Ignore \r\n vs. \n when computing similarity. */
+               if (c != '\r') {
+                       accum1 = (accum1 << 7) ^ (accum2 >> 25);
+                       accum2 = (accum2 << 7) ^ (old_1 >> 25);
+                       accum1 += c;
+               }
                if (++n < 64 && c != '\n')
                        continue;
                hashval = (accum1 + accum2 * 0x61) % HASHBASE;

-- 
1.5.2.2.571.ge134
Steven Grimm· Jun 28, 2007, 02:46 UTC · re: Steven Grimm · lore
Signed-off-by: Steven Grimm <koreth@midwinter.com>
---
Okay, let's try this again with an MUA that won't change my tabs to
spaces -- sorry about that.

A couple of source files got checked into my code base with DOS-style end-of-line characters. I converted them to UNIX-style (the convention for this project) in my branch. Then later, I renamed a couple of them.

Meanwhile, back in the original branch, someone else fixed a bug in one of the files and checked it in, still with DOS-style line endings.

When I merged that change into my branch, git didn't detect the rename because the fact that every line has a change (the end-of-line character) dropped the similarity score way too low.

This patch teaches git to ignore end-of-line style when looking for potential rename candidates. A separate question, which I expect may be more controversial, is what to do with conflict markers; with this patch, the entire file is still marked as in conflict if the end-of-line style changes (but it's still an improvement in that we at least detect the rename now.)

 diffcore-delta.c |    9 ++++++---
 1 files changed, 6 insertions(+), 3 deletions(-)
Show changes to diffcore-delta.c +6 −3
diff --git a/diffcore-delta.c b/diffcore-delta.c
index 7338a40..10bbf95 100644
--- a/diffcore-delta.c
+++ b/diffcore-delta.c
@@ -143,9 +143,12 @@ static struct spanhash_top *hash_chars(unsigned char *buf, unsigned int sz)
 		unsigned int c = *buf++;
 		unsigned int old_1 = accum1;
 		sz--;
-		accum1 = (accum1 << 7) ^ (accum2 >> 25);
-		accum2 = (accum2 << 7) ^ (old_1 >> 25);
-		accum1 += c;
+		/* Ignore \r\n vs. \n when computing similarity. */
+		if (c != '\r') {
+			accum1 = (accum1 << 7) ^ (accum2 >> 25);
+			accum2 = (accum2 << 7) ^ (old_1 >> 25);
+			accum1 += c;
+		}
 		if (++n < 64 && c != '\n')
 			continue;
 		hashval = (accum1 + accum2 * 0x61) % HASHBASE;

-- 
1.5.2.2.571.ge134
Johannes Sixt· Jun 28, 2007, 07:22 UTC · re: Steven Grimm · lore

Re: [PATCH] Ignore end-of-line style when computing similarity score for rename detection

Steven Grimm wrote:
Show 23 quoted lines
> 
> Signed-off-by: Steven Grimm <koreth@midwinter.com>
> ---
> Okay, let's try this again with an MUA that won't change my tabs to
> spaces -- sorry about that.
> 
> A couple of source files got checked into my code base with DOS-style
> end-of-line characters. I converted them to UNIX-style (the convention
> for this project) in my branch. Then later, I renamed a couple of them.
> 
> Meanwhile, back in the original branch, someone else fixed a bug in one
> of the files and checked it in, still with DOS-style line endings.
> 
> When I merged that change into my branch, git didn't detect the rename
> because the fact that every line has a change (the end-of-line
> character) dropped the similarity score way too low.
> 
> This patch teaches git to ignore end-of-line style when looking for
> potential rename candidates. A separate question, which I expect may be
> more controversial, is what to do with conflict markers; with this
> patch, the entire file is still marked as in conflict if the end-of-line
> style changes (but it's still an improvement in that we at least detect
> the rename now.)

I think that nobody would object to have a use-case description like this in the commit message...

-- Hannes
Junio C Hamano· Jun 28, 2007, 08:16 UTC · re: Johannes Sixt · lore

Re: [PATCH] Ignore end-of-line style when computing similarity score for rename detection

Johannes Sixt <J.Sixt@eudaptics.com> writes:
Show 27 quoted lines
> Steven Grimm wrote:
>> 
>> Signed-off-by: Steven Grimm <koreth@midwinter.com>
>> ---
>> Okay, let's try this again with an MUA that won't change my tabs to
>> spaces -- sorry about that.
>> 
>> A couple of source files got checked into my code base with DOS-style
>> end-of-line characters. I converted them to UNIX-style (the convention
>> for this project) in my branch. Then later, I renamed a couple of them.
>> 
>> Meanwhile, back in the original branch, someone else fixed a bug in one
>> of the files and checked it in, still with DOS-style line endings.
>> 
>> When I merged that change into my branch, git didn't detect the rename
>> because the fact that every line has a change (the end-of-line
>> character) dropped the similarity score way too low.
>> 
>> This patch teaches git to ignore end-of-line style when looking for
>> potential rename candidates. A separate question, which I expect may be
>> more controversial, is what to do with conflict markers; with this
>> patch, the entire file is still marked as in conflict if the end-of-line
>> style changes (but it's still an improvement in that we at least detect
>> the rename now.)
>
> I think that nobody would object to have a use-case description like
> this in the commit message...
Oh, yeah.  100% agreed.
Junio C Hamano· Jun 28, 2007, 04:29 UTC · re: Steven Grimm · lore

Re: [PATCH] Ignore end-of-line style when computing similarity score for rename detection

I wonder if we have a path or the attribute cue at this point of the operation. Your patch may solve that special case of CRLF mangled files, but diffcore-delta works both on text and binary and I am not sure what damange/side-effect you are causing.

And you are not ignoring "\r\n vs \n difference" as the comment claims, but are discarding '\r' unconditionally. When we start doing something like that, I would feel much better if we _know_ we are operating on a text file at least.

Steven Grimm· Jun 28, 2007, 06:04 UTC · re: Junio C Hamano · lore
Signed-off-by: Steven Grimm <koreth@midwinter.com>
---
Junio rightly points out that it would be a mistake to discard \r
characters from binary files when computing similarity scores. So now we
only do it if the file contents test as non-binary.

The file attributes aren't available at this level of the code, but they could be propagated down from the higher levels if we don't trust buffer_is_binary() to make an adequately accurate decision.

 diffcore-delta.c |   19 +++++++++++++------
 1 files changed, 13 insertions(+), 6 deletions(-)
Show changes to diffcore-delta.c +13 −6
diff --git a/diffcore-delta.c b/diffcore-delta.c
index 7338a40..52e648f 100644
--- a/diffcore-delta.c
+++ b/diffcore-delta.c
@@ -1,6 +1,7 @@
 #include "cache.h"
 #include "diff.h"
 #include "diffcore.h"
+#include "xdiff-interface.h"
 
 /*
  * Idea here is very simple.
@@ -125,7 +126,8 @@ static struct spanhash_top *add_spanhash(struct spanhash_top *top,
 	}
 }
 
-static struct spanhash_top *hash_chars(unsigned char *buf, unsigned int sz)
+static struct spanhash_top *hash_chars(unsigned char *buf, unsigned int sz,
+				       int is_binary)
 {
 	int i, n;
 	unsigned int accum1, accum2, hashval;
@@ -143,9 +145,12 @@ static struct spanhash_top *hash_chars(unsigned char *buf, unsigned int sz)
 		unsigned int c = *buf++;
 		unsigned int old_1 = accum1;
 		sz--;
-		accum1 = (accum1 << 7) ^ (accum2 >> 25);
-		accum2 = (accum2 << 7) ^ (old_1 >> 25);
-		accum1 += c;
+		/* Ignore \r\n vs. \n when computing text file similarity. */
+		if (c != '\r' && ! is_binary) {
+			accum1 = (accum1 << 7) ^ (accum2 >> 25);
+			accum2 = (accum2 << 7) ^ (old_1 >> 25);
+			accum1 += c;
+		}
 		if (++n < 64 && c != '\n')
 			continue;
 		hashval = (accum1 + accum2 * 0x61) % HASHBASE;
@@ -172,14 +177,16 @@ int diffcore_count_changes(void *src, unsigned long src_size,
 	if (src_count_p)
 		src_count = *src_count_p;
 	if (!src_count) {
-		src_count = hash_chars(src, src_size);
+		int src_is_binary = buffer_is_binary(src, src_size);
+		src_count = hash_chars(src, src_size, src_is_binary);
 		if (src_count_p)
 			*src_count_p = src_count;
 	}
 	if (dst_count_p)
 		dst_count = *dst_count_p;
 	if (!dst_count) {
-		dst_count = hash_chars(dst, dst_size);
+		int dst_is_binary = buffer_is_binary(dst, dst_size);
+		dst_count = hash_chars(dst, dst_size, dst_is_binary);
 		if (dst_count_p)
 			*dst_count_p = dst_count;
 	}

-- 
1.5.2.2.571.ge134
Shawn O. Pearce· Jun 28, 2007, 06:18 UTC · re: Steven Grimm · lore

Re: [PATCH] Ignore end-of-line style when computing similarity score for rename detection

Steven Grimm <koreth@midwinter.com> wrote:
Show 7 quoted lines
> Junio rightly points out that it would be a mistake to discard \r
> characters from binary files when computing similarity scores. So now we
> only do it if the file contents test as non-binary.
> 
> The file attributes aren't available at this level of the code, but they
> could be propagated down from the higher levels if we don't trust
> buffer_is_binary() to make an adequately accurate decision.

Ick. If we can get the attributes into diff_filespec this is pretty easy, as you can do a crlf->lf conversion on both files if both are considered to be text, but it doesn't look like it would be very easy to get the attributes into the diff_filespec.

Actually even better if you can also run the in/out filter things. I'm thinking of say an XML file that has had whitespace formatting changes, but whose XSD and processors ignore unnecessary whitespace. Be nice if the rename detection actually was able to canonicalize both files before detecting the rename, assuming both files had a canonicalizer input filter defined that does that...

Of course diff.c defines a nice diff_is_binary() at file scope that does at least a "can we diff this" decision. Might be good if that could be reused for the rename detection.

OK, that's far more than I actually know about diffcore. This is one for Junio, Linus, you, and those who are less tired than I feel right now... ;-)

Personally I'd rather see us doing the right thing (use attributes and fallback on guessing if no preference is stated either way) over doing something half-a**ed (only guessing).

-- 
Shawn.
Junio C Hamano· Jun 29, 2007, 06:34 UTC · re: Shawn O. Pearce · lore

Re: [PATCH] Ignore end-of-line style when computing similarity score for rename detection

"Shawn O. Pearce" <spearce@spearce.org> writes:
Show 6 quoted lines
> Actually even better if you can also run the in/out filter things.
> I'm thinking of say an XML file that has had whitespace formatting
> changes, but whose XSD and processors ignore unnecessary whitespace.
> Be nice if the rename detection actually was able to canonicalize
> both files before detecting the rename, assuming both files had a
> canonicalizer input filter defined that does that...

This certainly is tempting, but I suspect that should be left to later rounds. I suspect that it would introduce a concept of two different kinds of diffs, one to be mechanically processed (i.e. use in merge with "git-merge-recursive", and apply with "git-am"), and another to be inspected by humans to understand. It often may be useful to munge the input for the latter case, even though the output from comparing munged input files may not be readily usable for mechanical application.

Which is not a bad thing per-se, but needs to be done carefully.
A replacement set for Steven to comment on follows.
  [PATCH 1/4] diffcore_count_changes: pass diffcore_filespec
  [PATCH 2/4] diffcore_filespec: add is_binary
  [PATCH 3/4] diffcore-delta.c: update the comment on the algorithm.
  [PATCH 4/4] diffcore-delta.c: Ignore CR in CRLF for text files
Johannes Schindelin· Jun 28, 2007, 12:41 UTC · re: Steven Grimm · lore

Re: [PATCH] Ignore end-of-line style when computing similarity score for rename detection

Hi,
On Wed, 27 Jun 2007, Steven Grimm wrote:
> Junio rightly points out that it would be a mistake to discard \r
> characters from binary files when computing similarity scores.

Somehow I think that this should be triggered by "--ignore-space-at-eol", _and_ be accompanied by a test case.

Ciao, Dscho

Steven Grimm· Jun 28, 2007, 18:17 UTC · re: Johannes Schindelin · lore

Re: [PATCH] Ignore end-of-line style when computing similarity score for rename detection

Johannes Schindelin wrote:
> Somehow I think that this should be triggered by "--ignore-space-at-eol", 
> _and_ be accompanied by a test case.
>

Should --ignore-space-at-eol be an option to git-merge? Merges are where this functionality matters; for simple diffs, --ignore-space-at-eol actually already covers it. If we allow that option, should we also allow other git-diff options like --ignore-all-space and --ignore-space-change? What are the semantics of an autoresolved merge with those options in effect -- are they only used for rename detection, or do we, e.g., not flag conflicts with only whitespace changes? And if we don't, which version do we accept automatically?

-Steve
Johannes Schindelin· Jun 29, 2007, 10:19 UTC · re: Steven Grimm · lore

Re: [PATCH] Ignore end-of-line style when computing similarity score for rename detection

Hi,
On Thu, 28 Jun 2007, Steven Grimm wrote:
Show 8 quoted lines
> Johannes Schindelin wrote:
> > Somehow I think that this should be triggered by "--ignore-space-at-eol",
> > _and_ be accompanied by a test case.
> >   
> 
> Should --ignore-space-at-eol be an option to git-merge? Merges are where 
> this functionality matters; for simple diffs, --ignore-space-at-eol 
> actually already covers it.

Good point. However, I fail to see how the similarity detection should be so decoupled from the application. IOW what good is it if two files are rated similar if the merge cannot handle the CRLF/LF differences properly?

So two points here: since the merges are what you target, you definitely should mention that in the commit message. And you should make sure that all this trickery only kicks in when the merge has a chance to succeed.

Ciao, Dscho

← back to recent threads