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

On Tue, 6 Oct 2026 at 14:08, Patrick Steinhardt [off-list ref] wrote:

quoted

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?

Since T~2 is the bottom of the incoming commits, its parent
commits must be part of the boundary -- by definition, since
otherwise they would instead by included by rev-list --not --all.

Here is a concrete example with a push of 3 commits, where N1
is a merge commit and we have two pre-existing refs R1 and R2
(T, T~1, T~2 maps to N3, N2 and N1 respectively here):

    B1---R1
     \
      N1---N2---N3
     /
    B2---R2

    --not --all produces: {N1, N2, N3}

    B1 and B2 are boundary (reachable from existing refs R1 and R2)

    Verification (bottom-up):
    N1: compare N1.tree vs B1.tree and B2.tree
        (B1, B2 are boundary -- not in incoming set,
         so connected by definition)
    N2: compare N2.tree vs N1.tree
        (N1 just verified, trusted inductively)
    N3:  compare N3.tree vs N2.tree
        (N2 just verified, trusted inductively)

We never walk B1 or B2's full trees to mark objects
uninteresting.  We only read their root trees as comparison
bases when they are direct parents of an incoming commit.
That is where the savings come from.

So to directly answer your question: we know T~2's parents
(B1 and B2 in this example) are connected because --not --all
told us so -- they were not produced by the commit walk, which
means they are reachable from existing refs.  This is the same
trust boundary the full check uses.  The only new idea is the
inductive step: once we verify a commit just above the boundary,
it itself becomes trusted and extends the boundary upward.

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.

Yes, precisely.

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.

Yes, I've noted a few other workstreams that are sort of
touching similar areas, though not directly the connectivity
check, so it's a lot of context to juggle at the same time
(and I will need to take that into account for the next steps).

Thanks,
Kristofer