chiark / gitweb /
abe24410def1fdeb757404dc30f0d9cbe7ce4f1c
[topbloke-formulae.git] / trav-alg.tex
1 \section{Traversal phase --- algorithm}
2
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
7 $W \assign R$.)
8
9
10 For each patch $\pc \in \allpatches$ in topological order by $\hasdep$,
11 lowest first:
12
13 \begin{enumerate}
14
15 \item Optionally, attempt
16  $\alg{Merge-Base}(\pc)$.  This may or may not succeed.
17
18 \item If this didn't succeed, or was not attempted, execute
19  $\alg{Recreate-Base}(\pc)$.
20
21 \item Then in any case, execute
22  $\alg{Merge-Tip}(\pc)$.
23
24 \end{enumerate}
25
26 After processing each $\pc$ we will have created $\tipcn$ and $\tipcy$
27 such that:
28
29 \statement{Correct Base}{
30   \baseof{\tipcy} = \tipcn
31 }
32 \statement{Tip Exceeds Inputs}{
33   \tipcy \ge \pendsof{\allsrcs}{\pcy}
34 }
35 \statement{Base Exceeds Inputs' Bases}{
36   \bigforall_{E \in \pendsof{\allsrcs}{\pcy}} \tipcn \ge \baseof{E}
37 }
38 \statement{Base Exceeds Base Inputs}{
39   \bigforall_{H \in \set H^{\pn}} \tipcn \ge H
40 }
41
42 \subsection{$\alg{Merge-Base}(\pc)$}
43
44 This algorithm attempts to construct a suitably updated version of the
45 base branch $\pcn$ using some existing version of $\pcn$ as a starting
46 point.
47
48 It should be executed noninteractively.  Specifically, if any step
49 fails with a merge conflict, the whole thing should be abandoned.
50 This avoids asking the user to resolve confusing conflicts.  It also
51 avoids asking the user to pointlessly resolve conflicts in situations
52 where we will later discover that $\alg{Merge-Base}$ wasn't feasible
53 after all.
54
55 If $\pc$ has only one direct dependency, this algorithm should not be
56 used as in that case $\alg{Recreate-Base}$ is trivial and guaranteed
57 to generate a perfect answer, whereas this algorithm might involve
58 merges and therefore might not produce a perfect answer if the
59 situation is complicated.
60
61 Initially, set $W \iassign W^{\pcn}$.
62
63 \subsubsection{Bases and sources}
64
65 In some order, perhaps interleaving the two kinds of merge:
66
67 \begin{enumerate}
68
69 \item For each $\hasdep$-maximal $\pd \isdirdep \pc$, find a merge base
70 $M \le W,\; \le \tipdy$ and merge $\tipdy$ into $W$.
71 That is, use $\alg{Merge}$ with $L = W,\; R = \tipdy$.
72 (Base Dependency Merge.)
73
74 \item For each $S \in S^{\pcn}_i$, merge it into $W$.
75 That is, use $\alg{Merge}$ with $L = W,\; R = S,\; M = M^{\pcn}_i$.
76 (Base Sibling Merge.)
77
78 \end{enumerate}
79
80 \subsubsection{Fixup}
81
82 Execute $\alg{Fixup-Base}(W,\pc)$.
83
84 TODO define Fixup-Base
85
86 \subsubsection{Result}
87
88 If all of that was successful, let $\tipcn = W$.
89
90 \subsection{$\alg{Recreate-Base}(\pc)$}
91
92 \begin{enumerate}
93
94 \item
95
96 Choose a $\hasdep$-maximal direct dependency $\pd$ of $\pc$.
97
98 \item
99
100 Use $\alg{Create Base}$ with $L$ = $\pdy,\; \pq = \pc$ to generate $C$
101 and set $W \iassign C$.  (Recreate Base Beginning.)
102
103 \item
104
105 Execute the subalgorithm $\alg{Recreate-Recurse}(\pc)$.
106
107 \item
108
109 Declare that we contain all of the relevant information from the
110 sources.  That is, use $\alg{Pseudo-Merge}$ with $L = W, \;
111 \set R = \{ W \} \cup \set S^{\pcn}$.
112 (Recreate Base Final Declaration.)
113
114 \end{enumerate}
115
116 \subsubsection{$\alg{Recreate-Recurse}(\pd)$}
117
118 \begin{enumerate}
119
120 \item Is $W \haspatch \pd$ ?  If so, there is nothing to do: return.
121
122 \item TODO what about non-Topbloke base branches
123
124 \item For all $\hasdep$-maximal $\pd' \isdirdep \pd$,
125 execute $\alg{Recreate-Recurse}(\pd')$.
126
127 \item Use $\alg{Pseudo-Merge}$ with $L = W,\; \set R = \{ \tipdn \}$.
128 (Recreate Base Dependency Base Declaration.)
129
130 \item Use $\alg{Merge}$ to apply $\pd$ to $W$.  That is,
131 $L = W, \; R = \tipdy, \; M = \baseof{R} = \tipdn$.
132 (Recreate Reapply.)
133
134 \end{enumerate}
135
136
137 \subsection{$\alg{Merge-Tip}(\pc)$}
138
139 \begin{enumerate}
140
141 \item TODO CHOOSE/REFINE W AND S as was done during Ranking for bases
142
143 \item $\alg{Merge}$ from $\tipcn$.  That is, $L = W, \;
144 R = \tipcn$ and choose any suitable $M$.  (Tip Base Merge.)
145
146 \item For each source $S \in \set S^{\pcy}$,
147 $\alg{Merge}$ with $L = W, \; R = S$ and any suitable $M$.
148 (Tip Source Merge.)
149
150 \end{enumerate}
151
152