
\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.

We will give two descriptions on how merging works. The first,
sequence-wise merge, is much simpler, but the second, patch-wise merge,
is closer to what we have to do once conflicts are involved. Whichever
merge algorithm is chosen, we first do merge preparation.

\subsection{Merge preparation}

Suppose we have two patch sequences (which could be entire repos)
$\seq{p}$ and $\seq{q}$. They start from the same state (if they are
repos, then the empty state), and then apply their respective patch
sequences:
\begin{igpic}{0}{4}{-1}{1}
    \drawpoint{O}{(0,0)}
    \definepoint{midP}{(-1,-0.2)}
    \drawpoint{P}{(-2,-1)}
    \definepoint{midQ}{(1,-0.2)}
    \drawpoint{Q}{(2,-1)}
    \arrlab{O}{midP}{P}{br}{$\seq{p}$}
    \arrlab{O}{midQ}{Q}{bl}{$\seq{q}$}
\end{igpic}
Then before we can merge these two repositories, we first need to
commute their common patches to a prefix, {\ie} we commute the patches
within $\seq{p}$ and $\seq{q}$ to create:
\begin{igpic}{0}{4}{-1}{1}
    \drawpoint{O}{(0,2)}
    \definepoint{midR}{(0,1)}
    \drawpoint{R}{(0,0)}
    \definepoint{midS}{(-1,-0.2)}
    \drawpoint{S}{(-2,-1)}
    \definepoint{midT}{(1,-0.2)}
    \drawpoint{T}{(2,-1)}
    \arrlab{O}{midR}{R}{cr}{$\seq{r}$}
    \arrlab{R}{midS}{S}{br}{$\seq{s}$}
    \arrlab{R}{midT}{T}{bl}{$\seq{t}$}
\end{igpic}
where $\seq{p} <->* \seq{r} \seq{s}$, $\seq{q} <->* \seq{r} \seq{t}$,
and $\names{\seq{s}} \cap \names{\seq{t}} = \emptyset$.

We will prove that it is always possible to commute $\seq{p}$ and
$\seq{q}$ into such a state.

Then the actual merging is done on $\seq{s}$ and $\seq{t}$.

\subsection{Sequence-wise merge}

Suppose we have two sequences $\seq{p}$ and $\seq{q}$, where
$\names{\seq{p}} \cap \names{\seq{q}} = \emptyset$:
\begin{igpic}{0}{4}{-1}{1}
    \drawpoint{O}{(0,0)}
    \definepoint{midP}{(-1,-0.2)}
    \drawpoint{P}{(-2,-1)}
    \definepoint{midQ}{(1,-0.2)}
    \drawpoint{Q}{(2,-1)}
    \arrlab{O}{midP}{P}{br}{$\seq{p}$}
    \arrlab{O}{midQ}{Q}{bl}{$\seq{q}$}
\end{igpic}
Our goal is to find $\seq{p'}$ and $\seq{q'}$ such that
$\seq{p} \seq{q'} <->* \seq{q} \seq{p'}$, and is ``morally equivalent''
to applying both $\seq{p}$ and $\seq{q}$.

In order to achieve this, we use the fact that all patches are
invertible, along with the notion of patch commute that we already have.
To start with, let's add the sequence $\seq{p^}$ to our diagram:
\begin{igpic}[2][2]{0}{4}{-1}{1}
    \drawpoint{O}{(0,0)}
    \definepoint{midP}{(-1,-0.2)}
    \definepoint{midPi}{(-1,-0.8)}
    \drawpoint{P}{(-2,-1)}
    \definepoint{midQ}{(1,-0.2)}
    \drawpoint{Q}{(2,-1)}
    \arrlab{O}{midP}{P}{br}{$\seq{p}$}
    \arrlab{P}{midPi}{O}{tl}{$\seq{p}^$}
    \arrlab{O}{midQ}{Q}{bl}{$\seq{q}$}
\end{igpic}
Now $\seq{p}^$ and $\seq{q}$ are in sequence, so we can commute them:
\begin{igpic}[2][2]{0}{4}{-1}{1}
    \drawpoint{O}{(0,0)}
    \definepoint{midP}{(-1,-0.2)}
    \definepoint{midPi}{(-1,-0.8)}
    \drawpoint{P}{(-2,-1)}
    \definepoint{midQ}{(1,-0.2)}
    \drawpoint{Q}{(2,-1)}
    \definepoint{midPQ}{(-1,-1.8)}
    \definepoint{midQPi}{(1,-1.2)}
    \drawpoint{PQ}{(0,-2)}
    \arrlab{O}{midP}{P}{br}{$\seq{p}$}
    \arrlab{P}{midPi}{O}{tl}{$\seq{p}^$}
    \arrlab{P}{midPQ}{PQ}{tr}{$\seq{q'}$}
    \arrlab{O}{midQ}{Q}{bl}{$\seq{q}$}
    \arrlab{PQ}{midQPi}{Q}{br}{$\seq{p'}^$}
\end{igpic}
Invert $\seq{p'}^$ again and throw away the inverted sequences, and we
have the merge result:
\begin{igpic}{0}{4}{-1}{1}
    \drawpoint{O}{(0,0)}
    \definepoint{midP}{(-1,-0.2)}
    \drawpoint{P}{(-2,-1)}
    \definepoint{midQ}{(1,-0.2)}
    \drawpoint{Q}{(2,-1)}
    \definepoint{midPQ}{(-1,-1.8)}
    \definepoint{midQP}{(1,-1.8)}
    \drawpoint{PQ}{(0,-2)}
    \arrlab{O}{midP}{P}{br}{$\seq{p}$}
    \arrlab{P}{midPQ}{PQ}{tr}{$\seq{q'}$}
    \arrlab{O}{midQ}{Q}{bl}{$\seq{q}$}
    \arrlab{Q}{midQP}{PQ}{tl}{$\seq{p'}$}
\end{igpic}
But does this satisfy the ``moral equivalence'' requirement?

Consider starting with the sequence $\seq{p} \seq{p}^ \seq{q}$, which
has the effect of just $\seq{q}$. Then we commuted $\seq{p}^$ and
$\seq{q}$ giving us $\seq{p} \seq{q'} \seq{p'}^$, which must still have
the effect of just $\seq{q}$. The ``moral equivalence'' guaranteed by
commute tells us that $\seq{p'}^$ must be ``morally equivalent'' to
$\seq{p}^$, and thus $\seq{p'}^$ removes the ``moral effect'' of
$\seq{p}$. Therefore, if we take our sequence $\seq{p} \seq{q'}
\seq{p'}^$ and throw away $\seq{p'}^$, leaving just $\seq{p} \seq{q'}$,
we must have the ``moral effects'' of $\seq{p}$ and $\seq{q}$.

That paragraph was very hand-wavey, but that's because our notion of
``moral equivalence'' is very hand-wavey.

\subsection{Patch-wise merge}

To start with, let's see how to merge single patches. Suppose we have
the two sequences $\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 sequences. We can make a graph
containing the patches in both sequences thus:
\begin{igpic}{0}{4}{-1}{1}
    \drawpoint{O}{(0,2)}
    \definepoint{midP}{(0,1)}
    \drawpoint{P}{(0,0)}
    \definepoint{midQ}{(-1,-0.2)}
    \drawpoint{Q}{(-2,-1)}
    \definepoint{midR}{(1,-0.2)}
    \drawpoint{R}{(2,-1)}
    \arrlab{O}{midP}{P}{cr}{$\seq{p}$}
    \arrlab{P}{midQ}{Q}{br}{$q$}
    \arrlab{P}{midR}{R}{bl}{$r$}
\end{igpic}
In order to merge the two sequences, we want a single sequence of patches
incorporating the effects of both $q$ and $r$. We do this in the same
way that we handled sequences in sequence-wise merge, by completing the
bottom of our diagram to form a commutation square:
\begin{igpic}{0}{4}{-1}{1}
    \drawpoint{O}{(0,2)}
    \definepoint{midP}{(0,1)}
    \drawpoint{P}{(0,0)}
    \definepoint{midQ}{(-1,-0.2)}
    \drawpoint{Q}{(-2,-1)}
    \definepoint{midR}{(1,-0.2)}
    \drawpoint{R}{(2,-1)}
    \definepoint{midQR}{(-1,-1.8)}
    \definepoint{midRQ}{(1,-1.8)}
    \drawpoint{QR}{(0,-2)}
    \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{igpic}
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 sequence 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{igpic}{0}{4}{-1}{1}
    \drawpoint{O}{(0,2)}
    \definepoint{midP}{(0,1)}
    \drawpoint{P}{(0,0)}
    \definepoint{midQ}{(-1,-0.2)}
    \drawpoint{Q}{(-2,-1)}
    \definepoint{midR}{(-2,-2)}
    \drawpoint{R}{(-2,-3)}
    \definepoint{midS}{(1,-0.2)}
    \drawpoint{S}{(2,-1)}
    \definepoint{midT}{(2,-2)}
    \drawpoint{T}{(2,-3)}
    \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{igpic}
We start off by merging $q$ and $s$:
\begin{igpic}{0}{4}{-1}{1}
    \drawpoint{O}{(0,2)}
    \definepoint{midP}{(0,1)}
    \drawpoint{P}{(0,0)}
    \definepoint{midQ}{(-1,-0.2)}
    \drawpoint{Q}{(-2,-1)}
    \definepoint{midR}{(-2,-2)}
    \drawpoint{R}{(-2,-3)}
    \definepoint{midS}{(1,-0.2)}
    \drawpoint{S}{(2,-1)}
    \definepoint{midQS}{(-1,-1.2)}
    \drawpoint{QS}{(0,-2)}
    \definepoint{midT}{(2,-2)}
    \drawpoint{T}{(2,-3)}
    \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{igpic}
Note that $q s'$ commutes to $s q'$. Now recursively merge $s'$ with
$\seq{r}$:
\begin{igpic}{0}{4}{-1}{1}
    \drawpoint{O}{(0,2)}
    \definepoint{midP}{(0,1)}
    \drawpoint{P}{(0,0)}
    \definepoint{midQ}{(-1,-0.2)}
    \drawpoint{Q}{(-2,-1)}
    \definepoint{midR}{(-2,-2)}
    \drawpoint{R}{(-2,-3)}
    \definepoint{midS}{(1,-0.2)}
    \drawpoint{S}{(2,-1)}
    \definepoint{midRS}{(-1,-3.2)}
    \drawpoint{RS}{(0,-4)}
    \definepoint{midT}{(2,-2)}
    \drawpoint{T}{(2,-3)}
    \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{igpic}
For the same reason that $q$ and $s'$ commute, $s''$ can be commuted
past all the patches in $\seq{r}$:
\begin{igpic}{0}{4}{-1}{1}
    \drawpoint{O}{(0,2)}
    \definepoint{midP}{(0,1)}
    \drawpoint{P}{(0,0)}
    \definepoint{midQ}{(-1,-0.2)}
    \drawpoint{Q}{(-2,-1)}
    \definepoint{midSX}{(-2,-2)}
    \drawpoint{SX}{(-2,-3)}
    \definepoint{midR}{(-2,-4)}
    \drawpoint{R}{(-2,-5)}
    \definepoint{midS}{(1,-0.2)}
    \drawpoint{S}{(2,-1)}
    \definepoint{midT}{(2,-2)}
    \drawpoint{T}{(2,-3)}
    \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{igpic}
and of course, we can then commute $s'$ and $q$:
\begin{igpic}{0}{4}{-1}{1}
    \drawpoint{O}{(0,2)}
    \definepoint{midP}{(0,1)}
    \drawpoint{P}{(0,0)}
    \definepoint{midSX}{(-1,-0.2)}
    \drawpoint{SX}{(-2,-1)}
    \definepoint{midQ}{(-2,-2)}
    \drawpoint{Q}{(-2,-3)}
    \definepoint{midR}{(-2,-4)}
    \drawpoint{R}{(-2,-5)}
    \definepoint{midS}{(1,-0.2)}
    \drawpoint{S}{(2,-1)}
    \definepoint{midT}{(2,-2)}
    \drawpoint{T}{(2,-3)}
    \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{igpic}
Coalescing our two $\seq{p}s$ nodes gives us:
\begin{igpic}{0}{4}{-1}{1}
    \drawpoint{O}{(0,2)}
    \definepoint{midP}{(0,1)}
    \drawpoint{P}{(0,0)}
    \definepoint{midS}{(0,-1)}
    \drawpoint{S}{(0,-2)}
    \definepoint{midQ}{(-1,-2.2)}
    \drawpoint{Q}{(-2,-3)}
    \definepoint{midR}{(-2,-4)}
    \drawpoint{R}{(-2,-5)}
    \definepoint{midT}{(1,-2.2)}
    \drawpoint{T}{(2,-3)}
    \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{igpic}
so we have merged $s$. Now we merge each patch in $\seq{t}$ in the same
way, resulting in:
\begin{igpic}{0}{4}{-1}{1}
    \drawpoint{O}{(0,2)}
    \definepoint{midP}{(0,1)}
    \drawpoint{P}{(0,0)}
    \definepoint{midS}{(0,-1)}
    \drawpoint{S}{(0,-2)}
    \definepoint{midT}{(0,-3)}
    \drawpoint{T}{(0,-4)}
    \definepoint{midQ}{(0,-5)}
    \drawpoint{Q}{(0,-6)}
    \definepoint{midR}{(0,-7)}
    \drawpoint{R}{(0,-8)}
    \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{igpic}

