]>
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 | ||
110 | class Commit: | |
111 | def __init__(self, sha, parents, tree=None): | |
112 | self.parents = parents | |
113 | self.firstLineMsg = None | |
114 | self.children = [] | |
115 | ||
116 | if tree: | |
117 | tree = tree.rstrip() | |
118 | assert(isSha(tree)) | |
119 | self._tree = tree | |
120 | ||
121 | if not sha: | |
122 | self.sha = getUniqueId() | |
123 | self.virtual = True | |
124 | self.firstLineMsg = 'virtual commit' | |
125 | assert(isSha(tree)) | |
126 | else: | |
127 | self.virtual = False | |
128 | self.sha = sha.rstrip() | |
129 | assert(isSha(self.sha)) | |
130 | ||
131 | def tree(self): | |
132 | self.getInfo() | |
133 | assert(self._tree != None) | |
134 | return self._tree | |
135 | ||
136 | def shortInfo(self): | |
137 | self.getInfo() | |
138 | return str(self.sha) + ' ' + self.firstLineMsg | |
139 | ||
140 | def __str__(self): | |
141 | return self.shortInfo() | |
142 | ||
143 | def getInfo(self): | |
144 | if self.virtual or self.firstLineMsg != None: | |
145 | return | |
146 | else: | |
147 | info = runProgram(['git-cat-file', 'commit', self.sha]) | |
148 | info = info.split('\n') | |
149 | msg = False | |
150 | for l in info: | |
151 | if msg: | |
152 | self.firstLineMsg = l | |
153 | break | |
154 | else: | |
155 | if l.startswith('tree'): | |
156 | self._tree = l[5:].rstrip() | |
157 | elif l == '': | |
158 | msg = True | |
159 | ||
160 | class Graph: | |
161 | def __init__(self): | |
162 | self.commits = [] | |
163 | self.shaMap = {} | |
164 | ||
165 | def addNode(self, node): | |
166 | assert(isinstance(node, Commit)) | |
167 | self.shaMap[node.sha] = node | |
168 | self.commits.append(node) | |
169 | for p in node.parents: | |
170 | p.children.append(node) | |
171 | return node | |
172 | ||
173 | def reachableNodes(self, n1, n2): | |
174 | res = {} | |
175 | def traverse(n): | |
176 | res[n] = True | |
177 | for p in n.parents: | |
178 | traverse(p) | |
179 | ||
180 | traverse(n1) | |
181 | traverse(n2) | |
182 | return res | |
183 | ||
184 | def fixParents(self, node): | |
185 | for x in range(0, len(node.parents)): | |
186 | node.parents[x] = self.shaMap[node.parents[x]] | |
187 | ||
188 | # addDebug('buildGraph') | |
189 | def buildGraph(heads): | |
190 | debug('buildGraph heads:', heads) | |
191 | for h in heads: | |
192 | assert(isSha(h)) | |
193 | ||
194 | g = Graph() | |
195 | ||
196 | out = runProgram(['git-rev-list', '--parents'] + heads) | |
197 | for l in out.split('\n'): | |
198 | if l == '': | |
199 | continue | |
200 | shas = l.split(' ') | |
201 | ||
202 | # This is a hack, we temporarily use the 'parents' attribute | |
203 | # to contain a list of SHA1:s. They are later replaced by proper | |
204 | # Commit objects. | |
205 | c = Commit(shas[0], shas[1:]) | |
206 | ||
207 | g.commits.append(c) | |
208 | g.shaMap[c.sha] = c | |
209 | ||
210 | for c in g.commits: | |
211 | g.fixParents(c) | |
212 | ||
213 | for c in g.commits: | |
214 | for p in c.parents: | |
215 | p.children.append(c) | |
216 | return g | |
217 | ||
218 | # Write the empty tree to the object database and return its SHA1 | |
219 | def writeEmptyTree(): | |
88f8f0a5 | 220 | tmpIndex = os.environ.get('GIT_DIR', '.git') + '/merge-tmp-index' |
720d150c JH |
221 | def delTmpIndex(): |
222 | try: | |
223 | os.unlink(tmpIndex) | |
224 | except OSError: | |
225 | pass | |
226 | delTmpIndex() | |
227 | newEnv = os.environ.copy() | |
228 | newEnv['GIT_INDEX_FILE'] = tmpIndex | |
229 | res = runProgram(['git-write-tree'], env=newEnv).rstrip() | |
230 | delTmpIndex() | |
231 | return res | |
232 | ||
233 | def addCommonRoot(graph): | |
234 | roots = [] | |
235 | for c in graph.commits: | |
236 | if len(c.parents) == 0: | |
237 | roots.append(c) | |
238 | ||
239 | superRoot = Commit(sha=None, parents=[], tree=writeEmptyTree()) | |
240 | graph.addNode(superRoot) | |
241 | for r in roots: | |
242 | r.parents = [superRoot] | |
243 | superRoot.children = roots | |
244 | return superRoot | |
245 | ||
246 | def getCommonAncestors(graph, commit1, commit2): | |
247 | '''Find the common ancestors for commit1 and commit2''' | |
248 | assert(isinstance(commit1, Commit) and isinstance(commit2, Commit)) | |
249 | ||
250 | def traverse(start, set): | |
251 | stack = [start] | |
252 | while len(stack) > 0: | |
253 | el = stack.pop() | |
254 | set.add(el) | |
255 | for p in el.parents: | |
256 | if p not in set: | |
257 | stack.append(p) | |
258 | h1Set = Set() | |
259 | h2Set = Set() | |
260 | traverse(commit1, h1Set) | |
261 | traverse(commit2, h2Set) | |
262 | shared = h1Set.intersection(h2Set) | |
263 | ||
264 | if len(shared) == 0: | |
265 | shared = [addCommonRoot(graph)] | |
266 | ||
267 | res = Set() | |
268 | ||
269 | for s in shared: | |
270 | if len([c for c in s.children if c in shared]) == 0: | |
271 | res.add(s) | |
272 | return list(res) |