Re: [PATCH 10/21] tree_entry_interesting(): fix depth limit with overlapping pathspecs

From: Nguyen Thai Ngoc Duy <pclouds@gmail.com>
Date: Dec 18, 2010, 03:37 UTC
Message-ID: <AANLkTik+DaUrh99qs4T-Pm_+3Oq499L_NtP6Xcht1wfH@mail.gmail.com>
In-Reply-To: <7vmxo5l2g4.fsf@alter.siamese.dyndns.org>

2010/12/17 Junio C Hamano <gitster@pobox.com>:

Show 20 quoted lines

> One possible definition of interaction between limit and wildcard may be
> to count the number of slashes in the part of the path that matches the
> wildcarded part of the pathspec, add the number of path components
> appended due to the leading directory match, and then subtract the number
> of literal slashes in the wildcarded part of the pattern from the above,
> and declare that a match is found if the difference is less than the
> limit.
>
> E.g. a pathspec element "a/*/x" would match "a/b/c/x", "a/b/c/d/e/x",
> "a/b/x/y" and "a/b/x/y/z" without limit, and with the limit of 1:
>
>    a/b/c/x        matches ('*' expands to "b/c")
>    a/b/c/d/e/x    no ('*' has to expand to "c/d/e" and needs 2 levels)
>    a/b/x/y        matches ('*' expands to "b" costing zero, "/y" needs 1)
>    a/b/x/y/z      does not match
>
> Another definition could be to count _only_ the part that is appended by
> recursion (i.e. we do not count how many slashes has to match '*' in the
> above examples), and as the option is called --depth, it might make more
> sense.

So with the above example, "a/" won't be counted. Depth limit of 0 or 1 will result in no matches. Depth limit of 2 will result in a/b/c/x and a/b/x/y, correct?

I prefer this definition to the former. It sounds simpler to understand and use, also less computation. But I can implement both :-) We can mark what matching strategy we would use in struct pathspec. Hmm.. I'm not much help in figuring out which one makes more sense.

Another thing, I don't know if anybody would need it. Should we support depth limit per pathspec, so "a/*/x" can have depth limit of 2, but "*.c" has depth limit of 1..For one thing, his may help keeping current's git-grep depth limit behavior if depth limit can also be applied to wildcard pathspecs by setting depth limit for wildcard pathspecs to -1. Exposing depth limit per pathspec to users is another matter.

> In either case, I am not sure if "if it matches the longest pathspec, we
> have the answer without looking at shorter ones" would be a good rule to
> use.

As long as the rule of matching is "if any of these pathspecs is matched, we have a match", then pathspec order should not matter (without depth limit). Matching decision of one pathspec does not affect the others. Depth limit is the first one breaking the last sentence. And because pathspec order does not matter before depth limit introduction, it should not cause any regression when depth limit requires pathspecs in certain order. That's how I thought when I decided to sort pathspecs.

Wildcard pathspecs are handled in a completely different path (even with depth limit in either way you described). Overlapping is no issue to wildcard pathspecs, we always need full pathspec to call fnmatch() (unless you implied some early cut optmization that I don't see). Therefore pathspec order is no issue.

Even when I introduce negative pathspec, it would be actually negative prefix and go the same route as current depth limit impl (it also has the same overlapping pathspec issue). Negative wildcard pathspecs would blow my mind.

-- 
Duy