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