Log in

No account? Create an account

Fri, May. 6th, 2005, 07:24 pm
More version control stuff

Linus Torvalds thinks that Git is already better at merging than everything else. In the sense that Linus personally has a magic merge algorithm knows as 'Andrew Morton' that's correct, but for everybody else this claim is completely false. (I asked around about what he could mean, and some people suggested that 'better' might have meant 'faster', which is the only explanation which doesn't involve Linus being delusional or lying.)

Unfortunately Linus's stated plans for Git are that it should only ever have whole tree three way merging (because that's the simple, practical, expedient way) and that it will have implicit renames and moves of lines between files (because that's the 'right' way). The resulting approach isn't workable even on paper. Whether the plans will be changed in advance of a disaster remains to be seen.

Meanwhile, we recently made a big advance in merge algorithms, you can read the latest about the upcoming new Codeville merge algorithm in this post.

Mon, May. 9th, 2005 11:33 pm (UTC)

We disagree on four cases:

llu	u	l
ldu	u	l
ddu	u	d
ddl	l	d

These are all "roll-back" cases - they can only arise if the revision history is something like "C -> B -> A" and we want a version of A without the C -> B change. I think you're right about "ldu l" (it's one of the ones I marked with a query) but I'm surprised on all the other three - surely where A = B, a "roll-back" has to do what's in C?

Thinking about it further, for rollback to work, the rule has to be more like ((C == B) ? A : C), but this isn't right for "ldu l" or "dlu d" - I'm not sure if "udl u" is correct or not. The cases with discrepancies are

ddl l l d
ddu u u d
dlu u d d
dul l d d
ldu u l l
llu u u l
udl l u u

Columns are my rule, my hand-picked, your rule.

Tue, May. 10th, 2005 12:38 am (UTC)

The problem with doing rollback in this sort of way is that A inevitably gets merged with a near-relative of A very quickly, so if something was d in A then it will rapidly become d again. Rollback needs to use a different mechanism, probably involving line suppressions which can be undone later.