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 def 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-index', '-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
  64 getFilesRE = re.compile('([0-9]+) ([a-z0-9]+) ([0-9a-f]{40})\t(.*)')
  65 def 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
  79 class 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
  89 unmergedRE = re.compile('^([0-9]+) ([0-9a-f]{40}) ([1-3])\t(.*)$')
  90 def 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
 120 def 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
 166 def 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-index', '--add', '--', path])
 209         elif updateCache:
 210             runProgram(['git-update-index', '--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-index', '--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
 385 def 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
 393 if len(sys.argv) < 4:
 394     usage()
 395
 396 for 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
 407 print 'Merging', h1, 'with', h2
 408
 409 try:
 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 ''
 419 except:
 420     traceback.print_exc(None, sys.stderr)
 421     sys.exit(2)
 422
 423 if clean:
 424     sys.exit(0)
 425 else:
 426     sys.exit(1)