[darcs-users] questions on patch theory

[David Roundy]

On Thu, Sep 18, 2003 at 01:35:28PM -0400, Mirian Crzig Lennox wrote:
> droundy at jdj5.mit.edu (David Roundy) writes:
> > 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
> 
> In general I see your point, but there is one twist I would like to
> mention, which is that nothing forces you to describe a hunk relative
> to the beginning of the file (as you do above); it is equally valid to
> describe a hunk relative to the end of the file.  If you had done so
> in your hunkmove patch above, then it would commute with the hunk
> patch without modification, and the influence would go in one
> direction only.

I'm not sure I follow your reasoning here.  The hunkmove is modified by the
commute because its size changes, and the hunk is modified because its
location changes.  I don't see how the way we count line numbers could
affect this.

> Similarly (although it doesn't help in this particular situation), any
> hunkmove can also be converted into one which moves in the opposite
> direction; (e.g. instead of lines 1-5 moving 5 lines down, the same
> hunkmove can be specified as lines 6-9 moving 5 lines up).

That's true, there is an ambiguity, and it does cause annoyances when
creating hunkmoves.  I think the ambiguity can be useful, in that it means
that you can (in principle) use the hunkmove to describe the intention of
the user (which *should* affect its commutation).

The obvious use of a hunkmove is when you order the functions within a
file.  In this case, if the hunkmove boundaries match the function
boundaries, then any hunks modifying the function will commute with the
hunkmove (as they should), while any that overlap the edge of the function
will conflict (as they should).  Of course, there is no way to reliably
guess where to put the boundaries, so I'd like to make it customizable in
some way (either by a prefs file indicating preferred boundaries, or
interactively).

Actually, similar ambiguities exist when defining hunks.  I first calculate
the LCS (longest common substring), which is usually unambiguous, but then
there are also usually multiple equivalent ways of matching up that LCS
with the file, which create "equivalent" patches that commute differently.
Unually this shows up in the choice of whether to include a space at the
beginning or end of a hunk.

> So, at the risk of making things even more complicated, a patch
> describes a change not only across an infinite set of possible
> commutations, but there may also exist equivalent permutations of that
> patch which have different commutation properties.  I'm not sure if
> this makes things easier, or if it just opens up a huge can of worms.

It's a feature, not a bug!  :) The key is to view each of these changes
(which affect the file in the same way) as being different, which they are.
The difference is (or should be) associated with the user's intentions.
The existing case of this sort of difference actually reflecting the user's
intentions is the token replace patch, which of course is equivalent to a
lot of hunks.  Its advantage isn't that it is smaller (although that is
also true) but rather that because it (presumably) reflects the user's
desire more accurately, it will commute with pretty much any hunk, and
merges with it very rarely lead to conflicts, and when they do lead to
conflicts, it is when they should conflict (e.g. I rename variable A to B,
but you introduce a new variable named B).

> > 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.
> 
> This brings up an interesting issue on its own, one which is not
> really covered in your theory: how are commutations on aggregate
> patches performed?  If you have the composition MC, where M is itself
> a composite patch, AB, then how is the commutation MC <-> C'M'
> represented?  My naïve guess is to expand M and perform a three-way
> commutation; i.e.,  { ABC -> AC'B' -> C''A'B' -> C''B''A'' }.
> Is this correct?  

That is correct.  A composite patch behaves just like the composition of
its subpatches--(AB) commutes like AB.
-- 
David Roundy
http://www.abridgegame.org