mercurial/ancestor.py

# ancestor.py - generic DAG ancestor algorithm for mercurial
#
# Copyright 2006 Matt Mackall <[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.

import heapq
from node import nullrev

def ancestor(a, b, pfunc):
    """
    Returns the common ancestor of a and b that is furthest from a
    root (as measured by longest path) or None if no ancestor is
    found. If there are multiple common ancestors at the same
    distance, the first one found is returned.

    pfunc must return a list of parent vertices for a given vertex
    """

    if a == b:
        return a

    a, b = sorted([a, b])

    # find depth from root of all ancestors
    # depth is stored as a negative for heapq
    parentcache = {}
    visit = [a, b]
    depth = {}
    while visit:
        vertex = visit[-1]
        pl = pfunc(vertex)
        parentcache[vertex] = pl
        if not pl:
            depth[vertex] = 0
            visit.pop()
        else:
            for p in pl:
                if p == a or p == b: # did we find a or b as a parent?
                    return p # we're done
                if p not in depth:
                    visit.append(p)
            if visit[-1] == vertex:
                # -(maximum distance of parents + 1)
                depth[vertex] = min([depth[p] for p in pl]) - 1
                visit.pop()

    # traverse ancestors in order of decreasing distance from root
    def ancestors(vertex):
        h = [(depth[vertex], vertex)]
        seen = set()
        while h:
            d, n = heapq.heappop(h)
            if n not in seen:
                seen.add(n)
                yield (d, n)
                for p in parentcache[n]:
                    heapq.heappush(h, (depth[p], p))

    def generations(vertex):
        sg, s = None, set()
        for g, v in ancestors(vertex):
            if g != sg:
                if sg:
                    yield sg, s
                sg, s = g, set((v,))
            else:
                s.add(v)
        yield sg, s

    x = generations(a)
    y = generations(b)
    gx = x.next()
    gy = y.next()

    # increment each ancestor list until it is closer to root than
    # the other, or they match
    try:
        while True:
            if gx[0] == gy[0]:
                for v in gx[1]:
                    if v in gy[1]:
                        return v
                gy = y.next()
                gx = x.next()
            elif gx[0] > gy[0]:
                gy = y.next()
            else:
                gx = x.next()
    except StopIteration:
        return None

def missingancestors(revs, bases, pfunc):
    """Return all the ancestors of revs that are not ancestors of bases.

    This may include elements from revs.

    Equivalent to the revset (::revs - ::bases). Revs are returned in
    revision number order, which is a topological order.

    revs and bases should both be iterables. pfunc must return a list of
    parent revs for a given revs.

    graph is a dict of child->parent adjacency lists for this graph:
    o  13
    |
    | o  12
    | |
    | | o    11
    | | |\
    | | | | o  10
    | | | | |
    | o---+ |  9
    | | | | |
    o | | | |  8
     / / / /
    | | o |  7
    | | | |
    o---+ |  6
     / / /
    | | o  5
    | |/
    | o  4
    | |
    o |  3
    | |
    | o  2
    |/
    o  1
    |
    o  0
    >>> graph = {0: [-1], 1: [0], 2: [1], 3: [1], 4: [2], 5: [4], 6: [4],
    ...          7: [4], 8: [-1], 9: [6, 7], 10: [5], 11: [3, 7], 12: [9],
    ...          13: [8]}
    >>> pfunc = graph.get

    Empty revs
    >>> missingancestors([], [1], pfunc)
    []
    >>> missingancestors([], [], pfunc)
    []

    If bases is empty, it's the same as if it were [nullrev]
    >>> missingancestors([12], [], pfunc)
    [0, 1, 2, 4, 6, 7, 9, 12]

    Trivial case: revs == bases
    >>> missingancestors([0], [0], pfunc)
    []
    >>> missingancestors([4, 5, 6], [6, 5, 4], pfunc)
    []

    With nullrev
    >>> missingancestors([-1], [12], pfunc)
    []
    >>> missingancestors([12], [-1], pfunc)
    [0, 1, 2, 4, 6, 7, 9, 12]

    9 is a parent of 12. 7 is a parent of 9, so an ancestor of 12. 6 is an
    ancestor of 12 but not of 7.
    >>> missingancestors([12], [9], pfunc)
    [12]
    >>> missingancestors([9], [12], pfunc)
    []
    >>> missingancestors([12, 9], [7], pfunc)
    [6, 9, 12]
    >>> missingancestors([7, 6], [12], pfunc)
    []

    More complex cases
    >>> missingancestors([10], [11, 12], pfunc)
    [5, 10]
    >>> missingancestors([11], [10], pfunc)
    [3, 7, 11]
    >>> missingancestors([11], [10, 12], pfunc)
    [3, 11]
    >>> missingancestors([12], [10], pfunc)
    [6, 7, 9, 12]
    >>> missingancestors([12], [11], pfunc)
    [6, 9, 12]
    >>> missingancestors([10, 11, 12], [13], pfunc)
    [0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12]
    >>> missingancestors([13], [10, 11, 12], pfunc)
    [8, 13]
    """

    revsvisit = set(revs)
    basesvisit = set(bases)
    if not revsvisit:
        return []
    if not basesvisit:
        basesvisit.add(nullrev)
    start = max(max(revsvisit), max(basesvisit))
    bothvisit = revsvisit.intersection(basesvisit)
    revsvisit.difference_update(bothvisit)
    basesvisit.difference_update(bothvisit)
    # At this point, we hold the invariants that:
    # - revsvisit is the set of nodes we know are an ancestor of at least one
    #   of the nodes in revs
    # - basesvisit is the same for bases
    # - bothvisit is the set of nodes we know are ancestors of at least one of
    #   the nodes in revs and one of the nodes in bases
    # - a node may be in none or one, but not more, of revsvisit, basesvisit
    #   and bothvisit at any given time
    # Now we walk down in reverse topo order, adding parents of nodes already
    # visited to the sets while maintaining the invariants. When a node is
    # found in both revsvisit and basesvisit, it is removed from them and
    # added to bothvisit instead. When revsvisit becomes empty, there are no
    # more ancestors of revs that aren't also ancestors of bases, so exit.

    missing = []
    for curr in xrange(start, nullrev, -1):
        if not revsvisit:
            break

        if curr in bothvisit:
            bothvisit.remove(curr)
            # curr's parents might have made it into revsvisit or basesvisit
            # through another path
            for p in pfunc(curr):
                revsvisit.discard(p)
                basesvisit.discard(p)
                bothvisit.add(p)
            continue

        # curr will never be in both revsvisit and basesvisit, since if it
        # were it'd have been pushed to bothvisit
        if curr in revsvisit:
            missing.append(curr)
            thisvisit = revsvisit
            othervisit = basesvisit
        elif curr in basesvisit:
            thisvisit = basesvisit
            othervisit = revsvisit
        else:
            # not an ancestor of revs or bases: ignore
            continue

        thisvisit.remove(curr)
        for p in pfunc(curr):
            if p == nullrev:
                pass
            elif p in othervisit or p in bothvisit:
                # p is implicitly in thisvisit. This means p is or should be
                # in bothvisit
                revsvisit.discard(p)
                basesvisit.discard(p)
                bothvisit.add(p)
            else:
                # visit later
                thisvisit.add(p)

    missing.reverse()
    return missing