1 \section{Traversal phase --- algorithm}
3 (In general, unless stated otherwise below, when we generate a new
4 commit $C$ using one of the commit kind recipies, we update
5 $W \assign C$. In any such case where we say we're going to Merge
6 with $L = W$, if $R \ge W$ we do not Merge but instead simply set
10 For each patch $\pc \in \allpatches$ in topological order by $\hasdep$,
15 \item Optionally, attempt
16 $\alg{Merge-Base}(\pc)$. This may or may not succeed.
18 \item If this didn't succeed, or was not attempted, execute
19 $\alg{Recreate-Base}(\pc)$.
21 \item Then in any case, execute
22 $\alg{Merge-Tip}(\pc)$.
26 After processing each $\pc$ we will have created $\tipcn$ and $\tipcy$
29 \statement{Correct Base}{
30 \baseof{\tipcy} = \tipcn
32 \statement{Base Correct Contents}{
37 \statement{Tip Exceeds Inputs}{
38 \tipcy \ge \pendsof{\allsrcs}{\pcy}
40 \statement{Base Exceeds Inputs' Bases}{
41 \bigforall_{E \in \pendsof{\allsrcs}{\pcy}} \tipcn \ge \baseof{E}
43 \statement{Base Exceeds Base Inputs}{
44 \bigforall_{H \in \set H^{\pn}} \tipcn \ge H
47 \subsection{$\alg{Merge-Base}(\pc)$}
49 This algorithm attempts to construct a suitably updated version of the
50 base branch $\pcn$ using some existing version of $\pcn$ as a starting
53 It should be executed noninteractively. Specifically, if any step
54 fails with a merge conflict, the whole thing should be abandoned.
55 This avoids asking the user to resolve confusing conflicts. It also
56 avoids asking the user to pointlessly resolve conflicts in situations
57 where we will later discover that $\alg{Merge-Base}$ wasn't feasible
60 If $\pc$ has only one direct dependency, this algorithm should not be
61 used as in that case $\alg{Recreate-Base}$ is trivial and guaranteed
62 to generate a perfect answer, whereas this algorithm might involve
63 merges and therefore might not produce a perfect answer if the
64 situation is complicated.
66 Initially, set $W \iassign W^{\pcn}$.
68 \subsubsection{Bases and sources}
70 In some order, perhaps interleaving the two kinds of merge:
74 \item For each $\hasdep$-maximal $\pd \isdirdep \pc$, find a merge base
75 $M \le W,\; \le \tipdy$ and merge $\tipdy$ into $W$.
76 That is, use $\alg{Merge}$ with $L = W,\; R = \tipdy$.
77 (Base Dependency Merge.)
79 \item For each $S \in S^{\pcn}_i$, merge it into $W$.
80 That is, use $\alg{Merge}$ with $L = W,\; R = S,\; M = M^{\pcn}_i$.
87 Execute $\alg{Fixup-Base}(W,\pc)$.
89 TODO define Fixup-Base
91 \subsubsection{Result}
93 If all of that was successful, let $\tipcn = W$.
95 \subsection{$\alg{Recreate-Base}(\pc)$}
101 Choose a $\hasdep$-maximal direct dependency $\pd$ of $\pc$.
105 Use $\alg{Create Base}$ with $L$ = $\tipdy,\; \pq = \pc$ to generate $C$
106 and set $W \iassign C$. (Recreate Base Beginning.)
110 Execute the subalgorithm $\alg{Recreate-Recurse}(\pc)$.
114 Declare that we contain all of the relevant information from the
115 sources. That is, use $\alg{Pseudo-Merge}$ with $L = W, \;
116 \set R = \{ W \} \cup \set S^{\pcn}$.
117 (Recreate Base Final Declaration.)
121 \subsubsection{$\alg{Recreate-Recurse}(\pd)$}
125 \item Is $W \haspatch \pd$ ? If so, there is nothing to do: return.
127 \item TODO what about non-Topbloke base branches
129 \item For all $\hasdep$-maximal $\pd' \isdirdep \pd$,
130 execute $\alg{Recreate-Recurse}(\pd')$.
132 \item Use $\alg{Pseudo-Merge}$ with $L = W,\; \set R = \{ \tipdn \}$.
133 (Recreate Base Dependency Base Declaration.)
135 \item Use $\alg{Merge}$ to apply $\pd$ to $W$. That is,
136 $L = W, \; R = \tipdy, \; M = \baseof{R} = \tipdn$.
142 \subsection{$\alg{Merge-Tip}(\pc)$}
146 \item TODO CHOOSE/REFINE W AND S as was done during Ranking for bases
148 \item $\alg{Merge}$ from $\tipcn$. That is, $L = W, \;
149 R = \tipcn$ and choose any suitable $M$. (Tip Base Merge.)
151 \item For each source $S \in \set S^{\pcy}$,
152 $\alg{Merge}$ with $L = W, \; R = S$ and any suitable $M$.