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