[darcs-users] Make darcs force-commute patches from CLI, to learn about darcs?

Ben Franksen ben.franksen at online.de
Mon Jun 29 12:50:56 UTC 2020

Am 29.06.20 um 12:53 schrieb James Cook:
>> Converting existing repos to darcs-3 is unfortunately one of the things
>> we havent't done yet. I have implemented a number of conversion schemes
>> but they all fail in some situations. There are two hard problems to
>> solve here:
>> (1) What to do about so called "Duplicates" in the darcs-2 format. These
>> have no equivalent in the darcs-3 format (in darcs-3 duplicate prim
>> patches conflict).
>> (2) How to ensure separately converted branches of a project remain
>> interoperable. The existing 'convert darcs-2' command gives up on this
>> and simply assigns new identities for all patches. This means you cän
>> convert at most one branch and have to throw away all others. (Or first
>> merge them all into a single repo, but that typically hits the dreaded
>> eponential behavior in the darcs-1 format, so in practice normally
>> doesn't work.) I always found this to be an extremely poor user
>> experience! It is one of the reasons many people never converted their
>> repos to the darcs-2 format.
> As an attempt to solve problem (2) ignoring problem (1), what would
> happen if you used the entire darcs-2 patch theory, including
> conflictors, as the primitive patch theory for darcs-3? The idea being
> that you avoid creating any new darcs-2 conflictors going forward, but
> if you do encounter them, they're just a legacy type of primitive
> patch. Or does the existence of darcs-2 style conflictors make the
> patch theory unsuitable?

That's an interesting idea. Unfortunately yes, the existence of /any/
style of conflictors makes them unsuitable to serve as prim patches. At
least not without making some further assumptions.

The problem is that primitive patches must be invertible. But
conflictors cannot properly be inverted. Darcs used to have inverse
conflictors in the code until a while ago, but they were always
hazardous (some operations would just call error if they get such a
thing as input) and we had to make sure they never ended up being stored
on disk. So eventually we removed them from the code base.

The reason conflictors cannot be inverted is that they contain
"references" to patches coming before them (namely the patches we are in
conflict with). If you invert a sequence of patches that contains
conflictors, then the inverted conflictors refer to patches coming
/after/ them. That in turn invalidates the invariant that it is always
safe to drop patches from the end of a sequence of patches.

But now that I have written all this, perhaps it would be possible to
get by with some sort of purely formal inversion. We already have a
wrapper type to allow such formal inversion of patches that are not
properly invertible. These patches are either "positive" (just a plain
wrapper) or "negative" (formally inverted). They cannot be commuted in
general (since we have no way to commute patches with different
"polarities"). And in darcs-3 we already distinguish between positive
and negative prim patches via their IDs. Perhaps it turns out that we
can avoid doing mixed polarity commutation for prims in the darcs-3
implementation. I will investigate if that is the case. If it is, then
your idea may be workable. In that case it may even make sense to track
polarity in the type system (i.e. via an additional type parameter) to
make sure we don't accidentally mix them inappropriately.

> As an even more desparate attempt to solve (1), what if you said the
> primitive patch theory is a disjoint union of (a) "old-style" darcs-2
> patches and (b) "new-style" darcs-3 primitive patches, and type (a)
> and (b) patches never commute? In practice you'd get awful conflicts
> if you tried to interleave darcs-2 and darcs-3 work, but in theory
> could that conversion be lossless? (Maybe old-style and new-style
> patches could sometimes commute. I'm trying to treat them as black
> boxes, making no assumptions.)

This suffers from the same problem as above (or not, depending on
whether we can get by with "formal" inversion). Apart from that, yes,
this may be a possible way to solve all the conversion problems with one
big stroke.

It had never occurred to me to think of that as a possible solution.
Sometimes it helps to get input from someone who is not as deeply
involved and who can come up with fresh ideas. Many thanks for sharing them!


More information about the darcs-users mailing list