--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/upmana/mercurial/graphmod.py	Tue Nov 10 14:11:28 2009 -0600
@@ -0,0 +1,119 @@
+# 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, incorporated herein by reference.
+
+"""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 revisions(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
+    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.
+    """
+    cur = start
+    while cur >= stop:
+        ctx = repo[cur]
+        parents = [p.rev() for p in ctx.parents() if p.rev() != nullrev]
+        yield (cur, CHANGESET, ctx, sorted(parents))
+        cur -= 1
+
+def filerevs(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 down to revision 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, sorted(parents))
+        if rev <= stop:
+            break
+        filerev -= 1
+
+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 = [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), colors[p]))
+
+        # Yield and move on
+        yield (cur, type, data, (col, color), edges)
+        seen = next