Hi James
I think I mentioned that inverses in patch theory always confuse me. So
I may be talking nonsense here.
My current thinking is this:
When we add names to primitive patches, we implicitly make the theory
asymmetric in the sense that /new/ patches can enter the scene only as
positive patches: any patch you record starts out as a positive one. The
only way to get a negative patch is to have the VCS implicitly negate a
positive patch to cancel it, which is done (only) when it detects that
the patch conflicts with another (positive) one.
Can we get by without the notion of inversion for named patches?
Perhaps. A conflicted repo could look like a tree, with conflicted
branches hanging off the side:
a--b--c
|\
d e--f
|\
g h--i
Here, only the top sequence a;b;c is actually applied. All other patches
are implicitly "negated" or "cancelled" because they conflict. Any patch
can occur at most once in the tree.
Since c is in the trunk i.e. applied, it must be the case that it either
does not conflict with any of the cancelled branches, or it has been
recorded after the conflict (i.e. as a manual resolution).
We now have to answer the question: how does the picture look if we
commute b;c to c';b' (assuming b;c does indeed commute)? This can only
succeed if we find a way to move the cancelled branches to a new
context, since the context "between b and c" no longer exists in the trunk.
So this can succeed only if c does not conflict with either of its
sibling cancelled branches, that is, if c^ commutes with all sequences
("paths") in the cancelled branches, that is, all elements of {d, e;f,
e;g, e;h;i}. We then get
a--b'-c'
|\
d' e'-f'
|\
g' h'-i'
where we dropped the result of commuting c^ past.
Note that we did employ inversion of the patch c here, but it is now
apparent that it is only needed temporarily to move the conflicted
branches to a new context.
I think this theory is completely equivalent to that of Darcs in the
sense that all operations have the same semantics. However, we can no
longer represent the set of patches in a linear sequence, so this would
have to have quite a different UI.
Whether that helps in your quest for a theory with unrestricted
commutation is hard to say. The side conditions we have to impose on
whether we are allowed to commute b;c to b';c' do have a certain
similarity to how your "re-arrangement" of sequences depends on the context.
Conflictors in Darcs can be seen as "internalizing" the relevant parts
of the above tree structure /into/ the (conflicted) patch
representation. This is the source of their complexity. What we gain
form that is the possibility arrange all patches in a repo in a linear
sequence where commutation is the only allowed (and required) form of
sequence re-arrangement.
It *may* be that the tree representation is more efficient, however, so
I think it might be worth exploring this region of the design space.
Cheers
Ben
_______________________________________________
darcs-users mailing list
darcs-users@osuosl.org
https://lists.osuosl.org/mailman/listinfo/darcs-users
