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

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