3 # Copyright (C) 2005 Fredrik Kuivinen
7 sys.path.append('''@@GIT_PYTHON_PATH@@''')
9 import math, random, os, re, signal, tempfile, stat, errno, traceback
10 from heapq import heappush, heappop
13 from gitMergeCommon import *
17 sys.stdout.write(' '*outputIndent)
20 originalIndexFile = os.environ.get('GIT_INDEX_FILE',
21 os.environ.get('GIT_DIR', '.git') + '/index')
22 temporaryIndexFile = os.environ.get('GIT_DIR', '.git') + \
23 '/merge-recursive-tmp-index'
24 def setupIndex(temporary):
26 os.unlink(temporaryIndexFile)
30 newIndex = temporaryIndexFile
32 newIndex = originalIndexFile
33 os.environ['GIT_INDEX_FILE'] = newIndex
35 # This is a global variable which is used in a number of places but
36 # only written to in the 'merge' function.
38 # cacheOnly == True => Don't leave any non-stage 0 entries in the cache and
39 # don't update the working directory.
40 # False => Leave unmerged entries in the cache and update
41 # the working directory.
45 # The entry point to the merge code
46 # ---------------------------------
48 def merge(h1, h2, branch1Name, branch2Name, graph, callDepth=0):
49 '''Merge the commits h1 and h2, return the resulting virtual
50 commit object and a flag indicating the cleaness of the merge.'''
51 assert(isinstance(h1, Commit) and isinstance(h2, Commit))
52 assert(isinstance(graph, Graph))
61 ca = getCommonAncestors(graph, h1, h2)
62 output('found', len(ca), 'common ancestor(s):')
69 outputIndent = callDepth+1
70 [mergedCA, dummy] = merge(mergedCA, h,
71 'Temporary merge branch 1',
72 'Temporary merge branch 2',
74 outputIndent = callDepth
75 assert(isinstance(mergedCA, Commit))
83 runProgram(['git-read-tree', h1.tree()])
86 [shaRes, clean] = mergeTrees(h1.tree(), h2.tree(), mergedCA.tree(),
87 branch1Name, branch2Name)
89 if clean or cacheOnly:
90 res = Commit(None, [h1, h2], tree=shaRes)
97 getFilesRE = re.compile(r'^([0-7]+) (\S+) ([0-9a-f]{40})\t(.*)$', re.S)
98 def getFilesAndDirs(tree):
101 out = runProgram(['git-ls-tree', '-r', '-z', '-t', tree])
102 for l in out.split('\0'):
103 m = getFilesRE.match(l)
105 if m.group(2) == 'tree':
107 elif m.group(2) == 'blob':
108 files.add(m.group(4))
112 # Those two global variables are used in a number of places but only
113 # written to in 'mergeTrees' and 'uniquePath'. They keep track of
114 # every file and directory in the two branches that are about to be
116 currentFileSet = None
117 currentDirectorySet = None
119 def mergeTrees(head, merge, common, branch1Name, branch2Name):
120 '''Merge the trees 'head' and 'merge' with the common ancestor
121 'common'. The name of the head branch is 'branch1Name' and the name of
122 the merge branch is 'branch2Name'. Return a tuple (tree, cleanMerge)
123 where tree is the resulting tree and cleanMerge is True iff the
126 assert(isSha(head) and isSha(merge) and isSha(common))
129 output('Already uptodate!')
137 [out, code] = runProgram(['git-read-tree', updateArg, '-m',
138 common, head, merge], returnCode = True)
140 die('git-read-tree:', out)
142 [tree, code] = runProgram('git-write-tree', returnCode=True)
145 global currentFileSet, currentDirectorySet
146 [currentFileSet, currentDirectorySet] = getFilesAndDirs(head)
147 [filesM, dirsM] = getFilesAndDirs(merge)
148 currentFileSet.union_update(filesM)
149 currentDirectorySet.union_update(dirsM)
151 entries = unmergedCacheEntries()
152 renamesHead = getRenames(head, common, head, merge, entries)
153 renamesMerge = getRenames(merge, common, head, merge, entries)
155 cleanMerge = processRenames(renamesHead, renamesMerge,
156 branch1Name, branch2Name)
157 for entry in entries:
160 if not processEntry(entry, branch1Name, branch2Name):
163 if cleanMerge or cacheOnly:
164 tree = runProgram('git-write-tree').rstrip()
170 return [tree, cleanMerge]
172 # Low level file merging, update and removal
173 # ------------------------------------------
175 def mergeFile(oPath, oSha, oMode, aPath, aSha, aMode, bPath, bSha, bMode,
176 branch1Name, branch2Name):
181 if stat.S_IFMT(aMode) != stat.S_IFMT(bMode):
183 if stat.S_ISREG(aMode):
190 if aSha != oSha and bSha != oSha:
202 elif stat.S_ISREG(aMode):
203 assert(stat.S_ISREG(bMode))
205 orig = runProgram(['git-unpack-file', oSha]).rstrip()
206 src1 = runProgram(['git-unpack-file', aSha]).rstrip()
207 src2 = runProgram(['git-unpack-file', bSha]).rstrip()
208 [out, code] = runProgram(['merge',
209 '-L', branch1Name + '/' + aPath,
210 '-L', 'orig/' + oPath,
211 '-L', branch2Name + '/' + bPath,
212 src1, orig, src2], returnCode=True)
214 sha = runProgram(['git-hash-object', '-t', 'blob', '-w',
223 assert(stat.S_ISLNK(aMode) and stat.S_ISLNK(bMode))
229 return [sha, mode, clean, merge]
231 def updateFile(clean, sha, mode, path):
232 updateCache = cacheOnly or clean
233 updateWd = not cacheOnly
235 return updateFileExt(sha, mode, path, updateCache, updateWd)
237 def updateFileExt(sha, mode, path, updateCache, updateWd):
242 pathComponents = path.split('/')
243 for x in xrange(1, len(pathComponents)):
244 p = '/'.join(pathComponents[0:x])
247 createDir = not stat.S_ISDIR(os.lstat(p).st_mode)
255 die("Couldn't create directory", p, e.strerror)
257 prog = ['git-cat-file', 'blob', sha]
258 if stat.S_ISREG(mode):
267 fd = os.open(path, os.O_WRONLY | os.O_TRUNC | os.O_CREAT, mode)
268 proc = subprocess.Popen(prog, stdout=fd)
271 elif stat.S_ISLNK(mode):
272 linkTarget = runProgram(prog)
273 os.symlink(linkTarget, path)
277 if updateWd and updateCache:
278 runProgram(['git-update-index', '--add', '--', path])
280 runProgram(['git-update-index', '--add', '--cacheinfo',
281 '0%o' % mode, sha, path])
283 def setIndexStages(path,
287 prog = ['git-update-index', '-z', '--index-info']
288 proc = subprocess.Popen(prog, stdin=subprocess.PIPE)
290 # Clear stages first.
291 pipe.write("0 " + ("0" * 40) + "\t" + path + "\0")
293 pipe.write("%o %s %d\t%s\0" % (oMode, oSHA1, 1, path))
294 pipe.write("%o %s %d\t%s\0" % (aMode, aSHA1, 2, path))
295 pipe.write("%o %s %d\t%s\0" % (bMode, bSHA1, 3, path))
299 def removeFile(clean, path):
300 updateCache = cacheOnly or clean
301 updateWd = not cacheOnly
304 runProgram(['git-update-index', '--force-remove', '--', path])
310 if e.errno != errno.ENOENT and e.errno != errno.EISDIR:
313 os.removedirs(os.path.dirname(path))
317 def uniquePath(path, branch):
318 def fileExists(path):
323 if e.errno == errno.ENOENT:
328 branch = branch.replace('/', '_')
329 newPath = path + '~' + branch
331 while newPath in currentFileSet or \
332 newPath in currentDirectorySet or \
335 newPath = path + '~' + branch + '_' + str(suffix)
336 currentFileSet.add(newPath)
339 # Cache entry management
340 # ----------------------
343 def __init__(self, path):
349 # Used for debugging only
351 if self.mode != None:
352 m = '0%o' % self.mode
360 return 'sha1: ' + sha1 + ' mode: ' + m
362 self.stages = [Stage(), Stage(), Stage(), Stage()]
364 self.processed = False
367 return 'path: ' + self.path + ' stages: ' + repr([str(x) for x in self.stages])
369 class CacheEntryContainer:
373 def add(self, entry):
374 self.entries[entry.path] = entry
377 return self.entries.get(path)
380 return self.entries.itervalues()
382 unmergedRE = re.compile(r'^([0-7]+) ([0-9a-f]{40}) ([1-3])\t(.*)$', re.S)
383 def unmergedCacheEntries():
384 '''Create a dictionary mapping file names to CacheEntry
385 objects. The dictionary contains one entry for every path with a
386 non-zero stage entry.'''
388 lines = runProgram(['git-ls-files', '-z', '--unmerged']).split('\0')
391 res = CacheEntryContainer()
393 m = unmergedRE.match(l)
395 mode = int(m.group(1), 8)
397 stage = int(m.group(3))
405 e.stages[stage].mode = mode
406 e.stages[stage].sha1 = sha1
408 die('Error: Merge program failed: Unexpected output from',
412 lsTreeRE = re.compile(r'^([0-7]+) (\S+) ([0-9a-f]{40})\t(.*)\n$', re.S)
413 def getCacheEntry(path, origTree, aTree, bTree):
414 '''Returns a CacheEntry object which doesn't have to correspond to
415 a real cache entry in Git's index.'''
421 m = lsTreeRE.match(out)
423 die('Unexpected output from git-ls-tree:', out)
424 elif m.group(2) == 'blob':
425 return [m.group(3), int(m.group(1), 8)]
429 res = CacheEntry(path)
431 [oSha, oMode] = parse(runProgram(['git-ls-tree', origTree, '--', path]))
432 [aSha, aMode] = parse(runProgram(['git-ls-tree', aTree, '--', path]))
433 [bSha, bMode] = parse(runProgram(['git-ls-tree', bTree, '--', path]))
435 res.stages[1].sha1 = oSha
436 res.stages[1].mode = oMode
437 res.stages[2].sha1 = aSha
438 res.stages[2].mode = aMode
439 res.stages[3].sha1 = bSha
440 res.stages[3].mode = bMode
444 # Rename detection and handling
445 # -----------------------------
449 src, srcSha, srcMode, srcCacheEntry,
450 dst, dstSha, dstMode, dstCacheEntry,
454 self.srcMode = srcMode
455 self.srcCacheEntry = srcCacheEntry
458 self.dstMode = dstMode
459 self.dstCacheEntry = dstCacheEntry
462 self.processed = False
464 class RenameEntryContainer:
469 def add(self, entry):
470 self.entriesSrc[entry.srcName] = entry
471 self.entriesDst[entry.dstName] = entry
473 def getSrc(self, path):
474 return self.entriesSrc.get(path)
476 def getDst(self, path):
477 return self.entriesDst.get(path)
480 return self.entriesSrc.itervalues()
482 parseDiffRenamesRE = re.compile('^:([0-7]+) ([0-7]+) ([0-9a-f]{40}) ([0-9a-f]{40}) R([0-9]*)$')
483 def getRenames(tree, oTree, aTree, bTree, cacheEntries):
484 '''Get information of all renames which occured between 'oTree' and
485 'tree'. We need the three trees in the merge ('oTree', 'aTree' and
486 'bTree') to be able to associate the correct cache entries with
487 the rename information. 'tree' is always equal to either aTree or bTree.'''
489 assert(tree == aTree or tree == bTree)
490 inp = runProgram(['git-diff-tree', '-M', '--diff-filter=R', '-r',
493 ret = RenameEntryContainer()
495 recs = inp.split("\0")
496 recs.pop() # remove last entry (which is '')
500 m = parseDiffRenamesRE.match(rec)
503 die('Unexpected output from git-diff-tree:', rec)
505 srcMode = int(m.group(1), 8)
506 dstMode = int(m.group(2), 8)
513 srcCacheEntry = cacheEntries.get(src)
514 if not srcCacheEntry:
515 srcCacheEntry = getCacheEntry(src, oTree, aTree, bTree)
516 cacheEntries.add(srcCacheEntry)
518 dstCacheEntry = cacheEntries.get(dst)
519 if not dstCacheEntry:
520 dstCacheEntry = getCacheEntry(dst, oTree, aTree, bTree)
521 cacheEntries.add(dstCacheEntry)
523 ret.add(RenameEntry(src, srcSha, srcMode, srcCacheEntry,
524 dst, dstSha, dstMode, dstCacheEntry,
526 except StopIteration:
530 def fmtRename(src, dst):
531 srcPath = src.split('/')
532 dstPath = dst.split('/')
534 endIndex = min(len(srcPath), len(dstPath)) - 1
535 for x in range(0, endIndex):
536 if srcPath[x] == dstPath[x]:
537 path.append(srcPath[x])
543 return '/'.join(path) + \
544 '/{' + '/'.join(srcPath[endIndex:]) + ' => ' + \
545 '/'.join(dstPath[endIndex:]) + '}'
547 return src + ' => ' + dst
549 def processRenames(renamesA, renamesB, branchNameA, branchNameB):
552 srcNames.add(x.srcName)
554 srcNames.add(x.srcName)
557 for path in srcNames:
558 if renamesA.getSrc(path):
561 branchName1 = branchNameA
562 branchName2 = branchNameB
566 branchName1 = branchNameB
567 branchName2 = branchNameA
569 ren1 = renames1.getSrc(path)
570 ren2 = renames2.getSrc(path)
572 ren1.dstCacheEntry.processed = True
573 ren1.srcCacheEntry.processed = True
578 ren1.processed = True
579 removeFile(True, ren1.srcName)
581 # Renamed in 1 and renamed in 2
582 assert(ren1.srcName == ren2.srcName)
583 ren2.dstCacheEntry.processed = True
584 ren2.processed = True
586 if ren1.dstName != ren2.dstName:
587 output('CONFLICT (rename/rename): Rename',
588 fmtRename(path, ren1.dstName), 'in branch', branchName1,
589 'rename', fmtRename(path, ren2.dstName), 'in',
593 if ren1.dstName in currentDirectorySet:
594 dstName1 = uniquePath(ren1.dstName, branchName1)
595 output(ren1.dstName, 'is a directory in', branchName2,
596 'adding as', dstName1, 'instead.')
597 removeFile(False, ren1.dstName)
599 dstName1 = ren1.dstName
601 if ren2.dstName in currentDirectorySet:
602 dstName2 = uniquePath(ren2.dstName, branchName2)
603 output(ren2.dstName, 'is a directory in', branchName1,
604 'adding as', dstName2, 'instead.')
605 removeFile(False, ren2.dstName)
607 dstName2 = ren1.dstName
609 # NEEDSWORK: place dstNameA at stage 2 and dstNameB at stage 3
610 # What about other stages???
611 updateFile(False, ren1.dstSha, ren1.dstMode, dstName1)
612 updateFile(False, ren2.dstSha, ren2.dstMode, dstName2)
614 [resSha, resMode, clean, merge] = \
615 mergeFile(ren1.srcName, ren1.srcSha, ren1.srcMode,
616 ren1.dstName, ren1.dstSha, ren1.dstMode,
617 ren2.dstName, ren2.dstSha, ren2.dstMode,
618 branchName1, branchName2)
620 if merge or not clean:
621 output('Renaming', fmtRename(path, ren1.dstName))
624 output('Auto-merging', ren1.dstName)
627 output('CONFLICT (content): merge conflict in',
632 setIndexStages(ren1.dstName,
633 ren1.srcSha, ren1.srcMode,
634 ren1.dstSha, ren1.dstMode,
635 ren2.dstSha, ren2.dstMode)
637 updateFile(clean, resSha, resMode, ren1.dstName)
639 # Renamed in 1, maybe changed in 2
640 if renamesA == renames1:
645 srcShaOtherBranch = ren1.srcCacheEntry.stages[stage].sha1
646 srcModeOtherBranch = ren1.srcCacheEntry.stages[stage].mode
648 dstShaOtherBranch = ren1.dstCacheEntry.stages[stage].sha1
649 dstModeOtherBranch = ren1.dstCacheEntry.stages[stage].mode
653 if ren1.dstName in currentDirectorySet:
654 newPath = uniquePath(ren1.dstName, branchName1)
655 output('CONFLICT (rename/directory): Rename',
656 fmtRename(ren1.srcName, ren1.dstName), 'in', branchName1,
657 'directory', ren1.dstName, 'added in', branchName2)
658 output('Renaming', ren1.srcName, 'to', newPath, 'instead')
660 removeFile(False, ren1.dstName)
661 updateFile(False, ren1.dstSha, ren1.dstMode, newPath)
662 elif srcShaOtherBranch == None:
663 output('CONFLICT (rename/delete): Rename',
664 fmtRename(ren1.srcName, ren1.dstName), 'in',
665 branchName1, 'and deleted in', branchName2)
667 updateFile(False, ren1.dstSha, ren1.dstMode, ren1.dstName)
668 elif dstShaOtherBranch:
669 newPath = uniquePath(ren1.dstName, branchName2)
670 output('CONFLICT (rename/add): Rename',
671 fmtRename(ren1.srcName, ren1.dstName), 'in',
672 branchName1 + '.', ren1.dstName, 'added in', branchName2)
673 output('Adding as', newPath, 'instead')
674 updateFile(False, dstShaOtherBranch, dstModeOtherBranch, newPath)
677 elif renames2.getDst(ren1.dstName):
678 dst2 = renames2.getDst(ren1.dstName)
679 newPath1 = uniquePath(ren1.dstName, branchName1)
680 newPath2 = uniquePath(dst2.dstName, branchName2)
681 output('CONFLICT (rename/rename): Rename',
682 fmtRename(ren1.srcName, ren1.dstName), 'in',
683 branchName1+'. Rename',
684 fmtRename(dst2.srcName, dst2.dstName), 'in', branchName2)
685 output('Renaming', ren1.srcName, 'to', newPath1, 'and',
686 dst2.srcName, 'to', newPath2, 'instead')
687 removeFile(False, ren1.dstName)
688 updateFile(False, ren1.dstSha, ren1.dstMode, newPath1)
689 updateFile(False, dst2.dstSha, dst2.dstMode, newPath2)
690 dst2.processed = True
697 oName, oSHA1, oMode = ren1.srcName, ren1.srcSha, ren1.srcMode
698 aName, bName = ren1.dstName, ren1.srcName
699 aSHA1, bSHA1 = ren1.dstSha, srcShaOtherBranch
700 aMode, bMode = ren1.dstMode, srcModeOtherBranch
701 aBranch, bBranch = branchName1, branchName2
703 if renamesA != renames1:
704 aName, bName = bName, aName
705 aSHA1, bSHA1 = bSHA1, aSHA1
706 aMode, bMode = bMode, aMode
707 aBranch, bBranch = bBranch, aBranch
709 [resSha, resMode, clean, merge] = \
710 mergeFile(oName, oSHA1, oMode,
715 if merge or not clean:
716 output('Renaming', fmtRename(ren1.srcName, ren1.dstName))
719 output('Auto-merging', ren1.dstName)
722 output('CONFLICT (rename/modify): Merge conflict in',
728 setIndexStages(ren1.dstName,
733 updateFile(clean, resSha, resMode, ren1.dstName)
737 # Per entry merge function
738 # ------------------------
740 def processEntry(entry, branch1Name, branch2Name):
741 '''Merge one cache entry.'''
743 debug('processing', entry.path, 'clean cache:', cacheOnly)
748 oSha = entry.stages[1].sha1
749 oMode = entry.stages[1].mode
750 aSha = entry.stages[2].sha1
751 aMode = entry.stages[2].mode
752 bSha = entry.stages[3].sha1
753 bMode = entry.stages[3].mode
755 assert(oSha == None or isSha(oSha))
756 assert(aSha == None or isSha(aSha))
757 assert(bSha == None or isSha(bSha))
759 assert(oMode == None or type(oMode) is int)
760 assert(aMode == None or type(aMode) is int)
761 assert(bMode == None or type(bMode) is int)
763 if (oSha and (not aSha or not bSha)):
765 # Case A: Deleted in one
767 if (not aSha and not bSha) or \
768 (aSha == oSha and not bSha) or \
769 (not aSha and bSha == oSha):
770 # Deleted in both or deleted in one and unchanged in the other
772 output('Removing', path)
773 removeFile(True, path)
775 # Deleted in one and changed in the other
778 output('CONFLICT (delete/modify):', path, 'deleted in',
779 branch1Name, 'and modified in', branch2Name + '.',
780 'Version', branch2Name, 'of', path, 'left in tree.')
784 output('CONFLICT (modify/delete):', path, 'deleted in',
785 branch2Name, 'and modified in', branch1Name + '.',
786 'Version', branch1Name, 'of', path, 'left in tree.')
790 updateFile(False, sha, mode, path)
792 elif (not oSha and aSha and not bSha) or \
793 (not oSha and not aSha and bSha):
795 # Case B: Added in one.
798 addBranch = branch1Name
799 otherBranch = branch2Name
802 conf = 'file/directory'
804 addBranch = branch2Name
805 otherBranch = branch1Name
808 conf = 'directory/file'
810 if path in currentDirectorySet:
812 newPath = uniquePath(path, addBranch)
813 output('CONFLICT (' + conf + '):',
814 'There is a directory with name', path, 'in',
815 otherBranch + '. Adding', path, 'as', newPath)
817 removeFile(False, path)
818 updateFile(False, sha, mode, newPath)
820 output('Adding', path)
821 updateFile(True, sha, mode, path)
823 elif not oSha and aSha and bSha:
825 # Case C: Added in both (check for same permissions).
830 output('CONFLICT: File', path,
831 'added identically in both branches, but permissions',
832 'conflict', '0%o' % aMode, '->', '0%o' % bMode)
833 output('CONFLICT: adding with permission:', '0%o' % aMode)
835 updateFile(False, aSha, aMode, path)
837 # This case is handled by git-read-tree
841 newPath1 = uniquePath(path, branch1Name)
842 newPath2 = uniquePath(path, branch2Name)
843 output('CONFLICT (add/add): File', path,
844 'added non-identically in both branches. Adding as',
845 newPath1, 'and', newPath2, 'instead.')
846 removeFile(False, path)
847 updateFile(False, aSha, aMode, newPath1)
848 updateFile(False, bSha, bMode, newPath2)
850 elif oSha and aSha and bSha:
852 # case D: Modified in both, but differently.
854 output('Auto-merging', path)
855 [sha, mode, clean, dummy] = \
856 mergeFile(path, oSha, oMode,
859 branch1Name, branch2Name)
861 updateFile(True, sha, mode, path)
864 output('CONFLICT (content): Merge conflict in', path)
867 updateFile(False, sha, mode, path)
869 updateFileExt(sha, mode, path, updateCache=False, updateWd=True)
871 die("ERROR: Fatal merge failure, shouldn't happen.")
876 die('Usage:', sys.argv[0], ' <base>... -- <head> <remote>..')
878 # main entry point as merge strategy module
879 # The first parameters up to -- are merge bases, and the rest are heads.
880 # This strategy module figures out merge bases itself, so we only
883 if len(sys.argv) < 4:
886 for nextArg in xrange(1, len(sys.argv)):
887 if sys.argv[nextArg] == '--':
888 if len(sys.argv) != nextArg + 3:
889 die('Not handling anything other than two heads merge.')
891 h1 = firstBranch = sys.argv[nextArg + 1]
892 h2 = secondBranch = sys.argv[nextArg + 2]
897 print 'Merging', h1, 'with', h2
900 h1 = runProgram(['git-rev-parse', '--verify', h1 + '^0']).rstrip()
901 h2 = runProgram(['git-rev-parse', '--verify', h2 + '^0']).rstrip()
903 graph = buildGraph([h1, h2])
905 [dummy, clean] = merge(graph.shaMap[h1], graph.shaMap[h2],
906 firstBranch, secondBranch, graph)
910 if isinstance(sys.exc_info()[1], SystemExit):
913 traceback.print_exc(None, sys.stderr)