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