[darcs-devel] Commuting rebase Fixups with Named patches

[Ben Franksen]

Am 21.09.2018 um 08:38 schrieb Ganesh Sittampalam:
> On 20/09/2018 09:44, Ben Franksen wrote:
>> When a patch is suspended it first gets moved from the head inventory to
>> the rebase chain without any changes. When patches are added to or
>> removed from the repo, or modified with amend, or a preceding suspended
>> patch is obliterated, we push the effect of what has been removed as
>> fixup into the rebase chain, and then commute every single prim of it as
>> far to the right as possible.
>>
>> Now, if we do /not/ coalesce or otherwise "edit" the fixups in an ad-hoc
>> manner, but instead restrict ourselves to merely cancel a fixup when we
>> hit its inverse, then I claim that we can cleanly recover any subset of
>> suspended patches with the property that together they can be commuted
>> to the head of the rebase chain with no remaining fixups preceding any
>> of them.
> 
> FWIW, I think coalescing/editing fixups is quite important to a good
> user experience. However this belief is mostly from memory of my
> experiments at the time I was developing rebase, so we'd have to do some
> playing around with a rebase without coalescing to verify it.

Agreed.

>> In other words, the only patches that are in "danger" of loosing their
>> identity on unsuspend are those that have residual fixups immediately
>> preceding them, together with all their reverse dependencies. Even so,
>> it may turn out that we do /not/ have to change their identities after
>> all. For instance, if we obliterate a patch during a rebase and then
>> later (but before finishing the rebase) decide to pull it back, then the
>> new fixups from the pull should exactly cancel out the fixups from the
>> obliterate, allowing more suspended patches to retain their identity.
> 
> I think this is tricky to get right. For example, consider implicit
> dependencies - where patch B depends on patch A because you can't
> commute some primitive A0 in A past a primitive in B. Let's assume the
> other primitives in A do commute past B.
> 
> With rebase, you can suspend B, unrecord A, then record a new patch A'
> that just contains the primitive A0 but none of the other primitives in
> A. The fixups resulting from those other primitives will have freely
> commuted past B in the rebase state, and the A0 fixup will be cancelled
> by the newly recorded A', so it'll seem we can unsuspend B without
> changing its identity. So now we've managed to replace A;B with A';B
> which I don't think we want, at least in the current implementation.

Yes, this is correct. I am now so much used to thinking in terms of the
V3 theory that I was unconsciously assuming prims with identities (where
the newly recorded prim A0' would be different from the original A0 and
thus /not/ cancel with the inverse of A0).

> Rebase does actually store fixups corresponding to the identity of
> patches, as well as the content (see src/Darcs/Patch/Rebase/Name.hs),
> but these are currently used for tracking explicit dependencies in a
> rebase and so the RebaseName for A would commute freely past B in this
> case. If we could figure out a way to stop that, it might help, but I
> can't think of one.
> 
> Perhaps if V3 primitives have to have an identity associated, we can
> guarantee that the identity is tied to the patch that contains them.

That's the idea. It isn't written down in the paper, but Ian's
implementation in camp does exactly that. He uses the term 'SubName' for
the identity of a prim, and it consists of the (meta data) hash of the
containing patch, plus a sequence number.

> Then any operation like unrecord/record/amend-record that changes the
> identity of A would also change the identity of A0,

Exactly.

> preventing the fixup
> cancelling. But this is then a good example of where you really need
> some kind of coalesce at some point, as you really don't want an actual
> conflict on unsuspending B, just to force an identity change to B'.

Yes, sure. When we unsuspend a patch that /does/ have remaining fixups
preceding it, so we finally decide to change its identity, we lump the
fixups together with the prims in the patch, sortCoalesceFL the whole
thing and re-record. But we must then push the difference as new fixups
up the rebase chain, which may force further suspended patches to get
new identities on unsuspend.


In the end it looks like my "improved rebase" is better postponed until
we have V3 patches fully integrated and usable. At this point it may
make sense to start fresh and re-implement a new version of rebase
(perhaps renamed to stash) that works only with V3 patches.

Cheers
Ben