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

[Tom Grennan <tmgrennan@gmail.com>]

On Sat, Feb 11, 2012 at 12:06:56AM -0800, Junio C Hamano wrote:
>Tom Grennan <tmgrennan@gmail.com> writes:
>
>> +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).

Yes, I should have stated that this emphasized containment over
efficiency.  If instead we stipulate that the caller must list exclusion
patterns before others, this could simply be:

int match_pattern(const char **patterns, const char *refname)
{
	if (*patterns)
		return 1;
	for (; *patterns && **patterns == '!'; patterns++)
		if (!fnmatch(*patterns+1, refname, 0))
			return 0;
	for (; *patterns; patterns++)
		if (!fnmatch(*patterns, refname, 0))
			return 1;
	return 0;
}

Of course I'd add a with_exclusions_first() before the
respective ref iterator.

-- 
TomG