[darcs-users] questions on patch theory

[Mirian Crzig Lennox]

droundy at jdj5.mit.edu (David Roundy) writes:
> 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.

The hunk which moves *down* changes size; the hunk which moves
up stays the same size.  So one must actually use both of the
transforms I mentioned (I erred in saying that the second transform
doesn't help; that's what I get for not plotting it out on paper
first).

So, in the example you gave,

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

let's assume that the file has 20 lines before any patches are
applied.  Let's also say for convenience that a negative line number
in a patch means "count that magnitude back from the end of the file".
Hence in our 20 line file, line 1 == line -20, line 2 == line -19, and
so on to line -1, which of course marks the last line in any file.

Thus, an equivalent representation of the above composition would be:

  hunk (at line 2)
  +hello world
  hunkmove (9 lines) (from line -16) (to line -21)

which would commute to

  hunkmove (9 lines) (from line -16) (to line -21)
  hunk (at line 11)
  +hello world

allowing the hunkmove to remain constant in commutation.

Unfortunately, this pretty well proves that my "influence" cannot be a
relationship purely of changes, because here is a case where
equivalent representations of the same changes have contradicting
influence.  So influence *must* be primarily a relationship of
patches.  And in fact, reflecting on what you wrote below, it makes
sense that it should be this way:

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

This is a very good point, and leads to an interesting rhetorical
question, "Why does commutation *ever* result in differing patches?"
A patch is after all a representation of the user's intent, which is
not itself changing.  Therefore, if commutation results in differing
patches, then it is because one or more of the original patches
imprecisely represents the user's intent.  The theoretical ideal
representation of intent results in patches which are perfectly
commutative with one another, except where a genuine dependence or
conflict exists.

Given the above, what I have been calling "influence" is perhaps more
aptly something like "distortion".  Though the theoretical ideal of
zero distortion is probably not universally achievable, it may be
approachable, given a suitably powerful grammar for describing
changes.

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

Hence the number of commute operations increases in a triangular
progression with the number of primitive patches involved:

        2 patches require 1 commute
        3   "        "    3 commutes
        4   "        "    6    "
        5   "        "   10    "
        n   "        "   (n * (n - 1)) / 2 commutes

That starts to add up.  Are there any shortcuts?  My knowledge of
Haskell has increased (from nil a fortnight ago) to the point where I
can just about make out that commute_composite in Patch.lhs seems to
perform a recursive series of commutations on its component patches,
but if any additional cleverness is taking place, it'll be right over
my head. :)

--Mirian