[darcs-users] darcs cannot apply some patch bundles

[Ganesh Sittampalam]

On 05/03/2012 17:05, Owen Stephens wrote:
> On 5 March 2012 16:18, Michael Hendricks <michael at ndrix.org
> <mailto:michael at ndrix.org>> wrote:
>>Since I'm not yet familiar with Darcs' internal workings, can someone
>>help me understand why calculating a minimal context is so expensive?
> 
> Because you need to do a whole bunch of commutes - working out which of
> *all*
> the patches in the repository cleanly commute past a given patch.
> 
>>Is it because Darcs doesn't have quick access to patch summaries and
>>must load every patch, in its entirety, from disk to perform a
>>commutation?
> 
> Yeah, I think that's pretty much it.

It's also that, whether or not you have the patch data, the naive
algorithm is O(n^2) to commute the minimal context of a single patch,
and I don't know a more sophisticated one (though I have some vague ideas).

Consider a repo ABCDEF, and you want to calculate the minimal context of
F. First you commute F past E, and that succeeds so you can drop E. I'm
ignoring the fact that the representation changes as you do it:

ABCDF

Now you try D. That fails. Now you need to try C. But to try C, you
first have to commute it past D. So now what we really have is a list of
patches we need to try to commute everything else past:

ABC|DF

In general the lists on the left-hand side and right-hand side of the |
may be O(n), so each operation to reduce the list on the left by 1 is
O(n) and the whole job is O(n^2).

In practice it may be that the list on the right doesn't grow too much,
but I actually tried this on the darcs repo itself a while back and it
did seem to be quite slow in practice.

Ganesh