1 Here we describe the update algorithm. This is responsible for
2 refreshing patches against updated versions of their dependencies,
3 for merging different versions of the various braches created by
4 distributed development, and for implementing decisions to add and
5 remove dependencies from patches.
7 Broadly speaking the update proceeds as follows: during the Ranking
8 phase we construct the intended graph of dependencies between patches
9 (and incidentally select a merge order for the base branch of each
10 patch). Then during the Traversal phase we walk that graph from the
11 bottom up, constructing for each patch by a series of merges and other
12 operations first a new base branch head commit and then a new tip
13 branch head commit. These new head commits are maximums - that is,
14 each has as ancestors all of its branches' sources and indeed all
15 relevant commits in that branch.
17 We have two possible strategies for constructing new base branch
18 heads: we can either Merge (works incrementally even if there the
19 patch has multiple dependencies, but may sometimes not be possible) or
20 we can Regenerate (trivial if there is a single dependency, and is
21 always possible, but may involve the user re-resolving conflicts if
22 there are multiple dependencies).
28 \desclabelstyle{\nextlinelabel}
30 \item[ $\depsreqof{K}$ ]
31 The set of direct dependencies (in the form $\py$)
32 requested in the commit $K$ ($K \in \pn$) for the patch $\p$.
34 \item[ $\pc \hasdirdep \p$ ]
35 The patch $\pc$ has as a direct dependency the
36 patch $\p$. This is an acyclic relation.
38 \item[ $\p \hasdep \pq$ ]
39 The patch $\p$ has as direct or indirect dependency the
41 Acyclic; the completion of $\hasdirdep$ into a
44 \item[ $\pendsof{\set J}{\p}$ ]
45 Convenience notation for
46 the $\le$-maximal elements of $\bigcup_{J \in \set J} \pendsof{J}{\p}$
47 (where $\set J$ is some set of commits).
49 \item[ $\pendsof{\set X}{\p} \le T$ ]
50 Convenience notation for
51 $\bigforall_{E \in \pendsof{\set X}{\p}} E \le T$
53 %\item[ $\set E_{\pc}$ ]
54 %$ \bigcup_i \pendsof{S_{\pc,i}}{\pc} $.
55 %All the ends of $\pc$ in the sources.
57 %\item[ $ \tipzc, \tipcc, \tipuc, \tipfc $ ]
58 %The git ref for the Topbloke commit set $\pc$: respectively,
59 %the original, current, updated, and final values.
63 \stdsection{Inputs to the update algorithm}
67 \desclabelstyle{\nextlinelabel}
70 The topmost patch which we are trying to update. This and
71 all of its dependencies will be updated.
73 \item[ $h : \pc^{+/-} \mapsto \set H_{\pc^{+/-}}$ ]
74 Function for getting the existing heads $\set H$ of the branch $\pc^{+/-}$.
75 These are the heads which will be merged and used in this update.
76 This will include the current local and remote git refs, as desired.
78 \item[ $g : \pc, \Gamma \mapsto \Gamma'$ ]
79 Function to allow explicit adjustment of the direct dependencies
80 of $\pc$. It is provided with a putative set of direct dependencies
81 $\Gamma$ computed as an appropriate merge of the dependencies requested by the
82 sources and should return the complete actual set $\Gamma'$ of direct
83 dependencies to use. This allows the specification of any desired
84 (acyclic) relations $\hasdirdep$ and $\hasdep$.
88 \stdsection{Important variables and values in the update algorithm}
92 \desclabelstyle{\nextlinelabel}
94 \item[ $\Gamma_{\pc}$ ]
95 The desired direct dependencies of $\pc$, a set of patches.
97 \item[ $\allpatches$ ]
98 The set of all the patches we are dealing with (constructed
99 during the update algorithm).
101 \item[ $\tipcn, \tipcy$ ]
102 The new tips of the git branches $\pcn$ and $\pcy$, containing
103 all the correct commits (and the correct other patches), as
104 generated by the Traversal phase of the update algorithm.
108 \section{Ranking phase}
110 We run the following algorithm:
112 \item Set $\allpatches = \{ \}$.
115 \item Clear out the graph $\hasdirdep$ so it has no edges.
116 \item Execute $\alg{Rank-Recurse}(\pc_0)$
117 \item Until $\allpatches$ remains unchanged.
121 $\alg{Rank-Recurse}(\pc)$ is:
124 \item If we have already done $\alg{Rank-Recurse}(\pc)$ in this
125 ranking iteration, do nothing. Otherwise:
127 \item Add $\pc$ to $\allpatches$ if it is not there already.
131 \set S \iassign h(\pcn)
133 \bigcup_{\p \in \allpatches}
134 \bigcup_{H \in h(\pn) \lor H \in h(\py)}
135 \{ \baseof{E} \; | \; E \in \pendsof{H}{\pcy} \}
138 and $W \iassign w(h(\pcn))$
140 \item While $\exists_{S \in \set S} S \ge W$,
141 update $W \assign S$ and $\set S \assign \set S \, \backslash \{ S \}$
143 (This will often remove $W$ from $\set S$. Afterwards, $\set S$
144 is a collection of heads to be merged into $W$.)
146 \item Choose an ordering of $\set S$, $S_i$ for $i=1 \ldots n$.
148 \item For each $S_i$ in turn, choose a corresponding $M_i$
150 M_i \le S_i \land \left[
151 M_i \le W \lor \bigexists_{j<i} M_i \le S_j
155 \item Set $\Gamma \iassign \depsreqof{W}$.
157 If there are multiple candidates we prefer $M_i \in \pcn$
160 \item For each $i \ldots 1..n$, update our putative direct
163 \Gamma \assign \setmergeof{
167 M_i \in \pcn : & \depsreqof{M_i} \\
168 M_i \not\in \pcn : & \{ \}
175 TODO define $\setmerge$
177 \item Finalise our putative direct dependencies
179 \Gamma \assign g(\pc, \Gamma)
182 \item For each direct dependency $\pd \in \Gamma$,
185 \item Add an edge $\pc \hasdirdep \pd$ to the digraph (adding nodes
187 If this results in a cycle, abort entirely (as the function $g$ is
188 inappropriate; a different $g$ could work).
189 \item Run $\alg{Rank-Recurse}(\pd)$.
194 \subsection{Results of the ranking phase}
196 By the end of the ranking phase, we have recorded the following
201 $ \allpatches, \hasdirdep $ and hence the completion of $\hasdirdep$
202 into the partial order $\hasdep$.
205 For each $\pc \in \allpatches$,
206 the base branch starting point commit $W^{\pcn} = W$.
210 the direct dependencies $\Gamma^{\pc} = \Gamma$.
214 the ordered set of base branch sources $\set S^{\pcn} = \set S,
216 and corresponding merge bases $M^{\pcn}_i = M_i$.
220 \subsection{Proof of termination}
222 $\alg{Rank-Recurse}(\pc)$ recurses but only downwards through the
223 finite graph $\hasdirdep$, so it must terminate.
225 The whole ranking algorithm iterates but each iteration involves
226 adding one or more patches to $\allpatches$. Since there are
227 finitely many patches and we never remove anything from $\allpatches$
228 this must complete eventually.
232 \section{Traversal phase --- algorithm}
234 (In general, unless stated otherwise below, when we generate a new
235 commit $C$ using one of the commit kind algorith, we update
236 $W \assign C$. In any such case where we say we're going to Merge
237 with $L = W$, if $R \ge W$ we do not Merge but instead simply set
241 For each patch $\pc \in \allpatches$ in topological order by $\hasdep$,
246 \item Optionally, attempt
247 $\alg{Merge-Base}(\pc)$. This may or may not succeed.
249 \item If this didn't succeed, or was not attempted, execute
250 $\alg{Recreate-Base}(\pc)$.
252 \item Then in any case, execute
253 $\alg{Merge-Tip}(\pc)$.
257 After processing each $\pc$ we will have created:
261 \item $\tipcn$ and $\tipcy$ such that $\baseof{\tipcy} = \tipcn$.
265 \subsection{$\alg{Merge-Base}(\pc)$}
267 This algorithm attempts to construct a suitably updated version of the
268 base branch $\pcn$ using some existing version of $\pcn$ as a starting
271 It should be executed noninteractively. Specifically, if any step
272 fails with a merge conflict, the whole thing should be abandoned.
273 This avoids asking the user to resolve confusing conflicts. It also
274 avoids asking the user to pointlessly resolve conflicts in situations
275 where we will later discover that $\alg{Merge-Base}$ wasn't feasible
278 If $\pc$ has only one direct dependency, this algorithm should not be
279 used as in that case $\alg{Recreate-Base}$ is trivial and guaranteed
280 to generate a perfect answer, whereas this algorithm might involve
281 merges and therefore might not produce a perfect answer if the
282 situation is complicated.
284 Initially, set $W \iassign W^{\pcn}$.
286 \subsubsection{Bases and sources}
288 In some order, perhaps interleaving the two kinds of merge:
292 \item For each $\pd \isdirdep \pc$, find a merge base
293 $M \le W,\; \le \tipdy$ and merge $\tipdy$ into $W$.
294 That is, use $\alg{Merge}$ with $L = W,\; R = \tipdy$.
297 \item For each $S \in S^{\pcn}_i$, merge it into $W$.
298 That is, use $\alg{Merge}$ with $L = W,\; R = S,\; M = M^{\pcn}_i$.
299 (Base Sibling Merge.)
303 \subsubsection{Fixup}
305 Execute $\alg{Fixup-Base}(W,\pc)$.
308 \subsection{$\alg{Recreate-Base}(\pc)$}
314 Choose a $\hasdep$-maximal direct dependency $\pd$ of $\pc$.
318 Use $\alg{Create Base}$ with $L$ = $\pdy,\; \pq = \pc$ to generate $C$
319 and set $W \iassign C$. (Recreate Base Beginning.)
323 Execute the subalgorithm $\alg{Recreate-Recurse}(\pc)$.
327 Declare that we contain all of the relevant information from the
328 sources. That is, use $\alg{Pseudo-merge}$ with $L = W, \;
329 \set R = \{ W \} \cup \set S^{\pcn}$.
330 (Recreate Base Final Declaration.)
334 \subsubsection{$\alg{Recreate-Recurse}(\pd)$}
338 \item Is $W \haspatch \pd$ ? If so, there is nothing to do: return.
340 \item TODO what about non-Topbloke base branches
342 \item Use $\alg{Pseudo-Merge}$ with $L = W,\; \set R = \{ \tipdn \}$.
343 (Recreate Base Dependency Base Declaration.)
345 \item For all $\hasdep$-maximal $\pd' \isdirdep \pd$,
346 execute $\alg{Recreate-Recurse}(\pd')$.
348 \item Use $\alg{Merge}$ to apply $\pd$ to $W$. That is,
349 $L = W, \; R = \tipdy, \; M = \baseof{R} = \tipdn$.
355 \subsection{$\alg{Merge-Tip}(\pc)$}
359 \item TODO CHOOSE/REFINE W AND S as was done during Ranking for bases
361 \item $\alg{Merge}$ from $\tipcn$. That is, $L = W, \;
362 R = \tipcn$ and choose any suitable $M$. (Tip Base Merge.)
364 \item For each source $S \in \set S^{\pcy}$,
365 $\alg{Merge}$ with $L = W, \; R = S$ and any suitable $M$.
371 \section{Traversal phase --- proofs}
373 For each operation called for by the traversal algorithms, we prove
374 that the commit generation preconditions are met.
376 \subsection{Tip Base Merge}