git-merge-recursive.py

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