changeset 26003:62371c539c89

revset: remove grandparent by using reachableroots

This patch is part of a series of patches to speed up the computation of
revset.reachableroots by introducing a C implementation. The main motivation
is to speed up smartlog on big repositories. At the end of the series, on our
big repositories the computation of reachableroots is 10-50x faster and
smartlog on is 2x-5x faster.

Before this patch, we had a custom computation for grandparent that was very
close to the idea of reacheablerooots. This patch expresses grandparent with
reachableroots to reduce the amount of code.

--- a/mercurial/graphmod.py	Fri Jun 19 20:18:54 2015 -0700
+++ b/mercurial/graphmod.py	Fri Jun 19 20:28:52 2015 -0700
@@ -22,7 +22,10 @@
 import heapq
 
 from .node import nullrev
-from . import util
+from . import (
+    revset,
+    util,
+)
 
 CHANGESET = 'C'
 
@@ -235,8 +238,6 @@
     if not revs:
         return
 
-    cl = repo.changelog
-    lowestrev = revs.min()
     gpcache = {}
 
     if repo.ui.configbool('experimental', 'graph-group-branches', False):
@@ -258,7 +259,7 @@
         for mpar in mpars:
             gp = gpcache.get(mpar)
             if gp is None:
-                gp = gpcache[mpar] = grandparent(cl, lowestrev, revs, mpar)
+                gp = gpcache[mpar] = revset.reachableroots(repo, revs, [mpar])
             if not gp:
                 parents.append(mpar)
             else:
@@ -356,24 +357,6 @@
         yield (cur, type, data, (col, color), edges)
         seen = next
 
-def grandparent(cl, lowestrev, roots, head):
-    """Return all ancestors of head in roots which revision is
-    greater or equal to lowestrev.
-    """
-    pending = set([head])
-    seen = set()
-    kept = set()
-    llowestrev = max(nullrev, lowestrev)
-    while pending:
-        r = pending.pop()
-        if r >= llowestrev and r not in seen:
-            if r in roots:
-                kept.add(r)
-            else:
-                pending.update([p for p in cl.parentrevs(r)])
-            seen.add(r)
-    return sorted(kept)
-
 def asciiedges(type, char, lines, seen, rev, parents):
     """adds edge info to changelog DAG walk suitable for ascii()"""
     if rev not in seen: