[PATCH] Fix assertion failure when merging common ancestors.
[git] / git-merge-fredrik.py
1 #!/usr/bin/python
2
3 import sys, math, random, os, re, signal, tempfile, stat, errno
4 from heapq import heappush, heappop
5 from sets import Set
6
7 sys.path.append('@@GIT_PYTHON_PATH@@')
8 from gitMergeCommon import *
9
10 alwaysWriteTree = False
11
12 # The actual merge code
13 # ---------------------
14
15 def merge(h1, h2, branch1Name, branch2Name, graph, callDepth=0):
16     '''Merge the commits h1 and h2, return the resulting virtual
17     commit object and a flag indicating the cleaness of the merge.'''
18     assert(isinstance(h1, Commit) and isinstance(h2, Commit))
19     assert(isinstance(graph, Graph))
20
21     def infoMsg(*args):
22         sys.stdout.write('  '*callDepth)
23         printList(args)
24     infoMsg('Merging:')
25     infoMsg(h1)
26     infoMsg(h2)
27     sys.stdout.flush()
28
29     ca = getCommonAncestors(graph, h1, h2)
30     infoMsg('found', len(ca), 'common ancestor(s):')
31     for x in ca:
32         infoMsg(x)
33     sys.stdout.flush()
34
35     Ms = ca[0]
36     for h in ca[1:]:
37         [Ms, ignore] = merge(Ms, h,
38                              'Temporary shared merge branch 1',
39                              'Temporary shared merge branch 2',
40                              graph, callDepth+1)
41         assert(isinstance(Ms, Commit))
42
43     if callDepth == 0:
44         if len(ca) > 1:
45             runProgram(['git-read-tree', h1.tree()])
46             runProgram(['git-update-cache', '-q', '--refresh'])
47         # Use the original index if we only have one common ancestor
48         
49         updateWd = True
50         if alwaysWriteTree:
51             cleanCache = True
52         else:
53             cleanCache = False
54     else:
55         runProgram(['git-read-tree', h1.tree()])
56         updateWd = False
57         cleanCache = True
58
59     [shaRes, clean] = mergeTrees(h1.tree(), h2.tree(), Ms.tree(),
60                                  branch1Name, branch2Name,
61                                  cleanCache, updateWd)
62
63     if clean or cleanCache:
64         res = Commit(None, [h1, h2], tree=shaRes)
65         graph.addNode(res)
66     else:
67         res = None
68
69     return [res, clean]
70
71 getFilesRE = re.compile('([0-9]+) ([a-z0-9]+) ([0-9a-f]{40})\t(.*)')
72 def getFilesAndDirs(tree):
73     files = Set()
74     dirs = Set()
75     out = runProgram(['git-ls-tree', '-r', '-z', tree])
76     for l in out.split('\0'):
77         m = getFilesRE.match(l)
78         if m:
79             if m.group(2) == 'tree':
80                 dirs.add(m.group(4))
81             elif m.group(2) == 'blob':
82                 files.add(m.group(4))
83
84     return [files, dirs]
85
86 class CacheEntry:
87     def __init__(self, path):
88         class Stage:
89             def __init__(self):
90                 self.sha1 = None
91                 self.mode = None
92         
93         self.stages = [Stage(), Stage(), Stage()]
94         self.path = path
95
96 unmergedRE = re.compile('^([0-9]+) ([0-9a-f]{40}) ([1-3])\t(.*)$')
97 def unmergedCacheEntries():
98     '''Create a dictionary mapping file names to CacheEntry
99     objects. The dictionary contains one entry for every path with a
100     non-zero stage entry.'''
101
102     lines = runProgram(['git-ls-files', '-z', '--unmerged']).split('\0')
103     lines.pop()
104
105     res = {}
106     for l in lines:
107         m = unmergedRE.match(l)
108         if m:
109             mode = int(m.group(1), 8)
110             sha1 = m.group(2)
111             stage = int(m.group(3)) - 1
112             path = m.group(4)
113
114             if res.has_key(path):
115                 e = res[path]
116             else:
117                 e = CacheEntry(path)
118                 res[path] = e
119                 
120             e.stages[stage].mode = mode
121             e.stages[stage].sha1 = sha1
122         else:
123             print 'Error: Merge program failed: Unexpected output from', \
124                   'git-ls-files:', l
125             sys.exit(2)
126     return res
127
128 def mergeTrees(head, merge, common, branch1Name, branch2Name,
129                cleanCache, updateWd):
130     '''Merge the trees 'head' and 'merge' with the common ancestor
131     'common'. The name of the head branch is 'branch1Name' and the name of
132     the merge branch is 'branch2Name'. Return a tuple (tree, cleanMerge)
133     where tree is the resulting tree and cleanMerge is True iff the
134     merge was clean.'''
135     
136     assert(isSha(head) and isSha(merge) and isSha(common))
137
138     if common == merge:
139         print 'Already uptodate!'
140         return [head, True]
141
142     if updateWd:
143         updateArg = '-u'
144     else:
145         updateArg = '-i'
146     runProgram(['git-read-tree', updateArg, '-m', common, head, merge])
147     cleanMerge = True
148
149     [tree, code] = runProgram('git-write-tree', returnCode=True)
150     tree = tree.rstrip()
151     if code != 0:
152         [files, dirs] = getFilesAndDirs(head)
153         [filesM, dirsM] = getFilesAndDirs(merge)
154         files.union_update(filesM)
155         dirs.union_update(dirsM)
156         
157         cleanMerge = True
158         entries = unmergedCacheEntries()
159         for name in entries:
160             if not processEntry(entries[name], branch1Name, branch2Name,
161                                 files, dirs, cleanCache, updateWd):
162                 cleanMerge = False
163                 
164         if cleanMerge or cleanCache:
165             tree = runProgram('git-write-tree').rstrip()
166         else:
167             tree = None
168     else:
169         cleanMerge = True
170
171     return [tree, cleanMerge]
172
173 def processEntry(entry, branch1Name, branch2Name, files, dirs,
174                  cleanCache, updateWd):
175     '''Merge one cache entry. 'files' is a Set with the files in both of
176     the heads that we are going to merge. 'dirs' contains the
177     corresponding data for directories. If 'cleanCache' is True no
178     non-zero stages will be left in the cache for the path
179     corresponding to the entry 'entry'.'''
180
181 # cleanCache == True  => Don't leave any non-stage 0 entries in the cache.
182 #               False => Leave unmerged entries
183
184 # updateWd  == True  => Update the working directory to correspond to the cache
185 #              False => Leave the working directory unchanged
186
187 # clean     == True  => non-conflict case
188 #              False => conflict case
189
190 # If cleanCache == False then the cache shouldn't be updated if clean == False
191
192     def updateFile(clean, sha, mode, path):
193         if cleanCache or (not cleanCache and clean):
194             runProgram(['git-update-cache', '--add', '--cacheinfo',
195                         '0%o' % mode, sha, path])
196
197         if updateWd:
198             prog = ['git-cat-file', 'blob', sha]
199             if stat.S_ISREG(mode):
200                 try:
201                     os.unlink(path)
202                 except OSError:
203                     pass
204                 if mode & 0100:
205                     mode = 0777
206                 else:
207                     mode = 0666
208                 fd = os.open(path, os.O_WRONLY | os.O_TRUNC | os.O_CREAT, mode)
209                 proc = subprocess.Popen(prog, stdout=fd)
210                 proc.wait()
211                 os.close(fd)
212             elif stat.S_ISLNK(mode):
213                 linkTarget = runProgram(prog)
214                 os.symlink(linkTarget, path)
215             else:
216                 assert(False)
217             runProgram(['git-update-cache', '--', path])
218
219     def removeFile(clean, path):
220         if cleanCache or (not cleanCache and clean):
221             runProgram(['git-update-cache', '--force-remove', '--', path])
222
223         if updateWd:
224             try:
225                 os.unlink(path)
226             except OSError, e:
227                 if e.errno != errno.ENOENT and e.errno != errno.EISDIR:
228                     raise
229
230     def uniquePath(path, branch):
231         newPath = path + '_' + branch
232         suffix = 0
233         while newPath in files or newPath in dirs:
234             suffix += 1
235             newPath = path + '_' + branch + '_' + str(suffix)
236         files.add(newPath)
237         return newPath
238
239     debug('processing', entry.path, 'clean cache:', cleanCache,
240           'wd:', updateWd)
241
242     cleanMerge = True
243
244     path = entry.path
245     oSha = entry.stages[0].sha1
246     oMode = entry.stages[0].mode
247     aSha = entry.stages[1].sha1
248     aMode = entry.stages[1].mode
249     bSha = entry.stages[2].sha1
250     bMode = entry.stages[2].mode
251
252     assert(oSha == None or isSha(oSha))
253     assert(aSha == None or isSha(aSha))
254     assert(bSha == None or isSha(bSha))
255
256     assert(oMode == None or type(oMode) is int)
257     assert(aMode == None or type(aMode) is int)
258     assert(bMode == None or type(bMode) is int)
259
260     if (oSha and (not aSha or not bSha)):
261     #
262     # Case A: Deleted in one
263     #
264         if (not aSha     and not bSha) or \
265            (aSha == oSha and not bSha) or \
266            (not aSha     and bSha == oSha):
267     # Deleted in both or deleted in one and unchanged in the other
268             if aSha:
269                 print 'Removing ' + path
270             removeFile(True, path)
271         else:
272     # Deleted in one and changed in the other
273             cleanMerge = False
274             if not aSha:
275                 print 'CONFLICT (del/mod): "' + path + '" deleted in', \
276                       branch1Name, 'and modified in', branch2Name, \
277                       '. Version', branch2Name, ' of "' + path + \
278                       '" left in tree'
279                 mode = bMode
280                 sha = bSha
281             else:
282                 print 'CONFLICT (mod/del): "' + path + '" deleted in', \
283                       branch2Name, 'and modified in', branch1Name + \
284                       '. Version', branch1Name, 'of "' + path + \
285                       '" left in tree'
286                 mode = aMode
287                 sha = aSha
288
289             updateFile(False, sha, mode, path)
290     
291     elif (not oSha and aSha     and not bSha) or \
292          (not oSha and not aSha and bSha):
293     #
294     # Case B: Added in one.
295     #
296         if aSha:
297             addBranch = branch1Name
298             otherBranch = branch2Name
299             mode = aMode
300             sha = aSha
301             conf = 'file/dir'
302         else:
303             addBranch = branch2Name
304             otherBranch = branch1Name
305             mode = bMode
306             sha = bSha
307             conf = 'dir/file'
308     
309         if path in dirs:
310             cleanMerge = False
311             newPath = uniquePath(path, addBranch)
312             print 'CONFLICT (' + conf + \
313                   '): There is a directory with name "' + path + '" in', \
314                   otherBranch + '. Adding "' + path + '" as "' + newPath + '"'
315
316             removeFile(False, path)
317             path = newPath
318         else:
319             print 'Adding "' + path + '"'
320
321         updateFile(True, sha, mode, path)
322     
323     elif not oSha and aSha and bSha:
324     #
325     # Case C: Added in both (check for same permissions).
326     #
327         if aSha == bSha:
328             if aMode != bMode:
329                 cleanMerge = False
330                 print 'CONFLICT: File "' + path + \
331                       '" added identically in both branches,'
332                 print 'CONFLICT: but permissions conflict', '0%o' % aMode, \
333                       '->', '0%o' % bMode
334                 print 'CONFLICT: adding with permission:', '0%o' % aMode
335
336                 updateFile(False, aSha, aMode, path)
337             else:
338                 # This case is handled by git-read-tree
339                 assert(False)
340         else:
341             cleanMerge = False
342             newPath1 = uniquePath(path, branch1Name)
343             newPath2 = uniquePath(path, branch2Name)
344             print 'CONFLICT (add/add): File "' + path + \
345                   '" added non-identically in both branches.', \
346                   'Adding "' + newPath1 + '" and "' + newPath2 + '" instead.'
347             removeFile(False, path)
348             updateFile(False, aSha, aMode, newPath1)
349             updateFile(False, bSha, bMode, newPath2)
350
351     elif oSha and aSha and bSha:
352     #
353     # case D: Modified in both, but differently.
354     #
355         print 'Auto-merging', path 
356         orig = runProgram(['git-unpack-file', oSha]).rstrip()
357         src1 = runProgram(['git-unpack-file', aSha]).rstrip()
358         src2 = runProgram(['git-unpack-file', bSha]).rstrip()
359         [out, ret] = runProgram(['merge',
360                                  '-L', branch1Name + '/' + path,
361                                  '-L', 'orig/' + path,
362                                  '-L', branch2Name + '/' + path,
363                                  src1, orig, src2], returnCode=True)
364
365         if aMode == oMode:
366             mode = bMode
367         else:
368             mode = aMode
369
370         sha = runProgram(['git-hash-object', '-t', 'blob', '-w',
371                           src1]).rstrip()
372
373         if ret != 0:
374             cleanMerge = False
375             print 'CONFLICT (content): Merge conflict in "' + path + '".'
376             updateFile(False, sha, mode, path)
377         else:
378             updateFile(True, sha, mode, path)
379
380         os.unlink(orig)
381         os.unlink(src1)
382         os.unlink(src2)
383     else:
384         print 'ERROR: Fatal merge failure.'
385         print "ERROR: Shouldn't happen"
386         sys.exit(2)
387
388     return cleanMerge
389
390 def usage():
391     print 'Usage:', sys.argv[0], ' <base>... -- <head> <remote>..'
392     sys.exit(2)
393
394 # main entry point as merge strategy module
395 # The first parameters up to -- are merge bases, and the rest are heads.
396 # This strategy module figures out merge bases itself, so we only
397 # get heads.
398
399 for nextArg in xrange(1, len(sys.argv)):
400     if sys.argv[nextArg] == '--':
401         if len(sys.argv) != nextArg + 3:
402             print 'Not handling anything other than two heads merge.'
403             sys.exit(2)
404         try:
405             h1 = firstBranch = sys.argv[nextArg + 1]
406             h2 = secondBranch = sys.argv[nextArg + 2]
407         except IndexError:
408             usage()
409         break
410
411 print 'Merging', h1, 'with', h2
412 h1 = runProgram(['git-rev-parse', '--verify', h1 + '^0']).rstrip()
413 h2 = runProgram(['git-rev-parse', '--verify', h2 + '^0']).rstrip()
414
415 graph = buildGraph([h1, h2])
416
417 [res, clean] = merge(graph.shaMap[h1], graph.shaMap[h2],
418                      firstBranch, secondBranch, graph)
419
420 print ''
421
422 if clean:
423     sys.exit(0)
424 else:
425     print 'Automatic merge failed, fix up by hand'
426     sys.exit(1)