{"thread":{"id":"2002","subject":"[PATCH] Teach the recursive merge strategy about renames.","startedAt":"2005-10-02T15:43:07Z","lastAt":"2005-10-02T15:43:07Z","messageCount":1,"participants":["Fredrik Kuivinen"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"9612","messageId":"20051002154307.GB1685@c165.ib.student.liu.se","threadId":"2002","inReplyTo":null,"subject":"[PATCH] Teach the recursive merge strategy about renames.","fromName":"Fredrik Kuivinen","fromEmail":"freku045@student.liu.se","sentAt":"2005-10-02T15:43:07Z","receivedAt":"2005-10-02T15:43:07Z","isPatch":true,"sender":{"key":"frekui@gmail.com","avatar":"https://avatars.githubusercontent.com/u/13770967?v=4"},"body":"It will now merge cases where a file was renamed in one branch and\nmodified in the other branch cleanly. We also detect a couple of\nconflict cases now that wasn't detected before.\n\nSigned-off-by: Fredrik Kuivinen <freku045@student.liu.se>\n\n\n---\n\nThis patch turned out to be quite large.\n\nI have tested it on all the problematic merge cases that have been\nreported on this list, all multiple common ancestor cases in Thomas\nGleixner's historic Linux repository and a number of handcrafted test\ncases.\n\nWith the patch the recursive merge strategy produces correct result\nfor all those merge commits (with one possible exception, see below).\nWith 'correct result' I mean that one of the following cases occur:\n\n1. The merge is clean and the result match the committed tree.\n2. The merge is non-clean.\n3. The merge is clean and the difference from the committed tree can\n   be explained. One commit which is in this category is Tony Luck's\n   merge (<200508232256.j7NMuR1q027892@agluck-lia64.sc.intel.com>).\n\nThe possible exception is commit\n091cced38d83732ee3212806ef5ea07abbef01fe in the historic repository.\nI have still not managed to find out what the correct result should be\nin this case. The recursive strategy merges it cleanly and the result\ndiffers from what was actually committed. The resolve strategy\nproduces a non-clean result.\n\nThere are 409 merge commits in the historic repository which has more\nthan one common ancestor. Of those 409 commits 26 are merged\nnon-cleanly by the recursive strategy. Everything else, except\n091cce..., is merged cleanly and correctly.\n\nWith the resolve strategy we get 73 non-clean results and five cases\nwhich are merged cleanly but the result do not match what was\ncommitted.\n\n\n git-merge-recursive.py |  794 +++++++++++++++++++++++++++++++++++++-----------\n 1 files changed, 605 insertions(+), 189 deletions(-)\n\neccd8d673e2401ed2495272204b42173214ae27c\ndiff --git a/git-merge-recursive.py b/git-merge-recursive.py\n--- a/git-merge-recursive.py\n+++ b/git-merge-recursive.py\n@@ -7,9 +7,6 @@ from sets import Set\n sys.path.append('@@GIT_PYTHON_PATH@@')\n from gitMergeCommon import *\n \n-# The actual merge code\n-# ---------------------\n-\n originalIndexFile = os.environ.get('GIT_INDEX_FILE',\n                                    os.environ.get('GIT_DIR', '.git') + '/index')\n temporaryIndexFile = os.environ.get('GIT_DIR', '.git') + \\\n@@ -21,11 +18,23 @@ def setupIndex(temporary):\n         pass\n     if temporary:\n         newIndex = temporaryIndexFile\n-        os.environ\n     else:\n         newIndex = originalIndexFile\n     os.environ['GIT_INDEX_FILE'] = newIndex\n \n+# This is a global variable which is used in a number of places but\n+# only written to in the 'merge' function.\n+\n+# cacheOnly == True  => Don't leave any non-stage 0 entries in the cache and\n+#                       don't update the working directory.\n+#              False => Leave unmerged entries in the cache and update\n+#                       the working directory.\n+\n+cacheOnly = False\n+\n+# The entry point to the merge code\n+# ---------------------------------\n+\n def merge(h1, h2, branch1Name, branch2Name, graph, callDepth=0):\n     '''Merge the commits h1 and h2, return the resulting virtual\n     commit object and a flag indicating the cleaness of the merge.'''\n@@ -35,6 +44,7 @@ def merge(h1, h2, branch1Name, branch2Na\n     def infoMsg(*args):\n         sys.stdout.write('  '*callDepth)\n         printList(args)\n+\n     infoMsg('Merging:')\n     infoMsg(h1)\n     infoMsg(h2)\n@@ -46,27 +56,27 @@ def merge(h1, h2, branch1Name, branch2Na\n         infoMsg(x)\n     sys.stdout.flush()\n \n-    Ms = ca[0]\n+    mergedCA = ca[0]\n     for h in ca[1:]:\n-        [Ms, ignore] = merge(Ms, h,\n-                             'Temporary shared merge branch 1',\n-                             'Temporary shared merge branch 2',\n-                             graph, callDepth+1)\n-        assert(isinstance(Ms, Commit))\n+        [mergedCA, dummy] = merge(mergedCA, h,\n+                                  'Temporary shared merge branch 1',\n+                                  'Temporary shared merge branch 2',\n+                                  graph, callDepth+1)\n+        assert(isinstance(mergedCA, Commit))\n \n+    global cacheOnly\n     if callDepth == 0:\n         setupIndex(False)\n-        cleanCache = False\n+        cacheOnly = False\n     else:\n         setupIndex(True)\n         runProgram(['git-read-tree', h1.tree()])\n-        cleanCache = True\n+        cacheOnly = True\n \n-    [shaRes, clean] = mergeTrees(h1.tree(), h2.tree(), Ms.tree(),\n-                                 branch1Name, branch2Name,\n-                                 cleanCache)\n+    [shaRes, clean] = mergeTrees(h1.tree(), h2.tree(), mergedCA.tree(),\n+                                 branch1Name, branch2Name)\n \n-    if clean or cleanCache:\n+    if clean or cacheOnly:\n         res = Commit(None, [h1, h2], tree=shaRes)\n         graph.addNode(res)\n     else:\n@@ -89,16 +99,255 @@ def getFilesAndDirs(tree):\n \n     return [files, dirs]\n \n+# Those two global variables are used in a number of places but only\n+# written to in 'mergeTrees' and 'uniquePath'. They keep track of\n+# every file and directory in the two branches that are about to be\n+# merged.\n+currentFileSet = None\n+currentDirectorySet = None\n+\n+def mergeTrees(head, merge, common, branch1Name, branch2Name):\n+    '''Merge the trees 'head' and 'merge' with the common ancestor\n+    'common'. The name of the head branch is 'branch1Name' and the name of\n+    the merge branch is 'branch2Name'. Return a tuple (tree, cleanMerge)\n+    where tree is the resulting tree and cleanMerge is True iff the\n+    merge was clean.'''\n+    \n+    assert(isSha(head) and isSha(merge) and isSha(common))\n+\n+    if common == merge:\n+        print 'Already uptodate!'\n+        return [head, True]\n+\n+    if cacheOnly:\n+        updateArg = '-i'\n+    else:\n+        updateArg = '-u'\n+\n+    [out, code] = runProgram(['git-read-tree', updateArg, '-m',\n+                                common, head, merge], returnCode = True)\n+    if code != 0:\n+        die('git-read-tree:', out)\n+\n+    [tree, code] = runProgram('git-write-tree', returnCode=True)\n+    tree = tree.rstrip()\n+    if code != 0:\n+        global currentFileSet, currentDirectorySet\n+        [currentFileSet, currentDirectorySet] = getFilesAndDirs(head)\n+        [filesM, dirsM] = getFilesAndDirs(merge)\n+        currentFileSet.union_update(filesM)\n+        currentDirectorySet.union_update(dirsM)\n+\n+        entries = unmergedCacheEntries()\n+        renamesHead =  getRenames(head, common, head, merge, entries)\n+        renamesMerge = getRenames(merge, common, head, merge, entries)\n+\n+        cleanMerge = processRenames(renamesHead, renamesMerge,\n+                                    branch1Name, branch2Name)\n+        for entry in entries:\n+            if entry.processed:\n+                continue\n+            if not processEntry(entry, branch1Name, branch2Name):\n+                cleanMerge = False\n+                \n+        if cleanMerge or cacheOnly:\n+            tree = runProgram('git-write-tree').rstrip()\n+        else:\n+            tree = None\n+    else:\n+        cleanMerge = True\n+\n+    return [tree, cleanMerge]\n+\n+# Low level file merging, update and removal\n+# ------------------------------------------\n+\n+def mergeFile(oPath, oSha, oMode, aPath, aSha, aMode, bPath, bSha, bMode,\n+              branch1Name, branch2Name):\n+\n+    merge = False\n+    clean = True\n+\n+    if stat.S_IFMT(aMode) != stat.S_IFMT(bMode):\n+        clean = False\n+        if stat.S_ISREG(aMode):\n+            mode = aMode\n+            sha = aSha\n+        else:\n+            mode = bMode\n+            sha = bSha\n+    else:\n+        if aSha != oSha and bSha != oSha:\n+            merge = True\n+\n+        if aMode == oMode:\n+            mode = bMode\n+        else:\n+            mode = aMode\n+\n+        if aSha == oSha:\n+            sha = bSha\n+        elif bSha == oSha:\n+            sha = aSha\n+        elif stat.S_ISREG(aMode):\n+            assert(stat.S_ISREG(bMode))\n+\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, code] = runProgram(['merge',\n+                                      '-L', branch1Name + '/' + aPath,\n+                                      '-L', 'orig/' + oPath,\n+                                      '-L', branch2Name + '/' + bPath,\n+                                      src1, orig, src2], returnCode=True)\n+\n+            sha = runProgram(['git-hash-object', '-t', 'blob', '-w',\n+                              src1]).rstrip()\n+\n+            os.unlink(orig)\n+            os.unlink(src1)\n+            os.unlink(src2)\n+            \n+            clean = (code == 0)\n+        else:\n+            assert(stat.S_ISLNK(aMode) and stat.S_ISLNK(bMode))\n+            sha = aSha\n+\n+            if aSha != bSha:\n+                clean = False\n+\n+    return [sha, mode, clean, merge]\n+\n+def updateFile(clean, sha, mode, path):\n+    updateCache = cacheOnly or clean\n+    updateWd = not cacheOnly\n+\n+    return updateFileExt(sha, mode, path, updateCache, updateWd)\n+\n+def updateFileExt(sha, mode, path, updateCache, updateWd):\n+    if cacheOnly:\n+        updateWd = False\n+\n+    if updateWd:\n+        pathComponents = path.split('/')\n+        for x in xrange(1, len(pathComponents)):\n+            p = '/'.join(pathComponents[0:x])\n+\n+            try:\n+                createDir = not stat.S_ISDIR(os.lstat(p).st_mode)\n+            except: \n+                createDir = True\n+            \n+            if createDir:\n+                try:\n+                    os.mkdir(p)\n+                except OSError, e:\n+                    die(\"Couldn't create directory\", p, e.strerror)\n+\n+        prog = ['git-cat-file', 'blob', sha]\n+        if stat.S_ISREG(mode):\n+            try:\n+                os.unlink(path)\n+            except OSError:\n+                pass\n+            if mode & 0100:\n+                mode = 0777\n+            else:\n+                mode = 0666\n+            fd = os.open(path, os.O_WRONLY | os.O_TRUNC | os.O_CREAT, mode)\n+            proc = subprocess.Popen(prog, stdout=fd)\n+            proc.wait()\n+            os.close(fd)\n+        elif stat.S_ISLNK(mode):\n+            linkTarget = runProgram(prog)\n+            os.symlink(linkTarget, path)\n+        else:\n+            assert(False)\n+\n+    if updateWd and updateCache:\n+        runProgram(['git-update-index', '--add', '--', path])\n+    elif updateCache:\n+        runProgram(['git-update-index', '--add', '--cacheinfo',\n+                    '0%o' % mode, sha, path])\n+\n+def removeFile(clean, path):\n+    updateCache = cacheOnly or clean\n+    updateWd = not cacheOnly\n+\n+    if updateCache:\n+        runProgram(['git-update-index', '--force-remove', '--', path])\n+\n+    if updateWd:\n+        try:\n+            os.unlink(path)\n+        except OSError, e:\n+            if e.errno != errno.ENOENT and e.errno != errno.EISDIR:\n+                raise\n+\n+def uniquePath(path, branch):\n+    def fileExists(path):\n+        try:\n+            os.lstat(path)\n+            return True\n+        except OSError, e:\n+            if e.errno == errno.ENOENT:\n+                return False\n+            else:\n+                raise\n+\n+    newPath = path + '_' + branch\n+    suffix = 0\n+    while newPath in currentFileSet or \\\n+          newPath in currentDirectorySet  or \\\n+          fileExists(newPath):\n+        suffix += 1\n+        newPath = path + '_' + branch + '_' + str(suffix)\n+    currentFileSet.add(newPath)\n+    return newPath\n+\n+# Cache entry management\n+# ----------------------\n+\n class CacheEntry:\n     def __init__(self, path):\n         class Stage:\n             def __init__(self):\n                 self.sha1 = None\n                 self.mode = None\n+\n+            # Used for debugging only\n+            def __str__(self):\n+                if self.mode != None:\n+                    m = '0%o' % self.mode\n+                else:\n+                    m = 'None'\n+\n+                if self.sha1:\n+                    sha1 = self.sha1\n+                else:\n+                    sha1 = 'None'\n+                return 'sha1: ' + sha1 + ' mode: ' + m\n         \n-        self.stages = [Stage(), Stage(), Stage()]\n+        self.stages = [Stage(), Stage(), Stage(), Stage()]\n         self.path = path\n+        self.processed = False\n+\n+    def __str__(self):\n+        return 'path: ' + self.path + ' stages: ' + repr([str(x) for x in self.stages])\n+\n+class CacheEntryContainer:\n+    def __init__(self):\n+        self.entries = {}\n+\n+    def add(self, entry):\n+        self.entries[entry.path] = entry\n \n+    def get(self, path):\n+        return self.entries.get(path)\n+\n+    def __iter__(self):\n+        return self.entries.itervalues()\n+    \n unmergedRE = re.compile(r'^([0-7]+) ([0-9a-f]{40}) ([1-3])\\t(.*)$', re.S)\n def unmergedCacheEntries():\n     '''Create a dictionary mapping file names to CacheEntry\n@@ -108,155 +357,340 @@ def unmergedCacheEntries():\n     lines = runProgram(['git-ls-files', '-z', '--unmerged']).split('\\0')\n     lines.pop()\n \n-    res = {}\n+    res = CacheEntryContainer()\n     for l in lines:\n         m = unmergedRE.match(l)\n         if m:\n             mode = int(m.group(1), 8)\n             sha1 = m.group(2)\n-            stage = int(m.group(3)) - 1\n+            stage = int(m.group(3))\n             path = m.group(4)\n \n-            if res.has_key(path):\n-                e = res[path]\n-            else:\n+            e = res.get(path)\n+            if not e:\n                 e = CacheEntry(path)\n-                res[path] = e\n-                \n+                res.add(e)\n+\n             e.stages[stage].mode = mode\n             e.stages[stage].sha1 = sha1\n         else:\n-            die('Error: Merge program failed: Unexpected output from', \\\n+            die('Error: Merge program failed: Unexpected output from',\n                 'git-ls-files:', l)\n     return res\n \n-def mergeTrees(head, merge, common, branch1Name, branch2Name,\n-               cleanCache):\n-    '''Merge the trees 'head' and 'merge' with the common ancestor\n-    'common'. The name of the head branch is 'branch1Name' and the name of\n-    the merge branch is 'branch2Name'. Return a tuple (tree, cleanMerge)\n-    where tree is the resulting tree and cleanMerge is True iff the\n-    merge was clean.'''\n+lsTreeRE = re.compile(r'^([0-7]+) (\\S+) ([0-9a-f]{40})\\t(.*)\\n$', re.S)\n+def getCacheEntry(path, origTree, aTree, bTree):\n+    '''Returns a CacheEntry object which doesn't have to correspond to\n+    a real cache entry in Git's index.'''\n     \n-    assert(isSha(head) and isSha(merge) and isSha(common))\n+    def parse(out):\n+        if out == '':\n+            return [None, None]\n+        else:\n+            m = lsTreeRE.match(out)\n+            if not m:\n+                die('Unexpected output from git-ls-tree:', out)\n+            elif m.group(2) == 'blob':\n+                return [m.group(3), int(m.group(1), 8)]\n+            else:\n+                return [None, None]\n \n-    if common == merge:\n-        print 'Already uptodate!'\n-        return [head, True]\n+    res = CacheEntry(path)\n \n-    if cleanCache:\n-        updateArg = '-i'\n+    [oSha, oMode] = parse(runProgram(['git-ls-tree', origTree, '--', path]))\n+    [aSha, aMode] = parse(runProgram(['git-ls-tree', aTree, '--', path]))\n+    [bSha, bMode] = parse(runProgram(['git-ls-tree', bTree, '--', path]))\n+\n+    res.stages[1].sha1 = oSha\n+    res.stages[1].mode = oMode\n+    res.stages[2].sha1 = aSha\n+    res.stages[2].mode = aMode\n+    res.stages[3].sha1 = bSha\n+    res.stages[3].mode = bMode\n+\n+    return res\n+\n+# Rename detection and handling\n+# -----------------------------\n+\n+class RenameEntry:\n+    def __init__(self,\n+                 src, srcSha, srcMode, srcCacheEntry,\n+                 dst, dstSha, dstMode, dstCacheEntry,\n+                 score):\n+        self.srcName = src\n+        self.srcSha = srcSha\n+        self.srcMode = srcMode\n+        self.srcCacheEntry = srcCacheEntry\n+        self.dstName = dst\n+        self.dstSha = dstSha\n+        self.dstMode = dstMode\n+        self.dstCacheEntry = dstCacheEntry\n+        self.score = score\n+\n+        self.processed = False\n+\n+class RenameEntryContainer:\n+    def __init__(self):\n+        self.entriesSrc = {}\n+        self.entriesDst = {}\n+\n+    def add(self, entry):\n+        self.entriesSrc[entry.srcName] = entry\n+        self.entriesDst[entry.dstName] = entry\n+\n+    def getSrc(self, path):\n+        return self.entriesSrc.get(path)\n+\n+    def getDst(self, path):\n+        return self.entriesDst.get(path)\n+\n+    def __iter__(self):\n+        return self.entriesSrc.itervalues()\n+\n+parseDiffRenamesRE = re.compile('^:([0-7]+) ([0-7]+) ([0-9a-f]{40}) ([0-9a-f]{40}) R([0-9]*)$')\n+def getRenames(tree, oTree, aTree, bTree, cacheEntries):\n+    '''Get information of all renames which occured between 'oTree' and\n+    'tree'. We need the three trees in the merge ('oTree', 'aTree' and\n+    'bTree') to be able to associate the correct cache entries with\n+    the rename information. 'tree' is always equal to either aTree or bTree.'''\n+\n+    assert(tree == aTree or tree == bTree)\n+    inp = runProgram(['git-diff-tree', '-M', '--diff-filter=R', '-r',\n+                      '-z', oTree, tree])\n+\n+    ret = RenameEntryContainer()\n+    try:\n+        recs = inp.split(\"\\0\")\n+        recs.pop() # remove last entry (which is '')\n+        it = recs.__iter__()\n+        while True:\n+            rec = it.next()\n+            m = parseDiffRenamesRE.match(rec)\n+\n+            if not m:\n+                die('Unexpected output from git-diff-tree:', rec)\n+\n+            srcMode = int(m.group(1), 8)\n+            dstMode = int(m.group(2), 8)\n+            srcSha = m.group(3)\n+            dstSha = m.group(4)\n+            score = m.group(5)\n+            src = it.next()\n+            dst = it.next()\n+\n+            srcCacheEntry = cacheEntries.get(src)\n+            if not srcCacheEntry:\n+                srcCacheEntry = getCacheEntry(src, oTree, aTree, bTree)\n+                cacheEntries.add(srcCacheEntry)\n+\n+            dstCacheEntry = cacheEntries.get(dst)\n+            if not dstCacheEntry:\n+                dstCacheEntry = getCacheEntry(dst, oTree, aTree, bTree)\n+                cacheEntries.add(dstCacheEntry)\n+\n+            ret.add(RenameEntry(src, srcSha, srcMode, srcCacheEntry,\n+                                dst, dstSha, dstMode, dstCacheEntry,\n+                                score))\n+    except StopIteration:\n+        pass\n+    return ret\n+\n+def fmtRename(src, dst):\n+    srcPath = src.split('/')\n+    dstPath = dst.split('/')\n+    path = []\n+    endIndex = min(len(srcPath), len(dstPath)) - 1\n+    for x in range(0, endIndex):\n+        if srcPath[x] == dstPath[x]:\n+            path.append(srcPath[x])\n+        else:\n+            endIndex = x\n+            break\n+\n+    if len(path) > 0:\n+        return '/'.join(path) + \\\n+               '/{' + '/'.join(srcPath[endIndex:]) + ' => ' + \\\n+               '/'.join(dstPath[endIndex:]) + '}'\n     else:\n-        updateArg = '-u'\n+        return src + ' => ' + dst\n \n-    [out, code] = runProgram(['git-read-tree', updateArg, '-m', common, head, merge], returnCode = True)\n-    if code != 0:\n-        die('git-read-tree:', out)\n+def processRenames(renamesA, renamesB, branchNameA, branchNameB):\n+    srcNames = Set()\n+    for x in renamesA:\n+        srcNames.add(x.srcName)\n+    for x in renamesB:\n+        srcNames.add(x.srcName)\n \n     cleanMerge = True\n-\n-    [tree, code] = runProgram('git-write-tree', returnCode=True)\n-    tree = tree.rstrip()\n-    if code != 0:\n-        [files, dirs] = getFilesAndDirs(head)\n-        [filesM, dirsM] = getFilesAndDirs(merge)\n-        files.union_update(filesM)\n-        dirs.union_update(dirsM)\n+    for path in srcNames:\n+        if renamesA.getSrc(path):\n+            renames1 = renamesA\n+            renames2 = renamesB\n+            branchName1 = branchNameA\n+            branchName2 = branchNameB\n+        else:\n+            renames1 = renamesB\n+            renames2 = renamesA\n+            branchName1 = branchNameB\n+            branchName2 = branchNameA\n         \n-        cleanMerge = True\n-        entries = unmergedCacheEntries()\n-        for name in entries:\n-            if not processEntry(entries[name], branch1Name, branch2Name,\n-                                files, dirs, cleanCache):\n+        ren1 = renames1.getSrc(path)\n+        ren2 = renames2.getSrc(path)\n+\n+        ren1.dstCacheEntry.processed = True\n+        ren1.srcCacheEntry.processed = True\n+\n+        if ren1.processed:\n+            continue\n+\n+        ren1.processed = True\n+        removeFile(True, ren1.srcName)\n+        if ren2:\n+            # Renamed in 1 and renamed in 2\n+            assert(ren1.srcName == ren2.srcName)\n+            ren2.dstCacheEntry.processed = True\n+            ren2.processed = True\n+\n+            if ren1.dstName != ren2.dstName:\n+                print 'CONFLICT (rename/rename): Rename', \\\n+                      fmtRename(path, ren1.dstName), 'in branch', branchName1, \\\n+                      'rename', fmtRename(path, ren2.dstName), 'in', branchName2\n                 cleanMerge = False\n-                \n-        if cleanMerge or cleanCache:\n-            tree = runProgram('git-write-tree').rstrip()\n-        else:\n-            tree = None\n-    else:\n-        cleanMerge = True\n \n-    return [tree, cleanMerge]\n+                if ren1.dstName in currentDirectorySet:\n+                    dstName1 = uniquePath(ren1.dstName, branchName1)\n+                    print ren1.dstName, 'is a directory in', branchName2, \\\n+                          'adding as', dstName1, 'instead.'\n+                    removeFile(False, ren1.dstName)\n+                else:\n+                    dstName1 = ren1.dstName\n \n-def processEntry(entry, branch1Name, branch2Name, files, dirs, cleanCache):\n-    '''Merge one cache entry. 'files' is a Set with the files in both of\n-    the heads that we are going to merge. 'dirs' contains the\n-    corresponding data for directories. If 'cleanCache' is True no\n-    non-zero stages will be left in the cache for the path\n-    corresponding to the entry 'entry'.'''\n-\n-# cleanCache == True  => Don't leave any non-stage 0 entries in the cache and\n-#                        don't update the working directory\n-#               False => Leave unmerged entries and update the working directory\n-\n-# clean     == True  => non-conflict case\n-#              False => conflict case\n-\n-# If cleanCache == False then the cache shouldn't be updated if clean == False\n-\n-    def updateFile(clean, sha, mode, path, onlyWd=False):\n-        updateCache = not onlyWd and (cleanCache or (not cleanCache and clean))\n-        updateWd = onlyWd or (not cleanCache and clean)\n-\n-        if updateWd:\n-            prog = ['git-cat-file', 'blob', sha]\n-            if stat.S_ISREG(mode):\n-                try:\n-                    os.unlink(path)\n-                except OSError:\n-                    pass\n-                if mode & 0100:\n-                    mode = 0777\n+                if ren2.dstName in currentDirectorySet:\n+                    dstName2 = uniquePath(ren2.dstName, branchName2)\n+                    print ren2.dstName, 'is a directory in', branchName1, \\\n+                          'adding as', dstName2, 'instead.'\n+                    removeFile(False, ren2.dstName)\n                 else:\n-                    mode = 0666\n-                fd = os.open(path, os.O_WRONLY | os.O_TRUNC | os.O_CREAT, mode)\n-                proc = subprocess.Popen(prog, stdout=fd)\n-                proc.wait()\n-                os.close(fd)\n-            elif stat.S_ISLNK(mode):\n-                linkTarget = runProgram(prog)\n-                os.symlink(linkTarget, path)\n+                    dstName2 = ren1.dstName\n+\n+                updateFile(False, ren1.dstSha, ren1.dstMode, dstName1)\n+                updateFile(False, ren2.dstSha, ren2.dstMode, dstName2)\n             else:\n-                assert(False)\n+                print 'Renaming', fmtRename(path, ren1.dstName)\n+                [resSha, resMode, clean, merge] = \\\n+                         mergeFile(ren1.srcName, ren1.srcSha, ren1.srcMode,\n+                                   ren1.dstName, ren1.dstSha, ren1.dstMode,\n+                                   ren2.dstName, ren2.dstSha, ren2.dstMode,\n+                                   branchName1, branchName2)\n+\n+                if merge:\n+                    print 'Auto-merging', ren1.dstName\n+\n+                if not clean:\n+                    print 'CONFLICT (content): merge conflict in', ren1.dstName\n+                    cleanMerge = False\n+\n+                    if not cacheOnly:\n+                        updateFileExt(ren1.dstSha, ren1.dstMode, ren1.dstName,\n+                                      updateCache=True, updateWd=False)\n+                updateFile(clean, resSha, resMode, ren1.dstName)\n+        else:\n+            # Renamed in 1, maybe changed in 2\n+            if renamesA == renames1:\n+                stage = 3\n+            else:\n+                stage = 2\n+                \n+            srcShaOtherBranch  = ren1.srcCacheEntry.stages[stage].sha1\n+            srcModeOtherBranch = ren1.srcCacheEntry.stages[stage].mode\n \n-        if updateWd and updateCache:\n-            runProgram(['git-update-index', '--add', '--', path])\n-        elif updateCache:\n-            runProgram(['git-update-index', '--add', '--cacheinfo',\n-                        '0%o' % mode, sha, path])\n-\n-    def removeFile(clean, path):\n-        if cleanCache or (not cleanCache and clean):\n-            runProgram(['git-update-index', '--force-remove', '--', path])\n+            dstShaOtherBranch  = ren1.dstCacheEntry.stages[stage].sha1\n+            dstModeOtherBranch = ren1.dstCacheEntry.stages[stage].mode\n \n-        if not cleanCache and clean:\n-            try:\n-                os.unlink(path)\n-            except OSError, e:\n-                if e.errno != errno.ENOENT and e.errno != errno.EISDIR:\n-                    raise\n-\n-    def uniquePath(path, branch):\n-        newPath = path + '_' + branch\n-        suffix = 0\n-        while newPath in files or newPath in dirs:\n-            suffix += 1\n-            newPath = path + '_' + branch + '_' + str(suffix)\n-        files.add(newPath)\n-        return newPath\n+            tryMerge = False\n+            \n+            if ren1.dstName in currentDirectorySet:\n+                newPath = uniquePath(ren1.dstName, branchName1)\n+                print 'CONFLICT (rename/directory): Rename', \\\n+                      fmtRename(ren1.srcName, ren1.dstName), 'in', branchName1,\\\n+                      'directory', ren1.dstName, 'added in', branchName2\n+                print 'Renaming', ren1.srcName, 'to', newPath, 'instead'\n+                cleanMerge = False\n+                removeFile(False, ren1.dstName)\n+                updateFile(False, ren1.dstSha, ren1.dstMode, newPath)\n+            elif srcShaOtherBranch == None:\n+                print 'CONFLICT (rename/delete): Rename', \\\n+                      fmtRename(ren1.srcName, ren1.dstName), 'in', \\\n+                      branchName1, 'and deleted in', branchName2\n+                cleanMerge = False\n+                updateFile(False, ren1.dstSha, ren1.dstMode, ren1.dstName)\n+            elif dstShaOtherBranch:\n+                newPath = uniquePath(ren1.dstName, branchName2)\n+                print 'CONFLICT (rename/add): Rename', \\\n+                      fmtRename(ren1.srcName, ren1.dstName), 'in', \\\n+                      branchName1 + '.', ren1.dstName, 'added in', branchName2\n+                print 'Adding as', newPath, 'instead'\n+                updateFile(False, dstShaOtherBranch, dstModeOtherBranch, newPath)\n+                cleanMerge = False\n+                tryMerge = True\n+            elif renames2.getDst(ren1.dstName):\n+                dst2 = renames2.getDst(ren1.dstName)\n+                newPath1 = uniquePath(ren1.dstName, branchName1)\n+                newPath2 = uniquePath(dst2.dstName, branchName2)\n+                print 'CONFLICT (rename/rename): Rename', \\\n+                      fmtRename(ren1.srcName, ren1.dstName), 'in', \\\n+                      branchName1+'. Rename', \\\n+                      fmtRename(dst2.srcName, dst2.dstName), 'in', branchName2\n+                print 'Renaming', ren1.srcName, 'to', newPath1, 'and', \\\n+                      dst2.srcName, 'to', newPath2, 'instead'\n+                removeFile(False, ren1.dstName)\n+                updateFile(False, ren1.dstSha, ren1.dstMode, newPath1)\n+                updateFile(False, dst2.dstSha, dst2.dstMode, newPath2)\n+                dst2.processed = True\n+                cleanMerge = False\n+            else:\n+                tryMerge = True\n+\n+            if tryMerge:\n+                print 'Renaming', fmtRename(ren1.srcName, ren1.dstName)\n+                [resSha, resMode, clean, merge] = \\\n+                         mergeFile(ren1.srcName, ren1.srcSha, ren1.srcMode,\n+                                   ren1.dstName, ren1.dstSha, ren1.dstMode,\n+                                   ren1.srcName, srcShaOtherBranch, srcModeOtherBranch,\n+                                   branchName1, branchName2)\n+\n+                if merge:\n+                    print 'Auto-merging', ren1.dstName\n+\n+                if not clean:\n+                    print 'CONFLICT (rename/modify): Merge conflict in', ren1.dstName\n+                    cleanMerge = False\n+\n+                    if not cacheOnly:\n+                        updateFileExt(ren1.dstSha, ren1.dstMode, ren1.dstName,\n+                                      updateCache=True, updateWd=False)\n+                updateFile(clean, resSha, resMode, ren1.dstName)\n+\n+    return cleanMerge\n \n-    debug('processing', entry.path, 'clean cache:', cleanCache)\n+# Per entry merge function\n+# ------------------------\n+\n+def processEntry(entry, branch1Name, branch2Name):\n+    '''Merge one cache entry.'''\n+\n+    debug('processing', entry.path, 'clean cache:', cacheOnly)\n \n     cleanMerge = True\n \n     path = entry.path\n-    oSha = entry.stages[0].sha1\n-    oMode = entry.stages[0].mode\n-    aSha = entry.stages[1].sha1\n-    aMode = entry.stages[1].mode\n-    bSha = entry.stages[2].sha1\n-    bMode = entry.stages[2].mode\n+    oSha = entry.stages[1].sha1\n+    oMode = entry.stages[1].mode\n+    aSha = entry.stages[2].sha1\n+    aMode = entry.stages[2].mode\n+    bSha = entry.stages[3].sha1\n+    bMode = entry.stages[3].mode\n \n     assert(oSha == None or isSha(oSha))\n     assert(aSha == None or isSha(aSha))\n@@ -275,28 +709,26 @@ def processEntry(entry, branch1Name, bra\n            (not aSha     and bSha == oSha):\n     # Deleted in both or deleted in one and unchanged in the other\n             if aSha:\n-                print 'Removing ' + path\n+                print 'Removing', path\n             removeFile(True, path)\n         else:\n     # Deleted in one and changed in the other\n             cleanMerge = False\n             if not aSha:\n-                print 'CONFLICT (del/mod): \"' + path + '\" deleted in', \\\n-                      branch1Name, 'and modified in', branch2Name, \\\n-                      '. Version', branch2Name, ' of \"' + path + \\\n-                      '\" left in tree'\n+                print 'CONFLICT (delete/modify):', path, 'deleted in', \\\n+                      branch1Name, 'and modified in', branch2Name + '.', \\\n+                      'Version', branch2Name, 'of', path, 'left in tree.'\n                 mode = bMode\n                 sha = bSha\n             else:\n-                print 'CONFLICT (mod/del): \"' + path + '\" deleted in', \\\n-                      branch2Name, 'and modified in', branch1Name + \\\n-                      '. Version', branch1Name, 'of \"' + path + \\\n-                      '\" left in tree'\n+                print 'CONFLICT (modify/delete):', path, 'deleted in', \\\n+                      branch2Name, 'and modified in', branch1Name + '.', \\\n+                      'Version', branch1Name, 'of', path, 'left in tree.'\n                 mode = aMode\n                 sha = aSha\n \n             updateFile(False, sha, mode, path)\n-    \n+\n     elif (not oSha and aSha     and not bSha) or \\\n          (not oSha and not aSha and bSha):\n     #\n@@ -307,27 +739,26 @@ def processEntry(entry, branch1Name, bra\n             otherBranch = branch2Name\n             mode = aMode\n             sha = aSha\n-            conf = 'file/dir'\n+            conf = 'file/directory'\n         else:\n             addBranch = branch2Name\n             otherBranch = branch1Name\n             mode = bMode\n             sha = bSha\n-            conf = 'dir/file'\n+            conf = 'directory/file'\n     \n-        if path in dirs:\n+        if path in currentDirectorySet:\n             cleanMerge = False\n             newPath = uniquePath(path, addBranch)\n-            print 'CONFLICT (' + conf + \\\n-                  '): There is a directory with name \"' + path + '\" in', \\\n-                  otherBranch + '. Adding \"' + path + '\" as \"' + newPath + '\"'\n+            print 'CONFLICT (' + conf + '):', \\\n+                  'There is a directory with name', path, 'in', \\\n+                  otherBranch + '. Adding', path, 'as', newPath\n \n             removeFile(False, path)\n-            path = newPath\n+            updateFile(False, sha, mode, newPath)\n         else:\n-            print 'Adding \"' + path + '\"'\n-\n-        updateFile(True, sha, mode, path)\n+            print 'Adding', path\n+            updateFile(True, sha, mode, path)\n     \n     elif not oSha and aSha and bSha:\n     #\n@@ -336,10 +767,9 @@ def processEntry(entry, branch1Name, bra\n         if aSha == bSha:\n             if aMode != bMode:\n                 cleanMerge = False\n-                print 'CONFLICT: File \"' + path + \\\n-                      '\" added identically in both branches,', \\\n-                      'but permissions conflict', '0%o' % aMode, '->', \\\n-                      '0%o' % bMode\n+                print 'CONFLICT: File', path, \\\n+                      'added identically in both branches, but permissions', \\\n+                      'conflict', '0%o' % aMode, '->', '0%o' % bMode\n                 print 'CONFLICT: adding with permission:', '0%o' % aMode\n \n                 updateFile(False, aSha, aMode, path)\n@@ -350,8 +780,9 @@ def processEntry(entry, branch1Name, bra\n             cleanMerge = False\n             newPath1 = uniquePath(path, branch1Name)\n             newPath2 = uniquePath(path, branch2Name)\n-            print 'CONFLICT (add/add): File \"' + path + \\\n-                  '\" added non-identically in both branches.'\n+            print 'CONFLICT (add/add): File', path, \\\n+                  'added non-identically in both branches. Adding as', \\\n+                  newPath1, 'and', newPath2, 'instead.'\n             removeFile(False, path)\n             updateFile(False, aSha, aMode, newPath1)\n             updateFile(False, bSha, bMode, newPath2)\n@@ -360,39 +791,24 @@ def processEntry(entry, branch1Name, bra\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', branch1Name + '/' + path,\n-                                 '-L', 'orig/' + path,\n-                                 '-L', branch2Name + '/' + path,\n-                                 src1, orig, src2], returnCode=True)\n-\n-        if aMode == oMode:\n-            mode = bMode\n+        print 'Auto-merging', path\n+        [sha, mode, clean, dummy] = \\\n+              mergeFile(path, oSha, oMode,\n+                        path, aSha, aMode,\n+                        path, bSha, bMode,\n+                        branch1Name, branch2Name)\n+        if clean:\n+            updateFile(True, sha, mode, path)\n         else:\n-            mode = aMode\n-\n-        sha = runProgram(['git-hash-object', '-t', 'blob', '-w',\n-                          src1]).rstrip()\n-\n-        if ret != 0:\n             cleanMerge = False\n-            print 'CONFLICT (content): Merge conflict in \"' + path + '\".'\n+            print 'CONFLICT (content): Merge conflict in', path\n \n-            if cleanCache:\n+            if cacheOnly:\n                 updateFile(False, sha, mode, path)\n             else:\n-                updateFile(True, aSha, aMode, path)\n-                updateFile(False, sha, mode, path, True)\n-        else:\n-            updateFile(True, sha, mode, path)\n-\n-        os.unlink(orig)\n-        os.unlink(src1)\n-        os.unlink(src2)\n+                updateFileExt(aSha, aMode, path,\n+                              updateCache=True, updateWd=False)\n+                updateFileExt(sha, mode, path, updateCache=False, updateWd=True)\n     else:\n         die(\"ERROR: Fatal merge failure, shouldn't happen.\")\n \n@@ -416,7 +832,7 @@ for nextArg in xrange(1, len(sys.argv)):\n         try:\n             h1 = firstBranch = sys.argv[nextArg + 1]\n             h2 = secondBranch = sys.argv[nextArg + 2]\n-\texcept IndexError:\n+        except IndexError:\n             usage()\n         break\n \n@@ -428,8 +844,8 @@ try:\n \n     graph = buildGraph([h1, h2])\n \n-    [res, clean] = merge(graph.shaMap[h1], graph.shaMap[h2],\n-                         firstBranch, secondBranch, graph)\n+    [dummy, clean] = merge(graph.shaMap[h1], graph.shaMap[h2],\n+                           firstBranch, secondBranch, graph)\n \n     print ''\n except:\n"}]}