]>
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 | 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 | ||
720d150c JH |
34 | # Program execution |
35 | # ----------------- | |
36 | ||
37 | class ProgramError(Exception): | |
38 | def __init__(self, progStr, error): | |
39 | self.progStr = progStr | |
40 | self.error = error | |
41 | ||
4e48fe3f FK |
42 | def __str__(self): |
43 | return self.progStr + ': ' + self.error | |
44 | ||
720d150c JH |
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(): | |
88f8f0a5 | 216 | tmpIndex = os.environ.get('GIT_DIR', '.git') + '/merge-tmp-index' |
720d150c JH |
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) |