view mercurial/graphmod.py @ 14088:e83ced8b6464

graphlog: use a set for inclusion test

This makes a big difference in performance in the special case where all
revisions are being graphed.

# Revision graph generator for Mercurial
#
# Copyright 2008 Dirkjan Ochtman <[e-mail]>
# Copyright 2007 Joel Rosdahl <[e-mail]>
#
# 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

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) or grandparent(cl, lowestrev, revs, mpar)
            gpcache[mpar] = gp
            if gp is None:
                parents.append(mpar)
            elif gp not in parents:
                parents.append(gp)

        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):
    """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), color))

        # 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