diff -r bcc6ed0f6c3b -r 9966c95b8c4f mercurial/graphmod.py --- 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