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