[darcs-devel] CommuteNoConflicts

Ben Franksen ben.franksen at online.de
Fri May 18 10:55:10 UTC 2018


I made a bit of progress with this, looking again at how commute works
for catches in the camp paper. Ian distinguishes two groups of cases for
which commute succeeds: those where both sides are unrelated and commute
because all the ingredients commute at the primitive patch level; and
those where the commute succeeds because one side is the result of a
conflicted merge with the other side (because both branches of a merge
must commute to each other).

It looks very much like commuteNoConflicts is the darcs-2 equivalent of
the "unrelated" cases. It has many more cases because of the presence of
Duplicate patches and because the paper does not cover inverse
conflictors whereas commuteNoConflicts does, but otherwise the
correspondence is striking.

Now, why does the instance Conflict for an RL of patches use
commuteNoConflicts and not the plain commute? I think this is an
optimization. I made some tests with my experimental version where I
replace commuteNoConflicts with plain commute and found that there are
conflict scenarios where this version is much slower than the original
version that uses commuteNoConflicts. And the reason we can get away
with commuteNoConflicts here is that darcs-2 stores the transitive set
of conflicting patches (with their context) in each conflictor. Suppose
we have two conflictors p :> q and they conflict. Then the resolution
for q already contains every resolution for p, so commuting p past q and
calculating its resolution in turn would just be wasted work.

For camp this is different, since its conflictors only store the
immediate conflicts (with their context) and not the transitive closure.
This simplifies the camp theory significantly, compared to darcs-2, but
also means that conflict resolution is no longer self-contained, so
resolveConflicts cannot be implemented for a single camp conflictor.
Instead, we will have to first gather all the (contexted) conflicting
sets of all conflictors in the repo that can be commuted to the end.
Then we must reduce this set of sets by taking unions whenever there is
a conflict between any two elements. And then, for each remaining set,
we can calculate the resolution (using the spec I outlined in another
message).

Cheers
Ben



More information about the darcs-devel mailing list