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

On Fri, Sep 4, 2026 at 9:43 AM Junio C Hamano [off-list ref] wrote:

Elijah Newren [off-list ref] writes:

quoted

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

quoted

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.

quoted

quoted

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:

quoted

quoted

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