--- a/hgext3rd/evolve/obsdiscovery.py	Wed Mar 22 03:15:58 2017 +0100
+++ b/hgext3rd/evolve/obsdiscovery.py	Sat Mar 18 22:48:26 2017 +0100
@@ -50,12 +50,14 @@
 from . import (
     exthelper,
     utility,
+    stablerange,
 )
 
 _pack = struct.pack
 _unpack = struct.unpack
 
 eh = exthelper.exthelper()
+eh.merge(stablerange.eh)
 obsexcmsg = utility.obsexcmsg
 
 ##########################################
@@ -494,7 +496,7 @@
     revs = scmutil.revrange(repo, opts['rev'])
     # prewarm depth cache
     for r in repo.revs("::%ld", revs):
-        utility.depth(repo, r)
+        repo.stablerange.depthrev(repo, r)
     toproceed = [_range(repo, r, 0, ) for r in revs]
     ranges = set(toproceed)
     while toproceed:
@@ -553,7 +555,7 @@
 
     @util.propertycache
     def depth(self):
-        return utility.depth(self._repo, self.head)
+        return self._repo.stablerange.depthrev(self._repo, self.head)
 
     @util.propertycache
     def _revs(self):
@@ -570,7 +572,7 @@
         bottom = self._revs[:localindex]
         top = _range(self._repo, self.head, globalindex, self._revs[localindex:])
         #
-        toprootdepth = utility.depth(self._repo, top._revs[0])
+        toprootdepth = self._repo.stablerange.depthrev(self._repo, top._revs[0])
         if toprootdepth + len(top) == self.depth + 1:
             bheads = [bottom[-1]]
         else:
@@ -583,7 +585,7 @@
             #     assert 1 == len(self._repo.revs('roots(%ld)', top._revs))
         if len(bheads) == 1:
             newhead = bottom[-1]
-            bottomdepth = utility.depth(self._repo, newhead)
+            bottomdepth = self._repo.stablerange.depthrev(self._repo, newhead)
             newstart = bottomdepth - len(bottom)
             result.append(_range(self._repo, newhead, newstart, bottom))
         else:
@@ -592,7 +594,7 @@
             for h in bheads:
                 subset = cl.ancestors([h], inclusive=True)
                 hrevs = [r for r in bottom if r in subset]
-                start = utility.depth(self._repo, h) - len(hrevs)
+                start = self._repo.stablerange.depthrev(self._repo, h) - len(hrevs)
                 entry = _range(self._repo, h, start, [r for r in bottom if r in subset])
                 result.append(entry)
         result.append(top)

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hgext3rd/evolve/stablerange.py	Sat Mar 18 22:48:26 2017 +0100
@@ -0,0 +1,106 @@
+# Code dedicated to the computation and properties of "stable ranges"
+#
+# These stable ranges are use for obsolescence markers discovery
+#
+# Copyright 2017 Pierre-Yves David <pierre-yves.david@ens-lyon.org>
+#
+# This software may be used and distributed according to the terms of the
+# GNU General Public License version 2 or any later version.
+
+from mercurial import (
+    localrepo,
+    node as nodemod,
+)
+
+from . import (
+    exthelper,
+)
+
+eh = exthelper.exthelper()
+
+class stablerangecache(dict):
+
+    def __init__(self):
+        self._depthcache = {}
+
+    def depthrev(self, repo, rev):
+        cl = repo.changelog
+        cache = self._depthcache
+        nullrev = nodemod.nullrev
+        stack = [rev]
+        while stack:
+            revdepth = None
+            current = stack[-1]
+            revdepth = cache.get(current)
+            if revdepth is not None:
+                stack.pop()
+                continue
+            p1, p2 = cl.parentrevs(current)
+            if p1 == nullrev:
+                # root case
+                revdepth = 1
+            elif p2 == nullrev:
+                # linear commit case
+                parentdepth = cache.get(p1)
+                if parentdepth is None:
+                    stack.append(p1)
+                else:
+                    revdepth = parentdepth + 1
+            else:
+                # merge case
+                depth_p1 = cache.get(p1)
+                depth_p2 = cache.get(p2)
+                missingparent = False
+                if depth_p1 is None:
+                    stack.append(p1)
+                    missingparent = True
+                if depth_p2 is None:
+                    stack.append(p2)
+                    missingparent = True
+                if missingparent:
+                    continue
+                # computin depth of a merge
+                # XXX the common ancestors heads could be cached
+                ancnodes = cl.commonancestorsheads(cl.node(p1), cl.node(p2))
+                ancrevs = [cl.rev(a) for a in ancnodes]
+                anyunkown = False
+                ancdepth = []
+                for r in ancrevs:
+                    d = cache.get(r)
+                    if d is None:
+                        anyunkown = True
+                        stack.append(r)
+                    ancdepth.append((r, d))
+                if anyunkown:
+                    continue
+                if not ancrevs:
+                    # unrelated branch, (no common root)
+                    revdepth = depth_p1 + depth_p2 + 1
+                elif len(ancrevs) == 1:
+                    # one unique branch point:
+                    # we can compute depth without any walk
+                    depth_anc = ancdepth[0][1]
+                    revdepth = depth_p1 + (depth_p2 - depth_anc) + 1
+                else:
+                    # multiple ancestors, we pick one that is
+                    # * the deepest (less changeset outside of it),
+                    # * lowest revs because more chance to have descendant of other "above"
+                    anc, revdepth = max(ancdepth, key=lambda x: (x[1], -x[0]))
+                    revdepth += len(cl.findmissingrevs(common=[anc], heads=[current]))
+            if revdepth is not None:
+                cache[current] = revdepth
+                stack.pop()
+        # actual_depth = len(list(cl.ancestors([rev], inclusive=True)))
+        # assert revdepth == actual_depth, (rev, revdepth, actual_depth)
+        return revdepth
+
+@eh.reposetup
+def setupcache(ui, repo):
+
+    class stablerangerepo(repo.__class__):
+
+        @localrepo.unfilteredpropertycache
+        def stablerange(self):
+            return stablerangecache()
+
+    repo.__class__ = stablerangerepo

--- a/hgext3rd/evolve/utility.py	Wed Mar 22 03:15:58 2017 +0100
+++ b/hgext3rd/evolve/utility.py	Sat Mar 18 22:48:26 2017 +0100
@@ -4,7 +4,6 @@
 #
 # This software may be used and distributed according to the terms of the
 # GNU General Public License version 2 or any later version.
-from mercurial import node
 
 def obsexcmsg(ui, message, important=False):
     verbose = ui.configbool('experimental', 'verbose-obsolescence-exchange',
@@ -19,36 +18,3 @@
     if ui.configbool('experimental', 'verbose-obsolescence-exchange', False):
         topic = 'OBSEXC'
     ui.progress(topic, *args, **kwargs)
-
-_depthcache = {}
-def depth(repo, rev):
-    cl = repo.changelog
-    n = cl.node(rev)
-    revdepth = _depthcache.get(n, None)
-    if revdepth is None:
-        p1, p2 = cl.parentrevs(rev)
-        if p1 == node.nullrev:
-            revdepth = 1
-        elif p2 == node.nullrev:
-            revdepth = depth(repo, p1) + 1
-        else:
-            ancs = cl.commonancestorsheads(cl.node(p1), cl.node(p2))
-            depth_p1 = depth(repo, p1)
-            depth_p2 = depth(repo, p2)
-            if not ancs:
-                revdepth = depth_p1 + depth_p2 + 1
-            elif len(ancs) == 1:
-                anc = cl.rev(ancs[0])
-                revdepth = depth_anc = depth(repo, anc)
-                revdepth += depth_p1 - depth_anc
-                revdepth += depth_p2 - depth_anc
-                revdepth += 1
-            else:
-                # multiple ancestors, we pick the highest and search all missing bits
-                anc = max(cl.rev(a) for a in ancs)
-                revdepth = depth(repo, anc)
-                revdepth += len(cl.findmissingrevs(common=[anc], heads=[rev]))
-        _depthcache[n] = revdepth
-    # actual_depth = len(list(cl.ancestors([rev], inclusive=True)))
-    # assert revdepth == actual_depth, (rev, revdepth, actual_depth)
-    return revdepth