--- a/mercurial/graphmod.py Fri Apr 29 03:34:18 2011 -0500
+++ b/mercurial/graphmod.py Sun Mar 13 15:53:38 2011 +0100
@@ -18,43 +18,66 @@
"""
from mercurial.node import nullrev
+from mercurial.cmdutil import revrange
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.
+def revisions(repo, start, end):
+ """DAG generator for revisions between start and end
"""
- cur = start
- while cur >= stop:
- ctx = repo[cur]
- parents = set([p.rev() for p in ctx.parents() if p.rev() != nullrev])
- yield (cur, CHANGESET, ctx, sorted(parents))
- cur -= 1
+ revset = '%s:%s' % (start, end)
+ return dagwalker(repo, revrange(repo, [revset]))
def filerevs(repo, path, start, stop, limit=None):
- """file cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples
+ """DAG generator, which is limited by file passed
+ """
+ revset = '%s:%s and file("%s")' % (start, stop, path)
+ if limit:
+ revset = 'limit(%s, %s)' % (revset, limit)
+ return dagwalker(repo, revrange(repo, [revset]))
- This generator function walks through the revision history of a single
- file from revision start down to revision stop.
+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.
"""
- filerev = len(repo.file(path)) - 1
- rev = stop + 1
- count = 0
- while filerev >= 0 and rev > stop:
- fctx = repo.filectx(path, fileid=filerev)
- parents = set([f.linkrev() for f in fctx.parents() if f.path() == path])
- rev = fctx.rev()
- if rev <= start:
- yield (rev, CHANGESET, fctx.changectx(), sorted(parents))
- count += 1
- if count == limit:
- break
- filerev -= 1
+ if not revs:
+ return []
+
+ ns = [repo[r].node() for r in revs]
+ revdag = list(nodes(repo, ns))
+
+ cl = repo.changelog
+ lowestrev = min(revs)
+ gpcache = {}
+ leafs = {}
+
+ for i, (id, c, ctx, parents) in enumerate(revdag):
+ mpars = [p.rev() for p in ctx.parents() if
+ p.rev() != nullrev and p.rev() not in parents]
+ grandparents = []
+
+ for mpar in mpars:
+ gp = gpcache.get(mpar) or grandparent(cl, lowestrev, revs, mpar)
+ gpcache[mpar] = gp
+ if gp is None:
+ leafs.setdefault(mpar, []).append((i, ctx))
+ else:
+ grandparents.append(gp)
+
+ if grandparents:
+ for gp in grandparents:
+ if gp not in revdag[i][3]:
+ revdag[i][3].append(gp)
+
+ for parent, leafs in leafs.iteritems():
+ for i, ctx in leafs:
+ revdag[i][3].append(parent)
+
+ return revdag
def nodes(repo, nodes):
"""cset DAG generator yielding (id, CHANGESET, ctx, [parentids]) tuples
@@ -120,3 +143,78 @@
# Yield and move on
yield (cur, type, data, (col, color), edges)
seen = next
+
+
+def grandparent(cl, lowestrev, roots, head):
+ """Return closest 'root' rev in topological path from 'roots' to 'head'.
+
+ Derived from revlog.revlog.nodesbetween, but only returns next rev
+ of topologically sorted list of all nodes N that satisfy of these
+ constraints:
+
+ 1. N is a descendant of some node in 'roots'
+ 2. N is an ancestor of 'head'
+ 3. N is some node in 'roots' or nullrev
+
+ Every node is considered to be both a descendant and an ancestor
+ of itself, so every reachable node in 'roots' and 'head' will be
+ included in 'nodes'.
+ """
+ ancestors = set()
+ # Start at the top and keep marking parents until we're done.
+ revstotag = set([head])
+ revstotag.discard(nullrev)
+ llowestrev = max(nullrev, lowestrev)
+
+ while revstotag:
+ r = revstotag.pop()
+ # A node's revision number represents its place in a
+ # topologically sorted list of nodes.
+ if r >= llowestrev:
+ if r not in ancestors:
+ # If we are possibly a descendent of one of the roots
+ # and we haven't already been marked as an ancestor
+ ancestors.add(r) # Mark as ancestor
+ # Add non-nullrev parents to list of nodes to tag.
+ revstotag.update([p for p in cl.parentrevs(r)])
+
+ if not ancestors:
+ return
+ # Now that we have our set of ancestors, we want to remove any
+ # roots that are not ancestors.
+
+ # If one of the roots was nullrev, everything is included anyway.
+ if lowestrev > nullrev:
+ # But, since we weren't, let's recompute the lowest rev to not
+ # include roots that aren't ancestors.
+
+ # Filter out roots that aren't ancestors of heads
+ _roots = ancestors.intersection(roots)
+ if not _roots:
+ return
+ # Recompute the lowest revision
+ lowestrev = min(roots)
+ else:
+ # We are descending from nullrev, and don't need to care about
+ # any other roots.
+ lowestrev = nullrev
+ _roots = [nullrev]
+
+ # The roots are just the descendants.
+ # Don't start at nullrev since we don't want nullrev in our output list,
+ # and if nullrev shows up in descedents, empty parents will look like
+ # they're descendents.
+ lowestrevisnullrev = (lowestrev == nullrev)
+ for r in xrange(head - 1, max(lowestrev, -1) - 1, -1):
+ if lowestrevisnullrev or r in _roots:
+ pass
+ elif _roots.issuperset(cl.parentrevs(r)):
+ # A node is a descendent if either of its parents are
+ # descendents. (We seeded the dependents list with the roots
+ # up there, remember?)
+ _roots.add(r)
+ else:
+ continue
+ if r in ancestors:
+ # Only include nodes that are both descendents and ancestors.
+ return r