[darcs-devel] about conflict resolution

[Ben Franksen]

Am 03.10.2018 um 15:05 schrieb Ben Franksen:
> Let's assume we have the following invariant, which I know holds at
> least for V3 conflictors (because I added this as a property and tested
> with -q 50000): all patches that a conflictor C (directly) conflicts
> with can be commuted past C, thereby turning it back into a prim patch.
> So if we have C1 :> C2 which do not commute, then we can still commute
> all patches that C2 conflicts with past C2 (and therefore necessarily
> past C1, too), resulting in C1' :> C2', where C2' is no longer
> conflicted i.e. a prim. Now permutivity gives us that C1' :> C2' don't
> commute either. This shows that there is a commutation of our repo in
> which a "good" (prim) patch depends on (a commuted version of) C1. Does
> that mean we are justified in regarding C1 as resolved? Not yet. We must
> consider the possibility that some of the conflicts contained in C1 have
> been taken over by the patches we commuted past. In other words, some
> patches that C1 conflicts with, also conflict with C2. Since these have
> been commuted past C1, they are now the carriers of conflicts that were
> previously contained in C1, and we need to add their resolutions to our
> result. But that's exactly what the algorithm will do: these patches are
> (in our original repo) in the past of C1; we'll get to them when it is
> their turn. They commute past C1 and C2, so their resolution will be
> added, unless yet another patch depends on them.

Hmmm. This last statement is only true if we actually use commute, but
we currently use commuteNoConflicts in the algorithm. This means the
patches that C1 conflicts with will not be added to the resolution
because we can't "commuteNoConflicts" them past C1.

So is that perhaps wrong i.e. a bug? Should we use the general commute here?

I believe the algorithm works with commuteNoConflicts for V2 conflictors
because the contexts stored together with these conflicing patches may
themselves be conflictors. In fact, I believe that the enormous
complexity of the V2 code is at least in part caused by the (IMHO
misguided) desire to be able to extract a complete conflict resolution
from a conflictor at the end of the repo in a self-contained way, i.e.
without having to look at earlier patches in the repo. What I think is
that the C1 in our example is already part of some context inside the
conflictor C2, so its resolution will be added as part of calling
resolveConflicts on C2. I need to verify that this is the case by
constructing a suitable example (perhaps the examples in
tests/*hidden-conflict* will do) and inspecting the V2 conflictors that
are generated.

Anyway, for V3 patches we will certainly need to use the general commute
for the resolution algorithm, because contexts in V3 conflictors consist
of prim patches. In fact, V3 conflictors reference only those (prim)
patches that they /directly/ conflict with, which means that a
self-contained resolveConflicts method can't be implemented anyway.

Cheers
Ben