git-merge-recursive.py

   1 #!/usr/bin/python
   2 #
   3 # Copyright (C) 2005 Fredrik Kuivinen
   4 #
   5
   6 import sys
   7 sys.path.append('''@@GIT_PYTHON_PATH@@''')
   8
   9 import math, random, os, re, signal, tempfile, stat, errno, traceback
  10 from heapq import heappush, heappop
  11 from sets import Set
  12
  13 from gitMergeCommon import *
  14
  15 outputIndent = 0
  16 def output(*args):
  17     sys.stdout.write('  '*outputIndent)
  18     printList(args)
  19
  20 originalIndexFile = os.environ.get('GIT_INDEX_FILE',
  21                                    os.environ.get('GIT_DIR', '.git') + '/index')
  22 temporaryIndexFile = os.environ.get('GIT_DIR', '.git') + \
  23                      '/merge-recursive-tmp-index'
  24 def setupIndex(temporary):
  25     try:
  26         os.unlink(temporaryIndexFile)
  27     except OSError:
  28         pass
  29     if temporary:
  30         newIndex = temporaryIndexFile
  31     else:
  32         newIndex = originalIndexFile
  33     os.environ['GIT_INDEX_FILE'] = newIndex
  34
  35 # This is a global variable which is used in a number of places but
  36 # only written to in the 'merge' function.
  37
  38 # cacheOnly == True  => Don't leave any non-stage 0 entries in the cache and
  39 #                       don't update the working directory.
  40 #              False => Leave unmerged entries in the cache and update
  41 #                       the working directory.
  42
  43 cacheOnly = False
  44
  45 # The entry point to the merge code
  46 # ---------------------------------
  47
  48 def merge(h1, h2, branch1Name, branch2Name, graph, callDepth=0):
  49     '''Merge the commits h1 and h2, return the resulting virtual
  50     commit object and a flag indicating the cleaness of the merge.'''
  51     assert(isinstance(h1, Commit) and isinstance(h2, Commit))
  52     assert(isinstance(graph, Graph))
  53
  54     global outputIndent
  55
  56     output('Merging:')
  57     output(h1)
  58     output(h2)
  59     sys.stdout.flush()
  60
  61     ca = getCommonAncestors(graph, h1, h2)
  62     output('found', len(ca), 'common ancestor(s):')
  63     for x in ca:
  64         output(x)
  65     sys.stdout.flush()
  66
  67     mergedCA = ca[0]
  68     for h in ca[1:]:
  69         outputIndent = callDepth+1
  70         [mergedCA, dummy] = merge(mergedCA, h,
  71                                   'Temporary merge branch 1',
  72                                   'Temporary merge branch 2',
  73                                   graph, callDepth+1)
  74         outputIndent = callDepth
  75         assert(isinstance(mergedCA, Commit))
  76
  77     global cacheOnly
  78     if callDepth == 0:
  79         setupIndex(False)
  80         cacheOnly = False
  81     else:
  82         setupIndex(True)
  83         runProgram(['git-read-tree', h1.tree()])
  84         cacheOnly = True
  85
  86     [shaRes, clean] = mergeTrees(h1.tree(), h2.tree(), mergedCA.tree(),
  87                                  branch1Name, branch2Name)
  88
  89     if clean or cacheOnly:
  90         res = Commit(None, [h1, h2], tree=shaRes)
  91         graph.addNode(res)
  92     else:
  93         res = None
  94
  95     return [res, clean]
  96
  97 getFilesRE = re.compile(r'^([0-7]+) (\S+) ([0-9a-f]{40})\t(.*)$', re.S)
  98 def getFilesAndDirs(tree):
  99     files = Set()
 100     dirs = Set()
 101     out = runProgram(['git-ls-tree', '-r', '-z', '-t', tree])
 102     for l in out.split('\0'):
 103         m = getFilesRE.match(l)
 104         if m:
 105             if m.group(2) == 'tree':
 106                 dirs.add(m.group(4))
 107             elif m.group(2) == 'blob':
 108                 files.add(m.group(4))
 109
 110     return [files, dirs]
 111
 112 # Those two global variables are used in a number of places but only
 113 # written to in 'mergeTrees' and 'uniquePath'. They keep track of
 114 # every file and directory in the two branches that are about to be
 115 # merged.
 116 currentFileSet = None
 117 currentDirectorySet = None
 118
 119 def mergeTrees(head, merge, common, branch1Name, branch2Name):
 120     '''Merge the trees 'head' and 'merge' with the common ancestor
 121     'common'. The name of the head branch is 'branch1Name' and the name of
 122     the merge branch is 'branch2Name'. Return a tuple (tree, cleanMerge)
 123     where tree is the resulting tree and cleanMerge is True iff the
 124     merge was clean.'''
 125
 126     assert(isSha(head) and isSha(merge) and isSha(common))
 127
 128     if common == merge:
 129         output('Already uptodate!')
 130         return [head, True]
 131
 132     if cacheOnly:
 133         updateArg = '-i'
 134     else:
 135         updateArg = '-u'
 136
 137     [out, code] = runProgram(['git-read-tree', updateArg, '-m',
 138                                 common, head, merge], returnCode = True)
 139     if code != 0:
 140         die('git-read-tree:', out)
 141
 142     [tree, code] = runProgram('git-write-tree', returnCode=True)
 143     tree = tree.rstrip()
 144     if code != 0:
 145         global currentFileSet, currentDirectorySet
 146         [currentFileSet, currentDirectorySet] = getFilesAndDirs(head)
 147         [filesM, dirsM] = getFilesAndDirs(merge)
 148         currentFileSet.union_update(filesM)
 149         currentDirectorySet.union_update(dirsM)
 150
 151         entries = unmergedCacheEntries()
 152         renamesHead =  getRenames(head, common, head, merge, entries)
 153         renamesMerge = getRenames(merge, common, head, merge, entries)
 154
 155         cleanMerge = processRenames(renamesHead, renamesMerge,
 156                                     branch1Name, branch2Name)
 157         for entry in entries:
 158             if entry.processed:
 159                 continue
 160             if not processEntry(entry, branch1Name, branch2Name):
 161                 cleanMerge = False
 162
 163         if cleanMerge or cacheOnly:
 164             tree = runProgram('git-write-tree').rstrip()
 165         else:
 166             tree = None
 167     else:
 168         cleanMerge = True
 169
 170     return [tree, cleanMerge]
 171
 172 # Low level file merging, update and removal
 173 # ------------------------------------------
 174
 175 def mergeFile(oPath, oSha, oMode, aPath, aSha, aMode, bPath, bSha, bMode,
 176               branch1Name, branch2Name):
 177
 178     merge = False
 179     clean = True
 180
 181     if stat.S_IFMT(aMode) != stat.S_IFMT(bMode):
 182         clean = False
 183         if stat.S_ISREG(aMode):
 184             mode = aMode
 185             sha = aSha
 186         else:
 187             mode = bMode
 188             sha = bSha
 189     else:
 190         if aSha != oSha and bSha != oSha:
 191             merge = True
 192
 193         if aMode == oMode:
 194             mode = bMode
 195         else:
 196             mode = aMode
 197
 198         if aSha == oSha:
 199             sha = bSha
 200         elif bSha == oSha:
 201             sha = aSha
 202         elif stat.S_ISREG(aMode):
 203             assert(stat.S_ISREG(bMode))
 204
 205             orig = runProgram(['git-unpack-file', oSha]).rstrip()
 206             src1 = runProgram(['git-unpack-file', aSha]).rstrip()
 207             src2 = runProgram(['git-unpack-file', bSha]).rstrip()
 208             [out, code] = runProgram(['merge',
 209                                       '-L', branch1Name + '/' + aPath,
 210                                       '-L', 'orig/' + oPath,
 211                                       '-L', branch2Name + '/' + bPath,
 212                                       src1, orig, src2], returnCode=True)
 213
 214             sha = runProgram(['git-hash-object', '-t', 'blob', '-w',
 215                               src1]).rstrip()
 216
 217             os.unlink(orig)
 218             os.unlink(src1)
 219             os.unlink(src2)
 220
 221             clean = (code == 0)
 222         else:
 223             assert(stat.S_ISLNK(aMode) and stat.S_ISLNK(bMode))
 224             sha = aSha
 225
 226             if aSha != bSha:
 227                 clean = False
 228
 229     return [sha, mode, clean, merge]
 230
 231 def updateFile(clean, sha, mode, path):
 232     updateCache = cacheOnly or clean
 233     updateWd = not cacheOnly
 234
 235     return updateFileExt(sha, mode, path, updateCache, updateWd)
 236
 237 def updateFileExt(sha, mode, path, updateCache, updateWd):
 238     if cacheOnly:
 239         updateWd = False
 240
 241     if updateWd:
 242         pathComponents = path.split('/')
 243         for x in xrange(1, len(pathComponents)):
 244             p = '/'.join(pathComponents[0:x])
 245
 246             try:
 247                 createDir = not stat.S_ISDIR(os.lstat(p).st_mode)
 248             except OSError:
 249                 createDir = True
 250
 251             if createDir:
 252                 try:
 253                     os.mkdir(p)
 254                 except OSError, e:
 255                     die("Couldn't create directory", p, e.strerror)
 256
 257         prog = ['git-cat-file', 'blob', sha]
 258         if stat.S_ISREG(mode):
 259             try:
 260                 os.unlink(path)
 261             except OSError:
 262                 pass
 263             if mode & 0100:
 264                 mode = 0777
 265             else:
 266                 mode = 0666
 267             fd = os.open(path, os.O_WRONLY | os.O_TRUNC | os.O_CREAT, mode)
 268             proc = subprocess.Popen(prog, stdout=fd)
 269             proc.wait()
 270             os.close(fd)
 271         elif stat.S_ISLNK(mode):
 272             linkTarget = runProgram(prog)
 273             os.symlink(linkTarget, path)
 274         else:
 275             assert(False)
 276
 277     if updateWd and updateCache:
 278         runProgram(['git-update-index', '--add', '--', path])
 279     elif updateCache:
 280         runProgram(['git-update-index', '--add', '--cacheinfo',
 281                     '0%o' % mode, sha, path])
 282
 283 def setIndexStages(path,
 284                    oSHA1, oMode,
 285                    aSHA1, aMode,
 286                    bSHA1, bMode,
 287                    clear=True):
 288     istring = []
 289     if clear:
 290         istring.append("0 " + ("0" * 40) + "\t" + path + "\0")
 291     if oMode:
 292         istring.append("%o %s %d\t%s\0" % (oMode, oSHA1, 1, path))
 293     if aMode:
 294         istring.append("%o %s %d\t%s\0" % (aMode, aSHA1, 2, path))
 295     if bMode:
 296         istring.append("%o %s %d\t%s\0" % (bMode, bSHA1, 3, path))
 297
 298     runProgram(['git-update-index', '-z', '--index-info'],
 299                input="".join(istring))
 300
 301 def removeFile(clean, path):
 302     updateCache = cacheOnly or clean
 303     updateWd = not cacheOnly
 304
 305     if updateCache:
 306         runProgram(['git-update-index', '--force-remove', '--', path])
 307
 308     if updateWd:
 309         try:
 310             os.unlink(path)
 311         except OSError, e:
 312             if e.errno != errno.ENOENT and e.errno != errno.EISDIR:
 313                 raise
 314         try:
 315             os.removedirs(os.path.dirname(path))
 316         except OSError:
 317             pass
 318
 319 def uniquePath(path, branch):
 320     def fileExists(path):
 321         try:
 322             os.lstat(path)
 323             return True
 324         except OSError, e:
 325             if e.errno == errno.ENOENT:
 326                 return False
 327             else:
 328                 raise
 329
 330     branch = branch.replace('/', '_')
 331     newPath = path + '~' + branch
 332     suffix = 0
 333     while newPath in currentFileSet or \
 334           newPath in currentDirectorySet  or \
 335           fileExists(newPath):
 336         suffix += 1
 337         newPath = path + '~' + branch + '_' + str(suffix)
 338     currentFileSet.add(newPath)
 339     return newPath
 340
 341 # Cache entry management
 342 # ----------------------
 343
 344 class CacheEntry:
 345     def __init__(self, path):
 346         class Stage:
 347             def __init__(self):
 348                 self.sha1 = None
 349                 self.mode = None
 350
 351             # Used for debugging only
 352             def __str__(self):
 353                 if self.mode != None:
 354                     m = '0%o' % self.mode
 355                 else:
 356                     m = 'None'
 357
 358                 if self.sha1:
 359                     sha1 = self.sha1
 360                 else:
 361                     sha1 = 'None'
 362                 return 'sha1: ' + sha1 + ' mode: ' + m
 363
 364         self.stages = [Stage(), Stage(), Stage(), Stage()]
 365         self.path = path
 366         self.processed = False
 367
 368     def __str__(self):
 369         return 'path: ' + self.path + ' stages: ' + repr([str(x) for x in self.stages])
 370
 371 class CacheEntryContainer:
 372     def __init__(self):
 373         self.entries = {}
 374
 375     def add(self, entry):
 376         self.entries[entry.path] = entry
 377
 378     def get(self, path):
 379         return self.entries.get(path)
 380
 381     def __iter__(self):
 382         return self.entries.itervalues()
 383
 384 unmergedRE = re.compile(r'^([0-7]+) ([0-9a-f]{40}) ([1-3])\t(.*)$', re.S)
 385 def unmergedCacheEntries():
 386     '''Create a dictionary mapping file names to CacheEntry
 387     objects. The dictionary contains one entry for every path with a
 388     non-zero stage entry.'''
 389
 390     lines = runProgram(['git-ls-files', '-z', '--unmerged']).split('\0')
 391     lines.pop()
 392
 393     res = CacheEntryContainer()
 394     for l in lines:
 395         m = unmergedRE.match(l)
 396         if m:
 397             mode = int(m.group(1), 8)
 398             sha1 = m.group(2)
 399             stage = int(m.group(3))
 400             path = m.group(4)
 401
 402             e = res.get(path)
 403             if not e:
 404                 e = CacheEntry(path)
 405                 res.add(e)
 406
 407             e.stages[stage].mode = mode
 408             e.stages[stage].sha1 = sha1
 409         else:
 410             die('Error: Merge program failed: Unexpected output from',
 411                 'git-ls-files:', l)
 412     return res
 413
 414 lsTreeRE = re.compile(r'^([0-7]+) (\S+) ([0-9a-f]{40})\t(.*)\n$', re.S)
 415 def getCacheEntry(path, origTree, aTree, bTree):
 416     '''Returns a CacheEntry object which doesn't have to correspond to
 417     a real cache entry in Git's index.'''
 418
 419     def parse(out):
 420         if out == '':
 421             return [None, None]
 422         else:
 423             m = lsTreeRE.match(out)
 424             if not m:
 425                 die('Unexpected output from git-ls-tree:', out)
 426             elif m.group(2) == 'blob':
 427                 return [m.group(3), int(m.group(1), 8)]
 428             else:
 429                 return [None, None]
 430
 431     res = CacheEntry(path)
 432
 433     [oSha, oMode] = parse(runProgram(['git-ls-tree', origTree, '--', path]))
 434     [aSha, aMode] = parse(runProgram(['git-ls-tree', aTree, '--', path]))
 435     [bSha, bMode] = parse(runProgram(['git-ls-tree', bTree, '--', path]))
 436
 437     res.stages[1].sha1 = oSha
 438     res.stages[1].mode = oMode
 439     res.stages[2].sha1 = aSha
 440     res.stages[2].mode = aMode
 441     res.stages[3].sha1 = bSha
 442     res.stages[3].mode = bMode
 443
 444     return res
 445
 446 # Rename detection and handling
 447 # -----------------------------
 448
 449 class RenameEntry:
 450     def __init__(self,
 451                  src, srcSha, srcMode, srcCacheEntry,
 452                  dst, dstSha, dstMode, dstCacheEntry,
 453                  score):
 454         self.srcName = src
 455         self.srcSha = srcSha
 456         self.srcMode = srcMode
 457         self.srcCacheEntry = srcCacheEntry
 458         self.dstName = dst
 459         self.dstSha = dstSha
 460         self.dstMode = dstMode
 461         self.dstCacheEntry = dstCacheEntry
 462         self.score = score
 463
 464         self.processed = False
 465
 466 class RenameEntryContainer:
 467     def __init__(self):
 468         self.entriesSrc = {}
 469         self.entriesDst = {}
 470
 471     def add(self, entry):
 472         self.entriesSrc[entry.srcName] = entry
 473         self.entriesDst[entry.dstName] = entry
 474
 475     def getSrc(self, path):
 476         return self.entriesSrc.get(path)
 477
 478     def getDst(self, path):
 479         return self.entriesDst.get(path)
 480
 481     def __iter__(self):
 482         return self.entriesSrc.itervalues()
 483
 484 parseDiffRenamesRE = re.compile('^:([0-7]+) ([0-7]+) ([0-9a-f]{40}) ([0-9a-f]{40}) R([0-9]*)$')
 485 def getRenames(tree, oTree, aTree, bTree, cacheEntries):
 486     '''Get information of all renames which occured between 'oTree' and
 487     'tree'. We need the three trees in the merge ('oTree', 'aTree' and
 488     'bTree') to be able to associate the correct cache entries with
 489     the rename information. 'tree' is always equal to either aTree or bTree.'''
 490
 491     assert(tree == aTree or tree == bTree)
 492     inp = runProgram(['git-diff-tree', '-M', '--diff-filter=R', '-r',
 493                       '-z', oTree, tree])
 494
 495     ret = RenameEntryContainer()
 496     try:
 497         recs = inp.split("\0")
 498         recs.pop() # remove last entry (which is '')
 499         it = recs.__iter__()
 500         while True:
 501             rec = it.next()
 502             m = parseDiffRenamesRE.match(rec)
 503
 504             if not m:
 505                 die('Unexpected output from git-diff-tree:', rec)
 506
 507             srcMode = int(m.group(1), 8)
 508             dstMode = int(m.group(2), 8)
 509             srcSha = m.group(3)
 510             dstSha = m.group(4)
 511             score = m.group(5)
 512             src = it.next()
 513             dst = it.next()
 514
 515             srcCacheEntry = cacheEntries.get(src)
 516             if not srcCacheEntry:
 517                 srcCacheEntry = getCacheEntry(src, oTree, aTree, bTree)
 518                 cacheEntries.add(srcCacheEntry)
 519
 520             dstCacheEntry = cacheEntries.get(dst)
 521             if not dstCacheEntry:
 522                 dstCacheEntry = getCacheEntry(dst, oTree, aTree, bTree)
 523                 cacheEntries.add(dstCacheEntry)
 524
 525             ret.add(RenameEntry(src, srcSha, srcMode, srcCacheEntry,
 526                                 dst, dstSha, dstMode, dstCacheEntry,
 527                                 score))
 528     except StopIteration:
 529         pass
 530     return ret
 531
 532 def fmtRename(src, dst):
 533     srcPath = src.split('/')
 534     dstPath = dst.split('/')
 535     path = []
 536     endIndex = min(len(srcPath), len(dstPath)) - 1
 537     for x in range(0, endIndex):
 538         if srcPath[x] == dstPath[x]:
 539             path.append(srcPath[x])
 540         else:
 541             endIndex = x
 542             break
 543
 544     if len(path) > 0:
 545         return '/'.join(path) + \
 546                '/{' + '/'.join(srcPath[endIndex:]) + ' => ' + \
 547                '/'.join(dstPath[endIndex:]) + '}'
 548     else:
 549         return src + ' => ' + dst
 550
 551 def processRenames(renamesA, renamesB, branchNameA, branchNameB):
 552     srcNames = Set()
 553     for x in renamesA:
 554         srcNames.add(x.srcName)
 555     for x in renamesB:
 556         srcNames.add(x.srcName)
 557
 558     cleanMerge = True
 559     for path in srcNames:
 560         if renamesA.getSrc(path):
 561             renames1 = renamesA
 562             renames2 = renamesB
 563             branchName1 = branchNameA
 564             branchName2 = branchNameB
 565         else:
 566             renames1 = renamesB
 567             renames2 = renamesA
 568             branchName1 = branchNameB
 569             branchName2 = branchNameA
 570
 571         ren1 = renames1.getSrc(path)
 572         ren2 = renames2.getSrc(path)
 573
 574         ren1.dstCacheEntry.processed = True
 575         ren1.srcCacheEntry.processed = True
 576
 577         if ren1.processed:
 578             continue
 579
 580         ren1.processed = True
 581
 582         if ren2:
 583             # Renamed in 1 and renamed in 2
 584             assert(ren1.srcName == ren2.srcName)
 585             ren2.dstCacheEntry.processed = True
 586             ren2.processed = True
 587
 588             if ren1.dstName != ren2.dstName:
 589                 output('CONFLICT (rename/rename): Rename',
 590                        fmtRename(path, ren1.dstName), 'in branch', branchName1,
 591                        'rename', fmtRename(path, ren2.dstName), 'in',
 592                        branchName2)
 593                 cleanMerge = False
 594
 595                 if ren1.dstName in currentDirectorySet:
 596                     dstName1 = uniquePath(ren1.dstName, branchName1)
 597                     output(ren1.dstName, 'is a directory in', branchName2,
 598                            'adding as', dstName1, 'instead.')
 599                     removeFile(False, ren1.dstName)
 600                 else:
 601                     dstName1 = ren1.dstName
 602
 603                 if ren2.dstName in currentDirectorySet:
 604                     dstName2 = uniquePath(ren2.dstName, branchName2)
 605                     output(ren2.dstName, 'is a directory in', branchName1,
 606                            'adding as', dstName2, 'instead.')
 607                     removeFile(False, ren2.dstName)
 608                 else:
 609                     dstName2 = ren2.dstName
 610                 setIndexStages(dstName1,
 611                                None, None,
 612                                ren1.dstSha, ren1.dstMode,
 613                                None, None)
 614                 setIndexStages(dstName2,
 615                                None, None,
 616                                None, None,
 617                                ren2.dstSha, ren2.dstMode)
 618
 619             else:
 620                 removeFile(True, ren1.srcName)
 621
 622                 [resSha, resMode, clean, merge] = \
 623                          mergeFile(ren1.srcName, ren1.srcSha, ren1.srcMode,
 624                                    ren1.dstName, ren1.dstSha, ren1.dstMode,
 625                                    ren2.dstName, ren2.dstSha, ren2.dstMode,
 626                                    branchName1, branchName2)
 627
 628                 if merge or not clean:
 629                     output('Renaming', fmtRename(path, ren1.dstName))
 630
 631                 if merge:
 632                     output('Auto-merging', ren1.dstName)
 633
 634                 if not clean:
 635                     output('CONFLICT (content): merge conflict in',
 636                            ren1.dstName)
 637                     cleanMerge = False
 638
 639                     if not cacheOnly:
 640                         setIndexStages(ren1.dstName,
 641                                        ren1.srcSha, ren1.srcMode,
 642                                        ren1.dstSha, ren1.dstMode,
 643                                        ren2.dstSha, ren2.dstMode)
 644
 645                 updateFile(clean, resSha, resMode, ren1.dstName)
 646         else:
 647             removeFile(True, ren1.srcName)
 648
 649             # Renamed in 1, maybe changed in 2
 650             if renamesA == renames1:
 651                 stage = 3
 652             else:
 653                 stage = 2
 654
 655             srcShaOtherBranch  = ren1.srcCacheEntry.stages[stage].sha1
 656             srcModeOtherBranch = ren1.srcCacheEntry.stages[stage].mode
 657
 658             dstShaOtherBranch  = ren1.dstCacheEntry.stages[stage].sha1
 659             dstModeOtherBranch = ren1.dstCacheEntry.stages[stage].mode
 660
 661             tryMerge = False
 662
 663             if ren1.dstName in currentDirectorySet:
 664                 newPath = uniquePath(ren1.dstName, branchName1)
 665                 output('CONFLICT (rename/directory): Rename',
 666                        fmtRename(ren1.srcName, ren1.dstName), 'in', branchName1,
 667                        'directory', ren1.dstName, 'added in', branchName2)
 668                 output('Renaming', ren1.srcName, 'to', newPath, 'instead')
 669                 cleanMerge = False
 670                 removeFile(False, ren1.dstName)
 671                 updateFile(False, ren1.dstSha, ren1.dstMode, newPath)
 672             elif srcShaOtherBranch == None:
 673                 output('CONFLICT (rename/delete): Rename',
 674                        fmtRename(ren1.srcName, ren1.dstName), 'in',
 675                        branchName1, 'and deleted in', branchName2)
 676                 cleanMerge = False
 677                 updateFile(False, ren1.dstSha, ren1.dstMode, ren1.dstName)
 678             elif dstShaOtherBranch:
 679                 newPath = uniquePath(ren1.dstName, branchName2)
 680                 output('CONFLICT (rename/add): Rename',
 681                        fmtRename(ren1.srcName, ren1.dstName), 'in',
 682                        branchName1 + '.', ren1.dstName, 'added in', branchName2)
 683                 output('Adding as', newPath, 'instead')
 684                 updateFile(False, dstShaOtherBranch, dstModeOtherBranch, newPath)
 685                 cleanMerge = False
 686                 tryMerge = True
 687             elif renames2.getDst(ren1.dstName):
 688                 dst2 = renames2.getDst(ren1.dstName)
 689                 newPath1 = uniquePath(ren1.dstName, branchName1)
 690                 newPath2 = uniquePath(dst2.dstName, branchName2)
 691                 output('CONFLICT (rename/rename): Rename',
 692                        fmtRename(ren1.srcName, ren1.dstName), 'in',
 693                        branchName1+'. Rename',
 694                        fmtRename(dst2.srcName, dst2.dstName), 'in', branchName2)
 695                 output('Renaming', ren1.srcName, 'to', newPath1, 'and',
 696                        dst2.srcName, 'to', newPath2, 'instead')
 697                 removeFile(False, ren1.dstName)
 698                 updateFile(False, ren1.dstSha, ren1.dstMode, newPath1)
 699                 updateFile(False, dst2.dstSha, dst2.dstMode, newPath2)
 700                 dst2.processed = True
 701                 cleanMerge = False
 702             else:
 703                 tryMerge = True
 704
 705             if tryMerge:
 706
 707                 oName, oSHA1, oMode = ren1.srcName, ren1.srcSha, ren1.srcMode
 708                 aName, bName = ren1.dstName, ren1.srcName
 709                 aSHA1, bSHA1 = ren1.dstSha, srcShaOtherBranch
 710                 aMode, bMode = ren1.dstMode, srcModeOtherBranch
 711                 aBranch, bBranch = branchName1, branchName2
 712
 713                 if renamesA != renames1:
 714                     aName, bName = bName, aName
 715                     aSHA1, bSHA1 = bSHA1, aSHA1
 716                     aMode, bMode = bMode, aMode
 717                     aBranch, bBranch = bBranch, aBranch
 718
 719                 [resSha, resMode, clean, merge] = \
 720                          mergeFile(oName, oSHA1, oMode,
 721                                    aName, aSHA1, aMode,
 722                                    bName, bSHA1, bMode,
 723                                    aBranch, bBranch);
 724
 725                 if merge or not clean:
 726                     output('Renaming', fmtRename(ren1.srcName, ren1.dstName))
 727
 728                 if merge:
 729                     output('Auto-merging', ren1.dstName)
 730
 731                 if not clean:
 732                     output('CONFLICT (rename/modify): Merge conflict in',
 733                            ren1.dstName)
 734                     cleanMerge = False
 735
 736                     if not cacheOnly:
 737                         setIndexStages(ren1.dstName,
 738                                        oSHA1, oMode,
 739                                        aSHA1, aMode,
 740                                        bSHA1, bMode)
 741
 742                 updateFile(clean, resSha, resMode, ren1.dstName)
 743
 744     return cleanMerge
 745
 746 # Per entry merge function
 747 # ------------------------
 748
 749 def processEntry(entry, branch1Name, branch2Name):
 750     '''Merge one cache entry.'''
 751
 752     debug('processing', entry.path, 'clean cache:', cacheOnly)
 753
 754     cleanMerge = True
 755
 756     path = entry.path
 757     oSha = entry.stages[1].sha1
 758     oMode = entry.stages[1].mode
 759     aSha = entry.stages[2].sha1
 760     aMode = entry.stages[2].mode
 761     bSha = entry.stages[3].sha1
 762     bMode = entry.stages[3].mode
 763
 764     assert(oSha == None or isSha(oSha))
 765     assert(aSha == None or isSha(aSha))
 766     assert(bSha == None or isSha(bSha))
 767
 768     assert(oMode == None or type(oMode) is int)
 769     assert(aMode == None or type(aMode) is int)
 770     assert(bMode == None or type(bMode) is int)
 771
 772     if (oSha and (not aSha or not bSha)):
 773     #
 774     # Case A: Deleted in one
 775     #
 776         if (not aSha     and not bSha) or \
 777            (aSha == oSha and not bSha) or \
 778            (not aSha     and bSha == oSha):
 779     # Deleted in both or deleted in one and unchanged in the other
 780             if aSha:
 781                 output('Removing', path)
 782             removeFile(True, path)
 783         else:
 784     # Deleted in one and changed in the other
 785             cleanMerge = False
 786             if not aSha:
 787                 output('CONFLICT (delete/modify):', path, 'deleted in',
 788                        branch1Name, 'and modified in', branch2Name + '.',
 789                        'Version', branch2Name, 'of', path, 'left in tree.')
 790                 mode = bMode
 791                 sha = bSha
 792             else:
 793                 output('CONFLICT (modify/delete):', path, 'deleted in',
 794                        branch2Name, 'and modified in', branch1Name + '.',
 795                        'Version', branch1Name, 'of', path, 'left in tree.')
 796                 mode = aMode
 797                 sha = aSha
 798
 799             updateFile(False, sha, mode, path)
 800
 801     elif (not oSha and aSha     and not bSha) or \
 802          (not oSha and not aSha and bSha):
 803     #
 804     # Case B: Added in one.
 805     #
 806         if aSha:
 807             addBranch = branch1Name
 808             otherBranch = branch2Name
 809             mode = aMode
 810             sha = aSha
 811             conf = 'file/directory'
 812         else:
 813             addBranch = branch2Name
 814             otherBranch = branch1Name
 815             mode = bMode
 816             sha = bSha
 817             conf = 'directory/file'
 818
 819         if path in currentDirectorySet:
 820             cleanMerge = False
 821             newPath = uniquePath(path, addBranch)
 822             output('CONFLICT (' + conf + '):',
 823                    'There is a directory with name', path, 'in',
 824                    otherBranch + '. Adding', path, 'as', newPath)
 825
 826             removeFile(False, path)
 827             updateFile(False, sha, mode, newPath)
 828         else:
 829             output('Adding', path)
 830             updateFile(True, sha, mode, path)
 831
 832     elif not oSha and aSha and bSha:
 833     #
 834     # Case C: Added in both (check for same permissions).
 835     #
 836         if aSha == bSha:
 837             if aMode != bMode:
 838                 cleanMerge = False
 839                 output('CONFLICT: File', path,
 840                        'added identically in both branches, but permissions',
 841                        'conflict', '0%o' % aMode, '->', '0%o' % bMode)
 842                 output('CONFLICT: adding with permission:', '0%o' % aMode)
 843
 844                 updateFile(False, aSha, aMode, path)
 845             else:
 846                 # This case is handled by git-read-tree
 847                 assert(False)
 848         else:
 849             cleanMerge = False
 850             newPath1 = uniquePath(path, branch1Name)
 851             newPath2 = uniquePath(path, branch2Name)
 852             output('CONFLICT (add/add): File', path,
 853                    'added non-identically in both branches. Adding as',
 854                    newPath1, 'and', newPath2, 'instead.')
 855             removeFile(False, path)
 856             updateFile(False, aSha, aMode, newPath1)
 857             updateFile(False, bSha, bMode, newPath2)
 858
 859     elif oSha and aSha and bSha:
 860     #
 861     # case D: Modified in both, but differently.
 862     #
 863         output('Auto-merging', path)
 864         [sha, mode, clean, dummy] = \
 865               mergeFile(path, oSha, oMode,
 866                         path, aSha, aMode,
 867                         path, bSha, bMode,
 868                         branch1Name, branch2Name)
 869         if clean:
 870             updateFile(True, sha, mode, path)
 871         else:
 872             cleanMerge = False
 873             output('CONFLICT (content): Merge conflict in', path)
 874
 875             if cacheOnly:
 876                 updateFile(False, sha, mode, path)
 877             else:
 878                 updateFileExt(sha, mode, path, updateCache=False, updateWd=True)
 879     else:
 880         die("ERROR: Fatal merge failure, shouldn't happen.")
 881
 882     return cleanMerge
 883
 884 def usage():
 885     die('Usage:', sys.argv[0], ' <base>... -- <head> <remote>..')
 886
 887 # main entry point as merge strategy module
 888 # The first parameters up to -- are merge bases, and the rest are heads.
 889 # This strategy module figures out merge bases itself, so we only
 890 # get heads.
 891
 892 if len(sys.argv) < 4:
 893     usage()
 894
 895 for nextArg in xrange(1, len(sys.argv)):
 896     if sys.argv[nextArg] == '--':
 897         if len(sys.argv) != nextArg + 3:
 898             die('Not handling anything other than two heads merge.')
 899         try:
 900             h1 = firstBranch = sys.argv[nextArg + 1]
 901             h2 = secondBranch = sys.argv[nextArg + 2]
 902         except IndexError:
 903             usage()
 904         break
 905
 906 print 'Merging', h1, 'with', h2
 907
 908 try:
 909     h1 = runProgram(['git-rev-parse', '--verify', h1 + '^0']).rstrip()
 910     h2 = runProgram(['git-rev-parse', '--verify', h2 + '^0']).rstrip()
 911
 912     graph = buildGraph([h1, h2])
 913
 914     [dummy, clean] = merge(graph.shaMap[h1], graph.shaMap[h2],
 915                            firstBranch, secondBranch, graph)
 916
 917     print ''
 918 except:
 919     if isinstance(sys.exc_info()[1], SystemExit):
 920         raise
 921     else:
 922         traceback.print_exc(None, sys.stderr)
 923         sys.exit(2)
 924
 925 if clean:
 926     sys.exit(0)
 927 else:
 928     sys.exit(1)