introduce \proofstarts

[topbloke-formulae.git] / article.tex

diff --git a/article.tex b/article.tex
index 4c5f6751682c83a13e478fdb11d64496abd1bd22..1fa67c2330d692aed86011628931177731e8a99a 100644 (file)
--- 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,7 +55,8 @@
 \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{\patch}{{\mathcal P}}
@@ -78,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*{}}
@@ -152,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
@@ -261,13 +265,13 @@ XXX proof TBD.
 
 If we are constructing $C$, given
 \gathbegin
-  \merge{C}{L}{M}{R}
+  \mergeof{C}{L}{M}{R}
 \gathnext
   L \le C
 \gathnext
   R \le C
 \end{gather}
-No Replay is preserved.  {\it Proof:}
+No Replay is preserved.  \proofstarts
 
 \subsubsection{For $D=C$:} $D \isin C, D \le C$.  OK.
 
@@ -397,7 +401,7 @@ Used for removing a branch dependency.
 \gathnext
  \patchof{C} = \patchof{L}
 \gathnext
- \merge{C}{L}{R^+}{R^-}
+ \mergeof{C}{L}{R^+}{R^-}
 \end{gather}
 
 \subsection{Conditions}
@@ -408,10 +412,9 @@ Used for removing a branch dependency.
 \[ \eqn{ Currently Included }{
  L \haspatch \pry
 }\]
-
-\subsection{Desired Contents}
-
-xxx need to prove $D \isin C \equiv D \not\in \pry \land D \isin L$.
+\[ \eqn{ Not Self }{
+ L \not\in \{ R^+ \}
+}\]
 
 \subsection{No Replay}
 
@@ -419,12 +422,48 @@ 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}
 
 Merge commits $L$ and $R$ using merge base $M$ ($M < L, M < R$):
@@ -433,7 +472,7 @@ Merge commits $L$ and $R$ using merge base $M$ ($M < L, M < R$):
 \gathnext
  \patchof{C} = \patchof{L}
 \gathnext
- \merge{C}{L}{M}{R}
+ \mergeof{C}{L}{M}{R}
 \end{gather}
 
 \subsection{Conditions}
@@ -487,4 +526,42 @@ 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$.  
+
+We will use $X,Y$ s.t. $\{X,Y\} = \{L,R\}$.
+
+\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$.
+
 \end{document}