git-merge-fredrik.py

   1 #!/usr/bin/python
   2
   3 import sys, math, random, os, re, signal, tempfile, stat, errno
   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 alwaysWriteTree = False
  11
  12 # The actual merge code
  13 # ---------------------
  14
  15 def 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
  71 getFilesRE = re.compile('([0-9]+) ([a-z0-9]+) ([0-9a-f]{40})\t(.*)')
  72 def 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
  86 class 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
  96 unmergedRE = re.compile('^([0-9]+) ([0-9a-f]{40}) ([1-3])\t(.*)$')
  97 def 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
 128 def 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
 173 def 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
 390 def 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
 399 for 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
 411 print 'Merging', h1, 'with', h2
 412 h1 = runProgram(['git-rev-parse', '--verify', h1 + '^0']).rstrip()
 413 h2 = runProgram(['git-rev-parse', '--verify', h2 + '^0']).rstrip()
 414
 415 graph = buildGraph([h1, h2])
 416
 417 [res, clean] = merge(graph.shaMap[h1], graph.shaMap[h2],
 418                      firstBranch, secondBranch, graph)
 419
 420 print ''
 421
 422 if clean:
 423     sys.exit(0)
 424 else:
 425     print 'Automatic merge failed, fix up by hand'
 426     sys.exit(1)