Mercurial > hg
view mercurial/graphmod.py @ 16986:79902f7e27df
tests: convert some hghave unix-permissions to #if
author | Mads Kiilerich <mads@kiilerich.com> |
---|---|
date | Tue, 19 Jun 2012 01:43:41 +0200 |
parents | 6e4de55a41a4 |
children | 0849d725e2f9 |
line wrap: on
line source
# 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 import util 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, repo): """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 config = {} for key, val in repo.ui.configitems('graph'): if '.' in key: branch, setting = key.rsplit('.', 1) # Validation if setting == "width" and val.isdigit(): config.setdefault(branch, {})[setting] = int(val) elif setting == "color" and val.isalnum(): config.setdefault(branch, {})[setting] = val if config: getconf = util.lrucachefunc( lambda rev: config.get(repo[rev].branch(), {})) else: getconf = lambda rev: {} 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: bconf = getconf(eid) edges.append(( ecol, next.index(eid), colors[eid], bconf.get('width', -1), bconf.get('color', ''))) elif eid == cur: for p in parents: bconf = getconf(p) edges.append(( ecol, next.index(p), color, bconf.get('width', -1), bconf.get('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)