[prev in list] [next in list] [prev in thread] [next in thread] 

List:       darcs-devel
Subject:    Re: [darcs-devel] conflicted rebase (or rather: rebase with conflicted fixups)
From:       Ben Franksen <ben.franksen () online ! de>
Date:       2020-05-31 18:52:16
Message-ID: rb0ud0$2k9c$2 () ciao ! gmane ! io
[Download RAW message or body]

Am 31.05.20 um 12:36 schrieb Ganesh Sittampalam:
>> The problem here is that the (rmfile ./wibble; addfile ./wibble) pair is
>> stuck on the patch to be edited. In the old rebase these would cancel
>> each other and then we could commute the (move ./wobble ./wibble) past
>> and drop it.
> 
> (I think) we'd never have got the pair because we would have directly
> pushed in the move without the rmfile/addfile.

Yes, of course. (We could imagine slightly different situations where it
would happen in this way, though, e.g. if the rmfile and addfile would
originally have been recorded separately.)

>> I think this can be fixed, though. I currently simply inject all stuck
>> fixups. This is allowed because conflicts can always be commuted into
>> proximity, so we know that the stuck fixups cannot be ones that later
>> items conflict with. But we can do better than just injecting
>> everything: we could first cancel inverses and then try again to commute
>> fixups past. I think this would solve the problem here. I will try to
>> improve the inject procedure to do that.
> 
> If you cancel inverses, aren't you just returning to the old behaviour?

I have thought about this and I don't think so.

With the old behavior inverses cancel immediately when we push them.
This is indeed bad because it could remove a patch that a later
conflicted patch conflicts with.

But with my proposal this would happen only when we unsuspend a patch.
The main difference is that now we do this only with fixups that are
stuck before the toedit that we want to unsuspend. Since they are stuck
we can be sure that no later rebase item conflicts with them, because
conflicting patches can always be brought into proximity. This is also
the reason why it is safe to inject them into the patch that gets
unsuspended (and thereby destroy their identity) as my implementation
currently does (and will continue to do, at least with those fixups that
are still stuck after cancelling inverses).

> If you push in
> 
>   (fixup original patch; fixup (invert (original patch;amendment))

(I think it is the other way around i.e.

  fixup (invert (original patch;amendment)); fixup original patch

)

> Then the copies of original patch will cancel and give us just the
> amendment.

This would be the case if we cancelled them immediately. But we do it
only on unsuspend when we know that they are stuck. That is, we /first/
allow each fixup to commute past.

> Overall I haven't yet got what we gain from having conflicted fixups. I
> understand why conflicted "toedit" patches are worthwhile: we keep
> information about the full conflict structure, which means suspended
> resolution patches remain valid. Do we need conflicted fixups just to
> make sure that V3 conflicts in toedit patches remain valid?

One immediate advantage is that we no longer loose any important
information when we convert a conflicted named patch to fixups. Whereas
converting via its effect is inherently lossy.

Compared with the purely prim based approach, we gain a clear
distinction between dependencies and conflicts. A (stuck) fixup means
something depends on it, independent of whether there are conflicts.

Comparing with the original rebase implementation with prim fixups and
conflicted suspended patches, we saw that this wasn't sound and we got
crashes. I think this is because replacing a named patch with its effect
(which is done when we remove a patch from the repo) is unsound if a
later patch conflicts with that patch. With V3 this is obvious, as it
invalidates the back references, but I believe it also violates implicit
invariants for V1 and V2.

Finally, with conflicted fixups we can avoid force-commute, which is a
rather shady operation. It is true that we can circumvent the obvious
unsoundness of adding an inverted conflictor by immediately converting
it back to its effect, but I am still glad to be rid of force-commute.
This is replaced by merging any new patch we add to the repo with the
rebase state. I think it is quite obvious that this will generate
precisely those conflicts that we should expect to get.

> And might it be enough just to have named prims in fixups?

I tend to think: no. I can't present a definitive counter example at
this point but i think a good starting point to construct one would be
the three-way conflict followed by a resolution. If you suspend them all
and then convert one of the two conflicted patches to named prim fixups
by taking its "named effect", then I think it should be possible to show
that this violates permutivity.

From a more high level perspective, I think that representing
conflicting fixups as conflictors is just good engineering: we already
/have/ a way to represent conflicts, so why not use it?

Cheers
Ben

_______________________________________________
darcs-devel mailing list
darcs-devel@osuosl.org
https://lists.osuosl.org/mailman/listinfo/darcs-devel
[prev in list] [next in list] [prev in thread] [next in thread]