-\section{Traversal phase --- algorithm}
+\section{Traversal phase}
-(In general, unless stated otherwise below, when we generate a new
+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 commit generation operation called for by the traversal
-algorithms, we prove that the commit generation preconditions are met.)
+algorithms, we prove that the commit generation preconditions are met.
+
+\subsection{Algorithm}
For each patch $\pc \in \allpatches$ in topological order by $\hasdep$,
lowest first:
\end{enumerate}
+\subsection{Results}
+
After processing each $\pc$ we will have created $\tipcn$ and $\tipcy$
such that:
-
\statement{Correct Base}{
\baseof{\tipcy} = \tipcn
}
and set $W \iassign C$.
\commitproof{
- Create Acyclic: by Tip Correct Contents of $L$,
- $L \haspatch \pa E \equiv \pa E = \pd \lor \pa E \isdep \pd$.
- Now $\pd \isdirdep \pc$,
- so by Coherence, and setting $\pa E = \pc$,
- $L \nothaspatch \pc$. I.e. $L \nothaspatch \pq$. OK.
-
+ \condproof{Create Acyclic}{
+ by Tip Correct Contents of $L$,
+ $L \haspatch \pa E \equiv \pa E = \pd \lor \pa E \isdep \pd$.
+ Now $\pd \isdirdep \pc$,
+ so by Coherence, and setting $\pa E = \pc$,
+ $L \nothaspatch \pc$. I.e. $L \nothaspatch \pq$. OK.
+ }
That's everything for Create Base.
}
\set R = \{ W \} \cup \set S^{\pcn}$.
\commitproof{
- Base Only: $\patchof{W} = \patchof{L} = \pn$. OK.
+ \condproof{Base Only}{ $\patchof{W} = \patchof{L} = \pn$. OK. }
- Unique Tips:
- Want to prove that for any $\p \isin C$, $\tipdy$ is a suitable $T$.
- WIP TODO
+ \condproof{Unique Tips}{
+ Want to prove that for any $\p \isin C$, $\tipdy$ is a suitable $T$.
+ WIP TODO
+ }
WIP TODO INCOMPLETE
}
\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$.
+R = \tipcn$ and $M = \baseof{W}$.
\commitproof{
- $L = W$, $R = \tipcn$.
+ \condproof{Ingredients}{
+ $M \le L$ is trivial. For $M \le R$ we want
+ $\tipcn \ge \baseof{W}$.
+ Well $W \in \set S^{\pcy}$ so $W \in \allreachof{\pcn}$
+ and $W \in \pcy$. So $W \in \pendsof{\allreachof{\pcn}}{\pcy}$
+ so Base Covers Reachable indeed
+ $\tipcn \ge \baseof{W}$.
+ }
+ \condproof{Tip Merge}{ Trivial. }
+ \condproof{Merge Acyclic}{
+ By Base Acyclic, $\tipcn \nothaspatch \p$.
+ }
+ \condproof{Foreign Merges}{ Not applicable. }
+
TODO TBD
Afterwards, $\baseof{W} = \tipcn$.