From: Kristofer Karlsson Date: Mon, 22 Jun 2026 19:30:16 GMT Subject: Re: [PATCH/RFC 6/6] Documentation/technical: add paint-down-to-common doc Message-ID: In-Reply-To: <50dd5fb1-6b4e-448c-977c-cdc476f7fe40@gmail.com> On Mon, 22 Jun 2026 at 20:21, Derrick Stolee wrote: > > I like the idea of documenting this so it's easier to understand. Yes I was myself thinking that I can prove it to myself now that it works, and anyone else could also prove it to themselves, but having it explicit here is even better. I found the other documents (i.e. commit-graph) to be a good source of inspiration here. > 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. Good idea, will add that. > > +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. I did consider that initially but I was worried it would be considered noisy. I am quite happy to rework it in a way that first explains the status quo. That would make the document diff more interesting. Agreed that should become the first patch, and the patch that changes the algorithm should include the documentation change. > 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. Agreed, I would need to rephrase from tracking non-stale to tracking counts of p1 and p2 (and pending merge bases) commits, but I think that would be a small tweak and well worth doing. Thanks, Kristofer