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

[AntC]

Florent Becker <florent.becker <at> ens-lyon.org> writes:

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

I'm aiming to capture patches in a context-independent representation (subject 
to pre-conditions), such that pulling/merging each patch:
1. validates the pre-conditions by looking purely at the repo 'as is'
2. can then straightforwardly apply the patch as deletes/inserts to the
   repos internal representation, and map that to external representation

I guess that means pushing the hard work back to the point of recording the 
patch: extracting the context-dependent bit into pre-conditions, and the 
effect into the representation.

It's not clear to me whether under Houston's model patches are held in a 
context-independent representation(?)

AntC