On Sat, Feb 11, 2012 at 03:43:34PM -0800, Junio C Hamano wrote:
>Tom Grennan <tmgrennan@xxxxxxxxx> writes:
>
>> 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:
>
>No.
>
>You have to pre-parse and rearrange the pattern[] list *only once* before
>matching them against dozens of refs, so instead of forcing the callers do
>anything funky, you give a function that gets a pattern[] list and returns
>something that can be efficiently used by the match_pattern() function,
>and have the caller pass that thing, not the original pattern[] list, to
>the match_pattern() function.
Hmm, I'm not communicating very well; this is exactly what I meant by,
>> Of course I'd add a with_exclusions_first() before the
>> respective ref iterator.
--
TomG
--- Begin Message ---
On Sat, Feb 11, 2012 at 12:06:56AM -0800, Junio C Hamano wrote:
>Tom Grennan <tmgrennan@xxxxxxxxx> 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
--- End Message ---