Re: [PATCH 4/6] copy vs rename detection: avoid unnecessary O(n*m) loops

[Junio C Hamano <gitster@pobox.com>]

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

> @@ -2640,27 +2640,21 @@ static void diff_resolve_rename_copy(void)
>  		 * either in-place edit or rename/copy edit.
>  		 */
>  		else if (DIFF_PAIR_RENAME(p)) {
> +			/*
> +			 * A rename might have re-connected a broken
> +			 * pair up, causing the pathnames to be the
> +			 * same again. If so, that's not a rename at
> +			 * all, just a modification..
> +			 *
> +			 * Otherwise, see if this source was used for
> +			 * multiple renames, in which case we decrement
> +			 * the count, and call it a copy.
>  			 */
> +			if (!strcmp(p->one->path, p->two->path))
> +				p->status = DIFF_STATUS_MODIFIED;
> +			else if (--p->one->rename_used > 0)
>  				p->status = DIFF_STATUS_COPIED;
> +			else
>  				p->status = DIFF_STATUS_RENAMED;
>  		}
>  		else if (hashcmp(p->one->sha1, p->two->sha1) ||

The interaction between the above and ...

> @@ -338,15 +320,25 @@ void diffcore_rename(struct diff_options *options)
>  				locate_rename_dst(p->two, 1);
>  		}
>  		else if (!DIFF_FILE_VALID(p->two)) {
> +			/*
> +			 * If the source is a broken "delete", and
>  			 * they did not really want to get broken,
>  			 * that means the source actually stays.
> +			 * So we increment the "rename_used" score
> +			 * by one, to indicate ourselves as a user
> +			 */
> +			if (p->broken_pair && !p->score)
> +				p->one->rename_used++;
> +			register_rename_src(p->one, p->score);
> +		}
> +		else if (detect_rename == DIFF_DETECT_COPY) {
> +			/*
> +			 * Increment the "rename_used" score by
> +			 * one, to indicate ourselves as a user.
>  			 */
> +			p->one->rename_used++;
> +			register_rename_src(p->one, p->score);
>  		}
>  	}
>  	if (rename_dst_nr == 0 || rename_src_nr == 0)
>  		goto cleanup; /* nothing to do */

... this part feels a bit too subtle for a still-jet-lagged
brain to grok.  I wonder what happens if the preimage of a
broken pair is used as the rename source for more than two
postimages.