Andrew's git - gitweb.git/blob

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