Andrew's git - gitweb.git/blob

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