William Uther
2008-01-17 02:57:23 UTC
Hi,
I have brief question about DARCS correctness. I must admit to
being more familiar with Operational Transformation theory better
than Darcs theory of patches, but I believe the two are very
similar. There is a brief intro to OT theory here: http://
revctrl.org/OperationalTransformation . In OT theory there are two
correctness constraints on any system, which I believe are related to
the two constraints in DARCS that patch commute is its own inverse,
and that:
ABC <=> B'A'C <=> B'C'A'' <=> C''B''A'' <=> C''A'''B''' <=>
A''''C'''B''' <=> A''''B''''C'''' where A'''' = A, B'''' = B and
C'''' = C
Basically, if you start off with a set of patches, you may need to
transform them to apply them, but if you do it right then the order
in which you apply them should not affect the final state of the system.
My question is: does that requirement apply to conflicts (merger
patches) in the DARCS theory?
The reason I ask that question is because my understanding of the
DARCS commute operation for textual patches is that it is very
similar to Ressel's Transformation Functions in OT theory. These are
known NOT to be valid. However, there are no conflicts in OT theory
- any result is acceptable as long as you get the same result
everywhere. The particular counter example I have for Ressel's
transformations, when translated to work with DARCS, causes
conflicts. Re-stating the question above in a slightly different form:
If I have two Darcs workspaces, each of which have the same set of
patches, but in different orders, should these workspaces be
identical (even in the presence of conflicts)?
If the answer is 'yes', then I have a counter-example. If the answer
is 'no', is there a write-up on how this affects correctness?
Here is the (possible) counter example (converted to Darcs from the
revctrl wiki page mentioned above):
#! /bin/sh
mkdir darcsTest
cd darcsTest
mkdir site1
cd site1
darcs init
cat > myfile <<EOF
Line A
Line B
Line C
EOF
darcs add myfile
darcs record -am "initial record" --author=EMAIL
cd ..
darcs get site1 site2
darcs get site1 site3
cd site1
cat > myfile <<EOF
Line A
Line B
Line X
Line C
EOF
darcs record -am "op 1" --author=EMAIL
cd ../site2
cat > myfile <<EOF
Line A
Line C
EOF
darcs record -am "op 2" --author=EMAIL
cd ../site3
cat > myfile <<EOF
Line A
Line Y
Line B
Line C
EOF
darcs record -am "op 3" --author=EMAIL
#having set up the operations, lets do some pulls to sync everything
#first each of site2 and site3 pulls the other
darcs pull -a ../site2
cd ../site2
darcs pull -a ../site3
# next they both pull site1
darcs pull -a ../site1
cd ../site3
darcs pull -a ../site1
# Now we'll check for differences in the result
cd ..
diff site2/myfile site3/myfile
If the final diff outputs anything then the workspaces are in
different states after pulling all the patches... and I get output
under Darcs 1.0.9rc1 which is the version installed on one of the
servers here.
Thanks in advance for your thoughts,
Will :-}
I have brief question about DARCS correctness. I must admit to
being more familiar with Operational Transformation theory better
than Darcs theory of patches, but I believe the two are very
similar. There is a brief intro to OT theory here: http://
revctrl.org/OperationalTransformation . In OT theory there are two
correctness constraints on any system, which I believe are related to
the two constraints in DARCS that patch commute is its own inverse,
and that:
ABC <=> B'A'C <=> B'C'A'' <=> C''B''A'' <=> C''A'''B''' <=>
A''''C'''B''' <=> A''''B''''C'''' where A'''' = A, B'''' = B and
C'''' = C
Basically, if you start off with a set of patches, you may need to
transform them to apply them, but if you do it right then the order
in which you apply them should not affect the final state of the system.
My question is: does that requirement apply to conflicts (merger
patches) in the DARCS theory?
The reason I ask that question is because my understanding of the
DARCS commute operation for textual patches is that it is very
similar to Ressel's Transformation Functions in OT theory. These are
known NOT to be valid. However, there are no conflicts in OT theory
- any result is acceptable as long as you get the same result
everywhere. The particular counter example I have for Ressel's
transformations, when translated to work with DARCS, causes
conflicts. Re-stating the question above in a slightly different form:
If I have two Darcs workspaces, each of which have the same set of
patches, but in different orders, should these workspaces be
identical (even in the presence of conflicts)?
If the answer is 'yes', then I have a counter-example. If the answer
is 'no', is there a write-up on how this affects correctness?
Here is the (possible) counter example (converted to Darcs from the
revctrl wiki page mentioned above):
#! /bin/sh
mkdir darcsTest
cd darcsTest
mkdir site1
cd site1
darcs init
cat > myfile <<EOF
Line A
Line B
Line C
EOF
darcs add myfile
darcs record -am "initial record" --author=EMAIL
cd ..
darcs get site1 site2
darcs get site1 site3
cd site1
cat > myfile <<EOF
Line A
Line B
Line X
Line C
EOF
darcs record -am "op 1" --author=EMAIL
cd ../site2
cat > myfile <<EOF
Line A
Line C
EOF
darcs record -am "op 2" --author=EMAIL
cd ../site3
cat > myfile <<EOF
Line A
Line Y
Line B
Line C
EOF
darcs record -am "op 3" --author=EMAIL
#having set up the operations, lets do some pulls to sync everything
#first each of site2 and site3 pulls the other
darcs pull -a ../site2
cd ../site2
darcs pull -a ../site3
# next they both pull site1
darcs pull -a ../site1
cd ../site3
darcs pull -a ../site1
# Now we'll check for differences in the result
cd ..
diff site2/myfile site3/myfile
If the final diff outputs anything then the workspaces are in
different states after pulling all the patches... and I get output
under Darcs 1.0.9rc1 which is the version installed on one of the
servers here.
Thanks in advance for your thoughts,
Will :-}