Re: Merge with git-pasky II.

[Sanjoy Mahajan <sanjoy@mrao.cam.ac.uk>]

> And that "where did this come from" decision should be done at _search_
> time, not commit time.

I like this elegant approach, but clever pattern matching can help even
at commit time.  Suppose hello.c is simply:

  printf ("Hello %d\n", year);

And then developer A updates hello.c to:

  printf ("Hello %d\n", year);
  printf ("And   %d\n", year+1);

Meanwhile developer B updates hello.c to:

  printf ("Hello %d\n", yyyy);

How to merge these two changes?  The psychic solution is

  printf ("Hello %d\n", yyyy);
  printf ("And   %d\n", yyyy+1);

Darcs handles token renames specially, but it's not a general solution
so let's leave it aside.  The example does not have enough information
to make the psychic solution unique or reliable, but imagine that the
example were longer to solve that problem.  You'd want to describe the
delta A(hello.c) as
   
  1. duplicated message line
  2. changed 2nd line a bit

And B(hello.c) as

  1. Changed year to yyyy

In that representation, merging the two deltas becomes

  1. duplicated message line
  2. changed 2nd line a bit
  3. Changed year to yyyy in both lines

Or, by commuting the merge operations and adjusting for their
non-commutativity (in terminology like darcs's -- I'm also a physicist):

  1. Changed year to yyyy
  2. duplicated message line
  3. changed 2nd line a bit

So here some of the computation that Linus wants only at question time
(e.g. 'how did that line get here??') is also useful at merge time.
It's difficult (expensive, unreliable) to describe deltas in the form
above or, worse, to merge two such descriptions, but I hope it
illustrates the point.  And perhaps a robust and easier-to-compute
change-description language can be dreamt up, even if the general
problem of describing changes compactly is not computable -- it's almost
the same, or is the same, as finding the Kolmogorov complexity of a data
set.

Or have I missed a fundamental point?

-Sanjoy

`A society of sheep must in time beget a government of wolves.'
   - Bertrand de Jouvenal