Re: [PATCH] match_pathname(): give fnmatch one char of prefix context

From: Jeff King <peff@peff.net>
Date: Oct 26, 2025, 15:26 UTC
Message-ID: <20251026152614.GB2095501@coredump.intra.peff.net>
In-Reply-To: <xmqq7bwltlb8.fsf@gitster.g>

On Thu, Oct 23, 2025 at 01:28:11PM -0700, Junio C Hamano wrote:

Show 6 quoted lines

> > Subject: match_pathname(): give fnmatch one char of prefix context
> >
> > In match_pathname(), which we use for matching .gitignore and
> > .gitattribute patterns, we are comparing paths with with fnmatch
> 
> "with with" -> "with".

Thanks, will fix.

Show 5 quoted lines

> > My suspicion is that most of the improvement comes from (1), and it
> > would be very easy to retain that case and get rid of (2). But I haven't
> > done any measuring.
> 
> The above matches my intuition as well.

I poked at performance a bit more, but it was long so I put it into a separate email. My findings are that yes, this optimization is very measurable, and that my proposed patch does not hurt anything.

Show 19 quoted lines

> > @@ -1360,6 +1360,13 @@ int match_pathname(const char *pathname, int pathlen,
> >  
> >  		if (fspathncmp(pattern, name, prefix))
> >  			return 0;
> > +
> > +		/*
> > +		 * Retain one character of the prefix to
> > +		 * pass to fnmatch, which lets it distinguish
> > +		 * the start of a directory component correctly.
> > +		 */
> > +		prefix--;
> >  		pattern += prefix;
> >  		patternlen -= prefix;
> >  		name    += prefix;
> 
> So, checking pattern "fo*o/bar" against "foo/bar", we'd use
> "o*o/bar" to match "oo/bar", which is not necessary but our
> conjecture is that feeding shorter fnmatch() is not buying
> us much, which justifies this change.

Yeah. It turns out it _does_ buy us something (at least in some corner cases), but pushing one extra char onto fnmatch is not a big deal.

Show 20 quoted lines

> If not, we could do a more targetted pessimization, perhaps like
> this, ...
> 
>         /* the non-wildcard prefix does not match? */ 
> 	if (fspathncmp(pattern, name, prefix))
> 		return 0;
> 
> 	/* the non-wildcard prefix is the whole thing? */
> 	if (namelen == prefix && patternlen == prefix)
> 		return 1;
> 
> 	/* avoid making foo**/bar match foobar */
> 	if (3 <= prefix && memcmp(pattern, "**/", 3)
> 		prefix--;
> 	pattern += prefix;
> 	patternlen -= prefix;
> 	name += prefix;
> 	namelen -= prefix;
> 
> ... but that is even more specific hack than yours.

Yeah, I think that would also work. Mostly I would worry that there are other cases besides a raw "**/" which causes similar problems, but I could not think of any. Passing in a single char of context seemed like an easy but general fix.

I also wonder how expensive that memcmp() is. ;) Obviously not very, but if the point is that we are trying to save fnmatch from looking at that one extra character, we already pinching pennies in a mostly un-measurable way.

Show 12 quoted lines

> > @@ -1370,7 +1377,7 @@ int match_pathname(const char *pathname, int pathlen,
> >  		 * then our prefix match is all we need; we
> >  		 * do not need to call fnmatch at all.
> >  		 */
> > -		if (!patternlen && !namelen)
> > +		if (patternlen == 1 && namelen == 1)
> >  			return 1;
> >  	}
> 
> In any case, I do prefer doing this "our non-wildcard part matched
> the whole thing, so let's return true" before stripping matching
> prefix from the pattern and the name (like I showed earlier).

Me too. I wrote it a few different ways before ending up with the "== 1", just because it made the diff smaller. But let me do it as two steps, which I think will make it all more clear.

-Peff