annotate foreign ends too

[topbloke-formulae.git] / strategy.tex

diff --git a/strategy.tex b/strategy.tex
index 62998371becf379d9aea154b32663e7d034c0ae2..0f03ddb9883200fed514b821df14948994e78aca 100644 (file)
--- a/strategy.tex
+++ b/strategy.tex
@@ -98,6 +98,11 @@ The desired direct dependencies of $\pc$, a set of patches.
 The set of all the patches we are dealing with (constructed
 during the update algorithm).
 
 The set of all the patches we are dealing with (constructed
 during the update algorithm).
 

+\item[ $\tipcn, \tipcy$ ]
+The new tips of the git branches $\pcn$ and $\pcy$, containing
+all the correct commits (and the correct other patches), as
+generated by the Traversal phase of the update algorithm.
+

 \end{basedescript}
 
 \section{Ranking phase}
 \end{basedescript}
 
 \section{Ranking phase}


@@ -224,7 +229,14 @@ this must complete eventually.
 
 $\qed$
 
 
 $\qed$
 

-\section{Traversal phase}
+\section{Traversal phase --- algorithm}
+
+(In general, unless stated otherwise below, when we generate a new
+commit $C$ using one of the commit kind algorith, we update
+$W \assign C$.  In any such case where we say we're going to Merge
+with $L = W$, if $R \ge W$ we do not Merge but instead simply set
+$W \assign R$.)
+

 
 For each patch $\pc \in \allpatches$ in topological order by $\hasdep$,
 lowest first:
 
 For each patch $\pc \in \allpatches$ in topological order by $\hasdep$,
 lowest first:


@@ -246,14 +258,15 @@ After processing each $\pc$ we will have created:
 
 \begin{itemize}
 
 
 \begin{itemize}
 

-\item tip
+\item $\tipcn$ and $\tipcy$ such that $\baseof{\tipcy} = \tipcn$.

 
 \end{itemize}
 
 \subsection{$\alg{Merge-Base}(\pc)$}
 
 This algorithm attempts to construct a suitably updated version of the
 
 \end{itemize}
 
 \subsection{$\alg{Merge-Base}(\pc)$}
 
 This algorithm attempts to construct a suitably updated version of the

-base branch $\pcn$.
+base branch $\pcn$ using some existing version of $\pcn$ as a starting
+point.

 
 It should be executed noninteractively.  Specifically, if any step
 fails with a merge conflict, the whole thing should be abandoned.
 
 It should be executed noninteractively.  Specifically, if any step
 fails with a merge conflict, the whole thing should be abandoned.


@@ -262,17 +275,103 @@ avoids asking the user to pointlessly resolve conflicts in situations
 where we will later discover that $\alg{Merge-Base}$ wasn't feasible
 after all.
 
 where we will later discover that $\alg{Merge-Base}$ wasn't feasible
 after all.
 

+If $\pc$ has only one direct dependency, this algorithm should not be
+used as in that case $\alg{Recreate-Base}$ is trivial and guaranteed
+to generate a perfect answer, whereas this algorithm might involve
+merges and therefore might not produce a perfect answer if the
+situation is complicated.
+
+Initially, set $W \iassign W^{\pcn}$.
+

 \subsubsection{Bases and sources}
 
 In some order, perhaps interleaving the two kinds of merge:
 
 \begin{enumerate}
 
 \subsubsection{Bases and sources}
 
 In some order, perhaps interleaving the two kinds of merge:
 
 \begin{enumerate}
 

-\item For each $\pd \isdirdep \pc$, merge $\pd$
+\item For each $\pd \isdirdep \pc$, find a merge base
+$M \le W,\; \le \tipdy$ and merge $\tipdy$ into $W$.
+That is, use $\alg{Merge}$ with $L = W,\; R = \tipdy$.
+(Dependency Merge.)
+
+\item For each $S \in S^{\pcn}_i$, merge it into $W$.
+That is, use $\alg{Merge}$ with $L = W,\; R = S,\; M = M^{\pcn}_i$.
+(Base Sibling Merge.)
+
+\end{enumerate}
+
+\subsubsection{Fixup}
+
+Execute $\alg{Fixup-Base}(W,\pc)$.
+
+
+\subsection{$\alg{Recreate-Base}(\pc)$}
+
+\begin{enumerate}
+
+\item
+
+Choose a $\hasdep$-maximal direct dependency $\pd$ of $\pc$.
+
+\item
+
+Use $\alg{Create Base}$ with $L$ = $\pdy,\; \pq = \pc$ to generate $C$
+and set $W \iassign C$.  (Recreate Base Beginning.)
+
+\item
+
+Execute the subalgorithm $\alg{Recreate-Recurse}(\pc)$.

 
 \item
 
 
 \item
 

+Declare that we contain all of the relevant information from the
+sources.  That is, use $\alg{Pseudo-merge}$ with $L = W, \;
+\set R = \{ W \} \cup \set S^{\pcn}$.
+(Recreate Base Final Declaration.)
+
+\end{enumerate}
+
+\subsubsection{$\alg{Recreate-Recurse}(\pd)$}
+
+\begin{enumerate}
+
+\item Is $W \haspatch \pd$ ?  If so, there is nothing to do: return.
+
+\item TODO what about non-Topbloke base branches
+
+\item Use $\alg{Pseudo-Merge}$ with $L = W,\; \set R = \{ \tipdn \}$.
+(Recreate Base Dependency Base Declaration.)
+
+\item For all $\hasdep$-maximal $\pd' \isdirdep \pd$,
+execute $\alg{Recreate-Recurse}(\pd')$.
+
+\item Use $\alg{Merge}$ to apply $\pd$ to $W$.  That is,
+$L = W, \; R = \tipdy, \; M = \baseof{R} = \tipdn$.
+(Recreate Reapply.)
+

 \end{enumerate}
 
 
 \end{enumerate}
 
 

+\subsection{$\alg{Merge-Tip}(\pc)$}
+
+\begin{enumerate}
+
+\item TODO CHOOSE/REFINE W AND S as was done during Ranking for bases
+
+\item $\alg{Merge}$ from $\tipcn$.  That is, $L = W, \;
+R = \tipcn$ and choose any suitable $M$.  (Tip Base Merge.)
+
+\item For each source $S \in \set S^{\pcy}$,
+$\alg{Merge}$ with $L = W, \; R = S$ and any suitable $M$.
+(Tip Source Merge.)
+
+\end{enumerate}
+
+
+\section{Traversal phase --- proofs}
+
+For each operation called for by the traversal algorithms, we prove
+that the commit generation preconditions are met.
+
+\subsection{Tip Base Merge}