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