strategy: traversal, Tip-Merge, from base, Foreign Merges

[topbloke-formulae.git] / traversal.tex

diff --git a/traversal.tex b/traversal.tex
index c9647ad7e6ea93d98c08f0177cb709df1c035328..ab1e6d4ade011651642cbc61bf8ac5ab3e3a4aae 100644 (file)
--- a/traversal.tex
+++ b/traversal.tex
@@ -1,13 +1,15 @@
-\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:
@@ -25,9 +27,10 @@ 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
 }
@@ -151,12 +154,13 @@ Use $\alg{Create Base}$ with $L$ = $\tipdy,\; \pq = \pc$ to generate $C$
 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.
  }
 
@@ -171,11 +175,12 @@ sources.  That is, use $\alg{Pseudo-Merge}$ with $L = W, \;
 \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
  }
@@ -210,10 +215,23 @@ $L = W, \; R = \tipdy, \; M = \baseof{R} = \tipdn$.
 \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$.