git-merge-recursive.py

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