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    runProgram(['git-read-tree', updateArg, '-m', common, head, merge])
 153    cleanMerge = True
 154
 155    [tree, code] = runProgram('git-write-tree', returnCode=True)
 156    tree = tree.rstrip()
 157    if code != 0:
 158        [files, dirs] = getFilesAndDirs(head)
 159        [filesM, dirsM] = getFilesAndDirs(merge)
 160        files.union_update(filesM)
 161        dirs.union_update(dirsM)
 162        
 163        cleanMerge = True
 164        entries = unmergedCacheEntries()
 165        for name in entries:
 166            if not processEntry(entries[name], branch1Name, branch2Name,
 167                                files, dirs, cleanCache):
 168                cleanMerge = False
 169                
 170        if cleanMerge or cleanCache:
 171            tree = runProgram('git-write-tree').rstrip()
 172        else:
 173            tree = None
 174    else:
 175        cleanMerge = True
 176
 177    return [tree, cleanMerge]
 178
 179def processEntry(entry, branch1Name, branch2Name, files, dirs, cleanCache):
 180    '''Merge one cache entry. 'files' is a Set with the files in both of
 181    the heads that we are going to merge. 'dirs' contains the
 182    corresponding data for directories. If 'cleanCache' is True no
 183    non-zero stages will be left in the cache for the path
 184    corresponding to the entry 'entry'.'''
 185
 186# cleanCache == True  => Don't leave any non-stage 0 entries in the cache and
 187#                        don't update the working directory
 188#               False => Leave unmerged entries and update the working directory
 189
 190# clean     == True  => non-conflict case
 191#              False => conflict case
 192
 193# If cleanCache == False then the cache shouldn't be updated if clean == False
 194
 195    def updateFile(clean, sha, mode, path, onlyWd=False):
 196        updateCache = not onlyWd and (cleanCache or (not cleanCache and clean))
 197        updateWd = onlyWd or (not cleanCache and clean)
 198
 199        if updateWd:
 200            prog = ['git-cat-file', 'blob', sha]
 201            if stat.S_ISREG(mode):
 202                try:
 203                    os.unlink(path)
 204                except OSError:
 205                    pass
 206                if mode & 0100:
 207                    mode = 0777
 208                else:
 209                    mode = 0666
 210                fd = os.open(path, os.O_WRONLY | os.O_TRUNC | os.O_CREAT, mode)
 211                proc = subprocess.Popen(prog, stdout=fd)
 212                proc.wait()
 213                os.close(fd)
 214            elif stat.S_ISLNK(mode):
 215                linkTarget = runProgram(prog)
 216                os.symlink(linkTarget, path)
 217            else:
 218                assert(False)
 219
 220        if updateWd and updateCache:
 221            runProgram(['git-update-index', '--add', '--', path])
 222        elif updateCache:
 223            runProgram(['git-update-index', '--add', '--cacheinfo',
 224                        '0%o' % mode, sha, path])
 225
 226    def removeFile(clean, path):
 227        if cleanCache or (not cleanCache and clean):
 228            runProgram(['git-update-index', '--force-remove', '--', path])
 229
 230        if not cleanCache and clean:
 231            try:
 232                os.unlink(path)
 233            except OSError, e:
 234                if e.errno != errno.ENOENT and e.errno != errno.EISDIR:
 235                    raise
 236
 237    def uniquePath(path, branch):
 238        newPath = path + '_' + branch
 239        suffix = 0
 240        while newPath in files or newPath in dirs:
 241            suffix += 1
 242            newPath = path + '_' + branch + '_' + str(suffix)
 243        files.add(newPath)
 244        return newPath
 245
 246    debug('processing', entry.path, 'clean cache:', cleanCache)
 247
 248    cleanMerge = True
 249
 250    path = entry.path
 251    oSha = entry.stages[0].sha1
 252    oMode = entry.stages[0].mode
 253    aSha = entry.stages[1].sha1
 254    aMode = entry.stages[1].mode
 255    bSha = entry.stages[2].sha1
 256    bMode = entry.stages[2].mode
 257
 258    assert(oSha == None or isSha(oSha))
 259    assert(aSha == None or isSha(aSha))
 260    assert(bSha == None or isSha(bSha))
 261
 262    assert(oMode == None or type(oMode) is int)
 263    assert(aMode == None or type(aMode) is int)
 264    assert(bMode == None or type(bMode) is int)
 265
 266    if (oSha and (not aSha or not bSha)):
 267    #
 268    # Case A: Deleted in one
 269    #
 270        if (not aSha     and not bSha) or \
 271           (aSha == oSha and not bSha) or \
 272           (not aSha     and bSha == oSha):
 273    # Deleted in both or deleted in one and unchanged in the other
 274            if aSha:
 275                print 'Removing ' + path
 276            removeFile(True, path)
 277        else:
 278    # Deleted in one and changed in the other
 279            cleanMerge = False
 280            if not aSha:
 281                print 'CONFLICT (del/mod): "' + path + '" deleted in', \
 282                      branch1Name, 'and modified in', branch2Name, \
 283                      '. Version', branch2Name, ' of "' + path + \
 284                      '" left in tree'
 285                mode = bMode
 286                sha = bSha
 287            else:
 288                print 'CONFLICT (mod/del): "' + path + '" deleted in', \
 289                      branch2Name, 'and modified in', branch1Name + \
 290                      '. Version', branch1Name, 'of "' + path + \
 291                      '" left in tree'
 292                mode = aMode
 293                sha = aSha
 294
 295            updateFile(False, sha, mode, path)
 296    
 297    elif (not oSha and aSha     and not bSha) or \
 298         (not oSha and not aSha and bSha):
 299    #
 300    # Case B: Added in one.
 301    #
 302        if aSha:
 303            addBranch = branch1Name
 304            otherBranch = branch2Name
 305            mode = aMode
 306            sha = aSha
 307            conf = 'file/dir'
 308        else:
 309            addBranch = branch2Name
 310            otherBranch = branch1Name
 311            mode = bMode
 312            sha = bSha
 313            conf = 'dir/file'
 314    
 315        if path in dirs:
 316            cleanMerge = False
 317            newPath = uniquePath(path, addBranch)
 318            print 'CONFLICT (' + conf + \
 319                  '): There is a directory with name "' + path + '" in', \
 320                  otherBranch + '. Adding "' + path + '" as "' + newPath + '"'
 321
 322            removeFile(False, path)
 323            path = newPath
 324        else:
 325            print 'Adding "' + path + '"'
 326
 327        updateFile(True, sha, mode, path)
 328    
 329    elif not oSha and aSha and bSha:
 330    #
 331    # Case C: Added in both (check for same permissions).
 332    #
 333        if aSha == bSha:
 334            if aMode != bMode:
 335                cleanMerge = False
 336                print 'CONFLICT: File "' + path + \
 337                      '" added identically in both branches,', \
 338                      'but permissions conflict', '0%o' % aMode, '->', \
 339                      '0%o' % bMode
 340                print 'CONFLICT: adding with permission:', '0%o' % aMode
 341
 342                updateFile(False, aSha, aMode, path)
 343            else:
 344                # This case is handled by git-read-tree
 345                assert(False)
 346        else:
 347            cleanMerge = False
 348            newPath1 = uniquePath(path, branch1Name)
 349            newPath2 = uniquePath(path, branch2Name)
 350            print 'CONFLICT (add/add): File "' + path + \
 351                  '" added non-identically in both branches.'
 352            removeFile(False, path)
 353            updateFile(False, aSha, aMode, newPath1)
 354            updateFile(False, bSha, bMode, newPath2)
 355
 356    elif oSha and aSha and bSha:
 357    #
 358    # case D: Modified in both, but differently.
 359    #
 360        print 'Auto-merging', path 
 361        orig = runProgram(['git-unpack-file', oSha]).rstrip()
 362        src1 = runProgram(['git-unpack-file', aSha]).rstrip()
 363        src2 = runProgram(['git-unpack-file', bSha]).rstrip()
 364        [out, ret] = runProgram(['merge',
 365                                 '-L', branch1Name + '/' + path,
 366                                 '-L', 'orig/' + path,
 367                                 '-L', branch2Name + '/' + path,
 368                                 src1, orig, src2], returnCode=True)
 369
 370        if aMode == oMode:
 371            mode = bMode
 372        else:
 373            mode = aMode
 374
 375        sha = runProgram(['git-hash-object', '-t', 'blob', '-w',
 376                          src1]).rstrip()
 377
 378        if ret != 0:
 379            cleanMerge = False
 380            print 'CONFLICT (content): Merge conflict in "' + path + '".'
 381
 382            if cleanCache:
 383                updateFile(False, sha, mode, path)
 384            else:
 385                updateFile(True, aSha, aMode, path)
 386                updateFile(False, sha, mode, path, True)
 387        else:
 388            updateFile(True, sha, mode, path)
 389
 390        os.unlink(orig)
 391        os.unlink(src1)
 392        os.unlink(src2)
 393    else:
 394        die("ERROR: Fatal merge failure, shouldn't happen.")
 395
 396    return cleanMerge
 397
 398def usage():
 399    die('Usage:', sys.argv[0], ' <base>... -- <head> <remote>..')
 400
 401# main entry point as merge strategy module
 402# The first parameters up to -- are merge bases, and the rest are heads.
 403# This strategy module figures out merge bases itself, so we only
 404# get heads.
 405
 406if len(sys.argv) < 4:
 407    usage()
 408
 409for nextArg in xrange(1, len(sys.argv)):
 410    if sys.argv[nextArg] == '--':
 411        if len(sys.argv) != nextArg + 3:
 412            die('Not handling anything other than two heads merge.')
 413        try:
 414            h1 = firstBranch = sys.argv[nextArg + 1]
 415            h2 = secondBranch = sys.argv[nextArg + 2]
 416        except IndexError:
 417            usage()
 418        break
 419
 420print 'Merging', h1, 'with', h2
 421
 422try:
 423    h1 = runProgram(['git-rev-parse', '--verify', h1 + '^0']).rstrip()
 424    h2 = runProgram(['git-rev-parse', '--verify', h2 + '^0']).rstrip()
 425
 426    graph = buildGraph([h1, h2])
 427
 428    [res, clean] = merge(graph.shaMap[h1], graph.shaMap[h2],
 429                         firstBranch, secondBranch, graph)
 430
 431    print ''
 432except:
 433    traceback.print_exc(None, sys.stderr)
 434    sys.exit(2)
 435
 436if clean:
 437    sys.exit(0)
 438else:
 439    sys.exit(1)