Issue 1609 darcs conflict marking gives different results in different orders (OT TP2)

Title darcs conflict marking gives different results in different orders (OT TP2)
Priority bug Status resolved
Milestone Resolved in
Superseder Nosy List darcs-devel, dmitry.kurochkin, ganesh, kowey, momo54
Assigned To
Topics Core

Created on 2009-09-12.16:11:22 by kowey, last changed 2020-07-29.16:07:38 by bfrk.

File name Uploaded Type Edit Remove
darcs.tp2.sh kowey, 2009-09-12.16:11:20 application/x-sh
msg8794 (view) Author: kowey Date: 2009-09-12.16:11:20
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
msg8796 (view) Author: ganesh Date: 2009-09-12.16:43:17
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.
msg15710 (view) Author: gh Date: 2012-05-20.20:37:13


msg15711 (view) Author: gh Date: 2012-05-20.20:58:06
The test for this issue now pass, what happened?
msg15902 (view) Author: owst Date: 2012-07-21.14:51:19
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...)
msg18543 (view) Author: bfrk Date: 2015-06-17.21:09:58
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.
msg18544 (view) Author: ganesh Date: 2015-06-17.21:24:59
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.
msg18553 (view) Author: bfrk Date: 2015-06-17.22:24:13
Your objection sounds reasonable. Besides, it seems I made a mistake:
the test indeed succeeds only for darcs2 repo format.
msg20156 (view) Author: bfrk Date: 2018-06-14.17:50:07
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
msg22281 (view) Author: bfrk Date: 2020-07-29.16:07:35
I am marking this as resolved. Test test succeeds. We can always re-
open this if someone finds a counter example.
Date User Action Args
2009-09-12 16:11:23koweycreate
2009-09-12 16:43:20ganeshsetnosy: + ganesh
messages: + msg8796
2009-09-12 19:27:56koweysetpriority: bug
status: unknown -> deferred
topic: + Core
nosy: kowey, darcs-devel, ganesh, dmitry.kurochkin, momo54
2009-10-21 19:00:56koweylinkpatch1 issues
2012-05-20 20:37:14ghsetmessages: + msg15710
2012-05-20 20:58:06ghsetmessages: + msg15711
2012-07-21 14:51:20owstsetmessages: + msg15902
2015-06-17 21:09:59bfrksetmessages: + msg18543
2015-06-17 21:25:00ganeshsetmessages: + msg18544
2015-06-17 22:24:14bfrksetmessages: + msg18553
2018-06-14 17:50:09bfrksetstatus: deferred -> needs-implementation
messages: + msg20156
2020-07-29 16:07:38bfrksetstatus: needs-implementation -> resolved
messages: + msg22281