[PATCH 08 of 10] graphmod/webcommands: use generic DAG walks

[Peter Arrenbrecht]

# HG changeset patch
# User Peter Arrenbrecht <peter.arrenbrecht at gmail.com>
# Date 1242402809 -7200
graphmod/webcommands: use generic DAG walks

Changes graph() to colorededges(), which operates on the new
generic DAG walks and adds color and edge information needed
by the web graph.

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/mercurial/graphmod.py b/mercurial/graphmod.py
--- a/mercurial/graphmod.py
+++ b/mercurial/graphmod.py
@@ -25,11 +25,10 @@
     """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
+    start down to revision stop.
+    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.
     """
-    assert start >= stop
     cur = start
     while cur >= stop:
         ctx = repo[cur]
@@ -41,10 +40,8 @@
     """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).
+    file from revision start down to revision stop.
     """
-    assert start >= stop
     filerev = len(repo.file(path)) - 1
     while filerev >= 0:
         fctx = repo.filectx(path, fileid=filerev)
@@ -68,32 +65,24 @@
         parents = [p.rev() for p in ctx.parents() if p.node() in include]
         yield (ctx.rev(), CHANGESET, ctx, sorted(parents))
 
-def graph(repo, start_rev, stop_rev):
-    """incremental revision grapher
+def colorededges(dag):
+    """annotates a DAG with colored edge information
 
-    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:
+    For each DAG node this function emits tuples::
 
-      - Context of the current node
+      (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.
     """
-
-    if start_rev == nullrev and not stop_rev:
-        return
-
-    assert start_rev >= stop_rev
-    assert stop_rev >= 0
-    id = start_rev
     seen = []
-    cl = repo.changelog
     colors = {}
     newcolor = 1
+    for (id, type, data, parentids) in dag:
 
-    while id >= stop_rev:
         # Compute seen and next
         if id not in seen:
             seen.append(id) # new head
@@ -104,9 +93,8 @@
         color = colors.pop(id)
         next = seen[:]
 
-        # Add parents to next_revs
-        parents = [x for x in cl.parentrevs(id) if x != nullrev]
-        addparents = [p for p in parents if p not in next]
+        # Add parents to next
+        addparents = [p for p in parentids if p not in next]
         next[col:col + 1] = addparents
 
         # Set colors for the parents
@@ -123,10 +111,9 @@
             if eid in next:
                 edges.append((ecol, next.index(eid), colors[eid]))
             elif eid == id:
-                for p in parents:
+                for p in parentids:
                     edges.append((ecol, next.index(p), colors[p]))
 
         # Yield and move on
-        yield (repo[id], (col, color), edges)
+        yield (id, type, data, (col, color), edges)
         seen = next
-        id -= 1
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,