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

From: Elijah Newren <newren@gmail.com>
Date: Sep 4, 2026, 19:19 UTC
Message-ID: <CABPp-BHviE8uLgh6PE=6MYkz_zTDZfKU9CbHQjJOeLgA=qpUSA@mail.gmail.com>
In-Reply-To: <xmqqy0dh3r2k.fsf@gitster.g>

On Fri, Sep 4, 2026 at 9:43 AM Junio C Hamano <gitster@pobox.com> wrote:

Show 47 quoted lines

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

Show 7 quoted lines

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

[...]

Show 30 quoted lines

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

Show 19 quoted lines

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