Re: [PATCH] revision: use priority queue in limit_list()

[Jeff King <peff@peff.net>]

On Thu, May 14, 2026 at 04:51:31PM +0000, Kristofer Karlsson via GitGitGadget wrote:

> @@ -1451,6 +1447,7 @@ static int limit_list(struct rev_info *revs)
>  	struct commit_list *newlist = NULL;
>  	struct commit_list **p = &newlist;
>  	struct commit *interesting_cache = NULL;
> +	struct prio_queue queue = { .compare = compare_commits_by_commit_date };
>  
>  	if (revs->ancestry_path_implicit_bottoms) {
>  		collect_bottom_commits(original_list,
> @@ -1461,6 +1458,11 @@ static int limit_list(struct rev_info *revs)
>  
>  	while (original_list) {
>  		struct commit *commit = pop_commit(&original_list);
> +		prio_queue_put(&queue, commit);
> +	}
> +
> +	while (queue.nr) {
> +		struct commit *commit = prio_queue_get(&queue);

Here we push the whole starting list into the prio-queue, which will let
us pull the commits out in date order. But is the incoming list always
in date order?

If revs->unsorted_input, then we don't sort the initial list. So we'd
now see the commits in a different order, and put them onto newlist in
that different order.

I _think_ it may not matter because we don't call limit_list() when
revs->no_walk is set, and we only have revs->unsorted_input when no_walk
is also set. If that wasn't true, it would get weird when limit_list()
calls process_parents(), which uses commit_list_insert_by_date().


I was on the lookout for this issue particularly because I have another
patch which converts revs.commits to a prio_queue totally. And I
remember running into issues (and the solution is that sometimes the
prio_queue has a NULL comparator and acts like a LIFO queue). But if my
analysis is right above, we can ignore that for now. And if we
eventually move to revs.commits as a prio_queue, then it will just slot
in nicely here (we can drop the queue generation step and just use it
directly).

The rest of the patch looks as I'd expect from what my other patch does.

-Peff