graphmod.py
494 lines
| 16.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. | ||||
""" | ||||
|
r25951 | from __future__ import absolute_import | ||
|
r8840 | |||
|
r25951 | from .node import nullrev | ||
|
r26003 | from . import ( | ||
|
r32903 | dagop, | ||
|
r38806 | pycompat, | ||
|
r31023 | smartset, | ||
|
r26003 | util, | ||
) | ||||
|
r25951 | |||
|
r8840 | CHANGESET = 'C' | ||
|
r28376 | PARENT = 'P' | ||
GRANDPARENT = 'G' | ||||
MISSINGPARENT = 'M' | ||||
|
r28601 | # Style of line to draw. None signals a line that ends and is removed at this | ||
|
r29134 | # point. A number prefix means only the last N characters of the current block | ||
# will use that style, the rest will use the PARENT style. Add a - sign | ||||
# (so making N negative) and all but the first N characters use that style. | ||||
|
r28627 | EDGES = {PARENT: '|', GRANDPARENT: ':', MISSINGPARENT: None} | ||
|
r6691 | |||
|
r14042 | def dagwalker(repo, revs): | ||
|
r28376 | """cset DAG generator yielding (id, CHANGESET, ctx, [parentinfo]) tuples | ||
|
r14042 | |||
This generator function walks through revisions (which should be ordered | ||||
|
r28376 | from bigger to lower). It returns a tuple for each node. | ||
Each parentinfo entry is a tuple with (edgetype, parentid), where edgetype | ||||
is one of PARENT, GRANDPARENT or MISSINGPARENT. The node and parent ids | ||||
are arbitrary integers which identify a node in the context of the graph | ||||
|
r14042 | returned. | ||
|
r28376 | |||
|
r8836 | """ | ||
|
r14042 | gpcache = {} | ||
|
r14087 | for rev in revs: | ||
ctx = repo[rev] | ||||
|
r28376 | # partition into parents in the rev set and missing parents, then | ||
# augment the lists with markers, to inform graph drawing code about | ||||
# what kind of edge to draw between nodes. | ||||
pset = set(p.rev() for p in ctx.parents() if p.rev() in revs) | ||||
mpars = [p.rev() for p in ctx.parents() | ||||
if p.rev() != nullrev and p.rev() not in pset] | ||||
parents = [(PARENT, p) for p in sorted(pset)] | ||||
|
r14042 | |||
for mpar in mpars: | ||||
|
r14131 | gp = gpcache.get(mpar) | ||
|
r14042 | if gp is None: | ||
|
r26187 | # precompute slow query as we know reachableroots() goes | ||
# through all revs (issue4782) | ||||
|
r31023 | if not isinstance(revs, smartset.baseset): | ||
revs = smartset.baseset(revs) | ||||
|
r32903 | gp = gpcache[mpar] = sorted(set(dagop.reachableroots( | ||
|
r28376 | repo, revs, [mpar]))) | ||
|
r14131 | if not gp: | ||
|
r28376 | parents.append((MISSINGPARENT, mpar)) | ||
pset.add(mpar) | ||||
|
r14131 | else: | ||
|
r28376 | parents.extend((GRANDPARENT, g) for g in gp if g not in pset) | ||
pset.update(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] | ||||
|
r28376 | parents = set((PARENT, 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 | ||
|
r28376 | addparents = [p for pt, 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: | ||
|
r28376 | for ptype, 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 | |||
|
r33860 | def asciiedges(type, char, state, rev, parents): | ||
|
r17179 | """adds edge info to changelog DAG walk suitable for ascii()""" | ||
|
r28375 | seen = state['seen'] | ||
|
r17179 | if rev not in seen: | ||
seen.append(rev) | ||||
nodeidx = seen.index(rev) | ||||
knownparents = [] | ||||
newparents = [] | ||||
|
r28376 | for ptype, parent in parents: | ||
|
r31552 | if parent == rev: | ||
# self reference (should only be seen in null rev) | ||||
continue | ||||
|
r17179 | if parent in seen: | ||
knownparents.append(parent) | ||||
else: | ||||
newparents.append(parent) | ||||
|
r28600 | state['edges'][parent] = state['styles'].get(ptype, '|') | ||
|
r17179 | |||
ncols = len(seen) | ||||
|
r33860 | width = 1 + ncols * 2 | ||
|
r17179 | nextseen = seen[:] | ||
nextseen[nodeidx:nodeidx + 1] = newparents | ||||
|
r31552 | edges = [(nodeidx, nextseen.index(p)) for p in knownparents] | ||
|
r17179 | |||
|
r28998 | seen[:] = nextseen | ||
|
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 | ||||
|
r33860 | width += 2 | ||
yield (type, char, width, (nodeidx, edges, ncols, nmorecols)) | ||||
|
r17179 | char = '\\' | ||
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 | ||||
|
r33860 | if nmorecols > 0: | ||
width += 2 | ||||
|
r28600 | # remove current node from edge characters, no longer needed | ||
state['edges'].pop(rev, None) | ||||
|
r33860 | yield (type, char, width, (nodeidx, edges, ncols, nmorecols)) | ||
|
r17179 | |||
def _fixlongrightedges(edges): | ||||
for (i, (start, end)) in enumerate(edges): | ||||
if end > start: | ||||
edges[i] = (start, end + 1) | ||||
def _getnodelineedgestail( | ||||
|
r28600 | echars, idx, pidx, ncols, coldiff, pdiff, fix_tail): | ||
if fix_tail and coldiff == pdiff and coldiff != 0: | ||||
|
r17179 | # Still going in the same non-vertical direction. | ||
|
r28600 | if coldiff == -1: | ||
start = max(idx + 1, pidx) | ||||
tail = echars[idx * 2:(start - 1) * 2] | ||||
tail.extend(["/", " "] * (ncols - start)) | ||||
|
r17179 | return tail | ||
else: | ||||
|
r28600 | return ["\\", " "] * (ncols - idx - 1) | ||
|
r17179 | else: | ||
|
r28600 | remainder = (ncols - idx - 1) | ||
return echars[-(remainder * 2):] if remainder > 0 else [] | ||||
|
r17179 | |||
|
r28600 | def _drawedges(echars, edges, nodeline, interline): | ||
|
r17179 | for (start, end) in edges: | ||
if start == end + 1: | ||||
interline[2 * end + 1] = "/" | ||||
elif start == end - 1: | ||||
interline[2 * start + 1] = "\\" | ||||
elif start == end: | ||||
|
r28600 | interline[2 * start] = echars[2 * start] | ||
|
r17179 | 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] = "-" | ||||
|
r28600 | def _getpaddingline(echars, idx, ncols, edges): | ||
# all edges up to the current node | ||||
line = echars[:idx * 2] | ||||
# an edge for the current node, if there is one | ||||
if (idx, idx - 1) in edges or (idx, idx) in edges: | ||||
# (idx, idx - 1) (idx, idx) | ||||
|
r17179 | # | | | | | | | | | ||
# +---o | | o---+ | ||||
|
r28600 | # | | X | | X | | | ||
|
r17179 | # | |/ / | |/ / | ||
# | | | | | | | ||||
|
r28600 | line.extend(echars[idx * 2:(idx + 1) * 2]) | ||
|
r17179 | else: | ||
|
r32160 | line.extend([' ', ' ']) | ||
|
r28600 | # all edges to the right of the current node | ||
remainder = ncols - idx - 1 | ||||
if remainder > 0: | ||||
line.extend(echars[-(remainder * 2):]) | ||||
|
r17179 | return line | ||
|
r28601 | def _drawendinglines(lines, extra, edgemap, seen): | ||
"""Draw ending lines for missing parent edges | ||||
None indicates an edge that ends at between this node and the next | ||||
Replace with a short line ending in ~ and add / lines to any edges to | ||||
the right. | ||||
""" | ||||
if None not in edgemap.values(): | ||||
return | ||||
# Check for more edges to the right of our ending edges. | ||||
# We need enough space to draw adjustment lines for these. | ||||
edgechars = extra[::2] | ||||
while edgechars and edgechars[-1] is None: | ||||
edgechars.pop() | ||||
shift_size = max((edgechars.count(None) * 2) - 1, 0) | ||||
while len(lines) < 3 + shift_size: | ||||
lines.append(extra[:]) | ||||
if shift_size: | ||||
empties = [] | ||||
toshift = [] | ||||
first_empty = extra.index(None) | ||||
for i, c in enumerate(extra[first_empty::2], first_empty // 2): | ||||
if c is None: | ||||
empties.append(i * 2) | ||||
else: | ||||
toshift.append(i * 2) | ||||
targets = list(range(first_empty, first_empty + len(toshift) * 2, 2)) | ||||
positions = toshift[:] | ||||
for line in lines[-shift_size:]: | ||||
line[first_empty:] = [' '] * (len(line) - first_empty) | ||||
for i in range(len(positions)): | ||||
pos = positions[i] - 1 | ||||
positions[i] = max(pos, targets[i]) | ||||
line[pos] = '/' if pos > targets[i] else extra[toshift[i]] | ||||
map = {1: '|', 2: '~'} | ||||
for i, line in enumerate(lines): | ||||
if None not in line: | ||||
continue | ||||
line[:] = [c or map.get(i, ' ') for c in line] | ||||
# remove edges that ended | ||||
remove = [p for p, c in edgemap.items() if c is None] | ||||
for parent in remove: | ||||
del edgemap[parent] | ||||
seen.remove(parent) | ||||
|
r17179 | def asciistate(): | ||
"""returns the initial value for the "state" argument to ascii()""" | ||||
|
r28600 | return { | ||
'seen': [], | ||||
'edges': {}, | ||||
'lastcoldiff': 0, | ||||
'lastindex': 0, | ||||
'styles': EDGES.copy(), | ||||
|
r28891 | 'graphshorten': False, | ||
|
r28600 | } | ||
|
r17179 | |||
|
r38167 | def outputgraph(ui, graph): | ||
"""outputs an ASCII graph of a DAG | ||||
this is a helper function for 'ascii' below. | ||||
takes the following arguments: | ||||
- ui to write to | ||||
- graph data: list of { graph nodes/edges, text } | ||||
this function can be monkey-patched by extensions to alter graph display | ||||
without needing to mimic all of the edge-fixup logic in ascii() | ||||
""" | ||||
for (ln, logstr) in graph: | ||||
ui.write((ln + logstr).rstrip() + "\n") | ||||
|
r17179 | 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 | ||||
|
r28600 | |||
edgemap, seen = state['edges'], state['seen'] | ||||
# Be tolerant of history issues; make sure we have at least ncols + coldiff | ||||
# elements to work with. See test-glog.t for broken history test cases. | ||||
echars = [c for p in seen for c in (edgemap.get(p, '|'), ' ')] | ||||
echars.extend(('|', ' ') * max(ncols + coldiff - len(seen), 0)) | ||||
|
r17179 | 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) | ||||
|
r28600 | nodeline = echars[:idx * 2] | ||
|
r17179 | nodeline.extend([char, " "]) | ||
nodeline.extend( | ||||
|
r28600 | _getnodelineedgestail( | ||
echars, idx, state['lastindex'], ncols, coldiff, | ||||
state['lastcoldiff'], fix_nodeline_tail)) | ||||
|
r17179 | |||
# shift_interline is the line containing the non-vertical | ||||
# edges between this entry and the next | ||||
|
r28600 | shift_interline = echars[:idx * 2] | ||
|
r38806 | for i in pycompat.xrange(2 + coldiff): | ||
|
r32160 | shift_interline.append(' ') | ||
|
r28600 | count = ncols - idx - 1 | ||
|
r17179 | if coldiff == -1: | ||
|
r38806 | for i in pycompat.xrange(count): | ||
|
r32160 | shift_interline.extend(['/', ' ']) | ||
|
r17179 | elif coldiff == 0: | ||
|
r28600 | shift_interline.extend(echars[(idx + 1) * 2:ncols * 2]) | ||
|
r17179 | else: | ||
|
r38806 | for i in pycompat.xrange(count): | ||
|
r32160 | shift_interline.extend(['\\', ' ']) | ||
|
r17179 | |||
# draw edges from the current node to its parents | ||||
|
r28600 | _drawedges(echars, edges, nodeline, shift_interline) | ||
|
r17179 | |||
# lines is the list of all graph lines to print | ||||
lines = [nodeline] | ||||
if add_padding_line: | ||||
|
r28600 | lines.append(_getpaddingline(echars, idx, ncols, edges)) | ||
|
r28891 | |||
# If 'graphshorten' config, only draw shift_interline | ||||
# when there is any non vertical flow in graph. | ||||
if state['graphshorten']: | ||||
if any(c in '\/' for c in shift_interline if c): | ||||
lines.append(shift_interline) | ||||
# Else, no 'graphshorten' config so draw shift_interline. | ||||
else: | ||||
lines.append(shift_interline) | ||||
|
r17179 | |||
# make sure that there are as many graph lines as there are | ||||
# log strings | ||||
|
r28601 | extra_interline = echars[:(ncols + coldiff) * 2] | ||
if len(lines) < len(text): | ||||
while len(lines) < len(text): | ||||
lines.append(extra_interline[:]) | ||||
_drawendinglines(lines, extra_interline, edgemap, seen) | ||||
|
r17179 | while len(text) < len(lines): | ||
text.append("") | ||||
|
r29134 | if any(len(char) > 1 for char in edgemap.values()): | ||
# limit drawing an edge to the first or last N lines of the current | ||||
# section the rest of the edge is drawn like a parent line. | ||||
|
r36198 | parent = state['styles'][PARENT][-1:] | ||
|
r29134 | def _drawgp(char, i): | ||
# should a grandparent character be drawn for this line? | ||||
if len(char) < 2: | ||||
return True | ||||
num = int(char[:-1]) | ||||
# either skip first num lines or take last num lines, based on sign | ||||
return -num <= i if num < 0 else (len(lines) - i) <= num | ||||
for i, line in enumerate(lines): | ||||
|
r36198 | line[:] = [c[-1:] if _drawgp(c, i) else parent for c in line] | ||
|
r29184 | edgemap.update( | ||
(e, (c if len(c) < 2 else parent)) for e, c in edgemap.items()) | ||||
|
r29134 | |||
|
r17179 | # print lines | ||
indentation_level = max(ncols, ncols + coldiff) | ||||
|
r38167 | lines = ["%-*s " % (2 * indentation_level, "".join(line)) for line in lines] | ||
outputgraph(ui, zip(lines, text)) | ||||
|
r17179 | |||
# ... and start over | ||||
|
r28375 | state['lastcoldiff'] = coldiff | ||
state['lastindex'] = idx | ||||