git-merge-recursive.py

   1 #!/usr/bin/python
   2
   3 import sys, math, random, os, re, signal, tempfile, stat, errno, traceback
   4 from heapq import heappush, heappop
   5 from sets import Set
   6
   7 sys.path.append('@@GIT_PYTHON_PATH@@')
   8 from gitMergeCommon import *
   9
  10 # The actual merge code
  11 # ---------------------
  12
  13 originalIndexFile = os.environ.get('GIT_INDEX_FILE',
  14                                    os.environ.get('GIT_DIR', '.git') + '/index')
  15 temporaryIndexFile = os.environ.get('GIT_DIR', '.git') + \
  16                      '/merge-recursive-tmp-index'
  17 def 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
  29 def 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
  77 getFilesRE = re.compile(r'^([0-7]+) (\S+) ([0-9a-f]{40})\t(.*)$', re.S)
  78 def 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
  92 class 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
 102 unmergedRE = re.compile(r'^([0-7]+) ([0-9a-f]{40}) ([1-3])\t(.*)$', re.S)
 103 def 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
 133 def 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
 182 def 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
 401 def 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
 409 if len(sys.argv) < 4:
 410     usage()
 411
 412 for 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
 423 print 'Merging', h1, 'with', h2
 424
 425 try:
 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 ''
 435 except:
 436     if isinstance(sys.exc_info()[1], SystemExit):
 437         raise
 438     else:
 439         traceback.print_exc(None, sys.stderr)
 440         sys.exit(2)
 441
 442 if clean:
 443     sys.exit(0)
 444 else:
 445     sys.exit(1)