[darcs-users] questions on patch theory

[David Roundy]

On Sun, Sep 14, 2003 at 03:11:56PM -0400, Mirian Crzig Lennox wrote:
> All right.  Just as a reality check, one of the assumptions I'm making
> is that, for any existing composition of patches AB, exactly one of
> the following is true:
> 
>         (1)  A is dependent on B
>         (2)  AB <-> BA    (i.e. A and B represent orthogonal changes)
>         (3)  AB <-> BA'   (changing context modifies A)
>         (4)  AB <-> B'A   (changing context modifies B)
> 
> In particular, it's never the case that commutation requires both A
> and B to change (AB <-> B'A').  (At least, I can't think of a reason
> why it should; can you?)

Yes, there could be a case where both change.  I don't think there is yet
one in the current implementation, but I want to implement hunk moves
(which would move a hunk of lines from one location to another, as you
might guess).

So

hunk (at line 2)
+hello world
hunkmove (5 lines) (from line 1) (to line 10)

would commute to

hunkmove (4 lines) (from line 1) (to line 10)
hunk (at line 11)
+hello world

There are a number of thorny issues in the commutation of hunks with
hunkmoves--basically they come up whenever there is an overlap of
boundaries--which is why I haven't yet implemented hunkmoves.  My plan is
to implement them after I've released darcs 1.0, since they will take a
while to debug and may introduce interesting bugs.  Even hunkmoves
commuting with hunkmoves is a challenge, since you could end up splitting a
hunkmove into two hunkmoves upon commutation.

> For want of a better word, I've been calling this effect "influence"
> (or the lack thereof).  In (3), B influences A because A is modified
> leaving B's context.  In (4), A influences B because B is modified
> entering A's context.  In (2), neither change has influence over the
> other.  And of course, in (1), B exerts maximal influence over A (such
> that A is indeed stuck in B's context).
> 
> The useful feature of influence is that it is defined entirely on
> changes, rather than patches, and I believe it also obeys
> transitivity.  Precedence is essentially influence plus context: a
> patch is preceded by all changes in its context which influence it.

I'm afraid that when hunkmoves are introduced the influence will get all
messed up, since removing a hunkmove C from the context of both A and B may
change their influence relationship.
-- 
David Roundy
http://www.abridgegame.org