[darcs-devel] conflict resolution: a formal specification

[Ben Franksen]

I think I have finally arrived at an understanding of how conflict
resolution is supposed to work. As it turns out, Darcs currently does
not alway behave as I think it should.

Here is my specification of what conflict resolution should do:

Given a conflictor representing the primitive patch q at the end of a
repo r, define the transitive set of conflicting (primitive) patches
C(q) as the smallest set of patches in r such that

 1) q `elem` C(q)
 2) if p `elem` C(q) and s conflicts with p then s `elem`C(q)

The notation here is a bit lax: I use the same name for a primitive
patch and the catch/repopatch/conflictor representing it. Furthermore,
names for primitive patches are supposed to ignore changes due to
commutation: if (o,p) <-> (p',o') I regard p and p' as equivalent and
use the same letter p to denote both. That is, p stands for a whole
equivalence class of patches.

It is assumed here that the semantics of conflictors is such that for
each p in C(q) we can construct a context for p, that is, there is a
subsequence c⁻¹ of E(r) such that E(r) :> c :> p is well-typed and c is
minimal in the sense that none of its elements can be commuted past p.
Here, E(r) is the effect of the repo r.

Now, form the set M(q) of all maximal non-conflicting subsets of C(q).
"Non-conflicting subset" means that for any two elements s and t of the
subset, the sequences consisting of s and t, each together with their
contexts, cleanly merge.

The set R(q) of sequences of primitive patches resulting from merging
each maximally non-conflicting subset in M(q) is called the /conflict
resolution/ of q. R(q) is uniquely determined up to commutation.

The conflict markup that the user gets presented should present the
elements of R(q) as the alternatives to the baseline (which we get from
r by obliterating all the patches in C(q)).

This is the only reasonable definition of conflict resolution I can
think of.

I have made some tests and found that darcs-2 does not follow this spec
in all cases. A simple example is constructed by merging a "conflict
chain", where we merge (independent) patches p_1..p_n into a baseline
context c, such that p_i conflicts only with p_(i+1). For instance, let
p_i be a hunk that changes lines (i,i+1) by appending the number i to
both lines. Starting with a file f with content

a
b
c
d
e
f

p_1 changes this to

a1
b1
c
d
e
f

etc. When we merge these patches by pulling them into the common
baseline c, darcs-2 gives us the following markup:

v v v v v v v
a
b
c
d
e
f
=============
a
b
c
d
e5
f5
*************
a
b
c
d4
e4
f
*************
a
b2
c2
d
e
f
*************
a1
b1
c
d
e
f
*************
a1
b1
c3
d3
e5
f5
^ ^ ^ ^ ^ ^ ^

which corresponds to merges of the following subsets:

  {p5}, {p4}, {p2}, {p1}, {p1,p3,p5}

In contrast, the spec above would arrive at:

  {p2, p5}, {p2, p4}, {p1, p4}, {p1, p3, p5}

which, when translated to markup, results in

v v v v v v v
a
b
c
d
e
f
=============
a
b2
c2
d
e5
f5
*************
a
b2
c2
d4
e4
f
*************
a1
b1
c
d4
e4
f
*************
a1
b1
c3
d3
e5
f5
^ ^ ^ ^ ^ ^ ^

I find this result a lot more consistent than what Darcs gives us today.
Also note that according to our spec we get one less alternative.

One more point to note:

The above specification of conflict resolution also points a way toward
more informative markup. When constructing the set C(q), we could
associate each primitive patch not only with a suitable context, but
also with the abstract (meta data) hash of the named patch that
originally contained it. When forming R(q) the single hash would be
transformed into a set of hashes and we could enrich the markup by
adding this set of hashes, so the user gets an idea where each
alternative came from. For instance, suppose we have

p1: 64673593...
p2: 4ad7ebde...
p3: 83e97372...
p4: 5c3e62d4...
p5: 2de3c70f...

we could produce:

v v v v v v v
a
b
c
d
e
f
============= {4ad7ebde,2de3c70f}
a
b2
c2
d
e5
f5
************* {4ad7ebde,5c3e62d4}
a
b2
c2
d4
e4
f
************* {64673593,5c3e62d4}
a1
b1
c
d4
e4
f
************* {64673593,83e97372,2de3c70f}
a1
b1
c3
d3
e5
f5
^ ^ ^ ^ ^ ^ ^

Cheers
Ben