view mercurial/ @ 4398:3b7e284b8f28

merge: expand and simplify the invalid handling for directory moves
author Matt Mackall <>
date Thu, 03 May 2007 17:24:43 -0500
parents eb0b4a2d70a9
line wrap: on
line source

# - generic DAG ancestor algorithm for mercurial
# Copyright 2006 Matt Mackall <>
# This software may be used and distributed according to the terms
# of the GNU General Public License, incorporated herein by reference.

import heapq

def ancestor(a, b, pfunc):
    return the least common ancestor of nodes a and b or None if there
    is no such ancestor.

    pfunc must return a list of parent vertices

    if a == b:
        return a

    # find depth from root of all ancestors
    visit = [a, b]
    depth = {}
    while visit:
        vertex = visit[-1]
        pl = pfunc(vertex)
        if not pl:
            depth[vertex] = 0
            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:
            if visit[-1] == vertex:
                depth[vertex] = min([depth[p] for p in pl]) - 1

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

    def generations(vertex):
        sg, s = None, {}
        for g, v in ancestors(vertex):
            if g != sg:
                if sg:
                    yield sg, s
                sg, s = g, {v:1}
                s[v] = 1
        yield sg, s

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

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