Andrew's git - gitweb.git/blob

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