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