[darcs-devel] patch selection vs. actually modifying the repo

Ben Franksen ben.franksen at online.de
Mon Feb 9 00:34:52 UTC 2015


Let me recap the result of my experimentation with issue 1327:

Given three successive patches A B C, we can attempt to commute them 
pairwise in three steps

    A   B   C
 -> A   C'  B'
 -> C'' A'  B'
 -> C'' B'' A''

If this succeeds, we have (among other changes) commuted the (sub-)sequence 
[A B] to [B'' A'']. But this does *not* necessarily mean it is possible to 
do this in another order. For instance,

    A   B   C
 -> B^  A^  C -- this may fail

This is quite counter-intuitive, considering that X, X', X'', and X^ are all 
"morally the same patch" (for X in A, B, C). The order in which we commute 
them should make no difference.

Fortunately, at least in the case of issue 1327, it seems that the 
succeeding order of commutations is not actually wrong: I can save it to a 
bundle and replay it in an empty repository and the results are what you'd 
expect. I'll be optimistic and hope that this is true for all the corner 
cases, i.e. that the failure is limited to missing an order of commutation 
that rightfully succeeds, rather than allowing an invalid commutation that 
would be impossible to realize in an actual tree.

Still, this failing property currently causes crashes. This is because lots 
of code in Darcs, primarily the code that actually modifies a repository, 
*assumes* that the commutations necessary to perform the desired effect will 
succeed.

Abstracting from issue 1327, what happens is this:

 * Patch selection (interactive or not) chooses certain patches, performing
   the commutations in some clandestine (and rather obscure) order.

 * Repository mutating procedures get the resulting selection as input, then
   go ahead to perform the operation without allowing for them to fail.
   Presumably they do this on the assumption that patch selection has
   already proven that failure is impossible. But as we have seen, this is
   not true: in certain corner cases, success might depend on the order in
   which commutation is performed.

How can we cope with this problem?

We probably all agree that, in the long run, we must fix the patch 
representation and commutation code so that commutation respects 
associativity. However, we currently don't have the manpower with the 
necessary expertise to do this. It may require some amount of non-trivial 
mathematics to work out a solution and prove it correct. And even if and 
when we manage that, we will probably have to change the on-disc format of 
patches, which means yet more effort to achieve a reasonable degree of 
compatibility with existing repo formats.

What can we do in the short run?

We should first stop acting like we had a perfect patch theory (and an 
implementation to match it). We don't. People who have been longer into 
hacking Darcs than me (i.e. most of you who read this) are probably quite 
aware of the problems. But for me it took an effort of will to *really* 
acknowledge this as a fact.

My first idea was to review the existing code base with the goal of removing 
all the (mostly undocumented) assumptions that certain commutations will 
succeed, and fail more gracefully instead. However, the operation will fail 
nevertheless and the user may still wonder why she can select certain 
patches but finally acting on them does not succeed. In a way this is just 
putting plaster on an ugly wart.

I am currently thinking about a slightly more radical approach. The idea is 
simple: we make sure that after patch selection there remains no commutation 
work to be done. The result we get back from patch selection should consist 
of three parts:

(1) the selection (has been moved to the front)
(2) a middle part (modified by commutation with the selection, but otherwise
    in the original order)
(3) an unmodified tail

Whatever happens afterwards should not require any further commutation (and 
thus cannot unexpectedly fail). For instance, for the obliterate command we 
just have to write out part 2 (part 3 remains as is). For unrecord, we do 
the same but without changing the working tree. Similar for amend, where we 
afterwards add the selected patch (after modifying it as desired). Commands 
like push and pull are not directly affected by this, because the repo where 
me make the selection is different from the one we modify afterwards.

Why is this better than just allowing for the realization of a command to 
fail? For two reasons:

(1) If Darcs thinks something is not possible, it may be wrong about that, 
because it did not consider all the possible ways it could have been done. 
But at least you get the message as early as possible, i.e. during the 
selection process instead of afterwards.(*)

(2) It would improve modularity as a by-product, cleaning up some of the 
current spaghetti between Darcs.Repository and Darcs.Patch. I also suspect 
that it will allow me to delete whole swats of no longer needed code.

The whole plan is not more than a rough sketch at the moment. I *think* the 
idea works for all commands but I may very well have overlooked some 
important detail that renders all of it infeasible. If you happen to know of 
any such detail or perhaps only suspect there may be one lurking in some 
specific command, please yell!

Cheers
Ben

(*) Things such as trying to commute pending changes *after* patch 
selection, as this is done momentarily in e.g. obliterate, is a bad user 
experience anyway. Pending changes should be added to the front of the patch 
set before selection. The latter can treat it in the same way as it does 
recorded patches (but, perhaps by default preselected to "No").

PS: In parallel to what I sketched above, I will continue to re-factor code 
that directly accesses the list of DarcsFlags until all of it is 
concentrated inside Darcs.UI.Flags. When this is done, [DarcsFlag] will be 
hidden behind a newtype, opaque to the rest of the code. Fortunately this is 
orthogonal to the question of whether to further pursue the idea of giving 
each command its own configuration record (of which I am still rather 
doubtful).
-- 
"Make it so they have to reboot after every typo." -- Scott Adams



More information about the darcs-devel mailing list