move detection doesnt take filename into account

if you move two identical {e.g.: empty} files to two new locations in a single commit, the move detection picks them {seemingly?} arbitrarily. it should use a statistical algorithm to compare the filenames and pick a likely match.

my apologies in advance if this isnt the right venue or is improperly formatted, or if this is extraneous noise, or widely known, etc.

+ cd /tmp
+ mkdir repo
+ cd repo
+ git init
Initialized empty Git repository in /tmp/repo/.git/
+ touch a1 b1 c1
+ git add a1 b1 c1
+ git commit -m 1
[master (root-commit) 72f8c89] 1

 3 files changed, 0 insertions(+), 0 deletions(-)
 create mode 100644 a1
 create mode 100644 b1
 create mode 100644 c1

+ git mv a1 a2
+ git mv b1 b2
+ git mv c1 c2
+ git commit -m 2
[master 359da78] 2

 3 files changed, 0 insertions(+), 0 deletions(-)
 rename c1 => a2 (100%)
 rename b1 => b2 (100%)
 rename a1 => c2 (100%)
+ git log --name-status -M
commit 359da78caaaf06848ae32359abfeb87db35cdb30
Author: Elliot Wolk <[email protected]>
Date:   Mon Jun 30 02:26:49 2014 -0400

    2

R100    c1      a2
R100    b1      b2
R100    a1      c2

commit 72f8c89b418e3b1d13ec350f4c30b5088fc69e83

Author: Elliot Wolk <[email protected]>
Date:   Mon Jun 30 02:26:49 2014 -0400

    1

A       a1
A       b1
A       c1

----- Ursprungligt meddelande -----

I think it does, but based on filename suffix. E.g. here is a rename of three empty files with a suffix.

 3 files changed, 0 insertions(+), 0 deletions(-)
 rename 1.a => 2.a (100%)
 rename 1.b => 2.b (100%)
 rename 1.c => 2.c (100%)

-- robin

interesting that it considers suffixes {only suffixes following periods?}. this is insufficient, in my opinion.

with all other things being equal, it ought to find the closest match {using smith-waterman or some such algorithm}.

as a real-world use case, i have a repository with empty files that mirrors the file structure of a directory containing large binary files. when i move a dir, it seems to select the files renamed at random.

This is not more than a chance.

We tie-break rename source candidates that have the same content similarity score to a rename destination using "name similarity", whose implementation has been diffcore-rename.c::basename_same(), which scores 1 if basename $src and basename $dst are the same and 0 otherwise, i.e. from 1.a to a/1.a is judged to be a better rename than from 1.a to a/2.a but otherwise there is nothing that favors rename from 1.a to 2.a over 1.a to 2.b.

thanks for the info!
then i suppose my bug is a petition to have name similarity instead use a different statistical matching algorithm.

[administrivia: please do not top-post on this list]

I didn't think it through but my gut feeling is that we could change the name similarity score to be the length of the tail part that matches (e.g. 1.a to a/2.a that has the same two bytes at the tail is a better match than to a/2.b that does not share any tail, and to a/1.a that shares the three bytes at the tail is an even better match).

Oh, and rename basename_same() to something else; currently it is only used as the "name similarity", and after such a change, it will stay to be "name similarity" but will not be asking "are basenames the same?" anymore.

Hint, hint...

The delta heuristics in pack-objects use pack_name_hash, which claims:

/*
* This effectively just creates a sortable number from the
* last sixteen non-whitespace characters. Last characters
* count "most", so things that end in ".c" sort together. */

which might be another option (and seems like a superset of the basename check, short of basenames that are longer than 16 characters).

-Peff

Perhaps.

I am however not sure if the code to compute similarity score is as OK with false positives, i.e. dissimilar names that happen to hash together getting clumped in a same bin or in close bins, as the existing callers of pack_name_hash().

I think the hash here does not collide in that way. It really is just the last sixteen characters shoved into a uint32_t.

But thinking on it more, that is useful to the delta code because it wants to create a sorted list of items. In the rename code we are doing pairwise comparisons, so we are more flexible. We can compare whole basenames, or whole suffixes (so "a/foo/bar.c" is closer to "b/foo/bar.c" than to "c/other/bar.c"). Or just use a general-purpose edit-distance function.

The tricky part is that the rename detection seems to take the score as a binary 0/1 "is it the same", but we would want to express more nuance (i.e., the "best" match among those that have similar content scores).

-Peff

All bytes overlap with their adjacent byte because they are shifted by only 2 bits, not 8 bits, when a new byte is brought in. We can say that the topmost two bits of the result must have come from the last character, but other than these, there are more than one input byte for each bit position to be set/unset by, so two names that human would not consider "similar" would be given the same hash, no?

That is useful for delta code because the code only needs that similar things are grouped together, it does not mind things that are not similar is also mixed to a group, as the end result is primarily determined by similarity of the actual contents, not pathnames.

What is under topic in this discussion is the other way around; we know two paths have contents of the same similarity to the third one and want to tie-break these two using how similar their pathnames are to the third one.

Yeah, you're right. I didn't look at the algorithm closely enough.

-Peff