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