Re: [PATCH 2/3] Move pathspec validation into interactive_add

From: Junio C Hamano <gitster@pobox.com>
Date: Nov 24, 2007, 22:34 UTC
Message-ID: <7vtznbp91f.fsf@gitster.siamese.dyndns.org>
In-Reply-To: <4D81F973-8951-458A-958D-E24C826CA548@wincent.com>

Wincent Colaiuta <win@wincent.com> writes:

Show 15 quoted lines

> El 24/11/2007, a las 20:15, Junio C Hamano escribió:
>
>> Wincent Colaiuta <win@wincent.com> writes:
>>
>>> Instead of throwing away the return status of pathspec_match() I am
>>> keeping it, and any successful match breaks out of the loop early.
>>
>> Leaving it early before checking if all the given pathspecs are
>> used defeats the whole "error-unmatch" business, doesn't it?
>
> No, I probably didn't explain that clearly enough... If you look at
> the patch, I break out of the *inner* loop the first time a particular
> pattern matches. Then I move on to the next pattern, and any single
> invalid pattern will be enough to provide the "error-unmatch"
> indication.

Heh, I missed that the code was doing something so stupid ;-).

The helper function pathspec_match() takes a single path and a set of pathspecs (NULL terminated), and says if the path is covered with that set, while recording which one of the pathspecs caused the match in the ps_matched array.

You are checking first with the full set of patterns, then the full set minus the first pattern, and then the full set minus the first two patterns, and so on. No wonder it is inefficient.

Why are you trying to micro-optimize this part in the first place? Have you benchmarked and determined that iterating over full cache is the bottleneck?

In order to prove that there is a pathspec (or more) that does not match anything in the cache, you need to interate over the whole cache at least once. The only case you can short-cut is when you can tell that all of them have been used before you iterated over all cache entries.

So lose that silly outer loop, and replace the inner function with something like this:

        static int validate_pathspec(const char *prefix, const char **pattern)
        {
                int i, ret = 0, num_patterns;
                char *m;

                if (!pattern || !*pattern)
                        return 0;

                for (num_patterns = 0; pattern[num_patterns]; num_patterns++)
                        ;
                m = xcalloc(1, num_patterns + 1);
                for (i = 0; i < active_nr; i++) {
                        struct cache_entry *ce = active_cache[i];

                        if (pathspec_match(pattern, m, ce->name, 0)) {
                                /*
                                 * You could micro optimize by leaving
                                 * the loop early when you notice that all
				 * patterns are used.
				 *
                                 * if (strlen(m) == num_patterns)
                                 * 	goto ok;
				 *
                                 */ 
				; /* nothing */
			}
                }
                report_path_error(m, pattern, prefix ? strlen(prefix) : 0);
        ok:
                free(m);
                return ret;
        }

My gut feeling is that the micro-optimization is not worth it here, but I didn't try. I think without the micro-optimization the above is the same as I gave you earlier.