threads / patch / 31812

patchexclude: fix a bug in prefix comparison optimization

Subject: [PATCH] exclude: fix a bug in prefix comparison optimization

## tl;dr

5 messages between Oct 14, 2012 and Oct 15, 2012. Diffs are folded; open one to read it.

replies: 4people: 2as markdown or json

Nguyễn Thái Ngọc Duy· Oct 14, 2012, 11:35 UTC · lore

When "namelen" becomes zero at this stage, we have matched the fixed part, but whether it actually matches the pattern still depends on the pattern in "exclude". As demonstrated in t3001, path "three/a.3" exists and it matches the "three/a.3" part in pattern "three/a.3[abc]", but that does not mean a true match.

Don't be too optimistic and let fnmatch() do the job.
Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@gmail.com>
---
 dir.c                              | 2 +-
 t/t3001-ls-files-others-exclude.sh | 6 ++++++
 2 files changed, 7 insertions(+), 1 deletion(-)
Show changes to 2 files +7 −1

dir.c, t/t3001-ls-files-others-exclude.sh

diff --git a/dir.c b/dir.c
index 4868339..90bf3a4 100644
--- a/dir.c
+++ b/dir.c
@@ -575,7 +575,7 @@ int excluded_from_list(const char *pathname,
 			namelen -= prefix;
 		}
 
-		if (!namelen || !fnmatch_icase(exclude, name, FNM_PATHNAME))
+		if (!fnmatch_icase(exclude, name, FNM_PATHNAME))
 			return to_exclude;
 	}
 	return -1; /* undecided */
diff --git a/t/t3001-ls-files-others-exclude.sh b/t/t3001-ls-files-others-exclude.sh
index c8fe978..dc2f045 100755
--- a/t/t3001-ls-files-others-exclude.sh
+++ b/t/t3001-ls-files-others-exclude.sh
@@ -214,4 +214,10 @@ test_expect_success 'subdirectory ignore (l1)' '
 	test_cmp expect actual
 '
 
+test_expect_success 'pattern matches prefix completely' '
+	: >expect &&
+	git ls-files -i -o --exclude "/three/a.3[abc]" >actual &&
+	test_cmp expect actual
+'
+
 test_done

-- 
1.8.0.rc2.11.g2b79d01
Junio C Hamano· Oct 14, 2012, 17:36 UTC · re: Nguyễn Thái Ngọc Duy · lore

Re: [PATCH] exclude: fix a bug in prefix comparison optimization

Nguyễn Thái Ngọc Duy <pclouds@gmail.com> writes:
Show 7 quoted lines
> When "namelen" becomes zero at this stage, we have matched the fixed
> part, but whether it actually matches the pattern still depends on the
> pattern in "exclude". As demonstrated in t3001, path "three/a.3"
> exists and it matches the "three/a.3" part in pattern "three/a.3[abc]",
> but that does not mean a true match.
>
> Don't be too optimistic and let fnmatch() do the job.

Yeah, the existing code is correct _only_ if the pattern part can match an empty string (e.g. "three/a.3*") and this is a correct fix.

With your "teach attr.c match the same optimization as dir.c" series, you would need something like this

Show changes to diff +1 −1
diff --git i/attr.c w/attr.c
index 6d39406..528e935 100644
--- i/attr.c
+++ w/attr.c
@@ -710,7 +710,7 @@ static int path_matches(const char *pathname, int pathlen,
 	 * if the non-wildcard part is longer than the remaining
 	 * pathname, surely it cannot match.
 	 */
-	if (!namelen || prefix > namelen)
+	if (prefix > namelen)
 		return 0;
 	if (baselen != 0)
 		baselen++;

Comparing the corresponding code in dir.c, there is no "compare the
literal prefix part with strcmp() before doing the fnmatch()"
optimization.  Intended?

(warning: I haven't had my caffeine yet)
Junio C Hamano· Oct 14, 2012, 18:25 UTC · re: Junio C Hamano · lore

Re: [PATCH] exclude: fix a bug in prefix comparison optimization

Junio C Hamano <gitster@pobox.com> writes:
Show 5 quoted lines
> Comparing the corresponding code in dir.c, there is no "compare the
> literal prefix part with strcmp() before doing the fnmatch()"
> optimization.  Intended?
>
> (warning: I haven't had my caffeine yet)
And it turns out that at the point I wrote the response, I still had
the attr-match-optim-more updates to be read in my mailbox ;-)
Nguyen Thai Ngoc Duy· Oct 15, 2012, 04:09 UTC · re: Junio C Hamano · lore

Re: [PATCH] exclude: fix a bug in prefix comparison optimization

On Mon, Oct 15, 2012 at 12:36 AM, Junio C Hamano <gitster@pobox.com> wrote:
Show 16 quoted lines
> With your "teach attr.c match the same optimization as dir.c"
> series, you would need something like this
>
> diff --git i/attr.c w/attr.c
> index 6d39406..528e935 100644
> --- i/attr.c
> +++ w/attr.c
> @@ -710,7 +710,7 @@ static int path_matches(const char *pathname, int pathlen,
>          * if the non-wildcard part is longer than the remaining
>          * pathname, surely it cannot match.
>          */
> -       if (!namelen || prefix > namelen)
> +       if (prefix > namelen)
>                 return 0;
>         if (baselen != 0)
>                 baselen++;

If there's still a chance to rewrite attr-match-optim-more series (I see it's in next now), then I could reorder the patches so that excluded_from_list code refactoring goes first, then rewrite "teach attr.c match... as dir.c" patch makes use of the new functions without code duplication. The end result would be the same, except that we won't see this bug in attr.c's history. Not much value so if it may take a lot of your time, don't bother. -- Duy

Junio C Hamano· Oct 15, 2012, 04:28 UTC · re: Nguyen Thai Ngoc Duy · lore

Re: [PATCH] exclude: fix a bug in prefix comparison optimization

Nguyen Thai Ngoc Duy <pclouds@gmail.com> writes:
Show 25 quoted lines
> On Mon, Oct 15, 2012 at 12:36 AM, Junio C Hamano <gitster@pobox.com> wrote:
>> With your "teach attr.c match the same optimization as dir.c"
>> series, you would need something like this
>>
>> diff --git i/attr.c w/attr.c
>> index 6d39406..528e935 100644
>> --- i/attr.c
>> +++ w/attr.c
>> @@ -710,7 +710,7 @@ static int path_matches(const char *pathname, int pathlen,
>>          * if the non-wildcard part is longer than the remaining
>>          * pathname, surely it cannot match.
>>          */
>> -       if (!namelen || prefix > namelen)
>> +       if (prefix > namelen)
>>                 return 0;
>>         if (baselen != 0)
>>                 baselen++;
>
> If there's still a chance to rewrite attr-match-optim-more series (I
> see it's in next now), then I could reorder the patches so that
> excluded_from_list code refactoring goes first, then rewrite "teach
> attr.c match... as dir.c" patch makes use of the new functions without
> code duplication. The end result would be the same, except that we
> won't see this bug in attr.c's history. Not much value so if it may
> take a lot of your time, don't bother.

Actually it started to become nuisance to deal with conflicts among as/check-ignore and the attr/dir/wildmatch series, and I've been wondering if it makes sense to eject all of these out of 'next' (as they won't advance beyond 'next' until the next release anyway).

So please go ahead and reroll the whole thing if you think the end result would be a history with better organization.

← back to recent threads