Re: [PATCH 3/4] last-modified: check pathspec against Bloom filter first

[Taylor Blau <ttaylorr@openai.com>]

On Sat, Jul 18, 2026 at 04:37:57AM -0400, Jeff King wrote:
> > I don't think this is safe with '--show-trees'. The original pathspec
> > does not cover every entry in 'lm->paths', since the function
> > 'populate_paths_from_revs()' also adds ancestor tree entries.
>
> Hmm, interesting. I am surprised to learn that "-t" includes "d" when
> the pathspec asked for "d/a". I thought it was mostly about showing
> "d/a" when we recurse to find "d/a/b". But I guess it does not make a
> distinction between the two (probably because it is just telling the
> diff code to show trees, and it does not further apply the pathspec to
> the output).
>
> Does this mean there is also a bug in "git log"? I guess not, because it
> is purely pruning based on the pathspec, and only shows "d/" for those
> commits.

Right.

> > I think that the conditional is otherwise correct, if guarded when we
> > know that 'lm->show_trees' is false, like so:
> >
> >     if (!lm->show_trees &&
> >         !revs_maybe_changed_in_bloom(&lm->rev, filter))
> >             return false;
>
> Hmph. That makes this optimization all but useless, because the intended
> use case of last-modified is almost always going to use "-t" to be able
> to mark the interior trees. And most callers are not going to care about
> seeing "d" here; their purpose was to find out about the things _inside_
> "d".
>
> Would we consider removing "d" from the output for this case? Presumably
> by double-checking the pathspecs again in add_path_from_diff(). That
> gives less surprising output (to me, anyway) and would enable this
> optimization. And the command is still marked as experimental, and I
> think this is exactly the kind of corner case that is meant to cover.

I think that we could feasibly get rid of "d" in the output in this
particular case within last-modified. As you note, the command is marked
EXPERIMENTAL for a reason, after all ;-).

If we wanted to do that, it should be straightforward to do. I think the
following (untested) patch would be sufficient:

--- 8< ---
diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index adc7cd8c74..0f0c1d1d17 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -103,7 +103,7 @@ struct last_modified_callback_data {
 };

 static void add_path_from_diff(struct diff_queue_struct *q,
-			       struct diff_options *opt UNUSED, void *data)
+			       struct diff_options *opt, void *data)
 {
 	struct last_modified *lm = data;

@@ -112,6 +112,11 @@ static void add_path_from_diff(struct diff_queue_struct *q,
 		struct last_modified_entry *ent;
 		const char *path = p->two->path;

+		if (!match_pathspec(opt->repo->index, &opt->pathspec, path,
+				    strlen(path), 0, NULL,
+				    S_ISDIR(p->two->mode)))
+			continue;
+
 		FLEX_ALLOC_STR(ent, path, path);
 		oidcpy(&ent->oid, &p->two->oid);
 		if (lm->rev.bloom_filter_settings)
--- >8 ---

If, on the other hand, we wanted to retain "d" in the output (which I am
inclined to suggest is a bad idea), we could keep a list of paths which
are not covered by the given pathspec.

If you had such a list, you could check only active entries within that
list, removing them as they are resolved. That makes a Bloom query miss
O(U*H) (where U is the uncovered subset of all paths, and H is the
number of hash functions in our Bloom key, which in our case is 7) as
opposed to O(P*H), where P is the number of active paths.

Of course, as U approaches P, the advantage disappears and so too do
the benefits of Toon's optimization.

If you wanted to go that route, you could do something like the
following (lightly tested):

--- 8< ---
diff --git a/builtin/last-modified.c b/builtin/last-modified.c
index adc7cd8c74..e69c7a44b6 100644
--- a/builtin/last-modified.c
+++ b/builtin/last-modified.c
@@ -11,6 +11,7 @@
 #include "ewah/ewok.h"
 #include "hashmap.h"
 #include "hex.h"
+#include "list.h"
 #include "object-name.h"
 #include "object.h"
 #include "parse-options.h"
@@ -25,9 +26,11 @@

 struct last_modified_entry {
 	struct hashmap_entry hashent;
+	struct list_head uncovered;
 	struct object_id oid;
 	struct bloom_key key;
 	size_t diff_idx;
+	bool covered_by_pathspec;
 	const char path[FLEX_ARRAY];
 };

@@ -52,6 +55,7 @@ define_commit_slab(active_paths_for_commit, struct bitmap *);

 struct last_modified {
 	struct hashmap paths;
+	struct list_head uncovered_paths;
 	struct rev_info rev;
 	bool show_trees;
 	bool nul_termination;
@@ -103,7 +107,7 @@ struct last_modified_callback_data {
 };

 static void add_path_from_diff(struct diff_queue_struct *q,
-			       struct diff_options *opt UNUSED, void *data)
+			       struct diff_options *opt, void *data)
 {
 	struct last_modified *lm = data;

@@ -114,6 +118,16 @@ static void add_path_from_diff(struct diff_queue_struct *q,

 		FLEX_ALLOC_STR(ent, path, path);
 		oidcpy(&ent->oid, &p->two->oid);
+
+		if (match_pathspec(opt->repo->index, &opt->pathspec, path,
+				   strlen(path), 0, NULL,
+				   S_ISDIR(p->two->mode))) {
+			ent->covered_by_pathspec = true;
+		} else {
+			list_add_tail(&ent->uncovered, &lm->uncovered_paths);
+			ent->covered_by_pathspec = false;
+		}
+
 		if (lm->rev.bloom_filter_settings)
 			bloom_key_fill(&ent->key, path, strlen(path),
 				       lm->rev.bloom_filter_settings);
@@ -202,6 +216,8 @@ static void mark_path(const char *path, const struct object_id *oid,
 	last_modified_emit(data->lm, path, data->commit);

 	hashmap_remove(&data->lm->paths, &ent->hashent, path);
+	if (!ent->covered_by_pathspec)
+		list_del(&ent->uncovered);
 	bloom_key_clear(&ent->key);
 	free(ent);
 }
@@ -272,8 +288,22 @@ static bool maybe_changed_path(struct last_modified *lm,
 	if (!filter)
 		return true;

-	if (revs_maybe_changed_in_bloom(&lm->rev, filter) == 0)
+	if (revs_maybe_changed_in_bloom(&lm->rev, filter) == 0) {
+		struct list_head *pos;
+
+		list_for_each(pos, &lm->uncovered_paths) {
+			ent = list_entry(pos, struct last_modified_entry,
+					 uncovered);
+			if (active && !bitmap_get(active, ent->diff_idx))
+				continue;
+
+			if (bloom_filter_contains(filter, &ent->key,
+						  lm->rev.bloom_filter_settings))
+				return true;
+		}
+
 		return false;
+	}

 	hashmap_for_each_entry(&lm->paths, &iter, ent, hashent) {
 		if (active && !bitmap_get(active, ent->diff_idx))
@@ -490,6 +520,7 @@ static int last_modified_init(struct last_modified *lm, struct repository *r,
 	struct last_modified_entry *ent;

 	hashmap_init(&lm->paths, last_modified_entry_hashcmp, NULL, 0);
+	INIT_LIST_HEAD(&lm->uncovered_paths);

 	repo_init_revisions(r, &lm->rev, prefix);
 	lm->rev.def = "HEAD";
--- >8 ---

On my machine, in a synthetic repository containing 10,000 commits with
5,001 covered paths and 1 uncovered path, Toon's original patch runs in
~450ms. With the above patch, the timing drops to ~227ms, whereas it
drops further to ~190ms when omitting the uncovered path entirely.

So I'm inclined to suggest that we take advantage of the command's
EXPERIMENTAL nature and avoid printing the uncovered path entirely.

Thanks,
Taylor