finish merge unique base (we think)

[topbloke-formulae.git] / article.tex

diff --git a/article.tex b/article.tex
index bd68fb10b8624ddecb0e2ed04f5f72f0ba758e1a..1e42670e628e92e064dd162a960f8ba65b5c8c81 100644 (file)
--- a/article.tex
+++ b/article.tex
@@ -1,4 +1,5 @@
 \documentclass[a4paper,leqno]{strayman}
+\errorcontextlines=50
 \let\numberwithin=\notdef
 \usepackage{amsmath}
 \usepackage{mathabx}
@@ -18,8 +19,12 @@
 \newcommand{\haspatch}{\sqSupset}
 \newcommand{\patchisin}{\sqSubset}
 
-\newcommand{\set}[1]{\mathbb #1}
-\newcommand{\pa}[1]{\varmathbb #1}
+        \newif\ifhidehack\hidehackfalse
+        \DeclareRobustCommand\hidefromedef[2]{%
+          \hidehacktrue\ifhidehack#1\else#2\fi\hidehackfalse}
+        \newcommand{\pa}[1]{\hidefromedef{\varmathbb{#1}}{#1}}
+
+\newcommand{\set}[1]{\mathbb{#1}}
 \newcommand{\pay}[1]{\pa{#1}^+}
 \newcommand{\pan}[1]{\pa{#1}^-}
 
@@ -59,6 +64,8 @@
     {\hbox{\scriptsize$\forall$}}}%
 }
 
+\newcommand{\Largeexists}{\mathop{\hbox{\Large$\exists$}}}
+\newcommand{\Largenexists}{\mathop{\hbox{\Large$\nexists$}}}
 
 \newcommand{\qed}{\square}
 \newcommand{\proof}[1]{{\it Proof.} #1 $\qed$}
@@ -66,6 +73,9 @@
 \newcommand{\gathbegin}{\begin{gather} \tag*{}}
 \newcommand{\gathnext}{\\ \tag*{}}
 
+\newcommand{\true}{t}
+\newcommand{\false}{f}
+
 \begin{document}
 
 \section{Notation}
@@ -111,7 +121,7 @@ which are in $\set P$.
 \item[ $ \pendsof{C}{\set P} $ ]
 $ \{ E \; | \; E \in \pancsof{C}{\set P}
   \land \mathop{\not\exists}_{A \in \pancsof{C}{\set P}}
-  A \neq E \land E \le A \} $ 
+  E \neq A \land E \le A \} $ 
 i.e. all $\le$-maximal commits in $\pancsof{C}{\set P}$.
 
 \item[ $ \baseof{C} $ ]
@@ -214,6 +224,17 @@ in which case we repeat for $A'$.  Since there are finitely many
 commits, this terminates with $A'' \in \pends()$, ie $A'' \le M$
 by the LHS.  And $A \le A''$.
 }
+\[ \eqn{Calculation Of Ends:}{
+  \bigforall_{C \hasparents \set A}
+    \pendsof{C}{\set P} =
+       \Bigl\{ 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\}
+}\]
+XXX proof TBD.
 
 \section{Commit annotation}
 
@@ -286,7 +307,7 @@ Ancestors of $C$:
 $ D \le C $.
 
 Contents of $C$:
-$ D \isin C \equiv \ldots \lor t \text{ so } D \haspatch C $.
+$ D \isin C \equiv \ldots \lor \true \text{ so } D \haspatch C $.
 
 \subsubsection{For $A \haspatch P, D \neq C$:}
 Ancestors: $ D \le C \equiv D \le A $.
@@ -313,4 +334,92 @@ $\qed$
 If $D = C$, trivial.  For $D \neq C$:
 $D \isin C \equiv D \isin A \equiv D \le A \equiv D \le C$.  $\qed$
 
+\section{Merge}
+
+Merge commits $L$ and $R$ using merge base $M$ ($M < L, M < R$):
+\gathbegin
+ C \hasparents \{ L, 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}
+\end{gather}
+
+\subsection{Conditions}
+
+\[ \eqn{ Tip Merge }{
+ L \in \py \implies
+   \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}
+}\]
+
+\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$
+
+\subsection{Unique Base}
+
+Need to consider only $C \in \py$, ie $L \in \py$,
+and calculate $\pendsof{C}{\pn}$.  So we will consider some
+putative ancestor $A \in \pn$ and see whether $A \le C$.
+
+By Exact Ancestors for C, $A \le C \equiv A \le L \lor A \le R \lor A = C$.
+But $C \in py$ and $A \in \pn$ so $A \neq C$.  
+Thus $A \le C \equiv A \le L \lor A \le R$.
+
+By Unique Base of L and Transitive Ancestors,
+$A \le L \equiv A \le \baseof{L}$.
+
+\subsubsection{For $R \in \py$:}
+
+By Unique Base of $R$ and Transitive Ancestors,
+$A \le R \equiv A \le \baseof{R}$.
+
+But by Tip Merge condition on $\baseof{R}$,
+$A \le \baseof{L} \implies A \le \baseof{R}$, so
+$A \le \baseof{R} \lor A \le \baseof{L} \equiv A \le \baseof{R}$.
+Thus $A \le C \equiv A \le \baseof{R}$.  
+That is, $\baseof{C} = \baseof{R}$.
+
+\subsubsection{For $R \in \pn$:}
+
+By Tip Merge condition on $R$,
+$A \le \baseof{L} \implies A \le R$, so
+$A \le R \lor A \le \baseof{L} \equiv A \le R$.  
+Thus $A \le C \equiv A \le R$.  
+That is, $\baseof{C} = R$.
+
+$\qed$
+
 \end{document}