Staging
v0.5.1
v0.5.1
buildtree.py
# buildtree.py - the graph algorithm inherited from gitk
#
# Copyright (C) 2007 Logilab. All rights reserved.
# Copyright (C) 2005 Tristan Wibberley <tristan at wibberley.com>. All rights reserved.
# Copyright (C) 2005 Paul Mackerras. All rights reserved.
#
# This software may be used and distributed according to the terms
# of the GNU General Public License, incorporated herein by reference.
# This was translated by Tristan from tcl/tk (gitk) to python
# and then reworked and pruned
# I got it from : http://www.selenic.com/pipermail/mercurial/2005-August/003585.html
from mercurial import hg, ui
from mercurial.node import hex as binhex
from itertools import *
nullid = "\x00"*20
def parents_of(repo, node):
return [ p for p in repo.changelog.parents(node) if p != nullid ]
# TODO : make it work with a partial set of nodes ?
COLORS = [ "blue", "darkgreen", "darkred", "green", "darkblue", "purple",
"cyan", "magenta" ]
class RevGraph(object):
def __init__(self, repo, nodes, allnodes):
self.repo = repo
self.nextcolor = 0
start = repo.heads()
# number of children left to do for a given node
ncleft = {}
# for a given node
self.x = {}
# mapping of node to row
self.idrow = {}
# mapping of row to list of lines
self.rowlines = [ set() for i in xrange(len(allnodes)) ]
# initial depot when it is empty
if len(allnodes) == 0:
allnodes= [nullid]
# mapping of row to number of line
self.rownlines = [None]*len(allnodes)
self.rows = [None]*len(allnodes)
# calculate initial ncleft for each node
ncleft = dict( izip( nodes, repeat(0) ) )
ncleft[nullid] = 0
# build parent mapping
_parents = {}
for p in allnodes:
_parents[p] = _p = parents_of(repo, p)
if len(nodes) == len(allnodes):
todo = start[:] # None is a blank column
parents = _parents
else:
# this path is ... approximative at best
children = {}
parents = {}
todo = allnodes
_nodes = set(nodes)
while todo:
next = set()
for node in todo:
par = _parents[node]
npar = set()
for p in par:
if p not in _nodes:
npar.update( _parents[p] )
next.add( node )
else:
npar.add(p)
for p in set(npar):
for k in _parents[p]:
if k in npar:
npar.remove(p)
break
_parents[node] = npar
todo = next
for n in nodes:
par = _parents[n]
parents[n] = list(par)
for p in par:
children[p] = n
todo = []
for p in nodes:
if p not in children:
todo.append( p )
del children
for node in nodes:
ps = parents[node]
for p in ps:
ncleft[p] += 1
level = len(todo) - 1 # column of the node being worked with
# next column to be eradicate when it is determined that one should be
nullentry = -1
todo.reverse()
rowno = -1
linestarty = {}
self.datemode = False
self.todo = todo
self.colors = {}
self.rowno = rowno
self.level = level
self.parents = parents
self.ncleft = ncleft
self.nchildren = ncleft.copy()
self.linestarty = linestarty
self.nullentry = nullentry
self.done = False
#print "START", [binhex(n) for n in todo]
def assigncolor(self, p, color = None):
while len(self.parents[p]) == 1:
p = self.parents[p][0]
if self.nchildren[p] != 1:
break
if p in self.colors:
return p
if color is None:
n = self.nextcolor
color = COLORS[n]
n += 1
if n == len(COLORS):
n = 0
self.nextcolor = n
self.colors[p] = color
return p
def build(self, NMAX = 500 ):
datemode = self.datemode
todo = self.todo
rowno = self.rowno
level = self.level
parents = self.parents
ncleft = self.ncleft
linestarty = self.linestarty
nullentry = self.nullentry
rowmax = rowno + NMAX
# each node is treated only once
while todo:
if rowno == rowmax:
break
rowno += 1
self.rownlines[rowno] = len(todo)
id = todo[level]
self.idrow[id] = rowno
self.rows[rowno] = id
idcolor = self.assigncolor(id)
actualparents = parents[id]
# for each parent reduce the number of
# childs not handled by 1
for p in actualparents:
ncleft[p] -= 1
self.x[id] = level
level_linestart = linestarty.get( level, rowno )
# linestarty is top of line at each level
# and thus should always be <= rowno
assert level_linestart <= rowno
if level_linestart < rowno:
# add line from (x, linestarty[level]) to (x, rowno)
# XXX: shouldn't we have added the ones <rowno already ??
for r in xrange(level_linestart, rowno + 1 ):
self.rowlines[r].add( (idcolor, level,
level_linestart, level, rowno) )
linestarty[level] = rowno # starting a new line
# if only one parent and last child,
# replace with parent in todo
if (not datemode) and (len(actualparents) == 1):
p = actualparents[0]
if (ncleft[p] == 0) and (p not in todo):
todo[level] = p
continue
# otherwise obliterate a sensible gap choice
oldtodo = todo[:]
oldlevel = level
lines = []
oldstarty = {}
for i in xrange(self.rownlines[rowno]):
if todo[i] is None:
continue
if i in linestarty:
oldstarty[i] = linestarty[i]
del linestarty[i]
if i != level:
lines.append((i, todo[i]))
if nullentry >= 0:
del todo[nullentry]
if nullentry < level:
level -= 1
# delete the done id
del todo[level]
if nullentry > level:
nullentry -= 1
# and insert the parents
i = level
for p in actualparents:
if p not in todo:
todo.insert(i, p)
if nullentry >= i:
nullentry += 1
i += 1
lines.append((oldlevel, p))
# then choose a new level
todol = len(todo)
level = -1
latest = None
for k in xrange(todol -1, -1, -1):
p = todo[k]
if p is None:
continue
if ncleft[p] == 0:
if datemode:
if (latest is None) or (cdate[p] > latest):
level = k
latest = cdate[p]
else:
level = k
break
if level < 0:
if todo != []:
print "ERROR: none of the pending commits can be done yet"
for p in todo:
print " " + binhex(p)
break
# if we are reducing, put in a null entry
if todol < self.rownlines[rowno]:
if nullentry >= 0:
i = nullentry
while (i < todol and oldtodo[i] == todo[i]):
i += 1
else:
i = oldlevel
if level >= i:
i += 1
if i >= todol:
nullentry = -1
else:
nullentry = i
todo.insert(nullentry, None)
if level >= i:
level += 1
else:
nullentry = -1
# j is x at the bottom of a horizontalish line
# i is x at the top of a horizontalish
for (i, dst) in lines:
j = todo.index(dst)
colordst = self.assigncolor( dst )
if i == j:
if i in oldstarty:
linestarty[i] = oldstarty[i]
continue
coords = []
if (i in oldstarty) and (oldstarty[i] < rowno):
coords.append((i, oldstarty[i]))
coords.append((i, rowno))
if j < i - 1:
coords.append((j + 1, rowno))
elif j > i + 1:
coords.append((j - 1, rowno))
coords.append((j, rowno + 1))
# add line from (x1, y1) to (x2, y2)
(x1, y1) = coords[0]
for (x2, y2) in coords[1:]:
for r in xrange(min(y1, y2), max(y1, y2) + 1):
self.rowlines[r].add((colordst, x1, y1, x2, y2))
(x1, y1) = (x2, y2)
if j not in linestarty:
linestarty[j] = rowno + 1
self.todo = todo
self.rowno = rowno
self.level = level
self.parents = parents
self.ncleft = ncleft
self.linestarty = linestarty
self.nullentry = nullentry
if __name__ == '__main__':
ui_ = ui.ui()
repo = hg.repository(ui.ui())
revlog = RevGraph(repo)