X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?p=topbloke-formulae.git;a=blobdiff_plain;f=strategy.tex;h=a4716b313dd577c5e74c6e1a7afe4f39ba8be082;hp=9bed7cf094dd3f0a8940ff8d9a0338cb982e6b6a;hb=f4b799f5604417c83c799c3ff513864502f5ef67;hpb=64a3ef281cdbfa63f1c306222d6e3e2b507d21a0 diff --git a/strategy.tex b/strategy.tex index 9bed7cf..a4716b3 100644 --- a/strategy.tex +++ b/strategy.tex @@ -6,7 +6,7 @@ remove dependencies from patches. Broadly speaking the update proceeds as follows: during the Ranking phase we construct the intended graph of dependencies between patches -(which involves select a merge order for the base branch of each +(and incidentally select a merge order for the base branch of each patch). Then during the Traversal phase we walk that graph from the bottom up, constructing for each patch by a series of merges and other operations first a new base branch head commit and then a new tip @@ -50,12 +50,9 @@ the $\le$-maximal elements of $\bigcup_{J \in \set J} \pendsof{J}{\p}$ Convenience notation for $\bigforall_{E \in \pendsof{\set X}{\p}} E \le T$ -\item[ $\Gamma_{\pc}$ ] -The desired direct dependencies of $\pc$, a set of patches. - -\item[ $\allpatches$ ] -The set of all the patches we are dealing with (constructed -during the update algorithm). +\item[ $\allsrcs$ ] +$\bigcup_{\p \in \allpatches} \set H^{\pn} \cup \set H^{\py}$. +All the input commits to the update algorithm. (See below.) %\item[ $\set E_{\pc}$ ] %$\bigcup_i \pendsof{S_{\pc,i}}{\pc}$. @@ -77,7 +74,7 @@ during the update algorithm). The topmost patch which we are trying to update. This and all of its dependencies will be updated. -\item[ $h : \pc^{+/-} \mapsto \set H_{\pc^{+/-}}$ ] +\item[ $h : \pc^{+/-} \mapsto \set H^{\pc^{+/-}}$ ] Function for getting the existing heads $\set H$ of the branch $\pc^{+/-}$. These are the heads which will be merged and used in this update. This will include the current local and remote git refs, as desired. @@ -92,278 +89,38 @@ dependencies to use. This allows the specification of any desired \end{basedescript} -\section{Ranking phase} - -We run the following algorithm: -\begin{enumerate} -\item Set $\allpatches = \{ \}$. -\item Repeatedly: -\begin{enumerate} -\item Clear out the graph $\hasdirdep$ so it has no edges. -\item Execute {\bf Rank-Recurse}($\pc_0$) -\item Until $\allpatches$ remains unchanged. -\end{enumerate} -\end{enumerate} - -{\bf Rank-Recurse}($\pc$) is: -\begin{enumerate} - -\item If we have already done {\bf Rank-Recurse}($\pc$) in this -ranking iteration, do nothing. Otherwise: - -\item Add $\pc$ to $\allpatches$ if it is not there already. - -\item Let -$$- \set S = h(\pcn) - \cup - \bigcup_{\p \in \allpatches} - \bigcup_{H \in h(\pn) \lor H \in h(\py)} - \{ \baseof{E} \; | \; E \in \pendsof{H}{\pcy} \} -$$ - -and $W = w(h(\pcn))$ - -\item While $\exists_{S \in \set S} S \ge W$, -update $W \assign S$ and $\set S \assign \set S \, \backslash \{ S \}$ - -(This will often remove $W$ from $\set S$. Afterwards, $\set S$ -is a collection of heads to be merged into $W$.) - -\item Choose an order of $\set S$, $S_i$ for $i=1 \ldots n$. - -\item For each $S_i$ in turn, choose a corresponding $M_i$ -such that  - M_i \le S_i \land \left[ - M_i \le W \lor \bigexists_{S_i, j