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