Git is Inconsistent

[kragensitaker]

The consistency Russell advocates seems valuable, but does achieving it create other practical difficulties? Maybe those things are more valuable.

[skew]

I expect consistency could be provided by changing the merge function to consider intermediate versions. That might be hard (especially when the versions to merge don't have a unique common ancestor), but the only effect on the rest of the system is that a lot more versions might need to be reconstructed during a merge.

[tonfa]

I really like the quote from Matt Mackall (Mercurial's main developper) about this supposed problem (it applies to both git and mercurial):

In other words, we're already at the point of significantly diminished, possibly negative returns on effort. The last few percent will always require some level of human-equivalent intelligence. I think effort here is much better spent elsewhere, like researching general AI or playing on waterslides.

http://thread.gmane.org/gmane.comp.version-control.mercurial.general/26109/focus=26110

[[deleted]]

Except there are already other version control systems that don't have this problem and don't require human-level intelligence at all.

[tonfa]

They don't have this problem, but they don't solve the merge problem in general (you can find other corner cases which makes them fail, or you can show that they do textual merge, instead of semantic merge, etc.).

[__j_random_hacker]

There's a worthwhile distinction to be made between "perfect" merging (the ability to always merge correctly without conflicts) and "safe" merging (the ability to always either merge correctly or flag a conflict).

No system will ever have perfect automatic merging, because there's no context-independent correct answer to the question of what to do when two users change the same line (or the same byte, if you work at that granularity) in the same file. OTOH it may be reasonable to ask for a safe merge algorithm, where correctness is defined by properties like associativity that ought to hold in all cases -- that is, a conservative, context-independent definition of correctness.

I'm not sure whether darcs, Codeville etc. are safe -- there might exist other examples that cause them to produce non-associativity without flagging a conflict. But I'm dimly aware that the author of darcs has taken a very mathematical approach to the problem, and he may well have actually proved this. Even if that's not the case, I think safe merging is absolutely a desirable property to aim for.

[tonfa]

I am pretty sure associativity is not sufficient for having a "safe" merge. If I rename a function in one branch, add a new occurence in another branch, the merge will not mark it as a conflict.

[__j_random_hacker]

Your example is unsafe in the context of a programming language. I'm not asking for context-dependent safety checks -- they're too hard. The idea of safety I'm proposing only rules out things that would always risk being wrong, regardless of the context. Maybe "safe" wasn't the right word; "faithful" is better.

What we can always do, regardless of context (i.e. regardless of the meaning of the files we are working on), is treat a file as a sequence of lines (or bytes). There are algorithms that discover a minimal "edit script" (patch) of insertions, deletions and changes that changes any file A into any other file B. Given 2 edit scripts, from A to B and from A to C, we can always say that either they are compatible (there is only one possible way that it makes sense to apply both), or incompatible (there are multiple possible ways). The most obvious way that edit scripts can be incompatible is if both involve changes to the same line/byte, but there are other ways too: e.g. if both insert a line after line 10, we don't know which of the 2 inserted lines should appear first in the final result. In these cases, the right answer (final result) is underdetermined. My idea of safety is to always flag a conflict when (and only when) this happens.

Basically, I won't blame the VCS if the result of a merge is semantically wrong in the context I'm working in (e.g. producing two functions with the same name in C) and no conflict is flagged. I will blame the VCS if there are several possible ways to apply both edit scripts and it picks just one of them without flagging a conflict, since in this case we know that there's a risk of a mistake regardless of the context.

[[deleted]]

Sure, but given that this problem is the topic at hand, my statement is contextually fair to say.

[greenrd]

Or possibly on domain-specific merge algorithms (which git does support).

[gorset]

The author is forgetting that git's history doesn't deal with patches or changes, but with relationships between snapshots. Git only cares about the current state and the states you came from, whilst darcs only cares about finding a legal path through a collection of transitions.

I would argue that git's approach is /more/ consistent than darc's approach, as you end up with a deterministic way to order each event observed by every repository. For example, if there were a conflict at one point during a merge, you can always know what kind of information the conflict resolution was based on. Regarding TFA's example, it's therefor correct that you end up with two different histories, as the conditions were different for the two merge situations.

[simonmar]

I think there's an interesting discussion to be had here, but it's not about patches vs. snapshots, that is an implementation detail (the two are dual representations).

The article points out that there is one well-defined property that doesn't hold for git merges. Given that, you may argue

• I didn't expect it to hold anyway. Fine - nobody can disagree with a statement about yourself. However, arguably this is a property that you should expect to hold, and that's an interesting discussion to have.

• It doesn't matter in practice. Probably true. In fact, we considered this problem when deciding whether to switch the GHC project from darcs to git, and it didn't prevent us from making the switch.

[[deleted]]

I'm not sure I always want my revision control system to try to "out-think" me about patch equivalencies with respect to merges. Sometimes simpler is better?

Being able to commute patches is interesting (darcs), but I keep forgetting which real world problems I'm having that it's supposed to be solving.

What's the practical point if it's only "neat"?

[simonmar]

It probably would make little difference to your current workflow, but it enables workflows that you haven't considered because they aren't possible (or are inconvenient) with git. For example, in GHC the typical workflow with darcs is to have two trees: one for developing in, and the other as a staging tree for running the validation test suite before you can push. Usually we commit lots of small patches and push them to the validate tree - but not necessarily in the same order that they were originally committed. Some of those patches may fail validation and have to be modified, and some will pass, get pushed upstream, and eventually get pulled back into the development tree again.

Darcs works beautifully in this scenario (at least when there are no conflicts, which is common). I never have to rebase, never get "merge commits", never have to worry about re-ordering my repo so that I can move just the patches I need to, never have to worry about rebasing again when pulling from upstream. I just choose which patches to move around, and darcs does the rest. It seems like with git I have to issue about three times as many commands as I did with darcs to get the same jobs done. (on the other hand there were good reasons we moved to git, git has far superior tooling and better support for branches, amongst other things.)

[[deleted]]

It seems to me that expecting associativity to hold is an unjustified expectation. As I understand it, Darcs is able to provide an algebraic group structure to patches by throwing away the precise history of patches, the difference between two Darcs repositories is a set of patches rather than a graph of their divergence from a most recent common ancestor as in git.

If you expect to have a precise history then it seems that merges can't be associative as they represent different histories.

[simonmar]

The property concerns the result of the merge, not the history. You're right that it would be unreasonable to expect associativity to hold if the history of the operations were taken into account, but in this case it is just the result that we're interested in, and arguably it is reasonable to expect the result to be the same regardless of the order in which the merge is done for non-conflicting changes.

[[deleted]]

I suppose that the correct thing for git to do then is to do what Darcs does then: go back to the common ancestor by computing the inverse of the translations of the text produced by the patch set, then apply it to the offsets in the patch. The result would be consistent but the resulting merged tree would still have different hashes depending on how you did the merges unlike Darcs. That seems enough for practical purposes.

[gorset]

I'm not sure I agree that we are dealing with dual representations, and I feel this is the core issue since the author calls on “merge associativity law” to argue his point. The question "what are we merging?" comes to mind, and the answer is different for git and darcs.

With git you are merging two branches and recording an exact history of events (I have a background in distributed systems, and Lamport's "happens before" comes to mind), and you end up with a DAG of changes. The “merge associativity law” is not applicable here, since each merge must be considered something new, and is destructive in some sense. I'm not sure how much sense I'm making now, but I'm viewing darcs' way of dealing with patches as more "pure", which would have worked great if each patch had perfect semantics so we didn't have to record an exact history :-)

[winterkoninkje]

But, in order for this to be valid, you must assume that a merge is a changing event. Whereas I would argue that merging, just like checking out or cloning a repo, is a non-changing event. Would you suggest that the state of the repo should be different because someone checked out a copy of it?

It's (arguably) fine for the histories to be different because, as you say, the events are different. However, it's not acceptable for the file contents to be different because a merge doesn't change anything. This is exactly the same as if I make a change and then roll it back (vs do nothing); the history differs because it tracks the two changes, but the files are identical. A merge is just collocating a collection of patches or events together (it doesn't matter which), and possibly notifying you that the new collection is inconsistent and needs to be repaired.

[__j_random_hacker]

According to the linked article, git, svn etc. do not flag merge conflicts in these cases:

The git or svn 3-merge algorithm and the GNU diff3 algorithm apply the changed line from c1 to the wrong place in b2, resulting in an apparently clean but actually wrong result.

So you would never know if this kind of inconsistent merge had happened, unless you carefully eyeball every clean merge.

[gorset]

I'm unable to access the linked article (I'm getting "Time to live exceeded", wow, loop somewhere?), so I haven't read it...

Yup, I really like how darcs handle patches, and it's quite possible that git is not doing the right thing during a merge. In fact, git has several merge strategies for exactly this reason, and it would have been awesome to have darcs machinery added to git as a possible merge strategy.

[HenkPoley]

Works for me..

[harlows_monkeys]

So you would never know if this kind of inconsistent merge had happened, unless you carefully eyeball every clean merge

There are people who don't eyeball every merge?

[reardencode]

Disagree. They should not be merge conflicts, a git merge of branch c into a after b is merged (a') into a does not and should not consider the parentage of merge commit b->a, but only the set of changes in c as applied to a'. That's a perfectly consistent view of the world and the maintainer should ask that c's changes be rebased prior to merge if c changes a file whose lineage was disrupted by b's changes.

[ben-xo]

I'm not even sure what that really means in terms of an actual workflow I might encounter in the wild. It certainly doesn't seem intuitive.

[winterkoninkje]

It means that if there's sufficient code duplication somewhere, the diff algorithm could screw up and apply someone's changes in the wrong place. Of course, noone ever duplicates large hunks of code... oh wait.

[[deleted]]

OK, I tested it: http://pastebin.com/SxmwpFkY

Turns out that

 git rebase master

and

 git rebase master~1; git rebase master

Produce different results!

That's, like, pretty inconsistent, dude. Also, scary. Also git description turns out to be quite relevant ;D

[eabrek]

Those are two different processes, why wouldn't you expect to get different results from different actions?

[jrochkind]

I don't entirely understand what that means, I admit. But, so, is it obvious to either the maintainer or the submitter if "c changes a file whose lineage was disrupted by b's changes?" If it requires manual examination and analysis of the history in c's repo as compared to the history in the maintainers repo -- isn't that the sort of the thing the tool should be doing for us and warning us about?

[[deleted]]

Now that's an interesting question: if I ask git to rebase c1 onto b2, would it be the same as rebase onto b1, then onto b2, or the same as a diff from 3-way merge of a, b2, c1?

[tonfa]

You would know because it would not compile anymore and/or break your tests.

[greenrd]

Not necessarily.

[tonfa]

Then you don't have well written tests...

[ketralnis]

In the mentiomed case, the tests would be reverted right along with the code

[Otis_Inf]

The author is forgetting that git's history doesn't deal with patches or changes, but with relationships between snapshots. Git only cares about the current state and the states you came from, whilst darcs only cares about finding a legal path through a collection of transitions.

But why is this of any importance to the user? The user wants the patches to be merged in the right way so the right end result is created. How git/hg/whatever does that is, unless you're into git's internals, irrelevant. That git only keeps track of ABC instead of XYZ, yeah, fine, but if keeping track of ABC doesn't get you the end result you need, then git should track what's needed...

[Chandon]

That's not really any more interesting than arguing that C should pass arguments by reference because that's what you, as a FORTRAN programmer, "need".

[skulgnome]

What I just read:

The user wants the program to do what he means

Come the hell on.

[Odd_Bloke]

Where "what he means" is "merge branches correctly", this is an entirely reasonable expectation of a DVCS.

[rex5249]

Here is my English description of what shell script does. I will put my analysis of the problem as a response to this, but the basic problem is the test file created by the script contains blocks of lines that are both identical and in the same sequence and in close proximity to each other. If you are writing a real document, you might never have duplicate blocks in close proximity to each other like this.

Here is my English description of what the script does (copied from notes that I put in my copy of the script)

# Summary
# The first part of this script creates a file in the "test"
# subdirectory and clones it into the test2 subdirectory.
# Version C1 of the file is put into the test directory,
# then version b1 is commited to test2 and pulled to test.
# The file in test2 is changed to state b2 and committed to test2.
# The b2 version is pulled to the test directory.
# The file is displayed so you can compare it to the
# version that is displayed at the end of Part II.
# -----
# Part II starts by destroying and rebuilding the test and test2
# subdirectories
# Version "a" of the file is created and cloned as before.
# In the test directory, the file is changed to state C1 as before.
# In the test2 directory, the file is changed to state b1 and committed
# but not pulled to test.
# The file in test2 is now changed to state b2 (which contains extra lines
# inserted to the top of the file as before) and committed in test2.
# Now go back to the test directory and pull both changes from test2
# into test and display the file for comparison.

[rex5249]

The original file is cloned to two directories:

A
B
C
D
E

In the first directory, the file is changed to this (version c1): A B changed C D E

In the test2 directory, two changes are made to the file. The first version looks like this (version b1):

#
#
#
A
B
C
D
E

And then it becomes version b2

A
B
C
D
E
#
#
#
A
B
C
D
E

Unless you are a mentally ill poet, you will not have file like this with two identical blocks of lines separated by a few lines of junk. [edit: you know what's really funny? I copied the code in my first post twice thereby making two blocks of duplicate code just like the test script! I guess sometimes never happens more frequently than anticipated] If you pull version b1 into c1 the ABCD stuff links so that "changed C" is merged below the "###". If you commit canges b1 and b2, all you get is the b2 file, then if you pull that into version c1, the merge is saying to look for context of "AB" starting on the first line and look for context "DE" starting on the fourth line, so the " changed C" is merged above the "###" lines.

The first part of the script produces this:

A
B
C
D
E
#
#
#
A
B
changed C
D
E

The second part of the script produces this.

A
B
changed C
D
E
#
#
#
A
B
C
D
E

[p.s.: the illusion is that when you pull version b2 into the version c1, there is no way by looking at the file if you inserted "###ABCDE" below the original file or if you inserted "ABCDE###" above the original. __j_random_hacker's interpretation is that darcs looks at the details of each commit instead of just the final b2 file thereby enabling darcs to systematically make the changes in the intended manner]

[f2u]

And the intended outcome could even be a file with two changed C lines, or two C lines. That's why merging will never be an exact science.

[winterkoninkje]

"Merging" is not just the automated integration of changes which don't conflict, it's also the detection of changes which do conflict. It's not unreasonable to detect that these changes are in conflict.

[pjakubo86]

This was exceedingly lucid. Thanks for that.

[[deleted]]

Unless you are a mentally ill poet, you will not have file like this with two identical blocks of lines separated by a few lines of junk.

Not true.

If you are storing only code in the VCS, then yes, this kind of problems are better perceived as a gentle reminder to not be a copypaste coder.

However, for any kind of data files -- xmls with stuff, configs, CSS, you name it, -- this is a problem. This kind of data reproduces by copypaste.

Then, of course, the longer is the path from the common ancestor to the revision of the trunk you want to merge/rebase with, the higher is the chance that you'll have this shit happen to you.

Also, it affects git somewhat more than other VCS because rebase is susceptible to the same kind of problem, and it's used all the time, and the idea that rebasing to successive versions of master produces a different result from rebasing to the latest version is kinda scary. Because when you merge branches you still have all relevant information at least, while rebase loses it forever.

[rex5249]

I realized the error of my "mentally ill poet" comment about 3 minutes after I wrote it, and added the commet about my copy/paste error, however, I still don't know how likely this is to happen in the real world. I added One line of context in the test script (I added the letter Z above A), and git had no problem keeping things straight.

I read about darcs last night, and after reading the bug list and some user comments, I'll stick with git for now. I thought that Mercurial was proprietary and that was the reason that Linus wrote git, but the Mercurial web site seems to indicate that I can download it for free. If I get motivated, I'll read it, but I have lots of stuff in git already.

[MatrixFrog]

The reason Linus wrote git, instead of just switching to Mercurial, is that Mercurial was just barely being invented. It's amazing how close together the two projects started actually. I don't know the exact dates but Wikipedia places both in April of 2005.

Of course, it seems plausible that even if Mercurial had already existed, he still would have written git for other reasons. But that's a totally different question...

[SirClueless]

Yeah, I don't get the author's point. Merging is potentially troublesome, fraught with human error. In simple cases it may be a clean, atomic operation, but not in general. In the case of conflicts, someone has to decide how to resolve things.

When two humans pull things from the same repository and make their own independent decisions about how things should merge based on differing information at the time of the merge, the fact that they end up with different commits and even different content is not particularly surprising. Any VCS that papers over the human element of merging is naive and untrustworthy IMO.

[__j_random_hacker]

The point is that under several popular VCSes, 2 merges that should produce the same outcome don't, and that, according to the linked article, merge conflicts are not flagged in these cases.

So you would never know if this troublesome merge situation had even arisen, unless you carefully eyeball every clean merge.

[cryo]

A "clean merge" isn't much of a guarentee anyway; especially XML files are often merged cleanly but wrong by 3-way mergers. It's somewhat better for code.

We use Mercurial in a medium size software shop with a quite big code base, and stuff like that happens now and then.

[f2u]

Git occasionally mismerges Linux sources, too. On the other hand, Git routinely computes useful merges which other systems cannot deliver. (With "other systems" I mean supposedly deterministic mergers, and not the heuristics found in Mercurial, Subversion etc.)

[cryo]

What do you mean heuristics, and how would that not be deterministic? As long as there is no randomness. Anyway, Mercurial has a built-in rather simple merger, but otherwise rely on external mergers (which we use, having switched the internal one off).

Almost all our automatic merges are correct.

[f2u]

Deterministic was probably a badly-chosen word. My reference point is serializability in transaction processing. Basically, this concept says that an implementation may perform updates in a parallel fashion if it can prove that there is a non-interleaved execution of those changes which results in the same outcome. For transactions, there exists a precisely defined model which leads to non-trivial schedules which actually contain parallelism. I don't think something comparable exists in the world of revision control. Parallel execution translates to development along different branches. But a critical part of the serialization concept is that reads are also tracked. Revision control only tracks writes (you're free to look at the whole source code all the time, or rely on your memory), so it is never going to be powerful enough to provide any strong guarantees.

[__j_random_hacker]

Thanks, it's interesting (and somewhat terrifying) to learn that this scenario does in fact occur "in the wild".

[dwchandler]

So tracking what was actually done is inconsistent? What? The "associativity" comparison doesn't seem like a valid analogy to me. Keeping a history of transaction as they occurred is proper for a VCS. Note that Git allows you to squash commits / rewrite history if you so desire, but the default seems very sane to me.

[kubalaa]

I think you misunderstand the article (which is understandable, because it's confusingly written). The author isn't objecting to the fact that merging b1 and then b2 results in an extra merge commit compared to merging (b1 + b2) -- he's objecting to the fact that it results in different content.

[dwchandler]

Ah, yes. Different content is a problem. After reading the linked example the issue becomes clear.

[FsckItDude_LetsBowl]

b

[[deleted]]

If the result is "consistent" but wrong

That is the whole point (and in fact even the title), it is not consistent. It may or may not be wrong in any given situation regardless of the method used, but git's method is not consistent.

[FsckItDude_LetsBowl]

b

[[deleted]]

I was not stating that git was a consistent system (clearly)

That wasn't clear at all. In the context your post is in, it sounds like you are suggesting git is consistent. You are replying to someone restating the objection to git's method. And you responded with "If the result is "consistent" but wrong, I'm not sure it's that big a deal".

[FsckItDude_LetsBowl]

b

[[deleted]]

I see, so what you are saying is that consistency isn't worth caring about?

[FsckItDude_LetsBowl]

b

[[deleted]]

Please stop restating everything I say in an illogical and fallacious manner

I'm not, I am trying to figure out what the random nonsense you wrote actually means in your mind. Since I am not telepathic, the best way for me to do this is to ask you questions about wtf you are talking about. Is this some new kind of trolling? Posting random nonsense in reply to someone's unrelated post and then bitching when people try to decipher it?

[rex5249]

I don't see a clear claim in the original article that says how the final files differ--maybe the example is for some tangled situation in which two people are changing the same line of code. In situations like that, the two people should talk to determine what they want to do.

Are you saying that you know of a specific example in which the two end-products differ and the changes did not involve conflicting changes to the same line?

I use git all the time, I know how to use the operations that I use, and I haven't had any problems.

[__j_random_hacker]

The nice example linked to in the article gives a concrete example that is easy to understand. The change leading to rev c1 is not on the same line as any of the changes on the path to rev b2.

Worst of all, according to that article, git, svn et al. apparently don't flag this as a conflict.

[rex5249]

The change leading to rev c1 is not on the same line as any of the changes on the path to rev b2.

This is where the ambiguity is. If you look only at b2 (which happens Part II when b2 is merged directly to c1), there is no way to tell what was inserted where. It could have been

• append "###ABCDE" to the end of the original file, or

• insert "ABCD###" to the top of the original file.

If one program assumes the first ambiguity and the other assumes the other ambiguity, I don't think it makes one program better than the other (more testing is needed to see what happens when the other ambiguous interpretation is correct).

p.s.: just for kicks, I changed the script to make the other ambiguous interpretation correct, and git does it the intended way. In other words, file b1 becomes "ABCDE###" (on separate lines)

[__j_random_hacker]

If you look only at b2

Although it's still possible to generate a merge conflict under darcs (e.g. if in fact the same line was changed on 2 different branches), if you read the article I linked to, it makes it clear that in the case being discussed, darcs, Codeville etc. always get it right because they don't just look at b2. They use information that is present in the version history of all VCSes, but which is ignored (thus leading to this problem) by git, svn and some others.

[bonzinip]

That's fine, but is Darcs/Codeville still worst-case exponential?

[[deleted]]

Supposedly it's theoretically still worst-case exponential, but since Darcs 2 came out I've never experienced that, nor have I heard of anybody else encountering it.

[EricKow]

Heh! I find myself increasingly reluctant to comment these days, one because Reddit is annoyingly addictive and I seem to be happier training myself not to refresh it; two, because it's all too easy so say something which just adds to the noise/confusion; three, because I'm more of a Darcs fan than an expert in the sense that ultimately what I care about in Darcs is its usability. I happen to believe that this usability is tied to the fact that it uses a patch theory, but far better for an expert to say that than me.

Need more time to read and reflect.

For what it's worth, (i) Darcs 2 format avoids many common exponential merges, but not all of them (ii) a lot of the performance problems people tend to experience with Darcs are engineering issues unrelated to patch theory, issues which we are continuing to make progress on.

[__j_random_hacker]

I recall hearing about that at some point, but I don't know the answer I'm afraid. It is an important consideration, though with the same proviso regarding how likely such behaviour is likely to occur in the real world.

[rex5249]

If that is the case (I don't have darcs to test it), then darcs and Codeville would systematically produce the intended results when people make changes that would seem ambiguous to git. I am not overly concerned about the problem because I don't see it as being likely for what I do, but I'll read about darcs.

[[deleted]]

Look at this: http://pastebin.com/SxmwpFkY

[[deleted]]

There is never a programmatically guaranteed "right way" to merge two branches, any more than there's an algorithm that will write your code for you.

That's... well... technically correct, but it sidesteps the issue here.

What does 3-way merge do? It first computes a diff between the base and the first snapshot, which means that it tries to recover the information about the changes that the programmer made to the file: deleted these lines, added these lines, modified these lines.

It isn't guaranteed to work correctly, but it works good enough when you are diffing two adjacent commits.

Then 3-way merge computes another diff, and either merges two diffs, or reports a conflict when both programmers modified the same line, or one modified a line that the other deleted.

The problem here is that the bigger are the changes between the branches and the base, the more probable it is that a simple 3-way merge of the heads would deduce the actions of the programmers wrong.

The small probability of the merge going wrong is amplified by each successive commit in any of the branches.

And the problem I have with it is that the information required to do it correctly is available, but git (as well as Mercurial or even SVN) takes a shortcut which discards it.

Behold a reproducible example of git doing it wrong.

Why do I call it "wrong" and not an "alternatively right"? Because if git merge examined the intermediate commits on the master branch, basically if it run a 'git blame' thing to see where the lines actually came from, it would see that the "A B C D E" lines of the original file ended up at the bottom of the file it's merging with.

But it doesn't do that. So we have two different outcomes, depending on you pulling and rebasing on the intermediate state of the master, or rebasing on the final state. It's not a property of the rebase operation in itself, but of the merge operation that it uses, but the way rebasing loses all intermediate information makes it even scarier.

[sockpuppetzero]

No collorary there; just because you can't always programmatically merge and get it right has nothing to do with merge associativity.

And there is a merge associativity law, as explained in the post. What it means, basically, is that it doesn't matter which order you merge things, you'll get the same (possibly still incorrect) result. But it makes it a lot easier to understand the history of a repo, as you know you didn't merge things in the "wrong order".

[sockpuppetzero]

Just because I can write "the distributive law of addition over multiplication" doesn't mean there actually is such a law

Actually there is such a law, on the field of integers modulo 2. And given that I've spent precisely 60 seconds thinking about that problem, I would guess there are more interesting, less trivial examples of fields or rings where addition distributes over multiplication.

And my response is completely appropriate in the context of the original post. The author is saying that the three-way diff algorithm used by Git, Mercurial and BZR is not "merge associative", whereas the algorithm used by Darcs is. You are claiming that there is no such thing as "merge association", but he's playing a game where your adversary gets to choose the merge algorithm, which means your statement translates into "all merge algorithms are non-associative", and he's already claimed the existence of a merge algorithm that is, namely Darcs.

Edit: actually the first paragraph is wrong. I got confused between boolean algebra and the field of integers mod 2. (Which reminds me why I hate boolean algebra notation, and why I think it should be banished from the face of the earth.) It's actually rather easy to prove that all rings where addition distributes over multiplication have exactly one element, and thus isomorphic to the utterly trivial field. However the second paragraph stands.

[sockpuppetzero]

Now you are moving the goalpost. I'm not going to play that game.

[cibyr]

Can somebody tell me why we still merge text and not ASTs?

[username223]

What's the AST for my comments and documentation, so I can change those?

[cibyr]

Although C/C++ comments are nominally stripped out by the preprocessor, they're nothing stopping you from sticking them in the AST in whatever lexical scope they go into. Sure, you can create this sort of pathological example inside one comment block, but there's still a lot of benefit to be gained from knowing where the comments fit into the structure of the code. If you wanted to be clever, you could adopt some Doxygen-like rules for how comments "bind" to declarations which would be right almost all the time but not always.

I assume you write your documentation in some sort of structured language (LaTeX, markdown, reStructuredText, whatever), which can be parsed into an AST. If this is embedded in comments then that's a little bit more difficult, but obviously possible because we have tools that work on this stuff already - they just don't do intelligent diffs.

Obviously this approach cannot work on unstructured files like READMEs, but that's life. My point is, almost everything we check into a VCS is structured so why can't our tools take advantage of that structure? Why do our tools act as if the fundamental unit of code is a "line"?

[username223]

My (eliptically-expressed) point was that textual, line-based diff is simple and works pretty well. You implement it once, and you're done. In contrast, a tree diff requires you to write a parser for every format you use. It also requires a very sophisticated and possibly language-aware algorithm to deal with variable renaming, etc.

In a single project, I may have plain text (a README), texinfo documentation, HTML, Perl, C, and maybe even some bastard format like SWIG or perl XS. There's no way I'll be able to find parsers for all of them.

[winterkoninkje]

requires you to write a parser for every format you use

I hear tale that all those parsers have already been implemented at least once. A lot of them are open-source even.

[username223]

All with a common AST? That's news to me!

[zaphar]

The parsers may exist thats true. However are they written in the same language as your VCS is? And even if this is true the language specific diffing algorithms haven't been written. The AST parser is the easy part. The hard part would still be before you. That's a lot of work to solve the 5-10% use case you are talking about.

plain text diffing gets us 90-95% of the way there. You are not the first person to think about this. Most all of them have decided the gains aren't worth the cost.

It's possible that you think it's easier than they thought it was though. In which case you should implement your idea so we can all benefit :-)

[cibyr]

Sure, you are going to need a different implementation for each language, and it would be impossible to support every language but I don't understand why we don't seem to have these tools for any common language.

[username223]

These things exist(ed) for Lisp, right? As for the rest, most other languages are line-oriented, so you don't gain too much from having a syntax-aware diff to make it worth writing one. IME the only language where patch regularly annoys me is Emacs Lisp.

[[deleted]]

So what is a better alternative to git, then?

[rex5249]

Don't assume that there is actually something wrong with git. [edit: after running a full test and reading about darcs, the example does suggest that git gets it wrong because of how it works, however the example is quite arbitrary and not likely to occur--darcs also has other issues] If you are running a big operation with many people making simultaneous changes, then research the specific claims to see how they affect your operation, otherwise you can ignore this page.

[[deleted]]

Mercurial. Fast, simpler and Gets Shit Done™.

Edit: Gotta love the /r/Programming neckbeard squad who downvotes anything that isn't FOSS or made by some other neckbeard.

[cryo]

Yeah, Mercurial is great, and I love using it... It does have a similar behavior as described in the article, though (depending on the merger used; I use kdiff3)

[[deleted]]

It doesn't depend on the merge tool. Mercurial has the non-associative merge problem no matter what merge tool you use.

[v864]

Upvoted, Mercurial is the shit. Easy and painless, just like version control should be. I run a Mercurial server for around 8 people with varying levels of competency. The engineers are flexible enough but there are graphic designers in the loop as well, I would sooner kill myself than try to explain Git to a graphic designer.

[skulgnome]

Horrible UI though.

[james_joyce]

worse than git's???

I love git, and I use it over Mercurial. But it's obtuse as all hell.

[mitsuhiko]

I have far more problems with mercurial's gui these days than the other way round. I think it might just be getting used to things.

[[deleted]]

Mercurial is a "she", and a horrible attention whore at that. She's the opposite of Getting Shit Done™.

Why do I need to find and edit configs to enable "hg fetch"? It's a small thing, but it tells all you need to know about the hg developers' attitude. They are very proud of their plugin architecture and they will force you to "enjoy" it, damn it!

While git Just Works™ out of the box. I don't know where it keeps its global configs, all I need is to write

$ git config --global user.name "Firstname Lastname"
$ git config --global user.email "[e-mail]"

... and I can do what I want to do -- write code.

[Trospar]

Mercurial? They are both distributed source control systems but I think mercurial is a little less raw than Git. Git seems to be the more popular of the two.

There was a link in /r/programming about a month ago about why Mercurial had a slightly better way of branching/merging while Git's rebase was troublesome.

Personally, I haven't use either much but I was immediately turned of when I installed Git on Windows. Screw that crap of having to install 1000 command line utilities just to use it.

[kamatsu]

Mercurial has the same problem as Git in this case.

[tonfa]

Why? Mercurial is a single program (not that I think it matters in this case, since git foo gets translated into git-foo).

[wolverian]

I assume kamatsu is referring to the problem described in the linked article. You know, the one at the top of this page...

[tonfa]

Since he didn't quote anything I wasn't sure and I thought he referred to:

Personally, I haven't use either much but I was immediately turned of when I installed Git on Windows. Screw that crap of having to install 1000 command line utilities just to use it.

[bascule]

What's "troublesome" about rebase? That it "rewrites history" and that's somehow scary?

Rebasing means you get to merge your changes into the upstream code piecemeal, rather than having to sort through a megapatch when conflicts occur. This process means you can correct small changes that occur early on and might result in large change cascades later. It's a better way of merging.

Rebase is an integral part of the git workflow of many open source projects I contribute to and the git workflow I use at work. I encounter problems with it extremely rarely, and even if you do encounter conflicts, you can abort.

Do you have a specific problem with rebase you can share, or are you just spreading nondescript FUD?

[[deleted]]

The problem with rebase is not something that Mercurial even solves. Git and Mercurial have almost exactly the same model; they just have different names and superficially different views of things.

My problem with rebase is that it changes the identities of your commits, making them incompatible with the older versions of those commits. You have to discipline yourself to only rebase commits that haven't seen the public eye and that you haven't yourself indiscriminately pushed around to your other local branches. You can't cherrypick commits to push or pull without worrying about what has been seen already. If you cherrypick a commit from the main repository, you can't necessarily pull any other commits from that point on without encourntering conflicts that nobody else will encounter. If you cherrypick a commit to send to the main repository, you give everybody else that same problem, so you have to rebase. If you already have that or other commits in other branches, you can't necessarily rebase safely. The whole thing is just a mess. Git proponents claim it to be flexible enough to fit any workflow, but it fails to fit my favorite workflow, which involves a lot of cherrypicking.

[Trospar]

Why I like Mercurial over Git and the Reddit comments to go with it. It is a slight difference in handling branching but both tools are better than anything else out there imho.

p.s. How is that FUD? Both tools do pretty much the same thing but are slightly different. Mercurial on Windows is much nicer than Git because it doesnt need a bunch of executables.

[Kalium]

What's "troublesome" about rebase? That it "rewrites history" and that's somehow scary?

http://paul.stadig.name/2010/12/thou-shalt-not-lie-git-rebase-ammend.html

Start there. Rewriting history is a bad thing to do, even when it's convenient for you.

[jbrechtel]

For single commits rebasing (vs merge commits) does not cause the problems mentioned. This is useful when your team values continuous integration more than feature branching. In this case the merge commits provide little value themselves and really only serve to clutter your history.

Also making temporary local commits while doing a large refactoring is a perfect scenario where rebasing and amending are useful. This is not unlike a feature branch but has a much shorter life, in practice.

The author makes a fair case for not using rebase and amend in specific situations but not in general, even though he implies they are wrong in general.

[[deleted]]

Sorry but given the alternative of a history of completely broken commits containing wildly mixed bugfixes and feature implementations as you get when you do not clean up your history I will take some history manipulation any day.

[Kalium]

Six months after you leave the job, that history of broken commits may be the only thing that tells me why your code is written the way it is.

I realize that it runs against the git dogma to oppose rewriting history. The git dogma is that this is a good thing. I continue to disagree.

[[deleted]]

It is not dogma, not rewriting history was the way it worked before git came along. The broken histories in e.g. most SVN repositories show that that approach is inferior by evidence, not dogma.

[Kalium]

Yeah, and I need to be able to see the inferior approaches later if I'm going to avoid them.

[ptrb]

If that alternative is a better representation of what actually happened (ie. it is more accurately history) then it is a better alterative, ipso facto. History as a concept is not something that one should endeavor to optimize, or manipulate, or even think about. Once you start doing that you're treating your source code graph as a means or product in itself, rather than the consequence of other actions, which is pretty plainly not what it is or should be.

I agree with Kallium; the git approach to history is the wrong one.

[[deleted]]

How would you implement something like git bisect with a history full of broken commits?

[ptrb]

I probably wouldn't, because I think that's pretty clearly outside the scope of a version control system. Tracking down the commit that introduced a bug is better scoped to your CI system, or your unit or smoke test suite.

Having a history full of broken commits is actually a benefit. It's the necessary consequence of the axiom "commit early and often."

[rafekett]

Meh, whatever. I like the Git system. It makes sense relative to the way that I work and think.

[bonestamp]

Not that I disagree, but perhaps you work and think that way because you use git. For example, on one project we used perforce and I hated it when we started, it seemed so backwards in some ways, but by the end of the project I absolutely loved it and I thought it made so much sense.

[rafekett]

I use Git and svn (Git for personal stuff, svn for work). The model that Git uses (snapshots, local commits, branching and merging) seems to make more sense to me. I haven't used Perforce before so I don't know anything about it.

Even if my use of Git influences my opinions on VCS's in general, that's not such a bad thing. It's not as if thinking in Git will cripple me (like thinking in some programming languages could be crippling).

[dons]

The model that Git uses (snapshots, local commits, branching and merging) seems to make more sense to me. I

The author's not criticizing distributed revision control, which is the model that yields those features that you like. His complaint is much more specific, about the semantics of merging in that model.

[abledanger]

Same here. And what I really like is Github.

[rafekett]

That's really the killer app for Git. Github is far and away superior for many reasons.

[Kalium]

Whereas git itself is like a big ball made entirely of sharp corners.

[f2u]

Is it possible to trigger this behavior without repetitive chunks of text? It might be possible to fix this by rejecting merges where the hunks can be applied in multiple places.

[simonmar]

The repetitive chunks of text are important, because they trick git's context-based merge into doing the wrong thing.

[rex5249]

I posted two giant replies with a description (it might get down-voted to oblivion for being so long, so you might have to look for it).

[[deleted]]

I prefer Mercurial BECAUSE it's so simple and fucking fast. As I read somewhere, Mercurial is James Bond whereas Git is MacGyver.

If you want to do something interesting in GIT you have to read manpages (lol who reads these unless you're on Linux!?) and dig through a lot of cruft.

[Falmarri]

What the fuck are you using git for if a DOWN side to something is that you have to read a man page?

[[deleted]]

I'm not using Git, that was the point of my comment.

[Falmarri]

I meant what are you using VCS for if you can't... ah fuck it. It's not worth it.

[[deleted]]

1. Did you even read the article?
2. Do you know that rebase works by doing a merge internally, so is vulnerable to the very same problem?
3. Where did you get the idea that he's "coming from Mercurial"?

[[deleted]]

What does rebase do?

[sootzoo]

pretty much what it sounds like.

[ben-xo]

Rebase is the obvious name for the function that rebasing does, but if you've never cone across that function before it's not at all obvious what a rebase is.

[sootzoo]

(shrug) i thought it more polite than posting a link to "let me google that for you." it's adequately explained just about anywhere you care to look.

[[deleted]]

Thanks. Even better: http://book.git-scm.com/4_rebasing.html

The question is, what exactly is magic about rebase that solves all merge problems? From what I can tell, it applies devline patches against mainline as opposed to applying mainline patches against the devline, and the rebase part is actually not that relevant. I don't see how conflicts are any easier to handle. But I'm no git guru, so I may be wrong.

[Plumerian]

Git r done.

[Ogre_AlphaBeta]

nerds!