Re: [PATCH] fetch: avoid quadratic loop checking for updated submodules

From: Junio C Hamano <gitster@pobox.com>
Date: Sep 12, 2011, 21:25 UTC
Message-ID: <7vr53l5u7h.fsf@alter.siamese.dyndns.org>
In-Reply-To: <20110912195652.GA27850@sigill.intra.peff.net>

Jeff King <peff@peff.net> writes:

Show 8 quoted lines

> +struct argv_array {
> +	const char **argv;
> +	unsigned int argc;
> +	unsigned int alloc;
> +};
> +
> ...
> +static void calculate_changed_submodule_paths() {

Locally fixed while queueing; no need to resend:

        static void calculate_changed_submodule_paths(void)
        {

Show 17 quoted lines

>  	struct rev_info rev;
>  	struct commit *commit;
> -	const char *argv[] = {NULL, NULL, "--not", "--all", NULL};
> -	int argc = ARRAY_SIZE(argv) - 1;
> +	struct argv_array argv;
>  
>  	init_revisions(&rev, NULL);
> -	argv[1] = xstrdup(sha1_to_hex(new_sha1));
> -	setup_revisions(argc, argv, &rev, NULL);
> +	init_argv(&argv);
> +	push_argv(&argv, "--"); /* argv[0] program name */
> +	sha1_array_for_each_unique(&ref_tips_after_fetch,
> +				   add_sha1_to_argv, &argv);
> +	push_argv(&argv, "--not");
> +	sha1_array_for_each_unique(&ref_tips_before_fetch,
> +				   add_sha1_to_argv, &argv);
> +	setup_revisions(argv.argc, argv.argv, &rev, NULL);

I initially thought "eh, what if we have very many refs that may not fit on the command line", but this is running the internal rev-list, so there is no such issue.

I however have to wonder if the use of object flags done by this revision walking need to be cleared to prevent them from interfering with the ancestry walking done in find_common(). Shouldn't this be done in a subprocess "rev-list" that is fed these positive and negative refs from its standard input?

The patch does not make things worse in any sense, so I'll queue it but I have this suspicion that fetching in a superproject that uses submodules may be broken in the versions of Git with these internal revision walking.