socklen_t is unsigned int on most Linux platforms
[git] / gitMergeCommon.py
1 import sys, re, os, traceback
2 from sets import Set
3
4 def die(*args):
5     printList(args, sys.stderr)
6     sys.exit(2)
7
8 def printList(list, file=sys.stdout):
9     for x in list:
10         file.write(str(x))
11         file.write(' ')
12     file.write('\n')
13
14 import subprocess
15
16 # Debugging machinery
17 # -------------------
18
19 DEBUG = 0
20 functionsToDebug = Set()
21
22 def addDebug(func):
23     if type(func) == str:
24         functionsToDebug.add(func)
25     else:
26         functionsToDebug.add(func.func_name)
27
28 def debug(*args):
29     if DEBUG:
30         funcName = traceback.extract_stack()[-2][2]
31         if funcName in functionsToDebug:
32             printList(args)
33
34 # Program execution
35 # -----------------
36
37 class ProgramError(Exception):
38     def __init__(self, progStr, error):
39         self.progStr = progStr
40         self.error = error
41
42     def __str__(self):
43         return self.progStr + ': ' + self.error
44
45 addDebug('runProgram')
46 def runProgram(prog, input=None, returnCode=False, env=None, pipeOutput=True):
47     debug('runProgram prog:', str(prog), 'input:', str(input))
48     if type(prog) is str:
49         progStr = prog
50     else:
51         progStr = ' '.join(prog)
52     
53     try:
54         if pipeOutput:
55             stderr = subprocess.STDOUT
56             stdout = subprocess.PIPE
57         else:
58             stderr = None
59             stdout = None
60         pop = subprocess.Popen(prog,
61                                shell = type(prog) is str,
62                                stderr=stderr,
63                                stdout=stdout,
64                                stdin=subprocess.PIPE,
65                                env=env)
66     except OSError, e:
67         debug('strerror:', e.strerror)
68         raise ProgramError(progStr, e.strerror)
69
70     if input != None:
71         pop.stdin.write(input)
72     pop.stdin.close()
73
74     if pipeOutput:
75         out = pop.stdout.read()
76     else:
77         out = ''
78
79     code = pop.wait()
80     if returnCode:
81         ret = [out, code]
82     else:
83         ret = out
84     if code != 0 and not returnCode:
85         debug('error output:', out)
86         debug('prog:', prog)
87         raise ProgramError(progStr, out)
88 #    debug('output:', out.replace('\0', '\n'))
89     return ret
90
91 # Code for computing common ancestors
92 # -----------------------------------
93
94 currentId = 0
95 def getUniqueId():
96     global currentId
97     currentId += 1
98     return currentId
99
100 # The 'virtual' commit objects have SHAs which are integers
101 shaRE = re.compile('^[0-9a-f]{40}$')
102 def isSha(obj):
103     return (type(obj) is str and bool(shaRE.match(obj))) or \
104            (type(obj) is int and obj >= 1)
105
106 class Commit:
107     def __init__(self, sha, parents, tree=None):
108         self.parents = parents
109         self.firstLineMsg = None
110         self.children = []
111
112         if tree:
113             tree = tree.rstrip()
114             assert(isSha(tree))
115         self._tree = tree
116
117         if not sha:
118             self.sha = getUniqueId()
119             self.virtual = True
120             self.firstLineMsg = 'virtual commit'
121             assert(isSha(tree))
122         else:
123             self.virtual = False
124             self.sha = sha.rstrip()
125         assert(isSha(self.sha))
126
127     def tree(self):
128         self.getInfo()
129         assert(self._tree != None)
130         return self._tree
131
132     def shortInfo(self):
133         self.getInfo()
134         return str(self.sha) + ' ' + self.firstLineMsg
135
136     def __str__(self):
137         return self.shortInfo()
138
139     def getInfo(self):
140         if self.virtual or self.firstLineMsg != None:
141             return
142         else:
143             info = runProgram(['git-cat-file', 'commit', self.sha])
144             info = info.split('\n')
145             msg = False
146             for l in info:
147                 if msg:
148                     self.firstLineMsg = l
149                     break
150                 else:
151                     if l.startswith('tree'):
152                         self._tree = l[5:].rstrip()
153                     elif l == '':
154                         msg = True
155
156 class Graph:
157     def __init__(self):
158         self.commits = []
159         self.shaMap = {}
160
161     def addNode(self, node):
162         assert(isinstance(node, Commit))
163         self.shaMap[node.sha] = node
164         self.commits.append(node)
165         for p in node.parents:
166             p.children.append(node)
167         return node
168
169     def reachableNodes(self, n1, n2):
170         res = {}
171         def traverse(n):
172             res[n] = True
173             for p in n.parents:
174                 traverse(p)
175
176         traverse(n1)
177         traverse(n2)
178         return res
179
180     def fixParents(self, node):
181         for x in range(0, len(node.parents)):
182             node.parents[x] = self.shaMap[node.parents[x]]
183
184 # addDebug('buildGraph')
185 def buildGraph(heads):
186     debug('buildGraph heads:', heads)
187     for h in heads:
188         assert(isSha(h))
189
190     g = Graph()
191
192     out = runProgram(['git-rev-list', '--parents'] + heads)
193     for l in out.split('\n'):
194         if l == '':
195             continue
196         shas = l.split(' ')
197
198         # This is a hack, we temporarily use the 'parents' attribute
199         # to contain a list of SHA1:s. They are later replaced by proper
200         # Commit objects.
201         c = Commit(shas[0], shas[1:])
202
203         g.commits.append(c)
204         g.shaMap[c.sha] = c
205
206     for c in g.commits:
207         g.fixParents(c)
208
209     for c in g.commits:
210         for p in c.parents:
211             p.children.append(c)
212     return g
213
214 # Write the empty tree to the object database and return its SHA1
215 def writeEmptyTree():
216     tmpIndex = os.environ['GIT_DIR'] + '/merge-tmp-index'
217     def delTmpIndex():
218         try:
219             os.unlink(tmpIndex)
220         except OSError:
221             pass
222     delTmpIndex()
223     newEnv = os.environ.copy()
224     newEnv['GIT_INDEX_FILE'] = tmpIndex
225     res = runProgram(['git-write-tree'], env=newEnv).rstrip()
226     delTmpIndex()
227     return res
228
229 def addCommonRoot(graph):
230     roots = []
231     for c in graph.commits:
232         if len(c.parents) == 0:
233             roots.append(c)
234
235     superRoot = Commit(sha=None, parents=[], tree=writeEmptyTree())
236     graph.addNode(superRoot)
237     for r in roots:
238         r.parents = [superRoot]
239     superRoot.children = roots
240     return superRoot
241
242 def getCommonAncestors(graph, commit1, commit2):
243     '''Find the common ancestors for commit1 and commit2'''
244     assert(isinstance(commit1, Commit) and isinstance(commit2, Commit))
245
246     def traverse(start, set):
247         stack = [start]
248         while len(stack) > 0:
249             el = stack.pop()
250             set.add(el)
251             for p in el.parents:
252                 if p not in set:
253                     stack.append(p)
254     h1Set = Set()
255     h2Set = Set()
256     traverse(commit1, h1Set)
257     traverse(commit2, h2Set)
258     shared = h1Set.intersection(h2Set)
259
260     if len(shared) == 0:
261         shared = [addCommonRoot(graph)]
262         
263     res = Set()
264
265     for s in shared:
266         if len([c for c in s.children if c in shared]) == 0:
267             res.add(s)
268     return list(res)