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

On 6/22/2026 3:14 PM, Kristofer Karlsson wrote:

On Mon, 22 Jun 2026 at 20:10, Derrick Stolee [off-list ref] wrote:

quoted

quoted

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.

quoted

quoted

+     while ((commit = paint_queue_get(&queue))) {

...> +

quoted

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

quoted

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.

quoted

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