/usr/share/pyshared/mercurial/graphmod.py is in mercurial-common 2.0.2-1ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 | # Revision graph generator for Mercurial
#
# Copyright 2008 Dirkjan Ochtman <dirkjan@ochtman.nl>
# Copyright 2007 Joel Rosdahl <joel@rosdahl.net>
#
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2 or any later version.
"""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'
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.
"""
if not revs:
return
cl = repo.changelog
lowestrev = min(revs)
gpcache = {}
knownrevs = set(revs)
for rev in revs:
ctx = repo[rev]
parents = sorted(set([p.rev() for p in ctx.parents()
if p.rev() in knownrevs]))
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)
if gp is None:
gp = gpcache[mpar] = grandparent(cl, lowestrev, revs, mpar)
if not gp:
parents.append(mpar)
else:
parents.extend(g for g in gp if g not in parents)
yield (ctx.rev(), CHANGESET, ctx, parents)
def nodes(repo, nodes):
"""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.
"""
include = set(nodes)
for node in nodes:
ctx = repo[node]
parents = set([p.rev() for p in ctx.parents() if p.node() in include])
yield (ctx.rev(), CHANGESET, ctx, sorted(parents))
def colored(dag):
"""annotates a DAG with colored edge information
For each DAG node this function emits tuples::
(id, type, data, (col, color), [(col, nextcol, color)])
with the following new elements:
- Tuple (col, color) with column and color index for the current node
- A list of tuples indicating the edges between the current node and its
parents.
"""
seen = []
colors = {}
newcolor = 1
for (cur, type, data, parents) in dag:
# Compute seen and next
if cur not in seen:
seen.append(cur) # new head
colors[cur] = newcolor
newcolor += 1
col = seen.index(cur)
color = colors.pop(cur)
next = seen[:]
# Add parents to next
addparents = [p for p in parents if p not in next]
next[col:col + 1] = addparents
# Set colors for the parents
for i, p in enumerate(addparents):
if not i:
colors[p] = color
else:
colors[p] = newcolor
newcolor += 1
# Add edges to the graph
edges = []
for ecol, eid in enumerate(seen):
if eid in next:
edges.append((ecol, next.index(eid), colors[eid]))
elif eid == cur:
for p in parents:
edges.append((ecol, next.index(p), color))
# Yield and move on
yield (cur, type, data, (col, color), edges)
seen = next
def grandparent(cl, lowestrev, roots, head):
"""Return all ancestors of head in roots which revision is
greater or equal to lowestrev.
"""
pending = set([head])
seen = set()
kept = set()
llowestrev = max(nullrev, lowestrev)
while pending:
r = pending.pop()
if r >= llowestrev and r not in seen:
if r in roots:
kept.add(r)
else:
pending.update([p for p in cl.parentrevs(r)])
seen.add(r)
return sorted(kept)
|