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

Ben Franksen bugs at darcs.net
Wed Sep 4 16:58:43 UTC 2019


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

>> I had to pipe one more 'y' into the suspend commands. Then the test
>> indeed succeeded! Good work so far.
> 
> FWIW they succeed as-is with the more recent change I sent, as it
> doesn't introduce unexpected extra patches.

Confirmed. I removed them.

>> Your unwind doesn't look at the set of conflicts in a conflictor at all.
>> This could turn out to be problematic for more complicated conflicts.
>> For instance, the last conflictor of a three-way conflicted merge has an
>> empty effect.
> 
> I did think about that, but my intuition is that it doesn't actually
> matter.

You are probably right with that.

> The point of the unwind is to preserve the actual underlying
> patch, with proper context so we can slot it into a larger sequence. The
> set of conflicts that currently have no effect is irrelevant to that,
> and only needed for the commute behaviour of the original conflictor.

It is also needed for merging and conflict resolution. But I get the point.

> Once we suspend a patch, we don't care about that commute behaviour;

Yes. And resolution is also done in a different way.

> when we unsuspend we'll have a new unconflicted patch with different
> commute behaviour. (So rebase will continue to be a fundamentally lossy
> operation.)

Yes, this is always understood when we rebase. Or it should be, I
haven't check that the docs (i.e. --help) mention it.

> I could include the set of conflicts with the p;p^ trick (which is
> indeed very useful for thinking about conflicts), but it'd just
> disappear as soon as the fixups were simplified anyway.

Yes, I found that out when I played with this idea. Makes no sense then.

>> I guess in the end you'll have to bite the bullet and more or less
>> reflect the structure of what is in a Named patch a bit more faithfully.
> 
> I did manage to avoid this at least for simple cases in my followup. And
> I have an informal proof that it must be _possible_ to unwind an entire
> Named into a single sequence fixups_before;actuals;fixups_after.
> 
> Consider that the Named was originally recorded in a context where all
> its constituents were unconflicted. To simplify things, consider its
> minimal context where it would also be completely unconflicted. That
> minimal context is a subset of our current repository.
> 
> Define
> 
> context_diff = the patches in the current context (without the Named we
> are suspending) minus the patches in the minimal context
> 
> tosuspend_minimal = the Named we are suspending in its minimal context
> tosuspend = the Named in its current context
> 
> fixups_before = effect(context_diff^)
> actuals = tosuspend_minimal
> fixups_after = tosuspend_minimal^;effect(context_diff);effect(tosuspend)

As you hinted, using the minimal context isn't necessary. Just commute
the Named patch N backwards (pushing dependencies with it) until it
becomes fully unconflicted.

More formally, initially we have C;F;P, where C is some initial context,
F is a sequence (your context_diff, but perhaps shorter), and our patch
P comes last, all consisting of Named patches. We only need to assume
that F;P commutes to P';F' such that P' is unconflicted. We can always
find such a split point for any Named patch P in any repo.

So we have

  C;F;P = C;P';F'

We then construct

  C;F :> e(F^) :> e(P') :> e(P'^);e(F);e(P)

where e is short for effect. 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.

If P' consists of a single prim, then it is easy to see that this is the
case: When we commute everything we can from e(F^) past e(P'), then we
should get exactly the minimal context (in terms of prims) for P' i.e.
exactly the (already minimized) context from the contexted patch in the
single conflictor inside P. That whatever from e(F^) we commute past P'
cancels against e(F) is obvious if we realize that if something commutes
past P', then it also commutes afterwards past P'^. (I am referring to
the implementation of unwind for RepoPatchV3.)

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.

Q.E.D.

> In practice many of the fixups would be unnecessary so the unwound
> sequence could be much smaller. But the difficulty is finding an
> algorithm that can produce it without traversing the whole repository
> history, and being confident it is reliable.

See above.

> 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.

> I would
> like it to work just by cancelling inverses and commuting, in a way that
> isn't dependent on the particular order we do it.

Definitely.

>> That is, ToEdit will have to consist of a PatchInfo plus explicit
>> dependencies, plus a /sequence/ of (fixup;patch), not just a single one.
> 
>> This could be done by embedding a Named (RebasePatch prim), where
>> (RebasePatch prim) lives at the same level as (RepoPatchVx prim) and
>> consists of (fixups;prim) or perhaps even (fixups;prim;fixups). The
>> latter would be particularly elegant, as unwind would then become a
>> patch converter:
>>
>>   unwind : p wX wY -> RebasePatch (PrimOf p) wX wY
> 
> Hmm, yes, that is a good alternative strategy.

Given the above proof with the added details, we would be fine either way.

>> I think this would also free you from having to create random junk on
>> the fly.
> 
> I think doing that is completely unviable, I just did it initially to
> see if I could get something halfway working. It's gone now and is
> staying gone :-)

Good!

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


More information about the darcs-devel mailing list