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).
103 \section{Ranking phase}
105 We run the following algorithm:
107 \item Set $\allpatches = \{ \}$.
110 \item Clear out the graph $\hasdirdep$ so it has no edges.
111 \item Execute $\alg{Rank-Recurse}(\pc_0)$
112 \item Until $\allpatches$ remains unchanged.
116 $\alg{Rank-Recurse}(\pc)$ is:
119 \item If we have already done $\alg{Rank-Recurse}(\pc)$ in this
120 ranking iteration, do nothing. Otherwise:
122 \item Add $\pc$ to $\allpatches$ if it is not there already.
126 \set S \iassign h(\pcn)
128 \bigcup_{\p \in \allpatches}
129 \bigcup_{H \in h(\pn) \lor H \in h(\py)}
130 \{ \baseof{E} \; | \; E \in \pendsof{H}{\pcy} \}
133 and $W \iassign w(h(\pcn))$
135 \item While $\exists_{S \in \set S} S \ge W$,
136 update $W \assign S$ and $\set S \assign \set S \, \backslash \{ S \}$
138 (This will often remove $W$ from $\set S$. Afterwards, $\set S$
139 is a collection of heads to be merged into $W$.)
141 \item Choose an ordering of $\set S$, $S_i$ for $i=1 \ldots n$.
143 \item For each $S_i$ in turn, choose a corresponding $M_i$
145 M_i \le S_i \land \left[
146 M_i \le W \lor \bigexists_{j<i} M_i \le S_j
150 \item Set $\Gamma \iassign \depsreqof{W}$.
152 If there are multiple candidates we prefer $M_i \in \pcn$
155 \item For each $i \ldots 1..n$, update our putative direct
158 \Gamma \assign \setmergeof{
162 M_i \in \pcn : & \depsreqof{M_i} \\
163 M_i \not\in \pcn : & \{ \}
170 TODO define $\setmerge$
172 \item Finalise our putative direct dependencies
174 \Gamma \assign g(\pc, \Gamma)
177 \item For each direct dependency $\pd \in \Gamma$,
180 \item Add an edge $\pc \hasdirdep \pd$ to the digraph (adding nodes
182 If this results in a cycle, abort entirely (as the function $g$ is
183 inappropriate; a different $g$ could work).
184 \item Run $\alg{Rank-Recurse}(\pd)$.
189 \subsection{Results of the ranking phase}
191 By the end of the ranking phase, we have recorded the following
196 $ \allpatches, \hasdirdep $ and hence the completion of $\hasdirdep$
197 into the partial order $\hasdep$.
200 For each $\pc \in \allpatches$,
201 the base branch starting point commit $W^{\pcn} = W$.
205 the direct dependencies $\Gamma^{\pc} = \Gamma$.
209 the ordered set of base branch sources $\set S^{\pcn} = \set S,
211 and corresponding merge bases $M^{\pcn}_i = M_i$.
215 \subsection{Proof of termination}
217 $\alg{Rank-Recurse}(\pc)$ recurses but only downwards through the
218 finite graph $\hasdirdep$, so it must terminate.
220 The whole ranking algorithm iterates but each iteration involves
221 adding one or more patches to $\allpatches$. Since there are
222 finitely many patches and we never remove anything from $\allpatches$
223 this must complete eventually.
227 \section{Traversal phase}
229 For each patch $\pc \in \allpatches$ in topological order by $\hasdep$,
234 \item Optionally, attempt
235 $\alg{Merge-Base}(\pc)$. This may or may not succeed.
237 \item If this didn't succeed, or was not attempted, execute
238 $\alg{Recreate-Base}(\pc)$.
240 \item Then in any case, execute
241 $\alg{Merge-Tip}(\pc)$.
245 After processing each $\pc$
247 \subsection{$\alg{Merge-Base}(\pc)$}
249 This algorithm attempts to construct a suitably updated version of the
252 It should be executed noninteractively. Specifically, if any step
253 fails with a merge conflict, the whole thing should be abandoned.
254 This avoids asking the user to resolve confusing conflicts. It also
255 avoids asking the user to pointlessly resolve conflicts in situations
256 where we will later discover that $\alg{Merge-Base}$ wasn't feasible
259 \subsubsection{Bases and sources}
261 In some order, perhaps interleaving the two kinds of merge:
265 \item For each $\pd \isdirdep$
274 \section{Planning phase}
276 The results of the planning phase consist of:
278 \item{ The relation $\hasdirdep$ and hence the partial order $\hasdep$. }
279 \item{ For each commit set $\pc$, a confirmed set of sources $\set S_{\pc}$. }
280 \item{ For each commit set $\pc$, the order in which to merge the sources
281 $E_{\pc,j} \in \set E_{\pc}$. }
282 \item{ For each $E_{\pc,j}$ an intended merge base $M_{\pc,j}$. }
285 We use a recursive planning algorith, recursing over Topbloke commit
286 sets (ie, sets $\py$ or $\pn$). We'll call the commit set we're
287 processing at each step $\pc$.
288 At each recursive step
289 we make a plan to merge all $\set E_{\pc} = \{ E_{\pc,j \ldots} \}$
290 and all the direct contributors of $\pc$ (as determined below)
291 into $\tipzc$, to make $\tipfc$.
293 We start with $\pc = \pl$ where $\pl = \patchof{L}$.
296 \subsection{Direct contributors for $\pc = \pcn$}
298 The direct contributors of $\pcn$ are the commit sets corresponding to
299 the tip branches for the direct dependencies of the patch $\pc$. We
300 need to calculate what the direct dependencies are going to be.
302 Choose an (arbitrary, but ideally somehow optimal in
303 a way not discussed here) ordering of $\set E_{\pc}$, $E_{\pc,j}$
305 For brevity we will write $E_j$ for $E_{\pc,j}$.
306 Remove from that set (and ordering) any $E_j$ which
307 are $\le$ and $\neq$ some other $E_k$.
309 Initially let $\set D_0 = \depsreqof{\tipzc}$.
310 For each $E_j$ starting with $j=1$ choose a corresponding intended
311 merge base $M_j$ such that $M_j \le E_j \land M_j \le T_{\pc,j-1}$.
312 Calculate $\set D_j$ as the 3-way merge of the sets $\set D_{j-1}$ and
313 $\depsreqof{E_j}$ using as a base $\depsreqof{M_j}$. This will
314 generate $D_m$ as the putative direct contributors of $\pcn$.
316 However, the invocation may give instructions that certain direct
317 dependencies are definitely to be included, or excluded. As a result
318 the set of actual direct contributors is some arbitrary set of patches
319 (strictly, some arbitrary set of Topbloke tip commit sets).
321 \subsection{Direct contributors for $\pc = \pcy$}
323 The sole direct contributor of $\pcy$ is $\pcn$.
325 \subsection{Recursive step}
327 For each direct contributor $\p$, we add the edge $\pc \hasdirdep \p$
328 and augment the ordering $\hasdep$ accordingly.
330 If this would make a cycle in $\hasdep$, we abort . The operation must
331 then be retried by the user, if desired, but with different or
332 additional instructions for modifying the direct contributors of some
333 $\pqn$ involved in the cycle.
335 For each such $\p$, after updating $\hasdep$, we recursively make a plan
340 \section{Execution phase}
342 We process commit sets from the bottom up according to the relation
343 $\hasdep$. For each commit set $\pc$ we construct $\tipfc$ from
344 $\tipzc$, as planned. By construction, $\hasdep$ has $\patchof{L}$
345 as its maximum, so this operation will finish by updating
346 $\tipca{\patchof{L}}$ with $\tipfa{\patchof{L}}$.
348 After we are done with each commit set $\pc$, the
349 new tip $\tipfc$ has the following properties:
350 \[ \eqn{Tip Sources}{
351 \bigforall_{E_i \in \set E_{\pc}} \tipfc \ge E_i
353 \[ \eqn{Tip Dependencies}{
354 \bigforall_{\pc \hasdep \p} \tipfc \ge \tipfa \p
356 \[ \eqn{Perfect Contents}{
357 \tipfc \haspatch \p \equiv \pc \hasdep \py
360 For brevity we will sometimes write $\tipu$ for $\tipuc$, etc. We will start
361 out with $\tipc = \tipz$, and at each step of the way construct some
362 $\tipu$ from $\tipc$. The final $\tipu$ becomes $\tipf$.
364 \subsection{Preparation}
366 Firstly, we will check each $E_i$ for being $\ge \tipc$. If
367 it is, are we fast forward to $E_i$
368 --- formally, $\tipu = \text{max}(\tipc, E_i)$ ---
369 and drop $E_i$ from the planned ordering.
371 Then we will merge the direct contributors and the sources' ends.
372 This generates more commits $\tipuc \in \pc$, but none in any other
373 commit set. We maintain
375 \bigforall_{\p \isdep \pc}
376 \pancsof{\tipcc}{\p} \subset
377 \pancsof{\tipfa \p}{\p}
380 For $\tipcc = \tipzc$, $T$ ...WRONG WE NEED $\tipfa \p$ TO BE IN $\set E$ SOMEHOW
383 \subsection{Merge Contributors for $\pcy$}
385 Merge $\pcn$ into $\tipc$. That is, merge with
386 $L = \tipc, R = \tipfa{\pcn}, M = \baseof{\tipc}$.
387 to construct $\tipu$.
391 Ingredients satisfied by construction.
392 Tip Merge satisfied by construction. Merge Acyclic follows
393 from Perfect Contents and $\hasdep$ being acyclic.
395 Removal Merge Ends: For $\p = \pc$, $M \nothaspatch \p$; OK.
396 For $\p \neq \pc$, by Tip Contents,
397 $M \haspatch \p \equiv L \haspatch \p$, so we need only
398 worry about $X = R, Y = L$; ie $L \haspatch \p$,
399 $M = \baseof{L} \haspatch \p$.
400 By Tip Contents for $L$, $D \le L \equiv D \le M$. OK.~~$\qed$
404 Addition Merge Ends: If $\py \isdep \pcn$, we have already
405 done the execution phase for $\pcn$ and $\py$. By
406 Perfect Contents for $\pcn$, $\tipfa \pcn \haspatch \p$ i.e.
407 $R \haspatch \p$. So we only need to worry about $Y = R = \tipfa \pcn$.
408 By Tip Dependencies $\tipfa \pcn \ge \tipfa \py$.
409 And by Tip Sources $\tipfa \py \ge $
411 want to prove $E \le \tipfc$ where $E \in \pendsof{\tipcc}{\py}$
413 $\pancsof{\tipcc}{\py} = $
416 computed $\tipfa \py$, and by Perfect Contents for $\py$
419 with $M=M_j, L=T_{\pc,j-1}, R=E_j$,
420 and calculate what the resulting desired direct dependencies file
421 (ie, the set of patches $\set D_j$)
422 would be. Eventually we
424 So, formally, we select somehow an order of sources $S_i$. For each
427 Make use of the following recursive algorithm, Plan
432 recursively make a plan to merge all $E = \pends$