{"thread":{"id":"37025","subject":"move detection doesnt take filename into account","startedAt":"2014-06-30T06:38:18Z","lastAt":"2014-07-10T03:53:28Z","messageCount":11,"participants":["Elliot Wolk","Robin Rosenberg","Junio C Hamano","Jeff King"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"245171","messageId":"53B105DA.30004@gmail.com","threadId":"37025","inReplyTo":null,"subject":"move detection doesnt take filename into account","fromName":"Elliot Wolk","fromEmail":"elliot.wolk@gmail.com","sentAt":"2014-06-30T06:38:18Z","receivedAt":"2014-06-30T06:38:18Z","isPatch":false,"sender":{"key":"elliot.wolk@gmail.com","avatar":null},"body":"if you move two identical {e.g.: empty} files to two new locations in a \nsingle commit, the move detection picks them {seemingly?} arbitrarily. \nit should use a statistical algorithm to compare the filenames and pick \na likely match.\n\nmy apologies in advance if this isnt the right venue or is improperly \nformatted, or if this is extraneous noise, or widely known, etc.\n\n+ cd /tmp\n+ mkdir repo\n+ cd repo\n+ git init\nInitialized empty Git repository in /tmp/repo/.git/\n+ touch a1 b1 c1\n+ git add a1 b1 c1\n+ git commit -m 1\n[master (root-commit) 72f8c89] 1\n 3 files changed, 0 insertions(+), 0 deletions(-)\n create mode 100644 a1\n create mode 100644 b1\n create mode 100644 c1\n+ git mv a1 a2\n+ git mv b1 b2\n+ git mv c1 c2\n+ git commit -m 2\n[master 359da78] 2\n 3 files changed, 0 insertions(+), 0 deletions(-)\n rename c1 => a2 (100%)\n rename b1 => b2 (100%)\n rename a1 => c2 (100%)\n+ git log --name-status -M\ncommit 359da78caaaf06848ae32359abfeb87db35cdb30\nAuthor: Elliot Wolk \nDate: Mon Jun 30 02:26:49 2014 -0400\n\n 2\n\nR100 c1 a2\nR100 b1 b2\nR100 a1 c2\n\ncommit 72f8c89b418e3b1d13ec350f4c30b5088fc69e83\nAuthor: Elliot Wolk \nDate: Mon Jun 30 02:26:49 2014 -0400\n\n 1\n\nA a1\nA b1\nA c1\n"},{"id":"245228","messageId":"287177519.16421.1404206204124.JavaMail.zimbra@dewire.com","threadId":"37025","inReplyTo":"53B105DA.30004@gmail.com","subject":"Re: move detection doesnt take filename into account","fromName":"Robin Rosenberg","fromEmail":"robin.rosenberg@dewire.com","sentAt":"2014-07-01T09:16:44Z","receivedAt":"2014-07-01T09:16:44Z","isPatch":false,"sender":{"key":"robin.rosenberg@dewire.com","avatar":"https://avatars.githubusercontent.com/u/46357?v=4"},"body":"\n\n----- Ursprungligt meddelande -----\n> Från: \"Elliot Wolk\" \n> Till: git@vger.kernel.org\n> Skickat: måndag, 30 jun 2014 8:38:18\n> Ämne: move detection doesnt take filename into account\n> \n> if you move two identical {e.g.: empty} files to two new locations in a\n> single commit, the move detection picks them {seemingly?} arbitrarily.\n> it should use a statistical algorithm to compare the filenames and pick\n> a likely match.\n\nI think it does, but based on filename suffix. E.g. here is a rename of\nthree empty files with a suffix.\n\n 3 files changed, 0 insertions(+), 0 deletions(-)\n rename 1.a => 2.a (100%)\n rename 1.b => 2.b (100%)\n rename 1.c => 2.c (100%)\n\n-- robin\n"},{"id":"245231","messageId":"53B2C870.4030406@gmail.com","threadId":"37025","inReplyTo":"287177519.16421.1404206204124.JavaMail.zimbra@dewire.com","subject":"Re: move detection doesnt take filename into account","fromName":"Elliot Wolk","fromEmail":"elliot.wolk@gmail.com","sentAt":"2014-07-01T14:40:48Z","receivedAt":"2014-07-01T14:40:48Z","isPatch":false,"sender":{"key":"elliot.wolk@gmail.com","avatar":null},"body":"interesting that it considers suffixes {only suffixes following \nperiods?}. this is insufficient, in my opinion.\n\nwith all other things being equal, it ought to find the closest match \n{using smith-waterman or some such algorithm}.\n\nas a real-world use case, i have a repository with empty files that \nmirrors the file structure of a directory containing large binary files.\nwhen i move a dir, it seems to select the files renamed at random.\n\nOn 07/01/2014 05:16 AM, Robin Rosenberg wrote:\n>\n> ----- Ursprungligt meddelande -----\n>> Från: \"Elliot Wolk\" \n>> Till: git@vger.kernel.org\n>> Skickat: måndag, 30 jun 2014 8:38:18\n>> Ämne: move detection doesnt take filename into account\n>>\n>> if you move two identical {e.g.: empty} files to two new locations in a\n>> single commit, the move detection picks them {seemingly?} arbitrarily.\n>> it should use a statistical algorithm to compare the filenames and pick\n>> a likely match.\n> I think it does, but based on filename suffix. E.g. here is a rename of\n> three empty files with a suffix.\n>\n> 3 files changed, 0 insertions(+), 0 deletions(-)\n> rename 1.a => 2.a (100%)\n> rename 1.b => 2.b (100%)\n> rename 1.c => 2.c (100%)\n>\n> -- robin\n"},{"id":"245233","messageId":"xmqqtx71xh27.fsf@gitster.dls.corp.google.com","threadId":"37025","inReplyTo":"287177519.16421.1404206204124.JavaMail.zimbra@dewire.com","subject":"Re: move detection doesnt take filename into account","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-07-01T14:57:36Z","receivedAt":"2014-07-01T14:57:36Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Robin Rosenberg writes:\n\n> I think it does, but based on filename suffix. E.g. here is a rename of\n> three empty files with a suffix.\n>\n> 3 files changed, 0 insertions(+), 0 deletions(-)\n> rename 1.a => 2.a (100%)\n> rename 1.b => 2.b (100%)\n> rename 1.c => 2.c (100%)\n\nThis is not more than a chance.\n\nWe tie-break rename source candidates that have the same content\nsimilarity score to a rename destination using \"name similarity\",\nwhose implementation has been diffcore-rename.c::basename_same(),\nwhich scores 1 if `basename $src` and `basename $dst` are the same\nand 0 otherwise, i.e. from 1.a to a/1.a is judged to be a better\nrename than from 1.a to a/2.a but otherwise there is nothing that\nfavors rename from 1.a to 2.a over 1.a to 2.b.\n"},{"id":"245235","messageId":"53B2CE4A.9060509@gmail.com","threadId":"37025","inReplyTo":"xmqqtx71xh27.fsf@gitster.dls.corp.google.com","subject":"Re: move detection doesnt take filename into account","fromName":"Elliot Wolk","fromEmail":"elliot.wolk@gmail.com","sentAt":"2014-07-01T15:05:46Z","receivedAt":"2014-07-01T15:05:46Z","isPatch":false,"sender":{"key":"elliot.wolk@gmail.com","avatar":null},"body":"thanks for the info!\nthen i suppose my bug is a petition to have name similarity instead use \na different statistical matching algorithm.\n\nOn 07/01/2014 10:57 AM, Junio C Hamano wrote:\n> Robin Rosenberg writes:\n>\n>> I think it does, but based on filename suffix. E.g. here is a rename of\n>> three empty files with a suffix.\n>>\n>> 3 files changed, 0 insertions(+), 0 deletions(-)\n>> rename 1.a => 2.a (100%)\n>> rename 1.b => 2.b (100%)\n>> rename 1.c => 2.c (100%)\n> This is not more than a chance.\n>\n> We tie-break rename source candidates that have the same content\n> similarity score to a rename destination using \"name similarity\",\n> whose implementation has been diffcore-rename.c::basename_same(),\n> which scores 1 if `basename $src` and `basename $dst` are the same\n> and 0 otherwise, i.e. from 1.a to a/1.a is judged to be a better\n> rename than from 1.a to a/2.a but otherwise there is nothing that\n> favors rename from 1.a to 2.a over 1.a to 2.b.\n"},{"id":"245240","messageId":"xmqq61jhxb0g.fsf@gitster.dls.corp.google.com","threadId":"37025","inReplyTo":"53B2CE4A.9060509@gmail.com","subject":"Re: move detection doesnt take filename into account","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-07-01T17:08:15Z","receivedAt":"2014-07-01T17:08:15Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Elliot Wolk writes:\n\n> On 07/01/2014 10:57 AM, Junio C Hamano wrote:\n>> Robin Rosenberg writes:\n>>\n>>> I think it does, but based on filename suffix. E.g. here is a rename of\n>>> three empty files with a suffix.\n>>>\n>>> 3 files changed, 0 insertions(+), 0 deletions(-)\n>>> rename 1.a => 2.a (100%)\n>>> rename 1.b => 2.b (100%)\n>>> rename 1.c => 2.c (100%)\n>> This is not more than a chance.\n>>\n>> We tie-break rename source candidates that have the same content\n>> similarity score to a rename destination using \"name similarity\",\n>> whose implementation has been diffcore-rename.c::basename_same(),\n>> which scores 1 if `basename $src` and `basename $dst` are the same\n>> and 0 otherwise, i.e. from 1.a to a/1.a is judged to be a better\n>> rename than from 1.a to a/2.a but otherwise there is nothing that\n>> favors rename from 1.a to 2.a over 1.a to 2.b.\n>\n> thanks for the info!\n> then i suppose my bug is a petition to have name similarity instead\n> use a different statistical matching algorithm.\n\n[administrivia: please do not top-post on this list]\n\nI didn't think it through but my gut feeling is that we could change\nthe name similarity score to be the length of the tail part that\nmatches (e.g. 1.a to a/2.a that has the same two bytes at the tail\nis a better match than to a/2.b that does not share any tail, and to\na/1.a that shares the three bytes at the tail is an even better\nmatch).\n\nOh, and rename basename_same() to something else; currently it is\nonly used as the \"name similarity\", and after such a change, it will\nstay to be \"name similarity\" but will not be asking \"are basenames\nthe same?\" anymore.\n\nHint, hint...\n"},{"id":"245576","messageId":"20140709064521.GA14682@sigill.intra.peff.net","threadId":"37025","inReplyTo":"xmqq61jhxb0g.fsf@gitster.dls.corp.google.com","subject":"Re: move detection doesnt take filename into account","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-07-09T06:45:21Z","receivedAt":"2014-07-09T06:45:21Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jul 01, 2014 at 10:08:15AM -0700, Junio C Hamano wrote:\n\n> I didn't think it through but my gut feeling is that we could change\n> the name similarity score to be the length of the tail part that\n> matches (e.g. 1.a to a/2.a that has the same two bytes at the tail\n> is a better match than to a/2.b that does not share any tail, and to\n> a/1.a that shares the three bytes at the tail is an even better\n> match).\n\nThe delta heuristics in pack-objects use pack_name_hash, which claims:\n\n /*\n * This effectively just creates a sortable number from the\n * last sixteen non-whitespace characters. Last characters\n * count \"most\", so things that end in \".c\" sort together.\n */\n\nwhich might be another option (and seems like a superset of the basename\ncheck, short of basenames that are longer than 16 characters).\n\n-Peff\n"},{"id":"245636","messageId":"xmqqegxu7cpg.fsf@gitster.dls.corp.google.com","threadId":"37025","inReplyTo":"20140709064521.GA14682@sigill.intra.peff.net","subject":"Re: move detection doesnt take filename into account","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-07-09T15:51:07Z","receivedAt":"2014-07-09T15:51:07Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> On Tue, Jul 01, 2014 at 10:08:15AM -0700, Junio C Hamano wrote:\n>\n>> I didn't think it through but my gut feeling is that we could change\n>> the name similarity score to be the length of the tail part that\n>> matches (e.g. 1.a to a/2.a that has the same two bytes at the tail\n>> is a better match than to a/2.b that does not share any tail, and to\n>> a/1.a that shares the three bytes at the tail is an even better\n>> match).\n>\n> The delta heuristics in pack-objects use pack_name_hash, which claims:\n>\n> /*\n> * This effectively just creates a sortable number from the\n> * last sixteen non-whitespace characters. Last characters\n> * count \"most\", so things that end in \".c\" sort together.\n> */\n>\n> which might be another option (and seems like a superset of the basename\n> check, short of basenames that are longer than 16 characters).\n\nPerhaps.\n\nI am however not sure if the code to compute similarity score is as\nOK with false positives, i.e. dissimilar names that happen to hash\ntogether getting clumped in a same bin or in close bins, as the\nexisting callers of pack_name_hash().\n"},{"id":"245666","messageId":"20140709220337.GF25854@sigill.intra.peff.net","threadId":"37025","inReplyTo":"xmqqegxu7cpg.fsf@gitster.dls.corp.google.com","subject":"Re: move detection doesnt take filename into account","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-07-09T22:03:37Z","receivedAt":"2014-07-09T22:03:37Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 09, 2014 at 08:51:07AM -0700, Junio C Hamano wrote:\n\n> > The delta heuristics in pack-objects use pack_name_hash, which claims:\n> >\n> > /*\n> > * This effectively just creates a sortable number from the\n> > * last sixteen non-whitespace characters. Last characters\n> > * count \"most\", so things that end in \".c\" sort together.\n> > */\n> >\n> > which might be another option (and seems like a superset of the basename\n> > check, short of basenames that are longer than 16 characters).\n> \n> Perhaps.\n> \n> I am however not sure if the code to compute similarity score is as\n> OK with false positives, i.e. dissimilar names that happen to hash\n> together getting clumped in a same bin or in close bins, as the\n> existing callers of pack_name_hash().\n\nI think the hash here does not collide in that way. It really is just\nthe last sixteen characters shoved into a uint32_t.\n\nBut thinking on it more, that is useful to the delta code because it\nwants to create a sorted list of items. In the rename code we are doing\npairwise comparisons, so we are more flexible. We can compare whole\nbasenames, or whole suffixes (so \"a/foo/bar.c\" is closer to\n\"b/foo/bar.c\" than to \"c/other/bar.c\"). Or just use a general-purpose\nedit-distance function.\n\nThe tricky part is that the rename detection seems to take the score as\na binary 0/1 \"is it the same\", but we would want to express more nuance\n(i.e., the \"best\" match among those that have similar content scores).\n\n-Peff\n"},{"id":"245670","messageId":"xmqqa98i9nwc.fsf@gitster.dls.corp.google.com","threadId":"37025","inReplyTo":"20140709220337.GF25854@sigill.intra.peff.net","subject":"Re: move detection doesnt take filename into account","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2014-07-09T22:18:43Z","receivedAt":"2014-07-09T22:18:43Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King writes:\n\n> I think the hash here does not collide in that way. It really is just\n> the last sixteen characters shoved into a uint32_t.\n\nAll bytes overlap with their adjacent byte because they are shifted\nby only 2 bits, not 8 bits, when a new byte is brought in. We can\nsay that the topmost two bits of the result must have come from the\nlast character, but other than these, there are more than one input\nbyte for each bit position to be set/unset by, so two names that human\nwould not consider \"similar\" would be given the same hash, no?\n\nThat is useful for delta code because the code only needs that\nsimilar things are grouped together, it does not mind things that\nare not similar is also mixed to a group, as the end result is\nprimarily determined by similarity of the actual contents, not\npathnames.\n\nWhat is under topic in this discussion is the other way around; we\nknow two paths have contents of the same similarity to the third one\nand want to tie-break these two using how similar their pathnames\nare to the third one. \n"},{"id":"245675","messageId":"20140710035328.GB28401@sigill.intra.peff.net","threadId":"37025","inReplyTo":"xmqqa98i9nwc.fsf@gitster.dls.corp.google.com","subject":"Re: move detection doesnt take filename into account","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2014-07-10T03:53:28Z","receivedAt":"2014-07-10T03:53:28Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Wed, Jul 09, 2014 at 03:18:43PM -0700, Junio C Hamano wrote:\n\n> Jeff King writes:\n> \n> > I think the hash here does not collide in that way. It really is just\n> > the last sixteen characters shoved into a uint32_t.\n> \n> All bytes overlap with their adjacent byte because they are shifted\n> by only 2 bits, not 8 bits, when a new byte is brought in. We can\n> say that the topmost two bits of the result must have come from the\n> last character, but other than these, there are more than one input\n> byte for each bit position to be set/unset by, so two names that human\n> would not consider \"similar\" would be given the same hash, no?\n\nYeah, you're right. I didn't look at the algorithm closely enough.\n\n-Peff\n"}]}