Re: [PATCH 3/3] read-tree -m 3-way: handle more trivial merges internally

LT> Namely that read-tree doesn't have a frigging clue about renames, and LT> shouldn't have.

LT> But a real merge program _could_ have a frigging clue, and might notice LT> patterns like

LT> - file got modified in one branch, removed in the other LT> - a file got added in the other branch LT> - "Hey, that added file looks like the removed one!" LT> - Let's merge the modifications from the first branch into the move of LT> the second branch!

LT> Now, you can (validly) argue that you could still just look at the LT> original trees ("git-diff-tree -C $O $M") and grep for copies/movement and LT> do it by hand _there_ instead of looking at the result of the read-tree, LT> and you may well be right. So again, this is not a _fundamental_ problem, LT> although it's a bit more fundamental than the first one.

My knee-jerk reaction was "No, I would refuse to make that argument, because making the merge mechanism to examine trees itself would take us full-circle back to where we started [*1*]".

I agree we can, as the zeroth order approximation, run two "diff-tree -B --find-copies-harder -C" [*3*, *4*] on (O,A) and (O,B) pairs, and compare their output to cover the rename case [*2*] you described. I think we also can write a simple program that reads an unmerged index file and do the equivalent of these two diff-tree commands.

However, what I suspect to happen in practice is that the lines of development leading to A and B may have so much modification to those renamed or copied files since they forked at O that we may not recognize renames or copies as such by only looking at (O,A) and (O,B). In order to do a reasonable job while merging, we may end up needing to run "diff-tree --stdin -B -C" on the output of "rev-list O A" to fully follow the rename/copy trail [*5*].

What all this means is that the simple three-stage information read-tree -m gives us, which is about only three trees, might not be enough to handle renames and copies intelligently, when we need to deal with a pair of trees that have diverged for too long.

Once we go down this path, arguing against making "read-tree -m" results useless for such an intelligent merge logic (because it forces the merge logic to look at the trees and commits involved) ceases to make much sense, because such an intelligent merge logic needs to look at more than three trees _anyway_.

What "read-tree -m" gives us, while being very efficient, elegant and effective in "merge small and merge often" use pattern we recommend, may not be so useful to implement such an intelligent merge logic, and instead we would do better if we did it the hard way by inspecting individual commits. I do not have problem with that approach. It would be a much longer-term project, though.

So, yes I ended up arguing that the intelligent merge logic could and probably needs to look at the trees involved ;-).

Among the three-way cases, the only case I think that may make a practical difference is the case #5ALT, which deals with "a file added identically in both branches" case. This is what happens when a widely accepted patch has been applied independently to both trees recently (eh, "since they forked"). New files tend to get updated more often, and allowing the file to be locally modified, instead of failing the merge in read-tree phase, would help the workflow. If the file were modified in the user's repository, and checked in, then the current 3-way merge code cannot help the user that much, because we would be in !O && A && B && A!=B situation. I have a suspicion that we could probably help this case by looking at not just merge base but the edge commits as well.

I consider #14ALT an improvement, but at the same time I doubt that particular one would make much practical difference. It is more or less "while we are at it" kind of change. All others, including the "remove" cases (I botched -u but as you point out it is correctable), do not contribute to loosening the index requirements, but I suspect they might help me later unify two-way fast forward and three-way merge. Yes, I am still looking at "read-tree -m H I-mixed-with-H M" that emulates "read-tree H M".

[Footnotes]

*1* Remember merge-trees Perl script, which I did before you invented the multi-stage read-tree? Boy it feels like it was so distant past...

*2* A casual reader may notice that we are arguing about renames after both of us publicly stated that "renames do not matter". Here is a clarification. We both consider "recording renames at commit time" does not matter, but we do take "tracking and handling the renames" seriously. There is a difference.

*3* Oops.  There is not --find-copies-harder yet ;-).

*4* This would be further helped if we had a --show-rename-only diffcore filter. The operation is similar to the pickaxe, but it would prune changesets down only to renames and copies. I actually wrote and threw away such a filter back when I was trying to find good test cases in linux-2.6 repository.

*5* And the development line leading to A or B may not even be linear, in which case it may be easier to first decompose the chain between O and A into individual epochs. Jon Seymour's "rev-list --merge-order O A" would be very handy for this.