Subject: Re: [PATCH v3 26/30] pack-bitmap.c: use pseudo-merges during traversal

From: Jeff King <[email-masked]>
Date: Thu, 23 May 2024 06:48:37 -0400

On Tue, May 21, 2024 at 03:03:03PM -0400, Taylor Blau wrote:

> The basic operation is as follows:
> 
>   - When enumerating objects on either side of a reachability query,
>     first see if any subset of the roots satisfies some pseudo-merge
>     bitmap. If it does, apply that pseudo-merge bitmap.
> 
>   - If any pseudo-merge bitmap(s) were applied in the previous step, OR
>     them into the result[^1]. Then repeat the process over all
>     pseudo-merge bitmaps (we'll refer to this as "cascading"
>     pseudo-merges). Once this is done, OR in the resulting bitmap.
> 
>   - If there is no fill-in traversal to be done, return the bitmap for
>     that side of the reachability query. If there is fill-in traversal,
>     then for each commit we encounter via show_commit(), check to see if
>     any unsatisfied pseudo-merges containing that commit as one of its
>     parents has been made satisfied by the presence of that commit.
> 
>     If so, OR in the object set from that pseudo-merge bitmap, and then
>     cascade. If not, continue traversal.

Ah, OK. This is the high-level overview I was looking for in the earlier
commit. ;) I think it is fine here. I just hadn't gotten to it yet (and
I think it is much better stated than what I wrote in my earlier
response).

> [^1]: Importantly, we cannot OR in the entire set of roots along with
>   the objects reachable from whatever pseudo-merge bitmaps were
>   satisfied.  This may leave some dangling bits corresponding to any
>   unsatisfied root(s) getting OR'd into the resulting bitmap, tricking
>   other parts of the traversal into thinking we already have a
>   reachability closure over those commit(s) when we do not.

I think I know how you made this realization. :)

The code itself looks as I'd expect, and the entry points are nice and
clean.

-Peff