libgit2/libgit2 — pull request #1643 by ethomson (2013-06-10 20:38:40+00:00)
Title: Keep data about source of similarity

This change adds data about the source of similarity matching. Consider the case where you have two files, both very similar and both renamed and modified such that they rename very similar. For example:

Initial commit:
Class1.cs: `class Class1 { }`
Class2.cs: `class Class2 { }`

And these files are both renamed:
ClassA.cs: `class ClassA { }`
ClassB.cs: `class ClassB { }`

The loop in `git_diff_find_similar` loops at the possible rename targets (in this case, ClassA.cs and ClassB.cs) and compute similarity from possible sources and record them in the `matches` array.

If our `deltas` vector is:
1. Class1.cs (delete)
2. Class2.cs (delete)
3. ClassA.cs (add)
4. ClassB.cs (add)

Then we will decide that ClassA.cs is 96% similar to Class1.cs and record it as `match[2]`. Since ClassA.cs is also 96% similar to Class2.cs, it is not better, and this match is ignored.

Similarly, we will decide that ClassB.cs is 96% similar to Class1.cs and record it as `match[3]`. Again, Class2.cs will be ignored.

After the loop to calculate similarity:

matches[2] = { idx = 0, similarity = 93 }
matches[3] = { idx = 0, similarity = 93 }

This gives us a rename from Class1.cs to ClassA.cs, and records Class2.cs as a delete and ClassB.cs as an add. This is nonoptimal and different from core git.

By adding data about the similarity source, we are able to avoid doubling up a single source as the best similarity match for two targets. With the proposed change, at the end of our loop:

matches[2] = { idx = 0, similarity = 93 }
matches[3] = { idx = 1, similarity = 93 }

And thus we have a rename from Class1.cs to ClassA.cs and a rename from Class2.cs to ClassB.cs.