github - Trying to understand `git diff` and `git mv` rename detection mechanism

Question

This is a followup to another question I asked before.

Before being edited, the initially created file something gets renamed to somethingelse which can be observed here:

git mv something somethingelse

The file somethingelse then gets renamed back to something before the second vim edit:

git mv somethingelse something

Basically in the following portion of the code:

# If you add something to the first line, the rename will not be detected by Git
# However, if you instead create 2 newlines and fill line 3 with new code,
# the rename gets detected for whatever reason
printf "
COMMAND: vim something

"
vim something

If at this point I add abc to the code, we would end up with:

First line of code. abc

Which I think is an addition of 4 bytes on line 1, which in turn will end up in this:

On branch master
Changes to be committed:
  (use "git reset HEAD <file>..." to unstage)

        new file:   something
        deleted:    somethingelse

Then, if we add a newline and type in abc into the third line (which should also be 4 bytes, correct me if wrong):

First line of code.

abc

Suddenly, Git will detect the rename (edit inclusive):

On branch master
Changes to be committed:
  (use "git reset HEAD <file>..." to unstage)

        renamed:    somethingelse -> something

One good answer/comment by @torek given here explains this to a certain extent, taking the git diff rename detection treshold of git status into consideration.

Shouldn't Git behave identically since we added 4 bytes in both cases, but in a different manner or does the newline have something to do with this?

Answer 1

Git's "similarity index" computation is not, as far as I know, documented anywhere other than in the source, starting with diffcore-delta.c.

To compute the similarity index for two files S (source) and D (destination), Git:

• reads both files
• computes a hash table of all of the chunks of file S
• computes a second hash table of all of the chunks of file D

The entries in these two hash tables are simply a count of occurrences of instances of that hash value (plus, as noted below, the length of the chunk).

The hash value for a file chunk is computed by:

• start at the current file offset (initially zero)
• read 64 bytes or until ' ' character, whichever occurs first
• if the file is claimed to be text and there is a ' ' before the ' ', discard the ' '
• hash the resulting string-of-up-to-64 bytes using the algorithm shown in the linked file

Now that there are hash tables for both S and D, each possible hash h_i appears n_S times in S and n_D in D (either may be zero, though the code skips right over both-zero hash values). If the number of occurrences in D is less than or the same as the number of occurrences in S—i.e., n_D ≤ n_S—then D "copies from S" n_D times. If the number of occurrences in D exceeds the number in S (including when the number in S is zero), then D has a "literal add" of n_D - n_S occurrences of the hashed chunk, and D also copies all n_S original occurrences as well.

Each hashed chunk retains its number-of-input-bytes, and these multiply the number of copies or number of additions of "chunks" to get the number of bytes copied or added. (Deletions, where D lacks items that exist in S, have only indirect effect here: the byte copy and add counts get smaller, but Git does not specifically count the deletions themselves.)

These two values (src_copied and literal_added) computed in diffcore_count_changes are handed over to function estimate_similarity in diffcore-rename.c. It completely ignores the literal_added count (this count is used in deciding how to build packfile deltas, but not in terms of rename scoring). Instead, only the src_copied number matters:

score = (int)(src_copied * MAX_SCORE / max_size);

where max_size is the size in bytes of larger of the two input files S and D.

Note that there is an earlier computation:

max_size = ((src->size > dst->size) ? src->size : dst->size);
base_size = ((src->size < dst->size) ? src->size : dst->size);
delta_size = max_size - base_size;

and if the two files have changed size "too much":

if (max_size * (MAX_SCORE-minimum_score) < delta_size * MAX_SCORE)
        return 0;

we never even get into the diffcore-delta.c code to hash them. The minimum_score here is the argument to -M or --find-renames, converted to a scaled number. MAX_SCORE is 60000.0 (type double), so the default minimum_score, when you use the default -M50%, is 30000 (half of 60000). Except for the case of CR-before-LF eating, though, this particular shortcut should not affect the outcome of the more expensive similarity computation.

Again, git status always uses the default. There is no knob to change the threshold (nor the number of files allowed in the rename-finding queue). If there were the code would go here, setting the rename_score field of the diff options.