On Thu, May 23, 2024 at 06:48:37AM -0400, Jeff King wrote: > 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). Good, thanks. > > [^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. :) ;-). Thanks, Taylor
