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