git/list[1] front-page[2] threads[3] people[4] search[5] about
 

[PATCH v2 4/6] revision: add Bloom check that includes parent directories

From
Toon Claes <toon@iotcl.com>
Date
Aug 7, 2026, 18:26 UTC
Message-ID
<20260807-toon-speed-up-last-modified-v2-4-7d87bbdeaf9b@iotcl.com>
In-Reply-To
<20260807-toon-speed-up-last-modified-v2-0-7d87bbdeaf9b@iotcl.com>

revs_maybe_changed_in_bloom() reports whether a commit may have changed any of the paths in the pathspec. It uses bloom_filter_contains_vec(), which requires all keys of a path's key vector to be present, so it only answers for the paths themselves.

A caller may track more than those paths. git-last-modified(1) with --show-trees reports the last modifying commit for the tree entries containing the paths as well, up to the root. For a pathspec "a/b/c/" that means it reports "a" and "a/b" next to "a/b/c" and its entries, and those can each resolve to a different commit. A commit that only changed "a/top" is the answer for "a", even though it touched nothing under "a/b".

Such a caller needs to know whether the path, or any of the directories leading up to it, may have changed. Add revs_maybe_changed_in_bloom_with_parents(), which asks that question by using bloom_filter_contains_any_vec() instead. A key vector holds a key for the path and one for each of its leading directories, so looking up any of them answers it.

There are no callers yet, one is added in a subsequent commit.
Signed-off-by: Toon Claes <toon@iotcl.com>
---
 revision.c | 15 +++++++++++++++
 revision.h |  8 ++++++++
 2 files changed, 23 insertions(+)
diff --git a/revision.c b/revision.c
index 78dcb40d9f..3195c0cab1 100644
--- a/revision.c
+++ b/revision.c
@@ -789,6 +789,21 @@ bool revs_maybe_changed_in_bloom(struct rev_info *revs,
 	return false;
 }
 
+bool revs_maybe_changed_in_bloom_with_parents(struct rev_info *revs,
+					      struct bloom_filter *filter)
+{
+	if (!revs->bloom_keyvecs_nr || !filter)
+		return true;
+
+	for (size_t nr = 0; nr < revs->bloom_keyvecs_nr; nr++)
+		if (bloom_filter_contains_any_vec(filter,
+						  revs->bloom_keyvecs[nr],
+						  revs->bloom_filter_settings))
+			return true;
+
+	return false;
+}
+
 static int rev_compare_tree(struct rev_info *revs,
 			    struct commit *parent, struct commit *commit, int nth_parent)
 {
diff --git a/revision.h b/revision.h
index 67778558e1..192001ff79 100644
--- a/revision.h
+++ b/revision.h
@@ -507,6 +507,14 @@ int prepare_revision_walk(struct rev_info *revs);
 bool revs_maybe_changed_in_bloom(struct rev_info *revs,
 				 struct bloom_filter *filter);
 
+/**
+ * Same as revs_maybe_changed_in_bloom(), but a change to any of the directories
+ * leading up to a path counts as well. Callers that track the tree entries
+ * containing the paths, and not just the paths themselves, need this.
+ */
+bool revs_maybe_changed_in_bloom_with_parents(struct rev_info *revs,
+					      struct bloom_filter *filter);
+
 /* Drain the commits linked list into the priority queue. */
 void rev_info_commit_list_to_queue(struct rev_info *revs);
 /**
-- 
2.55.0.679.g6767b8d81c
Previous: Toon ClaesNext: Toon Claes
Message 27 of 30 in “last-modified: use the pathspec's Bloom key to pre-filter commits”
  1. 0/4 last-modified: use the pathspec's Bloom key to pre-filter commitsToon Claes, Jul 17, 2026
  2. 1/4 revision: move bloom keyvec precondition into functionToon Claes, Jul 17, 2026
  3. Jeff KingJul 18, 2026
  4. Toon ClaesAug 5, 2026
  5. Jeff KingAug 5, 2026
  6. 2/4 revision: expose check for paths maybe changed in Bloom filterToon Claes, Jul 17, 2026
  7. Junio C HamanoJul 17, 2026
  8. Taylor BlauJul 17, 2026
  9. 3/4 last-modified: check pathspec against Bloom filter firstToon Claes, Jul 17, 2026
  10. Taylor BlauJul 17, 2026
  11. Jeff KingJul 18, 2026
  12. Taylor BlauJul 18, 2026
  13. Jeff KingJul 20, 2026
  14. 4/4 last-modified: keep per-path Bloom filters for wildcard pathspecsToon Claes, Jul 17, 2026
  15. Toon ClaesJul 17, 2026
  16. Jeff KingJul 18, 2026
  17. Junio C HamanoAug 4, 2026
  18. Taylor BlauAug 5, 2026
  19. Junio C HamanoAug 5, 2026
  20. Jeff KingAug 5, 2026
  21. Taylor BlauJul 17, 2026
  22. Toon ClaesJul 17, 2026
  23. 0/6 last-modified: use the pathspec's Bloom key to pre-filter commitsToon Claes, Aug 7, 2026
  24. 1/6 revision: move bloom keyvec precondition into functionToon Claes, Aug 7, 2026
  25. 2/6 revision: expose check for paths maybe changed in Bloom filterToon Claes, Aug 7, 2026
  26. 3/6 bloom: add helper to check if any key in a vector is presentToon Claes, Aug 7, 2026
  27. 4/6 revision: add Bloom check that includes parent directoriesToon Claes, Aug 7, 2026
  28. 5/6 last-modified: check pathspec against Bloom filter firstToon Claes, Aug 7, 2026
  29. 6/6 last-modified: keep per-path Bloom filters for wildcard pathspecsToon Claes, Aug 7, 2026
  30. Junio C HamanoAug 8, 2026

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.