[darcs-users] How to extend a patch theory to fully commute

[James Cook]

On Thu, 2 Jul 2020 at 18:40, Ben Franksen <ben.franksen at online.de>
wrote:> The final chapter about the effect of extended patches and how
to
> resolve the conflicts they represent could use a bit of elaboration. For
> instance, though you refer to the process, you haven't explained how
> (extended) patches are merged. I think you will need to introduce
> inversion for this. This is probably quite simple but maybe still worth
> writing down explicitly.

I mention at the start "every merge is a clean merge in the new
theory". So the procedure for merging A and B is supposed to be that
you make A;A^;B then commute that to A;B;A^ and drop the A^. You could
similarly merge three changes A B C by permuting A;A^;B;B^;C;C^ to
A;B;C;A^;B^;C^.

But yes, I realized after writing it that I never covered inverting
extended patches.

Thinking about it more, I think I've found some problems. Let's say s
is the starting context of A and B, and A ends with a and B ends with
B. Here are three problems:

(a) I'm not sure inverses exist in general.

(b) Even when A^ and B^ do exist (e.g. if they're primitive patches),
merging A and B in a different order results in different ending
contexts. If you write A;A^;B then commute to A;B', you end up with
the context (a, b, A^;B, {B}, {A^}). If you switch the roles of A and
B, you end up with (b, a, B^;A, {A}, {B^}). It would be better if
those two contexts were the same.

(c) I think Proposition 5 might introduce duplicate primitive patches.
Also, the patch sequence it generates is longer than it needs to be.

I've got an idea for solving all three of those. It involves a
substantial change. I need to think more about it.

I've written about the starting point for that idea in the next two
paragraphs, but you may wish to skip it until I've thought it through
more carefully...

Everywhere one of those sequences (Qi) appears in an address, add a
requirement that (Qi) is a cycle: it starts and ends at the same
context, and for every patch P that appears in (Qi), P^ also appears
in (Qi). I'm pretty sure that if you don't care about addresses being
minimal, you can always extend ("unsimplify"?) an address to satisfy
this property. I would need to adapt the definition of "minimal" to
accommodate the cycle requirement. Also, the definition of
"equivalent" would need to be extended substantially, so that for
example the cycles A^;B;B^;A and B^;A;A^;B would be considered
equivalent.

My intuition is that (a) will somehow be solved by the sequence (Qi)
always having inverses; (b) will be solved because we've expanded the
notion of "equivalent"; and the solution to (c) will have something to
do with rotating the cycle to start and end at the associated
primitive context c.

But I haven't thought it through fully, so what I wrote might turn out
to be nonsense.

> I find the last chapter hard to follow because I don't quite understand
> the motivation. It sounds as if what you are saying here is that we
> cannot merge patches from another repo as long as our repo is
> conflicted. But that cannot be true if all patches can be commuted. Or
> is this about /recording/ new patches in a conflicted repo? Some
> clarification would be helpful.

The issue is recording new patches. I tried to explain that in the
remark: "In other words, the problem here is that after applying a
conflicted patch, e.g. after a conflicted merge, the user would like
to be able to get back to work applying ordinary patches." Maybe I
should change the last three words to "recording new primitive
patches"?

Here's my attempt to work through an example of the problem:

* Suppose primitive patches A^ and B don't commute and we try to merge
A and B. So, we permute AA^B to AB'A^' and then drop A^' from the end.
Let c' be the starting context of A and B (because I called it c' in
Chapter 7).

* The final context of the repo, after AB', is a context outside the
primitive patch theory. This is called c in Chapter 7. If we don't
mark the conflict in some way, then to the user, c looks just like its
associated primitive context, which is c' (i.e. the context before
applying either A or B).

* Now the user wants to continue working, so they create a primitive
patch C which has starting context c'. Assume C doesn't commute with
A^ or B^.

* We need C to have starting context c in order to apply it to the
repo. Naïvely, we might try to commute C to an extended patch C' with
the same name but starting context c.

* However, that new patch C' will not have the expected effect.
Applying C from context c' will just turn our two-way conflict into a
three-way conflict. We end up with the patch sequence AB'C', the
ending context of which is another extended context which is
associated with the original primitive context c'.

* In summary, applying C (as its commuted form C') ended up having no
effect on the repo.

> Also, this paragraph is unsatisfying:
>
> > After some quick thinking, Pseudo managed to find a patch P' which was
> > equivalent in effect to P. However, this turned out not to be a great
> > solution, since although P' had the same effect as P, it had the name of
> > a completely different patch, which was confusing. Moreover, the space
> > required to store P', and computing power needed to commute it, was more
> > than one should rightfully expect from a simple primitive patch.
>
> I think this should either be extended to explain how P' was
> constructed, or it should be left out.

That was speculative. I didn't have a construction in mind. I think I
put it there as an argument why even if you could find an extended
patch with starting context c and the desired effect, it would
probably be a bad idea. I've deleted it.

James