Andrew's git - gitweb.git/blob

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