chiark / gitweb /
strategy: new, wip, found
[topbloke-formulae.git] / strategy.tex
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.
6
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.
16
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).
23
24 \section{Notation}
25
26 \begin{basedescript}{
27 \desclabelwidth{5em}
28 \desclabelstyle{\nextlinelabel}
29 }
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$.
33
34 \item[ $\pc \hasdirdep \p$ ]
35 The Topbloke commit set $\pc$ has as a direct contributor the
36 commit set $\p$.  This is an acyclic relation.
37
38 \item[ $\p \hasdep \pq$ ]
39 The commit set $\p$ has as direct or indirect contributor the commit
40 set $\pq$.
41 Acyclic; the completion of $\hasdirdep$ into a
42 partial order.
43
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).
48
49 \item[ $\pendsof{\set X}{\p} \le T$ ]
50 Convenience notation for
51 $\bigforall_{E \in \pendsof{\set X}{\p}} E \le T$
52
53 %\item[ $\set E_{\pc}$ ]
54 %$ \bigcup_i \pendsof{S_{\pc,i}}{\pc} $.
55 %All the ends of $\pc$ in the sources.
56
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.
60
61 \end{basedescript}
62
63 \stdsection{Inputs to the update algorithm}
64
65 \begin{basedescript}{
66 \desclabelwidth{5em}
67 \desclabelstyle{\nextlinelabel}
68 }
69 \item[ $\pc_0$ ]
70 The topmost patch which we are trying to update.  This and
71 all of its dependencies will be updated.
72
73 \item[ $h : \pc^{+/-} \mapsto \set H_{\pc^{+/-}}$ ]
74 Function for getting the existing heads $\set H$ of the branch $\pc^{+/-}$.
75 This will include the current local and remote git refs, as desired.
76
77 \item[ $g : \pc, \Gamma \mapsto \Gamma'$ ]
78 Function to allow explicit adjustment of the direct dependencies
79 of $\pc$.  It is provided with a putative set of direct dependencies
80 $\Gamma$ computed as an appropriate merge of the dependencies requested by the
81 sources and should return the complete actual set $\Gamma'$ of direct
82 dependencies to use.  This allows the specification of any desired
83 (acyclic) relation $\hasdirdep$.
84
85 \end{basedescript}
86
87 \section{Ranking phase}
88
89 We run the following algorithm:
90 \begin{enumerate}
91 \item Set $\allpatches = \{ \}$.
92 \item Repeatedly:
93 \begin{enumerate}
94 \item Clear out the graph $\hasdirdep$ so it has no edges.
95 \item Execute {\bf Rank-Recurse}($\pc_0$)
96 \item Until $\allpatches$ remains unchanged.
97 \end{enumerate}
98 \end{enumerate}
99
100 {\bf Rank-Recurse}($\pc$) is:
101 \begin{enumerate}
102
103 \item If we have already done {\bf Rank-Recurse}($\pc$) in this
104 ranking iteration, do nothing.  Otherwise:
105
106 \item Add $\pc$ to $\allpatches$ if it is not there already.
107
108 \item Let
109 $$
110   \set S = h(\pcn)
111      \cup 
112         \bigcup_{\p \in \allpatches}
113         \bigcup_{H \in h(\pn) \lor H \in h(\py)}
114          \{ \baseof{E} \; | \; E \in \pendsof{H}{\pcy} \}
115 $$
116
117 and $W = w(h(\pcn))$
118
119 \item While $\exists_{S \in \set S} S \ge W$,
120 update $W \assign S$ and $\set S \assign \set S \, \backslash \{ S \}$
121
122 (This will often remove $W$ from $\set S$.  Afterwards, $\set S$
123 is a collection of heads to be merged into $W$.)
124
125 \item Choose an order of $\set S$, $S_i$ for $i=1 \ldots n$.
126
127 \item For each $S_i$ in turn, choose a corresponding $M_i$
128 such that $$
129    M_i \le S_i \land \left[
130    M_i \le W \lor \bigexists_{S_i, j<i} M_i \le S_i
131    \right]
132 $$
133
134 \item Set $\Gamma = \depsreqof{W}$.
135
136 If there are multiple candidates we prefer $M_i \in \pcn$
137 if available.
138
139 \item For each $i \ldots 1..n$, update our putative direct
140 dependencies:
141 $$
142 \Gamma \assign \text{\bf set-merge}\left(\Gamma, 
143  \left[ \begin{cases} 
144   M_i \in \pcn :     & \depsreqof{M_i} \\
145   M_i \not\in \pcn : & \{ \}
146  \end{cases} \right],
147  \depsreqof{S_i}
148  \right)
149 $$
150
151 \item Finalise our putative direct dependencies
152 $
153 \Gamma \assign g(\pc, \Gamma)
154 $
155
156 \item For each direct dependency $\pd \in \Gamma$,
157
158 \begin{enumerate}
159 \item Add an edge $\pc \hasdirdep \pd$ to the digraph (adding nodes
160 as necessary).
161 If this results in a cycle, abort entirely (as the function $g$ is
162 inappropriate; a different $g$ could work.)
163 \end{enumerate}
164 \item Run ${\text{\bf Rank-Recurse}}(\pd)$.
165
166 \end{enumerate}
167
168 The results of the ranking phase are:
169
170 $ \allpatches, \hasdirdep $ and hence the completion of $\hasdirdep$
171 into the partial order $\hasdep$.
172
173 For each $\pc$, the base branch starting point commit $W_{\pcn} = W$,
174 the direct dependencies $\Gamma_{\pc}$,
175 the ordered set of base branch sources $\set S_{\pcn} = \set S,
176 S_{\pcn,i} = S_i$
177 and corresponding merge bases $M_{\pcn,i} = M_i$.
178
179 \section{Traversal phase}
180
181
182
183
184
185 \section{Planning phase}
186
187 The results of the planning phase consist of: 
188 \begin{itemize*}
189 \item{ The relation $\hasdirdep$ and hence the partial order $\hasdep$. }
190 \item{ For each commit set $\pc$, a confirmed set of sources $\set S_{\pc}$. }
191 \item{ For each commit set $\pc$, the order in which to merge the sources
192         $E_{\pc,j} \in \set E_{\pc}$. }
193 \item{ For each $E_{\pc,j}$ an intended merge base $M_{\pc,j}$. }
194 \end{itemize*}
195
196 We use a recursive planning algorith, recursing over Topbloke commit
197 sets (ie, sets $\py$ or $\pn$).  We'll call the commit set we're
198 processing at each step $\pc$.
199 At each recursive step 
200 we make a plan to merge all $\set E_{\pc} = \{ E_{\pc,j \ldots} \}$
201 and all the direct contributors of $\pc$ (as determined below)
202 into $\tipzc$, to make $\tipfc$.
203
204 We start with $\pc = \pl$ where $\pl = \patchof{L}$.
205
206
207 \subsection{Direct contributors for $\pc = \pcn$}
208
209 The direct contributors of $\pcn$ are the commit sets corresponding to
210 the tip branches for the direct dependencies of the patch $\pc$.  We
211 need to calculate what the direct dependencies are going to be.
212
213 Choose an (arbitrary, but ideally somehow optimal in
214 a way not discussed here) ordering of $\set E_{\pc}$, $E_{\pc,j}$
215 ($j = 1 \ldots m$).
216 For brevity we will write $E_j$ for $E_{\pc,j}$.
217 Remove from that set (and ordering) any $E_j$ which
218 are $\le$ and $\neq$ some other $E_k$.
219
220 Initially let $\set D_0 = \depsreqof{\tipzc}$.
221 For each $E_j$ starting with $j=1$ choose a corresponding intended
222 merge base $M_j$ such that $M_j \le E_j \land M_j \le T_{\pc,j-1}$.
223 Calculate $\set D_j$ as the 3-way merge of the sets $\set D_{j-1}$ and
224 $\depsreqof{E_j}$ using as a base $\depsreqof{M_j}$.  This will
225 generate $D_m$ as the putative direct contributors of $\pcn$.
226
227 However, the invocation may give instructions that certain direct
228 dependencies are definitely to be included, or excluded.  As a result
229 the set of actual direct contributors is some arbitrary set of patches
230 (strictly, some arbitrary set of Topbloke tip commit sets).
231
232 \subsection{Direct contributors for $\pc = \pcy$}
233
234 The sole direct contributor of $\pcy$ is $\pcn$.
235
236 \subsection{Recursive step}
237
238 For each direct contributor $\p$, we add the edge $\pc \hasdirdep \p$
239 and augment the ordering $\hasdep$ accordingly.
240
241 If this would make a cycle in $\hasdep$, we abort . The operation must
242 then be retried by the user, if desired, but with different or
243 additional instructions for modifying the direct contributors of some
244 $\pqn$ involved in the cycle.
245
246 For each such $\p$, after updating $\hasdep$, we recursively make a plan
247 for $\pc' = \p$.
248
249
250
251 \section{Execution phase}
252
253 We process commit sets from the bottom up according to the relation
254 $\hasdep$.  For each commit set $\pc$ we construct $\tipfc$ from
255 $\tipzc$, as planned.  By construction, $\hasdep$ has $\patchof{L}$
256 as its maximum, so this operation will finish by updating
257 $\tipca{\patchof{L}}$ with $\tipfa{\patchof{L}}$.
258
259 After we are done with each commit set $\pc$, the
260 new tip $\tipfc$ has the following properties:
261 \[ \eqn{Tip Sources}{
262   \bigforall_{E_i \in \set E_{\pc}} \tipfc \ge E_i
263 }\]
264 \[ \eqn{Tip Dependencies}{
265   \bigforall_{\pc \hasdep \p} \tipfc \ge \tipfa \p
266 }\]
267 \[ \eqn{Perfect Contents}{
268   \tipfc \haspatch \p \equiv \pc \hasdep \py
269 }\]
270
271 For brevity we will sometimes write $\tipu$ for $\tipuc$, etc.  We will start
272 out with $\tipc = \tipz$, and at each step of the way construct some
273 $\tipu$ from $\tipc$.  The final $\tipu$ becomes $\tipf$.
274
275 \subsection{Preparation}
276
277 Firstly, we will check each $E_i$ for being $\ge \tipc$.  If
278 it is, are we fast forward to $E_i$
279 --- formally, $\tipu = \text{max}(\tipc, E_i)$ ---
280 and drop $E_i$ from the planned ordering.
281
282 Then we will merge the direct contributors and the sources' ends.
283 This generates more commits $\tipuc \in \pc$, but none in any other
284 commit set.  We maintain
285 $$
286  \bigforall_{\p \isdep \pc}
287  \pancsof{\tipcc}{\p} \subset
288    \pancsof{\tipfa \p}{\p}
289 $$
290 \proof{
291  For $\tipcc = \tipzc$, $T$ ...WRONG WE NEED $\tipfa \p$ TO BE IN $\set E$ SOMEHOW
292 }
293
294 \subsection{Merge Contributors for $\pcy$}
295
296 Merge $\pcn$ into $\tipc$.  That is, merge with
297 $L = \tipc, R = \tipfa{\pcn}, M = \baseof{\tipc}$.
298 to construct $\tipu$.
299
300 Merge conditions:
301
302 Ingredients satisfied by construction.
303 Tip Merge satisfied by construction.  Merge Acyclic follows
304 from Perfect Contents and $\hasdep$ being acyclic.
305
306 Removal Merge Ends: For $\p = \pc$, $M \nothaspatch \p$; OK.
307 For $\p \neq \pc$, by Tip Contents,
308 $M \haspatch \p \equiv L \haspatch \p$, so we need only
309 worry about $X = R, Y = L$; ie $L \haspatch \p$,
310 $M = \baseof{L} \haspatch \p$.
311 By Tip Contents for $L$, $D \le L \equiv D \le M$.  OK.~~$\qed$
312
313 WIP UP TO HERE
314
315 Addition Merge Ends: If $\py \isdep \pcn$, we have already
316 done the execution phase for $\pcn$ and $\py$.  By
317 Perfect Contents for $\pcn$, $\tipfa \pcn \haspatch \p$ i.e.
318 $R \haspatch \p$.  So we only need to worry about $Y = R = \tipfa \pcn$.
319 By Tip Dependencies $\tipfa \pcn \ge \tipfa \py$.
320 And by Tip Sources $\tipfa \py \ge $
321
322 want to prove $E \le \tipfc$ where $E \in \pendsof{\tipcc}{\py}$
323
324 $\pancsof{\tipcc}{\py} = $
325
326
327 computed $\tipfa \py$, and by Perfect Contents for $\py$
328
329
330 with $M=M_j, L=T_{\pc,j-1}, R=E_j$,
331 and calculate what the resulting desired direct dependencies file
332 (ie, the set of patches $\set D_j$)
333 would be.  Eventually we 
334
335 So, formally, we select somehow an order of sources $S_i$.  For each 
336
337
338 Make use of the following recursive algorithm, Plan 
339
340
341
342
343  recursively make a plan to merge all $E = \pends$
344
345 Specifically, in