[PATCH v3 4/6] revision: add Bloom check that includes parent directories
- From
Toon Claes <toon@iotcl.com>
- Date
- Aug 31, 2026, 15:18 UTC
- Message-ID
- <20260831-toon-speed-up-last-modified-v3-4-2bbb864acf93@iotcl.com>
- In-Reply-To
- <20260831-toon-speed-up-last-modified-v3-0-2bbb864acf93@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 ed46b90b00..a560146b4d 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