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 (which involves 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[ $\Gamma_{\pc}$ ]
54 The desired direct dependencies of $\pc$, a set of patches.
56 \item[ $\allpatches$ ]
57 The set of all the patches we are dealing with (constructed
58 during the update algorithm).
60 %\item[ $\set E_{\pc}$ ]
61 %$ \bigcup_i \pendsof{S_{\pc,i}}{\pc} $.
62 %All the ends of $\pc$ in the sources.
64 %\item[ $ \tipzc, \tipcc, \tipuc, \tipfc $ ]
65 %The git ref for the Topbloke commit set $\pc$: respectively,
66 %the original, current, updated, and final values.
70 \stdsection{Inputs to the update algorithm}
74 \desclabelstyle{\nextlinelabel}
77 The topmost patch which we are trying to update. This and
78 all of its dependencies will be updated.
80 \item[ $h : \pc^{+/-} \mapsto \set H_{\pc^{+/-}}$ ]
81 Function for getting the existing heads $\set H$ of the branch $\pc^{+/-}$.
82 These are the heads which will be merged and used in this update.
83 This will include the current local and remote git refs, as desired.
85 \item[ $g : \pc, \Gamma \mapsto \Gamma'$ ]
86 Function to allow explicit adjustment of the direct dependencies
87 of $\pc$. It is provided with a putative set of direct dependencies
88 $\Gamma$ computed as an appropriate merge of the dependencies requested by the
89 sources and should return the complete actual set $\Gamma'$ of direct
90 dependencies to use. This allows the specification of any desired
91 (acyclic) relations $\hasdirdep$ and $\hasdep$.
95 \section{Ranking phase}
97 We run the following algorithm:
99 \item Set $\allpatches = \{ \}$.
102 \item Clear out the graph $\hasdirdep$ so it has no edges.
103 \item Execute {\bf Rank-Recurse}($\pc_0$)
104 \item Until $\allpatches$ remains unchanged.
108 {\bf Rank-Recurse}($\pc$) is:
111 \item If we have already done {\bf Rank-Recurse}($\pc$) in this
112 ranking iteration, do nothing. Otherwise:
114 \item Add $\pc$ to $\allpatches$ if it is not there already.
120 \bigcup_{\p \in \allpatches}
121 \bigcup_{H \in h(\pn) \lor H \in h(\py)}
122 \{ \baseof{E} \; | \; E \in \pendsof{H}{\pcy} \}
127 \item While $\exists_{S \in \set S} S \ge W$,
128 update $W \assign S$ and $\set S \assign \set S \, \backslash \{ S \}$
130 (This will often remove $W$ from $\set S$. Afterwards, $\set S$
131 is a collection of heads to be merged into $W$.)
133 \item Choose an order of $\set S$, $S_i$ for $i=1 \ldots n$.
135 \item For each $S_i$ in turn, choose a corresponding $M_i$
137 M_i \le S_i \land \left[
138 M_i \le W \lor \bigexists_{S_i, j<i} M_i \le S_i
142 \item Set $\Gamma = \depsreqof{W}$.
144 If there are multiple candidates we prefer $M_i \in \pcn$
147 \item For each $i \ldots 1..n$, update our putative direct
150 \Gamma \assign \text{\bf set-merge}\left[\Gamma,
152 M_i \in \pcn : & \depsreqof{M_i} \\
153 M_i \not\in \pcn : & \{ \}
159 TODO define {\bf set-merge}
161 \item Finalise our putative direct dependencies
163 \Gamma \assign g(\pc, \Gamma)
166 \item For each direct dependency $\pd \in \Gamma$,
169 \item Add an edge $\pc \hasdirdep \pd$ to the digraph (adding nodes
171 If this results in a cycle, abort entirely (as the function $g$ is
172 inappropriate; a different $g$ could work.)
174 \item Run ${\text{\bf Rank-Recurse}}(\pd)$.
178 \subsection{Results of the ranking phase}
180 By the end of the ranking phase, we have recorded the following
185 $ \allpatches, \hasdirdep $ and hence the completion of $\hasdirdep$
186 into the partial order $\hasdep$.
189 For each $\pc \in \allpatches$, the base branch starting point commit $W_{\pcn} = W$.
193 the direct dependencies $\Gamma_{\pc}$.
197 the ordered set of base branch sources $\set S_{\pcn} = \set S,
199 and corresponding merge bases $M_{\pcn,i} = M_i$.
203 \section{Traversal phase}
209 \section{Planning phase}
211 The results of the planning phase consist of:
213 \item{ The relation $\hasdirdep$ and hence the partial order $\hasdep$. }
214 \item{ For each commit set $\pc$, a confirmed set of sources $\set S_{\pc}$. }
215 \item{ For each commit set $\pc$, the order in which to merge the sources
216 $E_{\pc,j} \in \set E_{\pc}$. }
217 \item{ For each $E_{\pc,j}$ an intended merge base $M_{\pc,j}$. }
220 We use a recursive planning algorith, recursing over Topbloke commit
221 sets (ie, sets $\py$ or $\pn$). We'll call the commit set we're
222 processing at each step $\pc$.
223 At each recursive step
224 we make a plan to merge all $\set E_{\pc} = \{ E_{\pc,j \ldots} \}$
225 and all the direct contributors of $\pc$ (as determined below)
226 into $\tipzc$, to make $\tipfc$.
228 We start with $\pc = \pl$ where $\pl = \patchof{L}$.
231 \subsection{Direct contributors for $\pc = \pcn$}
233 The direct contributors of $\pcn$ are the commit sets corresponding to
234 the tip branches for the direct dependencies of the patch $\pc$. We
235 need to calculate what the direct dependencies are going to be.
237 Choose an (arbitrary, but ideally somehow optimal in
238 a way not discussed here) ordering of $\set E_{\pc}$, $E_{\pc,j}$
240 For brevity we will write $E_j$ for $E_{\pc,j}$.
241 Remove from that set (and ordering) any $E_j$ which
242 are $\le$ and $\neq$ some other $E_k$.
244 Initially let $\set D_0 = \depsreqof{\tipzc}$.
245 For each $E_j$ starting with $j=1$ choose a corresponding intended
246 merge base $M_j$ such that $M_j \le E_j \land M_j \le T_{\pc,j-1}$.
247 Calculate $\set D_j$ as the 3-way merge of the sets $\set D_{j-1}$ and
248 $\depsreqof{E_j}$ using as a base $\depsreqof{M_j}$. This will
249 generate $D_m$ as the putative direct contributors of $\pcn$.
251 However, the invocation may give instructions that certain direct
252 dependencies are definitely to be included, or excluded. As a result
253 the set of actual direct contributors is some arbitrary set of patches
254 (strictly, some arbitrary set of Topbloke tip commit sets).
256 \subsection{Direct contributors for $\pc = \pcy$}
258 The sole direct contributor of $\pcy$ is $\pcn$.
260 \subsection{Recursive step}
262 For each direct contributor $\p$, we add the edge $\pc \hasdirdep \p$
263 and augment the ordering $\hasdep$ accordingly.
265 If this would make a cycle in $\hasdep$, we abort . The operation must
266 then be retried by the user, if desired, but with different or
267 additional instructions for modifying the direct contributors of some
268 $\pqn$ involved in the cycle.
270 For each such $\p$, after updating $\hasdep$, we recursively make a plan
275 \section{Execution phase}
277 We process commit sets from the bottom up according to the relation
278 $\hasdep$. For each commit set $\pc$ we construct $\tipfc$ from
279 $\tipzc$, as planned. By construction, $\hasdep$ has $\patchof{L}$
280 as its maximum, so this operation will finish by updating
281 $\tipca{\patchof{L}}$ with $\tipfa{\patchof{L}}$.
283 After we are done with each commit set $\pc$, the
284 new tip $\tipfc$ has the following properties:
285 \[ \eqn{Tip Sources}{
286 \bigforall_{E_i \in \set E_{\pc}} \tipfc \ge E_i
288 \[ \eqn{Tip Dependencies}{
289 \bigforall_{\pc \hasdep \p} \tipfc \ge \tipfa \p
291 \[ \eqn{Perfect Contents}{
292 \tipfc \haspatch \p \equiv \pc \hasdep \py
295 For brevity we will sometimes write $\tipu$ for $\tipuc$, etc. We will start
296 out with $\tipc = \tipz$, and at each step of the way construct some
297 $\tipu$ from $\tipc$. The final $\tipu$ becomes $\tipf$.
299 \subsection{Preparation}
301 Firstly, we will check each $E_i$ for being $\ge \tipc$. If
302 it is, are we fast forward to $E_i$
303 --- formally, $\tipu = \text{max}(\tipc, E_i)$ ---
304 and drop $E_i$ from the planned ordering.
306 Then we will merge the direct contributors and the sources' ends.
307 This generates more commits $\tipuc \in \pc$, but none in any other
308 commit set. We maintain
310 \bigforall_{\p \isdep \pc}
311 \pancsof{\tipcc}{\p} \subset
312 \pancsof{\tipfa \p}{\p}
315 For $\tipcc = \tipzc$, $T$ ...WRONG WE NEED $\tipfa \p$ TO BE IN $\set E$ SOMEHOW
318 \subsection{Merge Contributors for $\pcy$}
320 Merge $\pcn$ into $\tipc$. That is, merge with
321 $L = \tipc, R = \tipfa{\pcn}, M = \baseof{\tipc}$.
322 to construct $\tipu$.
326 Ingredients satisfied by construction.
327 Tip Merge satisfied by construction. Merge Acyclic follows
328 from Perfect Contents and $\hasdep$ being acyclic.
330 Removal Merge Ends: For $\p = \pc$, $M \nothaspatch \p$; OK.
331 For $\p \neq \pc$, by Tip Contents,
332 $M \haspatch \p \equiv L \haspatch \p$, so we need only
333 worry about $X = R, Y = L$; ie $L \haspatch \p$,
334 $M = \baseof{L} \haspatch \p$.
335 By Tip Contents for $L$, $D \le L \equiv D \le M$. OK.~~$\qed$
339 Addition Merge Ends: If $\py \isdep \pcn$, we have already
340 done the execution phase for $\pcn$ and $\py$. By
341 Perfect Contents for $\pcn$, $\tipfa \pcn \haspatch \p$ i.e.
342 $R \haspatch \p$. So we only need to worry about $Y = R = \tipfa \pcn$.
343 By Tip Dependencies $\tipfa \pcn \ge \tipfa \py$.
344 And by Tip Sources $\tipfa \py \ge $
346 want to prove $E \le \tipfc$ where $E \in \pendsof{\tipcc}{\py}$
348 $\pancsof{\tipcc}{\py} = $
351 computed $\tipfa \py$, and by Perfect Contents for $\py$
354 with $M=M_j, L=T_{\pc,j-1}, R=E_j$,
355 and calculate what the resulting desired direct dependencies file
356 (ie, the set of patches $\set D_j$)
357 would be. Eventually we
359 So, formally, we select somehow an order of sources $S_i$. For each
362 Make use of the following recursive algorithm, Plan
367 recursively make a plan to merge all $E = \pends$