{"thread":{"id":"8754","subject":"[PATCH] Ignore end-of-line style when computing similarity score for rename detection","startedAt":"2007-06-28T02:39:44Z","lastAt":"2007-06-29T10:19:04Z","messageCount":11,"participants":["Steven Grimm","Junio C Hamano","Shawn O. Pearce","Johannes Sixt","Johannes Schindelin"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"45946","messageId":"46831F70.2060403@midwinter.com","threadId":"8754","inReplyTo":null,"subject":"[PATCH] Ignore end-of-line style when computing similarity score for rename detection","fromName":"Steven Grimm","fromEmail":"koreth@midwinter.com","sentAt":"2007-06-28T02:39:44Z","receivedAt":"2007-06-28T02:39:44Z","isPatch":true,"sender":{"key":"koreth@midwinter.com","avatar":"https://gravatar.com/avatar/71b4d2e8b62f168bdc9e9205341159e3567003b4f9e2127c617c5fa0a1f5bad2?d=mp&s=160"},"body":"Signed-off-by: Steven Grimm \n---\nA couple of source files got checked into my code base with DOS-style \nend-of-line characters. I converted them to UNIX-style (the convention \nfor this project) in my branch. Then later, I renamed a couple of them.\n\nMeanwhile, back in the original branch, someone else fixed a bug in one \nof the files and checked it in, still with DOS-style line endings.\n\nWhen I merged that change into my branch, git didn't detect the rename \nbecause the fact that every line has a change (the end-of-line \ncharacter) dropped the similarity score way too low.\n\nThis patch teaches git to ignore end-of-line style when looking for \npotential rename candidates. A separate question, which I expect may be \nmore controversial, is what to do with conflict markers; with this \npatch, the entire file is still marked as in conflict if the end-of-line \nstyle changes (but it's still an improvement in that we at least detect \nthe rename now.)\n\n\n diffcore-delta.c | 9 ++++++---\n 1 files changed, 6 insertions(+), 3 deletions(-)\n\ndiff --git a/diffcore-delta.c b/diffcore-delta.c\nindex 7338a40..10bbf95 100644\n--- a/diffcore-delta.c\n+++ b/diffcore-delta.c\n@@ -143,9 +143,12 @@ static struct spanhash_top *hash_chars(unsigned \nchar *buf, unsigned int sz)\n unsigned int c = *buf++;\n unsigned int old_1 = accum1;\n sz--;\n- accum1 = (accum1 << 7) ^ (accum2 >> 25);\n- accum2 = (accum2 << 7) ^ (old_1 >> 25);\n- accum1 += c;\n+ /* Ignore \\r\\n vs. \\n when computing similarity. */\n+ if (c != '\\r') {\n+ accum1 = (accum1 << 7) ^ (accum2 >> 25);\n+ accum2 = (accum2 << 7) ^ (old_1 >> 25);\n+ accum1 += c;\n+ }\n if (++n < 64 && c != '\\n')\n continue;\n hashval = (accum1 + accum2 * 0x61) % HASHBASE;\n-- \n1.5.2.2.571.ge134\n"},{"id":"45947","messageId":"20070628024603.GA1534@midwinter.com","threadId":"8754","inReplyTo":"46831F70.2060403@midwinter.com","subject":"[PATCH] Ignore end-of-line style when computing similarity score for rename detection","fromName":"Steven Grimm","fromEmail":"koreth@midwinter.com","sentAt":"2007-06-28T02:46:03Z","receivedAt":"2007-06-28T02:46:03Z","isPatch":true,"sender":{"key":"koreth@midwinter.com","avatar":"https://gravatar.com/avatar/71b4d2e8b62f168bdc9e9205341159e3567003b4f9e2127c617c5fa0a1f5bad2?d=mp&s=160"},"body":"Signed-off-by: Steven Grimm \n---\nOkay, let's try this again with an MUA that won't change my tabs to\nspaces -- sorry about that.\n\nA couple of source files got checked into my code base with DOS-style\nend-of-line characters. I converted them to UNIX-style (the convention\nfor this project) in my branch. Then later, I renamed a couple of them.\n\nMeanwhile, back in the original branch, someone else fixed a bug in one\nof the files and checked it in, still with DOS-style line endings.\n\nWhen I merged that change into my branch, git didn't detect the rename\nbecause the fact that every line has a change (the end-of-line\ncharacter) dropped the similarity score way too low.\n\nThis patch teaches git to ignore end-of-line style when looking for\npotential rename candidates. A separate question, which I expect may be\nmore controversial, is what to do with conflict markers; with this\npatch, the entire file is still marked as in conflict if the end-of-line\nstyle changes (but it's still an improvement in that we at least detect\nthe rename now.)\n\n\n diffcore-delta.c | 9 ++++++---\n 1 files changed, 6 insertions(+), 3 deletions(-)\n\ndiff --git a/diffcore-delta.c b/diffcore-delta.c\nindex 7338a40..10bbf95 100644\n--- a/diffcore-delta.c\n+++ b/diffcore-delta.c\n@@ -143,9 +143,12 @@ static struct spanhash_top *hash_chars(unsigned char *buf, unsigned int sz)\n \t\tunsigned int c = *buf++;\n \t\tunsigned int old_1 = accum1;\n \t\tsz--;\n-\t\taccum1 = (accum1 << 7) ^ (accum2 >> 25);\n-\t\taccum2 = (accum2 << 7) ^ (old_1 >> 25);\n-\t\taccum1 += c;\n+\t\t/* Ignore \\r\\n vs. \\n when computing similarity. */\n+\t\tif (c != '\\r') {\n+\t\t\taccum1 = (accum1 << 7) ^ (accum2 >> 25);\n+\t\t\taccum2 = (accum2 << 7) ^ (old_1 >> 25);\n+\t\t\taccum1 += c;\n+\t\t}\n \t\tif (++n < 64 && c != '\\n')\n \t\t\tcontinue;\n \t\thashval = (accum1 + accum2 * 0x61) % HASHBASE;\n-- \n1.5.2.2.571.ge134\n"},{"id":"45951","messageId":"7vtzssog5i.fsf@assigned-by-dhcp.pobox.com","threadId":"8754","inReplyTo":"46831F70.2060403@midwinter.com","subject":"Re: [PATCH] Ignore end-of-line style when computing similarity score for rename detection","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-06-28T04:29:45Z","receivedAt":"2007-06-28T04:29:45Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"I wonder if we have a path or the attribute cue at this point of\nthe operation. Your patch may solve that special case of CRLF\nmangled files, but diffcore-delta works both on text and binary\nand I am not sure what damange/side-effect you are causing.\n\nAnd you are not ignoring \"\\r\\n vs \\n difference\" as the comment\nclaims, but are discarding '\\r' unconditionally. When we start\ndoing something like that, I would feel much better if we _know_\nwe are operating on a text file at least.\n"},{"id":"45955","messageId":"20070628060416.GA13162@midwinter.com","threadId":"8754","inReplyTo":"7vtzssog5i.fsf@assigned-by-dhcp.pobox.com","subject":"[PATCH] Ignore end-of-line style when computing similarity score for rename detection","fromName":"Steven Grimm","fromEmail":"koreth@midwinter.com","sentAt":"2007-06-28T06:04:16Z","receivedAt":"2007-06-28T06:04:16Z","isPatch":true,"sender":{"key":"koreth@midwinter.com","avatar":"https://gravatar.com/avatar/71b4d2e8b62f168bdc9e9205341159e3567003b4f9e2127c617c5fa0a1f5bad2?d=mp&s=160"},"body":"Signed-off-by: Steven Grimm \n---\nJunio rightly points out that it would be a mistake to discard \\r\ncharacters from binary files when computing similarity scores. So now we\nonly do it if the file contents test as non-binary.\n\nThe file attributes aren't available at this level of the code, but they\ncould be propagated down from the higher levels if we don't trust\nbuffer_is_binary() to make an adequately accurate decision.\n\n\n diffcore-delta.c | 19 +++++++++++++------\n 1 files changed, 13 insertions(+), 6 deletions(-)\n\ndiff --git a/diffcore-delta.c b/diffcore-delta.c\nindex 7338a40..52e648f 100644\n--- a/diffcore-delta.c\n+++ b/diffcore-delta.c\n@@ -1,6 +1,7 @@\n #include \"cache.h\"\n #include \"diff.h\"\n #include \"diffcore.h\"\n+#include \"xdiff-interface.h\"\n \n /*\n * Idea here is very simple.\n@@ -125,7 +126,8 @@ static struct spanhash_top *add_spanhash(struct spanhash_top *top,\n \t}\n }\n \n-static struct spanhash_top *hash_chars(unsigned char *buf, unsigned int sz)\n+static struct spanhash_top *hash_chars(unsigned char *buf, unsigned int sz,\n+\t\t\t\t int is_binary)\n {\n \tint i, n;\n \tunsigned int accum1, accum2, hashval;\n@@ -143,9 +145,12 @@ static struct spanhash_top *hash_chars(unsigned char *buf, unsigned int sz)\n \t\tunsigned int c = *buf++;\n \t\tunsigned int old_1 = accum1;\n \t\tsz--;\n-\t\taccum1 = (accum1 << 7) ^ (accum2 >> 25);\n-\t\taccum2 = (accum2 << 7) ^ (old_1 >> 25);\n-\t\taccum1 += c;\n+\t\t/* Ignore \\r\\n vs. \\n when computing text file similarity. */\n+\t\tif (c != '\\r' && ! is_binary) {\n+\t\t\taccum1 = (accum1 << 7) ^ (accum2 >> 25);\n+\t\t\taccum2 = (accum2 << 7) ^ (old_1 >> 25);\n+\t\t\taccum1 += c;\n+\t\t}\n \t\tif (++n < 64 && c != '\\n')\n \t\t\tcontinue;\n \t\thashval = (accum1 + accum2 * 0x61) % HASHBASE;\n@@ -172,14 +177,16 @@ int diffcore_count_changes(void *src, unsigned long src_size,\n \tif (src_count_p)\n \t\tsrc_count = *src_count_p;\n \tif (!src_count) {\n-\t\tsrc_count = hash_chars(src, src_size);\n+\t\tint src_is_binary = buffer_is_binary(src, src_size);\n+\t\tsrc_count = hash_chars(src, src_size, src_is_binary);\n \t\tif (src_count_p)\n \t\t\t*src_count_p = src_count;\n \t}\n \tif (dst_count_p)\n \t\tdst_count = *dst_count_p;\n \tif (!dst_count) {\n-\t\tdst_count = hash_chars(dst, dst_size);\n+\t\tint dst_is_binary = buffer_is_binary(dst, dst_size);\n+\t\tdst_count = hash_chars(dst, dst_size, dst_is_binary);\n \t\tif (dst_count_p)\n \t\t\t*dst_count_p = dst_count;\n \t}\n-- \n1.5.2.2.571.ge134\n"},{"id":"45956","messageId":"20070628061821.GM32223@spearce.org","threadId":"8754","inReplyTo":"20070628060416.GA13162@midwinter.com","subject":"Re: [PATCH] Ignore end-of-line style when computing similarity score for rename detection","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2007-06-28T06:18:21Z","receivedAt":"2007-06-28T06:18:21Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Steven Grimm wrote:\n> Junio rightly points out that it would be a mistake to discard \\r\n> characters from binary files when computing similarity scores. So now we\n> only do it if the file contents test as non-binary.\n> \n> The file attributes aren't available at this level of the code, but they\n> could be propagated down from the higher levels if we don't trust\n> buffer_is_binary() to make an adequately accurate decision.\n\nIck. If we can get the attributes into diff_filespec this is\npretty easy, as you can do a crlf->lf conversion on both files if\nboth are considered to be text, but it doesn't look like it would\nbe very easy to get the attributes into the diff_filespec.\n\nActually even better if you can also run the in/out filter things.\nI'm thinking of say an XML file that has had whitespace formatting\nchanges, but whose XSD and processors ignore unnecessary whitespace.\nBe nice if the rename detection actually was able to canonicalize\nboth files before detecting the rename, assuming both files had a\ncanonicalizer input filter defined that does that...\n\nOf course diff.c defines a nice diff_is_binary() at file scope that\ndoes at least a \"can we diff this\" decision. Might be good if that\ncould be reused for the rename detection.\n\nOK, that's far more than I actually know about diffcore. This is\none for Junio, Linus, you, and those who are less tired than I feel\nright now... ;-)\n\nPersonally I'd rather see us doing the right thing (use attributes\nand fallback on guessing if no preference is stated either way)\nover doing something half-a**ed (only guessing).\n\n-- \nShawn.\n"},{"id":"45959","messageId":"4683619A.F753C97E@eudaptics.com","threadId":"8754","inReplyTo":"20070628024603.GA1534@midwinter.com","subject":"Re: [PATCH] Ignore end-of-line style when computing similarity score for rename detection","fromName":"Johannes Sixt","fromEmail":"j.sixt@eudaptics.com","sentAt":"2007-06-28T07:22:02Z","receivedAt":"2007-06-28T07:22:02Z","isPatch":true,"sender":{"key":"j6t@kdbg.org","avatar":"https://avatars.githubusercontent.com/u/14810926?v=4"},"body":"Steven Grimm wrote:\n> \n> Signed-off-by: Steven Grimm \n> ---\n> Okay, let's try this again with an MUA that won't change my tabs to\n> spaces -- sorry about that.\n> \n> A couple of source files got checked into my code base with DOS-style\n> end-of-line characters. I converted them to UNIX-style (the convention\n> for this project) in my branch. Then later, I renamed a couple of them.\n> \n> Meanwhile, back in the original branch, someone else fixed a bug in one\n> of the files and checked it in, still with DOS-style line endings.\n> \n> When I merged that change into my branch, git didn't detect the rename\n> because the fact that every line has a change (the end-of-line\n> character) dropped the similarity score way too low.\n> \n> This patch teaches git to ignore end-of-line style when looking for\n> potential rename candidates. A separate question, which I expect may be\n> more controversial, is what to do with conflict markers; with this\n> patch, the entire file is still marked as in conflict if the end-of-line\n> style changes (but it's still an improvement in that we at least detect\n> the rename now.)\n\nI think that nobody would object to have a use-case description like\nthis in the commit message...\n\n-- Hannes\n"},{"id":"45960","messageId":"7vejjwo5ne.fsf@assigned-by-dhcp.pobox.com","threadId":"8754","inReplyTo":"4683619A.F753C97E@eudaptics.com","subject":"Re: [PATCH] Ignore end-of-line style when computing similarity score for rename detection","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-06-28T08:16:37Z","receivedAt":"2007-06-28T08:16:37Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johannes Sixt writes:\n\n> Steven Grimm wrote:\n>> \n>> Signed-off-by: Steven Grimm \n>> ---\n>> Okay, let's try this again with an MUA that won't change my tabs to\n>> spaces -- sorry about that.\n>> \n>> A couple of source files got checked into my code base with DOS-style\n>> end-of-line characters. I converted them to UNIX-style (the convention\n>> for this project) in my branch. Then later, I renamed a couple of them.\n>> \n>> Meanwhile, back in the original branch, someone else fixed a bug in one\n>> of the files and checked it in, still with DOS-style line endings.\n>> \n>> When I merged that change into my branch, git didn't detect the rename\n>> because the fact that every line has a change (the end-of-line\n>> character) dropped the similarity score way too low.\n>> \n>> This patch teaches git to ignore end-of-line style when looking for\n>> potential rename candidates. A separate question, which I expect may be\n>> more controversial, is what to do with conflict markers; with this\n>> patch, the entire file is still marked as in conflict if the end-of-line\n>> style changes (but it's still an improvement in that we at least detect\n>> the rename now.)\n>\n> I think that nobody would object to have a use-case description like\n> this in the commit message...\n\nOh, yeah. 100% agreed.\n"},{"id":"45973","messageId":"Pine.LNX.4.64.0706281340090.4438@racer.site","threadId":"8754","inReplyTo":"20070628060416.GA13162@midwinter.com","subject":"Re: [PATCH] Ignore end-of-line style when computing similarity score for rename detection","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-06-28T12:41:01Z","receivedAt":"2007-06-28T12:41:01Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Wed, 27 Jun 2007, Steven Grimm wrote:\n\n> Junio rightly points out that it would be a mistake to discard \\r\n> characters from binary files when computing similarity scores.\n\nSomehow I think that this should be triggered by \"--ignore-space-at-eol\", \n_and_ be accompanied by a test case.\n\nCiao,\nDscho\n"},{"id":"45994","messageId":"4683FB25.3080204@midwinter.com","threadId":"8754","inReplyTo":"Pine.LNX.4.64.0706281340090.4438@racer.site","subject":"Re: [PATCH] Ignore end-of-line style when computing similarity score for rename detection","fromName":"Steven Grimm","fromEmail":"koreth@midwinter.com","sentAt":"2007-06-28T18:17:09Z","receivedAt":"2007-06-28T18:17:09Z","isPatch":true,"sender":{"key":"koreth@midwinter.com","avatar":"https://gravatar.com/avatar/71b4d2e8b62f168bdc9e9205341159e3567003b4f9e2127c617c5fa0a1f5bad2?d=mp&s=160"},"body":"Johannes Schindelin wrote:\n> Somehow I think that this should be triggered by \"--ignore-space-at-eol\", \n> _and_ be accompanied by a test case.\n> \n\nShould --ignore-space-at-eol be an option to git-merge? Merges are where \nthis functionality matters; for simple diffs, --ignore-space-at-eol \nactually already covers it. If we allow that option, should we also \nallow other git-diff options like --ignore-all-space and \n--ignore-space-change? What are the semantics of an autoresolved merge \nwith those options in effect -- are they only used for rename detection, \nor do we, e.g., not flag conflicts with only whitespace changes? And if \nwe don't, which version do we accept automatically?\n\n-Steve\n"},{"id":"46023","messageId":"7vwsxngtfc.fsf@assigned-by-dhcp.pobox.com","threadId":"8754","inReplyTo":"20070628061821.GM32223@spearce.org","subject":"Re: [PATCH] Ignore end-of-line style when computing similarity score for rename detection","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2007-06-29T06:34:47Z","receivedAt":"2007-06-29T06:34:47Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Shawn O. Pearce\" writes:\n\n> Actually even better if you can also run the in/out filter things.\n> I'm thinking of say an XML file that has had whitespace formatting\n> changes, but whose XSD and processors ignore unnecessary whitespace.\n> Be nice if the rename detection actually was able to canonicalize\n> both files before detecting the rename, assuming both files had a\n> canonicalizer input filter defined that does that...\n\nThis certainly is tempting, but I suspect that should be left to\nlater rounds. I suspect that it would introduce a concept of\ntwo different kinds of diffs, one to be mechanically processed\n(i.e. use in merge with \"git-merge-recursive\", and apply with\n\"git-am\"), and another to be inspected by humans to understand.\nIt often may be useful to munge the input for the latter case,\neven though the output from comparing munged input files may not\nbe readily usable for mechanical application.\n\nWhich is not a bad thing per-se, but needs to be done carefully.\n\nA replacement set for Steven to comment on follows.\n\n [PATCH 1/4] diffcore_count_changes: pass diffcore_filespec\n [PATCH 2/4] diffcore_filespec: add is_binary\n [PATCH 3/4] diffcore-delta.c: update the comment on the algorithm.\n [PATCH 4/4] diffcore-delta.c: Ignore CR in CRLF for text files\n"},{"id":"46043","messageId":"Pine.LNX.4.64.0706291114090.4438@racer.site","threadId":"8754","inReplyTo":"4683FB25.3080204@midwinter.com","subject":"Re: [PATCH] Ignore end-of-line style when computing similarity score for rename detection","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2007-06-29T10:19:04Z","receivedAt":"2007-06-29T10:19:04Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Thu, 28 Jun 2007, Steven Grimm wrote:\n\n> Johannes Schindelin wrote:\n> > Somehow I think that this should be triggered by \"--ignore-space-at-eol\",\n> > _and_ be accompanied by a test case.\n> > \n> \n> Should --ignore-space-at-eol be an option to git-merge? Merges are where \n> this functionality matters; for simple diffs, --ignore-space-at-eol \n> actually already covers it.\n\nGood point. However, I fail to see how the similarity detection should be \nso decoupled from the application. IOW what good is it if two files are \nrated similar if the merge cannot handle the CRLF/LF differences properly?\n\nSo two points here: since the merges are what you target, you definitely \nshould mention that in the commit message. And you should make sure that \nall this trickery only kicks in when the merge has a chance to succeed.\n\nCiao,\nDscho\n"}]}