--- /dev/null
+\section{Some lemmas}
+
+\subsection{Alternative (overlapping) formulations of $\mergeof{C}{L}{M}{R}$}
+$$
+ D \isin C \equiv
+ \begin{cases}
+ D \isin L \equiv D \isin R : & D = C \lor D \isin L \\
+ D \isin L \nequiv D \isin R : & D = C \lor D \not\isin M \\
+ D \isin L \equiv D \isin M : & D = C \lor D \isin R \\
+ D \isin L \nequiv D \isin M : & D = C \lor D \isin L \\
+ \text{as above with L and R exchanged}
+ \end{cases}
+$$
+\proof{ ~ Truth table (ordered by original definition): \\
+ \begin{tabular}{cccc|c|cc}
+ $D = C$ &
+ $\isin L$ &
+ $\isin M$ &
+ $\isin R$ & $\isin C$ &
+ $L$ vs. $R$ & $L$ vs. $M$
+ \\\hline
+ y & ? & ? & ? & y & ? & ? \\
+ n & y & y & y & y & $\equiv$ & $\equiv$ \\
+ n & y & n & y & y & $\equiv$ & $\nequiv$ \\
+ n & n & y & n & n & $\equiv$ & $\nequiv$ \\
+ n & n & n & n & n & $\equiv$ & $\equiv$ \\
+ n & y & y & n & n & $\nequiv$ & $\equiv$ \\
+ n & n & y & y & n & $\nequiv$ & $\nequiv$ \\
+ n & y & n & n & y & $\nequiv$ & $\nequiv$ \\
+ n & n & n & y & y & $\nequiv$ & $\equiv$ \\
+ \end{tabular} \\
+ And original definition is symmetrical in $L$ and $R$.
+}
+
+\subsection{Exclusive Tip Contents}
+Given Base Acyclic for $C$,
+$$
+ \bigforall_{C \in \py}
+ \neg \Bigl[ D \isin \baseof{C} \land ( D \in \py \land D \le C )
+ \Bigr]
+$$
+Ie, the two limbs of the RHS of Tip Contents are mutually exclusive.
+
+\proof{
+Let $B = \baseof{C}$ in $D \isin \baseof{C}$. Now $B \in \pn$.
+So by Base Acyclic $D \isin B \implies D \notin \py$.
+}
+\[ \eqntag{{\it Corollary - equivalent to Tip Contents}}{
+ \bigforall_{C \in \py} D \isin C \equiv
+ \begin{cases}
+ D \in \py : & D \le C \\
+ D \not\in \py : & D \isin \baseof{C}
+ \end{cases}
+}\]
+
+\subsection{Tip Self Inpatch}
+Given Exclusive Tip Contents and Base Acyclic for $C$,
+$$
+ \bigforall_{C \in \py} C \haspatch \p
+$$
+Ie, tip commits contain their own patch.
+
+\proof{
+Apply Exclusive Tip Contents to some $D \in \py$:
+$ \bigforall_{C \in \py}\bigforall_{D \in \py}
+ D \isin C \equiv D \le C $
+}
+
+\subsection{Exact Ancestors}
+$$
+ \bigforall_{ C \hasparents \set{R} }
+ \left[
+ D \le C \equiv
+ ( \mathop{\hbox{\huge{$\vee$}}}_{R \in \set R} D \le R )
+ \lor D = C
+ \right]
+$$
+\proof{ ~ Trivial.}
+
+\subsection{Transitive Ancestors}
+$$
+ \left[ \bigforall_{ E \in \pendsof{C}{\set P} } E \le M \right] \equiv
+ \left[ \bigforall_{ A \in \pancsof{C}{\set P} } A \le M \right]
+$$
+
+\proof{
+The implication from right to left is trivial because
+$ \pends() \subset \pancs() $.
+For the implication from left to right:
+by the definition of $\mathcal E$,
+for every such $A$, either $A \in \pends()$ which implies
+$A \le M$ by the LHS directly,
+or $\exists_{A' \in \pancs()} \; A' \neq A \land A \le A' $
+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''$.
+}
+
+\subsection{Calculation of Ends}
+$$
+ \bigforall_{C \hasparents \set A}
+ \pendsof{C}{\set P} =
+ \begin{cases}
+ C \in \p : & \{ C \}
+ \\
+ C \not\in \p : & \displaystyle
+ \left\{ E \Big|
+ \Bigl[ \Largeexists_{A \in \set A}
+ E \in \pendsof{A}{\set P} \Bigr] \land
+ \Bigl[ \Largenexists_{B \in \set A, F \in \pendsof{B}{\p}}
+ E \neq F \land E \le F \Bigr]
+ \right\}
+ \end{cases}
+$$
+\proof{
+Trivial for $C \in \set P$. For $C \not\in \set P$,
+$\pancsof{C}{\set P} = \bigcup_{A \in \set A} \pancsof{A}{\set P}$.
+So $\pendsof{C}{\set P} \subset \bigcup_{E in \set E} \pendsof{E}{\set P}$.
+Consider some $E \in \pendsof{A}{\set P}$. If $\exists_{B,F}$ as
+specified, then either $F$ is going to be in our result and
+disqualifies $E$, or there is some other $F'$ (or, eventually,
+an $F''$) which disqualifies $F$.
+Otherwise, $E$ meets all the conditions for $\pends$.
+}
+
+\subsection{Ingredients Prevent Replay}
+$$
+ \left[
+ {C \hasparents \set A} \land
+ \\
+ \bigforall_{D}
+ \left(
+ D \isin C \implies
+ D = C \lor
+ \Largeexists_{A \in \set A} D \isin A
+ \right)
+ \right] \implies \left[ \bigforall_{D}
+ D \isin C \implies D \le C
+ \right]
+$$
+\proof{
+ Trivial for $D = C$. Consider some $D \neq C$, $D \isin C$.
+ By the preconditions, there is some $A$ s.t. $D \in \set A$
+ and $D \isin A$. By No Replay for $A$, $D \le A$. And
+ $A \le C$ so $D \le C$.
+}
+
+\subsection{Simple Foreign Inclusion}
+$$
+ \left[
+ C \hasparents \{ L \}
+ \land
+ \bigforall_{D} D \isin C \equiv D \isin L \lor D = C
+ \right]
+ \implies
+ \left[
+ \bigforall_{D \text{ s.t. } \patchof{D} = \bot}
+ D \isin C \equiv D \le C
+ \right]
+$$
+\proof{
+Consider some $D$ s.t. $\patchof{D} = \bot$.
+If $D = C$, trivially true. For $D \neq C$,
+by Foreign Inclusion of $D$ in $L$, $D \isin L \equiv D \le L$.
+And by Exact Ancestors $D \le L \equiv D \le C$.
+So $D \isin C \equiv D \le C$.
+}
+
+\subsection{Totally Foreign Contents}
+$$
+ \left[
+ C \hasparents \set A \land
+ \patchof{C} = \bot \land
+ \bigforall_{A \in \set A} \patchof{A} = \bot
+ \right]
+ \implies
+ \left[
+ \bigforall_{D}
+ D \le C
+ \implies
+ \patchof{D} = \bot
+ \right]
+$$
+\proof{
+Consider some $D \le C$. If $D = C$, $\patchof{D} = \bot$ trivially.
+If $D \neq C$ then $D \le A$ where $A \in \set A$. By Foreign
+Contents of $A$, $\patchof{D} = \bot$.
+}
+
~ian / topbloke-formulae.git / blobdiff