libgit2/libgit2 — pull request #1656 by ethomson (2013-06-17 23:08:48+00:00)
Title: Rename diff failures

Adding some tests that illustrate some issues with renames. The first is another where similarities are similar. Our rename detection always takes the most similar and then removes previous similarities for those sides. But if we later find something *still more* similar, then that previous similarity that we rejected might become legitimate again.

For example, consider these similarities:

`a.txt` -> `c.txt` = 83% similar
`a.txt` -> `d.txt` = 81% similar
`b.txt` -> `c.txt` = 87% similar
`b.txt` -> `d.txt` = 88% similar

Our steps will be:

1. Compare `a.txt` to `c.txt`, mark it as best match for `a.txt` and `c.txt`
2. Compare `b.txt` to `c.txt`, mark it as best match (removing `a.txt` -> `c.txt` match)
3. Compare `a.txt` to `d.txt`, mark it as best match for `a.txt` and `d.txt`
4. Compare `b.txt` to `d.txt`, mark it as best match for `b.txt` and `d.txt` (removing `a.txt` -> `d.txt` and `b.txt` -> `c.txt`)

Which leaves us with a single rename when we expected:

>git status
# On branch renames_similar_two
# Changes to be committed:
# (use "git reset HEAD ..." to unstage)
#
# renamed: a.txt -> c.txt
# renamed: b.txt -> d.txt
#

I tried to attack these problems by creating a list of similarities for all similarities > 50% (or whatever the minimum similarity we care is for renames/rewrites/copies/etc is), sorting that by similarity and applying in that order, except that I got hung up on the renames from rewrites issue.

Which led to unit test #2 - it seems that we only expect renames from rewrites to be 1-cyclical - that a->b and b->a, so I added a unit test that introduces a longer cycle length.

I was then going to break rewrites out in an earlier step, but after reading the `-Bn/m` flag for `git_diff`, my eyes glazed over and I don't think I even understand anything about breaking rewrites anymore. (My reading suggests that the default is to break rewrites *for renames* at 50% but otherwise into an add/delete pair at 60%? Which means at 55% a non-rename is still just modified?) I guess we could break and then reassemble rewrites, but bleh.

I think I'm in over my head with rewrite breaking.

/cc @arrbee