[darcs-users] darcs cannot apply some patch bundles

[Ben Franksen]

Ganesh Sittampalam wrote:
> 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.

Hey Ganesh

thank you very much for the explanation. The problem is a lot clearer to me 
now.

I wonder if this process could be optimized somehow.

What darcs could at least do, I think, is to cache whether two patches 
commute or not. Darcs already has a global cache for patches, why not add a 
global cache for commutability/dependency information?

For instance, every time I try to amend-record a patch from somewhere in the 
past, darcs seems to calculate some patch dependencies, so it can tell me 
whether the amend is possible.

I have often wished for a graphical tool for viewing the dependencies (or 
maybe the opposite i.e. commutability) between patches. Such a tool could 
also contribute to the global cache, speeding up future requests.

Just raw ideas, of course.

Cheers
Ben