Re: Merge with git-pasky II.

(my apologies for responding to old messages, I only just subscribed to this list)

Linus Torvalds wrote:

The LCA for different files might be at different points in the history. Forcing them to all come from the same point produces very bad merges.

You're incorrect. Codeville does exactly that (history-aware merges which do the right thing even in cases where 3-way merge can't)

The Codeville merge algorithm is also quite simple, and is already implemented and mature.

If one person renames a file and another person modifies it then the changes should be applied to the moved file.

Also, there's the directory rename case where one person moves a directory and another person adds a file to it, in which case the file should be moved to the new directory location on merge. I gather than BK doesn't support this functionality, but Codeville and Monotone both do.

Nothing, not eveny our beloved BitKeeper, has 'move lines between files' functionality, and for good reason.

To begin with, it's behaviorally extremely dubious. It would be not uncommon for the system to erroneously think that some files deleted from one file were added to another, and then further changes down the line would cause random unrelated files to get modified in unpredictable ways when merges happened.

Also, it presents a completely unsolved UI problem. If one person moves lines 5-15 of file A to file B, and another person concurrently rewrites lines 10-20 of file A, how on earth is that supposed to be presented to the user? Codeville can support line moves *within* files just fine, but doesn't do it because of the UI problem of presenting all the corner cases. Maybe someday somebody will do a PhD thesis on that topic and we'll add it, but until then we're sticking with the basic functionality.

Honestly, that you would think of doing whole-tree three-way merges and even consider moving lines between files shows that you haven't explored the merge problem very deeply. This is a much harder problem than you think it is, and one which has already been solved by other systems.

-Bram

On Tue, 26 Apr 2005, Bram Cohen wrote:

Bzzt. Wrong answer.

The _right_ answer is "if one person moves a function, and another person modifies the function, the changes should be applied to the moved function".

Which is clearly a _much_ more common case than file renames.

In other words, if your algorithm doesn't handle the latter, then there is no point in handling the former either.

And _if_ your algorithm handles the latter, then there's no point in handling file renames specially, since the algorithm will have done that too, as a small part of it.

		Linus

   From: Linus Torvalds <torvalds@osdl.org>

   On Tue, 26 Apr 2005, Bram Cohen wrote:
   > 
   > If one person renames a file and another person modifies it then the
   > changes should be applied to the moved file.

   Bzzt. Wrong answer.

You're a little bit nuts, guy.

-t

Linus Torvalds wrote:

I'm trying to be polite. You're not making that easy.

Now that you're done being dismissive, could you either (a) rebut my quite detailed explanation of exactly why that functionality is both a dubious idea and difficult to implement, or (b) admit that you have no plans whatsoever for supporting any of this stuff? You can't have it both ways.

What I'd really like to hear is some explanation of why git is reimplementing all of this stuff from scratch. Your implicit claims that git will do more things than the other systems without having to reinvent all of their functionality first are, honestly, naive, ill-informed arrogance.

I'd like to reiterate that *nothing* out there supports moving lines between files, and further predict, with total confidence, that if git tries to support such functionality it will simply fail, either by giving up or creating a system which can behave horribly. Before you get all dismissive about this claim, please remember that I've spent years thinking about merge algorithms, and have actually designed and implemented them, and have spoken at length with other people who have done the same, while you've merely thought about them for a few weeks.

Even if we pretend that these are comparable features, that's far from clearly true. Function moves within a file occur more frequently, but a file rename moves *all* the functions within that file.

If someone offers you a dollar, no strings attached, do you turn them down because they didn't offer you ten?

In case these concepts got conflated, I'd like to point out that Codeville merge both supports renames *and* does better than three-way merge can do at merging a single, non-renamed file. In most cases three-way and codeville merge give the same answer, but there are some cases where there isn't a single appropriate LCA available, and in those cases codeville will do the right thing while three-way can't.

-Bram

  > What I'd really like to hear is some explanation of why git is
  > reimplementing all of this stuff from scratch.

Whatever Linus' reasons, it's not a bad exercise and it does help robustify the kernel project to roll its own. Not that he seems to be doing *this* part especially well or anything, but that doesn't matter from the perspective of the good reasons to do it.

It doesn't matter much -- get stuff into git and people can layer on that pretty gently. The low layers of git are a common idea but context and Linus' nifty code make this instance of the idea a bit of a gem.

  > please remember that I've spent years
  > thinking about merge algorithms

I'm surprised we haven't met sooner.  If we did and I forgot, sorry.

-t

On Tue, 26 Apr 2005, Bram Cohen wrote:

I'm absolutely not going to do it myself, you're right about that.

I just don't like your notion that you should support the 5% problem with ugly hacks, and then you dismiss the 95% problem with "nothing else does it either".

In other words, we're already merging manually for the 95%. Why do you think the 5% is so important?

Git does in ~5000 lines and two weeks of work what _I_ think is the right thing to do. You're welcome to disagree, but the fact is, people have whined and moaned about my use of BK FOR THREE YEARS without showing me any better alternatives.

So why are you complaining now, when I implement my own version in two weeks?

"no strings attached"?

There are lots of strings attached to the "follow renames" thing. There's 30 _years_ of strings attached, and they result in people not looking at the _interesting_ problem.

Exactly because people follow renames, they think that they have the history of the code, but then they ignore the fact that they don't - because it doesn't follow merging of code or splitting of code.

In other words, it's sometimes better to know that you don't know the answer, than it is to _think_ that you know the answer.

And I'd like to point out (again) that git doesn't actually care what merge strategy the user uses.

Me _personally_, I want to have something that is very repeatable and non-clever. Something I understand _or_ tells me that it can't do it. And quite frankly, merging single-file history _without_ taking all the other files' history into account makes me go "ugh".

That's why I like the "we do _not_ look for 'nearer' parents on a per-file basis", which is what this discussion started with, afaik. I think the only original source that makes sense is the least common parent for the whole _project_, exactly because other files have done things that may or may not depend on the history of the file you're merging.

I (and thus git) really takes a "whole project" approach. 

			Linus

On Tue, 26 Apr 2005, Linus Torvalds wrote:

Btw, I've also been pretty disgusted by SCM's apparently generally caring about stuff that is totally not relevant.

For example, it seems like most SCM people think that merging is about getting the end result of two conflicting patches right.

In my opinion, that's the _least_ important part of a merge. Maybe the kernel is very unusual in this, but basically true _conflicts_ are not only rare, but they tend to be things you want a human to look at regardless.

The important part of a merge is not how it handles conflicts (which need to be verified by a human anyway if they are at all interesting), but that it should meld the history together right so that you have a new solid base for future merges.

In other words, the important part is the _trivial_ part: the naming of the parents, and keeping track of their relationship. Not the clashes.

For example, CVS gets this part totally wrong. Sure, it can merge the contents, but it totally ignores the important part, so once you've done a merge, you're pretty much up shit creek wrt any subsequent merges in any other direction. All the other CVS problems pale in comparison. Renames? Just a detail.

And it looks like 99% of SCM people seem to think that the solution to that is to be more clever about content merges. Which misses the point entirely.

Don't get me wrong: content merges are nice, but they are _gravy_. They are not important. You can do them manually if you have to. What's important is that once you _have_ done them (manually or automatically), the system had better be able to go on, knowing that they've been done.

		Linus

Linus Torvalds wrote:

Now you're just being an ass. I stated, flatly, that what you're proposing to have done (by you or whoever, for feasibility it doesn't matter which) is not going to happen due to just plain difficulty. You obviously disagree with me, but rather than coming out and saying so you're pretending I didn't make that statement.

So you think that a system which supports snapshots and history but has no merging functionality whatsoever is the right thing? I'm asking this seriously. You have a magic --make-somebody-else-do-merge command, but for everybody else the current state of things is workable as a stopgap measure (the original plan) but very painful for anything more.

Codeville is comparable in terms of number of lines of code to Git, by the way.

You were happy with BitKeeper, so why should we? Monotone and Codeville are only just about now really mature, and you aren't exactly known as a model customer.

I'm trying to tell you that the amount of time between now and when a system as nice as BitKeeper is in use by the kernel can be dramatically reduced by either using an existing system verbatim or basing new efforts on one.

If you think that git as it exists right now is at all comparable to Monotone or Codeville you're completely delusional.

Now you've just gone off the deep end. This is an apples-to-apples comparison. Please accept one of thee following two statements:

(a) Git doesn't do merging, and none of the related new tools around it do merging.

(b) Codeville merge (sans rename functionality) would be superior for the merging which will be done.

-Bram

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Am Dienstag, 26. April 2005 23:28 schrieb Bram Cohen:

I have one very humble question:

Why don't you write and contribute some code for git to do good merging?

This would resolve all your problems.

I think the "magic-merge" command is quite exchangable and if your way works good and is compatible, then people will automatically start using that.

cu

Fabian
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.4 (GNU/Linux)

iD8DBQFCbrRdI0lSH7CXz7MRAkS4AJ9JEka71M0Zc6cizXhrYpHiKHhL0gCcD/3Q j+UnPU/cXafGjGG6Bt9mZE8= =IYk0 -----END PGP SIGNATURE-----

On Tue, 26 Apr 2005, Fabian Franz wrote:

Don't bother. Bram doesn't know what he's talking about. 

		Linus

On Tue, 26 Apr 2005, Bram Cohen wrote:

You haven't looked at git, have you?

Git already merges better than _any_ open-source SCM out there. It just does it so effortlessly that you didn't even realize it does that.

Today I've done four (count them) fully automated merges on the kernel tree: serial, networking, usb and arm.

And they took a fraction of a second (plus the download of the new objects, which is the real cost).

This is something that SVN _still_ cannot do, for example. 

		Linus

Dear diary, on Wed, Apr 27, 2005 at 12:25:58AM CEST, I got a letter where Linus Torvalds <torvalds@osdl.org> told me that...

Did you (or any other kernel developer reading this) actually try the Codeville merge? (I admit I didn't get time to do anything real with it yet.) SCM people keep praising it (as basically the best (at least open-source) merge out there), so it would be interesting to compare that with the actual real-world experience with it on the kernel.

I think SVN is just irrelevant here - it is a completely different league. The contenders here are probably Codeville, Monotone and perhaps GNU Arch offsprings.

El Tue, 26 Apr 2005 13:31:31 -0700 (PDT), Bram Cohen <bram@bitconjurer.org> escribió:

Renaming or moving files is _so_ rare and unusual that even not implementing it (like CVS) is hardly a big issue. Even in the linux kernel people moved subsystems around - OSS went from drivers/sound to /sound/oss in 2.6, and a USB subdirectory moved too, I think.

The patch got bigger. People wasted 30 seconds more of their life because the .gz file was bigger - who cares? If it's something it's going to happen every 5 years, I'd rather move them like CVS does rather than wasting a single second implementing file renaming/moving...

If something so uncommon like file renaming has been implemented, I don't see why people shouldn't implement something really useful like the thing linus proposes, in fact it doesn't looks like a bad idea at all (and you'd get file renaming for free, too). Perhaps it would be hard to implement and get right, but at least it would be _useful_.

On Tue, 26 Apr 2005, Linus Torvalds wrote:

I'd even go so far as to say that we need to have the user sign off on this. The modification is reasonably likely to not work in the new location, due to use of statics that aren't available or something of the sort.

I suspect that we want to report a conflict in the new location between the old version and the new version, and let the person merging check whether the change is okay. That is, both sides modified the same section at the same time: one side modified its content, while the other modified its location. We can give a good suggestion, but we need a final ruling.

	-Daniel
*This .sig left intentionally blank*