I'm just opening a long-term ticket for this.  Pascal Molli sent me a
nice test for Darcs's conflict marking (attached).  I'll submit it in
Darcs regression test style and link the ensuing discussion here.

NB: From http://en.wikipedia.org/wiki/Operational_transformation

CP/TP1: For every pair of concurrent operations op1 and op2 defined on the same
state, the transformation function T satisfies CP1/TP1 property if and only if:
op_1 \circ T(op_2,op_1) \equiv op_2 \circ T(op_1,op_2)  where where op_i \circ
op_j denotes the sequence of operations containing opi followed by opj;and
where \equiv denotes equivalence of the two sequences of operations.

CP2/TP2: For every three concurrent operations op1,op2 and op3 defined on the
same document state, the transformation function T satisfies CP2/TP2 property
if and only if: T(op_3, op_1 \circ T(op_2,op_1)) = T(op_3, op_2 \circ
T(op_1,op_2)).

Attachments

• darcs.tp2.sh

This is about darcs' conflict marking not being consistent w.r.t the order in
which the patches arrive, which is well-known and expected. We could certainly
"solve" it by not introducing conflict markers, but that wouldn't be very
user-friendly. I don't think an alternative solution exists within the current
general behaviour of darcs patches, but I could be wrong.

We would probably need something like Jean-Phillipe Bernardy's work on
conflict-free revision control to solve this problem and keep "conflict"
markers, but although that might solve the hunk-hunk conflict problem, there's
still the issue of conflicts between arbitrary patch types that don't know
anything about each other.

The test for this issue now pass, what happened?

The failing test for this issue actually passes on darcs2, but doesn't
on hashed repos. Is it something to do with deferring the creation of
the conflict markers that's causing it to pass? (I say that without
knowing how mark-conflicts works...)

This came up again when I searched for no longer failing tests. I tested
this with darcs1 and darcs2 and both refused to fail now. However, due
to the current strangeness of the --repoformat option for darcs-test
(issue2457) I am not 100% sure darcs1 actually got tested despite
darcs-test telling me so.

I'm not entirely sure we should have a test for these properties. Even 
if the tests happen to pass now, I don't think it's deliberate, and I'm 
worried a reasonable future change might break them again.

Your objection sounds reasonable. Besides, it seems I made a mistake:
the test indeed succeeds only for darcs2 repo format.

Re-opening this ticket. The requirement stated here is that the conflict
markup produced by Darcs should be independent of the order of the
patches. I think is a sensible property and I am convinced that it can
be satisfied with both of our existing patch theories (and without
giving up on conflict markup).

Basically, all we have to do is stick to the specification I invented
recently. To summarize: The alternatives to the baseline are merges of
the the maximal independent sets of the components of the conflict graph
whose vertices are all the contexted patches involved in each conflict
(conflictor or merger) that can be commuted to the end of the repo. Of
course, for the displayed markup to be reproducibly order-independent,
we have to sort the contexted patches resulting from the merges of the
independent sets, using some arbitrary but fixed ordering (but we
already do that).

Darcs does not (yet) adhere to the above spec, even though the test
script succeeds. Of course it tests only one possible scenario and that
only involves hunks. Testing this with QuickCheck would be much more
thorough. Any test(s) for this should also make sure to avoid conflicts
with unrecorded changes, so it would be better to use --allow-conflicts
when pulling and only generate the markup in one last 'darcs
mark-conflicts'.

I am marking this as resolved. Test test succeeds. We can always re-
open this if someone finds a counter example.