strategy: traversal wip

diff --git a/strategy.tex b/strategy.tex
index 62998371becf379d9aea154b32663e7d034c0ae2..7ceff45fb8ade776b0d6a8184d6358023e87b73a 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}


@@ -226,6 +231,13 @@ $\qed$
 
 \section{Traversal phase}
 
 
 \section{Traversal phase}
 

+(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,71 @@ 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
 
 
 \item
 

+Use $\alg{Create Base}$ with $L$ = $\pdy,\; \pq = \pc$ to generate $C$
+and set $W \iassign C$.
+
+\item
+
+Execute the subalgorithm $\alg{Recreate-Recurse}(\pc)$.
+

 \end{enumerate}
 
 \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 Psuedo-merge.)

 
 

+\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}