From: Patrick Steinhardt Date: Tue, 06 Oct 2026 12:08:42 GMT Subject: Re: [PATCH v2 2/2] connected: add incremental connectivity check via rev-list Message-ID: In-Reply-To: On Tue, Oct 06, 2026 at 12:37:40PM +0200, Kristofer Karlsson wrote: > On Mon, 5 Oct 2026 at 10:00, Patrick Steinhardt 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