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

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 <[email protected]>
---
 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