Re: [PATCH v2 2/2] connected: add incremental connectivity check via rev-list

On Tue, Oct 06, 2026 at 12:37:40PM +0200, Kristofer Karlsson wrote:

On Mon, 5 Oct 2026 at 10:00, Patrick Steinhardt [off-list ref] wrote:

[snip]

quoted

quoted

+The incremental mode, selected by
+`transfer.connectivityCheck=incremental`, avoids traversing the
+full tree walk of the boundary commits.  Instead, it verifies
+each incoming commit's tree against the already-trusted trees of
+its parents.

Can we define "parents" here? Specifically, I wonder how you define
"parent" in the case where you perform a force push or when creating a
new reference. Is it the parent of the first new commit? Is it the old
state of the ref, if it even exists?

Parent is always defined relative to the commit we are
currently verifying.  For example, a push may come with
3 commits (let's call the tip T), and then we do the
following comparisons:

    T   vs T^1, T^2
    T~1 vs T~1^1, T~1^2
    T~2 vs T~2^1, T~2^2

T~2^1 and T~2^2 must already exist and be reachable and
so we can trust them to be connected.  And since this is
relying on memoizing already seen results, it's important
to run the checks bottom-up (reverse topological order).

This is the part that still eludes me though. How do we know that T~2^1
and T~2^2 must already exist and be reachable?

I think I was coming in with a false expectation that we're somehow
getting rid of marking preexistingrefs as uninteresting, and that is
where my confusion comes from. Because ultimately, that does not seem to
be the case -- we still mark reference tips as uninteresting, as far as
I can see. And then we can of course easily determine whether a specific
commit is preexisting because we marked the boundary as uninteresting.

I was probably primed by my own earlier patch series in this context
that focussed on refs, and that may be the reason why I had skewed
expectations.

quoted

quoted

+Incoming commits are processed with ancestors before descendants.
+Once an incoming commit's tree has been verified, it is trusted
+and can be used as a comparison base for later descendants.
+
+This gives an inductive correctness argument: every parent of the
+commit currently being verified is either already connected or is
+an earlier incoming commit whose tree has already been verified.

Right. The big question to me still is how you identify
already-connected trees without having to read all references.

That part works just as before -- rev-list finds the
already-connected commits implicitly with the --not --all query.
It actually finds all the new commits, but we can deduce the
boundary from there (and the pre-existing rev-list code also does
that).

Yeah.

quoted

quoted

diff --git a/tree-verify.c b/tree-verify.c
new file mode 100644
index 0000000000..5c11c2251a
--- /dev/null
+++ b/tree-verify.c

@@ -0,0 +1,316 @@

[snip]

quoted

+static void verify_commit_tree(struct repository *repo,
+                            struct commit *commit,
+                            struct verify_state *vs)
+{
+     struct oid_array base_trees = OID_ARRAY_INIT;
+     struct commit_list *p;
+
+     /*
+      * Parent trees are trusted: boundary parents are already
+      * connected, and earlier incoming parents were verified
+      * first due to the topological processing order.
+      */

I feel like I still miss where exactly you establish the trust boundary
between preexisting fully-connected commits and new commits.

This is the same as before -- git rev-list produces the trust
boundary based on reachability.  I think the only new thing here
is the inductive leap.  Once we have verified a commit just above
the trust boundary, that itself becomes a new trust boundary.

quoted

quoted

+     if (commit_list_count(*commits) < nr_before)
+             die(_("cycle detected in incoming commit graph"));

I don't think we should just die, should we? That may not interact well
with git-receive-pack(1) and others that expect a broken connectivity
check to bubble up errors so that they can properly report those to the
client and clean up their local state.

This is one of the advantages of running within a sub-process --
we can safely die without breaking things -- and this is in fact
how the existing rev-list based implementation work, it will also
die with an error message / return code that the parent process
picks up.

Ah, right, I forgot that we're running in a separate process. I think
this will also become a bit clearer once this series is split up into
smaller individual steps.

Thanks!

Patrick