{"thread":{"id":"2477","subject":"git-merge-recursive: documentation and implementation notes","startedAt":"2005-11-12T20:34:57Z","lastAt":"2005-11-13T17:12:07Z","messageCount":3,"participants":["Fredrik Kuivinen","Petr Baudis"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"11696","messageId":"20051112203457.GA5234@c165.ib.student.liu.se","threadId":"2477","inReplyTo":null,"subject":"git-merge-recursive: documentation and implementation notes","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-11-12T20:34:57Z","receivedAt":"2005-11-12T20:34:57Z","isPatch":false,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"Hi,\n\nThis mail contains the promised documentation for the recursive merge\nstrategy. I don't really know where or even if this belongs in the Git\nrepository, so I am not posting it as a patch. If it is understandable\nit might be appropriate for Documentaion/technical.\n\n\n\nThis note is supposed to describe how the recursive merge strategy\nworks. As I am not a native English speaker comments regarding\nspelling and grammar are more than welcome. Comments on the content\nis, of course, even more welcome :)\n\nThe fundamental merge problem that the recursive strategy tries to\nsolve is when there are more than one common ancestor of the branches\nwe want to merge. This happens, for example, in the \"criss-cross\"\nmerge case:\n\nA\n|\\\n| \\\n|  \\\n|   \\\n|    \\\n|     \\\n|      \\\nB8      C3\n|\\     /|\n| \\   / |\n|  \\ /  |\n|   X   |\n|  / \\  |\n| /   \\ |\n|/     \\|\nD8      E3\n \\      |\n  \\     |\n   \\    |\n    \\   |\n     \\  |\n      \\ |\n       \\|\n        M\n\n(This example and the ASCII graphic are from Bram Cohen's excellent\ndescription of the criss-cross case in\nhttp://marc.theaimsgroup.com/?l=git&m=111463358500362&w=2)\n\nWe have a common base A, at commit B and D line 8 was changed and at\ncommit C and E line 3 was changed. There is only one file, so the same\nfile is modified in B, C, D and E. The result of the merge is called\nM.\n\nIf we do a classical three-way merge of D and E with either A, B or C\nas the common ancestor we will get conflicts. Theoretically this\nshouldn't happen as both the D branch and the E branch knows about the\nchanges made at both B and C, the theoretical clean merge should\ntherefore contain line number 3 from E and line number 8 from D.\n\nThe recursive merge strategy solves this problem by recursively\nmerging any common ancestors. Hence, in the criss-cross scenario above\nthe code will detect that D and E has both B and C as their common\nancestor. It will then recursively merge B with C. The common ancestor\nof B and C is A. When there is only one common ancestor an ordinary\nthree-way merge is done (modulo renames, will talk about those\nbelow). So in this case we will merge B and C with A as the common\nancestor to create a temporary tree. This new tree will then be used\nas the common ancestor for a merge of D and E.\n\nIn some cases there are more than two common ancestor, for example\n44583d380d189095fa959ec8ba87f0cb6deb15f5 in Thomas Gleixner's\nhistorical Linux kernel repository has no less than six common\nancestors.\n\nThe recursive strategy also has some support for renamed objects.\nConsider the following ancestry graph:\n\n   O\n  / \\\n /   \\\nA     B\n\nLet the file 'foo' be renamed to 'bar' in A. In the B branch 'foo' is\nmodified. The result of a merge of A and B will contain a file 'bar'\nwith whatever contents merge(1) produced given A/bar and B/foo as the\nfiles to be merged and O/foo as the ancestor. Renames are detected by\nexecuting 'git-diff-tree -M --diff-filter=R <branch> <ancestor>' for\nboth branches. The rename processing may be seen as a pre-processing\nstep to the three-way merge procedure in the sense that renames are\nprocessed first and then the ordinary file-level merging is done.\n\nThere are, essentially, only two merge scenarios which involves\nrenames that are cleanly merged. The first one is the case described\nabove when a file is renamed (and possibly modified) in one branch and\nmodified in the other branch. The other scenario is when the same file\nis renamed to the same new name in both branches. However, there are\nseveral scenarios which causes conflicts, if for example we are going\nto merge the branches A and B then the following table contain a few\nof the conflict cases:\n\nIn A                  In B\n-------------------------------------\nrename a -> b         rename a -> c\nrename a -> b         rename c -> b\nadd a                 rename b -> a\ndelete a              rename a -> b\n\n(Each line should be interpreted as an individual scenario, file names\non different lines do not have anything in common.)\n\n\nThere is currently no support for directory renames. If a directory is\nrenamed it will be processed as if every file in the directory was\nrenamed. This will cause clean merges of certain cases which probably\nshould be conflicts. (Such as: directory 'foo' is renamed to 'bar' in\none branch, in the other branch a new file 'foo/baz' is added. With\nthe current code we will end up with both a 'foo' directory,\ncontaining 'foo/baz', and a 'bar' directory containing whatever 'foo'\ncontained in the common ancestor. A better outcome would probably be\nto flag this as a conflict.)\n\nThe code tries, as far as possible, to let the user know what happens\nin the conflict cases. The idea is that the user shouldn't have to\nguess what the algorithm has done when she stumbles upon some strange\ncorner case. For example, if a file 'foo/bar' is added in the branch\n'testing' and 'baz' is renamed to 'foo' in the branch 'release' then\nthe user will be given the message:\n\n    CONFLICT (rename/directory): Rename baz => foo in branch release directory foo added in testing\n    Renaming baz to foo~release instead\n\n(The file name 'foo~release' is carefully constructed to not overwrite\nany existing files.)\n\n\nWhat follows is pseudo code which describes the algorithm from a\nhigh-level point of view. Text within [brackets] is either a name of a\nPython function where the real code can be found or a short\ndescription of where the code can be found. Currently, the code is\ncontained in two files, git-merge-recursive.py and gitMergeCommon.py.\n\n[merge]\nmerge(A, B)\n{\n    [getCommonAncestors]\n    commonAncestors = getCommonAncestors(A, B)\n\n    mergeCommonAncestor = commonAncestors[0]\n    for(i = 1; i < length(commonAncestors); i++) {\n        mergedCommonAncestor = merge(mergedCommonAncestor, commonAncestors[i])\n    }\n\n    [in mergeTrees]\n    git-read-tree -m mergeCommonAncestor A B\n\n    [loop in mergeTrees, git-diff-tree execution in getRenames]\n    for each file in either\n        'git-diff-tree -M --diff-filter=R -r mergeCommonAncestor A' or\n        'git-diff-tree -M --diff-filter=R -r mergeCommonAncestor B':\n        \n\t[processRenames]\n        All rename processing is done here. This includes detection of\n        various conflict cases and merge the 'rename in one branch and\n        modified in the other'-case \n        \n        [processRenames]\n        For every file which is merged cleanly update the index\n\n\n    [loop in mergeTrees]\n    for each file which is still 'unmerged' in the index:\n\n        [processEntry]\n        Do a file-level merge. This is more or less the same thing as\n        git-merge-one-file does, but it is implemented in Python.\n\n    Return the new merged tree. \n}\n\nPlease note that the pseudo code above just is a sketch of the real\ncode. One important difference is that in the real code a resulting\ntree is always returned from the 'merge'-function as soon as the\n'merge'-function has been called recursively.\n\nLets assume there is a merge conflict when we merge B and C in the\ncriss-cross case above. Then both D and E must resolve this\nconflict. If they have done it in the same way we wont get a merge\nconflict at M, if they have resolved it differently we will get a\nmerge conflict. In the first case there is no merge conflict at M, in\nthe second case the user has to pick which one of the two different\nresolutions she wants.\n\nNote that the algorithm will happily write non-clean merge results to\nthe object database during the \"merge common ancestors\" stage. Hence,\nwhen we are merging B and C \"internally\" we will _not_ ask the user to\nresolve any eventual merge conflicts.\n\nThe temporary trees and non-cleanly merged files which are written to\nthe object database are not removed when the merge is finished. Hence,\nin some cases, there will be unreachable objects in the database after\na merge.\n\n- Fredrik\n"},{"id":"11698","messageId":"20051112210306.GG30496@pasky.or.cz","threadId":"2477","inReplyTo":"20051112203457.GA5234@c165.ib.student.liu.se","subject":"Re: git-merge-recursive: documentation and implementation notes","fromName":"Petr Baudis","fromEmail":"pasky@suse.cz","sentAt":"2005-11-12T21:03:06Z","receivedAt":"2005-11-12T21:03:06Z","isPatch":false,"sender":{"key":"pasky@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/18439?v=4"},"body":"  Hi,\n\nDear diary, on Sat, Nov 12, 2005 at 09:34:57PM CET, I got a letter\nwhere Fredrik Kuivinen <freku045@student.liu.se> said that...\n> Lets assume there is a merge conflict when we merge B and C in the\n> criss-cross case above. Then both D and E must resolve this\n> conflict. If they have done it in the same way we wont get a merge\n> conflict at M, if they have resolved it differently we will get a\n> merge conflict. In the first case there is no merge conflict at M, in\n> the second case the user has to pick which one of the two different\n> resolutions she wants.\n> \n> Note that the algorithm will happily write non-clean merge results to\n> the object database during the \"merge common ancestors\" stage. Hence,\n> when we are merging B and C \"internally\" we will _not_ ask the user to\n> resolve any eventual merge conflicts.\n\n  I find this part somewhat unclear. So how does the user pick which of\nthe two different resolution she wants if we will not ask the user to\nresolve any conflicts?\n\n-- \n\t\t\t\tPetr \"Pasky\" Baudis\nStuff: http://pasky.or.cz/\nVI has two modes: the one in which it beeps and the one in which\nit doesn't.\n"},{"id":"11733","messageId":"20051113171207.GB4805@c165.ib.student.liu.se","threadId":"2477","inReplyTo":"20051112210306.GG30496@pasky.or.cz","subject":"Re: git-merge-recursive: documentation and implementation notes","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-11-13T17:12:07Z","receivedAt":"2005-11-13T17:12:07Z","isPatch":false,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Sat, Nov 12, 2005 at 10:03:06PM +0100, Petr Baudis wrote:\n>   Hi,\n> \n> Dear diary, on Sat, Nov 12, 2005 at 09:34:57PM CET, I got a letter\n> where Fredrik Kuivinen <freku045@student.liu.se> said that...\n> > Lets assume there is a merge conflict when we merge B and C in the\n> > criss-cross case above. Then both D and E must resolve this\n> > conflict. If they have done it in the same way we wont get a merge\n> > conflict at M, if they have resolved it differently we will get a\n> > merge conflict. In the first case there is no merge conflict at M, in\n> > the second case the user has to pick which one of the two different\n> > resolutions she wants.\n> > \n> > Note that the algorithm will happily write non-clean merge results to\n> > the object database during the \"merge common ancestors\" stage. Hence,\n> > when we are merging B and C \"internally\" we will _not_ ask the user to\n> > resolve any eventual merge conflicts.\n> \n>   I find this part somewhat unclear. So how does the user pick which of\n> the two different resolution she wants if we will not ask the user to\n> resolve any conflicts?\n> \n\nIf we have a conflict when we merge B and C we will get a file with\nconflict markers from merge(1) in it, so it will look something like\n\n    1\n    2\n    3\n    <<<<<<\n    4\n    5\n    ======\n    6\n    7\n    >>>>>>\n    8\n    9\n\nThis file will be stored in the object database and the temporary tree\nwhich is created by the merge of B and C will refer to it.\n\nThe algorithm will then merge D and E and use the file above as the\ncommon ancestor. There are now two cases to consider, the first one is\nthat both D and E resolve the conflict above in the same way (and\npossible make other changes which can be cleanly merged), we end up\nwith something like\n\n    1\n    2\n    3\n    4\n    5\n    8\n    9\n\nin both D and E. This will be merged cleanly into M. The other case is\nthat D and E either resolves the conflict differently or that they do\nother modifications which aren't possible to merge automatically. In\nthis case we will let the user do the conflict resolution.\n\nSo, what I meant was that during the first merge, of B and C, the user\ndo not have to do anything with any eventual conflicts. However, in\nthe top-level merge, conflict resolution works in the same way as it\ndoes for the 'resolve' strategy, i.e., the output of merge(1) is\nstored in the working directory and the index is updated to make 'git\ndiff' useful.\n\n- Fredrik\n"}]}