paint-down-to-common.adoc · leroysheep/BookAlchemy

test

bisect jch maint master next seen test todo

adoc 154 lines 6.11 KB

Raw

1	Merge-Base Computation and paint_down_to_common()
2	==================================================
3
4	The function `paint_down_to_common()` in `commit-reach.c` computes merge
5	bases by walking the commit graph backwards from two sets of tips and
6	finding where their ancestry meets.
7
8	Use cases
9	---------
10
11	Computing merge bases is used in two different ways:
12
13	1. Finding all merge bases (`merge-base --all`, `merge-tree`,
14	`merge`, `rebase`). A merge base is a common ancestor that is
15	not itself an ancestor of another common ancestor.
16
17	2. Ancestry checks (`in_merge_bases`, used by `merge-base
18	--is-ancestor`, `branch -d`, `fetch`). These ask: "is commit A
19	an ancestor of commit B?" If a common ancestor equals one of the
20	inputs, that input is necessarily the only merge base -- no other
21	common ancestor can be both as recent and not an ancestor of it.
22
23	Both use cases share the same algorithm and implementation.
24
25	Algorithm
26	---------
27
28	Given a commit `one` and a set of commits `twos[]`, the walk paints
29	commits with two colors:
30
31	- PARENT1: reachable from `one`
32	- PARENT2: reachable from any commit in `twos[]`
33
34	The walk uses a priority queue ordered by generation number
35	(highest first), breaking ties by commit date. Each step dequeues
36	the highest-priority commit (this is when we say a commit is
37	"visited") and propagates its paint flags to its parents, enqueuing
38	them if they gained new flags. When a commit receives both PARENT1
39	and PARENT2, it is a merge-base candidate. A candidate gains the
40	STALE flag so its ancestors propagate staleness -- any deeper common
41	ancestor is necessarily redundant.
42
43	[[generation-regions]]
44	INFINITY and finite generation regions
45	--------------------------------------
46
47	The commit-graph stores a generation number for each commit.
48	Commits not in the commit-graph have generation
49	`GENERATION_NUMBER_INFINITY`. The graph is closed under
50	reachability: if a commit is in the graph, all its ancestors are
51	too. This partitions the commit graph into two regions:
52
53	....
54	+---------------------------------------+
55	\| INFINITY region \|
56	\| generation = INFINITY \|
57	\| queue order: heuristic (commit date) \|
58	+---------------------------------------+
59	\|
60	v
61	+---------------------------------------+
62	\| Finite region \|
63	\| generation = finite \|
64	\| queue order: topological \|
65	+---------------------------------------+
66	....
67
68	When the commit-graph is enabled, the INFINITY region is typically
69	very small -- it only contains commits added since the last
70	commit-graph refresh.
71
72	All reachable INFINITY-generation commits are visited before any
73	finite-generation commit, because INFINITY is larger than any finite
74	value. Once the walk crosses into the finite region, it stays there.
75
76	In the finite region, generation ordering guarantees topological
77	traversal: children are always visited before their parents. This
78	means that paint on already-visited commits is final -- no future
79	traversal step can add paint to them.
80
81	In the INFINITY region, all commits share the same generation
82	value, so the queue breaks ties by commit date. This can violate
83	topological ordering: a parent with a later date can be visited
84	before a child with an earlier date. Paint flags are therefore
85	NOT final at visit time, and a commit visited with only one
86	side's paint may later gain the other.
87
88	Paint flags are only added, never removed. Since each flag can be set
89	at most once per commit, the number of times a commit can be
90	re-enqueued is bounded by the number of flag transitions.
91
92	Termination
93	-----------
94
95	The walk tracks the number of commits of each type in the queue
96	(PARENT1-only, PARENT2-only, pending merge-base). The main loop
97	ends when one of the following conditions holds:
98
99	1. The queue is empty.
100	2. The queue contains only stale entries.
101	3. Generation cutoff: the dequeued commit's generation is below
102	a caller-supplied `min_generation` threshold.
103	4. Single result: the caller only needs one merge base, one has
104	been found, and the walk has entered the finite-generation
105	region.
106	5. Side exhaustion: no pure PARENT1 or pure PARENT2 commits
107	remain in the queue, no pending merge-base candidates exist,
108	and the walk has entered the finite-generation region.
109
110	Stale entry condition
111	~~~~~~~~~~~~~~~~~~~~~
112	Once all queued entries are stale, no new merge-base candidates can
113	be discovered -- that requires at least one non-stale commit from
114	each side meeting. Continuing the walk could still invalidate
115	existing candidates by proving one is an ancestor of another, but
116	`remove_redundant()` handles that as a post-processing step, so it
117	is safe to exit early.
118
119	Side-exhaustion condition
120	~~~~~~~~~~~~~~~~~~~~~~~~~
121	A new merge-base requires commits from both sides to meet. When one
122	side's exclusive counter reaches zero and there are no pending
123	merge-base candidates, no future traversal step can produce a new
124	candidate.
125
126	This optimization only activates in the finite-generation region
127	where topological ordering holds. In that region, children are
128	always visited before parents, so paint flags are final at visit
129	time and an exhausted side cannot reappear. In the INFINITY region,
130	commit-date ordering can violate this guarantee, so the check is
131	skipped.
132
133	Generation cutoff
134	~~~~~~~~~~~~~~~~~
135	Some callers (notably `remove_redundant()`) supply a `min_generation`
136	threshold -- the minimum generation of the input commits. No merge
137	base can have a generation below this threshold, so the walk
138	terminates as soon as it dequeues such a commit.
139
140	Single result
141	~~~~~~~~~~~~~
142	When only one merge base is needed, the walk is in the
143	finite-generation region, and the queue uses generation ordering,
144	the first candidate found is necessarily the highest-generation
145	common ancestor. No remaining commit in the queue can be a
146	descendant of this candidate (generation ordering guarantees
147	children are visited first), so it cannot be redundant and the walk
148	can stop immediately.
149
150	Related documentation
151	---------------------
152
153	- `Documentation/technical/commit-graph.adoc` -- generation numbers
154	and the reachability closure property.