[darcs-devel] [patch1911] WIP: use Prim patches in rebase toedit

[Ganesh Sittampalam]

Ganesh Sittampalam <ganesh at earth.li> added the comment:

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

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