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

[Patrick Steinhardt <ps@pks.im>]

On Tue, Oct 06, 2026 at 12:37:40PM +0200, Kristofer Karlsson wrote:
> On Mon, 5 Oct 2026 at 10:00, Patrick Steinhardt <ps@pks.im> wrote:
[snip]
> > > +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.

> > > +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.

> > > 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]
> > > +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.
> 
> > > +     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