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

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