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