chiark / gitweb /
strategy: replace old \tip... macros
[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 (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.
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 patch $\pc$ has as a direct dependency the
36 patch $\p$.  This is an acyclic relation.
37
38 \item[ $\p \hasdep \pq$ ]
39 The patch $\p$ has as direct or indirect dependency the
40 patch $\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 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.
77
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$.
85
86 \end{basedescript}
87
88 \stdsection{Important variables and values in the update algorithm}
89
90 \begin{basedescript}{
91 \desclabelwidth{5em}
92 \desclabelstyle{\nextlinelabel}
93 }
94 \item[ $\Gamma_{\pc}$ ]
95 The desired direct dependencies of $\pc$, a set of patches.
96
97 \item[ $\allpatches$ ]
98 The set of all the patches we are dealing with (constructed
99 during the update algorithm).
100
101 \end{basedescript}
102
103 \section{Ranking phase}
104
105 We run the following algorithm:
106 \begin{enumerate}
107 \item Set $\allpatches = \{ \}$.
108 \item Repeatedly:
109 \begin{enumerate}
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.
113 \end{enumerate}
114 \end{enumerate}
115
116 $\alg{Rank-Recurse}(\pc)$ is:
117 \begin{enumerate}
118
119 \item If we have already done $\alg{Rank-Recurse}(\pc)$ in this
120 ranking iteration, do nothing.  Otherwise:
121
122 \item Add $\pc$ to $\allpatches$ if it is not there already.
123
124 \item Set
125 $$
126   \set S \iassign h(\pcn)
127      \cup 
128         \bigcup_{\p \in \allpatches}
129         \bigcup_{H \in h(\pn) \lor H \in h(\py)}
130          \{ \baseof{E} \; | \; E \in \pendsof{H}{\pcy} \}
131 $$
132
133 and $W \iassign w(h(\pcn))$
134
135 \item While $\exists_{S \in \set S} S \ge W$,
136 update $W \assign S$ and $\set S \assign \set S \, \backslash \{ S \}$
137
138 (This will often remove $W$ from $\set S$.  Afterwards, $\set S$
139 is a collection of heads to be merged into $W$.)
140
141 \item Choose an ordering of $\set S$, $S_i$ for $i=1 \ldots n$.
142
143 \item For each $S_i$ in turn, choose a corresponding $M_i$
144 such that $$
145    M_i \le S_i \land \left[
146    M_i \le W \lor \bigexists_{j<i} M_i \le S_j
147    \right]
148 $$
149
150 \item Set $\Gamma \iassign \depsreqof{W}$.
151
152 If there are multiple candidates we prefer $M_i \in \pcn$
153 if available.
154
155 \item For each $i \ldots 1..n$, update our putative direct
156 dependencies:
157 $$
158 \Gamma \assign \setmergeof{
159     \Gamma
160   }{
161     \begin{cases}
162      M_i \in \pcn :     & \depsreqof{M_i} \\
163      M_i \not\in \pcn : & \{ \}
164     \end{cases}
165   }{
166     \depsreqof{S_i}
167   }
168 $$
169
170 TODO define $\setmerge$
171
172 \item Finalise our putative direct dependencies
173 $
174 \Gamma \assign g(\pc, \Gamma)
175 $
176
177 \item For each direct dependency $\pd \in \Gamma$,
178
179 \begin{enumerate}
180 \item Add an edge $\pc \hasdirdep \pd$ to the digraph (adding nodes
181 as necessary).
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)$.
185 \end{enumerate}
186
187 \end{enumerate}
188
189 \subsection{Results of the ranking phase}
190
191 By the end of the ranking phase, we have recorded the following
192 information:
193
194 \begin{itemize}
195 \item
196 $ \allpatches, \hasdirdep $ and hence the completion of $\hasdirdep$
197 into the partial order $\hasdep$.
198
199 \item
200 For each $\pc \in \allpatches$,
201 the base branch starting point commit $W^{\pcn} = W$.
202
203 \item
204 For each $\pc$,
205 the direct dependencies $\Gamma^{\pc} = \Gamma$.
206
207 \item
208 For each $\pc$,
209 the ordered set of base branch sources $\set S^{\pcn} = \set S,
210 S^{\pcn}_i = S_i$
211 and corresponding merge bases $M^{\pcn}_i = M_i$.
212
213 \end{itemize}
214
215 \subsection{Proof of termination}
216
217 $\alg{Rank-Recurse}(\pc)$ recurses but only downwards through the
218 finite graph $\hasdirdep$, so it must terminate.  
219
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.
224
225 $\qed$
226
227 \section{Traversal phase}
228
229 For each patch $\pc \in \allpatches$ in topological order by $\hasdep$,
230 lowest first:
231
232 \begin{enumerate}
233
234 \item Optionally, attempt
235  $\alg{Merge-Base}(\pc)$.  This may or may not succeed.
236
237 \item If this didn't succeed, or was not attempted, execute
238  $\alg{Recreate-Base}(\pc)$.
239
240 \item Then in any case, execute
241  $\alg{Merge-Tip}(\pc)$.
242
243 \end{enumerate}
244
245 After processing each $\pc$ we will have created:
246
247 \begin{itemize}
248
249 \item tip
250
251 \end{itemize}
252
253 \subsection{$\alg{Merge-Base}(\pc)$}
254
255 This algorithm attempts to construct a suitably updated version of the
256 base branch $\pcn$.
257
258 It should be executed noninteractively.  Specifically, if any step
259 fails with a merge conflict, the whole thing should be abandoned.
260 This avoids asking the user to resolve confusing conflicts.  It also
261 avoids asking the user to pointlessly resolve conflicts in situations
262 where we will later discover that $\alg{Merge-Base}$ wasn't feasible
263 after all.
264
265 \subsubsection{Bases and sources}
266
267 In some order, perhaps interleaving the two kinds of merge:
268
269 \begin{enumerate}
270
271 \item For each $\pd \isdirdep \pc$, merge $\pd$
272
273 \item
274
275 \end{enumerate}
276
277
278