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

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