<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
<!--Converted with LaTeX2HTML 2008 (1.71)
original version by: Nikos Drakos, CBLU, University of Leeds
* revised and updated by: Marcus Hennecke, Ross Moore, Herb Swan
* with significant contributions from:
Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
<HTML>
<HEAD>
<TITLE>Theory of patches</TITLE>
<META NAME="description" CONTENT="Theory of patches">
<META NAME="keywords" CONTENT="darcs">
<META NAME="resource-type" CONTENT="document">
<META NAME="distribution" CONTENT="global">
<META NAME="Generator" CONTENT="LaTeX2HTML v2008">
<META HTTP-EQUIV="Content-Style-Type" CONTENT="text/css">
<LINK REL="STYLESHEET" HREF="darcs.css">
<LINK REL="next" HREF="node10.html">
<LINK REL="previous" HREF="node8.html">
<LINK REL="up" HREF="darcs.html">
<LINK REL="next" HREF="node10.html">
</HEAD>
<BODY >
<!--Navigation Panel-->
<A NAME="tex2html541"
HREF="node10.html">
<IMG WIDTH="22" HEIGHT="22" title="Next" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="./next.png"></A>
<A NAME="tex2html537"
HREF="darcs.html">
<IMG WIDTH="22" HEIGHT="22" title="Up" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="./up.png"></A>
<A NAME="tex2html531"
HREF="node8.html">
<IMG WIDTH="22" HEIGHT="22" title="Previous" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="./prev.png"></A>
<A NAME="tex2html539"
HREF="node1.html">
<IMG WIDTH="22" HEIGHT="22" title="Contents" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="./contents.png"></A>
<BR>
<B> Next:</B> <A NAME="tex2html542"
HREF="node10.html">DarcsRepo format</A>
<B> Up:</B> <A NAME="tex2html538"
HREF="darcs.html">Darcs 2.2.0 (release) Darcs</A>
<B> Previous:</B> <A NAME="tex2html532"
HREF="node8.html">Darcs commands</A>
<B> <A NAME="tex2html540"
HREF="node1.html">Contents</A></B>
<BR>
<BR>
<!--End of Navigation Panel-->
<!--Table of Child-Links-->
<A NAME="CHILD_LINKS"><STRONG>Subsections</STRONG></A>
<UL>
<LI><A NAME="tex2html543"
HREF="node9.html#SECTION00910000000000000000">Background</A>
<LI><A NAME="tex2html544"
HREF="node9.html#SECTION00920000000000000000">Introduction</A>
<LI><A NAME="tex2html545"
HREF="node9.html#SECTION00930000000000000000">Applying patches</A>
<UL>
<LI><A NAME="tex2html546"
HREF="node9.html#SECTION00931000000000000000">Hunk patches</A>
<LI><A NAME="tex2html547"
HREF="node9.html#SECTION00932000000000000000">Token replace patches</A>
</UL>
<BR>
<LI><A NAME="tex2html548"
HREF="node9.html#SECTION00940000000000000000">Patch relationships</A>
<LI><A NAME="tex2html549"
HREF="node9.html#SECTION00950000000000000000">Commuting patches</A>
<UL>
<LI><A NAME="tex2html550"
HREF="node9.html#SECTION00951000000000000000">Composite patches</A>
<UL>
<LI><A NAME="tex2html551"
HREF="node9.html#SECTION00951010000000000000">Merge</A>
</UL>
<LI><A NAME="tex2html552"
HREF="node9.html#SECTION00952000000000000000">How merges are actually performed</A>
</UL>
<BR>
<LI><A NAME="tex2html553"
HREF="node9.html#SECTION00960000000000000000">Conflicts</A>
<LI><A NAME="tex2html554"
HREF="node9.html#SECTION00970000000000000000">Patch string formatting</A>
<UL>
<LI><A NAME="tex2html555"
HREF="node9.html#SECTION00970010000000000000">Merger patches</A>
<LI><A NAME="tex2html556"
HREF="node9.html#SECTION00970020000000000000">Named patches</A>
</UL></UL>
<!--End of Table of Child-Links-->
<HR>
<H1><A NAME="SECTION00900000000000000000"></A>
<A NAME="Patch"></A>
<BR>
Theory of patches
</H1>
<P>
<P>
<H1><A NAME="SECTION00910000000000000000">
Background</A>
</H1>
<P>
I think a little background on the author is in order. I am a physicist,
and think like a physicist. The proofs and theorems given here are what I
would call ``physicist'' proofs and theorems, which is to say that while
the proofs may not be rigorous, they are practical, and the theorems are
intended to give physical insight. It would be great to have a
mathematician work on this to give patch theory better formalized
foundations.
<P>
From the beginning of this theory, which originated as the result of a
series of email discussions with Tom Lord, I have looked at patches as
being analogous to the operators of quantum mechanics. I include in this
appendix footnotes explaining the theory of patches in terms of the theory
of quantum mechanics. I advise against taking this analogy too seriously,
although it could provide some insight into how a physicist might think
about darcs.
<P>
<H1><A NAME="SECTION00920000000000000000">
Introduction</A>
</H1>
<P>
A patch describes a change to the tree. It could be either a primitive
patch (such as a file add/remove, a directory rename, or a hunk replacement
within a file), or a composite patch describing many such changes. Every
patch type must satisfy the conditions described in this appendix. The
theory of patches is independent of the data which the patches manipulate,
which is what makes it both powerful and useful, as it provides a framework
upon which one can build a revision control system in a sane manner.
<P>
Although in a sense, the defining property of any patch is that it can be
applied to a certain tree, and thus make a certain change, this change does
not wholly define the patch. A patch is defined by a
<I>representation</I>, together with a set of rules for how it behaves
(which it has in common with its patch type). The <I>representation</I> of
a patch defines what change that particular patch makes, and must be
defined in the context of a specific tree. The theory of patches is a
theory of the many ways one can change the representation of a patch to
place it in the context of a different tree. The patch itself is not
changed, since it describes a single change, which must be the same
regardless of its representation<A NAME="tex2html22"
HREF="footnode.html#foot2539"><SUP>A.1</SUP></A>.
<P>
So how does one define a tree, or the context of a patch? The simplest way
to define a tree is as the result of a series of patches applied to the
empty tree<A NAME="tex2html23"
HREF="footnode.html#foot2400"><SUP>A.2</SUP></A>. Thus, the
context of a patch consists of the set of patches that precede it.
<P>
<H1><A NAME="SECTION00930000000000000000">
Applying patches</A>
</H1>
<P>
<H2><A NAME="SECTION00931000000000000000">
Hunk patches</A>
</H2>
<P>
Hunks are an example of a complex filepatch. A hunk is a set of lines of a
text file to be replaced by a different set of lines. Either of these sets
may be empty, which would mean a deletion or insertion of lines.
<P>
<H2><A NAME="SECTION00932000000000000000"></A><A NAME="token_replace"></A>
<BR>
Token replace patches
</H2>
<P>
Although most filepatches will be hunks, darcs is clever enough to support
other types of changes as well. A ``token replace'' patch replaces all
instances of a given token with some other version. A token, here, is
defined by a regular expression, which must be of the simple [a-z...] type,
indicating which characters are allowed in a token, with all other
characters acting as delimiters. For example, a C identifier would be a
token with the flag <code>[A-Za-z_0-9]</code>.
<P>
What makes the token replace patch special is the fact that a token replace
can be merged with almost any ordinary hunk, giving exactly what you would
want. For example, you might want to change the patch type <TT>TokReplace</TT> to <TT>TokenReplace</TT> (if you decided that saving two
characters of space was stupid). If you did this using hunks, it would
modify every line where <TT>TokReplace</TT> occurred, and quite likely provoke
a conflict with another patch modifying those lines. On the other hand, if
you did this using a token replace patch, the only change that it could
conflict with would be if someone else had used the token ``<TT>TokenReplace</TT>'' in their patch rather than TokReplace--and that actually
would be a real conflict!
<P>
<H1><A NAME="SECTION00940000000000000000">
Patch relationships</A>
</H1>
<P>
The simplest relationship between two patches is that of ``sequential''
patches, which means that the context of the second patch (the one on the
left) consists of the first patch (on the right) plus the context of the
first patch. The composition of two patches (which is also a patch) refers
to the patch which is formed by first applying one and then the other. The
composition of two patches, <IMG
WIDTH="22" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img16.png"
ALT="$P_1$"> and <IMG
WIDTH="22" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img17.png"
ALT="$P_2$"> is represented as <IMG
WIDTH="39" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img18.png"
ALT="$P_2P_1$">,
where <IMG
WIDTH="22" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img16.png"
ALT="$P_1$"> is to be applied first, then <IMG
WIDTH="22" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img17.png"
ALT="$P_2$"><A NAME="tex2html24"
HREF="footnode.html#foot2410"><SUP>A.3</SUP></A>
<P>
There is one other very useful relationship that two patches can have,
which is to be parallel patches, which means that the two patches have an
identical context (i.e. their representation applies to identical trees).
This is represented by <!-- MATH
$P_1\parallel P_2$
-->
<IMG
WIDTH="56" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img19.png"
ALT="$P_1\parallel P_2$">. Of course, two patches may also
have no simple relationship to one another. In that case, if you want to
do something with them, you'll have to manipulate them with respect to
other patches until they are either in sequence or in parallel.
<P>
The most fundamental and simple property of patches is that they must be
invertible. The inverse of a patch is described by: <IMG
WIDTH="34" HEIGHT="16" ALIGN="BOTTOM" BORDER="0"
SRC="img20.png"
ALT="$P^{ -1}$">. In the
darcs implementation, the inverse is required to be computable from
knowledge of the patch only, without knowledge of its context, but that
(although convenient) is not required by the theory of patches.
<P>
<DIV><B>Definition 1</B>
<I>The inverse of patch <IMG
WIDTH="17" HEIGHT="14" ALIGN="BOTTOM" BORDER="0"
SRC="img21.png"
ALT="$P$"> is <IMG
WIDTH="34" HEIGHT="16" ALIGN="BOTTOM" BORDER="0"
SRC="img20.png"
ALT="$P^{ -1}$">, which is the ``simplest'' patch for
which the composition <IMG
WIDTH="46" HEIGHT="16" ALIGN="BOTTOM" BORDER="0"
SRC="img22.png"
ALT="\( P^{ -1} P \)"> makes no changes to the tree.</I></DIV><P></P>
Using this definition, it is trivial to prove the following theorem
relating to the inverse of a composition of two patches.
<P>
<DIV><B>Theorem 1</B>
<I>The inverse of the composition of two patches is
</I>
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH
\begin{displaymath}
(P_2 P_1)^{ -1} = P_1^{ -1} P_2^{ -1}.
\end{displaymath}
-->
<IMG
WIDTH="146" HEIGHT="28" BORDER="0"
SRC="img23.png"
ALT="\begin{displaymath}(P_2 P_1)^{ -1} = P_1^{ -1} P_2^{ -1}. \end{displaymath}">
</DIV>
<BR CLEAR="ALL">
<P></P></DIV><P></P>
Moreover, it is possible to show that the right inverse of a patch is equal
to its left inverse. In this respect, patches continue to be analogous to
square matrices, and indeed the proofs relating to these properties of the
inverse are entirely analogous to the proofs in the case of matrix
multiplication. The compositions proofs can also readily be extended to
the composition of more than two patches.
<P>
<H1><A NAME="SECTION00950000000000000000">
Commuting patches</A>
</H1>
<P>
<H2><A NAME="SECTION00951000000000000000">
Composite patches</A>
</H2>
<P>
Composite patches are made up of a series of patches intended to be applied
sequentially. They are represented by a list of patches, with the first
patch in the list being applied first.
<P>
<P>
The first way (of only two) to change the context of a patch is by
commutation, which is the process of changing the order of two sequential
patches.
<P>
<DIV><B>Definition 2</B>
<I>The commutation of patches <IMG
WIDTH="22" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img16.png"
ALT="$P_1$"> and <IMG
WIDTH="22" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img17.png"
ALT="$P_2$"> is represented by
</I>
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH
\begin{displaymath}
P_2 P_1 \longleftrightarrow {P_1}' {P_2}'.
\end{displaymath}
-->
<IMG
WIDTH="119" HEIGHT="26" BORDER="0"
SRC="img24.png"
ALT="\begin{displaymath}P_2 P_1 \longleftrightarrow {P_1}' {P_2}'. \end{displaymath}">
</DIV>
<BR CLEAR="ALL">
<P></P><I>
Here <IMG
WIDTH="22" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img25.png"
ALT="$P_1'$"> is intended to describe the same change as <IMG
WIDTH="22" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img16.png"
ALT="$P_1$">, with the
only difference being that <IMG
WIDTH="22" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img25.png"
ALT="$P_1'$"> is applied after <IMG
WIDTH="22" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img26.png"
ALT="$P_2'$"> rather than
before <IMG
WIDTH="22" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img17.png"
ALT="$P_2$">.</I></DIV><P></P>
The above definition is obviously rather vague, the reason being that what
is the ``same change'' has not been defined, and we simply assume (and
hope) that the code's view of what is the ``same change'' will match those
of its human users. The `<!-- MATH
$\longleftrightarrow$
-->
<IMG
WIDTH="34" HEIGHT="15" ALIGN="BOTTOM" BORDER="0"
SRC="img27.png"
ALT="$\longleftrightarrow $">' operator should be read as something
like the <IMG
WIDTH="29" HEIGHT="15" ALIGN="BOTTOM" BORDER="0"
SRC="img28.png"
ALT="$==$"> operator in C, indicating that the right hand side performs
identical changes to the left hand side, but the two patches are in
reversed order. When read in this manner, it is clear that commutation
must be a reversible process, and indeed this means that commutation
<I>can</I> fail, and must fail in certain cases. For example, the creation
and deletion of the same file cannot be commuted. When two patches fail to
commutex, it is said that the second patch depends on the first, meaning
that it must have the first patch in its context (remembering that the
context of a patch is a set of patches, which is how we represent a tree).
<A NAME="tex2html25"
HREF="footnode.html#foot2432"><SUP>A.4</SUP></A>
<P>
<H4><A NAME="SECTION00951010000000000000">
Merge</A>
</H4>
The second way one can change the context of a patch is by a <B>merge</B>
operation. A merge is an operation that takes two parallel patches and
gives a pair of sequential patches. The merge operation is represented by
the arrow ``<!-- MATH
$\Longrightarrow$
-->
<IMG
WIDTH="30" HEIGHT="13" ALIGN="BOTTOM" BORDER="0"
SRC="img30.png"
ALT="\( \Longrightarrow \)">''.
<P>
<DIV><A NAME="merge_dfn"><B>Definition 3</B></A>
<I>The result of a merge of two patches, <IMG
WIDTH="22" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img16.png"
ALT="$P_1$"> and <IMG
WIDTH="22" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img17.png"
ALT="$P_2$"> is one of two patches,
<IMG
WIDTH="22" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img25.png"
ALT="$P_1'$"> and <IMG
WIDTH="22" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img26.png"
ALT="$P_2'$">, which satisfy the relationship:
</I>
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH
\begin{displaymath}
P_2 \parallel P_1 \Longrightarrow {P_2}' P_1 \longleftrightarrow {P_1}' P_2.
\end{displaymath}
-->
<IMG
WIDTH="205" HEIGHT="28" BORDER="0"
SRC="img31.png"
ALT="\begin{displaymath}P_2 \parallel P_1 \Longrightarrow {P_2}' P_1 \longleftrightarrow {P_1}' P_2. \end{displaymath}">
</DIV>
<BR CLEAR="ALL">
<P></P></DIV><P></P>
Note that the sequential patches resulting from a merge are <I>required</I>
to commutex. This is an important consideration, as without it most of the
manipulations we would like to perform would not be possible. The other
important fact is that a merge <I>cannot fail</I>. Naively, those two
requirements seem contradictory. In reality, what it means is that the
result of a merge may be a patch which is much more complex than any we
have yet considered<A NAME="tex2html26"
HREF="footnode.html#foot2540"><SUP>A.5</SUP></A>.
<P>
<H2><A NAME="SECTION00952000000000000000">
How merges are actually performed</A>
</H2>
<P>
The constraint that any two compatible patches (patches which can
successfully be applied to the same tree) can be merged is actually quite
difficult to apply. The above merge constraints also imply that the result
of a series of merges must be independent of the order of the merges. So
I'm putting a whole section here for the interested to see what algorithms
I use to actually perform the merges (as this is pretty close to being the
most difficult part of the code).
<P>
The first case is that in which the two merges don't actually conflict, but
don't trivially merge either (e.g. hunk patches on the same file, where the
line number has to be shifted as they are merged). This kind of merge can
actually be very elegantly dealt with using only commutation and inversion.
<P>
There is a handy little theorem which is immensely useful when trying to
merge two patches.
<P>
<DIV><A NAME="merge_thm"><B>Theorem 2</B></A>
<I><!-- MATH
$P_2' P_1 \longleftrightarrow P_1' P_2$
-->
<IMG
WIDTH="112" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img32.png"
ALT="$ P_2' P_1 \longleftrightarrow P_1' P_2 $"> if and only if <!-- MATH
$P_1'^{ -1}
P_2' \longleftrightarrow P_2 P_1^{ -1}$
-->
<IMG
WIDTH="140" HEIGHT="36" ALIGN="MIDDLE" BORDER="0"
SRC="img33.png"
ALT="$ P_1'^{ -1}
P_2' \longleftrightarrow P_2 P_1^{ -1} $">, provided both commutations succeed. If
either commutex fails, this theorem does not apply.</I></DIV><P></P>
This can easily be proven by multiplying both sides of the first
commutation by <IMG
WIDTH="38" HEIGHT="36" ALIGN="MIDDLE" BORDER="0"
SRC="img34.png"
ALT="$P_1'^{ -1}$"> on the left, and by <IMG
WIDTH="34" HEIGHT="36" ALIGN="MIDDLE" BORDER="0"
SRC="img35.png"
ALT="$P_1^{ -1}$"> on the right.
Besides being used in merging, this theorem is also useful in the recursive
commutations of mergers. From Theorem <A HREF="#merge_thm"><IMG ALIGN="BOTTOM" BORDER="1" ALT="[*]"
SRC="./crossref.png"></A>, we see that the
merge of <IMG
WIDTH="22" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img16.png"
ALT="$P_1$"> and <IMG
WIDTH="22" HEIGHT="32" ALIGN="MIDDLE" BORDER="0"
SRC="img26.png"
ALT="$P_2'$"> is simply the commutation of <IMG
WIDTH="22" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img17.png"
ALT="$P_2$"> with <IMG
WIDTH="34" HEIGHT="36" ALIGN="MIDDLE" BORDER="0"
SRC="img35.png"
ALT="$P_1^{ -1}$"> (making sure to do the commutation the right way). Of course, if this
commutation fails, the patches conflict. Moreover, one must check that the
merged result actually commutes with <IMG
WIDTH="22" HEIGHT="30" ALIGN="MIDDLE" BORDER="0"
SRC="img16.png"
ALT="$P_1$">, as the theorem applies only
when <I>both</I> commutations are successful.
<P>
Of course, there are patches that actually conflict, meaning a merge where
the two patches truly cannot both be applied (e.g. trying to create a file
and a directory with the same name). We deal with this case by creating a
special kind of patch to support the merge, which we will call a
``merger''. Basically, a merger is a patch that contains the two patches
that conflicted, and instructs darcs basically to resolve the conflict. By
construction a merger will satisfy the commutation property (see
Definition <A HREF="#merge_dfn"><IMG ALIGN="BOTTOM" BORDER="1" ALT="[*]"
SRC="./crossref.png"></A>) that characterizes all merges. Moreover the
merger's properties are what makes the order of merges unimportant (which
is a rather critical property for darcs as a whole).
<P>
The job of a merger is basically to undo the two conflicting patches, and
then apply some sort of a ``resolution'' of the two instead. In the case
of two conflicting hunks, this will look much like what CVS does, where it
inserts both versions into the file. In general, of course, the two
conflicting patches may both be mergers themselves, in which case the
situation is considerably more complicated.
<P>
Much of the merger code depends on a routine which recreates from a single
merger the entire sequence of patches which led up to that merger (this is,
of course, assuming that this is the complicated general case of a merger
of mergers of mergers). This ``unwind'' procedure is rather complicated,
but absolutely critical to the merger code, as without it we wouldn't even
be able to undo the effects of the patches involved in the merger, since we
wouldn't know what patches were all involved in it.
<P>
Basically, unwind takes a merger such as
<PRE>
M( M(A,B), M(A,M(C,D)))
</PRE>
From which it recreates a merge history:
<PRE>
C
A
M(A,B)
M( M(A,B), M(A,M(C,D)))
</PRE>
(For the curious, yes I can easily unwind this merger in my head [and on
paper can unwind insanely more complex mergers]--that's what comes of
working for a few months on an algorithm.) Let's start with a simple
unwinding. The merger <code>M(A,B)</code> simply means that two patches
(<code>A</code> and <code>B</code>) conflicted, and of the two of them <code>A</code> is
first in the history. The last two patches in the unwinding of any merger
are always just this easy. So this unwinds to:
<PRE>
A
M(A,B)
</PRE>
What about a merger of mergers? How about <code>M(A,M(C,D))</code>. In this case
we know the two most recent patches are:
<PRE>
A
M(A,M(C,D))
</PRE>
But obviously the unwinding isn't complete, since we don't yet see where
<code>C</code> and <code>D</code> came from. In this case we take the unwinding of
<code>M(C,D)</code> and drop its latest patch (which is <code>M(C,D)</code> itself) and
place that at the beginning of our patch train:
<PRE>
C
A
M(A,M(C,D))
</PRE>
As we look at <code>M( M(A,B), M(A,M(C,D)))</code>, we consider the unwindings of
each of its subpatches:
<PRE>
C
A A
M(A,B) M(A,M(C,D))
</PRE>
As we did with <code>M(A,M(C,D))</code>, we'll drop the first patch on the
right and insert the first patch on the left. That moves us up to the two
<code>A</code>'s. Since these agree, we can use just one of them (they
``should'' agree). That leaves us with the <code>C</code> which goes first.
<P>
The catch is that things don't always turn out this easily. There is no
guarantee that the two <code>A</code>'s would come out at the same time, and if
they didn't, we'd have to rearrange things until they did. Or if there was
no way to rearrange things so that they would agree, we have to go on to
plan B, which I will explain now.
<P>
Consider the case of <code>M( M(A,B), M(C,D))</code>. We can easily unwind the
two subpatches
<PRE>
A C
M(A,B) M(C,D)
</PRE>
Now we need to reconcile the <code>A</code> and <code>C</code>. How do we do this?
Well, as usual, the solution is to use the most wonderful
Theorem <A HREF="#merge_thm"><IMG ALIGN="BOTTOM" BORDER="1" ALT="[*]"
SRC="./crossref.png"></A>. In this case we have to use it in the reverse of
how we used it when merging, since we know that <code>A</code> and <code>C</code> could
either one be the <I>last</I> patch applied before <code>M(A,B)</code> or
<code>M(C,D)</code>. So we can find <code>C'</code> using
<BR><P></P>
<DIV ALIGN="CENTER">
<!-- MATH
\begin{displaymath}
A^{ -1} C \longleftrightarrow C' A'^{ -1}
\end{displaymath}
-->
<IMG
WIDTH="128" HEIGHT="24" BORDER="0"
SRC="img36.png"
ALT="\begin{displaymath}
A^{ -1} C \longleftrightarrow C' A'^{ -1}
\end{displaymath}">
</DIV>
<BR CLEAR="ALL">
<P></P>
Giving an unwinding of
<PRE>
C'
A
M(A,B)
M( M(A,B), M(C,D) )
</PRE>
There is a bit more complexity to the unwinding process (mostly having to
do with cases where you have deeper nesting), but I think the general
principles that are followed are pretty much included in the above
discussion.
<P>
<H1><A NAME="SECTION00960000000000000000">
Conflicts</A>
</H1>
<P>
There are a couple of simple constraints on the routine which determines
how to resolve two conflicting patches (which is called `glump'). These
must be satisfied in order that the result of a series of merges is always
independent of their order. Firstly, the output of glump cannot change
when the order of the two conflicting patches is switched. If it did, then
commuting the merger could change the resulting patch, which would be bad.
Secondly, the result of the merge of three (or more) conflicting patches
cannot depend on the order in which the merges are performed.
<P>
The conflict resolution code (glump) begins by ``unravelling'' the merger
into a set of sequences of patches. Each sequence of patches corresponds
to one non-conflicted patch that got merged together with the others. The
result of the unravelling of a series of merges must obviously be
independent of the order in which those merges are performed. This
unravelling code (which uses the unwind code mentioned above) uses probably
the second most complicated algorithm. Fortunately, if we can successfully
unravel the merger, almost any function of the unravelled merger satisfies
the two constraints mentioned above that the conflict resolution code must
satisfy.
<P>
<H1><A NAME="SECTION00970000000000000000">
Patch string formatting</A>
</H1>
<P>
Of course, in order to store our patches in a file, we'll have to save them
as some sort of strings. The convention is that each patch string will end
with a newline, but on parsing we skip any amount of whitespace between
patches.
<P>
<H4><A NAME="SECTION00970010000000000000">
Merger patches</A>
</H4>
Merge two patches. The MERGERVERSION is included to allow some degree of
backwards compatibility if the merger algorithm needs to be changed.
<PRE>
merger MERGERVERSION
<first patch>
<second patch>
</PRE>
<P>
<H4><A NAME="SECTION00970020000000000000">
Named patches</A>
</H4>
<P>
Named patches are displayed as a ``patch id'' which is in square brackets,
followed by a patch. Optionally, after the patch id (but before the patch
itself) can come a list of dependencies surrounded by angle brackets. Each
dependency consists of a patch id.
<P>
<HR>
<!--Navigation Panel-->
<A NAME="tex2html541"
HREF="node10.html">
<IMG WIDTH="22" HEIGHT="22" title="Next" ALIGN="BOTTOM" BORDER="0" ALT="next"
SRC="./next.png"></A>
<A NAME="tex2html537"
HREF="darcs.html">
<IMG WIDTH="22" HEIGHT="22" title="Up" ALIGN="BOTTOM" BORDER="0" ALT="up"
SRC="./up.png"></A>
<A NAME="tex2html531"
HREF="node8.html">
<IMG WIDTH="22" HEIGHT="22" title="Previous" ALIGN="BOTTOM" BORDER="0" ALT="previous"
SRC="./prev.png"></A>
<A NAME="tex2html539"
HREF="node1.html">
<IMG WIDTH="22" HEIGHT="22" title="Contents" ALIGN="BOTTOM" BORDER="0" ALT="contents"
SRC="./contents.png"></A>
<BR>
<B> Next:</B> <A NAME="tex2html542"
HREF="node10.html">DarcsRepo format</A>
<B> Up:</B> <A NAME="tex2html538"
HREF="darcs.html">Darcs 2.2.0 (release) Darcs</A>
<B> Previous:</B> <A NAME="tex2html532"
HREF="node8.html">Darcs commands</A>
<B> <A NAME="tex2html540"
HREF="node1.html">Contents</A></B>
<!--End of Navigation Panel-->
<ADDRESS>
2009-01-22
</ADDRESS>
</BODY>
</HTML>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
c92510584fd710384970429bf5ec0aaa
>
files
>
72
