Moved files and merges

I currently have two klibc trees,

rsync://rsync.kernel.org/pub/scm/libs/klibc/klibc.git

and

rsync://rsync.kernel.org/pub/scm/libs/klibc/klibc-kbuild.git

One of the differences between the trees is that a bunch of files have been rearranged. Unfortunately, it seems that whenever I try to merge one into the other, using cg-update from the former branch to the latter, if any of these files have been touched, cg-update fails, and I have to:

- touch these files in the "old location" manually;
- manually apply the change to the new location (and, sad to say, I haven't even figured out how to take the numbers cg-update spits out and feed them to cg-diff);
- commit.

Is there any way I can record in the repository that these files are actually moved files, and that the merge should apply the patch elsewhere?

Thanks,

-hpa

Well, if you run pickaxe at merge-time on the file-paths that weren't found, you can probably walk the pickaxe output until you find the file move, and then reapply the patches.

Probably should be hacked into cg-merge. When the merge reports a file is missing, what happens? Does it leave a .rej file or anything?

cheers

martin

The error message is:

MERGE ERROR: nfsmount/mount.c: Not handling case 3225ecdf8d172cda2a6ea5276af0d3edc566a0e7 -> -> c02da9e576a525a2a49da930107ed3936a45b6e1 MERGE ERROR: nfsmount/sunrpc.c: Not handling case 037e33e84ebcee4e097a009439c1bab7143ef92d -> -> e2fe5f8b728b5235010ed317e759222179dcd45c

Conflicts during merge. Do cg-commit after resolving them.

-hpa

I cloned them to take a look. You_do_ seem to have a lot of renames.

    $ git clone .../klibc.git klibc
    $ cd klibc
    $ git fetch .../klibc-kbuild.git master:kbuild
    $ git diff -M --diff-filter=R -p kbuild..master |
      git apply --summary --stat

shows that there are 36 files moved around and there are not that much change overall between them.

Currently merge operation of git does not take any advantage of the rename/copy detection smarts from git-diff-* family. So the short answer to your question is unfortunately no.

Given that they are 'related' trees, and we have proper merge ancestry information ('git show-branch kbuild master' shows they were merged two commits before klibc's master branch, and kbuild's master has 8 or so commits since they last merged), we should be able to do better. Let me think about it a bit.

Well, I think I understand how your trees ancestry looks like, but still haven't come up with a good problem definition. I am sorry that this message is not a solution for your problem but would end up to be just my rambling and thinking aloud.

The ancestry looks like this:

       ----#4-#5---#7   #0: 1.0.14 released, next version is 1.0.15
      /      /              5691e96ebfccd21a1f75d3518dd55a96b311d1aa
     /---#1-#3---#6     #1: Explain why execvpe/execlpe work the way they do.
    //     /                1d774a8cbd8e8b90759491591987cb509122bd78
  #0-----#2             #2: 1.1 released, next version is 1.1.1
                            3a41b60f6730077db3f04cf2874c96a0e53da453
                        #3: Merge of #2 into #1
                            7ab38d71de2964129cf1d5bc4e071d103e807a0d
                        #4: socketcalls aren't always *.S files; they can...
                            f52be163e684fc3840e557ecf242270926136b67
                        #5: Merge of #3 into #4
                            2e2a79d62a96b6b0d4bc93697fe77cd3030cdfd9
                        #6: Warnings cleanup
                            f5260f8737517f19a03ee906cd64dfc9930221cd
                        #7: Remove obsoleted files from merge
                            59709a172ee58c9d529a8c4b6f5cf53460629cb3

and you are trying to merge #6 into #7 (or #7 into #6). #6 does not have usr/kinit and nfsmount at the top; #7 has nfsmount under usr/kinit/.

The merge base of #6 and #7 is #3. #3->#7 involves many renames like nfsmount/sunrpc.h -> usr/kinit/nfsmount/sunrpc.h, while #3->#6 involves no renames. This can be seen by

       $ git-diff-tree -M --diff-filter=R -r '#3' '#7' | wc -l

These renames are introduced by #5 merge, whose immediate ancestors are #3 and #4.

Now, there is a question. When you merge #6 and #7, development between #3 and #7 have a lot of renames, while #3 and #6 do not. What should this merge do? Should it follow the rename, and if so why?

Maybe I am trying to solve a wrong problem. First I thought there should be an automated way for merge to tell whether renames done in one branch should be ignored, but that may be better left under human control. By looking at #6, #7 and #3 alone, even with looking at #5 which introduced the renames, I do not see a good reason for the merge machinery to dictate that these renames are to be followed or ignored when merging #6 and #7.

So this is not what we ordinary call a 'merge', but what really is happening is something else . Let's say the tree you would want to end up with is 'similar' to #6 but contains the changes done on the branch leading to #7, except #7 has renames unwanted for moving #6 forward. Is that what we should be solving?

Then, I think we could do something along these lines, perhaps?

- Ask git-diff-tree about changes betwen #3 (merge-base) and #7.

        git-diff-tree -M --diff-filter=R -r '#3' '#7' |
        sed -e 's/^[^	]*	//' >.rename-tmp

This will give us list of <old-name> <new-name>, one pair on each line, separated with tabs.

- check out '#7', and move files around reversing the rename we found in the previous step. Make a throw-away tree out of it; we do not even have to have a commit.

git checkout -b junk7 '#7'
while read name3 name7
do
test -f $name7 || { echo $name7; continue; } git rename $name7 $name3
done <.rename-tmp tree7_sans_rename=$(git-write-tree)
git reset --hard junk7

- check out '#6', and run three-way merge like this.

	git checkout -b junk6 '#6'
        git-read-tree -m -u '#3' '#6' $tree7_sans_rename

- Notice I did not run merge-cache above. I suspect that #6 and #7 just have overlaps but there may be a lot of things missing from #7 that you would rather keep (I am not familiar with the relationship between these two projects, so I am just guessing). First let's see what is in the tree:

    $ git-ls-files --unmerged
    100644 450e5c7f5c4f4c90df8f60fc98b96cb7db25a502 1       MCONFIG
    100644 450e5c7f5c4f4c90df8f60fc98b96cb7db25a502 2       MCONFIG
    100644 41fdd07af8c4e3eebbafcc3ced8b361882fe4c0d 1       MRULES
    100644 41fdd07af8c4e3eebbafcc3ced8b361882fe4c0d 2       MRULES
    100644 521bf99c2ab1f647156bf16a7f977e951fb9cdb0 1       ash/Makefile
    100644 521bf99c2ab1f647156bf16a7f977e951fb9cdb0 2       ash/Makefile
    100644 66ba9bb16f8289dc8c1af7d1cd49e5f563b5f624 1       gzip/MCONFIG
    100644 66ba9bb16f8289dc8c1af7d1cd49e5f563b5f624 2       gzip/MCONFIG
    100644 d5f9f94be0795accd8b02e2743ab899ac7ca661e 1       gzip/Makefile
    100644 d5f9f94be0795accd8b02e2743ab899ac7ca661e 2       gzip/Makefile
    100644 472f09205986fd9c2f9c7da6e31b45cebb9fe0af 1       ipconfig/MCONFIG
    ...

Stage 1 is from #3, 2 is from #6, and these files does not exist in the faked sans-rename version of #7. I presume that you would want to keep them in #6, so we keep them without letting git-merge-cache to remove them by:

	git-ls-files --unmerged | cut -f2 | uniq |
        xargs git-update-cache --

This still may be slurping a lot of files that only exist in #7 but not in #6 in your cache (for example, I suspect you do not want to slurp usr/kinit/ into #6 with this 'merge'). You may need to remove them, using 'rm -f <file> && git-update-cache --remove <file>'.

- Then we merge-cache as usual.

git-merge-cache -o git-merge-one-file-script -a

Maybe I am missing something... but why should the merge operation ignore renames? Is there a merge case when ignoring renames is the Right Thing to do?

Lets say the branches A and B has the common ancestor C which contains a file named "foo". If A has renamed "foo" to "foobar" and B has made some content changes to "foo" shouldn't the result be a file named "foobar" with the content changes B made to "foo" in it?

As I see it when we rename 'foo' to 'foobar' we say that "this file should from now on be named 'foobar'". Furthermore, when we make some content changes to some file we say "this file should have this new content instead of its old content". In particular I do not think the user expresses an intent to keep the name of a file just because she makes some changes to its contents. So IMHO the merge of "this file should from now on be named 'foobar'" and "this file should have this new content instead of its old content" should be "this file should from now on be named 'foobar' and have this new content".

I think it is feasible to teach the merge machinery about those rename cases, it probably isn't trivial to implement but I certainly think it is possible. It may be the case that the user should be warned when such automatic merges involving renames are performed though.

- Fredrik

Our messages mostly crossed, but as I described in the longer message I just sent out, the problem is that two lines of development runs in parallel, each of them wants to pick criss-cross nonstructural changes from the other, while keeping their own tree structure. If the goal of a 'merge' is to converge into a single commit for both lines of development to agree on a single tree structure to carry on from, then what you said is right, but the problem at hand is slightly different.

Hi Junio.

Ican expalin some of the background for this particular merge. At about one month ago I cloned the current klibc.git tree and started doing the necessary modifications needed to introduce kbuild - the build system used in the kernel.
Futhermore we decided to move files around so they fit the directory structure planned to be used in the kernel - when we at one point in the future merged with mainline.
While I were modifying the build system the development continued and a few files saw some updates in the official klibc tree.

So what we want to do in this case is:
- Merge the kbuild changes into the official tree without loosing the changes made to renamed files.

On purpose I did not modify any of the renamed files so the klibc-kbuild tree contains renames only for these.

If it would be possible to merge:
libs/klibc/klibc.git and libs/klibc/sam/klibc-kbuild.git using the above rules it would be perfect.

Then a few of the patches from libs/klibc/klibc-kbuild.git would have to be applied again, but thats doable.

Anyway my view on it. Since Peter is the one doing the merge he may have better ideas.

Sam

This is a simplified scenario of klibc vs klibc-kbuild HPA had trouble with, to help us think of a way to solve this interesting merge problem.

	 #1 - #3 - #5 - #7
       /    /         /
    #0 - #2 - #4 - #6

There are two lines of developments. #0->#2 renames F to G and introduces K. #0->#1 keeps F as F and does not introduce K.

At commit #3, #2 is merged into #1. The changes made to the file contents of F between #0 and #2 are appreciated, but the renaming of F to G and introduction of K were not. So commit #3 has the resulting merge contents in F and does not have file K. This _might_ be different from what we traditionally consider a 'merge', but from the use case point of view it is a valid thing one would want to do.

Commit #4 is a continued development from #2; changes are made to G, and K has further changes. Commit #5 similarly is a continued development from #3; its changes are in F and K does not exist.

We are about to merge #6 into #5 to create #7. We should be able to take advantage of what the user did when the merge #3 was made; namely, we should be able to infer that the line of development that flows #0 .. #3 .. #7 prefers to keep F as F, and does not want the newly introduced K. We should be able to tell it by looking at what the merge #3 did.

Now, how can we use git to figure that out?

First, given our current head (#5) and the other head we are about to merge (#6), we need a way to tell if we merged from them before (i.e. the existence of #3) and if so the latest of such merge (i.e. #3).

The merge base between #5 and #6 is #2. We can look at commits between us (#5) and the merge base (#2), find a merge (#3), which has two parents. One of the parents is #2 which is reachable from #6, and the other is #1 which is not reachable from #6 but is reachable from #5. Can we say that this reliably tells us that #2 is on their side and #1 is on our side? Does the fact that #3 is the commit topologically closest to #5 tell us that #3 is the one we want to look deeper?

This is still handwaving, but assuming the answers to these questions are yes, we have found that the 'previous' merge is #3, that #1 is its parent on our side, and that #2 is its parent on their side.

Then we can ask 'diff-tree -M #2 #3' to see what tree structure changes we do _not_ want from their line of development, while slurping the contents changes from them. When making the tree to put at #7, just like I outlined to my previous message to HPA, we can first create a tree that is a derivative of #6 with only the structural changes detected between #2 and #3 (which are 'rename from G to F' and 'removal of K') applied. Similarly, we make another derivative, this time of #2, with only the structural changes to adjust it to 'our' tree (again, 'rename from G to F' and 'removal of K'). Then we can run 3-way git-read-tree like this:

    git-read-tree -m -u '#2-adjusted' '#5' '#6-adjusted'

The last part, using the structurally adjusted tree as the merge-base tree, is what I forgot to do in the previous message to HPA.

Hmm.

As explained in another mail what we want to do is actually to transpose the changes made to F to the now renamed file G. So we end up with G containing the modifications made to F.

Also we want to include the new file K.

So we end up with a new commit containing the renamed file with modifications and the new files too.

I hope this simplfies the usecase from a git perspective.

Sam

Thanks for the clarification. But the principles are the same.

Not the way I read your explanation.

Lets try to cook up an example:

Common ancestor looks like this:
foo/foo.c

Then we have two lines of parallel development dev-line-0 modifes foo/foo.c
dev-line-1 moves foo/foo.c to bar/bar.c
In addition dev-line-1 adds a second file bar/Makefile

So what should happen when we merge the two dev-lines? The resulting tree should look like this:
bar/bar.c (including the modifications down in dev-line-1 to foo.c bar/Makefile as added in dev-line-2

If this fits into your longer description - then yes this is the same principle. But I failed to see it fit, therefore this simple example.

If the problem is not fully understood it can be difficult to come up with the proper solution. And with the example above the problem should be really easy to understand.
Then we have the tree as used by hpa with a few more mergers in it. But the above is what was initial tried to do with the added complexity of a few more renames etc.

Sam

All true. Let's redraw that simplified scenario, and see if what I said still holds. It may be interesting to store my previous message and this one and run diff between them. I suspect that the main difference to come out would be the the problem description part and the merge machinery part would not be all that different.

------------
This is a simplified scenario of klibc vs klibc-kbuild HPA had trouble with, to help us think of a way to solve this interesting merge problem.

	 #1 - #3 - #5 - #7
       /    /         /
    #0 - #2 - #4 - #6

There are two lines of developments. #0->#1 renames F to G and introduces K. #0->#2 keeps F as F and does not introduce K.

At commit #3, #2 is merged into #1. The changes made to the file contents of F between #0 and #2 are appreciated, but we would also want to keep our decision to rename F to G and our new file K. So commit #3 has the resulting merge contents in G and has K, inherited from #1. This _might_ be different from what we traditionally consider a 'merge', but from the use case point of view it is a valid thing one would want to do.

I handwaved in my original message, but resolving this merge is not something git can help you mechanically; obviously it cannot decide if you want to keep the rename for you.

Commit #4 is a continued development from #2; changes are made to F, and there is no K. Commit #5 similarly is a continued development from #3; its changes are made to G and K also has further changes.

We are about to merge #6 into #5 to create #7. We should be able to take advantage of what the user did when the merge #3 was made; namely, we should be able to infer that the line of development that flows #0 .. #3 .. #7 prefers to rename F to G, and also wants the newly introduced K. We should be able to tell it by looking at what the merge #3 did.

Now, how can we use git to figure that out?

First, given our current head (#5) and the other head we are about to merge (#6), we need a way to tell if we merged from them before (i.e. the existence of #3) and if so the latest of such merge (i.e. #3).

The merge base between #5 and #6 is #2. We can look at commits between us (#5) and the merge base (#2), find a merge (#3), which has two parents. One of the parents is #2 which is reachable from #6, and the other is #1 which is not reachable from #6 but is reachable from #5. Can we say that this reliably tells us that #2 is on their side and #1 is on our side? Does the fact that #3 is the commit topologically closest to #5 tell us that #3 is the one we want to look deeper?

This is still handwaving, but assuming the answers to these questions are yes, we have found that the 'previous' merge is #3, that #1 is its parent on our side, and that #2 is its parent on their side.

Then we can ask 'diff-tree -M #2 #3' to see what tree structure non-changes we do _not_ want from their line of development, while slurping the contents changes from them. When making the tree to put at #7, just like I outlined to my previous message to HPA, we can first create a tree that is a derivative of #6 with only the structural changes detected between #2 and #3 (which are 'rename from F to G' and 'addition of K') applied. Here, applying 'addition of K' is only conceptual, unlike the original message you (Sam) had trouble with due to my misunderstanding of which line of development renames/adds. It is conceptual in the sense that we do not have to do anything special. #6-adjusted is different from #6 in that it has F's contents from #6 at G.

Similarly, we make another derivative, this time of #2, with only the structural changes to adjust it to 'our' tree (again, 'rename from F to G' and 'addition of K' which is only conceptual --- that is, #2-adjusted has contents of F from #2 at G). Then we can run 3-way git-read-tree like this:

    git-read-tree -m -u '#2-adjusted' '#5' '#6-adjusted'

The last part, using the structurally adjusted tree as the merge-base tree, is what I forgot to do in the previous message to HPA.

In all these three trees fed to read-tree, the original F (modified in two lines since #0 which had it at F) appears at F, so the normal 3-way merge machinery would work just fine. #2 does not have G (neither #2-adjusted), #5 does, and #6 does not (neither #6-adjusted), so again the ordinary 3-way merge machinery would pick up G from #5 and drop it in #7. That's why 'adjusting to our tree' for addition is only conceptual, unlike the removal and rename in the previous message.

So as I said, the principle is not that different.

Any volunteer to code this up and see how well it works in practice?

I'm not quite so convinced, because I think that the actual situation is a bit more natural, and therefore our expectations at the end should be closer to right with less attention to detail. But I think the actual situation is more interesting, anyway, because it's more likely to happen and we're more likely to be able to help.

I think this is actually quite a regular merge, and I think we should be able to offer some assistance. The situation with K is normal: case #3ALT. If someone introduces a file and there's no file or directory with that name in other trees, we assume that the merge should include it.

F/G is trickier, and I don't think we can actually do much about it with the current structure of read-tree/merge-cache/etc, but, theoretically, we should recognize that #0->#1 is a rename plus content changes, and #0->#2 is content changes, so the total should be the rename plus contents changes; I think we want to additionally signal a conflict, because there's a reasonable chance that the rename will interfere with the #0->#2 changes, and need intervention. Most likely, this just means that we should not commit automatically, but have the user test the result first.

For now, of course, we don't get renames at any point in the merging procedure, so our code can't tell, and sees it as a big conflict that the user has to deal with. But we can agree on what the result is if the user "includes all the changes from the other branch" (and see the situation you reported first as "cherry-picking" the content and leaving the structural changes).

Again, K should be unexceptional, because we're keeping a file that was added to one side but not the other. (In the other situation, it still works; relative to the common ancestor, we're in #8ALT, since #5 doesn't have K, which was in #2 and #6; we see the rejection in a merge as a removal, which is effectively the same.)

First off, it should handle K automatically, because we're still including a file added by one side without interference from the other side.

That's true, but we don't need to find and use #3; we can just use #5. The only difference is structural changes introduced between #3 and #5, and we presume we want those changes as well, unless they conflict with something. And if we don't look for #3, we can recognize the merge of #0, #1, and #2 as the same situation, with the same solution.

We already do the addition and non-addition (like removal) in read-tree. We could also handle renames there as well, although I can't quite picture an efficient code organization for it. Of course, read-tree is in flux at the moment, so making more structural changes to it at the same time is awkward.

In any case, I think that your algorithm is correct, except that you can use the sides of the present merge and the common ancestor, rather than looking for past merges, which aren't really relevant. (For that matter, there's no reason to believe that #1 and #5 are "part of the same line"; you'd get the same graph if #3 were merging some third party's restructuring, and 4 and 6 were a fork that started before the change and is being merged after it:

1
/ \
0-2-3-5-7
\ /

    4-6

It shouldn't matter to the merge at 7 if the 2-3 reorganization was done locally, by applying a patch, or by merging.

-Daniel
*This .sig left intentionally blank*

I was not particularly interested in discussing the initial merge, which is a perfectly regular merge as you said. I was more focusing on reusing the tree-structure change information we _could_ find in merge #3 when we make later merges, because that merge is something the user did in the past and would be a good guide for guessing what the user wants to happen to this round.

There is no question about K in 'keeping addition' case. It gets interesting only when the first merge prefered 'reject addition by them' and we would want to reuse that preference in the second merge. But as I tried to clarify in the "a couple of things worth mentioning" message, there is no fundamental reason to treat removal and addition any differently. It is just a way to reduce unnecessary conflicts.

No question about it again.

Doing this in read-tree is a bit premature. I'd prefer a scripted solution first to see what we want and how well it works in practice.

There was another problem in my message that treated #3 specially. I did it that way primarily because I wanted to have an algorithm that needs to look only limited (namely, one) number of commits, more than what we currently look at. The problem is that the trail #0..#1..#3 (in the example in second message, whose rename probably happened between #0 and #1) may change the contents of the renamed file so drastically that diff between #2 and #3 may not look like rename anymore, while we could still detect it if we followed the whole trail and looked for renames between each commit on it.

One question, of course, is if one should simply keep additional metadata around to handle this sort of situations. One could, for example, keep a UUID for each file, which would be carried over by the renaming commit. If one runs into a tree which doesn't have the UUIDs, they should be generated at that time (this could be a bit tricky to do without invalidating all signatures in the tree, since the obvious way -- adding it to the tree object -- would invalidate all the commit and tag objects.)

In some ways this is similar to the Unix filesystem model of separating location (pathname) from identity (device:inode).

It would also hade the somewhat interesting possibility that one could "remove and recreate" a file and have it exist as a different entity. That probably needs to be a user option.

-hpa

If I am not mistaken, that is exactly what tla does. It seems to work well in practice and seem so simple (at least superficially, I have not looked deeply into the issues involved in keeping it sync with the contents and how to recover if the user ever screws up, etc.), and I can see why people find it so attractive. I myself once did.

But previous argument by Linus made in a distant (in git timescale) past is now ingrained in my brain: "the additional metadata" recorded at the commit time can only help us what we envisioned in the past when the tool to record that metadata was written. If we try to "track" by contents, we can do at least the same (diff -M being able to tell renames is an example that we can get away without having a UUID) and possibly better, depending on how much effort we are willing to spend "drilling down" when we actually need to know what happened at merge time. What I found most important in that argument by Linus is that the "drilling down" algorithm can improve over time while "the additional metadata" specification is cast in stone when a commit is made.

... unless the "additional metadata" is merely a cache, derived from the contents. The advantage, of course, is that you can produce data that is more expensive that way. On the other hand, if you don't need it, it's pointless.

-hpa

It's a totally broken model. Really.

You think it solves issues, but it just creates more bugs and problems than it solves.

Trust me. The whole point of git is that "content is the only thing that matters", and that there isn't any other meta-data. If you break that fundamental assumption, everything git does so well will break.

I think we've already shown that the "content matters" approach works. I claim that the git rename tracking works better than any other SCM out there, _exactly_ because it doesn't make the mistake of trying to track anything but content.

The "moved + modified files" is not anything special. The current automatic merger may not handle it, but that's not because it _can't_ handle it, it's because it tries to be simple and efficient.

And because it's so _incredibly_ fast for all the normal cases, you can now spend some effort on figuring out renames dynamically for the few cases where it fails. Does it do so now? No. Would adding UUID's help? Hell no. It would be just an unmitigated disaster.

Exactly the same way "git-diff-tree" can figure out renames, a merge algorithm can figure them out.

Right now, we have two stages in merges: we try the trivial merge first (pure "git-read-tree"), and when that fails, we try the automatic 3-way merge. The fact that we don't have a third (and fourth, and fifth) merge algorithm for when those two trivial merges happen to not work is _not_ an indication that the "contents only" approach doesn't work - it's just an indication of the fact that 99.9% of all merges are trivial, and they should be optimized for.

So the next step is _not_ to do UUID's, it's to notice that merge errors happened, and try to figure out why. Right now we just give up and say "sort it out by hand". That's actually a perfectly valid approach even in the presense of moved files - it's a bit painful, but once you _do_ sort it out and commit the merge, especially if you can push the merge back (so that both sides then agree on the final rename), future merges will be trivial again - ie you won't have to go through it over and over again.

Of course, if you don't push it back, but keep the two trees separate and keep on modifying files that have different names in the other repository, you'll keep on getting into the situation that the trivial merge doesn't work. So we _do_ want to get an automated "phase 3" (and maybe 4..) merge that can figure out renames, but the point here is that it's something we _can_ figure out.

For example, one way of doing it is to just do the exact merge we do now, and then look at the files that didn't merge. Do a cross-diff between such files and new/deleted files (if not _exactly_ the way we do for "git diff -M", then at least it's exactly the same concept), and try to do a three-way merge where the base/first/second pairs don't have the same name.

For example, let's say that you have the common commit A, and file "x", and two paths (B and C) where B has renamed the file "x" to "y", and C has modified file "x". You end up with the schenario that our trivial merge fails to handle, and right now we give up, and don't help the user very much at all. But the _solution_ is not to change "read-tree" to know about renames, nor is it to make git keep any new data. The solution is to just make phase 3 say:

- "Automatic merge failed, trying rename merge"
- go through all files that exist in C but not in B (or vice versa), and pair them up with all files that exist in B but not in C (or vice versa) and see if _they_ can be handled as a three-way merge. And exactly the same way that we do the rename detection, we may want to find the "optimal pairing" by looking at the distance between the files.

Notice? This will automatically handle the "renamed in one branch, modified in another" case. In fact, if the renamer modified it too, that's not a problem at all - the three-way merge will work exactly the same way it does now with the case of a non-moved "modified in both" files.

Problem solved. Without complicating the trivial (and very common) cases, and without introducing any new metadata that is fundamentally impossible to maintain (and it _is_ fundamentally impossible to maintain, because it has nothing to do with the contents of the files, so patches etc will by definition break it).

Linus

Okay, how about keeping a cache (derived from the contents) of these types of data, to assist the merge if necessary? If it doesn't exist when needed, it can just be created, which may take O(n) time.

-hpa

Thanks. You very well said exactly what I should have said; I failed to explain where that reusing rename information from previous merge algorithm should fit in the bigger picture.

And the algorithm you describe (and Daniel briefly outlined) is slightly different from what I had in mind in that it does not have to depend on previous merge, which is also nice.

There are a couple of things worth mentioning about the two examples (one that I resolved favoring non-rename and non-addition, and the other I resolved favoring rename and addition) I gave tonight.

1. When I said "the principles are the same", I was primarily referring to the part that detects the 'previous' merge, which of its parents is 'ours' and which is 'theirs'. Although I handwaved that part in both examples, my gut feeling is that this part is probably harder than the part that adjusts trees before merging. klibc vs klibc-kbuild case had a clear distinction between which commit is ours and which is theirs, but I am not sure if things are that black and white in real projects when a lot of criss-crossing merges are involved.

2. When adjusting trees, I treated removals and additions a bit differently, but there is no fundamental reason to do so.

In the first example which had a removal, I adjusted the tree #2 and #6 by removing the path involved. In the second example which had an addition, I did not adjust the tree #2 and #6 to add that path. But you _could_ do nothing to adjust for removal; i.e. leaving K in tree #2-adjusted and #6-adjusted in the first example. Also you _could_ adjust for the addition by copying K from #3 into #2-adjusted and copying K from #5 into #6-adjusted in the second example.

If you did the former, merging the resulting #6-adjusted into #5 pivoting at #2-adjusted would leave a non-trivial conflict for you to resolve by hand. #6-adjusted changes K from #2-adjusted while #5 would remove it from #2-adjusted. This would be a remove-modify conflict (case 7 in the 3-way merge case table in t/t1000-read-tree-m-3way.sh). But this is only non-trivial to git and what you want is obvious to you as the maintainer of the line of development that removed the file at #3. You removed it the last time, and you remove it this time again. I adjusted #2 and #6 to remove the path only to save you from this tedium upfront before the read-tree phase.

Similarly, in the second example, if #2 and #6 are adjusted for the addition of K by copying K from #3 and #5 into them, the resulting merge would see that one line #2-adjusted to #6-adjusted changes K (whose contents is that of #3) to that of #5, while the other line #2-adjusted to #5 changes K (whose contents is again that of #3) to that of #5. Since this is both-change-identically (case 12 in the 3-way merge table), it trivially resolves to keep K from #5, and the result is the same as what you would get from my second example which did nothing about additions.

On Sat, Sep 03, 2005 at 11:46:53AM -0700, Junio C Hamano wrote:
[lots of good stuff]

I obviously misunderstood the complexity of this merge case. Thank you for the explanation.

- Fredrik