Directory rename detection breaks if repo has a lot of similar/identical files

[Yannis Zarkadas <yanniszark@arrikto.com>]

Hi everyone! I believe I have found a use-case that breaks git's directory
rename detection algorithm. In short, when a repo has a lot of identical 
files,
directory rename detection breaks. I believe this happens because git feeds
misleading renames to the directory rename detection algorithm.

For example, suppose a changeset (COMMIT_A, COMMIT_B). If `x/a` and `y/b` in
COMMIT_A are the same as `new/x/a` and `new/y/b` in COMMIT_B, then git may
decide the renames are `x/a -> new/y/b` and `y/b -> new/x/a` instead of
`x/a -> new/x/a` and `y/b -> new/y/b`. Of course, this confuses the 
directory
rename detection algorithm.

To make a long story short (I am including all the individual steps to
investigate this below), it seems the following enhancement would work 
to solve
this particular problem:

If file `a/base/base.txt` in COMMIT_A is the same as 
`new/a/base/base.txt` AND
`new/z/base/base.txt` in COMMIT_B, then prefer the rename
`a/base/base.txt->new/a/base/base.txt` over the rename
`a/base/base.txt->new/z/base/base.txt`. I have included a more generic 
algorithm
below.


Problem
=======

The original repo was very large, so I tried to find a simpler example that
caused git to detect directory renames incorrectly. I managed to create such
an environment with the following script:
https://gist.github.com/yanniszark/4165bd8f92d9838e143495e5a8df2ce0

The script creates a repo (/tmp/demo) with 3 branches:
- *upstream*: Contains a lot of folders, with some files being identical 
across
   folders.
- *upstream-restructured*: Same as upstream, but with all folders moved 
under
   `new/`. For example, `a/`->`new/a`
- *downstream*: Based on upstream, adds some extra files under every 
folder of
   upstream.

Then, it tries to rebase downstream ontop of upstream-restructured. Git 
detects
the WRONG directory rename `z/->new/a/` and fails with a wrong conflict.

$ git -c merge.directoryRenames=true rebase -v -m --onto 
upstream-restructured upstream
Path updated: z/overlays/develop/overlay.txt added in 9bf94f0 (Add 
overlay for z) inside a directory that was renamed in HEAD; moving it to 
new/a/overlays/develop/overlay.txt.
CONFLICT (rename/rename): Rename 
a/overlays/develop/overlay.txt->new/a/overlays/develop/overlay.txt in 
HEAD. Rename 
z/overlays/develop/overlay.txt->new/a/overlays/develop/overlay.txt in 
9bf94f0 (Add overlay for z)


We are going to work with this example for the rest of this mail.


Analysis
========

After learning a bit about how git works internally, I found out:
- Rebasing with the merge backend (`-m`) uses cherry-pick underneath.
- Cherry-pick frames the problem as a merge, with the merge-base being the
   parent of the REMOTE commit.
- The merge algorithm accepts 3 inputs (BASE, LOCAL, REMOTE), computes the
   changesets of (BASE, LOCAL) and (BASE, REMOTE), and finally combines 
them.


With this background in mind, I run the demo script and got this message:

Path updated: z/overlays/develop/overlay.txt added in 9bf94f0 (Add 
overlay for z) inside a directory that was renamed in HEAD; moving it to 
new/a/overlays/develop/overlay.txt.
CONFLICT (rename/rename): Rename 
a/overlays/develop/overlay.txt->new/a/overlays/develop/overlay.txt in 
HEAD. Rename 
z/overlays/develop/overlay.txt->new/a/overlays/develop/overlay.txt in 
9bf94f0 (Add overlay for z)

Applying our knowledge of rebase, cherry-pick and merge from above, let's
calculate the BASE, LOCAL and REMOTE commits.

LOCAL=HEAD
REMOTE=9bf94f0  # same as the error message
BASE=REMOTE~    # based on how cherry-pick works

At this point, we can peek at what changesets git's merge algorithm is 
seeing:

git diff --find-renames --stat $BASE $LOCAL
git diff --find-renames --stat $BASE $REMOTE

The first command is the interesting one and returns suspicious entries 
like the
following:

{z => new/a}/base/base.txt                   | 0
{a => new/a}/overlays/develop/overlay.txt    | 0
{a => new/a}/overlays/upstream/file_1.txt    | 0
{z => new/a}/overlays/upstream/file_3.txt    | 0
{z => new/a}/overlays/upstream/file_5.txt    | 0
{a => new/a}/overlays/upstream/file_a.txt    | 0
{z => new/a}/overlays/upstream/overlay.txt   | 0
[...]
{a => new/z}/base/base.txt                   | 0
{z => new/z}/overlays/upstream/file_1.txt    | 0
{a => new/z}/overlays/upstream/file_3.txt    | 0
{a => new/z}/overlays/upstream/file_5.txt    | 0
{z => new/z}/overlays/upstream/file_z.txt    | 0
{a => new/z}/overlays/upstream/overlay.txt   | 0


Hypothesis
==========

At this point, I formed a hypothesis:
- git detects renames between (BASE, LOCAL) as they appear in the `git diff`
   command above.
- git feeds those renames in the directory rename detection algorithm, which
   gets confused about what directory renames actually happened.


Confirming the Hypothesis
=========================

I tried to confirm my hypothesis by diving in the source code. My C is a bit
rusty, but I managed to find out the function that handles the renames, 
called
`detect_and_process_renames` (inside `merge-recursive.c`). The following 
part
is particularly interesting:

head_pairs = get_diffpairs(opt, common, head);
merge_pairs = get_diffpairs(opt, common, merge);
[...]
     dir_re_head = get_directory_renames(head_pairs);
     dir_re_merge = get_directory_renames(merge_pairs);

The first part is computing the changeset for (BASE, LOCAL) and (BASE, 
REMOTE).
The second part is feeding the changeset to the get_directory_renames 
function
for calculating directory renames.

By inspecting the `head_pairs` variable with my debugger, I confirmed 
that the
changeset is the one I saw with `git diff`. Indeed, git is feeding the
`get_directory_renames` function confusing renames.


Proposed Enhancement
====================

Now that we know what is most likely going on, I can describe what I 
would like
git to do.

Intuition: If file `a/base/base.txt` in BASE is the same as
`new/a/base/base.txt` AND `new/z/base/base.txt` in LOCAL, then prefer 
the rename
`a/base/base.txt->new/a/base/base.txt` over the rename
`a/base/base.txt->new/z/base/base.txt`.

In other words, if multiple rename candidates are possible, prefer the 
ones that
look more like the user move the file/folder from one path to another.

Possible Algorithm:

More generally, if files `A1`, `A2`, ..., `An` in commit A are the same 
as `B1`,
`B2`, `Bm` in commit B, then:
- Calculate a sorted list of scores `S(Ai, Bj), i=1,...,n and 
j=1,...,m`, where
   `S(Ai, Bj)` is the length of the suffix match of `Ai` and `Bj`.
- Walk the sorted list and for each element:
     - If `Ai` and `Bj` is not used in a rename yet, apply the rename.
     - Stop when you have found `min(n, m)` renames.
- The remaining `max(n, m) - min(n, m)` files are either deletes (if 
they are on
   commit A) or copies (if they are on commit B).


Conclusion
==========

I want to attempt to implement something like what I described above, when I
have more time to get familiar with diff's internals. In the meantime, I 
would
love to hear the opinion of more seasoned git developers on this issue. 
Do you
agree with my findings and the direction I proposed? Is there something 
I have
overlooked? Perhaps someone is already having these problems.


Thanks in advance,
Yannis Zarkadas