[darcs-users] darcs conflicts/dependencies -- is patch theory the place to start?

[Florent Becker]

Le 18/09/2012 13:26, Miles Gould a écrit :
> On 18/09/12 12:09, Miles Gould wrote:
>>  I *think* this means that the merge algorithm is
>> constant-time in the depth of patches that need merging.
> 
> A minute's extra thought convinces me that I was wrong about that.
> Suppose we have
> 
> a-b-c-d-e-f-g
>      \
>       h-i-j-k-l-m
> 
> and want to merge them using pushouts. We must first compose the patches
> c-d, ..., f-g and the patches h-i, ..., l-m and then take the pushout of
> the two resulting composite patches. So in general, merging n patches
> with m patches is O(n + m). But AIUI in Darcs, we have to commute every
> patch in one branch past every patch in the other branch, so it's O(nm)
> - is this right?
> 
I think it would be O(nm) in the categorical framework too, if finding
the pushout is linear in the size of each of the patches (ie the
compositions c…g and h…m). I think this more or less follows from the
definition of the pushouts.

--
Florent