Re: [PATCH/RFC 2/6] commit-reach: introduce struct paint_queue with per-side counters

[Derrick Stolee <stolee@gmail.com>]

On 6/22/2026 3:14 PM, Kristofer Karlsson wrote:
> On Mon, 22 Jun 2026 at 20:10, Derrick Stolee <stolee@gmail.com> wrote:
>>

>> Also: technically "case 0" should be a BUG() state, right? We
>> shouldn't be walking any commit that isn't reachable from at
>> least one side. (case 0 does happen for old_paint, though.)
> 
> No, this is actually intended - initially I started with skipping
> case 0 and let it fall through, but that would hide _other_ bugs.
> I use 0 as a marker for "not in the queue" so we have this:
> Enqueuing: 0 -> flags
> Dequeueing: flags -> 0
> Only the case with the modified commit being in the queue
> will have non-zero flags. I tried to document this, but perhaps
> it is not clear enough, I will see if I can rephrase it, or add an
> inline comment around the case itself.

I bet this would be obvious if I tried to change the code and
run the tests. thanks for the explanation.

>>> +     while ((commit = paint_queue_get(&queue))) {
>> ...> +
>>> +             if (queue.p1_count + queue.p2_count +
>>> +                 queue.pending_merge_bases == 0)
>>> +                     break;
>>>       }
>> When possible, I like to try to make loops only have one terminating
>> condition. Should we have paint_queue_get() return NULL when it sees
>> this internal state condition?
> 
> Possibly, but that would couple the paint_queue struct very tightly with
> the usage. Not a problem in practice since it only has one call site, and
> it's unlikely that we want to add more of them but it may feel more natural
> to let the paint_queue purely have the queue semantics and counters,
> and keep the halt condition within the function itself. I don't feel
> super-strongly about this and can change it if needed, I will just need to
> verify that nothing else gets complex as a result, I have not fully thought
> through the effects.

Hm. Interesting. The coupling is perhaps expected, because the data
structure tracks counts that don't otherwise need to be tracked.
Maybe the terminating condition method could be descriptively named
to say why it would be completing.

>> Also, I'd rather see it of the form of (!count) instead of using
>> addition to make it clear that we care about each value being zero.
> 
> I did consider that, and most of the code in commit-reach.c at least
> prefers x and !x over x != 0 and x == 0, but my thinking was that
> other code in the repo did use comparison operators specifically
> for things like counters. Happy to change it to conform better though!
I just worry about the idea that a negative number (or an addition
overflow) would create conditions for termination that we did not
intend. That's why using the nonzero status as true/false combined
with ands and ors is better.

>> Finally, I think we actually want this case to get the benefit:
>>
>>         if ((!queue.p1_count || !queue.p2_count) &&
>>             !queue.pending_merge_bases)
>>
>> I do see that you have this condition in patch 3 with the extra
>> detail that the max generation in the queue is finite. I think this
>> is more reason to include this in the data structure method and not
>> in the loop.
> 
> Yes, but just to be clear, you don't want to merge together patch 2 and 3
> here, just grouping the halt conditions closer together
> (within paint_queue_get)? Keeping patch 2 and 3 separate would be nice
> to make it easier to show that introducing this extra counter bookkeeping
> does not negatively impact the overall performance too much.
No, I don't want you to squash them. I was perhaps unclear as I was
discovering the structure as we went. The thing I was missing above
was the "finite generation number" condition, which you make very
clear in patch 3.

Thanks,
-Stolee