X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ian/git?p=topbloke-formulae.git;a=blobdiff_plain;f=article.tex;h=fac5c82efd6483ac6cc865cbd2db836f2d29d81e;hp=06b76126865f6c828a0fb58a3f7cbf9ae6d6c5b0;hb=13285d550a2eceb866519b89d1ed3c4894f3db65;hpb=7bcd460d5b2d6b000aa3a612c48881b5bf29674d

diff --git a/article.tex b/article.tex
index 06b7612..fac5c82 100644
--- a/article.tex
+++ b/article.tex
@@ -10,6 +10,8 @@
 
 \renewcommand{\ge}{\geqslant}
 \renewcommand{\le}{\leqslant}
+\newcommand{\nge}{\ngeqslant}
+\newcommand{\nle}{\nleqslant}
 
 \newcommand{\has}{\sqsupseteq}
 \newcommand{\isin}{\sqsubseteq}
@@ -53,11 +55,15 @@
 \newcommand{\pancsof}[2]{\pancs ( #1 , #2 ) }
 \newcommand{\pendsof}[2]{\pends ( #1 , #2 ) }
 
-\newcommand{\merge}[4]{{\mathcal M}(#1,#2,#3,#4)}
+\newcommand{\merge}{{\mathcal M}}
+\newcommand{\mergeof}[4]{\merge(#1,#2,#3,#4)}
 %\newcommand{\merge}[4]{{#2 {{\frac{ #1 }{ #3 } #4}}}}
 
-\newcommand{\patchof}[1]{{\mathcal P} ( #1 ) }
-\newcommand{\baseof}[1]{{\mathcal B} ( #1 ) }
+\newcommand{\patch}{{\mathcal P}}
+\newcommand{\base}{{\mathcal B}}
+
+\newcommand{\patchof}[1]{\patch ( #1 ) }
+\newcommand{\baseof}[1]{\base ( #1 ) }
 
 \newcommand{\eqn}[2]{ #2 \tag*{\mbox{\bf #1}} }
 \newcommand{\corrolary}[1]{ #1 \tag*{\mbox{\it Corrolary.}} }
@@ -75,7 +81,8 @@
 \newcommand{\Largenexists}{\mathop{\hbox{\Large$\nexists$}}}
 
 \newcommand{\qed}{\square}
-\newcommand{\proof}[1]{{\it Proof.} #1 $\qed$}
+\newcommand{\proofstarts}{{\it Proof:}}
+\newcommand{\proof}[1]{\proofstarts #1 $\qed$}
 
 \newcommand{\gathbegin}{\begin{gather} \tag*{}}
 \newcommand{\gathnext}{\\ \tag*{}}
@@ -149,7 +156,7 @@ patch is applied to a non-Topbloke branch and then bubbles back to
 the Topbloke patch itself, we hope that git's merge algorithm will
 DTRT or that the user will no longer care about the Topbloke patch.
 
-\item[ $\displaystyle \merge{C}{L}{M}{R} $ ]
+\item[ $\displaystyle \mergeof{C}{L}{M}{R} $ ]
 The contents of a git merge result:
 
 $\displaystyle D \isin C \equiv
@@ -245,15 +252,46 @@ by the LHS.  And $A \le A''$.
 \[ \eqn{Calculation Of Ends:}{
   \bigforall_{C \hasparents \set A}
     \pendsof{C}{\set P} =
-       \Bigl\{ E \Big|
+       \left\{ E \Big|
            \Bigl[ \Largeexists_{A \in \set A} 
                        E \in \pendsof{A}{\set P} \Bigr] \land
            \Bigl[ \Largenexists_{B \in \set A} 
                        E \neq B \land E \le B \Bigr]
-       \Bigr\}
+       \right\}
 }\]
 XXX proof TBD.
 
+\subsection{No Replay for Merge Results}
+
+If we are constructing $C$, with,
+\gathbegin
+  \mergeof{C}{L}{M}{R}
+\gathnext
+  L \le C
+\gathnext
+  R \le C
+\end{gather}
+No Replay is preserved.  \proofstarts
+
+\subsubsection{For $D=C$:} $D \isin C, D \le C$.  OK.
+
+\subsubsection{For $D \isin L \land D \isin R$:}
+$D \isin C$.  And $D \isin L \implies D \le L \implies D \le C$.  OK.
+
+\subsubsection{For $D \neq C \land D \not\isin L \land D \not\isin R$:}
+$D \not\isin C$.  OK.
+
+\subsubsection{For $D \neq C \land (D \isin L \equiv D \not\isin R)
+ \land D \not\isin M$:}
+$D \isin C$.  Also $D \isin L \lor D \isin R$ so $D \le L \lor D \le
+R$ so $D \le C$.  OK.
+
+\subsubsection{For $D \neq C \land (D \isin L \equiv D \not\isin R)
+ \land D \isin M$:}
+$D \not\isin C$.  OK.
+
+$\qed$
+
 \section{Commit annotation}
 
 We annotate each Topbloke commit $C$ with:
@@ -355,7 +393,7 @@ $D \isin C \equiv D \isin A \equiv D \le A \equiv D \le C$.  $\qed$
 \section{Anticommit}
 
 Given $L, R^+, R^-$ where
-$\patchof{R^+} = \pry, \patchof{R^-} = \prn$.  
+$R^+ \in \pry, R^- = \baseof{R^+}$.  
 Construct $C$ which has $\pr$ removed.
 Used for removing a branch dependency.
 \gathbegin
@@ -363,17 +401,68 @@ Used for removing a branch dependency.
 \gathnext
  \patchof{C} = \patchof{L}
 \gathnext
- D \isin C \equiv
-   \begin{cases}
-      R \in \py : & \baseof{R} \ge \baseof{L}
-              \land [\baseof{L} = M \lor \baseof{L} = \baseof{M}] \\
-      R \in \pn : & R \ge \baseof{L}
-              \land M = \baseof{L} \\
-      \text{otherwise} : & \false
-   \end{cases}
+ \mergeof{C}{L}{R^+}{R^-}
 \end{gather}
 
-xxx want to prove $D \isin C \equiv D \not\in pry \land D \isin L$.
+\subsection{Conditions}
+
+\[ \eqn{ Unique Tip }{
+ \pendsof{L}{\pry} = \{ R^+ \}
+}\]
+\[ \eqn{ Currently Included }{
+ L \haspatch \pry
+}\]
+\[ \eqn{ Not Self }{
+ L \not\in \{ R^+ \}
+}\]
+
+\subsection{No Replay}
+
+By Unique Tip, $R^+ \le L$.  By definition of $\base$, $R^- \le R^+$
+so $R^- \le L$.  So $R^+ \le C$ and $R^- \le C$ and No Replay for
+Merge Results applies. $\qed$
+
+\subsection{Desired Contents}
+
+\[ D \isin C \equiv [ D \notin \pry \land D \isin L ] \lor D = C \]
+\proofstarts
+
+\subsubsection{For $D = C$:}
+
+Trivially $D \isin C$.  OK.
+
+\subsubsection{For $D \neq C, D \not\le L$:}
+
+By No Replay $D \not\isin L$.  Also $D \not\le R^-$ hence
+$D \not\isin R^-$.  Thus $D \not\isin C$.  OK.
+
+\subsubsection{For $D \neq C, D \le L, D \in \pry$:}
+
+By Currently Included, $D \isin L$.
+
+By Tip Self Inpatch, $D \isin R^+ \equiv D \le R^+$, but by
+by Unique Tip, $D \le R^+ \equiv D \le L$.  
+So $D \isin R^+$.
+
+By Base Acyclic, $D \not\isin R^-$.
+
+Apply $\merge$: $D \not\isin C$.  OK.
+
+\subsubsection{For $D \neq C, D \le L, D \notin \pry$:}
+
+By Tip Contents for $R^+$, $D \isin R^+ \equiv D \isin R^-$.
+
+Apply $\merge$: $D \isin C \equiv D \isin L$.  OK.
+
+$\qed$
+
+\subsection{Unique Base}
+
+Need to consider only $C \in \py$, ie $L \in \py$.
+
+xxx tbd
+
+xxx need to finish anticommit
 
 \section{Merge}
 
@@ -383,13 +472,9 @@ Merge commits $L$ and $R$ using merge base $M$ ($M < L, M < R$):
 \gathnext
  \patchof{C} = \patchof{L}
 \gathnext
- D \isin C \equiv
-  \begin{cases}
-    (D \isin L \land D \isin R) \lor D = C : & \true \\
-    (D \not\isin L \land D \not\isin R) \land D \neq C : & \false \\
-    \text{otherwise} : & D \not\isin M
-  \end{cases}
+ \mergeof{C}{L}{M}{R}
 \end{gather}
+We will occasionally use $X,Y$ s.t. $\{X,Y\} = \{L,R\}$.
 
 \subsection{Conditions}
 
@@ -403,31 +488,18 @@ Merge commits $L$ and $R$ using merge base $M$ ($M < L, M < R$):
       \text{otherwise} : & \false
    \end{cases}
 }\]
+\[ \eqn{ Merge Ends }{
+    X \not\haspatch \p \land
+    Y \haspatch \p
+  \implies \left[
+  \bigforall_{E \in \pendsof{X}{\py}}
+    E \le Y
+  \right]
+}\]
 
 \subsection{No Replay}
 
-\subsubsection{For $D=C$:} $D \isin C, D \le C$.  OK.
-
-\subsubsection{For $D \isin L \land D \isin R$:}
-$D \isin C$.  And $D \isin L \implies D \le L \implies D \le C$.  OK.
-
-\subsubsection{For $D \neq C \land D \not\isin L \land D \not\isin R$:}
-$D \not\isin C$.  OK.
-
-\subsubsection{For $D \neq C \land D \not\isin L \land D \not\isin R$:}
-$D \not\isin C$.  OK.
-
-\subsubsection{For $D \neq C \land (D \isin L \equiv D \not\isin R)
- \land D \not\isin M$:}
-$D \isin C$.  Also $D \isin L \lor D \isin R$ so $D \le L \lor D \le
-R$ so $D \le C$.  OK.
-
-\subsubsection{For $D \neq C \land (D \isin L \equiv D \not\isin R)
- \land D \isin M$:}
-$D \not\isin C$.  Also $D \isin L \lor D \isin R$ so $D \le L \lor D \le
-R$ so $D \le C$.  OK.
-
-$\qed$
+See No Replay for Merge Results.
 
 \subsection{Unique Base}
 
@@ -463,4 +535,57 @@ That is, $\baseof{C} = R$.
 
 $\qed$
 
+\subsection{Coherence and patch inclusion}
+
+Need to determine $C \haspatch \p$ based on $L,M,R \haspatch \p$.
+This involves considering $D \in \py$.  
+
+\subsubsection{For $L \nothaspatch \p, R \nothaspatch \p$:}
+$D \not\isin L \land D \not\isin R$.  $C \not\in \py$ (otherwise $L
+\in \py$ ie $L \haspatch \p$ by Tip Self Inpatch).  So $D \neq C$.
+Applying $\merge$ gives $D \not\isin C$ i.e. $C \nothaspatch \p$.
+
+\subsubsection{For $L \haspatch \p, R \haspatch \p$:}
+$D \isin L \equiv D \le L$ and $D \isin R \equiv D \le R$.
+(Likewise $D \isin X \equiv D \le X$ and $D \isin Y \equiv D \le Y$.)
+
+Consider $D = C$: $D \isin C$, $D \le C$, OK for $C \haspatch \p$.
+
+For $D \neq C$: $D \le C \equiv D \le L \lor D \le R
+ \equiv D \isin L \lor D \isin R$.  
+(Likewise $D \le C \equiv D \le X \lor D \le Y$.)
+
+Consider $D \neq C, D \isin X \land D \isin Y$:
+By $\merge$, $D \isin C$.  Also $D \le X$ 
+so $D \le C$.  OK for $C \haspatch \p$.
+
+Consider $D \neq C, D \not\isin X \land D \not\isin Y$:
+By $\merge$, $D \not\isin C$.  
+And $D \not\le X \land D \not\le Y$ so $D \not\le C$.  
+OK for $C \haspatch \p$.
+
+Remaining case, wlog, is $D \not\isin X \land D \isin Y$.
+$D \not\le X$ so $D \not\le M$ so $D \not\isin M$.  
+Thus by $\merge$, $D \isin C$.  And $D \le Y$ so $D \le C$.
+OK for $C \haspatch \p$.
+
+So indeed $L \haspatch \p \land R \haspatch \p \implies C \haspatch \p$.
+
+\subsubsection{For (wlog) $X \not\haspatch \p, Y \haspatch \p$:}
+
+$C \haspatch \p \equiv M \nothaspatch \p$.
+
+\proofstarts
+
+Merge Ends applies.  Recall that we are considering $D \in \py$.
+$D \isin Y \equiv D \le Y$.  $D \not\isin X$.
+We will show for each of
+various cases that $D \isin C \equiv M \nothaspatch \p \land D \le C$
+(which suffices by definition of $\haspatch$ and $\nothaspatch$).
+
+Consider $D = C$.  Thus $C \in \py, L \in \py$, and by Tip
+Self Inpatch $L \haspatch \p$, so $L=Y, R=X$.  By Tip Merge,
+$M=\baseof{L}$.  So by Base Acyclic $D \not\isin M$, i.e.
+$M \nothaspatch \p$.  And indeed $D \isin C$ and $D \le C$.  OK.
+
 \end{document}