changeset 21101:64911a12dc28

ancestors: extract candidates function as commonancestorsheads

--- a/mercurial/ancestor.py	Thu Apr 17 14:54:46 2014 +0200
+++ b/mercurial/ancestor.py	Thu Apr 17 19:49:56 2014 +0200
@@ -9,6 +9,62 @@
 import util
 from node import nullrev
 
+def commonancestorsheads(pfunc, *nodes):
+    """Returns a set with the heads of all common ancestors of all nodes,
+    heads(::nodes[0] and ::nodes[1] and ...) .
+
+    pfunc must return a list of parent vertices for a given vertex.
+    """
+    if not isinstance(nodes, set):
+        nodes = set(nodes)
+    if nullrev in nodes:
+        return set()
+    if len(nodes) <= 1:
+        return nodes
+
+    allseen = (1 << len(nodes)) - 1
+    seen = [0] * (max(nodes) + 1)
+    for i, n in enumerate(nodes):
+        seen[n] = 1 << i
+    poison = 1 << (i + 1)
+
+    gca = set()
+    interesting = len(nodes)
+    nv = len(seen) - 1
+    while nv >= 0 and interesting:
+        v = nv
+        nv -= 1
+        if not seen[v]:
+            continue
+        sv = seen[v]
+        if sv < poison:
+            interesting -= 1
+            if sv == allseen:
+                gca.add(v)
+                sv |= poison
+                if v in nodes:
+                    # history is linear
+                    return set([v])
+        if sv < poison:
+            for p in pfunc(v):
+                sp = seen[p]
+                if p == nullrev:
+                    continue
+                if sp == 0:
+                    seen[p] = sv
+                    interesting += 1
+                elif sp != sv:
+                    seen[p] |= sv
+        else:
+            for p in pfunc(v):
+                if p == nullrev:
+                    continue
+                sp = seen[p]
+                if sp and sp < poison:
+                    interesting -= 1
+                seen[p] = sv
+    return gca
+
 def ancestors(pfunc, *orignodes):
     """
     Returns the common ancestors of a and b that are furthest from a
@@ -16,57 +72,6 @@
 
     pfunc must return a list of parent vertices for a given vertex.
     """
-    if not isinstance(orignodes, set):
-        orignodes = set(orignodes)
-    if nullrev in orignodes:
-        return set()
-    if len(orignodes) <= 1:
-        return orignodes
-
-    def candidates(nodes):
-        allseen = (1 << len(nodes)) - 1
-        seen = [0] * (max(nodes) + 1)
-        for i, n in enumerate(nodes):
-            seen[n] = 1 << i
-        poison = 1 << (i + 1)
-
-        gca = set()
-        interesting = len(nodes)
-        nv = len(seen) - 1
-        while nv >= 0 and interesting:
-            v = nv
-            nv -= 1
-            if not seen[v]:
-                continue
-            sv = seen[v]
-            if sv < poison:
-                interesting -= 1
-                if sv == allseen:
-                    gca.add(v)
-                    sv |= poison
-                    if v in nodes:
-                        # history is linear
-                        return set([v])
-            if sv < poison:
-                for p in pfunc(v):
-                    sp = seen[p]
-                    if p == nullrev:
-                        continue
-                    if sp == 0:
-                        seen[p] = sv
-                        interesting += 1
-                    elif sp != sv:
-                        seen[p] |= sv
-            else:
-                for p in pfunc(v):
-                    if p == nullrev:
-                        continue
-                    sp = seen[p]
-                    if sp and sp < poison:
-                        interesting -= 1
-                    seen[p] = sv
-        return gca
-
     def deepest(nodes):
         interesting = {}
         count = max(nodes) + 1
@@ -123,7 +128,7 @@
             k |= i
         return set(n for (i, n) in mapping if k & i)
 
-    gca = candidates(orignodes)
+    gca = commonancestorsheads(pfunc, *orignodes)
 
     if len(gca) <= 1:
         return gca