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