graphmod.py
368 lines
| 11.8 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 | ||||
|
r16132 | import util | ||
|
r8840 | |||
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 | ||||
|
r20762 | lowestrev = revs.min() | ||
|
r14042 | gpcache = {} | ||
|
r22878 | knownrevs = 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: | ||||
|
r14131 | gp = gpcache.get(mpar) | ||
|
r14042 | if gp is None: | ||
|
r14131 | gp = gpcache[mpar] = grandparent(cl, lowestrev, revs, mpar) | ||
if not gp: | ||||
|
r14087 | parents.append(mpar) | ||
|
r14131 | else: | ||
parents.extend(g for g in gp if g not in parents) | ||||
|
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 | |||
|
r16129 | def colored(dag, repo): | ||
|
r8842 | """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 | ||
|
r16129 | config = {} | ||
for key, val in repo.ui.configitems('graph'): | ||||
|
r16131 | if '.' in key: | ||
branch, setting = key.rsplit('.', 1) | ||||
# Validation | ||||
if setting == "width" and val.isdigit(): | ||||
|
r16138 | config.setdefault(branch, {})[setting] = int(val) | ||
|
r16131 | elif setting == "color" and val.isalnum(): | ||
config.setdefault(branch, {})[setting] = val | ||||
|
r16129 | |||
|
r16132 | if config: | ||
|
r16138 | getconf = util.lrucachefunc( | ||
lambda rev: config.get(repo[rev].branch(), {})) | ||||
|
r16132 | else: | ||
|
r16138 | getconf = lambda rev: {} | ||
|
r16129 | |||
|
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: | ||||
|
r16138 | bconf = getconf(eid) | ||
|
r16129 | edges.append(( | ||
ecol, next.index(eid), colors[eid], | ||||
|
r16138 | bconf.get('width', -1), | ||
bconf.get('color', ''))) | ||||
|
r8842 | elif eid == cur: | ||
|
r6691 | for p in parents: | ||
|
r16138 | bconf = getconf(p) | ||
|
r16129 | edges.append(( | ||
ecol, next.index(p), color, | ||||
|
r16138 | bconf.get('width', -1), | ||
bconf.get('color', ''))) | ||||
|
r6691 | |||
# Yield and move on | ||||
|
r8842 | yield (cur, type, data, (col, color), edges) | ||
|
r8841 | seen = next | ||
|
r14042 | |||
def grandparent(cl, lowestrev, roots, head): | ||||
|
r14131 | """Return all ancestors of head in roots which revision is | ||
greater or equal to lowestrev. | ||||
|
r14042 | """ | ||
|
r14131 | pending = set([head]) | ||
seen = set() | ||||
kept = set() | ||||
|
r14042 | llowestrev = max(nullrev, lowestrev) | ||
|
r14131 | 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) | ||||
|
r17179 | |||
def asciiedges(type, char, lines, seen, rev, parents): | ||||
"""adds edge info to changelog DAG walk suitable for ascii()""" | ||||
if rev not in seen: | ||||
seen.append(rev) | ||||
nodeidx = seen.index(rev) | ||||
knownparents = [] | ||||
newparents = [] | ||||
for parent in parents: | ||||
if parent in seen: | ||||
knownparents.append(parent) | ||||
else: | ||||
newparents.append(parent) | ||||
ncols = len(seen) | ||||
nextseen = seen[:] | ||||
nextseen[nodeidx:nodeidx + 1] = newparents | ||||
|
r18467 | edges = [(nodeidx, nextseen.index(p)) for p in knownparents if p != nullrev] | ||
|
r17179 | |||
while len(newparents) > 2: | ||||
# ascii() only knows how to add or remove a single column between two | ||||
# calls. Nodes with more than two parents break this constraint so we | ||||
# introduce intermediate expansion lines to grow the active node list | ||||
# slowly. | ||||
edges.append((nodeidx, nodeidx)) | ||||
edges.append((nodeidx, nodeidx + 1)) | ||||
nmorecols = 1 | ||||
yield (type, char, lines, (nodeidx, edges, ncols, nmorecols)) | ||||
char = '\\' | ||||
lines = [] | ||||
nodeidx += 1 | ||||
ncols += 1 | ||||
edges = [] | ||||
del newparents[0] | ||||
if len(newparents) > 0: | ||||
edges.append((nodeidx, nodeidx)) | ||||
if len(newparents) > 1: | ||||
edges.append((nodeidx, nodeidx + 1)) | ||||
nmorecols = len(nextseen) - ncols | ||||
seen[:] = nextseen | ||||
yield (type, char, lines, (nodeidx, edges, ncols, nmorecols)) | ||||
def _fixlongrightedges(edges): | ||||
for (i, (start, end)) in enumerate(edges): | ||||
if end > start: | ||||
edges[i] = (start, end + 1) | ||||
def _getnodelineedgestail( | ||||
node_index, p_node_index, n_columns, n_columns_diff, p_diff, fix_tail): | ||||
if fix_tail and n_columns_diff == p_diff and n_columns_diff != 0: | ||||
# Still going in the same non-vertical direction. | ||||
if n_columns_diff == -1: | ||||
start = max(node_index + 1, p_node_index) | ||||
tail = ["|", " "] * (start - node_index - 1) | ||||
tail.extend(["/", " "] * (n_columns - start)) | ||||
return tail | ||||
else: | ||||
return ["\\", " "] * (n_columns - node_index - 1) | ||||
else: | ||||
return ["|", " "] * (n_columns - node_index - 1) | ||||
def _drawedges(edges, nodeline, interline): | ||||
for (start, end) in edges: | ||||
if start == end + 1: | ||||
interline[2 * end + 1] = "/" | ||||
elif start == end - 1: | ||||
interline[2 * start + 1] = "\\" | ||||
elif start == end: | ||||
interline[2 * start] = "|" | ||||
else: | ||||
if 2 * end >= len(nodeline): | ||||
continue | ||||
nodeline[2 * end] = "+" | ||||
if start > end: | ||||
(start, end) = (end, start) | ||||
for i in range(2 * start + 1, 2 * end): | ||||
if nodeline[i] != "+": | ||||
nodeline[i] = "-" | ||||
def _getpaddingline(ni, n_columns, edges): | ||||
line = [] | ||||
line.extend(["|", " "] * ni) | ||||
if (ni, ni - 1) in edges or (ni, ni) in edges: | ||||
# (ni, ni - 1) (ni, ni) | ||||
# | | | | | | | | | ||||
# +---o | | o---+ | ||||
# | | c | | c | | | ||||
# | |/ / | |/ / | ||||
# | | | | | | | ||||
c = "|" | ||||
else: | ||||
c = " " | ||||
line.extend([c, " "]) | ||||
line.extend(["|", " "] * (n_columns - ni - 1)) | ||||
return line | ||||
def asciistate(): | ||||
"""returns the initial value for the "state" argument to ascii()""" | ||||
return [0, 0] | ||||
def ascii(ui, state, type, char, text, coldata): | ||||
"""prints an ASCII graph of the DAG | ||||
takes the following arguments (one call per node in the graph): | ||||
- ui to write to | ||||
- Somewhere to keep the needed state in (init to asciistate()) | ||||
- Column of the current node in the set of ongoing edges. | ||||
- Type indicator of node data, usually 'C' for changesets. | ||||
- Payload: (char, lines): | ||||
- Character to use as node's symbol. | ||||
- List of lines to display as the node's text. | ||||
- Edges; a list of (col, next_col) indicating the edges between | ||||
the current node and its parents. | ||||
- Number of columns (ongoing edges) in the current revision. | ||||
- The difference between the number of columns (ongoing edges) | ||||
in the next revision and the number of columns (ongoing edges) | ||||
in the current revision. That is: -1 means one column removed; | ||||
0 means no columns added or removed; 1 means one column added. | ||||
""" | ||||
idx, edges, ncols, coldiff = coldata | ||||
assert -2 < coldiff < 2 | ||||
if coldiff == -1: | ||||
# Transform | ||||
# | ||||
# | | | | | | | ||||
# o | | into o---+ | ||||
# |X / |/ / | ||||
# | | | | | ||||
_fixlongrightedges(edges) | ||||
# add_padding_line says whether to rewrite | ||||
# | ||||
# | | | | | | | | | ||||
# | o---+ into | o---+ | ||||
# | / / | | | # <--- padding line | ||||
# o | | | / / | ||||
# o | | | ||||
add_padding_line = (len(text) > 2 and coldiff == -1 and | ||||
[x for (x, y) in edges if x + 1 < y]) | ||||
# fix_nodeline_tail says whether to rewrite | ||||
# | ||||
# | | o | | | | o | | | ||||
# | | |/ / | | |/ / | ||||
# | o | | into | o / / # <--- fixed nodeline tail | ||||
# | |/ / | |/ / | ||||
# o | | o | | | ||||
fix_nodeline_tail = len(text) <= 2 and not add_padding_line | ||||
# nodeline is the line containing the node character (typically o) | ||||
nodeline = ["|", " "] * idx | ||||
nodeline.extend([char, " "]) | ||||
nodeline.extend( | ||||
_getnodelineedgestail(idx, state[1], ncols, coldiff, | ||||
state[0], fix_nodeline_tail)) | ||||
# shift_interline is the line containing the non-vertical | ||||
# edges between this entry and the next | ||||
shift_interline = ["|", " "] * idx | ||||
if coldiff == -1: | ||||
n_spaces = 1 | ||||
edge_ch = "/" | ||||
elif coldiff == 0: | ||||
n_spaces = 2 | ||||
edge_ch = "|" | ||||
else: | ||||
n_spaces = 3 | ||||
edge_ch = "\\" | ||||
shift_interline.extend(n_spaces * [" "]) | ||||
shift_interline.extend([edge_ch, " "] * (ncols - idx - 1)) | ||||
# draw edges from the current node to its parents | ||||
_drawedges(edges, nodeline, shift_interline) | ||||
# lines is the list of all graph lines to print | ||||
lines = [nodeline] | ||||
if add_padding_line: | ||||
lines.append(_getpaddingline(idx, ncols, edges)) | ||||
lines.append(shift_interline) | ||||
# make sure that there are as many graph lines as there are | ||||
# log strings | ||||
while len(text) < len(lines): | ||||
text.append("") | ||||
if len(lines) < len(text): | ||||
extra_interline = ["|", " "] * (ncols + coldiff) | ||||
while len(lines) < len(text): | ||||
lines.append(extra_interline) | ||||
# print lines | ||||
indentation_level = max(ncols, ncols + coldiff) | ||||
for (line, logstr) in zip(lines, text): | ||||
ln = "%-*s %s" % (2 * indentation_level, "".join(line), logstr) | ||||
ui.write(ln.rstrip() + '\n') | ||||
# ... and start over | ||||
state[0] = coldiff | ||||
state[1] = idx | ||||