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
