[darcs-users] A proposal: patch incoherence

[Juliusz Chroboczek]

Sorry for making once again a proposal that I don't have time to
implement right now.  I'll get back to darcs hacking sometime in
March, but right now it's simply not an option.

I recently claimed[1] that patches are immutable, and I was right.  I
hence concluded that rerecord/amend-record and unrecord are heresy,
and, after thinking about it, I was wrong.

I also suggested that darcs should implement a notion which I called
``patch subsumption''.  Marnix Klooster[2] later clarified that notion
by calling it ``patch conflict''.  As the term ``conflict'' is already
used for merges, I prefer to call it ``patch incoherence''.


1. Definition of incoherence

There are two notions, (direct) incoherence and hereditary incoherence.

Every patch carries a list of patches that it is (directly) incoherent
with.  (Incoherence is antireflexive and symmetric.)

Hereditary incoherence is incoherence up to dependency.  Precisely,
two patches P and Q are hereditarily incoherent if there exist two
patches P' and Q' such that P depends on P', Q depends on Q', and P'
and Q' are (directly) incoherent.


2. Invariant

A darcs repository never contains two patches that are hereditarily
incoherent.

As a repo always contains all the patches that a given patch depends
on, it is enough to make sure that a darcs repository never contains
two patches that are (directly) incoherent.


3. Behaviour of darcs commands

Amend-record should mark the new patch as being incoherent with the
patch that's being amended.  Unrecord should record a new empty patch
that is marked as incoherent with the patch that's being unrecorded.

Apply should by defauilt fail if attempting to incorporate a patch
that would violate incoherence, but perhaps provide an option to
unpull the incoherent patches.  Send should by default ignore patches
that would violate incoherence but print a warning, and provide an
option (for example |--force-incoherent|) to send all missing patches.

Pull/push is send followed with apply, hence four possible behaviours,
only two of which make sense.

There should be a way to record a change and explicitly mark the
resulting patch as being incoherent with some other patch(es).  While
I'm bad at designing user interfaces, I would reckon that the best way
would be to have a |darcs incoherent| command which marks pending as
being incoherent with a given patch; a subsequent record would
actually create an incoherent patch.


4. Applications


4.1 Safe amend-record

Since amend-record marks the new patch as incoherent, pushing a patch
that amends a patch that was already pushed will fail.


4.2 Safe-ish unrecord

Since unrecord creates a new empty patch that conflicts with the patch
being unrecorded, pushing a repository that contains unrecorded
patches that were already pushed will usually fail.

(Unrecord remains partially unsafe, though.)


4.3 Patch refusals

It is often the case that you want to make sure that you won't pull or
push a given patch.  For example, one of my contributors has in his
tree a patch that he wants to keep, but I've refused to include in my
tree.  Whenever he pushes his changes to me, he manually excludes that
patch; if he forgets, I have to exclude it when applying his bundle.

I would like to mark his patch as not belonging in my repository.  For
that, I would need to generate a patch refusal, which can be
implemented as an empty patch that is incoherent with his patch.


4.4 Arch-style merges

Darcs merges are the right thing in many cases.  However, they some-
times are not desirable, either because you want to keep track of the
history of the merge, or because they generate too many conflicts and
hence are unbearably slow.  In that case, you find yourself wishing
that Darcs could implement Arch-style merges.

Arch has three algorithms for performing merges.  However, all three
have the same structure, and only differ in the precise definition of
point (i) below:

 (i)   select the set of patches to merge;
 (ii)  perform a sequence of (two- or three-way) merges on your
       working tree;
 (iii) record the resulting patch.

All of that can be done in darcs (and I have done so repeatedly).
However, since point (iii) generates a patch that subsumes the patches
merged from, it requires patch incoherence in order to be safe.


5. Conclusion

Patch incoherence is a simple, well defined notion that solves a lot
of problems with darcs.  It begs implementing, and I sure hope someone
beats me to it.


[1] http://www.abridgegame.org/pipermail/darcs-users/2004-October/003775.html

[2] http://www.abridgegame.org/pipermail/darcs-users/2004-November/003981.html