X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?a=blobdiff_plain;f=strategy.tex;h=c8a0bfe41846f830e22019a152b950ac53648286;hb=8a59e774f52ee89b29274d3148a3b72707adedc9;hp=eff0adfd8ca423dd3668b48c386189f352d086cc;hpb=f89923e74f62530c7aa6633bf2b13fec8ec1bfc0;p=topbloke-formulae.git

diff --git a/strategy.tex b/strategy.tex
index eff0adf..c8a0bfe 100644
--- a/strategy.tex
+++ b/strategy.tex
@@ -1,10 +1,27 @@
-When we are trying to do an update of some kind, in general,
-for each patch $\pc$
-we want to merge some source commits $S \in \set S_{\pc}$.
-We require $\patchof{S} = \pc$,
-and $\tipcc \in \set S_{\pc}$.
-
-\stdsection{Notation}
+Here we describe the update algorithm.  This is responsible for
+refreshing patches against updated versions of their dependencies,
+for merging different versions of the various braches created by
+distributed development, and for implementing decisions to add and
+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
+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
+branch head commit.  These new head commits are maximums - that is,
+each has as ancestors all of its branches' sources and indeed all
+relevant commits in that branch.
+
+We have two possible strategies for constructing new base branch
+heads: we can either Merge (works incrementally even if there the
+patch has multiple dependencies, but may sometimes not be possible) or
+we can Regenerate (trivial if there is a single dependency, and is
+always possible, but may involve the user re-resolving conflicts if
+there are multiple dependencies).
+
+\section{Notation}
 
 \begin{basedescript}{
 \desclabelwidth{5em}
@@ -24,16 +41,74 @@ set $\pq$.
 Acyclic; the completion of $\hasdirdep$ into a
 partial order.
 
+\item[ $\pendsof{\set J}{\p}$ ]
+Convenience notation for
+the maximal elements of $\bigcup_{J \in \set J} \pendsof{J}{\p}$
+(where $\set J$ is some set of commits).
+
+\item[ $\pendsof{\set X}{\p} \le T$ ]
+Convenience notation for
+$\bigforall_{E \in \pendsof{\set X}{\p}} E \le T$
+
 %\item[ $\set E_{\pc}$ ]
 %$ \bigcup_i \pendsof{S_{\pc,i}}{\pc} $.
 %All the ends of $\pc$ in the sources.
 
-\item[ $ \tipzc, \tipcc, \tipuc, \tipfc $ ]
-The git ref for the Topbloke commit set $\pc$: respectively,
-the original, current, updated, and final values.
+%\item[ $ \tipzc, \tipcc, \tipuc, \tipfc $ ]
+%The git ref for the Topbloke commit set $\pc$: respectively,
+%the original, current, updated, and final values.
+
+\end{basedescript}
+
+\stdsection{Inputs to the update algorithm}
+
+\begin{basedescript}{
+\desclabelwidth{5em}
+\desclabelstyle{\nextlinelabel}
+}
+\item[ $\pc_0$ ]
+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^{+/-}}$ ]
+Function for getting the existing heads $\set H$ of the branch $\pc^{+/-}$.
+This will include the current local and remote git refs, as desired.
+
+\item[ $g : \pc, \Gamma \mapsto \Gamma'$ ]
+Function to allow explicit adjustment of the direct dependencies
+of $\pc$.  It is provided with a putative set of direct dependencies
+$\Gamma$ computed as an appropriate merge of the dependencies requested by the
+sources and should return the complete actual set $\Gamma'$ of direct
+dependencies to use.  This allows the specification of any desired
+(acyclic) relation $\hasdirdep$.
 
 \end{basedescript}
 
+\section{Ranking phase}
+
+{\bf Ranking} is:
+\begin{enumerate}
+\item Set $\allpatches = \{ \}$.
+\item Repeatedly:
+\begin{enumerate}
+\item Clear out the graph $\hasdirdep$ so it has neither nodes nor 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 Add $\pc$ to $\allpatches$ if it is not there already.
+\item Let $\set S_{\pcn} = h(\pcn)
+     \cup 
+        \bigcup_{\p \in \allpatches}
+        \bigcup_{H \in h(\pn) \lor H \in h(\py)}
+         \{ \baseof{E} \; | \; E \in \pendsof{H}{\pcy} \} $.
+
+(We write $\set S = \set S_{\pcn}$ when it's not ambiguous.)
+\end{enumerate}
+
 \section{Planning phase}
 
 The results of the planning phase consist of: