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