From: Kristofer Karlsson Date: Mon, 22 Jun 2026 19:14:57 GMT Subject: Re: [PATCH/RFC 2/6] commit-reach: introduce struct paint_queue with per-side counters Message-ID: In-Reply-To: On Mon, 22 Jun 2026 at 20:10, Derrick Stolee wrote: > > On 6/20/2026 6:36 AM, Kristofer Karlsson via GitGitGadget wrote: > > From: Kristofer Karlsson > > > + if (!(old_paint & STALE)) { > > + switch (old_paint & (PARENT1 | PARENT2)) { > > + case 0: break; > > + case PARENT1: queue->p1_count--; break; > > + case PARENT2: queue->p2_count--; break; > > + case PARENT1 | PARENT2: queue->pending_merge_bases--; break; > > + default: BUG("unexpected paint state"); > > + } > > + } > > + if (!(new_paint & STALE)) { > > + switch (new_paint & (PARENT1 | PARENT2)) { > > + case 0: break; > > + case PARENT1: queue->p1_count++; break; > > + case PARENT2: queue->p2_count++; break; > > + case PARENT1 | PARENT2: queue->pending_merge_bases++; break; > > + default: BUG("unexpected paint state"); > > + } > > + } > > While correct and compact, I don't believe that these switch > statements follow the coding guidelines. We should split the > lines appropriately so they are more standard, such as: > > if (!(new_paint & STALE)) { > switch (new_paint & (PARENT1 | PARENT2)) { > case 0: > break; > > case PARENT1: > queue->p1_count++; > break; > > case PARENT2: > queue->p2_count++; > break; > > case PARENT1 | PARENT2: > queue->pending_merge_bases++; > break; > > default: > BUG("unexpected paint state"); > } > } Agreed, I will change to that style. I did try to look for style guidelines but I missed the .clang-format file (I was only looking through text files). Apologies, will remember clang-format for next time (and v2) > 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. > > -static void clear_nonstale_queue(struct nonstale_queue *queue) > > +static void paint_queue_put(struct paint_queue *queue, > > + struct commit *c, unsigned add_flags) > > { > > - clear_prio_queue(&queue->pq); > > - queue->max_nonstale = NULL; > > -} > > + unsigned old_flags = c->object.flags; > > + c->object.flags |= add_flags; > > Diffs like this are part of the reason I'd like to see a _new_ > data structure instead of replacing the old one. Keeping the > old one for ahead_behind seems like a good idea to me, but even > if we don't land on that end state then deleting the old code > _after_ adding the new code will make the diff more readable. Agreed, will address that. > > - struct nonstale_queue queue = { > > - { compare_commits_by_gen_then_commit_date } > > + struct paint_queue queue = { > > + .pq = { compare_commits_by_gen_then_commit_date } > > }; > > I didn't notice when reading the struct definition, but looking at > 'pq' here makes me think that we shouldn't be using that abbreviation > as it could stand for "prio_queue" or "paint_queue". Good point, I should pick a longer name for the field. Perhaps simply queue (I want to avoid prio_queue since it exactly matches the name of the struct which could be confusing.) > > + 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. > 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! > 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. Thanks! I appreciate the thorough review of this patch (which I feared was the most annoying one to look at). Kristofer