[darcs-devel] [patch1947] refactor simplifyPush (and 9 more)

Ganesh Sittampalam ganesh at earth.li
Mon Sep 30 08:50:30 UTC 2019


On 29/09/2019 21:48, Ben Franksen wrote:

> Okay, so this is due to the (legacy?) mixing of fixups with suspended
> patches.

Yes.

I think it's a tradeoff whether you express the interleaving of fixups
and suspended patches as a product type - FL (fixups, suspended) - or a
sum type - FL (Either fixup suspended). I think I went back and forth on
it a bit when first writing rebase.

The need to integrate with the rest of darcs using things like Named is
the biggest thing that pushes the balance towards the product type.

> Cancelling inverses is subsumed by canonizeFL because that starts with a
> sortCoalesceFL which, among other things, cancels inverses.

Fair enough. I like having it explicitly as a first step, because it
guarantees that doing an operation and then the exact opposite will
always be a no-op (e.g. pulling then obliterating a patch).

>> I'm not sure this will find everything either. Suppose you have an FL of
>> fixups (x1 :>: x2 :>: xs) and (x1 :> x2) doesn't commute with xs, but
>> canonize (x1 :> x2) does commute with xs and then with the item
>> immediately following the fixups.
> 
> Let us postulate an invariant: every FL of fixups is in canonized form.
> Commuting a fixup fully through a canonized sequence leaves it
> canonized. If that isn't possible we add the fixup at the head and
> re-canonize the full sequence. So the invariant is always maintained.
> 
> Now, the scenario you describe is impossible: first, we never canonize a
> subsequence. And even if we did, that could never make anything commute
> that didn't commute before.

I don't see why canonizing in general can't make things commute.
Consider a fixup that's a large hunk change, and another that's nearly
its inverse apart from a very small difference. Once you canonize the
pair, you just have the very small difference that will commute with a
lot more things.

> My idea was very similar: instead of checking if the canonizeFL has
> changed anything, we reverseFL the complete sequence, then pull off
> elements from the end and try to push them into the next item,
> accumulating an FL of fixups for which this fails and which when we are
> done become the new FL of fixups.
> 
> And now that I think a bit more about it, we can drop the initial
> attempt to commute the fixup past and instead immediately add it to the
> head and then canonize. This means that in this scheme a new fixup is
> first pushed /into/ the FL. Afterwards we /extract/ fixups from it to
> push them through the next item. So this treats an FL of fixups as a
> black box, so ideally we would wrap it in a new type.

I guess that we might assume that canonizing won't prevent commutes that
would otherwise have succeeded, because probably if two prims can be
coalesced then the second would have depended on the first. But it's
hard to be sure without inspecting canonize in detail, and of course
there's no specification for exactly what it does and doesn't do (which
is perhaps inevitable).

Overall, there are two invariants we might be interested in:

1. an FL of fixups before an item is always canonized
2. an item always depends on all the fixups immediately before it (i.e.
after the previous item) - so we can't commute any fixups through the item

If we want to maintain both invariants and we want to avoid having to
iterate, then we need to be sure either that canonizing won't introduce
new commute opportunities, or that commuting won't introduce new
canonizing opportunities.

As above I think that canonizing can introduce new commute
opportunities, so the question is whether commuting can introduce new
canonizing opportunities. I'm not sure. If it doesn't, we could use the
one pass algorithm you suggest.


More information about the darcs-devel mailing list