Re: [PATCH 1/3] revision: support tracking uninteresting commits

[Derrick Stolee <derrickstolee@github.com>]

On 5/3/2023 6:08 PM, Taylor Blau wrote:
> On Tue, Apr 25, 2023 at 02:15:49PM -0400, Derrick Stolee wrote:
>> I know that the walking code in builtin/pack-objects.c does
>> this same computation, but it's muddled with other checks and
>> the trees are marked as UNINTERESTING at the same time. It
>> doesn't seem like we can reuse anything directly out of there,
>> but it did give me the idea to try a callback.
> 
> Interesting idea. When you say callback, do you mean a function that we
> invoke in place of where we currently call `add_object_array()`? Or do
> you mean something else? Curious.

I was talking about passing a callback into the revision walk
instead of having the revision code create a list, as you
replied to in this response:

>> But could we also do this at the caller's end by passing a
>> callback that checks each walked commit if it is UNINTERESTING
>> and adds it to a set?
> 
> I think I remember trying this when I originally wrote this code, and
> ended up discarding the idea because it walked over more commits than we
> needed to consider.
 
It's interesting that it walked more commits than you wanted. I
suppose it's somehow related to the boundary condition you're
implying by enabling the construction of this list.

Could you describe the situation where more commits are walked
than you want? I imagine we can't actually stop at the boundary
because we need to know that certain commits are actually reachable
from those boundary commits.

Here's an example (assume horizontal levels are equal generation
number for the sake of the walk's stopping condition).

  1 (UNINTERESTING)  2 (INTERESTING)
  |\_____       ____/|
  |      \     /     |
  3       4    5     6
  |       |\__ |     |
  |       |   \|     |
  7       8   [9]    10
  |       |    |     |
  11      12   13    14
  |       |    | ___/|
  |       |    |/    |
  15      16  [17]   18
  |       | ___|____/
  |       |/   |
 (19)    [20]   21

Here, 9, 17, and 20 are the boundary, as they are UNINITERESTING
but reachable from an interesting commit (5, 14, and 18,
respectively). This is sufficient to provide a stopping point
for this single-directional difference "2 --not 1".

It's important that we didn't stop walking at 9, since its
UNINTERESTING bit needed to propagate through 13 to get to 17.

Note that 19 is reachable from 1 but not 2, so we would need to
keep walking if we were looking for the boundary of the symmetric
difference 1...2. But we don't need it here since everything at
that level is marked UNINTERESTING so the walk can stop.

Is this example sufficiently complex for you to describe what
causes the extra commit walking? In such a case, what does the
object array approach add to prevent the extra walking?

Thanks,
-Stolee