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