diff options
Diffstat (limited to 'websdk/mercurial/graphmod.py')
-rw-r--r--[l---------] | websdk/mercurial/graphmod.py | 140 |
1 files changed, 139 insertions, 1 deletions
diff --git a/websdk/mercurial/graphmod.py b/websdk/mercurial/graphmod.py index 0fda9ed..314f2b8 120000..100644 --- a/websdk/mercurial/graphmod.py +++ b/websdk/mercurial/graphmod.py @@ -1 +1,139 @@ -/usr/share/pyshared/mercurial/graphmod.py
\ No newline at end of file +# 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) |