Re: [PATCH 3/3] diffcore-rename: guide inexact rename detection based on basenames

Hi,

On Sun, Feb 7, 2021 at 6:38 AM Derrick Stolee <stolee@gmail.com> wrote:

I'm glad you all are open to possible behavioral changes, but I was
proposing a much smaller behavioral change that is quite different
than what you have suggested here.  Perhaps my wording was poor; I
apologize for forgetting that "basename" has different meanings in
different contexts.  Let me try again; I am not treating the filename
extension as special in any manner here; by "basename" I just mean the
portion of the path ignoring any leading directories.  Thus
    src/foo.txt
might be a good match against
    source/foo.txt
but this optimization as a preliminary step would not consider
matching src/foo.txt against any of
    source/bar.txt
    source/foo.md
since the basenames ('bar.txt' and 'foo.md') do not match our original
file's basename ('foo.txt').

Of course, if this preliminary optimization step fails to find another "foo.txt" to match src/foo.txt against (or finds more than one and thus doesn't compare against any of them), then the fallback inexact rename detection matrix might match it against either of those two latter paths, as it always has.

Seems reasonable; I'll add some commentary below on the rules...

0. Unless break detection is on, files with the same fullname are
considered the same file even if their content is completely
different.  (With break detection turned on, we can have e.g. both
src/foo.txt -> src/bar.txt and otherdir/baz.txt -> src/foo.txt, i.e.
src/foo.txt can be both a source and a destination of a rename.)

[The merge machinery never turns break detection on, but diffcore-rename is used by git diff, git log, etc. too, so if we're documenting the rules we should cover all the cases.]

find_identical_files() already breaks ties based on basename_same(), yes. So there's another area of the code that uses basenames to guide rename detection already, just in a much more limited fashion.

This is an interesting idea, but is not what I implemented. It is possible that your suggestion is also a useful optimization; it'd be hard to know without trying. However, as noted in optimization batch 8 that I'll be submitting later, I'm worried about having any optimization pre-steps doing more than O(1) comparisons per path (and here you suggest comparing each .txt file with all other .txt files); doing that can interact badly with optimization batch 9. Additionally, unless we do something to avoid re-comparing files again when doing the later all-unmatched-files-against-each-other check, then worst case behavior can approach twice as slow as the original code.

Anyway, the explanation I'd use for the optimization I've added in this series is:

       i. if looking through the two sets (of add pairs, and of delete
pairs), there is exactly one file with the same basename from each
set, and they have the minimum similarity, then mark them as a rename

Optimization batch 8 will extend this particular rule.

Optimization batches 9 and 10 will optimize the rename detection more, but instead of using rule changes, will instead pass in a list of "irrelevant" sources that can be skipped. The trick is in determining source files that are irrelevant and why. I'm not sure if we want to also mention in the rules that different areas of the code (the merge machinery, log --follow, etc.) can make the rename detection focus just on some "relevant" subset of files. (Which will also touch on optimization batch 12.)

Yes, this will remain as the fallback at the very end.

Yeah, and we probably also need to mention copy detection above somehow too, and add more precise wording about how break detection is involved.