graphmod.py
195 lines
| 6.4 KiB
| text/x-python
|
PythonLexer
/ mercurial / graphmod.py
|
r6691 | # Revision graph generator for Mercurial | ||
# | ||||
# Copyright 2008 Dirkjan Ochtman <dirkjan@ochtman.nl> | ||||
# Copyright 2007 Joel Rosdahl <joel@rosdahl.net> | ||||
# | ||||
|
r8225 | # This software may be used and distributed according to the terms of the | ||
|
r10263 | # GNU General Public License version 2 or any later version. | ||
|
r6691 | |||
|
r8840 | """supports walking the history as DAGs suitable for graphical output | ||
The most basic format we use is that of:: | ||||
(id, type, data, [parentids]) | ||||
The node and parent ids are arbitrary integers which identify a node in the | ||||
context of the graph returned. Type is a constant specifying the node type. | ||||
Data depends on type. | ||||
""" | ||||
from mercurial.node import nullrev | ||||
CHANGESET = 'C' | ||||
|
r6691 | |||
|
r14042 | def dagwalker(repo, revs): | ||
"""cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples | ||||
This generator function walks through revisions (which should be ordered | ||||
from bigger to lower). It returns a tuple for each node. The node and parent | ||||
ids are arbitrary integers which identify a node in the context of the graph | ||||
returned. | ||||
|
r8836 | """ | ||
|
r14042 | if not revs: | ||
|
r14087 | return | ||
|
r14042 | |||
cl = repo.changelog | ||||
lowestrev = min(revs) | ||||
gpcache = {} | ||||
|
r14088 | knownrevs = set(revs) | ||
|
r14087 | for rev in revs: | ||
ctx = repo[rev] | ||||
|
r14088 | parents = sorted(set([p.rev() for p in ctx.parents() | ||
if p.rev() in knownrevs])) | ||||
|
r14042 | mpars = [p.rev() for p in ctx.parents() if | ||
p.rev() != nullrev and p.rev() not in parents] | ||||
for mpar in mpars: | ||||
gp = gpcache.get(mpar) or grandparent(cl, lowestrev, revs, mpar) | ||||
gpcache[mpar] = gp | ||||
if gp is None: | ||||
|
r14087 | parents.append(mpar) | ||
elif gp not in parents: | ||||
parents.append(gp) | ||||
|
r14042 | |||
|
r14087 | yield (ctx.rev(), CHANGESET, ctx, parents) | ||
|
r8836 | |||
|
r8837 | def nodes(repo, nodes): | ||
|
r8840 | """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples | ||
This generator function walks the given nodes. It only returns parents | ||||
that are in nodes, too. | ||||
""" | ||||
|
r8837 | include = set(nodes) | ||
for node in nodes: | ||||
ctx = repo[node] | ||||
|
r12951 | parents = set([p.rev() for p in ctx.parents() if p.node() in include]) | ||
|
r8840 | yield (ctx.rev(), CHANGESET, ctx, sorted(parents)) | ||
|
r8837 | |||
|
r8842 | def colored(dag): | ||
"""annotates a DAG with colored edge information | ||||
For each DAG node this function emits tuples:: | ||||
|
r6691 | |||
|
r8842 | (id, type, data, (col, color), [(col, nextcol, color)]) | ||
|
r6691 | |||
|
r8842 | with the following new elements: | ||
|
r8835 | - Tuple (col, color) with column and color index for the current node | ||
|
r8842 | - A list of tuples indicating the edges between the current node and its | ||
parents. | ||||
|
r6691 | """ | ||
|
r8841 | seen = [] | ||
|
r6691 | colors = {} | ||
|
r8841 | newcolor = 1 | ||
|
r8842 | for (cur, type, data, parents) in dag: | ||
|
r6691 | |||
|
r8841 | # Compute seen and next | ||
if cur not in seen: | ||||
seen.append(cur) # new head | ||||
colors[cur] = newcolor | ||||
newcolor += 1 | ||||
|
r6691 | |||
|
r8841 | col = seen.index(cur) | ||
color = colors.pop(cur) | ||||
next = seen[:] | ||||
|
r6691 | |||
|
r8842 | # Add parents to next | ||
|
r6691 | addparents = [p for p in parents if p not in next] | ||
|
r8841 | next[col:col + 1] = addparents | ||
|
r6691 | |||
# Set colors for the parents | ||||
for i, p in enumerate(addparents): | ||||
if not i: | ||||
colors[p] = color | ||||
else: | ||||
|
r8841 | colors[p] = newcolor | ||
newcolor += 1 | ||||
|
r6691 | |||
# Add edges to the graph | ||||
edges = [] | ||||
|
r8841 | for ecol, eid in enumerate(seen): | ||
if eid in next: | ||||
edges.append((ecol, next.index(eid), colors[eid])) | ||||
|
r8842 | elif eid == cur: | ||
|
r6691 | for p in parents: | ||
|
r10602 | edges.append((ecol, next.index(p), color)) | ||
|
r6691 | |||
# Yield and move on | ||||
|
r8842 | yield (cur, type, data, (col, color), edges) | ||
|
r8841 | seen = next | ||
|
r14042 | |||
def grandparent(cl, lowestrev, roots, head): | ||||
"""Return closest 'root' rev in topological path from 'roots' to 'head'. | ||||
Derived from revlog.revlog.nodesbetween, but only returns next rev | ||||
of topologically sorted list of all nodes N that satisfy of these | ||||
constraints: | ||||
1. N is a descendant of some node in 'roots' | ||||
2. N is an ancestor of 'head' | ||||
3. N is some node in 'roots' or nullrev | ||||
Every node is considered to be both a descendant and an ancestor | ||||
of itself, so every reachable node in 'roots' and 'head' will be | ||||
included in 'nodes'. | ||||
""" | ||||
ancestors = set() | ||||
# Start at the top and keep marking parents until we're done. | ||||
revstotag = set([head]) | ||||
revstotag.discard(nullrev) | ||||
llowestrev = max(nullrev, lowestrev) | ||||
while revstotag: | ||||
r = revstotag.pop() | ||||
# A node's revision number represents its place in a | ||||
# topologically sorted list of nodes. | ||||
if r >= llowestrev: | ||||
if r not in ancestors: | ||||
# If we are possibly a descendent of one of the roots | ||||
# and we haven't already been marked as an ancestor | ||||
ancestors.add(r) # Mark as ancestor | ||||
# Add non-nullrev parents to list of nodes to tag. | ||||
revstotag.update([p for p in cl.parentrevs(r)]) | ||||
if not ancestors: | ||||
return | ||||
# Now that we have our set of ancestors, we want to remove any | ||||
# roots that are not ancestors. | ||||
# If one of the roots was nullrev, everything is included anyway. | ||||
if lowestrev > nullrev: | ||||
# But, since we weren't, let's recompute the lowest rev to not | ||||
# include roots that aren't ancestors. | ||||
# Filter out roots that aren't ancestors of heads | ||||
_roots = ancestors.intersection(roots) | ||||
if not _roots: | ||||
return | ||||
# Recompute the lowest revision | ||||
lowestrev = min(roots) | ||||
else: | ||||
# We are descending from nullrev, and don't need to care about | ||||
# any other roots. | ||||
lowestrev = nullrev | ||||
_roots = [nullrev] | ||||
# The roots are just the descendants. | ||||
# Don't start at nullrev since we don't want nullrev in our output list, | ||||
# and if nullrev shows up in descedents, empty parents will look like | ||||
# they're descendents. | ||||
lowestrevisnullrev = (lowestrev == nullrev) | ||||
for r in xrange(head - 1, max(lowestrev, -1) - 1, -1): | ||||
if lowestrevisnullrev or r in _roots: | ||||
pass | ||||
elif _roots.issuperset(cl.parentrevs(r)): | ||||
# A node is a descendent if either of its parents are | ||||
# descendents. (We seeded the dependents list with the roots | ||||
# up there, remember?) | ||||
_roots.add(r) | ||||
else: | ||||
continue | ||||
if r in ancestors: | ||||
# Only include nodes that are both descendents and ancestors. | ||||
return r | ||||