On Sun, 09 Sep 2012 19:04:15 -0700, AntC <anthony_clay...@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
_______________________________________________
darcs-users mailing list
darcs-users@darcs.net
http://lists.osuosl.org/mailman/listinfo/darcs-users
