darcs

Patch 1911 WIP: use Prim patches in rebase toedit

Title WIP: use Prim patches in rebase toedit
Superseder Nosy List ganesh
Related Issues
Status in-discussion Assigned To
Milestone

Created on 2019-09-03.16:14:22 by ganesh, last changed 2019-10-04.11:51:37 by bf.

Files
File name Status Uploaded Type Edit Remove
cut-back-some-constraints-in-d_p_r_change.dpatch ganesh, 2019-09-30.14:28:01 application/x-darcs-patch
pEpkey.asc bf, 2019-10-01.11:40:40 application/pgp-keys
pEpkey.asc bf, 2019-10-01.22:12:34 application/pgp-keys
pEpkey.asc bf, 2019-10-02.10:08:52 application/pgp-keys
pEpkey.asc bf, 2019-10-02.22:47:59 application/pgp-keys
pEpkey.asc bf, 2019-10-03.21:03:42 application/pgp-keys
pEpkey.asc bf, 2019-10-03.21:33:53 application/pgp-keys
pEpkey.asc bf, 2019-10-04.11:51:36 application/pgp-keys
patch-preview.txt ganesh, 2019-09-03.16:14:21 text/x-darcs-patch
patch-preview.txt ganesh, 2019-09-04.11:01:16 text/x-darcs-patch
patch-preview.txt ganesh, 2019-09-04.20:24:58 text/x-darcs-patch
patch-preview.txt ganesh, 2019-09-11.12:18:38 text/x-darcs-patch
patch-preview.txt ganesh, 2019-09-14.10:20:46 text/x-darcs-patch
patch-preview.txt ganesh, 2019-09-14.16:18:45 text/x-darcs-patch
patch-preview.txt ganesh, 2019-09-20.23:04:54 text/x-darcs-patch
patch-preview.txt ganesh, 2019-09-21.20:36:00 text/x-darcs-patch
patch-preview.txt ganesh, 2019-09-27.21:36:59 text/x-darcs-patch
patch-preview.txt ganesh, 2019-09-30.14:28:01 text/x-darcs-patch
refactor-simplifypush.dpatch ganesh, 2019-09-27.21:36:59 application/x-darcs-patch
unnamed ganesh, 2019-09-03.16:14:21 text/plain
unnamed ganesh, 2019-09-04.11:01:16 text/plain
unnamed ganesh, 2019-09-04.20:24:58 text/plain
unnamed ganesh, 2019-09-11.12:18:38 text/plain
unnamed ganesh, 2019-09-14.10:20:46 text/plain
unnamed ganesh, 2019-09-14.16:18:45 text/plain
unnamed ganesh, 2019-09-20.23:04:54 text/plain
unnamed ganesh, 2019-09-21.20:36:00 text/plain
unnamed ganesh, 2019-09-27.21:36:59 text/plain
unnamed ganesh, 2019-09-30.14:28:01 text/plain
use-prim-patches-in-rebase-suspended-patches.dpatch ganesh, 2019-09-14.10:20:46 application/x-darcs-patch
wip_-use-prim-patches-in-rebase-suspended-patches.dpatch ganesh, 2019-09-14.16:18:45 application/x-darcs-patch
wip_-use-prim-patches-in-rebase-suspended-patches.dpatch ganesh, 2019-09-20.23:04:54 application/x-darcs-patch
wip_-use-prim-patches-in-rebase-suspended-patches.dpatch ganesh, 2019-09-21.20:36:00 application/x-darcs-patch
wip_-use-prim-patches-in-rebase-toedit.dpatch ganesh, 2019-09-03.16:14:21 application/x-darcs-patch
wip_-use-prim-patches-in-rebase-toedit.dpatch ganesh, 2019-09-04.11:01:16 application/x-darcs-patch
wip_-use-prim-patches-in-rebase-toedit.dpatch ganesh, 2019-09-04.20:24:58 application/x-darcs-patch
wip_-use-prim-patches-in-rebase-toedit.dpatch ganesh, 2019-09-11.12:18:38 application/x-darcs-patch
See mailing list archives for discussion on individual patches.
Messages
msg21343 (view) Author: ganesh Date: 2019-09-03.16:14:21
For discussion for now.

As we discussed in a separate thread, the rebase ToEdit
patch should really use primitive patches rather than
repo patches.

This patch removes one fromAnonymousPrim from the commute
code for RebaseFixup, and also significantly simplifies
those commute methods as they don't need to use effect
and hence return an FL any more.

In exchange we get one extra fromAnonymousPrim in the
Summary instance for RebaseChange, for not particularly
good reasons. But it's in a less critical place in the
code (just for looking at things).

To do is to figure out backwards compatibility. It didn't
break any tests which I guess is because we don't have
any regression repositories saved out, so I should fix that
anyway.

Given that "new-style" rebase hasn't yet been released,
one possible strategy would be to make the change
unconditionally for new-style and then convert when
migrating from old-style rebase. Or we could just
always try to parse a ToEdit patch using a repo patch
first, and use 'effect' if needed.

1 patch for repository darcs-unstable@darcs.net:screened:

patch 7610904aa6588a30d42e43d531162b7843fb0fff
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Tue Sep  3 17:05:38 BST 2019
  * WIP: use Prim patches in rebase toedit
Attachments
msg21359 (view) Author: bf Date: 2019-09-03.19:59:10
I am just looking at the diffs and there is one thing I am wondering
about. Your change leads to ever more uses of (PrimOf p). You say that
rebase internally doesn't use the RepoPatch p anymore, only (PrimOf p).
Wouldn't it be possible then to make the rebase patch types parametric
in the prim patch, rather than the RepoPatch? This would also mean we
don't need UndecidableInstances for the modules under Darcs.Patch.Rebase
and I guess it would clean up type signatures pretty well.
msg21361 (view) Author: ganesh Date: 2019-09-03.20:50:27
> Wouldn't it be possible then to make the rebase patch types parametric
> in the prim patch, rather than the RepoPatch?

Yes, I think it should be. Perhaps as a followup because I think it'd be easier
to understand it each patch in isolation. I'll take a look.
msg21378 (view) Author: ganesh Date: 2019-09-04.11:01:16
Using prim directly looks very doable, though things
get a bit tricky on the boundary. Part of the problem
is that Rebase doesn't have a clean API so calling code
often gets infected by representation changes.

The Summary instance for RebaseChange is a complete pain
and it's doing something really trivial. I think I'll
just rewrite it directly.

3 patches for repository darcs-unstable@darcs.net:screened:

patch 7610904aa6588a30d42e43d531162b7843fb0fff
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Tue Sep  3 17:05:38 BST 2019
  * WIP: use Prim patches in rebase toedit

patch f924c6c6ad237da0b7d55728803310bb5863a98f
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Sep  4 11:38:37 BST 2019
  * WIP: convert most Rebase types to have a prim parameter directly
  
  Types on the "boundary" are tricky. For now Suspended is changed
  but RebaseChanges and RebaseSelect are not. RebaseChanges is
  hardest because of the Summary instance, which intrinsically
  wants to know what the RepoPatch type is so it can build a
  Merge.
  

patch b0d8fbe22e64b65ab5fdd250f95a35f5781af1a3
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Sep  4 11:51:38 BST 2019
  * parameterise RebaseSelect with Prim
Attachments
msg21386 (view) Author: bf Date: 2019-09-04.17:33:17
Would you mind squashing the WIP patches you have sent so far into a
single patch, including the ones you attached to patch1902? And send
further updates to this patch?

I would like to comment on some details of the implementation (which I
know is not yet ready for screened, but anyway). I don't want to get
distracted with intermediate versions that are no longer relevant.
msg21387 (view) Author: ganesh Date: 2019-09-04.17:48:57
> Would you mind squashing the WIP patches you have sent so far into a
> single patch, including the ones you attached to patch1902? And send
> further updates to this patch?
> 
> I would like to comment on some details of the implementation (which I
> know is not yet ready for screened, but anyway). I don't want to get
> distracted with intermediate versions that are no longer relevant.

I might do a bit of squashing before submission but broadly I would
prefer to keep the ones in this patch separate to keep the changes
smaller and logically distinct. If you want to see the whole effect and
comment on it together, would darcs diff --last=3 or similar help?

The patches in patch1902 will definitely get significantly more surgery
as clearly there are intermediate states that are utter nonsense, but at
the moment I'm still feeling my way towards the end state so I'd rather
keep most of it independent, as it often makes it easier to reorganise
for submission later. I don't mind moving them here instead of patch1902
though.
msg21388 (view) Author: bf Date: 2019-09-04.19:06:09
> I might do a bit of squashing before submission but broadly I would
> prefer to keep the ones in this patch separate to keep the changes
> smaller and logically distinct. If you want to see the whole effect and
> comment on it together, would darcs diff --last=3 or similar help?

More like --last=6 IIRC. But it's okay, doing that now...

My first comment is about class Unwind. I think that fullUnwind should
be a method of class Conflict and that a separate class is not needed.
This is clearly about conflicted patches, which class Conflict is for.
As for the instance Unwind (FL p), I don't think this is the right place
to put this. The validity of it relies on this sequence being a part of
a Named patch in a repo (see your proof with the details I added in
msg21382). So this should be restricted to the instance for Named.

I you'd like I could help with trying to get rid of the
coalesce/canonize calls. But I don't want to interfere with ongoing work
of yours, so if you are working on that or plan to I'll leave it alone.

A few more remarks:

It should be possible to get rid of all fromAnonymousPrim calls in the
final version.

(I mentioned this  before, repeat here for reference:) We should define
the result of fullUnwind as a proper data type for. This is an
alternative representation for conflicted patches that doesn't preserve
commutation behavior.

Force-commute should be a primitive operation, defined generically for
any two prim patch sequences, resulting in an unwound (possibly)
conflicted patch as above.
msg21390 (view) Author: ganesh Date: 2019-09-04.20:21:18
> My first comment is about class Unwind. I think that fullUnwind should
> be a method of class Conflict and that a separate class is not needed.
> This is clearly about conflicted patches, which class Conflict is for.

I considered that, but wasn't sure if the set of wanted/implementable
instances would line up. But happily it looks like they will, given your
suggestion:

> As for the instance Unwind (FL p), I don't think this is the right place
> to put this. The validity of it relies on this sequence being a part of
> a Named patch in a repo (see your proof with the details I added in
> msg21382). So this should be restricted to the instance for Named.

Yes, that's a very good idea.

> I you'd like I could help with trying to get rid of the
> coalesce/canonize calls. But I don't want to interfere with ongoing work
> of yours, so if you are working on that or plan to I'll leave it alone.

Go for it. For now I'm going to focus on the rebase code in general.

> A few more remarks:
> 
> It should be possible to get rid of all fromAnonymousPrim calls in the
> final version.

I've already got rid of the ones in Summary RebaseChange (I'll send an
updated bundle soon). The remaining one would be in the force commute
code called by extractRebaseSelect.

> (I mentioned this  before, repeat here for reference:) We should define
> the result of fullUnwind as a proper data type for. This is an
> alternative representation for conflicted patches that doesn't preserve
> commutation behavior.
> 
> Force-commute should be a primitive operation, defined generically for
> any two prim patch sequences, resulting in an unwound (possibly)
> conflicted patch as above.

What exactly are you proposing for force-commute as a primitive
operation? If you're saying we should define a new type to store the
result of the force-commute, then that's exactly what I was proposing in
a slightly confused way in the thread a few days ago, so I'm all for it :-)

If you're also proposing that this type be the result type of
fullUnwind, then I'm not immediately sure if it's exactly the right
thing, as the second send of fixups create some extra noise that may
just get in the way. But maybe it is.
msg21391 (view) Author: ganesh Date: 2019-09-04.20:24:58
Latest version of my refactorings.

Next two things I plan to work on are:
- See if storing Named (fixups;changes) improves the rebase code in general
- Write some backwards-compatibility tests and think about how to support it

6 patches for repository darcs-unstable@darcs.net:screened:

patch 7610904aa6588a30d42e43d531162b7843fb0fff
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Tue Sep  3 17:05:38 BST 2019
  * WIP: use Prim patches in rebase toedit

patch f924c6c6ad237da0b7d55728803310bb5863a98f
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Sep  4 11:38:37 BST 2019
  * WIP: convert most Rebase types to have a prim parameter directly
  
  Types on the "boundary" are tricky. For now Suspended is changed
  but RebaseChanges and RebaseSelect are not. RebaseChanges is
  hardest because of the Summary instance, which intrinsically
  wants to know what the RepoPatch type is so it can build a
  Merge.
  

patch b0d8fbe22e64b65ab5fdd250f95a35f5781af1a3
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Sep  4 11:51:38 BST 2019
  * parameterise RebaseSelect with Prim

patch c84b5c6f565ebf162e899dbe5781759335d75327
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Sep  4 16:00:13 BST 2019
  * rewrite Summary RebaseChange to avoid force-commute

patch 6aa423b7eb6647c10c93d037170ff11330232ef8
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Sep  4 16:59:31 BST 2019
  * parameterise RebaseChange over PrimOf

patch ee77f46fbac56bc7f13293810583c174f49bd2b0
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Sep  4 17:26:43 BST 2019
  * rename D.P.Rebase.Container to D.P.Rebase.Suspended
  
  The module primarily contains the Suspended type and code
  to manipulate it.
Attachments
msg21392 (view) Author: bf Date: 2019-09-04.22:14:01
I just realized that the whole plan has one major flaw. I think it is
this flaw that has initially led me to instinctively reject your idea,
even before I fully understood it.

The problem is that the operations fullUnwind and forceCommute, as well
as the proof that you can commute intermediate fixups out of the
sequence of prims of a Named patch are only sound if the prims involved
have identities. Only with named prims you can safely cancel inverses.
Without them you run into problems as soon as duplicate prims enter the
picture.

Until we have an answer to that it makes no sense to further talk about
details.
msg21400 (view) Author: bf Date: 2019-09-11.10:57:15
Let me come back to the suggestion I made in msg21370:

> 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
I really think this is the correct way to get rid of the hacky
implementation of Unwind for FLs where you squash the intermediate
fixups using canonize/coalesce. This hack is making me quite nervous and
I would hope that with the idea sketched above we could completely avoid it.

I am pretty much interested in getting this re-design of rebase into a
usable shape because of patch1913. If we can find an implementation of
force-commute that directly works on (RebasePatch prim), then patch1913
could easily be completed, allowing us to remove all the bogus Regrem
and Rotcilfnoc pseudo inverses. (BTW, one patch in that bundle already
removes the Rev constructors for RebaseChange and RebaseSelect together
with zillions of error calls.)
msg21401 (view) Author: ganesh Date: 2019-09-11.12:14:46
> Let me come back to the suggestion I made in msg21370:
> 
>> 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
> I really think this is the correct way to get rid of the hacky
> implementation of Unwind for FLs where you squash the intermediate
> fixups using canonize/coalesce. This hack is making me quite nervous and
> I would hope that with the idea sketched above we could completely avoid it.

I've spent some time working on this. In summary, it's probably doable,
but there are some tricky aspects and things to design, including
perhaps the structure of Named itself. Getting rid of Invert for Named
is actually one of the prerequisites so it's great that's getting closer.

I'll send my current draft, but bear in mind it's just a hacky
experiment to see what was possible, not something I am seriously
intending to submit in its current form.

Patch type
----------

The type of the patch parameter to Named would be something like

 FL (PrimFixup prim) :> prim)

It could even be (FL prim :> prim) but then it's not very obvious that
some are fixups and some aren't.

Given that it's in a Named, that then expands to

 FL ((FL (PrimFixup prim) :> prim)

which is a bit annoying but we need some way to express the fact that at
any point there can be zero or more PrimFixups.

Invert
------

Getting rid of inverses is important because it's not easy to invert
that type. The alternative would be to have

 FL (FL (PrimFixup prim) :> prim :> FL (PrimFixup prim))

but as I commented elsewhere in this thread, that makes lots of other
things messy.

Explicit dependencies
---------------------

The trickiest thing is NamedFixups, which ultimately are used to track
lost explicit dependencies.

At present during a rebase, they get just stuck behind a Named if they
conflict with it, i.e. if they result from someone removing a patch that
the Named had an explicit dependency on.

So we end up with something like

 Fixup (NameFixup (AddName n1)) :>: ToEdit (Named n2 [n1] contents)

The AddName fixup is the residue of the original patch named n1 that has
been removed.

If we want to put everything in the contents of the Named, there isn't a
good place to put the fixup any more.

 Named n2 [n1] (AddName n1 ??? contents)

Logically the n1 is in conflict with the [n1] so having it inside the
contents of the Named is confusing when we try to write code that works
on those contents, and also quite dangerous as textually it seems like
it's already "made it past" the [n1].

I can think of a couple of options.

- Give up on even bothering about explicit dependencies inside a rebase.
We could just scan the entire repo for them on unsuspend. We wouldn't be
able to show them as conflicts while a rebase is still in progress
without also doing that scan. (I only thought of this idea while writing
the email. It seems a bit inelegant, but might actually be the best fix.)

- Generalised Named somehow to be also able to track the name fixups.
At a theoretical level my view is that names should have their own
theory; they are things that do have commute rules when we consider
dependencies. Currently those are expressed directly in the commute rule
for Named but it would be more compositional if they went somewhere
separate.

The latter idea is roughly what I experimented with in my draft, but
it's a bit extreme: Named needs a new type parameter for the 'name'
object. In the normal case that name object is (PatchInfo, [PatchInfo])
to express the name+deps - actually named PatchName in my draft. In the
rebase case, the name gets a list of NameFixups to go with it.

But then ideally we want to track the commutes etc of these name objects
with witnesses. That's all fine in itself, but combining those witnesses
with the witnesses for the patch contents gets a bit messy: a name and
contents should generally freely commute, but we need a lot of machinery
or unsafecoerces to make it happen. So the end result has some nice
commute rules for the name objects, but the composite commutes etc for
things like Named get quite cluttered. I experimented with a few ideas
like more structure for witnesses and having the witnesses for names and
contents run in parallel rather than series, but I don't think there's
any very clean solution.


> I am pretty much interested in getting this re-design of rebase into a
> usable shape because of patch1913. If we can find an implementation of
> force-commute that directly works on (RebasePatch prim), then patch1913
> could easily be completed, allowing us to remove all the bogus Regrem
> and Rotcilfnoc pseudo inverses. (BTW, one patch in that bundle already
> removes the Rev constructors for RebaseChange and RebaseSelect together
> with zillions of error calls.)

If the force-commute is the only obstacle, then I think we don't need
the full re-design. If we finish the work on changing to Prims in rebase
(which is mainly about backwards compatibility), then I'd expect we
could first invert the Prims, then construct the repo patch, then merge.
And vice-versa afterwards. In fact, given it's the fixups we invert,
maybe we can already do that even without changing to Prims in rebase.
msg21402 (view) Author: ganesh Date: 2019-09-11.12:18:38
The draft I mentioned in my previous email. Very hacky.
(And with the final patch, doesn't actually build.)

19 patches for repository darcs-unstable@darcs.net:screened:

patch 7610904aa6588a30d42e43d531162b7843fb0fff
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Tue Sep  3 17:05:38 BST 2019
  * WIP: use Prim patches in rebase toedit

patch f924c6c6ad237da0b7d55728803310bb5863a98f
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Sep  4 11:38:37 BST 2019
  * WIP: convert most Rebase types to have a prim parameter directly
  
  Types on the "boundary" are tricky. For now Suspended is changed
  but RebaseChanges and RebaseSelect are not. RebaseChanges is
  hardest because of the Summary instance, which intrinsically
  wants to know what the RepoPatch type is so it can build a
  Merge.
  

patch b0d8fbe22e64b65ab5fdd250f95a35f5781af1a3
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Sep  4 11:51:38 BST 2019
  * parameterise RebaseSelect with Prim

patch c84b5c6f565ebf162e899dbe5781759335d75327
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Sep  4 16:00:13 BST 2019
  * rewrite Summary RebaseChange to avoid force-commute

patch 6aa423b7eb6647c10c93d037170ff11330232ef8
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Sep  4 16:59:31 BST 2019
  * parameterise RebaseChange over PrimOf

patch ee77f46fbac56bc7f13293810583c174f49bd2b0
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Sep  4 17:26:43 BST 2019
  * rename D.P.Rebase.Container to D.P.Rebase.Suspended
  
  The module primarily contains the Suspended type and code
  to manipulate it.
  

patch 7540e3c78fc17ca264db5723c38f2d06862b36be
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Thu Sep  5 07:58:17 BST 2019
  * use a type class to restructure/modularize simplifyPush

patch 9b5023b4fc2d50db97e7b9da6b0ea303bfd2e7f9
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Thu Sep  5 08:54:08 BST 2019
  * wrap up name+dependencies in a single PatchName type

patch 0464d133c26bb0de7e887f767dd8b5d4d0d1fc0c
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Thu Sep  5 10:00:21 BST 2019
  * WIP: tweak types/API of working inside a Named

patch 9257a36eb734e47bd33916cc10ab5b86434a908f
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Thu Sep  5 11:59:24 BST 2019
  * WIP: witnesses for PatchName

patch f9ec7b3779134b48e259eea958719e7954c3b866
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Thu Sep  5 12:07:17 BST 2019
  * generalise Named

patch 05a3bba33f216b40b809ad39a2be393ee816311a
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Thu Sep  5 12:31:59 BST 2019
  * MPTC PushFixup

patch aebee5094ce8294ce2f93ab273ab0bb1c335a43c
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Thu Sep  5 13:05:12 BST 2019
  * refactor RebaseFixup

patch 53e0f90ed0b173c6122d19c25508d17ac6a6345f
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Thu Sep  5 13:11:48 BST 2019
  * extract instances

patch ace292e715600b11ce3c020d17cdb0dee3cb1e2a
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Thu Sep  5 13:18:07 BST 2019
  * generalise instance

patch 6c12af3229a868f95b8234e38aeb13d762f7ca84
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Thu Sep  5 13:28:26 BST 2019
  * get rid of pointless NameFixup wrapper

patch 4a15329a848abbdc1b2e084e0f72cb85406115e5
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Thu Sep  5 13:49:06 BST 2019
  * make pushing a RebaseName into a commute problem

patch 019a31f34b19f98e2bdf8a64ee2a1806ffbcd980
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Thu Sep  5 15:34:18 BST 2019
  * pushing for NamedRebase

patch 907dccda7ab6d9a8aedf6ec2d04afa39a3db62eb
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Wed Sep 11 12:42:03 BST 2019
  * WIP: switching to RebaseNamed
  
  problems:
   lots of TODO
   rebase reify
   Invert instances
   Witnesses unpleasant
Attachments
msg21405 (view) Author: bf Date: 2019-09-11.18:16:06
> Patch type
> ----------
> 
> The type of the patch parameter to Named would be something like
> 
>  FL (PrimFixup prim) :> prim)
> 
> It could even be (FL prim :> prim) but then it's not very obvious that
> some are fixups and some aren't.

(except perhaps if you create a new data type for the whole thing)

> Given that it's in a Named, that then expands to
> 
>  FL ((FL (PrimFixup prim) :> prim)
> 
> which is a bit annoying but we need some way to express the fact that at
> any point there can be zero or more PrimFixups.

See above.

> Explicit dependencies
> ---------------------
> 
> The trickiest thing is NamedFixups, which ultimately are used to track
> lost explicit dependencies.

You are right, name fixups belong to the whole ToEdit thing.

> If we want to put everything in the contents of the Named, there isn't a
> good place to put the fixup any more.

Yes. I wouldn't even try that.

> - Give up on even bothering about explicit dependencies inside a rebase.
> We could just scan the entire repo for them on unsuspend. We wouldn't be
> able to show them as conflicts while a rebase is still in progress
> without also doing that scan. (I only thought of this idea while writing
> the email. It seems a bit inelegant, but might actually be the best fix.)

I would find it sad to loose name fixups. I like them a lot, they are
light-weight and easy to understand. In patch1913 I have further
simplified them by getting rid of the unsused patch type parameter.

> - Generalised Named somehow to be also able to track the name fixups.
> At a theoretical level my view is that names should have their own
> theory; they are things that do have commute rules when we consider
> dependencies. Currently those are expressed directly in the commute rule
> for Named but it would be more compositional if they went somewhere
> separate.

True, but do we have anything resembling a theory that allows us to
"compose" patch theories in this way i.e. something like a "direct
product of patch theories"? I think not! I mentioned it in another
discussion: separating concerns is nice if you know how to compose the
separate things, otherwise I wouldn't bother.

BTW, doesn't the failure of RepoPatchV1/V2 and the success of V3
indicate that combining names and content is /not/ "orthogonal"?

> But then ideally we want to track the commutes etc of these name objects
> with witnesses. That's all fine in itself, but combining those witnesses
> with the witnesses for the patch contents gets a bit messy: a name and
> contents should generally freely commute, but we need a lot of machinery
> or unsafecoerces to make it happen. So the end result has some nice
> commute rules for the name objects, but the composite commutes etc for
> things like Named get quite cluttered. I experimented with a few ideas
> like more structure for witnesses and having the witnesses for names and
> contents run in parallel rather than series, but I don't think there's
> any very clean solution.

I would have thought that, if anything, witnesses for something that
combines two independent theories should be pairs i.e. something like

  Named p (wXCont, wXName) (wYCont, wYName)

etc. No idea if this works out in practice, and anyway see the caveat
above about "orthogonality".

> If the force-commute is the only obstacle, then I think we don't need
> the full re-design. If we finish the work on changing to Prims in rebase
> (which is mainly about backwards compatibility), then I'd expect we
> could first invert the Prims, then construct the repo patch, then merge.
> And vice-versa afterwards. In fact, given it's the fixups we invert,
> maybe we can already do that even without changing to Prims in rebase.

I think this is a very good idea and I will try to get it working
together with your patch1914.

Cheers
Ben
msg21406 (view) Author: ganesh Date: 2019-09-11.18:33:44
>> It could even be (FL prim :> prim) but then it's not very obvious that
>> some are fixups and some aren't.
> 
> (except perhaps if you create a new data type for the whole thing)
> 
>> Given that it's in a Named, that then expands to
>>
>>  FL ((FL (PrimFixup prim) :> prim)
>>
>> which is a bit annoying but we need some way to express the fact that at
>> any point there can be zero or more PrimFixups.
> 
> See above.

I don't think a new datatype can help with the fundamental structure of
the type - some way or another, the end result inside a Named will need
to be isomorphic to FL (FL prim :> prim).

It could also be FL (prim :> FL prim) or FL (FL prim :> FL prim) but I
thought giving the "real" patches the more special place was better.

> I would find it sad to loose name fixups. I like them a lot, they are
> light-weight and easy to understand. In patch1913 I have further
> simplified them by getting rid of the unsused patch type parameter.

FWIW it was deliberately put there, but I agree it doesn't add anything
and should be removed.

> True, but do we have anything resembling a theory that allows us to
> "compose" patch theories in this way i.e. something like a "direct
> product of patch theories"? I think not! I mentioned it in another
> discussion: separating concerns is nice if you know how to compose the
> separate things, otherwise I wouldn't bother.

I haven't really thought it through in detail, but isn't there a fairly
obvious lifting of a patch theory on A and a patch theory on B to one on
AxB? Intuitively it feels like all the axioms would just follow
automatically.

> BTW, doesn't the failure of RepoPatchV1/V2 and the success of V3
> indicate that combining names and content is /not/ "orthogonal"?

True, but from a theoretical perspective the PrimPatchIds are
independent of the enclosing PatchInfo so just form an independent layer
of their own.

> I would have thought that, if anything, witnesses for something that
> combines two independent theories should be pairs i.e. something like
> 
>   Named p (wXCont, wXName) (wYCont, wYName)
> 
> etc. No idea if this works out in practice, and anyway see the caveat
> above about "orthogonality".

That's exactly one of the things I tried. The biggest sticking point is
that classes like Effect that are currently supposed to work on both
Named p and on p but with the tupled witnesses on Named the type of
'effect' would be different.

Then I tried a type function to conditionally project down to wXCont,
and then I couldn't use mapFL_FL any more, and then I gave up. Other
annoying problems were that I had to make lots of things
kind-polymorphic and there are no kind classes to constrain it.

I suppose that we could work around the problem with Effect by splitting
it and a few other classes like it, if we think this route is really
worth pursuing.
msg21407 (view) Author: bf Date: 2019-09-12.13:46:27
>> If the force-commute is the only obstacle, then I think we don't need
>> the full re-design. If we finish the work on changing to Prims in rebase
>> (which is mainly about backwards compatibility), then I'd expect we
>> could first invert the Prims, then construct the repo patch, then merge.
>> And vice-versa afterwards. In fact, given it's the fixups we invert,
>> maybe we can already do that even without changing to Prims in rebase.
> 
> I think this is a very good idea and I will try to get it working
> together with your patch1914.

The good news is that I got this working.

The main problem was to adapt the V3 hack, where we have to insert an
inverse pair so that the conflictor we produce can refer to some
RepoPatchV3 in its past. The solution is create a RepoPatch and an
inverse RepoPatch with separate calls to fromAnonymousPrim. So these
patches aren't be inverses for RepoPatchV3, but the contained prims are:

forceCommutePrim (p :> wq) =
  let rp = fromAnonymousPrim p
      irp = fromAnonymousPrim (invert p)
  in case mergerIdWDD (mergerIdNamed selfMerger) (irp :\/: wq) of
       wq' :/\: irp' ->
         prefixWith (rp :>: irp :>: NilFL) wq' :> invert (effect irp')
  where
    ... as before ...

With this I can replace all (Invert p) constraints with (Invert (PrimOf
p)) and all the rebase tests succeed. I will send patches when I have
cleaned up my history.
msg21408 (view) Author: ganesh Date: 2019-09-12.17:26:18
> The main problem was to adapt the V3 hack, where we have to insert an
> inverse pair so that the conflictor we produce can refer to some
> RepoPatchV3 in its past. The solution is create a RepoPatch and an
> inverse RepoPatch with separate calls to fromAnonymousPrim. So these
> patches aren't be inverses for RepoPatchV3, but the contained prims are:
> 
> forceCommutePrim (p :> wq) =
>   let rp = fromAnonymousPrim p
>       irp = fromAnonymousPrim (invert p)
>   in case mergerIdWDD (mergerIdNamed selfMerger) (irp :\/: wq) of
>        wq' :/\: irp' ->
>          prefixWith (rp :>: irp :>: NilFL) wq' :> invert (effect irp')
>   where
>     ... as before ...
> 
> With this I can replace all (Invert p) constraints with (Invert (PrimOf
> p)) and all the rebase tests succeed. I will send patches when I have
> cleaned up my history.

Great. I think we can get this properly removed before we actually
release, but getting this landed first seems most sensible.

Does a test fail if we don't have the inverse pair? Just to check we'll
know if we remove it without actually fixing the problem.
msg21410 (view) Author: ganesh Date: 2019-09-14.10:20:46
Updated version of migration to Prim, resolving conflicts
with patch1914 (which simplifies this bundle).

I think the backwards compatibility story needs a bit
more investigation. I realised that suspending conflicts
is probably not completely broken (for one thing, I do it
myself sometimes). I'll do some testing to see what does
actually work now and then encode that in tests.

5 patches for repository darcs-unstable@darcs.net:screened:

patch b475daf7b08816e62399c6da81ecb5243d1676c0
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 14 10:58:09 BST 2019
  * Use Prim patches in rebase suspended patches
  
  It doesn't make sense to support conflicted patches
  inside a rebase, as conflicts are more naturally
  expressed inside a rebase with fixups. Attempts to
  suspend conflicted patches don't work well anyway
  (see issue2634).
  
  This change is backwards compatible with the on-disk
  rebase format for unconflicted patches because each
  RepoPatch type just saves unconflicted patches without
  any wrapping.
  

patch 93428bf455c0915f5a4702f621cc53fcb19603db
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 14 11:03:19 BST 2019
  * WIP: convert most Rebase types to have a prim parameter directly
  
  Types on the "boundary" are tricky. For now Suspended is changed
  but RebaseChanges and RebaseSelect are not. RebaseChanges is
  hardest because of the Summary instance, which intrinsically
  wants to know what the RepoPatch type is so it can build a
  Merge.
  

patch 4d7181a06ac474e74362b2a48a506991fa54b4d0
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 14 11:12:38 BST 2019
  * parameterise RebaseSelect with Prim

patch 29440dfe49ca543575acc5af5dd2d5fca8f929b6
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 14 11:13:14 BST 2019
  * parameterise RebaseChange over PrimOf

patch 6ae679a4ef497809978c47ac1673a1a028867410
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 14 11:19:03 BST 2019
  * rename D.P.Rebase.Container to D.P.Rebase.Suspended
  
  The module primarily contains the Suspended type and code
  to manipulate it.
Attachments
msg21413 (view) Author: ganesh Date: 2019-09-14.16:18:45
latest version of the Prim migration for Rebase.

But patch1915 shows that it does actually cause a
regression, without a solution for suspending conflicted
patches into fixups directly.

2 patches for repository darcs-unstable@darcs.net:screened:

patch db927933af5a3755e956fb0b9e8602e57173c5f4
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 14 17:10:30 BST 2019
  * WIP: Use Prim patches in rebase suspended patches
  
  This change is backwards compatible with the on-disk
  rebase format for unconflicted patches because each
  RepoPatch type just saves unconflicted patches without
  any wrapping.
  
  However it breaks the existing cases where suspending
  a conflicted patch does work (as well as reading those
  cases from disk.)

patch e64abfd8f9e33ab9ce8cfb6732289f67c5cfcd6e
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 14 17:11:38 BST 2019
  * WIP: convert Rebase types to have a prim parameter directly
Attachments
msg21429 (view) Author: bf Date: 2019-09-15.17:58:42
>> The main problem was to adapt the V3 hack, where we have to insert an
>> inverse pair so that the conflictor we produce can refer to some
>> RepoPatchV3 in its past. The solution is create a RepoPatch and an
>> inverse RepoPatch with separate calls to fromAnonymousPrim. So these
>> patches aren't be inverses for RepoPatchV3, but the contained prims are:
>>
>> forceCommutePrim (p :> wq) =
>>   let rp = fromAnonymousPrim p
>>       irp = fromAnonymousPrim (invert p)
>>   in case mergerIdWDD (mergerIdNamed selfMerger) (irp :\/: wq) of
>>        wq' :/\: irp' ->
>>          prefixWith (rp :>: irp :>: NilFL) wq' :> invert (effect irp')
>>   where
>>     ... as before ...
>>
>> With this I can replace all (Invert p) constraints with (Invert (PrimOf
>> p)) and all the rebase tests succeed. I will send patches when I have
>> cleaned up my history.
> 
> Great. I think we can get this properly removed before we actually
> release, but getting this landed first seems most sensible.
> 
> Does a test fail if we don't have the inverse pair? Just to check we'll
> know if we remove it without actually fixing the problem.

It's been some time ago since I added the hack, I'll have to check...
yes, there is tests/rebase-apply.sh which for darcs-3 runs into an error
("autsch, hit the bottom", hehe).
msg21431 (view) Author: bf Date: 2019-09-15.23:05:52
>>> It could even be (FL prim :> prim) but then it's not very obvious that
>>> some are fixups and some aren't.
>>
>> (except perhaps if you create a new data type for the whole thing)
>>
>>> Given that it's in a Named, that then expands to
>>>
>>>  FL ((FL (PrimFixup prim) :> prim)
>>>
>>> which is a bit annoying but we need some way to express the fact that at
>>> any point there can be zero or more PrimFixups.
>>
>> See above.
> 
> I don't think a new datatype can help with the fundamental structure of
> the type - some way or another, the end result inside a Named will need
> to be isomorphic to FL (FL prim :> prim).

Of course. I thought you were worried about readability. I think in the
end we need something like

  RebaseContainer prim ~ Suspended prim ~ FL RebaseChange prim
  RebaseChange prim ~ FL RebaseName :> Named (Unwound prim)

where Unwound is a single prim with fixups before and possibly after.
RebaseFixup and RebaseItem no longer make sense.

BTW, forceCommute for prims is not hard to define. I just made up the
following definition (it typechecks but is untested):

data Unwound prim wX wY where
  Unwound :: FL prim wX wA
          -> prim wA wB
          -> FL prim wB wY
          -> Unwound prim wX wY

forceCommute
  :: (Commute prim, Invert prim)
  => (prim :> prim) wX wY -> (Unwound prim :> Unwound prim) wX wY
forceCommute (p :> q) =
  case commute (p :> q) of
    Just (q' :> p') -> Unwound NilFL q' NilFL :> Unwound NilFL p' NilFL
    Nothing ->
      Unwound (singleFL p) q (singleFL (invert q))
      :>
      Unwound (singleFL (invert p)) p (singleFL q)
  where
    singleFL x = x :>: NilFL
msg21435 (view) Author: ganesh Date: 2019-09-16.16:48:28
> I think in the end we need something like
> 
>   RebaseContainer prim ~ Suspended prim ~ FL RebaseChange prim
>   RebaseChange prim ~ FL RebaseName :> Named (Unwound prim)
> 
> where Unwound is a single prim with fixups before and possibly after.
> RebaseFixup and RebaseItem no longer make sense.

That sounds like a good way of avoiding having to push the RebaseName
inside Named. I did keep playing with how to do it and it looks possible
after all, but at the cost of more complexity in the witnesses that
probably isn't justified if there's an alternative. (Though it does
still make the Name commuting logic much more modular.)

I guess that your draft patch merging RebaseSelect and RebaseChange has
found a way of avoiding having to construct Named (RebaseChange p).

In Unwound, I'd still hope we won't need the fixups after, getting rid
of Invert instances will probably make that possible.

> BTW, forceCommute for prims is not hard to define. I just made up the
> following definition (it typechecks but is untested):

Agreed. The tricky bits are not defining forceCommute itself, but
dealing with Unwound elsewhere in the code.
msg21436 (view) Author: bf Date: 2019-09-16.21:24:37
> I guess that your draft patch merging RebaseSelect and RebaseChange has
> found a way of avoiding having to construct Named (RebaseChange p).

Indeed. The trick was to take advantage of the fact that I already
generalized PatchInfoAnd to PatchInfoAndG, which I did so we can use it
with WrappedNamed, too, instead of Named.

So we generalize D.UI.Commands.Log.changelog to take a PatchInfoAndG and
then we can change the type signature for toRebaseChanges to

toRebaseChanges
    :: FL (RebaseItem p) wX wY
    -> FL (PatchInfoAndG ('RepoType 'IsRebase) (RebaseChange p)) wX wY

with a much simplified implementation.

> In Unwound, I'd still hope we won't need the fixups after, getting rid
> of Invert instances will probably make that possible.

After playing a bit with the idea I agree that the fixups after should
not be part of the argument to Named inside a RebaseChange. So I think
we would need a new type for that e.g.

  RebasePatch prim ~= FL prim :> prim
  RebaseChange prim ~= FL RebaseName :> Named (RebasePatch prim)

But I see no way to convert (i.e. fullUnwind) a single Conflictor to a
(RebasePatch prim) without also producing the trailing fixups, because
(1) the types don't match up and (2) we need to add them as additional
fixups to the next converted RepoPatch in the sequence.

It is interesting to note how the trailing fixups make the whole thing
work at all. Consider the 3-way merge with prims p, q, r that all
conflict with each other. The merged sequence looks like

  [p] [p^, {:p}, :q] [, {:p,:q}, :r]

If we fullUnwind the last Conflictor alone, then we get no fixups, so it
looks as if it were unconflicted, which would be bad. But due to the
trailing fixups of the middle conflictor it gets q^ as extra fixup. This
is what I think we get when we fullUnwind the sequence:

  (;p) (p^;q) (q^;r) ; r^

Here I already pushed trailing fixups to the right, and write (fixups;p)
for a prim with fixups; and note that we also get the trailing r^ to add
to whatever comes next.

It is not as easy to calculate with these things as we are used to: we
must always allow for trailing fixups to appear, remember them, and push
them through to what follows. It would be nice if we could abstract that
as a monadic effect, similar to how we use Maybe for the effect of
commute being partial... probably won't work because of the witnesses,
especially the ones we existentially quantify over.

Cheers
Ben
msg21439 (view) Author: ganesh Date: 2019-09-16.22:58:35
> It is interesting to note how the trailing fixups make the whole thing
> work at all.

I think the fact that we always maintain proper contexts (which in turn
implies tracking the trailing fixups) pretty much guarantees this will
always work out. Either the fixups mean we have a conflict, or the
fixups cancel out somehow and we don't have a conflict but the
underlying patch is in the right context. Of course if we just unwind an
existing conflict we don't expect it to suddenly disappear just because
we went through a rebase, but the user might then do other operations
that do remove it.

> It is not as easy to calculate with these things as we are used to: we
> must always allow for trailing fixups to appear, remember them, and push
> them through to what follows. It would be nice if we could abstract that
> as a monadic effect, similar to how we use Maybe for the effect of
> commute being partial... probably won't work because of the witnesses,
> especially the ones we existentially quantify over.

I don't think it's that bad in practice, though I doubt we will be
proving theorems about rebase any time soon.

It's like commuting through a sequence, the witnesses help a lot with
not losing things.

Plus, we already have the code to manage fixups (simplifyPush and
friends). In one of my (many :-)) prototype refactorings I just
introduced a class to generalise the operations. The core type is
something like

simplifyPushOne :: (fixup :> item) wX wY -> (FL item :> FL fixup) wX wY
msg21509 (view) Author: ganesh Date: 2019-09-20.23:04:54
updated version of prim-ifying Rebase

I'll look at introducing RebasePatch prim next.

3 patches for repository darcs-unstable@darcs.net:screened:

patch cf6355b601d19d124dc561103950e47f76094619
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 20 22:48:04 BST 2019
  * WIP: Use Prim patches in rebase suspended patches
  
  This change is backwards compatible with the on-disk
  rebase format for unconflicted patches because each
  RepoPatch type just saves unconflicted patches without
  any wrapping.
  
  However it breaks the existing cases where suspending
  a conflicted patch does work (as well as reading those
  cases from disk.)

patch d57d7d85b5bee97ef768658004965cc70c7e182a
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 20 23:46:47 BST 2019
  * WIP: convert Rebase types to have a prim parameter directly

patch d90bb8378df1fba1a74d29eda558eed1b011554e
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 20 23:49:06 BST 2019
  * improve safety of commuteNamePrim/commutePrimName
Attachments
msg21510 (view) Author: bf Date: 2019-09-21.10:14:44
> But patch1915 shows that it does actually cause a
> regression, without a solution for suspending conflicted
> patches into fixups directly.

You haven't mentioned it expressly but I guess this failure is fully
expected. I spell things out below in order to clarify where we stand,
what the missing pieces are, and what the end goal should be (IMHO).

What you have sent so far (referring to your latest bundle) is replacing
Named p with Named (PrimOf p) everywhere in rebase. In namedToFixups and
doSuspend you now use effect to transform RepoPatches to prims.

This fixes the crashes we see with RepoPatchV3 but of course it can't
give us the expected behavior when Conflictors are suspended: it misses
out on the fact that they are conflicted to begin with. So the next step
would be to introduce some variant of what you called fullUnwind in a
previous discussion/bundle which translates a RepoPatch to a
representation where conflicts are expressed (only) using fixups. In
rebase this will require dealing with fixups nested in between the
individual constituents of a Named patch, as well as separating out the
RebaseName fixups as they belong to the Named patch itself and not its
content.

I believe that the final version should no longer be represented as a
sequence of RebaseItem (i.e. a mixted sequence of RebaseName,
RebaseFixup, or ToEdit). Instead, with a liberal dose of renamings (for
clarity) I think the goal should be

  RebaseContainer prim ~ FL (Suspended prim)
  Suspended prim ~ FL RebaseName :> Named (RebasePatch prim)
  RebasePatch prim ~ FL (Fixup prim) :> prim
  Fixup prim ~ prim

(where ~ means equivalence, not necessarily equality)

fullUnwind (we really should find a better name) should return

  RebasePatch prim :> FL (Fixup prim)

with the trailing fixups returned explicitly because we are going to
push them into the next RebasePatch anyway (or drop them if we are at
the end of the RebaseContainer).

BTW, I think Fixup could be a newtype wrapping a single prim with most
instances derived.

I wouldn't care too much about compatibility of the on-disk
representation, at least not in the initial effort. Just make sure that
we keep enough of the old code that we can upgrade an existing rebase patch.
msg21514 (view) Author: ganesh Date: 2019-09-21.11:03:15
>> But patch1915 shows that it does actually cause a
>> regression, without a solution for suspending conflicted
>> patches into fixups directly.
> 
> You haven't mentioned it expressly but I guess this failure is fully
> expected. 

Right.

>   RebaseContainer prim ~ FL (Suspended prim)
>   Suspended prim ~ FL RebaseName :> Named (RebasePatch prim)
>   RebasePatch prim ~ FL (Fixup prim) :> prim
>   Fixup prim ~ prim
> 
> (where ~ means equivalence, not necessarily equality)
> 
> fullUnwind (we really should find a better name) should return
> 
>   RebasePatch prim :> FL (Fixup prim)

IMO fullUnwind would be independent of rebase and would continue to return

  FL prim :> prim :> FL prim

We can then build on it in the rebase code to get the types you mention.

Apart from that I roughly agree, except perhaps the names, but we can
review that later.

> I wouldn't care too much about compatibility of the on-disk
> representation, at least not in the initial effort. Just make sure that
> we keep enough of the old code that we can upgrade an existing rebase patch.

What I intend to do is produce a draft sequence of patches that gets us
to the rough end-state so we can discuss that, and then go back and
figure out how to keep backwards compatibility. I'm working on that at
the moment.
msg21520 (view) Author: ganesh Date: 2019-09-21.20:36:00
Here's my latest draft. I've got the types we want to end up
with and most of the implementation roughly done - I don't
think finishing it will be too much more effort though it'll
need cleaning up/documenting as well.

The broad outline is

- switch ToEdit to use prim

- use prim as the parameter type for all rebase types

- a bunch of incremental refactorings to modularise the
  functionality of D.P.R.Item.simplifyPush - this is
  one of the core bits of functionality of rebase and is
  currently quite monolothic. I wanted to make sure that
  the core logic is clearly exposed and easy to read, and
  that I can reassemble the pieces differently to
  implement simplifyPush for a different type.

- make the internal patch type of rebase be RebaseChange
  instead of RebaseItem. This goes through surprisingly
  smoothly.

- switch RebaseChange from
    FL (RebaseFixup prim) :> Named prim
  to
    FL RebaseName :> Named (RebasePatch prim)

    RebasePatch = FL prim :> prim - I didn't yet go through
    and wrap the fixups with a new 'Fixup' type. I also
    didn't convert everything yet but most of the tricky
    bits look ok.


TODO:
 - finish off the RebasePatch implementation
 - integrate with fullUnwind
 - backwards compatibility
 - add haddocks etc
 - finalise names, design etc

I plan to leave this for a bit now so we can talk about the design.

In the meanwhile I have a bunch of small unfinished things in the
patch tracker to finalise, and there are also some refactorings/
cleanups in this bundle that could be pulled out independently.

19 patches for repository darcs-unstable@darcs.net:screened:

patch cf6355b601d19d124dc561103950e47f76094619
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 20 22:48:04 BST 2019
  * WIP: Use Prim patches in rebase suspended patches
  
  This change is backwards compatible with the on-disk
  rebase format for unconflicted patches because each
  RepoPatch type just saves unconflicted patches without
  any wrapping.
  
  However it breaks the existing cases where suspending
  a conflicted patch does work (as well as reading those
  cases from disk.)

patch d57d7d85b5bee97ef768658004965cc70c7e182a
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 20 23:46:47 BST 2019
  * WIP: convert Rebase types to have a prim parameter directly

patch e0114d8246103f52e9479d8367d7e1d6898fb55b
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 21 00:29:21 BST 2019
  * add comment about safety of commuteNamePrim/commutePrimName

patch d5cf16c552d2ec5e682db76e163bd1b0c780b15f
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 21 00:35:33 BST 2019
  * get rid of the PrimPatchBase superclass for Summary
  
  It sort of makes sense in theory, especially given that
  the type of conflictedEffect mentions PrimOf, but in
  practice it infects instances in unpleasant ways.

patch 540181afa768399fe24173d2a6ca742b5a36f49e
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 21 00:37:22 BST 2019
  * remove embedded PrimPatch constraint from PrimFixup
  
  I think it dates from a time when the encoding of rebase
  required it to be there, but it's not needed any more and
  we can just put smaller constraints at use sites instead.

patch e7323eb0a0bd9a3881aa7764b3bb5856f1295cbe
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 21 13:48:17 BST 2019
  * WIP: refactor simplifyPush

patch a4cbbd0caffeb7657be0ccde4b90f81c5086aa2c
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 21 13:48:22 BST 2019
  * drop redundant case

patch d04d10030c1c6fa110a6bfdce20cd56d28789bd0
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 21 13:48:26 BST 2019
  * drop error in commuteNameNamed if a deleted name is readded
  
  As in D.P.R.Item.pushFixupItem, this scenario isn't impossible
  so should just be a failed commute rather than an error.
  

patch f699ba0326e63229d2dc987662fc884ba16c58e0
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 21 13:48:29 BST 2019
  * reuse commuteNameNamed to push RebaseName through ToEdit

patch ceb0cb54a3d033d012b06be7bb96fc664a04d443
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 21 13:57:03 BST 2019
  * move logic for pushing name fixups to D.P.R.Name

patch f6b32b1913e37d6f900fcb7e361049235fd19a82
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 21 14:14:17 BST 2019
  * move logic for pushing prim fixups to D.P.R.Fixup

patch 2585a2ecd030cb05a2d67317335d1b07c28cb9f3
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 21 14:50:07 BST 2019
  * reorder cases

patch 5240342a5128433e463470b6b38e38fd0b52a84a
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 21 14:55:42 BST 2019
  * move logic for pushing past fixups into D.P.R.Fixup

patch 91dfc515fdc9a0b1ad29a52daec0b46d87a75d0d
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 21 15:07:41 BST 2019
  * rename D.P.R.Viewing to D.P.R.Change
  
  Now that it contains one major type the name makes more sense, and the
  functionality in this module was never solely about Viewing anyway.

patch 4c6b3dfd1ebf26747e697c78284feef8afccf5dc
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 21 15:59:33 BST 2019
  * use commuteFixupNamed in pushFixupItem

patch 689e6c2f67395aa54d4cd7697ab5fe389e55c7d6
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 21 17:26:34 BST 2019
  * WIP: change internals of Suspended

patch 9597c0237676f9617e217eeaa6d15969008e46eb
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 21 18:01:21 BST 2019
  * simplify rcToPia

patch 83042e6084451fb2f49d3b7d93ef410d8bfa0dad
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 21 19:09:12 BST 2019
  * commuteNamedFixups = commuterIdFL commuteNamedFixup

patch 9277c36f232cd4b8ccd6eb3cbed86e970c4d860a
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 21 20:56:53 BST 2019
  * WIP: RebasePatch
Attachments
msg21528 (view) Author: bf Date: 2019-09-22.09:26:00
Just one side remark for now:

mapMB_MB :: (p wX wY -> q wX wY) -> Maybe2 p wX wY -> Maybe2 q wX wY
mapMB_MB _ Nothing2 = Nothing2
mapMB_MB f (Just2 v) = Just2 (f v)

I guess it's time to finally introduce

class Functor2 f where
  fmap2 :: p wX wY -> q wX wY -> f p wX wY -> f p wX wY

Off the top of my head I can think of instances for at least Maybe2, FL,
RL, Named, PatchInfoAndG; there are probably more.

I may give this one a try.
msg21529 (view) Author: ganesh Date: 2019-09-22.09:51:15
> Just one side remark for now:
> 
> mapMB_MB :: (p wX wY -> q wX wY) -> Maybe2 p wX wY -> Maybe2 q wX wY
> mapMB_MB _ Nothing2 = Nothing2
> mapMB_MB f (Just2 v) = Just2 (f v)
> 
> I guess it's time to finally introduce
> 
> class Functor2 f where
>   fmap2 :: p wX wY -> q wX wY -> f p wX wY -> f p wX wY
> 
> Off the top of my head I can think of instances for at least Maybe2, FL,
> RL, Named, PatchInfoAndG; there are probably more.
> 
> I may give this one a try.

To work for FL+RL, the type would need to be:

(forall wA wB . p wA wB -> q wA wB) -> f p wX wY -> f p wX wY

I think that's fine for mapMB_MB too in practice, but it does show a
problem of working with witnesses - you sometimes end up with subtle
differences in types of things that inhibits polymorphism. I'm not sure
if it would be acceptable for Named and PatchInfoAndG, it depends on how
the existing functions are used.

BTW I am planning on putting Maybe2 in Darcs.Patch.Witnesses somewhere,
either .Ordered or a new Darcs.Patch.Witnesses.Maybe.
msg21540 (view) Author: bf Date: 2019-09-23.10:41:38
>> I guess it's time to finally introduce
>>
>> class Functor2 f where
>>   fmap2 :: p wX wY -> q wX wY -> f p wX wY -> f p wX wY
> 
> To work for FL+RL, the type would need to be:
> 
> (forall wA wB . p wA wB -> q wA wB) -> f p wX wY -> f p wX wY

Yup.

> I think that's fine for mapMB_MB too in practice, but it does show a
> problem of working with witnesses - you sometimes end up with subtle
> differences in types of things that inhibits polymorphism. I'm not sure
> if it would be acceptable for Named and PatchInfoAndG, it depends on how
> the existing functions are used.

It cannot replace fmapFL_Named and fmapFLPIAP since these take functions
that transform an FL and the types are parameteric over the patches
themselves. Otherwise works out nicely. Will send a patch.
msg21646 (view) Author: ganesh Date: 2019-09-27.21:36:59
Building on patch1947, I've extracted the code changes
to move from RebaseItem to RebaseChange inside Suspended
into a patch that also doesn't depend on the change to
prim types.

It still needs some work - in particular I didn't implement
ReadPatch yet, and this is the point where we start
needing backwards compatibility - but it's nearly there.

Once merged it would reduce the leap we need to take to
switch to prims in rebase whilst avoiding regressions.

12 patches for repository darcs-unstable@darcs.net:screened:

patch 393574cfc5cbccd959c0f9a14c2e9d9eed4f0ab9
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 27 20:15:09 BST 2019
  * refactor simplifyPush
  
  This patch introduces a general concept of pushing 'fixups'
  past 'items', and uses it to implement simplifyPush.
  
  This provides a framework for modularizing the logic in
  subsequent patches.

patch fcc84f7dfb92f769a649bfbdd5ba6aba639f4280
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 27 20:19:06 BST 2019
  * drop redundant case in pushFixupItem

patch 17f854155bbacb52bf2ab974e04fcb82a2e56d00
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 27 20:19:28 BST 2019
  * drop error in commuteNameNamed if a deleted name is readded
  
  As in D.P.R.Item.pushFixupItem, this scenario isn't impossible
  so should just be a failed commute rather than an error.
  

patch 287c8c901e9ba38e018dfeef7c79cf2473edd563
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 27 20:21:22 BST 2019
  * reuse commuteNameNamed to push RebaseName through ToEdit
  
  A commute is the natural way of implementing this operation
  and following the previous refactors the logic was identical

patch f7235ff1566651fe2f04dac2a71d103b3edd9435
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 27 20:32:01 BST 2019
  * add Maybe2 type

patch 2283cc4f2f6a131728fbcd0a622a9bc49f7458cd
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 27 20:32:08 BST 2019
  * move logic for pushing name fixups to D.P.R.Name

patch 08e571529264913630083abe368ef355a5d4195b
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 27 20:40:03 BST 2019
  * move logic for pushing prim fixups to D.P.R.Fixup

patch 9f3996fbc438da7df101b85535aa760077fbcab3
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 27 20:41:40 BST 2019
  * reorder cases in pushFixupItem
  
  Just to make it easier to see how connected logic can be
  extracted to a separate function.

patch 3e3ebc087fb95171de2fc1ed7befc0b111135289
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 27 20:50:20 BST 2019
  * move logic for pushing past fixups into D.P.R.Fixup

patch efe5448f9d159779df7ebf47099bcd5cd249d2b5
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 27 21:38:04 BST 2019
  * use commuteFixupNamed in pushFixupItem

patch a1f99e396271c01ca4e862ee4a6215bdee6d4ef7
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 27 21:45:03 BST 2019
  * cut back some constraints in D.P.R.Change

patch f256835edb5d55dc583cc6e19ceb1fc02f826e87
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 27 22:35:31 BST 2019
  * WIP: use RebaseChange inside Suspended
Attachments
msg21654 (view) Author: ganesh Date: 2019-09-30.14:28:01
Here's an updated draft of the rebase refactoring.

The functionality is mostly there in that most rebase
tests pass, including issue2634-rebase-conflicted-patches
for Darcs2 and Darcs3.

There are some expected failures of any tests that rely
on upgrade, and unexpected failures in rebase-skip-conflicts
and in issue2634 for Darcs1.

I haven't actually tried running it at all to see if it
behaves sanely outside the tests :-)

You'll notice I've added a new type SimpleConflict (in
Darcs.Patch.Rebase.Conflict) which is used to communicate
the conflicts in a rebase when unsuspending. I am not yet
very confident about the full implementation details of
that.

The relationship between SimpleConflict and RebasePatch
throws up an interesting point about the relationship between
rebase and conflicts that I hadn't fully grasped before.
When we work with a rebase, we use fixups to keep everything
in a single linear sequence. But conflicts in Darcs are
fundamentally designed to shunt them off to the side, which
means you actually need quite a bit of rearranging when
translating between the two. We see that both in fullUnwind,
and in D.P.R.Conflict.forceCommutePrimSC.

I did wonder about producing something that returns the
same output was standardResolution directly, rather than
going via SimpleConflict, but didn't pursue it. Perhaps it
would simplify things. But given we have a goal of getting
some patch into the repo that will allow "darcs mark-conflicts"
to reproduce the unsuspend conflicts, my feeling was that
it might be going in the wrong direction.

BTW please ignore D.P.R.Conflict.toSimpleConflict, it's
not used.

Still to do:
 - backwards compatibility
 - rework fullUnwind as discussed elsewhere
 - decide on whether we actually need/want RebasePatch
 - add haddocks etc
 - finalise names, design etc. I particularly don't like
   RebasePatch as a name, though I don't have a better one.
 - fix reify, inject (reify isn't completely fixable with
   RebasePatch, it'll only work if all the fixups can go
   to the start)
 - no doubt lots of other things I've forgotten

24 patches for repository darcs-unstable@darcs.net:screened:

patch a1f99e396271c01ca4e862ee4a6215bdee6d4ef7
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 27 21:45:03 BST 2019
  * cut back some constraints in D.P.R.Change

patch f256835edb5d55dc583cc6e19ceb1fc02f826e87
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 27 22:35:31 BST 2019
  * WIP: use RebaseChange inside Suspended

patch 9e561e97b8856a98e30cf9cec0421750f0278efe
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sat Sep 28 09:30:39 BST 2019
  * WIP: change interface to updatePatchHeader

patch 2310d46db25c57f3b8a880b0613ac95ce93ac3eb
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Fri Sep 27 16:40:23 BST 2019
  * WIP: introduce concept of unwinding a conflict
  
  This provides a generic way to get at the underlying
  primitive patch in the conflict.

patch a52c59da4a28f1c7a4c17f7712003d63816985d0
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Sep 29 17:37:34 BST 2019
  * update comment

patch b4294ebbb0feb4e910bad1eaf3c322a99e3ff17b
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Sep 29 22:04:32 BST 2019
  * WIP: use Named prim inside rebase
  
  This change is backwards compatible with the on-disk
  rebase format for unconflicted patches because each
  RepoPatch type just saves unconflicted patches without
  any wrapping.
  
  However it breaks the existing cases where suspending
  a conflicted patch does work (as well as reading those
  cases from disk.)

patch 7de1305aff986302cb8ba233d331a8a1af50022d
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Sep 29 22:12:47 BST 2019
  * WIP: SimpleConflict

patch 3076f0552700406334dfdcd13cee5eb0dea00f51
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Sun Sep 29 22:12:49 BST 2019
  * WIP: extract pushThrough from D.P.R.Viewing

patch a1e94576db54b10e0d953821b5cf6acdc13d826a
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Mon Sep 30 06:24:19 BST 2019
  * WIP: use SimpleConflict to unsuspend

patch a5cd002e2dbb87527ee35ca5ab4c538b98cdb759
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Mon Sep 30 06:30:03 BST 2019
  * reindent

patch 8b15f0129e8f446d95fa8aa6b259e81cb7ddf6d5
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Mon Sep 30 07:10:32 BST 2019
  * read/show for RebaseChange

patch 15726eaabf9c4c79b36acb9567fcd6fcf8f26dc1
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Mon Sep 30 11:01:41 BST 2019
  * move SimpleConflict to Rebase

patch edfc64cdd144b8499647d54f4c2f58ebccf58271
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Mon Sep 30 11:03:26 BST 2019
  * more forceCommutePrimSC etc to Rebase.Conflict

patch c11bd89d0fa3033384e1243a384970b7f53cb7f1
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Mon Sep 30 11:06:36 BST 2019
  * treat forceCommutePrimSC as a PushFixupFn

patch de8283374f70e583e5a077bb456d587bd99b3e54
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Mon Sep 30 11:09:49 BST 2019
  * forceCommute with SimpleConflict can return a Maybe

patch f4caa4251106675da49d7d01f0678d95511e06e3
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Mon Sep 30 11:18:53 BST 2019
  * use PushFixupFn for more forceCommutes

patch 7ceecf65284de90f893651415ffa8684c1482717
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Mon Sep 30 11:27:42 BST 2019
  * move WithDroppedDeps to D.P.R.Name

patch a7b6ea29a37f0609f85e33711f01a7bae7bba981
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Mon Sep 30 11:28:33 BST 2019
  * use noDroppedDeps in extractRebaseChange

patch 30b685b7f3fee2a6a444e83ee9002abc626a4627
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Mon Sep 30 11:29:27 BST 2019
  * rename extract/reifyRebaseChange to be plural

patch d0eb9c02eec658a5ca600f0a12d19934bb74eb69
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Mon Sep 30 11:47:55 BST 2019
  * use pushFixup infrastructure for forceCommutess

patch 70f5d6a7be708ea6d9e9ae7213c0e9ce60b2a85a
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Mon Sep 30 12:39:38 BST 2019
  * drop now-irrelevant comment

patch 087c9b50d0d33190d253b0b112a14bb2f3ded51c
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Mon Sep 30 13:01:39 BST 2019
  * drop unused fromRebaseChange

patch dc0310c573f241231f1abf7d7e24190715d89b25
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Mon Sep 30 14:04:29 BST 2019
  * restructure extractRebaseChanges a bit

patch 772635b734c45f049a0c51b2068cf0e59c4ac435
Author: Ganesh Sittampalam <ganesh@earth.li>
Date:   Mon Sep 30 15:11:29 BST 2019
  * introduce RebasePatch
Attachments
msg21656 (view) Author: bf Date: 2019-10-01.11:40:40
> You'll notice I've added a new type SimpleConflict (in
> Darcs.Patch.Rebase.Conflict) which is used to communicate
> the conflicts in a rebase when unsuspending. I am not yet
> very confident about the full implementation details of
> that.

Conflicted :: FL prim wA wB -> prim wA wC -> SimpleConflict prim wB wA

I was first having trouble getting an intuition about the witnesses
here. But then I got it: this is almost the same as a V1 Merger, except
that a Merger is recursive, whereas your Conflicted contains only prims.

> The relationship between SimpleConflict and RebasePatch
> throws up an interesting point about the relationship between
> rebase and conflicts that I hadn't fully grasped before.
> When we work with a rebase, we use fixups to keep everything
> in a single linear sequence. But conflicts in Darcs are
> fundamentally designed to shunt them off to the side,

Okay... I think I get what you mean here. I would express this
differently, though. This is not a fundamental design issue but rather
one of efficiency. For example, in a V3 Conflictor I am pretty sure we
could, instead of using contexted patches that fork off to the side, use
a linearized version where we flatten each contexted patch followed by
its inverse and include that in the linear sequence (i.e. the effect).
The only question here would be why we can ignore their relative
ordering when linearized in this way. I think the reason for that is
that they must have originated as forking patches: if we start with
a\/b, then a;a^ :> b;b^ should trivially commute.

> which
> means you actually need quite a bit of rearranging when
> translating between the two. We see that both in fullUnwind,
> and in D.P.R.Conflict.forceCommutePrimSC.

The remarks I made above may help to make this transformation a bit clearer.

BTW, forceCommutePrimSC seems to be treating treat the prim (in and out)
as (merely) a fixup, you don't bother to make the RHS conflicted, too.
Perhaps worth a comment.

> I did wonder about producing something that returns the
> same output was standardResolution directly, rather than
> going via SimpleConflict, but didn't pursue it. Perhaps it
> would simplify things. But given we have a goal of getting
> some patch into the repo that will allow "darcs mark-conflicts"
> to reproduce the unsuspend conflicts, my feeling was that
> it might be going in the wrong direction.

I think this goal is unattainable if we go this route i.e. use only
prims in rebase. We cannot construct "real" conflicted patches except by
merging. And the prims you push into rebase have deliberately forgotten
which Named patch they once belonged to (if any), so you cannot know
from which point in the past you need to merge.

> BTW please ignore D.P.R.Conflict.toSimpleConflict, it's
> not used.

If it is not used then how else are SimpleConflicts introduced in the
first place? extractRebaseChanges calls toWddNamed which calls
toSimpleConflict...

On a more general note, I have been wondering if perhaps the whole idea
of building rebase on prims goes in the wrong direction. What if we go
in the opposite direction and try and get rid of fixups? We could
replace them with "real" conflicts, that is, pushing a fixup would be
replaced with merging, together with some notion of forceCommute that
would have to be implemented as a primitive operation in our 3 RepoPatch
types. The obvious problem with this is that sometimes we don't have a
RepoPatch but only prims, e.g. when we amend a patch. I think the
correct solution here would be to push a merge between the old and new
versions of the amended patch.
Attachments
msg21657 (view) Author: ganesh Date: 2019-10-01.19:31:37
> Conflicted :: FL prim wA wB -> prim wA wC -> SimpleConflict prim wB wA
> 
> I was first having trouble getting an intuition about the witnesses
> here. But then I got it: this is almost the same as a V1 Merger, except
> that a Merger is recursive, whereas your Conflicted contains only prims.

It's basically the simplest form of any conflict representation
(V1/V2/V3). They all have a list of patches they undo. Some store that
inverted, i.e. as the undo, and some store that forward.

What this representation lacks is any notion of patches with which we
conflict but don't need to undo, and any context for the underlying patch.

> For example, in a V3 Conflictor I am pretty sure we
> could, instead of using contexted patches that fork off to the side, use
> a linearized version where we flatten each contexted patch followed by
> its inverse and include that in the linear sequence (i.e. the effect).
> The only question here would be why we can ignore their relative
> ordering when linearized in this way. I think the reason for that is
> that they must have originated as forking patches: if we start with
> a\/b, then a;a^ :> b;b^ should trivially commute.

So we'd need a special commute rule for pairs like a;a^?

> BTW, forceCommutePrimSC seems to be treating treat the prim (in and out)
> as (merely) a fixup, you don't bother to make the RHS conflicted, too.
> Perhaps worth a comment.

Yeah. This is consistent with the old code, which was commuting prim :>
Named and would end up taking the effect after the commute to get back
to a prim. Here it's just happening more directly.

The forceCommute name may not be entirely right, given this behaviour -
and also that actually the structure is the same as pushFixup. The only
real difference with pushFixup is that that fixups end up being captured
as conflicts rather than fixups.

>> But given we have a goal of getting
>> some patch into the repo that will allow "darcs mark-conflicts"
>> to reproduce the unsuspend conflicts, my feeling was that
>> it might be going in the wrong direction.
> 
> I think this goal is unattainable if we go this route i.e. use only
> prims in rebase. We cannot construct "real" conflicted patches except by
> merging. And the prims you push into rebase have deliberately forgotten
> which Named patch they once belonged to (if any), so you cannot know
> from which point in the past you need to merge.

I don't think such conflicts would ever refer to the repo's history.
They'd just be there so the user could use mark-conflicts to get the
markup back. When unsuspending, the "toedit" prims would end up in the
Named patch the user had originally suspended, and the "fixup" prims
would end up in some new dummy Named patch.

>> BTW please ignore D.P.R.Conflict.toSimpleConflict, it's
>> not used.
> 
> If it is not used then how else are SimpleConflicts introduced in the
> first place? extractRebaseChanges calls toWddNamed which calls
> toSimpleConflict...

toWddNamed calls a function with a subtly different name and location:
D.P.R.Patch.toSimpleConflicts.

The basic flow is that we do a fullUnwind on suspend, and
toSimpleConflicts/forceCommutePrimSC on unsuspend.

> On a more general note, I have been wondering if perhaps the whole idea
> of building rebase on prims goes in the wrong direction. What if we go
> in the opposite direction and try and get rid of fixups? We could
> replace them with "real" conflicts, that is, pushing a fixup would be
> replaced with merging, together with some notion of forceCommute that
> would have to be implemented as a primitive operation in our 3 RepoPatch
> types. The obvious problem with this is that sometimes we don't have a
> RepoPatch but only prims, e.g. when we amend a patch. 

I think the two big downsides are that real conflicts are much more
complicated than the rebase representation, and that we still (probably)
need some appropriate point to do a canonize. At the very least we need
cancellation of inverses, though perhaps we can already capture that in
merge operations somehow.

On the other hand if we could do it, it might allow us to remove a whole
load of extra infrastructure related to rebase patches.

> I think the
> correct solution here would be to push a merge between the old and new
> versions of the amended patch.

The special treatment that amend gets in rebase is important in practice
- at least, I wrote it after realising that amending otherwise doesn't
work well. You really need to use the actual diff being amended in. The
RebaseName operation rename is also important for updating explicit deps.
msg21658 (view) Author: bf Date: 2019-10-01.22:12:34
>> For example, in a V3 Conflictor I am pretty sure we could, instead
>> of using contexted patches that fork off to the side, use a
>> linearized version where we flatten each contexted patch followed
>> by its inverse and include that in the linear sequence (i.e. the
>> effect). The only question here would be why we can ignore their
>> relative ordering when linearized in this way. I think the reason
>> for that is that they must have originated as forking patches: if
>> we start with a\/b, then a;a^ :> b;b^ should trivially commute.
> 
> So we'd need a special commute rule for pairs like a;a^?

Yes, I think so (and also similarly for FLs and RLs). Note that this is
a theoretical consideration and not meant to be implemented.

>>> But given we have a goal of getting some patch into the repo that
>>> will allow "darcs mark-conflicts" to reproduce the unsuspend
>>> conflicts, my feeling was that it might be going in the wrong
>>> direction.
>> 
>> I think this goal is unattainable if we go this route i.e. use
>> only prims in rebase. We cannot construct "real" conflicted patches
>> except by merging. And the prims you push into rebase have
>> deliberately forgotten which Named patch they once belonged to (if
>> any), so you cannot know from which point in the past you need to
>> merge.
> 
> I don't think such conflicts would ever refer to the repo's history.

Yup.

> They'd just be there so the user could use mark-conflicts to get the 
> markup back.

I'd like to know what "being there" means, more concretely.

> When unsuspending, the "toedit" prims would end up in the Named patch
> the user had originally suspended,

Okay, this works because the "toedit" is not conflicted (even if it was
when it became suspended...

> and the "fixup" prims would end up in some new dummy Named patch.

Where do you store this patch? You cannot possibly plan to mix it with
normal patches... =:-/

>>> BTW please ignore D.P.R.Conflict.toSimpleConflict, it's not
>>> used.
>> 
>> If it is not used then how else are SimpleConflicts introduced in
>> the first place? extractRebaseChanges calls toWddNamed which calls 
>> toSimpleConflict...
> 
> toWddNamed calls a function with a subtly different name and
> location: D.P.R.Patch.toSimpleConflicts.

Okay, missed that one due to the name collision.

>> On a more general note, I have been wondering if perhaps the whole
>> idea of building rebase on prims goes in the wrong direction. What
>> if we go in the opposite direction and try and get rid of fixups?
>> We could replace them with "real" conflicts, that is, pushing a
>> fixup would be replaced with merging, together with some notion of
>> forceCommute that would have to be implemented as a primitive
>> operation in our 3 RepoPatch types. The obvious problem with this
>> is that sometimes we don't have a RepoPatch but only prims, e.g.
>> when we amend a patch.
> 
> I think the two big downsides are that real conflicts are much more 
> complicated than the rebase representation, and that we still
> (probably) need some appropriate point to do a canonize. At the very
> least we need cancellation of inverses, though perhaps we can already
> capture that in merge operations somehow.
> 
> On the other hand if we could do it, it might allow us to remove a
> whole load of extra infrastructure related to rebase patches.

I agree that we will have to canonize at some point. I was thinking that
maybe we could postpone that to the last possible moment, that is, when
we create new (unconflicted) patches on unsuspend.

That still leaves open the question of how to represent/store conflicts
when we unsuspend.

>> I think the correct solution here would be to push a merge between
>> the old and new versions of the amended patch.
> 
> The special treatment that amend gets in rebase is important in
> practice - at least, I wrote it after realising that amending
> otherwise doesn't work well. You really need to use the actual diff
> being amended in. The RebaseName operation rename is also important
> for updating explicit deps.

I agree with all that, but my intuition tells me that we can achieve the
same with merging. I must admit that I haven't thought this through in
detail, yet. Anyway, here is a rough sketch.

Suppose we have suspended patches R that start after A. We amend A to B
and have to adapt the rebase state. So we merge B\/(A;R) and get
A';R'/\_ of which the lhs A';R' is the resulting new rebase state. The
A' retains all the information we need: we could recover the difference
between A and B as prim fixups from it (including rename fixups) if we
want. Indeed this A' /is/ a rebase fixup, just not as a prim, but
instead as a regular Named patch, tagged with a boolean flag to
distinguish it from other suspended patches. Like our current fixups we
won't normally show it to the user. Similarly, a suspended patch that we
rebase obliterate just turns into such a fixup. And a regular patch that
we obliterate gets pushed into rebase as a fixup w/o any further changes.

Okay, so now we unsuspend R (or some part of it) and let us suppose this
depends on the A'. So we use our primitive force-commute on A':>R to
get... what? I don't know yet what the result of a force-commute should
be. Need to think about that. This is the interesting part where all the
rebase magic happens...

One thing that is clear to me now is that we would need a special
implementation of force-commute for Named patches that handles the
explicit dependencies: if we force-commute P:>R, where R has an explicit
dependency on R, we need to represent the loss of that dependency; this
is what we currently do with the WDDNamed wrapper and I guess we'd need
something quite similar here.

Cheers
Ben
Attachments
msg21659 (view) Author: ganesh Date: 2019-10-02.05:35:34
>> So we'd need a special commute rule for pairs like a;a^?
> 
> Yes, I think so (and also similarly for FLs and RLs). Note that this is
> a theoretical consideration and not meant to be implemented.

OK - I guess that encapsulates the theoretical differences between the
two approaches (fork off to the side versus linear sequence).

>> They'd just be there so the user could use mark-conflicts to get the 
>> markup back.
> 
> I'd like to know what "being there" means, more concretely.

(see the below response to "Where do you store this patch")

>> When unsuspending, the "toedit" prims would end up in the Named patch
>> the user had originally suspended,
> 
> Okay, this works because the "toedit" is not conflicted (even if it was
> when it became suspended...

Right - it's fundamental to the current rebase approach that you lose
conflicts with existing patches when you round-trip through rebase.

>> and the "fixup" prims would end up in some new dummy Named patch.
> 
> Where do you store this patch? You cannot possibly plan to mix it with
> normal patches... =:-/

I thought that was exactly what you were suggesting here:

https://lists.osuosl.org/pipermail/darcs-devel/2019-July/019823.html

"Let me introduce a new command which is a mixture of the current reify
and unsuspend commands. It works like reify in that we create an
artificial Named patch for the (residual) fixups."

we then discussed the idea back and forth a bit further at the end of
August/beginning of September in that same thread.

>>> I think the correct solution here would be to push a merge between
>>> the old and new versions of the amended patch.
>>
>> The special treatment that amend gets in rebase is important in
>> practice - at least, I wrote it after realising that amending
>> otherwise doesn't work well. You really need to use the actual diff
>> being amended in. The RebaseName operation rename is also important
>> for updating explicit deps.
> 
> I agree with all that, but my intuition tells me that we can achieve the
> same with merging. I must admit that I haven't thought this through in
> detail, yet. Anyway, here is a rough sketch.
> 
> Suppose we have suspended patches R that start after A. We amend A to B
> and have to adapt the rebase state. So we merge B\/(A;R) and get
> A';R'/\_ of which the lhs A';R' is the resulting new rebase state. The
> A' retains all the information we need: we could recover the difference
> between A and B as prim fixups from it (including rename fixups) if we

Why would A' contain any information about the name of B? I guess that
if as is likely A and B conflicted, then A' might have some V3 prims
from B that could be used to recover the name of B, but that is quite
roundabout.

BTW a good example where you really care about what actually happened in
an amend comes from things like move and replace patches. There's an
example in the 'rebase-move.sh' test:

Add a file A and record a series of patches that touch A, then suspend
all but the one that originally created it. Now rename it to B and
amend-record that original patch. The rename gets coalesced with the add
to get "add B" instead of "add A". If you just diff the old and new
patches, you have "del A; add B" as a fixup which makes a horrible mess
of conflicts. If you remember what the user did, and push it as a fixup
"move A B", as amend does, it commutes beautifully and the rebase state
becomes a sequence of edits to B without any conflicts.

> Okay, so now we unsuspend R (or some part of it) and let us suppose this
> depends on the A'. So we use our primitive force-commute on A':>R to
> get... what? I don't know yet what the result of a force-commute should
> be. Need to think about that. This is the interesting part where all the
> rebase magic happens...

Right, a generalised force-commute is fundamental and would be of more
general interest.

I'm not quite sure how to characterise any rebase magic we have at the
moment. I guess if anything it's the code where we push fixups around,
and then turn fixups back into conflicts.

> One thing that is clear to me now is that we would need a special
> implementation of force-commute for Named patches that handles the
> explicit dependencies: if we force-commute P:>R, where R has an explicit
> dependency on R, we need to represent the loss of that dependency; this
> is what we currently do with the WDDNamed wrapper and I guess we'd need
> something quite similar here.

Yep. This kind of thing is why, at least theoretically, I'd like to
treat names and dependencies as proper patches of their own, so that we
can make this kind of thing just happen automatically by reusing the
infrastructure for prims. But keeping track of it adds a lot of overhead
to the code that's hard to justify.
msg21660 (view) Author: bf Date: 2019-10-02.10:08:52
>>> So we'd need a special commute rule for pairs like a;a^?
>>
>> Yes, I think so (and also similarly for FLs and RLs). Note that this is
>> a theoretical consideration and not meant to be implemented.
> 
> OK - I guess that encapsulates the theoretical differences between the
> two approaches (fork off to the side versus linear sequence).

I think this may be related to the question: why is it sound to cancel
inverses in sequences of fixups or in the context of a patch we forked
off to the side? I have tried on and off to find a simple theoretical
explanation for this but failed so far.

>>> and the "fixup" prims would end up in some new dummy Named patch.
>>
>> Where do you store this patch? You cannot possibly plan to mix it with
>> normal patches... =:-/
> 
> I thought that was exactly what you were suggesting here:
> 
> https://lists.osuosl.org/pipermail/darcs-devel/2019-July/019823.html
What I had in mind was always a /proper/ conflicted patch, not something
like SimpleConflict with possibly unsound commute and merge behavior! I
thought I had made that clear, but apparently I did not.

Either we can create a proper conflicted patch resulting from a regular
merge (or a sound and well-tested version of force-commute) or we have
to store the conflict somewhere else. IMO mixing SimpleConflict with
regular patches is completely out of the question. With RepoPatchV3 we
/finally/ have a sound implementation of conflictors and I am not
willing to jeopardize that just to get a better rebase unsuspend.
Besides, wouldn't that require us to define how a SimpleConflict
commutes and merges with /all three/ RepoPatch types?

However, there may be a solution that avoids this mixing. The idea is
similar to how patch queues work in Mercurial. When we unsuspend a
patch, it will not immediately be converted to a regular patch. Instead
we have a third sequence of patches in between the regular recorded
patches and the suspended patches. These patches are applied to the
working tree and they have their own version of a pristine tree, which
allows us to directly edit them using amend etc. But we maintain a
strict separation from the regular patches. When we are done with
conflict resolution etc, we can convert them to regular patches.

This adds a significant amount of complication to the UI, though. And to
support it requires lots of changes to the Repository layer.

>>>> I think the correct solution here would be to push a merge between
>>>> the old and new versions of the amended patch.
>>>
>>> The special treatment that amend gets in rebase is important in
>>> practice - at least, I wrote it after realising that amending
>>> otherwise doesn't work well. You really need to use the actual diff
>>> being amended in. The RebaseName operation rename is also important
>>> for updating explicit deps.
>>
>> I agree with all that, but my intuition tells me that we can achieve the
>> same with merging. I must admit that I haven't thought this through in
>> detail, yet. Anyway, here is a rough sketch.
>>
>> Suppose we have suspended patches R that start after A. We amend A to B
>> and have to adapt the rebase state. So we merge B\/(A;R) and get
>> A';R'/\_ of which the lhs A';R' is the resulting new rebase state. The
>> A' retains all the information we need: we could recover the difference
>> between A and B as prim fixups from it (including rename fixups) if we
> 
> Why would A' contain any information about the name of B? I guess that
> if as is likely A and B conflicted, then A' might have some V3 prims
> from B that could be used to recover the name of B, but that is quite
> roundabout.

You are right. I wasn't thinking clearly here. RebaseName gives us the
ability to express that the user views A and B as "the same" patch even
though their identities (names) are different. This is a new feature
that cannot be expressed with the existing Named and RepoPatch machinery.

> BTW a good example where you really care about what actually happened in
> an amend comes from things like move and replace patches. There's an
> example in the 'rebase-move.sh' test:
> 
> Add a file A and record a series of patches that touch A, then suspend
> all but the one that originally created it. Now rename it to B and
> amend-record that original patch. The rename gets coalesced with the add
> to get "add B" instead of "add A". If you just diff the old and new
> patches, you have "del A; add B" as a fixup which makes a horrible mess
> of conflicts. If you remember what the user did, and push it as a fixup
> "move A B", as amend does, it commutes beautifully and the rebase state
> becomes a sequence of edits to B without any conflicts.

Right again. I knew all that at some point but forgot the details. Sorry
for needing you to remind me ;-)

So amend needs to be treated specially. We could create a new named
patch that expresses the users intention of how the amended patch is to
be modified (or rather, the inverse of that). And then we push that as a
named fixup into rebase. And we have to somehow capture that a patch and
its amended version are regarded as the same thing, so we need to attach
rename fixups to this thing.

There is one more potential problem with the idea. Prim fixups can be
commuted independently past suspended patches and then dropped or
coalesced with later fixups. But if we keep them together in a Named
patch, we loose that ability, at least we cannot do it eagerly. But
perhaps we don't have to. It may be possible we can be address this by a
suitable implementation of force-commute for Named patches: it could
first try to commute the components of a Named patch one by one using
the regular commute, and only then "forcibly" deal with what remains.
(Whatever that means, I am still pretty unclear about that.)

>> Okay, so now we unsuspend R (or some part of it) and let us suppose this
>> depends on the A'. So we use our primitive force-commute on A':>R to
>> get... what? I don't know yet what the result of a force-commute should
>> be. Need to think about that. This is the interesting part where all the
>> rebase magic happens...
> 
> Right, a generalised force-commute is fundamental and would be of more
> general interest.

I guess the difficulty in defining it lies in the fact that it must be
able to create new identities. None of the code we have in e.g.
RepoPatchV3 does that, yet.

>> One thing that is clear to me now is that we would need a special
>> implementation of force-commute for Named patches that handles the
>> explicit dependencies: if we force-commute P:>R, where R has an explicit
>> dependency on R, we need to represent the loss of that dependency; this
>> is what we currently do with the WDDNamed wrapper and I guess we'd need
>> something quite similar here.
> 
> Yep. This kind of thing is why, at least theoretically, I'd like to
> treat names and dependencies as proper patches of their own, so that we
> can make this kind of thing just happen automatically by reusing the
> infrastructure for prims. But keeping track of it adds a lot of overhead
> to the code that's hard to justify.

I agree, it would ne nice to have this logic factored out. Perhaps some
future Haskell extension will make that more practical.
Attachments
msg21661 (view) Author: ganesh Date: 2019-10-02.12:21:41
> I think this may be related to the question: why is it sound to cancel
> inverses in sequences of fixups or in the context of a patch we forked
> off to the side? I have tried on and off to find a simple theoretical
> explanation for this but failed so far.

My perspective is that we only ever do it in contexts where we don't
rely on the properties of commute/merge, so it's sound for the same
reasons that coalescing is sound in amend/record/pending patch handling:
the theoretical requirements are much lower. But of course it'd be great
if we could deduce a stronger set of properties that still holds even
when we cancel inverses.

> What I had in mind was always a /proper/ conflicted patch, not something
> like SimpleConflict with possibly unsound commute and merge behavior! I
> thought I had made that clear, but apparently I did not.

> Either we can create a proper conflicted patch resulting from a regular
> merge (or a sound and well-tested version of force-commute) or we have
> to store the conflict somewhere else. IMO mixing SimpleConflict with
> regular patches is completely out of the question. With RepoPatchV3 we
> /finally/ have a sound implementation of conflictors and I am not
> willing to jeopardize that just to get a better rebase unsuspend.
> Besides, wouldn't that require us to define how a SimpleConflict
> commutes and merges with /all three/ RepoPatch types?

Sorry, I was unclear here because the discussion arose in the context of
a side comment about returning a resolution directly instead of
SimpleConflict.

If we did create a real patch then certainly it would be a proper
conflicted patch, not a SimpleConflict. It should be trivial to make one
from a SimpleConflict.

> However, there may be a solution that avoids this mixing. The idea is
> similar to how patch queues work in Mercurial. When we unsuspend a
> patch, it will not immediately be converted to a regular patch. Instead
> we have a third sequence of patches in between the regular recorded
> patches and the suspended patches. These patches are applied to the
> working tree and they have their own version of a pristine tree, which
> allows us to directly edit them using amend etc. But we maintain a
> strict separation from the regular patches. When we are done with
> conflict resolution etc, we can convert them to regular patches.

Interesting idea in general. Maybe we could also build more
functionality into rebase to help with these kinds of workflows.

>> BTW a good example where you really care about what actually happened in
>> an amend comes from things like move and replace patches. There's an
>> example in the 'rebase-move.sh' test:
> 
> Right again. I knew all that at some point but forgot the details. Sorry
> for needing you to remind me ;-)

It took me a while to remember this point myself :-)
msg21662 (view) Author: bf Date: 2019-10-02.19:42:12
>> I think this may be related to the question: why is it sound to cancel
>> inverses in sequences of fixups or in the context of a patch we forked
>> off to the side? I have tried on and off to find a simple theoretical
>> explanation for this but failed so far.
> 
> My perspective is that we only ever do it in contexts where we don't
> rely on the properties of commute/merge, so it's sound for the same
> reasons that coalescing is sound in amend/record/pending patch handling:
> the theoretical requirements are much lower.

But why can we get away with it for the contexts in a Contexted patch
for RepoPatchV3?

I think I may have found an answer and it is quite simple: These
contexts should only ever consist of positive prims! Whenever we add a
negative prim to a context, what we really want to do is /remove/ an
existing positive prim from it.

This suggests that we can strengthen the invariants for contexted prims
considerably. Indeed, I have just run the tests with the strengthened
invariant

  forall (Contexted ps p).
    allFL (isPositive .ident) ps
    && isPositive (ident p)

and this succeeeds with large numbers of QC tests (-q=100000).

>> What I had in mind was always a /proper/ conflicted patch, not something
>> like SimpleConflict with possibly unsound commute and merge behavior! I
>> thought I had made that clear, but apparently I did not.
> 
> Sorry, I was unclear here because the discussion arose in the context of
> a side comment about returning a resolution directly instead of
> SimpleConflict.
> 
> If we did create a real patch then certainly it would be a proper
> conflicted patch, not a SimpleConflict.

Ah, I see. Good!

> It should be trivial to make one from a SimpleConflict.

Hm, I did not expect that to be the case, at least not for RepoPatchV3.
But I suppose it is possible, if not exactly trivial, given that we know
we conflict only with precisely one Named patch (the one we just
unsuspended): if we know its PatchInfo we can re-construct the
PrimPatchIds of its content and make the conflicted patch refer to them.
Or perhaps we can even do this using merge?
msg21663 (view) Author: ganesh Date: 2019-10-02.20:32:05
>> It should be trivial to make one from a SimpleConflict.
> 
> Hm, I did not expect that to be the case, at least not for RepoPatchV3.
> But I suppose it is possible, if not exactly trivial, given that we know
> we conflict only with precisely one Named patch (the one we just
> unsuspended): if we know its PatchInfo we can re-construct the
> PrimPatchIds of its content and make the conflicted patch refer to them.
> Or perhaps we can even do this using merge?

Well, we haven't worked out exactly what the patch should be so it does
what we want, so this is a bit hypothetical.

But suppose we just wanted to turn SimpleConflict c p into a Named
RepoPatchV3. We invent a new dummy PatchInfo for the fixups, take the
PatchInfo we already have for the toedit patch, and just call merge
(Named dummyPI [] c :\/: NamedP toeditPI [] p).
msg21664 (view) Author: ganesh Date: 2019-10-02.22:04:54
>>> It should be trivial to make one from a SimpleConflict.
>>
>> Hm, I did not expect that to be the case, at least not for RepoPatchV3.
>> But I suppose it is possible, if not exactly trivial, given that we know
>> we conflict only with precisely one Named patch (the one we just
>> unsuspended): if we know its PatchInfo we can re-construct the
>> PrimPatchIds of its content and make the conflicted patch refer to them.
>> Or perhaps we can even do this using merge?
> 
> Well, we haven't worked out exactly what the patch should be so it does
> what we want, so this is a bit hypothetical.
> 
> But suppose we just wanted to turn SimpleConflict c p into a Named
> RepoPatchV3. We invent a new dummy PatchInfo for the fixups, take the
> PatchInfo we already have for the toedit patch, and just call merge
> (Named dummyPI [] c :\/: NamedP toeditPI [] p).

Hmm, maybe it's not quite that simple given that we would actually have
an FL of SimpleConflicts, potentialy with some Unconflicted and some
Conflicted. We'd need to essentially back out a hypothetical merge that
constructed them, in order to repeat it on a real conflict
representation inside a Named. If we were going to make up a PatchInfo
for the fixups anyway, we might be better off just constructing the
Nameds in extractRebaseChange and merging there, and not using
SimpleConflict after all.

But we still need to work out what the actual patch would be, for this
to be relevant at all.
msg21665 (view) Author: bf Date: 2019-10-02.22:47:59
>>> It should be trivial to make one from a SimpleConflict.
>>
>> Hm, I did not expect that to be the case, at least not for RepoPatchV3.
> 
> But suppose we just wanted to turn SimpleConflict c p into a Named
> RepoPatchV3. We invent a new dummy PatchInfo for the fixups, take the
> PatchInfo we already have for the toedit patch, and just call merge
> (Named dummyPI [] c :\/: NamedP toeditPI [] p).

Uh. Trivial indeed :-)
Attachments
msg21666 (view) Author: ganesh Date: 2019-10-03.07:42:09
As the discussion has tended to go off in (interesting!) tangents, I
want to just summarise what I see as the current state of this bundle.

The two biggest things to do are:

 - Deciding on the backwards compatibility story (being discussed in a
separate thread on darcs-devel) and then implement it. Once we know the
strategy, I can update "* WIP: use RebaseChange inside Suspended" to
include migration. It won't give us the final format, but I think we can
reasonably regard the interim format it will create as something that we
won't need to keep supporting.

 - Finalise fullUnwind so we can decide on RebasePatch. I'm working on
this at the moment, i.e. working on a clean implementation of the
squashing of adjacent unwinds, and doing the testing you suggested.

Apart from any general design discussions, I think we can also usefully
now think about the type names we want to have. With my refactoring as
it stands at the moment, we have:

Suspended - the container patch. Rename to RebaseContainer?
RebaseChange - an individual suspended patch. Rename to Suspended?
RebaseItem - backwards compatibility only
RebasePatch - if we go with it, holds individual suspended prims plus
their fixups
RebaseFixup - if we go with RebasePatch, then this is just used in APIs
and could probably be removed. If we don't go with RebasePatch then it's
part of RebaseChange.
msg21668 (view) Author: bf Date: 2019-10-03.21:03:42
>> suppose we just wanted to turn SimpleConflict c p into a Named
>> RepoPatchV3. We invent a new dummy PatchInfo for the fixups, take the
>> PatchInfo we already have for the toedit patch, and just call merge
>> (Named dummyPI [] c :\/: NamedP toeditPI [] p).
> 
> Hmm, maybe it's not quite that simple given that we would actually have
> an FL of SimpleConflicts, potentialy with some Unconflicted and some
> Conflicted. We'd need to essentially back out a hypothetical merge that
> constructed them, in order to repeat it on a real conflict
> representation inside a Named. If we were going to make up a PatchInfo
> for the fixups anyway, we might be better off just constructing the
> Nameds in extractRebaseChange and merging there, and not using
> SimpleConflict after all.
> 
> But we still need to work out what the actual patch would be, for this
> to be relevant at all.

I thought that was clear: the patch we are unsuspending. Formerly a
RebasePatch prim; now, after the forceCommute of its fixups, a

  WDDNamed prim ~ WithDroppedDeps (Named (SimpleConflict prim))

While I thought about what this means in practice, I noticed that
rebasing patches as prims has one practical disadvantage that is quite
independent of how exactly the unsuspend is done.

In the last line of

forceCommutePrimSC (p :> Unconflicted q) =
  case commute (p :> q) of
    Just (q' :> p') -> Unconflicted q' :> Just2 p'
    Nothing -> Conflicted (invert p :>: NilFL) q :> Just2 q

we duplicate q, so we can push the second q as a fixup into the next
patch. Suppose this q fixup gets stuck on the next RebasePatch. When we
unsuspend this next patch, too, the q fixup will get a new identity. I
think this may result in less than optimal conflict markup when we
unsuspend multiple patches. We should write a test for what we expect
the conflict markup to be when multiple conflicted patches are unsuspended.
Attachments
msg21669 (view) Author: ganesh Date: 2019-10-03.21:32:56
>> But we still need to work out what the actual patch would be, for this
>> to be relevant at all.
> 
> I thought that was clear: the patch we are unsuspending. Formerly a
> RebasePatch prim; now, after the forceCommute of its fixups, a
> 
>   WDDNamed prim ~ WithDroppedDeps (Named (SimpleConflict prim))

I don't think it's that simple (and I didn't think we thought it was
that simple when we last discussed it in the previously mentioned thread).

At the moment when unsuspending fixups :> Named p, we construct
Named (effect p') where merge (inverse fixups :\/ p) = (p' :/\: _), and
put that in the repo.

And then we apply the conflict markup for p' to working.

The problem is how do we get a patch we can use to reproduce that
conflict marking any time the user runs 'mark-conflicts'.

We can't just put Named p' in the repo because that has conflicts with
orphaned prims.

> we duplicate q, so we can push the second q as a fixup into the next
> patch. Suppose this q fixup gets stuck on the next RebasePatch. When we
> unsuspend this next patch, too, the q fixup will get a new identity. I
> think this may result in less than optimal conflict markup when we
> unsuspend multiple patches. We should write a test for what we expect
> the conflict markup to be when multiple conflicted patches are unsuspended.

I was wondering about that too and I agree we need some tests.

My vague intuition was that it's equivalent to the context in a V3
conflictor: if the next patch depends on it then it'll end up as part of
the conflict there and that's the right thing to happen.

Even with the current code using repo patches, I think the result of the
force commute would produce something similar: if you merge (inverse
fixups :\/: q) and get a conflicted result (q' :/\: ifixups'), then q'
will have the effect of inverse (inverse fixups) and ifixups' will have
the effect of inverse q, so when we uninvert the fixups we are pushing
onwards are just q.

But I'm not very confident about any of this. Needs experiments.

Also, using SimpleConflict means we don't get the nice new conflict
resolution algorithm from V3. That may be a significant downside. The
more we discuss it the less convinced I become it's a good solution.
msg21670 (view) Author: bf Date: 2019-10-03.21:33:53
> As the discussion has tended to go off in (interesting!) tangents, I
> want to just summarise what I see as the current state of this bundle.

Let me first remark that I am positively surprised that you got to the
point where the failing-issue2634 no longer fails, in particular it
passes the three-way conflict tests in there, which I must admit I had
doubts a rebase with prim fixups could handle at all. I stand corrected.

> The two biggest things to do are:
> 
>  - Deciding on the backwards compatibility story (being discussed in a
> separate thread on darcs-devel) and then implement it. Once we know the
> strategy, I can update "* WIP: use RebaseChange inside Suspended" to
> include migration. It won't give us the final format, but I think we can
> reasonably regard the interim format it will create as something that we
> won't need to keep supporting.

I haven't yet looked at the individual patches of your bundle, just the
end result. So I cannot usefully comment beyond what I already said
about compatibility.

>  - Finalise fullUnwind so we can decide on RebasePatch. I'm working on
> this at the moment, i.e. working on a clean implementation of the
> squashing of adjacent unwinds, and doing the testing you suggested.

Okay. I wonder... will squashing adjacent unwinds make a lot of
difference to the rebase code?

BTW, your refactors have indeed made that code a lot more modular,
though at the price of making type signatures more complex. The
PushFixupFn abstraction is really quite useful to get a handle on that.

> Apart from any general design discussions, I think we can also usefully
> now think about the type names we want to have. With my refactoring as
> it stands at the moment, we have:
> 
> Suspended - the container patch. Rename to RebaseContainer?
> RebaseChange - an individual suspended patch. Rename to Suspended?
> RebaseItem - backwards compatibility only
> RebasePatch - if we go with it, holds individual suspended prims plus
> their fixups
> RebaseFixup - if we go with RebasePatch, then this is just used in APIs
> and could probably be removed. If we don't go with RebasePatch then it's
> part of RebaseChange.

I think the renames would be a good thing. I like RebasePatch and I
think RebaseFixup is only needed for compatibility (if at all).

Let me finally mention that rebase reify is not yet implemented, it
currently throws an error. Since we found out that reify can be useful
to convert an existing rebase state to normal patches and then back to
another rebase state, I guess it is something we may want to keep after
all, and perhaps turn into an officially supported command.
Attachments
msg21671 (view) Author: ganesh Date: 2019-10-04.05:35:52
> I haven't yet looked at the individual patches of your bundle, just the
> end result. So I cannot usefully comment beyond what I already said
> about compatibility.

That's fine. The conclusion I draw from the last email was that we want
to support the current rebase format too, so I'll work on that too.

>>  - Finalise fullUnwind so we can decide on RebasePatch. I'm working on
>> this at the moment, i.e. working on a clean implementation of the
>> squashing of adjacent unwinds, and doing the testing you suggested.
> 
> Okay. I wonder... will squashing adjacent unwinds make a lot of
> difference to the rebase code?

Yes: it'll mean we don't need RebasePatch, though we could still use it
if we want.

Although RebasePatch is aesthetically appealing in that it moves the
fixups as close as possible to the things blocking them, it does IMO
make the code a bit more complicated.

But more importantly it does mean we can't reliably fix rebase reify.
Since that captures all the fixups in a patch that lives before the
unsuspended patch, it can't be implemented with RebasePatch unless we
can commute all the fixups backwards, outside the RebasePatch.

> Let me finally mention that rebase reify is not yet implemented, it
> currently throws an error. Since we found out that reify can be useful
> to convert an existing rebase state to normal patches and then back to
> another rebase state, I guess it is something we may want to keep after
> all, and perhaps turn into an officially supported command.

Yep, I intend to fix that (albeit only partially if we keep RebasePatch
- it might have to throw an error if we can't commute the fixups
backwards). There are some other things that need fixing/cleaning up
too, like the unexpectedly broken tests.
msg21672 (view) Author: bf Date: 2019-10-04.11:51:36
Okay, all understood now. Thanks. Also for reminding me why rebase reify
is not trivial to do with RebasePatch present. I agree that RebasePatch
is nice, and that it nevertheless makes sense to search for a way to get
rid of it.

However, before you invest too much effort here, I think I have finally
found a clean solution to the force-commute problem, which may mean we
no longer need rebase reify. I'll explain in a separate message.
Attachments
History
Date User Action Args
2019-09-03 16:14:22ganeshcreate
2019-09-03 19:59:10bfsetmessages: + msg21359
2019-09-03 20:50:27ganeshsetmessages: + msg21361
2019-09-03 22:53:08ganeshsetstatus: needs-screening -> in-discussion
2019-09-04 11:01:16ganeshsetfiles: + patch-preview.txt, wip_-use-prim-patches-in-rebase-toedit.dpatch, unnamed
messages: + msg21378
2019-09-04 17:33:17bfsetmessages: + msg21386
2019-09-04 17:48:57ganeshsetmessages: + msg21387
2019-09-04 19:06:09bfsetmessages: + msg21388
2019-09-04 20:21:19ganeshsetmessages: + msg21390
2019-09-04 20:25:00ganeshsetfiles: + patch-preview.txt, wip_-use-prim-patches-in-rebase-toedit.dpatch, unnamed
messages: + msg21391
2019-09-04 22:14:01bfsetmessages: + msg21392
2019-09-11 10:57:16bfsetmessages: + msg21400
2019-09-11 12:14:48ganeshsetmessages: + msg21401
2019-09-11 12:18:39ganeshsetfiles: + patch-preview.txt, wip_-use-prim-patches-in-rebase-toedit.dpatch, unnamed
messages: + msg21402
2019-09-11 18:16:06bfsetmessages: + msg21405
2019-09-11 18:33:45ganeshsetmessages: + msg21406
2019-09-12 13:46:28bfsetmessages: + msg21407
2019-09-12 17:26:18ganeshsetmessages: + msg21408
2019-09-14 10:20:47ganeshsetfiles: + patch-preview.txt, use-prim-patches-in-rebase-suspended-patches.dpatch, unnamed
messages: + msg21410
2019-09-14 16:18:45ganeshsetfiles: + patch-preview.txt, wip_-use-prim-patches-in-rebase-suspended-patches.dpatch, unnamed
messages: + msg21413
2019-09-15 17:58:42bfsetmessages: + msg21429
2019-09-15 23:05:52bfsetmessages: + msg21431
2019-09-16 16:48:28ganeshsetmessages: + msg21435
2019-09-16 21:24:38bfsetmessages: + msg21436
2019-09-16 22:58:35ganeshsetmessages: + msg21439
2019-09-20 23:04:54ganeshsetfiles: + patch-preview.txt, wip_-use-prim-patches-in-rebase-suspended-patches.dpatch, unnamed
messages: + msg21509
2019-09-21 10:14:44bfsetmessages: + msg21510
2019-09-21 11:03:16ganeshsetmessages: + msg21514
2019-09-21 20:36:00ganeshsetfiles: + patch-preview.txt, wip_-use-prim-patches-in-rebase-suspended-patches.dpatch, unnamed
messages: + msg21520
2019-09-22 09:26:01bfsetmessages: + msg21528
2019-09-22 09:51:15ganeshsetmessages: + msg21529
2019-09-23 10:41:39bfsetmessages: + msg21540
2019-09-27 21:36:59ganeshsetfiles: + patch-preview.txt, refactor-simplifypush.dpatch, unnamed
messages: + msg21646
2019-09-30 14:28:02ganeshsetfiles: + patch-preview.txt, cut-back-some-constraints-in-d_p_r_change.dpatch, unnamed
messages: + msg21654
2019-10-01 11:40:41bfsetfiles: + pEpkey.asc
messages: + msg21656
2019-10-01 19:31:38ganeshsetmessages: + msg21657
2019-10-01 22:12:35bfsetfiles: + pEpkey.asc
messages: + msg21658
2019-10-02 05:35:35ganeshsetmessages: + msg21659
2019-10-02 10:08:53bfsetfiles: + pEpkey.asc
messages: + msg21660
2019-10-02 12:21:41ganeshsetmessages: + msg21661
2019-10-02 19:42:12bfsetmessages: + msg21662
2019-10-02 20:32:05ganeshsetmessages: + msg21663
2019-10-02 22:04:54ganeshsetmessages: + msg21664
2019-10-02 22:47:59bfsetfiles: + pEpkey.asc
messages: + msg21665
2019-10-03 07:42:09ganeshsetmessages: + msg21666
2019-10-03 21:03:43bfsetfiles: + pEpkey.asc
messages: + msg21668
2019-10-03 21:32:56ganeshsetmessages: + msg21669
2019-10-03 21:33:53bfsetfiles: + pEpkey.asc
messages: + msg21670
2019-10-04 05:35:53ganeshsetmessages: + msg21671
2019-10-04 11:51:37bfsetfiles: + pEpkey.asc
messages: + msg21672