Re: [PATCHv2 1/4] refs: add common refname_match_patterns()

From: Junio C Hamano <gitster@pobox.com>
Date: Feb 11, 2012, 08:06 UTC
Message-ID: <7vpqdln68v.fsf@alter.siamese.dyndns.org>
In-Reply-To: <1328926618-17167-2-git-send-email-tmgrennan@gmail.com>

Tom Grennan <tmgrennan@gmail.com> writes:

Show 13 quoted lines

> +int refname_match_patterns(const char **patterns, const char *refname)
> +{
> +	int given_match_pattern = 0, had_match = 0;
> +
> +	for (; *patterns; patterns++)
> +		if (**patterns != '!') {
> +			given_match_pattern = 1;
> +			if (!fnmatch(*patterns, refname, 0))
> +				had_match = 1;
> +		} else if (!fnmatch(*patterns+1, refname, 0))
> +			return 0;
> +	return given_match_pattern ? had_match : 1;
> +}

This, while its semantics seem sane, is highly inefficient when you have many patterns, and you will be calling this to filter dozens of refs. And it can trivially improved by first pre-parsing the pattern[] array.

 * If you know the patterns do not have any negative entry, you can return
   true upon seeing the first match. Because you do not pre-parse the
   pattern[] array, this loop does not know if there is any negative one,
   and has to scan it always all the way.

 * If you arrange the pattern[] array so that it has negative ones early,
   again, you can return false upon seeing the first hit with a negative
   one. If your input has negative ones at the end, the loop ends up
   scanning all the way, noting the positive matches, only to discard upon
   seeing the negative match at the end.

That is why I said Nguyen's idea of reusing pathspec matching logic somewhat attractive, even though I think it has downsides (the exact matching logic for pathspec is more similar to that of for-each-ref and very different from branch/tag).