\section{Traversal phase --- algorithm}

(In general, unless stated otherwise below, when we generate a new
commit $C$ using one of the commit kind recipies, 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:

\begin{enumerate}

\item Optionally, attempt
 $\alg{Merge-Base}(\pc)$.  This may or may not succeed.

\item If this didn't succeed, or was not attempted, execute
 $\alg{Recreate-Base}(\pc)$.

\item Then in any case, execute
 $\alg{Merge-Tip}(\pc)$.

\end{enumerate}

After processing each $\pc$ we will have created $\tipcn$ and $\tipcy$
such that:

\statement{Correct Base}{
  \baseof{\tipcy} = \tipcn
}
\statement{Tip Exceeds Inputs}{
  \tipcy \ge \pendsof{\allsrcs}{\pcy}
}
\statement{Base Exceeds Inputs' Bases}{
  \bigforall_{E \in \pendsof{\allsrcs}{\pcy}} \tipcn \ge \baseof{E}
}
\statement{Base Exceeds Base Inputs}{
  \bigforall_{H \in \set H^{\pn}} \tipcn \ge H
}

\subsection{$\alg{Merge-Base}(\pc)$}

This algorithm attempts to construct a suitably updated version of the
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.
This avoids asking the user to resolve confusing conflicts.  It also
avoids asking the user to pointlessly resolve conflicts in situations
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}

\item For each $\hasdep$-maximal $\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$.
(Base 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)$.

\subsubsection{Result}

If all of that was successful, let $\tipcn = W$.

\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

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 For all $\hasdep$-maximal $\pd' \isdirdep \pd$,
execute $\alg{Recreate-Recurse}(\pd')$.

\item Use $\alg{Pseudo-Merge}$ with $L = W,\; \set R = \{ \tipdn \}$.
(Recreate Base Dependency Base Declaration.)

\item Use $\alg{Merge}$ to apply $\pd$ to $W$.  That is,
$L = W, \; R = \tipdy, \; M = \baseof{R} = \tipdn$.
(Recreate Reapply.)

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


