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}
\desclabelstyle{\nextlinelabel}
}
\item[ $\depsreqof{K}$ ]
The set of direct dependencies (in the form $\py$)
requested in the commit $K$ ($K \in \pn$) for the patch $\p$.
\item[ $\pc \hasdirdep \p$ ]
The Topbloke commit set $\pc$ has as a direct contributor the
commit set $\p$. This is an acyclic relation.
\item[ $\p \hasdep \pq$ ]
The commit set $\p$ has as direct or indirect contributor the commit
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.
\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}
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