Re: Fix a pathological case in git detecting proper renames

From: Junio C Hamano <gitster@pobox.com>
Date: Nov 30, 2007, 00:40 UTC
Message-ID: <7v4pf4tvka.fsf@gitster.siamese.dyndns.org>
In-Reply-To: <alpine.LFD.0.9999.0711291442300.8458@woody.linux-foundation.org>

Linus Torvalds <torvalds@linux-foundation.org> writes:

Show 7 quoted lines

> For the fuzzy rename detection, we generate the full score matrix, and 
> sort it by the score, up front. So all the scoring - and more importantly, 
> all the sorting - has actually been done before we actually start looking 
> at *any* renames at all, so we cannot easily do the same thing I did for 
> the exact renames, namely to take into account _earlier_ renames in the 
> scoring. Because those earlier renames have simply not been done when the 
> score is calculated.

I think I've mentioned this before, but another thing we may want to do is to give similarity boost to a src-dst pair if other files in the same src directory are found to be renamed to the same dst directory. That is, if you have the same contents in the preimage at A/init.S and B/init.S, and a similar contents appear in C/init.S in the postimage, instead of randomly picking A/init.S over B/init.S as the source, we can notice that A/Makefile was moved to C/Makefile (but B/Makefile was sufficiently different from A/Makefile in the preimage), and favor A/init.S over B/init.S as the rename source of C/init.S.

About the code structure, I think the very early draft of rename detector did not do the full matrix, but iterated over dst to see if there is a good src for it, picked the best src that is above the threshold, and went on to next dst, like this:

	for (dst in dst candidates) {
        	best_src = NULL;
                best_score = minimum_score;
                for (src in src candidates) {
                	score = similarity(dst, src);
                        if (score > best_score)
                            best_src = src;
		}
		if (best_src) {
			match dst with src;
		}
	}

This was restructured in the current "full matrix first" form before the rename detection logic first hit your tree, and I do not think it was shown in the field to perform worse than the full matrix version.

We could do the current full matrix that does not take basename similarity nor what other renames were detected first, and then use that matrix result in order to primarily define the order of dst candidates to process and run the above loop. At that point, similarity between dst and src does not need to be recomputed fully (the matrix would record it). Instead, we can tweak it to take other renames that already have been detected (this includes "this src has already been used", and "somebody nearby moved to the same directory") and basename similarity to affect which possible src candidate to choose for each dst.