[PATCH 15 of 16] ancestors: return all ancestors - not just those who are furthest from a root

Mads Kiilerich mads at kiilerich.com
Sun Mar 2 13:15:48 CST 2014


# HG changeset patch
# User Mads Kiilerich <madski at unity3d.com>
# Date 1393278134 -3600
#      Mon Feb 24 22:42:14 2014 +0100
# Node ID ce8005617789415633a79cd654f788b6f8dd41f2
# Parent  2a40d688a6d74c7cf6aad31ed471098364ac73ad
ancestors: return all ancestors - not just those who are furthest from a root

Mercurial had a heuristic for picking the "greatest" among multiple "heads of
common ancestors". It was stable and optimized and worked, but:

* There could still be a tie where the caller had to use another heuristic for
  picking which one to use.
* Low level functions should be generic and without hardcoded policies.
* We do (also) want all the common ancestor heads at the higher levels.
* The algorithm for finding the greatest was complex in code and computation.

We thus trim the ancestors function so it no longer try to find the best heads
but return all of them.

This will only make a real difference in rare situations. The new and more
generic functionality for getting all the common ancestor heads can be used for
other purposes.

The lack of test suite changes shows that we don't have any test cases where
the special heuristic for picking the greatest common ancestor head makes any
difference (or that the high level heuristic of picking one arbitrarily is
just as good).

diff --git a/mercurial/ancestor.py b/mercurial/ancestor.py
--- a/mercurial/ancestor.py
+++ b/mercurial/ancestor.py
@@ -11,8 +11,8 @@ from node import nullrev
 
 def ancestors(pfunc, *orignodes):
     """
-    Returns the common ancestors of a and b that are furthest from a
-    root (as measured by longest path).
+    Returns a set with the heads of all common ancestors of all orignodes,
+    heads(::orignodes[0] and ::orignodes[1] and ...) .
 
     pfunc must return a list of parent vertices for a given vertex.
     """
@@ -67,67 +67,9 @@ def ancestors(pfunc, *orignodes):
                     seen[p] = sv
         return gca
 
-    def deepest(nodes):
-        interesting = {}
-        count = max(nodes) + 1
-        depth = [0] * count
-        seen = [0] * count
-        mapping = []
-        for (i, n) in enumerate(sorted(nodes)):
-            depth[n] = 1
-            b = 1 << i
-            seen[n] = b
-            interesting[b] = 1
-            mapping.append((b, n))
-        nv = count - 1
-        while nv >= 0 and len(interesting) > 1:
-            v = nv
-            nv -= 1
-            dv = depth[v]
-            if dv == 0:
-                continue
-            sv = seen[v]
-            for p in pfunc(v):
-                if p == nullrev:
-                    continue
-                dp = depth[p]
-                nsp = sp = seen[p]
-                if dp <= dv:
-                    depth[p] = dv + 1
-                    if sp != sv:
-                        interesting[sv] += 1
-                        nsp = seen[p] = sv
-                        if sp:
-                            interesting[sp] -= 1
-                            if interesting[sp] == 0:
-                                del interesting[sp]
-                elif dv == dp - 1:
-                    nsp = sp | sv
-                    if nsp == sp:
-                        continue
-                    seen[p] = nsp
-                    interesting.setdefault(nsp, 0)
-                    interesting[nsp] += 1
-                    interesting[sp] -= 1
-                    if interesting[sp] == 0:
-                        del interesting[sp]
-            interesting[sv] -= 1
-            if interesting[sv] == 0:
-                del interesting[sv]
-
-        if len(interesting) != 1:
-            return []
-
-        k = 0
-        for i in interesting:
-            k |= i
-        return set(n for (i, n) in mapping if k & i)
-
     gca = candidates(orignodes)
 
-    if len(gca) <= 1:
-        return gca
-    return deepest(gca)
+    return gca
 
 def genericancestor(a, b, pfunc):
     """
diff --git a/mercurial/parsers.c b/mercurial/parsers.c
--- a/mercurial/parsers.c
+++ b/mercurial/parsers.c
@@ -1288,162 +1288,8 @@ bail:
 }
 
 /*
- * Given a disjoint set of revs, return the subset with the longest
- * path to the root.
- */
-static PyObject *find_deepest(indexObject *self, PyObject *revs)
-{
-	const Py_ssize_t revcount = PyList_GET_SIZE(revs);
-	static const Py_ssize_t capacity = 24;
-	int *depth, *interesting = NULL;
-	int i, j, v, ninteresting;
-	PyObject *dict = NULL, *keys;
-	long *seen = NULL;
-	int maxrev = -1;
-	long final;
-
-	if (revcount > capacity) {
-		PyErr_Format(PyExc_OverflowError,
-			     "bitset size (%ld) > capacity (%ld)",
-			     (long)revcount, (long)capacity);
-		return NULL;
-	}
-
-	for (i = 0; i < revcount; i++) {
-		int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));
-		if (n > maxrev)
-			maxrev = n;
-	}
-
-	depth = calloc(sizeof(*depth), maxrev + 1);
-	if (depth == NULL)
-		return PyErr_NoMemory();
-
-	seen = calloc(sizeof(*seen), maxrev + 1);
-	if (seen == NULL) {
-		PyErr_NoMemory();
-		goto bail;
-	}
-
-	interesting = calloc(sizeof(*interesting), 2 << revcount);
-	if (interesting == NULL) {
-		PyErr_NoMemory();
-		goto bail;
-	}
-
-	if (PyList_Sort(revs) == -1)
-		goto bail;
-
-	for (i = 0; i < revcount; i++) {
-		int n = (int)PyInt_AsLong(PyList_GET_ITEM(revs, i));
-		long b = 1l << i;
-		depth[n] = 1;
-		seen[n] = b;
-		interesting[b] = 1;
-	}
-
-	ninteresting = (int)revcount;
-
-	for (v = maxrev; v >= 0 && ninteresting > 1; v--) {
-		int dv = depth[v];
-		int parents[2];
-		long sv;
-
-		if (dv == 0)
-			continue;
-
-		sv = seen[v];
-		index_get_parents(self, v, parents);
-
-		for (i = 0; i < 2; i++) {
-			int p = parents[i];
-			long nsp, sp;
-			int dp;
-
-			if (p == -1)
-				continue;
-
-			dp = depth[p];
-			nsp = sp = seen[p];
-			if (dp <= dv) {
-				depth[p] = dv + 1;
-				if (sp != sv) {
-					interesting[sv] += 1;
-					nsp = seen[p] = sv;
-					if (sp) {
-						interesting[sp] -= 1;
-						if (interesting[sp] == 0)
-							ninteresting -= 1;
-					}
-				}
-			}
-			else if (dv == dp - 1) {
-				nsp = sp | sv;
-				if (nsp == sp)
-					continue;
-				seen[p] = nsp;
-				interesting[sp] -= 1;
-				if (interesting[sp] == 0 && interesting[nsp] > 0)
-					ninteresting -= 1;
-				interesting[nsp] += 1;
-			}
-		}
-		interesting[sv] -= 1;
-		if (interesting[sv] == 0)
-			ninteresting -= 1;
-	}
-
-	final = 0;
-	j = ninteresting;
-	for (i = 0; i < (int)(2 << revcount) && j > 0; i++) {
-		if (interesting[i] == 0)
-			continue;
-		final |= i;
-		j -= 1;
-	}
-	if (final == 0)
-		return PyList_New(0);
-
-	dict = PyDict_New();
-	if (dict == NULL)
-		goto bail;
-
-	for (i = 0; i < revcount; i++) {
-		PyObject *key;
-
-		if ((final & (1 << i)) == 0)
-			continue;
-
-		key = PyList_GET_ITEM(revs, i);
-		Py_INCREF(key);
-		Py_INCREF(Py_None);
-		if (PyDict_SetItem(dict, key, Py_None) == -1) {
-			Py_DECREF(key);
-			Py_DECREF(Py_None);
-			goto bail;
-		}
-	}
-
-	keys = PyDict_Keys(dict);
-
-	free(depth);
-	free(seen);
-	free(interesting);
-	Py_DECREF(dict);
-
-	return keys;
-bail:
-	free(depth);
-	free(seen);
-	free(interesting);
-	Py_XDECREF(dict);
-
-	return NULL;
-}
-
-/*
- * Given a (possibly overlapping) set of revs, return the greatest
- * common ancestors: those with the longest path to the root.
+ * Given a (possibly overlapping) set of revs, return all the greatest
+ * common ancestors: heads(::a and ::b and ...)
  */
 static PyObject *index_ancestors(indexObject *self, PyObject *args)
 {
@@ -1522,11 +1368,8 @@ static PyObject *index_ancestors(indexOb
 	if (gca == NULL)
 		goto bail;
 
-	if (PyList_GET_SIZE(gca) <= 1) {
-		ret = gca;
-		Py_INCREF(gca);
-	}
-	else ret = find_deepest(self, gca);
+	ret = gca;
+	Py_INCREF(gca);
 
 done:
 	free(revs);


More information about the Mercurial-devel mailing list