[darcs-users] darcs conflicts/dependencies -- is patch theory the place to start?

[Kevin Quick]

On Sun, 09 Sep 2012 19:04:15 -0700, AntC <anthony_clayden at clear.net.nz>  
wrote:

> I'm trying to understand conflicts and why they're so problematic. I saw  
> in
> one of the papers an example:
> - Fork B wants a patch from Fork A that is a change in content for file  
> F.
> - But preceeding this change in Fork A is a patch that creates file F.
> ==> So there's a dependency: can't commute a change to a file before its
> creation, in order to 'slide' it round to fork B.
>
> At first sight that scenario seems daft:
> - Presumably F didn't exist in the repo at the common point of origin
>   where A and B forked apart. (Otherwise the create couldn't have been  
> valid.)
> - So the change to F wouldn't be valid in Fork B.
> - So Fork B should be pulling both the create and the change.

Without knowing where the original citation came from it's impossible to  
be sure, but I believe the author was probably demonstrating the microcosm  
of attempting to pull only the desired patch.  In actual operation, darcs  
will start with the patch selected and then compute any dependent patches  
(such as the creation of F) and select or inquire about them all,  
resulting in (a superset of) your last item above.  Also, the "slide  
around" is a bit of a misleading term... more on this below.

>
> But on further thought I saw it:
> - Fork B has already pulled the patch to create F.
> - (Let's furthermore say that the only difference between the forks
>    is that B has some unrelated change to file G.)
>
> So we have:
> - O -> Fork A ->             Create F -> Change F
>     -> Fork B -> Change G -> Create F -> (try to) Pull the Change F
>
> Am I right in thinking the Pull would give a conflict under darcs theory?
> That the Change F would have to commute with the Create F, but can't?
> And similarly if Fork B tried to pull both the Create and Change, there  
> would
> be a conflict with the Create that's already in Fork B?

One thing to be aware of is that a Create does not include any contents  
whatsoever.  If you "darcs add" a file and then commit, darcs will ask you  
first if you want to add the file, and then if you want to add the  
contents; most people do this in the same patch, but that patch is  
therefore a Create+Change patch.

An additional consideration here is how darcs handles patches of identical  
impact; i.e. are the two Create F patches identical.   If two patches have  
identical impact, Patch Theory can consider them to be interchangeable.   
In actuality, the handling of this scenario has been one of the areas in  
which the darcs implementation has been evolving.

The pull will come from the repository represented by Fork A.  It will  
start with your selection Change F, add to it the Create F as a dependency  
as it commutes backward to O.  Once it reaches O, it has the minimal set  
of patches required to Then it will attempt to apply that patch bundle to  
the repository designated as Fork B.  To do this, darcs removes all  
identical patches from the bundle (as determined by the patch's hash  
identifier) that also exist Fork B.  It can then attempt to apply the  
remaining patch bundle to Fork B, mostly by considering it as a delta to  
be applied to the current state of Fork B (what other VCS's would call the  
"tip").  At this point, darcs must determine if there are any conflicts.   
In a simple attempt to apply the patch bundle to the Fork B repository, it  
will fail because the Create F in the bundle to import from Fork A will  
fail because F already exists in Fork B.  IIRC, this was as far as the  
original darcs would go and you would encounter a conflict; in more recent  
versions I believe it attempts to identify "identical" changes and  
consider them to be equivalent.

As an aside, the efficiency of the above is improved when tags are  
present.  Darcs will get the list of common tags from both the Fork A and  
Fork B repository.  During the initial creation of the needed patch bundle  
 from Fork A, it can stop when it gets to one of these common tags rather  
than commuting all the way back to the origin because a tag represents a  
specific collection of patches from which darcs can infer a content  
equivalency.

On a more abstract level, Patch Theory can be used to start from a known  
point (usually the current state of the repository), select one (or more)  
patches, and then determine which of the remaining patches depend on it.   
It does not require, nor implement a DAG of patches, and in any particular  
repository, all patches are active and there is no "fork" (in darcs  
terminology, this is "branch by cloning").  Thus there is no concept in  
Patch Theory of a directed chain as you've represented above.  In Patch  
Theory, you do not start with 'O' and "walk forward" along a DAG or chain  
because none exists (and this is probably the primary thing that most  
people oppose in Patch Theory and the darcs implementation: they want  
their VCS to implement a specific *history* as an immutable sequence of  
events).

For example, Fork B is simply a separate repo that contains 3 patches.    
In the darcs implementation there is an implicit ordering of patches as  
they are stored, but this is simply one possible arrangement in which the  
dependencies of a particular patch were considered prior to that patch  
itself.  The initial arrangement matches the commit sequence, but it can  
be changed over time (and this is one of the effects of "darcs optimize").

One could easily imagine two repos that were cloned one from the other  
(what you called "Fork"s above) with the following darcs internal patch  
sequence:

Repo A:  O-A-B-C-D-E-F
Repo B:  O-A-E-D-F-B-C

If you ran a diff comparison of the working tree of these two repos, it  
would be identical, even though the "sequence" of patches is different.   
In Repo B, patch E does not depend on any changes in patches B, C, or D,  
so it was commuted backwards.  It may or may not depend on A, we don't  
know that for sure unless we select E (directly or as a dependency of  
another patch) and attempt to commute with A.

>
> Thank you
> AntC

Sorry the above rambles a bit, but hopefully it helps.  You might also be  
interested in the following paper:  
http://www.staff.science.uu.nl/~swier004/Publications/PrincipledVersionControl.pdf

-Kevin

-- 
-KQ