view mercurial/graphmod.py @ 14093:ce99d887585f

httprepo: long arguments support (issue2126)

Send the command arguments in the HTTP headers. The command is still part
of the URL. If the server does not have the 'httpheader' capability, the
client will send the command arguments in the URL as it did previously.

Web servers typically allow more data to be placed within the headers than
in the URL, so this approach will:
- Avoid HTTP errors due to using a URL that is too large.
- Allow Mercurial to implement a more efficient wire protocol.

An alternate approach is to send the arguments as part of the request body.
This approach has been rejected because it requires the use of POST
requests, so it would break any existing configuration that relies on the
request type for authentication or caching.

Extensibility:
- The header size is provided by the server, which makes it possible to
  introduce an hgrc setting for it.
- The client ignores the capability value after the first comma, which
  allows more information to be included in the future.

# 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