[darcs-devel] [patch1902] add failing test for rebase of conflicted patches

Ben Franksen bugs at darcs.net
Wed Sep 4 23:10:07 UTC 2019


Ben Franksen <ben.franksen at online.de> added the comment:

>> What remains to show is that this is
>> actually equivalent to your optimized implementation. What means
>> "equivalent"? I think we agree that here it can only mean equal up to
>> commutation and cancellation of inverses.
> 
> FWIW I don't have an optimized implementation yet, just some quick
> hacks. What I've done needs to at least be changed to find all pairs of
> inverses in the adjacent fixups.

I meant the unwind implementation for RepoPatchVx. Which, at least for
V3, takes the prim and its context directly from each single conflictor.
This is "optimized" relative to the "safe" version that commutes the
Named patch back until it becomes unconflicted and then constructs
common fixups for the full sequence of prims inside it, before and
after. Which may involve a lot more prims as you noted.

>> What about the general case where P and thus P' may consist of several
>> patches? I think this is a simple consequence of permutivity: in P' =
>> p1';...;pn' the pi' are adjacent, so for the corresponding
>> P=f1;p1;g1;...;fn;pn;gn (with gi the fixups after pi), it must be
>> possible to find a commutation where the p1;...;pn are also adjacent.
> 
> I don't think permutivity applies here. The sequence f1;p1;g1;... was
> never reached by commuting p1';...;pn' (at least not at the Prim level).
> Just because p;q are adjacent, doesn't mean you can commute p;r;r^;q to
> get p;q if r is something that has a dependency (e.g. if it just deletes
> the whole repo).

You are right. We need a further theorem (or axiom), one that tells us
that cancelling inverses is valid. In other words, we regard patch
sequences as equal if they differ only by adding or removing inverse
pairs. This is really the approach I took when I wrote Theory.hs, where
I postulated that patch sequences form a groupoid. In practice we can
guarantee this only if we assume that prim patches come with a (signed)
identity.

>>> So far what I have is in the Unwind instance for FL, but it's pretty
>>> hacky and I really don't want it to depend on coalesce/canonize;
>>
>> No it should definitely not. I think a good point of reference is the
>> code for commutePast in Dracs.Patch.V3.Contexted.
> 
> Did you mean ctxAdd? commutePast on its own doesn't cancel inverses.

You are right, I meant ctxAdd. The difference between commutePast and
ctxAdd has always confused me because I really don't understand why we
sometimes have to use one and sometimes the other.

__________________________________
Darcs bug tracker <bugs at darcs.net>
<http://bugs.darcs.net/patch1902>
__________________________________


More information about the darcs-devel mailing list