{"thread":{"id":"1665","subject":"[RFC, PATCH] A new merge algorithm (EXPERIMENTAL)","startedAt":"2005-08-26T18:47:31Z","lastAt":"2005-08-27T01:40:09Z","messageCount":8,"participants":["Fredrik Kuivinen","Daniel Barkalow","Junio C Hamano","Linus Torvalds"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"7817","messageId":"20050826184731.GA13629@c165.ib.student.liu.se","threadId":"1665","inReplyTo":null,"subject":"[RFC, PATCH] A new merge algorithm (EXPERIMENTAL)","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-08-26T18:47:31Z","receivedAt":"2005-08-26T18:47:31Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"Hi,\n\nI have for some time now been playing with a new merge algorithm.  It\nis designed to solve some of the content merges that comes up now and\nthen. For example the criss-cross merge case described by Bram Cohen\n[1], the similar case described by Matthias Urlichs [3] and the merge\ncase Tony Luck found [2].\n\nIt does _not_ do anything smart with respect to tree changes. So with\nrespect to file renames, directory renames etc it wont be any better\nthan the current git-resolve-script.\n\nThe new code consists of a few files merge.py,\ngit-new-merge-one-file-script.py, gitMergeCommon.py and\ngitMergeCore.py. Its all written in Python, at least version 2.4 is\nrequired. It also need a small patch to read-tree.c. Right now its all\nvery much experimental. It seems to do the right thing on the test\ncases I have given to it, but it probably contains lots of bugs and\nunsolved corner cases.\n\nThe user interface consists of the program 'merge.py'. \nThe syntax is: merge.py <branch> \n\nmerge.py expects that the working directory is in sync with both the\ncache and HEAD. It will merge HEAD with <branch>. The result of the\nmerge will be written to the working directory and the cache will be\nupdated to match the working directory. Those two steps are always\ndone, even if the merge was non-clean. merge.py will create the\nappropriate .git/MERGE_HEAD.\n\nI will try to describe how the algorithm works. The problem with the\nusual 3-way merge algorithm is that we sometimes do not have a unique\ncommon ancestor. In [1] B and C seems to be equally good. What this\nalgorithm does is to _merge_ the common ancestors, in this case B and\nC, into a temporary tree lets call it T. It does then use this\ntemporary tree T as the common ancestor for D and E to produce the\nfinal merge result. In the case described in [1] this will work out\nfine and we get a clean merge with the expected result.\n\nThe common ancestors that are found to be \"equally good\" are named\n\"shared heads\" in the code. In the criss-cross merge case there are\ntwo shared heads, B and C.\n\nIn [2] the algorithm finds three shared heads,\nf6fdd7d9c273bb2a20ab467cb57067494f932fa3,\n3a931d4cca1b6dabe1085cc04e909575df9219ae and\nc1ffb910f7a4e1e79d462bb359067d97ad1a8a25. Those three commits are then\nmerged to produce a new temporary tree T. T is then used as the common\nancestor to merge the original\na4cce10492358b33d33bb43f98284c80482037e8 and\n7ffacc1a2527c219b834fe226a7a55dc67ca3637.\n\nThe result is the expected one, that is the diff between the merge\nproduced by 'merge.py' and 'git-resolve-script' is\n\ndiff --git a/arch/ia64/hp/sim/boot/bootloader.c b/arch/ia64/hp/sim/boot/bootloader.c\n--- a/arch/ia64/hp/sim/boot/bootloader.c\n+++ b/arch/ia64/hp/sim/boot/bootloader.c\n@@ -30,10 +30,14 @@ struct disk_req {\n        unsigned len;\n };\n \n+/* SSC_WAIT_COMPLETION appears to want this large alignment.  gcc < 4\n+ * seems to give it by default, however gcc > 4 is smarter and may\n+ * not.\n+ */\n struct disk_stat {\n        int fd;\n        unsigned count;\n-};\n+} __attribute__ ((aligned (16)));\n \n extern void jmp_to_kernel (unsigned long bp, unsigned long e_entry);\n extern struct ia64_boot_param *sys_fw_init (const char *args, int arglen);\n\n\n\nIn most merges there is only one shared head, in this case 'merge.py'\nis supposed to produce similar results as we get with\n'git-resolve-script'.\n\nIn real numbers it is as follows: In Linus' kernel tree there are\n5996 commits. 400 of those have more than one parent. Of those 400\nmerge commits 4 have more than one shared head.\n\nCurrently the main problems and questions that I see with this patch\nare:\n\n* There is no way to easily detect if the merge was clean or not. A\n  message about it is written to stdout but merge.py wont return a\n  usable error code. This shouldn't be too hard to fix.\n* Temporary trees and other objects may be written to the object\n  database during the merge. They are currently not deleted.\n* If this is going to be used for anything real it has to be cleaned\n  up.\n* Are there merge cases for which this algorithm clearly produces the \n  wrong result?\n* Is it worth it? That is, is the added complexity in the merge logic\n  worth the advantages of correctly handling some strange (but real\n  life) merge cases?\n\n- Fredrik\n\n[1] http://www.gelato.unsw.edu.au/archives/git/0504/2279.html\n[2] http://www.gelato.unsw.edu.au/archives/git/0508/8072.html, and the\n    follow-up discussion.\n[3] http://www.gelato.unsw.edu.au/archives/git/0507/6082.html\n\nSigned-off-by: Fredrik Kuivinen <freku045@student.liu.se>\n\n---\n\n Makefile                  |    3 \n git-new-merge-one-file.py |  153 ++++++++++++++++++++\n gitMergeCommon.py         |   68 +++++++++\n gitMergeCore.py           |  350 +++++++++++++++++++++++++++++++++++++++++++++\n merge.py                  |   39 +++++\n read-tree.c               |   13 +-\n 6 files changed, 623 insertions(+), 3 deletions(-)\n\ndiff --git a/Makefile b/Makefile\n--- a/Makefile\n+++ b/Makefile\n@@ -66,7 +66,8 @@ SCRIPTS=git git-apply-patch-script git-m\n \tgit-format-patch-script git-sh-setup-script git-push-script \\\n \tgit-branch-script git-parse-remote-script git-verify-tag-script \\\n \tgit-ls-remote-script git-clone-dumb-http git-rename-script \\\n-\tgit-request-pull-script git-bisect-script\n+\tgit-request-pull-script git-bisect-script merge.py gitMergeCommon.py \\\n+\tgitMergeCore.py git-new-merge-one-file.py\n \n SCRIPTS += git-count-objects-script\n # SCRIPTS += git-send-email-script\ndiff --git a/git-new-merge-one-file.py b/git-new-merge-one-file.py\nnew file mode 100755\n--- /dev/null\n+++ b/git-new-merge-one-file.py\n@@ -0,0 +1,153 @@\n+#!/usr/bin/env python\n+#\n+# This script is based on 'git-merge-one-file-script' in the Git\n+# distribution.\n+#\n+# This is a git per-file merge script, called with\n+#\n+#   $1 - original file SHA1 (or empty)\n+#   $2 - file in branch1 SHA1 (or empty)\n+#   $3 - file in branch2 SHA1 (or empty)\n+#   $4 - pathname in repository\n+#   $5 - orignal file mode (or empty)\n+#   $6 - file in branch1 mode (or empty)\n+#   $7 - file in branch2 mode (or empty)\n+#\n+# Handle some trivial cases.. The _really_ trivial cases have\n+# been handled already by git-read-tree, but that one doesn't\n+# do any merges that might change the tree layout.\n+\n+import sys, os\n+from gitMergeCommon import *\n+from sets import Set\n+\n+oSha = sys.argv[1]\n+aSha = sys.argv[2]\n+bSha = sys.argv[3]\n+path = sys.argv[4]\n+oMode = sys.argv[5]\n+aMode = sys.argv[6]\n+bMode = sys.argv[7]\n+\n+branch1 = os.environ['GIT_MERGE_BRANCH_1']\n+branch2 = os.environ['GIT_MERGE_BRANCH_2']\n+[files, dirs] = eval(open(os.environ['GIT_MERGE_DIRS']).read())\n+\n+# TODO\n+# dir/file name conflicts\n+\n+# x <==> sha != '', - <==> sha == '' \n+#\n+# Case  o a b\n+# D     x x x\n+# A     x x -\n+# A     x - x\n+# A     x - -\n+# C     - x x\n+# B     - x -\n+# B     - - x\n+#       - - - Doesn't happen\n+\n+if (oSha != '' and (aSha == '' or bSha == '')):\n+#\n+# Case A: Deleted in one\n+#\n+    if (aSha == ''   and bSha == '') or \\\n+       (aSha == oSha and bSha == '') or \\\n+       (aSha == ''   and bSha == oSha):\n+# Deleted in both or deleted in one and unchanged in the other\n+        print 'Removing ' + path\n+        runProgram(['git-update-cache', '--force-remove', '--', path])\n+    else:\n+# Deleted in one and changed in the other\n+        if aSha == '':\n+            print 'CONFLICT (del/mod): \"' + path + '\" deleted in', \\\n+                  branch1, 'and modified in', branch2, '. Version ', branch2, ' of \"' + path + '\" left in tree'\n+            mode = bMode\n+            sha = bSha\n+        else:\n+            print 'CONFLICT (mod/del): \"' + path + '\" deleted in ' + branch2 + ' and modified in ' + branch1 + \\\n+                  '. Version ' + branch1 + ' of \"' + path + '\" left in tree'\n+            mode = aMode\n+            sha = aSha\n+        runProgram(['git-update-cache', '--cacheinfo', mode, sha, path])\n+\n+elif (oSha == '' and aSha != '' and bSha == '') or \\\n+     (oSha == '' and aSha == '' and bSha != ''):\n+#\n+# Case B: Added in one.\n+#\n+    if aSha != '':\n+        addBranch = branch1\n+        otherBranch = branch2\n+        conf = 'file/dir'\n+    else:\n+        addBranch = branch2\n+        otherBranch = branch1\n+        conf = 'dir/file'\n+\n+    if path in dirs:\n+        newPath = path + '_' + addBranch\n+        print 'CONFLICT (' + conf + '): There is a directory with name \"' + path + '\" in ' + otherBranch + \\\n+              '. Adding \"' + path + '\" as \"' + newPath + '\"'\n+        runProgram(['git-update-cache', '--force-remove', '--', path])\n+        path = newPath\n+    else:\n+        print 'Adding \"' + path + '\"'\n+    runProgram(['git-update-cache', '--add', '--cacheinfo', aMode+bMode, aSha+bSha, path])\n+\n+elif oSha == '' and aSha != '' and bSha != '':\n+#\n+# Case C: Added in both (check for same permissions).\n+#\n+    if aSha == bSha:\n+        if aMode != bMode:\n+            print 'CONFLICT: File \"' + path + '\" added identically in both branches,'\n+            print 'CONFLICT: but permissions conflict ' + aMode + '->' + bMode + '.'\n+            print 'CONFLICT: adding with permission: ' + aMode\n+            runProgram(['git-update-cache', '--add', '--cacheinfo', aMode, aSha, path])\n+        else:\n+            # This case is handled by git-read-tree\n+            print 'Adding ' + path\n+            runProgram(['git-update-cache', '--add', '--cacheinfo', aMode, aSha, path])\n+    else:\n+        newPath1 = path + '_' + branch1\n+        newPath2 = path + '_' + branch2\n+        print 'CONFLICT (add/add): File \"' + path + '\" added non-identically in both branches. ' + \\\n+              'Adding \"' + newPath1 + '\" and \"' + newPath2 + '\" instead.'\n+        runProgram(['git-update-cache', '--force-remove', '--', path])\n+        runProgram(['git-update-cache', '--add',\n+                    '--cacheinfo', aMode, aSha, newPath1,\n+                    '--cacheinfo', bMode, bSha, newPath2])\n+\n+elif oSha != '' and aSha != '' and bSha != '':\n+#\n+# case D: Modified in both, but differently.\n+#\n+    print 'Auto-merging ' + path + '.'\n+    orig = runProgram(['git-unpack-file', oSha]).rstrip()\n+    src1 = runProgram(['git-unpack-file', aSha]).rstrip()\n+    src2 = runProgram(['git-unpack-file', bSha]).rstrip()\n+    [out, ret] = runProgram(['merge',\n+                             '-L', os.environ['GIT_MERGE_BRANCH_1'] + '/' + path,\n+                             '-L', 'orig/' + path,\n+                             '-L', os.environ['GIT_MERGE_BRANCH_2'] + '/' + path,\n+                             src1, orig, src2], returnCode=True)\n+\n+    if ret != 0:\n+        print 'CONFLICT (content): Merge conflict in \"' + path + '\".'\n+\n+    if aMode == oMode:\n+        mode = bMode\n+    else:\n+        mode = aMode\n+\n+    sha = runProgram(['git-hash-object', '-t', 'blob', '-w', src1])\n+    runProgram(['git-update-cache', '--cacheinfo', aMode, sha, path])\n+    os.unlink(orig)\n+    os.unlink(src1)\n+    os.unlink(src2)\n+else:\n+    print 'ERROR: Fatal merge failure.'\n+    print \"ERROR: Shouldn't happen\"\n+\ndiff --git a/gitMergeCommon.py b/gitMergeCommon.py\nnew file mode 100644\n--- /dev/null\n+++ b/gitMergeCommon.py\n@@ -0,0 +1,68 @@\n+import sys\n+\n+if sys.version_info[0] < 2 or (sys.version_info[0] == 2 and sys.version_info[1] < 4):\n+    print 'Python version 2.4 required, found', \\\n+    str(sys.version_info[0])+'.'+str(sys.version_info[1])+'.'+str(sys.version_info[2])\n+    sys.exit(1)\n+\n+import subprocess, os\n+\n+DEBUG = 1\n+\n+def debug(str, level=1):\n+    if level > DEBUG:\n+        print str\n+\n+class ProgramError(Exception):\n+    def __init__(self, progStr, error):\n+        self.progStr = progStr\n+        self.error = error\n+\n+def runProgram(prog, input=None, returnCode=False):\n+    debug('runProgram prog: ' + str(prog) + \" input: \" + str(input))\n+    if type(prog) is str:\n+        progStr = prog\n+    else:\n+        progStr = ' '.join(prog)\n+    \n+    try:\n+        pop = subprocess.Popen(prog,\n+                               shell = type(prog) is str,\n+                               stderr=subprocess.STDOUT,\n+                               stdout=subprocess.PIPE,\n+                               stdin=subprocess.PIPE)\n+    except OSError, e:\n+        debug(\"strerror: \" + e.strerror, 2)\n+        raise ProgramError(progStr, e.strerror)\n+\n+    if input != None:\n+        pop.stdin.write(input)\n+    pop.stdin.close()\n+    \n+    out = pop.stdout.read()\n+    code = pop.wait()\n+    if returnCode:\n+        ret = [out, code]\n+    else:\n+        ret = out\n+    if code != 0 and not returnCode:\n+            print \"error output: \" + out\n+            print 'prog: ' + str(prog)\n+            raise ProgramError(progStr, out)\n+    debug(\"output: \" + out.replace('\\0', '\\n'))\n+    return ret\n+\n+def setupEnvironment():\n+    if 'GIT_DIR' not in os.environ:\n+        os.environ['GIT_DIR'] = '.git'\n+\n+    if not os.environ.has_key('GIT_OBJECT_DIRECTORY'):\n+        os.environ['GIT_OBJECT_DIRECTORY'] = os.environ['GIT_DIR'] + '/objects'\n+\n+def repoValid():\n+    if not (os.path.exists(os.environ['GIT_DIR']) and\n+            os.path.exists(os.environ['GIT_DIR'] + '/refs') and\n+            os.path.exists(os.environ['GIT_OBJECT_DIRECTORY']) and\n+            os.path.exists(os.environ['GIT_OBJECT_DIRECTORY'] + '/00')):\n+        print \"Not a Git archive\"\n+        sys.exit(1)\ndiff --git a/gitMergeCore.py b/gitMergeCore.py\nnew file mode 100644\n--- /dev/null\n+++ b/gitMergeCore.py\n@@ -0,0 +1,350 @@\n+import sys, math, random, os, re, signal, tempfile\n+from gitMergeCommon import runProgram, debug, DEBUG\n+from heapq import heappush, heappop\n+from sets import Set\n+\n+class GitObject:\n+    def __init__(self, sha):\n+        self.sha = sha.rstrip()\n+\n+def loadCommit(sha):\n+    c = Commit(sha)\n+    c.getInfo()\n+    return c\n+\n+class Commit(GitObject):\n+    def __init__(self, sha, parents=None, tree=None, author=None,\n+                 committer=None, msg=None):\n+        self.parents = parents\n+        self.author = author\n+        self.committer = committer\n+        self.msg = msg\n+        self.children = []\n+\n+        if tree:\n+            tree = tree.rstrip()\n+        self._tree = tree\n+\n+        if not sha:\n+            sha = self.writeObject(False)\n+\n+        GitObject.__init__(self, sha)\n+\n+    def writeObject(self, write=True):\n+        fout = tempfile.NamedTemporaryFile('w')\n+\n+        fout.write('tree ' + self._tree + '\\n')\n+        for p in self.parents:\n+            if isinstance(p, Commit):\n+                p = p.sha\n+            fout.write('parent ' + p + '\\n')\n+        fout.write('author Temporary merge author <temp@example.com> 0 +0000\\n')\n+        fout.write('committer Temporary merge committer <temp@example.com> 0 +0000\\n\\n')\n+        fout.write(self.msg + '\\n')\n+        fout.flush()\n+        if write:\n+            runProgram(['git-hash-object', '-w', '-t', 'commit', fout.name])\n+            ret = None\n+        else:\n+            ret = runProgram(['git-hash-object', '-t', 'commit', fout.name]).rstrip()\n+        fout.close()\n+        return ret\n+        \n+    def tree(self):\n+        self.getInfo()\n+        return self._tree\n+\n+    def shortInfo(self):\n+        self.getInfo()\n+        return self.sha.rstrip() + ' ' + self.msg.split('\\n')[0]\n+\n+    def __str__(self):\n+        return self.shortInfo()\n+\n+    def getInfo(self):\n+        if self.msg != None:\n+            return\n+        else:\n+            info = runProgram(['git-cat-file', 'commit', self.sha])\n+            info = info.split('\\n')\n+            msg = False\n+            self.msg = ''\n+            newParents = []\n+            for l in info:\n+                if msg:\n+                    self.msg += l + '\\n'\n+                else:\n+                    if l.startswith('tree'):\n+                        self._tree = l[5:].rstrip()\n+                    elif l.startswith('author'):\n+                        self.author = l\n+                    elif l.startswith('committer'):\n+                        self.committer = l\n+                    elif l.startswith('parent'):\n+                        newParents.append(l[7:].rstrip())\n+                    elif l == '':\n+                        msg = True\n+            if not self.parents:\n+                self.parents = newParents\n+\n+    # This is needed by the heap implementation in heapq. We want a\n+    # max heap, but heapq provides us with a min heap. We therefore use\n+    # >= instead of <= in this function.\n+    def __le__(self, other):\n+        return self.index >= other.index\n+\n+class Graph:\n+    def __init__(self):\n+        self.topoOrder = []\n+        self.shaMap = {}\n+\n+    def addNode(self, node):\n+        assert(isinstance(node, Commit) or isSha(node))\n+        if isSha(node):\n+            node = loadCommit(node)\n+            self.fixParents(node)\n+        self.shaMap[node.sha] = node\n+        node.index = len(self.topoOrder)\n+        self.topoOrder.append(node)\n+        for p in node.parents:\n+            p.children.append(node)\n+        return node\n+\n+    def reachableNodes(self, n1, n2):\n+        res = {}\n+        def traverse(n):\n+            res[n] = True\n+            for p in n.parents:\n+                traverse(p)\n+\n+        traverse(n1)\n+        traverse(n2)\n+        return res\n+\n+    def fixParents(self, node):\n+        for x in range(0, len(node.parents)):\n+            node.parents[x] = self.shaMap[node.parents[x]]\n+\n+def buildGraph(heads):\n+    print 'buildGraph heads: ' + str(heads)\n+    for h in heads:\n+        assert(isSha(h))\n+\n+    g = Graph()\n+\n+    out = runProgram(['git-rev-list', '--parents', '--topo-order'] + heads)\n+    print 'git-rev-list done.'\n+    for l in out.split('\\n'):\n+        if l == '':\n+            continue\n+        shas = l.split(' ')\n+\n+        # This is a hack, we temporarily use the 'parents' attribute\n+        # to contain a list of SHA1:s. They are later replaced by proper\n+        # Commit objects.\n+        c = Commit(shas[0], shas[1:])\n+\n+        g.topoOrder.append(c)\n+        g.shaMap[c.sha] = c\n+\n+    for c in g.topoOrder:\n+        g.fixParents(c)\n+\n+    g.topoOrder.reverse()\n+\n+#    print 'topoOrder:'\n+#    for c in topoOrder:\n+#        print str(c) + ' sha: ' + c.sha\n+#        print 'parents: ' + str(c.parents)\n+            \n+    i = 0\n+    for c in g.topoOrder:\n+        c.index = i\n+        i += 1\n+        for p in c.parents:\n+#            print 'p: ' + str(p) + ' c: ' + str(c)\n+            p.children.append(c)\n+    return g\n+\n+# Write the empty tree to the object database and return its SHA1\n+def writeEmptyTree():\n+    try:\n+        os.unlink(os.environ['GIT_DIR'] + '/index')\n+    except OSError:\n+        pass\n+    return runProgram(['git-write-tree']).rstrip()\n+\n+# Given a Graph of commit objects and two heads (which also are commit\n+# objects), h1 and h2, this function computes the Minimal Most Common\n+# Ancestor of h1 and h2.\n+def mmca(graph, h1, h2):\n+    h = []\n+    heappush(h, h1)\n+    heappush(h, h2)\n+\n+    roots = []\n+    while(len(h) > 0):\n+#        print 'heap: '\n+#        for x in h:\n+#            print str(x), x.index\n+        if len(h) == 1 and len(roots) == 0:\n+            break\n+        \n+        el = heappop(h)\n+\n+        if len(el.parents) == 0:\n+            roots.append(el)\n+\n+        for p in el.parents:\n+            if not p in h:\n+                heappush(h, p)\n+\n+    if len(roots) > 0:\n+        superRoot = Commit(sha=None, parents=[], tree=writeEmptyTree(), author='author',\n+                           committer='committer', msg='empty tree commit')\n+        graph.addNode(superRoot)\n+        for r in roots:\n+            r.parents = [superRoot]\n+        superRoot.children = roots\n+        return superRoot\n+    else:\n+        return h[0]\n+\n+def findShared(mmca, h1, h2):\n+    def traverse(start, end, set):\n+        stack = [start]\n+        while len(stack) > 0:\n+            el = stack.pop()\n+            set.add(el)\n+            if start != end:\n+                for p in el.parents:\n+                    if p not in set:\n+                        stack.append(p)\n+    h1Set = Set()\n+    h2Set = Set()\n+    traverse(h1, mmca, h1Set)\n+    traverse(h2, mmca, h2Set)\n+\n+    return h1Set.intersection(h2Set)\n+\n+def sharedHeads(mmca, shared):\n+    h = Set()\n+    searched = Set()\n+    stack = [mmca]\n+    while len(stack) > 0:\n+        el = stack.pop()\n+        searched.add(el)\n+        if len([c for c in el.children if c in shared]) == 0:\n+            h.add(el)\n+\n+        for c in el.children:\n+            if c in shared and c not in searched:\n+                stack.append(c)\n+\n+    return list(h)\n+\n+getFilesRE = re.compile('([0-9]+) ([a-z0-9]+) ([0-9a-f]{40})\\t(.*)')\n+def getFilesAndDirs(tree1, tree2):\n+    files = Set()\n+    dirs = Set()\n+    def addFilesDirs(tree):\n+        out = runProgram(['git-ls-tree', '-r', '-z', tree])\n+        for l in out.split('\\0'):\n+            m = getFilesRE.match(l)\n+            if m:\n+                if m.group(2) == 'tree':\n+                    dirs.add(m.group(4))\n+                elif m.group(2) == 'blob':\n+                    files.add(m.group(4))\n+\n+    addFilesDirs(tree1)\n+    addFilesDirs(tree2)\n+    return [files, dirs]\n+\n+def merge(h1, h2, branch1Name, branch2Name, graph, indent=0, first=True):\n+    print '\\n' + '  '*indent, 'Merging:'\n+    print '  '*indent, h1\n+    print '  '*indent, h2\n+    assert(isinstance(h1, Commit) and isinstance(h2, Commit))\n+    assert(isinstance(graph, Graph))\n+\n+    a = mmca(graph, h1, h2)\n+    print '  '*indent, 'mmca:', a\n+    s = findShared(a, h1, h2)\n+    print '  '*indent, 'found', len(s), 'shared commits.'\n+    if len(s) < 10:\n+        for x in s:\n+            print '  '*indent, x\n+    sys.stdout.flush()\n+    s = sharedHeads(a, s)\n+    print '  '*indent, 'found', len(s), 'shared head(s):'\n+    for x in s :\n+        print '  '*indent, x\n+    Ms = s[0]\n+\n+    for h in s[1:]:\n+        Ms = merge(Ms, h, branch1Name, branch2Name, graph, indent+1, False)\n+\n+    filesDirs = getFilesAndDirs(h1.tree(), h2.tree())\n+    \n+    print '  '*indent, 'running resolve on'\n+    print '  '*indent, h1\n+    print '  '*indent, h2\n+\n+    if first:\n+        b1 = branch1Name\n+        b2 = branch2Name\n+    else:\n+        b1 = 'Temporary shared merge branch 1'\n+        b2 = 'Temporary shared merge branch 2'\n+    shaRes = resolve(h1.tree(), h2.tree(), Ms.tree(), b1, b2, filesDirs)\n+\n+    res = Commit(None, [h1, h2], tree=shaRes, msg='Temporary merge commit')\n+    graph.addNode(res)\n+    res.writeObject()\n+    print '  '*indent, 'merge returned: (tree)',  res.tree(), '(commit)', res.sha\n+    return res\n+\n+shaRE = re.compile('^[0-9a-f]{40}$')\n+def isSha(obj):\n+    return type(obj) is str and bool(shaRE.match(obj))\n+\n+def resolve(head, merge, common, b1, b2, filesDirs):\n+    assert(isSha(head) and isSha(merge) and isSha(common))\n+    head = runProgram(['git-rev-parse', '--revs-only', head]).rstrip()\n+    merge = runProgram(['git-rev-parse', '--revs-only', merge]).rstrip()\n+\n+    if common == merge:\n+        return head\n+\n+    if common == head:\n+        return merge\n+\n+    runProgram(['git-read-tree', head])\n+    runProgram(['git-read-tree', '-i', '-m', common, head, merge])\n+    os.environ['GIT_MERGE_BRANCH_1'] = b1\n+    os.environ['GIT_MERGE_BRANCH_2'] = b2\n+    fdirs = tempfile.NamedTemporaryFile('w')\n+    fdirs.write(repr(filesDirs))\n+    fdirs.flush()\n+    os.environ['GIT_MERGE_DIRS'] = fdirs.name\n+    try:\n+        [tree, code] = runProgram('git-write-tree', returnCode=True)\n+        tree = tree.rstrip()\n+        if code != 0:\n+            [out, code] = runProgram(['git-merge-cache', '-o',\n+                                      'git-new-merge-one-file.py', '-a'],\n+                                     returnCode=True)\n+            \n+            print out\n+            if code != 0:\n+                # Shouldn't happen...\n+                print 'Fatal error: merge program failed.'\n+                print out\n+                sys.exit(1)\n+            else:\n+                return runProgram('git-write-tree').rstrip()\n+        else:\n+            return tree\n+    finally:\n+        fdirs.close()\ndiff --git a/merge.py b/merge.py\nnew file mode 100755\n--- /dev/null\n+++ b/merge.py\n@@ -0,0 +1,39 @@\n+#!/usr/bin/env python\n+\n+from gitMergeCommon import *\n+from gitMergeCore import buildGraph, merge\n+import sys\n+\n+if len(sys.argv) < 1:\n+    print 'Usage:', sys.argv[0], '<branch>'\n+    sys.exit(1)\n+\n+setupEnvironment()\n+repoValid()\n+\n+h1 = firstBranch = 'HEAD'\n+h2 = secondBranch = sys.argv[1]\n+\n+print 'h1: ' + h1 + ' h2: ' + h2\n+h1 = runProgram(['git-rev-parse', '--revs-only', h1]).rstrip()\n+h2 = runProgram(['git-rev-parse', '--revs-only', h2]).rstrip()\n+print 'Resolved heads: h1: ' + h1 + ' h2: ' + h2\n+\n+print 'Building graph...'\n+graph = buildGraph([h1, h2])\n+print 'graph done.'\n+\n+res = merge(graph.shaMap[h1], graph.shaMap[h2], firstBranch, secondBranch, graph)\n+print 'Merge result: (tree) ' + res.tree() + ' (commit) ' + res.sha\n+\n+# Checkout the merge results\n+runProgram(['git-read-tree', 'HEAD'])\n+runProgram(['git-update-cache', '--refresh'])\n+runProgram(['git-read-tree', '-m', '-u', 'HEAD', res.tree()])\n+\n+try:\n+    fout = open(os.environ['GIT_DIR'] + '/MERGE_HEAD', 'w+')\n+    fout.write(h2 + '\\n')\n+    fout.close()\n+except OSError, e:\n+    print 'Failed to open', os.environ['GIT_DIR'] + '/MERGE_HEAD', '!'\ndiff --git a/read-tree.c b/read-tree.c\n--- a/read-tree.c\n+++ b/read-tree.c\n@@ -7,6 +7,7 @@\n \n static int stage = 0;\n static int update = 0;\n+static int ignore_working_dir = 0;\n \n static int unpack_tree(unsigned char *sha1)\n {\n@@ -80,7 +81,10 @@ static void verify_uptodate(struct cache\n {\n \tstruct stat st;\n \n-\tif (!lstat(ce->name, &st)) {\n+        if (ignore_working_dir)\n+            return;\n+\n+        if (!lstat(ce->name, &st)) {\n \t\tunsigned changed = ce_match_stat(ce, &st);\n \t\tif (!changed)\n \t\t\treturn;\n@@ -510,7 +514,7 @@ static int read_cache_unmerged(void)\n \treturn deleted;\n }\n \n-static const char read_tree_usage[] = \"git-read-tree (<sha> | -m [-u] <sha1> [<sha2> [<sha3>]])\";\n+static const char read_tree_usage[] = \"git-read-tree (<sha> | -m [-u] [-i] <sha1> [<sha2> [<sha3>]])\";\n \n static struct cache_file cache_file;\n \n@@ -535,6 +539,11 @@ int main(int argc, char **argv)\n \t\t\tcontinue;\n \t\t}\n \n+                if (!strcmp(arg, \"-i\")) {\n+                        ignore_working_dir = 1;\n+                        continue;\n+                }\n+\n \t\t/* This differs from \"-m\" in that we'll silently ignore unmerged entries */\n \t\tif (!strcmp(arg, \"--reset\")) {\n \t\t\tif (stage || merge || emu23)\n"},{"id":"7820","messageId":"Pine.LNX.4.63.0508261558550.23242@iabervon.org","threadId":"1665","inReplyTo":"20050826184731.GA13629@c165.ib.student.liu.se","subject":"Re: [RFC, PATCH] A new merge algorithm (EXPERIMENTAL)","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-08-26T20:48:32Z","receivedAt":"2005-08-26T20:48:32Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Fri, 26 Aug 2005, Fredrik Kuivinen wrote:\n\n> I will try to describe how the algorithm works. The problem with the\n> usual 3-way merge algorithm is that we sometimes do not have a unique\n> common ancestor. In [1] B and C seems to be equally good. What this\n> algorithm does is to _merge_ the common ancestors, in this case B and\n> C, into a temporary tree lets call it T. It does then use this\n> temporary tree T as the common ancestor for D and E to produce the\n> final merge result. In the case described in [1] this will work out\n> fine and we get a clean merge with the expected result.\n\nThe only problem I can see with this is that it's likely to generate\nconflicts between the shared heads, and the user is going to be confused\ntrying to resolve them, because the files with the conflicts will be\nmissing all of the more recent changes. Other than that, I think it should\ngive the right answer, although it will presumably involve a lot of\nancient history doing the internal merge. (Which would probably be really\npainful if you've got two branches that cross-merge regularly and never\nactually completely sync)\n\nI'm getting pretty close to having a version of read-tree that does the\ntrivial merge portion based comparing the sides against all of the shared\nheads. I think yours will be better for the cases we've identified, giving\nthe correct answer for Tony's case rather than reporting a conflict, but\nit's clearly more complicated. I think my changes are worthwhile anyway,\nsince they make the merging logic more central, but obviously\ninsufficient.\n\nI've been thinking that could be useful to have read-tree figure out the\nhistory itself, instead of being passed ancestors, in which case it could\nuse your method, except more efficiently (and only look further at the\nhistory when needed).\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"7821","messageId":"20050826213900.GA18880@c165.ib.student.liu.se","threadId":"1665","inReplyTo":"Pine.LNX.4.63.0508261558550.23242@iabervon.org","subject":"Re: [RFC, PATCH] A new merge algorithm (EXPERIMENTAL)","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-08-26T21:39:00Z","receivedAt":"2005-08-26T21:39:00Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Fri, Aug 26, 2005 at 04:48:32PM -0400, Daniel Barkalow wrote:\n> On Fri, 26 Aug 2005, Fredrik Kuivinen wrote:\n> \n> > I will try to describe how the algorithm works. The problem with the\n> > usual 3-way merge algorithm is that we sometimes do not have a unique\n> > common ancestor. In [1] B and C seems to be equally good. What this\n> > algorithm does is to _merge_ the common ancestors, in this case B and\n> > C, into a temporary tree lets call it T. It does then use this\n> > temporary tree T as the common ancestor for D and E to produce the\n> > final merge result. In the case described in [1] this will work out\n> > fine and we get a clean merge with the expected result.\n> \n> The only problem I can see with this is that it's likely to generate\n> conflicts between the shared heads, and the user is going to be confused\n> trying to resolve them, because the files with the conflicts will be\n> missing all of the more recent changes.\n\nI don't actually think that conflicts between shared heads is a\nproblem. Given the criss-cross case (we want to merge A and B into M):\n\n M\n |\\\n | \\\n A  B\n |\\/|\n |/\\|\n C  D\n | /\n |/\n E\n\nLets assume there is a merge conflict if we try to merge C and D\n(which are the two shared heads). Then both A and B 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 shared heads\" stage. Hence, when\nwe are merging C and D \"internally\" we will _not_ ask the user to\nresolve any eventual merge conflicts.\n\n> Other than that, I think it should\n> give the right answer, although it will presumably involve a lot of\n> ancient history doing the internal merge. (Which would probably be really\n> painful if you've got two branches that cross-merge regularly and never\n> actually completely sync)\n\nThe expensive part is the repeated merging. But as I wrote in my mail\nmultiple shared heads seems to be pretty uncommon. As far as I can\ntell there is no reason for the number of shared heads to increase as\na repository grows larger. However, this do probably depend on usage\npatterns.\n\nBut it is certainly possible to construct cases with an arbitrary\nnumber of shared heads. In which case the algorithm will be a bit\nslow, at least if there are real content merges going on which are\nhandled by merge(1).\n\n> I'm getting pretty close to having a version of read-tree that does the\n> trivial merge portion based comparing the sides against all of the shared\n> heads. I think yours will be better for the cases we've identified, giving\n> the correct answer for Tony's case rather than reporting a conflict, but\n> it's clearly more complicated. I think my changes are worthwhile anyway,\n> since they make the merging logic more central, but obviously\n> insufficient.\n> \n> I've been thinking that could be useful to have read-tree figure out the\n> history itself, instead of being passed ancestors, in which case it could\n> use your method, except more efficiently (and only look further at the\n> history when needed).\n\nIt will be interesting to have a look at the code when you are done.\nI find the Git architecture with respect to merging to be quite\nnice. A core which handles the simple cases _fast_ and let the more\ncomplicated cases be handled by someone else.\n\n- Fredrik\n"},{"id":"7822","messageId":"Pine.LNX.4.63.0508261748330.23242@iabervon.org","threadId":"1665","inReplyTo":"20050826213900.GA18880@c165.ib.student.liu.se","subject":"Re: [RFC, PATCH] A new merge algorithm (EXPERIMENTAL)","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2005-08-26T22:45:02Z","receivedAt":"2005-08-26T22:45:02Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Fri, 26 Aug 2005, Fredrik Kuivinen wrote:\n\n> On Fri, Aug 26, 2005 at 04:48:32PM -0400, Daniel Barkalow wrote:\n> > On Fri, 26 Aug 2005, Fredrik Kuivinen wrote:\n> >\n> > > I will try to describe how the algorithm works. The problem with the\n> > > usual 3-way merge algorithm is that we sometimes do not have a unique\n> > > common ancestor. In [1] B and C seems to be equally good. What this\n> > > algorithm does is to _merge_ the common ancestors, in this case B and\n> > > C, into a temporary tree lets call it T. It does then use this\n> > > temporary tree T as the common ancestor for D and E to produce the\n> > > final merge result. In the case described in [1] this will work out\n> > > fine and we get a clean merge with the expected result.\n> >\n> > The only problem I can see with this is that it's likely to generate\n> > conflicts between the shared heads, and the user is going to be confused\n> > trying to resolve them, because the files with the conflicts will be\n> > missing all of the more recent changes.\n>\n> I don't actually think that conflicts between shared heads is a\n> problem. Given the criss-cross case (we want to merge A and B into M):\n>\n>  M\n>  |\\\n>  | \\\n>  A  B\n>  |\\/|\n>  |/\\|\n>  C  D\n>  | /\n>  |/\n>  E\n>\n> Lets assume there is a merge conflict if we try to merge C and D\n> (which are the two shared heads). Then both A and B 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 shared heads\" stage. Hence, when\n> we are merging C and D \"internally\" we will _not_ ask the user to\n> resolve any eventual merge conflicts.\n\nOh, okay, didn't see that part. So the merge for M sees that the old\nconflict is replaced entire with the common resolution or with a conflict\nbetween the different resolutions, but it doesn't report the old conflict\nanyway, because that section's been replaced in both sides.\n\n> > Other than that, I think it should\n> > give the right answer, although it will presumably involve a lot of\n> > ancient history doing the internal merge. (Which would probably be really\n> > painful if you've got two branches that cross-merge regularly and never\n> > actually completely sync)\n>\n> The expensive part is the repeated merging. But as I wrote in my mail\n> multiple shared heads seems to be pretty uncommon. As far as I can\n> tell there is no reason for the number of shared heads to increase as\n> a repository grows larger. However, this do probably depend on usage\n> patterns.\n\nI'd guess that the number of shared heads will increase as the people's\nusage gets more flexible. If people expected good results, I could see the\nstable series being mostly done as patches to 2.6.X, which would then be\nmerged into various trees, and these would then be frequent common\nancestors in merges. I'd also not be surprised in Linus's tree were\nabnormally straightforward, due to stuff getting serialized in -mm.\n\n> > I'm getting pretty close to having a version of read-tree that does the\n> > trivial merge portion based comparing the sides against all of the shared\n> > heads. I think yours will be better for the cases we've identified, giving\n> > the correct answer for Tony's case rather than reporting a conflict, but\n> > it's clearly more complicated. I think my changes are worthwhile anyway,\n> > since they make the merging logic more central, but obviously\n> > insufficient.\n> >\n> > I've been thinking that could be useful to have read-tree figure out the\n> > history itself, instead of being passed ancestors, in which case it could\n> > use your method, except more efficiently (and only look further at the\n> > history when needed).\n>\n> It will be interesting to have a look at the code when you are done.\n> I find the Git architecture with respect to merging to be quite\n> nice. A core which handles the simple cases _fast_ and let the more\n> complicated cases be handled by someone else.\n\nRight; I'm mostly just trying to get the fast path to not miss cases that\nare more complicated than they look.\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"7823","messageId":"7v64tsb9en.fsf@assigned-by-dhcp.cox.net","threadId":"1665","inReplyTo":"20050826213900.GA18880@c165.ib.student.liu.se","subject":"Re: [RFC, PATCH] A new merge algorithm (EXPERIMENTAL)","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-08-26T22:50:08Z","receivedAt":"2005-08-26T22:50:08Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Fredrik Kuivinen <freku045@student.liu.se> writes:\n\n> I find the Git architecture with respect to merging to be quite\n> nice. A core which handles the simple cases _fast_ and let the more\n> complicated cases be handled by someone else.\n\nExactly my feeling.  The three-way read-tree was made to do\n\"trivial\" merges because the three-way merge operation is so\nfundamental and more importantly because in what it does there\nis no other plausible heuristics.  The cases that it leaves\nstages unmerged in the index file are cases that a merge policy\nmight want to use heuristics to affect the outcome, and are left\nfor merge-cache to resolve.  And it is a good thing.\n\nIf the updated read-tree reads more than three trees at once and\nmakes decision internally which ones to choose, it would be very\ndesirable to see an implementation in which there is _no_\nheuristics involved in the selection made by the built-in logic.\n\nIf there can be better selection made by more expensive logic,\nand faster but less reliable heuristics by cheaper logic, it\nwould be very nice for the selection logic to call out a helper\n\"merge policy\" program or dll module, just like the way\nmerge-cache calls merge-one-file-script, to make that decision.\n"},{"id":"7825","messageId":"Pine.LNX.4.58.0508261730480.3317@g5.osdl.org","threadId":"1665","inReplyTo":"20050826184731.GA13629@c165.ib.student.liu.se","subject":"Re: [RFC, PATCH] A new merge algorithm (EXPERIMENTAL)","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-08-27T00:38:21Z","receivedAt":"2005-08-27T00:38:21Z","isPatch":true,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Fri, 26 Aug 2005, Fredrik Kuivinen wrote:\n>\n> In real numbers it is as follows: In Linus' kernel tree there are\n> 5996 commits. 400 of those have more than one parent. Of those 400\n> merge commits 4 have more than one shared head.\n\nOk, that's already interesting in itself. I was wanting to re-run all the \nmerges with the new \"git-merge-base -a\" to see which merges might have had \ndifferent merge bases, and you've actually done that. Interesting to see \nthe numbers.\n\n> * Is it worth it? That is, is the added complexity in the merge logic\n>   worth the advantages of correctly handling some strange (but real\n>   life) merge cases?\n\nI am of two minds on this. I hate the notion of a more complex merge. But\nat the same time, it clearly is a very interesting case when we do have\nmultiple possible shared parents, and I think that at the very least we\nshould warn the user. And using a more complex merge algorithm when it\nhappens seems to be a very valid thing to do.\n\nAlso, it's possible that other developers see more of the criss-crossing\nmerges than I do - iow, they're probably more likely to happen in the\nthrow-away trees than in some of the main trees. Neither of the two cases\nwe've seen and had issues were merges I did, for example. Which means that\nyour \"1% of all merges\" number is probably low. Of course, it's quite\nlikely that in most cases, the \"pick either one\" approach will give the\nexact same result as the more complex merge.\n\nUsing python, which people have less exposure to, sounds like an \nadditional thorny issue..\n\n\t\tLinus\n"},{"id":"7826","messageId":"7vk6i89ofi.fsf@assigned-by-dhcp.cox.net","threadId":"1665","inReplyTo":"Pine.LNX.4.58.0508261730480.3317@g5.osdl.org","subject":"Re: [RFC, PATCH] A new merge algorithm (EXPERIMENTAL)","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-08-27T01:08:33Z","receivedAt":"2005-08-27T01:08:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> On Fri, 26 Aug 2005, Fredrik Kuivinen wrote:\n>>\n>> In real numbers it is as follows: In Linus' kernel tree there are\n>> 5996 commits. 400 of those have more than one parent. Of those 400\n>> merge commits 4 have more than one shared head.\n>\n> Ok, that's already interesting in itself. I was wanting to re-run all the \n> merges with the new \"git-merge-base -a\" to see which merges might have had \n> different merge bases, and you've actually done that. Interesting to see \n> the numbers.\n\nFredrik, mind giving us the commit ID of those four for us to\ntake a look at them?\n\n> I am of two minds on this. I hate the notion of a more complex merge. But\n> at the same time, it clearly is a very interesting case when we do have\n> multiple possible shared parents, and I think that at the very least we\n> should warn the user. And using a more complex merge algorithm when it\n> happens seems to be a very valid thing to do.\n\nI agree.  GIT is lightening fast for trivial cases and we can\nafford to spend more time to handle more complex ones carefully,\nat the same time telling the user what we are doing is a good thing.\n\n> Using python, which people have less exposure to, sounds like an \n> additional thorny issue..\n\nNot too big a problem for me to follow the patch ;-).\n"},{"id":"7834","messageId":"20050827014009.GB18880@c165.ib.student.liu.se","threadId":"1665","inReplyTo":"7vk6i89ofi.fsf@assigned-by-dhcp.cox.net","subject":"Re: [RFC, PATCH] A new merge algorithm (EXPERIMENTAL)","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-08-27T01:40:09Z","receivedAt":"2005-08-27T01:40:09Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"On Fri, Aug 26, 2005 at 06:08:33PM -0700, Junio C Hamano wrote:\n> Linus Torvalds <torvalds@osdl.org> writes:\n> \n> > On Fri, 26 Aug 2005, Fredrik Kuivinen wrote:\n> >>\n> >> In real numbers it is as follows: In Linus' kernel tree there are\n> >> 5996 commits. 400 of those have more than one parent. Of those 400\n> >> merge commits 4 have more than one shared head.\n> >\n> > Ok, that's already interesting in itself. I was wanting to re-run all the \n> > merges with the new \"git-merge-base -a\" to see which merges might have had \n> > different merge bases, and you've actually done that. Interesting to see \n> > the numbers.\n> \n> Fredrik, mind giving us the commit ID of those four for us to\n> take a look at them?\n\nSure, they are:\n467ca22d3371f132ee225a5591a1ed0cd518cb3d which has two shared heads\n7e2987503dda95a5f80290bb8c06279009c2419e and\neff910a91ac04ab1d9e210d4f721484af3b39c8d\n\n0e396ee43e445cb7c215a98da4e76d0ce354d9d7 with the heads\n462cee296476278acaa54c41925b3273e0e4dd40 and\n8be3de3fd8469154a2b3e18a4712032dac5b4a53\n\n3190186362466658f01b2e354e639378ce07e1a9 with\n38d84c3bd6dd22bdb1f797c87006931133d71aea and\n46906c4415f88cebfad530917bada0835d651824\n\nand finally\n\nda28c12089dfcfb8695b6b555cdb8e03dda2b690 with\n9e566d8bd61f939b7f5d7d969f5b178571471cf9 and\n18190cc08d70a6ec8ef69f0f6ede021f7cb3f9b8\n\n(The script which finds those commits also prints out the commit id of\nany octopus commits. There is one commit with more than two parents in\nthe kernel repository,\n13e652800d1644dfedcd0d59ac95ef0beb7f3165. However, it only looks like\nthat commit has three parents, two of them are actually identical.)\n\n> > I am of two minds on this. I hate the notion of a more complex merge. But\n> > at the same time, it clearly is a very interesting case when we do have\n> > multiple possible shared parents, and I think that at the very least we\n> > should warn the user. And using a more complex merge algorithm when it\n> > happens seems to be a very valid thing to do.\n> \n> I agree.  GIT is lightening fast for trivial cases and we can\n> afford to spend more time to handle more complex ones carefully,\n> at the same time telling the user what we are doing is a good thing.\n> \n> > Using python, which people have less exposure to, sounds like an \n> > additional thorny issue..\n> \n> Not too big a problem for me to follow the patch ;-).\n> \n\nGood to know :)\n\nI mainly wanted to try the idea with the new algorithm, so some kind\nof high level language seemed like a good choice.\n\n- Fredrik\n"}]}