{"thread":{"id":"1719","subject":"Moved files and merges","startedAt":"2005-09-02T23:59:16Z","lastAt":"2005-09-05T18:43:00Z","messageCount":23,"participants":["H. Peter Anvin","Martin Langhoff","Junio C Hamano","Fredrik Kuivinen","Sam Ravnborg","Daniel Barkalow","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"8023","messageId":"4318E754.9000703@zytor.com","threadId":"1719","inReplyTo":null,"subject":"Moved files and merges","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2005-09-02T23:59:16Z","receivedAt":"2005-09-02T23:59:16Z","isPatch":false,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"I currently have two klibc trees,\n\nrsync://rsync.kernel.org/pub/scm/libs/klibc/klibc.git\n\nand\n\nrsync://rsync.kernel.org/pub/scm/libs/klibc/klibc-kbuild.git\n\n\nOne of the differences between the trees is that a bunch of files have \nbeen rearranged. Unfortunately, it seems that whenever I try to merge \none into the other, using cg-update from the former branch to the \nlatter, if any of these files have been touched, cg-update fails, and I \nhave to:\n\n- touch these files in the \"old location\" manually;\n- manually apply the change to the new location (and, sad to say, I \nhaven't even figured out how to take the numbers cg-update spits out and \nfeed them to cg-diff);\n- commit.\n\nIs there any way I can record in the repository that these files are \nactually moved files, and that the merge should apply the patch elsewhere?\n\nThanks,\n\n\t-hpa\n"},{"id":"8024","messageId":"46a038f90509021720417a9b59@mail.gmail.com","threadId":"1719","inReplyTo":"4318E754.9000703@zytor.com","subject":"Re: Moved files and merges","fromName":"Martin Langhoff","fromEmail":"martin.langhoff@gmail.com","sentAt":"2005-09-03T00:20:41Z","receivedAt":"2005-09-03T00:20:41Z","isPatch":false,"sender":{"key":"martin.langhoff@gmail.com","avatar":"https://gravatar.com/avatar/1e3f311b6c4c15836501901ca58f8c0b0667246488084ba524d8bc9867e22fd9?d=mp&s=160"},"body":"On 9/3/05, H. Peter Anvin wrote:\n> Is there any way I can record in the repository that these files are\n> actually moved files, and that the merge should apply the patch elsewhere?\n\nWell, if you run pickaxe at merge-time on the file-paths that weren't\nfound, you can probably walk the pickaxe output until you find the\nfile move, and then reapply the patches.\n\nProbably should be hacked into cg-merge. When the merge reports a file\nis missing, what happens? Does it leave a .rej file or anything?\n\ncheers\n\n\nmartin\n"},{"id":"8026","messageId":"7vek87djat.fsf@assigned-by-dhcp.cox.net","threadId":"1719","inReplyTo":"4318E754.9000703@zytor.com","subject":"Re: Moved files and merges","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-03T01:36:10Z","receivedAt":"2005-09-03T01:36:10Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"H. Peter Anvin\" writes:\n\n> I currently have two klibc trees,\n>\n> rsync://rsync.kernel.org/pub/scm/libs/klibc/klibc.git\n>\n> and\n>\n> rsync://rsync.kernel.org/pub/scm/libs/klibc/klibc-kbuild.git\n\nI cloned them to take a look. You_do_ seem to have a lot of\nrenames.\n\n $ git clone .../klibc.git klibc\n $ cd klibc\n $ git fetch .../klibc-kbuild.git master:kbuild\n $ git diff -M --diff-filter=R -p kbuild..master |\n git apply --summary --stat\n\nshows that there are 36 files moved around and there are not\nthat much change overall between them.\n\nCurrently merge operation of git does not take any advantage of\nthe rename/copy detection smarts from git-diff-* family. So\nthe short answer to your question is unfortunately no.\n\nGiven that they are 'related' trees, and we have proper merge\nancestry information ('git show-branch kbuild master' shows they\nwere merged two commits before klibc's master branch, and\nkbuild's master has 8 or so commits since they last merged), we\nshould be able to do better. Let me think about it a bit.\n"},{"id":"8034","messageId":"7vek867e29.fsf@assigned-by-dhcp.cox.net","threadId":"1719","inReplyTo":"7vek87djat.fsf@assigned-by-dhcp.cox.net","subject":"Re: Moved files and merges","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-03T08:25:50Z","receivedAt":"2005-09-03T08:25:50Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> \"H. Peter Anvin\" writes:\n>\n>> I currently have two klibc trees,\n>\n> I cloned them to take a look. You_do_ seem to have a lot of\n> renames.\n\nWell, I think I understand how your trees ancestry looks like,\nbut still haven't come up with a good problem definition. I am\nsorry that this message is not a solution for your problem but\nwould end up to be just my rambling and thinking aloud.\n\nThe ancestry looks like this:\n\n ----#4-#5---#7 #0: 1.0.14 released, next version is 1.0.15\n / / 5691e96ebfccd21a1f75d3518dd55a96b311d1aa\n /---#1-#3---#6 #1: Explain why execvpe/execlpe work the way they do.\n // / 1d774a8cbd8e8b90759491591987cb509122bd78\n #0-----#2 #2: 1.1 released, next version is 1.1.1\n 3a41b60f6730077db3f04cf2874c96a0e53da453\n #3: Merge of #2 into #1\n 7ab38d71de2964129cf1d5bc4e071d103e807a0d\n #4: socketcalls aren't always *.S files; they can...\n f52be163e684fc3840e557ecf242270926136b67\n #5: Merge of #3 into #4\n 2e2a79d62a96b6b0d4bc93697fe77cd3030cdfd9\n #6: Warnings cleanup\n f5260f8737517f19a03ee906cd64dfc9930221cd\n #7: Remove obsoleted files from merge\n 59709a172ee58c9d529a8c4b6f5cf53460629cb3\n\nand you are trying to merge #6 into #7 (or #7 into #6). #6 does\nnot have usr/kinit and nfsmount at the top; #7 has nfsmount\nunder usr/kinit/.\n\nThe merge base of #6 and #7 is #3. #3->#7 involves many renames\nlike nfsmount/sunrpc.h -> usr/kinit/nfsmount/sunrpc.h, while\n#3->#6 involves no renames. This can be seen by \n\n $ git-diff-tree -M --diff-filter=R -r '#3' '#7' | wc -l\n\nThese renames are introduced by #5 merge, whose immediate\nancestors are #3 and #4.\n\nNow, there is a question. When you merge #6 and #7, development\nbetween #3 and #7 have a lot of renames, while #3 and #6 do not.\nWhat should this merge do? Should it follow the rename, and if\nso why?\n\nMaybe I am trying to solve a wrong problem. First I thought\nthere should be an automated way for merge to tell whether\nrenames done in one branch should be ignored, but that may be\nbetter left under human control. By looking at #6, #7 and #3\nalone, even with looking at #5 which introduced the renames, I\ndo not see a good reason for the merge machinery to dictate that\nthese renames are to be followed or ignored when merging #6 and\n#7.\n\nSo this is not what we ordinary call a 'merge', but what really\nis happening is something else . Let's say the tree you would\nwant to end up with is 'similar' to #6 but contains the changes\ndone on the branch leading to #7, except #7 has renames unwanted\nfor moving #6 forward. Is that what we should be solving?\n\nThen, I think we could do something along these lines, perhaps?\n\n - Ask git-diff-tree about changes betwen #3 (merge-base) and\n #7.\n\n git-diff-tree -M --diff-filter=R -r '#3' '#7' |\n sed -e 's/^[^\t]*\t//' >.rename-tmp\n\n This will give us list of , one pair on\n each line, separated with tabs.\n\n - check out '#7', and move files around reversing the rename we\n found in the previous step. Make a throw-away tree out of it;\n we do not even have to have a commit.\n\n git checkout -b junk7 '#7'\n while read name3 name7\n do\n\t test -f $name7 || { echo $name7; continue; }\n\t git rename $name7 $name3\n done <.rename-tmp\n\ttree7_sans_rename=$(git-write-tree)\n\tgit reset --hard junk7\n\n - check out '#6', and run three-way merge like this.\n\n\tgit checkout -b junk6 '#6'\n git-read-tree -m -u '#3' '#6' $tree7_sans_rename\n\n - Notice I did not run merge-cache above. I suspect that #6\n and #7 just have overlaps but there may be a lot of things\n missing from #7 that you would rather keep (I am not familiar\n with the relationship between these two projects, so I am\n just guessing). First let's see what is in the tree:\n\n $ git-ls-files --unmerged\n 100644 450e5c7f5c4f4c90df8f60fc98b96cb7db25a502 1 MCONFIG\n 100644 450e5c7f5c4f4c90df8f60fc98b96cb7db25a502 2 MCONFIG\n 100644 41fdd07af8c4e3eebbafcc3ced8b361882fe4c0d 1 MRULES\n 100644 41fdd07af8c4e3eebbafcc3ced8b361882fe4c0d 2 MRULES\n 100644 521bf99c2ab1f647156bf16a7f977e951fb9cdb0 1 ash/Makefile\n 100644 521bf99c2ab1f647156bf16a7f977e951fb9cdb0 2 ash/Makefile\n 100644 66ba9bb16f8289dc8c1af7d1cd49e5f563b5f624 1 gzip/MCONFIG\n 100644 66ba9bb16f8289dc8c1af7d1cd49e5f563b5f624 2 gzip/MCONFIG\n 100644 d5f9f94be0795accd8b02e2743ab899ac7ca661e 1 gzip/Makefile\n 100644 d5f9f94be0795accd8b02e2743ab899ac7ca661e 2 gzip/Makefile\n 100644 472f09205986fd9c2f9c7da6e31b45cebb9fe0af 1 ipconfig/MCONFIG\n ...\n\n Stage 1 is from #3, 2 is from #6, and these files does not\n exist in the faked sans-rename version of #7. I presume that\n you would want to keep them in #6, so we keep them without\n letting git-merge-cache to remove them by:\n\n\tgit-ls-files --unmerged | cut -f2 | uniq |\n xargs git-update-cache --\n\n This still may be slurping a lot of files that only exist in\n #7 but not in #6 in your cache (for example, I suspect you do\n not want to slurp usr/kinit/ into #6 with this 'merge'). You\n may need to remove them, using 'rm -f &&\n git-update-cache --remove '.\n\n - Then we merge-cache as usual.\n\n\tgit-merge-cache -o git-merge-one-file-script -a\n \n"},{"id":"8036","messageId":"20050903180654.GB2314@c165.ib.student.liu.se","threadId":"1719","inReplyTo":"7vek867e29.fsf@assigned-by-dhcp.cox.net","subject":"Re: Moved files and merges","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-09-03T18:06:54Z","receivedAt":"2005-09-03T18:06:54Z","isPatch":false,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Sat, Sep 03, 2005 at 01:25:50AM -0700, Junio C Hamano wrote:\n> Junio C Hamano writes:\n> \n> > \"H. Peter Anvin\" writes:\n> >\n> >> I currently have two klibc trees,\n> >\n> > I cloned them to take a look. You_do_ seem to have a lot of\n> > renames.\n> \n> Well, I think I understand how your trees ancestry looks like,\n> but still haven't come up with a good problem definition. I am\n> sorry that this message is not a solution for your problem but\n> would end up to be just my rambling and thinking aloud.\n> \n> The ancestry looks like this:\n> \n> ----#4-#5---#7 #0: 1.0.14 released, next version is 1.0.15\n> / / 5691e96ebfccd21a1f75d3518dd55a96b311d1aa\n> /---#1-#3---#6 #1: Explain why execvpe/execlpe work the way they do.\n> // / 1d774a8cbd8e8b90759491591987cb509122bd78\n> #0-----#2 #2: 1.1 released, next version is 1.1.1\n> 3a41b60f6730077db3f04cf2874c96a0e53da453\n> #3: Merge of #2 into #1\n> 7ab38d71de2964129cf1d5bc4e071d103e807a0d\n> #4: socketcalls aren't always *.S files; they can...\n> f52be163e684fc3840e557ecf242270926136b67\n> #5: Merge of #3 into #4\n> 2e2a79d62a96b6b0d4bc93697fe77cd3030cdfd9\n> #6: Warnings cleanup\n> f5260f8737517f19a03ee906cd64dfc9930221cd\n> #7: Remove obsoleted files from merge\n> 59709a172ee58c9d529a8c4b6f5cf53460629cb3\n> \n> and you are trying to merge #6 into #7 (or #7 into #6). #6 does\n> not have usr/kinit and nfsmount at the top; #7 has nfsmount\n> under usr/kinit/.\n> \n> The merge base of #6 and #7 is #3. #3->#7 involves many renames\n> like nfsmount/sunrpc.h -> usr/kinit/nfsmount/sunrpc.h, while\n> #3->#6 involves no renames. This can be seen by \n> \n> $ git-diff-tree -M --diff-filter=R -r '#3' '#7' | wc -l\n> \n> These renames are introduced by #5 merge, whose immediate\n> ancestors are #3 and #4.\n> \n> Now, there is a question. When you merge #6 and #7, development\n> between #3 and #7 have a lot of renames, while #3 and #6 do not.\n> What should this merge do? Should it follow the rename, and if\n> so why?\n> \n\nMaybe I am missing something... but why should the merge operation\nignore renames? Is there a merge case when ignoring renames is the\nRight Thing to do?\n\nLets say the branches A and B has the common ancestor C which contains\na file named \"foo\". If A has renamed \"foo\" to \"foobar\" and B has made\nsome content changes to \"foo\" shouldn't the result be a file named\n\"foobar\" with the content changes B made to \"foo\" in it?\n\nAs I see it when we rename 'foo' to 'foobar' we say that \"this file\nshould from now on be named 'foobar'\". Furthermore, when we make some\ncontent changes to some file we say \"this file should have this new\ncontent instead of its old content\". In particular I do not think the\nuser expresses an intent to keep the name of a file just because she\nmakes some changes to its contents. So IMHO the merge of \"this file\nshould from now on be named 'foobar'\" and \"this file should have this\nnew content instead of its old content\" should be \"this file should\nfrom now on be named 'foobar' and have this new content\".\n\nI think it is feasible to teach the merge machinery about those rename\ncases, it probably isn't trivial to implement but I certainly think it\nis possible. It may be the case that the user should be warned when\nsuch automatic merges involving renames are performed though.\n\n\n- Fredrik\n"},{"id":"8037","messageId":"7vy86erntu.fsf@assigned-by-dhcp.cox.net","threadId":"1719","inReplyTo":"7vek867e29.fsf@assigned-by-dhcp.cox.net","subject":"Re: Moved files and merges","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-03T18:46:53Z","receivedAt":"2005-09-03T18:46:53Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This is a simplified scenario of klibc vs klibc-kbuild HPA had\ntrouble with, to help us think of a way to solve this\ninteresting merge problem.\n\n\t #1 - #3 - #5 - #7\n / / /\n #0 - #2 - #4 - #6\n\nThere are two lines of developments. #0->#2 renames F to G and\nintroduces K. #0->#1 keeps F as F and does not introduce K.\n\nAt commit #3, #2 is merged into #1. The changes made to the\nfile contents of F between #0 and #2 are appreciated, but the\nrenaming of F to G and introduction of K were not. So commit #3\nhas the resulting merge contents in F and does not have file K.\nThis _might_ be different from what we traditionally consider a\n'merge', but from the use case point of view it is a valid thing\none would want to do.\n\nCommit #4 is a continued development from #2; changes are made\nto G, and K has further changes. Commit #5 similarly is a\ncontinued development from #3; its changes are in F and K does\nnot exist.\n\nWe are about to merge #6 into #5 to create #7. We should be\nable to take advantage of what the user did when the merge #3\nwas made; namely, we should be able to infer that the line of\ndevelopment that flows #0 .. #3 .. #7 prefers to keep F as F,\nand does not want the newly introduced K. We should be able to\ntell it by looking at what the merge #3 did.\n\nNow, how can we use git to figure that out?\n\nFirst, given our current head (#5) and the other head we are\nabout to merge (#6), we need a way to tell if we merged from\nthem before (i.e. the existence of #3) and if so the latest of\nsuch merge (i.e. #3).\n\nThe merge base between #5 and #6 is #2. We can look at commits\nbetween us (#5) and the merge base (#2), find a merge (#3),\nwhich has two parents. One of the parents is #2 which is\nreachable from #6, and the other is #1 which is not reachable\nfrom #6 but is reachable from #5. Can we say that this reliably\ntells us that #2 is on their side and #1 is on our side? Does\nthe fact that #3 is the commit topologically closest to #5 tell\nus that #3 is the one we want to look deeper?\n\nThis is still handwaving, but assuming the answers to these\nquestions are yes, we have found that the 'previous' merge is\n#3, that #1 is its parent on our side, and that #2 is its parent\non their side.\n\nThen we can ask 'diff-tree -M #2 #3' to see what `tree\nstructure` changes we do _not_ want from their line of\ndevelopment, while slurping the contents changes from them.\nWhen making the tree to put at #7, just like I outlined to my\nprevious message to HPA, we can first create a tree that is a\nderivative of #6 with only the structural changes detected\nbetween #2 and #3 (which are 'rename from G to F' and 'removal\nof K') applied. Similarly, we make another derivative, this\ntime of #2, with only the structural changes to adjust it to\n'our' tree (again, 'rename from G to F' and 'removal of K').\nThen we can run 3-way git-read-tree like this:\n\n git-read-tree -m -u '#2-adjusted' '#5' '#6-adjusted'\n\nThe last part, using the structurally adjusted tree as the\nmerge-base tree, is what I forgot to do in the previous message\nto HPA.\n\nHmm.\n"},{"id":"8038","messageId":"7vslwmrnit.fsf@assigned-by-dhcp.cox.net","threadId":"1719","inReplyTo":"20050903180654.GB2314@c165.ib.student.liu.se","subject":"Re: Moved files and merges","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-03T18:53:30Z","receivedAt":"2005-09-03T18:53:30Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen writes:\n\n> Maybe I am missing something... but why should the merge operation\n> ignore renames? Is there a merge case when ignoring renames is the\n> Right Thing to do?\n>\n> Lets say the branches A and B has the common ancestor C which contains\n> a file named \"foo\". If A has renamed \"foo\" to \"foobar\" and B has made\n> some content changes to \"foo\" shouldn't the result be a file named\n> \"foobar\" with the content changes B made to \"foo\" in it?\n\nOur messages mostly crossed, but as I described in the longer\nmessage I just sent out, the problem is that two lines of\ndevelopment runs in parallel, each of them wants to pick\ncriss-cross nonstructural changes from the other, while keeping\ntheir own tree structure. If the goal of a 'merge' is to\nconverge into a single commit for both lines of development to\nagree on a single tree structure to carry on from, then what you\nsaid is right, but the problem at hand is slightly different.\n"},{"id":"8039","messageId":"20050903185912.GA8379@mars.ravnborg.org","threadId":"1719","inReplyTo":"7vek867e29.fsf@assigned-by-dhcp.cox.net","subject":"Re: Moved files and merges","fromName":"Sam Ravnborg","fromEmail":"sam@ravnborg.org","sentAt":"2005-09-03T18:59:13Z","receivedAt":"2005-09-03T18:59:13Z","isPatch":false,"sender":{"key":"sam@ravnborg.org","avatar":"https://gravatar.com/avatar/168a912606ed0742d840bb365e3cc21db390c36531a58341dc7a069cc1f15f62?d=mp&s=160"},"body":"On Sat, Sep 03, 2005 at 01:25:50AM -0700, Junio C Hamano wrote:\n> Junio C Hamano writes:\n> \n> > \"H. Peter Anvin\" writes:\n> >\n> >> I currently have two klibc trees,\n> >\n> > I cloned them to take a look. You_do_ seem to have a lot of\n> > renames.\n> \n> Well, I think I understand how your trees ancestry looks like,\n> but still haven't come up with a good problem definition. I am\n> sorry that this message is not a solution for your problem but\n> would end up to be just my rambling and thinking aloud.\n> \n> The ancestry looks like this:\n> \n> ----#4-#5---#7 #0: 1.0.14 released, next version is 1.0.15\n> / / 5691e96ebfccd21a1f75d3518dd55a96b311d1aa\n> /---#1-#3---#6 #1: Explain why execvpe/execlpe work the way they do.\n> // / 1d774a8cbd8e8b90759491591987cb509122bd78\n> #0-----#2 #2: 1.1 released, next version is 1.1.1\n> 3a41b60f6730077db3f04cf2874c96a0e53da453\n> #3: Merge of #2 into #1\n> 7ab38d71de2964129cf1d5bc4e071d103e807a0d\n> #4: socketcalls aren't always *.S files; they can...\n> f52be163e684fc3840e557ecf242270926136b67\n> #5: Merge of #3 into #4\n> 2e2a79d62a96b6b0d4bc93697fe77cd3030cdfd9\n> #6: Warnings cleanup\n> f5260f8737517f19a03ee906cd64dfc9930221cd\n> #7: Remove obsoleted files from merge\n> 59709a172ee58c9d529a8c4b6f5cf53460629cb3\n> \n> and you are trying to merge #6 into #7 (or #7 into #6). #6 does\n> not have usr/kinit and nfsmount at the top; #7 has nfsmount\n> under usr/kinit/.\n\n\nHi Junio.\n\nIcan expalin some of the background for this particular merge.\nAt about one month ago I cloned the current klibc.git tree and started\ndoing the necessary modifications needed to introduce kbuild - the\nbuild system used in the kernel.\nFuthermore we decided to move files around so they fit the directory\nstructure planned to be used in the kernel - when we at one point in the\nfuture merged with mainline.\nWhile I were modifying the build system the development continued and a\nfew files saw some updates in the official klibc tree.\n\nSo what we want to do in this case is:\n- Merge the kbuild changes into the official tree without loosing the\n changes made to renamed files.\n\nOn purpose I did not modify any of the renamed files so the klibc-kbuild\ntree contains renames only for these.\n\nIf it would be possible to merge:\nlibs/klibc/klibc.git and libs/klibc/sam/klibc-kbuild.git\nusing the above rules it would be perfect.\n\nThen a few of the patches from libs/klibc/klibc-kbuild.git would have to\nbe applied again, but thats doable.\n\nAnyway my view on it. Since Peter is the one doing the merge he may have\nbetter ideas.\n\n\tSam\n"},{"id":"8040","messageId":"20050903190500.GB8379@mars.ravnborg.org","threadId":"1719","inReplyTo":"7vy86erntu.fsf@assigned-by-dhcp.cox.net","subject":"Re: Moved files and merges","fromName":"Sam Ravnborg","fromEmail":"sam@ravnborg.org","sentAt":"2005-09-03T19:05:00Z","receivedAt":"2005-09-03T19:05:00Z","isPatch":false,"sender":{"key":"sam@ravnborg.org","avatar":"https://gravatar.com/avatar/168a912606ed0742d840bb365e3cc21db390c36531a58341dc7a069cc1f15f62?d=mp&s=160"},"body":"On Sat, Sep 03, 2005 at 11:46:53AM -0700, Junio C Hamano wrote:\n> This is a simplified scenario of klibc vs klibc-kbuild HPA had\n> trouble with, to help us think of a way to solve this\n> interesting merge problem.\n> \n> \t #1 - #3 - #5 - #7\n> / / /\n> #0 - #2 - #4 - #6\n> \n> There are two lines of developments. #0->#2 renames F to G and\n> introduces K. #0->#1 keeps F as F and does not introduce K.\n\nAs explained in another mail what we want to do is actually to\ntranspose the changes made to F to the now renamed file G.\nSo we end up with G containing the modifications made to F.\n\nAlso we want to include the new file K.\n\nSo we end up with a new commit containing the renamed file with\nmodifications and the new files too.\n\nI hope this simplfies the usecase from a git perspective.\n\n\tSam\n"},{"id":"8041","messageId":"20050903192137.GC2314@c165.ib.student.liu.se","threadId":"1719","inReplyTo":"7vy86erntu.fsf@assigned-by-dhcp.cox.net","subject":"Re: Moved files and merges","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-09-03T19:21:38Z","receivedAt":"2005-09-03T19:21:38Z","isPatch":false,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Sat, Sep 03, 2005 at 11:46:53AM -0700, Junio C Hamano wrote:\n[lots of good stuff]\n\nI obviously misunderstood the complexity of this merge case. Thank you\nfor the explanation. \n\n- Fredrik\n"},{"id":"8042","messageId":"7voe7arlqk.fsf@assigned-by-dhcp.cox.net","threadId":"1719","inReplyTo":"20050903190500.GB8379@mars.ravnborg.org","subject":"Re: Moved files and merges","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-03T19:32:03Z","receivedAt":"2005-09-03T19:32:03Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Sam Ravnborg writes:\n\n> As explained in another mail what we want to do is actually to\n> transpose the changes made to F to the now renamed file G.\n> So we end up with G containing the modifications made to F.\n>\n> Also we want to include the new file K.\n\nThanks for the clarification. But the principles are the same.\n"},{"id":"8043","messageId":"20050903220355.GA1895@mars.ravnborg.org","threadId":"1719","inReplyTo":"7voe7arlqk.fsf@assigned-by-dhcp.cox.net","subject":"Re: Moved files and merges","fromName":"Sam Ravnborg","fromEmail":"sam@ravnborg.org","sentAt":"2005-09-03T22:03:56Z","receivedAt":"2005-09-03T22:03:56Z","isPatch":false,"sender":{"key":"sam@ravnborg.org","avatar":"https://gravatar.com/avatar/168a912606ed0742d840bb365e3cc21db390c36531a58341dc7a069cc1f15f62?d=mp&s=160"},"body":"On Sat, Sep 03, 2005 at 12:32:03PM -0700, Junio C Hamano wrote:\n> Sam Ravnborg writes:\n> \n> > As explained in another mail what we want to do is actually to\n> > transpose the changes made to F to the now renamed file G.\n> > So we end up with G containing the modifications made to F.\n> >\n> > Also we want to include the new file K.\n> \n> Thanks for the clarification. But the principles are the same.\n\nNot the way I read your explanation.\n\nLets try to cook up an example:\n\nCommon ancestor looks like this:\nfoo/foo.c\n\nThen we have two lines of parallel development\ndev-line-0 modifes foo/foo.c\ndev-line-1 moves foo/foo.c to bar/bar.c\nIn addition dev-line-1 adds a second file bar/Makefile\n\nSo what should happen when we merge the two dev-lines?\nThe resulting tree should look like this:\nbar/bar.c (including the modifications down in dev-line-1 to foo.c\nbar/Makefile as added in dev-line-2\n\nIf this fits into your longer description - then yes this is the same\nprinciple. But I failed to see it fit, therefore this simple example.\n\nIf the problem is not fully understood it can be difficult to come up\nwith the proper solution. And with the example above the problem should\nbe really easy to understand.\nThen we have the tree as used by hpa with a few more mergers in it. But\nthe above is what was initial tried to do with the added complexity of a\nfew more renames etc.\n\n\tSam\n"},{"id":"8044","messageId":"431A749D.9090607@zytor.com","threadId":"1719","inReplyTo":"46a038f90509021720417a9b59@mail.gmail.com","subject":"Re: Moved files and merges","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2005-09-04T04:14:21Z","receivedAt":"2005-09-04T04:14:21Z","isPatch":false,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Martin Langhoff wrote:\n> \n> Probably should be hacked into cg-merge. When the merge reports a file\n> is missing, what happens? Does it leave a .rej file or anything?\n> \n\nThe error message is:\n\nMERGE ERROR: nfsmount/mount.c: Not handling case \n3225ecdf8d172cda2a6ea5276af0d3edc566a0e7 -> -> \nc02da9e576a525a2a49da930107ed3936a45b6e1\nMERGE ERROR: nfsmount/sunrpc.c: Not handling case \n037e33e84ebcee4e097a009439c1bab7143ef92d -> -> \ne2fe5f8b728b5235010ed317e759222179dcd45c\n\n Conflicts during merge. Do cg-commit after resolving them.\n\n\t-hpa\n"},{"id":"8045","messageId":"7v64thl248.fsf@assigned-by-dhcp.cox.net","threadId":"1719","inReplyTo":"20050903220355.GA1895@mars.ravnborg.org","subject":"Re: Moved files and merges","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-04T07:32:23Z","receivedAt":"2005-09-04T07:32:23Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Sam Ravnborg writes:\n\n> If the problem is not fully understood it can be difficult to come up\n> with the proper solution. And with the example above the problem should\n> be really easy to understand.\n> Then we have the tree as used by hpa with a few more mergers in it. But\n> the above is what was initial tried to do with the added complexity of a\n> few more renames etc.\n\nAll true. Let's redraw that simplified scenario, and see if\nwhat I said still holds. It may be interesting to store my\nprevious message and this one and run diff between them. I\nsuspect that the main difference to come out would be the the\nproblem description part and the merge machinery part would not\nbe all that different.\n\n------------\nThis is a simplified scenario of klibc vs klibc-kbuild HPA had\ntrouble with, to help us think of a way to solve this\ninteresting merge problem.\n\n\t #1 - #3 - #5 - #7\n / / /\n #0 - #2 - #4 - #6\n\nThere are two lines of developments. #0->#1 renames F to G and\nintroduces K. #0->#2 keeps F as F and does not introduce K.\n\nAt commit #3, #2 is merged into #1. The changes made to the\nfile contents of F between #0 and #2 are appreciated, but we\nwould also want to keep our decision to rename F to G and our\nnew file K. So commit #3 has the resulting merge contents in G\nand has K, inherited from #1. This _might_ be different from\nwhat we traditionally consider a 'merge', but from the use case\npoint of view it is a valid thing one would want to do.\n\nI handwaved in my original message, but resolving this merge is\nnot something git can help you mechanically; obviously it cannot\ndecide if you want to keep the rename for you.\n\nCommit #4 is a continued development from #2; changes are made\nto F, and there is no K. Commit #5 similarly is a continued\ndevelopment from #3; its changes are made to G and K also has\nfurther changes.\n\nWe are about to merge #6 into #5 to create #7. We should be\nable to take advantage of what the user did when the merge #3\nwas made; namely, we should be able to infer that the line of\ndevelopment that flows #0 .. #3 .. #7 prefers to rename F to G,\nand also wants the newly introduced K. We should be able to\ntell it by looking at what the merge #3 did.\n\nNow, how can we use git to figure that out?\n\nFirst, given our current head (#5) and the other head we are\nabout to merge (#6), we need a way to tell if we merged from\nthem before (i.e. the existence of #3) and if so the latest of\nsuch merge (i.e. #3).\n\nThe merge base between #5 and #6 is #2. We can look at commits\nbetween us (#5) and the merge base (#2), find a merge (#3),\nwhich has two parents. One of the parents is #2 which is\nreachable from #6, and the other is #1 which is not reachable\nfrom #6 but is reachable from #5. Can we say that this reliably\ntells us that #2 is on their side and #1 is on our side? Does\nthe fact that #3 is the commit topologically closest to #5 tell\nus that #3 is the one we want to look deeper?\n\nThis is still handwaving, but assuming the answers to these\nquestions are yes, we have found that the 'previous' merge is\n#3, that #1 is its parent on our side, and that #2 is its parent\non their side.\n\nThen we can ask 'diff-tree -M #2 #3' to see what `tree\nstructure` non-changes we do _not_ want from their line of\ndevelopment, while slurping the contents changes from them.\nWhen making the tree to put at #7, just like I outlined to my\nprevious message to HPA, we can first create a tree that is a\nderivative of #6 with only the structural changes detected\nbetween #2 and #3 (which are 'rename from F to G' and 'addition\nof K') applied. Here, applying 'addition of K' is only\nconceptual, unlike the original message you (Sam) had trouble\nwith due to my misunderstanding of which line of development\nrenames/adds. It is conceptual in the sense that we do not have\nto do anything special. #6-adjusted is different from #6 in\nthat it has F's contents from #6 at G.\n\nSimilarly, we make another derivative, this time of #2, with\nonly the structural changes to adjust it to 'our' tree (again,\n'rename from F to G' and 'addition of K' which is only\nconceptual --- that is, #2-adjusted has contents of F from #2 at\nG). Then we can run 3-way git-read-tree like this:\n\n git-read-tree -m -u '#2-adjusted' '#5' '#6-adjusted'\n\nThe last part, using the structurally adjusted tree as the\nmerge-base tree, is what I forgot to do in the previous message\nto HPA.\n\nIn all these three trees fed to read-tree, the original F\n(modified in two lines since #0 which had it at F) appears at F,\nso the normal 3-way merge machinery would work just fine. #2\ndoes not have G (neither #2-adjusted), #5 does, and #6 does not\n(neither #6-adjusted), so again the ordinary 3-way merge\nmachinery would pick up G from #5 and drop it in #7. That's why\n'adjusting to our tree' for addition is only conceptual, unlike\nthe removal and rename in the previous message.\n\nSo as I said, the principle is not that different.\n\nAny volunteer to code this up and see how well it works in\npractice?\n"},{"id":"8046","messageId":"7vfysli6g3.fsf@assigned-by-dhcp.cox.net","threadId":"1719","inReplyTo":"20050903220355.GA1895@mars.ravnborg.org","subject":"Re: Moved files and merges","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-04T08:27:08Z","receivedAt":"2005-09-04T08:27:08Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n> All true. Let's redraw that simplified scenario, and see if\n> what I said still holds. It may be interesting to store my\n> previous message and this one in a file and run diff between\n> them.\n\nThere are a couple of things worth mentioning about the two\nexamples (one that I resolved favoring non-rename and\nnon-addition, and the other I resolved favoring rename and\naddition) I gave tonight.\n\n1. When I said \"the principles are the same\", I was primarily\n referring to the part that detects the 'previous' merge,\n which of its parents is 'ours' and which is 'theirs'.\n Although I handwaved that part in both examples, my gut\n feeling is that this part is probably harder than the part\n that adjusts trees before merging. klibc vs klibc-kbuild\n case had a clear distinction between which commit is ours and\n which is theirs, but I am not sure if things are that black\n and white in real projects when a lot of criss-crossing\n merges are involved.\n\n2. When adjusting trees, I treated removals and additions a bit\n differently, but there is no fundamental reason to do so.\n\n In the first example which had a removal, I adjusted the tree\n #2 and #6 by removing the path involved. In the second\n example which had an addition, I did not adjust the tree #2\n and #6 to add that path. But you _could_ do nothing to\n adjust for removal; i.e. leaving K in tree #2-adjusted and\n #6-adjusted in the first example. Also you _could_ adjust for\n the addition by copying K from #3 into #2-adjusted and\n copying K from #5 into #6-adjusted in the second example.\n\n If you did the former, merging the resulting #6-adjusted into\n #5 pivoting at #2-adjusted would leave a non-trivial conflict\n for you to resolve by hand. #6-adjusted changes K from\n #2-adjusted while #5 would remove it from #2-adjusted. This\n would be a remove-modify conflict (case 7 in the 3-way merge\n case table in t/t1000-read-tree-m-3way.sh). But this is only\n non-trivial to git and what you want is obvious to you as the\n maintainer of the line of development that removed the file\n at #3. You removed it the last time, and you remove it this\n time again. I adjusted #2 and #6 to remove the path only to\n save you from this tedium upfront before the read-tree phase.\n\n Similarly, in the second example, if #2 and #6 are adjusted\n for the addition of K by copying K from #3 and #5 into them,\n the resulting merge would see that one line #2-adjusted to\n #6-adjusted changes K (whose contents is that of\n #3) to that of #5, while the other line #2-adjusted to #5\n changes K (whose contents is again that of #3) to that of\n #5. Since this is both-change-identically (case 12 in the\n 3-way merge table), it trivially resolves to keep K from #5,\n and the result is the same as what you would get from my\n second example which did nothing about additions.\n\n\n\n \n"},{"id":"8060","messageId":"Pine.LNX.4.63.0509041329340.23242@iabervon.org","threadId":"1719","inReplyTo":"7v64thl248.fsf@assigned-by-dhcp.cox.net","subject":"Re: Moved files and merges","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-09-04T18:28:27Z","receivedAt":"2005-09-04T18:28:27Z","isPatch":false,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Sun, 4 Sep 2005, Junio C Hamano wrote:\n\n> Sam Ravnborg writes:\n> \n> > If the problem is not fully understood it can be difficult to come up\n> > with the proper solution. And with the example above the problem should\n> > be really easy to understand.\n> > Then we have the tree as used by hpa with a few more mergers in it. But\n> > the above is what was initial tried to do with the added complexity of a\n> > few more renames etc.\n> \n> All true. Let's redraw that simplified scenario, and see if\n> what I said still holds. It may be interesting to store my\n> previous message and this one and run diff between them. I\n> suspect that the main difference to come out would be the the\n> problem description part and the merge machinery part would not\n> be all that different.\n\nI'm not quite so convinced, because I think that the actual situation is a \nbit more natural, and therefore our expectations at the end should be \ncloser to right with less attention to detail. But I think the actual \nsituation is more interesting, anyway, because it's more likely to happen \nand we're more likely to be able to help.\n\n> ------------\n> This is a simplified scenario of klibc vs klibc-kbuild HPA had\n> trouble with, to help us think of a way to solve this\n> interesting merge problem.\n> \n> \t #1 - #3 - #5 - #7\n> / / /\n> #0 - #2 - #4 - #6\n> \n> There are two lines of developments. #0->#1 renames F to G and\n> introduces K. #0->#2 keeps F as F and does not introduce K.\n> \n> At commit #3, #2 is merged into #1. The changes made to the\n> file contents of F between #0 and #2 are appreciated, but we\n> would also want to keep our decision to rename F to G and our\n> new file K. So commit #3 has the resulting merge contents in G\n> and has K, inherited from #1. This _might_ be different from\n> what we traditionally consider a 'merge', but from the use case\n> point of view it is a valid thing one would want to do.\n\nI think this is actually quite a regular merge, and I think we should be \nable to offer some assistance. The situation with K is normal: case #3ALT. \nIf someone introduces a file and there's no file or directory with that \nname in other trees, we assume that the merge should include it.\n\nF/G is trickier, and I don't think we can actually do much about it with \nthe current structure of read-tree/merge-cache/etc, but, theoretically, we \nshould recognize that #0->#1 is a rename plus content changes, and #0->#2 \nis content changes, so the total should be the rename plus contents \nchanges; I think we want to additionally signal a conflict, because \nthere's a reasonable chance that the rename will interfere with the #0->#2 \nchanges, and need intervention. Most likely, this just means that we \nshould not commit automatically, but have the user test the result first.\n\nFor now, of course, we don't get renames at any point in the merging \nprocedure, so our code can't tell, and sees it as a big conflict that the \nuser has to deal with. But we can agree on what the result is if the user \n\"includes all the changes from the other branch\" (and see the situation \nyou reported first as \"cherry-picking\" the content and leaving the \nstructural changes).\n\n> Commit #4 is a continued development from #2; changes are made\n> to F, and there is no K. Commit #5 similarly is a continued\n> development from #3; its changes are made to G and K also has\n> further changes.\n> \n> We are about to merge #6 into #5 to create #7. We should be\n> able to take advantage of what the user did when the merge #3\n> was made; namely, we should be able to infer that the line of\n> development that flows #0 .. #3 .. #7 prefers to rename F to G,\n> and also wants the newly introduced K. We should be able to\n> tell it by looking at what the merge #3 did.\n\nAgain, K should be unexceptional, because we're keeping a file that was \nadded to one side but not the other. (In the other situation, it still \nworks; relative to the common ancestor, we're in #8ALT, since #5 doesn't \nhave K, which was in #2 and #6; we see the rejection in a merge as a \nremoval, which is effectively the same.)\n\n> Now, how can we use git to figure that out?\n\nFirst off, it should handle K automatically, because we're still including \na file added by one side without interference from the other side.\n\n> First, given our current head (#5) and the other head we are\n> about to merge (#6), we need a way to tell if we merged from\n> them before (i.e. the existence of #3) and if so the latest of\n> such merge (i.e. #3).\n> \n> The merge base between #5 and #6 is #2. We can look at commits\n> between us (#5) and the merge base (#2), find a merge (#3),\n> which has two parents. One of the parents is #2 which is\n> reachable from #6, and the other is #1 which is not reachable\n> from #6 but is reachable from #5. Can we say that this reliably\n> tells us that #2 is on their side and #1 is on our side? Does\n> the fact that #3 is the commit topologically closest to #5 tell\n> us that #3 is the one we want to look deeper?\n> \n> This is still handwaving, but assuming the answers to these\n> questions are yes, we have found that the 'previous' merge is\n> #3, that #1 is its parent on our side, and that #2 is its parent\n> on their side.\n> \n> Then we can ask 'diff-tree -M #2 #3' to see what `tree\n> structure` non-changes we do _not_ want from their line of\n> development, while slurping the contents changes from them.\n> When making the tree to put at #7, just like I outlined to my\n> previous message to HPA, we can first create a tree that is a\n> derivative of #6 with only the structural changes detected\n> between #2 and #3 (which are 'rename from F to G' and 'addition\n> of K') applied. Here, applying 'addition of K' is only\n> conceptual, unlike the original message you (Sam) had trouble\n> with due to my misunderstanding of which line of development\n> renames/adds. It is conceptual in the sense that we do not have\n> to do anything special. #6-adjusted is different from #6 in\n> that it has F's contents from #6 at G.\n\nThat's true, but we don't need to find and use #3; we can just use #5. The \nonly difference is structural changes introduced between #3 and #5, and we \npresume we want those changes as well, unless they conflict with \nsomething. And if we don't look for #3, we can recognize the merge of #0, \n#1, and #2 as the same situation, with the same solution.\n\n> Similarly, we make another derivative, this time of #2, with\n> only the structural changes to adjust it to 'our' tree (again,\n> 'rename from F to G' and 'addition of K' which is only\n> conceptual --- that is, #2-adjusted has contents of F from #2 at\n> G). Then we can run 3-way git-read-tree like this:\n> \n> git-read-tree -m -u '#2-adjusted' '#5' '#6-adjusted'\n> \n> The last part, using the structurally adjusted tree as the\n> merge-base tree, is what I forgot to do in the previous message\n> to HPA.\n> \n> In all these three trees fed to read-tree, the original F\n> (modified in two lines since #0 which had it at F) appears at F,\n> so the normal 3-way merge machinery would work just fine. #2\n> does not have G (neither #2-adjusted), #5 does, and #6 does not\n> (neither #6-adjusted), so again the ordinary 3-way merge\n> machinery would pick up G from #5 and drop it in #7. That's why\n> 'adjusting to our tree' for addition is only conceptual, unlike\n> the removal and rename in the previous message.\n> \n> So as I said, the principle is not that different.\n\nWe already do the addition and non-addition (like removal) in read-tree. \nWe could also handle renames there as well, although I can't quite picture \nan efficient code organization for it. Of course, read-tree is in flux at \nthe moment, so making more structural changes to it at the same time is \nawkward.\n\nIn any case, I think that your algorithm is correct, except that you can \nuse the sides of the present merge and the common ancestor, rather than \nlooking for past merges, which aren't really relevant. (For that matter, \nthere's no reason to believe that #1 and #5 are \"part of the same line\"; \nyou'd get the same graph if #3 were merging some third party's \nrestructuring, and 4 and 6 were a fork that started before the change and \nis being merged after it:\n\n 1\n / \\\n0-2-3-5-7\n \\ /\n 4-6\n\nIt shouldn't matter to the merge at 7 if the 2-3 reorganization was done \nlocally, by applying a patch, or by merging.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"8063","messageId":"7vvf1gejjf.fsf@assigned-by-dhcp.cox.net","threadId":"1719","inReplyTo":"Pine.LNX.4.63.0509041329340.23242@iabervon.org","subject":"Re: Moved files and merges","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-04T19:10:12Z","receivedAt":"2005-09-04T19:10:12Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Daniel Barkalow writes:\n\n> I think this is actually quite a regular merge, and I think we should be \n> able to offer some assistance. The situation with K is normal: case #3ALT. \n> If someone introduces a file and there's no file or directory with that \n> name in other trees, we assume that the merge should include it.\n\nI was not particularly interested in discussing the initial\nmerge, which is a perfectly regular merge as you said. I was\nmore focusing on reusing the tree-structure change information\nwe _could_ find in merge #3 when we make later merges, because\nthat merge is something the user did in the past and would be a\ngood guide for guessing what the user wants to happen to this\nround.\n\nThere is no question about K in 'keeping addition' case. It\ngets interesting only when the first merge prefered 'reject\naddition by them' and we would want to reuse that preference in\nthe second merge. But as I tried to clarify in the \"a couple of\nthings worth mentioning\" message, there is no fundamental reason\nto treat removal and addition any differently. It is just a way\nto reduce unnecessary conflicts.\n\n> Most likely, this just means that we \n> should not commit automatically, but have the user test the result first.\n\nNo question about it again.\n\n> Of course, read-tree is in flux at \n> the moment, so making more structural changes to it at the same time is \n> awkward.\n\nDoing this in read-tree is a bit premature. I'd prefer a\nscripted solution first to see what we want and how well it\nworks in practice.\n\n> 1\n> / \\\n> 0-2-3-5-7\n> \\ /\n> 4-6\n>\n> It shouldn't matter to the merge at 7 if the 2-3 reorganization was done \n> locally, by applying a patch, or by merging.\n\nThere was another problem in my message that treated #3\nspecially. I did it that way primarily because I wanted to have\nan algorithm that needs to look only limited (namely, one)\nnumber of commits, more than what we currently look at. The\nproblem is that the trail #0..#1..#3 (in the example in second\nmessage, whose rename probably happened between #0 and #1) may\nchange the contents of the renamed file so drastically that diff\nbetween #2 and #3 may not look like rename anymore, while we\ncould still detect it if we followed the whole trail and looked\nfor renames between each commit on it.\n"},{"id":"8089","messageId":"431C6167.4070703@zytor.com","threadId":"1719","inReplyTo":"7vvf1gejjf.fsf@assigned-by-dhcp.cox.net","subject":"Re: Moved files and merges","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2005-09-05T15:16:55Z","receivedAt":"2005-09-05T15:16:55Z","isPatch":false,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Junio C Hamano wrote:\n> \n>> 1\n>> / \\\n>>0-2-3-5-7\n>> \\ /\n>> 4-6\n>>\n>>It shouldn't matter to the merge at 7 if the 2-3 reorganization was done \n>>locally, by applying a patch, or by merging.\n> \n> \n> There was another problem in my message that treated #3\n> specially. I did it that way primarily because I wanted to have\n> an algorithm that needs to look only limited (namely, one)\n> number of commits, more than what we currently look at. The\n> problem is that the trail #0..#1..#3 (in the example in second\n> message, whose rename probably happened between #0 and #1) may\n> change the contents of the renamed file so drastically that diff\n> between #2 and #3 may not look like rename anymore, while we\n> could still detect it if we followed the whole trail and looked\n> for renames between each commit on it.\n> \n\nOne question, of course, is if one should simply keep additional \nmetadata around to handle this sort of situations. One could, for \nexample, keep a UUID for each file, which would be carried over by the \nrenaming commit. If one runs into a tree which doesn't have the UUIDs, \nthey should be generated at that time (this could be a bit tricky to do \nwithout invalidating all signatures in the tree, since the obvious way \n-- adding it to the tree object -- would invalidate all the commit and \ntag objects.)\n\nIn some ways this is similar to the Unix filesystem model of separating \nlocation (pathname) from identity (device:inode).\n\nIt would also hade the somewhat interesting possibility that one could \n\"remove and recreate\" a file and have it exist as a different entity. \nThat probably needs to be a user option.\n\n\t-hpa\n"},{"id":"8092","messageId":"Pine.LNX.4.58.0509050825170.3568@evo.osdl.org","threadId":"1719","inReplyTo":"431C6167.4070703@zytor.com","subject":"Re: Moved files and merges","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-09-05T15:47:40Z","receivedAt":"2005-09-05T15:47:40Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 5 Sep 2005, H. Peter Anvin wrote:\n> \n> It would also hade the somewhat interesting possibility that one could \n> \"remove and recreate\" a file and have it exist as a different entity. \n> That probably needs to be a user option.\n\nIt's a totally broken model. Really.\n\nYou think it solves issues, but it just creates more bugs and problems \nthan it solves.\n\nTrust me. The whole point of git is that \"content is the only thing that \nmatters\", and that there isn't any other meta-data. If you break that \nfundamental assumption, everything git does so well will break. \n\nI think we've already shown that the \"content matters\" approach works. I\nclaim that the git rename tracking works better than any other SCM out \nthere, _exactly_ because it doesn't make the mistake of trying to track \nanything but content.\n\nThe \"moved + modified files\" is not anything special. The current \nautomatic merger may not handle it, but that's not because it _can't_ \nhandle it, it's because it tries to be simple and efficient. \n\nAnd because it's so _incredibly_ fast for all the normal cases, you can \nnow spend some effort on figuring out renames dynamically for the few \ncases where it fails. Does it do so now? No. Would adding UUID's help? \nHell no. It would be just an unmitigated disaster.\n\nExactly the same way \"git-diff-tree\" can figure out renames, a merge \nalgorithm can figure them out. \n\nRight now, we have two stages in merges: we try the trivial merge first\n(pure \"git-read-tree\"), and when that fails, we try the automatic 3-way\nmerge. The fact that we don't have a third (and fourth, and fifth) merge\nalgorithm for when those two trivial merges happen to not work is _not_ an\nindication that the \"contents only\" approach doesn't work - it's just an\nindication of the fact that 99.9% of all merges are trivial, and they\nshould be optimized for.\n\nSo the next step is _not_ to do UUID's, it's to notice that merge errors \nhappened, and try to figure out why. Right now we just give up and say \n\"sort it out by hand\". That's actually a perfectly valid approach even in \nthe presense of moved files - it's a bit painful, but once you _do_ sort \nit out and commit the merge, especially if you can push the merge back (so \nthat both sides then agree on the final rename), future merges will be \ntrivial again - ie you won't have to go through it over and over again.\n\nOf course, if you don't push it back, but keep the two trees separate and \nkeep on modifying files that have different names in the other repository, \nyou'll keep on getting into the situation that the trivial merge doesn't \nwork. So we _do_ want to get an automated \"phase 3\" (and maybe 4..) merge \nthat can figure out renames, but the point here is that it's something we \n_can_ figure out.\n\nFor example, one way of doing it is to just do the exact merge we do now,\nand then look at the files that didn't merge. Do a cross-diff between such\nfiles and new/deleted files (if not _exactly_ the way we do for \"git diff\n-M\", then at least it's exactly the same concept), and try to do a\nthree-way merge where the base/first/second pairs don't have the same\nname.\n\nFor example, let's say that you have the common commit A, and file \"x\",\nand two paths (B and C) where B has renamed the file \"x\" to \"y\", and C has\nmodified file \"x\". You end up with the schenario that our trivial merge\nfails to handle, and right now we give up, and don't help the user very\nmuch at all. But the _solution_ is not to change \"read-tree\" to know about\nrenames, nor is it to make git keep any new data. The solution is to just \nmake phase 3 say:\n\n - \"Automatic merge failed, trying rename merge\"\n - go through all files that exist in C but not in B (or vice versa), and \n pair them up with all files that exist in B but not in C (or vice\n versa) and see if _they_ can be handled as a three-way merge. And \n exactly the same way that we do the rename detection, we may want to\n find the \"optimal pairing\" by looking at the distance between the\n files.\n\nNotice? This will automatically handle the \"renamed in one branch, \nmodified in another\" case. In fact, if the renamer modified it too, that's \nnot a problem at all - the three-way merge will work exactly the same way \nit does now with the case of a non-moved \"modified in both\" files.\n\nProblem solved. Without complicating the trivial (and very common) cases, \nand without introducing any new metadata that is fundamentally impossible \nto maintain (and it _is_ fundamentally impossible to maintain, because it \nhas nothing to do with the contents of the files, so patches etc will by \ndefinition break it).\n\n\t\tLinus\n"},{"id":"8097","messageId":"431C7456.80907@zytor.com","threadId":"1719","inReplyTo":"Pine.LNX.4.58.0509050825170.3568@evo.osdl.org","subject":"Re: Moved files and merges","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2005-09-05T16:37:42Z","receivedAt":"2005-09-05T16:37:42Z","isPatch":false,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Linus Torvalds wrote:\n> \n> It's a totally broken model. Really.\n> \n> You think it solves issues, but it just creates more bugs and problems \n> than it solves.\n> \n> Trust me. The whole point of git is that \"content is the only thing that \n> matters\", and that there isn't any other meta-data. If you break that \n> fundamental assumption, everything git does so well will break. \n> \n> I think we've already shown that the \"content matters\" approach works. I\n> claim that the git rename tracking works better than any other SCM out \n> there, _exactly_ because it doesn't make the mistake of trying to track \n> anything but content.\n> \n> The \"moved + modified files\" is not anything special. The current \n> automatic merger may not handle it, but that's not because it _can't_ \n> handle it, it's because it tries to be simple and efficient. \n> \n> And because it's so _incredibly_ fast for all the normal cases, you can \n> now spend some effort on figuring out renames dynamically for the few \n> cases where it fails. Does it do so now? No. Would adding UUID's help? \n> Hell no. It would be just an unmitigated disaster.\n> \n\nOkay, how about keeping a cache (derived from the contents) of these \ntypes of data, to assist the merge if necessary? If it doesn't exist \nwhen needed, it can just be created, which may take O(n) time.\n\n\t-hpa\n"},{"id":"8099","messageId":"7vzmqr5qva.fsf@assigned-by-dhcp.cox.net","threadId":"1719","inReplyTo":"Pine.LNX.4.58.0509050825170.3568@evo.osdl.org","subject":"Re: Moved files and merges","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-05T18:08:57Z","receivedAt":"2005-09-05T18:08:57Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds writes:\n\n> Of course, if you don't push it back, but keep the two trees separate and \n> keep on modifying files that have different names in the other repository, \n> you'll keep on getting into the situation that the trivial merge doesn't \n> work. So we _do_ want to get an automated \"phase 3\" (and maybe 4..) merge \n> that can figure out renames, but the point here is that it's something we \n> _can_ figure out.\n\nThanks. You very well said exactly what I should have said; I\nfailed to explain where that `reusing rename information from\nprevious merge` algorithm should fit in the bigger picture.\n\nAnd the algorithm you describe (and Daniel briefly outlined) is\nslightly different from what I had in mind in that it does not\nhave to depend on previous merge, which is also nice.\n"},{"id":"8102","messageId":"7v4q8z5pqv.fsf@assigned-by-dhcp.cox.net","threadId":"1719","inReplyTo":"431C6167.4070703@zytor.com","subject":"Re: Moved files and merges","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-09-05T18:33:12Z","receivedAt":"2005-09-05T18:33:12Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"H. Peter Anvin\" writes:\n\n> One question, of course, is if one should simply keep additional \n> metadata around to handle this sort of situations. One could, for \n> example, keep a UUID for each file,...\n\nIf I am not mistaken, that is exactly what tla does. It seems\nto work well in practice and seem so simple (at least\nsuperficially, I have not looked deeply into the issues involved\nin keeping it sync with the contents and how to recover if the\nuser ever screws up, etc.), and I can see why people find it so\nattractive. I myself once did.\n\nBut previous argument by Linus made in a distant (in git\ntimescale) past is now ingrained in my brain: \"the additional\nmetadata\" recorded at the commit time can only help us what we\nenvisioned in the past when the tool to record that metadata was\nwritten. If we try to \"track\" by contents, we can do at least\nthe same (diff -M being able to tell renames is an example that\nwe can get away without having a UUID) and possibly better,\ndepending on how much effort we are willing to spend \"drilling\ndown\" when we actually need to know what happened at merge\ntime. What I found most important in that argument by Linus is\nthat the \"drilling down\" algorithm can improve over time while\n\"the additional metadata\" specification is cast in stone when a\ncommit is made.\n"},{"id":"8104","messageId":"431C91B4.6040609@zytor.com","threadId":"1719","inReplyTo":"7v4q8z5pqv.fsf@assigned-by-dhcp.cox.net","subject":"Re: Moved files and merges","fromName":"H. Peter Anvin","fromEmail":"hpa@zytor.com","sentAt":"2005-09-05T18:43:00Z","receivedAt":"2005-09-05T18:43:00Z","isPatch":false,"sender":{"key":"hpa@zytor.com","avatar":null},"body":"Junio C Hamano wrote:\n> \n> But previous argument by Linus made in a distant (in git\n> timescale) past is now ingrained in my brain: \"the additional\n> metadata\" recorded at the commit time can only help us what we\n> envisioned in the past when the tool to record that metadata was\n> written. If we try to \"track\" by contents, we can do at least\n> the same (diff -M being able to tell renames is an example that\n> we can get away without having a UUID) and possibly better,\n> depending on how much effort we are willing to spend \"drilling\n> down\" when we actually need to know what happened at merge\n> time. What I found most important in that argument by Linus is\n> that the \"drilling down\" algorithm can improve over time while\n> \"the additional metadata\" specification is cast in stone when a\n> commit is made.\n> \n\n... unless the \"additional metadata\" is merely a cache, derived from the \ncontents. The advantage, of course, is that you can produce data that \nis more expensive that way. On the other hand, if you don't need it, \nit's pointless.\n\n\t-hpa\n"}]}