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

[Owen Stephens]

Hi AntC,

On 10 September 2012 03:04, AntC <anthony_clayden at clear.net.nz> wrote:
> Can I also say that it's really hard to figure out what's going on in the
> darcs world from the wikis and published papers. (This is by way of
apology if
> there's already an answer to my question. I've just failed to find it.)

Yes, I agree, there are various bits and pieces of information, most of it
is
likely out of date, or not quite what's implemented in Darcs at the moment.

> I'm trying to understand conflicts and why they're so problematic.

The complications arise due to the need to be able to conceptually consider
a
darcs repo as a *set* of patches, where the order in which (non-dependent)
patches are pulled doesn't matter. A conflict must therefore always track
the
other patches that it conflicts with, and must update this tracking
whenever it
is commuted with other patches/conflicts.

I did write a quick wiki page on conflictors a while back, which may help to
shed some light on their behaviour/implementation:

    http://darcs.net/Theory/Conflictors

But be warned, conflictors are fairly complicated, and their implementation
is
really difficult to pick apart - we are definitely wanting to replace them
with
something better.

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

Right, so Fork A has <... ; Create A ; Change A> and Fork B wants to pull
just
"Change A".

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

Yes, this is what would happen. Pulling would calculate all the patches that
aren't in Fork B, and present them as a list to the user - the user then can
only select patches that have their dependencies selected too:

    > mkdir darcs-testing
    > cd darcs-testing
    [...]
    > darcs init --repo R
    > cd R
    [...]
    > touch a
    > darcs rec -alm 'add a'
    [...]
    > touch b
    > darcs rec -alm 'add b'
    [...]
    > echo 'foo' > a
    > darcs rec -alm 'change a'
    [...]
    > cd ..
    > darcs init --repo S
    > cd S
    [...]
    > darcs pull ../R
    Mon Sep 10 10:07:00 BST 2012  Owen Stephens <darcs at owenstephens.co.uk>
      * add a
    Shall I pull this patch? (1/3)  [ynW...], or ? for more options: n
    Mon Sep 10 10:07:05 BST 2012  Owen Stephens <darcs at owenstephens.co.uk>
      * add b
    Shall I pull this patch? (2/3)  [ynW...], or ? for more options: n
    Will not ask whether to pull 1 already decided patch.

Note here that having said no to "add a" darcs will not let me select
"change
a".

> But on further thought I saw it:
> - Fork B has already pulled the patch to create F.

Right, so previously, B has pulled the "create F" patch.

> - (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?

No, there would be no conflict, assuming that B has pulled in the "Create F"
patch previously from A. Upon attempting a pull, B would calculate the set
of
patches not in A, which would *not* include "Create F".

> 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?

Currently, in darcs' implementation, there *would* be a conflict between two
files created with the same path, but in different repos, see this page:

    http://darcs.net/Ideas/AddAddConflicts

Also, I think mornfall's GSoC project would go a long way to solving this
problem, by assigning GUIDs to each file, rather than just using the
filepath:

    http://web.mornfall.net/blog/soc_reloaded:_outcomes.html

> (Of course the situation could be a lot more complicated: F could have
been
> renamed or moved along the way; there might be other changes to the
content of
> F -- which is why we have to 'slide' the patches through all intervening
> changes.)

Yes, but it should work fine :-)

> So to resolve this scenario, would this approach help?:
I'm entirely clear what the scenario is, but I think I understand what you
mean.
> - The Create F in Fork B must be pulled from Fork A.
Yes
>   Not just create a file which happens to have the same directory/name
>   (that could just be a concidence).
Yes
> - Pulling the Change F detects the dependency on Create F,
>   and validates that the patch is already pulled into Fork B.
Yes
> - Then 'slide' both the Create and Change into Fork B.
> - At the point of 'sliding' past the Create towards the end of Fork B,
> - Detect it's the same patch and identical effect, so they 'cancel out'.
Well, essentially, but it's done before any real commutation is attempted.
>
> I think this should manage the risk of combinatorial explosion, because
the
> rule is that depended-upon patches must have already been pulled into the
> target repo.

I'm not sure it does, but perhaps I just don't understand your proposal.
Please
do ask more questions or clarify!

> I understand that real-life conflicts are much more complex, and are
typically
> conflicts of partially overlapping 'hunk' changes. But would it help
there to
> have a rule that depended-upon patches must be already pulled into the
target?

As far as I understand this is a rule already - you can't pull patches
without
pulling in their dependencies.

> Thank you
> AntC

Cheers,

Owen.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osuosl.org/pipermail/darcs-users/attachments/20120910/0633a853/attachment-0001.html>