Git can't be made consistent

More like: semantically correct merge requires AI. Technical correctness, whatever the definition is, may be achieved algorithmically.

Merge associativity would be where taking an initial stage and merging commit A then merging commit B (where A and B are commits created independently but from a common start point) always creates exactly the same results as merging in commit B followed by commit A. The word "associativity" in this instance is being used in the same sense as it is used in basic arithmetic: (1+A)+B === 1+(A+B) === (1+B)+A and (1xA)xB === 1x(AxB) === (1xB)xA.

The merge processes used by Git and other common source control systems are associative for most circumstances where the two (or more) merges affect different parts of the code (including different parts of the same source file). The issue tends to raise its ugly head when the two merges affect the same lines. For instance:

    Original:     Commit A:     Commit B:
    line 1        line 1        line 1
    line 2        line 3        line 2
    line 3        line 4        line 3 updated
    line 4                      line 4

If you merge in that order line 2 will get put back as it will look to simple inspection like that is what is intended (merging in A removes line two, merging in B inserts line 2 (which to the merge algorithm is now a new line) and updates line 3). If you merge B first then line 2 is gone from the result (merging in B updates line 3, line 2 not needing to be touched as it is the same, and merging in A after that will remove line 2.

    Merge A then B:     Merge B then A:
    line 1              line 1   
    line 2              line 3 updated
    line 3 updated      line 4
    line 4       

It isn't just deletes/inserts that are affected: changes to the same lines can produce similarly inconsistent results depending on merge order. The trouble is that for a DVCS it is impossible to consistently deal with these situations without a manual merge (or AI better than we currently have). Either output could be the intention and without context other than the original state and the two commits you can't tell one way or the other.

A centralised source control system doesn't have this problem because as far as the repository is concerned there is one and only one timeline: commits happen in one order so the second will either always override the first where there is a question. This doesn't mean that the CCVS would be correct though, just that it would be consistent.

With either CVSC or a DVSC where a three-way merge (where the start point of each commit is known so the compare is done between commit, original state and current state) can be used then a merge conflict could be flagged for these issues, but a human still needs to make the final decision as no algorithm can be consistent (or correct) 100% of the time without a universe of extra context.

If you were presented with the commits above, would you know what should be done with line2? Does the change in line 3 depend upon it existing, so you must keep it, or is it irrelevant, so you should delete it (A says delete, B doesn't care either way)? Even if you knew that commit B was done later than commit A that wouldn't mean that it is necessarily the one to trust, and in any case there might be a more complex set of commits with a mix of conflicts where A is right in some cases and B in others.

People expecting Git to be associative in these instances are (by my understanding) asking for the impossible. Perhaps the merge algorithm could be made a little more intelligent, but I doubt it could ever be 100% correct or consistent (where consistent implies the associativity of merges). Remember that what we are dealing with here are edge cases (unless you have lots of people working on the same areas of the source tree at anyone time, in which case you should probably consider a more hierarchical distributed repository arrangement) and changing the behaviour will likely create other, similar, edge cases so it is probably not worth spending many man hours tweaking the merge algorithms for instead of introducing a little human intervention into the potentially inconsistent situations. Any changes that get "lost" due to the wrong decision being made by the automatic merge algorithm or the human will still be present in a good source control system (unless you have explicitly told it to purge them) so they are not lost forever.

Caveat: I've not used Git (or any DVCS) in anger yet, but I have been reading around the area with the intention of starting to use it to track my personal projects and perhaps recommend it (or something similar) to be considered at work. This is an issue that I thought about a while ago, and I'm thankful of this recent discussion as it has reaffirmed what I decided after thinking about it a bit back then: these are edge cases that are safe to ignore until the rare occasion when they happen, at which point nothing is lost (I'll just may have to make some decisions manually and/or raise a new commit to revert changes that are "made in error" due to the inconsistency). Of course I lack the experience needed to confidently suggest I can't be proven completely wrong on the matter!

My thinking when I posted my comment above was that any diff format used in the repository could be treated as an "internal" format, and any actual merges that you perform could use any merge strategy that they like, as long as the commit code converted it into the repository's format on the way in. Which is why I pointed out that git also uses an internal diff format. However, if your point is that hg uses an internal format which cannot store particular changes to files correctly, or requires excessive engineering, then yes, that would be a problem and I see where you are coming from. I do very much like the conceptual simplicity of git.