[prev in list] [next in list] [prev in thread] [next in thread] 

List:       darcs-conflicts
Subject:    [darcs-conflicts] conflictor-conflictor commutes (Part III)
From:       David Roundy <droundy () abridgegame ! org>
Date:       2005-05-26 12:36:19
Message-ID: 20050526123614.GC26176 () abridgegame ! org
[Download RAW message or body]

One last commute algorithm will complete the survey of the
conflictor-conflictor commutation cases that are currently handled.

(4) conflictor-conflictor commute of type II

This is another conflictor-conflictor commute rule, which in this case can
be derived from the consideration of a somewhat more complicated merge.  In
this case we merge two lengthy sequences of conflicting patches

BsYsZ || XsCsD

where Xs commute with CsD and Bs commute with YsZ, but BsYs all conflict
with CsD (but not with Xs) and XsCs conflict with YsZ (but not with Bs).

In this case

BsYsZ + XsCs => ... [,CsXs;Ys,Z]
XsCsD + BsYs => ... [,BsYs;Cs,D]

Then the question is, what do we get when we merge these two parallel
patches? The answer is pretty simple:

[,CsXs;Ys,Z] + [,BsYs;Cs,D] => [,CsXs;Ys,Z][,BsYsZ;Cs,D]

from which we conclude that

inv([,CsXs;Ys,Z])[,BsYs;Cs,D] <-> [,BsYsZ;Cs,D]inv([,CsXsD;Ys,Z])

One trickiness that I've glossed over is that in my notation here I've
assumed that Bs commutes trivially with YsZ, which won't often be the case.
Also we have to look for the fact that the commutation has this form, which
means recognizing that CsXs starts with Cs and BsYs starts with Ys--or
rather can be reordered to start with Ys..

There are two other situations to deal with, one of which is its own
inverse.  The inverse of the above is

[,BsYsZ;Cs,D]inv([,CsXsD;Ys,Z]) <-> inv([,CsXs;Ys,Z])[,BsYs;Cs,D]

This is similar, in implementation to the above, with the added complexity
that we need to check that BsYsZ can start with YsZ this time.

The juggled commute as usual is perhaps a bit more interesting.  It says
that

[,CsXs;Ys,Z][,BsYsZ;Cs,D] <-> [,BsYs;Cs,D][,CsXsD;Ys,Z]

This again has similar sort of pattern matching to recognize the
relationship between BsYsZ and YsZ and between CsXs and Cs.  This pattern
is clearly its own inverse.


As I'm sure some of you have noticed, all these rules apply only to
restricted cases (in this case the "first" sequence of patches is empty).
My hope is that when I've got an algorithm that works for two full
conflictors:

inv([As,Bs;Cs,D])[Ws,Xs;Ys,Z] <-> ???

Then we can eliminate both conflictor_conflictor_(un)?force and
conflictor_conflictor_(un)?force2, which should be subsumed by that
algorithm.  The tricky question is how one performs such a commute.  If I
could imagine a scenario in which one would *need* to perform such a
commute (as the beginning of this email described a merge scenario where we
need to perform a conflictor_conflictor_force2), I think the rest would be
almost straightforward.

It may be more helpful to work on something other than the merge, and let
the merge come out "for free".  Perhaps if I start by implementing

[As,Bs;Cs,D][Ws,Xs;Ys,Z] <-> ???

it will be easier to see the solution?

Another approach to take would be to look for commutes failed by the unit
test.  The trouble here is that the quickcheck genererators have an
unfortunate tendancy to generate invalid patch sequences (which then quite
rightly fail to commute--it's an impossible situation).  I could focus on
fixing this by generating random pairs of sequential (or equivalently
parallel) patches rather than generating individual random patches and then
as a postprocessing step try to verify that they could be applied in
sequence.  The current method works well for all but the patch types but
conflictors, in which case it fails pretty miserably.  I think I'll start
working along this route, because regardless of how I eventually figure out
the proper conflictor commutations, it'll be nice to have a working test
suite...

My current idea is to generate individual non-conflictor patches as we
currently do, and then check (again, as we currently do) whether they're
parallel.  This gives us a source of parallel (and equivalently sequential)
patches, and we can perhaps define combinators that combine these (by
merging) into potentially more complex parallel or sequential pairs.  It's
just a vague idea at the moment, but I think that by taking a more
"physical" approach to random pair generation we may be able to guarantee
that for every conflictor commutation tested there is a sequence of merges
that could result in that pair of conflictors.
-- 
David Roundy
http://www.darcs.net

_______________________________________________
darcs-conflicts mailing list
darcs-conflicts@darcs.net
http://www.abridgegame.org/cgi-bin/mailman/listinfo/darcs-conflicts
[prev in list] [next in list] [prev in thread] [next in thread]