2
# Copyright (C) 2005 Fredrik Kuivinen
5
import sys, re, os, traceback
9
printList(args, sys.stderr)
12
def printList(list, file=sys.stdout):
24
functionsToDebug = Set()
28
functionsToDebug.add(func)
30
functionsToDebug.add(func.func_name)
34
funcName = traceback.extract_stack()[-2][2]
35
if funcName in functionsToDebug:
41
class ProgramError(Exception):
42
def __init__(self, progStr, error):
43
self.progStr = progStr
47
return self.progStr + ': ' + self.error
49
addDebug('runProgram')
50
def runProgram(prog, input=None, returnCode=False, env=None, pipeOutput=True):
51
debug('runProgram prog:', str(prog), 'input:', str(input))
55
progStr = ' '.join(prog)
59
stderr = subprocess.STDOUT
60
stdout = subprocess.PIPE
64
pop = subprocess.Popen(prog,
65
shell = type(prog) is str,
68
stdin=subprocess.PIPE,
71
debug('strerror:', e.strerror)
72
raise ProgramError(progStr, e.strerror)
75
pop.stdin.write(input)
79
out = pop.stdout.read()
88
if code != 0 and not returnCode:
89
debug('error output:', out)
91
raise ProgramError(progStr, out)
92
# debug('output:', out.replace('\0', '\n'))
95
# Code for computing common ancestors
96
# -----------------------------------
104
# The 'virtual' commit objects have SHAs which are integers
105
shaRE = re.compile('^[0-9a-f]{40}$')
107
return (type(obj) is str and bool(shaRE.match(obj))) or \
108
(type(obj) is int and obj >= 1)
110
class Commit(object):
111
__slots__ = ['parents', 'firstLineMsg', 'children', '_tree', 'sha',
114
def __init__(self, sha, parents, tree=None):
115
self.parents = parents
116
self.firstLineMsg = None
125
self.sha = getUniqueId()
127
self.firstLineMsg = 'virtual commit'
131
self.sha = sha.rstrip()
132
assert(isSha(self.sha))
136
assert(self._tree != None)
141
return str(self.sha) + ' ' + self.firstLineMsg
144
return self.shortInfo()
147
if self.virtual or self.firstLineMsg != None:
150
info = runProgram(['git-cat-file', 'commit', self.sha])
151
info = info.split('\n')
155
self.firstLineMsg = l
158
if l.startswith('tree'):
159
self._tree = l[5:].rstrip()
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)
176
def reachableNodes(self, n1, n2):
187
def fixParents(self, node):
188
for x in range(0, len(node.parents)):
189
node.parents[x] = self.shaMap[node.parents[x]]
191
# addDebug('buildGraph')
192
def buildGraph(heads):
193
debug('buildGraph heads:', heads)
199
out = runProgram(['git-rev-list', '--parents'] + heads)
200
for l in out.split('\n'):
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
208
c = Commit(shas[0], shas[1:])
221
# Write the empty tree to the object database and return its SHA1
222
def writeEmptyTree():
223
tmpIndex = os.environ.get('GIT_DIR', '.git') + '/merge-tmp-index'
230
newEnv = os.environ.copy()
231
newEnv['GIT_INDEX_FILE'] = tmpIndex
232
res = runProgram(['git-write-tree'], env=newEnv).rstrip()
236
def addCommonRoot(graph):
238
for c in graph.commits:
239
if len(c.parents) == 0:
242
superRoot = Commit(sha=None, parents=[], tree=writeEmptyTree())
243
graph.addNode(superRoot)
245
r.parents = [superRoot]
246
superRoot.children = roots
249
def getCommonAncestors(graph, commit1, commit2):
250
'''Find the common ancestors for commit1 and commit2'''
251
assert(isinstance(commit1, Commit) and isinstance(commit2, Commit))
253
def traverse(start, set):
255
while len(stack) > 0:
263
traverse(commit1, h1Set)
264
traverse(commit2, h2Set)
265
shared = h1Set.intersection(h2Set)
268
shared = [addCommonRoot(graph)]
273
if len([c for c in s.children if c in shared]) == 0: