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

From: Derrick Stolee <derrickstolee@github.com>
Date: May 4, 2023, 13:59 UTC
Message-ID: <7a0ea3d7-f67b-8f9d-f9ea-550fcc05108d@github.com>
In-Reply-To: <ZFLbXTKOK6KTEy7q@nand.local>

On 5/3/2023 6:08 PM, Taylor Blau wrote:

Show 10 quoted lines

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

Show 7 quoted lines

>> 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