blob: ff6f58a07c8f46563d34876a70449d79d527300c [file] [log] [blame]
#
# Copyright (C) 2005 Fredrik Kuivinen
#
import sys, re, os, traceback
from sets import Set
def die(*args):
printList(args, sys.stderr)
sys.exit(2)
def printList(list, file=sys.stdout):
for x in list:
file.write(str(x))
file.write(' ')
file.write('\n')
import subprocess
# Debugging machinery
# -------------------
DEBUG = 0
functionsToDebug = Set()
def addDebug(func):
if type(func) == str:
functionsToDebug.add(func)
else:
functionsToDebug.add(func.func_name)
def debug(*args):
if DEBUG:
funcName = traceback.extract_stack()[-2][2]
if funcName in functionsToDebug:
printList(args)
# Program execution
# -----------------
class ProgramError(Exception):
def __init__(self, progStr, error):
self.progStr = progStr
self.error = error
def __str__(self):
return self.progStr + ': ' + self.error
addDebug('runProgram')
def runProgram(prog, input=None, returnCode=False, env=None, pipeOutput=True):
debug('runProgram prog:', str(prog), 'input:', str(input))
if type(prog) is str:
progStr = prog
else:
progStr = ' '.join(prog)
try:
if pipeOutput:
stderr = subprocess.STDOUT
stdout = subprocess.PIPE
else:
stderr = None
stdout = None
pop = subprocess.Popen(prog,
shell = type(prog) is str,
stderr=stderr,
stdout=stdout,
stdin=subprocess.PIPE,
env=env)
except OSError, e:
debug('strerror:', e.strerror)
raise ProgramError(progStr, e.strerror)
if input != None:
pop.stdin.write(input)
pop.stdin.close()
if pipeOutput:
out = pop.stdout.read()
else:
out = ''
code = pop.wait()
if returnCode:
ret = [out, code]
else:
ret = out
if code != 0 and not returnCode:
debug('error output:', out)
debug('prog:', prog)
raise ProgramError(progStr, out)
# debug('output:', out.replace('\0', '\n'))
return ret
# Code for computing common ancestors
# -----------------------------------
currentId = 0
def getUniqueId():
global currentId
currentId += 1
return currentId
# The 'virtual' commit objects have SHAs which are integers
shaRE = re.compile('^[0-9a-f]{40}$')
def isSha(obj):
return (type(obj) is str and bool(shaRE.match(obj))) or \
(type(obj) is int and obj >= 1)
class Commit:
def __init__(self, sha, parents, tree=None):
self.parents = parents
self.firstLineMsg = None
self.children = []
if tree:
tree = tree.rstrip()
assert(isSha(tree))
self._tree = tree
if not sha:
self.sha = getUniqueId()
self.virtual = True
self.firstLineMsg = 'virtual commit'
assert(isSha(tree))
else:
self.virtual = False
self.sha = sha.rstrip()
assert(isSha(self.sha))
def tree(self):
self.getInfo()
assert(self._tree != None)
return self._tree
def shortInfo(self):
self.getInfo()
return str(self.sha) + ' ' + self.firstLineMsg
def __str__(self):
return self.shortInfo()
def getInfo(self):
if self.virtual or self.firstLineMsg != None:
return
else:
info = runProgram(['git-cat-file', 'commit', self.sha])
info = info.split('\n')
msg = False
for l in info:
if msg:
self.firstLineMsg = l
break
else:
if l.startswith('tree'):
self._tree = l[5:].rstrip()
elif l == '':
msg = True
class Graph:
def __init__(self):
self.commits = []
self.shaMap = {}
def addNode(self, node):
assert(isinstance(node, Commit))
self.shaMap[node.sha] = node
self.commits.append(node)
for p in node.parents:
p.children.append(node)
return node
def reachableNodes(self, n1, n2):
res = {}
def traverse(n):
res[n] = True
for p in n.parents:
traverse(p)
traverse(n1)
traverse(n2)
return res
def fixParents(self, node):
for x in range(0, len(node.parents)):
node.parents[x] = self.shaMap[node.parents[x]]
# addDebug('buildGraph')
def buildGraph(heads):
debug('buildGraph heads:', heads)
for h in heads:
assert(isSha(h))
g = Graph()
out = runProgram(['git-rev-list', '--parents'] + heads)
for l in out.split('\n'):
if l == '':
continue
shas = l.split(' ')
# This is a hack, we temporarily use the 'parents' attribute
# to contain a list of SHA1:s. They are later replaced by proper
# Commit objects.
c = Commit(shas[0], shas[1:])
g.commits.append(c)
g.shaMap[c.sha] = c
for c in g.commits:
g.fixParents(c)
for c in g.commits:
for p in c.parents:
p.children.append(c)
return g
# Write the empty tree to the object database and return its SHA1
def writeEmptyTree():
tmpIndex = os.environ.get('GIT_DIR', '.git') + '/merge-tmp-index'
def delTmpIndex():
try:
os.unlink(tmpIndex)
except OSError:
pass
delTmpIndex()
newEnv = os.environ.copy()
newEnv['GIT_INDEX_FILE'] = tmpIndex
res = runProgram(['git-write-tree'], env=newEnv).rstrip()
delTmpIndex()
return res
def addCommonRoot(graph):
roots = []
for c in graph.commits:
if len(c.parents) == 0:
roots.append(c)
superRoot = Commit(sha=None, parents=[], tree=writeEmptyTree())
graph.addNode(superRoot)
for r in roots:
r.parents = [superRoot]
superRoot.children = roots
return superRoot
def getCommonAncestors(graph, commit1, commit2):
'''Find the common ancestors for commit1 and commit2'''
assert(isinstance(commit1, Commit) and isinstance(commit2, Commit))
def traverse(start, set):
stack = [start]
while len(stack) > 0:
el = stack.pop()
set.add(el)
for p in el.parents:
if p not in set:
stack.append(p)
h1Set = Set()
h2Set = Set()
traverse(commit1, h1Set)
traverse(commit2, h2Set)
shared = h1Set.intersection(h2Set)
if len(shared) == 0:
shared = [addCommonRoot(graph)]
res = Set()
for s in shared:
if len([c for c in s.children if c in shared]) == 0:
res.add(s)
return list(res)