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