@matheusbsbs / matheus-bagliano
Code Commits Pulls CI/CD 82,128
seen
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.