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

From: Kristofer Karlsson <krka@spotify.com>
Date: Oct 6, 2026, 12:36 UTC
Message-ID: <CAL71e4OCuwT=Wj8eMF0DJ3UXFocb24yssLf4buyFDGEnTR6mgw@mail.gmail.com>
In-Reply-To: <asTkyiIZvX1ztMrH@pks.im>

On Tue, 6 Oct 2026 at 14:08, Patrick Steinhardt <ps@pks.im> wrote:

Show 16 quoted lines

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

Show 7 quoted lines

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