From 67e27b1cb5487e79f47e828773fdd574b9da9712 Mon Sep 17 00:00:00 2001
From: Ian Jackson <ijackson@chiark.greenend.org.uk>
Date: Sat, 14 Jul 2012 02:24:08 +0100
Subject: [PATCH] strategy: reachable is going well

---
 strategy.tex    | 14 --------------
 trav-alg.tex    |  6 ++----
 trav-proofs.tex | 27 +++++++++++++++++++++++++--
 3 files changed, 27 insertions(+), 20 deletions(-)

diff --git a/strategy.tex b/strategy.tex
index 253ffc3..a4716b3 100644
--- a/strategy.tex
+++ b/strategy.tex
@@ -124,17 +124,3 @@ The set of reachable commits at the point where we have just generated
 $\tippy$, i.e. just after $\alg{Merge-Tip}(\p)$.
 
 \end{basedescript}
-
-\stdsection{ WIP tip satisfaction, reachable commits }
-
-We preserve/ensure
-$$ \tippy >= \pendsof{\allreach_{\py}}{\py} $$
-($\tippy$ is computed during traversal for the patch $\p$)
-
-We ensure this property by:
-  - we do not generate any commits for py other than
-    during Merge-Tip
-  - so at the start of Merge-Tip pendsof (O, py) = pendsof (U, py)
-  - Merge-Tip itself wip wip wip
-
-
diff --git a/trav-alg.tex b/trav-alg.tex
index 82bca6d..e56a8a9 100644
--- a/trav-alg.tex
+++ b/trav-alg.tex
@@ -34,8 +34,8 @@ such that:
    \equiv
   \pa E \isdep \pc
 }
-\statement{Tip Covers Inputs}{
-  \tipcy \ge \pendsof{\allsrcs}{\pcy}
+\statement{Tip Covers Reachable}{
+  \tipcy \ge \pendsof{\allreachof{\pcy}}{\pcy}
 }
 \statement{Base Covers Inputs' Bases}{
   \bigforall_{E \in \pendsof{\allsrcs}{\pcy}} \tipcn \ge \baseof{E}
@@ -153,5 +153,3 @@ $\alg{Merge}$ with $L = W, \; R = S$ and any suitable $M$.
 (Tip Source Merge.)
 
 \end{enumerate}
-
-
diff --git a/trav-proofs.tex b/trav-proofs.tex
index 06a54cf..421bb61 100644
--- a/trav-proofs.tex
+++ b/trav-proofs.tex
@@ -3,11 +3,34 @@
 For each operation called for by the traversal algorithms, we prove
 that the commit generation preconditions are met.
 
-WIP WHAT ABOUT PROVING ALL THE TRAVERSAL RESULTS
+\subsection{Reachability and coverage}
+
+We ensure Tip Covers Reachable as follows:
+
+\begin{itemize}
+\item  We do not generate any commits $\in \py$ other than
+       during $\alg{Merge-Tip}(\py)$;
+\item  So at the start of $\alg{Merge-Tip}(\py)$,
+       $ \pendsof{\allreach}{\py} = \pendsof{\allsrcs}{\py} $
+\item  $\alg{Merge-tip}$ arranges that when it is done
+       $\tippy \ge \pendsof{\allreach}{\py}$ --- see below.
+\end{itemize}
+
+A corrolary is as follows:
+\statement{Tip Covers Superior Reachable} {
+  \bigforall_{\pd \isdep \pc}
+    \tipdy \ge \pendsof{\allreachof{\pcy}}{\pdy}
+}
+\proof{
+  No commits $\in \pdy$ are created other than during
+  $\alg{Merge-Tip}(\pd)$, which runs (and has thus completed)
+  before $\alg{Merge-Tip}(\pcy)$
+  So $\pendsof{\allreachof{\pcy}}{\pdy} =
+      \pendsof{\allreachof{\pdy}}{\pdy}$.
+}
 
 \subsection{Traversal Lemmas}
 
-Firstly, some lemmas.
 \statement{Tip Correct Contents}{
   \tipcy \haspatch \pa E
     \equiv
-- 
2.30.2