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             try:
 209                 [out, code] = runProgram(['merge',
 210                                           '-L', branch1Name + '/' + aPath,
 211                                           '-L', 'orig/' + oPath,
 212                                           '-L', branch2Name + '/' + bPath,
 213                                           src1, orig, src2], returnCode=True)
 214             except ProgramError, e:
 215                 print >>sys.stderr, e
 216                 die("Failed to execute 'merge'. merge(1) is used as the "
 217                     "file-level merge tool. Is 'merge' in your path?")
 218
 219             sha = runProgram(['git-hash-object', '-t', 'blob', '-w',
 220                               src1]).rstrip()
 221
 222             os.unlink(orig)
 223             os.unlink(src1)
 224             os.unlink(src2)
 225
 226             clean = (code == 0)
 227         else:
 228             assert(stat.S_ISLNK(aMode) and stat.S_ISLNK(bMode))
 229             sha = aSha
 230
 231             if aSha != bSha:
 232                 clean = False
 233
 234     return [sha, mode, clean, merge]
 235
 236 def updateFile(clean, sha, mode, path):
 237     updateCache = cacheOnly or clean
 238     updateWd = not cacheOnly
 239
 240     return updateFileExt(sha, mode, path, updateCache, updateWd)
 241
 242 def updateFileExt(sha, mode, path, updateCache, updateWd):
 243     if cacheOnly:
 244         updateWd = False
 245
 246     if updateWd:
 247         pathComponents = path.split('/')
 248         for x in xrange(1, len(pathComponents)):
 249             p = '/'.join(pathComponents[0:x])
 250
 251             try:
 252                 createDir = not stat.S_ISDIR(os.lstat(p).st_mode)
 253             except OSError:
 254                 createDir = True
 255
 256             if createDir:
 257                 try:
 258                     os.mkdir(p)
 259                 except OSError, e:
 260                     die("Couldn't create directory", p, e.strerror)
 261
 262         prog = ['git-cat-file', 'blob', sha]
 263         if stat.S_ISREG(mode):
 264             try:
 265                 os.unlink(path)
 266             except OSError:
 267                 pass
 268             if mode & 0100:
 269                 mode = 0777
 270             else:
 271                 mode = 0666
 272             fd = os.open(path, os.O_WRONLY | os.O_TRUNC | os.O_CREAT, mode)
 273             proc = subprocess.Popen(prog, stdout=fd)
 274             proc.wait()
 275             os.close(fd)
 276         elif stat.S_ISLNK(mode):
 277             linkTarget = runProgram(prog)
 278             os.symlink(linkTarget, path)
 279         else:
 280             assert(False)
 281
 282     if updateWd and updateCache:
 283         runProgram(['git-update-index', '--add', '--', path])
 284     elif updateCache:
 285         runProgram(['git-update-index', '--add', '--cacheinfo',
 286                     '0%o' % mode, sha, path])
 287
 288 def setIndexStages(path,
 289                    oSHA1, oMode,
 290                    aSHA1, aMode,
 291                    bSHA1, bMode,
 292                    clear=True):
 293     istring = []
 294     if clear:
 295         istring.append("0 " + ("0" * 40) + "\t" + path + "\0")
 296     if oMode:
 297         istring.append("%o %s %d\t%s\0" % (oMode, oSHA1, 1, path))
 298     if aMode:
 299         istring.append("%o %s %d\t%s\0" % (aMode, aSHA1, 2, path))
 300     if bMode:
 301         istring.append("%o %s %d\t%s\0" % (bMode, bSHA1, 3, path))
 302
 303     runProgram(['git-update-index', '-z', '--index-info'],
 304                input="".join(istring))
 305
 306 def removeFile(clean, path):
 307     updateCache = cacheOnly or clean
 308     updateWd = not cacheOnly
 309
 310     if updateCache:
 311         runProgram(['git-update-index', '--force-remove', '--', path])
 312
 313     if updateWd:
 314         try:
 315             os.unlink(path)
 316         except OSError, e:
 317             if e.errno != errno.ENOENT and e.errno != errno.EISDIR:
 318                 raise
 319         try:
 320             os.removedirs(os.path.dirname(path))
 321         except OSError:
 322             pass
 323
 324 def uniquePath(path, branch):
 325     def fileExists(path):
 326         try:
 327             os.lstat(path)
 328             return True
 329         except OSError, e:
 330             if e.errno == errno.ENOENT:
 331                 return False
 332             else:
 333                 raise
 334
 335     branch = branch.replace('/', '_')
 336     newPath = path + '~' + branch
 337     suffix = 0
 338     while newPath in currentFileSet or \
 339           newPath in currentDirectorySet  or \
 340           fileExists(newPath):
 341         suffix += 1
 342         newPath = path + '~' + branch + '_' + str(suffix)
 343     currentFileSet.add(newPath)
 344     return newPath
 345
 346 # Cache entry management
 347 # ----------------------
 348
 349 class CacheEntry:
 350     def __init__(self, path):
 351         class Stage:
 352             def __init__(self):
 353                 self.sha1 = None
 354                 self.mode = None
 355
 356             # Used for debugging only
 357             def __str__(self):
 358                 if self.mode != None:
 359                     m = '0%o' % self.mode
 360                 else:
 361                     m = 'None'
 362
 363                 if self.sha1:
 364                     sha1 = self.sha1
 365                 else:
 366                     sha1 = 'None'
 367                 return 'sha1: ' + sha1 + ' mode: ' + m
 368
 369         self.stages = [Stage(), Stage(), Stage(), Stage()]
 370         self.path = path
 371         self.processed = False
 372
 373     def __str__(self):
 374         return 'path: ' + self.path + ' stages: ' + repr([str(x) for x in self.stages])
 375
 376 class CacheEntryContainer:
 377     def __init__(self):
 378         self.entries = {}
 379
 380     def add(self, entry):
 381         self.entries[entry.path] = entry
 382
 383     def get(self, path):
 384         return self.entries.get(path)
 385
 386     def __iter__(self):
 387         return self.entries.itervalues()
 388
 389 unmergedRE = re.compile(r'^([0-7]+) ([0-9a-f]{40}) ([1-3])\t(.*)$', re.S)
 390 def unmergedCacheEntries():
 391     '''Create a dictionary mapping file names to CacheEntry
 392     objects. The dictionary contains one entry for every path with a
 393     non-zero stage entry.'''
 394
 395     lines = runProgram(['git-ls-files', '-z', '--unmerged']).split('\0')
 396     lines.pop()
 397
 398     res = CacheEntryContainer()
 399     for l in lines:
 400         m = unmergedRE.match(l)
 401         if m:
 402             mode = int(m.group(1), 8)
 403             sha1 = m.group(2)
 404             stage = int(m.group(3))
 405             path = m.group(4)
 406
 407             e = res.get(path)
 408             if not e:
 409                 e = CacheEntry(path)
 410                 res.add(e)
 411
 412             e.stages[stage].mode = mode
 413             e.stages[stage].sha1 = sha1
 414         else:
 415             die('Error: Merge program failed: Unexpected output from',
 416                 'git-ls-files:', l)
 417     return res
 418
 419 lsTreeRE = re.compile(r'^([0-7]+) (\S+) ([0-9a-f]{40})\t(.*)\n$', re.S)
 420 def getCacheEntry(path, origTree, aTree, bTree):
 421     '''Returns a CacheEntry object which doesn't have to correspond to
 422     a real cache entry in Git's index.'''
 423
 424     def parse(out):
 425         if out == '':
 426             return [None, None]
 427         else:
 428             m = lsTreeRE.match(out)
 429             if not m:
 430                 die('Unexpected output from git-ls-tree:', out)
 431             elif m.group(2) == 'blob':
 432                 return [m.group(3), int(m.group(1), 8)]
 433             else:
 434                 return [None, None]
 435
 436     res = CacheEntry(path)
 437
 438     [oSha, oMode] = parse(runProgram(['git-ls-tree', origTree, '--', path]))
 439     [aSha, aMode] = parse(runProgram(['git-ls-tree', aTree, '--', path]))
 440     [bSha, bMode] = parse(runProgram(['git-ls-tree', bTree, '--', path]))
 441
 442     res.stages[1].sha1 = oSha
 443     res.stages[1].mode = oMode
 444     res.stages[2].sha1 = aSha
 445     res.stages[2].mode = aMode
 446     res.stages[3].sha1 = bSha
 447     res.stages[3].mode = bMode
 448
 449     return res
 450
 451 # Rename detection and handling
 452 # -----------------------------
 453
 454 class RenameEntry:
 455     def __init__(self,
 456                  src, srcSha, srcMode, srcCacheEntry,
 457                  dst, dstSha, dstMode, dstCacheEntry,
 458                  score):
 459         self.srcName = src
 460         self.srcSha = srcSha
 461         self.srcMode = srcMode
 462         self.srcCacheEntry = srcCacheEntry
 463         self.dstName = dst
 464         self.dstSha = dstSha
 465         self.dstMode = dstMode
 466         self.dstCacheEntry = dstCacheEntry
 467         self.score = score
 468
 469         self.processed = False
 470
 471 class RenameEntryContainer:
 472     def __init__(self):
 473         self.entriesSrc = {}
 474         self.entriesDst = {}
 475
 476     def add(self, entry):
 477         self.entriesSrc[entry.srcName] = entry
 478         self.entriesDst[entry.dstName] = entry
 479
 480     def getSrc(self, path):
 481         return self.entriesSrc.get(path)
 482
 483     def getDst(self, path):
 484         return self.entriesDst.get(path)
 485
 486     def __iter__(self):
 487         return self.entriesSrc.itervalues()
 488
 489 parseDiffRenamesRE = re.compile('^:([0-7]+) ([0-7]+) ([0-9a-f]{40}) ([0-9a-f]{40}) R([0-9]*)$')
 490 def getRenames(tree, oTree, aTree, bTree, cacheEntries):
 491     '''Get information of all renames which occured between 'oTree' and
 492     'tree'. We need the three trees in the merge ('oTree', 'aTree' and
 493     'bTree') to be able to associate the correct cache entries with
 494     the rename information. 'tree' is always equal to either aTree or bTree.'''
 495
 496     assert(tree == aTree or tree == bTree)
 497     inp = runProgram(['git-diff-tree', '-M', '--diff-filter=R', '-r',
 498                       '-z', oTree, tree])
 499
 500     ret = RenameEntryContainer()
 501     try:
 502         recs = inp.split("\0")
 503         recs.pop() # remove last entry (which is '')
 504         it = recs.__iter__()
 505         while True:
 506             rec = it.next()
 507             m = parseDiffRenamesRE.match(rec)
 508
 509             if not m:
 510                 die('Unexpected output from git-diff-tree:', rec)
 511
 512             srcMode = int(m.group(1), 8)
 513             dstMode = int(m.group(2), 8)
 514             srcSha = m.group(3)
 515             dstSha = m.group(4)
 516             score = m.group(5)
 517             src = it.next()
 518             dst = it.next()
 519
 520             srcCacheEntry = cacheEntries.get(src)
 521             if not srcCacheEntry:
 522                 srcCacheEntry = getCacheEntry(src, oTree, aTree, bTree)
 523                 cacheEntries.add(srcCacheEntry)
 524
 525             dstCacheEntry = cacheEntries.get(dst)
 526             if not dstCacheEntry:
 527                 dstCacheEntry = getCacheEntry(dst, oTree, aTree, bTree)
 528                 cacheEntries.add(dstCacheEntry)
 529
 530             ret.add(RenameEntry(src, srcSha, srcMode, srcCacheEntry,
 531                                 dst, dstSha, dstMode, dstCacheEntry,
 532                                 score))
 533     except StopIteration:
 534         pass
 535     return ret
 536
 537 def fmtRename(src, dst):
 538     srcPath = src.split('/')
 539     dstPath = dst.split('/')
 540     path = []
 541     endIndex = min(len(srcPath), len(dstPath)) - 1
 542     for x in range(0, endIndex):
 543         if srcPath[x] == dstPath[x]:
 544             path.append(srcPath[x])
 545         else:
 546             endIndex = x
 547             break
 548
 549     if len(path) > 0:
 550         return '/'.join(path) + \
 551                '/{' + '/'.join(srcPath[endIndex:]) + ' => ' + \
 552                '/'.join(dstPath[endIndex:]) + '}'
 553     else:
 554         return src + ' => ' + dst
 555
 556 def processRenames(renamesA, renamesB, branchNameA, branchNameB):
 557     srcNames = Set()
 558     for x in renamesA:
 559         srcNames.add(x.srcName)
 560     for x in renamesB:
 561         srcNames.add(x.srcName)
 562
 563     cleanMerge = True
 564     for path in srcNames:
 565         if renamesA.getSrc(path):
 566             renames1 = renamesA
 567             renames2 = renamesB
 568             branchName1 = branchNameA
 569             branchName2 = branchNameB
 570         else:
 571             renames1 = renamesB
 572             renames2 = renamesA
 573             branchName1 = branchNameB
 574             branchName2 = branchNameA
 575
 576         ren1 = renames1.getSrc(path)
 577         ren2 = renames2.getSrc(path)
 578
 579         ren1.dstCacheEntry.processed = True
 580         ren1.srcCacheEntry.processed = True
 581
 582         if ren1.processed:
 583             continue
 584
 585         ren1.processed = True
 586
 587         if ren2:
 588             # Renamed in 1 and renamed in 2
 589             assert(ren1.srcName == ren2.srcName)
 590             ren2.dstCacheEntry.processed = True
 591             ren2.processed = True
 592
 593             if ren1.dstName != ren2.dstName:
 594                 output('CONFLICT (rename/rename): Rename',
 595                        fmtRename(path, ren1.dstName), 'in branch', branchName1,
 596                        'rename', fmtRename(path, ren2.dstName), 'in',
 597                        branchName2)
 598                 cleanMerge = False
 599
 600                 if ren1.dstName in currentDirectorySet:
 601                     dstName1 = uniquePath(ren1.dstName, branchName1)
 602                     output(ren1.dstName, 'is a directory in', branchName2,
 603                            'adding as', dstName1, 'instead.')
 604                     removeFile(False, ren1.dstName)
 605                 else:
 606                     dstName1 = ren1.dstName
 607
 608                 if ren2.dstName in currentDirectorySet:
 609                     dstName2 = uniquePath(ren2.dstName, branchName2)
 610                     output(ren2.dstName, 'is a directory in', branchName1,
 611                            'adding as', dstName2, 'instead.')
 612                     removeFile(False, ren2.dstName)
 613                 else:
 614                     dstName2 = ren2.dstName
 615                 setIndexStages(dstName1,
 616                                None, None,
 617                                ren1.dstSha, ren1.dstMode,
 618                                None, None)
 619                 setIndexStages(dstName2,
 620                                None, None,
 621                                None, None,
 622                                ren2.dstSha, ren2.dstMode)
 623
 624             else:
 625                 removeFile(True, ren1.srcName)
 626
 627                 [resSha, resMode, clean, merge] = \
 628                          mergeFile(ren1.srcName, ren1.srcSha, ren1.srcMode,
 629                                    ren1.dstName, ren1.dstSha, ren1.dstMode,
 630                                    ren2.dstName, ren2.dstSha, ren2.dstMode,
 631                                    branchName1, branchName2)
 632
 633                 if merge or not clean:
 634                     output('Renaming', fmtRename(path, ren1.dstName))
 635
 636                 if merge:
 637                     output('Auto-merging', ren1.dstName)
 638
 639                 if not clean:
 640                     output('CONFLICT (content): merge conflict in',
 641                            ren1.dstName)
 642                     cleanMerge = False
 643
 644                     if not cacheOnly:
 645                         setIndexStages(ren1.dstName,
 646                                        ren1.srcSha, ren1.srcMode,
 647                                        ren1.dstSha, ren1.dstMode,
 648                                        ren2.dstSha, ren2.dstMode)
 649
 650                 updateFile(clean, resSha, resMode, ren1.dstName)
 651         else:
 652             removeFile(True, ren1.srcName)
 653
 654             # Renamed in 1, maybe changed in 2
 655             if renamesA == renames1:
 656                 stage = 3
 657             else:
 658                 stage = 2
 659
 660             srcShaOtherBranch  = ren1.srcCacheEntry.stages[stage].sha1
 661             srcModeOtherBranch = ren1.srcCacheEntry.stages[stage].mode
 662
 663             dstShaOtherBranch  = ren1.dstCacheEntry.stages[stage].sha1
 664             dstModeOtherBranch = ren1.dstCacheEntry.stages[stage].mode
 665
 666             tryMerge = False
 667
 668             if ren1.dstName in currentDirectorySet:
 669                 newPath = uniquePath(ren1.dstName, branchName1)
 670                 output('CONFLICT (rename/directory): Rename',
 671                        fmtRename(ren1.srcName, ren1.dstName), 'in', branchName1,
 672                        'directory', ren1.dstName, 'added in', branchName2)
 673                 output('Renaming', ren1.srcName, 'to', newPath, 'instead')
 674                 cleanMerge = False
 675                 removeFile(False, ren1.dstName)
 676                 updateFile(False, ren1.dstSha, ren1.dstMode, newPath)
 677             elif srcShaOtherBranch == None:
 678                 output('CONFLICT (rename/delete): Rename',
 679                        fmtRename(ren1.srcName, ren1.dstName), 'in',
 680                        branchName1, 'and deleted in', branchName2)
 681                 cleanMerge = False
 682                 updateFile(False, ren1.dstSha, ren1.dstMode, ren1.dstName)
 683             elif dstShaOtherBranch:
 684                 newPath = uniquePath(ren1.dstName, branchName2)
 685                 output('CONFLICT (rename/add): Rename',
 686                        fmtRename(ren1.srcName, ren1.dstName), 'in',
 687                        branchName1 + '.', ren1.dstName, 'added in', branchName2)
 688                 output('Adding as', newPath, 'instead')
 689                 updateFile(False, dstShaOtherBranch, dstModeOtherBranch, newPath)
 690                 cleanMerge = False
 691                 tryMerge = True
 692             elif renames2.getDst(ren1.dstName):
 693                 dst2 = renames2.getDst(ren1.dstName)
 694                 newPath1 = uniquePath(ren1.dstName, branchName1)
 695                 newPath2 = uniquePath(dst2.dstName, branchName2)
 696                 output('CONFLICT (rename/rename): Rename',
 697                        fmtRename(ren1.srcName, ren1.dstName), 'in',
 698                        branchName1+'. Rename',
 699                        fmtRename(dst2.srcName, dst2.dstName), 'in', branchName2)
 700                 output('Renaming', ren1.srcName, 'to', newPath1, 'and',
 701                        dst2.srcName, 'to', newPath2, 'instead')
 702                 removeFile(False, ren1.dstName)
 703                 updateFile(False, ren1.dstSha, ren1.dstMode, newPath1)
 704                 updateFile(False, dst2.dstSha, dst2.dstMode, newPath2)
 705                 dst2.processed = True
 706                 cleanMerge = False
 707             else:
 708                 tryMerge = True
 709
 710             if tryMerge:
 711
 712                 oName, oSHA1, oMode = ren1.srcName, ren1.srcSha, ren1.srcMode
 713                 aName, bName = ren1.dstName, ren1.srcName
 714                 aSHA1, bSHA1 = ren1.dstSha, srcShaOtherBranch
 715                 aMode, bMode = ren1.dstMode, srcModeOtherBranch
 716                 aBranch, bBranch = branchName1, branchName2
 717
 718                 if renamesA != renames1:
 719                     aName, bName = bName, aName
 720                     aSHA1, bSHA1 = bSHA1, aSHA1
 721                     aMode, bMode = bMode, aMode
 722                     aBranch, bBranch = bBranch, aBranch
 723
 724                 [resSha, resMode, clean, merge] = \
 725                          mergeFile(oName, oSHA1, oMode,
 726                                    aName, aSHA1, aMode,
 727                                    bName, bSHA1, bMode,
 728                                    aBranch, bBranch);
 729
 730                 if merge or not clean:
 731                     output('Renaming', fmtRename(ren1.srcName, ren1.dstName))
 732
 733                 if merge:
 734                     output('Auto-merging', ren1.dstName)
 735
 736                 if not clean:
 737                     output('CONFLICT (rename/modify): Merge conflict in',
 738                            ren1.dstName)
 739                     cleanMerge = False
 740
 741                     if not cacheOnly:
 742                         setIndexStages(ren1.dstName,
 743                                        oSHA1, oMode,
 744                                        aSHA1, aMode,
 745                                        bSHA1, bMode)
 746
 747                 updateFile(clean, resSha, resMode, ren1.dstName)
 748
 749     return cleanMerge
 750
 751 # Per entry merge function
 752 # ------------------------
 753
 754 def processEntry(entry, branch1Name, branch2Name):
 755     '''Merge one cache entry.'''
 756
 757     debug('processing', entry.path, 'clean cache:', cacheOnly)
 758
 759     cleanMerge = True
 760
 761     path = entry.path
 762     oSha = entry.stages[1].sha1
 763     oMode = entry.stages[1].mode
 764     aSha = entry.stages[2].sha1
 765     aMode = entry.stages[2].mode
 766     bSha = entry.stages[3].sha1
 767     bMode = entry.stages[3].mode
 768
 769     assert(oSha == None or isSha(oSha))
 770     assert(aSha == None or isSha(aSha))
 771     assert(bSha == None or isSha(bSha))
 772
 773     assert(oMode == None or type(oMode) is int)
 774     assert(aMode == None or type(aMode) is int)
 775     assert(bMode == None or type(bMode) is int)
 776
 777     if (oSha and (not aSha or not bSha)):
 778     #
 779     # Case A: Deleted in one
 780     #
 781         if (not aSha     and not bSha) or \
 782            (aSha == oSha and not bSha) or \
 783            (not aSha     and bSha == oSha):
 784     # Deleted in both or deleted in one and unchanged in the other
 785             if aSha:
 786                 output('Removing', path)
 787             removeFile(True, path)
 788         else:
 789     # Deleted in one and changed in the other
 790             cleanMerge = False
 791             if not aSha:
 792                 output('CONFLICT (delete/modify):', path, 'deleted in',
 793                        branch1Name, 'and modified in', branch2Name + '.',
 794                        'Version', branch2Name, 'of', path, 'left in tree.')
 795                 mode = bMode
 796                 sha = bSha
 797             else:
 798                 output('CONFLICT (modify/delete):', path, 'deleted in',
 799                        branch2Name, 'and modified in', branch1Name + '.',
 800                        'Version', branch1Name, 'of', path, 'left in tree.')
 801                 mode = aMode
 802                 sha = aSha
 803
 804             updateFile(False, sha, mode, path)
 805
 806     elif (not oSha and aSha     and not bSha) or \
 807          (not oSha and not aSha and bSha):
 808     #
 809     # Case B: Added in one.
 810     #
 811         if aSha:
 812             addBranch = branch1Name
 813             otherBranch = branch2Name
 814             mode = aMode
 815             sha = aSha
 816             conf = 'file/directory'
 817         else:
 818             addBranch = branch2Name
 819             otherBranch = branch1Name
 820             mode = bMode
 821             sha = bSha
 822             conf = 'directory/file'
 823
 824         if path in currentDirectorySet:
 825             cleanMerge = False
 826             newPath = uniquePath(path, addBranch)
 827             output('CONFLICT (' + conf + '):',
 828                    'There is a directory with name', path, 'in',
 829                    otherBranch + '. Adding', path, 'as', newPath)
 830
 831             removeFile(False, path)
 832             updateFile(False, sha, mode, newPath)
 833         else:
 834             output('Adding', path)
 835             updateFile(True, sha, mode, path)
 836
 837     elif not oSha and aSha and bSha:
 838     #
 839     # Case C: Added in both (check for same permissions).
 840     #
 841         if aSha == bSha:
 842             if aMode != bMode:
 843                 cleanMerge = False
 844                 output('CONFLICT: File', path,
 845                        'added identically in both branches, but permissions',
 846                        'conflict', '0%o' % aMode, '->', '0%o' % bMode)
 847                 output('CONFLICT: adding with permission:', '0%o' % aMode)
 848
 849                 updateFile(False, aSha, aMode, path)
 850             else:
 851                 # This case is handled by git-read-tree
 852                 assert(False)
 853         else:
 854             cleanMerge = False
 855             newPath1 = uniquePath(path, branch1Name)
 856             newPath2 = uniquePath(path, branch2Name)
 857             output('CONFLICT (add/add): File', path,
 858                    'added non-identically in both branches. Adding as',
 859                    newPath1, 'and', newPath2, 'instead.')
 860             removeFile(False, path)
 861             updateFile(False, aSha, aMode, newPath1)
 862             updateFile(False, bSha, bMode, newPath2)
 863
 864     elif oSha and aSha and bSha:
 865     #
 866     # case D: Modified in both, but differently.
 867     #
 868         output('Auto-merging', path)
 869         [sha, mode, clean, dummy] = \
 870               mergeFile(path, oSha, oMode,
 871                         path, aSha, aMode,
 872                         path, bSha, bMode,
 873                         branch1Name, branch2Name)
 874         if clean:
 875             updateFile(True, sha, mode, path)
 876         else:
 877             cleanMerge = False
 878             output('CONFLICT (content): Merge conflict in', path)
 879
 880             if cacheOnly:
 881                 updateFile(False, sha, mode, path)
 882             else:
 883                 updateFileExt(sha, mode, path, updateCache=False, updateWd=True)
 884     else:
 885         die("ERROR: Fatal merge failure, shouldn't happen.")
 886
 887     return cleanMerge
 888
 889 def usage():
 890     die('Usage:', sys.argv[0], ' <base>... -- <head> <remote>..')
 891
 892 # main entry point as merge strategy module
 893 # The first parameters up to -- are merge bases, and the rest are heads.
 894 # This strategy module figures out merge bases itself, so we only
 895 # get heads.
 896
 897 if len(sys.argv) < 4:
 898     usage()
 899
 900 for nextArg in xrange(1, len(sys.argv)):
 901     if sys.argv[nextArg] == '--':
 902         if len(sys.argv) != nextArg + 3:
 903             die('Not handling anything other than two heads merge.')
 904         try:
 905             h1 = firstBranch = sys.argv[nextArg + 1]
 906             h2 = secondBranch = sys.argv[nextArg + 2]
 907         except IndexError:
 908             usage()
 909         break
 910
 911 print 'Merging', h1, 'with', h2
 912
 913 try:
 914     h1 = runProgram(['git-rev-parse', '--verify', h1 + '^0']).rstrip()
 915     h2 = runProgram(['git-rev-parse', '--verify', h2 + '^0']).rstrip()
 916
 917     graph = buildGraph([h1, h2])
 918
 919     [dummy, clean] = merge(graph.shaMap[h1], graph.shaMap[h2],
 920                            firstBranch, secondBranch, graph)
 921
 922     print ''
 923 except:
 924     if isinstance(sys.exc_info()[1], SystemExit):
 925         raise
 926     else:
 927         traceback.print_exc(None, sys.stderr)
 928         sys.exit(2)
 929
 930 if clean:
 931     sys.exit(0)
 932 else:
 933     sys.exit(1)