3 import sys, math, random, os, re, signal, tempfile, stat, errno, traceback
4 from heapq import heappush, heappop
7 sys.path.append('''@@GIT_PYTHON_PATH@@''')
8 from gitMergeCommon import *
12 sys.stdout.write(' '*outputIndent)
15 originalIndexFile = os.environ.get('GIT_INDEX_FILE',
16 os.environ.get('GIT_DIR', '.git') + '/index')
17 temporaryIndexFile = os.environ.get('GIT_DIR', '.git') + \
18 '/merge-recursive-tmp-index'
19 def setupIndex(temporary):
21 os.unlink(temporaryIndexFile)
25 newIndex = temporaryIndexFile
27 newIndex = originalIndexFile
28 os.environ['GIT_INDEX_FILE'] = newIndex
30 # This is a global variable which is used in a number of places but
31 # only written to in the 'merge' function.
33 # cacheOnly == True => Don't leave any non-stage 0 entries in the cache and
34 # don't update the working directory.
35 # False => Leave unmerged entries in the cache and update
36 # the working directory.
40 # The entry point to the merge code
41 # ---------------------------------
43 def merge(h1, h2, branch1Name, branch2Name, graph, callDepth=0):
44 '''Merge the commits h1 and h2, return the resulting virtual
45 commit object and a flag indicating the cleaness of the merge.'''
46 assert(isinstance(h1, Commit) and isinstance(h2, Commit))
47 assert(isinstance(graph, Graph))
56 ca = getCommonAncestors(graph, h1, h2)
57 output('found', len(ca), 'common ancestor(s):')
64 outputIndent = callDepth+1
65 [mergedCA, dummy] = merge(mergedCA, h,
66 'Temporary merge branch 1',
67 'Temporary merge branch 2',
69 outputIndent = callDepth
70 assert(isinstance(mergedCA, Commit))
78 runProgram(['git-read-tree', h1.tree()])
81 [shaRes, clean] = mergeTrees(h1.tree(), h2.tree(), mergedCA.tree(),
82 branch1Name, branch2Name)
84 if clean or cacheOnly:
85 res = Commit(None, [h1, h2], tree=shaRes)
92 getFilesRE = re.compile(r'^([0-7]+) (\S+) ([0-9a-f]{40})\t(.*)$', re.S)
93 def getFilesAndDirs(tree):
96 out = runProgram(['git-ls-tree', '-r', '-z', tree])
97 for l in out.split('\0'):
98 m = getFilesRE.match(l)
100 if m.group(2) == 'tree':
102 elif m.group(2) == 'blob':
103 files.add(m.group(4))
107 # Those two global variables are used in a number of places but only
108 # written to in 'mergeTrees' and 'uniquePath'. They keep track of
109 # every file and directory in the two branches that are about to be
111 currentFileSet = None
112 currentDirectorySet = None
114 def mergeTrees(head, merge, common, branch1Name, branch2Name):
115 '''Merge the trees 'head' and 'merge' with the common ancestor
116 'common'. The name of the head branch is 'branch1Name' and the name of
117 the merge branch is 'branch2Name'. Return a tuple (tree, cleanMerge)
118 where tree is the resulting tree and cleanMerge is True iff the
121 assert(isSha(head) and isSha(merge) and isSha(common))
124 output('Already uptodate!')
132 [out, code] = runProgram(['git-read-tree', updateArg, '-m',
133 common, head, merge], returnCode = True)
135 die('git-read-tree:', out)
137 [tree, code] = runProgram('git-write-tree', returnCode=True)
140 global currentFileSet, currentDirectorySet
141 [currentFileSet, currentDirectorySet] = getFilesAndDirs(head)
142 [filesM, dirsM] = getFilesAndDirs(merge)
143 currentFileSet.union_update(filesM)
144 currentDirectorySet.union_update(dirsM)
146 entries = unmergedCacheEntries()
147 renamesHead = getRenames(head, common, head, merge, entries)
148 renamesMerge = getRenames(merge, common, head, merge, entries)
150 cleanMerge = processRenames(renamesHead, renamesMerge,
151 branch1Name, branch2Name)
152 for entry in entries:
155 if not processEntry(entry, branch1Name, branch2Name):
158 if cleanMerge or cacheOnly:
159 tree = runProgram('git-write-tree').rstrip()
165 return [tree, cleanMerge]
167 # Low level file merging, update and removal
168 # ------------------------------------------
170 def mergeFile(oPath, oSha, oMode, aPath, aSha, aMode, bPath, bSha, bMode,
171 branch1Name, branch2Name):
176 if stat.S_IFMT(aMode) != stat.S_IFMT(bMode):
178 if stat.S_ISREG(aMode):
185 if aSha != oSha and bSha != oSha:
197 elif stat.S_ISREG(aMode):
198 assert(stat.S_ISREG(bMode))
200 orig = runProgram(['git-unpack-file', oSha]).rstrip()
201 src1 = runProgram(['git-unpack-file', aSha]).rstrip()
202 src2 = runProgram(['git-unpack-file', bSha]).rstrip()
203 [out, code] = runProgram(['merge',
204 '-L', branch1Name + '/' + aPath,
205 '-L', 'orig/' + oPath,
206 '-L', branch2Name + '/' + bPath,
207 src1, orig, src2], returnCode=True)
209 sha = runProgram(['git-hash-object', '-t', 'blob', '-w',
218 assert(stat.S_ISLNK(aMode) and stat.S_ISLNK(bMode))
224 return [sha, mode, clean, merge]
226 def updateFile(clean, sha, mode, path):
227 updateCache = cacheOnly or clean
228 updateWd = not cacheOnly
230 return updateFileExt(sha, mode, path, updateCache, updateWd)
232 def updateFileExt(sha, mode, path, updateCache, updateWd):
237 pathComponents = path.split('/')
238 for x in xrange(1, len(pathComponents)):
239 p = '/'.join(pathComponents[0:x])
242 createDir = not stat.S_ISDIR(os.lstat(p).st_mode)
250 die("Couldn't create directory", p, e.strerror)
252 prog = ['git-cat-file', 'blob', sha]
253 if stat.S_ISREG(mode):
262 fd = os.open(path, os.O_WRONLY | os.O_TRUNC | os.O_CREAT, mode)
263 proc = subprocess.Popen(prog, stdout=fd)
266 elif stat.S_ISLNK(mode):
267 linkTarget = runProgram(prog)
268 os.symlink(linkTarget, path)
272 if updateWd and updateCache:
273 runProgram(['git-update-index', '--add', '--', path])
275 runProgram(['git-update-index', '--add', '--cacheinfo',
276 '0%o' % mode, sha, path])
278 def removeFile(clean, path):
279 updateCache = cacheOnly or clean
280 updateWd = not cacheOnly
283 runProgram(['git-update-index', '--force-remove', '--', path])
289 if e.errno != errno.ENOENT and e.errno != errno.EISDIR:
292 def uniquePath(path, branch):
293 def fileExists(path):
298 if e.errno == errno.ENOENT:
303 branch = branch.replace('/', '_')
304 newPath = path + '_' + branch
306 while newPath in currentFileSet or \
307 newPath in currentDirectorySet or \
310 newPath = path + '_' + branch + '_' + str(suffix)
311 currentFileSet.add(newPath)
314 # Cache entry management
315 # ----------------------
318 def __init__(self, path):
324 # Used for debugging only
326 if self.mode != None:
327 m = '0%o' % self.mode
335 return 'sha1: ' + sha1 + ' mode: ' + m
337 self.stages = [Stage(), Stage(), Stage(), Stage()]
339 self.processed = False
342 return 'path: ' + self.path + ' stages: ' + repr([str(x) for x in self.stages])
344 class CacheEntryContainer:
348 def add(self, entry):
349 self.entries[entry.path] = entry
352 return self.entries.get(path)
355 return self.entries.itervalues()
357 unmergedRE = re.compile(r'^([0-7]+) ([0-9a-f]{40}) ([1-3])\t(.*)$', re.S)
358 def unmergedCacheEntries():
359 '''Create a dictionary mapping file names to CacheEntry
360 objects. The dictionary contains one entry for every path with a
361 non-zero stage entry.'''
363 lines = runProgram(['git-ls-files', '-z', '--unmerged']).split('\0')
366 res = CacheEntryContainer()
368 m = unmergedRE.match(l)
370 mode = int(m.group(1), 8)
372 stage = int(m.group(3))
380 e.stages[stage].mode = mode
381 e.stages[stage].sha1 = sha1
383 die('Error: Merge program failed: Unexpected output from',
387 lsTreeRE = re.compile(r'^([0-7]+) (\S+) ([0-9a-f]{40})\t(.*)\n$', re.S)
388 def getCacheEntry(path, origTree, aTree, bTree):
389 '''Returns a CacheEntry object which doesn't have to correspond to
390 a real cache entry in Git's index.'''
396 m = lsTreeRE.match(out)
398 die('Unexpected output from git-ls-tree:', out)
399 elif m.group(2) == 'blob':
400 return [m.group(3), int(m.group(1), 8)]
404 res = CacheEntry(path)
406 [oSha, oMode] = parse(runProgram(['git-ls-tree', origTree, '--', path]))
407 [aSha, aMode] = parse(runProgram(['git-ls-tree', aTree, '--', path]))
408 [bSha, bMode] = parse(runProgram(['git-ls-tree', bTree, '--', path]))
410 res.stages[1].sha1 = oSha
411 res.stages[1].mode = oMode
412 res.stages[2].sha1 = aSha
413 res.stages[2].mode = aMode
414 res.stages[3].sha1 = bSha
415 res.stages[3].mode = bMode
419 # Rename detection and handling
420 # -----------------------------
424 src, srcSha, srcMode, srcCacheEntry,
425 dst, dstSha, dstMode, dstCacheEntry,
429 self.srcMode = srcMode
430 self.srcCacheEntry = srcCacheEntry
433 self.dstMode = dstMode
434 self.dstCacheEntry = dstCacheEntry
437 self.processed = False
439 class RenameEntryContainer:
444 def add(self, entry):
445 self.entriesSrc[entry.srcName] = entry
446 self.entriesDst[entry.dstName] = entry
448 def getSrc(self, path):
449 return self.entriesSrc.get(path)
451 def getDst(self, path):
452 return self.entriesDst.get(path)
455 return self.entriesSrc.itervalues()
457 parseDiffRenamesRE = re.compile('^:([0-7]+) ([0-7]+) ([0-9a-f]{40}) ([0-9a-f]{40}) R([0-9]*)$')
458 def getRenames(tree, oTree, aTree, bTree, cacheEntries):
459 '''Get information of all renames which occured between 'oTree' and
460 'tree'. We need the three trees in the merge ('oTree', 'aTree' and
461 'bTree') to be able to associate the correct cache entries with
462 the rename information. 'tree' is always equal to either aTree or bTree.'''
464 assert(tree == aTree or tree == bTree)
465 inp = runProgram(['git-diff-tree', '-M', '--diff-filter=R', '-r',
468 ret = RenameEntryContainer()
470 recs = inp.split("\0")
471 recs.pop() # remove last entry (which is '')
475 m = parseDiffRenamesRE.match(rec)
478 die('Unexpected output from git-diff-tree:', rec)
480 srcMode = int(m.group(1), 8)
481 dstMode = int(m.group(2), 8)
488 srcCacheEntry = cacheEntries.get(src)
489 if not srcCacheEntry:
490 srcCacheEntry = getCacheEntry(src, oTree, aTree, bTree)
491 cacheEntries.add(srcCacheEntry)
493 dstCacheEntry = cacheEntries.get(dst)
494 if not dstCacheEntry:
495 dstCacheEntry = getCacheEntry(dst, oTree, aTree, bTree)
496 cacheEntries.add(dstCacheEntry)
498 ret.add(RenameEntry(src, srcSha, srcMode, srcCacheEntry,
499 dst, dstSha, dstMode, dstCacheEntry,
501 except StopIteration:
505 def fmtRename(src, dst):
506 srcPath = src.split('/')
507 dstPath = dst.split('/')
509 endIndex = min(len(srcPath), len(dstPath)) - 1
510 for x in range(0, endIndex):
511 if srcPath[x] == dstPath[x]:
512 path.append(srcPath[x])
518 return '/'.join(path) + \
519 '/{' + '/'.join(srcPath[endIndex:]) + ' => ' + \
520 '/'.join(dstPath[endIndex:]) + '}'
522 return src + ' => ' + dst
524 def processRenames(renamesA, renamesB, branchNameA, branchNameB):
527 srcNames.add(x.srcName)
529 srcNames.add(x.srcName)
532 for path in srcNames:
533 if renamesA.getSrc(path):
536 branchName1 = branchNameA
537 branchName2 = branchNameB
541 branchName1 = branchNameB
542 branchName2 = branchNameA
544 ren1 = renames1.getSrc(path)
545 ren2 = renames2.getSrc(path)
547 ren1.dstCacheEntry.processed = True
548 ren1.srcCacheEntry.processed = True
553 ren1.processed = True
554 removeFile(True, ren1.srcName)
556 # Renamed in 1 and renamed in 2
557 assert(ren1.srcName == ren2.srcName)
558 ren2.dstCacheEntry.processed = True
559 ren2.processed = True
561 if ren1.dstName != ren2.dstName:
562 output('CONFLICT (rename/rename): Rename',
563 fmtRename(path, ren1.dstName), 'in branch', branchName1,
564 'rename', fmtRename(path, ren2.dstName), 'in',
568 if ren1.dstName in currentDirectorySet:
569 dstName1 = uniquePath(ren1.dstName, branchName1)
570 output(ren1.dstName, 'is a directory in', branchName2,
571 'adding as', dstName1, 'instead.')
572 removeFile(False, ren1.dstName)
574 dstName1 = ren1.dstName
576 if ren2.dstName in currentDirectorySet:
577 dstName2 = uniquePath(ren2.dstName, branchName2)
578 output(ren2.dstName, 'is a directory in', branchName1,
579 'adding as', dstName2, 'instead.')
580 removeFile(False, ren2.dstName)
582 dstName2 = ren1.dstName
584 updateFile(False, ren1.dstSha, ren1.dstMode, dstName1)
585 updateFile(False, ren2.dstSha, ren2.dstMode, dstName2)
587 [resSha, resMode, clean, merge] = \
588 mergeFile(ren1.srcName, ren1.srcSha, ren1.srcMode,
589 ren1.dstName, ren1.dstSha, ren1.dstMode,
590 ren2.dstName, ren2.dstSha, ren2.dstMode,
591 branchName1, branchName2)
593 if merge or not clean:
594 output('Renaming', fmtRename(path, ren1.dstName))
597 output('Auto-merging', ren1.dstName)
600 output('CONFLICT (content): merge conflict in',
605 updateFileExt(ren1.dstSha, ren1.dstMode, ren1.dstName,
606 updateCache=True, updateWd=False)
607 updateFile(clean, resSha, resMode, ren1.dstName)
609 # Renamed in 1, maybe changed in 2
610 if renamesA == renames1:
615 srcShaOtherBranch = ren1.srcCacheEntry.stages[stage].sha1
616 srcModeOtherBranch = ren1.srcCacheEntry.stages[stage].mode
618 dstShaOtherBranch = ren1.dstCacheEntry.stages[stage].sha1
619 dstModeOtherBranch = ren1.dstCacheEntry.stages[stage].mode
623 if ren1.dstName in currentDirectorySet:
624 newPath = uniquePath(ren1.dstName, branchName1)
625 output('CONFLICT (rename/directory): Rename',
626 fmtRename(ren1.srcName, ren1.dstName), 'in', branchName1,
627 'directory', ren1.dstName, 'added in', branchName2)
628 output('Renaming', ren1.srcName, 'to', newPath, 'instead')
630 removeFile(False, ren1.dstName)
631 updateFile(False, ren1.dstSha, ren1.dstMode, newPath)
632 elif srcShaOtherBranch == None:
633 output('CONFLICT (rename/delete): Rename',
634 fmtRename(ren1.srcName, ren1.dstName), 'in',
635 branchName1, 'and deleted in', branchName2)
637 updateFile(False, ren1.dstSha, ren1.dstMode, ren1.dstName)
638 elif dstShaOtherBranch:
639 newPath = uniquePath(ren1.dstName, branchName2)
640 output('CONFLICT (rename/add): Rename',
641 fmtRename(ren1.srcName, ren1.dstName), 'in',
642 branchName1 + '.', ren1.dstName, 'added in', branchName2)
643 output('Adding as', newPath, 'instead')
644 updateFile(False, dstShaOtherBranch, dstModeOtherBranch, newPath)
647 elif renames2.getDst(ren1.dstName):
648 dst2 = renames2.getDst(ren1.dstName)
649 newPath1 = uniquePath(ren1.dstName, branchName1)
650 newPath2 = uniquePath(dst2.dstName, branchName2)
651 output('CONFLICT (rename/rename): Rename',
652 fmtRename(ren1.srcName, ren1.dstName), 'in',
653 branchName1+'. Rename',
654 fmtRename(dst2.srcName, dst2.dstName), 'in', branchName2)
655 output('Renaming', ren1.srcName, 'to', newPath1, 'and',
656 dst2.srcName, 'to', newPath2, 'instead')
657 removeFile(False, ren1.dstName)
658 updateFile(False, ren1.dstSha, ren1.dstMode, newPath1)
659 updateFile(False, dst2.dstSha, dst2.dstMode, newPath2)
660 dst2.processed = True
666 [resSha, resMode, clean, merge] = \
667 mergeFile(ren1.srcName, ren1.srcSha, ren1.srcMode,
668 ren1.dstName, ren1.dstSha, ren1.dstMode,
669 ren1.srcName, srcShaOtherBranch, srcModeOtherBranch,
670 branchName1, branchName2)
672 if merge or not clean:
673 output('Renaming', fmtRename(ren1.srcName, ren1.dstName))
676 output('Auto-merging', ren1.dstName)
679 output('CONFLICT (rename/modify): Merge conflict in',
684 updateFileExt(ren1.dstSha, ren1.dstMode, ren1.dstName,
685 updateCache=True, updateWd=False)
686 updateFile(clean, resSha, resMode, ren1.dstName)
690 # Per entry merge function
691 # ------------------------
693 def processEntry(entry, branch1Name, branch2Name):
694 '''Merge one cache entry.'''
696 debug('processing', entry.path, 'clean cache:', cacheOnly)
701 oSha = entry.stages[1].sha1
702 oMode = entry.stages[1].mode
703 aSha = entry.stages[2].sha1
704 aMode = entry.stages[2].mode
705 bSha = entry.stages[3].sha1
706 bMode = entry.stages[3].mode
708 assert(oSha == None or isSha(oSha))
709 assert(aSha == None or isSha(aSha))
710 assert(bSha == None or isSha(bSha))
712 assert(oMode == None or type(oMode) is int)
713 assert(aMode == None or type(aMode) is int)
714 assert(bMode == None or type(bMode) is int)
716 if (oSha and (not aSha or not bSha)):
718 # Case A: Deleted in one
720 if (not aSha and not bSha) or \
721 (aSha == oSha and not bSha) or \
722 (not aSha and bSha == oSha):
723 # Deleted in both or deleted in one and unchanged in the other
725 output('Removing', path)
726 removeFile(True, path)
728 # Deleted in one and changed in the other
731 output('CONFLICT (delete/modify):', path, 'deleted in',
732 branch1Name, 'and modified in', branch2Name + '.',
733 'Version', branch2Name, 'of', path, 'left in tree.')
737 output('CONFLICT (modify/delete):', path, 'deleted in',
738 branch2Name, 'and modified in', branch1Name + '.',
739 'Version', branch1Name, 'of', path, 'left in tree.')
743 updateFile(False, sha, mode, path)
745 elif (not oSha and aSha and not bSha) or \
746 (not oSha and not aSha and bSha):
748 # Case B: Added in one.
751 addBranch = branch1Name
752 otherBranch = branch2Name
755 conf = 'file/directory'
757 addBranch = branch2Name
758 otherBranch = branch1Name
761 conf = 'directory/file'
763 if path in currentDirectorySet:
765 newPath = uniquePath(path, addBranch)
766 output('CONFLICT (' + conf + '):',
767 'There is a directory with name', path, 'in',
768 otherBranch + '. Adding', path, 'as', newPath)
770 removeFile(False, path)
771 updateFile(False, sha, mode, newPath)
773 output('Adding', path)
774 updateFile(True, sha, mode, path)
776 elif not oSha and aSha and bSha:
778 # Case C: Added in both (check for same permissions).
783 output('CONFLICT: File', path,
784 'added identically in both branches, but permissions',
785 'conflict', '0%o' % aMode, '->', '0%o' % bMode)
786 output('CONFLICT: adding with permission:', '0%o' % aMode)
788 updateFile(False, aSha, aMode, path)
790 # This case is handled by git-read-tree
794 newPath1 = uniquePath(path, branch1Name)
795 newPath2 = uniquePath(path, branch2Name)
796 output('CONFLICT (add/add): File', path,
797 'added non-identically in both branches. Adding as',
798 newPath1, 'and', newPath2, 'instead.')
799 removeFile(False, path)
800 updateFile(False, aSha, aMode, newPath1)
801 updateFile(False, bSha, bMode, newPath2)
803 elif oSha and aSha and bSha:
805 # case D: Modified in both, but differently.
807 output('Auto-merging', path)
808 [sha, mode, clean, dummy] = \
809 mergeFile(path, oSha, oMode,
812 branch1Name, branch2Name)
814 updateFile(True, sha, mode, path)
817 output('CONFLICT (content): Merge conflict in', path)
820 updateFile(False, sha, mode, path)
822 updateFileExt(aSha, aMode, path,
823 updateCache=True, updateWd=False)
824 updateFileExt(sha, mode, path, updateCache=False, updateWd=True)
826 die("ERROR: Fatal merge failure, shouldn't happen.")
831 die('Usage:', sys.argv[0], ' <base>... -- <head> <remote>..')
833 # main entry point as merge strategy module
834 # The first parameters up to -- are merge bases, and the rest are heads.
835 # This strategy module figures out merge bases itself, so we only
838 if len(sys.argv) < 4:
841 for nextArg in xrange(1, len(sys.argv)):
842 if sys.argv[nextArg] == '--':
843 if len(sys.argv) != nextArg + 3:
844 die('Not handling anything other than two heads merge.')
846 h1 = firstBranch = sys.argv[nextArg + 1]
847 h2 = secondBranch = sys.argv[nextArg + 2]
852 print 'Merging', h1, 'with', h2
855 h1 = runProgram(['git-rev-parse', '--verify', h1 + '^0']).rstrip()
856 h2 = runProgram(['git-rev-parse', '--verify', h2 + '^0']).rstrip()
858 graph = buildGraph([h1, h2])
860 [dummy, clean] = merge(graph.shaMap[h1], graph.shaMap[h2],
861 firstBranch, secondBranch, graph)
865 if isinstance(sys.exc_info()[1], SystemExit):
868 traceback.print_exc(None, sys.stderr)