mercurial/ancestor.py

23331:3b1b8f25443e

    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)

23332:194508240dc9

    if not basesvisit:
        basesvisit.add(nullrev)
    start = max(max(revsvisit), max(basesvisit))
    bothvisit = revsvisit.intersection(basesvisit)
    revsvisit.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, and that are smaller
    #   than curr. bothvisit and revsvisit are mutually exclusive, but bothvisit
    #   is a subset of basesvisit.
    # 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 revsvisit and added
    # to bothvisit. 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 through another
            # path
            for p in pfunc(curr):
                revsvisit.discard(p)
                basesvisit.add(p)
                bothvisit.add(p)
            continue

        if curr in revsvisit:
            missing.append(curr)
            revsvisit.remove(curr)
            thisvisit = revsvisit
            othervisit = basesvisit
        elif curr in basesvisit:
            thisvisit = basesvisit
            othervisit = revsvisit
        else:
            # not an ancestor of revs or bases: ignore
            continue

        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.add(p)
                bothvisit.add(p)
            else:
                # visit later
                thisvisit.add(p)