Re: [PATCH/RFC 6/6] Documentation/technical: add paint-down-to-common doc

From: Derrick Stolee <stolee@gmail.com>
Date: Jun 22, 2026, 18:21 UTC
Message-ID: <50dd5fb1-6b4e-448c-977c-cdc476f7fe40@gmail.com>
In-Reply-To: <9cbfc67d724d91b9abc3621f03a3c97208c76a70.1781951820.git.gitgitgadget@gmail.com>

On 6/20/2026 6:36 AM, Kristofer Karlsson via GitGitGadget wrote:

> From: Kristofer Karlsson <krka@spotify.com>
> 
> Add a technical document describing the paint_down_to_common()
> algorithm used for merge-base computation.

I like the idea of documenting this so it's easier to understand.

There is risk of drift from the actual implementation. You may want to add a comment to the method in commit-reach.c to indicate that any change should be reflected in this document.

Show 11 quoted lines

> +Termination
> +-----------
> +
> +Termination happens when we can prove that no extra progress is
> +possible. We are done with the main loop when one of the following
> +conditions holds:
> +
> +  1. The queue is empty.
> +  2. The queue only contains STALE entries.
> +  3. Side-exhaustion: the walk has reached the finite region and one
> +     of the sides is fully exhausted.

It could be an interesting exercise, but potentially wasteful, to add this document as a Patch 1, but reflecting the old algorithm and then to update the document at the same time as you update the code.

The changes in your patch 2 would impact this doc in terms of the data being tracked by the paint_queue data structure instead of the nonstale_queue structure (though those details are not currently handled in the current version). The change to the termination condition would come along with patch 3.

Thanks, -Stolee