Add a new merge strategy by Fredrik Kuivinen.
[git/git.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 alwaysWriteTree:
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)