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

From: Elijah Newren <newren@gmail.com>
Date: Sep 4, 2026, 05:02 UTC
Message-ID: <CABPp-BF6hps9DibSV4ghbowkOD-NfEsHYFdLoKab0hCfEi9rgw@mail.gmail.com>
In-Reply-To: <27FF785F-F5D5-44EC-93C2-5BD67BD99147@ytausch.de>

On Thu, Sep 3, 2026 at 3:08 AM Yannik Tausch <dev@ytausch.de> wrote:

Show 10 quoted lines

>
> 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.

Show 152 quoted lines

> 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.