Merge branch 'fixes'
[git] / 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 originalIndexFile = os.environ.get('GIT_INDEX_FILE',
11                                    os.environ.get('GIT_DIR', '.git') + '/index')
12 temporaryIndexFile = os.environ.get('GIT_DIR', '.git') + \
13                      '/merge-recursive-tmp-index'
14 def setupIndex(temporary):
15     try:
16         os.unlink(temporaryIndexFile)
17     except OSError:
18         pass
19     if temporary:
20         newIndex = temporaryIndexFile
21     else:
22         newIndex = originalIndexFile
23     os.environ['GIT_INDEX_FILE'] = newIndex
24
25 # This is a global variable which is used in a number of places but
26 # only written to in the 'merge' function.
27
28 # cacheOnly == True  => Don't leave any non-stage 0 entries in the cache and
29 #                       don't update the working directory.
30 #              False => Leave unmerged entries in the cache and update
31 #                       the working directory.
32
33 cacheOnly = False
34
35 # The entry point to the merge code
36 # ---------------------------------
37
38 def merge(h1, h2, branch1Name, branch2Name, graph, callDepth=0):
39     '''Merge the commits h1 and h2, return the resulting virtual
40     commit object and a flag indicating the cleaness of the merge.'''
41     assert(isinstance(h1, Commit) and isinstance(h2, Commit))
42     assert(isinstance(graph, Graph))
43
44     def infoMsg(*args):
45         sys.stdout.write('  '*callDepth)
46         printList(args)
47
48     infoMsg('Merging:')
49     infoMsg(h1)
50     infoMsg(h2)
51     sys.stdout.flush()
52
53     ca = getCommonAncestors(graph, h1, h2)
54     infoMsg('found', len(ca), 'common ancestor(s):')
55     for x in ca:
56         infoMsg(x)
57     sys.stdout.flush()
58
59     mergedCA = ca[0]
60     for h in ca[1:]:
61         [mergedCA, dummy] = merge(mergedCA, h,
62                                   'Temporary shared merge branch 1',
63                                   'Temporary shared merge branch 2',
64                                   graph, callDepth+1)
65         assert(isinstance(mergedCA, Commit))
66
67     global cacheOnly
68     if callDepth == 0:
69         setupIndex(False)
70         cacheOnly = False
71     else:
72         setupIndex(True)
73         runProgram(['git-read-tree', h1.tree()])
74         cacheOnly = True
75
76     [shaRes, clean] = mergeTrees(h1.tree(), h2.tree(), mergedCA.tree(),
77                                  branch1Name, branch2Name)
78
79     if clean or cacheOnly:
80         res = Commit(None, [h1, h2], tree=shaRes)
81         graph.addNode(res)
82     else:
83         res = None
84
85     return [res, clean]
86
87 getFilesRE = re.compile(r'^([0-7]+) (\S+) ([0-9a-f]{40})\t(.*)$', re.S)
88 def getFilesAndDirs(tree):
89     files = Set()
90     dirs = Set()
91     out = runProgram(['git-ls-tree', '-r', '-z', tree])
92     for l in out.split('\0'):
93         m = getFilesRE.match(l)
94         if m:
95             if m.group(2) == 'tree':
96                 dirs.add(m.group(4))
97             elif m.group(2) == 'blob':
98                 files.add(m.group(4))
99
100     return [files, dirs]
101
102 # Those two global variables are used in a number of places but only
103 # written to in 'mergeTrees' and 'uniquePath'. They keep track of
104 # every file and directory in the two branches that are about to be
105 # merged.
106 currentFileSet = None
107 currentDirectorySet = None
108
109 def mergeTrees(head, merge, common, branch1Name, branch2Name):
110     '''Merge the trees 'head' and 'merge' with the common ancestor
111     'common'. The name of the head branch is 'branch1Name' and the name of
112     the merge branch is 'branch2Name'. Return a tuple (tree, cleanMerge)
113     where tree is the resulting tree and cleanMerge is True iff the
114     merge was clean.'''
115     
116     assert(isSha(head) and isSha(merge) and isSha(common))
117
118     if common == merge:
119         print 'Already uptodate!'
120         return [head, True]
121
122     if cacheOnly:
123         updateArg = '-i'
124     else:
125         updateArg = '-u'
126
127     [out, code] = runProgram(['git-read-tree', updateArg, '-m',
128                                 common, head, merge], returnCode = True)
129     if code != 0:
130         die('git-read-tree:', out)
131
132     [tree, code] = runProgram('git-write-tree', returnCode=True)
133     tree = tree.rstrip()
134     if code != 0:
135         global currentFileSet, currentDirectorySet
136         [currentFileSet, currentDirectorySet] = getFilesAndDirs(head)
137         [filesM, dirsM] = getFilesAndDirs(merge)
138         currentFileSet.union_update(filesM)
139         currentDirectorySet.union_update(dirsM)
140
141         entries = unmergedCacheEntries()
142         renamesHead =  getRenames(head, common, head, merge, entries)
143         renamesMerge = getRenames(merge, common, head, merge, entries)
144
145         cleanMerge = processRenames(renamesHead, renamesMerge,
146                                     branch1Name, branch2Name)
147         for entry in entries:
148             if entry.processed:
149                 continue
150             if not processEntry(entry, branch1Name, branch2Name):
151                 cleanMerge = False
152                 
153         if cleanMerge or cacheOnly:
154             tree = runProgram('git-write-tree').rstrip()
155         else:
156             tree = None
157     else:
158         cleanMerge = True
159
160     return [tree, cleanMerge]
161
162 # Low level file merging, update and removal
163 # ------------------------------------------
164
165 def mergeFile(oPath, oSha, oMode, aPath, aSha, aMode, bPath, bSha, bMode,
166               branch1Name, branch2Name):
167
168     merge = False
169     clean = True
170
171     if stat.S_IFMT(aMode) != stat.S_IFMT(bMode):
172         clean = False
173         if stat.S_ISREG(aMode):
174             mode = aMode
175             sha = aSha
176         else:
177             mode = bMode
178             sha = bSha
179     else:
180         if aSha != oSha and bSha != oSha:
181             merge = True
182
183         if aMode == oMode:
184             mode = bMode
185         else:
186             mode = aMode
187
188         if aSha == oSha:
189             sha = bSha
190         elif bSha == oSha:
191             sha = aSha
192         elif stat.S_ISREG(aMode):
193             assert(stat.S_ISREG(bMode))
194
195             orig = runProgram(['git-unpack-file', oSha]).rstrip()
196             src1 = runProgram(['git-unpack-file', aSha]).rstrip()
197             src2 = runProgram(['git-unpack-file', bSha]).rstrip()
198             [out, code] = runProgram(['merge',
199                                       '-L', branch1Name + '/' + aPath,
200                                       '-L', 'orig/' + oPath,
201                                       '-L', branch2Name + '/' + bPath,
202                                       src1, orig, src2], returnCode=True)
203
204             sha = runProgram(['git-hash-object', '-t', 'blob', '-w',
205                               src1]).rstrip()
206
207             os.unlink(orig)
208             os.unlink(src1)
209             os.unlink(src2)
210             
211             clean = (code == 0)
212         else:
213             assert(stat.S_ISLNK(aMode) and stat.S_ISLNK(bMode))
214             sha = aSha
215
216             if aSha != bSha:
217                 clean = False
218
219     return [sha, mode, clean, merge]
220
221 def updateFile(clean, sha, mode, path):
222     updateCache = cacheOnly or clean
223     updateWd = not cacheOnly
224
225     return updateFileExt(sha, mode, path, updateCache, updateWd)
226
227 def updateFileExt(sha, mode, path, updateCache, updateWd):
228     if cacheOnly:
229         updateWd = False
230
231     if updateWd:
232         pathComponents = path.split('/')
233         for x in xrange(1, len(pathComponents)):
234             p = '/'.join(pathComponents[0:x])
235
236             try:
237                 createDir = not stat.S_ISDIR(os.lstat(p).st_mode)
238             except: 
239                 createDir = True
240             
241             if createDir:
242                 try:
243                     os.mkdir(p)
244                 except OSError, e:
245                     die("Couldn't create directory", p, e.strerror)
246
247         prog = ['git-cat-file', 'blob', sha]
248         if stat.S_ISREG(mode):
249             try:
250                 os.unlink(path)
251             except OSError:
252                 pass
253             if mode & 0100:
254                 mode = 0777
255             else:
256                 mode = 0666
257             fd = os.open(path, os.O_WRONLY | os.O_TRUNC | os.O_CREAT, mode)
258             proc = subprocess.Popen(prog, stdout=fd)
259             proc.wait()
260             os.close(fd)
261         elif stat.S_ISLNK(mode):
262             linkTarget = runProgram(prog)
263             os.symlink(linkTarget, path)
264         else:
265             assert(False)
266
267     if updateWd and updateCache:
268         runProgram(['git-update-index', '--add', '--', path])
269     elif updateCache:
270         runProgram(['git-update-index', '--add', '--cacheinfo',
271                     '0%o' % mode, sha, path])
272
273 def removeFile(clean, path):
274     updateCache = cacheOnly or clean
275     updateWd = not cacheOnly
276
277     if updateCache:
278         runProgram(['git-update-index', '--force-remove', '--', path])
279
280     if updateWd:
281         try:
282             os.unlink(path)
283         except OSError, e:
284             if e.errno != errno.ENOENT and e.errno != errno.EISDIR:
285                 raise
286
287 def uniquePath(path, branch):
288     def fileExists(path):
289         try:
290             os.lstat(path)
291             return True
292         except OSError, e:
293             if e.errno == errno.ENOENT:
294                 return False
295             else:
296                 raise
297
298     newPath = path + '_' + branch
299     suffix = 0
300     while newPath in currentFileSet or \
301           newPath in currentDirectorySet  or \
302           fileExists(newPath):
303         suffix += 1
304         newPath = path + '_' + branch + '_' + str(suffix)
305     currentFileSet.add(newPath)
306     return newPath
307
308 # Cache entry management
309 # ----------------------
310
311 class CacheEntry:
312     def __init__(self, path):
313         class Stage:
314             def __init__(self):
315                 self.sha1 = None
316                 self.mode = None
317
318             # Used for debugging only
319             def __str__(self):
320                 if self.mode != None:
321                     m = '0%o' % self.mode
322                 else:
323                     m = 'None'
324
325                 if self.sha1:
326                     sha1 = self.sha1
327                 else:
328                     sha1 = 'None'
329                 return 'sha1: ' + sha1 + ' mode: ' + m
330         
331         self.stages = [Stage(), Stage(), Stage(), Stage()]
332         self.path = path
333         self.processed = False
334
335     def __str__(self):
336         return 'path: ' + self.path + ' stages: ' + repr([str(x) for x in self.stages])
337
338 class CacheEntryContainer:
339     def __init__(self):
340         self.entries = {}
341
342     def add(self, entry):
343         self.entries[entry.path] = entry
344
345     def get(self, path):
346         return self.entries.get(path)
347
348     def __iter__(self):
349         return self.entries.itervalues()
350     
351 unmergedRE = re.compile(r'^([0-7]+) ([0-9a-f]{40}) ([1-3])\t(.*)$', re.S)
352 def unmergedCacheEntries():
353     '''Create a dictionary mapping file names to CacheEntry
354     objects. The dictionary contains one entry for every path with a
355     non-zero stage entry.'''
356
357     lines = runProgram(['git-ls-files', '-z', '--unmerged']).split('\0')
358     lines.pop()
359
360     res = CacheEntryContainer()
361     for l in lines:
362         m = unmergedRE.match(l)
363         if m:
364             mode = int(m.group(1), 8)
365             sha1 = m.group(2)
366             stage = int(m.group(3))
367             path = m.group(4)
368
369             e = res.get(path)
370             if not e:
371                 e = CacheEntry(path)
372                 res.add(e)
373
374             e.stages[stage].mode = mode
375             e.stages[stage].sha1 = sha1
376         else:
377             die('Error: Merge program failed: Unexpected output from',
378                 'git-ls-files:', l)
379     return res
380
381 lsTreeRE = re.compile(r'^([0-7]+) (\S+) ([0-9a-f]{40})\t(.*)\n$', re.S)
382 def getCacheEntry(path, origTree, aTree, bTree):
383     '''Returns a CacheEntry object which doesn't have to correspond to
384     a real cache entry in Git's index.'''
385     
386     def parse(out):
387         if out == '':
388             return [None, None]
389         else:
390             m = lsTreeRE.match(out)
391             if not m:
392                 die('Unexpected output from git-ls-tree:', out)
393             elif m.group(2) == 'blob':
394                 return [m.group(3), int(m.group(1), 8)]
395             else:
396                 return [None, None]
397
398     res = CacheEntry(path)
399
400     [oSha, oMode] = parse(runProgram(['git-ls-tree', origTree, '--', path]))
401     [aSha, aMode] = parse(runProgram(['git-ls-tree', aTree, '--', path]))
402     [bSha, bMode] = parse(runProgram(['git-ls-tree', bTree, '--', path]))
403
404     res.stages[1].sha1 = oSha
405     res.stages[1].mode = oMode
406     res.stages[2].sha1 = aSha
407     res.stages[2].mode = aMode
408     res.stages[3].sha1 = bSha
409     res.stages[3].mode = bMode
410
411     return res
412
413 # Rename detection and handling
414 # -----------------------------
415
416 class RenameEntry:
417     def __init__(self,
418                  src, srcSha, srcMode, srcCacheEntry,
419                  dst, dstSha, dstMode, dstCacheEntry,
420                  score):
421         self.srcName = src
422         self.srcSha = srcSha
423         self.srcMode = srcMode
424         self.srcCacheEntry = srcCacheEntry
425         self.dstName = dst
426         self.dstSha = dstSha
427         self.dstMode = dstMode
428         self.dstCacheEntry = dstCacheEntry
429         self.score = score
430
431         self.processed = False
432
433 class RenameEntryContainer:
434     def __init__(self):
435         self.entriesSrc = {}
436         self.entriesDst = {}
437
438     def add(self, entry):
439         self.entriesSrc[entry.srcName] = entry
440         self.entriesDst[entry.dstName] = entry
441
442     def getSrc(self, path):
443         return self.entriesSrc.get(path)
444
445     def getDst(self, path):
446         return self.entriesDst.get(path)
447
448     def __iter__(self):
449         return self.entriesSrc.itervalues()
450
451 parseDiffRenamesRE = re.compile('^:([0-7]+) ([0-7]+) ([0-9a-f]{40}) ([0-9a-f]{40}) R([0-9]*)$')
452 def getRenames(tree, oTree, aTree, bTree, cacheEntries):
453     '''Get information of all renames which occured between 'oTree' and
454     'tree'. We need the three trees in the merge ('oTree', 'aTree' and
455     'bTree') to be able to associate the correct cache entries with
456     the rename information. 'tree' is always equal to either aTree or bTree.'''
457
458     assert(tree == aTree or tree == bTree)
459     inp = runProgram(['git-diff-tree', '-M', '--diff-filter=R', '-r',
460                       '-z', oTree, tree])
461
462     ret = RenameEntryContainer()
463     try:
464         recs = inp.split("\0")
465         recs.pop() # remove last entry (which is '')
466         it = recs.__iter__()
467         while True:
468             rec = it.next()
469             m = parseDiffRenamesRE.match(rec)
470
471             if not m:
472                 die('Unexpected output from git-diff-tree:', rec)
473
474             srcMode = int(m.group(1), 8)
475             dstMode = int(m.group(2), 8)
476             srcSha = m.group(3)
477             dstSha = m.group(4)
478             score = m.group(5)
479             src = it.next()
480             dst = it.next()
481
482             srcCacheEntry = cacheEntries.get(src)
483             if not srcCacheEntry:
484                 srcCacheEntry = getCacheEntry(src, oTree, aTree, bTree)
485                 cacheEntries.add(srcCacheEntry)
486
487             dstCacheEntry = cacheEntries.get(dst)
488             if not dstCacheEntry:
489                 dstCacheEntry = getCacheEntry(dst, oTree, aTree, bTree)
490                 cacheEntries.add(dstCacheEntry)
491
492             ret.add(RenameEntry(src, srcSha, srcMode, srcCacheEntry,
493                                 dst, dstSha, dstMode, dstCacheEntry,
494                                 score))
495     except StopIteration:
496         pass
497     return ret
498
499 def fmtRename(src, dst):
500     srcPath = src.split('/')
501     dstPath = dst.split('/')
502     path = []
503     endIndex = min(len(srcPath), len(dstPath)) - 1
504     for x in range(0, endIndex):
505         if srcPath[x] == dstPath[x]:
506             path.append(srcPath[x])
507         else:
508             endIndex = x
509             break
510
511     if len(path) > 0:
512         return '/'.join(path) + \
513                '/{' + '/'.join(srcPath[endIndex:]) + ' => ' + \
514                '/'.join(dstPath[endIndex:]) + '}'
515     else:
516         return src + ' => ' + dst
517
518 def processRenames(renamesA, renamesB, branchNameA, branchNameB):
519     srcNames = Set()
520     for x in renamesA:
521         srcNames.add(x.srcName)
522     for x in renamesB:
523         srcNames.add(x.srcName)
524
525     cleanMerge = True
526     for path in srcNames:
527         if renamesA.getSrc(path):
528             renames1 = renamesA
529             renames2 = renamesB
530             branchName1 = branchNameA
531             branchName2 = branchNameB
532         else:
533             renames1 = renamesB
534             renames2 = renamesA
535             branchName1 = branchNameB
536             branchName2 = branchNameA
537         
538         ren1 = renames1.getSrc(path)
539         ren2 = renames2.getSrc(path)
540
541         ren1.dstCacheEntry.processed = True
542         ren1.srcCacheEntry.processed = True
543
544         if ren1.processed:
545             continue
546
547         ren1.processed = True
548         removeFile(True, ren1.srcName)
549         if ren2:
550             # Renamed in 1 and renamed in 2
551             assert(ren1.srcName == ren2.srcName)
552             ren2.dstCacheEntry.processed = True
553             ren2.processed = True
554
555             if ren1.dstName != ren2.dstName:
556                 print 'CONFLICT (rename/rename): Rename', \
557                       fmtRename(path, ren1.dstName), 'in branch', branchName1, \
558                       'rename', fmtRename(path, ren2.dstName), 'in', branchName2
559                 cleanMerge = False
560
561                 if ren1.dstName in currentDirectorySet:
562                     dstName1 = uniquePath(ren1.dstName, branchName1)
563                     print ren1.dstName, 'is a directory in', branchName2, \
564                           'adding as', dstName1, 'instead.'
565                     removeFile(False, ren1.dstName)
566                 else:
567                     dstName1 = ren1.dstName
568
569                 if ren2.dstName in currentDirectorySet:
570                     dstName2 = uniquePath(ren2.dstName, branchName2)
571                     print ren2.dstName, 'is a directory in', branchName1, \
572                           'adding as', dstName2, 'instead.'
573                     removeFile(False, ren2.dstName)
574                 else:
575                     dstName2 = ren1.dstName
576
577                 updateFile(False, ren1.dstSha, ren1.dstMode, dstName1)
578                 updateFile(False, ren2.dstSha, ren2.dstMode, dstName2)
579             else:
580                 print 'Renaming', fmtRename(path, ren1.dstName)
581                 [resSha, resMode, clean, merge] = \
582                          mergeFile(ren1.srcName, ren1.srcSha, ren1.srcMode,
583                                    ren1.dstName, ren1.dstSha, ren1.dstMode,
584                                    ren2.dstName, ren2.dstSha, ren2.dstMode,
585                                    branchName1, branchName2)
586
587                 if merge:
588                     print 'Auto-merging', ren1.dstName
589
590                 if not clean:
591                     print 'CONFLICT (content): merge conflict in', ren1.dstName
592                     cleanMerge = False
593
594                     if not cacheOnly:
595                         updateFileExt(ren1.dstSha, ren1.dstMode, ren1.dstName,
596                                       updateCache=True, updateWd=False)
597                 updateFile(clean, resSha, resMode, ren1.dstName)
598         else:
599             # Renamed in 1, maybe changed in 2
600             if renamesA == renames1:
601                 stage = 3
602             else:
603                 stage = 2
604                 
605             srcShaOtherBranch  = ren1.srcCacheEntry.stages[stage].sha1
606             srcModeOtherBranch = ren1.srcCacheEntry.stages[stage].mode
607
608             dstShaOtherBranch  = ren1.dstCacheEntry.stages[stage].sha1
609             dstModeOtherBranch = ren1.dstCacheEntry.stages[stage].mode
610
611             tryMerge = False
612             
613             if ren1.dstName in currentDirectorySet:
614                 newPath = uniquePath(ren1.dstName, branchName1)
615                 print 'CONFLICT (rename/directory): Rename', \
616                       fmtRename(ren1.srcName, ren1.dstName), 'in', branchName1,\
617                       'directory', ren1.dstName, 'added in', branchName2
618                 print 'Renaming', ren1.srcName, 'to', newPath, 'instead'
619                 cleanMerge = False
620                 removeFile(False, ren1.dstName)
621                 updateFile(False, ren1.dstSha, ren1.dstMode, newPath)
622             elif srcShaOtherBranch == None:
623                 print 'CONFLICT (rename/delete): Rename', \
624                       fmtRename(ren1.srcName, ren1.dstName), 'in', \
625                       branchName1, 'and deleted in', branchName2
626                 cleanMerge = False
627                 updateFile(False, ren1.dstSha, ren1.dstMode, ren1.dstName)
628             elif dstShaOtherBranch:
629                 newPath = uniquePath(ren1.dstName, branchName2)
630                 print 'CONFLICT (rename/add): Rename', \
631                       fmtRename(ren1.srcName, ren1.dstName), 'in', \
632                       branchName1 + '.', ren1.dstName, 'added in', branchName2
633                 print 'Adding as', newPath, 'instead'
634                 updateFile(False, dstShaOtherBranch, dstModeOtherBranch, newPath)
635                 cleanMerge = False
636                 tryMerge = True
637             elif renames2.getDst(ren1.dstName):
638                 dst2 = renames2.getDst(ren1.dstName)
639                 newPath1 = uniquePath(ren1.dstName, branchName1)
640                 newPath2 = uniquePath(dst2.dstName, branchName2)
641                 print 'CONFLICT (rename/rename): Rename', \
642                       fmtRename(ren1.srcName, ren1.dstName), 'in', \
643                       branchName1+'. Rename', \
644                       fmtRename(dst2.srcName, dst2.dstName), 'in', branchName2
645                 print 'Renaming', ren1.srcName, 'to', newPath1, 'and', \
646                       dst2.srcName, 'to', newPath2, 'instead'
647                 removeFile(False, ren1.dstName)
648                 updateFile(False, ren1.dstSha, ren1.dstMode, newPath1)
649                 updateFile(False, dst2.dstSha, dst2.dstMode, newPath2)
650                 dst2.processed = True
651                 cleanMerge = False
652             else:
653                 tryMerge = True
654
655             if tryMerge:
656                 print 'Renaming', fmtRename(ren1.srcName, ren1.dstName)
657                 [resSha, resMode, clean, merge] = \
658                          mergeFile(ren1.srcName, ren1.srcSha, ren1.srcMode,
659                                    ren1.dstName, ren1.dstSha, ren1.dstMode,
660                                    ren1.srcName, srcShaOtherBranch, srcModeOtherBranch,
661                                    branchName1, branchName2)
662
663                 if merge:
664                     print 'Auto-merging', ren1.dstName
665
666                 if not clean:
667                     print 'CONFLICT (rename/modify): Merge conflict in', ren1.dstName
668                     cleanMerge = False
669
670                     if not cacheOnly:
671                         updateFileExt(ren1.dstSha, ren1.dstMode, ren1.dstName,
672                                       updateCache=True, updateWd=False)
673                 updateFile(clean, resSha, resMode, ren1.dstName)
674
675     return cleanMerge
676
677 # Per entry merge function
678 # ------------------------
679
680 def processEntry(entry, branch1Name, branch2Name):
681     '''Merge one cache entry.'''
682
683     debug('processing', entry.path, 'clean cache:', cacheOnly)
684
685     cleanMerge = True
686
687     path = entry.path
688     oSha = entry.stages[1].sha1
689     oMode = entry.stages[1].mode
690     aSha = entry.stages[2].sha1
691     aMode = entry.stages[2].mode
692     bSha = entry.stages[3].sha1
693     bMode = entry.stages[3].mode
694
695     assert(oSha == None or isSha(oSha))
696     assert(aSha == None or isSha(aSha))
697     assert(bSha == None or isSha(bSha))
698
699     assert(oMode == None or type(oMode) is int)
700     assert(aMode == None or type(aMode) is int)
701     assert(bMode == None or type(bMode) is int)
702
703     if (oSha and (not aSha or not bSha)):
704     #
705     # Case A: Deleted in one
706     #
707         if (not aSha     and not bSha) or \
708            (aSha == oSha and not bSha) or \
709            (not aSha     and bSha == oSha):
710     # Deleted in both or deleted in one and unchanged in the other
711             if aSha:
712                 print 'Removing', path
713             removeFile(True, path)
714         else:
715     # Deleted in one and changed in the other
716             cleanMerge = False
717             if not aSha:
718                 print 'CONFLICT (delete/modify):', path, 'deleted in', \
719                       branch1Name, 'and modified in', branch2Name + '.', \
720                       'Version', branch2Name, 'of', path, 'left in tree.'
721                 mode = bMode
722                 sha = bSha
723             else:
724                 print 'CONFLICT (modify/delete):', path, 'deleted in', \
725                       branch2Name, 'and modified in', branch1Name + '.', \
726                       'Version', branch1Name, 'of', path, 'left in tree.'
727                 mode = aMode
728                 sha = aSha
729
730             updateFile(False, sha, mode, path)
731
732     elif (not oSha and aSha     and not bSha) or \
733          (not oSha and not aSha and bSha):
734     #
735     # Case B: Added in one.
736     #
737         if aSha:
738             addBranch = branch1Name
739             otherBranch = branch2Name
740             mode = aMode
741             sha = aSha
742             conf = 'file/directory'
743         else:
744             addBranch = branch2Name
745             otherBranch = branch1Name
746             mode = bMode
747             sha = bSha
748             conf = 'directory/file'
749     
750         if path in currentDirectorySet:
751             cleanMerge = False
752             newPath = uniquePath(path, addBranch)
753             print 'CONFLICT (' + conf + '):', \
754                   'There is a directory with name', path, 'in', \
755                   otherBranch + '. Adding', path, 'as', newPath
756
757             removeFile(False, path)
758             updateFile(False, sha, mode, newPath)
759         else:
760             print 'Adding', path
761             updateFile(True, sha, mode, path)
762     
763     elif not oSha and aSha and bSha:
764     #
765     # Case C: Added in both (check for same permissions).
766     #
767         if aSha == bSha:
768             if aMode != bMode:
769                 cleanMerge = False
770                 print 'CONFLICT: File', path, \
771                       'added identically in both branches, but permissions', \
772                       'conflict', '0%o' % aMode, '->', '0%o' % bMode
773                 print 'CONFLICT: adding with permission:', '0%o' % aMode
774
775                 updateFile(False, aSha, aMode, path)
776             else:
777                 # This case is handled by git-read-tree
778                 assert(False)
779         else:
780             cleanMerge = False
781             newPath1 = uniquePath(path, branch1Name)
782             newPath2 = uniquePath(path, branch2Name)
783             print 'CONFLICT (add/add): File', path, \
784                   'added non-identically in both branches. Adding as', \
785                   newPath1, 'and', newPath2, 'instead.'
786             removeFile(False, path)
787             updateFile(False, aSha, aMode, newPath1)
788             updateFile(False, bSha, bMode, newPath2)
789
790     elif oSha and aSha and bSha:
791     #
792     # case D: Modified in both, but differently.
793     #
794         print 'Auto-merging', path
795         [sha, mode, clean, dummy] = \
796               mergeFile(path, oSha, oMode,
797                         path, aSha, aMode,
798                         path, bSha, bMode,
799                         branch1Name, branch2Name)
800         if clean:
801             updateFile(True, sha, mode, path)
802         else:
803             cleanMerge = False
804             print 'CONFLICT (content): Merge conflict in', path
805
806             if cacheOnly:
807                 updateFile(False, sha, mode, path)
808             else:
809                 updateFileExt(aSha, aMode, path,
810                               updateCache=True, updateWd=False)
811                 updateFileExt(sha, mode, path, updateCache=False, updateWd=True)
812     else:
813         die("ERROR: Fatal merge failure, shouldn't happen.")
814
815     return cleanMerge
816
817 def usage():
818     die('Usage:', sys.argv[0], ' <base>... -- <head> <remote>..')
819
820 # main entry point as merge strategy module
821 # The first parameters up to -- are merge bases, and the rest are heads.
822 # This strategy module figures out merge bases itself, so we only
823 # get heads.
824
825 if len(sys.argv) < 4:
826     usage()
827
828 for nextArg in xrange(1, len(sys.argv)):
829     if sys.argv[nextArg] == '--':
830         if len(sys.argv) != nextArg + 3:
831             die('Not handling anything other than two heads merge.')
832         try:
833             h1 = firstBranch = sys.argv[nextArg + 1]
834             h2 = secondBranch = sys.argv[nextArg + 2]
835         except IndexError:
836             usage()
837         break
838
839 print 'Merging', h1, 'with', h2
840
841 try:
842     h1 = runProgram(['git-rev-parse', '--verify', h1 + '^0']).rstrip()
843     h2 = runProgram(['git-rev-parse', '--verify', h2 + '^0']).rstrip()
844
845     graph = buildGraph([h1, h2])
846
847     [dummy, clean] = merge(graph.shaMap[h1], graph.shaMap[h2],
848                            firstBranch, secondBranch, graph)
849
850     print ''
851 except:
852     if isinstance(sys.exc_info()[1], SystemExit):
853         raise
854     else:
855         traceback.print_exc(None, sys.stderr)
856         sys.exit(2)
857
858 if clean:
859     sys.exit(0)
860 else:
861     sys.exit(1)