[PATCH] dir: find common prefix among positive pathspecs

[PATCH] dir: find common prefix among positive pathspecs

[Yannik Tausch]

common_prefix_len() skips exclude pathspec items, but uses n == 0 to
identify the initial item and items[0] as the comparison source. When
an exclude item comes first, the function returns zero even when all
positive pathspecs share a directory.

Track the first positive item explicitly. Return its match and the
common prefix length together so that common_prefix() and
fill_directory() use the correct string. Add a unit test with an
unrelated exclude before two positive pathspecs that share a directory.

Signed-off-by: Yannik Tausch <dev@ytausch.de>
---

This patch is based on https://lore.kernel.org/git/0CA8678D-0540-4A2E-B314-B9BEB04E2BF5@ytausch.de/T/#u.

 dir.c                | 51 +++++++++++++++++++++++++++-----------------
 t/unit-tests/u-dir.c | 28 ++++++++++++++++++++++++
 2 files changed, 60 insertions(+), 19 deletions(-)

diff --git a/dir.c b/dir.c
index 7072715389..441c1795a1 100644
--- a/dir.c
+++ b/dir.c
@@ -212,9 +212,19 @@ static int fnmatch_icase_mem(const char *pattern, int patternlen,
 	return match_status;
 }
 
-static size_t common_prefix_len(const struct pathspec *pathspec)
+struct pathspec_prefix {
+	const char *match;
+	size_t len;
+};
+
+/*
+ * Find the common prefix of positive pathspec items. The returned match
+ * points into the first positive item and is not NUL-terminated at len.
+ */
+static struct pathspec_prefix find_common_prefix(const struct pathspec *pathspec)
 {
-	int n;
+	struct pathspec_prefix prefix = { 0 };
+	int n, first = -1;
 	size_t max = 0;
 
 	/*
@@ -237,44 +247,47 @@ static size_t common_prefix_len(const struct pathspec *pathspec)
 		size_t i = 0, len = 0, item_len;
 		if (pathspec->items[n].magic & PATHSPEC_EXCLUDE)
 			continue;
+		if (first < 0)
+			first = n;
 		if (pathspec->items[n].magic & PATHSPEC_ICASE)
 			item_len = pathspec->items[n].prefix;
 		else
 			item_len = pathspec->items[n].nowildcard_len;
-		while (i < item_len && (n == 0 || i < max)) {
+		while (i < item_len && (n == first || i < max)) {
 			char c = pathspec->items[n].match[i];
-			if (c != pathspec->items[0].match[i])
+			if (c != pathspec->items[first].match[i])
 				break;
 			if (c == '/')
 				len = i + 1;
 			i++;
 		}
-		if (n == 0 || len < max) {
+		if (n == first || len < max) {
 			max = len;
 			if (!max)
 				break;
 		}
 	}
-	return max;
+	prefix.match = first < 0 ? NULL : pathspec->items[first].match;
+	prefix.len = max;
+	return prefix;
 }
 
 /*
- * Returns a copy of the longest leading path common among all
+ * Returns a copy of the longest leading path common among all positive
  * pathspecs.
  */
 char *common_prefix(const struct pathspec *pathspec)
 {
-	unsigned long len = common_prefix_len(pathspec);
+	struct pathspec_prefix prefix = find_common_prefix(pathspec);
 
-	return len ? xmemdupz(pathspec->items[0].match, len) : NULL;
+	return prefix.len ? xmemdupz(prefix.match, prefix.len) : NULL;
 }
 
 int fill_directory(struct dir_struct *dir,
 		   struct index_state *istate,
 		   const struct pathspec *pathspec)
 {
-	const char *prefix;
-	size_t prefix_len;
+	struct pathspec_prefix prefix;
 
 	unsigned exclusive_flags = DIR_SHOW_IGNORED | DIR_SHOW_IGNORED_TOO;
 	if ((dir->flags & exclusive_flags) == exclusive_flags)
@@ -284,13 +297,13 @@ int fill_directory(struct dir_struct *dir,
 	 * Calculate common prefix for the pathspec, and
 	 * use that to optimize the directory walk
 	 */
-	prefix_len = common_prefix_len(pathspec);
-	prefix = prefix_len ? pathspec->items[0].match : "";
+	prefix = find_common_prefix(pathspec);
 
 	/* Read the directory and prune it */
-	read_directory(dir, istate, prefix, prefix_len, pathspec);
+	read_directory(dir, istate, prefix.len ? prefix.match : "",
+		       prefix.len, pathspec);
 
-	return prefix_len;
+	return prefix.len;
 }
 
 int within_depth(const char *name, int namelen,
@@ -394,7 +407,7 @@ static int match_pathspec_item(struct index_state *istate,
 
 	/*
 	 * The normal call pattern is:
-	 * 1. prefix = common_prefix_len(ps);
+	 * 1. prefix = find_common_prefix(ps).len;
 	 * 2. prune something, or fill_directory
 	 * 3. match_pathspec()
 	 *
@@ -411,11 +424,11 @@ static int match_pathspec_item(struct index_state *istate,
 	 * prefix part when :(icase) is involved. We do exact
 	 * comparison ourselves.
 	 *
-	 * Normally the caller (common_prefix_len() in fact) does
+	 * Normally the caller (find_common_prefix() in fact) does
 	 * _exact_ matching on name[-prefix+1..-1] and we do not need
 	 * to check that part. Be defensive and check it anyway, in
-	 * case common_prefix_len is changed, or a new caller is
-	 * introduced that does not use common_prefix_len.
+	 * case find_common_prefix() is changed, or a new caller is
+	 * introduced that does not use find_common_prefix().
 	 *
 	 * If the penalty turns out too high when prefix is really
 	 * long, maybe change it to
diff --git a/t/unit-tests/u-dir.c b/t/unit-tests/u-dir.c
index 2d0adaa39e..8b558e0391 100644
--- a/t/unit-tests/u-dir.c
+++ b/t/unit-tests/u-dir.c
@@ -45,3 +45,31 @@ void test_dir__within_depth(void)
 
 
 }
+
+void test_dir__common_prefix_skips_excluded_pathspecs(void)
+{
+	struct pathspec_item items[] = {
+		{
+			.match = "unrelated/path",
+			.magic = PATHSPEC_EXCLUDE,
+			.nowildcard_len = 14,
+		},
+		{
+			.match = "foo/bar",
+			.nowildcard_len = 7,
+		},
+		{
+			.match = "foo/baz",
+			.nowildcard_len = 7,
+		},
+	};
+	struct pathspec pathspec = {
+		.nr = ARRAY_SIZE(items),
+		.magic = PATHSPEC_EXCLUDE,
+		.items = items,
+	};
+	char *prefix = common_prefix(&pathspec);
+
+	cl_assert_equal_s(prefix, "foo/");
+	free(prefix);
+}

base-commit: 1630431f326e15fcde608827b5ff38422528eb59
prerequisite-patch-id: 256750f07ff447732869d1aadde2f1050e7bb169
-- 
2.55.0

Re: [PATCH] dir: find common prefix among positive pathspecs

[Junio C Hamano]

Yannik Tausch <dev@ytausch.de> writes:

> common_prefix_len() skips exclude pathspec items, but uses n == 0 to
> identify the initial item and items[0] as the comparison source. When
> an exclude item comes first, the function returns zero even when all
> positive pathspecs share a directory.
>
> Track the first positive item explicitly. Return its match and the
> common prefix length together so that common_prefix() and
> fill_directory() use the correct string. Add a unit test with an
> unrelated exclude before two positive pathspecs that share a directory.
>
> Signed-off-by: Yannik Tausch <dev@ytausch.de>
> ---
>
> This patch is based on https://lore.kernel.org/git/0CA8678D-0540-4A2E-B314-B9BEB04E2BF5@ytausch.de/T/#u.

I am not sure what you mean.  Do you mean that the other one should
have been marked as [PATCH 1/2] and this one [PATCH 2/2]?  The way
we use the phrase "based on" does not exactly match that situation.
It is more like "This patch applies on top of the other one", or
"This patch depends on the other one."

> -static size_t common_prefix_len(const struct pathspec *pathspec)
> +struct pathspec_prefix {
> +	const char *match;
> +	size_t len;
> +};
> +
> +/*
> + * Find the common prefix of positive pathspec items. The returned match
> + * points into the first positive item and is not NUL-terminated at len.
> + */
> +static struct pathspec_prefix find_common_prefix(const struct pathspec *pathspec)

Our norm in C is not to pass structures by value either as parameter
of as return value, unless there is a very good reason to do so.

Since we can easily use

	const char *common_prefix(const sturct pathspec *pathspec, size_t *len);

to return .match and store the length in *len when we return, we
cannot say that this case has a very good reason to use a structure
passed by value.

Actually, I have a feeling that we do not want find_common_prefix()
helper.  Instead perhaps

    static size_t common_prefix_len(const struct pathspec *pathspec,
				    const char **matched_prefix)

may be an alternative that is easier to work with.  Because the
existing callers assume that pathspec->items[0].match is where they
can grab the common prefix from, they should look like

	len = common_prefix_len(pathspec);
	... use the first len bytes of pathspec->items[0].match[] ...

They want to be told to do this instead now:

	const char *common_prefix;

	len = common_prefix_len(pathspec, &common_prefix);
	... use the first len bytes of common_prefix[] ...

In "use the first len bytes" logic they already have, they know not
to memdup when len == 0 (and ignore pathspec->items[0].match[] in
that case), and they know they need to memdup if they want to have
their own copies, etc., so the changes to them can be kept to the
minimum.

> +	prefix.match = first < 0 ? NULL : pathspec->items[first].match;
> +	prefix.len = max;
> +	return prefix;

So instead of these three lines, your return sequence would become

	*matched_prefix = first < 0 ? NULL : pathspec->items[first].match;
	return max;

If there is no positive element in the given pathspec (by the way,
"pathspec" refers to the whole set, and each element in it may be
either positive or negative, so "positive pathspec(s)" is a
misnomer),  the loop never touches first or max, so when the loop
exits, we won't have "match" and "len" is 0.  Your changes in the
loop to avoid assuming [0] is positive element all look correct.

Re: [PATCH] dir: find common prefix among positive pathspecs

[Yannik Tausch]

Hi,

> Junio C Hamano <gitster@pobox.com> writes:

> I am not sure what you mean.  Do you mean that the other one should
> have been marked as [PATCH 1/2] and this one [PATCH 2/2]?  The way
> we use the phrase "based on" does not exactly match that situation.
> It is more like "This patch applies on top of the other one", or
> "This patch depends on the other one."

I wanted to indicate that this patch depends on the other one, but they can reviewed
independently. This is because the other patch eliminates a bug that leads to wrong 
input data for the code segments I change in this one.

Re-reading your contribution docs, I understand that this might indeed be better
submitted as a patch series. I will resubmit as patch series v2.

>> -static size_t common_prefix_len(const struct pathspec *pathspec)
>> +struct pathspec_prefix {
>> + const char *match;
>> + size_t len;
>> +};
>> +
>> +/*
>> + * Find the common prefix of positive pathspec items. The returned match
>> + * points into the first positive item and is not NUL-terminated at len.
>> + */
>> +static struct pathspec_prefix find_common_prefix(const struct pathspec *pathspec)
> 
> Our norm in C is not to pass structures by value either as parameter
> of as return value, unless there is a very good reason to do so.
> 
> Since we can easily use
> 
> const char *common_prefix(const sturct pathspec *pathspec, size_t *len);
> 
> to return .match and store the length in *len when we return, we
> cannot say that this case has a very good reason to use a structure
> passed by value.

Fair if that’s your convention, note that in other languages I usually write, - I’m probably
telling you nothing new - we usually prefer clear separation of input and output values,
which is, IMO, cleaner when returning a struct and makes this version more readable.

> Actually, I have a feeling that we do not want find_common_prefix()
> helper.  Instead perhaps
> 
>    static size_t common_prefix_len(const struct pathspec *pathspec,
>     const char **matched_prefix)
> 
> may be an alternative that is easier to work with.  Because the
> existing callers assume that pathspec->items[0].match is where they
> can grab the common prefix from, they should look like
> 
> len = common_prefix_len(pathspec);
> ... use the first len bytes of pathspec->items[0].match[] ...
> 
> They want to be told to do this instead now:
> 
> const char *common_prefix;
> 
> len = common_prefix_len(pathspec, &common_prefix);
> ... use the first len bytes of common_prefix[] ...
> 
> In "use the first len bytes" logic they already have, they know not
> to memdup when len == 0 (and ignore pathspec->items[0].match[] in
> that case), and they know they need to memdup if they want to have
> their own copies, etc., so the changes to them can be kept to the
> minimum.
> 
>> + prefix.match = first < 0 ? NULL : pathspec->items[first].match;
>> + prefix.len = max;
>> + return prefix;
> 
> So instead of these three lines, your return sequence would become
> 
> *matched_prefix = first < 0 ? NULL : pathspec->items[first].match;
> return max;
> 
> If there is no positive element in the given pathspec (by the way,
> "pathspec" refers to the whole set, and each element in it may be
> either positive or negative, so "positive pathspec(s)" is a
> misnomer),  the loop never touches first or max, so when the loop
> exits, we won't have "match" and "len" is 0.  Your changes in the
> loop to avoid assuming [0] is positive element all look correct.

I addressed all your comments and will follow up with v2.

Yannik

[PATCH v2 0/2] dir: fix pathspec prefixes with exclusions

[Yannik Tausch]

Pathspec prefix optimization must account for exclude items separately.
The prefix is derived from non-exclude items, so applying it while matching
an exclude item can compare the wrong portions of the paths. Conversely, an
exclude item at the start of the pathspec currently prevents finding a common
prefix among the remaining items.

The first patch matches exclude items against the full pathname. The second
patch finds the common prefix starting with the first non-exclude item and
returns both the prefix length and the string from which it was derived.

Changes since v1:

* Send the changes as a two-patch series in dependency order.
* Return the matched prefix through an output parameter instead of returning
  a structure by value.
* Use "non-exclude pathspec item" terminology and consistent variable names.

Yannik Tausch (2):
  dir: do not apply prefix to negative pathspecs
  dir: find common prefix among non-exclude pathspec items

 dir.c                       | 39 +++++++++++++++++++++----------------
 t/t6132-pathspec-exclude.sh |  9 +++++++++
 t/unit-tests/u-dir.c        | 28 ++++++++++++++++++++++++++
 3 files changed, 59 insertions(+), 17 deletions(-)

Range-diff against v1:
1:  c8a2f1e22e = 1:  c8a2f1e22e dir: do not apply prefix to negative pathspecs
2:  5a179872c1 ! 2:  d0e08fdb96 dir: find common prefix among positive pathspecs
    @@ Metadata
     Author: Yannik Tausch <dev@ytausch.de>
     
      ## Commit message ##
    -    dir: find common prefix among positive pathspecs
    +    dir: find common prefix among non-exclude pathspec items
     
         common_prefix_len() skips exclude pathspec items, but uses n == 0 to
         identify the initial item and items[0] as the comparison source. When
         an exclude item comes first, the function returns zero even when all
    -    positive pathspecs share a directory.
    +    remaining items share a directory.
     
    -    Track the first positive item explicitly. Return its match and the
    -    common prefix length together so that common_prefix() and
    -    fill_directory() use the correct string. Add a unit test with an
    -    unrelated exclude before two positive pathspecs that share a directory.
    +    Track the first non-exclude item explicitly. Return its match through
    +    an output parameter so that common_prefix() and fill_directory() use
    +    the correct string. Add a unit test with an unrelated exclude item
    +    before two non-exclude items that share a directory.
     
         Signed-off-by: Yannik Tausch <dev@ytausch.de>
     
    @@ dir.c: static int fnmatch_icase_mem(const char *pattern, int patternlen,
      }
      
     -static size_t common_prefix_len(const struct pathspec *pathspec)
    -+struct pathspec_prefix {
    -+	const char *match;
    -+	size_t len;
    -+};
    -+
    -+/*
    -+ * Find the common prefix of positive pathspec items. The returned match
    -+ * points into the first positive item and is not NUL-terminated at len.
    -+ */
    -+static struct pathspec_prefix find_common_prefix(const struct pathspec *pathspec)
    ++static size_t common_prefix_len(const struct pathspec *pathspec,
    ++				const char **matched_prefix)
      {
     -	int n;
    -+	struct pathspec_prefix prefix = { 0 };
     +	int n, first = -1;
      	size_t max = 0;
      
    @@ dir.c: static size_t common_prefix_len(const struct pathspec *pathspec)
      				break;
      		}
      	}
    --	return max;
    -+	prefix.match = first < 0 ? NULL : pathspec->items[first].match;
    -+	prefix.len = max;
    -+	return prefix;
    ++	*matched_prefix = first < 0 ? NULL : pathspec->items[first].match;
    + 	return max;
      }
      
      /*
     - * Returns a copy of the longest leading path common among all
    -+ * Returns a copy of the longest leading path common among all positive
    -  * pathspecs.
    +- * pathspecs.
    ++ * Returns a copy of the longest leading path common among all pathspec
    ++ * items that are not excluded.
       */
      char *common_prefix(const struct pathspec *pathspec)
      {
     -	unsigned long len = common_prefix_len(pathspec);
    -+	struct pathspec_prefix prefix = find_common_prefix(pathspec);
    ++	const char *matched_prefix;
    ++	size_t len = common_prefix_len(pathspec, &matched_prefix);
      
     -	return len ? xmemdupz(pathspec->items[0].match, len) : NULL;
    -+	return prefix.len ? xmemdupz(prefix.match, prefix.len) : NULL;
    ++	return len ? xmemdupz(matched_prefix, len) : NULL;
      }
      
      int fill_directory(struct dir_struct *dir,
    @@ dir.c: static size_t common_prefix_len(const struct pathspec *pathspec)
      		   const struct pathspec *pathspec)
      {
     -	const char *prefix;
    --	size_t prefix_len;
    -+	struct pathspec_prefix prefix;
    ++	const char *matched_prefix;
    + 	size_t prefix_len;
      
      	unsigned exclusive_flags = DIR_SHOW_IGNORED | DIR_SHOW_IGNORED_TOO;
    - 	if ((dir->flags & exclusive_flags) == exclusive_flags)
     @@ dir.c: int fill_directory(struct dir_struct *dir,
      	 * Calculate common prefix for the pathspec, and
      	 * use that to optimize the directory walk
      	 */
     -	prefix_len = common_prefix_len(pathspec);
     -	prefix = prefix_len ? pathspec->items[0].match : "";
    -+	prefix = find_common_prefix(pathspec);
    ++	prefix_len = common_prefix_len(pathspec, &matched_prefix);
      
      	/* Read the directory and prune it */
     -	read_directory(dir, istate, prefix, prefix_len, pathspec);
    -+	read_directory(dir, istate, prefix.len ? prefix.match : "",
    -+		       prefix.len, pathspec);
    ++	read_directory(dir, istate, prefix_len ? matched_prefix : "",
    ++		       prefix_len, pathspec);
      
    --	return prefix_len;
    -+	return prefix.len;
    + 	return prefix_len;
      }
    - 
    - int within_depth(const char *name, int namelen,
     @@ dir.c: static int match_pathspec_item(struct index_state *istate,
      
      	/*
      	 * The normal call pattern is:
     -	 * 1. prefix = common_prefix_len(ps);
    -+	 * 1. prefix = find_common_prefix(ps).len;
    ++	 * 1. prefix = common_prefix_len(ps, &matched_prefix);
      	 * 2. prune something, or fill_directory
      	 * 3. match_pathspec()
      	 *
     @@ dir.c: static int match_pathspec_item(struct index_state *istate,
    - 	 * prefix part when :(icase) is involved. We do exact
    - 	 * comparison ourselves.
    - 	 *
    --	 * Normally the caller (common_prefix_len() in fact) does
    -+	 * Normally the caller (find_common_prefix() in fact) does
    + 	 * Normally the caller (common_prefix_len() in fact) does
      	 * _exact_ matching on name[-prefix+1..-1] and we do not need
      	 * to check that part. Be defensive and check it anyway, in
     -	 * case common_prefix_len is changed, or a new caller is
     -	 * introduced that does not use common_prefix_len.
    -+	 * case find_common_prefix() is changed, or a new caller is
    -+	 * introduced that does not use find_common_prefix().
    ++	 * case common_prefix_len() is changed, or a new caller is
    ++	 * introduced that does not use common_prefix_len().
      	 *
      	 * If the penalty turns out too high when prefix is really
      	 * long, maybe change it to
    @@ t/unit-tests/u-dir.c: void test_dir__within_depth(void)
      
      }
     +
    -+void test_dir__common_prefix_skips_excluded_pathspecs(void)
    ++void test_dir__common_prefix_skips_excluded_pathspec_items(void)
     +{
     +	struct pathspec_item items[] = {
     +		{
-- 
2.55.0

[PATCH v2 1/2] dir: do not apply prefix to negative pathspecs

[Yannik Tausch]

common_prefix_len() derives the common prefix solely from positive
pathspecs, skipping those marked with PATHSPEC_EXCLUDE. However,
match_pathspec_with_flags() also passes that prefix when matching the
negative pathspecs.

A negative pathspec may be shorter than the prefix. In that case,
match_pathspec_item() advances item->match beyond its allocation and
subtracts the prefix from item->len, producing a negative matchlen. It
then dereferences the out-of-bounds pointer. If the resulting byte is
not NUL, matchlen is converted to size_t when passed to ps_strncmp(),
which may cause a much larger out-of-bounds read.

The problem can be reproduced with AddressSanitizer:

    make SANITIZE=address CFLAGS="-g -O0" git
    git init test &&
    cd test &&
    DIR=$(printf "a%.0s" {1..150}) &&
    mkdir -p "$DIR" &&
    touch "$DIR/f.txt" &&
    git add -A &&
    git commit -m test &&
    ../git ls-files -- "$DIR/" ":(exclude)xy"

This reports a heap-buffer-overflow. Without AddressSanitizer, the
output may depend on the contents of memory following the negative
pathspec.

Fix the bug by using a zero prefix when matching negative pathspecs.
Add a regression test that combines a positive pathspec with a longer
common prefix and a shorter, unrelated negative pathspec.

Signed-off-by: Yannik Tausch <dev@ytausch.de>
---
 dir.c                       | 2 +-
 t/t6132-pathspec-exclude.sh | 9 +++++++++
 2 files changed, 10 insertions(+), 1 deletion(-)

diff --git a/dir.c b/dir.c
index 95d8a1cce9..7072715389 100644
--- a/dir.c
+++ b/dir.c
@@ -593,7 +593,7 @@ static int match_pathspec_with_flags(struct index_state *istate,
 	if (!(ps->magic & PATHSPEC_EXCLUDE) || !positive)
 		return positive;
 	negative = do_match_pathspec(istate, ps, name, namelen,
-				     prefix, seen,
+				     0, seen,
 				     flags | DO_MATCH_EXCLUDE);
 	return negative ? 0 : positive;
 }
diff --git a/t/t6132-pathspec-exclude.sh b/t/t6132-pathspec-exclude.sh
index 9fdafeb1e9..ad919cc739 100755
--- a/t/t6132-pathspec-exclude.sh
+++ b/t/t6132-pathspec-exclude.sh
@@ -183,6 +183,15 @@ EOF
 	test_cmp expect actual
 '
 
+test_expect_success 'negative pathspec shorter than positive pathspec prefix' '
+	git ls-files -- sub/sub/ ":(exclude)sub2" >actual &&
+	cat <<-\EOF >expect &&
+	sub/sub/file
+	sub/sub/sub/file
+	EOF
+	test_cmp expect actual
+'
+
 test_expect_success 'multiple exclusions' '
 	git ls-files -- ":^*/file2" ":^sub2" >actual &&
 	cat <<-\EOF >expect &&
-- 
2.55.0

[PATCH v2 2/2] dir: find common prefix among non-exclude pathspec items

[Yannik Tausch]

common_prefix_len() skips exclude pathspec items, but uses n == 0 to
identify the initial item and items[0] as the comparison source. When
an exclude item comes first, the function returns zero even when all
remaining items share a directory.

Track the first non-exclude item explicitly. Return its match through
an output parameter so that common_prefix() and fill_directory() use
the correct string. Add a unit test with an unrelated exclude item
before two non-exclude items that share a directory.

Signed-off-by: Yannik Tausch <dev@ytausch.de>
---
 dir.c                | 37 +++++++++++++++++++++----------------
 t/unit-tests/u-dir.c | 28 ++++++++++++++++++++++++++++
 2 files changed, 49 insertions(+), 16 deletions(-)

diff --git a/dir.c b/dir.c
index 7072715389..d896e7be4b 100644
--- a/dir.c
+++ b/dir.c
@@ -212,9 +212,10 @@ static int fnmatch_icase_mem(const char *pattern, int patternlen,
 	return match_status;
 }
 
-static size_t common_prefix_len(const struct pathspec *pathspec)
+static size_t common_prefix_len(const struct pathspec *pathspec,
+				const char **matched_prefix)
 {
-	int n;
+	int n, first = -1;
 	size_t max = 0;
 
 	/*
@@ -237,43 +238,47 @@ static size_t common_prefix_len(const struct pathspec *pathspec)
 		size_t i = 0, len = 0, item_len;
 		if (pathspec->items[n].magic & PATHSPEC_EXCLUDE)
 			continue;
+		if (first < 0)
+			first = n;
 		if (pathspec->items[n].magic & PATHSPEC_ICASE)
 			item_len = pathspec->items[n].prefix;
 		else
 			item_len = pathspec->items[n].nowildcard_len;
-		while (i < item_len && (n == 0 || i < max)) {
+		while (i < item_len && (n == first || i < max)) {
 			char c = pathspec->items[n].match[i];
-			if (c != pathspec->items[0].match[i])
+			if (c != pathspec->items[first].match[i])
 				break;
 			if (c == '/')
 				len = i + 1;
 			i++;
 		}
-		if (n == 0 || len < max) {
+		if (n == first || len < max) {
 			max = len;
 			if (!max)
 				break;
 		}
 	}
+	*matched_prefix = first < 0 ? NULL : pathspec->items[first].match;
 	return max;
 }
 
 /*
- * Returns a copy of the longest leading path common among all
- * pathspecs.
+ * Returns a copy of the longest leading path common among all pathspec
+ * items that are not excluded.
  */
 char *common_prefix(const struct pathspec *pathspec)
 {
-	unsigned long len = common_prefix_len(pathspec);
+	const char *matched_prefix;
+	size_t len = common_prefix_len(pathspec, &matched_prefix);
 
-	return len ? xmemdupz(pathspec->items[0].match, len) : NULL;
+	return len ? xmemdupz(matched_prefix, len) : NULL;
 }
 
 int fill_directory(struct dir_struct *dir,
 		   struct index_state *istate,
 		   const struct pathspec *pathspec)
 {
-	const char *prefix;
+	const char *matched_prefix;
 	size_t prefix_len;
 
 	unsigned exclusive_flags = DIR_SHOW_IGNORED | DIR_SHOW_IGNORED_TOO;
@@ -284,11 +289,11 @@ int fill_directory(struct dir_struct *dir,
 	 * Calculate common prefix for the pathspec, and
 	 * use that to optimize the directory walk
 	 */
-	prefix_len = common_prefix_len(pathspec);
-	prefix = prefix_len ? pathspec->items[0].match : "";
+	prefix_len = common_prefix_len(pathspec, &matched_prefix);
 
 	/* Read the directory and prune it */
-	read_directory(dir, istate, prefix, prefix_len, pathspec);
+	read_directory(dir, istate, prefix_len ? matched_prefix : "",
+		       prefix_len, pathspec);
 
 	return prefix_len;
 }
@@ -394,7 +399,7 @@ static int match_pathspec_item(struct index_state *istate,
 
 	/*
 	 * The normal call pattern is:
-	 * 1. prefix = common_prefix_len(ps);
+	 * 1. prefix = common_prefix_len(ps, &matched_prefix);
 	 * 2. prune something, or fill_directory
 	 * 3. match_pathspec()
 	 *
@@ -414,8 +419,8 @@ static int match_pathspec_item(struct index_state *istate,
 	 * Normally the caller (common_prefix_len() in fact) does
 	 * _exact_ matching on name[-prefix+1..-1] and we do not need
 	 * to check that part. Be defensive and check it anyway, in
-	 * case common_prefix_len is changed, or a new caller is
-	 * introduced that does not use common_prefix_len.
+	 * case common_prefix_len() is changed, or a new caller is
+	 * introduced that does not use common_prefix_len().
 	 *
 	 * If the penalty turns out too high when prefix is really
 	 * long, maybe change it to
diff --git a/t/unit-tests/u-dir.c b/t/unit-tests/u-dir.c
index 2d0adaa39e..a3442c3d3c 100644
--- a/t/unit-tests/u-dir.c
+++ b/t/unit-tests/u-dir.c
@@ -45,3 +45,31 @@ void test_dir__within_depth(void)
 
 
 }
+
+void test_dir__common_prefix_skips_excluded_pathspec_items(void)
+{
+	struct pathspec_item items[] = {
+		{
+			.match = "unrelated/path",
+			.magic = PATHSPEC_EXCLUDE,
+			.nowildcard_len = 14,
+		},
+		{
+			.match = "foo/bar",
+			.nowildcard_len = 7,
+		},
+		{
+			.match = "foo/baz",
+			.nowildcard_len = 7,
+		},
+	};
+	struct pathspec pathspec = {
+		.nr = ARRAY_SIZE(items),
+		.magic = PATHSPEC_EXCLUDE,
+		.items = items,
+	};
+	char *prefix = common_prefix(&pathspec);
+
+	cl_assert_equal_s(prefix, "foo/");
+	free(prefix);
+}
-- 
2.55.0

Re: [PATCH v2 2/2] dir: find common prefix among non-exclude pathspec items

[Yannik Tausch]

Hi,

> Darik P <Prescottdarik@outlook.com> wrote:
> 
> 940-842-9147

could you clarify what these numbers refer to?

Note that, as indicated in the v1 patch (https://lore.kernel.org/git/0CA8678D-0540-4A2E-B314-B9BEB04E2BF5@ytausch.de/), I already discussed this matter with the git security mailing list. Not sure if it might be related to it.

Yannik

Re: [PATCH v2 0/2] dir: fix pathspec prefixes with exclusions

[Yannik Tausch]

I just found [1], which is related to this patch series. I didn’t review the discussion in detail yet, will follow up.

[1]: https://lore.kernel.org/git/xmqqv78qw3hc.fsf@gitster.g/T/#t

Re: [PATCH v2 2/2] dir: find common prefix among non-exclude pathspec items

[Junio C Hamano]

Yannik Tausch <dev@ytausch.de> writes:

> +void test_dir__common_prefix_skips_excluded_pathspec_items(void)
> +{
> +	struct pathspec_item items[] = {
> +		{
> +			.match = "unrelated/path",
> +			.magic = PATHSPEC_EXCLUDE,
> +			.nowildcard_len = 14,
> +		},

This unfortunately triggers

t/unit-tests/u-dir.c: In function 'test_dir__common_prefix_skips_excluded_pathspec_items':
t/unit-tests/u-dir.c:53:34: error: initialization discards 'const' qualifier from pointer target type [-Werror=discarded-qualifiers]
   53 |                         .match = "unrelated/path",
      |                                  ^~~~~~~~~~~~~~~~

Other than that, looking good.

pathspec: match and original in pathspec_item are const

[Junio C Hamano]

Junio C Hamano <gitster@pobox.com> writes:

> This unfortunately triggers
>
> t/unit-tests/u-dir.c: In function 'test_dir__common_prefix_skips_excluded_pathspec_items':
> t/unit-tests/u-dir.c:53:34: error: initialization discards 'const' qualifier from pointer target type [-Werror=discarded-qualifiers]
>    53 |                         .match = "unrelated/path",
>       |                                  ^~~~~~~~~~~~~~~~
>
> Other than that, looking good.

We may want a preparatory patch before this step.

----- >8 -----
Subject: pathspec: match and original in pathspec_item are const

No existing code modifies these two strings in pathspec elements
after they are created via these two pointers.  Declare them as
"const char *" to stress on this fact and cast away constness from
the code that frees these two strings.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---
 pathspec.c | 4 ++--
 pathspec.h | 4 ++--
 2 files changed, 4 insertions(+), 4 deletions(-)

diff --git c/pathspec.c w/pathspec.c
index f78b22709c..06b7065372 100644
--- c/pathspec.c
+++ w/pathspec.c
@@ -749,8 +749,8 @@ void clear_pathspec(struct pathspec *pathspec)
 	int i, j;
 
 	for (i = 0; i < pathspec->nr; i++) {
-		free(pathspec->items[i].match);
-		free(pathspec->items[i].original);
+		free((void *)pathspec->items[i].match);
+		free((void *)pathspec->items[i].original);
 
 		for (j = 0; j < pathspec->items[i].attr_match_nr; j++)
 			free(pathspec->items[i].attr_match[j].value);
diff --git c/pathspec.h w/pathspec.h
index 5e3a6f1fe7..fc1b9465ad 100644
--- c/pathspec.h
+++ w/pathspec.h
@@ -35,8 +35,8 @@ struct pathspec {
 	unsigned magic;
 	int max_depth;
 	struct pathspec_item {
-		char *match;
-		char *original;
+		const char *match;
+		const char *original;
 		unsigned magic;
 		int len, prefix;
 		int nowildcard_len;

Re: pathspec: match and original in pathspec_item are const

[Yannik Tausch]

> I just found [1], which is related to this patch series. I didn’t review the discussion in detail yet, will follow up.

I read this as you came to the same conclusion as me independently discovering the same issue in July. Perfect! I hope it’s fine that I took over the fix that way.

> Junio C Hamano <gitster@pobox.com> writes:
> 
>> This unfortunately triggers
>> 
>> t/unit-tests/u-dir.c: In function 'test_dir__common_prefix_skips_excluded_pathspec_items':
>> t/unit-tests/u-dir.c:53:34: error: initialization discards 'const' qualifier from pointer target type [-Werror=discarded-qualifiers]
>>   53 |                         .match = "unrelated/path",
>>      |                                  ^~~~~~~~~~~~~~~~
>> 
>> Other than that, looking good.
> 
> We may want a preparatory patch before this step.

Thanks, I will include your preparatory patch in v3. 

[PATCH v3 0/3] dir: fix pathspec prefixes with exclusions

[Yannik Tausch]

Pathspec prefix optimization must account for exclude items separately.
The prefix is derived from non-exclude items, so applying it while matching
an exclude item can compare the wrong portions of the paths. Conversely, an
exclude item at the start of the pathspec currently prevents finding a common
prefix among the remaining items.

The first patch, authored by Junio, marks the immutable strings in a pathspec
item as const. The second patch matches exclude items against the full
pathname. The third patch finds the common prefix starting with the first
non-exclude item and returns both the prefix length and the string from which
it was derived.

Changes since v2:

* Add Junio's preparatory const-correctness patch, which also fixes the unit
  test build with DEVELOPER=1.
* Keep the two pathspec prefix fixes unchanged.

Junio C Hamano (1):
  pathspec: match and original in pathspec_item are const

Yannik Tausch (2):
  dir: do not apply prefix to negative pathspecs
  dir: find common prefix among non-exclude pathspec items

 dir.c                       | 39 +++++++++++++++++++++----------------
 pathspec.c                  |  4 ++--
 pathspec.h                  |  4 ++--
 t/t6132-pathspec-exclude.sh |  9 +++++++++
 t/unit-tests/u-dir.c        | 28 ++++++++++++++++++++++++++
 5 files changed, 63 insertions(+), 21 deletions(-)

Range-diff against v2:
-:  ---------- > 1:  a257ce081e pathspec: match and original in pathspec_item are const
1:  c8a2f1e22e = 2:  16c6df5080 dir: do not apply prefix to negative pathspecs
2:  d0e08fdb96 = 3:  b05b77f399 dir: find common prefix among non-exclude pathspec items
-- 
2.55.0

[PATCH v3 1/3] pathspec: match and original in pathspec_item are const

[Yannik Tausch]

From: Junio C Hamano <gitster@pobox.com>

No existing code modifies these two strings in pathspec elements
after they are created via these two pointers.  Declare them as
"const char *" to stress on this fact and cast away constness from
the code that frees these two strings.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
Signed-off-by: Yannik Tausch <dev@ytausch.de>
---
 pathspec.c | 4 ++--
 pathspec.h | 4 ++--
 2 files changed, 4 insertions(+), 4 deletions(-)

diff --git a/pathspec.c b/pathspec.c
index 281858f21f..41c53ff26e 100644
--- a/pathspec.c
+++ b/pathspec.c
@@ -749,8 +749,8 @@ void clear_pathspec(struct pathspec *pathspec)
 	int i, j;
 
 	for (i = 0; i < pathspec->nr; i++) {
-		free(pathspec->items[i].match);
-		free(pathspec->items[i].original);
+		free((void *)pathspec->items[i].match);
+		free((void *)pathspec->items[i].original);
 
 		for (j = 0; j < pathspec->items[i].attr_match_nr; j++)
 			free(pathspec->items[i].attr_match[j].value);
diff --git a/pathspec.h b/pathspec.h
index 5e3a6f1fe7..fc1b9465ad 100644
--- a/pathspec.h
+++ b/pathspec.h
@@ -35,8 +35,8 @@ struct pathspec {
 	unsigned magic;
 	int max_depth;
 	struct pathspec_item {
-		char *match;
-		char *original;
+		const char *match;
+		const char *original;
 		unsigned magic;
 		int len, prefix;
 		int nowildcard_len;
-- 
2.55.0

[PATCH v3 2/3] dir: do not apply prefix to negative pathspecs

[Yannik Tausch]

common_prefix_len() derives the common prefix solely from positive
pathspecs, skipping those marked with PATHSPEC_EXCLUDE. However,
match_pathspec_with_flags() also passes that prefix when matching the
negative pathspecs.

A negative pathspec may be shorter than the prefix. In that case,
match_pathspec_item() advances item->match beyond its allocation and
subtracts the prefix from item->len, producing a negative matchlen. It
then dereferences the out-of-bounds pointer. If the resulting byte is
not NUL, matchlen is converted to size_t when passed to ps_strncmp(),
which may cause a much larger out-of-bounds read.

The problem can be reproduced with AddressSanitizer:

    make SANITIZE=address CFLAGS="-g -O0" git
    git init test &&
    cd test &&
    DIR=$(printf "a%.0s" {1..150}) &&
    mkdir -p "$DIR" &&
    touch "$DIR/f.txt" &&
    git add -A &&
    git commit -m test &&
    ../git ls-files -- "$DIR/" ":(exclude)xy"

This reports a heap-buffer-overflow. Without AddressSanitizer, the
output may depend on the contents of memory following the negative
pathspec.

Fix the bug by using a zero prefix when matching negative pathspecs.
Add a regression test that combines a positive pathspec with a longer
common prefix and a shorter, unrelated negative pathspec.

Signed-off-by: Yannik Tausch <dev@ytausch.de>
---
 dir.c                       | 2 +-
 t/t6132-pathspec-exclude.sh | 9 +++++++++
 2 files changed, 10 insertions(+), 1 deletion(-)

diff --git a/dir.c b/dir.c
index 95d8a1cce9..7072715389 100644
--- a/dir.c
+++ b/dir.c
@@ -593,7 +593,7 @@ static int match_pathspec_with_flags(struct index_state *istate,
 	if (!(ps->magic & PATHSPEC_EXCLUDE) || !positive)
 		return positive;
 	negative = do_match_pathspec(istate, ps, name, namelen,
-				     prefix, seen,
+				     0, seen,
 				     flags | DO_MATCH_EXCLUDE);
 	return negative ? 0 : positive;
 }
diff --git a/t/t6132-pathspec-exclude.sh b/t/t6132-pathspec-exclude.sh
index 9fdafeb1e9..ad919cc739 100755
--- a/t/t6132-pathspec-exclude.sh
+++ b/t/t6132-pathspec-exclude.sh
@@ -183,6 +183,15 @@ EOF
 	test_cmp expect actual
 '
 
+test_expect_success 'negative pathspec shorter than positive pathspec prefix' '
+	git ls-files -- sub/sub/ ":(exclude)sub2" >actual &&
+	cat <<-\EOF >expect &&
+	sub/sub/file
+	sub/sub/sub/file
+	EOF
+	test_cmp expect actual
+'
+
 test_expect_success 'multiple exclusions' '
 	git ls-files -- ":^*/file2" ":^sub2" >actual &&
 	cat <<-\EOF >expect &&
-- 
2.55.0

[PATCH v3 3/3] dir: find common prefix among non-exclude pathspec items

[Yannik Tausch]

common_prefix_len() skips exclude pathspec items, but uses n == 0 to
identify the initial item and items[0] as the comparison source. When
an exclude item comes first, the function returns zero even when all
remaining items share a directory.

Track the first non-exclude item explicitly. Return its match through
an output parameter so that common_prefix() and fill_directory() use
the correct string. Add a unit test with an unrelated exclude item
before two non-exclude items that share a directory.

Signed-off-by: Yannik Tausch <dev@ytausch.de>
---
 dir.c                | 37 +++++++++++++++++++++----------------
 t/unit-tests/u-dir.c | 28 ++++++++++++++++++++++++++++
 2 files changed, 49 insertions(+), 16 deletions(-)

diff --git a/dir.c b/dir.c
index 7072715389..d896e7be4b 100644
--- a/dir.c
+++ b/dir.c
@@ -212,9 +212,10 @@ static int fnmatch_icase_mem(const char *pattern, int patternlen,
 	return match_status;
 }
 
-static size_t common_prefix_len(const struct pathspec *pathspec)
+static size_t common_prefix_len(const struct pathspec *pathspec,
+				const char **matched_prefix)
 {
-	int n;
+	int n, first = -1;
 	size_t max = 0;
 
 	/*
@@ -237,43 +238,47 @@ static size_t common_prefix_len(const struct pathspec *pathspec)
 		size_t i = 0, len = 0, item_len;
 		if (pathspec->items[n].magic & PATHSPEC_EXCLUDE)
 			continue;
+		if (first < 0)
+			first = n;
 		if (pathspec->items[n].magic & PATHSPEC_ICASE)
 			item_len = pathspec->items[n].prefix;
 		else
 			item_len = pathspec->items[n].nowildcard_len;
-		while (i < item_len && (n == 0 || i < max)) {
+		while (i < item_len && (n == first || i < max)) {
 			char c = pathspec->items[n].match[i];
-			if (c != pathspec->items[0].match[i])
+			if (c != pathspec->items[first].match[i])
 				break;
 			if (c == '/')
 				len = i + 1;
 			i++;
 		}
-		if (n == 0 || len < max) {
+		if (n == first || len < max) {
 			max = len;
 			if (!max)
 				break;
 		}
 	}
+	*matched_prefix = first < 0 ? NULL : pathspec->items[first].match;
 	return max;
 }
 
 /*
- * Returns a copy of the longest leading path common among all
- * pathspecs.
+ * Returns a copy of the longest leading path common among all pathspec
+ * items that are not excluded.
  */
 char *common_prefix(const struct pathspec *pathspec)
 {
-	unsigned long len = common_prefix_len(pathspec);
+	const char *matched_prefix;
+	size_t len = common_prefix_len(pathspec, &matched_prefix);
 
-	return len ? xmemdupz(pathspec->items[0].match, len) : NULL;
+	return len ? xmemdupz(matched_prefix, len) : NULL;
 }
 
 int fill_directory(struct dir_struct *dir,
 		   struct index_state *istate,
 		   const struct pathspec *pathspec)
 {
-	const char *prefix;
+	const char *matched_prefix;
 	size_t prefix_len;
 
 	unsigned exclusive_flags = DIR_SHOW_IGNORED | DIR_SHOW_IGNORED_TOO;
@@ -284,11 +289,11 @@ int fill_directory(struct dir_struct *dir,
 	 * Calculate common prefix for the pathspec, and
 	 * use that to optimize the directory walk
 	 */
-	prefix_len = common_prefix_len(pathspec);
-	prefix = prefix_len ? pathspec->items[0].match : "";
+	prefix_len = common_prefix_len(pathspec, &matched_prefix);
 
 	/* Read the directory and prune it */
-	read_directory(dir, istate, prefix, prefix_len, pathspec);
+	read_directory(dir, istate, prefix_len ? matched_prefix : "",
+		       prefix_len, pathspec);
 
 	return prefix_len;
 }
@@ -394,7 +399,7 @@ static int match_pathspec_item(struct index_state *istate,
 
 	/*
 	 * The normal call pattern is:
-	 * 1. prefix = common_prefix_len(ps);
+	 * 1. prefix = common_prefix_len(ps, &matched_prefix);
 	 * 2. prune something, or fill_directory
 	 * 3. match_pathspec()
 	 *
@@ -414,8 +419,8 @@ static int match_pathspec_item(struct index_state *istate,
 	 * Normally the caller (common_prefix_len() in fact) does
 	 * _exact_ matching on name[-prefix+1..-1] and we do not need
 	 * to check that part. Be defensive and check it anyway, in
-	 * case common_prefix_len is changed, or a new caller is
-	 * introduced that does not use common_prefix_len.
+	 * case common_prefix_len() is changed, or a new caller is
+	 * introduced that does not use common_prefix_len().
 	 *
 	 * If the penalty turns out too high when prefix is really
 	 * long, maybe change it to
diff --git a/t/unit-tests/u-dir.c b/t/unit-tests/u-dir.c
index 2d0adaa39e..a3442c3d3c 100644
--- a/t/unit-tests/u-dir.c
+++ b/t/unit-tests/u-dir.c
@@ -45,3 +45,31 @@ void test_dir__within_depth(void)
 
 
 }
+
+void test_dir__common_prefix_skips_excluded_pathspec_items(void)
+{
+	struct pathspec_item items[] = {
+		{
+			.match = "unrelated/path",
+			.magic = PATHSPEC_EXCLUDE,
+			.nowildcard_len = 14,
+		},
+		{
+			.match = "foo/bar",
+			.nowildcard_len = 7,
+		},
+		{
+			.match = "foo/baz",
+			.nowildcard_len = 7,
+		},
+	};
+	struct pathspec pathspec = {
+		.nr = ARRAY_SIZE(items),
+		.magic = PATHSPEC_EXCLUDE,
+		.items = items,
+	};
+	char *prefix = common_prefix(&pathspec);
+
+	cl_assert_equal_s(prefix, "foo/");
+	free(prefix);
+}
-- 
2.55.0

Re: pathspec: match and original in pathspec_item are const

[Junio C Hamano]

Yannik Tausch <dev@ytausch.de> writes:

>> I just found [1], which is related to this patch series. I didn’t review the discussion in detail yet, will follow up.
>
> I read this as you came to the same conclusion as me independently discovering the same issue in July. Perfect! I hope it’s fine that I took over the fix that way.
>
>> Junio C Hamano <gitster@pobox.com> writes:
>> 
>>> This unfortunately triggers
>>> 
>>> t/unit-tests/u-dir.c: In function 'test_dir__common_prefix_skips_excluded_pathspec_items':
>>> t/unit-tests/u-dir.c:53:34: error: initialization discards 'const' qualifier from pointer target type [-Werror=discarded-qualifiers]
>>>   53 |                         .match = "unrelated/path",
>>>      |                                  ^~~~~~~~~~~~~~~~
>>> 
>>> Other than that, looking good.
>> 
>> We may want a preparatory patch before this step.
>
> Thanks, I will include your preparatory patch in v3. 

The 'const' patch will be queued separately, and a synthetic base will
be prepared for your two-patch series by merging the 'const' patch on
a recent tip of master.

Unless you have other changes, there is no need for you to send a
three-patch series.  We do not need to take the 'const' patch hostage
to the 'pathspec' patch.

Thanks.

Re: pathspec: match and original in pathspec_item are const

[Yannik Tausch]

> The 'const' patch will be queued separately, and a synthetic base will
> be prepared for your two-patch series by merging the 'const' patch on
> a recent tip of master.
> 
> Unless you have other changes, there is no need for you to send a
> three-patch series.  We do not need to take the 'const' patch hostage
> to the 'pathspec' patch.

Okay, anything I need to do now since I already submitted this as v3?

Re: pathspec: match and original in pathspec_item are const

[Junio C Hamano]

Yannik Tausch <dev@ytausch.de> writes:

>> The 'const' patch will be queued separately, and a synthetic base will
>> be prepared for your two-patch series by merging the 'const' patch on
>> a recent tip of master.
>> 
>> Unless you have other changes, there is no need for you to send a
>> three-patch series.  We do not need to take the 'const' patch hostage
>> to the 'pathspec' patch.
>
> Okay, anything I need to do now since I already submitted this as v3?

If [v3 2/3] and [v3 3/3] are identical to v2, just telling me to
ignore v3 would be sufficient.

If you need to make further changes, a two-patch series v4 on top of
d66ac2af30 (Merge branch 'jc/pathspec-match-const' into
yt/pathspec-negative-prefix, 2026-09-03) would be great.

Thanks.

Re: pathspec: match and original in pathspec_item are const

[Yannik Tausch]

> If [v3 2/3] and [v3 3/3] are identical to v2, just telling me to
> ignore v3 would be sufficient.

Please ignore v3 then.

> If you need to make further changes, a two-patch series v4 on top of
> d66ac2af30 (Merge branch 'jc/pathspec-match-const' into
> yt/pathspec-negative-prefix, 2026-09-03) would be great.

Many thanks, I‘ll use that if further changes become necessary in the review.

Re: [PATCH v2 1/2] dir: do not apply prefix to negative pathspecs

[Elijah Newren]

Hi Yannik,

On Thu, Sep 3, 2026 at 3:23 AM Yannik Tausch <dev@ytausch.de> wrote:
>
> common_prefix_len() derives the common prefix solely from positive
> pathspecs, skipping those marked with PATHSPEC_EXCLUDE. However,
> match_pathspec_with_flags() also passes that prefix when matching the
> negative pathspecs.
>
> A negative pathspec may be shorter than the prefix. In that case,
> match_pathspec_item() advances item->match beyond its allocation and
> subtracts the prefix from item->len, producing a negative matchlen. It
> then dereferences the out-of-bounds pointer. If the resulting byte is
> not NUL, matchlen is converted to size_t when passed to ps_strncmp(),
> which may cause a much larger out-of-bounds read.
>
> The problem can be reproduced with AddressSanitizer:
>
>     make SANITIZE=address CFLAGS="-g -O0" git
>     git init test &&
>     cd test &&
>     DIR=$(printf "a%.0s" {1..150}) &&
>     mkdir -p "$DIR" &&
>     touch "$DIR/f.txt" &&
>     git add -A &&
>     git commit -m test &&
>     ../git ls-files -- "$DIR/" ":(exclude)xy"
>
> This reports a heap-buffer-overflow. Without AddressSanitizer, the
> output may depend on the contents of memory following the negative
> pathspec.
>
> Fix the bug by using a zero prefix when matching negative pathspecs.
> Add a regression test that combines a positive pathspec with a longer
> common prefix and a shorter, unrelated negative pathspec.
>
> Signed-off-by: Yannik Tausch <dev@ytausch.de>
> ---
>  dir.c                       | 2 +-
>  t/t6132-pathspec-exclude.sh | 9 +++++++++
>  2 files changed, 10 insertions(+), 1 deletion(-)
>
> diff --git a/dir.c b/dir.c
> index 95d8a1cce9..7072715389 100644
> --- a/dir.c
> +++ b/dir.c
> @@ -593,7 +593,7 @@ static int match_pathspec_with_flags(struct index_state *istate,
>         if (!(ps->magic & PATHSPEC_EXCLUDE) || !positive)
>                 return positive;
>         negative = do_match_pathspec(istate, ps, name, namelen,
> -                                    prefix, seen,
> +                                    0, seen,
>                                      flags | DO_MATCH_EXCLUDE);
>         return negative ? 0 : positive;
>  }
> diff --git a/t/t6132-pathspec-exclude.sh b/t/t6132-pathspec-exclude.sh
> index 9fdafeb1e9..ad919cc739 100755
> --- a/t/t6132-pathspec-exclude.sh
> +++ b/t/t6132-pathspec-exclude.sh
> @@ -183,6 +183,15 @@ EOF
>         test_cmp expect actual
>  '
>
> +test_expect_success 'negative pathspec shorter than positive pathspec prefix' '
> +       git ls-files -- sub/sub/ ":(exclude)sub2" >actual &&
> +       cat <<-\EOF >expect &&
> +       sub/sub/file
> +       sub/sub/sub/file
> +       EOF
> +       test_cmp expect actual
> +'

Would it make sense to add a regression case whose failure before this
patch is deterministic without ASan?

The test above advances beyond the end of "sub2", so its result
depends on out-of-bounds memory.  I actually saw this test pass
without your fixes, when not run under ASan, which may depend on the
allocator or build.

An alternative would be an exclude whose length equals the seven-byte
prefix, keeping the accesses in bounds:

        test_expect_success 'exclude is matched against the full path' '
                git ls-files -- sub/sub/ ":(exclude)zzzzzzz" >actual &&
                cat <<-\EOF >expect &&
                sub/sub/file
                sub/sub/sub/file
                EOF
                test_cmp expect actual
        '

Before this patch, stripping seven bytes points at the exclude
string's NUL terminator, which is then treated as matching everything.
I get no output before the fix, and both expected paths after your
fix.

I'm not suggesting this as a replacement for your regression test; I
think the out-of-bounds case is still useful.  I just think this extra
testcase might be a nice complement.

Re: [PATCH v2 2/2] dir: find common prefix among non-exclude pathspec items

[Elijah Newren]

On Thu, Sep 3, 2026 at 3:08 AM Yannik Tausch <dev@ytausch.de> wrote:
>
> common_prefix_len() skips exclude pathspec items, but uses n == 0 to
> identify the initial item and items[0] as the comparison source. When
> an exclude item comes first, the function returns zero even when all
> remaining items share a directory.
>
> Track the first non-exclude item explicitly. Return its match through
> an output parameter so that common_prefix() and fill_directory() use
> the correct string. Add a unit test with an unrelated exclude item
> before two non-exclude items that share a directory.

This to me looked more like what you are changing, and I had a hard
time figuring out why you were changing it.

Does the following alternative correctly capture your intent and change here? :


dir: preserve pathspec prefix optimization with leading excludes

Directory walks use the common directory prefix of non-exclude
pathspec items to avoid scanning unrelated portions of the working
tree or index.  Exclude items only remove paths from that candidate
set, so they do not need to widen the traversal.

When an exclude item is the first pathspec item,
common_prefix_len() fails to establish a comparison base and returns
a zero-length prefix.  The result is correct, but git unnecessarily
traverses from a broader starting point even when all non-exclude
items share a directory.

Use the first non-exclude item as the comparison base and return its
string together with the prefix length, allowing callers to start
from the recovered directory prefix.  Exclude matching continues to
use full paths, so this restores the optimization without changing
which paths are selected.  Add a unit test covering an exclude item
before two non-exclude items with a common directory.


> Signed-off-by: Yannik Tausch <dev@ytausch.de>
> ---
>  dir.c                | 37 +++++++++++++++++++++----------------
>  t/unit-tests/u-dir.c | 28 ++++++++++++++++++++++++++++
>  2 files changed, 49 insertions(+), 16 deletions(-)
>
> diff --git a/dir.c b/dir.c
> index 7072715389..d896e7be4b 100644
> --- a/dir.c
> +++ b/dir.c
> @@ -212,9 +212,10 @@ static int fnmatch_icase_mem(const char *pattern, int patternlen,
>         return match_status;
>  }
>
> -static size_t common_prefix_len(const struct pathspec *pathspec)
> +static size_t common_prefix_len(const struct pathspec *pathspec,
> +                               const char **matched_prefix)
>  {
> -       int n;
> +       int n, first = -1;
>         size_t max = 0;
>
>         /*
> @@ -237,43 +238,47 @@ static size_t common_prefix_len(const struct pathspec *pathspec)
>                 size_t i = 0, len = 0, item_len;
>                 if (pathspec->items[n].magic & PATHSPEC_EXCLUDE)
>                         continue;
> +               if (first < 0)
> +                       first = n;
>                 if (pathspec->items[n].magic & PATHSPEC_ICASE)
>                         item_len = pathspec->items[n].prefix;
>                 else
>                         item_len = pathspec->items[n].nowildcard_len;
> -               while (i < item_len && (n == 0 || i < max)) {
> +               while (i < item_len && (n == first || i < max)) {
>                         char c = pathspec->items[n].match[i];
> -                       if (c != pathspec->items[0].match[i])
> +                       if (c != pathspec->items[first].match[i])
>                                 break;
>                         if (c == '/')
>                                 len = i + 1;
>                         i++;
>                 }
> -               if (n == 0 || len < max) {
> +               if (n == first || len < max) {
>                         max = len;
>                         if (!max)
>                                 break;
>                 }
>         }
> +       *matched_prefix = first < 0 ? NULL : pathspec->items[first].match;
>         return max;
>  }
>
>  /*
> - * Returns a copy of the longest leading path common among all
> - * pathspecs.
> + * Returns a copy of the longest leading path common among all pathspec
> + * items that are not excluded.
>   */
>  char *common_prefix(const struct pathspec *pathspec)
>  {
> -       unsigned long len = common_prefix_len(pathspec);
> +       const char *matched_prefix;
> +       size_t len = common_prefix_len(pathspec, &matched_prefix);
>
> -       return len ? xmemdupz(pathspec->items[0].match, len) : NULL;
> +       return len ? xmemdupz(matched_prefix, len) : NULL;
>  }
>
>  int fill_directory(struct dir_struct *dir,
>                    struct index_state *istate,
>                    const struct pathspec *pathspec)
>  {
> -       const char *prefix;
> +       const char *matched_prefix;
>         size_t prefix_len;
>
>         unsigned exclusive_flags = DIR_SHOW_IGNORED | DIR_SHOW_IGNORED_TOO;
> @@ -284,11 +289,11 @@ int fill_directory(struct dir_struct *dir,
>          * Calculate common prefix for the pathspec, and
>          * use that to optimize the directory walk
>          */
> -       prefix_len = common_prefix_len(pathspec);
> -       prefix = prefix_len ? pathspec->items[0].match : "";
> +       prefix_len = common_prefix_len(pathspec, &matched_prefix);
>
>         /* Read the directory and prune it */
> -       read_directory(dir, istate, prefix, prefix_len, pathspec);
> +       read_directory(dir, istate, prefix_len ? matched_prefix : "",
> +                      prefix_len, pathspec);
>
>         return prefix_len;
>  }
> @@ -394,7 +399,7 @@ static int match_pathspec_item(struct index_state *istate,
>
>         /*
>          * The normal call pattern is:
> -        * 1. prefix = common_prefix_len(ps);
> +        * 1. prefix = common_prefix_len(ps, &matched_prefix);
>          * 2. prune something, or fill_directory
>          * 3. match_pathspec()
>          *
> @@ -414,8 +419,8 @@ static int match_pathspec_item(struct index_state *istate,
>          * Normally the caller (common_prefix_len() in fact) does
>          * _exact_ matching on name[-prefix+1..-1] and we do not need
>          * to check that part. Be defensive and check it anyway, in
> -        * case common_prefix_len is changed, or a new caller is
> -        * introduced that does not use common_prefix_len.
> +        * case common_prefix_len() is changed, or a new caller is
> +        * introduced that does not use common_prefix_len().
>          *
>          * If the penalty turns out too high when prefix is really
>          * long, maybe change it to
> diff --git a/t/unit-tests/u-dir.c b/t/unit-tests/u-dir.c
> index 2d0adaa39e..a3442c3d3c 100644
> --- a/t/unit-tests/u-dir.c
> +++ b/t/unit-tests/u-dir.c
> @@ -45,3 +45,31 @@ void test_dir__within_depth(void)
>
>
>  }
> +
> +void test_dir__common_prefix_skips_excluded_pathspec_items(void)
> +{
> +       struct pathspec_item items[] = {
> +               {
> +                       .match = "unrelated/path",
> +                       .magic = PATHSPEC_EXCLUDE,
> +                       .nowildcard_len = 14,
> +               },
> +               {
> +                       .match = "foo/bar",
> +                       .nowildcard_len = 7,
> +               },
> +               {
> +                       .match = "foo/baz",
> +                       .nowildcard_len = 7,
> +               },
> +       };
> +       struct pathspec pathspec = {
> +               .nr = ARRAY_SIZE(items),
> +               .magic = PATHSPEC_EXCLUDE,
> +               .items = items,
> +       };
> +       char *prefix = common_prefix(&pathspec);
> +
> +       cl_assert_equal_s(prefix, "foo/");
> +       free(prefix);
> +}
> --
> 2.55.0

If my wording above is correct, I think the code looks like it
correctly implements that idea.

Re: [PATCH v2 1/2] dir: do not apply prefix to negative pathspecs

[Junio C Hamano]

Elijah Newren <newren@gmail.com> writes:

> Hi Yannik,
>
> On Thu, Sep 3, 2026 at 3:23 AM Yannik Tausch <dev@ytausch.de> wrote:
>>
>> common_prefix_len() derives the common prefix solely from positive
>> pathspecs, skipping those marked with PATHSPEC_EXCLUDE. However,
>> match_pathspec_with_flags() also passes that prefix when matching the
>> negative pathspecs.
>>
>> A negative pathspec may be shorter than the prefix. In that case,
>> match_pathspec_item() advances item->match beyond its allocation and
>> subtracts the prefix from item->len, producing a negative matchlen. It
>> then dereferences the out-of-bounds pointer. If the resulting byte is
>> not NUL, matchlen is converted to size_t when passed to ps_strncmp(),
>> which may cause a much larger out-of-bounds read.
>>
>> The problem can be reproduced with AddressSanitizer:
> ...
> Would it make sense to add a regression case whose failure before this
> patch is deterministic without ASan?

Very good point.

Even if a negative pathspec were long enough, it would produce an
incorrect result if you strip the leading part of a negative entry.

With positive elements "a/b" and "a/c", and a negative element
"x/b", both paths "a/b/m" and "a/c/n" should match the pathspec with
these three elements, but if you incorrectly use prefix=2 to strip
the common prefix computed across positives, i.e., "a/", while
trying to see if the path "a/b/m" matches negative "x/b", we'd end
up trying to see if subpath "b/m" (in "a/b/m", after 2 leading
prefix bytes are stripped away) matches subpattern "b" (in "x/b",
after incorrectly stripping 2 leading bytes).  Yay, "b/m" begins
with "b" so it matches!  Not quite.

    $ git init
    $ mkdir -p a/b a/c
    $ >a/b/m >a/c/n
    $ git add a
    $ rungit jch ls-files a/b ':!x/b' a/c
    a/b/m
    a/c/n
    $ rungit master ls-files a/b ':!x/b' a/c
    a/c/n

So "if prefix computed across positives is longer than a negative
element" is a special case that may manifest as one extra breakage
(i.e., logically it is wrong in that it uses incorrectly shortened
pattern and path for negated matching and produce incorrect result,
but in addition to that, the negated pattern string points outside
the original string, accessing wrong piece of memory), but I tend to
agree that it is equally if not more important to demonstrate what
is broken even without that extra breakage.

Thanks.

Re: [PATCH v2 2/2] dir: find common prefix among non-exclude pathspec items

[Junio C Hamano]

Elijah Newren <newren@gmail.com> writes:

> This to me looked more like what you are changing, and I had a hard
> time figuring out why you were changing it.

While I share this assessment,...

>
> Does the following alternative correctly capture your intent and change here? :
>
>
> dir: preserve pathspec prefix optimization with leading excludes
>
> Directory walks use the common directory prefix of non-exclude
> pathspec items to avoid scanning unrelated portions of the working
> tree or index.  Exclude items only remove paths from that candidate
> set, so they do not need to widen the traversal.
>
> When an exclude item is the first pathspec item,
> common_prefix_len() fails to establish a comparison base and returns
> a zero-length prefix.  The result is correct, but git unnecessarily
> traverses from a broader starting point even when all non-exclude
> items share a directory.

... I do not think this is true.

What happens inside dir.c::fill_directory() is driven only with the
return value of common_prefix_len(), which already ignores and has
always ignored the negative pathspec elements.

What this [2/2] changes is what string common_prefix() returns.  If
you have "!x/b" "a/b" "a/c", common_prefix_len() goes over the two
positive ones "a/b" and "a/c" and correctly notices that "a/" is
common among the positive ones and its length is 2.

The problem this patch fixes is that common_prefix() used to always
grab the first two bytes of the element that happens to be at the
beginning of pathspec, so a pathspec ("!x/b" "a/b" "a/c") would have
given you "!x" as the common prefix string, which obviously is
bogus.  The common_prefix() is only used in two code paths that are
quite distant from here.  It is clear there is a bug (i.e., the code
that wants to be passed "a/" in such a case cannot be happy to see
"!x" instead), but it is totally unclear what the end-user visible
effect of that bug (i.e. what happens when overlay_tree_on_index()
passes an incorrectly computed common_prefix() when "git ls-files"
is run with "--with-tree=<treeish>" option?).

> Use the first non-exclude item as the comparison base and return its
> string together with the prefix length, allowing callers to start
> from the recovered directory prefix.  Exclude matching continues to
> use full paths, so this restores the optimization without changing
> which paths are selected.  Add a unit test covering an exclude item
> before two non-exclude items with a common directory.

I do not think this is what this patch does.  What you are
describing is this bit:

>> -static size_t common_prefix_len(const struct pathspec *pathspec)
>> ...
>>                 size_t i = 0, len = 0, item_len;
>>                 if (pathspec->items[n].magic & PATHSPEC_EXCLUDE)
>>                         continue;

which dates back to the very beginning of negative pathspec elements
support introduced at ef79b1f870 (Support pathspec magic :(exclude)
and its short form :!, 2013-12-06), I think.

Re: [PATCH v2 2/2] dir: find common prefix among non-exclude pathspec items

[Elijah Newren]

On Fri, Sep 4, 2026 at 9:43 AM Junio C Hamano <gitster@pobox.com> wrote:
>
> Elijah Newren <newren@gmail.com> writes:
>
> > This to me looked more like what you are changing, and I had a hard
> > time figuring out why you were changing it.
>
> While I share this assessment,...
>
> >
> > Does the following alternative correctly capture your intent and change here? :
> >
> >
> > dir: preserve pathspec prefix optimization with leading excludes
> >
> > Directory walks use the common directory prefix of non-exclude
> > pathspec items to avoid scanning unrelated portions of the working
> > tree or index.  Exclude items only remove paths from that candidate
> > set, so they do not need to widen the traversal.
> >
> > When an exclude item is the first pathspec item,
> > common_prefix_len() fails to establish a comparison base and returns
> > a zero-length prefix.  The result is correct, but git unnecessarily
> > traverses from a broader starting point even when all non-exclude
> > items share a directory.
>
> ... I do not think this is true.
>
> What happens inside dir.c::fill_directory() is driven only with the
> return value of common_prefix_len(), which already ignores and has
> always ignored the negative pathspec elements.
>
> What this [2/2] changes is what string common_prefix() returns.  If
> you have "!x/b" "a/b" "a/c", common_prefix_len() goes over the two
> positive ones "a/b" and "a/c" and correctly notices that "a/" is
> common among the positive ones and its length is 2.
>
> The problem this patch fixes is that common_prefix() used to always
> grab the first two bytes of the element that happens to be at the
> beginning of pathspec, so a pathspec ("!x/b" "a/b" "a/c") would have
> given you "!x" as the common prefix string, which obviously is
> bogus.  The common_prefix() is only used in two code paths that are
> quite distant from here.  It is clear there is a bug (i.e., the code
> that wants to be passed "a/" in such a case cannot be happy to see
> "!x" instead), but it is totally unclear what the end-user visible
> effect of that bug (i.e. what happens when overlay_tree_on_index()
> passes an incorrectly computed common_prefix() when "git ls-files"
> is run with "--with-tree=<treeish>" option?).

Maybe I'm misreading the code.  Did it always grab the first two bytes
of the element at the beginning of pathspec, or did it get an empty
string?  By my reading of the code (copied here for convenience), it
got an empty string:

>-static size_t common_prefix_len(const struct pathspec *pathspec)
>+static size_t common_prefix_len(const struct pathspec *pathspec,
>+                               const char **matched_prefix)
> {
>-       int n;
>+       int n, first = -1;
>        size_t max = 0;
[...]
>        for (n = 0; n < pathspec->nr; n++) {
>                size_t i = 0, len = 0, item_len;
>                if (pathspec->items[n].magic & PATHSPEC_EXCLUDE)
>                        continue;
>+               if (first < 0)
>+                       first = n;
>                if (pathspec->items[n].magic & PATHSPEC_ICASE)
>                        item_len = pathspec->items[n].prefix;
>                else
>                        item_len = pathspec->items[n].nowildcard_len;
>-               while (i < item_len && (n == 0 || i < max)) {
>+               while (i < item_len && (n == first || i < max)) {
>                        char c = pathspec->items[n].match[i];
>-                       if (c != pathspec->items[0].match[i])
>+                       if (c != pathspec->items[first].match[i])
>                                break;
>                        if (c == '/')
>                                len = i + 1;
>                        i++;
>                }
>-               if (n == 0 || len < max) {
>+               if (n == first || len < max) {
>                        max = len;
>                        if (!max)
>                                break;
>                }
>        }
>+       *matched_prefix = first < 0 ? NULL : pathspec->items[first].match;
>        return max;
> }

Following the preimage, and using your pathspec of ("!x/b", "a/b", "a/c"):
  - when n=0, we hit the PATHSPEC_EXCLUDE case at the top, so max remains 0
  - for each n>0, we fail both sides of the (n==0 || i < max checks),
so len remains 0.  We then fail (n==0 || len < max) checks, so max is
not adjusted (though it'd only be adjusted to 0 anyway)
So, at the end, max is 0 and we return 0.

>> > Use the first non-exclude item as the comparison base and return its
> > string together with the prefix length, allowing callers to start
> > from the recovered directory prefix.  Exclude matching continues to
> > use full paths, so this restores the optimization without changing
> > which paths are selected.  Add a unit test covering an exclude item
> > before two non-exclude items with a common directory.
>
> I do not think this is what this patch does.  What you are
> describing is this bit:
>
> >> -static size_t common_prefix_len(const struct pathspec *pathspec)
> >> ...
> >>                 size_t i = 0, len = 0, item_len;
> >>                 if (pathspec->items[n].magic & PATHSPEC_EXCLUDE)
> >>                         continue;
>
> which dates back to the very beginning of negative pathspec elements
> support introduced at ef79b1f870 (Support pathspec magic :(exclude)
> and its short form :!, 2013-12-06), I think.

I was trying to describe "n == first" vs. "n == 0" in the last
if-check, which allows us to set max to something greater than 0 when
an excluded pathspec appears first.

Happy to hear if I'm mis-reading or if my previous explanation
mis-describes this.

Re: [PATCH v2 2/2] dir: find common prefix among non-exclude pathspec items

[Junio C Hamano]

Elijah Newren <newren@gmail.com> writes:

> Maybe I'm misreading the code.  Did it always grab the first two bytes
> of the element at the beginning of pathspec, or did it get an empty
> string?  By my reading of the code (copied here for convenience), it
> got an empty string:

No, I was the one who misread the code.  Indeed in the loop, we
assume all elements in the pathspec share the same prefix we have
found to be valid so far (the loop is about shortening what we found
so far with later elements in the pathspec), and blindly use the
first element, which is wrong.

[PATCH v4 0/2] dir: fix pathspec prefixes with exclusions

[Yannik Tausch]

Pathspec prefix optimization must account for exclude items separately.
The prefix is derived from non-exclude items, so applying it while
matching an exclude item can compare the wrong portions of the paths.
Conversely, an exclude item at the start of the pathspec currently
prevents finding a common prefix among the remaining items.

The first patch matches exclude items against the full pathname. The
second patch finds the common prefix starting with the first non-exclude
item and returns both the prefix length and the string from which it was
derived.

Changes since v3, which was withdrawn in favor of v2:

* Return to a two-patch series based on d66ac2af30, leaving Junio's
  preparatory const-correctness patch on its separately queued topic.
* Add the deterministic regression test suggested by Elijah, while
  retaining the shorter-pattern test for the out-of-bounds access.
* Explain the observable incorrect match in patch 1 and use consistent
  non-exclude/exclude terminology.
* Reword patch 2 to describe the directory-walk optimization it restores.

Yannik Tausch (2):
  dir: do not apply prefix to negative pathspecs
  dir: preserve pathspec prefix optimization with leading excludes

 dir.c                       | 39 +++++++++++++++++++++----------------
 t/t6132-pathspec-exclude.sh | 18 +++++++++++++++++
 t/unit-tests/u-dir.c        | 28 ++++++++++++++++++++++++++
 3 files changed, 68 insertions(+), 17 deletions(-)

Range-diff against v2:
1:  c8a2f1e22e ! 1:  adeb7f2fb6 dir: do not apply prefix to negative pathspecs
    @@ Metadata
      ## Commit message ##
         dir: do not apply prefix to negative pathspecs
     
    -    common_prefix_len() derives the common prefix solely from positive
    -    pathspecs, skipping those marked with PATHSPEC_EXCLUDE. However,
    -    match_pathspec_with_flags() also passes that prefix when matching the
    -    negative pathspecs.
    +    common_prefix_len() derives the common prefix solely from non-exclude
    +    pathspec items. However, match_pathspec_with_flags() also passes that
    +    prefix when matching exclude items.
     
    -    A negative pathspec may be shorter than the prefix. In that case,
    -    match_pathspec_item() advances item->match beyond its allocation and
    -    subtracts the prefix from item->len, producing a negative matchlen. It
    -    then dereferences the out-of-bounds pointer. If the resulting byte is
    -    not NUL, matchlen is converted to size_t when passed to ps_strncmp(),
    -    which may cause a much larger out-of-bounds read.
    +    This can produce incorrect results because that prefix does not
    +    necessarily match an exclude item. For example, given non-exclude items
    +    "a/b" and "a/c" and an exclude item "x/b", stripping the two-byte
    +    prefix from both the pathname "a/b/m" and pattern "x/b" makes the
    +    remaining strings match and incorrectly excludes the pathname.
     
    -    The problem can be reproduced with AddressSanitizer:
    +    If an exclude item is shorter than the prefix, match_pathspec_item()
    +    instead advances item->match beyond its allocation and subtracts the
    +    prefix from item->len, producing a negative matchlen. It then
    +    dereferences the out-of-bounds pointer. If the resulting byte is not
    +    NUL, matchlen is converted to size_t when passed to ps_strncmp(), which
    +    may cause a much larger out-of-bounds read.
    +
    +    The out-of-bounds access can be reproduced with AddressSanitizer:
     
             make SANITIZE=address CFLAGS="-g -O0" git
             git init test &&
    @@ Commit message
             git commit -m test &&
             ../git ls-files -- "$DIR/" ":(exclude)xy"
     
    -    This reports a heap-buffer-overflow. Without AddressSanitizer, the
    -    output may depend on the contents of memory following the negative
    -    pathspec.
    -
    -    Fix the bug by using a zero prefix when matching negative pathspecs.
    -    Add a regression test that combines a positive pathspec with a longer
    -    common prefix and a shorter, unrelated negative pathspec.
    +    Fix the bug by using a zero prefix when matching exclude items. Add
    +    regression tests for both the deterministic incorrect match and the
    +    shorter exclude item that causes the out-of-bounds access.
     
         Signed-off-by: Yannik Tausch <dev@ytausch.de>
     
    @@ t/t6132-pathspec-exclude.sh: EOF
     +	EOF
     +	test_cmp expect actual
     +'
    ++
    ++test_expect_success 'exclude is matched against the full path' '
    ++	git ls-files -- sub/sub/ ":(exclude)zzzzzzz" >actual &&
    ++	cat <<-\EOF >expect &&
    ++	sub/sub/file
    ++	sub/sub/sub/file
    ++	EOF
    ++	test_cmp expect actual
    ++'
     +
      test_expect_success 'multiple exclusions' '
      	git ls-files -- ":^*/file2" ":^sub2" >actual &&
2:  d0e08fdb96 ! 2:  e8f72cab9c dir: find common prefix among non-exclude pathspec items
    @@ Metadata
     Author: Yannik Tausch <dev@ytausch.de>
     
      ## Commit message ##
    -    dir: find common prefix among non-exclude pathspec items
    +    dir: preserve pathspec prefix optimization with leading excludes
     
    -    common_prefix_len() skips exclude pathspec items, but uses n == 0 to
    -    identify the initial item and items[0] as the comparison source. When
    -    an exclude item comes first, the function returns zero even when all
    -    remaining items share a directory.
    +    Directory walks use the common directory prefix of non-exclude
    +    pathspec items to avoid scanning unrelated portions of the working
    +    tree or index. Exclude items only remove paths from that candidate
    +    set, so they do not need to widen the traversal.
     
    -    Track the first non-exclude item explicitly. Return its match through
    -    an output parameter so that common_prefix() and fill_directory() use
    -    the correct string. Add a unit test with an unrelated exclude item
    -    before two non-exclude items that share a directory.
    +    When an exclude item is the first pathspec item, common_prefix_len()
    +    fails to establish a comparison base and returns a zero-length prefix.
    +    The result is correct, but Git unnecessarily traverses from a broader
    +    starting point even when all non-exclude items share a directory.
    +
    +    Use the first non-exclude item as the comparison base and return its
    +    string together with the prefix length, allowing callers to start from
    +    the recovered directory prefix. Exclude matching continues to use full
    +    paths, so this restores the optimization without changing which paths
    +    are selected. Add a unit test covering an exclude item before two
    +    non-exclude items with a common directory.
     
         Signed-off-by: Yannik Tausch <dev@ytausch.de>
     

base-commit: d66ac2af300f33bd9e8558c5645f2a808cc01f89
-- 
2.55.0

[PATCH v4 1/2] dir: do not apply prefix to negative pathspecs

[Yannik Tausch]

common_prefix_len() derives the common prefix solely from non-exclude
pathspec items. However, match_pathspec_with_flags() also passes that
prefix when matching exclude items.

This can produce incorrect results because that prefix does not
necessarily match an exclude item. For example, given non-exclude items
"a/b" and "a/c" and an exclude item "x/b", stripping the two-byte
prefix from both the pathname "a/b/m" and pattern "x/b" makes the
remaining strings match and incorrectly excludes the pathname.

If an exclude item is shorter than the prefix, match_pathspec_item()
instead advances item->match beyond its allocation and subtracts the
prefix from item->len, producing a negative matchlen. It then
dereferences the out-of-bounds pointer. If the resulting byte is not
NUL, matchlen is converted to size_t when passed to ps_strncmp(), which
may cause a much larger out-of-bounds read.

The out-of-bounds access can be reproduced with AddressSanitizer:

    make SANITIZE=address CFLAGS="-g -O0" git
    git init test &&
    cd test &&
    DIR=$(printf "a%.0s" {1..150}) &&
    mkdir -p "$DIR" &&
    touch "$DIR/f.txt" &&
    git add -A &&
    git commit -m test &&
    ../git ls-files -- "$DIR/" ":(exclude)xy"

Fix the bug by using a zero prefix when matching exclude items. Add
regression tests for both the deterministic incorrect match and the
shorter exclude item that causes the out-of-bounds access.

Signed-off-by: Yannik Tausch <dev@ytausch.de>
---
 dir.c                       |  2 +-
 t/t6132-pathspec-exclude.sh | 18 ++++++++++++++++++
 2 files changed, 19 insertions(+), 1 deletion(-)

diff --git a/dir.c b/dir.c
index 32430090dc..5f42c992d3 100644
--- a/dir.c
+++ b/dir.c
@@ -593,7 +593,7 @@ static int match_pathspec_with_flags(struct index_state *istate,
 	if (!(ps->magic & PATHSPEC_EXCLUDE) || !positive)
 		return positive;
 	negative = do_match_pathspec(istate, ps, name, namelen,
-				     prefix, seen,
+				     0, seen,
 				     flags | DO_MATCH_EXCLUDE);
 	return negative ? 0 : positive;
 }
diff --git a/t/t6132-pathspec-exclude.sh b/t/t6132-pathspec-exclude.sh
index 9fdafeb1e9..e0c3f73ef0 100755
--- a/t/t6132-pathspec-exclude.sh
+++ b/t/t6132-pathspec-exclude.sh
@@ -183,6 +183,24 @@ EOF
 	test_cmp expect actual
 '
 
+test_expect_success 'negative pathspec shorter than positive pathspec prefix' '
+	git ls-files -- sub/sub/ ":(exclude)sub2" >actual &&
+	cat <<-\EOF >expect &&
+	sub/sub/file
+	sub/sub/sub/file
+	EOF
+	test_cmp expect actual
+'
+
+test_expect_success 'exclude is matched against the full path' '
+	git ls-files -- sub/sub/ ":(exclude)zzzzzzz" >actual &&
+	cat <<-\EOF >expect &&
+	sub/sub/file
+	sub/sub/sub/file
+	EOF
+	test_cmp expect actual
+'
+
 test_expect_success 'multiple exclusions' '
 	git ls-files -- ":^*/file2" ":^sub2" >actual &&
 	cat <<-\EOF >expect &&
-- 
2.55.0

[PATCH v4 2/2] dir: preserve pathspec prefix optimization with leading excludes

[Yannik Tausch]

Directory walks use the common directory prefix of non-exclude
pathspec items to avoid scanning unrelated portions of the working
tree or index. Exclude items only remove paths from that candidate
set, so they do not need to widen the traversal.

When an exclude item is the first pathspec item, common_prefix_len()
fails to establish a comparison base and returns a zero-length prefix.
The result is correct, but Git unnecessarily traverses from a broader
starting point even when all non-exclude items share a directory.

Use the first non-exclude item as the comparison base and return its
string together with the prefix length, allowing callers to start from
the recovered directory prefix. Exclude matching continues to use full
paths, so this restores the optimization without changing which paths
are selected. Add a unit test covering an exclude item before two
non-exclude items with a common directory.

Signed-off-by: Yannik Tausch <dev@ytausch.de>
---
 dir.c                | 37 +++++++++++++++++++++----------------
 t/unit-tests/u-dir.c | 28 ++++++++++++++++++++++++++++
 2 files changed, 49 insertions(+), 16 deletions(-)

diff --git a/dir.c b/dir.c
index 5f42c992d3..abc4a78f31 100644
--- a/dir.c
+++ b/dir.c
@@ -212,9 +212,10 @@ static int fnmatch_icase_mem(const char *pattern, int patternlen,
 	return match_status;
 }
 
-static size_t common_prefix_len(const struct pathspec *pathspec)
+static size_t common_prefix_len(const struct pathspec *pathspec,
+				const char **matched_prefix)
 {
-	int n;
+	int n, first = -1;
 	size_t max = 0;
 
 	/*
@@ -237,43 +238,47 @@ static size_t common_prefix_len(const struct pathspec *pathspec)
 		size_t i = 0, len = 0, item_len;
 		if (pathspec->items[n].magic & PATHSPEC_EXCLUDE)
 			continue;
+		if (first < 0)
+			first = n;
 		if (pathspec->items[n].magic & PATHSPEC_ICASE)
 			item_len = pathspec->items[n].prefix;
 		else
 			item_len = pathspec->items[n].nowildcard_len;
-		while (i < item_len && (n == 0 || i < max)) {
+		while (i < item_len && (n == first || i < max)) {
 			char c = pathspec->items[n].match[i];
-			if (c != pathspec->items[0].match[i])
+			if (c != pathspec->items[first].match[i])
 				break;
 			if (c == '/')
 				len = i + 1;
 			i++;
 		}
-		if (n == 0 || len < max) {
+		if (n == first || len < max) {
 			max = len;
 			if (!max)
 				break;
 		}
 	}
+	*matched_prefix = first < 0 ? NULL : pathspec->items[first].match;
 	return max;
 }
 
 /*
- * Returns a copy of the longest leading path common among all
- * pathspecs.
+ * Returns a copy of the longest leading path common among all pathspec
+ * items that are not excluded.
  */
 char *common_prefix(const struct pathspec *pathspec)
 {
-	unsigned long len = common_prefix_len(pathspec);
+	const char *matched_prefix;
+	size_t len = common_prefix_len(pathspec, &matched_prefix);
 
-	return len ? xmemdupz(pathspec->items[0].match, len) : NULL;
+	return len ? xmemdupz(matched_prefix, len) : NULL;
 }
 
 int fill_directory(struct dir_struct *dir,
 		   struct index_state *istate,
 		   const struct pathspec *pathspec)
 {
-	const char *prefix;
+	const char *matched_prefix;
 	size_t prefix_len;
 
 	unsigned exclusive_flags = DIR_SHOW_IGNORED | DIR_SHOW_IGNORED_TOO;
@@ -284,11 +289,11 @@ int fill_directory(struct dir_struct *dir,
 	 * Calculate common prefix for the pathspec, and
 	 * use that to optimize the directory walk
 	 */
-	prefix_len = common_prefix_len(pathspec);
-	prefix = prefix_len ? pathspec->items[0].match : "";
+	prefix_len = common_prefix_len(pathspec, &matched_prefix);
 
 	/* Read the directory and prune it */
-	read_directory(dir, istate, prefix, prefix_len, pathspec);
+	read_directory(dir, istate, prefix_len ? matched_prefix : "",
+		       prefix_len, pathspec);
 
 	return prefix_len;
 }
@@ -394,7 +399,7 @@ static int match_pathspec_item(struct index_state *istate,
 
 	/*
 	 * The normal call pattern is:
-	 * 1. prefix = common_prefix_len(ps);
+	 * 1. prefix = common_prefix_len(ps, &matched_prefix);
 	 * 2. prune something, or fill_directory
 	 * 3. match_pathspec()
 	 *
@@ -414,8 +419,8 @@ static int match_pathspec_item(struct index_state *istate,
 	 * Normally the caller (common_prefix_len() in fact) does
 	 * _exact_ matching on name[-prefix+1..-1] and we do not need
 	 * to check that part. Be defensive and check it anyway, in
-	 * case common_prefix_len is changed, or a new caller is
-	 * introduced that does not use common_prefix_len.
+	 * case common_prefix_len() is changed, or a new caller is
+	 * introduced that does not use common_prefix_len().
 	 *
 	 * If the penalty turns out too high when prefix is really
 	 * long, maybe change it to
diff --git a/t/unit-tests/u-dir.c b/t/unit-tests/u-dir.c
index 2d0adaa39e..a3442c3d3c 100644
--- a/t/unit-tests/u-dir.c
+++ b/t/unit-tests/u-dir.c
@@ -45,3 +45,31 @@ void test_dir__within_depth(void)
 
 
 }
+
+void test_dir__common_prefix_skips_excluded_pathspec_items(void)
+{
+	struct pathspec_item items[] = {
+		{
+			.match = "unrelated/path",
+			.magic = PATHSPEC_EXCLUDE,
+			.nowildcard_len = 14,
+		},
+		{
+			.match = "foo/bar",
+			.nowildcard_len = 7,
+		},
+		{
+			.match = "foo/baz",
+			.nowildcard_len = 7,
+		},
+	};
+	struct pathspec pathspec = {
+		.nr = ARRAY_SIZE(items),
+		.magic = PATHSPEC_EXCLUDE,
+		.items = items,
+	};
+	char *prefix = common_prefix(&pathspec);
+
+	cl_assert_equal_s(prefix, "foo/");
+	free(prefix);
+}
-- 
2.55.0

Re: [PATCH v4 0/2] dir: fix pathspec prefixes with exclusions

[Junio C Hamano]

Yannik Tausch <dev@ytausch.de> writes:

> Pathspec prefix optimization must account for exclude items separately.
> The prefix is derived from non-exclude items, so applying it while
> matching an exclude item can compare the wrong portions of the paths.
> Conversely, an exclude item at the start of the pathspec currently
> prevents finding a common prefix among the remaining items.
> ...
> Yannik Tausch (2):
>   dir: do not apply prefix to negative pathspecs
>   dir: preserve pathspec prefix optimization with leading excludes

Thnaks.  This round looks ready for 'next'.