Andrew's git - gitweb.git/blob - git-merge-recursive.py

   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
  10# The actual merge code
  11# ---------------------
  12
  13originalIndexFile = os.environ.get('GIT_INDEX_FILE',
  14                                   os.environ.get('GIT_DIR', '.git') + '/index')
  15temporaryIndexFile = os.environ.get('GIT_DIR', '.git') + \
  16                     '/merge-recursive-tmp-index'
  17def setupIndex(temporary):
  18    try:
  19        os.unlink(temporaryIndexFile)
  20    except OSError:
  21        pass
  22    if temporary:
  23        newIndex = temporaryIndexFile
  24        os.environ
  25    else:
  26        newIndex = originalIndexFile
  27    os.environ['GIT_INDEX_FILE'] = newIndex
  28
  29def merge(h1, h2, branch1Name, branch2Name, graph, callDepth=0):
  30    '''Merge the commits h1 and h2, return the resulting virtual
  31    commit object and a flag indicating the cleaness of the merge.'''
  32    assert(isinstance(h1, Commit) and isinstance(h2, Commit))
  33    assert(isinstance(graph, Graph))
  34
  35    def infoMsg(*args):
  36        sys.stdout.write('  '*callDepth)
  37        printList(args)
  38    infoMsg('Merging:')
  39    infoMsg(h1)
  40    infoMsg(h2)
  41    sys.stdout.flush()
  42
  43    ca = getCommonAncestors(graph, h1, h2)
  44    infoMsg('found', len(ca), 'common ancestor(s):')
  45    for x in ca:
  46        infoMsg(x)
  47    sys.stdout.flush()
  48
  49    Ms = ca[0]
  50    for h in ca[1:]:
  51        [Ms, ignore] = merge(Ms, h,
  52                             'Temporary shared merge branch 1',
  53                             'Temporary shared merge branch 2',
  54                             graph, callDepth+1)
  55        assert(isinstance(Ms, Commit))
  56
  57    if callDepth == 0:
  58        setupIndex(False)
  59        cleanCache = False
  60    else:
  61        setupIndex(True)
  62        runProgram(['git-read-tree', h1.tree()])
  63        cleanCache = True
  64
  65    [shaRes, clean] = mergeTrees(h1.tree(), h2.tree(), Ms.tree(),
  66                                 branch1Name, branch2Name,
  67                                 cleanCache)
  68
  69    if clean or cleanCache:
  70        res = Commit(None, [h1, h2], tree=shaRes)
  71        graph.addNode(res)
  72    else:
  73        res = None
  74
  75    return [res, clean]
  76
  77getFilesRE = re.compile(r'^([0-7]+) (\S+) ([0-9a-f]{40})\t(.*)$', re.S)
  78def getFilesAndDirs(tree):
  79    files = Set()
  80    dirs = Set()
  81    out = runProgram(['git-ls-tree', '-r', '-z', tree])
  82    for l in out.split('\0'):
  83        m = getFilesRE.match(l)
  84        if m:
  85            if m.group(2) == 'tree':
  86                dirs.add(m.group(4))
  87            elif m.group(2) == 'blob':
  88                files.add(m.group(4))
  89
  90    return [files, dirs]
  91
  92class CacheEntry:
  93    def __init__(self, path):
  94        class Stage:
  95            def __init__(self):
  96                self.sha1 = None
  97                self.mode = None
  98        
  99        self.stages = [Stage(), Stage(), Stage()]
 100        self.path = path
 101
 102unmergedRE = re.compile(r'^([0-7]+) ([0-9a-f]{40}) ([1-3])\t(.*)$', re.S)
 103def unmergedCacheEntries():
 104    '''Create a dictionary mapping file names to CacheEntry
 105    objects. The dictionary contains one entry for every path with a
 106    non-zero stage entry.'''
 107
 108    lines = runProgram(['git-ls-files', '-z', '--unmerged']).split('\0')
 109    lines.pop()
 110
 111    res = {}
 112    for l in lines:
 113        m = unmergedRE.match(l)
 114        if m:
 115            mode = int(m.group(1), 8)
 116            sha1 = m.group(2)
 117            stage = int(m.group(3)) - 1
 118            path = m.group(4)
 119
 120            if res.has_key(path):
 121                e = res[path]
 122            else:
 123                e = CacheEntry(path)
 124                res[path] = e
 125                
 126            e.stages[stage].mode = mode
 127            e.stages[stage].sha1 = sha1
 128        else:
 129            die('Error: Merge program failed: Unexpected output from', \
 130                'git-ls-files:', l)
 131    return res
 132
 133def mergeTrees(head, merge, common, branch1Name, branch2Name,
 134               cleanCache):
 135    '''Merge the trees 'head' and 'merge' with the common ancestor
 136    'common'. The name of the head branch is 'branch1Name' and the name of
 137    the merge branch is 'branch2Name'. Return a tuple (tree, cleanMerge)
 138    where tree is the resulting tree and cleanMerge is True iff the
 139    merge was clean.'''
 140    
 141    assert(isSha(head) and isSha(merge) and isSha(common))
 142
 143    if common == merge:
 144        print 'Already uptodate!'
 145        return [head, True]
 146
 147    if cleanCache:
 148        updateArg = '-i'
 149    else:
 150        updateArg = '-u'
 151
 152    [out, code] = runProgram(['git-read-tree', updateArg, '-m', common, head, merge], returnCode = True)
 153    if code != 0:
 154        die('git-read-tree:', out)
 155
 156    cleanMerge = True
 157
 158    [tree, code] = runProgram('git-write-tree', returnCode=True)
 159    tree = tree.rstrip()
 160    if code != 0:
 161        [files, dirs] = getFilesAndDirs(head)
 162        [filesM, dirsM] = getFilesAndDirs(merge)
 163        files.union_update(filesM)
 164        dirs.union_update(dirsM)
 165        
 166        cleanMerge = True
 167        entries = unmergedCacheEntries()
 168        for name in entries:
 169            if not processEntry(entries[name], branch1Name, branch2Name,
 170                                files, dirs, cleanCache):
 171                cleanMerge = False
 172                
 173        if cleanMerge or cleanCache:
 174            tree = runProgram('git-write-tree').rstrip()
 175        else:
 176            tree = None
 177    else:
 178        cleanMerge = True
 179
 180    return [tree, cleanMerge]
 181
 182def processEntry(entry, branch1Name, branch2Name, files, dirs, cleanCache):
 183    '''Merge one cache entry. 'files' is a Set with the files in both of
 184    the heads that we are going to merge. 'dirs' contains the
 185    corresponding data for directories. If 'cleanCache' is True no
 186    non-zero stages will be left in the cache for the path
 187    corresponding to the entry 'entry'.'''
 188
 189# cleanCache == True  => Don't leave any non-stage 0 entries in the cache and
 190#                        don't update the working directory
 191#               False => Leave unmerged entries and update the working directory
 192
 193# clean     == True  => non-conflict case
 194#              False => conflict case
 195
 196# If cleanCache == False then the cache shouldn't be updated if clean == False
 197
 198    def updateFile(clean, sha, mode, path, onlyWd=False):
 199        updateCache = not onlyWd and (cleanCache or (not cleanCache and clean))
 200        updateWd = onlyWd or (not cleanCache and clean)
 201
 202        if updateWd:
 203            prog = ['git-cat-file', 'blob', sha]
 204            if stat.S_ISREG(mode):
 205                try:
 206                    os.unlink(path)
 207                except OSError:
 208                    pass
 209                if mode & 0100:
 210                    mode = 0777
 211                else:
 212                    mode = 0666
 213                fd = os.open(path, os.O_WRONLY | os.O_TRUNC | os.O_CREAT, mode)
 214                proc = subprocess.Popen(prog, stdout=fd)
 215                proc.wait()
 216                os.close(fd)
 217            elif stat.S_ISLNK(mode):
 218                linkTarget = runProgram(prog)
 219                os.symlink(linkTarget, path)
 220            else:
 221                assert(False)
 222
 223        if updateWd and updateCache:
 224            runProgram(['git-update-index', '--add', '--', path])
 225        elif updateCache:
 226            runProgram(['git-update-index', '--add', '--cacheinfo',
 227                        '0%o' % mode, sha, path])
 228
 229    def removeFile(clean, path):
 230        if cleanCache or (not cleanCache and clean):
 231            runProgram(['git-update-index', '--force-remove', '--', path])
 232
 233        if not cleanCache and clean:
 234            try:
 235                os.unlink(path)
 236            except OSError, e:
 237                if e.errno != errno.ENOENT and e.errno != errno.EISDIR:
 238                    raise
 239
 240    def uniquePath(path, branch):
 241        newPath = path + '_' + branch
 242        suffix = 0
 243        while newPath in files or newPath in dirs:
 244            suffix += 1
 245            newPath = path + '_' + branch + '_' + str(suffix)
 246        files.add(newPath)
 247        return newPath
 248
 249    debug('processing', entry.path, 'clean cache:', cleanCache)
 250
 251    cleanMerge = True
 252
 253    path = entry.path
 254    oSha = entry.stages[0].sha1
 255    oMode = entry.stages[0].mode
 256    aSha = entry.stages[1].sha1
 257    aMode = entry.stages[1].mode
 258    bSha = entry.stages[2].sha1
 259    bMode = entry.stages[2].mode
 260
 261    assert(oSha == None or isSha(oSha))
 262    assert(aSha == None or isSha(aSha))
 263    assert(bSha == None or isSha(bSha))
 264
 265    assert(oMode == None or type(oMode) is int)
 266    assert(aMode == None or type(aMode) is int)
 267    assert(bMode == None or type(bMode) is int)
 268
 269    if (oSha and (not aSha or not bSha)):
 270    #
 271    # Case A: Deleted in one
 272    #
 273        if (not aSha     and not bSha) or \
 274           (aSha == oSha and not bSha) or \
 275           (not aSha     and bSha == oSha):
 276    # Deleted in both or deleted in one and unchanged in the other
 277            if aSha:
 278                print 'Removing ' + path
 279            removeFile(True, path)
 280        else:
 281    # Deleted in one and changed in the other
 282            cleanMerge = False
 283            if not aSha:
 284                print 'CONFLICT (del/mod): "' + path + '" deleted in', \
 285                      branch1Name, 'and modified in', branch2Name, \
 286                      '. Version', branch2Name, ' of "' + path + \
 287                      '" left in tree'
 288                mode = bMode
 289                sha = bSha
 290            else:
 291                print 'CONFLICT (mod/del): "' + path + '" deleted in', \
 292                      branch2Name, 'and modified in', branch1Name + \
 293                      '. Version', branch1Name, 'of "' + path + \
 294                      '" left in tree'
 295                mode = aMode
 296                sha = aSha
 297
 298            updateFile(False, sha, mode, path)
 299    
 300    elif (not oSha and aSha     and not bSha) or \
 301         (not oSha and not aSha and bSha):
 302    #
 303    # Case B: Added in one.
 304    #
 305        if aSha:
 306            addBranch = branch1Name
 307            otherBranch = branch2Name
 308            mode = aMode
 309            sha = aSha
 310            conf = 'file/dir'
 311        else:
 312            addBranch = branch2Name
 313            otherBranch = branch1Name
 314            mode = bMode
 315            sha = bSha
 316            conf = 'dir/file'
 317    
 318        if path in dirs:
 319            cleanMerge = False
 320            newPath = uniquePath(path, addBranch)
 321            print 'CONFLICT (' + conf + \
 322                  '): There is a directory with name "' + path + '" in', \
 323                  otherBranch + '. Adding "' + path + '" as "' + newPath + '"'
 324
 325            removeFile(False, path)
 326            path = newPath
 327        else:
 328            print 'Adding "' + path + '"'
 329
 330        updateFile(True, sha, mode, path)
 331    
 332    elif not oSha and aSha and bSha:
 333    #
 334    # Case C: Added in both (check for same permissions).
 335    #
 336        if aSha == bSha:
 337            if aMode != bMode:
 338                cleanMerge = False
 339                print 'CONFLICT: File "' + path + \
 340                      '" added identically in both branches,', \
 341                      'but permissions conflict', '0%o' % aMode, '->', \
 342                      '0%o' % bMode
 343                print 'CONFLICT: adding with permission:', '0%o' % aMode
 344
 345                updateFile(False, aSha, aMode, path)
 346            else:
 347                # This case is handled by git-read-tree
 348                assert(False)
 349        else:
 350            cleanMerge = False
 351            newPath1 = uniquePath(path, branch1Name)
 352            newPath2 = uniquePath(path, branch2Name)
 353            print 'CONFLICT (add/add): File "' + path + \
 354                  '" added non-identically in both branches.'
 355            removeFile(False, path)
 356            updateFile(False, aSha, aMode, newPath1)
 357            updateFile(False, bSha, bMode, newPath2)
 358
 359    elif oSha and aSha and bSha:
 360    #
 361    # case D: Modified in both, but differently.
 362    #
 363        print 'Auto-merging', path 
 364        orig = runProgram(['git-unpack-file', oSha]).rstrip()
 365        src1 = runProgram(['git-unpack-file', aSha]).rstrip()
 366        src2 = runProgram(['git-unpack-file', bSha]).rstrip()
 367        [out, ret] = runProgram(['merge',
 368                                 '-L', branch1Name + '/' + path,
 369                                 '-L', 'orig/' + path,
 370                                 '-L', branch2Name + '/' + path,
 371                                 src1, orig, src2], returnCode=True)
 372
 373        if aMode == oMode:
 374            mode = bMode
 375        else:
 376            mode = aMode
 377
 378        sha = runProgram(['git-hash-object', '-t', 'blob', '-w',
 379                          src1]).rstrip()
 380
 381        if ret != 0:
 382            cleanMerge = False
 383            print 'CONFLICT (content): Merge conflict in "' + path + '".'
 384
 385            if cleanCache:
 386                updateFile(False, sha, mode, path)
 387            else:
 388                updateFile(True, aSha, aMode, path)
 389                updateFile(False, sha, mode, path, True)
 390        else:
 391            updateFile(True, sha, mode, path)
 392
 393        os.unlink(orig)
 394        os.unlink(src1)
 395        os.unlink(src2)
 396    else:
 397        die("ERROR: Fatal merge failure, shouldn't happen.")
 398
 399    return cleanMerge
 400
 401def usage():
 402    die('Usage:', sys.argv[0], ' <base>... -- <head> <remote>..')
 403
 404# main entry point as merge strategy module
 405# The first parameters up to -- are merge bases, and the rest are heads.
 406# This strategy module figures out merge bases itself, so we only
 407# get heads.
 408
 409if len(sys.argv) < 4:
 410    usage()
 411
 412for nextArg in xrange(1, len(sys.argv)):
 413    if sys.argv[nextArg] == '--':
 414        if len(sys.argv) != nextArg + 3:
 415            die('Not handling anything other than two heads merge.')
 416        try:
 417            h1 = firstBranch = sys.argv[nextArg + 1]
 418            h2 = secondBranch = sys.argv[nextArg + 2]
 419        except IndexError:
 420            usage()
 421        break
 422
 423print 'Merging', h1, 'with', h2
 424
 425try:
 426    h1 = runProgram(['git-rev-parse', '--verify', h1 + '^0']).rstrip()
 427    h2 = runProgram(['git-rev-parse', '--verify', h2 + '^0']).rstrip()
 428
 429    graph = buildGraph([h1, h2])
 430
 431    [res, clean] = merge(graph.shaMap[h1], graph.shaMap[h2],
 432                         firstBranch, secondBranch, graph)
 433
 434    print ''
 435except:
 436    if isinstance(sys.exc_info()[1], SystemExit):
 437        raise
 438    else:
 439        traceback.print_exc(None, sys.stderr)
 440        sys.exit(2)
 441
 442if clean:
 443    sys.exit(0)
 444else:
 445    sys.exit(1)