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