
\section{\label{sec:patch_merge}Patch Merge}

In order to give you some idea of where we are going, in this section we
will describe how merging of non-conflicting patches works. This whole
section is only informational.

To start with, let's see how to merge single patches. Suppose we have
the two repos $\seq{p} q$ and $\seq{p} r$, where $\name{q} \ne
\name{r}$, {\ie} they differ only in the
last patch. We wish to merge these two repos. We can make a graph
containing the patches in both repos thus:\\
\begin{mfpic}{0}{4}{-1}{1}
    \pointdef{O}(0,2)
    \pointdef{midP}(0,1)
    \pointdef{P}(0,0)
    \pointdef{midQ}(-1,-0.2)
    \pointdef{Q}(-2,-1)
    \pointdef{midR}(1,-0.2)
    \pointdef{R}(2,-1)
    \point{\O,\P,\Q,\R}
    \arrlab{\O}{\midP}{\P}{cr}{$\seq{p}$}
    \arrlab{\P}{\midQ}{\Q}{br}{$q$}
    \arrlab{\P}{\midR}{\R}{bl}{$r$}
\end{mfpic}\\
In order to merge the two repos, we want a single sequence of patches
incorporating the effects of both $q$ and $r$. To do this, we can
complete the bottom of our diagram to form a commutation square:\\
\begin{mfpic}{0}{4}{-1}{1}
    \pointdef{O}(0,2)
    \pointdef{midP}(0,1)
    \pointdef{P}(0,0)
    \pointdef{midQ}(-1,-0.2)
    \pointdef{Q}(-2,-1)
    \pointdef{midR}(1,-0.2)
    \pointdef{R}(2,-1)
    \pointdef{midQR}(-1,-1.8)
    \pointdef{midRQ}(1,-1.8)
    \pointdef{QR}(0,-2)
    \point{\O,\P,\Q,\R,\QR}
    \arrlab{\O}{\midP}{\P}{br}{$\seq{p}$}
    \arrlab{\P}{\midQ}{\Q}{br}{$q$}
    \arrlab{\Q}{\midQR}{\QR}{tr}{$r'$}
    \arrlab{\P}{\midR}{\R}{bl}{$r$}
    \arrlab{\R}{\midRQ}{\QR}{tl}{$q'$}
\end{mfpic}\\
Provided the commute succeeds, we have that the result of the merge is
$q r'$ (or, equivalently, $r q'$). If the commute does not succeed then
the patches cannot be cleanly merged, {\ie} $q$ and $r$ conflict.

Now let's generalise to arbitrarily large merges. In one repo we have
$\seq{p} q \seq{r}$, and in the other we have $\seq{p} s \seq{t}$, where
$\names{q \seq{r}} \cap \names{s \seq{t}} = \emptyset$:\\
\begin{mfpic}{0}{4}{-1}{1}
    \pointdef{O}(0,2)
    \pointdef{midP}(0,1)
    \pointdef{P}(0,0)
    \pointdef{midQ}(-1,-0.2)
    \pointdef{Q}(-2,-1)
    \pointdef{midR}(-2,-2)
    \pointdef{R}(-2,-3)
    \pointdef{midS}(1,-0.2)
    \pointdef{S}(2,-1)
    \pointdef{midT}(2,-2)
    \pointdef{T}(2,-3)
    \point{\O,\P,\Q,\R,\S,\T}
    \arrlab{\O}{\midP}{\P}{cr}{$\seq{p}$}
    \arrlab{\P}{\midQ}{\Q}{br}{$q$}
    \arrlab{\Q}{\midR}{\R}{cr}{$\seq{r}$}
    \arrlab{\P}{\midS}{\S}{bl}{$s$}
    \arrlab{\S}{\midT}{\T}{cl}{$\seq{t}$}
\end{mfpic}\\
We start off by merging $q$ and $s$:\\
\begin{mfpic}{0}{4}{-1}{1}
    \pointdef{O}(0,2)
    \pointdef{midP}(0,1)
    \pointdef{P}(0,0)
    \pointdef{midQ}(-1,-0.2)
    \pointdef{Q}(-2,-1)
    \pointdef{midR}(-2,-2)
    \pointdef{R}(-2,-3)
    \pointdef{midS}(1,-0.2)
    \pointdef{S}(2,-1)
    \pointdef{midQS}(-1,-1.2)
    \pointdef{QS}(0,-2)
    \pointdef{midT}(2,-2)
    \pointdef{T}(2,-3)
    \point{\O,\P,\Q,\R,\S,\QS,\T}
    \arrlab{\O}{\midP}{\P}{cr}{$\seq{p}$}
    \arrlab{\P}{\midQ}{\Q}{br}{$q$}
    \arrlab{\Q}{\midR}{\R}{cr}{$\seq{r}$}
    \arrlab{\P}{\midS}{\S}{bl}{$s$}
    \arrlab{\Q}{\midQS}{\QS}{bl}{$s'$}
    \arrlab{\S}{\midT}{\T}{cl}{$\seq{t}$}
\end{mfpic}\\
Note that $q s'$ commutes to $s q'$. Now recursively merge $s'$ with
$\seq{r}$:\\
\begin{mfpic}{0}{4}{-1}{1}
    \pointdef{O}(0,2)
    \pointdef{midP}(0,1)
    \pointdef{P}(0,0)
    \pointdef{midQ}(-1,-0.2)
    \pointdef{Q}(-2,-1)
    \pointdef{midR}(-2,-2)
    \pointdef{R}(-2,-3)
    \pointdef{midS}(1,-0.2)
    \pointdef{S}(2,-1)
    \pointdef{midRS}(-1,-3.2)
    \pointdef{RS}(0,-4)
    \pointdef{midT}(2,-2)
    \pointdef{T}(2,-3)
    \point{\O,\P,\Q,\R,\S,\RS,\T}
    \arrlab{\O}{\midP}{\P}{cr}{$\seq{p}$}
    \arrlab{\P}{\midQ}{\Q}{br}{$q$}
    \arrlab{\Q}{\midR}{\R}{cr}{$\seq{r}$}
    \arrlab{\P}{\midS}{\S}{bl}{$s$}
    \arrlab{\R}{\midRS}{\RS}{bl}{$s''$}
    \arrlab{\S}{\midT}{\T}{cl}{$\seq{t}$}
\end{mfpic}\\
For the same reason that $q$ and $s'$ commute, $s''$ can be commuted
past all the patches in $\seq{r}$:\\
\begin{mfpic}{0}{4}{-1}{1}
    \pointdef{O}(0,2)
    \pointdef{midP}(0,1)
    \pointdef{P}(0,0)
    \pointdef{midQ}(-1,-0.2)
    \pointdef{Q}(-2,-1)
    \pointdef{midSX}(-2,-2)
    \pointdef{SX}(-2,-3)
    \pointdef{midR}(-2,-4)
    \pointdef{R}(-2,-5)
    \pointdef{midS}(1,-0.2)
    \pointdef{S}(2,-1)
    \pointdef{midT}(2,-2)
    \pointdef{T}(2,-3)
    \point{\O,\P,\Q,\SX,\R,\S,\T}
    \arrlab{\O}{\midP}{\P}{cr}{$\seq{p}$}
    \arrlab{\P}{\midQ}{\Q}{br}{$q$}
    \arrlab{\Q}{\midSX}{\SX}{cr}{$s'$}
    \arrlab{\SX}{\midR}{\R}{cr}{$\seq{r}'$}
    \arrlab{\P}{\midS}{\S}{bl}{$s$}
    \arrlab{\S}{\midT}{\T}{cl}{$\seq{t}$}
\end{mfpic}\\
and of course, we can then commute $s'$ and $q$:\\
\begin{mfpic}{0}{4}{-1}{1}
    \pointdef{O}(0,2)
    \pointdef{midP}(0,1)
    \pointdef{P}(0,0)
    \pointdef{midSX}(-1,-0.2)
    \pointdef{SX}(-2,-1)
    \pointdef{midQ}(-2,-2)
    \pointdef{Q}(-2,-3)
    \pointdef{midR}(-2,-4)
    \pointdef{R}(-2,-5)
    \pointdef{midS}(1,-0.2)
    \pointdef{S}(2,-1)
    \pointdef{midT}(2,-2)
    \pointdef{T}(2,-3)
    \point{\O,\P,\Q,\SX,\R,\S,\T}
    \arrlab{\O}{\midP}{\P}{cr}{$\seq{p}$}
    \arrlab{\P}{\midSX}{\SX}{br}{$s$}
    \arrlab{\SX}{\midQ}{\Q}{cr}{$q'$}
    \arrlab{\Q}{\midR}{\R}{cr}{$\seq{r}'$}
    \arrlab{\P}{\midS}{\S}{bl}{$s$}
    \arrlab{\S}{\midT}{\T}{cl}{$\seq{t}$}
\end{mfpic}\\
Coalescing our two $\seq{p}s$ nodes gives us:\\
\begin{mfpic}{0}{4}{-1}{1}
    \pointdef{O}(0,2)
    \pointdef{midP}(0,1)
    \pointdef{P}(0,0)
    \pointdef{midS}(0,-1)
    \pointdef{S}(0,-2)
    \pointdef{midQ}(-1,-2.2)
    \pointdef{Q}(-2,-3)
    \pointdef{midR}(-2,-4)
    \pointdef{R}(-2,-5)
    \pointdef{midT}(1,-2.2)
    \pointdef{T}(2,-3)
    \point{\O,\P,\S,\Q,\R,\T}
    \arrlab{\O}{\midP}{\P}{cr}{$\seq{p}$}
    \arrlab{\P}{\midS}{\S}{cr}{$s$}
    \arrlab{\S}{\midQ}{\Q}{br}{$q'$}
    \arrlab{\Q}{\midR}{\R}{cr}{$\seq{r}'$}
    \arrlab{\S}{\midT}{\T}{bl}{$\seq{t}$}
\end{mfpic}\\
so we have merged $s$. Now we merge each patch in $\seq{t}$ in the same
way, resulting in:\\
\begin{mfpic}{0}{4}{-1}{1}
    \pointdef{O}(0,2)
    \pointdef{midP}(0,1)
    \pointdef{P}(0,0)
    \pointdef{midS}(0,-1)
    \pointdef{S}(0,-2)
    \pointdef{midT}(0,-3)
    \pointdef{T}(0,-4)
    \pointdef{midQ}(0,-5)
    \pointdef{Q}(0,-6)
    \pointdef{midR}(0,-7)
    \pointdef{R}(0,-8)
    \point{\O,\P,\S,\Q,\R,\T}
    \arrlab{\O}{\midP}{\P}{cr}{$\seq{p}$}
    \arrlab{\P}{\midS}{\S}{cr}{$s$}
    \arrlab{\S}{\midT}{\T}{cr}{$\seq{t}$}
    \arrlab{\T}{\midQ}{\Q}{cr}{$q''$}
    \arrlab{\Q}{\midR}{\R}{cr}{$\seq{r}''$}
\end{mfpic}

