[PATCH 2 of 4] graphmod/graphlog: refactor and move common code to graphmod
Peter Arrenbrecht
peter.arrenbrecht at gmail.com
Thu May 14 10:36:43 CDT 2009
# HG changeset patch
# User Peter Arrenbrecht <peter.arrenbrecht at gmail.com>
# Date 1242315165 -7200
graphmod/graphlog: refactor and move common code to graphmod
This is in preparation of adding DAG walk filters, like the
linear run collapser in the next patch. The idea is to have
a bunch of changelog walkers that return basic data. Then we
can filter this data. Finally we add edge and formatting info
suitable for the output media we want to target (glog, hgweb).
diff --git a/hgext/graphlog.py b/hgext/graphlog.py
--- a/hgext/graphlog.py
+++ b/hgext/graphlog.py
@@ -12,59 +12,31 @@
revision graph is also shown.
'''
-import os
+import os, sys
from mercurial.cmdutil import revrange, show_changeset
from mercurial.commands import templateopts
from mercurial.i18n import _
from mercurial.node import nullrev
from mercurial import bundlerepo, changegroup, cmdutil, commands, extensions
-from mercurial import hg, url, util
+from mercurial import hg, url, util, graphmod
-def revisions(repo, start, stop):
- """cset DAG generator yielding (rev, node, [parents]) tuples
+ASCIIDATA = 'ASC'
- This generator function walks through the revision history from revision
- start to revision stop (which must be less than or equal to start).
- """
- assert start >= stop
- cur = start
- while cur >= stop:
- ctx = repo[cur]
- parents = [p.rev() for p in ctx.parents() if p.rev() != nullrev]
- parents.sort()
- yield (ctx, parents)
- cur -= 1
+def asciiformat(ui, repo, revdag, opts):
+ """formats a changelog DAG walk for ascii output"""
+ showparents = [ctx.node() for ctx in repo[None].parents()]
+ displayer = show_changeset(ui, repo, opts, buffered=True)
+ for (id, type, ctx, parentids) in revdag:
+ if type == graphmod.CHANGESET:
+ displayer.show(ctx)
+ lines = displayer.hunk.pop(ctx.rev()).split('\n')[:-1]
+ char = ctx.node() in showparents and '@' or 'o'
+ yield (id, ASCIIDATA, (char, lines), parentids)
-def filerevs(repo, path, start, stop):
- """file cset DAG generator yielding (rev, node, [parents]) tuples
-
- This generator function walks through the revision history of a single
- file from revision start to revision stop (which must be less than or
- equal to start).
- """
- assert start >= stop
- filerev = len(repo.file(path)) - 1
- while filerev >= 0:
- fctx = repo.filectx(path, fileid=filerev)
- parents = [f.linkrev() for f in fctx.parents() if f.path() == path]
- parents.sort()
- if fctx.rev() <= start:
- yield (fctx, parents)
- if fctx.rev() <= stop:
- break
- filerev -= 1
-
-def grapher(nodes):
- """grapher for asciigraph on a list of nodes and their parents
-
- nodes must generate tuples (node, parents, char, lines) where
- - parents must generate the parents of node, in sorted order,
- and max length 2,
- - char is the char to print as the node symbol, and
- - lines are the lines to display next to the node.
- """
+def asciiedges(nodes):
+ """adds edge info to changelog DAG walk suitable for ascii()"""
seen = []
- for node, parents, char, lines in nodes:
+ for node, type, data, parents in nodes:
if node not in seen:
seen.append(node)
nodeidx = seen.index(node)
@@ -88,7 +60,7 @@
edges.append((nodeidx, nodeidx + 1))
nmorecols = len(nextseen) - ncols
seen = nextseen
- yield (char, lines, nodeidx, edges, ncols, nmorecols)
+ yield (nodeidx, type, data, edges, ncols, nmorecols)
def fix_long_right_edges(edges):
for (i, (start, end)) in enumerate(edges):
@@ -142,14 +114,16 @@
line.extend(["|", " "] * (n_columns - ni - 1))
return line
-def ascii(ui, grapher):
- """prints an ASCII graph of the DAG returned by the grapher
+def ascii(ui, dag):
+ """prints an ASCII graph of the DAG
- grapher is a generator that emits tuples with the following elements:
+ dag is a generator that emits tuples with the following elements:
- - Character to use as node's symbol.
- - List of lines to display as the node's text.
- Column of the current node in the set of ongoing edges.
+ - Type indicator of node data == ASCIIDATA.
+ - 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.
@@ -160,7 +134,7 @@
"""
prev_n_columns_diff = 0
prev_node_index = 0
- for (node_ch, node_lines, node_index, edges, n_columns, n_columns_diff) in grapher:
+ for (node_index, type, (node_ch, node_lines), edges, n_columns, n_columns_diff) in dag:
assert -2 < n_columns_diff < 2
if n_columns_diff == -1:
@@ -278,34 +252,19 @@
if path:
path = util.canonpath(repo.root, os.getcwd(), path)
if path: # could be reset in canonpath
- revdag = filerevs(repo, path, start, stop)
+ revdag = graphmod.filelogwalk(repo, path, start, stop)
else:
- revdag = revisions(repo, start, stop)
+ revdag = graphmod.changelogwalk(repo, start, stop)
- graphdag = graphabledag(ui, repo, revdag, opts)
- ascii(ui, grapher(graphdag))
+ fmtdag = asciiformat(ui, repo, revdag, opts)
+ ascii(ui, asciiedges(fmtdag))
def graphrevs(repo, nodes, opts):
- include = set(nodes)
limit = cmdutil.loglimit(opts)
- count = 0
- for node in reversed(nodes):
- if count >= limit:
- break
- ctx = repo[node]
- parents = [p.rev() for p in ctx.parents() if p.node() in include]
- parents.sort()
- yield (ctx, parents)
- count += 1
-
-def graphabledag(ui, repo, revdag, opts):
- showparents = [ctx.node() for ctx in repo[None].parents()]
- displayer = show_changeset(ui, repo, opts, buffered=True)
- for (ctx, parents) in revdag:
- displayer.show(ctx)
- lines = displayer.hunk.pop(ctx.rev()).split('\n')[:-1]
- char = ctx.node() in showparents and '@' or 'o'
- yield (ctx.rev(), parents, char, lines)
+ nodes.reverse()
+ if limit < sys.maxint:
+ nodes = nodes[:limit]
+ return graphmod.nodelistwalk(repo, nodes)
def goutgoing(ui, repo, dest=None, **opts):
"""show the outgoing changesets alongside an ASCII revision graph
@@ -332,8 +291,8 @@
o = repo.changelog.nodesbetween(o, revs)[0]
revdag = graphrevs(repo, o, opts)
- graphdag = graphabledag(ui, repo, revdag, opts)
- ascii(ui, grapher(graphdag))
+ fmtdag = asciiformat(ui, repo, revdag, opts)
+ ascii(ui, asciiedges(fmtdag))
def gincoming(ui, repo, source="default", **opts):
"""show the incoming changesets alongside an ASCII revision graph
@@ -381,8 +340,8 @@
chlist = other.changelog.nodesbetween(incoming, revs)[0]
revdag = graphrevs(other, chlist, opts)
- graphdag = graphabledag(ui, repo, revdag, opts)
- ascii(ui, grapher(graphdag))
+ fmtdag = asciiformat(ui, repo, revdag, opts)
+ ascii(ui, asciiedges(fmtdag))
finally:
if hasattr(other, 'close'):
diff --git a/mercurial/graphmod.py b/mercurial/graphmod.py
--- a/mercurial/graphmod.py
+++ b/mercurial/graphmod.py
@@ -6,67 +6,117 @@
# This software may be used and distributed according to the terms of the
# GNU General Public License version 2, incorporated herein by reference.
-from node import nullrev
+"""supports walking the history as DAGs suitable for graphical output
-def graph(repo, start_rev, stop_rev):
- """incremental revision grapher
+The most basic format we use is that of::
- This generator function walks through the revision history from
- revision start_rev to revision stop_rev (which must be less than
- or equal to start_rev) and for each revision emits tuples with the
- following elements:
+ (id, type, data, [parentids])
- - Context of the current node
+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 changelogwalk(repo, start, stop):
+ """cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples
+
+ This generator function walks through the revision history from revision
+ start to revision stop (which must be less than or equal to start). It
+ return a tuple for each node. The node and parent ids are arbitrary
+ integers which identify a node in the context of the graph returned.
+ """
+ assert start >= stop
+ cur = start
+ while cur >= stop:
+ ctx = repo[cur]
+ parents = [p.rev() for p in ctx.parents() if p.rev() != nullrev]
+ yield (cur, CHANGESET, ctx, parents)
+ cur -= 1
+
+def filelogwalk(repo, path, start, stop):
+ """file cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples
+
+ This generator function walks through the revision history of a single
+ file from revision start to revision stop (which must be less than or
+ equal to start).
+ """
+ assert start >= stop
+ filerev = len(repo.file(path)) - 1
+ while filerev >= 0:
+ fctx = repo.filectx(path, fileid=filerev)
+ parents = [f.linkrev() for f in fctx.parents() if f.path() == path]
+ rev = fctx.rev()
+ if rev <= start:
+ yield (rev, CHANGESET, fctx, parents)
+ if rev <= stop:
+ break
+ filerev -= 1
+
+def nodelistwalk(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 = [p.rev() for p in ctx.parents() if p.node() in include]
+ yield (ctx.rev(), CHANGESET, ctx, parents)
+
+def colorededges(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
- - Edges; a list of (col, next_col, color) indicating the edges between
- the current node and its parents.
+ - A list of tuples indicating the edges between the current node and its
+ parents.
"""
+ seen = []
+ colors = {}
+ newcolor = 1
+ for (id, type, data, parentids) in dag:
- if start_rev == nullrev and not stop_rev:
- return
+ # Compute seen and next
+ if id not in seen:
+ seen.append(id) # new head
+ colors[id] = newcolor
+ newcolor += 1
- assert start_rev >= stop_rev
- assert stop_rev >= 0
- curr_rev = start_rev
- revs = []
- cl = repo.changelog
- colors = {}
- new_color = 1
+ col = seen.index(id)
+ color = colors.pop(id)
+ next = seen[:]
- while curr_rev >= stop_rev:
- # Compute revs and next_revs
- if curr_rev not in revs:
- revs.append(curr_rev) # new head
- colors[curr_rev] = new_color
- new_color += 1
-
- idx = revs.index(curr_rev)
- color = colors.pop(curr_rev)
- next = revs[:]
-
- # Add parents to next_revs
- parents = [x for x in cl.parentrevs(curr_rev) if x != nullrev]
- addparents = [p for p in parents if p not in next]
- next[idx:idx + 1] = addparents
+ # Add parents to next
+ addparents = [p for p in parentids if p not in seen]
+ 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] = new_color
- new_color += 1
+ colors[p] = newcolor
+ newcolor += 1
# Add edges to the graph
edges = []
- for col, r in enumerate(revs):
- if r in next:
- edges.append((col, next.index(r), colors[r]))
- elif r == curr_rev:
- for p in parents:
- edges.append((col, next.index(p), colors[p]))
+ for ecol, eid in enumerate(seen):
+ if eid in next:
+ edges.append((ecol, next.index(eid), colors[eid]))
+ elif eid == id:
+ for p in parentids:
+ edges.append((ecol, next.index(p), colors[p]))
# Yield and move on
- yield (repo[curr_rev], (idx, color), edges)
- revs = next
- curr_rev -= 1
+ yield (id, type, data, (col, color), edges)
+ seen = next
diff --git a/mercurial/hgweb/webcommands.py b/mercurial/hgweb/webcommands.py
--- a/mercurial/hgweb/webcommands.py
+++ b/mercurial/hgweb/webcommands.py
@@ -659,18 +659,21 @@
count = len(web.repo)
changenav = webutil.revnavgen(rev, revcount, count, web.repo.changectx)
- tree = list(graphmod.graph(web.repo, rev, downrev))
+ dag = graphmod.changelogwalk(web.repo, rev, downrev)
+ tree = list(graphmod.colorededges(dag))
canvasheight = (len(tree) + 1) * bg_height - 27;
data = []
- for (ctx, vtx, edges) in tree:
- node = short(ctx.node())
- age = templatefilters.age(ctx.date())
- desc = templatefilters.firstline(ctx.description())
- desc = cgi.escape(templatefilters.nonempty(desc))
- user = cgi.escape(templatefilters.person(ctx.user()))
- branch = ctx.branch()
- branch = branch, web.repo.branchtags().get(branch) == ctx.node()
- data.append((node, vtx, edges, desc, user, age, branch, ctx.tags()))
+ for (id, type, any, vtx, edges) in tree:
+ if type == graphmod.CHANGESET:
+ ctx = any
+ node = short(ctx.node())
+ age = templatefilters.age(ctx.date())
+ desc = templatefilters.firstline(ctx.description())
+ desc = cgi.escape(templatefilters.nonempty(desc))
+ user = cgi.escape(templatefilters.person(ctx.user()))
+ branch = ctx.branch()
+ branch = branch, web.repo.branchtags().get(branch) == ctx.node()
+ data.append((node, vtx, edges, desc, user, age, branch, ctx.tags()))
return tmpl('graph', rev=rev, revcount=revcount, uprev=uprev,
lessvars=lessvars, morevars=morevars, downrev=downrev,
More information about the Mercurial-devel
mailing list