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     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
 179 def 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
 398 def 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
 406 if len(sys.argv) < 4:
 407     usage()
 408
 409 for 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
 420 print 'Merging', h1, 'with', h2
 421
 422 try:
 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 ''
 432 except:
 433     traceback.print_exc(None, sys.stderr)
 434     sys.exit(2)
 435
 436 if clean:
 437     sys.exit(0)
 438 else:
 439     sys.exit(1)